2012-07-03 15 views
5

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)?Modificar el rango de un generador de números aleatorios uniforme


  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.
+0

Nota adicional: en general, resumiendo rand5() no funcionará. Al sumar más de rand5(), comenzaremos a desviarnos de la distribución uniforme, y comenzaremos a aproximarnos a una distribución normal. –

+2

Parece un duplicado para http://stackoverflow.com/questions/10464360/use-rand5-to-generate-rand7-with-the-same-probability – Mathias

+0

@Mathias, no, estas no son la misma pregunta, una tu enlace es sobre no poder generar números pseudoaleatorios usando C# – unkulunkulu

Respuesta

2

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.

+0

rand2 devolverá 0 cuando rand5 devuelva 1 o 2; devolverá 1 cuando rand5 devuelva 3, 4 o 5. Necesita rand2 para devolver 0 o 1 con la misma probabilidad. –

+1

Es cierto, bueno, todavía podría hacer que la función rand2 reinicie rand5 si fuera 3 – hackartist

+0

Había comenzado a lo largo de esta línea, y estaba atrapado en la observación hecha por Ted Hopp. Nunca pensé en reutilizar rand2() si el primer lanzamiento me dio 3. ¡Uf, y doble ugh! Me gusta mucho este enfoque, porque detrás de mi pregunta radica la generalización, exactamente como lo señala @hackartist, y este es un proceso finito en el sentido de que Pr (el proceso nunca termina) = 0. –

7

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 
+0

tenemos la posibilidad de dibujar infinitamente (con una probabilidad de 0) :) Aunque creo que eso es imposible de implementar sin ese detalle :) Oh, tienes la prueba de la imposibilidad, luego limpia +1 :) – unkulunkulu

+0

@unkulunkulu : Lea mi edición (última oración) por qué no se puede hacer una distribución uniforme perfecta con el número limitado de draw5 ops – amit

+0

Le sugiero que mueva esa oración al principio, ya que esto es lo que espera el autor (una solución perfecta matemáticamente) – unkulunkulu

4

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.
+0

good answer , Me pregunto cómo se generaliza si el número inicial fue y en lugar de 5 y el número objetivo fue x en lugar de 7 ... – hackartist

+0

Al igual que la solución de amit, no se garantiza que sea un proceso finito. –

+0

@hackartist - Creo que este tipo de muestreo de rechazo debería ser bastante fácil de generalizar a cualquier par de rangos. –

2

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}) 
+0

Un enfoque muy interesante, pero: I No entiendo por qué debería funcionar (es decir, podemos utilizar uno de los otros algoritmos sugeridos en lugar de descartar algunos números en particular, solo contarlos como uno de los 7 números, para que, por ejemplo, se obtenga un uniforme distribución, pero no al azar, por lo que esta muestra no prueba nada. Además, esta solución busca desperdiciar aún más números que otros. – unkulunkulu

+0

@unkulunkulu: No hice ningún reclamo de eficiencia. Sin embargo, ¿qué te preocupa del enfoque? En cada iteración, cada término tiene la misma posibilidad de ser devuelto o eliminado. – DSM

+0

Lo que me molesta es que el algoritmo es algo complicado, primero se dibuja una idea básica (que tampoco es muy clara), luego se presenta un fragmento de código sin tratar de probar que funcionará. Y no veo una razón para estas complicaciones: no es más rápido, no es más simple, no se garantiza que regrese en un tiempo finito. Es interesante simplemente porque no está claro si es correcto o no. – unkulunkulu

Cuestiones relacionadas