Imagine that you have a collection of very weird dice. For every prime 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.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it.
If you care about more than the first roll, so you want to make lots and lots of uniform random numbers in 1, 1001, then the best die is (rot13′d) gur ynetrfg cevzr va enatr orpnhfr vg tvirf lbh gur zbfg ragebcl cre ebyy. Lbh arire qvfpneq erfhygf, fvapr gung jbhyq or guebjvat njnl ragebcl, naq vafgrnq hfr jung vf rffragvnyyl nevguzrgvp pbqvat.
Onfvpnyyl, pbafvqre lbhe ebyyf gb or qvtvgf nsgre gur qrpvzny cbvag va onfr C. Abgvpr gung, tvira gung lbh pbhyq ebyy nyy 0f be nyy (C-1)f sebz urer, gur ahzore vf pbafgenvarq gb n cnegvphyne enatr. Abj ybbx ng onfr 1001: qbrf lbhe enatr snyy ragveryl jvguva n qvtvg va gung onfr? Gura lbh unir n enaqbz bhgchg. Zbir gb gur arkg qvtvg cbfvgvba naq ercrng.
Na vagrerfgvat fvqr rssrpg bs guvf genafsbezngvba vf gung vs lbh tb sebz onfr N gb onfr O gura genafsbez onpx, lbh trg gur fnzr frdhrapr rkprcg gurer’f n fznyy rkcrpgrq qrynl ba gur erfhygf.
Ebyy n friragrra fvqrq qvr naq n svsgl guerr fvqrq qvr (fvqrf ner ynoryrq mreb gb A zvahf bar). Zhygvcyl gur svsgl-guerr fvqrq qvr erfhyg ol friragrra naq nqq gur inyhrf.
Gur erfhyg jvyy or va mreb gb bar gubhfnaq gjb. Va gur rirag bs rvgure bs gurfr rkgerzr erfhygf, ergel.
Rkcrpgrq ahzore bs qvpr ebyyf vf gjb gvzrf bar gubhfnaq guerr qvivqrq ol bar gubhfnaq bar, be gjb cbvag mreb mreb sbhe qvpr ebyyf.
I am glad someone is thinking about it enough to fully appreciate the solution. You are suggesting taking advantage of 709*977=692693. You can do better.
You can do better than missing one part in 692693? You can’t do it in one roll (not even a chance of one roll) since the dice aren’t large enough to ever uniquely identify one result… is there SOME way to get it exactly? No… then it would be a multiple of 1001.
I am presently stumped. I’ll think on it a bit more.
ETA: OK, instead of having ONE left over, you leave TWO over. Assuming the new pair is around the same size that nearly doubles your trouble rate, but in the event of trouble, it gives you one bit of information on the outcome. So, you can roll a single 503 sided die instead of retrying the outer procedure?
Depending on the pair of primes that produce the two-left-over, that might be better. 709 is pretty large, though.
Imagine that you have a collection of very weird dice. For every prime 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.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it.
Solution
If you care about more than the first roll, so you want to make lots and lots of uniform random numbers in 1, 1001, then the best die is (rot13′d) gur ynetrfg cevzr va enatr orpnhfr vg tvirf lbh gur zbfg ragebcl cre ebyy. Lbh arire qvfpneq erfhygf, fvapr gung jbhyq or guebjvat njnl ragebcl, naq vafgrnq hfr jung vf rffragvnyyl nevguzrgvp pbqvat.
Onfvpnyyl, pbafvqre lbhe ebyyf gb or qvtvgf nsgre gur qrpvzny cbvag va onfr C. Abgvpr gung, tvira gung lbh pbhyq ebyy nyy 0f be nyy (C-1)f sebz urer, gur ahzore vf pbafgenvarq gb n cnegvphyne enatr. Abj ybbx ng onfr 1001: qbrf lbhe enatr snyy ragveryl jvguva n qvtvg va gung onfr? Gura lbh unir n enaqbz bhgchg. Zbir gb gur arkg qvtvg cbfvgvba naq ercrng.
Na vagrerfgvat fvqr rssrpg bs guvf genafsbezngvba vf gung vs lbh tb sebz onfr N gb onfr O gura genafsbez onpx, lbh trg gur fnzr frdhrapr rkprcg gurer’f n fznyy rkcrpgrq qrynl ba gur erfhygf.
I give working code in “Transmuting Dice, Conserving Entropy”.
I will say as little as possible to avoid spoilers, because you seem to have thought enough about this to not want it spoiled.
The algorithm you are describing is not optimal.
Edit: Oh, I just realized you were talking about generating lots of samples. In that case, you are right, but you have not solved the puzzle yet.
Ebyy n friragrra fvqrq qvr naq n svsgl guerr fvqrq qvr (fvqrf ner ynoryrq mreb gb A zvahf bar). Zhygvcyl gur svsgl-guerr fvqrq qvr erfhyg ol friragrra naq nqq gur inyhrf.
Gur erfhyg jvyy or va mreb gb bar gubhfnaq gjb. Va gur rirag bs rvgure bs gurfr rkgerzr erfhygf, ergel.
Rkcrpgrq ahzore bs qvpr ebyyf vf gjb gvzrf bar gubhfnaq guerr qvivqrq ol bar gubhfnaq bar, be gjb cbvag mreb mreb sbhe qvpr ebyyf.
You can do better :)
Yeah, I realized that a few minutes after I posted, but didn’t get a chance to retract it… Gimme a couple minutes.
Vf vg gur fnzr vqrn ohg jvgu avar avargl frira gjvpr, naq hfvat zbq 1001? Gung frrzf njshyyl fznyy, ohg V qba’g frr n tbbq cebbs. Vqrnyyl, gur cebqhpg bs gjb cevzrf jbhyq or bar zber guna n zhygvcyr bs 1001, naq gung’f gur bayl jnl V pna frr gb unir n fubeg cebbs. Guvf qbrfa’g qb gung.
I am glad someone is thinking about it enough to fully appreciate the solution. You are suggesting taking advantage of 709*977=692693. You can do better.
You can do better than missing one part in 692693? You can’t do it in one roll (not even a chance of one roll) since the dice aren’t large enough to ever uniquely identify one result… is there SOME way to get it exactly? No… then it would be a multiple of 1001.
I am presently stumped. I’ll think on it a bit more.
ETA: OK, instead of having ONE left over, you leave TWO over. Assuming the new pair is around the same size that nearly doubles your trouble rate, but in the event of trouble, it gives you one bit of information on the outcome. So, you can roll a single 503 sided die instead of retrying the outer procedure?
Depending on the pair of primes that produce the two-left-over, that might be better. 709 is pretty large, though.
The best you can do leaving 2 over is 709*953=675677, coincidentally using the same first die. You can do better.