# How to Prove that an Event Occurs Infinitely Often (Almost Surely)?

Exercise: There is a fair 6-sided die and a biased coin that has probability p > 0 of coming up heads on each toss. The die gets rolled infinitely often, and whenever you roll a 6, you then toss the coin. Prove that with probability 1, you toss "heads" infinitely often.

Now, I get this question intuitively; infinite rolls of the dice means infinite occurrences of each number on the die including 6, this meaning the coin will also be flipped an infinite number of times and since there is a guaranteed chance of heads being an outcome we will also get an infinite number of heads.

I'm not sure how to express this in mathematical notation however and I'm hoping someone here can help me out.

• What do you already know that you can use? For instance, have you already established that the number of heads appearing in infinitely many flips of a biased coin will be infinite almost surely? – whuber Aug 6 '15 at 13:33
• Nope this still needs to be established. I've been trying to use the binomial distribution as n goes to infinity but thats not leading anywhere... – FaxDogTitanicSoccer Aug 6 '15 at 13:54
• I believe that this is an application of the converse result of the Borel-Cantelli lemma... en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma Does this help? – RayVelcoro Aug 6 '15 at 15:16

The sample space consists of seven possible outcomes: "1" through "5" on the die, "6" and "tails", and "6" and "heads." Let's abbreviate these as $\Omega=\{1,2,3,4,5,6T,6H\}$.

The events will be generated by the atoms $\{1\}, \{2\}, \ldots, \{6H\}$ and therefore all subsets of $\Omega$ are measurable.

The probability measure $\mathbb{P}$ is determined by its values on these atoms. The information in the question, together with the (reasonable) assumption that the coin toss is independent of the die throw, tells us those probabilities are as given in this table:

$$\begin{array}{lc} \text{Outcome} & \text{Probability} \\ 1 & \frac{1}{6} \\ 2 & \frac{1}{6} \\ 3 & \frac{1}{6} \\ 4 & \frac{1}{6} \\ 5 & \frac{1}{6} \\ \text{6T} & \frac{1-p}{6} \\ \text{6H} & \frac{p}{6} \end{array}$$

A sequence of independent realizations of $X$ is a sequence $(\omega_1, \omega_2, \ldots, \omega_n, \ldots)$ all of whose elements are in $\Omega$. Let's call the set of all such sequences $\Omega^\infty$. The basic problem here lies in dealing with infinite sequences. The motivating idea behind the following solution is to keep simplifying the probability calculation until it can be reduced to computing the probability of a finite event. This is done in stages.

First, in order to discuss probabilities at all, we need to define a measure on $\Omega^\infty$ that makes events like "$6H$ occurs infinitely often" into measurable sets. This can be done in terms of "basic" sets that don't involve an infinite specification of values. Since we know how to define probabilities $\mathbb{P}_n$ on the set of finite sequences of length $n$, $\Omega^n$, let's define the "extension" of any measurable $E \subset \Omega^n$ to consist of all infinite sequences $\omega\in\Omega^\infty$ that have some element of $E$ as their prefix:

$$E^\infty = \{(\omega_i)\in\Omega^\infty\,|\, (\omega_1,\ldots,\omega_n)\in E\}.$$

The smallest sigma-algebra on $\Omega^\infty$ that contains all such sets is the one we will work with.

The probability measure $\mathbb{P}_\infty$ on $\Omega^\infty$ is determined by the finite probabilities $\mathbb{P}_n$. That is, for all $n$ and all $E\subset \Omega^n$,

$$\mathbb{P}_\infty(E^\infty) = \mathbb{P}_n(E).$$

(The preceding statements about the sigma-algebra on $\Omega^\infty$ and the measure $\mathbb{P}_\infty$ are elegant ways to carry out what will amount to limiting arguments.)

Having managed these formalities, we can do the calculations. To get started, we need to establish that it even makes sense to discuss the "probability" of $6H$ occurring infinitely often. This event can be constructed as the intersection of events of the type "$6H$ occurs at least $n$ times", for $n=1, 2, \ldots$. Because it is a countable intersection of measurable sets, it is measurable, so its probability exists.

Second, we need to compute this probability of $6H$ occurring infinitely often. One way is to compute the probability of the complementary event: what is the chance that $6H$ occurs only finitely many times? This event $E$ will be measurable, because it's the complement of a measurable set, as we have already established. $E$ can be partitioned into events $E_n$ of the form "$6H$ occurs exactly $n$ times", for $n=0, 1, 2, \ldots$. Because there are only countably many of these, the probability of $E$ will be the (countable) sum of the probabilities of the $E_n$. What are these probabilities?

