Entropy estimation of symbol sequences

Abstract

We discuss algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations. In particular, we consider algorithms which estimate h from the code lengths produced by some compression algorithm. Our interest is in describing their convergence with sequence length, assuming no limits for the space and time complexities of the compression algorithms. A scaling law is proposed for extrapolation from finite sample lengths. This is applied to sequences of dynamical systems in non-trivial chaotic regimes, a 1-D cellular automaton, and to written English texts.

14 pages, 13 figures, 2 tables

References in corpus (2)

• Entropy and Long range correlations in literary English
• Enlarged scaling ranges for the KS-entropy and the information dimension

Cited by in corpus (75)

• Equitability, mutual information, and the maximal information coefficient
• Entropy inference and the James-Stein estimator, with application to nonlinear gene association networks
• Estimating dissipation from single stationary trajectories
• Entropy production and Kullback-Leibler divergence between stationary trajectories of discrete systems
• Mutual Information Rate-Based Networks in Financial Markets
• The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing
• Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Structural Information in Two-Dimensional Patterns: Entropy Convergence and Excess Entropy
• Entropy estimates of small data sets
• Natural Language Statistical Features of LSTM-generated Texts
• Estimating the entropy of binary time series: Methodology, some theory and a simulation study
• Information-theoretic measurements of coupling between structure and dynamics in glass-formers
• Key Generation in Wireless Sensor Networks Based on Frequency-selective Channels - Design, Implementation, and Analysis
• The statistical trade-off between word order and word structure - large-scale evidence for the principle of least effort
• Complexity Through Nonextensivity
• Information flow reveals prediction limits in online social activity
• Inference of entropies of discrete random variables with unknown cardinalities
• Quantifying the dynamical complexity of time series
• Towards the quantification of the semantic information encoded in written language
• Information Content of Turbulence
• Gibbs distribution analysis of temporal correlations structure in retina ganglion cells
• Exploring Temporal Networks with Greedy Walks
• Distinct word length frequencies: distributions and symbol entropies
• Random Language Model
• Information-theoretic approach to lead-lag effect on financial markets
• Experiments on predictability of word in context and information rate in natural language
• Identifying delayed directional couplings with symbolic transfer entropy
• On the non-randomness of maximum Lempel Ziv complexity sequences of finite size
• Authentication of optical physical unclonable functions based on single-pixel detection
• Estimating probabilities from experimental frequencies
• Estimation of the Rate-Distortion Function
• Non-invasive estimation of dissipation from non-equilibrium fluctuations in chemical reactions
• Maximally predictive states: from partial observations to long timescales
• Human Languages with Greater Information Density Increase Communication Speed, but Decrease Conversation Breadth
• Mixing Bandt-Pompe and Lempel-Ziv approaches: another way to analyze the complexity of continuous-states sequences
• Large deviations for empirical entropies of Gibbsian sources
• Analysis of the phase transition in the $2D$ Ising ferromagnet using a Lempel-Ziv string parsing scheme and black-box data-compression utilities
• Entropy and hierarchical clustering: characterising the morphology of the urban fabric in different spatial cultures
• The word entropy of natural languages
• Phenomenology of coupled non linear oscillators
• A note on entropy estimation
• Measuring complexity with zippers
• Complexity-entropy analysis at different levels of organization in written language
• Non-equilibrium Dynamics, Thermalization and Entropy Production
• Non Sequential Recursive Pair Substitution: Some Rigorous Results
• Breakdown of random matrix universality in Markov models
• Entropy estimators for Markovian sequences: A comparative analysis
• Calculating entropy at different scales among diverse communication systems
• Fluctuations of the Empirical Entropies of a Chain of Infinite Order
• Mutual information as a measure of mixing efficiency in viscous fluids
• The quoter model: a paradigmatic model of the social flow of written information
• Partial Mutual Information Analysis of Financial Networks
• Scaling behaviour of entropy estimates
• Estimating entropy rate from censored symbolic time series: a test for time-irreversibility
• Computational capabilities at the edge of chaos for one dimensional system undergoing continuous transitions
• Entropy of finite random binary sequences with weak long-range correlations
• Artificial Sequences and Complexity Measures
• Entropy-based parametric estimation of spike train statistics
• Complexity and transition to chaos in coupled Adler-type oscillators
• Entropy estimation in bidimensional sequences
• Minimax Optimal Estimators for Additive Scalar Functionals of Discrete Distributions
• The distribution of information content in English sentences
• From form to information: Analysing built environments in different spatial cultures
• Profile Entropy: A Fundamental Measure for the Learnability and Compressibility of Discrete Distributions
• Symbolic partition in chaotic maps
• Non-linear oscillators with Kuramoto-like local coupling: Complexity analysis and spatiotemporal pattern generation
• On the analysis of signals in a permutation Lempel-Ziv complexity - permutation Shannon entropy plane
• Cryptocurrency Time Series on the Binary Complexity-Entropy Plane: Ranking Efficiency from the Perspective of Complex Systems
• Comment on "Universal and accessible entropy estimation using a compression algorithm"
• Information Theory of Meaningful Communication
• PolyMorph: Increasing P300 Spelling Efficiency by Selection Matrix Polymorphism and Sentence-Based Predictions
• A computational mechanics approach to estimate entropy and (approximate) complexity for the dynamics of the 2D Ising Ferromagnet
• Turbulence as Information
• Markov Chain Analysis of Musical Dice Games