2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This might be insightful: every sequence of heads and tails corresponds to a unique number between $0$ and $1$ by encoding the heads as 1, the tails as 0, and putting a binary point in front of the sequence. Any infinite coin flip thereby is tantamount to throwing a dart at the line segment from $0$ to $1$. Never getting a head is the same as hitting the $0$ at the end of the segment. As in the two-dimensional dartboard case, this event is possible but its probability is zero. $\endgroup$ – whuber Jun 12 '14 at 21:51
  • $\begingroup$ @whuber Yep, I'm aware that the set of infinite binary sequences has a bijection into the reals. That's part of the reason that to me the "intuitive" answer is almost certain $\endgroup$ – Ben Aaronson Jun 12 '14 at 21:53
  • $\begingroup$ Careful: it's not a bijection! But it still helps the intuition and avoids the mistakes and contradictions made in talking about "after infinite flips" and trying to diagram such a process with a finite flow chart. $\endgroup$ – whuber Jun 12 '14 at 22:01
  • $\begingroup$ @whuber I thought it was a bijection... at least into a finite interval of the reals, not the whole set. I agree that "after infinite flips" is clumsy terminology, I couldn't think of a better way to phrase it. I'm afraid it hasn't given me any additional insight into why a flow chart is inappropriate, though $\endgroup$ – Ben Aaronson Jun 12 '14 at 22:04
  • $\begingroup$ A flow chart can never get to infinity. Interestingly, the sequence --> real number map is a bijection except on a set of probability zero (the sequences corresponding to the dyadic rational numbers). For instance, .1000... (one head followed by all tails) and .0111... (one tail followed by all heads) both map to $1/2$, but only the sequence .010100010111110011000001101101110010011100100010000... maps to $1/\pi$. $\endgroup$ – whuber Jun 12 '14 at 22:10
3
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.