Find transition matrix for Markov chain (hopscotch 'path')

[buckaroobill]

i was studying for a daily quiz that we have at the beginning of every class and i came across this problem. i was wondering how to do it in case i get asked a similar one.

Suppose we have a 3 by 3 grid (used for perhaps playing some weird kind of hopscotch.) 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.

I was wondering:
1) how one would find the transition matrix for the Markov chain.

and

2) if the child starts off in the upper right hand square, what is the probability that he will end up in the center square three seconds later?

 

[galactus]

By adjacent I suppose you mean having a side in common. That is, assume square 2 is occupied, then the child can move to 1, 3, or 5. Not 4 and 6 also?.

If you set up the transition matrix if the child is at the third square.

\(\displaystyle \L\\\left[\begin{array}{ccccccccc|c}1&2&3&4&5&6&7&8&9\\0&1/3&0&1/3&0&0&0&0&0&1\\1/2&0&1/2&0&1/4&0&0&0&0&2\\0&1/3&0&0&0&1/3&0&0&0&3\\1/2&0&0&0&1/4&0&1/2&0&0&4\\0&1/3&0&1/3&0&1/3&0&1/3&0&5\\0&0&1/2&0&1/4&0&0&0&1/2&6\\0&0&0&1/3&0&0&0&1/3&0&7\\0&0&0&0&1/4&0&1/2&0&1/2&8\\0&0&0&0&0&1/3&0&1/3&0&9\end{array}\right]\cdot\begin{bmatrix}0\\0\\1\\0\\0\\0\\0\\0\\0\end{bmatrix}=\begin{bmatrix}0\\1/2\\0\\0\\0\\1/2\\0\\0\\0\end{bmatrix}\)

That's the first. Can you do the second and third?.

 

[soroban]

Re: Problem

Hello, buckaroobill!

Suppose we have a 3 by 3 grid.
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.

1) How one would find the transition matrix for the Markov chain.

I will assume that "adjacent" includes diagonally adjacent.
The grid looks like this:

    * - * - * - *
    | 1 | 2 | 3 |
    * - * - * - *
    | 4 | 5 | 6 |
    * - * - * - *
    | 7 | 8 | 9 |
    * - * - * - *

If the boy is on square #1, he can jump to squares #2, 4, or 5
. . with probability \(\displaystyle \frac{1}{3}\) each.

If he is on square #2, he can jump to squares #1, 3, 4, 5, 6
. . with probability \(\displaystyle \frac{1}{5}\) each.

If he is on square #5, he can jump to squares #1, 2, 3, 4, 6, 7, 8, 9
. . with probability \(\displaystyle \frac{1}{8}\) each.


We will have a 9-by-9 transition matrix.

\(\displaystyle \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}\)

2) If the child starts off in the upper right hand square,
what is the probability that he will end up in the center square three seconds later?

Calculate \(\displaystyle A^3\).

Then look at the entry at \(\displaystyle a_{35}\) (third row, fifth column).

 

[buckaroobill]

Re: Problem

thank you so much!

i get it now!

 

[buckaroobill]

Re: Problem

Eh sorry, one more question. How is the steady state vector for the transition matrix found?