# Coded Shotgun Sequencing

Aditya Narayan  Aditya Narayan Ravi, Alireza Vahid, Ilan Shomorony Aditya
Narayan Ravi and Ilan Shomorony are with the Electrical and Computer
Engineering Department of the University of Illinois, Urbana-Champaign, IL,
USA. Email: anravi2<EMAIL_ADDRESS>Vahid is with the
Department of Electrical and Microelectronic Engineering at Rochester
Institute of Technology, Rochester, NY, 14623, USA. Email:
<EMAIL_ADDRESS>
# Recovering a Message from an Incomplete Set of Noisy Fragments111This paper
was presented in part at the IEEE International Symposium of Information
Theory 2021

Aditya Narayan  Aditya Narayan Ravi, Alireza Vahid, Ilan Shomorony Aditya
Narayan Ravi and Ilan Shomorony are with the Electrical and Computer
Engineering Department of the University of Illinois, Urbana-Champaign, IL,
USA. Email: anravi2<EMAIL_ADDRESS>Vahid is with the
Department of Electrical and Microelectronic Engineering at Rochester
Institute of Technology, Rochester, NY, 14623, USA. Email:
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of communicating over a channel that breaks the
message block into fragments of random lengths, shuffles them out of order,
and deletes a random fraction of the fragments. Such a channel is motivated by
applications in molecular data storage and forensics, and we refer to it as
the torn-paper channel. We characterize the capacity of this channel under
arbitrary fragment length distributions and deletion probabilities. Precisely,
we show that the capacity is given by a closed-form expression that can be
interpreted as ${\rm F}-{\rm A}$, where ${\rm F}$ is the coverage fraction,
i.e., the fraction of the input codeword that is covered by output fragments,
and ${\rm A}$ is an alignment cost incurred due to the lack of ordering in the
output fragments. We then consider a noisy version of the problem, where the
fragments are corrupted by binary symmetric noise. We derive upper and lower
bounds to the capacity, both of which can be seen as ${\rm F}-{\rm A}$
expressions. These bounds match for specific choices of fragment length
distributions, and they are approximately tight in cases where there are not
too many short fragments.

###### Index Terms:

Torn-paper channel, channel capacity, molecular data storage, DNA storage, DNA
sequencing

##  I Introduction

Consider the problem of transmitting a message by encoding it in a codeword,
which is then torn up into fragments of random sizes. The codeword may be also
subject to noise, and some of the fragments may be lost in the process. The
remaining fragments are received out of order by a decoder who wishes to
recover the original message. How does one optimally encode a message to
protect against the tearing, the fragment losses, the noise, and the
shuffling? How do the achievable rates depend on specific fragment length
distributions, noise, and fragment deletion probabilities?

This channel was originally proposed in [1] as the torn-paper channel (TPC).
This channel is motivated by macromolecular data storage, and in particular
DNA-based data storage [2, 3, 4, 5, 6, 7], where the data is encoded into
molecules that may be subject to breaks during storage. Moreover, when
retrieving the data via sequencing, molecules are read in a random order, and
many fragments are lost [8]. It can also be motivated by applications in
fingerprinting and forensics, where one may wish to encode a serial number
into a physical object (such as a weapon), which should be recoverable even
from a small set of pieces left over from the original object [9, 10].

In this paper, we generalize the torn-paper channel to capture several real-
world challenges of DNA storage. Precisely, we consider a TPC whose input is a
length-$n$ binary string, which is broken up into $K$ fragments of random
lengths $N_{1},\dots,N_{K}$, such that $N_{1}+\dots+N_{K}=n$, where the number
of fragments $K$ is itself random. Each resulting fragment can be
independently deleted with a probability $d$, which in general is allowed to
be a function $d(\cdot)$ of the fragment length $N_{i}$. The channel output is
an unordered multiset of all the fragments that are not deleted. This torn-
paper channel with lost pieces is illustrated in Figure 1.

The original TPC introduced in [1] is a special case of this channel where
there are no fragment deletions ($d=0$) and the fragment lengths are
distributed as $N_{i}\sim{\rm Geometric}(1/\ell_{n})$ (where
$E[N_{i}]=\ell_{n}$ can be a function of $n$). The capacity in this setting
was shown in [1] to be

$\displaystyle C_{\rm TPC}=\exp\left({-\lim_{n\to\infty}\frac{\log
n}{\ell_{n}}}\right).$ (1)

By defining $\alpha\triangleq\lim_{n\to\infty}(\log n)/\ell_{n}$, we can also
write $C_{\rm TPC}=e^{-\alpha}$. The simplicity and “elegance” of the capacity
expression $C_{\rm TPC}=e^{-\alpha}$ is a result of the specific choice of
geometrically-distributed fragment lengths and the connection between the
geometric and exponential distributions. As such, it is unclear how (1) would
generalize to different fragment distributions and to the case of lost
fragments.

Figure 1: The torn-paper channel with lost pieces.

Another related result we consider that can help build intuition is the
capacity of the shuffling channel [11]. The input to the shuffling channel is
a multiset of strings of a fixed length, which are shuffled by the channel.
The shuffling channel can be thought of as a TPC where the fragment lengths
are all deterministic and equal; i.e., $N_{1}=\dots=N_{K}=\ell_{n}$, and
$K=n/\ell_{n}$. Notice that, in this case, the encoder knows all the tearing
locations (since they are deterministic) and can combat the lack of ordering
at the output by placing a unique index at the beginning of each fragment. The
results in [11] show that the capacity of this shuffling channel is

$\displaystyle C_{\rm shuf}=\left(1-\lim_{n\to\infty}\frac{\log
n}{\ell_{n}}\right)^{+}=(1-\alpha)^{+},$ (2)

where $(x)^{+}\triangleq\max(0,x)$. As explained in [11], the term $(\log
n)/\ell_{n}$ can be understood as the fraction of bits in each
length-$\ell_{n}$ fragment that must be used for a unique index, which allows
for the alignment of the shuffled fragments. We can thus think of
$\alpha=\lim_{n\to\infty}\frac{\log n}{\ell_{n}}$ as a fundamental alignment
cost. Notice that the results in (1) and (2) feel qualitatively different, and
it is not clear how they can both be seen as special cases of a general TPC
capacity.

The first main result in this paper generalizes the capacity of the TPC to (i)
accommodate the case of lost fragments with a general deletion probability
function $d(\cdot)$, and (ii) allow any distribution for the fragment length
$N_{i}$, as long as some mild regularity conditions hold. In Section II-B, we
obtain closed-form expressions for various choices of $d(\cdot)$ and $N_{i}$.
Moreover, in doing so, we provide a capacity expression that allows us to
reconcile (1) and (2). More precisely, we prove that discarding fragments of
length $\log n$ or shorter at the output does not affect the capacity, and
that the capacity of the TPC can always be written as

$\displaystyle C_{{\rm TPC}}={\rm F}_{d}{\\{\log{n}\\}}-{\rm
A}_{d}{\\{\log{n}\\}}.$ (3)

Here, ${\rm F}_{d}\\{\log{n}\\}$ (the covered fraction) represents the
fraction of the original length-$n$ string that is covered by the non-deleted
output fragments (with deletion probability $d$) and after discarding those
shorter than $\log n$. The alignment cost ${\rm A}_{d}\\{\log{n}\\}$
represents the fraction of the non-deleted output fragments that would need to
be dedicated for the placing of a unique index to help align the fragments if
we knew the tearing locations (again after discarding fragments shorter than
$\log{n}$)222The terms $F$ and $A$ are referred to as “coverage” ($\Phi$) and
“reordering cost” ($\Omega$) in the conference version of this paper [12].
Here, we adopt $F$ and $A$ in an attempt to improve the notation..
Surprisingly, it turns out that this alignment cost does not change in the
setting of the TPC where the tearing points are unknown a priori even when the
encoder cannot place unique indices at the beginning of each fragment.

Consider the capacity expression for the deterministic case with fragments of
length $\ell_{n}>\log{n}$ and no lost fragments. Notice that the covered
fraction for this case is $1$, since all the fragments are retained. Now, the
alignment cost is the fraction of bits in each length-$\ell_{n}$ piece used
for indexing purposes given by $\lim_{n\to\infty}\log n/\ell_{n}=\alpha$ as
discussed before. Thus, the formula “F$-$ A” recovers (2) as a special case.
Similarly, the result in [1] for a TPC with geometric piece lengths and no
lost fragments is a special case of (3). More specifically, for the setting in
[1] the covered fraction can be calculated as $(1+\alpha)e^{-\alpha}$ and the
alignment cost can be shown to be $\alpha e^{-\alpha}$, which yields (1) (see
[13] for details).

The general expression in (3) captures in an intuitive way the impact of
sequence fragmentation and fragment losses, but it is based on a model where
the fragments are observed in an error-free fashion at the output. In many
applications, including macromolecular data storage, one can observe bit-level
substitution errors, or bit flips. Channels such as the shuffling channel have
been extended to accommodate these kinds of errors [11, 14]. Notably, [11]
considers the capacity of the noisy shuffling channel, where the input string
is passed through a Binary Symmetric Channel (BSC) with crossover probability
$p$. Specifically, the results in [11] show that if the fragment size is
$\ell_{n}\geq\frac{2\log n}{1-H(2p)}$, then the capacity is

$\displaystyle C_{\text{noisy-shuf}}=1-H(p)-\alpha.$ (4)

Therefore to study the impact of symbol-level noise on the TPC capacity, we
also study a TPC where the input is passed symbol-wise through a Binary
Symmetric Channel (BSC) with crossover probability $p$. This is followed by a
tearing of the resulting string in the exact same fashion as before. To keep
things simple, we assume no fragments are lost, but the results can be easily
extended to accommodate lost fragments too. The Noisy-TPC is shown in Figure
2.

Figure 2: The noisy torn-paper channel.

The second main result in this paper provides inner and outer bounds to the
capacity $C_{\text{Noisy-TPC}}$ for arbitrary distributions of fragment length
$N_{i}$ and crossover probability $p$. Following the intuition from the ${\rm
F}{}-{\rm A}{}$ expression, a natural conjecture is that the capacity
$C_{\text{noisy-TPC}}$ in this case is given by

$\displaystyle xc=C_{\rm BSC}\cdot{\rm F}{\left\\{\frac{\log{n}}{C_{\rm
BSC}}\right\\}}-{\rm A}{\left\\{\frac{\log{n}}{C_{\rm BSC}}\right\\}},$ (5)

where $C_{\rm BSC}=1-H(p)$ is the capacity of a BSC($p$) channel. Here, ${\rm
F}$ and ${\rm A}$ have the same meaning as before, except only pieces of
lengths greater than the lengths indicated in the brackets are considered.
Since the fragments are now noisy, we expect the covered fraction F to be
multiplied by $C_{\rm BSC}$, since that is effectively the fraction of “good”
bits recovered. Moreover, due to the noise, we expect the “effective” length
of a given fragment (call it $N_{\rm eff}$) to be related to its original
length $N$ as $N_{\rm eff}=C_{\rm BSC}\times N.$ Since we discarded all
strings of size less than $\log{n}$ for the noiseless case, it is natural to
conjecture that we should discard all pieces with $N_{\rm eff}\leq\log{n}$
while calculating coverage fraction and alignment cost, which is equivalent to
discarding fragments with $N\leq\log{n}/C_{\rm BSC}$.

As it turns out, we can indeed construct codes that achieve the rate in (5).
More precisely we prove that rate $R$ is achievable if

$\displaystyle R<(1-H(p)){\rm F}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}-{\rm
A}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}.$ (6)

However, deriving an outer bound that matches this inner bound is hard in
general. Instead, we prove that no rates $R$ with

$\displaystyle R>(1-H(p)){\rm F}{\left\\{\log{n}\right\\}}-{\rm
A}{\left\\{\frac{2\log{n}}{1-H(2p)}\right\\}}$ (7)

are achievable. Notice that the difference between (6) and (7) is in the
length of the pieces we discard when computing F and A. As such, as long as
the fragment lengths $N_{i}$ are all guaranteed to be large enough, the inner
and outer bounds match.

Specifically, we can show that for the class of noisy TPCs where
$N_{1}\geq\frac{2\log{n}}{1-H(2p)}$ with probability $1$ (i.e., every fragment
is longer than this threshold), the capacity of the noisy TPC is given by

$\displaystyle C_{\text{noisy-TPC}}=1-H(p)-\alpha.$ (8)

Interestingly, this result generalizes the capacity of the noisy shuffling
channel when $\ell_{n}\geq\frac{2\log{n}}{1-H(2p)}$. Therefore, we can view
the result for the noisy shuffling channel in (4) as a special case of this
more general result that allows fragments to have random lengths.

Related Work: The torn-paper channel we consider is a generalization of the
channel from [1, 13, 12], originally introduced with the goal of modeling
message fragmentation in macromolecular data storage and especially DNA-based
data storage. As such, our work is related to other attempts at modeling the
DNA storage channel and characterizing its capacity. This includes the noisy
shuffling channel model [15, 11, 16] and multi-draw sampling channels [14,
17]. See [18, 19] for a broader survey of the topic.

The idea of index-based coding was used in [20] to develop an encoding-
decoding scheme for an adverserial version of the TPC. Specifically it
considered a TPC where the length of the torn pieces were restricted between
values $L_{\rm min}$ and $L_{\rm max}$ with probability $1$. Moreover [20]
proves that decoding can be done in linear time with this coding scheme.

The torn-paper channel we consider is also related to the shotgun sequencing
channel [21, 22], whose output also consists of pieces of the input codewords.
However, the shotgun sequencing channel models standard next-generation
sequencing platforms, where the observed output fragments have overlaps with
each other [23, 24]. Moreover, an “extreme” version of a torn-paper channel
that breaks the message down to its symbols (i.e., fragments of length one)
and shuffles them was studied as the noisy permutation channel [25, 26].

In addition to information-theoretic characterizations of the fundamental
limits of DNA storage channels, several recent works have proposed new
explicit code constructions based on unique aspects of DNA data storage. These
works focus on DNA synthesis constraints such as sequence composition [27, 28,
6], the asymmetric nature of the DNA sequencing error channel [29], the need
for codes that correct insertion errors [30], and techniques to allow random
access [28]. Moreover [31, 32] propose various VT codes for the TPC model
considered in [13].

##  II The Torn-Paper Channel with Lost Pieces

In this section, we consider a version of the TPC in which some fragments are
lost. The converse involves a careful decomposition of the TPC into parallel
channels that contain pieces of roughly the same lengths. The converse is
inspired by the converse proved in [1], but requires considerable
generalization to account for general distributions of $N_{i}$ and lost
fragments. We present an achievable argument based on random coding. The
resulting inner and outer bounds match, characterizing the capacity of this
channel. We will consider the noisy TPC in Section III.

###  II-A Problem Setting

We consider the TPC as shown in Figure 1. The transmitter encodes a binary
codeword $X^{n}\in\\{0,1\\}^{n}$ corresponding to the message
$W\in[1:2^{nR}]$. The channel output is a multiset of variable-length binary
strings $\mathcal{Y}$. The process by which $\mathcal{Y}$ is obtained from
$X^{n}$ is described as follows. The channel first breaks the input sequence
into pieces of a random length. Specifically, define $N_{1},N_{2},\dots$ to be
i.i.d. random variables. We assume $E[N_{i}]=\ell_{n}$ $\forall$ $i$. Let $K$
be the smallest index such that $\sum_{i=1}^{K}N_{i}$ is greater than or equal
to $n$. Note that $K$ is also a random variable. The channel tears the string
$X^{n}$ into $\vec{X}_{1},\vec{X}_{2},\dots,\vec{X}_{K}$ where

$\displaystyle\vec{X}_{i}\triangleq\left[X_{1+\sum_{j=1}^{i-1}N_{j}},\dots,X_{\sum_{j=1}^{i}N_{j}}\right]\text{
and}$
$\displaystyle\vec{X}_{K}\triangleq\left[X_{1+\sum_{j=1}^{K-1}N_{j}},\dots,X_{n}\right].$

Then, the multiset $\mathcal{Y}$ (which is the output of the channel) is
defined as follows. Consider the strings
$\\{\vec{X}_{1},\vec{X}_{2},\dots,\vec{X}_{K}\\}$. Each element $\vec{X}_{i}$
is independently discarded with probability $d(N_{i})$, where $d(\cdot)$ is
the deletion probability (which in general depends on the length of the
pieces), for a function $d:\\{1,2,\dots\\}\to[0,1]$. The new multi-set
obtained is $\mathcal{Y}$, which is the output of the channel. Note that there
are no bit-level errors (e.g., deletions or bit-flips). Moreover, $\ell_{n}$
in general depends on the value of $n$.

For the purposes of this paper we assume (i) the limit
$\alpha\triangleq\lim_{n\to\infty}\log n/\ell_{n}$ exists and
$\alpha\in(0,\infty)$ and (ii) $E[N_{1}^{2}/(\log{n})^{2}]$ is finite and
bounded for all $n$. This means we expect the second moment of $N_{i}$ to
scale as $\log^{2}{n}$. This is typically valid when pieces are of a size that
scales as $\log{n}$ when we increase $n$. Our results also hold in the case
where $\alpha=0,\infty$, but would require different steps to prove.

Notation: Throughout the paper, $\log(\cdot)$ represents the logarithm in base
$2$. For functions $a(n)$ and $b(n)$, we say $a(n)=o(b(n))$ if $a(n)/b(n)\to
0$ as $n\to\infty$. For an event $A$, we let $\mathbf{1}_{A}$ be the binary
indicator of $A$. For $x\in{\mathbb{R}}$, $\lceil x\rceil$ refers to the
smallest integer greater than equal to $x$.

###  II-B Capacity of the generalized TPC

Intuitively, the capacity of the TPC should be affected by two distinct
sources of uncertainty: (i) some of the fragments (which potentially carry
information) are discarded by the channel, and (ii) the remaining fragments
are observed as an unordered set. As it turns out, (i) will be captured in the
capacity expression by a quantity that represents the fraction of bits in
$X^{n}$ retained at the output, which can be written as

$\displaystyle\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}\\}}.$
(9)

The limit as $n\to\infty$ of the expected value of (9), after ignoring
fragments smaller than a fixed number $g(n)$, turns out to be fundamental in
calculating the capacity of the TPC.

######  Definition 1.

The coverage fraction ${\rm F}_{d}\\{g(n)\\}$ ($d$ is suppressed if $d\equiv
0$) is defined as

$\displaystyle{\rm
F}_{d}\\{g(n)\\}\triangleq\lim_{n\to\infty}E\left[\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\left\\{\vec{X}_{i}\in\mathcal{Y},N_{i}\geq
g(n)\right\\}}\right].$ (10)

The capacity of the TPC will also involve a quantity that captures (ii). To
build intuition, let us imagine a channel where the tearing points and the set
of pieces that are discarded are known a priori. For this channel, to preserve
the ordering, a simple coding strategy is to include an index/address at the
beginning of each fragment. There are roughly $n/\ell_{n}$ fragments prior to
some of them being lost. We therefore need

$\displaystyle\log{(n/\ell_{n})}$
$\displaystyle=\log{n}-\log{\ell_{n}}\stackrel{{\scriptstyle(a)}}{{=}}\log{n}-o(\log{n})$

bits per piece for indexing, where (a) holds since $\alpha\in(0,\infty)$ and
$1/\ell_{n}=\alpha/\log{n}$ asymptotically. Therefore, for a piece
$\vec{X}_{i}$ in $\mathcal{Y}$, $\log{n}$ bits are needed for indexing. This
can be written as $\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}\\}}\log{n}$ and
can be thought of as an “alignment cost” that one must pay to know where in a
codeword $\vec{X}_{i}$ belongs. Surprisingly, this cost remains unchanged even
when the tearing locations are unknown. The average of this quantity across
all pieces also plays a key role in the capacity of the TPC.

######  Definition 2.

The alignment cost ${\rm A}_{d}\\{g(n)\\}$ ($d$ is suppressed if $d\equiv 0$)
is defined as

$\displaystyle{\rm
A}_{d}\\{g(n)\\}\triangleq\lim_{n\to\infty}E\left[\frac{\log{n}}{n}\sum_{i=1}^{K}\mathbf{1}_{\left\\{\vec{X}_{i}\in\mathcal{Y},N_{i}\geq
g(n)\right\\}}\right].$ (11)

We now state our main result.

######  Theorem 1.

The capacity of the TPC is

$\displaystyle C={\rm F}_{d}\\{\log{n}\\}-{\rm A}_{d}\\{\log{n}\\}.$ (12)

The capacity expression is of the form “${\rm F}-{\rm A}$”, which intuitively
is the fraction of bits that carry information about the message. The
following corollary allows us to compute the capacity numerically. It is also
used to obtain closed form expressions for various distributions of $N_{i}$.

######  Corollary 2.

Assuming limits exist, the capacity of the TPC is equivalently written as

$\displaystyle
C=\alpha\int_{1}^{\infty}\left(\beta-1\right)\left(1-\hat{d}(\beta)\right)h(\beta)d\beta,$
(13)

where $\hat{d}(\beta)\triangleq\lim_{n\to\infty}d(\beta\log{n})$ and
$h(\beta)\triangleq\lim_{n\to\infty}\Pr(N_{1}=\beta\log{n})\log{n}$.

We prove Corollary 2 in Appendix A. Note that the result in [1] for the TPC
with no lost pieces can be obtained by taking $\hat{d}(\beta)=0$. To see this
note that when $N_{1}\sim\rm Geom(1/\ell_{n})$, we can compute $h(\beta)$ as

$\displaystyle
h(\beta)=\lim_{n\to\infty}\left(1-\frac{1}{\ell_{n}}\right)^{\beta\log{n}}\frac{\log{n}}{\ell_{n}}=\alpha
e^{-\alpha\beta}.$ (14)

Using this to compute (13) we obtain

$\displaystyle C=\alpha\int_{1}^{\infty}(\beta-1)(\alpha
e^{-\alpha\beta})d\beta=\left(1+\alpha\right)e^{-\alpha}-\alpha
e^{-\alpha}=e^{-\alpha},$ (15)

which is the capacity result discussed in Section I and first proved in [1].
Similarly, we can find a closed-form expression for the capacity of several
different choices of $N_{i}$ and the deletion probability $d(\cdot)$, as shown
in Table I. Note that $h(\beta)$ can have multiple $d(\cdot)$s associated with
it.

TABLE I: Capacity Expressions

$\hat{d}(\beta)$ | $N_{i}$ | $h(\beta)$ | $C_{\text{{\rm TPC}}}$
---|---|---|---
$0$ | Geometric($1/\ell_{n}$) | $\alpha e^{-\alpha\beta}$ | $e^{-\alpha}$
$\epsilon$ | Geometric($1/\ell_{n}$) | $\alpha e^{-\alpha\beta}$ | $(1-\epsilon)e^{-\alpha}$
$e^{-\gamma\beta}$ | Geometric($1/\ell_{n}$) | $\alpha e^{-\alpha\beta}$ | $e^{-\alpha}\left(1-\frac{\alpha^{2}e^{-\gamma}}{(\alpha+\gamma)^{2}}\right)$
$0$ |  $\text{U}[0:\gamma\log{n}]$, $\gamma\geq 1$ | $1/\gamma$ | $\left((\gamma-1)/\gamma\right)^{2}$
$0$ |  Fixed($\ell_{n}$), $\ell_{n}\geq\log{n}$ | NA333$h(\cdot)$ does not exist, hence we directly employ Theorem 1. | $1-\alpha$

2 $h(\cdot)$ does not exist, hence we directly employ Theorem 1.

###  II-C Achievability via Random Coding

We use a random coding argument to prove the achievability of Theorem 1. We
generate a codebook $\mathcal{C}$ with $2^{nR}$ codewords, by independently
picking each letter as $\text{Bern}(1/2)$. Let the resulting random codebook
be
$\mathcal{C}=\\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{2^{nR}}\\}$.

Assume that $W=1$ is the message that is transmitted. The output $\mathcal{Y}$
is available at the decoder. We follow steps similar to [1], but with
considerable generalization. We choose a sub-optimal decoder, which throws out
all fragments of size at most $\log{n}$. Let this set be $\mathcal{Y}_{\geq
1}$. If elements of $\mathcal{Y}_{\geq 1}$ exist as non-overlapping substrings
in a single codeword $\mathbf{x}_{i}$, then the decoder declares the index of
that codeword as the message. Since there is no noise in the observed
fragments, the only error event corresponds to the existence of an incorrect
codeword containing all fragments in $\mathcal{Y}_{\geq 1}$. We bound the
probability of error averaged over all codebook choices as

$\displaystyle\text{Pr}(\mathcal{E})=\text{Pr}(\mathcal{E}|W=1)$
$\displaystyle=\text{Pr}\left(\exists\text{ }j\neq 1:x_{j}\text{ contains all
fragments in $\mathcal{Y}_{\geq 1}$}\middle|W=1\right).$ (16)

We now state two lemmas (the proofs of which are available in Appendices B and
C) that are crucial to prove the achievable part of Theorem 1. They provide us
with a concentration on the coverage fraction and the alignment cost. This
intuitively can be used to bound the probability of error by restricting the
possibility of the value of the coverage fraction ${\rm F}$ being too high or
the alignment cost ${\rm A}$ being too low, since they are events of low
probability. Let us define the event
$\tilde{B}:=\\{\vec{X}_{1}\in\mathcal{Y}_{\geq 1}\\}$. Then the following
lemmas hold.

######  Lemma 1.

For any $\epsilon>0$, as $n\to\infty$,

$\displaystyle\Pr\left(\left|\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}\right|>\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}\epsilon\right)\to
0.$ (17)

In particular, this implies that ${\rm F}_{d}\\{\log
n\\}=\lim_{n\to\infty}\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}$.

######  Lemma 2.

For any $\epsilon>0$, as $n\to\infty$,

$\displaystyle\Pr\left(\middle|\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-\frac{nE[\mathbf{1}_{\tilde{B}}]}{\ell_{n}}\middle|\geq\frac{nE[\mathbf{1}_{\tilde{B}}]}{\ell_{n}}\epsilon\right)\to
0.$ (18)

In particular, this implies that ${\rm A}_{d}\\{\log
n\\}=\lim_{n\to\infty}\frac{\log(n)E[\mathbf{1}_{\tilde{B}}]}{\ell_{n}}=\alpha\lim_{n\to\infty}E[\mathbf{1}_{\tilde{B}}]$.

Now we let $B_{1}=(1+\epsilon)\frac{nE[\mathbf{1}_{\tilde{B}}]}{\ell_{n}}$ and
$B_{2}=(1-\epsilon)\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}$ and define
the event

$\displaystyle\mathcal{B}=\left\\{\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}>B_{1}\right\\}\cup\left\\{\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}<B_{2}\right\\}.$ (19)

Lemmas 1 and 2 imply that $\text{Pr}(\mathcal{B})\to 0$ as $n\to\infty$.
Therefore, we have

$\displaystyle\text{Pr}(\mathcal{E})$ $\displaystyle=\text{Pr}(\exists j\neq
1:x_{j}\text{ containing all fragments in $\mathcal{Y}_{\geq 1}$}|W=1)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\text{Pr}(\exists j\neq
1:x_{j}\text{ containing all fragments in $\mathcal{Y}_{\geq
1}$}|W=1,\overline{\mathcal{B}})$ $\displaystyle+\text{Pr}(\mathcal{B})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}|\mathcal{C}|\frac{n^{B_{1}}}{2^{nB_{2}}}+\text{Pr}(\mathcal{B})$
$\displaystyle=2^{nR}2^{B_{1}\log{n}}2^{-nB_{2}}+o(1).$ (20)

Inequality $(a)$ follows from the law of total probability and the fact that
$\mathcal{B}$ is independent of $W=1$. Inequality $(b)$ follows from the union
bound and the fact that given $\overline{\mathcal{B}}$, there are at most
$n^{B_{1}}$ ways to align the fragments in $\mathcal{Y}_{\geq 1}$ to a
codeword $x_{j}$. To see this, note that, given $|\mathcal{Y}_{\geq 1}|\leq
B_{1}$, there are at most $n$ places the fragments can start from to align
each piece and at most $B_{1}$ such pieces. Since a non-overlapping alignment
of the strings in $\mathcal{Y}_{\geq 1}$ to a codeword $x_{j}$ covers at least
$nB_{2}$ positions of $x_{j}$, the probability that it matches $x_{j}$ when
$j\neq 1$, on all covered positions is at most $2^{-nB_{2}}$. Now,
$\Pr(\mathcal{E})\to 0$ if

$\displaystyle R$
$\displaystyle<\lim_{n\to\infty}\left(B_{2}-\frac{\log{n}}{n}B_{1}\right)$
$\displaystyle=\lim_{n\to\infty}\left((1-\epsilon)\frac{E\left[N_{1}\mathbf{1}_{\tilde{B}}\right]}{\ell_{n}}-(1+\epsilon)\frac{E\left[\mathbf{1}_{\tilde{B}}\right]\log{n}}{\ell_{n}}\right)$
$\displaystyle=(1-\epsilon){\rm F}_{d}\\{\log{n}\\}-(1+\epsilon){\rm
A}_{d}\\{\log{n}\\}.$ (21)

Letting $\epsilon\to 0$, we conclude that any rate $R<{\rm
F}_{d}\\{\log{n}\\}-{\rm A}_{d}\\{\log{n}\\}$ is achievable. This proves the
achievability part of Theorem 1.

###  II-D Converse

In order to prove the converse, we partition the set $\mathcal{Y}$ into sets
that contain pieces of roughly the same length. This allows us to view the TPC
as a set of parallel channels that process pieces of roughly the same length.
More precisely, we define

$\displaystyle\mathcal{Y}_{k}\triangleq\left\\{\vec{X}_{i}\in\mathcal{Y}:\frac{k-1}{L}\log{n}\leq
N_{i}<\frac{k}{L}\log{n}\right\\},$ (22)

where $L$ is a fixed integer. We then split the set of “channels” into two
sets, one with pieces of smaller sizes and the other with larger sizes.
Specifically, we fix another integer $J>L$, and define $\mathcal{Y}_{\geq
J}=\\{\vec{X}_{i}:N_{i}\geq(J/L)\log{n}\\}$. Then, by Fano’s inequality, we
have

$\displaystyle R$
$\displaystyle\leq\lim_{n\to\infty}\frac{I(X^{n};\mathcal{Y})}{n}\leq\lim_{n\to\infty}\frac{H(\mathcal{Y})}{n}\stackrel{{\scriptstyle(a)}}{{\leq}}\lim_{n\to\infty}\sum_{k=1}^{J}\frac{H(\mathcal{Y}_{k})}{n}+\lim_{n\to\infty}\frac{H(\mathcal{Y}_{\geq
J})}{n},$ (23)

where (a) holds from the independence bound on partition
$\mathcal{Y}=(\cup_{k=1}^{J}\mathcal{Y}_{k})\cup\mathcal{Y}_{\geq J}$.

The key idea is that for fixed large values of $J$, the second term in
equation (23) is finite, but arbitrarily small. We will now use the fact that
$|\mathcal{Y}_{k}|$ concentrates around its mean to tackle the first term in
(23). To that end, we define the event $B=\\{X_{1}\in\mathcal{Y}\\}$ and

$\displaystyle q_{k,n}$ $\displaystyle=\text{Pr}\left(\frac{k-1}{L}\log{n}\leq
N_{1}<\frac{k}{L}\log{n}\right)$ $\displaystyle e_{k,n}$
$\displaystyle=\text{Pr}\left(B\,\middle|\,\frac{k-1}{L}\log{n}\leq
N_{1}<\frac{k}{L}\log{n}\right).$ (24)

Additionally, we define the event

$\displaystyle\mathcal{E}_{k,n}=\\{||\mathcal{Y}_{k}|-nq_{k,n}e_{k,n}/\ell_{n}|>\epsilon_{n}n/\ell_{n}\\}.$

We establish that $|\mathcal{Y}_{k}|$ concentrates in the following lemma.

######  Lemma 3.

For $\epsilon_{n}>0$ and n large enough,

$\displaystyle\Pr(\mathcal{E}_{k,n})\leq
2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}.$
(25)

We prove this in the Appendix D. The lemma indicates that with high
probability, $|\mathcal{Y}_{k}|$ is close to $nq_{k,n}e_{k,n}/\ell_{n}$. We
set $\epsilon_{n}=1/\log{n}$, ensuring that $\epsilon_{n}\to 0$ and
$\text{Pr}(\mathcal{E}_{k,n})\to 0$ from Lemma 3. Then

$\displaystyle H(\mathcal{Y}_{k})$ $\displaystyle\leq
H(\mathcal{Y}_{k},\mathbf{1}_{\mathcal{E}_{k,n}})\leq
1+H(\mathcal{Y}_{k}|\mathbf{1}_{\mathcal{E}_{k,n}})\leq
1+2n\text{Pr}(\mathcal{E}_{k,n})+H(\mathcal{Y}_{k}|\overline{\mathcal{E}}_{k,n}).$
(26)

Here, we loosely upper bound $H(\mathcal{Y}_{k}|\mathcal{E}_{k,n})$ with $2n$
since $\mathcal{Y}_{k}$ is fully described by $X^{n}$ and $n-1$ binary
variables that indicate whether there is a tear between the $(i-1)$th and
$i$th bits. We now need to upper bound
$H(\mathcal{Y}_{k}|\overline{\mathcal{E}}_{k,n})$. We first note that the
total number of possible distinct sequences in $\mathcal{Y}_{k}$ are

$\displaystyle\sum_{i=\frac{k-1}{L}\log{n}}^{\frac{k}{L}\log{n}}2^{i}<2\times
2^{\frac{k}{L}\log{n}}=2n^{k/L}.$ (27)

Now given $\overline{\mathcal{E}}_{k,n}$,

$\displaystyle|\mathcal{Y}_{k}|\leq
M_{k}\triangleq\left(\epsilon_{n}+q_{k,n}e_{k,n}\right)n/\ell_{n}.$ (28)

Following the counting argument in [15], we note that the set
$\mathcal{Y}_{k}$ can be viewed as a histogram over $2n^{k/L}$ sequences.
Moreover, we can view the last element of the histogram as containing “excess
counts” if $|\mathcal{Y}_{k}|<M$, so that the sum of the histogram entries is
exactly $M$. This allows us to bound the term
$H(\mathcal{Y}_{k}|\overline{\mathcal{E}}_{k,n})$ as

$\displaystyle H$
$\displaystyle(\mathcal{Y}_{k}|\overline{\mathcal{E}}_{k,n})\leq\log\binom{2n^{k/L}+M_{k}-1}{M_{k}}\leq
M_{k}\log\left(\frac{e(2n^{k/L}+M_{k}-1)}{M_{k}}\right)$
$\displaystyle=M_{k}(\log(2n^{k/L}+M_{k}-1)+\log{e}-\log{M_{k}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}M_{k}\left[\max\middle(\frac{k}{L}\log{n},\log{M_{k}}\middle)+\log{e}-\log{M_{k}}+P\right]$
$\displaystyle=M_{k}\left[\left(\frac{k}{L}\log{n}-\log{M_{k}}\right)^{+}+\log{e}+P\right],$
(29)

where

$P:=\min\left(\log\middle(2+\frac{M_{k}-1}{n^{k/L}}\middle),\log\middle(1+\frac{2n^{k/L}-1}{M_{k}}\middle)\right).$

In step (a), we employ the fact that if $a=b+c=d+e$, then
$a=\max(b,d)+\min(c,e)$. Specifically, we can select $(a,b,c,d,e)$ as

$\displaystyle a:=\log(2n^{k/L}+M_{k}-1)$
$\displaystyle=\log{\left(n^{k/L}\left(2+\frac{M_{k}-1}{n^{k/L}}\right)\right)}$
$\displaystyle=\frac{k}{L}\log{n}+\log{\left(2+\frac{M_{k}-1}{n^{k/L}}\right)}:=b+c$

and

$\displaystyle a:=\log(2n^{k/L}+M_{k}-1)$
$\displaystyle=\log{\left(M_{k}\left(1+\frac{2n^{k/L}-1}{M_{k}}\right)\right)}$
$\displaystyle=\log{M_{k}}+\log{\left(1+\frac{n^{k/L}-1}{M_{k}}\right)}:=d+e$

to arrive at the required expansion. Proceeding from (26), this implies that

$\displaystyle\frac{H(\mathcal{Y}_{k})}{n}\leq\frac{1+2n\text{Pr}(\mathcal{E}_{k,n})+H(\mathcal{Y}_{k}|\overline{\mathcal{E}}_{k,n})}{n}\leq\frac{M_{k}}{n}\left(\frac{k}{L}\log{n}-\log{M_{k}}\right)^{+}+A(k,n)$
$\displaystyle\leq\frac{M_{k}\log{n}}{n}\left(\frac{k}{L}-\frac{\log{M_{k}}}{\log{n}}\right)^{+}+A(k,n)\stackrel{{\scriptstyle(a)}}{{=}}\frac{M_{k}\log{n}}{n}\left(\frac{k}{L}-\frac{\log{(n(\epsilon_{n}+q_{k,n}e_{k,n})/\ell_{n})}}{\log{n}}\right)^{+}$
$\displaystyle+A(k,n)\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{M_{k}\log{n}}{n}\left(\frac{k}{L}-\frac{\log{(n\epsilon_{n}/\ell_{n})}}{\log{n}}\right)^{+}+A(k,n)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{M_{k}\log{n}}{n}\left(\frac{k}{L}-1\right)^{+}+A(k,n)+\frac{M_{k}\log{n}\log{(\ell_{n}\log{n})}}{n}$
$\displaystyle\leq\frac{\log{n}}{\ell_{n}}(\epsilon_{n}+q_{k,n}e_{k,n})\left(\frac{k}{L}-1\right)^{+}+A(k,n)+\frac{(\epsilon_{n}+1)\log{(\ell_{n}\log{n})}}{\ell_{n}}\log{n}$
(30)

where
$A(k,n)\triangleq\frac{1}{n}+2\text{Pr}(\mathcal{E}_{k,n})+\frac{M_{k}}{n}\left(\log{e}+P\right)$.
$(a)$ is due to the definition of $M_{k}$, $(b)$ is because
$q_{k,n}e_{k,n}\geq 0$ and $(c)$ follows because $\epsilon_{n}=1/\log{n}$.
This allows us to bound $\sum_{k=1}^{J}\frac{H(\mathcal{Y}_{k})}{n}$ as
follows:

$\displaystyle\sum_{k=1}^{J}\frac{H(\mathcal{Y}_{k})}{n}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\log{n}}{\ell_{n}}\sum_{k=1}^{J}q_{k,n}e_{k,n}\left(\frac{k}{L}-1\right)^{+}+A(n)=\frac{\log{n}}{\ell_{n}}\sum_{k=L+1}^{J}q_{k,n}e_{k,n}\left(\frac{k}{L}-1\right)+A(n)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\log{n}}{\ell_{n}}\sum_{k=L+1}^{\infty}\frac{k}{L}q_{k,n}e_{k,n}+A(n)-\frac{\log{n}}{\ell_{n}}E[\mathbf{1}_{\tilde{B}}],$
(31)

where in $(a)$ we define

$\displaystyle
A(n)\triangleq\sum_{k=1}^{J}\frac{(\epsilon_{n}+1)\log{(\ell_{n}\log{n})\log{(n)}}}{\ell_{n}}$
$\displaystyle+\sum_{k=1}^{J}\epsilon_{n}\left(\frac{k}{L}-1\right)^{+}+\sum_{i=1}^{J}A(k,n).$

$(b)$ holds if we recall the definition of the event
$\tilde{B}=\\{\vec{X}_{1}\in\mathcal{Y}_{\geq 1}\\}$ and note that
$\sum_{k=L+1}^{\infty}q_{k,n}e_{k,n}=E[{\mathbf{1}}_{\tilde{B}}]$. The first
term in (II-D) is

$\displaystyle\frac{\log{n}}{\ell_{n}}\sum_{k=L+1}^{\infty}\frac{k}{L}q_{k,n}e_{k,n}=\sum_{k=L+1}^{\infty}\tfrac{q_{k,n}}{\ell_{n}}E\left[\tfrac{k}{L}\log{n}\mathbf{1}_{B}\middle|\tfrac{N_{1}L}{\log
n}\in[k-1,k)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{k=L+1}^{\infty}\tfrac{q_{k,n}}{\ell_{n}}E\left[N_{1}\mathbf{1}_{B}\middle|\tfrac{N_{1}L}{\log
n}\in[k-1,k)\right]+\sum_{k=L+1}^{\infty}\tfrac{q_{k,n}}{\ell_{n}}E\left[\delta(N_{1})\mathbf{1}_{B}\middle|\tfrac{N_{1}L}{\log
n}\in[k-1,k)\right]$
$\displaystyle=\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}+\sum_{k=L+1}^{\infty}\tfrac{q_{k,n}}{\ell_{n}}E\left[\delta(N_{1})\mathbf{1}_{B}\middle|\tfrac{N_{1}L}{\log
n}\in[k-1,k)\right]$ (32)

where, in $(a)$, we define $\delta(N_{1})\triangleq\frac{k}{L}\log{n}-N_{1}$.
Note that given $\frac{k-1}{L}\log{n}\leq N_{1}<\frac{k}{L}\log{n}$,

$\displaystyle\delta(N_{1})\leq(\log{n})/{L}.$ (33)

The second summation in (II-D) can be upper bounded as

$\displaystyle\frac{1}{\ell_{n}}\sum_{k=L+1}^{\infty}q_{k}E[\delta(N_{1})\mathbf{1}_{B}|\tfrac{N_{1}L}{\log
n}\in[k-1,k)]$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\log
n}{\ell_{n}}\sum_{k=L+1}^{\infty}\frac{q_{k}}{L}E[\mathbf{1}_{B}|\tfrac{N_{1}L}{\log
n}\in[k-1,k)]$
$\displaystyle\leq\frac{\log{n}}{\ell_{n}L}\sum_{k=L+1}^{\infty}q_{k}\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\log{n}}{\ell_{n}L},$
(34)

where (a) follows from (33) and (b) follows because $q_{k,n}$ is a probability
mass function over $k\in\\{0,1,2,\dots\\}$. In summary equations (II-D)-(II-D)
show that

$\displaystyle\sum_{k=1}^{J}\frac{H(\mathcal{Y}_{k})}{n}\leq\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}-\frac{\log{n}}{\ell_{n}}E[\mathbf{1}_{\tilde{B}}]+\frac{\log{n}}{\ell_{n}L}+A(n).$
(35)

Lemma 4 formalizes $H(\mathcal{Y}_{\geq J})/n$ being finite as $n\to\infty$,
and Lemma 5 handles the term $A(n)$.

######  Lemma 4.

The entropy of the set $\mathcal{Y}_{\geq J}$ is upper bounded as

$\lim_{n\to\infty}\frac{H(\mathcal{Y}_{\geq J})}{n}\leq
2\left(S\sqrt{L/J}+\delta\right),$

for some finite $S$, and every $J$, $L$ and $\delta>0$.

######  Lemma 5.

As $n\to\infty$, $A(n)\to 0$.

The proofs of Lemmas 4 and 5 are in Appendix F and E. From (23) and (35), we
obtain

$\displaystyle R$
$\displaystyle\leq\lim_{n\to\infty}\left(\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}-\frac{\log{n}}{\ell_{n}}E[\mathbf{1}_{\tilde{B}}]+A(n)+\frac{H(\mathcal{Y}_{\geq
J})}{n}\right)$ $\displaystyle+\lim_{n\to\infty}\frac{\log{n}}{\ell_{n}L}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}{\rm
F}_{d}\\{\log{n}\\}-{\rm
A}_{d}\\{\log{n}\\}+2\left(S\sqrt{L/J}+\delta\right)+\alpha/L,$ (36)

