I'm reading a book called A Practical Guide to Quantitative Finance Interview, and got the following question and its corresponding solution, since I cannot make sense of the solution, so I really appreciate your advice.
Question:
You are given a fair coin. Can you design a simple game using the fair coin So that your probability of winning is $p$?
Solution:
The key to this problem is to realize that $p$ can also be expressed as the binary number. And each digit of the binary number can be simulated using a fair coin. First, we can express the probability $p$ as binary number: $p=0.p_1p_2...p_n = p_12^{-1}+p_22^{-2}+...+p_n2^{-n}$,$p_i$ can be either 0 or 1. Then we can start tossing the fair coin, and count heads as $1$ and tails as $0$. Let $s_i$ be the result of the $ith$ toss starting from $i=1$. After each toss, we compare $p_i$ with $s_i$ and $s_i$ can be either 0 or 1. If $s_i<p_i$, we win and the coin tossing stops. If $s_i>p_i$, we lose and the coin tossing stops. If $s_i=p_i$, we continue to toss more coins. Some $p$ values (ex.$1/3$) are infinite series when expressed as a binary number. In these cases, the probability to reach "$s_i$ Not Euqal To$p_i$" is 1 as $i$ increases. If the sequence is finite (ex.$1/4$), and we reach the final stage with $s_n=p_n$, we lose(ex. for $1/4$, only the sequence 00 will be classified as win; all other sequences 01,10,11 are classifies as loss). Such a simulation will give us probability $p$ of winning.
I highlighted my doubts in bold above, basically I cannot understand those cases like why "If $s_i<p_i$, we win", "If $s_i>p_i$, we lose", "we reach the final stage with $s_n=p_n$, we lose"?
Could any expert give me some guidance?
To make it a bit clearer: The game is designed so that winning sequences correspond to each fractional power of two in the binary decomposition of p. So, to elaborate:
Imagine some fraction that is a pure sum of $2^{-i}$, like p=5/8 or p=3/8. First, you are representing p (in decimal) as a sum: $$ p = \sum_{i}\bigg(\frac{1}{2}\bigg)^i = 1/2 + 1/4 + 1/8 \cdots $$ Essentially, from the rules of the game, you win anytime you get a sequence ending in 0 and lose otherwise. So your winning sequences look like:
Essentially you are winning precisely for sequences that have probability 1/2, 1/4, 1/8, etc.
Okay, so what if you have something like 0.101 = 0.625? Well the a similar principle applies. We win for sequences 0 and 100, which have 1/2 and 1/8 chance of occurring, which still gives us the same probability.