# Tail bound for sum of product Normal-Bernoulli random variables

Let $Z \sim \pi N(\mu, \sigma^2) + (1-\pi)\delta_0$ and $z_i \sim Z$ are iid for $i=1,\ldots,n$. I would like to obtain a result of the form $$P[n^{-1}\sum_i z_i - \pi\mu > \epsilon]\leq\exp(-c n \epsilon^2)$$ with an explicit constant c.

I computed ${\mathbb E}[\exp(t(Z - \pi\mu)] = \exp(-t\pi\mu)[1-\pi + \pi\exp(\mu t + \frac{\sigma^2}{2}t^2)]$ and tried upper bounding RHS of

$$P[n^{-1}\sum_i z_i - \pi\mu > \epsilon]\leq \min_{t > 0} \exp(-nt\epsilon)\exp(-nt\pi\mu)[1-\pi + \pi\exp(\mu t + \frac{\sigma^2}{2}t^2)]^n,$$ however, I have problems finding explicit $t$ that minimizes the RHS objective.

Are there alternative approaches to finding desired upper bound?

-
what is $\delta_0$? – leonbloy May 15 '12 at 15:43
@leonbloy point mass at zero. Z is equal zero with probability (1-p) and normal distributed with probability p – mkolar May 15 '12 at 15:48
ok, that's what i thought at first. but you used $\pi$ instead of $p$ and that confused me. – leonbloy May 15 '12 at 15:50
are you sure about $E[exp(t(Z− p \mu)]$? I'm getting $p[exp(\mu t + \sigma^2 t^2 /2)] + 1-p$ instead (checking...) – leonbloy May 15 '12 at 15:58
Let $Z = XU$ where $X \sim N(\mu, \sigma^2)$ and $U \sim {\rm Bern}(p)$. Then $E(\exp(t(Z-p\mu))) = E_U E(\exp(t(XU-p\mu))|U) = p E(\exp(t(X-p\mu))) + (1-p)\exp(-t p\mu)$. Result then follows by plugging in the mgf for normal. – mkolar May 15 '12 at 16:45

Cramér's exponential inequalities also yield (non-optimal) upper bounds for (non-optimal) choices of $t$, hence to identify the exact optimal value $t^*$ of $t$ is not always necessary. Instead, one can simply find some value of $t$ such that the RHS decreases geometrically fast to zero. Of course, this assumes one is able to locate roughly $t^*$, since good choices of $t$ will often be near $t^*$, but this allows to bypass the determination of the exact value of $t^*$.

In the case at hand, one wants to find $t\gt0$ such that $g(t)\lt1$, where $$g(t)=\left(1-p+p\mathrm e^{\mu t+\sigma^2 t^2/2}\right)\mathrm e^{-t(\epsilon+p\mu)}.$$ Assuming that $\epsilon\to0^+$ and that $t=\epsilon/\tau$ for some fixed positive $\tau$, one sees that the choice $$\tau=p(\sigma^2+(1-p)\mu^2)$$ yields $g(t)\leqslant\mathrm e^{-\epsilon^2/(2\tau)+o(\epsilon^2)}$. Hence, for small enough values of $\epsilon$, the desired inequality holds for every positive $c$ such that $$c\lt1/(2\tau).$$ Note finally that $\tau$ is the variance of $Z$.

-
Replaced the (unfortunate) notation $\pi$ by $p$. – Did May 18 '12 at 7:20

Not an aswer, just a hint, too long for comment: let $g(t) = \exp{(−n t \epsilon − nt p \mu)} [1−p+ p\, \exp{(\mu t + \sigma^2 t/2)}]^n$

Taking logarithms to simplify, and because $(1-p)+p \, x \ge x^p$, we get

$\log(g(t)) \ge - n t \epsilon + n p \frac{\sigma^2 t^2 }{2}$ and the minimum of the right side, for $t\ge 0$ is of the form $- c \, n \, \epsilon^2$.

From this, we'd get the desired result ... except for the little detail that the inequality is not the desired one. Perhaps someone can find something along this lines.

-