# Information Rates Over Multi-View Channels

V. Arvind Rameshwar and Nir Weinberger V. A. Rameshwar is with India Urban
Data Exchange, SID, Indian Institute of Science, Bengaluru 560094, email:
<EMAIL_ADDRESS>N. Weinberger is with the Department of Electrical
and Computer Engineering, Technion, Haifa 3200003, Israel, email:
<EMAIL_ADDRESS>. This paper was accepted in part to the 2024 IEEE
International Symposium on Information Theory. The research of N. W. was
supported by the Israel Science Foundation (ISF), grant no. 1782/22.

###### Abstract

We investigate the fundamental limits of reliable communication over multi-
view channels, in which the channel output is comprised of a large number of
independent noisy views of a transmitted symbol. We consider first the setting
of multi-view discrete memoryless channels and then extend our results to
general multi-view channels (using multi-letter formulas). We argue that the
channel capacity and dispersion of such multi-view channels converge
exponentially fast in the number of views to the entropy and varentropy of the
input distribution, respectively. We identify the exact rate of convergence as
the smallest Chernoff information between two conditional distributions of the
output, conditioned on unequal inputs. For the special case of the deletion
channel, we compute upper bounds on this Chernoff information. Finally, we
present a new channel model we term the Poisson approximation channel — of
possible independent interest — whose capacity closely approximates the
capacity of the multi-view binary symmetric channel for any fixed number of
views.

##  I Introduction

Consider a communication setting, in which the decoder receives multiple,
potentially noisy, views of a single transmitted sequence, which is sent via
independent transmissions through a stochastic noise channel. Clearly,
multiple noisy views (or multiple draws) of a transmitted sequence can only
improve the error probabilities of decoding, as compared to decoding a single
received sequence. Viewed differently, it is also clear that the Shannon
capacity of the _multi-view_ channel, as described above, is at least as large
as the capacity of the standard single-view channel.

In this paper, we consider first the setting where the noisy channel is a
discrete memoryless channel (DMC) and then extend our results to general
multi-letter channels. Multi-view DMCs were first studied in the classic work
by Levenshtein [1] on sequence reconstruction. Among several other results,
[1] presented bounds on the probability of error under ML decoding and
characterized the number of noisy views required to guarantee recovery of the
transmitted sequence, with _decaying error probability_. These results are
determined by the minimum Chernoff information between conditional
distributions of outputs of the DMC, conditioned on unequal inputs.
Levenshtein’s result on the number of noisy views required for reconstruction,
however, depends crucially on the assumption that the error probability decays
with the blocklength, and leaves open the question of characterizing the rates
achievable over DMCs with fixed error probability, using finitely many channel
uses. Furthermore, the proof strategy in [1] resists extension to channels,
such as those that model synchronization errors, wherein the lengths of the
input and output sequences could be different.

In this work, we characterize exactly the rate of convergence of the
information rate and the channel dispersion of general multi-view channels,
under arbitrary input distributions, to the input entropy and the varentropy,
respectively, when the number of views is large. As our main result, we show
that the rates of (exponential) convergence are again determined by the
minimum Chernoff information between conditional distributions, as above. This
result does not assume any additional structure on the channel such as
symmetry, or binary alphabets (though require the input and output alphabet to
be finite)

While our result on the convergence of information rate to the input entropy
can be derived from the results in [1] (and [2, Thm. 5])111We show, moreover,
that for binary-input memoryless symmetric (BIMS) channels with a uniform
input distribution, it is possible to derive the convergence of the
information rate (which, in this case, is the capacity of the channel) to the
input entropy, using a simple argument from binary hypothesis testing., we
present new tools for deriving such a result, which also helps us obtain the
rate of convergence of the channel dispersion to the input varentropy. An
important consequence of our results for DMCs (under some regularity
conditions) is our characterization of the largest rates achievable over
finitely many channel uses, with any _fixed error probability_ , using results
from finite-blocklength information theory, thereby resolving a natural
question that stems from Levenshtein’s work [1]. We then show that our results
also hold for multi-letter channels with potentially different lengths of
input and output sequences. Furthermore, for the special case of the (multi-
letter) deletion channel, which is a popular synchronization error channel
[3], we compute explicit upper bounds on the above Chernoff information, and
discuss some interesting consequences.

Our interest in this setting is strongly motivated by the recently proposed
model for DNA-based storage systems (see, e.g., [4, 5, 6, 7] and [8, 9] for
coding schemes). In a nutshell, in this channel, information is encoded into a
large multiset of short sequences from a quarternary alphabet, called
molecules (or strands). These sequences are then stored in a pool without
order, and reading the information is performed by sampling molecules from the
pool. After being inserted into the pool, the molecules are “amplified” by a
process called Polymerase Chain Reaction (PCR), to produce several copies of
each molecule. Therefore the sampling process during reading can be accurately
modelled by sampling with replacement. Each sampled molecule is then sequenced
to read the written symbols it consist of. This sequencing operation is noisy,
and the noise is independent from one molecule read to the other. Furthermore,
in some cases, this noisy operation is well modelled by a DMC, which tends to
be asymmetric [10].

Evidently, in this DNA-storage model, each molecule is possibly read many
times, and so the multi-view mutual information between the molecule sequence
and its multiple output reads plays a pivotal role in determining the capacity
of this storage system. Indeed, it was shown in [7, Thm. 5], that the capacity
is composed of a weighted average of such mutual information terms, which
accounts for the multiple input molecules, and the possibility that each of
them is sampled a different number of times.

The total number of sampled molecules in the reading operation is a design
parameter, say the number of moelcueles sampled may be a constant factor of
the total number of molecules, say $d_{0}$. In this case, it is expected that
each input molecule is also sampled about $d_{0}$ times, and the mutual
information term between the input molecule sequences and its multiple output
reads falls into the setting considered in this paper. Moreover, as said, each
molecule on its own is rather short, and so finite-blocklength bounds appears
to be relevant. Specifically, given a molecule length, and $d_{0}$, one may
determine using our results when the maximal multi-view rate of this molecule
is approached, for a given error probability. A detailed investigation of this
setting is beyond the scope of this paper, but of interest for future work.

Previous works considered the mutual information for a fixed number of views.
In this non-asymptotic setting, the capacity of a multi-view binary symmetric
channel (BSC) was identified and an explicit expression was provided in [11].
More generally, bounds on the capacities of multi-view DMCs were derived in
the literature on “information combining” (see [12, 13] and the references
therein). Also related is the well-studied problem on trace reconstruction
[14, 15, 16], wherein an input string is passed independently through a
deletion channel and the goal is to find the number of resultant outputs
required for reconstruction with high-probability. By contrast, in this work
we focus on the scaling to mutual information and dispersion in the asymptotic
regime of large number of views.

As an additional contribution, we also explore the non-asymptotic capacity of
the so-called _Poisson approximation channel_ , which we believe is of
possible independent interest. We show that the capacity of this channel is a
tight lower bound on the capacity of the multi-view BSC. Such a technique also
allows us to obtain simple bounds on the non-asymptotic capacities of general
binary-input memoryless symmetric (BIMS) channels.

The rest of the paper is organized as follows: Section II sets down the
notation; Section III presents our main results for DMCs; Section IV provides
a proof sketch of the rate of convergence of the information rate and channel
dispersion of a DMC to their respective limits. Section V then extends our
results to general multi-letter channels and presents upper bounds on Chernoff
information discussed above for the deletion channel. Section VI contains a
proof that the capacity of the Poisson approximation channel is a tight lower
bound on the capacity of the multi-view BSC. Section VII then provides full
proofs of our main convergence results. Section VIII concludes the paper and
proposes problems for further research.

##  II Notation Conventions

All logarithms are assumed to be natural logarithms. Random variables are
denoted by capital letters, e.g., $X,Y$, and small letters, e.g., $x,y$,
denote their instantiations. Sets are denoted by calligraphic letters, e.g.,
$\mathcal{X},\mathcal{Y}$. The set of positive natural numbers
$\\{1,2,\ldots\\}$ is denoted as $\mathbb{N}$. Notation such as $P(x),P(y|x)$
are used to denote the probabilities $P_{X}(x),P_{Y|X}(y|x)$, when it is clear
which random variables are being referred to. For $\alpha\in[0,1]$ and $n\geq
1$, Ber$(\alpha)$ and Bin$(n,\alpha)$, denote, respectively, the Bernoulli
distribution, supported on $\\{0,1\\}$, with
$\Pr_{X\sim\text{Ber}(\alpha)}[X=1]=\alpha$, and the Binomial distribution,
supported on $\\{0,1,\ldots,n\\}$, with

$\Pr_{X\sim\text{Bin}(n,\alpha)}[X=k]=\binom{n}{k}\alpha^{k}(1-\alpha)^{n-k},$
(1)

for $k\in\\{0,1,\ldots,n\\}$.

The entropy of $X\sim P_{X}$ is denoted by
$\mathsf{H}(X)=\mathsf{H}(P_{X}):=\mathbb{E}[-\log P_{X}(X)]$ and its
varentropy is denoted by

$\mathsf{V}(X):=\mathbb{E}\left[\left(-\log{P_{X}(X)}-\mathsf{H}(X)\right)^{2}\right].$
(2)

Both only depend only on the distribution of $X$. For $\gamma\in[0,1]$, the
binary entropy function is denoted by
$h_{b}(\gamma):=-\gamma\log\gamma-(1-\gamma)\log(1-\gamma)$. The Chernoff
information $\mathsf{C}(P,Q)$ between two distributions $P$ and $Q$ defined on
the same alphabet $\mathcal{X}$ is given by (see [17, Ch. 11])

$\mathsf{C}(P,Q):=-\min_{\lambda\in[0,1]}\log\left(\sum_{x\in\mathcal{X}}P(x)^{1-\lambda}Q(x)^{\lambda}\right).$
(3)

Furthermore, the standard Kullback-Leibler (KL) divergence between two
distributions $P,Q$ on the same alphabet $\mathcal{X}$ is given by

$D(P||Q):=\mathbb{E}_{X\sim P}\left[\log\frac{P(X)}{Q(X)}\right],$ (4)

where we take $0\log\frac{0}{z}=0$ and we set $D(P||Q)=\infty$ if there exists
$x\in\mathcal{X}$ such that $Q(x)=0$ but $P(x)>0$.

The the length-$n$ vector $(a_{1},\ldots,a_{n})$ is denoted by $a^{n}$, and
the Hamming weight, i.e., the number of ones in $a^{n}$, is denoted by
$w(a^{n})$. The indicator that $x$ equals $b$ is denoted by
$\mathds{1}\\{x=b\\}$; this indicator equals $1$ if $x=b$ and $0$, otherwise.
For sequences $(a_{n})_{n\geq 1}$ and $(b_{n})_{n\geq 1}$ of positive reals,
$a_{n}=o(b_{n})$ if $\lim_{n\to\infty}\frac{a_{n}}{b_{n}}=0$, $a_{n}=O(b_{n})$
if for all $n$ large enough, $a_{n}\leq c\cdot b_{n}$, for some $c>0$, and
$a_{n}=\Theta(b_{n})$ if for all $n$ large enough, we have that $m\cdot
b_{n}\leq a_{n}\leq M\cdot b_{n}$, for some constants $m,M\in\mathbb{R}$.

##  III Main Results for DMCs

We now formalize the problem for the case the noisy channel is a DMC, and
present our main results. Later on, in Section V we will extend Theorem III.1
here to general multi-letter channels. Consider a DMC $W$ with finite input
and output alphabets $\mathcal{X}$ and $\mathcal{Y}$, respectively, specified
by the channel law $\\{P_{Y|X}(y|x)=W(y|x):\
x\in\mathcal{X},y\in\mathcal{Y}\\}$. Let $X\sim P_{X}$ be the input to the
channel. Our setting of interest is when $d\geq 1$ noisy outputs are obtained
by independently passing the input through the DMC. Let these outputs be
denoted by $Y_{1},\ldots,Y_{d}$; their conditional distribution obeys

$P(Y^{d}=y^{d}\mid X=x)=\prod_{i=1}^{d}W(y_{i}|x).$ (5)

We call a DMC with a channel law as above as the _$d$ -view_ DMC $W^{(d)}$. We
assume further that $|\mathcal{X}|$ and $|\mathcal{Y}|$ do not depend on $d$.

Now, given any DMC $W$, we denote its capacity by [18]

$C(W)=\max_{P_{X}}I(X;Y)=\max_{P_{X}}\mathbb{E}\left[\log\frac{W(Y|X)}{\sum_{x\in\mathcal{X}}P(x)W(Y|x)}\right].$
(6)

Hence, the capacity of $W^{(d)}$ is given by $C^{(d)}:=\max_{P_{X}}I^{(d)},$
where $I^{(d)}:=I(X;Y^{d})$. Further, for any input distribution $P_{X}$, the
channel dispersion of the $d$-view DMC $W$ is given by

$V^{(d)}:=\mathbb{E}\left[\left(\iota(X;Y^{d})-I(X;Y^{d})\right)^{2}\right],$
(7)

where

$\iota(x;y^{d}):=\log\frac{P(y^{d}|x)}{P(y^{d})}$ (8)

is the information density. We are interested in characterizing the behaviour
of $C^{(d)}$ (or more generally, of $I^{(d)}$) and $V^{(d)}$ when $d$ is
large. From operational considerations, we can argue that $I^{(d)}$ and
$V^{(d)}$ are non-decreasing in $d$. More formally, for $I^{(d)}$, the data
processing inequality [17, Thm. 2.8.1] guarantees that $I^{(d)}$ is non-
decreasing in $d$. Furthermore, it is reasonable to expect that $I^{(d)}$ and
$V^{(d)}$ converge to $\mathsf{H}(X)$ and $\mathsf{V}(X)$, respectively, since
for very large $d$, the “uncertainty” introduced by the channel is expected to
drop to $0$. In this work, we confirm these convergence results by showing
that the $I^{(d)}$ and $V^{(d)}$ in fact converge to their limiting values
exponentially quickly in $d$, and explicitly identify the rate of convergence.

To build some intuition why the convergence is exponentially fast in $d$, at
least for $I^{(d)}$, consider the simple example of the $d$-view BSC$(p)$,
which we denote by BSC${}^{(d)}(p)$ (here, $p<1/2$ is the crossover
probability of the BSC), with a uniform input distribution. At the decoder
end, we construct a simple “data processor” that takes the (random) outputs
$Y^{d}\in\\{0,1\\}^{d}$ and computes their majority $M\in\\{0,1\\}$.
Intuitively, the more the number of noisy output sequences (or views) that are
available to the decoder, the better the estimate that results from majority
decoding. More precisely, we have

$\displaystyle I^{(d)}$ $\displaystyle=I(X;Y^{d})$ (9) $\displaystyle\geq
I(X;M)=\log 2-h_{b}(\Pr[X\neq M]),$ (10)

where the inequality holds by the data processing inequality and the last
equality holds by symmetry. Now, observe that since $p<1/2$, we have by the
Chernoff bound (see [19, Example 1.6.2]) that

$\displaystyle\Pr[X\neq M]$ $\displaystyle\leq\text{exp}(-d\cdot
D(\text{Ber}(1/2)||\text{Ber}(p)))$ (11) $\displaystyle=\text{exp}(-d\cdot
Z(p)),$ (12)

where $Z(p)=2\sqrt{p(1-p)}$ is the Bhattacharya parameter for the BSC$(p)$.
Therefore, for large enough $d$, we have that $\Pr[X\neq M]$ is sufficiently
small so that

$h_{b}(\Pr[X\neq M])\leq-2\Pr[X\neq M]\cdot\log\Pr[X\neq M].$ (13)

Hence, for sufficiently large $d$, we see that $I^{(d)}\geq\log
2-dZ(p)\cdot\text{exp}(-d\cdot Z(p))$, thereby providing reason for the
intuition that the convergence of $I^{(d)}$ to $\log 2$ is exponentially fast
in $d$. In fact, in Theorem III.1, we argue that the rate $Z(p)$ is in fact
tight for the BSC$(p)$.

Our main theorem is given below.

######  Theorem III.1.

We have that

$I^{(d)}=\mathsf{H}(X)-\textnormal{exp}\left({-d\rho+\Theta(\log
d|\mathcal{X}|)}\right),\ $ (14)

and

$\left\lvert
V^{(d)}-\mathsf{V}(X)\right\rvert=\textnormal{exp}\left({-d\rho+\Theta(\log
d|\mathcal{X}|)}\right),$ (15)

where

$\rho=\min_{x,x^{\prime}:x\neq
x^{\prime}}\mathsf{C}(P_{Y|x},P_{Y|x^{\prime}}).$ (16)

Note that the theorem above captures the dependence of the speed of
convergence of mutual information and dispersion to their limits in terms of
both the number of views $d$ and the size of the input alphabet (assumed to be
independent of $d$). The dependence on $|\mathcal{X}|$ will assume
significance when we transition to multi-letter channels in Section V.

We now proceed to interpret Theorem III.1. Suppose we define the rates

$\displaystyle\rho(I)$
$\displaystyle:=\liminf_{d}-\frac{1}{d}\cdot\log\left(\mathsf{H}(X)-I^{(d)}\right)$
(17) $\displaystyle=\liminf_{d}-\frac{1}{d}\cdot\log\mathsf{H}(X|Y^{d}),$ (18)

and

$\displaystyle\rho(V)$
$\displaystyle:=\liminf_{d}-\frac{1}{d}\cdot\log\left\lvert\mathsf{V}(X)-V^{(d)}\right\rvert,$
(19)

we get by the above result that these rates of convergence obey
$\rho(I)=\rho(V)=\rho$, which in turn is independent of the input distribution
$P_{X}$, with possible dependence on its support. Further, the limits in the
definitions of these rates exist. Moreover, note that for a binary-input
memoryless symmetric (BIMS) channel $W$ (see [20, Ch. 4] for a definition),
the function

$f(\lambda):=\log\left(\sum_{y\in\mathcal{Y}}P(y|0)^{1-\lambda}P(y|1)^{\lambda}\right)$
(20)

is symmetric about $\lambda=1/2$. Hence, using the fact that $f$ is convex, we
obtain that the minimum in (3) is attained at $\lambda=1/2$, giving

$\displaystyle\mathsf{C}(P_{Y|0},P_{Y|1})$
$\displaystyle=-\log\sum_{z\in\mathcal{Z}}\sqrt{P_{Y|0}(z|0)P_{Y|1}(z|1)}$
(21) $\displaystyle=-\log Z_{b}(W),$ (22)

where $Z_{b}(W)$ is the Bhattacharya parameter of the BIMS channel $W$. Hence,
following the results in [21], the rates of convergence for a BIMS channel $W$
are extremized by a BEC and BSC having the same capacity as $W$, respectively,
with the BEC having the largest and BSC having the smallest Bhattacharya
parameters, respectively. Here, for the $d$-view BSC$(p)$, we have
$\rho(I)=\rho(V)=-\log 2\sqrt{p(1-p)}$, and for the $d$-view BEC$(\epsilon)$,
we have $\rho(I)=\rho(V)=-\log\epsilon$. Furthermore, for the Z-channel with
parameter $\delta$, $\rho(I)=\rho(V)=-\log\delta$. In fact, for most well-
behaved DMCs $W$, we will have that $\rho(I)=\rho(V)>0$, implying exponential
convergence of mutual information and dispersion to $\mathsf{H}(X)$ and
$\mathsf{V}(X)$, respectively.

Theorem III.1 along with the normal approximation for finite blocklengths [22]
then allow us to characterize, up to exponential tightness, the largest
finite-blocklength rates achievable over a $d$-view DMC $W^{(d)}$, under some
regularity conditions. Our presentation follows that in [23] (see also [24,
Thm. 22.2]). Suppose that the DMC $W^{(d)}$ is non-singular (see the
definition in [23, Sec. 4.2.1]). Let $M^{\star}(n,\epsilon)$ be the largest
integer $M$ such that there exists a blocklength-$n$ code with maximal
probability of error $\epsilon>0$ over $W^{(d)}$. Further, suppose that under
the uniform input distribution, we have that $V^{(d)}>0$. For
$t\in\mathbb{R}$, let $\Phi(t)$ be the Gaussian cumulative distribution
function (c.d.f.), i.e.,

$\Phi(t)=\int_{-\infty}^{t}\frac{1}{\sqrt{2\pi}}e^{-z^{2}/2}\mathrm{d}z,$ (23)

with $\Phi^{-1}$ denoting its inverse. We then have the following theorem:

######  Theorem III.2.

For any non-singular DMC $W^{(d)}$, for all $n\geq 1$ and $\epsilon\in(0,1)$,
we have

$\displaystyle\frac{\log M^{\star}(n,\epsilon)}{n}$
$\displaystyle\geq\log|\mathcal{X}|-e^{-d\rho+\Theta(\log
d|\mathcal{X}|)}+\Phi^{-1}(\epsilon)\cdot\frac{e^{-d\rho/2+\Theta(\log
d|\mathcal{X}|)}}{\sqrt{n}}+\frac{\log n}{2n}+O\left(1\right),$ (24)

where $\rho=\rho(I)=\rho(V)$.

###### Proof.

The proof follows from [23, Thm. 4.1] by choosing the input distribution
$P_{X}$ to be the uniform distribution. ∎

Clearly, it follows from the above theorem that for any finite $n$, by
choosing $d=\rho^{-1}\log n$, we can obtain rates

$\frac{\log M^{\star}(n,\epsilon)}{n}\geq\log|\mathcal{X}|-O\left(\frac{\log
n}{n}\right)$ (25)

over any $d$-view DMC $W^{(d)}$.

Next, we consider the special case of the $d$-view BSC$(p)$, which we denote
by $\text{BSC}^{(d)}(p)$; the capacity of this channel is known to be equal to
the capacity of the so-called binomial channel [11, Sec. III.A], denoted by
$\mathsf{Bin}_{d}(p)$. This capacity $C(\mathsf{Bin}_{d}(p))$ obeys

$\displaystyle C(\mathsf{Bin}_{d}(p))=\log
2+\sum_{i=0}^{d}\binom{d}{i}\left(p^{i}(1-p)^{d-i}\log\frac{p^{i}(1-p)^{d-i}}{p^{i}(1-p)^{d-i}+p^{d-i}(1-p)^{i}}\right),$
(26)

and the capacity is achieved by the input distribution
$P_{X}=\text{Ber}(1/2)$.

While Theorem III.1 determines the rate of convergence of
$C\left(\text{BSC}^{(d)}(p)\right)=C(\mathsf{Bin}_{d}(p))$ (via the rate of
convergence of the mutual information $I(X;Y^{d})$ under a uniform input
distribution $P_{X}=\text{Ber}(1/2)$) to $\mathsf{H}(P_{X})=1$ in the
asymptotic regime of large $d$, it will be useful if a more fine-grained, non-
asymptotic understanding of the capacity of this basic multi-view channel is
obtainable. To this end, we identify a closely-related DMC, which we call the
_Poisson approximation channel_ and denote by $\mathsf{Poi}_{d}(p)$, whose
capacity turns out to be a good approximation to $C(\mathsf{Bin}_{d}(p))$. The
DMC $\mathsf{Poi}_{d}(p)$ has input alphabet $\mathcal{X}=\\{0,1\\}$ and
output alphabet
$\mathcal{R}=(\mathbb{N}\cup\\{0\\})\times(\mathbb{N}\cup\\{0\\})$. We denote
the input bit as $X$ and the output as the pair $(R_{1},R_{2})$. The channel
law obeys

$\displaystyle
P_{R_{1},R_{2}|X}(r_{1},r_{2}|x)=P_{R_{1}|X}(r_{1}|x)P_{R_{2}|x}(r_{2}|x),\text{for
all}\ x\in\\{0,1\\}\ \text{and}\
(r_{1},r_{2})\in(\mathbb{N}\cup\\{0\\})\times(\mathbb{N}\cup\\{0\\}),$ (27)

where

$\displaystyle P_{R_{1}|0}$ $\displaystyle=\text{Poi}(d(1-p)),\
P_{R_{2}|0}=\text{Poi}(dp),\ \text{and}\ P_{R_{1}|1}=\text{Poi}(dp),\
P_{R_{2}|1}=\text{Poi}(d(1-p)).$ (28)

Here, the random variables $R_{1}$ and $R_{2}$ are approximations for the
number of $0$s and $1$s, respectively, that are received as part of the $d$
outputs of the binomial channel. Further, Poi$(\gamma)$ denotes the Poisson
distribution with parameter $\gamma$. Note that $\mathsf{Poi}_{d}(p)$ is a
BIMS channel; hence, its capacity is achieved by $P_{X}=\text{Ber}(1/2)$ (see
[20, Problem 4.8]). The following theorem then holds.

######  Theorem III.3.

We have that

$C(\mathsf{Poi}_{d}(p))\leq C(\mathsf{Bin}_{d}(p))\leq
C(\mathsf{Poi}_{d}(p))+\exp(-d(1-Z(p)))-Z(p)^{2d},$ (29)

where $Z(p)=2\sqrt{p(1-p)}$ is the Bhattacharya parameter of the BSC$(p)$.

Figure 1 plots the capacities of the $\mathsf{Bin}(p)$ and $\mathsf{Poi}(p)$
channels for varying values of $d$. It is clear from the plots and from
Theorem III.3 that $C(\mathsf{Poi}_{d}(p))$ is a tight lower bound on
$C(\mathsf{Bin}_{d}(p))$; furthermore, the tightness of the lower bound
improves as $d$ increases.

The result of Theorem III.3 can be easily generalized to $d$-view BIMS
channels $W^{(d)}$ with a finite output alphabet. It is well-known (see, e.g.,
Section II in [25]) that any BIMS channel $W$ with a finite output alphabet
can be decomposed into finitely many BSC subchannels, i.e.,

$W_{Y|X=x}=\sum_{i=1}^{K}\epsilon_{i}\cdot W^{(i)}_{Y|X=x},$ (30)

for some $K<\infty$, for any $x\in\\{0,1\\}$, with $W^{(i)}_{Y|X=x}$ being the
channel law of a BSC with crossover probability $p_{i}$. Here, $\epsilon_{i}$
is the probability of choosing subchannel $i$, with $\sum_{i}\epsilon_{i}=1$.
Let $P_{s}$ be the distribution on $\\{1,\ldots,K\\}$ with mass $\epsilon_{i}$
at point $i$. We then have that

$C^{(d)}(W)=\mathbb{E}\left[C(J_{1},\ldots,J_{d})\right],$ (31)

where the random variables $J_{i}$, $1\leq i\leq K$, are drawn i.i.d.
according to $P_{s}$, and the notation $C(j_{1},\ldots,j_{d})$ refers to the
capacity of that channel with the channel law

$P(Y^{d}=y^{d}|X=x)=\prod_{\ell=1}^{d}W^{(j_{\ell})}(y_{\ell}|x),$ (32)

for $x\in\\{0,1\\}$ and $y^{d}\in\mathcal{Y}^{d}$. Now, suppose that
$0<p_{1}\leq p_{2}\leq\ldots\leq p_{K}<1/2$. We then have from Theorem III.3
and (31) that

$C(\mathsf{Poi}_{d}(p_{K}))\leq C^{(d)}(W)\leq
C(\mathsf{Poi}_{d}(p_{1}))+\exp(-d(1-Z(p_{1})))-Z(p_{1})^{2d}.$ (33)

Figure 1: Plots comparing $C(\mathsf{Bin}(p))$ and $C(\mathsf{Poi}(p))$ for
$p\in[0,1]$, and $d\in\\{3,6,12,24\\}$.

##  IV Proof Sketch of Main Results

In this section, we provide a sketch of our strategy for proving Theorem III.1
for a DMC $W$ with an aribitrary distribution $P_{X}$. To this end, we shall
first consider the special case when $W$ is a BIMS channel, with a uniform
input distribution, and provide a simple proof for the convergence of the
mutual information $I^{(d)}$ to the input entropy. We then provide a brief
sketch of the proof of Theorem III.1 for general DMCs, which makes use of
well-known results from large-deviations theory. The full proof, owing to its
length, is presented in Section VII.

###  IV-A Convergence of Mutual Information for BIMS Channels

To build intuition, we present a simple proof for the case when the DMC $W$ is
a BIMS channel, with $P_{X}=\text{Ber}(1/2)$. The choice of the input
distribution being uniform assumes relevance since the capacity of a BIMS
channel is achieved by uniform inputs (see [20, Problem 4.8]).

The following bounds on the conditional entropy of the input to a BIMS channel
given the output, which are drawn from [26, Prop. 2.8], will prove useful.
Recall the definition of the Bhattacharya parameter of a BIMS channel $W$ with
output alphabet $\mathcal{Y}$ given by
$Z_{b}(W):=\sum_{y\in\mathcal{Y}}\sqrt{P_{Y|0}(y)P_{Y|1}(y)}$.

######  Lemma IV.1.

Given a BIMS channel $\overline{W}$ with input $\overline{X}\sim P_{X}$, where
$P_{X}=\operatorname{Ber}(1/2)$, and output $\overline{Y}$, we have that

$Z_{b}(\overline{W})^{2}\leq\mathsf{H}(\overline{X}\mid\overline{Y})\leq\log(1+Z_{b}(\overline{W})).$
(34)

We thus obtain the following simple corollary.

######  Corollary IV.1.

Given a BIMS channel $W$ with input $X\sim P_{X}$, where
$P_{X}=\operatorname{Ber}(1/2)$, we have that for the $d$-view DMC $W^{(d)}$,

$Z_{b}({W})^{2d}\leq\mathsf{H}({X}\mid{Y^{d}})\leq Z_{b}({W})^{d}.$ (35)

###### Proof.

We first observe that when $W$ is a BIMS channel, then so is the $d$-view DMC
$W^{(d)}$. To see why this is true, note that corresponding to a BIMS channel
$W$, there exists a permutation $\pi:\mathcal{Y}\to\mathcal{Y}$ such that

$W(y\mid 0)=W(\pi(y)\mid 1),$ (36)

with $\pi$ being an involution, i.e., $\pi^{-1}=\pi$. Now, for the $d$-view
DMC $W^{(d)}$, we define the permutation
$\pi^{(d)}:\mathcal{Y}^{d}\to\mathcal{Y}^{d}$ such that

$\pi^{(d)}(y_{1},y_{2},\ldots,y_{d})=(\pi(y_{1}),\pi(y_{2}),\ldots,\pi(y_{d})),$
(37)

for $y_{1},\ldots,y_{d}\in\mathcal{Y}$. Clearly, we have that $\pi^{(d)}$ is
an involution, with

$W^{(d)}((y_{1},\ldots,y_{d})\mid 0)=W(\pi^{(d)}(y_{1},\ldots,y_{d})\mid 1),$
(38)

from (5). This hence implies that $W^{(d)}$ is also a BIMS channels.

Now, the Bhattacharya parameter

$\displaystyle Z_{b}(W^{(d)})$
$\displaystyle=\sum_{y^{d}\in\mathcal{Y}^{d}}\sqrt{P_{Y|0}(y^{d}|0)P_{Y|1}(y^{d}|1)}$
(39)
$\displaystyle=\sum_{y^{d}\in\mathcal{Y}^{d}}\prod_{i=1}^{d}\sqrt{P_{Y|0}(y_{i}|0)P_{Y|1}(y_{i}|1)}$
(40)
$\displaystyle=\prod_{i=1}^{d}\sum_{y_{i}\in\mathcal{Y}}\sqrt{P_{Y|0}(y_{i}|0)P_{Y|1}(y_{i}|1)}$
(41) $\displaystyle=Z_{b}(W)^{d}.$ (42)

The proof is then completed by appealing to Lemma IV.1 and noting that
$\log(1+z)\leq z$, for all $z>-1$. ∎

Moreover, we have the following bound on $\rho(I)$ for general binary-input
DMCs and for arbitrary input distributions $P_{X}$.

######  Lemma IV.2.

Given a binary-input DMC $W$ with input $X\sim P_{X}$, where $P_{X}$ is
arbitrary, we have that

$\mathsf{H}(X|Y^{d})\geq e^{-d\cdot\mathsf{C}(P_{Y\mid X=0},P_{Y\mid
X=1})+\Theta(\log d)}.$ (43)

###### Proof.

Observe that

$\displaystyle\mathsf{H}(X|Y^{d})$
$\displaystyle=\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(X\mid
Y^{d})}\right].$ (44)

Further, recall that in a binary Bayesian hypothesis testing setting (see [17,
Ch. 11]) with prior $P_{X}$ and hypotheses $\\{P_{Y\mid 0},P_{Y\mid 1}\\}$, we
have that the probability of correct decision is given by

$\mathbb{E}\left[P(X\mid Y^{d})\right]=1-e^{-d\cdot\mathsf{C}(P_{Y\mid
X=0},P_{Y\mid X=1})+\Theta(\log d)}.$ (45)

Hence, we see that for large enough $d$,

$\displaystyle\mathsf{H}(X|Y^{d})$
$\displaystyle=\mathbb{E}\left[\log\frac{1}{P(X\mid Y^{d})}\right]$ (46)
$\displaystyle\geq-\log\left(1-e^{-d\cdot\mathsf{C}(P_{Y\mid X=0},P_{Y\mid
X=1})+\Theta(\log d)}\right)$ (47) $\displaystyle\geq
e^{-d\cdot\mathsf{C}(P_{Y\mid X=0},P_{Y\mid X=1})+\Theta(\log d)},$ (48)

where the first inequality follows from Jensen’s inequality and the second
from the fact that $\log(1+z)\leq z$, for $z>-1$. Also, the $\Theta(\log d)$
term in the exponent in (47) is due either to the Laplace method (see [27,
Sec. 4.2]) or to the results of [28, Thm. 2.1 and Corollary 1].

∎

The above ingredients suffice to afford a proof of Theorem III.1 for the
special case of BIMS channels with a uniform input distribution.

###### Proof of Thm. III.1 for BIMS channels with uniform inputs.

For the case when $W$ is a BIMS channel, we have that
$\mathsf{C}(P_{Y|0},P_{Y|1})=-\log Z_{b}(W)$ (see the remark following the
statement of Theorem III.1). Hence, when the input distribution is uniform, we
have from Corollary IV.1, we have that $\mathsf{H}(X|Y^{d})\leq
e^{-d\cdot\mathsf{C}(P_{Y|0},P_{Y|1})}$. The proof concludes by appealing then
to Lemma IV.2, which shows that

$\mathsf{H}(X|Y^{d})\geq e^{-d\cdot\mathsf{C}(P_{Y|0},P_{Y|1})+\Theta(\log
d)}.$ (49)

Hence, overall, we have that

$\mathsf{H}(X|Y^{d})=e^{-d\cdot\mathsf{C}(P_{Y|0},P_{Y|1})+\Theta(\log d)}.$
(50)

∎

It is possible, with some effort, to prove Theorem III.1 for $I^{(d)}$ for
general DMCs with arbitrary input distributions with the aid of [1, Lemma 9]
(see also [2, Thm. 5]) and an extension of Lemma IV.2. However, the analysis
of dispersion requires more involved techniques. Owing to the length of the
proofs, we present a detailed proof for $I^{(d)}$ that introduces our
techniques, in Section VII-A, and then extend them to $V^{(d)}$, in Section
VII-B.

We now sketch a broad outline of the proof strategy for the convergence of
mutual information to the input entropy. We first express the conditional
entropy $\mathsf{H}(X|Y^{d})$ as

$\displaystyle\mathsf{H}(X|Y^{d})$
$\displaystyle=\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(X\mid
Y^{d})}\right]$ (51)
$\displaystyle=\sum_{x\in\mathcal{X}}P_{X}(x)\mathbb{E}\left[\log\frac{1}{P_{X\mid
Y^{d}}(x\mid Y^{d})}\Bigg{\lvert}X=x\right].$ (52)

We then fix an $x\in\mathcal{X}$ and focus on the inner term in the summation
above. Then,

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]=\int_{0}^{\infty}\mathbb{P}\left[\log\frac{1}{P_{X\mid
Y^{d}}(x\mid Y^{d})}\geq t\Bigg{\lvert}X=x\right]\mathrm{d}t.$ (53)

Our approach is to obtain (exponentially tight) bounds on the probability
$\mathbb{P}\left[-\log P_{X\mid Y^{d}}(x\mid Y^{d})\geq t\lvert X=x\right]$,
using techniques from large-deviations theory—Sanov’s theorem, in particular.
We show that

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]=\text{exp}\left({-d\cdot\min_{\tilde{x}\neq
x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d|\mathcal{X}|)}\right).$
(54)

This then allows us to use Laplace’s method (e.g., see [27, Sec. 4.2]) and the
independence of the input distribution $P_{X}$ on $d$ to conclude that

$\mathsf{H}(X|Y^{d})=\max_{\begin{subarray}{c}x,\tilde{x}:\tilde{x}\neq
x\end{subarray}}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right),$ (55)

and hence that

$I^{(d)}=\mathsf{H}(X)-\textnormal{exp}\left({-d\rho+\Theta(\log
d|\mathcal{X}|)}\right).$ (56)

Interestingly, our proof strategy allows us to obtain insights into the
“higher-order” terms in the exponent of $\mathsf{H}(X|Y^{d})$ and their
dependence on both $d$ and the size of the input alphabet $|\mathcal{X}|$. The
proof for the convergence of the channel dispersion to the input varentropy is
similar, and relies on the results obtained during the derivation of the
convergence of the mutual information to the input entropy.

In the next section, we extend Theorem III.1 to general _multi-letter_
channels, which includes as a special case, synchronization channels such as
the deletion channel. We then derive explicit, analytical bounds on the rates
of convergence of the mutual information and dispersion of the deletion
channel to their limits.

##  V Convergence for Multi-Letter Channels and Some Examples

Recall that Theorem III.1 presented the convergence of mutual information and
channel dispersion for $d$-view DMCs $W^{(d)}$, where the channel $W$ is
specified by _single-letter_ transition probabilities $\\{W(y|x):\
x\in\mathcal{X},y\in\mathcal{Y}\\}$. In this section, we first extend the
statement of this theorem and its proof to multi-letter channels. Consider a
multi-letter channel $W_{n,\nu}$, for any $n,\nu\geq 0$ that are independent
of $d$, specified by a channel law
$\\{W(y^{\nu}|x^{n})=P_{Y^{\nu}|X^{n}}(y^{\nu}|x^{n}):\
x^{n}\in\mathcal{X}^{n},y^{\nu}\in\mathcal{Y}^{\nu}\\}$. Here, the input
alphabet is $\mathcal{X}^{n}$ and the output alphabet is $\mathcal{Y}^{\nu}$.
We work with the $d$-view multi-letter channel $W_{n,\nu}^{(d)}$ defined by
the channel law

$P(Y^{d\nu}=y^{d\nu}\mid
X^{n}=x^{n})=\prod_{i=1}^{d}W_{n,\nu}(y^{\nu}|x^{n}).$ (57)

Recall here our assumption that $|\mathcal{X}|$ and $|\mathcal{Y}|$ do not
depend on $d$. Similar to the earlier definition, we let

$I_{n,\nu}^{(d)}:=I(X^{n};Y^{d\nu})$ (58)

to be the mutual information rate over $W_{n,\nu}^{(d)}$. Here, we assume as
before that the input distribution $P_{X^{n}}$ is arbitrary, but fixed; in
particular, it is $d$-independent. Likewise, let the channel dispersion be

$V_{n,\nu}^{(d)}:=\mathbb{E}\left[\left(\iota(X^{n};Y^{d\nu})-I(X^{n};Y^{d\nu})\right)^{2}\right],$
(59)

where $\iota(x;y^{d}):=\log\frac{P(y^{d\nu}|x^{n})}{P(y^{d\nu})}$. The
following corollary of Theorem III.1 holds:

######  Corollary V.1.

We have that

$I_{n,\nu}^{(d)}=\mathsf{H}(X^{n})-\textnormal{exp}\left({-d\rho_{n,\nu}+\Theta(\log
d)+\Theta(n\cdot\log|\mathcal{X}|)}\right),$ (60)

and

$\left\lvert
V_{n,\nu}^{(d)}-\mathsf{V}(X^{n})\right\rvert=\textnormal{exp}\left({-d\rho_{n,\nu}+\Theta(\log
d)+\Theta(n\cdot\log|\mathcal{X}|)}\right),$ (61)

where

$\rho_{n,\nu}:=\min_{x^{n},\tilde{x}^{n}:x^{n}\neq\tilde{x}^{n}}\mathsf{C}(P_{Y^{\nu}|x^{n}},P_{Y^{\nu}|\tilde{x}^{n}}).$
(62)

Note that the $\Theta(n\cdot\log|\mathcal{X}|)$ terms above arise due to the
fact that the input alphabet size is now $|\mathcal{X}|^{n}$, instead of
$|\mathcal{X}|$, as in Theorem III.1. Observe also, from the earlier proofs,
that only the $\Theta(\log|\mathcal{X}|)$ term gets scaled by a factor of $n$
and not the $\Theta(\log d)$ term.

Now, consider the special case when $\nu=n$ and the channel $W_{n,n}$
corresponds to an $n$-letter DMC; more precisely, suppose that the multi-
letter channel law obeys

$W_{n,n}(y^{n}|x^{n})=\prod_{i=1}^{n}W(y_{i}|x_{i}).$ (63)

Now, for the _single-letter_ channel $W$ as above, let
$\rho=\min_{x,\tilde{x}:x\neq\tilde{x}}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})$.
We then have the following corollary:

######  Corollary V.2.

For an $n$-letter DMC $W_{n,n}$,

$I_{n,n}^{(d)}=\mathsf{H}(X^{n})-\textnormal{exp}\left({-dn\rho+\Theta(\log
d)+n\cdot\Theta(\log|\mathcal{X}|)}\right),\ $ (64)

and

$\left\lvert
V_{n,n}^{(d)}-\mathsf{V}(X^{n})\right\rvert=\textnormal{exp}\left({-dn\rho+\Theta(\log
d)+n\cdot\Theta(\log|\mathcal{X}|)}\right).$ (65)

###### Proof.

The proof will follow from Corollary V.1 if we can show that
$\rho_{n,n}=n\rho$, for an $n$-letter DMC $W_{n,n}$. To this end, let
$u,v\in\mathcal{X}$ be such that $\rho=\mathsf{C}(P_{Y|u},P_{Y|v})$. Further,
observe that for any two inputs $x^{n}\neq\tilde{x}^{n}$, we have
$\mathsf{C}(P_{Y^{n}|x^{n}},P_{Y^{n}|\tilde{x}^{n}})=\sum_{i=1}^{n}\mathsf{C}(P_{Y|x_{i}},P_{Y|\tilde{x}_{i}})$.
Hence,

