Subgaussian random variables, Hoeffding’s inequality, and Cramér’s large deviation theorem

1 Subgaussian random variables

For a random variable $X$, let ${\mathrm{\Lambda }}_X(t)=\log E(e^{tX})$, the cumulant generating function of $X$. A $b$-subgaussian random variable, $b>0$, is a random variable $X$ such that

$${\mathrm{\Lambda }}_X(t)\le \frac{b^2{t}^2}{2},t\in ℝ.$$

We remark that for ${\gamma }_{a,{\sigma }^2}$ a Gaussian measure, whose density with respect to Lebesgue measure on $ℝ$ is

$$p(x,a,{\sigma }^2)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{{(x-a)}^2}{2{\sigma }^2}},$$

we have

$${\int }_{ℝ}{e}^{tx}𝑑{\gamma }_{0,b^2}(x)={\int }_{ℝ}{e}^{bty}\frac{1}{\sqrt{2\pi }}{e}^{-\frac{y^2}{2}}𝑑y={\int }_{ℝ}{e}^{\frac{b^2{t}^2}{2}}\frac{1}{\sqrt{2\pi }}{e}^{-\frac{{(y-bt)}^2}{2}}𝑑y=e^{\frac{b^2{t}^2}{2}}.$$

We prove that a $b$-subgaussian random variable is centered and has variance $\le b^2$.

Theorem 1.

If $X$ is $b$-subgaussian then $E(X)=0$ and $\mathrm{Var}(X)\le b^2$.

Proof.

For each $\omega \in \mathrm{\Omega }$, ${\sum }_{k=0}^n\frac{t^{k}X{(\omega )}^k}{k!}\to e^{tX(\omega )}$, and by the dominated convergence theorem,

$$\sum _{k=0}^n\frac{t^{k}E{(X)}^k}{k!}\to E(e^{tX})\le e^{\frac{b^2{t}^2}{2}}=\sum _{k=0}^{\mathrm{\infty }}{\left(\frac{b^2{t}^2}{2}\right)}^k\frac{1}{k!}.$$

Therefore

$$1+tE(X)+t^{2}E(X^2)+O(t^3)\le 1+\frac{b^2{t}^2}{2}+O(t^4),$$

whence

$$tE(X)+t^{2}E(X^2)\le \frac{b^2{t}^2}{2}+o(t^2),$$

and so, for $t>0$,

$$E(X)+tE(X^2)\le \frac{b^{2}t}{2}+o(t).$$

First, this yields $E(X)=o(t)$, which means that $E(X)=0$. Second, since $E(X)=0$,

$$tE(X^2)\le \frac{b^{2}t}{2}+o(t),$$

and then

$$E(X^2)\le \frac{b^2}{2}+o(1),$$

which measn that $E(X^2)\le \frac{b^2}{2}$. ∎

Stromberg attributes the following theorem to Saeki; further, it is proved in Stromberg that if for some $t$ the inequality in the theorem is an equality then the random variable has the Rademacher distribution.

Theorem 2.

If $X$ is a random variable satisfying $E(X)=0$ and $P(X\in [-1,1])=1$, then

$$E(e^{tX})\le \cosh t,t\in ℝ.$$

Proof.

Define $f:ℝ\to ℝ$ by

$$f(t)=e^t\left(\cosh t-E(e^{tX})\right)=\frac{e^{2t}}{2}+\frac{1}{2}-e^{t}E(e^{tX}).$$

Then

$$f^{\prime }(t)=e^{2t}-e^{t}E(e^{tX})-e^{t}E(X{e}^{tX});$$

the derivative of $E(e^{tX})$ with respect to $t$ is obtained using the dominated convergence theorem. Let $Y=1+X$, with which

$$f^{\prime }(t)=e^{2t}-E(e^{tY})-E(X{e}^{tY})=e^{2t}-E(e^{tY})-E((Y-1)e^{tY})=e^{2t}-E(Y{e}^{tY}).$$

$E(X)=0$, so $E(Y)=1$, hence

$$f^{\prime }(t)=E(e^{2t}Y)-E(Y{e}^{tY})=E(Y(e^{2t}-e^{tY})).$$

