betaFeedback

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 pθp_\theta, Shannon’s rate-distortion function Rθ(D)R_\theta(D) [5] gives the infimum of the compression rates for which the expected distortion between the source and its reconstruction does not exceed DD. In this work, we consider a class of sources Λ\Lambda, where each θ∈Λ\theta\in\Lambda is associated with its own probability law pθ(⋅)p_\theta(\cdot). The encoder and decoder have no knowledge of θ\theta, 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 θ\theta evolves over time. In the fast regime, θ\theta is redrawn on a short time scale according to an ergodic process over Λ\Lambda, so the resulting symbol sequence is itself ergodic. One can then average over Λ\Lambda, describe the class by a single law and then use the rate-distortion theory tools directly. In the slow regime, a single θ∈Λ\theta\in\Lambda 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 pθp_\theta. The resulting process is a mixture of ergodic components and is non-ergodic in general. So, again, averaging over Λ\Lambda loses its operational meaning. Moreover, the realized θ\theta may require a rate that exceeds the available rate budget to meet DD. 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 θ\theta generates a sequence of nn IID symbols Xn=(X1,⋯ ,Xn)∈XnX^n = (X_1,\cdots,X_n) \in\mathcal{X}^n, where X\mathcal{X} is a separate metric space and encoded by fn:Xn→{1,…,Mn}f_n : \mathcal{X}^n \to\{1,\ldots,M_n\} and decoded by gn:{1,…,Mn}→X^ng_n : \{1,\ldots,M_n\} \to\hat{\mathcal{X}}^n, yielding the reconstruction X^n:=gn(fn(Xn))\hat{X}^n := g_n(f_n(X^n)). Let d:X×X^→[0,∞)d : \mathcal{X} \times\hat{\mathcal{X}} \to[0,\infty) be a per-symbol distortion measure, where d(xi,x^i)d(x_i,\hat{x}_i) quantifies the distortion between a source symbol xix_i and its reconstruction x^i\hat{x}_i. The distortion between a source sequence xnx^n and its reconstruction x^n\hat{x}^n is defined as the per-symbol average, d(xn,x^n):=1n∑i=1nd(xi,x^i)d(x^n,\hat{x}^n) := \frac{1}{n}\sum_{i=1}^{n}d(x_i,\hat{x}_i). 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 Λ\Lambda of sources, in which case (fn,gn)(f_n,g_n) 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 pθp_\theta, Shannon’s information rate–distortion function [1] is defined as

Rθ(D):=inf⁡pX^∣X:Eθ[d(X,X^)]≤DIθ(X;X^),R_\theta(D) := \inf_{p_{\hat{X}|X}:\mathbb{E}_\theta[d(X,\hat{X})]\leq D} I_\theta(X;\hat{X}),

where the minimization is over all conditional distributions pX^∣Xp_{\hat{X}|X} such that the expectation, taken with respect to the joint law pθ(x)pX^∣X(x^∣x)p_\theta(x)p_{\hat{X}|X}(\hat{x}|x), satisfies the fidelity constraint DD. The Shannon coding theorem establishes the operational meaning of Rθ(D)R_\theta(D) as the infimum of the rates at which a source with law pθp_\theta can be compressed such that the average per-symbol distortion between the source and its reconstruction does not exceed DD.

We exclusively consider in this work a class Λ\Lambda of sources such that Eθ[d(X,x0)]<∞\mathbb{E}_\theta[d(X,x_0)]<\infty for all θ∈Λ\theta\in\Lambda, for some x0∈X′x_0\in\mathcal{X}'. Sakrison [6] extended this notion to such a class Λ\Lambda of sources by providing a definition for the information rate–distortion function of the class, RΛI(D)R^I_\Lambda(D), via a minimax formulation:

RΛI(D):=inf⁡pX^∣X∈QΛ(D)sup⁡θ∈ΛIθ(X;X^),(1)R^I_\Lambda(D) := \inf_{p_{\hat{X}|X}\in Q_\Lambda(D)} \sup_{\theta\in\Lambda} I_\theta(X;\hat{X}), \tag*{(1)}

where

QΛ(D):={pX^∣X:Eθ[d(X,X^)]≤D∀ θ∈Λ}.Q_\Lambda(D):=\left\{p_{\hat{X}|X}:\mathbb{E}_\theta[d(X,\hat{X})]\leq D\quad\forall\ \theta\in\Lambda\right\}.

That is, the optimization is over the choice of a single conditional distribution pX^∣Xp_{\hat{X}|X}, satisfying the distortion constraint for every source in the class simultaneously, which minimizes the worst-case mutual information over Λ\Lambda.

Following Sakrison [6], a class Λ\Lambda is said to be compact if, given any ϵ1>0\epsilon_1>0, there exists a totally bounded set X′⊆X\mathcal{X}'\subseteq\mathcal{X} (totally bounded in the sense that X′\mathcal{X}' can be covered by finitely many neighborhoods of any given radius) and a function

xp:X⟶X′x_p:\mathcal{X}\longrightarrow\mathcal{X}'

such that

Eθ[d(X,xp(X))]≤ϵ1∀ θ∈Λ.(2)\mathbb{E}_\theta[d(X,x_p(X))]\leq\epsilon_1\quad\forall\ \theta\in\Lambda. \tag*{(2)}

Intuitively, compactness requires that all sources in Λ\Lambda 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 Λ\Lambda, compact or not: if an encoder–decoder pair achieves distortion at most DD for every θ∈Λ\theta\in\Lambda, the rate of the code must be at least RΛI(D)R^I_\Lambda(D). Therefore, RΛI(D)R^I_\Lambda(D) 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 DD and δ\delta, there exists a code of sufficiently large length achieving a distortion at most D+δD+\delta for every θ∈Λ\theta\in\Lambda, with rate no greater than sup⁡θ∈ΛRθ(D)+δ\sup_{\theta\in\Lambda}R_\theta(D)+\delta.

Consequently and in general,

RΛI(D)≥sup⁡θ∈ΛRθ(D),(3)R^I_\Lambda(D)\geq\sup_{\theta\in\Lambda}R_\theta(D), \tag*{(3)}

which follows directly from the definition of RΛI(D)R^I_\Lambda(D): restricting a single conditional distribution to satisfy the constraint for every θ∈Λ\theta\in\Lambda 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 RΛI(D)R^I_\Lambda(D) as a necessary rate) with the positive statement for a compact class (proving that a rate arbitrarily close to sup⁡θ∈ΛRθ(D)\sup_{\theta\in\Lambda}R_\theta(D) is achievable), together with (3), forces equality:

RΛI(D)=sup⁡θ∈ΛRθ(D)for a compact class Λ.(4)R^I_\Lambda(D)=\sup_{\theta\in\Lambda}R_\theta(D)\qquad\text{for a compact class }\Lambda. \tag*{(4)}

As noted by Sakrison, this equality is of considerable practical importance, since RΛI(D)R^I_\Lambda(D) as defined in (1) is generally difficult to evaluate directly, whereas sup⁡θ∈ΛRθ(D)\sup_{\theta\in\Lambda}R_\theta(D) 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; RΛI(D)R^I_\Lambda(D) 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, RΛI(D)R^I_\Lambda(D) is non-increasing and convex in DD [6], one can also define the information distortion–rate function for any class of sources, denoted DΛI(R)D^I_\Lambda(R), as the “inverse” of RΛI(D)R^I_\Lambda(D):

DΛI(R):=inf⁡{D:RΛI(D)≤R}D^I_\Lambda(R):=\inf\{D:R^I_\Lambda(D)\leq R\}
RΛI(D):=inf⁡{R:DΛI(R)≤D}.R^I_\Lambda(D):=\inf\{R:D^I_\Lambda(R)\leq D\}.

Additionally, if RΛI(0)=R0R^I_\Lambda(0)=R_0 is finite, then DΛI(R)=0D^I_\Lambda(R)=0 for all R>R0R>R_0, 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 θ\theta.

