霍夫丁不等式 使用實例

置信區(qū)間

霍夫丁不等式被用來分析樣本的置信區(qū)間，我們可以通過定理一得到：

這個不等式說明了估計值比真值大t的概率被指數(shù)邊界控制,。對稱的,，以下的不等式同樣成立：

將兩式相加我們可以得到如下不等式：

上述不等式可以理解為：

即真值的估值范圍。其中

所以,，我們要求至少上述不等式右邊式子的樣本數(shù)量從而使得估值邊間更加靠近真值,。

霍夫丁不等式

霍夫丁不等式（Hoeffding’s inequality），在概率論中,，該不等式給出了隨機變量的和與其期望值偏差的概率上限,。霍夫丁不等式被Wassily Hoeffding于1963年提出并證明,。

霍夫丁不等式是一個Azuma-Hoeffding不等式的特例,，并且他比Sergei Bernstein于1923年證明的Bernstein不等式更加具有廣泛性。這幾個不等式都是McDiarmid’s不等式的特例,。這樣,，我們基本就把這幾個不等式的關(guān)系理清楚了。

1 伯努利隨機變量的特例

霍夫丁不等式經(jīng)常被應(yīng)用于一些獨立分布的伯努利隨機變量的重要特例中,，這也是為什么這個不等式在計算機科學(xué)以及組合數(shù)學(xué)中如此常見,。我們認(rèn)為一個拋硬幣時一個硬幣A面朝上的概率為p，B面朝上的概率則為1-p,。我們拋n次硬幣,，那么A面朝上次數(shù)的期望值為np。那么進(jìn)一步我們可以知道,，A面朝上的次數(shù)不超過k次的概率能夠被下面的表達(dá)式完全確定：

這里的H(n)為拋n次硬幣其A面朝上的次數(shù),。

對某一ε>0，當(dāng)k=(p-ε)n時,，上面不等式確定的霍夫丁上界將會按照指數(shù)級變化：

相似的,對某一ε>0,當(dāng)k=(p+ε)n,，霍夫丁不等式的概率邊界同樣可以確定為：

這樣根據(jù)上面兩個式子我們可以得到：

比如說現(xiàn)在我們令

那么可以得到

2 普遍情況

現(xiàn)在令X1，X2,，…,，Xn為[0,1]的獨立隨機變量，即0<=Xi<=1,。我們定義這些變量的經(jīng)驗均值為：

在1963年霍夫丁提出該不等式,，其中霍夫丁定理一中的一個不等式為：

當(dāng)知道Xi嚴(yán)格的邊界范圍ai，bi（即Xi屬于[ai,bi]）時,，霍夫丁定理二更加廣泛：

這個不等式也可以寫成和的形式：

其中

需要注意的是對于Xi為不放回的抽樣該等式依然成立,；在這樣的例子中這些隨機變量不在是獨立的了。這種情形的證明可以看Hoeffding在1963年發(fā)表的論文,。如果需要一個在無放回抽樣的例子中更好的邊界,，可以查看Serfling在1974年發(fā)表的論文,。