Simulate repeated rolls of a 7-sided die with a 6-sided die 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$?
 A: I would use the following Las Vegas algorithm.
The "%7" below means "the rest of the division with 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;
    }
}

A: Okay, here's a pretty good edit: really @#$%ing awesome algorithm! Like andre's, it uses only integer arithmetic. Like Erick Wong's, it achieves (nearly) the ideal entropy rate. There are three modifications to andre's algorithm:


*

*When taking the modulus of the current value, don't throw away the quotient. Instead, save the quotient to expedite the next request.

*If the current value is unusable, save it for the next request, considering it to be uniformly distributed over all unusable values.

*Hold as much entropy in reserve as you can, given the integer size. This is important so that the branch in the main loop is highly predictable, i.e. testing it doesn't extract much entropy from the reserve.


Here's some terse C-ish code:
unsigned Roll() {
    static unsigned rMod = 1, rValue = 0;
    while (true) {
        while (rMod < (unsigned)-1 / 6) {
            rValue = rValue * 6 + (unsigned)rand() % 6;
            rMod *= 6; }
        unsigned unused = rMod % 7;
        if (rValue < unused) rMod = unused;
        else {
            rValue -= unused; rMod -= unused;
            unsigned answer = rValue % 7;
            rValue /= 7; rMod /= 7;
            return answer; } } }

Here's the output:
0: 1428604207
1: 1428626732
2: 1428565440
3: 1428630701
4: 1428475676
5: 1428538428
6: 1428558816

die.InRollCount: 10860331523
die.OutRollCount: 10000000000

Die roll rate (lower is better):
Actual: 1.0860331523
Ideal:  1.086033132502

And the full C++ test program that generates the above output:
#include <iostream>
#include <cmath>
#include <random>

std::default_random_engine generator;

template<unsigned InMod, unsigned OutMod>
struct ConvertedDie
{
    ConvertedDie() :
        InRollCount(0),
        OutRollCount(0),
        _inDie(0, InMod - 1),
        _reserveMod(1),
        _reserveValue(0) { }

    unsigned Next()
    {
        ++OutRollCount;

        while (true)
        {
            // Roll the input die as many times as we can
            while (_reserveMod < std::numeric_limits<typeof(_reserveMod)>::max() / InMod)
            {
                ++InRollCount;

                _reserveValue = _reserveValue * InMod + _inDie(generator);
                _reserveMod *= InMod;
            }

            const unsigned unusableValues = _reserveMod % OutMod;

            // This comparison loses entropy,
            // which is minimized by making it fail almost always.
            if (_reserveValue < unusableValues)
            {
                _reserveMod = unusableValues;
            }
            else
            {
                _reserveValue -= unusableValues;
                _reserveMod -= unusableValues;

                const unsigned answer = _reserveValue % OutMod;

                _reserveValue /= OutMod;
                _reserveMod /= OutMod;

                return answer;
            }
        }
    }

    unsigned long InRollCount;
    unsigned long OutRollCount;

private:
    std::uniform_int_distribution<unsigned char> _inDie;
    unsigned _reserveMod;
    unsigned _reserveValue;
};

using namespace std;

int main()
{
    constexpr unsigned inMod = 6;
    constexpr unsigned outMod = 7;

    ConvertedDie<inMod, outMod> die;

    unsigned bins[outMod] = {};

    for (long i = 0; i < 10000000000; ++i)
    {
        ++bins[die.Next()];
    }

    for (int i = 0; i < outMod; ++i)
    {
        cout << i << ": " << bins[i] << endl;
    }

    cout << endl;
    cout << "die.InRollCount: " << die.InRollCount << endl;
    cout << "die.OutRollCount: " << die.OutRollCount << endl;

    cout.precision(log10(die.OutRollCount) + 1);
    cout << endl << "Die roll rate (lower is better):" << endl;
    cout << "Actual: " << (double)die.InRollCount / (double)die.OutRollCount << endl;

    cout.precision(log10(die.OutRollCount) + 3);
    cout << "Ideal:  " << log((double)outMod) / log((double)inMod) << endl;

    return 0;
}

