Processing math: 100%
ThmDex – An index of mathematical definitions, results, and conjectures.
Probabilistic Chernoff inequality
Formulation 0
Let XRandom(R) be a D3161: Random real number.
Let λ>0 be a D5407: Positive real number.
Then P(Xλ)inft[0,)1etλE(etX)
Also known as
Probabilistic Chernoff bound
Proofs
Proof 0
Let XRandom(R) be a D3161: Random real number.
Let λ>0 be a D5407: Positive real number.
Let 0t< be an unsigned basic real number. Since etX now takes values in (0,)[0,), then we may apply R2016: Probabilistic Markov's inequality to obtain the inequality P(Xλ)=P(etXetλ)1etλE(etX) Since t[0,) was arbitrary, we may extend the right-hand side to infimum to obtain P(Xλ)inft[0,)1etλE(etX)