# Rate of convergence in the Law of Large Numbers

I'm working on a problem where I need information on the size of $E_n=|S_n-n\mu|$, where $S_n=X_1+\ldots+X_n$ is a sum of i.i.d. random variables and $\mu=\mathbb EX_1$. For this to make sense, the $(X_i)$ have to be integrable. In that case, the weak law of large numbers says $E_n/n$ converges to 0 in probability, while the strong law says $E_n=o(n)$ almost surely.

If $X_1$ is square integrable, then we get the (stronger) result $E_n/(n^{1/2+\epsilon})$ converges to 0 in probablility. What I am looking for is a result for the case $\mathbb E|X_1|^\alpha<\infty$ for some $1<\alpha<2$. Back-of-the-envelope calculations suggest a result of the form $E_n=O(n^{1/\alpha+\epsilon})$ holds. I suspect a relationship with $\alpha$-stable laws and have tracked down Gnedenko and Kolmogorov's book, but find (1) their notation is quite hard to read; (2) they seem to mainly care about something that's not so important for me; namely a result of the Central Limit Theorem type. They impose extra conditions under which suitably scaled and translated versions of $S_n$ converge to a non-trivial distribution. I don't want to assume anything beyond an $\alpha$th moment inequality, but am looking for a correspondingly weaker conclusion giving upper bounds on $E_n$.

Can anyone point me to some results about deviation from the mean for sums of iid random variables with $\alpha$th moments ($1<\alpha<2$)?
In a similar vein, what if the random variables fail to have an $\alpha$th moment for some $\alpha<1$. Here I'd expect to see some kind of result telling me that if $S_n/a_n$ converges in probability to a constant for some sequence $(a_n)$, then that constant must be 0.

Edit: Let me give a precise Chebyshev-like statement I would really like to be true. Let $(X_n)$ be iid; $\mathbb EX_1=0$ and $\mathbb E|X_1|^\alpha<\infty$ for some $1<\alpha<2$. Then $\mathbb P(|S_n|>t)<C_\alpha n\mathbb E|X_1|^\alpha/t^\alpha$, where $C_\alpha$ is a constant that only depends on $\alpha$ (I have guessed the bound based on "symbol-bashing" with the $\alpha$-stable law and believe it's at least "dimensionally correct".)

• Maybe I'm confused, but doesn't a CLT-type result give you exactly what you want? In the finite-variance case, the classical CLT says that $(S_n - \mu n)/n^{1/2}$ converges weakly, so as a result $E_n/n^{1/2 + \epsilon} \to 0$ weakly and hence in probability (standard result). So a CLT-type result telling you that $(S_n - \mu n)/ n^{1/\alpha}$ converges in distribution would imply that $E_n / n^{1/\alpha + \epsilon} \to 0$ in probability. – Nate Eldredge Apr 16 '15 at 1:55
• @Nate: Don't you need a second moment condition to apply CLT? – Anthony Quas Apr 16 '15 at 2:05
• Right. In the infinite second moment case, by "CLT-type result" I'm talking about a Kolmogorov-Gnedenko style stable law limit theorem giving the weak convergence of $(S_n - \mu n)/n^{1/\alpha}$ (typically the weak limit is a stable law, not the normal distribution). – Nate Eldredge Apr 16 '15 at 2:06
• Sorry @NateEldredge for the misunderstanding. So yes. I hope that a K-G stable law limit theorem would do the trick. It's just that I did not find a reference for such a theorem that didn't have a bunch of extra conditions (about slowly varying densities etc). If you know where I can find a statement of the type you're mentioning, that will probably resolve (at least the first part of) my issue. – Anthony Quas Apr 16 '15 at 2:19
• I don't know an exact reference either, but I suspect that with a little work you can show that a distribution satisfying $E|X|^\alpha < \infty$ will satisfy the K-G hypotheses. – Nate Eldredge Apr 16 '15 at 2:21

An early occurence of such bounds is in the theorem of Theorem of vonBahr and Eseen

vonBahr, B., Esseen C.-G.: Inequalities for the rth absolute moment of a sum of random variables, $1\leq r \leq 2$. Ann. Math. Statist. 36, No.1, 299-393 (1965).

Theorem: Let $X_i$ be independent (not necessarily i.i.d.) zero mean random variables. Then, for $\alpha\in [1,2]$, $$E|\sum_{i=1}^n X_i|^\alpha\leq C_\alpha \sum_{i=1}^n E|X_i|^\alpha\,.$$ ($C_\alpha$ is explicit)

Applying Markov's inequality in your setup gives $$P(|S_n|>t)\leq C_\alpha n E|X_1|^\alpha t^{-\alpha}$$ as you wanted.

Note: the moment condition certainly does not imply convergence to $\alpha$-stable - one would need some regularly varying conditions on the tail for that.

Note2: A good summary (up to late 70s) of estimates of this kind (mostly from the Russian school) are in Nagaev's Annals of Probability paper (1979). Petrov's 1975 book is also a good resource - in particular the VonBahr-Essen bound is mentioned there (on page 60).

Your exact question seems to be answered by Lenny Baum and Melvin Katz in their 1963 paper. (convergence rates in the law of large numbers)

• Thanks @Igor. This does seem very close to my question. I'll see if I can extract a Chebyshev-like result (which is what I really want) from this. – Anthony Quas Apr 16 '15 at 4:52

If we assume that the $X_i$ are iid in $L^p$ for some $p\in ]1,2[$, then we have:

$$a.e. \ \ {1 \over n} \sum_{k=0}^{n−1} X_k=E(X_0)+o(n^{1/p−1})$$

This follows from the Kolmogorov three series theorem. This is done in the book of Durrett, probability, theory and examples, theorem 2.5.8.

Note that if you are not interested by the exact exponent, then the standard quick $L^2$ proof gives you such an estimate.

• Thanks - but isn't Var$(Y_i)$ infinite? – Anthony Quas Apr 16 '15 at 6:34
• OK. Thanks a lot. I'll look in Durrett tomorrow. – Anthony Quas Apr 16 '15 at 6:46
• @quas the book is on his webpage, I have provided a link. Define $Y_i = X_i {\bf 1}_{|X_i|\leq i^{1/p}} / i^{1/p}$, check that $\sum Var(Y_i)$ is finite, this gives a.e. convergence of $\sum Y_i$, then apply the Kronecker lemma and Borel-Cantelli. – coudy Apr 16 '15 at 6:49
• So I did look at Durrett. I have a paper copy that does not seem to include Thm 2.5.8, but the online version is as you say; and also includes an answer to the other question I asked. Thanks again. – Anthony Quas Apr 16 '15 at 19:13

I guess what you are looking for is a concentration inequality for heavy-tail distributions. How about this one:

Barthe, F., Cattiaux, P., & Roberto, C. (2005). Concentration for independent random variables with heavy tails. Applied Mathematics Research eXpress, 2005(2), 39-60.

Also, please take a look at the Bernstein inequalities.

• Thanks @Taha. So I think Bernstein inequalities are based on exponential moments (which diverge in my setting); I was unable to pick out useful results from the paper by the French authors either. – Anthony Quas Apr 16 '15 at 0:29
• Well, I am pretty sure someone should have derived the concentration inequalities for heavy-tail distributions. I tried to look at this: Robust Estimation of High-Dimensional Mean Regression, but their lemmas require me to read the entire paper to understand. I'll look into the robust statistic literature to see what I can find. – Taha Apr 16 '15 at 4:22