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

New contributor
金之涵 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 2
    $\begingroup$ Erm... What is the event in brackets? $\endgroup$ – fedja May 16 at 15:40
  • $\begingroup$ Is that meant to be $P[...-1]>0$? $\endgroup$ – Bullet51 May 17 at 2:08
  • $\begingroup$ Sorry for the mistake. I have updated. $\endgroup$ – 金之涵 May 17 at 2:13
  • $\begingroup$ It is unclear what you mean by poly(n) and polylogn; please use standard mathematical notation. It is also unclear if you mean an upper or lower bound. If you mean an upper bound that goes to $0$ as $n\to\infty$, for each $\epsilon>0$, then such a bound does not exist. $\endgroup$ – Iosif Pinelis 2 days ago
  • $\begingroup$ Why doesn't it exist? $\endgroup$ – 金之涵 2 days ago

Your Answer

金之涵 is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.