6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Oct 2 '13 at 19:59
  • $\begingroup$ I've tried looking at graphs, but it didn't really help me find the steady state vector. $\endgroup$
    – user30991
    Oct 2 '13 at 20:16
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user30991
    Oct 3 '13 at 1:54
  • $\begingroup$ @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. $\endgroup$
    – Henry
    Oct 3 '13 at 7:08
1
$\begingroup$

Here are the generic steps to solve these problems. The first computations may be difficult or time consuming, so do not hesitate to use online symbolic equation solvers like wolframalpha to gain time.

  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.
$\endgroup$

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.