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. 
 A: 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

