Hoeffding’s Inequality:

Suppose $x_1,x_2,……x_N$x1​,x2​,……xN​ are independent random variables, and $x_i∈[a_i, b_i]$xi​∈[ai​,bi​], $i=1,2,……,N$i=1,2,……,N; $\bar{X}$Xˉ is the expirical mean of $x_1,x_2,……x_N$x1​,x2​,……xN​, namely, $\bar{X}=\frac{1}{N}\sum_{i=1}^{N}{x_i}$Xˉ=N1​∑i=1N​xi​, then for any $t>0$t>0, the following inequality holds：
$P[ \bar{X}-E(\bar{X})\geq t ]\leq exp\left(-\frac{2N^2t^2}{\sum_{i=1}^{N}{(b_i-a_i)^2}} \right)$P[Xˉ−E(Xˉ)≥t]≤exp(−∑i=1N​(bi​−ai​)22N2t2​)
$P[E(\bar{X})- \bar{X}\geq t ]\leq exp\left(-\frac{2N^2t^2}{\sum_{i=1}^{N}{(b_i-a_i)^2}} \right)$P[E(Xˉ)−Xˉ≥t]≤exp(−∑i=1N​(bi​−ai​)22N2t2​)

Hoeffding’s lemma:

Suppose $x$x is an random variable, and $x∈[a, b]$x∈[a,b], and $E(x)=0$E(x)=0, then for any $t>0$t>0，the following inequality holds：
$E(e^{tx})\leq exp\frac{t^2(b-a)^2}{8}$E(etx)≤exp8t2(b−a)2​

We prove the lemma first:

Obviously, $f(x)=e^{tx}$f(x)=etx is a convex function, so for any $α∈[0,1]$α∈[0,1], we have:
$f(αx_1+(1-α)x_2)\le αf(x_1)+(1-α)f(x_2)$f(αx1​+(1−α)x2​)≤αf(x1​)+(1−α)f(x2​)

Let $α=\frac{b-x}{b-a}, \forall x∈[a,b]$α=b−ab−x​,∀x∈[a,b], then $αx_1+(1-α)x_2=x$αx1​+(1−α)x2​=x, so we have:
$e^{tx} \leq \frac{b-x}{b-a} e^{ta}+\frac{x-a}{b-a} e^{tb}, \forall x \in[a, b]$etx≤b−ab−x​eta+b−ax−a​etb,∀x∈[a,b]
take expectations on both sides, and because of $E(x)=0$E(x)=0, there is:
$E(e^{tx}) \leq \frac{b}{b-a} e^{ta}-\frac{a}{b-a} e^{tb}$E(etx)≤b−ab​eta−b−aa​etb
Try to simplify it.
Let $p=-\frac{a}{b-a}$p=−b−aa​, then $right=(1-p)e^{-t(b-a)p}+pe^{-t(b-a)(p-1)}$right=(1−p)e−t(b−a)p+pe−t(b−a)(p−1),
let $h=t(b-a)$h=t(b−a), then $right=(1-p)e^{-hp}+pe^{h(1-p)}=e^{-hp}(1-p+pe^h)$right=(1−p)e−hp+peh(1−p)=e−hp(1−p+peh), note the function $L(h)=-hp+ln(1-p+pe^h),h>0$L(h)=−hp+ln(1−p+peh),h>0, now we need to prove $L(h) \le \frac{t^{2}(b-a)^{2}}{8}=\frac{h^{2}}{8}$L(h)≤8t2(b−a)2​=8h2​.

Give two ways to evident this inequality above:

1. Construct function, $g(h)=L(h)-\frac{h^{2}}{8}=-hp+ln(1-p+pe^h)-\frac{h^{2}}{8},h>0$g(h)=L(h)−8h2​=−hp+ln(1−p+peh)−8h2​,h>0
   Obviously, $g(0)=0, g'(0)=0,g''(h)=\frac{(1-p) p e^{h}}{[(1-p)+(p e^{h})]^2}-\frac{1}{4} \le0$g(0)=0,g′(0)=0,g′′(h)=[(1−p)+(peh)]2(1−p)peh​−41​≤0, according to the monotonicity, $g(h)\le0$g(h)≤0, namely $L(h) \le \frac{h^{2}}{8}=\frac{t^{2}(b-a)^{2}}{8}$L(h)≤8h2​=8t2(b−a)2​.

2. Apply taylor expansion to function $g(h)$g(h), $g(h)=0+0+\frac{g''(0)}{2!}(h-0)^2+o(h^2)=(\frac{(1-p) p e^{h}}{[(1-p)+(p e^{h})]^2}-\frac{1}{4})h^2 +o(h^2)\le0$g(h)=0+0+2!g′′(0)​(h−0)2+o(h2)=([(1−p)+(peh)]2(1−p)peh​−41​)h2+o(h2)≤0, namely $L(h) \le \frac{h^{2}}{8}=\frac{t^{2}(b-a)^{2}}{8}$L(h)≤8h2​=8t2(b−a)2​.

So the hoeffding’s lemma is true.

To be continue……

reference：

https://www.cnblogs.com/kolmogorov/p/9518867.html
http://dict.cnki.net/
李航《统计学习方法》 北京：清华大学出版社，2019