{'fraction_non_alphanumeric': 0.06475984889368591, 'fraction_numerical': 0.01347164757850133, 'mean_word_length': 3.556233494217284, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimum Trade-offs Between the Error Exponent and the Excess-Rate Exponent of Variable-Rate Slepian-Wolf Coding

We analyze the optimal trade-off between the error exponent and the excess-rate exponent for variable-rate Slepian-Wolf codes. In particular, we first derive upper (converse) bounds on the optimal error and excess-rate exponents, and then lower (achievable) bounds, via a simple class of variable-rate codes which assign the same rate to all source blocks of the same type class. Then, using the exponent bounds, we derive bounds on the optimal rate functions, namely, the minimal rate assigned to each type class, needed in order to achieve a given target error exponent. The resulting excess-rate exponent is then evaluated. Iterative algorithms are provided for the computation of both bounds on the optimal rate functions and their excess-rate exponents. The resulting Slepian-Wolf codes bridge between the two extremes of fixed-rate coding, which has minimal error exponent and maximal excess-rate exponent, and average-rate coding, which has maximal error exponent and minimal excess-rate exponent.


I. INTRODUCTION
The problem of distributed encoding of correlated sources has been studied extensively since the seminal paper of Slepian and Wolf [22]. This paper addresses the case, where a memoryless source {(X i , Y i )} needs to be compressed by two separate encoders, one for {X i } and one for {Y i }. In a nutshell, the most significant result of [22] states that if {Y i } is known at the decoder side, then {X i } can be compressed at the rate of the conditional entropy of {X i } given {Y i }. Since this is the minimal rate even for the case where {Y i } is known also to the encoder, then no rate loss is incurred by the lack of knowledge of {Y i } at the encoder. Early research has focused on asymptotic analysis of the decoding error probability for the ensemble of random binning codes. Gallager [14] has adapted his well known analysis techniques from random channel coding [13,] to the random binning ensemble of distributed source coding. Later, it was shown in [9] and [6] that the universal minimum entropy decoder also achieves the same exponent. Expurgated error exponents were given in [7] assuming optimal decoding (non-universal). The expurgated exponent analysis was then generalized to coded side information in [5] (with linear codes) and [18].
More recently, a simple modification of the random binning scheme was suggested [3], [17] 1 . The idea was that the encoder may inform the decoder about the type class of the source block using a short header, of negligible length. Then, a different code can be used for every type class, and in particular, different rates are possible.
However, in both [3], [17] the average coding rate was the main concern. Since the empirical probability mass function (PMF) of the source tends to concentrate around its true PMF, then in essence, asymptotically, it is only necessary that the rate constraint will be satisfied for the true type class of the source (see [3,Thm. 1]). The average rate constraint will continue to be satisfied even if the rate for other types, distant from the true source type, is arbitrarily large. Naturally, one can increase the rates of these types up to a point in which any further increase does not improve the decoding error exponent.
This motivates us to take a somewhat different approach and address a more refined figure of merit for the rate.
Specifically, we will be interested in the probability that the rate exceeds a certain threshold. Indeed, consider an online compression scheme, in which the codeword is buffered at the encoder before transmitted. If the instantaneous codeword length is larger than the buffer size, then the buffer will overflow. If the decoder is aware of this event (using a dedicated feed-forward channel, e.g.) then this is an erasure event. Thus, it is desirable to minimize this probability, while maintaining some given error probability. In a different case, the buffer length might be larger than the maximal codeword length, but the buffer is also used for other purposes (e.g. sending status data). If the data codewords have priority over all other uses, then it is desirable to minimize the occasions of blocking other usage of the buffer.
In this paper, we analyze the trade-off between excess rate probability and the error probability in the asymptotic regime of large block-length using error exponents. We assume the standard ensemble of random binning and that source blocks from the same type class have the same coding rate. This allows us to find the exact excess rate and error exponents for any given allocation of rate. Then, for every type class, the minimal encoding rate, required to meet a prescribed value of error exponent, is found. The resulting excess rate performance of the system may then be evaluated. Since calculation of both the rate for a given type, and the excess rate exponent, lead to optimization problems without a closed-form solution, we provide alternating minimization algorithms that converge to the optimal solution.
We leave it as an open question whether allocating identical rates to all source blocks in the same type class provides the optimal trade-off between the excess rate probability and error probability.
The outline of the remaining part of the paper is as follows. In Section II, we establish notation conventions and define an ensemble of type-dependent variable-length codes. In Section III, we evaluate the exact random binning error exponent as well as the excess rate exponent for a given rate allocation for source types. Then, in Section IV, we characterize the optimal rate allocation (in a sense that will be made precise), under an average error exponent constraint. An alternating minimization algorithm is suggested for the calculation of the optimal rate, for any given source type class. In Section V, the excess rate exponent is characterized for the optimal rate function and another alternating minimization algorithm is suggested for the excess rate exponent calculation. Finally, Section VI demonstrates the results via a numerical example.

A. 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 subscripted by their dimensions. For example, the random vector X = (X 1 , . . . , X n ), (n positive integer) may take a specific vector value x = (x 1 , . . . , x n ) in X n , the nth order Cartesian power of X , which is the alphabet of each component of this vector.
The source to be compressed will be denoted by the letter P , subscripted by the names of the relevant random variables/vectors and their conditionings, if applicable. We will follow the standard notation conventions, e.g., P X (x), P Y |X (y|x), P XY (x, y) and so on. The arguments will be omitted when we address the entire PMF, e.g. P X , P Y |X and P XY . Similarly, generic sources will be denoted by Q,Q, Q * , and in other forms, again subscripted by the relevant random variables/vectors/conditioning. An exceptional case will be 'hat' notation. For this notation, Q x will denote the empirical distribution of a sequence x ∈ X n , i.e., the vector of relative frequenciesQ x (x) of each symbol x ∈ X in x. The type class of x ∈ X n , which will be denoted by T (x), is the set of all vectors x ′ withQ x ′ =Q x . When we wish to emphasize the dependence of the type class on the empirical distributionQ, we will denote it by T (Q). Similarly, the empirical distribution of a pair of sequences (x, y) will be denoted byQ xy and the joint type class will be denoted by T (x, y). The empirical conditional distribution induced by (x, y) will be denoted byQ x|y (x|y), and the conditional type class, namely, the set {x ′ :Q x ′ y =Q xy }, will be denoted by T (x|y). The set of all type classes of sequences of length n over X will be denoted by P n (X ), and the joint type classes over the Cartesian product alphabet X × Y will be denoted by P n (X × Y). The probability simplex for X will be denoted by S(X ) , and the simplex for the alphabet X × Y will be denoted by S(X × Y). The entropy of the PMF Q will be denoted by H(Q). The average conditional entropy of Q Y |X with respect to (w.r.t.) Q X will be denoted by H(Q Y |X |Q X ) x∈X Q X (x)H(Q Y |X (·|x)). The information divergence between two PMFs P and Q will be denoted by D(P ||Q) and the average divergence between Q Y |X and P Y |X w.r.t. Q X will be denoted by ). In all the information measures above, the PMF may also be an empirical PMF, for example, H(Q x ), D(Q y|x ||P Y |X ) and so on.
The complement of a set A will be denoted by A c , and A will be its closure. P(A) will denote the probability of the event A, and I(A) will denote the indicator function of this event. The expectation operator will be denoted by E PX [·] where, again, the subscript will be omitted if the underlying probability distribution is clear from the context.
The support of a PMF Q X will be denoted by supp(Q X ) {x : Q X (x) = 0} ⊆ X . For two positive sequences, {a n } and {b n } the notation a n . = b n will mean asymptotic equivalence in the exponential scale, that is, lim n→∞ 1 n log( an bn ) = 0. Similarly, a n≤ b n will mean lim sup n→∞ 1 n log( an bn ) ≤ 0, and so on. The function [t] + will be defined as max{t, 0}. Logarithms and exponents will be understood to be taken to the natural base, thus we will use nats for descriptive purposes.

B. System Model
be n independent copies of a pair of random variables (X, Y ). We assume that X ∈ X and Y ∈ Y, where X and Y are finite alphabets, are distributed according to a given PMF P XY (x, y) = P(X = x, Y = y). It is assumed that supp(P X ) = X and that supp(P Y ) = Y, otherwise, remove the irrelevant letters from their alphabet.
A Slepian-wolf (SW) code C n for sequences of length n is defined by an encoder and a decoder where {0, 1} * is the set of all finite length binary strings. The encoder maps a source block x into a binary string f n (x) ∈ {0, 1} * , and the decoder uses both y and f n (x) to obtain a decoded source blockx = g(f (x), y). For b ∈ {0, 1} * , the inverse image of f n is defined as A random ensemble of SW codes is defined by a random sequence of encoders-decoders (F n , G n ) with probability P(F n = f n , G n = g n ). The error probability for a given code C n is denoted by e n (C n ) = P(X = X), and the average error probability over the random ensemble of codes is defined asē n = E [e n (C n )] . The error probability random-binning exponent is defined asĒ The rate of x ∈ X n is defined as r(x) |fn(x)| n where |f n (x)| is the length of f n (x). For a given target rate R, we define the excess rate exponent function as A variable-rate code is termed type-dependent variable-length code, if r(x) depends on x only via its empirical PMF (type class). Namely, for all x,x ∈ X n , and all n, whenQ x =Qx then r(x) = r(x). Throughout, we disregard integer codeword length constraints, as they have negligible effect on the rate, for large n.
We analyze the ensemble performance of type-dependent, variable-length SW codes, that are defined as follows: • Codebook generation: For a given rate function R(Q X ), generate e nR(QX ) bins for every Q X ∈ P n (X ) and map each bin into a different binary string of length n · R(Q X ) nats. Next, assign to each x ∈ X n a bin by independent random selection with a uniform distribution over all the bins of type class T (x). Then, assign an index to each type class Q X ∈ P n (X ). The above data is revealed to both the encoder and the decoder offline.
• Encoding: Upon observing x, determine its type class T (x). Send to the decoder its type index, concatenated with its bin index (for the current type T (x)).
• Decoding: First, recover the type class T (x) of x. Then, we consider two options.
-Maximum likelihood (ML) decoder: Choosex ∈ f −1 n (f n (x)) that maximizes P X|Y (x|y). Since allx ∈ f −1 n (f n (x)) are in the same type class, they have the same probability P X (x), this decoding rule is equivalent to maximizing P Y|X (y|x).

III. EXPONENTS ANALYSIS
It is well known that the ML decoder, which depends on the source statistics P XY , minimizes the error probability.
By contrast, the MCE decoder does not use P XY at all. In the next theorem, we evaluate the random binning error exponent of the ML decoder, and show that the MCE decoder also achieves the same exponent, and thus it is a universal decoder. This exponent was initially derived in [6] (for both decoders), but the proof here is simpler, and also shows that the lower bound on the ML error exponent is tight, for all rates.

