Computable Bounds and Monte Carlo Estimates of the Expected Edit Distance

Gianfranco Bilardi, Michele Schimd

The edit distance is a metric of dissimilarity between strings, widely applied in computational biology, speech recognition, and machine learning. Let $e_k(n)$ denote the average e…