math.wiki
Probability › Limit theorems › The law of large numbers
Sign in

The law of large numbers

Owen fires paintball after paintball at a target. Why must the fraction of hits settle on a single number, and in what sense does it settle?

Where you are 4 in Limit theorems

Why this exists

The axioms of Probability axioms and sample spaces say what a probability must satisfy, not what it means. The school lesson The law of large numbers and the gambler's fallacy takes the long-run reading from experience: over many independent repetitions, the share of trials on which an event happens settles near its probability. This lesson proves it. From the axioms, independence and Chebyshev’s inequality (Markov and Chebyshev inequalities), an average of many independent copies of a random variable is, with probability as close to 1 as we like, as close to its mean as we like. That theorem is what licenses estimating a mean by an average, a probability by a frequency, and an integral by random sampling.

Definition

A sequence of random variables Y_1, Y_2, \dots on one sample space converges in probability to a constant c if, for every \varepsilon > 0, the probability that Y_n misses c by \varepsilon or more tends to 0:

\lim_{n \to \infty} P(|Y_n - c| \ge \varepsilon) = 0.

We write Y_n \xrightarrow{P} c. Equivalently, P(|Y_n - c| < \varepsilon) \to 1 for every \varepsilon > 0. The statement is about one probability for each n; it says nothing directly about a single run of outcomes.

For random variables X_1, X_2, \dots, the partial sum and the sample mean are

S_n = X_1 + \dots + X_n, \qquad \bar{X}_n = \frac{S_n}{n}.

As in Independence of events and variables, the sequence is independent when every finite collection of its terms is, and iid when it is independent and its terms share one distribution. A law of large numbers is a theorem giving conditions under which \bar{X}_n \xrightarrow{P} \mu, the common mean. In plain words: for any tolerance, a long enough run makes it as likely as we like that the average lands within that tolerance of the mean.

Intuition

Averaging keeps the mean and shrinks the spread. If the X_i are uncorrelated with mean \mu and variance \sigma^2, then E(\bar{X}_n) = \mu and \displaystyle \operatorname{Var}(\bar{X}_n) = \frac{\sigma^2}{n}, so the Standard deviation of the average is \displaystyle \frac{\sigma}{\sqrt{n}}. The sum behaves the other way: \operatorname{Var}(S_n) = n\sigma^2, so S_n typically strays farther from n\mu as n grows, but only by an amount of order \displaystyle \sqrt{n}, which division by n crushes.

Figure 1 shows this for shots that each hit with probability 0.4. Here X_i is 1 for a hit and 0 for a miss, so \bar{X}_n is the proportion of hits and takes the values \displaystyle \frac{k}{n}. Drawing n P(S_n = k) above \displaystyle \frac{k}{n} puts the three distributions on one scale, each enclosing an area close to 1.

0 0.2 0.4 0.6 0.8 1 5 10 n = 250 n = 50 n = 10 proportion of hits
Figure 1The distribution of the proportion of hits \bar{X}_n when each shot hits with probability 0.4, drawn as n P(S_n = k) above \displaystyle \frac{k}{n} for n = 10, 50 and 250. The mass crowds into the band from 0.3 to 0.5.

Figure 2 follows the probability outside the band, P(|\bar{X}_n - 0.4| \ge 0.1), against Chebyshev’s bound \displaystyle \frac{0.24}{0.01n} = \frac{24}{n}. At n = 100 the exact value is about 0.0519 against a bound of 0.24; at n = 200 it is about 0.0048 against 0.12. The bound is crude, but it goes to 0, and going to 0 is all the law claims.

0 50 100 150 200 0.5 1 Chebyshev 24/n exact number of shots n
Figure 2The exact probability P(|\bar{X}_n - 0.4| \ge 0.1) that the proportion of hits leaves the band of Figure 1, with Chebyshev’s bound \displaystyle \frac{24}{n}. Both go to 0; the bound far more slowly.

Results

Result 1 (a mean-square test). Let each Y_n have finite variance, and let c be a constant. For every \varepsilon > 0,

P(|Y_n - c| \ge \varepsilon) \le \frac{\operatorname{Var}(Y_n) + \big(E(Y_n) - c\big)^2}{\varepsilon^2}.

So if E(Y_n) \to c and \operatorname{Var}(Y_n) \to 0, then Y_n \xrightarrow{P} c.

