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.

  • $\begingroup$ 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. $\endgroup$ – mjqxxxx May 7 '14 at 4:45
  • $\begingroup$ 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. $\endgroup$ – M.K. May 7 '14 at 5:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Ian May 7 '14 at 5:29
  • $\begingroup$ @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. $\endgroup$ – M.K. May 8 '14 at 0:07
  • 1
    $\begingroup$ 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. $\endgroup$ – 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. $$

  • $\begingroup$ Just one point, in my book it defines the increasing sequences like this $A_n \subseteq A_{n+1}$. Will that make any difference? $\endgroup$ – M.K. May 8 '14 at 10:02
  • $\begingroup$ 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. $\endgroup$ – Ian May 8 '14 at 10:03
  • $\begingroup$ 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. $\endgroup$ – Did May 8 '14 at 10:07
  • $\begingroup$ @Did, indeed, thanks for the remark. This had been an ongoing discussion and I was lacking some perspective! $\endgroup$ – Ian May 8 '14 at 10:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Ian Jan 22 '15 at 23:16

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.