A Review of Shannon and Differential Entropy Rate Estimation

In this paper, we present a review of Shannon and differential entropy rate estimation techniques. Entropy rate, which measures the average information gain from a stochastic process, is a measure of uncertainty and complexity of a stochastic process. We discuss the estimation of entropy rate from empirical data, and review both parametric and non-parametric techniques. We look at many different assumptions on properties of the processes for parametric processes, in particular focussing on Markov and Gaussian assumptions. Non-parametric estimation relies on limit theorems which involve the entropy rate from observations, and to discuss these, we introduce some theory and the practical implementations of estimators of this type.     

Variational principle for regular and random Ising models on the cactus tree or on the usual lattice in the “cactus approximation”

The distribution functions and the free energy are expressed in terms of the effective fields for the regular and random Ising models of an arbitrary spin S on the generalized cactus tree. The same expressions apply to systems on the usual lattice in the “cactus approximation” in the cluster variation method. For an ensemble of random Ising models of an arbitrary spin S on the generalized cactus tree, the equation for the probability distribution function of the effective fields is set up and the averaged free energy is expressed in terms of the probability distribution. The same expressions apply to the system on the usual lattice in the “cactus approximation”. We discuss the quantities on the usual lattice when the system or the ensemble of random systems has the translational symmetry. Variational properties of the free energy for a system and of the averaged free energy for an ensemble of random systems are noted. The “cactus approximations” are applicable to the Heisenberg model as well as to the Ising model of an arbitrary spin, and to ensembles of random systems of these models.     

A new complexity measure for time series analysis and classification

Complexity measures are used in a number of applications including extraction of information from data such as ecological time series, detection of non-random structure in biomedical signals, testing of random number generators, language recognition and authorship attribution etc. Different complexity measures proposed in the literature like Shannon entropy, Relative entropy, Lempel-Ziv, Kolmogrov and Algorithmic complexity are mostly ineffective in analyzing short sequences that are further corrupted with noise. To address this problem, we propose a new complexity measure ETC and define it as the “Effort To Compress” the input sequence by a lossless compression algorithm. Here, we employ the lossless compression algorithm known as Non-Sequential Recursive Pair Substitution (NSRPS) and define ETC as the number of iterations needed for NSRPS to transform the input sequence to a constant sequence. We demonstrate the utility of ETC in two applications. ETC is shown to have better correlation with Lyapunov exponent than Shannon entropy even with relatively short and noisy time series. The measure also has a greater rate of success in automatic identification and classification of short noisy sequences, compared to entropy and a popular measure based on Lempel-Ziv compression (implemented by Gzip).     

The Szilard engine revisited: Entropy,macroscopic randomness,and symmetry breaking phase transitions

The role of symmetry breaking phase transitions in the Szilard engine is analyzed. It is shown that symmetry breaking is the only necessary ingredient for the engine to work. To support this idea, we show that the Ising model behaves exactly as the Szilard engine. We design a purely macroscopic Maxwell demon from an Ising model, demonstrating that a demon can operate with information about the macrostate of the system. We finally discuss some aspects of the definition of entropy and how thermodynamics should be modified to account for the variations of entropy in second-order phase transitions. (c) 2001 American Institute of Physics.     

Physical complexity of variable length symbolic sequences

A measure called physical complexity is established and calculated for a population of sequences, based on statistical physics, automata theory, and information theory. It is a measure of the quantity of information in an organism’s genome. It is based on Shannon’s entropy, measuring the information in a population evolved in its environment, by using entropy to estimate the randomness in the genome. It is calculated from the difference between the maximal entropy of the population and the actual entropy of the population when in its environment, estimated by counting the number of fixed loci in the sequences of a population. Up until now, physical complexity has only been formulated for populations of sequences with the same length. Here, we investigate an extension to support variable length populations. We then build upon this to construct a measure for the efficiency of information storage, which we later use in understanding clustering within populations. Finally, we investigate our extended physical complexity through simulations, showing it to be consistent with the original.     

Complexity of two-dimensional patterns

To describe quantitatively the complexity of two-dimensional patterns we introduce a complexity measure based on a mean information gain. Two types of patterns are studied: geometric ornaments and patterns arising in random sequential adsorption of discs on a plane (RSA). For the geometric ornaments analytical expressions for entropy and complexity measures are presented, while for the RSA patterns these are calculated numerically. We compare the information-gain complexity measure with some alternative measures and show advantages of the former one, as applied to two-dimensional structures. Namely, this does not require knowledge of the “maximal” entropy of the pattern, and at the same time sensitively accounts for the inherent correlations in the system. Received 12 November 1999     

