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.


1 Answer 1


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?

  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Oct 2, 2017 at 15:30
  • $\begingroup$ Your conditions do not exclude $u_{ij}=t_i t_j$, do they? $\endgroup$ Oct 2, 2017 at 15:36
  • $\begingroup$ I see what you say.... then this is one partial answer.... could you also state how fast it approaches $0$? $\endgroup$
    – Turbo
    Oct 2, 2017 at 15:37
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 2, 2017 at 15:40
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 2, 2017 at 15:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.