# Math Help - Markov chain

1. ## 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

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

3. 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.

4. 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.

5. What if there were a state that was not directly or indirectly accessible from another state? How would you deal with that?

6. 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.