I am having some trouble with the following probability question from an introductory class:
Suppose we toss a fair coin infinitely many times, independently, and let $X_i \in \{H, T\}$ denote the outcome of the $i$th coin toss. What is the probability that there exists an infinite arithmetic progression such that $X_i = H$ for all $i$ in that arithmetic progression? Stated another way, there exist $a, b \in \mathbb{N}$ such that $X_i = H$ whenever $i \in \{ a, a+b, a+2b, a+3b, \ldots \}$.
The hint that was provided suggested using the countable additivity axiom, which was presented as the following:
For any countable sequence of mutually exclusive events $E_1, E_2, \ldots$, where $E_i \cap E_j = \emptyset$ if $i \neq j$,
$$
P\left(\bigcup_{i=1}^{\infty} E_i \right) = \sum_{i=1}^\infty P(E_i).
$$
This is the progress that I have so far:
Let $E_{a,b}$ denote the event that there exists an infinite arithmetic progression of heads where the first term of this arithmetic progression is $a$ and the common difference is $b$. Then the probability that this occurs is $P(E_{a,b}) = \lim_{n\rightarrow \infty} (1/2)^n$.
Now, there are a countably infinite number of choices of $a$ and $b$. Our desired probability, by the axiom of countable additivity, is
$$
P\left(\bigcup_{a=1}^{\infty} \bigcup_{b=1}^{\infty} E_{a,b}\right) = \lim_{n\rightarrow \infty} \sum_{a=1}^{\infty} \sum_{b=1}^{\infty} (1/2)^n = 0.
$$
However, this argument doesn't seem particularly rigorous. What parts of it are incorrect? How might I improve it?
Best Answer
What you have done looks correct to me. Under the stated probability model (IID Bernoulli trials with equal probabilities of outcomes), it is easy to establish that any specific binary sequence has zero probability. Thus, all you need to do is to show that there are only a countable number of binary sequences with the desired property, and this is sufficient to establish that the desired property occurs with zero probability. (Assuming you are willing to accept countable additivity in probability.)
In relation to this type of question, it is worth noting that there are an uncountable number of possible binary sequences. The set of all binary sequences effectively just gives us a binary representation of the real numbers on the interval $[0,1]$. Thus, in this question you are effectively just trying to find out whether the subset of binary sequences with the desired arithmetic recurrence property is countable (and therefore has zero measure). This follows immediately from the fact that $(a,b) \in\mathbb{N}^2$ and $\mathbb{N}^2$ is countable.