Konsentrasi yang tajam untuk seleksi melalui partisi acak?

Algoritma sederhana yang biasa untuk menemukan elemen median dalam array dari bilangan adalah: $A$ $n$

Contoh elemen dari dengan penggantian ke $n^{3/4}$ $A$ $B$
Urutkan dan temukan pangkat elemen dan dari $B$ $|B|\pm \sqrt{n}$ $l$ $r$ $B$
Periksa bahwa dan berada di sisi berlawanan dari median dan bahwa ada paling banyak elemen di antara dan untuk beberapa konstanta . Gagal jika ini tidak terjadi. $l$ $r$ $A$ $C\sqrt{n}$ $A$ $l$ $r$ $C > 0$
Jika tidak, temukan median dengan mengurutkan elemen-elemen $A$ antara $l$ dan $r$

Tidak sulit untuk melihat bahwa ini berjalan dalam waktu linier dan berhasil dengan probabilitas tinggi. (Semua peristiwa buruk adalah penyimpangan besar dari harapan binomial.)

Algoritme alternatif untuk masalah yang sama, yang lebih alami untuk diajarkan kepada siswa yang telah melihat pengurutan cepat adalah yang dijelaskan di sini: Pilihan Acak

Juga mudah untuk melihat bahwa yang ini memiliki waktu berjalan yang diharapkan secara linier: katakan bahwa "putaran" adalah urutan panggilan rekursif yang berakhir ketika seseorang memberikan 1 / 4-3 / 4 split, dan kemudian amati bahwa panjang yang diharapkan dari putaran paling banyak 2. (Pada undian pertama ronde, probabilitas mendapatkan split yang baik adalah 1/2 dan kemudian setelah benar-benar meningkat, karena algoritma itu dijelaskan sehingga panjang bulat didominasi oleh variabel acak geometris.)

Jadi sekarang pertanyaannya:

Apakah mungkin untuk menunjukkan bahwa pemilihan acak berjalan dalam waktu linier dengan probabilitas tinggi?

Kami memiliki putaran , dan setiap putaran memiliki panjang setidaknya dengan probabilitas paling banyak , sehingga ikatan gabungan menyatakan bahwa waktu operasinya adalah dengan probabilitas . $O(\log n)$ $k$ $2^{-k+1}$ $O(n\log\log n)$ $1-1/O(\log n)$

Ini agak tidak memuaskan, tapi apakah ini benar?

algorithms algorithm-analysis randomized-algorithms Louis
sumber

Harap jelaskan algoritma mana yang dirujuk pertanyaan Anda.

Raphael

Apakah Anda bertanya apakah Anda menerapkan ikatan Anda dengan benar, atau apakah ada ikatan yang lebih baik dan lebih memuaskan?

Joe

@ Jo. Yang terakhir. Intinya adalah bahwa putaran adalah artefak untuk mendapatkan bahwa panjang putaran didominasi oleh geometris. Kemudian anaylisys "lupa" apakah algoritma di depan atau di belakang yang selalu mendapat 1 / 4-3 / 4 split pada hidung untuk membuat geometrik independen. Saya bertanya apakah "kecurangan" ini seperti yang Yuval letakkan di bawah masih ketat.

Louis

Jawaban:

$\Theta(n)$ $G(1/2)$ $p(n) \longrightarrow 0$ $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$ $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

(Ada beberapa kecurangan yang terlibat, karena panjang putaran pertama tidak benar-benar . Analisis yang lebih cermat mungkin atau mungkin tidak memvalidasi jawaban ini.) $G(1/2)$

Sunting: Grübel dan Rosler membuktikan bahwa jumlah perbandingan yang diharapkan dibagi dengan cenderung (dalam arti tertentu) ke beberapa batas distribusi, yang tidak terikat. Lihat misalnya makalah Grübel "Algoritme pemilihan Hoare: pendekatan rantai Markov", yang mereferensikan makalah asli mereka. $n$

Yuval Filmus
sumber

Inilah hal yang menggangguku. Seperti yang saya katakan di komentar saya di atas, putaran hanyalah cara untuk menganalisis versi "melambat" dari algoritma yang menunggu sampai mendapat poros yang cukup baik untuk melanjutkan. Apa yang Anda tunjukkan adalah bahwa untuk setiap

tetap

probabilitas putaran pertama yang membutuhkan lebih dari

pivot adalah

. Tapi, pada prinsipnya, putaran pertama yang panjang bisa diimbangi dengan putaran ke-2 yang kosong, dalam arti bahwa pada akhirnya, algoritma "un-slowed" menyusul yang selalu mendapatkan 1 / 4-3 / 4 split .

C > 0

$C>0$

C

$C$

> 0

$>0$

Louis

Itu tidak benar, jika putaran pertama panjang maka seluruh waktu berjalan panjang, karena putaran selanjutnya tidak dapat mengurangi waktu berjalan. Intinya adalah bahwa untuk setiap , putaran pertama membutuhkan waktu setidaknya dengan beberapa probabilitas konstan .

C

$C$

C n

$Cn$

p_{C} > 0

$p_C > 0$

Yuval Filmus

Saya lebih bahagia sekarang, karena panjang bulat tidak jauh lebih kecil dari geometris yang digunakan untuk batas atas. Saya kira inilah yang membuat G&R gegabah. Jawaban bagus.

Louis