# Near-Optimal Average-Case Approximate Trace Reconstruction
from Few Traces

Xi Chen
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants CCF-1703925 and IIS-1838154.
Anindya De
University of Pennsylvania
<EMAIL_ADDRESS>Supported by NSF grants CCF-1926872 and CCF-1910534.
Chin Ho Lee
Columbia University
<EMAIL_ADDRESS>Supported by the Croucher Foundation and the Simons
Collaboration on Algorithms and Geometry. Rocco A. Servedio
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants CCF-1814873, IIS-1838154,
CCF-1563155, and by the Simons Collaboration on Algorithms and Geometry.
Sandip Sinha
Columbia University
<EMAIL_ADDRESS>Supported by NSF grants CCF-1714818, CCF-1822809,
IIS-1838154, CCF-1617955, CCF-1740833, and by the Simons Collaboration on
Algorithms and Geometry.

###### Abstract

In the standard trace reconstruction problem, the goal is to _exactly_
reconstruct an unknown source string $\mathsf{x}\in\\{0,1\\}^{n}$ from
independent “traces”, which are copies of $\mathsf{x}$ that have been
corrupted by a $\delta$-deletion channel which independently deletes each bit
of $\mathsf{x}$ with probability $\delta$ and concatenates the surviving bits.
We study the _approximate_ trace reconstruction problem, in which the goal is
only to obtain a high-accuracy approximation of $\mathsf{x}$ rather than an
exact reconstruction.

We give an efficient algorithm, and a near-matching lower bound, for
approximate reconstruction of a random source string
$\mathsf{x}\in\\{0,1\\}^{n}$ from few traces. Our main algorithmic result is a
polynomial-time algorithm with the following property: for any deletion rate
$0<\delta<1$ (which may depend on $n$), for almost every source string
$\mathsf{x}\in\\{0,1\\}^{n}$, given any number $M\leq\Theta(1/\delta)$ of
traces from $\mathrm{Del}_{\delta}(\mathsf{x})$, the algorithm constructs a
hypothesis string $\widehat{\mathsf{x}}$ that has edit distance at most
$n\cdot(\delta M)^{\Omega(M)}$ from $\mathsf{x}$. We also prove a near-
matching information-theoretic lower bound showing that given
$M\leq\Theta(1/\delta)$ traces from $\mathrm{Del}_{\delta}(\mathsf{x})$ for a
random $n$-bit string $\mathsf{x}$, the smallest possible expected edit
distance that any algorithm can achieve, regardless of its running time, is
$n\cdot(\delta M)^{O(M)}$.

##  1 Introduction

###  1.1 Background and prior work

In the _trace reconstruction problem_ [Kal73, Lev01b, Lev01a, BKKM04], there
is an unknown $n$-bit source string $\mathsf{x}\in\\{0,1\\}^{n}$, and a
reconstruction algorithm that has access to independent _traces_ of
$\mathsf{x}$, where a trace of $\mathsf{x}$ is a draw from
$\mathrm{Del}_{\delta}(\mathsf{x})$. Here $\mathrm{Del}_{\delta}(\cdot)$ is
the _deletion channel_ , which independently deletes each bit of $\mathsf{x}$
with probability $\delta$ and outputs the concatenation of the surviving bits.
The goal of the reconstruction algorithm is to correctly reconstruct the
source string $\mathsf{x}$.

####  1.1.1 Exact trace reconstruction

Much research effort has been dedicated to different aspects of the trace
reconstruction problem in recent years [MPV14, DOS17, NP17, PZ17, HPP18,
HHP18, BCF+19, BCSS19, Cha21a, KMMP19, HPPZ19, Cha21b, NR21, CDL+21b,
CDL+21a]. In the “worst-case” version of trace reconstruction, the source
string $\mathsf{x}$ may be an arbitrary $n$-bit string. This is a challenging
problem, with the best known information theoretic lower bound on the number
of traces required for trace reconstruction (for constant deletion rates
$\delta$) being $\tilde{\Omega}(n^{3/2})$ traces [Cha21a] and the best known
information theoretic upper bound being $\exp(\tilde{O}(n^{1/5}))$ traces
[Cha21b] (improving on earlier $\exp(\tilde{O}(n^{1/2}))$ and
$\exp(\tilde{O}(n^{1/3}))$-time and sample algorithms due to [HMPW08] and
[NP17, DOS17] respectively). In the subconstant deletion rate regime, a
$\mathrm{poly}(n)$-time and sample algorithm for worst-case source strings was
recently given in [CDL+21a] for deletion rate
$\delta=O(1/n^{1/3+\varepsilon})$, improving on an earlier result for deletion
rate $\delta=O(1/n^{1/2+\varepsilon})$ [BKKM04]. Turning to the “average-case”
variant of trace reconstruction, the goal is to give algorithms (and lower
bounds) that hold for most possible source strings $\mathsf{x}$ (equivalently,
hold with high probability for a uniform random source string
$\text{\boldmath${\mathsf{x}}$}\in\\{0,1\\}^{n}$). For the average-case
problem, at constant deletion rate $\delta$ the current best known lower bound
is $\tilde{\Omega}((\log n)^{5/2})$ traces [Cha21a] and the best known upper
bound is $\exp(O(\log n)^{1/3})$ traces [HPP18, HPPZ19]. In [BKKM04] an
$O(\log n)$-trace, $\mathrm{poly}(n)$-time algorithm is given for the average
case problem when the deletion rate is $\delta=O(1/\log n).$

####  1.1.2 Approximate trace reconstruction

Motivation. In this paper we study a relaxation of the exact trace
reconstruction problem in which the goal is only to obtain an _approximation_
of the unknown source string $\mathsf{x}$. Of course this immediately raises
the question of what distance measure to use; throughout this paper we use
edit distance as our distance measure between strings. We remark that edit
distance is a natural metric to consider in the context of trace
reconstruction: in particular, trace reconstruction is motivated by problems
such as ancestral DNA reconstruction where the natural corruption process
includes synchronization errors such as insertion and deletion. Indeed, edit
distance is the distance measure used in all of the works discussed below
under “Prior work.”

The study of approximate trace reconstruction has several natural motivations;
first, in some applications a high-accuracy reconstruction of $\mathsf{x}$ may
be all that is required rather than exact reconstruction. Second, it is of
interest to obtain algorithmic results for trace reconstruction in settings
where insufficiently many traces are available for exact reconstruction
(because of known lower bounds mentioned above); approximate trace
reconstruction offers a potential avenue for obtaining rigorous results in
such settings. Finally, as sketched above, there is a frustrating exponential
gap between the known upper and lower bounds for exact trace reconstruction in
both the worst-case and average-case problem variants. Hence it is natural to
wonder whether sharper bounds can be achieved for approximate versions of the
problem.

Prior work. Several authors have quite recently considered the approximate
trace reconstruction problem and related questions.

Davies, Raćz, Rashtchian, and Schiffer [DRRS21] gave several algorithms that
use $\mathrm{polylog}(n)$ traces and achieve edit distance
$n/\mathrm{polylog}(n)$ for certain classes of source strings defined by
various run-length assumptions. They also give other algorithms which, under
stronger run-length assumptions, succeed in performing approximate
reconstruction using only a single trace. In another recent work,
Srinivasavaradhan, Du, Diggavi, and Fragouli [SDDF18] proposed heuristics for
approximate reconstruction based on a few traces.

Sima and Bruck [SB21] have recently studied exact trace reconstruction under
an edit distance constraint. They showed that $n^{O(k)}$ traces suffice to
distinguish between two (known) worst-case $n$-bit strings that are promised
to have edit distance at most $k$ from each other. In a related but
incomparable result, Grigorescu, Sudan, and Zhu [GSZ21] have given lower
bounds on “mean-based” algorithms for distinguishing between worst-case pairs
of strings that have small edit distance.

Summarizing the prior results on approximate trace reconstruction, we are not
aware of either algorithms or lower bounds in the previous literature that
apply to typical source strings
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ (though see below for a
discussion of the recent work of [CP21] that is simultaneous to ours). It is
easy to see that simply outputting a single trace gives expected edit distance
$\delta n$ (for any source string), and also that given $M$ traces no
algorithm can achieve expected edit distance better than $\Theta(\delta^{M}n)$
for random source strings (since in expectation $\delta^{M}n$ bits of the
$n$-bit source string will have been deleted from all $M$ traces). Other than
these simple observations, to the best of our knowledge no prior results were
known, either in terms of algorithms or lower bounds, for approximate trace
reconstruction of random strings. We describe our algorithms and lower bounds
for this setting below.

###  1.2 Our results

Matching upper and lower bounds on approximate reconstruction of random
strings from few traces. Our main contribution is the following algorithmic
result:

######  Theorem 1 (Approximate average-case trace reconstruction algorithm).

There is a $\mathrm{poly}(n)$ time algorithm Reconstruct with the following
property: Let $0<\delta<1$, and let ${\mathsf{x}}$ be an unknown source string
that is uniform random over $\\{0,1\\}^{n}$. Let
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
be $M\leq\Theta(1/\delta)$ independent traces drawn from
$\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$. Then with probability
at least $1-1/\mathrm{poly}(n)$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$,
the output of Reconstruct on input $\delta$ and
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
is a string $\widehat{\mathsf{x}}\in\\{0,1\\}^{\ast}$ that has
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$},\widehat{\mathsf{x}})\leq
n\cdot(\delta M)^{\Omega(M)}.$

An interesting special case of Theorem 1 is obtained when the number of
available traces $M$ is $\Theta(1/\delta).$ In this case the Reconstruct
algorithm achieves edit distance $n/2^{\Omega(1/\delta)}$, which is
exponentially better than the benchmark of $\delta n$ edit distance that is
trivially achievable using a single trace.

To complement Theorem 1, we prove an information-theoretic lower bound on
approximate trace reconstruction of random strings from
$M\leq\Theta(1/\delta)$ traces. This lower bound shows that the accuracy
achieved by Reconstruct is essentially the best possible:

######  Theorem 2 (Lower bound on approximate average-case trace
reconstruction).

Let $0<\delta<1$, and let ${\mathsf{x}}$ be an unknown source string that is
uniform random over $\\{0,1\\}^{n}$. Let
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
be $M$ independent traces drawn from
$\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$, where
$M\leq\Theta(1/\delta)$. Let $\tt{A}$ be any algorithm which, given $\delta$
and
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
as input, outputs a hypothesis string $\widehat{\mathsf{x}}$ for
${\mathsf{x}}$. Then the expected edit distance between $\widehat{\mathsf{x}}$
and ${\mathsf{x}}$ is at least $n\cdot(\delta M)^{O(M)}$.

We observe that for natural parameter settings, Theorem 2 improves on the
simple $\Omega(\delta^{M}n)$ expected edit distance lower bound mentioned
earlier; for example, taking $M=\Theta(1/\delta)$, Theorem 2 proves that the
best possible accuracy is $n/2^{O(M)}$ rather than $\delta^{M}n.$

######  Remark 3.

In simultaneous and independent work to ours, Chase and Peres [CP21] have also
considered the problem of approximate trace reconstruction of random source
strings ${\mathsf{x}}$. Their main result is that for any constant deletion
rate $\delta$ (bounded away from 1) and any constant $\varepsilon$ (bounded
away from 0), there is an algorithm that uses $O_{\delta,\varepsilon}(1)$
traces and, with high probability over a random source string
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, succeeds in reconstructing
a hypothesis string $\widehat{x}$ with edit distance at most $\varepsilon n$
from ${\mathsf{x}}$.

The work of [CP21] and the current paper focus on different parameter
settings, in particular different regimes for the number of traces available
to the algorithm, and establish complementary results. The results of [CP21]
apply in the regime where “many traces ” (significantly more than
$\Theta(1/\delta)$) are available, and give high-accuracy reconstruction in
this regime. In contrast, our results apply in the “few traces” regime where
only some number $1\leq M\leq\Theta(1/\delta)$ of traces are available, and
give essentially optimal reconstruction for any such small number of traces.

###  1.3 Discussion and future work

A number of directions suggest themselves for future work on approximate trace
reconstruction; we close this introduction by briefly mentioning a few of
these.

One natural goal is to obtain results for average-case approximate trace
reconstruction which generalize both the results of the current paper and the
results of [CP21], by establishing sharp bounds on approximate average-case
trace reconstruction in the regime where more than $\Theta(1/\delta)$ many
traces are available. It is clear that the $n\cdot(\delta M)^{\Theta(M)}$ form
of our edit distance bound no longer holds once $M$ is $\omega(1/\delta)$; it
would be interesting to understand the best achievable edit distance, as a
function of $\delta$ and $M$, in this regime.

Another natural goal is to obtain algorithmic results for approximate trace
reconstruction of _worst-case_ rather than random strings. Here we observe
that the current state of the art for worst-case exact trace reconstruction
places significant limitations on how much better than edit distance $\delta
n$ (trivially achievable by simply outputting a random trace) it is possible
to do for approximate reconstruction of worst-case strings. As noted earlier,
until quite recently the best result known for the low deletion rate regime
was that of [BKKM04], which gave an algorithm using $O(n\log n)$ traces to
reconstruct an arbitrary source string $\mathsf{x}$ at deletion rate
$\delta=n^{-(1/2+\varepsilon)}$. This was recently strengthened to a
$\mathrm{poly}(n)$-trace algorithm that reconstructs at rate
$\delta=n^{-(1/3+\varepsilon)}$ [CDL+21a]. For the worst case approximate
trace reconstruction problem, achieving edit distance $\delta^{3}n$ for all
$\delta$, even using $\mathrm{poly}(n)$ traces, would require improving the
recently established state of the art from [CDL+21a] for the low-deletion-rate
regime of the exact reconstruction problem.

##  2 Our approach

###  2.1 Overview of our algorithmic approach (Theorem 1)

####  2.1.1 Some preliminary observations and simplifications

We begin by observing that to prove Theorem 1 it suffices to prove it under
the assumptions that

${\frac{1}{n^{2}}}\leq\delta<\frac{1}{KM},\quad\quad K^{2}\leq
M\leq{\frac{1}{K\delta}},\quad\quad\text{and}\quad\quad(\delta M)^{M/K}\geq
1/n^{2},$ (1)

for a sufficiently large absolute constant $K$. The upper bounds on $\delta$
and $M$ follow directly from our assumption $M\leq\Theta(1/\delta)$ in Theorem
1. For the lower bound on $\delta$, note that if $\delta<1/n^{2}$, then with
probability at least $1-1/n$ a single input trace will have no bits deleted
and hence will trivially yield a string $\widehat{\mathsf{x}}$ that has
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$},\widehat{\mathsf{x}})=0$.

For the lower bound on $M$, we observe that if $M<K^{2}$, then a single trace
would satisfy the claimed edit distance bound in Theorem 1. Indeed, since a
single trace has edit distance from ${\mathsf{x}}$ distributed as
$\mathrm{Bin}(n,\delta)$, and the probability that a draw from
$\mathrm{Bin}(n,\delta)$ exceeds $n\cdot\delta^{0.1}$ is at most
$n^{-\Omega(1)}$ (by a standard multiplicative Chernoff bound, using that
$1/n^{2}\leq\delta\leq 1/K$), the trivial algorithm that simply outputs a
single input trace would satisfy edit distance

$n\delta^{0.1}\leq n(\delta M)^{0.1}\leq n(\delta M)^{0.1M/K^{2}}=n(\delta
M)^{\Omega(M)}.$

For our final simplifying observation that $M$ and $\delta$ jointly satisfy
$(\delta M)^{M/K}\geq 1/n^{2}$, note that if $(\delta M)^{M/K}$ is less than
$1/n^{2}$, then the claimed high-probability edit distance bound
$n\cdot(\delta M)^{\Omega(M)}$ of Theorem 1 is less than 1 (for a suitable
choice of the hidden constants), and hence the claim of Theorem 1 is that with
high probability the edit distance achieved is zero. In this case since
$(\delta M)^{M/K}$ is decreasing for $M\in[0,\delta/e]$, we can simply use
$M^{\prime}<M$ traces so that $1/n^{2}\leq(\delta
M^{\prime})^{M^{\prime}/K}<1/n$, and achieve edit distance $n\cdot(\delta
M^{\prime})^{M^{\prime}/K}$ which will also achieve edit distance 0 (which of
course suffices to achieve the edit distance required by the theorem
statement). Therefore we will assume that the conditions given in (1) hold
throughout the rest of our proof of Theorem 1.

####  2.1.2 The high-level approach

Our main algorithm Reconstruct makes essential use of one particular
distinguished trace, which we denote $\text{\boldmath${\mathsf{y}}$}^{\ast}$
and refer to as the _reference trace_ , as well as $M$ other traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.
The overall Reconstruct algorithm works by repeatedly executing two different
subroutines. Below we first give a high level description of what each of
these subroutines does and then we present the overall algorithm and explain
how it uses these subroutines.

First subroutine: Alignment. The first subroutine is an alignment procedure
which we call Align. It takes as input the reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$ and a pointer $\ell^{\ast}$ to a
location in the reference trace, as well as the $M$ other traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.
It outputs a list of $M$ pointers $(\ell^{(1)},\dots,\ell^{(M)})$ where each
pointer $\ell^{(m)}$ specifies a location in the $m$-th trace
$\text{\boldmath${\mathsf{y}}$}^{(m)}.$ Roughly speaking, Align uses the
reference trace to “align” the other $M$ traces, i.e. to come up with a
pointer into each trace so that most of the pointers agree (Align does not
change the location $\ell^{\ast}$ of the pointer into the reference trace). In
more detail but still at a high level, the main guarantee of the Align
algorithm is that with high probability, a clear majority of the $M$ pointers
all point to locations that came from the same bit
$\text{\boldmath${\mathsf{x}}$}_{i}$ of the source string ${\mathsf{x}}$.
(Another important guarantee is that with high probability this location
$i\in[n]$ is “not too far” from the location in ${\mathsf{x}}$ that
$\text{\boldmath${\mathsf{y}}$}^{\ast}_{\ell^{\ast}}$ came from; we give more
details on this below.) Thus a successful run of Align results in a clear
majority of the $M+1$ pointers (including the reference trace’s pointer
$\ell^{\ast}$) all being in agreement. We refer to a specification of the
pointer locations $(\ell^{(1)},\dots,\ell^{(M)})$ as a _configuration_ , and
we say that a configuration for which there is a clear majority in agreement
as described above is _in consensus._ (We give a fully detailed definition in
Section 2.2, along with a detailed statement of the Align algorithm’s
performance guarantee.) We emphasize that the correctness of this subroutine,
i.e., Alignment, crucially relies on the source string $\boldsymbol{x}$ being
uniform random.

Second subroutine: Bitwise Majority. The second subroutine is a “Bitwise
Majority Alignment” procedure, which we call BMA. This procedure was first
introduced in the work of [BKKM04] and was further analyzed in the recent work
[CDL+21a]. (As we explain below, a crucial ingredient in our proof of Theorem
1 is a new refined analysis of BMA that goes significantly beyond the results
of [CDL+21a].) All of the output bits that our algorithm constructs are
produced by BMA. The BMA procedure takes as input the $M+1$ traces
$\text{\boldmath${\mathsf{y}}$}^{\ast},\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
and the corresponding pointers $\ell^{\ast},\ell^{(1)},\dots,\ell^{(M)}$. The
BMA algorithm is run for $R:=(\delta M)^{-\Theta(M)}$ many stages to
reconstruct $R$ output bits; in the course of its execution it updates the
pointers into all $M+1$ of the traces
$\text{\boldmath${\mathsf{y}}$}^{\ast},\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.

To explain the performance guarantee of the BMA procedure we need the notion
of a _$k$ -desert._ Roughly speaking, a binary string $z\in\\{0,1\\}^{*}$ is
said to be a _$k$ -desert_ if (i) it is sufficiently long, and (ii) it is a
prefix of $s^{\infty}$ for some $s\in\\{0,1\\}^{\leq k}$ (we give a precise
definition in Section 2.3). The main guarantee of the BMA procedure is that if
it is run on a configuration that is in consensus at some location $i$ in the
source string $x$, then with high probability it produces a $R$-bit string
that agrees with $(x_{i},x_{i+1},\dots)$ up to the location (if any) where a
$k$-desert of length $L:=\Theta(M\log(1/(M\delta)))$ first appears, for some
$k\leq L/2.$ We note that unlike the first subroutine Alignment, the guarantee
of BMA procedure is a worst-case guarantee.

The overall Reconstruct algorithm. As stated earlier, the overall algorithm
repeatedly runs Align, then BMA, then Align, then BMA, and so on. We present a
slightly simplified version of the algorithm in Figure 1 (see Section 6 for
the formal algorithm; the version in Figure 1 differs only in that some
parameter settings have been slightly simplified for the sake of readability).

Input: A positive integer $n$ and $(M+1)$ traces
${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ for some
$M\leq 1/(K\delta)$

Output: A binary string ${\mathsf{w}}$

1 Set $\ell^{*}=1$ and ${\mathsf{w}}=\varepsilon$ (the empty string)

2 while  _$\ell^{*}\leq|{\mathsf{y}}^{*}|$_ do

3 Run $\textup{{\tt Align}}\hskip
1.13791pt(\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$
to obtain a tuple of locations $(\ell^{(1)},\ldots,\ell^{(M)})$

4 Run $\smash{\textup{{\tt BMA}}\hskip
1.13791pt({\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)};\ell^{*},\ell^{(1)},\ldots,\ell^{(m)})}$
to obtain a binary string ($\varepsilon$ or in $\\{0,1\\}^{R}$)

5 Concatenate the string returned by BMA to the end of ${\mathsf{w}}$

6 Set $\ell^{*}$ to be the final pointer of ${\mathsf{y}}^{*}$ in the run of
BMA above and increment it

7

return ${\mathsf{w}}$.

Algorithm 1 Reconstruct (slightly simplified) Figure 1: A slightly simplified
version of our main algorithm Reconstruct (the actual algorithm differs in
some small details and is given in Figure 6).

The high level intuition for why the algorithm succeeds is as follows. Each
run of Align with high probability succeeds in putting the $M$ traces in
consensus at a location “not too far” from the location in ${\mathsf{x}}$
corresponding to $\text{\boldmath${\mathsf{y}}$}^{\ast}_{\ell^{\ast}}$. Given
that this consensus has been achieved by Align, then the subsequent run of BMA
with high probability succeeds in correctly reconstructing the next
$R:=(\delta M)^{-\Theta(M)}$ many bits of ${\mathsf{x}}$. In the course of
running BMA the pointer $\ell^{\ast}$ is with high probability advanced to
“approximately the right location” corresponding to the last-reconstructed bit
of ${\mathsf{x}}$, so the next run of Align again establishes consensus at
approximately the right location. Thus the overall output string $w$ of the
algorithm is the concatenation of many length-$R$ strings, most of which
correspond to subwords of ${\mathsf{x}}$ from approximately the right
locations. From this it can be shown that the overall reconstructed string is
not too far in edit distance from ${\mathsf{x}}$.

The above high-level explanation sketches an idealized version of the actual
scenario and glosses over a number of technical difficulties. In more detail,
there are many sources of error from different possible failure events and a
careful analysis is required (and is provided in Section 6) to keep the
failure probabilities from all of these under control and not “give away too
much” in the overall edit distance. The issues that must be handled include
the following:

  * •

Align may fail to align the traces to a consensus location, or may misalign
the traces and achieve consensus at a location that is far away from the
location in ${\mathsf{x}}$ corresponding to
$\text{\boldmath${\mathsf{y}}$}_{\ell^{\ast}}^{\ast}$. Our analysis shows that
this happens with small (but non-negligible probability), and bounds the
cumulative error (edit distance) incurred by the runs of Align for which this
happens.

  * •

Even when Align aligns the traces at a location that is “not too far” from the
correct location, the alignment location in ${\mathsf{x}}$ may not be exactly
the location in ${\mathsf{x}}$ corresponding to
$\text{\boldmath${\mathsf{y}}$}_{\ell^{\ast}}^{\ast}$. This contributes to the
overall edit distance between $\widehat{x}$ and ${\mathsf{x}}$ even when the
Align algorithm succeeds.

  * •

On average the random string ${\mathsf{x}}$ will have a $k$-desert of length
$L$ occuring roughly once every $2^{\Theta(L)}$ positions. When a run of BMA
encounters such a location the resulting $R$-bit string that it produces may
be badly off from the true corresponding portion of ${\mathsf{x}}$. This
contributes to the overall edit distance between $\widehat{x}$ and
${\mathsf{x}}$ even when the algorithm succeeds.

  * •

Even when the portion of ${\mathsf{x}}$ that a given run of BMA is operating
on does not contain a $k$-desert of length $L$, the BMA algorithm may fail to
correctly reconstruct the relevant portion of BMA with small (but non-
negligible) probability. Our analysis bounds the overall error in the
reconstructed string that comes from such “failed runs” of BMA.

###  2.2 The Align procedure

As stated earlier, Align takes as input the reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$, a pointer $\ell^{\ast}$ to a location
in the reference trace, and the $M$ other traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$,
and outputs a list of $M$ pointers $\ell^{(1)},\dots,\ell^{(M)}$ into the $M$
traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}.$
In a successful run of Align, it generates a list of pointers most of which
point to locations that came from the same bit
$\text{\boldmath${\mathsf{x}}$}_{i}$ of the source string ${\mathsf{x}}$.

At a very high level, Align works in two stages. The first stage, which
performs an “approximate alignment,” consists of a sequence of iterative
refinement steps; in each successive step of this stage, for each trace
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ Align tries to identify successively
smaller subwords of $\text{\boldmath${\mathsf{y}}$}^{(m)}$ that fairly closely
match (as measured by edit distance) suitable successively smaller subwords,
centered at $\ell^{\ast}$, of the reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$. At the end of a successful execution
of the first stage, for each trace $\text{\boldmath${\mathsf{y}}$}^{(m)}$ a
relatively small subword $\text{\boldmath${\mathsf{y}}$}^{(m)}_{Q^{m}_{1}}$
has been identified which contains the “right location” in
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ (informally, corresponding to the
portion of ${\mathsf{x}}$ that
$\text{\boldmath${\mathsf{y}}$}^{\ast}_{\ell^{\ast}}$ came from). In the
second stage, Align searches for a suitable subword that appears in at least
95% of
$\text{\boldmath${\mathsf{y}}$}^{(1)}_{Q^{1}_{1}},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}_{Q^{M}_{1}}$
and uses the location of this subword in each
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ to determine the exact final pointer
location $\ell^{(m)}.$

Correctness of the second stage (given that a successful “approximate
alignment” was indeed achieved in the first stage) is established using an
elementary but careful analysis that we do not describe here but is given in
Section 4.4.2. To gain intuition for the iterative approach employed in the
first stage, it is useful to consider the following toy scenario: Fix an
$a$-bit subword ${\mathsf{w}}$ of the reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$ that is centered at location
$\ell^{\ast}$. Intuitively, the deletion rate $\delta$ is relatively low, so
the subword ${\mathsf{w}}$ of $\text{\boldmath${\mathsf{y}}$}^{\ast}$ should
have small edit distance from the corresponding subword of the source string
${\mathsf{x}}$, and, transitively, should also have small edit distance from
the corresponding subwords of each of the $M$ traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.
However, since ${\mathsf{x}}$ is uniform random (and hence each trace
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ is also uniform random), if $a$ is a
“small” value that is $\ll\log n$, then it is very likely that ${\mathsf{w}}$
will occur as an $\ell$-bit subword of each
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ in many locations, and thus a
simpleminded approach of just scanning all of
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ to try to find ${\mathsf{w}}$ (or a
close match to it) will not succeed in uniquely identifying the correct
location. But if $a$ is a “large” value (actually, being just modestly larger
than $\log n$ will do), then it is very likely that only one location in each
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ will be a close match to the $a$-bit
string ${\mathsf{w}}$. This reduces the problem of finding the right location
in the $\approx n$-bit string $\text{\boldmath${\mathsf{y}}$}^{(m)}$ to the
problem of finding the right location in the $\approx a$-bit subword of
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ that was just identified (by virtue of
closely matching ${\mathsf{w}}$); and now we can iterate.

A more complete overview and explanation of Align is given in Section 4.1.
Section 4 gives a detailed proof of Theorem 7, which is our main result about
Align; since the exact theorem statement is somewhat cumbersome (involving
various specific parameter settings), we give an informal version here and
defer the fully detailed statement to Section 4. Informally, we say that the
Align algorithm _succeeds_ on source string $\mathsf{x}$ with respect to a
tuple of traces
$({\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$ if the
following condition holds for “almost all” locations
$\ell^{*}\in[|{\mathsf{y}}^{*}|]$: The output $(\ell^{(1)},\ldots,\ell^{(M)})$
of $\textup{{\tt
Align}}(\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$
satisfies (1) At least 90% of $\mathrm{source}^{(m)}(\ell^{(m)})$, $m\in[M]$,
agree on the same location $i\in[n]$, and (2) The consensus location $i$ is
“quite close” to the location in ${\mathsf{x}}$ that
$\text{\boldmath${\mathsf{y}}$}^{\ast}_{\ell^{\ast}}$ came from. Now we can
state an informal version of Theorem 7, which gives a performance guarantee on
Align:

######  Theorem 4 (Main result about Align, informal statement).

Let $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and let
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
be independent traces drawn from
$\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$, where $\delta$ and
$M$ satisfy Equation 1. Then Align succeeds on ${\mathsf{x}}$ with respect to
$(\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)})$
with probability at least $1-1/\mathrm{poly}(n)$.

###  2.3 The BMA procedure

The Bitwise Majority Alignment, or BMA, procedure, operates in discrete time
steps on a collection of $M$ independent traces. At each time step it outputs
one bit of the hypothesis string that it is reconstructing. Throughout its
execution, at each time step $t$, for each $m\in[M]$ the BMA algorithm
maintains a pointer into the $m$-th trace. The idea of BMA is that at each
time step $t$, it should be the case that most of the pointers are correctly
aligned, i.e. the majority of the bits that they point to in their respective
traces came from the same bit of the source string $\mathsf{x}$. In the $t$-th
time step the majority vote of the $M$ bits that are pointed to in the traces
is the output bit BMA produces, and

  * •

For each trace in which the pointer points to a bit that agrees with the
majority, the pointer is incremented by one location;

  * •

For each trace in which the pointer points to a bit that disagrees with the
majority, the pointer stays in the same location.

A first analysis of BMA, for deletion rate $\delta$ slightly less than
$n^{-1/2}$, was originally given in [BKKM04], and more recently an analysis
for deletion rate $\delta$ slightly less than $n^{-1/3}$ was given in
[CDL+21a]. We give a significant extension of [CDL+21a] by providing a much
more refined analysis which yields a considerably stronger quantitative
result.111This quantitative strengthening plays an essential role in our being
able to obtain tight bounds (recall the essentially matching Theorems 1 and 2)
via our approach. In more detail, in the current work our analysis of BMA
handles deletion rates even as large as a (small) absolute constant
independent of $n$, and indeed handling such deletion rates is essential for
our overall results.

To state our main theorem about BMA we require the following terminology:
Recall that a string is said to be a _$k$ -desert_ for some $k\geq 1$ if it is
the prefix of ${\mathsf{s}}^{\infty}$ for some string
${\mathsf{s}}\in\\{0,1\\}^{k}$. We say a string is a _long desert_ if it is a
$k$-desert of length $L$ for some $k\leq L/2$.

Our main result about BMA says, roughly speaking, that if the source string
does not contain any long desert then with high probability BMA succeeds in
exactly reconstructing the source string, and moreover does so with a “clear
majority” in each round. Similar to Align, the detailed theorem statement
about BMA involves various specific parameter settings, so we defer its exact
statement until later (see Theorem 25) and here give an informal statement:

######  Theorem 5 (Main result about BMA, informal statement).

Let $\tilde{\mathsf{x}}\in\\{0,1\\}^{R}$ be a string that does not contain any
long desert. Let
$\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$
be independent traces. For suitable settings of $R,M,k,L$ and $\delta$, with
high probability BMA returns exactly $\tilde{\mathsf{x}}$, and in every round
$t\in[R]$ the majority is reached by at least $90\%$ of
$\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}$.

###  2.4 Overview of our lower bound approach (Theorem 2)

Our lower bound approach is informed by insights arising from the analysis of
our algorithm. Given the arguments sketched above for our algorithmic results,
it is natural to pursue a lower bound based on the difficulty of
reconstructing deserts. The high-level idea of our lower bound is that having
access to only a limited number $M\leq\Theta(1/\delta)$ of traces imposes
strong limitations on the ability of any reconstruction algorithm to
accurately estimate the lengths of deserts, and this inability to accurately
reconstruct deserts translates into an inability to perform overall high-
accuracy approximate reconstruction. Guided by this general idea, it is
natural to consider 1-deserts (runs of all 0’s or all 1’s) as potential
sources of hardness, and indeed this is our approach.

In more detail, our lower bound proceeds in four conceptual stages.

  1. 1.

We first (Section 7.1) consider the following simple distribution
distinguishing problem: an algorithm is given $M$ draws which are guaranteed
to come from one of two product distributions over
$\mathds{N}\times\mathds{N}$: (a) the product distribution
$\mathrm{Bin}(M,1-\delta)\times\mathrm{Bin}(M+1,1-\delta)$, or (b) the product
distribution $\mathrm{Bin}(M+1,1-\delta)\times\mathrm{Bin}(M,1-\delta)$, where
both (a) and (b) are equally likely to be the target product distribution. We
show that any algorithm for determining whether it is (a) or (b) must have
failure probability at least $(\delta M)^{O(M)}.$

  2. 2.

Next, in Section 7.2 we consider the algorithmic task of solving $B$
independent instances of the distinguishing problem described in (1) above;
this may be viewed as the problem of inferring an unknown $B$-bit string that
is uniform over $\\{0,1\\}^{B}$ given certain partial/noisy information about
the string. Building on (1) above, we show that the expected edit distance
from the output of any algorithm for this problem to the unknown uniform
string in $\\{0,1\\}^{B}$ will be at least $B(\delta M)^{O(M)}$.

  3. 3.

We then (in Section 7.3) observe that a random string ${\mathsf{x}}$ can be
viewed as containing, with high probability, $B=n/2^{\Theta(M)}$ independent
instances of the distribution distinguishing problem from (1). Roughly
speaking, this is because a random string
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ can be viewed as composed of
$n/(2M+4)$ blocks of $2M+4$ bits each, and with high probability
$\Theta(n/2^{2M+4})$ of these blocks will consist of either the string
$\alpha=0^{M}10^{M+1}11$ or the string $\beta=0^{M+1}10^{M}11$, and these two
strings are equally likely for each block. (The specific structure of these
$\alpha$ and $\beta$ strings is chosen to ensure that they cannot overlap;
this is useful for (4) below.)

  4. 4.

Using (3), in Section 7.3 we show that any algorithm that achieves a certain
$n(\delta M)^{\Omega(M)}$ expected edit distance for reconstructing a random
string from $M$ traces can be used to give an algorithm that solves
$B=n/2^{\Theta(M)}$ independent copies of the distinguishing problem described
in (1) with an expected edit distance that is lower than can possibly be
obtained, contradicting the lower bound from item (2) above. Establishing this
reduction is the most intricate part of our lower bound.

###  2.5 Organization

In Section 3 we set up some preliminaries. In Section 4 we prove Theorem 4,
our main result about the Align algorithm. In Section 5 we prove Theorem 5,
our main result about BMA. In Section 6 we use Theorems 4 and 5 to prove
Theorem 1. Finally, Section 7 proves our lower bound, Theorem 2.

##  3 Preliminaries

Notation. Given a positive integer $n$, we write $[n]$ to denote
$\\{1,\ldots,n\\}$. Given two integers $a\leq b$ we write $[a:b]$ to denote
$\\{a,\ldots,b\\}$. We write $\ln$ to denote natural logarithm and $\log$ to
denote logarithm to the base 2. We denote the set of non-negative integers by
$\mathbbm{Z}_{\geq 0}$. We write “$a=b\pm c$” to indicate that $b-c\leq a\leq
b+c$.

Subwords. It will be convenient for us to index a binary string
$\mathsf{x}\in\\{0,1\\}^{n}$ using $[1:n]$ as
$\mathsf{x}=(\mathsf{x}_{1},\dots,\mathsf{x}_{n})$. Given such a string
$\mathsf{x}\in\\{0,1\\}^{n}$ and integers $1\leq i\leq j\leq n$, we write
$\mathsf{x}_{[i:j]}$ to denote the _subword_
$(\mathsf{x}_{i},\mathsf{x}_{i+1},\dots,\mathsf{x}_{j})$ of $\mathsf{x}$. An
_$\ell$ -subword_ of $\mathsf{x}$ is a subword of $\mathsf{x}$ of length
$\ell$, given by
$(\mathsf{x}_{i},\mathsf{x}_{i+1},\dots,\mathsf{x}_{i+\ell-1})$ for some
$i\in[1:n-\ell+1]$.

Distributions. When we use bold font such as
$\mathbf{D},\text{\boldmath${\mathsf{y}}$},\boldsymbol{z}$, etc., it indicates
that the entity in question is a random variable. We write
“$\boldsymbol{r}\sim{\cal P}$” to indicate that random variable
$\boldsymbol{r}$ is distributed according to probability distribution ${\cal
P}$. If $S$ is a finite set we write “$\boldsymbol{r}\sim S$” to indicate that
$\boldsymbol{r}$ is distributed uniformly over $S$.

Deletion channel and traces. Throughout this paper the parameter $0<\delta<1$
denotes the _deletion probability_. Given a string
$\mathsf{x}\in\\{0,1\\}^{n}$, we write $\mathrm{Del}_{\delta}(\mathsf{x})$ to
denote the distribution of the string that results from passing $\mathsf{x}$
through the $\delta$-deletion channel (so the distribution
$\mathrm{Del}_{\delta}(\mathsf{x})$ is supported on $\\{0,1\\}^{\leq n}$), and
we refer to a string in the support of $\mathrm{Del}_{\delta}(\mathsf{x})$ as
a _trace_ of $\mathsf{x}$. Recall that a random trace
$\text{\boldmath${\mathsf{y}}$}\sim\mathrm{Del}_{\delta}(\mathsf{x})$ is
obtained by independently deleting each bit of $\mathsf{x}$ with probability
$\delta$ and concatenating the surviving bits. 222For simplicity in this work
we assume that the deletion probability $\delta$ is known to the
reconstruction algorithm. We note that it is possible to obtain a high-
accuracy estimate of $\delta$ simply by measuring the average length of traces
received from the deletion channel.

When a trace ${\mathsf{y}}$ is drawn from $\mathrm{Del}_{\delta}(\mathsf{x})$
we write $\mathbf{D}$ to denote the set of _locations deleted_ when
$\mathsf{x}$ goes through the deletion channel, i.e., $\mathbf{D}$ is obtained
by including each element of $[n]$ independently with probability $\delta$,
and ${\mathsf{y}}$ is set to be $\smash{\mathsf{x}_{[n]\setminus\mathbf{D}}}$.
(When the trace is denoted $\text{\boldmath${\mathsf{y}}$}^{\ast}$ or
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ we use $\mathbf{D}^{\ast}$ or
$\mathbf{D}^{(m)}$ to denote the set of locations deleted.)

As discussed earlier, our algorithm uses a special reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$ and $M$ additional traces
$\text{\boldmath${\mathsf{y}}$}^{(m)}$, $m\in[M]$, and maintains pointers into
each of these traces. We write $\ell^{\ast}$ to denote the pointer into
$\text{\boldmath${\mathsf{y}}$}^{\ast}$ and $\ell^{(m)}$ to denote the pointer
into $\text{\boldmath${\mathsf{y}}$}^{(m)}$ for $m\in[M]$.

Edit distance and matchings. It will be convenient for us to define the edit
distance between two strings
$\mathsf{x},\mathsf{x}^{\prime}\in\\{0,1\\}^{\ast}$ as

${d_{\mathrm{edit}}}(\mathsf{x},\mathsf{x}^{\prime}):=|\mathsf{x}|+|\mathsf{x}^{\prime}|-2\cdot|\mathrm{LCS}(\mathsf{x},\mathsf{x}^{\prime})|,$

where $|\mathrm{LCS}(\mathsf{x},\mathsf{x}^{\prime})|$ is the length of the
longest common subsequence of $\mathsf{x}$ and $\mathsf{x}^{\prime}$. This is
equivalent to viewing insertions and deletions of characters as being the only
allowable “atomic edits” that can be used to transform $\mathsf{x}$ to
$\mathsf{x}^{\prime}$, and is easily seen to be equivalent to the standard
definition (in which substitutions are also allowed) up to at most a factor of
2, since a substitution can be simulated by a deletion followed by an
insertion.

A _matching_ $\mu$ between two strings
$\mathsf{x},\mathsf{x}^{\prime}\in\\{0,1\\}^{\ast}$ is a list of pairs
$(i_{1},j_{1}),(i_{2},j_{2}),\dots$ such that $i_{1}\leq i_{2}\leq\cdots$,
$j_{1}\leq j_{2}\leq\cdots$, and for every $t$ we have
$\mathsf{x}_{i_{t}}=\mathsf{x}^{\prime}_{j_{t}}.$ The _size_ of a matching is
the number of pairs. We note that the largest matching between $\mathsf{x}$
and $\mathsf{x}^{\prime}$ is of length
$|\mathrm{LCS}(\mathsf{x},\mathsf{x}^{\prime})|$.

For two intervals $A=[a_{1},a_{2}]$ and $B=[b_{1},b_{2}]$ of equal length, we
write “$\mu(A)=B$” to indicate that for every element $a_{1}+j\in A$, the pair
$(a_{1}+j,b_{1}+j)$ is in the matching (note that this implies that the
subwords $\mathsf{x}_{A}$ and $\mathsf{x}^{\prime}_{B}$ are identical).

Some notational conventions. To aid the reader we adopt the following
conventions:

  * •

Locations in strings of different types: The letters $i,j$ are reserved for
locations in the source string $\mathsf{x}$, so these variables refer to
integers in the range $[1:n].$ We use capital letters $I,J$ to denote
intervals of such locations. The letters $p,q$ are reserved for locations in
traces, so if $p$ is a location in a particular trace ${\mathsf{y}}$ then it
refers to an integer in the range $[1:|{\mathsf{y}}|].$ We use capital letters
$P,Q$ to denote intervals of such locations. The letters $a,b$ are reserved
for locations in other incidental strings that arise in our analysis, and
intervals of such locations are denoted $A,B.$

  * •

Indexing multiple strings: On a number of occasions we deal with collections
of multiple strings (such as our $M$ traces). We index such collections with
parenthesized superscripts, so for example our $M$ traces are denoted
$\text{\boldmath${\mathsf{y}}$}^{(1)},\text{\boldmath${\mathsf{y}}$}^{(2)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.

  * •

Correspondence between traces and source string ${\mathsf{x}}$. Given a
location $q\in|\text{\boldmath${\mathsf{y}}$}^{\ast}|$ in the reference trace
$\text{\boldmath${\mathsf{y}}$}^{\ast}$, we write $\mathrm{source}^{\ast}(q)$
to denote the location $i\in[n]$ such that bit
$\text{\boldmath${\mathsf{x}}$}_{i}$ gave rise to
$\text{\boldmath${\mathsf{y}}$}^{\ast}_{q}$. For $m\in[M]$ we similarly write
$\mathrm{source}^{(m)}(q)$ to denote the location $i\in[n]$ such that bit
$\text{\boldmath${\mathsf{x}}$}_{i}$ gave rise to
$\text{\boldmath${\mathsf{y}}$}^{(m)}_{q}$ in the trace
$\text{\boldmath${\mathsf{y}}$}^{(m)}$. For an interval $Q=[q_{1}:q_{2}]$ of
locations in ${\mathsf{y}}^{(m)}$, we write $\mathrm{source}^{(m)}(Q)$ to
denote the set $\\{\mathrm{source}^{(m)}(q):q\in[q_{1}:q_{2}]\\}.$ We define
$\overline{\mathrm{source}^{(m)}(Q)}$ to be the interval
$[\mathrm{source}^{(m)}(a):\mathrm{source}^{(m)}(b)]\subseteq[n]$.

Given a location $i\in[n]$, if $i\notin{\mathbf{D}^{\ast}}$ then
$\mathrm{image}^{\ast}(i)$ denotes the element of
$[|\text{\boldmath${\mathsf{y}}$}^{\ast}|]$ that
$\text{\boldmath${\mathsf{x}}$}_{i}$ lands in (and if
$i\in{\mathbf{D}^{\ast}}$ then we define $\mathrm{image}^{\ast}(i)$ to be
$\bot$). The notation $\mathrm{image}^{(m)}(i)$ is defined similarly with
respect to trace $\text{\boldmath${\mathsf{y}}$}^{(m)}$, $m\in[M].$ We observe
that if $I\subseteq\overline{\mathrm{source}^{(m)}(Q)}$ then
$\mathrm{image}^{(m)}(I)\subseteq Q$.

  * •

Notation for bitstrings. To help the reader differentiate between bits and the
locations of bits in bitstrings, we use $\mathsf{sans\ serif\ font}$ to denote
“bit-valued objects.” Hence the uniform random source string in
$\\{0,1\\}^{n}$ is ${\mathsf{x}}$, the traces are
$\text{\boldmath${\mathsf{y}}$}^{\ast},\text{\boldmath${\mathsf{y}}$}^{(1)}$,
etc., a generic fixed word in $\\{0,1\\}^{\ast}$ which is not a random
variable would be denoted ${\mathsf{w}}$, a generic word in $\\{0,1\\}^{\ast}$
which is a random variable would be denoted ${\mathsf{w}}$, and so on.

Finally we introduce some useful terminology: We refer to a tuple of pointers
$(\ell^{(1)},\dots,\ell^{(M)})$ into traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\dots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
(so each $\ell^{(m)}$ belongs to $[|\text{\boldmath${\mathsf{y}}$}^{(m)}|]$)
as a _configuration_. We say the configuration $(\ell^{(1)},\dots,\ell^{(M)})$
is _in consensus_ if at least $0.9M$ of the values $m\in[M]$ all have
$\mathrm{source}^{(m)}(\ell^{(m)})$ equal to the same location $i\in[n]$.

###  3.1 Useful results

We recall McDiarmid’s basic “method of bounded differences” inequality, which
we will use repeatedly in our analysis:

######  Theorem 6 (Theorem 3.1 of [McD98]).

Let $\mathbf{X}=(\mathbf{X}_{1},\dots,\mathbf{X}_{n})$ be a family of
independent random variables where each $\mathbf{X}_{k}$ takes values in a set
$A_{k}$. Suppose that $f:A_{1}\times\cdots\times A_{n}\to\mathbbm{R}$
satisfies

$|f(x)-f(x^{\prime})|\leq c_{k}$

whenever the vectors $x$ and $x^{\prime}$ differ only in the $k$-th
coordinate. Then for any $t\geq 0$, writing $\mu$ for $\operatorname{{\bf
E}}[f(\mathbf{X})]$, we have

$\operatorname{{\bf Pr}}[f(\mathbf{X})-\mu\geq
t]\leq\exp\left(-2t^{2}/\sum_{k=1}^{n}c_{k}^{2}\right).$

We use standard notation for the binary entropy function $H(p)=-p\log
p-(1-p)\log(1-p)$, and we recall the standard upper bound on binomial
coefficients in terms of this function, namely that ${n\choose pn}\leq
2^{nH(p)}$ for any $0<p<1$.

##  4 The Align algorithm and proof of Theorem 4

Recall from Section 2.1.1 that the two parameters $\delta$ and $M$ satisfy

${\frac{1}{n^{2}}}\leq\delta<{\frac{1}{KM}}<{\frac{1}{K}}\quad\text{and}\quad
K^{2}\leq M\leq{\frac{1}{K\delta}},$ (2)

where $K$ is some sufficiently large absolute constant. Let

$H:=\frac{M}{K}\log\left(\frac{1}{\delta M}\right)\leq 2\log n,$ (3)

where the inequality is by Equation 1. We observe that Equation 2 also gives
that $H\geq K$, and that $2^{-\Omega(H)}=(\delta M)^{\Omega(M)}$. Let

$\gamma=0.01,\quad\tau=5/\gamma=500$ (4)

be two constants that will be used in this section.

In this section we describe the (deterministic) Align algorithm and prove
Theorem 4 about its performance. Let $\mathsf{x}\in\\{0,1\\}^{n}$ be the
source string and
${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ be traces of
$\mathsf{x}$ obtained with corresponding deletion sets
$D^{*},D^{(1)},\ldots,D^{(M)}\subseteq[n]$, respectively. The algorithm Align
takes $\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$
as inputs, where $\ell^{*}\in[5\tau\log n:|{\mathsf{y}}^{*}|-5\tau\log n]$,
and returns a tuple of locations $(\ell^{(1)},\ldots,\ell^{(M)})$.

The following terminology will be useful: we say that the Align algorithm
_succeeds_ on source string $\mathsf{x}$ with respect to a tuple of traces
$({\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$ if the
following condition holds for all except at most $2^{-0.1H}n$ many locations
$\ell^{*}\in[5\tau\log n:|{\mathsf{y}}^{*}|-5\tau\log n]$: The output
$(\ell^{(1)},\ldots,\ell^{(M)})$ of $\textup{{\tt
Align}}(\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$
satisfies

  1. 1.

The configuration $(\ell^{(1)},\dots,\ell^{(M)})$ is in consensus, i.e. at
least 90% of $\mathrm{source}^{(m)}(\ell^{(m)})$, $m\in[M]$, agree on the same
location $i\in[n]$, and

  2. 2.

The consensus location $i$ satisfies

$\mathrm{source}^{*}(\ell^{*})-2H\leq i\leq\mathrm{source}^{*}(\ell^{*}).$ (5)

Now we can state the main result of this section which gives a performance
guarantee on Align:

######  Theorem 7 (Theorem 4, detailed statement).

Let $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and let
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$
independently, where $\delta$ and $M$ satisfy Equations 2 and 3. Align
succeeds on ${\mathsf{x}}$ with respect to
$(\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)})$
with probability at least $1-1/n^{2}$.

###  4.1 Overview

We first give a high-level overview of Align. Let $\ell^{\ast}$ be a location
in the special reference trace ${\mathsf{y}}^{\ast}$ that is not too close to
the left and right ends of ${\mathsf{y}}^{*}$. Let
$Q_{S}^{*}\supset\cdots\supset Q_{1}^{*}$ be a sequence of nested intervals
(of locations of ${\mathsf{y}}^{*}$) centered at $\ell^{*}$, with
$|Q^{\ast}_{s}|=t_{s}$ for each $s\in[S]$,

$t_{1}=2H+1,\quad t_{s+1}=3t_{s},\quad\text{and~{}}t_{S}=\Theta(\log n)$

(note that hence $S=O(\log\log n)$). Let
$\smash{{\mathsf{w}}_{s}^{*}={\mathsf{y}}^{*}_{Q^{*}_{s}}}$ for each
$s\in[S]$.

The Align algorithm consists of two stages. In this subsection we give some
intuition behind each stage and its analysis. In the intuitive discussion
below, we focus chiefly on understanding the probability that Align succeeds
at a particular location $\ell^{*}$; in the formal proof we need to apply the
bounded difference inequality of McDiarmid to argue that Align succeeds on all
but except $2^{-\Omega(H)}n$ many locations with high probability.

For the rest of this section, we say that an event is _most likely_ to happen
if it happens with probability $1-2^{-\Omega(H)}$.

##### First stage — locating a small neighborhood of
$\mathrm{source}^{\ast}(\ell^{\ast})$ in each trace ${\mathsf{y}}^{(m)}$.

In the first stage, Align works separately on each ${\mathsf{y}}^{(m)}$,
$m\in[M]$. It iteratively uses
${\mathsf{w}}^{*}_{S},\ldots,{\mathsf{w}}^{\ast}_{1}$ (as templates) to find a
sequence of nested intervals $Q^{m}_{S}\supset\cdots\supset Q^{m}_{1}$ of
locations of ${\mathsf{y}}^{(m)}$ such that

${d_{\mathrm{edit}}}\left({\mathsf{w}}^{*}_{s},{\mathsf{y}}^{(m)}_{Q^{m}_{s}}\right)\leq
2\gamma t_{s},\quad\text{for each $s=S,\ldots,1$.}$ (6)

This is done by first finding $Q^{m}_{S}\subset[|{\mathsf{y}}^{(m)}|]$ that
satisfies (6) and then repeatedly finding $Q^{m}_{s}\subset Q^{m}_{s+1}$ that
satisfies (6), for each $s=S-1,\ldots,1$. When multiple $Q^{m}_{s}$ satisfy
(6), we pick one arbitrarily; when no interval $Q^{m}_{s}$ exists for some $s$
and some $m$, Align fails and returns
$\smash{\ell^{(1)}=\cdots=\ell^{(M)}=1}$.

In the analysis we show that when
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$,
it is most likely that every $m\in[M]$ satisfies

$\left|\hskip
1.42271pt{\overline{\mathrm{source}^{*}(Q^{*}_{s})}}\bigtriangleup{\overline{\mathrm{source}^{(m)}(Q^{m}_{s})}}\hskip
1.42271pt\right|\leq 4\gamma t_{s},\quad\text{for each $s=S,\ldots,1$;}$ (7)

in words, this means that the interval $Q^{m}_{s}$ of
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ (almost) comes from the subword of
${\mathsf{x}}$ whose image is $Q_{s}^{*}$ in
$\text{\boldmath${\mathsf{y}}$}^{*}$. The proof proceeds by induction on
$s=S,\ldots,1$ (see Lemma 22). Assume that (7) holds for $s+1$:

$\left|\hskip
1.42271pt{\overline{\mathrm{source}^{*}(Q^{*}_{s+1})}}\bigtriangleup{\overline{\mathrm{source}^{(m)}(Q^{m}_{s+1})}}\hskip
1.42271pt\right|\leq 4\gamma t_{s+1}.$ (8)

Then most likely $I^{*}_{s}:=\overline{\mathrm{source}^{*}(Q^{*}_{s})}$ is
contained in $\overline{\mathrm{source}^{(m)}(Q^{m}_{s+1})}$ given (8) and
that $I^{*}_{s}$ is roughly the middle one-third of
$\smash{\overline{\mathrm{source}^{*}(Q^{*}_{s+1})}}$ (also recall that
$\gamma=0.01$ is a small constant). As a result,
$\mathrm{image}^{(m)}(I^{*}_{s})$ would most likely satisfy (6) as $Q^{m}_{s}$
(using that $\delta$ is sufficiently smaller than $\gamma$ and thus, the
number of bits deleted from $I^{*}_{s}$ in getting both
$\text{\boldmath${\mathsf{y}}$}^{*}$ and
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ is smaller than $\gamma t_{s}$). On the
other hand, let $Q^{m}_{s}$ be the interval actually picked by Align. To
finish the proof of (7), we show that when (8) is violated, since
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, the two subwords
$x_{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s})}}$ and
$x_{\overline{\mathrm{source}^{(m)}(Q^{m}_{s})}}$ most likely have large edit
distance (see Claim 10), which in turn implies that
$\text{\boldmath${\mathsf{y}}$}^{\ast}_{Q^{\ast}_{s}}$ (i.e., the string
${\mathsf{w}}^{*}_{s}$) has large edit distance from
$\text{\boldmath${\mathsf{y}}$}^{(m)}_{Q^{m}_{s}}$, which contradicts (6).

##### Second stage — determining a consensus location close to
$\mathrm{source}^{\ast}(\ell^{\ast})$.

In the second stage, Align uses subwords
$\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$, $m\in[M]$, to determine the final
locations $\ell^{(1)},\dots,\ell^{(M)}$. This is done by first identifying a
string ${\mathsf{w}}$ that (a) has length at least $0.9t_{1}$, and (b) appears
as a subword in at least $95\%$ of $\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$,
$m\in[M]$. (When multiple strings ${\mathsf{w}}$ satisfy the two conditions,
Align picks one arbitrarily; when no such ${\mathsf{w}}$ exists, Align fails
and sets $\ell^{(m)}=1$ for all $m\in[M]$.) Finally Align finds ${\mathsf{w}}$
in $\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$ and sets $\ell^{(m)}$ to be the
location of the first symbol of ${\mathsf{w}}$ in
$\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$, for each $m\in[M]$. (When
${\mathsf{w}}$ appears in $\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$ at multiple
locations, Align picks one of them arbitrarily as $\ell^{(m)}$; when
${\mathsf{w}}$ does not appear, Align sets $\ell^{(m)}=1$ by default.)

Using $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$,
we show that most likely $\ell^{(1)},\ldots,\ell^{(M)}$ satisfy the two
desired conditions in the definition of “success” (i.e. at least 95% of
$\mathrm{source}^{(m)}(\ell^{(m)})$, $m\in[M]$, agree on the same location
$i\in[n]$, and this consensus location $i$ satisfies (5)). To give some
intuition behind the analysis, we first assume that every $m\in[M]$ satisfies
(7) and in particular,

$\left|\hskip
1.42271pt{\overline{\mathrm{source}^{*}(Q^{*}_{1})}}\bigtriangleup{\overline{\mathrm{source}^{(m)}(Q^{m}_{1})}}\hskip
1.42271pt\right|\leq 4\gamma t_{1}.$ (9)

Since $|Q^{*}_{1}|=t_{1}$, most likely
$I_{1}^{*}:=\overline{\mathrm{source}^{*}(Q^{*}_{1})}$ has length close to
$t_{1}$. Let $I_{1}^{**}$ denote the interval obtained from $I_{1}^{*}$ by
extending it in both directions by $4\gamma t_{1}$ (so $I_{1}^{**}$ also has
length close to $t_{1}$ since $\gamma=0.01$). Using our choice of
$t_{1}=2H+1$, it follows from simple calculations that most likely at least
$95\%$ of $\text{\boldmath${\mathsf{y}}$}^{(m)}$, $m\in[M]$, are obtained from
${\mathsf{x}}$ with no deletions in $I_{1}^{**}$. Let $G\subseteq[M]$ be the
set of such $m\in[M]$. It follows from (9) that
$\smash{\text{\boldmath${\mathsf{y}}$}^{(m)}_{Q^{m}_{1}}}$ comes from
$\text{\boldmath${\mathsf{x}}$}_{I^{m}_{1}}$ with no deletions for some
interval $I^{m}_{1}$ such that $|I^{m}_{1}\bigtriangleup I^{*}_{1}|\leq
4\gamma t_{1}$, for each $m\in G$.

At this point it is clear that
${\mathsf{w}}=\text{\boldmath${\mathsf{x}}$}_{\cap_{m\in G}I^{m}_{1}}$ would
satisfy both conditions (a) and (b) (using $\gamma=0.01$). On the other hand,
if there is a string ${\mathsf{w}}$ that appears in at least $95\%$ of all
$x_{I^{m}_{1}}$, $m\in[M]$, then for at least $90\%$ of $m\in[M]$,
${\mathsf{w}}$ appears in
$\smash{\text{\boldmath${\mathsf{y}}$}^{(m)}_{Q^{m}_{1}}}$ and $m\in G$. Using
the randomness of $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, one can
argue that most likely no string of length at least $0.9t_{1}$ can appear as a
subword more than once in $\text{\boldmath${\mathsf{x}}$}_{I_{1}^{**}}$. This
implies that at least $90\%$ of $\ell^{(m)}$ returned are in consensus. To see
that the consensus location $i\in[n]$ satisfies (5), we recall $t_{1}=2H+1$
and observe that $\mathrm{source}^{*}(\ell^{*})$ appears around the middle of
$I_{1}^{**}$ but $i$ (as the unique location where ${\mathsf{w}}$ appears as a
subword in $\mathsf{x}_{I_{1}^{**}}$) lies close to its left end.

###  4.2 Algorithm Align

We now describe the algorithm Align which takes as input
$\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ with
$\ell^{*}\in[5\tau\log n:|{\mathsf{y}}^{*}|-5\tau\log n]$. (See Algorithm 2
for a formal presentation of the algorithm.)

Align starts by computing a sequence of nested subwords of ${\mathsf{y}}^{*}$
centered at $\ell^{*}$ as follows. Let $t_{1}=$ $2H+1$ (recall that $H\leq
2\log n$) and $t_{s}=3t_{s-1}$ for each $s\geq 1$, and let $S$ be the smallest
integer such that

$t_{S}\geq\tau\log n\quad\text{(and hence $t_{S}\leq 3\tau\log n$)}$

(recall that $\tau=500$). Given ${\mathsf{y}}^{*}$ and $\ell^{*}$, we define
the sequence of subwords
${\mathsf{w}}^{\ast}_{1},\ldots,{\mathsf{w}}^{\ast}_{S}$, where
${\mathsf{w}}^{\ast}_{s}$ is the $t_{s}$-bit subword
${\mathsf{y}}^{\ast}_{Q^{\ast}_{s}}$ with
$Q^{\ast}_{s}=[\ell^{*}-(t_{s}-1)/2:\ell^{*}+(t_{s}-1)/2]$ centered at
$\ell^{\ast}$ in ${\mathsf{y}}^{\ast}$. (Given that $t_{S}\leq 3\tau\log n$,
we always have $Q_{S}^{*}\subset[|{\mathsf{y}}^{*}|]$; indeed we have that
there are more than $t_{S}$ elements to the left and to the right of
$Q_{S}^{*}$ in $[|{\mathsf{y}}^{*}|]$, which is the reason why we only
consider $\ell^{*}$’s that are at least $5\tau\log n$ away from both ends of
${\mathsf{y}}^{*}$.)

Input: A location $\ell^{\ast}$ and a tuple of $M+1$ strings
${\mathsf{y}}^{\ast},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$

Output: $M$ locations $\ell^{(1)},\ldots,\ell^{(M)}$, where
$\ell^{(i)}\in[|{\mathsf{y}}^{(i)}|]$ is a location in ${\mathsf{y}}^{(i)}$

1

2Compute ${\mathsf{w}}^{\ast}_{1},\ldots,{\mathsf{w}}^{\ast}_{S}$ from
${\mathsf{y}}^{\ast}$ as defined in Section 4.2. Let
$Q_{S+1}^{m}=[|{\mathsf{y}}^{(m)}|]$ for each $m\in[M]$.

3

4for  _each $m\in[M]$_ do // First stage

5 for  _$s=S,\ldots,1$_ do

6 Find any subword ${\mathsf{y}}^{(m)}_{Q^{m}_{s}}$ in
$\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{s+1}}}$ (breaking ties arbitrarily) that
has edit distance at most $2\gamma t_{s}$ from ${\mathsf{w}}_{s}^{*}$; if such
a subword does not exist return $\ell^{(1)}=\cdots=\ell^{(M)}=1$.

7

8

9Find any string ${\mathsf{w}}$ of length at least $0.9t_{1}$ that appears as
a subword in at least $95\%$ of ${\mathsf{y}}^{(m)}_{{Q^{m}_{1}}}$, $m\in[M]$.
If no such ${\mathsf{w}}$ exists, return $\ell^{(1)}=\cdots=\ell^{(M)}=1$. //
Second stage

10 for  _each $m\in[M]$_ do

11 If ${\mathsf{y}}^{(m)}_{Q_{1}^{m}}$ has ${\mathsf{w}}$ as a subword, set
$\ell^{(m)}$ to be any location such that ${\mathsf{y}}^{(m)}_{Q_{1}^{m}}$ has
${\mathsf{w}}$ as a subword starting at $\ell^{(m)}$; otherwise
($\smash{{\mathsf{y}}^{(m)}_{Q_{1}^{m}}}$ does not contain ${\mathsf{w}}$ as a
subword), set $\ell^{(m)}=1.$

return $\ell^{(1)},\ldots,\ell^{(M)}$

Algorithm 2 Align Figure 2: The Align algorithm.

We divide the analysis of Align into two parts. In the first part (Section
4.3) we begin by describing some good events over the randomness of
$\mathbf{D}^{\ast}$, ${\mathsf{x}}$, and $\mathbf{D}^{(m)}$, $m\in[M]$, where
$\mathbf{D}^{\ast}$ and $\mathbf{D}^{(m)}$ are the sets of deleted locations
that gave rise to traces $\text{\boldmath${\mathsf{y}}$}^{\ast}$ and
$\text{\boldmath${\mathsf{y}}$}^{(m)}$ of ${\mathsf{x}}$, respectively. We
then show that these events happen with probability at least $1-1/n^{2}$. The
second part of our analysis (Section 4.4) will be entirely deterministic. We
show that Align succeeds on $\mathsf{x}$ with respect to
$({\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$ whenever
$D^{*},$ $\mathsf{x}$ and $D^{(m)}:m\in[M]$ satisfy all conditions described
in the first part (Section 4.3).

###  4.3 Probabilistic Analysis

Let $\mathcal{D}$ denote the distribution over subsets of $[n]$ where
$\mathbf{D}\sim\mathcal{D}$ is drawn by including each integer of $[n]$
independently with probability $\delta$. We prove Theorem 7 in two steps. In
this subsection we describe an event over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\mathbf{D}^{*},\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}\sim\mathcal{D}$ (as
deletions used to obtain
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
from ${\mathsf{x}}$) and show that it happens with probability at least
$1-1/n^{2}$ (see Corollary 20). In Section 4.4, we show that whenever the
event occurs, Align succeeds on ${\mathsf{x}}$ with respect to
$(\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)})$.

We describe the event by imposing conditions on random variables in the
following order: first $\mathbf{D}^{\ast}\sim\mathcal{D}$, then
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and finally
$\mathbf{D}^{(m)}\sim\mathcal{D}$, $m\in[M]$. We describe conditions on each
random variable conditioning on the event that previous ones have already met
conditions imposed on them.

We start with some preliminary claims.

######  Claim 8.

Let $t$ be a positive integer and let $1\leq i_{1}<\cdots<i_{t}\leq n$ and
$1\leq j_{1}<\cdots<j_{t}\leq n$ with $i_{k}\neq j_{k}$ for all $k\in[t]$. For
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, we have $\operatorname{{\bf
Pr}}[\text{\boldmath${\mathsf{x}}$}_{i_{k}}=\text{\boldmath${\mathsf{x}}$}_{j_{k}}$
for all $k\in[t]]=2^{-t}.$

###### Proof.

The proof is by induction on $t$. The base case when $t=1$ is trivial. For the
inductive step, we assume that the statement holds for $t-1$. Using the
induction hypothesis we have

$\displaystyle\operatorname{{\bf
Pr}}\bigl{[}\text{\boldmath${\mathsf{x}}$}_{i_{k}}=\text{\boldmath${\mathsf{x}}$}_{j_{k}}\text{
for all $k\in[t]$}\bigr{]}$ $\displaystyle=\operatorname{{\bf
Pr}}\bigl{[}\text{\boldmath${\mathsf{x}}$}_{i_{t}}=\text{\boldmath${\mathsf{x}}$}_{j_{t}}\bigm{|}\text{\boldmath${\mathsf{x}}$}_{i_{k}}=\text{\boldmath${\mathsf{x}}$}_{j_{k}}\text{
for all $k\in[t-1]$}\bigr{]}\cdot 2^{-(t-1)}.$

Without loss of generality we assume that $i_{t}<j_{t}$. Note that
$\text{\boldmath${\mathsf{x}}$}_{j_{t}}$ is still uniform when conditioned on
values of $\text{\boldmath${\mathsf{x}}$}_{i_{k}}:k\leq t$ and
$\text{\boldmath${\mathsf{x}}$}_{j_{k}}:k<t$. Therefore the conditional
probability on the right hand side is $1/2$. This finishes the induction step
and the proof of the claim. ∎

Claim 8 has the following corollary which we will use later:

######  Corollary 9.

Let $t$ be a positive integer, and let $I\neq I^{\prime}\subseteq[n]$ be two
distinct (but not necessarily disjoint) intervals of length $t$. For
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, we have $\operatorname{{\bf
Pr}}[\text{\boldmath${\mathsf{x}}$}_{I}=\text{\boldmath${\mathsf{x}}$}_{I^{\prime}}]=2^{-t}.$

Claim 8 lets us bound the edit distance between subwords of a random string as
follows:

######  Claim 10.

Let $t$ be a positive integer. Let $I,I^{\prime}\subseteq[n]$ be two intervals
that satisfy (1) $|I|\geq 25t$ and (2) $|I\bigtriangleup I^{\prime}|\geq t$.
Then we have
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I},\text{\boldmath${\mathsf{x}}$}_{I^{\prime}})<t$
with probability at most $2^{-5t}$ when
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$.

###### Proof.

Having
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I},\text{\boldmath${\mathsf{x}}$}_{I^{\prime}})<t$
implies that there exist $J\subseteq I$ and $J^{\prime}\subseteq I^{\prime}$
such that $|J|+|J^{\prime}|<t$, $|I\setminus J|=|I^{\prime}\setminus
J^{\prime}|$ and $\text{\boldmath${\mathsf{x}}$}_{I\setminus
J}=\text{\boldmath${\mathsf{x}}$}_{I^{\prime}\setminus J^{\prime}}$. Fixing
such a pair $(J,J^{\prime})$ and writing $I\setminus J$ as
$i_{1}<i_{2}<\cdots$ and $I^{\prime}\setminus J^{\prime}$ as
$j_{1}<j_{2}<\cdots$, we claim that $i_{k}\neq j_{k}$ for all $k$. To see this
we note that having $i_{k}=j_{k}$ for some $k$ implies that we need to delete
at least $|I\bigtriangleup I^{\prime}|\geq t$ bits from $I$ and $I^{\prime}$
even just to match the lengths of $I$ to the left and to the right of $k$ with
those of $I^{\prime}$, a contradiction with $|J|+|J^{\prime}|<t$.

Therefore, it follows from Claim 8 that
$\text{\boldmath${\mathsf{x}}$}_{I\setminus
J}=\text{\boldmath${\mathsf{x}}$}_{I^{\prime}\setminus J^{\prime}}$ with
probability at most $2^{-(|I|+|I^{\prime}|-t)/2}.$ It follows by a union bound
on all pairs $(J,J^{\prime})$ that
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I},\text{\boldmath${\mathsf{x}}$}_{I^{\prime}})<t$
with probability at most

$2^{-(|I|+|I^{\prime}|-t)/2}\cdot\sum_{k\leq t}{|I|\choose k}\cdot\sum_{k\leq
t}{|I^{\prime}|\choose k}\leq 2^{-(|I|+|I^{\prime}|-t)/2}\cdot
2^{H(0.04)(|I|+|I^{\prime}|)}<2^{-5t}.$

This finishes the proof of the claim. ∎

####  4.3.1 Conditions on $\mathbf{D}^{\ast}\sim\mathcal{D}$

We start with conditions on $\mathbf{D}^{\ast}\sim\mathcal{D}$, i.e., the
locations of bits deleted in $\text{\boldmath${\mathsf{y}}$}^{*}$. Given an
outcome $D^{\ast}\subseteq[n]$ of $\mathbf{D}^{\ast}$, we write $L^{*}$ to
denote the interval

$L^{*}:=[5\tau\log n:n-|D^{*}|-5\tau\log n].$

For each $\ell^{*}\in L^{*}$ and $s\in[S]$ we write $Q^{*}_{s,\ell^{*}}$ to
denote the interval of length $t_{s}$ that is centered at $\ell^{*}$. Let
$L_{1}^{*}$ denote the set of $\ell^{*}\in L^{*}$ such that

$\left|{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s,\ell^{*}})}}\right|\leq(1+\gamma)t_{s},\quad\text{for
all $s\in[S]$.}$

######  Claim 11.

With probability at least $1-\exp(-n^{0.1})$ over $\mathbf{D}^{\ast}$, we have
$|\boldsymbol{L}^{*}\setminus\boldsymbol{L}^{*}_{1}|\leq 2^{-0.2H}n$.

###### Proof.

Given $D^{*}$, for each $\ell^{*}\in L^{*}\setminus L_{1}^{*}$ there is an
$s\in[S]$ such that
$|{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s,\ell^{*}})}}|\geq(1+\gamma)t_{s}$.
We can get from it an interval $I$ with $|I|=(1+\gamma)t_{s}$ and
$|\mathrm{image}^{*}(I)|\leq|Q_{s,\ell^{*}}^{*}|=t_{s}$ by deleting elements
from the right end of
$\smash{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s,\ell^{*}})}}$. We note
that the intervals $I$ obtained from different $\ell^{*}\in L^{*}\setminus
L_{1}^{*}$ are different. (To obtain the same interval, we must use the same
$s\in[S]$ because of the length of $I$; on the other hand, sharing the same
left end and the same $s$ implies that the $\ell^{*}$ is the same as well.)
Therefore, $|L^{*}\setminus L_{1}^{*}|$ is at most the number of intervals
$I\subseteq[n]$ such that $|I|=(1+\gamma)t_{s}$ for some $s\in[S]$ and
$|\mathrm{image}^{*}(I)|\leq t_{s}$. Below we upperbound the latter when
$\mathbf{D}^{*}\sim\mathcal{D}$.

We apply the McDiarmid inequality (Theorem 6). We draw $\mathbf{D}^{*}$ by
drawing $n$ independent random indicator variables
$\mathbf{X}_{1},\ldots,\mathbf{X}_{n}$ with $\mathbf{X}_{k}=1$ with
probability $\delta$ (so $k\in\mathbf{D}^{*}$ if $\mathbf{X}_{k}=1$). We use
$f(\mathbf{X}_{1},\ldots,\mathbf{X}_{n})$ to denote the number of
$I\subseteq[n]$ such that $|I|=(1+\gamma)|t_{s}|$ for some $s\in[S]$ and
$|\mathrm{image}^{*}(I)|\leq t_{s}$. On the one hand, the probability of an
interval $I$ with $|I|=(1+\gamma)t_{s}$ satisfying
$|\mathrm{image}^{*}(I)|\leq t_{s}$ is at most $2^{|I|}\cdot\delta^{\gamma
t_{s}}\leq\delta^{\gamma t_{s}/2}$, by using $\delta\leq 1/K$ and making $K$
sufficiently large. As a result,

$\mathbf{E}\big{[}f\big{]}\leq n\left(\sum_{s=1}^{S}\delta^{\gamma
t_{s}/2}\right)=\delta^{\Omega(t_{1})}n=\delta^{\Omega(H)}n.$

On the other hand, flipping one variable $\mathbf{X}_{k}$ can change $f$ by no
more than $O(t_{S})=O(\log n)$. Thus it follows from the McDiarmid inequality
that

$f(\mathbf{X}_{1},\ldots,\mathbf{X}_{n})\leq\delta^{\Omega(H)}n+\tilde{O}(n^{0.55})\leq
2^{-0.2H}n,$

with probability at least $1-\exp(-n^{0.1})$, where we used that $\delta$ is
sufficiently small and $H\leq 2\log n$ in the last inequality. This finishes
the proof of the claim. ∎

####  4.3.2 Conditions on $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$

We fix a $D^{*}\subseteq[n]$ that satisfies Claim 11 when describing the
conditions for ${\mathsf{x}}$ and $\mathbf{D}^{(m)}$ below. As $D^{*}$ is
fixed, $L^{*},L^{*}_{1}$ and
$\smash{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s,\ell^{*}})}}$ for each
$\ell^{*}\in L_{1}^{*}$ are all fixed and are no longer random variables. For
each $\ell^{\ast}\in L^{\ast}_{1}$, for brevity we write
$I^{\ast}_{s,\ell^{\ast}}$ to denote
$\smash{\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s,\ell^{*}})}}$, and we
observe that for each $\ell^{*}\in L^{*}_{1}$ we have

$t_{s}\leq|I^{*}_{s,\ell^{*}}|\leq(1+\gamma)t_{s}.$ (10)

The conditions for $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ are given
in the next three claims.

######  Claim 12.

With probability at least $1-1/n^{3}$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, every $\ell^{*}\in
L_{1}^{*}$ and every interval $I\subseteq[n]$ with $|I\bigtriangleup
I_{S,\ell^{*}}^{*}|\geq 4\gamma t_{S}$ satisfy
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I^{*}_{S,\ell^{*}}},\text{\boldmath${\mathsf{x}}$}_{I})\geq
4\gamma t_{S}$.

###### Proof.

Recall that $|I^{*}_{S,\ell^{*}}|\geq t_{S}$ and $\gamma=0.01$. Fix an
$\ell^{*}\in L_{1}^{*}$ and an interval $I$ with $|I\bigtriangleup
I^{*}_{S,\ell^{*}}|\geq 4\gamma t_{S}$. By Claim 10 we have that
$\smash{{d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I^{*}_{S,\ell^{*}}},\text{\boldmath${\mathsf{x}}$}_{I})<4\gamma
t_{S}}$ occurs with probability at most $\smash{2^{-20\gamma t_{S}}\leq
1/n^{100}}$, using $\smash{t_{S}\geq\tau\log n}$ and $\gamma\tau=5$. The claim
follows by a union bound over no more than $\smash{n^{3}}$ pairs of
$\smash{\ell^{*}}$ and $I$. ∎

For the next claim we need the following notation. Given $\ell^{*}\in L^{*}$
and $s\in[S]$, we let $N(I^{*}_{s,\ell^{*}})$ denote the interval obtained by
adding $t_{s}$ elements to both ends of $I^{*}_{s,\ell^{*}}$ (so
$N(I^{*}_{s,\ell^{*}})$ has length $|I^{*}_{s,\ell^{*}}|+2t_{s}$). Note that
$N(I^{*}_{s,\ell^{*}})$ is an interval contained in $[n]$ given that
$\ell^{*}\in L^{*}$ is at least $5\tau\log n$ from both ends of $[n-|D^{*}|]$
(recall that $t_{s}\leq t_{S}\leq 3\tau\log n$).

######  Claim 13.

With probability at least $1-\exp(-n^{0.1})$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, all but at most
$2^{-0.2H}n$ many locations $\ell^{*}\in L^{*}_{1}$ satisfy the following
condition: For any $s\in[2:S]$ and any interval $I\subseteq
N(I^{*}_{s,\ell^{*}})$ such that $|I\bigtriangleup I^{*}_{s-1,\ell^{*}}|\geq
4\gamma t_{s-1}$, we have
${d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I},\text{\boldmath${\mathsf{x}}$}_{I^{*}_{s-1,\ell^{*}}})\geq
4\gamma t_{s-1}.$

###### Proof.

Again we use the McDiarmid inequality. Let
$f(\text{\boldmath${\mathsf{x}}$}_{1},\ldots,\text{\boldmath${\mathsf{x}}$}_{n})$
denote the number of $\ell^{*}\in L^{*}_{1}$ that violates the condition. We
first upperbound the probability over
$\text{\boldmath${\mathsf{x}}$}_{1},\dots,\text{\boldmath${\mathsf{x}}$}_{n}$
of a fixed $\ell^{*}\in L_{1}^{*}$ violating the condition.

For each $s\in[2:S]$ and each interval $I\subseteq N(I^{*}_{s,\ell^{*}})$ with
$|I\bigtriangleup I_{s-1,\ell^{*}}^{*}|\geq 4\gamma t_{s-1}$ (note that
$\smash{I^{*}_{s-1,\ell^{*}}}$ has length at least $t_{s-1}$), by Claim 10 the
probability of
$\smash{{d_{\mathrm{edit}}}(\text{\boldmath${\mathsf{x}}$}_{I},\text{\boldmath${\mathsf{x}}$}_{I^{*}_{s-1,\ell^{*}}})<4\gamma
t_{s-1}}$ is at most $\smash{2^{-20\gamma t_{s-1}}}$. As

$\left|N(I^{*}_{s,\ell^{*}})\right|\leq|I^{*}_{s,\ell^{*}}|+2t_{s}\leq(3+\gamma)t_{s},$

by (10), it follows from a union bound that each $\ell^{*}$ in $L^{*}_{1}$
violates the condition with probability at most

$\sum_{s\in[2:S]}O(t_{s}^{2})\cdot 2^{-20\gamma
t_{s-1}}\leq\sum_{s\in[2:S]}2^{-19\gamma t_{s-1}}\leq 2^{-18\gamma t_{1}}\leq
2^{-0.3H},$

using $t_{1}=2H+1$ and $H$ is sufficiently large, and hence
$\operatorname{{\bf E}}[f]\leq 2^{-0.3H}n$. Given that each variable
$\text{\boldmath${\mathsf{x}}$}_{i}$ can change $f$ by no more than $O(\log
n)$, the lemma follows from arguments similar to the proof of Claim 11. ∎

######  Claim 14.

With probability at least $1-\exp(-n^{0.1})$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, all but at most
$2^{-0.2H}n$ many $\ell^{*}\in L^{*}_{1}$ are such that no two subwords of
$\text{\boldmath${\mathsf{x}}$}_{N(I^{*}_{1,\ell^{*}})}$ of length $H$ are the
same.

###### Proof.

The probability of an $\ell^{*}\in L_{1}^{*}$ violating the above condition is
at most $O(t_{1}^{2})\cdot 2^{-H}\leq 2^{-0.5H}$ by Corollary 9. The proof
follows from a similar application of McDiarmid inequality. ∎

####  4.3.3 Conditions on
$\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}\sim\mathcal{D}$

We fix an outcome $D^{*}$ that satisfies Claim 11 and a string
$\mathsf{x}\in\\{0,1\\}^{n}$ that satisfies Claim 12, Claim 13, and Claim 14.

We now describe some useful conditions on
$\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}$. We start with two conditions for
every $\mathbf{D}^{(m)}$.

######  Claim 15.

With probability at least $1-1/n^{3}$ over $\mathbf{D}\sim\mathcal{D}$, every
interval $I\subseteq[n]$ of length at most $(1+3\gamma)t_{S}$ satisfies that
$|\mathrm{image}(I)|\geq|I|-\gamma t_{S}$.

###### Proof.

For each $I\subseteq[n]$ of length at most $(1+3\gamma)t_{S}$, we have
$|\mathrm{image}(I)|<|I|-\gamma t_{S}$ with probability at most
$2^{|I|}\cdot\delta^{\gamma t_{S}}\leq\delta^{\gamma t_{S}/2}$, where the
inequality uses that $\delta$ is sufficiently small. Using $t_{S}\geq\tau\log
n$ we have that $\delta^{\gamma t_{S}/2}\leq\delta^{5\log n/2}\leq 1/n^{5}$
(as $\delta$ is sufficiently small). The claim then follows from a union
bound. ∎

######  Remark 16.

We note that the event described in Claim 15 implies that any interval
$Q\subseteq[n-|\mathbf{D}|]$ with length at most $(1+2\gamma)t_{S}$ must
satisfy $|\overline{\mathrm{source}(Q)}|\leq|Q|+\gamma t_{S}$. To see this,
let $I=\overline{\mathrm{source}(Q)}$ and assume for a contradiction that
$|I|>|Q|+\gamma t_{S}$. If $|I|\leq(1+3\gamma)t_{S}$ then $I$ violates the
event of Claim 15; if $|I|>(1+3\gamma)t_{S}$ then we can delete bits of $I$
from the beginning to obtain an interval $I^{\prime}$ with
$|I^{\prime}|=(1+3\gamma)t_{S}$, which satisfies
$|\mathrm{image}(I^{\prime})|<|\mathrm{image}(I)|\leq(1+2\gamma)t_{S}$ and
thus, $I^{\prime}$ violates the condition of Claim 15.

Let $L_{2}^{*}$ be the set of all $\ell^{*}\in L^{*}_{1}$ that satisfy the
conditions in Claim 13 and Claim 14.

######  Claim 17.

With probability at least $1-\exp(-n^{0.1})$ over $\mathbf{D}\sim\mathcal{D}$,
all but at most $2^{-0.2H}n$ many $\ell^{*}\in L^{*}_{2}$ satisfy the
following condition: For every $s\in[2:S]$ and every interval $I\subseteq
N(I^{*}_{s,\ell^{*}})$ of length at most $(1+3\gamma)t_{s-1}$, we have
$|\mathrm{image}(I)|\geq|I|-\gamma t_{s-1}$.

###### Proof.

We upper bound the probability of an $\ell^{*}\in L_{2}^{*}$ violating the
condition above, and then apply the McDiarmid inequality. Fixing an
$\ell^{*}\in L^{*}_{2}$, a value of $s\in[2:S]$, and any interval $I\subseteq
N(I^{*}_{s,\ell^{*}})$ of length at most $(1+3\gamma)t_{s-1}$, $I$ violates
the condition with probability $\smash{2^{|I|}\cdot\delta^{\gamma
t_{s-1}}\leq\delta^{\gamma t_{s-1}/2}}$. By a union bound (over all
possibilities for $s$ and $I$), the probability of $\ell^{*}$ violating the
condition is at most

$\sum_{s\in[2:S]}O(t_{s}^{2})\cdot\delta^{\gamma t_{s-1}/2},$

and hence the expected number of $\ell^{\ast}\in L^{\ast}_{2}$ that violate
the condition is at most $n$ times this, which is at most $2^{-0.3H}n$ using
that $t_{s-1}\geq t_{1}=2H+1$ and $\delta$ is sufficiently small. Finally,
given that the outcome of each independent event (of whether an element in
$[n]$ is included in $\mathbf{D}$ or not) can change the number of
$\ell^{\ast}$ that satisfy the condition by at most $O(\log n)$, the lemma
follows from arguments similar to the proof of Claim 11. ∎

######  Remark 18.

Remark 16 applies similarly: Whenever the condition holds for $\ell^{*}\in
L_{2}^{*}$, any interval $Q\subseteq\mathrm{image}(N(I^{*}_{s,\ell^{*}}))$ for
any $s$ with length at most $(1+2\gamma)t_{s-1}$ satisfies
$|\overline{\mathrm{source}(Q)}|\leq|Q|+\gamma t_{s-1}$.

The last condition considers $\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}$
together:

######  Claim 19.

With probability at least $1-\exp(-n^{0.1})$ over
$\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}\sim\mathcal{D}$, all but at most
$2^{-0.2H}n$ many $\ell^{*}\in L^{*}_{2}$ satisfy the following condition: At
least $95\%$ of $m\in[M]$ satisfy

$N(I^{*}_{1,\ell^{*}})\cap\mathbf{D}^{(m)}=\varnothing,$

i.e., no bit of the subword
$\text{\boldmath${\mathsf{x}}$}_{N(I^{*}_{1,\ell^{*}})}$ of ${\mathsf{x}}$ is
deleted in at least $95\%$ of the traces
$\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}$.

###### Proof.

Consider drawing $\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}$ by drawing $nM$
independent indicator random variables $\smash{\mathbf{X}_{k}^{(m)}}$,
$k\in[n]$ and $m\in[M]$, with $\smash{k\in\mathbf{D}^{(m)}}$ if
$\smash{\mathbf{X}_{k}^{(m)}=1}$. We write $f$ to denote the number of
$\ell^{*}\in L^{*}_{2}$ such that at least $5\%$ of $m\in[M]$ have
$\smash{N(I^{*}_{1,\ell^{*}})\cap\mathbf{D}^{(m)}\neq\varnothing}$. On the one
hand, fixing an outcome of $\ell^{*}$, the probability of
$\smash{N(I^{*}_{1,\ell^{*}})\cap\mathbf{D}^{(m)}=\varnothing}$ is at most
$7\delta H$ given that $\smash{|N(I^{*}_{1,\ell^{*}})|\leq(3+\gamma)t_{1}\leq
7H}$, and hence the probability of $\ell^{*}$ being one of the locations
counted in $f$ is at most $2^{M}\cdot(7\delta H)^{0.05M}$. Recalling the
constraint Equation 3 on $H$, we have that

$\delta H=\frac{1}{K}\cdot\delta M\log\left(\frac{1}{\delta
M}\right)\leq\frac{\sqrt{\delta M}}{K}$ (11)

where the inequality holds given that $\delta M$ is sufficiently small
(observe from Equation 2 that $\delta M\leq 1/K$). Hence the probability is at
most

$2^{M}\cdot(7\delta H)^{0.05M}\leq(\delta M)^{0.025M}\leq 2^{-0.3H}$

where the first inequality is by Equation 11 and the second uses Equation 3
and the fact that $K$ is sufficiently large. Recalling that $H=O(\log n)$, the
claim follows from the McDiarmid inequality using similar arguments to those
given above and the fact that changing the outcome of any one of the $nM$
independent indicator random variables can only change $f$ by at most $O(H)$.
∎

####  4.3.4 Conclusion of Probabilistic Analysis

We summarize our probabilistic analysis with the following corollary, which
combines all the claims from this subsection.

######  Corollary 20.

With probability at least $1-1/n^{2}$ over the randomness of
$\mathbf{D}^{*},\text{\boldmath${\mathsf{x}}$},\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}$,
all of the following hold:

  1. 1.

$\mathbf{D}^{*}$ satisfies Claim 11;

  2. 2.

${\mathsf{x}}$ satisfies Claim 12, Claim 13 and Claim 14;

  3. 3.

Every $\mathbf{D}^{(m)}$, $m\in[M]$, satisfies Claim 15 and Claim 17, and

  4. 4.

$\mathbf{D}^{(1)},\ldots,\mathbf{D}^{(M)}$ together satisfy Claim 19.

###  4.4 Deterministic Analysis

The rest of Section 4 is dedicated to proving the following lemma, which
finishes the proof of Theorem 7 (and hence Theorem 4):

######  Lemma 21.

Align succeeds on $\mathsf{x}$ with respect to
${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ when they
satisfy Corollary 20.

Assume that $\mathsf{x},D^{*},D^{(1)},\ldots,D^{(M)}$ satisfy all conditions
of Corollary 20. Then we have that all but at most $O(M2^{-0.2H}n)\leq
2^{-0.1H}n$ (where the $M$ comes from a union bound in item (vi) and the
inequality follows from $H>M/K\geq\sqrt{M}$ using Equation 3 and $M\geq K^{2}$
from Equation 2 and thus, $2^{0.1H}$ is enough to cover $O(M)$ when $M$ is
sufficient large) many $\ell^{*}\in L^{*}$ satisfy the following list of
conditions (below we use $I^{*}_{s}$ to denote $I^{*}_{s,\ell^{*}}$ for
convenience given that $\ell^{*}$ is fixed in the rest of the proof):

  1. (i)

$|I^{*}_{s}|<(1+\gamma)t_{s}$ for every $s\in[S]$ (Claim 11);

  2. (ii)

Every interval $I\subseteq[n]$ with $|I\bigtriangleup I^{*}_{S}|\geq 4\gamma
t_{S}$, has ${d_{\mathrm{edit}}}(\mathsf{x}_{I},\mathsf{x}_{I^{*}_{S}})\geq
4\gamma t_{S}$ (Claim 12);

  3. (iii)

For all $s\in[2:S]$ and intervals $I\subseteq N(I^{*}_{s})$ with
$|I\bigtriangleup I^{*}_{s-1}|\geq 4\gamma t_{s-1}$, it holds that
${d_{\mathrm{edit}}}(\mathsf{x}_{I},\mathsf{x}_{I^{*}_{s-1}})\geq 4\gamma
t_{s-1}$ (Claim 13);

  4. (iv)

No two subwords of $\mathsf{x}_{N(I^{*}_{1})}$ of length $H$ are the same
(Claim 14);

  5. (v)

(Claim 15 and Remark 16) For all $m\in[M]$,
$|\mathrm{image}^{(m)}(I_{S}^{*})|\geq|I_{S}^{*}|-\gamma t_{S}$ and every
interval $Q^{m}\subseteq[|{\mathsf{y}}^{(m)}|]$ of length at most
$(1+2\gamma)t_{S}$ satisfies

$\left|\overline{\mathrm{source}^{(m)}(Q^{m})}\right|\leq|Q^{m}|+\gamma
t_{S};$

  6. (vi)

(Claim 17 and Remark 18) For all $m\in[M]$ and $s\in[2:S]$,
$|\mathrm{image}^{(m)}(I_{s-1}^{*})|\geq|I_{s-1}^{*}|-\gamma t_{s-1}$ and
every interval $Q^{m}\subseteq\mathrm{image}(N(I^{*}_{s}))$ of length at most
$(1+2\gamma)t_{s-1}$ satisfies

$\left|\overline{\mathrm{source}^{(m)}(Q^{m})}\right|\leq|Q^{m}|+\gamma
t_{s-1};$

  7. (vii)

At least $95\%$ of $m\in[M]$ satisfy that $N(I_{1}^{*})\cap
D^{(m)}=\varnothing$ (Claim 19).

####  4.4.1 First stage: Locating a small neighborhood of
$\mathrm{source}^{\ast}(\ell^{\ast})$ in each trace ${\mathsf{y}}^{(m)}$

$\text{\boldmath${\mathsf{y}}$}^{\ast}$${\mathsf{x}}$$\text{\boldmath${\mathsf{y}}$}^{(m)}$$Q^{\ast}_{s-1}$$Q^{\ast}_{s}$$I^{\ast}_{s}=\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s})}$$\overline{\mathrm{source}^{(m)}(Q^{m}_{s})}$$N(I^{\ast}_{s})$$Q^{m}_{s}$$\mathrm{image}^{(m)}(N(I^{\ast}_{s}))$
Figure 3: First stage of Align: The 3 red lines are the subwords
${\mathsf{y}}^{\ast}_{Q^{\ast}_{s-1}}$,
$\mathsf{x}_{I^{\ast}_{s-1}=\overline{\mathrm{source}^{\ast}(Q^{\ast}_{s-1})}}$,
and ${\mathsf{y}}^{(m)}_{Q^{m}=\mathrm{image}^{(m)}(I^{\ast}_{s-1})}$. The
blue lines are the subwords
$\mathsf{x}_{\overline{\mathrm{source}^{(m)}(Q^{m}_{s-1})}}$, and
${\mathsf{y}}^{(m)}_{Q^{m}_{s-1}}$ found by Align. In the completeness
argument, we have $Q^{m}=\mathrm{image}^{(m)}(I^{\ast}_{s-1})\subseteq
Q^{m}_{s}$ because $I^{\ast}_{s-1}\subseteq I^{\ast}_{s}$ and
$\lvert\overline{\mathrm{source}^{(m)}(Q^{m}_{s})}\bigtriangleup
I^{\ast}_{s}\rvert$ is small. In the soundness argument, as
$Q^{m}_{s-1}\subseteq Q^{m}_{s}$ and
$\lvert\overline{\mathrm{source}^{(m)}(Q^{m}_{s})}\bigtriangleup
I^{\ast}_{s}\rvert$ is small, we have
$I:=\mathrm{source}^{(m)}(Q^{m}_{s-1})\subseteq N(I^{\ast}_{s})$, which
implies $Q^{m}_{s-1}\subseteq\mathrm{image}^{(m)}(N(I^{\ast}_{s}))$.

