Prime Sided Dice

[gavinksong]

Credit for this puzzle goes to the author of the blog, By Way of Contradiction.

 

Imagine that you have a collection of very weird dice. For every prime number between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001, inclusive.

 

What is the fewest expected number of die rolls needed to complete this task?

[dgreening]

Some initial thoughts

 

 

About the dice

• There are 168 prime numbers between 1 and 1000 [i looked it up]
  • Therefore there are 832 non-primes in the range
  • The average of these 168 numbers is about  453.1
  • All except for "2" are odd numbers [which will come up about 0.6% of the time]
     
• The distribution is not close to uniform
  • For any range, the primes with lower values, tend to be more represented
    • 25 primes are below 100, while only 13 primesare between 900 and 1000
    •  there are 95 primes in the range 1-500, while there are only 73 primes from
      500 to 1000

Since about 99.4% of all rolls will result in an odd number

 

• If you simply roll the dice and sum the results -
  • An even number of rolls will alomst always result in an even number
  • An odd number of rolls will almosat always result in an odd number

Based on these observations, you cannot simply roll the dice a specific number of items and add them

• The results will be biased to odd or even
• low numbers [like 4 or 20] will almost never occur.

The algorithm must be more complicated than simple summation.

[k-man]

Just to clarify...

 

Since there are 168 primes in the range of 1...1000 I have 168 dice at my disposal. Each die N has the number of sides equal to the Nth prime number. Each side of the die N has numbers between 1 and Nth prime inclusive on it, so that the die with 997 sides has numbers 1...997. All dice are fair.

Edited March 2, 2015 by k-man

[bonanova]

That helps. OP does not specify the numbers on the die faces.

[k-man]

My previous post was meant to be a clarifying question rather than a statement. Sorry if I caused more confusion.

[DejMar]

Three dice will do the trick.

Take the 7-, 11-, and 13-sided dice.

7*11*13 = 1001, thus, a random integer may be generated uniformly between 1 to 1001, inclusive, using these dice.

Let the faces of the 13-sided die be numbered: 0, 77, 154, 231, 308, 385, 462, 539, 615, 693, 770, 847, and 924.
Let the faces of the 11-sided die be numbered: 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70.
Let the faces of the 7-sided die be numbered: 1, 2, 3, 4, 5, 6, 7.

Roll the three dice, summing the numbers on each of the dice for the random integer.

[gavinksong]

Three dice will do the trick.

Take the 7-, 11-, and 13-sided dice.

7*11*13 = 1001, thus, a random integer may be generated uniformly between 1 to 1001, inclusive, using these dice.

Let the faces of the 13-sided die be numbered: 0, 77, 154, 231, 308, 385, 462, 539, 615, 693, 770, 847, and 924.

Let the faces of the 11-sided die be numbered: 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70.

Let the faces of the 7-sided die be numbered: 1, 2, 3, 4, 5, 6, 7.

Roll the three dice, summing the numbers on each of the dice for the random integer.

 

Well done, DejMar! That was quite good.

 

However, I claim that you can do better.

[gavinksong]

Just to clarify...

 

Since there are 168 primes in the range of 1...1000 I have 168 dice at my disposal. Each die N has the number of sides equal to the Nth prime number. Each side of the die N has numbers between 1 and Nth prime inclusive on it, so that the die with 997 sides has numbers 1...997. All dice are fair.

 

Yes. Everything you have said is correct, although it does not matter what is printed on each side of the die. All that matters is that they are distinguishable.

[DejMar]

ERROR...

Edited March 4, 2015 by DejMar

[plasmid]

Roll the 59-sided die and the 17-sided die, and take their product. If that product is in the range 1-1001 then use that number. Otherwise re-roll both dice and take the new product, and repeat however many times it takes until the product is in the range 1-1001. 

 

59*17 = 1003, so there is a 1001/1003 chance that the product will be in the desired range each time. The expected number of rolls would be:

Sum from n=1 to infinity of (the number of die rolls you would make if you rolled the pair of dice n times) * (probability you will need to roll them n times)

= Sum [n=1 to inf] (2*n) * (2/1003)^n-1 * (1001/1003)

which I'm not sure how to calculate explicitly, but it's ~= 2.004

[DejMar]

@plasmid

 

Ignoring the re-roll part and probability, rolling 2-dice and taking the product does not create a uniform random integer. Some values will occur more often than others in that manner (1x4 & 2x2 both equal 4, e.g.),

[gavinksong]

 

Roll the 59-sided die and the 17-sided die, and take their product. If that product is in the range 1-1001 then use that number. Otherwise re-roll both dice and take the new product, and repeat however many times it takes until the product is in the range 1-1001. 

 

59*17 = 1003, so there is a 1001/1003 chance that the product will be in the desired range each time. The expected number of rolls would be:

Sum from n=1 to infinity of (the number of die rolls you would make if you rolled the pair of dice n times) * (probability you will need to roll them n times)

= Sum [n=1 to inf] (2*n) * (2/1003)^n-1 * (1001/1003)

