Designing a Probability Game with a Fair Coin

This question considers how to design a simple game driven only by flips of a fair coin so that the probability of winning is exactly some chosen value between zero and one. The setup is algorithmic rather than financial: you want a procedure that consumes unbiased random bits and outputs "win" or "lose" with a controllable, precisely specified win probability. The twist is that the target probability can be any real number in that open interval, not just neat rational values that might be engineered with a finite state machine or small decision tree.

It leans heavily on understanding binary representations of real numbers, how infinite bit sequences map to the unit interval, and how to use that mapping to control probabilities. A strong solution shows comfort with measure-theoretic intuition in a discrete setting, constructions that terminate almost surely, and careful reasoning about edge cases in binary expansions. Interviewers watch for candidates who can turn high-level ideas about random numbers and intervals into a concrete procedure, reason about correctness without hand-waving, and address efficiency and implementability concerns.

What it tests

Any probability $p$ in $(0,1)$ can be uniquely represented as an infinite binary fraction, and random processes (like fair coin flips) can be used to simulate each digit of this expansion. The key is that each coin flip generates an independent, uniformly random bit, so the sequence of coin flips corresponds to a uniformly random number in $[0,1)$. By comparing the coin-generated binary sequence to the binary expansion of $p$ digit by digit, you can decide the outcome in a way that exactly matches the probability $p$. This works because the set of all infinite binary sequences is in bijection with the real interval $[0,1)$, and the comparison process partitions this space according to the value of $p$. Thus, the probability of the coin-generated sequence being less than the binary expansion of $p$ is exactly $p$.