We prove the following lemma for the first stage of $\textup{{\tt
Align}}(\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$
(algorithms 2, 2 and 2):

######  Lemma 22.

For every $m\in[M]$, the final interval $Q^{m}_{1}$ found by Align in the
first stage satisfies

$\left|\overline{\mathrm{source}^{(m)}(Q_{1}^{m})}\bigtriangleup
I_{1}^{*}\right|\leq 4\gamma t_{1}.$ (12)

###### Proof.

We prove by induction on $s=S,\ldots,1$ that

$\left|\overline{\mathrm{source}^{(m)}(Q_{s}^{m})}\bigtriangleup
I^{*}_{s}\right|\leq 4\gamma t_{s}.$ (13)

We start with the base case $s=S$. First we establish completeness by showing
that there is an interval $Q^{m}\subset[|{\mathsf{y}}^{(m)}|]$ such that
$\smash{{d_{\mathrm{edit}}}({\mathsf{w}}_{S}^{*},{\mathsf{y}}^{(m)}_{Q^{m}})\leq
2\gamma t_{S}}$. To this end, let $Q^{m}=\mathrm{image}^{(m)}(I^{*}_{S})$, and
observe that this is an interval in $[|{\mathsf{y}}^{(m)}|]$. We have

${d_{\mathrm{edit}}}({\mathsf{w}}_{S}^{*},{\mathsf{y}}^{(m)}_{Q^{m}})\leq{d_{\mathrm{edit}}}({\mathsf{w}}_{S}^{*},\mathsf{x}_{I^{*}_{S}})+{d_{\mathrm{edit}}}({\mathsf{y}}^{(m)}_{Q^{m}},\mathsf{x}_{I_{S}^{*}})<2\gamma
t_{S},$

where we used (i) $|I_{S}^{*}|<(1+\gamma)t_{S}$ to upper bound the first edit
distance by $\gamma t_{S}$, and (v) $|Q^{m}|\geq|I_{S}^{*}|-\gamma t_{S}$ to
upper bound the second edit distance by $\gamma t_{S}$. Next we establish
soundness by showing that any interval $Q_{S}^{m}$ picked by Align satisfies
(13). Let $\smash{I=\overline{\mathrm{source}^{(m)}(Q_{S}^{m})}}$. Then we
have

${d_{\mathrm{edit}}}(\mathsf{x}_{I},\mathsf{x}_{I_{S}^{*}})\leq{d_{\mathrm{edit}}}(\mathsf{x}_{I},{\mathsf{y}}^{(m)}_{Q_{S}^{m}})+{d_{\mathrm{edit}}}({\mathsf{y}}^{(m)}_{Q_{S}^{m}},{\mathsf{w}}_{S}^{*})+{d_{\mathrm{edit}}}({\mathsf{w}}_{S}^{*},\mathsf{x}_{I_{S}^{*}})<\gamma
t_{S}+2\gamma t_{S}+\gamma t_{S}=4\gamma t_{S}.$ (14)

To see that
$\smash{{d_{\mathrm{edit}}}(\mathsf{x}_{I},{\mathsf{y}}^{(m)}_{Q_{S}^{m}})\leq\gamma
t_{S}}$ we first notice that $|Q_{S}^{m}|\leq(1+2\gamma)t_{S}$ because
$\smash{{d_{\mathrm{edit}}}({\mathsf{y}}^{(m)}_{Q_{S}^{m}},{\mathsf{w}}_{S}^{*})\leq
2\gamma t_{S}}$. It then follows from item (v) that
$\smash{|I|\leq|Q_{S}^{m}|+\gamma t_{S}}$, which gives
$\smash{{d_{\mathrm{edit}}}(\mathsf{x}_{I},{\mathsf{y}}^{(m)}_{Q_{S}^{m}})\leq\gamma
t_{S}}$. For the last summand, as in the completeness argument (i) gives that
$|I_{S}^{*}|<(1+\gamma)t_{S}$ and hence
${d_{\mathrm{edit}}}({\mathsf{w}}_{S}^{*},\mathsf{x}_{I^{*}_{S}})\leq\gamma
t_{S}$. The soundness part then follows from (14) and (ii).

With the base case in hand, assume for the inductive step that (13) holds for
some $s\in[2:S]$. We use this to prove it for $s-1$.

The completeness proof is similar to the base case: let
$Q^{m}=\mathrm{image}^{(m)}(I_{s-1}^{*})$. It follows from (13) on $s$ that
$Q^{m}\subseteq Q_{s}^{m}$. Then

${d_{\mathrm{edit}}}({\mathsf{w}}_{s-1}^{*},{\mathsf{y}}^{(m)}_{Q^{m}})\leq{d_{\mathrm{edit}}}({\mathsf{w}}_{s-1}^{*},\mathsf{x}_{I_{s-1}^{*}})+{d_{\mathrm{edit}}}({\mathsf{y}}^{(m)}_{Q^{m}},\mathsf{x}_{I_{s-1}^{*}})\leq
2\gamma t_{s-1},$

where we used (i) and (vi).

The soundness argument is also similar to the base case. Let $Q_{s-1}^{m}$ be
the interval found by Align and let
$I=\smash{\overline{\mathrm{source}^{(m)}(Q_{s-1}^{m})}}$. Then
$Q_{s-1}^{m}\subseteq Q_{s}^{m}$ and it follows from (13) (and the definition
of $N(\cdot)$) that

$I=\overline{\mathrm{source}^{(m)}(Q_{s-1}^{m})}\subseteq\overline{\mathrm{source}^{(m)}(Q_{s}^{m})}\subseteq
N(I_{s}^{*})$

and thus, $Q_{s-1}^{m}\subseteq\mathrm{image}(N(I_{s}^{*}))$. We also have
$|Q_{s-1}^{m}|\leq(1+2\gamma)t_{s-1}$ given that $y^{(m)}_{Q_{s-1}^{m}}$ has
edit distance at most $2\gamma t_{s-1}$ from ${\mathsf{w}}_{s-1}^{*}$ (which
is of length $t_{s-1}$). As a result, analogous to (14), we have

${d_{\mathrm{edit}}}(\mathsf{x}_{I},\mathsf{x}_{I_{s-1}^{*}})\leq{d_{\mathrm{edit}}}(\mathsf{x}_{I},{\mathsf{y}}^{(m)}_{Q_{s-1}^{m}})+{d_{\mathrm{edit}}}({\mathsf{y}}^{(m)}_{Q_{s-1}^{m}},{\mathsf{w}}_{s-1}^{*})+{d_{\mathrm{edit}}}({\mathsf{w}}_{s-1}^{*},\mathsf{x}_{I_{s-1}^{*}})<4\gamma
t_{s-1},$ (15)

where
${d_{\mathrm{edit}}}(\mathsf{x}_{I},{\mathsf{y}}^{(m)}_{Q_{s-1}^{m}})\leq\gamma
t_{s-1}$ follows as in the base case but now using (vi) rather than (v). The
soundness follows from (15) and (iii), and the inductive step is completed. ∎

####  4.4.2 Second stage: Determining a consensus location close to
$\mathrm{source}^{\ast}(\ell^{\ast})$.

We finish the proof of Lemma 21 with the following lemma for the second stage
of Align:

######  Lemma 23.

Locations $\ell^{(1)},\ldots,\ell^{(M)}$ returned by Align satisfy the
following two conditions: (A) at least 90% of
$\mathrm{source}^{(m)}(\ell^{(m)})$, $m\in[M]$, agree on the same location
$i\in[n]$ and (B) the consensus location $i$ satisfies

$\mathrm{source}^{*}(\ell^{*})-2H\leq i\leq\mathrm{source}^{*}(\ell^{*}).$
(16)

$\text{\boldmath${\mathsf{y}}$}^{\ast}$${\mathsf{x}}$$\text{\boldmath${\mathsf{y}}$}^{(m)},m\in
G$$Q^{\ast}_{1}$$N(I^{\ast}_{1})$$I^{\ast}_{1}=\overline{\mathrm{source}^{\ast}(Q^{\ast}_{1})}$
Figure 4: Second stage of Align: The red line is the subword
${\mathsf{y}}^{\ast}_{Q^{\ast}_{1}}={\mathsf{w}}^{\ast}_{1}$ and it appears as
the disconnected red segments in
$\mathsf{x}_{\mathrm{source}^{\ast}(Q^{\ast}_{1})}$. The blue, green and
purple lines are the subwords ${\mathsf{y}}^{(m)}_{Q^{m}_{1}},m\in G$ and
$\mathsf{x}_{I^{m}=\overline{\mathrm{source}^{(m)}(Q^{m}_{1})}},m\in G$. Since
$m\in G$, we have that $N(I^{\ast}_{1})\cap D^{(m)}=\emptyset$, and so
$\smash{{\mathsf{y}}^{(m)}_{Q_{1}^{m}}=\mathsf{x}_{I^{m}}}$. The orange line
is the common subword $\mathsf{x}_{\cap_{m\in G}I^{m}}$ that appears in the
three subwords ${\mathsf{y}}^{(m)}_{Q^{m}_{1}}$.

###### Proof.

It follows from Lemma 22 that for every $m\in[M]$, the interval $Q_{1}^{m}$
satisfies (12). Let $G$ be the set of $m\in[M]$ such that $N(I_{1}^{*})\cap
D^{(m)}=\varnothing$; by (vii) we have that $|G|\geq 0.95M.$ Let
$\smash{I^{m}=\overline{\mathrm{source}^{(m)}(Q^{m}_{1})}}$. It follows from
(12) that every $m\in[M]$ satisfies $\smash{|I^{m}\bigtriangleup
I_{1}^{*}|\leq 4\gamma t_{1}}$ and thus $I^{m}\subseteq N(I_{1}^{*})$. As
$N(I_{1}^{*})\cap D^{(m)}=\varnothing$ we have
$\smash{{\mathsf{y}}^{(m)}_{Q_{1}^{m}}=\mathsf{x}_{I^{m}}}$ (and
$\mathrm{source}^{(m)}$ induces a bijection between $Q_{1}^{m}$ and $I^{m}$)
for each $m\in G$. Moreover,

${\left|\bigcap_{m\in G}I^{m}\right|\geq(1-2\cdot 4\gamma)t_{1}\geq
0.9t_{1}},$

which implies the completeness part: ${\mathsf{w}}:=\mathsf{x}_{\cap_{m\in
G}I^{m}}$ appears as a subword in at least $95\%$ of
$\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$ (i.e., every $m\in G$) and has length
at least $0.9t_{1}$.

Finally, we prove the soundness part: Assume that ${\mathsf{w}}$ is a string
of length at least $0.9t_{1}$ and appears as a subword in at least $95\%$ of
$\smash{{\mathsf{y}}^{(m)}_{Q^{m}_{1}}}$, $m=1,\dots,M$. Then at least $90\%$
of $m\in[M]$ have $m\in G$ and contain ${\mathsf{w}}$ as a subword. Let
$G^{\prime}\subseteq G$ denote the set of such $m\in G$. It follows from (iv)
that $\mathrm{source}^{(m)}(\ell^{(m)})$ are the same for all $m\in
G^{\prime}$, which consists of at least $90\%$ of $[M]$. To prove (16), we
take any $m\in G^{\prime}$ and have that $\mathrm{source}^{(m)}(\ell^{(m)})$
is at least $0.9t_{1}$ away from the right end of $I^{m}$; on the other hand,
$\mathrm{source}^{*}(\ell^{*})$ is no more than $H+\gamma t_{1}$ away from the
right end of $I_{1}^{*}$, using $|I_{1}^{*}|<(1+\gamma)t_{1}$. Given that the
right ends of $I^{m}$ and $I_{1}^{*}$ differ by no more than $4\gamma t_{1}$,
we have $\mathrm{source}^{(m)}(\ell^{(m)})\leq\mathrm{source}^{*}(\ell^{*})$.
Similarly, $\mathrm{source}^{(m)}(\ell^{(m)})$ is at least as large as the
left end of $I^{m}$ but $\mathrm{source}^{*}(\ell^{*})$ is similarly no more
than $H+\gamma t_{1}$ away from the left end of $I_{1}^{*}$. Given that their
left ends differ by no more than $4\gamma t_{1}$, we have that
$\mathrm{source}^{(m)}(\ell^{(m)})-\mathrm{source}^{*}(\ell^{*})\leq 4\gamma
t_{1}+H+\gamma t_{1}$, which is at most $2H$ by (4) and the definition of
$t_{1}=2H+1.$ ∎

##  5 The BMA algorithm and proof of Theorem 5

The goal of this section is to prove Theorem 5 which is restated below in full
detail. As mentioned in the introduction, the BMA algorithm (which stands for
Bitwise Majority Alignment) was first described and analyzed in [BKKM04].
Recall the two parameters $\delta$ (deletion rate) and $M$ (number of traces)
that satisfy (2) for some sufficiently large constant $K$, and the positive
integer $H\leq 2\log n$ given in $(\ref{eq:H})$. Let us set some parameters:
define

$L:=8H,\quad G:=L/2,\quad\text{~{}and~{}}R:=L2^{0.01L}.$ (17)

We prove in this section that BMA reconstructs any source string
$\smash{\tilde{\mathsf{x}}\in\\{0,1\\}^{R}}$ exactly with $M$ traces from
$\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$ with high probability333We use
$\tilde{\mathsf{x}}$ instead of $\mathsf{x}$ for the source string because
later in the next section the role of $\tilde{\mathsf{x}}$ will be played by
various different substrings of $\mathsf{x}$ of length $R$., when
$\tilde{\mathsf{x}}$ does not contain any “ _long deserts_.” We now recall the
definition of deserts from [CDL+21a].

######  Definition 24.

A string is said to be a _$k$ -desert_ for some $k\geq 1$ if it is the prefix
of ${\mathsf{s}}^{\infty}$ for some string ${\mathsf{s}}\in\\{0,1\\}^{k}$. We
say a string is a _long desert_ if it is a $k$-desert of length $L$ for some
$k\leq G$.

The algorithm BMA is described in Algorithm 3, and its input consists of $M$
traces $\mathsf{z}^{(1)},\ldots,\mathsf{z}^{(M)}$ of
$\tilde{\mathsf{x}}$.444Note that in Reconstruct, we run BMA on $M+1$ strings
obtained from ${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$
instead of $M$ strings. In its analysis, however, we pretend the string from
${\mathsf{y}}^{*}$ is not present and focus on what happens when running BMA
on the other $M$ strings only. This is why we focus on analyzing BMA running
on $M$ strings in this section. We restate the main theorem of this section:

######  Theorem 25 (Detailed statement of Theorem 5).

Let $\tilde{\mathsf{x}}\in\\{0,1\\}^{R}$ be a string that does not contain any
long desert. Let
$\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$
be independent traces. With probability at least $1-2^{-H}$, BMA returns
exactly $\tilde{\mathsf{x}}$ and in every round $t\in[R]$, the majority is
reached by at least $90\%$ of the $M$ bits that are pointed to in
$\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}$.

Similar to the previous section, we write $D^{(m)}\subseteq[R]$ to denote the
set of positions deleted in $\tilde{\mathsf{x}}$ to obtain $\mathsf{z}^{(m)}$,
and use them to define $\mathrm{source}^{(m)}(\cdot)$; the only difference is
that we set

$\mathrm{source}^{(m)}\bigl{(}|\mathsf{z}^{(m)}|+\ell\bigr{)}=R+\ell$

for every $m\in[M]$ and $\ell\geq 1$ since the pointer into
${\mathsf{z}}^{(m)}$ may move beyond $\mathsf{z}^{(m)}$ into the padded
$\ast$’s (this can be viewed as adding $\ast$’s to the end of the unknown
$\tilde{\mathsf{x}}$ which are never deleted and are where the $\ast$’s at the
end of $\mathsf{z}^{(m)}$ come from). As introduced in Algorithm 3, let
$\mathrm{current}^{(m)}(t)$ denote the location of the pointer of
$\mathsf{z}^{(m)}$ at the start of the $t$-th step of BMA. In addition, let

$\textup{{last}}^{(m)}(t):=\mathrm{source}^{(m)}\bigl{(}\mathrm{current}^{(m)}(t)\bigr{)}\quad\text{and}\quad\textnormal{dist}^{(m)}(t):=\textup{{last}}^{(m)}(t)-t.$

Informally, $\textnormal{dist}^{(m)}(t)$ captures the number of positions in
$\tilde{\mathsf{x}}$ that the pointer into ${\mathsf{z}}^{(m)}$ has gotten
“ahead of where it should be.”

To prove Theorem 25, it suffices to show that with high probability, for every
$t^{*}\in[R]$ it holds that $\textnormal{dist}^{(m)}(t^{*})=0$ for at least
$90\%$ of $m\in[M]$. We will analyze the behavior of
$\\{\textnormal{dist}^{(m)}(\cdot)\\}_{m\in[M]}$ over random traces
$\smash{\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})}$.
The high level goal of the analysis is to show that for each $m\in[M]$, the
sequence of random variables
$\textnormal{dist}^{(m)}(1),\ldots,\textnormal{dist}^{(m)}(R)$ are nonnegative
and _negatively drifted_ (i.e., $\textnormal{dist}^{(m)}(t)$ tends to decrease
as $t$ grows).

