The Chernoff exponent is a Legendre transform
ProofAdvanced⏱ 1 hourHigh-Dim Probabilitychernofflegendrelarge deviationsrate function
Problem
Let be i.i.d. with cumulant generating function finite near . Show that the Chernoff bound for reads
and compute explicitly for (i) and (ii) Bernoulli. Verify in each case that is non-negative, zero exactly at , 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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Markov and Chebyshev are attained | High-Dim Probability | Proof | 15 min | ||
| Azuma for a random walk with drift | High-Dim Probability | Proof | 30 min | ||
| Derive Hoeffding's inequality from Hoeffding's lemma | High-Dim Probability | Proof | 30 min | ||
| Locating the Bernstein crossover | High-Dim Probability | Numerical | 30 min | ||
| Simulate and compare the concentration inequalities run | High-Dim Probability | Coding | 1 hour |