Result 2 (weak law of large numbers). Let X_1, X_2, \dots be pairwise uncorrelated, each with mean \mu and finite variance \sigma^2; iid with finite variance is enough. For every \varepsilon > 0,

P(|\bar{X}_n - \mu| \ge \varepsilon) \le \frac{\sigma^2}{n\varepsilon^2},

so \bar{X}_n \xrightarrow{P} \mu.

Result 3 (frequencies). Repeat an experiment independently, let A be an event of probability p on each trial, and let N_n count the first n trials on which A happens. For every \varepsilon > 0,

P\Big(\Big|\frac{N_n}{n} - p\Big| \ge \varepsilon\Big) \le \frac{p(1 - p)}{n\varepsilon^2} \le \frac{1}{4n\varepsilon^2},

so \displaystyle \frac{N_n}{n} \xrightarrow{P} p. This is the long-run frequency of the school lesson, now a theorem.

Result 4 (averages of a function). Let X_1, X_2, \dots be iid and let g be a function with E\big(g(X_1)^2\big) finite. Then

\frac{1}{n} \sum_{i=1}^{n} g(X_i) \xrightarrow{P} E\big(g(X_1)\big).

In particular: (a) for each real x, the proportion of X_1, \dots, X_n that are at most x converges in probability to F_X(x); (b) if U_1, U_2, \dots are iid \operatorname{Uniform}(a, b) and \int_a^b h(x)^2 \, dx is finite, then \displaystyle \frac{b - a}{n} \sum_{i=1}^{n} h(U_i) \xrightarrow{P} \int_a^b h(x) \, dx (Monte Carlo integration).

Result 5 (continuous functions). Let Y_n \xrightarrow{P} a and Z_n \xrightarrow{P} b, and let g(y, z) be continuous at (a, b). Then g(Y_n, Z_n) \xrightarrow{P} g(a, b); likewise g(Y_n) \xrightarrow{P} g(a) when g(y) is continuous at a. In particular Y_n + Z_n \xrightarrow{P} a + b, Y_n Z_n \xrightarrow{P} ab, and, if b \ne 0, \displaystyle \frac{Y_n}{Z_n} \xrightarrow{P} \frac{a}{b}, the quotient given any value where Z_n = 0.

Result 6 (stated without proof). Let X_1, X_2, \dots be iid with finite mean \mu, and no assumption on the variance. (a) Khinchin’s weak law: \bar{X}_n \xrightarrow{P} \mu. (b) The strong law: P\big(\lim_{n \to \infty} \bar{X}_n = \mu\big) = 1, that is, with probability 1 the sequence of averages in a run converges to \mu. Part (b) implies part (a).

Why it is true

Result 1. Let m_n = E(Y_n). Then Y_n - c = (Y_n - m_n) + (m_n - c); squaring and taking means by linearity, the cross term 2(m_n - c)E(Y_n - m_n) is 0, so

E\big((Y_n - c)^2\big) = \operatorname{Var}(Y_n) + (m_n - c)^2.

Result 2 of Markov and Chebyshev inequalities with r = 2, applied to Y_n - c, gives \displaystyle P(|Y_n - c| \ge \varepsilon) \le \frac{E((Y_n - c)^2)}{\varepsilon^2}. Under the hypotheses the numerator tends to 0.

Result 2. The bound is Result 6 of Markov and Chebyshev inequalities, and for fixed \varepsilon it tends to 0 as n \to \infty. Independent variables with finite variances are uncorrelated by Result 5 of Variance and covariance.

Result 3. Let X_i = \mathbf{1}_{A_i}, where A_i is the event that A happens on trial i. The A_i are independent, so the indicators are (Result 6 of Independence of events and variables); each has mean p (Result 3 of Expectation, linearity and indicators) and variance p(1 - p) (Result 7 of Variance and covariance with one trial). Since N_n = S_n, Result 2 applies with \sigma^2 = p(1 - p). Finally \displaystyle \frac14 - p(1 - p) = \left(p - \frac12\right)^2 \ge 0.

