WorksComputer Science
Distortion-Rate Outage Probability for Non-ergodic Classes of Sources
Abstract
The concept of outage has been commonly used in the context of transmission rates over non-ergodic channels. For those channels, one channel state or realization may be encountered for the whole transmission duration of a codeword. In the dual setting of source coding and whenever source statistics are not ergodic, we define in this work the notion of outage; we discuss related properties, consider the special case of compact source classes and provide examples.
Introduction
Shannon’s channel coding theorem establishes the channel capacity as the supremum of the rates at which information could be transmitted reliably over a channel [1]. Whenever the transmission rate exceeds the capacity, reliable communication is impossible. In wireless communication settings, fading models such as Rayleigh fading [2] are often adopted for channels. When the fading is slow, the channel state remains fixed over the entire codeword, making the channel non-ergodic. In this case, one cannot simply average over the channel states and the classical capacity loses its operational meaning. For such channels, the notion of outage capacity was introduced (see, e.g., [3]), in which a prescribed probability of transmission failure is tolerated. With the overall communication chain in mind, an expected distortion may not be the appropriate metric to characterize reliability when using such non-ergodic channels. To that effect, the notion of distortion outage for MIMO block fading channel was introduced in [4].
When it comes to source coding, for a source with a known distribution , Shannon’s rate-distortion function [5] gives the infimum of the compression rates for which the expected distortion between the source and its reconstruction does not exceed . In this work, we consider a class of sources , where each is associated with its own probability law . The encoder and decoder have no knowledge of , i.e., they are blind. Such coding schemes were studied in [6], [7].
In this work, we study the source coding analogue of outage capacity: as with fading channels, we distinguish two regimes according to how evolves over time. In the fast regime, is redrawn on a short time scale according to an ergodic process over , so the resulting symbol sequence is itself ergodic. One can then average over , describe the class by a single law and then use the rate-distortion theory tools directly. In the slow regime, a single is drawn once and held fixed for the entire transmission of the codeword. The symbols are then generated Independent and Identically Distributed (IID) according to . The resulting process is a mixture of ergodic components and is non-ergodic in general. So, again, averaging over loses its operational meaning. Moreover, the realized may require a rate that exceeds the available rate budget to meet . We refer to this event as an outage. Building on Sakrison’s rate-distortion function for a class of sources [6], we formally define the Distortion-Rate Outage Probability (DROP) for this setting.
Preliminaries
Consider the classical source coding problem, shown in Figure 1. A source generates a sequence of IID symbols , where is a separate metric space and encoded by and decoded by , yielding the reconstruction . Let be a per-symbol distortion measure, where quantifies the distortion between a source symbol and its reconstruction . The distortion between a source sequence and its reconstruction is defined as the per-symbol average, . The definition of an encoder–decoder pair as a code, together with its rate and achievability are formalized in Section III.
Figure 1. Source coding.
The same schematic as in Figure 1 applies whether there is a single source, or the code is designed for a class of sources, in which case is expected to work well across the entire class in the sense of not exceeding a prescribed distortion level.
For a source with known probability law , Shannon’s information rate–distortion function [1] is defined as
where the minimization is over all conditional distributions such that the expectation, taken with respect to the joint law , satisfies the fidelity constraint . The Shannon coding theorem establishes the operational meaning of as the infimum of the rates at which a source with law can be compressed such that the average per-symbol distortion between the source and its reconstruction does not exceed .
We exclusively consider in this work a class of sources such that for all , for some . Sakrison [6] extended this notion to such a class of sources by providing a definition for the information rate–distortion function of the class, , via a minimax formulation:
where
That is, the optimization is over the choice of a single conditional distribution , satisfying the distortion constraint for every source in the class simultaneously, which minimizes the worst-case mutual information over .
Following Sakrison [6], a class is said to be compact if, given any , there exists a totally bounded set (totally bounded in the sense that can be covered by finitely many neighborhoods of any given radius) and a function
such that
Intuitively, compactness requires that all sources in have most of their probability mass concentrated on a common totally bounded set. A special case of compactness is when there is a finite number of sources in the class.
Additionally, Sakrison proves a source coding theorem [6] in two parts:
The negative (converse) statement holds for any class , compact or not: if an encoder–decoder pair achieves distortion at most for every , the rate of the code must be at least . Therefore, is always a necessary rate for uniform-distortion coding across the class.
The positive (achievability) statement requires the class to be compact, and states given any positive and , there exists a code of sufficiently large length achieving a distortion at most for every , with rate no greater than .
Consequently and in general,
which follows directly from the definition of : restricting a single conditional distribution to satisfy the constraint for every can only make the worst-case rate at least as large as the rate for the individual worst-case source. Combining the negative statement (giving as a necessary rate) with the positive statement for a compact class (proving that a rate arbitrarily close to is achievable), together with (3), forces equality:
As noted by Sakrison, this equality is of considerable practical importance, since as defined in (1) is generally difficult to evaluate directly, whereas can often be computed from the individual rate–distortion functions of the sources in the class. For a non-compact class, only the necessary-rate direction is guaranteed; need not be achievable (a notion we formalize in Section III), and the true minimum required rate may exceed it.
Similarly to the case of a single source, is non-increasing and convex in [6], one can also define the information distortion–rate function for any class of sources, denoted , as the “inverse” of :
Additionally, if is finite, then for all , and vice versa. We use this same notion for “inverses” for the operational objects that we introduce in the following section.
Distortion-Rate Outage Probability
In this section, we first formalize the operational objects introduced informally in Section II and restate Sakrison’s source coding theorem using our notation. We emphasize that we are primarily interested in a blind scenario where neither the encoders nor the decoders have any information about the chosen source .
In what follows, we consider a class of sources such that for all and for some . The sources are chosen with a probability law generically denoted .
Definition 1 (Code). A blocklength- code is a pair consisting of an encoder and a decoder . The rate of is
and, for a source , the distortion of is
Definition 2 (Achievability). A pair is achievable for the class if there exists a sequence of code with
The achievable region is the closure of the set of all achievable pairs.
Definition 3 (Rate–distortion function). For the class ,
By construction, is well-defined for and carries its intended operational meaning directly: it is the infimum of the rates at which a single code, designed without knowledge of , compresses any source in with asymptotic distortion at most for every .
The remainder of this section is stated in terms of the operational quantity , which always carries the intended operational guarantee; (8) is invoked wherever a compact subclass allows these to be evaluated via .
Consider a slow class of sources: for the whole duration of the transmitted codeword, the source produces characters according to a distribution chosen according to the probability law on . Suppose the distortion level should be below a threshold for every source (with probability 1). Then the minimum required rate is . However, similarly to the notion of outage for channel coding, if we allow the distortion level to exceed this threshold with some probability, we may require a lower rate . A distortion outage occurs when the distortion level exceeds the threshold . Due to the dual nature between rate and distortion, this problem may be viewed from another angle: one may instead want to limit the rate by a threshold , resulting in a distortion level . However, if we allow some probability for the rate to exceed , we may achieve lower distortion. We call such events rate outage.
Let denote a subclass of . For a rate limit and distortion level , consider all subclasses such that
We wish to find a subclass maximizing the probability
Notice that the optimization constraint is over the rate–distortion functions of the subclasses rather than of individual sources . We can now formally define the rate outage probability and distortion outage probability. Throughout, the optimization is understood to range over Pr-measurable subclasses .
optimization is understood to range over Pr-measurable subclasses .
Definition 4. The rate outage probability for a rate limit at a given distortion level is defined as
Definition 5. The distortion outage probability for a threshold distortion level at a given rate is
Note that these two definitions are equivalent, in part due to the dual nature of rate–distortion and distortion–rate functions, as shown in proposition 1.
Define the following sets of subclasses:
If , then , so , and by the same reasoning, . Therefore, , and the optimization problems in equations (9),(10) are taken over the same set of subclasses, and therefore the probabilities in (9) and (10) are equal. Hereafter, we drop the superscript and simply denote either quantity as
where and . We call the distortion-rate outage probability of the class of sources.
Proposition 1. For each fixed , there are at most countably many values such that
Proof. The sets are pairwise disjoint for distinct . Since is a probability measure, for each , fewer than of them can satisfy , as otherwise their union would have probability exceeding 1. Therefore,
is a countable union of finite sets, and hence at most countably many carry positive mass.
Remark 1. By Proposition 1, for any fixed , the boundary event has a Pr-probability zero for all but at most countably many values of . Throughout this paper, all inequalities involving a rate budget (e.g., ), are stated with non-strict inequality. Whenever is chosen outside this countable exceptional set, this choice is immaterial: , and is unambiguous regardless of convention. We do not further resolve the exceptional case, in which the precise treatment of the boundary reflects a definitional choice rather than an operationally distinguishable guarantee, consistent with Theorem 1, which is itself only stated with an arbitrarily small margin .
Computing the Outage Probability for Compact Classes
In general, evaluating requires optimizing over all subclasses , and is itself generally intractable to compute for an arbitrary unless is compact (Theorem 1). We now show that when itself is compact, this optimization complexity reduces considerably, and can be computed directly from the rate–distortion functions of the individual sources .
Lemma 1. If is compact, then every subclass is compact.
Proof. Since is compact, for any , there exists a totally bounded set and a function with range such that
for all .
Since , the same and satisfy
for all . As is arbitrary, is compact.
Consequently, by Theorem 1, for every subclass and not only for itself. This allows us to reduce the subclass-level optimization defining to a pointwise condition on individual sources.
Theorem 2. Let be compact. Then the subclass maximizing subject to is
and the outage probability is
provided is -measurable.
Proof. By Lemma 1, for every , so the constraint holds if and only if for every , i.e., if and only if . Since is monotone under inclusion, for every feasible , with equality at . Hence is the (essentially unique) maximizer, and (15) follows from the definition of in Section III.
Corollary 1 (Finite classes). If is finite (and hence compact), (15) reduces to
Corollary 1 provides a direct computational recipe: given the individual rate–distortion functions and the prior for each , the outage probability at any is obtained by summing over the sources whose individual rate–distortion function does not exceed at distortion ; No explicit search over subclasses, and no evaluation of for any , is required. More generally, Theorem 2 shows this same reduction holds for any compact class, finite or not such as a bounded-variance Gaussian class, with the sum replaced by an integral against the prior over .
Remark 2 (Side Information). Suppose we have an arbitrary compact class, , and both the encoder and decoders are informed of the source generating the symbols, i.e., with perfect knowledge of the source statistics. Then, the distortion-rate outage probability is . We could also consider the case where only the encoder is informed of the source , and is finite (and therefore compact). Here, we may use a finite number of prefix bits to signal . This essentially informs the decoder of the source . Even in this case, the outage probability remains the same: the prefix cost is a vanishing fraction of the rate as the block length grows. Therefore, this neither relaxes nor tightens which sources satisfy . Therefore, it does not the distortion-rate outage probability asymptotically.
Although no improvements are feasible in terms of DROP, side information may still be useful in the following cases:
Finite blocklength performance
Non-compact classes when
We illustrate the distortion-rate outage probability with two examples: a finite class of Bernoulli sources under Hamming distortion, for which Corollary 1 applies directly, and a continuum class of Gaussian sources under mean-squared error, which is known to be compact.
Example 1 (A finite class of Bernoulli sources). Let , where each is a Bernoulli() source, and let be the Hamming distortion measure. The rate–distortion function of a Bernoulli() source under Hamming distortion [1] is
where is the binary entropy function. Since is finite, by Corollary 1, for a rate limit and distortion level ,
where
As a concrete instance, let with prior , , , and fix . Here, bits. Table I lists . For , no source satisfies , so and . For (e.g., ), and . For (e.g., ), and . For , and .
| (bits) | (bits/sample) | ||
| 0.1 | 0.5 | 0.469 | 0.183 |
| 0.3 | 0.3 | 0.881 | 0.595 |
| 0.5 | 0.2 | 1.000 | 0.714 |
Table I. Bernoulli source classes at distortion level .
In Figure 2, we show for the tighter distortion level, , where bits. We notice that since is decreasing in , every breakpoint shifts to a higher rate, and the entire curve is shifted rightward relative to the higher distortion level, .

