Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Why is $6/7$ the optimum? Wouldn't it be $\log 6/\log 7 \approx 0.92$? –  Erick Wong Aug 17 at 17:30
    
How can you extract $4$ independent random bits from every pair of dice rolls? The state space of two dice is $36$, which is not divisible by $2^3$, let alone $2^4$. –  Erick Wong Aug 17 at 17:40
    
Hello @ErickWong - that's exactly what I'm looking for - mistakes on my thinking. On the 36- I agree at first sight. What I believe is this. Roll 1: 001 000 011 010 101 100 roll 2: 001 000 011 010 101 100 Two independent uniform LSB's = 2 bits and then (n0[1] xor n1[1]) and (n0[2] xor n1[2]) should also be uniform. –  neverlastn Aug 17 at 18:00
    
About log6/log7≈0.92 - I'm not arguing, I'm sure it's correct - just as a reference - based on what? –  neverlastn Aug 17 at 18:24
1  
The $\log 6/\log 7$ number comes from comparing the number of bits produced by $m$ 6-sided dice rolls with the number of bits produced by $n$ 7-sided dice rolls. –  Erick Wong Aug 17 at 20:03

14 Answers 14

up vote 5 down vote accepted

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;
}
share|improve this answer
1  
The only think I would note is that (_reserveValue - answer) / OutMod == _reserveValue / OutMod. Apart from that this looks excellent. It "wastes" ~12 dice rolls with a probability < 0.000001% for 32-bit unsigned. I particularly love the way you save those little pieces of entropy here... _reserveMod = unusableValues. Would you be able to provide any references or relevant material? Does this technique have a name? –  neverlastn Aug 18 at 5:12
    
I'm not aware of a reference for this particular technique, since I just made it up, but I'd bet that a reference exists somewhere. I think the general class of algorithms is called "rejection sampling" or sometimes the "rejection method". –  Chris Culter Aug 18 at 7:23
1  
+1 This is quite nice. –  Erick Wong Aug 18 at 17:04
    
@neverlastn Oh, and thanks for the suggestion: I modified the answer to take advantage of (_reserveValue - answer) / OutMod == _reserveValue / OutMod and re-ran it for longer. –  Chris Culter Aug 19 at 7:02
1  
To be honest, @chris, if I was you, I would simplify the code a bit - remove the constexpr and random so that it can compile with older compilers, static performance counters and maybe use less C++ (no templates-simpler naming etc.) I think that this answer didn't get the votes it deserved just due to the discouraging syntax for non C++ programmers. –  neverlastn Aug 19 at 17:37

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.

share|improve this answer
1  
Now that I understand @andre's code, I think this is the same answer. –  alex.jordan Aug 17 at 23:07
    
This is nice and simple and more detailed on @steveverrill's answers. The problem is that it gives a bit less than 0.5 D7's out of a D6 roll while some others solutions in this page are near-optimum (0.9208) –  neverlastn Aug 18 at 11:58
3  
The simplest way I can think of is this way: have a red die and a white die. Roll both. if it's double 6, then reroll both. Otherwise, if the red die shows 6, the answer is 7. Otherwise, the answer is the value of the white die. –  Dan Uznanski Aug 18 at 14:55
1  
I'm afraid that despite this answer being very popular it holds no chance due to its inefficiency. I appreciate the simplicity and how easy it is to prove that it works but it gives a bit less than 0.5 D7 rolls per D6 roll when the optimum is ~ 0.92 and many algorithms below approximate that with little additional complexity. –  neverlastn Aug 18 at 15:46
5  
@neverlastn - When dealing with physical dice, simplicity is to be preferred over efficiency. When dealing with dice simulators, efficiency is preferred over simplicity. –  Bobson Aug 18 at 20:39

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.

