<div dir="ltr"><div><div dir="ltr">On Wed, Aug 22, 2018 at 10:47 AM Howard Chu <<a href="mailto:hyc@symas.com">hyc@symas.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">John Denker via cryptography wrote:<br>> On 08/15/2018 07:20 AM, Dave Horsfall wrote:<br>> <br>>> it occurred to me that it's not as simple as it seems, with the<br>>> generated output (e.g. modulo 10) not being as uniform as one would<br>>> hope.<br>> </blockquote></div><div><br></div>A little Googling about von Neumann and dice led me to this <a href="http://markus-jakobsson.com/papers/jakobsson-ieeeit00.pdf">http://markus-jakobsson.com/papers/jakobsson-ieeeit00.pdf</a> which describes a very cute algorithm for getting fair resutls from biased dice. Since a lot of the discussion here has been "assuming perfect dice" and you describe a cheap pack of 12, which are likely far from perfect.<div><br></div><div>Essentially, partition the dice as suggested by John Denker - an egg carton seems ideal. Roll a few times, recording the results for each die. Result the lists of results to a list of *result ranks* - e.g. 3 2 6 -> 2 1 3 and 4 4 5 -> 1 1 2. Each such list is indexed into a canonical order of rank lists (e.g. 123, 132, [213], 231, 312, 321 -> 3) and the index is the result for that die for that set of rolls. Consume dice based on the "size" of the fair die (i.e. 326 is a result of a 6 sided fair die, but 445 is on a 3 sided die) until the sum of the sides is at least your required range.</div><div><br></div><div>The paper also describes how to convert the results into fair bitstrings, which might let you truncate at the point where you have enough bits, where the above summing solution would demand that you discard the whole result if it were greater than your intended range.</div><div><br></div><div>Alternatively (and on increasingly shaky ground), you might discard final "fair dice" until you found one of the right size to get you to your needed range. I think if the algorithm for choosing which dice to include were deterministic for a particular result, you might still get good random values, but I'd be shocked if no one here differed on that point.</div><div><br></div><div>Judson</div></div>