where $(a)$ is due to Lemmas 4 and 5, followed by Definitions 1 and 2. Note
here that the equivalence between the terms in (II-D) and Definitions 1 and 2
are implied by Lemmas 1 and 2 (which are stated in the previous section).
Further, note that (II-D) holds for all integers $J>L$ and any $\delta>0$. We
can thus pick $L=\log{J}$ and let $\delta\to 0$ and $J\to\infty$. This proves
the converse part of Theorem 1.

##  III The Noisy Torn Paper Channel

In the previous section, we characterized the capacity of a TPC with arbitrary
fragment length distribution and fragment deletion probabilities. The capacity
expression provides insights on the impact of strand breaks and missing
strands in DNA data storage, but does not incorporate the practical limitation
that DNA synthesis and sequencing technologies are subject to symbol-level
noise, including substitutions, insertions and deletions. For that reason, in
this section we study the impact of bit-wise noise in the capacity of the TPC.

We consider the TPC with BSC noise as shown in Figure 2. Note that this a
straightforward extension of the setting discussed in Section II-A. The only
difference is that the channel first passes the input string through a Binary
Symmetric Channel (BSC) with crossover probability $p$. The rest of the
process remains the same. For simplicity we also assume that no fragments are
lost. As before we seek to characterize the capacity of this channel.

We conjecture that, as in the noiseless case, the capacity of this channel
will retain the form of “F $-$ A”. But the presence of noise adds a layer of
complexity, making it more difficult to express the capacity of this channel
in general. We instead prove inner and outer bounds that match for certain
choices of fragment length distributions. The main theorem of this section is
as follows:

######  Theorem 3.

For the TPC with BSC$(p)$ noise, all rates $R$ less than $R_{\rm in}$ are
achievable, where

$\displaystyle R_{\rm in}=(1-H(p)){\rm
F}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}-{\rm
A}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}.$ (37)

Moreover no rates $R$ greater than $R_{\rm out}$ are achievable, where

$\displaystyle R_{\rm out}=(1-H(p)){\rm F}{\left\\{\log{n}\right\\}}-{\rm
A}{\left\\{\frac{2\log{n}}{1-H(2p)}\right\\}}.$ (38)

Notice that if we consider a fragment length distribution where
$N_{i}\geq\frac{2\log{n}}{1-H(2p)}$ with probability $1$, no fragments are
discarded in the computation of ${\rm F}{}$ and ${\rm A}{}$ for both the inner
bound and the outer bound and the bounds match. Specifically the capacity is
equal to $(1-H(p)){\rm F}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}-{\rm
A}{\left\\{\frac{\log{n}}{1-H(p)}\right\\}}$, which matches the capacity
conjecture in (5). Moreover we notice that even when $N_{1}$ is allowed to
take values less than $\frac{2\log{n}}{1-H(2p)}$, the gap between the lower
and upper bounds is not too large as seen in Figure 3. Specifically recalling
that $1/\alpha=\lim_{n\to\infty}\ell_{n}/\log{n}$, the x-axis of the figure is
the normalized expected length of a fragment. As this value is increased, the
gap between the lower and upper bound reduces, as seen in Figure 3.

Moreover when $N_{1}\geq\frac{2\log{n}}{1-H(2p)}$ with probability $1$, we
have ${\rm F}=1$ and ${\rm A}=\alpha$, where we recall that
$\alpha:=\lim_{n\to\infty}\log{n}/\ell_{n}$. This implies the following
corollary which states the capacity for a class of noisy TPCs.

######  Corollary 4.

If $N_{1}\geq\frac{2\log{n}}{1-H(2p)}$ with probability $1$, the capacity
$C_{\textrm{noisy-TPC}}$ of the TPC is

$\displaystyle C_{\textrm{noisy-TPC}}=1-H(p)-\alpha.$ (39)

Interestingly, this result for fragment lengths greater than the threshold
$\ell_{n}\geq\frac{2\log{n}}{1-H(2p)}$ matches the capacity of the noisy
shuffling channel. This implies that, beyond this threshold, the relative
differences in fragment lengths become irrelevant. For example, two
channels—one with an arbitrary distribution where $E[N_{i}]=\ell_{n}$, and the
noisy shuffling channel with deterministic fragment lengths $\ell_{n}$—have
identical capacities. This is surprising since the capacity is independent of
the distribution differences between the two channels, when
$N_{1}\geq\frac{2\log{n}}{1-H(2p)}$.

Figure 3:  Comparison between inner and outer bounds to the capacity of Noisy
TPC for $N_{1}\sim\text{Geometric}(1/\ell_{n})$ and noise parameter (a)$\text{
}p=0.01$, (b)$\text{ }p=0.02$ and (c)$\text{ }p=0.05$. We see that the inner
and outer bounds are close to each other as $1/\alpha$ increases and in fact
matches when $1/\alpha$ goes to $\infty$.

###  III-A Achievable rates via typical covering

We again use a random coding argument to prove the achievability of Theorem 3.
But we cannot use a decoder that simply looks for codewords that contain all
sequences in $\mathcal{Y}$ as substrings of the codeword, as we did before.
This is because these fragments are in general corrupted by BSC noise.
Therefore we introduce the concept of typical covering instead.

We generate a codebook $\mathcal{C}$ with $2^{nR}$ codewords, by independently
picking each letter as $\text{Bern}(1/2)$. Let the resulting random codebook
be
$\mathcal{C}=\\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{2^{nR}}\\}$.
Assume that $W=1$ is the message that is transmitted. The output $\mathcal{Y}$
is available at the decoder.

We consider a suboptimal decoder that throws away all pieces of size less than
$\gamma\log{n}$, where $\gamma$ is a parameter that we will optimize later. We
call the new set $\mathcal{Y}_{\geq\gamma}$. Now we define the notion of
typical covering on the set $\mathcal{Y}_{\geq\gamma}$ and string $x^{n}$.

######  Definition 3.

(Typical covering) The set $\mathcal{Y}_{\geq\gamma}$ is said to typically
cover a codeword $x^{n}$ if the set of reads in $\mathcal{Y}_{\geq\gamma}$ can
be aligned to $x^{n}$, such that the aligned segments are jointly typical.
That is for $\vec{Y}$, a given ordering of $\mathcal{Y}_{\geq\gamma}$

$\displaystyle\left(x^{n},\vec{Y}\right)\in T_{\epsilon}^{n}(X,Y),$ (40)

where $T_{\epsilon^{\prime}}^{n}(X,Y)$ denotes the set of
$\epsilon^{\prime}$-jointly typical sequences [33] $(X^{n},Y^{n})$.

The notion of typical covering is essentially a general version of the notion
of alignment considered in Section II-C for the standard TPC. We thus bound
the probability of error averaged over all codebook choices as

$\displaystyle\text{Pr}(\mathcal{E})=\text{Pr}(\mathcal{E}|W=1)$
$\displaystyle=\text{Pr}\left(\exists\text{ }j\neq
1:\mathcal{Y}_{\geq\gamma}\text{ typically covers }x_{j}\middle|W=1\right)$
(41)

We now state two lemmas that are straightforward generalizations of the lemmas
in Section II-C.

######  Lemma 6.

For any $\epsilon>0$, as $n\to\infty$,

$\displaystyle\Pr\left(\left|\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\\{N_{i}\geq\gamma\log{n}\\}}-\frac{E[N_{1}\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}\right|>\frac{E[N_{1}\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}\epsilon\right)\to
0.$ (42)

######  Lemma 7.

For any $\epsilon>0$, as $n\to\infty$,

$\displaystyle\Pr\left(\middle|\sum_{i=1}^{K}\mathbf{1}_{\\{N_{i}\geq\gamma\log{n}\\}}-\frac{nE[\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}\middle|\geq\frac{nE[\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}\epsilon\right)\to
0.$ (43)

Now we let
$B_{1}=(1+\epsilon)\frac{nE[\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}$
and
$B_{2}=(1-\epsilon)\frac{E[N_{1}\mathbf{1}_{\\{N_{1}\geq\gamma\log{n}\\}}]}{\ell_{n}}$
and define the event

$\displaystyle\mathcal{B}=\left\\{\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq\gamma}\\}}>B_{1}\right\\}\cup\left\\{\frac{1}{n}\sum_{i=1}^{K}N_{i}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq\gamma}\\}}<B_{2}\right\\}.$
(44)

Lemmas 6 and 7 imply that $\text{Pr}(\mathcal{B})\to 0$ as $n\to\infty$.
Therefore,

$\displaystyle\text{Pr}(\mathcal{E})$ $\displaystyle=\text{Pr}(\exists\text{
}j\neq 1:\mathcal{Y}_{\geq\gamma}\text{ typically covers }x_{j}|W=1)$
$\displaystyle\leq\text{Pr}(\exists\text{ }j\neq
1:\mathcal{Y}_{\geq\gamma}\text{ typically covers
}x_{j}|W=1,\overline{\mathcal{B}})$ $\displaystyle+\text{Pr}(\mathcal{B})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}|\mathcal{C}|\frac{n^{B_{1}}}{2^{nB_{2}I(A;B)(1-\epsilon^{\prime})}}+\text{Pr}(\mathcal{B})$
$\displaystyle\leq
2^{nR}2^{B_{1}\log{n}}2^{-nB_{2}(1-H(p))(1-\epsilon^{\prime})}+o(1),$ (45)

where $A$ is a Bern$\left(\frac{1}{2}\right)$ random variable and
$B=A\oplus\text{Bern}(p)$. Inequality $(a)$ follows from the union bound and
the fact that given $\overline{\mathcal{B}}$, there are at most $n^{B_{1}}$
ways to align $\mathcal{Y}_{\geq\gamma}$ to a codeword $x_{j}$. To see this
note that, given $|\mathcal{Y}_{\geq\gamma}|<B_{1}$, there are at most $n$
places the fragments can start from to align each piece and at most $B_{1}$
such pieces. Finally, the probability that there is an erroneous typical
covering of length $nB_{2}$ corresponds to the probability that two
independent Bern$\left(\frac{1}{2}\right)$ sequences seem jointly typical
according to $(A,B)$, which by standard typicality arguments, is at most
$2^{-nB_{2}I(A;B)(1-\epsilon^{\prime})}$ [33]. Note here that
$I(A;B)=H(A)-H(A|B)=1-H(p).$ From this we conclude that $\Pr(\mathcal{E})\to
0$ if

$\displaystyle
R<\lim_{n\to\infty}\left(\frac{(1-\epsilon^{\prime})(1-\epsilon)(1-H(p))}{\ell_{n}}E\left[N_{1}\mathbf{1}_{N_{1}\geq\gamma\log{n}}\right]-\frac{(1+\epsilon)\log{n}}{\ell_{n}}E\left[\mathbf{1}_{N_{1}\geq\gamma\log{n}}\right]\right).$
(46)

Now if we let $\epsilon\to 0$ and $\epsilon^{\prime}\to 0$, we can rewrite
(46) as

$\displaystyle R$
$\displaystyle<\lim_{n\to\infty}\left(\frac{\log{n}}{\ell_{n}}E\left[\left(\frac{N_{1}(1-H(p))}{\log{n}}-1\right)\mathbf{1}_{N_{1}\geq\gamma\log{n}}\right]\right)$
$\displaystyle=\lim_{n\to\infty}\left(\frac{\log{n}}{\ell_{n}}\sum_{x\geq\gamma\log{n}}\left(\frac{x(1-H(p))}{\log{n}}-1\right)p_{N_{1}}(x)\right).$
(47)

Note that since $p_{N_{1}}\geq 0$, the best achievability is obtained by
setting $\gamma$ to be the least value such that
$\left(\frac{x(1-H(p))}{\log{n}}-1\right)$ is greater than $0$, which
maximizes the above expression. This value is $\gamma^{*}=\frac{1}{1-H(p)}$.
Substituting this value of $\gamma$, we conclude that all rates $R\leq R_{\rm
in}$ are achievable.

###  III-B Outer-bound

In order to prove the converse for the noisy case, we again partition the set
$\mathcal{Y}$ into a set of parallel channels, each with fragments of roughly
the same length. To each of these channels, we apply a generalization of the
result in [11], which considered a noisy shuffling channel with pieces of a
fixed size. However, the result from [11] cannot be applied to the channels
with very short fragments. We therefore need to apply a different, possibly
looser bound for the channels with short fragments. More precisely let
$\vec{Y}_{i}$ be the output of the string $\vec{X}_{i}$ after it is passed
through the BSC$(p)$ channel. Then we define $\mathcal{Y}_{k}$ as

$\displaystyle\mathcal{Y}_{k}\triangleq\left\\{\vec{Y}_{i}\in\mathcal{Y}:\frac{k-1}{L}\log{n}\leq
N_{i}<\frac{k}{L}\log{n}\right\\}.$ (48)

Note that the above definition is slightly different from the definition used
in equation (22) from Section II-D. Since fragments are corrupted by noise,
the output is not just the unordered set of input strings. Then, from a
standard argument with Fano’s inequality, we have

$\displaystyle R$
$\displaystyle\leq\lim_{n\to\infty}\frac{I(X^{n};\mathcal{Y})}{n}.$ (49)

Let $Z^{n}$ be a binary string representing whether a bit has been flipped at
a given position in $X^{n}$. We also define $T_{2}^{n}$ to be the sequence of
tearing locations on string $X^{n}$. More precisely, let
$T_{2},T_{3},\dots,T_{n}$ be binary indicator random variables of whether
there is a cut between $X_{i-1}$ and $X_{i}$. The random vector
$\vec{{\mathcal{Z}}}_{k}$ is the ordered set of substrings of size in
$\left[\frac{k-1}{L}\log{n},\frac{k}{L}\log{n}\right)$ extracted from $Z^{n}$
based on tearing locations $T_{2}^{n}$. That is, if we take two successive
$1$s in $T_{2}^{n}$, say $T_{i}=1$ and $T_{j}=1$, such that
$j-(i+1)\in\left[\frac{k-1}{L}\log{n},\frac{k}{L}\log{n}\right)$, then
$Z_{i+1}^{j}\in\vec{Z}_{k}$. $\vec{{\mathcal{X}}}_{k}$ is defined in a similar
way.

We further define $\mathcal{Y}_{\leq
A}:=\\{\vec{Y}_{i}:N_{i}\leq(A/L)\log{n}\\}$, for some constant $A$. The
definitions of $\mathcal{Y}_{\in[A:B]}$ and $\mathcal{Y}_{\geq A}$ are
similar. Then for an integer $J$, we have that

