Is there a 1/poly(n) or 1/polylogn upper-bound for this tail bound?

Question

Is there a good tail bound for $\operatorname{P}\!\Bigg[\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n a_{i,j})^2}{n^2} -1\bigg\vert > \epsilon\Bigg]\,,$ where all $a_{i,j}$'s are iid, with $\operatorname{E}[a_{i,j}] = 0\,, \operatorname{E}[a_{i,j}^2] = 1\,, \operatorname{E}[|a_{i,j}|^3] = \rho\,.$

The tail bound can be without any relation to $\epsilon$ but needs to converge to 0 as $n\to\infty\,.$

Answer 1

Let $A:=\Bigg\{\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n a_{ij})^2}{n^2} -1\bigg\vert > \epsilon\Bigg\}\,$ denote the event in question. We will show that

$\operatorname{P}(A)\le C_{\epsilon}/n$ for a suitable constant $C_{\epsilon}$.

If $a_{ij}$ had a finite fourth moment, the argument would be easy. Given only a third moment, we resort to truncation. Observe that $\operatorname{P}(|a_{ij}|>n) \le E(|a_{ij}|^3)/n^3=\rho/n^3$,

so $X_{ij}:=a_{ij}1_{\{|a_{ij}| \le n\}}$ satisfy

$\operatorname{P}(\exists i,j \le n \, : \, X_{ij} \ne a_{ij}) \le \rho/n$. Therefore

$A_1:=\Bigg\{\bigg\vert\dfrac{\sum_{j=1}^n(\sum_{i=1}^n X_{ij})^2}{n^2} -1\bigg\vert > \epsilon\Bigg\}\,$ satisfies

$\operatorname{P}(A) \le \operatorname{P}(A_1)+ \rho/n$. Next, we estimate the moments $\mu_k:=E(X_{ij}^k)$.

First, $\mu_1=E(X_{ij})=-E(a_{ij}1_{\{|a_{ij}|> n\}})$, so that $|\mu_1| \le E(|a_{ij}|^3/n^2)=\rho/n^2$.

Second, $\mu_2 \le 1$ and $1-\mu_2 = E(a_{ij}^2 1_{\{|a_{ij}|> n\}}) \le E(|a_{ij}|^3/n)=\rho/n$.

Third, $|\mu_3| \le \rho$ and fourth, $\mu_4 \le n E(|X_{ij}|^3)\le n\rho$.

Thus for each $j$, the column sum $S_j=\sum_i X_{ij}$ satisfies

$E(n-S_j^2) = n(1-\mu_2)-n(n-1)\mu_1^2$ so $|E(n-S_j^2)| \le \rho$ (assuming $n>\rho$.)

Moreover,

$\operatorname{Var}(n-S_j^2) \le E(S_j^4)\le n\mu_4 +4n^2 |\mu_3 \mu_1|+3n^2{\mu_2}^2+ 6n^3 \mu_2 {\mu_1}^2 + n^4\mu_1^4 \le 5\rho n^2$,

provided that $n>\rho$. Here the constant 5 is not optimal, and we used $\rho \ge 1$ to simplify.

Therefore $S=\sum_j (n-S_j^2)$ satisfies (assuming $n>\rho$): $E(S^2)= \operatorname{Var}(S)+ (E[S])^2 \le 5\rho n^3 +n^2\rho^2\le 6\rho n^3$.

Finally, for $\epsilon>0$ and $n >\rho$, we have

$\operatorname{P}(A_1)=\operatorname{P}(|S|>n^2 \epsilon) \le E(S^2)/(n^4\epsilon^2) \le 6\rho/(n\epsilon^2)$,

whence $\operatorname{P}(A) \le 6\rho/(n\epsilon^2) +\rho/n$.