# How can the support of proposal distribution impact convergence of RH-MH algorithm?

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?

• 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. – Taylor Aug 6 '18 at 15:47

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

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.

• 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. – An old man in the sea. Aug 7 '18 at 8:09
• 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... ;) – An old man in the sea. Aug 7 '18 at 21:48