# Improved Hoeffding's Lemma and Hoeffding's Tail Bounds

arXiv: https://arxiv.org/abs/2012.03535 · HTML: https://mlsanity.com/paper/2012.03535/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [New-Type Hoeffding's Inequalities and Application in Tail Bounds](https://mlsanity.com/paper/2101.00360/) (2021)
- [TabQL: In-Context Q-Learning with Tabular Foundation Models](https://mlsanity.com/paper/2605.18979/) (2026)

## Abstract (arXiv)

The purpose of this letter is to improve Hoeffding's lemma and consequently Hoeffding's tail bounds. The improvement pertains to left skewed zero mean random variables X∈[a,b], where a<0 and -a>b. The proof of Hoeffding's improved lemma uses Taylor's expansion, the convexity of exp(sx), s∈ bf R and an unnoticed observation since Hoeffding's publication in 1963 that for -a>b the maximum of the intermediate function τ(1-τ) 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 P(Sn≥ t) and P(|Sn|≥ t), respectively, where Sn=sumi=1nXi and the Xi∈[ai,bi],i=1,...,n are independent zero mean random variables (not necessarily identically distributed). It is interesting to note that we could also improve Hoeffding's two sided bound for all Xi: aine bi,i=1,...,n. This is so because here the one sided bound should be increased by P(-Sn≥ t), wherein the left skewed intervals become right skewed and vice versa.