Large deviations and rare events

For a positive tilt theta, the event that a sum exceeds a threshold is equivalent to the exponential of that sum exceeding the exponential threshold. Markov's inequality then bounds the event probability by an exponential moment divided by the threshold. With independent identically distributed contributions, the moment factors into a product. Taking its logarithm makes the exponent linear in sample size. Independence and finiteness of the chosen moment are the two critical permissions in this calculation.

Optimizing over allowed positive theta yields the strongest bound of this form for an upper tail. This is a finite-sample inequality, so it remains a bound even when sample size is modest. For variables with no finite positive exponential moments, the same derivation supplies no useful positive-tilt estimate. Heavy-tailed sums can be dominated by one unusually large contribution rather than a coordinated shift of many moderate ones. A formula derived for light tails should not be applied merely because a sample average exists.

Under Cramér's theorem, IID real random variables whose moment-generating function is finite in a neighborhood of zero satisfy a large-deviation principle for their empirical means. The rate is the Legendre–Fenchel transform of the log moment-generating function. The theorem gives upper bounds for closed sets and lower bounds for open sets on the scale of logarithm divided by n. Turning these into one equality for a particular event requires regularity of that event and agreement of the relevant rate infima.

For Bernoulli variables with success probability p strictly between zero and one, the rate at an empirical success fraction a is binary relative entropy D(a||p). It is nonnegative and vanishes at a=p. For a>p, it gives the Chernoff exponent for an upper tail; a below p instead calls for a lower-tail analysis using negative tilts. Endpoint values use continuous conventions such as zero times log zero equals zero. A divergence in probability-parameter space measures the cost of an atypical empirical law, rather than an ordinary distance between individual outcomes.

A logarithmic asymptotic of the form probability approximately exp(−nI) identifies the dominant exponential decay while allowing polynomial factors and other subexponential corrections. It may be accurate in log probability yet inaccurate by a large multiplicative factor. An optimized Chernoff inequality is an upper bound, not an assertion that the probability attains that bound. For a small binomial model, summing exact terms supplies a valuable independent benchmark and exposes the difference between exponential order, finite-sample bounds, and exact values.

Naive Monte Carlo struggles when the event probability r is tiny: the variance of an indicator average is r(1−r)/N, giving relative standard error about 1/√(Nr). Observing no events does not establish r=0. Exponential tilting can make the rare empirical mean typical under a proposal distribution, after which likelihood-ratio weights recover the original probability. A good proposal must still cover the event and control weighted variance. Large-deviation geometry guides that choice, while estimator diagnostics and exact checks establish whether it actually improved the computation.