¿Cómo implementar Random (a, b) con solo Random (0,1)?

Duplicar posible:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)¿Cómo implementar Random (a, b) con solo Random (0,1)?

En el libro de Introducción a los algoritmos, hay un especial:

describir una aplicación del procedimiento aleatorio (a, b) que solo hace llamadas a Aleatorio (0,1). ¿Cuál es el tiempo de ejecución esperado de su procedimiento, como una función de a y b? La probabilidad del resultado de Random (a, b) debe ser puramente distribuida uniformemente, como Random (0,1)

Para la función Random, los resultados son enteros entre ayb, inclusive. Por ejemplo, Random (0,1) genera 0 o 1; Aleatorio (a, b) genera a, a + 1, a + 2, ..., b

Mi solución es la siguiente:

for i = 1 to b-a 
    r = a + Random(0,1) 
return r

el tiempo de ejecución es T = ba

¿Es esto correcto? ¿Los resultados de mis soluciones están distribuidos uniformemente?

Gracias

¿Qué pasa si mi nueva solución es la siguiente:

r = a 
for i = 1 to b - a //including b-a 
    r += Random(0,1) 
return r

Si no es correcto, ¿por qué r + = aleatorio (0,1) hace r no se distribuye de manera uniforme?

Fuente

2012-01-01 Jackson Tale

Su solución no se distribuye uniformemente. Como ejemplo, el valor más bajo 'a' solo puede ser" calculado "por la suma de random (0) + random (0) + random (0) + .... pero la probabilidad de un valor en" the middle "es más alto porque se puede calcular como 0 + 0 + 0 + 1 + 1, y 0 + 0 + 1 + 0 + 1, y 1 + 1 + 0 + 0 + 0, y así sucesivamente. Piensa que es como tirar 2 dados. La probabilidad de obtener 2 (1 + 1) o 12 (6 + 6) es menor que la probabilidad de obtener 7 (1 + 6,2 + 5,3 + 4,4 + 3,5 + 2,6 + 1) (colonos de catan ftw.;)). – Progman

Su segunda línea restablece 'r' cada vez. Debería inicializarlo en 'a' y luego actualizarlo en términos de sí mismo en el ciclo. –

Otros han explicado por qué su solución no funciona. Aquí está la solución correcta:

1) Encuentre el número más pequeño, p, tal que 2^p > b-a.

2) Realice el siguiente algoritmo:

r=0 
for i = 1 to p 
    r = 2*r + Random(0,1)

3) Si r es mayor que b-a, vaya al paso 2.

4) Su resultado es r+a

Así que vamos a tratar aleatoria (1,3)
Así es b-a 2.
2^1 = 2, por lo p tendrá que ser 2 para que 2^p es mayor que 2.
por lo que vamos bucle dos veces.Vamos a tratar todas las salidas posibles:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1. 
01 -> r=1, 1 is not > 2, so we output 1+1 or 2. 
10 -> r=2, 2 is not > 2, so we output 2+1 or 3. 
11 -> r=3, 3 is > 2, so we repeat.

Así 1/4 del tiempo, la salida 1. 1/4 del tiempo de salida que 2. 1/4 de la salida que el tiempo 3. Y un cuarto de el tiempo que tenemos para repetir el algoritmo por segunda vez. Se ve bien.

Tenga en cuenta que si usted tiene que hacer esto mucho, dos optimizaciones son útiles:

1) Si se utiliza la misma gama mucho, tiene una clase que calcula p vez por lo que no tiene que calcular cada vez

2) Muchas CPU tienen formas rápidas de realizar el paso 1 que no están expuestas en lenguajes de alto nivel. Por ejemplo, las CPU x86 tienen la instrucción BSR.

Fuente

2012-01-01 11:42:08

Entonces la idea aquí es encontrar el número máximo de bits que uno necesitaría para representar el número más alto, y luego simplemente lanzar la moneda para cada uno de esos bits. –

Sí. Y luego, si está fuera de rango, repita el proceso. –

Llego a algo similar, pero más bien en una forma de búsqueda binaria. Gracias, es bueno ver que estuvo bien. Sin embargo, esperaba una forma inteligente de reducir el problema de potencia de 2 a cualquier número (y mejor O-grande). – gorlum0

No, no es correcto, ese método se concentrará alrededor de (a+b)/2. Es una distribución binomial.

¿Estás seguro de que Random(0,1) produce enteros? tendría más sentido si produjera valores de coma flotante entre 0 y 1. Entonces la solución sería una transformación afín, con un tiempo de ejecución independiente de a y b.

Una idea que acabo de tener, en caso de que se trate de valores enteros: use la bisección. En cada paso, tiene un rango low-high. Si Random(0,1) devuelve 0, el siguiente rango es low-(low+high)/2, de lo contrario (low+high)/2-high. Detalles y complejidad que le quedan, ya que son tareas.

Eso debería crear (aproximadamente) una distribución uniforme.

