# The law of large numbers: How does the convergence take place? How does the “remainder” look like?

I have the independent and identically distributed random variables $X_1,X_2,\ldots$ with a finite expectation $\mu$. I also have defined $S_n = X_1 + \cdots + X_n$.

According to the law of large numbers, I already know that

$S_n/n \to \mu$ almost surely as $n\to\infty$.

However, my question is: How does the convergence take place? What is the “shape” of this convergence? For example, for a given $N>0$, how close is $S_N/N$ to $\mu$? How does the difference, or remainder/residual, look like?

Are there any results, or theorems, available that tell me these kinds of things?

-

As a very simple example, suppose that the $X_i$ have finite variance $\sigma^2$. Then it is easy to see that $\operatorname{Var}(\frac{S_n}{n}) = \frac{\sigma^2}{n}$, and Chebyshev's inequality gives that for any $\epsilon > 0$, we have $$P\left(\left|\frac{S_n}{n}-\mu\right| > \epsilon\right) \le \frac{\sigma^2}{n \epsilon^2}.$$
@TwoCents: Right. But a consequence of the last line is that $\frac{S_n}{n} \to \mu$ in probability. So you can think of it as a weak law of large numbers with an estimate for the remainder. – Nate Eldredge Mar 18 '12 at 13:46
I consider this a "strong law" type version of Nate's answer. Probably it's a bit crude (it's also a bit late so hopefully this is error-free). Assume finite fourth central moment $\mu_4$ and variacne $\sigma^2$. For fixed $m$ suppose we want to approximate $$P\left(\left|\frac{S_n}{n} - \mu \right| > \epsilon, \mbox{for some n \ge m }\right).$$ Let $Z_i = X_i - \mu$, and note that $\frac {S_n} n - \mu = \frac{\sum_{i = 1} ^ n Z_i} n$. By subadditivity, this is bounded above by $$\sum_{n = m} ^ \infty P\left(\left|\frac{S_n}{n} - \mu \right| > \epsilon\right)$$ and applying Markov's inequality this is bounded by $$\sum_{n = m} ^ \infty \frac{E[\sum_{i = 1} ^ n Z_i]^4}{n^4 \epsilon^4} = \sum_{n = m} ^ \infty \frac{\sum_{1 \le i, j, k, l \le n} E(Z_i Z_j Z_k Z_l)}{n^4 \epsilon^4} = \sum_{n = m} ^ \infty \frac{n\mu_4 + 3n(n-1)\sigma^4}{n^4 \epsilon^4} \le \sum_{n = m} ^ \infty \frac{K}{n^2}$$ for some $K$. So this probability goes down at least as fast as $m^{-1}$, which is the same rate you get in Nate's Chebychev weak-law-based answer, but now our bound ensures that $S_m / m$ gets within $\epsilon$ of $\mu$ and stays there forever with the probability of the complementary event going down like $m^{-1}$.
You can also look at this in terms of the central limit theorem which says that $\sqrt n (S_n / n - \mu)$ converges in distrbution to a standard normal, i.e. blowing up the residual by $\sqrt n$ is the "correct" factor to ensure convergence to something interesting. The law of iterated logarithm may also be of interest.