Dado una moneda con sesgo desconocido, generar variantes aleatorias de una moneda justa eficientemente

Question

Dado una moneda con desconocido bias $p$, ¿cómo puedo generar variantes aleatorias - tan eficientemente como sea posible - que son distribuidas Bernoulli con probabilidad 0.5? Es decir, utilizando el mínimo número de saltos por variante aleatoria generada.

Answer 1

Se trata de un problema conocido con varias soluciones agradables que se han discutido aquí en stackoverflow (parece no puedo publicar más que un solo link pero una búsqueda rápida de google le da algunas entradas interesantes). Echa un vistazo a la entrada de wikipedia

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

Answer 2

No estoy seguro de cómo la suma de los términos de manera eficiente, pero nos puede parar cuando el número total de rollos $n$ y el número total de éxitos $t$ son tales que $\binom{n}{t}$ es incluso ya podemos partición de los diferentes ordenamientos que podríamos haber logrado $n$ $t$ en dos grupos de igual probabilidad que corresponden a cada una diferentes imprima la etiqueta. Tenemos que tener cuidado de que no hemos hecho una parada para estos elementos, es decir, que ningún elemento tiene un prefijo de longitud $n'$ $t'$ éxitos que $\binom{n'}{t'}$ es incluso. No estoy seguro de cómo convertir esto en un número esperado de lanzamientos.

Para ilustrar:

Podemos parar en el TH o HT, ya que estos tienen la misma probabilidad. Mover hacia abajo triángulo de Pascal, el siguiente términos están en la cuarta fila: 4, 6, 4. Lo que significa que podemos parar después de rollos si uno de los jefes ha llegado ya podemos crear un bipartito de coincidencia: HHHT con HHTH, y técnicamente HTHH con THHH, aunque nosotros ya han dejado de aquellos. Del mismo modo, $\binom42$ los rendimientos de la coincidencia de HHTT con TTHH (el resto, nosotros ya habría detenido antes de llegar a ellos).

Para $\binom52$, todas las secuencias han dejado de prefijos. Se pone un poco más interesante en $\binom83$ donde hemos partido de FFFFTTFT con FFFFTTTF.

Para $p=\frac12$ después de 8 rollos, la probabilidad de no haber dejado de es$\frac1{128}$, con una previsión del número de rollos de si hemos dejado de $\frac{53}{16}$. Para la solución donde seguimos rodando parejas, hasta los que son diferentes, la probabilidad de no haber dejado de es$\frac{1}{16}$, con una previsión del número de rollos de si hemos dejado de 4. Por recursión, un límite superior a la esperada volteretas por el algoritmo presentado es $\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$.

Me escribió un programa en Python para imprimir los puntos 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()

impresiones:

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