Because $P(Y\in [0,2])=1$, for $t\ge 0$, we have almost surely $e^{2t}-e^{tY}\ge 0$, and therefore almost surely $Y(e^{2t}-e^{tY})\ge 0$. Therefore, for $t\ge 0$,

$$f^{\prime }(t)=E(Y(e^{2t}-e^{tY}))\ge 0,$$

which tells us that for $t\ge 0$,

$$f(0)\le f(t).$$

As $f(0)=0$, for $t\ge 0$,

$$0\le e^t\left(\cosh t-E(e^{tX})\right),$$

and so

$$E(e^{tX})\le \cosh t.$$

∎

Corollary 3.

If a random variable $X$ satisfies $E(X)=0$ and $P(|X|\le b)=1$, then $X$ is $b$-subgaussian.

2 Hoeffding’s inequality

We first prove Hoeffding’s lemma.

Lemma 4 (Hoeffding’s lemma).

If a random variable $X$ satisfies $E(X)=0$ and $P(X\in [a,b])=1$, then $X$ is $\frac{b-a}{2}$-subgaussian.

Proof.

Because $P(X\in [a,b])=1$, it follows that

$$\mathrm{Var}(X)\le \frac{{(b-a)}^2}{4},$$

not using that $P(X)=0$. (Namely, Popoviciu’s inequality.)

Write $\mu =X_{*}P$ and for $\lambda \in ℝ$ define

$$d{\nu }_{\lambda }(t)=\frac{e^{\lambda t}}{e^{\mathrm{\Lambda }(\lambda )}}d\mu (t).$$

We check

$${\int }_{ℝ}𝑑{\nu }_{\lambda }(t)=\frac{1}{e^{\mathrm{\Lambda }(\lambda )}}{\int }_{ℝ}{e}^{\lambda t}d(X_{*}P)(t)=\frac{1}{e^{\mathrm{\Lambda }(\lambda )}}{\int }_{\mathrm{\Omega }}{e}^{\lambda X}𝑑P=1.$$

There is a random variable $X_{\lambda }:({\mathrm{\Omega }}_{\lambda },{ℱ}_{\lambda },P_{\lambda })\to ℝ$ for which $X_{\lambda }{}_{*}{P}_{\lambda }={\nu }_{\lambda }$. $X_{\lambda }$ satisfies $P_{\lambda }(X_{\lambda }\in [a,b])=1$, and so

$$\mathrm{Var}(X_{\lambda })\le \frac{{(b-a)}^2}{4}.$$

We calculate

$${\mathrm{\Lambda }}_X^{\prime }(t)=\frac{E(X{e}^{tX})}{E(e^{tX})}$$

and

$${\mathrm{\Lambda }}_X^{\prime \prime }(t)=\frac{E(X^2{e}^{tX})E(e^{tX})-E(X{e}^{tX})E(X{e}^{tX})}{E{(e^{tX})}^2}.$$

But

$$E(X_{\lambda })={\int }_{ℝ}t𝑑{\nu }_{\lambda }(t)={\int }_{ℝ}t\frac{e^{\lambda t}}{e^{\mathrm{\Lambda }(\lambda )}}𝑑\mu (t)=\frac{1}{e^{\mathrm{\Lambda }(\lambda )}}E(X{e}^{\lambda X})$$

and

$$E(X_{\lambda }^2)={\int }_{ℝ}{t}^2𝑑{\nu }_{\lambda }(t)=\frac{1}{e^{\mathrm{\Lambda }(\lambda )}}E(X^2{e}^{\lambda X}),$$

and so

$\mathrm{Var}(X_{\lambda })$ $=E(X_{\lambda }^2)-E{(X_{\lambda })}^2$

$={\displaystyle \frac{E(X^2{e}^{\lambda X})}{e^{\mathrm{\Lambda }(\lambda )}}}-{\displaystyle \frac{E{(X{e}^{\lambda X})}^2}{e^{2\mathrm{\Lambda }(\lambda )}}}$

$={\mathrm{\Lambda }}_X^{\prime \prime }(\lambda ).$

For $\lambda \in ℝ$, Taylor’s theorem tells us that there is some $\theta$ between $0$ and $\lambda$ such that

