Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
1  
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
1  
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. Thank you. Do you know a reference for the lower bounds on expected f-distance? –  user32786 Apr 25 '13 at 6:29
1  
@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

1 Answer 1

This is not a complete answer and may not tell you anything you don't already know, but it's too long for a comment.

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$;
  2. one by one, go through the symbols 'e' and either change the symbol immediately before it, delete the symbol immediately before it, or insert a symbol immediately before it, and then delete the 'e'.

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.

share|improve this answer
    
Thank you. Maybe this questions turns out to be surprisingly hard. –  user32786 Apr 25 '13 at 19:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.