欢迎光临散文网 会员登陆 & 注册

几个概率不等式(三) Chernoff_bounds_用于泊松过程

2023-08-26 09:11 作者:乐吧的数学  | 我要投稿

这个文章讲一下基于泊松过程推导一下 Chernoff-Hoeffding Bounds.


定义随机变量:

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

要求上面的随机变量相互独立。


定义随机变量:

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

则我们想知道如下这个概率:

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

其中 m 大于 X 的均值(数学期望),小于等于 n.


下面展开推导过程,具体细节会在视频中讲解。

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 (算术几何平均不等式):

%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

经过推导有:

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 的指数的形式:

%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







几个概率不等式(三) Chernoff_bounds_用于泊松过程的评论 (共 条)

分享到微博请遵守国家法律