¿Dibujar números enteros de forma independiente y uniforme al azar de 1 a$N$ usando fair d6?

Question

Quiero llamar números enteros de 1 a determinados $N$ a rodar por algún número de la feria de seis caras de los dados (d6). Una buena respuesta podría explicar por qué su método produce uniforme e independiente de los números enteros.

Como un ejemplo ilustrativo, sería útil para explicar cómo una solución que funciona para el caso de $N=150$.

Asimismo, deseo para que el procedimiento sea lo más eficiente posible: roll el menor número de d6, en promedio, para cada número generado.

Las conversiones de senary a decimal son permisibles.

---

Esta pregunta fue inspirado por esta Meta hilo.

Answer 1

El conjunto $\Omega(d,n)$ de distinta identificable resultados en $n$ independiente rollos de morir con $d=6$ caras ha $d^n$ elementos. Cuando el morir es justo, que significa cada uno de los resultados de un rollo ha probabilidad de $1/d$ e independencia significa cada uno de estos resultados por lo tanto, tienen probabilidad de $(1/d)^n:$ es decir, tienen una distribución uniforme $\mathbb{P}_{d,n}.$

Supongamos que se han ideado algunos de procedimiento $t$ determina que cualquiera de las $m$ resultados de una $c (=150)$colindado mueren, es decir, un elemento de $\Omega(c,m)$- o más informes de fallo (lo que significa que usted tendrá que repetir con el fin de obtener un resultado). Es decir,

$$t:\Omega(d,n)\to\Omega(c,m)\cup\{\text{Failure}\}.$$

Let $F$ be the probability $t$ results in failure and note that $F$ is some integral multiple of $d^{-n},$ say

$$F = \Pr(t(\omega)=\text{Failure}) = N_F\, d^{-n}.$$

(For future reference, note that the expected number of times $t$ must be invoked before not failing is $1/(1-F).$)

The requirement that these outcomes in $\Omega(c,m)$ be uniform and independent conditional on $t$ not reporting failure means that $t$ preserves probability in the sense that for every event $\mathcal{A}\subset\Omega(c,m),$

$$\frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) \tag{1}$$

where

$$t^{*}\left(\mathcal A\right) = \{\omega\in\Omega\mid t(\omega)\in\mathcal{A}\}$$

is the set of die rolls that the procedure $t$ assigns to the event $\mathcal A.$

Consider an atomic event $\mathcal A = \{\eta\}\subconjunto\Omega(c,m)$, which must have probability $c^{m}.$ Let $t^{*}\left(\mathcal A\right)$ (the dice rolls associated with $\eta$) have $N_\eta$ elements. $(1)$ becomes

$$\frac{N_\eta d^{-n}}{1 - N_F d^{-n}} = \frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) = c^{-m}.\tag{2}$$

It is immediate that the $N_\eta$ are all equal to some integer $N.$ It remains only to find the most efficient procedures $t.$ The expected number of non-failures per roll of the $c$ sided die is

$$\frac{1}{m}\left(1 - F\right).$$

There are two immediate and obvious implications. One is that if we can keep $F$ small as $m$ grows large, then the effect of reporting a failure is asymptotically zero. The other is that for any given $m$ (the number of rolls of the $c$-sided die to simulate), we want to make $F$ as small as possible.

Let's take a closer look at $(2)$ by clearing the denominators:

$$N c^m = d^n - N_F \gt 0.$$

This makes it obvious that in a given context (determined by $c,d,n,m$), $F$ is made as small as possible by making $d^n-N_F$ equal the largest multiple of $c^m$ that is less than or equal to $d^n.$ We may write this in terms of the greatest integer function (or "floor") $\lfloor*\rfloor$ as

$$N = \lfloor \frac{d^n}{c^m} \rfloor.$$

Finally, it is clear that $N$ ought to be as small as possible for highest efficiency, because it measures redundancy in $t$. Specifically, the expected number of rolls of the $d$-sided die needed to produce one roll of the $c$-sided die is

$$N \times \frac{n}{m} \times \frac{1}{1-F}.$$

Thus, our search for high-efficiency procedures ought to focus on the cases where $d^n$ is equal to, or just barely greater than, some power $c^m.$

The analysis ends by showing that for given $d$ and $c,$ there is a sequence of multiples $(n,m)$ for which this approach approximates perfect efficiency. This amounts to finding $(n,m)$ for which $d^n/c^m \ge 1$ approaches $N=1$ in the limit (automatically guaranteeing $F\a 0$). One such sequence is obtained by taking $n=1,2,3,\ldots$ and determining

$$m = \lfloor \frac{n\log d}{\log c} \rfloor.\tag{3}$$

The proof is straightforward.

This all means that when we are willing to roll the original $d$-sided die a sufficiently large number of times $n,$ we can expect to simulate nearly $\log d / \log c = \log_c d$ outcomes of a $c$colindado mueren por rollo. Equivalentemente,

Es posible simular un gran número de $m$ independiente de rollos de una $c$colindado muere el uso de una feria de $d$colindado mueren utilizando un promedio de $\log(c)/\log(d) + \epsilon = \log_d(c) + \epsilon$ rollos por resultado que $\epsilon$ puede hacerse arbitrariamente pequeña eligiendo $m$ lo suficientemente grande.

---

Ejemplos de algoritmos y

En la pregunta, $d=6$ e $c=150,$ dónde

$$\log_d(c) = \frac{\log(c)}{\log(d)} \approx 2.796489.$$

Thus, the best possible procedure will require, on average, at least $2.796489$ rolls of a d6 to simulate each d150 outcome.

The analysis shows how to do this. We don't need to resort to number theory to carry it out: we can just tabulate the powers $d^n=6^n$ and the powers $c^m=150^m$ and compare them to find where $c^m \le d^n$ are close. This brute force calculation gives $(n,m)$ pairs

$$(n,m) \in \{(3,1), (14,5), \ldots\}$$

for instance, corresponding to the numbers

$$(6^n, 150^m) \in \{(216,150), (78364164096,75937500000), \ldots\}.$$

In the first case $t$ would associate $216-150=66$ of the outcomes of three rolls of a d6 to Failure and the other $150$ outcomes would each be associated with a single outcome of a d150.

In the second case $t$ would associate $78364164096-75937500000$ of the outcomes of 14 rolls of a d6 to Failure -- about 3.1% of them all -- and otherwise would output a sequence of 5 outcomes of a d150.

A simple algorithm to implement $t$ labels the faces of the $d$-sided die with the numerals $0,1,\ldots d, d-1$ and the faces of the $c$-sided die with the numerals $0,1,\ldots, c-1.$ The $n$ rolls of the first die are interpreted as an $n$-digit number in base $d.$ This is converted to a number in base $c.$ If it has at most $m$ digits, the sequence of the last $m$ digits is the output. Otherwise, $t$ returns Failure by invoking itself recursively.

For much longer sequences, you can find suitable pairs $(n,m)$ by considering every other convergent $n/m$ of the continued fraction expansion of $x=\log(c)/\log(d).$ The theory of continued fractions shows that these convergents alternate between being less than $x$ and greater than it (assuming $x$ is not already rational). Choose those that are less than $x.$

In the question, the first few such convergents are

$$3, 14/5, 165/59, 797/285, 4301/1538, 89043/31841, 279235/99852, 29036139/10383070 \ldots.$$

In the last case, a sequence of 29,036,139 rolls of a d6 will produce a sequence of 10,383,070 rolls of a d150 with a failure rate less than $2\veces 10^{-8},$ for an efficiency of $2.79649$--indistinguibles desde el límite asintótico.

Answer 2

Para el caso de $N=150$, tirar un d6 tres veces claramente crea $6^3=216$ de los resultados.

El resultado deseado puede ser tabulados en esta forma:

• Grabar un d6 tres veces de forma secuencial. Esto produce resultados $a,b,c$. El resultado es uniforme ya que todos los valores de $a,b,c$ son igualmente probables (los dados son justos, y estamos tratando a cada rollo distinto).
• Resta 1 de cada.
• Este es un senary número: cada uno de los dígitos (valor posicional) va de 0 a 5 por potencias de 6, así que usted puede escribir el número en decimal usando $$(a-1) \times 6^2 + (b-1) \times 6^1 + (c-1)\times 6^0$$
• Añadir 1.
• Si el resultado excede de 150, descartar el resultado y se vuelve a tirar.

La probabilidad de mantener un resultado es $p=\frac{150}{216}=\frac{25}{36}$. Todos los rollos son independientes, y volvemos a repetir el procedimiento hasta que el "éxito" (un resultado en $1,2,\dots,150$) por lo que el número de intentos para generar 1 empate entre 1 y 150 se distribuye como una variable aleatoria geométrica, que tiene la expectativa $p^{-1}=\frac{36}{25}$. Por lo tanto, el uso de este método para generar 1 empate requiere de rodadura $\frac{36}{25}\times 3 =4.32$ rollos de dados en promedio (porque cada intento de rollos de 3 dados).

---

Crédito a @whuber para lo que sugiere que esta en el chat.

Answer 3

Aquí aún es una alternativa más simple a la respuesta por Sycorax para el caso de que $N=150$. Desde $150 = 5 \times 5 \times 6$ puede realizar el siguiente procedimiento:

La generación de uniforme número aleatorio de 1 a 150:

