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

I. INTRODUCTION

• The article gathers mathematical foundations, estimation, and practical use of entropy-related measures, but leaves out some important prior work and is not a review.It also introduces publicly available estimation software.Source: §I · p. 2

II. STRINGS, ERGODICITY AND STATIONARITY

• A symbolic sequence is built from a finite alphabet, with positions indexed as time and finite sequences treated as words.The notation uses log base α, so binary-sequence entropies are expressed in bits.Source: §II · p. 3
• Ergodicity lets a single realization represent a source because finite-word frequencies converge to the same values across almost every emitted string.Stationarity means the probability of a finite string does not depend on its time of occurrence.Source: §II · p. 3

A. Shannon block entropy; B. Entropy gain

• Block entropy Hℓ is non-decreasing with block length, while entropy gain ΔHℓ is non-negative, non-increasing, and equals the uncertainty of the next symbol given its prefix.For an ergodic stationary source, the limit of ΔHℓ exists.Source: A. Shannon block entropy · p. 5, B. Entropy gain · p. 5

C. Entropy density

• For sufficiently large ℓ, block entropy Hℓ grows linearly with slope equal to entropy density.Entropy gain and finite-order entropy density agree in the limit, but entropy gain converges faster.Source: C. Entropy density · p. 6

D. Number of different words

• The normalized number of distinct length-ℓ words characterizes the sequence asymptotically; periodic sequences have limit zero, while i.i.d. sequences with nonzero symbol probabilities have maximal distinct-word growth.For a periodic sequence with minimal period p, the number of distinct words is p once ℓ ≥ p.Source: D. Number of different words · p. 7

E. Number of distinct words and entropy

• For an ergodic source, Ziv’s theorem states that the limiting normalized distinct-word count equals entropy density, despite depending on word counts rather than their occurrence frequencies.The theorem concerns the limit and does not establish equivalence at finite ℓ.Source: E. Number of distinct words and entropy · p. 7

F. Algorithmic complexity and entropy

• Kolmogorov complexity measures a string’s information content by the length of its shortest generating program, but is non-computable because of the halting problem.The non-computability of K(w) does not by itself imply non-computability of its per-symbol growth rate.Source: F. Algorithmic complexity and entropy · p. 8
• For an ergodic source, expectations of algorithmic information measures correspond to classical entropy quantities, linking Shannon-theoretic and Kolmogorov-theoretic descriptions.The article places this connection within its broader treatment of entropy-related magnitudes.Source: F. Algorithmic complexity and entropy · p. 8

IV. ENTROPY CONVERGENCE: EFFECTIVE MEASURE COMPLEXITY

• The convergence speed of an entropy-related magnitude depends on the summed deficits from its limiting value, and that sum may fail to converge.For a power-law decay proportional to ℓ^-γ, convergence requires γ > 1; for the stated intermediate decay form, it requires ν > 0.Source: §IV · p. 9
• For periodic sequences, ζℓ and hℓ yield a divergent harmonic-series contribution, whereas the article focuses on EΔHℓ as the effective measure complexity.The passage identifies the divergence as an unsuitable property for distinguishing periodic sequences.Source: §IV · p. 9
• Effective measure complexity is the mutual information between the two halves of a bi-infinite sequence, representing information shared between past and future.A positive value signals correlation across the partition; random and i.i.d. sequences have E = 0.Source: §IV · p. 10

V. INFORMATION DISTANCE

• Informational distance is the maximum of the two conditional algorithmic complexities and satisfies distance properties up to an O(1/K(wi)) correction.The correction is expressed in terms of the string with the largest algorithmic complexity.Source: §V · p. 10
• Unlike Jensen–Shannon divergence, informational distance measures information shared between individual sequences, making it appropriate when coupling rather than statistical similarity is sought.Independent realizations of the same source can have vanishing Jensen–Shannon divergence but informational distance close to one.Source: §V · p. 11

A. Flow of information

• Direct estimation of transfer entropy requires a joint histogram with α^(2m+1) cells for symbolic data, causing undersampling and sensitivity to estimation settings in realistic records.For continuous data, partitioning or kernel estimation adds further free parameters.Source: A. Flow of information · p. 12
• The transfer entropy rate expresses information flow per symbol and is asymmetric, vanishing when the source past adds no information about the target’s present.The article estimates it with Lempel–Ziv factorisation and uses a same-dimension surrogate to remove residual bias.Source: A. Flow of information · p. 12
• Surrogate correction compares the estimate with time-permuted source-past surrogates that preserve marginal statistics and embedding size, so the corrected rate measures reduction attributable to the real past.The correction averages over Γ surrogates.Source: A. Flow of information · p. 12

