# Sample average L1 convergence speed

Say $$X_1, \cdots, X_n$$ are i.i.d random variables with mean zero, let $$S_n = \sum_{i=1}^n X_i$$, we know by SLLN $$\frac{S_n}{n}\rightarrow 0\text{ a.s}$$

We could further know that the sequence of random variables $$\{\frac{S_n}{n}\}$$ are uniformly integrable. Hence u.i + converge in prob(weaker than a.s) implies that $$\mathbb{E}\left(\left|\frac{S_n}{n}\right|\right)\rightarrow 0$$

For classical large deviation theory, such as Cramer's rule(though for r.vs that has moment generating function existed), and roughly speaking, it tells us the speed of the probability convergence, $$P\left(\frac{S_n}{n}\in A\right) \sim e^{-nI(A)}$$(Please forgive me not rigorous here).

So for the L1 convergence as I mentioned above, could we have a convergence speed statement? Such as $$\mathbb{E}\left(\left|\frac{S_n}{n}\right|\right)= O(\frac{1}{n})$$(I just pick one decreasing order as $$O(\frac{1}{n})$$, it definitely could be something else)

I would like to find the result of the above type. Could anyone give me a hint on what literature or paper should I look at?

$$\newcommand{\ep}{\epsilon}$$Somehow, I have only now recalled about Latala's inequalities for moments of the sums of positive independent random variables (r.v.'s), which, in particular, allow one to easily obtain the order of magnitude of $$E|S_n|$$.

Indeed, by the Marcinkiewicz--Zygmund inequalities, $$\begin{equation*} E|S_n|\asymp E\Big(\sum_1^n X_i^2\Big)^{1/2}, \end{equation*}$$ where $$a\asymp b$$ means that $$a/C\le b\le Ca$$ for some universal real constant $$C>0$$.

By Latala's Theorem 1 (with $$X_i^2$$ in place of $$X_i$$ in that theorem), $$\begin{equation*} E\Big(\sum_1^n X_i^2\Big)^{1/2}\asymp b_n^{1/2}, \end{equation*}$$ where $$\begin{equation*} b_n:=\inf\{t>0\colon E\sqrt{1+X^2/t}\le e^{1/(2n)}\} \tag{-1} \end{equation*}$$ and $$X:=X_1$$.

Thus, $$\begin{equation*} E|S_n|\asymp b_n^{1/2}, \tag{0} \end{equation*}$$ which determines $$E|S_n|$$ up to a universal real constant factor.

In particular, this implies $$\begin{equation*} E\Big|\frac{S_n}n\Big|\to0\tag{1} \end{equation*}$$ whenever $$E|X|<\infty$$. Indeed, for real $$t>0$$, let $$\begin{equation*} Y_t:=(\sqrt{1+X^2/t}-1)\sqrt t. \end{equation*}$$ Then $$0\le Y_t\le|X|$$ and $$Y_t\to0$$ (since $$0\le Y_t\le X^2/(2\sqrt t))$$. So, by the condition $$E|X|<\infty$$ and dominated convergence, $$\begin{equation*} EY_t\to0 \end{equation*}$$ as $$t\to\infty$$. So, for each real $$\ep>0$$ and all large enough $$n$$ (depending on $$\ep$$), letting $$t=(2\ep n)^2$$, we have $$EY_t\le\ep$$, that is, $$\begin{equation*} E\sqrt{1+X^2/t}\le1+\ep/\sqrt t=1+1/(2n) In view of (-1), this yields $$\begin{equation*} b_n\le(2\ep n)^2. \end{equation*}$$ So, (0) implies $$\begin{equation*} \limsup_n E\Big|\frac{S_n}n\Big|\le2C\ep \end{equation*}$$ for some real $$C>0$$ and every $$\ep>0$$. Thus, (1) follows.

Using (0), one can show that actually the bound $$c_n$$ on $$E\big|\frac{S_n}n\big|$$ in formula (2) in my other answer here is optimal up to a universal real constant factor, that is, one has $$\begin{equation*} E|S_n|\asymp nc_n, \tag{2} \end{equation*}$$ provided that $$P(X=0)<1$$.

Indeed, by Jensen's inequality, $$E|S_n|=E|S_n^X|\le E|S_n^Z|=E|S_n^X-S_n^Y|\le2E|S_n|$$, where $$S_n^X,S_n^Y,S_n^Z$$ are as in my other answer on this page. So, (2) can be rewritten as $$\begin{equation*} E|S_n^Z|\asymp nc_n. \tag{2Z} \end{equation*}$$ Also, by (0), $$\begin{equation*} E|S_n^Z|\asymp\sqrt{b_n^Z}, \tag{0Z} \end{equation*}$$ where $$b_n^Z$$ is obtained from $$b_n$$ by replacing $$X$$ by $$Z:=Z_1$$ in the definition (-1) of $$b_n$$.

Next, for real $$u$$ $$\begin{equation*} \sqrt{1+u^2}-1\asymp\min(u^2,|u|)=u^2\,1(|u|\le1)+|u|\,1(|u|>1). \end{equation*}$$ On the other hand (cf. (-1)), $$\begin{equation*} E\sqrt{1+Z^2/b_n^Z}-1=e^{1/(2n)}-1\asymp1/n, \end{equation*}$$ so that $$\begin{equation*} E\frac{Z^2}{b_n^Z}\,1(|Z|\le b_n^Z)+E\frac{|Z|}{\sqrt{b_n^Z}}\,1(|Z|>b_n^Z)\asymp\frac1n, \end{equation*}$$ whence $$\begin{equation*} EZ^2\,1(|Z|\le b_n^Z)\ll\frac{{b_n^Z}}n,\quad E|Z|\,1(|Z|>b_n^Z)\ll\frac{\sqrt{b_n^Z}}n, \end{equation*}$$ where $$a\ll b$$ means $$a\le Cb$$ for some universal positive real constant $$C$$. So, by formula (2) in my other answer on this page, \begin{align*} nc_n&\le K(b_n^Z)\sqrt n+nL(b_n^Z) \\ &=\sqrt{EZ^2\,1(|Z|\le b_n^Z)}\sqrt n+n E|Z|\,1(|Z|>b_n^Z) \\ &\ll\sqrt{\frac{{b_n^Z}}n}\sqrt n+n \frac{\sqrt{b_n^Z}}n =2\sqrt{b_n^Z}. \end{align*} Therefore and in view of formulas (0Z) above and (2) in my other answer on this page, $$\begin{equation*} nc_n\ll\sqrt{b_n^Z}\asymp E|S_n^Z|\le2E|S_n|\ll nc_n. \end{equation*}$$ Thus, formula (2) in this answer has been proved.

