Math Is Fun Forum

virtualinsanity

Member

Registered: 2007-03-11

Posts: 38

Markov chain problem

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 (that includes diagonally as well).

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

and

2) what happens in the long term? if the markov chain does not have a steady-state vector, then explain what happens instead.

I'll show you my work so far:

I numbered the grid 1-9 like so:

1 2 3
4 5 6
7 8 9

Each number is in an individual box, but since I don't know how to draw boxes on this thing, let's imagine that they are!

I concluded that from square 1, the hopper can go to 2, 4, and 5. Thus, the probability of going to each of those from 1 is 1/3.

From square 2, the hopper can go to 1, 3, 4, 5, and 6. Therefore, the probability of going to each of those from 2 is 1/5.

And so on. As you can see, I've already gotten the probabilities. But how do I represent them in a transition matrix?

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Markov chain problem

I'm new to this subject, but I here's something off google that seems to imply that
you need a 9 by 9 matrix, with a diagonal from upper left to lower-right of zeros and
percentages in the other squares, such that a column or row all adds up to 100%.
Here is a quote:
The transition matrix describes a system that changes over discrete time increments, in which the value of any variable in a given time period is the sum of fixed percentages of the value of the variables in the previous time period. The sum of fractions along the column of the transition matrix is equal to one (See equations bellow). The diagonal line of the transition matrix needs not to be filled in since it models the percentage of unchangeable cells.

---

igloo myrtilles fourmis