Modificar el rango de un generador de números aleatorios uniforme

Question

Me da una función rand5() que genera, con una distribución uniforme, un entero aleatorio en el intervalo cerrado [1,5]. ¿Cómo puedo usar rand5(), y nada más, para crear una función rand7(), que genera enteros en [1,7] (de nuevo, uniformemente distribuidos)?

---

1. busqué stackoverflow, y encontró muchas preguntas similares, pero no exactamente como éste.
2. Mi primer intento fue rand5() + 0.5 * rand5() + 0.5 * rand5(). Pero esto no generará números enteros del 1 al 7 con probabilidad uniforme. Cualquier respuesta, o enlaces a respuestas, son bienvenidos.

Answer 1

bien, tuve que pensarlo un tiempo, pero en realidad no es tan difícil. Imagínese en lugar de rand5 que tenía rand2 que, o bien las salidas 0 o 1. Puede hacer que nuestra rand2 de rand5 simplemente haciendo

rand2() { 
    if(rand5() > 2.5) return 1 
    else return 0 
} 

ahora usando rand2 varias veces a hacer un árbol para obtener rand7. Por ejemplo, si comienza rand7 puede estar en [1,2,3,4,5,6,7] después de un lanzamiento de rand2 que le da 0 ahora subconjunto a [1,2,3,4] y después de otro lanzamiento o rand2 que es 1 subconjunto a [3,4] y un tiro final de 1 da la salida de rand7 a 4. En general, este truco de árbol puede funcionar para tomar un rand2 y mapear a randx donde x es cualquier número entero.

Answer 2

Tenga en cuenta que una distribución uniforme prefecto no puede ser alcanzado con un número acotado de draw5() invocaciones, ya que por cada k: 5^k % 7 != 0 - por lo que siempre tendrá algunos elementos "sobrantes".

Aquí es una solución con número ilimitado de draw5() usos:

Dibuje dos números, X1, X2. Hay 5 * 5 = 25 resultados posibles para esto.

Tenga en cuenta que 25/7 ~ = 3.57. Elija 3 * 7 = 21 combinaciones, de modo que cada combinación se correlacionará con un número en [1,7], para los otros 4 números - vuelva a dibujar.

Por ejemplo:

(1,1),(1,2),(2,1) : 1 
(3,1),(1,3),(3,2): 2 
(3,3),(1,4),(4,1): 3 
(2,4),(4,2)(3,4): 4 
(4,3), (4,4), (1,5): 5 
(5,1), (2,5), (5,2) : 6 
(5,3), (3,5), (4,5) : 7 
(5,4),(5,5),(2,3), (2,2) : redraw 

Answer 3

Aquí está una manera simple:

1. Uso rand5() para generar una secuencia de tres números enteros aleatorios del conjunto {1, 2, 4, 5} (es decir, deseche cualquier 3 que se genere).
2. Si los tres números están en el conjunto {1, 2}, descarte la secuencia y vuelva al paso 1.
3. Para cada número en la secuencia, correlaciona {1, 2} a 0 y {4, 5} a 1. Use estos como los valores de tres bits para un número de 3 bits. Debido a que los bits no pueden ser todos 0, el número estará en el rango [1, 7]. Como cada bit es 0 o 1 con igual probabilidad, la distribución sobre [1, 7] debe ser uniforme.

Answer 4

Aquí hay un meta-truco que es útil para muchos de estos problemas: el sesgo se presenta cuando tratamos los términos de manera diferente, por lo que si los tratamos igual en cada paso y realizamos operaciones solo en el establecer, nos mantendremos fuera de problemas.

Tenemos que llamar a rand5() al menos una vez (¡obviamente!), Pero si ramificamos en ese mal, las cosas suceden a menos que seamos inteligentes. Así que en lugar vamos a llamarlo una vez para cada uno de los 7 posibilidades:

In [126]: import random 

In [127]: def r5(): 
    .....:  return random.randint(1, 5) 
    .....: 

In [128]: [r5() for i in range(7)] 
Out[128]: [3, 1, 3, 4, 1, 1, 2] 

Es evidente que cada uno de estos términos fue la misma probabilidad de ser cualquiera de estos números .. pero sólo uno de ellos pasó a ser de 2, por lo que si nuestra regla había sido "elegir el término que rand5() devuelva 2 para", entonces habría funcionado. O 4, o lo que sea, y si simplemente hiciéramos un bucle lo suficiente como para que sucediera. Entonces, hay muchas formas de encontrar algo que funcione. Aquí (en pseudocódigo - esto es terrible Python) es una manera:

import random, collections 

def r5(): 
    return random.randint(1, 5) 

def r7(): 
    left = range(1, 8) 
    while True: 
     if len(left) == 1: 
      return left[0] 
     rs = [r5() for n in left] 
     m = max(rs) 
     how_many_at_max = rs.count(m) 
     if how_many_at_max == len(rs): 
      # all the same: try again 
      continue 
     elif how_many_at_max == 1: 
      # hooray! 
      return left[rs.index(m)] 
     # keep only the non-maximals 
     left = [l for l,r in zip(left, rs) if r != m] 

que da

In [189]: collections.Counter(r7() for _ in xrange(10**6)) 
Out[189]: Counter({7: 143570, 5: 143206, 4: 142827, 2: 142673, 6: 142604, 1: 142573, 3: 142547})