# Approximate Trace Reconstruction via Median String (in Average-Case)

Diptarka Chakraborty National University of Singapore. Work partially
supported by NUS ODPRT Grant, WBS No. R-252-000-A94-133. Email:
<EMAIL_ADDRESS>Debarati Das Basic Algorithm Research Copenhagen
(BARC), University of Copenhagen Email<EMAIL_ADDRESS>Robert
Krauthgamer Weizmann Institute of Science. Work partially supported by ONR
Award N00014-18-1-2364, the Israel Science Foundation grant #1086/18, and a
Minerva Foundation grant, and by the Israeli Council for Higher Education
(CHE) via the Weizmann Data Science Research Center. Email:
<EMAIL_ADDRESS>
###### Abstract

We consider an _approximate_ version of the trace reconstruction problem,
where the goal is to recover an unknown string $s\in\\{0,1\\}^{n}$ from $m$
traces (each trace is generated independently by passing $s$ through a
probabilistic insertion-deletion channel with rate $p$). We present a
deterministic near-linear time algorithm for the average-case model, where $s$
is random, that uses only _three_ traces. It runs in near-linear time
$\tilde{O}(n)$ and with high probability reports a string within edit distance
$O(\epsilon pn)$ from $s$ for $\epsilon=\tilde{O}(p)$, which significantly
improves over the straightforward bound of $O(pn)$.

Technically, our algorithm computes a $(1+\epsilon)$-approximate median of the
three input traces. To prove its correctness, our probabilistic analysis shows
that an approximate median is indeed close to the unknown $s$. To achieve a
near-linear time bound, we have to bypass the well-known dynamic programming
algorithm that computes an optimal median in time $O(n^{3})$.

##  1 Introduction

#### Trace Reconstruction.

One of the most common problems in statistics is to estimate an unknown
parameter from a set of noisy observations (or samples). The main objectives
are (1) to use as few samples as possible, (2) to minimize the estimation
error, and (3) to design an efficient estimation algorithm. One such
parameter-estimation problem is _trace reconstruction_ , where the unknown
quantity is a string $s\in\Sigma^{n}$, and the observations are independent
_traces_ , where a trace is a string that results from $s$ passing through
some noise channel. The goal is to reconstruct $s$ using a few traces. (Unless
otherwise specified, in this paper we consider $\Sigma=\\{0,1\\}$.) Various
noise channels have been considered so far. The most basic one only performs
substitutions. A more challenging channel performs deletions. Even more
challenging is the _insertion-deletion_ channel, which scans the string $s$
and keeps the next character with probability $1-p$, deletes it with
probability $p/2$, or inserts a uniformly randomly chosen symbol (without
processing the next character) with probability $p/2$, for some noise-rate
parameter $p\in[0,1)$. We denote this insertion-deletion channel by
$R_{p}(s)$, see Section 2 for a formal definition.111In the literature, an
insertion-deletion channel with different probabilities for insertion and for
deletion has been studied. For simplicity in exposition, we consider a single
error probability throughout this paper, however our results can easily be
generalized to different insertion and deletion probabilities. Another
possible generalization is to allow substitutions along with insertions and
deletions. Again, for simplicity, we do not consider substitutions, but with
slightly more careful analysis our results could be extended.

The literature studies mostly two variants of trace reconstruction. In the
_worst-case_ variant, the unknown string $s$ is an arbitrary string from
$\Sigma^{n}$, while in the _average-case_ variant, $s$ is assumed to be drawn
uniformly at random from $\Sigma^{n}$. The trace reconstruction problem finds
numerous applications in computational biology, DNA storage systems, coding
theory, etc. Starting from early 1970s [Kal73], various other versions of this
problem have been studied, including combinatorial channels [Lev01a, Lev01b],
smoothed complexity [CDL+21b], coded trace reconstruction [CGMR20], and
population recovery [BCF+19, Nar20].

We focus on the average-case variant, where it is known that
$\exp(O(\log^{1/3}n))$ samples suffice to reconstruct a (random) unknown
string $s$ over the insertion-deletion channel [HPPZ20]. On the other hand, a
recent result [Cha21a] showed that $\tilde{\Omega}(\log^{5/2}n)$ samples are
necessary, improving upon the previous best lower bound of
$\tilde{\Omega}(\log^{9/4}n)$ [HL20]. We emphasize that all these upper and
lower bounds are for _exact_ trace reconstruction, i.e., for recovering the
unknown string $x$ perfectly (with no errors). A natural question proposed by
Mitzenmacher [Mit09] is whether such a lower bound on the sample complexity
can be bypassed by allowing approximation, i.e., by finding a string $z$ that
is “close” to the unknown string $s$. One of the most fundamental measures of
closeness between a pair of strings $z$ and $z^{\prime}$, is their _edit
distance_ , denoted by $\operatorname{ED}(z,z^{\prime})$ and defined as the
minimum number of insertion, deletion, and substitution operations needed to
transform $z$ into $z^{\prime}$. Observe that a trace generated from $s$ via
an insertion-deletion channel $G_{p}$ has expected edit distance about $pn$
from the unknown string $s$ (see Section 3). We ask how many traces (or
samples) are required to construct a string $z$ at a much smaller edit
distance from the unknown $s$. (Since the insertion-deletion channel has no
substitutions, we also do not consider substitutions in our analysis of the
edit distance, however the results probably hold also when both allow also
substitutions.)

A practical application of average-case trace reconstruction is in the
portable DNA-based data storage system. In the DNA storage system [GBC+13,
RMR+17], a file is preprocessed by encoding it into a DNA sequence. This
encoded sequence is randomized using a pseudo-random sequence, and thus the
final encoding sequence could be treated as a (pseudo-)random string. The
stored (encoded) data is retrieved using next-generation sequencing (like
single-molecule real-time sequencing (SMRT) [RCS13] that involves $12-18\%$,
which generates several noisy copies (traces) of the stored data via some
insertion-deletion channel. The final step is to decode back the stored data
with as few traces as possible. Currently, researchers use multiple sequence
alignment algorithms to reconstruct the trace [YGM17, OAC+18]. Unfortunately,
such heuristic algorithms are notoriously difficult to analyze rigorously to
show a theoretical guarantee. However, the preprocessing step also involves
error-correcting code to encode the strings. Thus it suffices to reconstruct
the original string up to some small error (depending on the error-correcting
codes used). This specific application gives one motivation to study
approximate trace reconstruction.

Our main contribution is to show that it is sufficient to use only three
traces to reconstruct the unknown string up to a small edit error.

######  Theorem 1.1.

There is a constant $c_{0}>0$ and a deterministic algorithm that, given as
input a noise parameter $p\in(0,c_{0}]$, and three traces from the insertion-
deletion channel $R_{p}(s)$ for a uniformly random (but unknown) string
$s\in\\{0,1\\}^{n}$, outputs in time $\tilde{O}(n)$ a string $z$ that
satisfies $\Pr[\operatorname{ED}(s,z)\leq O(p^{2}\log(1/p)n)]\geq 1-n^{-1}$.

The probability in this theorem is over the random choice of $s$ and the
randomness of the insertion-deletion channel $R_{p}$. We note that the term
$\log(1/p)$ in the estimation error $\operatorname{ED}(s,z)$ can be shaved by
increasing the alphabet size to $\operatorname{poly}(1/\epsilon)$. An edit
error of $O(p^{2}n)$ is optimal for three traces, because in expectation
$O(p^{2}n)$ characters of $s$ are deleted in two of the three traces, and look
as if they are inserted to $s$ in one of the three traces (which occurs in
expectation for even more characters).

Our theorem demonstrates that the number of required traces exhibits a sharp
contrast between exact and approximate trace reconstruction. In fact,
approximate reconstruction not only beats the $\Omega(\log^{5/2}n)$ lower
bound for exact reconstruction, but surprisingly uses only _three_ traces! We
conjecture that the estimation error $\operatorname{ED}(s,z)$ can be reduced
further using more than three traces. We believe that our technique can be
useful here, but this is left open for future work.

######  Conjecture 1.

The estimation error $\operatorname{ED}(s,z)$ in Theorem 1.1 can be reduced to
$O(\epsilon pn)$ for arbitrarily small $\epsilon>0$, using
$\operatorname{poly}(1/\epsilon)$ traces.

This conjecture holds for $\epsilon<1/n$, as follows from known bounds for
exact reconstruction [HPPZ20], and perhaps suggests that a number of traces
that is sub-polynomial in $1/\epsilon$ it suffices for all $\epsilon$.

#### Median String.

As mentioned earlier, a common heuristic to solve the trace reconstruction
problem is multiple sequence alignment, which can be formulated equivalently
(see [Gus97] and the references therein) as the problem of finding a median
under edit distance. For general context, the median problem is a classical
aggregation task in data analysis; its input is a set $S$ of points in a
metric space relevant to the intended application, and the goal is to find a
point (not necessarily from $S$) with the minimum sum of distances to points
in $S$, i.e.,

$\min_{y}\sum_{x\in S}d(y,x).$ (1)

Such a point is called a _median_ (or _geometric median_ in a Euclidean
space). For many applications, it suffices to find an _approximate median_ ,
i.e., a point in the metric with approximately minimal objective value (1) .
The problem of finding an (approximate) median has been studied extensively
both in theory and in applied domains, over various metric spaces, including
Euclidean [CLM+16] (see references therein for an overview), Hamming
(folklore), the edit metric [San75, Kru83, NR03], rankings [DKNS01, ACN08,
KS07], Jaccard distance [CKPV10], Ulam [CDK21], and many more [FVJ08, Min15,
CCGB17].

The median problem over the _edit-distance metric_ is known as the _median
string_ problem [Koh85], and finds numerous applications in computational
biology [Gus97, Pev00], DNA storage system [GBC+13, RMR+17], speech
recognition [Koh85], and classification [MJC00]. This problem is known to be
NP-hard [dlHC00, NR03] (even W[1]-hard [NR03]), and can be solved by standard
dynamic programming [San75, Kru83] in time $O(2^{m}n^{m})$ when the input has
$m=|S|$ strings of length $n$ each. From the perspective of approximation
algorithms, a multiplicative $2$-approximation to the median is
straightforward (this works in every metric space by simply reporting the best
among the input strings, i.e., $y^{*}\in S$ that minimizes the objective).
However, no polynomial-time algorithm is known to break below
$2$-approximation (i.e., achieve factor $2-\delta$ for fixed $\delta>0$) for
the median string problem, despite several heuristic algorithms and results
for special cases [CA97, Kru99, FZ00, PB07, ARJ14, HK16, MAS19, CDK21].

Although the median string (or equivalently multiple sequence alignment) is a
common heuristic for trace reconstruction [YGM17, OAC+18], to the best of our
knowledge there is no definite connection between these two problems. We show
that both the problems are roughly the same in the average-case model. It is
not difficult to show that any string close to the unknown string is an
approximate median. To see this, we can show that for a set $S$ of $m$ traces
of an (unknown) random string $s$, their optimal median objective value is at
least $(1-O(\epsilon))pnm$ with high probability. On the other hand, the
median objective value with respect to $s$ itself is at most $(1+\epsilon)pnm$
with high probability. (See the proof of Claim 4.5.) Hence, the unknown string
$s$ is an $(1+O(\epsilon))$-approximate median of $S$, and by the triangle
inequality, every string close (in edit distance) to $s$ is also an
approximate median of $S$. One of the major contributions of this paper is the
converse direction, showing that given a set of traces of an unknown string,
any approximate median of the traces is close (in edit distance) to the
unknown string. This is true even for three traces.

######  Theorem 1.2.

For a large enough $n\in\mathbb{N}$ and a noise parameter $p\in(0,0.001)$, let
the string $s\in\\{0,1\\}^{n}$ be chosen uniformly at random, and let
$s_{1},s_{2},s_{3}$ be three traces generated by the insertion-deletion
channel $R_{p}(s)$. If $x_{\textrm{med}}$ is a $(1+\epsilon)$-approximate
median of $\\{s_{1},s_{2},s_{3}\\}$ for $\epsilon\in[110p\log(1/p),1/6]$, then
$\Pr[\operatorname{ED}(s,x_{\textrm{med}})\leq
O(\epsilon)\cdot\texttt{OPT}]\geq 1-n^{-3}$, where OPT denotes the optimal
median objective value of $\\{s_{1},s_{2},s_{3}\\}$.

An immediate consequence (see Corollary 4.9) is that for every $3\leq
m<n^{O(1)}$ traces, every $(1+\epsilon)$-approximate median $x_{\textrm{med}}$
satisfies $\operatorname{ED}(s,x_{\textrm{med}})\leq
O(\epsilon)\frac{\texttt{OPT}}{m}$.

Thus if we could solve any of the two problems (even approximately), we get an
approximate solution to the other problem. E.g., the current best (exact)
trace reconstruction algorithm for the average-case [HPPZ20] immediately gives
us an $O(n^{1+o(1)})$ time algorithm to find an $(1+O(\epsilon))$-approximate
median of a set of traces. We leverage this interplay between the two problems
to design an efficient algorithm for approximate trace reconstruction. Since
one can compute the (exact) median of three strings $s_{1},s_{2},s_{3}$ in
time $O(|s_{1}|\cdot|s_{2}|\cdot|s_{3}|)$ [San75, Kru83], the above theorem
immediately provides us the unknown string up to some small edit error in time
$O(n^{3})$. We further reduce the running time to near-linear by cleverly
partitioning each of the traces into $\operatorname{polylog}n$-size blocks and
then applying the median algorithm on these blocks. Finally, we concatenate
all the block-medians to get an “approximate” unknown string, leading to
Theorem 1.1. One may further note that Theorem 1.1 also provides a
$(1+O(\epsilon))$-approximate median for any set of traces in the average-case
(again due to Theorem 1.2).

Taking the smallest possible $\epsilon$ in Theorem 1.2, we get that for three
traces generated from $s$, with high probability
$\operatorname{ED}(s,x_{\textrm{med}})\leq\tilde{O}(p^{2}n)$. In comparison,
it is not hard to see that with high probability OPT is bounded by roughly
$3pn$. We conjecture that the number of traces increases, the median string
converges to the unknown string $s$. In particular,
$\operatorname{ED}(s,x_{\textrm{med}})\leq\epsilon n$ when using
$\operatorname{poly}(1/\epsilon)$ traces (instead of just three), with high
probability. We hope that our technique can be extended to prove the above
conjecture, but we leave it open for future work.

The main implication of this conjecture is an $\tilde{O}(n)$ time approximate
trace reconstruction algorithm, for any fixed $\epsilon>0$, as follows. It is
straightforward to extend our approximate median finding algorithm (in Section
5) to more input strings. (For brevity, we present only for three input
strings.) For $m$ strings, the running time would be $n(\log n)^{O(m)}$, and
for $m=\operatorname{poly}(1/\epsilon)$ strings this running time is
$n\operatorname{polylog}n$. As a consequence, we will be able to reconstruct
in $\tilde{O}(n)$ time a string $z$ such that
$\operatorname{ED}(s,z)\leq\epsilon n$, which in particular implies Conjecture
1.

###  1.1 Related Work

A systematic study on the trace reconstruction problem has been started since
[Lev01a, Lev01b, BKKM04]. However, some of its variants appeared even in the
early ’70s [Kal73]. One of the main objectives here is to reduce the number of
traces required, aka the sample complexity. Both the deletion only and the
insertion-deletion channels have been considered so far. In the general worst-
case version, the problem considers the unknown string $s$ to be any arbitrary
string from $\\{0,1\\}^{n}$. The very first result by Batu et al. [BKKM04]
asserts that for small deletion probability (noise parameter)
$p\leq\frac{1}{n^{1/2+\epsilon}}$, to reconstruct $s$ considering $O(n\log n)$
samples suffice. A very recent work [CDL+21a] improved the sample complexity
to $\mathrm{poly}(n)$ while allowing a deletion probability
$p\leq\frac{1}{n^{1/3+\epsilon}}$. For any constant deletion probability
bounded away from 1, the first subexponential (more specifically,
$2^{\tilde{O}(\sqrt{n})}$) sample complexity was shown by [HMPW08], which was
later improved to $2^{O(n^{1/3})}$ [NP17, DOS17], and then finally to
$2^{O(n^{1/5})}$ [Cha21b].

Another natural variant that has also been widely studied is the average-case,
where the unknown string $s$ is randomly chosen from $\\{0,1\\}^{n}$. It turns
out that this version is significantly simpler than the worst-case in terms of
the sample complexity. For sufficiently small noise parameter ($p=o(1)$ as a
function of $n$), efficient trace reconstruction algorithms are known [BKKM04,
KM05, VS08]. For any constant noise parameter bounded away from 1 in case of
insertion-deletion channel, the current best sample complexity is
$\exp(O(\log^{1/3}n))$ [HPPZ20] improving up on $\exp(O(\log^{1/2}n))$ [PZ17].
Both of these results are built on the worst-case trace reconstruction by
[NP17, DOS17]. Furthermore, the trace reconstruction algorithm of [HPPZ20]
runs in $n^{1+o(1)}$ time.

In the case of the lower bound, information-theoretically, it is easy to see
that $\Omega(\log n)$ samples must be needed when the deletion probability is
at least some constant. In the worst-case model, the best known lower bound on
the sample complexity is $\tilde{\Omega}(n^{3/2})$ [Cha21a]. For the average-
case, McGregor, Price, and Vorotnikova [MPV14] showed that $\Omega(\log^{2}n)$
samples are necessary to reconstruct the unknown (random) string $s$. This
bound was further improved to $\tilde{\Omega}(\log^{9/4}n)$ by Holden and
Lyons [HL20], and very recently to $\tilde{\Omega}(\log^{5/2}n)$ by Chase
[Cha21a].

The results described above show an exponential gap between the upper bound
and lower bound of the sample complexity. The natural question is, instead of
reconstructing the unknown string exactly, if we allow some error in the
reconstructed string, then can we reduce the sample complexity? Recently,
Davies et al. [DRRS20] presented an algorithm that for a specific class of
strings (considering various run-lengths or density assumptions), can compute
an approximate trace with $\epsilon n$ additive error under the edit distance
while using only $\mathrm{polylog}(n)$ samples. The authors also established
that to approximate within the edit distance $n^{1/3-\delta}$, the number of
required samples is $n^{1+3\delta/2}/\mathrm{polylog}(n)$, for $0<\delta<1/3$,
in the worst case. Independently, Grigorescu et al. [GSZ20] showed assuming
deletion probability $p=1/2$, there exist two strings within edit distance 4
such that any _mean-based algorithm_ requires $\exp(\Omega(\log^{2}n))$
samples to distinguish them.

###  1.2 Technical Overview

The key contribution of this paper is a linear-time approximate trace
reconstruction algorithm that uses only three traces to reconstruct an unknown
(random) string up to some small edit error (Theorem 1.1). To get our result,
we establish a relation between the (approximate) trace reconstruction problem
and the (approximate) median string problem. Consider a uniformly random
(unknown) string $s\in\Sigma^{n}$. We show that for any three traces of $s$
generated by the probabilistic insertion-deletion channel $R_{p}$, an
arbitrary $(1+\epsilon)$-approximate median of the three trace must be, with
high probability, $O(\epsilon)\texttt{OPT}$-close in edit distance to $s$
(Theorem 1.2). Once we establish this connection, it suffices to solve the
median problem (even approximately). The median of three traces can be solved
optimally in $O(n^{3})$ time using a standard dynamic programming algorithm
[San75, Kru83]. It is not difficult to show that the optimal median objective
value OPT is at least $3(1-O(\epsilon))pn$ (Claim 4.5), and thus the computed
median is at edit distance at most $O(\epsilon pn)$ from the unknown string
$s$. This result already beats the known lower bound for _exact_ trace
reconstruction in terms of sample complexity. However, the running time is
cubic in $n$, whereas current average-case trace reconstruction algorithms run
in time $n^{1+o(1)}$ [HPPZ20].

Next we briefly describe the algorithm that improves the running time to
$\tilde{O}(n)$. Instead of finding a median of the entire traces, we compute
the median block-by-block and then concatenate the resulting blocks. A natural
idea is that each such block is just the median of three substrings taken from
the three traces, but the challenge is to identify which substring to take
from each trace, particularly because $s$ is not known. To mitigate this
issue, we take the first trace $s_{1}$ and partition it into disjoint blocks
of length $\Theta(\log^{2}n)$ each. For each such block, we consider its
middle $\log^{2}n$-size sub-block as an _anchor_. We then locate for each
anchor its corresponding substrings in the other two traces $s_{2}$ and
$s_{3}$, using any approximate pattern matching algorithm under the edit
metric (e.g. [LV89, GP90]) to find the _best match_ of the anchor inside
$s_{2},s_{3}$. Each anchor has a _true match_ in $s_{2}$ and in $s_{3}$, i.e.,
the portion that the anchor generated under the noise channel. Since the
anchors in $s_{1}$ are “well-separated” (by at least $\omega(\log n)$), their
true matches are also far apart both in $s_{2},s_{3}$. Further, exploiting the
fact that $s$ is a random string, we can argue that each anchor’s best match
and true match overlap almost completely (i.e., except for a small portion),
see Section 5). We thus treat these best match blocks as anchors in $s_{2}$
and $s_{3}$ and partition them into blocks. From this point, the algorithm is
straightforward. Just consider the first block of each of $s_{1},s_{2},s_{3}$
and compute their median. Then consider the second block from each trace and
compute their median, and so on. Finally, concatenate all these block medians,
and output the resulting string.

