0
votes

Génération de bits aléatoires uniformes à l'aide d'une source de bits biaisés

Nous avons une source de bits aléatoires biaisés, à savoir une source qui produit 0 avec probabilité p , ou 1 avec probabilité 1 - p .

Comment pouvons-nous utiliser cette source pour construire un générateur qui produit 0 ou 1 avec une probabilité égale?

random probability

3 commentaires

La valeur de p connue?

@PeterO, inconnu

@PeterO, ouais, c'est ce que je voulais et ce que Progman a dit. Je n'ai pas trouvé cette discussion - ma mauvaise.

3 Réponses :

0
votes

Une façon serait d'appeler votre générateur biaisé N fois, de faire la somme des résultats, puis de prendre votre échantillon sans biais à 0 si la somme est inférieure à la médiane de la somme, 1 sinon. Le seul truc est de savoir comment choisir N et quelle est la médiane. Dans l' article du wiki, ils discutent de la recherche de la médiane. (Notez qu'ils ont p dans l'autre sens, dans l'article, c'est la probabilité de 1)

0 commentaires

0
votes

Vous lancez la pièce biaisée deux fois. Il y a quatre résultats possibles:

01 - Choisissez le nombre 0 comme valeur de retour.
10 - Choisissez le nombre 1 comme valeur de retour.
00 - Recommencez à lancer deux pièces.
11 - Recommencez à lancer deux pièces.

Lorsque vous calculez la probabilité d'obtenir 01 ou 10 , vous verrez que c'est la même chose. De cette façon, les séquences 01 et 10 apparaissent avec la même probabilité, quelle que soit la valeur p .

1 commentaires

bon, mais beaucoup de gaspillage

0
votes

Eh bien, il existe une approche, appelée extracteur d'entropie, qui permet d'obtenir de (bons) nombres aléatoires à partir de sources pas tout à fait aléatoires.

Si vous disposez de trois RNG indépendants mais de faible qualité (biaisés), vous pouvez les combiner en une source uniforme.

Supposons que vous ayez trois générateurs vous donnant chacun un seul octet, alors la sortie uniforme serait

t = X * Y + Z

où l'addition et la multiplication sont effectuées sur un corps fini GF (2 ⁸ ).

Code, Python

...
q = RNG(0.7) # just byte value from bits with p=0.7
...

produira un graphique de distribution d'octets - semble raisonnablement uniforme pour les valeurs de [0 ... 256). J'ai pu trouver du papier où cette idée a été proposée

Juste à titre d'illustration, voici à quoi cela ressemble lorsque nous collectons des octets sans extraction d'entropie, code

import numpy as np
import matplotlib.pyplot as plt
from pyfinite import ffield

def RNG(p):
    return np.random.binomial(1, p) + \
           np.random.binomial(1, p)*2 + \
           np.random.binomial(1, p)*4 + \
           np.random.binomial(1, p)*8 + \
           np.random.binomial(1, p)*16 + \
           np.random.binomial(1, p)*32 + \
           np.random.binomial(1, p)*64  + \
           np.random.binomial(1, p)*128

def muRNG(p):
    X = RNG(p)
    Y = RNG(p)
    Z = RNG(p)

    GF = ffield.FField(8)
    return GF.Add(GF.Multiply(X, Y), Z)

N = 100000
hist = np.zeros(256, dtype=np.int32)
for k in range(0, N):
    q = muRNG(0.7)
    hist[q] += 1

x = np.arange(0, 256, dtype=np.int32)

fig, ax = plt.subplots()
ax.stem(x, hist, markerfmt=' ')
plt.show()

et graphique

0 commentaires