# On concentration of a sum random variable

Take a random variable defined as

$$r=u_{11}v_{1}v_{1}+u_{12}v_{1}v_{2}+\dots+u_{n,n-1}v_{n}v_{n-1}+u_{nn}v_{n}v_{n}$$ where $v_{i}$ are independent uniform random variables from $\{0,\dots,b\}$, $u_{ij}$ are in $\{-T,\dots,0,\dots,T\}$ with the condition that probability that all $|u_{ij}|<\frac{T}2$ is at most some small $\epsilon\in(0,1)$, $u_{ij}$ are independent of $v_i,v_j$ and $u_{ij}$ might not be independent of $u_{i'j'}$ where either $i\neq i'$ or $j\neq j'$ holds.

Assume the mean of $r$ is $0$. Variance is at most $n^4b^4T^{2}$.

1. What is the probability that $|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T$ holds at any fixed $c\geq2$?

We know $P(|r|\leq k\sigma)\geq1-\frac1{k^2}$ and here $k=\frac 1{2n^2}\big(1+\frac1{n^c}\big)<1$ and so useless.

1. Under what broad conditions on distribution of $r$ can above probability be $>1-\frac1{n^2}$?

One possibility is for conditions on random variables that can force cancellations in summation defining $r$ leading to a smaller variance. If $u_{ij}$ are such that $\pm1$ signs occur equally likely with probability $>1-\frac1{n^2}$ then we can expect the variance close to $b^4T^2$ with probability $>1-\frac1{n^2}$ shaving a factor of $n^2$ which leads to desired probability for $|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T$ holds at any fixed $c\geq2$.

If the probability approaches $0$ on some conditions then I am interested in how fast precisely it approaches $0$ on those set conditions. This is implicit in query 1. where I have attempted the asymptotics using Chebyshev.

Under your conditions, $P(|r|\leq\frac12\big(1+\frac1{n^c}\big)b^2T)$ will usually go to $0$ as $n\to\infty$. So, the lower bound $1-\frac1{n^2}$ on this probability will be impossible.