The crucial claim is that the best match and true match of an anchor in
$s_{1}$ are the same except for a small portion, is crucial from two aspects.
First, it ensures that any $r$-th block of $s_{2},s_{3}$ contains the true
match of the $r$-th anchor of $s_{1}$. Consequently, computing a median of
these blocks reconstructs the corresponding portion of the unknown string $s$
up to edit distance $O(\epsilon)p\log^{2}n$ with high probability. Thus for
“most of the blocks”, we can reconstruct up to such edit distance bound. We
can make the length of the non-anchor portions negligible compared to the
anchors (simply because a relatively small “buffer” around each anchor
suffices), and thus we may ignore them and still ensure that the output string
is $O(\epsilon pn)$-close (in edit distance) to the unknown string $s$. (See
the proof of Lemma 5.6 for the details.) The second use of that crucial claim
is that it helps in searching for the best match of each anchor “locally”
(within a $O(\log^{2}n)$-size window) in each $s_{j}$, $j\in\\{2,3\\}$. As a
result, we bound the running time of the pattern matching step by
$\tilde{O}(n)$. The median computations are also on $\Theta(\log^{2}n)$-size
blocks, and thus takes a total $\tilde{O}(n)$ time.

It remains to explain the key contribution, which is the connection between
the (approximate) trace reconstruction and the (approximate) median string
problem. Its first ingredient is that there is an “almost unique” alignment
between the unknown string $s$ and a trace of it generated by the insertion-
deletion channel $R_{p}$. We provide below an overview of this analysis (see
Section 3 for details). We start by considering the random string $s$ and a
string $y$ generated by passing $s$ through the noise channel $R_{p}$. For
sake of analysis, we can replace $R_{p}$ with an _equivalent_ probabilistic
model $G_{p}$, that first computes a random alignment $A^{p}$ between $s$ and
$y$, and only then fills in random characters in $s$ and in the insertion-
positions in $y$. This model is more convenient because it separates the two
sources of randomness, for example we can condition on one ($A^{p}$) when
analyzing typical behavior of the other (characters of $s$).

Figure 1: (a) An example of well separated edit operation: $A^{p}$ deletes
$s[i]$ and aligns rest of the characters in block $B$ with block $B^{\prime}$.
(b) $M$ aligns $s[i]$ and $y[\bar{i}]$. For each index $j$ appearing left of
$i$ in $B$, $A^{p}[j]\neq M(j)$.

In expectation, the channel $G_{p}$ generates a trace $y$ by performing about
$pn$ random edit operations in $s$ (planting insertions/deletions), hence the
planted alignment $A^{p}$ has expected cost about $pn$. But can these edit
operations cancel each other? Can they otherwise interact, leading to the
optimal edit distance being smaller? For example, suppose $s[i]=0$. If $G_{p}$
first inserts a $0$ before $s[i]$ and then deletes $s[i]$, then clearly these
two operations cancel each other. We show that such events are unlikely.
Following this intuition, we establish our first claim, that with high
probability and the edit distance between $s,y$ is large, specifically
$\operatorname{ED}(s,y)\geq(1-6\epsilon)pn$ for $\epsilon\geq 15p\log(1/p)$,
see Lemma 3.3; thus, the planted alignment $A^{p}$ is near-optimal. Towards
proving this, we first show that a vast majority of the planted edit
operations are well-separated, i.e., have $\Theta(1/p)$ positions between
them. In this case, for one operation to cancel another one, the characters
appearing between them in $s$ must all be equal, which happens with a small
probability because $s$ is random.

Formally, for almost all indices $i$ where $G_{p}$ performs some edit
operation, the block around it
$B=\\{i-\frac{c}{r},i-\frac{c}{r}+1,\dots,i+\frac{c}{r}\\}$ in $s$ (for a
small constant $c>0$), satisfies that $i$ is the only index in $B$ that
$G_{p}$ edits (see Lemma 3.2). Next we show that in every _optimal_ alignment
between $s$ and $y$, almost all these blocks contribute a cost of $1$. As
otherwise, there is locally an alignment $M$ that aligns each index in $B$ to
some character in $y$, while $G_{p}$ makes exactly one edit operation, say
deletes $s[i]$. See for example Figure 1, where $M$ aligns $s[i]$ and
$y[\bar{i}]$ whereas $A^{p}$ deletes $s[i]$. In this case, $M$ and $A^{p}$
must disagree on at least $c/r$ indices (all indices either to the right or to
the left of $i$ in $B$). In Figure 1, all $j\in[i-\frac{c}{r},i]$ satisfy
$M[j]\neq A^{p}[j]$. The crux is that any pair of symbols in $s,y$ are chosen
independently at random unless $A^{p}$ aligns their positions. Thus
probability that in each of the $\frac{c}{r}$ pairs aligned by $M$, the two
matched symbols will be equal is $(1/|\Sigma|)^{\frac{c}{r}}$. In the formal
proof, we address several technical issues, like having not just one but many
blocks, and possible correlations due to overlaps between different pairs,
which are overcome by a carefully crafted union bound.

We further need to prove that the planted alignment is robust, in the sense
that, with high probability, every near-optimal alignment between $s$ and $y$
must “agree” with the planted alignment $A^{p}$ on all but a small fraction of
the edit operations. Formally, we again consider a partition of $s$ into
blocks containing exactly one planted edit operation, and show that for almost
all such blocks $B$, if $A^{p}$ maps $B$ to a substring $B^{\prime}$ in $y$,
that near-optimal alignment also maps $B$ to $B^{\prime}$ (see Lemma 3.6). To
see this, suppose there is a near-optimal alignment that maps $B$ to
$\bar{B}\neq B^{\prime}$. Then following an argument similar to the above, we
can show there are many indices in the block $B$ such that $A^{p}$ and $M$
disagree on them. Thus, in each such block, $M$ tries to match many pairs of
symbols that are chosen independently at random, and therefore the probability
that $M$ matches $B$ and $\bar{B}$ with a cost at most $1$ is small. Compared
to Lemma 3.2, an extra complication here is that now we allow $M$ to match $B$
and $\bar{B}$ with cost at most $1$ (and not only $0$), and in particular
$\bar{B}$ can have three different lengths: $|B|,|B|-1,|B|+1$. Hence the
analysis must argue separately for all these cases, requiring a few additional
ideas/observations.

After showing that a near-optimal alignment between a random string $s$ and
$R_{p}(s)$ is almost unique (or robust), we use that fact to argue about the
distance between $s$ and any approximate median of the traces. Let
$s_{1},s_{2},s_{3}$ be three independent traces of $s$, generated by $R_{p}$.
We can view $s_{1}$ as a uniformly random string, and $s_{2},s_{3}$ are
generated from $s_{1}$ by a insertion-deletion channel $R_{q}$ with a higher
noise rate $q\approx 2p$. (See Section 2 for the details.) Hence, any near-
optimal alignment between $s_{1},s_{2}$ and $s_{1},s_{3}$ “agree” with the
planted alignment $A^{q}$ induced by $R_{q}$ (denoted by $A_{1,2}^{q}$ and
$A_{1,3}^{q}$ respectively). Next, we consider the alignment $A_{1,2}$ from
$s_{1}$ to $s_{2}$ via $s$, that we get by composing the planted alignment
from $s_{1}$ to $s$ induced by $R_{p}$ (actually the inverse of the alignment
from $s$ to $s_{1}$) with the planted alignment from $s$ to $s_{2}$ induced by
$R_{p}$. Similarly, consider the alignment $A_{1,3}$ from $s_{1}$ to $s_{3}$
via $s$. Then we take any $(1+\epsilon)$-approximate median $x_{\textrm{med}}$
of $\\{s_{1},s_{2},s_{3}\\}$. Consider an optimal alignment between
$s_{1},x_{\textrm{med}}$, and $x_{\textrm{med}},s_{2}$, and
$x_{\textrm{med}},s_{3}$. Use these three alignments to define an alignment
$M_{1,2}$ from $s_{1}$ to $s_{2}$ via $x_{\textrm{med}}$, and an alignment
$M_{1,3}$ from $s_{1}$ to $s_{3}$ via $x_{\textrm{med}}$. It is not hard to
argue that both $A_{1,2}$ and $M_{1,2}$ are near-optimal alignments between
$s_{1},s_{2}$. Thus, both of them agree with the planted alignment
$A_{1,2}^{q}$. Similarly, both $A_{1,3}$ and $M_{1,3}$ agree with the planted
alignment $A_{1,3}^{q}$. Observe, $s_{2},s_{3}$ are not independently
generated from $s_{1}$ by $R_{q}$. The overlap between $A_{1,2}^{q}$ and
$A_{1,3}^{q}$ essentially provides an alignment from $s_{1}$ to $s$. Again,
using the robustness property of the planted alignment, this overlap between
$A_{1,2}^{q}$ and $A_{1,3}^{q}$ agrees with the planted alignment from $s_{1}$
to $s$ by $A^{p}$ (actually the inverse of the alignment from $s$ to $s_{1}$).
On the other hand, since $M_{1,2}$ agrees with $A_{1,2}^{q}$ and $M_{1,3}$
agrees with $A_{1,3}^{q}$, there is also a huge agreement between the overlap
of $M_{1,2},M_{1,3}$ and the overlap of $A_{1,2}^{q},A_{1,3}^{q}$. The overlap
between $M_{1,2},M_{1,3}$ is essentially the optimal alignment from $s_{1}$ to
$x_{\textrm{med}}$ (that we have considered before). This in turn implies that
there is a huge agreement between the optimal alignment from $s_{1}$ to
$x_{\textrm{med}}$ and the planted alignment from $s_{1}$ to $s$ by $R_{p}$.
Hence, we can deduce that $x_{\textrm{med}}$ and $s$ are the same in most of
the portions, and thus has small edit distance. We provide the detailed
analysis in Section 4.

###  1.3 Preliminaries

#### Alignments.

For two strings $x,y$ of length $n$, an alignment is a function
$A:[n]\to[n]\cup\\{\bot\\}$ that is monotonically increasing on the _support_
of $A$, defined as $\operatorname{supp}(A)\coloneqq A^{-1}([n])$, and also
satisfies $x[i]=y[A(i)]$ for all $i\in\operatorname{supp}(A)$. An alignment is
essentially a common subsequence of $x,y$, but provides the relevant location
information. Define the _length_ (or support size) of the alignment as
$\operatorname{len}(A)\coloneqq|\operatorname{supp}(A)|$, i.e., the number of
positions in $x$ (equivalently in $y$) that are matched by $A$. Define the
_cost of $A$_ to be the number of positions in $x$ and in $y$ that are not
matched by $A$, i.e., $\operatorname{cost}(A)\coloneqq
2(n-\operatorname{len}(A))$. Let $ED(x,y)$ denotes the minimum cost of an
alignment between $x,y$.

Given a substring $x^{\prime}=x[i_{1},i_{2}]$ of $x$, let
$\ell_{1}\coloneqq\min{\\{k\in[i_{1},i_{2}]\mid A(k)\neq\bot\\}}$ and
$\ell_{2}\coloneqq\max{\\{k\in[i_{1},i_{2}]\mid A(k)\neq\bot\\}}$, be the
first and last positions in the substring $x^{\prime}$ that are matched by
alignment $A$. If the above is not well-defined, i.e., $A(k)=\bot$ for all
$k\in[i_{1},i_{2}]$, then by convention $\ell_{1}=\ell_{2}=0$. Let
$A(x^{\prime})\coloneqq y[A(\ell_{1}),A(\ell_{2})]$ be the _mapping_ of
$x^{\prime}$ under $A$. If $\ell_{1}=\ell_{2}=0$, then by convention
$y^{\prime}$ is an empty string. Let
$\mathcal{U}_{x^{\prime}}\coloneqq\\{i_{1}\leq k\leq
i_{2};k\notin\operatorname{supp}(A)\\}$ be the positions in $x^{\prime}$ that
are not aligned by $A$, and similarly let $\mathcal{U}_{y^{\prime}}$ be the
positions in $y^{\prime}$ not aligned by $A$. These quantities are related
because the number of matched positions in $x^{\prime}$ is the same as in
$y^{\prime}$, giving us
$|x^{\prime}|-|\mathcal{U}_{x^{\prime}}|=|y^{\prime}|-|\mathcal{U}_{y^{\prime}}|$.
Define the _cost of alignment $A$ on substring $x^{\prime}$_ to be

$\operatorname{cost}_{A}(x^{\prime})\coloneqq|\mathcal{U}_{x^{\prime}}|+|\mathcal{U}_{y^{\prime}}|.$

By abusing the notation, sometimes we will also use
$\operatorname{cost}_{A}([i_{1},i_{2}])$ in place of
$\operatorname{cost}_{A}(x^{\prime})$. These definitions easily extend to
strings of non-equal length, and even of infinite length.

######  Lemma 1.3.

Given two strings $x,y$ and an alignment $A$, let $x_{1},\dots,x_{p}$ be
disjoint substrings of $x$. Then

  1. 1.

$A(x_{1}),\dots,A(x_{p})$ are disjoint substrings of $y$; and

  2. 2.

$\operatorname{cost}_{A}(x)\geq\sum_{i\in[p]}\operatorname{cost}_{A}(x_{i})$

###### Proof.

The first claim directly follows from the fact that $x_{1},\dots,x_{p}$ are
disjoint and $A$ is monotonically increasing.

Since $x_{1},\dots,x_{p}$ are disjoint, also
$\mathcal{U}_{A(x_{1})},\dots,\mathcal{U}_{A(x_{p})}$ are disjoint. Similarly,
since $A(x_{1}),\dots,A(x_{p})$ are disjoint, also
$\mathcal{U}_{x_{1}},\dots,\mathcal{U}_{x_{p}}$ are disjoint. Therefore,
$\operatorname{cost}_{A}(x)\geq\sum_{i\in[p]}(|\mathcal{U}_{x_{1}}|+|\mathcal{U}_{A(x_{1})}|)$.
Hence we can claim
$\operatorname{cost}_{A}(x)\geq\sum_{i\in[p]}\operatorname{cost}_{A}(x_{i})$.
∎

For an alignment $A:[n]\to[n]\cup\\{\bot\\}$, we define the inverse alignment
$A^{-1}:[n]\to[n]\cup\\{\bot\\}$ as follows: For each $j\in[n]$, if $A(i)=j$
for some $i\in[n]$, set $A^{-1}(j)=i$; otherwise, set $A^{-1}(j)=\bot$.

We use the notation $\circ$ for composition of two functions. Composition of
two alignments (or inverse of alignments) is defined in a natural way.

#### Approximate Median.

Given a set $S\subseteq\Sigma^{*}$ and a string $y\in\Sigma^{*}$, we refer the
quantity $\sum_{x\in S}\operatorname{ED}(y,x)$ by the _median objective value_
of $S$ with respect to $y$, denoted by $\texttt{Obj}(S,y)$.

Given a set $S\subseteq\Sigma^{*}$, a _median_ of $S$ is a string
$y^{*}\in\Sigma^{*}$ (not necessarily from $S$) such that
$\texttt{Obj}(S,y^{*})$ is minimized, i.e.,
$y^{*}=\operatorname*{arg\,min}_{y\in\Sigma^{*}}\texttt{Obj}(S,y)$. We refer
$\texttt{Obj}(S,y^{*})$ by $\texttt{OPT}(S)$. Whenever it will be clear from
the context, for brevity we will drop $S$ from both $\texttt{Obj}(S,y)$ and
$\texttt{OPT}(S)$. We call a string $\tilde{y}$ a _$c$ -approximate median_,
for some $c>0$, of $S$ iff $\texttt{Obj}(S,\tilde{y})\leq
c\cdot\texttt{OPT}(S)$.

##  2 Probabilistic Generative Model

Let us first introduce a probabilistic generative model. For simplicity, our
model is defined using infinite-length strings, but our algorithmic analysis
will consider only a finite prefix of each string. Fixing a finite alphabet
$\Sigma$, we denote by $\Sigma^{\mathbb{N}}$ the set of all infinite-length
strings over $\Sigma$. We write $x\odot y$ to denote the concatenation of two
finite-length strings $x$ and $y$.

We actually describe two probabilistic models that are equivalent. The first
model $R_{p}$ is just the insertion-deletion channel mentioned in Section 1.
These models are given an arbitrary string $x$ (base string) to generate a
random string $y$ (a trace), but in our intended application $x$ is usually a
random string. The second model $G_{p}$ consists of two stages, first
“planting” an alignment between two strings, and only then placing random
symbols (accordingly). This is more convenient in the analysis, because we
often want to condition on the planted alignment and rely on the randomness in
choosing symbols.

#### Model $R_{p}(x)$.

Given an infinite-length string $x\in\Sigma^{\mathbb{N}}$ and a parameter
$p\in[0,1]$. Consider the following random procedure:

  1. 1.

Initialize $i=1$. (We use $i$ to point to the current index positions of the
input string.) Also, initialize an empty string $Out$.

  2. 2.

Do the following independently at random:

    1. (a)

With probability $1-p$, set $Out\leftarrow Out\odot x[i]$ and increment $i$.
(Match $x[i]$.)

    2. (b)

With probability $p/2$, increment $i$. (Delete $x[i]$.)

    3. (c)

With probability $p/2$, choose independently uniformly at random a character
$a\in\Sigma$ and set $Out\leftarrow Out\odot a$. (Insert a random character.)

We call this procedure $R_{p}$, and denote the randomized output string $Out$
by $R_{p}(x)$.

#### Model $G_{p}(x)$.

This model first provides a randomized mapping (alignment)
$A^{p}:\mathbb{N}\to\mathbb{N}\cup\\{\bot\\}$, and then uses this alignment
(and $x$) to generate the output string. First, given a parameter $p\in[0,1]$,
consider the following random procedure to get a mapping $A^{p}$:

  1. 1.

Initialize $i=1$ and $j=1$. (Indices of current positions in the input and
output strings, respectively.)

  2. 2.

Do the following independently at random:

    1. (a)

With probability $1-p$, set $A^{p}(i)\leftarrow j$ and increment both $i$ and
$j$. (Match $x[i]$.)

    2. (b)

With probability $p/2$, set $A^{p}(i)\leftarrow\bot$ and increment $i$.
(Delete $x[i]$.)

    3. (c)

With probability $p/2$, increment $j$. (Insertion.)

Next, use this $A^{p}$ and a given string $x\in\Sigma^{\mathbb{N}}$ to
generate a string $y\in\Sigma^{\mathbb{N}}$ as follows. For each
$j\in\mathbb{N}$,

  * •

If there is $i\in\mathbb{N}$ with $A^{p}(i)=j$ then set $y[j]\leftarrow x[i]$.
(Match $x[i]$.)

  * •

Otherwise, choose independently uniformly at random a character $a\in\Sigma$
and set $y[j]\leftarrow a$. (Insert a random character.)

We denote by $G_{p}(x)$ the randomized string $y$ generated as above. By
construction, $A^{p}$ is an alignment between $x$ and $G_{p}(x)$.

#### Basic Properties.

We claim next that $R_{p}$ and $G_{p}$ are equivalent, which is useful because
we find it more convenient to analyze $G_{p}$. We use
$X_{1}\stackrel{{\scriptstyle\mathrm{dist}}}{{=}}X_{2}$ to denote that two
random variable $X_{i}\sim D_{i}$, $i\in\\{1,2\\}$ have equal distribution,
i.e., $D_{1}=D_{2}$. The next two propositions are immediate.

######  Proposition 2.1.

For every string $x\in\Sigma^{\mathbb{N}}$ and $p\in[0,1]$, we have
$R_{p}(x)\stackrel{{\scriptstyle\mathrm{dist}}}{{=}}G_{p}(x)$.

######  Proposition 2.2 (Transitivity).

For every $x\in\Sigma^{\mathbb{N}}$ and $p\in[0,1]$, let

$q(p)\coloneqq\frac{p(4-3p)}{2-p^{2}}.$ (2)

Then $G_{p}(G_{p}(x))\stackrel{{\scriptstyle\mathrm{dist}}}{{=}}G_{q(p)}(x)$.

#### Additional Properties (Random Base String).

Let $U$ be the uniform distribution over strings $x\in\Sigma^{\mathbb{N}}$,
i.e., each character $x[i]$ is chosen uniformly at random and independently
from $\Sigma$. We now state two important observations regarding the process
$G_{p}$. The first one is a direct corollary of Proposition 2.2. The second
observation follows because the probability of insertion is the same as that
of deletion at any index in the random process $G_{p}$.

######  Corollary 2.3 (Transitivity).

Let $p\in[0,1]$ and let $q(p)$ be as in (2). Draw a random string $X\sim U$,
and use it to draw $Y\sim G_{p}(G_{p}(X))$ and $Z\sim G_{q(p)}(X)$. Then
$(X,Y)\stackrel{{\scriptstyle\mathrm{dist}}}{{=}}(X,Z)$.

######  Proposition 2.4 (Symmetry).

Let $p\in[0,1]$. Draw a random string $X\sim U$ and use it to draw another
string $Y\sim G_{p}(X)$. Then
$(X,Y)\stackrel{{\scriptstyle\mathrm{dist}}}{{=}}(Y,X)$.

##  3 Robustness of the Insertion-Deletion Channel

In this section we analyze the finite-length version of our probabilistic
model $G_{p}$ (from Section 2), which gets a random string $x\in\Sigma^{n}$
and generates from it a trace $y$. We provide a high-probability estimates for
the cost of the planted alignment $A^{p}$ between $x$ and $y$ (Lemma 3.1), and
for the optimal alignment (i.e., edit distance) between the two strings
(Lemmas 3.3 and 3.4). It follows that with high probability the planted
alignment $A^{p}$ is near-optimal. We then further prove that the planted
alignment is robust, in the sense that, with high probability, every near-
optimal alignment between the two strings must “agree” with the planted
alignment $A^{p}$ on all but a small fraction of the edit operations (Lemmas
3.6 and 3.7).

Assume henceforth that $x\in\Sigma^{n}$ is a random string $x$, and given a
parameter $p>0$, generate from it a string $y$ by the random process $G_{p}$
described in Section 2, denoting by $A^{p}_{x,y}$ the random mapping used in
this process. A small difference here is that now $x$ has finite length, but
it can also be viewed as an $n$-length prefix of an infinite string.
Similarly, now $y$ has finite length and is obtained by applying $G_{p}$ on
$x[1,n]$, and it can be viewed also as a finite prefix of an infinite string.

Let $\mathcal{I}^{A^{p}_{x,y}}$ be the set of indices $i\in[n]$, for which
process $G_{p}$ performs at least one insert/delete operation after (not
including) $x[i-1]$ and up to (including) $x[i]$ (i.e., inserting at least one
character between $x[i-1],x[i]$, or deleting $x[i]$, or both). This
information can clearly be described using $A^{p}_{x,y}$ alone (independently
of $x$ and of the symbols chosen for insertions to $y$ in the second stage of
process $G_{p}$); we omit the formal definition. When clear from the context,
we shorten $\mathcal{I}^{A^{p}_{x,y}}$ to $\mathcal{I}$.

######  Lemma 3.1.

For every $i\in[n]$, the probability that $i\in\mathcal{I}$ is

$r=r(p)\coloneqq\sum_{k=1}^{\infty}(2-p)(p/2)^{k}=p.$ (3)

For all $\epsilon\in[r,1]$, we have
$\Pr[|\mathcal{I}|\notin(1\pm\epsilon)rn]\leq 2e^{-{\epsilon^{2}rn}/{3}}$.

###### Proof.

For every $i\in[n]$, the probability that $G_{p}$ performs $k\geq 1$ edit
operations after $x[i-1]$ and up to $x[i]$ is
$(p/2)^{k}+(p/2)^{k}(1-p)=(p/2)^{k}(2-p)$, where the first summand represents
$k-1$ insertions and one deletion, and the second summand represents $k$
insertions and no deletion. Thus
$r=\Pr[i\in\mathcal{I}]=\sum_{k=1}^{\infty}(2-p)(p/2)^{k}=p$.

For every $i\in[n]$, the probability it appears in $\mathcal{I}$ is $r$. Then
$\operatorname*{{\mathbb{E}}}[|\mathcal{I}|]=r\cdot n$. These events are
independent, hence by Chernoff’s bound, the probability that
$|\mathcal{I}|\notin(1\pm\epsilon)rn$ is at most $2e^{-{\epsilon^{2}rn}/{3}}$.
∎

As shown in (3), $r\coloneqq\sum_{k=1}^{\infty}(2-p)(p/2)^{k}=p$. Hence from
now on we replace $r$ by $p$. Given $\epsilon\in[p,1]$ and $i\in[n]$, we
consider the event $\mathcal{S}_{\epsilon}(i)$, which informally means that
process $G_{p}$ makes a single “well-spaced” edit operation at position $i$,
i.e., there is an edit operation at position $i$ and no other edit operations
within $(\tfrac{2\epsilon}{p}$ positions away from $i$. To define it formally,
we separate it into two cases, an insertion and a deletion. Observe that these
events depend on $A^{p}$ alone. Let $\mathcal{S}^{del}_{\epsilon}(i)$ be the
event that

  1. 1.

$A^{p}(i+1)=A^{p}(i-1)+1$ (thus $A^{p}(i)=\bot$); and

  2. 2.

for all $j\in[2,\frac{2\epsilon}{p}]$, we have $A^{p}(i+j)=A^{p}(i+j-1)+1$ and
$A^{p}(i-j)=A^{p}(i-j+1)-1$ (in particular, they are not $\bot$).

Similarly, let $\mathcal{S}^{ins}_{\epsilon}(i)$ be the event that

  1. 1.

$A^{p}(i)=A^{p}(i-1)+2$ (thus no index is mapped to $A^{p}(i-1)+1$);

  2. 2.

for all $j\in[1,\frac{2\epsilon}{p}]$, we have $A^{p}(i+j)=A^{p}(i+j-1)+1$;
and

  3. 3.

for all $j\in[2,\frac{2\epsilon}{p}]$, and $A^{p}(i-j)=A^{p}(i-j+1)-1$.

Now define the set of indices for which any of these two events happens

$\mathcal{\tilde{I}}_{\epsilon}^{A^{p}_{x,y}}\coloneqq{\\{i\in[n]\mid\text{event
$\mathcal{S}_{\epsilon}(i)\coloneqq\mathcal{S}^{del}_{\epsilon}(i)\cup\mathcal{S}^{ins}_{\epsilon}(i)$
occurs}\\}}.$

When clear from the context, we shorten
$\mathcal{\tilde{I}}_{\epsilon}^{A^{p}_{x,y}}$ to $\tilde{\mathcal{I}}$.

######  Lemma 3.2.

For every $\epsilon\geq p$, we have
$\Pr[|\mathcal{\tilde{I}}|\leq(1-5\epsilon)pn]\leq
e^{-{\epsilon^{2}p^{2}n}/{2}}$.

###### Proof.

For an index $i\in[n]$, define the random variable $X_{i}\in{\\{0,1\\}}$ to be
an indicator for the union event
$\mathcal{S}^{del}_{\epsilon}(i)\cup\mathcal{S}^{ins}_{\epsilon}(i)$. Observe
that each of the two events, $\mathcal{S}^{del}_{\epsilon}(i)$ and
$\mathcal{S}^{ins}_{\epsilon}(i)$, occurs with probability
$\frac{p}{2}(1-p)^{4\epsilon/p}/(1-p/2)$, and these events are disjoint.
Hence, $\Pr[X_{i}=1]=p(1-p)^{4\epsilon/p}/(1-p/2)\geq p(1-p)^{4\epsilon/p}\geq
p(1-4\epsilon)$

Next we prove a deviation bound for the random variable
$X\coloneqq\sum_{i\in[n]}X_{i}=|\mathcal{\tilde{I}}|$, which has expectation
is $\operatorname*{{\mathbb{E}}}[X]\geq(1-4\epsilon)pn$. Observe that
${\\{X|X_{1},\ldots,X_{i}\\}}_{i=1}^{n}$ is a Doob Martingale, and let us
apply the method of bounded differences. Revealing $X_{i}$ (after
$X_{1},\ldots,X_{i-1}$ are already known) might affect the value of $X_{j}$’s
for $j<i+\frac{4\epsilon}{p}$, but by definition their sum is bounded
$\sum_{i\leq j<i+\frac{4\epsilon}{p}}X_{j}\leq 2$, while the other $X_{j}$’s
are independent of $X_{i}$ hence the expectation of $\sum_{j\geq
i+\frac{2\epsilon}{p}}X_{j}$ by revealing it. Together, we see that
$|\operatorname*{{\mathbb{E}}}[X|X_{1},\dots,X_{i}]-\operatorname*{{\mathbb{E}}}[X|X_{1},\dots,X_{i-1}]|\leq
2$, and therefore by Azuma’s inequality,
$\Pr[X\leq(1-5\epsilon)pn]\leq\Pr[X\leq\operatorname*{{\mathbb{E}}}[X]-\epsilon
pn]<e^{-2\epsilon^{2}p^{2}n^{2}/(4n)}=e^{-\epsilon^{2}p^{2}n/2}$. ∎

#### Edit Distance (Optimal Alignment) between $x,y$.

For each $i\in\mathcal{\tilde{I}}$, define a window
$W_{\epsilon}^{i}=[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}]$.

######  Lemma 3.3.

For every $\epsilon\in[15p\log\frac{1}{p},\frac{1}{6}]$, we have
$\Pr[\operatorname{ED}(x,y)<(1-6\epsilon)pn]\leq 2e^{-\epsilon^{2}p^{2}n/2}$.

At a high level, our proof avoids a direct union bound over all low-cost
potential alignments, because there are too many of them. Instead, we
introduce a smaller set of basic events that “covers” all these potential
alignments, which is equivalent to carefully grouping the potential alignments
to get a more “efficient” union bound.

###### Proof.

We assume henceforth that $A^{p}$ (the alignment from process $G_{p}$) is
known and satisfies $|\mathcal{\tilde{I}}|>(1-5\epsilon)pn$, which occurs with
high probability by Lemma 3.2. In other words, we condition on $A^{p}$ and
proceed with a probabilistic analysis based only on the randomness of $x$ and
of the characters inserted into $y$.

Our plan is to define basic events $\mathcal{E}_{S,\bar{S}}$ for every two
subsets $S,\bar{S}\subset[n]$ of the same size $\ell=|S|=|\bar{S}|$,
representing positions in $x$ and in $y$, respectively. We will then show that
our event of interest is bounded by these events

$\displaystyle{\Big{\\{}\operatorname{ED}(x,y)<(1-6\epsilon)pn\Big{\\}}}\subseteq\bigcup_{S,\bar{S}\mid\ell=\epsilon
pn}\mathcal{E}_{S,\bar{S}},$ (4)

and bound the probability of each basic event by

$\displaystyle\Pr[\mathcal{E}_{S,\bar{S}}]\leq|\Sigma|^{-\epsilon\ell/(3p)}.$
(5)

The proof will then follow easily using a union bound and a simple
calculation.

To define the basic event $\mathcal{E}_{S,\bar{S}}$, we need some notation.
Write $S=\\{i_{1},i_{2},\dots,i_{\ell}\\}$ in increasing order, and similarly
$\bar{S}=\\{\bar{i}_{1},\bar{i}_{2},\dots,\bar{i}_{\ell}\\}$, and use these to
define $\ell$ blocks in $x$ and in $y$, namely,
$B_{i_{j}}=x[i_{j}-\tfrac{\epsilon}{p},i_{j}+\tfrac{\epsilon}{p}]$ and
$\bar{B}_{i_{j}}=y[\bar{i}_{j}-\tfrac{\epsilon}{p},\bar{i}_{j}+\tfrac{\epsilon}{p}]$.
Notice that all the blocks are of the same length $1+2\tfrac{\epsilon}{p}$.
Now define $\mathcal{E}_{S,\bar{S}}$ to be the event that (i)
$S\subseteq\mathcal{\tilde{I}}$;222This implies that the blocks
$B_{i_{1}},\dots,B_{i_{\ell}}$ in $x$ are disjoint. (ii) the blocks
$\bar{B}_{\bar{}i_{1}},\dots,\bar{B}_{\bar{i}_{\ell}}$ in $y$ are disjoint;
and (iii) each block $B_{i_{j}}$ in $x$ is equal to its corresponding block
$\bar{B}_{\bar{i}_{j}}$ in $y$. Notice that conditions (i) and (ii) actually
depend only on $A^{p}$, and thus can be viewed as restrictions on the choice
of $S,\bar{S}$ in (4); with this viewpoint in mind, we can simply write

$\mathcal{E}_{S,\bar{S}}\coloneqq{\\{B_{i_{1}}=\bar{B}_{\bar{i}_{1}},\ldots,B_{i_{\ell}}=\bar{B}_{\bar{i}_{\ell}}\\}}.$

We proceed to prove (4). Suppose there is an alignment $M$ from $x$ to $y$
with $\operatorname{cost}(M)<(1-6\epsilon)pn$, and consider its cost around
each position $i\in\mathcal{\tilde{I}}$, namely,
$\operatorname{cost}_{M}[i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}]$. These
intervals in $x$ are disjoint (by definition of $\mathcal{\tilde{I}}$), and
thus by Lemma 1.3,

$\sum_{i\in\mathcal{\tilde{I}}}\operatorname{cost}_{M}(x[i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}])\leq\operatorname{cost}(M)<(1-6\epsilon)pn.$

Let $S\subset\mathcal{\tilde{I}}$ include (the indices of) the summands equal
to $0$. Each other summand contributes at least $1$, thus
$|\mathcal{\tilde{I}}|-|S|=|\mathcal{\tilde{I}}\setminus S|\cdot
1<(1-6\epsilon)pn$ and by rearranging
$|S|>|\mathcal{\tilde{I}}|-(1-6\epsilon)pn>\epsilon pn$. To get the exact size
$|S|=\epsilon pn$, we can replace $S$ with an arbitrary subset of it of the
exact size. Now define $\bar{S}={\\{M(i)\mid i\in S\\}}$. It is easy to verify
that the event $\mathcal{E}_{S,\bar{S}}$ holds. Indeed, each $i\in S$
satisfies
$\operatorname{cost}_{M}[i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}]=0$,
which implies $M(i)\neq\bot$, and thus $|\bar{S}|=|S|$. Moreover, the block
$x[i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}]$ in $x$ is equal to the
corresponds block in $y$, and these blocks in $y$ are disjoint. This completes
the proof of (4).

Next, we prove (5). Fix $S,\bar{S}\subset[n]$ of the same size $\ell$, and
assume requirements (i) and (ii) hold (otherwise, the probability is 0). Let
$B_{i_{j}}$ and $\bar{B}_{\bar{i}_{j}}$ be the corresponding blocks in $x$ and
in $y$. Consider for now a given $j\in[\ell]$. The requirement
$B_{i_{j}}=\bar{B}_{\bar{i}_{j}}$ means that for all
$t\in{\\{-\tfrac{\epsilon}{p},\ldots,0,\ldots,+\tfrac{\epsilon}{p}\\}}$ we
require $x[i_{j}+t]=y[\bar{i}_{j}+t]$. The issue is that $x$ and $y$ are
random but correlated through $A^{p}$; in particular, the symbols $x[i_{j}+t]$
and $y[\bar{i}_{j}+t]$ are chosen independently at random unless $A^{p}$
aligns their positions, i.e., $A^{p}(i_{j}+t)=\bar{i}_{j}+t$. The key
observation is that this last event cannot happen for both $t=-1$ and $t=1$,
because in that case,
$A^{p}(i_{j}+1)-A^{p}(i_{j}-1)=\bar{i}_{j}+1-(\bar{i}_{j}-1)=2$; however,
$i_{j}\in\mathcal{\tilde{I}}$ implies that $A^{p}$ has exactly one edit
operation (insertion or deletion) in the interval $[i_{j}-1,i_{j}+1]$ (and not
at its endpoints), thus $A^{p}(i_{j}+1)-A^{p}(i_{j}-1)\in{\\{1,3\\}}$. Assume
first that $A^{p}(i_{j}+t)\neq\bar{i}_{j}+t$ for $t=1$. Then the same must
hold also for all $t=2,\ldots,\tfrac{\epsilon}{p}$; indeed, we again use that
$i_{j}\in\mathcal{\tilde{I}}$, which implies that $A^{p}$ has no edit
operations near position $i_{j}$, thus
$A^{p}(i_{j}+t)=A^{p}(i_{j}+1)+(t-1)\neq\bar{i}_{j}+1+(t-1)$. The argument for
$t=-1$ is similar, and we conclude that the requirement
$B_{i_{j}}=\bar{B}_{\bar{i}_{j}}$ encompasses at least $\tfrac{\epsilon}{p}$
requirements of the form $x[i_{j}+t]=y[\bar{i}_{j}+t]$ where these two
positions are not aligned by $A^{p}$, and thus these two symbols are chosen
independently at random.

The above argument applies to every $j\in[\ell]$, yielding overall at least
$\ell\cdot\tfrac{\epsilon}{p}$ requirements of the form
$x[i_{j}+t]=y[\bar{i}_{j}+t]$, where these two symbols are chosen
independently at random. Observe that each $y[\bar{i}_{j}+t]$ is either a
character $x[t^{\prime}]$ (for $t^{\prime}$ arising from $A^{p}$) or
completely independent. Since each character of $x$ appears in at most $2$
requirements (once on each side), we can extract a subset of at one-third of
the requirements such that the positions in $x$ appearing there are all
distinct, and thus the events are independent.333To see this, consider an
auxiliary graph whose a vertex for each character $x[t]$, and connect two by
an edge if they appear in the same constraint. Since every vertex has degree
at most $2$, a greedy matching contains at least one third of the edges.  We
overall obtain at least $\tfrac{1}{3}\ell\cdot\tfrac{\epsilon}{p}$
requirements, each occurring independently with probability $1/|\Sigma|$, and
thus

$\Pr[\mathcal{E}_{S,\bar{S}}]\leq|\Sigma|^{-\epsilon\ell/(3p)}.$

Finally, we are in position to prove the lemma. Combining (4) and (5) and a
union bound

$\displaystyle\Pr[\operatorname{ED}(x,y)<(1-6\epsilon)pn]$
$\displaystyle\leq\binom{n}{\ell}^{2}\cdot|\Sigma|^{-\epsilon\ell/(3p)}\leq\Big{(}\frac{ne}{\ell}\Big{)}^{2\ell}\cdot
2^{-\epsilon\ell/(3p)}=\Big{(}\frac{e}{\epsilon p}\Big{)}^{2\epsilon pn}\cdot
2^{-\epsilon^{2}n/3}$ $\displaystyle\leq(p^{2})^{-2\epsilon pn}\cdot
2^{-\epsilon(15p\log(1/p))n/3}\leq p^{-4\epsilon pn+5\epsilon pn}\leq
p^{\epsilon pn}.$

Recall that this was all conditioned on $A^{p}$, which had error probability
at most $e^{-{\epsilon^{2}p^{2}n}/{2}}$ (by Lemma 3.2), and now Lemma 3.3
follows by a union bound. ∎

A similar bound holds for even smaller values of $\epsilon$, provided that the
alphabet size is large. The proof is the same, except for the final
calculation.

######  Lemma 3.4.

Suppose $|\Sigma|\geq(\frac{1}{p})^{15}$. Then for every
$\epsilon\in[p,\frac{1}{6}]$, we have
$\Pr[\operatorname{ED}(x,y)<(1-6\epsilon)pn]\leq 2e^{-\epsilon^{2}p^{2}n/2}$.

Following an argument similar to the proof of Lemma 3.3 we can make the
following claim.

######  Lemma 3.5.

Let $\epsilon\in[15p\log\frac{1}{p},\frac{1}{6}]$. Then with probability at
least $1-2e^{-\epsilon^{2}p^{2}n/2}$, every alignment $M$ between $x,y$
satisfies
$|\\{i\in\mathcal{\tilde{I}}\mid\operatorname{cost}_{M}(x[i-\frac{\epsilon}{r},i+\frac{\epsilon}{r}])=0\\}|\leq
6\epsilon pn$.

#### Near-Optimal Alignments between $x,y$.

Given $\epsilon>0$, a potential alignment $M$ between $x,y$, and an index
$i\in[n]$, define the event

$\mathcal{E}_{\epsilon}^{M}(i)\coloneqq\begin{cases}A^{p}(i-\tfrac{\epsilon}{p})=\min\\{M(k)\neq\bot\mid
k\in[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}]\\};\text{ and }\\\
A^{p}(i+\tfrac{\epsilon}{p})=\max\\{M(k)\neq\bot\mid
k\in[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}]\\}.\end{cases}$ (6)

By convention, $\mathcal{E}_{\epsilon}^{M}(i)$ is _not_ satisfied if the
minimization/maximization is over the empty set (because $M(k)=\bot$ for all
relevant $k$). We will only use it for $i\in\mathcal{\tilde{I}}$, in which
case both $A^{p}(i-\frac{\epsilon}{p}),A^{p}(i+\frac{\epsilon}{p})\neq\bot$.
Intuitively, this event means that $A^{p}$ and $M$ agree on the block
boundaries; for example, in the simpler case where all relevant
$M(k)\neq\bot$, this event simply means that
$A^{p}(i-\tfrac{\epsilon}{p})=M(i-\tfrac{\epsilon}{p})$ and
$A^{p}(i+\tfrac{\epsilon}{p})=M(i+\tfrac{\epsilon}{p})$.

Denote the set of indices where the event $\mathcal{E}_{\epsilon}^{M}(i)$
occurs and the cost of $M$ over substring
$x[i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}]$ is $1$, by

$\mathcal{\tilde{I}}_{\epsilon,M}^{A^{p}_{x,y}}\coloneqq{\\{i\in\mathcal{\tilde{I}}\mid\text{
event $\mathcal{E}_{\epsilon}^{M}(i)$ occurs and
$\operatorname{cost}_{M}([i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}])=1$
}\\}}.$

When clear from the context, we shorten
$\mathcal{\tilde{I}}_{\epsilon,M}^{A^{p}_{x,y}}$ to $\mathcal{\tilde{I}}_{M}$.

######  Lemma 3.6.

Let $\epsilon\in[42p\log\frac{1}{p},\frac{1}{6}]$ and
$p\leq\delta\leq\epsilon$. Then with probability at least
$1-4e^{-\frac{\epsilon^{2}p^{2}n}{2}}$, every alignment $M$ between $x,y$ with
$\operatorname{cost}(M)\leq(1+\delta)pn$ satisfies
$|\mathcal{\tilde{I}}_{M}|\geq(1-23\epsilon-\delta)pn$.

At a high level, the proof follows the outline of Lemma 3.3, and avoids a
direct union bound over all (relevant) potential alignments, because there are
too many of them. Instead, we introduce a smaller set of basic events that
“covers” all these potential alignments. Specifically, we show that an
alignment $M$ violating the above gives rise to a large set $\tilde{S}$ of
indices $i\in\mathcal{\tilde{I}}$, where a corresponding block $B_{i}$ in $x$
is matched by $M$ to a block $\bar{B}_{i}$ in $y$ with cost at most $1$, and
event $\mathcal{E}^{M}_{\epsilon}(i)$ is not satisfied. It then remains to
show that the probability that such a large set $\tilde{S}$ exists is very
small. A crucial difference is that the cost of matching $B_{i}$ to
$\bar{B}_{i}$ is at most $1$ here (compared with $0$ in the proof of Lemma
3.3). It makes the notation more cumbersome, e.g, the length of $\bar{B}_{i}$
can be either $|B_{i}|$, $|B_{i}|-1$, or $|B_{i}|+1$, and the analysis more
elaborate with additional cases that require new technical ideas. We provide
this proof in Appendix A.

A similar bound holds for even smaller values of $\epsilon$, provided that the
alphabet size is large.

######  Lemma 3.7.

Suppose $|\Sigma|\geq(\frac{1}{p})^{42}$. Then for every
$\epsilon\in[p,\frac{1}{6}]$ and every $p\leq\delta\leq\epsilon$, with
probability at least $1-4e^{-\frac{\epsilon^{2}p^{2}n}{2}}$, every alignment
$M$ between $x,y$ with $\operatorname{cost}(M)\leq(1+\delta)pn$ satisfies
$|\mathcal{\tilde{I}}_{M}|\geq(1-23\epsilon-\delta)pn$.

##  4 Robustness of Approximate Median

In this section, we consider the (approximate) median string problem on a set
of strings generated by our probabilistic model $G_{p}$ (from Section 2). For
a random (unknown) string $s\in\Sigma^{n}$, $G_{p}$ generates a set
$S=\\{s_{1},s_{2},\cdots,s_{m}\\}$ of independent traces of $s$. We show that
with high probability, any $(1+\epsilon)$-approximate median of $S$ must be
close (in edit distance) to the unknown string $s$. In other words, any
$(1+\epsilon)$-approximate median must “agree” with the unknown string $s$ in
most of the portions. It is true even when $m=3$. In this section, we state
the results and the proofs by considering $m=3$. In particular, we prove
Theorem 1.2. At the end of the section, we remark on why such result with
three traces also directly provides a similar result for any $m>3$ traces.
Another way to interpret this result is the following. Suppose we take a set
of three traces and find its $(1+\epsilon)$-approximate median. Then if we add
more traces in the set, its $(1+\epsilon)$-approximate median does not change
by much. So in some sense, $(1+\epsilon)$-approximate median is robust in the
case of average-case traces.

For the purpose of the analysis, we start by considering infinite length
strings (as in Section 2), and then later we will move to the finite-length
versions. Recall that $U$ denotes the uniform distribution over strings
$x\in\Sigma^{\mathbb{N}}$, i.e., each character $x[i]$, for $i\in\mathbb{N}$,
is chosen uniformly at random and independently from $\Sigma$. Consider a
parameter $p\in(0,0.001)$ and define $q\coloneqq\frac{p(4-3p)}{2-p^{2}}$.
(Note, $q=2p-\Theta(p^{2})$.) Then consider the following two processes:

  * •

Process 1: Draw a string $s$ from $U$. Then draw three strings
$s_{1},s_{2},s_{3}$ independently from $G_{p}(s)$. Output the tuple
$(s,s_{1},s_{2},s_{3})$.

  * •

Process 2: Draw a string $x_{1}$ from $U$. Then draw $\bar{x}$ from
$G_{p}(x_{1})$ (and denote the corresponding alignment function by
$A_{1,\bar{x}}^{p}$). Finally, draw $x_{2},x_{3}$ independently from
$G_{p}(\bar{x})$ (and denote the corresponding alignment functions by
$A_{\bar{x},2}^{p},A_{\bar{x},3}^{p}$ respectively). Output the tuple
$(\bar{x},x_{1},x_{2},x_{3})$.

As an immediate corollary of Proposition 2.4, we know that the distributions
on $(s,s_{1})$ and $(\bar{x},x_{1})$ are the same. So we conclude the
following about the above two processes.

######  Claim 4.1.

The probability distributions on $(s,s_{1},s_{2},s_{3})$ and
$(\bar{x},x_{1},x_{2},x_{3})$, the tuples generated by Process 1 and Process 2
respectively, are identical.

We want to investigate the property of an approximate median of the strings
generated through Process 1. Due to the above claim, instead of considering
the strings $s_{1},s_{2},s_{3}$ from now on we focus on $x_{1},x_{2},x_{3}$
generated through Process 2. By Proposition 2.2, both $x_{2}$ and $x_{3}$ can
be viewed as strings drawn from $G_{q}(x_{1})$. Let us use the notations
$A_{1,2}^{q}$ and $A_{1,3}^{q}$ to denote the alignment functions produced by
the random process $G_{q}$ while generating $x_{2}$ and $x_{3}$ respectively,
from $x_{1}$. We want to emphasize that the process $G_{q}$ is considered
solely for the purpose of the analysis.

Next, we use the alignments $A_{1,\bar{x}}^{p},$ $A_{\bar{x},2}^{p}$ (and
$A_{\bar{x},3}^{p}$) to define an alignment between $x_{1},x_{2}$ (and
$x_{1},x_{3}$) via $\bar{x}$. Let $A_{1,\bar{x},2}^{p}$ and
$A_{1,\bar{x},3}^{p}$ denote $A_{\bar{x},2}^{p}\circ A_{1,\bar{x}}^{p}$ and
$A_{\bar{x},3}^{p}\circ A_{1,\bar{x}}^{p}$ respectively. (See Section 1.3 for
the definition of the notation $\circ$.)

#### Median of $n$-length prefixes of $x_{1},x_{2},x_{3}$.

So far in this section we have talked about infinite length strings. From now
on we restrict ourselves to the the $n$-length prefixes of $x_{1},x_{2}$ and
$x_{3}$ denoted by $x_{1}[1,n],x_{2}[1,n]$ and $x_{3}[1,n]$ respectively. By
abusing the notations, we simply use $x_{1},x_{2}$ and $x_{3}$ to also denote
$x_{1}[1,n],x_{2}[1,n]$ and $x_{3}[1,n]$ respectively. Also, we consider the
($n$-length) restriction of all the alignment functions (defined so far)
accordingly. Again, for simplicity, we use the same notations to refer to
these restricted alignment functions.

Now, we consider the (approximate) median string problem on the set
$S=\\{x_{1},x_{2},x_{3}\\}$. Recall, for any string $y$,
$\texttt{Obj}(S,y)\coloneqq\sum_{k=1}^{3}\operatorname{ED}(x_{k},y)$, and
$\texttt{OPT}(S)=\min_{y\in\Sigma^{*}}\texttt{Obj}(S,y)$. Since throughout
this section, $S=\\{x_{1},x_{2},x_{3}\\}$, to simplify the notations, we drop
$S$ from both Obj and OPT. The main result of this section is the following.

######  Theorem 4.2.

For a large enough $n\in\mathbb{N}$ and a noise parameter $p\in(0,0.001)$, let
$\bar{x},x_{1},x_{2}$ and $x_{3}$ be the $n$-length prefixes of the strings
generated by Process 2. If $x_{\textrm{med}}$ is a $(1+\epsilon)$-approximate
median of $S=\\{x_{1},x_{2},x_{3}\\}$ for $\epsilon\in[110p\log(1/p),1/6]$,
then $\Pr[\operatorname{ED}(\bar{x},x_{\textrm{med}})\leq
195\epsilon\cdot\texttt{OPT}(S)]\geq 1-e^{-\log^{2}n}$.

We would like to emphasize that (for the simplicity in the analysis) we have
made no attempt to optimize the constants. By a more careful analysis, both
the range of $p$ and the constant involved in the bound of
$\operatorname{ED}(\bar{x},x_{\textrm{med}})$ could be improved significantly.
The above theorem together with Claim 4.1 immediately gives us Theorem 1.2.
Note, in Theorem 1.2, we do not have any length restrictions on the traces. On
the other hand, the above theorem considers $\bar{x},x_{1},x_{2}$ and $x_{3}$
to of of length $n$. However, by a standard application of Chernoff-Hoeffding
bound, it suffices to restrict ourselves to the $(n-\sqrt{n}\log n)$-length
prefixes of all the traces (of Theorem 1.2). Then we can apply the above
theorem over them, to get Theorem 1.2.

Before proving Theorem 4.2, we make a few observations on the ($n$-length
restricted) alignments between $x_{1}$ and $x_{2}$ ($x_{1}$ and $x_{3}$).
Consider an $\epsilon\in[110p\log(1/p),1/6]$. Let $x_{\textrm{med}}$ be an
(arbitrary) $(1+\epsilon)$-approximate median of $x_{1},x_{2}$ and $x_{3}$.

Let $M_{1,\textrm{med}},M_{\textrm{med},x}$ and $M_{\textrm{med},x}$ be
(arbitrary) optimal alignment from $x_{1}$ to $x_{\textrm{med}}$,
$x_{\textrm{med}}$ to $x_{2}$, and $x_{\textrm{med}}$ to $x_{3}$ respectively.
Then we define an alignment between $x_{1},x_{2}$ and $x_{1},x_{3}$ via
$x_{\textrm{med}}$. We use $M_{1,\textrm{med},2}$ and $M_{1,\textrm{med},3}$
to denote $M_{\textrm{med},2}\circ M_{1,\textrm{med}}$ and
$M_{\textrm{med},3}\circ M_{1,\textrm{med}}$ respectively. Next, we compare
the alignments $A_{1,\bar{x},2}^{p}$ ($A_{1,\bar{x},3}^{p}$) and
$M_{1,\textrm{med},2}$ ($M_{1,\textrm{med},3}$) with $A_{1,2}^{q}$
($A_{1,3}^{q}$). For that purpose, we use the notations $\mathcal{I}$ and
$\mathcal{\tilde{I}}_{\epsilon}$ with respect to the alignments $A^{p},A^{q}$
and $M$ (as defined in Section 3). For any $i\in[n]$, let $W^{i}$ denotes the
interval $[i-\epsilon/q,i+\epsilon/q]$.

