¿Cómo se puede generar un número aleatorio distribuido uniformemente en [math] \ {1, 2, \ dots, 7 \} [/ math] con solo un dado con [math] 6 [/ math]?

Answer 1

Ok, aquí está mi opinión sobre esto.

---

¿Puedo reducir este problema a algo que ya sé? Creo que sí, supongamos que tenemos solo 2 números y una moneda y le pedimos que devuelva un número aleatorio entre los dos números.

¿Como lo haras? No lea más a menos que tenga una respuesta a esto o al menos haya ejercitado su cerebro.

.

.

Solo arroje la moneda y, según la cabeza o la cola, puede decidir el número que desea devolver. Entonces, ¿cómo resuelve esta solución el problema actual al que nos enfrentamos, es decir, lanzar un dado y luego devolver un número entre 1 y 7.

¿Podemos hacer que el resultado de lanzar un dado sea igual que lanzar una moneda? Si no lo es. ¿Cómo? El resultado de lanzar un dado puede dividirse en dos grupos, es decir, devolver la cabeza cuando el número está entre 1 y 3 y devolver la cola cuando el número está entre 4 y 6.

Ahora la pregunta se traduce a ¿podemos lanzar una moneda y devolver un número aleatorio entre 1 y 7? Sí, podemos verdad? Pensar.

.

.

Bueno, ¿qué pasa si podemos torcer un poco la pregunta y decir: devolver un número aleatorio entre 1 y 8 usando una moneda justa? Solo tenemos que dividir los números del 1 al 8 en 2 medias, tiene la misma probabilidad de elegir cualquiera de las dos (porque lanzar una moneda genera 0 o 1 con la misma probabilidad ). Esto significa claramente que no habrá ningún caso en el que elegiremos solo 1 mitad de 2, por lo tanto , siempre podemos lograr todos los números .

Código a continuación:

importar al azar
def random_1_8 (inicio, fin):
mientras que (1):
resultado = random.randint (0, 1) # lanzamiento de monedas simulando
si end-start + 1 == 2:
retorno final si el resultado más comienza
mid = (inicio + fin) / 2
if (fin-inicio + 1) == 2:
rotura;
si resultado == 1:
final = medio
más:
inicio = medio + 1
para i en rango (0, 40):
print (random_1_8 (1, 8))

Ahora, ¿qué debemos hacer en caso de que necesitemos devolver un resultado cuando los números son del 1 al 7? En ese caso, todo lo que tenemos que hacer es reiniciar el proceso cuando obtenga 8 según el concepto de muestreo de rechazo.

Código a continuación:

importar al azar
def random_1_7 (inicio, fin):
mientras que (1):
resultado = random.randint (0, 1) # lanzamiento de monedas simulando
si end-start + 1 == 2:
si resultado:
devuelve random_1_7 (1, 8) si end == 8 más end
más:
devuelve random_1_7 (1, 8) si start == 8 else start
mid = (inicio + fin) / 2
if (fin-inicio + 1) == 2:
rotura;
si resultado == 1:
final = medio
más:
inicio = medio + 1
para i en rango (0, 40):
print (random_1_7 (1, 8))

Answer 2

Si bien la respuesta de Michael Jørgensen es probablemente la más simple, la de Richard Morris es la más eficiente, con un promedio de ~ 2.06 tiros. De hecho, existe un método general para resolver todos los problemas de este tipo.

Un problema en este contexto consiste en usar un generador imparcial de números aleatorios de n lados (moneda, dado, etc.) para generar uno de los k resultados, con las probabilidades respectivas p_i donde Σp_i = 1. En este caso, n = 6, k = 7 y p_i = 1/7 para todo i. La generalización de esto a generadores aleatorios sesgados se deja como un ejercicio para el lector 🙂

Una solución consiste en un mapeo parcial f de posibles secuencias de entrada [1..n] * a posibles resultados [1..k] de modo que si f (s) está definido, entonces f (st) no está definido para todas las t no vacías , y Σ 1 / n ^ len (s) = p_i para s tal que f (s) = i. Aplicar la solución implica generar una secuencia de números aleatorios hasta que la secuencia esté en el dominio de f y luego seleccionar el resultado para esa secuencia. El número esperado de selecciones de números aleatorios es igual a Σ len (s) / n ^ len (s) para s de modo que se defina f (s).

Los siguientes diagramas ilustran dos soluciones para n = 2, k = 2, p_1 = 3/4, p_2 = 1/4: es decir, usar una moneda para elegir entre dos eventos con 75% y 25% de probabilidades. La primera solución siempre arroja dos monedas y selecciona 1 para HH, HT y TH y 2 para TT. El segundo arroja una o dos monedas y selecciona 1 para H y TH y 2 para TT. Claramente, la segunda solución es más eficiente que la primera: el número esperado de lanzamientos es 1.5 en lugar de 2.

