定義一個(gè)集合：

其中 ? 是概率為 1/2 的伯努利隨機(jī)變量.

證明下式成立：

其中 n > m > 0 ?，?

證明:?

?定義

其中，為了表示方便，令?

其中：

根據(jù) chernoff-hoeffding 不等式（參考我專欄中有對這個(gè)公式的詳細(xì)推導(dǎo)）：

（注意：公式 (3) 是一個(gè)引用，其中的 m 和 n 的符號，與前面公式 (1) (2) 是不同的含義，公式 (3) 是一個(gè)通用不等式）

則公式（2）繼續(xù)推導(dǎo)為： (p=1/2, )

對公式(4) 右側(cè)，取以 2為底的對數(shù)的變化，則：

其中：