Editar:aproximadamente es la palabra importante allí. Uniforme si b-a+1 tiene una potencia de 2, no demasiado lejos si está cerca, pero no lo suficientemente bueno en general. Ah, bueno, fue una idea espontánea, no puedo solucionarlos.

Fuente

2012-01-01 11:19:52

Aquí hay una cita del libro: Asumiremos que tenemos a nuestra disposición un generador de números aleatorios RANDOM. Una llamada a RANDOM (a, b) devuelve un número entero entre ayb, ambos inclusive, siendo cada uno de ellos igualmente probable. Por ejemplo, RANDOM (0, 1) produce 0 con probabilidad 1/2, y produce 1 con probabilidad 1/2 –

Aha. Correcto, habría sido demasiado fácil de lo contrario. Olvidé la primera línea cuando vi la etiqueta de tarea :) –

@DanielFischer Eso solo producirá una distribución aproximadamente uniforme. Considera (1,3). –

En primer lugar, supongo que en realidad está acumulando el resultado, sin agregar 0 o 1 a un en cada paso. Usando algunas probabilidades, puede probar que su solución no está distribuida uniformemente. La posibilidad de que el valor resultante r sea (a + b)/2 es mayor.Por ejemplo, si a es 0 yb es 7, la probabilidad de que obtenga un valor 4 es (combinación 4 de 7) dividida por 2 elevada a la potencia 7. La razón es que no importa cuál de los 4 valores de 7 son 1, el resultado seguirá siendo 4.

El tiempo de ejecución estimado es el correcto. pseudocódigo

Fuente

2012-01-01 11:22:29

-1

Tu de la solución debe verse como:

r=a 
for i = 0 to b-a 
    r+=Random(0,1) 
return r

En cuanto a la distribución uniforme, en el supuesto de que la aplicación aleatoria de este generador de números aleatorios se basa en es perfectamente uniforme las probabilidades de conseguir 0 o 1 son 50%. Por lo tanto, obtener el número que desea es el resultado de esa elección hecha una y otra vez.

Así que para a = 1, b = 5, hay 5 elecciones realizadas.

las probabilidades de conseguir 1 implica 5 decisiones, todos 0, las probabilidades de que son 0,5^5 = 3,125%

las probabilidades de conseguir 5 implica 5 decisiones, todos 1, las probabilidades de que son 0,5^5 = 3.125%

Como puede ver en esto, la distribución no es uniforme: las probabilidades de cualquier número deben ser del 20%.

Fuente

2012-01-01 11:22:31

En el algoritmo que ha creado, en realidad no se distribuye por igual.

El resultado "r" siempre será "a" o "a + 1". Nunca irá más allá de eso.

Debe ser algo como esto:

r=0; 
for i=0 to b-a 
    r = a + r + Random(0,1) 

return r;

Con la inclusión de la "r" en su cálculo, se está incluyendo la "aleatoriedad" de todas las anteriores "para" se ejecute el bucle.

Fuente

2012-01-01 11:26:00

No, su solución no es correcta. Esta suma tendrá distribución binomial.

Sin embargo, puede generar una secuencia aleatoria pura de 0, 1 y tratarla como un número binario.

repeat 
    result = a 
    steps = ceiling(log(b - a)) 

    for i = 0 to steps 
    result += (2^i) * Random(0, 1) 
until result <= b

KennyTM: my bad.

Fuente

2012-01-01 11:41:27 Arenielle

'2^(i * Aleatorio (0, 1))'? ¿Te refieres a '(2^i) * Aleatorio (0, 1)'? – kennytm

He leído las otras respuestas. Para divertirse, aquí hay otra forma de encontrar el número aleatorio:

Asignar una matriz con elementos b-a. Establezca todos los valores en 1. Iterar a través de la matriz. Para cada elemento distinto de cero, voltea la moneda, por así decirlo. Si se trata de 0, configure el elemento en 0.

Siempre que, después de una iteración completa, es suficiente con 1 elemento restante, que tenga su número al azar: a+i donde i es el índice del elemento distinto de cero (suponiendo que partimos de indexación en 0). Todos los números son igualmente probables. (Usted tendría que tratar con el caso en el que es un empate, pero lo dejo como ejercicio para usted.)

Esto tendría O(infinity) ... :) En promedio, sin embargo, la mitad de los números serían eliminados , por lo que tendría un tiempo promedio de ejecución de casos de log_2 (b-a).

Fuente

2012-01-01 11:56:19

En realidad, puede hacer que esto funcione razonablemente y si lo hace bien, es O (n log n) (donde n = b-a).Básicamente, si desea incrementar cada elemento de la matriz si Random (0,1) es 1, considere cada elemento en ejecución si su valor es menor que un punto de corte. Aumenta el límite después de cada pase y si no hay valores válidos, disminuye el límite. Cuando una entrada es válida, has terminado. –

¿Cómo implementar Random (a, b) con solo Random (0,1)?

Respuesta

Cuestiones relacionadas