Quantitative Analyst · Phone · Probability · reported by a candidate
You have a coin that lands heads with probability 1/3, and you need fair coin flips from it.
- (a) With the standard method (flip twice; HT and TH decide, otherwise repeat), how many biased flips does one fair flip take on average?
Answer and worked solution
Answer: 4.5
Key idea. HT and TH have equal probability, so they make a fair flip; other pairs are discarded.
- P(a pair decides) = 2 × (1/3)(2/3) = 4/9.
- Expected pairs = 9/4; flips = 2 × 9/4 = 4.5.
Check. Wasteful: more than 4 biased flips per fair one.
- (b) Follow-up: if you need many fair flips, what is the best possible number of fair flips per biased flip, in the long run?
Answer and worked solution
Answer: 0.9183
Key idea. Each biased flip contains H(p) bits of randomness, and a fair flip needs exactly 1 bit.
- H(1/3) = (1/3) log₂ 3 + (2/3) log₂(3/2) ≈ 0.528 + 0.390.
- ≈ 0.918 fair flips per biased flip, the best possible in the long run.
Check. Schemes that recycle the discarded pairs (Elias, Peres) approach this bound; plain von Neumann gets only 1/4.5 ≈ 0.22.
Source: Wall Street Oasis: D. E. Shaw interview reports · Try it in the app →