PG6.4 Uncountable sets, and infinitely many coin tosses

Simulate

Check the claim with numbers

Toss a coin for ever, and record the result as an infinite sequence of H and T, such as $HTTHH\ldots$ . Lesson PG6.3 listed $\mathbb{Z}$ and $\mathbb{N} \times \mathbb{N}$ . Can the set $\Omega$ of all infinite toss sequences be listed too?

A computer cannot hold an infinite list, but it can test the idea behind the answer on finite ones. Take any list of 6 sequences of 6 tosses.

Build a new sequence $d$ : its toss $j$ is the opposite of toss $j$ of sequence $j$ . That flips the diagonal of the list.

import numpy as np rng = np.random.default_rng(3) def flip(c): return "T" if c == "H" else "H" def diagonal(lst): return "".join(flip(lst[j][j]) for j in range(len(lst))) lst = ["".join(rng.choice(["H", "T"], size=6)) for _ in range(6)] for s in lst: print(s) print(diagonal(lst)) hits = 0 for trial in range(1000): lst = ["".join(rng.choice(["H", "T"], size=8)) for _ in range(8)] hits += diagonal(lst) in lst print(hits)

⌘/Ctrl + Enter runs the cell

The six tosses on the diagonal of the first list are T, T, H, H, H, T, so $d$ is HHTTTH. It differs from the first sequence at toss 1, from the second at toss 2, and so on down the list.

The last line repeats this for 1,000 random lists of 8 sequences of 8 tosses. The flipped diagonal was on its list 0 times.

Conjecture

s_1, s_2, s_3, \ldots

A thousand finite lists. A list of $\Omega$ would be infinite, and the claim is about every possible list. The proof must flip the diagonal at every place at once.

Proof by contradiction, with a diagonal

To show that no list works, suppose one does and derive something false, as in stage PG2. The false thing is a sequence that the list both contains, by assumption, and misses, by construction. Write $s_i(j)$ for toss $j$ of sequence $s_i$ .

Format 1

Reorder the steps

Here is the proof, with its lines shuffled. Put them in order with the arrows, or drag a line by its handle.

Write $s_i(j)$ for toss $j$ of the sequence $s_i$ ; each is H or T.
So $d$ is an infinite toss sequence that is not on the list, which contradicts the first line.
For every $i$ , the sequences $d$ and $s_i$ differ at toss $i$ , so $d \ne s_i$ .
Suppose, for a contradiction, that $s_1, s_2, s_3, \ldots$ is a list that contains every infinite toss sequence.
Build a sequence $d$ by flipping the diagonal: toss $j$ of $d$ is T when $s_j(j)$ is H, and H when $s_j(j)$ is T.
So no list contains every sequence: $\Omega$ is uncountable.

This is Cantor's diagonal argument. A version of it, with decimal digits, shows that the real numbers between 0 and 1 cannot be listed either.

Simulate

The probability of one sequence

With a fair coin, the $2^n$ patterns of the first $n$ tosses are equally likely (lesson 5.1.1). So each pattern has probability $2^{-n}$ , and together they add up to 1.

from fractions import Fraction from itertools import product for n in [1, 2, 3, 10]: patterns = list(product("HT", repeat=n)) print(n, len(patterns), sum(Fraction(1, 2**n) for _ in patterns)) for n in [10, 20, 50]: print(n, f"{2.0**-n:.2e}")

⌘/Ctrl + Enter runs the cell

Fix one infinite sequence $\omega$ (the Greek letter omega). To get $\omega$ exactly, the first $n$ tosses must match it, which has probability $2^{-n}$ : $9.77 \times 10^{-4}$ for $n = 10$ and $8.88 \times 10^{-16}$ for $n = 50$ . That holds for every $n$ , so the chance of $\omega$ itself is smaller than any of them.

Conjecture

P(\{\omega\}) = 0

Tossing for ever is a model, not an experiment, so no simulation can run it. The next proof shows what the model can and cannot do.

Format 3

Find the error

A proof that a fair coin cannot be tossed for ever, because the axioms of lesson 5.1.1 would contradict each other. One line misuses an axiom. Select it.

Why infinitely many tosses need measure theory

With finitely many tosses, a probability is a sum over outcomes: add up $2^{-n}$ for each pattern in the event. With infinitely many, every outcome has probability 0 and there are too many outcomes to list, so that recipe gives nothing.

Measure theory starts from events instead. It gives each event fixed by finitely many tosses, such as "the first two tosses are HT", the probability its patterns give. Then it extends $P$ to every event built from those by complements and by unions along a list.

That extension takes real work. It also has a limit. Some subsets of $\Omega$ get no probability at all, if the axioms hold and flipping finitely many tosses changes no probability.

The Stochastic Calculus course builds on this. Its random walks and Brownian motion live on sample spaces like $\Omega$ .

\Omega

Uncountable sets, and infinitely many coin tosses