El uso de una probabilidad establece para generar otro [duplicado]

Question

    

Esta pregunta ya tiene una respuesta aquí:

    

        
•              Expandir un intervalo aleatorio de 1-5 a 1-7                                      77 respuestas                          
    

    

¿Cómo puedo generar una mayor probabilidad fijar de un conjunto menor probabilidad? Esto es de
Manual de Diseño de Algoritmos -Steven Skiena
Q:

  

Utilice un generador de números aleatorios (rng04) que genera números de {0,1,2,3,4} con igual probabilidad para escribir un generador de números aleatorios que genera números de 0 a 7 (rng07) con igual probabilidad

He intentado durante alrededor de 3 horas ahora, en su mayoría sobre la base de la suma de dos salidas rng04. El problema es que en ese caso la probabilidad de cada valor es diferente - 4 puede venir con 5/24 de probabilidad, mientras que 0 ocurra es 1/24. He intentado algunas maneras de enmascarar, pero no puedo.

¿Alguien puede solucionar esto?

Answer 1

Tienes que encontrar una manera de combinar los dos conjuntos de números aleatorios (la primera y la segunda {0,1,2,3,4} al azar) y hacer n*n posibilidades distintas. Básicamente el problema es que con la adición a obtener algo como esto

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

¿Qué tiene duplicados, que no es lo que desea. Una forma posible combinar los dos conjuntos serían los Z = X + Y*5 donde X y Y son los dos números aleatorios. Eso le daría un conjunto de resultados como éste

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

Así que ahora que tiene un conjunto más amplio de números aleatorios, lo que necesita hacer a la inversa y hacerlo más pequeño. Este conjunto ha 25 valores distintos (ya que se utilizaron 5, y se utilizan dos números aleatorios, por lo 5*5=25). El conjunto que desee tiene 8 valores distintos. Una forma de hacer esto ingenuo sería

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

Esto de hecho tener una gama de {0,7}. Pero los valores {1,7} aparecería 3/25 veces, y el valor 0 aparecería 4/25 veces. Esto se debe a 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 y 24 mod 8 = 0 .

Para solucionar este problema, puede modificar el código anterior a esta.

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

Esto tomará el valor de uno (24) que está arrojando sus probabilidades y lo descarta. Generar un nuevo número aleatorio si se obtiene una 'mala' valor como esto hará que su algoritmo muy poco más largo (en este caso 1/25 del tiempo que tomará 2x siempre a correr, 1/625 tomará como 3x de largo, etc). Pero que le dará las probabilidades correctas.

Answer 2

El verdadero problema, por supuesto, es el hecho de que los números en el medio de la suma (4 en este caso) se producen en muchas combinaciones (0 + 4, 1 + 3, etc.), mientras que 0 y 8 tienen exactamente una manera de ser producido.

No sé cómo resolver este problema, pero voy a tratar de reducir un poco para usted. Algunos puntos a considerar:

• El rango de 0-7 tiene 8 valores posibles, por lo que en última instancia, el número total de posibles situaciones que deben aspirar a tiene que ser un múltiplo de 8. De esta manera se puede tener un número entero de distribuciones por valor en que codominio.
• Cuando se toma la suma de dos funciones de densidad, el número de posibles situaciones (no necesariamente distintos cuando se evalúa la suma, sólo en términos de distintas combinaciones de entradas) es igual al producto del tamaño de cada una de las entradas sets.
• Por lo tanto, dados dos conjuntos {0,1,2,3,4} suman entre sí, tienes 5 * 5 = 25 posibilidades.
• No será posible obtener un múltiplo de ocho (véase el primer punto) de las potencias de 5 (véase el segundo punto, pero extrapolar a cualquier número de conjuntos> 1), por lo que tendrá que tener un excedente de posible situaciones en su función y pasar por alto algunos de ellos si se presentan.
• La forma más sencilla de hacerlo, por lo que yo puedo ver en este punto, es utilizar la suma de dos {0,1,2,3,4} conjuntos (25 posibilidades) e ignorar 1 (dejar 24 , un múltiplo de 8).
• Así, el reto ahora se ha reducido a esto: Encontrar una manera de distribuir los 24 restantes posibilidades entre los valores de salida 8. Para ello, es probable que no desea utilizar la suma, sino sólo los valores de entrada.

Una forma de hacerlo es, imaginar un número en base 5 construido a partir de su entrada. No haga caso de 44 (que es el 25, el valor superfluo; si lo consigue, sintetizar un nuevo conjunto de entradas) y tomar las demás, módulo 8, y obtendrá sus 0-7 en 24 combinaciones diferentes de entrada (3 cada uno), el cual es una distribución igual.

Answer 3

Mi lógica sería la siguiente:

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2