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

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

share|cite|improve this question
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. – joriki Dec 20 '12 at 8:21
@joriki Good points. Sorry for too much proofreading after positing the question, but things should be in good shape now. – PlacidLake Dec 20 '12 at 8:24
up vote 1 down vote accepted

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

share|cite|improve this answer

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

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.