PROFESSOR: Hi, everyone.
Welcome back.
So today, I'd like to tackle a problem in Markov matrices.
Specifically, we're going to start with this problem which
almost has a physics origin.
If we have a particle that jumps between positions A and
B with the following probabilities--
I'll just state it--
if it starts at A and jumps to B with probability 0.4 or
starts at A and stays at A with probability 0.6 or if it
starts at B then it goes to A with probability 0.2 or stays
at B with probability 0.8, we'd like to note the
evolution of the probability of this particle over a long
period of time.
So specifically the problem we're interested today is if
we have a particle and we know that it starts at position A,
what is the probability that it is at position A and the
probability that it's at position B after one step,
after n steps, and then finally after an infinite
number of steps?
So I'll let you think about this problem for a moment and
I'll be back.
Hi everyone.
Welcome back.
So the main difficulty with this problem is that it's
phrased as a physics problem.
And we need to convert it into some mathematical language to
get a handle on it.
So specifically, what we'd like to do is to convert this
into a matrix formulism.
So what we can do is we can write this little graph down
and describe everything in this graph using a matrix.
So I'm going to call this matrix A, and I'm going to
associate the first row of A with particle position A and
particle position B. And I'll associate the first and second
columns with particles positions A and B. And then
what I'm going to do is I'm going to fill in this matrix
with the probability distributions.
So, specifically what's going to go in this top left corner?
Well, the number 0.6, which represents the probability
that I stay at position A, given that I start at position
A. What's going to go here in the bottom left hand corner?
Well, we're going to put 0.4, because this is the
probability that I wind up at B, given that I start at A.
And then lastly, we'll fill in these other two columns or the
second column with 0.8 and 0.2.
So I'll just state briefly this is what's
called a Markov matrix.
And it's called Markov, because first off, every
element is positive or 0.
And secondly, the sum of the elements in each column is 1.
So if we note 0.4 plus 0.6 is 1, 0.8 plus 0.2 is 1.
And these matrices come up all the time when we're talking
about probabilities and the evolution of probability
distributions.
OK.
So now once we've encoded this graph using this matrix A, we
now want to tackle this problem.
So I'm going to introduce the vector P, and I'm going to use
a subscript 0 is to denote the probability that the particle
is at time 0.
So we're told that the particle starts at position A.
So at time 0, I'm going to use the vector 1, 0 again.
I'm going to match the top component of this vector with
the top component of this matrix and the first column of
this matrix.
And then likewise the second component of this vector with
the second row and second column of this matrix.
And we're interested in how does this probability evolve
as the particle takes many steps.
So for one step, what's the probability of the particle
going to be?
Well, this is the beauty of introducing matrix notation.
I'm going to denote P1 to be the probability of the
particle after one step.
And we see that we can write this as the matrix A
multiplied by P0.
So the answer is 0.6 and 0.4.
And I achieve this just by multiplying this matrix by
this vector.
OK?
So this concludes part one.
Now part two is a little trickier.
So part two is n-steps.
And to tackle this problem, we need to use
a little more machinery.
So first off, I'm going to note that P1 is A times P0.
Likewise, P2--
so this is the position of the-- the probability
distribution of the particle after two steps.
This is A times P1, which is A squared times P0.
And we note that there's a general trend.
After n-steps--
so Pn--
the general trend is it's going to be this matrix A
raised to the nth power, multiply the vector P0.
So how do we take the nth of a matrix?
Well, this is where we use eigenvectors and eigenvalues.
So recall, that we can take any matrix A that's
diagonizable and write it as U D U inverse, where D is a
diagonal matrix and this matrix U is a matrix whose
columns correspond to the eigenvectors of A.
So for this problem I'm, just going to state what the
eigenvalues and eigenvectors are.
And I'll let you work them out.
So because it's a Markov matrix, we always have an
eigenvalue which is 1.
And in this case, we have an eigenvector U
which is 1 and 2.
In addition, the second eigenvalue is 0.4.
And the eigenvector corresponding to
this one is 1, -1.
And I'll just call these U1 and U2, like that.
OK, we can now write this big matrix U as 1, 2, 1, -1.
D is going to be--
now I have to match things up.
If I'm going to put the first eigenvector in the first
column, we have to stick 1 in the first column as well and
then 0.4 like this.
And then lastly, we also have U inverse which I can just
work out to be -1/3, one over the determinant, times -1, -1,
-2, and 1, which simplifies to this.
OK, so now if we take A and raise it to the power of n, we
have this nice identity that all the U and U inverses
collapse in the middle.
And we're left with U, D to the n, U inverse, P0.
Now raising the a diagonal matrix to the power of n is a
relatively simple thing to do.
We just take the eigenvalues and raise them to
the power of n.
So when we compute this product, there's a question of
what order do we do things?
Now these are 2 by 2 matrices, so in theory we could just
multiply a 2 by 2 matrix, 2 by 2 matrix, 2 by 2 matrix, and
then on a vector which is a 2 by 1 matrix.
But if you're in a test and you're cramped for time, you
want to do as little computations as possible.
So what you want to do is you want to start on the right
hand side and then work backwards.
So if we do this, we end up obtaining 1, 2, this is going
to be to the power of n, 1/3, 1, 2.
OK, so for this last part, I'm just going to write down the
final answer.
And I'll let you work out the multiplication of matrices.
So we have for Pn, 1/3, 2 times 0.4 to the n, plus 1,
-2, 0.4 to the n, plus 2.
And this is the final vector for P of n.
So this finishes up Part 2.
And then lastly for Part 3, what happens
when n goes to infinity?
Well, we have the answer for any n.
So we can just take the limit as n goes to infinity.
Now, specifically as n goes to infinity, 0.4 raised to some
very large power vanishes.
So these two terms drop off.
And at the end of the day, we're left with P
infinity is 1/3 1, 2.
OK?
So just to recap, we started off with a particle starting
at A, and then after a very long time, the particle winds
up with a probability distribution which
is 1/3 1 and 2.
And this is quite characteristic of Markov
matrix chains.
Specifically, we note that 1/3 1, 2 is a multiple of the
eigenvector corresponding to eigenvalue 1.
So even though the particle started at position A, after a
long period of time, it tended to forget where it started and
approached, diffused into this uniform distribution.
OK.
I'd like to finish up here.
And I'll see you next time.