Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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$.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.