1
$\begingroup$

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?

  • 0
    @did Thanks for the answer. This was very instructive. I managed to prove the result using a different argument. By writing $z_i = x_i r_i$, where $x_i \sim N(\mu, \sigma^2)$ and $r_i \sim {\rm Bern}(p)$, and then conditioning on the event \{ \sum_i r_i > p n/2 \}.2012-06-04

2 Answers 2

1

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$.

  • 0
    Replaced the (unfortunate) notation $\pi$ by $p$.2012-05-18
0

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.