Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 201 / 3

If ${\xi }_k=S_k-S_{k-1}$, thenThe centered increments ${\xi }_k-\mu$ are independent of the past and have mean zero, sois a martingale.

The increment variance isso independence givesLinear interpolation makes the supremum of the absolute centered process occur at an integer time. The Doob L2 maximal inequality therefore gives

The moment-generating function of one increment isThus withindependence givesThis is the exponential martingale of a biased simple random walk.

LetOn $A$, one has $T\le n$, $S_T\ge \mu T+\epsilon n$, and convexity of $\psi$ gives $\psi (\theta )-\mu \theta \ge 0$. Hence for $\theta >0$,The optional stopping theorem applies because $T$ is bounded, so $\mathbb{E}{Z}_T=1$. Therefore

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 functionand the union bound give