= Metropolis sampling on fixed-cardinality subsets
{c}
{title2=$q(v\mid u)=\mathbf1_{\{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.
Back to article page
