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.