CS Paper Radar

Information, Estimation, and Prediction for Discrete Memoryless Channels via Poissonization

Abhiram Gorle, Tsachy Weissman

cs.IT ·submitted 2026-10-20 07:02 UTC · v2

Abstract

We develop information--estimation relations for an arbitrary discrete memoryless channel with finite input and output alphabets by varying the expected number of observations while keeping the channel fixed. A single hidden input is observed through a \textit{Poisson} number of conditionally independent channel uses, whose mean specifies the observation budget. The derivative of mutual information with respect to this budget equals the minimum expected relative-entropy loss for estimating the input's output distribution. The posterior average of the channel's output distributions achieves this minimum and is the Bayesian predictor for the next observation. When the input distribution, the channel, or both are misspecified, the relative entropy between the true and assumed observation laws is the integral of the excess prediction loss over the budget. We also extend these relations to finite-state processes taking values in the input alphabet and observed through the channel at independent Poisson sampling times. Both in the matched setting and under model mismatch, the expected prediction loss accumulated over time using past observations equals the corresponding loss using the full observation record (noncausal estimation), averaged over lower sampling rates. We also characterize how redundancy between two outputs selects among input distributions that achieve one-use capacity. For the coupon-collector channel, where each observation is sampled uniformly from an unknown subset, we derive the exact capacity loss of any input distribution. In particular, balanced subset families can substantially reduce the input alphabet while preserving the leading capacity terms.

Closest papers

Nearest neighbours by meaning across the whole index.

Intrinsic Information Rates of Summaries in Simulation-Based Inference

cs.LG stat.MLstat.CO ·2026-10-26 ·Vansh Bansal, Pradip Sharma Poudel, James G. Scott
similarity 0.65
Abstract

Simulation-based inference often encodes observations $Y$ into a fixed-dimensional summary $S$, with the posterior conditioning only on $S$. While exact preservation often requires infinite information, any such summary imposes a finite information budget on inference which is rarely an explicit choice or measurement. In this paper, we make the budget explicit by modeling the summary as a lossy channel from $Y$ to $S$, and ask two questions: how large must the budget be, and how best is it spent? First, we show for parametric models that this budget, measured by the mutual information $I(Y;S)$, grows unboundedly as the posterior concentrates, even when fixed-dimensional sufficient statistics exist. More generally, the required budget is set by the distribution of the random posterior, and we bound it from above by quantizing posteriors and from below by converses that weight each posterior state by its probability. Second, we show that a finite budget is best spent stochastically. Under a common-support condition on the simulator, covering the continuous observation spaces typical of simulators, a deterministic summary necessarily loses something: a stochastic summary achieves \emph{strictly} lower distortion than every deterministic summary and every time-shared mixture of deterministic summaries at every positive budget too small for exact preservation. Motivated by these results, we insert a binary bottleneck into neural posterior estimators, measure each trained summary's rate, and compare summaries at matched rate. Across four simulator benchmarks and several encoder families, stochastic bottlenecks achieve favorable rate--loss tradeoffs, and architecture rankings change at different information budgets.

0.38

From Source Reconstruction to Predictive State Preservation: An Information-Theoretic Framework for AI-Native Communication

cs.IT ·2026-09-01 ·Yi Wang, Linglong Dai
similarity 0.64
Abstract

AI-native communication increasingly aims to support prediction rather than reproduce every detail of the source. This shift raises a basic question left implicit by conventional source coding: what should be preserved when the terminal goal is prediction? We take the source-induced predictive state as the fidelity object. It is the distribution of the specified future conditioned on the source observation and shared context. We show that this state is sufficient and minimal for exact predictive preservation. The terminal prediction loss then defines communication distortion as lost predictive performance rather than source reconstruction error. Under logarithmic loss, this distortion equals the conditional mutual information lost through communication. Using the receiver-side predictive state as a Bayes reference, we separate AI-receiver error into predictive value lost in communication, receiver-available value unusable by the model family, and family capability not realized by the deployed model. The same predictive state also suffices for matched compression. For finite-alphabet memoryless sources, access to the raw source gives no rate-distortion advantage over coding the state directly. Applying the same target-conditioned construction to sequential prediction reveals a dynamic boundary. A state induced by a fixed horizon is minimal for that horizon but may not support recursive updating as the target window shifts. Taking the entire future as the target yields a minimal full-future state that updates recursively and admits a Markov representation. Together, these results shift AI communication from source reconstruction to predictive-state preservation.

0.41

Memory Prediction Excess: A Probabilistic Quantity for Predictive Gain and Memory Length in Stochastic Processes

cs.IT stat.MLcs.LGmath.PR ·2026-09-28 ·Jiahao Jiang
theory similarity 0.61
Abstract

A central question in the prediction of stochastic processes is the extent to which past information can improve the probability of correctly predicting the next state. We introduce the Memory Prediction Excess (MPE) to address this question quantitatively. The MPE measures the average improvement in prediction accuracy obtained by using the entire observed history relative to using only the static marginal distribution, in discrete-time finite-state processes. It is defined as the difference between the expected optimal conditional prediction accuracy and the optimal static prediction accuracy. Its basic properties are examined: the MPE is always non-negative; it admits an upper bound depending on the static accuracy, attained if and only if the future is almost surely a deterministic function of the past; and degenerate cases in which the MPE vanishes are characterized. A normalized version, taking values in the unit interval, is introduced as a dimensionless measure of predictive efficiency. A lower bound is derived by comparing predictions based on histories of different lengths, showing that the expected optimal prediction accuracy is monotone with respect to the history length. The framework is extended to finite-length histories, where the finite-history MPE (FH-MPE) measures the predictive gain attainable when only the most recent observations are retained. This leads to the notion of a minimal memory length required to achieve the same predictive performance as the full history. For finite-order Markov chains, this minimal memory length is shown to be bounded by the Markov order. The MPE and its variants are formulated in terms of conditional probabilities and prediction accuracies, offering a probabilistic perspective on the predictive utility of memory that is complementary to classical information-theoretic approaches.

0.27

Information-Theoretic Analysis of Next-Token Prediction under Markovian Data

cs.IT stat.MLcs.LG ·2026-09-28 ·Masoud Kavian, Abdellatif Zaidi, Milad Sefidgaran
similarity 0.60
Abstract · 49 Pages, 6 Figures

We develop an information-theoretic framework for generalization in next-token prediction under temporally dependent data. We consider independent trajectories generated by finite-memory Markov processes and distinguish algorithmic dependence, quantified by mutual information, from temporal dependence, characterized by mixing. For cross-entropy loss, we derive an expected generalization bound using the Donsker--Varadhan variational representation and a McDiarmid-type concentration inequality for Markov chains. A refinement captures the joint effect of context length and temporal mixing through the mixing properties of the history-state process. We then extend the bound through a rate--distortion formulation, replacing mutual information with the minimum information rate required to represent the learned model within a prescribed distortion in the generalization gap, yielding informative guarantees for deterministic algorithms over continuous hypothesis spaces. For margin-based prediction, we derive explicit bounds for linear and self-attention next-token predictors via noisy low-dimensional compression, revealing the roles of context length, model complexity, sample size, margin, and temporal mixing. Experiments on TinyStories and ETTh2 show that longer contexts can reduce both training and test losses, but typically reduce training loss more, enlarging the generalization gap. A complementary ETTh2 analysis identifies an effective predictive-memory scale near 24 hours, with no statistically supported improvement beyond this scale, offering a plausible explanation for test-performance saturation at larger contexts.

0.31

Joint Identification, Transmission, and Sensing over State-Dependent Channels with Noiseless Feedback

