Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

A random walker moves at each step two units to the right or one unit to the left, with corresponding probabilities $p$ and $q = 1-p$. The allowed range is $[-A, B]$ and the starting position is $0$.

Is the recursion formula $f[z]= p f[z-2] + q f[z+1]$ valid?

I'm looking for the three boundary conditions in order to solve the formula.

$f(z)=P(S(τ)=B|S(0)=z)$ where $τ=\min \{n≥0:S(n) = B \text{ or } S(n) = −A\}$ where $S(n)$ is the position of the random walker after $n$ steps.

share|cite|improve this question
"The allowed range is $[−A,B]$" What happens when he is at position $B-1$? Does he jumps with probability $p$ to $B$ ? – leonbloy Aug 14 '12 at 21:17
@leonbloy Good point. My solution actually uses this assumption. – Byron Schmuland Aug 14 '12 at 21:38
@ByronSchmuland: yes, it sounds reasonable (and your solution seems right to me , +1) – leonbloy Aug 14 '12 at 23:18
up vote 3 down vote accepted

For convenience, add the state $B+1$ to your system and define $$\tau=\min(n≥0:S(n) \in\{-A,B,B+1\}).$$

The function $f(z)=P(S(\tau)\geq B\,|\,S(0)=z)$ satisfies $f(B+1)=1$, $f(B)=1$, $f(-A)=0$ and will be harmonic otherwise, i.e., $f(z)= p f(z+2) + q f(z-1)$ for $-A<z<B$.

From the theory of linear difference equations, such a harmonic function is given by $$ f(z)=a+b\rho_1^z+c\rho_2^z$$ where $$\rho_1=-{1\over2}+{\sqrt{1+4(q/p)}\over2} \quad\mbox{ and }\quad\rho_2=-{1\over2}-{\sqrt{1+4(q/p)}\over2}.$$ Choose the constants $a,b,c$ so that $f$ satisfies the boundary conditions at $-A$, $B$, and $B+1$. This $f$ solves your problem.

share|cite|improve this answer
Thank you, Byron. – Goofy Aug 15 '12 at 3:49

You should write down the definition of $f[z]$. It would seem you want $f(z,t)$ to be the probability that the walker is at position $z$ at time $t$. Then your starting conditions are $f(0,0)=1, f(z,0)=0 \text{ for } z \ne 0$ The recurrence in the middle then is $f(z,t)=pf(z-2,t-1)+qf(z+1,t-1)$. You then have to worry about the effects of the ends, which will change the recurrence near them.

share|cite|improve this answer

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.