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!

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.

If it helps, assume that $p(x_i=0)=p(x_i=1)=0.5$ for all $i$.

Thanks!