How to best obtain bit sequences from throwing normal dice?

Question

Throwing normal dice, one can get sequences of digits in [0,5]. Which is the best procedure in practice to transform such sequences into bit sequences desired?

Answer 1

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon.

Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple methods like

1 -> 00
2 -> 01
3 -> 10
4 -> 11
5 -> 0
6 -> 1

is quite simple and produces $1+\frac23 = \frac53 \doteq 1.667$ bits per roll. AFAIK, this is the maximum you can get without aggregating the rolls.

You can apply this idea to two rolls and obtain $5$ bits with probability of $\frac{32}{36}$ and $2$ bits otherwise thus getting

$$2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83 = \frac{14}3 = 4\frac23$$

bits for two rolls, i.e., $2\frac13 \doteq 2.333$ bits per roll, which is quite close to the theoretical maximum of $\log_2 6 \doteq 2.585$.

For a simple "implementation without computer", note that you can extract 1 bit directly from each roll and need to process the "rest" only (e.g. you can get the bit via $n \bmod 2$ and the rest via $\lfloor \frac{n-1}3 \rfloor$). This makes even combining 3 or 4 rolls using a small table easy.

Answer 2

The obvious approach is to consider the following bit extraction algorithm:

1. Roll the die, producing an integer $n$ uniform in $\mathbb{Z}_6$.

2. If $n < 4$, return $n$ as two bits. Otherwise, go to 1.

This will return two uniform bits. The algorithm will always terminate, since the probability of recursion is equal to $\frac{2}{6}$ which is subcritical. A proof of correctness can be found in Dennis' post on this question.

How many dice rolls will the algorithm require? At least one, and arbitrarily many, but on average:

$$1 + \frac{2}{6} + \left ( \frac{2}{6} \right )^2 + \cdots = \sum_{t = 0}^\infty \left ( \frac{2}{6} \right )^t = \frac{3}{2}$$

That is, on average, the algorithm will require one and a half dice rolls. This is, of course, in accordance with information theory, which states that the Shannon entropy of an unbiased dice roll is equal to:

$$\log_2{ \left ( 6 \right )} = \log_2{\left ( 4 \right )} + \log_2{ \left ( \frac{3}{2} \right )}$$

---

However, this is not optimal. A lot of effort is wasted into compressing this into two uniform bits. Can we do better? Yes. For instance, consider rolling two dice together, drawing a uniform $n$ out of $\mathbb{Z}_{36}$. Then we can apply the same algorithm, but returning five bits instead of four, since $32 < 36$. Similarly, the probability of recursion is also lower at $\frac{4}{36}$ which means we are wasting less time and entropy.

We could also roll three dice, drawing $n$ out of $\mathbb{Z}_{216}$, but this is not optimal, even though we can extract seven bits, the probability of recursion is $\frac{88}{216}$ which is much higher than with even just a single die.

So, clearly, the "trick" is to select an integral number of dice such that $6^k$ is very close to (but greater than) a power of two, to minimize the probability of recursion and maximize our use of entropy. A computer program could be written to find the optimal number of dice to roll according to some efficiency metric, depending on your application's needs (or perhaps a general one exists).

---

The "intuition" behind this is that you can't use arbitrary amounts of entropy, since the bit is the absolute smallest amount of information possible. Any non-integral amount of entropy remaining must be "left behind" (here we use a recursive procedure to eliminate it, but there are other alternatives*).

However, if you can combine multiple such non-integral amounts of entropy through a non-destructive process (here, throwing multiple dice at the same time) you will naturally get more integral amounts of entropy ($0.5 + 0.5 = 1$) which allows you to make better use, of what you would otherwise have had to throw away.

---

*The answers to this question also suggest recursion is not an optimal approach in terms of efficiency.

Answer 3

1 way to get 3 bits of entropy from a single die roll is as follows :

1. Roll the fair die
2. For 2,3,4,5 yield two bits {01,10,11,00} and go to 4, for 1 or 6 yield {1,0}.
3. For the number on the die appearing right-way-up to the thrower (0-179 degrees) yield {0} for the number on the die appearing upside-down to the thrower (180-359 degrees) yield {1} and go to 5.
4. For the number on the die being oriented within the first quadrant yield {00} for the other quadrants proceeding clockwise yield {01,10,11}.
5. Go to 1.

So for example I throw the following sequence 2(12 degrees), 3(111 degrees), 6 (98 degrees)

 2 -> 01, 12 degrees -> 0 , so 2(12) -> 010
 3 -> 10, 111 degrees -> 1, so 3(111) -> 101
 6 -> 0, 98 degrees -> 01, so 6(98) -> 001

Giving 010101001 169 for 3 throws.

Since number and rotations should both be random variables, the distribution is uniform, unbiased and random. The good thing is rotational distinctions between upper lower half, and all four quadrants are almost as easy to distinguish with the naked eye as the numbers themselves. Though on the boundaries there will be some error and bias, introducing a small additional noise into the signal.

Effectively this procedure amounts to the following : roll the die measuring its number and quadrant of rotation, and discard 1 bit of the quadrant information for the numbers {2,3,4 and 5}.