cs.IT ·2026-10-14 ·Vida Gholamian, Marcel A. Mross, Roberto Ferrara, Eduard A. Jorswieck, Christian Deppe
similarity 0.59
Abstract

We consider a discrete memoryless state-dependent channel with noiseless feedback, where the transmitter uses randomized encoding to jointly perform message transmission, identification, and state sensing. In this setting, the transmitter sends a conventional transmission message and an identification message while estimating the unknown channel state sequence under an average distortion constraint. We establish a single-letter characterization of the randomized identification-transmission-sensing capacity-distortion region. The result reveals a single-letter separation structure: the communication rates are determined by the averaged channel, subject to the sensing-induced constraint on admissible input distributions. Specifically, the transmission rate is characterized by mutual information, while the identification rate is characterized by output entropy under the same distortion constraint. The achievability proof combines constant-composition transmission coding, output partitioning, and combinatorial identification coding, while the converse follows from an averaged-channel reduction, distortion lower bounds, and feedback-identification converse arguments.

0.22

A Poisson Transition and Bias Law for KSG Mutual-Information Estimation

cs.IT ·2026-10-27 ·Abhiram Gorle, Tsachy Weissman
theory similarity 0.59
Abstract

We quantify the error of the strict-radius Kraskov--Stögbauer--Grassberger (KSG-1) mutual-information estimator on a Gaussian channel as the sample size \(n\) grows and the channel becomes nearly deterministic. For fixed dimension \(p\) and neighbor index \(k\), we define the resolution parameter \(u_n=ne^{-I_n}\), where \(I_n\) is the true mutual information in nats. When \(u_n\to u\in(0,\infty)\), we prove that the estimation error converges in mean square to a computable deterministic bias \(B_{p,k}(u)\). Sampling fluctuations therefore vanish, while an additive bias can persist. We derive this bias from an explicit marked-Poisson law for the neighborhood counts, characterize its small-\(u\) asymptotics, and show that it tends to zero as \(u\to\infty\). The same law describes how often neighborhoods saturate, meaning that they make the largest possible contribution to the estimate. The limiting saturation probability decreases continuously and strictly from one to zero, allowing a Gaussian-model bias correction on fixed critical intervals. Finite-sample experiments show substantial bias even when the true information lies below the estimator's logarithmic ceiling and saturated neighborhoods are rare. Saturation-based correction reduces estimation error in these experiments, though recovering the resolution parameter from the observed saturation fraction can remain difficult when saturation is rare.

0.23

The Sample Complexity of Channel Coding

cs.IT math.ST ·2026-11-16 ·Terence Viaud, Ioannis Kontoyiannis
similarity 0.58
Abstract · 31 pages, 3 figures

We introduce a new framework for the study and evaluation of the fundamental limits of channel coding, emphasizing genuinely nonasymptotic results. The {\em channel coding sample complexity} $n^*({\cal W},ε)$ of a channel ${\cal W}$ is defined as the smallest blocklength at which it is possible to transmit information through that channel with error probability below $ε$ and at a rate at least as high as that given by an appropriate constraint also in terms of $ε$. This formulation follows analogous developments in statistics, computer science and, more recently, in lossless source coding. For any discrete memoryless channel we derive nonasymptotic bounds on the sample complexity, with explicit constants. These bounds show that the sample complexity is characterized not by the usual channel capacity, but by the channel's Augustin--Csiszár capacity of order $1/2$, which coincides with the cutoff rate as well as with the channel's Sibson capacity of order $1/2$. The proof is partly based on a new channel-coding one-shot converse in terms of hypothesis testing. We also examine extensions of the sample complexity framework to general target rates. Moreover, we derive corresponding results for the sample complexity of the additive white Gaussian noise channel with a quadratic power constraint. Their proof relies on new, explicit upper bounds on the best achievable error probability, which may be of independent interest.

0.17

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

cs.IT ·2026-10-11 ·Yijun Fan, Aaron B. Wagner
similarity 0.58
Abstract

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

0.20