定义一个集合:
其中 是概率为 1/2 的伯努利随机变量.
(资料图)
证明下式成立:
其中 n > m > 0 ,
证明:
定义
其中,为了表示方便,令
其中:
根据 chernoff-hoeffding 不等式(参考我专栏中有对这个公式的详细推导):
(注意:公式 (3) 是一个引用,其中的 m 和 n 的符号,与前面公式 (1) (2) 是不同的含义,公式 (3) 是一个通用不等式)
则公式(2)继续推导为: (p=1/2, )
对公式(4) 右侧,取以 2为底的对数的变化,则:
其中: