How to explain this paradox involving coin-tosses?

Question

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?

Answer 1

You are wrong about your probability of winning at the beginning.

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.

Answer 2

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}}$$

Answer 3

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.

Answer 4

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 n^th 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.

Answer 5

What went wrong with your reasoning?

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