Particiones aleatorias con probabilidades de pertenencia por pares prescritas

Question

Sea $(p_{ij}) \in [0,1]^{n \times n}$ sea una matriz simétrica dada, con $1$ en la diagonal. Supongamos que $\pi$ es una partición de $[n]=\{1,\dots,n\}$ y escribamos $i \stackrel{\pi}{\sim} j$ si $i$ y $j$ pertenecen al mismo componente de $\pi$ .

¿Existe una partición aleatoria $\pi$ tal que $\mathbb{P}( i \stackrel{\pi}{\sim} j ) = p_{ij}$ para todos $i \neq j$ ?

En otras palabras, dada una matriz $(p_{ij})$ ¿existe una distribución en particiones de $[n]$ con la propiedad anterior y, en caso afirmativo, ¿hay alguna forma de muestrear a partir de dicha distribución? Además, suponiendo que exista, ¿es única?

EDIT: Como se ha señalado, no todas esas matrices producen una distribución. Pero ¿cuáles son las condiciones de $(p_{ij})$ que permita dicha distribución?

Answer 1

En $p \in \mathbb R^{n(n-1)/2}$ correspondientes a las distribuciones sobre las particiones forman un politopo convexo, cuyos puntos extremos corresponden a particiones individuales. No sé si hay una forma sencilla de caracterizar las caras de este politopo en general.

Para $n=3$ el politopo es el casco convexo de $[0,0,0], [1,0,0],[0,1,0],[0,0,1], [1,1,1]$ y ésta es la intersección de los semiespacios $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$ y $-p_{12} + p_{13} + p_{23} \le 1$ .

Para $n=4$ si mi programación es correcta, hay $22$ semiespacios: además de los seis $p_{ij} \ge 0$ y los doce $p_{ij} + p_{ik} - p_{jk} \le 1$ hay cuatro de la forma $\sum_{\{j,k\}: i \in \{j,k\}} p_{jk} - \sum_{\{j,k\}: i \notin\{j,k\}} p_{jk} \le 1$ , $i = 1 \ldots 4$ .