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 。求導(dǎo)可知當t = \log(1+\delta)時，取最大值 (\frac{e^{-\delta}}{(1+\delta)^{(1+\delta)}})^{\mu}。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 接觸機器學(xué)習(xí)時間也不短了, 趁國慶放假, 做一下深度整理. 1. 大綱 若想在企業(yè)勝任算法相關(guān)崗位知識, 除了掌握...
    婉妃閱讀 3,525評論 2贊 92
  • 考試形式和試卷結(jié)構(gòu)一、試卷滿分及考試時間 試卷滿分為150分，考試時間為180分鐘 二、答題方式 答題方式為閉卷、...
    幻無名閱讀 869評論 0贊 3
  • 2017年考研數(shù)學(xué)一大綱原文 考試科目：高等數(shù)學(xué)、線性代數(shù)、概率論與數(shù)理統(tǒng)計 考試形式和試卷結(jié)構(gòu) 一、試卷滿分及考...
    SheBang_閱讀 737評論 0贊 7
  • 一直以來，我都有個夢想，開一間甜品店，每天泡在廚房里，做烘焙，并且樂此不疲。如果我沒有上大學(xué)，我想我會去甜品店學(xué)習(xí)...
    大姐姐2333閱讀 872評論 6贊 17
  • 今晚召開了第一個家庭會議，豆妞和爸爸都興致很好，爸爸是記錄員，媽媽主持，豆妞負責(zé)娛樂。豆妞從頭到尾一直都是...
    倚秋閱讀 215評論 0贊 0

友情鏈接更多精彩內(nèi)容