Result 4. We use one fact stated without proof: functions of independent random variables are independent, so g(X_1), g(X_2), \dots are independent. Result 5 of Independence of events and variables states it for all random variables and proves it for discrete ones; the general proof belongs to measure-theoretic probability. They share one distribution, since P(g(X_i) \le t) = P\big(X_i \in \{x : g(x) \le t\}\big) is the same for every i. Since |y| \le 1 + y^2, a finite E(g(X_1)^2) gives a finite mean, and then a finite variance by Result 1 of Variance and covariance, so Result 2 applies to the terms g(X_i). For (a), take g = \mathbf{1}_{(-\infty, x]}: then g(X_i) indicates X_i \le x, its mean is F_X(x), and g^2 = g. For (b), take g = (b - a)h; by Result 1 of Expectation, linearity and indicators, \displaystyle E(g(U_1)) = (b - a)\int_a^b \frac{h(x)}{b - a} \, dx = \int_a^b h(x) \, dx, and E(g(U_1)^2) = (b - a)\int_a^b h(x)^2 \, dx is finite.

Result 5. Fix \varepsilon > 0. By continuity at (a, b) there is a \delta > 0 such that |y - a| < \delta and |z - b| < \delta together force |g(y, z) - g(a, b)| < \varepsilon. So the event \{|g(Y_n, Z_n) - g(a, b)| \ge \varepsilon\} lies inside \{|Y_n - a| \ge \delta\} \cup \{|Z_n - b| \ge \delta\}, and the union bound (Result 6 of Probability axioms and sample spaces) gives

\begin{aligned}&P(|g(Y_n, Z_n) - g(a, b)| \ge \varepsilon) \\ &\quad \le P(|Y_n - a| \ge \delta) + P(|Z_n - b| \ge \delta),\end{aligned}

which tends to 0. For one sequence, drop Z_n. Sums and products are continuous everywhere. The function equal to \displaystyle \frac{y}{z} for z \ne 0 and to any chosen value for z = 0 agrees with \displaystyle \frac{y}{z} on a neighborhood of (a, b) when b \ne 0, so it is continuous there.

Result 6. Not proved here. Khinchin’s law is proved by cutting each X_i off at a level that grows with n and treating the two pieces separately; the strong law needs the tools of measure-theoretic probability. Both are beyond this course.

Worked examples

Example 1

The rightmost splat

Leah’s practice board is 8 feet wide, and each of her shots splats at a distance from the left edge that is \operatorname{Uniform}(0, 8), independently. Let M_n be the distance of the rightmost of the first n splats. Show that M_n \xrightarrow{P} 8, find P(|M_n - 8| \ge 0.2) for n = 100, and find the least n that makes it at most 0.01.

Solution

This is not an average, so we use the definition. Since M_n \le 8 always, |M_n - 8| \ge \varepsilon is the event M_n \le 8 - \varepsilon. For 0 < \varepsilon < 8, the rightmost splat is at most 8 - \varepsilon exactly when every splat is, and the splats are independent, so

P(M_n \le 8 - \varepsilon) = \Big(1 - \frac{\varepsilon}{8}\Big)^n,

which tends to 0 because the base lies between 0 and 1. For \varepsilon \ge 8 the event is M_n \le 0, of probability 0. So M_n \xrightarrow{P} 8.

With \varepsilon = 0.2 the base is 0.975, and 0.975^{100} \approx 0.0795. The condition 0.975^n \le 0.01 means \displaystyle n \ge \frac{\ln 0.01}{\ln 0.975} \approx 181.9, since dividing by the negative \ln 0.975 reverses the inequality. So n = 182 shots.

Example 2

Jams per game

The number J of times Owen’s marker jams in a game has P(J = 0) = 0.45, P(J = 1) = 0.35, P(J = 2) = 0.15 and P(J = 3) = 0.05, independently from game to game. Over n games, find the limits in probability of the average number of jams, of the proportion of jam-free games, and of \displaystyle \frac1n \sum J_i^2. For n = 400, bound the chance that each of the first two misses its limit by 0.1 or more.

Solution

From the pmf,

\begin{aligned}E(J) &= 0.35 + 0.30 + 0.15 = 0.8, \\ E(J^2) &= 0.35 + 0.60 + 0.45 = 1.4,\end{aligned}

and \operatorname{Var}(J) = 1.4 - 0.64 = 0.76. The J_i are iid with finite variance, so by Result 2 the average converges in probability to 0.8. A game is jam-free with probability 0.45, so by Result 3 the proportion of jam-free games converges to 0.45. Since J \le 3, E(J^4) is finite, and Result 4 with g(j) = j^2 gives \displaystyle \frac1n \sum J_i^2 \xrightarrow{P} 1.4.