Recall, for any $k\in\\{2,3\\}$,
$\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}$ is the set of all
the indices $i$ on $x_{1}$ such that there is exactly one edit operation
inside the interval $W^{i}$ on $x_{1}$ with respect to both the alignments
$M_{1,\textrm{med},k}$ and $A_{1,k}^{q}$. Now consider any such interval
$W^{i}$. Since the alignment $M_{1,\textrm{med},k}$ is obtained by
concatenating two alignments $M_{1,\textrm{med}}$ and $M_{\textrm{med},k}$,
that one edit operation inside the interval $W^{i}$ happens either in the
alignment $M_{1,\textrm{med}}$ or $M_{\textrm{med},k}$, but not in both. Now,
let us consider the indices $i$ such that in the interval $W^{i}$ that one
edit operation happens with respect to the alignment $M_{1,\textrm{med}}$.
This leads us to the following definition,

$\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\coloneqq\\{i\in\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\mid\operatorname{cost}_{M_{1,\textrm{med}}}(W^{i})=\operatorname{cost}_{M_{1,\textrm{med},k}}(W^{i})=1\\}.$

Since in the above definition we consider the cost of the interval $W^{i}$ to
be exactly one with respect to the alignment $M_{1,\textrm{med}}$, if
$M_{1,\textrm{med}}(i-\epsilon/q)=\bot$ then
$M_{1,\textrm{med}}(i-\epsilon/q+1)\neq\bot$. Similarly, if
$M_{1,\textrm{med}}(i+\epsilon/q)=\bot$ then
$M_{1,\textrm{med}}(i+\epsilon/q-1)\neq\bot$. In words, if any one of the
boundary symbols of the block $x_{1}[W^{i}]$ gets deleted then the next symbol
inside the block must be mapped to some symbol in $x_{\textrm{med}}$.

Without loss of generality, from now on we assume that for all
$i\in\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}$,
$M_{1,\textrm{med}}(i-\epsilon/q)\neq\bot$ and
$M_{1,\textrm{med}}(i+\epsilon/q)\neq\bot$. (If for some $i$, the above
assumption is not true then we need to argue with
$M_{1,\textrm{med}}(i-\epsilon/q+1)$ instead of
$M_{1,\textrm{med}}(i-\epsilon/q)$, or with
$M_{1,\textrm{med}}(i+\epsilon/q-1)$ instead of
$M_{1,\textrm{med}}(i+\epsilon/q-1)$.)

In a similar way, define $\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}$ as

$\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\coloneqq\\{i\in\mathcal{\tilde{I}}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\mid\operatorname{cost}_{A_{1,\bar{x}}^{p}}(W^{i})=\operatorname{cost}_{A_{1,\bar{x},k}^{p}}(W^{i})=1\\}.$

Now from the above definition, it is easy to observe the following.

######  Proposition 4.3.

For any $k\in\\{2,3\\}$, for all
$i\in\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}$,

$x_{\textrm{med}}[M_{1,\textrm{med}}(i-\epsilon/q),M_{1,\textrm{med}}(i+\epsilon/q)]=\bar{x}[A_{1,\bar{x}}^{p}(i-\epsilon/q),A_{1,\bar{x}}^{p}(i+\epsilon/q)].$

Let us now define a set of good events and then from now on we proceed by
assuming those good events occur.

  * •

$\mathcal{G}_{1}\coloneqq$ For each of the pairs of strings
$(x_{1},\bar{x}),(\bar{x},x_{2})$ and $(\bar{x},x_{3})$, their edit distances
are at least $(1-6\epsilon)pn-2\sqrt{n}\log n$ and at most
$(1+\epsilon)pn+2\sqrt{n}\log n$.

  * •

$\mathcal{G}_{2}\coloneqq$ For any $i\neq j\in[3]$,
$(1-6\epsilon)qn-2\sqrt{n}\log
n\leq\operatorname{ED}(x_{i},x_{j})\leq(1+\epsilon)qn+4\sqrt{n}\log n$.

  * •

$\mathcal{G}_{3}\coloneqq$ For all $k\in\\{2,3\\}$,
$\Big{|}\mathcal{\tilde{I}}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}\geq(1-25\epsilon)qn-2\sqrt{n}\log
n$, and
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\Big{|}\geq(1-37\epsilon)qn-2\sqrt{n}\log
n$.

  * •

$\mathcal{G}_{4}\coloneqq$ For any $i\neq j\in\\{2,3\\}$,
$\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},j}}^{A_{1,j}^{q}}\Big{|}\leq
2\epsilon\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\Big{|}$.

Let $\mathcal{G}\coloneqq\bigcap_{i\in[4]}\mathcal{G}_{i}$.

######  Claim 4.4.

The probability that the event $\mathcal{G}$ occurs is at least
$1-e^{-\log^{2}n}$.

We defer the proof of the above claim to the end of this section. Let us now
make a simple observation on the value of OPT.

######  Claim 4.5.

Assuming $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ occur,
$3(1-7\epsilon)pn\leq\texttt{OPT}\leq 3(1+\epsilon)pn+6\sqrt{n}\log n$.

###### Proof.

Since $\bar{x}=G_{p}(x_{1})$,
$\operatorname{ED}(x_{1},\bar{x})\leq(1+\epsilon)pn+2\sqrt{n}\log n$, which
implies $|\mathcal{I}^{A_{1,\bar{x}}^{p}}|\leq(1+\epsilon)pn+2\sqrt{n}\log n$.
Similar bounds also hold for $\operatorname{ED}(x_{2},\bar{x})$ and
$\operatorname{ED}(x_{3},\bar{x})$. Thus,

$\displaystyle\texttt{Obj}(\bar{x})$
$\displaystyle=\operatorname{ED}(x_{1},\bar{x})+\operatorname{ED}(x_{2},\bar{x})+\operatorname{ED}(x_{3},\bar{x})$
$\displaystyle\leq 3(1+\epsilon)pn+6\sqrt{n}\log n$
$\displaystyle\text{assuming }\mathcal{G}_{1}.$

Clearly, $\texttt{OPT}\leq\texttt{Obj}(\bar{x})$.

Now for the lower bound, let $x_{\textrm{med}}^{*}$ be an optimal median. Thus
we deduce that

OPT
$\displaystyle=\sum_{i=1}^{3}\operatorname{ED}(x_{i},x_{\textrm{med}}^{*})$
$\displaystyle=\frac{1}{2}\sum_{i<j}(\operatorname{ED}(x_{i},x_{\textrm{med}}^{*})+\operatorname{ED}(x_{j},x_{\textrm{med}}^{*}))$
$\displaystyle\geq\frac{1}{2}\sum_{i<j}\operatorname{ED}(x_{i},x_{j})$ by
triangular inequality
$\displaystyle\geq\frac{3}{2}((1-6\epsilon)qn-2\sqrt{n}\log n)$
$\displaystyle\text{assuming }\mathcal{G}_{2}$ $\displaystyle\geq
3(1-7\epsilon)pn$ $\displaystyle\text{since }q=2p-\Theta(p^{2})\text{ and
}p\in(0,0.001).$

∎

Next, we provide an upper bound on the cost of an optimal alignment between
$x_{\textrm{med}}$ and $x_{i}$ for $i\in[3]$.

######  Claim 4.6.

Assuming $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ occur, for each $i\in[3]$,
$\operatorname{ED}(x_{i},x_{\textrm{med}})\leq(1+22\epsilon)pn$.

###### Proof.

Since $x_{\textrm{med}}$ is an $(1+\epsilon)$-approximate median of
$x_{1},x_{2},x_{3}$,
$\texttt{Obj}(x_{\textrm{med}})\leq(1+\epsilon)\texttt{OPT}$. Now, we show
that $\operatorname{ED}(x_{1},x_{\textrm{med}})\leq(1+22\epsilon)pn$. For the
contradiction sake, let us assume that
$\operatorname{ED}(x_{1},x_{\textrm{med}})\geq(1+22\epsilon)pn$. Then

$\displaystyle\operatorname{ED}(x_{2},x_{\textrm{med}})+\operatorname{ED}(x_{3},x_{\textrm{med}})$
$\displaystyle=\texttt{Obj}(x_{\textrm{med}})-\operatorname{ED}(x_{1},x_{\textrm{med}})$
$\displaystyle\leq(1+\epsilon)\texttt{OPT}-\operatorname{ED}(x_{1},x_{\textrm{med}})$
$\displaystyle\leq 3(1+\epsilon)^{2}pn+6(1+\epsilon)\sqrt{n}\log
n-(1+22\epsilon)pn$ by Claim 4.5 $\displaystyle\leq(1-7\epsilon)qn$
$\displaystyle\text{since}q=2p-\Theta(p^{2}).$

From the above we can deduce that by triangular inequality,
$\operatorname{ED}(x_{2},x_{3})\leq\operatorname{ED}(x_{2},x_{\textrm{med}})+\operatorname{ED}(x_{3},x_{\textrm{med}})\leq(1-7\epsilon)qn$,
which contradicts the fact that the event $\mathcal{G}_{2}$ occurs. A similar
argument works for $\operatorname{ED}(x_{2},x_{\textrm{med}})$ and
$\operatorname{ED}(x_{3},x_{\textrm{med}})$. ∎

The next claim is the key to prove Theorem 4.2.

######  Lemma 4.7.

Assuming $\mathcal{G}$ occurs, for any $k\in\\{2,3\\}$,
$\Big{|}\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}\geq(1-276\epsilon)pn$.

Before proving the above claim, let us fist prove Theorem 4.2 by assuming the
above claim.

###### Proof of Theorem 4.2.

Let us first assume that the good event $\mathcal{G}$ occurs. Let
$K\coloneqq\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}$.
By Claim 4.6, $\operatorname{ED}(x_{1},x_{\textrm{med}})\leq(1+22\epsilon)pn$,
which implies $|\mathcal{I}^{M_{1,\textrm{med}}}|\leq(1+22\epsilon)pn$. Note,
$\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\subseteq\mathcal{I}^{M_{1,\textrm{med}}}$
and
$\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\subseteq\mathcal{I}^{A_{1,\bar{x}}^{p}}$.
Then it follows from Lemma 4.7 that
$|\mathcal{I}^{M_{1,\textrm{med}}}\setminus K|\leq 298\epsilon pn$. Also,
assuming $\mathcal{G}_{1}$, $|\mathcal{I}^{A_{1,\bar{x}}^{p}}\setminus K|\leq
278\epsilon pn$.

Next observe, $\bar{x}$ can be transformed into $x_{\textrm{med}}$ by the
following alignment $B_{\bar{x},x_{\textrm{med}}}$: First, apply the alignment
function $(A_{1,\bar{x}}^{p})^{-1}$ and then $M_{1,\textrm{med}}$. Recall, by
Proposition 4.3, for all
$i\in\mathcal{J}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\cap\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}$,
$x_{\textrm{med}}[M_{1,\textrm{med}}(i-\epsilon/q),M_{1,\textrm{med}}(i+\epsilon/q)]=\bar{x}[A_{1,\bar{x}}^{p}(i-\epsilon/q),A_{1,\bar{x}}^{p}(i+\epsilon/q)]$.
Hence, we deduce that
$\operatorname{ED}(\bar{x},x_{\textrm{med}})\leq\operatorname{cost}(B_{\bar{x},x_{\textrm{med}}})\leq|\mathcal{I}^{A_{1,\bar{x}}^{p}}\setminus
K|+|\mathcal{I}^{M_{1,\textrm{med}}}\setminus K|\leq 576\epsilon pn$.

Hence, by Claim 4.5, $\operatorname{cost}(B_{\bar{x},x_{\textrm{med}}})\leq
195\epsilon\cdot\texttt{OPT}$. The probability bound of the lemma follows from
Claim 4.4. ∎

Now, it remains to show Lemma 4.7. For that purpose, we need the following
observation.

######  Claim 4.8.

Assuming $\mathcal{G}_{1},\mathcal{G}_{2}$ and $\mathcal{G}_{3}$ occur, for
any $k\in\\{2,3\\}$,
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}\geq(1-132\epsilon)pn$.

###### Proof.

Let us consider any $k\in\\{2,3\\}$. Assuming the good event
$\mathcal{G}_{2}$,
$|\mathcal{I}^{A_{1,k}^{q}}|\leq(1+\epsilon)qn+2\sqrt{n}\log n$. Further, by
definition (see Section 3),
$\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}},\mathcal{\tilde{I}}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\subseteq\mathcal{I}^{A_{1,k}^{q}}$.
Then, assuming the good event $\mathcal{G}_{3}$, it is easy to observe that,
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\bigcap\mathcal{\tilde{I}}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}\geq(1-65\epsilon)qn$.

Next observe,
$\Big{|}\mathcal{\tilde{I}}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}\leq|\mathcal{I}^{A_{\bar{x},k}^{p}}|$
and thus at most $(1+\epsilon)pn+2\sqrt{n}\log n$ (assuming the good event
$\mathcal{G}_{1}$). Hence,

$\displaystyle\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},k}}^{A_{1,k}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},k}^{p}}^{A_{1,k}^{q}}\Big{|}$
$\displaystyle\geq(1-65\epsilon)qn-(1+\epsilon)pn-2\sqrt{n}\log n$
$\displaystyle\geq(1-132\epsilon)pn$ $\displaystyle\text{recall,
}q=2p-\Theta(p^{2}).$

∎

Now we complete the proof of Lemma 4.7.

###### Proof of Lemma 4.7.

Let
$R\coloneqq\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},3}^{p}}^{A_{1,3}^{q}}$
and
$Q\coloneqq\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap\mathcal{\tilde{I}}_{M_{1,\textrm{med},3}}^{A_{1,3}^{q}}$.

$\displaystyle\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap
R\Big{|}$
$\displaystyle=\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\Big{|}-\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap\Big{(}\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},3}}^{A_{1,3}^{q}}\Big{)}\Big{|}$
$\displaystyle\geq\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\Big{|}-\Big{|}\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},3}}^{A_{1,3}^{q}}\Big{|}$
$\displaystyle\geq(1-132\epsilon)pn-2\epsilon\Big{|}\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\Big{|}\quad\text{by
Claim~{}\ref{clm:large-IJ} and assuming }\mathcal{G}_{4}$
$\displaystyle\geq(1-135\epsilon)pn$

where the last inequality uses the fact that
$\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\subseteq\mathcal{I}^{A_{1,\bar{x}}^{p}}$
and assuming the good event $\mathcal{G}_{1}$,
$|\mathcal{I}^{A_{1,\bar{x}}^{p}}|\leq(1+\epsilon)pn+2\sqrt{n}\log n$.

Similarly,
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},3}}^{A_{1,3}^{q}}\cap
R\Big{|}\geq(1-135\epsilon)pn$. Since
$\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}},\mathcal{J}_{A_{1,\bar{x},3}^{p}}^{A_{1,3}^{q}}\subseteq\mathcal{I}^{A_{1,\bar{x}}^{p}}$,
$|R|\leq(1+\epsilon)pn+2\sqrt{n}\log n$. Hence, we can deduce that,

$|Q\cap R|\geq(1-272\epsilon)pn$ (7)

Next, we claim that $\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}\leq
4\epsilon pn$. To prove the claim, observe, for each $i\in R$,

$\bar{x}[A_{1,\bar{x}}^{p}(i-\epsilon/q),A_{1,\bar{x}}^{p}(i+\epsilon/q)]=x_{2}[A_{1,2}^{q}(i-\epsilon/q),A_{1,2}^{q}(i+\epsilon/q)]=x_{3}[A_{1,3}^{q}(i-\epsilon/q),A_{1,3}^{q}(i+\epsilon/q)].$

Then consider any $i\in(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}$. Observe, the
followings hold directly from the definition.

  1. 1.

$x_{1}[i-\epsilon/q,i+\epsilon/q]=x_{\textrm{med}}[M_{1,\textrm{med}}(i-\epsilon/q),M_{1,\textrm{med}}(i+\epsilon/q)]$.

  2. 2.

For any $k\in\\{2,3\\}$, the cost of the (sub-)alignment $M_{\textrm{med},k}$
restricted to the mapping from the substring
$x_{\textrm{med}}[M_{1,\textrm{med}}(i-\epsilon/q),M_{1,\textrm{med}}(i+\epsilon/q)]$
to $x_{k}[A_{1,2}^{q}(i-\epsilon/q),A_{1,2}^{q}(i+\epsilon/q)]$ is exactly
one.

Thus we can modify the string $x_{\textrm{med}}$ as follows: Take each
$i\in(Q\cap R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}$, and
replace the block
$x_{\textrm{med}}[M_{1,\textrm{med}}(i-\epsilon/q),M_{1,\textrm{med}}(i+\epsilon/q)]$
by $\bar{x}[A_{1,\bar{x}}^{p}(i-\epsilon/q),A_{1,\bar{x}}^{p}(i+\epsilon/q)]$.
We call the resulting string $x_{\textrm{med}}^{\prime}$. Note, for any
$k\in\\{2,3\\}$,
$\operatorname{ED}(x_{\textrm{med}}^{\prime},x_{k})\leq\operatorname{ED}(x_{\textrm{med}},x_{k})-\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}$. On the
other hand,
$\operatorname{ED}(x_{\textrm{med}}^{\prime},x_{1})\leq\operatorname{ED}(x_{\textrm{med}},x_{1})+\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}$. Hence, we
get that

$\texttt{Obj}(x_{\textrm{med}}^{\prime})\leq\texttt{Obj}(x_{\textrm{med}})-\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}.$

Now, if $\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}>4\epsilon
pn$, then

$\displaystyle\texttt{Obj}(x_{\textrm{med}}^{\prime})$
$\displaystyle\leq\texttt{Obj}(x_{\textrm{med}})-4\epsilon pn$
$\displaystyle\leq(1+\epsilon)\texttt{OPT}-4\epsilon pn$
$\displaystyle\text{since }x_{\textrm{med}}\text{ is an
}(1+\epsilon)\text{-approximate median}$
$\displaystyle<(1+\epsilon)\texttt{OPT}-\epsilon\texttt{OPT}$ by Claim 4.5
$\displaystyle=\texttt{OPT}$

which leads us to a contradiction since
$\texttt{OPT}\leq\texttt{Obj}(x_{\textrm{med}}^{\prime})$. So we conclude that
$\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}\leq
4\epsilon pn$. So we can deduce the following

$\displaystyle\Big{|}\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\cap\mathcal{J}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\Big{|}$
$\displaystyle\geq\Big{|}J_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\bigcap(Q\cap
R)\Big{|}$ $\displaystyle=|Q\cap R|-\Big{|}(Q\cap
R)\setminus\mathcal{J}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}$
$\displaystyle\geq(1-276\epsilon)pn$ $\displaystyle\text{by~{}\eqref{eq:Q-R-
bound}}.$