$\displaystyle\rho_{n,n}$
$\displaystyle=\min_{x^{n},\tilde{x}^{n}:x^{n}\neq\tilde{x}^{n}}\sum_{i=1}^{n}\mathsf{C}(P_{Y|x_{i}},P_{Y|\tilde{x}_{i}})$
(66)
$\displaystyle\geq\sum_{i=1}^{n}\min_{x_{i},\tilde{x}_{i}:x_{i}\neq\tilde{x}_{i}}\mathsf{C}(P_{Y|x_{i}},P_{Y|\tilde{x}_{i}})=n\rho,$
(67)

where equality in the second step is obtained when $x^{n}=(u,u,\ldots,u)$ and
$\tilde{x}^{n}=(v,v,\ldots,v)$. ∎

While Corollary V.1 treats $n$ and $\nu$ as fixed constants, one can
generalize the definitions of the $d$-view mutual information and channel
dispersion to the setting where $\nu$ is a _random variable_ too. In
particular, let $I_{n}^{(d)}$ and $V_{n}^{(d)}$ be defined the same way as in
(58) and (59), respectively, but where the expectations are taken with respect
to the randomness in the length $\nu$ of the outputs too. Furthermore, let

$f_{\lambda}(x^{n},\tilde{x}^{n}):=\sum_{m\geq
0}\Pr[\nu=m]\sum_{y^{m}}P^{1-\lambda}(y^{m}|x^{n})P^{\lambda}(y^{m}|\tilde{x}^{n}).$
(68)

We then define

$\rho_{n}:=\min_{x^{n}\neq\tilde{x}^{n}}\max_{\lambda\in[0,1]}-\log
f_{\lambda}(x^{n},\tilde{x}^{n}).$ (69)

In what follows, we present some estimates of $\rho_{n}$ for the deletion
channel, where the length $\nu\leq n$ of the outputs is random.

###  V-A Upper Bounds on $\rho_{n}$ for the Deletion Channel

In this subsection, we consider the multi-letter deletion channel, which is an
important example of a synchronization channel [3]. Recall that for
$\delta\in(0,1)$, the deletion channel $\text{Del}(\delta)$ deletes each input
bit $x_{i}\in\mathcal{X}$, $1\leq i\leq n$, with probability $\delta$.

For Del$(\delta)$, for any fixed $x^{n},\tilde{x}^{n}$ with
$x^{n}\neq\tilde{x}^{n}$, and for any fixed $\lambda\in(0,1)$, we have

$\displaystyle
f_{\lambda}(x^{n},\tilde{x}^{n})=\sum_{m=0}^{n}\delta^{n-m}(1-\delta)^{m}\sum_{y^{m}}N^{1-\lambda}(x^{n}\to
y^{m})\cdot N^{\lambda}(\tilde{x}^{n}\to y^{m}),$ (70)

where $N(u^{n}\to v^{m})$, for $u^{n}\in\\{0,1\\}^{n}$,
$v^{m}\in\\{0,1\\}^{m}$, is the number of occurrences of $v^{m}$ as a
(potentially non-contiguous) subsequence in $u^{n}$.

In what follows, we present three upper bounds on $\rho_{n}$ for
Del$(\delta)$, and via these upper bounds, arrive at some interesting
properties of $\rho_{n}$ and comparisons with the rates $\rho_{n,n}$ of the
BEC$(\delta)$ and BSC$(\delta)$. The upper bounds are obtained by fixing
specific sequences $x^{n}$, $\tilde{x}^{n}\in\mathcal{X}^{n}$ and using
$\max_{\lambda\in[0,1]}-\log f_{\lambda}(x^{n},\tilde{x}^{n})$, evaluated at
these chosen sequences, as an upper bound on $\rho_{n}$. The first of our
upper bounds is naïve and will be subsumed by the later bounds.

######  Lemma V.1.

For $\operatorname{Del}(\delta)$, we have that $\rho_{n}\leq-n\log{\delta}$.

###### Proof.

Consider _any_ fixed $x^{n},\tilde{x}^{n}$ with $x^{n}\neq\tilde{x}^{n}$. For
any $\lambda\in[0,1]$, $f_{\lambda}(x^{n},\tilde{x}^{n})\geq\delta^{n}$, from
(70), since the empty string occurs exactly once as a subsequence of both
$x^{n}$ and $\tilde{x}^{n}$. Hence, we have that

$\rho_{n}=\min_{x^{n}\neq\tilde{x}^{n}}\max_{\lambda\in[0,1]}-\log
f_{\lambda}(x^{n},\tilde{x}^{n})\leq-n\log{\delta}.$ (71)

∎

As expected, from the above lemma and from Corollary V.2, we see that the rate
$\rho_{n}$ for the deletion channel is _smaller_ than the rate $\rho_{n,n}$
for the $n$-letter erasure channel with erasure probability $\delta$. Indeed,
recall that for the BEC$(\delta)$, we have that $\rho=-\log\delta$, and hence,
by Corollary V.2, $\rho_{n,n}=-n\log\delta$. Note also that by an application
of the data processing inequality, it follows that the capacity of
$\operatorname{Del}(\delta)$ is at most the capacity of the BEC$(\delta)$, for
$\delta\in[0,1]$ [3, Sec. 5.2].

The bound that follows improves on this naïve upper bound, for a certain range
of $\delta$ values, and for large enough $n$. For simplicity, in the second
part of the next lemma, we assume that $n$ is even; the case of odd $n$ can be
handled with minor modifications to the exisiting proof.

######  Lemma V.2.

For $\operatorname{Del}(\delta)$, we have that
$\limsup_{n\to\infty}\rho_{n}=0$, if $\delta>1/2$.

###### Proof.

Fix $\delta>1/2$. We pick $x^{n},\tilde{x}^{n}$ to be, respectively, the
alternating sequences $01010\ldots$ and $10101\ldots$, each having length $n$,
for the purposes of this lemma.

Now, for any $y^{m}\in\\{0,1\\}^{m}$, with $m\leq n$, we see that $N(x^{n}\to
y^{m})=N(\tilde{x}^{n}\to y^{m})$. Furthermore, $N(x^{n}\to y^{m})>0$ iff
$w(y^{m})\in[\max\\{0,m-n/2\\},n/2]$; we then call $y^{m}$ “admissible”. For
such admissible $y^{m}$, we have that

$N(x^{n}\to
y^{m})=\binom{n/2}{w(y^{m})}\cdot\binom{n/2}{m-w(y^{m})}=N(\tilde{x}^{n}\to
y^{m}).$ (72)

The above expression is obtained by choosing $w(y^{m})$ locations among the
$n/2$ $1$s in $x^{n}$ (resp. $\tilde{x}^{n}$) as the locations of the $1$s in
$y^{m}$, and likewise, $n-w(y^{m})$ locations among the $n/2$ $0$s in $x^{n}$
(resp. $\tilde{x}^{n}$) as the locations of the $0$s in $y^{m}$. Furthermore,
in the above expression, we implicitly assume that the binomial coefficient
$\binom{k}{t}=0$ if $t<0$ or $t>k$.

Thus, for $\lambda\in(0,1)$,

$\displaystyle f_{\lambda}(x^{n},\tilde{x}^{n})$
$\displaystyle=\sum_{m=0}^{n}\delta^{n-m}(1-\delta)^{m}\sum_{y^{m}\text{
admissible}}\binom{n/2}{w(y^{m})}\binom{n/2}{m-w(y^{m})}$ (73)
$\displaystyle=\sum_{m=0}^{n}\delta^{n-m}(1-\delta)^{m}\sum_{w=\max\\{m-n/2,0\\}}^{\min\\{m,n/2\\}}\binom{m}{w}\binom{n/2}{w}\binom{n/2}{m-w}.$
(74)

Let us call the inner summation above as $\beta(m)$. Now, note that

$\beta(m)=\begin{cases}\sum_{w=0}^{m}\binom{m}{w}\binom{n/2}{w}\binom{n/2}{m-w},\
\text{if }m\leq n/2,\\\
\sum_{w=m-n/2}^{n/2}\binom{m}{w}\binom{n/2}{w}\binom{n/2}{m-w},\ \text{if
}m>n/2.\end{cases}$ (75)

After some algebra, we can write

$\beta(m)=\begin{cases}\sum_{w=0}^{m}\binom{m}{w}\binom{n/2}{w}\binom{n/2}{m-w},\
\text{if }m\leq n/2,\\\
\sum_{w=0}^{n-m}\binom{m}{n/2-w}\binom{n/2}{w}\binom{n/2}{m-(n/2-w)},\
\text{if }m>n/2.\end{cases}$ (76)

Let

$\alpha_{1}(m):=\sum_{w=0}^{m}\binom{m}{w}\binom{n/2}{w}\binom{n/2}{m-w}$ (77)

and

$\alpha_{2}(m):=\sum_{w=0}^{n-m}\binom{m}{n/2-w}\binom{n/2}{w}\binom{n/2}{m-(n/2-w)}.$
(78)

Consider $\alpha_{1}(m)$, for the case when $m\leq n/2$. We then have that

$\displaystyle\alpha_{1}(m)$ $\displaystyle\geq\min_{0\leq\omega\leq
m}\binom{n/2}{m-\omega}\cdot\sum_{w=0}^{m}\binom{m}{w}\binom{n/2}{w}$ (79)
$\displaystyle=\binom{n/2}{0}\binom{n/2+m}{m}=\binom{n/2+m}{m},$ (80)

where the first equality follows from the Chu-Vandermonde identity (see, e.g.,
[29, p. 42]). Likewise, consider $\alpha_{2}(m)$, for the case when $m\geq
n/2$. Note that

$\displaystyle\alpha_{2}(m)$
$\displaystyle=\sum_{w=0}^{n-m}\binom{m}{n/2-w}\binom{n/2}{w}\binom{n/2}{m-(n/2-w)}$
(81)
$\displaystyle=\sum_{w=0}^{n-m}\binom{m}{n/2-w}\binom{n/2}{w}\binom{n/2}{n-m-w}$
(82)
$\displaystyle\geq\sum_{w=0}^{n-m}\binom{n/2}{w}\binom{n/2}{n-m-w}=\binom{n}{m},$
(83)

where the last equality above again uses the Chu-Vandermonde identity. Thus,
we obtain that

$\beta(m)\geq\begin{cases}\binom{n/2+m}{m},\ \text{if }m\leq n/2,\\\
\binom{n}{m},\ \text{if }m>n/2.\end{cases}$ (84)

Plugging this back into (74), we see that

$\displaystyle f_{\lambda}(x^{n},\tilde{x}^{n})$
$\displaystyle\geq\sum_{m=0}^{n/2}\delta^{n-m}(1-\delta)^{m}\cdot\binom{n/2+m}{m}+\sum_{m=n/2+1}^{n}\delta^{n-m}(1-\delta)^{m}\cdot\binom{n}{m}.$
(85)

Call the first summation above as $\gamma_{1}$ and the second as $\gamma_{2}$.
Now, observe that $\gamma_{2}$ is precisely the probability $\Pr[L>n/2]$, for
a binomial random variable $L\sim\text{Bin}(n,\delta)$. It is well-known (see,
e.g., [19, Example 1.6.2]) that for $\delta>1/2$, this probability is at least

$1-\text{exp}(-n\cdot
D(\text{Ber}(1/2)||\text{Ber}(\delta)))=1-Z(\delta)^{n},$ (86)

where $Z(\delta)=2\sqrt{\delta(1-\delta)}$ is the Bhattacharya parameter of
the BSC$(\delta)$. Furthermore, note that

$\displaystyle\gamma_{1}$
$\displaystyle\geq(\delta(1-\delta))^{n/2}\cdot\binom{n}{n/2}$ (87)
$\displaystyle=(\delta(1-\delta))^{n/2}\cdot 2^{n-O(\log n)}$ (88)
$\displaystyle=Z(\delta)^{n}\cdot 2^{-O(\log n)}.$ (89)

where the first equality follows from [30, Eq. (5.38)].

Hence, we obtain that for $\lambda\in(0,1)$,

$\displaystyle f_{\lambda}(x^{n},\tilde{x}^{n})\geq
1-Z(\delta)^{n}\cdot(1-2^{-O(\log n)}).$ (90)

Using the previous inequality, we obtain that when $\delta>1/2$,

$\displaystyle\limsup_{n\to\infty}\rho_{n}$
$\displaystyle\leq\limsup_{n\to\infty}\max_{\lambda\in[0,1]}-\log
f_{\lambda}(x^{n},\tilde{x}^{n})$ (91)
$\displaystyle\leq\limsup_{n}\max\\{0,-\log(1-Z(\delta)^{n}\cdot(1-2^{-O(\log
n)}))\\}$ (92) $\displaystyle=0,$ (93)

where the last inequality uses the fact that for $\lambda\in\\{0,1\\}$, we
have $f_{\lambda}(x^{n},\tilde{x}^{n})=1$. ∎

Next, we show that for all $\delta\in(0,1)$ (and hence for $\delta\leq 1/2$
too), the rate of convergence $\rho_{n}$ can in fact be bounded from above by
a constant, for large enough $n$. Before we do so, we state and prove a useful
lemma.

######  Lemma V.3.

For $\operatorname{Del}(\delta)$, where $\delta\in(0,1)$, we have that

$\rho_{n}\leq\max_{\lambda\in[0,1]}\lambda\log
n-\log\mathbb{E}_{L\sim\text{Bin}(n,\delta)}\left[L^{\lambda}\right].$ (94)

###### Proof.

As before, we pick specific sequences $x^{n},\tilde{x}^{n}$ and seek to upper
bound $\rho_{n,\nu}$ by $\max_{\lambda\in[0,1]}-\log
f_{\lambda}(x^{n},\tilde{x}^{n})$, for this choice of $x^{n},\tilde{x}^{n}$.
Here, we choose $x^{n}=0^{n}$ and $\tilde{x}^{n}=0^{n-1}1$.

Clearly, for any $m\leq n$, we have that $y^{m}\in\\{0,1\\}^{n}$ is a
subsequence of $x^{n}$ iff $y^{m}=0^{m}$. For $y^{m}=0^{m}$, hence, it follows
that

$N(x^{n}\to y^{m})=\binom{n}{m}\ \text{and}\ N(\tilde{x}^{n}\to
y^{m})=\binom{n-1}{m}.$ (95)

Thus, for $\lambda\in(0,1)$,

$\displaystyle f_{\lambda}(x^{n},\tilde{x}^{n})$
$\displaystyle=\sum_{m=0}^{n}\delta^{n-m}(1-\delta)^{m}\cdot\binom{n}{m}^{1-\lambda}\cdot\binom{n-1}{m}^{\lambda}$
(96)
$\displaystyle=\sum_{m=0}^{n}\delta^{n-m}(1-\delta)^{m}\cdot\binom{n}{m}\cdot\left(\frac{n-m}{n}\right)^{\lambda}$
(97)
$\displaystyle=\mathbb{E}_{L\sim\text{Bin}(n,1-\delta)}\left[\left(1-\frac{L}{n}\right)^{\lambda}\right]$
(98)
$\displaystyle=\frac{1}{n^{\lambda}}\cdot\mathbb{E}_{L\sim\text{Bin}(n,\delta)}\left[{L}^{\lambda}\right],$
(99)

and the claim follows by noting that $f_{\lambda}(x^{n},\tilde{x}^{n})=1$, for
$\lambda\in\\{0,1\\}$. ∎

We next use Lemma V.3 to show that for large enough $n$, $\rho_{n}$ can be
bounded from above by a _constant_. We thus obtain the following corollary:

######  Corollary V.3.

For $\operatorname{Del}(\delta)$, where $\delta\in(0,1)$, we have that
$\limsup_{n\to\infty}\rho_{n}\leq-\log\delta$.

###### Proof.

The proof proceeds by obtaining estimates of the fractional moments of a
binomial random variable used in Lemma V.3. Let $\beta,\eta>0$ be small real
numbers. We then have that for $L\sim\text{Bin}(n,\delta)$, and
$\lambda\in(0,1)$,

$\displaystyle\mathbb{E}[L^{\lambda}]$
$\displaystyle\geq(n(\delta-\beta))^{\lambda}\cdot\Pr[L\geq n(\delta-\beta)]$
(100) $\displaystyle\geq(n(\delta-\beta))^{\lambda}\cdot(1-\text{exp}(-n\cdot
D(\text{Ber}(\delta-\beta)||\text{Ber}(\delta))))$ (101)
$\displaystyle\geq(1-\eta)\cdot(n(\delta-\beta))^{\lambda},$ (102)

for $n$ large enough.

Plugging (102) into Lemma V.3, we obtain that for $n$ large enough,

$\displaystyle\rho_{n}$ $\displaystyle\leq\max_{\lambda\in[0,1]}\lambda\log
n-\log\mathbb{E}_{L\sim\text{Bin}(n,\delta)}\left[L^{\lambda}\right]$ (103)
$\displaystyle\leq\max\bigg{\\{}0,\max_{\lambda\in(0,1)}\lambda\log
n-\lambda\log(n(\delta-\beta))-\log(1-\eta)\bigg{\\}}$ (104)
$\displaystyle=\max\bigg{\\{}0,\max_{\lambda\in(0,1)}-\lambda\log(\delta-\beta)-\log(1-\eta)\bigg{\\}}$
(105) $\displaystyle\leq-(1-\zeta)\log\delta,$ (106)

for small $\zeta>0$. Thus, taking $\limsup_{n\to\infty}$ on both sides of the
inequality above and letting $\zeta\downarrow 0$, we obtain the statement of
the corollary. ∎

Hence, putting together Lemma V.2 and Corollary V.3, we see that for the
deletion channel Del$(\delta)$, the rate $\rho_{n}$, for large enough $n$, is
bounded above by a fixed constant, for $\delta\leq 1/2$, and by an arbitrarily
small constant, for $\delta>1/2$.

In the next section, we take a detour from the asymptotic regime of large $d$
considered in the rest of the paper, and seek to obtain tight, non-asymptotic
bounds on the capacity of a special multi-view DMC, which holds for all values
of $d$.

##  VI Poisson Approximation Channel

In this section, we consider the special case of the $d$-view BSC$(p)$,
denoted by $\text{BSC}^{(d)}(p)$. Recall that the capacity of this channel
equals the capacity of the binomial channel $\mathsf{Bin}_{d}(p)$, which is
given in (26). Our objective is to show that the Poisson approximation channel
$\mathsf{Poi}_{d}(p)$ introduced in Section III has capacity that is a very
good lower bound on the capacity of $\text{BSC}^{(d)}(p)$, via the proof of
Theorem III.3. Before we proceed with the proof, we state and prove a simple
lemma about the concavity of the mutual information $I^{(d)}=I(X;Y^{d})$, for
any $d$-view DMC $W^{(d)}$ and input distribution $P_{X}$.

######  Lemma VI.1.

For any $d$-view DMC $W^{(d)}$ and input distribution $P_{X}$, we have that
$I^{(d)}$ is concave over the positive integers, i.e.,

$I^{(d)}-I^{(d-1)}\geq I^{(d+1)}-I^{(d)},$ (107)

for all $d\geq 1$.

###### Proof.

We first rewrite what we intend to prove differently: since
$I^{(m)}=\mathsf{H}(X)+\mathsf{H}(Y^{m})-\mathsf{H}(X,Y^{m})$, for any $m\geq
0$, with $I^{(0)}:=0$, we would like to show that

$\displaystyle\mathsf{H}(Y^{d})-$
$\displaystyle\mathsf{H}(Y^{d-1})+\mathsf{H}(X,Y^{d-1})-\mathsf{H}(X,Y^{d})$
$\displaystyle\geq\mathsf{H}(Y^{d+1})-\mathsf{H}(Y^{d})+\mathsf{H}(X,Y^{d})-\mathsf{H}(X,Y^{d+1}).$
(108)

However, observe that for any $m\geq 0$,
$\mathsf{H}(X,Y^{m+1})-\mathsf{H}(X,Y^{m})=\mathsf{H}(Y_{m+1}|X,Y^{m})=\mathsf{H}(Y_{m+1}|X)$,
by the channel law of $W^{(d)}$. Hence, (108) reduces to showing that

$\mathsf{H}(Y^{d})-\mathsf{H}(Y^{d-1})\geq\mathsf{H}(Y^{d+1})-\mathsf{H}(Y^{d}).$
(109)

Now, by the submodularity of entropy [24, Thm. 1.6], we have that

$\mathsf{H}(Y^{d-1},Y_{d+1})-\mathsf{H}(Y^{d-1})\geq\mathsf{H}(Y^{d+1})-\mathsf{H}(Y^{d}).$
(110)

The above implies (109), since the distributions of $(Y^{d-1},Y_{d+1})$ and
$Y^{d}$ are equal, by the stationarity of the DMC $W^{(d)}$. ∎

For clarity, we first write down the capacity $C(\mathsf{Poi}_{d}(p))$ of the
Poisson approximation channel. As argued in Section III, the capacity is
achieved when the inputs $X\sim P_{X}=\text{Ber}(1/2)$, yielding

$\displaystyle C(\mathsf{Poi}_{d}(p))$
$\displaystyle=\mathsf{H}(X)-\mathsf{H}(X|R_{1},R_{2})$ (111)
$\displaystyle=1+\sum_{\begin{subarray}{c}r_{1}\geq 0,\\\ r_{2}\geq
0\end{subarray}}\frac{e^{-dp}(dp)^{r_{1}}}{r_{1}!}\cdot\frac{e^{-d(1-p)}(d(1-p))^{r_{2}}}{r_{2}!}\cdot\log\frac{p^{r_{1}}(1-p)^{r_{2}}}{p^{r_{1}}(1-p)^{r_{2}}+p^{r_{2}}(1-p)^{r_{1}}}.$
(112)

We now prove Theorem III.3.

###### Proof of Thm. 3.

Consider the mutual information between the input and outputs of the
$\mathsf{Poi}_{d}(p)$ channel when $P_{X}$ is uniform over the inputs. Since
the number of outputs $N=R_{1}+R_{2}$ is known to the decoder, we have that

$\displaystyle C(\mathsf{Poi}_{d}(p))$ $\displaystyle=I(X;R_{1},R_{2})$ (113)
$\displaystyle=I(X;R_{1},R_{2}\mid N)$ (114)
$\displaystyle=\sum_{n=0}^{\infty}\mathbb{P}[N=n]\cdot I(X;R_{1},R_{2}\mid
N=n).$ (115)

Now, observe that since the sum of a Poi$(dp)$ random variable and a
Poi$(d(1-p))$ random variable is distributed according to Poi$(d)$, we have by
symmetry that $N\sim\text{Poi}(d)$. Further, it is easy to check that the
conditional distribution $P_{R_{1},R_{2}\mid N=n}$ obeys $P_{R_{1},R_{2}\mid
N=n}(r_{1},r_{2}\mid n)=\binom{n}{r_{1}}p^{r_{1}}(1-p)^{n-r_{1}}$, for all
$r_{1},r_{2}\geq 0$ such that $r_{1}+r_{2}=n$. Hence, we have that
$I(X;R_{1},R_{2}\mid N=n)=C(\mathsf{Bin}_{n}(p))$.

Thus, substituting in (115), we get that

$C(\mathsf{Poi}_{d}(p))=\mathbb{E}_{N\sim\text{Poi}(d)}\left[C(\mathsf{Bin}_{N}(p))\right].$
(116)

Next, using the above pleasing expression, we show that
$C(\mathsf{Poi}_{d}(p))$ is indeed a lower bound on $C(\mathsf{Bin}_{d}(p))$.
From Lemma VI.1 we have that $C(\mathsf{Bin}_{n}(p))$ is concave over the
positive integers. Therefore, applying Jensen’s inequality, we get that

$\displaystyle C(\mathsf{Poi}_{d}(p))$
$\displaystyle=\mathbb{E}_{N\sim\text{Poi}(d)}\left[C(\mathsf{Bin}_{N}(p))\right]$
(117) $\displaystyle\leq
C(\mathsf{Bin}_{\mathbb{E}N}(p))=C(\mathsf{Bin}_{d}(p)).$ (118)

Furthermore, we have that

$\displaystyle C(\mathsf{Bin}_{d}(p))-C(\mathsf{Poi}_{d}(p))$
$\displaystyle=C(\mathsf{Bin}_{d}(p))-\mathbb{E}_{N\sim\text{Poi}(d)}\left[C(\mathsf{Bin}_{N}(p))\right]$
(119) $\displaystyle\leq
C(\mathsf{Bin}_{d}(p))-1+\mathbb{E}_{N\sim\text{Poi}(d)}[Z(p)^{N}]$ (120)
$\displaystyle\leq\text{exp}(-d(1-Z(p)))-Z(p)^{2d},$ (121)

where the two inequalities make use of Corollary IV.1 and the last inequality
uses the well-known expression for the moment-generating function of a Poisson
random variable. ∎

######  Remark.

For the binomial channel $\overline{\mathsf{Bin}}_{n}$, whose input is a real
number in $[0,1]$, with $n$ output trials, that is considered in [31] too, a
suitable Poisson approximation channel $\overline{\mathsf{Poi}}_{n}$ can be
designed. This channel takes as input $X\in[0,1]$ and outputs the pair
$(R_{1},R_{2})$ such that $P_{R_{1}|X}=\text{Poi}(nX)$ and
$P_{R_{2}|X}=\text{Poi}(n(1-X))$. For $\overline{\mathsf{Poi}}_{n}$, as above,
we will have that
$C(\overline{\mathsf{Poi}}_{n})=\mathbb{E}_{N\sim\text{Poi}(n)}\left[C(\overline{\mathsf{Bin}}_{N})\right]$.
However, the proof of the concavity of the capacity
$C(\overline{\mathsf{Bin}}_{n})$ as in Lemma VI.1 will not hold, owing to the
failure of the conditional independence assumption that is crucially employed
in the proof. We are hence unable to obtain a straightforward lower bound on
$C(\overline{\mathsf{Bin}}_{n})$ via $C(\overline{\mathsf{Poi}}_{n})$, using
the previous techniques.

##  VII Proofs

In this section, we provide a detailed proof of our main result, Theorem
III.1.

###  VII-A Convergence of Mutual Information for General DMCs

Given a general DMC $W$ with input alphabet $\mathcal{X}$ (not necessarily
binary) and output alphabet $\mathcal{Y}$, consider the $d$-view DMC
$W^{(d)}$. Let the input to $W^{(d)}$ be $X$, with input distribution being
$P_{X}$, and let its outputs be $Y_{1},\ldots,Y_{d}\in\mathcal{Y}^{d}$. The
joint distribution of the inputs and outputs is such that
$P_{X,Y^{d}}(x,y^{d})=P_{X}(x)\prod_{i=1}^{d}W(y_{i}|x)$. Much like the proof
of Corollary IV.1, the inequality

$\mathsf{H}(X|Y^{d})\leq Z_{g}(W)^{d},$ (122)

can be shown to hold (see [26, Prop. 4.8]), where

$Z_{g}(W):=\sum_{x\neq
x^{\prime}}\sum_{y\in\mathcal{Y}}\sqrt{P(x)W(y|x)P(x^{\prime})W(y|x^{\prime})}$
(123)

is a scaled version of the Bhattacharya parameter for general DMCs. This then
results in $\rho(I)\geq-\log Z_{g}(W)$, thereby showing that for well-behaved
DMCs, the rate of convergence of $I^{(d)}$ to $\mathsf{H}(X)$ is exponential
in $d$. We shall now take up the question of the exact speed of this
convergence.

To this end, we will be next interested in evaluating, up to exponential
tightness, the behaviour of

$\displaystyle\mathsf{H}(X|Y^{d})$
$\displaystyle=\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(X\mid
Y^{d})}\right]$ (124)
$\displaystyle=\sum_{x\in\mathcal{X}}P_{X}(x)\mathbb{E}\left[\log\frac{1}{P_{X\mid
Y^{d}}(x\mid Y^{d})}\Bigg{\lvert}X=x\right].$ (125)

Now, fix an $x\in\mathcal{X}$ and focus on the inner term in (125). Then,

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]=\int_{0}^{\infty}\mathbb{P}\left[\log\frac{1}{P_{X\mid
Y^{d}}(x\mid Y^{d})}\geq t\Bigg{\lvert}X=x\right]\mathrm{d}t.$ (126)

The inner probability, to wit,

$p_{x}(t):=\mathbb{P}\left[-\log P_{X\mid Y^{d}}(x\mid Y^{d})\geq t\lvert
X=x\right]$ (127)

is bounded as follows:

######  Lemma VII.1.

We have that

$\frac{p_{x}(t)}{(|{\cal X}|-1)}\leq\max_{\tilde{x}\neq
x}\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-(t-\log(|{\cal
X}|-1))}}{1-e^{-t}}\Bigg{\lvert}X=x\right]$ (128)

and

$p_{x}(t)\geq\max_{\tilde{x}\neq x}\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right].$
(129)

###### Proof.

First, observe that

$\displaystyle p_{x}(t)$
$\displaystyle=\mathbb{P}\left[\frac{P_{XY^{d}}(x,Y^{d})}{P_{Y^{d}}(Y^{d})}\leq
e^{-t}\Bigg{\lvert}X=x\right]$ (130)
$\displaystyle=\mathbb{P}\left[P(x)P(Y^{d}\mid x)\leq
e^{-t}\sum_{\tilde{x}}P(\tilde{x})P(Y^{d}\mid\tilde{x})\Big{\lvert}X=x\right]$
(131) $\displaystyle=\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{\sum_{\tilde{x}\neq
x}P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Big{\lvert}X=x\right].$
(132)

We first prove the upper bound in the lemma. The above probability obeys

$\displaystyle\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid x)}{\sum_{\tilde{x}\neq
x}P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right]$
$\displaystyle\leq\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid x)}{(|{\cal
X}|-1)\max_{\tilde{x}\neq
x}P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right]$
(133) $\displaystyle=\mathbb{P}\left[\frac{1}{|{\cal
X}|-1}\cdot\min_{\tilde{x}\neq x}\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right]$
(134) $\displaystyle\leq\sum_{\tilde{x}\neq x}\mathbb{P}\left[\frac{1}{|{\cal
X}|-1}\cdot\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right]$
(135) $\displaystyle\leq(|{\cal X}|-1)\cdot\max_{\tilde{x}\neq
x}\mathbb{P}\left[\frac{1}{|{\cal X}|-1}\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\Bigg{\lvert}X=x\right],$
(136)

thereby showing the upper bound. Further, for any $\tilde{x}$, we have that

$\displaystyle p_{x}(t)$ $\displaystyle=\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{\sum_{\tilde{x}\neq
x}P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\mid
X=x\right]$ (137) $\displaystyle\geq\max_{\tilde{x}\neq
x}\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-t}}{1-e^{-t}}\mid
X=x\right],$ (138)

thereby proving the lower bound. ∎

Since we are interested mainly in the behaviour of $\mathsf{H}(X|Y^{d})$ up to
first order in the exponent $d$, it suffices for us to understand the
behaviour of $p_{x}(t)$ upto first order in the exponent $d$ with the
expectation that we will accrue an additional $\Theta(\log d)$ term in the
exponent, in the final expression (see Eq. (126) above and [27, Sec. 4.2] for
intuition). To this end, following Lemma VII.1, for fixed $z\in[0,\infty)$ and
$c>0$, we shall focus on the term

$\Gamma_{x,\tilde{x}}(z):=\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{ce^{-z}}{1-e^{-z}}\Bigg{\lvert}X=x\right],$
(139)

with the reasoning that the rate of convergence of $\mathsf{H}(X|Y^{d})$ will
be dictated by the smallest rate of $\Gamma_{x,\tilde{x}}(z)$, as $z$
increases from $0$ to $\infty$.

Before we proceed, we require some more notation. Let us denote the log-
likelihood ratio by

$L_{x,\tilde{x}}^{y}:=\log\frac{P_{Y\mid X}(y\mid x)}{P_{Y\mid
X}(y\mid\tilde{x})}.$ (140)

For a given $y^{d}\in{\cal Y}^{d}$ and for $b\in\mathcal{Y}$, let
$\hat{Q}_{y^{d}}(b):=\frac{1}{d}\sum_{i=1}^{d}\mathds{1}\\{y_{i}=b\\}$ be the
empirical frequency of the letter $b$ in any output sequence. Further, we
define

$L_{x,\tilde{x}}(\hat{Q}):=\sum_{b\in{\cal Y}}\hat{Q}(b)L_{x,\tilde{x}}^{b}.$
(141)

Finally, let

$v_{x,\tilde{x}}\equiv
v_{x,\tilde{x}}(z):=\frac{1}{d}\left(\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(\tilde{x})}\right)$
(142)

and let $z(v_{x,\tilde{x}}):=\log\left(1+\frac{cP(\tilde{x})}{P(x)}\cdot
e^{-dv_{x,\tilde{x}}}\right)$ be its inverse function.

######  Proposition VII.1.

We have that for any fixed $\delta>0$,

  1. 1.

If $v_{x,\tilde{x}}\geq L_{x,\tilde{x}}({P_{Y|x}})+\delta$, then
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=\Theta(1)$.

  2. 2.

If $v_{x,\tilde{x}}\leq L_{x,\tilde{x}}({P_{Y|x}})-\delta$, then
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=e^{-dE(v_{x,\tilde{x}})+\Theta(\log
d)}$, where

$\displaystyle E(v_{x,\tilde{x}}):=$
$\displaystyle\begin{cases}\max\limits_{\lambda\geq
0}\bigg{[}-\log\left(\sum_{y}P(y|x)^{1-\lambda}P(y|x^{\prime})^{\lambda}\right)-\lambda
v_{x,\tilde{x}}\bigg{]},\ \text{if
}v_{x,\tilde{x}}\geq\min_{b\in\mathcal{Y}}L_{x,\tilde{x}}^{b},\\\ \infty,\
\text{otherwise}.\end{cases}$ (143)

###### Proof.

Observe that for any $z\in[0,\infty)$,

$\displaystyle\Gamma_{x,\tilde{x}}(z)$
$\displaystyle=\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{ce^{-z}}{1-e^{-z}}\Bigg{\lvert}X=x\right]$
(144) $\displaystyle=\mathbb{P}\left[\sum_{i=1}^{d}\log\frac{P_{Y\mid
X}(Y_{i}\mid x)}{P_{Y\mid
X}(Y_{i}\mid\tilde{x})}\leq\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(\tilde{x})}\Bigg{\lvert}X=x\right]$
(145)
$\displaystyle=\mathbb{P}\left[\sum_{i=1}^{d}L_{x,\tilde{x}}^{Y_{i}}\leq\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(\tilde{x})}\Bigg{\lvert}X=x\right]$
(146)
$\displaystyle=\mathbb{P}\left[\mathbb{E}_{\hat{Q}}\left[L_{x,\tilde{x}}^{Y^{d}}\right]\leq
v_{x,\tilde{x}}(z)\Big{\lvert}X=x\right].$ (147)

Writing this differently, we have that for any $v_{x,\tilde{x}}\in\mathbb{R}$,

$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=\mathbb{P}\left[\mathbb{E}_{\hat{Q}}\left[L_{x,\tilde{x}}^{Y^{d}}\right]\leq
v_{x,\tilde{x}}\Big{\lvert}X=x\right].$ (148)

Consider first the case when $v_{x,\tilde{x}}\geq
L_{x,\tilde{x}}({P_{Y|x}})+\delta$. Note that
$L_{x,\tilde{x}}({P_{Y|x}})=D(P_{Y|x}||P_{Y|\tilde{x}})>0$. We split this case
into two subcases.

  * •

If $v_{x,\tilde{x}}\geq\max_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}$ then
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=1$.

  * •

Otherwise, consider the case where $L_{x,\tilde{x}}(P_{Y\mid x})+\delta\leq
v_{x,\tilde{x}}\leq\max_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}$. Now, observe that

$\displaystyle 1\geq\Gamma_{x,\tilde{x}}($ $\displaystyle
z(v_{x,\tilde{x}}))\geq\mathbb{P}\left[\mathbb{E}_{\hat{Q}}\left[L_{x,\tilde{x}}^{Y^{d}}\right]\leq
L_{x,\tilde{x}}(P_{Y\mid x})+\delta\Big{\lvert}X=x\right].$ (149)

Furthermore, by a simple application of Markov’s inequality, we get that since
$L_{x,\tilde{x}}(P_{Y\mid x})=\mathbb{E}_{Y^{d}\sim
P_{Y^{d}|x}}[L_{x,\tilde{x}}^{Y^{d}}]$, the following inequality holds:

$\mathbb{P}\left[\mathbb{E}_{\hat{Q}}\left[L_{x,\tilde{x}}^{Y^{d}}\right]\leq
L_{x,\tilde{x}}(P_{Y\mid
x})+\delta\Big{\lvert}X=x\right]\geq\frac{\delta}{L_{x,\tilde{x}}(P_{Y\mid
x})+\delta}.$ (150)

Hence, we have that
$1\geq\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))\geq\frac{\delta}{L_{x,\tilde{x}}(P_{Y\mid
x})+\delta}$.

Hence, overall, if $v_{x,\tilde{x}}\geq L_{x,\tilde{x}}({P_{Y|x}})+\delta$, we
get that $\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=\Theta(1)$.

Next, consider the case when $v_{x,\tilde{x}}\leq
L_{x,\tilde{x}}({P_{Y|x}})-\delta$. We again split this case into two
subcases.

  * •

If $v_{x,\tilde{x}}\leq\min_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}$, then
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=0$.

  * •

If $\min_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}\leq v_{x,\tilde{x}}\leq
L_{x,\tilde{x}}(P_{Y\mid X=x})$, then this is a large-deviations event. The
probability $\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))$ thus decays
exponentially in $d$, i.e.,
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))=e^{-dE_{1}(v_{x,\tilde{x}})+\Theta(\log
d)}$, for some $E_{1}:\mathbb{R}\to[0,\infty)$, where by Sanov’s theorem (see
[17, Sec. 11.4]), we have that

$E_{1}(v_{x,\tilde{x}})=\min_{Q\colon L_{x,\tilde{x}}(Q)\leq
v_{x,\tilde{x}}}D(Q\mid\mid P_{Y\mid X=x}).$ (151)

We now aim to characterize this function $E_{1}$.

From convex duality (see [32, Sec. 5.2]), we obtain that

$E_{1}(v_{x,\tilde{x}})=\max_{\lambda\geq 0}\min_{Q}D(Q\mid\mid P_{Y\mid
X=x})+\lambda(L_{x,\tilde{x}}(Q)-v_{x,\tilde{x}}).$ (152)

First, let us solve the inner minimization. Fix $\lambda\geq 0$. Observe that
the term $f(\lambda,Q):=D(Q\mid\mid P_{Y\mid X=x})+\lambda L_{x,\tilde{x}}(Q)$
obeys

$\displaystyle f(\lambda,Q)$
$\displaystyle=\sum_{y}Q(y)\left(\log\frac{Q(y)}{P_{Y\mid X=x}(y)}+\lambda
L_{x,\tilde{x}}(y)\right)$ (153)
$\displaystyle=-\sum_{y}Q(y)\left(\log\frac{P_{Y\mid X=x}(y)}{Q(y)e^{\lambda
L_{x,\tilde{x}}(y)}}\right)$ (154)
$\displaystyle\geq-\log\sum_{y}\frac{P_{Y\mid X=x}(y)}{e^{\lambda
L_{x,\tilde{x}}(y)}},$ (155)

using Jensen’s inequality. Also note that equality holds when

$Q(y)=Q^{*}(y)=\frac{1}{Z_{x,\tilde{x}}(\lambda)}P_{Y\mid X=x}(y)e^{-\lambda
L_{x,\tilde{x}}(y)},$ (156)

where $Z_{x,\tilde{x}}(\lambda):=\sum_{y\in\mathcal{Y}}P_{Y\mid
X=x}(y)e^{-\lambda L_{x,\tilde{x}}(y)}$ is the partition function
(normalization constant). Substituting $Q^{*}$ back into the function results

$\displaystyle f(\lambda,Q^{*})$ $\displaystyle=-\log
Z_{x,\tilde{x}}(\lambda)-\lambda v_{x,\tilde{x}}$ (157)
$\displaystyle=-\log\left(\sum_{y}P_{Y\mid X=x}(y)e^{-\lambda
L_{x,\tilde{x}}(y)}\right)-\lambda v_{x,\tilde{x}}$ (158)
$\displaystyle=-\log\left(\sum_{y}P_{Y\mid X=x}^{1-\lambda}(y\mid x)P_{Y\mid
X}^{\lambda}(y\mid\tilde{x})\right)-\lambda v_{x,\tilde{x}}.$ (159)

Plugging back into (152), we get that

$\displaystyle E_{1}(v_{x,\tilde{x}})$ $\displaystyle=\max_{\lambda\geq
0}\Bigg{[}-\log\left(\sum_{y}P_{Y\mid X=x}^{1-\lambda}(y\mid x)P_{Y\mid
X}^{\lambda}(y\mid\tilde{x})\right)-\lambda v_{x,\tilde{x}}\Bigg{]}.$ (160)

Note that by setting $E(v_{x,\tilde{x}})=E_{1}(v_{x,\tilde{x}})$ when
$\min_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}\leq v_{x,\tilde{x}}\leq
L_{x,\tilde{x}}(P_{Y\mid X=x})$ and $E(v_{x,\tilde{x}})=\infty$ when
$v_{x,\tilde{x}}\leq\min_{b\in{\cal Y}}L_{x,\tilde{x}}^{b}$, we obtain a tight
characterization of the rate of exponential decay of
$\Gamma_{x,\tilde{x}}(z(v_{x,\tilde{x}}))$, in these ranges of
$v_{x,\tilde{x}}$. ∎

We now state a prove a lemma that will allow us to identify the exact rate of
exponential decay of $\mathsf{H}(X|Y^{d})$.

######  Lemma VII.2.

We have that

$\int_{0}^{\infty}\max_{\tilde{x}\neq
x}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z=e^{\Theta(\log d|\mathcal{X}|)}\cdot
e^{-d\cdot\min_{\tilde{x}\neq x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})}.$ (161)

###### Proof.

Consider an integral of the form

$\overline{I}=\int_{0}^{\infty}\max_{\tilde{x}\neq
x}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z.$ (162)

First, observe that

$\displaystyle\overline{I}$
$\displaystyle\leq\int_{0}^{\infty}\sum_{\tilde{x}\neq
x}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z$ (163)
$\displaystyle\leq|\mathcal{X}|^{2}\cdot\max_{\tilde{x}\neq
x}\int_{0}^{\infty}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z$ (164)
$\displaystyle=e^{\Theta(\log|\mathcal{X}|)}\cdot\max_{\tilde{x}\neq
x}\int_{0}^{\infty}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z.$ (165)

