Distribution on permutations derived from probability of pairwise orderings - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:29:20Z http://mathoverflow.net/feeds/question/27245 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27245/distribution-on-permutations-derived-from-probability-of-pairwise-orderings Distribution on permutations derived from probability of pairwise orderings David R. MacIver 2010-06-06T15:13:31Z 2010-06-07T02:51:49Z <p>A followup question to <a href="http://mathoverflow.net/questions/26166/probability-estimates-for-pairwise-majority-votes" rel="nofollow">Probability estimates for pairwise majority votes</a> - 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. :-)</p> <p>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> <p>P is a $N \times N$ matrix with P > 0 and <code>$P_{ij} = 1-P_{ji}$</code>. Define a random variable $T$ taking values in $S_N$ (the permutations of $1, \ldots, N$) by </p> <p><code>$P(T = \sigma) \propto \prod_{\sigma(i) &lt; \sigma(j)} P_{ij}$</code></p> <p>For fixed i, j I'd like to calculate $P(T(i) &lt; T(j))$.</p> <p>It's clear that this can't simply be <code>$P_{ij}$</code>: If you have e.g. <code>$P_{12} = P_{23} = P_{31} = 0.9$</code> then $P(T(1) &lt; T(2)) = 0.5$. </p> <p>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. </p> <p>One thing worth noting is that if we let <code>$R_{ij} = P(T(i) &lt; T(j))$</code> then for all k we have the constraint</p> <p><code>$R_{ik} \geq R_{ij} + R_{jk} - 1$</code></p> <p>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 <code>$R_{ij} = 1 - R_{ji}$</code>) which minimises some distance function from P. </p> http://mathoverflow.net/questions/27245/distribution-on-permutations-derived-from-probability-of-pairwise-orderings/27273#27273 Answer by Suresh Venkat for Distribution on permutations derived from probability of pairwise orderings Suresh Venkat 2010-06-06T21:23:53Z 2010-06-07T02:51:49Z <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) &lt; 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. </p> <p>This is your classic sum-of-products, with an exponential number of terms in the sum. I'd guess that the problem would be <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3ASymbols#sharpp" rel="nofollow">#P</a>-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). </p> <p><strong>Update</strong>: In response to your comment (I ran out of space in the comment field), there are two slightly half-assed things I can suggest: </p> <ol> <li>You might want to start with <a href="http://en.wikipedia.org/wiki/Junction_tree_algorithm" rel="nofollow">junction-tree</a> 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. </li> <li>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 <a href="http://portal.acm.org/citation.cfm?id=1008731.1008738" rel="nofollow">approximate the permanent</a>. That's highly nontrivial though. This article reviews some of the literature an</li> </ol>