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)$?**



Properties of a finite random walk
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. 


