Abrazolica

It's fairly easy to simulate a fair coin with a biased coin. See Coin Tossing: the Hydrogen Atom of Probability for a simple way to do it. But how do you turn a fair coin into a biased coin?

If you have a perfectly fair coin, \(P(H)=P(T)=1/2\), you can use it to simulate a biased coin with \(P(H)=\alpha\), \(P(T)=1-\alpha\). To see how let's first look at how to do it using a uniform random variable (URV). Let the URV have the following probability density function:

\[\begin{align} p(x) & = 1\;\;\; 0 \le x \lt 1\nonumber\\ & = 0\;\;\; \mbox{otherwise}\nonumber \end{align}\]

The cumulative distribution then says that \(P(x<\alpha)=\alpha\) and \(P(x\ge \alpha)=1-\alpha\). So the process is simple. Generate a random variate with this distribution. If \(x<\alpha\) take the result to be \(H\) otherwise take it to be \(T\).

You can mimic this process with a fair coin if you let \(H=0\), \(T=1\) and take the result of a toss sequence to be a fractional binary number. For example, the toss sequence \(HTHTT\) converts to the fractional binary number \(.01011\) which is equal to the decimal number \(1/4+1/16+1/32=11/32=0.34375\). If we were using this to simulate a biased coin with \(P(H)=1/3\), \(P(T)=2/3\) then at this point we could stop and output a \(T\) since the binary number will always stay above \(1/3\) no matter what the subsequent tosses are.

Suppose on the other hand that the toss sequence is \(HTHH\) which converts to \(.0100\) with decimal value \(1/4=0.25\). In this case we can stop and output a \(H\) since the binary number will always stay below \(1/3\) no matter what the subsequent tosses are. The same would be true if the toss sequence started as \(HH\). There is no way this can lead to a binary number greater than \(1/3\) so we can stop and output a \(H\).

This procedure can be used to simulate a biased coin with probability \(P(H)=\alpha\), \(P(T)=1-\alpha\). The basic algorithm is as follows. Let \(x\) be the probability we want to simulate, and \(y\) be the value of the toss sequence converted into a binary number. Then

1  input(x)
2  y = 0
3  i = 1
4  gettoss(t)
5  y = y + t/2^i
6  if y >= x
     output(1)
     goto 2
7  if x > y + 1/2^i
     output(0)
     goto 2
8  i = i + 1
9  goto 4

A C code implementation of this can be found here. It reads a string of \(1\)'s and \(0\)'s representing a fair coin toss sequence, and converts it into a string of \(1\)'s and \(0\)'s representing a biased coin with a probability of \(0\) given on the command line.

Using this program, we took data from the NIST randomness beacon that is supposed to be totally random, i.e. \(P(0)=P(1)=1/2\), and converted it using the C program linked to above to data with bias probabilities from \(0.0\) through \(1.0\) in increments of \(0.01\). For each bias, we took the first \(90000\) bits and created a \(300\) by \(300\) pixel image. All the images were then combined into the animated gif shown below.