Solved – Getting heads in an infinite series of coin flips- certain or almost certain

probability

A while ago I was introduced to the idea of something with probability happening "almost certainly", (or "almost surely"). Conceptually as I understand it, the probability of an event may be 1, but that does not mean it is certain, only almost certain. Wikipedia gives this example, based on throwing a dart at a square:

Consider the event that "the dart hits the diagonal of the unit square exactly". The probability that the dart lands on any subregion of the square is proportional to the area of that subregion. But, since the area of the diagonal of the square is zero, the probability that the dart lands exactly on the diagonal is zero. So, the dart will almost never land on the diagonal (i.e. it will almost surely not land on the diagonal). Nonetheless the set of points on the diagonal is not empty and a point on the diagonal is no less possible than any other point, therefore theoretically it is possible that the dart actually hits the diagonal.

So my basic question is: if I flip a fair coin an infinite number of times, am I certain, or merely almost certain, to get heads at least once?

Thought experiment

My initial reaction to the question was that the answer must be almost certain. However, I came up with a thought experiment which made me doubtful:

Two immortal scientists are tasked with monitoring a fair coin which will flip once a minute. They both share the same coin, but are given different instructions.

The first scientist's instructions are: If the coin has not come up heads after infinite flips, report "false". If the coin comes up heads on any single flip, report "true".

The second scientist is given this flow chart to describe what he should do:

coin flipping

Given this, I would say the following:

There is clearly no flow through the second scientist's diagram where there is any possible result apart from "true".
There is no sequence of coin flips where, at any point either:
- The two scientists report different results OR
- One scientist has reported a result while the other is still yet to report a result.

The first of those points seems to mean that it is certain, rather than almost certain, that the second scientist will report true. The second of those points seems to mean that the second scientist being certain to report true implies that the first scientist is certain to report true.

Putting those together, the first scientist is certain to report true, giving a counterintuitive answer to the basic question.

So to wrap up, is it certain or almost certain that an infinite series of flips of a fair coin will result in heads at least once? If certain, then what's the explanation for that counterintuitive result given that there's nothing forcing any single coin to come up heads? If almost certain, then what is the flaw in the reasoning of the thought experiment?

Best Answer

I believe there is a subtle issue in your analogy. The first scientist may never talk, as there is no such thing as "after" an infinite number of flips. Nevertheless, neither scientist is certain to report true, they can still be waiting for ever and ever and ever...

Thus, both are "almost certain".

Related Solutions

Solved – Statistics concept to explain why you’re less likely to flip the same number of heads as tails, as the number of flips increases

Note that the case where the number of heads and the number of tails are equal is the same as "exactly half the time you get heads". So let's stick to counting the number of heads to see if it's half the number of tosses or equivalently comparing the proportion of heads with 0.5.

The more you flip, the larger the number of possible counts of heads you can have -- the distribution becomes more spread out (e.g. an interval for the number of heads containing 95% of the probability will grow wider as the number of tosses increases), so the probability of exactly half heads will tend to go down as we toss more.

Correspondingly, the proportion of heads will take more possible values; see here, where we move from 100 tosses to 200 tosses:

With 100 tosses we can observe a proportion of 0.49 heads or 0.50 heads or 0.51 heads (and so on -- but nothing in between those values), but with 200 tosses, we can observe 0.49 or 0.495 or 0.50 or 0.505 or 0.510 - the probability has more values to "cover" and so each will tend to get a smaller share.

