Chernoff Bound

X_i是相互独立的Bernoulli变量,E(X_i) = p_i,记X=\sum X_i\mu = E(X)那么,我们有concentration表达式:

P(X > (1+\delta)\mu) <= e^{-\frac{\delta^2}{3}}.

证明方法:

P(X > (1+\delta)\mu) = P(e^{tX} > e^{(1+\delta)t\mu}) <\frac{E(e^{tX})}{e^{(1+\delta)t\mu}}

而求解E(e^{tX})需要X_i的独立性,变成乘积形式。

E(e^{tX}) = E(e^{t\sum_{i=1}^n X_i}) = \prod E(e^{tX_i})

E(e^{tX_i}) = p_ie^t+1-p_i = 1+p_i(e^t-1) \leq e^{p_i(e^t-1)}

E(e^{tX}) \leq e^{\mu(e^t-1)}

P(X > (1-\delta)\mu) < (\frac{e^{e^t-1}}{e^{(1+\delta)t}})^\mu 。求导可知当t = \log(1+\delta)时,取最大值 (\frac{e^{-\delta}}{(1+\delta)^{(1+\delta)}})^{\mu}

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 接触机器学习时间也不短了, 趁国庆放假, 做一下深度整理. 1. 大纲 若想在企业胜任算法相关岗位知识, 除了掌握...
    婉妃阅读 8,700评论 2 92
  • 考试形式和试卷结构一、试卷满分及考试时间 试卷满分为150分,考试时间为180分钟 二、答题方式 答题方式为闭卷、...
    幻无名阅读 4,164评论 0 3
  • 2017年考研数学一大纲原文 考试科目:高等数学、线性代数、概率论与数理统计 考试形式和试卷结构 一、试卷满分及考...
    SheBang_阅读 3,878评论 0 7
  • 一直以来,我都有个梦想,开一间甜品店,每天泡在厨房里,做烘焙,并且乐此不疲。如果我没有上大学,我想我会去甜品店学习...
    大姐姐2333阅读 4,212评论 6 17
  • 今晚召开了第一个家庭会议,豆妞和爸爸都兴致很好,爸爸是记录员,妈妈主持,豆妞负责娱乐。豆妞从头到尾一直都是...
    倚秋阅读 1,504评论 0 0

友情链接更多精彩内容