1. 证明Markov不等式

定义：

证明：

设X为离散随机变量

得证

2. 证明Hoeffding不等式

引理：

证明：

由于E(X)=0，令

得到

再令u=s(b-a)

定义

得到

根据泰勒展开和泰勒中值定理，∃η∈[0,u]使得：

得证：

定义：

证明：

取s>0，

根据Markov不等式，

根据Hoeffding不等式引理，

因为对∀s，以上不等式成立。令

所以，

Hoeffding不等式也可以变形为：

3. 泛化能力上界（以二分类为例）

定义：

证明：

令

其中，

参考文献：

【1】https://zhuanlan.zhihu.com/p/39663399

【2】https://blog.csdn.net/qq_30565883/article/details/104142990

【3】https://baike.baidu.com/item/%E5%87%B8%E5%87%BD%E6%95%B0/3371735?fr=aladdin

【4】https://blog.csdn.net/u010510549/article/details/47839241

【5】https://www.cnblogs.com/qizhou/p/12843557.html

【6】https://zhuanlan.zhihu.com/p/257167788

【7】https://www.cnblogs.com/aichemistar/p/13720564.html

【8】https://zhuanlan.zhihu.com/p/75486940

【9】https://blog.csdn.net/u013745804/article/details/79522209

【10】统计学习方法（第2版），李航著，清华大学出版社