Markov chain

• Jan 5th 2011, 11:12 AM
terminator
Markov chain
Each year at River High School, the parents sit on a committee.

Curently:
30% are in the Sports committee
20% are on the arts committee
50% are on the Graduation committee

At the end of the school year, the parents can change committees
Here are the changes that took place last June

10% of the parents from each committee stayed on their committee
15% of the members on the Sports committee joined the Graduation committee
5% of the members on the Arts committee joined the sports committee
30% of the members of the Graduation committee joined the Arts committee

a) create a transition matrix to show the changes

0.10 0.75 0.15
0.05 0.10 0.85
0.60 0.30 0.10

b) If the trend continues, determine the percentage of parents on each committee once it stabilizes. Povide proof of stabilization

• Jan 5th 2011, 11:52 AM
dwsmith
1st 10% stay in their respected committees.

$\displaystyle
\begin{bmatrix}
\mbox{S} & \mbox{A} & \mbox{G} & \mbox{Next Yr}\\
.10 & & & \mbox{S}\\
& .10 & & \mbox{A}\\
& & .10 & \mbox{G}
\end{bmatrix}$

2nd 15% of S joined G; Therefore, 85% went to A from S.

$\displaystyle
\begin{bmatrix}
\mbox{S} & \mbox{A} & \mbox{G} & \mbox{Next Yr}\\
.10 & & & \mbox{S}\\
.75 & .10 & & \mbox{A}\\
.15 & & .10 & \mbox{G}
\end{bmatrix}$

3rd 5% of A joined S which means 85% from A went to G.

$\displaystyle
\begin{bmatrix}
\mbox{S} & \mbox{A} & \mbox{G} & \mbox{Next Yr}\\
.10 & .05 & & \mbox{S}\\
.75 & .10 & & \mbox{A}\\
.15 & .85 & .10 & \mbox{G}
\end{bmatrix}$

Last 30% of G go to A. Hence, 60% go to S from G. Now we have our Stochastic Matrix.

$\displaystyle
A=\begin{bmatrix}
\mbox{S} & \mbox{A} & \mbox{G} & \mbox{Next Yr}\\
.10 & .05 & .6 & \mbox{S}\\
.75 & .10 & .3 & \mbox{A}\\
.15 & .85 & .10 & \mbox{G}
\end{bmatrix}$

Initial Vector:
$\displaystyle
\mathbf{x}_0=\begin{bmatrix}
.3\\
.2\\
.5\end{bmatrix}$

Now, you need to diagonalize the stochastic matrix.

$A=XDX^{-1}$

$\displaystyle\lim_{n\to\infty}(XD^nX^{-1}\mathbf{x}_0)$
• Jan 5th 2011, 12:09 PM
Random Variable
Let $\pi_{i} \ ( i=0,1,2)$ be the limiting probability of a parent being on committe $i$.

$\pi_{0} = 0.1 \pi_{0} + 0.05 \pi_{1} + 0.6 \pi_{2}$

$\pi_{1} = 0.75 \pi_{0} + 0.1 \pi_{1} + 0.3 \pi_{2}$

$\pi_{2} = 0.15 \pi_{0} + 0.85 \pi_{1} + 0.1 \pi_{2}$

$\pi_{0} + \pi_{1} +\pi_{2} = 1$

Solve the system. It's not as bad as it looks.

EDIT: The initial state shouldn't matter.
• Jan 5th 2011, 12:10 PM
Opalg
Quote:

Originally Posted by terminator
Each year at River High School, the parents sit on a committee.

Curently:
30% are in the Sports committee
20% are on the arts committee
50% are on the Graduation committee

At the end of the school year, the parents can change committees
Here are the changes that took place last June

10% of the parents from each committee stayed on their committee
15% of the members on the Sports committee joined the Graduation committee
5% of the members on the Arts committee joined the sports committee
30% of the members of the Graduation committee joined the Arts committee

a) create a transition matrix to show the changes

0.10 0.75 0.15
0.05 0.10 0.85
0.60 0.30 0.10

b) If the trend continues, determine the percentage of parents on each committee once it stabilizes. Povide proof of stabilization

As dwsmith points out, you have found the transpose of the correct answer to part (a). [In a transition matrix, the elements in each column should have sum 1. But in your matrix, the rows add up to 1.]

But you don't need to diagonalise the matrix. In fact, if the matrix is $A$, and the steady state vector is $\mathbf{x}$, then $A\mathbf{x} = \mathbf{x}$. (That's more or less the definition of the steady state: it doesn't change when you multiply it by the matrix.) In other words, $\mathbf{x}$ is the eigenvector of $A$ corresponding to the eigenvalue 1.

So you just have to solve the equations $(I-A)\mathbf{x} = \mathbf{0}$, normalising the result so that the coordinates of $\mathbf{x}$ have sum 1.

Edit. ... and that is exactly what Random Variable has just suggested.
• Jan 5th 2011, 12:47 PM
Random Variable
What if there were a state that was not directly or indirectly accessible from another state? How would you deal with that?
• Jan 6th 2011, 12:14 AM
Opalg
Quote:

Originally Posted by Random Variable
What if there were a state that was not directly or indirectly accessible from another state? How would you deal with that?

The method only applies to a regular stochastic process. If the process is not regular then you would somehow need to restrict attention to the invariant subspace of the state space containing the given initial state.

the interesting thing about a regular stochastic process is that the steady state is independent of the initial state.