Bernoulli's Theorem

From ProofWiki
(Redirected from Law of Large Numbers)
Jump to navigation Jump to search

Theorem

Let the probability of the occurrence of an event be $p$.

Let $n$ independent trials be made, with $k$ successes.


Then:

$\displaystyle \lim_{n \mathop \to \infty} \frac k n = p$


Also presented as

This result can also be presented in the form:

$\forall \epsilon \in \R_{>0}: \displaystyle \lim_{n \mathop \to \infty} \map \Pr {\size {\frac k n - p} < \epsilon} = 1$


Proof

Let the random variable $k$ have the binomial distribution with parameters $n$ and $p$, that is:

$k \sim \Binomial n p$

where $k$ denotes the number of successes of the $n$ independent trials of the event with probability $p$.


From Expectation of Binomial Distribution:

$\expect k = n p \leadsto \dfrac 1 n \expect k = p$

Linearity of Expectation Function gives:

$ \expect {\dfrac k n} = p =: \mu$


Similarly, from Variance of Binomial Distribution:

$\var k = n p \paren {1 - p} \leadsto \dfrac 1 {n^2} \var k = \dfrac {p \paren {1 - p} } n$

From Variance of Linear Combination of Random Variables:

$\var {\dfrac k n} = \dfrac {p \paren {1 - p} } n =: \sigma^2$


By applying Chebyshev's Inequality to $\dfrac {k} {n}$, we have for any $l>0$:

$\map \Pr {\size {\dfrac k m - \mu} \ge l \sigma} \le \dfrac 1 {l^2}$

Now, let $\epsilon > 0$ and choose $l = \dfrac \epsilon \sigma$, to get:

$\map \Pr {\size {\dfrac k m - \mu} \ge \dfrac \epsilon \sigma \cdot \sigma} \le \dfrac {\sigma^2} {\epsilon^2}$

Simplifying and plugging in the values of $\mu$ and $\sigma^2$ defined above yields:

$\map \Pr {\size {\dfrac k n - p} \ge \epsilon} \le \dfrac {p \paren {1 - p} } {n \epsilon^2}$

Scaling both sides by $-1$ and adding $1$ to both sides yields:

$1 - \map \Pr {\size {\dfrac k n - p} \ge \epsilon} \ge 1 - \dfrac {p \paren {1 - p} } {n \epsilon^2}$

Applying Union of Event with Complement is Certainty to the left hand side:

$\map \Pr {\size {\dfrac k n - p} \le \epsilon} \ge 1 - \dfrac {p \paren {1 - p} } {n\epsilon^2}$

Taking the limit as $n$ approaches infinity on both sides, we have:

$\displaystyle \lim_{n \mathop \to \infty} \map \Pr {\size {\frac k n - p} < \epsilon} = 1$

$\blacksquare$


Also known as

This theorem is also popularly known as the Law of Large Numbers.


Source of Name

This entry was named for Jacob Bernoulli.


Sources