share|improve this answer
1  
After 10^8 runs I get this distribution of number of rand6()'s per rand7(). It always terminates in less than 416 iterations. On average is 1.08603314, slightly better than Chris's & very close to the optimum 1.08603313. Compact algorithm but hard to understand or prove. I think that ((int)(a+width) != (int)a) tries to ensure that even if we roll 6 continuously from this point on (int)a won't change. I'm not sure it implements that. I guess it's very difficult to prove that there are no ill-cases but seems very efficient. Does this technique have a name? –  neverlastn Aug 18 at 11:48
1  
I think this is by far the most efficient implementation and has some sound theory to back it. –  neverlastn Aug 18 at 17:24
1  
This could be revised to have a perfectly even distribution by replacing the floating point arithmetic with unlimited-precision fractions (i.e. a ratio of BigIntegers). That would come at a certain cost in speed, though. –  Brilliand Aug 18 at 20:49
1  
Sorry for being slow (and not understanding code very well), but can someone please explain in words what this algorithm does? thanks. –  user103828 Aug 19 at 9:00
2  
@user103828: The key is that during the while loop and at the start and end of the function, the property that a + width is in the range |0, 7) is invariant (except for the base case, when a + width == 7). I've provided a more complete explanation here. –  jxh Aug 19 at 15:48

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}$$

share|improve this answer
    
Unless I read this wrong this gives you 1/6 probability of rolling a 7 - clearly very wrong. –  Daenyth Aug 18 at 15:50
3  
@Daenyth you have a 5 in 35 chance of rolling a 1,2,3,4,5,6 or 7, i.e. all have a 1/7 probability. –  Stephen Quan Aug 18 at 15:59
1  
@Daenyth: Huh? I see 35 non-X possibilities, 5 of them result in a 7, which gives the correct desired probability of 5/35 = 1/7 chance of resulting in a 7. –  David Cary Aug 18 at 16:02
    
After looking at it again it does look like you'll hit it with slightly more than 5/36 chance. Not perfect but close –  Daenyth Aug 18 at 16:03
1  
Nice and simple. Definitely the easiest way to do it with two physical dice. –  Bobson Aug 18 at 20:44

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 :)

share|improve this answer
    
Great creative answer :) –  neverlastn Aug 17 at 23:40
2  
I mean - more seriously... it's not easy to do this in an unbiased way :D –  neverlastn Aug 18 at 9:33
3  
Throw one die at your neighbor's dog. If it barks <= 7 times, that's your number. If it barks > 7 times, repeat. If again it barks > 7 times, go buy new dice. –  user2023861 Aug 18 at 16:04

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;
    }
}
share|improve this answer
    
This has 2.7% prob of needing more than one pair-roll and 0.07% of needing more than 2 which is quite good. The only problem is that it gives about 0.5 7-dice values per 6-dice roll. i.e. quite a bit of dice rolling at first sight. –  neverlastn Aug 17 at 22:39
    
@nerverlastn: You're going to need at least two rolls in order to have a chance at more than 6 possible values. The alternative would be to remember the previous roll and use that instead of rolling a second time...but that seems like it'd make the next roll partially dependent on the previous one (which might muck around with probabilities). –  cHao Aug 18 at 13:52
2  
@cHao: Yes, sometimes we want exactly one fair 1d7 value, and you're right that it's impossible to do that with only 1 roll of a 1d6 dice -- we need at least 2, sometimes more, and andre shows an excellent algorithm for that case. However, if we want several hundred independent and fair 1d7 values, it is (theoretically) possible to derive those values from (on average) log(7)/log(6) =~ 1.09 rolls of a fair 1d6 die per desired 1d7 value. However, the algorithm to do that is complex and more difficult to prove that it gives fair, independent 1d7 values. –  David Cary Aug 18 at 14:54
    
