CS Paper Radar

Revisiting Shannon's Source Coding Theorem with Distributional Uncertainty under the Nonlinear Expectation Theory

Wen-Xuan Lang, Shaoshi Yang, Jianhua Zhang, Zhiming Ma

cs.IT ·submitted 2026-08-17 13:16 UTC · v2
theory

Abstract

In classical information theory, a source is modeled by a single, precisely known probability distribution. However, in the increasingly complex communication networks full of unanticipated, nonstationary, and heterogeneous random events, the assumption of precise and well-defined probability distributions to describe random variables appears somewhat idealized. Therefore, it is important to characterize the uncertainty of distributions of source messages, subject to relaxing the assumption of deterministic probability models for analyzing information sources in information theory. Based on the nonlinear expectation theory, a novel axiomatical system that extends classical probability theory, this paper investigates the information sources whose distributions themselves are uncertain, and refers to them as uncertain-distribution sources. We generalize the fundamental concept information entropy to nonlinear information entropy, which describes the measurement of the amount of information contained in a uncertain-distribution source. By using the strong law of large numbers under sublinear expectation, we establish a nonlinear source coding theorem, which not only shows that the nonlinear information entropy is the upper bound for the infimum of achievable coding rate of uncertain-distribution sources under the maximum error probability criterion, but also determines a cluster point of the coding rate of uncertain-distribution sources under the minimum error probability criterion. Our findings reveal that the introduction of nonlinear expectation theory allows for a more comprehensive understanding of information sources.

Comment
6 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Functional Information, Optimal Channel Simulation and Lossy Source Coding

cs.IT ·2026-11-15 ·Gergely Flamich, Spencer Hill, Fady Alajaji, Tamás Linder
similarity 0.62
Abstract

We characterize, within a constant number of bits, the minimum achievable rate for several one-shot coding problems, such as channel simulation and lossy source coding. The basis of our work is a new information measure between random variables $X, Y$ that we call the functional information $I_F(X \to Y)$. We show that this quantity characterizes the minimum one-shot rate $R^*(X \to Y)$ of channel simulation, in which a sample $Y \sim P_{Y \mid X}$ is communicated in the presence of common randomness: $I_F(X \to Y) \leq R^*(X \to Y) < I_F(X \to Y) + 1.45$. For the achievability result, we construct an explicit code using the Poisson functional representation. Using these results, we develop new bounds for one-shot variable-rate lossy source coding: given some distortion measure $Δ$, we use $I_F(X \to Y)$ to define the functional rate-distortion function $R_F$. Then, letting $R_O$ denote the one-shot operational rate-distortion function with private encoder randomness and distortion measure $Δ$, we make use of our channel simulation result to show that $R_F(D) \leq R_O(D) < R_F(D) + 2.45$ at every positive distortion level $D$. Finally, we generalize our channel simulation result by introducing the Rényi $α$-functional information $I_{F, α}(X \to Y)$ and show that it characterizes the minimum Arimoto-Rényi conditional entropy for channel simulation, ${R^*_α(X \to Y)}$, associated with the Campbell cost: ${I_{F, α}(X \to Y) \leq R^*_α(X \to Y) \leq I_{F, α}(X \to Y) + O(1/α)}$.

0.22

A Mathematical Theory of Pragmatic Information

cs.IT cs.AIcs.ROeess.SY ·2026-09-10 ·Kai Niu, Ping Zhang
similarity 0.60
Abstract · 152 pages, 18 figures

We propose a mathematical theory of pragmatic information that connects communication, control, and decision-making. Its central notion is the isoteleia mapping, which formalizes equifinality: distinct semantic paths that lead to the same optimal action are treated as pragmatically equivalent. This mapping yields a three-tier hierarchy of syntactic, semantic, and pragmatic information, in which each successive abstraction removes distinctions that are irrelevant to the task. We then define pragmatic entropy, up/down pragmatic mutual information, channel capacity, and rate-distortion, and prove lossless source coding, channel coding, and rate-distortion theorems that extend Shannon's results. These measures quantify decision uncertainty, reliable transmission, and task-oriented compression at the level of terminal actions. We further introduce pragmatic value of information (VoI) and pragmatic cost of information (CoI) as decision-theoretic duals to rate-distortion and capacity, and develop a Lagrangian dual framework for cross-layer optimization. The resulting pragmatic efficiency bound $\mathcal{E}_p(λ)=\sup_R[Φ_p(R)-λ\mathrm{CoI}_p(R)]$ characterizes the maximum net utility attainable by a resource-constrained intelligent system under a given resource price, yielding a behavioral capacity that extends Shannon's symbol-level capacity to goal-directed action. Extensions to continuous messages provide closed-form expressions for Gaussian channels and sources, while dynamic settings are addressed through a Bellman equation for sequential decision-making. The framework supports task-oriented communication, networked control, autonomous systems, and embodied AI by shifting emphasis from symbol fidelity to the effectiveness of information in guiding actions. In this way, it offers a common language for systems that extract value from information under resource constraints.

0.24

Generative Rate-Distortion-Perception Theory on Riemannian Manifolds

