1、1第四章：不等式n不等式2markov不等式n4.1 定理（ markov不等式）：令x為非負隨機變量且假設 存在，則對任意 ，有n當 ，( )xe0t ()( )() 4.1xp xtte( ),tkxm m= e()1xkkmp1 k01kpp3markov 不等式證明：x 為非負隨機變量，對任何 t0，有()( )xxttep 證明： 0x 0 xxfx dxe （x 非負，所以積分區間從 0 開始） 0ttxfx dxxfx dx （分成兩段積分） txfx dx （ 00,0,0txtxfx dx，求和部分去掉正的一部分，不等號成立） ttfx dx （將 t 放到積分符號外面，相當

2、于令,xt由于,xt不等號成立） txtp xxttep 4markov不等式n將 換成滿足條件的 ( )，上述結論也成立！( )()22xr xms-=( )()( )()r xr xttep5chebyshev不等式n4.2 定理（chebyshev不等式）：令n則n其中n 在其期望附近（ 鄰域）的概率與方差 有關( )( )2,xxms=ev()()2221 xtzktksm-常常pp()zxms=-()()21 4,31 9.zzpp2s2s2s6chebyshev 不等式證明：令( )( )2,xxms=ev，則()22xttsm-常p 證明：()()()22xtxtmm-=-pp

3、（兩邊同時平方） ()()22xtm-e （markov 不等式） 22ts 當tk，則()( )2221xxkkkkmsmsss驏-常=桫pp 7chebyshev不等式在其期望附近（ 鄰域）的概率與方差 有關n另外一個變形：()21xkkms-常p2s()20.25xms-常p()30.11xms-常p()222222111222txxttxeztxedxedxttppp-=蝌p()()2222teztzttp-常pp()0,1znmills inequality8chebyshev不等式n4.3例：假設我們在一個有n個測試樣本的測試集上測試一個預測方法（以神經網絡為例）。若預測錯誤置 預

4、測正確則置 。則 為觀測到的錯誤率。每個 可視為有未知均值 的bernoulli分布。我們想知道真正的錯誤率 。n直觀地，我們希望 接近 。但 有多大可能不在 的鄰域內？n n由于對任意 有 ，所以當 時，邊界為0.0625。 1ix =0ix =-11nniixnx=ixnxnx( )( )()()( )()12221,11=.4nnnxxnppnxppxpnneeee=-常vvvp= 0.2,100 ne=()141pp-9hoeffding不等式n作用與chebyshev不等式類似，但區間更緊致（增加了獨立性約束）n4.4 定理（ hoeffding不等式）：設 相互獨立，且 。令 ，則

5、對任意n4.5 定理（ hoeffding不等式）：令 則對任意 ，有n其中0t 1nyy,.( )0,iiiiyayb=且e0e()22811 iinntbatiiiyeeee-=驏常 桫p( )1,.nxxbernoulli p:0e()222nnxpeee-p-11nniixnx=()1iiyxpn=-10hoeffding 不等式證明： 證明：1111nniiiinntytyttiiiiytyteeeeeeee=-=驏驏鼢邋驏驏瓏鼢瓏鼢瓏鼢常鼢瓏瓏鼢鼢瓏瓏鼢鼢桫桫瓏鼢鼢瓏桫桫邋pppe （markov 不等式） ( )1itntiyeee-=e （1） , 1, iiiiiiiiiia

6、ybybayaba 由于tye為凸函數，所以iiitytbtaiiiiiiiiyabyeeebaba iiitbtaiiiyiiig utabeeabeebae （ 0iye） 其中 ,log 1,uiiiiiiut bag uaea ba 000,1 4, 0gggufor u 根據 talayor 展開， 222221100288iiug ugugu ggutba 所以( )( )()228iiig ubytateee-e，代入（1） ，不等式得證。 11hoeffding不等式n4.6 例：令n則根據chebyshev不等式，有n根據hoeffding不等式，有n結果遠遠小于0.0625

7、。( )1,.nxxbernoulli p:100,0.2 ne=()0.0625.nxpe-p()() ( )22 100 .2.220.00067.nxpe-=p()( )2nnxpxee-常pv()222nnxpeee-常p12hoeffding不等式n可用來計算二項分布中的參數 的置信區間n對給定的 ，令n則根據hoeffding不等式n令 ，則n則 。n稱 為 置信區間。0a1a-1212log2nnea禳驏镲镲=睚镲桫镲鉿()222nnnnxpeeea-=p(),nncxxee=-+()()ncpxpea=-pp()1cpa緯-p13cauchy-schwarze不等式n4.8 定

8、理（ cauchy-schwarze不等式）：若 、 是有限方差，則()() ( )22 xyxyeee()()()()()()()22,xyxyxycov x yxyxymmmms s輊=-=臌eee()()222,xycov x ys s()cov,11xyx yrs s-=14jensen不等式n4.9 定理（ jensen不等式）：如果 是凸的，則( )( )()g xgx g ege( )( )()g xgxeeg( )()()222g xxxx=蕹 ee( )111g xxxx驏=蕹桫ee( )()()logloglogg xxxx=蓿 ee15 l xabxaxe g xa證明： ( )g x為凸函數，則( )()g xgxee 證明：令在點xx= e處，函數( )g x的切線為( )l xabx=+ 由于 ( )g x為凸函數，( )g x位于其切線之上，即 ( )( )g xl xabx=+ 所以 ( )()g xabx+ee （兩邊同區期望，不等式仍然成立） ab x=+e （期望的線性性質） ()lx=e （l 的定義） ()gx=e （在切點xxe處，l 等于函數值） 16凸函數n如果對所有的 ，滿足n則函數 為凸函數（convex）， 為凹函數（concave）(1) )( )(1) ( )gxyg xg y, , 0 1x y( )g