Distribution of the Maximum of a (infinite) Random Walk Let $S_0 = 0$ and define $S_n = \sum^n_{i = 1} X_i$ such that
\begin{align*}
\mathbb P(X_i = 1) &= p \\
\mathbb P(X_i = -1) &= 1 - p = q
\end{align*}
for $p < \frac{1}{2}$. Find the distribution of $Y = \max \{S_0, S_1, S_2, ...\}$.
My attempt at a solution: One known result (and a nice application of path counting/the reflection principle) is that if $Y_n = \max \{S_0, S_1, ..., S_n\}$ then
\begin{equation*}
\mathbb P(Y_n \geq r, S_n = b) =
\begin{cases}
 \mathbb P(S_n = b) & b \geq r \\
 \left(\frac{q}{p}\right)^{r - b} \mathbb P(S_n = 2r - b) & b < r
\end{cases}
\end{equation*}
and so, for $r \geq 1$, we find
\begin{align*}
\mathbb P(Y_n \geq r) &= \mathbb P(S_n \geq r) + \sum^{r - 1}_{b = -\infty} \left(\frac{q}{p}\right)^{r-b} \mathbb P(S_n = 2r - b) \\
&= \mathbb P(S_n = r) + \sum^\infty_{c = r + 1} \left[1 + \left(\frac{q}{p}\right)^{c - r}\right] \mathbb P(S_n = c)
\end{align*}
However, this was for the maximum over a finite random walk $S_n = \sum^n_{i = 1} X_i$. In the present case we're interested in the maximum over all $n \in \mathbb N$, say $S_\infty$, and it's not immediately obvious to me how to solve such a case.
Thank you for any input!
 A: 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}$.
A: 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.
