0
$\begingroup$

Let us consider the conventions on names used in the theoretical derivation of Metropolis-Hastings Monte Carlo as outlined here, for the sake of common nomenclature.

What we are building is a step-by-step Markov Chain Monte Carlo (MCMC) algorithm to describe the evolution of a system in an initial state towards a final state distributed according to a desired probability distribution $P(x)$. This final sentence is to be read in the sense that repeated iterations of the algorithm, on distinct initial states, lead to an ensemble of states distributed according to a desired distribution $P(x)$.

For each of these iterations, during each step, given an initial state $x$ for the system and a final state $x'$, the probability of the system moving from $x$ to $x'$ is factorized into the proposal probability $g(x'|x)$ and the acceptance probability $A(x'|x)$ -- i.e. $P(x'|x) = g(x'|x) A(x'|x)$.

The meaning of the proposal probability is that of being the probability associated to proposing the next state to be $x'$ if we start from the state $x$. That of the acceptance probability is the probability of accepting the state $x'$ if we start from the initial state $x$ and derives from the final desired distribution of the states $P(x)$ -- aside from physically justified fluctuations, the most probable states are accepted and the least ones rejected.

All that is stated above is valid for any MCMC method.

In a common scenario, the specific case of the Metropolis process -- which is a particular MCMC method -- we choose $g(x'|x)$ to be symmetrical. But beside it being so, we generally pose no further constraints on this choice.

It left me with some open questions: how does the choice of the form of the proposal distribution influence the MCMC algorithm? Does it depend on the system in analysis? Specifically, is there any physical meaning behind the choice of the proposal distribution $g(x'|x)$?

[Cross posted from physics.stackexchange]

$\endgroup$
0
$\begingroup$

In an extreme case, if $g(x^\prime | x) = P(x^\prime | x)$ then $A(x^\prime | x) = 1$ for all $x$ and $x^\prime$. This means that the proposal coincides with the conditional probability of the desired distribution. It is tempting to think that by choosing $g(x^\prime | x)$ close (in some sense) to $P(x^\prime, x)$, we will have a good MCMC sampler: the physical interpretation of $g(x^\prime | x)$ is straight forward in that case and we can ensure a very high acceptance ratio because $A \approx 1$.

However, in practice it is better to adopt a $g(x^\prime | x)$ that allows the system to transition from $x$ to a $x^\prime$ that is reasonably far away (in some suitable metric) from $x$ relatively often (i.e., with a relatively high expected acceptance ratio). Think, for example, of a system with many metastable states: if $g(x^\prime | x) = P(x^\prime | x)$ then the sampler will draw many points from the local metastable state but the MCMC chain will in general take a long number of iterations to explore the state space of the system (i.e., its mixing time will be large and it will only converge to the stationary distribution after a huge number of steps). By contrast, if we know something about the system and we judiciously select a function $g$ that allows for jumps between far away points in the state space sufficiently often, then the chain will converge faster. An example of this approach can be found in:

Minary, P., & Levitt, M. (2010). Conformational Optimization with Natural Degrees of Freedom: A Novel Stochastic Chain Closure Algorithm. Journal of Computational Biology, 17(8), 993–1010. http://doi.org/10.1089/cmb.2010.0016

$\endgroup$
0
$\begingroup$

It's less a question of physical meaning, and more a question of computational efficiency. The closer the proposal density is matched to the desired probability density, the faster the chain will converge to the probability distribution. I do not know of the proof of this, but it is straightforward to examine the end points. If the proposal distribution is much much wider than $P$, then the fraction of proposals that are rejected will be very high, converging to $100\%$ as the proposal width becomes infinitely wider than the width of $P$, causing the chain to contain only repeats of the original point. If the proposal distribution is much narrower than than $P$, then it will take more and more steps to explore the support of $P$, approaching an infinite number of steps as the width of the proposal distribution divided by the width of $P$ goes to $0$ (i.e. a delta function proposal always proposes the same point). My understanding is that the ideal acceptance rate for converging to $P$ at optimal speed is $50\%$.

Take all of this with a grain of salt, though, because I do not know of a rigorous proof.

$\endgroup$

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.