[MUSIC] In the previous videos we familiarised
ourself with the Monte Carlo part. So now,
let's talk about the Markov Chain part. Which is actually really cool idea
on how to generate samples from complicated multi-dimensional
distributions efficiently. So what is a Markov chain? Imagine a frog which sits on a water lily. And this frog has kind of a discrete time. So at each time stamp, at each second,
for example, it makes a decision, whether to stay on its current lily or
to jump to the other one. And its decisions are kind of
prefined in probabilistic way. So if it's right now on
the left water lily, it will stay there with probability 0.3,
and it will move with probability 0.7. And if it's on the right one,
it will stay or move of probability 0.5. For example, now we can say that we have kind of
a dynamic system which has a state. So the state will show us
where the frog is now. This dynamic system, it kind of
evolves for time, its states changes. And the rules by which these
states changes are as follows. So the probability to transition from
left state to left state is 0.3 and etc. So you can define the behavior of your
dynamic system by using these transition probabilities. So we can simulate our dynamic system. We can see that, for example, on
the timestamp 1, the frog was on the left, and then maybe jumped to
the right on the timestamp 2. And then maybe it stayed to the right. Then maybe it went to the left, and
then, for example, to the right. And we can write down the path through the
state space which our dynamic system made. So it was left, right, right, left, right. And this thing is called
Markov chain because the next state is kind of depends
only on the previous state. So the frog doesn't care where
it was ten time steps ago, the only thing it cares
about is where it is now. To make the decision, it just needs
to know what is the state now. Okay, so we can ask ourselves a question. Like where the frog will be
after 10 timestamps for example. So let's say that we started from the
timestamp 1, and the frog was on the left. So with probability 1, it was on the left. With probability 0, it was on the right. What is the probability
that will be on the left or on the right in the timestamp 2? Well, it's 0.3 and 0.7, right? Okay, and what about the timestamp 3? It's going to trigger because we
don't know where it was before. But using the rule of some of
probabilities we can kind of check all the possibilities for
the previous state and use that to compute
the next probabilities. So the law of some tells us that
the value of the state of the timestamp 3 equals to the value of
the state of the timestamp 3, given that at the second
timestamp it was on the left, times the probability it was on
the left on the second timestamp. Plus the same thing,
considering that the station, it was on the right on
the second timestamp. And we can just, we know all these
values because the conditional probability is just
the transition probability. So the probability that the frog
moves from left to right for example, and the probability of x2
are computed in the previous line, so it is what we have just computed. And we can write it down, so
it will be for probability of the left, in the third timestamp. It will be something like 0.3 because it's the probability of transitioning
from left to left, hence the probability of 0.3. So it's from the previous
line of the table. Plus the probability of
the prior probability of being on the right hand side of
the previous timestamp, which is 0.7 times
the transition probability of moving from right of,
right to right, which is 0.5. I'm sorry,
from right to left which is 0.5. And we can write the same thing for
the for being at the right state,
in the timestamp 3, and we'll have some numbers like
is which are around 44 and 56. And we can continue this table,
for as long as we want. And we'll found out that the table kind of converged the numbers around 42 and 58. So after 1 million steps, the probability is that the frog is
on the left is almost exactly 42. And the probability that the frog is
on the right is almost exactly 58. Which basically means that we, if we
stimulate our frog for long enough and then write down where it ended
up with the one millionth step. Then we will kind of get a sample from
this discreet distribution of the values. So with probability 42 we'll get left,
and with probability 58 we'll get right. So let's look how it works. Say we select our frog for
like 1 million steps, and the last step was for
example left, okay? We write down this left and then simulate
another [INAUDIBLE] for the state space. So begin simulation and
the last state was for example right. We are the down and
by then phase several types. We have a sample from distribution
of the millionth step of our dynamic system given that
the frog started on the left. And this thing will be close
the probability 42 and 58. So even here we can see that
we have two out of five lefts, and three out of five rights,
which are close to 42 and 58. So this way we can generate,
it's a really lousy way to generate samples from this
distribution with the radius. So there's a much simpler way which we
have just discussed in the previous video. But note that this way, so,
build a dynamic system and simulate it and see where it end up, works even for
more complicated cases. So what if you have for
example ten lilies? Or 1 billion lilies? If you want to simulate your
distribution by in naive way. If you have billion values for
in your variable, you'll have to spend amount of time proportional to 1
billion to generate one sample from it. If you use this kind of idea of
simulate some dynamic system and then write down the last position. And if you do not that many steps like
1000 and hope that everything has converged to the true distribution, then
you can get a random number from this. Complicated distribution without
much trouble too much trouble of the naive approach the example. Or maybe a frog can be continuous, and can jump from any point on your
2D plane to any other point. In this case, you will be able
to generate your samples from a continuous distribution by
simulating your dynamic system. So the reason that you can
still sample efficiently, even if you have this
continuous dynamic system, by just writing down the path of this 2D
plane, and writing down the last position. So the idea Markov Chain
simulation applied to generating samples of
random values is as follows. We have a distribution
we want to sample from. It may be continuous, it may be discrete. We build a Markov Chain
that has this distribution, that converges to this distribution, okay? Then we start with from a initialization,
x0, and then we simulate our Markov Chain for long enough,
for example for 1,000 iterations. [COUGH] So
we start with x0 then we generate x1, by using the transition probability and
etc. And then we hope that after 1,000 steps, you will converge to
the true distribution p(x). Because we built our
Markov Chain this way. Then, after these 1,000 steps, you can throw away the first
1,000 samples, 1,000 states. And then you can start writing down
the states after these 1,000 steps. Because they all will be
from the distribution p(x), or at least close to it, if your
Markov Chain converged close enough. Okay, so this is the general idea. And in the following we'll discuss how to
build Markov Chain with this property. So how to build Markov Chain that
converge to the distribution you want to sample from. Now let's first discuss a little bit about
whether a Markov Chain converge anywhere. So in which case it does converge,
and which it doesn't. Well, the first observation here
is that the Markov chain doesn't have to converge to anywhere. So for example,
if you take a dynamic system like this, the frog will always swap
the lily at each time stamp. And so if you look at the table,
it will look like this. The permute of being on the left
on the first time step was 1 and the p on the right is 0. And then you swap things, so you're will
be on the right on the next time stamp and you will certainly be on the left
on the next time stamp, and etc. This thing will never converge this table. So it will always swap if the place. So this thing does work for us. We want something that
converge to some distribution. And the question of whether or
not given a Markov chain is converged, is converging to something,
is actually, pretty well studied. But first of all, we'll need
a definition of what does it mean for Markov chain to converge to
something in mathematical terms? So this is something called
a stationary distribution. And this is a distribution
of pi called stationary for Markov chain T If
the following equation holds. Which basically tells us that if
you start the distribution y and if you marginalize out the current
position x, then you will get basically the distribution over
position on the next time stamp. This has to be pi again. So basically, if you start from pi,
if you sample a state from pi, and then if you make just one transition,
so one timestamp of the Markov chain, then the distribution you will
get after that is, again, pi. This means that if we converge to,
if we encounter this pi at any point of our sampling,
then we will stay at it. We will not change this distribution. And there is a nice theorem that tells
us that If the transition probability is non-zero for any two states, so if we
can jump from any state to any other one, with non-zero probability, then there
exists a unique pi which is stationary. And we will converge to this
pi from any starting point. So if we build a Markov chain that has
non-zero transition probabilities, and that has a stationary
distribution which we want sample from,
then no matter where we start, if we simulate our Markov
chain long enough, we will get eventually samples from
the desired distribution y, [SOUND]