# Markov chain

• Mar 13th 2007, 09:40 PM
buckaroobill
Markov chain
I have the following transition matrix for a Markov chain.

$\L A\;=\;\begin{pmatrix}0 \,&\, \frac{1}{3} \,&\, 0 \,&\, \frac{1}{3} \,&\, \frac{1}{3} \,&\, 0 \,&\, 0 \,&\, 0 \,&\, 0 \\
\frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & 0 & 0 \\
0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 \\

\frac{1}{5} & \frac{1}{5} & 0 & 0 & \frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & 0 \\
\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0 & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} \\
0 & \frac{1}{5} & \frac{1}{5} & 0 & \frac{1}{5} & 0 & 0 & \frac{1}{5} & \frac{1}{5} \\

0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\
0 & 0 & 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & \frac{1}{5} \\
0 & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0
\end{pmatrix}$
[/size]

This represents the problem:
A child is standing in a square on the grid (namely x).
Once time per second, he jumps to another square that is adjacent to x.

The grid looks like this:[/size]
Code:

    * - * - * - *     | 1 | 2 | 3 |     * - * - * - *     | 4 | 5 | 6 |     * - * - * - *     | 7 | 8 | 9 |     * - * - * - *
[size=14]

My question is, how do I find the steady state vector for the Markov chain?
• Mar 13th 2007, 11:21 PM
JakeD
Quote:

Originally Posted by buckaroobill
I have the following transition matrix for a Markov chain.

$\L A\;=\;\begin{pmatrix}0 \,&\, \frac{1}{3} \,&\, 0 \,&\, \frac{1}{3} \,&\, \frac{1}{3} \,&\, 0 \,&\, 0 \,&\, 0 \,&\, 0 \\
\frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & 0 & 0 \\
0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 \\

\frac{1}{5} & \frac{1}{5} & 0 & 0 & \frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & 0 \\
\frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0 & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} \\
0 & \frac{1}{5} & \frac{1}{5} & 0 & \frac{1}{5} & 0 & 0 & \frac{1}{5} & \frac{1}{5} \\

0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \\
0 & 0 & 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & \frac{1}{5} \\
0 & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0
\end{pmatrix}$
[/size]

This represents the problem:
A child is standing in a square on the grid (namely x).
Once time per second, he jumps to another square that is adjacent to x.

The grid looks like this:[/size]
Code:

    * - * - * - *     | 1 | 2 | 3 |     * - * - * - *     | 4 | 5 | 6 |     * - * - * - *     | 7 | 8 | 9 |     * - * - * - *
[size=14]

My question is, how do I find the steady state vector for the Markov chain?

Do a google on steady state vector markov chain and in the Wikipedia entry you'll find two ways to calculate it, as a limit and as an eigenvector.
• Mar 14th 2007, 12:51 AM
CaptainBlack
Quote:

Originally Posted by JakeD
Do a google on steady state vector markov chain and in the Wikipedia entry you'll find two ways to calculate it, as a limit and as an eigenvector.

Isn't that limit just another way of calculating that eigen vector?

(Rhetorical question I know the answer, and I know that you know the answer)

RonL
• Mar 14th 2007, 09:54 AM
JakeD
Quote:

Originally Posted by CaptainBlack
Isn't that limit just another way of calculating that eigen vector?

(Rhetorical question I know the answer, and I know that you know the answer)

RonL

I don't disagree, but ...

There are two ways of looking at this that are essentially mathematically equivalent.

1) A steady state is an eigenvector x from x = xP. The iterative method x(n+1) = x(n)P will converge to x if P is regular.

2) A steady state is the limit of x(n+1) = x(n)P. If P is regular, the limit exists and is an eigenvector x from x = xP.

The second way is what is presented in the Wikipedia page. I favor this way because the iteration can be implemented simply on a computer without introducing the machinery of eigenvectors.