Assisted Identification over Modulo-Additive Noise Channels

Abstract

The gain in the identification capacity afforded by a rate-limited description of the noise sequence corrupting a modulo-additive noise channel is studied. Both the classical Ahlswede–Dueck version and the Ahlswede–Cai–Ning–Zhang version, which does not allow for missed identifications, are studied. Irrespective of whether the description is provided to the receiver, to the transmitter, or to both, the two capacities coincide and both equal the helper-assisted Shannon capacity.

1. Introduction

If a helper can observe the additive noise corrupting a channel and can describe it to the decoder, then the latter can subtract it and thus render the channel noiseless. However, for this to succeed, the description must be nearly lossless and hence possibly of formidable rate. It is thus of interest to study scenarios where the description rate is limited, and to understand how the rate of the help affects performance.

When performance is measured in terms of the Shannon capacity, the problem was solved for a number of channel models [1,2,3], where the former two address assistance to the decoder and the latter to the encoder. When performance was measured in terms of the erasures-only capacity or the list-size capacity, the problem was solved in [4,5]. Error exponents with assistance were studied in [6]. Here we study how rate-limited help affects the identification capacity [7].

We focus on the memoryless modulo-additive channel (MMANC), whose time-k output $Y_k$ corresponding to the time-k input $x_k$ is:

$$Y_k=x_k\oplus Z_k$$

(1)

where $Z_k$ is the time-k noise sample; the channel input $x_k$, the channel output $Y_k$, and the noise $Z_k$ all take values in the set $\mathcal{A}$—also denoted $\mathcal{X}$, or $\mathcal{Y}$, or $\mathcal{Z}$—comprising the $\left|\mathcal{A}\right|$ elements $\{0,\dots ,|\mathcal{A}|-1\}$; and ⊕ and ⊖ denote mod-$\left|\mathcal{A}\right|$ addition and subtraction, respectively. The noise sequence $\left\{Z_k\right\}$ is IID $\sim P_Z$, where $P_Z$ is some PMF on $\mathcal{A}$.

Irrespective of whether the help is provided to the encoder, to the decoder, or to both, the Shannon capacity of this channel coincides with its erasures-only capacity, and both are given by [3] (Section V) and [4] (Theorems 2 and 6):

$$C_{\text{e-o}}\left(R_{\mathrm{h}}\right)=C_{\mathrm{S}\mathrm{h}}\left(R_{\mathrm{h}}\right)=log\left|\mathcal{A}\right|-{\left\{H\left(P_Z\right)-R_{\mathrm{h}}\right\}}^{+}$$

(2)

where ${\left\{\xi \right\}}^{+}$ denotes $max\{0,\xi \}$, and $H\left(P_Z\right)$ is the Shannon entropy of $P_Z$.

Here we study two versions of the identification capacity of this channel: Ahlswede and Dueck’s original identification capacity $C_{\mathrm{ID}}$ [7], and the identification capacity subject to no missed-identifications $C_{\mathrm{ID},0}$ [8]. Our main result is that—irrespective of whether the help is provided to the encoder, to the decoder, or to both—the two identification capacities coincide and both equal the right-hand side (RHS) of (2).

2. Problem Formulation

The identification-over-a-channel problem is parameterized by the blocklength n, which tends to infinity in the definition of the identification capacity. The n-length noise sequence $Z^n\in {\mathcal{A}}^n$ is presented to a helper, which produces its $n{R}_{\mathrm{h}}$-bit description $t\left(Z^n\right)$:

$$t\left(z^n\right)\in \mathcal{T}$$

(3)

where:

$$\mathcal{T}={\{0,1\}}^{n{R}_{\mathrm{h}}}.$$

(4)

We refer to the set $\mathcal{N}=\{1,\dots ,\mathsf{N}\}$ as the set of identification messages and to its cardinality $\mathsf{N}$ as the number of identification messages. The identification rate is defined (for $\mathsf{N}$ sufficiently large) as:

$$\frac{1}{n}loglog\mathsf{N}.$$

(5)

A generic element of $\mathcal{N}$—namely, a generic identification message—is denoted i.

If no help is provided to the encoder, then the latter is specified by a family ${\left\{P_{X^n}^i\right\}}_{i\in \mathcal{N}}$ of PMFs on ${\mathcal{A}}^n$ that are indexed by the identification messages, with the understanding that, to convey the identification message (IM) i, the encoder transmits a random sequence in ${\mathcal{A}}^n$ that it draws according to the PMF $P_{X^n}^i$. If help $T=t\left(Z^n\right)\in \mathcal{T}$ is provided to the encoder, then the encoder’s operation is specified by a family of PMFs ${\left\{P_{X^n|t}^i\right\}}_{(i,t)\in \mathcal{N}\times \mathcal{T}}$ that is now indexed by pairs of identification messages and noise descriptions, with the understanding that, to convey IM i given the description $T=t\left(Z^n\right)$, the encoder produces a random n-length sequence of channel inputs that is distributed according to $P_{X^n|T}^i$. In either case, the channel output sequence $Y^n$ is:

$$Y^n=X^n\oplus Z^n$$

(6)

componentwise.

If help is provided to the encoder, and if IM i is to be conveyed, then the joint distribution of $(X^n,Z^n,Y^n,T)$ has the form:

$$P_{Z^n}\left(z^n\right)P_{T|Z^n}\left(t\right|z^n)P_{X^n|T}^i\left(x^n\right|t)P_{Y^n|X^n,Z^n}\left(y^n\right|x^n,z^n)$$

(7)

where

$$P_{Y^n|X^n,Z^n}\left(y^n\right|x^n,z^n)=𝟙\left\{y^n=x^n\oplus z^n\right\}$$

(8)

and where

$$P_{T|Z^n}\left(t\right|z^n)=𝟙\left\{t=t\left(z^n\right)\right\}$$

(9)

because we are assuming that the noise description is a deterministic function of the noise sequence. (The results also hold if we allow randomized descriptions: our coding schemes employ deterministic descriptions and the converse allows for randomization.) Here $𝟙\left\{\mathrm{statement}\right\}$ equals 1 if the statement holds and equals 0 otherwise. In the absence of help, the joint distribution has the form:

$$P_{Z^n}\left(z^n\right)P_{T|Z^n}\left(t\right|z^n)P_{X^n}^i\left(x^n\right)P_{Y^n|X^n,Z^n}\left(y^n\right|x^n,z^n).$$

(10)