With n = 400 and \varepsilon = 0.1, Result 2 bounds the first miss by \displaystyle \frac{0.76}{400(0.01)} = 0.19, and Result 3 bounds the second by \displaystyle \frac{0.45(0.55)}{400(0.01)} = \frac{0.2475}{4} \approx 0.0619. The second is smaller because an indicator varies less than the jam count.

Example 3

Estimating pi from splats

A square board 2 feet on a side has a circle of radius 1 foot drawn at its center. Model each splat as landing at a point uniform over the square, independently. Show that four times the proportion \hat{p}_n of splats inside the circle converges in probability to \pi, and find how many splats make Chebyshev’s bound on P(|4\hat{p}_n - \pi| \ge 0.01) at most 0.05.

Solution

A uniform point on the square has joint density \displaystyle \frac14 there, so a region’s probability is its area over 4, and the circle’s is \displaystyle p = \frac{\pi}{4}. By Result 3, \displaystyle \hat{p}_n \xrightarrow{P} \frac{\pi}{4}, and Result 5 with g(y) = 4y gives 4\hat{p}_n \xrightarrow{P} \pi.

By Result 2 of Variance and covariance, \displaystyle \operatorname{Var}(4\hat{p}_n) = \frac{16p(1 - p)}{n}, and \displaystyle 16 \cdot \frac{\pi}{4}\big(1 - \frac{\pi}{4}\big) = 4\pi - \pi^2 \approx 2.6968. Chebyshev’s inequality (Result 3 of Markov and Chebyshev inequalities) gives

P(|4\hat{p}_n - \pi| \ge 0.01) \le \frac{4\pi - \pi^2}{0.0001n},

which is at most 0.05 when \displaystyle n \ge \frac{4\pi - \pi^2}{0.000005} \approx 539{,}353.2. So n = 539{,}354 splats suffice. The tolerance enters squared: one more correct digit of \pi multiplies this n by 100, because the standard deviation of the estimate falls only like \displaystyle \frac{1}{\sqrt{n}}.

Example 4

The sample variance settles

Leah’s chronograph records the velocities V_1, V_2, \dots of her shots, iid with mean \mu, variance \sigma^2 and E(V_1^4) finite. Prove that the sample variance \displaystyle \frac1n \sum_{i=1}^n (V_i - \bar{V}_n)^2 converges in probability to \sigma^2, and that the same holds with n - 1 in place of n.

Solution

Expanding the square and using \sum V_i = n\bar{V}_n,

\begin{aligned}\sum_{i=1}^n (V_i - \bar{V}_n)^2 &= \sum V_i^2 - 2\bar{V}_n \sum V_i + n\bar{V}_n^2 \\ &= \sum V_i^2 - n\bar{V}_n^2,\end{aligned}

so the sample variance is A_n - \bar{V}_n^2 with \displaystyle A_n = \frac1n \sum V_i^2. Result 4 with g(v) = v^2, whose square has the finite mean E(V_1^4), gives A_n \xrightarrow{P} E(V_1^2) = \sigma^2 + \mu^2. Result 2 gives \bar{V}_n \xrightarrow{P} \mu. The function g(y, z) = y - z^2 is continuous, so Result 5 gives

A_n - \bar{V}_n^2 \xrightarrow{P} \sigma^2 + \mu^2 - \mu^2 = \sigma^2.

With n - 1 the statistic is \displaystyle \frac{n}{n - 1} times this one. The constants \displaystyle \frac{n}{n - 1} tend to 1, so they converge in probability to 1, and Result 5 with g(y, z) = yz gives the limit \sigma^2 again.

Example 5

Back-to-back hits

Owen hits each shot with probability 0.4, independently. Let Y_i be 1 if shots i and i + 1 both hit, and 0 otherwise. Show that the proportion \displaystyle \frac1n \sum_{i=1}^n Y_i of back-to-back hits among the first n + 1 shots converges in probability to 0.16, though the Y_i are not independent, and bound the chance that it misses 0.16 by 0.05 or more when n = 1000.

Solution