$\displaystyle I(X^{n};\mathcal{Y})=H(\mathcal{Y})-H(\mathcal{Y}|X^{n})\leq
H(\mathcal{Y}_{\leq L})+H(\mathcal{Y}_{\in(L:J)})+H(\mathcal{Y}_{\geq
J})-H(\mathcal{Y}|X^{n},T_{2}^{n})$
$\displaystyle=H(\mathcal{Y}_{\in(L:J)})-H(\mathcal{Y},Z^{n}|X^{n},T_{2}^{n})+H(Z^{n}|X^{n},\mathcal{Y},T_{2}^{n})+H(\mathcal{Y}_{\leq
L})+H(\mathcal{Y}_{\geq J})$
$\displaystyle=H(\mathcal{Y}_{\in(L:J)})+H(Z^{n}|X^{n},\mathcal{Y},T_{2}^{n})-nH(p)+H(\mathcal{Y}_{\leq
L})+H(\mathcal{Y}_{\geq J}).$ (50)

Now to bound the term $H(Z^{n}|X^{n},\mathcal{Y},T_{2}^{n})$, we note that,
given the tearing locations $T_{2}^{n}$, $Z^{n}$ is a function of
$\vec{Z}_{1},\vec{Z_{2}},\dots$, since the substrings in each
$\vec{{\mathcal{Z}}}_{k}$ (which is an ordered set) can be uniquely located in
$Z^{n}$ based on the tearing points $T_{2}^{n}$. Hence,

$\displaystyle H(Z^{n}|X^{n},\mathcal{Y},T_{2}^{n})\leq
H(\vec{\mathcal{Z}}_{1},\vec{\mathcal{Z}}_{2},\dots,\vec{\mathcal{Z}}_{J},\vec{\mathcal{Z}}_{\geq
J}|X^{n},\mathcal{Y},T_{2}^{n})$ (51)
$\displaystyle\leq\sum_{k=1}^{J}H(\vec{{\mathcal{Z}}}_{k}|X^{n},\mathcal{Y})+H(\vec{{\mathcal{Z}}}_{\geq
J})\leq\sum_{k=1}^{L}H(\vec{{\mathcal{Z}}}_{k})+\sum_{k=L+1}^{J}H(\vec{{\mathcal{Z}}}_{k}|X^{n},\mathcal{Y})+H(\vec{{\mathcal{Z}}}_{\geq
J}).$

Therefore from (III-B) and (51), and using this definition one can conclude
that

$\displaystyle I(X^{n};\mathcal{Y})$
$\displaystyle\leq\sum_{k=L+1}^{J}\left(H(\mathcal{Y}_{k})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k})\right)+\sum_{k=1}^{L}H(\vec{{\mathcal{Z}}}_{k})$
$\displaystyle-nH(p)+H(\mathcal{Y}_{\leq L})+H(\mathcal{Y}_{\geq
J})+H(\vec{{\mathcal{Z}}}_{\geq J}).$ (52)

Now we follow steps similar to Section II-D. First we define the probability

$\displaystyle q_{k,n}$ $\displaystyle=\text{Pr}\left(\frac{k-1}{L}\log{n}\leq
N_{1}<\frac{k}{L}\log{n}\right).$ (53)

Additionally, we define the event

$\displaystyle\mathcal{E}_{k,n}=\\{||\mathcal{Y}_{k}|-nq_{k,n}/\ell_{n}|>n\epsilon_{n}/\ell_{n}\\}.$

We establish that $|\mathcal{Y}_{k}|$ concentrates in the following lemma,
which is similar to Lemma 3, but for the $\mathcal{Y}_{k}$ defined in (48).

######  Lemma 8.

For $\epsilon_{n}>0$ and n large enough,

$\displaystyle\Pr(\mathcal{E}_{k,n})\leq
2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}.$
(54)

The proof of the lemma is the similar to Lemma 3. As before we can set
$\epsilon_{n}=1/\log{n}$ to guarantee that $\epsilon_{n}\to 0$ and
$\Pr(\mathcal{E}_{k,n})\to 0$, as $n\to\infty$ for a fixed $k$. Now, given
$\bar{\mathcal{E}}_{k,n}$,

$\displaystyle\left(-\epsilon_{n}+q_{k,n}\right)\frac{n}{\ell_{n}}\leq|\vec{\mathcal{Z}}_{k}|=|\vec{\mathcal{X}}_{k}|=|\mathcal{Y}_{k}|\leq
M_{k},$ (55)

where

$\displaystyle M_{k}:=\left(\epsilon_{n}+q_{k,n}\right)\frac{n}{\ell_{n}}.$
(56)

As in Section II-D, we expand the terms $H(\mathcal{Y}_{k})$ and
$H(\vec{\mathcal{Z}}_{k}|\vec{\mathcal{X}}_{k},\mathcal{Y}_{k})$ as

$\displaystyle
H(\mathcal{Y}_{k})+H(\vec{\mathcal{Z}}_{k}|\vec{\mathcal{X}}_{k},\mathcal{Y}_{k})\leq
H(\mathcal{Y}_{k},\mathbf{1}_{\mathcal{E}_{k,n}})+H(\vec{\mathcal{Z}}_{k},\mathbf{1}_{\mathcal{E}_{k,n}}|\vec{\mathcal{X}}_{k},\mathcal{Y}_{k})$
$\displaystyle\leq
2(H(\Pr(\mathcal{E}_{k,n}))+2n\Pr(\mathcal{E}_{k,n}))+H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{\mathcal{Z}}_{k}|\vec{\mathcal{X}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n}).$
(57)

Let us first consider the term $H(\mathcal{Y}_{\leq L})$ which appears in
(III-B). The term $H(\mathcal{Y}_{\leq L})/n$ can be expanded as follows

$\displaystyle\frac{H(\mathcal{Y}_{\leq
L})}{n}=\sum_{k=1}^{L}\frac{H(\mathcal{Y}_{k})}{n}\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k=1}^{L}\left(\frac{H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})}{n}+2\Pr(\mathcal{E}_{k,n})+\frac{1}{n}\right),$
(58)

where $(a)$ follows similarly to (III-B). We can thus bound
$I(X^{n};\mathcal{Y})/n$ using (III-B), (III-B), (58) as

$\displaystyle\frac{I(X^{n};\mathcal{Y})}{n}$
$\displaystyle\leq\frac{1}{n}\sum_{k=L+1}^{J}\left(H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})\right)+\frac{1}{n}\sum_{k=1}^{L}H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})$
$\displaystyle+2\sum_{k=1}^{J}\left(2\Pr(\mathcal{E}_{k,n})+\frac{1}{n}\right)+\frac{H(\mathcal{Y}_{\geq
J})+H(\vec{{\mathcal{Z}}}_{\geq
J})}{n}+\frac{1}{n}\sum_{k=1}^{L}H(\vec{{\mathcal{Z}}}_{k}|\bar{\mathcal{E}}_{k,n})-H(p).$
(59)

Notice the first term in (III-B). They contain entropy terms on pieces of
“roughly” the same size. $H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})$ and
$H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})$
contend with each other in a way similar to [11]. Carefully using this tension
lets us apply a non-trivial upper bound on the sum of these entropies in a
certain regime. This is summarized formally in the following lemma, which is
the main work-horse to prove the outer bound stated in Theorem 3.

######  Lemma 9.

If $\frac{k-1}{L}>\frac{2}{1-H(2p)}$, we have

$\displaystyle
H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})$
$\displaystyle\leq\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}-\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)+o(M_{k}\log{M_{k}}),$
(60)

else

$\displaystyle
H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})\leq\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}+o(M_{k}\log{M_{k}}).$
(61)

The lemma above is the main additional technical step in this proof compared
to the noise-free case. Lemma 9 is proved in Appendix G. Using this lemma we
can evaluate a closed-form expression as an upper bound to the first term in
(III-B). This is summarized in the following lemma:

######  Lemma 10.

For $n$ large enough, it holds that

$\displaystyle\sum_{k=L+1}^{J}\left(H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k})\right)$
$\displaystyle=n\left(\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2\log{n}}{1-H(2p)}\right\\}}\right]\right)+o(n).$
(62)

Lemma 10 is proved in Appendix H. We now a state some lemmas to upper bound
the other terms in (III-B). Lemma 11 below formalizes $(H(\mathcal{Y}_{\geq
J})+H(\vec{Z}_{\geq J}))/n$ being finite as $n\to\infty$.

######  Lemma 11.

The entropy of the set $\mathcal{Y}_{\geq J}$ is upper bounded as

$\lim_{n\to\infty}\frac{H(\mathcal{Y}_{\geq J})+H(\vec{{\mathcal{Z}}}_{\geq
J})}{n}\leq 4\left(S\sqrt{L/J}+\delta\right),$

for some finite $S$, and every $J$, $L$ and $\delta>0$.

This lemma is a straightforward extension of Lemma 4. Moreover we can prove
the following lemma to show that the second and third summations in (III-B)
are small as $n\to\infty$ .

######  Lemma 12.

Define

$\displaystyle
B(n):=\frac{1}{n}\sum_{k=1}^{L}H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+2\sum_{k=1}^{J}\left(2\Pr(\mathcal{E}_{k,n})+\frac{1}{n}\right).$
(63)

Then $B(n)\to 0$ as $n\to\infty$.

$\lim_{n\to\infty}B(n)=0.$

This lemma is proved in Appendix I. We can thus conclude by applying Lemma 10,
Lemma 12 and Lemma 11 to (III-B) that

$\displaystyle
R\leq\lim_{n\to\infty}\frac{I(X^{n};\mathcal{Y})}{n}\stackrel{{\scriptstyle(a)}}{{\leq}}\lim_{n\to\infty}\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\lim_{n\to\infty}\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2}{1-H(2p)}\log{n}\right\\}}\right]$
$\displaystyle+\lim_{n\to\infty}B(n)+4\left(S\sqrt{L/J}+\delta\right)-H(p)+\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{L}H(\vec{{\mathcal{Z}}}_{k}|\overline{\mathcal{E}}_{k,n})+\lim_{n\to\infty}o(1)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\lim_{n\to\infty}\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\lim_{n\to\infty}\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2}{1-H(2p)}\log{n}\right\\}}\right]-\lim_{n\to\infty}\frac{H(p)}{\ell_{n}}E[N_{1}]$
$\displaystyle+\lim_{n\to\infty}\frac{H(p)}{\ell_{n}}\sum_{k=1}^{L}(\epsilon_{n}+q_{k,n})\frac{k}{L}\log{n}+4\left(S\sqrt{L/J}+\delta\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\lim_{n\to\infty}\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\lim_{n\to\infty}\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2}{1-H(2p)}\log{n}\right\\}}\right]$
$\displaystyle+\frac{H(p)}{\ell_{n}}E[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}]+\lim_{n\to\infty}\left(\frac{\log{n}}{\ell_{n}L}+\frac{LH(p)\epsilon_{n}}{\ell_{n}}\right)+4\left(S\sqrt{L/J}+\delta\right)$
$\displaystyle=\lim_{n\to\infty}\left((1-H(p))\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2\log{n}}{1-H(2p)}\right\\}}\right]\right)+4\left(S\sqrt{L/J}+\delta\right)+\frac{\alpha}{L},$
$\displaystyle=(1-H(p)){\rm F}\\{\log{n}\\}-{\rm
A}\left\\{\frac{2\log{n}}{1-H(2p)}\right\\}+4\left(S\sqrt{L/J}+\delta\right)+\frac{\alpha}{L},$
(64)

where $(a)$ is due to Lemma 10 and Lemma 4, $(b)$ is due to Lemma 12 and the
fact that the number of bits in an ordered set $\vec{{\mathcal{Z}}}_{k}$ is
upper bounded by

$M_{k}\times\frac{k}{L}\log{n}:=(\epsilon_{n}+q_{k,n})\frac{k}{L}\times\frac{n}{\ell_{n}}\log{n},$

and $(c)$ is due to to arguments considered in equations (II-D), (33) and
(II-D). As before we set $L=\log{J}$ and let $J\to\infty$ and $\delta\to 0$.
This proves the converse of Theorem 3.

##  IV Conclusion

Motivated by the application of DNA and macromolecular data storage, we have
studied the impact of fragment length distribution, deletion probabilities,
and bit-level noise in the capacity of the torn-paper channel. We have shown
that the capacity of a generalized TPC can be expressed as “F$-$A” in the
absence of bit-level noise. Moreover we showed inner and outer bounds, again
of the form “F$-$A”, when the observed sequences are subject to binary
symmetric noise.

A natural question for follow-up work is whether the inner and outer bounds on
the capacity of the TPC with bit-level noise can be tightened. We conjecture
that the inner bound in Section III-A is tight, and the slack is in the
converse argument. Related results on the Noisy Shuffling Channel [34] imply
that the first bound in Lemma 9 (equation 9) likely holds given a less
stringent condition, which would lead to a tighter outer bound. For instance
if it were true that (9) in Lemma 9 holds for any $(p,r)$ such that
$1-H(p)-1/r\geq 0$, instead of the original condition, it can be verified that
the same analysis used in Section III-B yields an outer bound that matches the
inner bound.

An other natural question, is what the results generalise to when you consider
a two dimensional codeword that is torn. This is particularly relevant in
forensics where typical messages are encoded in two dimensions (for example in
fingerprinting). Precisely this model is as follows: Assume messages are to be
written on a two dimensional codeword $X^{n\times m}$. This codeword is then
passed through a torn paper channel that tears this codeword into arbitrary
shapes. These pieces are then available to the decoder. What is the capacity
of this channel? This channel can be viewed as a generalisation of the TPC,
since if we set $m=1$ we get back the original TPC. But for $m$ greater than
$1$, unlike the TPC, spatial information can play a role in discerning the
order. Since the shapes are more arbitrary, it may be easier to order pieces
of the codeword based on matching shapes, not unlike a “jigsaw” puzzle. How we
make use of this spatial information or if it is beneficial to do so from a
capacity standpoint is subject to future work.

