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 symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{E}(01010,00100)=2.$$

Let $E_n$ be a random variable giving the edit distance between two random binary strings of length $n$.

What bounds can be found for

$$\lim_{n \to \infty} \frac{\mathbb{E}(E_n)}{n} = c\;?$$

According to my non-extensive simulations, $c \approx 0.288$.

There is related work by Luecker on the expected length of the longest common subsequence which has lower and upper bounds of $0.788071n$ and $0.826280n$. This was a line of work originally started by Chvatal and Sankoff. However the longest common subsequence length and $n$ minus the edit distance need not be similar.

share|improve this question
1  
Trying to understand the distance: $E(01010, 00100) = 2$ because $01010 \to 001010$ (insert $0$ inbetween first and second symbol) and $001010 \to 00100$ (remove the second $1$)? –  Michael Albanese Apr 27 '13 at 17:15
1  
Is it obvious that the limit exists? –  Sam Hopkins Apr 27 '13 at 18:29
1  
@Sam Hopkins: I would think so, since $E_n\leq n$ for all $n$. –  Carlo Beenakker Apr 27 '13 at 18:56
6  
The limit must exist because the expected edit distance is subadditive (we can always edit a string of length $m+n$ by editing each part separately). –  Kevin P. Costello Apr 27 '13 at 20:31
1  
I would add the Computer Science tag. Edit distance is studied mostly there and would increase the chances to be noticed... –  Dan Sălăjan May 14 '13 at 22:19
show 3 more comments

2 Answers

up vote 5 down vote accepted

The only rigorous bound I am aware of is due to Gonzalo Navarro*

$$c\geq 1-{\rm e}/\sqrt{\sigma},$$

for an alphabet of $\sigma$ characters. Obviously, for the binary string ($\sigma=2$) this bound is ineffective. Navarro also mentions a large-$\sigma$ conjecture $c=1-1/\sqrt{\sigma}$, which for the binary string would give $c=0.2929$, quite close to your numerical finding.

*G. Navarro, A guided tour to approximate string matching (2001)

share|improve this answer
2  
Thank you for the reference. For what it's worth, I don't believe the conjecture. I get a number just under $0.29$ for $n=2^{13}$. –  user32786 Apr 27 '13 at 18:24
1  
Perhaps I should have added that $E_n$ is a decreasing function of $n$. This is why my comment is meant to imply that the conjecture that $c=0.2929$ is (likely to be) wrong. –  user32786 Apr 27 '13 at 22:17
    
I mean $\mathbb{E}(E_n)/n$ is a decreasing function of $n$ of course. –  user32786 Apr 28 '13 at 16:26
    
Undoubtedly I am suffering from lack of sufficient coffee intake, but I don't follow the "rigorous bound". Isn't $c_n := \mathbb E(E_n) / n \leq 1/2$ trivially by either (a) comparing to the Hamming distance or (b) using the subadditive property that Kevin mentions in his comment above? –  cardinal Apr 30 '13 at 12:57
    
@cardinal The upper bound of $1/2$ is certainly true. And in fact given the subadditive property we can also use exhaustive computer solutions for finite $n$ to give even better upper bounds. I am not sure there is any proven lower bound so far however. –  user32786 Apr 30 '13 at 19:29
add comment

I am not sure there is any proven lower bound so far however.

This should really be a comment but it is too long.

A lot depends on how good lower bound you want. The trivial one can be obtained by just saying that if we have $k$ deletions, $k$ insertions, and $m$ substitutions, we can get just ${n\choose k}^2{n-k\choose m}$ new sequences from a given one. Now, if that is much less than $2^n$ for every $k,m$ with $2k+m < cn$, then the limit is at least $c$. Using the simple approximation $m!\approx m^me^{-m}$, we see that all we need is to ensure that $$ 2\mu\log\mu+(1-\mu)\log(1-\mu)+\nu\log\nu+(1-\mu-\nu)\log(1-\mu-\nu)>-\log 2 $$ whenever $2\mu+\nu\le c$, which (after some computations) yields $c>0.18$. Of course, this is very crude because it doesn't take into account the fact that the number of ways to convert one sequence into another within the edit distance is typically exponential in $n$ too.

share|improve this answer
    
You can tighten the bound slightly. The number of sequences with the given number of insertions, deletions and substitutions is less than you give because it doen't make sense to have an insertion next to a deletion. –  Carl Feynman May 6 '13 at 0:09
add comment

Your Answer

 
discard

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