Exact Random Coding Exponents and Universal Decoders for the Asymmetric Broadcast Channel
Ran Averbuch Neri Merhav

empty


Exact Random Coding Exponents and Universal 

Decoders for the Asymmetric Broadcast Channel

    
 Ran Averbuch and Neri Merhav

    December 30, 2023
============================================================================================



The Andrew & Erna Viterbi Faculty of Electrical Engineering 

Technion - Israel Institute of Technology 

Technion City, Haifa 3200004, ISRAEL 

{rans@campus, merhav@ee}.technion.ac.il







This work contains two main contributions concerning the
asymmetric broadcast channel. The first is an analysis of 
the exact random coding error exponents
for both users, and the second is the derivation
of universal decoders for both users. These universal decoders are
certain variants of the maximum mutual information (MMI)
universal decoder, which achieve the corresponding random coding
exponents of optimal decoding.
In addition, we introduce some lower bounds, 
which involve optimization over very few parameters, 
unlike the original, exact exponents, which involve minimizations over
auxiliary probability distributions.
Numerical results for the binary symmetric broadcast channel show improvements over 
previously derived error exponents for the same model. 


Index Terms:  Error exponent, asymmetric broadcast channel, universal decoding, MMI.




§ INTRODUCTION


One of the most elementary system configuation models in multi-user information theory 
is the broadcast channel (BC). It has been introduced in the 
early seventies of the twentieth century by Cover <cit.>, 
and since then, a vast amount of papers and books, studying different topics of 
the broadcast problem, have been published. 
Generally speaking, the BC
is a communication model, 
where a single transmitter wishes 
to communicate different messages to two or more receivers. 
The various messages may be private (i.e., aimed to one receiver only) 
or common (i.e., aimed to two or more receivers). 

Although the characterization of the capacity region of the general BC is still 
an open problem, some special cases have been solved, most notably, the
degraded BC (DBC), first presented in <cit.>.
The capacity region of the DBC, conjectured by Cover, was first proved 
to be achievable by Bergmans <cit.>, 
and the converse was established by Bergmans 
<cit.> and Gallager <cit.>.
Another special case, which is somewhat more general than the DBC and which was first 
introduced and solved by Körner and Marton <cit.>,
is the broadcast channel with degraded message sets, also known as the asymmetric broadcast channel (ABC). The direct part of their coding theorem relys on  
Bergmans' scheme, which suggested the use of an hierarchical random code: 
First generate “cloud centers", 
which designate messages 
intended to both the receiver with
the relatively high channel quality, 
henceforth referred to as the strong user, and the receiver with
the relatively low channel quality, henceforth referred to as the weak user.
Then, in the second step, “around" each cloud center,
generate a codeword for each message 
that is intended to the strong user
only. The transmitter sends a codeword pertaining to one of the clouds. 
The strong decoder 
fully decodes both the common message and his private message,
whereas the weak decoder decodes the common message only. 
Other channels in which one receiver is superior to another 
and channels with nested information were studied by 
Csiszár and Körner <cit.> and by El Gamal <cit.>, 
to name a few. 

Multi–user information theory is, first and foremost, driven by the quest to
characterize capacity regions, i.e., the region of all sets of rates that
allow reliable communication (a.k.a. achievable rates).
A somewhat sharper performance metric concerns the exponential decay rate
(the error exponent) of the
probability of error
for each user, as a function of the coding rates 
within the interior of the capacity region.
On top of that, an interesting question concerns the trade–off between
the error exponent of the strong user and the one of the weak user, or
equivalently, the achievable region in the plane of error exponents for a
given set of coding rates. 

While the capacity regions of the DBC and the ABC have been known for many years, 
only little has been known about their reliability functions.
Earlier works on error exponents for the general DBC and ABC 
include those of Gallager <cit.> and Körner and Sgarro <cit.>, respectively. 
In both works, the coding scheme of <cit.> was adopted, 
but the decoder was sub–optimal. 
More recently, Kaspi and Merhav <cit.> have derived
some tighter lower bounds to the reliability functions of both users
by analyzing random coding error exponents of their optimal decoders.
While their derivation
was exponentially tight at most of the steps, 
there were still some steps in <cit.> where exponential
tightness might have been compromised. 
Moreover, Kaspi and Merhav have analyzed ensembles of i.i.d.codes, which are not as good as ensembles of fixed composition codes <cit.>. These two points give rise to the thought that there 
is room for improvement upon the results of <cit.>,
and indeed, such an improvement is one of the contributions of this work. In
fact, the exponential error bounds, derived in this paper, both for the strong
user and the weak one, are tight in the sense that they provide the exact
random coding exponents for the ensemble of fixed composition codes.
Moreover, the resulting expressions are much simpler and easier to calculate
than those of the best exponential bounds of 
Kaspi and Merhav (see, in
particular, the second part of <cit.>). 

Interestingly, one of the ingredients 
that contributes significantly to this
simplification in the error exponent expressions, is the derivation of
universal decoders for both users, and this simplification is achieved thanks to
a simple sandwich argument, asserting that a lower bound to 
the error exponent of the universal
decoder cannot be larger than an upper bound to the error exponent of the
optimal decoder, but on the other hand, 
the latter turns out to be mathematically smaller
than or equal to the former, and so, 
by contrasting the two exponential error bounds, which must therefore be 
equivalent, the expressions are considerably simplified. 
In other words, beyond this simplification of the error
exponent bounds, there is an additional bonus, 
which is in obtaining universal decoders
for both users. These decoders achieve the same random coding error exponents 
as the corresponding
optimal decoders of the two users. Both universal decoders are certain variants of the
maximum mutual information (MMI) decoder <cit.>, but they are
different from the earlier proposed MMI-like universal decoders for the ABC, due to
Körner and Sgarro <cit.>. For one thing, our
universal decoder for the weak user depends explicitly on the entire code, 
unlike the one
in <cit.>, which depends on the cloud centers only. 

Since we rely heavily on the method of types, our exponential error bounds
have the flavor of those of Csiszár and Körner <cit.>. While
exponentially tight, their shortcoming is that they are not easy to calculate
since they involve minimizations over auxiliary channels, and these might be
computationally painful especially for large alphabets. To alleviate
this difficulty, we also propose Gallager–style bounds <cit.>, which require
optimizations over very 
few (one or two) parameters, but the caveat is that
exponential tightness might be sacrificed.
Moreover, the Gallager–style bounds lend themselves to better intuitive
understanding on the behavior of 
the error exponents for both of the users. 
Specifically, we derive a phase diagram for the weak user, 
which fully describes the functional behavior of the bound 
in different regions of the plane of rates. 
We also demonstrate our results numerically 
for an example of the binary symmetric BC, and
compare our results to those in earlier works, showing explicitly the improvement. 

The remaining part of the paper is organized as follows. 
In Section 2, we establish notation conventions, formalize the model and the problem, and finally, review 
some preliminaries. 
In Section 3, we summarize the main theoretical results of this paper, and give some numerical results for the binary symmetric BC. 
Section 4 provides the proofs concerning the strong user in the ABC (the exact random coding error exponent and the universal decoder), and 
Section 5 contains a similar treatment for the weak user.
In Section 6, we derive lower bounds on the exact random coding error exponents, 
and in Section 7 we study them.



§ NOTATION CONVENTIONS AND PROBLEM FORMULATION




 §.§ Notation Conventions

Throughout the paper, random variables will be denoted by capital letters, specific values they 
may take will be denoted by the corresponding lower case letters, and their alphabets will be 
denoted by calligraphic letters. Random vectors and their realizations will be denoted, 
respectively, by capital letters and the corresponding lower case letters, both in the bold face 
font. Their alphabets will be superscripted by their dimensions. 
For example, the random vector 𝐗 = (X_1, … , X_n), (n - positive integer) 
may take a specific vector value = (x_1, … , x_n) in 𝒳^n, 
the n-th order Cartesian power of 𝒳, which is the alphabet of each component of this vector. Sources and channels will be subscripted by the names of the relevant random 
variables/vectors and their conditionings, whenever applicable, 
following the standard notation conventions, e.g., Q_X, Q_Y|X, and so on. 
When there is no room for ambiguity, these subscripts will be omitted. For a generic joint 
distribution Q_XY = {Q_XY(x,y), x ∈𝒳, y ∈𝒴}, which will often 
be abbreviated by Q, information measures will be denoted in the conventional manner, but
with a subscript Q, that is, H_Q(X) 
is the marginal entropy of X, H_Q(X|Y) is the conditional entropy of X given Y, 
I_Q(X;Y) = H_Q(X) - H_Q(X|Y) is the mutual information between X and Y, 
and so on. The weighted divergence between 
two conditional distributions (channels), say, Q_Z|X and W = {W(z|x), 
x ∈𝒳, z ∈𝒵}, with weighting Q_X is defined as

    D(Q_Z|X || W | Q_X) = ∑_x ∈𝒳 Q_X(x) 
    ∑_z ∈𝒵 Q_Z|X(z|x) logQ_Z|X(z|x)/W(z|x),

where logarithms, here and throughout the sequel, are taken to the natural base.
The probability of an event ℰ will be denoted by 
Pr{ℰ}, and the expectation operator with respect to (w.r.t.) a 
probability distribution P will be denoted by 𝔼{·}. 
For two positive sequences a_n and b_n, the notation a_n≐ b_n will stand 
for equality in the exponential scale, that is, lim_n →∞1/nloga_n/b_n = 0. The indicator function of an event ℰ 
will be denoted by ℐ{ℰ}. 
The notation [x]_+ will stand for max{0, x}. 

The empirical distribution of a sequence ∈𝒳^n, which will 
be denoted by P̂_, is the vector of relative frequencies, P̂_(x), 
of each symbol x ∈𝒳 in . 
The type class of ∈𝒳^n, denoted 𝒯(), 
is the set of all vectors ' with P̂_' = P̂_. 
When we wish to emphasize the dependence of the type class on the empirical 
distribution P̂, we will denote it by 𝒯(P̂). Information measures 
associated with empirical distributions will be denoted with 'hats' and will be subscripted 
by the sequences from which they are induced. For example, the entropy associated 
with P̂_, which is the empirical entropy of , will be denoted 
by Ĥ_(X). Similar conventions will apply to the joint empirical distribution, 
the joint type class, the conditional empirical distributions and the conditional type classes 
associated with pairs (and multiples) of sequences of length n. 
Accordingly, P̂_ would be the joint empirical distribution 
of (, ) = {(x_i, y_i)}_i=1^n, 𝒯(, 
) or 𝒯(P̂_) will denote the joint type 
class of (, ), 𝒯(| ) will stand for the 
conditional type class of  given , Ĥ_(X,Y) 
will designate the empirical joint entropy of  and 
, Ĥ_(X|Y) will be the empirical conditional entropy, 
Î_(X;Y) will denote the empirical mutual information, and so on. 
When we wish to emphasize the dependence of 𝒯(| ) upon 
 and the relevant empirical conditional distribution, Q_X|Y = 
P̂_|, we denote it by 𝒯( Q_X|Y | ). 
Similar conventions will apply to triples of sequences, say, 
{(, , )}, etc. Likewise, when we wish to emphasize the 
dependence of empirical information measures upon a given empirical distribution given by Q, 
we denote them using the subscript Q, as described above.




 §.§ Problem Formulation


We consider a memoryless ABC 
with a finite input alphabet 𝒳 and finite output alphabets 𝒴 and 𝒵. 
Let W_1 = {W_1(y|x), x ∈𝒳, y ∈𝒴} 
and W_2 = {W_2(z|x), x ∈𝒳, z ∈𝒵}
denote the single–letter input–output transition probability matrices,
associated with the strong user and the weak user, respectively.
When these channels are fed by an input vector ∈𝒳^n, 
they produce
the corresponding output vectors ∈𝒴^n and ∈𝒵^n, according to

    W_1(|)     =  ∏_t=1^n  W_1(y_t|x_t), 
    
       W_2(|)     =  ∏_t=1^n  W_2(z_t|x_t).

We are interested in sending 
one out of M_yM_z messages to the strong user, 
that observes , and 
one out of M_z messages to the weak user, 
that observes . 
Specifically, 
consider the following mechanism of random selection of an hierarchical code
for the ABC.
Let 𝒰 be a finite alphabet, 
let P_U be a given probability distribution on 𝒰, 
and let P_X|U be a given matrix of conditional probabilities of X given U. 
We first select, independently at random, M_z = e^n R_z n-vectors 
(“cloud centers”), 
_0, _1, …, _M_z-1, 
all under the uniform distribution over the type class 𝒯(P_U). 
Next, for each i = 0,1, …, M_z - 1, we select conditionally 
independently (given _i), M_y = e^n R_y codewords, 
_i,0, _i,1, …, _i,(M_y-1),
under the uniform distribution across the conditional type 
class 𝒯(P_X|U|_i). We denote the sub-code
𝒞_i = {_i,0, _i,1, …, _i,(M_y-1)}.
Once selected, the entire codebook 𝒞=∪_i=0^M_z-1_i, 
together with the collection of all cloud centers, {_0,
_1, …, _M_z-1}, are
revealed to the encoder and to both decoders. 



The optimal decoder for the strong user is given by

    [î(), ĵ()] = *arg max_0 ≤ i ≤ M_z-1, 0 ≤ j ≤ M_y-1 W_1(|_i,j) ,

while the optimal decoder for the weak user (the bin index decoder) is given by

    ĩ() = *arg max_0 ≤ i ≤ M_z-1 W_2(|𝒞_i)  ,

where

    W_2(|𝒞_i)  △=1/M_y∑_∈𝒞_i 
    W_2(|) = 1/M_y∑_j=0^M_y-1 W_2(|_i,j).


Let 𝐘∈𝒴^n and 𝐙∈𝒵^n be the channel outputs resulting from the transmission of 𝐗_i,j.
Define the average error probabilities of decoders (<ref>) and
(<ref>) as

    P̅_(R_y, R_z)    =  1/M_y M_z∑_i=0^M_z-1∑_j=0^M_y-1Pr{ [î(𝐘), ĵ(𝐘)] ≠ (i,j) | 𝐗_i,j } ,

and

    P̅_ (R_y, R_z)
       =  1/M_y M_z∑_i=0^M_z-1∑_j=0^M_y-1Pr{ĩ(𝐙) ≠ i  | 𝐗_i,j } ,

where in both definitions, Pr{·} 
designates probabilities associated with the 
randomness of the codebook, as well as that of the channel outputs given its input.
The corresponding random coding error exponents are defined as

    E_(R_y, R_z) = lim_n →∞[ - lnP̅_ (R_y, R_z)/n],
 
and

    E_(R_y, R_z) = lim_n →∞[ - lnP̅_ (R_y, R_z)/n],

provided that the limits exist. Our main objective is to obtain 
single–letter expressions for 
E_(R_y, R_z) and E_(R_y,
R_z).
As for the universal decoders, consider first the weak user. 
We wish to find a function F(,_i,𝒞_i), 
that is independent of the (unknown) parameters of the channel W_2,
such that the following
universal decoder for the weak user

    ĩ_() = *arg max_0 ≤ i ≤ M_z-1 F(,_i,𝒞_i)

achieves an average error probability whose exponent is E_(R_y, R_z).
By the same token, we wish to find a universal decoder for the strong
user, of the form 

    [î_(), ĵ_()] 
    = *arg max_0 ≤ i ≤ M_z-1, 0 ≤ j ≤ M_y-1 G(,_i,_i,j) ,

where the function G is independent of W_1, yet the decoder
[î_(), ĵ_()] achieves E_(R_y, R_z).





§ MAIN RESULTS




 §.§ Exact Random Coding Error Exponents

Let Q_UXY and Q_UXZ denote two generic joint probability distributions of 
the random vectors (U,X,Y) and (U,X,Z), 
whose (UX)-marginals are both
identical to P_UX. 
Define

    E_y(Q_ UXY, R_y, R_z) = 
    min{[  I_Q(U;Y)  +     [ I_Q(X;Y|U) - R_y]_+ - R_z]_+, 
       [ I_Q(X;Y|U) - R_y]_+},

and

    E_z(Q_ UXZ, R_y, R_z) = 
     [  I_Q(U;Z)  +  [ I_Q(X;Z|U) - R_y]_+ - R_z]_+.

Our first main result is the following. 

Theorem 1. Under the assumptions of Section 2, the limits
(<ref>) and (<ref>) exist and are given by the following single–letter expressions: 

    E_(R_y, R_z)    =
    min_ Q_Y|UX{  D(Q_Y|UX W_Y|X |  P_UX   )  +  E_y(Q_ UXY, R_y, R_z)   },  
    
    E_(R_y, R_z)    =
    min_ Q_Z|UX{  D(Q_Z|UX W_Z|X |  P_UX   )  +  E_z(Q_ UXZ, R_y, R_z)   }.

We prove the result concerning the strong user in Section 4 and the result concerning the weak user in Sections 5.
Notice that both error exponents depend on both coding rates, 
in contrast to the error exponents given 
in the previous works <cit.> and <cit.>. 

Several remarks are now in order. 

∙ An immediate byproduct of Theorem 1 is finding the set of rate pairs (R_y, R_z) for which both E_(R_y, R_z) >0 and E_(R_y, R_z) >0. It is not difficult to show that this set is given by:

    ℛ = {(R_y, R_z) |  R_y< I(X;Y|U), R_y+R_z< I(X;Y), R_z< I(U;Z)  },

evaluated with the distribution P_UX× W_Y|X× W_Z|X. The convex hull of the closure of the union over all code distributions { P_UX} gives the capacity region. We may also consider an individual attainable region for each user, i.e., the set of rate pairs for which the probability of error vanishes for one of the users, but without taking into account the other user. Later on, individual attainable regions will become relevant when we consider the phase diagrams. It is not difficult to show that the attainable region for the weak user, to be denoted by ℛ_, is given by ℛ_ = {(R_y, R_z) |  R_y+R_z< I(X;Z)  }∪{(R_y, R_z) | R_z< I(U;Z)  },
evaluated with the distribution P_UX× W_Z|X, while the attainable region for the strong user, to be denoted by ℛ_, is given by
ℛ_ = {(R_y, R_z) |  R_y+R_z< I(X;Y)  }∩{(R_y, R_z) | R_y< I(X;Y|U)  },
evaluated with the distribution P_UX× W_Y|X. Notice that the attainable region of the weak user is not bounded, i.e., reliable bin index decoding may still be guaranteed for any satellites rate R_y, as long as R_z< I(U;Z).


∙ The computation of the error exponents involves minimizations over auxiliary channels Q_Y|UX and Q_Z|UX. For large input and output alphabets, we are motivated to look for alternative expressions for the error exponents, whose optimization does not depend on the alphabet sizes, even at the expense of some loss in the exponential tightness. We will discuss such an alternative form in the sequel. 


∙ Both error exponents depend on the input distribution. While in the single-user regime, we may maximize the final expression over the input distribution in order to maximize the error exponent, this is no longer the case for the ABC. Even in the simplest case of a binary symmetric BC, we see that the best code for the strong user is the worst one for the weak user, and vice versa. To see why is that true, let P_U=(1/2, 1/2) and let P_X|U be a BSC with a crossover probability 1/2. In this case, the hierarchy of the codebook degenerates, i.e., the codebook has a constant composition, which is best for the strong user. In the other extreme, P_X|U is a BSC with a crossover probability 0. The error probability of the strong user is almost one, but the error exponent of the weak user is the largest and independent of R_y.   
Hence, the choice of the input distribution trades off between the error exponents of the two users.


∙ As can be seen from the minimum in eq. (<ref>), there are two different kinds of error events for the strong user. Let Q^* denote the minimizer in (<ref>). Now, if for some (R_y, R_z), the inequality [  I_Q^*(U;Y)  +  [ I_Q^*(X;Y|U) - R_y]_+ - R_z]_+ > [ I_Q^*(X;Y|U) - R_y]_+ holds, then the dominant error event for the strong user is caused by competing codewords from the true cloud, otherwise, the dominant error event is caused by competitive clouds. 


∙ In fact, the cardinality || is a free parameter in our problem. As such, we may let || →∞, and it is definitely not obvious that a finite || is optimal. This is because we cannot see how to apply the usual cardinality bounding techniques based on the support lemma <cit.>. It must be clear that even if the optimal || is finite, it may not be the same as the bound given in the converse theorem of the capacity region of the ABC (|| ≤ || + 2) <cit.>.




 §.§ Universal Decoders


As mentioned in the Introduction, universal MMI decoders for both 
receivers were proposed in <cit.>, where for the weak user, this decoder was defined by:  

    ĩ_() = *arg max_0 ≤ i ≤ M_z-1Î__i(U;Z) .

The error exponent of such a decoder is 
inferior to the error exponent of the optimal (ML) decoder, 
because for one thing, it makes no use of {_i}, but only of the cloud centers. 
The universal decoder (<ref>) achieves the following error exponent <cit.>

    E_(R_z) =
    min_ Q_Z|UX{   D(Q_Z|UX W_Z|X |  P_UX   ) 
    + [ I_Q(U;Z) - R_z ]_+},

and by comparing it numerically to (<ref>) in the case of the binary symmetric BC (see Subsection 3.4), 
it is evident that E_(R_y, R_z) can be strictly higher than E_(R_z), 
due to the additional term in (<ref>).  
Hence, one may wonder whether a different universal decoder exists, 
whose error exponent is as large as E_(R_y, R_z).
It turns out that the answer to this question is affirmative, and indeed,
this universal decoder relies entirely on  and {_i}.
In Section 5, we prove the following theorem. 

Theorem 2. Define the function

    F(, _i, 𝒞_i) 
    = max_0 ≤ j ≤ M_y-1{Î__i(U;Z)  +  [ Î__i_ij(X;Z|U)  - R_y ]_+} .

The universal decoder

    ĩ_() = *arg max_0 ≤ i ≤ M_z-1   F(, _i, 𝒞_i)

achieves E_(R_y, R_z). 

It turns out that there is also another universal decoder (with the same error
exponent), whose structure is much more similar
to the ML decoder of (<ref>), 
in the sense that its metric is based on  
summation over _i, except that here, the unknown likelihood
function is replaced by the exponentiated empirical mutual information.
In the Appendix we prove the following theorem. 

Theorem 3. The universal decoder

    ĩ_() = *arg max_0 ≤ i ≤ M_z-1{∑_j=0^M_y-1 
    e^n   Î__i_ij(UX;Z)   }

achieves E_(R_y, R_z). 

We next proceed to the strong user and present a universal decoder.
It turns out that the MMI–like metric 
of the universal bin index decoder, as given in Theorem 2 (but with 
replaced by ), works well also for the strong user. 
The main difference between them is rooted in the way they use the metric. 
While the weak user first maximizes it within each cloud, 
and only then finds the cloud with the maximal value, 
the strong user maximizes it over both indices simultaneously. 
More precisely, we claim the following, which is proved in Section 4. 

Theorem 4. Define the function

    G(, _i, _ij) = Î__i(U;Y)  +  [ Î__i_ij(X;Y|U)  - R_y ]_+   .

The universal decoder

    [ĩ_(), j̃_()]
    = *arg max_0 ≤ i ≤ M_z-1, 0 ≤ j ≤ M_y-1  
      G(, _i, _ij)

achieves E_(R_y, R_z). 

At this point, it is interesting to compare
[ĩ_(), j̃_()]
to the universal decoder of the strong user in <cit.>,  

    [î_(), ĵ_() ] = *arg max_0 ≤ i ≤ M_z-1, 0 ≤ j ≤ M_y-1Î__i_ij(UX;Y),

and whose random coding error exponent is given by <cit.>

    E_(R_y, R_z) =
    min_ Q_Y|UX{  D(Q_Y|UX W_Y|X |  P_UX   )  +  E_y,(Q_ UXY, R_y, R_z)   },

where 

    E_y,(Q_ UXY, R_y, R_z) = 
    min{[  I_Q(UX;Y)  - (R_y + R_z)  ]_+, [ I_Q(X;Y|U) - R_y]_+}.

By the identity I(UX;Y) = I(U;Y) + I(X;Y|U), it is 
easy to see that E_(R_y, R_z) = E_(R_y, R_z), proving that (<ref>) has an error exponent as that of (<ref>), a fact that was not asserted in <cit.>.




 §.§ Gallager–Style Lower Bounds


As mentioned before, the calculations of (<ref>) and (<ref>) 
involve minimizations over auxiliary channels, 
which become painful when the input and output alphabets are large. 
For this reason, we look for other forms of error exponent formulas, 
where the number of parameters to be optimized does not grow with the alphabet sizes, 
but the price of this might be some loss in the tightness of the bounds, 
i.e., we obtain lower bounds on the random coding error exponents. Even in the single user case, the random coding error exponent involves a minimization over an auxiliary channel, where Csiszár and Körner <cit.> show that the exact error exponent is lower bounded by the following expression 

    E_(R) =
    max_ρ∈ [0,1] {  - log∑_y[ ∑_x P(x)W^1/1+ρ(y|x)     ]^1+ρ  -ρ R   },

where the subscript 'G' stands for “Gallager", who was the first to derive and analyze the error exponent in this form <cit.>. It is important to note that for the optimal code distribution, (<ref>) is not only a lower bound, but the exact random coding error exponent <cit.>. It turns out that the exact random coding error exponents of the two users in the ABC can be lower bounded by the same methods as in <cit.>. In Section 6, we prove the following theorem. 

Theorem 5. Define the functions

    Φ(u,y,s)    = ∑_x P(x|u)[W_1(y|x)]^1/1+s, 
    Ψ(u,z,s)    = ∑_x P(x|u)[W_2(z|x)]^1/1+s.

The exact random coding error exponent of the strong user is lower bounded by

    E_(R_y, R_z) ≥min{  E_ y,1 (R_y), E_ y,2 (R_y, R_z)      },

where

    E_ y,1 (R_y)    = max_ρ∈ [0,1] {  - ∑_u P(u) log( ∑_yΦ^1+ρ(u,y,ρ)  )  - ρ R_y},   
    
    E_ y,2 (R_y, R_z)    = max_μ∈ [0,1] max_λ∈ [0,μ] {    
      -  log[ ∑_y(  ∑_u P(u)  Φ^1+λ/1+μ(u,y,λ)    )^1+μ]   -  λ R_y  -μ R_z}  .

In addition, the random coding error exponent 
of the weak user is lower bounded by

    E_(R_y, R_z) ≥max_μ∈ [0,1] max_λ∈ [0,μ] {    
      -  log[ ∑_z(  ∑_u P(u)  Ψ^1+λ/1+μ(u,z,λ)    )^1+μ]   -  λ R_y  -μ R_z}  .



These lower bounds 
involve maximizations over one or two parameters only, in contrast to the original error exponents, and so, they are much easier to evaluate. In Section 7, we study them and show how they behave in different regions of the plane of rates. In contrast to the single user case, both lower bounds of the two users depend on the code distribution, but now we are no longer able to optimize both of them simultaneously, for the reason we mentioned above, in subsection 3.1.




 §.§ Numerical Results and Phase Diagrams

We next provide some numerical results, comparing our exponents to those of <cit.> and <cit.>. 
Let W_1 and W_2 be two binary symmetric channels (BSC´s) with
crossover parameters p_y and p_z, respectively (p_z > p_y).
Let 𝒰 be binary as well and let P_U be 
uniformly distributed over {0,1}. 
Also, let P_X|U be a BSC with crossover parameter β∈ [0,1].  

The capacity region of our model is given by:

    R_z   ≤ln 2 - h(β * p_z)  
    
    R_y   ≤ h(β * p_y) - h( p_y),

where β * p = β(1-p) + (1 - β)p and h(x) is the binary entropy function. 




  §.§.§ Gallager-Style Lower Bounds
 
Using Theorem 5, we find that for the strong user,

    E_(R_y, R_z)    ≥min{ E_y,1(R_y),  E_y,2(R_y, R_z)    },

where,

    E_y,1(R_y) =
    max_ρ∈ [0,1] {  -  log{[  (1-β)(1-p_y)^1/1+ρ + β· p_y^1/1+ρ]^1+ρ
                                                      +  [  (1-β) · p_y^1/1+ρ + β· (1-p_y)^1/1+ρ]^1+ρ}   - ρ R_y}, 
       E_y,2(R_y, R_z) 
       = max_μ∈ [0,1] max_λ∈ [0,μ] {  -  ln 2  - (1+μ) ·log{1/2·[ (1-β)(1-p_y)^1/1+ λ + β· p_y^1/1+λ]^1+λ/1+μ
                                     +  1/2·[  (1-β) · p_y^1/1+ λ + β· (1-p_y)^1/1+ λ]^1+λ/1+μ}    - λ R_y  -μ R_z}.

For the weak user,

    E_(R_y, R_z) 
       ≥max_μ∈ [0,1] max_λ∈ [0,μ] {  -  ln 2  - (1+μ) ·log{1/2·[ (1-β)(1-p_z)^1/1+ λ + β· p_z^1/1+λ]^1+λ/1+μ
                                     +  1/2·[  (1-β) · p_z^1/1+ λ + β· (1-p_z)^1/1+ λ]^1+λ/1+μ}    - λ R_y  -μ R_z}.

We present the lower bounds by plotting families of curves, one for each exponent, as a function of one rate, while the other rate is kept fixed. 
Let us choose the channel probabilities to be p_y = 0.05 and p_z = 0.1, and β = 0.25. 
In Fig. 1, we plot lower bounds to E_(R_y, R_z) as a function of R_y, as given by (<ref>), where R_z takes five different values.

As long as R_z < 0.09, the dominant error event is caused by wrong codewords from the true cloud. In this case, the error exponent is independent of the number of clouds and is given by the dark blue curve. As R_z increases more, we find that above some critical rate, the error exponent begins to depend on the number of clouds, since the dominant error event is due to wrong codewords from competitive clouds. When the rate of the weak user is high, i.e., when the exponential number of clouds is higher than the capacity of the channel to the strong user (R_z > 0.49 ≈ h(0.05)), reliable communication is no longer possible. 

In Fig. 2, we plot lower bounds to E_(R_y, R_z) as a function of R_z, as given by (<ref>), where R_y takes five different values.

At R_y = 0, we should obtain the error exponent of a single user. In this case, the numerical value at zero-rate is given by E_(0,0) = 0.22314, and E_(0,R_z) vanishes at R_z≅ 0.36 ≈ h(0.1), which is the capacity of the channel to the weak user. For R_y > 0.32, E_(R_y, R_z) becomes independent of R_y, and is given by the red curve. In this case, we get a lower bound to the error exponent of the equivalent binary symmetric channel from the cloud center U to the channel output of the weak user Z. 





  §.§.§ Exact Exponents

As for the exact random coding error exponents, given by Theorem 1, the optimization problems require the minimization over the auxiliary channels Q_Y|UX and Q_Z|UX. Let us compare the Gallager-style lower bounds to the exact exponents. In Fig. 3, we see two pairs of curves of the exact exponents and their lower bounds, where R_z=0.05 and β takes two different values. The exact exponents are strictly better than the Gallager-style exponents. Similar results are obtained for the weak user as well (not shown here). It is important to note that in some regions in the R_y-R_z plane, the lower bounds are equal to the exact random coding error exponents.






  §.§.§ Comparison with Previous Works

As far as we know, no other works on universal decoding for the ABC exists, besides the one of <cit.>. Although the error exponent of the strong user given there is optimal w.r.t. the ML decoder, it is not the case for the weak user. The universal decoder of <cit.> for the weak user uses only the cloud centers and is independent of R_y, while the new universal decoder of Theorem 2 makes use of the entire codebook, which is the main reason for the resulted improvement. The difference between the error exponents is larger for lower values of R_y. 

As before, let p_z = 0.1 and β = 0.25. 
Fig. 4 demonstrates the difference between the error exponents of the two universal decoders in the extreme case of R_y = 0.


To the best of our knowledge, the most up-to-date work on exponential lower bounds to the reliability functions of the ABC is <cit.>, where random coding error exponents were derived using two different techniques. Each of those derivations includes at least one step that may not be exponentially tight.
 Also, in <cit.>, the random codebooks are assumed to be drawn i.i.d.. We expect our proposed exact random coding error exponents to improve on <cit.>, because of two reasons: first, our analysis is exponentially tight, and second, our ensemble is of the uniform distribution across types. This kind of random codes are known <cit.> to be better than the i.i.d. ensembles. Our comparison here focuses on the error exponent of the weak user only. Again, let p_z = 0.1, β = 0.25 and R_y = 0.4. 
Fig. 5 compares the two error exponents, and shows that the new exponent is better.  




  §.§.§ Phase Diagrams

In the single user case, it is known that the error exponent behaves differently in different ranges of rates, i.e., it is affine at low rates and curvy at high rates. By the same token, for the ABC, the plane of rates can be divided into several different regions, where in each one of them, the error exponents behaves differently. This partition of the plane of rate pairs is of course, more involved than in the single-user case. We refer to it as a phase diagram, a term borrowed from physics.
In order to study the various types of behavior of the lower bound of Theorem 5, let us invoke the following alternative and equivalent lower bound for the random coding error exponent of the weak user

    E_(R_y, R_z) ≥max_μ∈ [0,1] max_s ∈ [0,1] {    
      -  log[ ∑_z(  ∑_u P(u)  Ψ^1+s μ/1+μ(u,z, sμ)    )^1+μ]   -  s μ R_y  -μ R_z}  .

Since the maximization region is now the unit square, this form is more convenient to analyze than that of (<ref>). 
Fig. 6 displays a partition of the plane R_y-R_z to different regions for the Gallager-style lower bound of the weak user, where β=0.1, and p_z = 0.1. Although not shown here, the phase diagrams of the exact exponents behave similarly.

The study in Section 7 provides a characterization of the different regions 
from the viewpoint of the type of dependence of the error exponent upon
the rates and the maximizers s^* and μ^* (see Table 1).














§ UNIVERSAL DECODING FOR THE STRONG USER




 §.§ Analysis for a General Decoder


Let us first derive the exact random coding error exponent for a strong user that uses the following generic decoder

    [î (), ĵ ()] =   *arg max_0 ≤ i ≤ M_z-1, 0 ≤ j ≤ M_y-1   f(Q_U_iX_ijY),

where from now on, Q_UXY will designates the joint empirical distribution induced by the three sequences ,  and , i.e., Q_UXY = P̂_. 
The average error probability P̅_e(R_y,R_z,n), associated with (<ref>) is 

    P̅_e(R_y,R_z,n)      △=1/M_y M_z∑_i=0^M_z-1∑_j=0^M_y-1   Pr{{⋃_k ≠ j{ f(Q_U_iX_ikY) ≥ f(Q_U_iX_ijY) | 𝐗_ij sent}}
       ⋃{⋃_l ≠ i⋃_k{ f(Q_U_lX_lkY) ≥ f(Q_U_iX_ijY) | 𝐗_ij sent}}}

where Pr{·} pertains to the randomness of the codebook as well as that of the channel output given its input. Without loss of generality, we assume throughout, that the transmitted codeword is 𝐗_00 = _00. 
We define

    𝒜△=⋃_k=1^M_y-1𝒜_k△=⋃_k=1^M_y-1{  f(Q_U_0X_0kY) ≥ f(Q_U_0X_00Y)     }

and                                       

    ℬ△=⋃_l=1^M_z-1ℬ_l△=⋃_l=1^M_z-1⋃_k=0^M_y-1ℬ_lk△=⋃_l=1^M_z-1⋃_k=0^M_y-1{ f(Q_U_lX_lkY) ≥ f(Q_U_0X_00Y) } .

Define the real number s as 

    s  △=   f(Q_U_0X_00Y)  .

The pairwise average error probability, conditioned on the center of the competitive cloud, is given by

    Pr(ℬ_lk | 𝐔_l = ')      △=Pr{ f(Q_U_lX_lkY) ≥ f(Q_U_0X_00Y) | 𝐔_l = ' }
       =     ∑_{':    f(Q_U'X'Y)  ≥ s  } P ( ' | ' ) 
       =  ∑_{ Q_X'|U'Y∈𝒮(Q_U'Y) :    f(Q_U'X'Y)  ≥ s   }∑_∈𝒯(Q_X'|U'Y|',)   P (  | ' ) 
       =  ∑_{ Q_X'|U'Y∈𝒮(Q_U'Y) :    f(Q_U'X'Y)  ≥ s   } 
           P ( ' | ' ) ·  |𝒯(Q_X'|U'Y|',)| 
       ≐∑_{ Q_X'|U'Y∈𝒮(Q_U'Y) :    f(Q_U'X'Y)  ≥ s   }exp{-n ·  I_ Q(X;Y|U)   }
       ≐max_{ Q_X'|U'Y∈𝒮(Q_U'Y) :    f(Q_U'X'Y)  ≥ s  }exp{-n ·    I_ Q(X;Y|U)    }
       =   exp{-n ·min_{ Q_X'|U'Y∈𝒮(Q_U'Y) :    f(Q_U'X'Y)  ≥ s  }      I_ Q(X;Y|U)      }
       △=exp{-n ·   E_0(s, Q_U'Y )    }   ,

where 𝒮(Q_UY) denotes the set of conditional distributions {Q_X|UY} that are consistent with P_UX.
For a given 𝐔_l = ', the events {ℬ_lk}_k are all pairwise independent since we have assumed that the various codewords are pairwise conditional independent given the cloud center. Using the exponential tightness of the truncated union bound <cit.>, we get

    Pr{⋃_k=0^M_y-1ℬ_lk| 𝐔_l = '   }   ≐min{ 1, ∑_k=0^M_y-1Pr(ℬ_lk | 𝐔_l = ')  }
       =   min{ 1, M_y·Pr(ℬ_l,0 | 𝐔_l = ')  }
       ≐min{ 1, e^nR_y·exp[ -n ·   E_0(s, Q_U'Y )    ]  }
       △=exp{-n ·   E_1(s, Q_U'Y  )    }  ,

where

    E_1(s, Q_U'Y ) =  min_Q_X'|U'Y∈𝒮(Q_U'Y){[ I_ Q(X;Y|U) - R_y]_+:      f(Q_U'X'Y)  ≥ s  }.



Next, we obtain the probability of ℬ_l by calculating the expectation w.r.t. the randomness of 𝐔_l:

    Pr{ℬ_l}   =  ∑_' ∈𝒯(P_U)  P_U(')  ·Pr{⋃_k=0^M_y-1ℬ_lk| 𝐔_l = '   }
       ≐∑_' ∈𝒯(P_U)    P_U(')  ·exp{-n ·   E_1(s, Q_U'Y )    }
       = ∑_{ Q_U'|Y∈𝒮(Q_Y)   }∑_∈𝒯(Q_U'|Y|)    P_U()  ·exp{-n ·   E_1(s, Q_ŨY )    }
       = ∑_{ Q_U'|Y∈𝒮(Q_Y)   }|𝒯(Q_U'|Y|)|/|𝒯(')|·exp{-n ·   E_1(s, Q_U'Y )    }
       ≐∑_{ Q_U'|Y∈𝒮(Q_Y)   }exp{-n ·[  
    I_ Q(U;Y)  +    E_1(s, Q_U'Y )    ]  }
       ≐exp{-n ·min_{ Q_U'|Y∈𝒮(Q_Y)   }[  I_ Q(U;Y)  +   E_1(s, Q_U'Y )   ]  }
       △=exp{-n ·   E_2(s, Q_Y )    },

where 𝒮(Q_Y) is the set of all {Q_U|Y} such that ∑_yQ_Y(y)Q_U|Y(u|y)=P_U(u) for every u ∈𝒰. 
Next, we turn to calculate the probabilities of the events 𝒜_k. One can easily check that the entire derivation of eqs. (<ref>)-(<ref>) holds in this case as well, except that now we condition on 𝐔_0 = _0, such that the codewords are drawn from P(· | _0). We get 

    Pr(𝒜_k | 𝐔_0 = _0)      △=Pr{ f(Q_U_0X_0kY) ≥ f(Q_U_0X_00Y) | 𝐔_0 = _0}
       ≐exp{-n ·   E_0(s, Q_U_0Y )    } .

Notice that, for a given 𝐔_0 = _0, 𝐗_00 = _00 and 𝐘 =, the events {𝒜_k} (errors caused by codewords from the correct cloud) and {ℬ_l} (errors caused by codewords from competitive clouds) are all pairwise independent. Thus, after taking the expectation w.r.t. the joint distribution of (𝐔_0,  𝐗_00, 𝐘), we have

    P̅_e(R_y,R_z,n) 
       =  𝔼[  Pr{{⋃_k=1^M_y-1𝒜_k}⋃{⋃_l=1^M_z-1ℬ_l}| 𝐔_0 = _0, 𝐗_00 = _00, 𝐘 = }]   
       ≐𝔼[ min{ 1, ∑_k=1^M_y-1Pr(𝒜_k | 𝐔_0 = _0, 𝐗_00 = _00, 𝐘 = )  
                                 +   ∑_l=1^M_z-1Pr(ℬ_l | 𝐔_0 = _0, 𝐗_00 = _00, 𝐘 = )  }]    
       ≐𝔼[ min{  1, e^nR_yexp{-n ·   E_0(S, Q_U_0Y )    }
                                +  e^nR_zexp{-n ·   E_2(S, Q_Y )    }}]    
       ≐𝔼[ min{  1,   exp{ -n ·min{[ E_0(S, Q_U_0Y ) -  R_y]   , 
    
                                                       [ E_2(S, Q_Y ) -  R_z] }}}]   
       =   𝔼[   exp( -n ·min{[ E_0(S, Q_U_0Y ) -  R_y]_+   , [ E_2(S, Q_Y ) -  R_z]_+})  ]   
       ≐exp{-n ·min_ Q_Y|U_0X_00[  D(Q_Y|U_0X_00||W_Y|X_00| P_U_0X_00  )  
    
                                                 + E_3( f(Q_U_0X_00Y), Q_U_0Y, R_y, R_z)  ]   }  ,

where we have defined

    E_3(S, Q_U_0Y, R_y, R_z )  △=min{[ E_0(S, Q_U_0Y ) -  R_y]_+   , [ E_2(S, Q_Y ) -  R_z]_+}.






 §.§ A Converse-Like[A converse result is usually w.r.t. both encoding and decoding. In our case, here and in Subsection 5.1, the converse results are w.r.t. the decoding only.] Result for the Strong User

We have the following: 
 
Lemma 1. For every empirical distribution Q_U_0X_00Y,

    E_3( f(Q_U_0X_00Y), Q_U_0Y , R_y, R_z) ≤min{[  I_Q(U_0;Y)  +    [ I_Q(X_00;Y|U_0) - R_y]_+ - R_z]_+, 
       [ I_Q(X_00;Y|U_0) - R_y]_+}.



Proof. We start by recalling that the function E_3 is defined as

    E_3(f(Q_U_0X_00Y), Q_U_0Y, R_y, R_z )  △=min{   [ E_0(f(Q_U_0X_00Y), Q_U_0Y ) -  R_y]_+   , 
       [ E_2( f(Q_U_0X_00Y) , Q_Y ) -  R_z]_+},

and we separately upper bound each one of the terms. We can upper bound them by choosing any specific distribution, instead of minimizing over them. Let us start with the left term:

    [ E_0(f(Q_U_0X_00Y), Q_U_0Y ) -  R_y]_+
       = min_{ Q_X|U_0Y∈𝒮(Q_U_0Y):      f(Q_U_0XY) ≥ f(Q_U_0X_00Y)    }[ I_Q(X;Y|U_0) - R_y]_+
       ≤[ I_Q(X_00;Y|U_0) - R_y]_+.

For the right term inside the minimum of (<ref>), we have the following 

    [ E_2(f(Q_U_0X_00Y), Q_Y ) -  R_z]_+
       = min_{ Q_U'|Y∈𝒮(Q_Y)   }[  I_ Q(U';Y)  +   E_1( f(Q_U_0X_00Y), Q_U'Y )  -  R_z]_+
       ≤[  I_ Q(U_0;Y)  +   E_1(f(Q_U_0X_00Y), Q_U_0Y )  -  R_z]_+
       =   [  I_ Q(U_0;Y)  +  min_{ Q_X|U_0Y∈𝒮(Q_U_0Y) :     f(Q_U_0XY) ≥ f(Q_U_0X_00Y)    }[ I_Q(X;Y|U_0) - R_y]_+   -  R_z]_+
       ≤[  I_ Q(U_0;Y)  +  [ I_Q(X_00;Y|U_0) - R_y]_+  -  R_z]_+ .

Combining both upper bounds, we see that (<ref>) holds, thus completing the proof.  





 §.§ An Optimal Universal Decoder

Let us now select

    f(Q_UXY) =
    I_Q(U;Y)  + [ I_Q(X;Y|U) - R_y]_+.

We show that (<ref>) achieves the maximum value of E_3( f(Q_U_0X_00Y), Q_U_0Y , R_y, R_z), as given by Lemma 1, and therefore, this decoder has the same error exponent as the one of the optimal (ML) decoder. As before, we start with the left term inside the minimum of (<ref>), and get

    [ E_0(f(Q_U_0X_00Y), Q_U_0Y ) -  R_y]_+
       = min_{ Q_X|U_0Y∈𝒮(Q_U_0Y)  }{[ I_Q(X;Y|U_0) - R_y]_+  :      f(Q_U_0XY) ≥ f(Q_U_0X_00Y)  }
       = min_{ Q_X|U_0Y∈𝒮(Q_U_0Y)  }{[ I_Q(X;Y|U_0) - R_y]_+  : 
       I_Q(U_0;Y)  + [ I_Q(X;Y|U_0) - R_y]_+≥ I_Q(U_0;Y)  + [ I_Q(X_00;Y|U_0) - R_y]_+}
       = min_{ Q_X|U_0Y∈𝒮(Q_U_0Y)  }{[ I_Q(X;Y|U_0) - R_y]_+  :  
         [ I_Q(X;Y|U_0) - R_y]_+≥  [ I_Q(X_00;Y|U_0) - R_y]_+}
       = [ I_Q(X_00;Y|U_0) - R_y]_+.

For the right term inside the minimum of (<ref>), 

    [ E_2(f(Q_U_0X_00Y), Q_Y ) -  R_z]_+
       = min_{ Q_UX|Y∈𝒮(Q_Y) :     f(Q_UXY) ≥ f(Q_U_0X_00Y)  }[  I_ Q(U;Y)  +   [ I_Q(X;Y|U) - R_y]_+  -  R_z]_+
       = min_{ Q_UX|Y∈𝒮(Q_Y)   }{[  I_ Q(U;Y)  +   [ I_Q(X;Y|U) - R_y]_+  -  R_z]_+ : 
       I_Q(U;Y)  + [ I_Q(X;Y|U) - R_y]_+≥ I_Q(U_0;Y)  + [ I_Q(X_00;Y|U_0) - R_y]_+}
       = [  I_ Q(U_0;Y)  +   [ I_Q(X_00;Y|U_0) - R_y]_+  -  R_z]_+.

Finally, compare the minimum between (<ref>) and (<ref>) to the right hand side of (<ref>).







§ UNIVERSAL BIN INDEX DECODING FOR THE WEAK USER




 §.§ Analysis for a General Decoding Metric and a Converse-Like Result

Let us first derive the exact random coding error exponent of the following bin index decoder,

    î() = *arg max_0 ≤ i ≤ M_z-1 F(,_i,𝒞_i)  ,

where

    F(,_i,𝒞_i)  △=1/M_y∑_j=0^M_y-1 e^nf(Q_U_iX_ijZ) ,

and assume that f is upper bounded by a real number Δ. Note that (<ref>) includes the optimal ML decoder (<ref>) as a special case. 

To present the formula of E^*_z(R_y, R_z), the error exponent of (<ref>), we first need a few definitions. For a given generic joint distribution Q_UXZ, let I_Q(X;Z|U) denote the conditional mutual information between X and Z given U. For a given marginal Q_UZ, let 𝒮(Q_UZ) denote the set of conditional distributions {Q_X|UZ} such that ∑_z Q_UZ(u,z)Q_X|UZ(x|u,z) = P_UX(u,x) for every (u,x) ∈𝒰×𝒳, where P_UX = P_U× P_X|U. We first define

    E_1(s, Q_UZ)  =  min_Q_X|UZ∈𝒮(Q_UZ){ [ I_Q (X;Z|U) - R_y]_+:f(Q_UXZ) +[R_y- I_Q (X;Z|U)]_+≥ s  },

where s is an arbitrary real. Next, for a given marginal Q_Z, define

    E_2(s, Q_Z)  =  min_Q_U|Z∈𝒮(Q_Z)[  I_Q (U;Z) +  E_1(s, Q_UZ)  ],

where the minimization is across all {Q_U|Z} such that ∑_zQ_Z(z)Q_U|Z(u|z)=P_U(u) for every u ∈𝒰. Finally, for a given Q_U_0Z, let

    s_0(Q_U_0Z) = R_y + max_{ Q_X|U_0Z∈𝒮(Q_U_0Z): I_Q (X;Z|U_0) ≤ R_y}[ f(Q_U_0XZ) - I_Q (X;Z|U_0) ],

and

    s_1(Q_U_0X_00Z) = max{ s_0(Q_U_0Z), f(Q_U_0X_00Z)  }.

Now, the error exponent of the decoder (<ref>) is given in the following lemma. 

Lemma 2. Under the assumptions of Section 2, 

    E^*_z(R_y, R_z) = min_Q_Z|U_0X_00{ D(Q_Z|U_0X_00||W_Z|X_00| P_U_0X_00  ) +   [E_2( s_1(Q_U_0X_00Z), Q_Z) - R_z]_+},

where (U_0,X_00) is a replica of (U,X), i.e., P_U_0X_00 = P_UX. 

Proof. The average probability of error, associated with (<ref>), is given by

    P_e^*   =  𝔼[ Pr{⋃_i=1^M_z-1{ F(𝐙,𝐔_i,𝒞_i) ≥  F(𝐙,𝐔_0,𝒞_0)  }}] 
       ≐𝔼[ min{1, M_z·Pr{ F(𝐙,𝐔_1,𝒞_1) ≥  F(𝐙,𝐔_0,𝒞_0)  }}]  ,

where the expectation is w.r.t. the randomness of 𝐔_0, 𝒞_0 and 𝐙, where 𝐙 is the channel output in response to the input 𝐗_00 (the transmitted codeword without loss of generality). The passage from (<ref>) to (<ref>) is due to the exponential tightness of the truncated union bound. 
Here, for a given , Pr{ F(,𝐔_1,𝒞_1) ≥  F(,_0,𝒞_0)  } is calculated w.r.t. the randomness of 𝐔_1 and 𝒞_1 = {𝐗_1,0,...,𝐗_1,(M_y-1)}, but for a given _0 and 𝒞_0. 

Let N_1(Q_U_1X'Z) denote the number of codewords _1,j∈𝒞_1, such that the joint empirical distribution of  _1,j with (_1, ) is Q_U_1X'Z, that is

    N_1(Q_U_1X'Z) = ∑_j=0^M_y-1ℐ{ (_1, _1,j, ) ∈𝒯(Q_U_1X'Z) }.

Defining

    s  △=1/nln [  ∑_j=0^M_y-1  e^nf(Q_U_0X_0jZ)]  ,

we have,

    Pr{ F(,_1,𝒞_1) ≥  F(,_0,𝒞_0)  }   =   Pr{ M_y· F(,_1,𝒞_1)   ≥  e^ns}
       =   Pr{∑_j=0^M_y-1  e^nf(Q_U_1X_1jZ)≥  e^ns}
       =   Pr{∑_Q_X'|U_1Z∈𝒮(Q_U_1Z) N_1(Q_U_1X'Z)e^nf(Q_U_1X'Z)≥  e^ns}
       ≐Pr{max_Q_X'|U_1Z∈𝒮(Q_U_1Z)  N_1(Q_U_1X'Z)e^nf(Q_U_1X'Z)≥  e^ns}
       =     Pr{⋃_Q_X'|U_1Z∈𝒮(Q_U_1Z){N_1(Q_U_1X'Z)e^nf(Q_U_1X'Z)≥  e^ns}}
       ≐∑_Q_X'|U_1Z∈𝒮(Q_U_1Z)Pr{ N_1(Q_U_1X'Z)e^nf(Q_U_1X'Z)≥  e^ns}
       ≐max_Q_X'|U_1Z∈𝒮(Q_U_1Z)Pr{ N_1(Q_U_1X'Z)e^nf(Q_U_1X'Z)≥  e^ns}.

Now, for a given Q_U_1X'Z, designating the joint empirical distribution of a randomly chosen ' (given _1) together with (_1, ), the binomial random variable N_1(Q_U_1X'Z) has e^nR_y trials and probability of success which is of the exponential order of e^-n I_Q(X;Z|U). Thus, a standard large deviations analysis (see, e.g., <cit.>) yields

    Pr{ N_1(Q_U_1X'Z)  ≥  e^n [ s-f(Q_U_1X'Z) ] }≐     e^-nE_0(Q_U_1X'Z) ,

where

    E_0(Q_U_1X'Z)  
                                    =             {[                      [ I_Q(X;Z|U) - R_y]_+     f(Q_U_1X'Z) ≥ s - [R_y- I_Q(X;Z|U) ]_+;                                          ∞ f(Q_U_1X'Z)  <    s- [R_y- I_Q(X;Z|U) ]_+. ].
 
Therefore, max_Q_X'|U_1Z∈𝒮(Q_U_1Z)Pr{ N_1(Q_U_1X'Z)  ≥  e^n [s-f(Q_U_1X'Z) ] } decays according to 

    E_1(s, Q_U_1Z ) = min_Q_X'|U_1Z∈𝒮(Q_U_1Z)   E_0(Q_U_1X'Z)  ,

which is given by (<ref>). 

The conditional pairwise error probability, given 𝐔_1=_1, is of the exponential order of e^-n E_1(s, Q_U_1Z ). Averaging w.r.t. the randomness of 𝐔_1, we get the exponential order of e^-n E_2(s, Q_Z ), where E_2(s, Q_Z ) is defined as in (<ref>). To see why this is true, consider the following:

    ∑__1∈𝒯 (P_U)  P_U(_1) ·Pr{ F(,_1,𝒞_1) ≥  F(,_0,𝒞_0)  }
       ≐∑_ Q_U_1|Z∈𝒮(Q_Z) ∑__1∈𝒯(Q_U_1|Z|)  P_U(_1) · e^-n · E_1(s, Q_U_1Z )  
       ≐∑_Q_U_1|Z∈𝒮(Q_Z)    e^-n · E_1(s, Q_U_1Z )  · e^-n · I_Q(U;Z)  
       ≐max_Q_U_1|Z∈𝒮(Q_Z)    e^-n ·[I_Q(U;Z) +  E_1(s, Q_U_1Z ) ]  
       =  e^-n · E_2(s, Q_Z ).

Finally, we have that

    P_e^*   ≐𝔼[   min{ 1,  M_z·   e^-n · E_2(S, Q_Z )  }] 
       =  𝔼{ e^-n [ E_2(S, Q_z ) - R_z]_+}  ,

where the expectation is w.r.t. the randomness of

    S  =  1/nln [  ∑_j=0^M_y-1  e^nf(Q_U_0X_0jZ)]  ,

the randomness of Q_Z, the empirical distribution of 𝐙, and 𝐔_0, the real cloud center.

This expectation will be taken in two steps, the first is over the randomness of {𝐗_0,1,...,𝐗_0,(M_y-1)}, while 𝐗_00=_00, 𝐔_0=_0 and 𝐙= are held fixed, whereas in the second step, the expectation is over the randomness of 𝐗_00, 𝐔_0 and 𝐙. 
Let _00, _0 and  be given and let ϵ > 0 be arbitrarily small. Then,

    P_e^*( _00, _0,   )     △=𝔼{  e^-n [ E_2(S, Q_Z ) - R_z]_+|  𝐗_00=_00, 𝐔_0=_0, 𝐙=}
       ≤∑_iPr{  iϵ≤ S < (i+1)ϵ|  𝐗_00=_00, 𝐔_0=_0, 𝐙=}
                            ×exp{ -n [ E_2(iϵ, Q_Z ) - R_z]_+}   ,

where i ranges from 1/ϵ f(Q_U_0X_00Z  ) to (R_y+ Δ )/ϵ.
Now,  

    e^nS   =    e^n f(Q_U_0X_00Z  )   +   ∑_j=1^M_y-1  e^nf(Q_U_0X_0jZ  ) 
       =   e^nf(Q_U_0X_00Z  )    + ∑_Q_X'|U_0Z∈𝒮(Q_U_0Z) N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z),

where N_0(Q_U_0X'Z) is the number of codewords in 𝒞_0∖{_00}, whose joint empirical distribution with (_0,) is Q_U_0X'Z.
On the one hand, we have

    Pr{∑_Q_X'|U_0Z∈𝒮(Q_U_0Z) N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z)≥ e^nt}≐         e^-n · E_1(t, Q_U_0Z )       ,

and on the other hand, 

    Pr{∑_Q_X'|U_0Z∈𝒮(Q_U_0Z)   N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z)≤ e^nt}
       ≐Pr{⋂_ Q_X'|U_0Z∈𝒮(Q_U_0Z) {  N_0(Q_U_0X'Z)  ≤    e^n[t- f(Q_U_0X'Z) ]}}  .

This probability behaves exponentially like an indicator function of the condition that for every Q_X'|U_0Z∈𝒮(Q_U_0Z), either I_Q(X;Z|U_0) ≥ R_y or R_y - I_Q(X;Z|U_0) ≤ t-f(Q_U_0X'Z) <cit.>. I.e.,

    Pr{∑_Q_X'|U_0Z∈𝒮(Q_U_0Z)   N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z)≤ e^nt}
       ≐ℐ{    R_y≤min_ Q_X'|U_0Z∈𝒮(Q_U_0Z) {  I_Q(X;Z|U_0)  +   [t - f(Q_U_0X'Z) ]_+}}  .

Let us now find what is the minimum value of t for which the value of this indicator function is unity. The condition is equivalent to

    min_ Q_X'|U_0Z∈𝒮(Q_U_0Z) max_0 ≤ a ≤ 1{   I_Q(X;Z|U_0)  + a  [t- f(Q_U_0X'Z) ]     }≥   R_y ,

or

    ∀Q_X'|U_0Z∈𝒮(Q_U_0Z) 
    
     ∃ a ∈ [0,1]: 
    
        I_Q(X;Z|U_0)  + a  [ t- f(Q_U_0X'Z) ]    ≥   R_y ,

or

    ∀ Q_X'|U_0Z∈𝒮(Q_U_0Z) 
    
     ∃ a ∈ [0,1]: 
    
            t ≥   f(Q_U_0X'Z) + 1/a( R_y - I_Q(X;Z|U_0) )  ,

or, equivalently, 

    t      ≥max_ Q_X'|U_0Z∈𝒮(Q_U_0Z) min_0 ≤ a ≤ 1[    f(Q_U_0X'Z)  + 1/a( R_y -  I_Q(X;Z|U_0) )   ]  
       =   max_ Q_X'|U_0Z∈𝒮(Q_U_0Z) [ f(Q_U_0X'Z)  +       {[        R_y - I_Q(X;Z|U_0)      ,  R_y≥ I_Q(X;Z|U_0);                      -  ∞ ,  R_y    <  I_Q(X;Z|U_0) ].    ]   
       = R_y + max_{ Q_X'|U_0Z∈𝒮(Q_U_0Z):   I_Q(X;Z|U_0) ≤ R_y}[ f(Q_U_0X'Z) - I_Q(X;Z|U_0) ]  
       △=    s_0(  Q_U_0Z   ).

Thus, in summary, we have
 
    Pr{   e^nt≤∑_Q_X'|U_0Z∈𝒮(Q_U_0Z)   N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z)≤   e^n(t+ϵ)}
       ≐{[                       0 t <s_0(  Q_U_0Z   ) - ϵ;  e^-n · E_1(t, Q_U_0Z )       t ≥ s_0( Q_U_0Z ) ].

Therefore, we get the expected error probability

    P_e^*(_00, _0,  )   
         ≤∑_iPr{  e^niϵ≤∑_Q_X'|U_0Z∈𝒮(Q_U_0Z) N_0(Q_U_0X'Z) e^nf(Q_U_0X'Z)≤      e^n(i+1)ϵ}
                          ×exp{-n [ E_2(max{ iϵ, f(Q_U_0X_00Z)  }, Q_Z) - R_z]_+}
       ≐∑_i ≥ s_0( Q_U_0Z) / ϵexp{-n E_1(iϵ, Q_U_0Z )  }
                          ×exp{-n [ E_2(max{ iϵ, f(Q_U_0X_00Z)  }, Q_Z) - R_z]_+} .

Since the dominant contribution to the sum over i is due to the term i = s_0(Q_U_0Z) / ϵ (by the non-decreasing monotonicity of the functions E_1(·, Q_U_0Z ) and E_2(·, Q_Z )), we obtain
 
    P_e^*( _00, _0,  )     ≐exp{-n [ E_2(max{ s_0(Q_U_0Z ), f(Q_U_0X_00Z)  }, Q_Z) - R_z]_+}
       △=exp{-n [ E_2( s_1(Q_U_0X_00Z) , Q_Z) - R_z]_+}.

Now, after taking the expectation w.r.t. the joint distribution of (𝐔_0,  𝐗_00, 𝐙), we get the exact random coding error exponent (<ref>),
and the proof of Lemma 2 is complete.    



Next, we introduce the following converse-like result for the weak user. 

Lemma 3. For every empirical distribution Q_U_0X_00Z,

    E_2(s_1(Q_U_0X_00Z), Q_Z)  ≤
    I_Q(U_0;Z)  +  [ I_Q(X_00;Z|U_0) - R_y]_+.

Proof. By (<ref>),

    E_2(s_1(Q_U_0X_00Z), Q_Z)     =   min_Q_U|Z∈𝒮(Q_Z) {  I_Q(U;Z) +  E_1(s_1(Q_U_0X_00Z), Q_UZ )  }
       ≤   I_Q(U_0;Z) +  E_1(s_1(Q_U_0X_00Z), Q_U_0Z )   ,

where

    E_1(s_1(Q_U_0X_00Z), Q_U_0Z) 
       = min_ Q_X'|U_0Z∈𝒮(Q_U_0Z):   f(Q_U_0X'Z) +[R_y- I_Q(X';Z|U_0) ]_+≥ s_1(Q_U_0X_00Z)  [ I_Q(X';Z|U_0) - R_y]_+ .
 
Now, since s_1(Q_U_0X_00Z) is given by the maximum
 
    s_1(Q_U_0X_00Z) =    
     max{ s_0(Q_U_0Z), f(Q_U_0X_00Z)  } ,

we treat each case separately. First, if s_1(Q_U_0X_00Z) =  f(Q_U_0X_00Z), 

    E_1( f(Q_U_0X_00Z), Q_U_0Z) 
       = min_ Q_X'|U_0Z∈𝒮(Q_U_0Z):   f(Q_U_0X'Z) +[R_y- I_Q(X';Z|U_0) ]_+≥ f(Q_U_0X_00Z)  [ I_Q(X';Z|U_0) - R_y]_+
       ≤[ I_Q(X_00;Z|U_0) - R_y]_+ ,

since the constraint is satisfied for Q_X_00|U_0Z∈𝒮(Q_U_0Z). 


On the other hand, if s_1(Q_U_0X_00Z) =  s_0(Q_U_0Z), which is given by (<ref>), we have

    s_0(Q_U_0Z)    =   R_y +  f(Q_U_0X̃Z) - I_Q(X̃;Z|U_0) ,

where we have denoted the maximizer of (<ref>) by Q_X̃|U_0Z, for which I_Q(X̃;Z|U_0) ≤ R_y must be satisfied. 
Next, we upper bound the minimum defining E_1(s_0(Q_U_0Z), Q_U_0Z) by using the same empirical distribution which is the maximizer of the right hand side of the constraint, for which the constraint becomes an exact equality:

    E_1(s_0(Q_U_0Z), Q_U_0Z) 
       = min_ Q_X'|U_0Z∈𝒮(Q_U_0Z):   f(Q_U_0X'Z) +[R_y- I_Q(X';Z|U_0) ]_+≥ s_0(Q_U_0Z)  [ I_Q(X';Z|U_0) - R_y]_+
       = min_ Q_X'|U_0Z∈𝒮(Q_U_0Z):   f(Q_U_0X'Z) +[R_y- I_Q(X';Z|U_0) ]_+≥ f(Q_U_0X̃Z) + R_y  - I_Q(X̃;Z|U_0)  [ I_Q(X';Z|U_0) - R_y]_+
       ≤[ I_Q(X̃;Z|U) - R_y]_+ =  0,

where the last equality is due to the constraint I_Q(X̃;Z|U) ≤ R_y. 

Combining the last two upper bounds, we get 

    E_1(s_1(Q_U_0X_00Z), Q_U_0Z) 
       ≤[ I_Q(X_00;Z|U_0) - R_y]_+,

and therefore

    E_2(s_1(Q_U_0X_00Z), Q_Z)  
    ≤  I_Q(U_0;Z)  +  [ I_Q(X_00;Z|U_0) - R_y]_+,

completing the proof of Lemma 3. 






 §.§ Analysis for a General Suboptimal Decoding Metric and a Direct Part

Let us now derive the exact random coding error exponent of the following suboptimal bin index decoder:

    ĩ() = *arg max_0 ≤ i ≤ M_z-1{max_0 ≤ j ≤ M_y-1 f(Q_U_iX_ijZ) }  ,

and assume, as before, that the function f is upper bounded by Δ.  

To present the formula of Ẽ_z(R_y, R_z), the error exponent of (<ref>), we first need a few new definitions. We first define

    Ẽ_1(t, Q_UZ)  =  min_Q_X|UZ∈𝒮(Q_UZ){ [ I_Q (X;Z|U) - R_y]_+: f(Q_UXZ) ≥ t  },

where t is an arbitrary real number. Next, for a given Q_Z, define

    Ẽ_2(t, Q_Z)  =  min_Q_U|Z∈𝒮(Q_Z) [  I_Q (U;Z) +  Ẽ_1(t, Q_UZ)  ].

Finally, let

    t_0(Q_U_0Z) = max_{ Q_X|U_0Z∈𝒮(Q_U_0Z): I_Q (X;Z|U_0) ≤ R_y}   f(Q_U_0XZ) ,

and

    t_1(Q_U_0X_00Z) = max{ t_0(Q_U_0Z), f(Q_U_0X_00Z)  }.

The error exponent of (<ref>) is given in the following lemma. 

Lemma 4. Under the assumptions of Section 2, 

    Ẽ_z(R_y, R_z) = min_Q_Z|U_0X_00{ D(Q_Z|U_0X_00||W_Z|X_00| P_U_0X_00  ) +   [ Ẽ_2(t_1(Q_U_0X_00Z), Q_Z) - R_z]_+},

where (U_0,X_00) is a replica of (U,X), i.e., P_U_0X_00 = P_UX. 



Proof. The average probability of error, associated with (<ref>), is given by

    P_e^*≐𝔼[ min{ 1, M_z·𝔼( min[ 1, M_y·Pr{   f(Q_U_1X_10Z)  ≥max_∈𝒞_0  f(Q_U_0XZ)   }]  )  }]   ,

where the inner expectation is w.r.t. the randomness of 𝐔_1, the outer expectation is w.r.t. the randomness of 𝐔_0, 𝒞_0 and 𝐙, the latter being the channel output in response to 𝐗_00. 

To see why this is true, observe that the average error probability, P̅_e(R_y,R_z,n), associated with (<ref>), is defined as 

    P̅_e(R_y,R_z,n)  
       △=1/M_y M_z∑_i=0^M_z-1∑_j=0^M_y-1Pr{⋃_l ≠ i⋃_k{ f(Q_U_lX_lkZ)  ≥max_∈𝒞_i  f(Q_U_iXZ)  | 𝐗_ij sent}}

where Pr{·} pertains to the randomness of the codebook as well as that of the channel output given its input. 
We define the following unions of events                                      

    𝒢△=⋃_l=1^M_z-1𝒢_l△=⋃_l=1^M_z-1⋃_k=0^M_y-1𝒢_lk△=⋃_l=1^M_z-1⋃_k=0^M_y-1{ f(Q_U_lX_lkZ)  ≥max_∈𝒞_0 f(Q_U_0XZ)  } .



Define 

    t  △=max_∈𝒞_0   f(Q_U_0XZ)  .

The probability of 𝒢_lk, conditioned on 𝐔_l, is given by

    Pr(𝒢_lk | 𝐔_l = ')      △=Pr{ f(Q_U_lX_lkZ)  ≥max_∈𝒞_0 
     f(Q_U_0XZ)  | 𝐔_l = ' }
       =     ∑_{':   f(Q_U'X'Z) ≥ t   } P ( ' | ' ) 
    
    
    
    
    
    
       ≐max_{ Q_X'|U'Z∈𝒮(Q_U'Z) :    f(Q_U'X'Z)  ≥ t  }exp{-n ·  
    I_ Q(X';Z|U')   }
       =   exp{-n ·min_{ Q_X'|U'Z∈𝒮(Q_U'Z) :    f(Q_U'X'Z)  ≥ t  }     I_ Q(X';Z|U')     }
       △=exp{-n ·Ẽ_0(t, Q_U'Z )    },

where the passage from (<ref>) to (<ref>) is due to (<ref>)-(<ref>). For a given 𝐔_l = ', the events {𝒢_lk}_k are all pairwise independent since we have assumed that the various codewords are pairwise conditional independent given the cloud center. Using the exponential tightness of the truncated union bound, we get

    Pr{⋃_k=0^M_y-1𝒢_lk| 𝐔_l = '   }   ≐min{ 1, ∑_k=0^M_y-1Pr(𝒢_lk | 𝐔_l = ')  }
       =   min{ 1, M_y·Pr(𝒢_l,0 | 𝐔_l = ')  }
       ≐min{ 1, e^nR_y·exp{-n ·Ẽ_0(t, Q_U'Z )    }}
       △=exp{-n ·Ẽ_1(t, Q_U'Z  )    }  ,

where

    Ẽ_1(t, Q_U'Z ) =  min_Q_X'|U'Z∈𝒮(Q_U'Z){[ I_ Q(X';Z|U') - R_y]_+:      f(Q_U'X'Z)  ≥ t  }.



Next, we obtain the probability of 𝒢_l by calculating the expectation w.r.t. the randomness of 𝐔_l:

    Pr{𝒢_l}   =  ∑_' ∈𝒯(P_U)  P_U(')  ·Pr{⋃_k=0^M_y-1𝒢_lk| 𝐔_l = '   }
       ≐∑_' ∈𝒯(P_U)    P_U(')  ·exp{-n ·Ẽ_1(t, Q_U'Z )    }
    
    
    
    
    
       ≐exp{-n ·min_{ Q_U'|Z∈𝒮(Q_Z)   }[ I_ Q(U;Z)  +   Ẽ_1(t, Q_U'Z )   ]  }
       △=exp{-n ·Ẽ_2(t, Q_Z )    } ,
 
where the passage from (<ref>) to (<ref>) is due to (<ref>)-(<ref>).
Conditioning on 𝐔_0, 𝒞_0 and 𝐙, the events {𝒢_l} are all pairwise independent since the various cloud centers are all independent. We get

    Pr{⋃_l=1^M_z-1𝒢_l| 𝐔_0, 𝒞_0, 𝐙}   ≐min{ 1, ∑_l=1^M_z-1Pr(𝒢_l | 𝐔_0, 𝒞_0, 𝐙 ) }
       =   min{ 1, (M_z-1) ·Pr(𝒢_1 | 𝐔_0, 𝒞_0, 𝐙 ) }
       ≐min{ 1, e^nR_z·exp{-n ·Ẽ_2(t, Q_Z )    }}
       =   exp{-n ·[  Ẽ_2(t, Q_Z )  - R_z]_+} .

Finally, we have that

    P̃_e   =   𝔼[ exp{-n ·[  Ẽ_2(T, Q_Z )  - R_z]_+}]  ,

where the expectation is taken w.r.t. the randomness of 

    T  =   max_∈𝒞_0   f(Q_U_0XZ)  ,

and the randomness of Q_Z and U_0, the correct cloud center. 
This expectation will be taken in two steps, first, over the randomness of {𝐗_0,1,...,𝐗_0,(M_y-1)}, while 𝐗_00=_00, 𝐔_0=_0 and 𝐙= are held fixed, and then - over the randomness of 𝐗_00, 𝐔_0 and 𝐙. Let _00, _0 and  be given and let ϵ > 0 be arbitrarily small. Then,

    P̃_e( _00, _0,   )     △=𝔼{  e^-n [ Ẽ_2(T, Q_Z ) - R_z]_+|  𝐗_00=_00, 𝐔_0=_0, 𝐙=}
       ≤∑_iPr{  iϵ≤  T  < (i+1)ϵ|  𝐗_00=_00, 𝐔_0=_0, 𝐙=}
                            ×exp{ -n [ Ẽ_2(iϵ, Q_Z ) - R_z]_+}   ,

where i ranges from 1/ϵ f(Q_U_0X_00Z  ) to Δ /ϵ.
Now,  

    T  =   max{  f(Q_U_0X_00Z  )  ,  max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  ) }.

On the one hand, we have:

    Pr{max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  )  ≥   t   }   = Pr{⋃_1 ≤ j ≤ M_y-1{  f(Q_U_0X_0jZ  )  ≥   t   }}
       ≐min{1,  (M_y - 1)  ·Pr{  f(Q_U_0X_01Z  )  ≥  t }}
       ≐min{1,  e^nR_y·exp{-n ·Ẽ_0(t, Q_U_0Z) }}
       =     exp{ -n [ Ẽ_0(t, Q_U_0Z) - R_y ]_+}
       =     exp{ -n ·Ẽ_1(t, Q_U_0Z)     } .

On the other hand,

    Pr{max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  )  <   t   }   =   Pr{⋂_1 ≤ j ≤ M_y-1 {  f(Q_U_0X_0jZ  )  <   t   }}
       =      [  Pr{  f(Q_U_0X_01Z  )  <   t   }] ^M_y - 1
       ≐ [ 1  -     e^-n ·Ẽ_0(t, Q_U_0Z)]  ^  e^nR_y
       =    exp{      e^nR_y·ln [ 1 -  e^-n ·Ẽ_0(t, Q_U_0Z)]  }
       ≐exp{  -   e^n · [  R_y -  Ẽ_0(t, Q_U_0Z) ]   }
       ≐{[                     0,  R_y >  Ẽ_0(t, Q_U_0Z);                     1, R_y <  Ẽ_0(t, Q_U_0Z), ].

which can also be written as:
 
    Pr{max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  )  <   t   }≐ℐ{  R_y <  Ẽ_0(t, Q_U_0Z)  }    .

Let us now find the minimum t for which the value of this indicator function is unity. The condition is equivalent to

    min_ Q_X'|U_0Z∈𝒮(Q_U_0Z) max_0 ≤ a < ∞{   I_Q(X';Z|U_0)  + a  [t- f(Q_U_0X'Z) ]     }≥   R_y ,

or

    ∀Q_X'|U_0Z∈𝒮(Q_U_0Z)  ∃ a ∈ [0, ∞ ):     I_Q(X';Z|U_0)  + a  [ t- f(Q_U_0X'Z) ]    ≥   R_y ,

or

    ∀ Q_X'|U_0Z∈𝒮(Q_U_0Z)  ∃ a ∈ [0, ∞ ):        t ≥   f(Q_U_0X'Z) + 1/a( R_y - I_Q(X';Z|U_0) )  ,

or, equivalently, 

    t      ≥max_ Q_X'|U_0Z∈𝒮(Q_U_0Z) min_0 ≤ a < ∞[    f(Q_U_0X'Z)  + 1/a( R_y -  I_Q(X';Z|U_0) )   ]  
       =   max_ Q_X'|U_0Z∈𝒮(Q_U_0Z) [ f(Q_U_0X'Z)  +       {[                 0     ,      R_y≥ I_Q(X';Z|U_0);                  -  ∞ , R_y    <  I_Q(X';Z|U_0) ].    ]   
       =  max_{ Q_X'|U_0Z∈𝒮(Q_U_0Z):   I_Q(X';Z|U_0) ≤ R_y}    f(Q_U_0X'Z)     
       △=    t_0(  Q_U_0Z   ).

Thus, in summary, we have
 
    Pr{   t  ≤max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  )  ≤   t+ϵ}≐{[                          0 ,  t <t_0(  Q_U_0Z   ) - ϵ;      e^-n ·Ẽ_1(t, Q_U_0Z )       ,  t ≥ t_0( Q_U_0Z ) ].

Then, the expected error probability w.r.t. {𝐗_0,1,...,𝐗_0,(M_y-1)} yields

    P̃_e( _00, _0,   )   
            ≐∑_iPr{ iϵ≤max_1 ≤ j ≤ M_y-1  f(Q_U_0X_0jZ  )    <         (i+1)ϵ}
           ×exp{ -n [ Ẽ_2(max{f(Q_U_0X_00Z), iϵ}, Q_Z) - R_z]_+}
       ≐∑_i ≥ t_0(Q_U_0Z) / ϵexp{-n Ẽ_1(iϵ, Q_U_0Z)  }
           ×exp{ -n [ Ẽ_2(max{f(Q_U_0X_00Z), iϵ}, Q_Z) - R_z]_+}  .

Since the dominant contribution to the sum over i is due to the term i = t_0(Q_U_0Z) / ϵ (by the non-decreasing monotonicity of the functions Ẽ_1(·, Q_U_0Z ) and Ẽ_2(·, Q_Z )), we obtain
 
    P̃_e( _00, _0,  )     ≐exp{-n [ Ẽ_2(max{ t_0(Q_U_0Z ), f(Q_U_0X_00Z)  }, Q_Z) - R_z]_+}
       △=exp{-n [ Ẽ_2( t_1(Q_U_0X_00Z) , Q_Z) - R_z]_+}.

Now, after taking the expectation w.r.t. the joint distribution of (𝐔_0,  𝐗_00, 𝐙), we get

    Ẽ_z(R_y, R_z) = min_Q_Z|U_0X_00{ D(Q_Z|U_0X_00||W_Z|X_00| P_U_0X_00  ) +   [ Ẽ_2(t_1(Q_U_0X_00Z), Q_Z) - R_z]_+},

and the proof of Lemma 4 is complete.  

Let us now select

    f(Q_UXZ) =
    I_Q(U;Z)  + [ I_Q(X;Z|U) - R_y]_+.

We show that (<ref>) achieves the maximum of E_2(s_1(Q_U_0X_00Z), Q_Z), as given by Lemma 3, and therefore, this decoder has the same error exponent as that of the optimal decoder. First, the threshold t_0(Q_U_0Z) can be easily simplified as

    t_0(Q_U_0Z)      =  max_{ Q_X|U_0Z∈𝒮(Q_U_0Z): I_Q (X;Z|U_0) ≤ R_y}  f(Q_U_0XZ)  
       =  max_{ Q_X|U_0Z∈𝒮(Q_U_0Z): I_Q (X;Z|U_0) ≤ R_y}{ I_Q(U_0;Z)  + [ I_Q(X;Z|U_0) - R_y]_+}
       =  I_Q(U_0;Z)  +  max_{ Q_X|U_0Z∈𝒮(Q_U_0Z): I_Q (X;Z|U_0) ≤ R_y}  [ I_Q(X;Z|U_0) - R_y]_+
       =  I_Q(U_0;Z) .

Now, t_1(Q_U_0X_00Z) is given by 

    t_1(Q_U_0X_00Z)    = 
     max{ I_Q(U_0;Z),   I_Q(U_0;Z)  + [ I_Q(X_00;Z|U_0) - R_y]_+}
       = I_Q(U_0;Z)  + [ I_Q(X_00;Z|U_0) - R_y]_+.

In general, the constraint of the inner minimization problem defining Ẽ_2(t_1(Q_U_0X_00Z), Q_Z) is given by

    f(Q_UXZ)  ≥  t_1(Q_U_0X_00Z),

which can now be written as

    I_Q(U;Z)  + [ I_Q(X;Z|U) - R_y]_+≥ I_Q(U_0;Z)  + [ I_Q(X_00;Z|U_0) - R_y]_+,
 
or simply by f(Q_UXZ)  ≥ f(Q_U_0X_00Z). Eventually, we have the following

    Ẽ_2(t_1(Q_U_0X_00Z), Q_Z) 
       =   min_Q_UX|Z∈𝒮(Q_Z):  f(Q_UXZ)  ≥ f(Q_U_0X_00Z)    f(Q_UXZ)     
       = I_Q(U_0;Z)  + [ I_Q(X_00;Z|U_0) - R_y]_+,

which is the same expression as on the right hand side of (<ref>).










§ GALLAGER-STYLE LOWER BOUNDS

In this section, we prove Theorem 5. 



 §.§ Derivation of eq. (<ref>)

We start by changing the clipping operator to a maximization problem and using convexity properties to change the order of the maximization and the minimization:

    Ê_y,1( R_y ) 
       △=min_ V {  D( V  W |  P   )  + [ I(X;Y|U) - R_y]_+}
       =  min_ V {  D( V  W |  P   )  +  max_ρ∈ [0,1] {ρ·[ I(X;Y|U) - R_y] }}
       =  max_ρ∈ [0,1] { - ρ R_y  +  min_ V {  D( V  W |  P   )  +   ρ·  I(X;Y|U)  }}.

Next,

    min_ V {  D( V  W |  P   )  +   ρ·  I(X;Y|U)  }
       = min_ V,Q {∑_x,uP(x,u)∑_y V(y|x,u)logV(y|x,u)/W(y|x)
                                       + ρ∑_x,u,y P(x,u)V(y|x,u) logV(y|x,u)/Q(y|u)}
       = min_ V,Q {∑_x,u,y P(x,u)V(y|x,u) 
     [  logV(y|x,u)/W(y|x)+ ρlogV(y|x,u)/Q(y|u)]  }
       = min_ V,Q {∑_x,u,y P(x,u)V(y|x,u) 
       log[ V^1+ρ(y|x,u)/W(y|x)Q^ρ(y|u)]  }.

First, we minimize over the auxiliary channel V. Holding the auxiliary channel Q fixed, and differentiating w.r.t. V(y|x,u), we find that the minimizing distribution is given by

    V^*(y|x,u) =  W^1/1+ρ(y|x)Q^ρ/1+ρ(y|u) /∑_y' W^1/1+ρ(y'|x)Q^ρ/1+ρ(y'|u) .

Substituting it back into (<ref>) and summing over y, we get that

    min_ Q {∑_x,u,y   P(x,u)V^*(y|x,u) 
       log[  [V^*(y|x,u)]^1+ρ/W(y|x)Q^ρ(y|u)]  }
       =  min_ Q { -(1+ρ) ∑_x,u P(x,u) 
       log[ ∑_y W^1/1+ρ(y|x)Q^ρ/1+ρ(y|u)  ]  }
       =  min_ Q { -(1+ρ) ∑_u P(u)  ∑_x P(x|u) 
       log[ ∑_y W^1/1+ρ(y|x)Q^ρ/1+ρ(y|u)  ]  }
       ≥min_ Q { -(1+ρ) ∑_u P(u)   
       log[ ∑_x P(x|u) ∑_y W^1/1+ρ(y|x)Q^ρ/1+ρ(y|u)  ]  },

where inequality (<ref>) is due to Jensen's inequality. Next, we minimize the lower bound over Q. Differentiating the last expression w.r.t. Q(y|u), we find that the minimizing distribution is given by

    Q^*(y|u) = [ Φ(u,y,ρ) ]^1+ρ/∑_y'[ Φ(u,y',ρ) ]^1+ρ.
 
Substituting (<ref>) into (<ref>), we get

    -(1+ρ) ∑_u P(u)   
       log[ ∑_x P(x|u) ∑_y W^1/1+ρ(y|x)[Q^*(y|u)]^ρ/1+ρ] 
       = -(1+ρ) ∑_u P(u)   
      log[ ∑_x P(x|u)  ∑_y W^1/1+ρ(y|x) [ Φ(u,y,ρ) ]^ρ/{∑_y'[ Φ(u,y',ρ) ]^1+ρ}^ρ/1+ρ]   
       = -(1+ρ) ∑_u P(u)   
       log[    ∑_y(  Φ(u,y,ρ)  ·[ Φ(u,y,ρ) ]^ρ) /{∑_y'[ Φ(u,y',ρ) ]^1+ρ}^ρ/1+ρ] 
       = -(1+ρ) ∑_u P(u)   
       log[  ∑_y[ Φ(u,y,ρ) ]^1+ρ/{∑_y'[ Φ(u,y',ρ) ]^1+ρ}^ρ/1+ρ]  
       = -(1+ρ) ∑_u P(u)   
       log[  {∑_y[ Φ(u,y,ρ) ]^1+ρ}^1/1+ρ]   
       = -∑_u P(u)   
       log{∑_y[ Φ(u,y,ρ) ]^1+ρ}  ,

which completes the proof of eq. (<ref>).  






 §.§ Derivation of eq. (<ref>)


Similarly as in (<ref>)-(<ref>),

    Ê_y,2( R_y, R_z )  
       △=min_ V {  D( V  W |  P   )  + [ I(U;Y) + [ I(X;Y|U)  -  R_y]_+ - R_z]_+}
       =  min_ V {  D( V  W |  P   )  +  max_μ∈ [0,1] {μ·[ I(U;Y) + max_ρ∈ [0,1] {ρ·[ I(X;Y|U) - R_y] } - R_z] }}
       =  min_ V {  D( V  W |  P   )  +  max_μ∈ [0,1] max_ρ∈ [0,1] {μ·[ I(U;Y) - R_z]+   μρ·[ I(X;Y|U) - R_y]   }}
       =  min_ V {  D( V  W |  P   )  +  max_μ∈ [0,1] max_λ∈ [0,μ] {μ·[ I(U;Y) - R_z]+   λ·[ I(X;Y|U) - R_y]   }}
       =  max_μ∈ [0,1] max_λ∈ [0,μ] { - λ R_y - μ R_z  +  min_ V {  D( V  W |  P   )  +  μ·  I(U;Y) + λ·  I(X;Y|U)  }}.

Now, for the inner-most minimization,

    min_ V {  D( V  W |  P   )  +  μ·  I(U;Y) + λ·  I(X;Y|U) }
       = min_ V,Q,T {∑_x,uP(x,u)∑_y V(y|x,u)logV(y|x,u)/W(y|x)
                      
    +   μ∑_x,u,y P(x,u)V(y|x,u) logQ(y|u)/T(y) + λ∑_x,u,y P(x,u)V(y|x,u) logV(y|x,u)/Q(y|u)}
       = min_ V,Q,T {∑_x,u,y P(x,u)V(y|x,u) 
     [  logV(y|x,u)/W(y|x)+ μlogQ(y|u)/T(y) + λlogV(y|x,u)/Q(y|u)]  }
       = min_ V,Q,T {∑_x,u,y P(x,u)V(y|x,u) 
       log[ V^1+λ(y|x,u)/W(y|x) T^μ(y) Q^λ - μ(y|u)]  }.

First, we minimize over V. Holding Q and T fixed, and differentiating w.r.t. V(y|x,u), we find that the minimizing V is given by

    V^*(y|x,u) =  W^1/1+λ(y|x) T^μ/1+λ(y) Q^λ - μ/1+λ(y|u) /∑_y' W^1/1+λ(y'|x) T^μ/1+λ(y') Q^λ - μ/1+λ(y'|u) .

Substituting (<ref>) into (<ref>) and summing over y, we get

    min_ Q,T {∑_x,u,y P(x,u)V^*(y|x,u) 
       log[  [V^*(y|x,u)]^1+λ/W(y|x) T^μ(y) Q^λ - μ(y|u)]  }
       =  min_ Q,T { -(1+ λ) ∑_x,u P(x,u) 
       log[ ∑_y W^1/1+λ(y|x) T^μ/1+λ(y) Q^λ - μ/1+λ(y|u)  ]  }
       =  min_ Q,T { -(1+ λ) ∑_u P(u)  ∑_x P(x|u) 
       log[ ∑_y W^1/1+λ(y|x) T^μ/1+λ(y) Q^λ - μ/1+λ(y|u)  ]  }
       ≥min_ Q,T { -(1+ λ) ∑_u P(u)   
       log[ ∑_x P(x|u) ∑_y W^1/1+λ(y|x) T^μ/1+λ(y) Q^λ - μ/1+λ(y|u)  ]  },

where (<ref>) is due to Jensen's inequality. Next, we minimize the lower bound over Q, while holding T fixed. Differentiating the last expression w.r.t. Q(y|u), we find that the minimizing Q is given by

    Q^*(y|u) = [ T^μ/1+λ(y)  ∑_x  P(x|u)  W^1/1+λ(y|x) ]^1+ λ/1 + μ/∑_y'[ T^μ/1+λ(y') ∑_x'  P(x'|u)  W^1/1+λ(y'|x') ]^1+ λ/1 + μ .
 
Substituting into (<ref>), we have

    min_ T {  -(1+ λ) ∑_u P(u)   
       log[ ∑_x P(x|u) ∑_y W^1/1+λ(y|x) T^μ/1+λ(y) [Q^*(y|u)]^λ - μ/1+λ]   }
       =  min_ T    - (1+ λ) ∑_u P(u)   
       log[ ∑_x P(x|u)  . 
                              . ×∑_y W^1/1+λ(y|x) T^μ/1+λ(y) [ T^μ/1+λ(y)  Φ(u,y,λ) ]^1+ λ/1 + μ·λ - μ/1+λ/{∑_y'[ T^μ/1+λ(y') Φ(u,y',λ) ]^1+ λ/1 + μ} ^λ - μ/1+λ] 
       = min_ T   -(1+ λ) ∑_u P(u)    
       log[  ∑_y[  T^μ/1+λ(y)  Φ(u,y,λ)  ] ·[  T^μ/1+λ(y)  Φ(u,y,λ)  ]^λ - μ/1+μ/{∑_y'[ T^μ/1+λ(y') Φ(u,y',λ) ]^1+ λ/1 + μ} ^λ - μ/1+λ]  
       = min_ T   -(1+ λ) ∑_u P(u)   
       log[  ∑_y[  T^μ/1+λ(y)  Φ(u,y,λ) ]^ 1 + λ/1+μ/{∑_y'[ T^μ/1+λ(y') Φ(u,y',λ) ]^1+ λ/1 + μ} ^λ - μ/1+λ] 
       = min_ T   -(1+ λ) ∑_u P(u)   
       log[    {∑_y[ T^μ/1+λ(y) Φ(u,y,λ) ]^1+ λ/1 + μ} ^ 1 + μ/1+λ]   
       = min_ T   -(1+ μ ) ∑_u P(u)   
       log[  ∑_y[ T^μ/1+λ(y) Φ(u,y,λ) ]^1+ λ/1 + μ]    
       = min_ T   -(1+ μ ) ∑_u P(u)   
       log[  ∑_y   T^μ/1+μ(y)  [ Φ(u,y,λ) ]^1+ λ/1 + μ]    
       ≥min_ T   -(1+ μ )    
       log[ ∑_u P(u)   ∑_y   T^μ/1+μ(y)  [  Φ(u,y,λ) ]^1+ λ/1 + μ] .

Next, we minimize over T. Differentiating w.r.t. T(y), we get

    T^*(y) = {∑_u P(u)  [   Φ(u,y,λ) ]^1+ λ/1 + μ}^1 + μ/∑_y'{∑_u' P(u')  [   Φ(u',y',λ) ]^1+ λ/1 + μ}^1 + μ .
 
Substituting into (<ref>), we finally get

    -(1+ μ )    
       log[ ∑_u P(u)   ∑_y   [T^*(y)]^μ/1+μ[  Φ(u,y,λ) ]^1+ λ/1 + μ]  
       =  -(1+ μ )    
       log[ ∑_u P(u)   ∑_y[  Φ(u,y,λ) ]^1+ λ/1 + μ.       
                                                   .  ×{∑_ũ P(ũ)  [   Φ(ũ,y,λ) ]^1+ λ/1 + μ}^μ/{∑_y'{∑_u' P(u')  [   Φ(u',y',λ) ]^1+ λ/1 + μ}^1 + μ} ^μ/1+μ] 
       =  -(1+ μ )    
       log[     ∑_y( {∑_u P(u)  [   Φ(u,y,λ) ]^1+ λ/1 + μ}·{∑_ũ P(ũ)  [  Φ(ũ,y,λ) ]^1+ λ/1 + μ}^μ) /{∑_y'{∑_u' P(u')  [ Φ(u',y',λ) ]^1+ λ/1 + μ}^1 + μ} ^μ/1+μ] 
       =  -(1+ μ )    
       log[   ∑_y{∑_u P(u)  [   Φ(u,y,λ) ]^1+ λ/1 + μ}^1 +  μ/{∑_y'{∑_u' P(u')  [  Φ(u',y',λ) ]^1+ λ/1 + μ}^1 + μ} ^μ/1+μ] 
       =  -(1+ μ )    
       log{∑_y{∑_u P(u)  [  Φ(u,y,λ) ]^1+ λ/1 + μ}^1 + μ} ^1/1+μ
       =     
     -  log∑_y{∑_u P(u)  [  Φ(u,y,λ) ]^1+ λ/1 + μ}^1 + μ.
 
Hence, (<ref>) is now proved, as well as the lower bound given in (<ref>). 








§ ANALYZING THE GALLAGER-STYLE LOWER BOUNDS





 §.§ A Study for E_y,1(R_y)






As in the single user case, we expect to find a critical rate and a maximal rate. By maximal rate, that will be denoted by R_max, 
we mean sup{R_y:   E_y,1(R_y)>0 }. 
By critical rate, to be denoted by R_, we mean the boundary between the range where E_y,1(R_y) is affine and the range where it is curvy.


Let 

    E_y,1(R_y) = max_ρ∈ [0,1] { E_0(ρ)  - ρ R_y} ,

where we have defined

    E_0(ρ) =  - ∑_u P(u) log∑_y[ ∑_x P(x|u)W^1/1+ρ(y|x)     ]^1+ρ.

Setting the partial derivative of the bracketed part of (<ref>) equal to 0, we get

    R_y =  ∂ E_0(ρ)/∂ρ .

Following the same considerations as in <cit.>, if some ρ∈ [0,1] satisfies (<ref>), then it must maximize (<ref>). It turns out that a solution to (<ref>) exists if

    .∂ E_0(ρ)/∂ρ |_ρ=1≤  R_y≤.∂ E_0(ρ)/∂ρ |_ρ=0 .

In this range, it is convenient to use (<ref>) to relate E_y,1(R_y) and R_y parametrically as functions of ρ. For the interval 0 ≤ρ≤ 1, this gives

    E_y,1(R_y)    =   E_0(ρ)  - ρ·∂ E_0(ρ)/∂ρ    ,  
    
    R_y   =  ∂ E_0(ρ)/∂ρ .

For R_y < ∂ E_0(ρ) / ∂ρ |_ρ = 1, the parametric equations are not valid. In this case, the maximum occurs at ρ = 1. Thus, E_y,1(R_y) is affine with slope -1:

    E_y,1(R_y)    =   E_0(1)  -  R_y,

where 

    E_0(1) =  - ∑_u P(u) log∑_y[ ∑_x P(x|u) √( W(y|x) )]^2.

Now, we can find R_max and R_, which are given by the right-most side and the left-most side of (<ref>), respectively. Differentiating E_0(ρ) w.r.t. ρ and substituting ρ = 0 gives 

    R_max =  .∂ E_0(ρ)/∂ρ |_ρ=0  =  I_P,W(X;Y|U),

where I_P,W(X;Y|U) is the conditional mutual information induced by the channel W(y|x) and the code distribution P(u,x). Next, define 

    F(u,y) =   ∑_x P(x|u) √( W(y|x) )    ,

and 

    G(u,y) =   ∑_x P(x|u) √( W(y|x) )log W(y|x)   .

After some algebra, we find that

    R_ =  .∂ E_0(ρ)/∂ρ |_ρ=1  = - ∑_u P(u) ∑_y[ F^2(u,y) log F(u,y) - 1/2 F(u,y) G(u,y)      ]/∑_y'  F^2(u,y')  .






 §.§ A Study for E_y,2(R_y, R_z)

Let 

    E_y,2(R_y, R_z)  
       = max_μ∈ [0,1] max_λ∈ [0,μ] {   -  log∑_y(  ∑_u P(u)  [ ∑_x P(x|u)W^1/1+λ(y|x)   ]^1+λ/1+μ)^1+μ
                                                                       - λ R_y  -μ R_z}
       = max_μ∈ [0,1] max_s ∈ [0,1] {  -  log∑_y(  ∑_u P(u)  [ ∑_x P(x|u)W^1/1+ s μ(y|x)   ]^1+ s μ/1+μ)^1+μ
                                                                      - s μ R_y  -μ R_z} ,

and define

    E_1(s, μ)    =  -  log∑_y{∑_u P(u)  [ ∑_x P(x|u)W^1/1+s μ(y|x)   ]^1+s μ/1+μ}^1+μ,

such that

    E_y,2(R_y, R_z)  
    = max_μ∈ [0,1] max_s ∈ [0,1] { E_1(s, μ)  - s μ R_y  -μ R_z} .

Setting the partial derivatives of the bracketed part of (<ref>) to zero, we get

    ∂/∂ s  E_1(s, μ )     =   μ R_y
    ∂/∂μ  E_1(s, μ )     = s R_y + R_z  ,

or, equivalently,

    R_y   = 1/μ·∂/∂ s  E_1(s, μ)     
     
    R_z   =  ∂/∂μ  E_1(s, μ)  -  s/μ·∂/∂ s  E_1(s, μ)  .

Now, if some (μ, s) ∈ [0,1]^2 satisfies (<ref>) and (<ref>), we may relate E_y,2(R_y, R_z), R_y and R_z parametrically as functions of s and μ. This gives

    E_y,2(R_y, R_z)    =  E_1(s, μ)  -  μ·∂/∂μ   E_1(s, μ)    
    
    R_y   =  1/μ·∂/∂ s  E_1(s, μ)        
    
    R_z   =  ∂/∂μ   E_1(s, μ)  -   s/μ·∂/∂ s  E_1(s, μ) .

For explicit expressions for the partial derivatives of E_1(s, μ) w.r.t. s and μ, we first define 

    A(y,s,μ)    =   ∑_u P(u)  [ ∑_x P(x|u)W^1/1+s μ(y|x)   ]^1+s μ/1+μ
     
    B(u,y,s,μ)    =   ∑_x P(x|u)W^1/1+s μ(y|x)       
    
    E(u,y,s,μ)    =   ∑_x P(x|u)W^1/1+s μ(y|x)  log W(y|x)       
    
    C(y,s,μ)    =   ∑_u P(u)  [  B(u,y,s,μ)  ]^1+s μ/1+μ( s-1/1+μ·log B(u,y,s,μ) - s/1+s μ·E(u,y,s,μ)/B(u,y,s,μ))  
    
    D(y,s,μ)    =   ∑_u P(u)  [  B(u,y,s,μ)  ]^1+s μ/1+μ(log B(u,y,s,μ) - 1/1+s μ·E(u,y,s,μ)/B(u,y,s,μ)),

and get that the partial derivative w.r.t. s is given by

    ∂/∂ s  E_1(s, μ) =  - μ·∑_y A^μ(y,s,μ)D(y,s,μ) /∑_y' A^1+μ(y',s,μ) ,

and the partial derivatives w.r.t. μ is given by

    ∂/∂μ  E_1(s, μ) =  -  ∑_y A^1+μ(y,s,μ) ·[ log A(y,s,μ) + C(y,s,μ)/A(y,s,μ)] /∑_y' A^1+μ(y',s,μ) .

Consider the rate pair (R_y,R_z) for which both (<ref>) and (<ref>) hold with s=μ=1:

    R_y   =  . ∂/∂ s  E_1(s, 1)  |_s=1
     
    R_y + R_z   =  .  ∂/∂μ  E_1(1, μ)   |_μ=1,

which is the corner point of the affine rate region. As an immediate consequence, due to the monotonicity of E_1, we get that for low rates, i.e., for rate pairs (R_y,R_z) that satisfy 

    R_y≤. ∂/∂ s  E_1(s, 1)  |_s=1   ,

and

    R_y + R_z≤. ∂/∂μ  E_1(1, μ)  |_μ=1,
 
the maximizers are s^*=μ^*=1, and E_y,2(R_y, R_z) is given by

    E_y,2(R_y, R_z) =   E_1(1, 1)  - ( R_y +  R_z )  ,

where

    E_1(1, 1)  =  -  log∑_y{∑_x P(x) √(W(y|x))}^2.

According to (<ref>), we can find the maximal sum-rate in the affine region. Let 

    F(y) =   ∑_x P(x) √( W(y|x) )    ,

and 

    G(y) =   ∑_x P(x) √( W(y|x) )log W(y|x)   .

After some algebra, we find that the maximal sum-rate is given by

    R_y + R_z≤. ∂/∂μ  E_1(1, μ)  |_μ=1   = -  ∑_y[ F^2(y) log F(y) - 1/2 F(y) G(y)      ]/∑_y'  F^2(y')  .



The error exponent E_y,2(R_y, R_z) depends solely on R_z+R_y if and only if the maximizing s ∈ [0,1] is s^*=1. In this case,

    E_y,2(R_y, R_z) 
       = max_μ∈ [0,1] {  -  log∑_y{∑_u P(u)  [ ∑_x P(x|u)W^1/1+ μ(y|x)   ]^1+ μ/1+μ}^1+μ    -  μ R_y  -μ R_z}
       = max_μ∈ [0,1] {  -  log∑_y{∑_u P(u)  ∑_x P(x|u)W^1/1+ μ(y|x)  }^1+μ    -  μ ( R_y  +  R_z )   }
       = max_μ∈ [0,1] {  -  log∑_y{∑_x P(x) W^1/1+ μ(y|x)  }^1+μ    -  μ ( R_y  +  R_z )   },

which means that E_y,2(R_y, R_z) = E_(R_y+ R_z, P_X), i.e., the ordinary random coding error exponent at rate R_y  +  R_z for an i.i.d. drawn code with distribution P_X. Next, we find the rate region for which E_y,2(R_y, R_z) depends solely on R_z+R_y, but it is not affine in the sum-rate. 
Consider the rate pairs (R_y,R_z) for which both (<ref>) and (<ref>) hold with s=1:

    μ R_y   =  . ∂/∂ s  E_1(s, μ)  |_s=1
    
      R_y + R_z   =   ∂/∂μ  E_1(1, μ)    .

Let Γ_S1 denote the curve given by eqs. (<ref>)-(<ref>):

    Γ_S1 = {  (R_y,R_z) |   R_y =  1/μ·. ∂/∂ s  E_1(s, μ)  |_s=1,      R_y + R_z =   ∂/∂μ  E_1(1, μ),      0< μ≤ 1      }.

Now, in the set of (R_y,R_z), with 

    . ∂/∂μ  E_1(1, μ)  |_μ=1≤  R_y + R_z≤. ∂/∂μ  E_1(1, μ)  |_μ=0    ,

and being underneath the curve Γ_S1, the maximizer is s^*=1, and E_y,2(R_y, R_z) is given by (<ref>). Notice that the left-hand-side and the right-hand-side of (<ref>) are expressions for the critical-rate and the maximal-rate for the channel W_1(y|x), respectively, and hence, the latter cannot be smaller than the former.   
Before moving forward, let us obtain a simple information-theoretic expression for the maximal sum-rate. According to the right-hand side of (<ref>), we only have to differentiate E_1(1, μ) w.r.t. μ and then substitute μ=0. We get

    R_y + R_z≤. ∂/∂μ  E_1(1, μ)  |_μ=0 =  I_P_X,W(X;Y)   ,

where I_P_X,W(X;Y) is the mutual information induced by the channel W_1(y|x) and the code distribution P(x). 

Let us now turn to the other extreme, where E_y,2(R_y, R_z) depends solely on R_z. This happens if and only if the maximizing s ∈ [0,1] is s^*=0. In this case,

    E_y,2(R_y, R_z) 
       = max_μ∈ [0,1] {  -  log∑_y{∑_u P(u)  [ ∑_x P(x|u)W(y|x)   ]^1/1+μ}^1+μ     -μ R_z}
       = max_μ∈ [0,1] {  -  log∑_y{∑_u P(u)  V^1/1+μ(y|u)    }^1+μ     -μ R_z},

which means that E_y,2(R_y, R_z) = E_(R_z, P_U), i.e., the ordinary random coding error exponent at rate R_z for an i.i.d. code with distribution P_U, where V is defined to be the equivalent channel from U to Y. The simple explanation for the fact that E_y,2(R_y, R_z) becomes independent of R_y, for high R_y, is that the satellite codewords behave like pure noise. 

Next, we find the region where E_y,2(R_y, R_z) depends solely on R_z. 
Consider the rate pairs (R_y,R_z) for which both (<ref>) and (<ref>) hold with s=0:

    μ R_y   =  . ∂/∂ s  E_1(s, μ)  |_s=0
    
       R_z   =   ∂/∂μ  E_1(0, μ)    ,

Let Γ_S0 denote the curve given by eqs. (<ref>)-(<ref>):

    Γ_S0 = {  (R_y,R_z) |   R_y =  1/μ·. ∂/∂ s  E_1(s, μ)  |_s=0,      R_z =   ∂/∂μ  E_1(0, μ),       0< μ≤ 1      }.

In addition, we have the following corner point for μ = 1: 

    (R̃_y,R̃_z) = (     . ∂/∂ s  E_1(s, 1)  |_s=0,   
           .  ∂/∂μ  E_1(0, μ)  |_μ = 1),

and we use it to define the straight line connecting that corner point to the R_y-axis: 

    Γ̃_S0 = {  (R_y,R_z) |   R_y =  R̃_y,   0 ≤  R_z≤R̃_z},

which is the set of all (R_y,R_z) for which the maximizers are s^*=0 and μ^*=1. 



Let Γ̂_S0 be defined by Γ_S0∪Γ̃_S0. In fact, the curve Γ̂_S0 is the borderline between the region where E_y,2(R_y, R_z) depends on R_y (affine or curvy) and the region where E_y,2(R_y, R_z) is independent of R_y. The set of all (R_y,R_z) that are above the curve Γ̂_S0 defines the region where E_y,2(R_y, R_z) is independent of R_y. In addition, let us obtain a simple informational expression for the maximum of R_z. According to (<ref>), we only have to differentiate E_1(0, μ) w.r.t. μ and then substitute μ=0. We get

    R_z≤. ∂/∂μ  E_1(0, μ)  |_μ=0 =  I_P_U,V(U;Y)   ,

where I_P_U,V(U;Y) is the mutual information induced by the channel {V(y|u)} and {P(u)}. In the region 

    R_z≤. ∂/∂μ  E_1(0, μ)  |_μ=1 ,

the maximizer is μ^* = 1, and E_y,2(R_y, R_z) is affine in R_z and is given by

    E_y,2(R_y, R_z) =   E_1(0, 1)  -  R_z   ,

where

    E_1(0, 1)  =  -  log∑_y{∑_u P(u) √(V(y|u))}^2.



The third region is the set of all (R_y,R_z) for which the maximizing s is in (0,1). In this case, we use (<ref>)-(<ref>), which hold for every s ∈ (0,1) and μ∈ [0,1] such that both (<ref>) and (<ref>) are satisfied.
This region can be devided into two complementary regions. In the first one, the maximizer is μ^* = 1, and E_y,2(R_y, R_z) is affine in R_z and curvy in R_y, while in the second one, the maximizer μ^* is in (0,1), and E_y,2(R_y, R_z) is curvy in both R_z and R_y. The borderline between those two regions is given by the curve

    Γ_μ 1 = {  (R_y,R_z) |   R_y =  ∂/∂ s  E_1(s, 1) ,        sR_y + R_z =  . ∂/∂μ  E_1(s, μ)  |_μ=1  ,      0 ≤ s ≤ 1      }.

For 

    R_z   ≥  I_P_U,V(U;Y)   
    
     R_y + R_z   ≥  I_P_X,W(X;Y)   ,

the maximizers are s^*=μ^*=0, and then E_y,2(R_y, R_z) = 0. 




§ APPENDIX


    


 §.§ Proof of Theorem 3


Regarding decoder (<ref>)-(<ref>), let us select

    f(Q_UXZ) =   I_Q(U;Z)  +  I_Q(X;Z|U) .

We show that (<ref>) achieves the maximum of E_2(s_1(Q_U_0X_00Z), Q_Z), given by Lemma 3, and therefore, the error exponent of this decoder is as large as that of the optimal decoder. First, the threshold s_0(Q_U_0Z) can be easily simplified as

    s_0(Q_U_0Z)      =  R_y + max_{ Q_X|U_0Z∈𝒮(Q_U_0Z):   I_Q(X;Z|U_0) ≤ R_y}[ f(Q_U_0XZ) - I_Q(X;Z|U_0) ] 
       =  R_y + max_{ Q_X|U_0Z∈𝒮(Q_U_0Z):   I_Q(X;Z|U_0)  ≤ R_y}[ I_Q(U_0;Z)  +  I_Q(X;Z|U_0)   - I_Q(X;Z|U_0) ]  
       =  R_y +  I_Q(U_0;Z) ,
  
such that 

    s_1(Q_U_0X_00Z)    = 
     max{ R_y +  I_Q(U_0;Z),  I_Q(U_0;Z)  +   I_Q(X_00;Z|U_0)  }
       =  I_Q(U_0;Z)  +   max{ R_y ,  I_Q(X_00;Z|U_0)  }.

In general, the constraint of the inner minimization problem defining E_2(s_1(Q_U_0X_00Z), Q_Z) is given by

    f(Q_UXZ) +[ R_y - I_Q(X;Z|U) ]_+≥ s_1(Q_U_0X_00Z),

which can now be written as

    I_Q(U;Z)  +   I_Q(X;Z|U) +[ R_y- I_Q(X;Z|U)  ]_+
                                     ≥ I_Q(U_0;Z)  +   max{ R_y ,  I_Q(X_00;Z|U_0)  }.

Substracting R_y from both sides gives

    I_Q(U;Z)  +   I_Q(X;Z|U)  -  R_y  +[ R_y- I_Q(X;Z|U)  ]_+
                                     ≥ I_Q(U_0;Z)  +   max{ 0 ,  I_Q(X_00;Z|U_0)  -  R_y},

or, 

    I_Q(U;Z) + [ I_Q(X;Z|U) - R_y]_+≥  I_Q(U_0;Z)  +  [  I_Q(X_00;Z|U_0)  -  R_y]_+.

Defining D(Q_UXZ) △= I_Q(U;Z) + [ I_Q(X;Z|U) - R_y]_+, we have

    E_2(s_1(Q_U_0X_00Z), Q_Z) 
       =   min_ Q_UX|Z∈𝒮(Q_Z):   D(Q_UXZ)  ≥ D(Q_U_0X_00Z)     D(Q_UXZ)    
       = I_Q(U_0;Z)  +  [  I_Q(X_00;Z|U_0)  -  R_y]_+ ,

which is the same as on the right hand side of (<ref>). 






AA

COVER72
T. M. Cover, “Broadcast channels," IEEE Trans. on Inform. Theory, 
vol. 18, no. 1, pp. 2–14, January 1972.

BERGMANS1
P. P. Bergmans, “Random coding theorem for broadcast channels with degraded components," 
IEEE Trans. on Inform. Theory, vol. IT-19, pp. 197–-207, March 1973. 

BERGMANS2
P. P. Bergmans, “A simple converse for broadcast channels with additive white Gaussian noise," 
IEEE Trans. on Inform. Theory, vol. IT-20, pp. 279-–280, March 1974.

GALLAGER74
R. G. Gallager, “Capacity and coding for degraded broadcast channels," 
Probl. Pered. Inform., vol. 10, no. 3, pp. 3–-14, July–-September 1974; 
translated in Probl. Inform. Transm., pp. 185-–193, July-–September 1974.

KM77
J. Körner and K. Marton, “General broadcast channels with degraded message sets,"
IEEE Trans. on Inform. Theory, vol. IT-23, pp. 60–-64, January 1977. 

CK78
I. Csiszár and J. Körner,
“Broadcast channels with confidential messages," 
IEEE Trans. on Inform. Theory, vol. IT-24, pp. 339-–348, May 1978.

ELGAMAL79
A. El Gamal, “The capacity of a class of broadcast channels," 
IEEE Trans. on Inform. Theory, vol. IT-25, pp. 166-–169, March 1979.

KS80
J. Körner and A. Sgarro, “Universally attainable error exponents for broadcast channels with degraded message sets," IEEE Trans. on Inform. Theory, vol. 26, no.6, pp. 670-–679, November 1980.

KM11
Y. Kaspi and N. Merhav, “Error exponents for broadcast channels with degraded message sets," IEEE Trans. on Inform. Theory, vol. 57, no. 1, pp. 101–123, January 2011.

MERHAV2014
N. Merhav, “Exact random coding error exponents of optimal bin index decoding," IEEE Trans. on Inform. Theory, vol. 60, no. 10, pp. 6024–6031, October 2014.

CK11
I. Csiszár and J. Körner, Information Theory: Coding Theorems for
Discrete Memoryless Systems, Cambridge University Press, 2011.

GAL68
R. G. Gallager, Information Theory and Reliable Communication, New York, Wiley 1968.

SHUL03
N. Shulman, Communication over an Unknown Channel via Common Broadcasting, 
Ph.D. dissertation, Department of Electrical Engineering - Systems, Tel Aviv University, July 2003. http://www.eng.tau.ac.il/∼shulman/papers/Nadav_—PhD.pdf

MERHAV09
 N. Merhav,“Statistical physics and information theory,”  
Foundations and Trends in Communications and Information Theory, vol. 6, nos. 1–2, pp. 1–212, 2009. 


