In the previous video we discussed one way
to build a Markov chains that converged to a zag distribution,
namely the Gibbs sampling.
And we have discussed that it has some downsides.
It produces highly correlated samples
and it converts somewhat slowly to the distribution.
And both of these downsides came from one property,
that Gibbs is doing kind of local and small steps in the sample space.
In this video, we're going to discuss some other scheme to build Markov chains,
which instead of producing just one predefined Markov chain,
will give you a whole family of Markov chains.
And you can choose the one that has the desired properties like,
it converges faster and or maybe it produces less correlated samples.
This family of techniques is called Metropolis-Hastings and the idea is
to apply the rejection sampling idea, two Markov chains.
So let's start with
sum Markov chain which maybe doesn't have anything to do with the desired distribution B.
But on the bright side,
this Markov chain Q is kind of through freely in the sample space.
It's doing very large steps and thus it can converge
faster and it produces almost uncorrelated samples.
It's a nice Markov chain but it doesn't produce what we want,
dissembles from the distribution B.
And now let's introduce a critic.
And a critic of something that says,
wait a minute you can go there right now,
so please stay where you are and wait until you generate some reasonable direction to go.
And the critic make sure that the Markov chain we have doesn't
go in some regions where the probability of our desired distribution B is low.
Well, at least it doesn't go there too often.
And we will accept the proposal,
the generated sample from the transition probabilities of the Markov chain Q with
probability given by the critic and otherwise
we will object and will stay where we were at the previous equation.
So, this is the general idea and
in the following part we will
discuss how to build such a critic for
a given Markov chain Q and the desired distribution B.
So first let's discuss how this overall scheme will look like in terms of a Markov chain.
So we had some Markov chain Q and we changed its procedure to generate points.
And so now this overall scheme generates its points like this.
It transitions from the point X to X prime with probability.
Well, first of all we need to generate this X prime from the proposal distribution Q
from the first Markov chain Q and then we have to accept this point.
And this happens with probability given by the critic.
So A of X to X prime.
This is true for all points that are not equal.
So if X not equal to X prime,
and if they're equal we have something a little bit more complicated because we again
could have proposed to move to X and then accepted that this proposal.
Or we can propose to move anywhere else and then reject that proposal,
which happens with probability one minus the probability given by the critic,
one is accepted in probability.
So, this is the transitional probability of overall Markov chain defined by
the process where we propose some points and then accept them with some probability.
And now we want our Markov chain to generate points from the desired distribution.
So, we want some distribution point to be stationary for this Markov chain
T. And the idea here is
to let alone the choice of the underlying command of Markov chain Q.
So give this freedom to the user of the method and try to choose A,
such that this quota holds.
So we have as input,
the Markov chain Q and the desired distribution pie.
And you want to choose the critic
such the distribution pie is indeed stationary for the final Markov chain G.
How can we do it?
Well, it's not easy because this equation is kind of complicated.
It has summation inside and this complicated definition of
the transition probability T. So,
to solve this problem we'll have to introduce one more concept,
which is called the Detailed Balance equation.
So, recall the definition of the stationary distribution, it's like this.
And Detailed balance equation is the following equation,
which gives you a sufficient condition for the stationary distribution.
So, if the detailed balance holds then the distribution pie isn't necessarily
a stationary one for
the transition probability D. And what does the Detailed Balance equation says us.
Well, it says that if we started from the distribution pie and made one step,
one timestep of our Markov chain G,
then the probability that we started
from X and move to X prime is the same as doing the reverse.
Is the same as starting from X prime and moving to X.
And if it's true, then the probability distribution pie is stationary for
G. And it's kind of easy to prove so let's just write down
the right hand side of the definition of
the stationary distribution and then substitute inside
that definition substitutes by
effects times the transition probability by the first equation,
by the detailed balance equation.
And thus we'll get a summation is the X of
this expression and the point expressed doesn't depend on x at all.
So we can move pie of X prime outside the summation to get something with this.
And finally summation of T of X brand X,
with respect to X is just one because this is some kind of probability distribution.
And if we sum out all possible outcomes, it will be one.
So, finally we have proven that if the Detailed Balance
holds then this solution isn't necessarily a stationary one.
So, returning to our problem.
We have a Markov chain Q,
which doesn't produce us samples which we all
want and we have a distribution of pie which we want to simplify.
Now we want to define a critic such
that the Markov chain that was created by this critic,
so the Markov chain T, will indeed produce samples from the distribution pie.
So, the distribution pie is stationary.
And since this property is hard to check,
instead we're going to just check that the distribution pie will be,
the detailed balance equation will be true for it.
So, in the next video,
we're going to use Blackboard to find the critic such that
this detailed balance equation holds for
the given Markov chain Q and the distribution pie.