From Fair Coin To Simulating a $$p$$ Event

You are given a fair coin. Can you design a simple game using the fair coin so that your probability of winning is $$p$$ , where $$0 < p < 1$$ ?

Answer

Let $$p$$ be a fixed value with binary representation

p = 0.p_1 p_2 p_3 \dots, \quad p_i \in \{0,1\}.

Step 1: Use the fair coin (toss it many times) to generate a random variable uniformly distributed on $$(0,1)$$ using its binary representation:
$U = 0.s_1 s_2 s_3 \dots = \sum_{k=1}^{\infty} \frac{s_k}{2^k},$
where each $$s_k$$ is an indicator of the $$k$$ -th toss (1 for heads, 0 for tails).
Step 2: Compare the bits $$s_i$$ and $$p_i$$ sequentially, starting from the most significant bit (leftmost).
- If $$s_i < p_i$$ , you win.
- If $$s_i > p_i$$ , you lose.
- If $$s_i = p_i$$ , continue tossing the coin (or if last digit, we lose).

Why this works: The idea is that since $U \sim \mathrm{Uniform}(0,1)$ aprroximately, the rule above is equivalent to the event $$U < p$$ . Hence,

P(\text{win}) = P(U < p) = p.

Note that in our case we are talking about an approximation of $$U$$ (finite case) hence the " $$<$$ " and not the " $\leq$ ".

Example 1 (finite binary case): Let $p = \tfrac{1}{4} = 0.01_2$ . After two tosses, the possible sequences are $$00, 01, 10, 11$$ , each with probability $$1/4$$ . Only $$00$$ gives $$U < p$$ (since $$00 < 01$$ ), so $P(\text{win}) = 1/4$ .

Example 2 (infinite binary case): Let $p = \tfrac{1}{3} = 0.010101\ldots_2$ . The comparison may continue indefinitely, but the probability that $$U = p$$ exactly is zero. Therefore, $P(\text{win}) = P(U < p) = p = \tfrac{1}{3}$ .

From Fair Coin To Simulating a $p$ Event

From Fair Coin To Simulating a $$p$$ Event