¿Es posible emular el lanzamiento de una moneda de dos caras (50/50) con un generador de números aleatorios que produzca equiprobablemente los números 1, 2 y 3? En caso afirmativo, ¿cómo?
Si no es así, ¿por qué?
¿Existe un teorema?
¿Puede ampliarse a cualquier número x ("caras" de la moneda) e y (salida del generador aleatorio)?
Sí, por supuesto. La forma más sencilla de hacerlo es tratar $1$ como cabezas, $2$ como colas, e inténtalo de nuevo si obtienes un $3$ .
El mismo enfoque funciona siempre que $y>x$ . Si $y<x$ , elija $n$ lo suficientemente grande como para que $y^n>x$ , entonces genera $n$ números a la vez y utilizar el enfoque anterior con el resultado $n$ -tuplas.
En general, deberá consultar el $3$ -generador de valores menos veces que el número de bits que se quiere producir, ya que la cantidad de entropía por consulta es $\log(3)/\log(2)=1.58496...$ bits. Sin embargo, como $\log(3)/\log(2)$ es irracional, no hay un número finito de consultas que pueda convertirse en un número fijo de bits. Lo mejor que se puede hacer es conservar la aleatoriedad redondeada y guardarla para un uso posterior, de la siguiente manera:
Comienza con $(x,w)=(0,1/3)$ .
Dejemos que $(x,w)=(x+aw,w/3)$ , donde $a=0,1,2$ con igual probabilidad (utilizando el $3$ -generador de valores).
Repita estas comprobaciones siempre que pase una: (a) Si $x\ge 1/2$ , salida " $1$ ", entonces deja que $(x,w)=(2x-1,2w)$ o (b) si $x+3w<1/2$ , salida " $0$ ", entonces deja que $(x,w)=(2x,2w)$ .
Vuelva al paso 2.
Lo que hace es generar las sucesivas cifras ternarias de un número real en $[0,1)$ y emite cada dígito binario del mismo número real en cuanto se conoce con certeza. Esto es esencialmente codificación aritmética y, por supuesto, puede utilizarse para dos bases cualesquiera.
Aquí está la solución al problema general: cómo muestrear con probabilidad p dado un dado con b caras. Ilustrado aquí con p = 1/pi y b = 6.
Escribe p en base b: p = 0,152431022133341414... (Por supuesto, si p es racional esta es una secuencia recurrente).
Lanza el dado para generar un conjunto de dígitos aleatorios en [0, b) = 1 3 5 2 ... y escribir como número real q en base b = 0,1352...
Devuelve q < p. Normalmente sólo hay que generar 1-2 dígitos aleatorios.
Curiosamente, el muestreo con probabilidad 1/pi puede hacerse sin conocer el valor de pi utilizando un teorema de Ramanujan. Véase
http://randomlib.sf.net/1.6/classRandomLib_1_1InversePiProb.html
y sus referencias.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
