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!
Best Answer
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}$.