Jaki jest najlepszy sposób na uzyskanie rzutu monetą zbliżoną do uczciwej z identycznych monet tendencyjnych?

21

(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą jest zobowiązany.)

Załóżmy, że mamy $n$ identycznych monet o nastawieniu $\delta=P[Head]-P[Tail]$ . Celem jest symulacja jednego rzutu monetą przy jednoczesnym zminimalizowaniu stronniczości.

Symulacja musi być wydajna w następującym znaczeniu: Algorytm działający w czasie wielomianowym sprawdza $n$ losowych bitów i wysyła pojedynczy bit. Odchylenie algorytmu jest określony jako $Bias(A)=|E[A=0]-E[A=1]|$ gdzie oczekiwane jest przejęcie rozkładu określonego przez $n$ bitów ${x_1,\ldots,x_n}$ takich, że $Prob[x_i=1]-Prob[x_i=0]=\delta$ .

Który algorytm działa w czasie wielomianowym ma najmniejszego odchylenia ? $A$ $Bias(A)$

To pytanie wydaje mi się bardzo naturalne i jest bardzo prawdopodobne, że zostało wcześniej rozważone.

Co wiadomo na temat tego problemu? Czy coś wiadomo, kiedy słabszy klasy (w $AC_0$ , itd.) Algorytmów jest brane pod uwagę?

cc.complexity-theory circuit-complexity pr.probability Hrushikesh
źródło

15

Rzucanie n stronniczymi monetami i przyjmowanie parzystości głów zbliża się wykładniczo do . $\frac{1}{2}$

[Jako dowód, rozważ losową zmienną, która wynosi -1, gdy główki i 1, gdy ogony, wtedy prawdopodobieństwo, że istnieje nieparzysta liczba głów, to tylko ] $E\left[\frac{1}{2} + \frac{1}{2}\prod_i X_i\right] = \frac{1}{2} + \frac{1}{2}\delta^n$

Być może jest to również optymalne z następującego powodu. Niech będzie dowolną funkcją kompozycji tych bitów. Następnie a najlepszym wydaje się być funkcja parzystości (prawda?). $f$ $\text{Bias}(f) = \sum_S \hat{f}(S) \delta^{|S|}$ $f$

Jeśli interesują Cię funkcje kompozycyjne o mniejszej złożoności, być może artykuł Ryana O'Donnella na temat „Wzmocnienia twardości w NP” byłby bardzo odpowiedni. Tam wykorzystuje funkcje kompozycji monotonicznej do wzmocnienia twardości, a funkcje, które działają, charakteryzują się wrażliwością na hałas.

Ramprasad
źródło

Czy mógłbyś uprzejmie wyjaśnić, dlaczego parzystość powinna być najlepszą funkcją? (A także, że nie ma znaczenia znacznie asymptotycznie, ale nie powinno być ono

w rozwoju Fouriera od

?). Dzięki za wskaźnik do papieru!

d e l t a^{| S |}

$delta^{|S|}$

E [x_{i}] = δ

$E[x_i]=\delta$

Hrushikesh

Och przepraszam, masz rację. Wyrażenie było niepoprawne i teraz je poprawiono. Nie ma dowodów na optymalność (może to nie jest optymalne), ale przyczyną zgadywałam tak, że to być ważne, jeśli ekspresja była zamiast

ponieważ jest to kombinacja wypukła.

\sum_{S} \hat{f} (S)^{2} δ^{| S |}

$\sum_S \hat{f}(S)^2 \delta^{|S|}$

Ramprasad

Być może może to rzucić nieco światła. Przez Cauchy'ego-Schwarza, wiemy, że

. Jednym ze sposobów optymalizacji byłoby zminimalizowanie górnej granicy tak bardzo, jak to możliwe, i dzieje się tak, gdy funkcja

jest funkcją parzystości, a w takim przypadku ilość, którą jesteśmy zainteresowani, odpowiada również górnej granicy. Jednak może się zdarzyć, że wektor współczynników Fouriera jest całkowicie ortogonalny do wektora

w którym to przypadku LHS jest po prostu zero! Czy są jakieś specjalne wartości

dla których znamy takie przykłady?

\sum_{S} \hat{f} (S) \leq \sqrt{\sum_{S : \hat{f} (S) \neq 0} δ^{2 | S |}}

$\sum_{S} \hat{f}(S) \leq \sqrt{\sum_{S:\hat{f}(S)\neq 0} \delta^{2|S|}}$

f

$f$

δ

$\delta$

δ

$\delta$

Ramprasad

Faktycznie, jeśli jeden z nich ma pewne nietrywialne monotonicznym funkcji

, a następnie w

oczekiwaniem prawdopodobieństwo

wynosi 0, a przy

to

. Dlatego dla niektórych pośrednich

musi przyjąć wartość

f

$f$

δ = - 1

$\delta = -1$

f (x_{1}, \dots, x_{n}) = 1

$f(x_1,\cdots, x_n) = 1$

δ = 1

$\delta=1$

1

$1$

δ

$\delta$

. Dlatego niesprawiedliwe jest oczekiwanie, że dla każdego

funkcja parzystości jest optymalna.

\frac{1}{2}

$\frac{1}{2}$

δ

$\delta$

Ramprasad

Czy możesz wyjaśnić ostatni komentarz bardziej szczegółowo? Pomijając kwestie złożoności F, a nie to prawdą tylko wtedy, gdy wniosek

dla

E [f] = 1 / 2

$E[f]=1/2$

ponieważ parzystość przyjmuje odchylenie od

do

?

δ \geq \frac{1}{2^{1 / n}}

$\delta \geq \frac{1}{2^{1/n}}$

δ

$\delta$

δ^{n}

$\delta^n$

Hrushikesh

12

Nie mów, czy uprzedzenie jest znane czy nieznane. Magia algorytmu von Neumanna polega na tym, że działa on w obu przypadkach.

Załóżmy, że jest to znane. Najlepsza odpowiedź zależy zatem krytycznie od liczbowo teoretycznych cech błędu. Weźmy p = 2/3. Rzuć monetą dwa razy i zamapuj HH na 0, a TH i HT na 1, powtarzając eksperyment, jeśli wynikiem jest TT. Wówczas 0 i 1 są jednakowo prawdopodobne, a szansa na powtórzenie wynosi tylko 1/9 zamiast 5/9 z algorytmem von Neumanna. Lub, ujmując to terminem, odchylenie jednego z wyników wynosi tylko 1/9, jeśli limit iteracji wynosi 2.

Wszystko to jest ściśle związane z teorią informacji i teorią kodowania. Gdy p jest ułamkiem o bardziej skomplikowanym liczniku i mianowniku, najlepszy algorytm będzie wymagał dłuższej długości bloku niż 2. Możesz użyć argumentu istnienia w stylu Shannona, aby pokazać, że dla danego błędu istnieje procedura, która jest tak optymalna jak chcesz, ale długość bloku może być bardzo duża.

Peres w swojej pracy „ Iterating von von Neumann's Procedury for Extracting Random Bits” dowodzi, że wersja algorytmu von Neumanna może dowolnie zbliżyć się do granicy Shannona. Wygląda na to, że wiele pracy w tej dziedzinie wykonali teoretycy informacji i statystycy, więc nie mogę wymyślić żadnej pracy o nachyleniu teoretycznym złożoności, która dałaby ci bezpośrednią odpowiedź na twoje pytanie.

Istnieje problem związany z zabawą, który stawia przeciwne pytanie: jeśli masz źródło uczciwych bitów, w jaki sposób wydajnie generujesz równomierny rozkład w pewnym zestawie innym niż potęga dwóch? Ograniczona do iteracji wersja problemu podobnego do twojego pytania prosi o maksymalizację entropii (tzn. Aby rozkład był jak najbardziej równomierny) za pomocą rzutów uczciwej monety.

