Dual Domain Expurgated Error Exponents for Source Coding with Side Information Mehdi Dabirnia, Hamdi Joudeh, Albert Guillén i Fàbregas Abstract We introduce an expurgation method for source coding with side information that enables direct dual-domain derivations of expurgated error exponents. Dual-domain methods yield optimization problems over few parameters, with any sub-optimal choice resulting in an achievable exponent, as opposed to primal-domain optimization over distributions. In addition, dual-domain methods naturally allow for general alphabets and/or memory. We derive two such expurgated error exponents for different random-coding ensembles. We show the better of the exponents coincides with the Csiszár-Körner exponent obtained via a graph decomposition lemma. We show some numerical examples that illustrate the differences between the two exponents and show that in the case of source coding without side information, the expurgated exponent coincides with the error exponent of the source optimal code. I 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 message index m , chosen from a set of M message indices. 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 message index m\in\{1,\dotsc,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}] (1) 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 message indices (or bins) uniformly at random in a pairwise independent manner. The corresponding achievable exponent is E_{\mathrm{r}}(R)=\max_{\rho\in[0,1]}\rho R-E_{0}(\rho) (2) where the function E_{0}(\rho) is defined as 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}. (3) 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 from in ( 2 ) is known as a dual domain expression. An equivalent primal domain expression for E_{\mathrm{r}}(R) is given as 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|^{+} (4) 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 ( 4 ) 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 take the following form E_{\mathrm{sp}}(R)=\sup_{\rho>0}\rho R-E_{0}(\rho). (5) We will refer to this as the sphere-packing exponent , as it closely resembles the sphere-packing exponent in channel coding [ 7 ] . 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 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}). (6) Both E_{\mathrm{r}}(R) and E_{\mathrm{sp}}(R) are non-negative for rates in the range H(X|Y)0 and every distribution P_{XY}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y}) there exists a standard block source code with maximum metric decoder ( 9 ) employing decoding metric q(x,y) that achieves the exponent E_{q}(R)=\max\{E_{q,\mathrm{r}}(R),E_{q,\mathrm{ex}}(R)\} (14) where E_{q,\mathrm{r}}(R)=\sup_{0\leq\rho\leq 1,s\geq 0}\rho R-\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}, (15) and E_{q,\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{q(\bar{x},y)}{q(x,y)}\right)^{s}\right)^{\frac{1}{\rho}}\right)^{\rho}. (16) Proof. The proof is structured in two parts. The first part consists of showing that there exists a code for which the error probability for every source sequence \boldsymbol{x}\in\mathcal{X}^{n} meets a certain upper bound (stated in Lemma 1 ). This bound is derived in Section III-A by introducing a method for expurgation in source coding with standard ensemble. The second part of the proof is the analysis of the bound in Lemma 1 , which results in the exponent ( 14 ). This can be found in Section IV . ∎ In deriving the error exponent of Theorem 16 we derive n -letter bounds in ( 93 ) and ( 111 ) 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. II-B 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 |\mathcal{M}_{i}| codewords. 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 . Definition 2 . The Type-by-Type Random Coding Ensemble is the set of all ( n,R ) block codes for the source alphabet \mathcal{X} with a probability measure over the codes having the following property: For every source type \hat{P}_{i} , i\in\{1,\cdots,|\mathcal{P}_{n}(\mathcal{X})|\} , each source sequence \boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i}) is independently assigned with equal probability \frac{1}{|\mathcal{M}_{i}|} to each of the codewords in \mathcal{M}_{i} . 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})=\argmax_{\boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i}):\phi_{i}(\boldsymbol{x})=m}q(\boldsymbol{x},\boldsymbol{y}), (17) 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. Theorem 2 (Type-by-Type Random Coding) . For every R>0 and every distribution P_{XY}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y}) there exists a type-by-type block source code with maximum metric decoder ( 17 ) employing decoding metric q(x,y) that achieves the exponent E_{q}^{\rm tt}(R)=\max\{E^{\rm tt}_{q,\mathrm{r}}(R),E^{\rm tt}_{q,\mathrm{ex}}(R)\} (18) where E^{\rm tt}_{q,\mathrm{r}}(R)=\sup_{0\leq\rho\leq 1,s\geq 0,a(\cdot)}\rho R-\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}, (19) and E^{\rm tt}_{q,\mathrm{ex}}(R)=\sup_{\rho\geq 1,s\geq 0,a(\cdot)}\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)\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}. (20) Proof. The proof is structured in two parts. The first part consists of showing that there exists a code for which the error probability for every source sequence \boldsymbol{x}\in\mathcal{X}^{n} meets a certain upper bound (stated in Lemma 2 ). This bound is derived in Section III-B by extending the introduced expurgation method to type-by-type ensemble. The second part of the proof is the analysis of the bound in Lemma 2 , which results in the exponent ( 18 ). This can be found in Section V . ∎ In deriving the error exponent of Theorem 2 we derive n -letter bounds in ( 125 ) and ( 140 ) 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. Proposition 1 (Primal-dual equivalence) . The dual-domain error exponent derived in Theorem 18 coincides with the Csiszár-Körner exponent ( 13 ) derived in the primal domain via graph decomposition, i.e., E^{\rm tt}_{q}(R)=E^{\mathrm{ck}}_{q}(R). (21) Proof. The proof has two parts. In the first part the equivalence of E^{\mathrm{ck}}_{q,\mathrm{ex}}(R,P_{XY}) in ( 11 ) to E^{\rm tt}_{q,\mathrm{ex}}(R) in ( 20 ) is shown. In the second part the equivalence of E^{\mathrm{ck}}_{q,\mathrm{r}}(R,P_{XY}) in ( 10 ) to E^{\rm tt}_{q,\mathrm{r}}(R) in ( 19 ) is shown. The proof can be found in Section VI . ∎ 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, \displaystyle E^{\mathrm{tt}}_{q,\rm r}(R) \displaystyle=D(Q\|P_{X})+E_{q,\mathrm{r}}^{\mathrm{cc}}\left(H(Q)-R,Q,P_{Y|X}\right), (22) \displaystyle E^{\mathrm{tt}}_{q,\rm ex}(R) \displaystyle=D(\tilde{Q}\|P_{X})+E_{q,\mathrm{ex}}^{\mathrm{cc}}\left(H(\tilde{Q})-R,\tilde{Q},P_{Y|X}\right), (23) where \displaystyle Q_{X}(x) \displaystyle=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^{*}}, (24) \displaystyle\tilde{Q}_{X}(x) \displaystyle=\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^{*}}, (25) and C and \tilde{C} are the normalization constants and s^{*},\rho^{*} and a^{*}(\cdot) in ( 24 ) and ( 25 ) are the optimizing choices, respectively in ( 19 ) and ( 20 ) 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 . For every mismatched decoder employing decoding metric q(x,y) , we have that E_{q,\mathrm{r}}(R)\leq E^{\rm tt}_{q,\mathrm{r}}(R)\leq E_{\mathrm{r}}(R), (26) where E_{\mathrm{r}}(R) is defined in ( 2 ) and the equality E^{\rm tt}_{q,\mathrm{r}}(R)=E_{\mathrm{r}}(R) holds for any q(x,y)=e^{b(x)+c(y)}P_{X|Y}(x|y)^{\tau} (27) with arbitrary b(x) , c(y) and \tau>0 . Furthermore, the equality E_{q,\mathrm{r}}(R)=E_{\mathrm{r}}(R) holds for any q(x,y)=e^{c(y)}P_{X|Y}(x|y)^{\tau} (28) with arbitrary c(y) and \tau>0 . Proof. The first inequality in ( 26 ) follows by setting a(x) equal to a constant for all x in ( 19 ). To show the second inequality we write the summation inside the logarithm in ( 19 ) as \sum\limits_{y\in\mathcal{Y}}P_{Y}(y)\bigg(\sum\limits_{x\in\mathcal{X}}P_{X|Y}(x|y)e^{-\rho a(x)}q(x,y)^{-s\rho}\bigg)\bigg(\sum\limits_{\bar{x}\in\mathcal{X}}e^{a(\bar{x})}q(\bar{x},y)^{s}\bigg)^{\rho}. (29) We now apply Hölder’s inequality: \bigg(\sum\limits_{i}a_{i}^{\frac{1}{1+\rho}}b_{i}^{\frac{1}{1+\rho}}\bigg)^{1+\rho}\leq\bigg(\sum\limits_{i}a_{i}\bigg)\bigg(\sum\limits_{i}b_{i}^{\frac{1}{\rho}}\bigg)^{\rho}. (30) Identifying a_{i}=P_{X|Y}(x|y)e^{-\rho a(x)}q(x,y)^{-s\rho} and b_{i}=(e^{a(x)}q(x,y)^{s})^{\rho} , we conclude that ( 29 ) is lower bounded by \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}. (31) The necessary and sufficient condition for equality in ( 30 ) is that a_{i}=cb_{i}^{\frac{1}{\rho}} for all i and some positive constant c . Applying this to ( 29 ) for all y in outer summation, we show that E^{\rm tt}_{q,\mathrm{r}}(R)=E_{\mathrm{r}}(R) holds for any decoding metric of the form given in ( 27 ). Similarly, rewriting the summation inside logarithm in ( 15 ) and applying Hölder’s inequality we can show that E^{\rm tt}_{q,\mathrm{r}}(R)=E_{\mathrm{r}}(R) holds if and only if the decoding metric is of the form given in ( 28 ). ∎ Corollary 1 shows that both type-by-type and standard ensembles recover E_{\mathrm{r}}(R) with a family of metrics given by ( 27 ) and ( 28 ), 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}, (32) 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}. (33) Similarly to Corollary 1 , we have the following. Corollary 2 . For every mismatched decoder employing decoding metric q(x,y) , we have that \displaystyle E_{q,\mathrm{ex}}(R) \displaystyle\leq E^{\rm tt}_{q,\mathrm{ex}}(R)\leq E^{\rm tt}_{\mathrm{ex}}(R), (34) \displaystyle E_{\mathrm{ex}}(R) \displaystyle\leq E^{\rm tt}_{\mathrm{ex}}(R), (35) and the equality E^{\rm tt}_{q,\mathrm{ex}}(R)=E^{\rm tt}_{\mathrm{ex}}(R) for all 0\leq R\leq\log|\mathcal{X}| holds for any q(x,y)=e^{b(x)+c(y)}P_{X|Y}(x|y)^{\tau} (36) with arbitrary b(x) , c(y) and \tau>0 , furthermore, the equality E_{q,\mathrm{ex}}(R)=E^{\rm tt}_{\mathrm{ex}}(R) holds for a given 0\leq R\leq\log|\mathcal{X}| for any q(x,y)=e^{c(y)}\left(e^{a(x)}\sqrt{P_{Y|X}(y|x)}\right)^{\tau} (37) where a(\cdot) is the optimal choice for given R in ( 33 ) and choice of c(y) and \tau>0 are arbitrary. Proof. The first inequality in ( 34 ) follows by setting a(x) equal to a constant for all x in ( 20 ). The second inequality in ( 34 ) follows from [ 8 , Lemma 4] and Proposition 21 . For a metric of the form given in ( 36 ), after some simplification we can rewrite ( 20 ) as E^{\rm tt}_{q,\mathrm{ex}}(R)=\sup_{\rho\geq 1,s^{\prime}\geq 0,r(\cdot)}\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_{X,Y}(x,y)\frac{e^{r(\bar{x})}}{e^{r(x)}}\left(\frac{P_{Y|X}(y|\bar{x})}{P_{Y|X}(y|x)}\right)^{s^{\prime}}\right)^{\frac{1}{\rho}}\right)^{\rho}, (38) where s^{\prime}=\tau s and r(x)=\rho a(x)+sb(x)+\tau s\log P_{X}(x) . As can be found in Section VI , we can rewrite this in similar form to ( 157 ) as E^{\rm tt}_{q,\mathrm{ex}}(R)=\min_{Q}\left[D(Q\|P_{X})+\sup_{\rho\geq 1}\left[E_{x}^{\rm cc}(Q,\rho)-\rho(H(Q)-R)\right]\right], (39) where \displaystyle E_{\rm{x}}^{\rm cc}(Q,\rho)=\sup_{s\geq 0,r(\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^{r(\bar{x})}}{e^{r(x)}}\left(\frac{P_{Y|X}(y|\bar{x})}{P_{Y|X}(y|x)}\right)^{s^{\prime}}\right)^{\frac{1}{\rho}}. (40) It has been shown in [ 12 ] that s^{\prime}=\frac{1}{2} optimizes ( 40 ) while the optimal choice of r(\cdot) is unclear in general. Replacing the latter optimal choice in ( 38 ) and further simplification results in ( 33 ). Replacing the metric q(x,y) in ( 16 ) with ( 37 ) and setting s=\frac{1}{\tau} results in ( 33 ). The inequality in ( 35 ) follows by setting r(x)=s^{\prime}\log P_{X}(x) in ( 38 ) which is an equivalent form of ( 33 ). ∎ 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 ( 36 ) and ( 37 ), 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 . II-C Special case: no side information Specializing the result of Theorem 16 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}. (41) For matched decoding, i.e., when q(x)=P_{X}(x) , the above exponent recovers the exponent of the optimal code as [ 13 ] 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}. (42) Theorem 2 recovers ( 42 ) 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 ( 42 ). II-D 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 , Ch. 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 ( 15 ) we find the achievable rate as \displaystyle H_{q}(X|Y)= \displaystyle\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}} (43) \displaystyle= \displaystyle H(X|Y)+\inf_{s\geq 0}D(P_{X|Y}\|Q^{(s)}_{X|Y}), (44) 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 ( 19 ) we find the achievable rate as \displaystyle H^{\rm tt}_{q}(X|Y)= \displaystyle\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)^{s}e^{a(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^{s}e^{a(\bar{x})}} (45) \displaystyle= \displaystyle H(X|Y)+\inf_{s\geq 0,a(\cdot)}D(P_{X|Y}\|Q^{(s,a(\cdot))}_{X|Y}), (46) where Q^{(s,a(\cdot))}_{X|Y}(x|y)=\frac{q(x,y)^{s}e^{a(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^{s}e^{a(\bar{x})}} . By inspecting the optimization problems in ( 43 ) and ( 45 ) we have that H_{q}(P_{X|Y}|P_{Y})\geq H^{\rm tt}_{q}(P_{X|Y}|P_{Y}). (47) The expressions of the above achievable rates bear a strong resemblance to their channel coding counterparts, the generalized mutual information [ 14 ] achieved by iid coding, and the LM rate [ 15 , 8 ] 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. Corollary 3 . The achievable rate H_{q}(X|Y) is related to the generalized mutual information [ 14 ] of corresponding channel W_{Y|X}(y|x)=\frac{P_{XY}(x,y)}{P_{X}(x)} with decoding metric \bar{q}(x,y)=q(x,y)P(x)^{-\frac{1}{s^{*}}} as H_{q}(X|Y)=H(X)-I^{\rm GMI}_{\bar{q}}(P_{X},W_{Y|X}) (48) where s^{*} is the optimizing parameter in ( 43 ) and I^{\rm GMI}_{\bar{q}}(P_{X},W_{Y|X})=\sup_{s>0}\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{\bar{q}(x,y)^{s}}{\sum\limits_{\bar{x}\in\mathcal{X}}P_{X}(\bar{x})\bar{q}(\bar{x},y)^{s}} (49) is the generalized mutual information [ 14 ] . Proof. Denoting the objective in ( 43 ) as H_{q,s}(X|Y) we have \displaystyle H_{q,s}(X|Y) \displaystyle=-\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}}-\sum\limits_{x\in\mathcal{X}}P_{X}(x)\log P_{X}(x)+H(X) (50) \displaystyle=-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^{s}}{P_{X}(x)\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^{s}}+H(X) (51) \displaystyle=-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{\bar{q}(x,y)^{s}}{\sum\limits_{\bar{x}\in\mathcal{X}}P_{X}(\bar{x})\bar{q}(\bar{x},y)^{s}}+H(X) (52) \displaystyle=-I_{\bar{q},s}(P_{X},W_{Y|X})+H(X) (53) where in ( 52 ) we have used the definition of decoding metric \bar{q}(x,y)=q(x,y)P(x)^{-\frac{1}{s}} . Taking the infimum of H_{q,s}(X|Y) over s and denoting the corresponding s by s^{*} we obtain ( 48 ). ∎ Corollary 4 . The achievable rate H^{\rm tt}_{q}(X|Y) is related to the LM rate [ 15 , 8 ] of corresponding channel as H^{\rm tt}_{q}(X|Y)=H(X)-I^{\rm LM}_{q}(P_{X},W_{Y|X}). (54) where I^{\rm LM}_{q}(P_{X},W_{Y|X})=\sup_{s>0,b(\cdot)}\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^{s}e^{b(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}P_{X}(\bar{x})q(\bar{x},y)^{s}e^{b(\bar{x})}} (55) is the LM rate [ 15 , 8 ] . Proof. Denoting the objective in ( 45 ) as H^{\rm tt}_{q,s,a}(X|Y) we have \displaystyle H^{\rm tt}_{q,s,a}(X|Y) \displaystyle=-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^{s}e^{a(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^{s}e^{a(\bar{x})}}-\sum\limits_{x\in\mathcal{X}}P_{X}(x)\log P_{X}(x)+H(X) (56) \displaystyle=-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^{s}e^{a(x)}}{P_{X}(x)\sum\limits_{\bar{x}\in\mathcal{X}}q(\bar{x},y)^{s}e^{a(\bar{x})}}+H(X) (57) \displaystyle=-\sum\limits_{x\in\mathcal{X},y\in\mathcal{Y}}P_{XY}(x,y)\log\frac{q(x,y)^{s}e^{b(x)}}{\sum\limits_{\bar{x}\in\mathcal{X}}P_{X}(\bar{x})q(\bar{x},y)^{s}e^{b(\bar{x})}}+H(X) (58) \displaystyle=-I_{q,s,b}(P_{X},W_{Y|X})+H(X), (59) where ( 58 ) follows from replacing e^{a(x)}=P_{X}(x)e^{b(x)} . Now taking the infimum of H^{\rm tt}_{q,s,a}(X|Y) over s and a(\cdot) we obtain ( 54 ). ∎ The achievability of the rate in ( 54 ), expressed in the primal domain, was observed in [ 16 , Corollary 1] . II-E Numerical example 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 0 5\cdot 10^{-2} 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 R E(R) E_{q}(R) matched E_{q}^{\rm tt}(R) matched E_{q}(R) mismatched E_{q}^{\rm tt}(R) mismatched 1.08 1.09 1.1 0.4 0.42 0.44 0.46 0.48 Fig. 1 : Error exponents for the source X and side information Y with joint distribution given in ( 60 ). The mismatched decoder uses the minimum Hamming distance metric. 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.49&0.005&0.005\\ 0.015&0.27&0.015\\ 0.05&0.05&0.1\end{bmatrix} (60) 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} (61) with \delta\in(0,\frac{1}{3}) . This is equivalent to a minimum Hamming distance decoding metric. Figure 1 illustrates the exponents for the standard and type-by-type ensembles with both matched and mismatched decoders. We observe that the type-by-type expurgated exponent is higher for both matched and mismatched decoding, even though the difference in the matched case is small for this example. Indeed, as discussed earlier, in the matched case, the random coding components of E_{q}(R) and E^{\rm tt}_{q}(R) coincide. The corresponding achievable rates are marked with dots in the figure. The conditional entropy H_{X|Y}=0.4654 nats is the limit for the matched case while in the mismatched case we respectively have H_{q}(P_{X|Y}|P_{Y})=0.5020 nats and H^{\rm tt}_{q}(P_{X|Y}|P_{Y})=0.4904 nats. III 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 sequence 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. III-A 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_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]. (62) Considering the standard random coding ensemble \mathsf{C} defined in Section I , 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}, (63) 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]\geq 1-\frac{1}{\eta}. (64) 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]. (65) Over the standard random coding ensemble \mathsf{C} , N_{0}(\mathsf{C}) is a random variable. Similarly to [ 5 , p. 151] , we first observe that the expected value of N_{0}(\mathsf{C}) can be lower bounded as \displaystyle\mathbb{E}\big[N_{0}(\mathsf{C})\big] \displaystyle=\mathbb{E}\bigg[\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}\mathds{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] (66) \displaystyle=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}\mathbb{E}\Big[\mathds{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] (67) \displaystyle=\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] (68) \displaystyle\geq|\mathcal{X}|^{n}\bigg(1-\frac{1}{\eta}\bigg) (69) where the last step follows from ( 64 ). Now we choose \eta=2 which yields 1-\frac{1}{\eta}=\frac{1}{2} in ( 69 ). 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}. (70) 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 ( 70 ), 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}. (71) 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 ( 62 ) 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] (72) 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 \displaystyle p_{e}(\boldsymbol{x},\bar{\mathcal{C}}) \displaystyle\leq\left(2\mathbb{E}\left[p_{e}(\boldsymbol{x},\bar{\mathsf{C}})^{\frac{1}{\rho}}\right]\right)^{\rho} (73) \displaystyle\leq\left(2\mathbb{E}\left[p_{e}(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\right)^{\rho}. (74) We denote by \mathcal{A}_{2} the set of above mentioned sequences satisfying ( 74 ) 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 ( 71 ). 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 ( 71 ). 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. Lemma 1 . There exists a code \mathcal{C}_{\rm ex} in the standard random coding ensemble such that for every source sequence \boldsymbol{x}\in\mathcal{X}^{n} and \rho\geq 0 p_{e}(\boldsymbol{x},\mathcal{C}_{ex\rm})\leq\Big(2\mathbb{E}\left[p_{e}(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right]\Big)^{\rho}, (75) where the expectation is over the standard random coding ensemble with \frac{M}{k} codewords with k=n\log_{2}|\mathcal{X}| . III-B 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_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right]. (76) 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}, (77) 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]\geq 1-\frac{1}{\eta}. (78) 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]. (79) 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 ( 78 ) 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}. (80) 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}. (81) 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 ( 81 ), 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 III-A 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 ( 81 ). 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} . Lemma 2 . There exists a code \boldsymbol{\mathcal{C}}_{\rm ex}=\{\mathcal{C}_{{\rm ex},1},\cdots,\mathcal{C}_{{\rm ex},|\mathcal{P}_{n}(\mathcal{X})|}\} in the type-by-type random coding ensemble such that for every i\in\{1,\cdots,|\mathcal{P}_{n}(\mathcal{X})|\} and for every source sequence \boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i}) and \rho\geq 0 p_{e}(\boldsymbol{x},\boldsymbol{\mathcal{C}}_{\rm ex})\leq\Big(2\mathbb{E}\left[p_{e}(\boldsymbol{x},\mathsf{C}_{i})^{\frac{1}{\rho}}\right]\Big)^{\rho}, (82) where the expectation is over the random coding ensemble for the corresponding type with \frac{M}{k_{i}|\mathcal{P}_{n}(\mathcal{X})|} codewords and k_{i}=\log_{2}|\mathcal{T}_{n}(\hat{P}_{i})|\leq n\log_{2}|\mathcal{X}| . IV 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 \displaystyle p_{e}(\boldsymbol{x},\mathcal{C}) \displaystyle=\mathbb{P}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right] (83) \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\mathds{1}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right] (84) \displaystyle\leq\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right] (85) \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\right]\mathds{1}\left[\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right] (86) \displaystyle\leq\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{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}, (87) where we use union bound in ( 85 ) and ( 87 ) holds for any s\geq 0 . 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 ( 87 ) as follows \displaystyle\mathbb{E}\left[p_{e}(\boldsymbol{x},\mathsf{C})^{\frac{1}{\rho}}\right] \displaystyle\leq\mathbb{E}\left[\left(\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{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] (88) \displaystyle\leq\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{X}^{n}}\mathbb{E}\left[\mathds{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}} (89) \displaystyle\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}} (90) where ( 89 ) 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, ( 90 ) follows from \mathbb{E}\left[\mathds{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 ( 90 ) in ( 75 ) 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 \displaystyle p_{e}(\mathcal{C}_{\rm ex}) \displaystyle=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}}(\boldsymbol{x})p_{e}(\boldsymbol{x},\mathcal{C}_{\rm ex}) (91) \displaystyle\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} (92) \displaystyle\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} (93) Equation ( 93 ) 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 \displaystyle p_{e}(\mathcal{C}_{\rm ex}) \displaystyle\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} (94) \displaystyle=e^{-n(\rho(R-\delta_{n})-E_{\rm{x}}(\rho,s))} (95) 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}, (96) 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). (97) To show that the same code of Lemma 1 achieves E_{q,\mathrm{r}}(R) we use ( 75 ) of Lemma 1 with \rho=1 , and obtain \displaystyle p_{e}(\boldsymbol{x},\mathcal{C}_{\rm ex})\leq 2\mathbb{E}\left[P_{e}(\boldsymbol{x},\mathsf{C})\right]. (98) Averaging over all source sequences we obtain \displaystyle p_{e}(\mathcal{C}_{\rm ex}) \displaystyle=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}}(\boldsymbol{x})p_{e}(\boldsymbol{x},\mathcal{C}_{\rm ex}) (99) \displaystyle\leq 2\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}}(\boldsymbol{x})\mathbb{E}\left[P_{e}(\boldsymbol{x},\mathsf{C})\right] (100) \displaystyle=2\mathbb{E}\left[\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}}(\boldsymbol{x})P_{e}(\boldsymbol{x},\mathsf{C})\right] (101) \displaystyle=2\mathbb{E}\left[p_{e}(\mathsf{C})\right], (102) 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 \displaystyle p_{e}(\boldsymbol{y},\mathcal{C}) \displaystyle=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathds{1}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right\}\right] (103) \displaystyle\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^{\rho} (104) \displaystyle=\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\right]\mathds{1}\left[\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^{\rho} (105) \displaystyle\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathds{1}\left[\phi(\bar{\boldsymbol{x}})=\phi(\boldsymbol{x})\right]\right)^{\rho}, (106) where ( 104 ) follows from using the inequality \mathds{1}\left[\bigcup\limits_{i}A_{i}\right]\leq\left(\sum\limits_{i}\mathds{1}\left[A_{i}\right]\right)^{\rho} for any set of events \{A_{i}\} and \rho\in[0,1] and ( 106 ) holds for any s\geq 0 . 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 ( 106 ) as follows \displaystyle\mathbb{E}\left[p_{e}(\boldsymbol{y},\mathsf{C})\right] \displaystyle\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\mathbb{E}\left[\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathds{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right)^{\rho}\right] (107) \displaystyle\leq\sum\limits_{\boldsymbol{x}\in\mathcal{X}^{n}}P_{\boldsymbol{X}|\boldsymbol{Y}}(\boldsymbol{x}|\boldsymbol{y})\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{X}^{n}\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{E}\left[\mathds{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\right)^{\rho} (108) \displaystyle\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}, (109) where ( 108 ) follows from Jensen’s inequality and the concavity of x^{\rho} for \rho\in\left[0,1\right] and ( 109 ) follows from \mathbb{E}\left[\mathds{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 \displaystyle\mathbb{E}\left[p_{e}(\mathsf{C})\right] \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}}(\boldsymbol{y})\mathbb{E}\left[p_{e}(\boldsymbol{y},\mathsf{C})\right] (110) \displaystyle\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} (111) where ( 111 ) holds for any \rho\in\left[0,1\right] and s\geq 0 . Introducing ( 111 ) in ( 102 ) and particularizing it to the case of memoryless sources and metrics we obtain \displaystyle p_{e}(\mathcal{C}_{\rm ex}) \displaystyle\leq 2\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} (112) \displaystyle=e^{-n(\rho(R-\delta_{n})-E_{\rm{s}}(\rho,s)-\delta^{\prime}_{n})} (113) where \delta_{n}=\frac{\log k}{n}\to 0 and \delta^{\prime}_{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} (114) Hence, we show the achievability of the exponent E_{q,\mathrm{r}}(R) by optimizing over \rho,s as in ( 15 ). V Proof of Theorem 18 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 18 . 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 \displaystyle P_{e}(\boldsymbol{x},\mathcal{C}_{i}) \displaystyle=\mathbb{P}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y})\cap\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right\}\right] (115) \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\mathds{1}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{Y})\geq q(\boldsymbol{x},\boldsymbol{Y})\cap\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right\}\right] (116) \displaystyle\leq\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right] (117) \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}|\boldsymbol{X}}(\boldsymbol{y}|\boldsymbol{x})\sum\limits_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\right]\mathds{1}\left[\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right] (118) \displaystyle\leq\sum\limits_{\begin{subarray}{c}\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}\end{subarray}}\mathds{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} (119) where we use union bound in ( 117 ) and ( 119 ) holds for any s\geq 0 . 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 ( 119 ) as follows \displaystyle\mathbb{E}\left[P_{e}(\boldsymbol{x},\mathsf{C}_{i})^{\frac{1}{\rho}}\right] \displaystyle\leq\mathbb{E}\left[\left(\sum\limits_{\begin{subarray}{c}\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}\end{subarray}}\mathds{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] (120) \displaystyle\leq\sum\limits_{\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})}\mathbb{E}\left[\mathds{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}} (121) \displaystyle\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}} (122) where ( 121 ) 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, ( 122 ) follows from \mathbb{E}\left[\mathds{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 \hat{P}_{i} . Now substituting ( 122 ) in ( 82 ) 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 \displaystyle 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} (123) Notice that using ( 123 ) 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} require maximization over the type. In order to find a simpler bound we can weaken the bound in ( 123 ) 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 \displaystyle p_{e}(\boldsymbol{\mathcal{C}}_{\rm ex}) \displaystyle=\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}) (124) \displaystyle\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}. (125) Equation ( 125 ) 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 \displaystyle p_{e}(\boldsymbol{\mathcal{C}}_{\rm ex}) \displaystyle\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} (126) \displaystyle=e^{-n(\rho(R-\delta_{n})-E^{\rm tt}_{\rm{x}}(\rho,s,a))} (127) where \delta_{n}=\frac{\log 2k|\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}. (128) 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)). (129) To show that the same code of Lemma 18 achieves E^{\rm tt}_{q,\mathrm{r}}(R) we use ( 82 ) of Lemma 2 with \rho=1 , and obtain that for every source sequence \boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i}) \displaystyle p_{e}(\boldsymbol{x},\boldsymbol{\mathcal{C}}_{\rm ex})\leq 2\mathbb{E}\left[P_{e}(\boldsymbol{x},\mathsf{C}_{i})\right]. (130) Averaging over all source sequences similar to the proof of Theorem 16 we obtain \displaystyle p_{e}(\boldsymbol{\mathcal{C}}_{\rm ex})\leq 2\mathbb{E}\left[p_{e}(\boldsymbol{\mathsf{C}})\right], (131) 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 IV . 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 \displaystyle p_{e}(\boldsymbol{y},\boldsymbol{\mathcal{C}}) \displaystyle=\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})\mathds{1}\left[\bigcup_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left\{q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right\}\right] (132) \displaystyle\leq\sum\limits_{i=1}^{|\mathcal{P}_{n}(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i})}\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\mathds{1}\left[q(\bar{\boldsymbol{x}},\boldsymbol{y})\geq q(\boldsymbol{x},\boldsymbol{y})\cap\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right]\right)^{\rho} (133) \displaystyle\leq\sum\limits_{i=1}^{|\mathcal{P}_{n}(\mathcal{X})|}\sum\limits_{\boldsymbol{x}\in\mathcal{T}_{n}(\hat{P}_{i})}\left(\sum_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathds{1}\left[\phi_{i}(\bar{\boldsymbol{x}})=\phi_{i}(\boldsymbol{x})\right]\right)^{\rho}, (134) where ( 133 ) follows from using the inequality \mathds{1}\left[\bigcup\limits_{i}A_{i}\right]\leq\left(\sum\limits_{i}\mathds{1}\left[A_{i}\right]\right)^{\rho} for any set of events \{A_{i}\} and \rho\in[0,1] and ( 134 ) holds for any s\geq 0 . 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 ( 134 ) as follows \displaystyle\mathbb{E}\left[p_{e}(\boldsymbol{y},\boldsymbol{\mathsf{C}})\right] \displaystyle\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_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathds{1}\left[\Phi_{i}(\bar{\boldsymbol{x}})=\Phi_{i}(\boldsymbol{x})\right]\right)^{\rho}\right] (135) \displaystyle\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_{\begin{subarray}{c}\bar{\boldsymbol{x}}\in\mathcal{T}_{n}(\hat{P}_{i})\\ \bar{\boldsymbol{x}}\neq\boldsymbol{x}\end{subarray}}\left(\frac{q(\bar{\boldsymbol{x}},\boldsymbol{y})}{q(\boldsymbol{x},\boldsymbol{y})}\right)^{s}\mathbb{E}\left[\mathds{1}\left[\Phi_{i}(\bar{\boldsymbol{x}})=\Phi_{i}(\boldsymbol{x})\right]\right]\right)^{\rho} (136) \displaystyle\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}, (137) \displaystyle\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}, (138) where ( 136 ) follows from Jensen’s inequality and the concavity of x^{\rho} for \rho\in\left[0,1\right] and ( 137 ) follows from \mathbb{E}\left[\mathds{1}\left[\Phi(\bar{\boldsymbol{x}})=\Phi(\boldsymbol{x})\right]\right]\leq\frac{k}{M} and ( 138 ) 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 \displaystyle\mathbb{E}\left[p_{e}(\boldsymbol{\mathsf{C}})\right] \displaystyle=\sum\limits_{\boldsymbol{y}\in\mathcal{Y}^{n}}P_{\boldsymbol{Y}}(\boldsymbol{y})\mathbb{E}\left[p_{e}(\boldsymbol{y},\boldsymbol{\mathsf{C}})\right] (139) \displaystyle\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} (140) where ( 140 ) holds for any \rho\in\left[0,1\right] and s\geq 0 . Introducing ( 140 ) in ( 131 ) and particularizing it to the case of memoryless sources, metrics and cost functions we obtain \displaystyle p_{e}(\boldsymbol{\mathcal{C}}_{\rm ex}) \displaystyle\leq 2\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} (141) \displaystyle=e^{-n(\rho(R-\delta_{n})-E^{\rm tt}_{\rm{s}}(\rho,s,a)-\delta^{\prime}_{n})} (142) where \delta_{n}=\frac{\log k|\mathcal{P}_{n}(\mathcal{X})|}{n}\to 0 and \delta^{\prime}_{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} (143) Hence, we show the achievability of the exponent E^{\rm tt}_{q,\mathrm{r}}(R) by optimizing over \rho,s,a(\cdot) as in ( 19 ). VI Proof of Proposition 21 : Primal-dual Equivalence We start by showing the equivalence of ( 11 ) to ( 20 ). We rewrite ( 11 ) 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], (144) where E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{\begin{subarray}{c}P_{\hat{X}\tilde{X}\tilde{Y}}\in\mathcal{T}(Q)\\ H(\hat{X}|\tilde{X})\geq R\end{subarray}}\left[D(P_{\tilde{Y}|\tilde{X}}\|P_{Y|X}|P_{\tilde{X}})+I(\tilde{X}\tilde{Y};\hat{X})+R-H(Q)\right] (145) and \mathcal{T}(Q)=\left\{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\}, (146) 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}}). (147) to split the minimization in ( 11 ). Defining \mathcal{S}(Q)=\left\{\tilde{P}_{\hat{X}\tilde{X}}\in\mathcal{P}(\mathcal{X}\times\mathcal{X}):\tilde{P}_{\hat{X}}=\tilde{P}_{\tilde{X}}=Q\right\}, (148) \mathcal{T}(\tilde{P}_{\hat{X}\tilde{X}})=\left\{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\}, (149) we can rewrite ( 145 ) as E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X})=\min_{\begin{subarray}{c}\tilde{P}_{\hat{X}\tilde{X}}\in\mathcal{S}(Q)\\ H(\hat{X}|\tilde{X})\geq R\end{subarray}}\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] (150) where we use [ 8 , Eq. (32)] 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}). (151) 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}). (152) The dual of this optimization problem has been found in [ 12 , Appendix B] . Using very similar arguments we find the following equivalent forms of ( 150 ) as \displaystyle E_{q,\mathrm{ex}}^{\mathrm{cc}}(H(Q)-R,Q,P_{Y|X}) \displaystyle=\sup_{s\geq 0}\min_{\begin{subarray}{c}P_{X\bar{X}}:P_{X}=Q,P_{\bar{X}}=Q\\ H(\bar{X}|X)\geq R\end{subarray}}\mathbb{E}_{P}\left[d_{s}(X,\bar{X})\right]+R-H(\bar{X}|X), (153) \displaystyle=\sup_{\rho\geq 1}E_{x}^{\mathrm{cc}}(Q,\rho)-\rho(H(Q)-R), (154) 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}, (155) and \displaystyle 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}}. (156) Using ( 154 ) in ( 144 ) we obtain \displaystyle 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], (157) Defining e^{a(x)}=Q_{X}(x)^{\rho}e^{b(x)} , we can rewrite ( 156 ) as \displaystyle E_{\rm{x}}^{\mathrm{cc}}(Q_{X},\rho) \displaystyle=\sup_{s\geq 0,a(\cdot)}-\rho\sum\limits_{x\in\mathcal{X}}Q_{X}(x)\log\sum\limits_{\bar{x}\in\mathcal{X}}Q_{X}(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}} (158) \displaystyle=\rho H(Q_{X})+\sup_{s\geq 0,a(\cdot)}-\rho\sum\limits_{x\in\mathcal{X}}Q_{X}(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}} (159) Introducing ( 159 ) in ( 157 ), noting that the objective in ( 157 ) is concave in Q and using Fan’s minimax theorem interchanging the minimum and supremum we obtain \displaystyle E^{\mathrm{ck}}_{\rm{ex}}(R)=\sup_{\rho\geq 1}\left[\rho R+\sup_{s\geq 0,a(\cdot)}\min_{Q_{X}}L\right], (160) where L=\sum\limits_{x\in\mathcal{X}}Q_{X}(x)\log\frac{Q_{X}(x)}{P_{X}(x)}-\rho\sum\limits_{x\in\mathcal{X}}Q_{X}(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}} (161) Setting \frac{\partial L}{\partial Q_{X}}=0 we find the minimizing distribution as the following mismatched tilted distribution Q_{X}(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} (162) 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}. (163) From ( 162 ) we have \frac{Q_{X}(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 ( 161 ) we obtain \displaystyle\min_{Q_{X}}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} (164) Plugging ( 164 ) into ( 160 ) we obtain the dual form of the type-by-type expurgated exponent in ( 20 ). To show the equivalence of ( 10 ) to ( 19 ). We rewrite ( 10 ) 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], (165) 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], (166) where we use P_{\tilde{X}}=Q and the identity ( 147 ) to split the minimization in ( 10 ). Defining \mathcal{S}(Q)=\left\{P_{\tilde{X}\tilde{Y}}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y}):P_{\tilde{X}}=Q\right\}, (167) \mathcal{T}(P_{\tilde{X}\tilde{Y}},Q)=\left\{\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\}, (168) we can rewrite ( 166 ) 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]. (169) The dual form of the cost constrained random coding error exponent in ( 169 ) is derived in [ 17 ] , using which we rewrite it as \displaystyle 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), (170) where \displaystyle 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}. (171) Defining e^{a(x)}=Q_{X}(x)e^{b(x)} , we can rewrite ( 156 ) as \displaystyle E_{0}^{\mathrm{cc}}(Q_{X},\rho) \displaystyle=\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} (172) \displaystyle=\rho H(Q_{X})+\sup_{s\geq 0,a(\cdot)}-\sum\limits_{x\in\mathcal{X}}Q_{X}(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} (173) Introducing ( 173 ) in ( 171 ), noting that the objective in ( 171 ) is concave in Q and using Fan’s minimax theorem interchanging the minimum and supremum we obtain \displaystyle E_{\rm{ex}}(R)=\sup_{\rho\geq 1}\left[\rho R+\sup_{s\geq 0,a(\cdot)}\min_{Q_{X}}L\right], (174) where L=\sum\limits_{x\in\mathcal{X}}Q_{X}(x)\log\frac{Q_{X}(x)}{P_{X}(x)}-\sum\limits_{x\in\mathcal{X}}Q_{X}(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}. (175) Setting \frac{\partial L}{\partial Q_{X}}=0 we find the minimizing distribution as the following mismatched tilted distribution Q_{X}(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} (176) 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}. (177) From ( 176 ) we have \frac{Q_{X}(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 ( 175 ) we obtain \displaystyle\min_{Q_{X}}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} (178) Plugging ( 178 ) into ( 174 ) we obtain the dual form of the type-by-type random coding exponent in ( 19 ).