How to create a biased number generator using a pair of six sided dice

Question

What is the most efficient way to use a pair of six sided dice to generate a random number in [1, 4] unevenly: it should produce 1 in 40% of the time, 2 in 30%, 3 in 20%, and 4 in 10%.

Please justify the correctness of the method and give an algorithm.

Dice could be of different colors.

Note: the only random number generators available are two differently coloured six-sided dice.

Answer 1

Assume two dice: one white one black.

1. Roll the two dice giving you two numbers from 1 to 6;
2. Create a new number: 6 * (white dice - 1) + black dice
3. This number is between 1 and 36. If it's above 30 go to 2 and repeat;

Now you have what you need:

• 1-12 = 1 (12/30 = 40%)
• 13-21 = 2 (9/30 = 30%)
• 22-27 = 3 (6/30 = 20%)
• 28-30 = 4 (3/30 = 10%)

What you need is not 4 possible outcomes but 10 because that can represent the weighted result you want. Two dice can produce 36 possibilities in a number of ways but what you need is 10 or a multiple of 10, such as the above.

The only downside to this method is that it's probabilistic (meaning you could sit there rerolling 31+ forever technically) but I'm not convinced a deterministic and accurate solution exists.

Answer 2

One method is to generate a random integer and use that as an index into an array that specifies your probabilities.

For example, the following psuedocode would produce 1 2/3rds of the time, and 2 1/3rd of the time.

var randArray = [1, 1, 2];
var randIndex = random(2);
return randArray[randIndex];

Answer 3

The key: "it should produce 1 in 40% of the time, 2 in 30%, 3 in 20%, and 4 in 10%"

There are 36 possible outcomes of a roll of a pair of 6 sided dice. red, blue (assume some distinguishment of the dice)
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

10% of 36 outcomes breaks down to 3.6 outcomes.. which is not possible, so you are going to throw out six outcomes to get it to 30 outcomes which is divisble by 10. For ease, throw out the duplicate roles (1-1, 2-2, 3-3, 4-4, 5-5, 6-6)

So now a unit of 10% if 3 outcomes. Now your bins [1-4] need the appropriate number of outcomes to make up 40%, 30%, 20%, 10%.

.. or
40% = 12 / 30 outcomes... so take the first twelve cases .. remember duplicates are removed = (1,2) through (3,2)
30% = 9 / 30 outcomes... take the next 9 outcomes = (3,4) through (5,1)
20% = 6 / 30 outcomes... take the next 6 outcomes = (5,2) through (6,2)
10% = 3 / 30 outcomes... take the final 3 outcomes = (6,3) through (6,5)

.. now the problem is that any duplicate roll forces a re-roll, and that can happen over and over again, so this is not efficient. The problem is that base 6 (dice) and base 10 (10% = 1/10th) are for lack of a better term - prime to eachother. This is the same problem as representing 1/10th in binary. You can only come close no matter how many bits you use = no matter how many rolls, you can not produce a perfect 10% bin with 6 sided die.

You would have to use 5 or 10 sided die.

Answer 4

As others have pointed out, there is not a solution that works 100% of the times, and you have to use rejection sampling.

In general, I second Cletus's answer, but using his algorithm you will obtain one result from two dice with probability 5/6, meaning that the expected "number of results per die" is 5/12 ~= 0.417. Multiplying the latter by the entropy of one of your random results, which is

-(0.1*log2(0.1) + 0.2*log2(0.2) + 0.3*log2(0.3) + 0.4*log2(0.4)) ~= 1.846

we obtain 0.770. In other words, we are using, on average, 0.770 bits of information from each die. We can do better than this.

For example, throwing 9 dice you have 6^9 = 10077696 possible outcomes. Following Cletus, form a number from 0 to 10077695, and keep it only if it falls between 0 and 9999999 (this happens with probability ~0.992). When this is the case, you have 7 random decimal digits with uniform distribution, and from each of these you can extract a random number as in your problem:

