Multiple-try Metropolis (MTM) is a sampling method that is a modified form of the Metropolis–Hastings method, first presented by Liu, Liang, and Wong in 2000. It is designed to help the sampling trajectory converge faster, by increasing both the step size and the acceptance rate.
Background
Problems with Metropolis–Hastings In Markov chain Monte Carlo, the Metropolis–Hastings algorithm (MH) can be used to sample from a probability distribution which is difficult to sample from directly. However, the MH algorithm requires the user to supply a proposal distribution, which can be relatively arbitrary. In many cases, one uses a Gaussian distribution centered on the current point in the probability space, of the form Q ( x ′ ; x t ) = N ( x t ; σ 2 I ) {\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\sigma ^{2}I)\,} . This proposal distribution is convenient to sample from and may be the best choice if one has little knowledge about the target distribution, π ( x ) {\displaystyle \pi (x)\,} . If desired, one can use the more general multivariate normal distribution, Q ( x ′ ; x t ) = N ( x t ; Σ ) {\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\mathbf {\Sigma } )} , where Σ {\displaystyle \mathbf {\Sigma } } is the covariance matrix which the user believes is similar to the target distribution. Although this method must converge to the stationary distribution in the limit of infinite sample size, in practice the progress can be exceedingly slow. If σ 2 {\displaystyle \sigma ^{2}\,} is too large, almost all steps under the MH algorithm will be rejected. On the other hand, if σ 2 {\displaystyle \sigma ^{2}\,} is too small, almost all steps will be accepted, and the Markov chain will be similar to a random walk through the probability space. In the simpler case of Q ( x ′ ; x t ) = N ( x t ; I ) {\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,} , we see that N {\displaystyle N\,} steps only takes us a distance of N {\displaystyle {\sqrt {N}}\,} . In this event, the Markov Chain will not fully explore the probability space in any reasonable amount of time. Thus the MH algorithm requires reasonable tuning of the scale parameter ( σ 2 {\displaystyle \sigma ^{2}\,} or Σ {\displaystyle \mathbf {\Sigma } } ).
Problems with high dimensionality Even if the scale parameter is well-tuned, as the dimensionality of the problem increases, progress can still remain exceedingly slow. To see this, again consider Q ( x ′ ; x t ) = N ( x t ; I ) {\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,} . In one dimension, this corresponds to a Gaussian distribution with mean 0 and variance 1. For one dimension, this distribution has a mean step of zero, however the mean squared step size is given by
⟨ x 2 ⟩ = ∫ − ∞ ∞ x 2 1 2 π e − x 2 2 d x = 1 {\displaystyle \langle x^{2}\rangle =\int _{-\infty }^{\infty }x^{2}{\frac {1}{\sqrt {2\pi }}}e^{-{\frac {x^{2}}{2}}}dx=1}
As the number of dimensions increases, the expected step size becomes larger and larger. In N {\displaystyle N\,} dimensions, the probability of moving a radial distance r {\displaystyle r\,} is related to the Chi distribution, and is given by
P n ( r ) ∝ r n − 1 e − r 2 / 2 {\displaystyle P_{n}(r)\propto r^{n-1}e^{-r^{2}/2}}
… excerpt ends here. Continue reading the full article.
