Skip to content
HTQHow To Quant
← Problem Bank

Probability Simulation

CalcMedium~20 min· Algorithms
Problem

You have a fair coin. You want to simulate a biased "coin" that comes up heads with probability for any whose binary expansion you can produce.

A.

For , describe an algorithm using only fair coin flips.

B.

Generalise: given any , give a procedure that outputs "heads" with probability and "tails" with probability , using a finite expected number of fair coin flips.