Sampling a random binary matrix with "Gaussian" probability distribution Let $A_{ij}$ be a $n\times n$ random binary matrix with probability mass function $P(A)$ given by
$$
\log P(A)=-\frac 12 \mathrm{tr}\left[\left(A-M\right)^TV\left(A-M\right)\right] + C,
$$
where $M$ and $V$ are also $n\times n$ matrices, $\mathrm{tr}$ denotes the trace of a matrix, $A^T$ is the transpose of $A$, and $C$ is a normalisation constant.
If $A$ was a real matrix, it would follow a matrix normal distribution and could be sampled easily. However, $A$ is a binary matrix in this problem. Is the above a known distribution? Is it possible to draw samples from it efficiently? I would like to avoid sampling the matrix using a Gibbs sampler.
 A: The target probability mass function is of the form
$$\begin{align}p(A)&\propto \exp\left\{-\frac 12 \mathrm{tr}\left[\left(A-M\right)^TV\left(A-M\right)\right]\right\}\\
&\propto \exp\left\{-\frac 12 \sum_{ij}(a_{ji}-\mu_{ji})\sum_{k} v_{jk} (a_{ki}-\mu_{ki})\right\}\\&\propto \exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ijk}v_{jk}a_{ji}\mu_{ki}+\frac 12 \sum_{ijk}v_{jk}\mu_{ji}a_{ki}\right\}\\
&\propto\exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ij}a_{ji}\left[\sum_k v_{jk}\mu_{ki}+ \sum_k v_{kj}\mu_{ki}\right]\right\}\\&\propto\exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ij}a_{ji}\sum_k \left[v_{jk}+ v_{kj}\right]\mu_{ki}\right\}\end{align}$$
if $M=(\mu_{ij})_{ij}$ and $V=(v_{ij})_{ij}$. It is therefore exactly an Potts model over $\{0,1\}^{n\times n}$ and there is no known exact simulation method (apart from perfect sampling).
Simulation by Gibbs sampling of the Potts model may indeed be quite slow. Accelerating techniques are the Swendsen–Wang algorithm, the Wolff algorithm and parallel tempering.
