Biorąc pod uwagę monetę o nieznanym nastawieniu , jak mogę generować zmienne - tak wydajnie, jak to możliwe - które są dystrybuowane według Bernoulliego z prawdopodobieństwem 0,5? Oznacza to, że użycie minimalnej liczby rzutów na wygenerowaną zmienną jest zmienne.
random-generation
Neil G.
źródło
źródło
Odpowiedzi:
Jest to dobrze znany problem z kilkoma fajnymi rozwiązaniami, które zostały tutaj omówione i w trybie overover (wydaje się, że nie mogę opublikować więcej niż jednego linku, ale szybkie wyszukiwanie w Google daje kilka interesujących wpisów). Zobacz wpis na Wikipedii
http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_noś_coin
źródło
Uważam, że jest to klasyczny problem przypisany pierwotnie von Neumannowi. Jednym z rozwiązań jest rzucanie monetą w pary, aż pary się od siebie różnią, a następnie przejście do wyniku pierwszej monety w parze.
Wyraźnie niech będzie wynikiem rzutu i , przy czym X i jest pierwszą monetą, a Y i jest drugą monetą. Każda moneta ma prawdopodobieństwo p głów. Następnie P ( X i = H | X i ≠ Y i ) = P ( X i = T | X i ≠ Y i ) z powodu symetrii, co implikuje P ((Xi,Yi) i Xi Yi p P(Xi=H|Xi≠Yi)=P(Xi=T|Xi≠Yi) . Aby wyraźnie zobaczyć tę notatkę symetrii, że X i ≠ Y i oznacza, że wyniki to ( H , T ) lub ( T , H ) , z których oba są jednakowo prawdopodobne z powodu niezależności.P(Xi=H|Xi≠Yi)=1/2 Xi≠Yi (H,T) (T,H)
Empirycznie czas oczekiwania na taką nierówną parę
który wybuchnie, gdy zbliża się do 0 lub 1 (co ma sens).p
źródło
Nie jestem pewien, jak skutecznie podsumować warunki, ale możemy zatrzymać się, gdy całkowita liczba rzutów i całkowita liczba sukcesów t są takie, że ( nn t jest nawet, ponieważ możemy podzielić różne uporządkowania, które moglibyśmy osiągnąćnit,na dwie grupy o jednakowym prawdopodobieństwie, z których każda odpowiada innej wyjściowej etykiecie. Musimy uważać, aby nie zatrzymać się jeszcze dla tych elementów, tzn. Że żaden element nie ma prefiksu o długościn′zsukcesamit′takimi, że ( n′(nt) n t n′ t′ jest parzysty. Nie jestem pewien, jak zmienić to w oczekiwaną liczbę rzutów.(n′t′)
Ilustrować:
Możemy zatrzymać się na TH lub HT, ponieważ mają one równe prawdopodobieństwo. Przechodząc w dół trójkąta Pascala, kolejne parzyste wyrażenia znajdują się w czwartym rzędzie: 4, 6, 4. Oznacza to, że możemy zatrzymać się po rzutach, jeśli pojawi się jedna głowa, ponieważ możemy stworzyć dwustronne dopasowanie: HHHT z HHTH i technicznie HTHH z THHH, chociaż już byśmy się na tym zatrzymali. Podobnie daje dopasowanie HHTT do TTHH (reszta byłaby już zatrzymana przed osiągnięciem ich).(42)
Dla , wszystkie sekwencje zatrzymały prefiksy. To staje się nieco bardziej interesujące w ( 8(52) gdzie dopasowujemy FFFFTTFT do FFFFTTTF.(83)
Dla po 8 rzutach, szansa, że się nie zatrzymasz, wynosi1p=12 z oczekiwaną liczbą rzutów, jeśli zatrzymamy się na531128 . W przypadku rozwiązania, w którym pary są zmienne, dopóki się nie różnią, szansa, że się nie zatrzymamy, wynosi15316 z oczekiwaną liczbą rzutów, jeśli zatrzymaliśmy się na 4. Według rekurencji górna granica oczekiwanych rzutów dla prezentowanego algorytmu wynosi128116 . 128127⋅5316=424127<4
Napisałem program w Pythonie, aby wydrukować punkty zatrzymania:
drukuje:
źródło