# Finding the exact solution of a difference equation

We know a particle moves two units to the right with probability $p$, or $1$ unit to the left with probability $q$, hence $(p+q=1)$.

$$q_k=P\left(S_n=0\mid S_0=k\right)$$

We are asked to find the general and exact solution.

I found the difference equation: $q_k=qq_\left(k-1\right)+pq_\left(k+2\right)$

And then I found the general solution:$$q_k=A\cdot 1+B\left(\frac{-1}{2}-\sqrt{\frac14+\frac qp}\right)^k+C\left(\frac{-1}{2}+\sqrt{\frac14+\frac qp}\right)^k$$

However, to find the exact solution, I don't know how to solve for $A, B$ & $C$. I tried assuming $q_0=1$, which lets $A+B+C=1$, but that's not enough. Any hint would be greatly appreciated!

-
Take two more values of $q_n$ to get three equations for the three parameters. – GEdgar Feb 14 '13 at 14:06
@GEdgar Not sure this can help. – Did Feb 14 '13 at 15:36

The first problem is your definition of $(q_k)_k$. One should consider $q_k=\mathbb P(\text{hits}\ 0\mid S_0=k)$, hence $q_0=1$. The second thing to realize is that there are several regimes.

Assume first that $2p\gt q$. The drift of the random walk is positive hence $S_n\to+\infty$ almost surely. Furthermore, since the only negative jump is $-1$, to hit $0$ starting from $k\geqslant1$, one must hit $k-1$ starting from $k$, then hit $k-1$ starting from $k$, and so on until one hits $0$ starting from $1$. In other words $q_k=q_1^k$ for every $k\geqslant0$.

Now the usual one-step recursion yields $q_k=pq_{k+2}+qq_{k-1}$ for every $k\geqslant1$, hence $q_1^k=pq_1^{k+2}+qq_1^{k-1}$, that is, $q_1$ solves $$r=pr^3+q.$$ The roots are $\{-s,t,1\}$ with $0\lt t\lt1\lt s$, namely, $$s=\tfrac12+\tfrac12\sqrt{1+4q/p},\qquad t=-\tfrac12+\tfrac12\sqrt{1+4q/p}.$$ Since $q_k\to0$ when $k\to+\infty$, the only option which is non absurd is that $q_1=t$, hence $q_k=t^k$ for every $k\geqslant0$.

To compute $q_k$ for $k\leqslant-1$, one adopts the same strategy since $q_k=pq_{k+2}+qq_{k-1}$ for every $k\leqslant-1$, where one already knows $q_0=1$ and $q_1=t$. A priori, $(q_k)_{k\leqslant0}$ is a linear combination of the sequences with general terms $1$, $(-s)^k$ and $t^k$. Since $q_k$ should stay bounded when $k\to-\infty$, there is no term in $t^k$, hence there exists some $A$ in $[0,1]$ such that, for every $k\leqslant0$, $q_k=1-A+A(-s)^k$. The recursion for $k=-1$ implies that $1-A+A(-s)^{-1}=pt+q(1-A+A(-s)^{-2})$, which yields $A$, hence $(q_k)_{k\leqslant-1}$.

The case $2p=q$ is singular since the random walk is recurrent hence $q_k=1$ for every $k$.

When $2p\lt q$, $S_n\to-\infty$ almost surely hence $q_k=1$ for every $k\geqslant1$. For $k\leqslant-1$, now $q_k\to0$ when $k\to-\infty$ hence the roots $1$ and $t$ do not contribute, that is, $q_k=(-s)^k$ for every $k\leqslant0$.

-
Thank you so much! I forgot to mention $k\ge0$, but your explanations really helped me understand. – Fantim Feb 15 '13 at 4:37