• Thank you so much for your two comments. It not only gives me insight but also tools that could be useful to me. I would be really appreciated it if you could share the reference or details about showing $c_n$ is the exact asympototic. Jan 11 '21 at 17:59
• @Robert : I have added the details on the optimality of $c_n$, up to a constant factor. (I don't know if this is anywhere in the existing literature.) Jan 11 '21 at 22:28
• Again, thanks so much for the other half you have added. Jan 12 '21 at 16:02

If (say) $$s:=\sqrt{EX_1^2}<\infty$$ then, by the central limit theorem, $$Z_n:=S_n/n^{1/2}\to sZ\sim N(0,s^2)$$ (as $$n\to\infty$$ in distribution). Also, $$EZ_n^2=s^2<\infty$$ and hence the sequence $$(|Z_n|)$$ is uniformly integrable. So, $$E|Z_n|\to s\,E|Z|=s\sqrt{2/\pi}$$. So, $$E\Big|\frac{S_n}n\Big|=\frac{E|Z_n|}{n^{1/2}}\sim\sqrt{\frac2\pi}\frac s{n^{1/2}}.\tag{0}$$

If you only have $$E|X_1|<\infty$$, then you still have $$E\Big|\frac{S_n}n\Big|\to0,\tag{1}$$ but of course the convergence in (1) can be arbitrarily slow.

Indeed, let $$X_1,X_2,\dots$$ be iid zero-mean random variables, with $$S_n=\sum_1^n X_i$$. Let the sequence $$(Y_1,Y_2,\dots)$$ be an independent copy of $$(X_1,X_2,\dots)$$. Take a real $$a>0$$ and for each natural $$i$$ let $$Z_i:=X_i-Y_i,\quad U_i:=Z_i\,1(|Z_i|\le a),\quad V_i:=Z_i\,1(|Z_i|>a).$$ For each natural $$n$$, let $$S_n^X:=S_n=\sum_1^n X_i,\quad S_n^Y:=\sum_1^n Y_i,\quad S_n^Z:=\sum_1^n Z_i,\quad S_n^U:=\sum_1^n U_i,\quad S_n^V:=\sum_1^n V_i=S_n^Z-S_n^U.$$ Then $$S_n^Z=S_n^X-S_n^Y$$, $$ES_n^Y=0$$, and $$S_n^Z=S_n^U+S_n^V$$. So, by Jensen's inequality and the triangle inequality, $$E|S_n|=E|S_n^X|\le E|S_n^Z|\le E|S_n^U|+E|S_n^V|.$$ Also, the $$Z_i$$'s are symmetrically distributed, and hence so are the $$U_i$$'s. So, $$E|S_n^U|\le\sqrt{E(S_n^U)^2}=\sqrt{Var\,S_n^U}=\sqrt{n\,Var\,U_1} =K(a)\sqrt n,$$ where $$K(a):=\sqrt{EZ_1^2\,1(|Z_1|\le a)}.$$ On the other hand, $$E|S_n^V|\le n E|V_1|=nL(a),$$ where $$L(a):=E|Z_1|\,1(|Z_1|>a).$$ Collecting pieces, we have $$E|S_n|\le K(a)\sqrt n+nL(a),$$ for all real $$a>0$$. Thus, $$E\Big|\frac{S_n}n\Big|\le c_n:=\inf_{a>0}\Big(\frac{K(a)}{\sqrt n}+L(a)\Big).\tag{2}$$ Clearly, for each real $$a>0$$ we have $$\limsup_n c_n\le\limsup_n\Big(\frac{K(a)}{\sqrt n}+L(a)\Big)\le L(a).$$ Now recall that note that $$Z_1=X_1-Y_1$$ and hence $$E|Z_1|\le E|X_1|+E|Y_1|=2E|X_1|<\infty$$. So, $$L(a)\to0$$ as $$a\to\infty$$. It follows that $$\limsup_n c_n\le0$$ and hence $$c_n\to0.$$

Thus, by (2), we do have (1), with the rate $$c_n$$, depending, of course, on the distribution of $$X_1$$.

In particular, if $$s=\sqrt{EX_1^2}<\infty$$, then $$c_n\le\lim_{a\to\infty}\Big(\frac{K(a)}{\sqrt n}+L(a)\Big) =\frac{\sqrt{EZ_1^2}}{\sqrt n}=\frac{s\sqrt2}{\sqrt n},$$ whence $$E\Big|\frac{S_n}n\Big|\le \frac{s\sqrt2}{\sqrt n};$$ cf. (0).

The bound $$c_n$$ in (2) can be a bit improved if -- instead of the symmetrization of the distribution of $$X:=X_1$$ by the formula $$Z:=X-Y$$, where $$Y$$ is an independent copy of $$X$$ -- we use a possibly asymmetric zero-mean truncation of a zero-mean random variable $$X$$ given by relations $$X\,1(-a\le X and $$EX_{a,b}=0$$ for arbitrarily large positive $$a$$ and $$b$$, depending on each other; such a zero-mean truncation always exists -- cf. the bottom paragraph on page 3.

• Thank you for your comments. This definitely helps. How about random variables that do not have variance but only have mean? Jan 8 '21 at 21:42
• @Robert : I have added a consideration of the general case with $EX_1=0$. Jan 10 '21 at 1:18

Theorem 1 (Hsu and Robbins [HR]) Let $$X_1,X_2,\ldots$$ be i.i.d. random variables with finite mean $$\mu$$ and finite variance. Then for all $$\epsilon>0$$, $$\sum_{n=1}^\infty P\bigl(|S_n-n\mu|\ge n \epsilon\bigr) <\infty.$$

the following extension of Theorem 1 is due to Katz [K].

Theorem 2 [K] Let $$X_1,X_2,\ldots$$ be i.i.d. random variables of mean $$\mu$$ satisfying $$E{|X_1|^t}<\infty$$ with $$t\ge 1$$. If $$r>t$$, then, for all $$\epsilon >0$$, $$\sum_{n=1}^\infty n^{r-2} P\bigl(|S_n-n\mu|\ge n^{r/t} \epsilon\bigr) <\infty.$$

A converse of the results in [K] appears in [BK].

Finally I mention two consequences of Theorem 1 from [F]: If you only assume a first moment, convergence in the LLN could be arbitrarily slow. But any specific distribution in $$L^1$$ will satisfy a condition slightly better than $$L^1$$, and then this will imply a rate of convergence in the strong law.

[HR] Hsu, P. L. and Robbins, H., Complete convergence and the law of large numbers, Proc. Nat. Acad. Sci. U.S.A. 33, 1947, 25--31.

[K] Katz, M., The probability in the tail of a distribution, Ann. Math. Statist. 34, 1963, 312--318.

[BK] Baum, L. E., Katz, M., Convergence rates in the law of large numbers, Trans. Amer. Math. Soc. 120 (1965), 108-123.

[F] Feller, William. "A limit theoerm for random variables with infinite moments." American Journal of Mathematics 68, no. 2 (1946): 257-262. https://www.jstor.org/stable/2371837?seq=1#metadata_info_tab_contents