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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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$.

Improve this answer
$\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
    Commented 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$
    – Robert Israel
    Commented 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.

Improve this answer
$\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$
    – Bjørn Kjos-Hanssen
    Commented 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$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .