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

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 . The proof of Hoeffding’s improved lemma uses Taylor’s expansion, the convexity of , and an unnoticed observation since Hoeffding’s publication in 1963 that for -a > b the maximum of the intermediate function appearing in Hoeffding’s proof is attained at an endpoint rather than at = 0.5 as in the case b > - a. Using Hoeffding’s improved lemma we obtain one sided and two sided tail bounds for , respectively, where are independent zero mean random variables (not necessarily identically distributed). We could also improve Hoeffding’s two sided bound for all . 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.