With H_i the indicator of a hit on shot i, Y_i = H_i H_{i+1}, so E(Y_i) = 0.4^2 = 0.16 by independence of the shots. Neighbors Y_i and Y_{i+1} both need shot i + 1, so Result 2 does not apply directly; we use Result 1.

The product Y_i Y_j indicates that every shot in \{i, i + 1, j, j + 1\} hits. If |i - j| \ge 2 these are four different shots, E(Y_i Y_j) = 0.4^4 = E(Y_i)E(Y_j), and the covariance is 0. If j = i + 1 they are three shots, so

\operatorname{Cov}(Y_i, Y_{i+1}) = 0.4^3 - 0.4^4 = 0.0384.

Also Y_i^2 = Y_i, so \operatorname{Var}(Y_i) = 0.16 - 0.0256 = 0.1344. Result 4 of Variance and covariance has n variance terms and n - 1 neighboring pairs, each counted twice:

\operatorname{Var}\Big(\sum_{i=1}^n Y_i\Big) = 0.1344n + 0.0768(n - 1).

The proportion has mean 0.16 and variance at most \displaystyle \frac{0.2112}{n}, which tends to 0, so Result 1 gives convergence in probability to 0.16. At n = 1000 the variance of the sum is 134.4 + 76.7232 = 211.1232, the proportion’s variance is 0.0002111232, and Result 1 bounds the miss by \displaystyle \frac{0.0002111232}{0.0025} \approx 0.0844. Dependence did no harm because it reached only one step.

Boundaries

A run of outcomes is not covered by Result 2. The weak law bounds one probability for each n; it does not say that the averages along one infinite run converge. That is the strong law, Result 6(b).

The sum does not settle. \operatorname{Var}(S_n - n\mu) = n\sigma^2 grows without bound. A surplus of hits is not paid back by later misses; it is diluted by the division by n, as the school lesson The law of large numbers and the gambler's fallacy shows with counts (Exercise 15 makes this exact).

A mean is needed. If the X_i are iid with the Cauchy density \displaystyle \frac{1}{\pi(1 + x^2)}, then E(|X_1|) is infinite, and \bar{X}_n has that same Cauchy density for every n. We state this without proof; it is proved with characteristic functions in a graduate probability course. So \displaystyle P(|\bar{X}_n| \ge 1) = \frac12 for every n and the average settles on nothing.

Some independence is needed. If X_1 = X_2 = X_3 = \cdots, then \bar{X}_n = X_1 for every n, which converges in probability to a constant only if X_1 is constant. Example 5 shows that dependence between neighbors is harmless; what Result 1 needs is \operatorname{Var}(\bar{X}_n) \to 0.

No rate comes with Result 6. Result 2 gives the rate \displaystyle \frac{\sigma^2}{n\varepsilon^2}, so it tells us how large n must be. Result 6(a) says only that the miss probability tends to 0, and without a variance it gives no n for a stated tolerance and confidence.

Where this goes next

The law says \bar{X}_n - \mu \to 0 in probability, and the standard deviation \displaystyle \frac{\sigma}{\sqrt{n}} says how fast the error shrinks. The The central limit theorem, proved magnifies the error by \displaystyle \sqrt{n} and finds a normal shape: \displaystyle \frac{\sqrt{n}(\bar{X}_n - \mu)}{\sigma} is approximately N(0, 1), proved through Moment generating functions, which also replace Chebyshev’s bound by one that falls exponentially in n. In Markov chains the steps are dependent, yet the share of time a chain spends in a state settles on its stationary probability, a law of large numbers of the same kind. In statistics, an estimate that converges in probability to its target is called consistent; Examples 2 and 4 show that averages, frequencies and the sample variance are consistent.

Exercises

Convergence in probability

  1. The times, in minutes, that n players take to reach the flag are iid \operatorname{Exponential}(0.5). Let Y_n be the fastest time. Find P(Y_n \ge \varepsilon) for \varepsilon > 0 and show that Y_n \xrightarrow{P} 0. For n = 40 find P(Y_n \ge 0.1), and find the least n with P(Y_n \ge 0.1) \le 0.01.
  2. Leah estimates Owen’s hit probability p = 0.35 by \displaystyle Y_n = \frac{N_n}{n + 1}, where N_n \sim \operatorname{Binomial}(n, p) counts his hits in n shots. Find E(Y_n) and \operatorname{Var}(Y_n), use Result 1 to show Y_n \xrightarrow{P} 0.35, and evaluate Result 1’s bound on P(|Y_{99} - 0.35| \ge 0.1).

