Sorting in a probabilistic order

Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.

• The question isn't well-defined. It's not clear exactly which algorithms are permissible (considered correct). It's not clear what it means for one permutation to be "more sorted" than another. You also don't say anything about how much more likely it is for i to be placed before j. Can you define precisely what distribution you want the output of the algorithm to have, or what class of distributions are acceptable? – D.W. Apr 11 '17 at 20:37
• The Mallows model (with respect to Kendall's tau distance) is a probabilistic model that satisfies your properties. See for example a paper of Lu and Boutilier. – Yuval Filmus Apr 12 '17 at 0:19
• @D.W. I left these questions unanswered on purpose. This problem is posed to us as part of an experiment that we are running; any "useful" definition of the properties you named is considered valid. – Andreas T Apr 12 '17 at 20:06
• @YuvalFilmus Thanks for the link. It seems to me that this might be an overkill though? It is hard to tell since the only reference to "Mallows model" that I can find is that very same paper. Is it known under another name? – Andreas T Apr 12 '17 at 20:08
• @AndreasT Unfortunately I'm not aware of the history, but sampling from this distribution is pretty easy. All you have to do is sample several truncated geometric random variables. Not sure what you mean by "overkill". – Yuval Filmus Apr 12 '17 at 20:18

One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0 < \phi \leq 1$:

2. Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.
3. Insert 3 into positions 1,2,3 with probabilities $\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.
4. Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the PlackettLuce model from 1959. There are other models, for example Tallis–Dansie.

The expected running time of quicksort with random pivot is actually $O(n\log n)$.

One can show that you cannot achieve better expected runtime, by any randomized algorithm that correctly sorts any list of $n$ elements. This is shown by Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

This gives you the power to, instead of considering coin tossing algorithms, fix some input distribution, and ask what is the best expected running time of any deterministic algorithm relative to that distribution (i.e. it relates randomize complexity to distributional complexity).

Now, since we can fix any distribution, you can look at the uniform distribution over all possible inputs, and ask what is the best expected running time a deterministic algorithm achieves, relative to the uniform distribution. A lower bound proof in this setting is closer in spirit to the regular lower bound proof for deterministic sorting that you know, you can find it in the following lecture notes.

The idea is similar, you consider a comparison based sorting algorithm as a binary tree, where each node is a query of the form $x<y$, and each leaf in the tree represents a different permutation. The number of comparisons required to sort some input $a_1,...,a_n$ is given by the height of the leaf corresponding to the sorted permutation $a_{i_1},...,a_{i_n}$. Since the number of leaves is $n!$, you know the depth is $\Omega(n\log n)$. The difference in the distributional case is that you need to bound the average leaf height of a binary tree with $n!$ leaves (not the depth). Now, proceed to show that the average leaf height is minimized by a balanced binary tree, in which the average leaf height is $\Omega(\log n!)$. To see why you can focus on balanced trees, show that if the tree is unbalanced somewhere, you can "fix it", and this operation only decreases average leaf height.

I only dealt with algorithms that correctly sort all inputs, but using Yao's principle for Monte-Carlo algoirthms, you can extend this to your case.

• Sorry, I do not understand what your overall message is. Are you saying that a lower bound of the problem is $\Omega(n \log n)$? – Andreas T Apr 11 '17 at 16:21
• Yep (the key point being that it also holds in the probabilistic setting) – Ariel Apr 11 '17 at 17:20
• I don't understand how this relates to the question. The question doesn't ask for an algorithm to sort the input list; but for an algorithm to output a permutation of the list that has certain (vague) properties. Thus, depending on what exactly the required properties are, it seems like it might be possible to produce an algorithm that meets the requirement without sorting the input elements into increasing order of $i$, or without sorting. Does your proof take this into account? I can't quite tell. Also I can't tell why it is reasonable to focus only on deterministic algorithms. – D.W. Apr 11 '17 at 20:39
• Well, I interpreted the question as "I have randomness, how can I use it to sort faster". The answer discussed randomized algorithms who correctly sort every input, but as I mentioned in the last line it can be generalized to algorithms who allow non sorted output with small constant probability. The discussion on deterministic algorithm followed the use of Yao's principle, exchanging randomized algorithms with deterministic ones relative to some input distribution. – Ariel Apr 11 '17 at 22:21
• @D.W. I did miss the "sortedness measure" part of the question. cs.stackexchange.com/questions/11836/how-to-measure-sortedness might be a better fit – Ariel Apr 11 '17 at 22:33