Symuluj uczciwą kość z tendencyjną

Biorąc pod uwagę stronniczą stronną matrycę, w jaki sposób można losowo wygenerować liczbę losową z zakresu ? Rozkład prawdopodobieństwa powierzchni matryc nie jest znany, wiadomo tylko, że każda powierzchnia ma niezerowe prawdopodobieństwo i że rozkład prawdopodobieństwa jest taki sam dla wszystkich rzutów (w szczególności rzuty są niezależne). Jest to oczywiste uogólnienie Uczciwych wyników przy nieuczciwej śmierci .$N$$[1,N]$

Ujmując to w kategoriach informatyki, mamy wyrocznię reprezentującą rzuty kostką: takie, że jest niezerowe i niezależne od . Szukamy deterministycznego algorytmu która jest parametryzowane przez (tj może wykonywać połączenia do D ), że P (A () = i) = 1 / N . Algorytm musi zakończyć się z prawdopodobieństwem 1, tzn. Prawdopodobieństwo, że A wykona więcej niż n wywołań do D, musi zbiegać się do 0, gdy n \ do \ infty .$D : \mathbb{N} \to [1,N]$$p_i = P(D(k)=i)$$k$$A$$D$$A$$D$$P(A()=i) = 1/N$$A$$n$$D$$0$$n\to\infty$

Dla $N=2$ (symulacja rzetelnej monety z rzutu monetą monetą tendencyjną) istnieje dobrze znany algorytm:

• Powtarzaj „odwróć dwa razy”, aż dwa rzuty dadzą różne wyniki ((głowy, ogony) lub (ogony, głowy)). Innymi słowy, pętla dla $k = 0..\infty$ aż $D(2k+1) \ne D(2k)$
• Zwraca 0, jeśli ostatnia para przewrotów to (głowy, ogony) i 1, jeśli tak było (ogony, głowy). Innymi słowy, zwróć $D(2k)$ gdzie $k$ jest indeksem, w którym pętla została zakończona.

Prostym sposobem na uzyskanie obiektywnej matrycy na podstawie stronniczości jest użycie metody rozbijania monet w celu zbudowania uczciwej monety i zbudowania rzetelnej kości z próbkowaniem odrzucenia, jak w przypadku Unbasingu sekwencji . Ale czy jest to optymalne (dla ogólnych wartości rozkładu prawdopodobieństwa)?

W szczególności moje pytanie brzmi: jaki jest algorytm, który wymaga najmniejszej oczekiwanej liczby wywołań wyroczni ? Jeśli zestaw osiągalnych wartości oczekiwanych jest otwarty, jaka jest dolna granica i jaka jest klasa algorytmów, która zbiega się w kierunku tej dolnej granicy?

W przypadku, gdy różne rodziny algorytmów są optymalne dla różnych rozkładów prawdopodobieństwa, skupmy się na prawie uczciwych kostkach: szukam algorytmu lub rodziny algorytmów, która byłaby optymalna dla rozkładów takich, że $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ dla niektórych $\epsilon \gt 0$ .

Poniższy artykuł stanowi odpowiedź na zbliżony wariant tego pytania: Efektywna konstrukcja nieobsługiwanej losowej sekwencji, Elias 1972 .

Wydaje się, że istnieje następujące pytanie: mając dostęp do tego stronniczego niezależnego źródła, wypisz ciąg liczb losowych w (zwróć uwagę na różnicę w stosunku do pytania, w której żądany jest tylko jeden symbol wyjściowy). Gdy długość pożądanego wyjścia dochodzi do nieskończoności, „wydajność” schematu w pracy (która wydaje się naturalnym uogólnieniem von Neumanna) idzie do , co oznacza, jak sądzę, że dane wejściowe z entropią są konwertowane na wyjście entropii zbliża się do .1 H $[1,N]$$1$$h$$h$

Pytanie wydaje się o wiele lepiej reagować, gdy jest wyrażane w ten sposób, zamiast żądać pojedynczej cyfry wyjściowej, ponieważ na przykład, jeśli narysujemy próbek i otrzymamy wynik z dużą ilością informacji (na przykład wszystkie symboli wejściowych są różne) , wówczas możemy wykorzystać wszystkie te informacje do wytworzenia wielu symboli wyjściowych, natomiast w przypadku pytania, które zostało tutaj sformułowane, wszelkie informacje poza tymi użytymi do wytworzenia jednego symbolu wyjściowego marnują się.$N$$N$

Uważam, że schemat wielokrotnie pobiera losów, analizuje sekwencję i odwzorowuje niektóre wyniki lub pusty ciąg. Być może istnieje sposób na ulepszenie schematu pytania poprzez spojrzenie na prefiksy i zatrzymanie się, jeśli mamy „wystarczającą” ilość informacji, aby wygenerować symbol? Nie wiem$N$

Metoda, którą opisujesz dla uogólnień. Używamy tego, że wszystkie permutacje są równie prawdopodobne, nawet przy tendencyjnej matrycy (ponieważ rzuty są niezależne). Dlatego możemy kontynuować walcowanie, dopóki nie zobaczymy takiej permutacji, jak ostatnie rzutów i wyrzucamy ostatni rzut.[ 1 .. N ] $N=2$$[1..N]$$N$

