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!
Best Answer
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.