1 Introduction↩︎

Consider a pair of discrete memoryless correlated sources with finite alphabets \(\mathcal{X}\) and \(\mathcal{Y}\), and joint distribution \(P_{XY}\). The pair of i.i.d. sequences of length \(n\) generated at random by the two sources are denoted by \(\boldsymbol{X}= X_1, X_2,\ldots, X_n\) and \(\boldsymbol{Y}= Y_1, Y_2,\ldots, Y_n\), while realizations are denoted with a lowercase font as \(\boldsymbol{x}= x_1, x_2,\ldots, x_n\) and \(\boldsymbol{y}= y_1, y_2,\ldots, y_n\). An encoder observes \(\boldsymbol{X}\) and maps it into a codeword (or bin) \(m\), chosen from a set of \(M\) codewords. A standard block source code \(\mathcal{C}(n,R)\) is defined as a mapping \(\phi:\mathcal{X}^n\to\mathcal{M}\) of source sequences \(\boldsymbol{x}\in\mathcal{X}^n\) to a set of codewords \(\mathcal{M}=\{1,\dotsc,M\}\) where \(R=\frac{\log M}{n}\) is the code rate. At the receiver end, the decoder observes the codeword \(m\) and, along with the side information \(\boldsymbol{y}\), provides an estimate of the original source sequence. More formally, the decoder \(\psi:\mathcal{M}\times\mathcal{Y}^n\to\mathcal{X}^n\) maps each codeword and side information sequence back into a source sequence \(\hat{\boldsymbol{x}}\). The decoder makes an error whenever \(\psi(\phi(\boldsymbol{x}),\boldsymbol{y})\neq \boldsymbol{x}\) and the probability of error is given by \[p_e = \mathbb{P}[\psi(\phi(\boldsymbol{X}),\boldsymbol{Y})\neq \boldsymbol{X}].\] This setting is known as block source coding with decoder side information, or Slepian-Wolf coding [1], [2]. In this paper, we are interested in the exponential decay rate of the decoding error probability with block-length \(n\), known as the error exponent or reliability function.

In [2], Gallager derived an achievable error exponent for the above setting using random coding, or random binning, and maximum a posteriori probability (MAP) decoding. In Gallager’s random coding ensemble, source sequences are mapped to codewords (or bins) uniformly at random in a pairwise independent manner. The corresponding achievable exponent is \[\label{eq:Er95dual} E_{\mathrm{r}}(R) = \max_{\rho \in [0,1]} \rho R - E_{0}(\rho)\tag{1}\] where the function \(E_{0}(\rho)\) is defined as \[\label{eq:E095function} E_{0}(\rho) \triangleq \log\sum\limits_{y \in \mathcal{Y}} P_Y(y)\bigg( \sum\limits_{x \in \mathcal{X}} P_{X|Y}(x|y)^{\frac{1}{1+\rho}} \bigg)^{1+\rho} .\tag{2}\] The function \(E_{0}(\rho)\) is known to be related to Arimoto’s conditional Rényi entropy as \(E_{0}(\rho) = \rho H_{\frac{1}{1+\rho}}(X|Y)\) [3]. We refer to \(E_{\mathrm{r}}(R)\) as the random-coding error exponent, due to close resemblance in proof and form to the random-coding error exponent in channel coding [4], [5]. The form in 1 is known as a dual domain expression. An equivalent primal domain³ expression for \(E_{\mathrm{r}}(R)\) is given as \[\label{eq:Er95primal} E_{\mathrm{r}}(R) = \min_{P_{\tilde{X}\tilde{Y}}} D(P_{\tilde{X}\tilde{Y}} \| P_{XY}) + \big| R - H(\tilde{X}|\tilde{Y}) \big|^{+}\tag{3}\] where the minimization is over all joint distributions \(P_{\tilde{X}\tilde{Y}}\) on \(\mathcal{X} \times \mathcal{Y}\). A direct achievability proof that yields the primal domain expression in 3 is given by Csiszár and Körner in [6], where type analysis and universal minimum entropy (ME) decoding are employed.

While \(E_{\mathrm{r}}(R)\) provides a lower bound on the reliability function, Gallager [2] also derived a corresponding upper bound, which takes the following form \[\label{eq:Esp95dual} E_{\mathrm{sp}}(R) = \sup_{\rho \geq 0} \rho R - E_{0}(\rho).\tag{4}\] We will refer to this as the sphere-packing exponent, as it closely resembles the sphere-packing exponent in channel coding [7]. The sphere-packing exponent \(E_{\mathrm{sp}}(R)\) is derived by providing the side information sequence \(\boldsymbol{Y}\) to the encoder, and is in fact equal to the error exponent of conditional source coding, where side information is available to both encoder and decoder. The sphere packing exponent admits an equivalent primal domain expression [6] given as \[\label{eq:Esp95primal} E_{\mathrm{sp}}(R) =\min_{P_{\tilde{X}\tilde{Y}} : H(\tilde{X}|\tilde{Y}) \geq R } D(P_{\tilde{X}\tilde{Y}} \| P_{XY}).\tag{5}\]

Both \(E_{\mathrm{r}}(R)\) and \(E_{\mathrm{sp}}(R)\) are non-negative for rates in the range \(H(X|Y) < R < \log |\mathcal{S}(X)|\), where \(\mathcal{S}(X) \subseteq \mathcal{X}\) is the support of \(P_X\); and are equal to zero for \(0 \leq R \leq H(X|Y)\). Moreover, \(E_{\mathrm{r}}(R)\) and \(E_{\mathrm{sp}}(R)\) coincide in the range \(H(X|Y) < R \leq R_{\mathrm{cr}}\), where \(R_{\mathrm{cr}}\) is the largest rate at which the convex curve \(E_{\mathrm{sp}}(R)\) meets its supporting line of slope 1. Note that \(R_{\mathrm{cr}}\) is reminiscent of the critical rate in channel coding.

1.1 Expurgated exponent↩︎

For a range of rates above the critical rate \(R_{\mathrm{cr}}\), a tighter achievable error exponent was derived by Csiszár and Körner in [8], and is given by \[\begin{align} \label{eq:Eex95primal} E_{\rm{ex}}(R)=\min_{P_{\tilde{X}}} \bigg \lbrace D(P_{\tilde{X}}\|P_X) + \min_{P_{\hat{X}\tilde{X}}:P_{\hat{X}}=P_{\tilde{X}}, H(\hat{X}|\tilde{X})\geq R} \Big\lbrace\mathbb{E}\big[d(\hat{X},\tilde{X})\big] + R - H(\hat{X}|\tilde{X})\Big\rbrace\bigg\rbrace \end{align}\tag{6}\] where \(d(\hat{x},\tilde{x})\) is the Bhattacharyya distance between \(P_{Y|X}(\cdot|\hat{x})\) and \(P_{Y|X}(\cdot|\tilde{x})\), defined as \[d(\hat{x},\tilde{x}) \triangleq - \log \sum\limits_{y \in \mathcal{Y}} \sqrt{ P_{Y|X}(y|\hat{x}) P_{Y|X}(y|\tilde{x}) }.\] The exponent \(E_{\rm{ex}}(R)\) is often referred to as the expurgated exponent, since it can be seen as a source coding counterpart to the expurgated exponent in channel coding when expressed in the primal domain [8], [9]. Relating the Slepian-Wolf source coding problem to a counterpart channel coding problem with input \(\boldsymbol{X}\) and output \(\boldsymbol{Y}\) is in fact the first step in the proof of Csiszár and Körner [8], as well as a later proof by Ahlswede and Dueck [10].

In deriving the expurgated exponent \(E_{\rm{ex}}(R)\), Csiszár and Körner [8] employ a type-by-type block coding scheme, in which source sequences assigned to the same codeword (or bin) all have the same type. Since source sequences of the same type have the same probability, optimal MAP decoding reduces to maximum likelihood (ML) decoding in this case, which was used to derive 6 . In the code construction, instead of relying on random coding, a graph-theoretic decomposition lemma is used to show that every type class can be partitioned into so-called “balanced” sets with a favorable packing property, and these balanced sets are taken as bins. The same exponent was later derived by Ahlswede and Dueck in [10] by exploiting the connection to the counterpart channel coding problem and using permutation codes. In particular, their approach relies on covering each source type class using permutations of a good constant-composition channel code of the same type, that achieves the channel coding expurgated exponent.

Both the Csiszár-Körner and Ahlswede-Dueck proofs of the expurgated exponent rely heavily on type analysis and combinatorial arguments, and do not use random coding or expurgation, at least not in a direct manner. Moreover, their derivations yield the primal expression in 6 , and currently it is not known whether this expression admits an equivalent dual form.

The main objective for our present work is to find a dual-domain derivation for the expurgated exponent in source coding with side information, mirroring Gallager’s original proof of the expurgated exponent in channel coding [4]. Gallager’s expurgation approach does not directly apply here as in the source coding setting, one cannot simply remove a “bad” fraction of source sequences. A dual-domain derivation is also expected to yield non-asymptotic bounds that are valid for settings with arbitrary memory, countable source alphabets, and general side information alphabet. Furthermore, compared to the primal expression in 6 , a dual domain expression will likely have far fewer parameters and will hence be easier to compute and evaluate.

1.2 Mismatched Decoding↩︎

