Skip to main content
MathOverflow

Return to Answer

Fixed expression for $N_{a.b}(Y_n)$.
Source Link
Daniel Cullina
Daniel Cullina
  • 116
  • 2

I can give a partial answer for the analogous question about deletion distance, the variant of edit distance where insertions and deletions are the only basic operations. Substitutions must be performed as a deletions plus and insertion, so their cost is larger than in the metric you gave.

Let $d(U,V)$ be the number deletions and insertions required to convert $U$ to $V$. For $U \in \Sigma^n$, let $N_{a,b}(U) = \{ V \in \Sigma^{n-a+b} : d(U,V) \leq a+b\}$. Let $q = |\Sigma|$.

For all $X \in \Sigma^n$, the size of the insertion ball is the same: $|N_{0,b}(X)| = \sum_{i = 0}^b \binom{n+b}{i}(q-1)^i$. The size of the deletion ball, $|N_{a,0}(X)|$ varies with $X$ and we have the trivial upper bound $|N_{a,0}(X)| \leq \binom{n}{a}$. Each $Y \in N_{a,b}(X)$ has a common substring of length $n-a$ with $X$, so $|N_{a,b}(X)| \leq \binom{n}{a} \sum_{i = 0}^b \binom{n-a+b}{i}(q-1)^i$. For $n \to \infty$ with $a$ and $b$ fixed, this bound is asymptotic to $\binom{n}{a}\binom{n}{b}(q-1)^b$.

Let $\Sigma = \{0,1\}$ and let $X_n$ be the length-$n$ string of alternating zeros and ones. It is not hard to show that $N_{a,b}(X_n) = N_{0,a+b}(X_{n-2a})$, so $|N_{a,b}(X_n)| = \sum_{i = 0}^{a+b} \binom{n-a+b}{i} \sim \binom{n}{a+b}$. This is a factor of $\binom{a+b}{a}$ below the asymptotic upper bound of $\binom{n}{a}\binom{n}{b}$.