Similarly, we can also show that
$\Big{|}\mathcal{J}_{M_{1,\textrm{med},3}}^{A_{1,3}^{q}}\cap\mathcal{J}_{A_{1,\bar{x},3}^{p}}^{A_{1,3}^{q}}\Big{|}\geq(1-276\epsilon)pn$.
∎

###### Proof of Claim 4.4.

First, we have already observed that $x_{2},x_{3}\sim G_{q}(x_{1})$ (when
viewed them as infinite length strings). Further, by Proposition 2.4
Proposition 2.2, we can say that $x_{3}\sim G_{q}(x_{2})$. We use the notation
$A_{x_{2},x_{3}}^{q}$ to denote the alignment produced by the random process
$G_{q}(x_{2})$. Then the followings are immediate from the Chernoff-Hoeffding
bound. For any $i\in[n]$,

  * •

$\Pr[|A_{1,2}^{q}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$,

  * •

$\Pr[|A_{1,3}^{q}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$,

  * •

$\Pr[|A_{x_{2},x_{3}}^{q}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$,

  * •

$\Pr[|A_{1,\bar{x}}^{p}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$,

  * •

$\Pr[|A_{\bar{x},3}^{p}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$,

  * •

$\Pr[|A_{\bar{x},2}^{p}(i)-i|>\sqrt{n}\log n]\leq 2e^{-2\log^{2}n}$.

So, by a union bound, we get that for all $i\in[n]$, all the above six
conditions hold with probability at least $1-e^{-1.5\log^{2}n}$ (for large
enough $n$). Below while considering the $n$-length prefixes, we assume that
the above event, denoted by $\mathcal{G}_{5}$, holds.

Recall, $\bar{x}=G_{p}(x_{1})$ (when viewed them as infinite length strings).
Then by Lemma 3.1 together with the assumption of $\mathcal{G}_{5}$, for any
$\epsilon>0$, with probability at least $1-2e^{-\epsilon^{2}pn/3}$,
$\operatorname{ED}(x_{,}\bar{x})\leq(1+\epsilon)pn+2\sqrt{n}\log n$. Further,
by Lemma 3.3, we get that with probability at least
$1-2e^{-\epsilon^{2}p^{2}n/2}$,
$\operatorname{ED}(x_{1},\bar{x})\geq(1-6\epsilon)pn-2\sqrt{n}\log n$. Similar
bounds holds for the pairs $(\bar{x},x_{2}),(\bar{x},x_{3})$ and
$(x_{i},x_{j})$ for any $i\neq j\in[3]$.

Next, we assume $\mathcal{G}_{1}$, $\mathcal{G}_{2}$ and $\mathcal{G}_{5}$
occur. Then given that, we want to claim that $\mathcal{G}_{3}$ occurs with
probability at least $1-12e^{-\epsilon^{2}q^{2}n/5}$. Note, by our choice of
$\epsilon$, it holds that $\epsilon\geq 54q\log_{2}\frac{1}{q}$. Note, by
triangular inequality,
$\operatorname{cost}(A_{1,\bar{x},2}^{p})\leq\operatorname{cost}(A_{1,\bar{x}}^{p})+\operatorname{cost}(A_{\bar{x},2}^{p})$.
Then by Lemma 3.1,
$\operatorname{cost}(A_{1,\bar{x},2}^{p})\leq(1+\epsilon)2pn$ with probability
at least $1-4e^{-\epsilon^{2}pn/4}$. Note, $q=2p-\Theta(p^{2})$. Then by Lemma
3.6,
$\Big{|}\mathcal{\tilde{I}}_{A_{1,\bar{x},2}^{p}}^{A_{1,2}^{q}}\Big{|}\geq(1-25\epsilon)qn-2\sqrt{n}\log
n$ with probability at least $1-4e^{-\epsilon^{2}q^{2}n/2}$. A similar
argument holds for
$\Big{|}\mathcal{\tilde{I}}_{A_{1,\bar{x},3}^{p}}^{A_{1,3}^{q}}\Big{|}$.

Next, we argue about the set
$\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}$. By Claim 4.6,
$\operatorname{ED}(x_{\textrm{med}},x_{i})\leq(1+22\epsilon)pn$ for each
$i\in[3]$. Then, by triangular inequality,
$\operatorname{cost}(M_{1,\textrm{med},2})\leq
2(1+22\epsilon)pn\leq(1+23\epsilon)qn$. Then by Lemma 3.3 (and assuming
$\mathcal{G}_{5}$ occurs), with probability at least
$1-2e^{-(23\epsilon)^{2}q^{2}n/2}$,
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},2}}^{A_{1,2}^{q}}\Big{|}\geq(1-37\epsilon)qn-2\sqrt{n}\log
n$. A similar argument holds for
$\Big{|}\mathcal{\tilde{I}}_{M_{1,\textrm{med},3}}^{A_{1,3}^{q}}\Big{|}$.

Next, we assume $\mathcal{G}_{1}$, $\mathcal{G}_{2}$, $\mathcal{G}_{3}$ and
$\mathcal{G}_{5}$ occur. For $\mathcal{G}_{4}$, observe,
$\mathbb{E}\Big{[}|\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},j}}^{A_{1,j}^{q}}\Big{|}\Big{]}=\epsilon\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\Big{|}$.
Then by a standard application of Chernoff bound, we get that the probability
that
$\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\setminus\mathcal{J}_{A_{1,\bar{x},j}}^{A_{1,j}^{q}}\Big{|}>2\epsilon\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\Big{|}$
is at most
$2^{-\epsilon\Big{|}\mathcal{J}_{A_{1,\bar{x},i}^{p}}^{A_{1,i}^{q}}\Big{|}/2}\leq
2^{-\frac{\epsilon pn}{4}}$ (by Claim 4.8).

So finally we get that $\mathcal{G}$ holds (i.e., all the $\mathcal{G}_{i}$,
for $i\in[4]$ hold) with probability at least $1-e^{-\log^{2}n}$. ∎

#### For more than three traces.

So far, we have shown that for any set $\\{s_{1},s_{2},s_{3}\\}$ of three
traces of $s$, its any $(1+\epsilon)$-approximate median is close to $s$.
Below we argue that a similar result for any arbitrary number (less than some
$\mathrm{poly}(n)$) of traces directly follows.

######  Corollary 4.9.

For a large enough $n\in\mathbb{N}$ and a noise parameter $p\in(0,0.001)$, let
the string $s\in\\{0,1\\}^{n}$ be chosen uniformly at random, and let
$s_{1},\cdots,s_{m}$ be $m=n^{O(1)}$ traces generated by $G_{p}(s)$. If
$x_{\textrm{med}}$ is a $(1+\epsilon)$-approximate median of
$S=\\{s_{1},\cdots,s_{m}\\}$ for any $\epsilon\in[110p\log(1/p),1/6]$, then
$\Pr[\operatorname{ED}(s,x_{\textrm{med}})\leq
O(\epsilon)\cdot\frac{\texttt{OPT}(S)}{m}]\geq 1-n^{-1}$.

###### Proof (Sketch)..

By an argument similar to that used in Claim 4.5, we can show that with high
probability $\texttt{OPT}(S)\leq\texttt{Obj}(S,s)\leq(1+\epsilon)pnm$. Let $z$
be an $(1+\epsilon)$-approximate median of $S$, then
$\texttt{Obj}(S,z)\leq(1+\epsilon)^{2}pnm$. By averaging, there exists a
subset $S^{\prime}=\\{s_{i},s_{i+1},s_{i+2}\\}\subseteq S$ such that
$\texttt{Obj}(S^{\prime},z)\leq 3(1+\epsilon)^{2}pn$, hence $z$ is a
$(1+O(\epsilon))$-approximate median of $S^{\prime}$. Thus by Theorem 4.2
together with a union bound, $z$ is at distance at most
$O(\epsilon)\texttt{OPT}(S^{\prime})$ from $s$. We can also show that with
high probability $\texttt{OPT}(S^{\prime})\geq(1-7\epsilon)pnm$, again by an
argument similar to Claim 4.5. We thus conclude that with high probability
$\operatorname{ED}(s,z)\leq O(\epsilon)\frac{\texttt{OPT}(S)}{m}$. ∎

##  5 Linear-time Approximate Trace Reconstruction

In this section, we describe a linear-time algorithm that reconstructs the
unknown string using only three traces, up to some small edit error. In
particular, we prove Theorem 1.1. Before describing our linear-time algorithm,
first note that we can compute an (exact) median of three traces using a
standard dynamic programming algorithm [San75, Kru83] in cubic time. Then by
Theorem 4.2, that median string will be close (in edit distance) to the
unknown string. More specifically, the edit distance between the computed
median string and the unknown string will be at most $O(\epsilon pn)$ (follows
from Theorem 4.2 and Claim 4.5) with high probability. In this section, we
design a more sophisticated method to compute an approximation of the unknown
string. For that purpose, we first divide each trace into “well-separated”
blocks of size $\log^{2}n$ each. Then we run the dynamic-programming-based
median algorithm [San75, Kru83] on these small blocks. Thus we spend only
$\mathrm{poly}\log n$ time per block, and hence in total $\tilde{O}(n)$ time.
Since we consider “well-separated” blocks, they are independent. Thus we apply
Theorem 4.2 for each of these blocks (instead of the whole string). Using
standard Chernoff-Hoeffding bound, we get that most of these block medians are
close to their corresponding block of the unknown string. Hence, by
concatenating these block medians, we get back the whole unknown string up to
some small edit error. Formally, our result is the following.

######  Theorem 5.1.

There is a small non-negative constant $c_{0}<1$ and a deterministic algorithm
that, given as input a noise parameter $p\in(0,c_{0}]$, an accuracy parameter
$\epsilon\in[110p\log(1/p),1/6]$, and three traces $s_{1},s_{2},s_{3}\sim
G_{p}(s)$ for a uniformly random (but unknown) string $s\in\\{0,1\\}^{n}$,
outputs in time $\tilde{O}(n)$ a string $z$ that satisfies
$\Pr[\operatorname{ED}(s,z)\leq 5270\epsilon pn]\geq 1-n^{-1}$.

Before describing the algorithm we would like to introduce some notation that
we use in this section. For a string $x\in\Sigma^{n}$, let
$y=x[i,i+1,\cdots,j]$ be a substring of it; then we denote by
$\texttt{start}(y)$ the index $i$ and by $\texttt{end}(y)$ the index $j$.

#### Description of the algorithm.

The algorithm works as follows. First, partition $s_{1}$ into
$r=\frac{|s_{1}|}{\ell}$ disjoint blocks
$s_{1}^{1},s_{1}^{2},\cdots,s_{1}^{r}$ each of length
$\ell=\log^{2}n+\frac{240}{p}\log^{3/2}n$. For each $s_{1}^{i}$, let us call
the middle $\log^{2}n$-size sub-block, denoted by $y_{1}^{i}$, an _anchor_.
Next, for each $i\in[r]$ and $j\in\\{2,3\\}$, find the _best match_ of the
anchor $y_{1}^{i}$ in the string $s_{j}$ i.e., for each $y_{1}^{i}$ find a
substring (breaking ties arbitrarily) in $s_{j}$ that has the minimum edit
distance with $y_{1}^{i}$. Let us denote the matched substrings in $s_{2}$ and
$s_{3}$ by $y_{2}^{i}$ and $y_{3}^{i}$ respectively. Then for each
$j\in\\{2,3\\}$, we divide $s_{j}$ into blocks $s_{j}^{1},\cdots,s_{j}^{r}$
(some of the $s_{j}^{i}$’s could be empty) by treating
$y_{j}^{1},\cdots,y_{j}^{r}$ as anchors. More specifically,

  * •

Set the start index of $s_{j}^{1}$ to be 1. For any other non-empty block
$s_{j}^{i}$, set its start index to be
$\lfloor(\texttt{end}(y_{j}^{i-1})+\texttt{start}(y_{j}^{i}))/2\rfloor$.

  * •

For the last non-empty block in $s_{j}$, set its end index to be $|s_{j}|$.
For any other non-empty block $s_{j}^{i}$, set its end index to be
$\lfloor(\texttt{end}(y_{j}^{i})+\texttt{start}(y_{j}^{i+1}))/2\rfloor-1$.

Next, for each $i\in[r]$, compute a median of
$\\{s_{1}^{i},s_{2}^{i},s_{3}^{i}\\}$, and let it be denoted by $z^{i}$.
Finally, output $z=z^{1}\odot\cdots\odot z^{r}$ (i.e., the concatenation of
all the $z^{i}$’s).

#### Correctness proof.

Before proceeding with the correctness proof, let us state a known fact from
[BEK+03] about the edit distance between two random strings.

######  Proposition 5.2 ([BEK+03]).

For any two strings $x\in\Sigma^{m}$ and $y\in\Sigma^{n}$ drawn uniformly at
random, $\Pr[\operatorname{ED}(x,y)\geq\frac{\max\\{m,n\\}}{10}]\geq
1-2^{-\max\\{m,n\\}/10}$.

######  Claim 5.3.

For every two substrings $x,y$ of length at least $60\log n$, of $s_{i},s_{j}$
respectively, where $i,j\in[3]$, such that $(A_{s,s_{i}}^{p})^{-1}(x)$ and
$(A_{s,s_{j}}^{p})^{-1}(y)$ are two disjoint substrings of $s$,
$\Pr[\operatorname{ED}(x,y)\geq\frac{\max\\{|x|,|y|\\}}{10}]\geq 1-n^{-4}$.

###### Proof.

By Proposition 2.4, $x$ and $y$ are two strings chosen uniformly at random by
picking each of its symbols independently uniformly at random from $\Sigma$.
Then the claim directly follows from Proposition 5.2 together with a standard
application of union bound. ∎

Let us now define a _true match_ for each block $y_{1}^{i}$ in strings $s_{2}$
and $s_{3}$. For each $j\in\\{2,3\\}$, we call the block
$A_{s,s_{j}}^{p}((A_{s,s_{1}}^{p})^{-1}(y_{1}^{i}))$ in $s_{j}$ the true match
of $y_{1}^{i}$, denoted by $t_{j}^{i}$. Next, we want to claim that for each
block $y_{1}^{i}$, its best match $y_{j}^{i}$ in a string $s_{j}$, for
$j\in\\{2,3\\}$, is close to its true match $t_{j}^{i}$. The following lemma
is crucial to show the correctness of the algorithm and also to establish a
linear-time bound for the algorithm.

######  Claim 5.4.

For each $i\in[r]$ and $j\in\\{2,3\\}$, with probability $1-5n^{-2}$,

  1. 1.

$|\texttt{start}(t_{j}^{i})-\texttt{start}(y_{j}^{i})|\leq\frac{200}{p}\log
n$, and

  2. 2.

$|\texttt{end}(t_{j}^{i})-\texttt{end}(y_{j}^{i})|\leq\frac{200}{p}\log n$.

###### Proof.

Let us partition $y_{1}^{i}$ into $\frac{p\log n}{10}$ sub-blocks
$y_{1}^{i,1},\cdots,y_{1}^{i,(p\log n)/10}$, each of size $\frac{10\log
n}{p}$. Next, for each of these sub-blocks $y_{1}^{i,k}$ consider its true
match in the string $s_{j}$ (for any $j\in\\{2,3\\}$) defined as
$t_{j}^{i,k}\coloneqq A_{s,s_{j}}^{p}((A_{s,s_{1}}^{p})^{-1}(y_{1}^{i,k}))$.

Now, consider an (arbitrary) optimal alignment $B$ between $y_{1}^{i}$ and
$y_{j}^{i}$. Observe, if for all $1\leq k\leq(p\log n)/10$, $B(y_{1}^{i,k})$
has a non-empty overlap with the corresponding true match $t_{j}^{i,k}$, then
the claim is true. So from now on, let us assume that at least for some block
$y_{1}^{i,k}$, $B(y_{1}^{i,k})$ does not overlap with $t_{j}^{i,k}$. Let
$y_{1}^{i,k^{\prime}}$ be the right-most sub-block such that there is a non-
empty overlapping between $B(y_{1}^{i,k^{\prime}})$ and
$t_{j}^{i,k^{\prime}}$. Then for each $k^{\prime}+1\leq k\leq(p\log n)/10$, by
Claim 5.3, $\operatorname{cost}_{B}(y_{1}^{i,k})\geq\frac{\log n}{p}$ with
probability at least $1-n^{-4}$.

We want to claim that $k^{\prime}\geq\frac{p\log n}{10}-\frac{10}{1-24p}$. If
not, then we deduce that $y_{j}^{i}$ is not the best match of $y_{1}^{i}$ in
the string $s_{j}$. To argue this, suppose $k^{\prime}<\frac{p\log
n}{10}-\frac{10}{1-24p}$. Then we modify the mapping $B$ to derive another
mapping $B^{\prime}$ as follows: $B^{\prime}$ respects $B$ till the block
$y_{1}^{i,k^{\prime}-1}$. Next, $B^{\prime}$ deletes the block
$y_{1}^{i,k^{\prime}}$, and then use the mapping
$A_{s,s_{j}}^{p}\circ(A_{s,s_{1}}^{p})^{-1}$ to map the remaining blocks
$y_{1}^{i,k^{\prime}+1},\cdots,y_{1}^{i,(p\log n)/10}$. By Lemma 3.1 (applied
on strings of size at least $\frac{10\log n}{p}$) together with an union
bound, we get that for all the blocks of $s_{1}$ of size at least
$\frac{10\log n}{p}$, the cost of the alignment
$A_{s,s_{j}}^{p}\circ(A_{s,s_{1}}^{p})^{-1}$ is at most $24\log n$ with
probability at least $1-2n^{-2}$.

Clearly, the cost of this new alignment $B^{\prime}$ is at least
$(\frac{10}{1-24p}+1)\frac{\log n}{p}-(\frac{10\log n}{p}+\frac{240\log
n}{1-24p})>0$ less than that of $B$. Hence, $y_{j}^{i}$ cannot be the best
match of $y_{1}^{i}$ in $s_{j}$. So we deduce that $k^{\prime}\geq\frac{p\log
n}{10}-\frac{10}{1-24p}$. Note, if an alignment function just deletes all the
blocks $y_{1}^{i,k^{\prime}+1},\cdots,y_{1}^{i,(p\log n)/10}$, it would cost
at most $\frac{100\log n}{p(1-24p)}$. Thus, since $t_{j}^{i}$ is the best
match of $y_{1}^{i}$, the cost of $B$ for these blocks
$y_{1}^{i,k^{\prime}+1},\cdots,y_{1}^{i,(p\log n)/10}$ must be at most
$\frac{100\log n}{p(1-24p)}$. From this we conclude that
$|\texttt{end}(t_{j}^{i})-\texttt{end}(y_{j}^{i})|\leq\frac{100}{p(1-24p)}\log
n\leq\frac{200}{p}\log n$ (for the choice of $p$ we have).

