A method for simplifying manual random number generation? [closed]

Question

Is there a good way to take a more complicated dice-rolling mechanism and create a simpler dice-rolling mechanism that gives roughly similar results?

Example 1: Say you have a game where both sides roll a number of 6-sided dice (each side rolling a possibly different number of dice) looking for 6s. Unfortunately, other rules of the game frequently cause the number of dice rolled to be excessive (say, 40-60 or 80). The assorted statistics of the resulting distribution is fairly easy to calculate, but is there a way to use that to create a simpler mechanism (using, say, not more than 10 dice) that produces approximately the same results?

Example 2: Say you have a game where $n$ 6-sided dice are rolled looking for values greater than $x$, to identify possible successes. These successes are then verified by rolling 1 die per possible success looking for a value greater than $y$. ($n, x,$ and $y$ are parameters of the mechanism.) Is there a way to create a mechanism that produces approximately the same results with only one step?

Answer 1

This is an interesting question from a simulation viewpoint as most simulation algorithms require the call to a uniform $\mathcal U(0,1)$ pseudo-random generator.

If $X_i$ is the number of 6's out of $n_i$ rolls, $$X_i\sim\mathcal Bin(n_i,1/6)\,,$$that is, $$\mathbb P(X_i=k) = {k \choose n_i} \dfrac{5^{n_i-k}}{6^{n_i}}\,.$$ Using a dice random generator over $\{1,\ldots,6\}$ rather than a Uniform generator to generate this distribution could proceed by

0. the unbiased estimator method: Find a joint distribution on $(X,Y)$ such that there exists a transform $H(x,y)$ such that $H(x,Y)$ is an unbiased estimator of $\mathbb P(X_i=x)$ and accept draws with probability $H(X,Y)$. Drawback: it is unclear such an unbiased estimator is available at a cost lower than $\mathsf O(n_i)$. Or is it $\mathsf O(\log_6~n_i)$ ?

1. the naïve method: Generate from the dice iid draws $Y_1,Y_2,\ldots,Y_{n_i}\in\{1,\ldots,6\}$ and count how many are equal to $6$. Drawback: this requires $n_i$ draws.

2. the inversion method (p.85): Generate from the dice iid draws $Y_1,Y_2,\ldots\in\{1,\ldots,6\}$ until the cumulated probability of the outcome (using eg lexicographic order) fits between two consecutive values of the $\mathcal Bin(n_i,1/6)$ cdf. Drawback: this requires a random number of draws and is only approximate.

3. the accept-reject method: Select a distribution $\mathbb Q$ on $\{0,1,\ldots,n_i\}$ with probabilities $p_0,p_1,\ldots,p_{n_i}$, which can be generated in $\mathsf O( \log_6(n_i) )$ rolls from a 6-face dice, compute the maximum $$M = \max_k p_k \Big/ {k \choose n_i} \dfrac{5^{n_i-k}}{6^{n_i}}$$ and accept a draw $k$ from $\mathbb Q$ with probability $$p_k \Big/ M {k \choose n_i} \dfrac{5^{n_i-k}}{6^{n_i}}$$ Drawback: the acceptance step implies further draws to mimick a Uniform draw and $M$ may prove quite large. For instance, using a uniform $\mathbb Q$ leads to $$M = \max_k 1 \Big/ {k \choose n_i} 5^{n_i-k}$$

4. the pseudo-uniform method: Generate from the dice iid draws $Y_1,Y_2,\ldots\in\{1,\ldots,6\}$, minus one, taken as digits of a uniform $\mathcal U(01,)$ variate (in base 5), until the number $R$ of digits (in base 5) is large enough for the intended precision, set $$U=\sum_{i=1}^R 5^{-i-1}(Y_i-1)$$ and use a uniformly fast generator from Devroye, p.520 based on uniform generators. Drawback: this is not completely exact unless $R$ equates the real number representation on the local machine.

Answer 2

For example 1, as in Xi’an’s answer, you could use a 10 sided die 3 times to get the first 3 digits of a unif(0,1) rv. Then use inverse cdf. If the result is simply the number of 6’s out of 80 throws, this is approximately normal with mean 80/6 and variance 805/36. Find some other manual rv approximately normal and transform it. For example the number of 6’s out of 20 throws is approximately normal with mean 10/6 and variance 25/36. Call that X. Then, 80/6+sqrt(805/36) (X-10-6)/sqrt(25/36) has approximately the righ normal distribution.

For example 2, you may be able to do it in one step. Assume you start with 6 sided dice. Probability of success is $(6-x)(6-y)/36$. If this fraction can be written with a denominator equal to the number of sides of a die you have, then you can do it in one step. If you have a 36 sided die, you can always do it. I’ve never seen one, but it would be a trapezohedron similar to the 10 sided die. If not, you have to check for your specific situation. For example, $x=3$, $y=2$. The probability is $1/3$ which can be done with either 6 or 12 sided die. If you only have 6 sided die, you can do it if and only if one of the parameters is 3 and the other is 2 or 4.