Let $(p\_{ij}) \in [0,1]^{n \times n}$ be a given symmetric matrix, with $1$ on the diagonal. Suppose $\pi$ is a partition of $[n]=\{1,\dots,n\}$ and let us write $i \stackrel{\pi}{\sim} j$ if $i$ and $j$ belong to the same component of $\pi$.


Is there a random partition $\pi$, such that $\mathbb{P}( i \stackrel{\pi}{\sim} j ) = p\_{ij}$ for all $i \neq j$? 


In other words, given a matrix $(p\_{ij})$, is there a distribution on partitions of $[n]$ with the above property, and if so is there a way to sample from such distribution? Also, assuming existence, is it unique?


EDIT: As has been pointed out, not all such matrices produce a distribution. But what are the conditions on $(p\_{ij})$ that allows for such distribution?



Random partitions with prescribed pairwise membership probabilities
The $p \in \mathbb R^{n(n-1)/2}$ corresponding to distributions on partitions form a convex polytope, the extreme points of which correspond to individual partitions. I don't know if there's a simple way to characterize the faces of this polytope in general. 


For $n=3$ the polytope is the convex hull of
$[0,0,0], [1,0,0],[0,1,0],[0,0,1], [1,1,1]$, and this is the intersection of the half-spaces $p\_{12} \ge 0$, $p\_{13} \ge 0$, $p\_{23} \ge 0$, $p\_{12} + p\_{13} - p\_{23} \le 1$, $p\_{12} - p\_{13} + p\_{23} \le 1$, and $-p\_{12} + p\_{13} + p\_{23} \le 1$.


For $n=4$, if my programming is correct, there are $22$ half-spaces:
in addition to the six $p\_{ij} \ge 0$ and the twelve $p\_{ij} + p\_{ik} - p\_{jk} \le 1$, there are four of the form $\sum\_{\{j,k\}: i \in \{j,k\}} p\_{jk} - \sum\_{\{j,k\}: i \notin\{j,k\}} p\_{jk} \le 1$, $i = 1 \ldots 4$.


