Showing the following bound

84 Views Asked by At

enter image description here

My attempt. I split the inequality into a sum of two parts:

$$\mathbb{P}(S_N-\mu\le{-\delta\mu}) + \mathbb{P}(S_N-\mu\ge{\delta\mu})$$

rearranging to make the LHS of the inequality $S_N$ and applying chernoff bounds I obtained:

$\le(\frac{1}{1+\delta})^{\mu+\mu\delta}e^{\mu\delta}+(\frac{1}{1-\delta})^{\mu-\mu\delta}e^{-\mu\delta}$

but can't to bound this by anything that resembles the bound in the question.

Have I gone completely the wrong direction?

1

There are 1 best solutions below

0
On BEST ANSWER

Applying the generic Chernoff bound, for $s>0$, \begin{align} \mathsf{P}(S_N\ge (1+\delta)\mu)&\le e^{-s(1+\delta)\mu}\prod_{i=1}^N\mathsf{E}e^{sX_i} \\ &\le e^{-s(1+\delta)\mu}\prod_{i=1}^N e^{(e^s-1)p_i} \\ &=e^{(e^s-1-s(1+\delta))\mu} \end{align} because for $x\in[0,1]$, $$ e^{sx}\le 1+(e^s-1)x\le e^{(e^s-1)x}, $$ and $\sum_{i=1}^Np_i=\mu$. Finally, optimizing over $s$, one gets $$ \mathsf{P}(S_N\ge (1+\delta)\mu)\le e^{-(\ln(1+\delta)(1+\delta)-\delta)\mu}\le e^{-c\mu\delta^2} $$ for some constant $c>0$ ($\because\delta\in (0,1])$. The second bound can be found similarly.