# Boundary conditions on asymmetric random walk recursion formula

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.

-
"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

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.
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.