Theorem 2.
Let R(Q X ) be a given rate function, and let the ensemble of SW codes be as defined in Section II-B.
Then for both the ML decoder and the MCE decoder, the limit in (4) exists and equals Proof: Suppose that (x, y) was emitted from the source and its joint type is Q XY =Q xy . Let the marginals and conditional types be Q X =Q x , Q Y =Q y , and Q X|Y =Q x|y .
For the ML decoder, let x ∈ X n : P X|Y (x|y) ≥ P X|Y (x|y) .
The conditional error probability, averaged over the random choice of binning is where the first inequality is due to Lemma 19 in Appendix C, and the fact that the bin indices are drawn independently in a given type class, and the second inequality is because for any pair (x, y) ∈ T (x|y), we have thatx ∈ T (x) and that P X|Y (x|y) = P X|Y (x|y).
For the MCE decoder, let Similarly,Π e,u (x, y) P where the first inequality is by the union bound, and the following equality is because the number of sequences in any conditional type that belongs to S u (x, y) is exponentially upper bounded by e nH(QX|Y |QY ) and the number of joint types is polynomial |P n (X × Y)|≤ (n + 1) |X ||Y| .
It can be seen that on the exponential scale, the lower bound onΠ e,o (x, y) and the upper bound onΠ e,u (x, y) are identical. Thus, when taking expectation w.r.t. the i.i.d. source P XY , the resulting asymptotic bounds on the error probability are identical (lower bound for the ML decoder, and upper bound for the MCE decoder). Moreover, since the ML decoder minimizes the error probability, taking expectation w.r.t. P XY we get so the asymptotic average error probability of both the ML decoder and the MCE decoder is where the last inequality is again because |P n (X × Y)|≤ (n + 1) |X ||Y| . Since the optimal value of the minimization problem inside the exponent is clearly finite, and the minimization argument is a continuous function, then Remark 3. The MCE decoder is equivalent to a decoder that estimates the unknown PMF P XY for any candidate source block (generalized likelihood ratio test). Indeed, suppose that the candidate source block is x, the side information is y and (x, y) has the joint type Q XY . The normalized log-likelihood is bounded as and equality is achieved when choosing P XY to be the ML estimate P M L , which equals to the observed empirical PMF, i.e. P M L = Q XY =Q xy . Indeed, the MCE decoder chooses the source block x ∈ X n that minimizes Next, we consider the excess rate exponent.

Theorem 4. For a regular rate function
Proof: The proof is technical and relegated to Appendix B.
It should be mentioned, that the same techniques used in this section also apply to the more general case of SW coding, where the side information is also encoded. In this case, there are two encoders, f n encoding x and f ′ n encoding y, while the central decoder g n now uses both codewords f n (x) and f ′ n (y). Similar encodings may be defined via random binning, and a header including the type for each codeword. Now, two rate functions R X (Q X ) and R Y (Q Y ) may be defined accordingly. The resulting error exponent is given bȳ and the excess rate exponents clearly depend only on marginal types and rate functions. Nonetheless, due to the sum-rate term in the inner minimization, a trickle of coordination is required between the two encoders. Specifically, at least one of the encoders needs to know the current rate (or equivalently, the type class of the current source block) of the other encoder. Moreover, solving the optimization problems needed to determine the optimal rate (cf. next section) requires solving complicated equations. Thus, we do not pursue this direction here.

IV. OPTIMAL RATE FUNCTIONS
For the system described in Section II-B, a good choice of a rate function R(Q X ) would achieve an error exponent requirement E e using a minimal rate, uniformly for all Q X . In this section, we define and characterize the optimal rate function, which achieves a specified target error exponent E e , for a given source P XY .
is said to be optimal if it achieves an error exponent E e , and for every In the next theorem, we give an expression for the optimal rate function. Notice that D(Q X ||P X ) is finite for any Q X , since it was assumed that supp(P X ) = X . Theorem 6. The optimal rate function is Proof: E e no actual constraint is imposed on the rate, and (37) is satisfied even for R(Q X ) = 0. Thus, in this case and then (37) implies that to achieve E e we must have Introducing an auxiliary PMFQ Y and using Lemma 22 (Appendix C) where the last equality is because the value of the inner minimum is finite (as the divergences are non-negative).
The following theorem provides several properties of the optimal rate function R * (Q X , E e ).

Theorem 7.
The optimal rate function R * (Q X , E e ) has the following properties: Algorithm 1 Iterative alternating minimization algorithm for the solution of (42) Input: A source P XY , a type class Q X , and a target error exponent E e . Output: The value of the optimization problem (42) and the optimal solution 2) Iterate over the following steps until convergence: It is evident from Theorem 6 that in order to calculate R * (Q X , E e ), one needs to solve the following optimization problem: Algorithm 1 describes an iterative minimization algorithm for solving this optimization problem, and the next lemma asserts its correctness. For a given 0 ≤ α ≤ 1 andQ Y , we shall use the following definition for a conditional PMF where ψ x is a normalization factor, such that y∈Y Q α Y |X (y|x) = 1 for all x ∈ X . In Algorithm 1 (and other algorithms in this paper), the bisection method (also called binary search) [12, Chapter 9.1] is used to find the root of a monotonic continuous function f in an interval [a, b], where f (a) and f (b) have opposite signs. In any iteration of this well-known method, the current interval is halved, and based on the sign of f in the middle of the interval, the root is known to belong to either the left or right half-interval. The bisection method always converges, but obviously, any other appropriate root finding method (that perhaps converges faster) may be used.

Lemma 8. Algorithm 1 outputs the minimal value and the optimal solution of (42).
Proof: See Appendix B.
Algorithm 2 Computation of optimal rate function R * (Q X , E e ) Input: A source P XY , a type class Q X , and a target error exponent E e . Output: The value of the optimal rate function R * (Q X , E e ).
} using the modification of Algorithm 1 suggested in Lemma 10, and find E e,a from Theorem 7 part 3. Return. Return.
Remark 9. The right limit of the optimal rate function R * (Q X , E e ) at its discontinuity point E e,0 can be easily and from (41) the resulting rate is Namely, the resulting rate is the conditional entropy , for all ǫ > 0, as expected.
Notice that Theorem 7, part 3 implies that for E e > E e,a , the optimal rate function is an affine function of E e with slope 1. Thus, for E e > E e,a a modification of Algorithm 1 can be used to find the optimal rate function in a simpler way. The next Lemma states how to find the optimal optimal solution (Q * Y |X ,Q * Y ) for this case, and then the resulting procedure for calculating the optimal rate function R * (Q X , E e ), for all possible cases of E e , is summarized in Algorithm 2 . The correctness of this algorithm is asserted in Theorem 11.

