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|$$
- Is there a closed-form formula for the distribution of $Y_N$ and $M_N$?
- If not, what is $E(Y_N)$ and $E(M_N)$?
- If the answer in (1) is negative, how fast can we compute $\Pr(Y_N = y)$?