# Computing entropy rate of symbol sources & a distribution-free limit theorem

@article{Chattopadhyay2014ComputingER, title={Computing entropy rate of symbol sources \& a distribution-free limit theorem}, author={Ishanu Chattopadhyay and Hod Lipson}, journal={2014 48th Annual Conference on Information Sciences and Systems (CISS)}, year={2014}, pages={1-6} }

Entropy rate of sequential data-streams naturally quantifies the complexity of the generative process. Thus entropy rate fluctuations could be used as a tool to recognize dynamical perturbations in signal sources, and could potentially be carried out without explicit background noise characterization. However, state of the art algorithms to estimate the entropy rate have markedly slow convergence; making such entropic approaches non-viable in practice. We present here a fundamentally new… Expand

#### 5 Citations

A high probability bound on the mutual information across an observed Discrete Memoryless Channel

- Mathematics, Computer Science
- 2015 49th Annual Conference on Information Sciences and Systems (CISS)
- 2015

Several new high probability bounds on the average mutual information, I (X; Y) between the input and output of a Discrete Memoryless Channel (DMC) based on a set of observed input-output samples are introduced. Expand

Causality Networks

- Computer Science, Mathematics
- ArXiv
- 2014

This work presents a new non-parametric test of Granger causality for quantized or symbolic data streams generated by ergodic stationary sources, and makes precise and computes the degree of causal dependence between data streams, without making any restrictive assumptions, linearity or otherwise. Expand

A Tamper-Free Semi-Universal Communication System for Deletion Channels

- Mathematics, Computer Science
- 2018 IEEE Conference on Decision and Control (CDC)
- 2018

A theoretical framework based on probabilistic finite-state automata is developed to define novel encoding and decoding schemes that ensure small error probability in both message decoding as well as tamper detecting. Expand

Universal risk phenotype of US counties for flu-like transmission to improve county-specific COVID-19 incidence forecasts

- Medicine
- PLoS computational biology
- 2021

This study demonstrates that knowledge of past epidemics may be used to chart the course of future ones, if transmission mechanisms are broadly similar, despite distinct disease processes and causative pathogens. Expand

#### References

SHOWING 1-10 OF 32 REFERENCES

Entropy estimation of symbol sequences.

- Mathematics, Physics
- Chaos
- 1996

Algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations are considered, and a scaling law is proposed for extrapolation from finite sample lengths. Expand

Compression of individual sequences via variable-rate coding

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1978

The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. Expand

Estimating the information content of symbol sequences and efficient codes

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1989

Several variants of an algorithm for estimating Shannon entropies of symbol sequences are presented, which seem to be the optimal algorithms for sequences with strong long-range correlations, e.g. natural languages. Expand

Numerical Methods for Computing Stationary Distributions of Finite Irreducible Markov Chains

- Mathematics
- 2000

In this chapter our attention will be devoted to computational methods for computing stationary distributions of finite irreducible Markov chains. We let q ij denote the rate at which an n-state… Expand

The sliding-window Lempel-Ziv algorithm is asymptotically optimal

- Computer Science
- 1994

The sliding-window version of the Lempel-Ziv data-compression algorithm is described, and it is shown that as the "window size," a quantity related to the memory and complexity of the procedure, goes to infinity, the compression rate approaches the source entropy. Expand

Elements of Information Theory

- Engineering, Computer Science
- 1991

The author examines the role of entropy, inequality, and randomness in the design of codes and the construction of codes in the rapidly changing environment. Expand

PAC-Learning of Markov Models with Hidden State

- Computer Science, Mathematics
- ECML
- 2006

This work proposes a new PAC framework for learning both the topology and the parameters in partially observable Markov models, and learns a Probabilistic Deterministic Finite Automata (PDFA) which approximates a Hidden Markov Model (HMM) up to some desired degree of accuracy. Expand

A note on Kolmogorov complexity and entropy

- Mathematics, Computer Science
- Appl. Math. Lett.
- 2003

It is shown that the Kolmogorov complexity per symbol of an n-sequence from a stationary ergodic source of finite alphabet approaches the entropy rate of the source in probability as n becomes large.

Probabilistic finite-state machines - part I

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2005

The relation of probabilistic finite-state automata with other well-known devices that generate strings as hidden Markov models and n-grams is studied and theorems, algorithms, and properties that represent a current state of the art of these objects are provided. Expand

Abductive learning of quantized stochastic processes with probabilistic finite automata

- Mathematics, Medicine
- Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2013

We present an unsupervised learning algorithm (GenESeSS) to infer the causal structure of quantized stochastic processes, defined as stochastic dynamical systems evolving over discrete time, and… Expand