# Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$

Given alphabet $$\{0,1\}$$, we want to uniformly sample $$x,y \in \{0,1\}^n$$ such that $$ed(x,y)=k$$, where $$ed$$ denotes the Levenstein distance, i.e., the minimum number of edit operations (insert, delete, substitute) that can transform $$x$$ to $$y$$.

Clearly, this can be done by brute force over all pairs of strings, which is very costly. To reduce the complexity, my main idea is to use Monte Carlo sampling:

Monte Carlo sampling: pick $$x\sim\{0,1\}^n$$ at random, introduce $$k$$ successive edit operations (equal number of delete and insert to end up with the same length) ending up in string $$y$$ and reject the pair iff $$ed(x,y)\neq k$$. The main challenge is to guarantee that the probability of confirmation is not exponentially low. Such a low probability of success forces us to repeat the sampling an exponential number of times, rendering any time savings useless.

Informal analysis: Let $$x=:x_0\to \dots \to x_k:=y$$ denote the intermediary strings during our $$k$$ random edits. Let $$S_i(x)$$ for $$i\le n$$ denote the level set for edit distance from $$x$$: $$S_i(x)=\{y\in \{0,1\}^n: ed(x,y)=i\}.$$ Therefore, $$ed(x,y)=k$$ implies $$x_i\in S_i$$ for all $$i=0,\dots, k$$. By construction, if we have $$x_i\in S_i$$, then $$x_{i+1}$$ must belong to one of $$S_{i-1}, S_i, S_{i+1}$$ level sets. Therefore, the probability of failure at step $$i$$ is bounded by the ratio $$\alpha_i=(|S_i|+|S_{i-1}|)/(|S_i|+|S_{i-1}|+|S_{i+1}|)$$. It remains to show that if $$k$$ is small (how small?) the ratio $$\alpha_i$$ remains very high, and in fact $$\prod_i^k \alpha_i$$ is not exponentially low.

Two main questions:

• How can we make my hand-wavy argument more rigorous?
• In the regime that $$k$$ is comparable to $$n$$ the proposed algorithm provably fails. Namely if $$k>2n/3$$, random walks will never get you much further than $$ed(x,y)\approx n/2$$, as even the edit distance of two randomly generated strings is concentrated around $$n/2$$. What would be an alternative to sampling for large $$k$$?
• Are you working in a regime where $k \ll n$? Where $k$ is large and close to $n$? Do you know?
– D.W.
Jun 3 at 17:39
• Thank you for raising this question, I added some explanation to the post. While both cases are relevant, I think the case of large $k$ is more challenging. Jun 3 at 18:24
• It's not the case that $x_i \in S_i \implies x_{i+1} \in S_i \cup S_{i+1}$, since it could be that the $(i+1)$-th edit undoes the $i$-th. In such cases, $x_{i+1} \in S_{i-1}$. Jun 3 at 23:46
• But note that an edit can never take you backwards further than 1 step, since that would contradict the optimality of the length-$i$ edit scripts in $S_i$: If $x_{i+1} \in S_{i-2}$, then you could transform $x_i$ into $y$ by first making 1 edit to get $x_{i+1}$, then $i-2$ edits to get $y$, for a total of $i-1$ edits. Jun 3 at 23:58
• you're right, I corrected the statement in the post, thank you! @j_random_hacker Jun 5 at 9:50

There are two considerations: running time, and correctness.

Running time: When $$k < (n-1)/\lg(4n)$$, heuristically I expect the running time of your algorithm to be fine and I'd guess you won't experience exponential blowup. We can show $$|S_k| \le (4n)^k$$, so when $$k < (n-1)/\lg(4n)$$, $$|S_k|/2^n \le 1/2$$. This is not a proof; to prove that everything is OK, we need to prove that $$|S_k|/(|S_0| + \dots + |S_k|)$$ is not too small, and I don't have a proof of that.

For large $$k$$, I don't know what algorithm might be suitable.

Correctness: Your method is not correct. It does not produce $$(x,y)$$ with the right distribution. Given $$x$$, not all $$y \in S_k(x)$$ will be equally be likely to be reached by the procedure you give, so your approach introduces a bias in the distribution of $$x,y$$.

For example, suppose $$x=10001$$ and $$k=2$$. If $$y=00000$$, there is just one edit script that transforms $$x$$ into $$y$$ (substitute bits 1 and 5). If $$y=10010$$, there are seven edit scripts that transform $$x$$ into $$y$$ (substitute bits 4 and 5; or, delete one of bits 2-4 and insert a 0 at the end, or do the same in the opposite order). So, if $$x=10001$$, your algorithm will be seven times as likely to output $$(10001,10010)$$ as it is to output $$(10001,00000)$$. This deviates from the uniform distribution.

Incidentally, I believe the procedure you outline is just rejection sampling (i.e., just Monte Carlo), not MCMC.

• Interesting point. However, I don't fully agree with your conclusion about the correctness. Uniform sampling of all pairs $x,y$ with $ed(x,y)=k$ also has an intrinsic bias to some strings. In other words, if we take the first string out of the uniformly sampled pair, it is not a uniformly random string. Jun 14 at 8:40
• @AmeerJewdaki, Well, look, you specified that distribution as what you wanted, so we can only answer based on the requirements in the question.
– D.W.
Jun 14 at 20:45