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

10

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

Neil G.
źródło
3
Prostym rozwiązaniem jest odwrócenie monety dwa razy: jeśli to , ją na głowach, jeśli to , na ogonach. W przeciwnym razie powtarzaj eksperyment aż do osiągnięcia jednego z tych dwóch. HTTH
kardynał
1
@cardinal: Fajnie! Dlaczego nie dodać odpowiedzi?
Neil G
2
@Glen_b: Dobra, ale czy możesz to zrobić przy minimalnej liczbie rzutów na wygenerowaną zmienną?
Neil G,
3
@MichaelLugo: Powiedziałbym, że to zdecydowanie zależy od . :-) Jeśli wiemy, że możemy to zrobić za jednym zamachem. Jeśli , wiemy, że możemy to zrobić na dwa sposoby, i wiemy, że jest to optymalne w obu przypadkach. Odpowiedź powinna być związana z entropią . Jeśli nie wiemy nic o innym niż , to podejrzewam, że wynik prostej teorii gier da coś zbliżonego do schematu w moim pierwszym komentarzu jako „optymalny” w odpowiedni sposób. pp=1/2p=1/4H(p)pp(0,1)
kardynał
4
Witaj Giorgio1927 i witaj na stronie! Dodaj znacznik „samokształcenie” do tego pytania, ponieważ pozwala ludziom zobaczyć, że powinni prowadzić cię do odpowiedzi, a nie tylko ją udzielić.
jbowman

Odpowiedzi:

6

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

Carlos Fuentes
źródło
Przepraszam, zmodyfikowałem pytanie, aby nie było tak łatwe w obsłudze przez Google…
Neil G
Osoby zastanawiające się nad odpowiedzią na pytanie zwróć uwagę, że ta odpowiedź nie jest optymalna dla mojego edytowanego pytania.
Neil G
3

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 iY i ) = P ( X i = T | X iY i ) z powodu symetrii, co implikuje P ((Xi,Yi)iXiYipP(Xi=H|XiYi)=P(Xi=T|XiYi) . Aby wyraźnie zobaczyć tę notatkę symetrii, że X iY 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|XiYi)=1/2XiYi(H,T)(T,H)

Empirycznie czas oczekiwania na taką nierówną parę

1/P(XY)=11p2(1p)2=12p(1p),

który wybuchnie, gdy zbliża się do 0 lub 1 (co ma sens).p

Alex R.
źródło
2

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 ( nnt 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ścinzsukcesamittakimi, że ( n(nt)ntntjest parzysty. Nie jestem pewien, jak zmienić to w oczekiwaną liczbę rzutów.(nt)

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. 1281275316=424127<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
Neil G.
źródło
pp0p1p2/((p(1p))
@whuber: Nie rozumiem, dlaczego powinien być optymalny. Moje rozwiązanie kończy się we wszystkich tych samych przypadkach, co jego. Będzie jednak nadal toczył się po tym, na przykład, podczas gdy możliwe jest zatrzymanie.
Neil G
Jakie jest twoje rozwiązanie Nie widzę tu jednego opisanego. Myślę, że możemy mieć różne koncepcje rozwiązania @ Cardinal. Rozumiem, że oznacza to „przestań, ilekroć liczba głów jest równa liczbie ogonów i odwzoruj to na wartość pierwszego wyniku w sekwencji”.
whuber
@whuber: Masz na myśli to: „Prostym rozwiązaniem jest odwrócenie monety dwa razy: jeśli jest to HT odwzoruj ją na głowy, jeśli to TH odwzoruj ją na reszki. W przeciwnym razie powtórz eksperyment aż do osiągnięcia jednego z tych dwóch”. Nie zatrzyma się to dla HHTT. Oczekuje na parę HT lub TH na parzystym indeksie.
Neil G
Moje rozwiązanie polega na znalezieniu dwustronnego dopasowania odpowiednich prefiksów (z których żaden nie jest przedrostkiem innym) i powiązaniu każdej połowy dopasowania z główkami lub ogonami.
Neil G