Metropolis sampling on fixed-cardinality subsets ($q(v\mid u)=1_{\{v\sim u\}}/[k(n-k)]$)

Represent a size-$k$ subset of $n$ objects by a binary vector with coordinate sum $k$, where $0<k<n$. Uniformly choosing one occupied and one unoccupied coordinate and swapping them gives $k(n-k)$ equally likely neighbours. This proposal distribution is symmetric, so its forward and reverse factors cancel in the Metropolis–Hastings acceptance probability. Every state is connected to every other by a sequence of swaps, establishing an irreducible Markov chain when the target masses are positive. Symmetry and the acceptance rule give detailed balance with that target.

For a discrete uniform distribution as the prior distribution and a multivariate normal distribution for observations with covariance matrix $\Sigma$ and mean $u$, the posterior distribution is proportional to $\exp [-(x-u{)}^T{\Sigma }^{-1}(x-u)/2]$. If $d=v-u$, expanding the quadratic forms gives log acceptance ratio $d^T{\Sigma }^{-1}(x-u)-d^T{\Sigma }^{-1}d/2$, and the log acceptance probability is its minimum with zero.