$${\mathrm{\Lambda }}_X(\lambda )={\mathrm{\Lambda }}_X(0)+\lambda {\mathrm{\Lambda }}_X^{\prime }(0)+\frac{{\lambda }^2}{2}{\mathrm{\Lambda }}_X^{\prime \prime }(\theta )=\frac{{\lambda }^2}{2}{\mathrm{\Lambda }}_X^{\prime \prime }(\theta );$$

here we have used that $E(X)=0$. But from what we have shown, $\mathrm{Var}(X_{\theta })={\mathrm{\Lambda }}_X^{\prime \prime }(\theta )$ and $\mathrm{Var}(X_{\theta })\le \frac{{(b-a)}^2}{4}$, so

$${\mathrm{\Lambda }}_X(\lambda )=\frac{{\lambda }^2}{2}\mathrm{Var}(X_{\theta })\le \frac{{\lambda }^2}{2}\cdot \frac{{(b-a)}^2}{4},$$

which shows that $X$ is $\frac{b-a}{2}$-subgaussian. ∎

We now prove Hoeffding’s inequality.

Theorem 5 (Hoeffding’s inequality).

Let $X_1,\mathrm{\dots },X_n$ be independent random variables such that for each $1\le k\le n$, $P(X_k\in [a_k,b_k])=1$, and write $S_n={\sum }_{k=1}^n{X}_k$. For any $a>0$,

$$P(S_n-E(S_n)\ge a)\le \exp (-\frac{2a^2}{{\sum }_{k=1}^n{(b_k-a_k)}^2}).$$

Proof.

For $\lambda >0$ and $\varphi (t)=e^{\lambda t}$, because $\varphi$ is nonnegative and nondecreasing, for $X$ a random variable we have

$$1_{X\ge a}\varphi (a)\le \varphi (X),$$

and so $E(1_{X\ge a}\varphi (a))\le E(\varphi (X))$, i.e.

$$P(X\ge a)\le \frac{E(e^{\lambda X})}{e^{\lambda a}}.$$

Using this with $X=S_n-E(S_n)$ and because the $X_k$ are independent,

$$P(S_n-E(S_n)\ge a)\le \frac{1}{e^{\lambda a}}E(e^{\lambda (S_n-E(S_n))})=e^{-\lambda a}\prod _{k=1}^{n}E(e^{\lambda (X_k-E(X_k))}).$$

Because $P(X_k\in [a_k,b_k])=1$, we have $P(X_k-E(X_k)\in [a_k-E(X_k),b_k-E(X_k)])=1$, and as $(b_k-E(X_k))-(a_k-E(X_k))=b_k-a_k$, Hoeffding’s lemma tells us

$$\log E(e^{\lambda (X_k-E(X_k))})\le \frac{{(b_k-a_k)}^2{\lambda }^2}{8},$$

and thus

$P(S_n-E(S_n)\ge a)$ $\le e^{-\lambda a}\exp \left({\displaystyle \sum _{k=1}^n}{\displaystyle \frac{{(b_k-a_k)}^2{\lambda }^2}{8}}\right)$

$=\exp \left(-\lambda a+{\displaystyle \frac{{\lambda }^2}{8}}{\displaystyle \sum _{k=1}^n}{(b_k-a_k)}^2\right).$

We remark that $\lambda$ does not appear in the left-hand side. Define

$$g(\lambda )=-\lambda a+\frac{{\lambda }^2}{8}\sum _{k=1}^n{(b_k-a_k)}^2,$$

for which

$$g^{\prime }(\lambda )=-a+\frac{\lambda }{4}\sum _{k=1}^n{(b_k-a_k)}^2.$$

Then $g^{\prime }(\lambda )=0$ if and only if

$$\lambda =\frac{4a}{{\sum }_{k=1}^n{(b_k-a_k)}^2},$$

at which $g$ assumes its infimum. Then

$P(S_n-E(S_n)\ge a)$ $\le \exp \left(-{\displaystyle \frac{4a^2}{{\sum }_{k=1}^n{(b_k-a_k)}^2}}+{\displaystyle \frac{16a^2}{8}}{\displaystyle \frac{1}{{\sum }_{k=1}^n{(b_k-a_k)}^2}}\right)$

$=\exp \left(-{\displaystyle \frac{2a}{{\sum }_{k=1}^n{(b_k-a_k)}^2}}\right),$

