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

<p>$$f(i, j) \cdot f(j, k) \le f(i, k)$$</p>

<p>For all $1 \le i, j, k \le n$.</p>

<p>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.)</p>

<p>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.</p>

<p>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 <em>efficient</em> such $A$?</p>

CC BY-SA 3.0
2015-02-12T07:12:06.170Z
Your condition is not even sufficient for $n=1$, you should refine it a bit.
domotorp
CC BY-SA 3.0
2015-02-12T07:12:22.840Z
A bit related result is the [Birkhoff–von Neumann theorem][1].



  [1]: http://en.wikipedia.org/wiki/Doubly_stochastic_matrix
domotorp
CC BY-SA 3.0
2015-02-12T14:24:05.900Z
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)$.
usul
<pr.probability><randomized-algorithms><sorting>
Probabilistic sorting given pairwise comparison probability
Federico Lebrón
# Probabilistic sorting given pairwise comparison probability

(Asked by: username_0 on 2015-02-12)

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$?

**Tags:** pr.probability, randomized-algorithms, sorting

> **Comments:**
> **username_1**: Your condition is not even sufficient for $n=1$, you should refine it a bit.  
> **username_1**: A bit related result is the [Birkhoff–von Neumann theorem][1].      [1]: http://en.wikipedia.org/wiki/Doubly_stochastic_matrix  
> **username_2**: 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)$.  

---

## 0 answers

