Real dice.

Suppose you want to draw randomly a number between 0 and 1, with multiple throws of a six sided dice, what would you write down on its face?

dice

If you want to form numbers between 0 (inclusive) and 1 (exclusive), you could assign the faces a subset of the usual digits (0 to 9), and throw the dice multiple time, each time giving you a new decimal. So throwing 3, 4, 7, 8, (say) would give you 0.3478. But how do we chose what to write on the faces?

Intuitively, we would think that spacing the digits as evenly as possible is the way to go, something like 1, 3, 5, 7, 8, 9. But is our intuition correct? There are \displaystyle\binom{10}{6}=210 subsets of six digits, so there’s not that many to check, so we can use brute force enumeration. But how do we measure the evenness of the spread of generated numbers? We simply measure the (square of the) distance between all possible numbers generated.

The test therefore relies on three steps. 1) generate all possible subsets, 2) generate all possible numbers we can represent with the digits from each of the subsets, and 3) measure distance.

The first step, generate all possible subsets, can be done using the “shuttle algorithm” that takes a permutation of (not necessarily distinct symbols) and yield the next one in lexicographical order. We’ve already met this algorithm in a previous entry. We start with the initial permutation 0,0,0,0,1,1,1,1,1,1. The next will be 0,0,0,1,0,1,1,1,1,1. Eventually, we reach the last one, 1,1,1,1,1,1,0,0,0,0. We use the permutation as a bit-vector to select the subset of digits: 0,1,1,0,0,0,1,1,1,1 selects 1,2,6,7,8,9 from 0,1,2,…,9.

The second step is done with a base six counter, that will count, on a fix length, from 0 to n-digit overflow. This counters goes 0, 1, 2, 4, 5, 10, 11, 12, 13, 15, 25,… A presentation layer converts the number represented by the counter to the actual symbols from the subset. That re-coded number is converted to a float (or an integer).

The third, and last, step, just measures the spacing between successive numbers. This means that a number that goes from xxxx15 to xxxx20 will incur a larger penalty than a number that goes from yyyy18 to yyyy20.

*
* *

Running the program will let us discover the best subset of digits to write on the dice’s faces:

024689	425723808
135789	520243666
146789	733009458
246789	827529316
256789	1040295108
345678	1339694288
356789	1347580758
456789	2080397992

So for this almost kind-of ten-sided dice on a six-side dice, the best combination is 0, 2, 4, 6, 8, 9. It’s not the only one. The program only selects a new combination if it has a strictly better score than the previous one. But we also find 0,1,2,3,5,7,9, 0,2,3,5,7,9, 0,2,4,5,7,9, and 0,2,4,6,7,9 with the same discrepancy, or, alternatively, with the same evenness.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: