Dada uma moeda com viés desconhecido, gere variáveis ​​a partir de uma moeda justa com eficiência

Dada uma moeda com viés desconhecido $p$ , como posso gerar variáveis ​​- tão eficientemente quanto possível - que são distribuídas por Bernoulli com probabilidade 0,5? Ou seja, usando o número mínimo de inversões por variável gerada.

Esse é um problema conhecido com várias soluções legais que foram discutidas aqui e no stackoverflow (parece que não posso postar mais de um link, mas uma rápida pesquisa no Google fornece algumas entradas interessantes). Dê uma olhada na entrada da Wikipedia

http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_beased_coin

Acredito que esse é um problema clássico, atribuído originalmente a von Neumann. Uma solução é continuar jogando a moeda em pares até que os pares sejam diferentes e depois adiar para o resultado da primeira moeda no par.

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

Empiricamente, o tempo de espera até que um par tão desigual seja

$p$

$n$$t$$\binom{n}{t}$$n$$t$$n'$$t'$$\binom{n'}{t'}$

Ilustrar:

Podemos parar em TH ou HT, pois estes têm igual probabilidade. Movendo-se para baixo do triângulo de Pascal, os próximos termos pares estão na quarta linha: 4, 6, 4. O que significa que podemos parar após as jogadas se uma cabeça subir, pois podemos criar uma correspondência bipartida: HHHT com HHTH e tecnicamente HTHH com THHH, embora já tivéssemos parado para isso. Da mesma forma, produz o HHTT correspondente ao TTHH (o resto, já teríamos parado antes de alcançá-los).$\binom42$

Para , todas as sequências pararam prefixos. Fica um pouco mais interessante em onde combinamos FFFFTTFT com FFFFTTTF.$\binom52$$\binom83$

Para após 8 jogadas, a chance de não ter parado é com um número esperado de rolagens se tivermos parado de . Para a solução em que mantemos pares rolantes até que eles diferam, a chance de não ter parado é com um número esperado de rolagens, se tivermos parado de 4. Por recursão, um limite superior nos lançamentos esperados para o algoritmo apresentado é . $p=\frac12$$\frac1{128}$$\frac{53}{16}$$\frac{1}{16}$$\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$

Eu escrevi um programa Python para imprimir os pontos de parada:

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

impressões:

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