Using Chernoff's Bound on a Poisson distribution

382 Views Asked by At

I am trying to understand how to apply Chernoff's Bound on a Poisson Distribution. As an example, let $X\sim Poisson(p\lambda)$ where $\lambda=10$ and $p=0.3$. I want to use Chernoff's Bound to find the upper bound for the probability that $X\geq5$.

I know the formula is $$\mathbb{P}(X\geq c)\leq \frac{\mathbb{E}[e^{tX}]}{e^{ct}}$$ but how do I continue from here?

Edit: Using the comments, I will find the MGF of the Poisson distribution.So $$\mathbb{E}[e^{tx}]=\sum^\infty_{x=0}e^{tx}\frac{\lambda^xe^{-\lambda}}{x!}=e^{\lambda(e^t-1)}$$.

1

There are 1 best solutions below

0
On

\begin{align*} P(X \ge c) &\le \inf_{t \ge 0} e^{-ct} \mathbb{E}[e^{tX}]\\ &= \inf_{t \ge 0} e^{-ct} e^{\lambda(e^t - 1)} \end{align*}

Now, define $f(t) = e^{\lambda(e^t-1)} e^{-ct}$, and find its minimum, say $t^*$, and plug $t^*$ back into the bound.