Convergence

In this section we discuss several topics that are a bit advanced, but very important. In particular the results obtained in this section will be essential for establishing

The Continuity Theorems

Increasing Events

A sequence of events

A 1 A 2

is said to be increasing if

A n A n 1

for each

n

. Thus, the events are increasing with respect to the subset partial order. The terminology is also justified by considering the corresponding indicator variables.

Let $I n$ denote the indicator variable of the event $A n$ for $n$ . Show that the sequence of events is increasing if and only if the sequence of indicator variables is increasing in the ordinary sense. That is, $I n I n 1$ for each $n$ .

A 1 A 2

is an increasing sequence of events, we refer to the union of the events as the limit of the events:

Once again, the terminology is clarified by the corresponding indicator variables.

Suppose that $A 1 A 2$ is an increasing sequence of events. Let $I n$ denote the indicator variable of $A n$ for $n$ , and let $I$ denote the indicator variable of the union of the events. Show that

n I n I

Generally speaking, a function is continuous if it preserves limits. Thus, the result in the following exercise is referred to as the continuity theorem for increasing events:

Suppose that $A 1 A 2$ is an increasing sequence of events. Show that

n A n n A n

Let $B 1 A 1$ and let $B i A i A i 1$ for $i 23$ .
Show that the collection of events $B 1 B 2$ is pairwise disjoint and has the same union as $A 1 A 2$
Use the additivity axiom of probability and the definition of an infinite series.

The construction in the continuity theorem

An arbitrary union of events can always be written as a union of increasing events, as the next exercise shows.

Suppose that $A 1 A 2$ is a sequence of events. Show that

$i 1 n A i$ is increasing in $n$
$n i 1 n A i i 1 A i$
$n i 1 n A i i 1 A i$

Suppose that $A$ is an event for a basic experiment with $A 0$ . In the compound experiment that consists of independent replications of the basic experiment, show that the event $A$ eventually occurs has probability 1.

Decreasing Events

A sequence of events

A 1 A 2

is said to be decreasing if

A n 1 A n

for each

n

. Thus, the events are decreasing with respect to the subset partial order. The terminology is also justified by considering the corresponding indicator variables.

Let $I n$ denote the indicator variable of an event $A n$ for $n$ . Show that the sequence of events is decreasing if and only if the sequence of indicator variables is decreasing in the ordinary sense. That is, $I n 1 I n$ for each $n$ .

A 1 A 2

is a decreasing sequence of events, we refer to the intersection of the events as the limit of the events:

Once again, the terminology is clarified by the corresponding indicator variables.

Suppose that $A 1 A 2$ is a decreasing sequence of events. Let $I n$ denote the indicator variable of $A n$ for $n$ , and let $I$ denote the indicator variable of the intersection of the events. Show that

n I n I

The result in the following exercise is referred to as the continuity theorem for decreasing events :

Suppose that $A 1 A 2$ is a decreasing sequence of events. Show that

n A n n A n

Show that the sequence of events $A 1 > A 2$ is increasing.
Apply the continuity theorem for increasing events to the sequence in part (a).
Use DeMorgan's law and the complement rule.

An arbitrary intersection of events can always be written as an intersection of decreasing events, as the next exercise shows.

Suppose that $A 1 A 2$ is a sequence of events. Show that

$i 1 n A i$ is decreasing in $n$
$n i 1 n A i i 1 A i$
$n i 1 n A i i 1 A i$

The Borel-Cantelli Lemmas

The First Lemma

Show that $i n A i$ is decreasing in $n$ .

The limit (that is, the intersection) of the decreasing sequence in the previous exercise is called the limit superior of the original sequence.

Show that $n A n$ is the event that occurs if and only if $A n$ occurs for infinitely many values of $n$ .

Once again, the terminology is justified by the corresponding indicator variables:

Let $I n$ denote the indicator variable of $A n$ for $n$ , and let $I$ denote the indicator variable of $n A n$ . Show that

I n I n

Use the continuity theorem for decreasing events to show that

n A n n i n A n

The result in the next exercise is the first Borel-Cantelli Lemma, named after Emil Borel and Francessco Cantelli. It gives a condition that is sufficient to conclude that infinitely many events occur with probability 0.

Show that if $n 1 A n$ then $n A n 0$ .

Start with the result of the previous exercise.
Apply Boole's inequality.
Recall that if an infinite series converges, then the tail of the series converges to 0.

The Second Lemma

Show that $i n A i$ is increasing in $n$ .

The limit (that is, the union) of the increasing sequence in the previous exercise is called the limit inferior of the original sequence.

