# Multiple-Try Metropolis question

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?
• step 2 says: Select $\textbf{y}$ from $\textbf{y}_{i}$ with probability proportional to the weights. What is this? – math_lover Apr 4 '16 at 17:24
• The weights do not sum up to one. – Xi'an Apr 4 '16 at 19:39
• The additional simulations at step 3. are there to ensure reversibility at step 4. – Xi'an Apr 5 '16 at 6:23
• @Xi'an Thanks for your answer. What is reversibility? I do not understand – math_lover Apr 6 '16 at 6:49
• 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. – 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.