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.
No comments:
Post a Comment