Coding against deletions in oblivious and online models∗

arXiv:1612.06335v4 [] 26 Jul 2017

Venkatesan Guruswami†

Ray Li‡

Carnegie Mellon University
Pittsburgh, PA 15213

Abstract
We consider binary error correcting codes when errors are deletions. A basic challenge concerning
deletion codes is determining p0(adv) , the zero-rate threshold of adversarial deletions, defined to be the
supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting
a fraction p of adversarial deletions. A recent construction of deletion-correcting codes [3] shows that
√
p0(adv) ≥ 2 − 1, and the trivial upper bound, p0(adv) ≤ 12 , is the best known. Perhaps surprisingly, we do
not know whether or not p0(adv) = 1/2.
In this work, to gain further insight into deletion codes, we explore two related error models: oblivious
deletions and online deletions, which are in between random and adversarial deletions in power. In the
oblivious model, the channel can inflict an arbitrary pattern of pn deletions, picked without knowledge
of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction
(obl iv)
p < 1 of oblivious deletions, establishing that the associated zero-rate threshold p0
equals 1.
For online deletions, where the channel decides whether to delete bit x i based only on knowledge
of bits x 1x 2 . . . x i , define the deterministic zero-rate threshold for online deletions p0(on,d ) to be the
supremum of p for which there exist deterministic codes against an online channel causing pn deletions
with low average probability of error. That is, the probability that a randomly chosen codeword is
decoded incorrectly is small. We prove p0(adv) = 21 if and only if p0(on,d ) = 21 .

∗ Research

supported in part by NSF grant CCF-1422045.
venkatg@cs.cmu.edu
‡ Email: ryli@andrew.cmu.edu
† Email:

Contents
1 Introduction
1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Other related work on deletion codes and oblivious/online noise models . . . . . . . . . . .

1
2
3

2 Outline of oblivious deletion codes

4

3 Outline of connection between online and adversarial deletions

8

4 Preliminaries

9

5 Deletion code decoding p-fraction of oblivious deletions
5.1 Overview of proof . . . . . . . . . . . . . . . . . . .
5.2 Construction . . . . . . . . . . . . . . . . . . . . . .
5.3 Analyzing construction behavior . . . . . . . . . . .
5.4 Technical combinatorial lemmas . . . . . . . . . . .
5.5 Proof of Construction (Theorem 2.2) . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

10
10
11
11
22
25

6 Relating zero-rate threshold of online and adversarial deletions
26
(on,d)
(adv)
1
1
= 2 . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.1 Proof that p0
= 2 if and only if p0
6.2 Extending to stochastic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7 Conclusion
30
7.1 Decoding deletions vs. insertions and deletions . . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8 Acknowledgements

31

A Relating average-case and worst-case miscommunication probability

33

B Comparison of oblivious deletions with oblivious bit flips

33

C Proofs of Lemma 5.19 and Lemma 5.20

36

1 Introduction
Tremendous progress has been made over the decades, including in recent years, on the problem of designing
error-correcting codes that can recover from bit (or symbol) errors and erasures, for both probabilistic and
adversarial noise models. The problem of correcting closely related insertion and deletion errors has also
been studied since the work of Levenshtein in the 60s [24], but has not seen commensurate progress. The
difficulty is that in the presence of deletions, the location of the missing symbol is not known to the decoder.
As a result, the sender and receiver lose valuable synchronization information on the location of various
symbols, which renders many of the standard techniques for constructing either inapplicable or at least very
tricky and messy to apply. To quote from Mitzenmacher’s survey [26]: “[C]hannels with synchronization
errors, including both insertions and deletions as well as more general timing errors, are simply not adequately
understood by current theory. Given the near-complete knowledge we have [for] channels with erasures and
errors . . . our lack of understanding about channels with synchronization errors is truly remarkable."
In particular, for both the random and adversarial noise models, there are big gaps in our knowledge
of the power and limitations of codes against insertions and deletions. For concreteness, let us focus our
discussion on the model when there are only deletions, which is already complicated enough, and captures
most of the chief difficulties associated with coding against synchronization errors. Note that over large
alphabets, in particular those which can grow with the code length, one can add the coordinate position as a
header to the codeword symbol, and reduce the deletion model to the simpler erasure model, at the expense
of a negligible decrease in rate (due to the addition of the header). However, for fixed alphabets, deletions
seem much harder to cope with than erasures. We focus on the most interesting case of binary codes in this
work.
In order to set the context and motivation for this work, let us review the situation for adversarial and
random deletions in turn, before turning to the contributions of this paper. In each setting we want a code
C ⊆ {0, 1}n consisting of binary codewords of length n that has good rate (where rate R means |C | = 2 Rn ,
and we would like R to be as large as possible, and certainly bounded away from 0 as n grows). We also
have a deletion fraction p ∈ (0, 1), roughly denoting, as a fraction of n, the number of bits the adversary can
delete. In adversarial deletions, the adversary is allowed to delete up to pn bits with full knowledge of the
code and the transmitted codeword. A code C is decodable against pn adversarial deletions if and only if, for
any two distinct codewords c and c ′ in C, it is impossible to apply pn (possibly different) deletions to c and
c ′ and obtain the same result. This is easily seen to be equivalent to the condition that the longest common
subsequence between any two codewords of C has less than (1 − p)n bits. By a lemma originally due to
Levenshtein [24], this condition also ensures that C is capable of correcting any combination of adversarial
insertions and deletions totaling pn in number. We state this lemma formally as it will be used later.
Lemma 1.1. Let LCS(C) be the maximum length of the longest common subsequence between two distinct
codewords in C. The following are equivalent: (1) LCS(C) ≤ n − t − 1, (2) C decodable under up to
t deletions, (3) C decodable under up to t insertions, and (4) C decodable under up to t insertions and
deletions.
When p ≥ 21 , the adversary can delete n/2 bits that includes either all the 0’s or all the 1’s in the codeword,
resulting in just two possible received sequences. Therefore, it is impossible to correct an adversarial deletion
fraction of 12 with rate bounded away from 0. Rather remarkably, we do not know if this trivial limit can
be approached. Denote the zero-rate threshold, p0(adv) , to be the supremum of all p for which there exist
families of codes C ⊆ {0, 1}n of size 2Ωp (n) decodable against pn adversarial deletions. In other words,
p0(adv) is the threshold at which the capacity of adversarial deletions is zero. An outstanding question in the
area is whether p0(adv) = 21 . Or, is p0(adv) < 12 , so that, for p0(adv) < p < 21 , any code C ⊆ {0, 1}n that is
decodable against pn deletions must have size at most 2o(n) ? This was explicitly raised as a key open problem
1

in [25]. Upper bounds on the asymptotic rate function in terms of the deletion fraction were obtained in [21],
improving in some respects Levenshtein’s bounds [25]. New upper bounds on code size for a fixed number
of deletions that improve over [24] were obtained in [7].
Turning to constructions of binary deletion codes, it was shown in [20] that randomly chosen codes
of small enough rate R > 0 can correctly decode against pn adversarial deletions when p ≤ 0.17. Even
non-constructively, this remained the best achievability result (in terms of correctable deletion fraction) until
recently. Bukh, Guruswami, and Håstad [2, 3] improved this and showed that√there are binary codes of rate
bounded away from 0 decodable against pn adversarial deletions for any p < 2 − 1; furthermore, they also
gave an efficient √
construction of such codes along with an efficient deletion correcting algorithm. Closing
the gap between 2 − 1 and 21 for the maximum fraction of correctable deletions, and determining whether
or not p0(adv) = 21 , remain fascinating open problems.
The other heavily studied model of deletion errors has been random deletions. Here the basic noise
model is the binary deletion channel, which deletes each bit independently with probability p. For random
deletions, the zero-rate threshold is known to be 1. In fact, Drinea and Mitzenmacher [11, 12] proved that
the capacity of random deletion codes is at least (1 − p)/9, which is within a constant factor of the upper
bound of 1 − p, the capacity of the simpler binary erasure channel (where the location of the missing bits are
known at the decoder). Recently, explicit codes of rate c(1 −p) for universal constant c > 0 efficiently coding
against random deletions were constructed in [14]. Rahmati and Duman [27] prove that the capacity is at
most 0.4143(1 − p) for p ≥ 0.65. For large deletion probabilities, this is, to our knowledge, the best known
upper bound. For small deletion probabilities, Diggavi and Grossglauser [10] establish that the capacity of
the deletion channel for p ≤ 21 is at least 1 − h(p). Kalai et al. [18] proved this lower bound is tight as p → 0,
and Kanoria and Montanari [19] determined a series expansion that can be used to determine the capacity
exactly for small deletion probabilities.

1.1 Our contributions
With the above context, we now turn to our results in this work. Our first result concerns a natural model that
bridges between the adversarial and random deletion models, namely oblivious deletions. Here we assume
that an arbitrary subset of pn locations of the codeword can be deleted, but these positions must be picked
without knowledge of the codeword. The oblivious model is well-motivated in settings where the noise may
be mercurial and caused by hard to model physical phenomena, but not by an adversary.
If the code is deterministic, tackling oblivious deletions is clearly equivalent to recovering from worstcase deletions. We therefore allow the encoder to be randomized, and require that for every message
m and every deletion pattern τ , most encodings of m can be decoded from the deletion pattern τ . The
randomness used at the encoding is private to the encoder and is not needed at the decoder, which we
require to be deterministic. Note that the oblivious model generalizes random deletions, as deleting each bit
independently with probability p is oblivious to the actual codeword, and with high probability one has ≈ pn
deletions. Of course, any code which is decodable against pn adversarial deletions is decodable also against
pn oblivious deletions, even without any randomization in the encoding. Perhaps surprisingly, we prove that
in the oblivious model, the limit of p ≤ 12 does not apply, and in fact one can correct a deletion fraction p
approaching 1. This generalizes the result that one can correct a fraction p → 1 of random deletions.
Theorem 1.2 (Oblivious). For every p < 1 there exists a family of constant rate stochastic codes that
corrects against pn oblivious deletions with high probability. More precisely, for every p < 1, there exists
R > 0 and a code family with a randomized encoder Enc : {0, 1} Rn → {0, 1}n and (deterministic) decoder
Dec : {0, 1}(1−p)n → {0, 1} Rn ∪ {⊥} such that for all deletion patterns τ with pn deletions and all messages
m ∈ {0, 1} Rn ,
Pr[Dec(τ (Enc(m))) , m] ≤ on (1) ,
2

where the probability is over the randomness of the encoder (which is private to the encoder and not known
to the decoder).1
The above result is implied by deterministic codes C decodable from arbitrary pn deletions under averageerror criterion; i.e., there is a decoding function Dec : {0, 1}(1−p)n → C such that for every deletion pattern
τ with pn deletions, for most codewords c ∈ C, Dec(τ (c)) = c. We note that Theorem 1.2 is an existential
result, and the codes it guarantees are not explicitly specified. The decoder looks for a codeword which
contains the received bit string as a subsequence, and outputting it if there is a unique such codeword.
We also prove an impossibility result for online deletions. An online channel OnAdv consists of n
functions {OnAdvi : i ∈ [n]} such that OnAdvi : X i × Y i−1 → Y, where X = {0, 1} and Y = {h0i, h1i, hi}
is a set of strings and hi denotes the empty string, satisfies OnAdv(x 1 , . . . , x i , y1 , . . . , yi−1 ) ∈ {hx i i, hi}.
The resulting string received by the output is the concatenation of the outputs of OnAdv1 , . . . , OnAdvn .
More concisely, an online channel chooses whether to delete the ith bit ci of a codeword c based on only the
first i bits c 1 , . . . , ci . Note that all online adversaries are valid adversaries in the omniscient adversary case,
so all codes correcting against pn adversarial deletions can also correct against pn online deletions. Notice
that an online channel can delete all the 0s or 1s in the string, so as in the case of adversarial deletions, it
is impossible to communicate with positive rate when the deletion fraction is at least 12 . However, as the
omniscient adversary has more information than the online channel, it could be the case that one can code
against a fraction of deletions approaching 12 for the online channel, whereas this is not possible against an
omniscient adversary. Our next result rules out this possibility for deterministic codes against the online
channel — if the zero-rate threshold p0(adv) for adversarial deletions is bounded away from 21 , then so is the
deterministic zero-rate threshold for online deletions.
Theorem 1.3 (Online). For any p > 1/(3 − 2p0(adv) ) and R > 0, there exists a deterministic online channel
OnAdv such that, for sufficiently large n, for any code C of block length n and rate R > 0, and any decoder
Dec : {0, 1}(1−p)n → C, we have Prc ∈C [Dec(OnAdv(c)) , c] ≥ η for some absolute constant η > 0.
In contrapositive form, the above states that in order to construct codes against adversarial deletions with
error fraction approaching 21 , it suffices to construct deterministic codes decodable in the average case against
a fraction of online deletions approaching 12 . We note our result does not rule out the possibility that there
exist stochastic codes against a fraction of online deletions approaching 21 in the case that p0(adv) < 21 . In
§6.2, we discuss the subtleties of extending our negative result to rule out stochastic codes against a fraction
of online deletions approaching 21 .
Note that since online deletions contain, as a special case, oblivious deletions, if we insist on deterministic
codes where every codeword is correctly decoded, then the question is just as hard as adversarial deletions.
Thus, it is important to allow some error, in the form of randomized encoding (i.e. stochastic codes) and/or
some small fraction of codewords to be decoded incorrectly (i.e., an average-error criterion). This is why,
for our result to be nontrivial, the online strategy of Theorem 1.3 ensures that a constant fraction, as opposed
to a constant number, of codewords are miscommunicated.

1.2 Other related work on deletion codes and oblivious/online noise models
Our focus in this work is on binary codes. Recently, there has been much progress in the situation for
correcting adversarial deletions over large (but fixed size) alphabets. Guruswami and Wang [16] proved that
for ϵ > 0 there exist polynomial time encodable and decodable codes with alphabet size poly(1/ϵ) correcting
1 − ϵ fraction of deletions with rate Ω(ϵ 2 ), and codes with alphabet size poly(1/ϵ) correcting ϵ fraction of
√
deletions with rate 1 − Õ( ϵ). Guruswami and Li [13] extended these results for high noise and high rate
1The notation τ (y) for y ∈ {0, 1}n denotes the bit string obtained by applying deletion pattern τ to y.

3

regimes to correcting insertions and deletions. Recently, in a beautiful work, Haeupler and Shahrasbi [17]
construct, for any ϵ, δ > 0, codes with alphabet size poly(1/ϵ) and rate 1 − δ − ϵ correcting a δ fraction of
insertions and deletions.
The model of oblivious errors (such as bit flips) has has been studied in the information-theory literature
as a particular case of arbitrarily varying channels with state constraints [23] (see the related work section
of [15] for more background on this connection). In particular, for the case of bit flips, the capacity against
the model of pn oblivious bit flips (for p ≤ 12 ) equals 1 − h(p), matching the Shannon capacity of the binary
symmetric channel that flips each bit independently with probability p. (This special case was re-proved in
[22] by a different simpler random coding argument compared to the original works [5, 6].) Similarly, the
capacity against the model of pn oblivious erasures is 1 − p, matching the Shannon capacity of the binary
erasure channel. Explicit codes of rate approaching 1 − h(p) to correct pn oblivious bit flips (in the sense
of Theorem 1.2, with randomized encoding) were given in [15]. This work also considered computationally
bounded noise models, such as channels with bounded memory or with small circuits, and gave optimal rate
codes for list decoding against those models. These models are more general than oblivious errors, but still
not as pessimistic as adversarial noise.
Notice that in the case of both erasures and errors, the capacity in the oblivious and random models
were the same. It is not clear if this is the case for deletions. While we show that the zero-rate threshold of
oblivious deletions equals the zero-rate threshold of random deletions, the rate of the codes we guarantee in
Theorem 1.2 for p → 1 is significantly worse than the Ω(1 − p) lower bound known for random deletions.
Turning to online models, Chen, Jaggi, and Langberg [4], in an impressive work, determined the exact
capacities of the online erasure channel and the online bit-flip channel. A recent work studies a seemingly
slight (but in fact fundamental) restriction of the online model where the channel’s decision regarding the
i’th bit depends only on the first (i − 1) bits and is independent of the current bit [9]. They proved that in the
setting of erasures, the capacity in this restricted online model increases to match the capacity 1 − p of the
binary erasure channel, as opposed to 1 − 2p in the true online model.
To the best of our knowledge, ours is the first work to address both oblivious and online deletions. We
feel that given the large gaps in our understanding of coding against adversarial deletions, and the potential
of taking advantage of less stringent models of deletion exhibited in this work, further study of these models
seems
timely and important. In particular, for online deletions as well, the zero-rate threshold is between
√
2 − 1 and 21 . It is an interesting challenge to ascertain if one can take advantage of the online restriction, and
push some of the ideas in [3] and this work, to enable decoding a fraction of online deletions approaching 12 .
Organization of this paper. In §2 we outline our oblivious deletion construction and sketch the proof of
why it is correct. In §3 we outline our proof that the online zero-rate threshold for deterministic code, p0(on,d) ,
is 21 if and only if the adversarial zero-rate threshold, p0(adv) , is 21 . In §4 we introduce definitions and notation
for the remainder of the paper. In §5 we state and formally prove our construction on codes in the oblivious
model with p deletion fraction where p ∈ (0, 1). In §6 we prove that the deterministic zero-rate threshold of
the online deletion channel p0(on,d) is also bounded away from 12 if p0(adv) < 21 .

2 Outline of oblivious deletion codes
Instead of proving Theorem 1.2 directly, we prove a related theorem for decoding in the average case, defined
below.
Definition 2.1. We say a (deterministic) binary code C of block length N decodes pN oblivious deletions in
the average case if for every deletion pattern τ deleting pN bits, we have
|{x ∈ C : ∃y ∈ C s. t. x , y and τ (x) ≤ y}| ≤ o N (1) · |C | .
4

(1)

Theorem 2.2 (Correcting oblivious deletions for average message). Let p ∈ (0, 1). There exists a constant
R > 0 such that there exist infinitely many N for which there is a rate R code C ⊆ {0, 1} N that decodes pN
oblivious deletions in average case.
It is standard to show that for oblivious deletions, a randomized code with low probability of incorrect
decoding for every message (as promised in Theorem 1.2), and a deterministic code with low probability of
incorrect decoding for a random message, are equivalent. In particular Theorem 2.2 implies Theorem 1.2.
For completeness we provide a proof of this implication in Appendix A. Roughly, if we have a length N
code C with rate R that decodes against pN deletions in the average case, then we can group the codewords
into sets of size 20.01Rn . Then we associate every message with a set of codewords and encode the message
by randomly choosing a codeword from its set. Our decoding function simply takes a received word s and
looks for a codeword c such that s ⊑ c, i.e. c is a superstring of s. If there is exactly one such c, output the
associated codeword, otherwise output ⊥. Using the fact that C decodes pN deletions in the average case, we
can show that for all deletion patterns τ , only a few codewords do not decode correctly via unique decoding
in our new stochastic code.
We now outline our construction for Theorem 2.2. A first, naive attempt at this problem would be
to choose a random subset of 2 RN codewords in {0, 1} N . This technique, however, does not work in the
same way it does for oblivious bit-flips. See Appendix B for a discussion on the difficulties faced by this
approach. Instead, our approach to prove Theorem 2.2 uses the so-called “clean construction” from [3] with
appropriately selected parameters. The idea is to choose a concatenated code such that the inner code widely
varies in the number of runs between codewords. Specifically, we choose sufficiently large constants R and
K and set our inner code to have length L = 2R K . For i = 1, 2, . . . , K, set our inner codewords to be
 i −1 i −1  L/(2R i −1 )
дi = 0R 1R

(2)

where 0k and 1k denote strings of k 0s and 1s, respectively. In this way, the number of runs between any
two codewords differs by a factor of at least R. Our outer code is a subset of [K]n , so that the total code
length is N = nL, and we concatenate the code via a function ψ : [K]∗ → {0, 1}∗ that replaces a symbol
i ∈ [K] with the string дi ∈ {0, 1}L . The outer code is chosen via a random process, detailed in the following
paragraphs; the process throws out a small subset of “bad” elements of [K]n and chooses a constant rate
code by including each remaining element independently with some small fixed probability. Our decoding
function is unique decoding. That is, given a received word s, we find a codeword c such that s ⊑ c. 2 If
such a codeword is unique, our decoder returns that output. Otherwise, the decoder returns ⊥.
The following example illustrates why the varying run length is powerful even for correct more than
0.5N deletions: Suppose n = 100, p = 0.9, R ≫ 20, our received word is s = д110 (that is, 10 copies of д1
concatenated together) and our code contains the codeword c = д2100 . Then s is a subsequence of c if and
only if we can identify each of the 10 д1 s with non-overlapping bits of c. However, since д1 contains over
20 times as many runs as д2 , each д1 must be identified with a subsequence of c spanning at least 20 inner
codewords, i.e. copies of д2 . This means the subsequence s roughly must span at least 200 inner codewords,
but c only has 100 inner codewords, contradiction. While this imbalanced run-count behavior is a key to our
argument, it is worth noting that the behavior is asymmetric. In particular, while it takes R copies of д2 to
produce д1 as a subsequence, we only need two copies of д1 to produce д2 as a subsequence.
To analyze this code, we leverage the run-count behavior of the inner codewords. This contrasts with the
adversarial setting, where the run-count property of the same code is featured less centrally in the proof of
correctness [3]. We show that for any deletion pattern τ with up to pN deletions, two random codewords X
2The relation w ⊑ w ′ means that w is a (not-necessarily consecutive) subsequence of w ′ .

5

and Y are “confusable” with exponentially small probability in N . To be precise, we have for all τ ,
Pr

[τ (ψ (X )) ⊑ ψ (Y )] < 2−Ω(n) .3

X,Y ∼U ([K ]n )

(3)

The idea for this proof can be illustrated in the case that τ deletes only entire inner codewords. If τ
deletes pn of the n inner codewords and does not touch the remaining codewords, then τ (ψ (X )) has the same
distribution over length (1 − p)N binary strings as ψ (X ′) where X ′ ∼ U ([K](1−p)n ). Thus we would like to
show
[ψ (X ′ ) ⊑ ψ (Y )] < 2−Ω(n) .
(4)
Pr
X ′ ∼U ([K ](1−p)n )
Y ∼U ([K ]n )

′
Consider trying to find ψ (X ′) as a substring of ψ (Y ) where X ′ = X 1′ X 2′ . . . X (1−p)n
This is possible if and only
′
if we match the bits of X to bits of Y greedily. However, each inner codeword дX i′ spans a large number
(R) of inner codewords of Y unless the greedy matching encounters at least one Yj such that Yj ≤ X i′ , i.e. a
higher frequency inner codeword (if Yj < X i′ , we may need to encounter two such higher frequency inner
codewords, but two is at least one). Thus, if X i′ = 1 for some i, then the number of inner codewords spanned
by дX i′ is approximately distributed as Geometric(1/K). In general, conditioned on X i′ = k, the number
of inner codewords spanned by дX i′ is approximately distributed as Geometric(k/K). Thus, the number of
inner codewords of Y spanned by a single inner codeword X i′ is
 
 
 
K
K
K
1
1
1
·Θ
+ ·Θ
+···+ ·Θ
= Θ(log K)
(5)
K
1
K
2
K
K
2
then the expected number of inner codewords of Y spanned by X ′ is
If we choose K so that Θ(log K) > 1−p
more than Θ(log K) · (1 − p)n > 2n, so concentration bounds tell us that the probability that ψ (X ′ ) ⊑ ψ (Y ) is
exponentially small in n.
Note that there is a slight caveat to the above argument because the numbers of inner codewords in ψ (Y )
spanned by ψ (X i′) are not independent across all i. For example, if ψ (Y ) begins with д2д1 and ψ (X ′ ) begins
with д1д1 , then the second inner codeword of ψ (Y ) has a few “leftover bits” that easily match with ψ (X ′)’s
second inner codeword. However, we can adjust for this independence by relaxing our analysis by a constant
factor.
The above addresses the case when the deletion pattern, for each inner codeword, either deletes the
codeword entirely or does not modify it at all. We now show how to extend this to general deletion patterns,
starting with the case of p < 21 .
Note that the above argument only depended on the inner codewords having widely varying runs. By
a simple counting argument, we can verify that at least a (0.5 − p) fraction of codewords have at most
(p + (0.5 − p)/2)L = (0.5 + p)L/2 deletions. Since we are in the setting where p < 21 , applying (0.5 + p)L/2
deletions to an inner codeword with r runs cannot make the number of runs less than (0.5 − p)r , as it can
delete at most (0.5 + p)/2 fraction of the runs, and deleting each run reduces the number of runs by at most
two. If we choose R ≫ 1/(0.5 − p)2 , then we can guarantee that even if we have a generic deletion pattern,
we have a constant fraction (0.5 − p) of positions for
√ which the run-count properties of all inner codewords
in those positions are preserved up to a factor of R. Thus, as the number of runs between any two inner
codewords differs by a factor of at least R, even after these
√ corruptions the ratio between the number of
runs of two “preserved” inner codewords is still at least R. Using the same argument as above and now
2
, we can conclude that even for general deletion patterns that the probability that
requiring Θ(log K) > 0.5−p
two random candidate codewords are confused is exponentially small.

3The notation U ([K]n ) denotes the uniform distribution on [K]n .

6

As a technical note, working with deletion patterns directly is messy as they encode a large amount
of information, much of which we do not need in our analysis. Furthermore, the caveat mentioned in the
clean deletion pattern case regarding the independence of number inner codewords spanned by some ψ (X i′ )
becomes more severe for general deletion patterns. This happens because in general deletion patterns,
especially later for p > 21 , the inner codewords of ψ (X ) that have preserved their run-count property might
nonetheless be shorter, so many (in particular, Θ(1/(1 − p))) inner codewords could match to single inner
codewords of ψ (Y ). To alleviate this complexity in the analysis, we introduce a technical notion called
a matching intended to approximate the subsequence relation. This notion allows us to capture only the
run-count behavior of the deletion patterns with respect to the inner codewords while also accounting for the
lack-of-independence caveat. For a deletion pattern τ , let σ be the associated deletion pattern such that σ (X )
to removes all outer codeword symbols except the ones in whose position τ preserves the run-count property
of all the inner codewords (these exist because we are still in the case p < 1/2). In our proof, we argue that
if τ (ψ (X )) is a subsequence of ψ (Y ), then σ (X ) has a matching in Y , and that the probability that σ (X ) has a
matching in Y for two codewords X and Y is exponentially small.
To extend the argument for generic deletion patterns from p < 1/2 to p < 1, we must use a “local list
decoding” idea. Note that when the number of deletion patterns exceeds 1/2, for every codeword there exists
deletion patterns that destroy all or almost all of the information in the codeword, e.g. the deletion pattern
that deletes all the 1s (or 0s) of the codeword. For this reason, codes cannot correct against more than 1/2
fraction of adversarial deletions. However, one can show that this does not happen too frequently allowing
us to correct oblivious and average case deletions. In contrast to the p < 1/2 case where we found a small,
constant fraction of inner codeword positions in which the deletion pattern of the inner codeword preserved
the run-count property for all inner codewords, we can now find a small, constant fraction of inner codeword
positions in which the deletion pattern of the inner codeword preserves the run-count property for all but a
few inner codewords. For example, even if an inner code deletion pattern deletes every other bit and thus
deletes all the information of д1 , the number of runs of д2 , д3 , . . . , дK are still preserved. We call this idea
“local list decoding” because while we cannot decode our constant fraction of inner codewords uniquely,
we can still pin down the inner codewords to a few possibilities. By extending our definition of matching
to account for a few inner codewords potentially losing their run-count behavior, we can prove, just as for
p < 1/2, that τ (ψ (X )) ⊑ ψ (Y ) implies σ (X ) has a matching in Y , and σ (X ) having a matching in Y happens
with small probability.
At this point of the proof, we have combinatorially established everything we need to prove that our
code is decodable in the average case (and thus against oblivious deletions). That is, we have shown that
a random candidate codeword in ψ ([K]n ) has an exponentially small probability of being confused with
another random candidate codeword. Given that codewords have an exponentially small probability of being
confusable with each other, it is natural to consider choosing a code by randomly selecting a subset of [K]n .
Using this construction, we might try using concentration bounds to show that, for any deletion pattern τ ,
the probability that we have more than ϵ |C | codewords (for ϵ = o(N )) that are confusable with some other
codeword is at most 2−ω(N ) , and we can union bound over the at-most-2N choices of τ . This however does
not work directly as the decodability for a given deletion pattern τ depends on the decodability of other
deletion patterns. For example, if p > 21 and we happen to choose c = ψ (11 . . . 1) = 0101 . . . 01 as a
codeword, then for any deletion pattern τ with pN deletions, c ′ ⊑ c for all candidate codewords c ′. From this
example alone, the probability of many codewords confusable with c is at least K −n and there are many more
examples of such easily disguised candidate codewords. Fortunately, we can prove that the number of easily
disguised candidate codewords is small. In particular, we show that the majority of elements of ψ ([K]n )
are not easily disguised in all deletion patterns τ . This intuitively makes sense because, as we have shown,
in any deletion pattern τ , on average, words are disguised as an exponentially small fraction of codewords,
and because the easily disguised words tend to be easily disguised in every deletion pattern τ . For example,

7

ψ (11 . . . 1K ) = 0101 . . . 01 is easily disguised for any deletion pattern τ .
After throwing out the easily disguised candidate codewords, we randomly choose a constant rate code
from the remaining candidate codewords. Careful bookkeeping confirms that with positive probability we
obtain a code that decodes pN -deletions in the average case. The bookkeeping is nontrivial, because just as
there are a handful of words like ψ (11 . . . 1) that are easily disguised as other codewords with deletions, there
are also a handful of easily confused words like ψ (KK . . . K) that can be confused with many other words
when deletions are applied to it. Furthermore, unlike easily disguised codewords, these easily confused
words vary over the different deletion patterns, so we cannot simply throw them out. However, like for easily
disguised codewords, we show the number of easily confused words is an exponentially small fraction of
the codebook size in expectation, so such words do not contribute significantly to the number of incorrectly
decoded codewords. Note the subtle difference between easily disguised and easily confused words: a single
easily disguised word like ψ (11 . . . 1) causes many candidate codewords to fail to decode under our unique
decoding, but any easily confused codeword adds at most one failed decoding.
We model managing easily disguised and easily confusable codewords via a directed graph, where,
−−→
roughly, for each deletion pattern, we consider a graph on [K]n where YX is an edge if and only if
τ (ψ (X )) ⊑ ψ (Y ). In our proof, we replace the subsequence relation with the matching relation (see §5.4).
In this graph language, the easily disguised codewords correspond to vertices with high outdegree, and the
easily confusable codewords correspond to vertices with high indegree.
Our construction illustrates the subtle nature of the oblivious deletion channel and average case errors.
These settings share much of the behavior of the adversarial deletion channel such as the fact that for p > 12 ,
every codeword has a deletion pattern destroying all of its information. Consequently, our approach tackles
the oblivious and average case errors using a combinatorial argument just as the best adversarial deletion
results do [3]. Yet, the relaxed decoding requirement allows us to exploit it to correct a fraction of deletions
approaching 1.

3 Outline of connection between online and adversarial deletions
We give a high level outline of the proof of Theorem 1.3. Recall that the goal is to prove that, assuming
p0(adv) < 12 , for some p < 21 , for every deterministic code of rate bounded away from 0, there exists a
deterministic online deletion channel applying up to pn deletions that prevents successful decoding in the
average case. That is, when a uniformly random codeword is transmitted, the probability of incorrect
decoding is bounded away from 0. Note first that it suffices to find a randomized online deletion strategy
guaranteeing average-case decoding error because, if for a given code the channel has a random strategy to
guarantee average-case decoding error, then sampling a strategy over the randomness of the channel gives a
deterministic online strategy that inflicts similar probability of incorrect decoding.
To do this, we assume that the adversarial zero-rate threshold is p0(adv) < 12 , and consider p ∗ = 1/(3 −
(adv)
(adv)
2p0
). Our choice of p ∗ satisfies p0
< p ∗ < 21 . Now we show that for any p ∗ < p < 12 , there exists a
randomized strategy that inflicts pn deletions in an online manner to a deterministic code, and guarantees that
the probability, over the randomness of a uniformly chosen codeword and the randomness of the adversary,
1
of incorrect decoding is positive (we show it is at least 10
).
We adapt the “wait-push” strategy of Bassily and Smith [1] for an online adversary against erasures. In
the “wait phase” of this strategy, the adversary observes a prefix x ∗ of ℓ bits from the transmitted word x
without erasing any bits. Then it constructs a list Lx ∗ of candidate codewords, among which is the actual
codeword chosen by the encoder. In the “push phase”, the adversary chooses a codeword x ′ randomly from
Lx ∗ , which, with positive probability, corresponds to a different message than the actually transmitted word.
The adversary then, for the last n − ℓ bits of the transmission, erases bit x i of x where x i , x i′ (x i′ the ith bit
8

of x ′ ).
Our strategy adapts the wait push strategy to deletions. In our wait phase, we observe a prefix of the
string until we know the codeword x exactly. We choose in advance a random bit and delete every instance
of that bit that we see during the wait phase. After the wait phase, suppose we have seen qn bits and deleted
rn bits, where r < q, and we also know the codeword x exactly. Using the definition of p0(adv) , we can show
that, for most choices of x, there is another codeword y such that (i) the wait phase lengths qn for x and y
are the same, (ii) their majority bits b in the wait phases are the same, (iii) the number of bits rn deleted in
the wait phases is the same, and (iv) the length-(1 − q)n suffixes x ∗ and y ∗ of x and y, respectively, have a
common subsequence s ∗ satisfying |s ∗ | > (1 − p0(adv) )|x ∗ |. We can form pairs of such codewords (x, y) in
advance, so that when we see either x or y we push the suffixes x ∗ or y ∗ to s ∗ , so that the received word in
both cases is b r n s ∗ . For these typical choices of x, the total number of required deletions to obtain b r n s ∗ is at
(adv)
most qn/2 + p0
(1 − q)n. If q is bounded away from 1 (in our case, less than (1 − p)n), then we can bound
the number of deletions away from 21 (in our case, less than p ∗ = 1/(3 − 2p0(adv) )). On the other hand, if q
is large (larger than (1 − p)n), then we can simply observe the first (1 − p)n bits and delete the rest. Since
we can only choose one strategy to run, we choose one of these two strategies at random. This gives our
modified wait push strategy.