However, we can construct other binary strings that do meet the asymptotic upper bound. Let $m \approx \sqrt{n}$ and let it be odd so $X_m$ begins and ends with zero. Let $Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m$$Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m + 10001$. If we perform $a$ deletions and $b$ insertions on $Y_n$ such that at most one insertion or deletion is inside each copy of $X_m$ and none are inside the 10001 segments, we produce each member of $N_{a,b}(Y_n)$ at most once because we do not create or destroy any runs of length three in $Y_n$. Thus $|N_{a,b}(Y_n)| \geq \binom{m}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{m^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$$|N_{a,b}(Y_n)| \geq \binom{n/(m+5)}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{(n/m)^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$.

Your question asks about the analogue of $\bigcup_{0 \leq i \leq k, 0 \leq j \leq k} N_{i,j}(X)$. For fixed $k$, only the contribution of $N_{k,k}(X)$ matters asymptotically.

I am not sure how easily these arguments can be adapted to edit distance allowing replacements, but hopefully this provides a helpful starting point.

My paper about an upper bound on the size of deletion correcting codes applies some variants of these ideas.

I can give a partial answer for the analogous question about deletion distance, the variant of edit distance where insertions and deletions are the only basic operations. Substitutions must be performed as a deletions plus and insertion, so their cost is larger than in the metric you gave.

Let $d(U,V)$ be the number deletions and insertions required to convert $U$ to $V$. For $U \in \Sigma^n$, let $N_{a,b}(U) = \{ V \in \Sigma^{n-a+b} : d(U,V) \leq a+b\}$. Let $q = |\Sigma|$.

For all $X \in \Sigma^n$, the size of the insertion ball is the same: $|N_{0,b}(X)| = \sum_{i = 0}^b \binom{n+b}{i}(q-1)^i$. The size of the deletion ball, $|N_{a,0}(X)|$ varies with $X$ and we have the trivial upper bound $|N_{a,0}(X)| \leq \binom{n}{a}$. Each $Y \in N_{a,b}(X)$ has a common substring of length $n-a$ with $X$, so $|N_{a,b}(X)| \leq \binom{n}{a} \sum_{i = 0}^b \binom{n-a+b}{i}(q-1)^i$. For $n \to \infty$ with $a$ and $b$ fixed, this bound is asymptotic to $\binom{n}{a}\binom{n}{b}(q-1)^b$.

Let $\Sigma = \{0,1\}$ and let $X_n$ be the length-$n$ string of alternating zeros and ones. It is not hard to show that $N_{a,b}(X_n) = N_{0,a+b}(X_{n-2a})$, so $|N_{a,b}(X_n)| = \sum_{i = 0}^{a+b} \binom{n-a+b}{i} \sim \binom{n}{a+b}$. This is a factor of $\binom{a+b}{a}$ below the asymptotic upper bound of $\binom{n}{a}\binom{n}{b}$.

However, we can construct other binary strings that do meet the asymptotic upper bound. Let $m \approx \sqrt{n}$ and let it be odd so $X_m$ begins and ends with zero. Let $Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m$. If we perform $a$ deletions and $b$ insertions on $Y_n$ such that at most one insertion or deletion is inside each copy of $X_m$ and none are inside the 10001 segments, we produce each member of $N_{a,b}(Y_n)$ at most once because we do not create or destroy any runs of length three in $Y_n$. Thus $|N_{a,b}(Y_n)| \geq \binom{m}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{m^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$.

Your question asks about the analogue of $\bigcup_{0 \leq i \leq k, 0 \leq j \leq k} N_{i,j}(X)$. For fixed $k$, only the contribution of $N_{k,k}(X)$ matters asymptotically.

I am not sure how easily these arguments can be adapted to edit distance allowing replacements, but hopefully this provides a helpful starting point.

My paper about an upper bound on the size of deletion correcting codes applies some variants of these ideas.

I can give a partial answer for the analogous question about deletion distance, the variant of edit distance where insertions and deletions are the only basic operations. Substitutions must be performed as a deletions plus and insertion, so their cost is larger than in the metric you gave.

Let $d(U,V)$ be the number deletions and insertions required to convert $U$ to $V$. For $U \in \Sigma^n$, let $N_{a,b}(U) = \{ V \in \Sigma^{n-a+b} : d(U,V) \leq a+b\}$. Let $q = |\Sigma|$.

For all $X \in \Sigma^n$, the size of the insertion ball is the same: $|N_{0,b}(X)| = \sum_{i = 0}^b \binom{n+b}{i}(q-1)^i$. The size of the deletion ball, $|N_{a,0}(X)|$ varies with $X$ and we have the trivial upper bound $|N_{a,0}(X)| \leq \binom{n}{a}$. Each $Y \in N_{a,b}(X)$ has a common substring of length $n-a$ with $X$, so $|N_{a,b}(X)| \leq \binom{n}{a} \sum_{i = 0}^b \binom{n-a+b}{i}(q-1)^i$. For $n \to \infty$ with $a$ and $b$ fixed, this bound is asymptotic to $\binom{n}{a}\binom{n}{b}(q-1)^b$.

Let $\Sigma = \{0,1\}$ and let $X_n$ be the length-$n$ string of alternating zeros and ones. It is not hard to show that $N_{a,b}(X_n) = N_{0,a+b}(X_{n-2a})$, so $|N_{a,b}(X_n)| = \sum_{i = 0}^{a+b} \binom{n-a+b}{i} \sim \binom{n}{a+b}$. This is a factor of $\binom{a+b}{a}$ below the asymptotic upper bound of $\binom{n}{a}\binom{n}{b}$.

However, we can construct other binary strings that do meet the asymptotic upper bound. Let $m \approx \sqrt{n}$ and let it be odd so $X_m$ begins and ends with zero. Let $Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m + 10001$. If we perform $a$ deletions and $b$ insertions on $Y_n$ such that at most one insertion or deletion is inside each copy of $X_m$ and none are inside the 10001 segments, we produce each member of $N_{a,b}(Y_n)$ at most once because we do not create or destroy any runs of length three in $Y_n$. Thus $|N_{a,b}(Y_n)| \geq \binom{n/(m+5)}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{(n/m)^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$.

Your question asks about the analogue of $\bigcup_{0 \leq i \leq k, 0 \leq j \leq k} N_{i,j}(X)$. For fixed $k$, only the contribution of $N_{k,k}(X)$ matters asymptotically.

I am not sure how easily these arguments can be adapted to edit distance allowing replacements, but hopefully this provides a helpful starting point.

My paper about an upper bound on the size of deletion correcting codes applies some variants of these ideas.

Source Link
Daniel Cullina
Daniel Cullina
  • 116
  • 2

I can give a partial answer for the analogous question about deletion distance, the variant of edit distance where insertions and deletions are the only basic operations. Substitutions must be performed as a deletions plus and insertion, so their cost is larger than in the metric you gave.

Let $d(U,V)$ be the number deletions and insertions required to convert $U$ to $V$. For $U \in \Sigma^n$, let $N_{a,b}(U) = \{ V \in \Sigma^{n-a+b} : d(U,V) \leq a+b\}$. Let $q = |\Sigma|$.

For all $X \in \Sigma^n$, the size of the insertion ball is the same: $|N_{0,b}(X)| = \sum_{i = 0}^b \binom{n+b}{i}(q-1)^i$. The size of the deletion ball, $|N_{a,0}(X)|$ varies with $X$ and we have the trivial upper bound $|N_{a,0}(X)| \leq \binom{n}{a}$. Each $Y \in N_{a,b}(X)$ has a common substring of length $n-a$ with $X$, so $|N_{a,b}(X)| \leq \binom{n}{a} \sum_{i = 0}^b \binom{n-a+b}{i}(q-1)^i$. For $n \to \infty$ with $a$ and $b$ fixed, this bound is asymptotic to $\binom{n}{a}\binom{n}{b}(q-1)^b$.

Let $\Sigma = \{0,1\}$ and let $X_n$ be the length-$n$ string of alternating zeros and ones. It is not hard to show that $N_{a,b}(X_n) = N_{0,a+b}(X_{n-2a})$, so $|N_{a,b}(X_n)| = \sum_{i = 0}^{a+b} \binom{n-a+b}{i} \sim \binom{n}{a+b}$. This is a factor of $\binom{a+b}{a}$ below the asymptotic upper bound of $\binom{n}{a}\binom{n}{b}$.

However, we can construct other binary strings that do meet the asymptotic upper bound. Let $m \approx \sqrt{n}$ and let it be odd so $X_m$ begins and ends with zero. Let $Y_n = X_m + 10001 + X_m + 10001 + \ldots + X_m$. If we perform $a$ deletions and $b$ insertions on $Y_n$ such that at most one insertion or deletion is inside each copy of $X_m$ and none are inside the 10001 segments, we produce each member of $N_{a,b}(Y_n)$ at most once because we do not create or destroy any runs of length three in $Y_n$. Thus $|N_{a,b}(Y_n)| \geq \binom{m}{a+b}\binom{a+b}{a}m^a(m+2)^b \sim \frac{m^{a+b}}{a!b!} m^{a+b} \sim \binom{n}{a}\binom{n}{b}$.

Your question asks about the analogue of $\bigcup_{0 \leq i \leq k, 0 \leq j \leq k} N_{i,j}(X)$. For fixed $k$, only the contribution of $N_{k,k}(X)$ matters asymptotically.

I am not sure how easily these arguments can be adapted to edit distance allowing replacements, but hopefully this provides a helpful starting point.

My paper about an upper bound on the size of deletion correcting codes applies some variants of these ideas.