Stochastic Matrices

Date: 03/17/98 at 09:46:14
From: Wayland
Subject: eigenvectors

Hi:

In an earlier answer you responded to a student's question about
eigenvectors. In stochastic hydrology there is an equation that
is used:

     p(t+1) = p(t)T 

where p(t+1) and p(t) are nx1 probability row vectors at two different 
time periods t and t+1, and T is a called a transitional probability 
matrix (nxn) whose rows sum to one. As t approaches infinity, p(t+1) 
approaches p(t). According to Eigenvector theory, the eigenvalue of 
this equation should then be one and solving for T should yield the 
identity matrix. It is true that the equation is satisfied for the 
identity matrix, but for other T matrices it converges to a unique 
vector that depends on the matrix, but not on p(0). I have tried to 
solve for this vector but when I put in the conditions that the 
probabilities sum to one, the problem is overspecified.

Please help me with this dilemma.

Thanks

Wayland

Date: 03/17/98 at 15:36:07
From: Doctor Anthony
Subject: Re: eigenvectors

I have worked through an example and hope it answers your queries on 
stochastic matrices.

Below is an example of the distribution of trade between depots.

The service specialist of Metrobug Heating and Air Conditioning
Company make their calls with a fleet of radio-dispatched service
trucks. Established procedure is that when a call requesting service 
is received by the office, the dispatcher sends the next available 
truck to respond to the call. One of the service specialists keeps 
records of his service calls, and his data are summarize in the table
below. Formulate this situation. Find the transition diagram and the
one-step transition matrix.

---------------------------------------------------------------------
District of         District of                 Percent of 
Current Call        Next Call                   Calls
---------------------------------------------------------------------
  East               East                       50
                     Central                    40
                     West                       10
---------------------------------------------------------------------
  Central            East                       10    
                     Central                    60
                     West                       30
---------------------------------------------------------------------
  West               East                       30
                     Central                    60
                     West                       10
---------------------------------------------------------------------

It is more usual to write the transition matrix with columns adding to 
1 rather than rows in the way you have shown it. This allows you to 
operate on a vector representing the present state as a product M.x  
where x is the vector of present position. Example below.

             East   Central   West
       
        East [.5       .1      .3][1]    [.5]
     Central |.4       .6      .6||0| =  |.4|
        West [.1       .3      .1][0]    [.1]         

If we take the stationary vector, that is we find the vector that does 
not change any more, we have:

            M[a]    [a]
             |b| =  |b|
             [c]    [c]

we get the vector  [ 9/38]
                   |21/38]
                   [ 8/38]

This vector is found by solving the three equations below for a, b, c.

   a(.5-1)  +  .1b     +  .3c    = 0
   .4a      +  b(.6-1) +  .6c    = 0
   .1a      +  .3b     + c(.1-1) = 0 

we get  a = 9/38,   b = 21/38,   c = 8/38 

This is in fact a quick way to find M^(infinity) as you will see 
below. This will always work for a stochastic matrix but is obviously 
not a general method for powers of matrices.

So, over the long term, East gets 9/38 of the trade, Central gets 
21/38 of the trade and West gets 8/38 of the trade.

If you raised M to an infinite power you will find that it settles 
down to the matrix shown below, and ANY starting vector will end up 
with the vector shown on the right hand side.

     [9/38   9/38    9/38][1/2]    [ 9/38]
     |21/38  21/38  21/38||1/4| =  |21/38]
     [8/38    8/38   8/38][1/4]    [ 8/38]

This shows that after an infinite application of the matrix every 
starting vector will end up with the same distribution. The columns of  
M^(infinity) are all the same and are given by the vector:

      [a]
      |b|
      [c]

-Doctor Anthony,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/