Consider than you have $2n$ tosses with some probability $p_i$ of getting $i$ heads (we know these probabilities but it's not critical for this part), and you add two more tosses. In $2n$ tosses, $n$ heads is the most likely outcome ($p_n>p_{n\pm 1}$ and it goes down from there).

What's the chance of having $n+1$ heads in $2n+2$ tosses?

(Label these probabilities with $q$ so we don't confuse them with the previous ones; also let P(HH) be the probability of "Head,Head" in the next two tosses, and so on)

$q_{n+1} = p_{n-1} P(HH) + p_n (P(HT)+P(TH)) + p_{n+1} P(TT)$

$\qquad < p_{n} P(HH) + p_n (P(HT)+P(TH)) + p_{n} P(TT) = p_n$

i.e. if you add two more coin-tosses, the probability of the middle value naturally goes down because it averages the most likely (middle) value with the average of the smaller values either side)

So as long as you're comfortable that the peak will be in the middle (for $2n= 2,4,6,...$), the probability of exactly half heads must decrease as $n$ goes up.

In fact we can show that for large $n$, $p_n$ decreases proportionally with $\frac{1}{\sqrt{n}}$ (unsurprisingly, since the distribution of the standardized number of heads approaches normality and the variance of the proportion of heads decreases with $n$).

As requested, here's R code that produces something close to the above plot:

 x1 = 25:75
 x2 = 50:150
 plot(x1 / 100, dbinom(x1, 100, 0.5), type = "h",
       main = "Proportion of heads in 100 and 200 tosses",
       xlab = "Proportion of heads",
       ylab = "probability")
 points(x2 / 200, dbinom(x2, 200, 0.5), type = "h", col = 3)

Solved – When can I expect to get 5 heads in a row when tossing a coin

I couldn't follow your derivation, but I believe the correct way to solve the problem is as follows.

First, some notation: take $x_i$ to be the expected number of flips to reach the end state ($n$ consecutive heads or $n$ consecutive tails), given that we're on a "run" of exactly $i$ consecutive flips of heads. Similarly, take $y_i$ to be the expected number of flips to reach the end state, given that we're on a run of exactly $i$ consecutive flips of tails. Clearly, $x_n = y_n = 0$, since if we've already had $n$ consecutive heads or tails, we're done.

Then, we're interested in finding $x_0$ ($= y_0$). The relevant equations are (for $i < n$):

\begin{equation} \begin{split} x_i & = (1-p)(1 + y_1) + p(1 + x_{i+1}) \\ y_i & = p(1 + x_1) + (1-p)(1 + y_{i+1}) \end{split} \end{equation}

Let's derive the first equation (the second one is analogous). Suppose we're on a run of $i$ heads. We want to find the expected number of flips to end the game, which is $x_i$. Let's take our next flip. There's a probability $p$ that it comes up heads, which means we now have a run of $i+1$ heads. That's the second term on the right-hand-side of the equation: there's a probability of $p$ of moving from the state with $i$ consecutive heads to the state with $i+1$ consecutive heads, and it costs 1 flip in order to do so. There's also a probability $1-p$ that it comes up tails, in which case we have a run of only 1 tail. That's the first term on the right-hand-side of the equation: there's a probability of $1-p$ of moving from the state with $i$ consecutive heads to the state with 1 consecutive tail, and it costs us 1 flip in order to do so.

With these equations you can solve the problem for any $n$. I tried implementing this in Mathematica, and if $p = 0$ or $p = 1$, I indeed get that $x_0 = y_0 = n$, as expected. ~~I'm not sure if there's any closed form solution to the equations for arbitrary $n$; that's probably a question for the Math StackExchange.~~ (Edit: see derivation below for the solution for arbitrary $n$).

What I've sketched out here is a general approach for solving many types of coin flipping problems (and other problems). It essentially constructs a Markov chain that has states (e.g., 3 consecutive heads), and transition probabilities for moving between states (e.g., a probability of $1-p$ of moving from 3 consecutive heads to 1 tail). The absorbing states are the end states of the game. See, for instance, the answer to this question.

EDIT: For the particular case of $n=5$, I get (using Mathematica):

\begin{equation} x_0 = \frac{(5 - 10p + 10p^2 - 5p^3 + p^4)(1 + p + p^2 + p^3 + p^4)}{1 - 4p + 6p^2 - 4p^3 + p^4 + 4p^5 - 6p^6 + 4p^7 - p^8} \end{equation}

which seems to have the right limits (although it's possible I have a typo somewhere).

Edit #2: Following @whuber's advice, I solved the recurrence relation for general $n$. The solution is:

\begin{equation} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} = (A + B)[(I-A^{n-1})^{-1}(I-A)-B]^{-1}c + c \end{equation}

where \begin{equation} A = \begin{bmatrix} p & 0 \\ 0 & 1-p \end{bmatrix} \end{equation}

and

\begin{equation} B = \begin{bmatrix} 0 & 1-p \\ p & 0 \end{bmatrix} \end{equation}

and

\begin{equation} c = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{equation}

and $I$ is the identity matrix. For $n=5$, this gives the same result as above.

Best Answer

Related Solutions

Solved – Statistics concept to explain why you’re less likely to flip the same number of heads as tails, as the number of flips increases

Solved – When can I expect to get 5 heads in a row when tossing a coin

Related Question