4
$\begingroup$

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.

  • 0
    @ByronSchmuland: yes, it sounds reasonable (and your solution seems right to me , +1)2012-08-14

2 Answers 2

3

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.

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.

0

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.