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!



Drawing random variates from a partially described probability distribution
Joris, 


So we assume we know only the marginals $p(x\_i)$ and the probabilities that $p(x\_i=x\_j)$. In terms of the physics' "spin" notation, $s\_i=\pm 1$, this means that we know $\left<s\_i \right> \equiv \sum\_{s\_i} s\_i p(s\_i)$ and $\left<s\_i s\_j \right> \equiv \sum\_{s\_i s\_j} s\_i s\_j p(s\_i,s\_j)$.


There are many different joint probability distributions $p(s) \equiv p(s\_1, \ldots, s\_N)$ that have these single node and pairwise statistics. Indeed Egosphere only asks for *some* distribution.


One common approach to model distributions with partial knowledge in the form of constraints is to consider a special distribution, namely the maximum entropy (maxent) distribution.


Here, the maxent distribution $p^\*(s)$ maximizes the entropy
$$
H = -\sum\_{s} p^\*(s) \log p^\*(s)
$$
 under the constraints $$\sum\_{s\_i} s\_i p^\*(s\_i) = \left<s\_i \right> \forall i~\mbox{and}~ \sum\_{s\_i s\_j} s\_i s\_j p^\*(s\_i,s\_j) = \left<s\_i s\_j \right> \forall i<j.$$ 
Using Lagrange multipliers $w = \{w\_i, w\_{ij} \}$, it can be shown that this distribution has the following parametrized form
$$p(s|w) = \frac{1}{Z(w)} \exp(\sum\_i w\_i s\_i + \sum\_{i<j} w\_{ij} s\_{i} s\_{j})$$
Such a distribution is known as a "Boltzmann Machine" (BM). The parameters $w$ are called weights.


The maxent distribution $p^\*(s)=p(s|w^\*)$ has optimal weights $w^\*$, which are such that the constraints are satisfied:
$$\left<s\_i \right>\_{w^\*} = \left<s\_i \right> ~\mbox{and}~\left<s\_i s\_j \right>\_{w^\*} = \left<s\_i s\_j \right>,$$
with notation $\left< s\_i \right>\_w \equiv \sum\_{s\_i} s\_i p(s\_i|w)$ etc.


These constraint equations can also be interpreted as the stationary equations $\nabla L(w) = 0$ of the loglikelihood $$L(w) = \sum\_s p(s) \log p(s|w),$$ which can be written equivalently as $$L(w) = \sum\_i w\_i \left<s\_i \right> + \sum\_{i<j} w\_{ij} \left<s\_i s\_j \right> - \log(Z(w)).$$ As a consequence, weights can be found by maximizing $L(w)$. E.g. gradient ascent leads to the well known Boltzmann Machine learning rule.
$$
\Delta w\_i = \eta \frac{\partial}{\partial w\_i} L(w) = \eta (\left<s\_i \right>-\left<s\_i \right>\_w)
$$
and
$$
\Delta w\_{ij} = \eta \frac{\partial}{\partial w\_{ij}} L(w) = \eta( \left<s\_i s\_j \right>-\left<s\_i s\_j \right>\_w)
$$
The optimal weights are unique because $L(w)$ is concave. To see this, consider the matrix of second derivatives of $\log Z(w)$. This matrix has the form of a covariance matrix, which is positive definite. Therefore $\log Z(w)$ is convex and $L(w)$ is concave. However, finding the optimal $w^\*$ can still be demanding since the computation of e.g. $\left<s\_i \right>\_w$, $\left<s\_i s\_j \right>\_w$ or $Z(w)$ require the summation over exponentially many states.


Sampling from a BM can be done by e.g. Gibbs sampling. The nice thing with Gibbs sampling in BM is that computing a probability of a single spin $s\_i$ given the others $s\_{\{j \neq i\}}$ is computationally cheap
$$
p(s\_i | s\_{\{j \neq i\}}) \propto \exp( (w\_i + \sum\_{j < i} w\_{ji} s\_j + \sum\_{j>i} w\_{ij} s\_j ) s\_i ) 
$$


An introductory page about BMs is e.g. <http://www.scholarpedia.org/article/Boltzmann_machine>


An interesting reference about the duality between statistics $\{\left<s\_i \right>\_w, \left<s\_i s\_j \right>\_w\}$ and weights $\{w\_i, w\_{ij}\}$ is chapter 3 in
M. J. Wainwright and M. I. Jordan (2008). Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, Vol. 1, Numbers 1--2, pp. 1--305, December 2008 


I hope this is of some use,


Wim 


