Large Deviations – Cramer’s theorem

Last summer I attended a conference on “Dynamics and Numbers” at the Max Planck Institute in Bonn. Vincent Delecroix gave a nice talk on large deviations for the Teichmuller flow, and I decided to learn a bit about this concept. I wrote the notes below at that time.

In this post, I will prove the simplest example of large deviations – Cramer’s theorem. Here is a simple example. Consider a random coin toss, and at each step you either win or loose {1} dollar. After {N} steps, consider the probability of having more than {aN} dollars, where {a>0} is fixed. Of course, it goes to zero as {N{\rightarrow} \infty}, but how fast? Playing around with Stirling’s formula reveals that the probability decays exponentially fast.

The theory of large deviations is concerned with these kinds of exponentially unlikely events. We now move on to a more precise setup. Continue reading