# Cramér's Theorem

The **cumulant generating function** of a real-valued random variable $X$ is $K_X(t) \equiv \log{\mathbb{E}[e^{tX}]}$, assuming the expectations exist for some range of $t$. Applying the exponential version of the Markov inequality yields, for any positive $t$

Taking the tightest bound over all $t$,

(2)Cramér's theorem extends this idea to bounds on the deviation of averages from expectation values. Take a sequence of IID copies of the random variable $X_1, X_2, \ldots$ and consider the sum $S_n$ of the first $n$ copies. The cumulative generating function of $S_n$ is $nK_X(t)$. Applying the above result

(3)This is called a large deviations result because the size of the deviation $\epsilon$ remains constant as $n$ grows. The full version of Cramér's theorem shows that there is a lower bound on the asymptotic probability which decays at the same rate as this upper bound.