Further,

$\displaystyle\overline{I}$ $\displaystyle\geq\max_{\tilde{x}\neq
x}\int_{0}^{\infty}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z.$ (166)

Hence, overall, we have that
$\overline{I}=\text{exp}(\Theta(\log|\mathcal{X}|))\cdot\max_{\tilde{x}\neq
x}\int_{0}^{\infty}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z$. We next focus on the
integral

$I=\int_{0}^{\infty}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z,$ (167)

for a fixed $x,\tilde{x}$.

By the definition

$v_{x,\tilde{x}}=v_{x,\tilde{x}}(z)=\frac{1}{d}\left(\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(x^{\prime})}\right),$
(168)

and from Prop. VII.1, we see that the integral $I$ can be split into two
integrals for its evaluation: integral $I_{1}$, when

$z\leq\log\left(1+\frac{cP(\tilde{x})}{P(x)}\cdot
e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)}\right):=u(d),$ (169)

or equivalently, when $v_{x,\tilde{x}}\geq L_{x,\tilde{x}}({P_{Y|x}})+\delta$,
and integral $I_{2}$, when

$z\geq\log\left(1+\frac{cP(\tilde{x})}{P(x)}\cdot
e^{-d(L_{x,\tilde{x}}(P_{Y|x})-\delta)}\right):=\ell(d),$ (170)

or equivalently, when $v_{x,\tilde{x}}\leq L_{x,\tilde{x}}({P_{Y|x}})-\delta$,
with $I=I_{1}+I_{2}$. Here, we pick $\delta<L_{x,\tilde{x}}({P_{Y|x}})$.

Consider first the integral $I_{1}$. We have that

$\displaystyle I_{1}$ $\displaystyle=\int_{z\leq
u(d)}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z$ (171) $\displaystyle=\Theta(1)\cdot
u(d).$ (172)

Now, we claim that $u(d)=e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)}$. To see
this, let $\tilde{c}:=\frac{cP(\tilde{x})}{P(x)}$ and recall that
$\frac{t}{1+t}\leq\log(1+t)\leq t$, for $t>-1$. Hence, we have that

$u(d)\leq\tilde{c}e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)},$ (173)

and

$u(d)\geq\frac{\tilde{c}e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)}}{1+\tilde{c}e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)}}\geq\frac{\tilde{c}}{2}\cdot
e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)},$ (174)

since $L_{x,\tilde{x}}({P_{Y|x}})=D(P_{Y|x}||P_{Y|\tilde{x}})>0$. Hence,
overall, we have that for any fixed $\delta>0$,

$I_{1}=e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)+\Theta(1)}.$ (175)

Taking the limit as $\delta\downarrow 0$, we get that

$I_{1}=e^{-dL_{x,\tilde{x}}(P_{Y|x})+\Theta(1)}=e^{-d\cdot
D(P_{Y|x}||P_{Y|\tilde{x}})+\Theta(1)}.$ (176)

Consider now the integral $I_{2}$. Note that from case 2) in Prop. VII.1, when
$z\geq\log\left(1+\tilde{c}e^{-d\cdot\min_{b}L_{x,\tilde{x}}^{b}}\right):=U(d)$,
we have that $I_{2}=0$. Hence, we can write

$I_{2}=\int_{\ell(d)\leq z\leq U(d)}\Gamma_{x,\tilde{x}}(z)\mathrm{d}z,$ (177)

where, for this interval $\ell(d)\leq z\leq U(d)$ of interest,

$\Gamma_{x,\tilde{x}}(z)=e^{-d{E}(v_{x,\tilde{x}}(z))+\Theta(\log d)},$ (178)

with

${E}(v_{x,\tilde{x}}(z))=\max_{\lambda\geq
0}\left[-\log\left(\sum_{y}P(y|x)^{1-\lambda}P(y|x^{\prime})^{\lambda}\right)-\lambda
v_{x,\tilde{x}}\right],$ (179)

from Prop. VII.1.

It is clear that $E(v_{x,\tilde{x}}(z))$ increases as $v_{x,\tilde{x}}$
decreases. In the integral $I_{2}$, we thus make the change of variables

$v=\frac{1}{d}\left(\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(x^{\prime})}\right),$
(180)

with $\mathrm{d}z=\frac{-dce^{-dv}}{1+ce^{-dv}}\mathrm{d}v$. Thus,

$\displaystyle I_{2}$
$\displaystyle=dc\int^{L_{x,\tilde{x}}(P_{Y|x})-\delta}_{v=\min_{b}L_{x,\tilde{x}}^{b}}e^{-dE(v)}\cdot\frac{e^{-dv}}{1+ce^{-dv}}\mathrm{d}v$
(181)
$\displaystyle=dc\int^{L_{x,\tilde{x}}(P_{Y|x})-\delta}_{v=0}e^{-dE(v)}\cdot\frac{e^{-dv}}{1+ce^{-dv}}\mathrm{d}v+dc\int^{0}_{v=\min_{b}L_{x,\tilde{x}}^{b}}e^{-dE(v)}\cdot\frac{e^{-dv}}{1+ce^{-dv}}\mathrm{d}v.$
(182)

Let us call the first integral in the expansion above as $I_{2,a}$ and the
second as $I_{2,b}$ (note that $\min_{b}L_{x,\tilde{x}}^{b}\leq 0$). Now,
observe that

$\displaystyle I_{2,a}$
$\displaystyle=dc\int^{L_{x,\tilde{x}}(P_{Y|x})-\delta}_{v=0}e^{-dE(v)}\cdot{e^{-dv+\Theta(\log
d)}}dv$ (183)
$\displaystyle=\text{exp}(-d(E(L_{x,\tilde{x}}(P_{Y|x}))+L_{x,\tilde{x}}(P_{Y|x})-\delta)+\Theta(\log
d)).$ (184)

Here, in the first eqauility, we argue as previously that

$\frac{e^{-dv}}{1+ce^{-dv}}=e^{-dv+\Theta(1)}.$ (185)

Furthermore, the second equation follows from Laplace’s method (e.g., see [27,
Sec. 4.2]), using the fact that both $e^{-dE(v)}$ and $e^{-dv}$ increase as
$v$ increases. Taking $\delta\downarrow 0$, we obtain that

$I_{2,a}=e^{-d(E(L_{x,\tilde{x}}(P_{Y|x}))+L_{x,\tilde{x}}(P_{Y|x}))+\Theta(\log
d)}.$ (186)

Moreover,

$\displaystyle I_{2,b}$ $\displaystyle=e^{\Theta(\log
d)}\cdot\int^{0}_{v=\min_{b}L_{x,\tilde{x}}^{b}}e^{-dE(v)}\mathrm{d}v$ (187)
$\displaystyle=e^{-dE(0)+\Theta(\log
d)}=e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d)}.$ (188)

Here, for the first equality, we use the fact that when $v\leq 0$,

$\frac{1}{2}\leq\frac{e^{-dv}}{1+ce^{-dv}}\leq\frac{1}{c},$ (189)

and hence $\frac{e^{-dv}}{1+ce^{-dv}}=\Theta(1)$. The second equality holds
again by Laplace’s method, using the fact that $e^{-dE(v)}$ increases with
$v$.

Putting everything together, in order to nail down the exponential behaviour
of integral $I$, we need to reconcile Equations (176), (186), and (188), to
understand which among $I_{1}$, $I_{2,a}$, and $I_{2,b}$, is the largest.
First, observe that since

$\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})\leq D(P_{Y|x}||P_{Y|\tilde{x}}),$ (190)

we have that $I_{2,b}$ dominates $I_{1}$.

Therefore, the exponential behaviour of integral $I$ is governed by the rate

$\overline{E}=\min\left\\{E(L_{x,\tilde{x}}(P_{Y|x}))+L_{x,\tilde{x}}(P_{Y|x}),\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})\right\\}.$
(191)

Now note that the maximum over $\lambda\geq 0$ in the expressions for $E$ and
$\mathsf{C}$ can be rewritten as a maximum over $\lambda\in[0,1]$ (owing to
the concavity of
$-\log\left(\sum_{y}P(y|x)^{1-\lambda}P(y|x^{\prime})^{\lambda}\right)$ and
the fact that it equals $0$ at $\lambda=0,1$). We then get that

$E(L_{x,\tilde{x}}(P_{Y|x}))+L_{x,\tilde{x}}(P_{Y|x})\geq\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}}),$
(192)

implying that $\overline{E}=\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})$. Therefore,

$I=e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d)},$ (193)

and hence that

$\overline{I}=\max_{\tilde{x}\neq
x}\text{exp}({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d)+\Theta(\log|\mathcal{X}|)}).$ (194)

∎

We are now ready to prove Theorem III.1 for the convergence of the mutual
information.

###### Proof of Thm. III.1 for mutual information.

Recall from Lemma VII.1 that

$p_{x}(t)\leq(|\mathcal{X}|-1)\cdot\max_{\tilde{x}\neq
x}\Gamma_{x,\tilde{x}}(t),$ (195)

with the constant $c$ in the definition of $\Gamma_{x,\tilde{x}}(t)$ taken to
be $|\mathcal{X}|-1$. Thus, from Lemma VII.2 and (126), we get that

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]$
$\displaystyle=\int_{0}^{\infty}p_{x}(t)\mathrm{d}t$ (196)
$\displaystyle\leq\text{exp}\left({-d\cdot\min_{\tilde{x}\neq
x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d|\mathcal{X}|)}\right),$
(197)

where the inequality holds by the Laplace method [27, Sec. 4.2]. Similarly,
since

$p_{x}(t)\geq\max_{\tilde{x}\neq x}\Gamma_{x,\tilde{x}}(t),$ (198)

with the constant $c$ in the definition of $\Gamma_{x,\tilde{x}}(t)$ taken to
be $1$, we get that

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]$
$\displaystyle\geq\text{exp}\left({-d\cdot\min_{\tilde{x}\neq
x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d|\mathcal{X}|)}\right).$
(199)

Thus,

$\displaystyle\mathbb{E}\left[\log\frac{1}{P_{X\mid Y^{d}}(x\mid
Y^{d})}\Bigg{\lvert}X=x\right]$
$\displaystyle=\text{exp}\left({-d\cdot\min_{\tilde{x}\neq
x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d|\mathcal{X}|)}\right).$
(200)

Plugging back in (125), we obtain that

$\mathsf{H}(X|Y^{d})=\max_{\begin{subarray}{c}x,\tilde{x}:\tilde{x}\neq
x\end{subarray}}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right),$ (201)

yielding the required result. ∎

###  VII-B Convergence of Channel Dispersion of DMCs

We now shift our attention to proving the convergence of the dispersion
$V^{(d)}=\mathbb{E}\left[\left(\iota(X;Y^{d})-I(X;Y^{d})\right)^{2}\right]$,
to the varentropy $\mathsf{V}(X)$ of the input distribution $P_{X}$, for
general DMCs $W$.

First, we write

$\displaystyle V^{(d)}$
$\displaystyle=\mathbb{E}\left[\left(\log\frac{P(X|Y^{d})}{P(X)}-\left(\mathsf{H}(X)-\mathsf{H}(X|Y^{d})\right)\right)^{2}\right]$
(202)
$\displaystyle=\mathbb{E}\left[\left(\log\frac{1}{P(X)}-\mathsf{H}(X)\right)^{2}\right]+\mathbb{E}\left[\left(\log
P(X|Y^{d})+\mathsf{H}(X|Y^{d})\right)^{2}\right]$ $\displaystyle\ \ \
+2\cdot\mathbb{E}\left[(\log
P(X|Y^{d})+\mathsf{H}(X|Y^{d}))\cdot\left(\log\frac{1}{P(X)}-\mathsf{H}(X)\right)\right]$
(203) $\displaystyle=\mathsf{V}(X)+\left(\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\right]-\mathsf{H}(X|Y^{d})^{2}\right)+\theta_{d},$ (204)

where we use the fact that $\mathbb{E}\left[-\log
P(X|Y^{d})\right]=\mathsf{H}(X|Y^{d})$, and the cross-term $\theta_{d}$ is

$2\cdot\mathbb{E}\left[(\log
P(X|Y^{d})+\mathsf{H}(X|Y^{d}))\cdot\left(\log\frac{1}{P(X)}-\mathsf{H}(X)\right)\right].$
(205)

Further, observe that when $P_{X}=\text{Unif}(\mathcal{X})$, the cross term
vanishes, since for any $x\in\mathcal{X}$, we have that
$\log\frac{1}{P(x)}=\log|\mathcal{X}|=\mathsf{H}(X)$. Our proof strategy hence
is to first characterize (up to exponential tightness) the behaviour of
$\mathbb{E}\left[\left(\log P(X|Y^{d})\right)^{2}\right]$ and then handle the
cross-term $\theta_{d}$.

######  Lemma VII.3.

We have that

$\mathbb{E}\left[\left(\log P(X|Y^{d})\right)^{2}\right]=e^{\Theta(\log
d|\mathcal{X}|)}\cdot\max_{x,\tilde{x}:\tilde{x}\neq
x}e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})}.$ (206)

###### Proof.

This proof is entirely analogous to the proof of convergence of $I^{(d)}$ to
$\mathsf{H}(X)$, for general DMCs, in Section VII-A, and we only highlight the
key steps.

We first consider the term $\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\right]$. As in (125), we first expand this term as:

$\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\right]=\sum_{x\in\mathcal{X}}P(x)\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\Bigg{\lvert}X=x\right],$ (207)

where for any $x\in\mathcal{X}$, we have

$\displaystyle\mathbb{E}\left[\left(\log
P(x|Y^{d})\right)^{2}\Bigg{\lvert}X=x\right]$
$\displaystyle=\int_{t=0}^{\infty}\Pr\left[\left(\log
P(x|Y^{d})\right)^{2}\geq t\Bigg{\lvert}X=x\right]\mathrm{d}t$ (208)
$\displaystyle=\int_{t=0}^{\infty}\mathbb{P}\left[\log
P(x|Y^{d})\geq\sqrt{t}\Big{\lvert}X=x\right]\mathrm{d}t+\int_{t=0}^{\infty}\mathbb{P}\left[\log
P(x|Y^{d})\leq-\sqrt{t}\Big{\lvert}X=x\right]\mathrm{d}t$ (209)
$\displaystyle=\int_{t=0}^{\infty}\mathbb{P}\left[\log
P(x|Y^{d})\leq-\sqrt{t}\Big{\lvert}X=x\right]\mathrm{d}t.$ (210)