Based on the data available to it—$Y^n$ in the absence of help to the decoder and $(Y^n,t\left(Z^n\right))$ in its presence—the receiver performs $\mathsf{N}$ binary tests indexed by $i\in \mathcal{N}$, where the i-th test is whether or not the IM is i. It accepts the hypothesis that the IM is i if $Y^n$ is in its acceptance region, which we denote ${\mathcal{D}}_i\left(t\right)\in {\mathcal{A}}^n$ in the presence of decoder assistance $t\in \mathcal{T}$ and ${\mathcal{D}}_i\in {\mathcal{A}}^n$ in its absence.

When the help $t\in \mathcal{T}$ is provided to the receiver, the probability of missed detection associated with IM $i\in \mathcal{N}$ is thus:

$$p_{\mathrm{MD}}^i\left(t\right)=1-P_{Y^n|T=t}^i\left({\mathcal{D}}_i\left(t\right)\right)$$

(11)

and the worst-case false alarm associated with it is:

$$p_{\mathrm{FA}}^i\left(t\right)={\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}{P}_{Y^n|T=t}^j\left({\mathcal{D}}_i\left(t\right)\right).$$

(12)

Note that, given $t\in \mathcal{T}$, the acceptance regions ${\left\{{\mathcal{D}}_i\left(t\right)\right\}}_{i\in \mathcal{N}}$ of the different tests need not be disjoint. We define:

$$p_{\mathrm{MD},\max }={\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)p_{\mathrm{MD}}^i\left(t\right)$$

(13)

and:

$$p_{\mathrm{FA},\max }={\displaystyle {\displaystyle \underset{i\in \mathcal{N}}{max}}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)p_{\mathrm{FA}}^i\left(t\right).$$

(14)

In the absence of help to the receiver, the probability of missed detection associated with IM i is:

$$p_{\mathrm{MD}}^i=1-{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)P_{Y^n|T=t}^i\left({\mathcal{D}}_i\right)=1-P_{Y^n}^i\left({\mathcal{D}}_i\right)$$

(15)

and the worst-case probability of false alarm associated with it is:

$$p_{\mathrm{FA}}^i={\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}{P}_{Y^n|T=t}^j\left({\mathcal{D}}_i\right).$$

(16)

In this case, we define:

$$p_{\mathrm{MD},\max }={\displaystyle \underset{i\in \mathcal{N}}{max}}{p}_{\mathrm{MD}}^i$$

(17)

and:

$$p_{\mathrm{FA},\max }={\displaystyle \underset{i\in \mathcal{N}}{max}}{p}_{\mathrm{FA}}^i.$$

(18)

In both cases we say that a scheme is of zero missed detectionsif $p_{\mathrm{MD},\max }$ is zero.

A rate R is an achievable identification rate if, for every $\gamma >0$ and every $ϵ>0$, there exists some positive integer $n_0$ such that, for all blocklengths n exceeding $n_0$, there exists a scheme with:

$$\mathsf{N}=\lceil 2^{2^{n(R-\gamma )}}\rceil$$

(19)

identification messages for which:

$$max\{p_{\mathrm{MD},\max },p_{\mathrm{FA},\max }\}<ϵ.$$

(20)

The supremum of achievable rates is the identification capacity with a helper $C_{\mathrm{ID}}\left(R_{\mathrm{h}}\right)$. Replacing requirement (20) with:

$$p_{\mathrm{MD},\max }=0,p_{\mathrm{FA},\max }<ϵ$$

(21)

leads to the definition of the zero missed-identification capacity $C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)$.

Remark 1.

Writing out $p_{\mathrm{FA},\max }$ of (14) as:

$$p_{\mathrm{FA},\max }={\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}{P}_{Y^n|T=t}^j\left({\mathcal{D}}_i\left(t\right)\right)$$

(22)

highlights that (prior to maximizing over i) we first maximize over j and then average the result over t. In this sense, the help—even if provided to both encoder and decoder—cannot be viewed as “common randomness” in the sense of [9,10,11] where the averaging over the common randomness is performed before taking the maximum. Our criterion is more demanding of the direct part (code construction) and less so of the converse.

Both criteria are interesting. Ours allows for the notion of “outage”, namely, descriptions that indicate that identification might fail and that therefore call for retransmission. The other criterion highlights the interplay between the noise description and the generation of common randomness (particularly when the help is provided to both transmitter and receiver).

The following theorem is the main result of this paper.

Theorem 1.

On the modulo additive noise channel—irrespective of whether the help is provided to the transmitter, to the receiver, or to both—the identification capacity with a helper $C_{\mathrm{ID}}\left(R_{\mathrm{h}}\right)$ and the zero missed-identification capacity with a helper $C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)$ are equal and coincide with the Shannon capacity:

$$C_{\mathrm{ID}}\left(R_{\mathrm{h}}\right)=C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)=C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$$

(23)

where the latter is given in (2).

We prove this result by establishing in Section 3 that $C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)\ge C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$ using a slight strengthening of recent results in [4] in combination with the code construction proposed in [8]. The converse is proved in Section 4, where we use a variation on a theme by Watanabe [12] to analyze the case where the assistance is provided to both transmitter and receiver.

3. Direct Part: Zero Missed Detection

In this section we prove that:

$$C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)\ge C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$$

(24)

by proposing identification schemes of no missed detections and of rates approaching $C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$. To this end, we extend to the helper setting the connection—due to Ahlswede, Cai, and Zhang [8]—between the zero-missed-detection identification capacity $C_{\mathrm{ID},0}$ and the erasures-only capacity $C_{\text{e-o}}$. We then call on recent results [4] to infer that, on the modulo-additive noise channel with a helper, the Erasures-Only capacity is equal to the Shannon capacity. We treat encoder-only assistance and decoder-only assistance separately. Either case also proves achievability when the assistance is provided to both encoder and decoder.

Recall that an erasures-only decoder produces a list $\mathcal{L}$ comprising the messages under which the observation is of positive likelihood and then act as follows: If the list contains only one message, it produces that message; otherwise, it declares an erasure. Since the list always contains the transmitted message, this decoder never errs. The erasures-only capacity is defined like the Shannon capacity, but with the additional requirement that the decoder be the erasures-only decoder. This notion extends in a natural way to settings with a helper [4].

3.1. Encoder Assistance

A rate-R, blocklength-n, encoder-assisted, erasures-only transmission code comprises a message set $\mathcal{M}=\{1,\dots ,\mathsf{M}\}$ with $\mathsf{M}=2^{nR}$ messages and a collection of $\mathsf{M}$ mappings ${\left\{f_m\right\}}_{m\in \mathcal{M}}$ from $\mathcal{T}$ to ${\mathcal{X}}^n$, indexed by $\mathcal{M}$, with the understanding that to transmit Message m after being presented with the help $t\left(Z^n\right)\in \mathcal{T}$, the encoder produces the n-tuple of channel inputs $f_m\left(t\left(Z^n\right)\right)\in {\mathcal{X}}^n$. Since the decoder observes only the channel outputs (and not the help), it forms the list:

$$\mathcal{L}\left(y^n\right)=\left\{m\in \mathcal{M}:\exists t\in \mathcal{T}\mathrm{s}.\mathrm{t}.P_{Y^n|X^n,T}\left(y^n|f_m\left(t\right),t)\right)>0\right\}.$$

(25)

The collection of output sequences that cause the erasures-only decoder to produce an erasure is:

$${\mathcal{Y}}_{\mathrm{er}}=\left\{y^n\in {\mathcal{A}}^n:\left|\mathcal{L}\left(y^n\right)\right|>1\right\}.$$

(26)

The probability of erasure associated with the transmission of Message m with encoder help t is $P_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)$. On the modulo additive noise channel with rate-$R_{\mathrm{h}}$ encoder assistance, the erasures-only capacity and the Shannon capacity coincide and [4]:

$$C_{\text{e-o}}\left(R_{\mathrm{h}}\right)=C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)=log\left|\mathcal{A}\right|-{\left\{H\left(P_Z\right)-R_{\mathrm{h}}\right\}}^{+}.$$

(27)

We shall need the following slightly-stronger version of the achievability part of this result, where we swap the maximization over the messages with the expectation over the help:

Proposition 1.

Consider the modulo additive noise channel with rate-$R_{\mathrm{h}}$ encoder assistance. For any transmission rate R smaller than $C_{\text{e-o}}\left(R_{\mathrm{h}}\right)$ of (27)), there exists a sequence of rate-R transmission codes for which:

$${\displaystyle \underset{n\to \infty }{lim}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{m\in \mathcal{M}}{max}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)=0.$$

(28)

A similar result holds for decoder assistance.

Proof. 

The proof is presented in Appendix A. It is based on the construction in [4], but with a slightly finer analysis. □

The coding scheme we propose is essentially that of [8]. We just need to account for the help. For each blocklength n, we start out with a transmission code of roughly $2^{n{C}_{\text{e-o}}\left(R_{\mathrm{h}}\right)}$ codewords for which (28) holds, and use Lemma 1 ahead to construct approximately $2^{2^{n{C}_{\text{e-o}}\left(R_{\mathrm{h}}\right)}}$ lightly-intersecting subsets of its message set. We then associate an IM with each of the subsets, with the understanding that to transmit an IM we pick uniformly at random one of the messages in the subset associated with it and transmit this message with the helper’s assistance.

Lemma 1

([7] Proposition 14). Let $\mathcal{Z}$ be a finite set, and let $\lambda \in (0,\frac{1}{2})$ be given. If $ϵ>0$ is sufficiently small so that:

$$\lambda log\left(\frac{1}{ϵ}-1\right)>2\mathrm{and}\frac{1}{ϵ}>6$$

(29)

then there exist subsets ${\mathcal{A}}_1,\dots ,{\mathcal{A}}_{\mathsf{N}}$ of $\mathcal{Z}$ such that for all distinct $i,j\in \{1,\dots ,\mathsf{N}\}$ the following hold:

$$\begin{array}{}\mathrm{(30)}& \left(a\right)\hfill & \hfill |{\mathcal{A}}_i|& =& ⌊ϵ\left|\mathcal{Z}\right|⌋,\hfill \mathrm{(31)}& \left(b\right)\hfill & \hfill |{\mathcal{A}}_i\cap {\mathcal{A}}_j|& <& \lambda ⌊ϵ\left|\mathcal{Z}\right|⌋,\hfill \mathrm{(32)}& \left(c\right)\hfill & \hfill \mathsf{N}& \ge & {\left|\mathcal{Z}\right|}^{-1}·2^{\lfloor ϵ\left|\mathcal{Z}\right|\rfloor }-1.\hfill \end{array}$$

With the aid of this lemma, we can now prove the achievability of $C_{\text{e-o}}\left(R_{\mathrm{h}}\right)$.

Proof. 

Given an erasures-only encoder-assisted transmission code ${\left\{\left(f_m\right)\right\}}_{m\in \mathcal{M}}$ where $f_m:\mathcal{T}\to {\mathcal{X}}^n$, we apply Lemma 1 to the transmission message set $\mathcal{M}$ with:

$$ϵ=\frac{1}{n^2+2}\mathrm{and}\lambda =\frac{1}{logn}$$

(33)

to infer, for large enough n, the existence of subsets ${\mathcal{F}}_1,\dots ,{\mathcal{F}}_{\mathsf{N}}\subseteq \mathcal{M}$ such that for all distinct $i,j\in \{1,\dots ,\mathsf{N}\}$ with $j\ne i$:

$$\begin{array}{}\mathrm{(34)}& \hfill |{\mathcal{F}}_i|& =& ⌊\frac{\mathsf{M}}{n^2+2}⌋\hfill \mathrm{(35)}& \hfill |{\mathcal{F}}_i\cap {\mathcal{F}}_j|& <& \frac{1}{logn}⌊\frac{\mathsf{M}}{n^2+2}⌋\hfill \mathrm{(36)}& \hfill \mathsf{N}& \ge & {\mathsf{M}}^{-1}·2^{⌊\frac{\mathsf{M}}{n^2+2}⌋}-1.\hfill \end{array}$$

Note that (36) implies that:

$${\displaystyle \underset{n\to \infty }{{\displaystyle \underline{lim}}}}\left(\frac{1}{n}loglog\mathsf{N}-\frac{1}{n}log\mathsf{M}\right)\ge 0.$$

(37)

To send IM i after obtaining the assistance $t\left(z^n\right)$, the encoder picks a random element M from ${\mathcal{F}}_i$ equiprobably and transmits $X^n=f_M\left(t\left(Z^n\right)\right)$, so:

$$P_{X^n|T}^i\left(x^n\right|t)=\frac{1}{|{\mathcal{F}}_i|}{\displaystyle \sum _{m\in {\mathcal{F}}_i}}𝟙\left\{x^n=f_m\left(t\right)\right\}.$$

(38)

To guarantee no missed detections, we set the acceptance region of i-th IM to be:

$${\mathcal{D}}_i=\left\{y^n\in {\mathcal{Y}}^n:\exists (m,t)\in {\mathcal{F}}_i\times \mathcal{T}\mathrm{s}.\mathrm{t}.P_{Y^n|X^n,T}\left(y^n|f_m\left(t\right),t\right)>0\right\}.$$