proving the claim. ∎

3 Cramér’s large deviation theorem

The following is Cramér’s large deviation theorem.

Theorem 6 (Cramér’s large deviation theorem).

Suppose that $X_n:(\mathrm{\Omega },ℱ,P)\to ℝ$, $n\ge 1$, are independent identically distributed random variables such that for all $t\in ℝ$,

For $x\in ℝ$ define

$${\mathrm{\Lambda }}^{*}(x)=\underset{t\in ℝ}{sup}(tx-\mathrm{\Lambda }(t)).$$

If $a>E(X_1)$, then

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log P(S_n\ge an)=-{\mathrm{\Lambda }}^{*}(a),$$

where $S_n={\sum }_{k=1}^n{X}_k$.

Proof.

For $a>E(X_1)$, let $Y_n=X_n-a$, let

$$L(t)=\log E(e^{t{Y}_1})=\log E(e^{t{X}_1}{e}^{-ta})=-ta+\mathrm{\Lambda }(t)$$

and let

$$L^{*}(x)=\underset{t\in ℝ}{sup}(tx-L(t))=\underset{t\in ℝ}{sup}(t(x+a)-\mathrm{\Lambda }(t))={\mathrm{\Lambda }}^{*}(x+a).$$

Lastly, let $T_n={\sum }_{k=1}^n{Y}_k=S_n-na$, with which

$$P(T_n\ge bn)=P(S_n\ge (b+a)n).$$

Thus, if we have

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log P(T_n\ge 0)=-L^{*}(0),$$

then

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log P(S_n\ge an)=-L^{*}(0)=-{\mathrm{\Lambda }}^{*}(a).$$

Therefore it suffices to prove the theorem for when and $a=0$.

Define

$$\varphi (t)=e^{\mathrm{\Lambda }(t)}=E(e^{t{X}_1})={\int }_{\mathrm{\Omega }}{e}^{t{X}_1}𝑑P={\int }_{ℝ}{e}^{tx}d(X_1{}_{*}P)(x),t\in ℝ,$$

the moment generating function of $X_1$, and define

$$\rho =e^{-{\mathrm{\Lambda }}^{*}(0)}=\exp \left(-\underset{t\in ℝ}{sup}(-\mathrm{\Lambda }(t))\right)=\exp \left(\underset{t\in ℝ}{inf}\mathrm{\Lambda }(t)\right)=\underset{t\in ℝ}{inf}\varphi (t),$$

using that $x\mapsto e^x$ is increasing.

Using the dominated convergence theorem, for $k\ge 0$ we obtain

$${\varphi }^{(k)}(t)={\int }_{ℝ}{x}^k{e}^{tx}d(X_1{}_{*}P)(x)=E(X_1^k{e}^{t{X}_1}).$$

In particular, ${\varphi }^{\prime }(t)=E(X_1{e}^{t{X}_1})$, for which , and ${\varphi }^{\prime \prime }(t)=E(X_1^2{e}^{t{X}_1})>0$ for all $t$ (either the expectation is $0$ or positive, and if it is $0$ then $X_1^2{e}^{t{X}_1}$ is $0$ almost everywhere, which contradicts ).

Either $P(X_1\le 0)=1$ or . In the first case,

$${\varphi }^{\prime }(t)={\int }_{\mathrm{\Omega }}{X}_1{e}^{t{X}_1}𝑑P={\int }_{X_1\le 0}{X}_1{e}^{t{X}_1}𝑑P\le 0,$$

so, using the dominated convergence theorem,

$$\rho =\underset{t\in ℝ}{inf}\varphi (t)=\underset{t\to \mathrm{\infty }}{lim}\varphi (t)={\int }_{X_1\le 0}\left(\underset{t\to \mathrm{\infty }}{lim}{e}^{t{X}_1}\right)dP={\int }_{X_1=0}dP=P(X_1=0).$$

Then

$$P(S_n\ge 0)=P(X_1=0,\mathrm{\dots },X_n=0)=P(X_1=0)\mathrm{\cdots }P(X_n=0)={\rho }^n.$$

That is, as $a=0$,

$$P(S_n\ge a)=e^{-n{\mathrm{\Lambda }}^{*}(a)},$$

