Étant donné une pièce de monnaie avec un biais inconnu, générer efficacement des variations d'une pièce équitable

Étant donné une pièce avec un biais inconnu , comment puis-je générer des variations - aussi efficacement que possible - qui sont distribuées par Bernoulli avec une probabilité de 0,5? Autrement dit, en utilisant le nombre minimum de flips par variable générée.$p$

C'est un problème bien connu avec plusieurs belles solutions qui ont été discutées ici et dans stackoverflow (il semble que je ne puisse pas poster plus d'un lien mais une recherche rapide sur Google vous donne des entrées intéressantes). Jetez un oeil à l'entrée wikipedia

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

C'est un problème classique, je crois attribué à l'origine à von Neumann. Une solution consiste à continuer à lancer la pièce par paires jusqu'à ce que les paires soient différentes, puis à s'en remettre au résultat de la première pièce de la paire.

Soit explicitement le résultat du tirage , étant la première pièce et étant la deuxième pièce. Chaque pièce a une probabilité de têtes. Alors raison de la symétrie, ce qui implique . Pour voir de façon explicite cette symétrie, notez que implique que les résultats sont ou , les deux étant également probables en raison de l'indépendance.$(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$ ( H , T ) ( T , H $X_i\neq Y_i$$(H,T)$$(T,H)$

Empiriquement, le temps d'attente jusqu'à ce qu'une paire aussi inégale soit

qui explose lorsque se rapproche de 0 ou 1 (ce qui est logique).$p$

Je ne sais pas comment résumer les termes efficacement, mais nous pouvons nous arrêter chaque fois que le nombre total de rouleaux et le nombre total de succès sont tels que est égal puisque nous pouvons partitionner les différents ordonnances que nous aurions pu atteindre et en deux groupes de probabilité égale correspondant chacun à une étiquette de sortie différente. Nous devons faire attention à ne pas nous être déjà arrêtés pour ces éléments, c'est-à-dire qu'aucun élément n'a un préfixe de longueur avec succès tel que soit pair. Je ne sais pas comment transformer cela en un nombre attendu de flips.$n$$t$$\binom{n}{t}$$n$$t$$n'$$t'$$\binom{n'}{t'}$

Pour illustrer:

Nous pouvons nous arrêter à TH ou HT car ceux-ci ont une probabilité égale. En descendant dans le triangle de Pascal, les termes pairs suivants sont dans la quatrième ligne: 4, 6, 4. Cela signifie que nous pouvons nous arrêter après les lancers si une tête est apparue car nous pouvons créer une correspondance bipartite: HHHT avec HHTH, et techniquement HTHH avec THHH bien que nous nous serions déjà arrêtés pour ceux-là. De même, donne le HHTT correspondant à TTHH (le reste, nous aurions déjà arrêté avant de les atteindre).$\binom42$

Pour , toutes les séquences ont des préfixes arrêtés. Cela devient un peu plus intéressant dans où nous associons FFFFTTFT à FFFFTTTF.$\binom52$$\binom83$

Pour après 8 lancers, la chance de ne pas avoir arrêté est avec un nombre attendu de lancers si nous avons arrêté de . Pour la solution où nous continuons à rouler les paires jusqu'à ce qu'elles diffèrent, la chance de ne pas s'arrêter est avec un nombre attendu de rouleaux si nous nous sommes arrêtés à 4. Par récursion, une borne supérieure sur les flips attendus pour l'algorithme présenté est . $p=\frac12$$\frac1{128}$$\frac{53}{16}$$\frac{1}{16}$$\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$

J'ai écrit un programme Python pour imprimer les points d'arrêt:

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

impressions:

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