Large Deviations 1 – Motivation and Cramer’s Theorem | Eventually Almost Everywhere

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 i.i.d. real-valued random variables with finite expectation, and , the Weak Law of Large Numbers asserts that the empirical mean converges in distribution to . So . In fact, if , we have the Central Limit Theorem, and a consequence is that whenever . 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 tends to zero. So the probability that at least 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: There are two observations to be made. The first is that the sec

saved by

• Mike Liang