Average-case reconstruction for the deletion channel:
subpolynomially many traces suffice
arXiv:1708.00854v1 [cs.DS] 1 Aug 2017

Yuval Peres

∗

Alex Zhai

†

August 3, 2017

Abstract
The deletion channel takes as input a bit string x ∈ {0, 1}n , and deletes
each bit independently with probability q, yielding a shorter string. The trace
reconstruction problem is to recover an unknown string x from many independent
outputs (called “traces”) of the deletion channel applied to x.
1/2
We show that if x is drawn uniformly at random and q < 1/2, then eO(log n)
traces suffice to reconstruct x with high probability. The previous best bound,
established in 2008 by Holenstein, Mitzenmacher, Panigrahy, and Wieder [5],
uses nO(1) traces and only applies for q less than a smaller threshold (it seems
that q < 0.07 is needed).
Our algorithm combines several ideas: 1) an alignment scheme for “greedily”
fitting the output of the deletion channel as a subsequence of the input; 2) a
version of the idea of “anchoring” used in [5]; and 3) complex analysis techniques
from recent work of Nazarov and Peres [9] and De, O’Donnell, and Servedio [3].

∗
†

Microsoft Research; peres@microsoft.com
Stanford University; azhai@stanford.edu

1

1

Introduction

The deletion channel takes as input a bit string x ∈ {0, 1}n . Each bit of x is (independently of other bits) retained with probability p and deleted with probability
q := 1 − p. The channel then outputs the concatenation of the retained bits; such an
output is called a trace. Suppose that the input x is unknown. The trace reconstruction problem asks the following: how many i.i.d. traces from the deletion channel do
we need to observe in order to determine x with high probability?
There are two basic variants of this problem, which we will call the “worst case”
and “average case”. In the worst case variant, the problem is to provide bounds that
hold uniformly over all possible input strings x. The average case variant supposes
that the input is chosen uniformly at random. In particular, we are allowed to ignore
some “hard-to-reconstruct” inputs, as long as they comprise a small fraction of all 2n
possible inputs. In this paper, we study the average case. Our main result is the
following.
Theorem 1.1. Suppose q < 12 , and let X ∈ {0, 1}n be an unknown bit string of length
n chosen uniformly at random. There is a constant Cq depending only on q such that it
√
is possible to reconstruct X with probability at least 1− Cnq using at most exp Cq log n
independent samples from the deletion channel with deletion probability q applied to X.

1.1

Related work

The study of trace reconstruction for the deletion channel seems to have been initiated
by Batu, Kannan, Khanna and McGregor [1], who were motivated by multiple sequence
alignment problems in computational biology. We focus on the regime where the
deletion probability q is held constant as n grows.
Previously, the best bound in the average case was due to Holenstein, Mitzenmacher, Panigrahy and Wieder [5], who gave an algorithm for reconstructing random
inputs using polynomially many traces when q is less than some small threshold c.1
Theorem 1.1 improves on this result in two ways: the number of traces is subpolynomial, and we extend the range of allowed q to the interval (0, 1/2).
1/2
In [5] it is also shown that eO(n log n) traces suffice for reconstruction with high
probability with worst case input. This was recently improved by Nazarov-Peres [9]
1/3
and De-O’Donnell-Servedio [3] (simultaneously and independently) to eO(n ) . Their
techniques, which we use in Section 4, play an important role in our proofs.
The question of whether the above bounds are optimal remains open. The best
lower bounds known are of order log2 n (McGregor, Price and Vorotnikova [7]) in the
average case and order n in the worst case ([1]).
Other settings for trace reconstruction include the case when q → 0 ([1]), when
insertions and substitutions are allowed as well as deletions ([6], [10]), or when the
1

The threshold c is not given explicitly in [5]. It seems that by optimizing their methods we cannot
achieve c > 0.07.

2

m

k

n

X
w
w
e
X
`0

`

Figure 1.1: Illustration of the alignment strategy. Dotted lines indicate correspondences between
e and positions in X.
positions in X

strings are taken over an alphabet whose size grows with n ([7]). For a more comprehensive review of the literature, we refer readers to the introduction of [3] or the survey
of Mitzenmacher [8].

1.2

Outline of approach

Let us give a high-level description of the algorithm used to prove Theorem 1.1. Suppose that we have already reconstructed the first k bits of X, and we consider a new
e Roughly speaking, our goal is to carry out the following steps:
trace X.
Alignment: Find some suitable index m slightly less than k, and try to (ape that corresponds to the m-th position
proximately) identify the position ` in X
of X. This occurs in two stages (see Figure 1.1):
e whose corresponding position
Initial alignment: Find a position `0 in X
in X is known to be about O(log n) places ahead of m.
Refined alignment: Consider a specific substring w of X located at m
e within O(log n)
and having length O(log1/2 n). Look for w to occur in X
characters following position `0 , and take ` to be the last position of this
occurrence of w.
e after ` as a trace of the bits of X after m.
Reconstruction: Use the bits of X
From these “traces”, we reconstruct at least k + 1 − m bits of X starting from
position m, which in particular includes the (k + 1)-th bit of X.
We can repeat the above
procedure for each k. In each iteration, the number of traces
√
needed will be eO( log n) . Moreover, these traces may be reused for each iteration,
because we will ultimately bound the probability of failure by a union bound.
1.2.1

Initial alignment step

e as a subsequence of X following a
The initial alignment step is based on fitting X
e respectively. We
e
“greedy algorithm”. Let Xi and Xi denote the i-th bits of X and X,
3

X:

e
X:
Figure 1.2: Illustration of the greedy algorithm used in the initial alignment step. Here, X = 11000110
e = 1010. Gray arrows point from the positions in X that were retained to their corresponding
and X
e Red arrows indicate the associations produced by our algorithm (i.e. X
e1 goes to X1 ,
positions in X.
e
e
e
X2 goes to X3 , X3 goes to X6 , X4 goes to X8 ).

e1 to the first bit in X that matches X
e1 , then associate X
e2 to the next bit in X
associate X
e2 , and so on (see Figure 1.2). This gives the “first possible” occurrence
that matches X
e as a subsequence of X, but does not necessarily reflect the true alignment of X
e to
of X
X. However, when q < 1/2 and X is random, it turns out that this greedy alignment
actually matches the true one to within O(log n) (stated precisely in Lemma 2.2).
Let us briefly describe why this is the case. Suppose that the position assigned by
our greedy algorithm lags behind the true position. Looking at the next bit in the
1
< 2 places in expectation. However,
trace, the true position should advance by 1−q
since the bits of X are uniformly random, the position for the greedy algorithm should
advance like a geometric random variable with mean 2, thereby “catching up”.
The same greedy matching idea was also considered by Mitzenmacher (see Section
3 of [8]) in the slightly different context of decoding for the deletion channel. Lemma
2.2 is a variant of Theorem 3.2 in [8]. However, many details are omitted in [8], so we
provide a self-contained proof in Section 2.
1.2.2

Refined alignment step

For the refined alignment, we take an approach similar to the use of “anchors” in
[5]. We again rely on the randomness of X and the assumption q < 1/2. Consider a
substring w of length a ≈ log1/2 n which contains the m-th bit of X. (In the language
of [5], w is our “anchor”.)
With probability pa , the string w appears in our trace because none of its bits
were deleted. There is also a chance that this exact sequence just happens to appear
after deletions to another part of the input. However, because X is random, the latter
scenario only happens with probability 2−a  pa . Thus, when we see w in our trace,
it most likely came from near position m of X (we discard traces if we do not see w),
thereby aligning to within O(log1/2 n).
We remark here that the above discussion sweeps under the rug a few considerations
about how to avoid accumulation of many small probabilities of error. In particular,
note that the error probabilities involved during the refined alignment step are like

4

1/2

e−O(log n) , which is not small enough to union bound over the whole string.
For example, a problem may arise if we have another copy of w appearing in X
e
that is only O(log n) positions away from m. In that case, appearances of w in X
might come from either copy of w in X, and it would be hard to distinguish the two
scenarios.
Recall, however, that we have allowed ourselves some flexibility in the choice of m.
Note that the initial alignment step means that we only need to worry about what
X looks like within distance O(log n) from the location m. We look at O(log1/2 n)
possible locations of m which are spaced O(log n) apart, and we argue that with high
probability, at least one of these locations (and the corresponding choice of w) behaves
in the desired way.
1.2.3

Reconstruction step

For the reconstruction step, we analyze bit statistics using methods based on those of [9]
and [3]. However, two adaptations are needed for our setting. First, our reconstruction
step only needs to recover a small number of bits, not the full string. The statement we
1/3
need is roughly that eO(r ) traces are enough to recover the first r bits of an unknown
string, which we apply with r = O(log3/2 n).
Second, since our alignment is not perfect, we must allow some random shifts of the
input string. The amount of shifting we can tolerate is relatively small, which explains
the need for accurate alignment. The issue of calculating bit statistics with random
shifts also appears in [5], although our techniques for handling this are rather different
from theirs.
These two adaptations can be carried out by small modifications to the relevant
proofs in [9] and [3], which are based on bounds for Littlewood polynomials on arcs of
the unit circle.

1.3

Notation

We will use boldface to denote bit strings, while the values of their bits are non-bolded
and subscripted by indices; for example, x = (x1 , x2 . . . , xn ) ∈ {0, 1}n . Let |x| = n
denote the length of x, and let xa:b denote the substring (xa , xa+1 , . . . , xb ). For brevity,
we also write xa: = xa:|x| for the suffix of x starting at xa .
Next, we introduce notation for describing the deletion channel. For a given pae) of sequences
rameter p ∈ (0, 1), let Dp∗ (x) denote the distribution over pairs (t, x
defined as follows: t = (t1 , t2 , . . . , tm ) is the random sequence of indices of x which are
retained by the deletion channel applied to x with deletion probability q = 1 − p, and
e = (e
x
x1 , x
e2 , . . . , x
em ) is given by x
ei = xti . Note that the length m = |t| is random.
e and not in t. Thus,
In some cases, we are only interested in the final output x
we also introduce the notation Dp (x) for the marginal distribution of Dp∗ (x) over the
e. We will sometimes use the notation Px ( · ) to emphasize that the string going
strings x
through the deletion channel is x.
5

e to
At some point, we will want to use t to associate several indices at once in x
their counterparts in x, or vice versa. Consider sets S ⊆ {1, 2, . . . , |x|} and Se ⊆
{1, 2, . . . , |e
x|}. Then, we use the notation
e := {ts : s ∈ S}
e
t(S)

and

t−1 (S) := {s : ts ∈ S},

which matches the usual notation for images/preimages if t is regarded as a map from
e to indices in x.
indices in x
Finally, in addition to the standard notation O( · ) and Ω( · ), we also use Op ( · ) and
Ωp ( · ) in cases where the implied constant may depend on p but nothing else.

1.4

Organization of the paper

The rest of the paper is organized as follows. In Sections 2 and 3, we prove the lemmas
needed to for the initial and refined alignment steps, respectively. In Section 4, we
prove the lemmas needed for the reconstruction step. Finally, in Section 5, we pull
together all the ingredients to prove Theorem 1.1.

Acknowledgements
Most of this work was carried out while the second author was visiting Microsoft
Research in Redmond. He thanks Microsoft for the hospitality.

2

Alignment by greedy matching

e) ∼ Dp∗ (x). Given only x and
Suppose we have a string x ∈ {0, 1}n and a sample (t, x
e, it is not in general possible to infer uniquely what t is. However, we may obtain an
x
approximation using a “greedy algorithm” as described in Section 1.2.
To state things precisely, consider any two bit strings x and y. We define a sequence
|y|
(gk (y, x))k=1 as follows:
• Define g1 (y, x) to be the least index such that xg1 (y,x) = y1 . If no bits in x are
equal to y1 , we set g1 (y, x) = ∞.
• For k < |y|, define inductively gk+1 (y, x) to be the least index greater than
gk (y, x) for which xgk+1 (y,x) = yk+1 . If no bits in x after the gk (y, x)-th position
are equal to yk+1 , we set gk+1 (y, x) = ∞. (Note that in particular if gk (y, x) = ∞,
then gk+1 (y, x) = ∞).
e, where x
e is a trace drawn from
We are primarily interested in the case where y = x
Dp (x). In this situation, gk (e
x, x) represents the “earliest possible” place in x that the
e could have come from. For an illustration, we refer back to Figure 1.2.
k-th bit of x
In that picture, we have g1 (e
x, x) = 1, g2 (e
x, x) = 3, g3 (e
x, x) = 6, and g4 (e
x, x) = 8.
6

One may check by a straightforward induction that gk (e
x, x) ≤ tk for all 1 ≤ k ≤
|e
x|. (This means that gk (e
x, x) is never ∞; the possibility of having gk (y, x) = ∞
doesn’t come into play until the proof of Lemma 5.4.) We will show that for retention
x, x) is usually not much less
probability p > 21 and x drawn uniformly at random, gk (e
than tk . The following definition makes this precise.
e) ∼ Dp∗ (x). We say
Definition 2.1. Consider a sequence x ∈ {0, 1}n , and take (t, x
that x is (α, β)-trackable if


λ−α
Px max (tk − gk (e
x, x)) ≥ λ ≤ e− β .
1≤k≤|t|

The main result of this section is the following lemma.
Lemma 2.2. Suppose p > 21 , and let X ∈ {0, 1}n be a uniformly random string of n
bits. There exists Cp > 0 depending only on p such that
 
1
P (X is (Cp log n, Cp )-trackable) ≥ 1 − Op
n
Lemma 2.2 is implied by Theorem 3.2 of [8]. However, many details are omitted
there, so we devote the rest of this section to proving Lemma 2.2 formally. We use the
same general approach, except that it is more natural for us to focus on the quantity
e X) rather than a slightly different quantity considered in [8]. The starting
tk − gk (X,
point is a conditional independence property similar to Lemma 3.3 of [8].
e ∼
Lemma 2.3. Let X ∈ {0, 1}n be drawn uniformly at random, and suppose (t, X)
Dp∗ (X). Then, for any integer k ≥ 1, conditioned on the event |t| ≥ k and the values
of
e X), g2 (X,
e X), . . . , gk (X,
e X),
t1 , t2 , . . . , tk and g1 (X,
the bits Xgk (X,X)+1
, Xgk (X,X)+2
, . . . , Xn are i.i.d. uniformly distributed.
e
e
Remark 2.4. The above lemma also applies when X is an infinite sequence of i.i.d.
uniform bits. In this case, the conclusion is that all of (Xi )∞
are i.i.d. uniform.
e
i=g (X,X)+1
k

Proof. We first condition on t; this conditioning will stay in effect for the remainder
of the proof. Note that all of the Xi are still i.i.d. uniform, since the ti depend only
on which bits are deleted and not on the values of the bits themselves. Since we have
e X) as a deterministic function of X. Therefore,
conditioned on t, we may regard gi (X,
e X).
for brevity we will write gi (X) = gi (X,
Next, fix any sequence S of integers s1 , s2 , . . . , sk where s1 < s2 < · · · < sk and
si ≤ ti for each i. We say a bit string z is S-compatible if gi (z) = si for each i, and let
ES be the event that X is S-compatible.
Consider any two strings w, w0 ∈ {0, 1}n−sk which differ in a single bit. We will
give a bijection between S-compatible realizations of X that end in w and those that
7

end in w0 . This is enough to establish the lemma, since by repeated application, it
shows that any two strings for X(sk +1): are equally likely conditioned on ES , and this
holds for arbitrary S.
To carry out the bijection, for any index j with 1 ≤ j ≤ k, we define its influencing
set to be the set
Ij = {t : sj−1 < t ≤ sj },
with the convention s0 = 0. Informally, it is the set of all indices t where the value of
Xt had some effect on the value of gj (X) (which is equal to sj if X is S-compatible).
For any two indices i and j with 1 ≤ i, j ≤ k, we say i directly influences j if ti ∈ Ij .
Note that because sj ≤ tj , we see that if i influences j, then i ≤ j with equality if and
only if si = ti . We say that i influences j if there is a chain of direct influences from i
to j (i.e. there exist c1 , c2 , . . . , cN such that c1 = i, cN = j, and cα directly influences
cα+1 for α = 1, 2, . . . , N − 1).
Suppose now that we have a S-compatible sequence z that ends in w. We will
describe a way to modify z so that it remains S-compatible but ends in w0 . Let ` be
the index at which w` 6= w`0 . First, suppose that sk + ` 6= ti for any i ≤ k. Then, we
may simply flip the (sk + `)-th bit of z to obtain a S-compatible sequence ending in
w0 .
Otherwise, sk + ` = tm for some m ≤ k. Define the sets
!
[
U = {m} ∪ {j : j influences m}
and
V = {tm } ∪
Ij .
j∈U

We claim that by flipping all the bits of z at positions in V , the resulting sequence
z0 ends in w0 and is S-compatible. The first claim follows from the fact that Ij ⊆
{1, 2, . . . , sk } for all j ≤ k, so the only bit flipped after position sk is the bit at position
tm = sk + `.
To show S-compatibility, we show by induction on j that gj (z0 ) = sj for each j,
where the base case j = 0 is established by the convention g0 (z0 ) = s0 = 0. For the
inductive step, suppose that gi (z0 ) = si for each i < j. We consider two cases.
Case j ∈ U . By the definition of U , either j = m or there exists j 0 ∈ U for which
tj ∈ Ij 0 . In either case, we see that tj ∈ V . We also have by definition that Ij ⊆ V .
By S-compatibility of z, the condition gj (z) = sj says that sj is the first position after
gj−1 (z) = sj−1 having the same value as position tj . In other words, sj is the unique
position in Ij with the same value as position tj .
The bits at positions tj and elements of Ij are all flipped for z0 , so the same property
holds in z0 . Since gj−1 (z0 ) = sj−1 by the inductive hypothesis, we have gj (z0 ) = sj as
well.
Case j 6∈ U . Note that tm > sk , so tm 6∈ Ij . Since j 6∈ U , it follows that Ij is
disjoint from V . Note that if tj ∈ Ij 0 for some j 0 ∈ U , then j directly influences j 0
8

and hence influences m, but this contradicts j 6∈ U . Also, clearly tj 6= tm since j 6= m.
Thus, tj 6∈ V .
We see that none of the bits at positions tj or elements of Ij are flipped for z0 , so
by the same argument as in the previous case, we conclude that gj (z0 ) = sj .
This completes the induction, showing that z0 indeed ends in w0 and is S-compatible.
Furthermore, observe that the set V depends only on S, and so we may symmetrically recover z from z0 by the same transformation. Thus, this gives a bijection from
S-compatible sequences ending in w to those ending in w0 , completing the proof.
The next two lemmas describe how closely gk tracks tk . To avoid boundary issues,
it is convenient to state them for infinite bit sequences.
e ∼
Lemma 2.5. Let X be an infinite sequence of i.i.d. uniform bits, and let (t, X)
∗
e
Dp (X). Define dk = tk − gk (X, X).
Then, dk+1 − dk is independent of d1 , d2 , . . . , dk and has the same law as max(Gp −
G1/2 , −dk ), where Gp and G1/2 are independent geometrics with parameters p and 21 ,
respectively.
e X). We condition on ti and gi for 1 ≤ i ≤ k. By
Proof. For brevity, write gk = gk (X,
∞
Lemma 2.3, the bits (Xi )i=gk +1 are i.i.d. uniform even after this conditioning. Next,
we sample tk+1 , which we may write as tk+1 = tk + Gp since each bit is retained
independently with probability p. We then examine the bits
Xgk +1 , Xgk +2 , . . . , Xtk+1 ,
which are still i.i.d. uniformly distributed. Recall that gk+1 is defined to be the earliest
ek+1 = Xt . Each of the above bits
position of these bits where the value matches X
k+1
has a 12 chance of being a match except for the last one, which is guaranteed to match.
Thus, gk+1 may be written as min(gk + G1/2 , tk+1 ). Consequently,
dk+1 − dk = (tk+1 − tk ) − (gk+1 − gk ) = Gp − min(G1/2 , tk+1 − gk )
= max(Gp − G1/2 , Gp + gk − tk+1 ) = max(Gp − G1/2 , −dk ),
as desired.
Lemma 2.6. Suppose p > 12 . Let X be an infinite sequence of i.i.d. uniform bits, and
e ∼ D∗ (x). Define dk = tk − gk (X,
e X).
let (t, X)
p
Then, there exist positive constants cp and Cp depending only on p such that for
each k, we have
P (dk ≥ λ) ≤ Cp e−cp λ .
Proof. Let Gp and G1/2 be independent geometrics with parameters p and 21 , as in
px
1
Lemma 2.5. Consider the function f (x) = 1−(1−p)x
· 2x−1
, which satisfies f (1) = 1
1
0
and f (1) = p − 2 < 0. Thus, we may take α ∈ (1, 1/p) to be a constant so that
9

f (α) < 1. We will show that E(αdk ) is bounded above uniformly in k, from which the
result immediately follows by Markov’s inequality.
We proceed by induction. For the base case, note that t1 has the distribution of
Gp , and we chose α < 1/p, so E(αGp ) is finite. Since d1 ≤ t1 , it follows that E(αd1 ) is
also finite.
For the inductive step, define γ = f (α) < 1, and let M be a large enough integer
so that
 M
1
1
≤√ .
1 + 2(α − 1)
2α
γ
Note that we have the formulas
E α

Gp



=p

∞
X

pα
1 − (1 − p)α

(1 − p)k−1 αk =

k=1

=
E α

− min(G1/2 ,M )



−M

=2

α

−M

+

M
X

−k

2 α

−k

k=1

1 + 2(α − 1)
=
2α − 1


1 M
2α


=

1
2α

M


1 M
1 1 − 2α
·
+
1
2α
1 − 2α

1
≤√
.
γ(2α − 1)

These calculations allow us to bound two conditional expectations, depending on
whether dk ≥ M . By Lemma 2.5, we have



E αdk+1 | dk ≥ M ≤ E αmax(Gp −G1/2 ,−M ) E αdk | dk ≥ M



≤ E αGp E α− min(G1/2 ,M ) E αdk | dk ≥ M

pα
1
≤
·√
· E αdk | dk ≥ M
1 − (1 − p)α
γ(2α − 1)

√
dk
≤ γ · E α | dk ≥ M


pαM +1
≤ 8αM .
E αdk+1 | dk < M ≤ E αM +Gp =
1 − (1 − p)α
Together, these imply that
 √

E αdk+1 ≤ γ · E αdk + 8αM .
Recall that α, γ, and M are all constants that depend only on p, and γ < 1. Hence,
E αdk is bounded above uniformly in k, completing the proof.
We are finally ready to prove Lemma 2.2.
Proof of Lemma 2.2. For a given string z of n bits and (tz , e
z) ∼ Dp∗ (z), write
d(z) = max (tz,k − gk (e
z, z))

and

1≤k≤|tz |

10

rλ (z) = Pz (d(z) ≥ λ) .

We apply Lemma 2.6 to the sequence X, where we may think of X as the first n bits of
an infinite sequence of i.i.d. uniform bits. Union bounding over all indices 1 ≤ k ≤ n,
we have
E[rλ (X)] ≤ n · C1,p · e−c1,p λ ,
where C1,p and c1,p are constants depending only on p. Consequently,

P rλ (X) ≥ e−c1,p λ/2 ≤ n · C1,p · e−c1,p λ/2 .
Define the event
E=

∞
\

(1)

n
o
r2λ/c1,p (X) ≤ e−λ .

λ=2dlog ne

Then, a union bound using (1) gives
∞
X

P(E) ≥ 1 − n · C1,p

λ=2dlog ne

e−λ ≥ 1 −

C2,p
,
n

(2)

where C2,p is another constant depending only on p.
 t
2
Meanwhile, on the event E, consider any t > c1,p
(2 dlog ne + 1). Let t0 = c1,p
.
2
0
Since t ≥ 2 dlog ne, we have


2t0
0
= r2t0 /c1,p (X) ≤ e−t
P (d(X) ≥ t) ≤ P d(X) ≥
c1,p
≤ e−

c1,p t
+1
2

.

(3)

Combining (2) and (3), we conclude that
P (X is (Cp log n, Cp )-trackable) ≥ 1 −

Cp
n

for a sufficiently large constant Cp .

3

Alignment by seeing a particular sequence

In this section, we develop the tools for our second alignment strategy based on looking
for a particular sequence of consecutive bits. The strategy follows the same main idea
as the use of “anchors” in [5]. However, our analysis is more precise. We first establish
some terminology and notation.
Definition 3.1. For any two bit strings w and y, we say that w occurs in y if there is
some index j such that yj+i−1 = wi for i = 1, 2, . . . , |w|. We use the following notation
to describe occurrences:

11

• Indw (y) denotes the first index at which w occurs in y (i.e. the smallest possible
j as above), or ∞ if w does not occur in y.
• Whenever Indw (y) < ∞,
IndSetw (y) := {j : Indw (y) ≤ j < Indw (w) + |w|}
denotes the set of all the indices in y corresponding to the occurrence of w in y.
In later sections, we will be interested in occurrences of w within a particular substring yi:j of y. However, we still want to work with indices based on position in y
rather than in yi:j . In these cases, we use the notation
i:j
• Indi:j
w (y) := Indw (y ) + i − 1.
i:j
i:j
• IndSeti:j
w (y) := {k : Indw (y) ≤ k < Indw (w) + |w|}.

Suppose that x is a string of length 2n, and w = x(n−a+1):(n+a) is a substring in the
e ∼ Dp (x), and we see that w occurs in
middle of x. Now, suppose we observe a trace x
e. We would like to say that in this case the bits in x
e corresponding to the occurrence
x
of w likely came from the occurrence of w in x (or at least, some of them did). Not all
strings x have this property, but as we will see shortly, it turns out that typical ones
do. We formalize the property in the following definition.
e) ∼ Dp∗ (x). Consider a
Definition 3.2. Suppose p > 12 , let x ∈ {0, 1}2n , and take (t, x
positive integer a ≤ n and positive real γ < 1, and write w = x(n−a+1):(n+a) . We say
that x is (a, γ)-distinguishable if


Px Indw (e
x) < ∞ and t(IndSetw (e
x)) ∩ [n − a, n + a] = ∅ ≤ γ a · p2a .
e if each of the positions n − a + 1
Remark 3.3. It is always possible for w to occur in x
through n + a in x are retained. This happens with probability p2a . The bound on the
probability in the above definition is given in the form γ a · p2a to highlight that it should
be smaller than p2a by a factor that is exponential in a.
The main result of this section is that random sequences are likely to be distinguishable.
Lemma 3.4. Suppose p > 21 , and suppose X ∈ {0, 1}2n is chosen uniformly at random.
Then, there exist γp < 1 and cp > 0 depending only on p such that



1/2
P X is ( n1/2 , γp )-distinguishable ≥ 1 − e−cp n .

12



e ∼ D∗ (X). Let
Proof. Let a = n1/2 , let w = X(n−a+1):(n+a) , and take (t, X)
p

 n
o
e
tj 6∈ [n − a, n + a]
J = t−1 [1, 2n] \ [n − a, n + a] = j : 1 ≤ j ≤ |X|,
e which did not come from the middle 2a positions of X.
denote the set of indices of X
Define the event
n
o
e
e
E = Indw (X) < ∞ and t(IndSetw (X)) ⊆ J ,
which is the relevant event for (a, γ)-distinguishability.
Let us condition on the middle 2a bits of X (i.e. the bits that form w) as well as
ej )j∈J are still i.i.d. uniform after our conditioning.
on t. The key observation is that (X
e but t(IndSetw (X))
e ⊆ J, then it means that w occurs in the
Now, if w occurs in X,
ej )j ∈ J . However, since the (X
ej )j∈J are i.i.d., in each possible position this
sequence (X
only happens with probability 2−|w| = 2−2a . Union bounding over at most 2n positions
yields
P(E) ≤ 2n · 2−2a ,
where we have also taken the expectation over our initial conditioning on the middle
2a bits and t.
The above probability is with respect to simultaneously two sources of randomness:
the random choice of X and the random choice of the deletions. To highlight this,
recall the notation Px for the probability over the randomness of the deletion channel
for a given input string x.
Take γp = (2p)−1/2 < 1. By Markov’s inequality,
P(PX (E) ≥ γpa · p2a ) ≤ γp−a · p−2a · E(PX (E)) = γp−a · p−2a · P(E)
1/2 )