## References

  * Shomorony and Vahid [2020] Ilan Shomorony and Alireza Vahid.  Communicating over the torn-paper channel.  In GLOBECOM 2020 - 2020 IEEE Global Communications Conference, pages 1–6, 2020.  doi: 10.1109/GLOBECOM42002.2020.9348147.
  * Church et al. [2012] G. M. Church, Y. Gao, and S. Kosuri.  Next-generation digital information storage in DNA.  Science, 337(6102):1628–1628, 2012.
  * Goldman et al. [2013] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney.  Towards practical, high-capacity, low-maintenance information storage in synthesized DNA.  Nature, 494(7435):77–80, 2013.
  * Grass et al. [2015] R. Grass, R. Heckel, M. Puddu, D. Paunescu, and W. J. Stark.  Robust chemical preservation of digital information on DNA in silica with error-correcting codes.  Angewandte Chemie International Edition, 54(8):2552–2555, 2015.
  * Bornholt et al. [2016] J. Bornholt, R. Lopez, D. M. Carmean, L. Ceze, G. Seelig, and K. Strauss.  A DNA-Based Archival Storage System.  In Proc. of ASPLOS, pages 637–649, New York, NY, USA, 2016. ACM.
  * Erlich and Zielinski [2017] Y. Erlich and D. Zielinski.  Dna fountain enables a robust and efficient storage architecture.  Science, 2017.
  * Organick et al. [2018] Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Konstantin Makarychev, Miklos Z. Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, and et al.  Random access in large-scale DNA data storage.  Nature Biotechnology, 2018.
  * Heckel et al. [2018] R. Heckel, G. Mikutis, and R. N. Grass.  A Characterization of the DNA Data Storage Channel.  arXiv:1803.03322, 2018.
  * Brooks et al. [2020] Evie Brooks, Meghan Prusinowski, Susan Gross, and Tatiana Trejos.  Forensic physical fits in the trace evidence discipline: A review.  Forensic Science International, 313:110349, 2020.  ISSN 0379-0738.  doi: https://doi.org/10.1016/j.forsciint.2020.110349.  URL https://www.sciencedirect.com/science/article/pii/S0379073820302115.
  * Wang et al. [2023] Canran Wang, Jin Sima, and Netanel Raviv.  Break-resilient codes for forensic 3d fingerprinting, 2023.
  * Shomorony and Heckel [2019] I. Shomorony and R. Heckel.  Capacity results for the noisy shuffling channel.  In IEEE International Symposium on Information Theory (ISIT), 2019.
  * Ravi et al. [2021] Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony.  Capacity of the torn paper channel with lost pieces.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1937–1942, 2021.  doi: 10.1109/ISIT45174.2021.9518272.
  * Shomorony and Vahid [2021] Ilan Shomorony and Alireza Vahid.  Torn-paper coding.  IEEE Transactions on Information Theory, 67(12):7904–7913, 2021.
  * Lenz et al. [2019] Andreas Lenz, P. Siegel, Antonia Wachter-Zeh, and Eitan Yaakobi.  An upper bound on the capacity of the DNA storage channel.  In IEEE Information Theory Workshop, 2019.
  * Heckel et al. [2017] R. Heckel, I. Shomorony, K. Ramchandran, and D. N. C. Tse.  Fundamental limits of dna storage systems.  In IEEE International Symposium on Information Theory (ISIT), pages 3130–3134, 2017.
  * Shomorony and Heckel [2021] Ilan Shomorony and Reinhard Heckel.  Dna-based storage: Models and fundamental limits.  IEEE Transactions on Information Theory, 67(6):3675–3689, 2021.
  * Lenz et al. [2020] Andreas Lenz, Paul H Siegel, Antonia Wachter-Zeh, and Eitan Yaakohi.  Achieving the capacity of the dna storage channel.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8846–8850. IEEE, 2020.
  * Shomorony et al. [2022] Ilan Shomorony, Reinhard Heckel, et al.  Information-theoretic foundations of dna data storage.  Foundations and Trends® in Communications and Information Theory, 19(1):1–106, 2022.
  * Ravi et al. [2024] Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony.  An information theory for out-of-order media with applications in dna data storage.  IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, 10(2):334–348, 2024.  doi: 10.1109/TMBMC.2024.3403759.
  * Bar-Lev et al. [2022] Daniella Bar-Lev, Sagi Marcovich, Eitan Yaakobi, and Yonatan Yehezkeally.  Adversarial torn-paper codes.  arXiv preprint arXiv:2201.11150, 2022.
  * Ravi et al. [2022a] Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony.  Coded shotgun sequencing.  IEEE Journal on Selected Areas in Information Theory, 3(1):147–159, 2022a.  doi: 10.1109/JSAIT.2022.3151737.
  * Ravi et al. [2022b] Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony.  Capacity of the shotgun sequencing channel.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 210–215, 2022b.  doi: 10.1109/ISIT50566.2022.9834409.
  * Motahari et al. [2013] A. Motahari, G. Bresler, and D. Tse.  Information Theory of DNA Shotgun Sequencing.  IEEE Transactions on Information Theory, 59(10):6273–6289, Oct. 2013.
  * Gabrys and Milenkovic [2018] Ryan Gabrys and Olgica Milenkovic.  Unique reconstruction of coded sequences from multiset substring spectra.  In 2018 IEEE International Symposium on Information Theory (ISIT), pages 2540–2544. IEEE, 2018.
  * Makur [2018] Anuran Makur.  Information capacity of bsc and bec permutation channels.  In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1112–1119. IEEE, 2018.
  * Tang and Polyanskiy [2022] Jennifer Tang and Yury Polyanskiy.  Capacity of noisy permutation channels.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1987–1992, 2022.  doi: 10.1109/ISIT50566.2022.9834509.
  * Kiah et al. [2016] H. M. Kiah, G. J. Puleo, and O. Milenkovic.  Codes for DNA sequence profiles.  IEEE Trans. on Information Theory, 62(6):3125–3146, 2016.
  * Yazdi et al. [2015] H. T. Yazdi, Y. Yuan, J. Ma, H. Zhao, and O. Milenkovic.  A rewritable, random-access DNA-based storage system.  Sci. Rep., 5:14138, 2015.
  * Gabrys et al. [2015] R. Gabrys, H. M. Kiah, and O. Milenkovic.  Asymmetric Lee distance codes: New bounds and constructions.  In 2015 IEEE Information Theory Workshop (ITW), pages 1–5, 2015.
  * Sala et al. [2017] F. Sala, R. Gabrys, C. Schoeny, and L. Dolecek.  Exact reconstruction from insertions in synchronization codes.  IEEE Transactions on Information Theory, 2017.
  * Nassirpour and Vahid [2021] Sajjad Nassirpour and Alireza Vahid.  Embedded codes for reassembling non-overlapping random dna fragments.  IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, 7(1):40–50, 2021.  doi: 10.1109/TMBMC.2020.3035370.
  * Nassirpour et al. [2024] Sajjad Nassirpour, Ilan Shomorony, and Alireza Vahid.  Dna merge-sort: A family of nested varshamov-tenengolts reassembly codes for out-of-order media.  IEEE Transactions on Communications, 72(3):1303–1317, 2024.  doi: 10.1109/TCOMM.2023.3335409.
  * Gamal and Kim [2012] A. El Gamal and Y.-H. Kim.  Network Information Theory.  Cambridge University Press, 2012.
  * Weinberger and Merhav [2021] Nir Weinberger and Neri Merhav.  The DNA storage channel: Capacity and error probability.  CoRR, abs/2109.12549, 2021.  URL https://arxiv.org/abs/2109.12549.

##  Appendix A Proof of Corollary 2

See 2 Corollary 2 provides us with an expression to numerically compute the
TPC capacity for certain classes of fragment length distributions ($N_{i}$).
Intuitively it holds for distributions of $N_{i}$ which have a continuous
analog (for example the geometric or uniform distributions). We proceed as
follows:

$\displaystyle C={\rm F}_{d}\\{\log{n}\\}-{\rm A}_{d}\\{\log{n}\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\lim_{n\to\infty}\left(\frac{E[N_{1}\mathbf{1}_{\tilde{B}}]}{\ell_{n}}-\frac{\log{n}E[\mathbf{1}_{\tilde{B}}]}{\ell_{n}}\right)$
$\displaystyle=\lim_{n\to\infty}(\log{n}/\ell_{n})\lim_{n\to\infty}E\left[\left(\frac{N_{1}}{\log{n}}-1\right)\mathbf{1}_{\tilde{B}}\right]$
$\displaystyle=\alpha\lim_{n\to\infty}E\left[\left(\frac{N_{1}}{\log{n}}-1\right)E\left[\mathbf{1}_{\tilde{B}}|N_{1}\right]\right]$
$\displaystyle=\alpha\lim_{n\to\infty}\sum_{x=\log{n}}^{\infty}\left(\frac{x}{\log{n}}-1\right)(1-\tilde{d}(x))\text{Pr}(N_{1}=x).$
(65)

Note in $(a)$ we use an equivalent definition of ${\rm F}$ and ${\rm A}$ that
we employed in (II-C). Now we substitute $x=\beta\log{n}$ in the above
equation, where
$\beta\in\\{1,1+\frac{1}{\log{n}},1+\frac{2}{\log{n}},\dots\\}\triangleq\mathcal{Q}$.
Then we have

$\displaystyle
C=\alpha\lim_{n\to\infty}\sum_{\beta\in\mathcal{Q}}\left(\beta-1\right)(1-\tilde{d}(\beta\log{n}))\text{Pr}(N_{1}=\beta\log{n})$
$\displaystyle=\alpha\lim_{n\to\infty}\sum_{\beta\in\mathcal{Q}}\left(\beta-1\right)(1-\tilde{d}(\beta\log{n}))\frac{\text{Pr}(N_{1}=\beta\log{n})}{\Delta_{n}}\Delta_{n}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\alpha\int_{1}^{\infty}(\beta-1)(1-\hat{d}(\beta))h(\beta)d\beta,$
(66)

where $\lim_{n\to\infty}\text{Pr}(N_{1}=\beta\log{n})\log{n}\triangleq
h(\beta)$ and $\Delta_{n}=\beta+1/\log{n}-\beta$. $(a)$ follows from the
definition of Riemann integration. This result holds when $h(\beta)$ exists
and is finite.

##  Appendix B Proof of Lemma 1

See 1 Define $Z_{i}=N_{i}\textbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}$, $Z=\sum_{i=1}^{K}V_{i}$ and $\tilde{V}=\sum_{i=1}^{n/\ell_{n}}V_{i}$.
Note that $\mathbf{E}[\tilde{V}]=n\mathbf{E}[V_{i}]/\ell_{n}$.
If $\tilde{V}>V$, then $K<n/\ell_{n}$ and

$\displaystyle|V-\tilde{V}|\leq\sum_{i=K+1}^{n/\ell_{n}}V_{i}\leq\sum_{i=K+1}^{n/\ell_{n}}N_{i}\leq\left|\sum_{i=1}^{n/\ell_{n}}N_{i}-n\right|.$
(67)

Similarly if $Z>\tilde{Z}$, then $K>n/\ell_{n}$ and

$\displaystyle|V-\tilde{V}|\leq\sum_{i=n/\ell_{n}}^{K}V_{i}\leq\sum_{i=n/\ell_{n}}^{K}V_{i}\leq\left|\sum_{i=1}^{n/\ell_{n}}N_{i}-n\right|.$
(68)

Therefore

$\displaystyle\text{Pr}(|V-\tilde{V}|\geq\delta
n)\leq\text{Pr}\left(\left|\sum_{i=1}^{n/\ell_{n}}N_{i}-n\right|\geq\delta
n\right)$ $\displaystyle=\text{Pr}\left(\sum_{i=1}^{n/\ell_{n}}N_{i}\geq
n(1+\delta/\ell_{n})\right)+\text{Pr}\left(\sum_{i=1}^{n/\ell_{n}}N_{i}\leq
n(1-\delta/\ell_{n})\right)$
$\displaystyle=\text{Pr}\left(\frac{\ell_{n}}{n}\sum_{i=1}^{n/\ell_{n}}(N_{i}-\mathbf{E}[N_{i}])>\delta\right)$
$\displaystyle+\text{Pr}\left(\frac{\ell_{n}}{n}\sum_{i=1}^{n/\ell_{n}}(N_{i}-\mathbf{E}[N_{i}])<-\delta\right)\leq
2e^{-2\delta^{2}n/\ell_{n}}.$ (69)

Now we use the Chebyshev’s inequality to bound
$|\tilde{V}-\mathbf{E}[\tilde{V}]|$.

$\displaystyle\text{Pr}(|\tilde{V}-\mathbf{E}[\tilde{V}]|>\delta
n)\leq\frac{\text{Var}(\tilde{V_{1}})}{\delta^{2}n}\leq\frac{\text{E}(V_{1}^{2})}{\delta^{2}n}$
$\displaystyle\leq\frac{\mathbf{E}[N_{1}^{2}]}{\delta^{2}n}.$ (70)

Now if
$|V-\tilde{V}|<\frac{n\mathbf{E}[N_{1}\mathbf{1}_{\tilde{B}}]}{2}\epsilon$ and
$|\tilde{V}-\mathbf{E}[\tilde{V}]|<\frac{n\mathbf{E}[N_{1}\mathbf{1}_{\tilde{B}}]}{2}\epsilon$,
then by triangle inequality
$|V-\mathbf{E}[\tilde{V}]|<n\mathbf{E}[N_{1}\mathbf{1}_{\tilde{B}}]\epsilon$.
Therefore (define
$\epsilon^{\prime}:=\mathbf{E}[N_{1}\mathbf{1}_{\tilde{B}}]\epsilon$)

$\displaystyle\text{Pr}(|V-\mathbf{E}[\tilde{V}]|>n\epsilon^{\prime})$
$\displaystyle\leq\text{Pr}(|V-\tilde{V}|>n\epsilon^{\prime}/2)+\text{Pr}(|\tilde{V}-\mathbf{E}[\tilde{V}]|>n\epsilon^{\prime}/2)$
$\displaystyle\leq
2e^{-{\epsilon^{\prime}}^{2}n/(2\ell_{n})}+\frac{\mathbf{E}[N_{1}^{2}]}{{{\epsilon^{\prime}}^{2}}n}\sim
2e^{-\epsilon^{2}n\log^{2}{n}/(2\ell_{n})}+\frac{1}{\epsilon^{2}n}=o(1)\to 0,$
(71)

as $n\to\infty$.

##  Appendix C Proof of Lemma 2

See 2 Define ${\epsilon^{\prime}}:=\epsilon E[\mathbf{1}_{\tilde{B}}]$. We
follow steps similar to Lemma 3. Let $V_{i}=\mathbf{1}_{\tilde{B}}$ for
$i=1,2,\dots$ and $\tilde{V}=\sum_{i=1}^{n/\ell_{n}}V_{i}$. We know that,

$\displaystyle E[\tilde{V}]=\frac{nE[\mathbf{1}_{B^{\prime}}]}{\ell_{n}}.$
(72)

Now if $|\tilde{V}-E[\tilde{V}]|<n{\epsilon^{\prime}}/(2\ell_{n})$ and
$\left|\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-\tilde{V}\right|\leq|K-n/\ell_{n}|<n{\epsilon^{\prime}}/(2\ell_{n})$,
by triangle inequality
$\left|\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-nE[\mathbf{1}_{B^{\prime}}]/\ell_{n}\right|\leq
n{\epsilon^{\prime}}/(2\ell_{n})$. Therefore,