Figure 2. Outage probability for the finite Bernoulli class, as a function of rate budget , for two distortion levels . The looser target shifts every drop to a lower rate, since decreases as increases.
Example 2 (A continuous class of Gaussian sources). Let and let . This class is compact according to [6 Section 6]. By Theorem 2, . The same holds for every subclass . With MSE rate–distortion being invariant to the mean,
for , depending on only through . Consequently,
and is an interval constraint on the variance alone.
Suppose and are independent under , with a uniform (and arbitrarily distributed on ). Then
By Theorem 2,
Equation (17) shows that is decreasing in and , reaching zero once . This is consistent with (3): no outage is possible once the rate budget covers the worst-case source in the class.

Figure 3. Outage probability for the compact Gaussian class with , as a function of rate budget , for several fixed distortion levels . Each curve reaches zero at , consistent with (17).
Since this class is a special case of the class of stable sources which have been recently studied in [8], the DROP expression can be readily extended to the general class of stable sources.
Conclusion
We revisited the source coding problem for a class of sources and introduced Distortion-Rate Outage Probability (DROP) as a performance metric for slow sources, in which the underlying source remains fixed over the duration of transmission of the codeword. This characterization provides a natural source-side analogue of the channel-side notions of outage capacity and distortion outage. Through illustrative examples, we demonstrated how DROP highlights the tradeoff between outage probability, rate and distortion constraints. This formulation may further serve as a foundation for a joint outage notion in which a slow class of sources is transmitted over a slow-fading channel.
AI USAGE
The authors acknowledge the use of ChatGPT for English and LaTeX-related assistance, and generation of Figures 2 and 3. The main ideas and technical contents in this work were produced independently by the authors. Claude was used to review and refine some of the technical contents.
References
References
- [1]T. M. Cover and J. A. Thomas, Elements of Information Theory, 1st ed. Wiley, Sep. 2005. [Online]. Available: https://onlinelibrary.wiley.com/doi/book/10.1002/047174882X
- [2]I. Abou-Faycal, M. Trott, and S. Shamai, “The capacity of discrete-time memoryless rayleigh-fading channels,” IEEE Transactions on Information Theory, vol. 47, no. 4, pp. 1290–1301, 2001.
- [3]D. Tse and P. Viswanath, Fundamentals of Wireless Communication. Cambridge University Press, 2005.DOI
- [4]L. Peng and A. Guillén i Fàbregas, “Distortion outage probability in mimo block-fading channels,” in 2010 IEEE International Symposium on Information Theory, 2010, pp. 2223–2227.DOI
- [5]C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1948.tb01338.x
- [6]D. J. Shamai, “The rate distortion function for a class of sources,” Information and Control, vol. 15, no. 2, pp. 165–195, 1969. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019995869904033
- [7]J. Ziv, “Coding of sources with unknown statistics--ii: Distortion relative to a fidelity criterion,” IEEE transactions on information theory, vol. 18, no. 3, pp. 389–394, 1972.DOI
- [8]K. Ezzeddine, J. Fahs, and I. C. Abou-Faycal, “A framework for lossy compression of heavy-tailed sources,” IEEE Transactions on Communications, vol. 74, pp. 6349–6363, 2026.DOI
