Generador de números aleatorios imparcial utilizando uno sesgado

Question

Tiene un generador de números aleatorios sesgados que produce un 1 con una probabilidad p y 0 con una probabilidad (1-p). No sabes el valor de p. Usando esto crea un generador imparcial de números aleatorios que produce 1 con una probabilidad de 0.5 y 0 con una probabilidad de 0.5.

Nota: este problema es un problema de ejercicio de Introducción a los algoritmos de Cormen, Leiserson, Rivest, Stein (CLR)

Answer 1

Los eventos (p) (1-p) y (1-p). (p) son equiprobables. Tomándolos como 0 y 1 respectivamente y descartando los otros dos pares de resultados obtienes un generador aleatorio imparcial.

En el código esto se hace tan fácil como:

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

Es necesario llamar la pares de los valores del generador de números aleatorios hasta que se obtiene una secuencia de valores diferentes, es decir CERO seguido de uno o uno seguido de cero. Luego tomas el primer valor (o el último, no importa) de esa secuencia. (Es decir, repetir siempre que el par dibujado sea dos ceros o dos)

La matemática detrás de esto es simple: una secuencia 0 luego 1 tiene la misma probabilidad que una secuencia 1 luego cero. Tomando siempre el primer (o el último) elemento de esta secuencia como la salida de su nuevo RNG, tenemos la posibilidad de obtener un cero o uno.

Answer 3

Aquí hay una forma, probablemente no la más eficiente. Mastica un montón de números aleatorios hasta que obtengas una secuencia de la forma [0 ..., 1, 0 ..., 1] (donde 0 ... es uno o más 0). Cuenta el número de 0. Si la primera secuencia es más larga, genere un 0, si la segunda secuencia es más larga, genere un 1. (Si son iguales, intente nuevamente.)

Esto es como lo que hace HotBits para generar números aleatorios a partir de radiactivo decaimiento de partículas:

Dado que el tiempo de cualquier caída es aleatorio, el intervalo entre dos decaimientos consecutivos también es aleatorio. Lo que hacemos, entonces, es medir un par de estos intervalos y emitir un cero o un bit en función de la longitud relativa de los dos intervalos. Si medimos el mismo intervalo para las dos desintegraciones, descartamos la medición y tratar de nuevo

HotBits: How It Works

Answer 4

El truco atribuido a von Neumann de conseguir dos bits a la vez, que tiene 01 correspondo a 0 y 10 a 1, y repetir para 00 u 11 ya ha aparecido. El valor esperado de los bits que necesita extraer para obtener un solo bit con este método es 1/p(1-p), que puede ser bastante grande si p es especialmente pequeño o grande, por lo que vale la pena preguntar si el método puede mejorarse, especialmente dado que es evidente que arroja mucha información (todos los casos 00 y 11).

En busca de "von neumann trick biased" producido this paper que desarrolla una mejor solución para el problema. La idea es que aún tomes bits de dos en dos, pero si los dos primeros intentos producen solo 00 y 11, debes tratar un par de 0 como un único 0 y un par de 1 como un solo 1, y aplicar el truco de von Neumann. a estos pares. Y si eso tampoco funciona, siga combinándose de manera similar en este nivel de pares, y así sucesivamente.

Más adelante, el trabajo se desarrolla esto en la generación de múltiples bits recomendaciones de la fuente de polarización negativa, usando esencialmente dos formas diferentes de la generación de los bits a partir de los pares de bits, y dando un boceto que esto es óptimo en el sentido de que produce exactamente el número de bits que la secuencia original tenía entropía.

Answer 5

El procedimiento para produce an unbiased coin from a biased one se atribuyó primero al Von Neumann (un tipo que ha hecho un trabajo enorme en matemáticas y en muchos campos relacionados). El procedimiento es super simple:

• lanzar la moneda dos veces.
• Si los resultados coinciden, vuelva a empezar, olvidando ambos resultados.
• Si los resultados difieren, use el primer resultado, olvidando el segundo.

La razón funciona este algoritmo se debe a que la probabilidad de obtener HT es p(1-p), lo que es lo mismo que recibir TH (1-p)p. Por lo tanto, dos eventos son igualmente probables.

También estoy leyendo este libro y me pregunta el tiempo de ejecución esperado. La probabilidad de que dos lanzamientos no sean iguales es z = 2*p*(1-p), por lo tanto, el tiempo de ejecución esperado es 1/z.

---

El ejemplo anterior se ve animando (después de todo, si usted tiene una moneda sesgada con un sesgo de p=0.99, tendrá que tirar la moneda de aproximadamente 50 veces, lo que no es que muchos). Entonces, podrías pensar que este es un algoritmo óptimo. Lamentablemente no lo es.

Así es como se compara con Shannon's theoretical bound (la imagen está tomada de este answer). Muestra que el algoritmo es bueno, pero dista de ser óptimo.

uno se puede topar con una mejora si se quiere considerar que HHTT será desechado por este algoritmo, pero en realidad tiene la misma probabilidad que TTHH. Entonces también puede detenerse aquí y regresar H. Lo mismo sucede con HHHHTTTT y demás. El uso de estos casos mejora el tiempo de ejecución esperado, pero no lo hace teóricamente óptimo.

---

Y al final - código Python:

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

es bastante explica por sí mismo, y aquí es un resultado ejemplo:

0.0973181652114 
505 495 

Como se ve, sin embargo, tuvimos un sesgo de 0.097, tenemos aproximadamente el mismo número de 1 y 0