Como ya se ha dicho en los comentarios, la respuesta depende mucho de la simulación de procedimientos permite. Por ejemplo supongamos que $p=\frac12$ y que se quiere simular un poco 0
o 1
con una probabilidad de $\sqrt{p}=\frac1{\sqrt2}$ de 1
. Desde $\frac1{\sqrt2}$ no es diádica, esto es imposible a partir de un conjunto finito de imparcial bits independientes, pero, tan pronto como uno permite un flujo de independiente, imparcial bits con finito pero ilimitado de longitud, básicamente, todo se vuelve posible.
Para ver esto en el ejemplo a mano, considere la posibilidad de la expansión de la serie
$$
\frac1{\sqrt2}=\sum\limits_{n\geqslant0}{2n\elegir n}\frac1{2^{3n+1}}.
$$
Esto sugiere el siguiente procedimiento. Primera simular algunos independiente, imparcial bits con valores de 0
o 1
, y contar el número N
de 0
s antes de la primera 1
. Si N=0
(es decir, si el primer bit 1
), el retorno, B=1
. De lo contrario, simular 2N
independiente, imparcial bits con valores de 0
o 1
y consideran que su suma S
. Si S=N
, el retorno, B=1
, de lo contrario, el retorno, B=0
. A continuación, B
tiene probabilidad de $\frac1{\sqrt2}$ 1
.
El número medio de imparcial bits necesarios para generar N
es 2, por lo tanto, el número medio de imparcial bits necesarios para obtener cada uno (parcial) bit B
2+4=6.