For example: suppose we have $n$ (fair) coins to toss and we want to know what is the probability that the total number of heads (i.e sum of indicators) will be “far” from half of the tosses (which is the sum of their means), say that either $\#heads>\frac{3}{4}n$ or $\#heads<\frac{1}{4}n$ . Chernoff’s and Hoeffding’s bounds can be used to bound the probability for that to happen.

Both bounds are similar in their settings and their results, and sometimes it is not clear which bound is better for a given setting; maybe even both bounds are equivalent. In this post we will try to get an intuition which bound is stronger (and when).

Note that each bounds have several common variations and we will discuss only the ones that are stated below. Let’s start with the first bound, a multiplicative version of Chernoff’s bound.

So for any $i\in\left[n\right]$ , denote $Y_{i}=\frac{X_{i}}{b-a}-a$ and let $Y=\sum_{i=1}^{n}Y_{i}=\frac{X}{b-a}-na$ . Observe that $\mathbb{E}\left[Y\right]=\frac{\mu}{b-a}-na$ . Clearly, now the range of the variables $\left\{ Y_{i}\right\} _{i=1}^{n}$ is $\left[0,1\right]$ so we can write Hoeffding’s bound in terms of $Y_{i}$ ’s

$$\begin{aligned} \mathbf{P}\left[\left|X-\mu\right|>t\right] & =\mathbf{P}\left[\left|\frac{X}{b-a}-na-\frac{\mu}{b-a}+na\right|>\frac{t}{b-a}\right]\\ & =\mathbf{P}\left[\left|Y-\mathbb{E}\left[Y\right]\right|>\frac{t}{b-a}\cdot\frac{\mathbb{E}\left[Y\right]}{\mathbb{E}\left[Y\right]}\right]\\ & \le2\exp\left(\frac{-t^{2}}{\left(b-a\right)^{2}\mathbb{E}\left[Y\right]^{2}}\cdot\frac{\mathbb{E}\left[Y\right]}{3}\right)\\ & =2\exp\left(\frac{-t^{2}}{3\left(b-a\right)^{2}}\left(\frac{\mu}{b-a}-na\right)^{-1}\right)\\ & =2\exp\left(\frac{-t^{2}}{3\mu\left(b-a\right)-3a\cdot n\left(b-a\right)^{2}}\right) \end{aligned}$$

Where the inequality in the middle of the process is where we apply Chernoff’s bound with $\epsilon=\frac{t}{\left(b-a\right)\mathbb{E}\left[Y\right]}$ , note that there is an implicit assumption here that $\epsilon<1$ .

So we managed to formulate Hoeffding’s bound in Chernoff’s settings, ending with a very messy formula. In order to explore the behavior of the bounds further, we will simplify the analysis by adding another assumption: that $a=0$ .

Next, the term we got for Hoeffding is simplified further into $$\mathbf{P}\left[\left|X-\mu\right|>t\right]\le2\exp\left(\frac{-t^{2}}{3\mu b}\right)$$ Now easy to compare between the bounds. With Hoeffding we can achieve bound of $2\exp\left(\frac{-t^{2}}{nb^{2}}\right)$ and with Chernoff $2\exp\left(\frac{-t^{2}}{3\mu b}\right)$ , it just left to compare between $nb$ and $3\mu$ . If $nb<3\mu$ then Chernoff is stronger and vise versa. We conclude that none of the bounds is always preferred upon the other (which is not so surprising), and the answer to the question “which one to use” depends on the parameters of the distribution in hand.

Note the differences between that regime and the one from the definition at the beginning of the post: in this theorem the variables are i.i.d (rather than only independent) and they are discrete.