4 Preliminaries
General Notation. For a boolean statement P, let 1[P] be 1 if P is true and 0 otherwise.
Throughout the paper, log x refers to the base-2 logarithm.
We use interval notation [a, b] = {a, a + 1, . . . , b} to denote intervals of integers, and we use [a] = [1, a] =
{1, 2, . . . , a}.

For a set S and an integer a, let Sa denote the family subsets of S of size a. Let U (S) denote the uniform
distribution on S.
Words. A word is a sequence of symbols from some alphabet. We denote string concatenation of two
words w and w ′ with ww ′. We denote w k = ww · · · w where there are k concatenated copies of w. We also
Î
denote a concatenation of a sequence of words as w 1w 2 · · · w k = ki=1 w i . We denote words from binary
alphabets with lowercase letters c, s, w and words from non-binary alphabets with capital letters X , Y , Z .
A subsequence of a word w is a word obtained by removing some (possibly none) of the symbols in w.
A subword or interval of a word w is a contiguous subsequence of characters from w. We identify
intervals of words with intervals of integers corresponding to the indices of the subsequence. For example,
the interval {1, 2, . . . , |w |} = [1, |w |] is identified with the entire word w.
Let w ′ ⊑ w denote “w ′ is a subsequence of w”.
Define a run of a word w to be a maximal single-symbol subword. That is, a subword w ′ in w consisting
of a single symbol such that any longer subword containing w ′ has at least two different symbols. Note the
runs of a word partition the word. For example, 110001 has 3 runs: one run of 0s and two runs of 1s.
Deletion Patterns. A deletion pattern is a function τ that removes a fixed subset of symbols from words
of a fixed length. Let D(n, m) denote the set of deletion patterns τ that operate on length n words and apply
n
exactly m deletions. For example τ : x 1x 2x 3 7→ x 1x 3 is a member of D(3, 1). Let D(n) = ∪m=0
D(n, m).
We identify each deletion pattern τ ∈ D(n, m) with a size m subset of [n] corresponding to the deleted
bits. We often use sets to describe deletion patterns when the length of the codeword is understood. For
example [n] refers to the single element of D(n, n). Accordingly, let ⊆ be a partial order on deletion patterns
corresponding to set inclusion, and let |τ | denote the number of bits deleted by τ . As such, we have τ ⊆ τ ′
implies |τ | ≤ |τ ′ |.
9

For a word w and τ ∈ D(|w |), let τ (w) and w \ τ both denote the result of applying τ to w. We use
the second notation when we identify sets with deletion patterns, as in the above paragraph where the set
elements correspond to the deleted positions.
In a concatenated code with outer code length n and inner code length L, we can identify a deletion pattern
on the entire codeword τ ∈ D(nL) as the “concatenation” of n deletion patterns τ1 ⌢ · · · ⌢ τn , one for each
inner codeword. To be precise, for all τ ∈ D(nL), there exists τi ∈ D(L) such that τ = ∪ni=1 {j+(i−1)L : j ∈ τi },
and we denote this by τ = τ1 ⌢ · · · ⌢ τn . Using this notation, we refer to τi as an inner code deletion
pattern.
Graphs. In a (directed or undirected) graph G, let V (G) and E(G) denote the vertex set and edge set of G
respectively. For a subset W ⊆ V (G) of the vertices, let G ↾ W denote the subgraph induced by W . We use
G ↾ W instead of the more standard G |W to avoid too many subscripts. For a vertex v ∈ V (G), let degG (v)
denote the degree of v in G when G is undirected, and let indegG (v), outdegG (v) denote the indegree and
outdegree of v, respectively, in G when G is directed. We drop the subscript of G in deg, indeg and outdeg
notations when the graph G is understood.
Concentration Bounds. We use the following forms of Chernoff bound.
Lemma 4.1 (Chernoff). Let A1 , . . . , An be independent random variables taking values in [0, 1]. Let
Í
A = ni=1 Ai and δ ∈ [0, 1]. Then


Pr[A ≤ (1 − δ ) E[A]] ≤ exp −δ 2 E[A]/2 .
(6)
Furthermore, if A1 , . . . , An are Bernoulli random variables, then
Pr[A ≥ (1 + δ ) E[A]] ≤



eδ
(1 + δ )( 1 + δ )

 E[A]

(7)

We also use the submartingale form of Azuma’s Inequality.
Lemma 4.2 (Azuma). Let c be a constant. Let X 1 , X 2 , . . . be a submartingale such that |X i − X i−1 | ≤ c for
all i. Then for all positive reals t, we have


−t 2
Pr[X k − X 1 ≤ −t] ≤ exp
.
(8)
2c 2 (k − 1)

5 Deletion code decoding p-fraction of oblivious deletions
5.1 Overview of proof
In §2 we gave a high level overview. We now begin with a brief snapshot of the proof structure and how it is
organized.
We present our general code construction in §5.2. The construction uses the “clean construction” in [3]
and an outer code that we choose randomly. We analyze properties of the concatenated construction in §5.3.
We begin by extracting the useful behavior of deletion patterns with respect to our codewords. This deletion
pattern analysis culminates in Lemma 5.7, allowing us to define the signature (Definition 5.8) of a deletion
pattern. The key result of §5.3 is Proposition 5.18. It states that for any deletion pattern τ , the probability
that two random candidate codewords c, c ′ are confusable (in the sense that τ (c) ⊑ c ′ ) is exponentially small
in the code length. However, because working with deletion patterns directly is messy, the proposition is
written in the language of matchings, a technical notion defined in Definition 5.11. In short, because the inner
10

codewords are nicely behaved, we do not need to know the exact details of the behavior of a given deletion
pattern τ , but rather only need certain properties of it, given by its signature. We thus define a matching to
approximate the subsequence relation using only the signature of τ , so that “σ (X ) is matchable in Y ” (where
σ is the outer code deletion pattern given by τ ’s signature) holds roughly when “τ (ψ (X )) ⊑ ψ (Y )” holds.
Combinatorially, Proposition 5.18 allows us to finish the proof. As stated in §2, for our outer code we
consider [K]n minus a small set of easily disguised candidate codewords. The notion of a easily disguised
candidate codeword is well defined by Lemma 5.23. For a sufficiently small constant γ , we randomly choose
a size 2γ n outer code over the remaining outer codewords. In §5.4, we use the graph language described in
§2 and prove Lemma 5.27, which roughly states that in a sparse directed graph, if we randomly sample a
small subset of vertices, the induced subgraph is also sparse (for some appropriate definition of sparse) with
high probability. Finally, in §5.5, we piece together these results, showing that Lemma 5.27 guarantees, with
positive probability, that our random code combinatorially decodes against pN deletions in the average case.

5.2 Construction
Let p ∈ (0, 1), and let λ = λ(p) be the smallest integer such that (1 + p)/2 < 1 − 2−λ . For our argument any
λ such that p < 1 − 2−λ suffices. In particular, for p < 12 , we can choose λ = 1, slightly simplifying the
argument as described in §2. However, we choose λ to be the smallest λ such that (1 + p)/2 < 1 − 2−λ to
ensure a clean formula for the rate.
Let δ be such that p = 1 − 2−λ − δ . Let n be a positive integer. With hindsight, choose
K = 2 ⌈2

λ+5 /δ ⌉

,

R = 4K 4 ,

L = 2R K ,

N = nL.

(9)

Note that R is even. For the remainder of this section, the variables p, λ, δ, K, R and L are fixed.
In this way we have 1 − 2−λ − √1 − δ2 > p. For i = 1, . . . , K, let дi be the length L word
R

 i −1 i −1  L/(2R i −1 )
дi = 0R 1R
.

(10)

Consider the encodingψ : [K]∗ → {0, 1}∗ whereψ (X 1 · · · X k ) = дX 1 дX 2 · · · дX k . We construct a concatenated
code where the outer code is a length n code over [K] and the inner code is {д1 , д2 , . . . , дK } ⊆ {0, 1}L . For
the outer code, we choose a random code Cout where each codeword is chosen uniformly at random from
[K]n minus a small undesirable subset that we specify later. We choose our decoding function to be unique
decoding. That is, our decoder iterates over all codewords c ∈ C and checks if the received word s is a
subsequence of c. If it is a subsequence of exactly one c, the decoder returns that c, otherwise it fails. While
this decoder is not optimal in terms of the fraction of correctly decoded codewords (it could try to break
ties instead of just giving up), it is enough for this proof. Furthermore, since we are showing combinatorial
decodability, we do not need the decoder to be efficient.
If, for some p ′ > p, a code can decode p ′nL average case or oblivious deletions, then it can decode pnL
deletions. Thus, we can decrease δ until δn is an even integer, so may assume without loss of generality that
δn is an even integer.

5.3 Analyzing construction behavior
Definition 5.1. A дi -segment is an interval in [L] corresponding to a run of дi . Note that the дi -segments
partition [L] and are of the form [1 + aRi−1 , (a + 1)Ri−1 ] for a ∈ {0, . . . , L/Ri−1 − 1}.

11

Note that дi has 2R K +1−i runs. In particular, the number of runs greatly varies between inner codewords.
This property makes the concatenated construction powerful because it is difficult to find common subsequences of different inner codewords. The following definition allows us to reason about the inner codewords
in terms of their run counts.
√
Definition 5.2. We say an inner code deletion pattern σ preserves дi if σ (дi ) has at least 2R K +1−i / R =
1
2R K + 2 −i runs. Otherwise we say σ corrupts дi .
We start with a basic but useful fact about deletion patterns and runs.
Lemma 5.3. Suppose w is a word with r runs I1 , . . . , Ir and τ is a deletion pattern such that τ (w) has r ′
runs. We can think of these runs Ik as subsets of consecutive indices in {1, . . . , |w |}. Then the number of
runs Ik of w completely deleted by τ , i.e. satisfying I ⊆ τ when τ is thought of as a subset of {1, . . . , |w |}, is
′
at least r −r
2 .
Proof. Deleting any run reduces the number of runs in a word by at most 2, and τ reduces the number of
runs by r − r ′ , so the claim follows.

The next lemma establishes the usefulness of widely varying runs in our construction. It says that even
when an inner code deletion pattern has a large number of deletions, most of the inner codewords still look
the same in terms of the number of runs. The intuition for the lemma is as follows. Consider the extreme
example of an inner code deletion pattern σ that “completely corrupts” the inner codewords д1 , . . . , дλ . That
is, σ deletes all the zeros of each of д1 , . . . , дλ . Since σ deletes all the zeros of дλ , it must delete every other
run of R λ−1 bits, thus deleting L/2 bits. Applying these deletions alone to дλ−1 leaves it with half as many
runs of length exactly R λ−2 . However, since σ also deletes all zeros of дλ−1 , it must delete every other run of
R λ−2 bits of the remaining L/2 bits, thus deleting L/4 more bits. Similarly, since σ deletes all zeros of дλ−2 ,
it must delete an additional L/8 bits. Continuing this logic, we have σ must delete L(1 − 2−λ ) bits total. This
tells us that if an inner code deletion pattern completely corrupts the inner codewords д1 , . . . , дλ , it needs
L(1 − 2−λ ) deletions. This logic works even if we chose to corrupt any subset of λ inner codewords other
than {д1 , . . . , дλ }. One can imagine that corrupting (according to Definition 5.2) inner codewords is almost
as hard as completely corrupting them, so adding some slack gives the lemma.


Lemma 5.4. If σ is an inner code deletion pattern with |σ | ≤ L 1 − 21λ − √1 , then σ preserves all but at
R
most λ − 1 choices of дi .
Proof. Suppose λ is a positive
integer such

 that σ corrupts дi for λ different values of i, say i 1 > i 2 > · · · > i λ .
1
1
We wish to show |σ | > L 1 − 2λ − √ .
R

Recall that a дi segment is an interval of the form [1 + aRi−1 , (a + 1)Ri−1 ]. Inductively define the
collections of intervals I1 , . . . , Iλ and the sets of indices I1 , . . . , I λ as follows. For 1 ≤ a ≤ λ, set
)
(
a−1
Ø
Ø
Ib
and Ia =
J.
(11)
Ia = J : J is дia -segment, J ⊆ σ \
b=1

J ∈Ia

Intuitively, I1 as the set of runs in дi1 that are entirely deleted by σ , and I1 is the set of those deleted indices.
Then, I2 is the set of runs of дi2 deleted by σ but not already accounted for by I1 , and I2 is the set of bits in
the runs of I2 . We can interpret I3 , . . . , Iλ and I3 , . . . , I λ similarly. By construction, I1 , . . . , I λ are disjoint,
Íλ
and their union is a subset of σ (thought of as a subset of [L]), so b=1
|Ib | ≤ |σ |. It thus suffices to prove

1
1
|Ib | > L 1 − λ − √ .
2
R
b=1
λ
Õ



12

(12)

′

Note that for any j < j ′, every дj ′ -segment is the disjoint union of R j −j many дj -segments. We thus have [L]
is the disjoint union of дia -segments and Ib is also the disjoint union of дia -segments when b < a (and thus
a−1 I is the disjoint union of д -segments. Furthermore, as R is even, each I covers
ib > i a ). Hence, [L] \ ∪b=1
ia
b
b
a−1 I alternate between segments corresponding
an even number of дia -segments, so the segments of [L] \ ∪b=1
b
a−1 I
to runs of 0s in дia and segments corresponding to runs of 1s in дia . It follows that all runs of дia \ ∪b=1
b
i
−1
a−1
a
have length exactly R
, so the number of runs in the string дia \ ∪b=1 Ib is
L
Ria −1

−

a−1
Õ
b=1

Rib −ia |Ib |.

(13)

By construction, the only дia -segments that are deleted√by σ are the intervals covered by I1 ∪ · · · ∪ Ia . Since
σ corrupts дia , we know σ (дia ) has less than L/(Ria −1 R) runs. By Lemma 5.3, we have
!
!
a−1
Õ
L
1
L
Rib −ia |Ib | −
−
|Ia | >
(14)
√ .
2 Ria −1
Ria −1 R
b=1
Simplifying and using |Ib | = Rib −1 |Ib | for all b, we obtain
|Ia | > L




a−1
1
1Õ
1
|Ib |.
− √ −
2 2 R
2
b=1

(15)

From here it is easy to verify by induction that, for all 1 ≤ a ≤ λ, we have



a
Õ
1
1
|Ib | > L 1 − a 1 − √ .
2
R

(16)

b=1

Indeed, (15) for a = 1 provides the base case, and if we know (16) for some a − 1, then by (15) we have



a−1
1
1
1Õ
|Ib | > L
|Ib |
− √ +
2 2 R
2
b=1
b=1





1
1
L
1
1
> L
− √ +
1 − a−1 1 − √
2 2 R
2
2
R



1
1
= L 1− a 1− √ ,
2
R
a
Õ

(17)

completing the induction. The induction proves (12), from which we have



1
1
|Ib | > L 1 − λ − √ ,
|σ | ≥
2
R
b=1
λ
Õ

(18)

as desired.



Lemma 5.4 motivates the following definition.
Definition 5.5. We say an inner code deletion pattern |σ | is ℓ-admissible if |σ | ≤ L(1 − 1/2ℓ+1 −

√1 ).
R

If, for some ℓ, σ is ℓ-admissible, then Lemma 5.4 tells us σ corrupts at most ℓ different дi . However,
note that ℓ-admissibility is stronger that corrupting at most ℓ different дi as ℓ-admissibility gives a stronger
upper bound on the number of deletions in σ , which is necessary in Lemma 5.12.
13

Lemma 5.6. Let δ > 0. Let τ = τ1 ⌢ · · · ⌢ τn be a deletion pattern with at most (1 −
deletions. There are at least δn indices i such that τi is (λ − 1)-admissible.
Proof. By a simple counting argument, we have |τi | > L(1 −

1
2λ

−

√1 )
R

1
2λ

−

√1
R

− δ2 )N

for at most





n · L 1 − 21λ − √1 − δ2
δ /2
R


≤ n (1 − δ )
≤ n 1−
1 − 2−λ
L 1 − 21λ − √1

(19)

R

values of i. For the remaining at least δn values of i, we have τi is (λ − 1)-admissible.



The following corollary allows us to reduce our analysis of a deletion pattern τ to analyzing positions
where τ ’s inner code deletion pattern is (λ − 1)-admissible. We effectively assume that our deletion pattern
completely deletes all inner codewords with a non-admissible index.
Lemma 5.7. Let τ ∈ D(nL, pnL). There exists τ ′ ∈ D(δnL), σ ∈ D(n, (1 − δ )n) and sets S 1 , . . . , S δ n such
that
1. |S i | = λ − 1 for all i,
2. for all X ∈ [K]n , we have τ ′(ψ (σ (X ))) ⊑ τ (ψ (X )), and
3. when we write τ ′ = τ1′ ⌢ · · · ⌢ τδ′ n as the concatenation of δn inner code deletion patterns, we have,
for all i and all j < S i , that τi′ ∈ D(L) preserves дj .
Proof. Let τ = τ1 ⌢ · · · ⌢ τn . By Lemma 5.6, there exist δn indices ℓ1 < · · · < ℓδ n such that, for
i = 1, . . . , δn, τ ℓi is (λ − 1)-admissible. Choose σ ∈ D(n, (1 − δ )n) via σ (X 1 . . . X n ) = X ℓ1 X ℓ2 . . . X ℓδ n , and
choose τ ′ ∈ D(δnL) via τ ′ = τℓ1 ⌢ · · · ⌢ τℓδ n . We have τ ′ ◦ ψ ◦ σ (X ) ⊑ τ ◦ ψ (X ) for all X ∈ [K]n because
τ ′ ◦ψ ◦ σ (X ) is simply the result of deleting the remaining bits in inner codewords of non-admissible indices
in τ ◦ ψ (X ). By construction, each τℓi ∈ D(L) is (λ − 1)-admissible, so we can choose S 1 , . . . , S δ n by setting
S ℓ to be the set that τℓi corrupts. Note that some S i may have size less than λ − 1, but we can arbitrarily add
elements of [K] to S i until it has λ − 1 elements. This is okay as item 3 in the corollary statement remains
true if we add elements to Si .

In our analysis, for a deletion pattern τ = τ1 ⌢ · · · ⌢ τn , we only care about the behavior of a given inner
code deletion pattern τi as far as the set Si of inner codewords дj that it corrupts; instead of considering all
possible deletion patterns τ ∈ D(nL), it suffices to only consider all possible σ , S 1 , . . . , Sδ n . This motivates
the following definition.
Definition 5.8. The signature of a deletion pattern τ is (σ , S 1 , S 2 , . . . , S δ n ), where σ , S 1 , . . . , S δ n are given
by Lemma 5.7. If the choice of σ , S 1 , . . . , Sδ n satisfying the conditions of Lemma 5.7 are not unique, then
choose one such collection of σ , S 1 , . . . , Sδ n arbitrarily and assign this collection to be the signature of τ .
Below we define the matchability relation ≺. Definition 5.11 allows us to worry only about the signature
of a deletion pattern τ rather than τ itself. Intuitively, we can think of the matchability relation ≺ as
an approximation of the subsequence relation ⊑. Proposition 5.12 establishes this relationship formally.
Specifically, it states that if τ is a deletion pattern with signature (σ , S 1 , . . . , S δ n ), then for X , Y ∈ [K]n , we
have σ (X ) ⊑ Y implies that σ (X ) has a matching in Y with appropriate parameters. This means that if
we want to show there are few incorrectly decoded codewords in a given code, it suffices to show that few
codewords have an appropriately parameterized matching in some other codeword.
14

We first define type-A and type-B pairs of indices (i, j) ∈ {1, . . . , |X |} × {1, . . . , |Y |}. Intuitively, pairs
(i, j) are type-B only if τi (ψ (X i )) has many more runs than ψ (Yj ), i.e. it is difficult to find (contiguous)
subwords of τi (ψ (X i )) as subsequences of ψ (Yj ).
Definition 5.9. Let X , Y ∈ [K]∗ be words over the alphabet [K] and let S 1 , . . . , S |X | be subsets of K. Given
a pair (i, j) ∈ {1, . . . , |X |} × {1, . . . , |Y |}, we say (i, j) is type-A with respect to X , Y , S 1 , . . . , S |X | (or simply
type-A if the parameters are understood) if X i ∈ S i or X i ≥ Yj . Call a pair (i, j) type-B with respect to
X , Y , S 1 , . . . , S |X | otherwise.
Definition 5.10. Let X , Y ∈ [K]∗ be words over the alphabet [K], let S 1 , . . . , S |X | be subsets of K, and let
s and t be positive integers. The following algorithm constructs the (s, t, S 1 , . . . , S |X | ) matching of X with
Y . Begin with a pair (a, b) = (1, 1). The first and second coordinates correspond to indices of the strings X
and Y , respectively. Define an A-move to be incrementing the first coordinate, a, by 1, and a B-move to be
incrementing of the second coordinate, b, by 1.
1. If a = |X | or b = |Y |, stop.
2. Do one of the following
(a) If the last s moves were A-moves, make a B-move.
(b) Else if the last t moves were B-moves, make an A-move.
(c) Else if (a, b) is type-A, make an A-move.

(d) Else, (a, b) must be type-B, in which case make a B-move.
3. Repeat from step 1.
Note that at the end of this algorithm, exactly one of a = |X | and b = |Y | is true. We say this matching is a
success if we ended with a = |X |, otherwise it is a failure.
Definition 5.11. Note also that the matching is uniquely determined by X , Y , S 1 , . . . , S |X | , s, t. If this matching
is a success, we say X is (s, t, S 1 , . . . , S |X | )-matachable (or has a (s, t, S 1 , . . . , S |X | )-matching) in Y , denoted
X ≺(s,t,S 1, ...,S |X | ) Y .

(20)

Proposition 5.12. Let S 1 , . . . , S δ n be subsets of [K] of size exactly λ − 1. Let τ = τ1 ⌢ · · · ⌢ τδ n ∈ D(nL)
be a deletion pattern such that for all i, τi ∈ D(L) is (λ − 1)-admissible and in particular preserves дj for all
j < S i . Suppose we have X ∈ [K]δ n and Y ∈ [K]n such that τ (ψ (X )) ⊑ ψ (Y ) (recall ⊑ is the subsequence
relation). Then X ≺(2λ , √R,S 1, ...,S δ n ) Y .
√
Proof. Let s = 2λ , t = R. Run the matching algorithm defined above to obtain a matching of X and Y .
Let M be the set of all (a, b) reached by some step of the algorithm. We wish to show this matching is a
success, i.e. that there exists some b such that (|X |, b) ∈ M, or, equivalently, there does not exist a such that
(a, |Y |) ∈ M.
Since τ (ψ (X )) ⊑ ψ (Y ), we can find τ (ψ (X )) as a subsequence of ψ (Y ) by greedily matching the bits of
τ (ψ (X )) with the bits of ψ (Y ). Let N be the set of (i, k) such that some bit of τi (ψ (X i )) is matched with some
bit in ψ (Yk ). We first establish some basic facts about M, N .
Fact 5.13.

1. (|X |, |Y |) < M.
15

Y
X

β0 κ0 βf κf

a

...

Y

...

X

b

...
...

ι0 α0 ιf αf

β 0 (α 0 (β 0 (α 0 (b))))
Y
X

β 0 (α 0 (b))

b

...
...

α 0 (β 0 (α 0 (b)))

α 0 (b)

Figure 1: Illustrations of α 0 (b), α f (b), β 0 (a), β f (a), ι 0 (b), ι f (b), κ 0 (a), κ f (a)
2. M, N ⊆ {1, . . . , |X |} × {1, . . . , |Y |}.
3. For all a ∗ ∈ {1, . . . , |X |}, b ∗ ∈ {1, . . . , |Y |}, we have {b : (a ∗ , b) ∈ M} and {a : (a, b ∗ ) ∈ M} are
intervals of consecutive integers of lengths at most t + 1 and s + 1, respectively.
4. For all i ∗ ∈ {1, . . . , |X |}, k ∗ ∈ {1, . . . , |Y |}, we have {k : (i ∗ , k) ∈ N } and {i : (i, k ∗ ) ∈ N } are
intervals of consecutive integers.
5. Let ≤ M be a relation on M such that (a, b) ≤ M (a ′, b ′ ) iff a ≤ a ′ and b ≤ b ′ . Then M is totally
ordered under ≤ M . As such, we can define next M (a, b) and prev M (a, b) to be the next larger and
next smaller element after (a, b) under ≤ M , respectively. Then next M (a, b) ∈ {(a + 1, b), (a, b + 1)}
and prev M (a, b) ∈ {(a − 1, b), (a, b − 1)}.
6. Let ≤ N be a relation on N such that (i, k) ≤ N (i ′, k ′) iff i ≤ i ′ and k ≤ k ′. Then N is totally ordered
under ≤ N . As such, we can define next N (i, k) and prev N (i, k) to be the next larger and next smaller
element after (i, k) under ≤ N , respectively. Then next N (i, k) ∈ {(i + 1, k), (i, k + 1), (i + 1, k + 1)} and
prev N (i, k) ∈ {(i − 1, k), (i, k − 1), (i − 1, k − 1)}.
7. If (a, b), (a ′ , b ′ ) ∈ M, we never have both a < a ′ and b ′ < b.
8. If (i, k), (i ′ , k ′) ∈ N , we never have both i < i ′ and k ′ < k.



For a ∈ {1, . . . , |X |} and b ∈ {1, . . . , |Y |}, define
α 0 (b) = min{a : (a, b) ∈ M}

α f (b) = max{a : (a, b) ∈ M}

ι 0 (b) = min{i : (i, b) ∈ N }

ι f (b) = max{i : (i, b) ∈ N }

β 0 (a) = min{b : (a, b) ∈ M}

β f (a) = max{b : (a, b) ∈ M}

κ 0 (a) = min{k : (a, k) ∈ N }

κ f (a) = max{k : (a, k) ∈ N }.

(21)

See Figure 1 for illustrations of the behavior of these eight functions. We first establish a few facts about the
notation α 0 , β 0 , . . . that are helpful for developing intuition and are also useful later. These proofs are more
involved than Fact 5.13 and are provided.
√
Lemma 5.14.
1. For all a ∈ {1, . . . , |X |}, if κ f (a) − κ 0 (a) < R, then there exists b ′ ∈ [κ 0 (a), κ f (a)]
such that (a, b ′ ) is type-A.
√
2. For all a ∈ {1, . . . , |X |} we have β f (a) − β 0 (a) ≤ R and for all β 0 (a) ≤ b ′ < β f (a) we have (a, b ′ ) is
√
type-B Furthermore, if β f (a) − β 0 (a) < R, then (a, β f (a)) is type-A.
3. For all b ∈ {1, . . . , |Y |}, we have ι f (b) − ι 0 (b) ≤ 2λ .
4. For all b ∈ {1, . . . , |Y |}, we have (i ′, b) is type-A for all i ′ ∈ [ι 0 (b) + 1, ι f (b) − 1].

16

Y

β0 κ0 κf βf

X

...
...

a

Figure 2: Step 2, Assume FSOC β 0 (a) ≤ κ 0 (a) ≤ κ f (a) < β f (a)
5. For all b ∈ {1, . . . , |Y |}, we have α f (b) − α 0 (b) ≤ 2λ and for all a ′ ∈ [α 0 (b), α f (b) − 1] we have (a ′, b)
is type-A. Furthermore, if α f (b) − α 0 (b) < 2λ , then (α f (b), b) is type-B.
Proof. Parts 2 and 5 follow from Definition 5.10.
For part 1, suppose for contradiction that (a, b ′ ) is type-B for all κ 0 (a) ≤ b ′ ≤ κ f (a). Then X a < S a
1
and X a < Yb ′ for all such b ′ . This means τa (ψ (X a )) has at least 2R K + 2 −X a runs while ψ (Yb ′ ) has at most
2R K +1−(X a +1) runs for κ 0 (a) ≤ b ′ ≤ κ f (a). On the other hand, we have


τa (ψ (X a )) ⊑ ψ Yκ0 (a) . . . Yκf (a) .
(22)
√
√
1
As κ f (a) − κ 0 (a) < R this means the right side of (22) has less than R · 2R K −X a = 2R K + 2 −X a runs while
the left side has at least that many runs, a contradiction.
Î ι (b)−1
For part 3, suppose for contradiction that ι f (b)−ι 0 (b)−1 ≥ 2λ . Sinceψ (Yb ) contains if′=ι (b)+1 τi ′ (ψ (X i ′ ))
0
as a strict subsequence (ψ (Yb ) additionally contains at least one bit from each of τι0 (ψ (X ι0 )) and τι f (ψ (X ι f ))),
we have
ι f −1
L
© Õ
ª
|τi ′ (ψ (X i ′ ))| ® + 2 ≤ |ψ (Yb )| = L,
L + 2 ≤ (ι f (b) − ι 0 (b) − 1) · λ + 2 ≤ ­
2
′
«i =ι0 +1
¬

(23)

a contradiction.
For part 4, suppose for contradiction that (i ′, b) is type-B for some ι 0 (b) < i ′ < ι f (b). Thus X i ′ < S i ′
1
and X i ′ < Yb . In particular, τi ′ (ψ (X i ′ )) has at least 2R K + 2 −X i ′ runs, which is more than the at-most-2R K −X i ′
runs of ψ (Yb ). However, ι 0 (b) < i ′ < ι f (b), so (i ′, b) ∈ N and in particular τi ′ (ψ (X i ′ )) ⊑ ψ (Yb ), which is a
contradiction. Note that i ′ = ι 0 (b) and i ′ = ι f (b) do not guarantee a contradiction because for such i ′, some
bits of τi ′ (ψ (X i ′ )) might be matched with other inner codewords in ψ (Y ).

The following definition of proper indices is introduced for convenience. Intuitively, indices of Y are
Y -proper if the bit-matching N consumes corresponding indices of X “slower” than in the algorithmic
matching M, and indices of X are X -proper if the bit-matching N consumes corresponding indices of Y
“faster” than in the algorithmic matching M.
Definition 5.15. We say an index in a ∈ {1, . . . , |X |} is X -proper if
β 0 (a) ≤ κ 0 (a),

β f (a) ≤ κ f (a)

(24)

and we say an index b ∈ {1, . . . , |Y |} is Y -proper if
ι 0 (b) ≤ α 0 (b),

17

ι f (b) ≤ α f (b).

(25)

b

Y
X

...

Y

...

X

ι0 α0 αf ιf

(a) Assume FSOC ι 0 (b) ≤ α 0 (b) ≤ α f (b) < ι f (b)

β 0(α 0 )

κ 0(α 0 )

b = κ f(α 0 )

β f(α 0 )

...
...

ι0 = α0 = αf

ιf

(b) ι 0 (b) = α 0 (b) = α f (b) < ι f (b)

Figure 3: Step 3

Y
X

κ f(α 0 (b))

b

b = κ f(α 0 (b))

...

Y

...

X

α 0 (b) ι 0 (b)
(a) b < κ f (α 0 (b))

...
...

α 0 (b) ι 0 (b)
(b) b = κ f (α 0 (b))

Figure 4: Step 4
Claim 5.16. For all a ∈ {1, . . . , |X |} and all b ∈ {1, . . . , |Y |}, a is X -proper and b is Y -proper.
Remark 5.17. First we illustrate how the Claim 5.16 implies Proposition 5.12. Suppose for contradiction that
Proposition 5.12 is false. Then there exists some a such that (a, |Y |) ∈ M and for all b we have (|X |, b) < M.
In particular, α f (b) < |X | for all b ∈ {1, . . . , |Y |}. By the claim, ι f (|Y |) ≤ α f (|Y |) < |X |, implying that no
bits from τ |X | (ψ (X |X | )) are matched with bits of ψ (Y ), a contradiction of τ (ψ (X )) ⊑ ψ (Y ).
Proof. Step 1. First, note that, as (1, 1) ∈ M, N , we have α 0 (1) = β 0 (1) = ι 0 (1) = κ 0 (1) = 1.
Step 2. Next, we show that for all a, if β 0 (a) ≤ κ 0 (a) then a is X -proper. That is, we show β f (a) ≤ κ f (a).
Suppose for contradiction we have κ f (a) < β f (a) so that β 0 (a) ≤ κ 0 (a) ≤ κ f (a) < β f (a) (see Figure 2). By
√
Lemma 5.14 part 2, we have β f (a)−β 0 (a) ≤ R and (a, b ′ ) is type-B for allb ′ ∈ [β 0 (a), β f (a)−1]. In particular,
√
(a, b ′ ) is type-B for all b ′ ∈ [κ 0 (a), κ f (a)]. As κ f (a) − κ 0 (a) < β f (a) − β 0 (a), we have κ f (a) − κ 0 (a) < R,
so we can apply Lemma 5.14 part 1 to obtain that (a, b ′ ) is type-A for some b ′ ∈ [κ 0 (a), κ f (a)]. This is a
contradiction as all such b ′ must be type-B.
Step 3. Next, we show that for all b, if ι 0 (b) ≤ α 0 (b) and α 0 (b) is X -proper, then b is Y -proper. That is, we
show ι f (b) ≤ α f (b). Suppose for contradiction that α f (b) < ι f (b) so that ι 0 (b) ≤ α 0 (b) ≤ α f (b) < ι f (b) (see
Figure 3a). We have α f − α 0 < ι f − ι 0 ≤ 2λ by Lemma 5.14 part 3. Thus, by Lemma 5.14 part 5, (α f (b), b) is
type-B. By Lemma 5.14 part 4, (i ′, b) is type-A for i ′ ∈ [ι 0 (b) + 1, ι f (b) − 1]. Since α f (b) ∈ [ι 0 (b), ι f (b) − 1]
we must have α f (b) = ι 0 (b), so ι 0 (b) = α 0 (b) = α f (b) (See Figure 3b). By definition of α f (b), we have
(α (b))

≥ b + 1. However, since we assumed α f < ι f , we have
next M (α f (b), b) = (α f (b), b + 1) so β f f
next N (α f (b), b) = (α f (b) + 1, b), so κ f (α f (b)) = b. Thus
β f (α 0 (b)) = β f (α f (b)) ≥ b + 1 > b = κ f (α f (b)) = κ f (α 0 (b)).

(26)

On the other hand, β f(α 0 (b)) ≤ κ f(α 0 (b)) by assumption that α 0 (b) is X -proper, which is a contradiction. This
covers all possible cases, completing Step 3.
Step 4. We prove that, for all b ∈ {1, . . . , |Y |}, if α 0 (b) is X -proper, then b is Y -proper. By Step 3, it
suffices to prove ι 0 (b) ≤ α 0 (b). Suppose for contradiction that α 0 (b) < ι 0 (b). Since (α 0 (b), b) ∈ M, we have
18

b ≤ β f (α 0 (b)). By assumption, α 0 (b) is X -proper, so β f (α 0 (b)) ≤ κ f (α 0 (b)), which means b ≤ κ f (α 0 (b)).
If b < κ f(α 0 ) , then we have (α 0 (b), κ f (α 0 (b))) ∈ N . However, (ι 0 (b), b) ∈ N , contradicting Fact 5.13 part
8. Thus, κ f (α 0 (b)) = b. But then (α 0 (b), b) = (α 0 (b), κ f (α 0 (b))) ∈ N with α 0 (b) < ι 0 (b), contradicting the
minimality of ι 0 (b).
Step 5. By the same argument as Step 4, we have that, for all a ∈ {1, . . . , |X |}, if β 0 (a) is Y -proper, then
a is X -proper.
Step 6. We prove by strong induction that for pairs (a, b), ordered by < M , we have a is X -proper and b
is Y -proper. Combining Steps 1,2, and 3, we have
β 0 (1) ≤ κ 0 (1),

β f (1) ≤ κ f (1),

ι 0 (1) ≤ α 0 (1),

ι f (1) ≤ α f (1),

(27)

where the first and third inequalities are actually equalities arising from Step 1, the second inequality is
established by Step 2, and the fourth is established by Step 3. Thus, 1 is both X -proper and Y -proper.
Now suppose we have some pair (a, b) ∈ M with (1, 1) < M (a, b) and (22) has been established for all
smaller pairs. If prev M (a, b) = (a − 1, b), then by the inductive hypothesis, we have b is Y -proper. However,
as (a − 1, b) ∈ M, we have (a, b − 1) < M, so we have β 0 (a) = b. Thus β 0 (a) is Y -proper, so a is X -proper
by Step 5. Similarly, if prev M (a, b) = (a, b − 1), then by the inductive hypothesis, we have a is X -proper.
Thus α 0 (b) = a is X -proper, so b is Y -proper by Step 4. This completes the proof of Claim 5.16, proving
Proposition 5.12.

The following proposition is the key result of this subsection. Following our approach, it should be
possible to prove this proposition for any choice of S 1 , . . . , S δ n , not just [λ − 1], . . . , [λ − 1]. However,
because of Lemma 5.23, which tells us that [λ − 1], . . . , [λ − 1] is the “worst” possible choice of S 1 , . . . , S δ n ,
it suffices to prove the proposition as stated.
Proposition 5.18. There exists a constant β > 0 such that for any fixed deletion pattern σ ∈ D(n, (1 − δ )n)
we have
(28)
Pr n [σ (X ) ≺(2λ , √R,[λ−1], ...,[λ−1]) Y ] < 2−βn .
X,Y ∼U ([K ] )

K
Proof. Let s = 2λ . With hindsight, let β = log
16R . It suffices to prove
i
h
X ≺(2λ , √R,[λ−1], ...,[λ−1]) Y < 2−βn .
Pr
X ∼U ([K ]δ n )
Y ∼U ([K ]n )

(29)

This suffices because for any σ , the distribution of σ (X ) for X ∼ U ([K]n ) is the same as X ∼ U ([K]δ n ).
Let X 1 , . . . , X δ n , Y1 , Y2 , . . . be independently chosen from [K]. Let X√= X 1 . . . X δ n , Y = Y1 . . . Yn , and
Y∞ = Y1Y2 . . . so that X ∼ U ([K]δ n ) and Y ∼ U ([K]n ). Construct a (2λ , R, S 1 , . . . , Sδ n )-matching of X in
Y∞ . Note that, as Y∞ is an infinite random string, M succeeds almost surely, i.e. ends in (|X |, b) for some
integer b.
Let M be the set of all reached states (a, b) in the matching, and let α f (b) = max{a : (a, b) ∈ M} and
β f (a) = max{b : (a, b) ∈ M} as in Proposition 5.12. Let A0 = 1, B 0 = 1. For i ≥ 1, set Ai = α f (Bi−1 )
and Bi = β f (Ai−1 ). As Ai − Ai−1 ≤ s for all i ≥ 1, we have Ai is well defined for i ≤ δn/s − 1. By the
definition of matching, M ′ succeeds if and only if M succeeds and the final position (|X |, β f (|X |)) satisfies
β f (|X |) < |Y |. It thus suffices to prove


Pr B ⌊δ n/s ⌋−1 < |Y | < 2−βn .
19

(30)

Y
X

B0

Ω(log K )

B1

B2

B3

...

...
A0

≤ 2λ

A1

A2

A3

Figure 5: Ai ’s and Bi ’s behavior
The key idea of this proof is that the Bi ’s grow much faster than the Ai ’s, so that the Bi ’s “run out of
indices in Y ” faster than the Ai ’s “run out of indices in X ”, even though Y is longer than X . In particular, by
definition of a matching, we have Ai+1 − Ai ≤ s = 2λ , but, on the other hand, we show that Bi+1 − Bi is, in
expectation, Ω(log K) (see Figure 5).
We have two technical lemmas. The proofs are straightforward, and we include them in Appendix C for
completeness.
Lemma 5.19. Let J be chosen uniformly from [K]. Let D be a random
√ variable that is 1 if J ∈ [λ − 1] and,
conditioned on a fixed J ≥ λ, is distributed as min(Geometric(J /K), R). Then E[D] ≥ (log K)/4.

Lemma 5.20. Let λ ′ ∈ [λ, K] and let J be chosen uniformly from {λ, λ + 1, . √
. . , λ ′ }. Let D be the random
variable that, conditioned on a fixed J , is distributed as min(Geometric(J /K), R). Then E[D] ≥ (log K)/4.
Claim 5.21. Let i ≥ 1. For any fixed A0 , . . . , Ai , B 0 , . . . , Bi , X 1 , . . . , X Ai , Y1 , . . . , YBi , we have

 log K
E Bi+1 − Bi |A1 , . . . , Ai , B 1 , . . . , Bi , X 1 , . . . , X Ai , Y1 , . . . , YBi >
.
4

(31)

Proof. It suffices to prove that if we additionally condition on Ai+1 − Ai < s, then the expectation is at least
(log K)/4, and that the same is true if we condition on Ai+1 − Ai = s.
√
First, note that, for 1 ≤ b < R, we have Bi+1 = Bi + b if and only if (Ai+1 , Bi + j) is √
type-B for
j ∈ {1, . . . , Bi + b − 1} and (Ai+1 , Bi + b) is type-A. If no such b exists, we have Bi+1 − Bi = R. Thus,
conditioned on fixed A0 , . . .√, Ai+1 , B 0 , . . . , Bi , X 1 , . . . , X Ai +1 , Y1 , . . . , YBi , we have Bi+1 − Bi is distributed as
min(Geometric(X Ai +1 /K), R).
Suppose we condition on Ai+1 − Ai = s. This is equivalent to saying (Ai + ℓ, Bi ) is type-A for
ℓ = 1, . . . , s − 1. However, this assertion depends only on X Ai , X Ai +1 , . . . , X Ai +s−1 , which are independent of
X Ai +1 , so we have X Ai +1 is still distributed uniformly on√[K]. If X Ai +1 ∈ [λ − 1], then Bi+1 − Bi = 1, otherwise
Bi+1 − Bi is distributed as min(Geometric(X Ai +1 /K), R), so by Lemma 5.19 on D = Bi+1 − Bi , we have
E[Bi+1 − Bi |Ai+1 − Ai = s, A1 , . . . , Ai , B 1 , . . . , Bi , X 1 , . . . , X Ai , Y1 , . . . , YBi ] >

log K
.
4

(32)

Suppose we condition on Ai+1 − Ai = s ′ < s. This is equivalent to saying (Ai + ℓ, Bi ) is type-A for
ℓ = 1, . . . , s ′ − 1 and (Ai + s ′, Bi ) is type-B. This implies X Ai +1 ≥ λ (i.e. X Ai +1 < [λ − 1]) and X Ai +1 < YBi ,
Since YBi is fixed and, without any conditioning, X Ai +1 is distributed uniformly in [K], we have X Ai +1
is distributed uniformly on√[λ, . . . , YBi ]. By the previous argument, we have Bi+1 − Bi is distributed as
min(Geometric(X Ai +1 /K), R), so by Lemma 5.20 on λ ′ = YBi and D = Bi+1 − Bi , we have
E[Bi+1 − Bi |Ai+1 − Ai = s ′ < s, A1 , . . . , Ai , B 1 , . . . , Bi , X 1 , . . . , X Ai , Y1 , . . . , YBi ] >

log K
.
4

(33)


20

Corollary 5.22. We have, for any fixed B 1 , . . . , Bi ,
E[Bi+1 − Bi |B 1, . . . , Bi ] >

1
log K.
4

(34)

1
4

log K so that


δn
1
α(k − 1) > log K · λ − 1 > 2n.
4
2

Continuing the proof of Proposition 5.18, let α =

(35)

Define the random variable Bi′ := Bi − i · α. As Bi′ and Bi uniquely determine each other, we have, by
Corollary 5.22,
′
E[Bi+1
− Bi′ |B 1′ , . . . , Bi′] = E[Bi+1 − Bi |B 1, . . . , Bi ] − α > 0.
(36)
√
′
− Bi′ | < R, so by Azuma’s Inequality (Lemma 4.2), we have
Thus, Bi′ form a submartingale with |Bi+1
!




 2

2
(α(k
−
1)/2)
n log K
α (k − 1)
α(k
−
1)
′
′
≤ exp −
< exp −
. (37)
= exp −
Pr Bk − B 1 ≤ −
√
2
8R
16R
2(k − 1) · ( R)2
Combining with (35) gives
Pr[Bk ≤ n] ≤

Pr[Bk′

− B 1′

≤ −n] ≤ Pr



Bk′

We conclude
Pr

[X

X ∼U ([K ]δ n )
Y ∼U ([K ]n )

≺(√R,2λ ,[λ−1], ...,[λ−1])

log K
) < 2−
As exp(− n 16R

n log K
16R

Y ] ≤ Pr[mδ n

− B 1′

α(k − 1)
≤−
2






n log K
< exp −
.
16R

(38)



(39)


n log K
≤ n] ≤ Pr[Bk ≤ n] < exp −
.
16R

, we have (29) is true, completing the proof of Proposition 5.18.



To conclude this section, we formalize the intuition that the “worst possible deletion pattern”, that is,
the deletion pattern that makes decoding most difficult in some sense, is the deletion pattern such that each
(λ − 1)-admissible inner deletion pattern corrupts д1 , . . . , дλ−1 . This fact is intuitive, as it is hard, for example,
to find д1 as a subsequence of a random ψ (Y ) because д1 has many runs. Thus if our deletion pattern τ
corrupts the inner codewords with the most runs, there is a greater probability that over random X , Y we have
τ (ψ (X )) is a subsequence of ψ (Y ). However, note that, to make a clean assertion, we continue to argue using
the matching relation rather than subsequence relation.
Lemma 5.23. Let r, s ∈ N and S 1 , . . . , S δ n be subsets of [K] of size exactly λ − 1. Then for all Y ∈ [K]n we
have
o
n
o
n
(40)
# X ∈ [K]δ n : X ≺(2λ , √R,S 1, ...,S δ n ) Y ≤ # X ∈ [K]δ n : X ≺(2λ , √R,[λ−1], ...,[λ−1]) Y

Proof. We start with a claim.

Claim 5.24. For every set A ⊆ [K] with size exactly λ − 1, there exists a bijection h A : [K] → [K] such that
h A (x) ∈ [λ − 1] for x ∈ A and h A (x) ≥ x for x < A.
Proof. Pair each element x ∈ A \ [λ − 1] with an element y ∈ [λ − 1] \ A arbitrarily and for each pair (x, y)
set h A (x) = y, h A (y) = x. Note this always gives x > y. This is possible as A \ [λ − 1] and [λ − 1] \ A have
the same size. Then set h A (x) = x for all other x. It is easy to check this function satisfies h A (x) ≥ x for
x < A.

21

Fix Y ∈ [K]n . For all i, let hi : S i → [λ − 1] be a bijection such that hi (x) ∈ [λ − 1] for x ∈ S i and
f (x) ≥ x for all other x. This exists by Claim 5.24. Let h : [K]δ n → [K]δ n be such that h(X 1 , . . . , X δ n ) =
h 1 (X 1 )h 2 (X 2 ) · · · hδ n (X δ n ). Since each of h 1 , . . . , hδ n are bijections, h is a bijection as well.
Let X be such that X ≺(2λ , √R,S 1, ...,S δ n ) Y . We claim h(X ) ≺(2λ , √R,[λ−1], ...,[λ−1]) Y . Let M be a
√
√
(2λ , R, S 1 , . . . , S δ n )-matching of X in Y and let M ′ be a (2λ , R, [λ − 1], . . . , [λ − 1])-matching of h(X ) in
Y . We know M is a successful matching, and we wish to show M ′ is a successful matching.
If (a, b) is type-A with respect to X , Y , S 1 , . . . , S |X | , then Yb ≤ X a or X a ∈ S a , so, by definition of h,
either h(X a ) ∈ [λ − 1] or Yb ≤ X a ≤ h(X a ), so (a, b) is type-A with respect to h(X ), Y , [λ − 1], . . . , [λ − 1].
Let ℓ ≥ 0 be an integer and let (a, b) ∈ M and (a ′, b ′ ) ∈ M ′ be the state of the matchings after the ℓth step
of the matchings of X in Y and h(X ) in Y , respectively. It is easy to see by induction that a ≤ a ′ and b ′ ≤ b;
if a < a ′ then after one move we still have a ≤ a ′, and if a = a ′ and Ms next move is an A-move, then
M ′s next move must also be an A-move. Since M succeeds, we have (|X |, b) ∈ M for some b < |Y |, so we
conclude that (|X |, b ′ ) ∈ M ′ for some b ′ ≤ b < |Y |. Thus M ′ succeeds as well.
Since h is a bijection such that
o
n
o
n
⊆ X ∈ [K]δ n : X ≺(2λ , √R,[λ−1], ...,[λ−1]) Y ,
(41)
h X ∈ [K]δ n : X ≺(2λ , √R,S 1, ...,S δ n ) Y
we have

o
n
o
n
# X ∈ [K]δ n : X ≺(2λ , √R,S 1, ...,S δ n ) Y ≤ # X ∈ [K]δ n : X ≺(2λ , √R,[λ−1], ...,[λ−1]) Y

as desired.

(42)


5.4 Technical combinatorial lemmas
Lemma 5.25. Let n be a positive integer and suppose we have 0 < β < 1. Suppose that γ = β/3, M = 2γ n ,
and ϵ ≥ 2−(γ −o(1))n/2 . Suppose G is a graph on N = K (1−o(1))n vertices such that each vertex has degree
at most d = N r for some r = r (n) = 2−(β −o(1))n . Suppose Cout is chosen as a random subset of V (G)
by including each vertex of V (G) in Cout with probability M/N . Then for sufficiently large n, we have
PrCout [|E(G ↾ Cout )| > ϵM] < 2−ω(n) .
Remark 5.26. Essentially this lemma is saying that when the edge density is extremely small, around 2−βn ,
then for all but an extremely small set of choices for Cout , Cout is extremely sparse.
Proof. Let E = E(G). We know E satisfies |E | ≤ dN /2 < N 2r .
Enumerate the edges 1, . . . , |E | arbitrarily. Let Y1 , . . . , Y |E | be Bernoulli random variables denoting
whether the ith edge is in Cout . Let Z = Y1 + · · · + Y |E | . We would like to show
Pr [Z > ϵM] < 2−n .

Cout

(43)

We do this by computing a sufficiently large moment of Z and using
Pr [Z > ϵM] ≤

Cout

E[Z k ]
.
(ϵM)k

(44)

For a tuple of (not necessarily distinct) edges (e1 , . . . , ek ), denote V (e1 , . . . , ek ) to be the set of vertices
on at least one of the edges e1 , . . . , ek . Alternatively, we say V (e1 , . . . , ek ) is the set of vertices covered by
edges e1 , . . . , ek . Note that for all e1 , . . . , ek , we have 2 ≤ V (e1 , . . . , ek ) ≤ 2k. Let Pk, ℓ = #{(e1 , . . . , ek ) :
|V (e1 , . . . , ek )| = ℓ} denote the number of ordered tuples of edges from E that cover exactly ℓ vertices.
22

Claim.
Pk, ℓ < N ℓ · r ℓ/2 · ℓ 2k+ℓ−1 · k k

(45)

Proof. We bound Pk, ℓ by first bounding the number of sets (unordered tuples) of edges covering exactly ℓ
vertices and then multiply by k!. We first compute the number of ways to construct a forest of trees covering
ℓ vertices using only edges from E. We do this by casework on the number of connected components. Let
1 ≤ c ≤ ⌊ℓ/2⌋ be an integer. To construct a forest with c connected components, we first choose c disjoint
edges e1 , . . . , ec . This can be done in at most |E | c ways. We have |V (e1 , . . . , ec )| = 2c. For c + 1 ≤ i ≤ ℓ − c,
choose a vertex v ∈ V (e1 , . . . , ei−1 ) and an edge vw such that w < V (e1 , . . . , ei−1 ). By construction, for
c + 1 ≤ i ≤ ℓ − c, we have |V (e1 , . . . , ei )| = i + c. Thus the i th edge can be added in at most (i + c − 1)d ways.
The i = ℓ − c th edge completes a forest covering ℓ vertices. Recalling that |E | < N 2r and d = N r , we have
that the total number of ways to construct a forest in this fashion is at most
|E | c · 2cd · (2c + 1)d · · · (ℓ − 1)d ≤ |E | c · d ℓ−2c · ℓ ℓ−2c < N ℓ · r ℓ−c · ℓ ℓ−2c .

(46)

We have used ℓ − c edges thus far. There are k − ℓ + c remaining edges. As |V (e1 , . . . , ek )| = ℓ, these
remaining edges must connect one of the 2ℓ pairs of vertices in V (e1 , . . . , ek−ℓ+c ). As c ≤ ⌊ℓ/2⌋ < ℓ, we
 k−ℓ+c
have k − ℓ + c < k. The remaining edges can thus be chosen in at most 2ℓ
< ℓ 2k ways. Using (46) and
multiplying by k! we have
ℓ/2
Õ

N ℓ · r ℓ−c · ℓ ℓ−2c · ℓ 2k < k k · (ℓ/2) · N ℓ · r ℓ/2 · ℓ ℓ−2 · ℓ 2k < N ℓ · r ℓ/2 · ℓ 2k+ℓ−1 · k k . (47)
c=1

√
Note that M r ≪ 1. With this claim, we have

Pk, ℓ < k! ·

E[Z k ] = E[(Y1 + · · · + Y |E | )k ]
Õ
E[Y1 · · · Yk ]
=
(e1, ...,ek )∈ {1, ..., |E | }k

=

2k
Õ

Õ

ℓ=2 |V (e1, ...,ek ) |=ℓ

=

2k
Õ

Õ

ℓ=2 |V (e1, ...,ek ) |=ℓ

=
<

<

ℓ
2k 
Õ
M
ℓ=2
2k
Õ

ℓ=2
2k
Õ
ℓ=2



N

M
N

ℓ

E[Ye1 · · · Yek ]


M
N

ℓ

· Pk, ℓ
· N ℓ · r ℓ/2 · ℓ 2k+ℓ−1 · k k

ℓ 2k+ℓ−1 · k k

< 2k · (2k)4k−1 · k k = 24k · k 5k .
Finally, choosing k = log n, we have

as desired.

E[Z k ]
24k k 5k
Pr[Z ≥ ϵM] ≤
<
<
(ϵM)k
ϵk Mk



16k 5
ϵ2γ n

k

≤



(48)

16k 5
2γ n/2

k

< 2−ω(n)

(49)


23

Lemma 5.27. Let n be a positive integer, and suppose 0 < β < 1 and γ = β/4. Suppose M = 2γ n and
ϵ ≥ 2−γ n/2 . Suppose G is a directed graph on N = K n(1−o(1)) vertices such that each vertex has outdegree at
most N r for some r = 2−(β −o(1))n . Choose a subset Cout ⊆ V (G) at random by including each vertex of V (G)
in Cout with probability M/N so that E[|Cout |] = M. Then, for sufficiently large n, we have
h n
o
i
−−→
(50)
Pr # X ∈ Cout : ∃Y ∈ Cout s. t. YX ∈ E(G) > ϵ |Cout | < 2−ω(n) .
Cout

Proof. As, by assumption, Y has outdegree at most N · r for all Y ∈ V (G), the average indegree of G is at
most N · r . Thus at most ϵ/8 fraction of all words in V (G) have indegree larger than ϵ8 · N · r . Call this set
of vertices W . We have
 

8
ϵ
E # X ∈ Cout : indegG (X ) > · N · r
= E[|Cout ∩ W |] ≤ M.
(51)
Cout
ϵ
8
Since |Cout ∩ W | is the sum of i.i.d Bernoulli random variables, we have by Lemma 4.1


 
h
1 ϵ
ϵ
ϵ i
8
Pr # X ∈ Cout : indegG (X ) > · N · r > M = Pr |Cout ∩ W | > M < e − 2 · 8 ·M < 2−ω(n) .
Cout
ϵ
4
4
(52)
−−→
−−→
Now consider the undirected graph H on V (G) such that XY ∈ E(H ) if XY ∈ E(G) and Y < W or YX ∈ E(G)
and X < W . For every vertex v, the in-edges of v in G correspond to edges in H only if the indegree is at
most ϵ8 · N · r , and the outdegree of v in G is always at most N r . Therefore the degree of every vertex in H
is at most r ′ N where r ′ = ϵ8 + 1 · r < 2−(β −γ −o(1))n .
We are including each vertex of V (G) (and thus each vertex of V (H )) in Cout independently with
probability M/N . Let ϵ ′ = ϵ/4, β ′ = 34 β, γ ′ = γ so that γ ′ = β ′/3, ϵ ≥ 2−(γ +o(1))n/2 , M = 2γ n , and
′
r ′ = 2−(β −o(1))n . By Lemma 5.25 for β ′, γ ′, M, ϵ ′, and r ′, and H , we have for sufficiently large n that

ϵ 
Pr E(H ↾ Cout ) > M < 2−ω(n) .
(53)
Cout
4
Also, by Chernoff bounds, we have




3
3
−Ω(M )
=⇒ Pr |Cout | < M < 2−ω(n) .
(54)
Pr |Cout | < M < 2
Cout
Cout
4
4
Note that if the number of X such that indegG↾Cout (X ) > 0 at least ϵ |Cout |, that is,
n
o
−−→
# X ∈ Cout : ∃Y ∈ Cout s. t. YX ∈ E(G) > ϵ |Cout |,

(55)

then one of the following must be false. .
1. |Cout | ≥ 34 M

2. #{X ∈ Cout : degH ↾Cout (X ) > 0} ≤ ϵ2 M
3. |Cout ∩ W | ≤ ϵ4 M
Indeed, suppose to the contrary all of these were true. The number of vertices in Cout ∩ W with positive
indegree in G ↾ Cout is at most |Cout ∩W | ≤ ϵ4 M. If a vertex X ∈ Cout \W has positive indegree in G ↾ Cout
−−→
then there exists Y ∈ Cout such that YX ∈ E(G), so XY ∈ E(H ) by definition of H and thus degH ↾Cout (X ) > 0.
Thus the number of vertices in Cout \W with positive indegree is at most ϵ2 M by property 2. Hence the total
number of vertices in Cout with positive indegree in G ↾ Cout is at most 34 ϵM ≤ ϵ |Cout |.
Each of items 1, 2, and 3 is false with probability 2−ω(n) by (52), (53), and (54), so the probability any
of them occur is at most 2−ω(n) , as desired.

24

5.5 Proof of Construction (Theorem 2.2)
Proof of Theorem 2.2. We would like to show there exists a code C and an ϵ = o N (1) such that, for any
deletion pattern τ deleting pN bits,
#{x ∈ C : ∃y ∈ C s. t. x , y and τ (x) ≤ y} ≤ ϵ |C |.
For Y ∈ [K]n , define

f (Y ) =

Pr

Z ∼U ([K ]δ n )

h
i
Z ≺(2λ , √R,[λ−1], ...,[λ−1]) Y .

(56)

(57)

Let σ ∈ D(n, (1 − δ )n) be a deletion pattern for our outer code [K]n . Let S 1 , . . . , S δ n be subsets of [K]
−−→
∗
be the graph on the vertex set [K]n such that YX is an edge if and only
of size exactly λ − 1. Let G σ,S
1, ...,S δ n
if σ (X ) ≺(2λ , √R,S 1, ...,S δ n ) Y . Note that for all σ ∈ D(n, (1 − δ )n) and all Y ∈ [K]n we have, by Lemma 5.23,
#{X ∈ [K]n : σ (X ) ≺(2λ , √R,S 1, ...,S δ n ) Y } = K (1−δ )n · #{Z ∈ [K]δ n : Z ≺(2λ , √R,S 1, ...,S δ n ) Y }

≤ K (1−δ )n · #{Z ∈ [K]δ n : Z ≺(2λ , √R,[λ−1], ...,[λ−1]) Y }

= K n · f (Y ).

(58)

∗
.
In the graph language, this means every Y ∈ [K]n has outdegree at most K n · f (Y ) in every G σ,S
1, ...,S δ n
We remove all Y with large f (Y ). Let β = log K/16R. By Proposition 5.18, we know the average
value of f (Y ) is 2−βn . Hence at most K n /2 such Y satisfy f (Y ) ≥ 2 · 2−βn . These are the easily disguised
candidate codewords mentioned in §2. There is thus a set W ⊆ [K]n such that |W | = K n /2 and each
Y ∈ W satisfies f (Y ) < 2 · 2−βn = 2−(β −o(1))n . For all σ ∈ D(n, (1 − δ )n), S 1 , . . . , S δ n , consider the subgraph
∗
↾ W . By construction, for all σ , S 1 , . . . , S δ n , the outdegree of every vertex of
G σ,S 1, ...,S δ n := G σ,S
1, ...,S δ n
n
G σ,S 1, ...,S δ n is at most (K /2) · r for some r = 2−(β −o(1))n .
Let γ = β/4. Let M = 2γ n and ϵ = 2−γ n/2 . Choose a subset Cout ⊆ W by including each vertex of W in
Cout independently with probability M/|W | so that E[|Cout |] = M.
By Lemma 5.27 for N = K n /2, β, γ , M, ϵ, r, and G σ,S 1, ...,S δ n , we have that, for all σ and sufficiently large
n,
h
i
−−→
Pr #{X ∈ Cout : ∃Y ∈ Cout s. t. YX ∈ E(G σ,S 1, ...,S δ n )} > ϵ |Cout | < 2−ω(n) .
(59)
Cout

This is equivalently
h
i
Pr #{X ∈ Cout : ∃Y ∈ Cout s. t. σ (X ) ≺(2λ , √R,S 1, ...,S δ n ) Y } > ϵ |Cout | < 2−ω(n) .
Cout

(60)

K δn
Union bounding over the at-most-2n possible values of σ and λ−1
values of S 1 , . . . , Sδ n gives
h
i

Pr ∃σ , S 1 , . . . , S δ n s. t. # X ∈ Cout : ∃Y ∈ Cout s. t. σ (X ) ≺(2λ , √R,S 1, ...,S σ n ) Y > ϵ |Cout |
Cout



K
< 2 ·
λ−1
n

δn

· 2−ω(n)

< 2n · 2nδ (λ−1) log K · 2−ω(n) = 2−ω(n) .

(61)

Additionally, with probability approaching 1, |Cout | ≥ 34 M. Thus, there exists a Cout with |Cout | ≥ 43 M
[K ] 
such that the following holds for all σ ∈ D(n, (1 − δ )n) and all S 1 , . . . , S δ n ∈ λ−1
: at most ϵ |Cout | of the
√
λ
codewords X are (2 , R, S 1 , . . . , Sδ n ) matchable in some other codeword Y ∈ Cout .
25

By Lemma 5.7, there exists σ ∈ D(n, (1 − δ )n) and τ ′ ∈ D(δnL) such that the following holds: If we
write τ ′ = τ1′ ⌢ · · · ⌢ τδ′ n then each τi′ is (λ − 1)-admissible and preserves all дj for all j not in some
size-λ − 1 set Si , and furthermore we have τ ′(ψ (σ (X ))) ⊑ √τ (ψ (X )) for all X ∈ [K]n . By choice of Cout , for
at least (1 − ϵ)|Cout | choices of X ∈ Cout , σ (X ) is not (2λ , R, S 1 , . . . , S δ n ) matchable in all Y ∈ Cout . Thus,
for these X , we have τ ′(ψ (σ (X ))) @ ψ (Y ) for all Y ∈ Cout by Lemma 5.12. Since τ ′(ψ (σ (X ))) ⊑ τ (ψ (X ))
for all X ∈ [K]n , we have for these (1 − ϵ)|Cout | choices of X that τ (ψ (X )) @ ψ (Y ) for all Y ∈ Cout . Thus,
choosing C = ψ (Cout ) gives our desired average deletion code.
Recall λ is the smallest integer such that (1 +p)/2 < 1 − 2−λ and δ = 1 − 2−λ −p so that 2λ = Θ(1/(1 −p))
λ+5
2
and δ = Θ(1 − p). Recall K = 2 ⌈2 /δ ⌉ and R = 4K 4 so that K = 2Θ(1/(1−p) ) . The rate of the outer code is
log 2γ n /n log K and the rate of the inner code is log K/L. The total rate is thus
R =

2
log K
−2Θ(1/(1−p) )
.
=
2
48R · 2R K

This completes the proof of Theorem 2.2.

(62)


6 Relating zero-rate threshold of online and adversarial deletions
6.1 Proof that p0(adv) =

1
2

if and only if p0(on,d) =

