= Solution
Each state has exactly $k(n-k)$ neighbours: choose one occupied coordinate and one unoccupied coordinate to swap. The normalized <proposal distribution> is therefore
$$
q(v\mid u)=\frac1{k(n-k)}\mathbf1_{\{v\sim u\}}.
$$
The swap relation is symmetric and the number of neighbours is constant, so $q(v\mid u)=q(u\mid v)$. The <discrete uniform distribution> used as the <prior distribution> is also constant on $S_k$, with mass $\binom nk^{-1}$. Both factors cancel in the <Metropolis–Hastings acceptance probability>.
Let $Q=\Sigma^{-1}$ and $d=v-u$. The displayed <multivariate normal distribution> presupposes that the <covariance matrix> $\Sigma$ is a <positive-definite matrix>, so $Q$ is a <symmetric matrix>. Expanding the difference of <quadratic forms> gives
$$
\begin{aligned}
\log\frac{\pi(v\mid x)}{\pi(u\mid x)}
&=-\tfrac12\{(x-v)^TQ(x-v)-(x-u)^TQ(x-u)\}\\
&=d^TQ(x-u)-\tfrac12d^TQd\\
&=d^TQ\left(x-\frac{u+v}{2}\right).
\end{aligned}
$$
Consequently
$$
\boxed{\log\alpha(u,v)=\min\!\left\{0,\ (v-u)^T\Sigma^{-1}\left(x-\frac{u+v}{2}\right)\right\}.}
$$
The truncation at zero is essential: a log acceptance ratio can be positive, but the <logarithm> of an acceptance <probability> cannot.
For the particular proposed swap, let $a=i_1$ be the coordinate changing from zero to one and $b=i_2$ the coordinate changing from one to zero. Then $d=e_a-e_b$, and the untruncated scalar simplifies further to
$$
\boxed{(Q(x-u))_a-(Q(x-u))_b-\tfrac12(Q_{aa}+Q_{bb}-2Q_{ab}).}
$$
Only two rows and four entries of $Q$ are needed for this evaluation. This is <Metropolis sampling on fixed-cardinality subsets>.
Back to article page
