Average number of strings with edit distance exactly 2

Consider a binary string of length $$n \geq 2$$. An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed to transform one string into the other one. Given a string $$S$$, my question relates to the number of distinct strings of length $$n$$ which are edit distance $$2$$ from $$S$$.

Let us write $$f_2(S)$$ for the number of distinct strings of length $$n$$ which are edit distance $$2$$ from $$S$$.

Let $$X_n$$ be a random variable representing a random binary string of length $$n$$, with the bits chosen uniformly and independently. My question is what is:

$$\mathbb{E}(f_2(X_n))\;?$$

For small $$n$$ we can compute the value exactly:

• $$\mathbb{E}(f_2(X_2)) = 1$$.
• $$\mathbb{E}(f_2(X_3)) = 3 \frac{1}{4}$$.
• $$\mathbb{E}(f_2(X_4)) = 7 \frac{1}{8}$$.
• $$\mathbb{E}(f_2(X_5)) = 12 \frac{13}{16}$$.
• $$\mathbb{E}(f_2(X_6)) = 20 \frac{13}{32}$$.
• $$\mathbb{E}(f_2(X_7)) = 29 \frac{61}{64}$$.
• $$\mathbb{E}(f_2(X_8)) = 41 \frac{61}{128}$$.
• $$\mathbb{E}(f_2(X_9)) = 54 \frac{253}{256}$$.
• $$\mathbb{E}(f_2(X_{10})) = 70 \frac{253}{512}$$.

See What is the expected number of distinct strings from a single edit operation? for a related question about edit distance 1 which has a very clean and simple solution.

• Do you want the edit distance to be at most $2$ or exactly $2$? Commented Dec 27, 2019 at 11:19
• @J.-E.Pin Exactly $2$.
– user35671
Commented Dec 27, 2019 at 11:23
• @J.-E.Pin - The OP wants the final string to have the same length $n$ as the original string. So if you can solve that problem for at most $2$, it is easy to solve the problem for exactly $2$, since the distance $1$ case (while maintaining same length) can only come from substitutions, not insert/deletions. Commented Dec 27, 2019 at 19:42
• @Anush - how did you calculate the $E[f_2(X_n)]$ values? E.g. for $n=10$, did you loop through all $1024$ original strings, and for each string $x$, calculate $f_2(x)$? How did you calculate $f_2(x)$? Unless you do another loop (through $1024$ final strings), there must have been some formula you used. Can you share that formula? Commented Dec 27, 2019 at 19:44
• @Anush - darn, I was hoping to start with whatever formula you used :) but you used a double loop and tested for $dist(x,y)=2$... Commented Dec 27, 2019 at 20:53

Since you want the length to remain unchanged and $$2$$ to be the minimal edit distance, the only options are two substitutions in different places, or an insertion and a deletion. (It doesn't matter in which order we carry out the insertion and the deletion.) It's straightforward that there are $$\binom n2=\frac{n(n-1)}2$$ different results of two substitutions in different places, so the task is to count the strings produced by an insertion and a deletion that can't be produced by at most two substitutions.

Let's count the cases where the insertion is to the left of the deletion and then multiply by $$2$$. The combined effect of the insertion and the deletion is to shift all $$k$$ bits between them to the right while replacing the first one and removing the last one. This result can also be achieved by at most $$k$$ substitutions, so we need $$k\gt2$$. Inserting $$x$$ within a run of $$x$$s has the same effect as inserting $$x$$ at the end of the run. Thus we can count all insertions with different effects once by always inserting the bit complementary to the one to the right of the insertion. Similarly, a deletion within a run has the same effect as a deletion at the start of the run, so we should only count deletions that follow a change between $$0$$ and $$1$$.

That gives us an initial count of

$$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;,$$

which together with $$\frac{n(n-1)}2$$ from the substitutions yields $$(n-1)^2$$. That's already of the order of the counts you computed, but a bit too high, so we're overcounting.

If there are no further changes in the $$k$$ shifted bits other than the one preceding the deletion, then only the bits next to the insertion and deletion change, and we can achieve that with $$2$$ substitutions, so we have to subtract

$$\sum_{k=3}^n\left(\frac12\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac12\right)^{n-k-1}k=n-3+2^{-(n-2)}\;.$$

Also, if the entire range of shifted bits consists of alternating zeros and ones, then swapping the insertion and the deletion yields the same effect, so in this case we were double-counting and need to subtract

$$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;,$$

which is half the previous sum. Thus, the expected number of binary strings of length $$n$$ at edit distance exactly $$2$$ from a uniformly randomly selected binary string of length $$n$$ is

$$(n-1)^2-\frac32\left(n-3+2^{-(n-2)}\right)=n^2-\frac72n+\frac{11}2-6\cdot2^{-n}\;,$$

in agreement with your computed results.

• This is really an impressive example of counting. Thank you. Can the same reasoning be applied for larger edit distance? I.e. 3,4,... Or does it become much more complicated?
– user35671
Commented Dec 28, 2019 at 9:59
• Maybe I should just ask another question of course.
– user35671
Commented Dec 28, 2019 at 13:19
• @Anush: In principle those cases could also be worked out in a similar fashion, but I think it would get too complicated (and accordingly error-prone) for my taste rather quickly. For small edit distances, if you just need the counts for practical purposes, it's more efficient to obtain them by fitting to the results for small $n$. For instance, for edit distance $3$, the result is $\frac23n^3-7n^2+\frac{361}{12}n-48+2^{-n}\left(-4n^2+6n+46\right)$, as obtained by this fit. Commented Dec 28, 2019 at 13:44
• @Anush: I tried it for distance $4$ but couldn't get it to work so far. Commented Dec 28, 2019 at 18:31
• @ChristianSievers: I tried including those terms and still didn't get a fit. I hope to return to the problem at some point. Commented Jan 15, 2020 at 16:29