(39)

It now remains to analyze the scheme’s maximal false-alarm probability.

$$\begin{array}{}\mathrm{(40)}& \hfill p_{\mathrm{FA},\max }& =\hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}{P}_{Y^n|T=t}^j\left({\mathcal{D}}_i\right)\hfill \mathrm{(41)}& & =\hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\frac{1}{|{\mathcal{F}}_j|}{\displaystyle \sum _{m\in {\mathcal{F}}_j}}{P}_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)\hfill \mathrm{(42)}& & =\hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\frac{1}{|{\mathcal{F}}_j|}[{\displaystyle \sum _{m\in {\mathcal{F}}_j\setminus {\mathcal{F}}_i}}{P}_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)\hfill & & & +{\displaystyle \sum _{m\in {\mathcal{F}}_j\cap {\mathcal{F}}_i}}{P}_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)]\hfill \mathrm{(43)}& & \le \hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\frac{1}{|{\mathcal{F}}_j|}\left[{\displaystyle \sum _{m\in {\mathcal{F}}_j\setminus {\mathcal{F}}_i}}{P}_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)+\left|{\mathcal{F}}_j\cap {\mathcal{F}}_i\right|\right]\hfill \mathrm{(44)}& & \le \hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\frac{1}{|{\mathcal{F}}_j|}\left[{\displaystyle \sum _{m\in {\mathcal{F}}_j\setminus {\mathcal{F}}_i}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)+\left|{\mathcal{F}}_j\cap {\mathcal{F}}_i\right|\right]\hfill \mathrm{(45)}& & <\hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\left\{\frac{1}{|{\mathcal{F}}_j|}{\displaystyle \sum _{m\in {\mathcal{F}}_j\setminus {\mathcal{F}}_i}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)+\frac{\lfloor \frac{\mathsf{M}}{n^2+2}\rfloor }{|{\mathcal{F}}_j|log n}\right\}\hfill \mathrm{(46)}& & \le \hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\left\{\frac{\left|{\mathcal{F}}_j\setminus {\mathcal{F}}_i\right|}{|{\mathcal{F}}_j|}{\displaystyle \underset{m\in \mathcal{M}}{max}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)\right\}+\frac{1}{log n}\hfill \mathrm{(47)}& & \le \hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{j\in \mathcal{N}\setminus \left\{i\right\}}{max}}\left\{{\displaystyle \underset{m\in \mathcal{M}}{max}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)\right\}+\frac{1}{log n}\hfill \mathrm{(48)}& & =\hfill & {\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right){\displaystyle \underset{m\in \mathcal{M}}{max}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)+\frac{1}{log n}\hfill \end{array}$$

where in (41) we expressed $P_{Y^n|T=t}^j\left({\mathcal{D}}_i\right)$ as $P_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)$ using (7); in (42) we expressed ${\mathcal{F}}_j$ as the disjoint union of ${\mathcal{F}}_j\cap {\mathcal{F}}_i$ and ${\mathcal{F}}_j\setminus {\mathcal{F}}_i$; in (43) we used the trivial bound:

$$P_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)\le 1;$$

(49)

in (44) we used the fact that whenever $m\ne i$:

$$P_{Y^n|X^n,T}\left({\mathcal{D}}_i|f_m\left(t\right),t\right)\le P_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)$$

(50)

which holds because, by the definition of the set ${\mathcal{Y}}_{\mathrm{er}}$, any output sequence $y^n$ that contributes to the LHS of (50), i.e., that is in ${\mathcal{D}}_i$ with $P_{Y^n|X^n,T}\left(y^n|f_m\left(t\right),t\right)>0$, must also be in ${\mathcal{Y}}_{\mathrm{er}}$; in (45) we used (35); in (46) we replaced each term in the sum with the global maximum (over $m\in \mathcal{M}$) and used (34); in (47) we used the trivial bound $|{\mathcal{F}}_j\setminus {\mathcal{F}}_i|\le |{\mathcal{F}}_j|$; and in (48) we could simplify the expression because the dependence on i and j is no longer.

The above construction demonstrates that every transmission scheme that drives ${\sum }_{t\in \mathcal{T}}{P}_T\left(t\right){max}_{m\in \mathcal{M}}{P}_{Y^n|X^n,T}\left({\mathcal{Y}}_{\mathrm{er}}|f_m\left(t\right),t\right)$ to zero induces a zero missed-identification scheme that drives the false-alarm probability to zero. Since the former exists for all rates up to $C_{\text{e-o}}\left(R_{\mathrm{h}}\right)$, we conclude, by (37), that $C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)\ge C_{\text{e-o}}\left(R_{\mathrm{h}}\right)$. This, in turn, implies that $C_{\mathrm{ID},0}\left(R_{\mathrm{h}}\right)\ge C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$ and hence concludes the achievability proof for encoder-assistance because, on the modulo additive noise channel, $C_{\text{e-o}}\left(R_{\mathrm{h}}\right)=C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$. □

3.2. Decoder Assistance

When, rather than to the encoder, the assistance is to the decoder, the transmission codewords are n-tuples in ${\mathcal{A}}^n$, and we denote the transmission codebook $\mathcal{C}={\left\{x^n\left(m\right)\right\}}_{m\in \mathcal{M}}$. For the induced identification scheme we use the same message subsets as before, with IM i being transmitted by choosing uniformly at random a message M from the subset ${\mathcal{F}}_i$ and transmitting the codeword $x^n\left(M\right)$. To avoid any missed detections, we set the acceptance region corresponding to IM i and decoder assistance t to be:

$${\mathcal{D}}_i\left(t\right)=\{y^n\in {\mathcal{A}}^n:\exists m\in {\mathcal{F}}_i\mathrm{s}.\mathrm{t}.P_{Y^n,T|X^n}\left(y^n,t|x^n\left(m\right)\right)>0\}$$

(51)

The analysis of the false-alarm probability is nearly identical to that with encoder assistance and is omitted.

4. Converse Part: Help Provided to Both Transmitter and Receiver

In this section we establish the converse for all the cases of interest by proving that the inequality:

$$C_{\mathrm{ID}}\left(R_{\mathrm{h}}\right)\le log\left|\mathcal{A}\right|-{\left\{H\left(P_Z\right)-R_{\mathrm{h}}\right\}}^{+}$$

(52)

holds even when the help is provided to both encoder and decoder. The RHS of (52) is the helper Shannon capacity, irrespective of whether the help is provided to the encoder, to the decoder, or to both [3] (Section V).

