Let $X_1, X_2,\dots$ be i.i.d random variables with $\mathbb P(X_1=1)=\mathbb P(X_1=-2)=\frac 1 2.$ I need to consider $S_n = \sum\limits_{i=1}^n X_i$ with $S_n = 0$.
What is $\mathbb P\left(\sup\limits_{n\geqslant 0} S_n \geqslant k\right)$ for $k\in\mathbb N$?
I know that $S_n$ is a supermartingale because
\begin{align*}
\mathbb E[S_{n+1}|\mathscr{F}_n] &= S_n + \frac 1 2 \cdot 1 – \frac 1 2\cdot 2\\
&= S_n-\frac 12\\
&\leqslant S_n.
\end{align*}
How can I use Doob's martingale inequality then? Furthermore I know that $$\mathbb P\left(\sup\limits_{n\geqslant 0} S_n \geqslant k\right) = \mathbb P\left(\inf\{n\in\mathbb N|S_n = k\} < \infty\right).$$
Is it useful to consider $X_i$ with $\mathbb P(X_1=1)= \frac 1 3, \mathbb P(X_1=-1)=\frac 2 3$ or $-S_n$? This looks somewhat related.
Best Answer
Let $P_k=P(\sup_n S_n\ge k)$, for each $k\ge 0$. On the one hand, it is pretty easy to prove that $$ \begin{align} P_k&=\frac12P_{k-1}+\frac12P_{k+2},\qquad (k\ge 1)\tag1 \end{align} $$ On the other hand, you can prove that $$ P_k = (P_1)^k,\qquad (k\ge 0)\tag2 $$ This is because you can only move upward in increments of one, so if you reach $k$, you must hit $\ell$ for each $\ell\in \{1,\dots,k-1\}$. Therefore, reaching $k$ starting from $0$ is equivalent to...
Reaching $1$ starting from $0$, then
reaching $2$ starting from $1$, then
reachinng $3$ starting from $2$, then
$\vdots$
reaching $k$ starting from $(k-1)$.
Each bullet point has a probability of $P_1$, since they are all equivalent processes to starting at $0$ and eventually moving to $1$.
Combining $(1)$ and $(2)$, you get $$ P_1=\frac12 +\frac12P_1^3 $$ The possible solutions to $x=\frac12(1+x^3)$ are $x\in \{1,\frac{-1\pm \sqrt5}{2}\}$. The negative solution can obviously be ignored. Furthermore, you can prove that $P_1=1$ is impossible. If $P_1=1$, this would mean the process will move from $0\to 1$ with probability $1$, and then $1\to 2$ with probability $1$, then $2\to 3$, and so on, eventually reaching arbitrarily high values. However, this would contradict the fact that $S_n\to-\infty$ almost surely, which is implied by SLLN.
Therefore, we deduce that $P_1=\frac12(-1+\sqrt 5)$, the inverse of the golden ratio.