= Solution
For the <simple symmetric random walk>, <independence> and the <Rademacher distribution> give the <moment-generating function>
$$
\mathbb E e^{\theta S_n}=\prod_{i=1}^n\mathbb E e^{\theta X_i}=\left(\frac{e^\theta+e^{-\theta}}2\right)^n=(\cosh\theta)^n.
$$
The function $\theta^2/2-\log\cosh\theta$ is even; for $\theta\ge0$ its derivative is $\theta-\tanh\theta\ge0$, since the derivative of $\tanh\theta$ is at most one and $\tanh0=0$. Here $\cosh$ and $\tanh$ are the <hyperbolic cosine> and <hyperbolic tangent>. Hence \b[the exponential-moment estimate] is
$$
\boxed{\mathbb E e^{\theta S_n}\le e^{n\theta^2/2}\quad(\theta\in\mathbb R).}
$$
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
$$
\boxed{\mathbb P(\max_{k\le n}S_k\ge t\sqrt n)\le e^{-t^2/2}\quad(t\ge0).}
$$
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 most
$$
\exp\left(-a^2\frac{n_m}{n_{m+1}}\log\log n_m\right).
$$
We 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 gives
$$
\frac{S_n}{\sqrt{2n\log\log n}}\le a.
$$
Intersect the probability-one events for $a=1+1/r$ to obtain \b[the <upper law of the iterated logarithm>]:
$$
\boxed{\mathbb P\left(\limsup_{n\to\infty}\frac{S_n}{\sqrt{2n\log\log n}}\le1\right)=1.}
$$
Back to article page