In what follows, we consider a class Λ\Lambda of sources such that Eθ[d(X,x0)]<∞\mathbb{E}_\theta[d(X,x_0)]<\infty for all θ∈Λ\theta\in\Lambda and for some x0∈X′x_0\in\mathcal{X}'. The sources θ∈Λ\theta\in\Lambda are chosen with a probability law generically denoted Pr⁡(⋅)\Pr(\cdot).

Definition 1 (Code). A blocklength-nn code Cn=(fn,gn)C_n=(f_n,g_n) is a pair consisting of an encoder fn:Xn→{1,…,Mn}f_n:\mathcal{X}^n\to\{1,\ldots,M_n\} and a decoder gn:{1,…,Mn}→X^ng_n:\{1,\ldots,M_n\}\to\hat{\mathcal{X}}^n. The rate of CnC_n is

R(Cn):=1nlog⁡Mn(5)R(C_n):=\frac{1}{n}\log M_n \tag*{(5)}

and, for a source θ∈Λ\theta\in\Lambda, the distortion of CnC_n is

dθ(Cn):=Eθ[d(Xn,gn(fn(Xn)))].(6)d_\theta(C_n):=\mathbb{E}_\theta\left[d\left(X^n,g_n(f_n(X^n))\right)\right]. \tag*{(6)}

Definition 2 (Achievability). A pair (R,D)(R,D) is achievable for the class Λ\Lambda if there exists a sequence of code {Cn}n\{C_n\}_n with

lim sup⁡n→∞R(Cn)≤R&lim sup⁡n→∞dθ(Cn)≤D∀θ∈Λ.\limsup_{n\to\infty} R(C_n) \le R \quad\& \quad\limsup_{n\to\infty} d_\theta(C_n) \le D \quad\forall\theta\in\Lambda.

The achievable region RΛ\mathcal{R}_{\Lambda} is the closure of the set of all achievable pairs.

Definition 3 (Rate–distortion function). For the class Λ\Lambda,

RΛ(D):=inf⁡{R:(R,D)∈RΛ}R_{\Lambda}(D) := \inf\{R : (R,D) \in\mathcal{R}_{\Lambda}\}
&DΛ(R):=inf⁡{D:(R,D)∈RΛ}.\& \quad D_{\Lambda}(R) := \inf\{D : (R,D) \in\mathcal{R}_{\Lambda}\}.

By construction, RΛ(D)R_{\Lambda}(D) is well-defined for Λ\Lambda and carries its intended operational meaning directly: it is the infimum of the rates at which a single code, designed without knowledge of θ\theta, compresses any source in Λ\Lambda with asymptotic distortion at most DD for every θ∈Λ\theta\in\Lambda.

Theorem 1 (Sakrison’s source coding theorem [6]). For the class Λ\Lambda,

RΛ(D)≥RΛI(D)≥sup⁡θ∈ΛRθ(D).(7)R_{\Lambda}(D) \ge R_{\Lambda}^{I}(D) \ge\sup_{\theta\in\Lambda} R_\theta(D). \tag*{(7)}

If Λ\Lambda is compact, then

RΛ(D)=RΛI(D)=sup⁡θ∈ΛRθ(D).(8)R_{\Lambda}(D) = R_{\Lambda}^{I}(D) = \sup_{\theta\in\Lambda} R_\theta(D). \tag*{(8)}

The remainder of this section is stated in terms of the operational quantity RΛ(D)R_{\Lambda}(D), which always carries the intended operational guarantee; (8) is invoked wherever a compact subclass allows these to be evaluated via sup⁡θRθ(D)\sup_{\theta} R_\theta(D).

Consider a slow class of sources: for the whole duration of the transmitted codeword, the source produces characters according to a distribution θ∈Λ\theta\in\Lambda chosen according to the probability law on Λ\Lambda. Suppose the distortion level should be below a threshold DD for every source (with probability 1). Then the minimum required rate is RΛ(D)R_{\Lambda}(D). 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 RR. A distortion outage occurs when the distortion level exceeds the threshold DD. 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 RR, resulting in a distortion level DΛ(R)D_{\Lambda}(R). However, if we allow some probability for the rate to exceed RR, we may achieve lower distortion. We call such events rate outage.

Let Σ⊆Λ\Sigma\subseteq\Lambda denote a subclass of Λ\Lambda. For a rate limit RR and distortion level DD, consider all subclasses such that

{Σ⊆Λ:RΣ(D)≤R}.\{\Sigma\subseteq\Lambda: R_{\Sigma}(D) \le R\}.

We wish to find a subclass maximizing the probability

sup⁡Σ⊆Λ:RΣ(D)≤RPr⁡(Σ).\sup_{\Sigma\subseteq\Lambda:R_{\Sigma}(D)\le R} \Pr(\Sigma).

Notice that the optimization constraint is over the rate–distortion functions of the subclasses Σ\Sigma rather than of individual sources θ\theta. We can now formally define the rate outage probability and distortion outage probability. Throughout, the optimization is understood to range over Pr-measurable subclasses Σ⊆Λ\Sigma\subseteq\Lambda.

optimization is understood to range over Pr-measurable subclasses Σ⊆Λ\Sigma\subseteq\Lambda.

Definition 4. The rate outage probability for a rate limit RR at a given distortion level DD is defined as

PoutR(R,D)=1−sup⁡Σ⊆Λ:RΣ(D)≤RPr⁡(Σ)(9)P_{\mathrm{out}}^{R}(R,D) = 1 - \sup_{\Sigma\subseteq\Lambda:R_{\Sigma}(D)\le R} \Pr(\Sigma) \tag*{(9)}

Definition 5. The distortion outage probability for a threshold distortion level DD at a given rate RR is

PoutD(D,R)=1−sup⁡Σ⊆Λ:DΣ(R)≤DPr⁡(Σ)(10)P_{\mathrm{out}}^{D}(D,R) = 1 - \sup_{\Sigma\subseteq\Lambda:D_{\Sigma}(R)\le D} \Pr(\Sigma) \tag*{(10)}

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:

AD:={Σ⊆Λ:DΣ(Rˉ)≤Dˉ},(11)\mathcal{A}_{D} := \{\Sigma\subseteq\Lambda: D_{\Sigma}(\bar{R}) \le\bar{D}\}, \tag*{(11)}
AR:={Σ⊆Λ:RΣ(Dˉ)≤Rˉ}.(12)\mathcal{A}_{R} := \{\Sigma\subseteq\Lambda: R_{\Sigma}(\bar{D}) \le\bar{R}\}. \tag*{(12)}

If Σ∈AR\Sigma\in\mathcal{A}_{R}, then RΣ(Dˉ)≤Rˉ⟹DΣ(Rˉ)=inf⁡{D:RΣ(D)≤Rˉ}≤Dˉ⟹Σ∈ADR_{\Sigma}(\bar{D}) \le\bar{R} \Longrightarrow D_{\Sigma}(\bar{R}) = \inf\{D : R_{\Sigma}(D) \le\bar{R}\} \le\bar{D} \Longrightarrow\Sigma\in\mathcal{A}_{D}, so AR⊆AD\mathcal{A}_{R} \subseteq\mathcal{A}_{D}, and by the same reasoning, AD⊆AR\mathcal{A}_{D} \subseteq\mathcal{A}_{R}. Therefore, AD=AR\mathcal{A}_{D} = \mathcal{A}_{R}, 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

Pout(R,D):=PoutR(Rˉ,Dˉ)=PoutD(Dˉ,Rˉ),(13)P_{\mathrm{out}}(R,D) := P_{\mathrm{out}}^{R}(\bar{R},\bar{D}) = P_{\mathrm{out}}^{D}(\bar{D},\bar{R}), \tag*{(13)}

where R=RˉR = \bar{R} and D=DˉD = \bar{D}. We call Pout(⋅,⋅)P_{\mathrm{out}}(\cdot,\cdot) the distortion-rate outage probability of the class Λ\Lambda of sources.

Proposition 1. For each fixed DD, there are at most countably many values Rˉ≥0\bar{R} \ge0 such that