Dilute antiferromagnets: Imry-Ma argument,hierarchical model,and equivalence to random field Ising models

We discuss some aspects of the problem of the equivalence of dilute antiferromagnets and random field Ising models. We first investigate for dilute antiferromagnets the validity of the arguments of Imry and Ma. It turns out that they are applicable, but some care is required concerning the role played by the so-called internal Peierls contours. Next we consider a hierarchical version of a dilute antiferromagnetic Ising model in the presence of a uniform magnetic field and show that a renormalization group transformation maps it exactly into a hierarchical version of the random field Ising model, thus proving their equivalence as far as the critical behavior is concerned. In particular this implies that phase transition with spontaneous magnetization occurs only for dimensiond>2. Finally we show that in the absence of internal Peierls contours both models, in their hierarchical versions, exhibit phase transition already in dimensiond=2.     

Permutation approach to finite-alphabet stationary stochastic processes based on the duality between values and orderings

The duality between values and orderings is a powerful tool to discuss relationships between various information-theoretic measures and their permutation analogues for discrete-time finite-alphabet stationary stochastic processes (SSPs). Applying it to output processes of hidden Markov models with ergodic internal processes, we have shown in our previous work that the excess entropy and the transfer entropy rate coincide with their permutation analogues. In this paper, we discuss two permutation characterizations of the two measures for general ergodic SSPs not necessarily having the Markov property assumed in our previous work. In the first approach, we show that the excess entropy and the transfer entropy rate of an ergodic SSP can be obtained as the limits of permutation analogues of them for the N-th order approximation by hidden Markov models, respectively. In the second approach, we employ the modified permutation partition of the set of words which considers equalities of symbols in addition to permutations of words. We show that the excess entropy and the transfer entropy rate of an ergodic SSP are equal to their modified permutation analogues, respectively.     

Informational and Causal Architecture of Continuous-time Renewal Processes

We introduce the minimal maximally predictive models (\(\epsilon \text{-machines }\)) of processes generated by certain hidden semi-Markov models. Their causal states are either discrete, mixed, or continuous random variables and causal-state transitions are described by partial differential equations. As an application, we present a complete analysis of the \(\epsilon \text{-machines }\) of continuous-time renewal processes. This leads to closed-form expressions for their entropy rate, statistical complexity, excess entropy, and differential information anatomy rates.     

The computational complexity of generating random fractals

We examine a number of models that generate random fractals. The models are studied using the tools of computational complexity theory from the perspective of parallel computation. Diffusion-limited aggregation and several widely used algorithms for equilibrating the Ising model are shown to be highly sequential; it is unlikely they can be simulated efficiently in parallel. This is in contrast to Mandelbrot percolation, which can be simulated in constant parallel time. Our research helps shed light on the intrinsic complexity of these models relative to each other and to different growth processes that have been recently studied using complexity theory. In addition, the results may serve as a guide to simulation physics.     

The Entropy of a Binary Hidden Markov Process

The entropy of a binary symmetric Hidden Markov Process is calculated as an expansion in the noise parameter ε. We map the problem onto a one-dimensional Ising model in a large field of random signs and calculate the expansion coefficients up to second order in ε. Using a conjecture we extend the calculation to 11th order and discuss the convergence of the resulting series     

Permutation complexity via duality between values and orderings

We study the permutation complexity of finite-state stationary stochastic processes based on a duality between values and orderings between values. First, we establish a duality between the set of all words of a fixed length and the set of all permutations of the same length. Second, on this basis, we give an elementary alternative proof of the equality between the permutation entropy rate and the entropy rate for a finite-state stationary stochastic processes first proved in [J.M. Amigó, M.B. Kennel, L. Kocarev, The permutation entropy rate equals the metric entropy rate for ergodic information sources and ergodic dynamical systems, Physica D 210 (2005) 77-95]. Third, we show that further information on the relationship between the structure of values and the structure of orderings for finite-state stationary stochastic processes beyond the entropy rate can be obtained from the established duality. In particular, we prove that the permutation excess entropy is equal to the excess entropy, which is a measure of global correlation present in a stationary stochastic process, for finite-state stationary ergodic Markov processes.     

Granger causality and the inverse Ising problem

The inference of the couplings of an Ising model with given means and correlations is called the inverse Ising problem. This approach has received a lot of attention as a tool to analyze neural data. We show that autoregressive methods may be used to learn the couplings of an Ising model, also in the case of asymmetric connections and for multispin interactions. We find that, for each link, the linear Granger causality is two times the corresponding transfer entropy (i.e., the information flow on that link) in the weak coupling limit. For sparse connections and a low number of samples, the ?₁ regularized least squares method is used to detect the interacting pairs of spins. Nonlinear Granger causality is related to multispin interactions.     