Show that $n A n$ is the event that occurs if and only if $A n$ occurs for all but finitely many values of $n$ .

Once again, the terminology is justified by the corresponding indicator variables:

Let $I n$ denote the indicator variable of $A n$ for $n$ , and let $I$ denote the indicator variable of $n A n$ . Show that

I n I n

Use the continuity theorem for decreasing events to show that

n A n n i n A i

Show that $n A n n A n$ .

Use DeMorgan's law to show that $n A n n A n$ .

The result in the next exercise is the second Borel-Cantelli Lemma. It gives a condition that is sufficient to conclude that infinitely many events occur with probability 1.

Suppose that $A 1 A 2$ is a sequence of independent events. Show that if $n 1 A n$ then $n A n 1$ .

Show that $1 x x$ for every $x$
Conclude that $1 A k A k$ for each $k$ .
Now use the result of the previous exercise and independence.

Suppose that $A$ is an event in a basic experiment with $A 0$ . Show that in the compound experiment that consists of independent replications of the basic experiment, the event $A$ occurs infinitely often has probability 1.

Suppose that we have an infinite sequence of coins labeled 1, 2, ... Moreover, coin $n$ has probability of heads $1 n a$ for each $n$ , where $a 0$ is a parameter. We toss each coin in sequence one time. In terms of $a$ , find the probability of the following events:

infinitely many heads.
infinitely many tails.

Convergence of Random Variables

Suppose that

X 1 X 2

and

X

are real-valued random variables for an experiment. We will discuss two ways that the sequence

X n

can converge to

X

n

. These are fundamentally important concepts, since some of the deepest results in probability theory are limit theorems.

The statement that an event has probability 1 is the strongest statement that we can make in probability theory. Thus, convergence with probability 1 is the strongest form of convergence. The phrases almost surely and almost everywhere are sometimes used instead of the phrase with probability 1.

The phrase in probability sounds superficially like the phrase with probability 1. However, as we will see, convergence in probability is much weaker than convergence with probability 1. Indeed, convergence with probability 1 is often called strong convergence, while convergence in probability is often called weak convergence. The next sequence of exercises explores convergence with probability 1. We will let

denote the set of positive rational numbers; a critical point to remember is that this set is countable.

Show that the following events are equivalent:

$X n$ does $not$ converge to $X$ as $n$ .
For some $ε 0$ , $X n X ε$ for infinitely many $n$ .
For some $ε$ , $X n X ε$ for infinitely many $n$ .

Use the result of the previous exercise to show that the following are equivalent

$X n X as n 1$
$X n X ε for infinitely many n 0$ for every $ε$ . Hint: Use Boole's inequality.
$X n X ε for infinitely many n 0$ for every $ε 0$ .
$X k X ε for some k n 0 as n$ for every $ε 0$ .

Part (b) of this exercise and the first Borel-Cantelli Lemma lead to a nice criterion for convergence with probability 1:

Show that if $n 1 X n X ε$ for every $ε 0$ then $X n X$ as $n$ with probability 1.

Part (c) of Exercise 25 leads to one of our main results: convergence with probability 1 implies convergence in probability.

Show that if $X n X$ as $n$ with probability 1 then $X n X$ as $n$ in probability.

As in Exercise 23, suppose that we have a sequence of coins labeled 1, 2, ...; coin $n$ lands heads up with probability $1 n$ for each $n$ . We toss the coins in order to produce a sequence $X 1 X 2$ of independent indicator random variables with

X n 1 1 n, X n 0 1 1 n, n

Use the second Borel-Cantelli lemma to show that $X n 0 for infinitely many n 1$ , so that infinitely many tails occur with probability 1.
Use the second Borel-Cantelli lemma to show that $X n 1 for infinitely many n 1$ , so that infinitely many heads occur with probability 1.
Use (a) and (b) to show that $X n does not converge as n 1$ .
Show that $X n 0 as n$ in probability.

Show that if $X n X$ as $n$ in probability, then there exists a subsequence $n 1 n 2 n 3$ of such that $X n k X$ as $k$ with probability 1.

Assuming convergence in probability, show that for each $k$ there exists $n k$ such that $X n k X 1 k 1 k 2$ .
We can make the choices in part (a) so that $n k n k 1$ for each $k$ .
From (a) and (b) conclude that $k 1 X n k X ε$ for every $ε 0$ ,
Use Exercise 26 to conclude that $X n k X$ as $k$ with probability 1.
The proof works because $1 k 0$ as $k$ and $k 1 1 k 2$ . Any two sequences with these properties would work just as well.

6. Convergence