[MUSIC] So that's just the critic. That's just the probability
a that with which probability will accept and move proposed by Markov. And that's just in the way
the detail equation holds. So here we have the desired distribution,
pi, which we want to sample from. And we have the Markov chain Q,
which we want to fix by a critic A. And we want to fix this A such that
this [INAUDIBLE] equation holds. So pi is indeed a stationary distribution
for the mark of chain T, and that's the mark of chain T converge to
this point from any starting point. So let's see how we can choose
A such that this property holds. Let's, compose this equality and, move all the parts
that depends on A in one part. So, A(x to x'), Divided by A(x' to x), Equals to the following equation,
so we have On the one side we have Y of X prime. And the Q of X prime to x, and in the denominator we
have the same thing but With swapping x and x prime. [SOUND] So,
this is something computable right? We know y and q. So, we can compute this thing for
any two values. Let's call this, ratio raw. Let's assume for
a moment that this row is less than 1. So it's always greater than 0 because
it's some ratio of probabilities. But let's assume that
it's also less than 1. So it's just an assumption, it may
not hold too much, let's assume that. In this case, we have a ratio of eights, which would make equal to
which is less than one. So let's just use A of
x prime to be your one And A ox X prime to X to be 1. This way the desire to holds true right, because A of X to X prime divided to
X prime to X Will be [INAUDIBLE]. And what you may notice that we could
have chosen here some other numbers, like 4 divided by 2, for
example, or 1 divided by 2. But this will also work, the overall mark of chain will
deconverge to the distribution. [INAUDIBLE]. Because this I think is
the probability we accepts they move. And the way to increase probability
will necessarily inject more moves. So we risk more capacity for
our more [INAUDIBLE] which will reject. So this choose is the maximum
acceptance probability we can make while keeping
the ratio to be low And what to do if the ratio
is greater than one. Well we can just choose
to be A of X prime, X to X prime to be divided by one,
and this P to be one N. So we can summarize this
to cases that are always less than one and
they're always greater than one, in the form of
the expression A of X prime, of X dot prime, To be equal to minimal. Within two values, 1 and this ratio, so and
pie of X prime times Q of X prime dot X And the same thing while changing the
parameters x to x prime and vice versa. So this expression works both for the case where the ratio is less
than than 1 and greater than 1. You can check it by considering two cases. And in one case it will
be just 1 because it's. Minimum between 1 and
something greater than 1. In other case it will be wrong. So this and by choosing this critic we
indeed can prove that the overall mark of defined by this kind of
procedure will indeed. Follow this equation. So the distribution probably will be
stationary for our Markov chain, and that we will convert to distribution for
any starting point. Last, by choosing this critic,
we may sample from the distribution y. To summarise the metropolis
Hastings approach to building chain that converges to
the desired distribution pi. We have to start with sum of mac chain q,
which we don't have anything to do with the distribution pie and
then this mark of chain on each step will propose symbols and we'll have a correct
with sometimes rejects this move. And ask the mark of chain to stay
where it was at the various straight. And we just proved that if you
defined your coreject to be like this, if your acceptance from bill will be
this expression minimum between one and some ratio. Then no matter from which
Markov chain Q is started with, you will necessarily converge
to the desired distribution pi. Note that this acceptance probability,
it's the only place where we use our distribution pi,
which we want to sample from. And note that we don't have to
know this distribution pi exactly. We may know it up to
normalization constant. because here, we'll have a ratio between
our distribution at two different points. It doesn't matter how we
normalize this distribution. The ratio will not care
about the normalization, because if we divide
each of the parts of this ratio by the normalization constant z,
nothing will change. So, this method, as well as
the Gibbs sampling, can be used when you don't know the normalization
constant of your distribution. We have discussed that we can choose q to
be anything in distribution number one. Well obviously,
the Q should be nonzero anywhere, so the ratio will be well-defined. But of course, the efficiency and the properties of your algorithm
will depend on the choice of Q. There are kind of two
opposing forces here. So first of all,
Q should make large steps, it should spread out and
kind of roll freely in the sample space, to make the samples less correlated and
to converge faster. On the other hand, if you have too large
steps, your critic will reject them, too often, and you will waste your capacity by
staying at the same place for too long. Because if you're now, for
example, already converged, and you're in the high-density region,
then if you're Q proposes all this to make too-large moves, then you will move
outside your high density region, and the will not be happy with that. It will say I don't want to go there,
the probability distribution curve ball doesn't work,
isn't high in that region. So in the next video, we'll see some small demo of how this
approach can work in One dimensional case. [SOUND]