Skip to content

Winning with any probability using a fair coin

Question

You only have a fair coin. Describe a game, played with that coin, that you win with probability exactly pp, where p∈(0,1)p\in(0,1) is any given number.

Short answer

Compare random binary digits with the binary expansion of pp. Write p=0.p1p2p3…p=0.p_1p_2p_3\ldots in base 22 and treat flip ii as a digit sis_i (heads =1=1). Stop at the first ii where si≠pis_i\ne p_i; you win if si<pis_i<p_i. The flips form a uniform number UU, you win exactly when U<pU<p, and the game takes 22 flips on average.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 7.2 The Power of Two, 'Probability simulation', p.181; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Basic Statistics and Regression is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free