1
2

Recall that the zero-rate threshold for adversarial deletions, p0(adv) , is the supremum of all p such that there
exists a family of code C ⊆ {0, 1}n with |C | = 2Ω(n) satisfying LCS(C) > (1 − p)n. Additionally, recall that
the deterministic zero-rate threshold for online deletions, p0(on,d) , is the supremum of p such that there exist
families of deterministic codes with rate bounded away from 0 that can correct against pn online deletions
in the average case (when a uniformly random codeword is transmitted). That is, when a uniformly random
codeword is transmitted, the probability of a decoding error, over the choice of the codeword and possibly the
randomness of the online channel strategy, is o(1) in the block length of the code. Since an online strategy
can guess the minority bit in the codeword and delete all its occurrences, adversary can always delete the
majority bit, we trivially have
1
(63)
p0(adv) ≤ p0(on,d) ≤ .
2
(adv)

is based on the code construction in [3] and
Recall that the currently best known lower bound on p0
√
(adv)
implies p0
≥ 2 − 1. An outstanding question in this area is whether p0(adv) = 1/2. Our main result in
this section ties this question to the corresponding question for online deletions. Namely, we have
Theorem 6.1. If p0(adv) =

1
2

if and only if p0(on,d) = 21 .

By virtue of (63), Theorem 6.1 follows if we show that p0(adv) < 21 implies p0(on,d) < 21 . Our result is
a negative result against deterministic codes, and our argument does not immediately extend to stochastic
codes. While we expect such a result to exist, we elaborate §6.2 on the current limitations of our approach
to proving a negative result against stochastic codes.
The idea of the proof of Theorem 6.1 is based on a suitable adaptation of the “wait-push” idea of [1].
We wait qn bits until we know the codeword, then push so that it is confused with another codeword. In
the first wait phase, we delete the minority bit for a budget of qn/2 deletions, and while we push we need at
most (1 − q)np0(adv) deletions. If we assume that p0(adv) < 21 , we end up with a total of αn deletions for some
α < 12 . The exact details are more subtle, but this is the rough idea.
From the definition of p0(adv) , we have the following fact.
26

Fact 6.2. For any R > 0 and p > p0(adv) , there exists n 0 such that for all n ≥ n 0 , for any C ⊆ {0, 1}n with
|C | ≥ 2 Rn , there exist two strings x, y ∈ C such that LCS(x, y) > (1 − p)n.
Corollary 6.3. For any R > 0 and p > p0(adv) , there exists n 0 such that for all n ≥ n 0 , for any C ⊆ {0, 1}n
with |C | ≥ 2 Rn , there exists C ′ ⊆ C such that |C ′ | ≥ |C | − 2 Rn/2 , and all elements of C ′ are confusable with
another element of C. That is, for all x ∈ C ′ there exists y ∈ C such that x , y and LCS(x, y) > (1 − p)n.
Proof. We can apply Fact 6.2 for R ′ = R/2. Start with C ′ = ∅. While |C \ C ′ | > 2 Rn/2 , find an x that is

confusable with some y in C and add it to C ′. This is possible by Fact 6.2.
The following is the precise statement of our result relating the zero-rate thresholds for online and
adversarial deletions.
Theorem 6.4. We have
p0(on,d) ≤

1
3 − 2p0(adv)

(64)

.

In particular, if p0(adv) < 21 , then p0(on,d) < 12 .
Remark 6.5. If it is the case that the bound in [3] is tight and p0(adv) =
gives p0(on,d) ≤ 0.4605.

√

2 − 1 ≈ 0.414, then Theorem 6.4

The rest of this section is devoted to proving Theorem 6.4. We start with the following helpful definition.
Definition 6.6. Given a code C and a codeword x ∈ C passing through an online deletion channel, define the
wait phase and the push phase for a codeword as follows. Let q x n be the smallest index such that x 1 . . . x qx n
uniquely determines the codeword. The wait phase refers to the time until Adv receives bit q x n, but not
acted on it (chosen whether to transmit or delete it). Thus in the wait phase Adv receives bits 1, . . . , q x n and
has acted on bits 1, . . . , q x n − 1. The push phase is the time after the end of the wait phase. We say the wait
length of x is q x n and the push length is (1 − q x )n.
For a codeword x, let q x denote the relative wait length (wait length divided by n), and let r x,b denote
number b-bits that appear in x 1x 2 . . . x qx n , so that r x,0 +r x,1 = q x . Let bx ∈ {0, 1} denote the bit that appears
more frequently in x 1 . . . x qx n (break ties arbitrarily).
Proof of Theorem 6.4. Since p0(on,d) ≤ 12 , (64) holds if p0(adv) = 21 , so assume p0(adv) < 12 .
Let p be such that
1
1
.
>p >
(adv)
2
3 − 2p

(65)

0

We show that, for large enough n, when Adv gets pn online deletions, he can, with constant probability
independent of n, guarantee that, if the encoder sends x ∈ C, the decoder receives a string s that is a substring
of y ∈ C where x , y.
Call a pair of codewords x, y online-confusable if q x = qy ≤ 1 − p, r x,0 = ry,0 , bx = by , and
LCS(x[q x n :], y[q x n :]) > (1 − q x )(1 − p0(adv) )n.

(66)

