Editing Chernoff bound (section)

=== Properties ===

The exponential function is convex, so by [[Jensen's inequality]] <math>\operatorname E (e^{t X}) \ge e^{t \operatorname E (X)}</math>. It follows that the bound on the right tail is greater or equal to one when <math>a \le \operatorname E (X)</math>, and therefore trivial; similarly, the left bound is trivial for <math>a \ge \operatorname E (X)</math>. We may therefore combine the two infima and define the two-sided Chernoff bound:<math display="block">C(a) = \inf_{t} M(t) e^{-t a} </math>which provides an upper bound on the folded [[cumulative distribution function]] of <math>X</math> (folded at the mean, not the median).

The logarithm of the two-sided Chernoff bound is known as the [[rate function]] (or ''Cramér transform'') <math>I = -\log C</math>. It is equivalent to the [[Legendre–Fenchel transformation|Legendre–Fenchel transform]] or [[convex conjugate]] of the [[cumulant generating function]] <math>K = \log M</math>, defined as: <math display="block">I(a) = \sup_{t} at - K(t) </math>The [[Moment-generating function#Important properties|moment generating function]] is [[Logarithmically convex function|log-convex]], so by a property of the convex conjugate, the Chernoff bound must be [[Logarithmically concave function|log-concave]]. The Chernoff bound attains its maximum at the mean, <math>C(\operatorname E(X))=1</math>, and is invariant under translation: <math display="inline">C_{X+k}(a) = C_X(a - k) </math>.

The Chernoff bound is exact if and only if <math>X</math> is a single concentrated mass ([[degenerate distribution]]). The bound is tight only at or beyond the extremes of a bounded random variable, where the infima are attained for infinite <math>t</math>. For unbounded random variables the bound is nowhere tight, though it is asymptotically tight up to sub-exponential factors ("exponentially tight").{{Citation needed|date=February 2023}} Individual moments can provide tighter bounds, at the cost of greater analytical complexity.<ref>{{Cite journal |last1=Philips |first1=Thomas K. |last2=Nelson |first2=Randolph |date=1995 |title=The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities |url=https://www.jstor.org/stable/2684633 |journal=The American Statistician |volume=49 |issue=2 |pages=175–178 |doi=10.2307/2684633 |jstor=2684633 |issn=0003-1305}}</ref>

In practice, the exact Chernoff bound may be unwieldy or difficult to evaluate analytically, in which case a suitable upper bound on the moment (or cumulant) generating function may be used instead (e.g. a sub-parabolic CGF giving a sub-Gaussian Chernoff bound).
{| class="wikitable mw-collapsible"
|+Exact rate functions and Chernoff bounds for common distributions
!Distribution
!<math>\operatorname E (X)</math>
!<math>K(t)</math>
!<math>I(a)</math>
!<math>C(a)</math>
|-
|[[Normal distribution]] 
|<math>0</math>
|<math>\frac{1}{2}\sigma^2t^2</math>
|<math>\frac{1}{2} \left( \frac{a}{\sigma} \right)^2</math>
|<math>\exp \left( {-\frac{a^2}{2\sigma^2}} \right)</math>
|-
|[[Bernoulli distribution]](detailed below)
|<math>p</math>
|<math>\ln \left( 1-p + pe^t \right)</math>
|<math>D_{KL}(a \parallel p)</math>
|<math>\left (\frac{p}{a}\right )^{a} {\left (\frac{1 - p}{1-a}\right )}^{1 - a}</math>
|-
|Standard Bernoulli 
(''H'' is the [[binary entropy function]])
|<math>\frac{1}{2}</math>
|<math>\ln \left( 1 + e^t \right) - \ln(2)</math>
|<math>\ln(2) - H(a)</math>
|<math>\frac{1}{2}a^{-a}(1-a)^{-(1-a)}</math>
|-
|[[Rademacher distribution]]
|<math>0</math>
|<math>\ln \cosh(t)</math>
|<math>\ln(2) - H\left(\frac{1+a}{2}\right)</math>
|<math>\sqrt{(1+a)^{-1-a}(1-a)^{-1+a}}</math>
|-
|[[Gamma distribution]]
|<math>\theta k</math>
|<math>-k\ln(1 - \theta t)</math>
|<math>-k\ln\frac{a}{\theta k} -k + \frac{a}{\theta} </math>
|<math>\left(\frac{a}{\theta k}\right)^k e^{k-a/\theta}</math>
|-
|[[Chi-squared distribution]]
|<math>k</math>
|<math>-\frac{k}{2}\ln (1-2t)</math>
|<math>\frac{k}{2} \left(\frac{a}{k} - 1 - \ln \frac{a}{k} \right)</math><ref>{{Cite journal |last=Ghosh |first=Malay |date=2021-03-04 |title=Exponential Tail Bounds for Chisquared Random Variables |journal=Journal of Statistical Theory and Practice |language=en |volume=15 |issue=2 |pages=35 |doi=10.1007/s42519-020-00156-x |s2cid=233546315 |issn=1559-8616|doi-access=free }}</ref>
|<math>\left( \frac{a}{k} \right)^{k/2} e^{k/2-a/2} </math>
|-
|[[Poisson distribution]]
|<math>\lambda</math>
|<math>\lambda(e^t - 1)</math>
|<math>a \ln (a/\lambda) - a + \lambda</math>
|<math>(a/\lambda)^{-a} e^{a-\lambda}</math>
|}