Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance

The edit distance is a metric of dissimilarity between strings, widely applied in computational biology, speech recognition, and machine learning. Let ek(n) denote the average edit distance between random, independent strings of n characters from an alphabet of size k. This paper is concerned with the efficient computation of αk(n)=ek(n)/n as well as of αk=limn→∞αk(n). It is shown that αk(n)−Θ(logn/n)≤αk≤αk(n) and that αk is computable. An algorithm for the exact computation of αk(n) is presented with running time T=O(n2kmin(3n,kn)) thus, of limited practical use. An analysis of Monte Carlo estimates, based on McDiarmid’s inequality, shows how αk(n) can be evaluated with good accuracy and high confidence level, for rather large values of n. In particular, 99.9% confidence intervals of width approximately 10−2 are obtained for αk. An efficiently computable lower bound βk* to αk is derived, with limk→∞βk*=1. For k greater than a few dozens, significant bounds on αk can be obtained faster via βk* than by statistical methods. The above techniques yield improvements on most previous numerical estimates as well as results for alphabet sizes and string lengths not reported before.