26
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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$)? $\endgroup$ Apr 27, 2013 at 17:15
  • 1
    $\begingroup$ Is it obvious that the limit exists? $\endgroup$ Apr 27, 2013 at 18:29
  • 1
    $\begingroup$ @Sam Hopkins: I would think so, since $E_n\leq n$ for all $n$. $\endgroup$ Apr 27, 2013 at 18:56
  • 8
    $\begingroup$ 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). $\endgroup$ Apr 27, 2013 at 20:31
  • 2
    $\begingroup$ I would add the Computer Science tag. Edit distance is studied mostly there and would increase the chances to be noticed... $\endgroup$ May 14, 2013 at 22:19

3 Answers 3

11
$\begingroup$

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)

$\endgroup$
6
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – user32786
    Apr 27, 2013 at 18:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – user32786
    Apr 27, 2013 at 22:17
  • $\begingroup$ I mean $\mathbb{E}(E_n)/n$ is a decreasing function of $n$ of course. $\endgroup$
    – user32786
    Apr 28, 2013 at 16:26
  • 1
    $\begingroup$ 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? $\endgroup$
    – cardinal
    Apr 30, 2013 at 12:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – user32786
    Apr 30, 2013 at 19:29
10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 6, 2013 at 0:09
  • 1
    $\begingroup$ @fedja Don't you also need a factor of $2^k$ to account for the different strings that may be inserted? $\endgroup$ Jul 9, 2018 at 6:29
  • $\begingroup$ @ThomasDybdahlAhle Looks like you are right. This moves the estimate down by some amount but still gives something :-) $\endgroup$
    – fedja
    Jul 10, 2018 at 1:35
2
$\begingroup$

I did some simulations myself, (5000 of each string length 1-1000) and thought I would share them here. They are plotted against Carlo's conjectured bound of $1-1/\sqrt{2}$ (in blue).

To me, the conjecture seems quite likely, since the smallest average distance I get is 0.296 at $n=1000$. enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy