12
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Can you clarify exactly what you mean by "entropy of the edit distance"? $\endgroup$
    – Vaughn Climenhaga
    Commented Apr 24, 2013 at 13:17
  • $\begingroup$ @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. $\endgroup$
    – user32786
    Commented Apr 24, 2013 at 13:23
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Anthony Quas
    Commented Apr 24, 2013 at 20:19
  • 1
    $\begingroup$ @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$. $\endgroup$
    – user32786
    Commented Apr 26, 2013 at 10:01
  • 1
    $\begingroup$ I'd still would like to know the definition or a link to a definition of "entropy of the edit distance". $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 17, 2014 at 6:50

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you. Maybe this questions turns out to be surprisingly hard. $\endgroup$
    – user32786
    Commented Apr 25, 2013 at 19:05

You must log in to answer this question.