1
$\begingroup$

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.

$\endgroup$

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.