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\,.$



Is there a 1/poly(n) or 1/polylogn upper-bound for this tail bound?
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$.


