Simular tiradas repetidas de un dado de 7 caras con un dado de 6 caras

Question

¿Cuál es la forma más eficaz de simular un dado de 7 caras con un dado de 6 caras? He pensado un poco en ello pero no estoy seguro de llegar a algún sitio en concreto.

Para crear un dado de 7 caras podemos utilizar una técnica de rechazo. Los 3 bits dan un uniforme 1-8 y nosotros necesitamos un uniforme 1-7, lo que significa que tenemos que rechazar 1/8, es decir, un 12,5% de probabilidad de rechazo.

Para crear $n * 7$ -sus tiradas de dados son necesarias $\lceil log_2( 7^n ) \rceil$ bits. Esto significa que nuestra probabilidad de rechazo es $p_r(n)=1-\frac{7^n}{2^{\lceil log_2( 7^n ) \rceil}}$ .

Resulta que la probabilidad de rechazo varía mucho pero para $n=26$ obtenemos $p_r(26) = 1 - \frac{7^{26}}{2^{\lceil log_2(7^{26}) \rceil}} = 1-\frac{7^{26}}{2^{73}} \approx 0.6\%$ probabilidad de rechazo que es bastante buena. Esto significa que podemos generar con buenas probabilidades 26 tiradas de 7 dados de 73 bits.

Del mismo modo, si lanzamos un dado justo $n$ veces obtenemos el número de $0...(6^n-1)$ que nos da $\lfloor log_2(6^{n}) \rfloor$ bits rechazando todo lo que está por encima $2^{\lfloor log_2(6^{n}) \rfloor}$ . En consecuencia, la probabilidad de rechazo es $p_r(n)=1-\frac{2^{\lfloor log_2( 6^{n} ) \rfloor}}{6^n}$ .

De nuevo, esto varía mucho, pero para $n = 53$ obtenemos $p_r(53) = 1-\frac{2^{137}}{6^{53}} \approx 0.2\%$ que es excelente. Como resultado, podemos lanzar el dado de 6 caras 53 veces y obtener ~137 bits.

Esto significa que obtenemos alrededor de $\frac{137}{53} * \frac{26}{73} = 0.9207$ El dado de 7 caras sale de las tiradas de 6 caras, lo que se aproxima al óptimo $\frac{log 7}{log6} = 0.9208$ .

¿Hay alguna manera de conseguir lo óptimo? ¿Existe una manera de encontrar esos $n$ números como los anteriores que minimizan los errores? ¿Hay alguna teoría relevante a la que pueda echar un vistazo?

P.D. Expresiones relevantes de python:

min([ (i, round(1000*(1-(  7**i )  /  (2**ceil(log(7**i,2)))) )/10)  for i in xrange(1,100)], key=lambda x: x[1])
min([ (i, round(1000*(1- ((2**floor(log(6**i,2))) / (  6**i ))   )    )/10)  for i in xrange(1,100)], key=lambda x: x[1])

P.S.2 Gracias a @Erick Wong por ayudarme a acertar la pregunta con sus estupendos comentarios.

Pregunta relacionada: ¿Existe una forma de simular cualquier $n$ -de la cara utilizando un conjunto fijo de tipos de troquel para todos $n$ ?

Answer 1

Tira el D6 dos veces. Ordena las parejas $(1,1), (1,2), \ldots, (6,5)$ y asociarlos con el conjunto $\{1,2,\ldots,35\}$ . Si sale uno de estos pares, se toma el valor individual asociado y se reduce mod $7$ . Hasta ahora se tiene una distribución uniforme en $1$ a través de $7$ .

Si la pareja $(6,6)$ se rueda, se requiere empezar de nuevo. Es probable que este procedimiento termine en algún momento. Dado que tiene un $\frac{35}{36}$ probabilidad de no requerir una repetición, el número esperado de repeticiones es sólo $\frac{36}{35}$ . Más concretamente, el número de iteraciones de este proceso de 2 dados tiene una distribución geométrica con $p=\frac{35}{36}$ . Así que $P(\mbox{requires $ n $ iterations})=\frac{35}{36}\left(\frac{1}{36}\right)^{n-1}$

---

Contar por tiradas en lugar de iteraciones, con este método, $$\{P(\mbox{exactly $ n $ die rolls are needed})\}_{n=1,2,3,\ldots}=\left\{0,\frac{35}{36},0,\frac{35}{36}\left(\frac{1}{36}\right),0,\frac{35}{36}\left(\frac{1}{36}\right)^{2},0,\frac{35}{36}\left(\frac{1}{36}\right)^{3},\ldots\right\}$$

El método que utiliza representaciones de base 6 de los números reales (la respuesta de @Erick Wong) tiene $$\{P(\mbox{exactly $ n $ die rolls are needed})\}_{n=1,2,3,\ldots}=\left\{0,\frac{5}{6},\frac{5}{6}\left(\frac{1}{6}\right),\frac{5}{6}\left(\frac{1}{6}\right)^{2},\frac{5}{6}\left(\frac{1}{6}\right)^{3},\frac{5}{6}\left(\frac{1}{6}\right)^{4},\ldots\right\}$$

Dicho de otro modo, dejemos que $Q(n)=P(\mbox{at most $ n $ die rolls are needed using this method})$ y $R(n)=P(\mbox{at most $ n $ die rolls are needed using the base-6 method})$ . A continuación, sumamos lo anterior término a término, y para facilitar la comparación, utilizaré denominadores comunes:

