2
$\begingroup$

In the book Introducing Monte Carlo Methods by Casella and Robert, there's a sentence with which I'm having some trouble to understand.

«If the domain explored in $q$ [proposal] is too small, compared with the range of $f$(the target's distribution density), the Markov Chain will have difficulties in exploring this range and will converge very slowly»

The acceptance probability depends on the proposed state $y$, through $$\frac{f(y)}{q(y|x)}$$ The higher this proportion, the higher the chances of accepting the proposed move.

Unintuitive to me at least, a very low transition prob. $q(y|x)$ w.r.t. $f(y)$ would increase the chances of accepting the new move. So, if I'm at $x$ and I'm proposed a move to a lower transition probability state, then I'll want to move...

Is that to make me explore the whole domain of $q$? How can the support of proposal distribution impact convergence of RH-MH algorithm?

$\endgroup$
  • $\begingroup$ You want to explore $f$, not $q$. And yeah, if $q(y|x)$ is small and $f(y)$ big you gotta “seize the opportunity” and jump before you miss your chance. $\endgroup$ – Taylor Aug 6 '18 at 15:47
1
$\begingroup$

While obviously biased, I have trouble to see the difficulty with that sentence! If the proposal distribution has a bounded support, the Markov chain can only move to a point within that support and nowhere else. This means connecting two values $y_1$ and $y_2$ that have positive densities, $f(y_1)>0$ and $f(y_2)>0$ but are far away will require many iterations of the Metropolis-Hastings algorithm. In the worst case, if the support of $f$ is made of two disjoint sets $A_1$ and $A_2$ with $y_1\in A_1$ and $y_2\in A_2$ and if the distance between both sets is larger than the diameter of the support of $q(\cdot|\cdot)$ the Markov chain cannot leave the $A_i$ it started from.

Here is an illustration on a basic example:

target<-function(x){
  (sum((x-c(1,1))^2)<1)+(sum((x-c(-1,-1))^2)<1)
}

propal<-function(x,y){
  prod((x-y)^2<.01)
}

hastin<-function(x){
  prop=x+runif(2,-.1,.1)
  if (runif(1)*target(x)*propal(x,prop)>target(prop)*propal(prop,x))
    prop=x
  return(prop)}

T=2e3
mark1=matrix(0,T,2)
mark1[1,]=c(1,1)
for (t in 2:T)
  mark1[t,]=hastin(mark1[t-1,])

mark2=matrix(0,T,2)
mark2[1,]=-c(1,1)
for (t in 2:T)
  mark2[t,]=hastin(mark2[t-1,])

plot(mark1,col="sienna",type="l",axes=FALSE,xlim=c(-2,2),ylim=c(-2,2),xlab="",ylab="")
lines(mark2,col="steelblue")

with outcome

enter image description here

This poor behaviour of $q$'s with small support is unrelated with the point that when $f(y)/q(y|x)$ is large the chain should move there, which is correct.

$\endgroup$
  • 1
    $\begingroup$ Now I get it. My confusion came from the (mis?)use of the words domain/range in the sentence. I would write something like «If the space explored by $q$ ( $\text{supp}(f)$ ) is too small when compared with the domain of $f$, the Markov Chain will have difficulties in exploring $f$'s domain and thus will converge very slowly, if at all for practical purposes. $\endgroup$ – An old man in the sea. Aug 7 '18 at 8:09
  • $\begingroup$ I hope you didn't take it badly, I'm not a native, and I'm self-studying this. So, I must absorb the most I can from each specific word. Since I have no one to ask in case of doubt, and sometimes using this forum helps, but it's not a perfect substitute for a physical professor. Also, I'm a really slow learner... ;) $\endgroup$ – An old man in the sea. Aug 7 '18 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.