VI. LEMPEL-ZIV FACTORISATION

• Each factor in an exhaustive Lempel-Ziv factorisation adds a word to the growing vocabulary, and the factorisation is unique.The exhaustive history is the smallest possible history factorisation.Source: §VI · p. 13, A. Properties of the LZ-factorisation · p. 13
• Lempel-Ziv complexity is the number of factors in the exhaustive factorisation, with each factor representing an innovation.More factors therefore correspond to a larger innovation process in producing the string.Source: §VI · p. 13

A. Properties of the LZ-factorisation

• The exhaustive history is the smallest possible history factorisation.Source: A. Properties of the LZ-factorisation · p. 13
• For strings w1 and w2, CLZ(w1w2) ≤ CLZ(w1) + CLZ(w2).The concatenated Lempel-Ziv factorizations form a history of w1w2, which gives the bound.Source: A. Properties of the LZ-factorisation · p. 13

B. Shannon entropy and LZ-factorisation

• Ziv’s theorem underpins using normalized Lempel-Ziv complexity to estimate entropy density, with the finite-length estimate subject to error.The error is related to εN and decays slowly; for a binary alphabet it is about 0.4 at one million symbols and 0.3 at 10^9 symbols.Source: A. Entropy density · p. 14, B. Shannon entropy and LZ-factorisation · p. 14

A. Entropy density

• Finite-sequence entropy-density estimates are underestimated by κ log N/N, and fitting complexity against sequence length is highly sensitive to the fit’s starting length N0.The sensitivity follows from slow convergence of normalized Lempel-Ziv complexity.Source: A. Entropy density · p. 14
• Across four examples, Lempel-Ziv complexity is asymptotically bounded by N/log N, while short-sequence behavior can deviate substantially, especially for DNA data.The figure compares complexity against N/log N for finite-state sources, mammalian DNA sequences, and a random string.Source: A. Entropy density · p. 14, Figure 1 · p. 15
• For the symmetric two-state process, estimated entropy density behaves almost identically to exact h from sequences of 256 symbols onward.Across the symmetric two-state, even, and random-random-xor processes, estimates follow the general trend at 256 symbols and are almost indistinguishable from exact h above 10^3 symbols.Source: A. Entropy density · p. 16

B. Effective measure complexity

• Estimating effective measure complexity is harder than estimating entropy density because its general evaluation involves infinite sums and usually converges more slowly.This makes estimates more cumbersome and less reliable for shorter sequences.Source: B. Effective measure complexity · p. 16
• The effective measure complexity estimator uses entropy gain because it converges monotonically to entropy density and at least as fast as block entropy hℓ.Only the entropy-gain terms need estimating; these require estimates of length-ℓ Shannon block entropy.Source: B. Effective measure complexity · p. 16
• The surrogate-and-Lempel-Ziv estimator can increasingly underestimate entropy density as ℓ grows once observed distinct blocks approach the available sample of blocks.With non-overlapping blocks, the available count mℓ = N/ℓ falls linearly while distinct blocks may grow as fast as min(mℓ, αℓ).Source: B. Effective measure complexity · p. 17
• For i.i.d. draws across 28,256 equally likely categories, Lempel-Ziv recovered only 55–80% of true entropy in the controlled test.The test was chosen to resemble the distinct-block versus sample-size balance reached in the surrogate construction.Source: B. Effective measure complexity · p. 17

1. Choice of n

• The estimated effective measure complexity resembles the true quantity most closely when correlation structure decays uniformly, while strongly varying synchronization times require larger n and longer sequences.The estimate is not claimed to equal the effective measure complexity.Source: §1 · p. 18

B. Effective measure complexity

• 2SSP reaches a low effective-measure-complexity error floor by N = 50,000, while the even process and RRXOR improve more slowly and have not reached a comparable floor at N = 500,000.The latter processes demand longer block-size resolution than the estimated block entropy can reliably support at this sample size.Source: Figure 3 · p. 19

C. Information distance

• The Lempel-Ziv-based distance is pattern-driven and can be near 1 for strings that the Kolmogorov-based distance renders close.It is therefore not an all-encompassing substitute for the Kolmogorov distance.Source: C. Information distance · p. 20
• For the even process, Lempel-Ziv information distance is near 1 between the output and its negation or reversal except at τ = 0, 1.This motivates checking simple, process-meaningful transformations when comparing sequences.Source: C. Information distance · pp. 20–21, Figure 5 · p. 20

D. Transfer entropy

• Embedding the target’s present with the joint past in an extended-alphabet Lempel–Ziv estimate preserves temporal alignment and yields a conditional rather than joint rate that responds to lagged influence.The marginal entropy-density estimate drops the conditioner block.Source: D. Transfer entropy · p. 21

VIII. LEMPEL-ZIV ALGORITHM

• More than 10-fold execution-time improvement over sequential algorithms is reported for strings longer than 10^6 symbols, with support for strings as large as 10^9 symbols.The open-source lzcomplexity library implements parallel algorithms in C++ and Python using oneTBB.Source: §VIII · p. 21

A. Brain connectivity

• The local entropy-density and complexity criterion classifies 8.61% of motor-task regions as active, while distinguishing dynamical regimes among regions with the same activation status.The map forms a continuum, so the authors use neighbourhood thresholds based on residuals from a linear fit rather than a fixed cut.Source: A. Brain connectivity · p. 22
• Informational-distance clustering groups visual, motor/sensory, and mixed visual, motor, and attentional regions, with active regions clustering at low dendrogram levels.The distance band narrows over the active block, indicating tighter functional coupling among active regions.Source: A. Brain connectivity · p. 22
• The motor-task activation pattern is anatomically coherent, and informational distances reveal functional groupings among active and other brain regions.The recovered pattern matches the task’s known substrate without a design matrix, hemodynamic model, or tuned parameter.Source: A. Brain connectivity · p. 22, Figure 6 · p. 23

B. Non-linear locally coupled oscillators

• In coupled oscillators, entropy density and effective measure complexity distinguish regimes, while informational-distance patterns near the needle region indicate collective behaviour.The needle region has near-zero entropy density and effective measure complexity approaching 3; wave-like patterns appear at ω = 2.225 and γ = 1.206.Source: B. Non-linear locally coupled… · p. 24, Figure 7 · p. 25

C. Electrocardiogram analysis

• SR recurrence maps show continuous diagonal lines absent in AFIB, while healthy subjects tend toward lower entropy density and higher effective measure complexity.AFIB maps suggest more complex dynamics with a stochastic component; some AFIB segments have effective complexity comparable to SR segments.Source: C. Electrocardiogram analysis · pp. 24–26
• 83.2% overall accuracy was achieved using entropy-density features from two leads of a 10-second ECG.The confusion matrix reports true-negative and true-positive rates above 82%.Source: Figure 8 · p. 26, C. Electrocardiogram analysis · pp. 26–27

D. Further applications

• Written-language measures distinguish writers and genres and quantify organizational levels; pathway-ordered gene-expression maps separate tumour from normal samples in 9 of 13 tumour types.Several tumour types have success rates above 98%; the reported trend emerges from pathway ordering without gene preselection or a disease model.Source: D. Further applications · p. 27
• Freeman chain-code sequences from trajectories separate regular from chaotic orbits and support classification by fall history under different postural conditions.The eight-symbol encoding requires no embedding or threshold.Source: D. Further applications · p. 27

X. CONCLUSIONS

• The article connects Shannon entropy with Kolmogorov complexity and develops finite-sequence estimation procedures for entropy density, effective measure complexity, informational distance, and transfer entropy rate.Its open-source lzcomplexity library implements parallel algorithms for sequences up to 10^9 symbols.Source: §X · p. 27

XII. DATA AVAILABILITY AND AUTHORS STATEMENT

• The authors report public availability of the supporting brain and heart data and the lzcomplexity software.The data are from the Human Connectome Project and PhysioNet; the software is available on GitHub and archived on Zenodo.Source: §XII · p. 28

Appendix A: Block entropy Hℓ(u) is a non-decreasing function of ℓ.

• Hℓ(u) is non-decreasing with ℓ because the added conditional-entropy terms are non-negative.The proof uses log P(·) ≤ 0 to establish positivity of each term in the sum.Source: Appendix A · p. 28

Appendix B: Entropy gain converges faster than hℓ.

