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!


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.


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.} $$

  • 1
    $\begingroup$ An interesting question is whether it is also true that for the symmetric random walk in the dimensions 2 and 3 the maximum expected distance the drunkard is away from its starting point during the first $n$ steps is the same as the expected distance the drunkard is away from its starting point after $n$ steps. If I am correct, the famous MIT probabilist G.C. Rota once addressed the question in an unpublished(?) manuscript $\endgroup$ – user164118 Apr 19 '17 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.