
> 
> Suppose that $\{X\_{ij}\}\_{1\leqslant i,j\leqslant n}$ are iid random variables with $\mathbb{E}(X\_{11})=0$ and $\mathrm{Var}(X\_{11})=1$, does the following convergence hold:
> $$
> \max\_{1\leqslant j\leqslant n}\biggl\{\frac{1}{n^2}\sum\_{1\leqslant i\neq i'\leqslant n}(X\_{ij}X\_{i'j})\biggr\} \to 0 \qquad \text{almost surely}?
> $$
> 
> 
> 


Comment: I first posted this question on [MSE](https://math.stackexchange.com/questions/4545745/maximal-inequality-of-iid-random-variables-x-ij-1-leqslant-i-j-leqslant), someone suggested me to post it on mathoverflow since it is an open problem.




---


Background
----------


I am reading the AoP paper "*Limit of the smallest eigenvalue of a large dimensional sample covariance matrix*" by Z. Bai and Y. Yin (1993). Their Lemma 2 states a generalization of the well-known Marcinkiewicz-Zygmund strong law of large numbers to the case of multiple arrays of iid random variables.



> 
> **[Lemma 2 in [Bai and Yin (1993)](https://projecteuclid.org/journals/annals-of-probability/volume-21/issue-3/Limit-of-the-Smallest-Eigenvalue-of-a-Large-Dimensional-Sample/10.1214/aop/1176989118.full)]** Let $\{\xi\_{ij},i,j=1,2,\ldots\}$ be a double array of iid random variables and let $\alpha>1/2,\beta\geqslant 0$ and $M$>0 be constants. Then as $n\to\infty$,
> $$
> \max\_{j\leqslant Mn^{\beta}} \biggl|n^{-\alpha}\sum\_{i=1}^n (\xi\_{ij}-c)\biggr|\to0\quad \text{almost surely},
> $$
> if and only if
> $$
> (i)\quad \mathbb{E}|\xi\_{11}|^{(1+\beta)/\alpha}<\infty
> $$
> $$
> (ii)\quad c = \left\{
> \begin{array}{ll}
>  \mathbb{E} \,\xi\_{11},& \text{if }\alpha\leqslant 1, \\
>  \text{any number}, &\text{if }\alpha>1.
> \end{array} 
> \right. 
> $$
> 
> 
> 


By our assumptions and taking $\alpha=\beta=M=1$, $\xi\_i=X\_{ij}^2$ in this lemma, we have
$$
\max\_{j\leqslant n}\biggl|\frac{1}{n}\sum\_{i,j}X\_{ij}^2-1\biggr|\to0\quad \text{almost surely}.
$$
This result is for square terms. I wonder if there is a similar result for the **cross terms**
$$
\max\_{1\leqslant j\leqslant n}\biggl\{\frac{1}{n^2}\sum\_{i\neq i'}(X\_{ij}X\_{i'j})\biggr\} \to 0 \qquad \text{almost surely}?
$$




---


Attempt
-------


I can prove that $(1/n^2)\sum\_{i\neq i'}(X\_{ij}X\_{i'j})\to 0\; a.s.$ for any fixed $j$. But I do not know how to deal with the problem with "$\max$".


For fixed $j$,
$$
\mathrm{Var}\Bigl(\sum\_{i\neq i'}X\_{ij}X\_{i'j}\Bigr)=2\sum\_{i\neq i'}\mathrm{E}\bigl(X\_{ij}^2\bigr)\cdot\mathrm{E}\bigl(X\_{i'j}^2\bigr)=2(n^2-n),
$$
then by Chebyshev's inequality, for any $\varepsilon>0$,
$$
\Pr\biggl(\frac{1}{n^2}\sum\_{i\neq i'}(X\_{ij}X\_{i'j})>\varepsilon\biggr) =O\Bigl(\frac{1}{n^2}\Bigr),
$$
which is summable. Hence, by using the Borel-Cantelli lemma, we have
$$
\frac{1}{n^2}\sum\_{i\neq i'}(X\_{ij}X\_{i'j})\to 0\qquad
 \text{almost surely}.$$


If we consider $\max\_{1\leqslant j\leqslant n}$, and use the trivial inequality to bound it, we have
$$
\Pr\biggl(\max\_{1\leqslant j\leqslant n}\biggl\{\frac{1}{n^2}\sum\_{i\neq i'}(X\_{ij}X\_{i'j})\biggr\}> \varepsilon\biggr)
\leqslant n\cdot \Pr\biggl(\frac{1}{n^2}\sum\_{i\neq i'}(X\_{i1}X\_{i'1})>\varepsilon\biggr)=O\Bigl(\frac{1}{n}\Bigr),$$
which means
$$
\max\_{1\leqslant j\leqslant n}\biggl\{\frac{1}{n^2}\sum\_{i\neq i'}(X\_{ij}X\_{i'j})\biggr\}\to 0\qquad
 \text{in probability}.\tag{\*}
$$


How can we improve the result (\*) to "almost surely"?



Maximal inequality of iid random variables $\{X_{ij}\}_{1\leqslant i,j \leqslant n}$
In the Math Stack Exchange post, I gave a proof based on Lemma 2 in Bai and Yin (1993). I will give an alternative proof.


