Markov chain: finding a general solution

[Christopher T.]

1. The problem statement
Given a stochastic matrix P with states s_1...s_5:

<br /> P =<br /> \begin{pmatrix}<br /> 1 &amp; p_2 &amp; 0 &amp; 0 &amp; 0\\<br /> 0 &amp; 0 &amp; p_3 &amp; 0 &amp; 0\\<br /> 0 &amp; q_2 &amp; 0 &amp; p_4 &amp; 0\\<br /> 0 &amp; 0 &amp; q_3 &amp; 0 &amp; 0 \\<br /> 0 &amp; 0 &amp; 0 &amp; q_4 &amp; 1<br /> \end{pmatrix}<br />

and the matrix A (which is obviously related to P, but I can't see how... ):

<br /> A =<br /> \begin{pmatrix}<br /> 1 &amp; -q_2 &amp; 0 \\<br /> -p_3 &amp; 1 &amp; -q_3 \\<br /> 0 &amp; -p_4 &amp; 1<br /> \end{pmatrix}<br />

The question is how the vector y = (x_2,x_3, x_4) is a solution to the system Ay =b for a certain b that I am supposed to find.

Homework Equations

The relevant equations are:
<br /> x_j^K = 1<br />
for all closed states

<br /> x_j^K = \sum_{i=1}^n p_{ij }x_i^K<br />
for all non-closed states

The Attempt at a Solution

I started by expanding Ay:

<br /> Ay=<br /> \left(<br /> \begin{matrix}<br /> 1 &amp; -q_2 &amp; 0 \\<br /> -p_3 &amp; 1 &amp; -q_3 \\<br /> 0 &amp; -p_4 &amp; 1<br /> \end{matrix}<br /> \right)<br /> \left(<br /> \begin{matrix}<br /> x_2\\<br /> x_3\\<br /> x_4<br /> \end{matrix}<br /> \right)<br /> =<br /> \left(<br /> \begin{matrix}<br /> 1x_2 + -q_2x_3 \\<br /> -p_3x_2 + x_3 -q_3x_4 \\<br /> -p_4x_3 + x_4<br /> \end{matrix}<br /> \right)<br /> = b<br />

But that seems to get me nowhere. The question hints to using the formulas listed above, but I can't see how I can use them to find b.

I appreciate all help.

 

[Ray Vickson]

1. The problem statement
Given a stochastic matrix P with states s_1...s_5:

<br /> P =<br /> \begin{pmatrix}<br /> 1 &amp; p_2 &amp; 0 &amp; 0 &amp; 0\\<br /> 0 &amp; 0 &amp; p_3 &amp; 0 &amp; 0\\<br /> 0 &amp; q_2 &amp; 0 &amp; p_4 &amp; 0\\<br /> 0 &amp; 0 &amp; q_3 &amp; 0 &amp; 0 \\<br /> 0 &amp; 0 &amp; 0 &amp; q_4 &amp; 1<br /> \end{pmatrix}<br />

and the matrix A (which is obviously related to P, but I can't see how... ):

<br /> A =<br /> \begin{pmatrix}<br /> 1 &amp; -q_2 &amp; 0 \\<br /> -p_3 &amp; 1 &amp; -q_3 \\<br /> 0 &amp; -p_4 &amp; 1<br /> \end{pmatrix}<br />

The question is how the vector y = (x_2,x_3, x_4) is a solution to the system Ay =b for a certain b that I am supposed to find.

Homework Equations

The relevant equations are:
<br /> x_j^K = 1<br />
for all closed states

<br /> x_j^K = \sum_{i=1}^n p_{ij }x_i^K<br />
for all non-closed states

The Attempt at a Solution

I started by expanding Ay:

<br /> Ay=<br /> \left(<br /> \begin{matrix}<br /> 1 &amp; -q_2 &amp; 0 \\<br /> -p_3 &amp; 1 &amp; -q_3 \\<br /> 0 &amp; -p_4 &amp; 1<br /> \end{matrix}<br /> \right)<br /> \left(<br /> \begin{matrix}<br /> x_2\\<br /> x_3\\<br /> x_4<br /> \end{matrix}<br /> \right)<br /> =<br /> \left(<br /> \begin{matrix}<br /> 1x_2 + -q_2x_3 \\<br /> -p_3x_2 + x_3 -q_3x_4 \\<br /> -p_4x_3 + x_4<br /> \end{matrix}<br /> \right)<br /> = b<br />

But that seems to get me nowhere. The question hints to using the formulas listed above, but I can't see how I can use them to find b.

I appreciate all help.

Your question uses the exact opposite convention for $P$ used in all the books on my shelves and all the papers I have ever read on the subject: usually, in the English-speaking world, stochastic matrices have rows summing to 1, not the columns. I would love to replace your $P$ by its transpose, but that would create too much confusion; so I will write $P(i \to j)$ for the one-step transition probability from state i to state j. (In your convention, $p_{ij} = P(j \to i)$, but in my convention---by far the majority--- $p_{ij} = P(i \to j)$.) The clumsier notation avoids confusion.

Anyway, if $I$ is the $5 \times 5$ identity matrix, your matrix $A$ is the submatrix of $I - P$ consisting of rows 2--4 and columns 2--4, so it has to do with the equations (a): $x_i = \sum_{j \neq 1,5} P(i \to j) x_j + b_i, \; i = 2,3,4$, or maybe the equations (b): $X_j = \sum_{i \neq 1,4} X_i P( i \to j) + R_j, \; j = 2,3,4$.

First, note that states 1 and 5 are absorbing, and states {2,3,4} form an intercommunicating but transient class. That is, starting from state 2, 3 or 4, the process will eventually (i.e., with probability 1) be absorbed into state 1 or state 4. One way equations like (a) arise is in computing the absorption probability for state 1, starting from states 2, 3 or 4. If we let $f_i =$ probability of absorption in state 1, starting from state $i$, then these can be found from the standard equations
f_i = P(i \to 1) + \sum_{j =2}^4 P(i \to j) f_j, \; i = 2,3,4 If you re-write these as $f_i - \sum P(i \to j) f_j = \text{something}$ you essentially involve the matrix $A$ you were given.

Other than that, I have no idea what the questioner wants.

 

[Christopher T.]

Your question uses the exact opposite convention for $P$ used in all the books on my shelves and all the papers I have ever read on the subject: usually, in the English-speaking world, stochastic matrices have rows summing to 1, not the columns. I would love to replace your $P$ by its transpose, but that would create too much confusion; so I will write $P(i \to j)$ for the one-step transition probability from state i to state j. (In your convention, $p_{ij} = P(j \to i)$, but in my convention---by far the majority--- $p_{ij} = P(i \to j)$.) The clumsier notation avoids confusion.

Anyway, if $I$ is the $5 \times 5$ identity matrix, your matrix $A$ is the submatrix of $I - P$ consisting of rows 2--4 and columns 2--4, so it has to do with the equations (a): $x_i = \sum_{j \neq 1,5} P(i \to j) x_j + b_i, \; i = 2,3,4$, or maybe the equations (b): $X_j = \sum_{i \neq 1,4} X_i P( i \to j) + R_j, \; j = 2,3,4$.

First, note that states 1 and 5 are absorbing, and states {2,3,4} form an intercommunicating but transient class. That is, starting from state 2, 3 or 4, the process will eventually (i.e., with probability 1) be absorbed into state 1 or state 4. One way equations like (a) arise is in computing the absorption probability for state 1, starting from states 2, 3 or 4. If we let $f_i =$ probability of absorption in state 1, starting from state $i$, then these can be found from the standard equations
f_i = P(i \to 1) + \sum_{j =2}^4 P(i \to j) f_j, \; i = 2,3,4 If you re-write these as $f_i - \sum P(i \to j) f_j = \text{something}$ you essentially involve the matrix $A$ you were given.

Other than that, I have no idea what the questioner wants.

Thank you, this gave me something to work on.