Does anyone familiar with the following format of Chernoff bound:
$$
Pr\left(\frac{1}{n}\sum\limits_{i=1}^n X_i \gt T\right ) \le \inf_{\gamma \gt 0}{\left ( \frac{E[e^{\gamma X_i}]}{e^{\gamma T}} \right )}^n,
$$
where $X_i$ are i.i.d.
How can this format be evaluated from Markov bound?
Thanks
Best Answer
Using $x > y$ if and only if $e^{n \gamma x} > e^{n \gamma y}$ for positive $\gamma$ for (1), the Markov inequality for (2), independence of the $X_i$ for (3) and identical distributions for (4), you get $$\begin{align} \forall \gamma > 0: \qquad Pr\left(\frac{1}{n}\sum\limits_{i=1}^n X_i \gt T\right ) &\stackrel{(1)}{=} Pr\left(\exp\left(\gamma\sum\limits_{i=1}^n X_i\right) \gt \exp\left(n\gamma T\right)\right ) \\ &\stackrel{(2)}{\leq} \frac{E\left[\exp\left(\gamma\sum\limits_{i=1}^n X_i\right)\right]}{e^{n\gamma T}} \\ &\stackrel{(3)}{=} \frac{\prod\limits_{i=1}^n E\left[\exp\left(\gamma X_i\right)\right]}{(e^{\gamma T})^n} \\ &\stackrel{(4)}{=} \frac{E\left[\exp\left(\gamma X_i\right)\right]^n}{(e^{\gamma T})^n} \end{align}$$ Then we can pull out the $n$th power, and take the infimum of $\gamma > 0$ to get the result.