Expressing $\sum\_{1\leqslant i\neq i'\leqslant n}X\_{i,j}X\_{i',j}$ as
$\left(\sum\_{i=1}^n X\_{i,j}\right)^2-\sum\_{i=1}^nX\_{i,j}^2$ and considering dyadic numbers, we are reduced to show that
$$
\tag{1}\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{n}}\max\_{1\leqslant \ell\leqslant 2^n}\left\lvert \sum\_{i=1}^\ell X\_{i,j}\right\rvert\to 0\mbox{ almost surely}
$$
$$
\tag{2}\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{2n}} \sum\_{i=1}^{2^n} X\_{i,j}^2\to 0\mbox{ almost surely}.
$$
By the Borel-Cantelli lemma, in order to prove (1), it suffices to show that
$$
\tag{1'}\forall\varepsilon>0, \sum\_{n\geqslant 1}\mathbb P\left(\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{n}}\max\_{1\leqslant \ell\leqslant 2^n}\left\lvert \sum\_{i=1}^\ell X\_{i,j}\right\rvert>\varepsilon\right) <\infty$$


which reduces, by a union bound, to prove that
$$
\tag{1''}\forall\varepsilon>0, \sum\_{n\geqslant 1}2^n\mathbb P\left( \frac{1}{2^{n}}\max\_{1\leqslant \ell\leqslant 2^n}\left\lvert \sum\_{i=1}^\ell X\_{i,0}\right\rvert>\varepsilon\right) <\infty$$


Let us prove (1''). Using Corollary 1.5 in [1](https://www.esaim-ps.org/articles/ps/pdf/2019/01/ps180007.pdf) (applied with $r'=r=2$ and $B=\mathbb R$, hence $C\_{r',B}=1$, we know that for each $q>0$, there exist constants $A(q)$ and $B(q)$ such that for each $x>0$ and each independent sequence $(Y\_i)$,
$$
\mathbb P\left(\max\_{1\leqslant \ell\leqslant N}\left\lvert \sum\_{i=1}^\ell Y\_i\right\rvert >x\right)\leqslant A(q)\int\_0^1u^{q-1}\mathbb P\left(\max\_{1\leqslant i\leqslant N}\lvert Y\_i\rvert>xB(q)u\right)du+A(q)x^{-q}\left(\mathbb E\left[Y\_i^2\right]\right)^{q/2}.
$$


Applying this inequality to $Y\_i=X\_{i,0}$, $x=2^n\varepsilon$ and $q=3$ shows that
$$
 \sum\_{n\geqslant 1}2^n\mathbb P\left( \frac{1}{2^{n}}\max\_{1\leqslant \ell\leqslant 2^n}\left\lvert \sum\_{i=1}^\ell X\_{i,0}\right\rvert>\varepsilon\right)\leqslant A(3)\sum\_{n\geqslant 1}2^{2n}\int\_0^1u^{2}\mathbb P\left( \lvert X\_{i,0}\rvert>\varepsilon B(3)2^nu\right)du + A(3)\sum\_{n\geqslant 1}2^{n}2^{-3n/2}\varepsilon^{-3/2}
$$
and finiteness of the first series follows from the elementary fact that $\sum\_{n\geqslant 1}2^{2n}\mathbb P\left(Y>2^n\right)\leqslant 4\mathbb E\left[Y^2\right]$.


(2'') follows from an application of the similar argument as the usual strong law of large number, but the truncation level changes. Let
$Y\_{i,j}=X\_{i,j}^2$ and for a fixed $\varepsilon$ and $n$, let
$$
Z\_{n,i,j}=Y\_{i,j}\mathbf{1} \{Y\_{i,j}\leqslant\varepsilon 2^{2n} \}-\mathbb E\left[Y\_{i,j}\mathbf{1}\{Y\_{i,j}\leqslant\varepsilon 2^{2n}\}\right],
$$
$$
W\_{n,i,j}=Y\_{i,j}\mathbf{1}\{Y\_{i,j}>\varepsilon 2^{2n}\}-\mathbb E\left[Y\_{i,j}\mathbf{1}\{Y\_{i,j}>\varepsilon 2^{2n}\}\right],
$$
We thus have to show that
$$
\tag{2'}\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{2n}} \sum\_{i=1}^{2^n} Z\_{n,i,j}\to 0\mbox{ almost surely}.
$$
$$
\tag{2''}\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{2n}} \sum\_{i=1}^{2^n} Z\_{n,i,j}\to 0\mbox{ almost surely}.
$$
For (2'), it suffices to show (by the Borel-Cantelli lemma) that
$\sum\_m\mathbb E\left[\left(\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{2n}} \sum\_{i=1}^{2^n} Z\_{n,i,j}\right)^2\right]<\infty$.
For (2''), note that $$ \left(\{\max\_{1\leqslant j\leqslant 2^n}\frac{1}{2^{2n}} \sum\_{i=1}^{2^n} Z\_{n,i,j}\neq 0 \}\right)\subset\bigcup\_{i,j=1}^{2^n}\left(\{Y\_{i,j}>\varepsilon 2^{2n}\}\right).$$




---


[1](https://www.esaim-ps.org/articles/ps/pdf/2019/01/ps180007.pdf) Deviation inequalities for Banach space valued martingales differences sequences and random fields Davide Giraudo ESAIM: PS 23 922-946 (2019)


