Improved Hoeffding’s Lemma and Hoeffding’s Tail Bounds: A Recent Study

Abstract

The goal of this chapter is to is to improve Hoeffding’s lemma and consequently Hoeffding’s tail bounds. Our starting point is to present Hoeffding’s lemma with a proof somewhat different than the original one and then present the improved Hoeffding’s lemma and prove it.   The improvement pertains to left skewed zero mean random variables \(X \in[a, b], \text { where } a<0 \text { and }-a>b\) . The proof of Hoeffding’s improved lemma uses Taylor’s expansion, the convexity of  \(\exp (s x), s \in \mathbb{R}\) , and an unnoticed observation since Hoeffding’s publication in 1963 that for -a > b the maximum of the intermediate function \(\tau(1-\tau)\) appearing in Hoeffding’s proof is attained at an endpoint rather than at \(\tau\) = 0.5 as in the case b > - a. Using Hoeffding’s improved lemma we obtain one sided and two sided tail bounds for  \(\mathbb{P}\left(S_{n} \geq t\right) \text { and } \mathbb{P}\left(\left|S_{n}\right| \geq t\right)\) , respectively, where \(S_{n}=\sum_{i=1}^{n} X_{i} \text { and the } X_{i}\in\left[a_{i}, b_{i}\right], i=1, \ldots, n\)  are independent zero mean random variables (not necessarily identically distributed). We could also improve Hoeffding’s two sided bound for all \(\left\{X_{i}:-a_{i} \neq\right.\) \(\left.b_{i}, i=1, \ldots, n\right\}\) . This is due to the fact that the one-sided bound should be increased by \ \mathbb{P}\left(-S_{n} \geq t\right)\) , causing left-skewed intervals to become right-skewed and vice versa.