5
$\begingroup$

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?

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks. I wonder how you wrote a computer program for it. I mean is there a way to enumerate all these half-spaces in general. $\endgroup$
    – passerby51
    Feb 5, 2015 at 19:01
  • 1
    $\begingroup$ My program was rather unsophisticated: just look at all possible sets of $n+1$ vertices and see which generate faces. For larger $n$, you might look at polymake.org/doku.php $\endgroup$ Feb 6, 2015 at 1:35
2
$\begingroup$

There are many more partitions than there are pairs for large enough $n$, so rank-nullity says uniqueness will fail. $\frac12 (12) + \frac12 (34) \sim \frac12 (12)(34) + \frac12 e$ where we identify permutations with their cycle decompositions.

$\endgroup$
1
  • 1
    $\begingroup$ Haven't seen that notation before but I guess it means $\mathbb P(X=\sigma)=\frac12 \mathbf 1_{\{(12)\}}(\sigma)+\frac12 \mathbf 1_{\{(3,4)\}}(\sigma)$. $\endgroup$ Feb 2, 2015 at 16:58
1
$\begingroup$

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?

No; $ p_{1,2}=p_{1,3}=1$ implies $p_{2,3}=1$.

$\endgroup$
1
  • $\begingroup$ OK... fair enough. Transitivity puts some restrictions. But can we make those restrictions precise. I have edited the question. $\endgroup$
    – passerby51
    Feb 2, 2015 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.