= Solution
Let
$$
T=\inf\{k\leq n:S_k-\mu k\geq\varepsilon n\}\wedge n.
$$
On $A$, one has $T\leq n$, $S_T\geq\mu T+\varepsilon n$, and convexity of $\psi$ gives $\psi(\theta)-\mu\theta\geq0$. Hence for $\theta>0$,
$$
Z_T
=e^{\theta(S_T-\mu T)-(\psi(\theta)-\mu\theta)T}
\geq e^{(\theta(\mu+\varepsilon)-\psi(\theta))n}.
$$
The <optional stopping theorem> applies because $T$ is bounded, so $\mathbb EZ_T=1$. Therefore
$$
\boxed{\mathbb P(A)\leq e^{-(\theta(\mu+\varepsilon)-\psi(\theta))n}}.
$$
Optimize over $\theta>0$ for the upper deviation and apply the same argument with $\theta<0$ to the lower deviation. Since the supremum of the linearly interpolated centered walk is attained at grid points, the <Legendre transform of a cumulant-generating function>
$$
\psi^*(x)=\sup_{\theta\in\mathbb R}(\theta x-\psi(\theta))
$$
and the <union bound> give
$$
\boxed{
\mathbb P\left(\sup_{0\leq t\leq1}|S_t^{(n)}-\mu t|\geq\varepsilon\right)
\leq e^{-n\psi^*(\mu+\varepsilon)}+e^{-n\psi^*(\mu-\varepsilon)}.}
$$
Back to article page
