Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 124 / 2 / c / Solution

For the simple symmetric random walk, independence and the Rademacher distribution give the moment-generating functionThe function ${\theta }^2/2-\log \cosh \theta$ is even; for $\theta \ge 0$ its derivative is $\theta -\tanh \theta \ge 0$, since the derivative of $\tanh \theta$ is at most one and $\tanh 0=0$. Here $\cosh$ and $\tanh$ are the hyperbolic cosine and hyperbolic tangent. Hence the exponential-moment estimate is

The supplied exponential maximal bound for a symmetric random walk now gives $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le \exp (-\theta t\sqrt{n}+n{\theta }^2/2)$. For $t>0$, choose $\theta =t/\sqrt{n}$; for $t=0$, use the elementary bound by one. Thus

Fix $a>1$, choose $0<\delta <a^2-1$, and set $n_m=\lfloor (1+\delta {)}^m\rfloor$. For large $m$ these form an increasing sequence. Apply the preceding exponential maximal bound for a symmetric random walk at $n_{m+1}$ with threshold $a\sqrt{2n_m\log \log n_m}$. The resulting probability is at mostWe have $n_m/n_{m+1}\to (1+\delta {)}^{-1}$ and $\log \log n_m=\log m+O(1)$. Choose $b$ strictly between $1$ and $a^2/(1+\delta )$; the displayed probabilities are $O(m^{-b})$. By the Borel-Cantelli first lemma, almost surely, eventually ${\max }_{k\le n_{m+1}}{S}_k<a\sqrt{2n_m\log \log n_m}$. For every $n_m\le n\le n_{m+1}$, monotonicity of $n\log \log n$ for large $n$ therefore givesIntersect the probability-one events for $a=1+1/r$ to obtain the upper law of the iterated logarithm: