Many complex systems are known to us through a single recorded signal, from which regularity, memory, and randomness must be disentangled. Entropy density, effective measure complexity, and informational distance measure exactly that – how unpredictable a signal is, how much memory it carries, how far two signals lie apart – yet their theory sits scattered across decades of literature, and their estimation is frequently done wrong. This article assembles that theory in one place, links Shannon’s entropy to Kolmogorov’s algorithmic complexity, and shows how Lempel-Ziv factorisation turns both into practical, parameter-free estimators, backed by open-source software that processes sequences of a billion symbols. Applied unchanged to fMRI recordings, a ring of coupled nonlinear oscillators, and electrocardiograms, the same measures recover task-related brain activity, detect collective behaviour near the onset of chaos, and separate healthy from arrhythmic heart rhythms with clinically relevant accuracy, showing that a single information-theoretic toolkit captures memory and unpredictability across strikingly different systems.
Introduction
Data from complex dynamical systems often appear as one or a few time series, from which the system’s dynamics must be extracted [65 ] . In data analysis, the usual aims are to assess regularity versus randomness, to identify patterns, to discover governing laws, or to predict future system behaviour [66 ] . One useful approach is to treat the dynamical system as an information source and apply information-theoretic tools alongside statistical descriptions [67 ] . In general, a single or just a few data sets are insufficient to fully understand the underlying dynamical system that drives the information source, yet these are often the only available data. In such cases, assuming ergodicity becomes necessary to extract the relevant information from the data [68 ] .
For most systems, a fundamental quest is to find the relation between randomness and pattern in the system signal [69 ] . Randomness can be considered noise or, in a more useful perspective, the intrinsic uncertainty of the system, while a pattern is related to the deterministic laws that govern the system’s behaviour. It has been argued that for a complex dynamical system, the behaviour lies between complete predictability and total randomness [69 ] . Entropy density captures the irreducible unpredictability in a signal. Entropy density, also known as Kolmogorov-Sinai entropy, entropy rate, among other names, has been defined in several fields, including information theory, ergodic theory, and dynamical systems [67 , 70 ] . A lesser-used measure of complexity is the effective measure of complexity, introduced by Grassberger [68 ] , which aims to capture a system’s intrinsic memory and, in time-series analysis, its reliance on the past to define its future. Both magnitudes can be theoretically justified by Kolmogorov’s algorithmic complexity, which laid a solid foundation for the analysis of data beyond the ensemble-statistical point of view [71 ] . Kolmogorov’s theory of complexity builds on the existence of a universal computational machine, as demonstrated by Turing, and on the computational theory of recurrent functions [72 ] . From Kolmogorov theory, several concepts emerge that are closely related to entropy density and effective measure complexity; significantly, it also allows us to define the informational distance as a measure of the distance between two data sets [73 ] .
The informational theory related concepts have been used extensively in analyzing experimental and theoretical models and there is an extensive literature regarding their use [70 , 74 , 75 , 67 , 76 , 77 , 78 , 66 ] . In particular there is abundant literature dealing with the estimation of entropy density, and in a much lesser extent, effective measure complexity and informational distance [79 , 80 , 81 , 82 , 83 , 84 , 85 , 86 ] . In spite of that, there persist some confusion in the validity of the estimation procedures, specially in the latter magnitudes, and its use, and the mathematics of the whole subject appears scattered in the scientific literature, some misconceptions also persist [84 , 87 ] .
This article revisits key concepts and their mathematical foundations, including estimation and practical use. It gathers work previously scattered across various sources, including new, unpublished results from the authors. The aim is to offer a comprehensive treatment, from theory to practice, in a single source. Publicly available software and a library for estimating these magnitudes are also introduced.
What this article is not, is a review, there are some important areas left out, specially the early work of Grassberger [68 , 87 ] and the further studies by Crutchfield and Feldman [69 ] on entropy estimation for finite state automata, although some analytical results from their work will be used to compare estimated values of entropy density, and effective measure complexity with the exact values.
The article comprises three main parts: (1) mathematical foundations of information theory (§ 2 , § 3 , § 4 , § 5 ); (2) analysis of Lempel-Ziv factorisation, complexity, and entropic magnitude estimation (§ 6 , § 7 , § 8 ); and (3) case studies (§ 9 ). Conclusions follow. The appendix contains additional material, including proofs and explanations of procedures. Table 1 collects the notation used throughout.
Strings, ergodicity and stationarity
The intuitive notion of a string corresponds to a sequence of successive symbols, which take values from a finite set, such as a binary alphabet. The index that traverses the positions of the symbols in a sequence is called time. Although in practice one must deal with finite strings, the concept extends to infinite strings, and this extension is used in proving certain theorems. However, it is worth clarifying that there are several types of infinite strings; the most general ones never begin or end (e.g., … 1011010000111010100110011111110 … \ldots 1011010000111010100110011111110\ldots … 1011010000111010100110011111110 … ), and are called bi-infinite. If a point is taken in a bi-infinite string, to the right there will be an infinite string that has a starting point but never ends (e.g., a b b b a c c b a a b … abbbaccbaab\ldots abbba cc baab … ); and to the left we will have one that ends but does not have a starting point (… 32214441233 \ldots32214441233 … 32214441233 ). Any point in a bi-infinite string can be taken as the middle point.
Formally, a string is a successive concatenation of symbols u = … u − 2 u − 1 u 0 u 1 u 2 … u i … u=\ldots u_{-2}u_{-1} u_0 u_1u_2\ldots u_i\ldots u = … u − 2 u − 1 u 0 u 1 u 2 … u i … emitted by a symbol source. u i u_i u i is known as a character and takes values from an alphabet A \mathcal{A} A , u i ∈ A ; ∀ i ∈ Z u_i\in\mathcal{A}; \forall i\in\mathbb{Z} u i ∈ A ; ∀ i ∈ Z . The index i i i will be called time even though it does not represent that physical variable. The number of symbols available to the source will be taken as finite, ∣ A ∣ < ∞ |\mathcal{A}|<\infty ∣ A ∣ < ∞ ; the cardinality of the alphabet will be denoted by α ( = ∣ A ∣ ) \alpha(=|\mathcal{A}|) α ( = ∣ A ∣ ) . Throughout, string positions are indexed from zero; u ( ℓ ) = u 0 u 1 … u ℓ − 1 u^{(\ell)}=u_0u_1\ldots u_{\ell-1} u ( ℓ ) = u 0 u 1 … u ℓ − 1 denotes the prefix of length ℓ \ell ℓ . Unless otherwise stated, log ≡ log α \log\equiv\log_\alpha log ≡ log α ; if the sequence is binary, then α = 2 \alpha=2 α = 2 and entropies are expressed in bits.
When a string is finite, we call it a word. A word w w w has length ∣ w ∣ |w| ∣ w ∣ . It is important to include the null sequence Λ \Lambda Λ , which has length ( ∣ Λ ∣ = ) 0 (|\Lambda|=)0 ( ∣Λ∣ = ) 0 . If we have two strings w w w and u u u , the sequence w u wu w u is the concatenation of both sequences in the indicated order, and its length would be ∣ w ∣ + ∣ u ∣ |w|+|u| ∣ w ∣ + ∣ u ∣ .
It is convenient to consider a symbol source or emitter as generating discrete strings uninterruptedly; its output is bi-infinite strings. To circumvent the problems associated with time in generating bi-infinite strings when considering the occurrence of multiple strings, we can imagine that instead of a single emitter, we have a set, called an ensemble, of countably infinite identical emitters, each generating a bi-infinite string. Since, from a practical point of view, it is useful to consider finite strings, they are taken as the result of observing an emitter’s output over a finite time interval (… 100100000 11000111111 10010000111 … \ldots100100000\boxed{11000111111}10010000111\ldots … 100100000 11000111111 10010000111 … ). For a source, the set of rules it follows as they generate the bi-infinite string is called a grammar and denoted by G G G (e.g., a binary source that only emits an even number of 0s).
The set of all strings of finite length (words) will be denoted by A ∗ \mathcal{A}^* A ∗ and those of infinite length by A ∞ \mathcal{A}^\infty A ∞ .
Consider an infinite string u ∈ A ∞ u\in\mathcal{A}^{\infty} u ∈ A ∞ . If we define the set of all finite substrings of u u u , it is possible to define a σ \sigma σ -algebra on that set and assign a probability measure to the set.
For example, take the set of all strings of finite length. Consider the initial collection formed by subsets of strings, where each subset contains strings of the same length. From this initial collection, a σ \sigma σ -algebra can be generated, and probabilities can be assigned to the strings based on their length. A similar probability assignment can be done to other partitions of the strings into classes.
A subsequence or substring w a b ⊆ u w_a^b\subseteq u w a b ⊆ u is a sequence of symbols extracted from u u u starting at time a a a , up to time b b b , and, therefore, of length b − a + 1 b-a+1 b − a + 1 . The word w w w , where the position in the u u u string is irrelevant, is called the base word. A subsequence can be infinite or can be a word.
It is useful to introduce the drop operator π \pi π , such that when operating on the left on a word, it removes the first character of the string, π w a b ≡ w a + 1 b \pi w_a^b\equiv w_{a+1}^b π w a b ≡ w a + 1 b (e.g., π 101100 = 01100 \pi 101100=01100 π 101100 = 01100 ); and operating on the right removes the last character of the string, w a b π ≡ w a b − 1 w_a^b \pi\equiv w_a^{b-1} w a b π ≡ w a b − 1 (e.g., 101100 π = 10110 101100\pi=10110 101100 π = 10110 ).
A sequence can be shifted to the right such that if we call Θ [ u ] \Theta[u] Θ [ u ] the shifted string, we will have [ Θ ( u ) ] t = u t − 1 [\Theta(u)]_t = u_{t-1} [ Θ ( u ) ] t = u t − 1 (Θ [ … u 5 1001 u 10 … ] = … u 4 u 5 1001 … \Theta[\dots u_5 1 0 0 1 u_{10} \ldots] = \dots u_4 u_5 1 0 0 1 \ldots Θ [ … u 5 1001 u 10 … ] = … u 4 u 5 1001 … ). We define the same for a left shift (Θ − 1 [ u ] \Theta^{-1}[u] Θ − 1 [ u ] ) where we will have [ Θ − 1 ( u ) ] t = u t + 1 [\Theta^{-1}(u)]_t = u_{t+1} [ Θ − 1 ( u ) ] t = u t + 1 (Θ − 1 [ … u 5 1001 u 10 … ] = … 1001 u 10 u 11 … \Theta^{-1}[\dots u_5 1 0 0 1 u_{10} \ldots] = \dots 1 0 0 1 u_{10} u_{11} \ldots Θ − 1 [ … u 5 1001 u 10 … ] = … 1001 u 10 u 11 … ). The operator Θ \Theta Θ is called the right shift operator, and Θ − 1 \Theta^{-1} Θ − 1 is called the left shift operator.
The two most important properties required of a source are ergodicity and stationarity.
Ergodicity means that the strings emitted by the source are statistically indistinguishable: for almost every string u ∈ A ∞ u\in\mathcal{A}^\infty u ∈ A ∞ emitted by an ergodic source ψ \psi ψ , the relative frequency with which any finite word w w w occurs along u u u converges to the same value P ( w ) P(w) P ( w ) , whatever the string (e.g., P u ( w ) = P v ( w ) P_u(w)=P_v(w) P u ( w ) = P v ( w ) for two emitted strings u u u and v v v ). A single string then characterises the source, and ensemble averages can be replaced by averages along one realisation.
Stationarity refers to the temporal invariance of the emitter’s statistical properties. In other words, the probability of a specific finite string, of any length, occurring in a bi-infinite string does not depend on the instant in time at which the finite string occurs.
Stationarity implies that the probability of occurrence of a substring in an infinite string emitted by the source depends only on the base word of the substring and not on the starting time. A stationary source implies that for all u ∈ A ∞ u\in\mathcal{A}^\infty u ∈ A ∞ , P ( u ) = P ( Θ ( u ) ) P(u)=P(\Theta(u)) P ( u ) = P ( Θ ( u )) .
If a process is stationary, all instances w i j w_i^j w i j of the base word w w w have the same probability (P ( w a b ) = P ( w ) P(w_a^b)=P(w) P ( w a b ) = P ( w ) ) for any string u ∈ A ∞ u\in\mathcal{A}^\infty u ∈ A ∞ .
Table 1. Notation used throughout. A hat denotes a magnitude estimated from a finite sequence.
Block entropy, entropy gain and entropy density
Shannon block entropy
Consider a bi-infinite string u u u from which the set { w ( ℓ ) } \{w^{(\ell)}\} { w ( ℓ ) } of all finite different substrings, w ( ℓ ) w^{(\ell)} w ( ℓ ) , of length ℓ \ell ℓ are taken. Let # ℓ \#_\ell # ℓ be the cardinality of { w ( ℓ ) } \{w^{(\ell)}\} { w ( ℓ ) } . To each string w ( ℓ ) w^{(\ell)} w ( ℓ ) a probability P ( w ( ℓ ) ) P(w^{(\ell)}) P ( w ( ℓ ) ) is assigned. The Shannon block entropy is then defined as [88 , 89 , 67 ]
H ℓ ( u ) = − ∑ w ( ℓ ) ∈ u P ( w ( ℓ ) ) log P ( w ( ℓ ) ) . \begin{equation}
H_\ell(u)=-\sum\limits_{w^{(\ell)}\in u}P(w^{(\ell)})\log P(w^{(\ell)}). \tag*{(1)}
\end{equation} H ℓ ( u ) = − w ( ℓ ) ∈ u ∑ P ( w ( ℓ ) ) log P ( w ( ℓ ) ) . (1)
The summand 0 log 0 ≡ 0 0\log 0\equiv 0 0 log 0 ≡ 0 by definition. H ℓ ( u ) = 0 H_\ell(u)=0 H ℓ ( u ) = 0 if u u u is a constant string formed by a single character and H ℓ ( u ) H_\ell(u) H ℓ ( u ) attains its maximum value log # ℓ \log \#_\ell log # ℓ when all different words w ( ℓ ) w^{(\ell)} w ( ℓ ) have the same probability P ( w ( ℓ ) ) = 1 / # ℓ P(w^{(\ell)})=1/\#_\ell P ( w ( ℓ ) ) = 1/ # ℓ .
H ℓ ( u ) H_\ell(u) H ℓ ( u ) is a non- decreasing function of ℓ \ell ℓ : H ℓ + 1 ( u ) ≥ H ℓ ( u ) H_{\ell+1}(u)\ge H_{\ell}(u) H ℓ + 1 ( u ) ≥ H ℓ ( u ) (see Appendix § 13 ).
Entropy gain
The entropy gain, a non-negative magnitude, is defined as [69 ]
Δ H ℓ ( u ) ≡ H ℓ ( u ) − H ℓ − 1 ( u ) . \begin{equation}
\Delta H_\ell(u)\equiv H_\ell(u)-H_{\ell-1}(u). \tag*{(2)}
\end{equation} Δ H ℓ ( u ) ≡ H ℓ ( u ) − H ℓ − 1 ( u ) . (2)
Since the null word Λ \Lambda Λ occurs with probability one, H 0 ( u ) = 0 H_0(u)=0 H 0 ( u ) = 0 and Δ H 1 ( u ) = H 1 ( u ) \Delta H_1(u)=H_1(u) Δ H 1 ( u ) = H 1 ( u ) . Equation (2) does not define Δ H 0 \Delta H_0 Δ H 0 ; following Crutchfield and Feldman [69 ] , we adopt the convention Δ H 0 ( u ) = log α = 1 \Delta H_0(u)=\log\alpha=1 Δ H 0 ( u ) = log α = 1 , the uncertainty assigned to a symbol before any observation is made. From equation (82)
Δ H ℓ ( u ) = − ∑ w ( ℓ ) ∈ u P ( w 0 … w ℓ − 1 ) log P ( w ℓ − 1 ∣ w 0 , . . . , w ℓ − 2 ) ≡ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) . \begin{equation}
\Delta H_\ell(u)=-\sum\limits_{w^{(\ell)}\in u} P(w_0\ldots w_{\ell-1}) \log P(w_{\ell-1} | w_0,...,w_{\ell-2})\equiv H(u_{\ell-1}|u^{(\ell-1)}). \tag*{(3)}
\end{equation} Δ H ℓ ( u ) = − w ( ℓ ) ∈ u ∑ P ( w 0 … w ℓ − 1 ) log P ( w ℓ − 1 ∣ w 0 , ... , w ℓ − 2 ) ≡ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) . (3)
Equations (2) and ((3) ) allow two equivalent interpretations of the entropy gain. On one hand, it is an estimate of how random a symbol source looks when only substrings up to length ℓ \ell ℓ are taken into account. On the other hand, it is the mean uncertainty of the symbol u ℓ − 1 u_{\ell-1} u ℓ − 1 if the prefix u ℓ − 1 u^{\ell-1} u ℓ − 1 is known. In the last sense, it is the amount of information that has to be stored in order to make an optimal prediction of u ℓ − 1 u_{\ell-1} u ℓ − 1 [69 ] .
For a stationary process
Δ H ℓ ( u ) = H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) ≤ H ( u ℓ − 1 ∣ π u ( ℓ − 1 ) ) = H ( u ℓ − 2 ∣ u ( ℓ − 2 ) ) = Δ H ℓ − 1 ( u ) . \Delta H_\ell(u)=H(u_{\ell-1}|u^{(\ell-1)})\leq H(u_{\ell-1}|\pi u^{(\ell-1)})=H(u_{\ell-2}|u^{(\ell-2)})=\Delta H_{\ell-1}(u). Δ H ℓ ( u ) = H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) ≤ H ( u ℓ − 1 ∣ π u ( ℓ − 1 ) ) = H ( u ℓ − 2 ∣ u ( ℓ − 2 ) ) = Δ H ℓ − 1 ( u ) .
The inequality follows from the fact that conditioning reduces the entropy, and the equality results from the stationarity condition. Δ H ℓ ( u ) \Delta H_\ell(u) Δ H ℓ ( u ) is a non-increasing function of ℓ \ell ℓ .
As Δ H ℓ ( u ) ≥ 0 \Delta H_\ell(u)\geq 0 Δ H ℓ ( u ) ≥ 0 , the last property implies
0 ≤ Δ H ∞ ( u ) < ∞ , \begin{equation}
0 \leq \Delta H_\infty(u)<\infty, \tag*{(4)}
\end{equation} 0 ≤ Δ H ∞ ( u ) < ∞ , (4)
where
Δ H ∞ ( u ) = lim ℓ → ∞ Δ H ℓ ( u ) = lim ℓ → ∞ H [ u ℓ ∣ u ( ℓ ) ] . \begin{equation}
\Delta H_\infty(u)=\lim\limits_{\ell\rightarrow \infty}\Delta H_\ell(u)=\lim\limits_{\ell\rightarrow \infty} H\left[u_\ell|u^{(\ell)}\right]. \tag*{(5)}
\end{equation} Δ H ∞ ( u ) = ℓ → ∞ lim Δ H ℓ ( u ) = ℓ → ∞ lim H [ u ℓ ∣ u ( ℓ ) ] . (5)
The limit Δ H ∞ ( u ) \Delta H_\infty(u) Δ H ∞ ( u ) exists for an ergodic stationary source. In what follows, when needed, the dependence on u u u will be dropped from Δ H ℓ \Delta H_\ell Δ H ℓ , since, for an ergodic source, any infinite string u u u is statistically equivalent to any other.
For a periodic sequence of minimal period p p p , the probabilities are the frequencies of occurrence along the sequence, and the words of length ℓ ≥ p \ell\geq p ℓ ≥ p are the p p p cyclic phases of the period, each occurring exactly once per period; their distribution is therefore uniform, and H ℓ = log p H_\ell=\log p H ℓ = log p for ℓ ≥ p \ell\geq p ℓ ≥ p , from where
Δ H ℓ = Δ H ∞ = 0. ( ℓ ≥ p ) , \begin{equation}
\Delta H_\ell=\Delta H_\infty=0. \;\;\;(\ell\geq p), \tag*{(6)}
\end{equation} Δ H ℓ = Δ H ∞ = 0. ( ℓ ≥ p ) , (6)
for a random sequence, by which we mean throughout a realisation of an i.i.d. source with equiprobable symbols, P ( a ) = 1 / α P(a)=1/\alpha P ( a ) = 1/ α for all a ∈ A a\in\mathcal{A} a ∈ A , H ℓ = ℓ H_\ell=\ell H ℓ = ℓ and
Δ H ℓ = Δ H ∞ = 1. \begin{equation}
\Delta H_\ell=\Delta H_\infty=1. \tag*{(7)}
\end{equation} Δ H ℓ = Δ H ∞ = 1. (7)
Entropy density
To measure the mean uncertainty per symbol of the ergodic source, the entropy density is defined as [88 , 89 ]
h ≡ lim ℓ → ∞ H ℓ ℓ , \begin{equation}
h\equiv \lim\limits_{\ell\rightarrow \infty}\frac{H_\ell}{\ell}, \tag*{(8)}
\end{equation} h ≡ ℓ → ∞ lim ℓ H ℓ , (8)
Entropy density has been referred to by different names in different contexts, such as Kolmogorov-Sinai (KS) entropy or entropy rate [70 , 67 ] .
Using the chain rule
H ℓ ( u ) ℓ = 1 ℓ ∑ i = 0 ℓ − 1 H ( u i ∣ u ( i ) ) , \begin{equation}
\frac{H_\ell(u)}{\ell}=\frac{1}{\ell}\sum\limits_{i=0}^{\ell-1}H(u_i|u^{(i)}), \tag*{(9)}
\end{equation} ℓ H ℓ ( u ) = ℓ 1 i = 0 ∑ ℓ − 1 H ( u i ∣ u ( i ) ) , (9)
and using the Cesáro theorem, which states that if there is a sequence in n n n such that a n → a a_n\rightarrow a a n → a , and b n = 1 / n ∑ i = 0 n − 1 a i b_n=1/n\sum_{i=0}^{n-1}a_i b n = 1/ n ∑ i = 0 n − 1 a i , then b n → a b_n\rightarrow a b n → a , we have [69 ] ,
h = lim ℓ → ∞ H ℓ ℓ = lim ℓ → ∞ H ( u ℓ ∣ u ( ℓ ) ) = Δ H ∞ . \begin{equation}
h=\lim\limits_{\ell\rightarrow \infty}\frac{H_\ell}{\ell}=\lim\limits_{\ell \rightarrow \infty}H(u_\ell|u^{(\ell)})=\Delta H_\infty. \tag*{(10)}
\end{equation} h = ℓ → ∞ lim ℓ H ℓ = ℓ → ∞ lim H ( u ℓ ∣ u ( ℓ ) ) = Δ H ∞ . (10)
This last expression allows us to understand the entropy density as the uncertainty in a new symbol when an infinite number of symbols in the string have been measured. In expression ((8) ), the numerator is a non-decreasing function of ℓ \ell ℓ , while the denominator is strictly increasing; knowing that for an ergodic and stationary source, the limit exists, convergence is guaranteed to be uniform, and
H ℓ ∼ h ℓ ℓ → ∞ . \begin{equation}
H_\ell\sim h \ell\;\;\;\ell\rightarrow \infty. \tag*{(11)}
\end{equation} H ℓ ∼ h ℓ ℓ → ∞. (11)
For a large enough ℓ \ell ℓ , H ℓ ( u ) H_\ell(u) H ℓ ( u ) is a linear function of ℓ \ell ℓ with slope equal to the entropy density [69 ] .
From equation (8) , we can define the terms in the sequence to infinity as
h ℓ = H ℓ ℓ , \begin{equation}
h_\ell=\frac{H_\ell}{\ell}, \tag*{(12)}
\end{equation} h ℓ = ℓ H ℓ , (12)
sometimes known as the finite entropy rate of order ℓ \ell ℓ . Although equation (10) guarantees that in the limit ℓ → ∞ \ell\rightarrow \infty ℓ → ∞ , Δ H ℓ \Delta H_\ell Δ H ℓ and h ℓ h_\ell h ℓ are equal, for finite ℓ \ell ℓ this is not the case. In fact, the entropy gain converges faster than h ℓ h_\ell h ℓ (See Appendix § 14 ).
For a periodic sequence of minimal period p p p , H ℓ = log p H_\ell=\log p H ℓ = log p for ℓ ≥ p \ell\geq p ℓ ≥ p , from where
h ℓ = log p ℓ ( ℓ ≥ p ) , \begin{equation}
h_\ell=\frac{\log p}{\ell} \;\;\;(\ell\geq p), \tag*{(13)}
\end{equation} h ℓ = ℓ log p ( ℓ ≥ p ) , (13)
and h = 0 h=0 h = 0 . For a random sequence
h ℓ = h = 1 , h_\ell=h=1, h ℓ = h = 1 ,
the same value as Δ H ℓ \Delta H_\ell Δ H ℓ .
Number of different words
As before, let # ℓ = α ℓ ζ ℓ ( u ) \#_\ell=\alpha^{\ell \zeta_\ell(u)} # ℓ = α ℓ ζ ℓ ( u ) be the number of different words of length ℓ \ell ℓ in a string u u u .
If for a given ℓ \ell ℓ we have # ℓ \#_\ell # ℓ , then at most we will have α # ℓ \alpha \#_\ell α # ℓ different words of length ℓ + 1 \ell+1 ℓ + 1 . It follows
α ℓ ζ ℓ ( u ) α ≥ α ( ℓ + 1 ) ζ ℓ + 1 ( u ) , \alpha^{\ell \zeta_\ell(u)}\alpha\ge \alpha^{(\ell+1) \zeta_{\ell+1}(u)}, α ℓ ζ ℓ ( u ) α ≥ α ( ℓ + 1 ) ζ ℓ + 1 ( u ) ,
from where
ζ ℓ + 1 ≤ ℓ ℓ + 1 ζ ℓ ( u ) + 1 ℓ + 1 . \begin{equation}
\zeta_{\ell+1}\leq\frac{\ell}{\ell+1} \zeta_\ell(u)+\frac{1}{\ell+1}. \tag*{(14)}
\end{equation} ζ ℓ + 1 ≤ ℓ + 1 ℓ ζ ℓ ( u ) + ℓ + 1 1 . (14)
On the other hand, # ℓ + 1 ≥ # ℓ \#_{\ell+1}\ge \#_\ell # ℓ + 1 ≥ # ℓ and
ζ ℓ + 1 ≥ ℓ ℓ + 1 ζ ℓ ( u ) . \begin{equation}
\zeta_{\ell+1}\ge \frac{\ell}{\ell+1} \zeta_\ell(u). \tag*{(15)}
\end{equation} ζ ℓ + 1 ≥ ℓ + 1 ℓ ζ ℓ ( u ) . (15)
There are at most α ℓ \alpha^\ell α ℓ different words of length ℓ \ell ℓ , therefore
ζ ℓ ( u ) ≤ 1. \begin{equation}
\zeta_\ell(u)\le 1. \tag*{(16)}
\end{equation} ζ ℓ ( u ) ≤ 1. (16)
By definition # ℓ ( u ) ≥ 1 \#_\ell(u)\ge 1 # ℓ ( u ) ≥ 1 , which implies that
ζ ℓ ( u ) ≥ 0. \begin{equation}
\zeta_\ell(u)\ge 0. \tag*{(17)}
\end{equation} ζ ℓ ( u ) ≥ 0. (17)
Form inequalities ((16) ) and ((17) ) it follows that ζ ℓ ( u ) \zeta_\ell(u) ζ ℓ ( u ) is bounded from below and above
0 ≤ ζ ℓ ( u ) ≤ 1. \begin{equation}
0\le \zeta_\ell(u) \leq 1. \tag*{(18)}
\end{equation} 0 ≤ ζ ℓ ( u ) ≤ 1. (18)
Consequently the lim inf ℓ → ∞ ζ ℓ ( u ) \liminf\limits_{\ell\rightarrow \infty} \zeta_\ell(u) ℓ → ∞ lim inf ζ ℓ ( u ) and lim sup ℓ → ∞ ζ ℓ ( u ) \limsup\limits_{\ell\rightarrow \infty} \zeta_\ell(u) ℓ → ∞ lim sup ζ ℓ ( u ) exist, are finite and are equal (see Appendix § 15 ).
The relation
ζ ∞ ( u ) = lim ℓ → ∞ ζ ℓ ( u ) ≤ 1 , \begin{equation}
\zeta_\infty(u)=\lim\limits_{\ell\rightarrow \infty} \zeta_\ell(u)\leq 1, \tag*{(19)}
\end{equation} ζ ∞ ( u ) = ℓ → ∞ lim ζ ℓ ( u ) ≤ 1 , (19)
makes ζ ∞ ( u ) \zeta_\infty(u) ζ ∞ ( u ) a quantity that characterises an infinite sequence u u u , and thus, for an ergodic source, the source itself. As done before, the dependence of ζ ℓ \zeta_\ell ζ ℓ on u u u will be dropped when it clutters the notation.
For a periodic sequence of minimal period p p p the different words of length ℓ ≥ p \ell\geq p ℓ ≥ p are the p p p cyclic phases of the period, so # ℓ = p \#_\ell= p # ℓ = p for ℓ ≥ p \ell\geq p ℓ ≥ p , from where it follows that
ζ ℓ = log p ℓ ( ℓ ≥ p ) , \begin{equation}
\zeta_\ell= \frac{\log p}{\ell}\;\;\;(\ell\geq p), \tag*{(20)}
\end{equation} ζ ℓ = ℓ log p ( ℓ ≥ p ) , (20)
and consequently ζ ∞ = 0 \zeta_\infty=0 ζ ∞ = 0 . For a random sequence, and more generally for any i.i.d. sequence in which every symbol has non-zero probability, # ℓ = α ℓ \#_\ell=\alpha^\ell # ℓ = α ℓ , and
ζ ℓ = 1. \begin{equation}
\zeta_\ell=1. \tag*{(21)}
\end{equation} ζ ℓ = 1. (21)
Number of distinct words and entropy
Consider an ergodic source characterized by an entropy rate h h h , let u u u be an infinite string produced by the source, Ziv [90 ] proved (see Appendix § 16 )
P [ ζ ∞ = h ] = 1. (Ziv’s theorem 5) \begin{equation}
P\left[\zeta_\infty=h\right]=1.\;\;\;\;\; \text{(Ziv’s theorem 5)} \tag*{(22)}
\end{equation} P [ ζ ∞ = h ] = 1. (Ziv’s theorem 5) (22)
In an ergodic source, its statistical properties can be estimated accurately from a single very long sequence generated by the source. The question is, how do we extract these properties from a single sequence? Equation (22) tells us one way. ζ ∞ \zeta_\infty ζ ∞ is, in principle, computable from a sufficiently long sequence. But beyond that practical value, equation (22) points to something more fundamental: asymptotically, the number of different strings of length ℓ ( ≫ 1 ) \ell(\gg 1) ℓ ( ≫ 1 ) is determined by the entropy of the ergodic source. In retrospect, it should not surprise us; a source is more unpredictable the more distinct strings it can generate. But the result also surprises us; entropy, and correspondingly h h h , is a function of occurrence probabilities, but ζ ∞ \zeta_\infty ζ ∞ is not a function of how many times each different string appears; it only depends on the number of distinct strings.
Ziv’s theorem ((22) ) guarantees the equivalence of ζ ℓ \zeta_\ell ζ ℓ to h ℓ h_\ell h ℓ and Δ H ℓ \Delta H_\ell Δ H ℓ at the limit ℓ → ∞ \ell\rightarrow \infty ℓ → ∞ ; it does not say anything for finite values of ℓ \ell ℓ . From equation (1) and the fact that the block entropy reaches its maximum value for a uniform distribution P ( u ) = 1 / # ℓ ( u ) P(u)=1/\#_\ell(u) P ( u ) = 1/ # ℓ ( u ) , it follows.
log # ℓ = ℓ ζ ℓ ( u ) ≥ H ℓ ( u ) , \log \#_\ell=\ell \zeta_\ell(u)\geq H_\ell(u), log # ℓ = ℓ ζ ℓ ( u ) ≥ H ℓ ( u ) ,
that is, ζ ℓ ≥ h ℓ \zeta_\ell\geq h_\ell ζ ℓ ≥ h ℓ . Together with h ℓ ≥ Δ H ℓ h_\ell\geq \Delta H_\ell h ℓ ≥ Δ H ℓ , Eq. (84) of Appendix § 14 , and Δ H ℓ ≥ 0 \Delta H_\ell\geq 0 Δ H ℓ ≥ 0 , it follows that
ζ ℓ ≥ h ℓ ≥ Δ H ℓ ≥ 0. \begin{equation}
\zeta_\ell \geq h_\ell \geq \Delta H_\ell \geq 0. \tag*{(23)}
\end{equation} ζ ℓ ≥ h ℓ ≥ Δ H ℓ ≥ 0. (23)
Algorithmic complexity and entropy
Kolmogorov complexity, also known as algorithmic complexity, quantifies the information content of a finite string [72 ] . Formally, for a given Universal Turing Machine (UTM) U \mathcal{U} U and a string w w w , this measure corresponds to the length of the shortest possible program w ∗ w^* w ∗ that can generate w w w as output:
K U ( w ) = min w ∗ ∈ A ∗ { ∣ w ∗ ∣ ∣ U ( w ∗ ) = w } , \begin{equation}
K_{\mathcal{U}}(w) = \min_{w^* \in \mathcal{A}^*} \bigl\{ |w^*| \mid \mathcal{U}(w^*) = w \bigr\}, \tag*{(24)}
\end{equation} K U ( w ) = w ∗ ∈ A ∗ min { ∣ w ∗ ∣ ∣ U ( w ∗ ) = w } , (24)
where K U ( w ) K_{\mathcal{U}}(w) K U ( w ) is the Kolmogorov complexity, ∣ w ∗ ∣ |w^*| ∣ w ∗ ∣ denotes the length of program w ∗ w^* w ∗ , U ( w ) \mathcal{U}(w) U ( w ) represents the output produced when U \mathcal{U} U executes program w ∗ w^* w ∗ . As changing the UTM amounts to adding a constant to the Kolmogorov complexity regardless of the string w w w , the use of another UTM just adds an O ( 1 ) O(1) O ( 1 ) upper-bound correction to the defined magnitudes; the subscript U \mathcal{U} U can be dropped, and in what follows we use K ( w ) K(w) K ( w ) . Kolmogorov complexity of a string represents its inherent (irreducible) information content.
There are certain constraints needed for the shortest possible program w ∗ w^* w ∗ . First of all, it must halt after a finite number of steps, and it will also be required that once it halts, its only output must be the string w w w . Another convenient condition usually imposed on w ∗ w^* w ∗ is that it must be self-delimiting, that is, w ∗ w^* w ∗ carries with it the information about its size, which implies an additional correction of log ∣ w ∣ \log |w| log ∣ w ∣ , we will drop the requirement in what follows for clarity.
The joint algorithmic complexity of strings w 1 w_1 w 1 and w 2 w_2 w 2 is defined as the size of the smallest program that computes both strings. The following inequality holds,
K ( w 1 , w 2 ) ≤ K ( w 1 ) + K ( w 2 ) + O ( 1 ) . \begin{equation}
K(w_1,w_2)\leq K(w_1)+K(w_2)+O(1). \tag*{(25)}
\end{equation} K ( w 1 , w 2 ) ≤ K ( w 1 ) + K ( w 2 ) + O ( 1 ) . (25)
The conditional Kolmogorov complexity K ( w 1 ∣ w 2 ) K(w_1|w_2) K ( w 1 ∣ w 2 ) is understood as the length of the minimal self-delimiting program that computes the string w 1 w_1 w 1 if the additional string w 2 w_2 w 2 is provided as input. The following relation holds,
K ( w 1 , w 2 ) = K ( w 2 ) + K ( w 1 ∣ w 2 ) + O ( 1 ) . \begin{equation}
K(w_1,w_2)=K(w_2)+K(w_1|w_2)+O(1). \tag*{(26)}
\end{equation} K ( w 1 , w 2 ) = K ( w 2 ) + K ( w 1 ∣ w 2 ) + O ( 1 ) . (26)
Finally, the algorithmic mutual information can be taken as
K ( w 1 : w 2 ) = K ( w 1 ) + K ( w 2 ) − K ( w 1 , w 2 ) , \begin{equation}
K(w_1:w_2)=K(w_1)+K(w_2)-K(w_1,w_2), \tag*{(27)}
\end{equation} K ( w 1 : w 2 ) = K ( w 1 ) + K ( w 2 ) − K ( w 1 , w 2 ) , (27)
which measures the additional amount of information needed to calculate w 1 w_1 w 1 and w 2 w_2 w 2 separately instead of jointly. Inequality (\ref{eq:jointk} ) makes K ( w 1 : w 2 ) ≥ 0 K(w_1:w_2)\geq 0 K ( w 1 : w 2 ) ≥ 0 .
To extend the definition of K ( ⋅ ) K(\cdot) K ( ⋅ ) to infinite string u u u , consider the finite string u ( ℓ ) u^{(\ell)} u ( ℓ ) of length ℓ \ell ℓ , the algorithmic complexity per symbol can then be defined as
k ( u ) = lim ℓ → ∞ k ℓ = lim ℓ → ∞ K ( u ( ℓ ) ) ℓ . \begin{equation}
k(u)=\lim\limits_{\ell\rightarrow \infty} k_\ell=\lim\limits_{\ell\rightarrow \infty} \frac{K(u^{(\ell)})}{\ell}. \tag*{(28)}
\end{equation} k ( u ) = ℓ → ∞ lim k ℓ = ℓ → ∞ lim ℓ K ( u ( ℓ ) ) . (28)
There are several troublesome subtleties in the above definition, particularly the question of whether such a limit exists. A more sound definition would be to define two k ( u ) k(u) k ( u ) , one taking the lim sup \limsup lim sup , k s u p ( u ) k_{sup}(u) k s u p ( u ) , and another taking the lim inf \liminf lim inf , k i n f ( u ) k_{inf}(u) k in f ( u ) , but as further on, we will be dealing exclusively with finite strings, we will leave it as defined by ((28) ) and the reader is referred to appropriate reference for the finer details [72 ] .
While Shannon entropy quantifies information through the probabilistic characteristics of data sources, treating individual objects as statistical realisations, Kolmogorov complexity evaluates information content directly through an object’s algorithmic properties, measuring its inherent descriptive complexity. This conceptual divergence notwithstanding, a systematic correspondence emerges between Shannon-theoretic and Kolmogorov-theoretic frameworks: expectations of algorithmic information measures typically match classical entropy quantities, establishing fundamental equivalences between the two approaches to information quantification. This fact, for an ergodic source, should come as no surprise, as the statistical properties of the source are translated to those of a single string.
The main result, proven in [72 ] , is that given an ergodic source and a set u {u} u of strings from the source with a probability measure defined over the set, then
lim ℓ → ∞ E [ K ( u ( ℓ ) ) ℓ ] = lim ℓ → ∞ E [ k ℓ ] = h , \begin{equation}
\lim\limits_{\ell\rightarrow \infty}\mathbb{E}\left [\frac{K(u^{(\ell)})}{\ell}\right]=\lim\limits_{\ell\rightarrow \infty}\mathbb{E}\left [k_\ell\right]=h, \tag*{(29)}
\end{equation} ℓ → ∞ lim E [ ℓ K ( u ( ℓ ) ) ] = ℓ → ∞ lim E [ k ℓ ] = h , (29)
where E [ ⋅ ] \mathbb{E}[\cdot] E [ ⋅ ] is the expected value. The main shortcoming of Kolmogorov complexity lies in the fact that it is non-computable due to the unsolvable nature of the halting problem, which renders it impossible to find a recursive function that can determine the shortest algorithm that produces a given string [72 ] . Yet the non-computability of K ( w ) K(w) K ( w ) does not necessarily translate to non-computability of K ( u ( ℓ ) ) / ℓ K(u^{(\ell)})/\ell K ( u ( ℓ ) ) / ℓ [91 ] .
Entropy convergence: effective measure complexity
Four magnitudes have been defined: ζ ℓ \zeta_\ell ζ ℓ , h ℓ h_\ell h ℓ , Δ H ℓ \Delta H_\ell Δ H ℓ and k ℓ k_\ell k ℓ , which, in the limit of infinite strings, converge to the KS entropy, yet the way they converge is different.
Let η ℓ \eta_\ell η ℓ be any of the mentioned magnitudes for finite ℓ \ell ℓ ; then δ h ℓ ( η ) = ∣ η ℓ − h ∣ \delta h^{(\eta)}_\ell=|\eta_\ell-h| δ h ℓ ( η ) = ∣ η ℓ − h ∣ is the deficit of the given magnitude with respect to its convergent value at time step ℓ \ell ℓ . δ h ℓ ( η ) \delta h^{(\eta)}_\ell δ h ℓ ( η ) is a magnitude of information, and its precise interpretation depends on the particular η \eta η . Regardless of its interpretation the sum of the δ h ℓ ( η ) \delta h^{(\eta)}_\ell δ h ℓ ( η ) with ℓ \ell ℓ can be taken as some sort of discrete integration [69 ]
E η = ∑ ℓ = 1 ∞ δ h ℓ ( η ) , \begin{equation}
E_{\eta}=\sum\limits_{\ell=1}^{\infty} \delta h^{(\eta)}_\ell, \tag*{(30)}
\end{equation} E η = ℓ = 1 ∑ ∞ δ h ℓ ( η ) , (30)
and it’s directly related to the convergence speed of the involved magnitude η \eta η . The larger the sum, the slower the convergence. It must be noticed that the series given by ((30) ) may not converge at all.
As is often the case, for an exponential decaying dependence of
δ h ℓ ( η ) = ( η 0 − h ) 2 − ν ℓ , \begin{equation}
\delta h^{(\eta)}_\ell=(\eta_0-h)\, 2^{-\nu \ell}, \tag*{(31)}
\end{equation} δ h ℓ ( η ) = ( η 0 − h ) 2 − ν ℓ , (31)
E η E_{\eta} E η will have the form
E η = η 0 − h 2 ν − 1 . \begin{equation}
E_{\eta}=\frac{\eta_0-h}{2^{\nu}-1}. \tag*{(32)}
\end{equation} E η = 2 ν − 1 η 0 − h . (32)
For a power law decay, δ h ℓ ( η ) ∝ ℓ − γ \delta h^{(\eta)}_\ell\propto \ell^{-\gamma} δ h ℓ ( η ) ∝ ℓ − γ , the sum ((30) ) converges only if γ > 1 \gamma>1 γ > 1 , while for decaying rates between these two behaviours, of the form
δ h ℓ ( η ) ∝ 2 − ν ℓ β , 0 < β < 1 , \begin{equation}
\delta h^{(\eta)}_\ell\propto 2^{-\nu \ell^\beta},\;\;\;\; 0<\beta<1, \tag*{(33)}
\end{equation} δ h ℓ ( η ) ∝ 2 − ν ℓ β , 0 < β < 1 , (33)
it will converge provided that ν > 0 \nu > 0 ν > 0 .
For all the ζ ℓ \zeta_\ell ζ ℓ , h ℓ h_\ell h ℓ , Δ H ℓ \Delta H_\ell Δ H ℓ magnitudes, from the results in the previous sections, it follows that for a random sequence E η = 0 E_\eta=0 E η = 0 . For a periodic sequence of minimal period p ≥ 2 p\geq 2 p ≥ 2 , equations (13) and ((20) ) give ζ ℓ = h ℓ = log p / ℓ \zeta_\ell=h_\ell=\log p/\ell ζ ℓ = h ℓ = log p / ℓ for ℓ ≥ p \ell\geq p ℓ ≥ p and h = 0 h=0 h = 0 , so that, for η ℓ = ζ ℓ \eta_\ell=\zeta_\ell η ℓ = ζ ℓ or h ℓ h_\ell h ℓ , E η E_\eta E η contains the harmonic series log p ∑ ℓ ≥ p ℓ − 1 \log p\sum_{\ell\geq p}\ell^{-1} log p ∑ ℓ ≥ p ℓ − 1 and does not converge, which is not a nice property to characterise a periodic sequence, as it does not distinguish among them. Yet, it is quite straightforward to see that in the case of Δ H ℓ \Delta H_\ell Δ H ℓ , for a periodic sequence of minimum period p p p ,
E Δ H = log p , \begin{equation}
E_{\Delta H}=\log p, \tag*{(34)}
\end{equation} E Δ H = log p , (34)
which makes it a much more interesting variable, and, in what follows, from all the E η E_\eta E η , we will be dealing only with E Δ H ℓ E_{\Delta H_\ell} E Δ H ℓ , the subscript will be dropped,
E = ∑ ℓ = 1 ∞ ( Δ H ℓ − h ) . \begin{equation}
E=\sum\limits_{\ell=1}^{\infty} (\Delta H_\ell-h). \tag*{(35)}
\end{equation} E = ℓ = 1 ∑ ∞ ( Δ H ℓ − h ) . (35)
E E E was introduced by Grassberger [68 ] under the name of effective measure complexity (EMC), but is also known as excess entropy [69 ] .
From the comment that was made after equation (3) , E E E is the minimal amount of information that has to be stored in order to make optimal predictions under absolute efficiency [68 ] . For sources where E E E converges, the minimal memory required is finite, and such sources have been called finitary [69 ] .
Consider the bi-infinite string u = u − u + u=u^-u^+ u = u − u + partition into two halves u − u^- u − and u + u^+ u + , the first known as the past and the latter as the future. Take the ℓ \ell ℓ last symbols from the past, u ℓ − u^-_\ell u ℓ − , and the first ℓ \ell ℓ symbols from the future, u ℓ + u^+_\ell u ℓ + ; the mutual information between the two finite strings is well defined
I [ u ℓ − , u ℓ + ] = H [ u ℓ + ] − H [ u ℓ + ∣ u ℓ − ] . \begin{equation}
I[u^-_\ell, u^+_\ell]=H[u^+_\ell]-H[u^+_\ell|u^-_\ell]. \tag*{(36)}
\end{equation} I [ u ℓ − , u ℓ + ] = H [ u ℓ + ] − H [ u ℓ + ∣ u ℓ − ] . (36)
The first term is equal to H ℓ H_\ell H ℓ , and the second term, using the chain rule, can be written as
H [ u ℓ + ∣ u ℓ − ] = ∑ i = 0 ℓ − 1 H [ u i ∣ u − ℓ u − ℓ + 1 … u i − 1 ] . H[u^+_\ell|u^-_\ell]=\sum\limits_{i=0}^{\ell-1}H[u_i|u_{-\ell}u_{-\ell+1}\ldots u_{i-1}]. H [ u ℓ + ∣ u ℓ − ] = i = 0 ∑ ℓ − 1 H [ u i ∣ u − ℓ u − ℓ + 1 … u i − 1 ] .
Using both terms, the following expression follows,
I [ u ℓ − , u ℓ + ] = H ℓ − ∑ i = 0 ℓ − 1 H [ u i ∣ u − ℓ u − ℓ + 1 … u i − 1 ] . \begin{equation}
I[u^-_\ell, u^+_\ell]=H_\ell-\sum\limits_{i=0}^{\ell-1}H[u_i|u_{-\ell}u_{-\ell+1}\ldots u_{i-1}]. \tag*{(37)}
\end{equation} I [ u ℓ − , u ℓ + ] = H ℓ − i = 0 ∑ ℓ − 1 H [ u i ∣ u − ℓ u − ℓ + 1 … u i − 1 ] . (37)
Consider the expression,
∑ i = 1 ℓ [ Δ H i − h ] = H ℓ − ℓ h \sum\limits_{i=1}^{\ell}[\Delta H_i-h]=H_\ell-\ell h i = 1 ∑ ℓ [ Δ H i − h ] = H ℓ − ℓ h
In the limit ℓ → ∞ \ell\rightarrow \infty ℓ → ∞ , this last expression is equal to E E E , but this is precisely the expression ((37) ) in the same limit; therefore, it has been proven that [69 ]
E = I [ u − , u + ] . \begin{equation}
E=I[u^-, u^+]. \tag*{(38)}
\end{equation} E = I [ u − , u + ] . (38)
The effective measure complexity is the mutual information between the two halves of the bi-infinite string u u u , further emphasising the interpretation given above. If convergence is uniform, then asymptotically [69 ]
H ℓ ∼ E + ℓ h , \begin{equation}
H_\ell\sim E+\ell h, \tag*{(39)}
\end{equation} H ℓ ∼ E + ℓ h , (39)
for ℓ ≫ 1 \ell\gg1 ℓ ≫ 1 .
As E E E is the mutual information between the two halves of the bi-infinite string, it can be written
E = H ( u − ) + H ( u + ) − H ( u ) . \begin{equation}
E=H(u^-)+H(u^+)-H(u). \tag*{(40)}
\end{equation} E = H ( u − ) + H ( u + ) − H ( u ) . (40)
The effective measure complexity is then a measure of how much more information is needed to specify the sequence u u u when it is split into two independent halves, u − u^- u − and u + u^+ u + , than to specify the single sequence u u u . This is consistent with the stated fact that, for a random sequence (and, indeed, for any i.i.d. sequence), E = 0 E=0 E = 0 ; any other (positive) value of E E E signals correlation in the sequence’s partition, and memory is then understood as a measure of such correlation.
Following from the above comment, there is something to be learned not only from the value of E E E , but also from the terms in the sum in equation (35) . If for a finite ℓ c \ell_c ℓ c , Δ H ℓ \Delta H_\ell Δ H ℓ converges to h h h , then correlations in the system can be found up to ℓ c \ell_c ℓ c . Even if that is not the case, the decreasing behaviour of the terms Δ H ℓ − h \Delta H_\ell-h Δ H ℓ − h as ℓ \ell ℓ increases is related to the decay of correlations in the system over time.
Algorithmic complexity provides an adequate framework for defining the informational distance between two strings [92 , 73 ] . What is sought is a measure of the minimal amount of information needed to compute one string from the other and vice versa. If this measure is to be considered a distance, apart from being non-negative, it must satisfy the identity axiom, that the distance from one string to itself of zero; the symmetry axiom, where the distance from string one to string two is equal to the distance from string two to string one; and the triangle inequality that states that the distance between two string is smaller or equal to the sum of the distance of both strings to a third one.
Let w 1 w_1 w 1 and w 2 w_2 w 2 be two strings. We define the information distance as the length of the shortest program that computes w 1 w_1 w 1 from w 2 w_2 w 2 as well as w 2 w_2 w 2 from w 1 w_1 w 1 . It can be shown that if
K ( w 1 ∣ w 2 ) > K ( w 2 ∣ w 1 ) , \begin{equation}
K(w_1|w_2)>K(w_2|w_1), \tag*{(41)}
\end{equation} K ( w 1 ∣ w 2 ) > K ( w 2 ∣ w 1 ) , (41)
Then the program that computes w 1 w_1 w 1 given w 2 w_2 w 2 can be made to contain the information needed to generate the program that computes w 2 w_2 w 2 given w 1 w_1 w 1 [92 ] . This last fact leads to defining the (absolute) informational distance as
d ∥ ( w 1 , w 2 ) = max { K ( w 1 ∣ w 2 ) , K ( w 2 ∣ w 1 ) } . \begin{equation}
d_\parallel(w_1,w_2)= \max\{K(w_1|w_2),K(w_2|w_1)\}. \tag*{(42)}
\end{equation} d ∥ ( w 1 , w 2 ) = max { K ( w 1 ∣ w 2 ) , K ( w 2 ∣ w 1 )} . (42)
The defined absolute distance is clearly non-negative and complies with the symmetric axiom, as well as the identity axiom up to a term O ( 1 / K ( w i ) ) O(1/K(w_i)) O ( 1/ K ( w i )) , where w i w_i w i is the string with the largest algorithmic complexity. In [73 ] , it is shown that it also complies with the triangular inequality, also up to a term O ( 1 / K ( w i ) ) O(1/K(w_i)) O ( 1/ K ( w i )) where w i w_i w i is now the string with the maximum Kolmogorov complexity of the three strings involved in the triangle inequality.
Zurek reasoned about the relation between algorithmic complexity and thermodynamic cost [93 , 91 ] : the minimum increase of thermodynamic entropy for a computation that turns string w 1 w_1 w 1 into w 2 w_2 w 2 , without retaining memory of the input or of the performed steps, should be equal to K ( w 1 ∣ w 2 ) + O ( 1 ) K(w_1|w_2)+O(1) K ( w 1 ∣ w 2 ) + O ( 1 ) . The demonstration is based on the Landauer principle that states that an erasure of a single bit implies a dissipation of energy of no less than k B T ln 2 k_BT\ln 2 k B T ln 2 , where k B T k_BT k B T is the Boltzmann product [94 ] . If w 2 w_2 w 2 contains all the information necessary to compute w 1 w_1 w 1 , then the process is reversible, and there is no increase in thermodynamic entropy. On the contrary, if w 1 w_1 w 1 cannot be recovered from w 2 w_2 w 2 , information has been lost, and thermodynamic entropy has increased. The absolute information distance can then be related to the maximum thermodynamic cost required to produce one string from the other, and vice versa.
The distance defined by ((42) ) encounters practical difficulties when comparing strings of different lengths. Two independent random strings of small length will have a smaller distance than two algorithmically related strings of much larger length, with just a small amount of dissimilar information. To avoid this dependence on the string length, the normalised informational distance has been defined as
d ( w 1 , w 2 ) = max { K ( w 1 ∣ w 2 ) , K ( w 2 ∣ w 1 ) } max { K ( w 1 ) , K ( w 2 ) } . \begin{equation}
d(w_1,w_2)= \frac{\max\{K(w_1|w_2),K(w_2|w_1)\}}{\max\{K(w_1),K(w_2)\}}. \tag*{(43)}
\end{equation} d ( w 1 , w 2 ) = max { K ( w 1 ) , K ( w 2 )} max { K ( w 1 ∣ w 2 ) , K ( w 2 ∣ w 1 )} . (43)
A discussion can be made on whether the denominator in ((43) ) is the proper normalisation factor; the reader can follow Li and Vitanyi [73 ] for a justification of the chosen factor.
From the definition of the conditional algorithmic complexity and the algorithmic mutual information, it follows
d ( w 1 , w 2 ) = 1 − K ( w 1 : w 2 ) K ( w 2 ) . \begin{equation}
d(w_1,w_2)=1-\frac{K(w_1:w_2)}{K(w_2)}. \tag*{(44)}
\end{equation} d ( w 1 , w 2 ) = 1 − K ( w 2 ) K ( w 1 : w 2 ) . (44)
where it has been assumed that K ( w 2 ) > K ( w 1 ) K(w_2)>K(w_1) K ( w 2 ) > K ( w 1 ) . From this last expression ((44) ), 1 − d ( w 1 , w 2 ) 1-d(w_1,w_2) 1 − d ( w 1 , w 2 ) is the amount of information (in bits) that is shared between both strings per bit of information of the string with the largest Kolmogorov complexity [73 ] .
The information distance should not be confused with entropy-based divergences between probability distributions, such as the Kullback-Leibler divergence or the Jensen-Shannon divergence [95 ] , whose square root is a metric [96 ] . Applied to two sequences, such divergences compare their (empirical) word distributions, and therefore quantify whether both sequences share the same statistics, that is, whether they look like realisations of the same source. The information distance quantifies instead how much information one individual sequence carries about the other. Two independent realisations of the same source have a vanishing Jensen-Shannon divergence but an information distance close to one, while two strongly coupled sequences with different statistics can be far apart in the Jensen-Shannon sense and close in the sense of d d d . The information distance is thus the appropriate measure when coupling, rather than statistical similarity, is sought, as in the case studies of § 9 . In addition, the Kullback-Leibler divergence is neither symmetric nor satisfies the triangle inequality, and both divergences require estimating length-ℓ \ell ℓ word distributions over α ℓ \alpha^\ell α ℓ cells, with the undersampling problems discussed in § 5.1 for the transfer entropy, whereas the estimate of d d d introduced in § 7 requires no block length.
If all strings involved are of the same length, in the right member of (\ref{eq:normd}) , the numerator and the denominator can be divided by the length and, in the limit of ℓ → ∞ \ell\rightarrow \infty ℓ → ∞ , the following expression follows
d ( w 1 , w 2 ) = max { h ( w 1 ∣ w 2 ) , h ( w 2 ∣ w 1 ) } max { h ( w 1 ) , h ( w 2 ) } . \begin{equation}
d(w_1,w_2)= \frac{\max\{h(w_1|w_2),h(w_2|w_1)\}}{\max\{h(w_1),h(w_2)\}}. \tag*{(45)}
\end{equation} d ( w 1 , w 2 ) = max { h ( w 1 ) , h ( w 2 )} max { h ( w 1 ∣ w 2 ) , h ( w 2 ∣ w 1 )} . (45)
The practical importance of this last expression is that while the Kolmogorov complexity is uncomputable, the entropy density is not. To achieve this, we have had to consider strings of the same length and normalised distance. In spite of the uncomputable nature of the Kolmogorov complexity, it has been demonstrated before that the growth rate of algorithmic complexity can be estimated, notably by Zurek, who derived the Sackur-Tetrode equation for the entropy of an ideal gas from the Kolmogorov complexity rate [91 ] .
Equation (45) will be used for computing the information distance between two sequences in practical terms and is the mathematical basis for the normalised compression distance used by Li and Vitanyi [73 ] .
Given a set of strings, the information distance between all pairs of strings allows us to build a distance matrix and, from there, an undirected weighted graph among the strings. Such a graph will be called an information graph. If a proper threshold is set, the distance matrix becomes a connectivity matrix, and the corresponding graph is unweighted and undirected.
Considering the inequality ((41) ), the net flow of information between two strings can be defined by [93 ] ,
Δ K = K ( w 1 ∣ w 2 ) − K ( w 2 ∣ w 1 ) . \begin{equation}
\Delta K=K(w_1|w_2)-K(w_2|w_1). \tag*{(46)}
\end{equation} Δ K = K ( w 1 ∣ w 2 ) − K ( w 2 ∣ w 1 ) . (46)
if Δ K > 0 \Delta K >0 Δ K > 0 , then the information flows from w 1 w_1 w 1 to w 2 w_2 w 2 , when Δ K < 0 \Delta K<0 Δ K < 0 , the opposite is true. The net flow allows us to turn the information graph into a directed graph that shows the flow of information in a given system.
As only the sign of Δ K \Delta K Δ K is of interest for the graph, the following variant can be used instead of equation (46) ,
Δ h = h ( w 1 ∣ w 2 ) − h ( w 2 ∣ w 1 ) . \begin{equation}
\Delta h=h(w_1|w_2)-h(w_2|w_1). \tag*{(47)}
\end{equation} Δ h = h ( w 1 ∣ w 2 ) − h ( w 2 ∣ w 1 ) . (47)
When the sign is not enough and actual values are needed, the same argument used to derive ((45) ) can be used to justify ((47) ), if both strings have the same length.
Flow of information as defined above is related but can not be identified with causality. Causality needs to account for the time in the flow of information between two strings. The concept of transfer entropy is then better suited for causality relations [97 ] .
Transfer entropy was introduced by Schreiber [97 ] to quantify directed, time-asymmetric dependence between two processes. For a target series w j w_j w j and a source series w i w_i w i , sampled as w j ( t ) w_j(t) w j ( t ) and w i ( t ) w_i(t) w i ( t ) , let w j ( m ) ( t ) = ( w j ( t ) , … , w j ( t − m + 1 ) ) w_j^{(m)}(t)=\big(w_j(t),\dots,w_j(t{-}m{+}1)\big) w j ( m ) ( t ) = ( w j ( t ) , … , w j ( t − m + 1 ) ) denote the m m m -block past. The transfer entropy from w i w_i w i to w j w_j w j is
T E w i → w j = ∑ P ( w j ( t + 1 ) , w j ( m ) ( t ) , w i ( m ) ( t ) ) log P ( w j ( t + 1 ) ∣ w j ( m ) ( t ) , w i ( m ) ( t ) ) P ( w j ( t + 1 ) ∣ w j ( m ) ( t ) ) , \begin{equation}
TE_{w_i\to w_j}=\sum P\big(w_j(t{+}1), w_j^{(m)}(t), w_i^{(m)}(t)\big)\,
\log\frac{P\big(w_j(t{+}1)\mid w_j^{(m)}(t),w_i^{(m)}(t)\big)}{P\big(w_j(t{+}1)\mid w_j^{(m)}(t)\big)}, \tag*{(48)}
\end{equation} T E w i → w j = ∑ P ( w j ( t + 1 ) , w j ( m ) ( t ) , w i ( m ) ( t ) ) log P ( w j ( t + 1 ) ∣ w j ( m ) ( t ) ) P ( w j ( t + 1 ) ∣ w j ( m ) ( t ) , w i ( m ) ( t ) ) , (48)
the sum over all realisations of its arguments. This is the conditional mutual information I ( w j ( t + 1 ) ; w i ( m ) ( t ) ∣ w j ( m ) ( t ) ) = H ( w j ( t + 1 ) ∣ w j ( m ) ( t ) ) − H ( w j ( t + 1 ) ∣ w j ( m ) ( t ) , w i ( m ) ( t ) ) I\big(w_j(t{+}1);w_i^{(m)}(t)\mid w_j^{(m)}(t)\big)=H\big(w_j(t{+}1)\mid w_j^{(m)}(t)\big)-H\big(w_j(t{+}1)\mid w_j^{(m)}(t),w_i^{(m)}(t)\big) I ( w j ( t + 1 ) ; w i ( m ) ( t ) ∣ w j ( m ) ( t ) ) = H ( w j ( t + 1 ) ∣ w j ( m ) ( t ) ) − H ( w j ( t + 1 ) ∣ w j ( m ) ( t ) , w i ( m ) ( t ) ) , the information the source past adds about the target’s next symbol beyond the target’s own past. It vanishes when that information is null and is in general asymmetric, T E w i → w j ≠ T E w j → w i TE_{w_i\to w_j}\neq TE_{w_j\to w_i} T E w i → w j = T E w j → w i .
The direct estimation of ((48) ) is problematic; it requires the joint distribution over a space of dimension 2 m + 1 2m+1 2 m + 1 ; for a symbolic source of alphabet size α \alpha α this is a histogram of α 2 m + 1 \alpha^{2m+1} α 2 m + 1 cells, so the sample size needed to populate it grows exponentially with the embedding order, and most cells remain empty or undersampled for realistic record lengths (for continuous data an additional partitioning or kernel step is required, introducing further free parameters). Plug-in entropy estimators are, moreover, systematically biased, and because the two terms of the difference live in spaces of different dimension their biases do not cancel, so that independent series can yield a spuriously positive value. The estimate is therefore sensitive to m m m , ℓ \ell ℓ , the embedding delay and the partition, and demands long stationary records [98 ] .
These difficulties motivate working with the per-symbol rate and estimating it without explicit density estimation. Taking the block pasts to the m m m -step past and normalising per symbol turns the block entropies of ((48) ) into entropy densities, and the transfer entropy rate from w i w_i w i to w j w_j w j becomes
T E R w i → w j = h ( w j ∣ w j < m ) − h ( w j ∣ w j < m , w i < m ) , \begin{equation}
TER_{w_i\to w_j}=h\big(w_j\mid w_j^{<m}\big)-h\big(w_j\mid w_j^{<m},w_i^{<m}\big), \tag*{(49)}
\end{equation} T E R w i → w j = h ( w j ∣ w j < m ) − h ( w j ∣ w j < m , w i < m ) , (49)
with w < m w^{<m} w < m the m m m -step past. Equation (49) is non-negative, vanishes when w i w_i w i ’s past adds no information about w j w_j w j ’s present, and is asymmetric under i ↔ j i\leftrightarrow j i ↔ j , thus encoding directionality [97 , 98 ] . It is the quantity estimated below with the Lempel-Ziv factorisation, where a same-dimension surrogate removes the residual bias that afflicts ((48) ).
Transfer entropy rate criterion.
At finite m m m and finite sequence length, the two densities in ((49) ) carry an embedding-dimension bias that does not cancel exactly. We remove it with a surrogate of the same embedding dimension: let S w i _\mathrm{S}w_i S w i be w i w_i w i with its past block time-permuted, which destroys its temporal relation to w j w_j w j while preserving its marginal statistics and the embedding size. The surrogate-corrected transfer entropy rate is
T E R ^ i → j = ⟨ h ^ ( w j ∣ w j < m , S w i < m ) ⟩ Γ − h ^ ( w j ∣ w j < m , w i < m ) , \begin{equation}
\widehat{\mathrm{TER}}_{i\to j}=\big\langle \widehat h\!\left(w_j\mid w_j^{<m}, {_\mathrm{S}w_i^{<m}}\right)\big\rangle_{\Gamma}-\widehat h\!\left(w_j\mid w_j^{<m},w_i^{<m}\right), \tag*{(50)}
\end{equation} TER i → j = ⟨ h ( w j ∣ w j < m , S w i < m ) ⟩ Γ − h ( w j ∣ w j < m , w i < m ) , (50)
where ⟨ ⋅ ⟩ Γ \langle\cdot\rangle_{\Gamma} ⟨ ⋅ ⟩ Γ averages over Γ \Gamma Γ surrogates. The surrogate reproduces the bias of the real estimate, so T E R ^ i → j ≥ 0 \widehat{\mathrm{TER}}_{i\to j}\ge 0 TER i → j ≥ 0 measures the genuine reduction in the entropy density of w j w_j w j due to w i w_i w i ’s real, as opposed to scrambled, past.
Lempel-Ziv factorisation
In this section, we follow [99 ] and [90 ] .
Given a string w w w , the set of all distinct words of w w w is called the vocabulary of w w w and is denoted by V ( w ) \mathcal{V}(w) V ( w ) . For example, w = 10011 w=10011 w = 10011 has vocabulary V ( w ) = { Λ , 0 , 1 , 10 , 00 , 01 , 11 , 100 , 001 , 011 , 1001 , 0011 , 10011 } \mathcal{V}(w) = \{ \Lambda, 0, 1, 10, 00, 01, 11, 100, 001, 011, 1001, 0011, 10011 \} V ( w ) = { Λ , 0 , 1 , 10 , 00 , 01 , 11 , 100 , 001 , 011 , 1001 , 0011 , 10011 } .
A sequence w w w can be partitioned into factors, that is, the concatenation of non-overlapping words,
w = F 1 F 2 … F n F , w=F_1F_2\ldots F_{n_F}, w = F 1 F 2 … F n F ,
such that the word F i ( w ) = w a i a i + 1 − 1 F_i(w)=w_{a_i}^{a_{i+1}-1} F i ( w ) = w a i a i + 1 − 1 , where a i a_i a i is the position in w w w at which the factor F i F_i F i begins.
A history of the finite string w w w is a factorisation such that
F i π ∈ V ( w 0 a i + 1 − 1 π 2 ) \begin{equation}
F_i\pi\in \mathcal{V}(w_{0}^{a_{i+1}-1}\pi^2) \tag*{(51)}
\end{equation} F i π ∈ V ( w 0 a i + 1 − 1 π 2 ) (51)
except, perhaps, for the first factor F 1 F_1 F 1 . π \pi π is the drop operator defined earlier. For example, for w = 1 ⋅ 0 ⋅ 01 ⋅ 11 ⋅ 010 ⋅ 110 ⋅ 00 ⋅ w=1\cdot0\cdot01\cdot11\cdot010\cdot110\cdot00\cdot w = 1 ⋅ 0 ⋅ 01 ⋅ 11 ⋅ 010 ⋅ 110 ⋅ 00 ⋅ , a history is described by the factors delimited by the dots.
Lempel-Ziv’s approach to sequence complexity derives from considering the unique history of w w w , which is the result of a recursive factor concatenation process starting from a prefix factor F 1 = w 0 ∈ A F_1 = w_0 \in \mathcal{A} F 1 = w 0 ∈ A that allows for innovation. Innovation, in this context, refers to the fact that each factor F i + 1 F_{i+1} F i + 1 adds a word to the vocabulary of the growing sequence V ( w 0 a i + 1 − 1 ) \mathcal{V}(w_{0}^{a_{i+1}-1}) V ( w 0 a i + 1 − 1 ) . Such a process is called an exhaustive production process and complies with,
F i ∉ V ( w 0 a i + 1 − 1 π ) , \begin{equation}
F_i\notin \mathcal{V}(w_{0}^{a_{i+1}-1}\pi), \tag*{(52)}
\end{equation} F i ∈ / V ( w 0 a i + 1 − 1 π ) , (52)
for all factors in the history of w w w , except, perhaps, the last factor of the factorisation.
For example, the exhaustive factorisation of the above example w = 10011101011000 w=10011101011000 w = 10011101011000 , will be 1 ⋅ 0 ⋅ 01 ⋅ 110 ⋅ 101 ⋅ 1000 1\cdot0\cdot01\cdot110\cdot101\cdot1000 1 ⋅ 0 ⋅ 01 ⋅ 110 ⋅ 101 ⋅ 1000 . An exhaustive factorisation is also called a Lempel-Ziv factorisation, L Z ( w ) LZ(w) L Z ( w ) . The Lempel-Ziv factorisation of a string is unique.
The Lempel-Ziv complexity of a sequence (from now on LZ-complexity) is defined as the number of factors in the exhaustive factorisation of the sequence,
C L Z ( w ) = ∣ L Z ( w ) ∣ . \begin{equation}
C_{LZ}(w)=|LZ(w)|. \tag*{(53)}
\end{equation} C L Z ( w ) = ∣ L Z ( w ) ∣. (53)
Lempel-Ziv complexity is a measure of a sequence’s innovativeness. Each factor in the Lempel-Ziv history corresponds to a single innovation (at the ending symbol of the factor). The larger the number of factors in L Z ( w ) LZ(w) L Z ( w ) , therefore, the larger the innovation process that produces the string. From this interpretation, it is clear that an appropriate normalisation of C L Z C_{LZ} C L Z can be taken, related to the innovation per symbol of the sequence.
Properties of the LZ-factorisation
The exhaustive history of a sequence is the smallest possible history factorisation.
Demonstration: See appendix § 17 .
For every string w w w with N = ∣ w ∣ N=|w| N = ∣ w ∣ ,
C L Z ( w ) < N ( 1 − ϵ N ) log N , \begin{equation}
C_{LZ}(w)<\frac{N}{(1-\epsilon_N)\log N}, \tag*{(54)}
\end{equation} C L Z ( w ) < ( 1 − ϵ N ) log N N , (54) where
ϵ N = 2 1 + log log ( α N ) log N . \begin{equation}
\epsilon_N=2\frac{1+\log\log (\alpha N)}{\log N}. \tag*{(55)}
\end{equation} ϵ N = 2 log N 1 + log log ( α N ) . (55) Demonstration: See appendix § 18 .
Let w w w be a string of length N ≫ 1 N\gg 1 N ≫ 1 emitted by an ergodic source of entropy density h h h . Then,
C L Z ( w ) ≤ N h / log N . \begin{equation}
C_{LZ}(w)\leq N h/\log N. \tag*{(56)}
\end{equation} C L Z ( w ) ≤ N h / log N . (56) Demonstration: See appendix § 19 .
Given the string formed by concatenating the sequences w 1 w_1 w 1 and w 2 w_2 w 2 , C L Z ( w 1 w 2 ) ≤ C L Z ( w 1 ) + C L Z ( w 2 ) C_{LZ}(w_1w_2)\leq C_{LZ}(w_1)+C_{LZ}(w_2) C L Z ( w 1 w 2 ) ≤ C L Z ( w 1 ) + C L Z ( w 2 ) .
Demonstration [99 ] : Consider a history of w 1 w 2 w_1w_2 w 1 w 2 , such that F ( w 1 w 2 ) = L Z ( w 1 ) ⋅ L Z ( w 2 ) F(w_1w_2)=LZ(w_1)\cdot LZ(w_2) F ( w 1 w 2 ) = L Z ( w 1 ) ⋅ L Z ( w 2 ) , that is the concatenation of the LZ-factorisation of w 1 w_1 w 1 and w 2 w_2 w 2 . From the first property C L Z ( w 1 w 2 ) ≤ ∣ F ( w 1 w 2 ) ∣ = C L Z ( w 1 ) + C L Z ( w 2 ) C_{LZ}(w_1w_2)\leq|F(w_1w_2)|=C_{LZ}(w_1)+C_{LZ}(w_2) C L Z ( w 1 w 2 ) ≤ ∣ F ( w 1 w 2 ) ∣ = C L Z ( w 1 ) + C L Z ( w 2 ) which proves the property.
Shannon entropy and LZ-factorisation
Define the normalized Lempel-Ziv complexity as [99 ]
c L Z ( u ) = lim sup N → ∞ C L Z ( u ) N / log N . \begin{equation}
c_{LZ}(u)=\limsup\limits_{N\rightarrow \infty} \frac{C_{LZ}(u)}{N/\log N}. \tag*{(57)}
\end{equation} c L Z ( u ) = N → ∞ lim sup N / log N C L Z ( u ) . (57)
From property 3, follows
c L Z ≤ h . \begin{equation}
c_{LZ}\leq h. \tag*{(58)}
\end{equation} c L Z ≤ h . (58)
On the other hand, in [90 ] it is shown that C L Z C_{LZ} C L Z is the basis for a lossless finite-state encoder, so according to the converse theorem of information theory [67 ] , it follows that
lim inf N → ∞ c L Z ≥ h . \begin{equation}
\liminf\limits_{N\rightarrow\infty} c_{LZ}\geq h. \tag*{(59)}
\end{equation} N → ∞ lim inf c L Z ≥ h . (59)
Combining inequalities ((58) ) and ((59) ), the following theorem [90 ] follows (theorem 7 of Ziv):
P [ ∣ c L Z ( u ) − h ∣ > ϵ ] = 0 , \begin{equation}
P\left[|c_{LZ}(u)-h|>\epsilon\right]=0, \tag*{(60)}
\end{equation} P [ ∣ c L Z ( u ) − h ∣ > ϵ ] = 0 , (60)
where ϵ > 0 \epsilon>0 ϵ > 0 is an arbitrary constant.
Estimation of entropic magnitudes using Lempel-Ziv factorisation
Entropy density
Theorem 7 7 7 of Ziv ((60) ) is the basis for using the Lempel-Ziv factorisation as an estimate of the entropy rate. The normalized Lempel-Ziv complexity has to be computed for a necessarily finite-length sequence, and therefore some error is unavoidable in the estimate. The error is related to ϵ N \epsilon_N ϵ N , but, as shown in [84 ] , Lempel-Ziv estimation of h h h is quite efficient at approximating the density rate even when relatively short sequences are used. This may come as a surprise, taking into account that ϵ N \epsilon_N ϵ N is a very slowly decaying function achieving a value of around 0.4 0.4 0.4 for a binary alphabet with strings as long as 1 1 1 million symbols, and only falls to 0.3 0.3 0.3 for a string length of 10 9 10^{9} 1 0 9 .
Consider u u u an infinite string that starts at i = 0 i=0 i = 0 . If u 0 N u_0^N u 0 N is a prefix of length N N N of u u u , then, by construction, C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) is a non-decreasing function of N N N . For very small sequences (N = 0 , 1 , 2 , 3 … N=0,1,2,3\ldots N = 0 , 1 , 2 , 3 … ), one should expect, in general, that C L Z ( u 0 N ) < N / log N C_{LZ}(u_0^N)<N/\log N C L Z ( u 0 N ) < N / log N does not need to be true. As N N N increases, the function N / log N N/\log N N / log N keeps growing while redundant subsequences start to appear in the string and the C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) starts to grow more slowly with intervals of plateau. The more redundant the string in terms of patterns, the slower the growth rate. It should be expected that the fastest-growing behaviour for C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) should be achieved for a random string.
Figure 1. Lempel-Ziv complexity and the asymptotic behaviour. The four plots show the Lempel-Ziv complexity as a function of the string length N N N , compared with the same curve for the asymptotic behaviour N / log N N/\log N N / log N (Dashed black line). (a): even and (b): 2ssp correspond to finite-state automata defined in Appendix § 21 . The first is the even process, which is controlled by a transition probability. Each colour corresponds to a different value of the transition probability. The second one (2ssp) is for the two-state symmetric process, which is also governed by a transition probability. (c): dna pertains to an experimental example, the DNA sequences of different mammals were used to factorise and estimate the complexity value. Finally, (d): random, stands for a random string. In all cases, the LZ-complexity is upper-bounded asymptotically by the asymptotic function as expected. What is interesting is that for large string size, the behaviour with the string length settles for an ansatz as described by equation (61) . For short string lengths, all examples except the random case deviate from the asymptotic curve, which can be significant, as shown in the DNA data. The inset in each plot is the histogram, and the closer Normal curve of the distribution of factor lengths in the Lempel-Ziv factorisation.
This is exemplified in Figure 1 where the C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) for four different symbol sources are shown as a function of the string length N N N . Two sources are unifilar finite-state automata, commonly discussed when analysing entropic measures [69 ] (see Appendix § 21 ). A third source is an experimental DNA sequence for mammals, and the fourth source is a random string. For the finite-state sources, the described behaviour can be readily observed, where for small sequence length C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) values are above the asymptotic N / log N N/\log N N / log N function, but as N N N increases, it falls below. In the DNA case, a number of sequences start with a growth rate for C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) well below the asymptotic curve and the pace of growth increases with N N N . Finally, for the random string, the C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) almost coincides with N / log N N/\log N N / log N for all the N N N range. One interesting feature of all four examples is that for large N N N values, C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) settles into a law
C L Z ( u 0 N ) = h N log N − κ , \begin{equation}
C_{LZ}(u_0^N)=h \frac{N}{\log N}-\kappa, \tag*{(61)}
\end{equation} C L Z ( u 0 N ) = h log N N − κ , (61)
with κ \kappa κ a constant. From this last equation
c L Z ( N ) = h − κ N / log N . \begin{equation}
c_{LZ}(N)=h-\frac{\kappa}{N/\log N}. \tag*{(62)}
\end{equation} c L Z ( N ) = h − N / log N κ . (62)
The estimation of the entropy density value from the c L Z ( N ) c_{LZ}(N) c L Z ( N ) of a finite sequence is underestimated by an amount κ log N / N \kappa\log N/N κ log N / N . One could be tempted to estimate h h h from the fit of C L Z ( u 0 N ) C_{LZ}(u_0^N) C L Z ( u 0 N ) vs N N N for large N N N values, but one must be warned that the slow convergence of c L Z ( N ) c_{LZ}(N) c L Z ( N ) implies that the fit will be highly sensitive to the smallest value N 0 = N N_0=N N 0 = N chosen to start the fit.
Amigó and Kennel have obtained an expression for the variance in the estimation of h h h by the normalized Lempel-Ziv complexity [100 ] . Let λ k \lambda_k λ k be the length of the k k k factor in the Lempel-Ziv factorisation of a string. It follows
N = ∑ k = 1 C L Z λ k , \begin{equation}
N=\sum\limits_{k=1}^{C_{LZ}}\lambda_k, \tag*{(63)}
\end{equation} N = k = 1 ∑ C L Z λ k , (63)
where N N N is the length of the string.
A normal distribution N ( μ , σ 2 ) \mathcal{N}(\mu,\sigma^2) N ( μ , σ 2 ) of the length of the factors, with mean μ \mu μ and variance σ 2 \sigma^2 σ 2 , is assumed. If n F n_F n F factors are considered to be drawn from a normal distribution, then the length N N N will be a random variable with expected value n F μ n_F\mu n F μ and variance n F σ 2 n_F\sigma^2 n F σ 2 . N N N can then be written as
N = n F μ + ( n F 1 / 2 σ ) Z , \begin{equation}
N=n_F\mu+(n_F^{1/2}\sigma)Z, \tag*{(64)}
\end{equation} N = n F μ + ( n F 1/2 σ ) Z , (64)
where Z Z Z is a random variable drawn from a normal distribution N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) . Let us reverse the point of view: fix N N N and consider n F n_F n F a random variable. In such a case, the estimated entropy density is
h ^ = n F log N / N \begin{equation}
\widehat{h}=n_F \log N/N \tag*{(65)}
\end{equation} h = n F log N / N (65)
and its standard deviation
σ h ^ = σ n F log N / N . \begin{equation}
\sigma_{\widehat{h}}=\sigma_{n_F} \log N/N. \tag*{(66)}
\end{equation} σ h = σ n F log N / N . (66)
From equation (64) ,
Z = N − n F μ n F 1 / 2 σ . \begin{equation}
Z=\frac{N-n_F\mu}{n_F^{1/2}\sigma}. \tag*{(67)}
\end{equation} Z = n F 1/2 σ N − n F μ . (67)
Propagating errors in this last equation
σ Z = ( d Z d n F ) σ n F , \begin{equation}
\sigma_Z=\left(\frac{\mathrm{d}Z}{\mathrm{d}n_F}\right)\sigma_{n_F}, \tag*{(68)}
\end{equation} σ Z = ( d n F d Z ) σ n F , (68)
but σ Z = 1 \sigma_Z=1 σ Z = 1 by construction, so, using equation (67)
σ n F = ∣ ( d Z d n F ) ∣ − 1 = 2 n F 3 / 2 σ n F μ + N . \begin{equation}
\sigma_{n_F}=\left|\left( \frac{\mathrm{d}Z}{\mathrm{d}n_F}\right)\right|^{-1}=\frac{2n_F^{3/2}\sigma}{n_F\mu+N}. \tag*{(69)}
\end{equation} σ n F = ( d n F d Z ) − 1 = n F μ + N 2 n F 3/2 σ . (69)
The best estimate for n F n_F n F is C L Z C_{LZ} C L Z , taking μ = N / C L Z \mu=N/C_{LZ} μ = N / C L Z , the following expression follows
σ h ^ = σ c L Z ( N ) 3 / 2 N log N , \begin{equation}
\sigma_{\widehat{h}}=\sigma\frac{c_{LZ}(N)^{3/2}}{\sqrt{N\log N}}, \tag*{(70)}
\end{equation} σ h = σ N log N c L Z ( N ) 3/2 , (70)
where equation (65) and ((66) ) were used. The reader must recall that σ 2 \sigma^2 σ 2 is the variance in the length of factors that can be obtained from the factorisation. Expression ((70) ) shows that the larger c L Z ( N ) c_{LZ}(N) c L Z ( N ) , the larger the error in its estimation.
Following the same procedure, we include the variance for a Poisson distribution in the factor length, resulting in
σ h ^ = c L Z ( N ) N . \begin{equation}
\sigma_{\widehat{h}}=\frac{c_{LZ}(N)}{N}. \tag*{(71)}
\end{equation} σ h = N c L Z ( N ) . (71)
The histogram over the factor length for each of the described processes can be well approximated by a Normal distribution (see insets in Figure 1 ), making the use of equation (70) as an estimate of the error in h ^ \widehat{h} h valid.
Figure 2. Convergence of the Lempel-Ziv entropy-density estimate with sequence length. Each row corresponds to one Hidden Markov Model process: (a) the two-state symmetric process (2SSP, top), (b) the even process (middle), and (c) RRXOR (bottom), swept across their full control-parameter range. Left column: the Lempel-Ziv estimate h ^ \widehat h h at four sequence lengths (N = 256 N=256 N = 256 ; 5,000 5{,}000 5 , 000 ; 50,000 50{,}000 50 , 000 ; 500,000 500{,}000 500 , 000 ) overlaid on the true entropy density (red), each curve independently normalised between 0 and 1, ( h − min ) / ( max − min ) (h-\min)/(\max-\min) ( h − min ) / ( max − min ) , to compare shape convergence independently of each process’s own entropy range. Right column: root-mean-square error of the raw, un-normalised h ^ \widehat h h against the true entropy density, computed over the same parameter sweep, as a function of sequence length (log scale). In both columns, entropy density shows no qualitative convergence failure for any of the three sources, only a shrinking quantitative bias.
The left column of Figure 2 are the plot of the estimated entropy density h ^ \widehat{h} h from the Lempel-Ziv factorisation for different sequence lengths in the already presented finite-state automata corresponding to the symmetric 2-state process (a), the even process (b) and the random-random-xor process (c) for all values of their control parameters. First, the estimate follows the general trend even for sequence lengths as short as 256 256 256 symbols, and it’s almost indistinguishable from the exact entropy density h h h for sequence lengths above 10 3 10^3 1 0 3 symbols. For the two-state symmetric process, the estimate is even better as it behaves almost identically to h h h for sequences of 256 256 256 symbols and above.
Effective measure complexity
Estimating the effective measure complexity is non-trivial. As a measure of correlation at all length scales, or the memory of the system, its precise evaluation implies, in the general case, sums over infinite terms [68 ] and convergence is usually slower than estimating entropy density. This makes any estimation more cumbersome than estimating the entropy density, both analytically and numerically, and less reliable for smaller sequence length.
One of the approaches followed, avoiding direct data estimation, is to try to build the minimal computational machine able to statistically reproduce the data. This approach was pioneered by Grassberger [68 ] and further developed by Crutchfield and Feldman [69 ] . In practice, such an approach has not gone beyond finite-state approximations of the data, and even then, the reconstruction procedure has been applied only to simple sources.
§ 4 singled out the entropy gain Δ H ℓ \Delta H_\ell Δ H ℓ , Eqs. (2) -(3) , as the preferred building block for the effective measure complexity: unlike h ℓ h_\ell h ℓ , ζ ℓ \zeta_\ell ζ ℓ or k ℓ k_\ell k ℓ , it converges to h h h monotonically and, by Appendix § 14 , at least as fast as h ℓ h_\ell h ℓ does, h ℓ ( u ) ≥ Δ H ℓ ( u ) ≥ h h_\ell(u)\geq \Delta H_\ell(u) \geq h h ℓ ( u ) ≥ Δ H ℓ ( u ) ≥ h .
The corresponding estimator is
Δ H ^ ℓ ≡ H ^ ℓ − H ^ ℓ − 1 , \begin{equation}
\Delta \widehat H_\ell \;\equiv\; \widehat H_\ell - \widehat H_{\ell-1}, \tag*{(72)}
\end{equation} Δ H ℓ ≡ H ℓ − H ℓ − 1 , (72)
and, inspired by Eq. (35) , the effective measure complexity is still estimated as
E ^ ( n ) = ∑ ℓ = 1 n ( Δ H ^ ℓ − h ^ ) = H ^ n − n h ^ , \begin{equation}
\widehat E(n) \;=\; \sum_{\ell=1}^{n}\left(\Delta \widehat H_\ell - \widehat h\right)
\;=\; \widehat H_n - n\,\widehat h, \tag*{(73)}
\end{equation} E ( n ) = ℓ = 1 ∑ n ( Δ H ℓ − h ) = H n − n h , (73)
with h ^ \widehat h h the entropy density of the original sequence estimated exactly as before, from the Lempel-Ziv factorisation. Only Δ H ^ ℓ \Delta \widehat H_\ell Δ H ℓ ’s have to be estimated, which involves the estimate of the block entropy H ℓ ( u ) H_\ell(u) H ℓ ( u ) – the Shannon block entropy of length-ℓ \ell ℓ .
Melchert and Hartmann’s approach [85 ] obtains this indirectly: partition u u u into non-overlapping blocks of length ℓ \ell ℓ , shuffle the blocks into a surrogate sequence u R S ( ℓ ) u^{RS(\ell)} u R S ( ℓ ) (destroying correlations above scale ℓ \ell ℓ while preserving the length-ℓ \ell ℓ block distribution exactly), and read H ℓ ( u ) H_\ell(u) H ℓ ( u ) off u R S ( ℓ ) u^{RS(\ell)} u R S ( ℓ ) ’s own Lempel-Ziv complexity via Ziv’s theorem.
This is a consistent estimator, but it inherits a slow-convergence property of the Lempel-Ziv complexity itself: once the number of distinct length-ℓ \ell ℓ blocks # ℓ \#_\ell # ℓ actually observed becomes comparable to the number of blocks m ℓ m_\ell m ℓ available to estimate their distribution from, the normalised Lempel-Ziv complexity underestimates entropy density by an amount that grows, not shrinks, with ℓ \ell ℓ . Under the non-overlapping partition above, m ℓ = N / ℓ m_\ell = N/\ell m ℓ = N / ℓ falls linearly as ℓ \ell ℓ grows while # ℓ \#_\ell # ℓ can grow as fast as min ( m ℓ , α ℓ ) \min(m_\ell,\alpha^{\ell}) min ( m ℓ , α ℓ ) so this regime is reached quickly: a controlled test with N = 5 × 10 5 N=5\times10^5 N = 5 × 1 0 5 i.i.d. draws over α = 28,256 \alpha=28{,}256 α = 28 , 256 equally likely categories – comparable to the # ℓ \#_\ell # ℓ vs. m ℓ m_\ell m ℓ balance reached at moderate ℓ \ell ℓ in the surrogate construction above – recovers only 55 55 55 -80 % 80\% 80% of the true entropy via Lempel-Ziv, depending on the exact draw.
To avoid the convergence problem, the surrogate-and-Lempel-Ziv step is replaced with a direct, coverage-adjusted estimate of H ℓ ( u ) H_\ell(u) H ℓ ( u ) from the block frequency histogram of u u u itself, following Chao and Shen [101 ] . Details are given in the Appendix § 20 .
Choice of n n n
It is left to define a convenient limit n n n for the sum in Eq. (73) . For a sequence of length N N N , the maximum n n n that can be examined with reliable statistical significance is inherently limited. A common estimate derives from assuming the sequence contains roughly N / n N/n N / n independent n n n -words, yielding the condition N ≥ n α n N \geq
n\,\alpha^n N ≥ n α n . This approximation is only accurate for independently and identically distributed sequences, where any dependence among n n n -words arises solely from their overlapping nature – the same caveat that applies, one level down, to the sliding-window histogram of Eq. (113) itself: consecutive windows share ℓ − 1 \ell-1 ℓ − 1 symbols and are therefore not independent draws, even though there are N − ℓ + 1 N-\ell+1 N − ℓ + 1 of them. Sliding rather than partitioning changes how much of the sequence’s information content is sampled at each ℓ \ell ℓ , easing the severely-undersampled regime identified above; it does not change how much information content the sequence has at that ℓ \ell ℓ , so it does not relax the bound below.
Lesne et al. [84 ] considered more realistic scenarios in which intrinsic correlations within the sequence also influence the n n n -words and must be accounted for. By interpreting the entropy rate h h h as the average amount of new independent information contributed per observed symbol, the nominal sequence length can be replaced with an effective length N e f f ≈ N h N_{\mathrm{eff}} \approx N h N eff ≈ N h . This adjustment incorporates the effect of internal correlations. Consequently, the constraint on n n n becomes more restrictive,
n α n ≤ N h . \begin{equation}
n\,\alpha^n \;\leq\; N h. \tag*{(74)}
\end{equation} n α n ≤ N h . (74)
Claiming that the estimated E ^ \widehat E E equals the effective measure complexity would be too strong, but its behaviour resembles that of E E E , as shown in Figure 3 . In Figure 4 the estimated effective measure complexity for the logistic map is shown (left), together with the complexity entropy map (right), which the reader can compare to the corresponding plots of Fig. 1 and 2, in [77 ] . The estimated E ^ \widehat E E captures properties of the sequence similar to those of the effective measure complexity, with the correspondence expected to be closest for sources whose correlation structure decays uniformly across their parameter space, and to require correspondingly larger n n n — and hence longer sequences, per Eq. (74) — for sources whose synchronisation time varies strongly with the source’s own control parameters.
Figure 3. Estimation of the effective measure complexity. Convergence of the effective measure complexity estimate across three Hidden Markov Model processes. Each row corresponds to one source: (a) the two-state symmetric process (2SSP, top), (b) the even process (middle), and (c) RRXOR (bottom). The control parameter τ \tau τ is the transition probability of the two-state symmetric and even processes, and p p p is the probability of a 1 1 1 in the two free symbols of each RRXOR block (Appendix § 21 , Figure 9 ). Left column: the estimate E ^ \widehat E E at four sequence lengths (N = 256 N=256 N = 256 ; 5,000 5{,}000 5 , 000 ; 50,000 50{,}000 50 , 000 ; 500,000 500{,}000 500 , 000 ) overlaid on the true effective measure complexity (red), each curve independently min-max normalized, ( E − min ) / ( max − min ) (E-\min)/(\max-\min) ( E − min ) / ( max − min ) , to compare shape convergence on a common scale. Right column: root-mean-square error of the raw, un-normalized E ^ \widehat E E against the true curve, over the same restricted range, as a function of sequence length. 2SSP converges cleanly to a low error floor by N = 50,000 N=50{,}000 N = 50 , 000 ; the even process and RRXOR both improve steadily but substantially more slowly, and neither has reached a comparable floor even at N = 500,000 N=500{,}000 N = 500 , 000 , reflecting the longer block-size resolution their correlation structure demands relative to what H ^ ℓ \widehat H_\ell H ℓ can reliably support at this sample size.
Figure 4. Estimation of the effective measure complexity in the logistic map. The effective measure complexity estimated for the logistic map. (left) E ^ \widehat{E} E as a function of the control parameter r r r ; (right) The complexity-entropy map. Both plots can be compared to figures 1 and 2 of [77 ] .
Following expression ((45) ), the conditional entropy can be written as h ( w 1 ∣ w 2 ) = h ( w 2 w 1 ) − h ( w 2 ) h(w_1|w_2)=h(w_2w_1)-h(w_2) h ( w 1 ∣ w 2 ) = h ( w 2 w 1 ) − h ( w 2 ) which leads to the expression
d ^ ( w 1 , w 2 ) = max { h ^ ( w 2 w 1 ) − h ^ ( w 2 ) , h ^ ( w 1 w 2 ) − h ^ ( w 1 ) } max { h ^ ( w 1 ) , h ^ ( w 2 ) } , \begin{equation}
\widehat{d}(w_1,w_2)= \frac{\max\{\widehat{h}(w_2w_1)-\widehat{h}(w_2),\widehat{h}(w_1w_2)-\widehat{h}(w_1)\}}{\max\{\widehat{h}(w_1),\widehat{h}(w_2)\}}, \tag*{(75)}
\end{equation} d ( w 1 , w 2 ) = max { h ( w 1 ) , h ( w 2 )} max { h ( w 2 w 1 ) − h ( w 2 ) , h ( w 1 w 2 ) − h ( w 1 )} , (75)
for estimating the informational distance. w 2 w 1 w_2w_1 w 2 w 1 is taken as the ordered concatenation of sequences w 2 w_2 w 2 and w 1 w_1 w 1 . The entropy densities h ^ \widehat{h} h involved in equation (75) can be estimated by the Lempel-Ziv factorisation as explained above. It must be noted that strictly speaking, K ( w 1 ∣ w 2 ) ≈ K ( w 2 w 1 ) − K ( w 2 ) K(w_1|w_2)\approx K(w_2w_1)-K(w_2) K ( w 1 ∣ w 2 ) ≈ K ( w 2 w 1 ) − K ( w 2 ) as there is a logarithmic correction which becomes negligible for long enough sequences, and therefore the distance computed using ((75) ) must not be for too short strings. However, if all strings studied are of the same length, then, without regard to the sequence’s size, the distance can be used as a relative measure.
Following the same idea but starting with equation (47) , the information flow can be estimated as
Δ h ^ = h ^ ( w 2 w 1 ) − h ^ ( w 1 w 2 ) + h ^ ( w 1 ) − h ^ ( w 2 ) . \begin{equation}
\Delta \widehat{h}=\widehat{h}(w_2w_1)-\widehat{h}(w_1w_2)+\widehat{h}(w_1)-\widehat{h}(w_2). \tag*{(76)}
\end{equation} Δ h = h ( w 2 w 1 ) − h ( w 1 w 2 ) + h ( w 1 ) − h ( w 2 ) . (76)
Δ h ^ > 0 \Delta \widehat{h}>0 Δ h > 0 means that information flows from w 1 w_1 w 1 to w 2 w_2 w 2 , negative value will signal the opposite flow.
It must be clear what the distance expressed by equation (75) measures when h ^ \widehat{h} h is estimated by the Lempel-Ziv complexity, as compared to the more general definition using Kolmogorov complexity given by equation (43) . The informational distance, as defined by Kolmogorov complexity, pertains to how hard it is, algorithmically, to go from one sequence to another; ‘‘hard’’ here is measured by the length of the algorithm. In this regard, the informational distance is not a Hamming type of distance, it does not measure pairwise, how different are two strings and actually, a string of symbols and its negation will have (near to) zero informational distance, while the normalized Hamming distance will be 1 1 1 , as can be seen in the following example, where the string w w w is the negation of w ~ \tilde{w} w ~ and the Hamming field H \mathcal{H} H is composed of only one’s:
w = 10110010011101010111100000 w ~ = 01001101100010101000011111 H = 11111111111111111111111111. \begin{array}{l}
w=10110010011101010111100000\\
\tilde{w}=01001101100010101000011111\\
\mathcal{H}=11111111111111111111111111.
\end{array} w = 10110010011101010111100000 w ~ = 01001101100010101000011111 H = 11111111111111111111111111.
However, a small algorithm of the type shown in Algorithm alg:neg will do the job, yielding a near-zero information distance.
\begin{algorithmic}[1]
\For{$i$ from $1$ to $N$}
\State $\tilde{w}_i = w_i \otimes 1$
\EndFor
\State Print $\tilde{w}_i$
\end{algorithmic}
\caption{Computing the negated string $\tilde{w}$ from string $w$. The XOR operator is represented by $\otimes$}
\label{alg:neg}
The same follows for a string of symbols and its reverse, where pairwise distance can be near one, and the Kolmogorov complexity would be, in all cases, (near) zero.
Figure 5. Estimation of information distance by Lempel-Ziv complexity. Both plots show the information distance between the output string of the even process and a surrogate string for the whole range of transition probabilities. (a) The information distance between the string w w w and its negated string w ~ \tilde{w} w ~ (= w ⊗ 1 =w\otimes 1 = w ⊗ 1 , where ⊗ \otimes ⊗ is the XOR logical operator). (b) The information distance between the string w w w and the reversed string w ˘ \breve{w} w ˘ . The inset shows a detailed scale of the same plot. In both cases, the distance is nearly 1 1 1 for all transition probabilities, except for τ = 0 , 1 \tau=0,1 τ = 0 , 1 .
When changing to a distance based on the definition ((75) ), where h ^ \widehat{h} h is estimated by the Lempel-Ziv complexity, it must be understood that Lempel-Ziv factorisation is a pattern-driven procedure; it grows as new patterns emerge in the sequence. In this sense, it is also not a pairwise distance, but it is not all-encompassing as the Kolmogorov distance. The Lempel-Ziv-based distance can also be near 1 for two strings, whereas the Kolmogorov-based distance renders them close.
Figure 5 shows, on the left, the plot of d ^ \widehat{d} d using Lempel-Ziv of the sequence of symbols produced by the even process for different values of the transition probability τ \tau τ and the negated string, while on the right, a similar plot with the distance between the process string and its reverse. Except for the values at τ = 0 , 1 \tau=0,1 τ = 0 , 1 , d ^ \widehat{d} d is near one in all other cases. This implies that when using Lempel-Ziv to compute the distance between two sequences, care must be taken to include, when necessary, simple operations that make sense for the process being analysed but are not captured by the Lempel-Ziv factorisation.
Let us clarify this last statement. We are not interested in abstract mathematical sources but rather in physical processes that can be considered sources of symbols (e.g., DNA, RNA, or the discretisation of a time signal). The physical laws governing the process will ultimately define a grammar for the source and the operations that can be regarded as within the ‘‘natural order’’ of the analysed system. It is within that set of rules that possible operations must be sought that can lead to a sequence transformation that could be missed by the Lempel-Ziv factorisation. Fortunately, this set of rules is almost always simple operations, and there is no need to seek involved ‘‘non-natural’’ transformations of the symbol sequence to compare with.
In most cases, a simple procedure as follows will suffice for calculating the distance between two strings w 1 w_1 w 1 and w 2 w_2 w 2 :
Compute the distance d ^ \widehat{d} d between w 1 w_1 w 1 and w 2 w_2 w 2 .
Compute the distance d ^ \widehat{d} d between w 1 w_1 w 1 and the reverse of w 2 w_2 w 2 .
Compute the distance d ^ \widehat{d} d between w 1 w_1 w 1 and some well defined negation of w 2 w_2 w 2 .
Take the distance as the smallest one among the three calculated distances.
Transfer entropy
The conditional entropy densities in ((50) ) are estimated with the Lempel-Ziv factorisation over an extended alphabet, with the target and conditioner roles assigned as required by each term. Let s i ( t ) s_i(t) s i ( t ) be the mean-binarised sequence of w i w_i w i (α = 2 \alpha=2 α = 2 ). For a target series with present s i ( t ) s_i(t) s i ( t ) and a conditioner s j s_j s j , form at each t = m , … , T − 1 t=m,\dots,T-1 t = m , … , T − 1 the state vector
v t = ( s j ( t − m ) , … , s j ( t − 1 ) ⏟ conditioner past , s i ( t − m ) , … , s i ( t − 1 ) ⏟ target past , s i ( t ) ⏟ target present ) ∈ { 0 , … , α − 1 } M , M = 2 m + 1 , \begin{equation}
v_t=\big(\underbrace{s_j(t{-}m),\dots,s_j(t{-}1)}_{\text{conditioner past}},\;\underbrace{s_i(t{-}m),\dots,s_i(t{-}1)}_{\text{target past}},\;\underbrace{s_i(t)}_{\text{target present}}\big)\in\{0,\dots,\alpha{-}1\}^{M},\quad M=2m+1, \tag*{(77)}
\end{equation} v t = ( conditioner past s j ( t − m ) , … , s j ( t − 1 ) , target past s i ( t − m ) , … , s i ( t − 1 ) , target present s i ( t ) ) ∈ { 0 , … , α − 1 } M , M = 2 m + 1 , (77)
and it collapses to a single symbol over an alphabet of size α ~ = α M \tilde\alpha=\alpha^{M} α ~ = α M by the encoding
z t = ∑ r = 0 M − 1 α r v t [ r ] ∈ { 0 , … , α ~ − 1 } . \begin{equation}
z_t=\sum_{r=0}^{M-1}\alpha^{r}\,v_t[r]\in\{0,\dots,\tilde\alpha-1\}. \tag*{(78)}
\end{equation} z t = r = 0 ∑ M − 1 α r v t [ r ] ∈ { 0 , … , α ~ − 1 } . (78)
Applying the entropy-density estimate of Eq. (65) to the resulting sequence z m T − 1 z_m^{T-1} z m T − 1 of length N = T − m N=T-m N = T − m , with the logarithm taken in base α ~ \tilde\alpha α ~ , gives
h ^ ( w i ∣ w j ) = C L Z ( z m T − 1 ) log α ~ N N . \begin{equation}
\widehat h(w_i\mid w_j)=\frac{C_{LZ}\!\left(z_m^{T-1}\right)\log_{\tilde\alpha} N}{N}. \tag*{(79)}
\end{equation} h ( w i ∣ w j ) = N C L Z ( z m T − 1 ) log α ~ N . (79)
The marginal density h ^ ( w i ) \widehat h(w_i) h ( w i ) follows by dropping the conditioner block (M = m + 1 M=m+1 M = m + 1 ). Encoding the embedded state as one letter over α ~ = α M \tilde\alpha=\alpha^{M} α ~ = α M is the multivariate generalisation of Lempel-Ziv complexity to vector-valued processes [102 ] , and placing the target’s present alongside the joint past makes ((79) ) a conditional rather than a joint rate [98 ] . Unlike a plain concatenation of the two strings, the embedding preserves the temporal alignment between the conditioner’s past and the target’s present, so the estimate responds to a lagged influence w j → w i w_j\to w_i w j → w i .
Lempel-Ziv algorithm
We developed lzcomplexity [103 ] , an open-source library implemented in C++ and Python that computes the entropic magnitudes described from the Lempel-Ziv factorisation. The algorithms have been optimised to fully exploit current computing power by implementing parallel processing that significantly accelerates performance. The parallel implementation of the algorithms uses the Intel oneTBB library [104 ] .
The algorithm used to obtain the factorisation consists of three phases [105 ] . The initial phase lexicographically sorts all suffixes of the input sequence. From the array of all sorted suffixes (SA), the lengths of the longest common prefixes (LCP) between consecutive suffixes are obtained. With the sorted suffixes, the second phase proceeds, where the longest previous factor (LPF) [106 ] is computed for each position. Finally, the LZ76 factorisation is obtained from the LPF array. Details will be given elsewhere.
The implementation shows execution-time improvements of more than 10 10 10 -fold compared to sequential algorithms for long (> 10 6 >10^6 > 1 0 6 ) strings, and supports processing strings as large as 10 9 10^9 1 0 9 symbols. The developed software can be obtained at https://github.com/pleros-ai/lzcomplexity [103 ] .
Case studies
Brain connectivity
The human brain’s function relies on a complex interplay of organisation across multiple scales, from individual neurons to large-scale networks. The “connectome,” or the map of structural and functional connections between brain regions, is central to understanding cognition and behaviour. Abnormalities in this network are linked to various neurological and psychiatric conditions, making its study crucial for diagnosis and treatment. Inferring these connections from imaging data such as fMRI is challenging: current methods often rely on strong assumptions, are limited to linear dynamics, or are sensitive to user-defined parameters, obscuring the brain’s inherently non-linear behaviour.
To overcome these limitations, we proposed a novel, model-free analytical approach grounded in entropic magnitudes introduced above. Instead of assuming linear correlations, the method characterises each region by its unpredictability (entropy density h ^ \widehat h h ) and its memory (effective measure complexity E ^ \widehat E E ), and uses the informational distance d ^ \widehat d d to assess functional connections. It thus detects both linear and non-linear dynamics without prior assumptions about the data, providing a generalisable characterisation of cognitive states across experimental conditions and signal types.
The fMRI data used in this study were sourced from the Human Connectome Project (HCP), for subjects performing a motor task cued for finger tapping, toe squeezing, or tongue movement. The brain was parcellated into 360 360 360 regions of interest (ROIs) using the Glasser atlas [107 ] (180 180 180 ROIs per hemisphere).
The data is discretised before estimating the entropic magnitudes. For each time series, the mean value is computed and used as the binarisation threshold. Binarisation results in the loss of information from the original signal, but it is assumed that the binarised strings still contain sufficient relevant information about the system’s dynamics. If this is the case, it can only be asserted by the results themselves.
Figure 6. Brain connectome through the entropic magnitudes.(a) The complexity-entropy map, E ^ \widehat{E} E vs h ^ \widehat{h} h , for the 360 360 360 brain parcellations during the motor task. Active regions (left of the vertical green line) cluster at lower h ^ \widehat h h and higher E ^ \widehat E E , reflecting less unpredictability and stronger pattern formation. Inactive regions exhibit higher randomness, as they do not suppress the noisy background [108 ] . (b) Brain surface mapping of entropy density showing the normalized h ^ \widehat{h} h for each ROI projected onto the cortical surface, red indicates lower h ^ \widehat{h} h (more active); blue indicates higher h ^ \widehat{h} h (less active). The visual regions, motor and sensory cortex are activated during the task. (c) The distance map. The informational distance was computed between all region pairs via equation (75) and ordered by activation level. Active regions (red square) lie farthest from non-active ones, while non-active regions cluster together. (d) Dendrogram from the distance matrix illustrating hierarchical relationships. Arrows point to active regions, indicating clusters of visual, motor, and attentional processing, with strong associations among them.
Figure 6 (a) shows the complexity-entropy of the different regions of the brain in the motor task. For this task all regions lie above h ^ = 0.75 \widehat h = 0.75 h = 0.75 and E ^ = 0.5 \widehat E = 0.5 E = 0.5 , placing them in a regime between complete predictability and total randomness, the hallmark of complex dynamics. The points form a continuum rather than distinct clusters, so no fixed cut separates active from inactive regions. We segment the map objectively from the residuals of a linear fit: a local threshold is computed for each point’s neighbourhood, cleanly splitting the map in two. Informed by previous studies suggesting that inactive regions exhibit more random signal patterns [108 ] , the side of the map with lower entropy density (and higher complexity) is taken as active. This criterion identifies a small subset of regions for every task; for the motor task, 8.61 % 8.61\% 8.61% of regions are classified as active.
The position of the active regions relative to the linear fit carries functional information. Most primary and sensory motor regions lie above the fit, generating more pattern complexity than the trend predicts for their entropy density, whereas the main visual areas lie below it. Reading the regression as the mean E ^ \widehat E E –h ^ \widehat h h relation, the motor and sensory cortices “overperform” in pattern generation while the visual areas “underperform” during this task: the motor response demands precisely coordinated movement, whereas the sustained visual cue allows looser visual engagement. This separation of regions that share an activation status but differ in dynamical regime is information that a single-amplitude activation measure cannot provide.
Projecting the normalised h ^ \widehat h h onto the cortical surface (Figure 6 (b)) shows that the active set is not scattered but anatomically coherent. The lowest h ^ \widehat h h values concentrate in the occipital visual areas and in the motor and sensory cortices of the posterior precentral gyrus, the two systems the task engages: a visual cue followed by a coordinated movement of fingers, toes, or tongue. The activation pattern recovered by the entropic criterion matches the known substrate of the task, obtained without a design matrix, a hemodynamic model, or any tuned parameter.
Functional connections were obtained from the LZ-distance d ^ \widehat d d between all 360 360 360 ROIs. The resulting distance matrix, ordered by increasing h ^ \widehat h h (Figure 6 (c)), was clustered with the Neighbour-Joining method to produce the dendrogram of Figure 6 (d). Regions with similar h ^ \widehat h h are close in d ^ \widehat d d (the diagonal band), but this band narrows sharply over the active block, indicating tighter functional coupling among active regions. Active regions cluster together at low levels of the dendrogram, and regions of similar functional roles group consistently: visual areas of the occipital lobe form one cluster, primary motor/sensory and premotor regions another, and a third, heterogeneous cluster integrates occipital, lateral-frontal, and lateral-parietal regions with mixed visual, motor, and attentional roles. The full region-by-region assignment is reported in the companion study [109 ] .
This example uses the motor task to illustrate the pipeline. Applied unchanged to memory, emotion, language, and resting-state data, the same measures recover task-relevant activation and modular functional structure, and the active sets agree with GLM and meta-analytic references; these results are detailed in [109 ] .
Non-linear locally coupled oscillators
Coupled non-linear oscillators under weak coupling have been extensively studied since the foundational work of Winfree [110 ] , which established the oscillator phase as the key dynamical variable, superseding amplitude-based descriptions. This framework was anticipated by Adler’s analysis of locking in feedback circuits [111 ] , leading to the phase equation for Adler-type oscillators:
d θ d t = − γ sin θ + Δ ω , \begin{equation}
\frac{\mathrm{d}\theta}{\mathrm{d}t}=-\gamma \sin \theta +\Delta \omega, \tag*{(80)}
\end{equation} d t d θ = − γ sin θ + Δ ω , (80)
where θ \theta θ denotes the phase, γ \gamma γ a control parameter, and Δ ω \Delta \omega Δ ω the frequency detuning. This formulation was later generalised to ensembles of coupled oscillators, culminating in the Kuramoto model [112 ] , which describes globally coupled oscillators via harmonic signals and has become a paradigm for studying synchronisation across physics, biology, and neuroscience [113 ] .
Recent work has introduced a system of locally coupled Adler-type oscillators arranged in a ring with nearest-neighbour interactions as shown in Figure 7 (a)[114 ] :
d θ i d t = ω + γ cos θ i + ( − 1 ) i [ cos θ i − 1 + cos θ i + 1 ] . \begin{equation}
\frac{\mathrm{d}\theta_i}{\mathrm{d}t}=\omega+\gamma \cos \theta_i+(-1)^ i \left [ \cos \theta_{i-1}+\cos \theta_{i+1}\right ]. \tag*{(81)}
\end{equation} d t d θ i = ω + γ cos θ i + ( − 1 ) i [ cos θ i − 1 + cos θ i + 1 ] . (81)
Equations (81) are integrated numerically with a fourth-order Runge-Kutta method, and the entropic magnitudes are computed from the discretised phase activity sin θ i \sin\theta_i sin θ i , following Ref. [115 ] . The phase activity is binarised with its mean value as threshold: values greater than or equal to the mean are mapped to 1 1 1 and the remaining ones to 0 0 0 . The temporal evolution of each oscillator thus becomes a binary string, and the spatial configuration of the ring at a given time a binary string of length equal to the number of oscillators.
This model exhibits a diverse configuration diagram as seen by the h ^ \widehat{h} h value, as a function of two control parameters (Figure 7 (b)), revealing regimes with distinct spatiotemporal dynamics: an absorbing region with near-zero entropy, a chaotic region with high sensitivity and disorder, a wedge region characterized by long-range correlations, and a needle region displaying intermediate complexity and intricate patterns [115 ] . Notably, the system exhibits a transition to chaos as the needle regions is abandoned while γ \gamma γ decreases, where computational capabilities—namely information storage, transmission, and modification—are enhanced near the edge of chaos [116 , 117 , 118 ] , supporting the hypothesis that dynamical systems poised at this transition can function as optimized computational substrates [119 , 120 , 121 , 122 ] .
Figure 7. Non-linear locally coupled oscillators. (a) Adler-type oscillators are coupled to their nearest neighbours as described by equation (81) , forming a circular chain. (b) The entropy density map as a function of the control parameters ω \omega ω and γ \gamma γ . Four regions are identified by the entropic magnitudes. The absorbing region has zero entropy density, while the chaotic region has a value near 1 1 1 . For the wedge region, the entropy density is higher than the absorbing region but still lower than 1 / 2 1/2 1/2 . Low values of h h h characterise the needle region. (c) Spatio-temporal map for γ = 1.206 \gamma=1.206 γ = 1.206 and ω = 2.225 \omega=2.225 ω = 2.225 at the border between the needle and the chaotic region (edge of chaos boundary). Wave-like patterns can be identified. Time is on the horizontal scale, and the oscillator’s values are displayed vertically in consecutive order. (d) Detail of the spatio-temporal map. Point 1 1 1 is in the chaotic region, while point 5 is well within the needle region; all other points are at the border of the needle-chaotic regions. (e) The informational distance map for all points shown in (d) is split into even (above) and odd (below) oscillators. In the chaotic region (point 1), no distinguishable pattern is observed; by contrast, in the rest of the analysed points, characteristic patterns are seen in the maps. (f) The complexity-entropy map for each point shown in (d) in the chaotic region (point 1) shows that the odd and even oscillators are clearly segmented, with the even oscillators having higher h ^ \widehat{h} h values and lower E ^ \widehat{E} E values. The segmentation becomes less clear for points on the edge of the chaos boundary, but there is still a clear grouping for each type of oscillator. At point 5, well within the needle region, the two sets of oscillators are again clearly segmented, with higher E ^ \widehat{E} E values for both sets and smaller h ^ \widehat{h} h values.
The needle region has an estimated entropy density near zero, while the effective measure complexity approaches 3 3 3 . At the lower boundary of the needle region, there is a surge in the E ^ \widehat{E} E value and a sudden fall to zero. It is at this surge point that enhanced system performance is expected. One such point is at ω = 2.225 \omega=2.225 ω = 2.225 , γ = 1.206 \gamma=1.206 γ = 1.206 , and the spatial-temporal diagram shown in Figure 7 (c) exhibits a complex pattern with local spatial arrangements seen as wave-like patterns in the oscillator’s behaviour, signalling that lasts for long temporal intervals.
When carefully studying the system behaviour with ω = 2.225 \omega=2.225 ω = 2.225 fixed and γ \gamma γ varied (Figure 7 (d)), several distinct pictures emerge. What is striking is that couplings seem to emerge between odd-indexed oscillators and between even-indexed oscillators, as seen in the d ^ \widehat{d} d maps shown in Figure 7 (e). While at point 1, within the chaotic region no recognizable pattern is seen in the informational distance map, but the E ^ \widehat{E} E vs h ^ \widehat{h} h complexity-entropy map (Figure 7 (f)) clearly shows that both set of oscillators, even and odd, can be segmented by their values of both entropic magnitudes. The even oscillators exhibit higher entropy density and lower E ^ \widehat{E} E values. As the studied points approach the edge and the needle region, clear patterns emerge in the distance map (points 2, 3, 4 in Figure 7 (d)) for both sets of oscillators. The entropic behaviour of the two groups of oscillators converges, as evidenced by the entropy-complexity map (Figure 7 (f)). Patterns in the distance map are a sign of coupling in the oscillators and therefore of collective behaviour. Well within the needle region, at point 5 in Figure 7 (d) the entropy-complexity map again shows a clear segmentation of odd and even oscillators but, compared to what was seen in point 1, the range of h ^ \widehat{h} h values for both groups overlaps, and the difference is mostly seen as a gap between the E ^ \widehat{E} E values of both sets.
Electrocardiogram analysis
Figure 8. Electrocardiogram analysis.(a) ECG of a healthy subject (below) and a subject with atrial fibrillation (above). The AFIB patient has irregular heart rate behaviour. (b) The recurrence map of the (left) AFIB patient and the (right) healthy subject. The SR subject’s map shows clear, long diagonal lines parallel to the main diagonal, which are absent in the AFIB subject’s map. (c) The complexity-entropy map, derived from the estimation of the entropy density h ^ \widehat{h} h and the effective measure complexity E ^ \widehat{E} E for each row of the recurrence matrix. SR and AFIB subjects are clearly segmented, with healthy subjects exhibiting higher E ^ \widehat{E} E and lower h ^ \widehat{h} h . (d) Confusion matrix resulting from the training of a convolutional neural network fed with the vector of entropy density values. True negatives and true positives are above 82 % 82\% 82% .
Electrocardiogram (ECG) classification has become a fundamental tool in modern cardiology. Usually, a complete ECG comprises signals from 12 12 12 sensors or leads. However, manual interpretation of ECGs faces several challenges, including limited access to specialists in rural areas, inter-observer variability, and low sensitivity in short recordings. ECG is the most widely used tool for diagnosing cardiac diseases. Figure 8 (a) shows the ECG of a healthy subject (SR) and of a patient with atrial fibrillation (AFIB). There have been attempts to use machine learning techniques to diagnose such illnesses from ECGs. The most commonly used approach in this regard is to train the neural network directly on labelled ECG data and use the trained model for diagnosis. We followed a different approach.
From the ECG, the recurrence matrix is computed (Figure 8 (b)). An entry r i j r_{ij} r ij in the recurrence matrix is the absolute value of the difference between the signal at time index i i i and time index j j j :
r i j = ∣ ( e c g ) i − ( e c g ) j ∣ r_{ij}=|(ecg)_i-(ecg)_j| r ij = ∣ ( ec g ) i − ( ec g ) j ∣
Figure 8 (b) shows the average recurrence matrices corresponding to AFIB and SR subjects.
Visually, the matrices reveal fundamental differences. The graph for the SR group exhibits a pattern of continuous diagonal lines parallel to the main diagonal. According to recurrence matrix theory, this characteristic indicates more deterministic, regular underlying dynamics, consistent with the periodic nature of SR. The presence of these diagonal lines indicates that trajectory segments evolve similarly at different time instants.
In contrast, the recurrence matrix obtained for the AFIB group suggests more complex cardiac dynamics, with a significant stochastic component. The lack of extended temporal recurrences in the trajectory reflects the inherent irregularity and loss of periodicity characteristic of this arrhythmia.
This confirms that diagonal lines constitute the key differentiating element between the two groups, serving as a visual biomarker of cardiovascular system dynamics. The abundance and continuity of these diagonal structures in the SR group not only capture the deterministic nature of SR but also quantify the system’s ability to maintain coherent and predictable temporal patterns.
The differences observed in the matrices suggest that entropic measures calculated from these structures will effectively capture their dynamic differences, thus providing a robust quantitative basis for automatic classification. From the distance matrices constructed for an AFIB subject and an SR subject, we proceed to calculate the entropic descriptors, entropy density and effective complexity measure for each row of the matrix. The values of E ^ \widehat{E} E and h ^ \widehat{h} h for each row for each lead are shown in the entropy-complexity map of Figure 8 (c)
In the healthy patient, values tend to cluster in a region of low h ^ \widehat{h} h and high E ^ \widehat{E} E , as expected from our description of the dynamics of subjects with SR. We observe higher values of h ^ \widehat{h} h and lower values of E ^ \widehat{E} E for the AFIB subject, consistent with more random dynamics and reduced long-range correlations and system memory. The presence of a fraction of AFIB data that exhibits high entropy density h ^ \widehat{h} h values and, simultaneously, effective complexity measure E ^ \widehat{E} E values comparable to those of the SR subject is interesting; it could represent segments of the time series that regularise or show more patterns.
Following this analysis, a convolutional neural network (CNN) was trained using a feature vector as follows. The signals from two leads, lead II and lead V1, were used, as they are known to be significant for diagnosing AFIB. Three distance maps were computed: one for each lead and one for the cross-signal between the leads. From each recurrence map, the entropy density h ^ \widehat{h} h was estimated for each row from the binarised signal (binarisation was performed by the median). The entropy density for each row and recurrence map was treated as a vector, which was used to train the CNN. The number of control and AFIB subjects was roughly equal during training. Details of the CNN architecture are given in Appendix § 22 .
The network was trained using 5-fold cross-validation, with the data split into training and validation sets. The result is shown in Figure 8 (d) as a confusion matrix. The classification results obtained with this neural network provide strong evidence of the discriminative capacity of the extracted features (the vector h ^ \widehat{h} h ). In particular, this type of descriptor has proven highly representative of the underlying dynamics in ECG recordings, capturing complex aspects of nonlinear physiological behaviour that are traditionally inaccessible through conventional linear metrics. The performance achieved for h ^ \widehat{h} h —with an overall accuracy of 83.2% using only two leads of the 10-second ECG—is particularly relevant when considering that the most effective methods reported in the literature typically employ all 12 standard leads or long-duration ECGs with beat-to-beat annotations. This level of accuracy, achieved with a significantly reduced amount of information, highlights not only the efficacy of the proposed approach but also its practical viability in environments where access to multichannel data is limited or where more efficient signal acquisition and processing is required.
Further applications
We applied the same magnitudes to other systems in previous and ongoing work; those results are not reproduced here for lack of space but are summarised for completeness. In written language, h ^ \widehat h h and E ^ \widehat E E were estimated for the books of different writers, each text treated as a symbolic sequence of characters, without any grammatical or syntactic analysis. On the complexity-entropy map the authors occupy distinct regions, so the measures capture their different styles. Also, dendrograms built from the Lempel-Ziv distance matrix segmented the authors and each author’s work by genre. Surrogates obtained by randomising each text at the sentence, word and character level allow the contribution of each level of organisation to be separated: the difference in h ^ \widehat h h between consecutive randomisations measures the information invested in organising characters into words, words into sentences, and sentences into the text, and the corresponding difference in E ^ \widehat E E measures the effective measure complexity gained at each of those levels, which decreases as one moves up the hierarchy [123 ] .
In gene expression data, the magnitudes were estimated from whole-genome expression levels ordered by pathway, for thirteen tumour types taken from the TCGA repository. The complexity-entropy map separates tumour from normal samples in nine of the thirteen types, with success rates above 98 % 98\% 98% in several of them, and d ^ \widehat d d discriminates in addition between tumour types, as shown for two kidney tumours. Neither gene preselection nor a model of the disease is required, and the ordering by pathway, rather than the identification of individual up- or down-regulated genes, is what makes the trend in the map emerge [124 ] .
For trajectories, a two-dimensional curve is discretised with the Freeman chain code, which yields a sequence over an alphabet of eight symbols and requires no embedding or threshold. The magnitudes estimated from that sequence separate regular from chaotic orbits in the Hénon-Heiles system, and, applied to centre-of-pressure trajectories from a public human balance dataset, provide the features with which a neural network classifies subjects by fall history under different postural conditions [125 ] . In all cases the procedure is the one followed above: discretise the signal, factorise it, and estimate h ^ \widehat h h , E ^ \widehat E E and d ^ \widehat d d from the factorisation, without tuning parameters or assuming a model for the source.
Conclusions
In this article, we have revisited the fundamental concepts of entropy and related magnitudes for the analysis of sequential data, providing a unified treatment of their mathematical foundations within information theory and ergodic theory. We have established the relationships between block entropy, entropy density, entropy gain, effective measure complexity, and informational distance, clarifying their interpretations and convergence properties. The connection between Shannon’s probabilistic entropy and Kolmogorov’s algorithmic complexity has been emphasised, with Ziv’s theorem providing the crucial link that enables practical estimation via Lempel-Ziv factorisation.
The Lempel-Ziv factorisation has been examined in detail, demonstrating its utility for estimating entropic magnitudes from finite sequences. We have presented estimation procedures for entropy density, effective measure complexity via coverage-adjusted block entropies, informational distance, and the transfer entropy rate, including error estimates and convergence considerations. The accompanying open-source software library, lzcomplexity [103 ] , implements parallel algorithms capable of processing sequences up to (10 9 10^9 1 0 9 ) symbols, making these analyses accessible for practical applications.
The three case studies illustrate the framework’s broad applicability. In brain connectivity analysis, entropic measures revealed task-specific activation patterns and hierarchical functional organisation, providing a model-free approach to characterise cognitive states. The study of coupled nonlinear oscillators demonstrated that entropy density and effective measure complexity capture transitions between dynamical regimes and identify collective behaviour through patterns of informational distance. Finally, electrocardiogram analysis showed that entropy-based features extracted from recurrence matrices can achieve clinically relevant classification performance for atrial fibrillation with only two leads, highlighting the approach’s practical diagnostic potential.
Taken together, these results demonstrate that the entropic magnitudes discussed—entropy density, effective measure complexity, and informational distance—provide a robust, theoretically grounded framework for characterising complex dynamics across diverse domains. Their estimation via Lempel-Ziv factorisation offers a practical, parameter-free methodology that captures both randomness and memory in sequential data, with promising applications in physics, biology, neuroscience, and medicine.
Acknowledgments
CITMA is acknowledged for financial support under the project CARDENT, grant PN223LH010-053. The MPI-PKS partially funded this work through its visitor program. EER thanks H. Kantz at MPI-PKS for the in-depth discussion and the excellent working environment.
Data availability and authors statement
The data supporting the findings in the brain and heart case studies come from third parties and are publicly available from the Human Connectome Project (https://www.humanconnectome.org/) and the PhysioNet Database (https://physionet.org/). The lzcomplexity software used to estimate the entropic magnitudes is openly available at https://github.com/pleros-ai/lzcomplexity and archived on Zenodo, https://doi.org/10.5281/zenodo.23531093 [103 ] .
The authors have no conflicts to disclose.
Block entropy H ℓ ( u ) H_\ell(u) H ℓ ( u ) is a non-decreasing function of ℓ \ell ℓ .
P ( w 0 ℓ ) = P ( w 0 ℓ − 1 ) P ( w ℓ ∣ w 0 ℓ − 1 ) ≤ P ( w 0 ℓ − 1 ) , P(w_0^{\ell})=P(w_0^{\ell-1})P(w_{\ell}|w_0^{\ell-1})\leq P(w_0^{\ell-1}), P ( w 0 ℓ ) = P ( w 0 ℓ − 1 ) P ( w ℓ ∣ w 0 ℓ − 1 ) ≤ P ( w 0 ℓ − 1 ) ,
then
H ℓ + 1 ( u ) = − ∑ w ( ℓ + 1 ) ∈ u P ( w 0 ℓ ) log P ( w 0 ℓ ) = − ∑ w ( ℓ + 1 ) ∈ u P ( w 0 ℓ ) log P ( w 0 ℓ − 1 ) − ∑ w ( ℓ + 1 ) ∈ u P ( w 0 ℓ ) log P ( w ℓ ∣ w 0 ℓ − 1 ) . \begin{array}{ll}
H_{\ell+1}(u)&=-\sum\limits_{w^{(\ell+1)}\in u} P(w_0^\ell) \log P(w_0^\ell)\\
&=-\sum\limits_{w^{(\ell+1)}\in u} P(w_0^\ell)\log P(w_0^{\ell-1}) -\sum\limits_{w^{(\ell+1)}\in u} P(w_0^\ell) \log P(w_{\ell} | w_0^{\ell-1}).
\end{array} H ℓ + 1 ( u ) = − w ( ℓ + 1 ) ∈ u ∑ P ( w 0 ℓ ) log P ( w 0 ℓ ) = − w ( ℓ + 1 ) ∈ u ∑ P ( w 0 ℓ ) log P ( w 0 ℓ − 1 ) − w ( ℓ + 1 ) ∈ u ∑ P ( w 0 ℓ ) log P ( w ℓ ∣ w 0 ℓ − 1 ) .
For the first term on the right-hand side, taking w ( ℓ + 1 ) ∈ u w^{(\ell+1)}\in u w ( ℓ + 1 ) ∈ u ,
− ∑ w 0 … w ℓ P ( w 0 … w ℓ ) log P ( w 0 … w ℓ − 1 ) = − ∑ w 0 … w ℓ − 1 [ log P ( w 0 … w ℓ − 1 ) ∑ w ℓ P ( w 0 … w ℓ ) ] = − ∑ w 0 … w ℓ − 1 P ( w 0 … w ℓ − 1 ) log P ( w 0 … w ℓ − 1 ) = H ℓ ( u ) . \begin{array}{l}
-\sum\limits_{w_0\ldots w_{\ell}} P(w_0 \ldots w_{\ell}) \log P(w_0\ldots w_{\ell-1})=- \sum\limits_{w_0\ldots w_{\ell-1}}\left[ \log P(w_0\ldots w_{\ell-1}) \sum\limits_{w_{\ell}}P(w_0 \ldots w_{\ell}) \right]\\
= -\sum\limits_{w_0\ldots w_{\ell-1}} P(w_0\dots w_{\ell-1}) \log P(w_0\ldots w_{\ell-1})
= H_\ell(u).
\end{array} − w 0 … w ℓ ∑ P ( w 0 … w ℓ ) log P ( w 0 … w ℓ − 1 ) = − w 0 … w ℓ − 1 ∑ [ log P ( w 0 … w ℓ − 1 ) w ℓ ∑ P ( w 0 … w ℓ ) ] = − w 0 … w ℓ − 1 ∑ P ( w 0 … w ℓ − 1 ) log P ( w 0 … w ℓ − 1 ) = H ℓ ( u ) .
Where use has been made of ∑ w ℓ P ( w 0 … w ℓ ) = P ( w 0 … w ℓ − 1 ) \sum\limits_{w_{\ell}}P(w_0 \ldots w_{\ell})= P(w_0 \ldots w_{\ell-1}) w ℓ ∑ P ( w 0 … w ℓ ) = P ( w 0 … w ℓ − 1 ) .
Now,
H ℓ + 1 ( u ) = H ℓ ( u ) − ∑ w ( ℓ + 1 ) ∈ u P ( w 0 … w ℓ ) log P ( w ℓ ∣ w 0 , . . . , w ℓ − 1 ) . \begin{equation}
H_{\ell+1}(u)=H_\ell(u)-\sum\limits_{w^{(\ell+1)}\in u} P(w_0\ldots w_{\ell}) \log P(w_{\ell} | w_0,...,w_{\ell-1}). \tag*{(82)}
\end{equation} H ℓ + 1 ( u ) = H ℓ ( u ) − w ( ℓ + 1 ) ∈ u ∑ P ( w 0 … w ℓ ) log P ( w ℓ ∣ w 0 , ... , w ℓ − 1 ) . (82)
Taking into account that log P ( ⋅ ) ≤ 0 \log P(\cdot)\leq 0 log P ( ⋅ ) ≤ 0 , each term on the last sum is positive and the non-decreasing behaviour of H ℓ ( u ) H_\ell(u) H ℓ ( u ) follows.
Entropy gain converges faster than h ℓ h_\ell h ℓ .
It has already been shown that Δ H ℓ ( u ) \Delta H_\ell(u) Δ H ℓ ( u ) is a non-increasing function of ℓ \ell ℓ , hence Δ H ℓ ( u ) ≥ h \Delta H_\ell(u)\geq h Δ H ℓ ( u ) ≥ h for all ℓ \ell ℓ . From ((9) ) will have
h ℓ ( u ) = 1 ℓ ∑ i = 0 ℓ − 1 H ( u i ∣ u ( i ) ) . \begin{equation}
h_\ell(u)=\frac{1}{\ell}\sum\limits_{i=0}^{\ell-1}H(u_i|u^{(i)}). \tag*{(83)}
\end{equation} h ℓ ( u ) = ℓ 1 i = 0 ∑ ℓ − 1 H ( u i ∣ u ( i ) ) . (83)
Also
H ( u i ∣ u i − 1 u i − 2 ⋯ u 1 ) ≥ H ( u ℓ − 1 ∣ u ℓ − 2 u ℓ − 3 ⋯ u 1 ) H(u_i|u_{i-1}u_{i-2}\cdots u_1)\geq H(u_{\ell-1}|u_{\ell-2}u_{\ell-3}\cdots u_1) H ( u i ∣ u i − 1 u i − 2 ⋯ u 1 ) ≥ H ( u ℓ − 1 ∣ u ℓ − 2 u ℓ − 3 ⋯ u 1 )
and
h ℓ ≥ 1 ℓ ∑ i = 0 ℓ − 1 H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) = 1 ℓ ℓ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) = Δ H ℓ . \begin{array}{rl}
h_\ell&\geq \frac{1}{\ell}\sum\limits_{i=0}^{\ell-1}H(u_{\ell-1}|u^{(\ell-1)})\\\\
&=\frac{1}{\ell}\ell H(u_{\ell-1}|u^{(\ell-1)})\\\\
&=\Delta H_\ell.
\end{array} h ℓ ≥ ℓ 1 i = 0 ∑ ℓ − 1 H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) = ℓ 1 ℓ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) = Δ H ℓ .
from where
h ℓ ≥ Δ H ℓ ≥ h . \begin{equation}
h_\ell\geq \Delta H_\ell\geq h. \tag*{(84)}
\end{equation} h ℓ ≥ Δ H ℓ ≥ h . (84)
Using equation (3)
H ℓ + 1 ℓ + 1 = H ℓ ℓ − 1 ℓ + 1 ( H ℓ ℓ − H ( u ℓ ∣ u ( ℓ ) ) ) . \begin{equation}
\frac{H_{\ell+1}}{\ell+1}=\frac{H_\ell}{\ell}-\frac{1}{\ell+1}\left(\frac{H_\ell}{\ell}-H(u_\ell|u^{(\ell)})\right). \tag*{(85)}
\end{equation} ℓ + 1 H ℓ + 1 = ℓ H ℓ − ℓ + 1 1 ( ℓ H ℓ − H ( u ℓ ∣ u ( ℓ ) ) ) . (85)
If we prove that the term in parentheses on the right-hand side is non-negative, then h ℓ ( u ) h_\ell(u) h ℓ ( u ) is a non-increasing function of ℓ \ell ℓ . Considering
H ℓ ( u ) ℓ ≥ H ( u ℓ ∣ u ( ℓ ) ) . \frac{H_\ell(u)}{\ell}\geq H(u_\ell|u^{(\ell)}). ℓ H ℓ ( u ) ≥ H ( u ℓ ∣ u ( ℓ ) ) .
and taking into account, by the chain rule, that
H ℓ ( u ) = H ( u 0 ) + H ( u 1 ∣ u 0 ) + H ( u 2 ∣ u 0 u 1 ) + ⋯ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) H_\ell(u)=H(u_0)+H(u_1|u_0)+H(u_2|u_0u_1)+\cdots H(u_{\ell-1}|u^{(\ell-1)}) H ℓ ( u ) = H ( u 0 ) + H ( u 1 ∣ u 0 ) + H ( u 2 ∣ u 0 u 1 ) + ⋯ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) )
it follows that
H ℓ ( u ) ℓ = 1 ℓ ∑ i = 0 ℓ − 1 H ( u i ∣ u ( i ) ) ≥ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) , \frac{H_\ell(u)}{\ell}=\frac{1}{\ell}\sum\limits_{i=0}^{\ell-1}H(u_i|u^{(i)})\geq H(u_{\ell-1}|u^{(\ell-1)}), ℓ H ℓ ( u ) = ℓ 1 i = 0 ∑ ℓ − 1 H ( u i ∣ u ( i ) ) ≥ H ( u ℓ − 1 ∣ u ( ℓ − 1 ) ) ,
where the last inequality is a consequence of the arithmetic mean always being greater than or equal to the smallest summand. Δ H ℓ \Delta H_\ell Δ H ℓ being non-increasing, h ℓ ≥ Δ H ℓ ≥ Δ H ℓ + 1 h_\ell\geq \Delta H_\ell \geq \Delta H_{\ell+1} h ℓ ≥ Δ H ℓ ≥ Δ H ℓ + 1 .
lim inf ℓ → ∞ ζ ℓ ( u ) \liminf\limits_{\ell\rightarrow \infty} \zeta_\ell(u) ℓ → ∞ lim inf ζ ℓ ( u ) and lim sup ℓ → ∞ ζ ℓ ( u ) \limsup\limits_{\ell\rightarrow \infty} \zeta_\ell(u) ℓ → ∞ lim sup ζ ℓ ( u ) exist and are finite
Let inf ℓ > ℓ i ζ ℓ ( u ) \inf\limits_{\ell>\ell_i} \zeta_\ell(u) ℓ > ℓ i inf ζ ℓ ( u ) be the infimum of ζ ℓ ( u ) \zeta_\ell(u) ζ ℓ ( u ) for ℓ > ℓ i \ell>\ell_i ℓ > ℓ i ,
ζ ℓ ( u ) ≥ inf ℓ ′ > ℓ i ζ ℓ ′ ( u ) . \zeta_\ell(u)\ge \inf\limits_{\ell'>\ell_i} \zeta_{\ell'}(u). ζ ℓ ( u ) ≥ ℓ ′ > ℓ i inf ζ ℓ ′ ( u ) .
It is clear that if ℓ q > ℓ i \ell_q>\ell_i ℓ q > ℓ i , then
inf ℓ > ℓ q ζ ℓ ( u ) ≥ inf ℓ > ℓ i ζ ℓ ( u ) . \inf\limits_{\ell>\ell_q} \zeta_{\ell}(u)\ge \inf\limits_{\ell>\ell_i} \zeta_{\ell}(u). ℓ > ℓ q inf ζ ℓ ( u ) ≥ ℓ > ℓ i inf ζ ℓ ( u ) .
Let ζ n inf = inf ℓ > ℓ n ζ ℓ ( u ) \zeta^{\inf}_n=\inf\limits_{\ell>\ell_n} \zeta_{\ell}(u) ζ n i n f = ℓ > ℓ n inf ζ ℓ ( u ) and assume that q > i q>i q > i implies ℓ q > ℓ i \ell_q>\ell_i ℓ q > ℓ i , then ζ n inf \zeta^{\inf}_n ζ n i n f is a non-decreasing sequence of n n n , but inequality ((16) ) implies that ζ n inf ≤ 1 \zeta^{\inf}_n\leq 1 ζ n i n f ≤ 1 . Therefore the lim n → ∞ ζ n inf \lim\limits_{n\rightarrow\infty}\zeta^{\inf}_n n → ∞ lim ζ n i n f exists and furthermore
lim inf ℓ → ∞ ζ ℓ ( u ) = lim n → ∞ ζ n inf ≤ 1. \liminf\limits_{\ell\rightarrow\infty} \zeta_{\ell}(u)=\lim\limits_{n\rightarrow \infty}\zeta^{\inf}_n \leq 1. ℓ → ∞ lim inf ζ ℓ ( u ) = n → ∞ lim ζ n i n f ≤ 1.
The same logic implies that lim sup ℓ → ∞ ζ ℓ ( u ) \limsup\limits_{\ell\rightarrow\infty} \zeta_{\ell}(u) ℓ → ∞ lim sup ζ ℓ ( u ) also exists. For lim ℓ → ∞ ζ ℓ ( u ) \lim\limits_{\ell\rightarrow\infty} \zeta_\ell(u) ℓ → ∞ lim ζ ℓ ( u ) to exist, it must hold that
ζ ∞ ( u ) = lim ℓ → ∞ ζ ℓ ( u ) = lim inf ℓ → ∞ ζ ℓ ( u ) = lim sup ℓ → ∞ ζ ℓ ( u ) . \begin{equation}
\zeta_\infty(u)=\lim\limits_{\ell\rightarrow\infty} \zeta_\ell(u)=\liminf\limits_{\ell\rightarrow\infty} \zeta_{\ell}(u)=\limsup\limits_{\ell\rightarrow\infty} \zeta_{\ell}(u). \tag*{(86)}
\end{equation} ζ ∞ ( u ) = ℓ → ∞ lim ζ ℓ ( u ) = ℓ → ∞ lim inf ζ ℓ ( u ) = ℓ → ∞ lim sup ζ ℓ ( u ) . (86)
Both limits indeed coincide. Every word of length ℓ + m \ell+m ℓ + m occurring in u u u is the concatenation of a word of length ℓ \ell ℓ and a word of length m m m , both occurring in u u u , so that # ℓ + m ≤ # ℓ # m \#_{\ell+m}\leq \#_\ell\,\#_m # ℓ + m ≤ # ℓ # m . The sequence a ℓ ≡ log # ℓ = ℓ ζ ℓ ( u ) a_\ell\equiv\log\#_\ell=\ell\,\zeta_\ell(u) a ℓ ≡ log # ℓ = ℓ ζ ℓ ( u ) is therefore subadditive, a ℓ + m ≤ a ℓ + a m a_{\ell+m}\leq a_\ell+a_m a ℓ + m ≤ a ℓ + a m , and by Fekete’s lemma [126 ] the limit of a ℓ / ℓ a_\ell/\ell a ℓ / ℓ exists and equals inf ℓ a ℓ / ℓ \inf_\ell a_\ell/\ell inf ℓ a ℓ / ℓ :
lim ℓ → ∞ ζ ℓ ( u ) = inf ℓ ≥ 1 ζ ℓ ( u ) , \lim\limits_{\ell\rightarrow\infty}\zeta_\ell(u)=\inf\limits_{\ell\geq 1}\zeta_\ell(u), ℓ → ∞ lim ζ ℓ ( u ) = ℓ ≥ 1 inf ζ ℓ ( u ) ,
which, by inequality ((18) ), lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Equation (86) follows. Note that inequalities ((14) ) and ((15) ) only imply ∣ ζ ℓ + 1 − ζ ℓ ∣ ≤ 1 / ( ℓ + 1 ) → 0 |\zeta_{\ell+1}-\zeta_\ell|\leq 1/(\ell+1)\rightarrow 0 ∣ ζ ℓ + 1 − ζ ℓ ∣ ≤ 1/ ( ℓ + 1 ) → 0 , which by itself would not guarantee convergence.
Ziv theorem 5
To prove ((22) ), consider the set of all subsequences u 1 n u^n_1 u 1 n of length n n n emitted by the ergodic source. By the asymptotic equipartition property, we have
lim n → ∞ P [ ∣ − 1 n log P ( u 1 n ) − h ∣ > ϵ ] = 0 , \lim\limits_{n\rightarrow \infty}P\left[\left|-\frac{1}{n}\log P(u_1^n)-h\right|>\epsilon\right]=0, n → ∞ lim P [ − n 1 log P ( u 1 n ) − h > ϵ ] = 0 ,
For any ϵ > 0 \epsilon>0 ϵ > 0 , arbitrarily small. Therefore, there exists an integer ℓ \ell ℓ , such that for all n ≥ ℓ n\geq \ell n ≥ ℓ
P [ ∣ − 1 n log P ( u 1 n ) − h ∣ > ϵ ] ≤ ϵ . P\left[\left|-\frac{1}{n}\log P(u_1^n)-h\right|>\epsilon\right]\leq \epsilon. P [ − n 1 log P ( u 1 n ) − h > ϵ ] ≤ ϵ .
For n = ℓ n=\ell n = ℓ there exists a set Ω \Omega Ω of typical sequences that includes at most α ℓ ( h + ϵ ) \alpha^{\ell(h+\epsilon)} α ℓ ( h + ϵ ) elements and at least ( 1 − ϵ ) α ℓ ( h − ϵ ) (1-\epsilon)\alpha^{\ell(h-\epsilon)} ( 1 − ϵ ) α ℓ ( h − ϵ ) elements, almost all equiprobable, such that
P ( u 1 ℓ ∈ Ω ) ≥ 1 − ϵ . \begin{equation}
P\left(u_1^\ell\in\Omega\right)\geq 1-\epsilon. \tag*{(87)}
\end{equation} P ( u 1 ℓ ∈ Ω ) ≥ 1 − ϵ . (87)
Consider the following partition of u u u
u = u 1 k − 1 u k ℓ + k − 1 u ℓ + k 2 ℓ + k − 1 … u j ℓ + k ( j + 1 ) ℓ + k − 1 … 1 ≤ k ≤ ℓ , j = 0 , 1 , … . u=u_1^{k-1}u_{k}^{\ell+k-1}u_{\ell+k}^{2\ell+k-1}\ldots u_{j\ell+k}^{(j+1)\ell+k-1}\ldots \;\;\;\;1\leq k\leq \ell,\;\;j=0,1,\ldots. u = u 1 k − 1 u k ℓ + k − 1 u ℓ + k 2 ℓ + k − 1 … u j ℓ + k ( j + 1 ) ℓ + k − 1 … 1 ≤ k ≤ ℓ , j = 0 , 1 , … .
Let 1 k ( 0 ) = 0 \mathds{1}_k(0)=0 1 k ( 0 ) = 0 ,
1 k ( j ) = { 0 , u j ℓ + k ( j + 1 ) ℓ + k − 1 ∈ Ω 1 , otherwise \mathds{1}_k(j)=\left\{\begin{array}{ll}0, & u_{j\ell+k}^{(j+1)\ell+k-1}\in \Omega\\\\ 1, & \text{otherwise}\end{array}\right. 1 k ( j ) = ⎩ ⎨ ⎧ 0 , 1 , u j ℓ + k ( j + 1 ) ℓ + k − 1 ∈ Ω otherwise
Define
ρ k ( u ) = lim L → ∞ 1 L ∑ j = 0 L − 1 1 k ( j ) . \rho_k(u)=\lim\limits_{L\rightarrow \infty}\frac{1}{L}\sum\limits_{j=0}^{L-1}\mathds{1}_k(j). ρ k ( u ) = L → ∞ lim L 1 j = 0 ∑ L − 1 1 k ( j ) .
which exists due to the stationary nature of the sequence 1 k ( 1 ) , … 1 k ( i ) , … \mathds{1}_k(1),\ldots \mathds{1}_k(i),\ldots 1 k ( 1 ) , … 1 k ( i ) , … . Noting, from ((87) ), that P ( u 1 ℓ ∉ Ω ) ≤ ϵ P\left(u_1^\ell\notin\Omega\right)\leq \epsilon P ( u 1 ℓ ∈ / Ω ) ≤ ϵ we will have with probability 1 1 1 , then,
1 ℓ ∑ k = 1 ℓ ρ k ( u ) = 1 − P [ Ω ] ≤ ϵ , \frac{1}{\ell}\sum_{k=1}^\ell\rho_k(u)=1-P[\Omega]\leq \epsilon, ℓ 1 k = 1 ∑ ℓ ρ k ( u ) = 1 − P [ Ω ] ≤ ϵ ,
the equality due to the source’s ergodicity. Therefore, there exists a k 0 k_0 k 0 (1 ≤ k 0 ≤ ℓ 1\leq k_0\leq \ell 1 ≤ k 0 ≤ ℓ ) for which
ρ k 0 ( u ) ≤ ϵ . \begin{equation}
\rho_{k_0}(u)\leq \epsilon. \tag*{(88)}
\end{equation} ρ k 0 ( u ) ≤ ϵ . (88)
Assume, without loss of generality, that k 0 = 1 k_0=1 k 0 = 1 and consider
u = u 1 ℓ u ℓ + 1 2 ℓ u 2 ℓ + 1 3 ℓ … u j ℓ + 1 ( j + 1 ) ℓ … j = 0 , 1 , … u=u_1^\ell u_{\ell+1}^{2\ell}u_{2\ell+1}^{3\ell}\ldots u_{j\ell+1}^{(j+1)\ell}\ldots \;\;\;\;j=0,1,\ldots u = u 1 ℓ u ℓ + 1 2 ℓ u 2 ℓ + 1 3 ℓ … u j ℓ + 1 ( j + 1 ) ℓ … j = 0 , 1 , …
Construct the sequence w w w where each block u j ℓ + 1 ( j + 1 ) ℓ u_{j\ell+1}^{(j+1)\ell} u j ℓ + 1 ( j + 1 ) ℓ of u u u that does not belong to Ω \Omega Ω is replaced by a block that does belong to Ω \Omega Ω . From ((88) ), it is clear that the Hamming distance between u u u and w w w , d H ( u , w ) ≤ ϵ d_H(u,w)\leq \epsilon d H ( u , w ) ≤ ϵ .
By construction, the number of distinct ℓ \ell ℓ -blocks in w = w 1 ℓ w ℓ + 1 2 ℓ … w=w_1^\ell w_{\ell+1}^{2\ell}\ldots w = w 1 ℓ w ℓ + 1 2 ℓ … cannot be greater than α ℓ ( h + ϵ ) \alpha^{\ell(h+\epsilon)} α ℓ ( h + ϵ ) , therefore
α ℓ q ζ ℓ q ( w ) ≤ [ α ℓ ( h + ϵ ) ] q − 1 α ℓ = α q ℓ ( h + ϵ ) − ℓ ( h + ϵ ) + ℓ ≤ α q ℓ [ h + ϵ + 1 / q ] , \alpha^{\ell q \zeta_{\ell q}(w)}\leq \left[ \alpha^{\ell(h+\epsilon)}\right]^{q-1}\alpha^\ell=\alpha^{q\ell(h+\epsilon)-\ell(h+\epsilon)+\ell}\leq \alpha^{q \ell\left[ h+\epsilon + 1/q \right ] }, α ℓ q ζ ℓ q ( w ) ≤ [ α ℓ ( h + ϵ ) ] q − 1 α ℓ = α q ℓ ( h + ϵ ) − ℓ ( h + ϵ ) + ℓ ≤ α q ℓ [ h + ϵ + 1/ q ] ,
or
ζ ℓ q ( w ) ≤ [ h + ϵ + 1 / q ] . \zeta_{\ell q}(w)\leq \left[h+\epsilon+1/q\right]. ζ ℓ q ( w ) ≤ [ h + ϵ + 1/ q ] .
Hence
ζ ∞ ( w ) = lim q → ∞ ζ q ℓ ( w ) ≤ h + ϵ . \begin{equation}
\zeta_\infty(w)=\lim\limits_{q\rightarrow \infty}\zeta_{q\ell}(w)\leq h+\epsilon. \tag*{(89)}
\end{equation} ζ ∞ ( w ) = q → ∞ lim ζ q ℓ ( w ) ≤ h + ϵ . (89)
Now choose the w j ℓ + 1 ( j + 1 ) ℓ w_{j\ell+1}^{(j+1)\ell} w j ℓ + 1 ( j + 1 ) ℓ that replace the corresponding blocks in u u u , such that
ζ ∞ ( u ) = ζ ∞ ( w ) ≤ h + ϵ , \zeta_\infty(u)=\zeta_\infty(w)\leq h+\epsilon, ζ ∞ ( u ) = ζ ∞ ( w ) ≤ h + ϵ ,
and therefore, for ϵ → 0 \epsilon\rightarrow 0 ϵ → 0
ζ ∞ ≤ h . \begin{equation}
\zeta_\infty\leq h. \tag*{(90)}
\end{equation} ζ ∞ ≤ h . (90)
For the reverse inequality, we use the other half of the asymptotic equipartition property ∣ Ω ∣ ≥ ( 1 − ϵ ) α ℓ ( h − ϵ ) |\Omega|\geq (1-\epsilon)\alpha^{\ell(h-\epsilon)} ∣Ω∣ ≥ ( 1 − ϵ ) α ℓ ( h − ϵ ) . Since our source is ergodic, every block of Ω \Omega Ω occurs in u u u with probability 1 1 1 , so that,
α ℓ ζ ℓ ( u ) ≥ ( 1 − ϵ ) α ℓ ( h − ϵ ) . \alpha^{\ell\zeta_\ell(u)}\geq (1-\epsilon) \alpha^{\ell(h-\epsilon)}. α ℓ ζ ℓ ( u ) ≥ ( 1 − ϵ ) α ℓ ( h − ϵ ) .
Hence
ζ ℓ ( u ) ≥ h − ϵ + log ( 1 − ϵ ) ℓ , \zeta_\ell(u)\geq h-\epsilon+\frac{\log (1-\epsilon)}{\ell}, ζ ℓ ( u ) ≥ h − ϵ + ℓ log ( 1 − ϵ ) ,
taking the limit ℓ → ∞ \ell\rightarrow \infty ℓ → ∞ and then ϵ → 0 \epsilon\rightarrow 0 ϵ → 0 gives
ζ ∞ ≥ h \begin{equation}
\zeta_\infty\geq h \tag*{(91)}
\end{equation} ζ ∞ ≥ h (91)
From ((90) ) and ((91) ) it follows
ζ ∞ = h , \begin{equation}
\zeta_\infty=h, \tag*{(92)}
\end{equation} ζ ∞ = h , (92)
in probability, which is what we wanted to prove.
The exhaustive history of a sequence is the smallest of all history factorisations [99 ]
Consider a sequence w w w out of an alphabet A \mathcal{A} A and a non-exhaustive history of w = f 1 f 2 … f n F ′ w=f_1f_2\ldots f_{n_F'} w = f 1 f 2 … f n F ′ . Then, for each factor f i f_i f i , these two conditions are fulfilled
f 1 ∈ A f i π ∈ V ( f 1 f 2 … f i π 2 ) . \begin{equation}
\begin{array}{c}
f_1\in \mathcal{A}\\\\
f_i\pi\in \mathcal{V}(f_1f_2\ldots f_i\pi^2).
\end{array} \tag*{(93)}
\end{equation} f 1 ∈ A f i π ∈ V ( f 1 f 2 … f i π 2 ) . (93)
Consider the LZ-factorisation (exhaustive history) w = F 1 F 2 … F n F w=F_1F_2\ldots F_{n_F} w = F 1 F 2 … F n F . For each factor F i F_i F i , these three conditions are true,
F 1 ∈ A F i π ∈ V ( F 1 F 2 … F i π 2 ) F i ∉ V ( F 1 F 2 … F i π ) . \begin{equation}
\begin{array}{c}
F_1\in \mathcal{A}\\
F_i\pi\in \mathcal{V}(F_1F_2\ldots F_i\pi^2)\\\\
F_i\notin \mathcal{V}(F_1F_2\ldots F_i\pi).
\end{array} \tag*{(94)}
\end{equation} F 1 ∈ A F i π ∈ V ( F 1 F 2 … F i π 2 ) F i ∈ / V ( F 1 F 2 … F i π ) . (94)
For all 1 ≤ i ≤ min ( n F , n F ′ ) 1\leq i \leq \min(n_F, n_F') 1 ≤ i ≤ min ( n F , n F ′ ) ,
∣ f 1 f 2 … f i ∣ ≤ ∣ F 1 F 2 … F i ∣ . \begin{equation}
|f_1f_2\ldots f_i|\leq |F_1F_2\ldots F_i|. \tag*{(95)}
\end{equation} ∣ f 1 f 2 … f i ∣ ≤ ∣ F 1 F 2 … F i ∣. (95)
Indeed, if this is not the case, consider i 0 i_0 i 0 the smallest index where the inequality breaks ∣ f 1 f 2 … f i 0 ∣ > ∣ F 1 F 2 … F i 0 ∣ |f_1f_2\ldots f_{i_0}|>|F_1F_2\ldots F_{i_0}| ∣ f 1 f 2 … f i 0 ∣ > ∣ F 1 F 2 … F i 0 ∣ . It follows that F i 0 F_{i_0} F i 0 can not be a suffix of f i 0 f_{i_0} f i 0 , because then ∣ f 1 f 2 … f i 0 ∣ = ∣ F 1 F 2 … F i 0 ∣ |f_1f_2\ldots f_{i_0}|=|F_1F_2\ldots F_{i_0}| ∣ f 1 f 2 … f i 0 ∣ = ∣ F 1 F 2 … F i 0 ∣ which has been excluded. A non-null suffix of F i 0 F_{i_0} F i 0 must belong to f i 0 f_{i_0} f i 0 , otherwise i 0 i_0 i 0 will not be the smallest i 0 i_0 i 0 where the inequality breaks, then ∣ f i 0 ∣ ≥ 2 |f_{i_0}|\geq 2 ∣ f i 0 ∣ ≥ 2 .
Because of condition ((93) ) and that F i 0 F_{i_0} F i 0 is not a suffix of f i 0 f_{i_0} f i 0 , the following is true,
F i 0 ∈ V ( f 1 f 2 … f i 0 π 2 ) . F_{i_0}\in \mathcal{V}(f_1f_2\ldots f_{i_0}\pi^2). F i 0 ∈ V ( f 1 f 2 … f i 0 π 2 ) .
Let us consider two cases, first that f 1 f 2 … f i 0 π = F 1 F 2 … F i 0 f_1f_2\ldots f_{i_0}\pi=F_1F_2\ldots F_{i_0} f 1 f 2 … f i 0 π = F 1 F 2 … F i 0 , then
F i 0 ∈ V ( F 1 F 2 … F i 0 π ) , F_{i_0}\in \mathcal{V}(F_1F_2\ldots F_{i_0}\pi), F i 0 ∈ V ( F 1 F 2 … F i 0 π ) ,
which contradicts the third condition in ((94) ) of the exhaustive nature of F i 0 F_{i_0} F i 0 .
The second case takes ∣ f 1 f 2 … f i 0 π ∣ > ∣ F 1 F 2 … F i 0 ∣ |f_1f_2\ldots f_{i_0}\pi|>|F_1F_2\ldots F_{i_0}| ∣ f 1 f 2 … f i 0 π ∣ > ∣ F 1 F 2 … F i 0 ∣ which implies f i 0 ∈ V ( f 1 f 2 … f i 0 π ) f_{i_0}\in \mathcal{V}(f_1f_2\ldots f_{i_0}\pi) f i 0 ∈ V ( f 1 f 2 … f i 0 π ) and then F i 0 F_{i_0} F i 0 is not the longest prefix of F i 0 … F n F F_{i_0}\ldots F_{n_F} F i 0 … F n F which has not occurred before, which is a contradiction with the exhaustive nature of F i 0 F_{i_0} F i 0 . This proves condition ((95) ), from where n F ≤ n F ′ n_F \leq n_F' n F ≤ n F ′ follows.
Upper bound for the length of the Lempel-Ziv factorisation [99 ] .
The inequality to be proven is
C L Z ( w ) < N ( 1 − ϵ N ) log N , \begin{equation}
C_{LZ}(w)<\frac{N}{(1-\epsilon_N)\log N}, \tag*{(96)}
\end{equation} C L Z ( w ) < ( 1 − ϵ N ) log N N , (96)
where
ϵ N = 2 1 + log log ( α N ) log N . \begin{equation}
\epsilon_N=2\frac{1+\log\log (\alpha N)}{\log N}. \tag*{(97)}
\end{equation} ϵ N = 2 log N 1 + log log ( α N ) . (97)
Consider a sequence of length N N N and let n F n_F n F be the number of different words in which the sequence can be parsed. By design C L Z ( w ) ≤ n F + 1 C_{LZ}(w)\leq n_F+1 C L Z ( w ) ≤ n F + 1 . Consider the string L L L formed by the concatenation of words lexicographically ordered up to a word length k k k , (e.g. 0 ⋅ 1 ⋅ 00 ⋅ 01 ⋅ 10 ⋅ 11 … ⋅ 11111 0\cdot1\cdot00\cdot01\cdot10\cdot11\ldots \cdot 11111 0 ⋅ 1 ⋅ 00 ⋅ 01 ⋅ 10 ⋅ 11 … ⋅ 11111 , k = 5 k=5 k = 5 ).
The length N k N_k N k of the string L L L is given by
N = N k = ∑ i = 0 k i α i = α α − 1 [ 1 α − 1 + α k ( k − 1 α − 1 ) ] , \begin{equation}
N=N_k=\sum\limits_{i=0}^{k}i \alpha^i=\frac{\alpha}{\alpha-1}\left [\frac{1}{\alpha-1}+\alpha^k\left(k-\frac{1}{\alpha-1}\right)\right], \tag*{(98)}
\end{equation} N = N k = i = 0 ∑ k i α i = α − 1 α [ α − 1 1 + α k ( k − α − 1 1 ) ] , (98)
it follows
Δ k max = N k + 1 − N k = ( 1 + k ) α k + 1 . \begin{equation}
\Delta^{\max}_{k}=N_{k+1}-N_{k}=(1+k)\alpha^{k+1}. \tag*{(99)}
\end{equation} Δ k m a x = N k + 1 − N k = ( 1 + k ) α k + 1 . (99)
The number n F = n F , k n_F=n_{F,k} n F = n F , k for such a string is
n F , k = ∑ i = 1 k α i = α α − 1 ( α k − 1 ) , n_{F,k}=\sum\limits_{i=1}^{k}\alpha^i=\frac{\alpha}{\alpha-1}\left(\alpha^k-1\right), n F , k = i = 1 ∑ k α i = α − 1 α ( α k − 1 ) ,
and
C L Z ( w ) < n F , k + 1 = α α − 1 α k − α α − 1 < α α − 1 α k . \begin{equation}
C_{LZ}(w)< n_{F,k}+1=\frac{\alpha}{\alpha-1}\alpha^k-\frac{\alpha}{\alpha-1}<\frac{\alpha}{\alpha-1}\alpha^k. \tag*{(100)}
\end{equation} C L Z ( w ) < n F , k + 1 = α − 1 α α k − α − 1 α < α − 1 α α k . (100)
On the other hand, from ((98) ),
N k α − 1 α = 1 α − 1 + α k ( k − 1 α − 1 ) > α k ( k − 1 α − 1 ) , N_k\frac{\alpha-1}{\alpha}=\frac{1}{\alpha-1}+\alpha^k\left(k-\frac{1}{\alpha-1}\right)>\alpha^k\left(k-\frac{1}{\alpha-1}\right), N k α α − 1 = α − 1 1 + α k ( k − α − 1 1 ) > α k ( k − α − 1 1 ) ,
from where
α k < α − 1 α N k k − 1 α − 1 . \begin{equation}
\alpha^k<\frac{\alpha-1}{\alpha}\frac{N_k}{k-\frac{1}{\alpha-1}}. \tag*{(101)}
\end{equation} α k < α α − 1 k − α − 1 1 N k . (101)
It follows from expression ((100) ),
C L Z ( w ) < N k k − 1 α − 1 ≤ N k k − 1 . \begin{equation}
C_{LZ}(w)<\frac{N_k}{k-\frac{1}{\alpha-1}}\leq\frac{N_k}{k-1}. \tag*{(102)}
\end{equation} C L Z ( w ) < k − α − 1 1 N k ≤ k − 1 N k . (102)
Consider a positive number N N N , and N k N_k N k be the largest number given by ((98) ) such that N k < N N_k<N N k < N , then it can be written
N = N k + Δ k , N=N_k+\Delta_k, N = N k + Δ k ,
and by equation (99) ,
0 ≤ Δ k < Δ k max . 0\leq \Delta_k<\Delta_{k}^{\max}. 0 ≤ Δ k < Δ k m a x .
The number of new distinct words that appear in the sequence after increasing the length by Δ k \Delta_k Δ k can not be larger than Δ k / ( k + 1 ) \Delta_k/(k+1) Δ k / ( k + 1 ) ; therefore, for any n n n , using inequality ((102) )
C L Z ( w ) < N k k − 1 + Δ k k + 1 < N k + Δ k k − 1 = N k − 1 . \begin{equation}
C_{LZ}(w)<\frac{N_k}{k-1}+\frac{\Delta_k}{k+1}<\frac{N_k+\Delta_k}{k-1}=\frac{N}{k-1}. \tag*{(103)}
\end{equation} C L Z ( w ) < k − 1 N k + k + 1 Δ k < k − 1 N k + Δ k = k − 1 N . (103)
The following is also true,
log N ≥ log ∑ i = 1 k i α i > log [ α k ( k − 1 α − 1 ) ] = k + log ( k − 1 α − 1 ) > k , \begin{equation}
\log N\geq\log \sum\limits_{i=1}^{k}i\alpha^i>\log\left[\alpha^k\left(k-\frac{1}{\alpha-1}\right)\right]=k+\log\left(k-\frac{1}{\alpha-1}\right)>k, \tag*{(104)}
\end{equation} log N ≥ log i = 1 ∑ k i α i > log [ α k ( k − α − 1 1 ) ] = k + log ( k − α − 1 1 ) > k , (104)
where expression ((101) ) has been used. On the other hand
log N < log ∑ i = 1 k + 1 i α i < log α k + 1 ∑ i = 1 k + 1 i = k + 1 + log ( k + 1 ) ( k + 2 ) 2 < k + 1 + 2 log ( k + 1 ) . \begin{equation}
\log N<\log\sum\limits_{i=1}^{k+1}i\alpha^i<\log\alpha^{k+1}\sum\limits_{i=1}^{k+1}i=k+1+\log\frac{(k+1)(k+2)}{2}<k+1+2\log (k+1). \tag*{(105)}
\end{equation} log N < log i = 1 ∑ k + 1 i α i < log α k + 1 i = 1 ∑ k + 1 i = k + 1 + log 2 ( k + 1 ) ( k + 2 ) < k + 1 + 2 log ( k + 1 ) . (105)
From this last inequality
k − 1 ≥ log N − 2 − 2 log ( k + 1 ) > log N − 2 [ 1 + log ( 1 + log N ) ] = ( 1 − ϵ N ) log N , \begin{equation}
k-1\geq \log N-2-2\log(k+1)>\log N-2\left[1+\log(1+\log N)\right]=(1-\epsilon_N)\log N, \tag*{(106)}
\end{equation} k − 1 ≥ log N − 2 − 2 log ( k + 1 ) > log N − 2 [ 1 + log ( 1 + log N ) ] = ( 1 − ϵ N ) log N , (106)
where the equation (104) was used.
From the last inequality ((106) ) and ((103) ), follows what we set to prove.
Upper bound for the length of the Lempel-Ziv factorisation and entropy density.
The inequality to be proven is
C L Z ( w ) ≤ N h / log N . \begin{equation}
C_{LZ}(w)\leq N h/\log N. \tag*{(107)}
\end{equation} C L Z ( w ) ≤ N h / log N . (107)
The asymptotic equipartition property of an ergodic sources defines the ‘‘typical’’ set as those with entropy equal to the entropy rate and cardinality α h N \alpha^{h N} α h N . For a large enough sequence N ≫ 1 N\gg 1 N ≫ 1 , almost all strings are ‘‘typical’’. We can then write
N k = ∑ i = 0 k i ( α h ) i = α h α h − 1 [ 1 α h − 1 + α h k ( k − 1 α h − 1 ) ] . \begin{equation}
N_k=\sum_{i=0}^k i (\alpha^h)^i=\frac{\alpha^h}{\alpha^h-1}\left [\frac{1}{\alpha^h-1}+\alpha^{hk}\left(k-\frac{1}{\alpha^h-1}\right)\right]. \tag*{(108)}
\end{equation} N k = i = 0 ∑ k i ( α h ) i = α h − 1 α h [ α h − 1 1 + α hk ( k − α h − 1 1 ) ] . (108)
Performing the same operation with n F , k n_{F,k} n F , k ,
n F , k = ∑ i = 1 k ( α h ) i = α h α h − 1 ( α h k − 1 ) . \begin{equation}
n_{F,k}=\sum_{i=1}^k(\alpha^h)^i=\frac{\alpha^h}{\alpha^h-1}\left(\alpha^{hk}-1\right). \tag*{(109)}
\end{equation} n F , k = i = 1 ∑ k ( α h ) i = α h − 1 α h ( α hk − 1 ) . (109)
now
C L Z ( w ) ≤ n F , k + 1 < α h α h − 1 α h k . \begin{equation}
C_{LZ}(w)\leq n_{F,k}+1 < \frac{\alpha^h}{\alpha^h-1}\alpha^{hk}. \tag*{(110)}
\end{equation} C L Z ( w ) ≤ n F , k + 1 < α h − 1 α h α hk . (110)
The same argument that led to inequality ((104) ) can be applied to show that it remains true.
On the other hand,
log N ≤ log ∑ i = 1 k + 1 i ( α h ) i < log α h ( k + 1 ) ∑ i = 1 k + 1 i < h ( k + 1 ) + 2 log ( k + 1 ) . \log N\leq \log \sum_{i=1}^{k+1} i (\alpha^h)^i<\log\alpha^{h (k+1)}\sum_{i=1}^{k+1} i<h (k +1)+2\log(k+1). log N ≤ log i = 1 ∑ k + 1 i ( α h ) i < log α h ( k + 1 ) i = 1 ∑ k + 1 i < h ( k + 1 ) + 2 log ( k + 1 ) .
From where,
h ( k − 1 ) > log N − 2 h − 2 log ( k + 1 ) . \begin{equation}
h(k-1)>\log N-2 h-2\log(k+1). \tag*{(111)}
\end{equation} h ( k − 1 ) > log N − 2 h − 2 log ( k + 1 ) . (111)
Is already known that C L Z ( w ) < N / ( k − 1 ) C_{LZ}(w)< N/(k-1) C L Z ( w ) < N / ( k − 1 ) , using equations (111) and ((104) ),,
C L Z ( w ) < N h ( 1 − ϵ N ′ ) log N , \begin{equation}
C_{LZ}(w)<\frac{N h}{(1-\epsilon'_N)\log N}, \tag*{(112)}
\end{equation} C L Z ( w ) < ( 1 − ϵ N ′ ) log N N h , (112)
where
ϵ N ′ = 2 h log N + 2 log ( log N + 1 ) log N , \epsilon'_N=\frac{2 h}{\log N}+\frac{2\log(\log N+1)}{\log N}, ϵ N ′ = log N 2 h + log N 2 log ( log N + 1 ) ,
which tends to zero as N → ∞ N\rightarrow \infty N → ∞ . The property ((56) ) follows.
Block entropy from a coverage-adjusted frequency estimator
Given a sequence u u u the surrogate-and-Lempel-Ziv step is replaced with a direct, coverage-adjusted estimate of H ℓ ( u ) H_\ell(u) H ℓ ( u ) from the block frequency histogram of the sequence itself, following Chao and Shen [101 ] which avoid the need of building surrogate sequence and no Lempel-Ziv factorisation of it is taken: entropy computed from a frequency histogram is manifestly insensitive to the order in which the blocks occur, so the shuffling step was never intrinsic to estimating H ℓ ( u ) H_\ell(u) H ℓ ( u ) – it was only ever necessary to make an order-sensitive estimator (Lempel-Ziv complexity) behave as if the blocks were exchangeable. Working from the histogram directly removes that intermediate step and its associated bias.
Two choices complete the construction. First, the histogram is built from sliding, overlapping length-ℓ \ell ℓ windows of u u u rather than a non-overlapping partition: m ℓ = N − ℓ + 1 m_\ell = N-\ell+1 m ℓ = N − ℓ + 1 windows rather than N / ℓ N/\ell N / ℓ blocks. The two constructions estimate the same quantity – the ergodic average over the source’s length-ℓ \ell ℓ block distribution is, by definition, insensitive to which of the ℓ \ell ℓ possible phases a given window happens to start on – but the non-overlapping partition realises only one such phase per sequence, which can measure something other than that average for sources with structure commensurate with ℓ \ell ℓ : e.g. a sequence with exact period ℓ \ell ℓ has every non-overlapping ℓ \ell ℓ -block identical, so a non-overlapping estimate of H ℓ ( u ) H_\ell(u) H ℓ ( u ) reads exactly 0 0 0 regardless of the source’s real per-block entropy, purely as an artifact of the single phase sampled. Sliding by 1 1 1 removes this phase-alignment sensitivity entirely, and incidentally supplies far more samples per scale, directly easing the # ℓ \#_\ell # ℓ -vs-m ℓ m_\ell m ℓ imbalance identified above.
Second, entropy is read off each histogram with the Good-Turing/Horvitz-Thompson coverage correction of Chao and Shen, rather than the maximum-likelihood estimate. Writing n i n_i n i for the count of the i i i -th distinct length-ℓ \ell ℓ block observed among the m ℓ m_\ell m ℓ windows, the Good-Turing coverage estimate is C ^ ℓ = 1 − f 1 , ℓ / m ℓ \widehat C_\ell = 1-f_{1,\ell}/m_\ell C ℓ = 1 − f 1 , ℓ / m ℓ , with f 1 , ℓ f_{1,\ell} f 1 , ℓ the number of blocks observed exactly once; each block’s coverage-adjusted probability is p ^ i = C ^ ℓ ( n i / m ℓ ) \widehat p_i = \widehat C_\ell\,(n_i/m_\ell) p i = C ℓ ( n i / m ℓ ) , and
H ^ ℓ C S = − ∑ i p ^ i log p ^ i 1 − ( 1 − p ^ i ) m ℓ , H ^ 0 ≡ 0 , \begin{equation}
\widehat H_\ell^{\mathrm{CS}} \;=\; -\sum_i \frac{\widehat p_i \log \widehat p_i}
{1-(1-\widehat p_i)^{m_\ell}},
\qquad \widehat H_0 \equiv 0, \tag*{(113)}
\end{equation} H ℓ CS = − i ∑ 1 − ( 1 − p i ) m ℓ p i log p i , H 0 ≡ 0 , (113)
consistent with H 0 ( u ) = 0 H_0(u)=0 H 0 ( u ) = 0 ; here H ^ ℓ \widehat H_\ell H ℓ denotes H ^ ℓ C S \widehat H_\ell^{\mathrm{CS}} H ℓ CS . The denominator is a Horvitz-Thompson correction for the categories the sample of size m ℓ m_\ell m ℓ is likely to have missed entirely; unlike a first-order correction such as Miller-Madow, it remains reliable well into the regime # ℓ ≳ m ℓ \#_\ell\gtrsim m_\ell # ℓ ≳ m ℓ . Numerical results estimate that it recovers the true entropy to within 3 % 3\% 3% .
Reliability safeguards: monotone projection and adaptive truncation
Because Δ H ℓ ( u ) − h ≥ 0 \Delta H_\ell(u) - h \geq 0 Δ H ℓ ( u ) − h ≥ 0 for every ℓ \ell ℓ (Appendix § 14 ), the exact partial sum ∑ ℓ ≤ n ( Δ H ℓ − h ) \sum_{\ell\leq n}(\Delta H_\ell - h) ∑ ℓ ≤ n ( Δ H ℓ − h ) is non-negative and non-decreasing in n n n – a direct consequence of Appendix § 13 ’s monotonicity of H ℓ ( u ) H_\ell(u) H ℓ ( u ) combined with Appendix § 14 ’s bound. The finite-sample estimate E ^ ( n ) \widehat E(n) E ( n ) of Eq. (73) is not guaranteed to inherit either property: h ^ \widehat h h still carries its own finite-N N N bias (§ 7 , Eq. (70) ), and while H ^ ℓ C S \widehat H_\ell^{\mathrm{CS}} H ℓ CS is markedly less biased than a Lempel-Ziv-based estimate at any single ℓ \ell ℓ (see above), h ^ \widehat h h ’s residual bias is still multiplied by a growing ℓ \ell ℓ in Eq. (73) : at large enough n n n , this can accumulate into a visibly non-monotone, or even net-negative, partial sum, even where every individual H ^ ℓ \widehat H_\ell H ℓ is itself accurate.
We therefore project the raw sequence { E ^ ( 1 ) , … , E ^ ( n ) } \{\widehat E(1),\ldots,\widehat E(n)\} { E ( 1 ) , … , E ( n )} onto the cone of non-negative, non-decreasing sequences before reading off the answer, via the pool-adjacent-violators algorithm [127 ] : consecutive values that violate monotonicity are replaced by their pooled average, repeatedly, until the whole sequence is non-decreasing, after which any remaining negative values are floored at zero. The reported summands Δ H ^ ℓ − h ^ \Delta\widehat H_\ell - \widehat h Δ H ℓ − h are the increments of this projection rather than the raw differences, and E ^ \widehat E E itself is the projected value at ℓ = n \ell=n ℓ = n .
n n n is further chosen as the index at which the raw (unprojected) partial sum peaks, rather than the largest n n n the reliability bound of § 7.2.1 below would allow: past that peak, h ^ \widehat h h ’s residual bias dominates whatever genuine structure remains to be resolved, and the decline that follows carries no information the projection above should be allowed to fold back in. This is a bound on what the data can support, not a claim of having recovered E E E in full: for sources whose correlation length is long relative to what N N N can resolve at the block sizes H ^ ℓ C S \widehat H_\ell^{\mathrm{CS}} H ℓ CS remains reliable at, the true peak of the exact partial sum lies beyond where the estimated one is truncated, and only a longer sequence recovers the difference.
Finite state automata
A finite-state process is one that can be represented by a finite-state automaton (FSA). In a finite-state automaton of the type considered here, a finite number of states S {S} S are connected by transitions from one state to another. The transition from one state to another happens with a certain probability, and upon such a transition, a unique symbol is emitted. For a given state S i S_i S i , T k i a \mathcal{T}^{a}_{ki} T k i a represents the probability of transitioning from state i i i to state k k k while emitting a symbol a a a . We will be interested in the class of processes where, given a state S i S_i S i , the emitted symbol a a a determines the state to which the transition happens (unifilar), and we can write T i a = T k i a \mathcal{T}^{a}_{i}=\mathcal{T}^{a}_{ki} T i a = T k i a . The process starts in an initial state, and at each step, a transition to another state occurs while a symbol is emitted. At step t t t , the probability that the process is at state S i S_i S i is denoted by p i ( t ) p_i^{(t)} p i ( t ) . The asymptotic probability of a state is denoted by p i ( ∞ ) p_i^{(\infty)} p i ( ∞ ) .
If one considers, among all possible FSAs, only the unifilar and minimal Markov chains [128 ] , then,
h = − ∑ i ∑ a p i ( ∞ ) T i a log T i a , h= -\sum\limits_i\sum\limits_a p_i^{(\infty)}\mathcal{T}^{a}_{i}\log \mathcal{T}^{a}_{i}, h = − i ∑ a ∑ p i ( ∞ ) T i a log T i a ,
and
E = ∑ t = 0 ∞ ∑ i ∑ a ( p i ( ∞ ) − p i ( t ) ) T i a log T i a E=\sum\limits_{t=0}^{\infty}\sum\limits_{i}\sum\limits_{a}(p_i^{(\infty)}-p_i^{(t)})\mathcal{T}^{a}_{i}\log \mathcal{T}^{a}_{i} E = t = 0 ∑ ∞ i ∑ a ∑ ( p i ( ∞ ) − p i ( t ) ) T i a log T i a
We have used three Markovian processes as examples: The even process, the 2-state symmetric process and the random-random-xor process.
Figure 9. Diagram of the recurrent part finite state automaton for the (a) even process; (b) two-state symmetric process and (c) the rrxor process.
The even process can be represented by a finite state automaton as depicted in Figure 9 (a). It generates binary strings with an even number of 0 0 0 ; the occurrence of a pair of 0 0 0 happens with probability τ \tau τ , while the occurrence of the symbol 1 1 1 happens with probability τ ˉ = 1 − τ \bar{\tau}=1-\tau τ ˉ = 1 − τ .
The two state symmetric process (2ssp) is shown in Figure 9 (b). It is a two-state FSA where the probability of transitioning from one state to the other is given by τ \tau τ , and, correspondingly, the probability of staying in the same state is τ ˉ = 1 − τ \bar{\tau}=1-\tau τ ˉ = 1 − τ .
The random-random-XOR process (RRXOR) is a five-state FSA, shown in Figure 9 (c). It generates binary strings in non-overlapping blocks of three symbols: the first two are independent, each equal to 1 with probability p p p and to 0 with probability p ˉ = 1 − p \bar p = 1-p p ˉ = 1 − p ; the third is fixed by the first two through s 3 = s 1 ⊕ s 2 s_3 = s_1 \oplus s_2 s 3 = s 1 ⊕ s 2 .
Convolutional neural network for heart disease diagnosis.
The structure of the CNN is given by:
A first convolutional layer, with 64 filters and a kernel size of 5, designed to identify simple, low-level local patterns.
A ReLU activation function to introduce nonlinearity, allowing the network to learn more complex relationships.
A Max-pooling layer with a kernel size of 2.
A second convolutional layer, with 128 filters and a kernel size of 3. By having more filters and a smaller kernel, it seeks to combine the simple patterns detected by the first layer into more complex features.
Then a ReLU function and a Max-pooling layer are applied again, and subsequently the output is flattened.
Three fully connected layers: the first reduces dimensionality to 128 neurons, the second to 64, and the final one to a single output neuron. Between these layers, ReLU activation functions and Dropout layers with a rate of 0.3 are applied.
The final output neuron uses a Sigmoid activation function. This function compresses the output to the range 0 to 1, allowing it to be interpreted as the probability that the patient belongs to each class.