CS Paper Radar

Revisiting entropy and entropy-related magnitudes of a symbolic sequence and their estimation

Efren Aragon-Perez, Ania Mesa-Rodriguez, Karel Garcia-Medina, Daniel Estevez-Moya, Amanda Mollineda-Rodriguez, Ernesto Estevez-Rams

cs.IT nlin.CDphysics.data-an ·submitted 2026-10-26 09:58 UTC · v1
theorycode/data

Abstract

This article revisits entropy and related magnitudes (entropy density, effective measure complexity, and informational distance) for the analysis of sequential data. We present their mathematical foundations within information theory and ergodic theory, establishing connections between probabilistic Shannon entropy and algorithmic Kolmogorov complexity. A central result, Zivs theorem, demonstrates the asymptotic equivalence between the normalised number of distinct words and entropy density, providing the theoretical basis for estimation via Lempel-Ziv factorisation. We examine the convergence properties of these magnitudes and introduce estimation procedures for finite sequences, including a method for the effective measure complexity and the transfer entropy rate. An open-source software library implementing parallel algorithms for efficient Lempel-Ziv factorisation is presented. The practical utility of the framework is illustrated through three case studies: functional brain connectivity analysis from fMRI data, characterisation of spatiotemporal dynamics in coupled nonlinear oscillators, and electrocardiogram-based classification of atrial fibrillation, demonstrating how entropic measures capture meaningful structural and dynamical properties across diverse domains.

Closest papers

Nearest neighbours by meaning across the whole index.

Information Estimation with Discrete Diffusion

cs.LG cs.IT ·2026-10-16 ·Alberto Foresti, Giulio Franzese, Pietro Michiardi
top venuecode/datahighly cited similarity 0.56
Abstract · Published as a conference paper at ICLR 2026 (Poster). ICLR Paper: https://proceedings.iclr.cc/paper_files/paper/2026/file/238747e153a84f50b…

Information-theoretic measures, such as Mutual Information (MI), play a crucial role in understanding non-linear relationships between random variables and are widely used across scientific disciplines. Yet, their use on real-world discrete data remains challenging. Existing methods typically rely on embedding discrete data into a continuous space and apply neural estimators originally designed for continuous distributions. This process requires careful engineering for both the embedding model and estimator architecture, but suffers from issues related to high data dimensionality. In this work, we introduce InfoSEDD, a discrete diffusion-based approach that bridges information-theoretic estimation and generative modeling such that they can be used to compute Kullback-Leibler divergences. Backed by Continuous Time Markov Chains theory principles, the design of InfoSEDD is lightweight and scalable and allows seamless integration with pretrained models. We showcase the versatility of our approach through applications on motif discovery in genetic promoter data, semantic-aware model selection in text summarization, and entropy estimation in Ising models. Finally, we construct consistency tests on real-world textual and genomics data. Our experiments demonstrate that InfoSEDD outperforms alternatives that rely on the "embedding trick". Our results position InfoSEDD as a robust and scalable tool for information-theoretic analysis of discrete data.

0.73

Sorted Mutability as an Entropic Functional: Theory and Two Applications

cs.IT physics.data-an ·2026-10-06 ·Michel Aguilera, Eugenio E. Vogel, Francisco J. Peña, Gonzalo Saravia, Patricio Vargas
unusual similarity 0.56
Abstract · 12 pages, 11 figures

We investigate sorted mutability, $ζ_S$, as an information-based quantity with an explicit entropic character. We show that $ζ_S$ is directly proportional to the diversity of a data sequence and can therefore be expressed in terms of Shannon entropies, establishing a connection between compression-based measures and conventional information theory. In contrast to regular mutability, which preserves the sequential ordering of the data, sorted mutability removes this ordering and provides a static characterization of the distribution of observed values. We illustrate these properties in two complementary settings: the two-dimensional ferromagnetic Q-clock model and wind-power production data. For the Q-clock model, sorted mutability and diversity display the same temperature dependence, consistent with their analytical relation, while conventional thermodynamic observables provide an independent reference. In the case of wind power, we report monthly results for sorted mutability and diversity, showing proportional time evolutions. These results support sorted mutability as a useful, easy-to-calculate entropic functional for analyzing both equilibrium and non-equilibrium data sets.

0.31

If the brain were so simple: Information-based drivers of intelligence and their interaction through an n-body-inspired framework

cs.IT q-bio.NCnlin.AOphysics.bio-ph ·2026-10-08 ·Brett J. Kagan, Johnson Zhou, Forough Habibollahi, Valentina Baccetti
similarity 0.55
Abstract

Theories of how the brain processes information and returns intelligent outputs are numerous and often difficult to conclusively test. Here, we consider an approach grounded in informatics and algorithmic thermodynamics for how neural systems respond to different patterns of information in different ways, with a focus on the relationship between the information entropy of a signal and a new proposed quantity we term information enthalpy, which represents the internal resource of structured information within a system available to be used for predictions and other forms of work. To evaluate the capacity of the external signals to increase information enthalpy in the system, we introduce the information enthalpy potential (IEP) as a defined metric. We propose and implement a method for quantifying the amount of potential information enthalpy - the IEP - in a given signal across a range of example signals. We offer a conjecture of how information enthalpy may be treated by neural systems within a biological framework before showing how it may integrate and offer falsifiability to existing approaches such as the Free Energy Principle. This framework is also positioned in light of the role of neural criticality. Finally, we postulate a testable and falsifiable framework where the distinct mechanisms within each driver interact through a described n-body-inspired model to govern the "motion" of a neural system through a high dimensional state-space. Through these processes, it is proposed that these features form the most fundamental basis of the neural drivers that give rise to the complexity of adaptive behaviors that are commonly called: intelligence.

