Recently, I saw the Chernoff bound written as follows.

Let $X_1,X_2,\ldots,X_n$ be drawn i.i.d. on alphabet $\mathcal{X}$ and let $f:\mathcal{X}\to [0,1]$ be any function. Let $\mathbb{E}f(X_1) = \mu.$ Then,

$$P\left(\left|\sum_{i=1}^n f(X_i) -\mu n\right|\geq \delta\mu n\right)\leq \begin{cases} e^{-\Omega(\delta^2\mu n)} & \mbox{ for $0\leq \delta\leq 1$,}\\ e^{-\Omega(\delta\mu n)} & \mbox{ for $\delta>1$.}\end{cases}~$$

While I had known that the probability is to decay exponentially in $n$ and I knew also that the tightest exponent should come from the Cramer-Chernoff theorem on large deviations, the role of the $\delta^2$ for $0\leq \delta\leq 1$ and $\delta$ for $\delta>1$ in the exponent is somewhat baffling to me. Can you provide any insights into this inequality? A precise quantification of this statement without the $\Omega$ notation will be particularly insightful too. Thanks!

EDIT: I found out the simple answer to this question in a nice blogpost by Terry Tao: https://terrytao.wordpress.com/2010/07/15/the-golden-thompson-inequality/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.