How to Unbias Dice
2025-05-24
---
In 1951, John von Neumann demonstrated a procedure to convert the output of a biased coin (a coin that lands on one side more often than the other) to that of a fair coin. The procedure was quite simple:
- Flip the coin twice.
- If the results match, discard them and start again.
- If the results differ, take the first result.
The procedure assumes that each coin flip is independent (a given flip will not influence future flips) and that the probabilities of each result do not change from one flip to the next.
Why does von Neumann's method work? Suppose a coin yields heads with probability p and tails with probability 1-p. Because each flip is independent and has constant probability, we can find the probabilities of all possible ordered result sets from two flips.
+--------+-------------+ | Result | Probability | +--------+-------------+ +--------+-------------+ | H, H | p^2 | +--------+-------------+ | H, T | p(1-p) | +--------+-------------+ | T, H | p(1-p) | +--------+-------------+ | T, T | (1-p)^2 | +--------+-------------+
Of these result sets, two (HT and TH) include both possible outcomes, but the order differs. Even more importantly, the probability of getting those two sets is equal (p(1-p)). We thus have two equally-probable result sets and a choice function for which outcome to take (the first), and that gives us an unbiased procedure.
A natural question is to ask if we can modify this procedure to work with n-sided dice, or more generally any event with n possible biased outcomes. A post on Gemini discussed the problem last year and even provided a partial solution for 20-sided dice.^ Fortunately, however, the general problem can be answered in a straightforward way, though it becomes quickly impractical for large numbers of outcomes.
Let's extend our test to include three possible results: A with probability p, B with probability q, and C with probability 1-p-q. Our table now looks like this:
+---------+-------------+ | Result | Probability | +---------+-------------+ +---------+-------------+ | A, A, A | p^3 | +---------+-------------+ | A, A, B | qp^2 | +---------+-------------+ | A, A, C | p^2(1-p-q) | +---------+-------------+ | A, B, A | qp^2 | +---------+-------------+ | A, B, B | pq^2 | +---------+-------------+ | A, B, C | pq(1-p-q) | +---------+-------------+ | A, C, A | p^2(1-p-q) | +---------+-------------+ | A, C, B | pq(1-p-q) | +---------+-------------+ | A, C, C | p(1-p-q)^2 | +---------+-------------+ | B, A, A | qp^2 | +---------+-------------+ | B, A, B | pq^2 | +---------+-------------+ | B, A, C | pq(1-p-q) | +---------+-------------+ | B, B, A | pq^2 | +---------+-------------+ | B, B, B | q^3 | +---------+-------------+ | B, B, C | q^2(1-p-q) | +---------+-------------+ | B, C, A | pq(1-p-q) | +---------+-------------+ | B, C, B | q^2(1-p-q) | +---------+-------------+ | B, C, C | q(1-p-q)^2 | +---------+-------------+ | C, A, A | p^2(1-p-q) | +---------+-------------+ | C, A, B | pq(1-p-q) | +---------+-------------+ | C, A, C | p(1-p-q)^2 | +---------+-------------+ | C, B, A | pq(1-p-q) | +---------+-------------+ | C, B, B | q^2(1-p-q) | +---------+-------------+ | C, B, C | q(1-p-q)^2 | +---------+-------------+ | C, C, A | p(1-p-q)^2 | +---------+-------------+ | C, C, B | q(1-p-q)^2 | +---------+-------------+ | C, C, C | (1-p-q)^3 | +---------+-------------+
Six of the 27 result sets above include each outcome once, and any of those sets can occur with equal probability--in this case pq(1-p-q). Among the six sets, the first outcome can be A, B or C with probability 1/3, so if we choose the first outcome among only those sets, we get an outcome of A, B or C with equal probability. This unbiases our outcome set.
The core of von Neumann's method is using the independence of each trial to find result sets that have equal probability. If the test is biased, certain outcomes are more likely than others, so their probabilities are unequal. von Neumann's observation is that if the trials are independent, then the probability of getting each possible outcome exactly once is the same, regardless of order. As each possible order is equally likely, we use the first member of the set as our outcome. In effect, we are replacing the probability of an outcome in isolation with the probability of an outcome appearing first in an ordered list of all outcomes--we are actually using the probability of a different test.
Mathematically, this procedure is perfect, but one major flaw makes it impractical in most real-world scenarios: the number of trials that need to be thrown out is quite large. If a test has n possible outcomes, the number of n-result sets is n^n, and n! of those sets have every outcome exactly once. Suppose the probability of each outcome is p_1, p_2, ... p_n; then the probability of getting each outcome once is n!(product(p_i)), and the probability of getting at least one repeat is 1-n!(product(p_i)). This is probability that a result set will "fail" our criterion of having each result once and will therefore need to be thrown out. The product is maximized when all of the p_i are equal, in which case the probability simplifies to 1-(n-1)!/n^(n-1)--this is the "at best" value. If any p_i and p_j are unequal, the product is smaller, so the probability of a failed result increases.
This value gets large fast. When we only have two outcomes, such as heads or tails, we can expect to throw out at least half of the two-flip result sets, because 1-(2-1)!/2^1=1/2. If the coin is biased 4-to-1 towards heads, we can expect to throw out 1-2!(4/5*1/5)=17/25, or 68%, of the result sets. With three outcomes, we can expect to throw out at least 77.8% of the result sets, and the probability only grows if the outcomes are biased.
Below is a table of 7 tabletop RPG dice and the minimum number of trials one can expect to discard when unbiasing them.
+------+---------------------+----------------------+ | Die | Fraction | Percentage | +------+---------------------+----------------------+ +------+---------------------+----------------------+ | D4 | 29/32 | 90.6% | +------+---------------------+----------------------+ | D6 | 319/324 | 98.4% | +------+---------------------+----------------------+ | D8 | 130757/131072 | 99.6% | +------+---------------------+----------------------+ | D10 | 1561933/1562500 | 99.96% | +------+---------------------+----------------------+ | D12 | 35829883/35831808 | 99.994% | +------+---------------------+----------------------+ | D20 | 639999985150744579/ | 99.999998% | | | 640000000000000000 | | +------+---------------------+----------------------+ | D100 | 1058791184067875423 | 99.99999999999999999 | | | 8354031258495524525 | 99999999999999999 | | | 6423851382338345532 | 9999991% | | | 7285240550335022479 | | | | 3147680428522331962 | | | | 1462371893320319769 | | | | 0416516092467073802 | | | | 3230834021115801188 | | | | 883/ | | | | 1058791184067875423 | | | | 8354031258495524525 | | | | 6423950195312500000 | | | | 0000000000000000000 | | | | 0000000000000000000 | | | | 0000000000000000000 | | | | 0000000000000000000 | | | | 0000000000000000000 | | | | 000 | | +------+---------------------+----------------------+
If one tried to unbias a D100 using von Neumann's procedure and generated a trillion result sets per second, it would take an amount of time at least a trillion times longer than the age of the universe to produce a single unbiased result. Clearly this won't be useful at your next Dungeons and Dragons session.
---
[Last updated: 2025-05-24]