{'fraction_non_alphanumeric': 0.05527024126030021, 'fraction_numerical': 0.010799742391465892, 'mean_word_length': 3.7053613053613055, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 36, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

We examine the structure of families of distortion balls from the perspective of Kolmogorov complexity. Special attention is paid to the canonical rate-distortion function of a source word which returns the minimal Kolmogorov complexity of all distortion balls containing that word subject to a bound on their cardinality. This canonical rate-distortion function is related to the more standard algorithmic rate-distortion function for the given distortion measure. Examples are given of list distortion, Hamming distortion, and Euclidean distortion. The algorithmic rate-distortion function can behave differently from Shannon's rate-distortion function. To this end, we show that the canonical rate-distortion function can and does assume a wide class of shapes (unlike Shannon's); we relate low algorithmic mutual information to low Kolmogorov complexity (and consequently suggest that certain aspects of the mutual information formulation of Shannon's rate-distortion function behave differently than would an analogous formulation using algorithmic mutual information); we explore the notion that low Kolmogorov complexity distortion balls containing a given word capture the interesting properties of that word (which is hard to formalize in Shannon's theory) and this suggests an approach to denoising; and, finally, we show that the different behavior of the rate-distortion curves of individual source words to some extent disappears after averaging over the source words.


I. INTRODUCTION
Rate distortion theory analyzes the transmission and storage of information at insufficient bit rates. The aim is to minimize the resulting information loss expressed in a given distortion measure. The original data is called the 'source word' and the encoding used for transmission or storage is called the 'destination word.' The number of bits available for a destination word is called the 'rate.' The choice of distortion measure is usually a selection of which aspects of the source word are relevant in the setting at hand, and which aspects are irrelevant (such as noise).
For example, in application to lossy compression of a sound file this results in a compressed file where, among others, the very high and very low inaudible frequencies have been suppressed. The distortion measure is chosen such that it penalizes the deletion of the inaudible frequencies but lightly because they are not relevant for the auditory experience. We study rate distortion of individual source words using Kolmogorov  Appendix E gives the proof, required for a Hamming distortion example, that every large Hamming ball can be covered by a small number of smaller Hamming balls (each of equal cardinality). More specifically, the number of covering balls is close to the ratio between the cardinality of the large Hamming ball and the small Hamming ball.
The proofs of the theorems are deferred to Appendix F.

A. Related Work
In [8] A.N. Kolmogorov formulated the 'structure function' which can be viewed as a proposal for nonprobabilistic model selection. This function and the associated Kolmogorov sufficient statistics are partially treated in [19], [24], [6] and analyzed in detail in [22]. We will show that the structure function approach can be generalized to give an approach to rate distortion and denoising of individual data.
Classical rate-distortion theory was initiated by Shannon in [17]. In [18] Shannon gave a nonconstructive asymptotic characterization of the expected rate-distortion curve of a random variable (Theorem 5 in Appendix A).
References [1], [2] treat more general distortion measures and random variables in the Shannon framework.
References [25], [13], [20] relate the classical and algorithmic approaches according to traditional informationtheoretic concerns. We follow their definitions of the rate-distortion function. The results show that if the source word is obtained from random i.i.d. sources, then with high probability and in expectation its individual ratedistortion curve is close to the Shannon's single rate-distortion curve. In contrast, our Theorem 1 shows that for distortion measures satisfying properties 1 through 4 below there are many different shapes of individual ratedistortion functions related to the different individual source words, and many of them are very different from Shannon's rate-distortion curve.
Also Ziv [26] considers a rate-distortion function for individual data. The rate-distortion function is assigned to every infinite sequence ω of letters of a finite alphabet Γ. The source words x are prefixes of ω and the encoding function is computed by a finite state transducer. Kolmogorov complexity is not involved.
In [22] Theorems 1, 3 were obtained for a particular distortion measure relevant to model selection (the example L in this paper). The techniques used in that paper do not generalize to prove the current theorems which concern arbitrary distortion measures satisfying certain properties given below.

B. Results
A source word is taken to be a finite binary string. Destination words are finite objects (not necessarily finite binary strings). For every destination word encoding a particular source word with a certain distortion, there is a finite set of source words that are encoded by this destination word with at most that distortion. We call these finite sets of source words 'distortion balls.' Our approach is based on the Kolmogorov complexity of distortion balls. DRAFT For every source word we define its 'canonical' rate-distortion function, from which the algorithmic rate-distortion function of that source word can be obtained by a simple transformation, Lemma 2.
Below we assume that a distortion measure satisfies certain properties which are specified in the theorems concerned. In Theorem 1 it is shown that there are distinct canonical rate-distortion curves (and hence distinct rate-distortion curves) associated with distinct source words (although some curves may coincide). Moreover, every candidate curve from a given family of curves is realized approximately as the canonical rate-distortion curve (and hence for a related family of curves every curve is realized approximately as the rate-distortion curve) of some source word. In Theorem 2 we prove a Kolmogorov complexity analogue for Shannon's theorem, Theorem 5 in Appendix A, on the characterization of the expected rate-distortion curve of a random variable. The new theorem states approximately the following: For every source word and every destination word there exists another destination word that has Kolmogorov complexity equal to algorithmic information in the first destination word about the source word, up to a logarithmic additive term, and both destination words incur the same distortion with the source word.
(The theorem is given in the distortion-ball formulation of destination words.) In Theorem 3 we show that, at every rate, the destination word incurring the least distortion is in fact the 'best-fitting' among all destination words at that rate. 'Best-fitting' is taken in the sense of sharing the most properties with the source word. (This notion of a 'best-fitting' destination word for a source word can be expressed in Kolmogorov complexity, but not in the classic probabilistic framework. Hence there is no classical analogue for this theorem.) It turns out that this yields a method of denoising by compression. Finally, in Theorem 4, we show that the expectation of the algorithmic rate-distortion functions is pointwise related to Shannon's rate-distortion function, where the closeness depends on the Kolmogorov complexities involved and ergodicity and stationarity of the source.

A. Data and Binary Strings
We write string to mean a finite binary string. Other finite objects can be encoded into strings in natural ways.
Then, |010| = 3. The emphasis is on binary sequences only for convenience; observations in every finite alphabet can be so encoded in a way that is 'theory neutral'. For example, if a finite alphabet Σ has cardinality 2 k , then every element i ∈ Σ can be encoded by σ(i) which is a block of bits of length k. With this encoding every x ∈ Σ * satisfies that the Kolmogorov complexity C(x) = C(σ(x)) (see Appendix C for basic definitions and results on Kolmogorov complexity) up to an additive constant that is independent of x.