and the claim is immediate in this case.

In the second case, . As ${\varphi }^{\prime \prime }(t)>0$ for all $t$, there is some $\tau \in ℝ$ at which for all $t\ne \tau$ (namely, a unique global minimum). Thus,

$$\varphi (\tau )=\rho ,{\varphi }^{\prime }(\tau )=0.$$

And , which with the above yields $\tau >0$. Because $\tau >0$, $S_n(\omega )\ge 0$ if and only if $\tau S_n(\omega )\ge 0$ if and only if $e^{\tau S_n(\omega )}\ge 1$. Applying Chebyshev’s inequality, and because $X_n$ are independent,

$$P(S_n\ge 0)=P(e^{\tau S_n}\ge 1)\le E(e^{\tau S_n})=E(e^{\tau X_1})\mathrm{\cdots }E(e^{\tau X_n})=\varphi {(\tau )}^n={\rho }^n,$$

thus $\log P(S_n\ge 0)\le n\log \rho$ and then

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\frac{1}{n}\log P(S_n\ge 0)\le \underset{n\to \mathrm{\infty }}{lim\; sup}\log \rho =\log \rho =\log e^{-{\mathrm{\Lambda }}^{*}(0)}=-{\mathrm{\Lambda }}^{*}(0).$$

To prove the claim, it now suffices to prove that, in the case ,

$$\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{1}{n}\log P(S_n\ge 0)\ge \log \rho .$$ (1)

Let $\mu =X_1{}_{*}P$, and let

$$d\nu (x)=\frac{e^{\tau x}}{\rho }d\mu (x).$$

$\nu$ is a Borel probability measure: it is apparent that it is a Borel measure, and

$$\nu (ℝ)={\int }_{ℝ}𝑑\nu (x)={\int }_{ℝ}\frac{e^{\tau x}}{\rho }𝑑\mu (x)=\frac{1}{\rho }{\int }_{ℝ}{e}^{\tau x}𝑑\mu (x)=\frac{\varphi (\tau )}{\rho }=1.$$

There are independent identically distributed random variables $Y_n$, $n\ge 1$, each with $Y_n{}_{*}Q=\nu$. Define

$$\psi (t)=E(e^{t{Y}_1})={\int }_{ℝ}{e}^{tx}𝑑\nu (x)={\int }_{ℝ}{e}^{tx}\frac{e^{\tau x}}{\rho }𝑑\mu (x)=\frac{1}{\rho }{\int }_{ℝ}{e}^{(t+\tau )x}𝑑\mu (x)=\frac{\varphi (t+\tau )}{\rho },$$

the moment generating function of $Y_1$. As ${\varphi }^{\prime }(\tau )=0$,

$$E(Y_1)={\psi }^{\prime }(0)=\frac{{\varphi }^{\prime }(\tau )}{\rho }=0.$$

As $\rho >0$ and ${\varphi }^{\prime \prime }(t)>0$ for all $t$,

$$\mathrm{Var}(Y_1)=E(Y_1^2)={\psi }^{\prime \prime }(0)=\frac{{\varphi }^{\prime \prime }(\tau )}{\rho }\in (0,\mathrm{\infty }).$$

For $T_n={\sum }_{k=1}^n{Y}_k$, using that the $X_n$ are independent and that the $Y_n$ are independent,

$P(S_n\ge 0)$ $={\displaystyle {\int }_{x_1+\mathrm{\cdots }+x_n\ge 0}}d(S_n{}_{*}P)(x)$

$={\displaystyle {\int }_{x_1+\mathrm{\cdots }+x_n\ge 0}}𝑑\mu (x_1)\mathrm{\cdots }𝑑\mu (x_n)$

$={\displaystyle {\int }_{x_1+\mathrm{\cdots }+x_n\ge 0}}\left({\displaystyle \frac{\rho }{e^{\tau x_1}}}d\nu (x_1)\right)\mathrm{\cdots }\left({\displaystyle \frac{\rho }{e^{\tau x_n}}}d\nu (x_n)\right)$

$={\rho }^n{\displaystyle {\int }_{x_1+\mathrm{\cdots }+x_n\ge 0}}{e}^{-\tau (x_1+\mathrm{\cdots }+x_n)}d(T_n{}_{*}Q).$

