Biorąc pod uwagę monetę o nieznanym nastawieniu, wydajnie generuje zmienne z uczciwej monety

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.$p$

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

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 $(X_i,Y_i)$$i$$X_i$$Y_i$$p$$P(X_i=H|X_i\neq Y_i)=P(X_i=T|X_i\neq Y_i)$ . 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(X_i=H|X_i\neq Y_i)=1/2$$X_i\neq Y_i$$(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$

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 ($n$$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$\binom{n}{t}$$n$$t$$n'$$t'$jest parzysty. Nie jestem pewien, jak zmienić to w oczekiwaną liczbę rzutów.$\binom{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).$\binom42$

Dla , wszystkie sekwencje zatrzymały prefiksy. To staje się nieco bardziej interesujące w ($\binom52$ gdzie dopasowujemy FFFFTTFT do FFFFTTTF.$\binom83$

Dla po 8 rzutach, szansa, że ​​się nie zatrzymasz, wynosi$p=\frac12$ z oczekiwaną liczbą rzutów, jeśli zatrzymamy się na$\frac1{128}$ . W przypadku rozwiązania, w którym pary są zmienne, dopóki się nie różnią, szansa, że ​​się nie zatrzymamy, wynosi$\frac{53}{16}$ z oczekiwaną liczbą rzutów, jeśli zatrzymaliśmy się na 4. Według rekurencji górna granica oczekiwanych rzutów dla prezentowanego algorytmu wynosi$\frac{1}{16}$. $\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$

Napisałem program w Pythonie, aby wydrukować punkty zatrzymania:

import scipy.misc
from collections import defaultdict


bins = defaultdict(list)


def go(depth, seq=[], k=0):
    n = len(seq)
    if scipy.misc.comb(n, k, True) % 2 == 0:
        bins[(n,k)].append("".join("T" if x else "F"
                                   for x in seq))
        return
    if n < depth:
        for i in range(2):
            seq.append(i)
            go(depth, seq, k+i)
            seq.pop()

go(8)

for key, value in sorted(bins.items()):
    for i, v in enumerate(value):
        print(v, "->", "F" if i < len(value) // 2 else "T")
    print()

drukuje:

FT -> F
TF -> T

FFFT -> F
FFTF -> T

FFTT -> F
TTFF -> T

TTFT -> F
TTTF -> T

FFFFFT -> F
FFFFTF -> T

TTTTFT -> F
TTTTTF -> T

FFFFFFFT -> F
FFFFFFTF -> T

FFFFFFTT -> F
FFFFTTFF -> T

FFFFTTFT -> F
FFFFTTTF -> T

FFFFTTTT -> F
TTTTFFFF -> T

TTTTFFFT -> F
TTTTFFTF -> T

TTTTFFTT -> F
TTTTTTFF -> T

TTTTTTFT -> F
TTTTTTTF -> T