Averages, frequencies and sampling

  1. Owen hits each shot with probability 0.35, independently. Bound the probability that over 2000 shots his proportion of hits \hat{p} misses 0.35 by 0.03 or more, and give the bound that holds whatever the hit probability is. To what does \displaystyle \frac{\hat{p}}{1 - \hat{p}} converge in probability as the number of shots grows?
  2. The number K of opponents Leah eliminates in a game has P(K = 0) = 0.2, P(K = 1) = 0.4, P(K = 2) = 0.3 and P(K = 3) = 0.1, independently across games. Find the limit in probability of her average over n games, bound the chance that the average over 900 games misses it by 0.1 or more, and find the least n for which Result 2’s bound with \varepsilon = 0.05 is at most 0.02.
  3. Shot velocities are iid N(285, 64) in feet per second, and the field limit is 300. To what does the proportion of shots over the limit converge in probability? Bound the chance that over 1000 shots it misses that limit by 0.01 or more.
  4. The distance R, in inches, from the center of the target to a splat has density \displaystyle f_R(r) = \frac{2r}{9} for 0 \le r \le 3, independently for each shot. Find the limits in probability of \displaystyle \frac1n \sum R_i^2 and of \bar{R}_n^2, and explain the difference.
  5. Let U_1, U_2, \dots be iid \operatorname{Uniform}(0, 1) and G_n = (U_1 U_2 \cdots U_n)^{1/n}. Show that G_n \xrightarrow{P} e^{-1} \approx 0.368.
  6. To estimate I = \int_0^2 e^{-x} \, dx, take iid U_i \sim \operatorname{Uniform}(0, 2) and \displaystyle I_n = \frac2n \sum_{i=1}^n e^{-U_i}. Find I and \operatorname{Var}(2e^{-U_1}), and the least n for which Chebyshev’s bound on P(|I_n - I| \ge 0.01) is at most 0.05.
  7. Shots hit independently with probability \displaystyle \frac12. Let Z_i = H_i(1 - H_{i+1}) indicate a hit on shot i followed by a miss. Find E(Z_i), \operatorname{Var}(Z_i), \operatorname{Cov}(Z_i, Z_{i+1}) and \operatorname{Var}(Z_1 + \dots + Z_n). Show that \displaystyle \frac1n \sum Z_i \xrightarrow{P} \frac14 and bound \displaystyle P\big(\big|\frac1n \sum Z_i - \frac14\big| \ge 0.02\big) for n = 1000.
  8. Let X have density \displaystyle \frac{3}{2x^{5/2}} for x \ge 1, and 0 otherwise. Check that it is a density, find E(X), and show E(X^2) is infinite. For iid copies of X, which result gives the limit of \bar{X}_n, and what is it?

Proofs

  1. Let Y_n = n with probability \displaystyle \frac1n and Y_n = 0 otherwise. Prove that Y_n \xrightarrow{P} 0, although E(Y_n) = 1 for every n and \operatorname{Var}(Y_n) \to \infty.
  2. Prove that limits in probability are unique: if Y_n \xrightarrow{P} c and Y_n \xrightarrow{P} d, then c = d.
  3. Let |Y_n| \le M at every outcome, for every n, and let Y_n \xrightarrow{P} c. Prove that E(Y_n) \to c.
  4. Let X_1, X_2, \dots be pairwise uncorrelated with common mean \mu and variances \sigma_i^2 such that \displaystyle \frac{1}{n^2} \sum_{i=1}^n \sigma_i^2 \to 0. Prove that \bar{X}_n \xrightarrow{P} \mu. Show the condition holds when \displaystyle \sigma_i^2 = \sqrt{i} and fails when \sigma_i^2 = i.
  5. Refute the claim that whenever \bar{X}_n \xrightarrow{P} \mu, also S_n - n\mu \xrightarrow{P} 0.
  6. Let X_1, X_2, \dots be iid with E(X_1^2) finite, and M_n = \max(|X_1|, \dots, |X_n|). Prove that \displaystyle \frac{M_n}{n} \xrightarrow{P} 0.