@David: It's not as complex as you might think. Rather than rolling twice, roll $n$ times, making each roll the next digit of a base-6 number. The $m = \lfloor{n \log{6} / \log{7}}\rfloor$ digits of its base-7 equivalent will correspond to 1d7 rolls as fair as the 1d6 rolls they came from. (The trick, though, is that you need to re-roll whenever your number would have more than $m$ base-7 digits. Simply discarding a digit would throw off the distribution. So optimization means picking an $n$ that minimizes $6^n/7^m$ (and thus the probability of needing to reroll). –  cHao Aug 18 at 16:20

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.

share|improve this answer
    
So if I roll D6 25 times, is the probability of having 0 as the leftmost digit of the base-7 equivalent, equal to the probability of having 6? –  neverlastn Aug 19 at 16:02
1  
You can do better. Those 4% of the time you don't have to discard everything. Because the next non-zero digit in your large number is two positions down, you can sometimes get a usable output that produces two less rolls. So 21 rolls. That's roughly 2% of the time. And you have another close to 2% of the time where you get 20 rolls, and a D6 left over because that digit is 6. You can continue this pattern all the way down, and you will hardly ever end up with no D7 at all. –  kasperd Aug 19 at 20:25
    
@kasperd Ah, so what you're saying is that you should roll your 25d6, convert to base 7, then delete all the leading digits that match $6^{25}$ plus the first non-matching digit, and use the remaining digits. Plus, if the non-matching digit in question is 6, you can save that d6 for next time. –  Neil Aug 19 at 23:22
    
@Neil If the number is less than $7^{23}$ it produces the 23 D7s. Otherwise subtract $7^{23}$ and look if the number is less than $7^{21}$, in which case it produces 21 D7s. Otherwise subtract $7^{21}$ and look if the number is less than $6*7^{20}$, in which case it produces 20 D7s and a D6. Otherwise subtract $6*7^{20}$ and look if the number is less than $2*7^{19}$, in which cases it produces 19 D7s and a D2 (but the D2 is not useful). Otherwise subtract $2*7^{19}$ and look if the number is less than $6*2^{17}$... –  kasperd Aug 20 at 6:11
    
@kasperd Yes, this is an equivalent procedure, you're matching the 1, 0, 1, 6, 2, 0, 6... from the digits of $6^{25}$ in base 7. –  Neil Aug 20 at 10:46

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.

share|improve this answer
    
A refinement of this will give an entropically optimum solution, you just have to retain the state instead of starting from scratch for each generated roll. –  Erick Wong Aug 17 at 23:41

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
share|improve this answer

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.

share|improve this answer
    
When you say e.g. "28 outcomes produce a simulated D7" how does this happen. Also in e.g. "2 outcomes take us to a state in group 2" - what state do they take you at? –  neverlastn Aug 18 at 12:13
    
@neverlastn There are 7 possibilities and 4 states in group 4. That means 4*7 = 28 possible combinations. Each of those must be mapped to exactly one of the 28 combinations of D6 and previous state. The last 2 outcomes are mapped to each of the 2 states in group 2. –  kasperd Aug 18 at 12:17
1  
I think if you pay a bit more careful attention you will see that the description is not that clear. "in group 4: 4*7 = 28 possible combinations" VS "From group 4 there are 24 outcomes". I think you either have an image in mind or an algorithm that you could share so that we can simulate and see how many D7's per D6 it gives. –  neverlastn Aug 18 at 12:44
    
This approach is pretty good, but not perfectly efficient. Perfect efficiency would in fact require an infinite number of states, since the sequence in which one has entered states is itself a piece of information which should eventually add up to a "free" D7 roll. –  supercat Aug 19 at 16:19
1  
@supercat Let me illustrate the behavior of that first algorithm with an example. Imagine the number $0.3$ in base 7. It could be written as $0.3\overline{0}$ or $0.2\overline{6}$, which produce different sequences of D7s. The probability of actually getting the base 6 representation of that number from your D6s is 0, but you can get an arbitrarily long prefix of that number. Until the D6s first deviate from that number, the algorithm don't know if the D7s will be a 2 followed by lots of 6s or a 3 followed by lots of 0s. –  kasperd Aug 19 at 19:52

