Improved Hoeffding’s Lemma and Hoeffding’s Tail Bounds


  •  David Hertz    

Abstract

The purpose of this article is to improve Hoeffding's lemma and consequently Hoeffding's tail bounds. The improvement pertains to left skewed zero mean random variables X\in[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\in \RR, 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 \PP(S_n\ge t) and \PP(|S_n|\ge t), respectively, where S_n=\sum_{i=1}^nX_i and the X_i\in[a_i,b_i],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 \{X_i:  -a_i\ne b_i,i=1,...,n\}. This is  so because here the one sided bound should be  increased by \PP(-S_n\ge t),  wherein the left skewed intervals become right skewed and vice versa.


This work is licensed under a Creative Commons Attribution 4.0 License.
  • ISSN(Print): 1927-7032
  • ISSN(Online): 1927-7040
  • Started: 2012
  • Frequency: bimonthly

Journal Metrics

  • h-index (December 2020): 18
  • i10-index (December 2020): 36
  • h5-index (December 2020): N/A
  • h5-median(December 2020): N/A

( The data was calculated based on Google Scholar Citations. Click Here to Learn More. )

Contact