幾個(gè)概率不等式(三) Chernoff_bounds_用于泊松過程

2023-08-26 09:11 作者:樂吧的數(shù)學(xué) 0人讀過 | 我要投稿

這個(gè)文章講一下基于泊松過程推導(dǎo)一下 Chernoff-Hoeffding Bounds.

定義隨機(jī)變量：

$X_i%20%3D%0A%0A%5Cbegin%7Bcases%7D%0A%0A%201%20%26%20p_i%20%5C%5C%0A%0A%200%20%26%201-p_i%0A%0A%5Cend%7Bcases%7D$

要求上面的隨機(jī)變量相互獨(dú)立。

定義隨機(jī)變量：

$X%20%3D%20%5Csum_%7Bi%3D1%7D%5En%20X_i$

則我們想知道如下這個(gè)概率：

$P(X%20%5Cge%20m)$

其中 m 大于 X 的均值（數(shù)學(xué)期望），小于等于 n.

下面展開推導(dǎo)過程，具體細(xì)節(jié)會(huì)在視頻中講解。

$P(X%20%5Cge%20m%20)%20%3D%20P(e%5E%7Btx%7D%20%5Cge%20e%5E%7Btm%7D)%20%5Cle%20%5Cfrac%7BE(e%5E%7Btx%7D)%7D%7Be%5E%7Btm%7D%7D%20%20%5Ctag%201$

其中： t > 0

$E(e%5E%7Btx%7D)%20%3D%20E(e%5E%7Bt%5Csum_%7Bi%3D1%7D%5En%20X_i%7D)%20%3D%20E(%5Cprod_%7Bi%3D1%7D%5En%20e%5E%7BtX_i%7D)%20%3D%20%5Cprod_%7Bi%3D1%7D%5En%20E(e%5E%7BtX_i%7D)%20%20%5Ctag%202$

其中：

$E(e%5E%7BtX_i%7D)%20%3D%20p_i%20e%5E%7Bt%5Ctimes%201%7D%20%2B%20(1-p_i)%20e%5E%7Bt%5Ctimes%200%7D%20%3D%20p_i%20e%5Et%20%2B%201-p_i%20%5Ctag%203$

把公式 (3) 代入公式 (2):

$E(e%5E%7Btx%7D)%20%3D%20%5Cprod_%7Bi%3D1%7D%5En(p_i%20e%5Et%20%2B%201-p_i%20)%20%20%5Ctag%204$

用 Arithmatic Mean/Geometric Mean Inequality （算術(shù)幾何平均不等式）：

$%5Cprod_%7Bi%3D1%7D%5En(p_i%20e%5Et%20%2B%201-p_i%20)%20%20%5Cle%20%5Cleft%20(%20%20%20%20%5Cfrac%7B%5Csum_%7Bi%3D1%7D%5En(p_i%20e%5Et%20%2B%201-p_i%20)%20%7D%7Bn%7D%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5Cright%20)%5En%20%20%3D%20(pe%5Et%2B1-p)%5En%20%20%5Ctag%205$

其中 :?

$p%20%3D%20%5Cfrac%7B%5Csum_i%3D1%5En%20p_i%7D%7Bn%7D$

把公式 (5) 代入公式 (4) :

$E(e%5E%7Btx%7D)%20%5Cle%20(pe%5Et%2B1-p)%5En%20%20%5Ctag%206$

公式 (6) 代入公式 (1):

$P(X%20%5Cge%20m%20)%20%5Cle%20%5Cfrac%7B(pe%5Et%2B1-p)%5En%7D%7Be%5E%7Btm%7D%7D%20%3D%20e%5E%7Bln%20%5Cleft%20%5C%7B%20%20%5Cfrac%7B(pe%5Et%2B1-p)%5En%7D%7Be%5E%7Btm%7D%7D%20%20%5Cright%20%5C%7D%20%7D%0A%0A%3D%20e%5E%7B%20n%20ln%20(pe%5Et%2B1-p)-tm%7D%20%20%5Ctag%207$

求公式 (7) 右邊的最小值：

$%5Cfrac%20%7B%5Cpartial%20%5Cleft%20%5B%20n%20ln%20(pe%5Et%2B1-p)-tm%20%5Cright%20%5D%7D%20%20%20%7B%20%5Cpartial%20t%7D%20%3D%20%5Cfrac%7Bn%7D%7Bpe%5Et%2B1-p%7D%20pe%5Et%20-%20m%20%3D%200$

