Improved Hoeffding’s Lemma and Hoeffding’s Tail Bounds: A Recent Study - Hertz, David (Novel Research Aspects in Mathematical and Computer Science Vol. 3, 2022)
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} eq\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.