 Solution

Each state has exactly $k(n-k)$ neighbours: choose one occupied coordinate and one unoccupied coordinate to swap. The normalized proposal distribution is thereforeThe 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 ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^{-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 givesConsequentlyThe 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 toOnly two rows and four entries of $Q$ are needed for this evaluation. This is Metropolis sampling on fixed-cardinality subsets.