Once more we can do a partition: $E_n$ breaks into events $E_{n,N}$ of the form "$6H$ occurs exactly $n$ times at roll $N$ and never occurs again." These events are disjoint and countable in number, so all we have to do (again!) is to compute their chances and add them up. But finally we have reduced the problem to a finite calculation: $\mathbb{P}_\infty(E_{n,N})$ is no greater than the chance of any finite event of the form "$6H$ occurs for the $n^\text{th}$ time at roll $N$ and does not occur between rolls $N$ and $M \gt N$." The calculation is easy because we don't really need to know the details: each time $M$ increases by $1$, the chance--whatever it may be--is further multiplied by the chance that $6H$ is not rolled, which is $1-p/6$. We thereby obtain a geometric sequence with common ratio $r = 1-p/6 \lt 1$. Regardless of the starting value, it grows arbitrarily small as $M$ gets large.

(Notice that we did not need to take a limit of probabilities: we only needed to show that the probability of $E_{n,N}$ is bounded above by numbers that converge to zero.)

Consequently $\mathbb{P}_\infty(E_{n,N})$ cannot have any value greater than $0$, whence it must equal $0$. Accordingly,

$$\mathbb{P}_\infty(E_n) = \sum_{N=0}^\infty \mathbb{P}_\infty(E_{n,N}) = 0.$$

Where are we? We have just established that for any $n \ge 0$, the chance of observing exactly $n$ outcomes of $6H$ is nil. By adding up all these zeros, we conclude that $$\mathbb{P}_\infty(E) = \sum_{n=0}^\infty \mathbb{P}_\infty(E_n) = 0.$$ This is the chance that $6H$ occurs only finitely many times. Consequently, the chance that $6H$ occurs infinitely many times is $1-0 = 1$, QED.

Every statement in the preceding paragraph is so obvious as to be intuitively trivial. The exercise of demonstrating its conclusions with some rigor, using the definitions of sigma algebras and probability measures, helps show that these definitions are the right ones for working with probabilities, even when infinite sequences are involved.

You have two nice answers addressing the question using basic probability principles. Here are two theorems that help you answer this question quickly in situations were such solutions are appropriate:

The Strong Law of Large Numbers (SLLN) tells you that for independent and identically distributed random variables with finite mean, the sample mean converges to the true mean almost surely.

The Second Borel-Cantelli Lemma (BC2) tells you that if the sum of probabilities of a sequence of independent events is infinite, then infinitely many of those events will happen almost surely.

Let $Y_i$ take the value 1 if you roll 6 and flip heads on trial $i$, and zero otherwise. Then $Y_i$ is a Bernoulli random variable with success probability $\theta:=p/6>0$. By the SLLN, $\sum_{i=1}^n Y_i/n \to \theta$ almost surely. But then we must have $\sum_{i=1}^n Y_i \to \infty$ almost surely, which is what we wanted to show.

Let $E_i$ be the event that you roll 6 and flip heads on trial $i$. Then $P(E_i)=p/6>0$, for every $i$, and consequently $\sum_{i=1}^nP(E_i)\to\infty$. Thus, by BC2 infinitely many of the events $E_i$ will happen almost surely, which is what we wanted to show.
Without relying on any kind of advanced probability theory as in the RayVelcoro's answer, one could proceed as follows. Let $I_j$ denote the event that the final heads was attained on the $j^{\text{th}}$ toss of the die. Then, by countable additivity, the probability of a finite number of heads is $$\sum_{j=0}^\infty P(I_j) \stackrel{?}{=} 0.$$ It now suffices to show that $P(I_j) = 0$ for all $j$. To do this, let $A_{j,n}$ denote the event that "after $n$ die rolls, the last head occured on the $j^{\text{th}}$ roll". Now, clearly $I_j \subseteq A_{j,n}$ for all $n$, and hence $P(I_j) \le P(A_{j,n})$; take $n \to \infty$ to see that $P(I_j) \le \lim_{n \to \infty} P(A_{j,n}) = 0$. $P(A_{j,n})$ can be computed directly in the obvious way (it is the probability of a success followed by $n-j - 1$ failures by independence).