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 , where is any given number.
Short answer
Compare random binary digits with the binary expansion of . Write in base and treat flip as a digit (heads ). Stop at the first where ; you win if . The flips form a uniform number , you win exactly when , and the game takes 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 solutionLessons behind this question
- Sample Spaces, Events, and the Probability Axioms
- Applications — Monte Carlo Estimation, Error, and Confidence Intervals
- Taylor and Maclaurin Series
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