Haciendo fuentes aleatorio distribuido uniformemente

Question

¿Cómo construir una fuente aleatoria que da salida a los bits 0 y 1 con $ prob (0) = Prob (1) = 0,5 $. Tenemos acceso a otra fuente aleatoria $ S $ que las salidas $ ao $ b $ con probabilidades independientes $ prob $ (a) $ y $ prob (b) = 1 -. Prob (a) $ que son desconocidas para nosotros

¿Cómo afirmar un algoritmo que hace el trabajo y que no consume más de un número esperado de $ (Prob (a) \ cdot prob (b)) ^ {- 1} $ símbolos de $ S $ entre dos bits de salida y probar su correcteness

Answer 1

Considere esto: tiene dos elementos x 0 $ $ y $ $ x 1 desde $ S $. Si x_0x_1 $ $ es $ aa $ o $ $ bb luego desecharlos y repetir. De lo contrario, devolver $ 0 $ de $ AB $ y $ 1 $ de $ ba $, eventos que se producen con la misma probabilidad p_ap_b $ $.

Esto utilizará $ 2n elementos $ De $ S $, $ n $ El número de etapas realizadas. La probabilidad de parar en cada paso es $ p = 1-2p_ap_b $. El valor esperado de $ 2n $ es por lo tanto $$ 2p \ sum_ {n = 1} ^ {n 8 (1-p) ^ {n-1}} = \ frac {2P} {(1- (1-p) ) ^ 2} = \ frac {1} {p_ap_b} \ enspace. $$