# Properties of a finite random walk

Consider the simplest random walk - $X_0 = 0$ and from there on (i.i.d), $X_i=X_{i-1}+1$ with probability $p$ or $X_{i-1}-1$ otherwise.

Let $Y_N$ be the highest point $X$ have reached on the first $N$ steps and similarly, let $M_N$ be the furthest point, that is: $$Y_N=\max_{i\leq N} X_i\\ M_N=\max_{i\leq N}|X_i|$$

1. Is there a closed-form formula for the distribution of $Y_N$ and $M_N$?
2. If not, what is $E(Y_N)$ and $E(M_N)$?
3. If the answer in (1) is negative, how fast can we compute $\Pr(Y_N = y)$?
• I don't know about exact formula for $Y_N$ (except as ugly sums - I would be surprised if there is a nice closed form formula) but a good approximation for large $N$ is for example $2P(S_N>x)\leq P(Y_N>x)\leq 2P(S_N>x)+P(S_N=x)$ (of course, $x\geq 0$ and $S_n$ is your random walk). For $P(M_N<x)$ you can write an equation (for small and intermediate values of $N$ it is not hard to solve numerically). For large values of $N$ good approximations can be obtained by Donsker's invariance principle. – ofer zeitouni Dec 27 '14 at 9:07

We have

$P(Y_{n} = r) = {n \choose [\frac{n-r}{2}]}2^{-n}$.

(for a proof see Theorem 2.4 from RANDOM WALK IN RANDOM AND NON-RANDOM ENVIRONMENTS of Pal Revesz, or Feller Vol I).

A simple expression for $E(Y_{n})$ may also be found in the latter reference.

• Of course these results address the problem in the symmetric case. – Achilleas May 25 '15 at 4:36
• It's Thm 1 in III.7 of Feller I. For $p\not={1 \over 2}$ replace $2^{-n}$ with $p^kq^{n-k}$ , $k:=\lceil{n+r+1 \over 2}\rceil$. – esg Jul 24 '15 at 14:57
• Furthermore, regarding the second part of the question, the asymptotic distribution for $M_{N}/\sqrt{N}$, as $N \rightarrow \infty$ is Theorem I in the free access paper: Erdös, P., & Kac, M. (1946). On certain limit theorems of the theory of probability. Bulletin of the American Mathematical Society, 52(4), 292-302. I do not know the exact distribution for fixed $N$ for this however. – Achilleas Jul 25 '15 at 19:28
• Apologies, my statement for $p\not={1/2}$ above is false. (The derivation can be done as in Feller, but the sum doesn't simplify). It seems that only in the symmetric case the distribution of $Y_n$ has a simple expression. – esg Jul 27 '15 at 17:42
• But note that in the asymmetric case $$\mathbb{P}(Y_n\geq r)=\mathbb{P}(X_n\geq r)+({p \over q})^r \mathbb{P}(X_n\leq -(r+1))$$ for $r\geq 0$. Thus for the cdf you essentially only need the cdf of the binomial distribution (incomplete Beta function). – esg Aug 23 '15 at 19:23