Maximum of *Absolute Value* of a Random Walk

Question

Suppose that $S_{n}$ is a simple random walk started from $S_{0}=0$. Denote $M_{n}^{*}$ to be the maximum absolute value of the walk in the first $n$ steps, i.e., $M_{n}^{*}=\max_{k\leq n}\left|S_{k}\right|$.

What is the expected value of $M_{n}^{*}$? Or perhaps a bit easier, asymptotically, what is $\lim_{n\to\infty}M_{n}^{*}/\sqrt{n}$?

This question relates to https://mathoverflow.net/questions/150740/expected-maximum-distance-of-a-random-walk, but I need to obtain the value of the multiplicative constant. Thanks!

Answer 1

For a Brownian motion $(S_t)_{t\ge 0}$, the corresponding process $(M^*_t)_{t\ge 0}$ and $y>0$, $$\mathbb{P}[M_t^* > y] = \frac{4}{\pi}\sum_{m=0}^\infty\frac{(-1)^m}{2m+1}\left[1 - e^{-(2m+1)^2t\pi^2 / (8y^2)}\right]$$ and $$\mathbb{E}[M_t^*]=\sqrt{\frac{t\pi}{2}}.$$ Thanks to Sangchul Lee for computing the integral. This may be proved by considering the martingale $(\mathbb{P}[M_t^* > y | \mathcal{F}_r])_{r<t}$ and relating it to a solution of the heat equation with Dirichlet boundary conditions [see, for example, equation 25 of these notes]. I'd be happy to write this up if anyone's interested. I don't know whether a similar method works for the discrete-time random walk.

Answer 2

Partial answer to the first question: Using the reflection principle, I obtained

$$ \Bbb{P}(M_n^* \geq k) = \sum_{m=0}^{\infty} (-1)^m \left\{ \Bbb{P}((2m+1)k \leq |S_n|) + \Bbb{P}((2m+1)k < |S_n|) \right\}. $$

(Since $|S_n| \leq n$, this is in fact a finite sum for $k \geq 1$ and there is no convergence issue.) Now summing both sides for $k = 1, 2, \cdots$, this gives

$$ \Bbb{E}[M_n^{*}] = \sum_{m=0}^{\infty} (-1)^m \Bbb{E} \bigg[ \left\lfloor \frac{|S_n|}{2m+1} \right\rfloor + \left\lceil \frac{|S_n|}{2m+1} \right\rceil - \mathbf{1}_{\{S_n \neq 0 \}} \bigg]. $$

For me, this seems to suggest that we might be able to get

$$ \frac{\Bbb{E}[M_n^*]}{\sqrt{n}} \to \sum_{m=0}^{\infty} \frac{(-1)^m}{2m+1} \cdot 2\Bbb{E}[\mathcal{N}(0,1)] = \sqrt{\frac{\pi}{2}}, $$

which matches the analogous result for the Wiener process proved by @Ben Derrett.

(As an alternative idea, we may possibly utilize Skorokhod embedding to realize the SRW using the Wiener process evaluated at certain stopping times $\tau_n$ and then control the deviation between $\tau_n$'s to carry over Ben Derrett's result to the SRW case. Note that similar idea is used to prove the law of iterated logarithms for normalized ranodm walks. But I haven't pursued this direction further.)

---

Answer to the second question: For the pointwise estimate, we can rely on the law of iterated logarithm (LIL). Indeed, let

$$M_n^{+} = \max\{S_0, \cdots, S_n\}, \qquad M_n^{-} = \max\{-S_0, \cdots, -S_n\}. $$

Then we have

$$ \limsup_{n\to\infty} \frac{M^{\pm}_n}{\sqrt{2n\log\log n}} = 1 \qquad \Bbb{P}\text{-a.s.} $$

Indeed, this follows from both LIL and the following lemma:

Lemma. Suppose that $(a_n)$ and $(b_n)$ are sequences of real numbers such that $b_n > 0$ and $b_n \uparrow \infty$. Then the following identity holds:

$$ \limsup_{n\to\infty} \frac{\max_{1\leq k \leq n} a_k}{b_n} = 0 \vee \limsup_{n\to\infty} \frac{a_n}{b_n}. $$

Since $M_n^* = \max\{M_n^+, M_n^-\}$, the same bound is true for $M_n^*$:

$$ \limsup_{n\to\infty} \frac{M^{*}_n}{\sqrt{2n\log\log n}} = 1 \qquad \Bbb{P}\text{-a.s.} $$