• Hacer tres ordenó rollos de 1D6 y denotan estas como $R_1, R_2, R_3$.
• Si cualquiera de los dos primeros rollos es un seis, rebollo hasta que no es 6.
• El número de $(R_1, R_2, R_3)$ es un número uniforme utilizando la notación posicional con una base de 5-5-6. Por lo tanto, usted puede calcular el número deseado como: $$X = 30 \cdot (R_1-1) + 6 \cdot (R_2-1) + (R_3-1) + 1.$$

Este método puede ser generalizado a mayor $N$, pero se vuelve un poco más difícil cuando el valor de uno o más factores primos de más de $6$.

Answer 4

Como una ilustración de un algoritmo para elegir de manera uniforme entre las $150$ valores de uso de seis caras de los dados, prueba esta que utiliza cada rollo de multiplicar los valores disponibles por $6$ y hacer que cada uno de los nuevos valores igualmente probables:

• Después de $0$ rollos, usted tiene $1$ posibilidad, no lo suficiente como para distinguir a $150$ valores
• Después de $1$ roll, ha $6$ posibilidades, no lo suficiente como para distinguir a $150$ valores
• Después de $2$ rollos, usted tiene $36$ posibilidades, no lo suficiente como para distinguir a $150$ valores
• Después de $3$ rollos, usted tiene $216$ posibilidades, lo suficiente como para distinguir a $150$ valores pero con $66$ restante de los valores; la probabilidad de parar ahora es $\frac{150}{216}$
• Si no se han detenido, a continuación, después de $4$ rollos ha $396$ restante posibilidades, lo suficiente como para distinguir a $150$ valores de dos maneras, pero con $96$ restante de los valores; la probabilidad de parar ahora es $\frac{300}{1296}$
• Si no se han detenido, a continuación, después de $5$ rollos ha $576$ restante posibilidades, lo suficiente como para distinguir a $150$ valores de tres maneras pero con $96$ restante de los valores; la probabilidad de parar ahora es $\frac{450}{7776}$
• Si no se han detenido, a continuación, después de $6$ rollos ha $756$ restante posibilidades, lo suficiente como para distinguir a $150$ valores de cinco maneras pero con $6$ restante de los valores; la probabilidad de parar ahora es $\frac{750}{46656}$

Si usted está en una de las $6$ restante de los valores después de la $6$ rollos entonces usted está en una situación similar a la de la posición después de la $1$ roll. Así que usted puede continuar de la misma manera: la probabilidad de dejar después de $7$ rollos es $\frac{0}{279936}$, después de $8$ rollos es $\frac{150}{1679616}$ etc.

Agregar estas arriba y te encuentras con que el número esperado de rollos necesarios es acerca de $3.39614$. Proporciona un uniforme de la selección de la $150$, ya que sólo seleccione un valor en un tiempo cuando usted puede seleccionar cada una de las $150$ , con igual probabilidad

---

Sycorax pedido en los comentarios de una forma más explícita algoritmo

• En primer lugar, voy a trabajar en base-$6$ con $150_{10}=410_6$
• Segundo, en vez de los valores de destino $1_6$ a $410_6$, voy a restar uno para los valores objetivo se $0_6$ a $409_6$
• En tercer lugar, cada morir debe tener los valores de $0_6$ a $5_6$, y el rodar de una matriz consiste en la adición de una base $6$ dígitos a la derecha de la actual número generado. Los números que se generan pueden tener ceros a la izquierda, y su número de dígitos es el número de rollos hasta ahora

El algoritmo se sucesivos dados:

• Rollo de la primera de tres dados para generar un número de $000_6$ a $555_6$. Desde $1000_6 \div 410_6 = 1_6 \text{ remainder } 150_6$ usted toma el valor generado (que también es su resto en la división por $410_6$) si el valor generado es estrictamente por debajo de $1000_6-150_6=410_6$ y parada;

• Si continua, rollo de la cuarta morir así que ahora ha generado un gran número de $4100_6$ a $5555_6$. Desde $10000_6 \div 410_6 = 12_6 \text{ remainder } 240_6$ tomar el resto del valor generado en la división por $410_6$ si el valor generado es estrictamente por debajo de $10000_6-240_6=5320_6$ y parada;

• Si continua, rollo de la quinta morir así que ahora ha generado un gran número de $53200_6$ a $55555_6$. Desde $100000_6 \div 410_6 = 123_6 \text{ remainder } 330_6$ tomar el resto del valor generado en la división por $410_6$ si el valor generado es estrictamente por debajo de $100000_6-330_6=55230_6$ y parada;

• Si continua, rollo de la sexta morir así que ahora ha generado un gran número de $552300_6$ a $555555_6$. Desde $1000000_6 \div 410_6 = 1235_6 \text{ remainder } 10_6$ tomar el resto del valor generado en la división por $410_6$ si el valor generado es estrictamente por debajo de $1000000_6-10_6=555550_6$ y parada;

• etc.