Szacowanie średniej w czasie wielomianowym

Niech $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ będzie funkcją. Chcemy oszacować średnią $f$ ; to znaczy: $\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!)

Niech $E$ będzie (randomizowanym) algorytmem estymatora. Załóżmy, że $E$ ma dostęp do czarnej skrzynki do $f$ . Oznaczamy to przez $E^f$ .

Są dwa warunki:

1) Czas działania estymatora: Istnieje jeden wielomian $p(\cdot)$ taki, że dla wszystkich $n$ i wszystkich $f$ czas działania $E^f(1^n)$ jest ograniczony przez $\frac{p(n)}{\mathbb{E}[f(n)]}$ .

2) Precyzja estymatora z pewnością $\delta$ : Istnieje jeden wielomian $q(\cdot)$ , taki, że dla wszystkich $n$ i wszystkich $f$ mamy ${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$z prawdopodobieństwem co najmniej$\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.

Czy istnieją takie estymatory?

Tło i motywacja

Na początku nie wspomniałem o mojej motywacji, ponieważ wymaga ona dużej wiedzy podstawowej. W każdym razie, dla entuzjastów, krótko to opisuję: Potrzeba takich estymatorów powstaje w kontekście „Dowodów zdolności”, jak określono w następującym artykule:

Mihir Bellare, Oded Goldreich. Proving Computational Ability , 1992. Niepublikowany rękopis.

W szczególności na dole strony 5 autorzy domyślnie zakładali istnienie takich estymatorów (nie ma wzmianki o precyzji, a czas działania nie jest precyzyjnie określony; jednak kontekst jasno wszystko określa).

Moja pierwsza próba polegała na przeczytaniu „ Próbki próbników --- perspektywa obliczeniowa próbkowania ”. Dotyczy bardzo podobnego problemu, ale zdefiniowane prawdopodobieństwo błędu jest addytywne, podczas gdy nasze jest multiplikatywne. (Nie przeczytałem w pełni tego artykułu, może wspomina gdzieś, czego potrzebuję.)

EDYCJA (zgodnie z prośbą Tsuyoshi): W rzeczywistości definicja „Dowodu zdolności obliczeniowej” wymaga istnienia „ekstraktora wiedzy”, którego (oczekiwany) czas działania wynosi . Ponieważ nie znamyE[f(n)], chcemy to oszacować; nie może to jednak znacząco zmienić czasu działania: powinno zmienić go na czynnik wielomianowy. Warunek dokładności próbuje uchwycić takie wymaganie.$p(n) \over E[f(n)]$$E[f(n)]$

EDYCJA: Rozwiązuje to wersję problemu, w której f wyprowadza tylko 0 lub 1. Myślę jednak, że rozwiązanie można dostosować, aby działało w bardziej ogólnym przypadku.

Może źle zrozumiałem pytanie, ale nie wygląda to zbyt ostro.

Zamiast szacować średnią, zastanówmy się nad oszacowaniem liczby 1 i nazwijmy tę liczbę k. Niech . Więc średnia to k / N. Chcesz to oszacować w ramach wielomianowego współczynnika multiplikatywnego w czasie O (N polilog (N) / k).$N = 2^n$

Myślę, że można tego dokonać również w ramach dowolnego stałego współczynnika multiplikatywnego. Na przykład, powiedzmy, że chcesz to oszacować z dokładnością do 2. Współczynnik wyjściowy algorytmu będzie wynosił od k / 2 do 2k.$k'$

Naszkicuję algorytm, który powinien mieć odpowiedni czas działania. Najpierw sprawdź, czy k jest pomiędzy N / 2 a N. To łatwe, po prostu próbkuj kilka losowych wartości, a jeśli otrzymasz więcej niż połowę 1, to w tym przedziale. Masz więc przybliżenie 2. Jeśli nie, sprawdź, czy jest pomiędzy N / 4 a N / 2. I tak dalej. Za każdym razem, gdy zmniejszasz interwał, bardziej kosztowne jest oszacowanie, czy k leży w tym zakresie. Ale koszt jest odwrotnie proporcjonalny do tego, jak mały jest odstęp.

Na przykład, jeśli sprawdzasz, czy wartość k wynosi od do 2 N / 2 q , musisz wykonać zapytania dotyczące O ( 2 q ) . W każdym razie, po powtórzeniu tej procedury wystarczająco wiele razy, powinieneś otrzymać przedział, w którym k leży. Powiedz k leży pomiędzy N / 2 q a 2 N / 2 q . Zatem k wynosi około N / 2 q . Więc 2 $N/2^q$$2N/2^q$$O(2^q)$$N/2^q$$2N/2^q$$N/2^q$$2^q$dotyczy k / N. Na tym etapie wydawalibyśmy zapytania O (k / N). Ale przejście do tego kroku wymagało q innych kroków, ale to tylko dodatkowy czynnik polilog (N). Zatem całkowity czas pracy wynosi O (N polilog (N) / k), dla przybliżenia 2.

(W rzeczywistości należałoby wykonać wzmocnienie błędu, aby uzyskać przyzwoitą precyzję na każdym etapie. Ale to tylko dodatkowy czynnik polilogu).

Powodem, dla którego lubię o tym myśleć w tym kilkuetapowym procesie, jest podkreślenie tego procesu jako odgadnięcie i sprawdzenie precedensu. Jeśli ktoś powiedział ci, że wynosi od N / 2 q do 2 n / 2 q , możesz to oszacować z jeszcze większą dokładnością, znając ten fakt, w obiecanym czasie. Musimy więc wyeliminować etap zgadywania k . Odbywa się to poprzez wyszukiwanie binarne we wszystkich możliwych interwałach tego typu.$k$$N/2^q$$2n/2^q$$k$

Aby to zadziałało w przypadku wyjść innych niż boolowskie, zamiast zliczać liczbę 1, po prostu zsumuj widoczne wartości. Spróbuję znaleźć odniesienie, aby pokazać, że to działa rygorystycznie.

$f_1,f_2,\ldots$$f$$\{0,1\}^n$$k$$\sum_{i=1}^k f_i \ge M$$M$$M=polylog(n)$$M / k$

$k$$\mu$$E(f)$$k_{low}$$k_{high}$$\mu$$1 - \delta$$\sum_{i=1}^{k_{low}} f_i < M$ i $\sum_{i=1}^{k_{high}} f_i > M$. Te sumy$f_i$można ograniczyć za pomocą Chernoffa. Wynika, że$k_{low} < k < k_{high}$ with probability at least $1-\delta$ and therefore the estimator $M/k$ is well concentrated.