Lemma 10.
For E e > E e,a , Algorithm 1 converges to the optimal solution (Q Theorem 11. Algorithm 2 returns R * (Q X , E e ).
Proof: See Appendix B.
In Appendix A, we provide two examples for optimal rate functions. Example 17 shows that even in the simple case of a double binary source X = Y = {0, 1}, where P Y |X is a binary symmetric channel, the calculation of the optimal rate function requires the solution of a non-trivial numerical equation. This emphasizes the importance of Algorithm 1. Nonetheless, in Example 18 it is shown that for very weakly correlated sources, an analytic approximation for the optimal rate function is indeed possible, and the resulting expression is provided.

V. EXCESS RATE PERFORMANCE
In this section, we evaluate the excess rate exponent for the optimal rate function R * (Q X , E e ), which we denote is a regular rate function (Theorem 7 part 5), then in essence, Theorem 4 can be used. However, as we have seen, R * (Q X , E e ) is not given analytically, and performing the maximization in (33) directly may be prohibitively complex, especially when |X | is large. Thus, in this section, we describe an indirect method to evaluate E * r (R). Throughout, it is assumed that E e is given and fixed. For a given R, the curve E * r (R) may be characterized by a condition that verifies whether (R, E r ) is either below or above the curve. While verifying such a condition is still difficult for R * (Q X , E e ), it can nonetheless be verified for a surrogate rate functionR(Q X ; R, E r ) which has simpler structure, but also attains (R, E r ). Before going into details we mention few properties of E * r (R).
The excess rate exponent E r (R) for the rate function R(Q X ) has the following properties: Proof: See Appendix B.
Now, for a given R we define the aforementioned surrogate rate function as 2 The exact value of R 0 is immaterial, as if it is chosen properly, it affects neither the error exponent nor the excess rate exponent. A precise condition on R 0 will be stated in the proof of Proposition 14 that will appear in what 2 Notice that the second argument in this rate function is a target rate and excess rate exponent, unlike the optimal rate function R * (QX, Ee) in which the second argument is a target error exponent.
follows. For now, we require that at least Notice that like the optimal rate function,R(Q X ; R, E r ) is also a regular rate function. The next lemma shows that (R, E r ) is achieved simultaneously for both rate functions,R(Q X ; R, E r ) and R * (Q X , E e ).
Lemma 13. The optimal rate function R * (Q X , E e ) achieves the pair (R, E r ) with an error exponent E e iff the rate functionR(Q X ; R, E r ) also achieves (R, E r ) with an error exponent E e .
Proof: We show that (R, E r ) is achievable by both rate functions simultaneously.
(⇐) Assume thatR(Q X ; R, E r ) achieves (R, E r ) with an error exponent E e . Clearly the definition of optimal rate functions imply that R * (Q X , E e ) also achieves (R, E r ).
and this implies thatR(Q X ; R, E r ) also achieves error exponent E e . It is easy to see thatR(Q X ; R, E r ) satisfies the large deviation constraint (R, E r ) directly from its construction and (33).
Thus, for any given (R, E r ) we may construct the properR(Q X ; R, E r ), and check if (R, E r ) is below or above The following proposition states a proper condition.

Proposition 14.
Let and Proof: The sufficient and necessary condition onR(Q X ; R, E r ) to achieve E e in (37) may be restated as For Q X that satisfies D(Q X ||P X ) ≥ E r , we can choose large enough R 0 that satisfies this requirement.
Algorithm 3 Iterative alternating minimization algorithm for calculation of υ(t) Input: A source P XY , a target error exponent E e , a target rate R, a target excess rate E r , and 0 ≤ t ≤ 1. Output: The value of υ(t). 1) InitializeQ Y randomly such that supp(Q Y ) = Y.
2) Iterate over the following steps until convergence: a) If D(Q 0,t X ||P X ) < E r then set λ = 0. Else, use the bisection method to find λ > 0 that satisfies and using Lemma 22, this is equivalent to The minimization problem in (55) is jointly convex in Q X (over the convex set {Q X ∈ S(X ) : The maximization problem is linear in t (over the convex set [0, 1]), and thus trivially concave.
Therefore, we can interchange the maximization and minimizations [21] order to obtain the resulting condition The maximization over t can be performed via a simple line search, over the finite interval [0, 1] (or using more sophisticated methods, e.g., Brent's method [12, Section 10.2]). However, for a given t, υ(t) needs to be found.
Algorithm 3 provides a method to calculate υ(t). The technique is somewhat similar to Algorithm 1, but here an additional optimization is carried over Q X . Its convergence proof is given in the lemma that follows. We shall utilize the the definition in (43) as well as where ψ is a normalization factor.
It can easily be seen that max 0≤t≤1 υ(t) is a non-increasing function of E r . Thus, for any given constraint on E e and target rate R, it is easy to search for E * r (R) = min {E r : (R, E r ) is achievable for E e }, e.g. using a simple bisection algorithm.
For the sake of comparison, we mention fixed-rate coding. In this case, to ensure an error exponent of E e one must for all Q X . Thus, the excess rate exponent is 0 for R < R * max (E e ) and ∞ for R > R * max (E e ).
Remark 16. In many practical cases, there is some uncertainty regarding the source P XY = P X × P Y |X . Clearly, if independence between X and Y is a possible scenario, then in this worst case, the side information Y n is useless (when no feedback link exists). In other cases, it may be known that P XY ∈ F ⊂ S(X × Y) for some family of PMFs F. In this case, a possible requirement is that the rate function R(Q X ) will be chosen to achieve error exponent of E e uniformly for all sources in F. With a slight change and abuse of notation, we define the optimal rate function for the source P XY as R * (Q X , E e ; P XY ) and the optimal rate function for the family F as This maximization is (relatively) easy to perform if, e.g., the conditional probability P Y |X is known exactly, and in addition, a nominalP X is known such that the actual P X satisfies D(P X ||P X ) ≤ U, for some given uncertainty level U > 0 (recall Pinsker's inequality [4, Lemma 11.6.1] and see also the discussion in [19]). Observing (41), it is noticed that R * (Q X , E e ) depends on P X only via D(Q X ||P X ), both as an additive factor and in the constraint set A. Nonetheless, the maximum of R * (Q X , E e ) is obtained when D (Q X ||P X ) is maximized. Thus, to perform that maximization (57), the following optimization problem should be solved for any given Q X . A standard Lagrange method, like the one used in previous sections, results in the solution P * X,α = αP X + (1 − α)Q X , where α is either chosen to satisfy the constraint D(P X ||P * X ) = U or α = 0 (and then the minimum is 0). The value D(Q X ||P * X ) can be substituted into the optimal rate function expression instead of D(Q X ||P X ) in Theorem 6. The calculation of the resulting excess rate exponent curve E * r (R) is more involved, since the minimizer P * X depends on Q X . Nonetheless, if in Proposition 14, we add the dependence in P X to (51), to obtain Γ(t, Q X , Q Y |X , P X ,Q Y ), then we have that Γ is jointly convex function of (Q X , Q Y |X , P X ,Q Y ).
Thus, arguments similar to the ones used in Lemma 15, show that an alternating minimization algorithm can be used, iterating between finding the optimal (Q X , Q Y |X , P X ) for a givenQ Y , and the optimalQ Y for a given (Q X , Q Y |X , P X ) (i.e., in Algorithm 3, P X is optimized after step 2a).

VI. A NUMERICAL EXAMPLE
In this section, we provide a simple numerical example to illustrate the results obtained in previous sections.
Assume the source symbols are generated from the alphabets X = {0, 1} and Y = {0, 1, 2, 3}, where P X is given   by P X (0) = 1 /4 = 1 − P X (1) and P Y |X is given by the following transition probability matrix (59) Figure 1 shows the optimal rate function R * (Q X , E e ) for Q X given by Q X (0) = 0.4 = 1 − Q X (1) as a function of E e . The three parts of the function -zero rate part, a concave part, and an affine part with a unity slope, are evident. Figure 2 shows the optimal rate function R * (Q X , E e ) for all possible types (indexed by Q X (0)) for various values of E e . It can be seen that indeed this optimal function is in the form of a regular rate function. The excess rate exponent is calculated for the optimal rate function R * (Q X , E e = 10 −1 ), and plotted in Figure 3.
Following Remark 16, suppose that P X is not precisely known, but D(P X ||P X ) ≤ U for a nominal PMFP X given byP X (0) = 1 /4 = 1 −P X (1), and uncertainty level of U = 10 −2 . The resulting optimal rate function and excess rate exponents, are also shown in the aforementioned figures.
It can be verified that Figure 2 and Figure 3 are consistent. Indeed, when there is no uncertainty, it can be seen in Figure 2 that when the type is Q X = P X the rate is R * (P X , 10 −1 ) ≈ 0.62 so the excess rate exponent is E * r (0.62) = 0. Then, as Q X (0) increases, the rate also increases, up to its maximal value of R * (Q X , 10 −1 ) ≈ 0.67, for Q X (0) ≈ 0.36. The excess rate exponent is determined by the divergence of this type from the true source P X , and given by E * r (0.67) ≈ D([0.25, 0.75]||[0.36, 0.64]) ≈ 2.8 · 10 −2 . This is the maximal value of E r (R) shown in Figure 3, and for larger rates, clearly E r (R) = ∞. For the case of uncertainty with U = 10 −2 , it should be observed that any source P X with 0.25 ≤ P X (0) ≤ 0.315 satisfies the uncertainty constraint, and such types result E * r (R) = 0. The rate for Q X (0) = 0.315 is R * (Q X , 10 −1 ) ≈ 0.67, which can be seen in Figure 3 as the minimal rate for which E * r (R) > 0. For larger Q X (0) the excess rate is determined by the divergence of Q X w.r.t. the worst source in the family F, namely P * X (0) = 0.315. For example, in the maximal rate of R * (Q X , 10 −1 ) ≈ 0.7 the type is Q X (0) ≈ 0.4 and E * r (0.7) ≈ D([0.315, 0.685]||[0.4, 0.6]) ≈ 1.55 · 10 −2 . For the sake of comparison, we also consider fixed-rate coding. First, notice that from Figure 3 for E e = 10 −1 we have E * r (R = 0.65) = 3.75 · 10 −3 . Second, it can be found that if one uses fixed-rate coding, with R(Q X ) = 0.65 for all Q X then the error exponent achieved is only E e = 0.78 · 10 −1 . Therefore, if the finite excess rate exponent of variable rate coding is tolerated, then this provides an improvement in the error exponent.

Example 17 (Double Binary Source). From the proof of Lemma 8 (Appendix B) we may deduce that the optimal
and using the common denominator of the fractions in the right term we get .

(A.4)
It can be noticed that the denominator does not depend on y and thus . We attempt to solve this equation in the simple case of X = Y = {0, 1}, and P Y |X represents a binary symmetric channel (BSC) with crossover probability ǫ. In this case, (A.5) is given bỹ In the special cases of α = 1 and α = 1 /2 an explicit solution can be found, and it is equal to both for α = 1 and α = 1 /2. However, generally, (A.9) may only be solved numerically. It also evident that even in this simple case, the optimalQ Y is not necessarily uniform (unless for some simple cases such as Q X (0) = Q X (1) = 1 /2 or ǫ = 1 /2).

Example 18 (Very Weakly Correlated Sources). Consider the case of very weakly correlated sources 3 , namely
where for all x ∈ X we have y∈Y ǫ xy = 0 and |ǫ xy |≪ 1 for all (x, y) ∈ (X , Y). Consider again the minimization problem in (40) and notice that if X and Y are independent, then the optimal solution isQ * Y = Q Y |X = P Y for all x ∈ X and both divergences vanish. A continuity argument then implies that for the low dependence case, the two divergences at the optimal solution are close to 0. Therefore, we can use the following Euclidean approximation [10, Theorem 4.1]: For two PMFs P X , Q X such that supp(P x ) = X and Q X ≈ P X we have that Moreover, for another PMFP X , ifP X ≈ P X then which also shows that D(P X ||Q X ) ≈ D(Q X ||P X ). Now, the objective function of the minimization problem can be approximated as and similarly the constraint Q Y |X ∈ A is approximated by The Lagrangian for a givenQ Y (ignoring positivity constraints for the moment) is and equating the derivative to zero in this case is equivalent to Thus, for some λ > 0 It can be easily seen that µ ′ for some α = 1+λ 2+λ , where α is either chosen to satisfy the constraint or α = 1 /2. It is evident that indeed the solution satisfies the positivity constraints. Now, for any given α the resulting value of the optimization problem is and by differentiating w.r.t. someQ Y (y ′ ) for y ′ ∈ Y we have and equating to zero we obtain that the optimal solution is Notice that the optimal solutionQ * Y does not depend on α. Thus, for a given E e ≥ E e,0 the optimal value of α is given by α * ≈ max(α, 1 /2) whereα achieves equality in (A.18), using again (A.14). Then, in the case of very weakly correlated sources, the optimal rate function can be approximated by where α * is given analytically as a function of E e . In addition, similar approximations for the unconstrained Thus, for E e,0 ≤ E e ≤ E e,a we haveα ≤ 1 /2 and by substitutingα in (A.28) we obtain Notice that D(P Y |X ||Q * Y |Q X ) is the mutual information of the joint PMF Q X × P Y |X and thus is a measure of the independence between X and Y . As D(P Y |X ||Q * Y |Q X ) → 0 then X and Y become "more" independent and E e,a → E e,0 . Thus, in the case of a small D(P Y |X ||Q * Y |Q X ), the optimal rate function R * (Q X , E e ) is affine for almost the entire range E e ≥ E e,0 . Indeed, in this case, the main error event is associated with "bad binning", i.e. at least two source blocks of the same type are mapped to the same bin by the random binning procedure.

Proof of Theorem 4: For a target rate R
Because supp(P X ) = X then D(Q X ||P X ) is continuous and finite for all Q X and as n → ∞ Now, for a source block x of type class T (x), the total rate is the sum of the description rate of its type class index and R(Q x ). Using the fact that |P n (X )|≤ (n + 1) |X | for any given ǫ > 0 and similarly Thus, to conclude the proof we show that min QX :R(QX )≥R D(Q X ||P X ) is left continuous as a function of R, since this will imply that when taking ǫ → 0, the upper and lower bounds on E r (R) will coincide.
To show this, let δ > 0 be given. Recall that R(Q X ) is regular, thus there exists V ⊂ S(X ) such that R(Q X ) is continuous in V, and equals a constant R(Q X ) = R 0 , for Q X ∈ V c . Also, since R(Q X ) ≥ 0 and S(X ) is a compact set, then exists a minimizer Q * X ∈ S(X ) for the right hand side of (B.3). For any ǫ > 0 we clearly have To obtain an inequality in the reversed direction, we split the proof into two cases, depending whether Q * X ∈ V or not.
Recall that R(Q X ) is continuous and finite inside the interior of V, and D(Q X ||P X ) is continuous function of Q X . Now, we may define for any Q X ∈ V such that R(Q X ) ≥ R, the closed neighborhood Then, the continuity of both R(Q X ) and D(Q X ||P X ) implies that there exists a closed ball (e.g. in L 1 norm) B(Q X , ρ) with center in Q X and radius ρ > 0 such that B(Q X , ρ) ⊂ D(Q X , R, ǫ). Also, we may define the set where ∂V = V\V is the boundary of V, and for any Q X ∈ V ′ (R) Here too, continuity arguments imply that there exists a closed ball B(Q X , ρ) with center in Q X and radius ρ > 0 and let R ′ max QX ∈U R(Q X ). Then we must have R ′ < R. To see this, assume by contradiction that R ′ = R and let Q X achieve the maximum, namely, R(Q X ) = R. Now, either Q X ∈ V or Q X ∈ ∂V, but both cases lead to contradiction. Indeed, the definition of U , and the fact that for some ρ > 0 we have B(Q X , ρ) ∩ V ⊂ D(Q X , R, ǫ) imply that Q X / ∈ V. Similar arguments show that Q X / ∈ ∂V. Now, consider two sub-cases: since the right minimization is over a smaller set.
2) R ≤ R 0 . Since Q * X is the minimizer for the right hand side of (B.3) then and if we choose ǫ ′ = min{ǫ, R − R ′ } we also have and thus (B.14) Case 2: Q * X ∈ V c . In this case we clearly have R 0 ≥ R. Now, let R sup QX ∈V R(Q X ) and let Q X ∈ V any PMF achieving the supremum. Then we must have that either Q X ∈ ∂V or R < R. To see this, assume by contradiction that both Q X ∈ V and R ≥ R. Recall that V {Q X : D(Q X ||P X ) < d}. This implies that Q * X could be any point on the boundary of V. Now, let (B.15) and since D(Q α X ||P X ) is an increasing function of α (Lemma 20 in Appendix C), then for someα > 1, we have D(Q α X ||P X ) = d and Q α X ∈ ∂V. But this implies that while both R(Qα X ) = R 0 ≥ R and R(Q X ) = R ≥ R we have and this contradicts the optimality of Q * X . Thus, we must have that either Q X ∈ ∂V (for any Q X achieving R) or R < R. Now, we have two sub-cases: 2) Otherwise, suppose Q X ∈ ∂V and R ≥ R. If R > R then similar arguments as before show that this contradicts the optimality of Q * X . If R = R then similar arguments to the ones used in the first case show that for any δ > 0 and small enough ǫ ′ > 0.
To conclude, in any of the two cases, for any given δ > 0 we can find ǫ > 0 such that This means that min QX :R(QX )≥R D(Q X ||P X ) is left continuous as a function of R, and the desired result is obtained.

Proof of Theorem 7:
1) The fact that R * (Q X , E e ) = 0 for E e ≤ E e,0 evident from (35). For E e > E e,0 , notice that if E e > D(Q X ||P X ) then to satisfy (37) for 2) Observing (39), we see that R * (Q X , E e ) equals a linear function of E e (which is a strictly increasing function , which is a non-decreasing function of E e (since as E e gets larger, the infimum is over a larger set).
3) Using (41) we get and for E e > E e,a equality is achieved since Q ′ Y |X ∈ A. 4) From (41), the optimal rate function The objective and constraint functions are jointly convex inQ Y × Q Y |X and for E e ∈ (E e,0 , ∞) the constraint set is feasible. Thus, the conditions of Lemma 21 (Appendix C) are satisfied and R * (Q X , E e ) is concave for E e ∈ (D(Q X ||P X ), ∞).

5) Let
Then clearly R * (Q X , E e ) = 0 for Q X ∈ V c . Also, for any Q X ∈ V there exists a closed neighborhood B of Q X such that B ∈ V. Inside B, the optimal rate R * (Q X , E e ) is given by the second term in (35). In this second term, both the objective and constraint are continuous functions of Q X , and thus R * (Q X , E e ) is continuous for Q X ∈ V.
Proof of Lemma 8: Notice that (42) is an optimization problem over (Q Y |X ,Q Y ) and consider utilizing an alternating minimization algorithm, where for a givenQ Y , the minimizer Q Y |X is found, and vice versa. We divide the rest of the proof into two main parts. In the first part, we prove that the alternating minimization algorithm indeed converges to the optimal solution, and in the second part, we solve the two individual optimization problems (resulting from keeping one of the optimization variables fixed). where P and Q are two positive measures (which may not necessarily sum to 1) over a finite alphabet Z, and P, Q are two convex sets. To prove that alternating minimization algorithm converges for the optimization problem (42), we now show that it can be written in the form of (B.23). The objective function of (42) is given by Thus, if we let Z = X × Y and consider the measures Q XY andQ XY Q Y P Y |X Q X then the objective function is of the form of (B.23). Now, using the definition of the set A, the feasible set for Q XY is which is a convex set. Now using Corollary 23 of Lemma 22 (Appendix C), we have that the feasible region of Q Y can be extended from the simplex S(Y) to the set which is also a convex set. Now, define the feasible set for the variablesQ XY as We show thatS is also a convex set.
Thus, to show thatQ α XY ∈S all is needed to prove is that Q and equating to zero we get Thus, the argument of the logarithm must not depend on x, and this implies that for any x ∈ X such that Q X (x) = 0 we must have where ψ x is a normalization constant, and the definition (43) was used. The value of Q * Y |X for x ∈ X with Q X (x) = 0 is immaterial as it does not affect the optimal value of the objective function. Also, it is evident that the solution Q * Y |X is indeed positive. To find the optimal Q * Y |X we need to choose α in order to satisfy the constraint Q α Y |X ∈ A. For this, the complementary slackness condition [2,Section 5.5.2] implies that α should be chosen either to satisfy and 1 /2 ≤ α ≤ 1, or α = 1 /2 and then To find α that satisfies the complementary slackness condition it is noticed that D(Q α Y |X ||P Y |X |Q X ) is a monotonically decreasing function of α. Indeed, it is easy to see that ifQ Y is initialized such that supp(Q Y ) = supp( x∈X Q X (x)P Y |X (y|x)) then this remains true for all iterations. Then, it follows from Lemma 25 (Appendix C) that for any given x ∈ X such that Q X (x) = 0 we have that D(Q α Y |X (·|x)||P Y |X (·|x)) is a decreasing function of α, and thus their average D(Q α Y |X ||P Y |X |Q X ) is also a decreasing function of α. Thus, if Thus, in the later case, a simple bisection search finds the required α.
Second, assume that Q Y |X is given. The minimizerQ Y can be found using Lemma 22 (Appendix C) to bẽ It is easily seen that Algorithm 1 indeed implements the procedure described in this proof.
Proof of Lemma 10: Using Theorem 7 part 3, for E e > E e,a , it is sufficient to solve the unconstrained minimization problem This is equivalent to setting E e = ∞. Thus, in step 2a of Algorithm 1, we always have and thus we need to set α = 1 /2.

Proof of Theorem 11:
First, consider the case E e,0 < E e ≤ E e,a , and assume that Algorithm 1 has converged is a solution of the unconstrained minimization (B.43). However, since the solution of the unconstrained minimization (B.43) is unique (since its objective function is strictly convex) then implies E e > E e,a , which contradicts the assumption. Now, we can substitute D(Q * Y |X ||P Y |X |Q X ) = E e − D(Q X ||P X ) in (35) to obtain (47).
Second, consider the case E e,a < E e . In this case, the optimal solution is clearly (Q 3) The first statement stems directly from the definition (5). When R(Q X ) is regular, we may use (33). Now, let Q * X be any minimizer of (33), for a given R < R ′ max . We begin with showing that R(Q * X ) = R. Assume by contradiction that R(Q * X ) > R. Since R < R ′ max then arguments used in the proof of Theorem (4) show that Q * X ∈ V. Now, consider Q α,X = (1 − α)P X + αQ * X . (B.45) Since R(Q X ) is continuous in V then intermediate value theorem implies that α < 1 must exist such that R(Q α,X ) = R. Using Lemma (20) we have that D(Q α,X ||P X ) < D(Q * X ||P X ) which contradicts the fact that Q * X is a minimizer of (33). Now, let Q(R) be the collection of all minimizers of (33), such that for all Q X / ∈ Q(R) we have either D(Q X ||P X ) > D(Q * X ||P X ) or R(Q X ) < R. Thus, for any R 1 > R we have 4) The first statement follows from the fact that monotonic functions are continuous almost everywhere. The proof of the second is a part of the proof of Theorem 4.
Proof of Lemma 15: Algorithm 3 is an alternating minimization algorithm, that keeps all variables but one fixed, and optimize over the non-fixed variable. Now, for a given 0 ≤ t ≤ 1, the objective function in (52) is given by The exact same technique which was used in the proof of lemma 8 shows that this optimization problem is of the form (B.23). Thus, an alternating minimization algorithm converges to the optimal solution.
We now turn to the minimization of individual variables, assuming that all other variables are fixed, for a given t. First, consider the minimization over Q XY , which itself can be separated to an unconstrained minimization over Q Y |X and constrained minimization over Q X . The minimizer Q * Y |X can again be found using similar Lagrange methods as in the proof of Lemma 8. The result is for all x ∈ X such that Q X (x) = 0 (and arbitrary otherwise, since the value of Q * Y |X (·|x) for x ∈ X such that Q X (x) = 0 does not affect the value of the optimization problem). For this optimal choice, using the definitions of δ 1,t (x) and δ 2,t (x) we obtain . (B.49) Next, we optimize over Q X using the KKT conditions. The Lagrangian with λ≥0 and µ is given by and equating to zero results where ψ is a normalization constant, and the definition (56). Using the complementary slackness condition [2, Section 5.5.2], λ is chosen to either satisfy D(Q λ,t X ||P X ) = E r or λ = 0. To show that a bisection method can be used to find the desired λ, we use Lemma 25 (Appendix (C)) to show that D(Q λ,t X ||P X ) is a monotonic decreasing function of λ. To see that the conditions of Lemma 25 are met, notice that initializingQ Y with support Y implies that in the first iteration supp(Q * Y |X ) = supp(P Y |X ) which assures that δ 1,t (x) and δ 2,t (x) are finite. As supp(Q λ,t X ) = supp(P X ) = X for all λ > 0 and t ∈ [0, 1] then supp(Q Y ) = Y for all iterations (cf. (B.58)). Thus, for any t = 0 we may express Q andψ is a normalization factor. Setting α = 1+λ 1+λ+t we get that D(Q λ,t X ||P X ) is a decreasing function of α. Since α is a monotonic increasing function of λ this implies that D(Q λ,t X ||P X ) is also a decreasing function of λ. For t = 0 we may write again Q λ,0 where nowP Similar arguments show that D(Q λ,0 X ||P X ) is a decreasing function of λ. The optimalQ * Y for a given t and Q X , Q Y |X is simplỹ using Lemma 22.
APPENDIX C

