Chapter 8: Law of Large NumbersContent check — Probability (Grinstead and Snell), Chapter 8: Law of Large Numbers

Let $S_n$ be the number of successes in $n$ Bernoulli trials with probability $p$ for success on each trial. Show, using Chebyshev’s Inequality, that for any $ϵ>0$ $$P(|\frac{S_n}{n}-p|\ge ϵ)\le \frac{p(1-p)}{n{ϵ}^2}.$$

Suppose that $n$ people have their hats returned at random. Let $X_i=1$ if the $i$⁠th person gets his or her own hat back and 0 otherwise. Let $S_n={\sum }_{i=1}^n{X}_i$⁠. Then $S_n$ is the total number of people who get their own hats back. Show that

(a) $E(X_i^2)=1/n$⁠.

(b) $E(X_i\cdot X_j)=1/n(n-1)$ for $i\ne j$⁠.

(c) $E(S_n^2)=2$ (using (a) and (b)).

(d) $V(S_n)=1$⁠.

Consider an experiment in which a fair coin is tossed repeatedly, without stopping. We have seen in Example 1.6 that, for a coin tossed $n$ times, the natural sample space is a binary tree with $n$ stages. On this evidence we expect that for a coin tossed repeatedly, the natural sample space is a binary tree with an infinite number of stages, as indicated in Figure 2.22.

It is surprising to learn that, although the $n$⁠-stage tree is obviously a finite sample space, the unlimited tree can be described as a continuous sample space. To see how this comes about, let us agree that a typical outcome of the unlimited coin tossing experiment can be described by a sequence of the form $\omega =\{\text{H H T H T T H}\dots \}$⁠. If we write 1 for H and 0 for T, then $\omega =\{1101001\dots \}$⁠. In this way, each outcome is described by a sequence of 0’s and 1’s.

Figure 2.22: Tree for infinite number of tosses of a coin.

Now suppose we think of this sequence of 0’s and 1’s as the binary expansion of some real number $x=.1101001\cdots$ lying between 0 and 1. (A binary expansion is like a decimal expansion but based on 2 instead of 10.) Then each outcome is described by a value of $x$⁠, and in this way $x$ becomes a coordinate for the sample space, taking on all real values between 0 and 1. (We note that it is possible for two different sequences to correspond to the same real number; for example, the sequences $\{\text{T H H H H H}\dots \}$ and $\{\text{H T T T T T}\dots \}$ both correspond to the real number $1/2$⁠. We will not concern ourselves with this apparent problem here.)

What probabilities should be assigned to the events of this sample space? Consider, for example, the event $E$ consisting of all outcomes for which the first toss comes up heads and the second tails. Every such outcome has the form $.10\ast \ast \ast \ast \cdots$⁠, where $\ast$ can be either 0 or 1. Now if $x$ is our real-valued coordinate, then the value of $x$ for every such outcome must lie between $1/2=.10000\cdots$ and $3/4=.11000\cdots$⁠, and moreover, every value of $x$ between 1/2 and 3/4 has a binary expansion of the form $.10\ast \ast \ast \ast \cdots$⁠. This means that $\omega \in E$ if and only if $1/2\le x<3/4$⁠, and in this way we see that we can describe $E$ by the interval $[1/\mathrm{2,3}/4)$⁠. More generally, every event consisting of outcomes for which the results of the first $n$ tosses are prescribed is described by a binary interval of the form $[k/2^n,(k+1)/2^n)$⁠.

We have already seen in Section 1.2 that in the experiment involving $n$ tosses, the probability of any one outcome must be exactly $1/2^n$⁠. It follows that in the unlimited toss experiment, the probability of any event consisting of outcomes for which the results of the first $n$ tosses are prescribed must also be $1/2^n$⁠. But $1/2^n$ is exactly the length of the interval of $x$⁠-values describing $E$⁠! Thus we see that, just as with the spinner experiment, the probability of an event $E$ is determined by what fraction of the unit interval lies in $E$⁠.

Consider again the statement: The probability is 1/2 that a fair coin will turn up heads when tossed. We have suggested that one interpretation of this statement is that if we toss the coin indefinitely the proportion of heads will approach 1/2. That is, in our correspondence with binary sequences we expect to get a binary sequence with the proportion of 1’s tending to 1/2. The event $E$ of binary sequences for which this is true is a proper subset of the set of all possible binary sequences. It does not contain, for example, the sequence $011011011\dots$ (i.e., (011) repeated again and again). The event $E$ is actually a very complicated subset of the binary sequences, but its probability can be determined as a limit of probabilities for events with a finite number of outcomes whose probabilities are given by finite tree measures. When the probability of $E$ is computed in this way, its value is found to be 1. This remarkable result is known as the Strong Law of Large Numbers (or Law of Averages) and is one justification for our frequency concept of probability. We shall prove a weak form of this theorem in Chapter 8.

A die is rolled once. We let $X$ denote the outcome of this experiment. Then the sample space for this experiment is the 6-element set $$\mathrm{\Omega }=\{\mathrm{1,2,3,4,5,6}\},$$ where each outcome $i$⁠, for $i=1$⁠, …, 6, corresponds to the number of dots on the face which turns up. The event $$E=\{\mathrm{2,4,6}\}$$ corresponds to the statement that the result of the roll is an even number. The event $E$ can also be described by saying that $X$ is even. Unless there is reason to believe the die is loaded, the natural assumption is that every outcome is equally likely. Adopting this convention means that we assign a probability of 1/6 to each of the six outcomes, i.e., $m(i)=1/6$⁠, for $1\le i\le 6$⁠.

Figure 2.22: Tree for infinite number of tosses of a coin.

We have proved a theorem often called the “Weak Law of Large Numbers." Most people’s intuition and our computer simulations suggest that, if we toss a coin a sequence of times, the proportion of heads will really approach 1/2; that is, if $S_n$ is the number of heads in $n$ times, then we will have $$A_n=\frac{S_n}{n}\to \frac{1}{2}$$ as $n\to \infty$⁠. Of course, we cannot be sure of this since we are not able to toss the coin an infinite number of times, and, if we could, the coin could come up heads every time. However, the “Strong Law of Large Numbers," proved in more advanced courses, states that $$P(\frac{S_n}{n}\to \frac{1}{2})=1.$$ Describe a sample space $\mathrm{\Omega }$ that would make it possible for us to talk about the event $$E=\{\omega :\frac{S_n}{n}\to \frac{1}{2}\}.$$ Could we assign the equiprobable measure to this space? (See Example 2.18.)

Consider an experiment in which a fair coin is tossed repeatedly, without stopping. We have seen in Example 1.6 that, for a coin tossed $n$ times, the natural sample space is a binary tree with $n$ stages. On this evidence we expect that for a coin tossed repeatedly, the natural sample space is a binary tree with an infinite number of stages, as indicated in Figure 2.22.

It is surprising to learn that, although the $n$⁠-stage tree is obviously a finite sample space, the unlimited tree can be described as a continuous sample space. To see how this comes about, let us agree that a typical outcome of the unlimited coin tossing experiment can be described by a sequence of the form $\omega =\{\text{H H T H T T H}\dots \}$⁠. If we write 1 for H and 0 for T, then $\omega =\{1101001\dots \}$⁠. In this way, each outcome is described by a sequence of 0’s and 1’s.

Figure 2.22: Tree for infinite number of tosses of a coin.

Now suppose we think of this sequence of 0’s and 1’s as the binary expansion of some real number $x=.1101001\cdots$ lying between 0 and 1. (A binary expansion is like a decimal expansion but based on 2 instead of 10.) Then each outcome is described by a value of $x$⁠, and in this way $x$ becomes a coordinate for the sample space, taking on all real values between 0 and 1. (We note that it is possible for two different sequences to correspond to the same real number; for example, the sequences $\{\text{T H H H H H}\dots \}$ and $\{\text{H T T T T T}\dots \}$ both correspond to the real number $1/2$⁠. We will not concern ourselves with this apparent problem here.)

What probabilities should be assigned to the events of this sample space? Consider, for example, the event $E$ consisting of all outcomes for which the first toss comes up heads and the second tails. Every such outcome has the form $.10\ast \ast \ast \ast \cdots$⁠, where $\ast$ can be either 0 or 1. Now if $x$ is our real-valued coordinate, then the value of $x$ for every such outcome must lie between $1/2=.10000\cdots$ and $3/4=.11000\cdots$⁠, and moreover, every value of $x$ between 1/2 and 3/4 has a binary expansion of the form $.10\ast \ast \ast \ast \cdots$⁠. This means that $\omega \in E$ if and only if $1/2\le x<3/4$⁠, and in this way we see that we can describe $E$ by the interval $[1/\mathrm{2,3}/4)$⁠. More generally, every event consisting of outcomes for which the results of the first $n$ tosses are prescribed is described by a binary interval of the form $[k/2^n,(k+1)/2^n)$⁠.

We have already seen in Section 1.2 that in the experiment involving $n$ tosses, the probability of any one outcome must be exactly $1/2^n$⁠. It follows that in the unlimited toss experiment, the probability of any event consisting of outcomes for which the results of the first $n$ tosses are prescribed must also be $1/2^n$⁠. But $1/2^n$ is exactly the length of the interval of $x$⁠-values describing $E$⁠! Thus we see that, just as with the spinner experiment, the probability of an event $E$ is determined by what fraction of the unit interval lies in $E$⁠.

Consider again the statement: The probability is 1/2 that a fair coin will turn up heads when tossed. We have suggested that one interpretation of this statement is that if we toss the coin indefinitely the proportion of heads will approach 1/2. That is, in our correspondence with binary sequences we expect to get a binary sequence with the proportion of 1’s tending to 1/2. The event $E$ of binary sequences for which this is true is a proper subset of the set of all possible binary sequences. It does not contain, for example, the sequence $011011011\dots$ (i.e., (011) repeated again and again). The event $E$ is actually a very complicated subset of the binary sequences, but its probability can be determined as a limit of probabilities for events with a finite number of outcomes whose probabilities are given by finite tree measures. When the probability of $E$ is computed in this way, its value is found to be 1. This remarkable result is known as the Strong Law of Large Numbers (or Law of Averages) and is one justification for our frequency concept of probability. We shall prove a weak form of this theorem in Chapter 8.

A die is rolled once. We let $X$ denote the outcome of this experiment. Then the sample space for this experiment is the 6-element set $$\mathrm{\Omega }=\{\mathrm{1,2,3,4,5,6}\},$$ where each outcome $i$⁠, for $i=1$⁠, …, 6, corresponds to the number of dots on the face which turns up. The event $$E=\{\mathrm{2,4,6}\}$$ corresponds to the statement that the result of the roll is an even number. The event $E$ can also be described by saying that $X$ is even. Unless there is reason to believe the die is loaded, the natural assumption is that every outcome is equally likely. Adopting this convention means that we assign a probability of 1/6 to each of the six outcomes, i.e., $m(i)=1/6$⁠, for $1\le i\le 6$⁠.

Figure 2.22: Tree for infinite number of tosses of a coin.

Let $X$ be a continuous random variable with values unformly distributed over the interval $[\mathrm{0,20}]$⁠.

(a) Find the mean and variance of $X$⁠.

(b) Calculate $P(|X-10|\ge 2)$⁠, $P(|X-10|\ge 5)$⁠, $P(|X-10|\ge 9)$⁠, and $P(|X-10|\ge 20)$ exactly. How do your answers compare with those of Exercise 1? How good is Chebyshev’s Inequality in this case?

Let $X$ be a continuous random variable with mean $\mu =10$ and variance ${\sigma }^2=100/3$⁠. Using Chebyshev’s Inequality, find an upper bound for the following probabilities.

(a) $P(|X-10|\ge 2)$⁠.

(b) $P(|X-10|\ge 5)$⁠.

(c) $P(|X-10|\ge 9)$⁠.

(d) $P(|X-10|\ge 20)$⁠.

Let $X$ be a continuous random variable with mean $\mu =10$ and variance ${\sigma }^2=100/3$⁠. Using Chebyshev’s Inequality, find an upper bound for the following probabilities.

(a) $P(|X-10|\ge 2)$⁠.

(b) $P(|X-10|\ge 5)$⁠.

(c) $P(|X-10|\ge 9)$⁠.

(d) $P(|X-10|\ge 20)$⁠.