Is Hoeffding's bound tight in any way?
The inequality: $$\Pr(\overline X - \mathrm{E}[\overline X] \geq t) \leq \exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right) $$
Is this bound (or any other form of hoeffding) tight in any sense? e.g. does there exist a distribution for which the bound is no more than a constant multiple of the true probability for every $n$?
$\endgroup$2 Answers
$\begingroup$Because it fully answers the question, I will quote almost verbatim Theorem 7.3.1 from Matoušek, Jiří, and Jan Vondrák. "The probabilistic method." Lecture Notes, Department of Applied Mathematics, Charles University, Prague (2001). downloadable as of today at
7.3.1 Theorem. Let $S$ be a sum of i.i.d. $[0,1]$-valued random variables, and assume $\sqrt{\operatorname{Var}(S)} \ge 200$. Then, there exists a constant $c>0$ such that, for all $t\in\big[0,\operatorname{Var}(S)/100\big]$, we have$$ \mathbb{P}\big(S\ge \mathbb{E}[S] + t\big)\ge c \exp\bigg(-\frac{t^2}{3\operatorname{Var}(S)}\bigg).$$In particular if $S=X_1+\dots+X_n$ for i.i.d. $X_i$, then for all $t\in \big[0,n\operatorname{Var}(X_1)/100\big]$$$ \mathbb{P}\big(S\ge \mathbb{E}[S] + t\big)\ge c \exp\bigg(-\frac{t^2n}{3\operatorname{Var}(X_1)}\bigg)$$Proposition 7.3.2 in the same reference has explicit values for $c$.
$\endgroup$ $\begingroup$Yes, one such case is when all the random variables are uniform in $[0,1]$. The sum of uniform random variables has the Irwin-Hall distribution and its tail bound matches the one given by Hoeffding's inequality. See Corollary 5 here. Also see Bernstein's inequality which is a generalization of Hoeffding.
$\endgroup$
