Probability – Finding the Exact Stationary Distribution for a Biased Random Walk on a Bounded Interval

markov chainsprobability

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

Best Answer

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