Simulando una probabilità di 1 di 2^n con meno di n bit casuali

Question

Suppongo che devo simulare la seguente distribuzione discreta:

$$ p (x = k) = inizio {casi} frac {1} {2^n}, & text {if $ k = 1 $} 1 - frac {1} {2^n} , & text {if $ k = 0 $} end {Cases} $$

Il modo più ovvio è disegnare $ N $ bit casuali e controlla se tutti sono uguali a $0$ (o $1$). Tuttavia, dice la teoria dell'informazione

$$ inizio {align} s & = - sum_ {i} p_i log {p_i} & = - frac {1} {2^n} log { frac {1} {2^n} } - a sinistra (1 - frac {1} {2^n} a destra) log { a sinistra (1 - frac {1} {2^n} a destra)} & = frac {1 } {2^n} log {2^n} + Left (1 - frac {1} {2^n} a destra) log { frac {2^n} {2^n - 1}} & Rightarrow 0 end {align} $$

Quindi il numero minimo di bit casuali richiesti effettivamente diminuisce come $ N $ va in grande. Com'è possibile?

Per favore, supponiamo che stiamo correndo su un computer in cui Bits è l'unica fonte di casualità, quindi non puoi semplicemente fare una moneta distorta.