• hℓ(u) is non-increasing, with hℓ(u) ≥ ΔHℓ(u) ≥ ΔHℓ+1(u).Source: Appendix B · p. 29
• The limit superior of ζℓ(u) also exists.Source: Appendix B · p. 29
• The sequence aℓ = log #ℓ = ℓζℓ(u) is subadditive, so Fekete’s lemma gives a limit of aℓ/ℓ equal to its infimum.The passage notes that a bound on successive differences alone would not guarantee convergence.Source: Appendix B · p. 30

• For sufficiently large block length, a typical set has at most αℓ(h+ϵ) elements and at least (1−ϵ)αℓ(h−ϵ), with its elements almost equiprobable.Source: Appendix D · p. 30
• Ergodicity ensures that every block in Ω occurs in the sequence with probability 1, supporting the reverse inequality in the proof.Source: Appendix D · p. 31
• The proof concludes the desired result in probability.Source: Appendix D · p. 31

Appendix E: The exhaustive history of a sequence is the smallest of all history factorisations [35]

• For a sequence over alphabet A, the exhaustive history has no more factors than any non-exhaustive history factorisation.The proof establishes this by showing the exhaustive factor count nF is no greater than n′F.Source: Appendix E · pp. 31–32

Appendix F: Upper bound for the length of the Lempel-Ziv factorisation [35].

• For a length-N sequence, CLZ(w) is at most nF + 1, where nF is the number of distinct words in its parsing.Source: Appendix F · p. 32
• The Appendix F upper-bound argument uses a string formed by concatenating words in lexicographic order up to length k.The passage gives 0 · 1 · 00 · 01 · 10 · 11 … as an example when k = 5.Source: Appendix F · pp. 32–33

• For an ergodic source, the typical set has cardinality α^hN, and almost all length-N strings are typical for large N.Source: Appendix G · p. 33
• The appendix states the bound CLZ(w) < N/(k−1).Source: Appendix G · p. 34
• The quantity preceding property (56) tends to zero as N → ∞, from which the appendix concludes that property.Source: Appendix G · p. 34

Appendix H: Block entropy from a coverage-adjusted frequency estimator

• The estimator computes block entropy directly from the sequence’s block-frequency histogram, avoiding surrogate generation and Lempel-Ziv factorisation.Because histogram entropy ignores block order, the shuffling step was needed only for the order-sensitive Lempel-Ziv estimator.Source: Appendix H · p. 34
• Sliding length-ℓ windows avoid phase-alignment sensitivity and provide more samples than a non-overlapping partition.For a sequence with period ℓ, non-overlapping blocks can all be identical and yield an estimate of zero despite nonzero per-block entropy.Source: Appendix H · p. 34
• Numerical results estimate that the coverage-adjusted estimator recovers true entropy to within 3%.The method uses a Horvitz–Thompson correction for categories likely missed by the sample, including when the number of possible blocks exceeds the number of windows.Source: Appendix H · p. 34
• The raw partial-sum estimate is projected onto non-negative, non-decreasing sequences because finite-sample bias can make it non-monotone or negative.The pool-adjacent-violators algorithm pools violations, floors remaining negative values at zero, and the projected value at n is reported.Source: a. Reliability safeguards: monotone… · pp. 34–35
• Truncation selects the peak of the raw partial sum because beyond it residual bias can overwhelm resolvable structure; long-correlation sources may require longer sequences.When the true peak lies beyond the estimated truncation point, only a longer sequence recovers the difference.Source: a. Reliability safeguards: monotone… · p. 35

Appendix I: Finite state automata

• The examples are unifilar finite-state processes, with emitted symbols determining transitions; they include the even, two-state symmetric, and random-random-XOR processes.The even process generates strings with an even number of zeros; RRXOR emits non-overlapping triples whose third symbol is the XOR of the first two.Source: Appendix I · pp. 35–36
• The two-state symmetric process switches states with probability τ and stays in the same state with probability 1 − τ.Figure 9 diagrams the recurrent automata for the even, two-state symmetric, and RRXOR processes.Source: Figure 9 · p. 35, Appendix I · p. 36

Appendix J: Convolutional neural network for heart disease diagnosis.

• The CNN uses two convolutional layers followed by three fully connected layers and a sigmoid output interpreted as class probability.The convolutional layers have 64 filters with kernel size 5 and 128 filters with kernel size 3; the fully connected layers have 128, 64, and 1 neurons.Source: Appendix J · p. 36