USEFUL LEMMAS
In this appendix, we provide several useful lemmas.
Lemma 19 (Tightness of the union bound). Let A 1 , A 2 . . . , A M be pairwise independent events from a probability space. Then Lemma 20. Let P, Q be two PMFs over some alphabet X such that supp(P ) = supp(Q) = X , P = Q, and Also, let α max = max{α : Q α ∈ S(X )}. Then, D(Q α ||P ) is a strictly increasing function of α for α ∈ (0, α max ).
Proof: Let 0 < α 1 < α 2 ≤ α max . Then, thus Q α1 is a convex combination of Q α2 and P with coefficient β α1 α2 , and 0 < β < 1. Now, since divergence is strictly convex function then Proof: This is a standard result. For example, in [1,Theorem 3], this theorem is proved for the case that f 1 and f 2 are information divergences. The proof may be used verbatim for any convex functions.

Lemma 22.
Let P X × P Y |X be a given joint distribution over X × Y. Then the distribution Q Y that minimizes D(P X × P Y |X ||P X × Q Y ) is the marginal distribution Q * Y corresponding to P Y |X namely, Q * Y (y) = x P X (x)P Y |X (y|x).

Corollary 23.
Let P X × P Y |X be a given joint distribution over X × Y. Then the vector Q Y ∈ R |Y| that minimizes D(P X × P Y |X ||P X × Q Y ) 4 under the constraint y∈Y Q Y (y) ≤ 1 and Q Y (y) ≥ 0 for all y ∈ Y, is Q * Y (y) = x P X (x)P Y |X (y|x).
Proof: Suppose that the minimizer vector Q * Y satisfies y∈Y Q * Y (y) < 1. Then for some y ′ ∈ Y, we can increase Q * Y (y ′ ) by 1 − y∈Y Q * Y (y) > 0 and obtainQ Y which satisfies y∈Y Q Y (y) = 1. But, x,y =y ′ P XY (x, y) log P XY (x, y) P X (x)Q * Y (y) (C.14) and this contradicts the fact that Q * Y is a minimizer. Thus, we must have y∈Y Q * Y (y) = 1. In this case, Lemma 22 shows that the optimal solution is Q * Y (y) = x P X (x)P Y |X (y|x).
Lemma 24 (Variant of Minkowski inequality). Let 0 ≤ λ ≤ 1, and let Q X be a PMF over a finite alphabet X , and let {a x (i)} be a set of non-negative numbers for 1 ≤ i ≤ I and x ∈ X . Then, Proof: This variant of Minkowski inequality is stated and proved in [23, Section 3A.1, inequality (k)].
Lemma 25. Let P 1 , P 2 be two PMFs over some alphabet X , such that supp(P 2 ) ⊆ supp(P 1 ). Define for any x ∈ X Q α (x) ψ α P α 1 (x)P 1−α 2 (x) (C. 17) where α ∈ [0, 1] and ψ α is a normalization factor such that Q α ∈ S(X ). Then, D (Q α ||P 1 ) is a continuous function of α whose limit as α → 0 is D(Q ′ ||P ) where for some normalization factor ψ ′ . Moreover, D (Q α ||P 1 ) is monotonic strictly decreasing function of α unless Proof: This is [8, Ex. 2.14, pp. 30-31] but for completeness, we provide a proof here based on [1]. First, notice that P 1 (x) = 0 ⇒ Q α (x) = 0 and thus all x ∈ X such that P 1 (x) = 0 are immaterial to the divergence, assuming the regular convention, that any summand of the form 0 · 0 0 is 0. Thus it may be assumed without loss of generality that supp(P 1 ) = X and P ′ 2 = P 2 . Continuity: Since supp(P 1 ) = X then D (Q α ||P 1 ) is a continuous function of Q α in S(X ). As Q α is a continuous function of α we get that D (Q α ||P 1 ) is a continuous function of α.
Limit for α → 0: Since supp(P 1 ) = X we get that supp(Q α ) = supp(P 2 ). It is easily seen that as α → 0 we have Q α (x) → P 2 (x). where λ ≥ 0 is either chosen such that the constraint is satisfied with equality, or λ = 0. When λ > 0 defining α 1 1+λ we get W (E) = D(Q α ||P 1 ). Thus, if we show that W (E) is a monotonic increasing function of λ, then the proof is finished because α is an increasing function of λ. To this end, notice that: 1) W (E) is a strictly decreasing function of E.
2) Using Lemma 21, W (E) is a strictly convex function of E which implies that dW (E) dE is a strictly increasing function of E.
(C. 21) To see this relation, suppose that λ is chosen to satisfy the constraint E. Then, we get is a monotonic increasing function of λ, and concludes the proof.
Strict monotonicity can be verified by noticing that all monotonicity relations are strict.