## A Fair Coin, An Unfair Game

Suppose you have an unbiased coin (i.e a coin with equal probability of landing heads or tails) but would like to construct an outcome of biased probability $p$, how would you do it?

I remember this question (or something along these lines) being asked in a hiring interview where I used to work, using $p = \frac{1}{3}$.

I’m not entirely sure what the expected answer was, but I believe they wanted candidates to answer something like “No, it is not possible because…”.

Presumably people would have argued that the closest thing you can get to $p = \frac{1}{3}$ is to flip the coin $2$ times:
If you hit Heads two times then the outcome is positive,
If you hit Heads and Tails (in either order) then the outcome is negative,
If you hit Tails two times then you repeat the procedure,
arguing that this procedure could repeat itself indefinitely so that it would be impossible to construct this outcome because you might be flipping the coin forever.
Although this does not exclude the possibility of a different working strategy it would probably have demonstrated enough analytical thinking for the interview exercise given the role the person was interviewing for.

I think this raises an interesting question because it sort of comes back to a popular philosophical debate about the essence of probability. What do we mean by “impossible” in this case? How likely is it that the procedure will continue forever?

A quick check will reveal that the probability of the procedure continuing up until the $(2n)^{th}$ coin toss is $(\frac{1}{4})^n$. So the probability that the coin is tossed forever is $lim_{k \rightarrow \infty} (\frac{1}{4})^k = 0$.

So the question is, what is the meaning of probability $0$?
Does it mean the procedure must stop eventually, in which case the expected answer should be “Yes, it is possible because…”? Or can an event of probability $0$ actually happen? Must an event of probability $1$ happen?

Mathematicians have assigned a special (and wonderfully vague) term to describe this phenomenon. They would say here that the procedure will almost surely not continue forever.

Therefore a more accurate answer to the question would be “Yes, one can construct this outcome almost surely” (i.e with probability 1).

To understand the difference between “surely never” and “with probability $0$” the standard metaphor is to consider a dart board. What is the probability of hitting any particular point with a dart?
In this continuous setting we are asking what the probability is of hitting any one out of infinitely many points. The probability of that happening is zero of course. On the other hand the dart must hit the board somewhere (assuming you don’t miss). The point landed on by the dart had probability zero of being hit, and yet it just happened. So in this case hitting any particular point will almost surely never happen. On the other hand if something surely never happens, then it has the intuitive meaning one would associate with the word ‘never’ i.e that the event is not in the sample space so we can’t even begin to assign a probability to it (impossible in other words).

Interestingly one can use a fair coin to construct any outcome of probability $p$ with probability $1$.

Problem (The Car Conundrum):

Suppose you and a friend play the lottery together and manage to win a car.
You paid a fraction $p > \frac{1}{2}$ of the lottery ticket and your friend the rest (i.e $1-p$).
Both of you have a claim on the car but only one of you can own it and it needs to be declared on the spot.
You only have a regular unbiased coin in your pocket to aid you.

How do you settle this fairly?

Solution:

To settle this fairly you should play an unfair game, biased in proportion to the amount each person contributed to the purchase of the winning lottery ticket.

So this is exactly the problem we have been discussing.

Let $I(n) = \begin{cases} 1, & if\;\;n^{th}\;toss\;is\;a\;Head \\ 0 & if \;\;n^{th}\;toss\;is\;a\;Tail \end{cases}$

Write $p$ in binary decimal form say, $p = 0.d_1d_2d_3... = \sum_{n=1}^{\infty} d_n2^{-n}$ where $d_i \in \{0,1\} \forall i$.

Now keep on tossing the coin as long as $I(n) = d_n$.

Suppose for the first time, on the $N^{th}$ toss, $I(N) \neq d_N$.

Declare yourself a winner if $d_N = 1$ and your friend a winner if $d_N = 0$.

The probability that the procedure is stopped after $n$ tosses is clearly $(\frac{1}{2})^n$.

Thus the probability that the procedure will stop after a finite number tosses is:

$\mathbb{P}( N < \infty ) = \sum_{n=1}^{\infty} (\frac{1}{2})^n = -1 + \sum_{n=0}^{\infty} (\frac{1}{2})^n = -1 + \frac{1}{1-\frac{1}{2}} = -1 + 2 = 1$
(note that the last sum is an infinite geometric series).

Finally since you can only win if $d_n = 1$ we get $\mathbb{P}( You\;Win ) = \sum_{n=1}^{\infty} d_n\mathbb{P}(N = n) = \sum_{n=1}^{\infty} d_n(\frac{1}{2})^n = p$ as required.

Exercise (Surely or Almost Surely? – Easy):

Determine whether the following events happen surely or almost surely.

i) Selecting a number uniformly at random in $[0,1]$ and not getting $\frac{1}{2}$.

ii) Selecting a number uniformly at random in $[0,1]$ and not getting $2$.

iii) (Infinite Monkey Theorem)
A monkey randomly typing the complete works of Shakespeare given infinite amount of time.