Law of Large Numbers

Suppose a referendum is to be held and the fraction of voters who support a proposed law will be some unknown value, denoted as $p$. Is there some way to know the actual value of $p$ before the referendum? The answer to this question lies in The Law of Large Numbers.

The Law of Large Numbers

The law of large numbers is one of the most famous probability theorems, and it has a very central role in probability and statistics. In general, the law of large numbers states that the average result of a series of independent random variables with the same distributions will be close to the value expected by the distribution. There are two main types of the law of large numbers. They are the weak and the strong laws of large numbers.

The Weak Law of Large Numbers

The weak law of large numbers simply means that with high probability, the sample mean of independent identically distributed (i.i.d) random variables is getting very close to the true mean as the sample size increases.

This law is very intuitive, so let me provide an example to make it solid. If we are given a fair coin with a probability of a head being 0.5 then by intuition we know that if we throw a coin 100 times we receive around 50 heads. It may not be exactly 50, but it sure will be close to it, and the fraction of heads will be close to 0.5. But if we throw a coin 10,000 times, we might get even closer to a fraction of heads being 0.5. So the law simply means that as the number of trials increases, we will get closer and closer to the true mean, which is 0.5 in our fair coin case.

If our coin is not fair, and we don't know the probability of a head, we can easily get it by throwing and observing how many times we get heads. Simply speaking, the more we throw, the more accurate our estimation of the probability will be.

Let's consider a sequence of independent identically distributed random variables $X_1, X_2, ...X_n$ each having a mean equal to $\mu$ and a variance equal to $\sigma^2$. The sample mean $M_n$ is defined by:

$$M_n ={ {X_1+X_2+...+X_n} \over n}$$Then the expected value of the sample mean is:

$$E[M_n ] = { {E[X_1] + E[X_2]+...+E[X_n] } \over n} = { {n\mu } \over n} = \mu$$And the variance of the sample mean can be derived with help of independence as:

$$var(M_n) = { {var(X_1 + X_2 +...+ X_n)} \over n^2} = { {var(X_1) + var(X_2) +...+ var(X_n) } \over n^2} = { {n\sigma^2} \over n^2} = { {\sigma^2} \over n}$$Now that we know both the expected value and the variance of our sample mean, we can apply Chebyshev inequality:

$$P(|M_n-\mu|\ge \epsilon) \le {{\sigma^2} \over n \epsilon^2}, \quad for \; any \; \epsilon>0$$For any fixed positive $\epsilon$ we can observe, as $n$ gets larger and larger, the right-hand side of the equation goes closer and closer to zero. Thus, with this, we obtain the weak law of large numbers.

The Weak Law of Large Numbers:

Let $X_1, X_2, ...X_n$ be independent identically distributed random variables with the mean equal to $\mu$. Then for every $\epsilon>0$,

$$P(|M_n-\mu|\ge \epsilon) = P(|{ {X_1+X_2+...+X_n} \over n}-\mu|\ge \epsilon) \rightarrow 0, \quad as \; n\rightarrow \infty$$It states that the larger $n$ gets, the higher the probability that $M_n$ (sample mean) will fall within the positive interval $[\mu-\epsilon, \mu+\epsilon]$ around the true mean $\mu$, and as $n\rightarrow \infty$, the probability of $M_n$ (sample mean) converges to the true mean.

The smaller the value of the $\epsilon$, the larger the sample size, which we need to make sure that the sample mean falls within the required interval.

The voting estimation

In order to solve our problem given above, we will follow a couple of simple steps:

1. Gather all the information and assign them to the variables
2. Apply Chebyshev inequality

Now let's go back to our earlier problem. The fraction of voters who support a proposed law is going to be some unknown $p$. We want to know the value of $p$ before the actual referendum. To answer this question, we can sample some amount of people randomly (uniformly and independently) and take their votes to get the sample mean. However, our sample might not be representative of the true population. Thus, that means we might not be able to get the exact value of $p$ from the sample mean. Luckily, as we know from the weak law of large numbers, we can get the probability that our $M_n$ (sample mean) will fall within the positive interval $\epsilon$ around the true mean.

So let's say we would like to know with at least 90% probability that our $M_n$ (sample mean) is accurate within 0.05 of the true mean, which is $p$. That means $\epsilon = 0.05$. The first question to answer is how many voters must be sampled to meet our condition?

Suppose we will randomly choose $n$ number of voters and record the sample mean $M_n$. We will view each voter as an independent identically distributed Bernoulli random variable $X_i$ since voters can vote either to support, which is equal to 1, or vice versa equal to 0. Since it is a Bernoulli random variable, we know that $E[X_i] = \mu= p$ and $var(X_i) = \sigma^2= p(1-p)$. Luckily for us, it is known that $p(1-p) \le 1/4$

Now we can apply Chebyshev inequality as:

$$P(|M_n-p|\ge 0.05) \le {{p(1-p)} \over n(0.05)^2} \le {1 \over 4n(0.05)^2}$$And since we want at least 90% probability, we can do the following:

$${1 \over 4n(0.05)^2} \le 1 - 0.9 = 0.1$$And from the above equation, we get $n \ge 1000$, meaning we need to randomly pick at least 1000 people from the population to be at least 90% confident that our $M_n$ (sample mean) is accurate within 0.05 of the true mean $p$.

Now let's see what will happen if we take $n = 50000$:

$$P(|M_{50000}-p|\ge 0.05) \le {{p(1-p)} \over 50000(0.05)^2} = {1 \over 4(50000)(0.05)^2} = 0.02$$This means that the probability that our $M_n$ (sample mean) will be accurate within 0.05 of the true mean $p$ is more than $1- 0.02 = 0.98$, which is 98%.

So, if we sample 1000 people we can with 90% be sure that the result of the sample mean will be accurate within 0.05 of the true mean $p$ and if we increase our sample size to 50000 people we will be 98% sure.

The Strong Law Of Large Numbers

The weak and the strong law of large numbers are similar in the sense that they both deal with a convergence of the sample mean to the true mean as we increase the sample space.

The Strong Law of Large Numbers:

Let $X_1, X_2, ...X_n$ be independent identically distributed random variables with the mean equal to $\mu$. Then the sample mean $M_n$ converges to the true mean $\mu$, with the probability 1.

$$P\bigl(\lim_{x \to +\infty} M_n \bigl) = P\bigl(\lim_{x \to +\infty} { {X_1+X_2+...+X_n} \over n} = \mu\bigl) = 1$$

Conclusion

Below is a summary of the concepts covered in this topic:

• The law of large numbers states that if we have a sequence of independent random variables with the same distributions, then the average result of these random variables is going to be close to the expected value of the distribution.
• There are the weak laws of large numbers and the strong laws of large numbers.
• The weak and the strong law of large numbers are similar in the sense that they both deal with a convergence of the sample mean to the true mean as we increase the sample space.
• The weak law of large numbers states that as $n$ (sample size) gets larger the higher the probability that $M_n$ (sample mean) will fall within the positive interval $[\mu-\epsilon, \mu+\epsilon]$ around the true mean $\mu$, and as $n\rightarrow \infty$, that probability converges to 1.
• The strong law of large numbers states the sample mean $M_n$ converges to the true mean $\mu$, with the probability 1.

Other examples where the law of large numbers is being implemented are:

• Casinos. From time to time individuals get lucky, but in the long run, the casino always wins.
• Insurance. Thousands of people will pay monthly, but only a few of them will end up needing the insurance.