Ogólna analiza jest trudna; jasne jest jednak, że oczekiwana liczba rolek rośnie szybko w ponieważ prawdopodobieństwo zaobserwowania permutacji na danym etapie jest niewielkie (i nie jest niezależne od kroków przed i po, a zatem trudne). To jest większy niż do stałej , jednak, więc procedura kończy się prawie na pewno (czyli z prawdopodobieństwem ).0 N $N$$0$$N$$1$

Dla ustalonego możemy zbudować łańcuch Markowa na zbiorze wektorów Parikha, które sumują się do , podsumowując wyniki ostatnich rzutów i określamy oczekiwaną liczbę kroków do osiągnięcia po raz pierwszy . Jest to wystarczające, ponieważ wszystkie permutacje dzielące wektor Parikha są jednakowo prawdopodobne; łańcuchy i obliczenia są w ten sposób prostsze.≤ N N ( 1 , … , 1 )$N$$\leq N$$N$$(1,\dots,1)$

Załóżmy, że znajdują się w stanie z . Wtedy prawdopodobieństwo uzyskania elementu (tj. Następny rzut to ) jest zawsze podawane przez∑ n i = 1 v i ≤ N i $v=(v_1,\dots,v_N)$$\sum_{i=1}^n v_i \leq N$$i$$i$

$\qquad\displaystyle \operatorname{Pr}[\text{gain } i] = p_i$ .

Z drugiej strony, możliwość usunięcia elementu z historii daje$i$

$\qquad\displaystyle \operatorname{Pr}_v[\text{drop } i] = \frac{v_i}{N}$

za każdym razem (i przeciwnym razie) właśnie dlatego, że wszystkie permutacje z wektorem Parikha są jednakowo prawdopodobne. Te prawdopodobieństwa są niezależne (ponieważ rzuty są niezależne), więc możemy obliczyć prawdopodobieństwa przejścia w następujący sposób:0 $\sum_{i=1}^n v_i = N$$0$$v$

$\qquad\begin{align*} &\operatorname{Pr}[v \to (v_1,\dots,v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} \operatorname{Pr}[\text{gain } j] &, \sum v < N \\ 0 &, \text{ else} \end{cases}\;,\\[3ex] &\operatorname{Pr}[v \to (v_1,\dots,v_i - 1, \dots v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} 0 &, \sum v < N \lor v_i=0 \lor v_j=N \\ \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } j] &, \text{ else} \end{cases}\;\text{ and}\\[3ex] &\operatorname{Pr}[v \to v] \\ &\qquad=\begin{cases} 0 &, \sum v < N \\ \sum_{v_i \neq 0} \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } i] &, \text{ else} \end{cases}\;; \end{align*}$

