Distribution of $\max_{n \ge 0} S_n$, random walk Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the left is $q = 1-p$. Let $S_n$ be such a random walk started at $0$ for some $p \in (0, {1\over2})$. Let $M = \max_{n \ge 0} S_n$. What is the distribution of $M$?
 A: As Lucia pointed out in a comment, by solving the hitting probability recursions for the Markov chain, you get that the distribution of the maximum is geometric; for $k=0,1,2,\dots$,
$$
\mathbb{P}(M=k)=\left(\frac{p}{1-p}\right)^k\left(1-\frac{p}{1-p}\right),
$$
or equivalently
$$
\mathbb{P}(M\geq k)=\left(\frac{p}{1-p}\right)^k.
$$
There's actually a simple intuition for why the answer must be geometric. The only way to reach site $k>0$ is by passing through sites $1,2,\dots,k-1$ on the way. So to hit $k$ starting from $0$, you first have to hit $1$ starting from $0$, then you have to hit $2$ starting from $1$, then $3$ starting from $2$, .... , and finally $k$ starting from $k-1$. Now use the Markov property (formally the strong Markov property) and the fact that the process is translation invariant (so that the probability of hitting $j+1$ starting from $j$ doesn't depend on $j$), to get that the probability of hitting $k$ from $0$ is just the $k$th power of the probability of hitting $1$ from $0$. 
A: More generally, for any upward skip–free random walk on the integers (such that $P(X>1)=0$), the distribution of $M$ is geometric (when finite): $P(M=n)= (1-\theta) \cdot \theta^n$, where $\theta$ is the unique solution in $(0,1)$ of $1=E[\theta^{-X}]$.
The distribution of $M$ can also be calculated inductively for downward skip free random walk (such that $P(X<-1)=0$).
See e.g. Corollary 5.5 and Corollary 5.6 in Asmussen, S. (2003). Applied probability and queues, 2nd ed. New York: Springer, and http://people.bu.edu/pekoz/skipfree.pdf for other interesting information concerning skip free random walks.
