The Information Content and Entropy of Finite Patterns from a Combinatorial Perspective
Zsolt Pocze · 2025
Read The Information Content and Entropy of Finite Patterns from a Combinatorial Perspective by Zsolt Pocze (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10824.txt.
Introduction
Zsolt Pocze wrote a theoretical paper in 2025 on how much information a finite pattern contains. Standard information theory grew up around Shannon's ideas, which fit signals from well-behaved random processes such as ergodic Markov chains. Many real patterns do not come from such processes, so Pocze seeks definitions of information content and entropy that apply more broadly while agreeing with the traditional ones where those work.
Working from a combinatorial viewpoint, he compares the information content of different finite patterns and derives general properties any such quantity should have. From those properties he builds normalized estimation methods based on compression algorithms and Kolmogorov complexity. He then redefines entropy in the same spirit, in a way that matches traditional entropy in the large limit.
Catalog record
| CREATOR | Zsolt Pocze |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10824
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Information Content and Entropy of Finite Patterns from a Combinatorial Perspective Zsolt Pocze Abstract A unified combinatorial definition of the information content and entropy of different types of patterns, compatible with the traditional concepts of information and entropy, going beyond the limitations of Shannon information interpretable for ergodic Markov processes. We compare the information content of various finite patterns and derive general properties of information quantity from these comparisons. Using these properties, we define normalized information estimation methods based on compression algorithms and Kolmogorov complexity. From a combinatorial point of view, we redefine the concept of entropy in a way that is asymptotically compatible with traditional entropy. 1 Introduction The characteristic feature of a material is its pattern, which we interpret broadly as the arrangement of its elementary components. This also includes the relationships between individual parts. In physical reality, every finite-dimensional pattern can be modeled, with some accuracy, as a one-dimensional finite sequence. Therefore, we examine information and entropy in relation to finite sequences (patterns). Let X^{*} denote the set of finite patterns, where X is the value set (or base set) of the patterns. For a given pattern A\in X^{*} , A=(x_{1},x_{2},...,x_{n}) , let n=|A| be the length of the pattern, k=|X| be the number of elements in the value set, and let f(x) , x\in X be the number of occurrences of the element x in the pattern. Information is nothing other than the number of binary decisions [ 6 ] , required to uniquely determine a pattern, i.e., the number of decisions needed to select the given pattern from among all possible patterns and the empty pattern. The fundamental unit of information is the binary decision, measured in bits. In practice, the number of decisions can only take integer values, but if we use a continuous function, we do not always obtain integer values; this yields the theoretical number of decisions. For the sake of mathematical simplicity, we will hereafter always refer to the theoretical number of decisions as the number of decisions. For this reason, and others, determining the amount of information is always an approximate process. Definition 1 . Let the information of a finite pattern A\in X^{*} be the minimum number of binary decisions necessary to uniquely specify that pattern. Denote this by I(A) , where I:X^{*}\rightarrow\mathbb{R^{\mathrm{+}}} is a function, and I(A)=min\{n|A\>is\>reproducible\>by\>decision\>sequence\>(d_{1},d_{2},...,d_{n})\}\>\boxempty (1) This definition is general since it does not depend on any specific system, purely theoretical since it explicitly incorporates all implicit information, and is philosophically less debatable because the minimum number of decisions represents the most general measure of information content. At the same time, the concepts within the definition are not precisely defined for practical or even theoretical application: we have not fixed what exactly constitutes an elementary decision, what reproducibility means, nor how to decompose the description of generating a pattern into elementary decisions. Kolmogorov complexity [ 4 ] is a special case of the above definition of information, which determines the number of decisions required to describe patterns using a universal Turing machine: Definition 2 . Let U be a fixed universal Turing machine. Then, the Kolmogorov complexity I_{K}(A) of a finite pattern A\in X^{\ast} is defined as: I_{K}(A)=min\{\mid B\mid\,\hskip 0.0pt:\,\hskip 0.0ptU(B)=A\} (2) where \mid B\mid denotes the length of the binary program (bit sequence), and the minimum is taken over all programs B that, when used as input to the universal Turing machine U , produce A as output. Unfortunately, Kolmogorov complexity is generally not computable [ 1 ] . However, the information content can be determined very precisely and explicitly in certain edge cases. These include numbers, constant patterns, uniformly distributed random patterns, and patterns with well-defined statistical properties, such as those generated by ergodic Markov processes. When seeking more accurate methods for defining information in both theoretical and practical contexts, it is essential to first examine these edge cases and the aforementioned special instances. 2 Information Content of a Constant Pattern For a constant and finite pattern A\in\{a\}^{\ast} , no information is required to determine the individual elements of the pattern since it consists of the repetition of a single element. Only the length of the pattern, n , carries information, which requires at most \lceil log_{2}n\rceil decisions (or bits of information) to determine, as each decision halves the possible options. For simplicity and mathematical tractability, we use the theoretical approximation log_{2}n . Starting from the information content of integers, one can calculate the information content of any pattern composed of identical elements if we interpret information as the process of selecting the given pattern from all possible sub-patterns, including the zero-length pattern. 1 () 2 a 3 aa … … n+1 aaa...a Table 1: In the case of a constant pattern of length n , the definition of information can be simplified to selecting from n+1 elements, where () denotes the empty pattern. The logarithm of the total number of possible patterns that can be formed from the elements of the pattern gives the information content of the specific pattern. In that case, the information of A is: I_{const}(A)=log_{2}(n+1) (3) Using n+1 instead of n is more practical because it allows the information content of an empty pattern to be defined, acknowledging that the empty pattern, as a possibility, also carries information. It is easy to see that among finite patterns, constant patterns have the lowest information content, as non-constant patterns require more decisions due to the presence of different elements. These additional decisions increase the information content. We do not use the formula log_{2}(n) because then subadditivity is not satisfied for patterns of length one. The condition for subadditivity is I_{rand}(ab)\leq I_{rand}(a)+I_{rand}(b) . If we used the formula log_{2}n , then for the concatenation of patterns of length n=1 , subadditivity would not be satisfied: log_{2}(2)\nleq log_{2}(1)+log_{2}(1) . In the case of the formula log_{2}(n+1) , however, subadditivity is satisfied for all n\geq 0 : n_{1} n_{2} Subadditivity 0 0 log_{2}1\leq log_{2}1+log_{2}1 0 1 log_{2}2\leq log_{2}1+log_{2}2 1 1 log_{2}3\leq log_{2}2+log_{2}2 1 2 log_{2}4\leq log_{2}2+log_{2}3 2 2 log_{2}5\leq log_{2}3+log_{2}3 Table 2: The fulfillment of subadditivity in the case of uniformly distributed random sequences of different lengths. 3 Information Content of a Uniformly Distributed Random Pattern A finite pattern A\in X^{*} with a uniform distribution can be generated such that each element of the pattern results from an independent decision requiring log_{2}\left(k\right) bits, where k is the number of possible symbols. Considering that we can select from n+1 patterns of different lengths, the pattern’s information content is: I_{rand}(A)=log_{2}\sum_{i=0}^{n}k^{i} (4) If k=1 , i.e., if A is a constant pattern, the formula simplifies to the constant pattern formula: I_{rand}(A)=log_{2}\sum_{i=0}^{n}1^{i}=log_{2}(n+1) The complexity of I_{rand}\left(A\right)=log_{2}\sum_{i=0}^{n}k^{i}=log_{2}\frac{k^{n+1}-1}{k-1} is O(n\cdot log_{2}(k)) , Thus, for sufficiently large n and k , the approximation I_{rand}(A)\approx n\cdot log_{2}(k) also holds. We do not use the formula n\cdot log_{2}(k) because, in the case of unit-length patterns, subadditivity would not hold: 2\cdot log_{2}(2)\nleq 1\cdot log_{2}(1)+1\cdot log_{2}(1) and it would not yield accurate values for constant patterns either. 4 Information Content of Patterns Generated by an Ergodic Markov Process Let A\in X^{*} be a pattern that can be generated by an ergodic Markov process, and let f_{rel}(x_{i})=\frac{f(x_{i})}{n} , x_{i}\in X , i=1,...,k be the relative