Cómo escalar un número entero aleatorio en $[A,B]$ y producir un número entero aleatorio en $[C,D]$

Question

Sé que hay muchos métodos para escalar un número a partir de un rango $[A,B]$ a una gama $[C,D]$ y he buscado una y otra vez en la web. He visto este hilo de math.SE .

Necesito escalar un gran número (entero de 32 bits con signo) entre $-2147483648$ y $2147483647$ a un intervalo más pequeño (de 0 a millones).

Sin embargo, el número original es generado por un generador de números aleatorios que no puedo controlar de ninguna manera, por lo que debo estar seguro de que la fórmula de salida no altera su aleatoriedad (de una manera que pueda demostrar - los trabajos académicos son bien aceptados).

Necesito la forma correcta de escalar este número teniendo en cuenta que:

• el rango de salida debe tener como valor máximo una potencia de dos (por ejemplo, $4194304$ )
• la fórmula puede demostrarse
• la fórmula no altera la aleatoriedad del número de origen

¿Alguien puede ser de ayuda?

Answer 1

Como se ha señalado en otras respuestas, esto es imposible; en concreto, se parte de una distribución discreta, en la que cada resultado tiene una probabilidad de $2^{-32}$ . Ahora, si tomas alguna función $f$ tomando tales resultados aleatorios y dando como salida un número entero en el rango deseado, entonces está claro que la probabilidad de recibir algún $n$ ya que la salida es igual a $2^{-32}$ veces el número de resultados $x$ tal que $f(x)=n$ - en particular, la probabilidad es siempre múltiplo de $2^{-32}$ . Por desgracia, cifras como $\frac{1}3$ no son múltiplos de $2^{-32}$ por lo que no podemos obtener una distribución uniforme en tres números (seamos nosotros puede obtener una distribución uniforme en $2^n$ resultados para $n\leq 32$ simplemente truncando el número).

Sin embargo, he aquí un procedimiento estándar y sencillo para generar un número entero aleatorio en $[1,N]$ dada la capacidad de generar una aleatoria en $[1,M]$ para $M\geq N$ . Su problema es fácilmente bajo esta clase.

Supongamos que $M=aN + b$ donde $a$ es un número entero y $b$ es positivo y menor que $N$ - es decir, $b$ es el resto de $M$ dividido por $N$ y $a$ es la parte entera del cociente. Generar un entero $x$ en $[1,M]$ . Si es inferior o igual a $aN$ devuelve el resto de $x_0$ dividido por $N$ . En caso contrario, genera otro entero en $[1,M]$ y comprobar si es inferior a $aN$ . Repetir indefinidamente.

Es decir, para generar un número aleatorio, se descartan ciertos resultados y se vuelve a intentar. Por ejemplo, si quisiéramos generar un número entero aleatorio en $[1,2]$ la capacidad de hacerlo en $[1,3]$ simplemente seguimos encontrando números aleatorios en $[1,3]$ hasta que uno de ellos $1$ o $2$ . Se trata claramente de una distribución uniforme. En el lo peor el método anterior arroja unos $\frac{1}2$ de los resultados generados. Sin embargo, si está generando números en $[1,2^{32}]$ y buscando un número aleatorio entre $1$ y un millón, aceptará casi todos los números aleatorios que obtenga (por ejemplo, alrededor del 99,97%), por lo que no hay una gran pérdida de eficiencia.

Answer 2

Parece que el número de entrada es una secuencia de 32 bits (interpretada como un entero con signo). Si la salida deseada es también una secuencia aleatoria de $n$ bits, para algunos $n < 32$ una forma sencilla es truncar la secuencia de entrada en el primer $n$ bits. Está bastante claro que si la entrada está uniformemente distribuida, la salida también lo estará.

Pero si la salida está en un rango de $N$ posibilidades, donde $N$ no es una potencia de 2, entonces no puede distribuirse uniformemente entre esas posibilidades. Así que no conseguirás que tu salida sea completamente aleatoria en ese caso. Podemos demostrarlo con un simple argumento de conteo.

AÑADIDO: Un argumento de recuento también demuestra la distribución uniforme mencionada anteriormente. Por ejemplo, supongamos que la entrada se distribuye uniformemente de $-2^{31}$ a $2^{31}-1$ y la salida deseada es de $0$ a $2^{22}-1$ . Podemos truncar tirando los bits más significativos con la función $y = (x + 2^{31}) \mod 2^{22}$ . La función asigna exactamente ${2^{32}}/{2^{22}} = 2^{10}$ valores de entrada a cada valor de salida. Suponemos que la probabilidad de obtener cualquier valor de entrada particular es $1 / 2^{32}$ por lo que la probabilidad de obtener un valor de salida determinado es $2^{10} / 2^{32} = 1 / 2^{22}$ lo que significa que cualquier valor de salida es igualmente probable.

Answer 3

Esto funciona en casos especiales:

Sea $[a,b]$ sea un intervalo y consideremos una distribución uniforme en los intervalos de este intervalo. Sea $k$ sea el número de enteros en $[a,b]$ .

Sea $[c,d]$ sea otro intervalo y supongamos que el número de enteros en este intervalo es $l$ .

GRAN SUPUESTO: Supongamos que $l\mid k$ .

Entonces, cualquier $\frac{k}{l}=m$ a $1$ le dará una distribución uniforme en $[c,d]$ .

Por ejemplo, si tiene el número $n$ , podrías tomar $n\pmod l$ y, a continuación, añada $c$ .

Si no tienes la GRAN SUPOSICIÓN, entonces puedes ser capaz de ponderar el mapa descrito aquí, (y no tenerlo exactamente $m$ a $1$ Pero eso es más difícil y depende de la situación).