# Entropy of edit distance

The edit or Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions to transform one string into another. If we take random binary strings $A$ and $B$ of the same length $n$, is it known what the entropy of the edit distance between $A$ and $B$ is?

Update. I would be happy with a proof that the entropy is asymptotically $c \log n$ for some (unknown) $c>0$ as suggested by Anthony Quas (or even $(\Theta(\log{n})$ which potentially saves having to prove convergence).

• Can you clarify exactly what you mean by "entropy of the edit distance"? – Vaughn Climenhaga Apr 24 '13 at 13:17
• @VaughnClimenhaga If $A$ and $B$ are random variables (in this case over random binary strings) then the edit distance between $A$ and $B$ will also be a random variable with some distribution. As another example, if we are interested in the Hamming distance rather than the edit distance then the entropy of the Hamming distance is $H(B(n,1/2))$ which is known. – user32786 Apr 24 '13 at 13:23
• This is also known in ergodic theory as the $\bar f$-distance. There are known linear lower bounds on the expected $\bar f$-distance between random strings of length $n$, so treating the $\bar f$ distance as a random variable, it will presumably be a unimodal distribution whose standard deviation is a power of $n$. Hence the entropy of this random variable will be approximately of the form $c\log n$. – Anthony Quas Apr 24 '13 at 20:19
• @AnthonyQuas I found a definition of $\bar{f}$-distance on page 3 of univ-rouen.fr/LMRS/Persopage/Janvresse/Publi/… . However this is the length of the longest common subsequence (essentially) not $n$ minus the edit distance I think. Those values can be arbitrarily far apart. Take for example two strings $00001111$ and $11110000$. The LCS length is $n/2$ and $n$ minus the edit distance is $0$. – user32786 Apr 26 '13 at 10:01
• I'd still would like to know the definition or a link to a definition of "entropy of the edit distance". – Włodzimierz Holsztyński Feb 17 '14 at 6:50

You can get an estimate on the number of words at an edit distance of $k$ from a given word of length $n$ by using the arguments in the proof of Lemma 2.6 in this paper. (The lemma is on page 10 and its proof is on page 28.)
The idea is that if a word $w$ is at an edit distance of $k$ from a word $v$, then one can get from $v$ to $w$ via the following steps:
1. insert $k$ copies of the symbol 'e' (for 'edit') into the word $v$;
Step 1 gives a word of length $n+k$ with $k$ occurrences of the symbol 'e', so there are ${n+k\choose k}$ possibilities after this step. Then step 2 gives at most $3^k$ possible words for each of those possibilities, so for a fixed word $v$ of length $n$ one obtains the bound $$\#\{w \mid \text{edit distance from v to w is k}\} \leq 3^k {n+k \choose k}.$$ For small $k$ this is a reasonable bound; in particular when $k\ll n$ this is not much larger than ${n\choose k}$, the number of words a Hamming distance of $k$ away. The problem is that for larger values of $k$ the procedure described above succumbs to a lot of overcounting, so it's not clear what the actual bound should be.