# Maximum of *Absolute Value* of a Random Walk

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

• 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 – user164118 Apr 19 '17 at 10:26