I recently wanted to randomly select among 12 choices, but didn’t have a 12-sided die handy. However, I did have two six-sided dice, which makes it easy to simulate rolling a single 12-sided die via this algorithm (\(d_{6_n}\) represents the rolled value of the \(n\)th six-sided die):
\[ d_{6_1} * \begin{cases} 2 &\text{if } d_{6_2} \leq 3 \\ 1 &\text{otherwise} \end{cases} \]
In fact, as long as you have a single fair die of any denomination (or even a single coin to flip), you can simulate any other! First, roll the die or toss the coin. Condense that information to one bit somehow. Because common dice (\(d_6\), \(d_8\), \(d_{10}\), \(d_{12}\), \(d_{20}\)) have an even number of sides, you can just use whether the rolled number is even or odd. If you had an odd-sided die somehow, just re-roll if you get the largest number. Then, collect enough bits to cover the space of possibilities. If your final result is too large, just repeat the procedure.
In pseudocode:
\[ \begin{aligned} & simroll \larr \infty \\ & \text{while } simroll > n \: \{ \\ & \quad bits \larr [] \\ & \quad \text{while}\:\text{length}(bits) < \lceil log_2(n) \rceil \: \{ \\ & \quad \quad roll \larr d_6 \\ & \quad \quad bit \larr \begin{cases} 1 &\text{if } roll \text{ odd} \\ 0 &\text{if } roll \text{ even} & \end{cases} \\ & \quad \quad bits \larr \text{append}(bit, bits) \\ & \quad \} \\ & \quad simroll \larr \sum_{i=0}^{\text{length}(bits)} 2^i \times bits_i + 1 \\ & \} \\ & \text{return } simroll \end{aligned} \]
Or in actual code, assuming d6 :: IO Int. By defining
e.g. d13 = dN 13 and looking at the set of possible values
of d13, we can see that we eventually get every number in
the range, and none outside the range (but proving uniformity is
harder).
dN :: Int -> IO Int
dN n = do
bits <- replicateM (numBits n) getBit
if bitsToInt bits < n
then pure $ bitsToInt bits + 1
else dN n -- try again
where
getBit = even <$> d6
numBits = ceiling . logBase 2.0 . fromIntegral
bitsToInt = foldr combine 0
combine bit rest =
2 * rest +
if bit then 1 else 0For the sake of clarity, let’s try an example: simulating a \(d_{12}\) with a single \(d_6\). Because \(\lceil \log_2(12) \rceil = 4\), we have to
come up with four bits. Roll the \(d_6\) four times, and note whether each
number is odd or even. Let’s say we get 1110, which is 14
in decimal. That’s already too big, so let’s re-roll four more times.
1010, which is 10. Add 1 to adjust the range to be from 1
to 12 rather than 0 to 11, and our final result for this roll is 11.
However, it took eight rolls to get the same result we already know we can get with just two! We’re certainly doing a lot of extra work. This algorithm’s runtime is \(\mathcal{O}(\infty)\), meaning that in the worst case it could run forever with no result (which would be supremely unlucky, and mean re-rolling forever). Even in the best case, we’re doing at least twice as many rolls as we need to. Just because we can correctly simulate any die this way, doesn’t mean it’s the best way to do so.
Our two-roll \(d_6\) simulating \(d_{12}\) algorithm runs in constant time—\(\mathcal{O}(1)\). There are a bunch of other constant-time die simulations. Let’s run through what we can simulate with a \(d_6\).
We can simulate a \(d_2\) with a \(d_6\) in one roll—even or odd? A \(d_3\) also takes one roll—just take your roll \(\text{mod } 3\). Four doesn’t divide evenly into six, so we can’t group all the rolls like we did for \(d_2\) and \(d_3\). We could re-roll if we see a five or six, but then we’re back to an \(\mathcal{O}(\infty)\) runtime. Practically, this won’t matter too much, but it still could be a dozen rolls before getting something between one and four. Luckily though, four is a power of two, so we can go back to treating rolls as bits. We need two bits, so two rolls, and we’ll never have to do any more than that (since we never have to throw away extra information and start over).
Five is unluckier still. It doesn’t divide 6 evenly. It’s not a power of two, so we can’t use the rolls-as-bits strategy without having to throw out extra bits. It’s not a power of anything else either (e.g. we can simulate a \(d_9\) with two ternary “bits”). How can we get a constant number of rolls, guaranteed to give us a result without further re-rolling?
It’s actually not possible. The last digit of some power of 6 is always a 6. We can set things up to roll a huge constant number of times, but we’ll always have one pesky scenario where a re-roll is necessary, because five won’t cleanly divide in. (Note that four divides evenly into \(6^2 = 36\), which is why that worked.) For practical purposes, though, the number of rolls should remain small. Rolling a six ten times in a row on a fair die happens something like 1 in 60 million times. Rolling sixes in a row much longer than that would definitely cause me to suspect the die, rather than worry more about the asymptotic behavior of my simulation algorithm.