Another motivation for our current work is to evaluate error exponents for source coding with side information under generic, and possibly mismatched, decoding metrics. Mismatched decoding, thoroughly studied in the context of channel coding, is the setting for which the decoder employs a fixed decoding metric, not necessarily related to the probability law describing the system (see [11] and references therein). Mismatched decoding naturally arises in cases where the decoder cannot accurately estimate the system’s parameters, or in cases where, for complexity reasons, the one prefers an alternative decoding metric. To this end, in the considered setting we adopt a maximum metric decoder of the form \[\psi(m,\boldsymbol{y})=\mathop{\mathrm{arg\,max}}_{\boldsymbol{x}\in\mathcal{X}^n:\phi(\boldsymbol{x})=m}q(\boldsymbol{x},\boldsymbol{y}), \label{eq:dec}\tag{7}\] where \(q\) is an arbitrary non-negative decoding metric. Upon observing \(m\) and \(\boldsymbol{y}\), the decoder chooses the source sequence \(\boldsymbol{x}\) whose metric is highest out of those encoded to \(m\). The decoding metric is said to be memoryless if \(q(\boldsymbol{x},\boldsymbol{y})=\prod_{i=1}^{n}q(x_i,y_i)\). In this case, and under memoryless source and side information, the optimal MAP decoder is recovered by choosing the metric as \(q(x,y) = P_{X|Y}(x|y)\). Otherwise, the decoder is said to be mismatched. As we shall see further on, the majority of our derivations are valid for an arbitrary metric \(q(\boldsymbol{x},\boldsymbol{y})\). With that said, in our single-letter asymptotic results, we choose to focus on the memoryless case.

Under an arbitrary memoryless decoding metric \(q\), primal-domain random coding and expurgated exponents that generalize 3 and 6 can be distilled from the results of Csiszár and Körner [8], obtained using their graph decomposition approach. These results are derived for a generic class of decoders called \(\alpha\)-decoders, which includes the memoryless mismatched decoder as a special case. The corresponding random coding and expurgated exponents are given by \[E^{\mathrm{ck}}_{q,\mathrm{r}}(R)= \min_{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}} D(P_{\tilde{X}\tilde{Y}}\|P_{XY})+|R-H(\hat{X}|\tilde{Y})|^{+}, \label{eq:RC95CK95SW95exponent}\tag{8}\] and \[E^{\mathrm{ck}}_{q,\mathrm{ex}}(R)=\min_{\substack{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}\\H(\hat{X}|\tilde{X})\geq R}}D(P_{\tilde{X}\tilde{Y}}\|P_{XY})+R-H(\hat{X}|\tilde{X},\tilde{Y}) \label{eq:EX95CK95SW95exponent}\tag{9}\] respectively, where the set of distributions \(\mathcal{T}\) is defined as \[\mathcal{T}=\Big\lbrace P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{X}\times\mathcal{Y}):P_{\hat{X}}=P_{\tilde{X}},\mathbb{E}\big[\log q(\hat{X},\tilde{Y})\big]\geq\mathbb{E}\big[\log q(\tilde{X},\tilde{Y})\big]\Big\rbrace.\] These exponents reduce to their matched counterparts in 3 and 6 when the decoding metric \(q(x,y)=P_{Y|X}(y|x)\) is chosen to be the ML decoder, which is optimal in this case due to the type-by-type coding scheme used in [8].

From 8 and 9 , we obtain the Csiszár-Körner’s achievable exponent given by \[E^{\mathrm{ck}}_q(R)=\max\left\{E^{\mathrm{ck}}_{q,\mathrm{r}}(R),E^{\mathrm{ck}}_{q,\mathrm{ex}}(R)\right\}. \label{eq:ck}\tag{10}\] Dual-domain derivations and expressions for 8 and 9 , and hence 10 , are currently not known. This is a gap in the literature that we aim to address in the present paper.

There is a body of work on variable-rate codes for source coding with side information, see e.g. [12]–[14]. In the variable-rate setting, the sequences of the types that are bounded away from source distribution \(P_{X}\) (assuming that the distribution \(P_{X}\) is known exactly) are losslessly encoded. This relaxation of the rate constraint does not affect the average rate asymptotically and improves the error exponent when the dominant error of the fixed-rate codes are caused by one of those types. The works [12], [14] analyze the trade-off between the error-exponent and excess-rate exponent for the variable-rate setting. While the idea of using variable-rate codes for the source coding with side-information problem is well-investigated for the matched case, it does not immediately extend to the mismatched case. In this paper we focus on the setting of fixed-length (fixed-rate) codes and do not consider variable-rate codes.

1.3 Contribution↩︎

The main contributions of the paper are as follows:

• In Section 2, we present our main theorems on dual-domain achievable exponents with mismatched decoding for two random coding ensembles, namely standard ensemble and type-by-type ensemble. These theorems show the existence of a code that attains the maximum of two exponents, namely random coding and expurgated exponents. The dual domain exponents for type-by-type ensemble and expurgated exponent for standard ensemble appear for the first time in the literature. We further show the equivalence of the dual domain exponents to the Csiszár-Körner’s achievable exponent in 10 . We also present relative comparisons of these achievable exponents and state the family of metrics that attain the corresponding optimal exponent. The achievable rates for these ensembles together with their relation to the generalized mutual information and LM rates of mismatched decoding in channel coding are also presented.

• In Section 3, we introduce an expurgation method for source coding that is valid for general source and side information models and arbitrary decoding metrics. The expurgation method works for either of the two code ensembles and can be summarized as follows. We first use Gallager’s expurgation technique, developed for channel coding [4], to show that there exists a code in the ensemble such that at least half of the source sequences satisfy a desired error bound. We expurgate the “bad” half of source sequences, encode them separately into a new set of codewords, and apply expurgation again. The error bound derived in the previous iteration remains valid here, since we now have fewer source sequences. The procedure stops after (at most) \(k = n \log_2 |\mathcal{X}|\) iterations, once all source sequences are exhausted. Combining the expurgated codes from all iterations, we obtain a code in which all the source sequences satisfy the desired error bound.

• Based on our expurgation method, in Sections 5 and 6, we derive non-asymptotic bounds that are valid for any discrete source model with arbitrary side information alphabet and arbitrary decoding metric.

1.4 Notation↩︎

We use bold symbols for vectors (e.g. \(\boldsymbol{x}\)), and denote the corresponding \(i\)-th entry using a subscript (e.g. \(x_i\)). The set of all probability distributions on an alphabet \(\mathcal{X}\), is denoted by \(\mathcal{P}(\mathcal{X})\), and the set of all empirical distributions on a vector in \(\mathcal{X}^n\) is denoted by \(\mathcal{P}_n(\mathcal{X})\). For a given type \(\hat{P}\in\mathcal{P}_n(\mathcal{X})\), the type class \(\mathcal{T}_n(\hat{P})\) is defined to be the set of all sequences in \(\mathcal{X}^n\) with type \(\hat{P}\). The probability of an event is denoted by \(\mathbb{P}[\cdot]\). The marginals of a joint distribution \(P_{XY}(x,y)\) are denoted by \(P_{X}(x)\) and \(P_{Y}(y)\). We write \(P_X=Q_X\) to denote element-wise equality between two probability distributions on the same alphabet. Expectation with respect to a joint distribution \(P_{XY}(x,y)\) is denoted by \(\mathbb{E}_{P}[\cdot]\), or simply \(\mathbb{E}[\cdot]\) when the associated probability distribution is understood from the context. Given a distribution \(Q_{X}\) and conditional distribution \(W_{Y|X}\), we write \(Q_{X}\times W_{Y|X}\) to denote the resulting joint distribution and the corresponding mutual information is written as \(I(Q_{X},W_{Y|X})\), or simply \(I(X;Y)\) when the distribution is understood from the context. We use standard notation for the entropy \(H(X)\) (also sometimes shown as \(H(Q)\) to emphasize the distribution of the random variable), conditional entropy \(H(X|Y)\) and divergence \(D(P\|Q)\). All logarithms have base \(e\) and all rates are in units of nats including in the example. We denote the indicator function of an event by \(\mathbb{1}[\cdot]\).

2 Main Results↩︎

In this section, we introduce our main results, which are dual domain expressions of expurgated error exponents. These expressions are obtained directly in the dual domain by means of an expurgation method detailed in Section 3 for two different code ensembles. These code ensembles differ on whether the set of source sequences and codewords are partitioned or not. The relative merits of these ensembles are illustrated by means of a numerical example. Proofs of the results are given in Sections 5, 6 and 7, respectively.

2.1 Standard Block Random Coding↩︎

For the standard random coding ensemble we have the following result concerning achievable error exponents for memoryless sources employing a memoryless decoding metric.

In deriving the error exponent of Theorem [th:standard] we derive \(n\)-letter bounds in 58 and 67 that are valid for any discrete source with arbitrary side information alphabets and arbitrary decoding metrics without the memoryless assumption. These bounds can be used to derive error exponents for general source models.

2.2 Type-by-Type Random Coding↩︎

We now introduce a different block random coding ensemble that encodes each source type separately. As will be shown next, this attains potentially a higher error exponent than the standard block code ensemble under the same decoding metric. Consider partitioning the codeword set \(\mathcal{M}=\{1,\cdots,M\}\) into \(|\mathcal{P}_n(\mathcal{X})|\) subsets as: \(\mathcal{M}=\bigcup\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\mathcal{M}_i\) where \(\mathcal{M}_i\) is the codeword set for source type \(\hat{P}_i\), \(i\in\{1,\cdots,|\mathcal{P}_n(\mathcal{X})|\}\), \(|\mathcal{M}_i|=\frac{M}{|\mathcal{P}_n(\mathcal{X})|}\) and \(\mathcal{M}_i\cap\mathcal{M}_j=\emptyset\) for \(i\neq j\).