Indeed, for simplicity let $T=1$. Note that $c_b^2:=Var(v_i)=(b^2-1)/12$. Let $u_{ij}:=t_i t_j$, where $t_1,\dots,t_n$ are iid Rademacher random variables (independent of the $v_i$'s), with $P(t_i=\pm1)=1/2$. Let $n\to\infty$. Then \begin{equation} \frac rn=\Big(\frac1{\sqrt n}\sum_{i=1}^n t_i v_i\Big)^2\to c_b^2 Z^2 \end{equation} in distribution, by the central limit theorem, where $Z\sim N(0,1)$. So, for any real $\delta>0$ and all $n>b^2/\delta$, \begin{equation} P(|r|\leq\tfrac12\big(1+\tfrac1{n^c}\big)b^2T) \le P(\tfrac{|r|}n\le\tfrac{b^2}n) \le P(\tfrac{|r|}n\le\delta)\to P(c_b^2 Z^2\le\delta), \end{equation} and the latter probability goes to $0$ as $\delta\downarrow0$.

Addition in response to the OP's clarifications of the question:

For simplicity, let $T=1$. Suppose first that the $u_{ij}$'s are nonrandom numbers. Then \begin{equation} Er^2=\sum_{i,j,k,\ell} u_{ij}u_{k,\ell}Ev_iv_jv_kv_\ell=\sum_i u_{ii}^2\mu_4 +2\sum_{i\ne \ell} u_{ii}(u_{i\ell}+u_{\ell i})\mu_3\mu_1 \end{equation} \begin{equation} +\sum_{i\ne k} [u_{ii}u_{kk}+u_{ik}(u_{ik}+u_{ki})]\mu_2^2 +\sum_{i\ne k\ne \ell}[2u_{ii}u_{k\ell}+(u_{ik}+u_{ki})(u_{i\ell}+u_{\ell i})]\mu_2\mu_1^2 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4, \end{equation} where $\mu_p:=Ev_1^p$, $\sum_{i\ne k\ne \ell}$ denotes the sum over all triples $(i,k,\ell)$ of pairwise distinct $i,k,\ell$, and $\sum_{i\ne j\ne k\ne \ell}$ denotes the sum over all quadruples $(i,j,k,\ell)$ of pairwise distinct $i,j,k,\ell$. Note also that \begin{equation} \sum_{i\ne k\ne \ell}u_{ii}u_{k\ell} =\sum_{k\ne \ell}u_{k\ell}\sum_i u_{ii}-\sum_{k\ne \ell}u_{kk}(u_{k\ell}+u_{\ell k}). \end{equation}

Suppose now further that the $u_{ij}$'s are in $[-1,1]\setminus(-1+1/n,1-1/n)$ for all $i,j$ and such that \begin{equation} \sum_i u_{ii}=0,\quad u_{ij}+u_{ji}=0 \text{ if $j\ne i$, }\tag{*} \end{equation} so that \begin{equation} \sum_{i\ne j} u_{ij}=0\quad\text{and hence}\quad \sum_{i,j} u_{ij}=0. \end{equation} E.g., if $n=2m$ is even, we can take $u_{ii}=1$ for $i\le m$, $u_{ii}=-1$ for $i>m$, $u_{ij}=1$ if $i<j$, $u_{ij}=-1$ if $i>j$. Let us consider this case in detail. We have \begin{equation} Er=\sum_{i,j} u_{ij}Ev_iv_j=\sum_i u_{ii}\mu_2+\sum_{i\ne j} u_{ij}\mu_1^2=0+0=0. \end{equation} So, \begin{equation} Var(r)=Er^2=n\mu_4+\sum_{i\ne k} u_{ii}u_{kk}\mu_2^2 +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4. \end{equation} Next, $\sum_{i\ne k} u_{ii}u_{kk}=\sum_{i,k} u_{ii}u_{kk}-\sum_i u_{ii}^2 =(\sum_i u_{ii})^2-\sum_i u_{ii}^2=0-n=-n$. So, \begin{equation} [Var(r)=]Er^2=n(\mu_4-\mu_2^2) +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}\mu_1^4. \end{equation} Repeating this reasoning with $1$ in place of $v_i$, we get \begin{equation} 0=\Big(\sum_{i,j} u_{ij}\Big)^2=n(1^4-(1^2)^2) +\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}1^4, \end{equation} whence
$\sum_{i\ne j\ne k\ne \ell}u_{ij}u_{k\ell}=0$ and \begin{equation} Var(r)=Er^2=n(\mu_4-\mu_2^2)=n\,Var(v_1^2)=\tfrac{n}{180} (2 b+1) (8 b+11) \left(b^2-1\right). \end{equation} This is smaller than $n^4b^4T^{2}=n^4b^4$ by a factor of $\asymp n^3$, not just $\asymp n^2$. The case of $n$ odd should be very similar.

Now of course you can take any random $u_{ij}$ (independent of the $v_i$'s) such that $(*)$ holds almost surely or with high enough probability. Is this "packing"/"forcing" condition broad enough?

• why $u_{ij}=t_it_j$? $u_{ij}$ are not in product form and $u_{ij}$ could be independent of each other (I only said might not be independent) and so we cannot force conditional dependence. – T.... Oct 2 '17 at 15:30
• Your conditions do not exclude $u_{ij}=t_i t_j$, do they? – Iosif Pinelis Oct 2 '17 at 15:36
• I see what you say.... then this is one partial answer.... could you also state how fast it approaches $0$? – T.... Oct 2 '17 at 15:37
• That is indeed quite a different question, and you can post it separately. I think it will be right if you restore the original question in this post. I don't understand why you say my answer to your original question is only partial. – Iosif Pinelis Oct 2 '17 at 15:40
• I think my answer suggests that the lower bound $1-\frac1{n^2}$ on that probability will be impossible under any reasonable broad conditions. Indeed, why would reasonable broad conditions exclude the case considered in my answer? – Iosif Pinelis Oct 2 '17 at 15:50