0,1,2,3 --> 1
4,5,6   --> 2
7,8     --> 3
9       --> 4

This way we have 7 random results every 9 dice with probability 0.992, or an average "number of results per die" of 0.992*7/9 ~= 0.772. Multiplying this by the entropy of a result, we have 1.846*0.772 ~= 1.425. Thus, in this way we are using on average 1.425 bits from every die.

We can probably do better throwing more dice or adopting another technique. Of course, an upper bound is the entropy of a die, which is log2(6) ~= 2.585 bits.

Answer 5

Since this homework has probably been turned in by now, I'll give my answer: The idea is to progressively refine your roll until you can be sure which color was chosen.

First, divide the span from 0 to 1 into chunks corresponging to the probabilities: Mark off 0.4, 0.7, 0.9 and 1.0 on a number line, which define regions labelled 1 to 4. You will need to keep track of the number of times you have rolled the dice, n, and a running counter, p. Initially, set n=1, p=0.

1. Roll a die and divide by 6*n, and add this value to p. Mark this spot on the number line.
2. If p and p + 1/6n are in the same 'region' (they do not cross the boundaries you defined above) you are done, and the color is the color of the region p falls in.
3. Otherwise increment n and go to 1.

This way, most of the time you will only need one or two rolls to figure out which color gets chosen, although ocasionally you will have to roll more if you end up near a boundary. With your weights, 40% of the time you only need 1 roll, 44% of times you need two, 13% you need 3, and around 3% of the time you will need more.

Answer 6

I don't feel very well about doing somebody else's homework, but I can give a hint: look at this graph and work from there.

Answer 7

Use a 10-sided die, marked 1,1,1,1,2,2,2,3,3,4. Or are you (for some reason) limited to six-sided dice? For a computer implementation, see Benny Jobigan's answer.

However, if you're restricted to two six-sided dice, one method is to make 36 small square cards. Mark 12 with "1", mark 9 with "2", mark 6 with "3", mark 3 with "4" and eithjer leave six blank or mark them "re-roll".

Arrange the 36 cards in a 6x6 square. Mark each row and column with the numbers 1-6 and decide what die corresponds to the columns and what to the rows.

Roll the dice and find the card that corresponds to the row and column selected. If the card has a number, that's the number you want, if it's blank (or says "re-roll"), roll both dice again.

Note that the exact placement of the numbers on the grid doesn't matter for fair dice, but will give different results for biased dice.

Answer 8

This is for 1 dice as I wrote it for a biased roulette wheel for a genetic algorithm, but can be adapted. It's in C# but will easily change for Java or other C-based languages.

First start with a set of values
Swap these values for numbers 1-6 if you want to replicate an actual dice.

double[] values =
{
    9,
    66,
    153,
    2,
    42,
    34
};

Then add the percentages you want each of these to appear.
For example, you want 153 to be biased so it's chosen 25% of the time:

double[] percentages = 
{ 
    15, 
    10, 
    25, 
    5, 
    37, 
    8 
};

Now setup some ranges for the percentages.
This is used for the dice roll, so if 15-25 is rolled, you know it's fallen within the second percentage range.

double[] ranges = new double[6];
ranges[0] = percentages[0];
ranges[1] = ranges[0] + percentages[1];
ranges[2] = ranges[1] + percentages[2];
ranges[3] = ranges[2] + percentages[3];
ranges[4] = ranges[3] + percentages[4];
ranges[5] = ranges[4] + percentages[5];

And lastly, generate a random number.
If that number falls between one of the ranges, pick that index from the values.

static Random _random = new Random();

static void Main(string[] args)
{
    ...

    for (int i = 0; i < percentages.Length; i++)
    {
        int rand = _random.Next(0, 100);
        double x = ranges.First(n => n >= rand);
        int index = ranges.ToList().IndexOf(x);
        Console.WriteLine(values[index]);
    }
}

I'm sure there's ways to improve this and I'd be interested to know them.