Distribution of Levenshtein distances for partially sorted lists I have a partially sorted list of distinct items and want to know the probability of this occurring by happenstance rather than intent.
The Levenshtein distance is a good metric for the problem domain.
What is needed is the probability distribution of Levenshtein distances for partially sorted lists compared to a fully sorted list.
A search has turned up one related paper, but this applies to the case of the alphabet size being much shorter than the list size.  For my problem the alphabet size is the same as the list length.
More exactly: Two lists, $L_1$ and $L_2$ where the elements in $L_1$ are sorted and $L_2$ contains the same elements as $L_1$ in some order. Compute the Levenshtein distance between $L_1$ and $L_2$ where $L_2$ takes on all possible permutations of the elements in $L_1$. Given this set of distances I can plot Levenshtein distance against the number of permutations having a given distance, this is the distribution I am after.
My lists are short'ish, around 20 or so items, so with some work all distances might be enumerated (there are some obvious optimizations to speed up the $n^2$ algorithm when permuting through the set of partially sorted lists).  The work could be reduced further by only considering versions of $L_2$ having elements that are, say, 90% sorted relative to $L_1$.
 A: The probability distribution of Levenshtein in the general case appears to be an open problem. If you are willing to use an approximation, you can use Monte Carlo simulation to generate the distribution under random sorting. Specifically, your simulation would begin with a sorted list; then randomly substitute, insert, or delete items; then compute the Levenshtein distance between the original and randomized list; and repeat over thousands of iterations. The proportion of iterations where Levenshtein $= d$ is the probability of obtaining that distance by chance.
The difficulty in this approach is in defining simulation parameters: number of substitutions, insertions, and deletions each; positions in the list where they occur; letters of the alphabet inserted or substituted. If we consider only the first parameter, and if we assume no more than $j$ operations ($x$ substitutions + $y$ insertions + $z$ deletions $= j$ operations) are performed on the original list, then the total number of ways the list can be randomly sorted using these three operations is $3^{j}$ + $3^{j - 1}$ + $3^{j - 2}$ + ... + $3^1$ + $3^0$). That quickly becomes a very large number of cells when j is not very small (e.g., 88,573 cells for $j = 10$), and a comprehensive simulation would have, say, $10,000$ reps or so per cell. Multiply that by the number of (nested) cells of the other two simulation parameters and it's apparent why the problem has not been solved mathematically.
Granted, there are simplifying assumptions that may be appropriate for your particular scenario, and you could sample cells probabilistically rather than simulating all conditions. But every step away from the complete simulation results in a rougher approximation of the answer you want.
Alternatively, you could use a version of the Hamming distance metric, which is much simpler because it allows substitutions only. Hamming is only truly appropriate under two assumptions: 1. each list is a permutation of exactly n distinct items (i.e., the number of letters in the alphabet equals n and every letter in the alphabet appears exactly once in each list), and 2. the mechanism that produces the partially-sorted list from the sorted list consists entirely of substitutions. Obviously, the second assumption is violated if, as in the Levenshtein distance, the sorting mechanism also involves insertions and deletions. However, even then, you may find that insertions and deletions are sufficiently rare that the impact of the violation is negligible, or that the degree of error in your answer is worth not using the more complex edit distance.
The "version" of Hamming referred to above is an obscure correlation statistic called the matching statistic or $m$. $m$ is equal to the number of matches between permuted lists, or $n$ minus the Hamming distance. When the two assumptions above hold, $m$ is distributed asymptotically $Poisson$ with parameter $1$ if the new list is just a random permutation of the original. This means the probability of getting a partially-sorted list with $k$ entries in their original positions (or $n - k$ in new positions) by chance is equal to the probability of drawing the value $k$ at random from a $Poisson(1)$ distribution. The approximation to $Poisson(1)$ improves rapidly with increasing $n$, and it's quite close with as few as four items.
Citations for m:
Vernon, P. E. (1936). The matching method applied to investigations of personality. Psychological Bulletin, 33(3), 149.
Vernon, P. E. (1936). The evaluation of the matching method. Journal of Educational Psychology, 27(1), 1.
