Générateur de nombres aléatoires non biaisé utilisant un générateur biaisé

Question

Vous avez un générateur de nombres aléatoires polarisés qui produit un 1 avec une probabilité p et 0 avec une probabilité (1-p). Vous ne connaissez pas la valeur de p. En utilisant ceci, on crée un générateur de nombres aléatoires sans biais qui produit 1 avec une probabilité de 0,5 et 0 avec une probabilité de 0,5.

Remarque: ce problème est un problème d'exercice de l'introduction aux algorithmes par Cormen, Leiserson, Rivest, Stein (RCG)

Answer 1

Les événements (p) (1-p) et (1-p). (p) sont équiprobables. En les prenant comme 0 et 1 respectivement et en écartant les deux autres paires de résultats, vous obtenez un générateur aléatoire non biaisé.

Dans le code cela se fait aussi facile que:

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

Vous devez dessiner paires des valeurs du RNG jusqu'à ce que vous obtenez une séquence de valeurs différentes, à savoir zéro suivi d'un ou un suivi zéro. Vous prenez alors la première valeur (ou dernière, n'a pas d'importance) de cette séquence. (Répéter aussi longtemps que la paire dessinée est soit deux zéros soit deux uns)

Le calcul derrière ceci est simple: une séquence 0 puis 1 a la même probabilité qu'une séquence 1 puis zéro. En prenant toujours le premier (ou le dernier) élément de cette séquence comme résultat de votre nouveau RNG, nous obtenons une chance égale d'obtenir un zéro ou un.

Answer 3

Voici une façon, probablement pas la plus efficace. Mordez à travers un tas de nombres aléatoires jusqu'à ce que vous obteniez une séquence de la forme [0 ..., 1, 0 ..., 1] (où 0 ... est un ou plusieurs 0). Comptez le nombre de 0. Si la première séquence est plus longue, générez un 0, si la seconde est plus longue, générez un 1. (Si ce sont les mêmes, réessayez.)

Cela ressemble à ce que fait HotBits pour générer des nombres aléatoires de radioactifs la désintégration de particules:

Puisque le temps de toute décroissance donnée est aléatoire, alors l'intervalle entre deux désintégrations consécutives est également aléatoire. Ce que nous faisons, alors, est de mesurer une paire de ces intervalles, et d'émettre un zéro ou un bit en fonction de la longueur relative des deux intervalles. Si nous mesurons le même intervalle pour les deux désintégrations, nous supprimons la mesure et essayez à nouveau

HotBits: How It Works

Answer 4

L'astuce attribuée à von Neumann d'obtenir deux bits à la fois, ayant 01 correspondons à 0 et 10 à 1, et répéter pour 00 ou 11 est déjà venu. La valeur attendue des bits que vous devez extraire pour obtenir un seul bit à l'aide de cette méthode est 1/p(1-p), ce qui peut devenir assez important si p est particulièrement petit ou grand, il est donc utile de demander si la méthode peut être améliorée, d'autant plus qu'elle est évident qu'il jette beaucoup d'informations (tous les cas 00 et 11).

La recherche de "von neumann trick biased" a produit this paper qui développe une meilleure solution au problème. L'idée est que vous prenez toujours deux bits à la fois, mais si les deux premières tentatives produisent seulement 00 et 11, vous traitez une paire de 0 comme un 0 et une paire de 1 comme une seule, et appliquez l'astuce de von Neumann à ces paires. Et si cela ne fonctionne pas non plus, continuez à combiner de la même manière à ce niveau de paires, et ainsi de suite.Plus loin, le document développe ceci en générant plusieurs bits non biaisés à partir de la source polarisée, utilisant essentiellement deux manières différentes de générer des bits à partir des paires de bits, et en donnant un croquis que c'est optimal en ce sens qu'il produit exactement le nombre de bits que la séquence originale a eu l'entropie.

Answer 5

La procédure à produce an unbiased coin from a biased one a d'abord été attribuée à Von Neumann (un gars qui a fait un travail énorme en mathématiques et de nombreux domaines connexes). La procédure est super simple:

• Lancez la pièce deux fois.
• Si les résultats correspondent, recommencer en oubliant les deux résultats.
• Si les résultats diffèrent, utilisez le premier résultat, en oubliant le second.

La raison fonctionne cet algorithme est parce que la probabilité d'obtenir HT est p(1-p), qui est la même chose que de TH (1-p)p. Ainsi, deux événements sont également probables.

Je lis aussi ce livre et il demande le temps de fonctionnement prévu. La probabilité que deux lancements ne soient pas égaux est z = 2*p*(1-p), par conséquent, la durée d'exécution attendue est 1/z.

---

L'exemple précédent semble encourageante (après tout, si vous avez une pièce de monnaie biaisée avec un parti pris de p=0.99, vous devez jeter votre pièce environ 50 fois, ce qui est pas beaucoup). Donc vous pourriez penser que c'est un algorithme optimal. Malheureusement, ce n'est pas le cas.

Voici comment il se compare avec le Shannon's theoretical bound (l'image est tirée de ce answer). Cela montre que l'algorithme est bon, mais loin d'être optimal.

Vous pouvez trouver une amélioration si vous considérerez que HHTT sera mis au rebut par cet algorithme, mais en fait, il a la même probabilité que TTHH. Donc, vous pouvez aussi arrêter ici et retourner H. La même chose est avec HHHHTTTT et ainsi de suite. L'utilisation de ces cas améliore le temps de fonctionnement prévu, mais ne le rend pas théoriquement optimal.

---

Et à la fin - code python:

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

Il est assez explicite, et est un résultat exemple ici:

0.0973181652114 
505 495 

Comme vous le voyez, néanmoins nous avions un biais de 0.097, nous avons eu environ le même nombre de 1 et 0