A type-by-type block source code \(\boldsymbol{\mathcal{C}}=\{\mathcal{C}_1,\cdots,\mathcal{C}_{|\mathcal{P}_n(\mathcal{X})|}\}\) is the union of \(|\mathcal{P}_n(\mathcal{X})|\) codes where each \(\mathcal{C}_i\) is an \((n,R_i)\) block code for source type \(\hat{P}_i\) with mapping function \(\phi_{i}:\mathcal{T}_n(\hat{P}_i)\to\mathcal{M}_i\) and rate \(R_i=\frac{\log M}{n}-\delta_n\) for \(i\in\{1,\cdots,|\mathcal{P}_n(\mathcal{X})|\}\), where \(\delta_n=\frac{\log|\mathcal{P}_n(\mathcal{X})|}{n}\). In other words, code \(\mathcal{C}_i\) is a code for the source sequences in source type class \(\mathcal{T}_n(\hat{P}_i)\) with codeword set \(\mathcal{M}_i\) . Observe that by construction, every code \(\mathcal{C}_i\) has the same rate, and that an error can only occur between source sequences of the same type. We also note that the effect of partitioning the codeword set on the coding rate vanishes asymptotically since \(\delta_n\to 0\) as \(n\to\infty\).

The decoder for a type-by-type code \(\boldsymbol{\mathcal{C}}\) is a set of mappings \(\psi_{i}:\mathcal{M}_i\times\mathcal{Y}^n\to\mathcal{T}_n(\hat{P}_i)\) for every \(i\in\{1,\cdots,|\mathcal{P}_n(\mathcal{X})|\}\). Similarly to the standard ensemble, we consider using a maximum metric decoder as follows. For every \(m\in\mathcal{M}_i\) \[\psi_{i}(m,\boldsymbol{y})=\mathop{\mathrm{arg\,max}}_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i):\phi_i(\boldsymbol{x})=m}q(\boldsymbol{x},\boldsymbol{y}),\label{eq:dec95tbt}\tag{14}\] where \(q(\boldsymbol{x},\boldsymbol{y})\) is an arbitrary non-negative decoding metric. For the type-by-type random coding ensemble we have the following result concerning the achievable error exponents for memoryless sources employing a memoryless decoding metric.

In deriving the error exponent of Theorem 2 we derive \(n\)-letter bounds in 73 and 83 that are valid for any discrete source with arbitrary side information alphabets and arbitrary decoding metrics without the memoryless assumption. These bounds can be used to derive error exponents for general source models.

The following result shows that the error exponent introduced in Theorem 2 coincides with Csiszár and Körner’s [8] for the case of using memoryless metric.

In proving the equivalence of the primal and dual forms of the type-by-type exponent we show the following relations between type-by-type exponents and the exponent of constant composition codes for a corresponding channel as follows, \[\begin{align} E^{\mathrm{tt}}_{q,\rm r}(R)&=D(Q\|P_{X})+ E_{q,\mathrm{r}}^{\mathrm{cc}}\left(H(Q)-R,Q,P_{Y|X}\right),\\ E^{\mathrm{tt}}_{q,\rm ex}(R)&=D(\tilde{Q}\|P_{X})+ E_{q,\mathrm{ex}}^{\mathrm{cc}}\left(H(\tilde{Q})-R,\tilde{Q},P_{Y|X}\right), \end{align}\] where \(E_{q,\mathrm{r}}^{\mathrm{cc}}\left(\cdot,\cdot,\cdot\right)\) and \(E_{q,\mathrm{ex}}^{\mathrm{cc}}\left(\cdot,\cdot,\cdot\right)\) are defined in 85 and 95 , respectively, and \[\begin{align} Q(x)&=CP_{X}(x)\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a^*(\bar{x})}}{e^{a^*(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^{s^*}\right)^{\rho^*},\tag{18}\\ \tilde{Q}(x)&=\tilde{C}P_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a^*(\bar{x})}}{e^{a^*(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^{s^*}\right)^{\frac{1}{\rho^*}}\right)^{\rho^*}\tag{19}, \end{align}\] and \(C\) and \(\tilde{C}\) are the normalization constants and \(s^*, \rho^*\) and \(a^*(\cdot)\) in 18 and 19 are the optimizing choices, respectively in 16 and 17 for rate \(R\).

The following results are relative comparisons among the exponents introduced in the previous theorems, stating the families of metrics that attain the optimal exponent.

Corollary 1 shows that both type-by-type and standard ensembles recover \(E_{\mathrm{r}}(R)\) with a family of metrics given by 21 and 22 , where the latter is a subset of the former and both include the MAP decoding as a special case.

In order to compare the mismatched error exponents introduced in previous theorems with their matched counterparts, we define the following matched expurgated exponents \[E_{\mathrm{ex}}(R) = \sup_{\rho\geq 1,s\geq 0}\rho R-\log\sum\limits_{x\in\mathcal{X}}\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{XY}(x,y)\left(\frac{P_{X|Y}(\bar{x}|y)}{P_{X|Y}(x|y)}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}\label{eqn:Ex95st95MAP},\tag{25}\] \[E_{\mathrm{ex}}^{\rm tt}(R) = \sup_{\rho\geq 1,a(\cdot)}\rho R-\log\sum\limits_{x\in\mathcal{X}}P_X(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\sqrt{P_{Y|X}(y|x)P_{Y|X}(y|\bar{x})}\right)^{\frac{1}{\rho}}\right)^{\rho}.\label{eqn:Ex95type95MAP}\tag{26}\]

Similarly to Corollary 1, we have the following.

Corollary 2 shows that both type-by-type and standard ensembles recover \(E^{\rm tt}_{\mathrm{ex}}(R)\) with a family of metrics given by 29 and 30 , where the earlier recovers the exponent for full range of rates with the same metric whilst latter recovers it with a different metric for each rate \(R\).

2.3 Special case: no side information↩︎

Specializing the result of Theorem [th:standard] to block source coding without side information, we recover the following exponent for the case of using a mismatched metric \(q(x)\) as \[E_{q}(R) = \sup_{\rho\geq 0,s\geq 0}\rho R-\log\sum\limits_{x\in\mathcal{X}}P_{X}(x)\bigg(\sum\limits_{\bar{x}\in\mathcal{X}}\bigg(\frac{q(\bar{x})}{q(x)}\bigg)^s\bigg)^{\rho}.\] For \(q(x) = \frac{P_X(x)^{\tau}}{\sum\limits_{\bar x}P_X(\bar x)^{\tau}}\), \(\tau>0\), which includes the matched decoding as special case, the above exponent recovers the exponent of the optimal code as [16] \[E(R) = \sup_{\rho\geq 0}\rho R-\log\bigg(\sum\limits_{x\in\mathcal{X}}P_{X}(x)^{\frac{1}{1+\rho}}\bigg)^{1+\rho}.\label{eqn:no95side95info95matched95exponent}\tag{33}\]

Theorem 2 recovers 33 independent of the employed decoding metric. In particular, by setting \(a(x)=\frac{1}{1+\rho}\log P_X(x)\) and \(s=0\), the type-by-type exponent recovers the exponent of the optimal source code 33 .

2.4 Achievable rates↩︎

In this section, we derive the achievable rates for both standard and type-by-type random coding ensembles. Noticing that exponent is a convex function of the rate and the maximizing \(\rho\) is the slope of the exponent curve, the achievable rates for both random coding schemes can be obtained similarly to [5] by evaluating the partial derivative of the exponent to find the rate at which \(\rho=0\) maximizes the exponent.

For the standard random coding case using 12 we find the achievable rate as \[\begin{align} H_{q}(X|Y)=&\inf_{s\geq 0}-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^s}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^s}\label{eq:rate95standard}\\ =&H(X|Y)+\inf_{s\geq 0}D(P_{X|Y}\|Q^{(s)}_{X|Y}), \end{align}\tag{34}\] where \(Q^{(s)}_{X|Y}(x|y)=\frac{q(x,y)^s}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^s}\).

Similarly for the type-by-type random coding case using 16 we find the achievable rate as \[\begin{align} H^{\rm tt}_{q}(X|Y)=&\inf_{s\geq 0,a(\cdot)}-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^se^{a(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^se^{a(\bar{x})}}\label{eq:rate95tbt}\\ =&H(X|Y)+\inf_{s\geq 0,a(\cdot)}D(P_{X|Y}\|Q^{(s,a(\cdot))}_{X|Y}), \end{align}\tag{35}\] where \(Q^{(s,a(\cdot))}_{X|Y}(x|y)=\frac{q(x,y)^se^{a(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^se^{a(\bar{x})}}\).

By inspecting the optimization problems in 34 and 35 we have that \[H_{q}(X|Y) \geq H^{\rm tt}_{q}(X|Y).\] The expressions of the above achievable rates bear a strong resemblance to their channel coding counterparts, the generalized mutual information [17] achieved by iid coding, and the LM rate [8], [18] achieved by constant composition codes. Indeed, as shown next, these achievable rates can be expressed as a function of the generalized mutual information and the LM rate.

The achievability of the rate in 38 , expressed in the primal domain, was observed in [19].

2.5 Numerical example↩︎

We conclude this section with a numerical example. The joint distribution of the source \(X\) with side information \(Y\) is defined by the entries of the \(|\mathcal{X}|\times|\mathcal{Y}|\) matrix \[P_{XY}=\begin{bmatrix} 0.588 & 0.006 & 0.006 \\ 0.03 & 0.24 & 0.03 \\ 0.02 & 0.02 & 0.06 \end{bmatrix} \label{eqn:example95joint95distribution}\tag{40}\] with \(\mathcal{X}=\mathcal{Y}=\{0,1,2\}\). We consider using a mismatched decoder with a memoryless metric given by the matrix \[q(x,y)=\begin{bmatrix} 1-2\delta & \delta & \delta \\ \delta & 1-2\delta & \delta \\ \delta & \delta & 1-2\delta \end{bmatrix} \label{eqn:example95decoding95metic}\tag{41}\] with \(\delta\in(0,\frac{1}{3})\). For any value of the \(\delta\in(0,\frac{1}{3})\), the corresponding decoder is exactly the same and is equivalent to a minimum Hamming distance decoding metric. This is because for any \(\delta\) and \(\delta'\) in this range one can find an \(s'\geq 0\) such that \((\frac{1-2\delta}{\delta})^{s}=(\frac{1-2\delta'}{\delta'})^{s'}\), so the optimization over \(s\) makes the explicit choice of the \(\delta\) irrelevant as long as it is in the range of \((0,\frac{1}{3})\).

Figure 1 illustrates the exponents for the standard and type-by-type ensembles with both matched and mismatched decoders. The sphere-packing upper bound is also shown for reference. We observe that the type-by-type expurgated exponent is higher for both matched and mismatched decoding. Indeed, as discussed earlier, in the matched case, the random coding components of \(E_q(R)\) and \(E^{\rm tt}_q(R)\) (for the rates below the critical rate \(R_{\rm cr}\)) both coincide with the sphere-packing upper-bound. The corresponding achievable rates are marked with dots in the figure. The conditional entropy \(H(X|Y)=0.3879\) nats is the limit for the matched case while in the mismatched case we respectively have \(H_{q}(X|Y)=0.4283\) nats and \(H^{\rm tt}_{q}(X|Y)=0.4140\) nats.

3 Expurgation method↩︎

In this section we introduce the expurgation method for source coding that is valid for any source and side information model with arbitrary decoding metric. The method is based on randomly generating codes for the source and removing (expurgating) poor source sequences from the codes. We then show that, there exists a code in the expurgated ensemble, such that half of the source sequences meets a desired upper bound on the error probability. Repeating this procedure enough times we show that there exists a code in which all the source sequences meet the desired upper bound on the error probability. Details of the expurgation method are given in the following, first for the standard random coding and then for type-by-type random coding.

3.1 Standard Block Coding↩︎

Given a standard block source code \(\mathcal{C}\), the probability that decoder \(\psi\) makes an error for a source sequence \(\boldsymbol{x}\) is given by \[p_e(\boldsymbol{x},\mathcal{C})=\mathbb{P}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]. \label{eqn:prob95union95error95events}\tag{42}\]

Considering the standard random coding ensemble \(\mathsf{C}\) defined in Section 1, \(p_e(\boldsymbol{x},\mathsf{C})\) is a random variable for every \(\boldsymbol{x}\). Applying Markov’s inequality to this random variable, we obtain \[\mathbb{P}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\geq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big]\Big] \leq\frac{1}{\eta},\] for any \(\rho>0\) and \(\eta>1\). Equivalently we have \[\mathbb{P}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big]\Big] \geq1-\frac{1}{\eta}.\label{eqn:bound95Markov95inequality}\tag{43}\]

For a given standard block source code \(\mathcal{C}\), denote by \(N_0(\mathcal{C})\) the number of source sequences \(\boldsymbol{x}\in\mathcal{X}^n\) that satisfy \[p_e(\boldsymbol{x},\mathcal{C})^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big].\label{eqn:bound95sequence95error}\tag{44}\] Over the standard random coding ensemble \(\mathsf{C}\), \(N_0(\mathsf{C})\) is a random variable. Similarly to [5], we first observe that the expected value of \(N_0(\mathsf{C})\) can be lower bounded as \[\begin{align} \mathbb{E}\big[N_0(\mathsf{C})\big]&= \mathbb{E}\bigg[\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}\mathbb{1}\Big\{p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big]\Big\}\bigg]\\ &=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}\mathbb{E}\Big[\mathbb{1}\Big\{p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big]\Big\}\Big]\\ &=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}\mathbb{P}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big]\Big]\\ &\geq |\mathcal{X}|^n\bigg(1-\frac{1}{\eta}\bigg)\label{eqn:bound95num95seq} \end{align}\tag{45}\] where the last step follows from 43 .

Now we choose \(\eta=2\) which yields \(1-\frac{1}{\eta}=\frac{1}{2}\) in 45 . Therefore, we conclude that there exists a standard block code \(\mathcal{C}\) in which at least half of the source sequences satisfy the inequality \[p_e(\boldsymbol{x},\mathcal{C})\leq \left(2\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\right)^{\rho}.\label{eqn:bound95seq95error}\tag{46}\] Let us denote the set of above mentioned sequences as \(\mathcal{A}_1\) where \(\mathcal{A}_1\subset\mathcal{X}^n\) and \(|\mathcal{A}_1|\geq\frac{|\mathcal{X}^n|}{2}\).

We now construct a code \(\mathcal{C}_1\) for the set \(\mathcal{A}_1\) from the code \(\mathcal{C}\) as follows: We keep all the sequences \(\boldsymbol{x}\in\mathcal{A}_1\) in \(\mathcal{C}\), which satisfy 46 , and we expurgate rest of the sequences \(\boldsymbol{x}\in\mathcal{X}^n\backslash\mathcal{A}_1\) from code \(\mathcal{C}\). Note that removing source sequences can only reduce the error probability of remaining ones. This construction yields a code \(\mathcal{C}_1\) which includes only the sequences in \(\mathcal{A}_1\) and for every \(\boldsymbol{x}\in\mathcal{A}_1\) we have \[p_e(\boldsymbol{x},\mathcal{C}_1)\leq \left(2\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\right)^{\rho}.\label{eqn:bound95original95error}\tag{47}\]

The rest of sequences in \(\mathcal{X}^n\backslash\mathcal{A}_1\) include at most half of the original sequences. We now repeat the procedure to find a good code from the standard random coding ensemble for the sequences in \(\mathcal{X}^n\backslash\mathcal{A}_1\) (which we denote for simplicity as \(\bar{\mathsf{C}}\)). Given a code \(\bar{\mathcal{C}}\) from the ensemble \(\bar{\mathsf{C}}\), the probability of decoding error for a sequence \(\boldsymbol{x}\in\mathcal{X}^n\backslash\mathcal{A}_1\) is given by 42 with the only difference that now the corresponding union is over \(\bar{\boldsymbol{x}}\in\mathcal{X}^n\backslash\mathcal{A}_1\) instead of \(\boldsymbol{x}\in\mathcal{X}^n\). Therefore, the average error probability of a source sequence in the new ensemble is upper bounded by that of the original ensemble, i.e., for any \(\boldsymbol{x}\in\mathcal{X}^n\backslash\mathcal{A}_1\) we have \[\mathbb{E}\Big[p_e(\boldsymbol{x},\bar{\mathsf{C}})^{\frac{1}{\rho}}\Big]\leq\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\Big].\] Now following similar steps as before we show existence of a code \(\bar\mathcal{C}\) from the ensemble \(\bar{\mathsf{C}}\) in which at least half of the remaining \(\mathcal{X}^n\backslash\mathcal{A}_1\) source sequences satisfy the inequality \[\begin{align} p_e(\boldsymbol{x},\bar{\mathcal{C}})&\leq \left(2\mathbb{E}\left[p_e(\boldsymbol{x},\bar{\mathsf{C}})^{\frac{1}{\rho}}\right]\right)^{\rho}\\ &\leq\left(2\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\right)^{\rho}.\label{eqn:bound95seq95error952iter} \end{align}\tag{48}\]

We denote by \(\mathcal{A}_2\) the set of above mentioned sequences satisfying 48 where \(\mathcal{A}_2\subset\mathcal{X}^n\backslash\mathcal{A}_1\) and \(|\mathcal{A}_2|\geq\frac{|\mathcal{X}^n|-|\mathcal{A}_1|}{2}\). We now construct a code \(\mathcal{C}_2\) for the set \(\mathcal{A}_2\) from the code \(\bar\mathcal{C}\) following similar expurgation step described above. This construction yields a code \(\mathcal{C}_2\) which includes only the sequences in \(\mathcal{A}_2\) and every sequence \(\boldsymbol{x}\in\mathcal{A}_2\) satisfies the desired bound as in 47 .

The set \(\mathcal{X}^n\backslash\mathcal{A}_1\bigcup\mathcal{A}_2\) includes at most one forth of the original sequences. By repeating this procedure \(k\) times, the set \(\mathcal{X}^n\backslash\bigcup_{i=1}^k\mathcal{A}_i\) includes at most a fraction \(\frac{1}{2^k}\) of the original sequences. By choosing \(k=n\log_{2}|\mathcal{X}|\) we guarantee that \(\bigcup_{i=1}^k\mathcal{A}_i=\mathcal{X}^n\). Finally we construct the code \(\mathcal{C}_{\rm ex}\) by combining all \(\mathcal{C}_i\)’s as \(\mathcal{C}_{\rm ex}=\{\mathcal{C}_1,\cdots,\mathcal{C}_k\}\). The code \(\mathcal{C}_{\rm ex}\) includes all the source sequences and every sequence satisfies the desired bound as in 47 . Considering the number of codewords in each iteration as \(\frac{M}{k}\), the total number of codewords of the final code \(\mathcal{C}_{\rm ex}\) is \(M\).

Therefore we proved the following lemma.

3.2 Type-by-Type Coding↩︎

Given a type-by-type block source code \(\boldsymbol{\mathcal{C}}\), the probability that decoder \(\psi_i\) yields an error for a source sequence \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) is given by \[p_e(\boldsymbol{x},\mathcal{C}_i)=\mathbb{P}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right].\]