Symmetric vertex models on planar random graphs

We solve a 4-(bond)-vertex model on an ensemble of 3-regular (Φ³) planar random graphs, which has the effect of coupling the vertex model to 2D quantum gravity. The method of solution, by mapping onto an Ising model in field, is inspired by the solution by Wu et.al. of the regular lattice equivalent – a symmetric 8-vertex model on the honeycomb lattice, and also applies to higher valency bond vertex models on random graphs when the vertex weights depend only on bond numbers and not cyclic ordering (the so-called symmetric vertex models).The relations between the vertex weights and Ising model parameters in the 4-vertex model on Φ³ graphs turn out to be identical to those of the honeycomb lattice model, as is the form of the equation of the Ising critical locus for the vertex weights. A symmetry of the partition function under transformations of the vertex weights, which is fundamental to the solution in both cases, can be understood in the random graph case as a change of integration variable in the matrix integral used to define the model.Finally, we note that vertex models, such as that discussed in this paper, may have a role to play in the discretisation of Lorentzian metric quantum gravity in two dimensions.     

Zero Entropy Systems

This paper introduces the notion of entropy dimension to measure the complexity of zero entropy dynamical systems, including the probabilistic and the topological versions. These notions are isomorphism invariants for measure-preserving transformation and continuity. We discuss basic propositions for entropy dimension and construct some examples to show that the topological entropy dimension attains any value between 0 and 1. This paper also gives a symbolic subspace to achieve zero topological entropy, but with full entropy dimension.     

Diagonal entropy in many-body systems: Volume effect and quantum phase transitions

We investigate the diagonal entropy(DE) of the ground state for quantum many-body systems, including the XY model and the Ising model with next nearest neighbor interactions. We focus on the DE of a subsystem of L continuous spins. We show that the DE in many-body systems, regardless of integrability, can be represented as a volume term plus a logarithmic correction and a constant offset. Quantum phase transition points can be explicitly identified by the three coefficients thereof. Besides, by combining entanglement entropy and the relative entropy of quantum coherence, as two celebrated representatives of quantumness, we simply obtain the DE, which naturally has the potential to reveal the information of quantumness. More importantly, the DE is concerning only the diagonal form of the ground state reduced density matrix, making it feasible to measure in real experiments, and therefore it has immediate applications in demonstrating quantum supremacy on state-of-the-art quantum simulators.     

Vertex models on Feynman diagrams

We discuss the statistical mechanics of vertex models on both generic (“thin”) and planar (“fat”) random graphs. Such models can be formulated as the N → 1 and N → ∞ limits of N × N complex matrix models, respectively. From the graph theoretic perspective one is using matrix model and field theory inspired methods to count various classes of directed graphs. For the thin random graphs we use saddle point methods to solve the models in the thermodynamic, large number of vertices limit and note that, as in the case of the eight-vertex model on the square lattice, various other models such as the Ising model appear as particular limits. The generic solution of the fat graph model is rather more elusive, but we show that for several choices of the couplings the models can be reduced to eigenvalue integrals and their critical behaviour deduced.     

Symbolic transfer entropy rate is equal to transfer entropy rate for bivariate finite-alphabet stationary ergodic Markov processes

Transfer entropy is a measure of the magnitude and the direction of information flow between jointly distributed stochastic processes. In recent years, its permutation analogues are considered in the literature to estimate the transfer entropy by counting the number of occurrences of orderings of values, not the values themselves. It has been suggested that the method of permutation is easy to implement, computationally low cost and robust to noise when applying to real world time series data. In this paper, we initiate a theoretical treatment of the corresponding rates. In particular, we consider the transfer entropy rate and its permutation analogue, the symbolic transfer entropy rate, and show that they are equal for any bivariate finite-alphabet stationary ergodic Markov process. This result is an illustration of the duality method introduced in [T. Haruna, K. Nakajima, Physica D 240, 1370 (2011)]. We also discuss the relationship among the transfer entropy rate, the time-delayed mutual information rate and their permutation analogues.     

Distribution of Mutual Information in Multipartite States

Using the relative entropy of total correlation, we derive an expression relating the mutual information of n-partite pure states to the sum of the mutual informations and entropies of its marginals and analyze some of its implications. Besides, by utilizing the extended strong subadditivity of von Neumann entropy, we obtain generalized monogamy relations for the total correlation in three-partite mixed states. These inequalities lead to a tight lower bound for this correlation in terms of the sum of the bipartite mutual informations. We use this bound to propose a measure for residual three-partite total correlation and discuss the non-applicability of this kind of quantifier to measure genuine multiparty correlations.