Similarly, we can argue that
$|\texttt{start}(t_{j}^{i})-\texttt{start}(y_{j}^{i})|\leq\frac{200}{p}\log
n$. This concludes the proof. ∎

The following is an immediate corollary of the above claim.

######  Corollary 5.5.

With probability at least $1-10n^{-2}$, for each $i\in[r]$ and
$j\in\\{2,3\\}$, $y_{j}^{i}$ and $y_{j}^{i+1}$ do not overlap.

###### Proof.

Consider the substring between the blocks $y_{1}^{i}$ and $y_{1}^{i+1}$, which
is of length $\frac{480}{p}\log^{3/2}n$. By Lemma 3.1,
$A_{s,s_{j}}^{p}\circ(A_{s,s_{1}}^{p})^{-1}$ maps that substring into a
substring of length at least $240\log^{3/2}n>\frac{400}{p}\log n$ in $s_{j}$
with probability at least $1-n^{-3}$. Now, it directly follows from Claim 5.4
that $y_{j}^{i}$ and $y_{j}^{i+1}$ do not overlap. ∎

Next, we use the above to establish an upper bound on the edit distance
between the unknown string $s$ and the recovered string $z$.

######  Lemma 5.6.

With probability at least $1-n^{-1}$, $\operatorname{ED}(s,z)\leq 1550\epsilon
pn$.

###### Proof.

For any $i\in[r]$, consider the set
$S^{i}\coloneqq\\{s_{1}^{i},s_{2}^{i},s_{3}^{i}\\}$. Consider the substring
$y^{i}$ of the string $s$ such that $A_{s,s_{1}}^{p}(y^{i})=y_{1}^{i}$ (i.e.,
$y^{i}$ maps to $y_{1}^{i}$ by the alignment $A_{s,s_{1}}^{p}$). Next, for the
analysis purpose, consider the set
$T^{i}=\\{y_{1}^{i},t_{2}^{i},t_{3}^{i}\\}$. Recall, by the definition of
$t_{j}^{i}=A_{s,s_{j}}^{p}(y^{i})$, for $j\in\\{2,3\\}$ are the traces
generated by $G_{p}$ from the block $y^{i}$.

Thus by Lemma 3.1, with probability at least $1-3n^{-4}$, for each $t\in
T^{i}$, $\operatorname{ED}(y^{i},t)\leq(1+\epsilon)p|y^{i}|$. Since
$y_{1}^{i}$ is a substring of $s_{1}^{i}$ (where
$|s_{1}^{i}|=|y_{1}^{i}|+\frac{240}{p}\log^{3/2}n$), by triangular inequality,
$\operatorname{ED}(y^{i},s_{1}^{i})\leq(1+\epsilon)p|y^{i}|+\frac{240}{p}\log^{3/2}n$.
Next observe, for each $j\in\\{2,3\\}$, by Corollary 5.5, $t_{j}^{i}$ is a
substring of $s_{j}^{i}$. Furthermore, by definition,
$|s_{j}^{i}|\leq|y_{j}^{i}|+\frac{240}{p}\log^{3/2}n$. Thus, again by
triangular inequality,
$\operatorname{ED}(y^{i},s_{j}^{i})\leq(1+\epsilon)p|y^{i}|+\frac{240}{p}\log^{3/2}n$.
So we get

$\displaystyle\texttt{Obj}(S^{i},y^{i})\leq
3(1+\epsilon)p|y^{i}|+\frac{750}{p}\log^{3/2}n.$ (8)

Since $z^{i}$ is an (exact) median of $S^{i}$,
$\texttt{Obj}(S^{i},z^{i})\leq\texttt{Obj}(S^{i},y^{i})$. Next, it follows
from Claim 5.4 and the construction of the blocks $s_{j}^{i}$, for
$j\in\\{2,3\\}$, that $t_{j}^{i}$ is a substring of $s_{j}^{i}$ where
$|t_{j}^{i}|\geq|s_{j}^{i}|-\frac{500}{p}\log^{3/2}n$. Hence, we can deduce
that

$\displaystyle\texttt{Obj}(T^{i},z^{i})$
$\displaystyle\leq\texttt{Obj}(S^{i},z^{i})+\frac{1500}{p}\log^{3/2}n$
$\displaystyle\leq\texttt{Obj}(S^{i},y^{i})+\frac{1500}{p}\log^{3/2}n$
$\displaystyle\leq 3(1+\epsilon)p|y^{i}|+\frac{2500}{p}\log^{3/2}n$
$\displaystyle\text{by~{}\eqref{eq:obj-bound}}.$ (9)

Further observe, it follows from Proposition 2.2 and Lemma 3.3, for each
$j\in\\{2,3\\}$,

$\operatorname{ED}(y_{1}^{i},t_{j}^{i})\geq(1-6\epsilon)q|y_{1}^{i}|=(1-6\epsilon)q\log^{2}n.$

Recall, $q=2p-\Theta(p^{2})$. Then by an argument similar to that used in the
proof of Claim 4.5,

$\displaystyle\texttt{OPT}(T^{i})\geq 3(1-7\epsilon)p\log^{2}n.$ (10)

From (5) and (10), we conclude that $z^{i}$ is an $(1+9\epsilon)$-approximate
median of $T^{i}$. So by Theorem 4.2, $\operatorname{ED}(y^{i},z^{i})\leq
1755\epsilon\cdot\texttt{OPT}(T^{i})$ with probability at least
$1-e^{-2\log^{2}(\log n)}$.

Now, since all the $y^{i}$’s are generated by picking each symbol uniformly at
random and by our construction for each $j\in\\{2,3\\}$ $t_{j}^{i}$’s are
disjoint, the sets $T^{i}$’s are independent. Hence, by applying standard
Chernoff-Hoeffding bound, we get that with probability at least $1-n^{-1}$,
all but at most $e^{-2\log^{2}(\log n)}r+\sqrt{r\log r}$ many blocks satisfy,
$\operatorname{ED}(y^{i},z^{i})\leq 1755\epsilon\cdot\texttt{OPT}(T^{i})$.

Let $s^{\prime}$ denote the string $y^{1}\odot\cdots\odot y^{r}$. Note as
$s^{\prime}$ is a subsequence of $s$,

$\operatorname{ED}(s,s^{\prime})=|s|-|s^{\prime}|\leq\frac{500n}{p}{\log^{1/2}n}$

Then,

$\displaystyle\operatorname{ED}(s,z)$
$\displaystyle\leq\operatorname{ED}(s^{\prime},z)+\frac{500n}{p\log^{1/2}n}$
by triangular inequality
$\displaystyle\leq\sum_{i=1}^{r}\operatorname{ED}(y^{i},z^{i})+\frac{500n}{p\log^{1/2}n}$
$\displaystyle\leq
1755\epsilon\sum_{i=1}^{r}\texttt{OPT}(T^{i})+(e^{-2\log^{2}(\log
n)}r+\sqrt{r\log r})2\log^{2}n+\frac{500n}{p\log^{1/2}n}$ $\displaystyle\leq
5270\epsilon pn$ $\displaystyle\text{by~{}\eqref{eq:obj} and
}r=\Theta(n/\log^{2}n).$

∎

#### Running time analysis.

Partitioning the string $s_{1}$ into $r$ blocks clearly takes linear time. The
main challenge here is to find the best match $y_{j}^{i}$ (for
$j\in\\{2,3\\}$) for each block $y_{1}^{i}$. To do this, for each
$j\in\\{2,3\\}$, we start with the first $10\log^{2}n$-sized substring of
$s_{j}$ and run the approximate pattern matching algorithm under the edit
metric by [LV89, GP90] to find the best match $y_{j}^{1}$ for $y_{1}^{1}$
(which takes $O(\log^{4}n)$ time). Next, we consider the $10\log^{2}n$-sized
substring of $s_{j}$ starting from the end index of $y_{j}^{1}$, and in a
similar way find the best match $y_{j}^{2}$ for $y_{1}^{2}$. We continue until
we find the best matches for all the blocks $y_{1}^{1},\cdots,y_{1}^{r}$.
Lemma 3.1 ensures that $y_{j}^{1}$ indeed lies on the first
$10\log^{2}n$-sized substring of $s_{j}$ with probability at least $1-n^{-4}$.
Then Corollary 5.5 together with Lemma 3.1 guarantees that to find the best
match for a block $y_{1}^{i}$, it suffices to look into the
$10\log^{2}n$-sized substring of $s_{j}$ after the best match of the previous
block $y_{1}^{i-1}$. Hence, we can identify the best matches for all the
blocks $y_{1}^{1},\cdots,y_{1}^{r}$ in time $\tilde{O}(n)$ (since
$r=\Theta(\frac{n}{\log^{2}n})$). Once we get $s_{1}^{i},s_{2}^{i},s_{3}^{i}$
for each $i\in[r]$, we can compute their median using the dynamic programming
algorithm [San75, Kru83] in time $O(\log^{6}n)$ time. So, the total running
time is $\tilde{O}(n)$.

##  6 Conclusion

Trace reconstruction in the average case is a well-studied problem. The
problem is to reconstruct an unknown (random) string by reading a few traces
of it generated via some noise (insertion-deletion) channel. The main
objective here is to minimize the sample complexity and also the efficiency of
the reconstruction algorithm. There is an exponential gap between the current
best upper and lower bound in the sample complexity despite several attempts.
The best lower bound is $\tilde{\Omega}(\log^{5/2}n)$ [Cha21a]. A natural
question is whether it is possible to beat this lower bound by allowing some
error in the reconstructed string. This version is also referred to as the
approximate trace reconstruction problem; however, nothing is known except for
a few special cases.

Our result not only beats the lower bound of the exact trace reconstruction
but uses only three traces. The reconstructed string is $O(\epsilon pn)$ close
(in edit distance) to the unknown string with high probability. We establish a
connection between the approximate trace reconstruction and the approximate
median string problem, another utterly significant problem. We show that both
the problems are essentially the same. We leverage this connection to design a
near-linear time approximate reconstruction algorithm using three traces.

An exciting future direction is to get a similar result for the worst-case,
where the unknown string is arbitrary. It will also be fascinating if we could
show some non-trivial sample complexity lower bound for that version.

## References

  * [ACN08] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  J. ACM, 55(5):23:1–23:27, 2008.  doi:10.1145/1411509.1411513.
  * [ARJ14] J. Abreu and Juan Ramón Rico-Juan.  A new iterative algorithm for computing a quality approximate median of strings based on edit operations.  Pattern Recognition Letters, 36:74–80, 2014.
  * [BCF+19] Frank Ban, Xi Chen, Adam Freilich, Rocco A Servedio, and Sandip Sinha.  Beyond trace reconstruction: Population recovery from the deletion channel.  In 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 745–768. IEEE, 2019.
  * [BEK+03] Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami.  A sublinear algorithm for weakly approximating edit distance.  In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC ’03, pages 316–324. ACM, 2003.
  * [BKKM04] Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.  Reconstructing strings from random traces.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pages 910–918. SIAM, 2004.
  * [CA97] Francisco Casacuberta and M. D. Antonio.  A greedy algorithm for computing approximate median strings.  In Proc. of National Symposium on Pattern Recognition and Image Analysis, pages 193–198, 1997.
  * [CCGB17] Hervé Cardot, Peggy Cénac, and Antoine Godichon-Baggioni.  Online estimation of the geometric median in Hilbert spaces: Nonasymptotic confidence balls.  Annals of Statistics, 45(2):591–614, 2017.  doi:10.1214/16-AOS1460.
  * [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.  Approximating the median under the ulam metric.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 761–775. SIAM, 2021.  doi:10.1137/1.9781611976465.48.
  * [CDL+21a] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the low deletion rate regime.  In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPIcs, pages 20:1–20:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [CDL+21b] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the smoothed complexity model.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 54–73. SIAM, 2021.
  * [CGMR20] Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Joao Ribeiro.  Coded trace reconstruction.  IEEE Transactions on Information Theory, 66(10):6084–6103, 2020\.
  * [Cha21a] Zachary Chase.  New lower bounds for trace reconstruction.  In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, volume 57, pages 627–643. Institut Henri Poincaré, 2021.
  * [Cha21b] Zachary Chase.  Separating words and trace reconstruction.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 21–31, 2021.
  * [CKPV10] Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, and Sergei Vassilvitskii.  Finding the Jaccard median.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 293–311. SIAM, 2010.  doi:10.1137/1.9781611973075.25.
  * [CLM+16] Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford.  Geometric median in nearly linear time.  In Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing, pages 9–21, 2016.
  * [DKNS01] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar.  Rank aggregation methods for the web.  In Proceedings of the Tenth International World Wide Web Conference, WWW 10, pages 613–622, 2001.  doi:10.1145/371920.372165.
  * [dlHC00] Colin de la Higuera and Francisco Casacuberta.  Topology of strings: Median string is NP-complete.  Theor. Comput. Sci., 230(1-2):39–48, 2000.  doi:10.1016/S0304-3975(97)00240-5.
  * [DOS17] Anindya De, Ryan O’Donnell, and Rocco A Servedio.  Optimal mean-based algorithms for trace reconstruction.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047–1056, 2017.
  * [DRRS20] Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian, and Benjamin G. Schiffer.  Approximate trace reconstruction.  CoRR, abs/2012.06713, 2020.  URL: https://arxiv.org/abs/2012.06713.
  * [FVJ08] P. Thomas Fletcher, Suresh Venkatasubramanian, and Sarang Joshi.  Robust statistics on riemannian manifolds via the geometric median.  In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2008.
  * [FZ00] Igor Fischer and Andreas Zell.  String averages and self-organizing maps for strings.  Proceedings of the neural computation, pages 208–215, 2000.
  * [GBC+13] Nick Goldman, Paul Bertone, Siyuan Chen, Christophe Dessimoz, Emily M. LeProust, Botond Sipos, and Ewan Birney.  Towards practical, high-capacity, low-maintenance information storage in synthesized DNA.  Nature, 494(7435):77–80, 2013.
  * [GP90] Zvi Galil and Kunsoo Park.  An improved algorithm for approximate string matching.  SIAM Journal on Computing, 19(6):989–999, 1990.
  * [GSZ20] Elena Grigorescu, Madhu Sudan, and Minshen Zhu.  Limitations of mean-based algorithms for trace reconstruction at small distance.  CoRR, abs/2011.13737, 2020.
  * [Gus97] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology.  Cambridge University Press, 1997.
  * [HK16] Morihiro Hayashida and Hitoshi Koyano.  Integer linear programming approach to median and center strings for a probability distribution on a set of strings.  In BIOINFORMATICS, pages 35–41, 2016.
  * [HL20] Nina Holden and Russell Lyons.  Lower bounds for trace reconstruction.  The Annals of Applied Probability, 30(2):503 – 525, 2020.
  * [HMPW08] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.  Trace reconstruction with constant deletion probability and related results.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pages 389–398. SIAM, 2008.
  * [HPPZ20] Nina Holden, Robin Pemantle, Yuval Peres, and Alex Zhai.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  Mathematical Statistics and Learning, 2(3):275–309, 2020.
  * [Kal73] V. V. Kalashnik.  Reconstruction of a word from its fragments.  Computational Mathematics and Computer Science (Vychislitel’naya matematika i vychislitel’naya tekhnika), Kharkov, 4:56–57, 1973.
  * [KM05] Sampath Kannan and Andrew McGregor.  More on reconstructing strings from random traces: insertions and deletions.  In Proceedings. International Symposium on Information Theory, 2005\. ISIT 2005., pages 297–301. IEEE, 2005.
  * [Koh85] Teuvo Kohonen.  Median strings.  Pattern Recognition Letters, 3(5):309–313, 1985.  doi:10.1016/0167-8655(85)90061-3.
  * [Kru83] Joseph B Kruskal.  An overview of sequence comparison: Time warps, string edits, and macromolecules.  SIAM review, 25(2):201–237, 1983.  doi:10.1137/1025045.
  * [Kru99] Ferenc Kruzslicz.  Improved greedy algorithm for computing approximate median strings.  Acta Cybernetica, 14(2):331–339, 1999.
  * [KS07] Claire Kenyon-Mathieu and Warren Schudy.  How to rank with few errors.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 95–103. ACM, 2007.  doi:10.1145/1250790.1250806.
  * [Lev01a] Vladimir I. Levenshtein.  Efficient reconstruction of sequences.  IEEE Transactions on Information Theory, 47(1):2–22, 2001.  doi:10.1109/18.904499.
  * [Lev01b] Vladimir I. Levenshtein.  Efficient reconstruction of sequences from their subsequences or supersequences.  Journal of Combinatorial Theory, Series A, 93(2):310–332, 2001\.  doi:10.1006/jcta.2000.3081.
  * [LV89] Gad M. Landau and Uzi Vishkin.  Fast parallel and serial approximate string matching.  Journal of Algorithms, 10(2):157–169, 1989.
  * [MAS19] P. Mirabal, J. Abreu, and D. Seco.  Assessing the best edit in perturbation-based iterative refinement algorithms to compute the median string.  Pattern Recognition Letters, 120:104–111, Apr 2019.
  * [Min15] Stanislav Minsker.  Geometric median and robust estimation in Banach spaces.  Bernoulli, 21(4):2308–2335, 2015.
  * [Mit09] Michael Mitzenmacher.  A survey of results for deletion channels and related synchronization channels.  Probability Surveys, 6:1–33, 2009.
  * [MJC00] Carlos D. Martínez-Hinarejos, Alfons Juan, and Francisco Casacuberta.  Use of median string for classification.  In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2, pages 903–906. IEEE, 2000.  doi:10.1109/ICPR.2000.906220.
  * [MPV14] Andrew McGregor, Eric Price, and Sofya Vorotnikova.  Trace reconstruction revisited.  In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 689–700. Springer, 2014.
  * [Nar20] Shyam Narayanan.  Population recovery from the deletion channel: Nearly matching trace reconstruction bounds.  arXiv preprint arXiv:2004.06828, 2020.
  * [NP17] Fedor Nazarov and Yuval Peres.  Trace reconstruction with exp(o(n${}^{\mbox{1/3}}$)) samples.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1042–1046. ACM, 2017.
  * [NR03] François Nicolas and Eric Rivals.  Complexities of the centre and median string problems.  In 14th Annual Symposium on Combinatorial Pattern Matching, CPM 2003, pages 315–327, 2003.
  * [OAC+18] Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Konstantin Makarychev, Miklos Z. Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, et al.  Random access in large-scale dna data storage.  Nature biotechnology, 36(3):242, 2018.
  * [PB07] Oscar Pedreira and Nieves R. Brisaboa.  Spatial selection of sparse pivots for similarity search in metric spaces.  In International Conference on Current Trends in Theory and Practice of Computer Science, pages 434–445. Springer, 2007.
  * [Pev00] Pavel Pevzner.  Computational molecular biology: an algorithmic approach.  MIT press, 2000.
  * [PZ17] Yuval Peres and Alex Zhai.  Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 228–239. IEEE Computer Society, 2017.
  * [RCS13] Richard J Roberts, Mauricio O Carneiro, and Michael C Schatz.  The advantages of smrt sequencing.  Genome Biology, 14(7):405, 2013.
  * [RMR+17] Cyrus Rashtchian, Konstantin Makarychev, Miklós Z. Rácz, Siena Ang, Djordje Jevdjic, Sergey Yekhanin, Luis Ceze, and Karin Strauss.  Clustering billions of reads for DNA data storage.  In Advances in Neural Information Processing Systems 30, pages 3360–3371. Curran Associates, Inc., 2017.
  * [San75] David Sankoff.  Minimal mutation trees of sequences.  SIAM Journal on Applied Mathematics, 28(1):35–42, 1975.  doi:10.1137/0128004.
  * [VS08] Krishnamurthy Viswanathan and Ram Swaminathan.  Improved string reconstruction over insertion-deletion channels.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 399–408, 2008.
  * [YGM17] SM Hossein Tabatabaei Yazdi, Ryan Gabrys, and Olgica Milenkovic.  Portable and error-free dna-based data storage.  Scientific reports, 7(1):1–6, 2017.

##  Appendix A Proof of Lemma 3.6

###### Proof of Lemma 3.6.

We follow the outline of the proof of Lemma 3.3. Let $\mathcal{B}$ be the
event that there exists an alignment $M$ between $x,y$ with
$\operatorname{cost}(M)\leq(1+\delta)pn$ such that
$|\mathcal{\tilde{I}}_{M}|<(1-23\epsilon-\delta)pn$. Moreover let
$\mathcal{B}^{0}$ be the event that there exists an alignment $\bar{M}$
between $x,y$ such that for at least $6\epsilon pn$ indices
$i\in\mathcal{\tilde{I}}$,
$\operatorname{cost}_{\bar{M}}(x[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}])=0$.
In the rest of the proof we shall bound the probability of event
$\mathcal{B}$. We assume henceforth that $A^{p}$ is known (i.e., we condition
on $A^{p}$), and that $|\mathcal{\tilde{I}}|>(1-5\epsilon)pn$, which occurs
with high probability by Lemma 3.2. The probabilistic analysis below will use
the randomness of $x$ and of the characters inserted into $y$.

