# How to explain this paradox involving coin-tosses?

I do this experiment: I flip fair coin, if it comes heads on first toss I win. If it comes tails, I flip it two times more and if both heads I win. Else, I flip it 3 more times, if it comes heads all three I win. On the n'th turn I flip it n times, and if I get n heads I win and quit the game.

Before I start, I calculate probability I win at some point: 1/2+1/2^2+1/2^3... = 1. So I am guaranteed to win this game always.

However I started to play, and it came tails first toss, now I calculate probability I win 1/2^2+1/2^3+1/2^4...=1/2.

Before I start I was guaranteed to win, but now only 50% chance I will win? What went wrong with the mathematical reasoning?

-
Why do you think the series 1/2+1/2^2+1/2^3... is related to the probability to win at some point? – Did Jan 4 '12 at 16:28
You can't add up the $1/2+1/2^2 + 1/2^3...$ because they are not disjoint events. You win on round $1$ with probability $1/2$. The probability that you win on round $2$ is the probability that you lost on round $1$ times the probability that you win on round $2$, which is $\frac{1}{8}$, not $\frac{1}{4}$. – Thomas Andrews Jan 4 '12 at 16:31
Please revise the title: it does not reflect the nature of the "paradox" that you describe. A more neutral title would be more useful. – Niel de Beaudrap Jan 4 '12 at 16:36
I wrote an answer (now deleted) without reading the description of the experiment carefully. It turns out there are two problems in your argument: (1) There seems to be some confusion between conditional probability and the probability of conjunction of events. (2) As is pointed out by the other answers, even your first probability calculation is off; this is already explained by them nicely, so I will skip the details. (I had missed this item (2) on my first reading of the question, so my answer focused only (1).) – Srivatsan Jan 4 '12 at 16:37
+1 for @Niel's comment. I edited the title appropriately; feel free to improve it. – Srivatsan Jan 4 '12 at 19:00

Let $p_n$ be the probability that you have not won by stage $n$.

Then the probability that you have will not have won at stage $n+1$ is $p_n(1-(\frac{1}{2})^{n+1})$.

So the probability that you never win is $\prod_{n=1}^\infty (1-(\frac{1}{2})^n)$. This is not zero.

Specifically, this is $\phi(\frac{1}{2})$ where $\phi$ is the Euler function.

In particular, $$\log(\phi(\frac{1}{2}))=-\sum_{n=1}^\infty \frac{1}{n}\frac{1}{2^n-1}$$

which converges.

-

Your calculation that you are guaranteed to win is incorrect. Let "$\ast$" stand for any sequence of events following the last one described in a sequence; and group together coin-flips into pairs, triples, etc. depending on whether they will be used to decide success. We have: $$\Pr(H,~\ast) = \frac{1}{2}$$ $$\Pr(\textrm{not}~H,~(H,H),~\ast) = \tfrac{1}{2} \cdot \tfrac{1}{4} = \frac{1}{8}$$ $$\Pr(\textrm{not}~H,~\textrm{not}~(H,H),~(H, H, H),~\ast) = \tfrac{1}{2} \cdot \tfrac{3}{4} \cdot \tfrac{1}{8} = \frac{3}{64}$$ $$\Pr(\textrm{not}~H,~\textrm{not}~(H,H),~\textrm{not}~(H,H,H),~(H,H,H,H),~\ast) = \tfrac{1}{2} \cdot \tfrac{3}{4} \cdot \tfrac{7}{8} \cdot \tfrac{1}{16} = \frac{21}{1024}$$ and so on, so that the probability of success at exactly the nth trial is $$2^{-n} \prod_{j=1}^{n-1} \Bigl(1 - \tfrac{1}{2^j}\Bigr) .$$ The sum of these will be less than 1, and indeed your probability of ever succeeding will diminish if you do not succeed early.

-

Let's introduce a bit of problem-specific notation. For $n\in \mathbb{N}$, let $H_n$ denote the event that you won on the $n^{th}$ set of coin flippings (ie $H_1$ denotes the event of flipping a coin and getting heads, $H_2$ denotes the event of flipping a coin and getting tails, then flipping twice more and getting two heads, etc).

You're correct in that the probability of winning is

$$\sum\limits_{n=1}^\infty P(H_n)=P(H_1)+P(H_2)+\cdots$$

Now, clearly $P(H_1)=\frac{1}{2}$. However, $P(H_2)$ is the probability of flipping (in order) one head followed by two tails. So, $P(H_2)=\frac{1}{8}$.

Here's where things get complicated...to achieve the event of $H_3$, the first flip is tails, the next two flips cannot be two heads, and the next three flips must be tails. So, $P(H_3)=\frac{1}{2}\cdot \frac{3}{4} \cdot \frac{1}{8}=\frac{3}{2^6}$.

To achieve $H_4$, the first flip must be a tails, the next two can't both be heads, the next three can't all be tails, and the next four must be all heads. So: $P(H_4)=\frac{1}{2}\cdot \frac{3}{4}\cdot \frac{7}{8}\cdot \frac{1}{16}=\frac{21}{2^{1+2+3+4}}$.

Following the same argument, it shouldn't be too tough to show that

$$P(H_n)=\frac{1}{2}\cdot \frac{3}{4}\cdots \frac{2^{n-1}-1}{2^{n-1}}\cdot \frac{1}{2^n}=\frac{1\cdot3 \cdot 7 \cdots (2^{n-1}-1)}{2^{n(n+1)/2}}$$

-

So you have a $.5$ probability to win on the first toss. You then have a $.5$ probability of going tails, and then a $.5^2$ probability to get heads twice in a row to win. So the probability that you'll win by the second attempt is $.5 + .5\cdot .5^2 = .5 + .5^3 = .5 (1 + .5^2)$.

But now it's a bit more complicated. There are a few ways not to get those two heads in a row. Perhaps you got THT, TTT, or TTH. In all of these, you would have to go on to the next (third) attempt.

If we look at this a bit more, though, we can still calculate it. So suppose we got T at first. We flip it twice and don't get HH. Although we could just count the number of ways this is possible, let's do it in a more general way. This is sort of like counting the number of binary strings of length 2, excluding HH. So we get $2^2 - 1 = 3$. Good.

So the probability of winning on the third attempt $3(.5^3)\cdot (.5^3) = (\text{number of ways this could happen})(\text{probability of each})(\text{probability of HHH})$. This corresponds to the sum of the probabilities of THTHHH, TTHHHH, and TTTHHH. So the probability of winning by the third attempt is $.5 + .5^3 + 3\cdot .5^6$.

In short, the initial probability is incorrect.

-

What went wrong with your reasoning?

"Before I start..." is not the same as "now (i.e. AFTER you have started)"!

-
Admittedly, I should have elaborated a bit, but I went with the "less is more" approach. Sometimes it works! In any case, there's no need to be rude. @Holowitz – The Chaz 2.0 Jan 6 '12 at 0:36