For an online-confusable pair x, y, let s ∗ (x, y) denote a common subsequence of x[q x n :] and y[q x n :] with
(adv)
)n, and let s(x, y) denote the string (bx )r x,b n s ∗ (x, y). Note that s(x, y) is a
length at least (1 − q x )(1 − p0

27

common substring of x and y and, by choice of p in (65) has length at least
|s(x, y)| = r x,b n + (1 − q x )(1 − p0(adv) )n
qx n
≥
+ (1 − q x )(1 − p0(adv) )n
 
2

1
(adv)
(adv)
− p0
qx n
= 1 − p0
−
2




1
(adv)
(adv)
− p0
(1 − p) n
≥ 1 − p0
−
2
> (1 − p)n ,

(67)

where the last step follows from the bound on p in (65).
We now claim we can find many disjoint online-confusable pairs. For fixed q ∗ , r ∗ , b ∗ , let
C(q ∗ , r ∗ , b ∗ ) := {x ∈ C : q x = q ∗, r x,b ∗ = r ∗ , bx = b ∗ }.

(68)
∗

By Lemma 6.2 on the set {x[q ∗n :] : x ∈ C(q ∗, r ∗ , b ∗ )}, among any 2 Rn/2 (in fact, any 2 R(1−q )n/2 ) codewords
in C(q ∗ , r ∗ , b ∗ ), there exists some two codewords x and y in C(q ∗ , r ∗ , b ∗ ) such that LCS(x[q ∗n :], y[q ∗n :
]) > (1 − q ∗ )(1 − p0(adv) )n. Thus, among any 2 Rn/2 codewords in C(q ∗ , r ∗ , b ∗ ), there are some two that are
online-confusable. Thus for every q ∗ , r ∗ , b ∗ , we can construct disjoint pairs of codewords (x, y) that are
online-confusable, so that all but 2 Rn/2 of the elements of C(q ∗ , r ∗ , b ∗ ) are paired. For (x, y) in a pair, call x
and y partners. Thus, all but 2n 2 · 2 Rn/2 of the elements of C have a partner. For sufficiently large n, this
means that at least 0.99|C | elements have a partner.
The online channel choose to run one of the following strategies, each with probability 12 .
1. Strategy 1
(a) Choose a bit b uniformly from {0, 1}.

(b) During the wait phase, delete every x i = 1 − b. After the wait phase, we know the codeword x
and have transmitted r x,b n copies of the bit b.
(c) If x < C(q x , r x,b , b) (i.e. x ∈ C(q x , r x,1−b , 1 − b)) or x has no partner codeword, transmit the
remaining bits (i.e. give up).
∗ by the canonical common subsequence
(d) If x ∈ C(q x , r x,b , b) and x has a partner y, then let s xy

∗ | ≥ (1 − q )(1 − p (adv) )n. Since we know that the remaining bits sent by the
of x ∗ , y ∗ with |s xy
x
0
encoder is x ∗ , we can delete bits so that the decoder receives s ∗ .

(e) If the online channel reaches pn deletions at any point, transmit the remaining bits.
2. Strategy 2
(a) Transmit the first (1 − p)n bits.

(b) Delete the last pn bits.

The idea behind the strategy is that either the wait phase is short, in which case strategy 1 requires
fewer than n/2 deletions, or the wait phase is long in which case strategy 2 gives less than n/2 deletions.
In particular with probability 12 , we employ a strategy (either strategy 1 or strategy 2) that, with constant
probability, needs at most min(q x n, q x n/2 + (1 − q x )p0(adv) n) deletions, and we check this is at most pn.

28

Suppose for codeword x ∈ C, the wait length is q x n. Condition on the fact that x has a partner y with
∗ of x ∗ and y ∗ with |s ∗ | ≥ (1 − q )(1 − p (adv) )n. By the
q x = qy and canonical common subsequence s xy
x
xy
0
above argument, this assumption holds with probability more than 0.99.
If q x > 1 − p, then knowing x 1 . . . x (1−p)n does not uniquely determine the codeword x, so there exists
another codeword y ∈ C with the same prefix y1 . . . y(1−p)n . Then when the encoder sends each of x and
y, the online channel applying strategy 2 transmits the same string x 1 . . . x (1−p)n = y1 . . . y(1−p)n . Since we
assume the choice of codeword in C is uniformly at random, x and y are equally likely to be transmitted, so
the decoder fails in this case with probability at least 12 .
If q x ≤ 1 − p, then with probability 12 over the choice of b, we have x ∈ C(q x , r x,b , b), in which case
strategy 1 reaches step (d). Since x ∈ C(q x , r x,b , b), we have x 1 . . . x qx n has majority bit b, so step (b) deletes
∗ | ≥ (1 − q )(1 − p (adv) )n, step (d) deletes |x ∗ | − |s ∗ | ≤ (1 − q )p (adv) n bits.
at most q x n/2 bits. Since |s xy
x
x 0
xy
0
The total number of bits required by strategy 1 is thus


 




qx n
1
1
+ (1 − q x )p0(adv) n = p0(adv) +
− p0(adv) q x n < p0(adv) +
− p0(adv) (1 − p) n < pn
(69)
2
2
2
∗ for both x and y being sent
by our choice of p. Because x and y are partners, the encoder receives b qx n s xy
through the online channel. Again, as each of x and y is equally likely, the decoder fails with probability at
least 21 .
We have shown that with probability at least 0.99 over the choice of codeword, either strategy 1 chooses
the correct value of b with probability 12 , and thus causes decoding error with probability at least 14 , or strategy
2 causes decoding error with probability at least 12 . Adv chooses the “correct” strategy with probability 21 ,
1
so with total probably at least 0.99 · 21 · min( 14 , 21 ) > 10
, there is a decoding error, as desired.


6.2 Extending to stochastic codes
It is natural to wonder whether the above conditional negative result on deterministic coding against online
deletions with deletion fraction approaching 1/2 can be extended to stochastic codes. Indeed, [1] and [8],
provide tight upper bounds for the capacities of the online erasure and substitution channels, respectively.
Both works provide online channels that cause constant probability decoding errors for both deterministic
and stochastic codes. Both use a two-stage strategy. In [1], the authors use a “wait-push” strategy to construct
an online erasure adversary that, for some transmitted word x, erases none of the first qn bits, for suitable
0 < q < 1, then suitably chooses a random codeword x ′ , and erases all bits x i for which i > qn and x i , x i′.
In [8], the authors use a “babble-push” strategy to construct an online substitution adversary that, for some
transmitted word x, randomly flips q ′n of the first qn bits for some 0 < q ′ < q < 1, then suitably chooses a
random codeword x ′, and with probability 1/2 flips each bit x i for which i > qn and x i , x i′ .
A key difference between our wait-push strategy and the strategies of [1] and [8] is that they do not require
the online adversary to know the transmitted word exactly - they simply need a guarantee that, with constant
probability, the codeword x ′ that they are “pushing to” (i) has low Hamming distance from the transmitted
word and (ii) is encoded by a different message. However, our wait-push strategy requires us to wait until
we know the transmitted codeword exactly, so that we can identify the LCS between the transmitted word x
and the word x ′ we are pushing to. In the case that the length of the wait phase, qn, is large (say, close to
n), our online channel against deterministic codes can still guarantee constant probability of error by, with
probability 1/2, choosing a different strategy that simply deletes the last pn bits. However, this patch of
choosing a different strategy doesn’t work in the stochastic case, since a stochastic code can have a message
be identified using a small fraction of the bits while individual codewords need many bits to be identified.
In such a code, the wait-push strategy must wait a long time until it knows the codeword exactly and is
thus expensive, while the “delete the last pn bits” strategy obscures only the codeword but not the message.
29

Stochastic codes with this description exist in the literature. One example is the mega-subcode construction
of [4], which encodes a message independently into t different stochastic codes and concatenates the results:
in this construction, the message can be identified in the first n/t bits, but an online channel must see at least
n(t − 1)/t bits to identify the codeword.
In spite of these obstacles to obtaining a negative result for stochastic codes, our result for the deterministic
case is still strong evidence that the zero rate thresholds for online and adversarial deletions are either both
or neither 1/2. In the oblivious error model, we simultaneously constructed deterministic codes under an
average error criterion and stochastic codes under a worst case error criterion for p approaching 1, suggesting
that for the online setting the zero-rate threshold and deterministic zero-rate thresholds are the same. As a
caution, we note that this is not always the case [9]: for online erasure channels with one bit of delay, the
capacity of the channel for deterministic codes under average error criterion is 1 − 2p, while for stochastic
codes it is 1 − p.

7 Conclusion
7.1 Decoding deletions vs. insertions and deletions
A lemma due to Levenshtein [24] states that a code C can decode against pn adversarial deletions if and only
if it can decode against pn adversarial insertions and deletions.
In the oblivious error model, decoding insertions vs insertions and deletions are not the same. In
decoding against oblivious deletions, we not only need to worry about whether two codewords are confusable
by insertions and deletions, but also the number of ways in which they are confusable. In particular, when
the fraction of oblivious deletions is greater than 12 , it is inevitable that there are codewords c and c ′ that are
confusable, but we need the number of deletion patterns τ that confuse them, i.e. with τ (c) ⊑ c ′ or τ (c ′ ) ⊑ c,
to be small.
It may be possible to extend our oblivious deletion construction to oblivious insertions and deletions by
tweaking the parameters. This was the case for bridging the gap between efficiently decoding adversarial
deletions [16] and efficiently decoding adversarial insertions and deletions [13]. Our analysis for deletions
analyzes runs of 0s and 1s, but perhaps it would be possible to analyze insertions and deletions by relaxing
the definition of a run to be “a subword with at least 0.9 density of 0s or 1s.” For now, however, we leave the
case of correcting a fraction of oblivious insertions and deletions approaching 1 as an open problem.

7.2 Open problems
These remain a number of open questions concerning deletion codes. Our work brings to the fore a few
more.
(adv)

1. What is the zero-rate threshold p0

for adversarial deletions?

2. We showed the existence of codes that decode against pn oblivious deletions for any p < 1. Can we
modify the proof to show existence of codes decoding against a combination of pn oblivious insertions
and deletions for every p < 1?
3. Can we adapt our existence proof of codes for oblivious deletions to obtain explicit codes that are
constructable, encodable, and decodable in polynomial time?
4. For erasures, the capacity of the random error channel and the capacity of the oblivious error channel
are both 1 − p. For bit flips, the random and oblivious error channels also have the same capacity at
1 − h(p). Can we construct codes that decode oblivious deletions with rate approaching the capacity of
30

the random deletion channel (note this capacity itself is not known)? On the other end, could we upper
bound the best possible rate for correcting a fraction p of oblivious deletions by o(1 − p) as p → 1?
Such an upper bound would fundamentally distinguish the behavior of the deletions from errors and
erasures.
5. Can one find deterministic codes correcting p fraction of online deletions when p approaches 21 ? By
Theorem 6.1, this would imply p0(adv) = 1/2.
6. Given the discussion in §6.2, can we extend our results against online deletions to stochastic codes,
showing that if p0(adv) < 1/2 then there do not exist stochastic codes correcting a fraction of online
deletions approaching 1/2?

8 Acknowledgements
The authors would like to thank Joshua Brakensiek and Boris Bukh for helpful discussions. The authors
would also like to thank anonymous reviewers for helpful feedback on earlier versions of this paper.

References
[1] Raef Bassily and Adam D. Smith. Causal erasure channels. In Proceedings of the Twenty-Fifth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7,
2014, pages 1844–1857, 2014.
[2] Boris Bukh and Venkatesan Guruswami. An improved bound on the fraction of correctable deletions.
In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2016, Arlington, VA, USA, January 10-12, 2016, pages 1893–1901, 2016.
[3] Boris Bukh, Venkatesan Guruswami, and Johan Håstad. An improved bound on the fraction of
correctable deletions. IEEE Trans. Information Theory, 63(1):93–103, 2017.
[4] Zitan Chen, Sidharth Jaggi, and Michael Langberg. A characterization of the capacity of online
(causal) binary channels. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory
of Computing, STOC ’15, pages 287–296, New York, NY, USA, 2015. ACM.
[5] Imre Csiszár and Prakash Narayan. Arbitrarily varying channels with constrained inputs and states.
IEEE Transactions on Information Theory, 34(1):27–34, 1988.
[6] Imre Csiszár and Prakash Narayan. Capacity and decoding rules for classes of arbitrarily varying
channels. IEEE Transactions on Information Theory, 35(4):752–769, 1989.
[7] Daniel Cullina and Negar Kiyavash. An improvement to Levenshtein’s upper bound on the cardinality
of deletion correcting codes. IEEE Trans. Information Theory, 60(7):3862–3870, 2014.
[8] Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. Upper bounds on the
capacity of binary channels with causal adversaries. IEEE Trans. Information Theory, 59(6):3753–
3763, 2013.
[9] Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, and Anand D. Sarwate. A bit of delay is sufficient
and stochastic encoding is necessary to overcome online adversarial erasures. In IEEE International
Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 880–884,
2016.
31

[10] Suhas Diggavi and Matthias Grossglauser. On transmission over deletion channels. In Proceedings
of the 39th Annual Allerton Conference on Communication, Control, and Computing, pages 573–582,
2001.
[11] Eleni Drinea and Michael Mitzenmacher. On lower bounds for the capacity of deletion channels. IEEE
Trans. Information Theory, 52(10):4648–4657, 2006.
[12] Eleni Drinea and Michael Mitzenmacher. Improved lower bounds for the capacity of i.i.d. deletion and
duplication channels. IEEE Trans. Information Theory, 53(8):2693–2714, 2007.
[13] Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for high-noise and
high-rate regimes. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona,
Spain, July 10-15, 2016, pages 620–624, 2016.
[14] Venkatesan Guruswami and Ray Li. Efficiently decodable codes for the binary deletion channel. CoRR,
abs/1705.01963, 2017.
[15] Venkatesan Guruswami and Adam D. Smith. Optimal rate code constructions for computationally
simple channels. J. ACM, 63(4):35:1–35:37, 2016.
[16] Venkatesan Guruswami and Carol Wang. Deletion codes in the high-noise and high-rate regimes. IEEE
Trans. Information Theory, 63(4):1961–1970, 2017.
[17] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: codes for insertions and
deletions approaching the singleton bound. In Proceedings of the 49th Annual ACM SIGACT Symposium
on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 33–46, 2017.
[18] Adam Kalai, Michael Mitzenmacher, and Madhu Sudan. Tight asymptotic bounds for the deletion
channel with small deletion probabilities. In IEEE International Symposium on Information Theory,
ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings, pages 997–1001, 2010.
[19] Yashodhan Kanoria and Andrea Montanari. Optimal coding for the binary deletion channel with small
deletion probability. IEEE Trans. Information Theory, 59(10):6192–6219, 2013.
[20] Ian A. Kash, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman. On the zero-error capacity
threshold for deletion channels. In Information Theory and Applications Workshop, ITA 2011, San
Diego, California, USA, February 6-11, 2011, pages 285–289, 2011.
[21] Ankur A. Kulkarni and Negar Kiyavash. Nonasymptotic upper bounds for deletion correcting codes.
IEEE Trans. Information Theory, 59(8):5115–5130, 2013.
[22] Michael Langberg. Oblivious communication channels and their capacity. IEEE Trans. Information
Theory, 54(1):424–429, 2008.
[23] Amos Lapidoth and Prakash Narayan. Reliable communication under channel uncertainty. IEEE Trans.
Information Theory, 44(6):2148–2177, 1998.
[24] Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals.
Dokl. Akad. Nauk, 163(4):845–848, 1965 (Russian). English translation in Soviet Physics Doklady,
10(8):707-710, 1966.
[25] Vladimir I. Levenshtein. Bounds for deletion/insertion correcting codes. In Proceedings of the IEEE
International Symposium on Information Theory, 2002.
32

[26] Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels.
Probability Surveys, 6:1–33, 2009.
[27] Mojtaba Rahmati and Tolga M. Duman. An improvement of the deletion channel capacity upper
bound. In 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton
2013, Allerton Park & Retreat Center, Monticello, IL, USA, October 2-4, 2013, pages 1221–1225,
2013.

A

Relating average-case and worst-case miscommunication probability

In this appendix, we prove the following lemma, which shows that constructing (deterministic) codes
decodable against oblivious deletions in the average case (over random messages, in the sense of Theorem 2.2),
suffices to construct randomized codes with low decoding error probability for every message, as guaranteed
by Theorem 1.2.
Lemma A.1. Let p ∈ (0, 1). Suppose we have a family of codes C of length n and rate R such that, for any
deletion pattern τ with at most pn deletions, at most ϵ = on (1) of the codewords are decoded incorrectly.
Then, for any δ < 21 , provided n is sufficiently large, we can find a family of stochastic codes C ′ of length n
and rate R(1 − δ ) − o(1) that corrects pn oblivious deletions with probability 1 − 3ϵ.
Proof. For set of codewords C ∗ , a pair (c, τ ) (where c ∈ C ∗ and τ is a deletion pattern) is said to be C ∗ -bad if
τ (c) ⊆ c ′ for some c ′ ∈ C ∗ \ {c}, and C ∗ -good otherwise.
Let M = |C | = 2 Rn . For any τ , let Aτ denote the set of c such that (c, τ ) is C-bad. Then |Aτ | ≤ ϵ |C | by
assumption that C decodes against pn deletions
in the average case. Let d = ⌈h(p)/R⌉ be a constant over
n
d
varying n, so that there are at most M > pn choices of τ .

Let t = M δ , and N = ⌊M 1−δ /2⌋. We construct C ′ iteratively. For 1 ≤ k ≤ N , chose a random subset of
k−1 E to form E . With these sets of codewords, we associate each message
exactly t codewords from C \ ∪i=1
i
k
mi with a set Ei . We encode each message mi by choosing uniformly at random one of t codewords in some
set Ei .
Note that C ′ ⊆ C and |C ′ | = N t = M/2. It is easy to see the rate of C ′ is R(1 − δ ) − o(1).
We claim that, with positive probability over the choice of C ′, C ′ corrects pn oblivious deletions with
probability 1 − 3ϵ. Define Bτ to be all c such that (c, τ ) is C ′-bad. As Bτ ⊆ Aτ , we have |Bτ | ≤ ϵM.
We wish to show that the probability there exists an Bτ and a message mi with encoding set Ei such that
|Bτ ∩ Ei | ≥ 3ϵ |Ei | is less than 1. Fix a τ . We show that the probability |Bτ ∩ Ei | ≥ 3ϵ |Ei | is tiny. When
we chose Ei , we can imagine we picked the t elements of Ei one after the other. Each one was chosen from
at least M/2 codewords, so each codeword lands in |Bτ ∩ Ei | with probability at most ϵM/(M/2) = 2ϵ. By
Chernoff bounds, Pr [|Bτ ∩ Ei | ≥ 3ϵ |Ei |] ≤ e −t /3 . By union bound over all Ei and all Bτ , we have
Pr [∃Ei ∃τ : |Bτ ∩ Ei | ≥ 3ϵ |Ei |] ≤ N · M d · e −t /3 < M d+1 /e M
This is less than 1 for n >
1 − 3ϵ, as desired.

2
δR

δ /3

(70)

log(3(d + 1)), so our code corrects pn oblivious deletions with probability


B Comparison of oblivious deletions with oblivious bit flips
First, for completeness, we outline the proof that that there exist codes against oblivious bit flips of rate
matching the capacity of the binary symmetric channel. After this, we show that it is not possible to follow
33

the same approach to construct codes against oblivious deletions.
Theorem B.1 ([22, 5]). For every p ∈ [0, 1/2), and every R < 1 − h(p), there exists a binary code family of
rate R that can correct a fraction p of oblivious bit flips. 4
Proof. We consider a stochastic code C where each message m is mapped uniformly into a set E(m) of size
t. Choose t = n and ϵ = 1/log n. This code decodes successfully if, for all m,


Ø


′
Bpn (c ) ≥ 1 − ϵ
Pr c + e ∈
c ∈E(m) 

c ∈C\E(m)



(71)

where Bpn (x) ⊆ {0, 1}n is the set of all words within Hamming distance pn of x.
Choose C to have 2 Rn codewords at random. Fix a message m, the rest of the codeword C \ E(m), and
the error vector e. We have
Pr

c∼{0,1}n



Rn
h(p)n
Ø


′
c ∈
 ≤ 1 |C | · |Bpn (0)| ≈ 2 · 2
B
(c
+
e)
,
pn


2n
2n


c
∈C\E(m)



(72)

which is 2−Ω(n) if R < 1 − h(p). In this case





Ø




′ 


Bpn (c ) < 1 − ϵ 
Pr  Pr c + e <
E(m) c ∈E(m) 


c ∈C\E(m)








Ø




= Pr  Pr c <
Bpn (c ′ + e) < 1 − ϵ 
E(m) c ∈E(m) 



 c ∈C\E(m)




Ø


Bpn (c ′ + e) > ϵt 
= Pr  E(m) ∩
E(m) 

c ∈C\E(m)


2
≤ 2−Ω(ϵ nt ) = 2−Ω̃(n ) .

(73)

Thus, applying a union bound over all m and error vectors e, we get





Ø




2
2
′ 


Bpn (c ) > ϵ  ≤ 2 Rn · 2n · 2−Ω̃(n ) ≤ 2−Ω̃(n ) .
Pr ∃m : Pr c + e ∈
C 
c ∈E(m) 


c ∈C\E(m)





(74)

Thus when R < 1 −h(p), we can construct a rate R stochastic code correcting w.h.p. p oblivious bit flips.



For oblivious deletions the above technique does not work. This is established by the following lemma.
Lemma B.2. Let C be a random length n rate R stochastic binary code such that each message is encoded
uniformly at random in one of t codewords. If p ≥ 0.4 and 0 < ϵ < 1, then for any message m and deletion
pattern τ we have


Pr
C

Pr [∃c ′ ∈ C \ E(m) : τ (c) ⊑ c ′] > ϵ

c ∈E(m)

> 2−h(p)n

(75)

where D k (s) = {s ′ : |s ′ | = |s | − k, s ′ ≤ s}.

4Note that 1 − h(p) is an upper bound on the rate as the capacity of the binary symmetric channel with crossover probability p is
1 − h(p) and the oblivious channel can always just choose the error vector randomly.

34

In plain English, this lemma says that for a fixed message and deletion pattern, the probability that
message decodes incorrectly too many times (> ϵ fraction of the time) is too large (> 2−h(p)n ). In short, the
reason the lemma is true is because the probability the entire code C contains a “really bad” word (e.g. a
word with at least 0.91n runs of 1s) is too large. The following remark shows us, using Lemma B.2, why we
cannot follow the same randomized approach as Theorem B.1.
Remark B.3. Following the approach of Theorem B.1, we would like to conclude, using union bound,


′
′
Pr ∀m∀τ Pr [∃c ∈ C \ E(m) : τ (c) ⊑ c ] > ϵ
C
c ∈E(m)

ÕÕ 
′
′
≤
Pr Pr [∃c ∈ C \ E(m) : τ (c) ⊑ c ] > ϵ
m

≤2

Rn



τ

C



c ∈E(m)

n
Pr
pn C



′

′

Pr [∃c ∈ C \ E(m) : τ (c) ⊑ c ] > ϵ

c ∈E(m)

< 2 Rn 2h(p)n 2−h(p)n−Ω(n) = 2−Ω(n)



(76)

Unfortunately the last inequality (indicated in red) is false by Lemma B.2.
Proof of Lemma B.2. It suffices to prove for p = 0.4. Indeed, as p increases,


Ø


′ 

Pr τ (c) ∈
Dpn (c )
c ∈E(m) 

c ′ ∈C\E(m)



(77)

increases as τ (c) contains fewer symbols.
If p = 0.4, then τ (c) has 0.6n characters. Note that if c is uniform on {0, 1}n , then τ (c) is uniform on
{0, 1}0.6n . It is easy to check that for a uniformly chosen 0.6n string, the probability it is a subsequence
of the length 0.91n string a 0.91n = 0101 . . . 01 is 1 − 2−Ω(n) : the position in the longest string increases by
1.5 each time, so in expectation the string spans 0.9n characters of a 0.91n , so it is not a subsequence with
exponentially small probability by Chernoff bounds.
There are 20.09n length n strings that start with a 0.91n . Call this set of strings A. Thus, the probability that
C contains an element of A is at least 2−0.91n since that is the probability the first element is an element of A.
Conditioned on C containing an element of A, the probability that, for some c ∈ E(m), τ (c) is a subsequence
of some element of A is at least the probability that c is a subsequence of a 0.91n , which is 1 − 2−Ω(n) . Thus,
conditioned on C containing an element of A, we have
E [#{c : ∃c ′ ∈ C \ E(m) s. t. τ (c) ≤ c ′ }] = t(1 − 2−Ω(n) )

(78)

Conditioned on C being fixed, consider the indicator random variables X i for whether each ci ∈ E(m) satisfies
Í
τ (ci ) is a subsequence of some c ′ ∈ C \ E(m). The X 1 , . . . , X t are i.i.d, so the probability X i /t > ϵ is
approximately 1, (for sure, it is 1 − 2−Ω(n) ).
Thus we conclude
Pr[#{c : ∃c ′ ∈ C \E(m) s. t. τ (c) ≤ c ′ } > ϵt] ≥ (1−2−Ω(n) ) Pr[C ∩A , ∅] > 2(0.91−o(1))n > 2−H (0.4)n (79)
C

C

as H (0.4) ≈ 0.97.



Intuitively B.2 should be true as deletion codes behave poorly when chosen completely randomly. In
the adversarial deletion channel, random codes correct only 0.17n deletions [20], while the best known
constructions correct 0.41n deletions [3].
35

C

Proofs of Lemma 5.19 and Lemma 5.20

√
Lemma C.1. For any j ∈ [1, K], if Z is a random variable distributed as min(Geometric(j/K), R − 1),
K
− 1.
then E[Z ] > 2j
Proof. We have
 
 

 
 √R−2
√
j
j
j
j
j
E[D] =
·1+
1−
·2+ ··· +
1−
· ( R − 1)
K
K
K
K
K

 √R−1
 √R−1

1 − 1 − Kj
√
j
=
− ( R − 1) 1 −
j/K
K
√
 R−1
 √R−1

√
1 − 1 − K1
K
1
≥
>
− ( R − 1) 1 −
−1
j/K
K
2j

(80)

The last inequality follows from recalling R = 4K 4 and twice applying
√
 K

K2
√
  K − 1  R−1
1
K −1
2
< 2K 2 ·
< 2K ·
< 1,
R−1
K
K
2

which is true since K > 8.

(81)


Lemma (Lemma 5.19). Let J be chosen uniformly from [K]. Let D be a random
√ variable that is 1 if J ∈ [λ −1]
and, conditioned on a fixed J ≥ λ, is distributed as min(Geometric(J /K), R). Then E[D] ≥ (log K)/4.
Proof. Applying Lemma C.1,


λ−1
K
K
Õ
Õ
1Õ
1
1 K
E[D] =
E[D |J = j] >
·1+
−1
K j=1
K
K 2j
j=1
≥ −1 +

K
Õ
j=λ



1
2j



j=λ

>

1
1
(ln K − ln λ − 1) − 1 > log K.
2
4

(82)


Lemma (Lemma 5.20). Let λ ′ ∈ [λ, K] and let J be chosen uniformly from {λ, λ + 1, . . . , λ ′ }.
√ Let D be
the random variable that, conditioned on a fixed J , is distributed as min(Geometric(J /K), R). Then
E[D] ≥ (log K)/4.
Proof. Applying Lemma C.1,

λ′
λ′ 
Õ
Õ
1
K
1
E[D |J = j] > ′
−1
E[D] = ′
λ −λ+1
λ −λ+1
2j
j=λ

1
>
K −λ+1

K 
Õ
j=λ

K
−1
2j



36

> −1 +

K 
Õ
j=λ

j=λ

1
2j



>

1
log K.
4