El siguiente diagrama ilustra una solución para n = 2, k = 2, p_1 = 2/3, p_2 = 1/3. Tenga en cuenta que en esta solución seguimos lanzando monedas hasta obtener una cara, que podría ser indefinidamente. A pesar de esto, el lanzamiento terminará en algún momento con probabilidad 1, y el número esperado de lanzamientos es solo 2.

El siguiente pseudo-algoritmo describe una solución óptima para un problema dado. Funciona comenzando con secuencias cortas y asignando la mayor cantidad posible de ellas a cada color, antes de pasar a la siguiente longitud de secuencias.

f = Ø; S = {ε}
mientras S no está vacío:
para i de 1 a k:
do piso (p_i) veces: f (S.pop ()) = i
p_i = n * (p_i – piso (p_i))
s = {si | s ∈ S, 1 ≤ i ≤ n}

Tenga en cuenta que la función set pop elimina un elemento arbitrario: no importa cuál, aunque las elecciones sensatas pueden hacer que la solución sea más fácil de recordar. Por ejemplo, cuando las probabilidades deseadas son las mismas, usar una función modular como en la respuesta de Richard Morris a menudo puede funcionar bien.

El siguiente diagrama ilustra la aplicación del algoritmo a n = 6, k = 4, p_i = 1/4. Esto corresponde a aceptar de inmediato una tirada de 1 a 4. De lo contrario, reste 5, multiplique por 6, agregue otra tirada de dado y devuelva el módulo de resultado 4. (Restar 5 no es necesario, pero facilita el cálculo).

El siguiente diagrama ilustra el comienzo del algoritmo aplicado a n = 8, k = 3, p_i = 1/3. Esto corresponde a aceptar el módulo de resultado 3 para tiradas hasta 6. De lo contrario, reste 7, multiplique por 8 y agregue otra tirada de dado. Acepte el resultado módulo 3 para valores hasta 15. De lo contrario, comience desde el principio con un nuevo rollo.

En el caso donde k = 2 hay una manera particularmente fácil de generar una solución . Escriba p_1 en la base n (por ejemplo, 1/3 es 0.010101 … en binario, 0.2 en la base 6 y 0.333 … en la base 10). Tira un dado y resta uno (para que los números estén entre 0 y n-1). Si la tirada es estrictamente menor que el primer dígito de p_1, seleccione el resultado 1. Si es estrictamente mayor, seleccione el resultado 2. Si es idéntico y todos los dígitos restantes son 0, luego seleccione el resultado 1. De lo contrario, pase al siguiente dígito y repita con otro dado. El número esperado de tiradas de dado es siempre como máximo n + 1 / n.

Answer 3

Bueno, permítanme repetir primero lo que hizo Michael Jørgensen usando la descomposición de 3 adic.

Anotamos el resultado [math] x = a_0 +3 a_1 [/ math] donde [math] 0 \ leq a_i \ leq 2 [/ math].

Por lo tanto, registramos [math] (a_0, a_1) [/ math], donde [math] a_ {i} [/ math] es un número de puntos [math] \ mod 3 [/ math] en el primer resp. segundo lanzamiento

Si obtenemos [matemáticas] x = 0 [/ matemáticas] o [matemáticas] x = 8 [/ matemáticas], comenzamos de nuevo.

Deje que [matemáticas] n [/ matemáticas] sea el número promedio de lanzamientos necesarios para obtener un resultado. Luego, usando el promedio condicional vemos:

[matemáticas] n = \ frac {7} {9} \ cdot 2 + \ frac {2} {9} \ cdot (2 + n) [/ matemáticas]

Por lo tanto, necesitaría en promedio [math] \ frac {18} {7} \ approx 2.57 [/ math] tiros.

Si utilizara el método original de Michael, necesitaría en promedio tiros de [matemática] m [/ matemática], donde [matemática] m = \ frac {7} {8} \ cdot 3 + \ frac {1} {8} \ cdot (3 + m) [/ matemáticas], es decir, [matemáticas] m = \ frac {24} {7} \ aprox 3.42 [/ matemáticas].

Hay un total de [matemática] 6 ^ k [/ matemática] de resultados igualmente probables después de tiros de [matemática] k [/ matemática], y no divide [matemática] 7 [/ matemática]. Por lo tanto, no hay posibilidad de resolver este problema en un número determinista de pasos.

Después de dos lanzamientos hay [matemáticas] 36 [/ matemáticas] posibles resultados. Si se excluye un resultado, será divisible por [matemáticas] 7 [/ matemáticas].