which I'm not sure how to calculate explicitly, but it's ~= 2.004

 

 

That's very good and quite close to the optimal number of expected rolls, but you can do even better. 

 

Edit -- After reading DejMar's post, I realized that he is right. plasmid's method wouldn't produce any primes above 59, for example.

Edited March 6, 2015 by gavinksong

[DejMar]

Label the faces of the 79-sided die from 1 to 77, with two faces marked re-roll.

Label the 13-sided die from 0k to 12k, where k=77.

Roll the two dice and add the faces, re-rolling the 79-sided die if so indicated.
There is a 2/79, i.e., approximate 2.5316% chance of a re-roll required after each roll, but an approximate 97.4684% chance that the two-dice will result in the random integer required in the first roll.

Edited March 6, 2015 by DejMar

[plasmid]

 Thanks for catching that DejMar.

Instead of taking the product of the 59-sided die and the 17-sided die:

Take 59 * ([what's on the 17-sided die] minus one) + (what's on the 59-sided die)

That will produce a uniform distribution from 1 to 1003. The rest of the argument remains unchanged with ~2.004 rolls expected.

I'll think about how it could be made even better.

[plasmid]

Slightly better

Roll the 601-sided die and the 5-sided die.

Take 5*([601-sided die roll] minus one) + (5-sided die roll)

The outcome will be a uniform distribution from 1 to 3005.

Add 2, then divide that by 3 and throw out the remainder if there is a remainder.

The outcome will now be a uniform distribution from 1 to 1001 plus an additional 2/3005 chance of getting 1002.

If the outcome is not in the 1 to 1001 range, re-roll those dice and keep repeating until you get 1-1001.

 

The expected number of rolls would be:

Sum from n=1 to infinity of (the number of die rolls you would make if you rolled the pair of dice n times) * (probability you will need to roll them n times)

= Sum [n=1 to inf] (2*n) * (2/3005)^n-1 * (3003/3005)

which I'm not sure how to calculate explicitly, but it's ~= 2.00133

You can do a minuscule bit better by taking those values of 3004 or 3005 that get thrown out if you don't accept those results, converting them to 0s and 1s, putting them together into a large binary number from 1 to 1024 if that happens repeatedly, and then taking that as sort of an extra free set of rolls to try to generate a number in the 1-1001 range. But the improvement would be so small that it wouldn't change the result in the decimal range that I've shown for the estimated answer.

[plainglazed]

roll the three sided die twice thus randomly generating with uniform distribution all the integers between 1 and 1001

[Rainman]

roll the three sided die twice thus randomly generating with uniform distribution all the integers between 1 and 1001

 What's three? Don't you mean the 11-sided die?

 

Firstly, let's prove that the number of die rolls can never be less than 2. Suppose one die roll could generate an integer. Then the probability of that integer being generated would be no less than the probability of that particular die roll, which is no less than 1/997, which is larger than 1/1001. So that integer is generated with a probability larger than 1/1001, which contradicts the uniform distribution requirement. Conclusion: the expected number of die rolls is greater than or equal to 2, with equality iff we can always do it with 2 die rolls.

Secondly, let's prove that we can't always do it with 2 die rolls. Suppose we could. Let P₁ and P₂ be the number of sides on the dice. Each of the P₁*P₂ outcomes would have to be uniquely mapped to one of the 1001 integers, with uniform distribution, meaning that P₁*P₂ has to be a multiple of 1001. But 1001 has more than two prime factors, while P₁*P₂ only has two. This is a contradiction, as a multiple of 1001 can't have fewer prime factors than 1001 itself has. Conclusion: the expected number of die rolls is greater than 2.

Now, to continue on the path that DejMar and plasmid have beaten, let's find two dice that can be rolled with a small risk of re-rolling. Suppose we roll dice P₁ and P₂ such that P₁*P₂ = 1001n + a, where 0<a<1001. Then the risk of re-rolling is equal to a/(1001n+a), so we ideally want to minimize a while maximizing n. To maximize n, we need large P₁ and P₂, which leads me to start counting modulo 1001. 997 can be rewritten as 1001-4, 991 can be rewritten as 1001-10, and so on for the other large prime numbers. Making a list of these differences (4,10,18,24,30,34,48,54,60,64,72...) we seek two numbers D₁ and D₂ which are as small as possible (meaning P₁ and P₂ are large) while keeping the remainder of D₁*D₂/1001 as small as possible (meaning a is as small as possible). Ideally a should be 1, and I found that 24*292 = 7008, where both 24 and 292 are found on the list of differences, and 7008 = 7*1001+1. Going back to the original primes, we have 1001-24 = 977 and 1001-292 = 709. 977*709 = 692693 = 692*1001+1. We could roll the 977-sided die (result x) and the 709-sided die (result y), and calculate 977*(y-1)+x which uniformly yields an integer result between 1 and 692693 inclusive. For results 1 through 692692, divide by 1001 and let the remainder be your integer between 1 and 1001 inclusive. For result 692693, re-roll.

Is this the optimal solution? I can't quite prove it. It is easily verified that no a>1 can be better, but possibly we could make P₁*P₂ > 692693 and get a better result. There's also the unlikely possibility of a better method altogether.

[gavinksong]

Firstly, let's prove that the number of die rolls can never be less than 2. Suppose one die roll could generate an integer. Then the probability of that integer being generated would be no less than the probability of that particular die roll, which is no less than 1/997, which is larger than 1/1001. So that integer is generated with a probability larger than 1/1001, which contradicts the uniform distribution requirement. Conclusion: the expected number of die rolls is greater than or equal to 2, with equality iff we can always do it with 2 die rolls.

 

Secondly, let's prove that we can't always do it with 2 die rolls. Suppose we could. Let P₁ and P₂ be the number of sides on the dice. Each of the P₁*P₂ outcomes would have to be uniquely mapped to one of the 1001 integers, with uniform distribution, meaning that P₁*P₂ has to be a multiple of 1001. But 1001 has more than two prime factors, while P₁*P₂ only has two. This is a contradiction, as a multiple of 1001 can't have fewer prime factors than 1001 itself has. Conclusion: the expected number of die rolls is greater than 2.

 

Now, to continue on the path that DejMar and plasmid have beaten, let's find two dice that can be rolled with a small risk of re-rolling. Suppose we roll dice P₁ and P₂ such that P₁*P₂ = 1001n + a, where 0<a<1001. Then the risk of re-rolling is equal to a/(1001n+a), so we ideally want to minimize a while maximizing n. To maximize n, we need large P₁ and P₂, which leads me to start counting modulo 1001. 997 can be rewritten as 1001-4, 991 can be rewritten as 1001-10, and so on for the other large prime numbers. Making a list of these differences (4,10,18,24,30,34,48,54,60,64,72...) we seek two numbers D₁ and D₂ which are as small as possible (meaning P₁ and P₂ are large) while keeping the remainder of D₁*D₂/1001 as small as possible (meaning a is as small as possible). Ideally a should be 1, and I found that 24*292 = 7008, where both 24 and 292 are found on the list of differences, and 7008 = 7*1001+1. Going back to the original primes, we have 1001-24 = 977 and 1001-292 = 709. 977*709 = 692693 = 692*1001+1. We could roll the 977-sided die (result x) and the 709-sided die (result y), and calculate 977*(y-1)+x which uniformly yields an integer result between 1 and 692693 inclusive. For results 1 through 692692, divide by 1001 and let the remainder be your integer between 1 and 1001 inclusive. For result 692693, re-roll.

Is this the optimal solution? I can't quite prove it. It is easily verified that no a>1 can be better, but possibly we could make P₁*P₂ > 692693 and get a better result. There's also the unlikely possibility of a better method altogether.

Impressive results from everybody. 

I especially applaud Rainman on his thorough analysis - although it is incorrect. One of your assumptions is false.

[DejMar]

Roll the d977 and the d709.
977*(d709-1)+d977 [or, alternately, 709*(d977-1)+d709] provides the range of 1 to 692693.
If the result is 692693, re-roll, else divide by 692, and take the ceiling of the result.

A re-roll will occur 1/692693 (approximately 0.00014436%) for each roll.

 

Edit - I see after the fact that Rainman already found this answer.

Edited March 7, 2015 by DejMar

[gavinksong]

There is a surprisingly elegant solution to this problem. Start by reexamining your assumptions.

[gavinksong]

The optimal number of rolls is 2.

[gavinksong]

This puzzle is admittedly quite hard, so here is another hint.

 

You can choose which die you roll second

after rolling the first die.

[gavinksong]

Feel free to solve this puzzle.

[bonanova]

Two cents: do the same number of equally likely results round to each of the numbers in the desired range?

[unreality]

How bout this?

1001 = 7*11*13

311 = 7*11 + 7*13 + 11*13

311 prime so roll 311

has three buckets:

Bucket A (size 7*11) : 1-77

Bucket B (size 7*13) : 78-168

Bucket C (size 11*13) : 169-311

 

Based on which bucket you roll in, select the remaining number from the set (7,11,13). So if you get Bucket A (7*11) choose the 13-sided die. If you get in Bucket B, choose the 11-sided die. And choose 7 for Bucket C.

 

So roll that second die. The possible outcomes are:

7*11*13 + 7*13*11 + 11*13*7 = 3*(7*11*13) = 3*1001

 

Aha! :-)

[gavinksong]

How bout this?

1001 = 7*11*13

311 = 7*11 + 7*13 + 11*13

311 prime so roll 311

has three buckets:

Bucket A (size 7*11) : 1-77

Bucket B (size 7*13) : 78-168

Bucket C (size 11*13) : 169-311

 

Based on which bucket you roll in, select the remaining number from the set (7,11,13). So if you get Bucket A (7*11) choose the 13-sided die. If you get in Bucket B, choose the 11-sided die. And choose 7 for Bucket C.

 

So roll that second die. The possible outcomes are:

7*11*13 + 7*13*11 + 11*13*7 = 3*(7*11*13) = 3*1001

 

Aha! :-)

 

Brilliant!