= 27d567bc2d48d9f40e9ccc20ea370b15)
Strilanc comments on Open Thread for February 11 - 17 - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (325)
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.