format: text

text:
# Kolmogorov’s Structure Functions and Model Selection

## I Introduction

As perhaps the last mathematical innovation of an extraordinary scientific career, A.N. Kolmogorov  proposed to found statistical theory on finite combinatorial principles independent of probabilistic assumptions. Technically, the new statistics is expressed in terms of Kolmogorov complexity, , the information in an individual object. The relation between the individual data and its explanation (model) is expressed by Kolmogorov’s structure function. This function, its variations and its relation to model selection, have obtained some notoriety , but it has not before been comprehensively analyzed and understood. It has often been questioned why Kolmogorov chose to focus on the the mysterious function $`h_x`$ below, rather than on the more evident $`\beta _x`$ variant below. The only written record by Kolmogorov himself is the following abstract  (translated from the original Russian by L.A. Levin):

“To each constructive object corresponds a function $`\mathrm{\Phi }_x(k)`$ of a natural number $`k`$—the log of minimal cardinality of $`x`$-containing sets that allow definitions of complexity at most $`k`$. If the element $`x`$ itself allows a simple definition, then the function $`\mathrm{\Phi }`$ drops to $`1`$ even for small $`k`$. Lacking such definition, the element is “random” in a negative sense. But it is positively “probabilistically random” only when function $`\mathrm{\Phi }`$ having taken the value $`\mathrm{\Phi }_0`$ at a relatively small $`k=k_0`$, then changes approximately as $`\mathrm{\Phi }(k)=\mathrm{\Phi }_0(kk_0)`$.”

These pregnant lines will become clear on reading this paper, where we use “$`h_x`$” for the structure function “$`\mathrm{\Phi }_x`$.” Our main result establishes the importance of the structure function: For every data item, and every complexity level, minimizing a two-part code, one part model description and one part data-to-model code (essentially a constrained two-part MDL estimator ), over the class of models of at most the given complexity, with certainty (and not only with high probability) selects models that in a rigorous sense are the best explanations among the contemplated models. The same holds for minimizing the one-part code consisting of just the data-to-model code (essentially a constrained maximum likelihood estimator). The explanatory value of an individual model for particular data, its goodness of fit, is quantified by by the randomness deficiency (II.6) expressed in terms of Kolmogorov complexity: minimal randomness deficiency implies that the data is maximally “random” or “typical” for the model. It turns out that the minimal randomness deficiency of the data in a complexity-constrained model class cannot be computationally monotonically approximated (in the sense of Definition VII.1) up to any significant precision. Thus, while we can monotonically approximate (in the precise sense of Section VIII) the minimal length two-part code, or the one-part code, and thus monotonically approximate implicitly the best fitting model, we cannot monotonically approximate the number expressing the goodness of this fit. But this should be sufficient: we want the best model rather than a number that measures its goodness.

### I-A Randomness in the Real World

Classical statistics investigates real-world phenomena using probabilistic methods. There is the problem of what probability means, whether it is subjective, objective, or exists at all. P.S. Laplace conceived of the probability of a physical event as expressing lack of knowledge concerning its true deterministic causes . A. Einstein rejected physical random variables as well “I do not believe that the good Lord plays dice.” But even if true physical random variables do exist, can we assume that a particular phenomenon we want to explain is probabilistic? Supposing that to be the case as well, we then use a probabilistic statistical method to select models. In this situation the proven “goodness” of such a method is so only in a probabilistic sense. But for current applications, the total probability concentrated on potentially realizable data may be negligible, for example, in complex video and sound data. In such a case, a model selection process that is successful with high probability may nonetheless fail on the actually realized data. Avoiding these difficulties, Kolmogorov’s proposal strives for the firmer and less contentious ground of finite combinatorics and effective computation.

### I-B Statistics and Modeling

Intuitively, a central task of statistics is to identify the true source that produced the data at hand. But suppose the true source is 100,000 fair coin flips and our data is the outcome $`00\mathrm{}0`$. A method that identifies flipping a fair coin as the cause of this outcome is surely a bad method, even though the source of the data it came up with happens to be the true cause. Thus, for a good statistical method to work well we assume that the data are “typical” for the source that produced the data, so that the source “fits” the data. The situation is more subtle for data like $`0101\mathrm{}01`$. Here the outcome of the source has an equal frequency of 0s and 1s, just like we would expect from a fair coin. But again, it is virtually impossible that such data are produced by a fair coin flip, or indeed, independent flips of a coin of any particular bias. In real-world phenomena we cannot be sure that the true source of the data is in the class of sources considered, or, worse, we are virtually certain that the true source is not in that class. Therefore, the real question is not to find the true cause of the data, but to model the data as well as possible. In recognition of this, we often talk about “models” instead of “sources,” and the contemplated “set of sources” is called the contemplated “model class.” In traditional statistics “typicality” and “fitness’ are probabilistic notions tied to sets of data and models of large measure. In the Kolmogorov complexity setting we can express and quantify “typicality” of individual data with respect to a single model, and express and quantify the “fitness” of an individual model for the given data.

## II Preliminaries

Let $`x,y,z𝒩`$, where $`𝒩`$ denotes the natural numbers and we identify $`𝒩`$ and $`\{0,1\}^{}`$ according to the correspondence

$$(0,ϵ),(1,0),(2,1),(3,00),(4,01),\mathrm{}$$

Here $`ϵ`$ denotes the empty word. The length $`|x|`$ of $`x`$ is the number of bits in the binary string $`x`$, not to be confused with the cardinality $`|S|`$ of a finite set $`S`$. For example, $`|010|=3`$ and $`|ϵ|=0`$, while $`|\{0,1\}^n|=2^n`$ and $`|\mathrm{}|=0`$. The emphasis is on binary sequences only for convenience; observations in any alphabet can be so encoded in a way that is ‘theory neutral’. Below we will use the natural numbers and the binary strings interchangeably.

### II-A Self-delimiting Code

A binary string $`y`$ is a proper prefix of a binary string $`x`$ if we can write $`x=yz`$ for $`zϵ`$. A set $`\{x,y,\mathrm{}\}\{0,1\}^{}`$ is prefix-free if for any pair of distinct elements in the set neither is a proper prefix of the other. A prefix-free set is also called a prefix code and its elements are called code words. An example of a prefix code, that is useful later, encodes the source word $`x=x_1x_2\mathrm{}x_n`$ by the code word

$$\overline{x}=1^n0x.$$

This prefix-free code is called self-delimiting, because there is fixed computer program associated with this code that can determine where the code word $`\overline{x}`$ ends by reading it from left to right without backing up. This way a composite code message can be parsed in its constituent code words in one pass, by the computer program. (This desirable property holds for every prefix-free encoding of a finite set of source words, but not for every prefix-free encoding of an infinite set of source words. For a single finite computer program to be able to parse a code message the encoding needs to have a certain uniformity property like the $`\overline{x}`$ code.) Since we use the natural numbers and the binary strings interchangeably, $`|\overline{x}|`$ where $`x`$ is ostensibly an integer, means the length in bits of the self-delimiting code of the binary string with index $`x`$. On the other hand, $`\overline{|x|}`$ where $`x`$ is ostensibly a binary string, means the self-delimiting code of the binary string with index the length $`|x|`$ of $`x`$. Using this code we define the standard self-delimiting code for $`x`$ to be $`x^{}=\overline{|x|}x`$. It is easy to check that $`|\overline{x}|=2n+1`$ and $`|x^{}|=n+2\mathrm{log}n+1`$. Let $``$ denote a standard invertible effective one-one encoding from $`𝒩\times 𝒩`$ to a subset of $`𝒩`$. For example, we can set $`x,y=x^{}y`$ or $`x,y=\overline{x}y`$. We can iterate this process to define $`x,y,z`$, and so on.

### II-B Kolmogorov Complexity

For precise definitions, notation, and results see the text . Informally, the Kolmogorov complexity, or algorithmic entropy, $`K(x)`$ of a string $`x`$ is the length (number of bits) of a shortest binary program (string) to compute $`x`$ on a fixed reference universal computer (such as a particular universal Turing machine). Intuitively, $`K(x)`$ represents the minimal amount of information required to generate $`x`$ by any effective process. The conditional Kolmogorov complexity $`K(x|y)`$ of $`x`$ relative to $`y`$ is defined similarly as the length of a shortest program to compute $`x`$, if $`y`$ is furnished as an auxiliary input to the computation. For technical reasons we use a variant of complexity, so-called prefix complexity, which is associated with Turing machines for which the set of programs resulting in a halting computation is prefix free. We realize prefix complexity by considering a special type of Turing machine with a one-way input tape, a separate work tape, and a one-way output tape. Such Turing machines are called prefix Turing machines. If a machine $`T`$ halts with output $`x`$ after having scanned all of $`p`$ on the input tape, but not further, then $`T(p)=x`$ and we call $`p`$ a program for $`T`$. It is easy to see that $`\{p:T(p)=x,x\{0,1\}^{}\}`$ is a prefix code. Let $`T_1,T_2,\mathrm{}`$ be a standard enumeration of all prefix Turing machines with a binary input tape, for example the lexicographical length-increasing ordered syntactic prefix Turing machine descriptions, , and let $`\varphi _1,\varphi _2,\mathrm{}`$ be the enumeration of corresponding functions that are computed by the respective Turing machines ($`T_i`$ computes $`\varphi _i`$). These functions are the partial recursive functions or computable functions (of effectively prefix-free encoded arguments). The Kolmogorov complexity of $`x`$ is the length of the shortest binary program from which $`x`$ is computed.

###### Definition II.1

The prefix Kolmogorov complexity of $`x`$ is

$$K(x)=\underset{p,i}{\mathrm{min}}\{|\overline{i}|+|p|:T_i(p)=x\},$$
(II.1)
where the minimum is taken over $`p\{0,1\}^{}`$ and $`i\{1,2,\mathrm{}\}`$. For the development of the theory we actually require the Turing machines to use auxiliary (also called conditional) information, by equipping the machine with a special read-only auxiliary tape containing this information at the outset. Then, the conditional version $`K(xy)`$ of the prefix Kolmogorov complexity of $`x`$ given $`y`$ (as auxiliary information) is is defined similarly as before, and the unconditional version is set to $`K(x)=K(xϵ)`$.

One of the main achievements of the theory of computation is that the enumeration $`T_1,T_2,\mathrm{}`$ contains a machine, say $`U=T_u`$, that is computationally universal in that it can simulate the computation of every machine in the enumeration when provided with its index: $`U(y,\overline{i}p)=T_i(y,p)`$ for all $`i,p,y`$. We fix one such machine and designate it as the reference universal prefix Turing machine. Using this universal machine it is easy to show $`K(xy)=\mathrm{min}_q\{|q|:U(y,q)=x\}`$.

A prominent property of the prefix-freeness of $`K(x)`$ is that we can interpret $`2^{K(x)}`$ as a probability distribution since $`K(x)`$ is the length of a shortest prefix-free program for $`x`$. By the fundamental Kraft’s inequality, see for example , we know that if $`l_1,l_2,\mathrm{}`$ are the code-word lengths of a prefix code, then $`_x2^{l_x}1`$. Hence,

$$\underset{x}{}2^{K(x)}1.$$
(II.2)
This leads to the notion of universal distribution—a rigorous form of Occam’s razor—which implicitly plays an important part in the present exposition. The functions $`K()`$ and $`K()`$, though defined in terms of a particular machine model, are machine-independent up to an additive constant and acquire an asymptotically universal and absolute character through Church’s thesis, from the ability of universal machines to simulate one another and execute any effective process. The Kolmogorov complexity of an individual object was introduced by Kolmogorov  as an absolute and objective quantification of the amount of information in it. The information theory of Shannon , on the other hand, deals with average information to communicate objects produced by a random source. Since the former theory is much more precise, it is surprising that analogs of theorems in information theory hold for Kolmogorov complexity, be it in somewhat weaker form. An example is the remarkable symmetry of information property used later. Let $`x^{}`$ denote the shortest prefix-free program $`x^{}`$ for a finite string $`x`$, or, if there are more than one of these, then $`x^{}`$ is the first one halting in a fixed standard enumeration of all halting programs. Then, by definition, $`K(x)=|x^{}|`$. Denote $`K(x,y)=K(x,y)`$. Then,

$`K(x,y)`$ $`=K(x)+K(yx^{})+O(1)`$ (II.3)
$`=K(y)+K(xy^{})+O(1).`$
###### Remark II.2

The information contained in $`x^{}`$ in the conditional above is the same as the information in the pair $`(x,K(x))`$, up to an additive constant, since there are recursive functions $`f`$ and $`g`$ such that for all $`x`$ we have $`f(x^{})=(x,K(x))`$ and $`g(x,K(x))=x^{}`$. On input $`x^{}`$, the function $`f`$ computes $`x=U(x^{})`$ and $`K(x)=|x^{}|`$; and on input $`x,K(x)`$ the function $`g`$ runs all programs of length $`K(x)`$ simultaneously, round-robin fashion, until the first program computing $`x`$ halts—this is by definition $`x^{}`$. $`\mathrm{}`$

### II-C Precision

It is customary in this area to use “additive constant $`c`$” or equivalently “additive $`O(1)`$ term” to mean a constant, accounting for the length of a fixed binary program, independent from every variable or parameter in the expression in which it occurs. In this paper we use the prefix complexity variant of Kolmogorov complexity for convenience. Actually some results, especially Theorem D.1, are easier to prove for plain complexity. Most results presented here are precise up to an additive term that is logarithmic in the length of the binary string concerned, which means that they are valid for plain complexity as well—prefix complexity of a string exceeds the plain complexity of that string by at most an additive term that is logarithmic in the length of that string. Thus, our use of prefix complexity is important for “fine details” only.

### II-D Meaningful Information

The information contained in an individual finite object (like a finite binary string) is measured by its Kolmogorov complexity—the length of the shortest binary program that computes the object. Such a shortest program contains no redundancy: every bit is information; but is it meaningful information? If we flip a fair coin to obtain a finite binary string, then with overwhelming probability that string constitutes its own shortest program. However, also with overwhelming probability all the bits in the string are meaningless information, random noise. On the other hand, let an object $`x`$ be a sequence of observations of heavenly bodies. Then $`x`$ can be described by the binary string $`pd`$, where $`p`$ is the description of the laws of gravity, and $`d`$ the observational parameter setting: we can divide the information in $`x`$ into meaningful information $`p`$ and accidental information $`d`$. The main task for statistical inference and learning theory is to distil the meaningful information present in the data. The question arises whether it is possible to separate meaningful information from accidental information, and if so, how. The essence of the solution to this problem is revealed when we rewrite (II.1) as follows:

$`K(x)`$ $`=\underset{p,i}{\mathrm{min}}\{|\overline{i}|+|p|:T_i(p)=x\}`$ (II.4)
$`=\underset{p,i}{\mathrm{min}}\{2|i|+|p|+1:T_i(p)=x\}`$
$`\underset{q}{\mathrm{min}}\{|q|:U(ϵ,q)=x\}+2|u|+1`$
$`\underset{r,j}{\mathrm{min}}\{K(j)+|r|:U(ϵ,j^{}\alpha r)=T_j(r)=x\}`$
$`+2|u|+1`$
$`K(x)+O(1).`$
Here the minima are taken over $`p,q,r\{0,1\}^{}`$ and $`i,j\{1,2,\mathrm{}\}`$. The last equalities are obtained by using the universality of the fixed reference universal prefix Turing machine $`U=T_u`$ with $`|u|=O(1)`$. The string $`j^{}`$ is a shortest self-delimiting program of $`K(j)`$ bits from which $`U`$ can compute $`j`$, and subsequent execution of the next self-delimiting fixed program $`\alpha `$ will compute $`\overline{j}`$ from $`j`$. Altogether, this has the effect that $`U(ϵ,j^{}\alpha r)=T_j(r)`$. This expression emphasizes the two-part code nature of Kolmogorov complexity. In the example

$$x=10101010101010101010101010$$

we can encode $`x`$ by a small Turing machine printing a specified number of copies of the pattern “01” which computes $`x`$ from the program “13.” This way, $`K(x)`$ is viewed as the shortest length of a two-part code for $`x`$, one part describing a Turing machine, or model, for the regular aspects of $`x`$, and the second part describing the irregular aspects of $`x`$ in the form of a program to be interpreted by $`T`$. The regular, or “valuable,” information in $`x`$ is constituted by the bits in the “model” while the random or “useless” information of $`x`$ constitutes the remainder.

### II-E Data and Model

To simplify matters, and because all discrete data can be binary coded, we consider only finite binary data strings $`x`$. Our model class consists of Turing machines $`T`$ that enumerate a finite set, say $`S`$, such that on input $`i|S|`$ we have $`T(i)=x`$ with $`x`$ the $`i`$th element of $`T`$’s enumeration of $`S`$, and $`T(i)`$ is a special undefined value if $`i>|S|`$. The “best fitting” model for $`x`$ is a Turing machine $`T`$ that reaches the minimum description length in (II.4). Such a machine $`T`$ embodies the amount of useful information contained in $`x`$, and we have divided a shortest program $`x^{}`$ for $`x`$ into parts $`x^{}=T^{}i`$ such $`T^{}`$ is a shortest self-delimiting program for $`T`$. Now suppose we consider only low complexity finite-set models, and under these constraints the shortest two-part description happens to be longer than the shortest one-part description. Does the model minimizing the two-part description still capture all (or as much as possible) meaningful information? Such considerations require study of the relation between the complexity limit on the contemplated model classes, the shortest two-part code length, and the amount of meaningful information captured.

### II-F Kolmogorov’s Structure Functions

We will prove that there is a close relation between functions describing three, a priori seemingly unrelated, aspects of modeling individual data by models of prescribed complexity: optimal fit, minimal remaining randomness, and length of shortest two-part code, respectively (Figure 1). We first need a definition. Denote the complexity of the finite set $`S`$ by $`K(S)`$—the length (number of bits) of the shortest binary program $`p`$ from which the reference universal prefix machine $`U`$ computes a listing of the elements of $`S`$ and then halts. That is, if $`S=\{x_1,\mathrm{},x_n\}`$, then $`U(p)=x_1,x_2,\mathrm{},x_{n1},x_n\mathrm{}`$. The shortest program $`p`$, or, if there is more than one such shortest program, then the first one that halts in a standard dovetailed running of all programs, is denoted by $`S^{}`$. The conditional complexity $`K(xS)`$ of $`x`$ given $`S`$ is the length (number of bits) in the shortest binary program $`p`$ from which the reference universal prefix machine $`U`$ computes $`x`$ from input $`S`$ given literally. In the sequel we also use $`K(xS^{})`$, defined as the length of the shortest program that computes $`x`$ from input $`S^{}`$. Just like in Remark II.2, the input $`S^{}`$ has more information, namely all information in the pair $`(S,K(S))`$, than just the literal list $`S`$. Furthermore, $`K(Sx)`$ is defined as the length of the shortest program that computes $`S`$ from input $`x`$, and similarly we can define $`K(S^{}x),K(Sx^{})`$. For every finite set $`S\{0,1\}^{}`$ containing $`x`$ we have

$$K(xS)\mathrm{log}|S|+O(1).$$
(II.5)
Indeed, consider the selfdelimiting code of $`x`$ consisting of its $`\mathrm{log}|S|`$ bit long index of $`x`$ in the lexicographical ordering of $`S`$. This code is called *data-to-model code*. Its length quantifies the maximal “typicality,” or “randomness,” data (possibly different from $`x`$) can have with respect to this model. The lack of typicality of $`x`$ with respect to $`S`$ is measured by the amount by which $`K(xS)`$ falls short of the length of the data-to-model code. The randomness deficiency of $`x`$ in $`S`$ is defined by

$$\delta (xS)=\mathrm{log}|S|K(xS),$$
(II.6)
for $`xS`$, and $`\mathrm{}`$ otherwise.

“Best Fit” function: The minimal randomness deficiency function is

$$\beta _x(\alpha )=\underset{S}{\mathrm{min}}\{\delta (xS):Sx,K(S)\alpha \},$$
(II.7)
where we set $`\mathrm{min}\mathrm{}=\mathrm{}`$. The smaller $`\delta (xS)`$ is, the more $`x`$ can be considered as a typical member of $`S`$. This means that a set $`S`$ for which $`x`$ incurs minimal deficiency, in the model class of contemplated sets of given maximal Kolmogorov complexity, is a “best fitting” model for $`x`$ in that model class—a most likely explanation, and $`\beta _x(\alpha )`$ can be viewed as a constrained best fit estimator. If the randomness deficiency is close to 0, then are no simple special properties that single it out from the majority of elements in $`S`$. This is not just terminology: If $`\delta (xS)`$ is small enough, then $`x`$ satisfies all properties of low Kolmogorov complexity that hold with high probability for the elements of $`S`$. To be precise: Consider strings of length $`n`$ and let $`S`$ be a subset of such strings. A property $`P`$ represented by $`S`$ is a subset of $`S`$, and we say that $`x`$ satisfies property $`P`$ if $`xP`$. Often, the cardinality of a family of sets $`\{S\}`$ we consider depends on the length $`n`$ of the strings in $`S`$. We discuss properties in terms of bounds $`\delta (n)\mathrm{log}|S|`$. (The lemma below can also be formulated in terms of probabilities instead of frequencies if we are talking about a probabilistic ensemble $`S`$.)

###### Lemma II.3

Let $`S\{0,1\}^n`$.

(i) If $`P`$ is a property satisfied by all $`xS`$ with $`\delta (xS)\delta (n)`$, then $`P`$ holds for a fraction of at least $`11/2^{\delta (n)}`$ of the elements in $`S`$.

(ii) Let $`n`$ and $`S`$ be fixed, and let $`P`$ be any property that holds for a fraction of at least $`11/2^{\delta (n)}`$ of the elements of $`S`$. There is a constant $`c`$, such that every such $`P`$ holds simultaneously for every $`xS`$ with $`\delta (xS)\delta (n)K(PS)c`$.

###### Proof:

(i) There are only $`_{i=0}^{\mathrm{log}|S|\delta (n)}2^i`$ programs of length not greater than $`\mathrm{log}|S|\delta (n)`$ and there are $`|S|`$ elements in $`S`$.

(ii) Suppose $`P`$ does not hold for an object $`xS`$ and the randomness deficiency satisfies $`\delta (x|S)\delta (n)K(P|S)c`$. Then we can reconstruct $`x`$ from a description of $`P`$, which can use $`S`$, and $`x`$’s index $`j`$ in an effective enumeration of all objects for which $`P`$ doesn’t hold. There are at most $`|S|/2^{\delta (n)}`$ such objects by assumption, and therefore there are constants $`c_1,c_2`$ such that

$$K(x|S)\mathrm{log}j+c_1\mathrm{log}|S|\delta (n)+c_2.$$

Hence, by the assumption on the randomness deficiency of $`x`$, we find $`K(P|S)c_2c`$, which contradicts the necesssary nonnegativity of $`K(P|S)`$ if we choose $`c>c_2`$. ∎

###### Example II.4

Lossy Compression The function $`\beta _x(\alpha )`$ is relevant to lossy compression (used, for instance, to compress images). Assume we need to compress $`x`$ to $`\alpha `$ bits where $`\alpha K(x)`$. Of course this implies some loss of information present in $`x`$. One way to select redundant information to discard is as follows: Find a set $`Sx`$ with $`K(S)\alpha `$ and with small $`\delta (x|S)`$, and consider a compressed version $`S^{}`$ of $`S`$. To reconstruct an $`x^{}`$, a decompresser uncompresses $`S^{}`$ to $`S`$ and selects at random an element $`x^{}`$ of $`S`$. Since with high probability the randomness deficiency of $`x^{}`$ in $`S`$ is small, $`x^{}`$ serves the purpose of the message $`x`$ as well as does $`x`$ itself. Let us look at an example. To transmit a picture of “rain” through a channel with limited capacity $`\alpha `$, one can transmit the indication that this is a picture of the rain and the particular drops may be chosen by the receiver at random. In this interpretation, $`\beta _x(\alpha )`$ indicates how “random” or “typical” $`x`$ is with respect to the best model at complexity level $`\alpha `$—and hence how “indistinguishable” from the original $`x`$ the randomly reconstructed $`x^{}`$ can be expected to be. The relation of the structure function to lossy compression and rate-distortion theory is the subject of an upcoming paper by the authors. $`\mathrm{}`$

“Structure” function: The original Kolmogorov structure function  for data $`x`$ is defined as

$$h_x(\alpha )=\underset{S}{\mathrm{min}}\{\mathrm{log}|S|:Sx,K(S)\alpha \},$$
(II.8)
where $`Sx`$ is a contemplated model for $`x`$, and $`\alpha `$ is a nonnegative integer value bounding the complexity of the contemplated $`S`$’s. Clearly, this function is non-increasing and reaches $`\mathrm{log}|\{x\}|=0`$ for $`\alpha =K(x)+c_1`$ where $`c_1`$ is the number of bits required to change $`x`$ into $`\{x\}`$. The function can also be viewed as a constrained maximum likelihood (ML) estimator, a viewpoint that is more evident for its version for probability models, Figure 5 in Appendix B. For every $`Sx`$ we have

$$K(x)K(S)+\mathrm{log}|S|+O(1).$$
(II.9)
Indeed, consider the following *two-part code* for $`x`$: the first part is a shortest self-delimiting program $`p`$ of $`S`$ and the second part is $`\mathrm{log}|S|`$ bit long index of $`x`$ in the lexicographical ordering of $`S`$. Since $`S`$ determines $`\mathrm{log}|S|`$ this code is self-delimiting and we obtain (II.9) where the constant $`O(1)`$ is the length of the program to reconstruct $`x`$ from its two-part code. We thus conclude that $`K(x)\alpha +h_x(\alpha )+O(1)`$, that is, the function $`h_x(\alpha )`$ never decreases more than a fixed independent constant below the diagonal *sufficiency line* $`L`$ defined by $`L(\alpha )+\alpha =K(x)`$, which is a lower bound on $`h_x(\alpha )`$ and is approached to within a constant distance by the graph of $`h_x`$ for certain $`\alpha `$’s (for instance, for $`\alpha =K(x)+c_1`$). For these $`\alpha `$’s we have $`\alpha +h_x(\alpha )=K(x)+O(1)`$ and the associated model (witness for $`h_x(\alpha )`$) is called an optimal set for $`x`$, and its description of $`\alpha `$ bits is called a sufficient statistic. If no confusion can result we use these names interchangeably. The main properties of a sufficient statistic are the following: If $`S`$ is a sufficient statistic for $`x`$, then $`K(S)+\mathrm{log}|S|=K(x)+O(1)`$. That is, the two-part description of $`x`$ using the model $`S`$ and as data-to-model code the index of $`x`$ in the enumeration of $`S`$ in $`\mathrm{log}|S|`$ bits, is as concise as the shortest one-part code of $`x`$ in $`K(x)`$ bits. Since now $`K(x)K(x,S)+O(1)K(S)+K(x|S)+O(1)K(S)+\mathrm{log}|S|+O(1)K(x)+O(1)`$, using straightforward inequalities (for example, given $`Sx`$, we can describe $`x`$ self-delimitingly in $`\mathrm{log}|S|+O(1)`$ bits) and the sufficiency property, we find that $`K(x|S)=\mathrm{log}|S|+O(1)`$. Therefore, the randomness deficiency of $`x`$ in $`S`$ is constant, $`x`$ is a typical element for $`S`$, and $`S`$ is a model of best fit for $`x`$. The data item $`x`$ can have randomness deficiency about 0, and hence be a typical element for models $`S`$ that are not sufficient statistics. A sufficient statistic $`S`$ for $`x`$ has the additional property, apart from being a model of best fit, that $`K(x,S)=K(x)+O(1)`$ and therefore by (II.3) we have $`K(S|x^{})=O(1)`$: the sufficient statistic $`S`$ is a model of best fit that is almost completely determined by $`x`$. The sufficient statistic associated with the least such $`\alpha `$ is called the minimal sufficient statistic. For more details see  and Section V.

“Minimal Description Length” function: The length of the minimal two-part code for $`x`$ consisting of the model cost $`K(S)`$ and the length of the index of $`x`$ in $`S`$, in the model class of sets of given maximal Kolmogorov complexity $`\alpha `$, the complexity of $`S`$ upper bounded by $`\alpha `$, is given by the MDL function or constrained MDL estimator:

$$\lambda _x(\alpha )=\underset{S}{\mathrm{min}}\{\mathrm{\Lambda }(S):Sx,K(S)\alpha \},$$
(II.10)
where $`\mathrm{\Lambda }(S)=\mathrm{log}|S|+K(S)K(x)O(1)`$ is the total length of two-part code of $`x`$ with help of model $`S`$. Apart from being convenient for the technical analysis in this work, $`\lambda _x(\alpha )`$ is the celebrated two-part Minimum Description Length code length (Section V-B) as a function of $`\alpha `$, with the model class restricted to models of code length at most $`\alpha `$.

## III Overview of Results

### III-A Background and Related Work

There is no written version, apart from the few lines which we reproduced in Section I, of A.N. Kolmogorov’s initial proposal  for a non-probabilistic approach to Statistics and Model Selection. We thus have to rely on oral history, see Appendix A. There, we also describe an early independent related result of L.A. Levin . Related work on so-called “non-stochastic objects” (where $`h_x(\alpha )+\alpha `$ drops to $`K(x)`$ only for large $`\alpha `$) is . In 1987, , V.V. V’yugin established that, for $`\alpha =o(|x|)`$, the randomness deficiency function $`\beta _x(\alpha )`$ can assume all possible shapes (within the obvious constraints). In the survey  of Kolmogorov’s work in information theory, the authors preferred to mention $`\beta _x(\alpha )`$, because it by definition optimizes “best fit,” rather than $`h_x(\alpha )`$ of which the usefulness and meaningfulness was mysterious. But Kolmogorov had a seldom erring intuition: we will show that his original proposal $`h_x`$ in the proper sense incorporates all desirable properties of $`\beta _x(\alpha )`$, and in fact is superior. In  a notion of “algorithmic sufficient statistics”, derived from Kolmogorov’s structure function, is suggested as the algorithmic approach to the probabilistic notion of sufficient statistic  that is central in classical statistics. The paper  investigates the algorithmic notion in detail and formally establishes such a relation. The algorithmic (minimal) sufficient statistic is related in  to the “minimum description length” principle  in statistics and inductive reasoning. Moreover,  observed that $`\beta _x(\alpha )h_x(\alpha )+\alpha K(x)+O(1)`$, establishing a one-sided relation between (II.7) and (II.8), and the question was raised whether the converse holds.

### III-B This Work

When we compare statistical hypotheses $`S_0`$ and $`S_1`$ to explain data $`x`$ of length $`n`$, we should take into account three parameters: $`K(S),K(xS)`$, and $`\mathrm{log}|S|`$. The first parameter is the simplicity of the theory $`S`$ explaining the data. The difference $`\delta (x|S)=\mathrm{log}|S|K(xS)`$ (the randomness deficiency) shows how typical the data is with respect to $`S`$. The sum $`\mathrm{\Lambda }(S)=K(S)+\mathrm{log}|S|`$ tells us how short the two part code of the data using theory $`S`$ is, consisting of the code for $`S`$ and a code for $`x`$ simply using the worst-case number of bits possibly required to identify $`x`$ in the enumeration of $`S`$. This second part consists of the full-length index ignoring savings in code length using possible non-typicality of $`x`$ in $`S`$ (like being the first element in the enumeration of $`S`$). We would like to define that $`S_0`$ is not worse than $`S_1`$ (as an explanation for $`x`$), in symbols: $`S_0S_1`$, if

* $`K(S_0)K(S_1)`$;
* $`\delta (x|S_0)\delta (x|S_1)`$; and
* $`\mathrm{\Lambda }(S_0)\mathrm{\Lambda }(S_1)`$.

To be sure, this is not equivalent to saying that $`K(S_0)K(S_1),\delta (x|S_0)\delta (x|S_1),\mathrm{log}|S_0|\mathrm{log}|S_1|`$. (The latter relation is stronger in that it implies $`S_0S_1`$ but not vice versa.) The algorithmic statistical properties of a data string $`x`$ are fully represented by the set $`A_x`$ of all triples $`K(S),\delta (x|S),\mathrm{\Lambda }(S)`$ such that $`Sx`$, together with a component wise order relation $``$ on the elements those triples. The complete characterization of how this set may look like (with $`O(\mathrm{log}n)`$-accuracy) is now known in the following sense.

Our results (Theorems IV.4, IV.8, IV.11) describe completely (with $`O(\mathrm{log}n)`$-accuracy) possible shapes of the closely related set $`B_x`$ consisting of all triples $`\alpha ,\beta ,\lambda `$ such that there is a set $`Sx`$ with $`K(S)\alpha `$, $`\delta (xS)\beta `$, $`\mathrm{\Lambda }(S)\lambda `$. That is, $`A_xB_x`$ and $`A_x`$ and $`B_x`$ have the same minimal triples. Hence, we can informally say that our results describe completely possible shapes of the set of triples $`K(S),\delta (x|S),\mathrm{\Lambda }(S)`$ for non-improvable hypotheses $`S`$ explaining $`x`$. For example up to $`O(\mathrm{log}n)`$ accuracy, and denoting $`k=K(x)`$ and $`n=|x|`$:

(i) For every minimal triple $`(\alpha ,\beta ,\gamma )`$ in $`B_x`$ we have $`0\alpha k`$, $`0\beta ,\beta +k=\gamma n`$.

(ii) There is a triple of the form $`(\alpha _0,0,k)`$ in $`B_x`$ (the minimal such $`\alpha _0`$ is the complexity of the minimal sufficient statistic for $`x`$). This property allows us to recover the complexity $`k`$ of $`x`$ from $`B_x`$.

(iii) There is a triple of the form $`(0,\lambda _0k,\lambda _0)`$ in $`B_x`$ with $`\lambda _0n`$.

Previously, a limited characterization was obtained by V’yugin  for the possible shapes of the projection of $`B_x`$ on $`\alpha ,\beta `$-coordinates but only for the case when $`\alpha =o(K(x))`$. Our results describe possible shapes of the entire set $`B_x`$ for the full domain of $`\alpha `$ (with $`O(\mathrm{log}n)`$-accuracy). Namely, let $`f`$ be a non-increasing integer valued function such that $`f(0)n`$, $`f(i)=k`$ for all $`ik`$ and

$$\stackrel{~}{B}_f=\{\alpha ,\beta ,\lambda 0\alpha ,f(\alpha )\lambda ,f(\alpha )k\beta \}.$$

For every $`x`$ of length $`n`$ and complexity $`k`$ there is $`f`$ such that

$$\stackrel{~}{B}_f+uB_x\stackrel{~}{B}_fu$$
(III.1)
where $`u=c\mathrm{log}n,c\mathrm{log}n,c\mathrm{log}n`$ for some universal constant $`c`$. Conversely, for every $`kn`$ and every such $`f`$ there is $`x`$ of length $`n`$ such that (III.1) holds for $`u=c\mathrm{log}K(n,f,k),c\mathrm{log}K(n,f,k),c\mathrm{log}K(n,f,k)`$ . Our results imply that the set $`B_x`$ is not computable given $`x,k`$ but is computable given $`x,k`$ and $`\alpha _0`$, the complexity of minimal sufficient statistic.

###### Remark III.1

There is also the fourth important parameter, $`K(Sx^{})`$ reflecting the determinacy of model $`S`$ by the data $`x`$. However, the equality $`\mathrm{log}|S|+K(S)K(x)=K(Sx^{})+\delta (xS)+O(1)`$ shows that this parameter can be expressed in $`\alpha ,\beta ,h`$. The main result (III.2) establishes that $`K(Sx^{})`$ is logarithmic for every set $`S`$ witnessing $`h_x(\alpha )`$. This also shows that there are at most polynomially many such sets. $`\mathrm{}`$

### III-C Technical Details

The results are obtained by analysis of the relations between the structure functions. The most fundamental result in this paper is the equality

$$\beta _x(\alpha )=h_x(\alpha )+\alpha K(x)=\lambda _x(\alpha )K(x)$$
(III.2)
which holds within additive terms, that are logarithmic in the length of the string $`x`$, in argument and value. Every set $`S`$ that witnesses the value $`h_x(\alpha )`$ (or $`\lambda _x(\alpha )`$), also witnesses the value $`\beta _x(\alpha )`$ (but not vice versa). It is easy to see that $`h_x(\alpha )`$ and $`\lambda _x(\alpha )`$ are upper semi-computable (Definition VII.1); but we show that $`\beta _x(\alpha )`$ is neither upper nor lower semi-computable. A priori there is no reason to suppose that a set that witnesses $`h_x(\alpha )`$ (or $`\lambda _x(\alpha )`$) also witnesses $`\beta _x(\alpha )`$, for every $`\alpha `$. But the fact that they do, vindicates Kolmogorov’s original proposal and establishes $`h_x`$’s pre-eminence over $`\beta _x`$. The result can be taken as a foundation and justification of common statistical principles in model selection such as maximum likelihood or MDL ( and our Sections V-B and V-C). We have also addressed the fine structure of the shape of $`h_x`$ (especially for $`\alpha `$ below the minimal sufficient statistic complexity) and a uniform (noncomputable) construction for the structure functions.

The possible (coarse) shapes of the functions $`\lambda _x,h_x`$ and $`\beta _x`$ are examined in Section IV. Roughly stated: The structure functions $`\lambda _x,h_x`$ and $`\beta _x`$ can assume all possible shapes over their full domain of definition (up to additive logarithmic precision in both argument and value). As a consequence, so-called “non-stochastic” strings $`x`$ for which $`h_x(\alpha )+\alpha `$ stabilize on $`K(x)`$ for large $`\alpha `$ are common. This improves and extends V’yugin’s result  above; it also improves the independent related result of L.A. Levin  in Appendix A; and, applied to “snooping curves” extends a recent result of V’yugin, , in Section V-A. The fact that $`\lambda _x`$ can assume all possible shapes over its full domain of definition establishes the significance of (III.2), since it shows that $`\lambda _x(\alpha )K(x)`$ indeed happens for some $`x,\alpha `$ pairs. In that case the more or less easy fact that $`\beta _x(\alpha )=0`$ for $`\lambda _x(\alpha )=K(x)`$ is not applicable, and a priori there is no reason for (III.2): Why should minimizing a set containing $`x`$ plus the set’s description length also minimize $`x`$’s randomness deficiency in the set? But (III.2) shows that it does! We determined the (fine) details of the function shapes in Section VI. (Non-)computability properties are examined in Section VII, incidentally proving a to our knowledge first natural example, $`\beta _x`$, of a function that is not semi-computable but computable with an oracle for the halting problem. In Section VIII, we exhibit a uniform construction for sets realizing $`h_x(\alpha )`$ for all $`\alpha `$.

### III-D Probability Models

Following Kolmogorov we analyzed a canonical setting where the models are finite sets. As Kolmogorov himself pointed out, this is no real restriction: the finite sets model class is equivalent, up to a logarithmic additive term, to the model class of probability density functions, as studied in , and the model class of total recursive functions, as studied in , see Appendix B.

### III-E All Stochastic Properties of the Data

The result (III.2) shows that the function $`h_x(\alpha )`$ yields all stochastic properties of data $`x`$ in the following sense: for every $`\alpha `$ the class of models of maximal complexity $`\alpha `$ has a best model with goodness-of-fit determined by the randomness deficiency $`\beta _x(\alpha )=h_x(\alpha )+\alpha K(x)`$—the equality being taken up to logarithmic precision. For example, for some value $`\alpha _0`$ the minimal randomness deficiency $`\beta _x(\alpha )`$ may be quite large for $`\alpha <\alpha _0`$ (so the best model in that class has poor fit), but an infinitessimal increase in model complexity may cause $`\beta _x(\alpha )`$ to drop to zero (and hence the marginally increased model class now has a model of perfect fit), see Figure 1. Indeed, the structure function quantifies the best possible fit for a model in classes of every complexity.

### III-F Used Mathematics

Kolmogorov’s proposal for a nonprobabilistic statistic is combinatorial and algorithmic, rather than probabilistic. Similar to other recent directions in information theory and statistics, this involves notions and proof techniques from computer science theory, rather than from probability theory. But the contents matter and results are about traditional statistic- and information theory notions like model selection, information and compression; consequently the treatment straddles fields that are not traditionally intertwined. For convenience of the reader who is unfamiliar with algorithmical notions and methods we have taken pains to provide intuitive explanations and interpretations. Moreover, we have delegated almost all proofs to Appendix C, and all precise formulations and proofs of the (non)computability and (non)approximability of the structure functions to Appendix D.

## IV Coarse Structure

In classical statistics, unconstrained maximal likelihood is known to perform badly for model selection, because it tends to want the most complex models possible. A precise quantification and explanation of this phenomenon, in the complexity-constrained model class setting, is given in this section. It is easy to see that unconstrained maximization will result in the singleton set model $`\{x\}`$ of complexity about $`K(x)`$. We will show that the structure function $`h_x(\alpha )`$ tells us all stochastic properties of data $`x`$. From complexity 0 up to the complexity where the graph hits the sufficiency line, the best fitting models do not represent all meaningful properties of $`x`$. The distance between $`h_x(\alpha )`$ and the sufficiency line $`L(\alpha )=K(x)\alpha `$, is a measure, expressed by $`\beta _x(\alpha )`$, of how far the best fitting model at complexity $`\alpha `$ falls short of a sufficient fitting model. The least complex sufficient fitting model, the minimal sufficient statistic, occurs at complexity level $`\alpha _0`$ where $`h_x`$ hits the sufficiency line. There, $`h_x(\alpha _0)+\alpha _0=K(x)`$. The minimal sufficient statistic model expresses all meaningful information in $`x`$, and its complexity is the number of bits of meaningful information in the data $`x`$. The remainder $`h_x(\alpha _0)`$ bits of the $`K(x)`$ bits of information in data $`x`$ is the “noise,” the meaningless randomness, contained in the data. When we consider the function $`h_x`$ at still higher complexity levels $`\alpha >\alpha _0`$, the function $`h_x(\alpha )`$ hugs the sufficiency line $`L(\alpha )=K(x)\alpha `$, which means that $`h_x(\alpha )+\alpha `$ stays constant at $`K(x)`$. The best fitting models at these complexities start to model more and more noise, $`h_x(\alpha )h_x(\alpha _0)=\alpha _0\alpha `$ bits, in the data $`x`$: the added complexity $`\alpha _0\alpha `$ in the sufficient statistic model at complexity level $`\alpha `$ over that of the minimal sufficient statistic at complexity level $`\alpha _0`$ is completely used to model increasing part of the noise in the data. The worst overfitting occurs when we arrive at complexity $`K(x)`$, at which point we model all noise in the data apart from the meaningful information. Thus, our approach makes the fitting process of constrained maximum likelihood, first underfitting at low complexity levels of the models considered, then the complexity level of optimal fit (the minimal sufficient statistic), and subsequently the overfitting at higher levels of complexity of models, completely and formally explicit in terms of fixed data and individual models.

### IV-A All Shapes are Possible

Let $`\beta _x(\alpha )`$ be defined as in (II.7) and $`h_x(\alpha )`$ be defined as in (II.8). Both functions are 0 ($`\beta _x(\alpha )`$ may be $`O(1)`$) for all $`\alpha K(x)+c_0`$ where $`c_0`$ is a constant. We represent the coarse shape of these functions for different $`x`$ by functions characteristic of that shape. Informally, $`g`$ represents $`f`$ means that the graph of $`f`$ is contained in a strip of logarithmic (in the length $`n`$ of $`x`$) width centered on the graph of $`g`$, Figure 2.

Intuition: $`f`$ follows $`g`$ up to a prescribed precision.

For formal statements we rely on the notion in Definition IV.1. Informally, we obtain the following results ($`x`$ is of length $`n`$ and complexity $`K(x)=k`$):

* Every non-increasing function $`\beta `$ represents $`\beta _x`$ for some $`x`$, and for every $`x`$ the function $`\beta _x`$ is represented by some $`\beta `$, provided $`\beta (k)=0`$, $`\beta (0)nk`$.
* Every function $`h`$, with non-increasing $`h(\alpha )+\alpha `$, represents $`h_x`$ for some $`x`$, and for every $`x`$ the function $`h_x`$ is represented by some $`h`$ as above, provided $`h(k)=0`$, $`h(0)n`$ (and by the non-increasing property $`h(0)k`$).
* $`h_x(\alpha )+\alpha `$ represents $`\beta _x(\alpha )+k`$, and conversely, for every $`x`$.
* For every $`x`$ and $`\alpha `$, every minimal size set $`Sx`$ of complexity at most $`\alpha ^{}=\alpha +O(\mathrm{log}n)`$, has randomness deficiency $`\beta _x(\alpha ^{})\delta (xS)\beta _x(\alpha )+O(\mathrm{log}n)`$.

To provide precise statements we need a definition.

###### Definition IV.1

Let $`f,g`$ be functions defined on $`\{0,1,\mathrm{},k\}`$ with values in $`\{\mathrm{}\}`$. We say that $`f`$ is $`(\epsilon (i),\delta (i))`$-close to $`g`$ (in symbols: $`f=(g)`$) if

$`f(i)`$ $`\mathrm{min}\{g(j):j[\epsilon (0),k],|ji|\epsilon (i)\}\delta (i)\},`$
$`f(i)`$ $`\mathrm{max}\{g(j):j[\epsilon (0),k],|ji|\epsilon (i)\}+\delta (i)\}`$
for every $`i[\epsilon (0),k]`$. If $`f=(g)`$ and $`g=(f)`$ we write $`fg`$.

Here $`\epsilon (i),\delta (i)`$ are small values like $`O(\mathrm{log}n)`$ when we consider data $`x`$ of length $`n`$. Note that this definition is not symmetric and allows $`f(i)`$ to have arbitrary values for $`i[0,\epsilon (0))`$. However, it is transitive in the following sense: if $`f`$ is $`(\epsilon _1(i),\delta _1(i))`$-close to $`g`$ and $`g`$ is $`(\epsilon _2(i),\delta _2(i))`$-close to $`h`$ then $`f`$ is $`(\epsilon _1(i)+\epsilon _2(i),\delta _1(i)+\delta _2(i))`$-close to $`h`$. If $`f=(g)`$ and $`g`$ is linear continuous, meaning that $`|g(i)g(j)|c|ij|`$ for some constant $`c`$, then the difference between $`f(i)`$ and $`g(i)`$ is bounded by $`c\epsilon (i)+\delta (i)`$ for every $`\epsilon (0)ik`$.

This notion of closeness, if applied unrestricted, is not always meaningful. For example, take as $`g`$ the function taking value $`n`$ for all even $`i[0,k]`$ and 0 for all odd $`i[0,k]`$. Then for every function $`f`$ on $`[0,k]`$ with $`f(i)[0,n]`$ we have $`f=(g)`$ for $`\epsilon =1`$, $`\delta =0`$. But if $`f=(g)`$ and $`g`$ is non-increasing then $`g`$ indeed gives much information about $`f`$.

It is instructive to consider the following example. Let $`g(i)`$ be equal to $`2ki`$ for $`i=0,1,\mathrm{},\frac{k}{2}1`$ and to $`ki`$ for $`i=\frac{k}{2},\mathrm{},k`$. Let $`\epsilon (i),\delta (i)`$ be constant. Then a function $`f=(g)`$ may take every value for $`i[0,\epsilon )`$, every value in $`[2ki2\delta ,2ki+2\delta ]`$ for $`i[\epsilon ,\frac{k}{2}\delta ]`$, every value in $`[ki\delta ,2ki+\delta ]`$ for $`i(\frac{k}{2}\delta ,\frac{k}{2}+\delta ]`$, and every value in $`[ki2\delta ,ki+2\delta ]`$ for $`i(\frac{k}{2}+\delta ,k]`$ (see Figure 2). Thus the point $`\frac{k}{2}`$ of discontinuity of $`g`$ gives an interval of size $`2\delta `$ of large ambiguity of $`f`$. Loosely speaking the graph of $`f`$ can be any function contained in the strip of radius $`2\delta `$ whose middle line is the graph of $`g`$. For technical reasons it is convenient to use, in place of $`h_x`$, the MDL function $`\lambda _x`$ (II.10).

The definition of $`\lambda _x`$ immediately implies the following properties: $`\lambda _x(\alpha )`$ is non-increasing, $`\lambda _x(\alpha )K(x)O(1)`$ for all $`\alpha `$.

The next lemma shows that properties of $`\lambda _x`$ translate directly into properties of $`h_x`$ since $`h_x(\alpha )`$ is always “close” to $`\lambda _x(\alpha )\alpha `$.

###### Lemma IV.2

For every $`x`$ we have $`\lambda _x(\alpha )h_x(\alpha )+\alpha \lambda _x(\alpha )+K(\alpha )+O(1)`$ for all $`\alpha `$. Hence $`\lambda _x(\alpha )h_x(\alpha )+\alpha `$ for $`\epsilon =0`$, $`\delta =K(\alpha )+O(1)`$.

Intuition: The functions $`h_x(\alpha )+\alpha `$ (the ML code length plus the model complexity) and $`\lambda _x(\alpha )`$ (the MDL code length) are essentially the same function.

###### Remark IV.3

The lemma implies that the same set witnessing $`h_x(\alpha )`$ also witnesses $`\lambda _x(\alpha )`$ up to an additive term of $`K(\alpha )`$. The converse is only true for the smallest cardinality set witnessing $`\lambda _x(\alpha )`$. Without this restriction a counter example is: for random $`x\{0,1\}^n`$ the set $`S=\{0,1\}^n`$ witnesses $`\lambda _x(\frac{n}{2})=n+O(K(n))`$ but does not witness $`h_x(\frac{n}{2})=\frac{n}{2}+O(K(n))`$. (If $`\lambda _x(\alpha )=K(x)`$, then every set of complexity $`\alpha ^{}\alpha `$ witnessing $`\lambda _x(\alpha ^{})=K(x)`$ also witnesses $`\lambda _x(\alpha )=K(x)`$.) $`\mathrm{}`$

The next two theorems state the main results of this work in a precise form. By $`K(i,n,\lambda )`$ we mean the minimum length of a program that outputs $`n,i`$, and computes $`\lambda (j)`$ given any $`j`$ in the domain of $`\lambda `$. We first analyze the possible shapes of the structure functions.

###### Theorem IV.4

(i) For every $`n`$ and every string $`x`$ of length $`n`$ and complexity $`k`$ there is an integer valued non-increasing function $`\lambda `$ defined on $`[0,k]`$ such that $`\lambda (0)n`$, $`\lambda (k)=k`$ and $`\lambda _x=(\lambda )`$ for $`\epsilon =\delta =K(n)+O(1)`$.

(ii) Conversely, for every $`n`$ and non-increasing integer valued function $`\lambda `$ whose domain includes $`[0,k]`$ and such that $`\lambda (0)n`$ and $`\lambda (k)=k`$, there is $`x`$ of length $`n`$ and complexity $`k\pm (K(k,n,\lambda )+O(1))`$ such that $`\lambda _x=(\lambda )`$ for $`\epsilon =\delta =K(i,n,\lambda )+O(1)`$.

Intuition: The MDL code length $`\lambda _x`$, and therefore by Lemma IV.2 also the original structure function $`h_x`$, can assume essentially every possible shape as a function of the contemplated maximal model complexity.

###### Remark IV.5

The theorem implies that for every function $`h(i)`$ defined on $`[0,k]`$ such that the function $`\lambda (i)=h(i)+i`$ satisfies the conditions of item (ii) there is an $`x`$ such that $`h_x(i)=(h(i))`$ with $`\epsilon =\delta =O(K(i,n,h))`$. $`\mathrm{}`$

###### Remark IV.6

The proof of the theorem shows that for every function $`\lambda (i)`$ satisfying the conditions of item (ii) there is $`x`$ such that $`\lambda _x(in,\lambda )=(\lambda (i))`$ with $`\epsilon =\delta =K(i)+O(1)`$ where the conditional structure function $`\lambda _x(iy)=\mathrm{min}_S\{K(Sy)+\mathrm{log}|S|:Sx,K(Sy)i\}`$. Consequently, for every function $`h(i)`$ such that the function $`\lambda (i)=h(i)+i`$ satisfies the conditions of item (ii) there is an $`x`$ such that $`h_x(in,h)=(h(i))`$ with $`\epsilon =\delta =O(K(i))`$ where the conditional structure function $`h_x(iy)=\mathrm{min}_S\{\mathrm{log}|S|:Sx,K(Sy)i\}`$. $`\mathrm{}`$

###### Remark IV.7

In the proof of Item (ii) of the theorem we can consider every finite set $`U`$ with $`|U|2^n`$ in place of the set $`A`$ of all strings of length $`n`$. Then we obtain a string $`xU`$ such that $`\lambda _x=(\lambda )`$ with $`\epsilon (i)=\delta (i)=K(i,U,\lambda )`$. $`\mathrm{}`$

### IV-B Selection of Best Fitting Model

Recall that in classical statistics a major issue is whether a given model selection method works well if the “right” model is in the contemplated model class, and what model the method selects if the “right” model is outside the model class. We have argued earlier that the best we can do is to look for the “best fitting” model. But both “best fitting” and “best fitting in a constrained model class” are impossible to express classically for individual models and data. Instead, one focusses on probabilistic definitions and analysis. It is precisely these issues that can be handled in the Kolmogorov complexity setting.

For the complexity levels $`\alpha `$ at which $`h_x(\alpha )`$ coincides with the diagonal sufficiency line $`L(\alpha )=K(x)\alpha `$, the model class contains a “sufficient” (the “best fitting”) model.

For the complexity levels $`\alpha `$ at which $`h_x(\alpha )`$ is above the sufficiency line, the model class does not contain a “sufficient” model. However, our results say that $`h_x(\alpha )L(\alpha )`$ equals the minimal randomness deficiency that can be achieved by a model of complexity $`\alpha `$, and hence quantifies rigorously the properties of the data $`x`$ such a model can represent, that is, the level of “fitness” of the best model in the class.

Semi-computing $`h_x(\alpha )`$ from above, together with the model wittnessing this value, automatically yields the objectively most fitting model in the class, that is, the model that is closest to the “true” model according to an objective measure of representing most properties of data $`x`$.

The following central result of this paper shows that the $`\lambda _x`$ (equivalently $`h_x`$, by Lemma IV.2) and $`\beta _x`$ can be expressed in one another but for a logarithmic additive error.

###### Theorem IV.8

For every $`x`$ of length $`n`$ and complexity $`k`$ it holds $`\beta _x(\alpha )+k\lambda _x(\alpha )`$ for $`\epsilon =\delta =O(\mathrm{log}n)`$.

Intuition: A model achieving the MDL code length $`\lambda _x(\alpha )`$, or the ML code length $`h_x(\alpha )`$, essentially achieves the best possible fit $`\beta _x(\alpha )`$.

###### Corollary IV.9

For every $`x`$ of length $`n`$ and complexity $`kn`$ there is a non-increasing function $`\beta `$ such that $`\beta (0)nk`$, $`\beta (k)=0`$ and $`\beta _x=(\beta )`$ for $`\epsilon ,\delta =O(\mathrm{log}n)`$. Conversely, for every non-increasing function $`\beta `$ such that $`\beta (0)nk`$, $`\beta (k)=0`$ there is $`x`$ of length $`n`$ and complexity $`k\pm \delta `$ such that $`\beta _x=(\beta )`$ for $`\epsilon =\delta =O(\mathrm{log}n)+K(\beta )`$.

###### Proof:

The first part is more or less immediate. Or use the first part of Theorem IV.4 and then let $`\beta (i)=\lambda (i)k`$. To prove the second part, use the second part of Theorem IV.8, and the second part of Theorem IV.4 with $`\lambda (i)=\beta (i)+k`$. ∎

###### Remark IV.10

From the proof of Theorem IV.8 we see that for every finite set $`Sx`$, of complexity at most $`\alpha +O(\mathrm{log}n)`$ and minimizing $`\mathrm{\Lambda }(S)`$, we have $`\delta (xS)\beta _x(\alpha )+O(\mathrm{log}n)`$. Ignoring $`O(\mathrm{log}n)`$ terms, at every complexity level, every best hypothesis at this level with respect to $`\mathrm{\Lambda }(S)`$ is also a best one with respect to typicality. This explains why it is worthwhile to find shortest two-part descriptions for given data $`x`$: this is the single known way to find an $`Sx`$ with respect to which $`x`$ is as typical as possible at that complexity level. Note that the set $`\{x,S,\beta xS,\delta (xS)<\beta \}`$ is not enumerable so we are not able to generate such $`S`$’s directly (Section VII).

The converse is not true: not every hypothesis, consisting of a finite set, witnessing $`\beta _x(\alpha )`$ also witnesses $`\lambda _x(\alpha )`$ or $`h_x(\alpha )`$. For example, let $`x`$ be a string of length $`n`$ with $`K(x)n`$. Let $`S_1=\{0,1\}^n\{y\}`$ where $`y`$ is a string of length $`\frac{n}{2}`$ such that $`K(x,y)\frac{3n}{2}`$ and let $`S_2=\{0,1\}^n`$. Then both $`S_1,S_2`$ witness $`\beta _x(\frac{n}{2}+O(\mathrm{log}n))=O(1)`$ but $`\mathrm{\Lambda }(S_1)=\frac{3n}{2}+O(\mathrm{log}n)\lambda _x(\frac{n}{2}+O(\mathrm{log}n))=n+O(\mathrm{log}n)`$ while $`\mathrm{log}|S_2|=nh_x(\frac{n}{2}+O(\mathrm{log}n))=\frac{n}{2}+O(\mathrm{log}n)`$. $`\mathrm{}`$

However, for every $`\alpha `$ such that $`\lambda _x(i)`$ decreases when $`i\alpha `$ with $`i\alpha `$, a witness set for $`\beta _x(\alpha )`$ is also a witness set for $`\lambda _x(\alpha )`$ and $`h_x(\alpha )`$. We will call such $`\alpha `$ critical (with respect to $`x`$): these are the model complexities at which the two-part MDL code-length decreases, while it is stable in between such critical points. The next theorem shows, for critical $`\alpha `$, that for every $`Ax`$ with $`K(A)\alpha `$ and $`\delta (xA)\beta _x(\alpha )`$, we have $`\mathrm{log}|A|h_x(\alpha )`$ and $`\mathrm{\Lambda }(A)\lambda _x(\alpha )`$. More specifically, if $`K(A)\alpha `$ and $`\delta (xA)\beta _x(\alpha )`$ but $`\mathrm{\Lambda }(A)\lambda _x(\alpha )`$ or $`\mathrm{log}|A|h_x(\alpha )`$ then there is $`Sx`$ with $`K(S)\alpha `$ and $`\mathrm{\Lambda }(S)\lambda _x(\alpha )`$.

###### Theorem IV.11

For all $`Ax`$ there is $`Sx`$ such that $`\mathrm{\Lambda }(S)\lambda _x(\alpha )+(\delta (x|A)\beta _x(\alpha ))`$, $`K(S)K(A)+(\lambda _x(\alpha )\mathrm{\Lambda }(A))+(\delta (x|A)\beta _x(\alpha ))`$, and $`K(S)\alpha +(h_x(\alpha )\mathrm{log}|A|)+(\delta (x|A)\beta _x(\alpha ))`$ where all inequalities hold up to $`O(\mathrm{log}\mathrm{\Lambda }(A))`$ additive term.

Intuition: Although models of best fit (witnessing $`\beta _x(\alpha )`$) do not necessarily achieve the MDL code length $`\lambda _x(\alpha )`$ or the ML code length $`h_x(\alpha )`$, they do so at the model complexities where the MDL code length decreases, and, equivalently, the ML code length decreases at a slope of more than $`1`$.

### IV-C Invariance under Recoding of Data

In what sense is the structure function invariant under recoding of the data? Osamu Watanabe suggested the example of replacing the data $`x`$ by a shortest program $`x^{}`$ for it. Since $`x^{}`$ is incompressible it is a typical element of the set of all strings of length $`|x^{}|=K(x)`$, and hence $`h_x^{}(\alpha )`$ drops to the sufficiency line $`L(\alpha )=K(x)\alpha `$ already for some $`\alpha K(K(x))`$, so almost immediately (and it stays within logarithmic distance of that line henceforth). That is, $`h_x^{}(\alpha )=K(x)\alpha `$ up to logarithmic additive terms in argument and value, irrespective of the (possibly quite different) shape of $`h_x`$. Since the Kolmogorov complexity function $`K(x)=|x^{}|`$ is not recursive, , the recoding function $`f(x)=x^{}`$ is also not recursive. Moreover, while $`f`$ is one-one and total it is not onto. But it is the partiality of the inverse function (not all strings are shortest programs) that causes the collapse of the structure function. If one restricts the finite sets containing $`x^{}`$ to be subsets of $`\{y^{}:y\{0,1\}^{}\}`$, then the resulting structure function $`h_x^{}`$ is within a logarithmic strip around $`h_x`$. However, the structure function is invariant under “proper” recoding of the data.

###### Lemma IV.12

Let $`f`$ be a recursive permutation of the set of finite binary strings (one-one, total, and onto). Then, $`h_{f(x)}=(h_x)`$ for $`\epsilon ,\delta =K(f)+O(1)`$.

###### Proof:

Let $`Sx`$ be a witness of $`h_x(\alpha )`$. Then, $`S_f=\{f(y):yS\}`$ satisfies $`K(S_f)\alpha +K(f)+O(1)`$ and $`|S_f|=|S|`$. Hence, $`h_{f(x)}(\alpha +K(f)+O(1))h_x(\alpha )`$. Let $`Rf(x)`$ be a witness of $`h_{f(x)}(\alpha )`$. Then, $`R_{f^1}=\{f^1(y):yR\}`$ satisfies $`K(R_{f^1})\alpha +K(f)+O(1)`$ and $`|R_{f^1}|=|R|`$. Hence, $`h_x(\alpha +K(f)+O(1))h_{f(x)}(\alpha )`$ (since $`K(f^1)=K(f)+O(1)`$). ∎

### IV-D Reach of Results

In Kolmogorov’s initial proposal, as in this work, models are finite sets of finite binary strings, and the data is one of the strings (all discrete data can be binary encoded). The restriction to finite set models is just a matter of convenience: the main results generalize to the case where the models are arbitrary computable probability density functions, , and to the model class consisting of arbitrary total recursive functions, . We summarize the proofs of this below. Since our results hold only within additive precision that is logarithmic in the binary length of the data, and the equivalences between the model classes hold up to the same precision, the results hold equally for the more general model classes.

The generality of the results are at the same time a restriction. In classical statistics one is commonly interested in model classes that are partially poorer and partially richer than the ones we consider. For example, the class of Bernoulli processes, or $`k`$-state Markov chains, is poorer than the class of computable probability density functions of moderate maximal Kolmogorov complexity $`\alpha `$, in that the latter may contain functions that require far more complex computations than the rigid syntax of the former classes allows. Indeed, the class of computable probability density functions of even moderate complexity allows implementation of a function mimicking a universal Turing machine computation. On the other hand, even the lowly Bernoulli process can be equipped with a noncomputable real bias in $`(0,1)`$, and hence the generated probability density function over $`n`$ trials is not a computable function. This incomparability of the here studied algorithmic model classes, and the traditionally studied statistical model classes, means that the current results cannot be directly transplanted to the traditional setting. They should be regarded as pristine truths that hold in a platonic world that can be used as guideline to develop analogues in model classes that are of more traditional concern, as in . The questions to be addressed are: Can these platonic truths say anything usable? If we restrict ourselves to statistical model classes, how far from optimal are we? Note that in themselves the finite set models are not really that far from classical statistical models.

## V Prediction and Model Selection

### V-A Best Prediction Strategy

In  the notion of a snooping curve $`L_x(\alpha )`$ of $`x`$ was introduced, expressing the minimal logarithmic loss in predicting the consecutive elements of a given individual string $`x`$, in each prediction using the preceding sequence of elements, by the best prediction strategy of complexity at most $`\alpha `$.

Intuition: The snooping curve quantifies the quality of the best predictor for a given sequence at every possible predictor-complexity.

Formally, $`L_x(\alpha )=\underset{K(P)\alpha }{\mathrm{min}}\mathrm{Loss}_P(x)`$. The minimum is taken over all prediction strategies $`P`$ of complexity at most $`\alpha `$. A prediction strategy $`P`$ is a mapping from the set of strings of length less than $`|x|`$ into the set of rational numbers in the segment $`[0,1]`$. The value $`P(x_1\mathrm{}x_i)`$ is regarded as our belief (or probability) that $`x_{i+1}=1`$ after we have observed $`x_1,\mathrm{},x_i`$. If the actual bit $`x_{i+1}`$ is 1 the strategy suffers the loss $`\mathrm{log}p`$ otherwise $`\mathrm{log}(1p)`$. The strategy is a finite object and $`K(P)`$ may by defined as the complexity of this object, or as the minimum size of a program that identifies $`n=|x|`$ and given $`y`$ finds $`P(y)`$. The notation $`\mathrm{Loss}_P(x)`$ indicates the total loss of $`P`$ on $`x`$, i.e. the sum of all $`n`$ losses: $`\mathrm{Loss}_P(x)=_{i=0}^{|x|1}(\mathrm{log}|P(x_1\mathrm{}x_i)1+x_{i+1}|)`$. Thus, the snooping curve $`L_x(\alpha )`$ gives the minimal loss suffered on all of $`x`$ by a prediction strategy, as a function of the complexity at most $`\alpha `$ of the contemplated class of prediction strategies. The question arises what shapes these functions can have—for example, whether there can be sharp drops in the loss for only minute increases in complexity of prediction strategies.

A result of  describes possible shapes of $`L_x`$ but only for $`\alpha =o(n)`$ where $`n`$ is the length of $`x`$. Here we show that for every function $`L`$ and every $`kn`$ there is a data sequence $`x`$ such that $`L_x(\alpha \pm O(\mathrm{log}n))=L(\alpha )\pm O(\mathrm{log}n)`$, provided $`L(0)n`$, $`L(\alpha )+\alpha `$ is non-increasing on $`[0,k]`$, and $`L(\alpha )=0`$ for $`\alpha k`$.

###### Lemma V.1

$`L_x(\alpha \pm O(\mathrm{log}n))=h_x(\alpha \pm O(\mathrm{log}n))`$ for every $`x`$ and $`\alpha `$. Thus, Lemma IV.2 and Theorem IV.4 describes also the coarse shape of all possible snooping curves.

###### Proof:

($``$) A given finite set $`A`$ of binary strings of length $`n`$ can be identified with the following prediction strategy $`P`$: Having read the prefix $`y`$ of $`x`$ it outputs $`p=|A_{y1}|/|A_y|`$ where $`A_y`$ stands for the number of strings in $`A`$ having prefix $`y`$.

It is easily seen, by induction, that $`\mathrm{Loss}_P(y)=\mathrm{log}(|A|/|A_y|)`$ for every $`y`$. Therefore, $`\mathrm{Loss}_P(x)=\mathrm{log}|A|`$ for every $`xA`$. Since $`P`$ corresponds to $`A`$ in the sense that $`K(PA)=O(1)`$, we obtain $`L_x(\alpha +O(\mathrm{log}n))h_x(\alpha )`$. The term $`O(\mathrm{log}n)`$ is required, because the initial set of complexity $`\alpha `$ might contain strings of different lengths while we need to know $`n`$ to get rid of the strings of lengths different from $`n`$.

($``$) Conversely, assume that $`\mathrm{Loss}_P(x)m`$. Let $`A=\{x\{0,1\}^n:\mathrm{Loss}_P(x)m\}`$. Since $`_{|x|=n}2^{\mathrm{Loss}_P(x)}=1`$ (proof by induction on $`n`$), and $`2^{\mathrm{Loss}_P(x)}2^m`$ for every $`xA`$, we can conclude that $`A`$ has at most $`2^m`$ elements. Since $`K(AP)=O(\mathrm{log}m)`$, we obtain $`h_x(\alpha +O(\mathrm{log}n))L_x(\alpha )`$. ∎

Thus, within the obvious constraint of the function $`L_x(\alpha )+\alpha `$ being non-increasing, all shapes for the minimal total loss $`L_x(\alpha )`$ as a function of the allowed predictor complexity are possible.

### V-B Foundations of MDL

(i) Consider the following algorithm based on the Minimum Description Length principle. Given $`x`$, the data to explain, and $`\alpha `$, the maximum allowed complexity of explanation, we search for programs $`p`$ of length at most $`\alpha `$ that print a finite set $`Sx`$. Such pairs $`(p,S)`$ are possible explanations. The best explanation is defined to be the $`(p,S)`$ for which $`\delta (x|S)`$ is minimal. Since the function $`\delta (x|S)`$ is not computable, we cannot find the best explanation. The programs use unknown computation time and thus we can never be certain that we have found all possible explanations.

To overcome this problem we use the indirect method of MDL: We run all programs in dovetailed fashion. At every computation step $`t`$ consider all pairs $`(p,S)`$ such that program $`p`$ has printed the set $`S`$ containing $`x`$ by time $`t`$. Let $`(p_t,L_t)`$ stand for the pair $`(p,S)`$ such that $`|p|+\mathrm{log}|S|`$ is minimal among all these pairs $`(p,S)`$. The best hypothesis $`L_t`$ changes from time to time due to the appearance of a better hypothesis. Since no hypothesis is declared best twice, from some moment onwards the explanation $`(p_t,L_t)`$ which is declared best does not change anymore.

Compare this indirect method with the direct one: after step $`t`$ of dovetailing select $`(p,S)`$ for which $`\mathrm{log}|S|K^t(x|S)`$ is minimum among all programs $`p`$ that up to this time have printed a set $`S`$ containing $`x`$, where $`K^t(x|S)`$ is the approximation of $`K^t(x|S)`$ obtained after $`t`$ steps of dovetailing, that is, $`K^t(x|S)=\mathrm{min}\{|q|:U\text{ on input }q,S\text{ prints }x\text{ in at most }t\text{ steps}\}`$. Let $`(q_t,B_t)`$ stand for that model. This time the same hypothesis can be declared best twice. However from some moment onwards the explanation $`(q_t,B_t)`$ which is declared best does not change anymore.

Why do we prefer the indirect method to the direct one? The explanation is that we have a comparable situation in the practice of the real-world MDL, in the analogous process of finding the MDL code. There, we deal often with $`t`$ that are much less than the time of stabilization of both $`L_t`$ and $`B_t`$. For small $`t`$, the model $`L_t`$ is better than $`B_t`$ in the following respect: $`L_t`$ has some guarantee of goodness, as we know that $`\delta (x|L_t)+K(x)|p_t|+\mathrm{log}|L_t|+O(1)`$. That is, we know that the sum of deficiency of $`x`$ in $`L_t`$ and $`K(x)`$ is less than some known value. In contrast, the model $`B_t`$ has no guarantee of goodness at all: we do not know any upper bound neither for $`\delta (x|B_t)`$, nor for $`\delta (x|B_t)+K(x)`$.

Theorem IV.8 implies that the indirect method of MDL gives not only some garantee of goodness but also that, in the limit, that guarantee approaches the value it upper bounds, that is, approaches $`\delta (x|L_t)+K(x)`$, and $`\delta (x|L_t)`$ itself is not much greater than $`\delta (x|B_t)`$ (assuming that $`\alpha `$ is not critical). That is, in the limit, the method of MDL will yield an explanation that is only a little worse than the best explanation.

(ii) If $`Sx`$ is a smallest set such that $`K(S)\alpha `$, then $`S`$ can be converted into a best strategy of complexity at most $`\alpha `$, to predict the successive bits of $`x`$ given the preceding ones, (Section V-A). Interpreting “to explain” as “to be able to predict well”, MDL in the sense of sets witnessing $`\lambda _x(\alpha )`$ gives indeed a good explanations at every complexity level $`\alpha `$.

(iii) In statistical applications of MDL , MML , and related methods, one selects the model in a given model class that minimizes the sum of the model code length and the data-to-model code length; in modern versions  one selects the model that minimizes just the data-to-model code length (ignoring the model code length). For example, one uses data-to-model code $`\mathrm{log}P(x)`$ for data $`x`$ with respect to probability (density function) model $`P`$. For example, if the model is the uniform distribution over $`n`$-bit strings, then the data-to-model code for $`x=00\mathrm{}0`$ is $`\mathrm{log}1/2^n=n`$, even though we can compress $`x`$ to about $`logn`$ bits, without even using the model. Thus, the data-to-model code is the worst-case number of bits required for data of given length using the model, rather than the optimal number of bits for the particular data at hand. This is precisely what we do in the structure function approach: the data-to-model cost of $`x`$ with respect to model $`Ax`$ is $`\mathrm{log}|A|`$, the worst-case number of bits required to specify an element of $`A`$ rather than the minimal number of bits required to specify $`x`$ in particular. In contrast, ultimate compression of the two-part code, which is suggested by the “minimum description length” phrase, , means minimizing $`K(A)+K(x|A)`$ over all models $`A`$ in the model class. In Theorem IV.8 we have essentially shown that the “worst-case” data-to-model code above is the approach that guarantees the best fitting model. In contrast, the “ultimate compression” approach can yield models that are far from best fit. (It is easy to see that this happens only if the data are “not typical” for the contemplated model, .) For instance, let $`x`$ be a string of length $`n`$ and complexity about $`n/2`$ for which $`\beta _x(O(\mathrm{log}(n))=n/4+O(\mathrm{log}(n)`$. This means that the best model at a very low complexity level (essentially level 0 within the “logarithmic additive precision” which governs our techniques and results) has significant randomness deficiency and hence is far from “optimal” or “sufficient”. Such strings exist by Corollary IV.9. Such strings are not the strings of maximal Kolmogorov complexity, with $`K(x)n`$, such as most likely result from $`n`$ flips with a fair coin, but strings that must have a more complex cause since their minimal sufficient statistic has complexity higher than $`O(\mathrm{log}n)`$. Consider the model class consisting of the finite sets containing $`x`$ at complexity level $`\alpha =O(\mathrm{log}n)`$. Then for the model $`A_0=\{0,1\}^n`$ we have $`K(A_0)=O(\mathrm{log}n)`$ and $`K(x|A_0)=n/2+O(\mathrm{log}n)`$ thus the sum $`K(A_0)+K(x|A_0)=n/2+O(\mathrm{log}n)`$ is minimal up to a term $`O(\mathrm{log}n)`$. However, the randomness defficiency of $`x`$ in $`A_0`$ is about $`n/2`$, which is much bigger than the minimum $`\beta _x(O(\mathrm{log}(n))n/4`$. For the model $`A_1`$ witnessing $`\beta _x(O(\mathrm{log}(n))n/4`$ we also have $`K(A_1)=O(\mathrm{log}n)`$ and $`K(x|A_1)=n/2+O(\mathrm{log}n)`$. However, it has smaller cardinality: $`\mathrm{log}|A_1|=3n/4+O(\mathrm{log}n)`$ which causes the smaller randomness deficiency.

The same happens also for other model classes, such as probability models, see Appendix B. Consider, for instance, the class of Bernoulli processes with rational bias $`p`$ for outcome “1” ($`0p1`$) to generate binary strings of length $`n`$. Suppose we look for the model minimizing the codelength of the model plus data given the model: $`K(p|n)+K(x|p,n)`$. Let the data be $`x=00\mathrm{}0`$. Then the probability model $`P`$ (the uniform distribution) with $`P(x)=1/2^n`$ corresponding to probability $`p=\frac{1}{2}`$ compresses the data code to $`K(xn,p)=O(1)`$ bits since we can describe $`x`$ by the program print n ‘‘0’’s, and hence need only $`O(1)`$ bits apart from $`n`$. We also trivially have $`K(p|n)K(p)+O(1)=O(1)`$. But we cannot distinguish between the probability model $`P`$ hypothesis based on $`p`$ and the probability model $`P^{}`$ with $`P^{}(x)=1`$ (singular distribution) hypothesis based on $`p^{}`$ in terms of tthese code lengths: we find the same code length $`K(xn,p^{})=O(1)`$ bits and $`K(p^{}|n)=O(1)`$ if we replace $`p=\frac{1}{2}`$ by $`p^{}=0`$ in these expressions. Thus we have no basis to prefer hypothesis $`p`$ or hypothesis $`p^{}`$, even though the second possibility is overwhelmingly more likely. This shows that ultimate compression of the two-part code, here for example resulting in $`K(p|n)+K(x|n,p)`$, may yield a (probability) model $`P`$ based on $`p=\frac{1}{2}`$ for which the data has the maximal possible randomness deficiency ($`\mathrm{log}P(x)K(xn,p)=nO(1)`$ and hence is atypical.

However, in the structure functions $`h_x(\alpha )`$ and $`\lambda _x(\alpha )`$ the data-to-model code for the model $`p=\frac{1}{2}`$ is $`\mathrm{log}P(x)=\mathrm{log}(\frac{1}{2})^n=n`$ bits, while $`p^{}=0`$ results $`\mathrm{log}P^{}(x)=\mathrm{log}1^n=0`$ bits. Choosing the shortest data-to-model code results in the minimal randomness deficiency, as in (the generalization to probability distributions of) Theorem IV.8.

(iv) Another question arising in MDL or maximum likelihood (ML) estimation is its performance if the “true” model is not part of the contemplated model class. Given certain data, why would we assume they are generated by probabilistic or deterministic processes? They have arisen by natural processes most likely not conforming to mathematical idealization. Even if we can assume the data arose from a process that can be mathematically formulated, such situations arise if we restrict modeling of data arising from a “complex” source (conventional analogue being data arising from $`2k`$-parameter sources) by “simple” models (conventional analogue being $`k`$-parameter models). Again, Theorem IV.8 shows that, within the class of models of maximal complexity $`\alpha `$, these constraints we still select a simple model for which the data is maximally typical. This is particularly significant for data $`x`$ if the allowed complexity $`\alpha `$ is significantly below the complexity of the Kolmogorov minimal sufficient statistic, that is, if $`h_x(\alpha )+\alpha K(x)+c`$. This situation is potentially common, for example if we have a small data sample generated by a complex process. Then, the data will typically be non-stochastic in the sense of Section V-E. For a data sample that is very large relative to the complexity of the process generating it, this will typically not be the case and the structure function will drop to the sufficiency line early on.

### V-C Foundations of Maximum Likelihood

The algorithm based on ML principle is similar to the algorithm of the previous example. The only difference is that the currently best $`(p,S)`$ is the one for which $`\mathrm{log}|S|`$ is minimal. In this case the limit hypothesis $`\stackrel{~}{S}`$ will witness $`h_x(\alpha )`$ and we obtain the same corollary: $`\delta (x|S)\beta _x(\alpha O(\mathrm{log}n))+O(\mathrm{log}n)`$.

### V-D Approximation Improves Models

Assume that in the MDL algorithm, as described in Section V-B, we change the currently best explanation $`(p_1,S_1)`$ to the explanation $`(p_2,S_2)`$ only if $`|p_2|+\mathrm{log}|S_2|`$ is much less than $`|p_1|+\mathrm{log}|S_1|`$, say $`|p_2|+\mathrm{log}|S_2||p_1|+\mathrm{log}|S_1|c\mathrm{log}n`$ for a constant $`c`$. It turns out that if $`c`$ is large enough and $`p_1`$ is a shortest program of $`S_1`$, then $`\delta (xS_2)`$ is much less than $`\delta (xS_1)`$. That is, every time we change the explanation we improve its goodness unless the change is just caused by the fact that we have not yet found the minimum length program for the current model.

###### Lemma V.2

There is a constant $`c`$ such that if $`\mathrm{\Lambda }(S_2)\mathrm{\Lambda }(S_1)2c\mathrm{log}|x|`$, then $`\delta (xS_2)\delta (xS_2)c\mathrm{log}|x|+O(1)`$.

###### Proof:

Assume the notation of Theorem IV.8. By (C.4), for every pair of sets $`S_1,S_2x`$ we have $`\delta (xS_2)\delta (xS_1)=\mathrm{\Lambda }(S_2)\mathrm{\Lambda }(S_1)+\mathrm{\Delta }`$ with $`\mathrm{\Delta }=K(S_1x^{})K(S_2x^{})+O(1)K(S_1S_2,x^{})+O(1)K(S_1S_2,x)+O(1)`$. As $`\mathrm{\Lambda }(S_2)\mathrm{\Lambda }(S_1)|p_2|+\mathrm{log}|S_2|\mathrm{\Lambda }(S_1)=|p_2|+\mathrm{log}|S_2|(|p_1|+\mathrm{log}|S_1|)2c\mathrm{log}|x|`$ we need to prove that $`K(S_2S_1,x)c\mathrm{log}|x|+O(1)`$. Note that $`(p_1,S_1)`$, $`(p_2,S_2)`$ are consecutive explanations in the algorithm and every explanation may appear only once. Hence to identify $`S_1`$ we only need to know $`p_2,S_2,\alpha `$ and $`x`$. Since $`p_2`$ may be found from $`S_2`$ and length $`|p_2|`$ as the first program computing $`S_2`$ of length $`|p_2|`$, obtained by running all programs dovetailed style, we have $`K(S_2S_1,x)2\mathrm{log}|p_2|+2\mathrm{log}|\alpha |+O(1)4\mathrm{log}|x|+O(1)`$. Hence we can choose $`c=4`$. (Continued in Section VI-D.) ∎

### V-E Non-stochastic Objects

Let $`\alpha _0,\beta _0`$ be natural numbers. A string $`x`$ is called $`(\alpha _0,\beta _0)`$-stochastic by Kolmogorov if $`\beta _x(\alpha _0)\beta _0`$. In  it is proven that for some $`c,C`$ for all $`n`$ and all $`\alpha _0,\beta _0`$ with $`2\alpha _0+\beta _0<nc\mathrm{log}nC`$ there is a string $`x`$ of length $`n`$ that is not $`(\alpha _0,\beta _0)`$-stochastic. Corollary IV.9 strengthens this result of Shen: for some $`c,C`$ for all $`n`$ and all $`\alpha _0,\beta _0`$ with $`\alpha _0+\beta _0<nc\mathrm{log}nC`$ there is a string $`x`$ of length $`n`$ that is not $`(\alpha _0,\beta _0)`$-stochastic. Indeed, apply Corollary IV.9 to $`k=\alpha _0+c_1\mathrm{log}n+C_1`$ (we will choose $`c_1,C_1`$ later) and the function $`\beta (i)=nk`$ for $`i<k`$ and $`\beta (i)=0`$ for $`i=k`$. For the $`x`$ existing by Corollary IV.9 we have $`\beta _x(\alpha _0)\beta (\alpha _0\pm (c_2\mathrm{log}n+C_2))(c_2\mathrm{log}n+C_2)\beta (k1)(c_2\mathrm{log}n+C_2)=nk(c_2\mathrm{log}n+C_2)=n(\alpha _0+c_1\mathrm{log}n+C_1)(c_2\mathrm{log}n+C_2)>\beta _0`$. (The first inequality is true if $`\alpha _0+c_2\mathrm{log}n+C_2k1`$; thus let $`c_1=c_2,C_1=C_2+1`$. For the last inequality to be true let $`c=c_1+c_2`$ and $`C=C_1+C_2`$.) That is, $`x`$ is not $`(\alpha _0,\beta _0)`$-stochastic.

## VI Fine Structure and Sufficient Statistic

Above, we looked at the coarse shape of the structure function, but not at the fine detail. We show that $`h_x`$ coming from infinity drops to the sufficiency line $`L`$ defined by $`L(\alpha )+\alpha =K(x)`$. It first touches this line for some $`\alpha _0K(x)+O(1)`$. It then touches this line a number of times (bounded by a universal constant) and in between moves slightly (logarithmically) away in little bumps. There is a simple explanation why these bumps are there: It follows from (II.3) and (II.5) that there is a constant $`c_1`$ such that for every $`Sx`$, we have $`K(S)+\mathrm{log}|S|K(x)+K(Sx^{})c_1`$. If, moreover, $`K(S)+\mathrm{log}|S|K(x)+c_2`$, then $`K(Sx^{})c_2+c_1`$. This was already observed in . Consequently, there are less than $`2^{c_2+c_1+1}`$ distinct such sets $`S`$. Suppose the graph of $`h_x`$ drops within distance $`c_2`$ of the sufficiency line at $`\alpha _0`$, then it cannot be within distance $`c_2`$ on more than $`2^{c_2+c_1+1}`$ points. By the pigeon-hole principle, there is $`\alpha [\alpha _0,K(x)]`$ such that $`h_x(\alpha )+\alpha \lambda _x(\alpha )K(x)+\mathrm{log}(K(x)\alpha _0)c_21`$. So if $`|K(x)\alpha _0|`$ is of order $`\mathrm{\Omega }(n)`$ , then we obtain the logarithmic bumps, or possibly only one logarithmic bump, on the interval $`[\alpha _0,K(x)]`$. However, we will show below that $`h_x`$ cannot move away more than $`O(\mathrm{log}|K(x)\alpha _0|)`$ from the sufficiency line on the interval $`[\alpha _0,K(x)]`$. The intuition here is that a data sequence can have a simple satisfactory probabilistic explanation, but we can also explain it by many only slightly more complex explanations that are slightly less satisfactory but also model more accidental random features—models that are only slightly more complex but that significantly overfit the data sequence by modeling noise.

### VI-A Initial behavior

Let $`x`$ be a string of complexity $`K(x)=k`$. The structure function $`h_x(\alpha )`$ defined by (II.8) rises sharply above the sufficiency line for very small values of $`\alpha `$ with $`h_x(\alpha )=\mathrm{}`$ for $`\alpha `$ close to 0. To analyze the behavior of $`h_x`$ near the origin, define a function

$$m(x)=\underset{y}{\mathrm{min}}\{K(y):yx\},$$
(VI.1)
the minimum complexity of a string greater than $`x`$—that is, $`m(x)`$ is the greatest monotonic non-decreasing function that lower bounds $`K(x)`$. The function $`m(x)`$ tends to infinity as $`x`$ tends to infinity, very slowly—slower than any computable function.

For every $`\alpha [0,m(x)O(1))`$ we have $`h_x(\alpha )=\mathrm{}`$. To see this, we reason as follows: For a set $`Sx`$ with $`K(S)=\alpha `$ with $`\alpha `$ in the above range we can consider the largest element $`y`$ of $`S`$. Then $`y`$ has complexity $`\alpha +O(1)<m(x)`$, that is, $`K(y)<m(x)`$, which implies that $`y<x`$. But then $`xS`$ which is a contradiction.

### VI-B Sufficient Statistic

A sufficient statistic of the data contains all information in the data about the model. In introducing the notion of sufficiency in classical statistics, Fisher  stated: “The statistic chosen should summarize the whole of the relevant information supplied by the sample. This may be called the Criterion of Sufficiency $`\mathrm{}`$ In the case of the normal curve of distribution it is evident that the second moment is a sufficient statistic for estimating the standard deviation.” For the classical (probabilistic) theory see, for example, . In  an algorithmic theory of sufficient statistic (relating individual data to individual model) was developed and its relation with the probabilistic version established. The algorithmic basics are as follows: Intuitively, a model expresses the essence of the data if the two-part code describing the data consisting of the model and the data-to-model code is as concise as the best one-part description. Formally:

###### Definition VI.1

A finite set $`S`$ containing $`x`$ is *optimal for $`x`$* if

$$\mathrm{\Lambda }(S)K(x)+c.$$
(VI.2)
Here $`c`$ is some small value, constant or logarithmic in $`K(x)`$, depending on the context. A minimal length description $`S^{}`$ of such an optimal set is called a *sufficient statistic for $`x`$*. To specify the value of $`c`$ we will say *$`c`$-optimal* and *$`c`$-sufficient*.

If a set $`S`$ is $`c`$-optimal with $`c`$ constant, then by (II.9) we have $`K(x)c_2\mathrm{\Lambda }(S)K(x)+c`$. Hence, with respect to the structure function $`\lambda _x(\alpha )`$ we can state that all optimal sets $`S`$ and only those, cause the function $`\lambda _x`$ to drop to its minimal possible value $`K(x)`$. We know that this happens for at least one set, $`\{x\}`$ of complexity $`K(x)+O(1)`$.

We are interested in finding optimal sets that have low complexity. Those having minimal complexity are called *minimal optimal sets* (and their programs *minimal sufficient statistics*). The less optimal the sets are, the more additional noise in the data they start to model, see the discussion of overfitting in the initial paragraphs of Section IV. To be rigorous we should say minimal among $`c`$-optimal. We know from  that the complexity of a minimal optimal set is at least $`K(K(x))`$, up to a fixed additive constant, for every $`x`$. So for smaller arguments the structure function definitively rises above the sufficiency line. We also know that for every $`n`$ there are so-called non-stochastic objects $`x`$ of length $`n`$ that have optimal sets of high complexity only. For example, there are $`x`$ of complexity $`K(xn^{})=n+O(1)`$ such that every optimal set $`S`$ has also complexity $`K(Sn^{})=n+O(1)`$, hence by the conditional version $`K(Sn^{})+\mathrm{log}|S|K(xn^{})+c`$ of (VI.2) we find $`|S|`$ is bounded by a fixed universal constant. As $`K(Sx^{})=O(1)`$ (this is proven in the beginning of this section), for every $`yS`$ we have $`K(yx^{})K(yS)+K(Sx^{})+O(1)=O(1)`$. Roughly speaking for such $`x`$ there is no other optimal set $`S`$ than the singleton $`\{x\}`$.

###### Example VI.2

Bernoulli Process: Let us look at the coin toss example of Item (iii) in Section V-B, this time in the sense of finite set models rather than probability models. Let $`k`$ be a number in the range $`0,1,\mathrm{},n`$ of complexity $`\mathrm{log}n+O(1)`$ given $`n`$ and let $`x`$ be a string of length $`n`$ having $`k`$ ones of complexity $`K(xn,k)\mathrm{log}\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ given $`n,k`$. This $`x`$ can be viewed as a typical result of tossing a coin with a bias about $`p=k/n`$. A two-part description of $`x`$ is given by the number $`k`$ of 1’s in $`x`$ first, followed by the index $`j\mathrm{log}|S|`$ of $`x`$ in the set $`S`$ of strings of length $`n`$ with $`k`$ 1’s. This set is optimal, since $`K(xn)=K(x,kn)=K(kn)+K(xk,n)=K(S|n)+\mathrm{log}|S|`$. $`\mathrm{}`$

###### Example VI.3

Hierarchy of Sufficient Statistics: Another possible application of the theory is to find a good summarization of the meaningful information in a given picture. All the information in the picture is described by a binary string $`x`$ of length $`n=ml`$ as follows. Chop $`x`$ into $`l`$ substrings $`x_i`$ ($`1il`$) of equal length $`m`$ each. Let $`k_i`$ denote the number of ones in $`x_i`$. Each such substring metaphorically represents a patch of, say, color. The intended color, say “cobalt blue”, is indicated by the number of ones in the substring. The actual color depicted may be typical cobalt blue or less typical cobalt blue. The smaller the randomness deficiency of substring $`x_i`$ in the set of all strings of length $`m`$ containing precisely $`k_i`$ ones, the more typical $`x_i`$ is, the better it achieves a typical cobalt blue color. The metaphorical “image” depicted by $`x`$ is $`\pi (x)`$, defined as the string $`k_1k_2\mathrm{}k_l`$ over the alphabet $`\{0,1,\mathrm{},m\}`$, the set of colors available. We can now consider several statistics for $`x`$.

Let $`X\{0,1,\mathrm{},m\}^l`$ (the set of possible realizations of the target image), and let $`Y_i`$ for $`i=0,1,\mathrm{},m`$ be a set of binary strings of length $`m`$ with $`i`$ ones (the set of realizations of target color $`i`$). Consider the set

$$S=\{x^{}:\pi (x^{})X,(x^{})_iY_{k_i}\text{ for all }i=1,\mathrm{},l\}$$

One possible application of these ideas are to gouge how good the picture is with respect to the given summarizing set $`S`$. Assume that $`xS`$. The set $`S`$ is then a statistic for $`x`$ that captures both the colors of the patches and the image, that is, the total picture. If $`S`$ is a sufficient statistic of $`x`$ then $`S`$ perfectly expresses the meaning aimed for by the image and the true color aimed for in everyone of the color patches. Clearly, $`S`$ summarizes the relevant information in $`x`$ since it captures both image and coloring, that is, the total picture. But we can distinguish more sufficient statistics.

The set

$$S_1=\{x^{}:\pi (x^{})X\}$$

is a statistic that captures only the image. It can be sufficient only if all colors used in the picture $`x`$ are typical. The set

$$S_2=\{x^{}:(x^{})_iY_{k_i}\text{ for all }i=1,\mathrm{},l\}$$

is a statistic that captures the color information in the picture. It can be sufficient only if the image is a random string of length $`l`$ over the alphabet $`\{0,1,\mathrm{},m\}`$, which is surely not the case for all the real images. Finally the set

$$A_i=\{x^{}:(x^{})_iY_{k_i}\}$$

is a statistic that captures only the color of patch $`(x^{})_i`$ in the picture. It can be sufficient only if $`K(i)0`$ and all the other color applications and the image are typical. $`\mathrm{}`$

### VI-C Bumps in the Structure Function

Consider $`x\{0,1\}^n`$ with $`K(xn)=n+O(1)`$ and the conditional variant $`h_x(\alpha y)=\mathrm{min}_S\{\mathrm{log}|S|:Sx,|S|<\mathrm{},K(Sy)\alpha \}`$ of (II.8). Since $`S_1=\{0,1\}^n`$ is a set containing $`x`$ and can be described by $`O(1)`$ bits (given $`n`$), we find $`h_x(\alpha n)n+O(1)`$ for $`\alpha =K(S_1n)=O(1)`$. For increasing $`\alpha `$, the size of a set $`Sx`$, one can describe in $`\alpha `$ bits, decreases monotonically until for some $`\alpha _0`$ we obtain a first set $`S_0`$ witnessing $`h_x(\alpha _0n)+\alpha _0=K(xn)+O(1)`$. Then, $`S_0`$ is a minimal-complexity optimal set for $`x`$, and $`S_0^{}`$ is a minimal sufficient statistic for $`x`$. Further increase of $`\alpha `$ halves the set $`S`$ for each additional bit of $`\alpha `$ until $`\alpha =K(xn)`$. In other words, for every increment $`d`$ we have $`h_x(\alpha _0+dn)=K(xn)(\alpha _0+d+O(\mathrm{log}d))`$, provided the right-hand side is non-negative, and 0 otherwise. Namely, once we have an optimal set $`S_0`$ we can subdivide it in a standard way into $`2^d`$ parts and take as new set $`S`$ the part containing $`x`$. The $`O(\mathrm{log}d)`$ term is due to the fact that we have to consider self-delimiting encodings of $`d`$. This additive term is there to stay, it cannot be eliminated. For $`\alpha K(xn)`$ obviously the smallest set $`S`$ containing $`x`$ that one can describe using $`\alpha `$ bits (given $`n`$) is the singleton set $`S=\{x\}`$. The same analysis can be given for the unconditional version $`h_x(\alpha )`$ of the structure function, which behaves the same except for possibly the small initial part $`\alpha [0,K(n))`$ where the complexity is too small to specify the set $`S_1=\{0,1\}^n`$, see the initial part of Section VI.

The little bumps in the sufficient statistic region $`[K(K(x)),K(x)]`$ in Figure 3 are due to the boundedness of the number of sufficient statistics.

### VI-D “Positive” and “Negative” Randomness

(Continuing Section V-E.) In  the existence of strings was shown for which essentially the singleton set consisting of the string itself is a minimal sufficient statistic. While a sufficient statistic of an object yields a two-part code that is as short as the shortest one part code, restricting the complexity of the allowed statistic may yield two-part codes that are considerably longer than the best one-part code (so the statistic is insufficient). This is what happens for the non-stochastic objects. In fact, for every object there is a complexity bound below which this happens—but if that bound is small (logarithmic) we call the object “stochastic” since it has a simple satisfactory explanation (sufficient statistic). Thus, Kolmogorov in  (full text given in Section I) makes the important distinction of an object just being random in the “negative” sense by having high Kolmogorov complexity, and an object having high Kolmogorov complexity but also being random in the “positive, probabilistic” sense of having a low-complexity minimal sufficient statistic. An example of the latter is a string $`x`$ of length $`n`$ with $`K(x)n`$, being typical for the set $`\{0,1\}^n`$, or the uniform probability distribution over that set, while this set or probability distribution has complexity $`K(n)+O(1)=O(\mathrm{log}n)`$. We depict the distinction in Figure 4.

Corollary IV.9 establishes that for some constant $`C`$, for every length $`n`$, for every complexity $`kn`$ and every $`\alpha _0[0,k]`$, there are $`x`$’s of length $`n`$ and complexity $`k\pm C\mathrm{log}n`$ such that the minimal randomness deficiency $`\beta _x(i)>nkC\mathrm{log}n`$ for every $`i\alpha _0C\mathrm{log}n`$ and $`\beta _x(i)<C\mathrm{log}n`$ for every $`i\alpha _0+C\mathrm{log}n`$. Fix $`\epsilon =C\mathrm{log}n`$ and define for all $`s,t=0,\mathrm{},n/(2\epsilon )1`$ the set $`A_{st}`$ of all $`n`$-length strings of complexity $`K(x)[(2s1)\epsilon ,(2s+1)\epsilon )`$ and such that the minimal randomness deficiency $`\beta _x(i)>n(2s+1)\epsilon `$ for every $`i(2t1)\epsilon `$ and $`\beta _x(i)<\epsilon `$ for every $`i(2t+1)\epsilon `$. Corollary IV.9 implies that every $`A_{st}`$ is non-empty (let $`\alpha _0=2t\epsilon `$, $`k=2s\epsilon `$). Note that $`A_{st}`$ are pair-wise disjoint. Indeed, if $`ss^{}`$ then $`A_{st}`$ and $`A_{s^{}t^{}}`$ are disjoint as the corresponding strings $`x,x^{}`$ have different complexities. And if $`tt^{}`$, say $`t<t^{}`$, then $`A_{st}`$ and $`A_{s^{}t^{}}`$ are disjoint, as the corresponding strings $`x,x^{}`$ have different value of deficiency function in the point $`i=(2t+1)\epsilon `$: $`\beta _x((2t+1)\epsilon )>n(2s+1)\epsilon \epsilon >\beta _x^{}((2t+1)\epsilon )`$.

Letting $`k=\alpha _0=n\sqrt{n}`$ we see that there are $`n`$-length non-stochastic strings of almost maximal complexity $`n\sqrt{n}\pm O(\mathrm{log}n)`$ having significant $`\sqrt{n}\pm O(\mathrm{log}n)`$ randomness deficiency with respect to $`\{0,1\}^n`$ or, in fact, every other finite set of complexity less than $`nO(\mathrm{log}n)`$!

## VII Computability Questions

How difficult is it to compute the functions $`h_x,\lambda _x,\beta _x`$, and the minimal sufficient statistic? To express the properties appropriately we require the notion of functions that are not computable, but can be approximated monotonically by a computable function.

###### Definition VII.1

A function $`f:𝒩`$ is upper semi-computable if there is a Turing machine $`T`$ computing a total function $`\varphi `$ such that $`\varphi (x,t+1)\varphi (x,t)`$ and $`lim_t\mathrm{}\varphi (x,t)=f(x)`$. This means that $`f`$ can be computably approximated from above. If $`f`$ is upper semi-computable, then $`f`$ is lower semi-computable. A function is called semi-computable if it is either upper semi-computable or lower semi-computable. If $`f`$ is both upper semi-computable and lower semi-computable, then we call $`f`$ computable (or recursive if the domain is integer or rational).

Semi-computability gives no speed-of-convergence guaranties: even though the limit value is monotonically approximated we know at no stage in the process how close we are to the limit value. The functions $`h_x(\alpha ),\lambda _x(\alpha ),\beta _x(\alpha )`$ have finite domain for given $`x`$ and hence can be given as a table—so formally speaking they are computable. But this evades the issue: there is no algorithm that computes these functions for given $`x`$ and $`\alpha `$. Considering them as two-argument functions we show the following (we actually quantify these):

* The functions $`h_x(\alpha )`$ and $`\lambda _x(\alpha )`$ are upper semi-computable but they are not computable up to any reasonable precision.
* Moreover, there is no algorithm that given $`x^{}`$ and $`\alpha `$ finds $`h_x(\alpha )`$ or $`\lambda _x(\alpha )`$.
* The function $`\beta _x(\alpha )`$ is not upper- or lower semi-computable, not even to any reasonable precision, but we can compute it given an oracle for the halting problem.
* There is no algorithm that given $`x`$ and $`K(x)`$ finds a minimal sufficient statistic for $`x`$ up to any reasonable precision.

Intuition: the functions $`h_x`$ and $`\lambda _x`$ (the ML-estimator and the MDL-estimator, respectively) can be monotonically approximated in the upper semi-computable sense. But the fitness function $`\beta _x`$ cannot be monotonically approximated in that sense, nor in the lower semi-computable sense, in both cases not even up to any relevant precision.

The precise forms of these quite strong noncomputability and nonapproximability results are given in Appendix D.

## VIII Realizing the Structure Function

It is straightforward that we can monotonically approximate $`h_x`$ and its witnesses (similarly $`\lambda _x`$) in the sense that there exists a non-halting algorithm $`A`$ that given any $`x,\alpha `$ outputs a finite sequence $`p_1,p_2,p_3,\mathrm{},p_l`$ of pairwise different computer programs each of length at most $`\alpha +C\mathrm{log}|x|`$ ($`C`$ is a constant) such that each program $`p_i`$ prints a model $`S_i`$ such that $`|S_1|>|S_2|>\mathrm{}>|S_l|`$. This way of computing $`h_x`$ or $`\lambda _x`$ is called upper semi-computable, formally defined in Definition VII.1. By the results of Section IV the last model $`S_l`$ is “near” the best possible model according to the randomness deficiency criterion: There is no program $`p`$ of length at most $`\alpha `$ that prints a model $`S`$ such that the randomness deficiency of $`x`$ for $`S`$ is $`C\mathrm{log}|x|`$ less than that of $`x`$ for $`S_l`$. Note that we are not able to identify $`p_l`$ given $`x,\alpha `$, since the algorithm $`A`$ is non-halting and thus we do not know which program will be output last. This way we obtain a model of (approximately) best fit at each complexity level $`\alpha `$, but non-uniformly.

The question arises whether there is a uniform construction to obtain the models that realize the structure functions at given complexities. Here we present such a construction. (In view of the non-computability of structure functions, Section VII, the construction is of course not computable.)

We give a general uniform construction of the finite sets witnessing $`\lambda _x`$, $`h_x`$, and $`\beta _x`$, at each argument (that is, level of model complexity), in terms of indexes of $`x`$ in the enumeration of strings of given complexity, up to the “coarse” equivalence precision of Section IV. This extends a technique introduced in .

###### Definition VIII.1

Let $`N^l`$ denote the number of strings of complexity at most $`l`$, and let $`|N^l|`$ denote the length of the binary notation of $`N^l`$. For $`i|N^l|`$ let $`N_i^l`$ stand for $`i`$ most significant bits of binary notation of $`N^l`$. Let $`D`$ denote the set of all pairs $`\{x,lK(x)l\}`$. Fix an enumeration of $`D`$ and denote by $`I_x^l`$ the minimum index of a pair $`x,i`$ with $`il`$ in that enumeration, that is, the number of pairs enumerated before $`x,i`$ (if $`K(x)>l`$ then $`I_x^l=\mathrm{}`$). Let $`m_x^l`$ denote the maximal common prefix of binary notations of $`I_x^l`$ and $`N^l`$, that is, $`I_x^l=m_x^l0\mathrm{}`$ and $`N^l=m_x^l1\mathrm{}`$ (we assume here that binary notation of $`I_x^l`$ is written in exactly $`|N^l|`$ bits with leading zeros if necessary).

(In  the notation $`m_x`$ is used for $`m_x^l`$ with $`l=K(x)`$.)

###### Theorem VIII.2

For every $`il`$, the number $`N_i^l`$ is algorithmically equivalent to $`N^i`$, that is, $`K(N^iN_i^l),K(N_i^lN^i)=O(\mathrm{log}l)`$.

Before proceeding to the main theorem of this section we introduce some more notation.

###### Definition VIII.3

For $`il`$ let $`S_i^l`$ denote the set of all strings $`y`$ such that the binary notation of $`I_y^l`$ has the form $`N_i^l0\mathrm{}`$ (we assume here that binary notations of indexes are written using exactly $`|N^l|`$ bits.)

Let $`c`$ denote a constant such that $`K(x)\mathrm{\Lambda }(S)+c`$ for every $`xS`$. The following theorem shows that sets $`S_i^l`$ form a universal family of statistics for $`x`$.

###### Theorem VIII.4

(i) If the $`(i+1)`$st most significant bit of $`N^l`$ is $`1`$ then $`|S_i^l|=2^{|N^l|i1}`$ and $`S_i^l`$ is algorithmically equivalent to $`N_i^l`$, that is $`K(N_i^lS_i^l),K(S_i^lN_i^l)=O(\mathrm{log}l)`$.

(ii) For every $`S`$ and every $`xS`$, let $`l=\mathrm{\Lambda }(S)+c`$ and $`i=|m_x^l|`$. Then $`xS_i^l`$, $`K(S_i^lS)=O(\mathrm{log}l)`$, $`K(S_i^l)=i+O(\mathrm{log}l)K(S)+O(\mathrm{log}l)`$, and $`\mathrm{\Lambda }(S_i^l)\mathrm{\Lambda }(S)+O(\mathrm{log}l)`$ (that is, $`S_i^l`$ is not worse than $`S`$, as a model explaining $`x`$).

(iii) If $`\alpha `$ is critical then every $`S`$ witnessing $`\lambda _x(\alpha )`$ is algorithmically equivalent to $`N^\alpha `$. That is, if $`K(S)\alpha `$ and $`\mathrm{\Lambda }(S)\lambda _x(\alpha )`$ but $`K(N^\alpha |S)0`$ or $`K(S|N^\alpha )0`$ then there is $`Ax`$ with $`K(A)\alpha `$ and $`\mathrm{\Lambda }(A)\lambda _x(\alpha )`$. More specifically, for all $`Sx`$ either $`K(S|N^\alpha )K(S)\alpha `$ and $`K(N^\alpha |S)=0`$, or there is $`Ax`$ such that $`\mathrm{\Lambda }(A)\mathrm{\Lambda }(S)`$ and $`K(A)\mathrm{min}\{\alpha K(N^\alpha |S),K(S)K(S|N^\alpha )\}`$, where all inequalities hold up to $`O(\mathrm{log}\mathrm{\Lambda }(S))`$ additive term.

Note that Item (iii) of the theorem does not hold for non-critical points. For instance, for a random string $`x`$ of length $`n`$ there are independent $`S_1,S_2`$ witnessing $`\lambda _x(\frac{n}{2})=n`$: let $`S_1`$ be the set of all $`x^{}`$ of length $`n`$ having the same prefix of length $`\frac{n}{2}`$ as $`x`$ and $`S_2`$ be the set of all $`x^{}`$ of length $`n`$ having the same suffix of length $`\frac{n}{2}`$ as $`x`$.

###### Corollary VIII.5

Let $`x`$ be a string of length $`n`$ and complexity $`k`$. For every $`\alpha `$ ($`K(n)+O(1)\alpha k`$) there is $`ln+K(n)+O(1)`$ such that the set $`S_\alpha ^l`$ both contains $`x`$ and witnesses $`h_x(\alpha )`$, $`\lambda _x(\alpha )`$, and $`\beta _x(\alpha )`$, up to an $`O(\mathrm{log}n)`$ additive term in the argument and value.

## Appendix A Oral History

Since there is no written version of Kolmogorov’s initial proposal , which we argued is a new approach to a “non-probabilistic statistics,” apart from a few lines  which we reproduced in Section I, we have to rely on the testimony of witnesses . Says Tom Cover : “I remember taking many long hours trying to understand the motivation of Kolmogorov’s approach.” According to Peter Gács, : “Kolmogorov drew a picture of $`h_x(\alpha )`$ as a function of $`\alpha `$ monotonically approaching the diagonal \[sufficiency line\]. Kolmogorov stated that it was known (proved by L.A. Levin) that in some cases it remained far from the diagonal line till the very end.” Leonid A. Levin : “Kolmogorov told me \[about\] $`h_x(i)`$ (or its inverse, I am not sure) and asked how this $`h(i)`$ could behave. I proved that $`i+h(i)+O(\mathrm{log}i)`$ is monotone but otherwise arbitrary within $`O(\sqrt{i})`$ accuracy; it stabilizes on $`K(x)`$ when $`i`$ exceeds $`I(x:\text{Halting})`$. (Actually, this expression for accuracy was Kolmogorov’s re-wording, I gave it in less elegant but equivalent terms—$`O(p\mathrm{log}i)`$ where p is the number of ”jumps”.) I do not remember Kolmogorov defining $`\beta _x(i)`$ or suggesting anything like your result. I never published anything on the topic because I do not believe strings $`x`$ with significant $`I(x:\text{Halting})`$ could exist in the world.” ($`I(x:y)=K(y)K(y|x)`$ is the information in $`x`$ about $`y`$. By (II.3) we have $`I(x:y)=I(y:x)`$, with equality holding up to a constant additive term indepennedent of $`x`$ and $`y`$, and hence we call this quantity the algorithmic mutual information. Above, ”Halting” stands for the infinite binary “halting sequence” defined as follows: The $`i`$th bit of Halting is 1 iff the $`i`$th program for the reference universal prefix machine $`U`$ halts, and 0 otherwise.)

###### Remark A.1

Levin’s statement  quoted above appears to suggest that strings $`x`$ such that $`h_x(i)+i`$ stabilizes on $`K(x)`$ only for large $`i`$ may exist mathematically but are unlikely to occur in nature, because such $`x`$’s must have a lot of information about the Halting problem. and hence the analysis of their properties is irrelevant. But the statement in question is imprecise. There are two ways to understand the statement: (i) $`h_x(i)+i`$ stabilizes on $`K(x)`$ when $`i`$ exceeds $`I(x:\text{Halting})`$ or earlier; or (ii) $`h_x(i)+i`$ stabilizes on $`K(x)`$ when $`i`$ exceeds $`I(x:\text{Halting})`$ and not earlier. It is not clear what “the information in $`x`$ about the halting problem” is, since the “Halting problem” is not a finite object and thus the notion of information about Halting needs a special definition. The usual $`I(x:\text{Halting})=K(\text{Halting})K(\text{Halting}x)`$ doesn’t make sense since both $`K(\text{Halting})`$ and $`K(\text{Halting}x)`$ are infinite. The expression $`I(x:\text{Halting})=K(x)K(x\text{Halting})`$ looks better provided $`K(x\text{Halting})`$ is understood as $`K(x)`$ relativized by the Halting problem. In the latter interpretation of $`I(x:\text{Halting})`$, case (i) is correct and case (ii) is false. The correctness of (i) is implicit in Theorem V.4. A counter example to (ii): Let $`p`$ be the halting program of length at most $`n`$ with the greatest running time. It is easy to show that $`K(p)`$ is about $`n`$, and therefore $`p`$ is a random string of length about $`n`$. As a consequence, the complexity of the minimal sufficient statistic $`\alpha _0`$ of $`p`$ is close to 0. On the other hand $`I(p:\text{Halting})`$ is about $`n`$. Indeed, given the oracle for the Halting problem and $`n`$ we can find $`x`$; hence $`I(p:\text{Halting})=K(p)K(p\text{Halting})nK(n)n2\mathrm{log}n`$. $`\mathrm{}`$

## Appendix B Validity for Extended Models

Following Kolmogorov we analyzed a canonical setting where the models are finite sets. As Kolmogorov himself pointed out, this is no real restriction: the finite sets model class is equivalent, up to a logarithmic additive term, to the model class of probability density functions, as studied in . The analysis is valid, up to logarithmic additive terms, also for the model class of total recursive functions, as studied in . The model class of computable probability density functions consists of the set of functions $`P:\{0,1\}^{}[0,1]`$ with $`P(x)=1`$. “Computable” means here that there is a Turing machine $`T_P`$ that, given $`x`$ and a positive rational $`\epsilon `$, computes $`P(x)`$ with precision $`\epsilon `$. The (prefix-) complexity $`K(P)`$ of a computable (possibly partial) function $`P`$ is defined by $`K(P)=\mathrm{min}_i\{K(i):\text{Turing machine }T_i\text{computes }P\}.`$ A string $`x`$ is typical for a distribution $`P`$ if the randomness deficiency $`\delta (xP)=\mathrm{log}P(x)K(xP)`$ is small. The conditional complexity $`K(xP)`$ is defined as follows. Say that a function $`A`$ approximates $`P`$ if $`|A(y,\epsilon )P(y)|<\epsilon `$ for every $`y`$ and every positive rational $`\epsilon `$. Then $`K(xP)`$ is the minimum length of a program that given every function $`A`$ approximating $`P`$ as an oracle prints $`x`$. Similarly, $`P`$ is $`c`$-optimal for $`x`$ if $`K(P)\mathrm{log}P(x)K(x)+c`$. Thus, instead of the data-to-model code length $`\mathrm{log}|S|`$ for finite set models, we consider the data-to-model code length $`\mathrm{log}P(x)`$ (the Shannon-Fano code). The value $`\mathrm{log}P(x)`$ measures also how likely $`x`$ is under the hypothesis $`P`$ and the mapping $`xP_{\mathrm{min}}`$ where $`P_{\mathrm{min}}`$ minimizes $`\mathrm{log}P(x)`$ over $`P`$ with $`K(P)\alpha `$ is a *constrained maximum likelihood estimator*, see Figure 5. Our results thus imply that such a constrained maximum likelihood estimator always returns a hypothesis with minimum randomness deficiency.

The essence of this approach is that we mean maximization over a class of likelihoods induced by computable probability density functions that are below a certain complexity level $`\alpha `$. In classical statistics, unconstrained maximal likelihood is known to perform badly for model selection, because it tends to want the most complex models possible. This is closely reflected in our approach: unconstrained maximization will result in the computable probability distribution of complexity about $`K(x)`$ that concentrates all probability on $`x`$. But the structure function $`h_x(\alpha )`$ tells us all stochastic properties of data $`x`$ in the sense as explained in detail in the start of Section IV. for finite set models.

The model class of total recursive functions consists of the set of computable functions $`p:\{0,1\}^{}\{0,1\}^{}`$. The (prefix-) complexity $`K(p)`$ of a total recursive function $`p`$ is defined by $`K(p)=\mathrm{min}_i\{K(i):\text{Turing machine }T_i\text{computes }p\}.`$ In place of $`\mathrm{log}|S|`$ for finite set models we consider the data-to-model code length $`l_x(p)=\mathrm{min}\{|d|:p(d)=x\}`$. A string $`x`$ is typical for a total recursive function $`p`$ if the randomness deficiency $`\delta (xp)=l_x(p)K(xp)`$ is small. The conditional complexity $`K(xp)`$ is defined as the minimum length of a program that given $`p`$ as an oracle prints $`x`$. Similarly, $`p`$ is $`c`$-optimal for $`x`$ if $`K(p)+l_x(p)K(x)+c.`$

It is easy to show that for every data string $`x`$ and a contemplated finite set model for it, there is an almost equivalent computable probability density function model and an almost equivalent total recursive function model.

###### Proposition B.1

For every $`x`$ and every finite set $`Sx`$ there is:

(a) A computable probability density function $`P`$ with $`\mathrm{log}P(x)=\mathrm{log}|S|`$, $`\delta (xP)=\delta (xS)+O(1)`$ and $`K(P)=K(S)+O(1)`$; and

(b) A total recursive function $`p`$ such that $`l_x(p)\mathrm{log}|S|`$, $`\delta (xp)\delta (xS)+O(1)`$ and $`K(p)=K(S)+O(1)`$.

###### Proof:

(a) Define $`P(y)=1/|S|`$ for $`yS`$ and 0 otherwise.

(b) If $`S=\{x_0,\mathrm{},x_{m1}\}`$, then define $`p(d)=x_{dmodm}`$. ∎

The converse of Proposition B.1 is slightly harder: for every data string $`x`$ and a contemplated computable probability density function model for it, as well as for a contemplated total recursive function model for $`x`$, there is a finite set model for $`x`$ that has no worse complexity, randomness deficiency, and worst-case data-to-model code for $`x`$, up to additive logarithmic precision.

###### Proposition B.2

There are constants $`c,C`$, such that for every string $`x`$, the following holds:

(a) For every computable probability density function $`P`$ there is a finite set $`Sx`$ such that $`\mathrm{log}|S|<\mathrm{log}P(x)+1`$, $`\delta (xS)\delta (xP)+2\mathrm{log}K(P)+K(\mathrm{log}P(x))+2\mathrm{log}K(\mathrm{log}P(x))+C`$ and $`K(S)K(P)+K(\mathrm{log}P(x))+C`$; and

(b) For every total recursive function $`p`$ there is a finite set $`Sx`$ with $`\mathrm{log}|S|l_x(p)`$, $`\delta (xS)\delta (xp)+2\mathrm{log}K(p)+K(l_x(p))+2\mathrm{log}K(l_x(p))+c`$ and $`K(S)K(p)+K(l_x(p))+c`$.

###### Proof:

(a) Let $`m=\mathrm{log}P(x)`$, that is, $`2^{m1}<P(x)2^m`$. Define $`S=\{y:P(y)>2^{m1}\}`$. Then, $`|S|<2^{m+1}2/P(x)`$, which implies the claimed value for $`\mathrm{log}|S|`$. To list $`S`$ it suffices to compute all consecutive values of $`P(y)`$ to sufficient precision until the combined probabilities exceed $`12^{m1}`$. That is, $`K(S)K(P)+K(m)+O(1)`$. Finally, $`\delta (xS)=\mathrm{log}|S|K(x|S^{})<\mathrm{log}P(x)K(xS^{})+1=\delta (xP)+K(xP)K(xS^{})+1\delta (xP)+K(S^{}P)+O(1)`$. The term $`K(S^{}P)`$ can be upper bounded as $`K(K(S))+K(m)+O(1)2\mathrm{log}K(S)+K(m)+O(1)2\mathrm{log}(K(P)+K(m))+K(m)+O(1)2\mathrm{log}K(P)+2\mathrm{log}K(m)+K(m)+O(1)`$, which implies the claimed bound for $`\delta (xS)`$.

(b) Define $`S=\{y:p(d)=y,|d|=l_x(p)\}`$. Then, $`\mathrm{log}|S|l_x(p)`$. To list $`S`$ it suffices to compute $`p(d)`$ for every argument of length equal $`l_x(p)`$. Hence, $`K(S)K(p)+K(l_x(p))+O(1)`$. The upper bound for $`\delta (xS)`$ is derived just in the same way as in the proof of item (a). ∎

###### Remark B.3

How large are the nonconstant additive complexity terms in Proposition B.2 for strings $`x`$ of length $`n`$? In item (a), we are commonly only interested in $`P`$ such that $`K(P)n+O(\mathrm{log}n)`$ and $`\mathrm{log}P(x)n+O(1)`$. Indeed, for every $`P`$ there is $`P^{}`$ such that $`K(P^{})\mathrm{min}\{K(P),n\}+O(\mathrm{log}n)`$, $`\delta (xP^{})\delta (xP)+O(\mathrm{log}n)`$, $`\mathrm{log}P^{}(x)\mathrm{min}\{\mathrm{log}P(x),n\}+1`$. Such $`P^{}`$ is defined as follows: If $`K(P)>n`$ then $`P^{}(x)=1`$ and $`P^{}(y)=0`$ for every $`yx`$; otherwise $`P^{}=(P+U_n)/2`$ where $`U_n`$ stands for the uniform distribution on $`\{0,1\}^n`$. Then the additive terms in item (a) are $`O(\mathrm{log}n)`$. In item (b) we are commonly only interested in $`p`$ such that $`K(p)n+O(\mathrm{log}n)`$ and $`l_x(p)n+O(1)`$. Indeed, for every $`p`$ there is $`p^{}`$ such that $`K(p^{})\mathrm{min}\{K(p),n\}+O(\mathrm{log}n)`$, $`\delta (xp^{})\delta (xp)+O(\mathrm{log}n)`$, $`l_x(p^{})\mathrm{min}\{l_x(p),n\}+1`$. Such $`p^{}`$ is defined as follows: If $`K(p)>n`$ then $`p^{}`$ maps all strings to $`x`$; otherwise $`p^{}(0u)=p(u)`$ and $`p^{}(1u)=u`$. Then the additive terms in item (b) are $`O(\mathrm{log}n)`$. Thus, in this sense all results in this paper that hold for finite set models extend, up to a logarithmic additive term, to computable probability density function models and to total recursive function models. Since the results in this paper hold only up to additive logarithmic term anyway, this means that all of them equivalently hold for the model class of computable probability density functions, as well as for the model class of total recursive functions. $`\mathrm{}`$

## Appendix C Proofs

###### Proof:

Lemma IV.2 The inequality $`\lambda _x(\alpha )h_x(\alpha )+\alpha `$ is immediate. So it suffices to prove that $`h_x(\alpha )+\alpha \lambda _x(\alpha )+K(\alpha )+O(1)`$. The proof of this inequality is based on the following:

###### Claim C.1

Ignoring additive $`K(i)`$ terms the function $`h_x(i)+i`$ does not increase:

$$h_x(i_2)+i_2h_x(i_1)+i_1+K(i_2i_1)+O(1)$$
(C.1)
for $`i_1<i_2K(x)`$.

###### Proof:

Let $`S`$ be a finite set containing $`x`$ with $`K(S)i_1`$ and $`\mathrm{log}|S|=h_x(i_1)`$. For every $`m\mathrm{log}|S|`$, we can partition $`S`$ into $`2^m`$ equal-size parts and select the part $`S^{}`$ containing $`x`$. Then, $`\mathrm{log}|S^{}|=\mathrm{log}|S|m`$ at the cost of increasing the complexity of $`S^{}`$ to

$$K(S^{})K(S)+m+K(mK(S))+O(1)$$

(we specify the part $`S^{}`$ containing $`x`$ by its index among all the parts). Choose

$$m=i_2K(S)K(i_2K(S))c$$

for a constant $`c`$ to be determined later. Note that

$`K(mK(S))`$ $`K(i_2,K(i_2K(S))K(S))+K(c)+c^{}`$
$`=K(i_2K(S))+K(c)+c^{\prime \prime }`$
for appropriate constants $`c^{},c^{\prime \prime }`$. The complexity of the resulting set $`S^{}`$ is thus at most

$`K(S)+i_2K(S)`$ $`K(i_2K(S))c`$
$`+K(i_2K(S))+K(c)+c^{\prime \prime }i_2,`$
provided $`c`$ is chosen large enough. Hence, $`h_x(i_2)\mathrm{log}|S^{}|=h_x(i_1)m=h_x(i_1)i_2+K(S)+K(i_2K(S))+c`$, and it suffices to prove that $`K(S)+K(i_2K(S))i_1+K(i_2i_1)+O(1)`$. This follows from the bound $`K(i_2K(S))K(i_2i_1)+K(i_1K(S))+O(1)K(i_2i_1)+K(i_1K(S))+O(1)K(i_2i_1)+i_1K(S)+O(1)`$. ∎

Let $`S`$ witness $`\lambda _x(\alpha )`$. Substituting $`K(S)=i_1`$, $`\alpha =i_2`$ in (C.1) we obtain: $`h_x(\alpha )+\alpha h_x(K(S))+K(S)+K(\alpha K(S))+O(1)\mathrm{\Lambda }(S)+K(\alpha )+O(1)=\lambda _x(\alpha )+K(\alpha )+O(1).`$

###### Proof:

Theorem IV.4 (i) We first observe that for every $`x`$ of length $`n`$ we have $`\lambda _x(K(n)+O(1))n+K(n)+O(1)`$, as witnessed by $`S=\{0,1\}^n`$. At the other extreme, $`\lambda _x(k+O(1))=k+O(1)`$, as witnessed by $`S=\{x\}`$.

Define $`\lambda (i)`$ by the equation $`\lambda (i)k=\mathrm{max}\{0,\lambda _x(i+K(n)+O(1))kO(1)\}`$. Then $`\lambda _x=(\lambda )`$ with $`\epsilon =\delta =K(n)+O(1)`$, and $`\lambda `$ satisfies the requirements of Item (i) of the theorem.

(ii) Fix $`\lambda (i)`$ satisfying the conditions in the theorem. It suffices to show that there is a string $`x`$ of length $`n`$ such that, for every $`i[0,k]`$, we have $`\lambda _x(i)\lambda (i)`$ and $`\lambda _x(i+\delta (i))\lambda (i)+\delta (i)`$ for $`\delta (i)=K(i,n,\lambda )+O(1)`$. Then, with $`\delta =\delta (k)`$, we have $`K(x)\lambda _x(k+\delta )+O(1)\lambda (k)+\delta +O(1)=k+\delta +O(1)`$. And the inequality $`\lambda _x(k)\lambda (k)=k`$ implies that $`K(x)>kO(1)`$.

###### Claim C.2

For every length $`n`$, there is a string $`x`$ of length $`n`$ such that $`\lambda _x(i)\lambda (i)`$ for every $`i`$ in the domain of $`\lambda `$.

###### Proof:

Fix a length $`n`$. If $`\lambda _x(i)<\lambda (i)`$ then $`x`$ belongs to a set $`A`$ with $`\mathrm{\Lambda }(A)<\lambda (i)\lambda (0)n`$. The total number of elements in different such $`A`$’s is less than $`_A2^{nK(A)}=2^n_A2^{K(A)}2^n`$, where the second inequality follows by (II.2). ∎

We prove Item (ii) by demonstrating that the lexicographically first $`x`$, as defined in Claim C.2, also satisfies $`\lambda _x(i+\delta (i))\lambda (i)+\delta (i)`$, for $`\delta (i)=K(i,n,\lambda )+O(1)`$ for all $`i[0,k]`$. It suffices to construct a set $`Sx`$ of cardinality $`2^{\lambda (i)i}`$ and of complexity at most $`i+\delta (i)`$, for every $`i[0,k]`$.

For every fixed $`i[0,k]`$ we can run the following:

Algorithm: Let $`A`$ be a set variable initially containing all strings of length $`n`$, and let $`S`$ be a set variable initially containing the $`2^{\lambda (i)i}`$ first strings of $`A`$ in lexicographical order. Run all programs of length at most $`n`$ dovetail style. Every time a program $`p`$ of some length $`j`$ halts, $`\lambda (j)`$ is defined, and $`p`$ prints a set $`B`$ of cardinality at most $`2^{\lambda (j)j}`$, we remove all the elements of $`B`$ from $`A`$ (but not from $`S`$); we call a step at which this happens a $`j`$-step. Every time $`SA`$ becomes empty at a $`j`$-step, we replace the contents of $`S`$ by the set of the $`2^{\lambda (i)i}`$ first strings in lexicographical order of (the current contents of) $`A`$. Possibly, the last replacement of $`S`$ is incomplete because there are less than $`2^{\lambda (i)i}`$ elements left in $`A`$. It is easy to see that $`xSA`$ just after the final replacement, and stays there forever after, even though some programs in the dovetailing process may still be running and elements from $`A`$ may still be eliminated.

###### Claim C.3

The contents of the set $`S`$ is replaced at most $`2^{i+1}`$ times.

###### Proof:

There are two types of replacements that will be treated separately.

Case 1: Replacement of the current contents of $`S`$ where at some $`j`$-step with $`ji`$ at least one element was removed from the current contents $`SA`$. Trivially, the number of this type of replacements is bounded by the number of $`j`$-steps with $`j<i`$, and hence by the number of programs of length less than $`i`$, that is, by $`2^i`$.

Case 2: Replacement of the current contents of $`S`$ where every one of the $`2^{\lambda (i)i}`$ elements of the current contents of $`S`$ is removed from $`A`$ by $`j`$-steps with $`ji`$. Let us estimate the number of this type of replacements: Every element $`x`$ removed at a $`j`$-step with $`ji`$ belongs to a set $`B`$ with $`\mathrm{\Lambda }(B)\lambda (j)\lambda (i)`$. The overall cumulative number of elements removed from $`A`$ on $`j`$-steps with $`ji`$ is bounded by $`_B2^{\lambda (i)K(B)}2^{\lambda (i)}`$, where the inequality follows by (II.2). Hence replacements of the second type can happen at most $`2^{\lambda (i)(\lambda (i)i)}=2^i`$ times. ∎

By Claim C.3, $`S`$ stabilizes after a certain number of $`j`$-steps. That number may be large. However, the number of replacements of $`S`$ is small. The final set $`Sx`$ has cardinality $`2^{\lambda (i)i}`$, and can be specified by the number of replacements resulting in its current contents (as in Claim C.3), and by $`i,n,\lambda `$. This shows that $`K(S)i+K(i,n,\lambda )+O(1)`$. ∎

###### Proof:

Theorem IV.8 The statement of the theorem easily follows from the following two inequalities that are valid for every $`x`$ (where $`n=|x|`$ and $`k=K(x)`$):

$`\beta _x(i)+k\lambda _x(i)+O(1),\text{ for every }ik\text{; and}`$ (C.2)
$`\lambda _x(i+O(\mathrm{log}n))\beta _x(i)+k+O(\mathrm{log}n),`$ (C.3)
for every $`i`$ satisfying $`K(n)+O(1)ik`$.
It is convenient to rewrite the formula defining $`\delta (xA)`$ using the symmetry of information (II.3) as follows:

$`\delta (xA)`$ $`=\mathrm{log}|A|+K(A)K(Ax^{})k+O(1)`$ (C.4)
$`=\mathrm{\Lambda }(A)K(Ax^{})k+O(1).`$
Ad (C.2): This is easy, because for every set $`Sx`$ witnessing $`\lambda _x(i)`$ we have $`\delta (xS)\mathrm{\Lambda }(S)k+O(1)=\lambda _x(i)k+O(1)`$ and $`\beta _x(i)\delta (xS)`$.

Ad (C.3): This is more difficult. By (C.4), and the obvious $`K(Ax^{})K(Ax)+O(1)`$, it suffices to prove that for every $`Ax`$ there is an $`Sx`$ with

$`K(S)K(A)+O(\mathrm{log}m),`$
$`\mathrm{log}|S|\mathrm{log}|A|K(Ax)+O(\mathrm{log}m),`$
where $`m=\mathrm{\Lambda }(A)`$. Indeed for every $`A`$ witnessing $`\beta _x(i)`$ the set $`S`$ will witness $`\lambda _x(i+O(\mathrm{log}n))\beta _x(i)+k+O(\mathrm{log}n)`$ (note that $`m=\mathrm{log}|A|+K(A)=K(xA^{})+\beta _x(i)+K(A)3n+O(\mathrm{log}n)`$ provided $`iK(n)+O(1)`$). The above assertion is only a little bit easier to prove than the one in Lemma C.4 below that also suffices. Since we need this lemma in any case in the proof of Theorem IV.11 we state and prove it right now.

###### Lemma C.4

For every $`Ax`$ there is $`Sx`$ with $`K(S)K(A)K(Ax)+O(\mathrm{log}m)`$ and $`\mathrm{log}|S|=\mathrm{log}|A|`$ (where $`m=\mathrm{\Lambda }(A)`$ ).

###### Proof:

Fix some $`A_0x`$ and let $`m=\mathrm{\Lambda }(A_0)`$. Our task is the following: Given $`K(A_0),\mathrm{log}|A_0|,K(A_0x)`$, to enumerate a family of at most $`2^{K(A_0)K(A_0x)+O(\mathrm{log}m)}`$ different sets $`S`$ with $`\mathrm{log}|S|=\mathrm{log}|A_0|`$ that cover all $`y`$’s covered by sets $`A`$, with $`K(A)=K(A_0)`$, $`K(Ay)=K(A_0x)`$ and $`\mathrm{log}|A|=\mathrm{log}|A_0|`$. Since the complexity of each enumerated $`S`$ does not exceed $`K(A_0)K(A_0x)+O(\mathrm{log}m)+K(K(A_0),\mathrm{log}|A_0|,K(A_0x))+O(1)=K(A_0)K(A_0x)+O(\mathrm{log}m)`$ the lemma will be proved. The proof is by running the following:

Algorithm: Given $`K(A_0),\mathrm{log}|A_0|,K(A_0x)`$ we run all programs dovetail style. We maintain auxiliary set-variables $`C,U,D`$, all of them initially $`\mathrm{}`$. Every time a new program $`p`$ of length $`K(A_0)`$ in the dovetailing process halts, with as output a set $`A`$ with $`\mathrm{log}|A|=\mathrm{log}|A_0|`$, we execute the following steps:

Update $`U:=UA`$.

Update $`D:=\{yUC`$: $`y`$ is covered by at least $`t=2^{K(A_0x)\delta }`$ different generated $`A`$’s$`\}`$, where $`\delta =O(\mathrm{log}m)`$ will be defined later.

This step is executed only if there is $`yD`$ that is covered by at least $`2t`$ different generated $`A`$’s. Enumerate as much new disjoint sets $`S`$ as are needed to cover $`D`$: we just chop $`D`$ into parts of size $`2^{\mathrm{log}|A_0|}`$ (the last part may be incomplete) and name those parts the new sets $`S`$. Every time a new set $`S`$ is enumerated, update $`C:=CS`$.

###### Claim C.5

The string $`x`$ is an element of some enumerated $`S`$, and the number of enumerated $`S`$’s is at most $`2^{K(A_0)K(A_0x)+O(\mathrm{log}m)}`$.

###### Proof:

By way of contradiction, assume that $`x`$ is not an element of the enumerated $`S`$’s. Then there are less than $`2^{K(A_0x)\delta +1}`$ different generated sets $`A`$ such that $`xA`$. Every such $`A`$ therefore satisfies $`K(Ax)K(A_0x)\delta +O(\mathrm{log}m)<K(A_0x)`$ if $`\delta `$ is chosen appropriately. Since $`A_0`$ was certainly generated this is a contradiction.

It remains to show that we enumerated at most $`2^{K(A_0)K(A_0x)+O(\mathrm{log}m)}`$ different $`S`$’s. Step 3 is executed only once per $`t`$ executions of Step 1, and Step 1 is executed at most $`2^{K(A_0)}`$ times. Therefore Step 3 is executed at most $`2^{K(A_0)}/t=2^{K(A_0)K(A_0x)+\delta }`$ times. The number of $`S`$’s formed from incomplete parts of $`D`$’s in Step 3 is thus at most $`2^{K(A_0)K(A_0)+\delta }`$. Let us bound the number of $`S`$’s formed from complete parts of $`D`$’s. The total number of elements in different $`A`$’s generated is at most $`2^{K(A_0)+\mathrm{log}|A_0|}`$ counting multiplicity. Therefore the number of elements in their union, having multiplicity $`2^{K(A_0x)\delta }`$ or more, is at most $`2^{K(A_0)+\mathrm{log}|A_0|K(A_0x)+\delta }`$. Every $`S`$ formed from a complete part of a set $`D`$ in Step 3 accounts for $`2^{\mathrm{log}|A_0|}`$ of them. Hence the number of $`S`$’s formed from complete parts of $`D`$’s is at most $`2^{K(A_0)K(A_0x)+\delta }`$. ∎

###### Proof:

Theorem IV.11 By Lemma C.4 there is $`Sx`$ with $`K(S)K(A)K(Ax)+O(\mathrm{log}\mathrm{\Lambda }(A))`$ and $`\mathrm{log}|S|=\mathrm{log}|A|`$.

Let us upper bound first $`K(S)`$. We have

$`K(S)`$ $`K(A)K(Ax)=\delta (x|A)+k\mathrm{log}|A|`$
$`=\beta _x(\alpha )+k\mathrm{log}|A|+(\delta (x|A)\beta _x(\alpha ))`$
$`\lambda _x(\alpha )\mathrm{log}|A|+(\delta (x|A)\beta _x(\alpha )).`$
(all inequalities are valid up to $`O(\mathrm{log}\mathrm{\Lambda }(A))`$ additive term). The obtained upper bound is obviosly equivalent to the first upper bound of $`K(S)`$ in the theorem. As $`\mathrm{log}|S|=\mathrm{log}|A|`$ it gives the upper bound of $`\mathrm{\Lambda }(S)`$ from the theorem. Finally, as $`\lambda _x(\alpha )h_x(\alpha )+\alpha +O(1)`$ we obtain $`K(S)\alpha +(h_x(\alpha )\mathrm{log}|A|)+(\delta (x|A)\beta _x(\alpha ))`$ (up to $`O(\mathrm{log}\mathrm{\Lambda }(A))`$ additive term). ∎

###### Proof:

Theorem VIII.2 We first show that $`|m_x^l|K(x)+O(\mathrm{log}l)`$ for every $`x`$ with $`K(x)l`$. Indeed, given $`x`$, $`l`$, $`|m_x^l|`$ and the $`|N^l||m_x^l|`$ least significant bits of $`N^l`$ we can find $`N^l`$: find $`I_x^l`$ by enumerating $`D`$ until a pair $`x,i`$ with $`il`$ appears and then complete $`m_x^l`$ by using the $`|m_x^l|`$ most significant bits of the binary representation of $`I_x^l`$. Given $`l`$ and $`N^l`$ we can find, using a constant-length program, the lexicographically first string not in $`N^l`$. By construction, this string has complexity at least $`l+1`$. Then, $`lK(N^l)+O(\mathrm{log}l)K(x)+|N^l||m_x^l|+O(\mathrm{log}l)K(x)+l|m_x^l|+O(\mathrm{log}l)`$ (use $`|N^l|l+O(1)`$). Thus, $`|m_x^l|K(x)+O(\mathrm{log}l)`$.

Let $`x`$ be the string of complexity at most $`i`$ with maximum $`I_x^l`$. Given $`m_x^l`$ and $`i,l,|N^l|`$ we can find all strings of complexity at most $`i`$ by enumerating $`D`$ until $`N`$ pairs $`y,j`$ with $`jl`$ appear, where $`N`$ is the number whose binary representation has prefix $`m_x^l1`$ and then $`(|N^l||m_x^l|1)`$ zeros. Since $`|m_x^l|i+O(\mathrm{log}l)`$, this proves $`K(N^iN_i^l)=O(\mathrm{log}l)`$. Since $`K(N^i)iO(\mathrm{log}i)K(N_i^l)O(\mathrm{log}i)`$ we have $`K(N_i^lN^i)=O(\mathrm{log}l)`$. ∎

###### Proof:

Theorem VIII.4 (i) If the $`(i+1)`$st most significant bit of $`N^l`$ is “1,” then all the numbers with binary representation of the form $`N_i^l0\mathrm{}`$ are used as indexes of some $`y`$ with $`K(y)l`$, that is, $`S_i^l`$ has exactly $`2^{|N^l|i1}`$ elements. We can find $`S_i^l`$ given $`l`$, $`i`$, $`|N^l|`$ and $`N_i^l`$ by enumerating all its elements. On the other hand, $`N_i^l`$ can be found given $`S_i^l`$ and $`i,l`$ as the first $`i`$ bits of $`I_x^l`$ for every $`xS_i^l`$.

(ii) Since $`i=|m_x^l|`$, the largest common prefix of binary representation of $`I_x^l`$ and $`N^l`$ has the form $`N_i^l0\mathrm{}`$ and the $`(i+1)`$st most significant bit of $`N^l`$ is 1. In particular, $`xS_i^l`$.

Let $`J=\mathrm{max}\{I_y^lyS\}`$. As $`xS`$, we have $`JI_x^l`$. We can find $`N_i^l`$ given $`i`$, $`l`$ and $`S`$ by finding $`J`$ and taking the $`i`$ first bits of $`J`$. Given $`N_i^l`$ we can find $`S_i^l`$. Hence $`K(S_i^lS)=O(\mathrm{log}l)`$. Therefore $`K(S_i^l)K(S)+O(\mathrm{log}l)`$. By Item (i) and by previous theorem we have $`K(S_i^l)=i+O(\mathrm{log}l)`$. Again by Item (i) we have $`\mathrm{\Lambda }(S_i^l)l+O(\mathrm{log}l)=\mathrm{\Lambda }(S)+O(\mathrm{log}l)`$.

(iii) Let $`i=|m_x^l|`$. We distinguish two cases.

Case 1: $`i\alpha `$. Then $`K(N^\alpha S)K(N^\alpha S_i^l)+O(\mathrm{log}l)K(N^\alpha N^i)+O(\mathrm{log}l)=O(\mathrm{log}l)`$. And $`K(SN^\alpha )=K(S)K(N^\alpha )+O(\mathrm{log}l)=K(S)\alpha +O(\mathrm{log}l)`$.

Case 2: $`i<\alpha `$. Let $`A=S_i^l`$. As $`\mathrm{\Lambda }(S_i^l)\mathrm{\Lambda }(S)+O(\mathrm{log}l)`$ we need to prove that $`K(S_i^l)\alpha K(N^\alpha |S)`$ and $`K(S_i^l)K(S)K(S|N^\alpha )`$ up to $`O(\mathrm{log}l)`$ additive term. We have

$`K(S_i^l)`$ $`=K(N^\alpha )K(N^\alpha |S_i^l)+O(\mathrm{log}l)`$
$`\alpha K(N^\alpha |S)+O(\mathrm{log}l)`$
and

$`K(S_i^l)`$ $`=K(S)K(S|S_i^l)+O(\mathrm{log}l)`$
$`K(S)K(S|N^\alpha )+O(\mathrm{log}l).`$
## Appendix D Computability properties

### D-A Structure Function

It is easy to see that $`h_x(\alpha )`$ or $`\lambda _x(\alpha )`$, and the finite set that witnesses its value, are upper semi-computable: run all programs of length up to $`\alpha `$ dovetailed fashion, check whether a halting program produced a finite set containing $`x`$, and replace the previous candidate with the new set if it is smaller.

The next question is: Is the function $`\lambda _x(\alpha )`$, as the function of two arguments, computable? Of course not, because if this were the case, then we could find, given every large $`k`$, a string of complexity at least $`k`$. Indeed, we know that there is a string $`x`$ for which $`\lambda _x(k)>k`$. Applying the algorithm to all strings in the lexicographical order find the first such $`x`$. Obviously $`K(x)kO(1)`$. But it is known that we cannot prove that $`K(x)>k`$ for sufficiently large $`k`$, .

Assume now that we are given also $`K(x)`$. The above argument does not work any more but the statement remains true: $`\lambda _x(\alpha )`$ is not computable even if the algorithm is given $`K(x)`$.

Assume first that the algorithm is required to output the correct answer given any approximation to $`K(x)`$. We show that no algorithm can find $`\lambda `$ that is close to $`\lambda _x(\alpha )`$ for some $`0\alpha K(x)`$.

###### Theorem D.1

For every constant $`c`$ there is a constant $`d`$ such the following holds. There is no algorithm that for infinitely many $`k`$, given $`k`$ and $`x`$ of length $`k+d\mathrm{log}k`$ with $`|K(x)k|2\mathrm{log}k`$, always finds $`\lambda `$ such that there is $`2\mathrm{log}k\alpha k`$ with $`|\lambda _x(\alpha )\lambda |<c\mathrm{log}k`$.

###### Proof:

Fix $`c`$. The value of $`d`$ will be chosen later. The proof is by contradiction. Let $`A`$ be some algorithm. We want to fool it on some pair $`x,k`$.

Fix large $`k`$. We will construct a set $`S`$ of cardinality $`2^{k2\mathrm{log}k}`$ such that every string $`x`$ in $`S`$ has length $`k+d\mathrm{log}k`$ and complexity at most $`k+2\mathrm{log}k`$, and the algorithm halts on $`x,k`$ and outputs $`\lambda (c+1)\mathrm{log}k`$. This is a contradiction. Indeed, there is $`xS`$ with $`K(x)k2\mathrm{log}k`$. Hence the output $`\lambda `$ of $`A`$ on $`x,k`$ is correct, that is, there is $`\alpha `$ with $`2\mathrm{log}k\alpha k`$ and $`|\lambda _x(\alpha )\lambda |<c\mathrm{log}k`$. Then $`\lambda _x(\alpha )>\mathrm{log}k`$. On the other hand, $`\lambda (2\mathrm{log}k)k`$ as witnessed by $`S`$. Thus we obtain

$$k<\lambda _x(\alpha )\lambda _x(2\mathrm{log}k)k,$$

a contradiction.

Run in a dovetailed fashion all programs of length $`k`$ or less. Start with $`x`$ equal to the first string of length $`k+d\mathrm{log}k`$ and with $`S=B=\mathrm{}`$. Run $`A`$ on $`x,k`$ and include in $`B`$ all strings $`x^{}`$ such that either a program $`p`$ of length at most $`k`$ has halted and output a set $`Cx^{}`$ with $`|p|+\mathrm{log}|C|k+(2c+1)\mathrm{log}k`$, or we find out that $`K(x^{})<k2\mathrm{log}k`$. Once $`x`$ gets in $`B`$ we change $`x`$ to the first string of length $`k+d\mathrm{log}k`$ outside $`BS`$. (We will show that at every step it holds $`|BS|<2^{k+d\mathrm{log}k}`$.)

We proceed in this way until $`A(x,k)`$ prints a number $`\lambda `$ or the number of changes of $`x`$ exceed $`2^{k+2}`$. (Actually, we will prove that the number of changes of $`x`$ does not exceed $`2^{k+1}+2^{k2\mathrm{log}k}`$.) Therefore $`K(x)k+2\mathrm{log}k`$ for all our $`x`$’s so we eventually will find $`x`$ such that $`A(x,k)`$ outputs a result $`\lambda `$. If $`\lambda k+(c+1)\mathrm{log}k`$ then include $`x`$ in $`S`$ and then change $`x`$ to the first string of length $`k+d\mathrm{log}k`$ outside (the current version of) $`BS`$. Otherwise, when $`\lambda <k+(c+1)\mathrm{log}k`$, let $`\stackrel{~}{\lambda }_x`$ be the current approximation of $`\lambda _x`$. We know that $`x`$ is outside all known sets $`C`$ with $`K(C)k`$, $`K(C)+\mathrm{log}|C|k+(2c+1)\mathrm{log}k`$. Therefore, for every $`\alpha k`$ it holds $`\stackrel{~}{\lambda }_x(\alpha )>k+(2c+1)\mathrm{log}k`$ and hence $`|\stackrel{~}{\lambda }_x(\alpha )\lambda |>c\mathrm{log}k`$. This implies that either $`K(x)<k2\mathrm{log}k`$ or $`\stackrel{~}{\lambda }_x`$ differs from $`\lambda _x`$. So we are sure that at least one more program of length $`k`$ or less still has to halt. We wait until this happens, then include $`x`$ in $`B`$ and change $`x`$ to the first string of length $`k+d\mathrm{log}k`$ outside $`BS`$.

Once we get $`2^{k2\mathrm{log}k}`$ elements in $`S`$ we halt. Every change of $`x`$ is caused by a halting of a new program of length at most $`k`$ or by including $`x`$ in $`S`$, thus the total number of changes does not exceed $`2^{k+1}+2^{k2\mathrm{log}k}`$.

Note that at every step we have

$$|BS|2^{k2\mathrm{log}k}+2^{k+(2c+1)\mathrm{log}k}+2^{k2\mathrm{log}k}<2^{k+d\mathrm{log}k}$$

provided that $`d>2c+1`$. ∎

What if the algorithm is required to approximate $`\lambda _x`$ only if it is given the precise value of $`K(x)`$? We are able to prove that in this case the algorithm cannot compute $`\lambda _x(\alpha )`$ too. It is even impossible to approximate the complexity of minimal sufficient statistic. To formulate this result precisely consider the following promise problem:

Input: $`x,k=K(x),\alpha [\epsilon ,k\epsilon ]`$.

Output:

1, if $`\lambda _x(\alpha \epsilon )<k+6\mathrm{log}k`$,

0, if $`\lambda _x(\alpha +\epsilon )>k+3\epsilon `$.

If neither of two above cases occurs the algorithm may output any value or no value at all.

###### Theorem D.2

There is no algorithm $`A`$ solving this promise problem for all $`x`$ and $`\epsilon =|x|/10\mathrm{log}|x|`$.

###### Corollary D.3

There is no algorithm that given $`x,k=K(x)`$ finds an integer valued function $`\lambda `$ on $`[0,k]`$ such that $`\lambda _x=(\lambda )`$ for $`\epsilon =\delta =|x|/10\mathrm{log}|x|`$.

Indeed, if there were such algorithm we could solve the above promise problem by answering 1 when $`\lambda (\alpha )k+2\epsilon `$ and 0 otherwise.

###### Proof:

The proof is by contradiction. The idea is as follows. Fix large $`k`$. We consider $`N=O(\mathrm{log}k)`$ points $`\alpha _1,\mathrm{},\alpha _N`$ that divide the segment $`[0,k]`$ into equal parts. We lower semicompute $`\lambda _x`$ and $`K(x)`$ for different $`x`$’s of length about $`k+4\epsilon `$. We are interested in strings $`x`$ with $`\stackrel{~}{\lambda }_x(\alpha _1+\epsilon )>k+3\epsilon `$ where $`\stackrel{~}{\lambda }_x`$ is the current approximation to $`\lambda _x`$. By counting arguments there are many such strings. We apply the algorithm to $`x,\stackrel{~}{K}(x),\alpha _1`$ for those $`x`$’s, where $`\stackrel{~}{K}(x)`$ stands for the currently known upper bound for $`K(x)`$. Assume that $`A(x,\stackrel{~}{K}(x),\alpha _1)`$ halts. If the answer is 1 then we know that $`K(x)<\stackrel{~}{K}(x)`$ or $`\lambda _x(\alpha _1+\epsilon )<\stackrel{~}{\lambda }_x(\alpha _1+\epsilon )`$ and we continue lower semicomputation until we get know which of two values $`\stackrel{~}{K}(x)`$ or $`\stackrel{~}{\lambda }_x(\alpha _1+\epsilon )`$ gets smaller. If the latter is decreased we just remove $`x`$ (the total number of removed $`x`$ will not increase $`2^{k+3\epsilon }`$ and thus they form a small fraction of strings of length $`k+4\epsilon `$). If for many $`x`$’s the answer is 0 we make those answers incorrect by including those $`x`$’s in a set of cardinality $`2^{k\alpha _1+2\epsilon }`$ and complexity $`\alpha _1\epsilon `$. Then for all such $`x`$’s $`\lambda _x(\alpha _1\epsilon )<k+\epsilon `$ and thus algorithm’s answer is incorrect. Hence $`K(x)<\stackrel{~}{K}(x)`$ and we continue lower semicomputation. For all those $`x`$’s for which $`\stackrel{~}{K}(x)`$ is decreased we repeat the trick with $`\alpha _2`$ in place of $`\alpha _1`$. In this way we will force $`\stackrel{~}{K}(x)`$ to decrease very fast for many $`x`$’s. For most of $`x`$’s $`\stackrel{~}{K}(x)`$ will become much less than $`k`$, which is impossible.

Here is the detailed construction. Fix large $`k`$. Let $`N=3\mathrm{log}k`$, $`\delta =k/9\mathrm{log}k`$ (one third of the distance between consecutive $`\alpha _i`$), $`\alpha _i=k3\delta i+\delta `$, $`n=k+4\delta `$ (the length of $`x`$). The value of parameter $`\epsilon `$ is chosen to be slightly less than $`\delta `$ (we will need that $`\delta >\epsilon +4\mathrm{log}k`$ for large enough $`k`$).

We will run all the programs of length at most $`k^{}=k+2\mathrm{log}k`$ and the algorithm $`A`$ on all possible inputs in a dovetailed fashion.

We will define a set $`X`$ of $`2^k`$ strings of length $`n`$. Our action will be determined by $`k`$ only, hence $`K(x)k+2\mathrm{log}k=k^{}`$ for every $`xX`$ provided $`k`$ is large enough. We will also define some small sets $`B_l`$ for $`l=1,\mathrm{},N`$, the sets of “bad” strings and $`B`$ will denote their union. Every $`B_l`$ will have at most $`2^{k\delta }`$ elements. We start with $`B_l=\mathrm{}`$ for $`l=1,\mathrm{},N`$.

We make $`2^k`$ stages. At every stage consider the sets

$`X_l`$ $`=\{xXB:\stackrel{~}{K}(x)=k^{}+1l\}\text{ for }l=1,\mathrm{},N,`$
$`X_0`$ $`=\{xXB:\stackrel{~}{K}(x)>k^{}\}.`$
Before and after every stage the following invariant will be true.

* $`|X_l|<2^{3\delta l}`$ for every $`0lN`$; in particular $`X_0=\mathrm{}`$.
* For all $`1lN`$ for all $`xX_l`$ it holds $`A(x,\stackrel{~}{K}(x),\alpha _l)=0`$.
* For all $`0l<iN`$ and all $`xX_l`$ it holds $`\stackrel{~}{\lambda }_x(\alpha _i+\delta )>k+3\delta `$.
* $`|B_i|2^{3i\delta 3\delta +1}\times `$(the number of programs of length at most $`k3i\delta +2\delta `$ that have halted so far).

At the start all $`X_l`$’s and $`B_i`$’s are empty so the invariant is true. Each stage starts by including a new element in $`X`$. This element is the first string $`x_0`$ of length $`n=k+4\delta `$ outside $`X`$ such that $`\stackrel{~}{\lambda }_x(\alpha )>k+3\delta `$ for all $`\alpha k`$. Thus by the choice of $`x_0`$ the assertions (3) and (4) remain true but (1) and (2) may not.

We claim that continuing the dovetailing and updating properly $`B_i`$’s we eventually make every one of (1), (2), (3) and (4) true. During the dovetailing the sets $`X_l`$ change (an element can move from $`X_l`$ to $`X_i`$ for $`i>l`$ and even to $`X(X_0\mathrm{}X_N)`$). We will denote by $`\stackrel{~}{X}_l`$ the version of $`X_l`$ at the beginning of the stage (and $`\stackrel{~}{X}_0=\{x_0\}`$) and keep the notations $`X_l,B_i`$ for current versions of $`X_l,B_i`$, respectively. The rule to update $`B_i`$’s is very simple: once at some step of the dovetailing a new set $`C`$ of complexity at most $`k3i\delta +2\delta =\alpha _i+\delta `$ appears, we include in $`B_i`$ all the elements of the set $`_{j=0}^{i1}\stackrel{~}{X}_j`$. As $`X_l_{j=0}^l\stackrel{~}{X}_j`$ this keeps (3) true. Moreover, this keeps true also the following assertion:

* For all $`1lN`$ for all $`xX_l\stackrel{~}{X}_l`$ it holds $`\stackrel{~}{\lambda }_x(\alpha _l+\delta )>k+3\delta `$.

And this also keeps (4) true since $`_{j=0}^{i1}|\stackrel{~}{X}_j|<1+_{j=1}^{i1}2^{3\delta j}<2^{3\delta (i1)+1}`$.

We continue the dovetailing and update $`B_i`$’s as described until both $`(1)`$ and $`(2)`$ are true. Let us prove that this happens eventually. It suffices to show that if $`(3)`$, (4) and (5) are true but $`(2)`$ is not, or $`(2)`$, (3), (4) and (5) are true but $`(1)`$ is not then at least one program of length $`k^{}`$ will halt or $`A(x,\stackrel{~}{K}(x),\alpha _l)`$ is undefined for some $`l`$ and some $`xX_l`$.

Consider the second case: $`(2)`$, (3), (4) and (5) are true but $`(1)`$ is not. Pick $`l`$ such that $`|X_l|2^{3\delta l}`$. If $`l=0`$, that is, $`\stackrel{~}{K}(x_0)>k^{}`$, we are done, as $`K(x_0)k^{}`$. Otherwise, let $`S`$ consist of the first $`2^{3\delta l}`$ elements in $`X_l`$. We claim that $`K(S)k3l\delta +4\mathrm{log}k\alpha _l\epsilon `$. To prove the claim we will show that all $`SX_l`$ obtained in this way are pairwise disjoint, therefore their number is at most $`2^k/2^{3l\delta }`$. Thus $`S`$ may be identified by $`k,l`$ and its index among all such $`SX_l`$.

Therefore for all $`xS`$ we have $`\lambda _x(\alpha _l\epsilon )<k+4\mathrm{log}k<\stackrel{~}{K}(x)+6\mathrm{log}\stackrel{~}{K}(x)`$ and the value $`A(x,\stackrel{~}{K}(x),\alpha _l)=0`$ is not correct. This implies that $`\stackrel{~}{K}(x)`$ is not correct for all $`xS`$. We continue the dovetailing until all elements of $`S`$ move outside $`X_l`$. Then $`S`$ becomes disjoint with $`X_0\mathrm{}X_l`$ and therefore it will be disjoint with all future versions of $`X_l`$.

Consider the first case: $`(3)`$, (4) and (5) are true but $`(2)`$ is not. Pick $`l`$ and $`xX_l`$ such that $`A(x,\stackrel{~}{K}(x),\alpha _l)`$ is undefined or $`A(x,\stackrel{~}{K}(x),\alpha _l)=1`$. If $`A(x,\stackrel{~}{K}(x),\alpha _l)`$ is undefined then we are done: since $`\stackrel{~}{\lambda }_x(\alpha _l+\epsilon )\stackrel{~}{\lambda }_x(\alpha _l+\delta )>k+3\delta >\stackrel{~}{K}(x)+3\epsilon `$, either $`\stackrel{~}{\lambda }_x`$ or $`\stackrel{~}{K}`$ will decrease, or $`A(x,\stackrel{~}{K}(x),\alpha _l)`$ will get defined. Consider the other case. Obviously $`xX_l\stackrel{~}{X}_l`$. By (5) we have $`\stackrel{~}{\lambda }_x(\alpha _l+\epsilon )\stackrel{~}{\lambda }_x(\alpha _l+\delta )>k+3\delta \stackrel{~}{K}(x)+3\epsilon `$. Therefore $`\lambda _x(\alpha _l+\delta )<\stackrel{~}{\lambda }_x(\alpha _l+\delta )`$ or $`\stackrel{~}{K}(x)<K(x)`$ and we are done.

After $`2^k`$ stages the set $`|X|`$ has $`2^k`$ elements and we have a contradiction. Indeed, all $`X_1,\mathrm{},X_N`$ form a very small part of $`X`$ because of (1). The sets $`B_1,\mathrm{},B_N`$ together form also a very small part of $`X`$ because of (4). Thus for most strings $`xX`$ it holds $`\stackrel{~}{K}(x)<k^{}N+1k`$ which is a contradiction. ∎

###### Remark D.4

Let us replace in the above promise problem $`K(x)`$, the prefix complexity of $`x`$, by $`C(x)`$, the plain complexity of $`x`$. For the modified problem we can strengthen the above theorem by allowing $`\epsilon =|x|/c`$ where the constant $`c`$ depends on the reference computer. Indeed for every $`xX`$ we have $`C(x)k+O(1)`$: every $`xX`$ can be described by its index in $`X`$ in exactly $`k`$ bits and the value of $`k`$ may be retrieved from the length of the description of $`x`$. Therefore we will need $`N=O(1)`$ to obtain a contradiction. $`\mathrm{}`$

After a discussion of these results, Andrei A. Muchnik suggested, and proved, that if we are also given an $`\alpha _0`$ such that $`\lambda _x(\alpha _0)K(x)`$ but $`\lambda _x(\alpha )`$ is much bigger than $`K(x)`$ for $`\alpha `$ much less than $`\alpha _0`$ (which is therefore the complexity of the minimal sufficient statistic), then we can compute $`\lambda _x`$ over all of its domain. This result underlines the significance of the information contained in the minimal sufficient statistic:

###### Theorem D.5

There are a constant $`c0`$ and an algorithm that given any $`x,k,\alpha _0`$ with $`K(x)k\lambda _x(\alpha _0)`$ finds a non-increasing function $`\lambda `$ defined on $`[0,k]`$ such that $`\lambda _x=(\lambda )`$ with $`\delta =\lambda _x(\alpha _0)K(x)+O(1)`$ and $`\epsilon =\alpha _0\alpha _1+c\mathrm{log}k`$ where $`\alpha _1=\mathrm{min}\{\alpha :\lambda _x(\alpha )k+c\mathrm{log}k\}`$.

###### Proof:

The algorithm is a follows. Let $`D_k=\{y,iK(y)ik\}D`$. Enumerate pairs $`y,iD_k`$ until a pair $`x,i_0`$ appears and form a list of all enumerated pairs. For $`\alpha \alpha _0`$ define $`\lambda (\alpha )`$ to be the minimum $`i+\mathrm{log}|S|`$ over all $`Sx`$ such that a pair $`x,i`$ with $`i\alpha `$ is in the list. For $`\alpha _0<\alpha k`$ let $`\lambda (\alpha )=k`$.

For every $`\alpha >\alpha _0`$ we have $`\lambda _x(\alpha )K(x)O(1)k\lambda _x(\alpha _0)+K(x)O(1)=\lambda (\alpha )\delta `$ and $`\lambda _x(\alpha )\lambda _x(\alpha _0)k+(\lambda _x(\alpha _0)K(x))\lambda (\alpha )+\delta `$.

For every $`\alpha \alpha _0`$ we have $`\lambda _x(\alpha )\lambda (\alpha )`$. So it remains to show that for every $`\epsilon \alpha \alpha _0`$ we have $`\lambda (\alpha )\lambda _x(\alpha \epsilon )+\delta `$. We will prove a stronger statement: $`\lambda (\alpha )=\lambda _x(\alpha )`$ for every $`\alpha \alpha _0\epsilon `$ provided $`c`$ is chosen appropriately. To prove this it suffices to show that all for all $`S`$ with $`K(S)\alpha _0\epsilon `$ the pair $`S,K(S)`$ belongs to the list.

By Theorem VIII.4 Item (i) we have $`\lambda _x(|m_x^k|+c_1\mathrm{log}k)k+c_2\mathrm{log}k`$. That is, $`\alpha _1|m_x^k|+c_1\mathrm{log}k`$ if $`cc_2`$ and $`\alpha _0\epsilon =\alpha _0\alpha _0+\alpha _1c\mathrm{log}k|m_x^k|+(c_1c)\mathrm{log}k`$.

From the proof of Theorem VIII.2 we see that there is a constant $`c_3`$ such that for every $`y`$ with $`K(y)|m_x^k|c_3\mathrm{log}k`$ the index of $`y,K(y)`$ in the enumeration of $`D_k`$ has less than $`|m_x^k|`$ common bits with $`N^k`$. Assuming that $`cc_1+c_3`$ we obtain that the indexes of all pairs $`y,K(y)`$ with $`K(y)\alpha _0\epsilon `$ in the enumeration of $`D_k`$ are less than $`I_x^k`$. ∎

### D-B Randomness Deficiency Function

The function $`\beta _x(\alpha )`$ is computable from $`x,\alpha `$ given an oracle for the halting problem: run all programs of length $`\alpha `$ dovetailed fashion and find all finite sets $`S`$ containing $`x`$ that are produced. With respect to all these sets determine the conditional complexity $`K(xS^{})`$ and hence the randomness deficiency $`\delta (xS)`$. Taking the minimum we find $`\beta _x(\alpha )`$. All these things are possible using information from the halting problem to determine whether a given program will terminate or not. It is also the case that the function $`\beta _x(\alpha )`$ is upper semi-computable from $`x,\alpha ,K(x)`$ up to a logarithmic error: this follows from the semi-computability of $`\lambda _x(\alpha )`$ and Theorem IV.8. More subtle is that $`\beta _x`$ is not semi-computable, not even within a large margin of error:

###### Theorem D.6

The function $`\beta _x(\alpha )`$ is

(i) not lower semi-computable to within precision $`|x|/3`$; and

(ii) not upper semi-computable to within precision $`|x|/\mathrm{log}^4|x|`$.

###### Proof:

(i) The proof is by contradiction. Assume Item (i) is false. Choose an arbitrary length $`n`$. Let $`\beta `$ be a function defined by $`\beta (i)=\frac{n}{2}`$ for $`0i\frac{n}{3}`$, and equal 0 otherwise. Then the function $`\beta _x`$ with $`x`$ of length $`n`$, corresponding to $`\beta `$, by Corollary IV.9, has $`x`$ with $`k=K(x)`$ satisfying $`\beta (0)=nk\pm O(\mathrm{log}n)`$ so that $`k=\frac{n}{2}\pm O(\mathrm{log}n)`$. Moreover, $`\beta _x(i)=\frac{n}{2}\pm O(\mathrm{log}n)`$ for $`O(\mathrm{log}n)<i\frac{n}{3}O(\mathrm{log}n)`$, and $`\beta _x(i)=O(\mathrm{log}n)`$ for $`i>\frac{n}{3}+O(\mathrm{log}n)`$. Write the set of such $`x`$’s as $`X`$. By dovetailing the lower approximation of $`\beta _x(i)`$ for all $`x`$ of length $`n`$ and some $`i`$ with $`\frac{n}{8}i\frac{n}{4}`$, by assumption on lower semi-computability of $`\beta _x`$, we must eventually find an $`x`$, if not $`xX`$ then $`xX`$, for which the lower semi-computation of $`\beta _x(i)`$ exceeds $`\frac{n}{2}\frac{n}{3}O(\mathrm{log}n)`$. But we know from Corollary IV.9 that $`\beta _x(i)=O(\mathrm{log}n)`$ for $`i>K(x)+O(\mathrm{log}n)`$, and hence we have determined that $`iO(\mathrm{log}n)<K(x)`$. Therefore, $`K(x)>\frac{n}{8}O(\mathrm{log}n)`$. But this contradicts the well-known fact  that there is no algorithm that for any given $`n`$ finds a string of complexity at least $`f(n)`$ where $`f`$ is a computable total unbounded function.

(ii) The proof is by contradiction. Assume Item (ii) is false. Fix a large length $`n=2^k`$ and let $`A_1=\{0,1\}^n`$, so that $`\alpha =2\mathrm{log}kK(A_1)`$. Let $`x`$ be a string of length $`n`$, let $`N^\alpha <2^{\alpha +1}`$ be the number of halting programs of length at most $`\alpha `$, and let $`𝒜=\{A_1,\mathrm{},A_m\}`$ be the set of all finite sets of complexity at most $`\alpha `$. Since $`xA_1`$, the value $`\beta _x(\alpha )`$ is finite and $`\beta _x(\alpha )=\mathrm{min}_{A𝒜}\{\delta (xA)\}.`$ Assuming $`\beta _x`$ is upper semi-computable, we can run the following algorithm:

Algorithm: Given $`N^\alpha `$, $`\alpha `$, and $`x`$,

Step 1: Enumerate all finite sets $`𝒜=\{A_1,\mathrm{},A_m\}`$ of complexity $`K(A_i)\alpha `$. Since we are given $`N^\alpha ,\alpha `$ we can list them exhaustively.

Step 2: Dovetail the following computations simultaneously:

Step 2.1: Upper semi-compute $`\beta _x(\alpha )`$, for all $`x`$ of length $`n`$.

Step 2.2: For all $`i=1,\mathrm{},m`$, lower semi-compute $`\delta (xA_i)=\mathrm{log}|A_i|K(xA_i)`$.

We write the approximations at the $`t`$th step as $`\beta _x^t(\alpha )`$, $`\delta ^t(xA_i)`$, and $`K^t(xA_i)`$, respectively. We continue the computation until step $`t`$ such that

$$\beta _x^t(\alpha )<\underset{A𝒜}{\mathrm{min}}\{\delta ^t(xA)\}+n/\mathrm{log}^4n.$$

This $`t`$ exists by the assumption above. By definition, $`\mathrm{min}_{A𝒜}\{\delta (xA)\}=\beta _x(\alpha )\beta _x^t(\alpha )`$. Let $`A^x`$ denote the set minimizing the right-hand side. (Here we use that $`x`$ belongs to a set in $`𝒜`$.) Together, this shows that $`\mathrm{log}|A^x|\beta _x^t(\alpha )K(xA^x)`$ and $`\mathrm{log}|A^x|\beta _x^t(\alpha )K^t(xA^x)n/\mathrm{log}^4nK(xA^x)n/\mathrm{log}^4n)`$. Thus we obtained an estimation $`\mathrm{log}|A^x|\beta _x^t(\alpha )`$ of $`K(xA^x)`$ with precision $`n/\mathrm{log}^4n`$. We use that $`K(xA^x)`$ is a good approximation to $`K(x)`$:

$`K(xA^x)c_1`$ $`K(x)K(xA^x)+|A^x|+c_1`$
$`K(xA^x)+\alpha +c_1,`$
where $`c_1`$ is a constant. Consequently,

$$K(K(x)x)K(N^\alpha ,\alpha ,K(x)\mathrm{log}|A^x|+\beta _x^t(\alpha ))+c_2.$$

where the constant $`c_2`$ is the length of a program to reconstruct $`\alpha ,N^\alpha `$ and $`K(x)\mathrm{log}|A^x|+\beta _x^t(\alpha )\alpha +c_1+n/\mathrm{log}^4n`$, and combining this information with the conditional information $`x`$, to compute $`K(x)`$. Observing $`K(N^\alpha )=\alpha K(\alpha )+O(1)`$ by , and substituting $`\alpha =2\mathrm{log}\mathrm{log}n`$, there is a constant $`c_3`$ such that

$$K(K(x)x)2\mathrm{log}\mathrm{log}n+\mathrm{log}n4\mathrm{log}\mathrm{log}n+c_3.$$

However, for every $`n`$, we can choose an $`x`$ of length $`n`$ such that $`K(K(x)x)\mathrm{log}n\mathrm{log}\mathrm{log}n`$ by , which gives the required contradiction. ∎

Open question. Is there a non-increasing (with respect to $`\alpha `$) upper semi-computable function $`f_x(\alpha )`$ such that, for all $`x`$, $`\beta _x(\alpha )=(f_x(\alpha ))`$ for $`\epsilon =\delta =O(\mathrm{log}|x|)`$ (or for $`\epsilon =\delta =o(|x|)`$)?

## Acknowledgment

We thank Harry Buhrman, Marcus Hütter, Andrei A. Muchnik, Osamu Watanabe, for helpful discussions, and Tom Cover, Péter Gács, and Leonid A. Levin for historical details about Kolmogorov’s original proposal of the structure function in the early seventies and about their own unpublished work on the subject. After the first author questioned Muchnik whether the result in Theorem IV.8 was perhaps known before, the latter answered negatively and supplied an independent proof of it. He also suggested and proved Theorem D.5. Watanabe suggested the question treated in Section IV-C.

## Biographies

Nikolai K. Vereshchagin is Professor (Chair of Mathematical Logic and Theory of Algorithms) at Moscow State University. He has worked on algorithms in number theory, decidable theories, computational complexity, Kolmogorov complexity. Together with Alexander Shen he co-authored “Computable Functions” and “Basic Set Theory”, MCNMO, Moscow, 1999, in Russian, both of which have been published by the American Mathematical Society in English translation.

Paul M.B. Vitányi is a Fellow of the Center for Mathematics and Computer Science (CWI) in Amsterdam and Professor of Computer Science at the University of Amsterdam. He serves on the editorial boards of Distributed Computing (until 2003), Information Processing Letters, Theory of Computing Systems, Parallel Processing Letters, International Journal of Foundations of Computer Science, Journal of Computer and Systems Sciences (guest editor), and elsewhere. He has worked on cellular automata, computational complexity, distributed and parallel computing, machine learning and prediction, physics of computation, Kolmogorov complexity, quantum computing. Together with Ming Li they pioneered applications of Kolmogorov complexity and co-authored “An Introduction to Kolmogorov Complexity and its Applications,” Springer-Verlag, New York, 1993 (2nd Edition 1997), parts of which have been translated into Chinese, Russian and Japanese.