Per Vognsen
źródło

1

Przyszło mi do głowy, że optymalizacja czasu działania bez uprzedzeń (to, co robi papier) jest Lagrange dual w stosunku do optymalizacji obciążenia zależnego od czasu działania. Myślę więc, że ten papier faktycznie odpowiada na twoje pytanie!

Per Vognsen,

5

Wolę myśleć o tym pytaniu w następującej uogólnionej formie: mamy pełne drzewo binarne wysokości n, w którym każdemu węzłowi przypisana jest liczba st suma liczb wynosi 1. Czy możemy podzielić liście na dwa zestawy st sumy numery są blisko?

Jeśli mamy tendencyjną monetę z parametrem i , węzły będą miały wartości $p$ $q=1-p$ . $p^i q^{n-i}$

Jak zauważono w innych odpowiedziach, dla większości celów pirackich dobranie pary bitów jest dobre. Bias będzie . $\sum_{i} {\binom{n}{i} parity(x) p^i q^{n-i}} = \sum_{i} {\binom{n}{i} (-p)^i q^{n-i}} = (q-p)^n$

Ogólnie, jeśli mamy wystarczającą ilość zasobów obliczeniowych (powiedzmy w liczbie losowych bitów), możemy podzielić węzły w najlepszy możliwy sposób. $PSpace$

EDYCJA „Zasadniczo jest to problem kodowania Shannona”. (Podziękowania dla Per Vognsen.) KONIEC EDYCJI

Z drugiej strony, jeśli wolno nam tylko korzystać $AC^0$

(Ta odpowiedź może zawierać błędy, nie sprawdziłem szczegółów).

Kaveh
źródło

2

„Czy możemy podzielić liście na dwa zestawy i sumy liczb, które są blisko?” Jest to w zasadzie problem z kodowaniem Shannona. Algorytm Shannona-Fano jest odgórny i zaczyna się od zestawu elementów ważonych prawdopodobieństwem i prosi o możliwie jak najbardziej dwuczęściowy podział. Zastosowanie tego rekurencyjnie daje integralny kod bez prefiksu. Algorytm Huffmana jest oddolny: zaczyna się od drzew singletonowych i wielokrotnie łączy pary z największym prawdopodobieństwem. Jeśli wiesz o kodowaniu arytmetycznym, to również słusznie sugeruje, że lepiej jest generować wiele uczciwych bitów naraz niż pojedynczo.

Per Vognsen

4

Możesz również uzyskać wiele losowych bitów z stronniczych monet, patrz artykuł Gabizona Algorytmy derandomizacji w części Dystrybucje produktów (http://sites.google.com/site/arielgabizon1/)

źródło

3

Powiązane pytanie, inna strona: wybielanie losowej sekwencji bitów

BCS
źródło

1

Jeśli chcesz, aby parzysta liczba rzutów monetą była bezstronna w przypadku monet o tendencyjnym charakterze, łatwym sposobem na usunięcie uprzedzeń jest odwrócenie wyniku każdego innego rzutu.

Dziekan J.
źródło

1

To oczywiście nie spowoduje jednolitej losowości sekwencji. Wyobraź sobie ograniczający przypadek, gdy odchylenie monety wynosi 1 - po prostu otrzymujesz deterministyczną sekwencję naprzemiennych bitów.

Aaron Roth,

Każda strategia, która bioptycznie odwzorowuje wyniki, zachowa entropię, więc nie może zmienić rozkładu z nie-maksymalnej entropii (stronnicza) na maksymalną entropię (obiektywna).

Per Vognsen

Jaki jest najlepszy sposób na uzyskanie rzutu monetą zbliżoną do uczciwej z identycznych monet tendencyjnych?

Odpowiedzi: