# 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.

• I doubt you will find a direct simulation method for this Ising-like distribution. E.g., the normalisation constant is most likely intractable. – Xi'an Mar 7 '16 at 16:12
• The problem I'm facing with a Gibbs sampler is that the probability mass function is quite rough such that the sampler gets stuck in local equilibria. I'll have a look whether I can find an "annealed" Gibbs sampler to do the job. – Till Hoffmann Mar 7 '16 at 17:28

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).