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
  • 2017年考研《数学一》大纲
    考试形式和试卷结构一、试卷满分及考试时间 试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、...
    幻无名阅读 4,164评论 0赞 3
  • 数学一考研大纲
    2017年考研数学一大纲原文 考试科目：高等数学、线性代数、概率论与数理统计 考试形式和试卷结构 一、试卷满分及考...
    SheBang_阅读 3,878评论 0赞 7
  • 烘焙新手的甜品梦—蛋挞篇
    一直以来，我都有个梦想，开一间甜品店，每天泡在厨房里，做烘焙，并且乐此不疲。如果我没有上大学，我想我会去甜品店学习...
    大姐姐2333阅读 4,212评论 6赞 17
  • PD正面管教打卡 家庭会议
    今晚召开了第一个家庭会议，豆妞和爸爸都兴致很好，爸爸是记录员，妈妈主持，豆妞负责娱乐。豆妞从头到尾一直都是...
    倚秋阅读 1,504评论 0赞 0

友情链接更多精彩内容