3
$\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$
5
  • 2
    $\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, 2014 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$ Jun 12, 2014 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, 2014 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$ Jun 12, 2014 at 22:04
  • 1
    $\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, 2014 at 22:10

2 Answers 2

4
$\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$
0
$\begingroup$

Certain or almost certain?

We can answer this question by mapping sequences of coin flips to numbers between 0 and 1, as explained by whuber’s comment on the question. Specifically, we can map an infinite sequence of coin flips to a binary representation of a number in $[0, 1)$ by doing the following:

  1. Start with a binary point (the binary equivalent of a decimal point).
  2. For each coin flip, write $1$ if the result is “heads” and $0$ if the result is “tails”.

Then flipping a coin infinitely many times is essentially equivalent to throwing a dart at the interval $[0, 1)$ and the original question is essentially equivalent to: “Are we certain, or merely almost certain, that the dart will not land on $0$?” As explained in the unit square analogy quoted in the question, the answer is almost certain.

For the sake of completeness, this analogy has a slight flaw (which does not affect the argument above). While the mapping to binary representations is bijective, the mapping to actual numbers is not bijective. Specifically, each dyadic rational has two binary representations.

Flaw in the reasoning

If almost certain, then what is the flaw in the reasoning of the thought experiment?

That reasoning depends on the second scientist reporting “true”. The reasoning claims that there is no flow through the flow chart with any result other than “true”. This is correct – assuming there is a result at all. The flow chart contains a loop that only terminates when the result of the coin flip is “heads”, but there is no guarantee that this will ever happen, and therefore no guarantee that the flow chart will produce a result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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