# Computing the steady state probability vector of a random walk on $\{0, 1, \dots, n\}$

Suppose we have a random walk on $\{0, \dots, n\}$ with transition probabilities

$$P(x, x + 1) = p \\ P(x, x - 1) = 1 - p$$

for $1 \le x \le n -1$, $P(0, 1) = a$, $P(0, 0) = 1 - a$, $P(n, n - 1) = b$, and $P(n, n) = 1- b$

I need to compute the steady state vector $\pi$ for this random walk. First I wrote down the five difference equations

$$\pi(x + 1)(1-p) + \pi(x - 1)p = \pi(x) \ \ \ \ \ \ \ 2 \le x \le n -2$$

$$\pi(0)(1 - a) + \pi(1)(1 - p) = \pi(0)$$

$$\pi(0)a + \pi(2)(1 - p) = \pi(1)$$

$$\pi(n-1)p + \pi(n)(1 - b) = \pi(n)$$

$$\pi(n - 2)p + \pi(n)b = \pi(n-1)$$

and we also have the requirement

$$\sum_{k=0}^n \pi(x) = 1$$

The general solution to the first equation is

$$\pi(x) = k_1 + k_2\bigg(\frac{p}{p-1}\bigg)^x , \ \ \, p \ne 1/2$$

$$\pi(x) = k_1 + k_2x, \ \ \ \ p = 1/2$$

I am unsure what do to next. Any help is appreciated.

• Have you worked out any explicit examples for small $n$, including $n=1$ and $n=2$? Drawing graphs of this process can be helpful, too.
– whuber
Oct 2 '13 at 19:59
• I've tried looking at graphs, but it didn't really help me find the steady state vector. Oct 2 '13 at 20:16

You can solve your second equation to give $\pi(1)=\frac{a}{1-p} \pi(0)$, then your third to give $\pi(2)=\frac{ap}{(1-p)^2} \pi(0)$, then your first to give $\pi(x)=\frac{a}{p}\left(\frac{p}{1-p}\right)^x \pi(0)$ for $0 \lt x \lt n$, and finally your fourth to give $\pi(n)=\frac{p}{b} \pi(n-1) = \frac{a}{b}\left(\frac{p}{1-p}\right)^{n-1} \pi(0)$. Your fifth equation is not independent of the others.
You can now add up the terms, noting the geometric progression in the middle, and set the sum equal to $1$ to solve for $\pi(0)$ and thus find all the values of $\pi(x)$.
• Minor question, what would happen if both $a$ and $b$ are $0$? The vectors $(0, 0 \dots, 0 1)$ and $(1, 0 \dots, 0)$ both satisfy this. Oct 3 '13 at 1:54
• @user: If $b=0$ then my method fails because of division by $0$, and in practice $n$ becomes an absorbing state. If both $a=0$ and $b=0$ then you have two absorbing states, at $0$ and $n$, and so there is no unique steady state vector. Oct 3 '13 at 7:08
1. Start by solving the case $n=3$ to compute explicitly $\pi_3$ and try to guess what will be the general form of $\pi_n$ for larger $n$. If the guessing step is not trivial, you should try to solve the case $n=4$ and understand how to pass from $\pi_3$ to $\pi_4$.
2. Prove by induction on $n$ that $\pi_n$ verifies $\pi_n \mathbf{P}_n = \pi_n$, where $\mathbf{P}_n$ is the transition matrix of your process.
3. Prove the ergodicity of your Markov chain in order to claim that $\pi_n$ is the unique steady state distribution.