There are two main steps to the proof. The first addresses the conditional probabilities of the two types of testing errors conditional on a given description $T=t$. It relates the two to the conditional entropy of the noise given the description, namely, $H\left(Z^n\right|T=t)$. Very roughly, this corresponds to proving the converse part of the ID-capacity theorem for the channel whose noise is distributed according to the conditional distribution of $Z^n$ given $T=t$. The difficulty in this step is that, given $T=t$, the noise is not memoryless, and the channel may not even be stable. Classical type-based techniques for proving the converse part of the ID-capacity theorem—such as those employed in [7] (Theorem 12), [13] (Section III), or [14] (Section III)—are therefore not applicable. Instead, we extend to the helper setting Watanabe’s technique [12], which is inspired by the partial channel resolvability method introduced by Steinberg [15].

The second step in the proof addresses the unconditional error probabilities. This step is needed because, in the definition of achievability (see (13) and (14)), the error probabilities are averaged over the noise description t. We will show that, when the identification rate exceeds the Shannon capacity, there exists an IM $i^{*}$ for which the sum of the two types of errors is large whenever the description t is in a subset ${\mathcal{T}}^{*}$ of $\mathcal{T}$ whose probability is bounded away from zero. This will imply that, for this IM $i^{*}$, the sum of the averaged probabilities of error is bounded away from zero, thus contradicting the achievability.

4.1. Additional Notation

Given a PMF $P_X$ and a conditional PMF $P_{Y|X}$, we write $P_X\circ P_{Y|X}$ for the joint PMF that assigns the pair $(x,y)$ the probability $P_X\left(x\right)P_{Y|X}\left(y\right|x)$. We use $I_{P\circ P_{Y|X}}(X;Y)$ to denote the mutual information between X and Y under the joint distribution $P\circ P_{Y|X}$. The product PMF of marginals $P_X$ and $P_Y$ is denoted $P_X\times P_Y$; it assigns $(x,y)$ the probability $P_X\left(x\right)P_Y\left(y\right)$.

For the hypothesis testing problem of guessing whether some observation X was drawn $\sim P_X$ (the “null hypothesis”) or $\sim Q_X$ (the “alternative hypothesis”), we use $K(·|X)$ to denote a generic randomized test that, after observing $X=x$, guesses the null hypothesis ($X\sim P_X$) with probability $K\left(0\right|X=x)$ and the alternative ($X\sim Q_X$) with probability $K\left(1\right|X=x)$. (Here $K\left(0\right|X=x)+K(1|X=x)=1$ for every $x\in \mathcal{X}$.) The type I error probability associated with $K(·|X)$ is:

$${\lambda }_1\left[K\right]={\displaystyle \sum _{x\in \mathcal{X}}}{P}_X\left(x\right)K\left(1\right|x)$$

(53)

and the type II:

$${\lambda }_2\left[K\right]={\displaystyle \sum _{x\in \mathcal{X}}}{Q}_X\left(x\right)K\left(0\right|x).$$

(54)

For a given $0<ϵ<1$ we define:

$${\beta }_{ϵ}(P_X,Q_X)={\displaystyle \underset{K:{\lambda }_1\left[K\right]\le ϵ}{inf}}{\lambda }_2\left[K\right]$$

(55)

to be the least type-II error probability that can be achieved under the constraint that the type-I error probability does not exceed $ϵ$.

4.2. Conditional Missed-Detection and False-Alarm Probabilities

The following lemma follows directly from Watanabe’s work [12].

Lemma 2

([12] Theorem 1 and Corollary 2). Let $P_{Y^n|X^n,T=t}$ be the n-letter conditional distribution of the channel output sequence given that the noise description is $T=t$ and the input is $X^n$. For any ${\lambda }_1$, ${\lambda }_2$ > 0 with ${\lambda }_1+{\lambda }_2<1$, any $0<\eta <1-{\lambda }_1-{\lambda }_2$, and any fixed $t\in \mathcal{T}$, the condition:

$$p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)<{\lambda }_1+{\lambda }_2,\forall i\in \mathcal{N}$$

(56)

implies:

$$\begin{array}{cc}\hfill loglog\mathsf{N}\le {\displaystyle \underset{P\in \mathcal{P}\left({\mathcal{X}}^n\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left({\mathcal{Y}}^n\right)}{inf}}& -log{\beta }_{{\lambda }_1+{\lambda }_2+\eta }\left(P\circ P_{Y^n|X^n,T=t},P\times Q\right)\hfill \\ & +{loglog\left|\mathcal{A}\right|}^n+2log\left(\frac{1}{\eta }\right)+2\hfill \end{array}$$

(57)

and hence:

$$\frac{1}{n}loglog\mathsf{N}\le \frac{1}{n}{\displaystyle \underset{P\in \mathcal{P}\left({\mathcal{X}}^n\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left({\mathcal{Y}}^n\right)}{inf}}-log{\beta }_{{\lambda }_1+{\lambda }_2+\eta }\left(P\circ P_{Y^n|X^n,T=t},P\times Q\right)+{\psi }_n\left(\eta \right),$$

(58)

where:

$${\psi }_n\left(\eta \right)=\frac{logn}{n}+\frac{loglog\left|\mathcal{A}\right|}{n}-\frac{2}{n}log\eta +\frac{2}{n}$$

(59)

which—for any fixed $\eta >0$—tends to 0 as n tends to ∞.

Substituting $P_{Y^n|X^n,T=t}$ for $P_{Y|X}$ in the following theorem will allow us to link the RHS of (57) with the conditional mutual information between $X^n$ and $Y^n$ given $t\in \mathcal{T}$. The theorem’s proof was inspired by the proof of [16] (Theorem 8). See also [17] (Lemma 1).

Theorem 2.

Given any $0<ϵ<1$ and any conditional PMF $P_{Y|X}$,

$${\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left(\mathcal{Y}\right)}{inf}}-log{\beta }_{ϵ}\left(P\circ P_{Y|X},P\times Q\right)\le \frac{{sup}_{P\in \mathcal{P}\left(\mathcal{X}\right)}{I}_{P\circ P_{Y|X}}(X;Y)+h\left(ϵ\right)}{1-ϵ}$$

(60)

where $h\left(ϵ\right)\triangleq -ϵlog\left(ϵ\right)-(1-ϵ)log(1-ϵ)$ is the binary entropy function.

Proof. 

Applying the data-processing inequality for relative entropy to the binary hypothesis testing setting (see, e.g., [18] (Thm. 30.12.5)) we conclude that for any randomized test $K(·|X)$,

$$D_{\mathrm{bin}}\left(1-{\lambda }_1\left[K\right]\parallel {\lambda }_2\left[K\right]\right)\le D\left(P\circ P_{Y|X}\parallel P\times Q\right)$$

(61)

where:

$$D_{\mathrm{bin}}(\alpha \parallel \beta )\triangleq \alpha log\frac{\alpha }{\beta }+(1-\alpha )log\frac{1-\alpha }{1-\beta }$$

(62)

denotes the binary divergence function. Since there exists a randomized test $K^{*}(·|X)$ for which $\left({\lambda }_1\left[K^{★}\right],{\lambda }_2\left[K^{★}\right]\right)=\left(ϵ,{\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\right)$ (see, e.g., [18] (Lemma 30.5.4 and Proposition 30.8.1) we can apply (61) to $K^{★}(·|X)$ to conclude that:

$$D_{\mathrm{bin}}\left(1-ϵ\parallel {\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\right)\le D\left(P\circ P_{Y|X}\parallel P\times Q\right).$$

(63)

(The above existence also holds when ${\beta }_{ϵ}(P\circ P_{Y|X},P\times Q))$ is zero, but for this case we can verify (63) directly by noting that in this case, since $ϵ<1$, the RHS of (63) is $+\infty$.) The LHS of (63) can be lower bounded by lower-bounding the binary divergence function as:

$$D_{\mathrm{bin}}\left(1-ϵ\parallel {\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\right)\ge -h\left(ϵ\right)-(1-ϵ)log{\beta }_{ϵ}(P\circ P_{Y|X},P\times Q).$$

(64)

It follows from (63) and (64) that:

$$-log{\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\le \frac{D\left(P\circ P_{Y|X}\parallel P\times Q\right)+h\left(ϵ\right)}{1-ϵ}$$

(65)

so the infimum over Q of the LHS is upper bounded by the infimum over Q on the RHS. The latter (for fixed $P\in \mathcal{P}\left(\mathcal{X}\right)$) is achieved when Q is the Y-marginal of $P\circ P_{Y|X}$, a marginal that we denote $P_Y$:

$${\displaystyle \underset{Q}{inf}}D\left(P\circ P_{Y|X}\parallel P\times Q\right)=I_{P\circ P_{Y|X}}(X;Y).$$

(66)

This is a special case of a more general result on Rényi divergence [19] (Theorem II.2). Here we give a simple proof for K-L divergence:

$$\begin{array}{}& D\left(P\circ P_{Y|X}\parallel P\times Q\right)\hfill \mathrm{(67)}& ={\displaystyle \sum _{x\in \mathcal{X},y\in \mathcal{Y}}}P\circ P_{Y|X}(x,y)log\left(\frac{P\circ P_{Y|X}(x,y)}{P\left(x\right)Q\left(y\right)}\right)\hfill \mathrm{(68)}& ={\displaystyle \sum _{x\in \mathcal{X},y\in \mathcal{Y}}}P\circ P_{Y|X}(x,y)log\left(\frac{P\circ P_{Y|X}(x,y)}{P\left(x\right)P_Y\left(y\right)}\frac{P_Y\left(y\right)}{Q\left(y\right)}\right)\hfill \mathrm{(69)}& ={\displaystyle \sum _{x\in \mathcal{X},y\in \mathcal{Y}}}P\circ P_{Y|X}(x,y)log\left(\frac{P\circ P_{Y|X}(x,y)}{P\left(x\right)P_Y\left(y\right)}\right)+{\displaystyle \sum _y}{P}_Y\left(y\right)log\frac{P_Y\left(y\right)}{Q\left(y\right)}\hfill \mathrm{(70)}& \ge I_{P\circ P_{Y|X}}(X;Y)+0\hfill \end{array}$$

with equality if and only if Q equals $P_Y$.

From (63), (64), and (66) we obtain:

$$\begin{array}{}& {\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left(\mathcal{Y}\right)}{inf}}-log{\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\hfill \mathrm{(71)}& \le {\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left(\mathcal{Y}\right)}{inf}}\frac{D_{bin}\left(1-ϵ\parallel {\beta }_{ϵ}(P\circ P_{Y|X},P\times Q)\right)+h\left(ϵ\right)}{1-ϵ}\hfill \mathrm{(72)}& \le {\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left(\mathcal{Y}\right)}{inf}}\frac{D\left(P\circ P_{Y|X}\parallel P\times Q\right)+h\left(ϵ\right)}{1-ϵ}\hfill \mathrm{(73)}& ={\displaystyle \underset{P\in \mathcal{P}\left(\mathcal{X}\right)}{sup}}\frac{I_{P\circ P_{Y|X}}(X;Y)+h\left(ϵ\right)}{1-ϵ}.\hfill \end{array}$$

□

Applying Lemma 2 and Theorem 2 to our channel when its law is conditioned on $T=t$ yields the following corollary.

Corollary 1.

On the MMANC, for any ${\lambda }_1$, ${\lambda }_2$ > 0 with ${\lambda }_1+{\lambda }_2<1$, any $0<\eta <1-{\lambda }_1-{\lambda }_2$, and any fixed $t\in \mathcal{T}$, the condition:

$$p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)<{\lambda }_1+{\lambda }_2,\forall i\in \mathcal{N}$$

(74)

implies:

$$\frac{1}{n}loglog\mathsf{N}\le \frac{log\left|\mathcal{A}\right|-H\left(Z^n\right|T=t)/n}{1-{ϵ}^{\prime }}+{\psi }_n\left(\eta \right),$$

(75)

where ${ϵ}^{\prime }={\lambda }_1+{\lambda }_2+\eta$.

Proof. 

Substituting ${\mathcal{X}}^n$ for $\mathcal{X}$, ${\mathcal{Y}}^n$ for $\mathcal{Y}$, $P_{Y^n|X^n,T=t}$ for $P_{Y|X}$, and ${ϵ}^{\prime }$ for $ϵ$ in Theorem 2, we obtain:

$$\begin{array}{c}\hfill {\displaystyle \underset{P\in \mathcal{P}\left({\mathcal{X}}^n\right)}{sup}}{\displaystyle \underset{Q\in \mathcal{P}\left({\mathcal{Y}}^n\right)}{inf}}-log{\beta }_{{ϵ}^{\prime }}(P\circ P_{Y^n|X^n,T=t},P\times Q)\\ \hfill \le \frac{{sup}_{P\in \mathcal{P}\left({\mathcal{X}}^n\right)}{I}_{P\circ P_{Y^n|X^n,T=t}}(X^n;Y^n)+h\left({ϵ}^{\prime }\right)}{1-{ϵ}^{\prime }}.\end{array}$$

(76)

Given $P\in \mathcal{P}\left({\mathcal{X}}^n\right)$ and $P_{Y^n|X^n,T=t}$, the mutual information term in (76) can be upper-bounded as follows:

$$\begin{array}{}\mathrm{(77)}& \hfill I_{P\circ P_{Y^n|X^n,T=t}}(X^n;Y^n)& \le \hfill & nlog\left|\mathcal{A}\right|-H_{P\circ P_{Y^n|X^n,T=t}}\left(Y^n\right|X^n,T=t)\hfill \mathrm{(78)}& & =\hfill & nlog\left|\mathcal{A}\right|-{\displaystyle \sum _{x^n}}P\left(x^n\right|T=t)H\left(Y^n\right|X^n=x^n,T=t)\hfill \mathrm{(79)}& & =\hfill & nlog\left|\mathcal{A}\right|-{\displaystyle \sum _{x^n}}P\left(x^n\right|T=t)H\left(Z^n\right|X^n=x^n,T=t)\hfill \mathrm{(80)}& & =\hfill & nlog\left|\mathcal{A}\right|-H\left(Z^n\right|T=t).\hfill \end{array}$$

Applying (76) and (80) to (58) in Lemma 2 establishes Corollary 1. □

4.3. Averaging over T

Corollary 1 deals with identification for a given fixed $T=t$, but our definition of achievability in (13) and (14) entails averaging over t, which we must thus study. We begin by lower-bounding the conditional entropy of the noise sequence $Z^n$ given the assistance T:

$$\begin{array}{}\mathrm{(81)}& \hfill H\left(Z^n\right|T)& =\hfill & H(Z^n,T)-H\left(T\right)\hfill \mathrm{(82)}& & \ge \hfill & {\{H\left(Z^n\right)-n{R}_{\mathrm{h}}\}}^{+}\hfill \mathrm{(83)}& & =\hfill & n{\{H\left(P_Z\right)-R_{\mathrm{h}}\}}^{+}.\hfill \end{array}$$

We next define, for every $\delta >0$, the subset of descriptions:

$${\mathcal{T}}^{*}\left(\delta \right)=\left\{t\in \mathcal{T}:H\left(Z^n\right|T=t)\ge n{\{H\left(P_Z\right)-R_{\mathrm{h}}-\delta \}}^{+}\right\}.$$

(84)

These are poor noise descriptions in the sense that, after they are revealed, the remaining uncertainty about the noise is still large. Key is that their probability is bounded away from zero. In fact, as we next argue:

$$P_T\left({\mathcal{T}}^{*}\left(\delta \right)\right)\ge \left\{\begin{array}{cc}\frac{\delta }{log\left|\mathcal{A}\right|-H\left(P_Z\right)+R_{\mathrm{h}}+\delta }\hfill & \mathrm{if}{R}_{\mathrm{h}}<H\left(P_Z\right)-\delta \hfill \\ 1\hfill & \mathrm{if}{R}_{\mathrm{h}}\ge H\left(P_Z\right)-\delta \hfill \end{array}\right.$$

(85)

where in the second case the probability is 1 because when $R_{\mathrm{h}}\ge H\left(P_Z\right)-\delta$ the condition appearing in the definition of ${\mathcal{T}}^{*}\left(\delta \right)$ in (84) translates to $H\left(Z^n\right|T=t)\ge 0$. As to the first case, we begin with (83) to obtain:

$$\begin{array}{}\mathrm{(86)}& \hfill n(H\left(P_Z\right)-R_{\mathrm{h}})& \le \hfill & H\left(Z^n\right|T)\hfill \mathrm{(87)}& & =\hfill & {\displaystyle \sum _{t\notin {\mathcal{T}}^{*}\left(\delta \right)}}{P}_T\left(t\right)H\left(Z^n\right|T=t)+{\displaystyle \sum _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}{P}_T\left(t\right)H\left(Z^n\right|T=t)\hfill \mathrm{(88)}& & \le \hfill & \left(1-P_T\left({\mathcal{T}}^{*}\left(\delta \right)\right)\right)·n\left(H\left(P_Z\right)-R_{\mathrm{h}}-\delta \right)+P_T\left({\mathcal{T}}^{*}\left(\delta \right)\right)·nlog\left|\mathcal{A}\right|\hfill \end{array}$$

from which the first case of the bound in (85) follows. Here (87) follows from expressing $\mathcal{T}$ as the disjoint union of ${\mathcal{T}}^{*}\left(\delta \right)$ and $\mathcal{T}\setminus {\mathcal{T}}^{*}\left(\delta \right)$, and (88) follows from the definition of ${\mathcal{T}}^{*}\left(\delta \right)$ and the bound $H\left(Z^n\right|T=t)\le nlog|\mathcal{A}|$.

Inequality (85) establishes that the probability of a poor description is lower bounded by a positive constant that does not depend on n. Using Corollary 1 for such t’s will be the key to the converse.

Henceforth, we fix some sequence of identification codes of rate R exceeding $C_{\mathrm{Sh}}\left(R_{\mathrm{h}}\right)$, i.e., satisfying $R>log\left|\mathcal{A}\right|-{\{H\left(P_Z\right)-R_{\mathrm{h}}\}}^{+}$, and show that $p_{\mathrm{MD},\max }+p_{\mathrm{FA},\max }$ cannot tend to 0 as n tends to ∞. For such a rate R, there exist $R^{\prime }$, $\delta >0$; a pair ${\lambda }_1,{\lambda }_2>0$ with ${\lambda }_1+{\lambda }_2<1$; and some $\eta \in (0,1-{\lambda }_1-{\lambda }_2)$ such that:

$$R>R^{\prime }>\frac{log\left|\mathcal{A}\right|-{\{H\left(P_Z\right)-R_{\mathrm{h}}-\delta \}}^{+}}{1-{ϵ}^{\prime }}$$

(89)

where ${ϵ}^{\prime }\triangleq {\lambda }_1+{\lambda }_2+\eta <1$. Fix such $R^{\prime }$, $\delta$, ${\lambda }_1$, ${\lambda }_2$, $\eta$, and ${ϵ}^{\prime }$.

Since the inequality on $R^{\prime }$ in (89) is strict, and since ${\psi }_n\left(\eta \right)$ tends to zero with n, it follows that the inequality continues to hold also when we add ${\psi }_n\left(\eta \right)$ to the RHS provided that n is sufficiently large, i.e., that there exists some $n_0\left(\eta \right)$ such that:

$$R^{\prime }>\frac{log\left|\mathcal{A}\right|-{\{H\left(P_Z\right)-R_{\mathrm{h}}-\delta \}}^{+}}{1-{ϵ}^{\prime }}+{\psi }_n\left(\eta \right),n\ge n_0\left(\eta \right).$$

(90)

It then follows from (90) and the definition of ${\mathcal{T}}^{*}\left(\delta \right)$ in (84) that, whenever $n\ge n_0\left(\eta \right)$, $R^{\prime }$ exceeds the RHS of (75):

$$R^{\prime }>\frac{log\left|\mathcal{A}\right|-n^{-1}H\left(Z^n\right|T=t)}{1-{ϵ}^{\prime }},\forall t\in {\mathcal{T}}^{*}\left(\delta \right).$$

(91)

Corollary 1 thus implies that, for $n>n_0\left(\eta \right)$:

$$\left(\frac{1}{n}loglog\mathsf{N}>R^{\prime }\right)\Rightarrow \left(\forall t\in {\mathcal{T}}^{★}\exists i\left(t\right)\in \mathcal{N}\mathrm{s}.\mathrm{t}.p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)\ge {\lambda }_1+{\lambda }_2\right).$$

(92)

However, we need a stronger statement because, in the above, the IM i for which $p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)\ge {\lambda }_1+{\lambda }_2$ depends on t, whereas in our definition of achievability we are averaging over T for fixed IM. The stronger result we will establish is that the condition on the LHS of (92) implies that, for all sufficiently large n, there exists some IM $i^{*}$ (that does not depend on t) which performs poorly for every t in ${\mathcal{T}}^{*}\left(\delta \right)$, i.e., for which:

$$p_{\mathrm{MD}}^{i^{*}}\left(t\right)+p_{\mathrm{FA}}^{i^{*}}\left(t\right)\ge {\lambda }_1+{\lambda }_2,\forall t\in {\mathcal{T}}^{*}\left(\delta \right).$$

(93)

That is, we will show that for sufficiently large n:

$$\left(\frac{1}{n}loglog\mathsf{N}>R^{\prime }\right)\Rightarrow \left(\exists i\in \mathcal{N}\mathrm{s}.\mathrm{t}{\displaystyle \underset{t\in {\mathcal{T}}^{★}\left(\delta \right)}{min}}\left\{p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)\right\}\ge {\lambda }_1+{\lambda }_2\right).$$

(94)

To this end, define for each $t\in {\mathcal{T}}^{*}\left(\delta \right)$:

$$\mathcal{N}\left(t\right)=\left\{i\in \mathcal{N}:p_{\mathrm{MD}}^i\left(t\right)+p_{\mathrm{FA}}^i\left(t\right)<{\lambda }_1+{\lambda }_2\right\}$$

(95)

and consider the identification code that results when we restrict our code to the IMs in $\mathcal{N}\left(t\right)$ (while keeping the same acceptance regions). Applying Corollary 1 to this restricted code using (91), we obtain that:

$$\frac{1}{n}loglog\left|\mathcal{N}\left(t\right)\right|<R^{\prime },\forall t\in {\mathcal{T}}^{*}\left(\delta \right).$$

(96)

Consequently,

$$\left|{\displaystyle \bigcup _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}\mathcal{N}\left(t\right)\right|\le {\displaystyle \sum _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}\left|\mathcal{N}\left(t\right)\right|\le 2^{n{R}_{\mathrm{h}}}{2}^{2^{n{R}^{\prime }}}$$

(97)

where the second inequality holds by (96) and the fact that ${\mathcal{T}}^{*}\left(\delta \right)$ is contained in $\mathcal{T}$, and the latter’s cardinality is $2^{n{R}_{\mathrm{h}}}$.

Since $R^{\prime }<R$ (89), there exists some $n_1(R,R^{\prime },R_{\mathrm{h}})$ such that:

$$2^{n{R}_{\mathrm{h}}}{2}^{2^{n{R}^{\prime }}}<2^{2^{nR}},n\ge n_1(R,R^{\prime },R_{\mathrm{h}}).$$

(98)

We can use this to upper-bound the RHS of (97) to obtain that, for $n\ge max\left\{n_0\left(\eta \right),n_1(R,R^{\prime },R_{\mathrm{h}})\right\}$:

$$\left|{\displaystyle \bigcup _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}\mathcal{N}\left(t\right)\right|<\mathsf{N}.$$

(99)

The complement (in $\mathcal{N}$) of the union on the LHS of (99) is thus not empty, which proves the existence of some $i^{★}\in \mathcal{N}$ for which (93) holds.

With $i^{★}$ in hand, the converse follows from the fact that the probability that T is in ${\mathcal{T}}^{*}\left(\delta \right)$ is bounded away from zero (85), because for every $n\ge max\left\{n_0\left(\eta \right),n_1(R,R^{\prime },R_{\mathrm{h}})\right\}$:

$$\begin{array}{}\mathrm{(100)}& \hfill p_{\mathrm{MD},\max }+p_{\mathrm{FA},\max }& =\hfill & {\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)p_{\mathrm{MD}}^i\left(t\right)+{\displaystyle \underset{i\in \mathcal{N}}{max}}{\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)p_{\mathrm{FA}}^i\left(t\right)\hfill \mathrm{(101)}& & \ge \hfill & {\displaystyle \sum _{t\in \mathcal{T}}}{P}_T\left(t\right)\left(p_M^{i^{*}}D\left(t\right)+p_{\mathrm{FA}}^{i^{*}}\left(t\right)\right)\hfill \mathrm{(102)}& & \ge \hfill & {\displaystyle \sum _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}{P}_T\left(t\right)\left(p_M^{i^{*}}D\left(t\right)+p_{\mathrm{FA}}^{i^{*}}\left(t\right)\right)\hfill \mathrm{(103)}& & \ge \hfill & {\displaystyle \sum _{t\in {\mathcal{T}}^{*}\left(\delta \right)}}{P}_T\left(t\right)·({\lambda }_1+{\lambda }_2)\hfill \mathrm{(104)}& & =\hfill & P_T\left({\mathcal{T}}^{*}\left(\delta \right)\right)·({\lambda }_1+{\lambda }_2)\hfill \\ \\ \\ \\ \end{array}$$

where (100) follows from the definitions in (13) and (14); in (101) we replaced the maximum with the IM $i^{*}$; and (103) follows from (93). Thus, any code of rate $R>log\left|\mathcal{A}\right|-{\{H\left(P_Z\right)-R_{\mathrm{h}}\}}^{+}$ with large enough n must have $p_{\mathrm{MD},\max }+p_{\mathrm{FA},\max }\ge P_T\left({\mathcal{T}}^{*}\right)·({\lambda }_1+{\lambda }_2)$, and the latter is bounded away from zero. This concludes the proof of the converse part.