View source for Physics 434, 2016: Law of large numbers

{{PHYS434-2016}}

One of the important results in probability theory is the law of large numbers, which is what we consider in this lecture.

Let's ask the following question. Suppose we have a biased coin, with an unknown probability <math>p</math> for coming heads up (in other words, the coin is a Bernoulli random number, with probability <math>p</math>). The coin is thrown <math>N</math> times, and comes up <math>n</math> times heads up. Clearly, in general, <math>n/N</math> is not going to be exactly <math>p</math> (for starters, <math>n/N</math> is always rational, and <math>p</math> can be arbitrary). But how close will they be? This is a very important question. Indeed, we previously defined the probability as a limit of frequencies for large <math>N</math>. Is our definition self-consistent? Do the frequencies actually converge to probabilities? 

To answer this, let's suppose we have a variable with an expectation value <math>\langle x\rangle</math> and the variance <math>\sigma^2_x</math>. We take samples <math>x_n,\, n=1,\dots,N</math> of this variable. We then define the ''empirical'' mean, or the ''sample'' mean <math>\bar{x}=\frac{1}{N}\sum_{n=1}^N x_n</math>. Note here that we use the notation <math>\langle\cdots\rangle</math> to denote expectation values, and <math>\bar{\cdots}</math> to denote empirical means. Our questions of whether frequencies converge to probabilities is then a special case of a more general question: how close is an expectation value of a variable <math>x</math>, namely <math>\langle x\rangle</math>, to its empirical mean <math>\bar{x}</math>?

This question is easy to answer for a special case of frequencies of Bernoulli variables. Here we can use the fact that the distribution of heads is given by the binomial distribution, <math>B(p,N)</math>. As we showed previously, for the binomial distribution, <math>\mu = pN</math>, so that the frequency becomes <math>f=pN/N=p</math>. Thus, indeed, the frequency converges to the probability. Further, for the binomial distribution, <math>\sigma = \sqrt{Np(1-p)}</math>, and thus the standard deviation of the frequency becomes <math>\sigma_f=\sqrt{p(1-p)/N}</math>. Thus the ratio of the standard deviation of the frequency to its mean is <math>\sigma_f/f=\sqrt{(1-p)/(Np)}</math>. So not only does the frequency of a Bernoulli variable converges to the probability, but the error decreases as about <math>\propto 1/\sqrt{N}</math>. 

Does this result hold more generally, beyond Bernoulli variables? We previously showed that, for independent variables, means and variances ad. Let's use this fact to answer the question. What is the expected value and the standard deviation of the empirical mean? We can write these as <math>\langle \bar{x}\rangle = \frac{1}{N}\langle \sum_{n=1}^N x_n\rangle</math>. Using the law of summation of the means, this becomes <math>\langle \bar{x}\rangle = \frac{1}{N} \sum_{n=1}^N \langle x_n\rangle = \langle x\rangle </math>. Thus the empirical mean converges to the true mean, as long as the true mean exist (for some ''long-tailed'' distributions, means don't exist, as we will see in the homework problem). How quickly does this convergence happen? We now calculate <math>\sigma^2_\bar{x} = \sum_{n=1}^N\sigma^2(x_n/N) = \frac{1}{N^2}\sum_{n=1}^N\sigma^2(x_n)= \frac{\sigma^2_x}{N} </math>. Thus the spread of an expectation value around its empirical mean decreases with the number of samples as <math>\propto 1/\sqrt{N}</math>, provided, of course, that the variance of a single sample is finite.