So let's look at another example for 
Markov Chains here. This is sometimes

known as the "Mouse in a Maze" model and 
we will see why in just a second. I just

want to recall from the previous slide
that I was showing you how to find a

steady state vector for a stochastic
matrix by solving the corresponding system

of linear equations. So what is this
Mouse in a Maze model all about then?

Well, I have depicted on the left, crudely
sorry about that, but a mouse placed in a

maze. We have made the maze very simple
and in the maze there are three rooms

labeled one two three, accordingly, and 
the mouse is kind of free to roam about

the maze, coming to and fro between the 
various rooms. So you can think of

the mouse as choice to transition from one
room to the next, as a probabilistic event

and in this fashion, then we are going to
model, in a way a really primitive almost,

Artificial Intelligence here, AI system
based on those probabilities.

So, let's go ahead and draw a directed
graph that explicitly shows these

transitional probabilities and then from 
there we can construct our stochastic

matrix. Right, so I have drawn the
directed graph and the corresponding

stochastic matrix for this example. You'll
notice a few things, for one I haven't

allowed the mouse to remain stationary
from step to step, it always moves and you

can see that in our directed graph, for
instance if it is in room one currently,

if its probability is one half it moves to
room three and similarly a probability of

one half it moves to room two. So, zero
probability that it remains still and it's

true for all the rooms and you can see
those remaining transitional probabilities

And then just kind of eyeballing the 
stochastic matrix here, just to make sure

we can sort of make sense of it.

The way you wanna read this is, I have the
columns as representing my starting place

and the rows representing my end place.
Okay?

So, for instance, if I am in room one I 
probably have been moving or

staying, I should say, to room one is zero
as we just mentioned a moment ago. Moving

to maybe a different component, if I am 
currently in room three, the probability

of, say, of moving then to room two or
transitioning is two-thirds. Lets see that

from the directed graph, so from three to 
two, yes true enough, is probability two

thirds. So, there is our sochastic matrix.

So now the question we wanna answer is
this, basically what happens as time

marches on? Can we in a sense get a 
cognitive blue print of the long term

thinking or the long term behavior of the
Mouse in the Maze? And in order to answer

that question we are gonna go ahead and
solve for the steady state vector with

respect to these stochastic matrix.

Okay, so before we go ahead and solve for 
the steady state vector for this

particular problem lets go ahead and just
to get the mechanisms down, plug in a

vector or two and induce some calculation
for this Markov chain. So, you will recall

that our stochastic matrix P is given as
follows. Let's suppose now that our

initial state vector is 1, 0, 0. So, in
other words the mouse starts in room one.

Now, if I want to figure out my 
probability vector, my transitional state

vector, after one time iteration, I just
multiply on the left by my matrix P and

then I get, not surprisingly, the 
following probability vector.

So, after one step we have probability of
one half that the mouse is in room two and

probability one half that the mouse is in 
room three. So, if I wanna turn the crank

with the Markov process again and see what
my probability look like after two

iterations or two time steps and multiply
again by P, now I get this new state

vector one third, one third, one third, so
uniform probability vector.

So, the way I would interpret this result
is to say after two movements of the

Mouse in the Maze, there is an equal
chance. So, in other words, a one third

probability that the mouse is either in
room one, room two or room three.

So the question is, what is the end 
behavior of the movement of the mouse in

the maze, in other words, what is the 
steady state vector for the system?

Let's codify the idea using the language
of mathematics. So, a steady state vector,

we'll denote it as x, is by definition a
probability vector, in other words, the

components of that vector sum to one. And
basically, what's happening is when I

multiplying in the left by my stochastic
matrix - when I multiply a stochastic

matrix times a steady state vector, it 
remains unchanged, so I get x back.

One way to put this also, we can say that
our system- our dynamic system is in

equilibrium when it reaches the steady
state vector.

Okay, so when I do that calculation, where
I solve for x or in other words, steady

state vector, we get the following result:
x equals to one quarter, three eights,

three eights. You can notice that if I add
the components of that vector together I

get sum 1. So it is, in fact, a 
probability vector, which is a nice thing

to check. And because it is a steady state
vector, to remind you, it remains fixed.

It's a fixed point, in other words, when I
multiply by the matrix P on the left.

So in a sense, at some point eventually,
our Markov chain turns into an infinite

sequence of just these steady state 
vectors. So to remind of a few conceptual

details as well here, how do we know, for
instance, that the steady state vector x

is the only such steady state vector
associated with that matrix P? We know

that from the theorem I mentioned
previously in this section. Namely, as

long as the stochastic matrix P is regular
meaning if I take power- enough powers of

it, I get strictly positive components.
Well, I haven't shown it directly here but

if you square a P, by the way, you can see
that you get strictly positive components.

So, P is regular. So, the theorem 
guaranteed us that if our stochastic

matrix is regular then, there are two
consequences, one is that the steady

state vector x is unique, so there is only
steady state vector or fixed point for

this matrix. The other guarantee which is
important in understanding and

interpreting this problem and its answer, 
is that no matter where we start in our

Markov chain, the Markov chain will
converge to that particular vector.

So, what does all this means in the 
context of this particular

application of the Mouse in the Maze
problem?

Well, it means the
following, if I were to place the mouse,

initially, in any of the rooms in the maze
in other words with respect to any initial

state vector I like and I let the mouse 
run around the maze as long as it wants,

I can then answer the question, what is 
the end behavior of the mouse? And that

answer is as follows, in the long run, the
mouse spends a quarter of its time in room

one, three eights of its time on room two
and similarly, three eights of its time in

room three. So, there we have it.
Let's then in retrospect, now that we have

solved the problem, take a step back and
appreciate what a Markov chain and sort

of in conjuncture with this procedure of
solving for a steady state vector have

done for us. Right in the beginning we 
posed a rather daunting and complicated

question or series of premises. We said 
knowing the probabilistic tendencies of

this mouse, moving in the maze, what is 
the long term behavior of this dynamical

process? And the answer, with just really
a scant few computations, in the end was

achieved pretty readily. So, there is a 
classic example of an application of the

Markov chain. And that ends for our
section 3E.