Our plan is to define some basic events $\mathcal{E}_{S,\bar{S},\Gamma}$ for
every two subset $S,\bar{S}\subseteq[n]$ of the same size
$\ell=|S|=|\bar{S}|$, representing positions in $x$ and in $y$, respectively,
and for every vector $\gamma\in\\{-1,1\\}^{\ell}$. We then show that the bad
events are bounded by these events and event $\mathcal{B}^{0}$

$\displaystyle\mathcal{B}\subseteq(\bigcup_{S,\bar{S},\gamma\mid\ell=\epsilon
pn}\mathcal{E}_{S,\bar{S},\gamma})\bigcup\mathcal{B}^{0},$ (11)

and bound the probability of each basic event by

$\displaystyle\Pr[\mathcal{E}_{S,\bar{S},\gamma}]\leq|\Sigma|^{-\epsilon\ell/(6p)}.$
(12)

The proof will then follow easily using a union bound and a simple
calculation.

To define the basic event $\mathcal{E}_{S,\bar{S},\gamma}$, we need some
notations. Write $S=\\{i_{1},\dots,i_{\ell}\\}$ in increasing order, and
similarly $\bar{S}=\\{\bar{i}_{1},\ldots,\bar{i}_{\ell}\\}$, and let
$\gamma=(\gamma_{1},\ldots,\gamma_{\ell})$. Use these to define $\ell$ blocks
in $x$, namely, $B_{i_{j}}=x[i_{j},i_{j}+\frac{2\epsilon}{p}]$, and $\ell$
blocks in $y$, namely,
$\bar{B}_{i_{j}}=y[\bar{i}_{j},\bar{i}_{j}+\frac{2\epsilon}{p}+\gamma_{j}]$.
Note that here $i_{j}$ and $\bar{i}_{j}$ are at the beginning of their blocks
(while in Lemma 3.3 they were at the middle), and that the length of
$B_{i_{j}}$ and of $\bar{B}_{i_{j}}$ might differ (they are
$1+\frac{2\epsilon}{p}$ and $\frac{2\epsilon}{p}+1+\gamma_{j}$, respectively).
Now define $\mathcal{E}_{S,\bar{S},\gamma}$ to be the event that (i)
$\tilde{S}\coloneqq\\{i_{1}+\frac{\epsilon}{p},\cdots,i_{\ell}+\frac{\epsilon}{p}\\}\subseteq\mathcal{\tilde{I}}$;444This
implies that the blocks $B_{i_{1}},\dots,B_{i_{\ell}}$ in $x$ are disjoint.
(ii) the blocks $\bar{B}_{\bar{}i_{1}},\dots,\bar{B}_{\bar{i}_{\ell}}$ in $y$
are disjoint; (iii) $A^{p}(i_{j})\neq\bar{i}_{j}$ or
$A^{p}(i_{j}+\frac{2\epsilon}{p})\neq\bar{i}_{j}+\frac{2\epsilon}{p}+\gamma_{j}$
(possibly both); and (iv) $\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$.
Notice that conditions (i), (ii) and (iii) actually depend only on $A^{p}$,
and thus can be viewed as restrictions on the choice of $S$, $\bar{S}$ and
$\gamma$ in (11); with this viewpoint in mind, we can simply write

$\mathcal{E}_{S,\bar{S},\gamma}\coloneqq{\\{\operatorname{ED}(B_{i_{1}},\bar{B}_{i_{1}})=1,\ldots,\operatorname{ED}(B_{i_{\ell}},\bar{B}_{i_{\ell}})=1\\}}.$

We proceed to prove (11). Suppose event $\mathcal{B}$ occurs, i.e., there
exists an alignment $M$ between $x,y$ with
$\operatorname{cost}(M)\leq(1+\delta)pn$ such that
$|\mathcal{\tilde{I}}_{M}|<(1-23\epsilon-\delta)pn$. Next first assume the
case where there exists at least $6\epsilon pn$ indices
$i\in\mathcal{\tilde{I}}$ such that
$\operatorname{cost}_{M}(x[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}])=0$. But
then trivially event $\mathcal{\bar{B}}$ is satisfied and thus we prove (11).
Hence from now on wards we assume the case where event $\mathcal{\bar{B}}$ is
not satisfied. Note for each position $i\in\mathcal{\tilde{I}}$, the intervals
$[i-\frac{\epsilon}{p},i+\frac{\epsilon}{p}]$ in $x$ are disjoint (by
definition of $\mathcal{\tilde{I}}$), and thus by Lemma 1.3,

$\sum_{i\in\mathcal{\tilde{I}}}\operatorname{cost}_{M}([i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}])\leq\operatorname{cost}(M)\leq(1+\delta)pn.$

The number of summands here is $|\mathcal{\tilde{I}}|\geq(1-5\epsilon)pn$.
Moreover, as $\mathcal{\bar{B}}$ is not satisfied, the number of indices in
$\mathcal{\tilde{I}}$ such that the associated block in $x$ has cost $0$ is at
most $6\epsilon pn$, and thus at least $(1-11\epsilon)pn$ summands contribute
cost at least $1$. Let $A$ be the set of indices $i$ that contribute cost $1$
to the above summation. Then

$\sum_{i\in\mathcal{\tilde{I}}}\operatorname{cost}_{M}([i-\tfrac{\epsilon}{p},i+\tfrac{\epsilon}{p}])\geq|A|\cdot
1+((1-11\epsilon)pn-|A|)\cdot 2=(2-22\epsilon)pn-|A|.$

Thus $|A|\geq(1-22\epsilon-\delta)pn$. Let
$\tilde{S}=A\setminus\mathcal{\tilde{I}}_{M}$ and by our assumption
$|\tilde{S}|\geq\epsilon pn$. To get the exact size $|\tilde{S}|=\epsilon pn$,
we can replace $\tilde{S}$ with an arbitrary subset of it of the exact size.

Now define $S={\\{i-\frac{\epsilon}{p}\mid i\in\tilde{S}\\}}$,
$\bar{S}={\\{\min_{k\in\\{0,1\\}}M(i+k)\mid i\in S;M(i+k)\neq\bot\\}}$. For
each $i\in S$ define
$N_{i}=\max_{k\in[i,i+\frac{2\epsilon}{p}];M(k)\neq\bot}M(k)-\min_{k\in[i,i+\frac{2\epsilon}{p}];M(k)\neq\bot}M(k)$.
Define $\gamma=\\{N_{i}-\frac{2\epsilon}{p}\mid i\in S\\}$. Let us verify that
the event $\mathcal{E}_{S,\bar{S},\gamma}$ holds. Indeed,
$\tilde{S}\subset\mathcal{\tilde{I}}$. Moreover as for each $i\in S$,
$\operatorname{cost}_{M}[i,i+\tfrac{2\epsilon}{p}]=1$, which implies
$N_{i}\in\\{\frac{2\epsilon}{p}-1,\frac{2\epsilon}{p}+1\\}$. Moreover, the
block $x[i,i+\tfrac{2\epsilon}{p}]$ in $x$ is at distance at most 1 from the
corresponding block in $y$, and these blocks in $y$ are disjoint. Also for
each $i\in S$;
$i+\frac{\epsilon}{p}\in\mathcal{\tilde{I}}\setminus\mathcal{\tilde{I}}_{M}$.
Thus either $A^{p}(i)\neq\min_{k\in[i,i+\frac{2\epsilon}{p}]}\\{M(k)\mid
M(k)\neq\bot\\}$. In this case $\bar{i}\neq A^{p}(i)$ and otherwise
$A^{p}(i+\frac{2\epsilon}{p})\neq\max_{k\in[i,i+\frac{2\epsilon}{p}]}\\{M(k)\mid
M(k)\neq\bot\\}$ and thus $\bar{i}+\frac{2\epsilon}{p}+\gamma_{j}\neq
A^{p}(i+\frac{2\epsilon}{p})$ This completes the proof of (11).

Next, we prove (12). Fix $S,\bar{S}\subset[n]$ of the same size $\ell$ and
$\gamma\in\\{-1,1\\}^{\ell}$. Assume requirements (i), (ii) and (iii) hold
(otherwise, the probability is 0). Consider now a given $j\in[\ell]$. Let
$B_{i_{j}}=x[i_{j},i_{j}+\frac{2\epsilon}{p}]$ and
$\bar{B}_{i_{j}}=y[\bar{i}_{j},\bar{i}_{j}+\frac{2\epsilon}{p}+\gamma_{j}]$ be
the corresponding blocks in $x$ and $y$ and let $\gamma_{j}$ be the
corresponding value from $\gamma$.

Case $\gamma_{j}=-1$: Notice in this case the requirement
$\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$ implies that block
$\bar{B}_{i_{j}}$ is obtained by one deletion from $B_{i_{j}}$. We further
divide this into two subcases. The first subcase is when that deletion occurs
in the “middle” interval
$[i_{j}+\frac{\epsilon}{2p},i_{j}+\frac{3\epsilon}{2p}]$ (including the
boundary points). This implies $\forall
t\in\\{0,\dots,\frac{2\epsilon}{p}\\}\cup\\{\frac{3\epsilon}{2p}+1,\dots,\frac{2\epsilon}{p}\\}$,
(a) the prefix of $B_{i_{j}}$ (i.e., $x[i_{j},i_{j}+\frac{\epsilon}{2p}-1]$)
satisfies $x[i_{j}+t]=y[\bar{i}_{j}+t]$ as the deletion occurs after this
prefix and (b) the suffix of $B_{i_{j}}$ (i.e.,
$x[i_{j}+\frac{3\epsilon}{2p}+1,i_{j}+\frac{2\epsilon}{p}]$) satisfies
$x[i_{j}+t]=y[\bar{i}_{j}+t-1]$ as the deletion occurs before this suffix. Now
again $x$ and $y$ are random but correlated through $A^{p}$; thus $x[i_{j}+t]$
and $y[\bar{i}_{j}+t]$ (or $y[\bar{i}_{j}+t-1]$) are chosen independently at
random unless $A^{p}$ aligns their positions, i.e.,
$A^{p}(i_{j}+t)=\bar{i}_{j}+t$ (or $=\bar{i}_{j}+t-1$). This cannot happen for
both $t=0$ and $t=\frac{2\epsilon}{p}$ as we assumed that condition (iii) is
satisfied. If $A^{p}(i_{j}+t)\neq\bar{i}_{j}+t$ for $t=0$, then the same holds
for all $t=1,\cdots,\frac{\epsilon}{2p}-1$, because $A^{p}$ has no edit
operation in the interval $[i_{j},i_{j}+\frac{\epsilon}{2p}-1]$, and thus

$A^{p}(i_{j}+t)=A^{p}(i_{j})+t\neq\bar{i}_{j}+t.$

If $A^{p}(i_{j}+t)\neq\bar{i}_{j}+t-1$ for $t=\frac{2\epsilon}{p}$, then by a
similar argument, the same inequality holds for all
$t=\frac{3\epsilon}{p}+1,\dots,\frac{2\epsilon}{p}-1$. Either way, we conclude
that for the event $\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$ to occur,
at least $\frac{\epsilon}{2p}$ constraints of the form
$x[i_{j}+t]=y[\bar{i}_{j}+t]$ must be satisfied, where these two positions are
not aligned by $A^{p}$, and thus these two symbols are chosen independently at
random.

Next, consider the subcase of a deletion outside the “middle” interval of
$B_{i_{j}}$, i.e., in
$[i_{j},i_{j}+\frac{\epsilon}{2p}-1]\cup[i_{j}+\frac{3\epsilon}{2p}+1,i_{j}+\frac{2\epsilon}{p}]$.
Let us first assume that the deletion occurs from interval
$[i_{j},i_{j}+\frac{\epsilon}{2p}-1]$. This implies for all
$t\in[\frac{\epsilon}{2p},\frac{3\epsilon}{2p}]$,
$x[i_{j}+t]=y[\bar{i}_{j}+t-1]$. Again we can claim the two symbols
$x[i_{j}+t]$ and $y[\bar{i}_{j}+t-1]$ are chosen independently at random
unless $A^{p}$ aligns their positions, $A^{p}(i_{j}+t)=\bar{i}_{j}+t-1$. Now
observe that this cannot happen for both $t=\frac{\epsilon}{p}-1$ and
$t=\frac{\epsilon}{p}+1$, because in that case,
$A^{p}(i_{j}+\frac{\epsilon}{p}+1)-A^{p}(i_{j}+\frac{\epsilon}{p}-1)=\frac{\epsilon}{p}-(\frac{\epsilon}{p}-2)=2$;
however $i_{j}+\frac{\epsilon}{p}\in\mathcal{\tilde{I}}$ implies that $A^{p}$
has exactly one edit operation (insertion or deletion) in the interval
$[i_{j}+\frac{\epsilon}{p}-1,i_{j}+\frac{\epsilon}{p}+1]$ (and not in the
boundary points), thus
$A^{p}(i_{j}+\frac{\epsilon}{p}+1)-A^{p}(i_{j}+\frac{\epsilon}{p}-1)\in\\{1,3\\}$.
Assume first $A^{p}(i_{j}+t)\neq\bar{i}_{j}+t-1$ for $t=\frac{\epsilon}{p}+1$.
Then the same must hold also for all
$t=\frac{\epsilon}{p}+2,\cdots,\frac{3\epsilon}{2p}$, because
$i_{j}+\frac{\epsilon}{p}\in\mathcal{\tilde{I}}$ and this implies that $A^{p}$
has no edit operation in the interval
$[i_{j}+\frac{\epsilon}{p}+1,i_{j}+\frac{3\epsilon}{2p}]$, thus

$A^{p}(i_{j}+t)=A^{p}(i_{j}+\tfrac{\epsilon}{p}+1)+(t-\tfrac{\epsilon}{p}-1)\neq(\bar{i}_{j}+\tfrac{\epsilon}{p})+(t-\tfrac{\epsilon}{p}-1)=\bar{i}_{j}+t-1.$

We can apply a similar argument for $t=\frac{\epsilon}{p}-1$, and again we
conclude that, for the event $\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$
to occur, at least $\frac{\epsilon}{2p}$ constraints of the form
$x[i_{j}+t]=y[\bar{i}_{j}+t-1]$ must be satisfied where these two positions
are not aligned by $A^{p}$, and thus these two symbols are chosen
independently at random. For the case where the deletion occurs in the
interval $[i_{j}+\frac{3\epsilon}{2p}+1,i_{j}+\frac{2\epsilon}{p}]$, following
a similar argument we can show if
$\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$ then for each
$t\in[\frac{\epsilon}{2p},\frac{3\epsilon}{2p}]$,
$x[i_{j}+t]=y[\bar{i}_{j}+t]$ where again these two positions are not aligned
by $A^{p}$ and hence the two symbols are chosen independently at random.

Case $\gamma_{j}=1$: We can show that if
$\operatorname{ED}(B_{i_{j}},\bar{B}_{i_{j}})=1$ then at least
$\frac{\epsilon}{2p}$ requirements of the form $x[i_{j}+t]=y[\bar{i}_{j}+t]$
(or $=y[\bar{i}_{j}+t+1]$) must be satisfied where these two positions are not
aligned by $A^{p}$, and thus these two symbols are chosen independently at
random.

The above argument applies to every $j\in[\ell]$, yielding overall at least
$\ell\cdot\tfrac{\epsilon}{2p}$ requirements of the form
$x[i_{j}+t]=y[\bar{i}_{j}+t^{\prime}]$ (where $t^{\prime}\in\\{t-1,t,t+1\\}$),
where these two symbols are chosen independently at random. Observe that each
$y[\bar{i}_{j}+t^{\prime}]$ is either a character $x[k]$ (for $k$ arising from
$A^{p}$) or completely independent. Since each character of $x$ appears in at
most $2$ requirements (once on each side), we can extract a subset of at one-
third of the requirements such that the positions in $x$ appearing there are
all distinct, and thus the events are independent.We overall obtain at least
$\tfrac{1}{3}\ell\cdot\tfrac{\epsilon}{2p}$ requirements, each occurring
independently with probability $1/|\Sigma|$, and thus

$\Pr[\mathcal{E}_{S,\bar{S},\gamma}]\leq|\Sigma|^{-\epsilon\ell/(6p)}.$