But

${\displaystyle {\int }_{x_1+\mathrm{\cdots }+x_n\ge 0}}{e}^{-\tau (x_1+\mathrm{\cdots }+x_n)}d(T_n{}_{*}Q)$ $={\displaystyle {\int }_{T_n\ge 0}}{e}^{-\tau T_n}𝑑Q$

$=E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n}),$

hence

$$P(S_n\ge 0)={\rho }^{n}E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n}).$$

Thus, (1) is equivalent to

$$\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{1}{n}\log \left({\rho }^{n}E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n})\right)\ge \log \rho ,$$

so, to prove the claim it suffices to prove that

$$\underset{n\to \mathrm{\infty }}{lim\; inf}\frac{1}{n}\log \left(E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n})\right)\ge 0.$$

For any $c>0$,

$\log \left(E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n})\right)$ $\ge \log E\left(1_{\{0\le T_n\le c\sqrt{n}\}}\cdot e^{-\tau T_n}\right)$

$\ge \log (e^{-\tau c\sqrt{n}}\cdot Q(0\le T_n\le c\sqrt{n}))$

$=-\tau c\sqrt{n}+\log Q({\displaystyle \frac{T_n}{\sqrt{n}}}\in [0,c]).$

Because the $Y_n$ are independent identically distributed $L^2$ random variables with mean $0$ and variance ${\sigma }^2=\mathrm{Var}(Y_1)=\frac{{\varphi }^{\prime \prime }(\tau )}{\rho }$, the central limit theorem tells us that as $n\to \mathrm{\infty }$,

$$Q(\frac{T_n}{\sqrt{n}}\in [0,c])\to {\gamma }_{0,{\sigma }^2}([0,c]),$$

where ${\gamma }_{a,{\sigma }^2}$ is the Gaussian measure, whose density with respect to Lebesgue measure on $ℝ$ is

$$p(t,a,{\sigma }^2)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{{(t-a)}^2}{2{\sigma }^2}}.$$

Thus, because for $c>0$ we have ${\gamma }_{0,{\sigma }^2}([0,c])>0$,

$\underset{n\to \mathrm{\infty }}{lim\; inf}{\displaystyle \frac{1}{n}}\log \left(E(1_{\{T_n\ge 0\}}\cdot e^{-\tau T_n})\right)$ $\ge \underset{n\to \mathrm{\infty }}{lim\; inf}({\displaystyle \frac{-\tau c}{\sqrt{n}}}+{\displaystyle \frac{1}{n}}\log Q({\displaystyle \frac{T_n}{\sqrt{n}}}\in [0,c]))$

$=\underset{n\to \mathrm{\infty }}{lim}-{\displaystyle \frac{\tau c}{\sqrt{n}}}+\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{1}{n}}\log Q({\displaystyle \frac{T_n}{\sqrt{n}}}\in [0,c])$

$=\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \frac{1}{n}}\log {\gamma }_{0,{\sigma }^2}([0,c])$

$=0,$

which completes the proof. ∎

For example, say that $X_n$ are independent identically distributed random variables with $X_1{}_{*}P={\gamma }_{0,1}$. We calculate that the cumulant generating function $\mathrm{\Lambda }(t)=\log E(e^{t{X}_1})$ is

$\mathrm{\Lambda }(t)$ $=\log \left({\displaystyle {\int }_{ℝ}}{e}^{tx}𝑑{\gamma }_{0,1}(x)\right)$

$=\log \left({\displaystyle {\int }_{ℝ}}{e}^{tx}{\displaystyle \frac{e^{-\frac{x^2}{2}}}{\sqrt{2\pi }}}𝑑x\right)$

$=\log \left({\displaystyle {\int }_{ℝ}}{\displaystyle \frac{e^{-\frac{1}{2}{(x-t)}^2}}{\sqrt{2\pi }}}{e}^{\frac{t^2}{2}}𝑑x\right)$

$=\log e^{t^2}2$

$={\displaystyle \frac{t^2}{2}},$

thus for all $t$. Then

$${\mathrm{\Lambda }}^{*}(x)=\underset{t\in ℝ}{sup}(tx-\mathrm{\Lambda }(t))=\underset{t\in ℝ}{sup}\left(tx-\frac{t^2}{2}\right)=\frac{x^2}{2}.$$