cs.IT ·2026-10-28 ·Tong Wu, Zhiyong Chen, Meixia Tao, Dazhi He, Feng Yang +1 more
theory similarity 0.59
Abstract

Generative communication uses transmitted information to control stochastic generation at the receiver. A fundamental question is how much source-specific information must be communicated so that outputs generated at the receiver satisfy prescribed fidelity and reliability requirements while preserving the conditional source distribution. We address this question for sources on compact Riemannian manifolds by developing a generative rate-distortion-perception (GRDP) framework without common randomness. We formulate an asymptotic operational GRDP function under a geodesic distortion radius and a failure-probability constraint, and establish its single-letter characterization through an equivalent informational formulation. Furthermore, for the informational formulation with the high-reliability limit, we derive a geometric lower bound determined by the largest source probability mass of a region with bounded geodesic diameter, together with an upper bound based on probabilistic coverings of the source manifold. Small-radius analysis of the lower bound reveals the roles of intrinsic dimension and scalar curvature in the required communication rate. For uniformly distributed sources on compact homogeneous Riemannian manifolds, we prove that the bounds coincide, yielding an exact characterization of the limiting GRDP function. We further specialize this result to unit spheres, obtaining an explicit expression that relates the minimum communication rate to the geodesic distortion radius and intrinsic dimension, revealing that for the $d$-dimensional unit sphere with $d\ge2$, increasing the communication rate by $d$ bits per source symbol can reduce the distortion radius by more than half.

0.25

Distortion-Rate Outage Probability for Non-ergodic Classes of Sources

cs.IT ·2026-10-23 ·Dongmin Park, Ibrahim Abou-Faycal, Razane Tajeddine
similarity 0.59
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.

0.26

Exact Redundancy under Average and Almost-Sure Distortion Constraints

cs.IT ·2026-11-15 ·Yijun Fan
hot direction similarity 0.59
Abstract

We characterize the exact redundancy of lossy source coding under average and almost-sure distortion constraints. For general source and output alphabets, we establish the asymptotic redundancy coefficients under suitable regularity conditions. Under the average distortion constraint, the coefficient is half of the minimum probability that an output reveals information about the source, among all rate-distortion optimal channels. Under the almost-sure distortion constraint, the coefficient is either $1/2$ or $1$, depending on whether the $D$-tilted information is constant or not. Both converse results follow from a common change-of-measure inequality. Finally, we verify the required conditions under both distortion requirements always hold for finite alphabets.

0.23

Optimal Min-Entropy Estimation with High Probability

cs.IT math.STquant-ph ·2026-11-17 ·Qisheng Wang
similarity 0.58
Abstract · 9 pages

Min-entropy plays a fundamental role in assessing the unpredictability of randomness sources. In particular, NIST SP 800-90B specifies min-entropy estimation as a key procedure for entropy sources used in cryptographic random bit generators, illustrating the practical importance of reliable min-entropy estimation. In this paper, we settle the sample complexity of min-entropy estimation with high probability in both the classical and quantum cases. Specifically, for min-entropy estimation with additive error $\varepsilon$ and probability at least $1-δ$, the sample complexity is $Θ(d\log(d/δ)/\varepsilon^2)$ for classical distributions on $d$ symbols and $Θ((d^2+d\log(1/δ))/\varepsilon^2)$ for quantum states on a $d$-dimensional Hilbert space. Our results admit short and simple proofs.

0.38

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.58
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

Distributional statistics of nonequilibrium

cs.IT cond-mat.stat-mechmath.PRphysics.data-an ·2026-10-24 ·Harrison Hartle, Aanjaneya Kumar, David H. Wolpert
similarity 0.58
Abstract · 23 pages, 5 figures

We establish a reference modeling framework for random probability distributions subject to constraints. Generalizing the hyperensemble approach of Crooks, we formulate Jaynesian priors of maximal uncertainty over the unit simplex of categorical distributions. This framework is entirely general, but we primarily investigate models with constraints on physically relevant quantities, namely, average energy and Shannon entropy. A constraint on the exact value of average energy uniquely determines a Boltzmann-Gibbs equilibrium, but also defines a hyperplanar subset of the probability simplex consisting of all distributions with that value of average energy. The associated hyperensemble has a uniform probability density across all such distributions, regardless of distance to equilibrium. Such reference models make predictions of generic nonequilibrium properties such as the mean and modal microstate distributions and the expected free energy of a random distribution, which we examine analytically and via exact sampling algorithms. Moreover, introducing constraints on Shannon entropy permits parametric access to tunably nonequilibrium regimes. The approach follows conventional Jaynesian modeling logic and is compatible with standard Bayesian inference, and reduces to Boltzmann-Gibbs statistics when Shannon entropy is maximized. We examine the physical predictions of this scheme, and demonstrate its wide compatibility with other approaches to nonequilibrium modeling. We illustrate the framework in three scenarios: (i) comparison to superstatistics quasi-equilibrium modeling, (ii) generation of random nonequilibrium steady states, and (iii) Bayesian inference under a prior hyperensemble. We highlight numerous prospects for theoretical extensions and empirical application.

0.25