Memperkirakan Rata-rata dalam Waktu Polinomial

Biarkan menjadi fungsi. Kami ingin memperkirakan rata-rata ; yaitu: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$$f$$\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Biarkan menjadi algoritma penduga (acak). Asumsikan bahwa memiliki akses kotak hitam ke . Kami menyatakan ini oleh .E f E $E$$E$$f$$E^f$

Ada dua kondisi:

1) Waktu berjalan Pengukur: Ada satu polinomial sehingga untuk semua dan semua , waktu berjalan dibatasi oleh .n f E f ( 1 n ) p ( n $p(\cdot)$$n$$f$$E^f(1^n)$$\frac{p(n)}{\mathbb{E}[f(n)]}$

2) Ketelitian Estimator dengan keyakinan :$\delta$ Ada polinomial tunggal , sehingga untuk semua dan semua , kita memiliki dengan probabilitas setidaknya .n f $q(\cdot)$$n$$f$${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$$\delta$

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

Apakah ada penaksir seperti itu?

Latar Belakang dan Motivasi

Saya tidak menyebutkan motivasi saya di awal karena membutuhkan banyak pengetahuan latar belakang. Pokoknya, bagi para penggemar, saya jelaskan secara singkat: Kebutuhan akan penduga seperti itu muncul dalam konteks "Bukti Kemampuan," sebagaimana didefinisikan dalam artikel berikut:

Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Naskah tidak diterbitkan.

Khususnya, di bagian bawah halaman 5, penulis secara implisit mengasumsikan keberadaan estimator tersebut (Tidak ada ketepatan, dan waktu berjalan tidak didefinisikan secara tepat; namun konteksnya jelas mendefinisikan segalanya.)

Upaya pertama saya adalah membaca " Contoh Pengambil Sampel --- Perspektif Komputasi pada Pengambilan Sampel ." Ini berkaitan dengan masalah yang sangat mirip, namun probabilitas kesalahan yang didefinisikan adalah aditif, sedangkan kita adalah multiplikatif. (Saya tidak sepenuhnya membaca koran, mungkin itu menyebutkan apa yang saya butuhkan di suatu tempat.)

EDIT (sesuai permintaan Tsuyoshi): Faktanya, definisi "Bukti Kemampuan Komputasi" mensyaratkan adanya "ekstraktor pengetahuan" yang waktu berjalan (yang diharapkan) adalah . Karena kita tidak tahu , kami ingin memperkirakannya; namun ini tidak boleh mengubah waktu berjalan secara signifikan: itu harus mengubahnya hingga faktor polinomial. Kondisi presisi mencoba menangkap persyaratan tersebut. E[f(n)$p(n) \over E[f(n)]$$E[f(n)]$

EDIT: Ini memecahkan versi masalah di mana f hanya menghasilkan 0 atau 1. Tapi saya pikir solusinya dapat disesuaikan untuk membuatnya berfungsi untuk kasus yang lebih umum.

Mungkin saya salah paham pertanyaannya, tetapi ini tidak terlihat terlalu sulit.

Alih-alih memperkirakan, rata-rata, mari kita berpikir memperkirakan jumlah 1s, dan memanggil nomor itu k. Misalkan . Jadi rata-rata adalah k / N. Anda ingin memperkirakan ini dalam faktor multiplikasi polinomial dalam waktu O (N polylog (N) / k).$N = 2^n$

Saya pikir ini dapat dilakukan untuk faktor multiplikasi yang konstan juga. Sebagai contoh, katakanlah Anda ingin memperkirakan ini dalam faktor 2. Jadi output dari algoritma akan berada di antara k / 2 dan 2k.$k'$

Saya akan membuat sketsa algoritma, yang seharusnya memiliki waktu berjalan yang sesuai. Pertama periksa apakah k adalah antara N / 2 dan N. Ini mudah, sampel saja beberapa nilai acak dan jika Anda mendapatkan lebih dari setengah 1s, maka itu dalam interval ini. Jadi, Anda memiliki 2-aproksimasi. Jika tidak, periksa apakah berada di antara N / 4 dan N / 2. Dan seterusnya. Setiap kali Anda membuat interval lebih kecil, akan lebih mahal untuk memperkirakan apakah k terletak pada rentang itu. Tetapi biaya berbanding terbalik dengan seberapa kecil intervalnya.

Misalnya, jika Anda memeriksa apakah k berada di antara dan , maka Anda perlu membuat pertanyaan tentang . Bagaimanapun, setelah mengulangi prosedur ini cukup banyak, Anda harus mendapatkan interval di mana k berada. Katakan k terletak di antara dan . Maka k kira-kira . Jadi adalah tentang k / N. Jadi pada langkah ini kita akan menghabiskan kueri O (k / N). Tetapi untuk sampai ke langkah ini diperlukan q langkah lain, tetapi itu hanya faktor polylog (N) tambahan. Jadi waktu menjalankan keseluruhan adalah O (N polylog (N) / k), untuk perkiraan 2.$N/2^q$$2N/2^q$$O(2^q)$$N/2^q$$2N/2^q$$N/2^q$$2^q$

(Seseorang sebenarnya harus melakukan amplifikasi kesalahan untuk mendapatkan presisi yang layak di setiap langkah. Tapi itu hanya faktor polylog tambahan.)

Alasan saya suka memikirkannya dalam beberapa tahap proses ini adalah karena ia menyoroti proses tersebut sebagai perkiraan dan memeriksa prasyarat. Jika seseorang memberi tahu Anda bahwa adalah antara dan , maka Anda dapat memperkirakannya dengan ketepatan yang lebih baik dengan mengetahui fakta ini, dalam batas waktu yang dijanjikan. Jadi kita perlu menghilangkan langkah diberi tebakan untuk . Ini dilakukan dengan pencarian biner pada semua interval yang mungkin dari tipe itu.$k$$N/2^q$$2n/2^q$$k$

Untuk membuat ini berfungsi untuk kasus keluaran non-boolean, alih-alih menghitung jumlah 1, hanya menjumlahkan nilai yang terlihat. Saya akan mencoba mencari referensi untuk menunjukkan bahwa ini bekerja dengan keras.

Misalkan menunjukkan nilai f yang diterapkan pada urutan tak terbatas dari sampel acak (dengan penggantian) dari { 0 , 1 } n . Biarkan k menjadi yang paling bilangan bulat positif sehingga Σ k i = 1 f i ≥ M untuk beberapa nilai M , mungkin M = p o l y l o g ( n ) . Saya akan menebak bahwa estimator M $f_1,f_2,\ldots$$f$$\{0,1\}^n$$k$$\sum_{i=1}^k f_i \ge M$$M$$M=polylog(n)$ harus mencapai apa yang Anda inginkan.$M / k$

Untuk analisis Anda tidak dapat menerapkan batas Chernoff langsung ke variabel acak tetapi ada trik untuk memungkinkan Anda menggunakan Chernoff pula. Biarkan μ menunjukkan ekspektasi E ( f ) yang tidak diketahui . Tentukan konstanta k l o w dan k h i g h (fungsi μ ) sehingga dengan probabilitas setidaknya 1 - δ kita memiliki ∑ k l o w i = 1 f i < M dan ∑ k $k$$\mu$$E(f)$$k_{low}$$k_{high}$$\mu$$1 - \delta$$\sum_{i=1}^{k_{low}} f_i < M$. Jumlahfis dapat dibatasi menggunakan Chernoff. Oleh karena ituklow<k<khighdengan probabilitas setidaknya1-δdan oleh karena itu estimatorM/kbaik terkonsentrasi.$\sum_{i=1}^{k_{high}} f_i > M$$f_i$$k_{low} < k < k_{high}$$1-\delta$$M/k$