On $\mathbb{Z}$ I have a random walk $S$ with the probability of an increment of size $-1,0,1$ at each time step is $a,b,a$ respectively, with $a+b+a=1$. That is, I stay put with probability $b$, otherwise I hop left or right with equal probabilities. Does the probability $p(n,k)$ that started at $n \geq 0$ I will reach $0$ in exactly $k \geq 0$ steps have a nice formula?

A quick one step analysis shows the system is determined by the equations $$ p(0,0) = 1, $$ $$ p(n,k) = 0, \qquad k<n, $$ $$ p(n,k) = ap(n-1,k-1) + b p(n,k-1) + ap(n+1,k-1). $$

I don't remember exactly how to solve these recurrence equations, though it is clear that given $a,b$ computing $p(n,k)$ could be done in a finite number of recursive calls. A reference I could cite with the answer would be appreciated as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.