Answers
  1. The fastest time is at least \varepsilon exactly when every time is, so P(Y_n \ge \varepsilon) = (e^{-0.5\varepsilon})^n = e^{-n\varepsilon/2}, which tends to 0; since Y_n \ge 0, this is P(|Y_n - 0| \ge \varepsilon). For n = 40, e^{-2} \approx 0.1353. And e^{-0.05n} \le 0.01 when n \ge 20\ln 100 \approx 92.1, so n = 93.
  2. \displaystyle E(Y_n) = \frac{np}{n + 1} \to p and \displaystyle \operatorname{Var}(Y_n) = \frac{np(1 - p)}{(n + 1)^2} \to 0, so Result 1 applies. At n = 99, E(Y_{99}) = 0.3465, \displaystyle \operatorname{Var}(Y_{99}) = \frac{99(0.2275)}{10{,}000} = 0.00225225, and the bound is \displaystyle \frac{0.00225225 + 0.0035^2}{0.01} = 0.22645.
  3. Result 3: \displaystyle \frac{0.2275}{2000(0.0009)} = \frac{0.2275}{1.8} \approx 0.126; whatever the hit probability, \displaystyle \frac{1}{4(2000)(0.0009)} = \frac{1}{7.2} \approx 0.139. The function \displaystyle \frac{y}{1 - y} is continuous at 0.35, so by Result 5 the odds converge to \displaystyle \frac{0.35}{0.65} = \frac{7}{13} \approx 0.538.
  4. E(K) = 0.4 + 0.6 + 0.3 = 1.3 and E(K^2) = 0.4 + 1.2 + 0.9 = 2.5, so \operatorname{Var}(K) = 2.5 - 1.69 = 0.81, and the average converges to 1.3. Bound: \displaystyle \frac{0.81}{900(0.01)} = 0.09. Then \displaystyle \frac{0.81}{0.0025n} \le 0.02 when n \ge 16{,}200.
  5. The limit is p = P(V > 300) = P(Z > 1.875) \approx 0.0304 by Result 3 (The normal distribution). Bound: \displaystyle \frac{p(1 - p)}{1000(0.0001)} \approx 0.295, a weak guarantee because the tolerance is a third of p itself.
  6. \displaystyle E(R^2) = \frac29 \int_0^3 r^3 \, dr = \frac29 \cdot \frac{81}{4} = 4.5, the limit of \displaystyle \frac1n \sum R_i^2 by Result 4. \displaystyle E(R) = \frac29 \int_0^3 r^2 \, dr = 2, so \bar{R}_n^2 \xrightarrow{P} 4 by Results 2 and 5. The difference is \operatorname{Var}(R) = 0.5: the mean of the square is not the square of the mean.
  7. \displaystyle \ln G_n = \frac1n \sum \ln U_i, with \ln U_i finite except on an event of probability 0. E(\ln U_1) = \int_0^1 \ln u \, du = -1 and E\big((\ln U_1)^2\big) = \int_0^1 (\ln u)^2 \, du = 2 is finite, so Result 4 gives \ln G_n \xrightarrow{P} -1, and Result 5 with the continuous e^y gives G_n \xrightarrow{P} e^{-1}.
  8. I = 1 - e^{-2} \approx 0.8647. \displaystyle E\big((2e^{-U_1})^2\big) = \frac12 \int_0^2 4e^{-2x} \, dx = 1 - e^{-4}, so the variance is 1 - e^{-4} - (1 - e^{-2})^2, which simplifies to 2e^{-2}(1 - e^{-2}) \approx 0.2340. Chebyshev: \displaystyle \frac{0.2340}{0.0001n} \le 0.05 when n \ge 46{,}807.9, so n = 46{,}808.
  9. \displaystyle E(Z_i) = \frac14 and Z_i^2 = Z_i, so \displaystyle \operatorname{Var}(Z_i) = \frac14 - \frac{1}{16} = \frac{3}{16}. Z_i Z_{i+1} contains H_{i+1}(1 - H_{i+1}) = 0, so \displaystyle \operatorname{Cov}(Z_i, Z_{i+1}) = 0 - \frac{1}{16} = -\frac{1}{16}; terms two or more apart involve four different shots and have covariance 0. So the variance of Z_1 + \dots + Z_n is \displaystyle \frac{3n}{16} - \frac{2(n - 1)}{16} = \frac{n + 2}{16}, the average has variance \displaystyle \frac{n + 2}{16n^2} \to 0, and Result 1 gives the limit \displaystyle \frac14. For n = 1000: \displaystyle \frac{1002}{16{,}000{,}000(0.0004)} = \frac{1002}{6400} \approx 0.157.
  10. \displaystyle \int_1^\infty \frac32 x^{-5/2} \, dx = 1, and the density is nonnegative. \displaystyle E(X) = \frac32 \int_1^\infty x^{-3/2} \, dx = 3, but \displaystyle E(X^2) = \frac32 \int_1^\infty x^{-1/2} \, dx diverges. Result 2 needs a finite variance, so it does not apply; Result 6(a) gives \bar{X}_n \xrightarrow{P} 3.
  11. Y_n takes only the values 0 and n, so for \varepsilon > 0, \displaystyle P(|Y_n| \ge \varepsilon) \le P(Y_n = n) = \frac1n \to 0. Yet \displaystyle E(Y_n) = n \cdot \frac1n = 1 and E(Y_n^2) = n, so \operatorname{Var}(Y_n) = n - 1 \to \infty. Convergence in probability does not force the means to converge, and the converse of Result 1 is false.
  12. Suppose c \ne d and let \displaystyle \varepsilon = \frac{|c - d|}{2} > 0. Since |c - d| \le |Y_n - c| + |Y_n - d|, at every outcome |Y_n - c| \ge \varepsilon or |Y_n - d| \ge \varepsilon. By the union bound, 1 \le P(|Y_n - c| \ge \varepsilon) + P(|Y_n - d| \ge \varepsilon) for every n, but the right side tends to 0, a contradiction.
  13. Fix \varepsilon > 0 and let A = \{|Y_n - c| \ge \varepsilon\}. Since |Y_n - c| \le M + |c|, at every outcome |Y_n - c| \le \varepsilon + (M + |c|)\mathbf{1}_A. Monotonicity, applied to \pm(Y_n - c), gives |E(Y_n) - c| \le E(|Y_n - c|) \le \varepsilon + (M + |c|)P(A). As P(A) \to 0, |E(Y_n) - c| < 2\varepsilon for all large n. As \varepsilon was arbitrary, E(Y_n) \to c.
  14. E(\bar{X}_n) = \mu, and with all covariances 0, Results 4 and 2 of Variance and covariance give \displaystyle \operatorname{Var}(\bar{X}_n) = \frac{1}{n^2} \sum \sigma_i^2 \to 0, so Result 1 applies. For \displaystyle \sigma_i^2 = \sqrt{i}, each term is at most \displaystyle \sqrt{n}, so \displaystyle \frac{1}{n^2}\sum \sqrt{i} \le \frac{n\sqrt{n}}{n^2} = \frac{1}{\sqrt{n}} \to 0. For \sigma_i^2 = i, \displaystyle \frac{1}{n^2} \cdot \frac{n(n + 1)}{2} \to \frac12, not 0, so Result 1 gives nothing.
  15. Let the X_i indicate hits on independent shots with probability \displaystyle \frac12. By Result 3, \displaystyle \bar{X}_n \xrightarrow{P} \frac12. For odd n, S_n is an integer and \displaystyle \frac{n}{2} is not, so \displaystyle |S_n - \frac{n}{2}| \ge \frac12 at every outcome: \displaystyle P(|S_n - \frac{n}{2}| \ge \frac12) = 1 for every odd n, which does not tend to 0.
  16. Fix \varepsilon > 0. The event \{M_n \ge n\varepsilon\} is the union of the events \{|X_i| \ge n\varepsilon\}, so the union bound and Result 2 of Markov and Chebyshev inequalities with r = 2 give
\begin{aligned}P(M_n \ge n\varepsilon) &\le nP(|X_1| \ge n\varepsilon) \\ &\le n \cdot \frac{E(X_1^2)}{n^2\varepsilon^2} = \frac{E(X_1^2)}{n\varepsilon^2},\end{aligned}

which tends to 0. Since \displaystyle \frac{M_n}{n} \ge 0, this is \displaystyle P\big(\big|\frac{M_n}{n}\big| \ge \varepsilon\big).

math.wiki · CC-BY-SA-4.0