# The Capacity of Causal Adversarial Channels

Yihan Zhang, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate Y. Zhang is
with the Institute of Science and Technology Austria, Vienna, Austria,
<EMAIL_ADDRESS>S. Jaggi is with the University of Bristol, Bristol,
UK<EMAIL_ADDRESS>Michael Langberg is with the University at
Buffalo, Buffalo, NY, USA<EMAIL_ADDRESS>Anand D. Sarwate is with
Rutgers, The State University of New Jersey, Piscataway, NJ, USA,
<EMAIL_ADDRESS>The work of ADS and ML was supported in part by the
US National Science Foundation under awards CCF-1909468 and CCF-1909451.

###### Abstract

We characterize the capacity for the discrete-time arbitrarily varying channel
with discrete inputs, outputs, and states when (a) the encoder and decoder do
not share common randomness, (b) the input and state are subject to cost
constraints, (c) the transition matrix of the channel is deterministic given
the state, and (d) at each time step the adversary can only observe the
current and past channel inputs when choosing the state at that time. The
achievable strategy involves stochastic encoding together with list decoding
and a disambiguation step. The converse uses a two-phase “babble-and-push”
strategy where the adversary chooses the state randomly in the first phase,
list decodes the output, and then chooses state inputs to symmetrize the
channel in the second phase. These results generalize prior work on specific
channels models (additive, erasure) to general discrete alphabets and models.

###### Contents

  1. I Introduction
  2. II Proof skecth
  3. III Model
    1. III-A Channels and codes
    2. III-B State-deterministic AVCs
  4. IV Capacity charatcterization
    1. IV-A Symmetrizing distributions
  5. V Proof of achievability (Theorem 1)
    1. V-A Determining a $P_{{\mathbf{x}}|{\mathbf{u}}}$ for code design
    2. V-B Code construction
    3. V-C Encoding
    4. V-D Decoding
    5. V-E Analysis
      1. V-E1 Code properties
      2. V-E2 Decoding analysis
  6. VI Converse
  7. VII Proof of converse (Theorem 10)
    1. VII-A Babble-only attack
    2. VII-B Babble-and-push attack
      1. VII-B1 Division point and jamming distributions
      2. VII-B2 DMC attack in the prefix
      3. VII-B3 Posterior distribution
      4. VII-B4 Symmetrization in the suffix
    3. VII-C Analysis of the babble-only attack
    4. VII-D Analysis of the babble-and-push attack
  8. A Basic tools

##  I Introduction

In introductory courses on information theory and coding theory students
encounter two basic models for communication channels. The Shannon-theoretic
model [Sha48] for memoryless channels treats the effect of the channel as
random, where each input symbol is transformed to an output symbol through the
same conditional distribution at each time step. Two canonical examples are
the binary symmetric channel (BSC) and binary erasure channel (BEC). With high
probability, for sufficiently large $n$, a BSC flips close to $pn$ bits for a
codeword of blocklength $n$ and the probability of error is _average-case_ ,
measured over the randomness in the channel. By contrast, in the basic coding
theory model, errors and erasures are modeled as _worst-case_ : for a
blocklength $n$ the goal is to design a code which can correct any pattern of
$pn$ errors or erasures.

One way to understand the difference between these models is to frame them
both in the context of arbitrarily varying channels (AVCs) [BBT60] under
constraints [CN88a, CN88b]. In the AVC there are three participants: Alice
(the transmitter/encoder), Bob (the receiver/decoder), and James (an
adversarial jammer). When communicating over an AVC, Alice encodes her message
into a codeword ${\underline{x}}$ of blocklength $n$ and James can choose an
equal-length vector of channel states ${\underline{s}}$. The output
${\underline{y}}$ is formed by applying a channel law
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)$ letter-by-letter to
$({\underline{x}},{\underline{s}})$. The difference between the two classical
communication models can be captured by modeling the information James has
about the transmitted codeword. The Shannon-theoretic model is similar to an
_oblivious adversary_ who must choose ${\underline{s}}$ without any knowledge
of ${\underline{x}}$. The coding-theoretic model is similar to a _omniscient
adversary_ in which James can choose ${\underline{s}}$ as a function of the
entire codeword ${\underline{x}}$.

Once we frame the difference between average and worst case models in terms of
the AVC, a variety of “intermediate case” models become natural by changing
what James can know about the transmitted codeword. In this paper we consider
one such model: the _causal (or online) adversary_ in which James chooses the
channel state ${\underline{s}}(t)$ at time $t$ based on knowledge of the
current and past inputs
$({\underline{x}}(1),{\underline{x}}(2),\ldots,{\underline{x}}(t))$. The
online adversary is a special case of the _delayed adversary_ [LJD09, DJLS10].

Much of the prior work on causal adversaries deals with specific channel
models. Capacity results for special cases of causal adversaries with “large
alphabets” [DJL13], the erasure setting [BS14, CJL15, CJL19], the bit-
flip/symbol-error setting [DJLS13, CJL19], and the quadratically-constrained
scenario [LDJ+18] are known. Other related channel models explored include
settings with a memoryless jammer [Maz14], and bit-flip and erasure models in
which the channel is not state-deterministic but James can observe the channel
output [SRL21].

In this work we focus on AVCs with finite input, state, and output alphabets
which are _state-deterministic_ , meaning the the channel output
${\underline{y}}(t)$ at each time $t$ is a deterministic function of
${\underline{x}}(t)$ and ${\underline{s}}(t)$. In such models, James can
compute the channel output. Our goal is to establish capacity results for
general state-deterministic AVC models with cost constraints.

After defining our model in Section III, and key concepts in Section IV, we
present an overview of our capacity analysis in Section II. At a high level,
both our achievability and converse proofs follow those appearing in [DJLS13,
CJL19] addressing the causal bit-flip/symbol-error setting. The main technical
contribution in this work thus lies in the highly non-trivial nature of
expanding the concepts and analysis in [DJLS13, CJL19] to fit the generalized
model of AVCs with both state and input constraints. We highlight the major
challenges of analyzing general AVCs and the tools used to overcome these
challenges in the overview of Section II.

##  II Proof skecth

The converse argument, broadly speaking, generalizes the two-phase “babble-
and-push” jamming strategy and analysis introduced in [DJLS13, CJL19] in the
bit-flip/symbol-error setting, with some novelties required for the general
setting. In particular the recently developed Generalized Plotkin bound
[WBBJ19] plays a critical role, since via combinatorial arguments it
guarantees that regardless of Alice’s encoding strategy, with positive
probability the joint type of randomly sampled pairs of codeword suffixes will
fall within a restricted range (just as the classical Plotkin bound for binary
codes can be used to argue that for any code of positive rate, for any
$\varepsilon>0$ the Hamming distance of a randomly chosen pair of codewords
does not exceed $\frac{n}{2}(1+\varepsilon)$ with probability
$\Omega(\varepsilon)$). In particular, the Generalized Plotkin bound ensures
that with positive probability the joint type of a randomly sampled pairs of
codewords (or, in the converse argument here, randomly sampled codeword
suffixes) is a convex combination of product distributions. The implication of
these types of bounds is that if James just wishes his attack to work with
positive probability bounded away from zero, rather than probability 1, then
in general he can use a significantly less costly state sequence (just as in
the binary setting, with probability $\Omega(\varepsilon)$ he only needs to
flip about $\frac{n}{4}(1+\varepsilon)$ bits to confuse Bob between the truly
transmitted codeword and some other codeword which differ in
$\frac{n}{2}(1+\varepsilon)$ bits, rather than $\frac{n}{2}$ as in the worst-
case when the two codewords differ in every bit).

Let $\varepsilon$ be an arbitrarily small positive constant that will help
specify various slack parameters in what follows. In particular, James’ attack
strategy operates on consecutive length-$\varepsilon n$ chunks of Alice’s
codewords, and hence operates on $K=1/\varepsilon$ chunks. In James’ attack
below, summarized first for the special case when Alice employs a
deterministic coding strategy (i.e., her transmission is a deterministic
function of the message she wishes to transmit to Bob). Steps 1 and 2
correspond to James analyzing Alice and Bob’s chosen codebook ${\mathcal{C}}$
prior to transmission, and steps 3 and 4 comprise respectively the babble and
push phases during the actual transmission.

  1. 1.

Sub-code extraction: First, given Alice’s codebook ${{\mathcal{C}}}$ of rate
$R$, James finds a subcode ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$
which has both the following two properties:

    1. (a)

The subcode ${\mathcal{C}}^{\prime}$ contains a constant fraction of the
codewords in ${\mathcal{C}}$, and

    2. (b)

Each codeword in ${\mathcal{C}}^{\prime}$ is chunk-wise $\delta$-approximately
constant composition, i.e., for each codeword
${\underline{x}}\in{\mathcal{C}}^{\prime}$ and each chunk with index
$u\in\\{1,\ldots,K\\}$, the $u$-th chunk-wise type of ${\underline{x}}$,
denoted $T_{{\underline{x}}^{(u)}}$ and defined as the type of
${\underline{x}}$ restricted to symbols in the $u$-th chunk, differs in the
$\ell_{\infty}$ norm from a given distribution
$P_{{\mathbf{x}}|{\mathbf{u}}=u}$ by at most $\delta$.

Such a sub-code can always be extracted for the following reason. There are
$1/\epsilon$ chunks, and so the simplex of all possible chunkwise-types of a
length-$n$ code can be $\delta$-approximated by a $\delta$-net with
${\mathcal{O}}((1/\delta)^{|{\mathcal{X}}|/\epsilon})$ elements. Hence picking
the cell of the $\delta$-net with the most codewords in it gives us the
subcode ${\mathcal{C}}^{\prime}$ with a constant fraction (at least
$\Omega(\delta^{|{\mathcal{X}}|/\epsilon})$-fraction) of the codewords in
${\mathcal{C}}$. Let this cell correspond to the set
$\\{P_{{\mathbf{x}}|{\mathbf{u}}=u}\\}_{u=1}^{K}$ of distributions. Going
forward, James’ attack is only guaranteed to succeed with positive probability
for codewords ${\underline{x}}\in{\mathcal{C}}^{\prime}$. Despite this
restriction, due to (b), this nonetheless happens with strictly positive
probability, bounded away from zero independently of the blocklength $n$.

  2. 2.

Choice of attack parameter/jamming distributions: James then simultaneously
selects a prefix-length parameter $\alpha\leq 1$ (w.l.o.g. it is assumed that
$\alpha K$ is an integer – if not, $\alpha$ can be appropriately quantized),
and two corresponding sets of jamming distributions:

    1. (a)

Prefix-babbling distributions: These comprise of a set of $\alpha K$
distributions
$\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}\\}_{u=1}^{\alpha K}$ that
James will use in the corresponding prefix chunks, as described in 3 below.

    2. (b)

Suffix-symmetrization distributions: These comprise of a set of $\alpha K$
distributions
$\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}=u}\\}_{u=\alpha
K+1}^{K}$ that James will use in the corresponding suffix chunks, as described
in 4 below.

In particular, these two sets of distributions are required to satisfy both
the following:

    1. (i)

State-feasibility: The prefix-babbling and suffix-symmetrization jamming
distributions are required to jointly satisfy a certain state-feasibility
condition – see Definition 6. This condition can be thought of as ensuring
that the overall jamming vector ${\underline{s}}$ that James chooses satisfies
the state cost constraint imposed by the AVC by separately computing the cost
of the prefix jamming sequence
$({\underline{s}}(1),\ldots,{\underline{s}}(\alpha n))$ induced by the prefix-
babbling distributions, and the cost of the suffix jamming sequence
$({\underline{s}}(\alpha n+1),\ldots,{\underline{s}}(n))$ induced by the
suffix-pushing distributions. It is important to highlight here that due to
the Generalized Plotkin bound [WBBJ19] the suffix state cost only needs to be
computed with respect to $P_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$
distributions that are convex combinations of product distributions.

    2. (i)

Suffix-symmetrizability: The suffix-symmetrization jamming distributions are
required to satisfy a certain suffix-symmetrizability condition – see
${\mathcal{V}}$ in Definition 10. This condition can be thought of ensuring
that the suffix $({\underline{y}}(\alpha n+1),\ldots,{\underline{y}}(n))$
observed by Bob was equally likely to have been generated by either the
codeword suffix ${\underline{x}}^{>\alpha}=({\underline{x}}(\alpha
n+1),\ldots,{\underline{x}}(n))$ or the codeword suffix
${\underline{x}}^{\prime>\alpha}=({\underline{x}}^{\prime}(\alpha
n+1),\ldots,{\underline{x}}^{\prime}(n))$ (with the jamming distribution
$V_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}$ acting on the pair of
codeword suffixes
$({\underline{x}}^{>\alpha},{\underline{x}}^{\prime>\alpha})$ in the first
case, and on the pair
$({\underline{x}}^{\prime>\alpha},{\underline{x}}^{>\alpha})$ in the second
case – note the reversal/symmetrization in the two scenarios).

After this pre-transmission analysis, once Alice starts transmitting, James
proceeds with his jamming attack as follows.

  3. 3.

Prefix-babbling phase: For the initial $\alpha K$ chunks (henceforth called
the $\alpha$-prefix of ${\underline{x}}$, or just the prefix) James uses a
“babble” attack. That is, for each time index $t$ in chunk $u\leq\alpha K$ he
selects his jamming symbols ${\underline{s}}(t)$ via the probabilistic map
$\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}\\}_{u=1}^{\alpha K}$ applied
symbol-by-symbol to the corresponding observed transmission
${\underline{x}}(t)$. For these chunks in the prefix James thereby induces
effective DMCs
$\\{W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{u}}=u}\\}_{u=1}^{\alpha K}$ from
Alice to Bob. If the rate $R$ of Alice’s code is too high (i.e., is not
$\delta$-good – see Definition 11), then for some $\alpha\leq 1$ there will be
a chunk number $\alpha K$ such that in addition to James’ jamming sequence
${\underline{s}}$ satisfying the state-feasability and suffix-symmetrizability
conditions described in 2) above, he can also force the “Large prefix-list”
condition described below.

     * •

Large prefix-list: For the prefix, the normalized cumulative mutual
information $\sum_{i=1}^{\alpha
K}\frac{1}{K}I(P_{{\mathbf{x}}|{\mathbf{u}}=u},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{u}}=u})$
(repeated in Definition 8) is less than the rate $R$ of Alice’s code. Via
standard information-theoretic arguments such as strong converses, this can be
used to argue that at this point in the transmission Bob must still have a
large set (say of size $2^{\Omega(n)}$) of potential messages that are
compatible with Alice’s coebook ${\mathcal{C}}$, his prefix observation
${\underline{y}}^{\leq\alpha}$ and the prefix channels
$\\{W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{u}}=u}\\}_{u=1}^{\alpha K}$ induced
by James.

  4. 4.

Suffix-pushing phase: Since the channel
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$ is state-deterministic (this is
the precise reason we need to restrict to state-deterministic AVCs the class
of channels for which we can claim our achievability and converse arguments
match), therefore at this $\alpha n$ point James can compute the same large
prefix-list that Bob would have computed. He then randomly selects some
$m^{\prime}$ in this prefix list, and sets the “spoofing suffix”
${\underline{x}}^{\prime>\alpha}_{m^{\prime}}$ as the codeword suffix
corresponding to this $m^{\prime}$, and for any time-index $t$ in suffix chunk
$u$, applies the corresponding suffix symmetrizing distribution
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}=u}(\cdot|{\underline{x}}(t),{\underline{x}}^{\prime}(t))$
symbol-by-symbol on the ${\underline{x}}(t)$ he (causally) observes and the
${\underline{x}}^{\prime}(t)$ in his chosen spoofing suffix.

Via analysis paralleling but significantly generalizing to a general class of
AVCs the symbol-error analysis in [CJL19] it can be shown that for any code
with rate that is not $\delta$-good the strategy outlined and motivated above
results, with probability bounded away from zero, in James being able to cause
a decoding error by Bob. We emphasize again that incorporating the recently
discovered Generalized Plotkin bound was a key step in this converse, without
which any converse would have resulted in a significantly weaker rate-bound
for general AVCs. Further, by the synthesis of information-theoretic and
coding-theoretic techniques introduced in [DJLS13], these arguments can be
generalized even to settings where Alice uses a stochastic encoder. Therefore,
by choosing among all possible choices of feasible attack parameter/jamming
distributions in Step 2 that attains the infimum of the “not $\delta$-good”
rates, we can ensure that if Alice wishes to reliably communicate to Bob,
James will be able to confuse Bob between the truly transmitted message and a
spoofing message.

To complement this impossibility argument, we can also demonstrate that for
the class of AVCs considered any rate that is $\delta$-good is indeed
achievable. Again, this broadly parallels the scheme for symbol-error AVC in
[CJL19], while significantly generalizing it to a general class of AVCs. In
particular, the achievability analysis required novel interpolating arguments
to ensure that certain algebraic conditions on distributions
($\delta$-goodness of the code, non-symmetrizability of the suffix) ensures
that if Bob follows a certain iterative decoding mechanism, he will, with high
probability, be able to decode correctly.

  1. 1.

Codebook parameter choices: First, for each chunk Alice chooses a length-$K$
time-sharing vector ${\underline{u}}$ and corresponding chunk-wise input
distributions $\\{P_{{\mathbf{x}}|{\mathbf{u}}=u}\\}_{u=1}^{K}$ such that the
overall time-averaged input distribution
$P_{\mathbf{x}}=\frac{1}{K}\sum_{u=1}^{K}P_{{\mathbf{x}}|{\mathbf{u}}=u}$
satisfies the input constraint set specified in the AVC problem. Among all
possible such choices of ${\underline{u}}$ and
$\\{P_{{\mathbf{x}}|{\mathbf{u}}=u}\\}_{u=1}^{K}$, Alice chooses the time-
sharing vector and chunk-wise input distributions for which the supremum of
all $\delta$-good rates is as large as possible, and sets this supremum (minus
a $\delta$ slack) as the rate $R$ of her code.

  2. 2.

Chunk-wise stochastic code design: Alice then designs a random chunk-wise
stochastic code as follows. In particular, for each chunk
$u\in\\{1,\ldots,K\\}$ and each message $m\in\\{1,\ldots,2^{nR}\\}$, she
chooses $2^{\varepsilon^{3}n}$ random length-$\varepsilon n$ codeword chunks
of type $P_{{\mathbf{x}}|{\mathbf{u}}=u}$. These codeword-chunks for chunk
number $u$ and message $m$ are denoted ${\underline{x}}^{(u)}_{(m,r^{(u)})}$,
where $r^{(u)}$ is an index varying in the set
$\\{1,\ldots,2^{n\varepsilon^{3}}\\}$. These multiple codeword-chunks for a
given message are used, as described below, to ensure that at any time $t$
James always has some uncertainty about the actual codeword to be transmitted
in the next chunk even if he knows Alice’s message.

  3. 3.

Chunk-wise stochastic encoding: Given the message $m$ and the chunk-wise
stochastic code described above, for each chunk $u\in\\{1,\ldots,K\\}$ Alice
picks a uniformly random $r^{(u)}$ from the set
$\\{1,\ldots,2^{n\varepsilon^{3}}\\}$ and transmits the codeword-chunk
${\underline{x}}^{(u)}_{(m,r^{(u)})}$. For small $\varepsilon$, note that the
entropy of $r^{(u)}$ (which equals $n\varepsilon^{3}$) is significantly
smaller than the chunk-length $n\varepsilon$. This is important in the list-
decoding steps described below.

  4. 4.

Chunkwise-iterative decoding: On receiving the vector ${\underline{y}}$, Bob’s
decoding scheme then proceeds iteratively over $K$ stages in a manner that
conceptually parallels the babble-and-push jamming strategy described above.
(We emphasize that we do not assume that James follows a babble-and-push
jamming strategy – rather, as a consequence of our analysis it turns out to be
the case that for the class of AVCs considered the babble-and-push jamming
strategy is an extremizing strategy in the sense that it results in the lowest
reliable throughput.)
We describe this chunkwise-iterative decoding scheme in more detail now as
follows. First, Bob initializes his prefix-chunk counter $\alpha K$ to $1$.
Then, for this value of $\alpha$ he performs the following two-step decoding
attempt.

    1. (a)

Prefix list-decoding: For the given $\alpha$, Bob considers all the tuples
$(\alpha,\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}\\}_{u=1}^{\alpha
K},\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}=u}\\}_{u=\alpha
K+1}^{K})$ which are feasible in the sense of Definition 6, and for which
$\alpha$ is the first chunk for which the the normalized cumulative mutual
information $\sum_{i=1}^{\alpha
K}\frac{1}{K}I(P_{{\mathbf{x}}|{\mathbf{u}}=u},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{u}}=u})$
(in the sense of Definition 8) is more than the rate $R$ of the code. Via
relatively standard list-decoding arguments (adapted to the chunkwise
stochastic encoding scheme here) ensure that with overwhelming probability
over code-design (indeed, with probability say $1-2^{\Omega(n^{2})}$) Bob can
decode down to a “small” list (of size say ${\mathcal{O}}(n)$).

    2. (b)

Suffix disambiguation: For this value of $\alpha$ and the corresponding list
of messages obtained from the prefix, Bob uses the suffix to disambiguate the
correct message from the list, by performing a suffix consistency check. This
comprises of checking to see if any of the codeword suffixes for any message
in the prefix-list is jointly typical with respect to the observed suffix. If
more than one message in the prefix list passes this suffix consistency test
then Bob declares a decoding error and aborts; if none of the messages in the
prefix list pass this consistency test then Bob increments the value of
$\alpha$ and tries again; and if a unique message passes this test then Bob
outputs that message as the decoded message and terminates. To show that this
decoding strategy suffices to attain the capacity, we need to show two things.
Firstly we need to demonstrate that the truly transmitted message does indeed
pass Bob’s suffix consistency check, and secondly that with high probability
over the private randomness in the suffix no other message in Bob’s prefix
list passes the consistency check. The former argument is relatively standard,
relying mostly on concentration arguments to show that joint typicality
decoding in the suffix results in the true message being suffix-consistent.
The latter argument is more delicate – we first demonstrate that at the true
$\alpha$ value, over the private randomness in suffix chunks that is currently
unknown to James, the joint types of most codeword suffixes for the truly
transmitted codeword will be jointly typical (with respect to a convex
combination of a product distribution) with every suffix codewords for all
other messages in Bob’s prefix message list (here, importantly, we use the
fact that the private-randomness rate is vanishing relative to the suffix
length, and hence suffix joint-types are closely concentrated around their
expectation). This coupled with suffix non-symmetrizability ensures that the
true codeword suffix typicality implies that no other message codeword suffix
can be jointly typical. Another non-trivial aspect to this analysis is to
demonstrate that even for decoding points preceding the “true” $\alpha$, this
decoding rule works in the sense that no other suffix passes the suffix
consistency test – this is done by carefully choosing two interpolating
jamming trajectories and using convexity arguments to argue that non-
symmetrizability with respect to the true $\alpha$ also implies non-
symmetrizability with respect to preceding $\alpha$s.

It should be emphasized that, perhaps surprisingly, input distributions
$P_{{\mathbf{x}}|{\mathbf{u}}=u}$ that are uniform in the time-sharing
variable ${\mathbf{u}}$ do not necessarily attain capacity for general AVCs.
For the special case of the finite alphabet symbol-error/erasure channels
considered in [CJL19] the uniform input distribution is indeed optimizing as
shown there, but for the quadratically constrained casual model [LDJ+18] it
can be shown that uniform power allocation is not capacity-achieving. The
reason for this phenomenon, which might seem counter-intuitive given the
convexity of mutual information function and the linearity of the
symmetrizability condition, is that since Alice has to choose a rate $R$ and
design her corresponding codebook distribution to simultaneously be
$\delta$-good for any possible choice of $\alpha$ (and the corresponding
feasible input distributions), therefore the problem becomes highly non-
convex. We are currently actively investigating alternating optimization
approaches to computationally tractable well-approximate the capacity function
for general AVCs, and simultaneously obtain the corresponding extremizing
input/jamming distributions.

##  III Model

Notation: alphabets are in calligraphic script (e.g. ${\mathcal{X}}$). In this
paper, all alphabets are finite. A boldface letter (e.g. ${\mathbf{x}}$) is a
random variable, with the non-boldface (e.g. $x$) as its realization. The set
$[M]=\\{1,2,\ldots,M\\}$. Tuples are written with an underline sign and
individual entries with the time index in parentheses (e.g.
${\underline{x}}=({\underline{x}}(1),{\underline{x}}(2),\ldots,{\underline{x}}(n))$)
and
${\underline{x}}(1:i)=({\underline{x}}(1),{\underline{x}}(2),\ldots,{\underline{x}}(i))$).
The _type_ of a tuple $T_{{\underline{x}}}$ is the empirical distribution of
${\underline{x}}$. The set of all probability distributions on an alphabet
${\mathcal{X}}$ is $\Delta({\mathcal{X}})$. The set of all conditional
distributions (randomized maps) from ${\mathcal{X}}$ to ${\mathcal{S}}$ is
$\Delta({\mathcal{S}}|{\mathcal{X}})$. The length $n$ _type class_
corresponding to $P\in\Delta({\mathcal{X}})$ is denoted by
${\mathcal{T}}_{n}(P)=\left\\{{\underline{x}}\in{\mathcal{X}}^{n}:T_{{\underline{x}}}=P\right\\}$.
For a joint distribution $P_{{\mathbf{x}},{\mathbf{s}}}$ we write
$[P_{{\mathbf{x}},{\mathbf{s}}}]_{{\mathbf{x}}}$ and
$[P_{{\mathbf{x}},{\mathbf{s}}}]_{{\mathbf{s}}}$ for the marginal
distributions of ${\mathbf{x}}$ and ${\mathbf{s}}$.

###  III-A Channels and codes

We consider a class of arbitrarily varying channels (AVCs) with cost
constraints on the input and state. Our formulation of the cost constraint
generalizes the standard definition [CN88a] by modeling the constraint as
requiring that the type of the channel input or state belong to a specified
set.

######  Definition 1 (AVC).

An _arbitrarily varying channel_ (AVC) is a sextuple
$({\mathcal{X}},{\mathcal{S}},{\mathcal{Y}},\lambda_{\mathbf{x}},\lambda_{\mathbf{s}},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}})$.
Here, ${\mathcal{X}},{\mathcal{S}},{\mathcal{Y}}$ are the input, state and
output alphabets, respectively. The input and state constraints are specified
by $\lambda_{\mathbf{x}}\subset\Delta({\mathcal{X}})$ and
$\lambda_{\mathbf{s}}\subset\Delta({\mathcal{S}})$, respectively. The channel
law is
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\in\Delta({\mathcal{Y}}|{\mathcal{X}}\times{\mathcal{S}})$.

Our goal is to communicate one of $M$ messages reliably over this AVC. For a
positive integer $M$, let ${\mathcal{M}}\coloneqq[M]$ denote all possible
messages that the transmitter may send.

######  Definition 2 (Codes).

A _code_ for a causal AVC
$({\mathcal{X}},{\mathcal{S}},{\mathcal{Y}},\lambda_{\mathbf{x}},\lambda_{\mathbf{s}},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}})$
is a pair $(\operatorname{Enc},\operatorname{Dec})$. Here
$\operatorname{Enc}\in\Delta({\mathcal{X}}^{n}|{\mathcal{M}})$ is a
(potentially stochastic) encoder. For $m\in{\mathcal{M}}$, we use
$\operatorname{Enc}(m)\in{\mathcal{X}}^{n}$ to denote the (possibly random)
encoding of $m$. Each such an encoding is called a _codeword_. The set
$\operatorname{Enc}({\mathcal{M}})$ of all codewords is called the _codebook_
, denoted by ${\mathcal{C}}$. The length $n$ of each codeword is called the
_blocklength_. The _rate_ of ${\mathcal{C}}$ is defined as
$R({\mathcal{C}})\coloneqq\frac{1}{n}\log M$. The code is required to satisfy
the input constraint: for every ${\underline{x}}\in{\mathcal{C}}$,
$T_{{\underline{x}}}\in\lambda_{\mathbf{x}}$. The decoder is given by
$\operatorname{Dec}\in\Delta({\mathcal{M}}|{\mathcal{Y}}^{n})$. We use
$\operatorname{Dec}({\underline{y}})\in{\mathcal{M}}$ to denote the
(potentially random) message output by the decoder given ${\underline{y}}$.

######  Definition 3 (Jamming strategies).

A _jamming strategy_ of blocklength $n$ is a set of maps
$\mathrm{Jam}=(\mathrm{Jam}_{1},\cdots,\mathrm{Jam}_{n})$ where
$\mathrm{Jam}_{t}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{n})$ is the jamming
function at time $t$. In a _causal jamming strategy_ ,
$\mathrm{Jam}_{t}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{t})$.

######  Definition 4 (Communication over causal/online AVC).

Communication over a _causal_ (a.k.a.  _online_) AVC
$({\mathcal{X}},{\mathcal{S}},{\mathcal{Y}},\lambda_{\mathbf{x}},\lambda_{\mathbf{s}},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}})$
has the following requirements. Let ${\mathcal{C}}$ be a code with an encoder-
decoder pair $(\operatorname{Enc},\operatorname{Dec})$ and
$\mathrm{Jam}=(\mathrm{Jam}_{1},\cdots,\mathrm{Jam}_{n})$ be a causal jamming
strategy. We use
$\mathrm{Jam}_{i}({\underline{x}}(1),\cdots,{\underline{x}}(i))$ to denote the
jamming symbol generated by the adversary at time $i$. Before communication
happens, $(\operatorname{Enc},\operatorname{Dec})$ are fixed and revealed to
the transmitter _Alice_ , the receiver _Bob_ and the adversary _James_. James
then fixes a causal jamming strategy
$\mathrm{Jam}=(\mathrm{Jam}_{1},\cdots,\mathrm{Jam}_{n})$ which can depend on
$(\operatorname{Enc},\operatorname{Dec})$.

The code is required to satisfy the input constraint
$T_{\underline{x}}\in\lambda_{\mathbf{x}}$ for every
${\underline{x}}\in{\mathcal{C}}$. Once a particular encoding
${\underline{x}}$ of a certain message $m$ is transmitted by Alice, James
observes ${\underline{x}}$ _causally_. That is, for any $i\in[n]$, he observes
${\underline{x}}(i)$ after observing
${\underline{x}}(1),\cdots,{\underline{x}}(i-1)$. Given his causal
observation, he computes
${\underline{s}}(i)=\mathrm{Jam}_{i}({\underline{x}}(1),\cdots,{\underline{x}}(i))$
which depends only on ${\underline{x}}(1),\cdots,{\underline{x}}(i)$ (and
$(\operatorname{Enc},\operatorname{Dec}),{\mathcal{C}}$ which are known to
everyone). The channel then outputs ${\underline{\mathbf{y}}}$ according to
the following distribution

$\displaystyle\Pr\left[{\underline{\mathbf{y}}}={\underline{y}}\,|\,{\underline{\mathbf{x}}}={\underline{x}},{\underline{\mathbf{s}}}={\underline{s}}\right]$
$\displaystyle\coloneqq\prod_{i=1}^{n}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}(i),{\underline{s}}(i)).$

Receiving ${\underline{\mathbf{y}}}$, Bob decodes to
$\operatorname{Dec}({\underline{\mathbf{y}}})$.

Communication reliability is measured by:

######  Definition 5 (Error probability).

Consider a causal AVC
$({\mathcal{X}},{\mathcal{S}},{\mathcal{Y}},\lambda_{\mathbf{s}},\lambda_{\mathbf{s}},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}})$.
Let $(\operatorname{Enc},\operatorname{Dec})$ and $\mathrm{Jam}$ be a coding
scheme and a jamming strategy for this channel, respectively. Define the
_maximum error probability_
$P_{{\mathrm{e}},\max}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})$ as
follows

$\displaystyle
P_{{\mathrm{e}},\max}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})\coloneqq$
$\displaystyle\max_{m\in{\mathcal{M}}}\sum_{\begin{subarray}{c}\widehat{m}\in{\mathcal{M}}\\\
\widehat{m}\neq
m\end{subarray}}\sum_{{\underline{y}}\in{\mathcal{Y}}^{n}}\sum_{{\underline{s}}\in{\mathcal{S}}^{n}}\sum_{{\underline{x}}\in{\mathcal{X}}^{n}}\operatorname{Enc}({\underline{x}}|m)\cdot\left(\prod_{i=1}^{n}\mathrm{Jam}_{i}({\underline{s}}(i)|{\underline{x}}(1:i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}(i),{\underline{s}}(i))\right)\cdot\operatorname{Dec}(\widehat{m}|{\underline{y}}).$

The _average error probability_ is defined analogously by averaging over
messages $m$:

$\displaystyle
P_{{\mathrm{e}},\mathrm{avg}}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})\coloneqq$
$\displaystyle\frac{1}{|{\mathcal{M}}|}\sum_{\begin{subarray}{c}\widehat{m}\in{\mathcal{M}}\\\
\widehat{m}\neq
m\end{subarray}}\sum_{{\underline{y}}\in{\mathcal{Y}}^{n}}\sum_{{\underline{s}}\in{\mathcal{S}}^{n}}\sum_{{\underline{x}}\in{\mathcal{X}}^{n}}\sum_{m\in{\mathcal{M}}}\operatorname{Enc}({\underline{x}}|m)\cdot$
$\displaystyle\left(\prod_{i=1}^{n}\mathrm{Jam}_{i}({\underline{s}}(i)|{\underline{x}}(1:i))W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}({\underline{y}}(i)|{\underline{x}}(i),{\underline{s}}(i))\right)\cdot\operatorname{Dec}(\widehat{m}|{\underline{y}}).$
(1)

Here we view $\operatorname{Enc}\in\Delta({\mathcal{X}}^{n}|{\mathcal{M}})$
and $\operatorname{Dec}\in\Delta({\mathcal{M}}|{\mathcal{Y}}^{n})$ as
conditional distributions.

###  III-B State-deterministic AVCs

We consider a class of AVCs which are state deterministic and have a single
cost constraint on the state. More precisely, we require the following five
assumptions to hold:

  1. 1.

All alphabets ${\mathcal{X}},{\mathcal{S}},{\mathcal{Y}}$ are finite.111The
quadratically-constrained infinite alphabet setting was considered in
[LDJ+18].

  2. 2.

The input constraint set $\lambda_{\mathbf{x}}\subset\Delta({\mathcal{X}})$ is
convex. This is a natural restriction – a non-convex set
$\lambda_{\mathbf{x}}$ would imply that the encoder is not allowed to time-
share between some potential transmissions.

  3. 3.

The set $\lambda_{\mathbf{s}}\subset\Delta({\mathcal{S}})$ is specified by a
_single_ constraint:

$\displaystyle\lambda_{\mathbf{s}}$
$\displaystyle\coloneqq\left\\{P_{\mathbf{s}}\in\Delta({\mathcal{S}}):\sum_{s\in{\mathcal{S}}}P_{\mathbf{s}}(s)B(s)\leq\Lambda\right\\},$

for some ${B}\in{\mathbb{R}}^{|{\mathcal{S}}|}$ and $\Lambda\in{\mathbb{R}}$.

  4. 4.

The channel law $W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$ is deterministic,
i.e., for every $(x,s)\in{\mathcal{X}}\times{\mathcal{S}}$, there is a unique
$y\in{\mathcal{Y}}$ such that
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)=1$. Alternatively, we write
the channel law as a (deterministic) function
$W\colon{\mathcal{X}}\times{\mathcal{S}}\to{\mathcal{Y}}$. 222Our
achievability result actually does not require this restriction – it holds
even if the AVC is not state-deterministic. However, our current converse
arguments providing a capacity upper bound asymptotically matching the rate
achievable by our achievability scheme rely on state-determinism, since they
rely on the jammer being able to predict the channel output resulting from a
specific jamming strategy.

  5. 5.

There exists a zero-cost state $s_{0}\in{\mathcal{S}}$ and a one-to-one
mapping $\phi:{\mathcal{Y}}\rightarrow{\mathcal{X}}$ for which for every $x$,
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(\phi(x)|x,s_{0})=1$. This final
assumption is rather natural and corresponds to many channel models. It
intuitively implies that there is a _stand-down_ state for James that on one
hand has zero cost and on the other does not corrupt communication at all,
e.g., the “non-erasure” state in an erasure channel.

##  IV Capacity charatcterization

In order to state our main result we must define a notion of
_symmetrizability_ [Eri85, CN88b] that is appropriate to the causal AVC model.
Symmetrizabillity conditions play an important role in characterizing AVC
capacities under deterministic coding. Roughly speaking, a channel is
symmetrizable if James can, via selecting the state sequence
${\underline{s}}$, cause the channel to behave like a symmetric two-user
multiple-access channel
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(y|x,x^{\prime})$.
Operationally, this means James can select an alternative (“spoofing”)
codeword ${\underline{x}}^{\prime}$ and use it to create a state
${\underline{s}}$ such that Bob cannot tell if Alice sent ${\underline{x}}$
and James chose ${\underline{x}}^{\prime}$ or if Alice sent
${\underline{x}}^{\prime}$ and James chose ${\underline{x}}$.

There are two aspects of the causal AVC which make it tricky to define a
notion of symmetrizability. First is the online nature of the adversarial
attack: James has to choose the elements of ${\underline{s}}$ sequentially as
opposed to selecting ${\underline{x}}^{\prime}$ and then ${\underline{s}}$.
Second is the cost constraint on ${\underline{s}}$: if we think of the cost as
“power,” then James faces a power allocation problem. Taken together, James
could spend little power at the beginning and more power at the end of the
transmission or vice versa. In the former case, Bob can get a good estimate of
the message initially but then the channel becomes much worse. In the latter,
Bob has a very bad estimate of the message but the channel is less noisy at
the end, allowing him to potentially decode to the true message. Since James
does not know the transmitted codeword a priori, he has to choose how to
allocate the power “on the fly” while satisfying the cost constraint.

###  IV-A Symmetrizing distributions

Let $K\in{\mathbb{Z}}_{\geq 1}$, ${\mathcal{U}}\coloneqq[K]$ and
${\mathcal{A}}\coloneqq\\{0,1/K,2/K,\cdots,1-1/K\\}$. For
$\alpha\in{\mathcal{A}}$, let
${\mathcal{U}}^{\leq\alpha}\coloneqq\\{1,2,\cdots,\alpha K\\}$ and
${\mathcal{U}}^{>\alpha}\coloneqq\\{\alpha K+1,\alpha K+2,\cdots,K\\}$. Let
$P_{\mathbf{u}}\coloneqq\operatorname{Unif}({\mathcal{U}})$. Fix
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ such
that
$\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{{\mathbf{x}}}\in\lambda_{\mathbf{x}}$.

In our achievable scheme we will use a code in which the total blocklength $n$
is broken into $K$ subblocks. In each block, we characterize the jammer by a
single letter channel.

######  Definition 6 (Feasible jamming distributions).

Let $P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$.
Define, for $\alpha\in{\mathcal{A}}$,

$\displaystyle{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}^{\leq\alpha})\times\Delta({\mathcal{S}}|{\mathcal{X}}^{2}\times{\mathcal{U}}^{>\alpha}):\\\
\displaystyle\frac{1}{\alpha K}\sum_{u=1}^{\alpha
K}\left[P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}=u}\right]_{{\mathbf{s}}}+\frac{1}{(1-\alpha)K}\sum_{u=\alpha
K+1}^{K}\left[P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\right]_{\mathbf{s}}\in\lambda_{\mathbf{s}}\end{array}\right\\},$
(4)

and

$\displaystyle{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})$
$\displaystyle\coloneqq\left\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}):\frac{1}{K}\sum_{u=1}^{K}\left[P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}\right]_{\mathbf{s}}\in\lambda_{\mathbf{s}}\right\\}.$

Generalizing the definition above for any $P_{{\mathbf{u}}}$ and slackness
$\delta$ we have:

######  Definition 7 ($\delta$-feasible jamming distributions).

Let
$(P_{{\mathbf{u}}},P_{{\mathbf{x}}|{\mathbf{u}}})\in\Delta({\mathcal{U}})\times\Delta({\mathcal{X}}|{\mathcal{U}})$.
Define, for $\alpha\in{\mathcal{A}}$,

$\displaystyle{\mathcal{F}}_{\alpha,\delta}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}^{\leq\alpha})\times\Delta({\mathcal{S}}|{\mathcal{X}}^{2}\times{\mathcal{U}}^{>\alpha}):\\\
\displaystyle\sum_{u\in{\mathcal{U}}^{\leq\alpha}}P_{\mathbf{u}}(u)\left[P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}=u}\right]_{{\mathbf{s}}}+\sum_{u\in{\mathcal{U}}^{>\alpha}}P_{\mathbf{u}}(u)\left[P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\right]_{\mathbf{s}}\in\mathrm{int}_{\delta}(\lambda_{\mathbf{s}})\end{array}\right\\},$
(7)

and

$\displaystyle{\mathcal{F}}_{\delta}(P_{{\mathbf{x}}|{\mathbf{u}}})$
$\displaystyle\coloneqq\left\\{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}):\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\right]_{\mathbf{s}}\in\mathrm{int}_{\delta}(\lambda_{\mathbf{s}})\right\\}.$

######  Definition 8 (Cumulative mutual information).

Fix $P_{{\mathbf{x}}|{\mathbf{u}}}$, $\alpha\in{\mathcal{A}}$ and
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\in\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}^{\leq\alpha})$.
The _cumulative mutual information_ w.r.t. $P_{{\mathbf{x}}|{\mathbf{u}}}$ and
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ is defined as

$\displaystyle
I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
$\displaystyle\coloneqq
I({\mathbf{x}};{\mathbf{y}}|{\mathbf{u}}^{\leq\alpha})=\frac{1}{K}\sum_{u=1}^{\alpha
K}I({\mathbf{x}}_{u};{\mathbf{y}}_{u}),$

where the joint distribution of $({\mathbf{x}}_{u},{\mathbf{y}}_{u})$ is given
by

$\displaystyle P_{{\mathbf{x}}_{u},{\mathbf{y}}_{u}}(x,y)$
$\displaystyle\coloneqq\sum_{s\in{\mathcal{S}}}P_{{\mathbf{x}}|{\mathbf{u}}}(x|u)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}(s|x,u)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s).$

Similarly, we generalize the above definition for any
$P_{{\mathbf{u}}^{\leq\alpha}}$.

######  Definition 9 (Cumulative mutual information).

Define the _cumulative mutual information_ w.r.t.
$(P_{{\mathbf{u}}^{\leq\alpha}},P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\in\Delta({\mathcal{U}}^{\leq\alpha})\times\Delta({\mathcal{X}}|{\mathcal{U}}^{\leq\alpha})\times\Delta({\mathcal{S}}|{\mathcal{X}}\times{\mathcal{U}}^{\leq\alpha})$
as

$\displaystyle
I(P_{{\mathbf{u}}^{\leq\alpha}},P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
$\displaystyle\coloneqq
I({\mathbf{x}};{\mathbf{y}}|{\mathbf{u}}^{\leq\alpha})=\alpha\sum_{u\in{\mathcal{U}}^{\leq\alpha}}P_{{\mathbf{u}}^{\leq\alpha}}(u)I({\mathbf{x}}_{u};{\mathbf{y}}_{u}),$

where the joint distribution of $({\mathbf{x}}_{u},{\mathbf{y}}_{u})$ is given
by

$\displaystyle P_{{\mathbf{x}}_{u},{\mathbf{y}}_{u}}(x,y)$
$\displaystyle\coloneqq\sum_{s\in{\mathcal{S}}}P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}(x|u)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}(s|x,u)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s).$

######  Remark 1.

In the above definition, the time-sharing distribution
$P_{{\mathbf{u}}^{\leq\alpha}}$ is over the prefix
${\mathcal{U}}^{\leq\alpha}$. However, the information throughput is measured
w.r.t. the whole block of transmissions of length $n$. Therefore, we need an
$\alpha$ factor to account for that. If we instead define the cumulative
mutual information with $P_{\mathbf{u}}\in\Delta({\mathcal{U}})$, then no
$\alpha$ factor is needed.

######  Definition 10 (Symmetrizing distributions).

Define

$\displaystyle{\mathcal{V}}$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2}):\\\
\displaystyle\forall(x,x^{\prime},y)\in{\mathcal{X}}^{2}\times{\mathcal{Y}},\,{\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)=\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)}\end{array}\right\\},$
(10) $\displaystyle{\mathcal{V}}_{\delta}$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2}):\\\
\displaystyle\forall(x,x^{\prime},y)\in{\mathcal{X}}^{2}\times{\mathcal{Y}},\,\left|{\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)-\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)}\right|\leq\delta\end{array}\right\\},$
(13) $\displaystyle{\mathcal{V}}^{\prime}$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}^{\prime})\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2})^{2}:\\\
\displaystyle\forall(x,x^{\prime},y)\in{\mathcal{X}}^{2}\times{\mathcal{Y}},\,{\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)=\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}^{\prime}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)}\end{array}\right\\},$
(16) $\displaystyle{{\mathcal{V}}}^{\prime}_{\delta}$
$\displaystyle\coloneqq\left\\{\begin{array}[]{l}(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}^{\prime})\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2})^{2}:\\\
\displaystyle\forall(x,x^{\prime},y)\in{\mathcal{X}}^{2}\times{\mathcal{Y}},\,\left|\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)-\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime}}^{\prime}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)\right|\leq\delta\end{array}\right\\}.$
(19)

In what follows, we show that $C$ defined below is the causal-capacity for
general AVC channels. We start by defining $C_{K}$ for every positive integer
$K$. Let $|{\mathcal{U}}|=K$.

$\displaystyle
C_{K}\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\Big{\\{}$
$\displaystyle\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),$
$\displaystyle\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime})\in{\mathcal{V}}^{\prime}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\Big{\\}}.$
(20)

Averaging over
$\frac{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}+V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime}}{2}$
in the rightmost $\min$ in the expression above, we have

$\displaystyle
C_{K}\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\Big{\\{}$
$\displaystyle\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),$
$\displaystyle\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\in{\mathcal{V}}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\Big{\\}}.$
(21)

Let $C=\limsup_{K\rightarrow\infty}C_{K}$.

######  Theorem 1 (Achievability).

For any $\delta_{0}>0$ rate $C-\delta_{0}$ is achievable.

######  Theorem 2 (Converse).

For any $\delta_{0}>0$ rate $C+\delta_{0}$ is not achievable.

Before we prove the theorems above we state a technical claim. For
${\mathcal{U}}\coloneqq[K]$ and $\delta>0$, $\underline{C}_{K,\delta}$ defined
below will be used in the proof of Theorem 1. The remainder of this work
includes several slackness parameters that are mutually related and
highlighted in blue to ease the reading and verification process.

$\displaystyle\underline{C}_{K,\delta}$
$\displaystyle\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\left\\{\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V^{\prime}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime})\in{\mathcal{V}}^{\prime}_{\delta}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\right\\}.$

Averaging over
$\frac{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}+V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime}}{2}$
in the rightmost $\min$ in the expression above, we have

$\displaystyle\underline{C}_{K,\delta}$
$\displaystyle\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\left\\{\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\in{\mathcal{V}}_{\delta}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\right\\}.$

For ${\mathcal{U}}\coloneqq[K]$, $\delta>0$, and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}=\operatorname{poly}(\delta)$,
$\overline{C}_{K,\delta}$ defined below will be used in the proof of Theorem
2.

$\displaystyle\overline{C}_{K,\delta}\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\Bigg{\\{}$
$\displaystyle\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),$
$\displaystyle\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\in{\mathcal{V}}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\Bigg{\\}}.$
(22)

Averaging over
$\frac{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}+V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime}}{2}$
in the rightmost $\min$ in the expression above, we have

$\displaystyle\overline{C}_{K,\delta}\coloneqq\max_{\begin{subarray}{c}P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}\end{subarray}}\min\Bigg{\\{}$
$\displaystyle\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),$
$\displaystyle\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\in{\mathcal{V}}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\Bigg{\\}}.$
(23)

######  Claim 3.

Let $K$ be a positive integer. Let $\delta$ be sufficiently small and let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}=\operatorname{poly}(\delta)$,
it holds that
$|C_{K}-\overline{C}_{K,\delta}|\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{GAP}(\delta)}}$
and
$|C_{K}-\underline{C}_{K,\delta}|\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{GAP}(\delta)}}$,
where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{GAP}(\delta)}}$
depends only on $\operatorname{poly}(\delta)$ , the parameters of the channel
$W$, and the cost function $\mathsf{cost}$.

###### Proof.

Let $\delta>0$ be a sufficiently small slackness parameter (the requirements
on $\delta$ will be discussed below). Let $|{\mathcal{U}}|=K$. Let
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ come
$\delta$-close to optimizing $C_{K}$ as defined in Equation (20). We compare
the first and second expressions in the definition of $C_{K}$ with those of
$\overline{C}_{K,\delta}$ and $\underline{C}_{K,\delta}$ when evaluated with
${\mathcal{U}}$ and
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$. By our
definitions, it follows that $C_{K}\leq\overline{C}_{K,\delta}$ and
$C_{K}\geq\underline{C}_{K,\delta}$. Thus to prove our assertion, it suffices
to compare the first and second expressions in $\overline{C}_{K,\delta}$ and
$\underline{C}_{K,\delta}$ to bound
$\overline{C}_{K,\delta}-\underline{C}_{K,\delta}$, and thus, in turn, to
bound $|C_{K}-\overline{C}_{K,\delta}|$ and
$|C_{K}-\underline{C}_{K,\delta}|$.

We note that once $P_{{\mathbf{x}}|{\mathbf{u}}}$ is fixed, the sets
${\mathcal{F}}$, ${\mathcal{F}}_{\alpha}$, and $V$ are convex sets defined by
linear constraints. Similarly for the
“${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$-contracted”
versions
${\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
and
${\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
or the “$\delta$-extracted” variant $V_{\delta}$. We also note that by the
properties given in Section III-B, for sufficiently small $\delta$, we have
that
${\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
and
${\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
are non-empty.

One can bound the difference between the first expression in
$\overline{C}_{K,\delta}$ and $\underline{C}_{K,\delta}$ using our observation
that
${\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
and
${\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
are non-empty combined with standard bounds on the mutual-information
function. More formally, for any optimizing
$\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}$ for
$\underline{C}_{K,\delta}$ one can find
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
for $\overline{C}_{K,\delta}$ for which
$\|\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}-\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\|_{\infty}$
is at most a linear function of
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$
and other constant parameters involved in the definition of ${\mathcal{F}}$.

For the second expression, we study the set ${\mathcal{V}}$ and
${\mathcal{V}}_{\delta}$ in combination with ${\mathcal{F}}_{\alpha}$ and
${\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$.
Namely, we study the set
${\mathcal{V}}\cap[{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
(where the latter set
${\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
in the intersection is projected onto the variables of
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}$).
If this intersection is non-empty for any sufficiently small $\delta$, then so
is
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$,
and thus, as previously discussed in the analysis of the first expression, for
any optimizing
$({\alpha},(\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq{\alpha}}},\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}))\in{\mathcal{A}}\times{\mathcal{F}}_{{\alpha}}$
such that $\forall
u\in{\mathcal{U}}^{>{\alpha}},\,\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}=u}\in{\mathcal{V}}_{\delta}$
in $\underline{C}_{K,\delta}$ one can find a corresponding
$(\alpha,(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}$
such that $\forall
u\in{\mathcal{U}}^{>\alpha},\,\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}=u}\in{\mathcal{V}}$
in $\overline{C}_{K,\delta}$ for which
$\|(\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq{\alpha}}},\underline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}})-(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\|_{\infty}$
is at most a linear function of $\delta$,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$
and other constant parameters involved in the definitions of ${\mathcal{F}}$
and ${\mathcal{V}}$.

If, alternatively, for some small $\delta$ the intersection
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
is empty, then so is
${\mathcal{V}}\cap[{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
and $\overline{C}_{K,\delta}$ and $\underline{C}_{K,\delta}$ are not impacted
by the second expressions under study.

Finally, if for any $\delta>0$,
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
is non-empty but
${\mathcal{V}}\cap[{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
is empty, we slightly modify the studied $P_{{\mathbf{x}}|{\mathbf{u}}}$ to
$P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}$ to guarantee that the new sets
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
and
${\mathcal{V}}\cap[{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
are both non-empty, which brings us to a case analyzed above. Our modification
on $P_{{\mathbf{x}}|{\mathbf{u}}}$ will be of limited statistical distance
implying a corresponding limited impact on the objective
$I(P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$.
To modify $P_{{\mathbf{x}}|{\mathbf{u}}}$, we fix an element
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}\in{\mathcal{V}}\cap[{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
and its corresponding
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$, the
existence of which follows from our assumption that for any $\delta>0$,
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
is non-empty. With
$(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}})$
in mind, ${\mathcal{F}}_{\alpha}$ is a structured quadratic function of
$P_{{\mathbf{x}}|{\mathbf{u}}}$. One can now reduce the state-cost of
$(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}},(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}))$
when compared to
$(P_{{\mathbf{x}}|{\mathbf{u}}},(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}))$
by
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$
by modifying $P_{{\mathbf{x}}|{\mathbf{u}}}$ to
$P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}$ with
$\|P_{{\mathbf{x}}|{\mathbf{u}}}-P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}\|_{\infty}$
bounded by a polynomial in
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}$
and other constant parameters involved in the definition of
${\mathcal{F}}_{\alpha}$. Accordingly, the objective
$I(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
when compared to
$I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
is similarly bounded. This now implies that both
${\mathcal{V}}_{\delta}\cap[{\mathcal{F}}_{\alpha}(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
and
${\mathcal{V}}\cap[{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}})]_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>{\alpha}}}}$
are non-empty, and we may use the analysis of the similar case studied above.

##  V Proof of achievability (Theorem 1)

###### Proof.

Let $\delta_{0}>0$. Let $R=C-\delta_{0}$. Let $\delta$ be a sufficiently small
function of $\delta_{0}$ to be determined shortly. Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}$
be a function of $\delta$ defined shortly through Claim 4. Let
$\varepsilon(\delta)=\delta{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}^{2}/2$.
Let $K=1/\varepsilon$. Take $\delta$ to be sufficiently small such that
$|C-C_{k}|\leq\delta_{0}/4$ and, by Claim 3,
$|C_{K}-\underline{C}_{K,\delta}|\leq\delta_{0}/4$, implying that
$R\leq\underline{C}_{K,\delta}-\delta$.

Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}\coloneqq\varepsilon$,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}\coloneqq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}+\varepsilon\log{|{\mathcal{X}}|}$,
and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}\coloneqq
3\varepsilon$. Note, with this setting of parameters, that
$2{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}/{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}^{2}=\delta$
(this fact will be used later in our proof). Without loss of generality,
assume $n$ is sufficiently large so that $n\varepsilon$ is an integer. Let
$\gamma\coloneqq\varepsilon^{4}$. Let $M\coloneqq 2^{nR},N\coloneqq
2^{n\gamma}$ and ${\mathcal{M}}\coloneqq[M],{\mathcal{R}}\coloneqq[N]$.

Let

$\displaystyle{\underline{u}}$
$\displaystyle\coloneqq(\underbracket{1,\cdots,1}_{n\varepsilon},\underbracket{2,\cdots,2}_{n\varepsilon},\cdots,\underbracket{K,\cdots,K}_{n\varepsilon})\in{\mathcal{U}}^{n}.$

For a vector ${\underline{v}}\in\Sigma^{n}$ over some alphabet $\Sigma$ and
$\alpha\in{\mathcal{A}}$, let

$\displaystyle{\underline{v}}^{\leq\alpha}$
$\displaystyle\coloneqq({\underline{v}}(1),\cdots,{\underline{v}}(\alpha
n))\in\Sigma^{\alpha n},$ $\displaystyle{\underline{v}}^{>\alpha}$
$\displaystyle\coloneqq({\underline{v}}(\alpha
n+1),\cdots,{\underline{v}}(n))\in\Sigma^{(1-\alpha)n};$

for $u\in{\mathcal{U}}$, let

$\displaystyle{\underline{v}}^{(u)}$
$\displaystyle\coloneqq({\underline{v}}((u-1)n\varepsilon+1),{\underline{v}}((u-1)n\varepsilon+2),\cdots,{\underline{v}}(un\varepsilon))\in\Sigma^{n\varepsilon}.$

For two vectors ${\underline{v}}_{1}\in\Sigma^{n_{1}}$ and
${\underline{v}}_{2}\in\Sigma^{n_{2}}$, denote their concatenation by

$\displaystyle{\underline{v}}_{1}\circ{\underline{v}}_{2}$
$\displaystyle\coloneqq({\underline{v}}_{1}(1),\cdots,{\underline{v}}_{1}(n_{1}),{\underline{v}}_{2}(1),\cdots,{\underline{v}}_{2}(n_{2}))\in\Sigma^{n_{1}+n_{2}}.$

For two sets of vectors ${\mathcal{V}}_{1}\in\Sigma^{n_{1}}$ and
${\mathcal{V}}_{2}\in\Sigma^{n_{2}}$, let

$\displaystyle{\mathcal{V}}_{1}\circ{\mathcal{V}}_{2}$
$\displaystyle\coloneqq\left\\{{\underline{v}}_{1}\circ{\underline{v}}_{2}:{\underline{v}}_{1}\in{\mathcal{V}}_{1},{\underline{v}}_{2}\in{\mathcal{V}}_{2}\right\\}.$

Our proof uses the following notion of code-goodness:

######  Definition 11 (Rate goodness).

Let $\delta>0$. Fix
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$. We say
that a rate $R\geq 0$ is _$\delta$ -good_ w.r.t.
$(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})$ if

  1. 1.

$\displaystyle R$
$\displaystyle\leq\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}});$

  2. 2.

For any
$(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
satisfying $\alpha\leq 1-1/K$ and
$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$,
the following property holds.

     * •

For every
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}^{\prime}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2}\times{\mathcal{U}}^{>\alpha})$
such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}^{\prime})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$,
there exists $u\in{\mathcal{U}}^{>\alpha}$ such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime})\not\in{\mathcal{V}}^{\prime}_{\delta}$.

###  V-A Determining a $P_{{\mathbf{x}}|{\mathbf{u}}}$ for code design

We first show using Claim 4 below that there exists a
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ with
$\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}$,
such that for any $u\in{\mathcal{U}}$, it holds that

$\min_{x;P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)>0}\\{P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)\\}\geq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}$

and in addition

$\displaystyle\underline{C}_{K,\delta}-\delta/2\leq\min\left\\{\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V^{\prime}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime})\in{\mathcal{V}}^{\prime}_{\delta}\end{subarray}}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\right\\}.$
(24)

######  Claim 4.

Let $\delta>0$. For a suitable
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}$
that depends polynomially on $\delta$ and additional parameters of the channel
$W$ at hand it holds that for any
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ with
$\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}$
there exists
$P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$
with
$\left[P_{\mathbf{u}}P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{\mathbf{x}}$
such that

  1. 1.

$\min_{x;P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}=u}(x)>0}\\{P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}=u}(x)\\}\geq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}$.

  2. 2.

The right-hand-side of (24) when evaluated on
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ or
$P^{\prime}_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$
differs by at most $\delta/2$.

###### Proof.

Follows lines similar to those presented in the proof of Claim 3.

Fix $P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ to
satisfy the above. We now show that $R$ is _$\delta$ -good_ w.r.t.
$(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})$. Namely, by our definition of
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$,
$R\leq\underline{C}_{K,\delta}-\delta\leq\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}})$.
Moreover, let
$(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
satisfy $\alpha\leq 1-1/K$ and
$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$,
then for every
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}^{\prime}\in\Delta({\mathcal{S}}|{\mathcal{X}}^{2}\times{\mathcal{U}}^{>\alpha})$
such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}^{\prime})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$,
there exists $u\in{\mathcal{U}}^{>\alpha}$ such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{\prime})\not\in{\mathcal{V}}^{\prime}_{\delta}$.
As otherwise, the right-hand-side of (24) would be less than
$R+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}=\underline{C}_{K,\delta}-\delta+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}<\underline{C}_{K,\delta}-\delta/2$
in contradiction to (24).

###  V-B Code construction

We describe below the construction of the codebook
${\mathcal{C}}\subset{\mathcal{X}}^{n}$. It is a concatenation of $K$ short
codebooks:
${\mathcal{C}}={\mathcal{C}}^{(1)}\circ{\mathcal{C}}^{(2)}\circ\cdots\circ{\mathcal{C}}^{(K)}$.
Here for each $u\in{\mathcal{U}}$,
${\mathcal{C}}^{(u)}\subset{\mathcal{X}}^{n\varepsilon}$ is sampled randomly
and independently. Specifically, $|{\mathcal{C}}^{(u)}|=M\cdot N$ and each
${\underline{x}}^{(u)}\in{\mathcal{C}}^{(u)}$ is independent and uniformly
distributed in
${\mathcal{T}}_{n\varepsilon}(P_{{\mathbf{x}}|{\mathbf{u}}=u})$. We label
codewords in ${\mathcal{C}}^{(u)}$ using a pair
$(m,r)\in{\mathcal{M}}\times{\mathcal{R}}$, i.e.,
${\mathcal{C}}^{(u)}=\\{{\underline{x}}^{(u)}_{(m,r)}\\}_{(m,r)\in{\mathcal{M}}\times{\mathcal{R}}}$.

###  V-C Encoding

The encoder $\operatorname{Enc}$ is stochastic. To encode a message
$m\in{\mathcal{M}}$, the encoder first samples a sequence of random seeds
${\mathbf{r}}=({\mathbf{r}}_{1},\cdots,{\mathbf{r}}_{K})\in{\mathcal{R}}^{K}$,
where
${\mathbf{r}}_{u}\overset{\mathrm{i.i.d.}}{\sim}\operatorname{Unif}({\mathcal{R}})$
for each $u\in{\mathcal{U}}$. These seeds are private to the encoder and not
revealed to any other parties. The encoding of $m$ with a random seed
${\mathbf{r}}$ is given by
$\operatorname{Enc}(m,{\mathbf{r}})\coloneqq{\underline{x}}_{(m,{\mathbf{r}}_{1})}^{(1)}\circ{\underline{x}}_{(m,{\mathbf{r}}_{2})}^{(2)}\circ\cdots\circ{\underline{x}}_{(m,{\mathbf{r}}_{K})}^{(K)}$,
where we make the dependence on ${\mathbf{r}}$ explicit.

###  V-D Decoding

Bob’s decoder runs iteratively. Suppose the channel output is
${\underline{y}}\in{\mathcal{Y}}^{n}$. For each $\alpha\in{\mathcal{A}}$ (from
small to large values, i.e., $\alpha=0,1/n,2/n,\cdots,1$) and for each
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ for which there
exists a
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}$
such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
satisfying
$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$,
the decoder performs the following two-step decoding.

  1. 1.

List-decoding. The decoder first list-decodes the prefix
$({\underline{y}}(1),\cdots,{\underline{y}}(\alpha K))$ to the following list
${\mathcal{M}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$:

$\displaystyle{\mathcal{M}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
$\displaystyle\coloneqq\left\\{m\in{\mathcal{M}}:\begin{array}[]{l}\exists(r_{1},\cdots,r_{\alpha
K})\in{\mathcal{R}}^{\alpha
K},\exists({\underline{s}}^{(1)},\cdots,{\underline{s}}^{(\alpha
K)})\in({\mathcal{S}}^{n\varepsilon})^{\alpha K}\,\mathrm{s.t.}\\\ \forall
u\in{\mathcal{U}}^{\leq\alpha},\,T_{{\underline{x}}_{(m,r_{u})}^{(u)},{\underline{s}}^{(u)},{\underline{y}}^{(u)}}=P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}=u}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\end{array}\right\\}.$
(27)

In words, the list consists of all messages whose corresponding codewords are
jointly typical with the prefix of the received vector according to the joint
distribution
$P_{{\mathbf{u}}}P_{{\mathbf{x}}|{\mathbf{u}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$.
We also define
${\mathcal{L}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
as the set of codewords whose corresponding messages are in
${\mathcal{M}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$.

  2. 2.

Unique decoding. Bob examines each codeword
${\underline{x}}^{\prime}\in{\mathcal{L}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
and outputs the message $m^{\prime}$ corresponding to
${\underline{x}}^{\prime}$ if and only if ${\underline{y}}$ could have been
obtained from ${\underline{x}}^{\prime}$ through a feasible
${\underline{s}}^{\prime}$. In particular, if there exists a vector
${\underline{s}}^{\prime}$ and
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}}$ for which
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
and $\forall u\in{\mathcal{U}}^{>\alpha}$,
$T_{{\underline{x}}^{\prime(u)},{\underline{s}}^{\prime(u)},{\underline{y}}^{(u)}}=P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}=u}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$.
I.e., corrupting ${\underline{x}}^{\prime}$ using ${\underline{s}}^{\prime}$
results in the received word ${\underline{y}}$. If no
${\underline{x}}^{\prime}\in{\mathcal{L}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
passes the test above, Bob continues in studying the next pair
$(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$ until
eventually finding a codeword and a corresponding message that pass the test.
Once such a codeword is found the decoding process is terminated. If no
codewords pass the test in any of Bob’s iterations, a decoding error is
considered.

###  V-E Analysis

We now show that with high probability over code design it is the case that
for every transmitted message $m$ with high probability over the stochasticity
of Alice the decoding process will succeed. Namely, with high probability over
the stochasticity of Alice, only the the codeword ${\underline{x}}_{(m,r)}$
corresponding to $m$ will pass the unique decoding step.

####  V-E1 Code properties

We start by analyzing some properties of our code:

######  Claim 5 (List size).

With probability at most ${\tt{prob}_{1}}=2^{-n\gamma/4}$ over the code
design, if we choose
$\gamma<{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}/2$,
for any pair
$(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$, the size
of the list produced in the first step of Bob’s decoding exceeds
${\tt{ListSize}}=\frac{2\log|{\mathcal{Y}}|}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}}$.

###### Proof:

Fix a pair $(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$.
For each $u\in{\mathcal{U}}$, define the joint distribution
$P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}=u}=[P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}=u}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}]_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}=u}$
and the “reverse channel” $V_{{\mathbf{x}}|{\mathbf{y}},{\mathbf{u}}=u}$ by
conditioning $P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}=u}$. Consider any
output prefix
${\underline{y}}^{\leq\alpha}=({\underline{y}}(1),{\underline{y}}(2),\ldots,{\underline{y}}(\alpha
K))$ where ${\underline{y}}(u)$ corresponds to chunk $u$ of
${\underline{y}}^{\leq\alpha}$. For each $u$, let
${\mathcal{A}}_{u}({\underline{y}}(u))=\\{{\underline{x}}\in{\mathcal{X}}^{n\varepsilon}:T_{{\underline{x}}}=V_{{\mathbf{x}}|{\mathbf{y}}=T_{{\underline{y}}(u)},{\mathbf{u}}=u}\\}$
be the set of ${\underline{x}}\in{\mathcal{X}}^{n\varepsilon}$ which are
jointly typical with ${\underline{y}}(u)$. Define
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}=\frac{1}{n}(|{\mathcal{X}}|-1)\log(n\varepsilon+1)$,
which goes to $0$ as $n\to\infty$. We have $|{\mathcal{A}}_{k}|\leq
2^{n\varepsilon H({\mathbf{x}}|{\mathbf{y}},{\mathbf{u}}=u)}$. From the code
construction, for each $u\in{\mathcal{U}}^{\leq\alpha}$ we have
$|{\mathcal{T}}_{n\varepsilon}(P_{{\mathbf{x}}|{\mathbf{u}}=u})|\geq
2^{n\varepsilon(H({\mathbf{x}}|{\mathbf{u}}=u)-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}})}$.

We want to show that with high probability over the construction of the code
that the list size will be guaranteed. To emphasize that codewords are random
variables, we write ${\underline{{\mathbf{x}}}}_{(m,r)}^{(u)}$ for the
codeword symbols corresponding to to message $m$, randomness $r$, and chunk
$u$. Fix a message $m$ and let
${\mathcal{C}}^{(u)_{m}}=\\{{\underline{{\mathbf{x}}}}^{(u)}_{(m,r)}:r\in{\mathcal{R}}\\}$
be the set of codeword chunks representing message $m$ in chunk $u$. The
probability over the code construction that a single
${\underline{{\mathbf{x}}}}^{(u)}_{(m,r)}$ uniformly selected from
${\mathcal{T}}_{n\varepsilon}(P_{{\mathbf{x}}|{\mathbf{u}}=u})$ falls in
${\mathcal{A}}_{k}({\underline{y}}(u))$ is

$\displaystyle\eta_{u}\leq\frac{2^{n\varepsilon
H({\mathbf{x}}|{\mathbf{y}},{\mathbf{u}}=u)}}{2^{n\varepsilon(H({\mathbf{x}}|{\mathbf{u}}=u)-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}})}}=2^{-n\varepsilon(I({\mathbf{x}};{\mathbf{y}}|{\mathbf{u}}=u)-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}})}$
(28)

Hence by a union bound, the probability that any element of
${\mathcal{C}}^{(u)_{m}}$ falls in ${\mathcal{A}}_{u}({\underline{y}}(u))$ is
at most $N\eta_{u}$.

With some abuse of notation, we use $\exp(a)=2^{a}$. Since the codebooks in
each chunk are chosen independently, the probability that there exists an $r$
such that ${\underline{{\mathbf{x}}}}^{(u)}_{(m,r)}$ is jointly typical with
${\underline{y}}(u)$ in each chunk $u\leq\alpha K$ is at most

$\displaystyle\eta$ $\displaystyle=\prod_{u=1}^{\alpha
K}N2^{-n\varepsilon(I({\mathbf{x}};{\mathbf{y}}|{\mathbf{u}}=u)-2{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}})}$
(29) $\displaystyle=\exp\left(-n\frac{1}{K}\sum_{u=1}^{\alpha
K}I({\mathbf{x}};{\mathbf{y}}|{\mathbf{u}}=u)+\alpha{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}n+\gamma
n\right)$ (30)
$\displaystyle=\exp\left(-n\left(I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}-\gamma\right)\right).$
(31)

We next have to find an upper bound on the list size. The probability that a
particular set of $L+1$ messages is in the list is upper bounded by
$\eta^{L+1}$. Taking a union bound over all possible lists (there are at most
$2^{nR(L+1)}$) and all $2^{n\log|{\mathcal{Y}}|}$ choices for
${\underline{y}}$, the probability that codebook generation places more than
$L+1$ messages in the list produced by Bob is at most

$\displaystyle\psi=\exp\left(-n\left(I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})(L+1)-R(L+1)-(L+1){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}-(L+1)\gamma-\log|{\mathcal{Y}}|\right)\right)$
(32)

By assumption,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}\leq
I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-R\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}$,
so

$\displaystyle\psi\leq\exp\left(-n(L+1)({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}-\gamma)+n\log|{\mathcal{Y}}|\right)$
(33)

To make this probability less than $1$ we can choose

$\displaystyle
L>\frac{\log|{\mathcal{Y}}|}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}-\gamma}.$
(34)

Now set
$\gamma<{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}/2$.
For sufficiently large $n$ we can make
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{TYP}(\delta)}}$
as small as we like and set

$\displaystyle
L>\frac{2\log|{\mathcal{Y}}|}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}}.$
(35)

to make the probability of not generating a good code smaller than
$2^{-n\gamma/2}$. To guarantee that that the above holds for any pair
$(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$ that may be
used in our decoding procedure, we apply the union bound over $2^{\phi(n)}$
such pairs where
$\phi(n)\leq(|{\mathcal{S}}||{\mathcal{X}}|+1)\log(n\varepsilon)+\log(1/\varepsilon)$.
All in all, for sufficiently large $n$, we conclude that the probability of
not generating a good code is smaller than $2^{-n\gamma/4}$. ∎

For a distribution $P$, let $\Delta_{\delta}(P)$ includes all distributions
within $\ell_{\infty}$ distance $\delta$ from $P$.

######  Claim 6 (Typicality properties).

With probability ${\tt{prob}_{2}}$ over code design it holds for any message
$m$ and any list ${\mathcal{L}}$ of size at most ${\tt{ListSize}}$ obtained in
the decoding process, that

$\displaystyle\left|\left\\{(r_{\alpha
K+1},\ldots,r_{K})\in{\mathcal{R}}^{K(1-\alpha)}:\forall
m^{\prime}\in{\mathcal{L}},\ \forall u\in{\mathcal{U}}^{>\alpha},\,\
\forall(r^{\prime}_{\alpha
K+1},\ldots,r^{\prime}_{K})\in{\mathcal{R}}^{K(1-\alpha)},\,\ \right.\right.$
(36)
$\displaystyle\left.\left.T_{{\underline{x}}_{(m,r_{u})}^{(u)},{\underline{x}}^{\prime(u)}_{(m^{\prime},r^{\prime}_{u})}}\in\Delta_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2})\right\\}\right|\geq(1-{\tt{prob}_{3}})|{\mathcal{R}}|^{K(1-\alpha)}$

###### Proof:

For any $m^{\prime}\in{\mathcal{L}}$ with $m^{\prime}\neq m$ and fixed
$(r_{\alpha K+1},\ldots,r_{K})$ and $(r^{\prime}_{\alpha
K+1},\ldots,r^{\prime}_{K})$, by Sanov’s theorem followed by Pinsker’s
inequality, and finally by setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}=3\varepsilon$,
we have that for any sufficiently large $n$,

$\displaystyle\Pr_{\bf{\underline{x}}_{(m,r_{u})}^{(u)}}\left(\exists
u\in{\mathcal{U}}^{>\alpha},\
T_{{\underline{x}}_{(m,r_{u})}^{(u)},{\underline{x}}^{\prime(u)}_{(m^{\prime},r^{\prime}_{u})}}\notin\Delta_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2})\right)$ $\displaystyle\leq$ $\displaystyle\exp\left(-n\varepsilon
D(P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}^{\otimes
2}\|P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes 2})\right)+c_{1}\log(n)$
$\displaystyle\leq$
$\displaystyle\exp\left(-n\varepsilon\frac{\|P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}^{\otimes
2}-P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2}\|_{1}^{2}}{2\ln(2)}\right)+c_{1}\log(n)$ $\displaystyle\leq$
$\displaystyle\exp\left(-3n\varepsilon^{3}\right).$

(In the inequalities above, $c_{1}$ is a constant independent of the
blocklength $n$.)

Taking a union bound over all
$|{\mathcal{R}}|^{K}=2^{n\gamma/\varepsilon}=2^{n\varepsilon^{3}}$ values of
$(r^{\prime}_{\alpha K+1},\ldots,r^{\prime}_{K})$ and all $|{\mathcal{L}}|$
elements $m^{\prime}$ in ${\mathcal{L}}$, we have that the probability that
the condition in (36) is not satisfied for fixed $(r_{\alpha
K+1},\ldots,r_{K})$ is at most
$|{\mathcal{L}}|\exp\left(-2n\varepsilon^{3}\right)<\exp\left(-\frac{3}{2}n\varepsilon^{3}\right)$
(by bounding $|{\mathcal{L}}|$ from above, very loosely, by Claim 5).

Hence for any given $m$ the expected fraction of $(r_{\alpha
K+1},\ldots,r_{K})$ not satisfying the event of (36) is at most
$\exp\left(-\frac{3}{2}n\varepsilon^{3}\right)$. By standard tail
inequalities, and additional ideas appearing in the analysis of Claim III.21
in [CJL19], the probability that the fraction of $(r_{\alpha
K+1},\ldots,r_{K})$ not satisfying the event of (36) exceeds
$\exp\left(-n\varepsilon^{3}\right)=1-{\tt{prob}_{3}}$ is at most
$\exp\left(-n^{2}\right)$.

The above computation is for a given $\alpha$, $m$, and list ${\mathcal{L}}$.
Hence to conclude the asserted claim we take the union bound over all possible
$\alpha$, $m$, and list ${\mathcal{L}}$, to obtain, for sufficiently large
$n$, ${\tt{prob}_{2}}=1-\exp(-n^{2}/2)$. ∎

From this point on, we assume our code ${\mathcal{C}}$ holds the properties of
Claims 5 and 6.

####  V-E2 Decoding analysis

Consider a message $m$, corresponding codeword transmitted by Alice
${\underline{x}}_{(m,r)}$, and a jamming vector ${\underline{s}}$ used by
James to obtain the received ${\underline{y}}$. Let
$V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})$
satisfy $\forall u\in{\mathcal{U}}$,
$T_{{\underline{x}}^{(u)},{\underline{s}}^{(u)},{\underline{y}}^{(u)}}=P_{{\mathbf{x}}|{\mathbf{u}}=u}V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$.
Let $\alpha^{*}$ satisfy
$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha^{*}}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha^{*}}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$.
By the facts that
$R=C_{K,\delta}-\delta\leq\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}(P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}})-\delta\leq
I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}})-\delta$;
and that
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}\geq\frac{1}{K}\log{|{\mathcal{X}}|}$
we conclude that such $\alpha^{*}\in[K-1]$ exists.

######  Theorem 7 (Correct decoding with
$(\alpha^{*},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$).

When Bob decodes using the pair
$(\alpha^{*},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$,
the message $m$ will pass the two-step decoding of Bob.

###### Proof.

(of Theorem 7) Follows directly by the suggested decoding scheme. ∎

######  Theorem 8 (No decoding when $\alpha\leq\alpha^{*}$).

When Bob decodes using a pair
$(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$ in which
$\alpha\leq\alpha^{*}$, if for the transmitted message
${\underline{x}}_{(m,r)}$ Alice’s stochasticity $r$ of falls into the set of
size $(1-{\tt{prob}_{3}})|{\mathcal{R}}|^{K(1-\alpha)}$ of Claim 6, no message
different from $m$ will be decoded (specifically, no codeword
${\underline{x}}^{\prime}\neq{\underline{x}}$ will pass the test in the
unique-decoding step).

###### Proof.

(of Theorem 8) Assume in contradiction that there exists
$(\alpha,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$ in which
$\alpha\leq\alpha^{*}$ and
${\underline{x}}^{\prime}\neq{\underline{x}}\in{\mathcal{L}}(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
such that the message $m^{\prime}\neq m$ corresponding to
${\underline{x}}^{\prime}$ is decoded by Bob. Let
$T_{{\underline{x}}^{(u)},{\underline{x}}^{\prime(u)}}=P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}$,
$\forall u\in{\mathcal{U}}$. In particular, there exists a vector
${\underline{s}}^{\prime}$ and
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}}$ for which
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
and $\forall u\in{\mathcal{U}}^{>\alpha}$,
$T_{{\underline{x}}^{\prime(u)},{\underline{s}}^{\prime(u)},{\underline{y}}^{(u)}}=P_{{\mathbf{x}}|{\mathbf{u}}=u}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{>\alpha}=u}W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}$.
I.e., corrupting ${\underline{x}}^{\prime}$ using ${\underline{s}}^{\prime}$
results in the received word ${\underline{y}}$.

Using the pair ${\underline{x}}$, ${\underline{x}}^{\prime}$ let
$V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}$
satisfy

$\forall(x,x^{\prime},s,y),\ \forall
u\in{\mathcal{U}}^{>\alpha},\,T_{{\underline{x}}^{(u)},{\underline{x}}^{\prime(u)},{\underline{s}}^{(u)},{\underline{y}}^{(u)}}(x,x^{\prime},s,y)=P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x,x^{\prime})V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)$

and let
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}$
satisfy

$\forall(x,x^{\prime},s,y),\ \forall
u\in{\mathcal{U}}^{>\alpha},\,T_{{\underline{x}}^{(u)},{\underline{x}}^{\prime(u)},{\underline{s}}^{\prime(u)},{\underline{y}}^{(u)}}(x,x^{\prime},s,y)=P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x^{\prime},x)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)$

It follows that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
and
$(V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$.

######  Claim 9.

There exists

$\displaystyle\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\in\operatorname*{argmin}_{\begin{subarray}{c}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}\\\
R\geq
I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}\end{subarray}}{\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})}$
(38)

such that

  1. 1.

$(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$.

  2. 2.

$(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$.

  3. 3.

$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$.

###### Proof.

(of Claim 9) Let
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ be any
distribution satisfying (38). The first claim that
$(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$
follows from the fact that
$R\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$
and thus
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})\leq\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})$
(here we use the nature of $\lambda_{\mathbf{s}}$). A similar analysis holds
for the second claim,
$(\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}})\in{\mathcal{F}}_{\alpha}(P_{{\mathbf{x}}|{\mathbf{u}}})$,
with the additional observation that as $\alpha\leq\alpha^{*}$ we have
$I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\leq
I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha^{*}}})\in[R+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}},R+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}]$.

Finally, the third claim follows from standard convexity arguments coupled by
our assumption that there exists a zero-cost state $s_{0}\in{\mathcal{S}}$ and
a one-to-one mapping $\phi:{\mathcal{Y}}\rightarrow{\mathcal{X}}$ for which
for every $x$,
$W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(\phi(x)|x,s_{0})=1$. More
formally, consider
${V}^{(0)}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ for which
for every $x$ and $u\leq\alpha$,
${V}^{(0)}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}(s_{0}|x,u)=1$.
It holds that
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}V^{(0)}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})=0$,
and that
$I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{(0)}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\geq
I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\geq
R+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}$.
Assume in contradiction that for every
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$
satisfying (38) it holds that
$R\not\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$
or equivalently that
$R>I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}$.
Consider one such
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ and
define the convex combination
$V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}=\lambda\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}+(1-\lambda)V^{(0)}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$
for an arbitrarily small $\lambda>0$. From the linear nature of our cost
function, it follows that
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})\leq\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})$
with equality only if
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})=0$.

For
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})>0$,
we have that
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})<\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})$.
Moreover, from the continuity of
$I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
(in $\lambda$), for sufficiently small $\lambda>0$ we have that
$R>I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}\geq
I(P_{{\mathbf{x}}|{\mathbf{u}}},\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}}$
in contradiction to the definition of
$\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ in (38).
If
$\mathsf{cost}([P_{{\mathbf{x}}|{\mathbf{u}}}\overline{V}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}]_{{\mathbf{s}}^{\leq\alpha}})=0$,
again from the continuity of
$I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$
(in $\lambda$), there exists a $\lambda\in(0,1)$ for which
$R=I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}\in[I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{LB}(\delta)}},I(P_{{\mathbf{x}}|{\mathbf{u}}},V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{UB}(\delta)}}]$,
inplying that
$V^{\lambda}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}}$ satisfies
(38) and can be used to conclude the assertion. ∎

Using Claim 9 and recalling that $R\in{\mathcal{R}}_{\delta}$ we conclude that
there exists $u\in{\mathcal{U}}^{>\alpha}$ such that
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*})\not\in{\mathcal{V}}^{\prime}_{\delta}$.
However, this latter fact is in contradiction with the definition of
$V^{*}_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}$
and
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}$.
In particular, we have for ${\mathbf{u}}=u$ that:

$\forall(x,x^{\prime},y),\
T_{{\underline{x}}^{(u)},{\underline{x}}^{\prime(u)},{\underline{y}}^{(u)}}(x,x^{\prime},y)=\sum_{s\in{\mathcal{S}}}P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x,x^{\prime})V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s),$
$\forall(x,x^{\prime},s,y),\
T_{{\underline{x}}^{(u)},{\underline{x}}^{\prime(u)},{\underline{y}}^{(u)}}(x,x^{\prime},y)=\sum_{s\in{\mathcal{S}}}P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x^{\prime},x)V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}(s|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s).$

In addition, by the assumption that Claim 6 holds, we have that

$T_{{\underline{x}}_{(m,r_{u})}^{(u)},{\underline{x}}^{\prime(u)}}=P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}\in\Delta_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}=u}^{\otimes
2}).$

Moreover, from our code design, we have for $x$ for which
$P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)=0$ we have for any $x^{\prime}$ that
$P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x,x^{\prime})=0$. This
implies that

$\forall(x,x^{\prime}),\
|P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x,x^{\prime})-P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)P_{{\mathbf{x}}|{\mathbf{u}}=u}(x^{\prime})|\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}\cdot{\bf
1}_{P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)\neq 0}\cdot{\bf
1}_{P_{{\mathbf{x}}|{\mathbf{u}}=u}(x^{\prime})\neq 0}$

Now, the above implies that

$\forall(x,x^{\prime},y),\
P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x,x^{\prime})\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)=P_{{\mathbf{x}},{\mathbf{x}}^{\prime}|{\mathbf{u}}=u}(x^{\prime},x)\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}(s^{\prime}|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)$

and thus $\forall(x,x^{\prime},y)$ for which
$P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)\neq 0$ and
$P_{{\mathbf{x}}|{\mathbf{u}}=u}(x^{\prime})\neq 0$:

$\displaystyle\left|\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*}(s|x,x^{\prime})W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x,s)-\sum_{s\in{\mathcal{S}}}V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}(s^{\prime}|x^{\prime},x)W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}(y|x^{\prime},s)\right|\leq\frac{2{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}{P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)P_{{\mathbf{x}}|{\mathbf{u}}=u}(x^{\prime})}$

In contradiction to
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}^{*})\not\in{\mathcal{V}}^{\prime}_{\delta}$
as
$\delta=\frac{2{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{MIN}(\delta)}}^{2}}\geq\frac{2{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{x|u}(\delta)}}}{\min_{x}\\{P_{{\mathbf{x}}|{\mathbf{u}}=u}^{2}(x)\\}}$
where the denominator-minimization is taken over $x$ for which
$P_{{\mathbf{x}}|{\mathbf{u}}=u}(x)\neq 0$. This concludes our proof.

∎

##  VI Converse

To prove Theorem 2 it suffices to prove the following theorem.

######  Theorem 10.

Let
$({\mathcal{X}},{\mathcal{S}},{\mathcal{Y}},\lambda_{{\mathbf{x}}},\lambda_{{\mathbf{s}}},W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}})$
be a causal channel satisfying Items 1, 2, 3 and 4 in Section III-B. For any
$\delta>0,K\geq\frac{2\log|{\mathcal{X}}|}{\delta}+\binom{|{\mathcal{X}}|+1}{2}$
and any code ${\mathcal{C}}\subset{\mathcal{X}}^{n}$ satisfying

  1. 1.

${\mathcal{C}}$ is equipped with an encoder-decoder pair
$(\operatorname{Enc},\operatorname{Dec})\in\Delta({\mathcal{X}}^{n}|{\mathcal{M}})\times\Delta({\mathcal{M}}|{\mathcal{Y}}^{n})$
(both potentially stochastic);

  2. 2.

$T_{{\underline{x}}}\in\lambda_{{\mathbf{x}}}$ for every
${\underline{x}}\in{\mathcal{C}}$;

  3. 3.

$R({\mathcal{C}})\geq\overline{C}_{K,\delta}+\delta$,

the average error probability is at least

$\displaystyle\sup_{\mathrm{Jam}}P_{{\mathrm{e}},\mathrm{avg}}(\operatorname{Enc},\operatorname{Dec},\mathrm{Jam})$
$\displaystyle\geq f(\delta)$

for some $f(\delta)>0$ such that $f(\delta)\xrightarrow{\delta\to 0}0$. The
supremum above is taken over all feasible causal jamming strategies as per
Definition 3. The rate bound $\overline{C}_{K,\delta}$ is defined (for general
$P_{\mathbf{u}}$) as follows:

$\displaystyle\overline{C}_{K,\delta}\coloneqq\max_{\begin{subarray}{c}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})\in\Delta({\mathcal{U}})\times\Delta({\mathcal{X}}|{\mathcal{U}})\\\
\left[P_{\mathbf{u}}P_{{\mathbf{x}}|{\mathbf{u}}}\right]_{\mathbf{x}}\in\lambda_{{\mathbf{x}}}\end{subarray}}\min\Bigg{\\{}$
$\displaystyle\min_{V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})}I(P_{{\mathbf{x}}|{\mathbf{u}}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}),$
$\displaystyle\min_{\begin{subarray}{c}(\alpha,(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}}))\in{\mathcal{A}}\times{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})\\\
\forall
u\in{\mathcal{U}}^{>\alpha},\,V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{u}}^{>\alpha}=u}\in{\mathcal{V}}\end{subarray}}I(P_{{\mathbf{u}}^{\leq\alpha}},P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})\Bigg{\\}},$

where $K_{1}\geq\frac{2\log|{\mathcal{X}}|}{\delta}$,
$K_{2}\geq\binom{|{\mathcal{X}}|+1}{2}$,
${\mathcal{U}}^{\leq\alpha}=\\{u_{1},\cdots,u_{K_{1}}\\}$,
${\mathcal{U}}^{>\alpha}=\\{v_{1},\cdots,v_{K_{2}}\\}$,
$P_{{\mathbf{u}}^{\leq\alpha}}=\operatorname{Unif}({\mathcal{U}}^{\leq\alpha})$,
$P_{{\mathbf{u}}^{>\alpha}}\in\Delta({\mathcal{U}}^{>\alpha})$,
${\mathcal{U}}={\mathcal{U}}^{\leq\alpha}\sqcup{\mathcal{U}}^{>\alpha}$,
$K=K_{1}+K_{2}$, $P_{{\mathbf{u}}}\in\Delta({\mathcal{U}})$ defined as

$\displaystyle P_{{\mathbf{u}}}(u)$ $\displaystyle=\begin{cases}\alpha
P_{{\mathbf{u}}^{\leq\alpha}},&u\in{\mathcal{U}}^{\leq\alpha}\\\
(1-\alpha)P_{{\mathbf{u}}^{>\alpha}(u)},&u\in{\mathcal{U}}^{>\alpha}\end{cases},$

and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}=(K_{1}|{\mathcal{X}}||{\mathcal{S}}|+K_{2}|{\mathcal{X}}|^{2}|{\mathcal{S}}|)\delta$.

######  Remark 2.

In the above upper bound, the distribution
$P_{{\mathbf{u}}}\in\Delta({\mathcal{U}})$ may not be uniform. Specifically,
though its restriction $P_{{\mathbf{u}}^{\leq\alpha}}$ is uniform over
${\mathcal{U}}^{\leq\alpha}$, the counterpart $P_{{\mathbf{u}}^{>\alpha}}$ in
the suffix is not necessarily uniform over ${\mathcal{U}}^{>\alpha}$. This is
because the latter is given by a decomposition of a CP distribution extracted
from the code. However, without loss of generality, one can always fine
quantize the alphabet ${\mathcal{U}}^{>\alpha}$ to make
$P_{{\mathbf{u}}^{>\alpha}}$ uniform at the cost of increasing
$|{\mathcal{U}}^{>\alpha}|$. The resulting bound will match our achievability
bound (Equation 20) upon taking $\delta\to 0$ and we therefore have a capacity
characterization.

##  VII Proof of converse (Theorem 10)

Let ${\mathcal{C}}\subset{\mathcal{X}}^{n}$ be an arbitrary codebook such that
$T_{{\underline{x}}}\in\lambda_{{\mathbf{x}}}$ for every
${\underline{x}}\in{\mathcal{C}}$. Suppose
$R({\mathcal{C}})=R\geq\overline{C}_{K,\delta}+\delta$. Let $M\coloneqq
2^{nR}$ and ${\mathcal{M}}\coloneqq[M]$. Without loss of generality, the
(potentially stochastic) encoder associated with ${\mathcal{C}}$ can be
assumed to take the form
$\operatorname{Enc}\colon{\mathcal{M}}\times{\mathcal{R}}\to{\mathcal{X}}^{n}$
for a certain finite alphabet ${\mathcal{R}}$. The stochastic encoding of a
message $m\in{\mathcal{M}}$ is then given by
$\operatorname{Enc}(m,{\mathbf{r}})\in{\mathcal{X}}^{n}$ where
${\mathbf{r}}\sim\operatorname{Unif}({\mathcal{R}})$. See [DJLS13] for why the
randomness in $\operatorname{Enc}$ can be assumed to come from
${\mathbf{r}}\sim\operatorname{Unif}({\mathcal{R}})$. Let
$N\coloneqq|{\mathcal{R}}|$. For notational convenience, we will also use
${\underline{x}}_{(m,r)}$ to denote $\operatorname{Enc}(m,r)$. We use
$P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}\in\Delta({\mathcal{X}}^{n}|{\mathcal{M}})$
to denote the distribution over codewords induced by $\operatorname{Enc}$:

$\displaystyle P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)$
$\displaystyle=\frac{1}{N}\left|\left\\{r\in{\mathcal{R}}:\operatorname{Enc}(m,r)={\underline{x}}\right\\}\right|.$

Assume also that the decoder associated with ${\mathcal{C}}$ is
$\operatorname{Dec}\in\Delta({\mathcal{M}}|{\mathcal{Y}}^{n})$.

Let $K\geq\frac{2\log|{\mathcal{X}}|}{\delta}$ and $\varepsilon\coloneqq 1/K$.
Set

$\displaystyle{\underline{u}}$
$\displaystyle\coloneqq(\underbracket{1,\cdots,1}_{n\varepsilon},\underbracket{2,\cdots,2}_{n\varepsilon},\cdots,\underbracket{K,\cdots,K}_{n\varepsilon})\in[K]^{n}.$

Let
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}=\delta/2$.
James examines all chunk-wise approximate constant composition subcodes with a
constant fraction of messages. To find such subcodes, for each
$\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|[K])$, James
computes

$\displaystyle{\mathcal{M}}^{\prime}$
$\displaystyle\coloneqq\left\\{m\in{\mathcal{M}}:\exists{\underline{x}}\in{\mathcal{X}}^{n},P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)\mathds{1}{\left\\{\left\|T_{{\underline{u}},{\underline{x}}}-\operatorname{Unif}([K])\times\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}\right\\}}>0\right\\}.$
(39)

Let $M^{\prime}=|{\mathcal{M}}^{\prime}|$. If

$\displaystyle\sum_{m\in{\mathcal{M}}^{\prime}}\sum_{{\underline{x}}\in{\mathcal{X}}^{n}}P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)\mathds{1}{\left\\{\left\|T_{{\underline{u}},{\underline{x}}}-\operatorname{Unif}([K])\times\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}\right\\}}$
$\displaystyle\geq cM$ (40)

for some constant $c>0$ that depends only on
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}},K$
and $|{\mathcal{X}}|$ (but not on $n$), then the following subcode

$\displaystyle{\mathcal{C}}^{\prime}$
$\displaystyle\coloneqq\left\\{{\underline{x}}\in{\mathcal{C}}:\left\|T_{{\underline{u}},{\underline{x}}}-\operatorname{Unif}([K])\times\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{input}(\delta)}}\right\\}$
(41)

will be considered by James. Define also the set ${\mathcal{R}}^{\prime}$ of
encoder randomness associated with ${\mathcal{C}}^{\prime}$ as:

$\displaystyle{\mathcal{R}}^{\prime}\coloneqq\left\\{r^{\prime}\in{\mathcal{R}}:\exists
m^{\prime}\in{\mathcal{M}}^{\prime},\,\operatorname{Enc}(m^{\prime},r^{\prime})\in{\mathcal{C}}^{\prime}\right\\}.$
(42)

Note that, for each subset ${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$, the
associated distribution $\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}$ may not be
unique and therefore the corresponding subcode ${\mathcal{C}}^{\prime}$ may
not be unique. However, by a standard Markov argument, a pair
$({\mathcal{M}}^{\prime},\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}})$ such that
Equation 40 holds for some $c>0$ must exist, and therefore there exists at
least one subcode ${\mathcal{C}}^{\prime}$ which James is looking for.

###  VII-A Babble-only attack

Let ${\mathcal{U}}\coloneqq[K]$ and
$P_{\mathbf{u}}\coloneqq\operatorname{Unif}({\mathcal{U}})$. James picks a
jamming distribution
$V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}}\in{\mathcal{F}}_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{{\mathbf{x}}|{\mathbf{u}}})$.
James causally observes
${\underline{x}}(1),{\underline{x}}(2),\cdots,{\underline{x}}(n)$. He samples
the jamming symbols in the following way: independently for each $1\leq i\leq
n$,

$\displaystyle{\underline{\mathbf{s}}}(i)$ $\displaystyle\sim
V_{{\mathbf{s}}|{\mathbf{x}}={\underline{x}}(i),{\mathbf{u}}={\underline{u}}(i)}.$

###  VII-B Babble-and-push attack

####  VII-B1 Division point and jamming distributions

Suppose James is examining a subcode
${\mathcal{C}}^{\prime}\subset{\mathcal{C}}$ with composition
$\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|[K])$ and a
message set ${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ of size $M^{\prime}$
such that Equation 40 holds for some constant $c>0$.

James picks $\alpha\in\\{0,1/K,2/K,\cdots,1\\}$. Let
${\mathcal{U}}^{\leq\alpha}\coloneqq[\alpha K]$. Let
${\underline{u}}^{\leq\alpha}\in({\mathcal{U}}^{\leq\alpha})^{\alpha n}$ be
the vectors containing the first $\alpha n$ entries of
${\underline{u}}\in[K]^{n}$. Let
$P_{{\mathbf{u}}^{\leq\alpha}}\coloneqq\operatorname{Unif}({\mathcal{U}}^{\leq\alpha})$.
Let
$P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}\in\Delta({\mathcal{X}}|{\mathcal{U}}^{\leq\alpha})$
be the natural restrictions of
$\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|[K])$, i.e.,

$\displaystyle P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}(x|u)$
$\displaystyle\coloneqq\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}(x|u),\quad\forall
u\in{\mathcal{U}}^{\leq\alpha}.$

Since the subcode ${\mathcal{C}}^{\prime}$ is chunk-wise constant composition,
James can compute the average type
$P_{{\mathbf{x}}^{>\alpha}}\in\Delta({\mathcal{X}})$ of the suffices:

$\displaystyle P_{{\mathbf{x}}^{>\alpha}}$
$\displaystyle\coloneqq\frac{1}{(1-\alpha)K}\sum_{u\in{\mathcal{U}}^{>\alpha}}\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}=u}.$

Now James finds a distribution
$\widehat{P}_{{\mathbf{x}},{\mathbf{x}}}\in{\mathsf{CP}}(P_{{\mathbf{x}}^{>\alpha}})$
such that the number (or more precisely the probability mass induced by the
stochastic encoder) of pairs of codewords from ${\mathcal{C}}^{\prime}$ whose
types are approximately $\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$ is
maximized, i.e.,

$\displaystyle\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$
$\displaystyle\coloneqq\operatorname*{argmax}_{Q_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\in{\mathsf{CP}}(P_{{\mathbf{x}}^{>\alpha}})}\sum_{(m,m^{\prime})\in\binom{{\mathcal{M}}^{\prime}}{2}}\sum_{({\underline{x}},{\underline{x}}^{\prime})\in({\mathcal{C}}^{\prime})^{2}}P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}^{\prime}|m^{\prime})\mathds{1}{\left\\{\left\|T_{{\underline{x}},{\underline{x}}^{\prime}}-Q_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}\right\\}},$

where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}=\delta/2$.
Again by a standard Markov-type argument, note that

$\displaystyle\sum_{(m,m^{\prime})\in\binom{{\mathcal{M}}^{\prime}}{2}}\sum_{({\underline{x}},{\underline{x}}^{\prime})\in({\mathcal{C}}^{\prime})^{2}}P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}|m)P_{{\underline{\mathbf{x}}}|{\mathbf{m}}}({\underline{x}}^{\prime}|m^{\prime})\mathds{1}{\left\\{\left\|T_{{\underline{x}},{\underline{x}}^{\prime}}-\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}\right\|_{\infty}\leq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{CP}(\delta)}}\right\\}}$
$\displaystyle\geq c^{\prime}\binom{M^{\prime}}{2}$ (43)

for some constant $c^{\prime}>0$ independent of $n$. Suppose that
$\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$ admits a CP decomposition
of the following form:

$\displaystyle\widehat{P}_{{\mathbf{x}},{\mathbf{x}}^{\prime}}$
$\displaystyle=\sum_{i=1}^{K^{\prime}}P_{{\mathbf{v}}}(v_{i})P_{{\mathbf{x}}|{\mathbf{v}}=v_{i}}^{\otimes
2},$

for a constant $K^{\prime}\subset{\mathbb{Z}}_{\geq 1}$, a time-sharing
distribution $P_{\mathbf{v}}\in\Delta(\\{v_{1},\cdots,v_{K^{\prime}}\\})$ and
a conditional distribution
$P_{{\mathbf{x}}|{\mathbf{v}}}\in\Delta({\mathcal{X}}|\\{v_{1},\cdots,v_{K^{\prime}}\\})$.

We then define the overall time-sharing structure. Define
${\mathcal{U}}^{>\alpha}\coloneqq\\{v_{1},\cdots,v_{K^{\prime}}\\}$ and
${\mathcal{U}}\coloneqq{\mathcal{U}}^{\leq\alpha}\sqcup{\mathcal{U}}^{>\alpha}$.
Let $P_{{\mathbf{u}}}\in\Delta({\mathcal{U}})$ be defined as

$\displaystyle P_{{\mathbf{u}}}(u)$
$\displaystyle\coloneqq\begin{cases}1/K,&u\in{\mathcal{U}}^{\leq\alpha}\\\
(1-\alpha)P_{{\mathbf{v}}}(u),&u\in{\mathcal{U}}^{>\alpha}\end{cases}.$

Note that $P_{{\mathbf{u}}}$ is a valid distribution since

$\displaystyle\sum_{u\in{\mathcal{U}}}P_{{\mathbf{u}}}(u)$
$\displaystyle=\alpha
K\cdot\frac{1}{K}+(1-\alpha)\sum_{v\in{\mathcal{U}}^{>\alpha}}P_{{\mathbf{v}}}(v)=\alpha+(1-\alpha)=1.$

The input distribution
$P_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$ under
this time-sharing structure can be defined as follows:

$\displaystyle P_{{\mathbf{x}}|{\mathbf{u}}}(x|{u})$
$\displaystyle\coloneqq\begin{cases}{P}_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}}(x|{u}),&{u}\in{\mathcal{U}}^{\leq\alpha}\\\
P_{{\mathbf{x}}|{\mathbf{v}}}(x|{u}),&{u}\in{\mathcal{U}}^{>\alpha}\end{cases}.$

For each subcode, James is able to perform the above computation. James
examines every chunk-wise (approximate) constant composition subcode that
satisfies Equation 40 for some constant $c>0$ (independent of $n$), and finds
$\alpha\in{\mathcal{A}}$ and
$(V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{x}}^{\prime},{\mathbf{v}}})\in{\mathcal{F}}_{\alpha,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tt{s}_{state}(\delta)}}}(P_{\mathbf{u}},P_{{\mathbf{x}}|{\mathbf{u}}})$
that minimizes
$I(P_{{\mathbf{u}}^{\leq\alpha}},P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})$.
Finally, James picks the subcode ${\mathcal{C}}^{\prime}\subset{\mathcal{C}}$
(as per Equation 41) whose induced minimum mutual information is the minimum
among all subcodes under consideration. Suppose that this
${\mathcal{C}}^{\prime}$ is associated with a message set
${\mathcal{M}}^{\prime}\subset{\mathcal{M}}$ (as per Equation 39) and encoding
randomness ${\mathcal{R}}^{\prime}\subset{\mathcal{R}}$ (as per Equation 42).
By the assumption

$\displaystyle R\geq\overline{C}_{K,\delta}+\delta,$ (44)

the coding rate $R$ must be larger than the minimum mutual information induced
by ${\mathcal{C}}^{\prime}$ by at least an additive factor $\approx\delta$.
More precisely, James can guarantee that

$\displaystyle R\geq
I(P_{{\mathbf{u}}^{\leq\alpha}},P_{{\mathbf{x}}|{\mathbf{u}}^{\leq\alpha}},V_{{\mathbf{s}}|{\mathbf{x}},{\mathbf{u}}^{\leq\alpha}})+\delta/2,$
(45)

where the RHS is the mutual information computed from the subcode
${\mathcal{C}}^{\prime}$, by setting $K$ to be sufficiently large, e.g.,
$K\geq(2\log|{\mathcal{X}}|)/\delta$. Indeed, this follows from the following
simple bound: for any $u\in[K]$,

$\displaystyle\frac{1}{K}I({\mathbf{x}}_{u};{\mathbf{y}}_{u})$
$\displaystyle\leq\frac{1}{K}H({\mathbf{x}}_{u})\leq\frac{1}{K}\log|{\mathcal{X}}|\leq\frac{\delta}{2}.$

######  Remark 3.

In the suffix, we allow James to ignore the chunk-wise (approximate) constant
composition structure of the subcode ${\mathcal{C}}^{\prime}$. In principle,
he could have tailored his jamming distribution to
$P_{{\mathbf{x}}|{\mathbf{u}}^{>\alpha}}$ (which is the natural restriction of
$\widehat{P}_{{\mathbf{x}}|{\mathbf{u}}}$ to
$u\in[K]\setminus{\mathcal{U}}^{\leq\alpha}$). This will create a two level
time-sharing structure in the suffix: the top level being the chunk-wise
structure given by ${\mathbf{u}}^{>\alpha}$, and the bottom level being the
time-sharing structure given by CP distributions in each suffix chunk.
However, this will not have an effective impact on the converse bound we are
aiming for. This is because $(i)$ the suffix is symmetrized by James and hence
does not effectively carry positive amount of information, and $(ii)$ the
chunk-wise composition structure does not change the zero-rate threshold