B. Rate-Distortion Vocabulary
Let X be a set, called the source alphabet whose elements are called source words or messages. We also use a set Y called the destination alphabet, whose elements are called destination words. (The destination alphabet is also called the reproduction alphabet.) In general there are no restrictions on the set X ; it can be countable or uncountable. However, for technical reasons, we assume X = {0, 1} * . On the other hand, it is important that the set Y consists of finite objects: we need that the notion of Kolmogorov complexity C(y) be defined for all y ∈ Y.
(Again, for basic definitions and results on Kolmogorov complexity see Appendix C.) In this paper it is not essential whether we use plain Kolmogorov complexity or the prefix variant; we use plain Kolmogorov complexity.
Suppose we want to communicate a source word x ∈ X using a destination word y ∈ Y that can be encoded in at most r bits in the sense that the Kolmogorov complexity C(y) ≤ r. Assume furthermore that we are given a distortion function d : X × Y → R {∞}, that measures the fidelity of the destination word against the source word. Here R denotes the nonnegative real numbers, DEFINITION 1: Let x ∈ X = {0, 1} * and Q denote the rational numbers. The rate-distortion function r x : Q → N is the minimum number of bits in a destination word y to obtain a distortion of at most δ defined by The 'inverse' of the above function is is the distortion-rate function d x : N → R and is defined by These functions are analogs for individual source words x of the Shannon's rate-distortion function defined in (8) and its related distortion-rate function, expressing the least expected rate or distortion at which outcomes from a random source X can be transmitted, see Appendix A.

C. Canonical Rate-Distortion Function
Let X = {0, 1} * be the source alphabet, Y a destination alphabet, and d a distortion measure.
DEFINITION 2: A distortion ball B(y, δ) centered on y ∈ Y with radius δ ∈ Q is defined by and its cardinality is denoted by b(y, δ) = |B(y, δ)|. (We will consider only pairs (Y, d) such that all distortion balls are finite.) If the cardinality b(y, δ) depends only on δ but not on the center y, then we denote it by b(δ). The family A d,Y is defined as the set of all nonempty distortion balls. The restriction to strings of length n is denoted by A d,Y n . To define the canonical rate-distortion function we need the notion of the Kolmogorov complexity of a finite set. DEFINITION 3: Fix a computable total order on the set of all strings (say the order defined in (1)). The Kolmogorov complexity C(A) of a finite set is defined as the length of the shortest string p such that the universal reference Turing machine U given p as input prints the list of all elements of A in the fixed order and halts. We require DRAFT that the constituent elements are distinguishable so that we can tell them apart. Similarly we define the conditional versions C(A | z) and C(z | A) where A is a finite set of strings and z is a string or a finite set of strings. REMARK 1: In Definition 3 it is important that U (p) halts after printing the last element in the list-in this way we know that the list is complete. If we allowed U (p) to not halt, then we would obtain the complexity of the so-called implicit description of A, which can be much smaller than C(A). ♦ A ∈ A}).
REMARK 3: An equivalent definition of C(A | z) and C(z | A) as in Definition 3 is as follows. Let φ be as in . ♦ DEFINITION 5: For every string x the canonical rate-distortion function g x : N → N is defined by In a similar way we can define the canonical distortion-rate function: The restriction to source words of length n is denoted by A n .
Every destination alphabet Y and distortion measure d gives rise to a set of distortion balls A d,Y , which is a distortion family. Thus the class of distortion families obviously includes every family of distortion balls (or distortion spheres, which is sometimes more convenient) arising from every combination of destination set and distortion measure. It is easy to see that we also can substitute the more general distortion families A for A d,Y in the definitions of the canonical rate-distortion and distortion-rate function.
In general, the canonical rate-distortion function of x can be quite different from the rate-distortion function of x. However, by Lemma 2 below it turns out that for every distortion measure satisfying certain conditions and for every x the rate-distortion function r x is obtained from g x by a simple transformation requiring the cardinality of the distortion balls.
REMARK 4: Fix a string x ∈ X = {0, 1} * and consider different distortion families A. Let g A x denote the canonical rate-distortion function of x with respect to a family A. Obviously, if A ⊂ B then g A x is pointwise not less than g B x (and it may happen that g A x (i) ≫ g B x (i) for some i). But as long as A satisfies certain natural properties, then the set of all possible g x , when x ranges over X , does not depend on the particular A involved, see Theorem 1.  The smaller the covering coefficient is, the more accurate will be the description that we obtain of the shapes of the structure functions below.
The following three example families A satisfy all four properties. x = x 1 . . . x n and y = y 1 . . . y n is defined by DRAFT If x and y have different lengths, then d(x, y) = ∞. A Hamming ball in {0, 1} n with center y ∈ {0, 1} n and radius δ (0 ≤ δ ≤ 1) is the set B(y, δ) = {x ∈ {0, 1} n : d(x, y) ≤ δ}. Every x is in either B(00 . . . 0, 1 2 ) or B(11 . . . 1, 1 2 ), so we need to consider only Hamming distance 0 ≤ δ ≤ 1 2 . Let H n be the family of all Hamming balls in {0, 1} n . We will use the following approximation of b(δ)-the cardinality of Hamming balls in H n of radius δ. Suppose that 0 ≤ δ ≤ 1 2 and δn is an integer, and let H(δ) = δ log 1/δ + (1 − δ) log 1/(1 − δ) be Shannon's binary entropy function. Then, In Appendix E it is shown that the covering coefficient as defined in property 4, for the Hamming distortion family  Trivially, the covering coefficient as defined in property 4, for the Euclidean distortion family E n , satisfies α n ≤ 2.

