请输入您要查询的字词:

 

单词 ProofOfChernoffCramerBound
释义

proof of Chernoff-Cramer bound


Let h(x) be the step functionPlanetmathPlanetmath (h(x)=1 for x0, h(x)=0 for x<0); then, by generalized Markov inequalityMathworldPlanetmath, for any t>0 andany ε0,

Pr{i=1n(Xi-E[Xi])>ε}=E[h(i=1n(Xi-E[Xi])-ε)]
E[et(i=1n(Xi-E[Xi])-ε)]=
=exp(-εt)E[ei=1nt(Xi-E[Xi])]=
=exp(-εt)E[i=1net(Xi-E[Xi])]=
(by independence)=exp(-εt)i=1nE[et(Xi-E[Xi])]=
=exp(-εt+i=1nlnE[et(Xi-E[Xi])])=
=exp[-(tε-ψ(t))].

Since this expression is valid for any t>0, the best bound is obtained taking the supremum:

Pr{i=1n(Xi-E[Xi])>ε}e-supt>0(tε-ψ(t))

which proves part c).

To prove part a), let’s observe that Ψ(0)=supt>0(-ψ(t))=-inft>0(ψ(t))and that

E[et(Xi-E[Xi])]E[1+t(Xi-E[Xi])]=
=E[1]+tE[Xi]-tE[E[Xi]]=
=1=E[et(Xi-E[Xi])]t=0

that is, t=0 is the infimum point for E[et(Xi-E[Xi])] i and consequently for ψ(t)=i=1nlnE[et(Xi-EXi)], so as a conclusion Ψ(0)=-ψ(0)=0

b) Let x>0 be fixed and let t0 be the supremum point for tx-ψ(t); we have to show that t0x-ψ(t0)>0.

By differentiationMathworldPlanetmath, ψ(t0)=x.

Let’s recall that the moment generating function is convex, so ψ′′(t)>0. Writing the Taylor expansionMathworldPlanetmath for ψ(t)around t=t0, we have, with a suitable t1<t0,

0=ψ(0)=ψ(t0)-ψ(t0)t0+12ψ′′(t1)t02

that is

Ψ(x)=t0x-ψ(t0)=t0ψ(t0)-ψ(t0)=12ψ′′(t1)t02>0

The convexity of Ψ(x) follows from the fact that Ψ(x) is the supremum of the linear (and hence convex) functions tx-ψ(t) and so must be convex itself.

Eventually, in to prove that Ψ(x) is an increasing function, let’s note that

Ψ(0)=limx0Ψ(x)-Ψ(0)x=limx0Ψ(x)x>0

and that, by Taylor formula with Lagrange form remainder, for a ξ=ξ(x)

Ψ(x)=Ψ(0)+Ψ′′(ξ)x0

since Ψ′′(ξ)0 by convexity and x0 byhypotheses.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 9:51:26