經(jīng)過推導(dǎo)有：

$e%5Et%20%3D%20%5Cfrac%7B(1-p)m%7D%7B(n-m)p%7D%20%20%20%5Ctag%208$

所以：

$t%20%3D%20ln%20%5Cfrac%7B(1-p)m%7D%7B(n-m)p%7D%20%20%5Ctag%209$

把公式 (8) 和 (9) 代入 (7):

$%5Cbegin%7Baligned%7D%0A%0AP(X%20%5Cge%20m%20)%20%26%20%5Cle%20e%5E%7B%20n%20ln%20%5C%7B%5Cfrac%7B(1-p)m%7D%7B(n-m)%20%7D%2B%201%20-%20p%5C%7D%20%20-%20m%20ln%5Cfrac%7B(1-p)m%7D%7B(n-m)p%7D%20%7D%20%5C%5C%20%20%5C%5C%0A%0A%26%20%3D%20e%5E%7B%20n%20ln%20%5Cfrac%7B(1-p)n%7D%7B(n-m)%20%7D%20%20-%20m%20ln%5Cfrac%7B(1-p)m%7D%7B(n-m)p%7D%20%7D%20%5C%5C%20%20%5C%5C%0A%0A%26%3D%20e%5E%7Bn%5Cleft%20%5C%7B%20%20%20%20ln%20%5C%7B%5Cfrac%7B(1-p)%7D%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)%20%7D%5C%7D%20%20-%20%5Cfrac%7Bm%7D%7Bn%7D%20ln%5Cfrac%7B(1-p)%20%5Cfrac%7Bm%7D%7Bn%7D%20%7D%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)p%7D%20%20%20%5Cright%20%5C%7D%7D%20%20%20%5C%5C%20%20%5C%5C%0A%0A%26%3D%20e%5E%7Bn%5Cleft%20%5C%7B%20%20%20(1-%5Cfrac%7Bm%7D%7Bn%7D)%20ln%20%5Cfrac%7B(1-p)%7D%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)%20%7D%20%20-%20%5Cfrac%7Bm%7D%7Bn%7D%20ln%5Cfrac%7B%5Cfrac%7Bm%7D%7Bn%7D%20%7D%7B%20p%7D%20%20%20%5Cright%20%5C%7D%7D%20%5C%5C%0A%0A%26%3D%20e%5E%7B-n%5Cleft%20%5C%7B%20%20%20(1-%5Cfrac%7Bm%7D%7Bn%7D)%20ln%20%5Cfrac%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)%7D%7B(1-p)%20%7D%20%20%2B%20%5Cfrac%7Bm%7D%7Bn%7D%20ln%5Cfrac%7B%5Cfrac%7Bm%7D%7Bn%7D%7D%7Bp%20%7D%20%20%20%5Cright%20%5C%7D%7D%20%5C%5C%20%5C%5C%0A%0A%26%3D%20e%5E%7B-n%20D((1-%5Cfrac%7Bm%7D%7Bn%7D)%7C%7Cp)%7D%20%20%20%20%0A%0A%5Cend%7Baligned%7D%20%20%5Ctag%7B10%7D$

把公式 (10) 寫成不是 e 的指數(shù)的形式:

$%5Cbegin%7Baligned%7D%0A%0AP(X%20%5Cge%20m%20)%20%26%20%5Cle%20%5Cleft%20%5C%7B%20%20%5Cleft%20%5B%5Cfrac%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)%7D%7B(1-p)%20%7D%20%5Cright%20%20%5D%5E%7B(1-%5Cfrac%7Bm%7D%7Bn%7D)%7D%0A%0A%20%5Cleft%20%5B%20%5Cfrac%7B%5Cfrac%7Bm%7D%7Bn%7D%7D%7Bp%20%7D%20%5Cright%20%20%5D%5E%7B%5Cfrac%7Bm%7D%7Bn%7D%7D%0A%0A%20%5Cright%20%5C%7D%20%5E%7B-n%7D%0A%0A%5Cend%7Baligned%7D%20%20%5Ctag%7B11%7D$