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.