Pr⁡θ∈Λ(Rθ(D)=Rˉ)>0.\Pr_{\theta\in\Lambda}\left(R_\theta(D)=\bar{R}\right)>0.

Proof. The sets ARˉ:={θ:Rθ(D)=Rˉ}A_{\bar{R}} := \{\theta: R_\theta(D)=\bar{R}\} are pairwise disjoint for distinct Rˉ\bar{R}. Since Pr⁡\Pr is a probability measure, for each n∈Nn \in\mathbb{N}, fewer than nn of them can satisfy Pr⁡(ARˉ)>1/n\Pr(A_{\bar{R}})>1/n, as otherwise their union would have probability exceeding 1. Therefore,

{Rˉ:Pr⁡(ARˉ)>0}=⋃n{Rˉ:Pr⁡(ARˉ)>1/n}\{\bar{R} : \Pr(A_{\bar{R}})>0\}=\bigcup_n\{\bar{R}:\Pr(A_{\bar{R}})>1/n\}

is a countable union of finite sets, and hence at most countably many Rˉ\bar{R} carry positive mass. □\square

Remark 1. By Proposition 1, for any fixed DD, the boundary event {θ:Rθ(D)=Rˉ}\{\theta:R_\theta(D)=\bar{R}\} has a Pr-probability zero for all but at most countably many values of Rˉ\bar{R}. Throughout this paper, all inequalities involving a rate budget Rˉ\bar{R} (e.g., Σopt(Rˉ,D)={θ:Rθ(D)≤Rˉ}\Sigma^{\mathrm{opt}}(\bar{R},D)=\{\theta:R_\theta(D)\le\bar{R}\}), are stated with non-strict inequality. Whenever RR is chosen outside this countable exceptional set, this choice is immaterial: Pr⁡({θ:Rθ(D)≤Rˉ})=Pr⁡({θ:Rθ(D)<Rˉ})\Pr(\{\theta:R_\theta(D)\le\bar{R}\})=\Pr(\{\theta:R_\theta(D)<\bar{R}\}), and Pout(Rˉ,D)P_{\mathrm{out}}(\bar{R},D) 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 δ>0\delta> 0.

Computing the Outage Probability for Compact Classes

In general, evaluating Pout(R,D)P_{\mathrm{out}}(R,D) requires optimizing over all subclasses Σ⊆Λ\Sigma\subseteq\Lambda, and RΣ(D)R_{\Sigma}(D) is itself generally intractable to compute for an arbitrary Σ\Sigma unless Σ\Sigma is compact (Theorem 1). We now show that when Λ\Lambda itself is compact, this optimization complexity reduces considerably, and Pout(R,D)P_{\mathrm{out}}(R,D) can be computed directly from the rate–distortion functions of the individual sources θ∈Λ\theta\in\Lambda.

Lemma 1. If Λ\Lambda is compact, then every subclass Σ⊆Λ\Sigma\subseteq\Lambda is compact.

Proof. Since Λ\Lambda is compact, for any ϵ1>0\epsilon_1 > 0, there exists a totally bounded set X′=X′(ϵ1)\mathcal{X}' = \mathcal{X}'(\epsilon_1) and a function xp(⋅)x_p(\cdot) with range X′\mathcal{X}' such that

Eθ[d(X,xp(X))]≤ϵ1\mathbb{E}_{\theta}[d(X,x_p(X))] \le\epsilon_1

for all θ∈Λ\theta\in\Lambda.

Since Σ⊆Λ\Sigma\subseteq\Lambda, the same X′\mathcal{X}' and xpx_p satisfy

Eθ[d(X,xp(X))]≤ϵ1\mathbb{E}_{\theta}[d(X,x_p(X))] \le\epsilon_1

for all θ∈Σ\theta\in\Sigma. As ϵ1\epsilon_1 is arbitrary, Σ\Sigma is compact.

Consequently, by Theorem 1, RΣ(D)=sup⁡θ∈ΣRθ(D)R_{\Sigma}(D) = \sup_{\theta\in\Sigma} R_{\theta}(D) for every subclass Σ⊆Λ\Sigma\subseteq\Lambda and not only for Λ\Lambda itself. This allows us to reduce the subclass-level optimization defining Pout(R,D)P_{\mathrm{out}}(R,D) to a pointwise condition on individual sources.

Theorem 2. Let Λ\Lambda be compact. Then the subclass maximizing Pr⁡(Σ)\Pr(\Sigma) subject to RΣ(D)≤RR_{\Sigma}(D) \le R is

Σopt:={θ∈Λ:Rθ(D)≤R},(14)\Sigma^{\mathrm{opt}} := \{\theta\in\Lambda: R_{\theta}(D) \le R\}, \tag*{(14)}

and the outage probability is

Pout(R,D)=1−Pr⁡(Σopt)P_{\mathrm{out}}(R,D) = 1 - \Pr(\Sigma^{\mathrm{opt}})
=1−∫{θ∈Λ:Rθ(D)≤R}dPr⁡(θ),(15)= 1 - \int_{\{\theta\in\Lambda: R_{\theta}(D) \le R\}} d\Pr(\theta), \tag*{(15)}

provided Σopt\Sigma^{\mathrm{opt}} is Pr⁡\Pr-measurable.

Proof. By Lemma 1, RΣ(D)=sup⁡θ∈ΣRθ(D)R_{\Sigma}(D) = \sup_{\theta\in\Sigma} R_{\theta}(D) for every Σ⊆Λ\Sigma\subseteq\Lambda, so the constraint RΣ(D)≤RR_{\Sigma}(D) \le R holds if and only if Rθ(D)≤RR_{\theta}(D) \le R for every θ∈Σ\theta\in\Sigma, i.e., if and only if Σ⊆Σopt\Sigma\subseteq\Sigma^{\mathrm{opt}}. Since Pr⁡\Pr is monotone under inclusion, Pr⁡(Σ)≤Pr⁡(Σopt)\Pr(\Sigma) \le\Pr(\Sigma^{\mathrm{opt}}) for every feasible Σ\Sigma, with equality at Σ=Σopt\Sigma= \Sigma^{\mathrm{opt}}. Hence Σopt\Sigma^{\mathrm{opt}} is the (essentially unique) maximizer, and (15) follows from the definition of PoutP_{\mathrm{out}} in Section III.

Corollary 1 (Finite classes). If Λ\Lambda is finite (and hence compact), (15) reduces to

Pout(R,D)=1−∑θ∈Λ:Rθ(D)≤RPr⁡(θ).(16)P_{\mathrm{out}}(R,D) = 1 - \sum_{\theta\in\Lambda: R_{\theta}(D) \le R} \Pr(\theta). \tag*{(16)}

Corollary 1 provides a direct computational recipe: given the individual rate–distortion functions Rθ(D)R_{\theta}(D) and the prior Pr⁡(θ)\Pr(\theta) for each θ∈Λ\theta\in\Lambda, the outage probability at any (R,D)(R,D) is obtained by summing Pr⁡(θ)\Pr(\theta) over the sources whose individual rate–distortion function does not exceed RR at distortion DD; No explicit search over subclasses, and no evaluation of RΣ(D)R_{\Sigma}(D) for any Σ\Sigma, 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 Pr⁡\Pr over Σopt\Sigma^{\mathrm{opt}}.

Remark 2 (Side Information). Suppose we have an arbitrary compact class, Λ\Lambda, and both the encoder and decoders are informed of the source θ\theta generating the symbols, i.e., with perfect knowledge of the source statistics. Then, the distortion-rate outage probability is 1−∑θ∈Λ:Rθ(D)≤RPr⁡(θ)1-\sum_{\theta\in\Lambda: R_{\theta}(D) \le R}\Pr(\theta). We could also consider the case where only the encoder is informed of the source θ\theta, and Λ\Lambda is finite (and therefore compact). Here, we may use a finite number of prefix bits to signal θ\theta. This essentially informs the decoder of the source θ\theta. 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 Rθ(D)≤RR_{\theta}(D) \le R. 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 nn performance

  • Non-compact classes when RΛ(D)≠sup⁡θ∈ΛRθ(D)R_{\Lambda}(D) \ne\sup_{\theta\in\Lambda} R_{\theta}(D)