I thought the algorithm described by kasperd was pretty clever, so I went ahead and implemented it. (Still learning Python, so I'd be happy for people to point out how this can be made easier to read and more Pythonic). I'm pretty sure this is effectively the same algorithm as the one described by alex.jordan . (The test_transitions() function compares the outputs of one transition_a() function that closely follows kasperd's description, vs. the outputs of another transition() function that closely follows alex.jordan's description, and verifies that both give identical output for every possible input).

#! /usr/bin/env python
# 2014-08-18: David Cary started.
# licensed under cc by-sa 3.0 with attribution required

def get_d6():
    import random
    return random.randint( 0, 5 )

def transition_a( numstates, substate, fresh_6_dice_value ):
    assert 1 <= numstates <= 6
    assert 0 <= substate < numstates
    outcome = substate*6 + fresh_6_dice_value

    if 1 == numstates :
        assert ( 0 <= outcome < 6 )
        fresh_7_dice_value = None
        numstates=6
        substate = outcome
    elif 2 == numstates :
        assert ( 0 <= outcome < 12 )
        if outcome < 7:
            fresh_7_dice_value = outcome
            numstates = 1
            substate = 0
        else:
            fresh_7_dice_value = None
            numstates = 12 - 7
            substate = outcome-7
    elif 3 == numstates :
        assert ( 0 <= outcome < 18 )
        if outcome < 14:
            fresh_7_dice_value = outcome % 7 # floor division
            numstates = 2
            substate = outcome // 7
        else:
            fresh_7_dice_value = None
            numstates = 18 - 14
            substate = outcome-14
    elif 4 == numstates :
        assert ( 0 <= outcome < 24 )
        if outcome < 21:
            fresh_7_dice_value = outcome % 7 # floor division
            numstates = 3
            substate = outcome // 7
        else:
            fresh_7_dice_value = None
            numstates = 24 - 21
            substate = outcome - 21
    elif 5 == numstates :
        assert ( 0 <= outcome < 30 )
        if outcome < 28:
            fresh_7_dice_value = outcome % 7 # floor division
            numstates = 4
            substate = outcome // 7
        else:
            fresh_7_dice_value = None
            numstates = 30 - 28
            substate = outcome - 28
    elif 6 == numstates :
        assert ( 0 <= outcome < 36 )
        if outcome < 35:
            fresh_7_dice_value = outcome % 7 # floor division
            numstates = 5
            substate = outcome // 7
        else:
            fresh_7_dice_value = None
            numstates = 36 - 35
            substate = outcome - 35
    else:
        print( "this should never happen." )

    assert 1 <= numstates <= 6
    assert 0 <= substate < numstates
    return numstates, substate, fresh_7_dice_value

def transition( numstates, substate, fresh_6_dice_value ):
    assert 1 <= numstates <= 6
    assert 0 <= substate < numstates
    outcome = substate*6 + fresh_6_dice_value
    num_outcomes = numstates*6
    assert ( 0 <= outcome < num_outcomes )

    max_sevens = num_outcomes // 7 # floor division

    if outcome < (7*max_sevens):
        # actual_newvalue has equal probability of any value
        # from 0 to 7*x-1,
        # which is the same as all possible pairs of
        # 1d7 (fresh_7_dice_value) and 1d(x) (new_group).
        # Store the 1d(x) value for later use, and emit the 1d7 value.
        fresh_7_dice_value = outcome % 7
        numstates = max_sevens
        substate = outcome // 7 # floor division
        """
        # (alternate method of partitioning)
        fresh_7_dice_value = outcome // max_sevens # floor division
        numstates = max_sevens
        substate = outcome % max_sevens
        """
    else:
        # actual_newvalue has equal probability of any value
        # from n=7*x to max_newvalue,
        # this always happens when 0 == n:
        fresh_7_dice_value = None
        numstates = num_outcomes - (7*max_sevens)
        assert( num_outcomes % 7 == numstates )
        substate = outcome - (7*max_sevens)
        assert( outcome % 7 == substate )

    # print( "-->", numstates, substate, fresh_7_dice_value )
    assert 1 <= numstates <= 6
    assert 0 <= substate < numstates
    return numstates, substate, fresh_7_dice_value

def test_dice_converter():
    input_6_dice = 0
    output_7_dice = 0
    output_passes = 0
    numstates = 1
    substate = 0
    d6values = [0, 0, 0,   0, 0, 0]
    d7values = [0, 0, 0,   0, 0, 0,  0]
    substate_values_pass = [0, 0, 0,   0, 0, 0,  0]
    substate_values_out  = [0, 0, 0,   0, 0, 0,  0]
    consecutive_passes = 0
    max_consecutive_passes = 0
    # at any one time, 0 <= substate <= numstates.
    # Also, at any one time, all values of substate have equal probability.
    while( output_7_dice < 10000 ):
        fresh_6_dice_value = get_d6()
        input_6_dice += 1
        d6values[fresh_6_dice_value] += 1
        if(consecutive_passes > 30 ):
            print( "consecutive_passes: ", consecutive_passes, "numstates: ", numstates, "substates: ", substate, fresh_6_dice_value )
        numstates, substate, fresh_7_dice_value = transition(
            numstates, substate, fresh_6_dice_value )
        if fresh_7_dice_value is None:
            output_passes += 1
            substate_values_pass[substate] += 1
            consecutive_passes += 1
        else:
            output_7_dice += 1
            d7values[fresh_7_dice_value] += 1
            substate_values_out[substate] += 1
            if consecutive_passes > max_consecutive_passes:
                max_consecutive_passes = consecutive_passes
            consecutive_passes = 0
        # print( fresh_6_dice_value, " ", fresh_7_dice_value )
    print( "input_6_dice ", input_6_dice )
    print( "output_7_dice ", output_7_dice )
    print( "d6 distribution:", d6values )
    print( "d7 distribution:", d7values )
    print( "passes:", output_passes)
    print( "max_consecutive_passes:", max_consecutive_passes)
    print( "substate_values_pass", substate_values_pass)
    print( "substate_values_out" , substate_values_out)
    assert( sum( d6values ) == input_6_dice )
    assert( sum( d7values ) == output_7_dice )
    assert( output_7_dice + output_passes == input_6_dice )

def main():
    test_transitions()
    test_dice_converter()

if __name__ == '__main__':
    main()

My tests indicate that this algorithm, given a fair 6-sided die, does give evenly-distributed simulated 7-sided die.

...
('input_6_dice ', 13713)
('output_7_dice ', 10000)
('d6 distribution:', [2277, 2312, 2295, 2299, 2291, 2239])
('d7 distribution:', [1425, 1474, 1437, 1444, 1308, 1446, 1466])
('passes:', 3713)
('max_consecutive_passes:', 6)
...

Alas, this requires about 13749 rolls of a 6-sided die in order to get 10000 rolls of the simulated 7-sided die -- better than the over 20000 rolls used by some other algorithms, but not as good as the about 10861 rolls that the algorithm from Chris Culter.

Both this algorithm and Culter's algorithm attempt to preserve some leftover entropy from previous D6 values.

As supercat pointed out, there's a small bit of entropy loss in this algorithm when we inspect the current state and decide whether or not to emit a D7 value -- equivalent to flipping a biased coin, so less than 1 bit of entropy. This algorithm simply throws away that entropy. Culter's algorithm does the same thing, but it adds a little code complexity to arrange things such that the "coin" is much, much more biased, so it loses much less entropy each time.

share|improve this answer

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."

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
i.e. this doesn’t answer the question at all. –  U2744 SNOWFLAKE Aug 19 at 6:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.