IV. SHAPES
The rate-distortion functions of the individual strings of length n can assume roughly every shape. That is, every shape derivable from a function in the large family G n of Definition 5 below through transformation (4).
We start the formal part of this section. Let A be a distortion family satisfying properties 1 through 4.
Property 1 implies that {0, 1} n ∈ A and property 4 applied to {0, 1} n and c = 1, for every n, implies trivially that the family A contains the singleton set {x} for every x ∈ {0, 1} * . Hence, Property 1 implies that for every n and string x of length n, DRAFT Together this means that for every n and every string x of length n, the function g x (l) decreases from about C(x) to about 0 as l increases from 0 to n. there is a covering of A by at most α n |A|/2 l sets in A n of cardinality at most 2 l each. Given a list of A and a list of A n , we can find such a covering. Let B be one of the covering sets containing x. Then, x can be specified by A, n, l, A n and the index i of B among the covering sets. We need also O(log k + log log i + log log l + log log n) extra bits to separate the descriptions of A and A n , and the binary representations of i, n, l, from one another.
Without loss of generality we can assume that k is less than n. Thus all the extra information and separator bits EXAMPLE 4: Lemma 1 shows that for every 0 ≤ i ≤ n. The right-hand inequality is obtained by setting m = n, l = i in the lemma, yielding The left-hand inequality is obtained by setting l = 0, m = i in the lemma, yielding The last displayed equation can also be shown by a simple direct argument: x can be described by the minimal description of the set A ∈ A witnessing g x (i) and by the ordinal number of x in A. ♦ The rate-distortion function r x differs from g x by just a change of scale depending on the distortion family involved, provided certain computational requirements are fulfilled. See Appendix B for computability notions.
LEMMA 2: Let X = {0, 1} * , Y, and d, be the source alphabet, destination alphabet, and distortion measure, Proof: Fix n and a string x of length n. Consider the auxiliary functioñ We claim thatr x (δ) = r x (δ)+O(C(δ)+log n). Indeed, let y witness r x (δ) = k. Given y, δ, n we can compute a list of elements of the ball B(y, δ): for all strings x ′ of length n determine whether d(x ′ , y) ≤ δ. Thus C(B(y, δ)) < Given a list of the elements of B(y, δ) and δ we can recursively enumerate Y to find the first element y ′ with B(y ′ , δ) = B(y, δ) (for every enumerated y ′ compute the list B(y ′ , δ) and compare it to the given list B(y, δ)). Then, Thus, it suffices to show thatr (g x (⌈log b n (δ)⌉) ≤r x (δ)) Assumer x (δ) = k is witnessed by a distortion ball B(y, δ). By our assumption, the Therefore it suffices to show thatr We claim that this . This implies that the radius of B is less than δ and hence B witnesses REMARK 5: When measuring distortion we usually do not need rational numbers with numerator or denominator more than n = |x|. Then, the term O(C(δ)) in (4) is absorbed by the term O(log n). Thus, describing the family of g x 's we obtain an approximate description of all possible rate-distortion functions r x for given destination alphabet and distortion measure, satisfying the computability conditions, by using the transformation (4). An example of an approximate rate-distortion curve r x for some string x of length n for Hamming distortion is given in Figure 1. ♦ REMARK 6: The computability properties of the functions r x , d x , and g x , as well as the relation between the destination word for a source word and the related distortion ball, is explained in Appendix B. ♦ We present an approximate description of the family of possible g x 's below. It turns out that the description does not depend on the particular distortion family A as long as properties 1 through 4 are satisfied.
DEFINITION 7: Let G n stand for the class of all functions g : {0, 1, . . . , n} → N such that g(n) = 0 and In other words, a function g is in G n iff it is nonincreasing and the function g(i) + i is nondecreasing and (i) For every n and every string x of length n, the function g x (l) is equal to g(l) + O(log n) for some function g ∈ G n .
(ii) Conversely, for every n and every function g in G n , there is a string x of length n such that for every l = 0, . . . , n, g x (l) = g(l) + O( √ n log n).
REMARK 7: For fixed k ≤ n the number of different integer functions g ∈ G n with g(0) = k is n k . For k = 1 2 n, this number is of order 2 n / √ n, and therefore far greater than the number of strings x of length n and Kolmogorov complexity C(x) = k = 1 2 n which is at most 2 n/2 . This explains the fact that in Theorem 1, Item (ii), we cannot precisely match a string x of length n to every function g ∈ G n , and therefore have to use approximate shapes. ♦ EXAMPLE 5: By Theorem 1, Item (ii), for every g ∈ G n there is a string x of length n that has g for its canonical rate-distortion function g x up to an additive O( √ n log n) term. By (3), (4), and Remark 5, for 0 ≤ δ ≤ 1 2 . Figure 1 gives the graph of a particular function r(δ) = g(nH(δ)) with g defined as follows: , and g(l) = n − l for nH( 1 3 ) < l ≤ n. In this way, g ∈ G n . Thus, there is a string x of length n with its rate-distortion graph r x (δ) in a strip of size O( √ n log n) around the graph of r(δ). Note that r x is almost constant on the segment Allowing the distortion to increase on this interval, all the way from 1 6 to 1 3 , so allowing n/6 incorrect extra bits, we still cannot significantly decrease the rate. This means that the distortion-rate function d x (r) of x drops , exhibiting a very unsmooth behavior. ♦

V. CHARACTERIZATION
Theorem 2 below states that a destination word that codes a given source word and minimizes the algorithmic mutual information with the given source word gives no advantage in rate over a minimal Kolmogorov complexity destination word that codes the source word. This theorem can be compared with Shannon's theorem, Theorem 5 in Appendix A, about the expected rate-distortion curve of a random variable. x there exists a string y at Hamming distance δ from x that has small information about x, then there exists another string z that is also within distance δ of x and has small Kolmogorov complexity itself (not only small algorithmic information about x). ♦

