Stochastic Matrix Computation

A stochastic matrix is a square matrix of non-negative entries such that each column adds up to 1. Such matrices appear in Markov chain models and have a wide range of applications in engineering, science, biology, economics, and internet search engines, such as Google’s pagerank matrix (which has size in the billions.) Given such a matrix P whose entries are strictly positive, then there is a theorem that guarantees the existence of a steady-state equilibrium vector x such that x = Px. Moreover, this vector can be computed recursively starting from an arbitrary initial vector x0 by the recursion:

xk+1 = Pxk, k= 0, 1, 2, . . . (1)

and xk converges to x as k→∞, regardless of the initial vector x0. The solution of Eq. (1) can be given explicitly as the matrix operation:

xk = Pkx0, k= 0, 1, 2, . . . (2)

Consider the following example:

P   [0.5 0.2 0.3

     0.3 0.7 0.3

     0.2 0.1 0.4]

x0 =[0.1
     0.3
     0.6]

a. Denote the equilibrium vector by

x =[x1
    x2
    x3]

To make it unique, we will assume that its entries add up to 1, that is, x1 +x2 +x3 = 1. Set up three equations in the three unknowns {x1, x2, x3}, cast them in matrix form, and solve them. Verify the equation x = Px for the resulting solution.

That is my assignment, and in short, from what I understand, I have to come up with three equations using x1 x2 and x3 and solve them.

Unfortunately, I have no idea what this means. Where am I supposed to get these equations from? Do I plug in the example numbers into the x=Px equation?

Any help whatsoever will be appreciated.

[bym]

I think it should read "set up _four_ equations in 3 unknowns". you can use any equations as long as the columns add up to 1

[bym]

do you have the symbolic toolbox?

Answer 1

[bym]

try using the matrix given to you

Px =

    0.5000    0.2000    0.3000
    0.3000    0.7000    0.3000
    0.2000    0.1000    0.4000

the columns represent x1, x2, x3. Then figure out how to write x1+x2+x3 = 1 and augment P with it and solve for the unknowns