Symuluj uczciwą kość z tendencyjną

18

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:N[1,N]pi=P(D(k)=i)kADADP(A()=i)=1/NAnD0n

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..D(2k+1)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 i,|pi1/N|<ϵ dla niektórych ϵ>0 .

Gilles „SO- przestań być zły”
źródło
Uwaga: ważne jest, aby dokładnie zdefiniować optymalne, ponieważ na przykład możesz otrzymać całkowicie uczciwą kostkę lub matrycę mającą , dla lub dowolną inną rodzaj śmierci. Optymalny schemat sprawiedliwej kości wymaga tylko jednego rzutu, podczas gdy w przypadku niesprawiedliwego przykładu optymalny schemat wymaga wielu. Ponadto supremum optymalnych nad wszystkimi możliwymi stronniczymi matrycami jest prawdopodobnie nieograniczone. Możesz więc wprowadzić parametr i załóżmy, że na przykład . p i = ϵ / ( N - 1 ) i > 1 maks. i p i1 - ϵp1=1ϵpi=ϵ/(N1)i>1maxipi1ϵ
usul
@usul Nie rozumiem twojego komentarza. Istnieją wydajniejsze algorytmy dla niektórych wartości (np. Jeśli ), ale pytam tylko o algorytmy, które nie zależą od . Jaki jest sens ? i , p i = 1 / N ( p i ) ϵpii,pi=1/N(pi)ϵ
Gilles 'SO - przestań być zły'
Jak mierzysz wydajność algorytmu, który nie zależy od ? Prawdopodobnie w przypadku takiego algorytmu nie ma górnej granicy oczekiwanej liczby potrzebnych wywołań, przenosząc mój przykładowy błąd umowny z . Mam na myśli to, że „supremum optymalnego ... prawdopodobnie nie ma granic”. Więc jeśli wszystkie algorytmy mogą wymagać dowolnie wielu rzutów matryc w oczekiwaniu, w jaki sposób decydujemy, który jest najlepszy? ϵ 0(pi)ϵ0
usul
@usul Oczywiście nie ma górnej granicy liczby rzutów, ale pytam o oczekiwaną wartość (tj. średnią liczbę rzutów). Dla danej dystrybucji oczekiwana wartość algorytmu, który tworzy uczciwą monetę i wykorzystuje ją do odrzucenia próbkowania, jest skończona, prawda? To prawda, że ​​oczekiwanie zależy od dystrybucji, więc różne (rodziny) algorytmów mogą być optymalne dla różnych dystrybucji. Jeśli tak jest, powiedzmy, że interesują mnie prawie uczciwe kości. (pi)
Gilles 'SO - przestań być zły'
Nie do końca dokładnie pytanie, ale czy chciałbyś szukać tylko wyniku zbliżonego do jednorodnego (w / całkowity dystans zmienności)? Jeśli tak, w zależności od gwarancji, której żądasz od pierwotnej dystrybucji, jest to badane w najnowszym artykule (przedłożonym), pod nazwą „polepszacz próbkowania dla jednolitości” - który pokazuje, że w szczególności można uzyskać liczbę losowań niezależnych od poprawić z odległości do odległości . N 1 ε ε 1N1εε
Klemens C.

Odpowiedzi:

3

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 H[1,N]1hh

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ę.NNN

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 wiemN

usul
źródło
Nie szukałem dalszej pracy ani pracy, powołując się na artykuł, więc nie wiem, ale może ktoś ulepszył program, zaproponował inny, odpowiedział na twoje pytanie itp.
usul
2

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 ] NN.=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 1N.0N.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.N.N.(1,,1)

Załóżmy, że znajdują się w stanie z . Wtedy prawdopodobieństwo uzyskania elementu (tj. Następny rzut to ) jest zawsze podawane przezn i = 1 v iN i iv=(v1,,vN)i=1nviNii

Pr[gain i]=pi .

Z drugiej strony, możliwość usunięcia elementu z historii dajei

Prv[drop i]=viN

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 vi=1nvi=N0v

Pr[v(v1,,vj+1,,vN)]={Pr[gain j],v<N0, else,Pr[v(v1,,vi1,vj+1,,vN)]={0,v<Nvi=0vj=NPrv[drop i]Pr[gain j], else andPr[vv]={0,v<Nvi0Prv[drop i]Pr[gain i], else;

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

Dla powstały łańcuch Markowa¹ wynosiN=2

Łańcuch Markowa dla N = 2
[ źródło ]

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

Esteps=2p0p12+i3(p0i1p1+p1i1p0)i=1p0+p02p0p02,

używając dla uproszczenia, że . Jeśli teraz, zgodnie z sugestią, dla niektórych , top 0 = 1p1=1p0ϵ[0,1p0=12±ϵϵ[0,12)

Esteps=3+4ϵ214ϵ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ę) toN6

NormalPlot LogPlot
Wykresy pokazują w funkcji ; po lewej regularny, a po prawej wykres logarytmiczny.N.EstepsN

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 = 3piN=3

Oczekiwana liczba kroków dla N = 3 i różne opcje
Wykres pokazuje jako funkcję i ; naturalnie .p 0 p 1 p 2 = 1 - p 0 - p 1Estepsp0p1p2=1p0p1

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 iNN=4pi

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 1ϵ01

2logN3+4ϵ214ϵ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.
Raphael
źródło
1

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 kN=2mmk pm k=0pk(1-p)m-log(mk)pk=pm

k=0mpk(1p)mk(mk)log(mk)mh(p).
k=pmmlog(mk)mh(k/m)mh(p) na rzut monetą (jest to optymalne ze względów teoretycznych, na przykład asymptotyczna właściwość ekwipartycji).

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 )NH(p)

Yuval Filmus
źródło
1

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)2pq2pqpqqppqqp

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)3pqrqpr

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=3pqr

.

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.i=1i=npi

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.

Poinformowano
źródło