A: If you want to keep as much entropy as you can, you can look at powers of 6 in base 7. For instance $6^{25} = 101620613015632362263436_7$ so you can extract 23 7-sided die rolls from 25 6-sided die rolls although you will have to re-roll about 4% of the time.
A: In the long run, just skip the binary conversion altogether and go with some form of arithmetic coding: use the $6$-dice rolls to generate a uniform base-$6$ real number in $[0,1]$ and then extract base-$7$ digits from that as they resolve.  For instance:
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);
}

A test run of $10000$ outputs usually requires exactly $10861$ dice rolls, and occasionally needs one or two more.  Note that the uniformity of this implementation is not exact (even if rand6 is perfect) due to floating-point truncation, but should be pretty good overall.
A: A variation on @steveverrill and @alex.jordan answers. Roll two D6s:
        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

Apply the following rules:


*

*Rule 1: If Die 2 isn't a 6, keep Die 1 as the result.

*Rule 2: If Die 2 is a 6, but Die 1 isn't a 6, treat the result as 7.

*Rule 3: If both Die 1 and Die 2 are 6s then reroll.


As mentioned in the comments, the probability of hitting 1,2,3,4,5,6 or 7 appears to be $\frac{5}{35} = \frac{1}{7}$. Taking into account of the reroll, the probability is more than $\frac{5}{36}$. It's actually an infinite series that converges to $\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}$$
A: Cut the field where you will throw the die into seven symmetric regions. Throw the die, ignore what number arises, and look to where it landed. Rethrow for border landings. Most of the time you'll only need to throw once :)
A: Another possibility is to use the die to generate a base 6 decimal (heximal?)  If you roll a 1, 2, 3, 4, 5, 6 respectively, write down 1, 2, 3, 4, 5, 0 respectively as the next digit to the right of heximal point.  For instance if your first two rolls were 6,2, then the first two digits of your heximal number would be $.02$.  After a while you would be able to identify your heximal as being in one of the intervals $(0,\frac17)$ or $(\frac17, \frac27)$,..., or $(\frac67,1)$.  At this point you could assign one of your desired 7 outcomes according to the numerator of the right endpoint of the interval you landed in.
A: I give this software answer here - which represents the process described in the question. It performs "poorly" in the sense of giving 0.9131 7-dice rolls per 6-dice roll BUT has the important property that its mathematics more or less make sense as described in the question. Other, way more efficient solutions like @Erick Wong's are excellent and generic which is brilliant - but I think they leave aspects of randomness to C's or machine's arbitrary characteristics like float truncation. Don't get me wrong - I'm ready to accept it since it is superior, but if possible I would like to see a bit of mathematics behind them. e.g. how it's guaranteed (?) that after a few million repeats it won't get stack-at 0 or it won't suddenly get severely degraded performance?
import random
from collections import defaultdict

class MetaDice:
    def __init__(self):
        self.bits = 0
        self.r = 0
        self.in_rejection_count = 0
        self.in_count = 0
        self.in_rounds = 0        
        self.out_rejection_count = 0
        self.out_count = 0

    def _get_more_6_dice(self):
        while True:
            self.in_rounds += 1
            t = 0
            for i in xrange(0,53):
                t *= 6
                t += random.randint(0,5)
                self.in_count += 1

            if t < 2**137:
                break

            self.in_rejection_count += 1

        self.r *= 2**137
        self.r += t
        self.bits += 137

    def _give_me_73_bits(self):
        if self.bits < 73:
            self._get_more_6_dice()

        self.bits -= 73
        t = self.r % (2**73)
        self.r /= (2**73)

        return t

    def give_me_26_7_dice(self):
        self.out_count += 1
        while True:
            inp = self._give_me_73_bits()
            if inp < 7**26:
                return inp

            self.out_rejection_count += 1

a = MetaDice()

hist = defaultdict(int)

for i in xrange(0, 100000):
    v = a.give_me_26_7_dice()
    for j in xrange(0,26):
        r = v % 7
        hist[r] +=1
        v /= 7

print hist

print "p_r in %3.2f%%" % (float(100 * a.in_rejection_count) / float(a.in_rounds))
print "p_r out %3.2f%%" % (float(100 * a.out_rejection_count) / float(a.out_count))
print "7-face die rolls out of 6-face die rolls: %3.4f" % (float(26 * a.out_count) / float(a.in_count))