Note that $\\{\textnormal{dist}^{(m)}(\cdot)\\}_{m\in[M]}$ are not independent
over $m$ due to correlations from the consensus $\boldsymbol{\mathsf{w}}$ they
produce together and thus this ensemble of random variables can be difficult
to analyze. To ease the analysis we introduce a new set of random variables
denoted by $\smash{\textnormal{dist}_{\textnormal{{ideal}}}^{(m)}(\cdot)}$ for
each ${m\in[M]}$. They are identical to $\textnormal{dist}^{(m)}(\cdot)$ with
one key difference: in Step 4 of BMA, we set
$\mathsf{w}_{t}=\tilde{\mathsf{x}}_{t}$ instead of the majority of the bits.
Note that this makes
$\smash{\\{\textnormal{dist}_{\textnormal{{ideal}}}^{(m)}(\cdot)\\}_{m\in[M]}}$
independent over $m$ and in fact, identically distributed. Hence, it suffices
to analyze any one of them which we denote by
$\textnormal{dist}_{\textnormal{{ideal}}}(\cdot)$ over the draw of
$\text{\boldmath${\mathsf{z}}$}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$;
we let $\mathbf{D}$ denote the set of positions deleted in ${\mathsf{z}}$. We
define $\textnormal{current}_{\textsf{ideal}}(\cdot)$ and
$\textup{{last}}_{\textnormal{{ideal}}}(\cdot)$ similarly.

The following is a key technical lemma.

######  Lemma 26.

For every $t^{*}\in[R]$, $\textnormal{dist}_{\textnormal{{ideal}}}(t^{*})=0$
with probability at least $1-2\delta L$ over
$\text{\boldmath${\mathsf{z}}$}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$.

We first use Lemma 26 to prove Theorem 25.

###### Proof of Theorem 25 using Lemma 26..

Let
$\text{\boldmath${\mathsf{z}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{z}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\tilde{\mathsf{x}})$.
For each $t\in[R]$, let $E_{t}$ be the event that

$\sum_{m\in[M]}\mathbf{1}\left[\textnormal{dist}_{\textnormal{{ideal}}}^{(m)}(t)=0\right]\geq
0.9M$

for each $t\in[R]$. When the event $E_{t}$ holds for every $t\in[R]$, we have
$\text{\boldmath${\mathsf{w}}$}=\tilde{\mathsf{x}}$ by an induction on $t$.
This implies that the two sets of random variables
($\smash{\textnormal{dist}^{(m)}(\cdot)}$ and
$\smash{\textnormal{dist}^{(m)}_{\mathsf{ideal}}(\cdot)}$) are indeed
identical, which in turn implies for every $t\in[R]$,
$\textnormal{dist}^{(m)}(t)=0$ for at least $90\%$ of $m\in[M]$.

As a result it suffices to understand the probability of $E_{t}$. Given that
these random variables are independent, it follows from Lemma 26 and Equation
3 that for every $t\in[R]$:

$\operatorname{{\bf Pr}}\bigl{[}E_{t}\bigr{]}\geq 1-2^{M}\cdot\bigl{(}2\delta
L\bigr{)}^{0.9M}\geq 1-\left(\frac{48\delta M}{K}\log\frac{1}{\delta
M}\right)^{\frac{0.9HK}{\log(1/(\delta M))}}\geq 1-2^{-0.45HK}.$

where the last inequality uses

$\frac{48\delta M}{K}\log\left(\frac{1}{\delta M}\right)\leq\sqrt{\delta M}$

which holds when $K$ is sufficiently large. It follows from a union bound
(using $R=L2^{0.01L}$) that

$\operatorname{{\bf Pr}}\bigl{[}E_{t}\text{~{}holds for
all~{}}t\in[R]\bigr{]}\geq 1-R\cdot 2^{-0.45HK}\geq 1-2^{-H}$

by setting $K$ to be sufficiently large. This finishes the proof of the
theorem. ∎

Input: A multiset $\\{\mathsf{z}^{(1)},\ldots,\mathsf{z}^{(M)}\\}$ of $M$
strings

Output: Either $\varepsilon$, the empty string, or a string
${\mathsf{w}}\in\\{0,1\\}^{R}$

1 For each $m\in[M]$, concatenate $R$ many $\ast$’s to the end of
$\mathsf{z}^{(m)}$

2 Set $t=1$ and $\textnormal{current}^{(m)}(t)=1$ for each $m\in[M]$

3 while  _$t\leq R$_ do

4 Set $\mathsf{w}_{t}\in\\{0,1,\ast\\}$ to be the majority of the $M$ symbols
$\smash{\mathsf{z}^{(m)}_{\textnormal{current}^{(m)}(t)}}$, $m\in[M]$

5 For each $m\in[M]$, set
$\textnormal{current}^{(m)}(t+1)=\begin{cases}\textnormal{current}^{(m)}(t)+1&\text{\
if
$\mathsf{z}^{(m)}_{\textnormal{current}^{(m)}(t)}=\mathsf{w}_{t}$}\\\\[-1.29167pt]
\textnormal{current}^{(m)}(t)&\text{\ otherwise}\end{cases}$

6 Increment $t$

return $\mathsf{w}$ if $\mathsf{w}$ does not contain any $*$ (so
$\mathsf{w}\in\\{0,1\\}^{R}$) or $\varepsilon$ if $\mathsf{w}$ contains at
least one $*$

Algorithm 3 Algorithm BMA Figure 5: The Algorithm BMA

###  5.1 Proof of Lemma 26

In the rest of the section we prove Lemma 26. We start with three simple
claims (which may also be found in [CDL+21a]); these claims hold for any trace
$\mathsf{z}$ (and deletions $D$):

######  Claim 27.

For each $t\in[R]$, letting $b$ be the _(_
${\textup{{last}}_{\textnormal{{ideal}}}(t)}$_)_ -th bit of
$\tilde{\mathsf{x}}$, we have

  1. 1.

If $\tilde{\mathsf{x}}_{t}\neq b$, then
$\textnormal{dist}_{\textnormal{{ideal}}}(t+1)=\textnormal{dist}_{\textnormal{{ideal}}}(t)-1$.

  2. 2.

If $\tilde{\mathsf{x}}_{t}=b$, then
$\textnormal{dist}_{\textnormal{{ideal}}}(t+1)=\textnormal{dist}_{\textnormal{{ideal}}}(t)+\ell$,
where $\ell$ is the nonnegative integer with

$\textup{{last}}_{\textnormal{{ideal}}}(t)+1,\ldots,\textup{{last}}_{\textnormal{{ideal}}}(t)+\ell\in
D\quad\text{and}\quad\textup{{last}}_{\textnormal{{ideal}}}(t)+\ell+1\notin
D.$ (18)

###### Proof.

The first item follows from the observation that
$\textnormal{current}_{\textsf{ideal}}(t+1)=\textnormal{current}_{\textsf{ideal}}(t)$.

For the second item, we have
$\smash{\textnormal{current}_{\textsf{ideal}}(t+1)=\textnormal{current}_{\textsf{ideal}}(t)+1}$.
It now points to the next bit in $\mathsf{z}^{(m)}$, which is the bit of
$\tilde{\mathsf{x}}$ indexed by
$\textup{{last}}_{\textnormal{{ideal}}}(t)+\ell+1$ with $\ell$ defined in
(18). ∎

We next have the following two easy observations:

######  Claim 28.

We have $\textnormal{dist}_{\textnormal{{ideal}}}(t)\geq 0$ and
$\textup{{last}}_{\textnormal{{ideal}}}(t)\leq R+1$ for every $t\in[R]$.

###### Proof.

The proof of the first part is by induction. Using Claim 27,
$\textnormal{dist}_{\textnormal{{ideal}}}(t+1)\geq\textnormal{dist}_{\textnormal{{ideal}}}(t)-1$.
So if $\textnormal{dist}_{\textnormal{{ideal}}}(t)>0$ then
$\textnormal{dist}_{\textnormal{{ideal}}}(t+1)\geq 0$. Otherwise, if
$\textnormal{dist}_{\textnormal{{ideal}}}(t)=0$, we can apply the second item
of Claim 27 to conclude that
$\textnormal{dist}_{\textnormal{{ideal}}}(t+1)\geq 0$. For the second part
note that once $\textup{{last}}_{\textnormal{{ideal}}}(t)$ reaches $R+1$
(i.e., $\textnormal{current}_{\textsf{ideal}}(t)$ reaches
$|{\mathsf{y}}^{*}|+1$), it cannot move further as $\mathsf{x}$ is a string in
$\\{0,1\\}$ but the current bit in ${\mathsf{y}}^{*}$ is $*$. ∎

######  Claim 29.

If
$\textnormal{dist}_{\textnormal{{ideal}}}(t)=\cdots=\textnormal{dist}_{\textnormal{{ideal}}}(t+L)=k$
for some $k\in[G]$, then $\tilde{\mathsf{x}}$ has a long desert.

###### Proof.

We have that $\tilde{\mathsf{x}}_{t+\ell}$ is equal to the
$\textup{{last}}_{\mathsf{ideal}}(t+\ell)$-th bit of $\tilde{\mathsf{x}}$ for
all $\ell\in[0:L-1]$, and hence using Claim 27, we have
$\tilde{\mathsf{x}}_{t+\ell}=\tilde{\mathsf{x}}_{t+k+\ell}$ for all
$\ell\in[0:L-1]$. The claim follows. ∎

We now start to prove Lemma 26. Let $t^{*}\in[R]$ be the round we consider in
Lemma 26, with $t^{*}=t_{0}+sL$ such that $t_{0}\in\\{0,1,$ $\ldots,L-1\\}$
and $s\leq 2^{0.01L}$. We observe that

$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}),\hskip
1.70709pt\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+L),\hskip
1.70709pt\ldots,\hskip
1.70709pt\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+sL)$ (19)

is a Markov process and look at how
$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+(\ell+1)L)$ changes
conditioned on $\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+\ell L)$.

To this end, let us condition on
$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+\ell L)=\Delta\geq 0$, so
$\textup{{last}}_{\textnormal{{ideal}}}(t_{0}+\ell L)=t_{0}+\ell L+\Delta$.
Conditioning on this, each bit of $\tilde{\mathsf{x}}$ after $t_{0}+\ell
L+\Delta$ is deleted independently and added to $\mathbf{D}$ with probability
$\delta$. Let ${\boldsymbol{\beta}}$ be the nonnegative random variable such
that _either_

$\displaystyle t_{0}+\ell L+\Delta+{\boldsymbol{\beta}}\text{~{}is at
most~{}}R\text{~{}and does not belong to~{}}\mathbf{D}\quad\text{and}$
$\displaystyle\bigl{\\{}t_{0}+\ell L+\Delta+1,\ldots,t_{0}+\ell
L+\Delta+{\boldsymbol{\beta}}\bigr{\\}}\cap\overline{\mathbf{D}}=L,$

i.e., $t_{0}+\ell L+\Delta+{\boldsymbol{\beta}}$ is the unique location in
$\mathsf{x}$ that is the $L$-th undeleted position after $t_{0}+\ell
L+\Delta$, _or_ ${\boldsymbol{\beta}}$ is chosen using $t_{0}+\ell
L+\Delta+{\boldsymbol{\beta}}=R+1$ if no such ${\boldsymbol{\beta}}$ exists.
Since $\textup{{last}}_{\textnormal{{ideal}}}(\cdot)$ can move forward by at
most $L$ undeleted positions in steps $t_{0}+\ell L+1,\dots,t_{0}+(\ell+1)L$,
it follows from the second part of Claim 28 that

$\textup{{last}}_{\textnormal{{ideal}}}\bigl{(}t_{0}+(\ell+1)L\bigr{)}\leq
t_{0}+\ell L+\Delta+{\boldsymbol{\beta}}$

and thus, we have the following upper bound:

$\textnormal{dist}_{\textnormal{{ideal}}}\bigl{(}t_{0}+(\ell+1)L\bigr{)}\leq\textnormal{dist}_{\textnormal{{ideal}}}\bigl{(}t_{0}+\ell
L\bigr{)}+{\boldsymbol{\beta}}-L.$

Moreover, when $\Delta\leq G$ and ${\boldsymbol{\beta}}\leq L$ (including
${\boldsymbol{\beta}}=L$), we have

$\textnormal{dist}_{\textnormal{{ideal}}}\bigl{(}t_{0}+(\ell+1)L\bigr{)}\leq\max\Bigl{(}\textnormal{dist}_{\textnormal{{ideal}}}\bigl{(}t_{0}+\ell
L\bigr{)}-1,0\Bigr{)}.$

It holds for ${\boldsymbol{\beta}}=L$ because otherwise by Claim 29, the
subword of $\tilde{\mathsf{x}}$ in ${[t_{0}+\ell L:t_{0}+(\ell+1)L-1]}$ would
be a long desert, contradicting with our assumption that $\tilde{\mathsf{x}}$
has no long deserts.

In the next portion of the analysis we relate this Markov process to a simpler
one for which the transition probabilities are the same for all states. Note
that ${\boldsymbol{\beta}}$ is distributed as

$\min\bigl{(}R+1-(t_{0}+\ell L+\Delta),{\boldsymbol{\beta}}^{*}\bigr{)}$

where ${\boldsymbol{\beta}}^{*}$ denotes the sum of $L$ i.i.d. geometric
random variables with success probability $1-\delta$.555We use the version of
the geometric distribution for which the outcome of a draw is the total number
of trials up to and including the first success (hence the support is
$\\{1,2,3,\dots\\}$). So ${\boldsymbol{\beta}}$ is stochastically dominated by
${\boldsymbol{\beta}}^{*}$.666Recall that a random variable $\mathbf{X}$ is
said to stochastically dominate $\mathbf{Y}$ if $\operatorname{{\bf
Pr}}[\mathbf{X}\geq a]\geq\operatorname{{\bf Pr}}[\mathbf{Y}\geq a]$ for all
$a$. Let $\alpha:=\delta L$, which can be made sufficiently small as $\delta
L\leq 8/K$ and $K$ can be made sufficiently large. We use the following rough
estimates for the probability of ${\boldsymbol{\beta}}^{*}=L+c$ for
$c=0,1,\ldots$: When $c=0$ we have

$\operatorname{{\bf
Pr}}\big{[}{\boldsymbol{\beta}}^{*}=L\big{]}=(1-\delta)^{L}\geq 1-\delta
L=1-\alpha>\frac{1-2\alpha}{1-\alpha}.$ (20)

(The reason for using the lower bound $(1-2\alpha)/(1-\alpha)$ in the second
inequality will become clear soon.) When $c\geq 1$,

$\operatorname{{\bf
Pr}}\big{[}{\boldsymbol{\beta}}^{*}=L+c\big{]}=\binom{L+c-1}{c}\delta^{c}(1-\delta)^{L}\leq\big{(}L\delta\big{)}^{c}=\alpha^{c}.$
(21)

Inspired by these estimates, we introduce the following simpler Markov chain
$\mathbf{X}_{0},\mathbf{X}_{1},\ldots,\mathbf{X}_{s}\geq 0$, where (1)
$\mathbf{X}_{0}$ is distributed the same as
$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0})$, and (2) for each
$\mathbf{X}_{\ell+1}$, if $\mathbf{X}_{\ell}>G$, then

$\mathbf{X}_{\ell+1}=\begin{cases}\mathbf{X}_{\ell}&\text{with probability
$(1-2\alpha)/(1-\alpha)$}\\\ \mathbf{X}_{\ell}+c&\text{with probability
$\alpha^{c}$ for each $c\geq 1$}\end{cases};$ (22)

if $\mathbf{X}_{\ell}\leq G$, then

$\mathbf{X}_{\ell+1}=\begin{cases}\max(\mathbf{X}_{\ell}-1,0)&\text{with
probability $(1-2\alpha)/(1-\alpha)$}\\\ \mathbf{X}_{\ell}+c&\text{with
probability $\alpha^{c}$ for each $c\geq 1$}\end{cases}.$ (23)

Note that the use of $(1-2\alpha)/(1-\alpha)$ makes sure that the
probabilities sum to $1$. Below we will analyze
$\mathbf{X}_{0},\mathbf{X}_{1},...,\mathbf{X}_{s}$ in lieu of Equation 19.

Lemma 26 follows directly by combining the following two claims:

######  Claim 30.

$\operatorname{{\bf
Pr}}\bigl{[}\textnormal{dist}_{\textnormal{{ideal}}}(t^{*})\geq
c\bigr{]}\geq\operatorname{{\bf Pr}}\bigl{[}\mathbf{X}_{s}\geq c\bigr{]}$ for
every $c$.

######  Claim 31.

$\operatorname{{\bf Pr}}\big{[}\mathbf{X}_{s}=0\big{]}\geq 1-2\alpha.$

###### Proof of Claim 30.

We prove by induction that for every $\ell\in[0:s]$, $\mathbf{X}_{\ell}$
stochastically dominates $\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+\ell
L)$. The basis is trivial since $\mathbf{X}_{0}$ has the same distribution as
$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0})$.

To prove the case with $\mathbf{X}_{\ell+1}$ using $\mathbf{X}_{\ell}$, we
make two simple observations:

  1. 1.

First, for any $a\geq b$, the distribution of $\mathbf{X}_{\ell+1}$
conditioned on $\mathbf{X}_{\ell}=a$ stochastically dominates the distribution
of $\mathbf{X}_{\ell+1}$ conditioned on $\mathbf{X}_{\ell}=b$.

  2. 2.

Next for any $a$, it follows from Equations 20 and 21 that the distribution of
$\mathbf{X}_{\ell+1}$ conditioned on $\mathbf{X}_{\ell}=a$ stochastically
dominates that of $\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+(\ell+1)L)$
conditioned on $\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+\ell L)=a$.

It follows from these two observations, as well as the inductive hypothesis on
$\ell$, that $\mathbf{X}_{\ell+1}$ stochastically dominates
$\textnormal{dist}_{\textnormal{{ideal}}}(t_{0}+(\ell+1)H)$. This finishes the
proof of the claim. ∎

###### Proof of Claim 31.

We prove by induction on $\ell=0,1,\ldots,s$ that the distribution of
$\mathbf{X}_{\ell}$ satisfies