≤ 2n · γp3a = e−Ωp (n

,

which yields (a, γp )-distinguishability with the desired probability.


We conclude the section by establishing a consequence of ( n1/2 , γp )-distinguishability
that is more convenient to work with than Definition 3.2.


Lemma 3.5. Suppose p > 21 , let a = n1/2 , and suppose x ∈ {0, 1}2n is (a, γp )e) ∼ Dp∗ (x).
distinguishable for some constant γp < 1 depending only on p. Consider (t, x
Then,


Px Indw (e
x) < ∞ and t(IndSetw (e
x)) 6⊆ [n − 10a, n + 10a] ≤ e−Ωp (a) · p2a .
Proof. The main idea is that if the set t(IndSetw (e
x)) intersects the interval [n−a, n+a],
then it is unlikely to stretch out very far from that interval.
Let
n
o
E1 = Indw (e
x) < ∞ and t(IndSetw (e
x)) ∩ [n − a, n + a] = ∅ ,
13

so that (a, γp )-distinguishability ensures Px (E1 ) ≤ γpa p2a .
Next, let


more than 7a deletions occurred among
E2 =
.
some 9a consecutive positions in x
By a standard Chernoff bound (see, e.g., [4]) and union bounding over all blocks of 9a
bits in x, we have
25a2

Px (E2 ) ≤ 2n · P (Binom(9a, 1/2) > 7a) ≤ 2n · e− 18a
≤ 2n · 4−a ≤ e−Ωp (a) · p2a .
Finally, let
E3 =

n

o
Indw (e
x) < ∞ and t(IndSetw (e
x)) 6⊆ [n − 10a, n + 10a] ,

which is the event of interest for the lemma. Suppose now that E1 holds but not E3 ,
i.e. t(IndSetw (e
x)) is not disjoint from [n − a, n + a] but is also not contained within
[n − 10a, n + 10a]. Then t(IndSetw (e
x)) must have two elements which are at least 9a
apart, so that E2 holds. Thus, we find that
Px (E3 ) ≤ Px (E1 ) + Px (E2 ) ≤ e−Ωp (a) · p2a .

4

Reconstruction from approximate alignment

In this section, we adapt the trace reconstruction methods of [9] and [3] to a setting
where the input string also undergoes a random shift. The main result of this section
is the following lemma.
Lemma 4.1. Let k, n, and N be positive integers with k < n < N . Let x, x0 ∈ {0, 1}N
be two strings whose first k digits are identical but whose first n digits are not. Let S
be a random variable taking integer values between 0 and k − 1.
Suppose the following conditions are satisfied:
E[|S − ES|] ≤ n1/3 ,

k ≤ n2/3 .

Then, for some constant Cp depending only p, there exists an index j ≤ Cp n such that
e ∼ Dp (x(S+1): ) and x
e0 ∼ Dp ((x0 )(S+1): ), then
if x

Px (e
xj = 1) − Px0 (e
x0j = 1) ≥ exp −Cp n1/3 .
The first ingredient in the proof of this lemma is a polynomial identity, which is
analogous to Lemma 2.1 in [9] or Section 4 in [3], but accounts for possible shifts to
the input sequence.
14

Lemma 4.2. Let n and k be positive integers with k ≤ n. Let a = (a0 , a1 , . . . , an−1 ) be
a sequence of real numbers whose first k elements are zero. Let S be a random variable
taking integer values between 0 and k − 1, with P(S = i) = βi .
Let e
a ∼ Dp (a(S+1): ), and pad e
a with zeroes to the right. Then,
"
#
! n−1
!
k−1
X
X
X
E
e
aj w j = p
βs (pw + q)−s
aj (pw + q)j .
(4)
s=0

j≥0

j=0

Proof. Let ` be any integer with k ≤ ` ≤ n − 1. By linearity, it suffices to show the
result for a having all zeroes except a` = 1. We now restrict to this case.
Let us condition on S = s and analyze for each j the probability P(e
aj = 1) that
the single non-zero entry a` gets shifted to position j without being deleted. Clearly, if
j > ` − s, then P(e
aj = 1 | S = s) = 0. Otherwise, the probability must account for the
retention of a` and the retention of exactly j of the first ` − s entries of a(s+1): . Note
that the condition k ≤ ` ensures that ` − s > 0. Thus for j ≤ ` − s,


` − s j `−s−j
P (e
aj = 1 | S = s) = p ·
pq
,
j
so that
!
E

X

e
aj w

j

S=s

=p


`−s 
X
`−s
j=0

j≥0

j

pj q `−s−j wj = p · (pw + q)`−s .

Taking the expectation over S, we conclude that
! k−1
!
k−1
X
X
X
X
j
j
E
βs E
βs (pw + q)`−s
e
aj w =
e
aj w S = s = p
s=0

j≥0

=p

s=0

j≥0
k−1
X

!
βs (pw + q)−s

(pw + q)` ,

s=0

which completes the proof.
As in [9] and [3], we also use the following Littlewood-type estimate of Borwein and
Erdélyi.
Lemma 4.3 (Borwein and Erdélyi, special case of Corollary 3.2 in [2]). There exists
a finite constant C such that the following holds. Let A(z)
 iθ be a polynomial with coefficients in [−1, 1] and A(0) = 1. Denote by γL the arc e : −1/L ≤ θ ≤ 1/L . Then
maxz∈γL |A(z)| ≥ e−CL .
We now carry out the proof of Lemma 4.1 using these two ingredients.

15

Proof of Lemma 4.1. For a fixed value of p, clearly it is enough to prove the statement
for sufficiently large n. We will assume implicitly at various points that n is sufficiently
large.
Write βj = P(S = j), let aj = xj+1 − x0j+1 , and let a = (aj )n−1
j=0 . Define the
polynomials
P (z) =

k−1
X

j

βj z ,

Q(z) =

j=0

n−1
X

aj z j ,

and A(z) = p · P (z −1 )Q(z).

j=0

Let ` be the smallest index for which a` 6= 0; note that by our hypotheses, ` ≤ n.
e
e
= 1.
Define Q(z)
= z1` Q(z), so that |Q(0)|
1/3
For convenience, let L = n , and define ρ = 1 − 1/L2 . Applying Lemma 4.3 to
p
p
e
e 0 )| ≥ e−CL/p .
the function Q(ρz),
there exists z0 = eiθ with − 10L
≤ θ ≤ 10L
and |Q(ρz
We next lower bound |P (ρ−1 z0−1 )|. Let Pe(z) = z −ES P (z), which is an analytic
function on the right half-plane. For all z in the right half-plane satisfying 1 ≤ |z| ≤
ρ−1 , differentiating Pe gives
|Pe0 (z)| =

k−1
X

(j − ES)βj z

j−ES−1

≤

k−1
X

|j − ES| · |z|j−ES−1

j=0

j=0

1.1k

≤ ρ−k · E[|S − ES|] ≤ ρ−k L ≤ e L2 · L ≤ 4L,
where we have used E[|S − ES|] ≤ L and k ≤ L2 . Also,
|ρ−1 z0−1 − 1| = ρ−1 |1 − ρz0 | ≤ |z0 − 1| + ρ−1 (1 − ρ)
p
2
p
≤
+ 2 ≤
.
10L L
8L
Consequently,
|P (ρ−1 z0−1 )| = ρ−ES |Pe(ρ−1 z0−1 )| ≥ 1 − |Pe(ρ−1 z0−1 ) − 1|
Z ρ−1 z0−1
Pe0 (z) dz ≥ 1 − |ρ−1 z −1 − 1| · 4L
=1−
0

1

≥1−

1
p
≥ .
2
2

Thus,
(C+2)L
− CL
−
e 0 )| ≥ p · e− 1.1n
p ≥ e
p
L2
|A(ρz0 )| = p · |P (ρ−1 z0−1 )| · ρ` · |Q(ρz
.
2

16

Next, define w = 1 +

ρz0 −1
,
p

so that ρz0 = pw + q. We have that

2
1
|w|2 = 1 + (ρ · Re(z0 ) − 1) + 2 |ρz0 − 1|2
p
p
2
2
ρ
≤ 1 + (ρ − 1) + 2 |ρ−1 z0−1 − 1|2
p
p
2
1
≤1− 2 +
≤ ρ.
L
64L2
Let e
a ∼ Dp (a(S+1): ). By Lemma 4.2,
"
#
X
(C+2)L
E
e
aj wj = |A(ρz0 )| ≥ e− p .
j≥0

Now, take Cp to be an integer larger than
∞
X

E[e
aj ]w

j

≤

∞
X

C+4
.
p

Note that

ρ j ≤ L 2 ρ Cp n ≤

j=Cp n

j=Cp n

1 − (C+2)L
p
.
·e
2

Hence,
E

"Cp n−1
X

#
e
aj w j

j=0

≥

1 − (C+2)L
p
≥ e−(Cp −1)L ,
·e
2

and therefore, we must have for some j with 0 ≤ j ≤ Cp n − 1 that
P(e
xj = 1) − P(e
x0j = 1) = |Ee
aj | ≥ |Ee
aj wj |
≥

1 −(Cp −1)L
e
≥ e−Cp L ,
Cp n

as desired.

5

Proof of Theorem 1.1

Throughout this section, we fix a deletion probability q < 12 (and hence a retention
probability p > 21 ). In addition, all of our inequalities are meant to apply for n
sufficiently large (i.e. larger than a constant depending only on p).
Let Cp be the larger of the two constants in Lemmas 2.2 and 4.1, and let cp be the
constant in Lemma 3.4. We define the following integers:


l
m
10 1/2
1/2
K log n .
M = dCp log ne ,
K1 = 40M,
K 0 = K1
,
K2 =
cp 1
17

It is helpful to keep in mind that K0 = Θp (log1/2 n), K1 = Θp (log n), and K2 =
Θp (log3/2 n).
Recall the high-level strategy of the proof from Section 1.2: we align traces against
what we have reconstructed so far, and then we use bit statistics to reconstruct additional bits. The alignment step in particular relies on the input X having certain
special properties which don’t hold for all strings but do hold for “most”. We encapsulate these properties in the following definition.
Definition 5.1. Let γp < 1 be the constant from Lemma 3.4. We say that a string
x ∈ {0, 1}n is good if the following conditions are satisfied:
(i). x is (M, Cp )-trackable,
(ii). there is no run of M consecutive identical bits in x,
(iii). among any K2 consecutive bits of x, there is a block of 2K1 of them that is
(K0 , γp )-distinguishable.
As the next lemma shows, a random string is good with high probability.
Lemma 5.2. Let X ∈ {0, 1}n be drawn uniformly at random. Then,
 
1
.
P(X is good) ≥ 1 − Op
n
Proof. It suffices to show that each condition in 5.1 holds with probability at least
1 − Op n1 . For condition (i), this is immediate by Lemma 2.2.
To establish condition (ii), note that the probability for M i.i.d. uniform bits to be
identical is 21−M . Union bounding over all blocks of M consecutive
 bits in X, we find
1
1−M
that (ii) holds with probability at least 1 − n · 2
≥1−O n .
Finally, for condition (iii), note that any K2 consecutive bits contain at least
√ n disjoint blocks of size 2K1 . By Lemma 3.4, the probability that a
bK2 /2K1 c ≥ c2plog
K1
√

single block fails to be (K0 , γp )-distinguishable is at most e−cp K1 . Thus, the probability that none of these blocks is (K0 , γp )-distinguishable is at most

p 
2 log n
1
exp − √
· cp K 1 = 2 .
n
cp K 1
Union bounding over at most n possible blocks of K2 consecutive
bits shows that

condition (iii) also holds with probability at least 1 − O n1 .

5.1

Alignment

Suppose x is a bit string that we know, and let m ≤ |x| be some position in x. Suppose
e from the deletion channel applied to x (or some longer
that we also have a sample x
string having x as a prefix). As described in Section 1.2, we would like to identify
e that was originally positioned near the m-th bit of
(with high probability) a bit of x
x. This motivates the following definition.
18

Definition 5.3. An alignment rule is a function L which takes as input a bit string
x, an index m ≤ |x|, and another bit string y. It outputs a value L(x, m, y) ∈
{1, 2, . . . , |y| − 1, |y|, ∞}.
In addition, we require that L satisfy the following adaptedness property with respect
to y: whenever L(x, m, y) < ∞, for any other string y0 identical to y in their first
L(x, m, y) bits, we have L(x, m, y0 ) = L(x, m, y).
Let us explain the conceptual meaning of this definition. Although it is not strictly
required for the definition, we emphasize that for our purposes, y will be a sample
from the deletion channel applied to a string whose prefix is x. The idea is that bits
near the m-th position of x should end up near the L(x, m, y)-th position in y after
going through the deletion channel; in this way, the position m in x is “aligned” with
position L(x, m, y) in y. When L(x, m, y) = ∞, it means that the rule cannot reliably
locate which bits of y came from around the m-th position of x.
The adaptedness condition says that an alignment rule must proceed by examining
the bits of y in order one by one, and either outputting the current position or giving
up and outputting ∞. In particular, we do not allow alignment rules to look ahead in
the string y before deciding whether a previous position should be the output. The
purpose of this requirement is to ensure that the deletion pattern after our alignment
position is independent of the alignment itself.
The next lemma constructs a particular alignment rule that has good quantitative
bounds on the quality of the alignment.
Lemma 5.4. Let k be a given integer with K2 ≤ k ≤ n/2, and let x0 ∈ {0, 1}k be a
string of length k. Then, there exists an index m with k − K2 + K1 ≤ m ≤ k − K1 and
an alignment rule L with the following property:
e) ∼ Dp∗ (x), we
For any good sequence x ∈ {0, 1}n with x0 as a prefix, taking (t, x
have
e) < ∞) ≥ 21 p2K0
(i). Px (L(x0 , m, x
e) < ∞) ≤ n−Ω(1)
(ii). Px (|tL(x0 ,m,ex) − m| ≥ K1 | L(x0 , m, x
e) < ∞) ≤ e−Ωp (K0 ) .
(iii). Px (|tL(x0 ,m,ex) − m| ≥ 10K0 | L(x0 , m, x
Informally speaking, the properties in the above lemma should be interpreted as
saying that (i) the alignment succeeds with some not-too-small probability; (ii) it is
extremely likely to align within K1 of the correct position; and (iii) it usually aligns
within 10K0 . Before giving the proof, we first establish an auxiliary lemma.
e) ∼ Dp∗ (x).
Lemma 5.5. Suppose x ∈ {0, 1}n is a good sequence, and suppose (t, x
Consider any k ≤ n/2, and let ` be the smallest index such that g` (e
x, x) ≥ k. Then,


1
Px ` exists and k ≤ t` ≤ k + 4M ≥ 1 −
n
for all sufficiently large n.
19



e is
Proof. Let n0 = 65 · pn . If ` does not exist, it means that g|ex| (e
x, x) < k (or x
empty). This can be bounded by
Px (` does not exist) ≤ Px (|e
x| < n0 ) + Px (gn0 (e
x, x) < n/2)
0
≤ Px (|e
x| < n ) + Px (tn0 − gn0 (e
x, x) ≥ n/6) + Px (tn0 < 2n/3).

(5)

Note that |e
x| is distributed as Binom(n, p), so Px (|e
x| < n0 ) = e−Ωp (n) . The second
term in (5) is at most e−Ω(n) because x was assumed to be (M, Cp )-trackable. Finally,
if tn0 < 2n/3, it means that at least 5pn/6 out of the first 2n/3 bits were retained,
which also occurs with probability at most e−Ωp (n) . Thus, all three probabilities in (5)
are exponentially small in n, so
Px (` does not exist) ≤

