Distribution of the Maximum of a (infinite) Random Walk

Define a function $f(n):= \big( \frac{1-p}{p} \big)^n$. Then $f$ is a harmonic function for this random walk. In other words, $f(n) = pf(n+1)+(1-p)f(n-1)$. Therefore $Y_n:=f(S_n)$ is a martingale.

For the rest of the problem, fix an integer $N \geq 0$. We will use the martingale property to compute the probability $P(\sup_n S_n \geq N)$.

Define $T:= \inf\{n \geq 0: S_n = N\}$. Then the stopped martingale $Y^T_n:=Y_{T\wedge n}$ is a bounded martingale (thus uniformly integrable).

Now there are two possibilities: if $S_n \to -\infty$ and $S_n < N$ for all $n$, then we see that $Y_{T\wedge n} \to 0$ as $n \to \infty$. On the other hand $Y_{T \wedge n} \to \big(\frac{1-p}{p} \big)^N$ if $S_n \geq N$ for some $n$. Therefore, by the optional stopping theorem we see that $$1 = E[Y^T_{\infty}] = E\bigg[ \bigg(\frac{1-p}{p} \bigg)^N \cdot 1_{\{T<\infty\}} \bigg] + E[0 \cdot 1_{\{T=\infty\}}] = \bigg(\frac{1-p}{p}\bigg)^NP(T<\infty) $$Thus $P(\sup_n S_n \geq N) =P(T<\infty)= \big( \frac{1-p}{p} \big)^{-N}$.

It is possible to find the distribution of $M := \max_{n\ge 0} S_n$ without using any involved techniques.

Upon reaching a level $x\ge 0$ for the first time, the random walk has two choices

• reach the level $x+1$ sometime;
• drift to $-\infty$.

(Thanks to LLN, it will make the second choice eventually.) By the strong Markov property and homogeneity, these choices are independent for $x=0,1,\dots,M$, and the probability of the first choice is the same and equal to $$ p' = P(\text{reaching 1 before $-\infty$ from 0}).$$ Therefore, $M$ is one less a geometrically distributed random variable with parameter $1-p'$, i.e. $$ P(M\ge n) = (p')^n,\ n\ge0, $$ so it remains to identify $p'$. The simplest way is to use a recursion, which is an obvious consequence of the total probability formula, conditioning on the first step: $$ p' = p + (1-p)(p')^2. $$ One of solutions of the latter quadratic equation is $1$ (as it was already mentioned, it is prohibited by LLN), so it is easy to find by Vieta's rule that $$ p' = \frac{p}{1-p}, $$ which confirms @Shalop's answer.