$\displaystyle\text{Pr}\left(\left|\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-\frac{nE[\mathbf{1}_{B^{\prime}}]}{\ell_{n}}\right|\geq
n{\epsilon^{\prime}}/\ell_{n}\right)\leq\text{Pr}\left(|K-n/\ell_{n}|>n{\epsilon^{\prime}}/(2\ell_{n})\right)$
$\displaystyle+\text{Pr}\left(\left|\sum_{i=1}^{K}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
1}\\}}-\frac{nE[\mathbf{1}_{B^{\prime}}]}{\ell_{n}}\right|\geq
n{\epsilon^{\prime}}/(2\ell_{n})\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2e^{-\frac{{\epsilon^{\prime}}^{2}\ell_{n}}{(2+{\epsilon^{\prime}})}n}+2e^{-n{\epsilon^{\prime}}^{2}/(2\ell_{n})}\to
0,$ (73)

uas $n\to\infty$. $(a)$ follows from (D) and Hoeffding’s inequality.

##  Appendix D Proof of Lemma 3

See 3 We first prove a concentration bound for $K$ and utilize that to prove
the lemma.

$\displaystyle\text{Pr}(|K-n/\ell_{n}|>\delta
n/\ell_{n})=\text{Pr}(K>(1+\delta)n/\ell_{n})+\text{Pr}(K<(1-\delta)n/\ell_{n})$
$\displaystyle\leq\text{Pr}\left(\sum_{i=1}^{{(1+\delta)n/\ell_{n}}}N_{i}\leq
n\right)+\text{Pr}\left(\sum_{i=1}^{{(1-\delta)n/\ell_{n}}}N_{i}\geq n\right)$
$\displaystyle=\text{Pr}\left(\sum_{i=1}^{{(1+\delta)n/\ell_{n}}}(N_{i}-E[N_{i}])\leq-\delta
n\right)+\text{Pr}\left(\sum_{i=1}^{{(1-\delta)n/\ell_{n}}}(N_{i}-E[N_{i}])\geq\delta
n\right)$
$\displaystyle=\text{Pr}\left(\frac{\ell_{n}}{(1+\delta)n}\sum_{i=1}^{(1+\delta)n/\ell_{n}}(N_{i}-E[N_{i}])\leq-\frac{\delta\ell_{n}}{1+\delta}\right)$
$\displaystyle+\text{Pr}\left(\frac{\ell_{n}}{(1-\delta)n}\sum_{i=1}^{(1-\delta)n/\ell_{n}}(N_{i}-E[N_{i}])\geq\frac{\delta\ell_{n}}{1-\delta}\right)$
$\displaystyle\leq
e^{-\frac{2\delta^{2}\ell_{n}^{2}}{(1+\delta)^{2}}(1+\delta)n/\ell_{n}}+e^{-\frac{2\delta^{2}\ell_{n}^{2}}{(1-\delta)^{2}}(1-\delta)n/\ell_{n}}$
$\displaystyle\leq 2e^{-\frac{2\delta^{2}\ell_{n}}{(1+\delta)}n}$ (74)

Define $V_{i}\triangleq\mathbf{1}_{\left\\{N_{i}=\lceil
r\log{n}\rceil,B\right\\}}$ and $\tilde{V}=\sum_{i=1}^{n/\ell_{n}}V_{i}$. It
is clear that $||\mathcal{Y}_{r}|-\tilde{V}|\leq|K-n/\ell_{n}|$. Moreover
$E[\tilde{V}]=\frac{n}{\ell_{n}}q_{r,n}e_{r,n}$. Therefore

Pr
$\displaystyle\left(\middle||\mathcal{Y}_{r}|-nq_{r,n}e_{r,n}/\ell_{n}\middle|\geq\epsilon_{r,n}n/\ell_{n}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\text{Pr}$
$\displaystyle\left(\middle|\tilde{Z}-nq_{r,n}e_{r,n}/\ell_{n}\middle|\geq
n\epsilon_{r,n}/(2\ell_{n})\right)+\text{Pr}\left(|K-n/\ell_{n}|\geq
n\epsilon_{r,n}/(2\ell_{n})\right)$ $\displaystyle\leq
2e^{-n\epsilon_{r,n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{r,n}^{2}\ell_{n}}{(1+2\epsilon_{r,n})}n},$
(75)

where (a) is due to triangle inequality. We then consequently use Hoeffding’s
Inequality and (D).

##  Appendix E Proof of Lemma 4

See 4 Consider Lemma 6. Since $\gamma$ is a value we can choose, choose it to
be $(J/L)$. Note that

$\displaystyle F_{d}\\{\gamma\log{n}\\}$
$\displaystyle=\frac{E\left[N_{1}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
g}\\}}\right]}{\ell_{n}}.$

Now define the event

$\displaystyle\mathcal{J}\triangleq\left\\{{\rm
F}_{d}\\{\gamma\log{n}\\}>E\left[N_{1}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
g}\\}}\middle/\ell_{n}\right]+\delta\right\\}.$

From the general version of Lemma 1, $\Pr(\mathcal{J})\to 0$ as $n\to\infty$.
Therefore we can write

$\displaystyle H(\mathcal{Y}_{\geq J})$ $\displaystyle\leq H(\mathcal{Y}_{\geq
J}|\overline{\mathcal{J}})+H(\mathcal{Y}_{\geq
J}|\mathcal{J})\Pr(\mathcal{J})+1$ $\displaystyle\leq H(\mathcal{Y}_{\geq
J}|\overline{\mathcal{J}})+2n\Pr(\mathcal{J})+1$ $\displaystyle\leq
2n\left(E\left[N_{1}\mathbf{1}_{\\{\vec{X}_{i}\in\mathcal{Y}_{\geq
g}\\}}\middle]\right/\ell_{n}+\delta\right)+o(n)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2n\left(E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq(J/L)\log{n}\\}}\middle/\ell_{n}\right]+\delta\right)+o(n)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2n\left(\sqrt{E[N_{1}^{2}]\Pr(N_{1}\geq(J/L)\log{n})}/\ell_{n}+\delta\right)+o(n)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2n\left(\sqrt{E[N_{1}^{2}]\ell_{n}L}/(\ell_{n}\sqrt{J\log{n}})\right)+\delta)+o(n)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}2n\left(S\sqrt{L/J}+\delta\right)+o(n),$

for some finite $S$. $(a)$ is true because we include the deleted fragments.
$(b)$ is due to Cauchy-Schwarz inequality. $(c)$ is due to Markov Inequality
and $(d)$ is due to $E[N_{1}/\log{n}]$ and $E[(N_{1}/\log{n})^{2}]$ being
finite and bounded. Therefore this implies

$\displaystyle\lim_{n\to\infty}\frac{H(\mathcal{Y}_{\geq J})}{n}\leq
2\left(S\sqrt{L/J}+\delta\right).$

##  Appendix F Proof of Lemma 5

See 5 This lemma can proved by careful splitting of terms and careful
manipulation of upper bounds. First we have

$\displaystyle\lim_{n\to\infty}A(n)=\lim_{n\to\infty}\sum_{k=1}^{J}\left(\frac{1}{n}+2\text{Pr}(\mathcal{E}_{k,n})+\frac{M_{k}}{n}(\log{e}+P)\right)+$
$\displaystyle\lim_{n\to\infty}\epsilon_{n}\sum_{k=1}^{J}\left(\left(\frac{k}{L}-1\right)^{+}+\frac{(\epsilon_{n}+1)\log{(\ell_{n}\log{n})\log{(n)}}}{\ell_{n}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\lim_{n\to\infty}\sum_{k=1}^{J}\left(\frac{1}{n}+2e^{-n\epsilon^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon^{2}\ell_{n}}{(1+2\epsilon)}n}\right)$
$\displaystyle+\lim_{n\to\infty}\sum_{k=1}^{J}\frac{M_{k}}{n}(\log{e}+P)$
$\displaystyle=J\lim_{n\to\infty}\left(\frac{1}{n}+2e^{-n\epsilon^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon^{2}\ell_{n}}{(1+2\epsilon)}n}\right)$
$\displaystyle+\lim_{n\to\infty}\sum_{k=1}^{\infty}\frac{M_{k}}{n}(\log{e}+P)=\lim_{n\to\infty}\sum_{k=1}^{\infty}\frac{M_{k}}{n}(\log{e}+P),$
(76)

where (a) is due to lemma 3 and the fact that we set $\epsilon_{n}=1/\log{n}$.
. We proceed as

$\displaystyle\sum_{k=1}^{J}\frac{M_{k}}{n}(\log{e}+P)=\frac{1}{\ell_{n}}\log{e}\sum_{k=1}^{J}(q_{k,n}e_{k,n}+\epsilon_{n})+\sum_{k=1}^{J}\frac{M_{k}}{n}P$
$\displaystyle\leq\frac{\log{e}}{\ell_{n}}\left(1+J\epsilon_{n}\right)+\sum_{k=1}^{L-1}\frac{M_{k}}{n}P+\sum_{k=L}^{J}\frac{M_{k}}{n}P$
$\displaystyle\leq
o(1)+\sum_{k=1}^{L-1}\frac{M_{k}}{n}\log\left(1+\frac{2n^{k/L}-1}{M_{k}}\right)$
$\displaystyle+\sum_{k=L}^{J}\frac{M_{k}}{n}\log\left(2+\frac{M_{k}-1}{n^{k/L}}\right)$
(77)

since $\min(a,b)\leq a,b$. Let’s now look at the second term

$\displaystyle\sum_{k=1}^{L-1}\frac{M_{k}}{n}\log\left(1+\frac{2n^{k/L}-1}{M_{k}}\right)$
$\displaystyle\leq\sum_{k=1}^{L-1}\frac{M_{k}}{n}\frac{2n^{k/L}}{M_{k}}$
$\displaystyle=2\sum_{k=1}^{L-1}n^{k/L-1}$ $\displaystyle\to 0,$ (78)

as $n\to\infty$. For a finite $L$, this is a finite summation. Since for
$k<L$, $n^{k/L-1}\to 0$ as $n\to\infty$, the above summation also goes to
zero. Now look at the third term

$\displaystyle\sum_{k=L}^{J}\frac{M}{n}\log\left(2+\frac{M_{k}-1}{n^{k/L}}\right)\leq\frac{1}{n}\sum_{k=L}^{J}M_{k}(1+(M_{k}-1)n^{-k/L})$
$\displaystyle\leq\frac{1}{\ell_{n}}\sum_{k=L}^{J}(q_{k,n}e_{k,n}+\epsilon_{n})+\frac{1}{\ell_{n}^{2}}\sum_{k=L}^{J}n^{1-k/L}(q_{k,n}e_{k,n}+\epsilon_{n})^{2}$
$\displaystyle\leq\frac{1}{\ell_{n}}E[\mathbf{1}_{B^{\prime}}]+\frac{1}{\ell_{n}^{2}}\sum_{k=L}^{\infty}n^{1-k/L}+3J\epsilon_{n}/\ell_{n}+\epsilon_{n}^{2}/\ell_{n}$
$\displaystyle\leq\frac{1}{\ell_{n}}+\frac{1}{(1-n^{-1/L})\ell_{n}^{2}}+o(1),$
(79)

which $\to 0$ as $n\to\infty$. Equations (F), (F) and (F) imply that $A(n)\to
0$ as $n\to\infty$.

##  Appendix G Proof of Lemma 9

See 9

Consider the noisy shuffling channel from [11]. Let $\vec{X}_{r}$ be the input
binary string, which consists of $M_{r}$ strings of length (exactly)
$r\log{n}$ in order (thus, this can also be viewed as a single string of
length $M_{r}(r\log{n})$). Let $\vec{Y}_{r}$ be the output binary string. The
first step towards proving Lemma 9, is to establish a relationship between the
entropies $H(\vec{Y}_{r})$ and $H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r})$, where
$S^{M_{r}}$ is a shuffling vector, formally defined in the next paragraph.

We define

$\vec{X}_{r}:=\left[\tilde{X}_{1}^{r\log{n}},\tilde{X}_{2}^{r\log{n}},\dots,\tilde{X}_{M_{r}}^{r\log{n}}\right],$

where $\tilde{X}_{i}^{r\log{n}}$ is the $i$th string of length $r\log{n}$. Let

$\vec{Z}_{r}=\left[\tilde{Z}_{1}^{r\log{n}},\tilde{Z}_{2}^{r\log{n}},\dots,\tilde{Z}_{M_{r}}^{r\log{n}}\right],$

be a random error pattern created by passing $\vec{X}_{r}$ through a BSC($p$).
Further, given $M_{r}$, define $S^{M_{r}}\in[1:M_{r}]^{M_{r}},$ as a shuffle
vector, uniformly distributed on all possible permutations of the indices
$[1:M_{r}]$. Now, similar to $\vec{X}_{r}$, we can define

$\vec{Y}_{r}:=\left[\tilde{Y}_{1}^{r\log{n}},\tilde{Y}_{2}^{r\log{n}},\dots,\tilde{Y}_{M_{r}}^{r\log{n}}\right],$

where $\tilde{Y}_{i}^{r\log{n}}:=X_{S(i)}^{r\log{n}}\oplus
Z_{S(i)}^{r\log{n}}.$ The following lemma adapted from [11] is central to
proving Lemma 9.

######  Lemma 13.

Let $\vec{Y}_{r}$ be obtained by passing string $\vec{X}_{r}$ through the
noisy shuffling channel. Let $S^{M_{r}}\in\\{1:M_{r}\\}^{M_{r}}$ be the
uniform shuffling vector, encoding the random shuffle induced by this channel.
For this channel, if

$\displaystyle 1-H(2p)-\frac{2}{r}\geq 0,$ (80)

then

$\displaystyle H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r}))\leq
M_{r}(\lceil r\log{n}\rceil)+M_{r}^{1-\delta^{\prime}}\log{M_{r}},$ (81)

for some $\delta^{\prime}>0$. Otherwise,

$\displaystyle H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r}))\leq
M_{r}(\lceil r\log{n}\rceil)+M_{r}\log{M_{r}}.$ (82)

The proof of the above lemma follows from very similar arguments as [11].
Equation (81) is similar to Lemma 1 in [11], with a key difference. Lemma 1 in
[11] uses the following upper bound:

$\displaystyle H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r}))\leq
M_{r}(\lceil r\log{n}\rceil)+o(M_{r}r\log{n}).$ (83)

During the proof of Lemma 1 in [11], a loose upper bound is used to bound the
term $M_{r}^{1-\delta}\log{M_{r}}\leq M_{r}r\log{n}$, where $\delta>0$.
Instead, we retain $M_{r}^{1-\delta}\log{M_{r}}$ in Lemma 13.

