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.