Consider the random walk $S_n=\sum_{k=1}^n X_k$ where $(X_n)$ is an i.i.d. sequence of variables with distribution $P(X_n=1)=P(X_n=-2)=\frac{1}{2}$. I am trying to evaluate the probability $P(E)$ where $E$ is the event $E=\lbrace \exists n, S_n \geq 1 \rbrace$.
If we define the stopping time $\tau={\sf min}(n\ | \ S_n \geq 1)$ (or $\infty$ if the sums never reach $1$), it is easy to see that $P(\tau=k)$ is nonzero iff $k$ is congruent to $1$ modulo $3$. I have computed the first values of $P(\tau=k)$ and $s_k=\sum_{j=1}^k P(\tau=j)$ :
$$
\begin{array}{|c|c|c|c|}
\hline
k & 1 & 4 & 7 & 10 & 13 & 16 \\
\hline
P(\tau=k) & \frac{1}{2} & \frac{1}{16} & \frac{3}{2^7} & \frac{3}{2^8} & \frac{55}{2^{13}} & \frac{273}{2^{16}} \\
\hline
s_k & 0.5 & 0.56 & 0.59 & 0.6 & 0.6 & 0.61 \\
\hline
\end{array}
$$
Question. Is it true that $P(E)\leq 0.7$ ?
My thoughts : one can introduce $f(k)=P(\lbrace \exists n, S_n \geq k)$. Then for $k\geq 1$ one has the linear recurrence $f(k)=\frac{f(k-1)+f(k+2)}{2}$, with $f(0)=1$ and $f(1)=P(E)$. The characteristic polynomial associated to this recurrence is $X^3-2X+1=(X-1)(X^2+X-1)$, and its root are $1$ and $\frac{-1\pm\sqrt{5}}{2}$. So there are constants $c_1,c_2,c_3$ such that
$f(k)=c_1+c_2\big(\frac{-1+\sqrt{5}}{2}\big)^k+c_3\big(\frac{-1-\sqrt{5}}{2}\big)^k$. Because of $0\leq f(k)\leq 1$ and $\big|\frac{1+\sqrt{5}}{2}\big| \gt 1$ it follows that $c_3=0$. I am stuck after this however because the only relation I can see is $f(0)=1$, which leaves one degree of freedom.
Best Answer
Define $\tau=\inf\{n:S_n\geq 1\}$. Then $P(E)=P(\tau <\infty)$. We seek a positive $a \neq 1$ s.t. $a^{S_n}$ is a $\mathscr{F}_n^X$-martingale where $\mathscr{F}_n^X=\sigma(X_k,k\leq n)$. We have $$E[a^{S_n-S_{n-1}}|\mathscr{F}_{n-1}]=\frac{1}{2}(a+a^{-2})=1\implies a=\frac{1+\sqrt{5}}{2}>1$$ By using optional stopping we obtain (note $S_0=0$) $$1=E[a^{S_{\tau \wedge n}}]=E[a^{S_\tau}\mathbf{1}_{\{\tau< n\}}]+E[a^{S_n}\mathbf{1}_{\{\tau\geq n\}}]\geq a P(\tau < n)+E[a^{S_n}\mathbf{1}_{\{\tau\geq n\}}]$$ and by dominated convergence (note $S_n\to -\infty$ $P$-a.s.) $$P(\tau<\infty)\leq a^{-1}\approx 0.62$$