Batas bawah pada estimasi

Saya ingin tahu (terkait dengan pertanyaan lain ini ) apakah batas bawah diketahui untuk masalah pengujian berikut: seseorang diberi akses permintaan ke urutan nomor non-negatif $a_n \geq \dots\geq a_1$ dan $\varepsilon \in (0,1)$ , dengan janji bahwa $\sum_{k=1}^n a_k = 1$ atau $\sum_{k=1}^n a_k \leq 1-\varepsilon$ .

Berapa banyak query (pencarian) yang cukup dan diperlukan untuk (adaptif) algoritma acak untuk membedakan antara dua kasus, dengan probabilitas setidaknya $2/3$ ?

Saya telah menemukan posting sebelumnya yang memberikan batas atas logaritmik (dalam $n$ ) untuk masalah terkait perkiraan jumlah, dan kira-kira pencocokan batas bawah pada masalah itu untuk algoritma deterministik; tetapi tidak dapat menemukan hasil untuk masalah spesifik yang saya pertimbangkan (khususnya, algoritma acak).

Sunting: Mengikuti jawaban di bawah ini, saya kira saya seharusnya lebih jelas: di atas (dan khususnya dalam asimptotik untuk batas bawah), $n$ adalah kuantitas "utama" yang terlihat sebagai tak terhingga, sedangkan $\varepsilon$ adalah (sewenang-wenang kecil) ) konstan.

Inilah batas bawah yang bisa saya tunjukkan. Aku dugaan bahwa untuk tetap , hak batas bawah adalah Ω ( log n ) , tapi tentu saja aku mungkin salah.$\epsilon$$\Omega( \log n)$

Saya akan menggunakan urutan menurun (hanya untuk kenyamanan). Mekanisme dasarnya adalah memecah urutan menjadi blok Dalam blok ke- i akan ada elemen n i (yaitu, β i n i = n ).$L$$i$$n_i$$\sum_i n_i = n$

Berikut ini, kami ingin algoritma berhasil dengan probabilitas , untuk beberapa parameter δ > 0 .$\geq 1-\delta$$\delta >0$

Batas bawah pertama: .$\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$

The blok th memiliki n i = 2 i - 1 elemen, sehingga L = lg n . Kami menetapkan nilai semua elemen di blok ke - i menjadi ( 1 + X i ) / ( 2 n i L ) , di mana X i adalah variabel yang bernilai 0 atau 1 . Jelas, jumlah total urutan ini adalah α = L Σ i = 1 1 + $i$$n_i = 2^{i-1}$$L = \lg n$$i$$(1+X_i)/(2n_iL)$$X_i$$0$$1$ Bayangkan memilih setiapXidengan probabilitasβmenjadi1dan0sebaliknya. Untuk memperkirakanα, kita membutuhkan estimasiβ yangandal. Dalam partikulat, kami ingin dapat membedakan basisβ=1-4ϵdan, katakanlah,β=1.

Sekarang, bayangkan sampel dari variabel-variabel acak, dan biarkan Z 1 , ... , Z m menjadi variabel sampel. Pengaturan Y = ∑ m i = 1 ( 1 - X i ) (perhatikan, bahwa kami mengambil jumlah variabel komplemen ), kami memiliki μ = E [ Y ] = ( 1 - β ) m , dan ketidaksamaan Chernoff memberi tahu kami bahwa jika β = 1 - $m$$Z_1, \ldots, Z_m$$Y = \sum_{i=1}^m (1-X_i)$$\mu = E[Y] = (1-\beta) m$ , maka μ = 4 ε m , dan probabilitas kegagalan adalah P [ Y ≤ 2 ε m ] = P [ Y ≤ ( 1 - 1 / 2 ) μ ] ≤ exp ( - μ ( 1 / 2 ) 2 / 2 ) = exp ( - ϵ m / 2 ) . Untuk membuat jumlah ini lebih kecil dari$\beta =1-4\epsilon$$\mu = 4\epsilon m$

Pengamatan utama adalah bahwa ketimpangan Chernoff ketat (kita harus hati-hati, karena tidak benar untuk semua parameter, tetapi itu benar dalam hal ini), sehingga Anda tidak dapat melakukan lebih baik dari itu (hingga konstanta).

Batas bawah kedua: .$\Omega( \log n / \log \log n)$

Mengatur th ukuran blok menjadi n i = L i , di mana L = Θ ( log n / log log n ) adalah jumlah blok. Elemen dalam blok ke- i memiliki nilai α i = ( 1 / L ) / n i . Jadi jumlah total nilai dalam urutan adalah 1 .$i$$n_i = L^i$$L = \Theta( \log n / \log \log n)$$i$$\alpha_i = \Bigl(1/L\Bigr)/n_i$$1$

Sekarang, kita mungkin memutuskan untuk memilih blok arbitrer, katakan yang , dan set semua nilai dalam bloknya menjadi α j - 1 = L α j (bukan α j ). Ini meningkat kontribusi dari j th blok dari 1 / L untuk 1 , dan meningkatkan massa total urutan ke (hampir) 2 .$j$$\alpha_{j-1} = L \alpha_j$$\alpha_j$$j$$1/L$$1$$2$

Sekarang, secara informal, algoritma acak apa pun harus memeriksa nilai di masing-masing blok. Karena itu, ia harus membaca setidaknya nilai dari urutan.$L$

Untuk membuat argumen di atas lebih formal, dengan probabilitas , memberikan urutan asli dari massa 1 sebagai input (kita sebut ini sebagai masukan asli). Jika tidak, pilih secara acak blok yang memiliki nilai tambah (input yang dimodifikasi). Jelas, jika algoritma acak membaca kurang dari, katakanlah, L / 8 entri, ia memiliki probabilitas (kira-kira) 1 / 8 untuk mendeteksi input dimodifikasi. Dengan demikian, probabilitas algoritma ini gagal, jika membaca kurang dari entri L / 8 setidaknya ( 1 - p ) ( 7 $p=1/2$$1$$L/8$$1/8$$L/8$

PS Saya pikir dengan lebih berhati-hati tentang parameter, batas bawah pertama dapat ditingkatkan menjadi .$\Omega(1/\epsilon^2)$

Batas bawah

$\Omega(1/\sqrt{\epsilon})$

$a_1,\dots,a_n$$\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$$n$$a_1+\dots+a_n = 1$$n \approx 1/\sqrt{2\epsilon}$

Sekarang buat urutan baru $a'_1,\dots,a'_n$$\epsilon$$a'_1=a_1$$a'_2=a_2$$a'_i = a_i - \epsilon$$a'_1 + \dots + a'_n = 1-\epsilon$

$a_1,\dots,a_n$$a'_1,\dots,a'_n$$i$$\Omega(n)$$n \approx 1/\sqrt{2\epsilon}$$\Omega(1/\sqrt{\epsilon})$

Batas atas

$O(\lg(n/\epsilon) [\lg n + 1 / \epsilon^2])$

$[0,1]$

$a_i$$a_i$$a_i$$[\ell,u]$$i,j$$a_i,\dots,a_j \in [\ell,u]$$O(\lg(n/\epsilon))$

Sekarang, kami akan memperkirakan jumlah nilai di setiap rentang. Rentang pertama akan ditangani secara terpisah dari yang lainnya:

• $[0,0.25\epsilon/n)$$0$$m \times 0.25\epsilon/n$$m$$m \le n$$0.25 \epsilon$

• $\delta$$O(1/\delta^2)$$2 \times$$\delta = 0.25 \epsilon$

$0.25 \epsilon$$0.25 \epsilon$$\le 0.5 \epsilon$$1$$1-\epsilon$