Let $\{Y_n\}_{n\ge 1}$ be i.i.d. exponential random variables with parameter $\lambda>0,$ and let $N$ be an independent Poisson random variable with parameter $\mu$.
Define $X=\sum_{i=1}^N Y_i$.
We want to prove that, for $x>\mu\,/\lambda,$ $$P[X\ge x]\le \exp\left[-(\sqrt{\lambda x} -\sqrt{\mu})^2\right].$$
My attempt:
To be honest, I don't know how to use the constraint that $x>\mu\,/\lambda.$
I have tried that, $$P[X\ge x] = \sum_{n=0}^\infty P[X\ge x|N=n]P[N=n]=\sum_{n=0}^\infty P[\sum_{i=1}^n Y_i \ge x]P[N=n]=\sum_{n=0}^\infty P[\sum_{i=1}^n Y_i \ge x] \exp(-\mu)\frac{\mu^n}{n!}.$$
If we define $S_n:=\sum_{i=1}^n [Y_i-E(Y_i)]=(\sum_{i=1}^n Y_i) -\frac n \lambda$, then $\{S_n\}$ is a martingale w.r.t the canonical filtration. I guess my professor wants me to use Hoeffding's inequality but I couldn't get the desired RHS for my inequality. Thanks for help.
This is the version of Hoeffding's inequality we learnt, which may look a bit different from the one on Wikipedia.
Hoeffding's inequality: Let $(Y,\mathscr F)$ be a martingale. Suppose that there exists a sequence $K_1, K_2, …$ of real numbers such that $P[|Y_n-Y_{n-1}|\leq K_n]=1$ for all $n$. Then, $$P[|Y_n-Y_0|\geq x]\leq 2 \exp\left(-\frac 1 2 x^2 \big/ \sum_{i=1}^n K_i^2 \right) \mbox{ , x>0}$$
and $$P[Y_n-Y_0\geq x]\leq \exp\left(-\frac 1 2 x^2 \big/ \sum_{i=1}^n K_i^2 \right) \mbox{ , x>0}.$$
Best Answer
For $s>0$ use the Markov inequality $\Pr(Y>y)\leq E(Y)/y$ : $$\Pr(X>x)=\Pr(e^{sX}>e^{sx})\leq e^{-sx}E(e^{sX})=e^{f_x(s)}$$ where $f_x(s)=-sx+\frac{ \mu s}{\lambda-s}$ is defined for $s<\lambda.$ Now you compute the point $s_0$ where $s\mapsto f_x(s)$ is minimum and you get the desired result.