I read Multiple-Try Metropolis from Wikipedia and I do not understand some points.

Suppose the current state is $\mathbf{x}$. The MTM algorithm is as follows:

  1. Draw ''k'' independent trial proposals $\mathbf{y}_1,\ldots,\mathbf{y}_k$ from $Q(\mathbf{x},.)$. Compute the weights $w(\mathbf{y}_j,\mathbf{x})=\pi(\mathbf{y}_j)Q(\mathbf{y}_j,\mathbf{x})\lambda(\mathbf{y}_j,\mathbf{x})$ where $\lambda$ is non-negative and symmetric, but otherwise arbitrarily chosen.
  2. Select $\mathbf{y}$ from the $\mathbf{y}_i$ with probability proportional to the weights.
  3. Now produce a reference set by drawing $\mathbf{x}_1,\ldots,\mathbf{x}_{k-1}$ from the distribution $Q(\mathbf{y},.)$. Set $\mathbf{x}_k=\mathbf{x}$ (the current point).
  4. Accept $\mathbf{y}$ with probability :$$r=\text{min} \left(1, \frac{ w(\mathbf{y}_1,\mathbf{x} )+ \ldots+ w(\mathbf{y}_k,\mathbf{x}) }{ w(\mathbf{x}_1,\mathbf{y})+ \ldots+ w(\mathbf{x}_k,\mathbf{y}) } \right)$$
  1. why is probability proportional?
  2. Why do we sample a reference set at the step 3?
  • $\begingroup$ step 2 says: Select $\textbf{y}$ from $\textbf{y}_{i}$ with probability proportional to the weights. What is this? $\endgroup$ – math_lover Apr 4 '16 at 17:24
  • $\begingroup$ The weights do not sum up to one. $\endgroup$ – Xi'an Apr 4 '16 at 19:39
  • $\begingroup$ The additional simulations at step 3. are there to ensure reversibility at step 4. $\endgroup$ – Xi'an Apr 5 '16 at 6:23
  • $\begingroup$ @Xi'an Thanks for your answer. What is reversibility? I do not understand $\endgroup$ – math_lover Apr 6 '16 at 6:49
  • $\begingroup$ Simulating things backward, i.e. conditionally on $\mathbf{y}$, is necessary to make the Markov process reversible, which helps in establishing that the right target is achieved via the detailed balance condition $$ \pi(\mathbf{y})K(\mathbf{y},\mathbf{x})=\pi(\mathbf{x})K(\mathbf{x},\mathbf{y}) $$ when $K(\cdot,\cdot)$ is the MH kernel and $\pi(\cdot)$ the stationary distribution density. $\endgroup$ – Xi'an Apr 6 '16 at 6:56

[Warning: I used the same notations $Q(y,x)$ $-$and $w(y,x)$$-$ as in the question but it is counter-intuitive as we usually denote this proposal kernel $Q(y|x)$ or $Q(x,y)$.]

Multiple-Try Metropolis is a regular Metropolis move when including the other proposals $y_2,\ldots,y_k$ as auxiliary variables (assuming $y=y_1$ and when picking $Q(y_2,x)\cdots Q(y_k,x)$ as the target for those auxiliaries. Indeed, if one considers the Metropolis-Hastings ratio for the proposed move from the vector $(x,x_2,\ldots,x_k)$ to the vector $(y_1,y_2,\ldots,y_k)$, one gets $$\begin{align*}\overbrace{\dfrac{\pi(y_1)Q(y_2|x)\cdots Q(y_k|x)}{\pi(x_1)Q(x_2|y_1)\cdots Q(x_k,y_1)}}^{\text{ratio of targets}} &\times \overbrace{\dfrac{Q(x,y_1)Q(x_2,y_1)\cdots Q(x_k,y_1)}{Q(y_2,x)\cdots Q(y_k|x)}}^{\text{ratio of proposals}}\\ &\times \underbrace{\dfrac{\frac{w(x,y_1)}{w(x,y_1)+w(x_2,y_1)+\ldots+w(x_k,y_1)}}{\frac{w(y_1,x)}{w(y_1,x)+w(y_2,x)+\ldots+w(y_k,x)}}}_{\text{ratio of selection probabilities}}\\ \end{align*} $$ Things then simplify to $$\dfrac{w(y_1,x)+w(y_2,x)+\ldots+w(y_k,x)}{w(x,y_1)+w(x_2,y_1)+\ldots+w(x_k,y_1)}$$ when using $$w({y}_j,{x})=\pi({y}_j)Q({y}_j,{x})\lambda({y}_j,{x})$$ since $$\dfrac{w(x,y_1)}{w(y_1,x)}=\dfrac{\pi(x)Q(x,y_1)\lambda(x,y_1)}{\pi(y_1)Q(y_1,x))\lambda(y_1,x)}$$

[An even more detailed validation is to establish that the move satisfies detailed balance, that is, that $$\pi(\mathbf{y})\mathfrak{h}(\mathbf{y},\mathbf{x})=\pi(\mathbf{x})\mathfrak{h}(\mathbf{x},\mathbf{y}),$$ where $\mathfrak{h}$ is the multiple-try kernel.]

A different validation is to use a pseudo-marginal approach since $$\dfrac{w(y_1,x)}{w(y_1,x)+w(y_2,x)+\ldots+w(y_k,x)}\,Q(y_1,x)$$ is an unbiased estimator of the marginal distribution of $Y_1$ given $X=x$, when integrating out the auxiliary $y_j$'s.


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.