What is the most efficient way to simulate a 7-sided die with a 6-sided die? I've put some thought into it but I'm not sure I get somewhere specifically.
To create a 7-sided die we can use a rejection technique. 3-bits give uniform 1-8 and we need uniform 1-7 which means that we have to reject 1/8 i.e. 12.5% rejection probability.
To create $n * 7$-sided die rolls we need $\lceil log_2( 7^n ) \rceil$ bits. This means that our rejection probability is $p_r(n)=1-\frac{7^n}{2^{\lceil log_2( 7^n ) \rceil}}$.
It turns out that the rejection probability varies wildly but for $n=26$ we get $p_r(26) = 1 – \frac{7^{26}}{2^{\lceil log_2(7^{26}) \rceil}} = 1-\frac{7^{26}}{2^{73}} \approx 0.6\%$ rejection probability which is quite good. This means that we can generate with good odds 26 7-die rolls out of 73 bits.
Similarly, if we throw a fair die $n$ times we get number from $0…(6^n-1)$ which gives us $\lfloor log_2(6^{n}) \rfloor$ bits by rejecting everything which is above $2^{\lfloor log_2(6^{n}) \rfloor}$. Consequently the rejection probability is $p_r(n)=1-\frac{2^{\lfloor log_2( 6^{n} ) \rfloor}}{6^n}$.
Again this varies wildly but for $n = 53$, we get $p_r(53) = 1-\frac{2^{137}}{6^{53}} \approx 0.2\%$ which is excellent. As a result, we can roll the 6-face die 53 times and get ~137 bits.
This means that we get about $\frac{137}{53} * \frac{26}{73} = 0.9207$ 7-face die rolls out of 6-face die rolls which is close to the optimum $\frac{log 7}{log6} = 0.9208$.
Is there a way to get the optimum? Is there an way to find those $n$ numbers as above that minimize errors? Is there relevant theory I could have a look at?
P.S. Relevant python expressions:
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 Thanks to @Erick Wong for helping me get the question right with his great comments.
Related question: Is there a way to simulate any $n$-sided die using a fixed set of die types for all $n$?
Best Answer
Roll the D6 twice. Order the pairs $(1,1), (1,2), \ldots, (6,5)$ and associate them with the set $\{1,2,\ldots,35\}$. If one of these pairs is rolled, take the associated single value and reduce it mod $7$. So far you have a uniform distribution on $1$ through $7$.
If the pair $(6,6)$ is rolled, you are required to start over. This procedure will probabilistically end at some point. Since it has a $\frac{35}{36}$ chance of not requiring a repeat, the expected number of repeats is only $\frac{36}{35}$. More specifically, the number of iterations of this 2-dice-toss process has a geometric distribution with $p=\frac{35}{36}$. So $P(\mbox{requires $n$ iterations})=\frac{35}{36}\left(\frac{1}{36}\right)^{n-1}$
Counting by die rolls instead of iterations, with this method, $$\{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\}$$
The method that uses base-6 representations of real numbers (@Erick Wong's answer) has $$\{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\}$$
Put another way, let $Q(n)=P(\mbox{at most $n$ die rolls are needed using this method})$ and $R(n)=P(\mbox{at most $n$ die rolls are needed using the base-6 method})$. Then we sum the above term by term, and for ease of comparison, I'll use common denominators:
$$\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}$$
So on every other $n$, the base-6 method ties with this method, and otherwise this method is "winning".
EDIT Ah, I first understood the question to be about simulating one D7 roll with $n$ D6 rolls, and minimizing $n$. Now I understand that the problem is about simulating $m$ D7 rolls with $n$ D6 rolls, and minimizing $n$.
So alter this by keeping track of "wasted" random information. Here is the recursion in words. I am sure that it could be coded quite compactly in perl:
Going into the first roll, we will have $6$ uniformly distributed outcomes (and so not enough to choose from $\{1,...,7\}$.) This is the initial condition for the recursion.
Generally, going into the $k$th roll, we have some number $t$ of uniformly distributed outcomes to consider. Partition $\{1,\ldots,t\}$ into $$\{1,\ldots,7; 8,\ldots,14;\ldots,7a;7a+1,\ldots,t\}$$ where $a=t\operatorname{div}7$. Agree that if the outcome from the $k$th roll puts us in $\{1,\ldots,7a\}$, we will consider the result mod $7$ to be a D7 roll result. If the $k$th roll puts us in the last portion of the partition, we must re-roll.
Now, either
we succeeded with finding a D7 roll. Which portion of the partition were we in? We could have uniformly been in the 1st, 2nd, ..., or $a$th. The next roll therefore will give us $6a$ options to consider, and the recursion repeats.
we did not find another D7 roll. So our value was among $7a+1, \ldots, t$, which is at most $6$ options. However many options it is, call it $b$ for now ($b=t\operatorname{mod}7$). Going into the next roll, we will have $6b$ options to consider, and the recursion repeats.