## understanding the Hastings algorithm

**D**avid Minh and Paul Minh [who wrote a 2001 Applied Probability Models] have recently arXived a paper on “understanding the Hastings algorithm”. They revert to the form of the acceptance probability suggested by Hastings (1970):

where s(x,y) is a symmetric function keeping the above between 0 and 1, and q is the proposal. This obviously includes the standard Metropolis-Hastings form of the ratio, as well as Barker’s (1965):

which is known to be less efficient by accepting less often (see, e.g., Antonietta Mira’s PhD thesis). The authors also consider the alternative

which I had not seen earlier. It is a rather intriguing quantity in that it can be interpreted as (a) a simulation of y from the cutoff target corrected by reweighing the previous x into a simulation from q(x|y); (b) a sequence of two acceptance-rejection steps, each concerned with a correspondence between target and proposal for x or y. There is an obvious caveat in this representation when the target is unnormalised since the ratio may then be arbitrarily small… Yet another alternative could be proposed in this framework, namely the delayed acceptance probability of our paper with Marco and Clara, one special case being

where

is an arbitrary decomposition of the target. An interesting remark in the paper is that any Hastings representation can alternatively be written as

where k(x,y) is a (positive) symmetric function. Hence every single Metropolis-Hastings is also a delayed acceptance in the sense that it can be interpreted as a two-stage decision.

**T**he second part of the paper considers an extension of the accept-reject algorithm where a value y proposed from a density q(y) is accepted with probability

and else the current x is repeated, where M is an arbitrary constant (incl. of course the case where it is a proper constant for the original accept-reject algorithm). Curiouser and curiouser, as Alice would say! While I think I have read some similar proposal in the past, I am a wee intrigued at the appear of using only the proposed quantity y to decide about acceptance, since it does not provide the benefit of avoiding generations that are rejected. In this sense, it appears as the opposite of our vanilla Rao-Blackwellisation. (The paper however considers the symmetric version called the independent Markovian minorizing algorithm that only depends on the current x.) In the extension to proposals that depend on the current value x, the authors establish that this Markovian AR is in fine equivalent to the generic Hastings algorithm, hence providing an interpretation of the “mysterious” s(x,y) through a local maximising “constant” M(x,y). A possibly missing section in the paper is the comparison of the alternatives, albeit the authors mention Peskun’s (1973) result that exhibits the Metropolis-Hastings form as *the* optimum.

*Related*

This entry was posted on August 26, 2014 at 12:14 am and is filed under Books, Statistics with tags accept-reject algorithm, acceptance probability, Barker's algorithm, delayed acceptance, Metropolis-Hastings algorithms, vanilla Rao-Blackwellisation. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

### One Response to “understanding the Hastings algorithm”

### Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

April 14, 2022 at 10:31 am

[…] alternative version sounds like Barker’s (1965) and Hastings’ (1970) versions when the acceptance probability is alpha(x,x^prime) = s(x,x^prime) left(1+dfrac{p(x) q(x^prime|x)}{p(x^prime) […]