I need to bind the value of a variable $\alpha$. $\alpha$ is defined as,

$\alpha=a_0\cdot b_0 + a_1\cdot b_1 + a_2\cdot b_2 + \cdots +a_{n-1}\cdot b_{n-1}$. - ( eq. 1 )

$a_i$'s are selected from a certain distribution with standard deviation $\sigma$ (for simplicity we can assume it a Gaussian distribution). And $b_i$'s are uniform random variable in $(-1/2,1/2]$. $a_i$'s and $b_i$'s are all independently sampled.

Now, $E[a^2]=\sigma^2$, as $\mu=0$ and similarly, $E[a^2]=\sigma_b^2=1/12$, also $\mu=0$. Hence, $a_ib_i$ has mean $=0$ and $E[a^2b^2]=\sigma^2/12$. Hence, from central limit theorem we can claim that $\alpha$ follows a Gaussian distribution with mean $0$ and variance $=n\cdot\sigma^2/12$ standard deviation $=\sqrt{n/12}\cdot\sigma$. - (Eq. 2 )

The above part was explained nicely by Henry in this question.

Now as $\alpha$ follows a Gaussian distribution we can claim using the Lemma 4.4 in this paper, that for $k>0$ $Pr[|\alpha|>k\sigma_\alpha : \alpha\leftarrow D_{\sigma_\alpha}]\leq 2e^{-k^2/2}$, Here, $\sigma_\alpha=\sqrt{n/12}\cdot\sigma$. - (eq. 3 ).

Now, My question is suppose that there are two collections of $t\geq n$ numbers $A$ and $B$. Each element of $A$ is sampled independently from Gaussian with standard deviation $\sigma$ and each element of $B$ is chosen independently from the uniform distribution $(-1/2,1/2]$.

Now, can I still claim that the relation in $eq. 3$ $\textit{i.e}$ $\alpha>k\sigma$ with probability $2\cdot e^{-k^2/2}$, holds if $\alpha$ is generated by choosing $n$ $a_i$'s and $b_i$'s from collection $A$ and $B$ respectively. As, each $a_i$ and $b_i$ is still independent of each other.

What will be the effect of 1) $t=n$ or 2) $t=n^2$

I appreciate your help.

  • $\begingroup$ How do you choose the $a_i$'s and $b_i$'s? Uniformly at random? If so, the same CLT argument remains valid because the chosen sequence of random variables remain i.i.d. $\endgroup$ – Yining Wang Aug 25 '17 at 0:28
  • $\begingroup$ @YiningWang yes I choose $a_i$'s and $b_i$'s randomly from the collection $A$ and $B$. $\endgroup$ – Rick Aug 25 '17 at 9:29

Your Answer

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.