0:03

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.

Â