Probability inequalities

Question

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 sum 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}[ X \geq \epsilon\sigma^2 N] \leq \exp(?)$, where $X = \sum_{i=1}^{N} w_iv_i$, $w_i$ and $v_i$ are generated i.i.d. from $\mathcal{N}(0, \sigma)$.

I tried to use the Chernoff bound using moment generating function (MGF), the derived bound is given by:

$\begin{eqnarray} \mathrm{Pr}[ X \geq \epsilon\sigma^2 N] &\leq& \min\limits_s \exp(-s\epsilon\sigma^2 N)g_X(s) \\ &=& \exp\left(-\frac{N}{2}\left(\sqrt{1+4\epsilon^2} -1 + \log(\sqrt{1+4\epsilon^2}-1) - \log(2\epsilon^2)\right)\right) \end{eqnarray}$

where $g_X(s) = \left(\frac{1}{1-\sigma^4 s^2}\right)^{\frac{N}{2}}$ is the MGF of $X$. But the bound is 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.

Answer 1

Using the Chernoff bound you suggested for some $s\le 1/(2\sigma^2)$ that will be specified later, \[ P[X>t] \le \exp(-st) \exp\Big(-(N/2) \log(1-\sigma^4s^2) \Big) \le \exp(-st + \sigma^4s^2 N) \] where the second inequality holds thanks to $-\log(1-x)\le 2x$ for any $x\in(0,1/2)$. Now take $t=\epsilon \sigma^2 N$ and $s=t/(2\sigma^4N)$, the right hand side becomes $\exp(-t^2/(4\sigma^4N)=\exp(-\epsilon^2 N/4)$ which yields \[ P[X>\epsilon \sigma^2 N] \le \exp(-\epsilon^2 N/4). \] for any $\epsilon\in(0,1)$.

Another avenue is to directly apply concentration inequalities such as the Hanson-Wright inequality, or concentration inequalities for Gaussian chaos of order 2 which encompasses the random variable you are interested in.

Simpler approach without using the moment generating function

Take $\sigma=1$ for simplicity (otherwise, one may rescale by dividing by $\sigma^2$).

Write $v=(v_1,...,v_n)^T$ and $w=(w_1,...,w_n)^T$. You are asking for upper bounds on $P(v^Tw>\epsilon N)$.

Let $Z= w^T v/\|v\|$. Then $Z\sim N(0,1)$ by independence of $v,w$ and $\|v\|^2$ is independent of $Z$ with the $\chi^2$ distribution with $n$ degrees-of-freedom.

By standard bounds on standard normal and $\chi^2$ random variables, $$P(|Z|>\epsilon\sqrt{n/2})\le 2\exp(-\epsilon^2 n/4), \qquad\qquad P(\|v\|>\sqrt{2n}) \le \exp(-n(\sqrt 2 -1)^2/2). $$ Combining with the union bound gives an upper bound on $P(v^Tw>\epsilon N)$ of the form $ 2\exp(-\epsilon^2 n/4) + \exp(-n(\sqrt 2 -1)^2/2)$.

Answer 2

The bound you obtain is of order $e^{-\epsilon}$ as $\epsilon \to \infty$. I don't think you can do much better for general $\epsilon$. From the Wikipedia page on Product Variables the distribution of $w_i v_i$ is $K_0(z)/\pi$ where $K_0$ is a modified Bessel function. From (10.25.3) in the DLMF function list, $K_0(t) \sim e^{-t}/\sqrt{t}$ so that for $x$ sufficiently large $\mathbb{P}(w_i v_i > x) \sim \int_x^\infty e^{-t}/\sqrt{t} dt$ which is not going to give you a sub-Gaussian bound.