0.31

Settling the Sample Complexity of Rényi Entropy Estimation

cs.IT cs.DSmath.ST ·2026-10-07 ·Qisheng Wang
theory similarity 0.55
Abstract · 23 pages, 1 table

Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger $α> 0$, it is sufficient and necessary to use \[ Θ\!\left(\frac{d^{\max\{1/α,1\}}}{\varepsilon^{1/α}\log(d)} + \frac{d^{|1-1/α|}}{\varepsilon^2}\right) \] samples to estimate the Rényi entropy of order $α$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the $α$-th moments, which is of independent interest.

0.20

Optimal mixing of the systematic scan dynamics via approximate tensorization of entropy

cs.DM math.PR ·2026-09-04 ·Antonio Blanca, Md Tahmidur Rafid
similarity 0.53
Abstract

We study the mixing time of the systematic scan dynamics for high-dimensional discrete distributions. This Markov chain updates coordinates sequentially according to a fixed predetermined order, in contrast to the Glauber dynamics that updates coordinates selected uniformly at random. The systematic scan is often favored in practice because it exhibits strong empirical performance, but its theoretical analysis remains far less developed than that of Glauber dynamics. We take a step toward addressing this imbalance by showing that two standard functional notions of weak dependence between the coordinates of the distribution provide strong convergence guarantees for the systematic scan dynamics. First, we show that approximate tensorization of entropy implies optimal $O(\log n)$ mixing time for every scan order under standard marginal, connectivity, and bounded interaction degree assumptions about the distribution. Second, we show that approximate tensorization of variance yields a constant-factor contraction of the variance functional per scan, which in turn implies an optimal $O(1)$ relaxation time for the natural additive and multiplicative reversibilizations of the systematic scan dynamics. Compared with our entropy result, the variance bound improves the dependence on the maximum interaction degree from exponential to quadratic and requires weaker assumptions on the distribution. As concrete applications of our results, we establish optimal $O(\log n)$ mixing of the systematic scan dynamics for bounded-degree antiferromagnetic two-spin systems in the tree-uniqueness region and for the ferromagnetic $q$-state Potts model on square boxes in $\mathbb{Z}^2$ throughout its subcritical regime.

0.28

A Mathematical Framework for EEG Functional Connectivity: Taxonomy, Measure Relationships, Identifiability, and Analytical Bounds

eess.SP ·2026-10-17 ·Jerrin Thomas Panachakel
similarity 0.52
Abstract

Electroencephalographic (EEG) functional connectivity is quantified using diverse measures of statistical dependence, spectral coupling, phase synchronization, information transfer, directed interactions, cross-frequency coupling, and network topology. An important question is what can be inferred about one connectivity measure from another. This paper develops a mathematical framework that treats connectivity measures as mappings from an explicitly defined admissible state space to observable values. For a source measure and a target measure, the set of target values compatible with an observed source value is defined as a cross-connectivity attainable set. This formulation distinguishes exact determination, conditional determination using additional information, bounded inference, approximate identification, and non-identifiability. The framework is extended to multichannel connectivity matrices, graph measures, and dynamic connectivity. It also incorporates the influence of filtering, referencing, volume conduction, source leakage, inverse modeling, epoch duration, and estimator assumptions on admissible inferences. Analytical examples examine relationships between covariance and correlation, mutual information and correlation under joint Gaussianity, coherence and phase-locking value under restrictive signal conditions, and the general non-identifiability of the phase-lag index and weighted phase-lag index without additional assumptions. By making assumptions and attainable values explicit, the framework provides a systematic basis for determining what connectivity results can and cannot establish about other measures.

0.18

Learning, Compression, and Meta-Complexity

cs.CC cs.LG ·2026-10-12 ·Halley Goldberg, Mikito Nanashima, Igor C. Oliveira
published similarity 0.51
Abstract

The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. Here we focus on settings in which that intuition can be made mathematically precise, surveying formal connections among learning algorithms, data compression, and computational complexity theory, with an emphasis on recent progress and current frontiers. We describe how techniques from complexity theory can guide the design of both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how learning algorithms can yield new insights and results in complexity theory. A central theme is the role of data compression as a bridge between learning and complexity, especially through an area called meta-complexity, which studies the computational difficulty of compression problems and time-bounded variants of Kolmogorov complexity.

0.39

Maximal input entropy for binary two-deletion and two-insertion channels

cs.IT cs.FLmath.CO ·2026-10-31 ·Haobo Ma, Wenlin Zhang
similarity 0.50
Abstract · 12 pages; exact enumeration code, outputs and Lean companion in ancillary files

Under uniform transmission, we determine the received binary words that maximize input entropy for two-deletion and two-insertion channels. For two deletions the maximizers are exactly the two alternating words at every positive received length. For two insertions the same conclusion holds from received length five onward; we give all smaller cases and exact maximal values. The proof combines an embedding-count identity organized by runs with strict convexity estimates, and a grouping of two-position deletion masks. For every insertion radius we give the complete positive embedding histogram of an alternating received word. We also determine its three-deletion histogram for every length, and certify all three-deletion maximizers through received length twelve and all three-insertion maximizers through length eighteen by exact integer comparison. These computations give precise three-error conjectures with their small-length exceptions.

0.12