1
n2

(6)

for large enough n.
We now work under the assumption that ` exists. We always have
t` ≥ g` (e
x, x) ≥ k

(7)

Since x does not have more than M consecutive identical bits, by the minimality of `,
we must have g` (e
x, x) ≤ k + M . By (M, Cp )-trackability of x, we have
Px (t` > k + 4M ) ≤ Px (t` − g` (e
x, x) > 3M ) ≤

1
.
n2

(8)

Combining (6), (7), and (8) completes the proof.
Proof of Lemma 5.4. If x0 is not a prefix of any good sequence, then there is nothing
to prove. Otherwise, because x0 is a prefix of a good sequence, there must exist m with
(m−K1 +1):(m+K1 )
k − K2 + K1 ≤ m ≤ k − K1 such that x0
is (K0 , γp )-distinguishable. We
(m−K0 +1):(m+K0 )
choose such an m and let w = x0
(see Figure 5.1).
e) ∼ Dp∗ (x).
Now, suppose x is any good sequence having x0 as a prefix, and take (t, x
Roughly speaking, our alignment rule will be to first use Lemma 5.5 to identify an index
e such that t`0 is slightly smaller than m. Then, we will look for an occurrence of
`0 in x
e shortly after position `0 . If such an occurrence exists, we output the position
w in x
of the last bit of the occurrence. If not, we output ∞.
To specify the alignment rule precisely, consider any string y, and define the statement
P0 (y) = “there exists ` such that ∞ > g` (y, x0 ) ≥ m − 8M ”.2
Whenever P0 (y) holds, take `0 (y) to be the smallest such `. Then, define
P1 (y) = P0 (y) ∧ “Ind`w0 (y):(`0 (y)+16M ) (y) < ∞”.
2

Recall that since y need not be drawn from Dp (x0 ), it is possible to have g` (y, x0 ) = ∞.

20

x0
k − K2

k

n

w
m − K1

m

m + K1

Figure 5.1: Illustration of positions involved in the proof of Lemma 5.4.

We then define our alignment rule to be
(
Ind`w0 (y):(`0 (y)+16M ) (y) + 2K0 − 1 if P1 (y) holds
L(x0 , m, y) =
∞
otherwise.
Note that this satisfies the adaptedness requirement for alignment rules. We will specife, so it is convenient to define the events
ically apply the above definition with y = x
E0 = {P0 (e
x) holds},

E1 = {P1 (e
x) holds},

and we abbreviate `0 = `0 (e
x).
Next, we establish properties (i), (ii), and (iii). In what follows, the reader may
find it helpful to refer to Figure 5.2. Define
F0 = E0 ∩ {m − 8M ≤ t`0 ≤ m − 4M }.
By Lemma 5.5, we have
1
(9)
n
We note a subtlety in our use of the lemma: the event E0 concerns existence of g` (e
x, x0 ),
while Lemma 5.5 concerns existence of g` (e
x, x). However, as long as t`0 ≤ m − 4M ,
the relevant indices are all less than k, so there is no difference between using x0 and
using x, and the lemma still applies.
e) < ∞) = Px (E1 ). Conditioned on F0 , it is
We can now lower bound Px (L(x0 , m, x
always possible for E1 to occur by retaining all the bits in positions m − K0 + 1 through
m + K0 in x. Thus,
Px (F0 ) ≥ 1 −

1
e) < ∞) = Px (E1 ) ≥ Px (F0 ) · p2K0 ≥ p2K0 ,
Px (L(x0 , m, x
2
establishing property (i).
To show property (ii), consider the event
F1 = {t`0 +16M ≤ m + K1 }.
21

m − K1

t`0

m

t`0 +16M

m + K1

x0
w
[m − 8M, m − 4M ]
e
x
`0

w

`0 + 16M

L(e
x, m, x0 )
e. In the diagram above, events F0 , F1 , and E1
Figure 5.2: A possible configuration for x0 , m, and x
all hold.

Note that if F0 and F1c both occur, then it means that fewer than 16M bits were retained
among the positions in x between m − 4M and m + K1 . There are K1 + 4M = 44M
such positions, so
Px (F0 ∩ F1c ) ≤ Px (Binom(44M, p) < 16M ) ≤ e−Ω(M ) = n−Ω(1) .

(10)

If F0 , F1 , and E1 all occur, then we have
tL(x,m,ex) ≥ t`0 ≥ m − 8M ≥ m − K1
tL(x,m,ex) ≤ t`0 +16M ≤ m + K1 .
Thus,




Px |tL(x,m,ex) − m| ≤ K1 E1 ≥ Px (F0 ∩ F1 | E1 ) ≥ 1 −

Px (F0c ) + Px (F0 ∩ F1c )
Px (E1 )

≥ 1 − n−Ω(1) ,
establishing property (ii).
Finally, we show property (iii). Let
I = t−1 ({m − K1 + 1, m − K1 + 2, . . . , m + K1 })
(m−K +1):(m+K )

1
e which “came from” x0 1
be the set of indices in x
. Note
 that we can regard
(m−K1 +1):(m+K1 )
(e
xi )i ∈ I in increasing order as being drawn from Dp x0
. Consider the event

n 

o
F2 = E1 ∩ t IndSet`w0 :(`0 +16M ) (e
x) ⊆ [m − 10K0 , m + 10K0 ] .
Note that we have the implication


`0 :(`0 +16M )
t IndSetw
(e
x) 6⊆ [m − 10K0 , m + 10K0 ]
22

and

[`0 : (`0 + 16M )] ⊆ I


x) 6⊆ [m − 10K0 , m + 10K0 ],
=⇒ t IndSetIw (e
which means



x) 6⊆ [m − 10K0 , m + 10K0 ]
Px (F2c ∩ (F0 ∩ F1 ∩ E1 )) ≤ Px t IndSetIw (e
≤ e−Ωp (K0 ) · p2K0 ,

(11)
(m−K +1):(m+K )

1
1
where the last inequality follows from the fact that x0
is (K0 , γp )-distinguishable
combined with Lemma 3.5.
Recall from property (i) that Px (E1 ) ≥ 21 p2K0 . We conclude that


Px |tL(ex) − m| ≤ 10K0 E1 ≥ Px (F0 ∩ F2 | E1 )

Px (F0c ) + Px (E1 ∩ F0 ∩ F1c ) + Px (E1 ∩ F0 ∩ F1 ∩ F2c )
Px (E1 )
−Ω(1)
−Ω(1)
−Ωp (K0 )
≥1−n
−n
−e
= 1 − e−Ωp (K0 ) ,
≥1−

where we have used (9), (10), and (11) to bound the numerator appearing in the second
line. This proves (iii).

5.2

Reconstruction

The following lemma provides a template for how we will reconstruct bits.
Lemma 5.6. Consider integers k1 and k2 with k1 < k2 , and let S ⊆ {0, 1}k2 be a
known set of length-k2 bit strings. Suppose that we have a number  > 0 and a family
of statistics bj : S → R for 1 ≤ j ≤ k2 which satisfies the following property: for any
two strings w, w0 ∈ S whose first k1 bits are not identical, there exists an index jw,w0
such that |bjw,w0 (w) − bjw,w0 (w0 )| > .
2
Let z ∈ S be an unknown string, and suppose that we observe estimates (b̂j )kj=1
such
that |b̂j − bj (z)| < /2 for each j. Then, we can determine the first k1 bits of z.
Proof. For any two strings w, w0 ∈ S whose first k1 bits are not identical, we say that
w beats w0 if b̂jw,w0 is closer to bjw,w0 (w) than to bjw,w0 (w0 ). We say w is dominant if
it beats all other strings w0 ∈ S that do not share its first k1 bits.
Our hypotheses imply that z is dominant. Moreover, any two dominant strings
must share their first k1 bits. Thus, we may recover the first k1 bits of z as the first k1
bits of any dominant string.
We now apply the template in two lemmas. The first lemma shows how to reconstruct the initial K2 bits, and the second lemma shows how to reconstruct additional
bits once we have already reconstructed a long enough prefix of x.

23

Lemma 5.7. Let x ∈ {0, 1}n be a good sequence. There is a constant Cp0 depending only


√
on p such that N = exp Cp0 log n independent samples from Dp (x) are sufficient
to recover the first K2 bits of x with probability at least 1 − n1 for all sufficiently large
n.
e1 , . . . , x
eN be the sampled traces. For each j ≤ n, let
Proof. Let x
x
eavg
j

N
1 X
=
x
ei,j
N i=1

ei at position j, where x
ei are padded to the right with
be the average of the bits of the x
zeroes.
We will apply Lemma 5.6 with k1 = K2 and k2 = n. We consider statistics bj (z)
equal to the expected value
of the j-th bit of a string drawn from Dp (z). By Lemma

1/3
1/2
−Op K2
4.1, we may take  = e
= e−Op (log n) .
Choose Cp0 sufficiently large so that 2 N ≥ e
a Chernoff bound we have

√

log n

. Noting that E[e
xavg
j ] = bj (x), by

− bj (x)| > /2) ≤ e−
Px (|e
xavg
j

2 N
2

≤

1
n2

for all large enough n. Thus, letting
E = {|e
xavg
− bj (x)| ≤ /2 for each j}
j
and union bounding over all 1 ≤ j ≤ n, we have Px (E) ≥ 1 − n1 .
Using b̂j = x
eavg
as our estimates, Lemma 5.6 asserts that we can recover the first
j
K2 bits of x on the event E, which proves the desired statement.
Lemma 5.8. Let n be a positive integer, and let k be an integer with K2 ≤ k ≤ n/2.
There is a constant Cp0 depending only on p such that the following holds:


√
Consider a good sequence x ∈ {0, 1}n , and suppose that N := exp Cp0 log n
e1 , . . . , x
eN are drawn from Dp (x). Then, whenever n is sufficiently large,
i.i.d. samples x
e1 , . . . , x
eN is sufficient to recover the
seeing only the first k bits of x and the traces x
1
(k + 1)-th bit of x with probability at least 1 − n2 .
Proof. Let m and L be the index and alignment rule given by Lemma 5.4, where we
take x0 = x1:k to be the first k bits of x (which we have been given). Let us consider
e ∼ Dp (x). For brevity, write ` = `(e
e).
a single trace x
x) = L(x0 , m, x
e is a usable trace if ` < ∞. Let E denote the event that x
e is usable,
We say that x
and let
E 0 = E ∩ {m − K1 ≤ t` ≤ m + K1 }
E 00 = E ∩ {m − 10K0 ≤ t` ≤ m + 10K0 }.

24

Lemma 5.4 ensures that Px (E 0 | E) ≥ 1 − n−Ω(1) and Px (E 00 | E) ≥ 1 − e−Ωp (K0 ) , which
taken together imply that
Px (E 00 | E 0 ) ≥ 1 − e−Ωp (K0 ) = 1 − e−Ωp (log

1/2

n)

.

(12)

Let H = m − K1 , and let ∆ be a random variable having the same distribution
as t` − H conditioned on E 0 . The reason for defining ∆ in this particular way will be
made clearer shortly. For now, let us take note of several properties of ∆:
• ∆ is an integer between 0 and 2K1 .
• The distribution of ∆ can be calculated just by looking at x0 (in particular, it
does not depend on bits of x after the k-th one).3
• By (12), it is straightforward to deduce that E∆ = m+Op (K0 ) and E[|∆−E∆|] =
Op (K0 ).
m
l
Define K3 = Cp00 log3/2 n , where Cp00 is a large enough constant to ensure that
1/3

E[|∆ − E∆|] ≤ K3 ,

2/3

2K1 ≤ K3 ,

and K3 > K2 .

Our goal will be to distinguish the true suffix x(H+1): from other possible suffixes via
Lemma 5.6, where we take (k1 , k2 ) = (K3 , n − H). Here, the set S is taken to be all
strings of length n − H having x(H+1):k as a prefix. By reconstructing the first K3 bits
of x(H+1): , we will have in particular reconstructed xk+1 , since
H + K3 = m − K1 + K3 > k + 1.
The statistics we use are, for any z ∈ S,
bj (z) := expected value of the j-th bit of a string drawn from Dp (z(∆+1): ),
1/3

1/2

and we take  = e−Cp K3 (it may be helpful to keep in mind that  = e−Θp (log n) ).
Note that we are able to compute these quantities bj (z) since we are able to compute
the distribution of ∆.
Let us first verify the property required of the bj and  in Lemma 5.6. Consider any
two strings w, w0 ∈ S that do not agree in their first K3 bits. We apply Lemma 4.1
to these strings with (k, n, S) = (2K1 , K3 , ∆). To check the hypotheses of the lemma,
note that by the definition of S and the assumption m ≤ k − K1 , w and w0 agree in
their first k − H = k + K1 − m ≥ 2K1 bits, as required. We also recall that by the way
we defined K3 , the conditions
1/3

E[|∆ − E∆|] = Op (K0 ) ≤ K3 ,
3

2/3

2K1 ≤ K3

It should be noted that the probability Px (E) of having a usable trace does depend on later bits
of x. However, the additional constraint m − K1 ≤ t` ≤ m + K1 combined with the adaptedness
property of L removes this dependence.

25

are satisfied. Thus, Lemma 4.1 tells us that there exists an index jw,w0 for which
1/3

|bj (w) − bj (w0 )| ≥ e−Cp K3

= ,

establishing that our choice of bj and  are suitable for use in Lemma 5.6.
Unfortunately, we cannot directly observe samples with the law of Dp (x(H+1+∆): ) in
e allows us to sample from this
order to estimate bj (x(H+1): ). However, a usable trace x
e (as required in Definition
distribution approximately. The fact that L is adapted to x
e(`+1): has the
5.3) means that if we condition on t`(ex) = h for some index h, the string x
(h+1):
same distribution as Dp (x
). Thus, the definition of ∆ ensures that, conditioned
0
(`+1):
e
on the event E , x
has exactly the law of Dp (x(H+1+∆): ).
e is usable, we define b̂j (e
e`+j and bj = E(b̂j (e
As long as x
x) := x
x) | E). The above
discussion implies that
bj − bj (x(H+1): ) ≤ Px (E 0c | E) ≤ n−Ω(1) ≤ /4,

(13)

where the bound on Px (E 0c | E) comes from Lemma 5.4.
e1 , . . . , x
eN will then give us a fairly good estimate on
Averaging over our N traces x
(H+1):
0
bj (x
). Choose Cp large enough so that the following hold:
1 2K0
p N ≥ 2N 2/3
2
√
=⇒ N 2/3 2 = eΩ( log n) .

N ≥ 64p−6K0 =⇒
√

N ≥ −3 e

log n

(14)
(15)

Let M be the number of usable traces. Since our alignment rule ensures that the
probability of being usable is at least 12 p2K0 , it follows by a Chernoff bound and (14)
that




√
2N 4/3
1
2/3
Ω( log n)
Px (M < N ) ≤ exp −
= exp −2e
≤ 3.
N
n
Define
X
1
=
b̂avg
b̂j (e
xi ).
j
M
ei is usable
x

By another Chernoff bound and (15),




−N 2/3 2
avg
2/3
Px |b̂j − bj | > /4 ≤ Px (M < N ) + exp −
8


√
1
1
≤ 3 + exp −eΩ( log n) ≤ 2 .
n
n
Combining (13) and (16), we conclude that


1
(H+1):
Px |b̂avg
−
b
(x
)|
<
/2
for
all
j
≤
n
≥ 1 − 2.
j
j
n

(16)

Thus, with probability at least 1 − n12 , the conclusion of Lemma 5.6 allows us to
determine the first K3 bits of x(H+1): . As noted earlier, this includes the (k + 1)-th bit
of x, as desired.
26

5.3

Completing the proof

We are finally ready to prove Theorem 1.1, which is mostly a matter of combining
Lemmas 5.7 and 5.8.


√
Proof of Theorem 1.1. We sample N = exp Cp0 log n traces, where Cp0 is large
enough so that Lemmas 5.7 and 5.8 apply.
We first condition on a realization X = x, and suppose that x is good. We will
construct a string x̂ = (x̂1 , x̂2 , . . . , x̂n ). Let Ek denote the event that x̂ matches x in
the first k bits. We construct the first K2 bits of x̂ using Lemma 5.7, which yields
Px (EK2 ) ≥ 1 −

1
.
n

(17)

Next, consider any k with K2 ≤ k ≤ n/2, and suppose we have constructed
x̂1 , . . . , x̂k already. We apply the algorithm of Lemma 5.8 and set x̂k+1 to its output. Although we do not have access to the first k bits of x, we use the first k bits
of x̂ instead. As long as Ek holds, this will give us the correct value for x̂k+1 with
probability at least 1 − n12 . Thus,
Px (Ek+1 ) ≥ Px (Ek ) −

1
.
n2

(18)

Using (17) followed by repeated applications of (18), we find that
Px (Edn/2e ) ≥ 1 −

1
.
n

By symmetry, we can repeat the same procedure in reverse to reconstruct the last
dn/2e bits of x. Accounting for both the forward and reverse steps, the probability of
failure is at most n2 .
The final possible mode of failure is if x is not good. However, by Lemma 5.2,
X with
this only happens with probability at most n1 . In total, we can reconstruct
√
3
Op ( log n)
probability at least 1 − n . Moreover, we have only used N = e
traces. This
completes the proof.

References
[1] Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Proceedings of the Fifteenth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 910–918. Society
for Industrial and Applied Mathematics, 2004.
[2] P. Borwein and T. Erdélyi. Littlewood-type problems on subarcs of the unit circle.
Indiana Univ. Math. J., 46(4):1323–1346, 1997.
27

[3] Anindya De, Ryan O’Donnell, and Rocco Servedio. Optimal mean-based algorithms for trace reconstruction. In Proceedings of the Forty-ninth Annual ACM
Symposium on the Theory of Computing (STOC), pages 1047–1056. Association
for Computing Machinery, 2017.
[4] Wassily Hoeffding. Probability inequalities for sums of bounded random variables.
J. Amer. Statist. Assoc., 58:13–30, 1963.
[5] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.
Trace reconstruction with constant deletion probability and related results. In
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 389–398. Society for Industrial and Applied Mathematics,
2008.
[6] Sampath Kannan and Andrew McGregor. More on reconstructing strings from
random traces: insertions and deletions. In Proceedings of the International Symposium on Information Theory (ISIT), pages 297–301. IEEE, 2005.
[7] Andrew McGregor, Eric Price, and Sofya Vorotnikova. Trace reconstruction revisited. In Algorithms-ESA, pages 689–700. Springer, 2014.
[8] Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels. Probability Surveys, 6:1–33, 2009.
[9] Fedor Nazarov and Yuval Peres. Trace reconstruction with exp(O(n1/3 )) samples. In Proceedings of the Forty-ninth Annual ACM Symposium on the Theory
of Computing (STOC), pages 1042–1046. Association for Computing Machinery,
2017.
[10] Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion-deletion channels. In Proceedings of the Nineteenth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 399–408. Society
for Industrial and Applied Mathematics, 2008.

28