We illustrate the distortion-rate outage probability Pout(R,D)P_{\mathrm{out}}(R,D) 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 Λ={p1,…,pk}⊂(0,1)\Lambda= \{p_1,\ldots,p_k\} \subset(0,1), where each θi=pi\theta_i = p_i is a Bernoulli(pip_i) source, and let d(⋅,⋅)d(\cdot,\cdot) be the Hamming distortion measure. The rate–distortion function of a Bernoulli(pp) source under Hamming distortion [1] is

Rθ(D)={Hb(p)−Hb(D),0≤D≤min⁡{p,1−p},0,D>min⁡{p,1−p},R_{\theta}(D) = \begin{cases} H_b(p) - H_b(D), & 0 \le D \le\min\{p,1-p\},\\ 0, & D > \min\{p,1-p\}, \end{cases}

where Hb(⋅)H_b(\cdot) is the binary entropy function. Since Λ\Lambda is finite, by Corollary 1, for a rate limit RR and distortion level DD,

Pout(R,D)=1−∑pi∈ΣoptPr⁡(pi),P_{\mathrm{out}}(R,D) = 1 - \sum_{p_i \in\Sigma^{\mathrm{opt}}} \Pr(p_i),

where

Σopt={{pi∈Λ:Hb(pi)≤R+Hb(D)},when 0<D<0.5,Λ,otherwise.\Sigma^{\mathrm{opt}} = \begin{cases} \{p_i \in\Lambda: H_b(p_i) \le R + H_b(D)\}, & \text{when } 0 < D < 0.5,\\ \Lambda, & \text{otherwise}. \end{cases}

As a concrete instance, let Λ={0.1,0.3,0.5}\Lambda= \{0.1,0.3,0.5\} with prior Pr⁡(0.1)=0.5\Pr(0.1) = 0.5, Pr⁡(0.3)=0.3\Pr(0.3) = 0.3, Pr⁡(0.5)=0.2\Pr(0.5) = 0.2, and fix D=0.05D = 0.05. Here, H(D)≈0.286H(D) \approx0.286 bits. Table I lists Rpi(D)R_{p_i}(D). For R<0.183R < 0.183, no source satisfies Rpi(D)≤RR_{p_i}(D) \le R, so Σopt=∅\Sigma^{\mathrm{opt}} = \emptyset and Pout(R,0.05)=1P_{\mathrm{out}}(R,0.05) = 1. For 0.183≤R<0.5950.183 \le R < 0.595 (e.g., R=0.2R = 0.2), Σopt={0.1}\Sigma^{\mathrm{opt}} = \{0.1\} and Pout(0.2,0.05)=1−0.5=0.5P_{\mathrm{out}}(0.2,0.05) = 1 - 0.5 = 0.5. For 0.595≤R<0.7140.595 \le R < 0.714 (e.g., R=0.65R = 0.65), Σopt={0.1,0.3}\Sigma^{\mathrm{opt}} = \{0.1, 0.3\} and Pout(0.65,0.05)=1−0.8=0.2P_{\mathrm{out}}(0.65,0.05) = 1 - 0.8 = 0.2. For R≥0.714R \ge0.714, Σopt=Λ\Sigma^{\mathrm{opt}} = \Lambda and Pout=0P_{\mathrm{out}} = 0.

pip_iPr⁡(θ=pi)\Pr(\theta= p_i)H(pi)H(p_i) (bits)Rpi(D)R_{p_i}(D) (bits/sample)
0.10.50.4690.183
0.30.30.8810.595
0.50.21.0000.714

Table I. Bernoulli source classes at distortion level D=0.05D = 0.05.

In Figure 2, we show Pout(R,D)P_{\mathrm{out}}(R,D) for the tighter distortion level, D=0.01D = 0.01, where H(0.01)≈0.081H(0.01) \approx0.081 bits. We notice that since Rpi(D)R_{p_i}(D) is decreasing in DD, every breakpoint shifts to a higher rate, and the entire curve is shifted rightward relative to the higher distortion level, D=0.05D = 0.05.

Outage probability for the finite Bernoulli class

Figure 2. Outage probability Pout(R,D)P_{\mathrm{out}}(R,D) for the finite Bernoulli class, as a function of rate budget RR, for two distortion levels D∈{0.01,0.05}D \in\{0.01, 0.05\}. The looser target D=0.05D = 0.05 shifts every drop to a lower rate, since Rpi(D)R_{p_i}(D) decreases as DD increases.

Example 2 (A continuous class of Gaussian sources). Let Λ={θ=(μ,σ2):∣μ∣≤M,0<σ2≤σ02}\Lambda= \{\theta= (\mu,\sigma^2) : |\mu| \le M, 0 < \sigma^2 \le\sigma_0^2\} and let d(x,x^)=(x−x^)2d(x,\hat{x}) = (x-\hat{x})^2. This class is compact according to [6 Section 6]. By Theorem 2, RΛ(D)=sup⁡θ∈ΛRθ(D)R_\Lambda(D) = \sup_{\theta\in\Lambda} R_\theta(D). The same holds for every subclass Σ⊆Λ\Sigma\subseteq\Lambda. With MSE rate–distortion being invariant to the mean,

Rθ(D)=12log⁡2(σ2/D),R_\theta(D) = \frac{1}{2}\log_2(\sigma^2/D),

for D≤σ2D \le\sigma^2, depending on θ=(μ,σ2)\theta= (\mu,\sigma^2) only through σ2\sigma^2. Consequently,

Σopt={(μ,σ2)∈Λ:σ2≤D⋅22R},\Sigma^{\mathrm{opt}} = \{(\mu,\sigma^2) \in\Lambda: \sigma^2 \le D \cdot2^{2R}\},

and is an interval constraint on the variance alone.

Suppose μ\mu and σ2\sigma^2 are independent under Pr⁡\Pr, with a uniform σ2∼U(0,σ02]\sigma^2 \sim\mathcal{U}(0,\sigma_0^2] (and μ\mu arbitrarily distributed on [−M,M][-M,M]). Then

Pr⁡(Σopt)=Pr⁡(σ2≤D⋅22R)=min⁡{D⋅22R,σ02}σ02.\Pr(\Sigma^{\mathrm{opt}}) = \Pr(\sigma^2 \le D \cdot2^{2R}) = \frac{\min\{D \cdot2^{2R},\sigma_0^2\}}{\sigma_0^2}.

By Theorem 2,

Pout(R,D)=max⁡{1−D⋅22Rσ02,0}.(17)P_{\mathrm{out}}(R,D) = \max\left\{1-\frac{D \cdot2^{2R}}{\sigma_0^2},0\right\}. \tag*{(17)}

Equation (17) shows that PoutP_{\mathrm{out}} is decreasing in RR and DD, reaching zero once R≥12log⁡2(σ02/D)=sup⁡θ∈ΛRθ(D)R \ge\frac{1}{2}\log_2(\sigma_0^2/D) = \sup_{\theta\in\Lambda} R_\theta(D). This is consistent with (3): no outage is possible once the rate budget covers the worst-case source in the class.

Outage probability for the compact Gaussian class

Figure 3. Outage probability Pout(R,D)P_{\mathrm{out}}(R,D) for the compact Gaussian class with (σ02=1)(\sigma_0^2 = 1), as a function of rate budget RR, for several fixed distortion levels DD. Each curve reaches zero at R=12log⁡2(σ02/D)R = \frac{1}{2}\log_2(\sigma_0^2/D), 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 θ\theta 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. [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. [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. [3]D. Tse and P. Viswanath, Fundamentals of Wireless Communication. Cambridge University Press, 2005.DOI
  4. [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. [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. [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. [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. [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

Paper details

vlnc:W_bpetfqfw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…
Contents