Skip to content
nonconvexcard

The Chernoff exponent is a Legendre transform

ProofAdvanced⏱ 1 hourHigh-Dim Probabilitychernofflegendrelarge deviationsrate function

Problem

Let X1,…,XnX_1,\dots,X_n be i.i.d. with cumulant generating function ψ(λ)=log⁡EeλX1\psi(\lambda) = \log\E e^{\lambda X_1} finite near 00. Show that the Chernoff bound for Xˉn\bar X_n reads

P(Xˉn≥a)≤e−nψ∗(a),ψ∗(a)=sup⁡λ>0(λa−ψ(λ)),\P(\bar X_n \ge a) \le e^{-n\psi^*(a)}, \qquad \psi^*(a) = \sup_{\lambda>0}\big(\lambda a - \psi(\lambda)\big),

and compute ψ∗\psi^* explicitly for (i) X1∼N(0,σ2)X_1\sim\Ncal(0,\sigma^2) and (ii) X1X_1 Bernoulli(p)(p). Verify in each case that ψ∗(a)\psi^*(a) is non-negative, zero exactly at a=EX1a = \E X_1, and convex.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
Azuma for a random walk with driftHigh-Dim ProbabilityProofIntermediate30 min
Derive Hoeffding's inequality from Hoeffding's lemmaHigh-Dim ProbabilityProofIntermediate30 min
Locating the Bernstein crossoverHigh-Dim ProbabilityNumericalIntermediate30 min
Simulate and compare the concentration inequalities runHigh-Dim ProbabilityCodingIntermediate1 hour