Por lo tanto, podemos dividir estos 35 resultados en 7 grupos de alguna manera, no importa cómo. Pero si después de dos lanzamientos tenemos mala suerte y obtenemos un resultado no admisible, tenemos que comenzar de nuevo.

Este método es ligeramente mejor en términos del número promedio de lanzamientos [matemática] s [/ matemática]. En este caso [matemática] s = \ frac {72} {35} \ aprox 2.06 [/ matemática].

¿Podemos hacerlo mejor sin hacer trampa? Creo que no, ya que no es posible determinar para ningún resultado a cuál de los 7 grupos pertenece sin un segundo lanzamiento.

Answer 4

Muchas soluciones posibles. Tiraría los dados tres veces y solo registraría si el número de puntos era par o impar. Esto esencialmente da un solo bit por cada lanzamiento, es decir, un total de tres bits. Interprete estos tres bits como un número binario en el intervalo 0 – 7. Si los tres bits son cero, simplemente comience de nuevo.

Answer 5

Para obtener las mismas probabilidades, debe utilizar una estrategia en la que descarte algunas opciones. Puedes ver esto al notar que tirar un dado de seis lados n veces tiene 6 ^ n combinaciones diferentes. Ahora 7 no divide 6 ^ n para ninguna n, por lo que las probabilidades no pueden ser exactas.

La solución de Michael Jørgensen es bastante agradable y simple de implementar.

Otra forma de hacerlo es tirar dos dados usando la siguiente tabla

. El | 1 2 3 4 5 6
—————
1 | 1 1 1 1 1 2
2 | 2 2 2 2 3 3
3 | 3 3 3 4 4 4
4 | 4 4 5 5 5 5
5 | 5 6 6 6 6 6
6 | 7 7 7 7 7 X

con la X siendo un re-roll. Necesita 5 de cada número como 7 * 5 = 35 uno menos que el número total de las combinaciones.

También puedes hacerlo tomando la suma de dos dados mod 7

. El | 1 2 3 4 5 6
———————
1 | 2 3 4 5 6 7
2 | 3 4 5 6 7 1
3 | 4 5 6 7 1 2
4 | 5 6 7 1 2 3
5 | 6 7 1 2 3 4
6 | X 1 2 3 4 5

Tenga en cuenta que hay 5 de cada número. Para los sietes, debe asegurarse de que solo haya 5 formas en que esto ocurra. Por lo tanto, debe volver a tirar si saca un seis seguido de un 1.

Answer 6

Tira los dados dos veces y registra los dos lanzamientos donde el orden importa, es decir, 3-4 y 4-3 son diferentes. Esto te dará 36 posibilidades. Desecha el último, así que si obtienes 6-6 vuelves a tirar. Ahora tiene 35. Haga una lista de los 35 y agrúpelos en cinco, y asigne a cada grupo un número entre 1 y 7. Esto debería generar un número aleatorio entre 1 y 7.

Answer 7

Aquí hay un algoritmo que funciona, aunque no pueda implementarlo en la vida real.

• Tira el dado un número infinito de veces, anotando los números que obtienes. (Suponga que los números a los lados del dado son 0-5.) Agregue 0. al principio y, leyendo en base-6 , obtendrá un número x como 0.10234105512310 … Acaba de generar un número aleatorio uniforme en el intervalo [0, 1].
• Si x está en el intervalo (0, 1/7), devuelve 1, si x está en (1/7, 2/7), devuelve 2, y así sucesivamente. (La probabilidad de que x sea ​​un número “límite” como 0 o 1/7 es insignificante).

Bien, bueno, no podemos hacer esto en la vida real, porque no tenemos una cantidad infinita de tiempo. Entonces, ¿cómo podemos obtener un algoritmo que funcione en la vida real?

Bueno, podemos ejecutar el procedimiento anterior, pero detenerse tan pronto como haya generado suficientes dígitos para determinar en qué intervalo va a aterrizar.

Por ejemplo, si los primeros dos lanzamientos producen 0, sé que el resultado final estará en el intervalo (0.00, 0.0055555555 …) = (0, 0.01) = (0, 1/36). Tenga en cuenta que esto es todo base 6. El intervalo (0, 1/36) está completamente contenido en (0, 1/7) para que podamos detenernos aquí sin generar todos nuestros dígitos.

Lo dejaré como un ejercicio para el lector para demostrar que el número esperado de tiradas de dados es finito en la expectativa. (Soy flojo, o lo que sea)

Answer 8

EDITAR: publicado originalmente como respuesta a una pregunta ligeramente diferente.

Si. Si genera dos números aleatorios con el primer generador, hay 36 combinaciones posibles (tenga en cuenta que [1,3] y [3,1] se consideran diferentes).