Here, the last equality holds since $P(x|Y^{d})\leq 1$, for any
$Y^{d}\in\mathcal{Y}^{d}$. As earlier, our task reduces to understanding the
exponential behaviour of

$q_{x}(t):=\Pr\left[\log P(x|Y^{d})\leq-\sqrt{t}\Big{\lvert}X=x\right].$ (211)

Exactly as in Lemma VII.1, we have that

$\displaystyle\frac{q_{x}(t)}{(|{\cal X}|-1)}$
$\displaystyle\leq\max_{\tilde{x}\neq x}\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-(\sqrt{t}-\log(|{\cal
X}|-1))}}{1-e^{-\sqrt{t}}}\Bigg{\lvert}X=x\right],$ (212)

and

$q_{x}(t)\geq\max_{\tilde{x}\neq x}\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{e^{-\sqrt{t}}}{1-e^{-\sqrt{t}}}\Bigg{\lvert}X=x\right].$
(213)

Consider, for a fixed $c>0$ and $z\in[0,\infty)$, the expression

$\Delta_{x,\tilde{x}}(z):=\mathbb{P}\left[\frac{P(x)P(Y^{d}\mid
x)}{P(\tilde{x})P(Y^{d}\mid\tilde{x})}\leq\frac{ce^{-\sqrt{z}}}{1-e^{-\sqrt{z}}}\Bigg{\lvert}X=x\right].$
(214)

As argued in the case of the mutual information, the rate of exponential decay
of $\Delta_{x,\tilde{x}}(z)$, as a function of $z$, dictates the rate of
exponential decay of $q_{x}(t)$, and hence of $\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\right]$. Once again, letting

$v_{x,\tilde{x}}=v_{x,\tilde{x}}(z)=\frac{1}{d}\left(\log\left(\frac{ce^{-z}}{1-e^{-z}}\right)-\log\frac{P(x)}{P(x^{\prime})}\right)$
(215)

and setting
$(z(v_{x,\tilde{x}}))^{1/2}:=\log\left(1+\frac{cP(\tilde{x})}{P(x)\cdot}e^{-dv_{x,\tilde{x}}}\right)$,
we obtain a result similar to Proposition VII.1, with the only modification
being the replacement of $\Gamma_{x,\tilde{x}}$ by $\Delta_{x,\tilde{x}}$.

Next, as in Lemma VII.2, consider the integral

$\overline{I}^{V}=\int_{0}^{\infty}\max_{\tilde{x}\neq
x}\Delta_{x,\tilde{x}}(z)\mathrm{d}z.$ (216)

We claim that

$\overline{I}^{V}=e^{\Theta(\log d)+\Theta(\log|\mathcal{X}|)}\cdot
e^{-d\min_{\tilde{x}\neq x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})}.$ (217)

To obtain this, we argue as in the proof of Lemma VII.2 that
$\overline{I}^{V}=e^{\Theta(\log|\mathcal{X}|)}\cdot\max_{\tilde{x}\neq
x}I^{V}$, where

$I^{V}=\int_{0}^{\infty}\Delta_{x,\tilde{x}}(z)\mathrm{d}z,$ (218)

for a fixed $x,\tilde{x}$.

Now, we split the evaluation of $I^{V}$ into two integrals: integral
$I_{1}^{V}$, when

$z\leq\left(\log\left(1+\frac{cP(\tilde{x})}{P(x)}\cdot
e^{-d(L_{x,\tilde{x}}(P_{Y|x})+\delta)}\right)\right)^{2},$ (219)

and integral $I_{2}^{V}$, when

$z\geq\left(\log\left(1+\frac{cP(\tilde{x})}{P(x)}\cdot
e^{-d(L_{x,\tilde{x}}(P_{Y|x})-\delta)}\right)\right)^{2},$ (220)

with $I^{V}=I_{1}^{V}+I_{2}^{V}$. By arguments analogous to those in the proof
of Lemma VII.2, we obtain that

$I_{1}^{V}=e^{-2d\cdot D(P_{Y|x}||P_{Y|\tilde{x}})+\Theta(\log d)},$ (221)

and

$I_{2}^{V}=e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d)}.$
(222)

Thus, we have that

$I^{V}=e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d)},$ (223)

and hence that

$\overline{I}^{V}=\text{exp}\left({-d\cdot\min_{\tilde{x}\neq
x}\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log d|\mathcal{X}|)}\right).$
(224)

Putting everything together, we get that

$\displaystyle\mathbb{E}\left[\left(\log P(X|Y^{d})\right)^{2}\right]$
$\displaystyle=\max_{x,\tilde{x}:\tilde{x}\neq
x}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right).$ (225)

∎

######  Lemma VII.4.

We have that

$\theta_{d}=e^{\Theta(\log
d|\mathcal{X}|)}\cdot\max_{x,\tilde{x}:\tilde{x}\neq
x}e^{-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})}.$ (226)

###### Proof.

Recall the cross term

$\theta_{d}:=2\cdot\mathbb{E}\left[(\log
P(X|Y^{d})+\mathsf{H}(X|Y^{d}))\cdot\left(\log\frac{1}{P(X)}-\mathsf{H}(X)\right)\right].$
(227)

We then write

$\displaystyle\theta_{d}(x)$
$\displaystyle:=\left(\log\frac{1}{P(x)}-\mathsf{H}(X)\right)\cdot\left(\mathbb{E}\left[\log
P(x|Y^{d})\Big{\lvert}X=x\right]+\mathsf{H}(X|Y^{d})\right),$ (228)

with $\theta_{d}=\sum_{x\in\mathcal{X}}P(x)\theta_{d}(x)$. From the capacity
analysis, we know that (see (126))

$\displaystyle\mathbb{E}\left[\log P(x|Y^{d})\Big{\lvert}X=x\right]$
$\displaystyle=-\max_{x^{\prime}\neq
x}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right).$ (229)

From our previous analysis, we know that

$\mathsf{H}(X|Y^{d})=\max_{x,x^{\prime}:x^{\prime}\neq
x}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right).$ (230)

Hence,

$\displaystyle\theta_{d}$ $\displaystyle=e^{\Theta(\log
d)}\cdot\theta_{d}(x)=\max_{x,x^{\prime}:x\neq
x^{\prime}}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right).$ (231)

∎

With these lemmas in place, the proof of Theorem is easily completed.

###### Proof of Thm. III.1 for dispersion.

From (204) we see that

$V^{(d)}-\mathsf{V}(X)=\mathbb{E}\left[\left(\log
P(X|Y^{d})\right)^{2}\right]-\mathsf{H}(X|Y^{d})^{2}+\theta_{d}.$ (232)

Putting together Lemmas VII.3 and VII.4 and the fact that

$\mathsf{H}(X|Y^{d})=\max_{\begin{subarray}{c}x,x^{\prime}:x^{\prime}\neq
x\end{subarray}}\text{exp}\left({-d\cdot\mathsf{C}(P_{Y|x},P_{Y|\tilde{x}})+\Theta(\log
d|\mathcal{X}|)}\right)$ (233)

(from the proof of Thm. III.1 for mutual information), we readily obtain the
required result. ∎

##  VIII Conclusion and Future Work

In this paper, we considered the behaviour of the information rate and channel
dispersion of multi-view noisy channels, with arbitrary, but fixed, input
distributions, in the regime where the number of views is very large. In the
first part of the paper, we considered multi-view discrete memoryless channels
(DMCs), and showed that the information rate and the channel dispersion
converge exponentially quickly to the input entropy and varentropy,
respectively, with an input distribution-independent rate that equals the
smallest Chernoff information between two conditional distributions of the
output given different inputs. We then extended these results to general
multi-letter channels, and computed explicit upper bounds on the Chernoff
information above for the deletion channel. Finally, for the special case of
the multi-view binary symmetric channel, we also presented a close, non-
asymptotic approximation to its capacity, via the capacity of the so-called
Poisson approximation channel.

One interesting direction for future work would be the extension of the
techniques and results in this paper to other multi-view channels with memory
and general synchronization channels (see [33] and [3, Sec. VII]).

## References

  * [1] V. Levenshtein, “Efficient reconstruction of sequences,” _IEEE Transactions on Information Theory_ , vol. 47, no. 1, pp. 2–22, 2001.
  * [2] C. Shannon, R. Gallager, and E. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I,” _Information and Control_ , vol. 10, no. 1, pp. 65–103, 1967. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019995867900526
  * [3] M. Cheraghchi and J. Ribeiro, “An overview of capacity results for synchronization channels,” _IEEE Transactions on Information Theory_ , vol. 67, no. 6, pp. 3207–3232, 2021.
  * [4] R. Heckel, G. Mikutis, and R. N. Grass, “A characterization of the DNA data storage channel,” _Scientific Reports_ , vol. 9, 2018. [Online]. Available: https://api.semanticscholar.org/CorpusID:4743189
  * [5] I. Shomorony and R. Heckel, “Information-theoretic foundations of DNA data storage,” _Foundations and Trends® in Communications and Information Theory_ , vol. 19, no. 1, pp. 1–106, 2022. [Online]. Available: http://dx.doi.org/10.1561/0100000117
  * [6] N. Weinberger, “Error probability bounds for coded-index DNA storage systems,” _IEEE Transactions on Information Theory_ , vol. 68, no. 11, pp. 7005–7022, 2022.
  * [7] N. Weinberger and N. Merhav, “The DNA storage channel: Capacity and error probability bounds,” _IEEE Transactions on Information Theory_ , vol. 68, no. 9, pp. 5657–5700, 2022.
  * [8] M. Kovačević and V. Y. F. Tan, “Codes in the space of multisets—coding for permutation channels with impairments,” _IEEE Transactions on Information Theory_ , vol. 64, no. 7, pp. 5156–5169, 2018.
  * [9] A. Lenz, P. H. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Coding over sets for DNA storage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2331–2351, 2020.
  * [10] R. Gabrys, H. M. Kiah, and O. Milenkovic, “Asymmetric Lee distance codes: New bounds and constructions,” in _2015 IEEE Information Theory Workshop (ITW)_ , 2015, pp. 1–5.
  * [11] M. Mitzenmacher, “On the theory and practice of data recovery with multiple versions,” in _2006 IEEE International Symposium on Information Theory_ , 2006, pp. 982–986.
  * [12] I. Land and J. Huber, “Information combining,” _Foundations and Trends® in Communications and Information Theory_ , vol. 3, no. 3, pp. 227–330, 2006. [Online]. Available: http://dx.doi.org/10.1561/0100000013
  * [13] I. Sutskover, S. Shamai, and J. Ziv, “Extremes of information combining,” _IEEE Transactions on Information Theory_ , vol. 51, no. 4, pp. 1313–1325, 2005.
  * [14] T. Batu, S. Kannan, S. Khanna, and A. McGregor, “Reconstructing strings from random traces,” in _Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , ser. SODA ’04. USA: Society for Industrial and Applied Mathematics, 2004, p. 910–918.
  * [15] M. Cheraghchi, R. Gabrys, O. Milenkovic, and J. Ribeiro, “Coded trace reconstruction,” _IEEE Transactions on Information Theory_ , vol. 66, no. 10, pp. 6084–6103, 2020.
  * [16] Y. Peres and A. Zhai, “Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice,” in _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2017, pp. 228–239.
  * [17] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. Wiley-India, 2010.
  * [18] C. E. Shannon, “A mathematical theory of communication,” _Bell Systems Technical Journal_ , vol. 27, no. 3, pp. 379–423, July 1948.
  * [19] R. G. Gallager, _Stochastic Processes: Theory for Applications_. Cambridge: Cambridge University Press, 2013.
  * [20] T. Richardson and R. Urbanke, _Modern Coding Theory_. Cambridge University Press, 2008.
  * [21] A. Guillen i Fabregas, I. Land, and A. Martinez, “Extremes of error exponents,” _IEEE Transactions on Information Theory_ , vol. 59, no. 4, pp. 2201–2207, 2013.
  * [22] Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel coding rate in the finite blocklength regime,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [23] V. Y. F. Tan, “Asymptotic estimates in information theory with non-vanishing error probabilities,” _Foundations and Trends® in Communications and Information Theory_ , vol. 11, no. 1-2, pp. 1–184, 2014. [Online]. Available: http://dx.doi.org/10.1561/0100000086
  * [24] Y. Polyanskiy and Y. Wu, _Information Theory: From Coding to Learning_. Cambridge University Press, 2023+ (_book draft_).
  * [25] I. Land, S. Huettinger, P. Hoeher, and J. Huber, “Bounds on information combining,” _IEEE Transactions on Information Theory_ , vol. 51, no. 2, pp. 612–619, 2005.
  * [26] E. Şaşoğlu, “Polarization and polar codes,” _Foundations and Trends® in Communications and Information Theory_ , vol. 8, no. 4, pp. 259–381, 2012. [Online]. Available: http://dx.doi.org/10.1561/0100000041
  * [27] N. Merhav, “Statistical physics and information theory,” _Foundations and Trends® in Communications and Information Theory_ , vol. 6, no. 1–2, pp. 1–212, 2010. [Online]. Available: http://dx.doi.org/10.1561/0100000052
  * [28] Z. Zhou and P. Li, “Non-asymptotic Chernoff lower bound and its application to community detection in stochastic block model,” _arXiv e-prints_ , p. arXiv:1812.11269, Dec. 2018.
  * [29] W. Koepf, _Hypergeometric Summation An Algorithmic Approach to Summation and Special Function Identities_. Vieweg, 1998.
  * [30] J. Spencer, _Asymptopia_. American Mathematical Society, 2014.
  * [31] R. D. Wesel, E. E. Wesel, L. Vandenberghe, C. Komninakis, and M. Medard, “Efficient binomial channel capacity computation with an application to molecular communication,” in _2018 Information Theory and Applications Workshop (ITA)_ , 2018, pp. 1–5.
  * [32] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge: Cambridge University Press, 2004.
  * [33] B. Haeupler and M. Mitzenmacher, “Repeated deletion channels,” in _2014 IEEE Information Theory Workshop (ITW 2014)_ , 2014, pp. 152–156.