# Increasing Sequence of Events

I'm stuck on how to approach the following problem:

A fair coin is tossed repeatedly. Show that, with probability one, a head turns up sooner or later.

I think I have to use the lemma for increasing sequence of events, that is

$\mathbb{P}(A) = \lim_{i \rightarrow \infty} \mathbb{P}(A_i)$

However I am not sure how to use this result. Where my intuition breaks down is that if I have a sequence of coin tosses (H,H,T,H,T,T....), how can that be a sequence of increasing events?

I looked around at some other text books and I think I can use the Borel-Cantelli lemma easily as follows:

The event 'Head' occurs infinitely often with probability one since $\Sigma_{n=1}^{\infty} \mathbb{P}(H) = \infty$ and the events 'Head' are independent.

But the problem is that we haven't studied the Borel-Cantelli lemma as that involves studying measure theory and I am only an undergraduate.

Any help or hints would be appreciated.

-
Let $A_n$ be the event that there is a head in the first $n$ flips. Then $A_1, A_2, \ldots$ is an increasing sequence of events. – mjqxxxx May 7 '14 at 4:45
Just to get my thinking verified, if I set the event that a head occurs arbitrarily as $A_n$, the increasing sequence lemma just says that if I repeat the trials of the experiment infinitely many times (in this case a coin toss), eventually I will reach my event $A_n$. So it is proved that a head will turn up sooner or later. – Mika'il May 7 '14 at 5:03
@I.K. I do not think your way of summarizing the situation is very rigorous, since you do not "reach an event". In fact, the events $(A_n)$ are increasing. Their union is $A:=\bigcup A_n=\{\exists n\in\mathbb{N}\ :\ \text{ there is a head in the first$n$flips}\}=\{\text{a head turns up sooner or later}\}$. Hence, by the increasing sequence lemma, the probability of the event you are looking for is the limit (as n goes to infinity) of the probability of $A_n$. You can show easily that this limit is 1. – Ian May 7 '14 at 5:29
@Ian, can you explain what you mean by "In fact, the events $(A_n)$ are increasing". This is where my intuition breaks-down. If I have a sequence of coin tosses, (H,T,H,H...), what aspect of it is increasing? Also I am not sure how to show that this limit is 1. Please can you give a hint on that. – Mika'il May 8 '14 at 0:07
It is the size of the events (in the sense of set theory), rather than their "number" or "length" that is increasing. Think of it as subsets of $\Omega$ that are getting larger and larger, and tending to the whole space $\Omega$. The associated probabilities are increasing (in the sense of real analysis) and tend to 1. By the way, to calculate the probability of $A_n$, it is simply $1-P(\{$there are no heads in the first $n$ flips$\})=1-P(\{$there are $n$ tails in the first $n$ flips$\})$, which I'm sure you can calculate easily. – Ian May 8 '14 at 1:14

Let $\Omega=\{H,T\}^{\mathbb{N}}$, and define the event $A_n=\{(\omega_k)_{k\in\mathbb{N}}\subset\Omega\ :\ \exists i\in\{1,\dots,n\}\text{ such that }\omega_i=H\}$ for $n\in\mathbb{N}$.

The sequence $(A_n)_{n\in\mathbb{N}}$ is increasing in the sense that for all $n\in\mathbb{N}$, $A_n\subset A_{n+1}$. Additionally, if we set $A=\bigcup_{n\in\mathbb{N}}A_n$, then $A=\{$a head turns up sooner or later$\}$.

We can also easily verify that $$\mathbb{P}(A_n^c)=\mathbb{P}(\{(\omega_k)_{k\in\mathbb{N}}\subset\Omega\ :\ \forall i\in\{1,\dots,n\}\text{ such that }\omega_i=T\})=\left(\frac{1}{2}\right)^n.$$

Hence, by the "increasing sequence lemma",

$$\mathbb{P}(A)=\lim_{n\rightarrow+\infty}\mathbb{P}(A_n)=\lim_{n\rightarrow+\infty}(1-\mathbb{P}(A_n^c))=\lim_{n\rightarrow+\infty}\left(1-\left(\frac{1}{2}\right)^n\right)=1.$$

-
Just one point, in my book it defines the increasing sequences like this $A_n \subseteq A_{n+1}$. Will that make any difference? – Mika'il May 8 '14 at 10:02
I use the notation $A_n\subset A_{n+1}$ in the loose sense, i.e. we may have $A_n=A_{n+1}$. So my definition of an increasing sequence is the same as the one in your book. – Ian May 8 '14 at 10:03
No lemma on sequences is needed here, only the comparison $A_n\subseteq A$ for every $n$, which implies $P(A)\geqslant P(A_n)$ for every $n$. Since $P(A_n)=1-(1/2)^n$ for every $n$ and $\lim\limits_{n\to\infty}1-(1/2)^n=1$, the proof is complete. – Did May 8 '14 at 10:07
@Did, indeed, thanks for the remark. This had been an ongoing discussion and I was lacking some perspective! – Ian May 8 '14 at 10:12
@Q-rious Here, I compute $\mathbb P(A_n^c)=1/2^n$, so $\mathbb P(A_n)=1-1/2^n<1$. Did you notice that in the definition of $A_n$, the $i$ such that $\omega_i=H$ should be before $n$? This ensures that $\mathbb P(A_n)<1$. By the way, the rigorous construction of the probability measure usually involves defining the measure on some finite subsets and extending it by an extension theorem. I think this is a bit outside the scope of this answer. – Ian Jan 22 '15 at 23:16