Question

Suppose we have a means of generating independent fair coin flips. We want to simulate a biased coin that comes up heads with probability `p`.

  1. Give an algorithm to simulate such a coin. Assume that `p` is given in binary notation, this notation describing p may possibly be infinite if `p` is irrational.
  2. Estimate the expected number of flips of a fair coin per a simulated flip of the biased one.

Answer

  1. Assume that 0 is shown with probability `1-p` and 1 is shown with probability `p`.

    Algorithm.

    Let binary representation of `p` is 0. `p_1,p_2,p_3...`.

    Repeat for `i=1,2,3...`.

    1. Flip a coin - obtain `X_i`.

    2. If `p_i=1` and `X_i=0`, stop and output 1.

    3. If `p_i=0` and `X_i=1`, stop and output 0.

  2. Notice, that on each iteration algorithm stops if `X_i!=p_i`. This happens with probability of `1/2`. Therefore `n` iterations will be performed with probability `1/2^n`. So, expected number of iterations (flips) is `E(X)=sum_(n=1)^oon/2^n=2`.

    Answer: 2.