wszystkie inne prawdopodobieństwa przejścia są równe zero. Pojedynczym stanem pochłaniającym jest , wektor wszystkich permutacji .[ 1 .. N $(1,\dots,1)$$[1..N]$

Dla powstały łańcuch Markowa¹ wynosi$N=2$

^{[ źródło ]}

z oczekiwaną liczbą kroków do wchłonięcia

$\qquad\displaystyle \mathbb{E}\,\text{steps} = 2 p_0 p_1 \cdot 2 + \sum_{i\geq 3} (p_0^{i-1}p_1 + p_1^{i-1}p_0)\cdot i = \frac{1 - p_0 + p_0^2}{p_0-p_0^2}\;,$

używając dla uproszczenia, że . Jeśli teraz, zgodnie z sugestią, dla niektórych , top 0 = $p_1=1-p_0$ϵ∈[0,$p_0 = \frac{1}{2} \pm \epsilon$$\epsilon \in [0,\frac{1}{2})$

$\qquad\displaystyle \mathbb{E}\,\text{steps} = \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$ .

Dla i rozkładów jednorodnych (najlepszy przypadek) wykonałem obliczenia za pomocą komputerowej algebry²; ponieważ przestrzeń stanu eksploduje szybko, trudno jest oszacować większe wartości. Wyniki (zaokrąglone w górę) to$N \leq 6$

^{Wykresy pokazują w funkcji ; po lewej regularny, a po prawej wykres logarytmiczny.$\mathbb{E}\,\text{steps}$$N$}

Wzrost wydaje się być wykładniczy, ale wartości są zbyt małe, aby dać dobre szacunki.

Jeśli chodzi o stabilność względem zakłóceń , możemy spojrzeć na sytuację dla : N = $p_i$$N=3$

^{Wykres pokazuje jako funkcję i ; naturalnie .p 0 p 1 p 2 = 1 - p 0 - p $\mathbb{E}\,\text{steps}$$p_0$$p_1$$p_2 = 1 - p_0 - p_1$}

Zakładając podobne obrazy dla większego (jądro ulega awarii przy obliczaniu wyników symbolicznych nawet dla ), oczekiwana liczba kroków wydaje się być dość stabilna dla wszystkich oprócz najbardziej ekstremalnych wyborów (prawie cała masa lub żadna masa przy niektórych ).N = 4 p $N$$N=4$$p_i$

Dla porównania, symulowanie monety niezależnej od (np. Poprzez równomierne przypisanie wyników do i ), użycie jej do symulacji uczciwej monety i wreszcie wykonanie próbkowania z odrzuceniem bitowym wymaga co najwyżej0 $\epsilon$$0$$1$

$\qquad\displaystyle 2\lceil \log N \rceil \cdot \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

kostki rzucają się w oczekiwaniu - prawdopodobnie powinieneś się z tym trzymać.

1. Ponieważ łańcuch absorbuje w krawędzie zaznaczone na szaro nigdy nie są przesuwane i nie wpływają na obliczenia. Zawieram je wyłącznie w celach kompletności i celów ilustracyjnych.$(11)$
2. Implementacja w Mathematica 10 ( Notatnik , Bare Source ); przepraszam, to wiem z tego rodzaju problemów.

Krótki komentarz dotyczący sprawy . Weź dużą liczbę i próbkuj rzuty kostką. Jeśli masz głów, możesz wyodrębnić bitów. Zakładając, że matryca jest wymuszonym średnia ilość informacji jest Aby uzyskać to oszacowanie, użyj faktu, że zmienna dwumianowa jest skoncentrowana wokół wraz z oszacowaniem . Gdy staje się większy, uzyskujemy optymalną szybkośćm m $N = 2$$m$$m$$k$ pm ∑ k=0pk(1-p)m$\log \binom{m}{k}$$p$k=p

Możesz użyć tej samej metody dla ogólnego i prawdopodobnie dostaniesz to samo . Algorytmy te są optymalne tylko w limicie, a algorytmy mogą osiągać limit szybciej niż te. W rzeczywistości zaniedbałem obliczenie prędkości konwergencji - może to być interesujące ćwiczenie.H ( → p$N$$H(\vec{p})$

Zaryzykowałbym następującą odpowiedź.

Szczególny przypadek 2, o którym wspomniałeś powyżej, jest szczególnym przypadkiem rozszerzenia (gdzie jest prob głowy i prob ogona), co daje termin Oznacza to, że możesz uzyskać dla jednego przypadku i dla drugiego przypadku. Będziesz musiał powtarzać próbkowanie, aż zobaczysz lub (głowa-ogon lub głowa-ogon). Używając ich jako symulacji, dasz jednakowe prawdopodobieństwo.$(p + q)^2$$p$$q$$2pq$$pq$$qp$$pq$$qp$

Gdy , masz rozszerzenie które daje termin . W tym przypadku robisz to samo, próbkując, aż zobaczysz wszystkie 3 wyniki , , w jakiejś kolejności w 3 kolejnych próbach.$N=3$$(p + q + r)^3$$pqr$$q$$p$$r$

To samo dotyczy przypadku ogólnego. Myśląc ostrożnie, muszę powiedzieć, że przypadek 2 jest najlepszym przypadkiem, w którym można wypracować różne rzeczy w dodatku. Gdy istnieje 6 różnych sekwencji dla i istnieje wiele innych terminów w rozwinięciu. Czułbym się nieswojo z innymi warunkami, w których wyniki są o wiele więcej.$N=3$$pqr$

.

Dodatkowy:

To sprawia, że ​​zastanawiam się nad pomysłem prostego próbkowania, aby oszacować prawdopodobieństwo każdego wyniku kostki. W tym najprostszym przypadku modelu jednowarstwowego bez warstwy ukrytej (znany model) możemy ustalić granicę, aby stwierdzić, że estymacja szybko się zbiega. W rzeczywistości granica Chernoffa pokazuje nam, że błąd maleje wykładniczo wraz ze wzrostem próbkowania (liniowo).

Teraz, gdy znane jest dobre oszacowanie prawdopodobieństwa dla każdej strony kości, istnieje wiele opcji. Jedną z opcji jest to, że możemy ponownie wykonać powyższe rozwinięcie, ale tym razem możemy potencjalnie użyć wielu innych terminów w rozszerzeniu, które mają taką samą wartość jak (lub dowolny termin, który używasz jako sekwencji bazującej). Będzie to nieco bardziej wydajne, ponieważ zostaną użyte więcej terminów w rozszerzeniu. Ale przyznaję, że nie wiem, czy spowoduje to jak najmniejszą liczbę wezwań do wyroczni, aby mieć gwarancję wszelkich warunków wstępnych (takich jak parametr ufności), jeśli zostaną podane.$\prod_{i=1}^{i=n} p_i$

Niemniej jednak takie podejście jest odpowiedzią na inny smak pytania. Pytanie dotyczy zagwarantowania doskonałej bezstronności kosztem potencjalnie dużego próbkowania (choć niskiego prawdopodobieństwa). Podejście to wykorzystuje tylko skończone próbkowanie z parametrem ufności związanej. Nie sądzę więc, aby takie podejście było odpowiednie do tego pytania, mimo że jest bardzo interesujące.