The Levenshtein or edit distance between two strings is the minimum number of edits (adding a letter, removing a letter or changing a letter) required to transform one into the other.
Assume that we have two strings, each of size $n$ and that consist of letters drawn uniformly IID from an alphabet of $k$ letters. What is the (possibly approximate) distribution of their Levenshtein distance?
This can be seen as an extreme value problem since the Levenshtein distance is the minimum number of mismatches over all the possible ways to align the two sequences. For an alignment chosen randomly among those with $m$ insertions and $m$ deletions, the number of mismatches has a Binomial distribution with parameters $n-m$ and $1-1/k$, so it is tempting to compute the distribution of the minimum of all those Binomial variables (as in this question), but in this case, the Binomial variables are not IID.
A solution to this problem would be useful in biology (where $k=4$ in the case of DNA sequences) because it would give the statistical properties of the alignment between unrelated sequences.