Solving a system of equations to find expected residence time of a Markov Chain

Question

I have been told that in order to calculate the expected residence time for a set of states I can use the following approach:

1. Construct a Markov Chain with index i,j being the probability of transition from state i to state j.
2. Transpose the matrix, so that each column contains the inbound probabilities for that state.
3. Invert the diagonal so that a value p becomes (1-p).
4. Add a row at the bottom, containing 1's
5. Construct a coefficient vector with 0's and the last element 1
6. Solve it. The resulting vector should contain the expected residence time for the various states

Let me give an example:

I have the initial Markov Chain:

  0.25  ;  0.25  ;  0.25  ; 0.25
  0.00  ;  0.50  ;  0.50  ; 0.00
  0.33  ;  0.33  ;  0.33  ; 0.00
  0.00  ;  0.00  ;  0.50  ; 0.50 

After step 1-3 it looks like this:

  0.75  ;  0.00  ;  0.33  ;  0.00
  0.25  ;  0.50  ;  0.33  ;  0.00
  0.25  ;  0.50  ;  0.67  ;  0.50
  0.25  ;  0.00  ;  0.00  ;  0.50

I add the last line:

  0.75  ;  0.00  ;  0.33  ;  0.00
  0.25  ;  0.50  ;  0.33  ;  0.00
  0.25  ;  0.50  ;  0.67  ;  0.50
  0.25  ;  0.00  ;  0.00  ;  0.50
  1.00  ;  1.00  ;  1.00  ;  1.00

The coefficient will be the following vector:

   0    ;    0   ;   0    ;   0   ;   1

The added line of 1's should enforce, that the solution sums to 1. However, my solution is the set:

  {0.42; 0.84; -0.79; 0.32}

Which sums to 0.79, so clearly something is wrong. I also note, that the expected residence time of state 3 is negative, which in my mind should not be possible.

I have it implemented in Java and I use Commons.Math to handle the matrix calculations. I have tried the various algorithms described in the documentation, but I get the same result.

I have also tried to substitute one of the rows with the line of 1's in order to make the matrix square. When I do that, I get the following set of solutions:

  {0.79; 0.79; -1.79; 1.2}

Even though the probabilities sum to 1 they must still be wrong as they should be in the range 0..1 AND sum to 1.

Is this an entirely wrong approach to the problem? Where am I off? Unfortunately I am not very mathematical, but I hope I have given enough information for you to see the problem.

Answer 1

I found the answer:

Let all probabilities p but the diagonal be -p in step 3:

0.75  ;  -0.00  ;  -0.33  ;  -0.00
-0.25  ;  0.50  ;  -0.33  ;  -0.00
-0.25  ;  -0.50  ;  0.67  ;  -0.50
-0.25  ;  -0.00  ;  -0.00  ;  0.50