Equation (82) can be shown as follows:

$\displaystyle
H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r}))\stackrel{{\scriptstyle(a)}}{{\leq}}H(\vec{Y}_{r})+H(S^{M_{r}})\stackrel{{\scriptstyle(b)}}{{\leq}}M_{r}(\lceil
r\log{n}\rceil)+M_{r}\log{M_{r}},$ (84)

where $(a)$ follows because conditioning reduces entropy and $(b)$ is because
the uniform distribution maximizes entropy.

To utilize this lemma, define $\mathcal{Y}_{r}$ as an unordered multiset which
contains $M_{r}$ pieces of size $r\log{n}$. We can view the output of the
noisy shuffling channel as either $\mathcal{Y}_{r}$ or $\vec{Y}_{r}$, since
the shuffling channel encodes a uniformly random shuffling on the input
strings. Further we assume $M_{r}$ to be a random variable, instead of a fixed
quantity. Precisely $(M_{r}:r\in A)$ are random variables that have a joint
conditional distribution of $(|\mathcal{Y}_{r}|:r\in A)$ conditioned on
$\bar{\mathcal{E}}_{k,n}$. We assume that the random variable $M_{r}$ is
implicitly conditioned on event $\bar{\mathcal{E}}_{k,n}$ for the rest of this
proof. We can now say that

$I(\vec{X}_{r};\mathcal{Y}_{r})=I(\vec{X}_{r};\vec{Y}_{r}).$

The left hand side of the above equation can be further expanded as

$\displaystyle
I(\vec{X}_{r};\mathcal{Y}_{r})=H(\mathcal{Y}_{r})-H(\mathcal{Y}_{r}|\vec{X}_{r})=H(\mathcal{Y}_{r})+H(\vec{Z}_{r}|\vec{X}_{r},\mathcal{Y}_{r})-H(\vec{Z}_{r})-H(\mathcal{Y}_{r}|\vec{X}_{r},\vec{Z}_{r})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}H(\mathcal{Y}_{r})+H(\vec{Z}_{r}|\vec{X}_{r},\mathcal{Y}_{r})-H(\vec{Z}_{r}),$
(85)

where $(a)$ follows, since given $(\vec{X}_{r},\vec{Z}_{r})$, we can calculate
$\mathcal{Y}_{r}$. Lemma 13 applies when we condition each entropy term in the
bounds (81) and (82) as $M_{r}=m_{r}$ for any fixed number $m_{r}$. Now
following the steps in equations (7) and (8) in [11] we can argue (for a fixed
length channel with output containing pieces of size $r\log{n}$ and
cardinality $M_{r}$),

$\displaystyle I(\vec{X}_{r};\vec{Y}_{r})$
$\displaystyle=H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r})-H(S^{M_{r}},\vec{Z}_{r},\vec{Y}_{r}|\vec{X}_{r})$
$\displaystyle=H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r})-H(S^{M_{r}})-H(\vec{Z}_{r}).$
(86)

Therefore from (G) and (G), we conclude that

$\displaystyle H(\mathcal{Y}_{r})$
$\displaystyle+H(\vec{Z}_{r}|\vec{X}_{r},\mathcal{Y}_{r})=H(\vec{Y}_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r})-H(S^{M_{r}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}H(\vec{Y}_{r},M_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},M_{r})-H(S^{M_{r}}|M_{r})$
$\displaystyle\leq
H(M_{r})+H(\vec{Y}_{r}|M_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},M_{r})-H(S^{M_{r}}|M_{r})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\log{(n+1)}+H(\vec{Y}_{r}|M_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},M_{r})-H(S^{M_{r}}|M_{r}),$
(87)

where $M_{r}$ is viewed as a random variable. Step $(a)$ follows because
$M_{r}$ is a deterministic function of $\vec{Y}_{r}$ and conditioning reduces
entropy, and $(b)$ follows because there are at most $n+1$ values that $M_{r}$
can take. To see this note that $M_{r}$ is defined as the number of elements
in $|\mathcal{Y}_{r}|$, and this cannot exceed the length of the length of the
input string $n$.

Now to prove Lemma 9, define
$\mathcal{A}:=\mathbb{Z}^{+}\cap\left[\frac{k-1}{L}\log{n},\frac{k}{L}\log{n}\right)$.
We can use Lemma 13, when conditioned on $M_{r}=m_{r}$, where $m_{r}$ is a
fixed number. The following upper bound then follows:

$\displaystyle
H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{\mathcal{Z}}_{k}|\vec{\mathcal{X}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})\leq\sum_{r:r\log{n}\in\mathcal{A}}\left(H(\mathcal{Y}_{r}|\bar{\mathcal{E}}_{k,n})+H(\vec{Z}_{r}|\vec{X}_{r},\mathcal{Y}_{r},\bar{\mathcal{E}}_{k,n})\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{r:r\log{n}\in\mathcal{A}}\left(\log{(n+1)}+H(\vec{Y}_{r}|M_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},M_{r})-H(S^{M_{r}}|M_{r})\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+\sum_{r:r\log{n}\in\mathcal{A}}\sum_{m_{r}\in[0:n]}\Pr(m_{r})\left(H(\vec{Y}_{r}|m_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},m_{r})-H(S^{M_{r}}|m_{r})\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{\log^{2}{(n+1)}}{L}+\sum_{r:r\log{n}\in\mathcal{A}}\sum_{m_{r}\in[0:n]}\Pr(m_{r})\left(H(\vec{Y}_{r}|m_{r})+H(S^{M_{r}}|\vec{X}_{r},\vec{Y}_{r},m_{r})-\log{(m_{r}!)}\right),$
(88)

where $(a)$ is due to (G) $(b)$ is because $|\mathcal{A}|\leq\log{n}/L$ and
$(c)$ is because $S^{M_{r}}$ given $\\{M_{r}=m_{r}\\}$ is a uniform shuffling
vector, which picks one of exactly $m_{r}!$ values, equiprobably. Note that we
use the shorthand $m_{r}$ to refer to the event $\\{M_{r}=m_{r}\\}$. Recall
that $M_{k}:=\left(\epsilon_{n}+q_{k,n}\right)\frac{n}{\ell_{n}}$, which is a
constant.

Firstly, when $\frac{k-1}{L}>\frac{2}{1-H(2p)}$ we can upper bound (G) as

$\displaystyle
H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{Z}_{k}|\vec{X}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+\sum_{r:r\log{n}\in\mathcal{A}}E\left(M_{r}(\lceil
r\log{n}\rceil)+M_{r}^{1-\delta^{\prime}}\log{M_{r}}-\log{(M_{r}!)}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}]\frac{k}{L}\log{n}+\sum_{r:r\log{n}\in\mathcal{A}}M_{r}^{1-\delta^{\prime}}\log{M_{k}}-\sum_{r:r\log{n}\in\mathcal{A}}\log{(M_{r}!)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}+o(M_{k}\log{M_{k}})-\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}\log(M_{r})]$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}+o(M_{k}\log{M_{k}})-\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}]\log(E[M_{r}])$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}+o(M_{k}\log{M_{k}})-\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right),$
(89)

where $(a)$ is due to the first part of Lemma 13, $(b)$ is because of
linearity of expectation followed by an upper bound on the sum of
$m_{r}\in\mathcal{A}$, upper bounding each term $\log{M_{r}}$ with
$\log{M_{k}}$ and Stirling’s approximation, and $(c)$ is due to Jensen’s
inequality for the convex function $x^{1-\delta^{\prime}}$. To obtain $(d)$,
we upper bound the last term in (G) as

$\displaystyle-\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}]\log(E[M_{r}])\stackrel{{\scriptstyle(i)}}{{\leq}}-\sum_{r:r\log{n}\in\mathcal{A}}(E[M_{r}])\times\log{\left(\frac{\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}]}{\sum_{r:r\log{n}\in\mathcal{A}}1}\right)}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}-\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)+\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log{\left(\frac{\log{n}}{L}\right)}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{=}}-\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)+o(M_{k}\log{M_{k}}),$
(90)

where $(i)$ is due to log-sum inequality, $(ii)$ is because
$\sum_{r:r\log{n}\in\mathcal{A}}E[M_{r}]=E[|\mathcal{Y}_{k}|]\geq\left(M_{k}-2n\epsilon_{n}/\ell_{n}\right)$
(see (55)) and $(iii)$ is because from the definition of
$M_{k}:=\left(\epsilon_{n}+q_{k,n}\right)\frac{n}{\ell_{n}}$ one can see that
$M_{k}\log n=o(M_{k}\log M_{k})$.

On the contrary if $\frac{k-1}{L}\leq\frac{2}{1-H(2p)}$ we opt for the looser
upper bound to show that

$\displaystyle
H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{Z}_{k}|\vec{X}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\log^{2}{(n+1)}}{L}+\sum_{r:r\log{n}\in\mathcal{A}}E\left(M_{r}(\lceil
r\log{n}\rceil)+M_{r}\log{M_{r}}-\log{(M_{r}!)}\right)$
$\displaystyle\leq\frac{\log^{2}{(n+1)}}{L}+M_{k}\frac{k}{L}\log{n}+o(M_{k}\log{M_{k}})$
(91)

This proves the theorem.

##  Appendix H Proof of Lemma 10

See 10 We apply Lemma 9, followed by careful analysis to prove Lemma 10. Steps
are similar to (II-D), (II-D) and (33), with some minor changes. Precisely

$\displaystyle\sum_{k=L+1}^{J}\left(H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+H(\vec{{\mathcal{Z}}}_{k}|\vec{{\mathcal{X}}}_{k},\mathcal{Y}_{k},\bar{\mathcal{E}}_{k,n})\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k=L+1}^{\frac{2L}{1-H(2p)}}\left(M_{k}\frac{k}{L}\log{n}\right)+\sum_{k=\frac{2L}{1-H(2p)}+1}^{J}\left(M_{k}\frac{k}{L}\log{n}-\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)\log{\left(M_{k}-\frac{2n\epsilon_{n}}{\ell_{n}}\right)}\right)$
$\displaystyle+\sum_{k=L+1}^{J}o(M_{k}\log{M_{k}})+\frac{J\log^{2}{(n+1)}}{L}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{k=L+1}^{\frac{2L}{1-H(2p)}}\left(\frac{n}{\ell_{n}}(\epsilon_{n}+q_{k,n})\right)\frac{k}{L}\log{n}$
$\displaystyle+\sum_{k=\frac{2L}{1-H(2p)}+1}^{J}\left(\left(\frac{n}{\ell_{n}}(\epsilon_{n}+q_{k,n})\right)+\frac{k}{L}\log{n}\left(\frac{n}{\ell_{n}}(-\epsilon_{n}+q_{k,n})\right)\log{\left(\frac{n}{\ell_{n}}(-\epsilon_{n}+q_{k,n})\right)}\right)$
$\displaystyle+\sum_{k=L+1}^{J}o(M_{k}\log{M_{k}})+\frac{J\log^{2}{(n+1)}}{L}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{n}{\ell_{n}}\sum_{k=L+1}^{\infty}q_{k,n}\frac{k}{L}\log{n}-\frac{n\log{n}}{\ell_{n}}\sum_{k=\frac{2L}{1-H(2p)}}^{\infty}q_{k,n}+o(n)$
$\displaystyle=n\left(\frac{E\left[N_{1}\mathbf{1}_{\\{N_{1}\geq\log{n}\\}}\right]}{\ell_{n}}-\frac{\log{n}}{\ell_{n}}E\left[\mathbf{1}_{\left\\{N_{1}\geq\frac{2}{1-2H(p)}\log{n}\right\\}}\right]\right)+o(n),$
(92)

where $(a)$ is due to Lemma 9, $(b)$ is from the definition of
$M_{k}=\frac{n}{\ell_{n}}(q_{k,n}+\epsilon_{n})$, $(c)$ is by collecting the
ancillary terms and grouping them. These terms can be shown to be $o(n)$ using
arguments similar to the ones used in (F).

##  Appendix I Proof of Lemma 12

See 12 This lemma again involves careful manipulation of upper bounds, to
arrive at the result.

$\displaystyle\frac{1}{n}\sum_{k=1}^{L}H(\mathcal{Y}_{k}|\bar{\mathcal{E}}_{k,n})+2\sum_{k=1}^{J}\left(2\Pr(\mathcal{E}_{k,n})+\frac{1}{n}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k=1}^{L}\left(\frac{M_{k}\log{n}}{n}\left(\frac{k}{L}-1\right)^{+}+\frac{M_{k}}{n}\left(\log{e}+P\right)+\frac{M_{k}\log{n}\log{(\ell_{n}\log{n})}}{n}\right)$
$\displaystyle+2\sum_{k=1}^{J}\left(2\Pr(\mathcal{E}_{k,n})+\frac{1}{n}\right)\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{k=1}^{L}\left(\frac{M_{k}}{n}\left(\log{e}+P\right)+\frac{M_{k}\log{n}\log{(\ell_{n}\log{n})}}{n}\right)$
$\displaystyle+2J\left(\frac{1}{n}+2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}\right)\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{k=1}^{L-1}\frac{M_{k}}{n}\left(\log{e}+\log{\left(1+\frac{2n^{k/L}-1}{M_{k}}\right)}\right)$
$\displaystyle+\frac{M_{L}}{n}\log{\left(e\left(1+\frac{2n-1}{M_{L}}\right)\right)}+2J\left(\frac{1}{n}+2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}\right)$
$\displaystyle\leq\sum_{k=1}^{L-1}\frac{M_{k}}{n}\left(\log{e}+\frac{2n^{k/L}}{M_{k}}\right)+\frac{\log\left(e\left(1+\frac{\ell_{n}}{\epsilon_{n}}\right)\right)}{\ell_{n}}+2J\left(\frac{1}{n}+2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}\right)$
$\displaystyle\leq
2\sum_{k=1}^{L-1}n^{k/L-1}+L(1+\epsilon_{n})\frac{\log{e}}{\ell_{n}}+O\left(\frac{\log\left(1+\log^{2}{n}\right)}{\log{n}}\right)$
$\displaystyle+2J\left(\frac{1}{n}+2e^{-n\epsilon_{n}^{2}/(2\ell_{n})}+2e^{-\frac{8\epsilon_{n}^{2}\ell_{n}}{(1+2\epsilon_{n})}n}\right)\to
0,$ (93)

as $n\to\infty$, where recall that

$\displaystyle
P:=\min\left(\log\middle(2+\frac{M_{k}-1}{n^{k/L}}\middle),\log\middle(1+\frac{2n^{k/L}-1}{M_{k}}\middle)\right).$
(94)