$\displaystyle\operatorname{{\bf Pr}}\bigl{[}\mathbf{X}_{\ell}=c\bigr{]}$
$\displaystyle\leq\frac{\alpha}{1-2\alpha}\cdot\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{c-1},\qquad\text{for
every $c\in[G]$};$ (24) $\displaystyle\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}>G\bigr{]}$
$\displaystyle\leq(\ell+1)\cdot\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{G}.$
(25)

Before working on the induction, we have from these two items that

$\displaystyle\operatorname{{\bf Pr}}\bigl{[}\mathbf{X}_{s}=0\bigr{]}$
$\displaystyle\geq 1-\frac{\alpha}{1-2\alpha}\cdot\sum_{a\geq
0}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{a}-(s+1)\cdot\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{G}$
$\displaystyle\geq 1-\frac{\alpha}{1-4\alpha+2\alpha^{2}}-\frac{\alpha}{2}$
$\displaystyle\geq 1-2\alpha.$

The second inequality used $s\leq 2^{0.01L}$, $G=L/2$ and the fact that
$\alpha$ can be made sufficiently small. The last inequality also used that
$\alpha$ is sufficiently small. We work on the induction below.

For the base case $\mathbf{X}_{0}$, recall that this random variable has the
same distribution as $\textnormal{dist}_{\textnormal{{ideal}}}(t_{0})$, and
hence we have for each $c\geq 1$,

$\operatorname{{\bf
Pr}}\bigl{[}\textnormal{dist}_{\textnormal{{ideal}}}(t_{0})=c\bigr{]}\leq\sum_{a\geq
c}\binom{t_{0}+c-1}{a}\delta^{a}\leq\sum_{a\geq
c}(L\delta)^{a}\leq\frac{\alpha^{c}}{1-2\alpha}\cdot\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{c-1},$

(where the second inequality above uses $t_{0}\leq L-1$ and the third uses
that $\alpha$ is sufficiently small) and also

$\operatorname{{\bf
Pr}}\bigl{[}\textnormal{dist}_{\textnormal{{ideal}}}(t_{0})>G\bigr{]}\leq\sum_{c\geq
G+1}\sum_{a\geq
c}\binom{t_{0}+c-1}{a}\delta^{a}\leq\frac{\alpha^{G+1}}{(1-\alpha)^{2}}\leq\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{G}.$

For the induction, we assume the statement holds for $\ell$ and use it to
prove the case with $\ell+1$. Using Equation 24, for every $c\in[G-1]$, we
have

$\displaystyle\operatorname{{\bf Pr}}\bigl{[}\mathbf{X}_{\ell+1}=c\bigr{]}$
$\displaystyle\leq\sum_{a=0}^{c-1}\alpha^{c-a}\cdot\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}=a\bigr{]}+\frac{1-2\alpha}{1-\alpha}\cdot\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}=c+1\bigr{]}$ (by Equation 23)
$\displaystyle\leq\alpha^{c}+\sum_{a=1}^{c-1}\alpha^{c-a}\frac{\alpha}{1-2\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{a-1}+\frac{1-2\alpha}{1-\alpha}\frac{\alpha}{1-2\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{c}$
$\displaystyle=\alpha^{c}+\frac{\alpha^{c}}{1-2\alpha}\sum_{a=1}^{c-1}\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{a-1}+\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{c}$
(26)
$\displaystyle=\alpha^{c}\left(1+\frac{1}{1-2\alpha}\frac{\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{c-1}-1}{\frac{2(1-\alpha)}{1-2\alpha}-1}+\frac{\alpha}{1-\alpha}\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{c}\right)$
$\displaystyle=\alpha^{c}\left(\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{c-1}+\frac{\alpha}{1-\alpha}\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{c}\right)$
(27)
$\displaystyle=\frac{\alpha}{1-2\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{c-1}.$

The proof for $c=G$ is similar except that we do not have the term for
$\mathbf{X}_{\ell}=G+1$.

Finally using Equations 24 and 25 we have

$\displaystyle\operatorname{{\bf Pr}}\bigl{[}\mathbf{X}_{\ell+1}>G\bigr{]}$
$\displaystyle\leq\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}>G\bigr{]}+\sum_{b>G}\sum_{a=0}^{G}\alpha^{b-a}\cdot\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}=a\bigr{]}$ (by definition of
$\mathbf{X}_{\cdot}$) $\displaystyle\leq\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}>G\bigr{]}+\frac{1}{1-\alpha}\sum_{a=0}^{G}\alpha^{G+1-a}\cdot\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}=a\bigr{]}$ $\displaystyle\leq\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}>G\bigr{]}+\frac{\alpha^{G+1}}{1-\alpha}\left(1+\frac{1}{1-2\alpha}\sum_{a=1}^{G}\left(\frac{2(1-\alpha)}{1-2\alpha}\right)^{a-1}\right)$
(by Equation 24) $\displaystyle=\operatorname{{\bf
Pr}}\bigl{[}\mathbf{X}_{\ell}>G\bigr{]}+\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{G}$
(28)
$\displaystyle\leq(\ell+2)\cdot\frac{\alpha}{1-\alpha}\left(\frac{2\alpha(1-\alpha)}{1-2\alpha}\right)^{G},$
(by Equation 25)

where Equation 28 used similar derivation between Equations 26 and 27 earlier.
This finishes the induction and the proof of the claim. ∎

##  6 Main Algorithm

Input: A positive integer $n$ and a tuple of $(M+1)$ strings
${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$

Output: A binary string ${\mathsf{w}}$

1 Set $\ell^{*}=5\tau\log n$ and ${\mathsf{w}}=\varepsilon$

2 while  _$\ell^{*}\leq|{\mathsf{y}}^{*}|-R$ and
$\ell^{*}\leq|{\mathsf{y}}^{*}|-5\tau\log n$_ do

3 Run $\textup{{\tt Align}}\hskip
1.13791pt(\ell^{*},{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)})$
to obtain a tuple of locations $(\ell^{(1)},\ldots,\ell^{(M)})$

4 Run $\smash{\textup{{\tt BMA}}\hskip
1.13791pt({\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)};\ell^{*},\ell^{(1)},\ldots,\ell^{(m)})}$
to obtain a binary string ($\varepsilon$ or in $\\{0,1\\}^{R}$)

5 Concatenate the string returned by BMA to the end of ${\mathsf{w}}$

6 Set $\ell^{*}$ to be the final pointer of ${\mathsf{y}}^{*}$ in the run of
BMA above and increment it

7

return ${\mathsf{w}}$.

Algorithm 4 Reconstruct Figure 6: The Algorithm Reconstruct

Let $\delta$ and $M$ be two parameters that satisfy Equations 2 and 3. Recall
the following parameters used in our analysis of Align and BMA:

$\tau=500,\quad H=\frac{M}{K}\log\left(\frac{1}{\delta M}\right)\leq{2\log
n},\quad L=8H,\quad G=L/2=4H\quad\text{and}\quad R=L2^{0.01L}.$

(Note that $L\leq 16\log n,$ $G\leq 8\log n$ and $R\leq O(n^{0.16}\log n).$)
Our main (deterministic) algorithm Reconstruct is described in Figure 6, where
we use

$\textup{{\tt
BMA}}\big{(}{\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)};\ell^{*},\ell^{(1)},\ldots,\ell^{(M)}\big{)}$

to denote running BMA on the suffix of ${\mathsf{y}}^{*}$ starting at location
$\ell^{*}$ and the suffix of each ${\mathsf{y}}^{(m)}$ starting at location
$\ell^{(m)}$. Recall that BMA either returns the empty string $\varepsilon$ or
a string ${\mathsf{w}}\in\\{0,1\\}^{R}$.

We prove the following theorem about the performance of Reconstruct:

######  Theorem 32.

Let $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(x)$.
With probability at least $1-1/n$, Reconstruct on
$\text{\boldmath${\mathsf{y}}$}^{*},\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}$
returns a string ${\mathsf{w}}$ with edit distance at most $2^{-0.01H}n$ from
${\mathsf{x}}$.

Similar to the analysis of Align in Section 4, we divide the analysis of
Reconstruct into two parts: In Section 6.1, we begin by describing some good
events over the randomness of ${\mathsf{x}}$, $\mathbf{D}^{*}$ and
$\mathbf{D}^{(m)}:m\in[M]$, and show that these events happen with probability
at least $1-1/n$. The rest of the analysis in Section 6.2 will be entirely
deterministic. We show that Reconstruct on
${\mathsf{y}}^{*},{\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ must return a
string ${\mathsf{w}}$ with small edit distance from $\mathsf{x}$ when all the
events described in Section 6.1 hold.

###  6.1 Probabilistic Analysis

We start by showing that for
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, the number of
length-${(2R)}$ subwords of ${\mathsf{x}}$ that contain at least one long
desert is small.

######  Lemma 33.

With probability at least $1-\exp(-n^{0.1})$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$, the number of
$i\in[n-{2R}+1]$ such that $\text{\boldmath${\mathsf{x}}$}_{[i:i+{2R}-1]}$ has
at least one long desert is at most $2^{-0.13H}n$.

###### Proof.

Fix any $k\leq G$. The probability of a random length-$L$ string being a
$k$-desert is at most

$2^{k}\cdot\frac{1}{2^{L}}.$

As a result, the probability of a random length-$L$ string being a long desert
is at most

$\sum_{k=1}^{G}\frac{2^{k}}{2^{L}}\leq 2^{-0.4L}.$

Consider the number of length-$L$ subwords in
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ that are long deserts. Given
that changing each bit can only change the number by no more than $L$, it
follows from McDiarmid’s inequality (Theorem 6) that with probability at least
$1-\exp(-n^{0.1})$, this number is at most

$2^{-0.4L}n+O(n^{0.55}L)\leq 2^{-0.22H}n$

using $H\leq 2\log n$. When this happens, the number of indices $i$ we care
about in the statement of the lemma is at most ${(4R-L)}\cdot 2^{-0.22H}n\leq
2^{-0.13H}n$ using $R=L2^{0.01L}$ and $L=8H$. ∎

We modify the definition of $\mathrm{image}^{(m)}$ so that it is well-defined
for every $i\in[n]$: $\mathrm{image}^{(m)}(i)$ is the smallest location
$\ell\in[|{\mathsf{y}}^{(m)}|]$ such that $\mathrm{source}^{(m)}(\ell)\geq i$,
or set $\mathrm{image}^{(m)}(i)=|{\mathsf{y}}^{(m)}|+1$ if no such $\ell$
exists. (Note that when the latter happens, the suffix of ${\mathsf{y}}^{(m)}$
starting at $|{\mathsf{y}}^{(m)}|+1$ is the empty string $\varepsilon$.) We
say BMA _succeeds on ${\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ at
location $i\in[n-R+1]$ of $\mathsf{x}$_ if running BMA on
${\mathsf{y}}^{(1)},\ldots,{\mathsf{y}}^{(M)}$ starting at
$\mathrm{image}^{(1)}(i),\ldots,\mathrm{image}^{(M)}(i)$ returns exactly the
$R$-bit string $\mathsf{x}_{[i:i+R-1]}$ and moreover, the consensus is
achieved by at least $90\%$ of strings in every round of BMA’s execution.

The following lemma is a direct corollary of Lemma 33 and Theorem 25:

######  Lemma 34.

Let $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\text{\boldmath${\mathsf{y}}$}^{(1)},\ldots,\text{\boldmath${\mathsf{y}}$}^{(M)}\sim\mathrm{Del}_{\delta}(\text{\boldmath${\mathsf{x}}$})$.
With probability at least $1-2\exp(-n^{0.1})$, BMA succeeds on all but at most
$2^{-0.1H}n$ locations $i\in[n-R+1]$ in ${\mathsf{x}}$.

###### Proof.

It follows from Lemma 33 that with probability at least $1-\exp(-n^{0.1})$, a
random $\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ has no more than
$2^{-0.13H}n$ length-${(2R)}$ subwords that contain at least one long desert.
Let $\mathsf{x}$ be such a string and fix any location $i$ such that
$\smash{x_{[i:i+R-1]}}$ contains no long deserts. If the conclusion of Theorem
25 holds on $\tilde{\mathsf{x}}:=\smash{\mathsf{x}_{[i:i+R-1]}}$ over subwords
of $\text{\boldmath${\mathsf{y}}$}^{(m)}$ that originate from
$\smash{\mathsf{x}_{[i:i+R-1]}}$, then BMA must succeed at location $i$. It
follows from Theorem 25 that this happens with probability at least
$1-2^{-H}$.

We will apply McDiarmid’s inequality. Note that each of the $nM$ independent
random variables (each of which indicates whether or not a bit of $\mathsf{x}$
is included in $\mathbf{D}^{(m)}$) can only change the number we care about
(i.e. the number of locations $i$ such that the conclusion of Theorem 25 holds
on $\tilde{\mathsf{x}}:=\mathsf{x}_{[i:i+R-1]}$ over subwords of
$\smash{\text{\boldmath${\mathsf{y}}$}^{(m)}}$ that originate from
$\mathsf{x}_{[i:i+R-1]}$) by no more than $R$. It follows that with
probability at least $\smash{1-\exp(-n^{0.1})}$, BMA succeeds on all except
$\smash{2^{-0.1H}n}$ many locations $i$ in $\mathsf{x}$ such that
$\mathsf{x}_{[i:i+R-1]}$ has no long deserts. The lemma follows. ∎

######  Lemma 35.

$\mathbf{D}^{*}\sim\mathcal{D}$ satisfies the following two properties with
probability at least $1-1/n^{2}$: (note that
$\lvert\text{\boldmath${\mathsf{y}}$}^{\ast}\rvert=n-\lvert\mathbf{D}^{\ast}\rvert$)

  1. 1.

$\mathrm{source}^{*}(5\tau\log n)=O(\log n)$ and

$\min\big{(}\mathrm{source}^{*}(\lvert\text{\boldmath${\mathsf{y}}$}^{\ast}\rvert-R),\,\mathrm{source}^{*}(\lvert\text{\boldmath${\mathsf{y}}$}^{\ast}\rvert-5\tau\log
n)\big{)}\geq n-(2R+O(\log n));$

  2. 2.

There are at most $2^{-0.2H}n$ values of $i\in[n]$ such that
$\mathrm{source}^{*}(\ell)<i<\mathrm{source}^{*}(\ell+1)$ for some
$\ell\in[\lvert\text{\boldmath${\mathsf{y}}$}^{\ast}\rvert-1]$ for which
$\mathrm{source}^{*}(\ell+1)-\mathrm{source}^{*}(\ell)\geq 2H$.

###### Proof.

The first part follows from a Chernoff bound.

For the second part, note that for $i$ to be counted, it must be the case that
either $\smash{[i-H+1:i]}$ $\smash{\subseteq\mathbf{D}^{*}}$ or
$\smash{[i:i+H-1]\subseteq\mathbf{D}^{*}}$, which occurs with probability at
most $2\cdot\delta^{H}\leq 2^{-H}$. The second part then follows from an
application of McDiarmid’s inequality. ∎

To describe our final condition on
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\mathbf{D}^{*}\sim\mathcal{D}$, we introduce a procedure which we call
$\textup{{\tt BMA}}^{\ast}$. $\textup{{\tt BMA}}^{\ast}$ takes as input a
string ${\mathsf{y}}^{*}$, a location $\ell^{*}$ such that
$|{\mathsf{y}}^{*}|\geq\ell^{*}+R$, and a reference string
${\mathsf{z}}\in\\{0,1\\}^{R}$. Let $\mathrm{current}^{*}(1)=\ell^{*}$. The
$\textup{{\tt BMA}}^{\ast}$ procedure repeats the following for $R$ rounds: In
the $t$-th round, $t\in[R]$, $\textup{{\tt BMA}}^{\ast}$ compares
${\mathsf{z}}_{t}$ with $\smash{{\mathsf{y}}^{*}_{\mathrm{current}^{*}(t)}}$
and set $\mathrm{current}^{*}(t+1)=\mathrm{current}^{*}(t)+1$ if they match
and $\mathrm{current}^{*}(t+1)=\mathrm{current}^{*}(t)$ if they do not match.
For each $t$ we also define
$\textup{{last}}^{*}(t)=\mathrm{source}^{*}\bigl{(}\mathrm{current}^{*}(t)\bigr{)}.$
After the final ($R$-th) round $\textup{{\tt BMA}}^{\ast}$ outputs

$\textup{{last}}^{*}(R+1):=\mathrm{source}^{*}\bigl{(}\mathrm{current}^{*}(R+1)\bigr{)}.$

Intuitively, $\textup{{\tt BMA}}^{\ast}$ outputs the final location of the
pointer $\ell^{\ast}$ after a successful run of BMA. Now we state the final
condition on $({\text{\boldmath${\mathsf{x}}$},\mathbf{D}^{*}})$. We say
$\textup{{\tt BMA}}^{*}$ _succeeds on a source string
$\mathsf{x}\in\\{0,1\\}^{n}$ with respect to ${\mathsf{y}}^{*}$_ if for all
but at most $2^{-0.1H}n$ many $\ell^{*}\in[|{\mathsf{y}}^{*}|-R]$, we have

$\textup{{\tt
BMA}}^{\ast}\big{(}{\mathsf{y}}^{*},\ell^{*},\mathsf{x}_{[i:i+R-1]}\big{)}\leq
i+R+G,\quad\text{for every
$i\in[\mathrm{source}^{*}(\ell^{*})-2H:\mathrm{source}^{*}(\ell^{*})]$.}$ (29)

Note that from an argument similar to the proof of Claim 28 we always have

$\textup{{\tt
BMA}}^{\ast}\big{(}{\mathsf{y}}^{*},\ell^{*},\mathsf{x}_{[i:i+R-1]}\big{)}\geq
i+R,$ (30)

so intuitively, $\textup{{\tt BMA}}^{\ast}$ succeeds on $\mathsf{x}$ with
respect to ${\mathsf{y}}^{*}$ if for almost every $\ell^{\ast}$, the output of
$\textup{{\tt BMA}}^{\ast}$ on input
$({\mathsf{y}}^{*},\ell^{*},\mathsf{x}_{[i:i+R-1]})$ is close to the “right
value” $i+R$.

######  Lemma 36.

With probability at least $1-2\exp(-n^{0.1})$ over
$\text{\boldmath${\mathsf{x}}$}\sim\\{0,1\\}^{n}$ and
$\mathbf{D}^{*}\sim\mathcal{D}$, $\textup{{\tt BMA}}^{*}$ succeeds on
${\mathsf{x}}$ with respect to $\text{\boldmath${\mathsf{y}}$}^{*}$.

###### Proof.

We will show that with high probability, the number of pairs $\ell^{*}$ and