3
$\begingroup$

Hi everyone,

I am looking for some probability inequalities for sums of unbounded random variables. I would really appreciate it if anyone can provide me some thoughts.

My problem is to find an exponential upper bound over the probability that the linear combination of unbounded i.i.d. random variables, which are in fact the multiplication of two i.i.d. Gaussian, exceeds some certain value, i.e., $\mathrm{Pr}[\lvert X \rvert \geq \epsilon] \leq \exp(?)$, where $X = \sum_{i=1}^{N} \alpha_i w_iv_i$, $w_i$ and $v_i$ are generated i.i.d. from $\mathcal{N}(0, \sigma)$, and $0 \leq \alpha_i \leq 1$ is a coefficient.

I tried to use the Chernoff bound using moment generating function (MGF), but the derived bound was not so tight. The main issue in my problem is that the random variables are unbounded, and unfortunately I can not use the bound of Hoeffding inequality.

I will be to happy if you help me find some tight exponential bound . Thanks in advance

Improve this question
$\endgroup$
5
  • $\begingroup$ Not clear what you're hoping to get here. Are you thinking of epsilon as small? In that case the probability will be close to 1/2 as $X$ will either be positive or negative (with equal probability); and will be close to 0 only with small probability. The probability of $|X|$ being less than $\epsilon$ should be about $\epsilon/\sqrt{\sigma N}$. $\endgroup$
    – Anthony Quas
    May 26, 2011 at 15:02
  • 2
    $\begingroup$ Let $w=(w_1,\dots,w_n)$ and $v=(v_1,\dots,v_n)$. By isotropy and independence between $w$ and $v$, $X$ has the same law as $<w,\|v\|_2e_1>$ which is $\|v\|_2w_1$. The law of $\|v\|_2$ and of $w_1$ are standard laws and the two r.v.\ are independent. Is it sufficient for your purpose ? $\endgroup$
    – camomille
    May 26, 2011 at 16:00
  • $\begingroup$ Dear Anthony, Thanks a lot for your answer but I need an upper bound over the probability not an approximate value. Dear Cammomille, Thanks a lot for your answer Unfortunately I did not understand what do you mean as ``law''. $\endgroup$
    – Farzad
    May 26, 2011 at 19:42
  • $\begingroup$ law means distribution here. $\endgroup$
    – camomille
    May 26, 2011 at 19:55
  • $\begingroup$ If I understood correctly, $X$ has the same distribution as $\lVert v \rVert_2 w$ whare $\lVert v \rVert_2$ has a chi distribution and $w_1$ has a Gaussian. Then, I can find the probability distribution of $X$? $\endgroup$
    – Farzad
    May 26, 2011 at 20:37

1 Answer 1

Reset to default
3
$\begingroup$

This is a standard exercise in large deviations. The exponential rate of decay for the large deviations of sums of i.i.d. random variables can be derived using Cramer's Theorem (see section 2.2 in Dembo and Zeitouni's book).

In the statement of the problem above, Cramer's theorem gives that $$P(|X| > \epsilon ) = e^{ - N I(\epsilon) + o(N) }, $$ where $I(x)$ is the large deviation rate function. In this example (unless I screwed up in my calculation) $$ I(x) = \frac{1}{2}\left( \sqrt{1+4x^2}-1+\log(\sqrt{1+4x^2}-1)-\log(2x^2) \right) .$$

Improve this answer
$\endgroup$
11
  • $\begingroup$ Cramer's theorem just gives exponential rate of decay. More precise asymptotics are $$P(|X| > \epsilon ) \sim \frac{C}{\sqrt{N}} e^{-N I(\epsilon)},$$ where the constant $C$ depends on $\epsilon$ and can be explicitly calculated in this case (see Theorem 3.7.4 in Dembo and Zeitouni's book). $\endgroup$
    – Jon Peterson
    May 26, 2011 at 20:20
  • $\begingroup$ Farzad, in your comment above you mentioned that you needed an upper bound. An examination of the proof of the upper bound in Cramer's theorem shows that the exponential rate of decay given by the large deviation rate function is a strict upper bound. That is, $ P(|X| > \epsilon ) \leq e^{-N I(\epsilon)} $ for all $\epsilon>0$ and all $N\geq 1$. $\endgroup$
    – Jon Peterson
    May 26, 2011 at 20:28
  • $\begingroup$ Thanks for your answer, can you give me the name of the book? $\endgroup$
    – Farzad
    May 26, 2011 at 20:43
  • $\begingroup$ @Jon: Strict upper bound in the sense of nonasymptotic upper bound, I guess. $\endgroup$
    – Did
    May 27, 2011 at 6:01
  • 1
    $\begingroup$ Actually, in this case the coefficients are decaying so fast, the infinite random sum $\sum_{i=1}^\infty \alpha_i w_i v_i$ actually converges almost surely. Therefore, $P(|X|>\epsilon)$ doesn't decay at all but converges to a non-zero constant. $\endgroup$
    – Jon Peterson
    May 27, 2011 at 19:54

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.