We notice that the type-by-type ensemble \(\boldsymbol{\mathsf{C}}\) is a product of random coding ensembles for each type \(\mathsf{C}_i\) and we can use the expurgation argument independently for each type. Here we only focus on a given fixed type \(\hat{P}_i\). Applying Markov’s inequality to random variable \(p_e(\boldsymbol{x},\mathsf{C}_i)\), we obtain for every \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) \[\mathbb{P}\Big[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\geq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\Big]\Big] \leq\frac{1}{\eta},\] for any \(\rho>0\) and \(\eta>1\). Equivalently we have \[\mathbb{P}\Big[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\Big]\Big] \geq1-\frac{1}{\eta}.\label{eqn:bound95Markov95inequality95type}\tag{50}\]

For a given type-by-type code \(\mathcal{C}_i\), denote by \(N_0(\hat{P}_i,\mathcal{C}_i)\) the number of source sequences \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) that satisfy \[p_e(\boldsymbol{x},\mathcal{C}_i)^{\frac{1}{\rho}}\leq \eta\mathbb{E}\Big[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\Big].\label{eqn:bound95sequence95error95type}\tag{51}\] Over the random ensemble \(\mathsf{C}_i\), \(N_0(\hat{P}_i,\mathsf{C}_i)\) is a random variable. Now choosing \(\eta=2\), and using 50 the expected value of \(N_0(\hat{P}_i,\mathsf{C}_i)\) is bounded below as \[\mathbb{E}\big[N_0(\hat{P}_i,\mathsf{C}_i)\big]\geq \frac{|\mathcal{T}_n(\hat{P}_i)|}{2}.\] Therefore, we conclude that there exists a source code \(\mathcal{C}_i\) for type \(\hat{P}_i\), such that at least half of the sequences of that type satisfy the inequality \[p_e(\boldsymbol{x},\mathcal{C}_i)\leq \left(2\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\right]\right)^{\rho}.\label{eqn:bound95seq95error95type}\tag{52}\] Let us denote the set of above mentioned sequences as \(\mathcal{A}_{i1}\) where \(\mathcal{A}_{i1}\subset|\mathcal{T}_n(\hat{P}_i)|\) and \(|\mathcal{A}_{i1}|\geq\frac{|\mathcal{T}_n(\hat{P}_i)|}{2}\).

We now construct a code \(\mathcal{C}_{i1}\) for the set \(\mathcal{A}_{i1}\) from the code \(\mathcal{C}_i\) as follows: We keep all the sequences \(\boldsymbol{x}\in\mathcal{A}_{i1}\) in \(\mathcal{C}_i\), which satisfy 52 , and we expurgate rest of the sequences \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\backslash\mathcal{A}_{i1}\) from code \(\mathcal{C}_i\). Note that removing source sequences can only reduce the error probability of remaining ones.

The rest of sequences in \(\mathcal{T}_n(\hat{P}_i)\backslash\mathcal{A}_{i1}\) include at most half of the sequences from type \(\hat{P}_i\). We now repeat the procedure by considering the random coding ensemble for the remaining sequences \(\mathcal{T}_n(\hat{P}_i)\backslash\mathcal{A}_{i1}\) (denoted by \(\bar{\mathsf{C}}_i\)) and finding a good code \(\bar{\mathcal{C}}_i\) from this ensemble and constructing a code \(\mathcal{C}_{i2}\) for the set \(\mathcal{A}_{i2}\). Similarly to the analysis in 3.1 we apply this procedure successively for at most \(k_i=\log_{2}|\mathcal{T}_n(\hat{P}_i)|\leq n\log_{2}|\mathcal{X}|\) times and we guarantee that \(\bigcup_{j=1}^k\mathcal{A}_{ij}=\mathcal{T}_n(\hat{P}_i)\). Finally we construct the code \(\mathcal{C}_{{\rm ex},i}\) by combining all codes \(\mathcal{C}_{ij}\) as \(\mathcal{C}_{{\rm ex},i}=\{\mathcal{C}_{i1},\cdots,\mathcal{C}_{ik_i}\}\). The code \(\mathcal{C}_{{\rm ex},i}\) includes all the source sequences in \(\mathcal{T}_n(\hat{P}_i)\) and every sequence satisfies the desired bound as in 52 . Considering the number of codewords in each iteration as \(\frac{M}{k_i|\mathcal{P}_n(\mathcal{X})|}\), the total number of codewords of the code \(\mathcal{C}_{{\rm ex},i}\) is \(\frac{M}{|\mathcal{P}_n(\mathcal{X})|}\). In a similar way we obtain the code for every type and combine those to construct the type-by-type code \(\boldsymbol{\mathcal{C}}_{\rm ex}\).

4 Conclusions↩︎

We have introduced an expurgation method for source coding that is valid for general source and side information models and arbitrary decoding metrics. Building on the developed expurgation method, we have derived dual-domain multi-letter upper bounds on the error probability of an expurgated code. We have further specialized the bounds to memoryless source models and memoryless mismatched decoding metrics and derived two achievable exponents for the standard and type-by-type random coding ensembles; the latter is shown to coincide with the Csiszár and Körner’s exponent. We have shown existence of a code in each ensemble that achieves the maximum of the corresponding random coding and expurgated exponent. While the expurgated exponent of the standard ensemble is shown to be weaker of the two, its derivation is relatively simpler and does not rely on the method of types.

5 Proof of Theorem 1↩︎

Lemma 1 showed the existence of a good code in the standard random coding ensemble which satisfies an upper bound on the error probability for every source sequence. Here we show that this code achieves the exponent of Theorem 1. We first show the achievability of \(E_{q,\mathrm{ex}}(R)\) and then \(E_{q,\mathrm{r}}(R)\).

We start by bounding \(p_e(\boldsymbol{x},\mathcal{C})\) for a given source sequence \(\boldsymbol{x}\) and given standard code \(\mathcal{C}\) as follows

\[\begin{align} p_e(\boldsymbol{x},\mathcal{C})&=\mathbb{P}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]\\ &=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\mathbb{1}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]\\ &\leq\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\tag{54}\\ &=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) \right] \mathbb{1}\left[\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\\ &\leq\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\tag{55}, \end{align}\] where we use union bound in 54 and 55 holds for any \(s\geq0\).

Now considering the ensemble of random standard block source codes and denoting the induced random encoding function by \(\Phi(\cdot)\), we upper bound the \(\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\) using 55 as follows

\[\begin{align} \mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]&\leq\mathbb{E}\left[\left(\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^{\frac{1}{\rho}}\right]\\ &\leq\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\mathbb{E}\left[\mathbb{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\tag{56}\\ &\leq\frac{k}{M}\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\tag{57} \end{align}\] where 56 follows from inequality \((\sum\limits_i a_i)^{\frac{1}{\rho}}\leq\sum\limits_i a_i^{\frac{1}{\rho}}\) for \(\rho\geq 1\) and including \(\bar{\boldsymbol{x}}=\boldsymbol{x}\) in the summation, 57 follows from \(\mathbb{E}\left[\mathbb{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\leq\frac{k}{M}\) where \(k=n\log_2|\mathcal{X}|\) is an upper bound on the number of iterations in expurgation method.

Now substituting 57 in 49 from Lemma 1 and summing over all source sequences we find an upper bound on the error probability of the codebook \(\mathcal{C}_{\rm ex}\) as

\[\begin{align} p_e(\mathcal{C}_{\rm ex})&=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})p_e(\boldsymbol{x},\mathcal{C}_{\rm ex})\\ &\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})\Big(2\mathbb{E}\left[p_e(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\Big)^{\rho}\\ &\leq\left(\frac{2k}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}\left(\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{X}\boldsymbol{Y}}(\boldsymbol{x},\boldsymbol{y})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}\label{eqn:bound95expurgated} \end{align}\tag{58}\]

Equation 58 is valid for any discrete source and any decoding metric. We now specialize this to the case of memoryless sources and metrics, using \(q(\boldsymbol{x},\boldsymbol{y})=\prod_{i=1}^{n}q(x_i,y_i)\). Therefore we obtain \[\begin{align} p_e(\mathcal{C}_{\rm ex})&\leq\left(\frac{2k}{M}\right)^{\rho}\left(\sum\limits_{x\in\mathcal{X}}\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{XY}(x,y)\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}\right)^{n}\\ &=e^{-n(\rho (R-\delta_n)-E_{\rm{x}}(\rho,s))} \end{align}\] where \(R=\frac{\log M}{n}\), \(\delta_n=\frac{\log(2n\log_2|\mathcal{X}|)}{n}\to 0\) as \(n\to\infty\) and \[E_{\rm{x}}(\rho,s)=\log\sum\limits_{x\in\mathcal{X}}\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{XY}(x,y)\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho},\label{eqn:Ex95St}\tag{59}\]

Hence, we show the achievability of the exponent \(E_{q,\mathrm{ex}}(R)\) by optimizing over \(\rho,s\) as \[E_{q,\mathrm{ex}}(R)=\max_{\rho\geq 1,s\geq 0}\rho R-E_{\rm{x}}(\rho,s).\label{eqn:expurgated95exponent}\tag{60}\]

To show that the same code of Lemma 1 achieves \(E_{q,\mathrm{r}}(R)\) we use 49 of Lemma 1 with \(\rho=1\), and obtain

\[\begin{align} p_e(\boldsymbol{x},\mathcal{C}_{\rm ex})\leq2\mathbb{E}\left[P_e(\boldsymbol{x},\mathsf{C})\right].\label{eqn:special95case95st} \end{align}\tag{61}\]

Averaging over all source sequences we obtain \[\begin{align} p_e(\mathcal{C}_{\rm ex})&=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})p_e(\boldsymbol{x},\mathcal{C}_{\rm ex})\\ &\leq2\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})\mathbb{E}\left[P_e(\boldsymbol{x},\mathsf{C})\right]\\ &=2\mathbb{E}\left[\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})P_e(\boldsymbol{x},\mathsf{C})\right]\\ &=2\mathbb{E}\left[p_e(\mathsf{C})\right],\label{eqn:ensemble95average} \end{align}\tag{62}\] which shows that the error probability of \(\mathcal{C}_{\rm ex}\) is upper bounded by twice the ensemble average error probability.

Now we derive an upper bound on the ensemble average error probability following the derivations in [2].

We start by bounding \(p_e(\boldsymbol{y},\mathcal{C})\) for a given side information sequence \(\boldsymbol{y}\) and given standard code \(\mathcal{C}\) as follows

\[\begin{align} p_e(\boldsymbol{y},\mathcal{C})&=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathbb{1}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]\\ &\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^\rho\tag{63}\\ &=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\right]\mathbb{1}\left[ \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^\rho\\ &\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{1}\left[ \phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^\rho,\tag{64} \end{align}\] where 63 follows from using the inequality \(\mathbb{1}\left[\bigcup\limits_{i}A_i\right]\leq\left(\sum\limits_{i}\mathbb{1}\left[A_{i}\right]\right)^{\rho}\) for any set of events \(\{A_i\}\) and \(\rho\in[0,1]\) and 64 holds for any \(s\geq0\).

Now considering the ensemble of random standard block source codes we upper bound the \(\mathbb{E}\left[p_e(\boldsymbol{y},\mathsf{C})\right]\) using 64 as follows \[\begin{align} \mathbb{E}\left[p_e(\boldsymbol{y},\mathsf{C})\right]&\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathbb{E}\left[\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{1}\left[ \Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right)^\rho\right]\\ &\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{X}^n\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{E}\left[\mathbb{1}\left[ \Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right] \right)^\rho\tag{65}\\ &\leq\left(\frac{k}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^\rho\tag{66}, \end{align}\] where 65 follows from Jensen’s inequality and the concavity of \(x^{\rho}\) for \(\rho\in\left[0,1\right]\) and 66 follows from \(\mathbb{E}\left[\mathbb{1}\left[ \Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\leq\frac{k}{M}\) and including \(\bar{\boldsymbol{x}}=\boldsymbol{x}\) in the summation.

Averaging over all side information sequences we obtain an upper bound on the ensemble average error probability as \[\begin{align} \mathbb{E}\left[p_e(\mathsf{C})\right]&=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}}(\boldsymbol{y})\mathbb{E}\left[p_e(\boldsymbol{y},\mathsf{C})\right]\\ &\leq\left(\frac{k}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n,\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{X}\boldsymbol{Y}}(\boldsymbol{x},\boldsymbol{y})\left(\sum_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^\rho\label{eqn:random95coding95bound} \end{align}\tag{67}\] where 67 holds for any \(\rho\in\left[0,1\right]\) and \(s\geq0\). Introducing 67 in 62 and particularizing it to the case of memoryless sources and metrics we obtain \[\begin{align} p_e(\mathcal{C}_{\rm ex})&\leq2\left(\frac{k}{M}\right)^{\rho}\left(\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\right)^{n}\\ &=e^{-n(\rho (R-\delta_n)-E_{\rm{s}}(\rho,s)-\delta'_n)} \end{align}\] where \(\delta_n=\frac{\log k}{n}\to 0\) and \(\delta'_n=\frac{\log 2}{n}\to 0\) as \(n\to\infty\) and \[E_{\rm{s}}(\rho,s)=\log\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\] Hence, we show the achievability of the exponent \(E_{q,\mathrm{r}}(R)\) by optimizing over \(\rho,s\) as in 12 .

6 Proof of Theorem [Thm:Exponent95Type]↩︎

Lemma 2 showed the existence of a good code in the type-by-type random coding ensemble which satisfies an upper bound on the error probability for every source sequence. Here we show that this code achieves the exponent of Theorem [Thm:Exponent95Type]. As for the proof in the previous section, we first show the achievability of \(E^{\rm tt}_{q,\mathrm{ex}}(R)\) and then that of \(E^{\rm tt}_{q,\mathrm{r}}(R)\).

We start by bounding \(P_e(\boldsymbol{x},\mathcal{C}_i)\) for a given source sequence \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_{i})\) and given type-by-type code \(\boldsymbol{\mathcal{C}}\) with subcode \(\mathcal{C}_i\) for type \(\hat{P}_{i}\) as follows \[\begin{align} P_e(\boldsymbol{x},\mathcal{C}_i)&=\mathbb{P}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y}) , \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right\}\right]\\ &=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\mathbb{1}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y}) , \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right\}\right]\\ &\leq\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right]\tag{68}\\ &=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) \right] \mathbb{1}\left[\phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right]\\ &\leq\sum\limits_{\substack{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}}\mathbb{1}\left[\phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right]\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\tag{69} \end{align}\] where we use union bound in 68 and 69 holds for any \(s\geq0\).

Now considering the ensemble of random type-by-type codes and denoting the induced random encoding function by \(\Phi_i(\cdot)\), we upper bound the \(\mathbb{E}\left[P_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\right]\) using 69 as follows

\[\begin{align} \mathbb{E}\left[P_e(\boldsymbol{x},\mathsf{C}_i)^{\frac{1}{\rho}}\right]&\leq\mathbb{E}\left[\left(\sum\limits_{\substack{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)\\\bar{\boldsymbol{x}}\neq\boldsymbol{x}}}}\mathbb{1}\left[\Phi_i(\bar{\boldsymbol{x}})=\Phi_i(\boldsymbol{x})\right]\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^{\frac{1}{\rho}}\right]\\ &\leq\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)}\mathbb{E}\left[\mathbb{1}\left[\Phi_i(\bar{\boldsymbol{x}})=\Phi_i(\boldsymbol{x})\right]\right]\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\tag{70}\\ &\leq\frac{k_i|\mathcal{P}_n(\mathcal{X})|}{M}\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)}\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\tag{71} \end{align}\] where 70 follows from inequality \((\sum\limits_i a_i)^{\frac{1}{\rho}}\leq\sum\limits_i a_i^{\frac{1}{\rho}}\) for \(\rho\geq 1\) and including \(\bar{\boldsymbol{x}}=\boldsymbol{x}\) in the summation, 71 follows from \(\mathbb{E}\left[\mathbb{1}\left[\Phi_i(\bar{\boldsymbol{x}})=\Phi_i(\boldsymbol{x})\right]\right]\leq\frac{k_i|\mathcal{P}_n(\mathcal{X})|}{M}\) where \(k_i=\log_{2}|\mathcal{T}_n(\hat{P}_i)|\) is an upper bound on the number of iterations in expurgation method for the type-by-type coding.

Now substituting 71 in 53 from Lemma 2 we find an upper bound on the error probability of every sequence \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) in the codebook \(\mathcal{C}_{{\rm ex},i}\) as

\[\begin{align} p_e(\boldsymbol{x},\mathcal{C}_{{\rm ex},i})\leq\left(\frac{2k_i|\mathcal{P}_n(\mathcal{X})|}{M}\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)}\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}\label{eqn:bound95sequence95expurgated} \end{align}\tag{72}\]

Notice that using 72 and summing over all source sequences \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) we can find an upper bound that depends on the type \(\hat{P}_i\). Therefore, resulting upper bound on the error probability of the codebook \(\mathcal{C}\) requires maximization over the type. In order to find a simpler bound we can weaken the bound in 72 by including all \(\bar{\boldsymbol{x}}\) in the sum, however to keep the bound tight we introduce ratio of an arbitrary cost function as \(\frac{e^{a(\bar{\boldsymbol{x}})}}{e^{a(\boldsymbol{x})}}\) where the cost function \(a(\boldsymbol{x})\) depends on the sequence \(\boldsymbol{x}\) only through its type. Observe that the ratio is equal to \(1\) when both \(\boldsymbol{x}\) and \(\bar{\boldsymbol{x}}\) have the same type, also this cost function can be optimized for to obtain the tightest bound. By upper-bounding \(k_i\) by \(k=n\log_{2}|\mathcal{X}|\) we obtain \[\begin{align} p_e(\boldsymbol{\mathcal{C}}_{\rm ex})&=\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}}(\boldsymbol{x})p_e(\boldsymbol{x},\mathcal{C}_{{\rm ex},i})\\&\leq\left(\frac{2k|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}}(\boldsymbol{x})\left(\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\left(\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\frac{e^{a(\bar{\boldsymbol{x}})}}{e^{a(\boldsymbol{x})}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}.\label{eqn:bound95expurgated95Type} \end{align}\tag{73}\]

Equation 73 is valid for any discrete source and any decoding metric. We now specialize this to the case of memoryless sources, metrics, and cost functions using \(q(\boldsymbol{x},\boldsymbol{y})=\prod_{i=1}^{n}q(x_i,y_i)\) and \(a(\boldsymbol{x})=\sum\limits_{i=1}^{n}a(x_i)\). Therefore we obtain \[\begin{align} p_e(\boldsymbol{\mathcal{C}}_{\rm ex})&\leq\left(\frac{2k|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\left(\sum\limits_{x\in\mathcal{X}}P_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}\right)^{n}\\ &=e^{-n(\rho (R-\delta_n)-E^{\rm tt}_{\rm{x}}(\rho,s,a))} \end{align}\] where \(\delta_n=\frac{\log2k|\mathcal{P}_n(\mathcal{X})|}{n}\to 0\) as \(n\to\infty\) and \[E^{\rm tt}_{\rm{x}}(\rho,s,a(\cdot))=\log\sum\limits_{x\in\mathcal{X}}P_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^{\rho}.\label{eqn:Ex95Type}\tag{74}\] Hence, we show the achievability of the exponent \(E_{q,\mathrm{ex}}(R)\) by optimizing over \(\rho,s,a(\cdot)\) as \[E^{\rm tt}_{q,\mathrm{ex}}(R)=\max_{\rho\geq 1,s\geq 0,a(\cdot)}\rho R-E_{\rm{x}}(\rho,s,a(\cdot)).\label{eqn:expurgated95exponent95Type}\tag{75}\]

To show that the same code of Lemma [Thm:Exponent95Type] achieves \(E^{\rm tt}_{q,\mathrm{r}}(R)\) we use 53 of Lemma 2 with \(\rho=1\), and obtain that for every source sequence \(\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)\) \[\begin{align} p_e(\boldsymbol{x},\boldsymbol{\mathcal{C}}_{\rm ex})\leq2\mathbb{E}\left[P_e(\boldsymbol{x},\mathsf{C}_i)\right].\label{eqn:special95case} \end{align}\tag{76}\]

Averaging over all source sequences similar to the proof of Theorem [th:standard] we obtain \[\begin{align} p_e(\boldsymbol{\mathcal{C}}_{\rm ex})\leq2\mathbb{E}\left[p_e(\boldsymbol{\mathsf{C}})\right],\label{eqn:ensemble95average95tbt} \end{align}\tag{77}\] which shows that the error probability of \(\boldsymbol{\mathcal{C}}_{\rm ex}\) is upper bounded by twice the average error probability over type-by-type ensemble.

Now we derive an upper bound on the type-by-type ensemble average error probability following similar steps as Section 5.

We start by bounding \(p_e(\boldsymbol{y},\boldsymbol{\mathcal{C}})\) for a given side information sequence \(\boldsymbol{y}\) and given type-by-type code \(\boldsymbol{\mathcal{C}}\) as follows

\[\begin{align} p_e(\boldsymbol{y},\boldsymbol{\mathcal{C}})&=\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathbb{1}\left[\bigcup_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i) \\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right\}\right]\\ &\leq\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i) \\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\mathbb{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y}) , \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right]\right)^\rho\tag{78}\\ &\leq\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i) \\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{1}\left[ \phi_i(\bar{\boldsymbol{x}})=\phi_i(\boldsymbol{x})\right]\right)^\rho,\tag{79} \end{align}\] where 78 follows from using the inequality \(\mathbb{1}\left[\bigcup\limits_{i}A_i\right]\leq\left(\sum\limits_{i}\mathbb{1}\left[A_{i}\right]\right)^{\rho}\) for any set of events \(\{A_i\}\) and \(\rho\in[0,1]\) and 79 holds for any \(s\geq0\).