VI. FITNESS OF DESTINATION WORD
In Theorem 3 we show that if a destination word of a certain maximal Kolmogorov complexity has minimal distortion with respect to the source word, then it also is the (almost) best-fitting destination word in the sense (explained below) that among all destination words of that Kolmogorov complexity it has the most properties in common with the source word. 'Fitness' of individual strings to an individual destination word is hard, if not impossible, to describe in the probabilistic framework. However, for the combinatoric and computational notion of Kolmogorov complexity it is natural to describe this notion using 'randomness deficiency' as in Definition 8 below.
Reference [22] uses 'fitness' with respect to the particular distortion family L. We briefly overview the generalization to arbitrary distortion families satisfying properties 2 and 3 (details, formal statements and proofs about L can be found in the cited reference). The goodness of fit of a destination word y for a source word x with respect to an arbitrary distortion family A is defined by the randomness deficiency of x in the the distortion ball B(y, δ) with δ = d(x, y). The lower the randomness deficiency, the better is the fit.
depending on the context of the future statements.
The randomness deficiency can be little smaller than 0, but not more than a constant.
DEFINITION 9: Let β be an integer parameter and P ⊆ A. We say P is a property in A if P is a 'majority' If the randomness deficiency δ(x | A) is not much greater than 0, then there are no simple special properties that single x out from the majority of strings to be drawn from A. This is not just terminology: If δ(x|A) is small enough, then x satisfies all properties of low Kolmogorov complexity in A (Lemma 4 in Appendix D). If A is a set containing x such that δ(x | A) is small then we say that x is a set of good fit for x. In [22] the notion of models for x is considered: Every finite set of strings containing x is a model for x. Let x be a string of length n and choose an integer i between 0 and n. Consider models for x of Kolmogorov complexity at most i. Theorem IV.8 DRAFT and Remark IV.10 in [22] show for the distortion family L that x has minimal randomness deficiency in every set That is, up to the stated precision every such witness set is the best-fitting model that is possible at model Kolmogorov complexity at most i. It is remarkable, and in fact unexpected to the authors, that the analogous result holds for arbitrary distortion families provided they satisfy properties 2 and 3.
THEOREM 3: Let A be a distortion family satisfying properties 2 and 3 and x a string of length n. Let B be a Let A x be a set of minimal Kolmogorov complexity among the sets A ∈ A with x ∈ A and ⌈log |A|⌉ = ⌈log |B|⌉. Then, LEMMA 3: For every set A with x ∈ A, up to a O(log n) additive term.
Proof: The inequality (6) means that that shows that every sufficient statistic for x is a model of a good fit for x.
EXAMPLE 7: Consider the elements of every A ∈ A uniformly distributed. Assume that we are given a string x that was obtained by a random sampling from an unknown set B ∈ A satisfying C(B) ≤ n = |x|. Given x we want to recover B, or some A ∈ A that is "a good hypothesis to be the source of x" in the sense that the randomness deficiency δ(x | A) is small. Consider the set A x from Theorem 3 as such a hypothesis. We claim that with high More specifically, for every β the probability of the event δ( then with high probability (Appendix D) the randomness deficiency δ(x | B) is small. That is, with probability Therefore the probability of the event δ(x | A x ) > β is less than 2 −β+O(log n) . ♦ EXAMPLE 8: Theorem 3 says that for fixed log-cardinality l the model that has minimal Kolmogorov complexity has also minimal randomness deficiency among models of that log-cardinality. Since g x satisfies Lemma 1, we have also that for every k the model of Kolmogorov complexity at most k that minimizes the log-cardinality also minimizes randomness deficiency among models of that Kolmogorov complexity. These models can be computed in the limit, in the first case by running all programs up to k bits and always keeping the one that outputs the smallest set in A containing x, and in the second case by running all programs up to n = |x| bits and always keeping the shortest one that outputs a set in A containing x having log-cardinality at most l. ♦

VII. DENOISING
In Theorem 3 using (6) we obtain This gives a method to identify good-fitting models for x using compression, as follows. Let k = C(A x ) and l = ⌈log |B|⌉. If A x is a set of minimal Kolmogorov complexity among sets A ∈ A with x ∈ A and ⌈log |A|⌉ = l, then by (7) the hypothesis "x is chosen at random in A x " is (almost) at least as plausible as the hypothesis "x is chosen at random in B" for every simply described B ∈ A (say, log C(B) = O(log n)) with ⌈log |B|⌉ = l.
Let us look at an example of denoising by compression (in the ideal sense of Kolmogorov complexity) for Hamming distortion. Fix a target string y of length n and a distortion 0 ≤ δ ≤ 1 2 . (This string y functions as the destination word.) Let a string x be a noisy version of y by changing at most nδ randomly chosen bits in y (string x functions as the source word). That is, the string x is chosen uniformly at random in the Hamming ball B = B(y, δ). Letx be a string witnessing r x (δ), that is,x is a string of minimal Kolmogorov complexity with d(x,x) ≤ δ and r x (δ) = C(x). We claim that at distortion δ the stringx is a good candidate for a denoised version of x, that is, the target string y. This means that in the two-part description (x,x ⊕ x) of x, the second part (the bitwise XOR of x andx) is noise:x ⊕ x is a random string in the Hamming ball B(00 . . . 0, δ) in the sense that Indeed, let l = ⌈log |B|⌉. By Definition 5 of g x , Theorem 3 implies that ignoring additive terms of O(log n) and observing that the additive term log C(B) is absorbed by O(log n). For every x, the rate-distortion function r x of x differs from g x just by changing the scale of the argument as in (4).
More specifically, we have r x (δ) = g x (l) and hence Since we assume that x is chosen uniformly at random in B, the randomness deficiency δ(x | B) is small, say O(log n) with high probability. Since r x (δ) = C(x) = C(B(x, δ))+O(C(δ)), C(δ) = O(log n), and l = ⌈log b(δ)⌉, it follows that with high probability, and the equalities up to an additive O(log n) term, Since by construction x ∈ B(x, δ), the displayed equation shows that the ball B(x, δ) is a sufficient statistic for x.
This implies that x is a typical element of B(x, δ), that is, Here p is an appropriate program of O(C(δ)) = O(log n) bits.
This provides a method of denoising via compression, at least in theory. In order to use the method practically, admittedly with a leap of faith, we ignore the ubiquitous O(log n) additive terms, and use real compressors to approximate the Kolmogorov complexity, similar to what was done in [10], [11]. The Kolmogorov complexity is not computable and can be approximated by a computable process from above but not from below, while a real compressor is computable. Therefore, the approximation of the Kolmogorov complexity by a real compressor involves for some arguments errors that can be high and are in principle unknowable. Despite all these caveats it turns out that the practical analogue of the theoretical method works surprisingly well in all experiments we tried [15].
As an example, we approximated the distortion-rate function of a noiseless cross of very low Kolmogorov complexity, to which artificial noise was added to obtain a noisy cross, [15]. Figure 2 shows two graphs. In the experiments in [15] a specially written block sorting compression algorithm with a move-to-front scheme DRAFT as described in [3] was used. The algorithm is very similar to a number of common general purpose compressors, such as bzip2 and zzip, but it is simpler and faster for small inputs; the source code (in C) is available from the authors of [15].

VIII. ALGORITHMIC VERSUS PROBABILISTIC RATE-DISTORTION
Theorem 4 shows that Shannon's rate-distortion function r n (δ) of (8) for a random variable is pointwise related to the expected value of the rate-distortion functions r x (δ) of the individual string x ∈ A n (outcomes of the random variable with the expectation taken over the probabilities of the random variable). This result generalizes [25], [13], [20] to arbitrary computable sources.
Formally, probabilistic rate-distortion theory is treated in Appendix A. Let X and Y be finite alphabets where we take X = {0, 1} for convenience. We generalize the setting from i.i.d. random variables to more general random variables. Let X 1 , X 2 , . . . , X n be a sequence of, possibly dependent, random variables with values in X n such that p(x 1 x 2 . . . x n ) = P (X 1 = x 1 , X 2 = x 2 , . . . , X n = x n ) is rational. With X = X 1 , X 2 , . . . , X n and . . x n , let C(X) denote the Kolmogorov complexity of the set of pairs (x, p(x)) ordered lexicographic.
Let E : X n → Y n be a code. Define the Shannon rate-distortion function by the expectation E taken over the probability mass function p. Note that we have taken X = {0, 1} n = X n and Y = Y n . The ∆ 1 quantity satisfies lim n→∞ ∆ 1 /n = 0. The quantity ∆ 2 is small only in the case where we have asymptotic equidistribution. This is the original setting of Shannon. Though independence is not needed, for example ergodic stationarity guarantees asymptotic equidistribution.

A. Shannon Rate Distortion
Classical rate-distortion theory was initiated by Shannon in [17], [18], and we briefly recall his approach. Let X and Y be finite alphabets. A single-letter distortion measure is a function d that maps elements of X × Y to the reals. Define the distortion between word x and y of the same length n over alphabets X and Y, respectively, by DRAFT Let X be a random variable with values in X. Consider the random variable X n with values in X n , that is, the sequence X 1 , . . . , X n of n independent copies of X. We want to encode words of length n over X by words over Y so that the number of all code words is small and the expected distortion between outcomes of X n and their codes is small. The tradeoff between the expected distortion and the number of code words used is expressed by the rate-distortion function denoted by r n (δ) as in (8). It maps every δ ∈ R to the minimal natural number r (we call r the rate) having the following property: There is an encoding function E : X n → Y n with a range of cardinality at most 2 r such that the expected distortion between the outcomes of X n and their corresponding codes is at most δ.

B. Computability
In 1936 A.M. Turing [21] defined the hypothetical 'Turing machine' whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domain. These Turing machines compute integer functions, the computable functions. By using pairs of integers for the arguments and values we can extend computable functions to functions with rational arguments and/or values. The notion of computability can be further extended, see for example [9]: A function f with rational arguments and real values is upper semicomputable if there is a computable function φ(x, k) with x an rational number and k a nonnegative integer such that φ(x, k + 1) ≤ φ(x, k) for every k and lim k→∞ φ(x, k) = f (x An example of a recursive set is the set of prime numbers; an example of a recursively enumerable set that is not recursive is {x ∈ N : C(x) < |x|}. ♦ Let X = {0, 1} * , and Y and the distortion measure d be given. Assume that Y is recursively (= computably) enumerable and the set { x, y, δ ∈ X × Y × Q : d(x, y) ≤ δ} is decidable. Then r x is upper semicomputable.
Namely, to determine r x (δ) proceed as follows. Recall that U is the reference universal Turing machine. Run U (p) for all p dovetailed fashion (in stage k of the overall computation execute the ith computation step of the (k − i)th program). Interleave this computation with a process that recursively enumerates Y. Put all enumerated elements of Y in a set W. Whenever U (p) halts we put the output in a set U. After every step in the overall computation we determine the minimum length of a program p such that U (p) ∈ W U and d(x, U (p)) ≤ δ. We call p a candidate program. The minimal length of all candidate programs can only decrease in time and eventually becomes equal to r x (δ). Thus, this process upper semicomputes r x (δ).
The function g x is also upper semicomputable. The proof is similar to that used to prove the upper semicomputability of r x . It follows from [22] that in general d x , and hence its 'inverse' r x and by Lemma 2 the function g x , are not computable.
Assume that the set Y is recursively enumerable and the set { x, y, δ ∈ X × Y × Q : d(x, y) ≤ δ} is decidable.
Assume that the resulting distortion family A d,Y satisfies Property 2. There is a relation between destination words and distortion balls. This relation is as follows.
(i) Communicating a destination word y for a source word x knowing a rational upper bound δ for the distortion d(x, y) involved is the same as communicating a distortion ball of radius δ containing x. Ad (ii). Let B be a given ball. Recursively enumerating Y and the possible β ∈ Q, we find for every newly enumerated element of y ∈ Y whether B(y, β) = B (see the proof of Lemma 2 for an algortihm to find a list of elements of B(y, β) given y, β). Put these β's in a set W. Consider the least element of W at every computation step. This process upper semicomputes the least distortion δ corresponding to the distortion ball B.

C. Kolmogorov Complexity
For precise definitions, notation, and results see the text [9]. Informally, the Kolmogorov complexity, or algorithmic entropy, C(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, C(x) represents the minimal amount of information required to generate x by any effective process. The conditional Kolmogorov complexity C(x | y) of x relative to y is defined similarly as the length of a shortest binary program to compute x, if y is furnished as an auxiliary input to the computation.
Let T 1 , T 2 , . . . be a standard enumeration of all (and only) Turing machines with a binary input tape, for example the lexicographic length-increasing ordered syntactic Turing machine descriptions, [9], and let φ 1 , φ 2 , . . . One of the main achievements of the theory of computation is that the enumeration T 1 , T 2 , . . . contains a machine, say T u , that is computationally universal in that it can simulate the computation of every machine in the enumeration when provided with its index. It does so by computing a function φ u such that φ u ( i, p , y) = φ i (p, y) for all i, p, y.
We fix one such machine and designate it as the reference universal Turing machine or reference Turing machine for short.
DEFINITION 10: The conditional Kolmogorov complexity of x given y (as auxiliary information) with respect to The conditional Kolmogorov complexity C(x | y) is defined as the conditional Kolmogorov complexity C u (x | y) with respect to the reference Turing machine T u usually denoted by U . The unconditional version is set to C(x) = C(x | ǫ).
Kolmogorov complexity C(x | y) has the following crucial property: C(x | y) ≤ C i (x | y)+c i for all i, x, y, where c i depends only on i (asymptotically, the reference Turing machine is not worse than any other machine). Intuitively, C(x | y) represents the minimal amount of information required to generate x by any effective process from input y. The functions C(·) and C(· | ·), 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, see for example [9], and from the ability of universal machines to simulate one another and execute any effective process. The Kolmogorov complexity of an individual finite object was introduced by Kolmogorov [7] as an absolute and objective quantification of the amount of information in it. The information theory of Shannon [17], 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. For example, let X and Y be random variables with a joint distribution. It is remarkable that also the algorithmic information in one finite object about another one is symmetric: I(x : y) = I(y : x) up to an additive term logarithmic in C(x) + C(y). This follows immediately from the symmetry of information property due to A.N. Kolmogorov and L.A. Levin: = C(y) + C(x | y) + O(log(C(x) + C(y))).

D. Randomness Deficiency and Fitness
Randomness deficiency of an element x of a finite set A according to Definition 8 is related with the fitness of x ∈ A (identified with the fitness of set A as a model for x) in the sense of x having most properties represented by the set A. Properties are identified with large subsets of A whose Kolmogorov complexity is small (the 'simple' subsets).
Then the randomness deficiency δ( The randomness deficiency measures our disbelief that x can be obtained by random sampling in A (where all elements of A are equiprobable). For every A, the randomness deficiency of almost all elements of A is small: The number of x ∈ A with δ(x | A) > β is fewer than |A|2 −β . This can be seen as follows. The inequality δ(x | A) > β implies C(x | A) < log |A| − β. Since 1 + 2 + 2 2 + · · · + 2 i−1 = 2 i − 1, there are less than 2 log |A|−β programs of fewer than log |A| − β bits. Therefore, the number of x's satisfying the inequality C(x | A) < log |A| − β cannot be larger. Thus, with high probability the randomness deficiency of an element randomly chosen in A is small. On the other hand, if δ(x | A) is small, then there is no way to refute the hypothesis that x was obtained by random sampling from A: Every such refutation is based on a simply described property possessed by a majority of elements of A but not by x. Here it is important that we consider only simply described properties, since otherwise we can refute the hypothesis by exhibiting the property P = A \ {x}.

E. Covering Coefficient for Hamming Distortion
The authors find it difficult to believe that the covering result in the lemma below is new. But neither a literature search nor the consulting of experts has turned up an appropriate reference. Proof: Fix a ball with center y and radius δ = j/n ≤ 1 2 where j is a natural number. All the strings in the ball that are at Hamming distance at most d from y can be covered by one ball of radius d with center y. Thus it suffices, for every ∆ of the form i/n with i = 2, 3, . . . , j (such that d < ∆ ≤ δ), to cover the set of all the strings at distance precisely ∆ from y by n c+1 b(δ)/b(d) balls of radius d for some fixed constant c. Then the ball B(y, δ) is covered by at most jn c+1 b(δ)/b(d) ≤ n c+2 b(δ)/b(d) balls of radius d.
By Stirling's formula, this is at least where the last inequality follows from (3). Therefore a ball B as above covers at least b(d)/n c strings of S. The probability that a ball B, chosen uniformly at random as above, covers a particular string x ∈ S is the same for every such x since they are in symmetric position. The number of elements in a Hamming sphere is smaller than the cardinality of a Hamming ball of the same radius, |S| ≤ b(δ). Hence with probability a random ball B covers a particular string x in S.
By Claim 1, the probability that a random ball B does not cover a particular string x ∈ S is at most 1 − b(d)/(n c b(δ)). The probability that no ball out of N randomly drawn such balls B covers a particular x ∈ S (all balls are equiprobable) is at most , the exponent of the right-hand side of the last inequality is −n, and the probability that x is not covered is at most e −n . This probability remains exponentially small even after multiplying by |S| ≤ 2 n , the number of different x's in S. Hence, with probability at least 1 − (2/e) n we have that N random balls of the given type cover all the strings in S. Therefore, there exists a deterministic selection of N such balls that covers all the strings in S. The lemma is proved. (A more accurate calculation shows that the lemma holds with α n = O(n 4 ).) function g x of every string x of length n is close to some function in the family G n . This can be seen as follows.
Second, we prove that for every l = 0, 1, . . . , n. Fix an l and consider the least m with l ≤ m ≤ n such that g x (m) = g(m). If there is no such m we take m = n and observe that g x (n) = O(log n) = g(n)+O(log n). This way, g x (m) = g(m)+O(log n) and for every l < l ′ ≤ m we have g(l ′ − 1) < g x (l ′ − 1) due to inequality (11) and definition of m. Then g x (l ′ − 1) > g(l ′ − 1) ≥ g(l ′ ), since we know that g is nonincreasing. Then, by the definition of g we have g(l ′ − 1) = g(l ′ ) + 1.  [22] we proved a similar statement for the special distortion family L with an error term of O(log n). However, for the special case L we can let x be equal to the first x satisfying the inequality g x (l) ≥ g(l) − O(log n) for every l. In the general case this does not work any more. Here we construct x together with sets ensuring the inequalities g x (l) ≤ g(l) + O( √ n log n) for every l = 0, . . . , n.
The construction is as follows. Divide the segment {0, 1, . . . , n} into N = n/ log n subsegments of length √ n log n each. Let l 0 = n > l 1 > · · · > l N = 0 denote the end points of the resulting subsegments.
To find the desired x, we run the nonhalting algorithm below that takes n and A n as input together with the values of the function g in the points l 0 , . . . , l N . Let δ(n) be a computable integer valued function of n of the order √ n log n that will be specified later.
A set is called forbidden if it is i-forbidden for some i = 0, 1, . . . , N .
We wish to find an x that is outside all forbidden sets (since this guarantees that g x (l i ) ≥ g(l i ) − δ(n) for every i). Since C(·) is upper semicomputable, moreover property 3 holds, and we are also given n and g(l 0 ), . . . , g(l N ), we are able to find all forbidden sets using the following subroutine.
Subroutine (n, A n , g(l 0 ), g(l 1 ), . . . , g(l n )): for every F ∈ A n upper semicompute C(F ); every time we find C(F ) < g(l i ) − δ(n) and |F | ≤ 2 li for some i and F , then print F .

End of Subroutine
This subroutine prints all the forbidden sets in some order. Let F 1 , . . . , F T be that order. Unfortunately we do not know when the subroutine will print the last forbidden set. In other words, we do not know the number T of forbidden sets. To overcome this problem, the algorithm will run the subroutine and every time a new forbidden set F t is printed, the algorithm will construct candidate sets B 0 (t), . . . , B N (t) ∈ A n satisfying |B i (t)| ≤ 2 li and C(B i (t)) ≤ g(l i ) + δ(n) and the following condition for every t = 0, . . . , T . For t = T the set t j=1 F j is the union of all forbidden sets, which guarantees the bounds g(l i ) − δ(n) ≤ g x (l i ) ≤ g(l i ) + δ(n) for all x in the set in the left hand side of (12). Then we will prove that these bounds imply that g(l) − δ(n) ≤ g x (l) ≤ g(l) + δ(n) for every l = 0, . . . , n. Each time a new forbidden set appears (that is, for every t = 1, . . . , T ) we will need to update candidate sets so that (12) remains true. To do that we will maintain a stronger condition than just non-emptiness of the left hand side of (12). Namely, we will maintain the following invariant: for every i = 0, 1, . . . , N , Note that for i = N inequality (13) implies (12).
Algorithm (n, A n , g(l 0 ), g(l 1 ), . . . , g(l n )): Initialize. Recall that l 0 = n. Define the set B t (0) = {0, 1} n for every t. This set is in A n by property 1. Trivially, this cover also covers B 0 (0) · · · B i−1 (0). The intersection of at least one of the covering sets with B 0 (0) · · · B i−1 (0) has cardinality at least Let B i (0) by the first such covering set in a given standard order. od Notice that after the Initialization the invariant (13) is true for t = 0, as t j=1 F j = ∅. For every t = 1, 2, . . . perform the following steps 1 and 2 maintaining the invariant (13): Step 1. Run the subroutine and wait until tth forbidden set F t is printed (if t > T the algorithms waits forever and never proceeds to Step 2).

Case 1. For every
Note the this inequality has one more forbidden set compared to the invariant (13) for t−1 (the argument in B j (t − 1)), and thus may be false. If that is the case, then we let B i (t) = B i (t − 1) for every i = 1, . . . , N (this setting maintains invariant (13)). (14) is false for some index i. In this case find the least such index (we will use later that (14) is true for all i ′ < i).

Case 2. Assume that
We claim that i > 0. That is, the inequality (14) is true for i = 0. In other words, the the cardinality of F 1 · · · F t is not larger than half of the cardinality of B 0 (t − 1) = {0, 1} n . Indeed, for every fixed i the total cardinality of all the sets of simultaneously cardinality at most 2 li and Kolmogorov complexity less than g(l i ) − δ(n) does not exceed 2 g(li)−δ(n) 2 li . Therefore, the total number of elements in t j=1 F t is at most where the first inequality follows since the function g(l) + l is monotonic nondecreasing, the first equality since g(n) = 0 by definition, and the last inequality since we will set δ(n) at order of magnitude √ n log n.
First let B k (t) = B k (t − 1) for all k < i (this maintains invariant (13) for all k < i). To define B i (t) find a covering of B i−1 (t) by at most α n 2 li−1−li sets in A n of cardinality at most 2 li . Since (14) is true for Thus the greatest cardinality of an intersection of the set in (15) with a covering set is at least Let B i (t) be the first such covering set in standard order. Note that 2 li−i α −i n is at least twice the threshold required by invariant (13). Use the same procedure to obtain successively B i+1 (t), . . . , B N (t).

End of Algorithm
Although the algorithm does not halt, at some unknown time the last forbidden set F T is enumerated. After this time the candidate sets are not changed anymore. The invariant (13) with i = N shows that the cardinality of the set in the left hand side of (12) is positive hence the set is not empty.
Next we show that C(B i (t)) ≤ g(l i ) + δ(n) for every i and every t = 1, . . . , T . We will see that to this end it suffices to upperbound the number of changes of each candidate set.
Proof: The Claim is proved by induction on i. For i = 0 the claim is true, since l 0 = n and g(n) = 0 while m 0 = 0 by initialization in the Algorithm (B(0) never changes).
(i > 0): assume that the Claim is satisfied for every j with 0 ≤ j < i. We will prove that m i ≤ 2 g(li)+i by counting separately the number of changes of B i of different types.
Change of type 1. The set B i is changed when (14) is false for an index strictly less than i. The number of these changes is at most where the first inequality follows from the inductive assumption, and the second inequality by the property of g that it is nonincreasing. Namely, since l i−1 > l i we have g(l i−1 ) ≤ g(l i ).
Change of type 2. The inequality (13) is false for i and is true for all smaller indexes.
Change of type 2a. After the last change of B i at least one j-forbidden set for some j < i has been enumerated.
The number of changes of this type is at most the number of j-forbidden sets for j = 0, . . . , i − 1. For every such j these forbidden sets have by definition Kolmogorov complexity less than g(l j ) − δ(n). Since l j ≥ l i and g is monotonic nonincreasing we have g(l j ) ≤ g(l i ). Because there are at most N of these j's, the number of such forbidden sets is at most since we will later choose δ(n) of order √ n log n, Change of type 2b. Finally, for every change of this type, between the last change of B i and the current one no candidate sets with indexes less than i have been changed and no j-forbidden sets with j < i have been enumerated. DRAFT Since after the last change of B i the cardinality of the set in the left-hand side of (13) was at least 2 li−i α −i n , which is twice the threshold in the right-hand side by the restoration of the invariant in the Algorithm Step 2, Case 2, the following must hold. The cardinality of t j=1 F j increased by at least 2 li−i−1 α −i n since the last change of B i , and this must be due to enumerating j-forbidden sets for j = i, . . . , N . For every such j every j-forbidden set has cardinality at most 2 lj and Kolmogorov complexity less than g(l j )− δ(n). Hence the total number of elements in all j-forbidden sets is less than 2 lj 2 g(lj )−δ(n) . Since j ≥ i and hence l j ≤ l i while g(l) + l is monotonic nondecreasing we have g(l j ) + l j ≤ g(l i ) + l i . Because there are at most N + 1 of these j's, the total number of elements in all those sets does not exceed M = (N + 1)2 g(li)−δ(n)+li . The number of changes of this type is not more than the total number M of elements involved divided by the increments of size 2 li−i−1 α −i n . Hence it is not more than Let δ(n) ≥ log((N + 1)2 i+10 α i n ) and (16) where the last equality uses that α n is polynomial in n by property 4. Then, the number of changes of type 2b is much less than 2 g(li) . The value of δ(n) can be computed from n.
Summing the numbers of changes of types 1, 2a, and 2b we obtain m i ≤ 2 g(li)+i , completing the induction. Proof: By construction x is not an element of any forbidden set in T t=1 F t , and therefore for every i = 0, 1, . . . , N . By construction |B i (T )| ≤ 2 li , and to finish the proof it remains to show that C(B i (T )) ≤ g(l i ) + δ(n) so that g x (l i ) ≤ g(l i ) + δ(n), for i = 0, 1, . . . , N . Fix i. The set B i (T ) can be described by a constant length program, that is O(1) bits, that runs the Algorithm and uses the following information: • A description of i in log N ≤ log n bits.
• A description of the distortion family A n in O(log n) bits by property 3.
• The values of g in the points l 0 , . . . , l N in N log n = √ n log n bits.
• The description of n in O(log n) bits. Let us show that the statement of Claim 3 holds not only for the subsequence of values l 0 , l 1 , . . . , l N but for every l = 0, 1, . . . , n, Let l i ≤ l ≤ l i−1 . Both functions g(l), g x (l) are nonincreasing so that By the spacing of the sequence of l i 's the length of the segment [g(l i−1 ), g(l i )] is at most If there is an x such that Claim 3 holds for every l i with i = 0, . . . , N , then it follows from the above that |g(l) − g x (l)| ≤ √ n log n + O( √ n log n) for every l = 0, 1, . . . , n.
Proof: of Theorem 2. We start with Lemma 6 stating a combinatorial fact that is interesting in its own right, as explained further in Remark 8. must be less than 2 k . (It is easy to see that without loss of generality we may assume that Alice makes exactly 2 k − 1 moves.) Bob can easily win if he marks every set produced by Alice. However, we want to minimize the total number of marked sets. CLAIM 4: Bob has a winning strategy that marks at most O(2 k−m k 2 n) sets.
Proof: We present an explicit strategy for Bob, which consists in in executing at every move t = 1, 2, . . . , 2 k −1 the following algorithm for the sequence A 1 , A 2 , . . . , A t which has been produced by Alice until then.
Step 1. Let 2 j be the largest power of 2 dividing t. Consider the last 2 j sets in the sequence A 1 , A 2 , . . . , A t and call them D 1 , . . . , D 2 j .
Step 2. Let T be the set of x's that occur in at least 2 m /k of the sets D 1 , . . . , D 2 j . Let D p be a set such that |D p T | is maximal. Mark D p (if there is more than one then choose the one with p least) and remove all elements of D p T from T . Call the resulting set T 1 . Let D q be a set such that |D q T 1 | is maximal (if there is more than one then choose the one with q least). After removing all elements of D q T 1 from T 1 we obtain a set T 2 . Repeat the argument until we obtain T ej = ∅.
Firstly, for the j above we have e j ≤ ⌈2 j−m kn ln 2⌉. This is proved as follows. We have since every x ∈ T is counted at least 2 m /k times in the sum in the left hand side. Thus there is a set in the list D 1 , . . . , D 2 j such that the cardinality of its intersection with T is at least 2 −j times the right hand side. By the choice of D p it is such a set and we have |D p T | ≥ |T |2 m−j /k.
The set T has lost at least a (2 m−j /k)th fraction of its elements, that is, obviously every element of T 1 (still) occurs in at least 2 m /k of the sets D 1 , . . . , D 2 j . Thus we can repeat the argument and mark a set D q with |D q T 1 | ≥ |T 1 |2 m−j /k. After removing all elements of D q T 1 from T 1 we obtain a set T 2 that is at most a (1 − 2 m−j /k)th fraction of T 1 , that is, Recall that we repeat the procedure e j times where e j is the number of repetitions until T ej = ∅. It follows that Secondly, for every fixed j = 0, 1, . . . , k − 1 there are at most 2 k−j different t's (t = 1, 2, . . . , 2 k − 1) divisible by 2 j and the number d j = 2 k−j e j of marked sets we need to use for this j satisfies d j ≤ 2 k−j 2 j−m kn ln 2 = 2 k−m kn ln 2. For all j = 0, . . . , k − 1 together we use a total number of marked sets of at most In this way, after every move t = 1, 2, . . . , 2 k −1 of Bob, every x occurring in 2 m of Alice's sets belongs to a marked set of Bob. This can be seen as follows. Assume to the contrary, that there is an x that occurs in 2 m of Alice's sets following move t of Bob, and x belongs to no set marked by Bob in step t or earlier. Let t = 2 j1 + 2 j2 + · · · with j 1 > j 2 > · · · be the binary expansion of t. By Bob's strategy, the element x occurs less than 2 m /k times in the first segment of 2 j1 sets of Alice, less than 2 m /k times in the next segment of 2 j2 of Alice's sets, and so on. Thus its total number of occurrences among the t first sets of Alice is strictly less than k2 m /k = 2 m . The contradiction proves the claim.
Let us finish the proof of the Lemma 6. Given the list of B, recursively enumerate the sets in B of Kolmogorov complexity less than k, say B 1 , B 2 , . . . , B T with T < 2 k , and consider this list as a particular sequence of moves by Alice. Use Bob's strategy of Claim 4 against Alice's sequence as above. Note that recursive enumeration of the sets in B of Kolmogorov complexity less than k means that eventually all such sets will be produced, although we do not know when the last one is produced. This only means that the time between moves is unknown, but the alternating moves between Alice and Bob are deterministic and sequential. According to Claim 4, Bob's strategy marks at most O(2 k−m k 2 n) sets. These marked sets cover every string occurring at least 2 m times in the sets rule: Bob looses if he marks more than 2 k−m+1 (n + 1) ln 2 sets. We will prove that in this game Bob has a winning strategy.
Assume the contrary: Bob has no winning strategy. Since the number of moves in the game is finite (less than 2 k ), this implies that Alice has a winning strategy.
Fix a winning strategy S of Alice. To obtain a contradiction we design a randomized strategy for Bob that beats Alice's strategy S with positive probability. Bob's strategy is very simple: mark every set produced by Alice with probability p = 2 −m (n + 1) ln 2.
CLAIM 5: (i) With probability more than 1 2 , following every move of Bob every element occurring in at least 2 m of Alice's sets is covered by a marked set of Bob.
(ii) With probability more than 1 2 , Bob marks at most 2 k−m+1 (n + 1) ln 2 sets. Proof: (i) Fix x and estimate the probability that there is move of Bob following which x belongs to 2 m of Alice's sets but belongs to no marked set of Bob.
Let R i be the event "following a move of Bob, string x occurs at least in i sets of Alice but none of them is marked". Let us prove by induction that DRAFT For i = 0 the statement is trivial. To prove the induction step we need to show that Pr[R i+1 |R i ] ≤ 1 − p.
Let z = z 1 , z 2 , . . . , z t be a sequence of decisions by Bob: z j = 1 if Bob marks the jth set produced by Alice and z j = 0 otherwise. Call z bad if following Bob's tth move it happens for the first time that x belongs to i sets produced by Alice by move t but none of them is marked. Then R i is the disjoint union of the events "Bob has made the decisions z" (denoted by Q z ) over all bad z. Thus it is enough to prove that Given that Bob has made the decisions z, the event R i+1 means that after those decisions the strategy S will at some time in the future produce the (i + 1)st set with member x but Bob will not mark it. Bob's decision not to mark that set does not depend on any previous decision and is made with probability 1 − p. Hence (ii) The expected number of marked sets is p2 k . Thus the probability that it exceeds p2 k+1 is less than 1 2 . It follows from Claim 5 that there exists a strategy by Bob that marks at most 2 k−m+1 (n + 1) ln 2 sets out of Alice's produced 2 k sets, and following every move of Bob every element occurring in at least 2 m of Alice's sets is covered by a marked set of Bob. Note that we have proved that this strategy of Bob exists but we have not constructed it. Given n, k and m, the number of games is finite, and a winning strategy for Bob can be found by brute force search. This is the number of extra bits incurred by the two-part code for x using B compared to the most optimal one-part code of x using C(x) bits. We relate this quantity with the randomness deficiency δ(x | B) = log |B| − C(x | B) of x in the set B. The randomness deficiency is always less than the sufficiency deficiency, and the difference between them is equal to C(B | x): where the equality follows from the symmetry of information (10), ignoring here and later in the proof additive terms of order O(log C(B) + log n).
By Theorem 2, which assumes that properties 2 and 3 hold for the distortion family A, there is A ∈ A(x) with ⌈log |A|⌉ = ⌈log |B|⌉ and C(A) ≤ C(B) − C(B | x). Since A x is a set of minimal Kolmogorov complexity among such A we have C(A x ) ≤ C(B) − C(B | x). Therefore where the last equality is true by (17).
Left inequality. Given δ, n, p, and the (discrete) graph of r n , we can compute an optimal E as in (8) such that r n (δ) = log |E(X n )|. Retrieve E(x) by its index of r n (δ) bits in the set E(X n ). Then, C(E(x)) ≤ r n (δ) + O(C(δ, r n , X, n)).
By definition, r x (δ) ≤ C(E(x)). Taking the expectation of r x (δ) over p, we are done.
Right inequality. Define a code E 0 such that C(E 0 (x)) = r x (δ) for every x ∈ X n . Let E 0 (X n ) be the range of E 0 . Although E 0 (X n ) cannot be computed, it is finite, and trivially log |E 0 (X n )| ≤ max x∈X n C(E 0 (x)).

S(y)C(y) ≥ H(S),
with S the distribution defined in the statement of the theorem. By definition, r n (δ) ≤ log |Y n |, which yields r n (δ) ≤ H(L), with L as in the statement of the theorem. Together, we obtain r n (δ) ≤ Er x (δ) + ∆ 2 .