output:
defaultdict(<type 'int'>, {0L: 370900, 1L: 372017, 2L: 371918, 3L: 371621, 4L: 371577, 5L: 370468, 6L: 371499})
p_r in 0.21%
p_r out 0.61%
7-face die rolls out of 6-face die rolls: 0.9131

A: A general algorithm
Rolls on a D6 with numbers from 0 through 5 is equivalent to the digits in a uniformly random real number in the range $[0;1]$ represented in base 6.
Rolls on a D7 with numbers from 0 through 6 is equivalent to the digits in a uniformly random real number in the range $[0;1]$ represented in base 7.
You can roll the D6 enough times to know what the first digit in base 7 to simulate the first D7. In order to simulate another D7 you roll the D6 enough times to know what the second digit in base 7 is.
This algorithm is optimal in terms of number of times you need to roll the D6. But the calculations you need to perform quickly blow up.
You can always throw away the entire state of the algorithm and start over. You lose some entropy, but the outputs will not get skewed.
Range coding/arithmetic coding
Instead of throwing away the entire state, it can be reduced through some clever rounding, which does not skew the output. And that is essentially what the arithmetic coding/range coding algorithms others have mentioned are doing.
Enumerating a small set of states
One possible variation is to enumerate a set of intermediate states and clearly define, what state is thrown away at each step. And algorithm with 21 intermediate states could work like this:
Rather than simply encoding the 21 possible intermediate states as an integer 1 to 21, it simplifies the algorithm to encode the intermediate state in 2 parts, a "current group" value from 1 to 6, and a "state within the group" value that ranges from 1 up to, at most, the current group value.
The intermediate state is in one of six groups of states, the probability distribution among the groups is not significant, all states within a group must have equal probability.
First group has 1 state, this is the starting state. Second group has 2 states, etc.
At each step you roll one D6, combined with the number of possible states in the current group, this produces from 6 to 36 possible outcomes. Each outcome is assigned a new state and whenever possible, a simulated D7.
In group 1 there is only 1 state, so there are 6 outcomes. A D7 can not be simulated. The 6 outcomes take us to the 6 possible states in group 6 with equal probability.
From group 2 there are 12 outcomes. 7 outcomes produce a simulated D7 and take us back to the starting state. 5 outcomes take us to group 5.
From group 3 there are 18 outcomes. 14 outcomes produce a simulated D7 and take us to a state in group 2. 4 outcomes take us to a state in group 4.
From group 4 there are 24 outcomes. 21 outcomes produce a simulated D7 and take us to a state in group 3. 3 outcomes take us to a state in group 3.
From group 5 there are 30 outcomes. 28 outcomes produce a simulated D7 and take us to a state in group 4. 2 outcomes take us to a state in group 2.
from group 6 there are 36 outcomes. 35 outcomes produce a simulated D7 and take us to a state in group 5. 1 outcome takes us back to the starting state.
A: As others have said, it's a good idea to roll again on a double six, to give you 35 possibilities instead of 36. The question then becomes how to assign the 35 possibilities to the 7 scores you require. The following formula is reasonably easy to calculate:
(7+Die1-Die2) mod 7
       Die 1
        1 2 3 4 5 6
        ===========
Die   1|0 1 2 3 4 5
2     2|6 0 1 2 3 4
      3|5 6 0 1 2 3
      4|4 5 6 0 1 2
      5|3 4 5 6 0 1
      6|2 3 4 5 6 X       X=roll again

As can be seen, each score from 0 to 6 appears in the table exactly 5 times.
In plain english, this becomes: "Roll the die twice. Subtract the second roll from the first (if this is not possible because it would give a negative number, add 7 to the value of the first roll before subtracting.) If you roll a double six, discard the score and roll again."
A: Let the first roll be $r1$ and the second be $r2$.  Re-roll on (6,6).  Otherwise, use the following formula to get the 7-sided result ($d7$):
$$d7 = ((r1*6 + r2) mod 7) + 1$$
When the number of rolls $n$ is even, this gives you a $1/36^{n/2}$ chance that you need to keep rolling.
A: Don't; use a d8 instead, rerolling 8's (or rolling 1d8-1 and rejecting 0).
No, this doesn't answer the precise question; yes it gives the same end result as a d7, so it depends on if the question was asked for practical or academic reasons.
