# Distribution on permutations derived from probability of pairwise orderings

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.

-

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.