Now applying Cramér’s theorem we get that for $a>E(X_1)=0$, for $S_n={\sum }_{k=1}^n{X}_k$ we have

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log P(S_n\ge an)=-\frac{a^2}{2}.$$

Another example: If $X_n$ are independent identically distributed random variables with the Rademacher distribution:

$$X_n{}_{*}P=\frac{1}{2}{\delta }_{-1}+\frac{1}{2}{\delta }_1.$$

Then

$$E(e^{t{X}_1})={\int }_{ℝ}{e}^{tx}d\left(\frac{1}{2}{\delta }_{-1}+\frac{1}{2}{\delta }_1\right)(x)=\frac{1}{2}{e}^{-t}+\frac{1}{2}{e}^t=\cosh t,$$

so the cumulant generating function of $X_1$ is

$$\mathrm{\Lambda }(t)=\log \cosh t,$$

and indeed for all $t\in ℝ$. Then, as $\frac{d}{dt}(tx-\log \cosh t)=x-\tanh t$,

$${\mathrm{\Lambda }}^{*}(x)=\underset{t\in ℝ}{sup}\left(tx-\log \cosh t\right)=\mathrm{arctanh}x\cdot x-\log \cosh \mathrm{arctanh}x.$$

For $x\in (-1,1)$,

$$\mathrm{arctanh}x=\frac{1}{2}\log \frac{1+x}{1-x}.$$

Then

$$\cosh \mathrm{arctanh}x=\frac{1}{2}\left(e^{\mathrm{arctanh}x}+e^{-\mathrm{arctanh}x}\right)=\frac{1}{2}\sqrt{\frac{1+x}{1-x}}+\frac{1}{2}\sqrt{\frac{1-x}{1+x}}=\frac{1}{\sqrt{1-x^2}}.$$

With these identities,

${\mathrm{\Lambda }}^{*}(t)$ $={\displaystyle \frac{x}{2}}\log {\displaystyle \frac{1+x}{1-x}}+{\displaystyle \frac{1}{2}}\log (1-x^2)$

$={\displaystyle \frac{x}{2}}\log (1+x)-{\displaystyle \frac{x}{2}}\log (1-x)+{\displaystyle \frac{1}{2}}\log (1+x)+{\displaystyle \frac{1}{2}}\log (1-x)$

$={\displaystyle \frac{1+x}{2}}\log (1+x)+{\displaystyle \frac{1-x}{2}}\log (1-x).$

With $S_n={\sum }_{k=1}^n{X}_k$, applying Cramér’s theorem, we get that for any $a>E(X_1)=0$,

$$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log P(S_n\ge an)=-\frac{1+x}{2}\log (1+x)-\frac{1-x}{2}\log (1-x).$$

For a Borel probability measure $\mu$ on $ℝ$, we define its Laplace transform $\check{\mu }:ℝ\to (0,\mathrm{\infty }]$ by

$$\check{\mu }(t)={\int }_{ℝ}{e}^{ty}𝑑\mu (y).$$

Suppose that and let $M_1={\int }_{ℝ}y𝑑\mu (y)$, the first moment of $\mu$. For any $t$ the function $x\mapsto e^{tx}$ is convex, so by Jensen’s inequality,

$$e^{t{M}_1}\le {\int }_{ℝ}{e}^{ty}𝑑\mu (y)=\check{\mu }(t).$$

Thus for all $t\in ℝ$,

$$t{M}_1-\log \check{\mu }(t)\le 0.$$

For a Borel probability measure $\mu$ with finite first moment, we define its Cramér transform $I_{\mu }:ℝ\to [0,\mathrm{\infty }]$ by

$$I_{\mu }(x)=\underset{t\in ℝ}{sup}(tx-\log \check{\mu }(t)).$$

For $t=0$, $tx-\log \check{\mu }(t)=-\log \check{\mu }(0)=-\log (1)=0$, which shows that indeed $0\le I_{\mu }(x)\le \mathrm{\infty }$ for all $x\in ℝ$. But $t{M}_1-\log \check{\mu }(t)\le 0$ for all $t$ yields

$$I_{\mu }(M_1)=0.$$