Temukan perkiraan argmax hanya dengan menggunakan perkiraan kueri maks

Pertimbangkan masalah berikut.

Ada $n$ nilai yang tidak diketahui $v_1, \cdots, v_n \in \mathbb{R}$ . Tugasnya adalah menemukan indeks yang terbesar hanya menggunakan kueri dari formulir berikut. Kueri ditentukan oleh himpunan $S \subseteq \{1,\cdots,n\}$ dan jawaban yang sesuai adalah $\max_{i \in S} v_i$ . Tujuannya adalah menggunakan pertanyaan sesedikit mungkin.

Masalah ini mudah: Kita dapat menggunakan pencarian biner untuk menemukan argmax dengan kueri . yaitu Membangun pohon biner lengkap dengan daun sesuai dengan indeks. Mulai dari akar dan berjalan ke daun sebagai berikut. Di setiap node, kueri nilai maksimum di subtree kanan dan kiri dan kemudian pindah ke anak di samping dengan jawaban yang lebih besar. Setelah mencapai daun, output indeksnya.$O(\log n)$$n$

Versi berisik berikut dari masalah ini telah muncul dalam penelitian saya.

Ada nilai yang tidak diketahui . Ini dapat diakses dengan kueri di mana set ditentukan dan sampel dari dikembalikan. Tujuannya adalah untuk mengidentifikasi i ∗ ∈ { 1 , ⋯ , n } sedemikian rupa sehingga E [ v i ∗ ] ≥ max i v i - 1 menggunakan pertanyaan sesedikit mungkin. (Harapannya lebih dari pilihan i ∗ v 1 , ⋯ , v n S ⊆ { 1 , ⋯ , n } N ( maks i ∈ S v i , 1 $n$$v_1, \cdots, v_n$$S \subseteq \{1, \cdots, n\}$$\mathcal{N}(\max_{i \in S} v_i,1)$$i_* \in \{1, \cdots, n\}$$\mathbb{E}[v_{i_*}] \geq \max_i v_i - 1$$i_*$, yang bergantung pada koin algoritme dan jawaban kueri berisik.)

Misalkan kita mencoba menyelesaikan ini menggunakan strategi pencarian biner yang sama seperti sebelumnya (tetapi dengan jawaban yang berisik). Cukup mudah untuk menunjukkan bahwa ini mencapai dan ini ketat dalam kasus terburuk. Kita dapat mengurangi kesalahan ke 1 yang diinginkan dengan mengulangi setiap permintaan O ( log 2 n ) kali dan menggunakan rata-rata (yang menurunkan varians). Ini memberikan algoritma menggunakan kueri O ( log 3 n ) .$\mathbb{E}[v_{i_*}] \geq \max_i v_i - O(\log n)$$1$$O(\log^2 n)$$O(\log^3 n)$

Apakah ada algoritma yang lebih baik? Saya menduga bahwa query sudah cukup. Dan saya percaya saya bisa membuktikan batas bawah Ω ( log 2 n ) . Juga, masalahnya menjadi mudah - yaitu ˜ O ( log n ) permintaan melalui pencarian biner - dengan janji bahwa ada Ω ( 1 ) kesenjangan antara nilai terbesar dan nilai terbesar kedua. Jika ini membantu, Anda dapat mengasumsikan semua nilai berada di antara 0 dan O ( log n ) .$O(\log^2 n)$$\Omega(\log^2 n)$$\tilde{O}(\log n)$$\Omega(1)$$0$$O(\log n)$

Komentar yang diperluas dari satu atau dua ide menuju batas bawah. Misalkan , katakan (meskipun pilihan terbaik mungkin berbeda), dan biarkan { v 1 , ... , v n } = { $B = \Theta(\log n)$. Pertimbangkan untuk menggambar input dengan memilih permutasi nilai-nilai ini secara seragam secara acak.$\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$

Idenya adalah bahwa jika kita memperbaiki indeks semua nilai kecuali untuk nilai dan n - $B$, maka kita harus dapat menunjukkan perbedaan dalam probabilitas algoritma untuk memilih satu dibandingkan yang lain sangat kecil: Jarak variasi antara hasil permintaan algoritma sangat kecil mengingat distribusi 50-50 pada penugasan ini nilai ke dua indeks yang tersedia dan hasil dari setiap urutan kueri.$\frac{n-1}{n}B$

Argumen ini berlaku untuk setiap pasangan nilai yang berdekatan, jadi kami mendapatkan rantai kendala pada probabilitas algoritma memilih nilai tertinggi, tertinggi kedua, ... Ini memberikan batas atas pada nilai yang diharapkan dari algoritma, jadi kami menetapkan batas atas ke dan melihat berapa jumlah kueri yang harus.$B-1$

$\log n$$(\log n)^2$

$\frac{B}{n}$

Maaf ini setengah matang, tapi semoga bermanfaat!