Imagine we have a biased random walk on an interval $[0, L]$, where the probability of taking a $+1$ step is $p$ and the probability of taking a $-1$ step is $(1-p)$. At the reflecting boundary $0$, the walker will take a $+1$ step with probability $p$ or remain in place, and at the reflecting boundary $L$, the walker will take a $-1$ step with probability $(1-p)$ or remain in place.

My guess is that having some $+1$ step probability of $p$ and $-1$ step probability of $q$, where $(p + q) < 1$, would make no difference, that what matters is the ratio $\frac{p}{q}$.

Is it possible to find an exact stationary distribution for this Markov process by solving the following recurrence relations?:

$P(X=0) = (1-p)P(X=0) + (1-p)P(X=1)$

$P(X=L) = pP(X=L-1) + p(X=L)$

$P(X=n) = pP(X=n-1) + (1-p)P(X=n+1)$

Where: $0 < n < L$

If anyone is able to find a solution, please do let me know what techniques you used! I haven't made much traction here myself, and I'd actually like to learn how to solve these sorts of constant coefficient recurrence relation problems.

For the user Henry's exact solution for the above problem without the reflecting boundary at $L$:

$\pi(X=n) = (\frac{p}{q})^n(1-\frac{p}{q})$

Please see: Probability distribution for the position of a biased random walker on the positive integers

  • 1
    $\begingroup$ a) You can get displayed equations that look nicer and are easier to read, especially with fractions, by using double dollar signs. b) It's unusual in mathmatics to use an asterisk for multiplication. If you need to disambiguate multiplication, you can use the centred dot generated by \cdot, but usually, including here, that's not necessary and multiplication is implied clearly enough. c) I think you're missing an $n$-th power in the stationary distribution. d) Frequently changing the question right after posting it decreases the motivation to answer it; better to proofread before posting. $\endgroup$ – joriki Dec 20 '12 at 8:21
  • $\begingroup$ @joriki Good points. Sorry for too much proofreading after positing the question, but things should be in good shape now. $\endgroup$ – PlacidLake Dec 20 '12 at 8:24

For several questions now, the OP could use the fact that, to approach solutions $(x_n)_n$ of recursion relations $x_n=ax_{n+1}+bx_{n-1}$ plus some boundary conditions, one first solves the characteristic equation $$ r=ar^2+b. $$ Then each root $r$ yields a solution $x_n=r^n$ hence, assuming there are two distinct roots $r$ and $s$, each $(x_n)_n$ defined by $x_n=Ar^n+Bs^n$ solves the recursion. Then one uses the boundary conditions to compute $A$ and $B$.

In the case at hand, $x_n=P(X=n)$, $a=1-p$, and $b=p$, hence $$ r=\frac{p}{1-p},\qquad s=1, $$ that is, $x_n=Ar^n+B$ for every $0\leqslant n\leqslant L$. The boundary conditions written in the post are equivalent to $x_1=rx_0$ and $x_L=rx_{L-1}$, and both these conditions are equivalent to $B=0$.

Finally, $\sum\limits_{n=0}^Lx_n=1$ hence $A\sum\limits_{n=0}^Lr^n=1$, and $$ \mathbb P(X=n)=r^n\frac{1-r}{1-r^{L+1}}. $$


Hint: write $P(X=j) = p P(X=j-1) + q P(X=j+1)$ as $p u_j = q u_{j+1}$ where $u_j = P(X=j) - P(X=j-1)$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.