$$\begin{align} \{Q(n)\}_{n=1,2,\ldots} &= \left\{0,\frac{45360}{36^3},\frac{45360}{36^3},\frac{46620}{36^3},\frac{46620}{36^3},\frac{46655}{36^3},\frac{46655}{36^3},\ldots\right\}\\ \{R(n)\}_{n=1,2,\ldots} &= \left\{0,\frac{38880}{36^3},\frac{45360}{36^3},\frac{46440}{36^3},\frac{46620}{36^3},\frac{46650}{36^3},\frac{46655}{36^3},\ldots\right\}\\ \end{align}$$

Así que en cualquier otro $n$ El método de base-6 empata con este método, y por lo demás este método está "ganando".

---

EDIT Ah, primero entendí que la pregunta era sobre la simulación de un Tirada de D7 con $n$ tiradas D6, y minimizando $n$ . Ahora entiendo que el problema está en simular $m$ Las tiradas de D7 con $n$ tiradas D6, y minimizando $n$ .

Así que altera esto llevando la cuenta de la información aleatoria "desperdiciada". Aquí está la recursión en palabras. Estoy seguro de que se podría codificar de forma bastante compacta en perl:

Entrando en la primera tirada, tendremos $6$ resultados uniformemente distribuidos (y por lo tanto no hay suficiente para elegir $\{1,...,7\}$ .) Esta es la condición inicial de la recursión.

Por lo general, al entrar en el $k$ de la tirada, tenemos algún número $t$ de resultados uniformemente distribuidos a considerar. Partición $\{1,\ldots,t\}$ en $$\{1,\ldots,7; 8,\ldots,14;\ldots,7a;7a+1,\ldots,t\}$$ donde $a=t\operatorname{div}7$ . Acuerda que si el resultado de la $k$ El rollo nos pone en $\{1,\ldots,7a\}$ , consideraremos el resultado mod $7$ para ser un resultado de la tirada D7. Si el $k$ Esta tirada nos pone en la última parte de la partición, debemos volver a tirar.

Ahora, o bien

• hemos tenido éxito con la búsqueda de un rollo D7. ¿En qué parte de la partición estábamos? Podríamos haber estado uniformemente en la 1ª, 2ª, ..., o $a$ th. Por lo tanto, la siguiente tirada nos dará $6a$ opciones a considerar, y la recursión se repite.

• no encontramos otro rollo D7. Así que nuestro valor estaba entre $7a+1, \ldots, t$ que es como máximo $6$ opciones. Por muchas opciones que sean, llámese $b$ por ahora ( $b=t\operatorname{mod}7$ ). Al entrar en la siguiente tirada, tendremos $6b$ opciones a considerar, y la recursión se repite.

Answer 2

A la larga, basta con omitir la conversión binaria y optar por alguna forma de codificación aritmética: utilizar el $6$ - tiradas de dados para generar una base uniforme $6$ número real en $[0,1]$ y luego extraer la base- $7$ dígitos de eso a medida que se resuelven. Por ejemplo:

int rand7()
{
  static double a=0, width=7;  // persistent state

  while ((int)(a+width) != (int)a)
  {
    width /= 6;
    a += (rand6()-1)*width;
  }

  int n = (int)a;
  a -= n; 
  a *= 7; width *= 7;
  return (n+1);
}

Una prueba de $10000$ salidas suele requerir exactamente $10861$ tiradas de dados, y ocasionalmente necesita una o dos más. Nótese que la uniformidad de esta implementación no es exacta (aunque rand6 es perfecto) debido al truncamiento en coma flotante, pero debería ser bastante bueno en general.

Answer 3

Una variación de las respuestas de @steveverrill y @alex.jordan. Tira dos D6:

        Die 1
     1 2 3 4 5 6
     ===========
   1|1 2 3 4 5 6
 D 2|1 2 3 4 5 6
 i 3|1 2 3 4 5 6
 e 4|1 2 3 4 5 6
 2 5|1 2 3 4 5 6
   6|7 7 7 7 7 X

Aplica las siguientes reglas:

• Regla 1: Si el dado 2 no es un 6, mantén el resultado del dado 1.
• Regla 2: Si el dado 2 es un 6, pero el dado 1 no es un 6, trata el resultado como un 7.
• Regla 3: Si tanto el dado 1 como el 2 son 6, vuelve a tirar.

Como se menciona en los comentarios, la probabilidad de acertar 1,2,3,4,5,6 o 7 parece ser $\frac{5}{35} = \frac{1}{7}$ . Teniendo en cuenta la repetición de la tirada, la probabilidad es superior a $\frac{5}{36}$ . En realidad es una serie infinita que converge a $\frac{1}{7}$ :

$$\sum_{i=1}^n \frac{5}{36^i} = \frac{5}{36} + \frac{5}{36^2} + \frac{5}{36^3} + ... = \frac{1}{7}$$

Answer 4

Corta el campo donde vas a lanzar el dado en siete regiones simétricas. Lanza el dado, ignora qué número surge y mira dónde ha caído. Vuelve a lanzarlo si cae en el borde. La mayoría de las veces sólo tendrás que lanzar una vez :)

Answer 5

Yo utilizaría el siguiente algoritmo de Las Vegas. El "%7" de abajo significa "el resto de la división con 7".

int roll_dice7()
{
    a0 = roll_dice6();
    a1 = roll_dice6();
    a = 6*(a1-1) + (a0-1) + 1;
    if (a > 35) {
        return roll_dice7();
    } else {
        return (a-1)%7+1;
    }
}