Distribution on permutations derived from probability of pairwise orderings - MathOverflow

Distribution on permutations derived from probability of pairwise orderings

2010-06-06T15:13:31Z

A followup question to Probability estimates for pairwise majority votes - I think it doesn't actually give an answer in any terribly precise sense, but it would give something I'd be happy to use in lieu of one. :-)

I'm basically looking at a certain class of distribution of permutations and trying to determine the probability of it putting two items in a given order. I suspect I'm treading on well worn ground here, but haven't been able to find anything.

P is a $N \times N$ matrix with P > 0 and $P_{ij} = 1-P_{ji}$ . Define a random variable $T$ taking values in $S_N$ (the permutations of $1, \ldots, N$) by

$P(T = \sigma) \propto \prod_{\sigma(i) < \sigma(j)} P_{ij}$

For fixed i, j I'd like to calculate $P(T(i) < T(j))$.

It's clear that this can't simply be $P_{ij}$ : If you have e.g. $P_{12} = P_{23} = P_{31} = 0.9$ then $P(T(1) < T(2)) = 0.5$.

Unfortunately it's not clear to me what a general solution should look like. I suspect there may be no nice closed form solution, so I'd be happy with a reasonably efficient way to calculate a numeric approximation.

One thing worth noting is that if we let $R_{ij} = P(T(i) < T(j))$ then for all k we have the constraint

$R_{ik} \geq R_{ij} + R_{jk} - 1$

I suspect but haven't yet been able to prove that if P satisfies this constraint then P = R. If this is the case then it seems likely that R can be calculated as a solution to these constraints (plus that $R_{ij} = 1 - R_{ji}$ ) which minimises some distance function from P.

Answer by Suresh Venkat for Distribution on permutations derived from probability of pairwise orderings

2010-06-06T21:23:53Z

In an indirect way, this related to graphical models and the problem of estimating events in a given model. Your matrix yields a digraph with parallel edges between each pair of nodes $(i,j)$ labelled $P_{ij}$ and $P_{ji} = 1 - P_{ij}$. Now pick any two nodes $i,j$. The probability of the event $T(i) < T(j)$ has to be summed over all DAGs induced by the sampling process in which $T(i)$ is before $T(j)$ in the topological (and total) order.

This is your classic sum-of-products, with an exponential number of terms in the sum. I'd guess that the problem would be #P-hard (i.e intractable to estimate) unless there's some deeper structure that one can assume or exploit (for example, in how graphical model estimation is easy if a related graph has bounded treewidth).

Update: In response to your comment (I ran out of space in the comment field), there are two slightly half-assed things I can suggest:

You might want to start with junction-tree like methods to get some ideas for what a convergent procedure might look like. While they are different problems, my suspicion is that much of the problem structure is similar.
On the theory side, even if the problem is intractable, you might be able to get an approximate answer (with guarantees) using similar ideas (or even a reduction) to the method used to approximate the permanent. That's highly nontrivial though. This article reviews some of the literature an