I have a probability distribution over $\{0,1\}^n$ but instead of knowing the full joint distribution $p(x_1,\dots,x_n)$, I only know $p(x_i=x_j)$ for each $i,j$. How could I draw a random binary vector $x$ from *some* distribution that has these marginals? Since $n$ is large I would rather not search over all distributions (in the $(2^n-1)$-dimensional simplex) to find one that matches (this can be hard even though by Caratheodory's theorem there is such a distribution with support only $\binom n 2$, because what's in the support is not known). Hopefully there's a more efficient method if all I want to do is draw a random variate.

Thanks!