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.