A question about the choice and interpretation of the jumping distribution in Metropolis-Hastings algorithm

Question

In order to implement the MH algorithm you need a proposal density or jumping distribution $q(⋅|⋅)$, from which it is easy to sample. If you want to sample from a distribution $f(⋅)$, the MH algorithm can be implemented as follows:

1. Pick a initial random state $x_0$.
2. Generate a candidate $x^*$ from $q(⋅|x_0)$.
3. Calculate the ratio $\alpha=\frac{f(x^*)}{f(x_0)} \frac{q(x_0|x^*)}{q(x^*|x_0)}$.
4. Accept $x^*$ as a realisation of f with probability min(1,α).
5. Take $x^*$ as the new initial state and continue sampling until you get the desired sample size.

$q$ is often symmetrical so $\frac{q(x^*|x_0)}{q(x_0|x^*)}=1$

I have two questions :

1. Does $q$ describe the Birth-or-Death move that is often associated with Metropolis Hastings algorithm? When would you want to take $q$ non symmetrical? A colleague of mine wants to implement MH for sampling from a complex distribution (Y is a sample from X with a distribution $f$), and said he would impose different probabilities of picking $u$ in $X-Y$ to make the chain converge quicker (with Y the sample at a time and $\{Y-{v}\}\cup{\{u\}}$ the sample retained the next time if the ratio is big enough at step 3). Is it standard?

2. The context in which I personally use MH algorithm is for Bayesian model averaging. In this context, I have some models $M_i$ with an a priori probability $\pi$, some data D and an a posteriori probability I want to sample from. So the ratio of the 3th step of the algorithm becomes $\frac{f(D|M_i)\pi(M_i)}{f(D|M_j) \pi(M_j)}$ (Bayes formula). Do you agree that $q$ in this case is still about the modification of $M_i$ between two iterations and the Bayesian context doesn't change anything about it? Shouldn't my colleague adopt a Bayesian approach and choose a a priori distribution on the observations to favour those he wants to select more often rather than changing the jumping distribution?

Sorry for the naive questions, I want to be sure I understood the algorithm.

EDIT : some of you say there is no link between MH and Birth-death moves, but here is what is explained in the vignette of the BMS package I use :

"In addition to enumerating all models, BMS implements two MCMC samplers that differ in the way they propose candidate models:

• Birth-death sampler (bd): This is the standard model sampler used in most BMA routines. One of the K potential covariates is randomly chosen; if the chosen covariate forms already part of the current model Mi, then the candidate model Mj will have the same set of covariates as Mi but for the chosen variable ('dropping' a variable). If the chosen covariate is not contained in Mi, then the candidate model will contain all the variables from Mi plus the chosen covariate ('adding' a variable).

• Reversible-jump sampler (rev.jump): Adapted to BMA by Madigan and York (1995) this sampler either draws a candidate by the birth-death method with 50% probability. In the other case (chosen with 50% probability) a 'swap' is proposed, i.e. the candidate model Mj randomly drops one covariate with respect to Mi and randomly adds one chosen at random from the potential covariates that were not included in model Mi.

• Enumeration (enum): Up to fourteen covariates, complete enumeration of all models is the default option: This means that instead of an approximation by means of the aforementioned MCMC sampling schemes all possible models are evaluated. As enumeration becomes quite time-consuming or infeasible for many variables, the default option is mcmc="bd" in case of K > 14, though enumeration can still be invoked with the command mcmc="enumerate"."

I just want to know if there is a link between the sampling option and $q$.

Answer 1

As signalled by bdeonovic, there seems to be some confusion in your understanding of Metropolis-Hastings algorithms. What you describe is the standard version of the algorithm where both target $f$ and proposal $q(\cdot|x)$ are densities against the same dominating measure (e.g., the Lebesgue measure). In this framework, the proposal $q(\cdot|x)$ can be absolutely anything and be chosen in terms of the target $f$ [and of the observations in a Bayesian setting] and of its mixing performances. For instance, when $q(\cdot|x)$ is a random walk, the scale of the random walk can be selected for the acceptance rate to stay around 0.234. But non-symmetric versions are also available like the Metropolis-adjusted Langevin (MALA) algorithm which is asymmetric and aims at bringing the chain towards the mode(s) of the target $f$.

You seem to be interested in model choice, where the measure issues are much more complicated because the target is defined on a space of varying dimension, with the measure being a direct sum of measures. thus requiring the move to be equally measurable against this sum. Green (1995) managed to formalise this requirement into a valid framework and produced the reversible jump Metropolis-Hastings algorithm, which works by pairs of models and spaces and proposals. While the implementation can be brought down to a reasonable level of difficulty, the presentation of the algorithm does not fit in a forum answer. I thus suggest you read the reference by Green (1995) or a book like my book with George Casella (2004, Chap. 11).

As for your question #2, if you can compare directly the models via the marginal likelihoods $p(D|M_i)$, there is no need for reversible jump as you are working on a finite or countably discrete space of model indices. Any proposal exploring this space produces a valid Markov chain on the model indices but in cases you can compute directly those probabilities $p(D|M_i)\pi(M_i)$ there is even no need for MCMC since all you have to do is select the highest value or average across models. If you cannot list (and compare) all models, you need a proposal $q$ that considers enough model indices at once to guarantee irreducibility of the resulting Markov chain: since $q$ can be asymmetric, it should appear in the ratio.

Answer 2

1. $q$ is the proposal distribution. I've only ever seen symmetric $q$, but it's okay to make it asymmetrical since you're dividing the ratio out in $\alpha$. It's normal to choose $q$ so that the chain converges more quickly. If $q$ is too wide, then you have a lot of rejected points, and if it's too narrow, it takes a long time to explore the high probability areas.

2. $q$ has nothing to do with your $\pi$ or $f$ or $M$. The $f$ in step 3 is your Bayesian posterior (likelihood times prior). Changing $q$ should not affect your sampled distribution (if it does, that's a bad $q$, and you would have to pick a weird $q$ for that to happen.)

Answer 3

I would add to other answers that $q$ can be chosen as asymmetric when the support of the prior for a given parameter is restricted. For example, if $p(\theta<0)=0$ then it could be interesting to choose a proposal avoiding negative $\theta$ e.g. using $q(.|x)$ as a gaussian density with location parameter $x$ truncated on $R^+$. In such a case $q(x_1|x_2) \ne q(x_2|x_1)$. This can easily noticed by considering that in a truncated normal density, the value of the location parameter appears in the normalisation constant of the density (and is thus different in $q(.|x_2)$ and $q(.|x_1)$).