Asigne cinco de esas combinaciones a 1, otras cinco a 2, y así sucesivamente. Utiliza 35 combinaciones y te deja con una, que simplemente ignoras.

Answer 9

Bajar
1. Tira los dados dos veces. Grabarlos.
2. Si ambos resultados son 6s, vuelva a pasar y regrese al paso 1
3. Si el primer resultado no es 6 pero el segundo resultado es 6, has generado “7”
4. De lo contrario, tome el número en su primer rollo. Ese es el número que has generado.

Answer 10

Tira los dados una vez. Obtienes 1 bit de información. Como se muestra a continuación en BlackboxFunc. Llama a la función 3 veces. Esto generará la serie 000,001… ..111

Si obtienes 000, vuelve a ejecutar el experimento, de lo contrario tienes una respuesta.

BlackboxFunc () {

Genera un número aleatorio r

si r en {1,2,3} devuelve 0;

más

volver 1

}

Answer 11

Seguro. Tira el dado dos veces. Si sacas el mismo número dos veces, es un siete, de lo contrario toma el primer número rodado como tu valor. Si rodó los ojos de serpiente, vuelva a tirar los dados e intente nuevamente.

Answer 12

Genere dos números aleatorios entre 1 y 6. Esto da 36 posibilidades. Cada uno de estos 36 es igualmente probable. 5 de estas posibilidades significarían 1, las siguientes cinco significarían 2, y así sucesivamente. Habríamos agotado 35 de estas posibilidades. Al obtener la 36ª posibilidad, seguimos el proceso nuevamente.

Answer 13

Rodar dos veces.
Si el primero no es 6, entonces X = el segundo resultado.
Si el primero es 6, pero el segundo no, entonces X = 7
Si es doble 6, rodar nuevamente.
Todo evento {1, …, 7} tiene 5/36 (condicionado, no es doble 6), por lo que será uniforme.

Esto es simple, fácil de recordar (y fue fácil de descubrir, me llevó 3 minutos), fácil de implementar, pero, por supuesto, muy lejos de ser óptimo.

Necesita en promedio 2.05 rollos / por número generado, (2 * 36/35),
y el mínimo teórico debería ser log (7) / log (6) = 1.08.

Además, no hay límite superior garantizado para el número de rollos …

Answer 14

Esta no es una solución perfecta; pero bueno, funciona y es realmente fácil, tanto conceptual como fácil de implementar en la vida real.

Haga una pequeña competencia donde 1-7 sean todos concursantes, si el concursante obtiene un 6 en el dado, continúa en la competencia. Cuando todos los concursantes hayan tirado el dado una vez, la primera ronda habrá terminado. Todos los concursantes que han recibido un 6 pasan a la siguiente ronda. Repita hasta que solo quede un concursante. Este es su número generado uniformemente.

---

Tenga en cuenta que: el uso de una moneda también funcionaría, pero en este algoritmo un dado es realmente más rápido, ya que el número de concursantes está más cerca del número de lados en el dado que en la moneda.

Answer 15

r (7) = r (r (6) + r (6), {x: x> 7})

dónde,

r (n) = resultado del dado con cara n

r (n, S) = resultado después de ignorar los resultados en S y volver a intentar

por ejemplo, r (x-1) es equivalente a r (x, {x})

S = conjunto de resultados a suprimir.

Answer 16

* Editado más adelante *

Las soluciones de Rajesh Durgapal y Richard Morris son mucho más eficientes.

* Editado *

Para un lanzamiento, llame al resultado 1 o 2 como A, 3 o 4 como B, 5 o 6 como C.

Entonces la probabilidad de A, B y C es 1/3 cada uno.

Tira el dado dos veces.

Un resultado es un par de resultados, el resultado en el primer lanzamiento y el segundo.

(A, A)

(A, B)

etc.

Asignar (A, A) -> 1 (probabilidad del resultado = 1/9)

(A, B) -> 2 (probabilidad del resultado = 1/9)

(A, C) -> 3

(B, A) -> 4

.

.

(C, A) -> 7 (probabilidad del resultado = 1/9)

Cualquier otro par lo tira a la basura.

Ahora, tiene un generador de números aleatorios distribuido uniformemente sobre {1, 2, …, 7}

Entonces, la forma de hacerlo es:

• Comience con Lanzar 1:
• Tenga en cuenta el resultado que obtiene. Es A, B o C
• Lanzamiento 2:
• Si tuvo A o B en el tiro 1, baje el par y vaya al tiro 1.
• Si tuvo C en el tiro 1 y obtiene B o C en el tiro 2, repita el tiro 2. Si obtiene A en el tiro 2, baje el par y vaya al tiro 1.

Answer 17

Tira los dados 7 veces, suma los números y toma el mod 7 de la suma.