Hacker News new | past | comments | ask | show | jobs | submit login

Given a dice with an unknown bias, you can generate a stream of unbiased random bits [1].

The method is an extension of von Neumann's trick for un-biasing a biased coin in which you flip it multiple times and take advantage of symmetry (specifically flip it twice and return heads if you got heads then tails, return tails if you got tails then heads, or repeat the procedure if you obtained two heads or two tails).

You can then go from this bit-stream to a number in {1,...,6} using the trick jknz mentions below (take 3 successive bits, and interpret them as a binary number between 0 and 7, add one to get a number between 1 and 8, and start again if the result is 7 or 8).

[The method in the paper is apparently asymptopically optimal (as the number of faces on the dice goes to infinity). However, for small numbers of faces I think it is slightly worse than the method jknz described. Consider the 4-faced dice: the Peres method converts a pair of dice rolls into 1 or zero bits, but jknz's method would sometimes produces two bits (the rolls 1,4/2,3/3,2/4,0 are binary 00,11/01,10/10,01/11,00 resulting in sampled bits 0,0/0,1/1,0/11). Working out all the cases shows this makes the method slighly more efficient.]

[1]: http://dx.doi.org/10.1109/TIT.2014.2381223




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: