请输入您要查询的字词:

 

单词 ChernoffCramerBound
释义

Chernoff-Cramer bound


The Chernoff-Cramèr inequalityMathworldPlanetmath is a very general and powerful way of bounding random variablesMathworldPlanetmath. Compared with the famous Chebyshev bound, which implies inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmath polynomialPlanetmathPlanetmath decay inequalities, the Chernoff-Cramèr method yields exponential decay inequalities, at the cost of needing a few morehypotheses on random variables’ .

Theorem: (Chernoff-Cramèr inequality)

Let {Xi}i=1n be a collection of independentPlanetmathPlanetmath randomvariables such that E[exp(tXi)]<+  i in a right neighborhoodMathworldPlanetmath of t=0, i.e. for any t(0,c) (Cramèr condition).

Then a zero-valued for x=0, positive, strictly increasing, strictly convex function Ψ(x):[0,)R+ existssuch that:

Pr{i=1n(Xi-E[Xi])>ε}exp(-Ψ(ε))ε0

Namely, one has:

Ψ(x)=sup0<t<c(tx-ψ(t))
ψ(t)=i=1nlnE[et(Xi-EXi)]=i=1n(lnE[etXi]-tE[Xi])

that is, Ψ(x) is the Legendre of the cumulant generating function of the i=1n(Xi-E[Xi]) random variable.

Remarks:

1) Besides its importance for theoretical questions, the Chernoff-Cramér bound is also the starting point to derive many deviationor concentration inequalities, among which Bernstein (http://planetmath.org/BernsteinInequality), Kolmogorov, Prohorov (http://planetmath.org/ProhorovInequality), Bennett (http://planetmath.org/BennettInequality),Hoeffding and Chernoff ones are worth mentioning. All of theseinequalities are obtained imposing various further conditions on Xi random variables, which turn out to affect the general form of the cumulant generating function ψ(t).
2) Sometimes, instead of bounding the sum of n independent random variables, one needs to estimate they ” i.e. the quantity 1ni=1nXi; in to reuse Chernoff-Cramér bound, it’s enough to note that

Pr{1ni=1n(Xi-E[Xi])>ε}=Pr{i=1n(Xi-E[Xi])>nε}

so that one has only to replace, in the above stated inequality, ε with nε.
3) It turns out that the Chernoff-Cramer bound is asymptotically sharp, as Cramèr theorem shows.

随便看

 

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

 

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