Tossing coins

Simulate a biased coin with a fair coin

The following algorithm simulates a biased coin with head probability 0<p<1, using a random number generator toss_coin that returns 0 and 1 with equal probability.

// Pre-condition: p is a rational number and 0 < p < 1
while (true) {
    var p = p * 2,
    var p2 = p - floor(p);
    var msb = p - p2;
    var random_bit = toss_coin(); // 0 or 1
    if (random_bit < msb) {
        print "head";
        break;
    }
    if (random_bit > msb) {
        print "tail";
        break;
    }
    p = p2;
}
// Post-condition: "head" is outputted with probability p
//                 "tail" is outputted with probability 1-p

To see why it works, consider a random number 0 < r < 1 generated by enumerating its binary representation with a fair coin. Observe that given 0 < p < 1, the probability that 0 < r < p is exactly p. The algorithm then enumerates p and r, digit by digit, and determines the return value according to the following fact: r < p if and only if r_i < p_i for some i and r_j = p_j for all j < i, where x_k denotes the kth digit in the binary representation of x.

The following code fragment is adapted from the book Abstraction, Refinement and Proof for Probabilistic Systems, A McIver, C Morgan, 2005. Succinct as it is, its behavior is not as straightforward to understand as the above one and we skip the analysis of its correctness.

// Pre-condition: p is a rational number and 0 < p < 1
var x = p;
while (toss_coin() == 1) {
    x = 2 * x;
    if(x > 1){
      x = x - 1;
    }
}
// Post-condition: x > 0.5 with probability p
print x > 0.5 ? "head" : "tail";

Simulate a fair coin with a biased coin

while (true) {
    var a = toss_biased_coin();
    var b = toss_biased_coin();
    if(a == b){
      print a == 1 ? "head" : "tail";
      break;
    }
}

The expected running time is $\frac{2}{1-2p(1-p)}$.

Checking whether a coin is fair

First, note that it is impossible to rule out arbitrarily small deviations from fairness such as might be expected to affect only one flip in a lifetime of flipping. Also, it is always possible for a biased coin to happen to turn up exactly 10 heads in 20 flips. As such, any fairness test must only establish a certain degree of confidence in a certain degree of fairness (a certain maximum bias). In more rigorous terminology, this problem can be viewed as a special case of determining the parameters of a Bernoulli process, given only a limited sample of Bernoulli trials.
Suppose that there are $h$ heads and $t$ tails in an experiment of $n=h+t$ tosses. The best estimator for the actual head probability $p$ is $$q=\frac{h}{h+t}.$$ One can associate this estimator with a margin of error $\epsilon$ at a particular confidence level, which is given by the Z-value of a standard normal distribution in the following sense: $$P\{|p-q|\le z\sigma\}=P\{|Z|\le z\},$$ where $\sigma$ is the standard deviation of error of the estimate and $Z$ is a standard-normal distributed random variable. For $n$ Bernoulli trials, the standard deviation is $$\sigma=\sqrt{\frac{p(1-p)}{n}}\le\frac{1}{2\sqrt n}.$$ Hence, suppose that $P\{|Z|\le z\}=c$ then we have $$P\{|p-q|\le \frac{z}{2\sqrt n}\}\ge c.$$ For example, by looking up the table we see that $z=2.5759$ for $c=99\%$. Suppose now $h=54$ and $t=46$, then the actual head probability $p$ falls into $0.54\pm 0.12879$ at 99% level of confidence.