Now considering the ensemble of random type-by-type block source codes we upper bound the \(\mathbb{E}\left[p_e(\boldsymbol{y},\boldsymbol{\mathsf{C}})\right]\) using 79 as follows \[\begin{align} \mathbb{E}\left[p_e(\boldsymbol{y},\boldsymbol{\mathsf{C}})\right]&\leq\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathbb{E}\left[\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i) \\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{1}\left[ \Phi_i(\bar{\boldsymbol{x}})=\Phi_i(\boldsymbol{x})\right]\right)^\rho\right]\\ &\leq\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\substack{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i) \\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{E}\left[\mathbb{1}\left[ \Phi_i(\bar{\boldsymbol{x}})=\Phi_i(\boldsymbol{x})\right]\right] \right)^\rho\tag{80}\\ &\leq\left(\frac{k_i|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\sum\limits_{i=1}^{|\mathcal{P}_n(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_n(\hat{P}_i)}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\bar{\boldsymbol{x}}\in\mathcal{T}_n(\hat{P}_i)}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^\rho\tag{81},\\ &\leq\left(\frac{k|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\frac{e^{a(\bar{\boldsymbol{x}})}}{e^{a(\boldsymbol{x})}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^\rho\tag{82}, \end{align}\] where 80 follows from Jensen’s inequality and the concavity of \(x^{\rho}\) for \(\rho\in\left[0,1\right]\) and 81 follows from \(\mathbb{E}\left[\mathbb{1}\left[ \Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\leq\frac{k}{M}\) and 82 follows from weakening the bound by upper bounding \(k_i\) with \(k=n\log_{2}|\mathcal{X}|\) and including all \(\bar{\boldsymbol{x}}\) in the sum, however to keep the bound tight we introduce ratio of an arbitrary cost function as \(\frac{e^{a(\bar{\boldsymbol{x}})}}{e^{a(\boldsymbol{x})}}\) where the cost function depends on the sequence \(\boldsymbol{x}\) only through its type..

Averaging over all side information sequences we obtain an upper bound on the type-by-type ensemble average error probability as \[\begin{align} \mathbb{E}\left[p_e(\boldsymbol{\mathsf{C}})\right]&=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{Y}}(\boldsymbol{y})\mathbb{E}\left[p_e(\boldsymbol{y},\boldsymbol{\mathsf{C}})\right]\\ &\leq\left(\frac{k|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\sum\limits_{\boldsymbol{x}\in\mathcal{X}^n,\boldsymbol{y}\in\mathcal{Y}^n}P_{\boldsymbol{X}\boldsymbol{Y}}(\boldsymbol{x},\boldsymbol{y})\left(\sum_{\bar{\boldsymbol{x}}\in\mathcal{X}^n}\frac{e^{a(\bar{\boldsymbol{x}})}}{e^{a(\boldsymbol{x})}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\right)^\rho\label{eqn:random95coding95bound95Type} \end{align}\tag{83}\] where 83 holds for any \(\rho\in\left[0,1\right]\) and \(s\geq0\). Introducing 83 in 77 and particularizing it to the case of memoryless sources, metrics and cost functions we obtain \[\begin{align} p_e(\boldsymbol{\mathcal{C}}_{\rm ex})&\leq2\left(\frac{k|\mathcal{P}_n(\mathcal{X})|}{M}\right)^{\rho}\left(\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\right)^{n}\\ &=e^{-n(\rho (R-\delta_n)-E^{\rm tt}_{\rm{s}}(\rho,s,a)-\delta'_n)} \end{align}\] where \(\delta_n=\frac{\log k|\mathcal{P}_n(\mathcal{X})|}{n}\to 0\) and \(\delta'_n=\frac{\log 2}{n}\to 0\) as \(n\to\infty\) and \[E^{\rm tt}_{\rm{s}}(\rho,s,a(\cdot))=\log\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\] Hence, we show the achievability of the exponent \(E^{\rm tt}_{q,\mathrm{r}}(R)\) by optimizing over \(\rho,s,a(\cdot)\) as in 16 .

7 Proof of Proposition 1: Primal-dual Equivalence↩︎

We start by showing the equivalence of 8 to 16 . We rewrite 8 as \[E^{\mathrm{ck}}_{q,\mathrm{r}}(R)= \min_{Q}\left[D(Q\|P_{X})+ E_{q,\mathrm{r}}^{\mathrm{cc}}\left(H(Q)-R,Q,P_{Y|X}\right)\right],\label{eqn:primal95form95rc95exponent}\tag{84}\] \[E_{q,\mathrm{r}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}(Q)}\left[D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}})+|I(\tilde{Y};\hat{X})+R-H(Q)|^{+}\right],\label{eqn:Channel95CC95rc95exponent}\tag{85}\] where we use \(P_{\tilde{X}}=Q\) and the identity \[D(P_{\tilde{X}\tilde{Y}}\|P_{XY})=D(P_{\tilde{X}}\|P_{X})+D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}}).\label{eqn:identity}\tag{86}\] to split the minimization in 8 .

Defining \[\mathcal{S}(Q)=\left\lbrace P_{\tilde{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y}):P_{\tilde{X}}=Q\right\rbrace,\] \[\mathcal{T}(P_{\tilde{X}\tilde{Y}},Q)=\left\lbrace \tilde{P}_{\hat{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y}):\tilde{P}_{\hat{X}}=Q,\tilde{P}_{\tilde{Y}}=P_{\tilde{Y}},\mathbb{E}_{\tilde{P}}\left[\log q(\hat{X},\tilde{Y})\right]\geq\mathbb{E}_{P}\left[\log q(\tilde{X},\tilde{Y})\right]\right\rbrace,\] we can rewrite 85 as \[E_{q,\mathrm{r}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{P_{\tilde{X}\tilde{Y}}\in\mathcal{S}(Q)}\min_{\tilde{P}_{\hat{X}\tilde{Y}}\in\mathcal{T}(P_{\tilde{X}\tilde{Y}},Q)}\left[D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}})+|I(\tilde{Y};\hat{X})+R-H(Q)|^{+}\right].\label{eqn:Channel95CC95rc95exp95break}\tag{87}\]

The dual form of the constant composition random coding error exponent in 87 is derived in scarlett2014_1?, using which we rewrite it as \[\begin{align} E_{q,\mathrm{r}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\sup_{\rho\in\left[0,1\right]}E_{0}^{\mathrm{cc}}(Q,\rho)-\rho(H(Q)-R), \end{align}\] where \[\begin{align} E_{0}^{\mathrm{cc}}(Q,\rho)=\sup_{s\geq 0,b(\cdot)}-\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}Q(\bar{x})\frac{e^{b(\bar{x})}}{e^{b(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}.\label{eqn:RC95cc95channel} \end{align}\tag{88}\] Defining \(e^{a(x)}=Q(x)e^{b(x)}\), we can rewrite 98 as \[\begin{align} E_{0}^{\mathrm{cc}}(Q,\rho)&=\sup_{s\geq 0,a(\cdot)}-\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}Q(x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\\ &=\rho H(Q)+\sup_{s\geq 0,a(\cdot)}-\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\label{eqn:RC95cc95rewrite} \end{align}\tag{89}\]

Introducing 89 in 88 , noting that the objective in 88 is concave in \(Q\) and using Fan’s minimax theorem interchanging the minimum and supremum we obtain \[\begin{align} E_{\rm{ex}}(R)=\sup_{\rho\geq 1}\left[\rho R+\sup_{s\geq 0,a(\cdot)}\min_{Q}L\right],\label{eqn:RC95exp95primal} \end{align}\tag{90}\] where \[L=\sum\limits_{x\in\mathcal{X}}Q(x)\log\frac{Q(x)}{P_{X}(x)}-\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}.\label{eqn:minimization95objective95rc}\tag{91}\]

Setting \(\frac{\partial L}{\partial Q}=0\) we find the minimizing distribution as the following mismatched tilted distribution \[Q(x)=CP_{X}(x)\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\label{eqn:minimizing95distribution95rc}\tag{92}\] where \(C\) is the normalization constant given by \[C^{-1}=\sum\limits_{x\in\mathcal{X}}P_{X}(x)\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}.\]

From 92 we have \(\frac{Q(x)}{CP_{X}(x)}=\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\), replacing it in 91 we obtain \[\begin{align} \min_{Q}L=-\log \sum\limits_{x\in\mathcal{X}}P_{X}(x)\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\rho}\label{eqn:min95L95rc} \end{align}\tag{93}\] Plugging 93 into 90 we obtain the dual form of the type-by-type random coding exponent in 16 .

To show the equivalence of 9 to 17 . We rewrite 9 as

\[E^{\mathrm{ck}}_{q,\rm ex}(R) = \min_{Q}\left[D(Q\|P_{X})+ E_{q,\mathrm{ex}}^{\mathrm{cc}}\left(H(Q)-R,Q,P_{Y|X}\right)\right],\label{eqn:primal95form95expurgated95exponent}\tag{94}\] where \[E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{\substack{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}(Q)\\H(\hat{X}|\tilde{X})\geq R}}\left[D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}})+I(\tilde{X}\tilde{Y};\hat{X})+R-H(Q)\right]\label{eqn:Channel95CC95expurgated95exponent}\tag{95}\] and \[\mathcal{T}(Q)=\left\lbrace P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{X}\times\mathcal{Y}):P_{\hat{X}}=P_{\tilde{X}}=Q,\mathbb{E}\left[\log q(\hat{X},\tilde{Y})\right]\geq\mathbb{E}\left[\log q(\tilde{X},\tilde{Y})\right]\right\rbrace,\] where we use \(P_{\tilde{X}}=Q\) and the identity 86 to split the minimization in 9 .

Defining \[\mathcal{S}(Q)=\left\lbrace \tilde{P}_{\hat{X}\tilde{X}}\in\mathcal{P}(\mathcal{X}\times\mathcal{X}):\tilde{P}_{\hat{X}}=\tilde{P}_{\tilde{X}}=Q\right\rbrace,\] \[\mathcal{T}(\tilde{P}_{\hat{X}\tilde{X}})=\left\lbrace P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{X}\times\mathcal{Y}):P_{\hat{X}\tilde{X}}=\tilde{P}_{\hat{X}\tilde{X}},\mathbb{E}\left[\log q(\hat{X},\tilde{Y})\right]\geq\mathbb{E}\left[\log q(\tilde{X},\tilde{Y})\right]\right\rbrace,\] we can rewrite 95 as \[E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{\substack{\tilde{P}_{\hat{X}\tilde{X}}\in\mathcal{S}(Q)\\H(\hat{X}|\tilde{X})\geq R}}\min_{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}(\tilde{P}_{\hat{X}\tilde{X}})}\left[D(P_{\hat{X}\tilde{X}\tilde{Y}}\|\tilde{P}_{\hat{X}\tilde{X}}\times P_{Y|X})+R-H(\hat{X}|\tilde{X})\right]\label{eqn:Channel95CC95expurgated95exp95broken}\tag{96}\] where we use [8] as \[D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}})+I(\tilde{X}\tilde{Y};\hat{X})=D(P_{\hat{X}\tilde{X}\tilde{Y}}\|\tilde{P}_{\hat{X}\tilde{X}}\times P_{Y|X})+I(\tilde{X};\hat{X}).\]

For a given \(\tilde{P}_{\hat{X}\tilde{X}}\in\mathcal{S}(Q)\), \(R-H(\hat{X}|\tilde{X})\) is constant, therefore we consider the optimization problem \[\min_{P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}(\tilde{P}_{\hat{X}\tilde{X}})}D(P_{\hat{X}\tilde{X}\tilde{Y}}\|\tilde{P}_{\hat{X}\tilde{X}}\times P_{Y|X}).\]

The dual of this optimization problem has been found in [15]. Using very similar arguments we find the following equivalent forms of 96 as \[\begin{align} E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})&=\sup_{s\geq0}\min_{\substack{P_{X\bar{X}}:P_{X}=Q,P_{\bar{X}}=Q\\H(\bar{X}|X)\geq R}}\mathbb{E}_{P}\left[d_{s}(X,\bar{X})\right]+R-H(\bar{X}|X),\\ &=\sup_{\rho\geq1}E_{x}^{\mathrm{cc}}(Q,\rho)-\rho(H(Q)-R)\label{eqn:lagrange95dual}, \end{align}\tag{97}\] where \[d_s(x,\bar{x})=-\log\sum\limits_{y}P_{Y|X}(y|x)\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^{s},\] and \[\begin{align} E_{\rm{x}}^{\mathrm{cc}}(Q,\rho)=\sup_{s\geq 0,b(\cdot)}-\rho\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{\bar{x}\in\mathcal{X}}Q(\bar{x})\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{b(\bar{x})}}{e^{b(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}.\label{eqn:Ex95cc95channel} \end{align}\tag{98}\]

Using 97 in 94 we obtain \[\begin{align} E^{\mathrm{ck}}_{\rm{ex}}(R)=\min_{Q}\left[ D(Q\|P_{X})+\sup_{\rho\geq 1}\left[E_{x}^{\mathrm{cc}}(Q,\rho)-\rho(H(Q)-R)\right] \right],\label{eqn:Expurgated95exp95primal} \end{align}\tag{99}\] Defining \(e^{a(x)}=Q(x)^{\rho}e^{b(x)}\), we can rewrite 98 as \[\begin{align} E_{\rm{x}}^{\mathrm{cc}}(Q,\rho)&=\sup_{s\geq 0,a(\cdot)}-\rho\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{\bar{x}\in\mathcal{X}}Q(x)\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\\ &=\rho H(Q)+\sup_{s\geq 0,a(\cdot)}-\rho\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\label{eqn:Ex95cc95rewrite} \end{align}\tag{100}\]

Introducing 100 in 99 , noting that the objective in 99 is concave in \(Q\) and using Fan’s minimax theorem interchanging the minimum and supremum we obtain \[\begin{align} E^{\mathrm{ck}}_{\rm{ex}}(R)=\sup_{\rho\geq 1}\left[\rho R+\sup_{s\geq 0,a(\cdot)}\min_{Q}L\right],\label{eqn:exp95dual} \end{align}\tag{101}\] where \[L=\sum\limits_{x\in\mathcal{X}}Q(x)\log\frac{Q(x)}{P_{X}(x)}-\rho\sum\limits_{x\in\mathcal{X}}Q(x)\log\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\label{eqn:minimization95objective}\tag{102}\] Setting \(\frac{\partial L}{\partial Q}=0\) we find the minimizing distribution as the following mismatched tilted distribution \[Q(x)=CP_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^\rho\label{eqn:minimizing95distribution}\tag{103}\] where \(C\) is the normalization constant given by \[C^{-1}=\sum\limits_{x\in\mathcal{X}}P_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^\rho.\]

From 103 we have \(\frac{Q(x)}{CP_{X}(x)}=\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^\rho\), replacing it in 102 we obtain \[\begin{align} \min_{Q}L=-\log \sum\limits_{x\in\mathcal{X}}P_{X}(x)\left(\sum\limits_{\bar{x}\in\mathcal{X}}\left(\sum\limits_{y\in\mathcal{Y}}P_{Y|X}(y|x)\frac{e^{a(\bar{x})}}{e^{a(x)}}\left(\frac{q(\bar{x},y)}{q(x,y)}\right)^s\right)^{\frac{1}{\rho}}\right)^\rho\label{eqn:min95L} \end{align}\tag{104}\] Plugging 104 into 101 we obtain the dual form of the type-by-type expurgated exponent in 17 .

References↩︎

---

1. Mehdi Dabirnia is with Centre Tecnològic de Telecomunicacions de Catalunya (CTTC), 08860 Castelldefels, Spain; e-mail: mehdi.dabirnia@cttc.cat. Hamdi Joudeh is with the Department of Electrical Engineering, Eindhoven University of Technology, Eindhoven, 5600 MB, The Netherlands; e-mail: h.joudeh@tue.nl. Albert Guillén i Fàbregas is with the Department of Engineering, University of Cambridge, CB2 1PZ Cambridge, U.K., the Department of Signal Theory and Communications and the Institute of Mathematics (IMTech), Universitat Politècnica de Catalunya (UPC) 08034 Barcelona, Spain (guillen@ieee.org).↩︎

2. This work was supported in part by the European Research Council under Grants 101116550, 101142747 and 101158232, and in part by the Spanish Ministry of Economy and Competitiveness under Grants PID2020-116683GB-C22 and PID2021-128373OB-I00 and partially by the WAVE-XL project (PID2024-160457OB-I00) funded by MCIN/AEI/10.13039/501100011033 and by FEDER, UE.↩︎

3. Dual domain expressions can be derived from their primal domain counterparts using Lagrange duality techniques.↩︎