Simulant une probabilité de 1 sur 2 ^ n avec moins de n bits aléatoires

Question

Dites que j'ai besoin de simuler la distribution discrète suivante:

$$ p (x = k) = begin {Cas} frac {1} {2 ^ n}, & text {if $ k = 1 $} 1 - frac {1} {2 ^ n} , & text {if $ k = 0 $} end {cas} $$

Le moyen le plus évident est de dessiner $ N $ Bits aléatoires et vérifiez si tous équivaut à $0$ (ou $1$). Cependant, la théorie de l'information dit

$$ begin {align} s & = - sum_ {i} p_i log {p_i} & = - frac {1} {2 ^ n} log { frac {1} {2 ^ n} } - Left (1 - frac {1} {2 ^ n} droite) log { Left (1 - frac {1} {2 ^ n} droite)} & = frac {1 } {2 ^ n} log {2 ^ n} + Left (1 - frac {1} {2 ^ n} droite) log { frac {2 ^ n} {2 ^ n - 1}} & rightarrow 0 end {align} $$

Ainsi, le nombre minimum de bits aléatoires requis en fait diminution comme $ N $ va grand. Comment est-ce possible?

Veuillez supposer que nous courons sur un ordinateur où les bits sont votre seule source de hasard, vous ne pouvez donc pas simplement prendre une pièce biaisée.