Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that

$$f(i, j) \cdot f(j, k) \le f(i, k)$$

For all $1 \le i, j, k \le n$.

Does there exist a randomized algorithm $A(X, f)$ that outputs permutations of $X$, such that if $\le_A$ is the total order defined by one such output permutation, we have $P(x_i \le_A x_j) = f(i, j)$? ($\le_A$ here is a random variable.)

That is, the permutations that $A$ outputs have a probability proportional to the pairwise probabilities defined by $f$. I believe this implies the probability of a permutation is, in fact, the product of these pairwise probabilities.

We have a special case, where $X$ is already a totally ordered set, and $f(i, j) = \delta_{x_i \le x_j}$, then $A$ is any sorting algorithm. Can this be done for any such $f$ as described? If not, what other requirements does one need? Finally, is there an efficient such $A$?

  • $\begingroup$ Your condition is not even sufficient for $n=1$, you should refine it a bit. $\endgroup$
    – domotorp
    Feb 12, 2015 at 7:12
  • $\begingroup$ A bit related result is the [Birkhoff–von Neumann theorem][1]. [1]: en.wikipedia.org/wiki/Doubly_stochastic_matrix $\endgroup$
    – domotorp
    Feb 12, 2015 at 7:12
  • $\begingroup$ Do you also need to add all the high-order transitivity conditions? e.g. $f(i,j)\cdot f(j,k) \cdot f(k,l) \leq f(i,l)$. $\endgroup$
    – usul
    Feb 12, 2015 at 14:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.