Can we simulate a biased coin with fair die?

Question

Given a fair 6-sided die, how can we simulate a biased coin with P(H)= 1/$\pi$ and P(T) = 1 - 1/$\pi$ ?

Answer 1

A fair die can obviously simulate a fair coin, so it suffices to show that a fair coin can simulate a biased one. There's a simple way to do so.

Write $p$, the desired (biased) probability of getting Heads, in binary, with $.111\ldots$ if the probability is $1$. Now toss the fair coin until the result of the $n$th toss matches the $n$th binary digit of the desired probability, with Heads matching $1$ and Tails matching $0$. The probability that the concluding toss is Heads is $p$, so this procedure simulates the biased coin.

Curiously, no matter what kind of bias you're trying to simulate, it takes, on average, just two tosses to carry out the simulation.

Added later: In case it's not clear that the simulation terminates at Heads with the target probability $p$, let me illustrate with an example.

Suppose the target probability is $p=.001011\ldots$. Then the simulation will terminate with Heads as the first match if and only if the first match occurs either on the third toss or the fifth toss or the sixth toss or any subsequent occurrence of a $1$ in the binary expansion of $p$. These are mutually exclusive events, since the first match, by the meaning of "first," can only occur once.

For the first match to occur on the third toss, the first two tosses must have been mismatches and the third toss a match. Since we're tossing a fair coin, this happens with probability

$${1\over2}\cdot{1\over2}\cdot{1\over2}={1\over8}=.001$$

(in binary). Likewise, the probability that the first match occurs on the fifth toss is

$${1\over2}\cdot{1\over2}\cdot{1\over2}\cdot{1\over2}\cdot{1\over2}={1\over32}=.00001$$

the probability it occurs on the sixth toss is

$${1\over2}\cdot{1\over2}\cdot{1\over2}\cdot{1\over2}\cdot{1\over2}\cdot{1\over2}={1\over64}=.000001$$

and so forth. Thus the probability of getting Heads as the first match is the sum

$$.001+.00001+.000001+\cdots=.001011\ldots=p$$

Answer 2

Well, here's an (approximate) way to do it: write P as a "hex-decimal" in base$_6$. Then toss your die repeatedly forming a hex-decimal. (if you throw a "6" mark it as "0"). A Win comes if the hex-decimal produced by the die is less than P.

Of course, it is theoretically possible that this takes an arbitrarily long set of tosses (hence the "approximate").

Answer 3

Throwing a dice $n$ times gives you a space of $6^n$ outcomes, so take an $n$ so that you can approximate $\frac{1}{\pi}$ by $\frac{m}{6^{n}}$ as precisely as required.

After this just pick $m$ of the $6^m$ results to represent heads and the other results represent tails.

The probability of getting tails is very close to $\frac{1}{\pi}$ (you can make it as close as you want).