23: Law of Large Numbers

Today: Law of Large Numbers

Goal: start to understand error as it relates to sample size

Objectives:

• Distribution of the mean ${\overline{X}}_n$
• Chebyshev’s Inequality
• Law of Large Numbers

i.i.d.

i.i.d.

Let $X_1,X_2,X_3,...$ be an independent and identically distributed sequence of random variables (denoted ``i.i.d’’)

• each $X_i$ is independent of each other
• each $X_i$ has mean $\mu$
• each $X_i$ has variance ${\sigma }^2$

Let us now seek the distribution of the mean $${\overline{X}}_n={\displaystyle \frac{X_1+X_2+...+X_n}{n}}$$

• expected value
• variance

Distribution of Mean

Distribution of Mean

If ${\overline{X}}_n$ is the mean of $n$ independent and identical random variables, each with mean $\mu$ and variance ${\sigma }^2$, then we can describe the distribution of ${\overline{X}}_n$ with

$$\text{E}[{\overline{X}}_n]=\mu \text{and}\text{Var}({\overline{X}}_n)={\displaystyle \frac{{\sigma }^2}{n}}$$

Far from the Mean

Far from the Mean

Idea: we can get a sense of the probability that, for a particular boundary location $a$, an observation lies outside of the interval $$(\mu -a,\mu +a)$$

• $\mu$: population average
• $a$: tolerance

Claim: $P(|X-\mu |\ge a)\le {\displaystyle \frac{\text{Var}(X)}{a^2}}$

Chebyshev’s Inequality

Chebyshev’s Inequality

For a random variable $X$ and boundary location $a$, $$P(|X-\mu |\ge a)\le {\displaystyle \frac{\text{Var}(X)}{a^2}}$$

That is, if we know the variance of a distribution, we can compute an upper bound for the probability of rare events!

Law of Large Numbers

The Law of Large Numbers basically combines Chebyshev’s Inequality with the earlier work for the distribution of the mean:

• $\text{E}[{\overline{X}}_n]=\mu \text{and}\text{Var}({\overline{X}}_n)={\displaystyle \frac{{\sigma }^2}{n}}$
• $P(|X-\mu |\ge a)\le {\displaystyle \frac{\text{Var}(X)}{a^2}}$

Idea: What happens when we observe a lot of data?

Law of Large Numbers

Taking the limit as $n$ goes to infinity, we arrive at the Law of Large Numbers:

$${\displaystyle \underset{n\to \mathrm{\infty }}{lim}P(|{\overline{X}}_n-\mu |\ge a)\le {\displaystyle \underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{{\sigma }^2}{a^{2}n}=0}}}$$

That is, the probability that the mean of a sample of random variables is ``far’’ from the inherent expected value eventually goes to zero.

Nerdy Example

How many numbers between zero and one do we have to add up to have a sum that is greater than one?

• Let $X_i\sim U(0,1)$ be i.i.d.
• Let $Y$ be the amount of $X_i$ added together to get a sum greater than one
• For a conservative estimate, suppose $Y\sim U(2,6)$, then

$$\text{Var}(Y)={\displaystyle \frac{4}{3}}$$ - Empirically (i.e. computer simulation), we saw convergence toward

$${\overline{Y}}_n=e\approx 2.7183$$

How many trials are needed so that the simulations converge to a mean within 0.01 of the true answer with at least 95 percent probability?

Looking Ahead

• due Fri., Mar. 24:

  • LHW8

• no lecture on Mar. 24, Apr. 3

• Exam 2 will be on Mon., Apr. 10

tweet source