Large Deviations 1 – Motivation and Cramer’s Theorem

I’ve been doing a lot of thinking about Large Deviations recently, in particular how to apply the theory to random graphs and related models. I’ve just writing an article about some of the more interesting aspects, so thought it was probably worth turning it into a few posts.

Motivation

Given $X_1,X_2,\ldots$ i.i.d. real-valued random variables with finite expectation, and $S_n:=X_1+\ldots+X_n$ , the Weak Law of Large Numbers asserts that the empirical mean $\frac{S_n}{n}$ converges in distribution to $\mathbb{E}X_1$ . So $\mathbb{P}(S_n\geq n(\mathbb{E}X_1+\epsilon))\rightarrow 0$ . In fact, if $\mathbb{E}X_1^2<\infty$ , we have the Central Limit Theorem, and a consequence is that $\mathbb{P}(S_n\geq n\mathbb{E}X_1+n^\alpha)\rightarrow 0$ whenever $\alpha>\frac12$ .

In a concrete example, if we toss a coin some suitably large number of times, the probability that the proportion of heads will be substantially greater or smaller than $\frac12$ tends to zero. So the probability that at least $\frac34$ of the results are heads tends to zero. But how fast? Consider first four tosses, then eight. A quick addition of the relevant terms in the binomial distribution gives:

$\mathbb{P}\left(\text{At least }\tfrac34\text{ out of four tosses are heads}\right)=\frac{1}{16}+\frac{4}{16}=\frac{5}{16},$

$\mathbb{P}\left(\text{At least }\tfrac34\text{ out of twelve tosses are heads}\right)=\frac{1}{2^{12}}+\frac{12}{2^{12}}+\frac{66}{2^{12}}+\frac{220}{2^{12}}=\frac{299}{2^{12}}.$

There are two observations to be made. The first is that the second is substantially smaller than the first – the decay appears to be relatively fast. The second observation is that $\frac{220}{2^{12}}$ is substantially larger than the rest of the sum. So by far the most likely way for at least $\tfrac34$ out of twelve tosses to be heads is if exactly $\tfrac34$ are heads. Cramer’s theorem applies to a general i.i.d. sequence of RVs, provided the tail is not too heavy. It show that the probability of any such large deviation event decays exponentially with n, and identifies the exponent.

Theorem (Cramer): Let $(X_i)$ be i.i.d. real-valued random variables which satisfy $\mathbb{E}e^{tX_1}<\infty$ for every $t\in\mathbb{R}$ . Then for any $a>\mathbb{E}X_1$ ,

$\lim_{n\rightarrow \infty}\frac{1}{n}\log\mathbb{P}(S_n\geq an)=-I(a),$

$\text{where}\quad I(z):=\sup_{t\in\mathbb{R}}\left[zt-\log\mathbb{E}e^{tX_1}\right].$

Remarks

So, informally, $\mathbb{P}(S_n\geq an)\sim e^{-nI(a)}$ .
I(z) is called the Fenchel-Legendre transform (or convex conjugate) of $\log\mathbb{E}e^{tX_1}$ .
Considering t=0 confirms that $I(z)\in[0,\infty]$ .
In their extremely useful book, Dembo and Zeitouni present this theorem in greater generality, allowing $X_i$ to be supported on $\mathbb{R}^d$ , considering a more general set of large deviation events, and relaxing the requirement for finite mean, and thus also the finite moment generating function condition. All of this will still be a special case of the Gartner-Ellis theorem, which will be examined in a subsequent post, so we make do with this form of Cramer’s result for now.

The proof of Cramer’s theorem splits into an upper bound and a lower bound. The former is relatively straightforward, applying Markov’s inequality to $e^{tS_n}$ , then optimising over the choice of t. This idea is referred to by various sources as the exponential Chebyshev inequality or a Chernoff bound. The lower bound is more challenging. We reweight the distribution function F(x) of $X_1$ by a factor $e^{tx}$ , then choose t so that the large deviation event is in fact now within the treatment of the CLT, from which suitable bounds are obtained.

To avoid overcomplicating this initial presentation, some details have been omitted. It is not clear, for example, whether I(x) should be finite whenever x is in the support of $X_1$ . (It certainly must be infinite outside – consider the probability that 150% or -40% of coin tosses come up heads!) In order to call this a Large Deviation Principle, we also want some extra regularity on I(x), not least to ensure it is unique. This will be discussed in the next posts.

7 thoughts on “Large Deviations 1 – Motivation and Cramer’s Theorem”

Pingback: Kraft’s inequality | cartesian product
Pingback: Large Deviations 4 – Sanov’s Theorem | Eventually Almost Everywhere
Pingback: Poisson Tails | Eventually Almost Everywhere
Pingback: Large Deviations 5 – Stochastic Processes and Mogulskii’s Theorem | Eventually Almost Everywhere
Pingback: Azuma-Hoeffding Inequality | Eventually Almost Everywhere
Pingback: Random walks conditioned to stay positive | Eventually Almost Everywhere
Pingback: When does it help to write a function as f(x)=supf(x) = sup_alpha phi_{alpha}(x) (an upper envelope)? – Math Solution

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Large Deviations 1 – Motivation and Cramer’s Theorem

7 thoughts on “Large Deviations 1 – Motivation and Cramer’s Theorem”

Leave a Reply Cancel reply

Share this:

Like this:

Related

7 thoughts on “Large Deviations 1 – Motivation and Cramer’s Theorem”

Leave a Reply Cancel reply