Laurent Bienvenu

Peter Gacs

Mathieu Hoyrup

Cristobal Rojas

Alexander Shen

Peter Gács

Algorithmic tests and randomness with

come   L'archive ouverte pluridisciplinaire

measure B p . A notion of "uniform test" for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures.

Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.

Introduction

This paper, though intended to be rather self-contained, can be seen as a continuation of [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF] (which itself built on earlier work of Levin) and [START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF].

Our enterprise is to develop the theory of randomness beyond the framework where the underlying probability distribution is the uniform distribution or a computable distribution. A randomness test t(ω, P) of object ω with respect to measure P is defined to be a function of both the measure P and the point ω.

In some later parts of the paper, we will also go beyond the case where the underlying space is the set of finite or infinite sequences: rather, we take a constructive metric space with its algebra of Borel sets.

We will apply the above notion of test to define, following ideas of [15], for a class C of measures having some compactness property, a "class test" t C (ω). This is a test to decide whether object ω is random with respect to any one measure P in the class C . We will show that in case of the class of Bernoulli measures over binary sequences, this notion is equivalent to the class tests introduced by Martin-Löf in [START_REF] Martin-Löf | The definition of random sequences[END_REF].

In case there is an effective sense in which the elements of the class are mutually orthogonal, we obtain an especially simple separation of the randomness test t(ω, P) into two parts: the class test and an arbitrarily simple test for "typicality" with respect to the measure P. In some natural special cases, the typicality test corresponds to a convergence property of relative frequencies, allowing to apply the theory to any general effectively compact class of ergodic stationary processes.

There are some properties of randomness tests t(ω, P) that depend on the measure P, which our tests do not necessarily possess, for example a kind of monotonicity in P. It is therefore notable that in case of the orthogonal classes, randomness is equivalent to an "blind" notion of randomness, that only considers randomness tests that do not depend on the measure P.

Here is an outline of the paper. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of tests. A randomness test provides a quantitative measure of non-randomness, called "randomness deficiency"; it is finite for random sequences and infinite for non-random ones. There are two versions of these tests ("average-bounded" and "probability-bounded" ones); a relation between them is established.

A formula that expresses the (average-bounded) randomness deficiency in terms of prefix complexity is given (in two forms). It implies the Levin-Schnorr criterion of randomness (with prefix complexity, as in the special case first announced in Chaitin's paper). Some approaches that go in another direction (from deficiency to complexity) are considered.

The notion of Bernoulli sequence (looking like the outcome of independent coin tosses for an asymmetric coin) is defined. It is shown that the set of Bernoulli sequences is the union (over all p ∈ [0, 1]) of the sets of sequences that are random with respect to B p , the Bernoulli measure with probability p; here we assume that p is given as an oracle). A notion of "uniform test" for Bernoulli sequences is introduced. Then the statement above is proved in the following quantitative form: the Bernoulli deficiency is the infimum of B p deficiencies over all p ∈ [0, 1].

The notion of general uniform test (not restricted to the class of Bernoulli measures) is introduced. It is shown that it generalizes Martin-Löfs earlier definition of randomness (which was given only for computable measures).

Bernoulli measures B p have the important property that p can be recovered from each random sequence of B p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.

The following notation is useful, since inequalities hold frequently only within an additive or multiplicative constant. Notation 1.1. We will write f (x) * < g(x) for inequality between positive functions within a multiplicative constant, that is for the relation f (x) = O(g(x)): precisely, if there is a constant c with f (x) cg(x) for all x. The relation f * = g means f * < g and f * > g. Similarly, f + < g and f + = g means inequality within an additive constant.

Let Λ denote the empty string. Logarithms are taken, as a default, to base 2. We use |x| to denote the length of a string x. For finite string, x and finite or infinite string y let x ⊑ y denote that x is a prefix of y. If x is a finite or infinite sequence then its elements are written as x(1), x(2), . . . , and its prefix of size n will be denoted by x(1 : n).

Let R + = [0, ∞] be the set of nonnegative reals, with the special value ∞ added. The binary alphabet {0, 1} will also be denoted by B.

2 Randomness on sequences, for computable measures

Lower semicomputable functions on sequences

In the first sections, we will study randomness over infinite binary sequences.

Definition 2.1 (Binary Cantor space, Baire space). We will denote by Ω the set of infinite binary sequences, and call it also the binary Cantor space. For a finite string x let xΩ be the set of all infinite sequences that have finite prefix x. These sets will be called basic open sets, the set of all basic open set is called the basis of Ω (as a topological space). A subset of Ω is open if it is the union of a set of basis elements. The set of infinite sequences of natural numbers will be called the Baire space. Basic open sets and open sets can be defined for it analogously.

A notion somewhat weaker than computability will play crucial role. A function t : Ω → [0, ∞] is lower semicomputable if (a) For any rational r the set {ω : r < t(ω)} is open in Ω, that is is a union of intervals xΩ.

(b) Moreover, this set is effectively open uniformly in r, that is there exists an algorithm that gets r as input and generates strings x 0 , x 1 , . . . such that the union of interval x i Ω is equal to {ω : r < t(ω)}.

This definition is a constructive version of the classical notion of lower semicontinuous function as in requirement (a). The same class of lower semicomputable functions has other (equivalent) definitions; here is one of them.

Definition 2.3. A function u defined on Ω and having rational values is called basic if the value u(ω) is determined by some finite prefix of ω.

If this prefix has length N, the function can be presented as a table with 2 N rows; each row contains N bits (the values of the first N bits of ω) and a rational number (the value of the function). Such a function is a finite object.

The proof of the following proposition is a simple exercise:

Proposition 2. [START_REF] Chaitin | A theory of program size formally identical to information theory[END_REF]. The (pointwise) limits of monotonic sequences of basic functions are exactly the lower semicomputable functions on Ω.

Since the difference of two basic functions is a basic function, we can reformulate this criterion as follows: lower semicomputable functions are (pointwise) sums of computable series made of non-negative basic functions.

One more way to define a lower semicomputable function goes as follows.

Definition 2.5 (Generating). Let T be a lower semicomputable function on the set {0, 1} * of finite sequences of zeros and ones with non-negative (finite or infinite) values. This means that the set of pairs (x, r) such that r < T (x) is enumerable. Then function t defined as

t(ω) = sup x⊑ω T (x)
is a lower semicomputable function on Ω: we will say that function T (•) generates function t(•) if it is also monotone: T (x) T (y) if x ⊑ y.

The monotonicity requirement can always be satisfied by taking T ′ (x) = max z⊑x T (z).

Proposition 2.6. Any lower semicomputable function t on Ω is generated by an appropriate function T on {0, 1} * this way.

We may also assume that T is a computable function with rational values. Indeed, since only the supremum of T on all the prefixes is important, instead of increasing T (x) for some x we may increase T (y) for all y ⊒ x of large length; this delay allows T to be computable.

For a given lower semicomputable function t on Ω there exists a maximal monotonic function T on finite strings that generates t (in the sense just described). This maximal T can be defined as follows:

T (x) = inf ω⊒x t(ω).
(

) 1
Let us now exploit the finiteness of the binary alphabet {0, 1}, which implies that the space Ω is a compact topological space.

Proposition 2. [START_REF] Gács | Complexity and Randomness[END_REF]. The function T defined by (1) is lower semicomputable. In the definition, we can replace inf by min.

Proof. Indeed, r < inf ω⊒x t(ω) if and only if there exists some rational r ′ > r with r ′ < t(ω) for all ω ⊒ x. The last condition can be reformulated: the open set of all sequences ω such that t(ω) > r ′ is a superset of xΩ. This open set is a union of an enumerable family of intervals; if these intervals cover xΩ, compactness implies that this is revealed at some finite stage, so the condition is enumerable (and the existential quantifier over r ′ keeps it enumerable). Since the function t(ω) is lower semicontinuous, it actually reaches its infimum on the compact set xΩ, so inf can be replaced with min.

Randomness tests

We assume that the reader is familiar with the basic concepts of measure theory and integration, at least in the space Ω of infinite binary sequences. A measure P on Ω is determined by the values P(x) = P(xΩ) which we will denote by the same letter P, without danger of confusion. Moreover, any function P : {0, 1} * → [0, 1] with the properties

P(Λ) = 1, P(x) = P(x0) + P(x1) (2)
uniquely defines a measure (this is a particular case of Caratheodory's theorem).

Definition 2.8 (Computable measure). A real number is called computable if there is an algorithm that for all rational ε returns a rational approximation of x with error not greater than ε. Computable numbers can also be determined as limits of sequences A function determined on words (or other constructive objects) is computable if its values are computable uniformly from the input, that is there is an algorithm that from each input and ε > 0 returns an ε-approximation of the function value on this input.

Measure P over Ω is said to be computable if the function P : {0, 1} * → [0, 1] is computable. Definition 2.9 (Randomness test, computable measure). Let P be a computable probability distribution (measure) on Ω. A lower semicomputable function t on Ω with non-negative (possible infinite) values is an (average-bounded) randomness test with respect to P (or P-test) if the expected value of t with respect to P is at most 1, that is t(ω) dP 1.

A sequence ω passes a test t if t(ω) < ∞. A sequence is called random with respect to P it is passes all P-randomness tests (as defined above).

The intuition: when t(ω) is large, this means that test t finds a lot of "regularities" in ω. Constructing a test, we are allowed to declare whatever we want as a "regularity"; however, we should not find too many of them on average: if we declare too many sequences to be "regular", the average becomes too big.

This definition turns out to be equivalent to randomness as defined by Martin-Löf (see below). But let us start with the universality theorem:

Theorem 2.10. For any computable measure P there exists a universal (maximal) P-test u: this means that for any other P-test t there exists a constant c such that t(ω) c • u(ω)

for every ω ∈ Ω.

In particular, u(ω) is finite if and only if t(ω) is finite for every P-test t, so the sequences that pass test u are exactly the random sequences.

Proof. Let us enumerate the algorithms that generate all lower semicomputable functions. Such an algorithm produces a monotone sequence of basic functions. Before letting through the next basic function of this sequence, let us check that its P-expectation is less than 2. If the algorithm considered indeed defines a Ptest, this expectation does not exceed 1, so by computing the values of P with sufficient precision we are able to guarantee that the expectation is less than 2. If this checking procedure does not terminate (or gives a negative result), we just do not let the basic function through.

In this way we enumerate all tests as well as some lower semicomputable functions that are not exactly tests but are at most twice bigger than tests. It remains to sum up all these functions with positive coefficients whose sum does not exceed 1/2 (say, 1/2 i+2 ).

Recall the definition of randomness according to Martin-Löf.

Definition 2.11. Let P be a computable distribution over Ω. A sequence of open sets U 1 , U 2 , . . . is called a Martin-Löf test for P if the sets U i are effectively open in a uniform way (that is U i = j x i j Ω where the double sequence x i j of strings is computable), moreover P(U k ) 2 -k for all k.

A set N is called a constructive (effective) null set for the measure P if there is a Martin-Löf test U 1 , U 2 , . . . with the property N = k U k . Note that effective null sets are constructive G δ sets.

A sequence ω ∈ Ω is said to pass the test U 1 , U 2 , . . . if it is not in N. It is Martin-Löf-random with respect to measure P if it is not contained in any constructive null set for P.

The following theorem is not new, see for example [START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF].

Theorem 2.12. A sequence ω passes all average-bounded P-tests (=passes the universal P-test) if and only if it is Martin-Löf random with respect to P.

Proof. If t is a test, then the set of all ω such that t(ω) > N is an effectively open set that can be found effectively given N. This set has P-measure at most 1/N (by Chebyshev's inequality), so the sets of sequences ω that do not pass t (that is t(ω) is infinite) is an effectively P-null set.

On the other hand, let us show that for every effectively null set Z there exists an average-bounded test that is infinite at all its elements. Indeed, for every effectively open set U the function 1 U that is equal to 1 inside U and to 0 outside U is lower semicomputable. Then we can get a test ∑ i 1 U i . The average of this test does not exceed ∑ i 2 -i = 1, while the sum is infinite for all elements of i U i .

When talking about randomness for a computable measure, we will write randomness from now on, understanding Martin-Löf randomness, since no other kind will be considered.

RANDOMNESS ON SEQUENCES, FOR COMPUTABLE MEASURES 9

Sometimes it is useful to switch to the logarithmic scale. Definition 2.13. For every computable measure P, we will fix a universal P-test and denote it by t P (ω). Let d P (ω) be the logarithm of the universal test t P (ω):

t P (ω) = 2 d P (ω) .
With other kinds of test also, it will be our convention to use t (boldface) for the universal test, and d (boldface) for its logarithm.

In a sense, the function d P measures the randomness deficiency in bits. The logarithm, along with the requirement t P (ω) dP 1, implies that d P (ω) may have some negative values, and even values -∞. By just choosing a different universal test we can always make d P (ω) bounded below by, say, -1, and also integer-valued. On the other hand, if we want to make it nonnegative, we will have to lose the property 2 d P (ω) dP 1, though we may still have 2 d P (ω) dP 2. It will still have the following property:

Proposition 2.14. The function d P (•) is lower semicomputable and is the largest (up to an additive constant) among all lower semicomputable functions such that the P-expectation of 2 d P (•) is finite.

As we have shown, for any fixed computable measure P the value d P (ω) (and t P (ω)) is finite if and only if the sequence ω is Martin-Löf random with respect to P. Remarks 2.15. 1. Each Martin-Löf's test (U 1 , U 2 , . . . ) is more directly related to a lower semicomputable function F(ω) = sup ω∈U i i. This function has the property P[ F(ω) k ] 2 -k . Such functions will be called probabilitybounded tests, and were used in [START_REF] Zvonkin | The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms[END_REF]. We will return to such functions later.

2. We have defined d P (ω) separately for each computable measure P (up to a constant). We will later give a more general definition of randomness deficiency d(ω, P) as a function of two variables P and ω that coincides with d P (ω) for every computable P up to a constant depending on P.

Average-bounded and probability-bounded deficiencies

Let us refer for example to [START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF][START_REF] Kh | Algorithmic information theory and Kolmogorov complexity[END_REF] for the definition of and basic properties of plain and prefix (Kolmogorov) complexity. We will define prefix complexity in Definition 2.18 below, though. We will not use complexities explicitly in the present section, just refer to some of their properties by analogy.

The definition of a test given above resembles the definition of prefix complexity; we can give another one which is closer to plain complexity. For that we use a weaker requirement: we require that the P-measure of the set of all sequences ω such that t(ω) > N does not exceed 1/N. (This property is true if the integral does not exceed 1, due to Chebyshev's inequality.)

In logarithmic scale this requirement can be restated as follows: the Pmeasure of the set of all sequences whose deficiency is greater than n does not exceed 2 -n . If we restrict tests to integer values, we arrive at the classical Martin-Löf tests: see also Remark 2.15, part 1.

While constructing an universal test in this sense, it is convenient to use the logarithmic scale and consider only integer values of n. As before, we enumerate all tests and "almost-tests" d i (where the measure is bounded by twice bigger bound) and then take the weighted maximum in the following way:

d(ω) = max i [d i (ω) -i] -c.
Then d is less than d i only by i + c, and the set of all ω such that d(ω) > k is the union of sets where d i (ω) > k +i+c. Their measures are bounded by O(2 -k-i-c ) and for a suitable c the sum of measures is at most 2 -k , as required.

In this way we get two measures of non-randomness that can be called "average-bounded deficiency" d aver (the first one, related to the tests called "integral tests" in [START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF]) and "probability bound deficiency" d prob (the second one). It is easy to see that they define the same set of nonrandom sequences (=sequences that have infinite deficiency). Moreover, the finite values of these two functions are also rather close to each other: Proposition 2.16.

d aver (ω) + < d prob (ω) + < d aver (ω) + 2 log d aver (ω).
Proof. Any average-bounded test is also a probability-bounded test, therefore

d aver (ω) + < d prob (ω).
For the other direction, let d be a probability-bounded test (in the logarithmic scale). Let us show that d -2 log d is an average-bounded test. Indeed, the probability of the event "d(ω) is between i -1 and i" does not exceed 1/2 i-1 , the integral of 2 d-2 log d over this set is bounded by 2 -i+1 2 i-2 log i = 2/i 2 and therefore the integral over the entire space converges.

RANDOMNESS ON SEQUENCES, FOR COMPUTABLE MEASURES11

It remains to note that the inequality a In the general case the question of the connection between boundedness in average and boundedness in probability is addressed in the paper [START_REF] Shafer | Test martingales, Bayes factors and p-values[END_REF]. It is shown there (and this is not difficult

+ < b + 2 log b follows from b + > a - 2 log a. Indeed,
) that if u : [1, ∞] → [0, ∞] is a monotonic continuous function with ∞ 1 u(t)/t 2 dt 1, then u(t(ω)
) is an average-bounded test for every probability-bounded test t, and that this condition cannot be improved. (Our estimate is obtained by choosing u(t) = t/ log 2 t.) Remark 2.17. This statement resembles the relation between prefix and plain description complexity. However, now the difference is bounded by the logarithm of the deficiency (that is bounded independently of length for the sequences that are close to random), not of the complexity (as usual), which would be normally growing with the length. Question 1. It would be interesting to understand whether the two tests differ only by a shift of scale or in some more substantial way. For the confirmation of such a more substantial difference could serve two families of sequences ω i and ω ′ i for which

d aver (ω ′ i ) -d aver (ω i ) → ∞ for i → ∞, while d prob (ω ′ i ) -d prob (ω i ) → -∞.
The authors do not know whether such a family exists.

A formula for average-bounded deficiency

Let us recall some concepts connected with the prefix description complexity. For reference, consult for example [START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF][START_REF] Kh | Algorithmic information theory and Kolmogorov complexity[END_REF].

Definition 2.18. A set of strings is called prefix-free if no element of it is a prefix of another element. A computable partial function T : {0, 1} * → {0, 1} * is called a self-delimiting interpreter if its domain of definition is a prefix-free set. We define the complexity Kp T (x) of a string x with respect to T as the length of a shortest string p with T (p) = x. It is known that there is an optimal (self-deliminiting) interpreter: that is a (self-delimiting) interpreter U with the property that for every self-delimiting interpreter T there is a constant c such that for every string x we have Kp U (x) Kp T (x) + c. We fix an optimal selfdelimiting interpreter U and denote Kp(x) = Kp U (x).

We also denote m(x) = 2 -Kp(x) , and call it sometimes discrete a priori probability.

The "a priori" name comes from some interpretations of a property that distinguishes the function m(x) among certain "weight distributions" called semimeasures.

Definition 2.19. A function f : {0, 1} * → [0, ∞) is called a discrete semimeasure if ∑ x f (x) 1.
Lower semicomputable semimeasures arise as the output distribution of a randomized algorithm using a source of random numbers, and outputting some word (provided the algorithm halts; with some probability, it may not halt).

It is easy to check that m(x) is a lower semicomputable discrete semimeasure.

Recall the following fact.

Proposition 2.20 (Coding Theorem). Among lower semicomputable discrete semimeasures, the function m(x) is maximal within a multiplicative constant: that is for every lower semicomputable discrete semimeasure f (x) there is a constant c with c • m(x) f (x) for all x.

The universal average-bounded randomness test t P 1 (the largest lower semicomputable function with bounded expectation) can be expressed in terms of a priori probability (and therefore prefix complexity):

Proposition 2.21. Let P be a computable measure and let t P be the universal average-bounded randomness test with respect to P. Then

t P (ω) * = ∑ x⊑ω m(x) P(x)
.

(If P(x) = 0, then the ratio m(x)/P(x) is considered to be infinite.)

Proof. A lower semicomputable function on sequences is a limit of an increasing sequence of basic functions.

RANDOMNESS ON SEQUENCES, FOR COMPUTABLE MEASURES13

Withouth loss of generality we may assume that each increase is made on some cylinder xΩ. In other terms, we increase the "weight" w(x) of x and let our basic function on ω be the sum of the weights of all prefixes of ω. The weights increase gradually: at any moment, only finitely many weights differ from zero. In terms of weights, the average-boundedness condition translates into

∑ x P(x)w(x) 1,
so after multiplying the weights by P(x), this condition corresponds exactly to the semimeasure requirement. Let us note that due to the computability of P, the lower semicomputability is conserved in both directions (multiplying or dividing by P(x)). More formally, the function

∑ x⊑ω m(x) P(x)
is a lower semicomputable average-bounded test: its integral is exactly ∑ x m(x). On the other hand, every lower semicomputable test can be presented in terms of an increase of weights, and the limits of these weights, multiplied by P(x), form a lower semicomputable semimeasure. (Note that the latter transformation is not unique: we can redistribute the weights among a string and its continuations without altering the sum over the infinite sequences.) Note that we used that both P (in the second part of the proof) and 1/P (in the first part) are lower semicomputable.

In Proposition 2.21, we can replace the sum with a least upper bound. This way, the following theorem connects three quantities, t P , the supremum and the sum, all of which are equal within a multiplicative constant.

Theorem 2.22. We have

t P (ω) * = sup x⊑ω m(x) P(x) * = ∑ x⊑ω m(x)

P(x) , or in logarithmic notation

d P (ω) + = sup x⊑ω (-log P(x) -Kp(x)).
(3)

Proof. The supremum is now smaller, so only the second part of the proof of Proposition 2.21 should be reconsidered. The lower semicomputable function ⌈d P (ω)⌉ can be obtained as the supremum of a sequence of integer-valued basic functions of the form k i g x i (ω), where g x (ω) = 1 xΩ (ω) = 1 if x ⊑ ω and 0 otherwise. We can also require that if i = j, x i ⊑ x j then k i = k j : indeed, suppose k i = k j . If i < j then we can delete the jth element, and if i > j, then we can replace 2 k i g x i with the sequence of all functions 2 k i g z where z has the same length as x j but differs from it. We have 2t P (ω)

2 ⌈d P (ω)⌉ = sup i 2 k i g x i (ω) = sup x i ⊑ω 2 k i 2 -1 ∑ i:x i ⊑ω 2 k i = 2 -1 ∑ i 2 k i g x i (ω).
The last inequality holds since according to our assumption, all the values k i belonging to prefixes x i of the same sequence ω are different, and the sum of different powers of 2 is at most twice larger than its largest element. Integrating by P, we obtain 4 ∑ i 2 k i P(x i ), hence 2 k i P(x i ) * < m(x i ) by the maximality of m(x), so 2 k i * < m(x i ) P(x i ) . We found

t P (ω) * < sup i:x i ⊑ω m(x i ) P(x i ) sup x⊑ω m(x) P(x) .
Here is a reformulation:

d P (ω) + = sup n (-log P(ω(1 : n)) -Kp(ω(1 : n))).
This reformulation can be generalized:

Theorem 2.23. Let n 1 < n 2 < • • • be an arbitrary computable sequence of natural numbers. Then

d P (ω) + = sup k (-log P(ω(1 : n k )) -Kp(ω(1 : n k ))).
The constant in the + = depends on the sequence n k .

Proof. Every step of the proof of Theorem 2.22 generalizes to this case straightforwardly.

This theorem has interesting implications of the case when instead of a sequence ω we consider an infinite two-dimensional array of bits. Then for the randomness deficiency, it is sufficient to compare complexity and probability of squares starting at the origin.

RANDOMNESS ON SEQUENCES, FOR COMPUTABLE MEASURES15

Historical digression

The above formula for randomness deficiency is a quantitative refinement of the following criterion.

Theorem 2.24 (Criterion of randomness in terms of prefix complexity). A sequence ω is random with respect to a computable measure P if and only if the differencelog P(x) -Kp(x) is bounded above for its prefixes.

(Indeed, the last theorem says that the maximum value of this difference over all prefixes is exactly the average-bounded randomness deficiency.) This characterization of randomness was announced first, without proof, in [START_REF] Chaitin | A theory of program size formally identical to information theory[END_REF], with the proof attributed to Schnorr. The first proof, for the case of a computable measure, appeared in [8].

The historically first clean characterizations of randomness in terms of complexity, by Levin and Schnorr independently in [15] and [START_REF] Peter | Process complexity and effective random tests[END_REF] have a similar form, but use complexity and a priori probability coming from a different kind of interpreter called "monotonic". (In the cited work, Schnorr uses a slightly different form of complexity, but later, he also adopted the version introduced by Levin.) Definition 2.25 (Monotonic complexity). Let us call to strings compatible if one is the prefix of the other. An enumerable subset A ⊆ {0, 1} * × {0, 1} * is called a monotonic interpreter if for every p, p ′ , q, q ′ , if (p, q) ∈ A and (p ′ , q ′ ) ∈ A and p is compatible with p ′ then q is compatible with q ′ . For an arbitrary finite or infinite p ∈ {0, 1} * ∪ Ω, we define

A(p) = sup{ x : ∃p ′ ⊑ p (p ′ , x) ∈ A }.
The monotonicity property implies that this limit, also in {0, 1} * ∪ Ω, is well defined.

We define the (monotonic) complexity Km A (x) of a string x with respect to A as the length of a shortest string p with A(p) ⊒ x. It is known that there is an optimal monotonic interpreter, where optimality has the same sense as above, for prefix complexity. We fix an optimal monotonic interpreter V and denote Km(x) = Km V (x).

Remark 2.26 (Oracle computation). A monotonic interpreter is a slightly generalized version of what can be accomplished by a Turing machine with a one-way read-only input tape containing the finite or infinite string p. The machine also has a working tape and a one-way output tape. In the process of work, on this tape appears a finite or infinite sequence T (p). The work may stop, if the machine halts or passes beyond the limit of the input word; it may continue forever otherwise. It is easy to check that the map p → T (p) is a monotonic interpreter (though not all monotonic interpreters correspond to such machines, resulting in a somewhat narrower class of mappings).

These machines can be viewed as the definition of what we will later call oracle computation: namely, a computation that uses p as an oracle.

In our applications, such a machine would have the form T (p, ω) where the machine works on both infinite strings p and ω as input, but considers p the oracle and ω the string it is testing for randomness.

The class of mappings is narrower indeed. Let S be an undecidable recursively enumerable set of integers. Set T (0 n 1) = 0 for all n ∈ S , and T (0 n 10) = 0 for all n. Now after reading 0 n 1, the machine T has to decide whether to output a 0 before reading the next bit, which is deciding the undecidable set S . It is unknown to us whether this class of mappings yields also a different monotonic complexity.

A monotonic interpreter will also give rise to something like a distribution over the set of finite and infinite strings.

Definition 2.27. Let us feed a monotonic interpreter A a sequence of independent random bits and consider the output distribution on the finite and infinite sequences. Denote M A (x) the probability that the output sequence begins with x. Denote KM V (x) =log M V (x).

Recall that Λ denotes the empty string. A function µ : {0, 1} * → [0, 1] is called a continous semimeasure over the Cantor space Ω if µ(Λ) 1 and µ(x) µ(x0) + µ(x1) for all x ∈ {0, 1} * .

It is easy to check that M V (x) is a lower semicomputable continuous semimeasure. The proposition below is similar in form to the Coding Theorem (Proposition 2.20) above, only weaker, since it does not connect to the complexity Km(x) defined in terms of shortest programs. (It cannot, as shown in [START_REF] Gács | On the relation between descriptional complexity and algorithmic probability[END_REF].) Proposition 2.28. (see [START_REF] Zvonkin | The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms[END_REF]) (a) Every lower semicomputable continuous semimeasure is the output distribution of some monotonic interpreter.

(b) Among lower semicomputable continuous semimeasures, there is one that is maximal within a multiplicative constant.

Definition 2.29 (Continuous a priori probability). Let us fix a maximal lower semicomputable continuous semimeasure and denote it M(x). We call M(x) sometimes the continuous a priori probability, or apriori probability on a tree. Now, the characterization by Levin (and a similar one by Schnorr) is the following. Its proof, technically not difficult, can be found in [START_REF] Gács | Lecture notes on descriptional complexity and randomness[END_REF][START_REF] Li | Introduction to Kolmogorov Complexity and its Applications[END_REF][START_REF] Kh | Algorithmic information theory and Kolmogorov complexity[END_REF].

Proposition 2.30. Let P be a computable measure over Ω. Then the following properties of an infinite sequence ω are equivalent.

(i) ω is random with respect to P.

(ii) lim sup x⊑ωlog P(x) -Km(x) < ∞.

(iii) lim inf x⊑ω -log P(x) -Km(x) < ∞. (iv) lim sup x⊑ω -log P(x) -KM(x) < ∞. (v) lim inf x⊑ω -log P(x) -KM(x) < ∞.
Theorem 2.24 proved above adds to this a next equivalent characterization, namely thatlog P(x) -Kp(x) is bounded above. It is different in nature from the one in Proposition 2.30: indeed, the expressionslog P(x) -Km(x) and log P(x) -KM(x) are always bounded from below by a constant depending only on the measure P (and not on x or ω), whilelog P(x) -Kp(x) is not.

Moreover, in the latter we cannot replace lim sup with lim inf, as the following example shows. Note that we can add to every word x some bits to achieve Kp(y) |y| (where |y| is the length of word y). Indeed, if this was not so, then for the continutations of the word we would have m(y) 2 -|y| , and the sum ∑ y m(y) would be infinite. Let us build a sequence, adding alternatingly long stretches of zeros to make the complexity substantially less than the length, then bits that again bring the complexity up to the length (as shown, this is always possible). Such a sequence will not be random with respect to the uniform measure (since the lim sup of the difference is infinite), but has infinitely many prefixes for which the complexity is not less than the length, making the lim inf finite.

The following statement is interesting since no direct proof of it is known: the proof goes through Theorem 2.23, and noting that since the permutation of terms of the sequence does not change the coin-tossing distribution, it does not change the notion of randomness. More general theorems of this type, under the name of randomness conservation, can be found in [START_REF] Levin | Uniform tests of randomness[END_REF][START_REF] Levin | Randomness conservation inequalities: Information and independence in mathematical theories[END_REF][START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF].

Corollary 2.31. Consider the uniform distribution (coin-tossing) P over binary sequences. The maximal difference between |x| and Kp(x) for prefixes x of a random sequence is invariant (up to a constant) under any computable permutation of the sequence terms. (The constant depends on the permutation, but not on the sequence.)

Here is another corollary, a reformulation of Proposition 2.21:

Corollary 2.32 (Miller-Yu "ample excess" lemma). A sequence ω is random with respect to a computable measure P if and only if

∑ x⊑ω 2 -log P(x)-Kp(x) < ∞.
This corollary also implies the fact mentioned above already:

Corollary 2.33. Every finite sequence x has an extension y with Kp(y) > |y|.

Proof. Take ω random, then xω is random, and therefore by the Miller-Yu lemma xω has arbitrarily long prefixes whose complexity is larger than the length.

Game interpretation

The formula for the average-bounded deficiency can be interpreted in terms of the following game. Alice and Bob make their moves having no information about the opponent's move. Alice chooses an infinite binary sequence ω, Bob chooses a finite string x. If x turns out to be a prefix of ω, then Alice pays Bob 2 n where n is the length of x. (This version of the game corresponds to the uniform Bernoulli measure, in the general case Alice pays 1/P(x).) Recall the game-theoretic notions of pure strategy, as a deterministic choice by a player, and mixed strategy, as a probability distribution over deterministic choices.

Bob has a trivial strategy (choosing the empty string) that guarantees him 1 whatever Alice does. Also Alice has a mixed strategy (the uniform distribution, or, in general case, P) that guarantees her the average loss 1 whatever Bob does. Bob can devise a strategy that will benefit him in case (for whatever reason) Alice brings a nonrandom sequence.

A randomized algorithm that has no input and produces a string (or nothing) can be considered a mixed strategy for Bob (if the algorithm does not produce anything, Bob gets no money). For any such algorithm D the expected payment (if Alice produces ω according to distribution P) does not exceed 1. Therefore, the set of sequences ω where the expected payment (averaged over Bob's random bits) is infinite, is a null set. Observe the following:

(i) For every probabilistic strategy of Bob, his expected gain (as a function of Alice's sequence) is an average-bounded test. (From here already follows that this expected value will be finite, if Alice's sequence is random in the sense of Martin-Löf.) (iii) Therefore if we take the algorithm outputting the discrete apriori probability m(x), then Bob's expected gain will be a universal test (by the proved formula for the universal test). Using the apriori probability as a mixed strategy enables Bob to punish Alice with an infinite penalty for any non-randomness in her sequence.

(ii) If m(x)
One can consider more general strategies for Bob: he can give for a pure strategy, not only a string x, but some basic function f on Ω with nonnegative values. Then his gain for the sequence ω brought by Alice is set to f (ω)/ f (ω) dP. (The denominator makes the expected return equal to 1.) To the move x corresponds the basic function that assigns 2 |x| to extensions of x and zero elsewhere. This extension does not change anything, since this move is a mixed strategy and we allow Bob to mix his strategies anyway. (After producing f , Bob can make one more randomized step and choose some of the intervals on which f is constant, with an appropriate probability.) In this way we get another formula for the universal test:

t P (ω) * = ∑ f m( f ) f (ω) f (ω) dP ,
where the sum is taken over all basic functions f . This formula might be useful in more general situations (not Cantor space) where we do not work with intervals and consider some class of basic functions instead. On concluding this part let us point to a similar game-theoretical interpretation of probability theory developed in the book [START_REF] Shafer | Probability and Finace: It's Only a Game![END_REF] of Shafer and Vovk. There, the randomness of an object is not its property but, roughly speaking, a kind of guarantee with which it is being sold.

3 From tests to complexities Formula (3) expresses the randomness deficiency (the logarithm of the universal test) of an infinite sequence in terms of complexities of its finite prefixes. A natural question arises: can we go in the other direction? Is it possible to express the complexity of a finite string x, or some kind of "randomness deficiency" of x, in terms of the deficiencies of x's infinite extensions? Proposition 2.6 and the discussion following it already brought us from infinite sequences to finite ones. This can also be done for the universal test: Definition 3.1. Fix some computable measure P, and let t be any (averagebounded) test for P. For any finite string x let t(x) be the minimal deficiency of all infinite extensions of x:

t(x) = inf ω⊒x t(ω).
By Proposition 2.7, t is a lower semicomputable function defined on finite strings, and the function t can be reconstructed back from t; so if t P is our fixed universal test then tP can be considered as a version of randomness deficiency for finite strings.

The intuitive meaning is clear: a finite sequence z looks non-random if all infinite sequences that have prefix z look non-random.

Question 2. Kolmogorov [START_REF] Kolmogorov | On the logical foundations of information theory and probability theory[END_REF] had a somewhat similar suggestion: for a given sequence z we may consider the minimal deficiency (with respect to the uniform distribution, defined as a difference between length and complexity) of all its finite extensions. Are there any formal connections?

Let us spell out what we found, in more general terms. Definition 3.2 (Extended test for a computable measure). A lower semicomputable, monotonic (with respect to the prefix relation) function T : {0, 1} * → [0, ∞] is called an extended test for computable measure P if for all N the average over words of length N is bounded by 1:

∑ x:|x|=N P(x)T (x) 1.
Monotonicity guarantees that the sum over words of a given length can be replaced by the sum over an arbitrary finite (or even infinite) prefix-free set S :

∑ x∈S P(x)T (x) 1. (4)
(Indeed, extend the words of S to some common greater length.)

Proposition 3.3. Every extended test generates (in the sense of Definition 2.5) some averge-bounded test on the infinite strings. Conversely, every averagebounded test on the infinite sequences is generated by some extended test.

Proof. The first part follows immediately from the definition (and the theorem of monotone convergence under the integral sign). In the opposite direction, we can set for example T (x) = t(x), or refer to Proposition 2.4 if we do not want to rely on compactness.

The existence of a universal extended test is proved by the usual methods:

Proposition 3.4. Among the extended tests T (x) for a computable measure P(x) there is a maximal one, up to a multiplicative constant.

Definition 3.5. Let us fix some dominating extended test and call it the universal extended test.

Proposition 3.6. The universal extended test coincides with tP (x) to within a bounded factor.

Proof. Since tP is an extended test, it is not greater than the universal test (to within a bounded factor). On the other hand, the universal extended test generates a test on the infinite sequences, it just remains to compare it with the maximal one.

If our space is not compact (say, it is the set of infinite sequences of integers), then tP (x) is not defined, but there is still a universal extended test, which we will denote by t P (x).

Warning: not all extended tests generating t P (ω) are maximal. (For example, one can make the test equal to zero on all short words, transferring its values to its extensions.)

The advantage of the function t P (x) is that it is defined on finite strings, the condition (4) (for finite sets S ) imposed on it is also more elementary than the integral condition, but clearly implies that it generates a test.

The method just shown is not the only way to move to tests on prefixes from tests on infinite sequences: Definition 3.7. Assume that the computable measure P is positive on all intervals: P(x) > 0 for all x. Let tP (x) be the conditional expected value of t P (ω) if a random variable ω ∈ Ω has distribution P and the condition is ω ⊒ x. In other terms: let tP (x) be the average of t P on the interval xΩ, that is let tP (x) = U(x)/P(x) where

U(x) = xΩ t P (ω) dP(ω).
The function U is a lower semicomputable semimeasure. (It is even a measure, but the measure is not guaranteed to be computable and the measure of the entire space Ω is not necessarily 1. In other words, we get a measure on Ω that has density t P with respect to P.) This implies that the function tP (x) is a martingale, according to the following definition. Definition 3.8. A function g : {0, 1} * → R is called a martingale with respect to the probability measure P if

P(x)g(x) = P(x0)g(x0) + P(x1)g(x1).

It is a supermartingale if at least the inequality holds here.

Note that, as a martingale, the function tP (x) is not monotonically increasing with respect to the prefix relation.

Theorem 3.9. m(x)

P(x) * < t P (x) * < tP (x) * < M(x) P(x) , ( 5
)
where m is the a priori probability on strings as isolated objects (whose logarithm is minus prefix complexity) and M is the a continuous priori probability as introduced in Definition 2.29.

Proof. In fact, the first inequality can be made stronger: we can replace m(x)/P(x) by ∑ t⊑x m(t)/P(t). Indeed, this sum is a part of the expression for t P (ω) for every ω that starts with x.

The second inequality uses Proposition 3.6 and relates the minimal and average values of a random variable. The third inequality just compares the lower semicomputable semimeasure U(x) and the maximal semimeasure M(x).

Note that while tP (x) is a martingale, M(x) P(x) is a supermartingale: it is actually maximal within multiplicative constant, among the lower semicomputable supermartingales for P. Remarks 3.10. 1. We may insert * < max t⊑x m(t)

P(t) * < ∑ t⊑x m(t) P(t) * < (6)
between the first and the second terms of (5).

2. Using the logarithmic scale, we get

-log P(x) -Kp(x) + < log t P (x) + < log tP (x) + < -log P(x) -KM(x).
3. The Measure U depends on P (recall that U is a maximal measure that has density with respect to P), so for different P's, for example with different supports, like the Bernoulli measures with different parameters, we get different measures. But this dependence is bounded by the inequality above: it shows that the possible variations do not exceed the difference between Kp(x) and KM(x).

4. The rightmost inequality cannot be replaced by an equality. For example, let P be the uniform (coin-tossing) measure. Then the value of U(x) tends to 0 when x is an increasing prefix of a computable sequence (we integrate over decreasing intervals whose intersection is a singleton that has zero uniform measure). On the other hand, the value M(x) is bounded by a positive constant for all these x.

5. We used compactness (the finiteness of the alphabet {0, 1}) in proving Proposition 2.7. But we could have used Proposition 2.6 and the discussion following it for a starting point, obtaining analogous results for the Baire space of infinite sequences of natural numbers.

All quantities listed in Theorem 3.9 can be used to characterize randomness: a sequence ω is random if the values of the quantity in question are bounded for its prefixes. Indeed, the Levin-Schnorr theorem guarantees that for a random sequence the right-hand side is bounded, and for a non-random one the left-hand side is unbounded. The monotonicity of the second term guarantees that all expressions except the first one tend to infinity. As we already mentioned above, one cannot say this about the first quantity.

Question 3. Some quantities used in the theorem (t P (x) and two added ones in [START_REF] Gács | Lecture notes on descriptional complexity and randomness[END_REF]) are monotonic (with respect to the prefix partial order of x) by definition. We have seen that tP (x), as a martingale, is not monotonic. What can be said about M(x) P(x) ?

All these quantities are "almost monotonic" since they do not differ much from the monotonic ones.

Bernoulli sequences

One can try to define randomness not only with respect to some fixed measure but also with respect to some family of measures. Intuitively a sequence is random if we can believe that it is obtained by a random process that respects one of these measures. As we show later, this definition can be given for any effectively compact class of measures. But to make it more intuitive, we start with a specific example: Bernoulli measures.

Tests for Bernoulli sequences

The Bernoulli measure B p arises from independent tossing of a non-symmetric coin, where the probability of success p is some real number in [0, 1] (the same for all trials). Note that we do not require p to be computable. Definition 4.1 (Average-bounded Bernoulli test). A lower semicomputable function t on infinite binary sequences is a Bernoulli test if its integral with respect to any B p does not exceed 1.

Proposition 4.2 (Universal Bernoulli test). There exists a universal (maximal up to a constant factor) Bernoulli test.

Proof. A lower semicomputable function is the monotonic limit of basic functions. If the integral of a given basic function with respect to every B p is less or equal than 1 for all p, this fact can be established effectively (indeed, the integral is a polynomial in p with rational coefficients). This allows us to eliminate all functions unfit to be tests, and to list all Bernoulli tests. Adding these up with appropriate coefficients, we obtain a universal one. Definition 4.3. We fix a universal Bernoulli test and denote it t B (ω). Its logarithm will be called Bernoulli deficiency d B (ω). A sequence is called a Bernoulli sequence if its Bernoulli deficiency is finite.

Again, we may modify the definition to within an additive constant, to make it nonnegative and integer.

The informal motivation is the following: ω is a Bernoulli sequence if the claim that it is obtained by independent coin tossing (coin symmetry is not required) looks plausible. And this statement is not plausible if one can formulate some property that is true for ω but defines an "effectively Bernoulli null set" (we did not formally introduce this notion, but could, analogously to effective null sets).

Analogously to the case of computable measures, we can extend the class test to finite sequences:

Definition 4.4 (Extended Bernoulli test). A lower semicomputable monotonic function T : {0, 1} * → [0, ∞] is called an extended Bernoulli tests if for all natural numbers N and for all p ∈ [0, 1] the inequality ∑ x:|x|=N B p (x)T (x) 1 holds.
As for computable measures, there is a connection between tests for finite and tests for infinite sequences: There is a dominating universal extended Bernoulli test: it generats a universal Bernoulli test on Ω. As earlier, we wil use the same notation t B for the maximal tests on the finite and on the infinite sequences. Of course, it generates a universal Bernoulli test.

Other characterizations of the Bernoulli property

Just as for the randomness with respect to computable measures, several equivalent definitions exist. One may consider probability-bounded tests (the probability of the event t(ω) > N on any of the measures B p must be not greater than 1/N). One may call a test, following Martin-Löf's definition for the computable measures, any computable sequence of effectively open sets U i with B p (U i ) 2 -i for all i and all p ∈ [0, 1]. All these variant definitions are equivalent (and this is proved just as for randomness with respect to a computable measures). Martin-Löf defined a Bernoulli test as a family of sets of words

U 1 ⊇ U 2 ⊇ U 3 ⊇ • • • ; each
of these sets is hereditary upward, that is for every word contains all of its extensions. The following restriction is made on these sets: consider arbitrary integer n 0 and k from 0 to n; it is required that for all i the share of words in B(n, k) belonging to U i is not greater than 2 -i .

For convenience of comparison let us replace the sets U i with an integervalued lower semicomputable function d for which

U i = { x : d(i) i }.
The hereditary property of the sets U i implies the monotonicity of this function d with respect to the prefix relation. Besides this, it is required that the event d i within each set B(n, k) is not greater than 2 -i . Clearly, these requirements correspond to probability-bounded extended tests (in the logarithmic scale), only in place of the class B p on words of length n another set of measures is considered, those concentrated on words of a given length with a given number of ones. The measures in the class B p take equal values on words of equal lengths with equal number of ones, and are therefore representable by a mixture of uniform measures on B(n, k) with some coefficients. Replacing B p with these measures, the condition becomes stronger.

Let us show that nonetheless, the set of Bernoulli sequences does not change from such a replacement; moreover, the universal test (as a function on infinite sequences) does not change (as usual, to within a bounded factor). We will show this for the average-bounded variant of tests (changing Martin-Löf's definition accordingly); this does not change the class of Bernoulli sequences. The reasoning is analogous for the probability-bounded tests.

|B(n, k)| -1 ∑ x∈B(n,k) f (x) 1. ( 7
)
The last condition says that not only is the average of f (x) bounded by 1 over the set {0, 1} n , as in extended tests for the unbiased coin-tossing measure, but its average is bounded by 1 separately in each set B(n, k) whose union is {0, 1} n .

Having such a test for words of bounded length, it can be continued by monotonicity: Proposition 4.8. If a combinatorial Bernoulli test f (x) is given on strings x of length less than n, then extending it to longer strings using monotonicity we get a function that is still a combinatorial Bernoulli test.

Proof. We extend f to words of length n, setting f (x0) = f (x1) = f (x) for words x of length n -1. The set B(n, k) consists of two parts: words ending on zero and words ending on one. The first ones are in a one-to-one correspondence with B(n-1, k), the second ones with B(n-1, k -1). The function conserves the values in this correspondence, therefore the average in both parts is not greater than 1. Hence, the average over the whole B(n, k) is not greater than 1.

The following is obtained by standard methods: Proposition 4.9 (Universal combinatorial Bernoulli test). Among combinatorial Bernoulli tests, there is one that is maximal to within a bounded factor. We will call the function obtained this way a universal combinatorial test on Ω and will denote it also by b.

(By monotonicity, the least upper bound in this definition can be replaced with a limit.) Let us show that the this test coincides (to within a bounded factor) with the Bernoulli tests introduced earlier in Definition 4.3.

Theorem 4.11. b(ω) * = t B (ω).
Proof. We have already seen that b(x) is an extended Bernoulli test (from the bounds on the average on each part B(n, k) follows the bound on the expected value by the measure B p , since this measure is constant on each part). Consequently b(ω) * < t B (ω). The converse is not true: an extended Bernoulli test may not be a combinatorial test. But it is possible to construct a combinatorial test that takes the same values (to within a bounded factor) on the infinite sequences, and only this is asserted in the theorem.

Here is the idea. Consider an extended Bernoulli test t on words of length n and transfer it to words of much greater length N (applying the old test to its beginnings of length n). We obtain a certain function t ′ . We have to show that t ′ is close to some combinatorial test (that is only exceeds it by a constant factor). For this, t ′ must be averaged over the set B(N, K) for an arbitrary K between 0 and N. In other words, we must average t by the probability distribution on the n-bit prefixes of sequences of length N containing K ones. With N ≫ n this distribution will be close to the Bernoulli one with distribution p = K/N.

In terms of elementary probability theory, we have an urn with N balls, K of which is black, and take out from it n balls. We must compare the probability distribution with the Bernoulli one that would have been obtained at sampling with replacement. Let us show that for N = n 2 the distribution without replacement does not exceed the one with replacement more than O(1) times. (The inequality does not hold in the other direction: for K = 1 without replacement we cannot obtain a word with two ones, and with replacement we can. But we only need the inequality in the given direction.) Indeed, in sampling without replacement the probability that a ball of a given color will be drawn is equal to the quotient the number of remaining balls of this color the number of all remaining balls .

The number of balls of this color is not more than in the case with replacement, on the other hand the denominator is at least Nn. Therefore the probability of any combination during sampling with replacement is at most the probability of the same combination with replacement, multiplied by N/(Nn) to the power n.

For N = n 2 the multiplier (1 + O(1/n)) n = O(1) is obtained.
This way, taking the extended Bernoulli test t and then defining t ′ (x) on a word x of length N as t on the prefix of x of length ⌊ √ N⌋, the obtained func-tion t ′ will be a combinatorial test to within a bounded factor. (Note that its monotonicity follows from that of t.)

Criterion for Bernoulli sequences

It is natural to compare the notion of Bernoulli sequence (those sequences for which the Bernoulli test is finite) with the notion of a sequence random with respect to the measure B p . But Martin-Löf definition of randomness assumes that the measure is computable. Therefore it cannot be applied directly to B p if p is non-computable. But this definition can be relativized, and if (the binary expansion of) p is given as an oracle (see Remark 2.26), then the measure B p becomes computable and randomness is well defined. The following theorem supports an intuitive idea of Bernoulli sequence as a sequence that is random with respect to some Bernoulli measure:

Theorem 4.12. A sequence ω is a Bernoulli sequence if and only if it is random with respect to some measure B p , with oracle p ∈ [0, 1].

By "with oracle p", we understand the possiblity to obtain from each i the ith bit in the binary expansion of the real number p (which is essentially unique, except in those cases when p is binary-rational, and in these cases both expansions are computable, and the oracle is trivial).

Before proving the theorem (even in a stronger quantitative form), we introduce a new notion, of a test depending explicitly on the parameter p of the Bernoulli measure B p , which later will be extended to arbitrary (not just Bernoulli) measures. The required result will be obtained as the combination of the following claims: (a) Among the "uniform" randomness tests, there exists a maximal test t(ω, p).

(b) The function ω → inf p t(ω, p) coincides (as usual, to within a bounded factor) with the universal Bernoulli test.

(c) For a fixed p, the function ω → t(ω, p) coincides (to the same precision) with the maximal randomness test for the (p-computable) measure B p , relativized to p. These three assertions imply Theorem 4.12 easily: sequence ω is Bernoulli, if the Bernoulli test is finite; the latter is equal to the greatest lower bound of t(ω, p), hence its finiteness means t(ω, p) < ∞ for some p, which is equivalent to the relativized randomness with respect to the measure B p .

We need some technical preparation. The randomness tests (as functions of two variables) will also be lower semicomputable, but the definition of this concept needs to be extended, since an additional real parameter is involved. (In what follows we will also consider a more general situation, in which the second argument is a measure.) Definition 4.13. In the space Ω × [0, 1], let us call basic rectangles all sets of the form xΩ × (u, v), where u < v are rational numbers. (A technical point: we allow u, v to be outside [0, 1], but in this case the rectangle we mean is xΩ

× ([0, 1] ∩ (u, v)).) A function f : Ω × [0, 1] → [-∞, ∞]
is called lower semicomputable if there is an algorithm that, given a rational r on its input, enumerates a sequence of basic rectangles whose union is the set of all pairs (ω, p) with f (ω, p) > r.

The notion of upper semicomputability is defined analogously, and is equivalent to the lower semicomputablity of (f ).

A function with finite real values is called computable if it is both upper and lower semicomputable. This definition, as earlier, requires that the preimage of (-∞, r) be an effective open set uniformly in r, only now we consider effectively open sets in Ω × [0, 1], defined in a natural way.

Since the intersection of effective open sets is effective open, the followingmore intuitive-formulation is obtained for computability: Proposition 4.14. A real function f : Ω × [0, 1] → R is computable if and only if for every rational interval (u, v) its preimage is the union of a sequence of basic rectangles that are effectively enumerated, uniformly in u and v.

The intuitive meaning of this characterization will become clearer after observing that to "give approximations to α with any given precision" is equivalent to "enumerate all intervals containing α". Therefore for a computable function f we can find approximations to f (ω, p), if we are given appropriate approximations to ω and p.

We can reformulate the definition of (non-negative) lower semicomputable function, introducing the notion of basic functions. It is important for us that the basic functions are continuous, therefore the dependence on the real argument will be piecewise linear, without jumps. Definition 4.15 (Basic functions, Bernoulli case). We define an enumerated list of basic functions E = {e 1 , e 2 , . . . } over the set Ω × [0, 1] as follows. For x ∈ {0, 1} * , positive integer k and rational numbers u, v with u + 2 -k < v -2 -k define the function g x,u,v,k (ω, p) as follows. If x ⊑ ω, then it is 0. Otherwise, its value does not depend on ω and depends piecewise linearly on p: it is 0 if p ∈ (u, v) and 1 if u + 2 -k p v -2 -k , and varies linearly in between. Now E is the smallest set of functions containing all g x,u,v,k , and closed under maxima, minima and rational linear combination. Now lower semicomputable functions admit the following equivalent characterization:

Proposition 4.16. A function f : Ω × [0, 1] → [0, ∞] is

lower semicomputable if and only if it is the pointwise limit of an increasing computable sequence of basic functions. (It follows that basic functions are computable.)

Proof. This would be completely clear if for basic functions we also allowed the indicator functions of basic rectangles and the maxima of such functions. But we want the basic functions to be continuous (this will be important in what follows). One must note therefore that for k → ∞ the function g x,u,v,k converges to the indicator function of a rectangle.

The continuity of the basic functions guarantees the following important property: (Computability is understood in the above described sense; we remark that every computable function is continuous. An analogous statement holds for an arbitrary computable function f , not only for basic functions, but we do not need this.)

The following fact, proved in [START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF], will be used in the present paper a number of times, also in generalizations, but with essentially the same proof.

Proposition 4.18 (Trimming). Let ϕ : Ω × [0, 1] → [0, ∞]
be a lower semicomputable function. There is a lower semicomputable function ϕ ′ (ω, p) not exceeding ϕ(ω, p) with the property that for all p: Proof of Lemma 4.22. Consider first the case when p is a computable real number. Then the function t p : ω → t(ω, p) (where t is a uniform randomness test for Bernoulli measures) is lower semicomputable (we can enumerate all intervals that contain p and combine then with an algorithm for t; in this way we represent t p as the least upper bound of the computable sequence of basic functions).

(a) ϕ ′ (ω, p)B p (dω) 2; (b) If ϕ(ω, p)B p (dω) 1 then ϕ ′ (ω, p) = ϕ(ω,
A similar argument works for an arbitary p and shows that t p is lower semicomputable with a p-oracle. Thus, t p does not exceed the universal relativized test with respect to B p .

The reverse implication is a bit more difficult. Assume that t is a lower semicomputable (with oracle p) randomness test with respect to B p . We need to find a uniform Bernoulli test t ′ that majorizes it (for a given p). This t ′ must be lower semicomputable, now (a subtle but important point) using p as an argument of the function t ′ , not as an oracle. In other words, one has to extend a function defined initially only for a single p, to all values of p, while also guaranteeing the bound on the integral.

As a warmup consider the case of computable p. Then no oracle is needed, and t is lower semicomputable. Adding dummy variable p we get a lower semicomputable function of two arguments. But this function may not be a uniform test since its expectation with respect to B q may be arbitrary if q = p. However, Proposition 4.18 helps transform it into a t ′ (which will now really depend on q) with t ′ (ω, q)B q (dω) 2 for all q and t ′ (•, p) = t(•, p). Dividing t ′ into half provides a uniform test. Now consider the case of noncomputable p. In this case p is irrational, so the bits of its binary expansion can be obtained from any sequence of decreasing rational intervals that converge to p. Therefore an oracle machine that enumerates approximations for t from below (having p as an oracle) can be transformed into a machine that enumerates from below some function t(ω, q), that coincides with t(ω) if q = p. The function t may not be a uniform Bernoulli test (its expectations for q = p can be arbitrary); but it again can be trimmed with the help of Proposition 4.18.

Arbitrary measures over binary sequences

In this section, we generalize the theory to arbitrary measures, not only Bernoulli ones, but still stay in the space Ω of binary sequences.

Notation 5.1. The set of all probability measures over the space Ω is denoted by M (Ω). (Recall that the measure of the whole space Ω is equal to 1.)

Uniform randomness tests Definition 5.2 (Uniform tests).

A uniform test is a lower semicomputable function t(ω, P) of two arguments (ω is a sequence, P is a measure on Ω) with t(ω, P) P(dω) 1 for every measure P.

However, we have to define carefully the notion of a lower semicomputability in this case. The set M (Ω) of all measures is a closed subset of the infinite (countable) product

Ξ = [0, 1] × [0, 1] × [0, 1] × • • • (8)
(the measure is defined by the values P(x) for all strings x; these values should satisfy the equations (2), so we get a closed subset).

Let us introduce basic open sets and computability notions for the set Ω × M (Ω). In much of what follows, we will exploit the fact that, due to the finiteness of the alphabet {0, 1}, the space Ω of infinite binary sequences is compact, and also the set of measures M (Ω) is compact. Recall that a set C is compact if every cover of C by open sets contains a finite subcover. We need, however, an effective version of compactness:

Definition 5.4 (Effective compactness). A compact subset C of M (Ω) is called effectively compact if the set { S : S is a finite set of basic open sets and E∈S E ⊇ C } is enumerable.
The set M (Ω) itself is, as it is easy to see, compact and effectively compact. It is compact, as said above, as a closed set in the product of compact spaces, and the effectivity follows from the fact that we can check whether some given basic sets cover the whole space (we are dealing with linear equations and inequalities in a finite number of variables, where everything is algorithmically decidable). From here, it also follows: In view of later generalization to cases where the space itself may not be compact, we will refer to some effectively closed sets of M (Ω) as effectively compact.

Now we introduce a dense set of computable functions called basic functions on the set Ω × M (Ω), similarly to Definition 4.15. Their specific form is not too important.

Definition 5.6 (Basic functions for binary sequences and arbitrary measures). The set of basic functions over the set Ω × M (Ω) is defined analogously to Definition 4.15, starting from the functions

g x,y,u,v,k : Ω × M (Ω) → [0, 1]
with x, y ∈ {0, 1} * defined as follows. If x ⊑ ω, then g x,y,u,v,k (ω, P) = 0. Otherwise, its value does not depend on ω and depends piecewise linearly on P(y) in a way that it is 0 if

P(y) ∈ (u, v) and 1 if u + 2 -k P(y) v -2 -k .
The analogue of Proposition 4.16 holds again: a lower semicomputable function is the monotonic limit of a computable sequence of basic functions (which themselves are computable).

The analogue of Proposition 4.17 holds also: the integral f (ω, P)P(dω) of a basic function is computable as a function of the measure P, uniformly in the number of the basic function.

Finally, the analogue of Proposition 4.18 holds again:

Theorem 5.7 (Trimming). Let ϕ(ω, P) be a lower semicomputable function.

Then there exists a lower semicomputable function ϕ ′ (ω, P) such that for all P:

(a) ϕ ′ (ω, P)P(dω) 2, (b) if ϕ(ω, P)P(dω) 1 then ϕ ′ (ω, P) = t(ω, P) for all ω.
The proof is completely analogous to the proof we gave for Proposition 4.18. This allows the construction of a universal test as a function of a sequence and an arbitrary measure over Ω: Theorem 5.8. There exists a maximal (maximal to within a bounded factor) uniform randomness test.

Proof. We use the same approach as before: we trim a lower semicomputable function in such a way that it becomes a test (or almost a test) and remains untouched if it were a test in the first place. Definition 5.9. Let us fix a universal uniform randomness test t(ω, P).

We call a sequence ω uniformly random with respect to a (not necessarily computable) measure P if t(ω, P) < ∞.

Let us show that for computable measures, the new definition coincides with the old one.

Proposition 5.10. Let P be a computable measure, let t P (ω) be a universal (average-bounded) randomness test for P as, and t(ω, P) the universal uniform test defined above. Then there are constants c 1 , c 2 > 0 such that c 1 t P (ω) t(ω, P) c 2 t P (ω).

The constants c 1 , c 2 here depend on the choice of measure P and of the choice of the test t P for this measure (this choice was done in an arbitrary way for each computable measure).

This proposition shows, that in the case of the computable measures, uniform randomness coincides with randomness in the sense of Martin-Löf.

Proof. Let us show t(ω, P) c 2 t P (ω) first. The function ω → t(ω, P) is lower semicomputable since we can effectively enumerate all intervals in the space of measures that contain P; therefore it is dominated by t P (ω).

To prove t(ω, P) c 1 t P (ω), consider the lower semicomputable function

t(ω, Q) = t P (ω).
The function (ω, Q) → t(ω) is not guaranteed to be a uniform randomness test, since its integral can be greater than 1 if Q = P. However, it can be trimmed without changing it at P, and then it still remains (almost) a test.

We are also interested in tests defined just for one, not necessarily computable, measure P: Definition 5.11. We will call a function f : Ω → [0, ∞] lower semicomputable relatively to measure P if it is obtained from a lower semicomputable function on the set Ω × M (Ω) after fixing the second argument at P.

For a measure P ∈ M (Ω), a P-test of randomness is a function f : Ω → [0, ∞] lower semicomputable from P with the property f (ω) dP 1.

It seems as if a P-test may capture some nonrandomnesses that uniform tests cannot-however, this is not so, since trimming (see Theorem 5.7) generalizes: Theorem 5.12. Let P 0 be some measure along with some P 0 -test t P 0 (ω). There is a uniform test t ′ (•, •) with t P 0 (ω) 2t ′ (ω, P 0 ). On the other hand, the restriction of any uniform test to the measure P is a P-test.

The notion of extended text can be generalized to uniform tests: Definition 5.13 (Extended uniform test). A lower semicomputable function T : {0, 1} * × M (Ω) → [0, 1] monotonic with respect to the prefix relation is called an extended uniform test if for all n and all distributions P we have ∑ x:|x|=n T (x, P)P(x) 1.

As earlier, due to monotonicity, we could sum not only over words of a given length, but over an arbitrary prefix-free set.

The following follows from the analogue of Proposition 4.16 (representing a nonnegative lower semicomputable function as a sum of nonnegative basic functions): Proposition 5.14. Every uniform test t(ω, P) can be generated by an extended uniform test in the sense of t(ω, P) = sup x⊑ω T (x, P). Conversely, every extended uniform test T generates a uniform test t.

Among the uniform extended tests, it is also possible to select a maximal one (using an analogous trimming method and summing the results). We fix an extended uniform test and denote it t(x, P) (where x ∈ {0, 1} * , and P is a measure over Ω). It generates a maximal uniform test t(ω, P) (to within a bounded factor).

Remark 5.15. Much of the theory worked out at the beginning of this paper for 0-1 sequences holds also for sequences whose elements are arbitrary natural numbers. The extended tests of Definition 5.13 generalize, and the existence of a uniform universal extended test is proven in the same way. But it becomes important to define extended tests directly, and not via tests for infinite sequences, since compactness may not hold. Proposition 5.10 allows us to generalize a result about Bernoulli measures: Theorem 5.16. Let P be a measure computable with some oracle A. Assume also that A can be effectively reconstructed as the values of the measure are provided with more and more precision. Then a sequence ω is uniformly random with respect to P if and only if it is random with respect to P with oracle A.

(Since the oracle A makes P computable, the notion of Martin-Löf randomness is well defined.)

Proof. Assume that t(ω, P) = ∞ for the universal uniform test t. Note that t(•, P) is an A-lower semicomputable function and is a P-test, so ω is nonrandom with respect to P with oracle A.

On the other hand, let t(ω, A) be some A-lower semicomputable P-test with t(ω, A) = ∞. That A can be reconstructed from P means that there is a computable mapping f from measures to binary sequences (oracles) defined at least over P, with A = f (P). But then (ω, P) → t(ω, f (P)) is a P-test. The uniformization theorem 5.12 converts it into a uniform test that is infinite on (ω, P).

Let us note that not all measures P satisfy the condition of the theorem (it means that the mass problem of "show approximations to the values of P" is equivalent to the decision problem of some set; on the degrees of such mass problems, see [START_REF] Miller | Degrees of unsolvability of continuous functions[END_REF]). Later, in Theorem 5.36, we show a characterization of uniform randomness for arbitrary measures (in terms of Martin-Löf randomness with oracle).

Another application of the trimming technique: let us show that the notion of uniform randomness test is indeed a generalization of the notion of an uniform Bernoulli test we introduced earlier in Definition 4.1.

Theorem 5.17. Let t(ω, P) be the universal uniform test and let t(ω, p) be the universal uniform Bernouli test defined in Lemma 4.20. Then t(ω, B p ) * = t(ω, p).

(Here B p is the Bernoulli measure with parameter p.)

Proof. For the inequality * < note that the function (ω, p) → t(ω, B p ) is an uniform Bernoulli test, since the mapping p → B p is computable mapping (in a natural sense).

For the other direction, there exists a computable function on measures that maps B p to p (just take the probability of the one-bit string). Combining this function with t(ω, p), we get a lower semicomputable function f (ω, P) on general measures P with f (ω, B p ) = t(ω, p). The function f (ω, p) is not a uniform test yet, but again the trimming technique given by Theorem 4.18 yields the desired result.

Apriori probability with an oracle, and uniform tests

For a computable measure, we had an expression for the universal test via apriori probability in Proposition 2.21. An analogous expression exists also for the universal uniform test: To be honest, we still owe the reader the definition of the concept of apriori probability with respect to a measure, that is the quantity m(x | P). We do this right away, before returning to the proof. Definition 5.19. A nonnegative function t(x, P) whose arguments are the binary word x and the measure P will be called a uniform lower semicomputable semimeasure, if it is lower semicomputable and ∑ x t(x, P) 1 for all measures P over Ω.

Proposition 5.20. Among the uniform lower semicomputable semimeasures, there is a largest one to within a multiplicative constant. This is proved by the same method as the existence of a universal test (and even simpler, since the constraints on the values of the test do not depend on the measure).

Definition 5.21. We will fix one such largest semimeasure, and call it the apriori probability with respect to P. We will denote it by m(x | P).

(The vertical bar in place of a comma emphasizes the similarity to the conditional apriori probability normally considered.)

Proof of Proposition 5.18. We need to check two things. First we need to convince ourselves that the right-hand side of the formula defines a uniform test. Every member of the sum can be considered to be a function of two arguments, equal to 0 outside the cone of extensions of x, and equal to m(x | P)/P(x) inside the cone. For every x, the functions m(x | P) and 1/P(x) are lower semicomputable (uniformly in x), and the sum gives a lower semicomputable function. The integral of this function by any measure P is equal to the sum of the integrals of the members, that is ∑ x m(x | P), and therefore does not exceed 1.

There is a special case, when P(x) = 0 for some x. In this case the corresponding member of the sum becomes infinite for any ω extending x. But since the measure of this cone is zero, the integral by this measure is by definition zero, and therefore the additive term, if is not equal to m(x | P), is simply smaller. This way, the right-hand side of the formula is a uniform test, and therefore does not exceed the universal uniform test: we proved the inequality *

>.

The second part of the proof is not so simple: observing the increase of the values of the uniform test, we must distribute this increase among the different members of the sum of the right-hand side, while preserving lower semicomputability. The difficulty is that if, say, the lower semicomputable function was 1 on some effectively open set A, and outside it was zero, and then this set was changed to a larger set B, then the difference (the characteristic function of B\ A) will not in general be lower semicomputable since in the set of measures (as also on a segment) the difference of two intervals will not be an open The.

This problem is solved by moving to continuous functions. Let us be given an arbitrary uniform test t(ω, P). Since it is lower semicomputable, it can be represented as the limit of a nondecreasing sequence of basic functions, orpassing to differences-in the form of a sum of a series of nonnegative basic functions: t(ω, P) = ∑ i t i (ω, P).

Being basic, the function t i of ω depends only on a finite prefix of the sequence ω; denote the length of this prefix by n i . For every word x of length n i we get some lower semicomputable function t i,x (P), where t i (ω, P) = t i,x (P) if ω begins by x. Now define m i (x, P) = t i,x (P) • P(x), if x has length n i (for the other lengths, zero). The function m i is lower semicomputable (as the product of two lower semicomputable functions) uniformly in i, and therefore the sum m(x, P) = ∑ i m i (x, P) will be lower semicomputable.

Let us show that m is a semimeasure, that is ∑ x m(x, P) 1 for all P. Indeed, in ∑ i m i (x, P) the nonzero terms correspond to words of length n i , and this sum is equal to ∑ x t i,x (P) • P(x), that is exactly the integral t i (ω, P) P(dω), and the sum of these integrals does not exceed 1 by our condition.

Moreover, if for all prefixes x of the sequence ω the measure P(x) is not equal to zero, then

∑ x⊑ω m i (x, P) P(x) = t i,x i (P) • P(x i ) P(x i ) = t i (ω, P)
(here x i is the prefix of length n i of ω), hence after summing over i ∑ x⊑ω m(x, P) P(x) = t(ω, P), and it just remains to apply the maximality of the apriori probability to obtain the * <-inequality for the case that all prefixes of ω have nonzero P-measure. On the other hand, if one of these has zero P-measure, then the right-hand side is infinite, and so here the inequality is also satisfied. Question 4. For the universal randomness test with respect to a computable measure, in this formula one could replace the sum with a maximum. Is this possible for uniform tests? (The reasoning applied there encounters difficulties in the uniform case.) Can one define apriori probabilithy on the tree in a reasonable way, and prove a uniform variant of the Levin-Schnorr theorem?

Effectively compact classes of measures

We have considered Bernoulli tests, that is lower semicomputable functions t(ω) that are tests with respect to all Bernoulli measures. In this definition, in place of Bernoulli measures, an arbitrary effectively compact class can be taken: Definition 5.22. Let C be an effectively compact class of measures over Ω. We say that lower semicomputable function t on Ω is a C -test if t(ω) dP 1 for every P ∈ C . Remark 5.24. Since C is compact and the function t(ω, P) is lower semicomputable, the inf-operation can be replaced by the min-operation.

Question 5. Can we give criteria for randomness with respect to natural closed classes of measures (for example in terms of complexity)? How can we describe Bernoulli sequences in terms of complexities of their initial segments? It is known that the main term of the randomness deficiency is

log n k -Kp(x | n, k).
The lecture notes [START_REF] Gács | Lecture notes on descriptional complexity and randomness[END_REF] contains a characterization Bernoulli sequences, but it is rather messy. What about Markov measures? Shift-invariant measures?

Sparse sequences

There are several situations closely related to some intuitive understanding of randomness, but not fitting directly into the framework of the question of a randomness of a given outcome ω to a given model (measure P). Our example is here a natural notion of sparsity, introduced in [3], but another example, online tests, will be considered in Section 9.

It is natural to call "p-sparse" a sequence ω, when its 1's come from some p-random sequence ω ′ , but we allow some of its 0's to also come from the 1's of ω ′ . For example, the 1's of ω ′ may be a sequence of miracles, and ω is the sequence of those miracles that have been reported. The tacit hypothesis is, of course, that all reported miracles actually happened. Definition 5.25 (Sparse sequences). Let us introduce a coordinate-wise order between infinite binary sequences (or binary sequences of the same length): we say ω ω ′ if this is true coordinate-wise, that is ω(i) ω ′ (i) for all i: in other words, ω ′ is obtained from ω replacing some 0's with 1s.

Let B p be a Bernoulli measure with some computable p. We say that a binary sequence ω is p-sparse if ω ω ′ for some B p -random sequence ω ′ . (In terms of sets, p-sparse sets are subsets of p-random sets).

We will show that in the definition of sparsity, the existential quantifier can be eliminated, giving a criterion in terms of monotonic tests. Definition 5.26. A real function f on Ω will be called

monotonic if ω ′ ω implies f (ω ′ ) f (ω).
A monotonic lower semicomputable function t : Ω → [0, ∞] is a p-sparsity test if t(ω) dB p 1. A p-sparsity test is universal if it multiplicatively dominates all other sparsity tests for p.

The monotonicity of tests guarantees, informally speaking, that only the presence of some 1s is counted as regularity, not their absence. (Note that earlier we spoke of an entirely different kind of monotonicity, while defining extended tests: there we compared the values of a function on a finite word and its extension.) Proposition 5.27. Consider the universal test t(ω, P). The expression

r p (ω) = min ω ′ ω t(ω ′ , B p )
defines a universal p-sparsity test.

Proof. Each p-sparsity test is by definition a test with respect to the measure B p . Using its monotonicity and comparing it with the universal test we obtain that no sparsity test exceeds r p (to within a bounded factor).

In the other direction it must be shown that the minimum in the expression for r p is achieved, and that this function is a p-sparsity test. The lower semicomputability is proved usin that the property ω ω ′ gives an effectively closed set of the effectively compact space Ω × Ω. The monotonicity and the integral inequality follow immediately from the definition.

From this follows the following characterization in terms of tests: Theorem 5.28. A sequence ω is p-sparse (is obtained from a p-random by replacing some 1s with zeros) if and only if the universal sparsity test r p (ω) is finite.

Sparsity is equivalent to randomness with respect to a certain class of measures. To define this class, we introduce the notion of coupling of measures. Definition 5.29. For measures P, Q we say P Q, or that P can be coupled below Q if there exists a probability distribution R on pairs of sequences (ω, ω ′ ) such that (a) The first projection (marginal distribution) is P and the second one is Q.

(b) Measure R is entirely concentrated on pairs (ω, ω ′ ) with ω ω ′ (the probability of this event by the measure R is 1.

The following characterization of coupling is well known: it has many proofs, but all seem to go back to [START_REF] Volker Strassen | The existence of probability measures with given marginals[END_REF] (Theorem 11, p. 436). A proof can be found in [3].

Proposition 5.30. The property P Q is equivalent to the following: for all monotonic basic functions f the following inequality holds:

f (ω) dP f (ω) dQ.
In this characterization, we could have said "all monotonic integrable functions" as well.

Definition 5.31. Let S p be the set of measures that can be coupled below B p .

Proposition 5.32. The set S p of measures is effectively closed (and thus effectively compact).

Proof. For each function f in Proposition 5.30, the condition defines an effectively closed set, and their intersection will also be effectively closed.

Theorem 5.33. The universal p-test r p (ω) is a universal class test for class S p .

Thus, a sequence is p-sparse if and only if it is random with respect to some measure that can be coupled below B p .

The following lemma will be key to the proof.

Lemma 5.34 (Monotonization). Let t : Ω → R be a basic function with t(ω) dQ 1 for all Q ∈ S p . Define the monotonic function t(ω) = max ω ′ ω t(ω ′ ) (the maximum is achieved since t(ω) depends only on finitely many positions of ω). Then t(ω) dB p 1.

Proof. Let function t depend only on the first n coordinates. For each x ∈ {0, 1} n fix x ′ x for which t(x ′ ) reaches the maximum (among all such x ′ ). Besides the distribution B p consider a distribution Q in which the Bernoulli measure of x is tranferred to x ′ (the measures of several x may be transferred to the same x ′ and then be added). We described the behavior of Q on the first n bits; the following bits are chosen independently, and the probability of 1 in each position is equal to p. Note also that for the expected values of the functions t and t only the first n bits count.

By the construction, Q B p (essentially, we described a measure on pairs), therefore t(ω) dQ 1. But this integral is equal to t(ω) dB p .

Let us return to the theorem.

Proof of Theorem 5.33. Every p-sparsity test t is a class test for S p . Indeed, its integral by a measure in the class S p does not exceed its integral by the measure B p , by the monotonicity of the test and the possibility of coupling.

On the other hand, let us show that for every test t for the class S p , there is a a p-sparsity test that is not smaller. Indeed, the test t is the limit of an increasing sequence t n of basic functions. Applying to them the monotonization lemma 5.34, we obtain a sequence of basic functions tn that are everywhere greater or equal to t n and have integrals bounded by 1 with respect to the measure B p . Their limit is the needed p-sparsity test.

Different kinds of randomness

There are several ways to define randomness with respect to an arbitrary (not necessarily computable) measure. We have already defined uniform randomness. Here are some other ways.

Oracles We can use the Martin-Löf definition (or its average-bounded version) with oracles. We would call a sequence ω random with respect to P, if there exists an oracle A that makes P computable such that ω is ML-random with respect to P with oracle A. (We say "there exists an oracle that makes P computable" but not "for all oracles that make P computable": indeed, some powerful oracle can always make ω computable and therefore non-random, unless ω is an atom of P.) As Adam Day and Joseph Miller have shown, this definition turns out to be equivalent to uniform randomness. The proof of this equivalence needs some preparation.

First let us look into why is it not possible to take for oracle the measure itself (as was done for the Bernoulli measures, where for oracle we chose a binary expansion of the number p). Well, the choice of such a representation is not unique (0.01111 • • • = 0.10000 . . . ). When all we have is a single number p then this is not important, as the non-uniqueness arises only for rational p, and in this case both representations are computable. But for measures this is not so: a measure is represented by a countable number of reals (say, the probabilities of individual words, or the conditional probabilities), and the arbitrariness in the choice of representation is not reduced to a finite number of variants. Definition 5.35. Fix some representation of measures by infinite binary sequences, that is a computable (and therefore continuous) mapping π → R π of Ω onto the space of measures. For example, we may split the binary sequence π into countably many parts and use these parts as binary representations of the probability that the sequence continues with 1 after a certain prefix.

Define the notion of an r-test (representation-test, test of randomness relative to a given representation of the measure) as a lower semicomputable function t(ω, π) with t(ω, π)R π (dω) 1 for all π.

This notion of r-test depends on the representation method chosen; there are no intuitive reasons to choose one specific representation and declare it to be "natural", but any representation is good for the argument below and we assume some representation fixed. The following statements can be proven just as similar statements before: (a) Every lower semicomputable function t(ω, π) can be trimmed to make it not greater than twice an r-test (not changing it for those π where it already was a r-test).

(b) There exists an universal (maximal to within a bounded factor) r-test t(ω, π).

For a fixed π, the function t(•, π) is universal among the π-computable average-bounded tests with respect to the measure R π . Indeed, it is such a test; on the other hand, any such test can be lower semicomputed by the oracle machine. This machine is applicable to any oracle (though may not give a test), giving a lower semicomputable function t ′ (ω, π) that is equal to the starting test for the given π. It remains to apply property (a).

As a consequence of this simple reasoning we obtain that the quantity t(ω, π) is finite if and only if the sequence ω is random relative to the oracle π, with respect to measure R π .

Theorem 5.36 (Day-Miller). A sequence ω is uniformly random with respect to measure P if and only if there is an oracle computing P that makes ω random (in the original Martin-Löf sense). More precisely,

t(ω, P) * = inf R π =P t(ω, π). (9)
Proof. Let us prove the equality shown in the theorem. Note that if t is a uniform test, then t(ω, R π ) as a function of ω and π is an r-test, and is therefore dominated by the universal r-test. The other direction is somewhat more difficult. We have to show that the function on the right-hand side is lower semicomputable as a function of the sequence ω and the measure P. (The integral condition is obtained easily afterwards, as the measure P has at least one representation π.) This can be proved using the effective compactness of the set of those pairs (P, π) with P = R π . In the general form (for constructive metric spaces) this statement forms the content of Lemma 7.21.

It remains to explain the connection between the given equality and randomness relative to an oracle. If t(ω, P) is finite, then by the proved equality a π exists with R π = P and finite t(ω, π). As we have seen, this in turn means that ω is random with respect to the measure P, with an oracle π that makes P computable. Conversely, if t(ω, P) is infinite, and some oracle A makes P computable, then the function t(•, P) becomes A-lower semicomputable, and its integral by measure P does not exceed 1, hence the sequence ω will not be random relative to oracle A and with respect to measure P.

Blind (oracle-free) tests

We can define the notion of an effectively null set as before, even if the measure is not computable. The maximal effectively null set may not exist. For example, if measure P may be concentrated on some noncomputable sequence π, then all intervals not containing π will be effective null sets, and their union (the complement of the singleton {π}) will not be, otherwise π would be computable.

However, we still can define random sequence as a sequence that does not belong to any effectively null set. Kjos-Hanssen suggested the name "Hippocratic randomness" for this definition (referring to a certain legend about the doctor Hippocrates), but we prefer the more neutral name "blind randomness". Definition 5.37 (Blind tests). A lower semicomputable function t(ω) with integral bounded by 1 will be called a blind, or oracle-free, test for measure P. A sequence ω is blindly random iff t(ω) < ∞ for all blind tests. As seen, there may not exist a maximal blind test. This oracle-free notion of randomness can be characterized in the terms introduced earlier: Theorem 5.38. Sequence ω is blindly random with respect to measure P if and only if ω is random with respect to any effectively compact class of measures that contains P.

Proof. Assume first that ω is not random with respect to some effectively compact class of measures that contains P. Then the universal test with respect to this class is a blind test that shows that ω is not blindly random with respect to P. Now assume that there exists some blind test t for measure P with t(ω) = ∞. Then just consider the class C of measures Q with t(ω) dQ 1. This class is effectively closed, (and thus effectively compact). Indeed, t be the supremum of the computable sequence of basic functions t n . The class of measures Q with t n (ω) dQ > 1 is effectively open, uniformly in n, and C is the complement of the union of these sets.

It is easy to see from the definition (or from the last theorem) that uniform randomness implies blind randomness (either directly or using the last theorem). The reverse statement is not true: Theorem 5.39. There exists a sequence ω and measure P such that ω is blindly random with respect to P but not uniformly random.

Proof. Indeed, oblivous randomness does not change if we change the measure slightly (up to O(1)-factor). On the other hand, the changed measure may have much more oracle power that makes a sequence non-random. For example, we may start with uniform Bernoulli random measure B 1/2 (coin tosses with probabilities 1/2, 1/2, 1/2, . . . and fix some random sequence ω = ω(1)ω(2) . . . . Then consider a (slightly) different measure B ′ with probabilities 1/2 + ω(1)ε 1 , 1/2 + ω(2)ε 2 , . . . where ε 1 , ε 2 , . . . are so small and converge to zero so fast that they do not change the measure more than by O(1)-factor while being all positive. Then B ′ encodes ω, which makes it easy to construct a uniform test t with t(ω, B ′ ) = ∞.

However, there are some special cases (including Bernoulli measures) where uniform and blind randomness are equivalent. In order to formulate the sufficient conditions for such a coincidence, let us start with some definitions. Definition 5.40 (Effective orthogonality). For a probability measure P, let Randoms(P) denote the set of sequences uniformly random with respect to P. A class of measures is called effectively orthogonal if Randoms(P) ∩ Randoms(Q) = / 0 for any two different measures in it.

Theorem 5.41. Let C be an effectively compact, effectively orthogonal class of measures. Then for every measure P in C the uniform randomness with respect to P is equivalent to blind randomness with respect to P.

The statement looks strange: we claim something about randomness with respect to measure P, but the condition of the claim is that P can be included into a class of measures with some properties. (It would be natural to have a more direct requirement for P instead.) The theorem implies that the measures of Theorem 5.39 do not belong to any such class.

Proof. We have noted already that in one direction the statement is obviously true. Let us prove the converse. Assume that sequence ω is blindly random with respect to measure P. By Theorem 5.38, it is random with respect to the class C . So, ω is uniformly random with respect to some measure P ′ from the class C . It remains to show P = P ′ .

Imagine that this is not the case. Then we can construct an effectively compact class of measures C ′ that contains P but not P ′ . Indeed, since P and P ′ are different, they assign different measures to some finite string, and this fact can be used, in form of a closed condition separating P from P ′ , to construct C ′ . Consider now the effectively compact class C ∩ C ′ . It contains P, and therefore ω will be random with respect to this class. Hence the class contains some measure P ′′ with respect to which ω is uniformly random. But P ′ = P ′′ (one measure is in C ′ , the other one is not), so we get a contradiction with the assumption with the effective orthogonality of the class C .

Remark 5.42. The proved theorem is applicable in particular to the class of Bernoulli measures. It is tempting to think that there is a simpler proof, at least for this case: if ω is random with respect to p we can compute p from ω as the limit of relative frequency, and no additional oracle is needed. This is not so: though p is determined by ω, it does not even depend continuously on ω. Indeed, no initial segment of the sequence guarantees that its limiting frequency is in some given interval. However, we can apply an analogous reasoning to those sequences ω with the randomness deficiency bounded by some constant. (See [START_REF] Hoyrup | An application of Martin-Löf randomness to effective probability[END_REF] which introduces the notion of layerwise computability.) In particular, it can be shown that if ω is random with respect to the measure B p then p is computable with oracle ω.

Neutral measure

The following theorem, first published in [START_REF] Levin | Uniform tests of randomness[END_REF] and then again in [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF], points to a curious property of uniform randomness which distinguishes it from randomness using an oracle. Definition 6.1. A measure is called neutral if every sequence is uniformly random with respect to it. Theorem 6.2. There exists a neutral measure; moreover, there is a measure N with t(ω, N) 1 for all sequences ω.

Note that a neutral measure cannot be computable. Indeed, for a computable measure there exists a computable sequence that is not an atom (adding bits sequentially, we choose the next bit in such a way that its conditional probability is at most 2/3). Such a sequence cannot be random with respect to N. For the same reason a neutral measure cannot be equivalent to an oracle (for a neutral measure N one cannot find an oracle A that make it computable and at the same time can be uniformly reconstructed from every approximation of N). Indeed, in this case uniform randomness (as we have shown) is equivalent to randomness with respect to N with oracle A, and the same argument works.

A neutral measure cannot be lower or upper semicomputable either, but this statement does not seem interesting, since here a semicomputable measure over Ω is also computable. Some more meaningful (and less trivial) versions of this fact are proved in [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF].

Proof. Consider the universal test t(ω, P). We claim that there exists a measure N with t(ω, N) 1 for every ω. In other terms, for every ω we have a condition on N saying that t(ω, N) 1 and we need to prove that these conditions (there is continuum of them) have non-empty intersection. Each of these condition is a closed set in a compact space (recall that t is lower semicontinuous), so it is enough to show that finite intersections are non-empty.

So let ω 1 , . . . , ω k be k sequences. We want to prove that there exists a measure N such that t(ω i , N) 1 for every i. This measure will be a convex combination of measures concentrated on ω 1 , . . . , ω k . So we need to prove that k closed subsets of a k-vertex simplex (corresponding to k inequalities) have a common point. It is a direct consequence of the following classical topology result formulated in Lemma 6.3 below (which is used in the standard proof of Brouwer's fixpoint theorem).

To show that the lemma gives us what we want, consider any point of some face. For example, let X be a measure that is a mixture of, say, ω 1 , ω 5 and ω 7 . We need to show that X belongs to A 1 ∪ A 5 ∪ A 7 : in our terms, that one of the numbers t(ω 1 , X), t(ω 5 , X) and t(ω 7 , X) does not exceed 1. It is easy since we know t(ω, X) dX(ω) 1 (by the definition of the test), and this integral is a convex combination of the above three numbers with some coefficients (the weights of ω 1 , ω 5 and ω 7 in X. Lemma 6.3. Let a simplex with vertices 1, . . . , n be covered by closed sets A 1 , . . . , A k in such a way that vertex i belongs to A i (for every i), edge i-j is covered by A i ∪ A j , and so on (formally, face (i 1 , . . . , i s ) of the simplex is a subset of A i 1 ∪ . . . ∪ A i s ; in particular, the union

A 1 ∪ • • • ∪ A k is the entire simplex). Then the intersection A 1 ∩ • • • ∩ A k is not empty.
For completeness, let us reproduce the standard proof of this lemma.

Proof. Consider a disjoint division T of the simplex into smaller n-dimensional simplices (in such a way that every vertex in the division is a vertex of every simplex containing it). Let S be the set of vertices of T . A Sperner-labeling is a covering of S by sets A 1 , . . . , A k such that the points of S belonging to each lower-dimensional simplex formed by some vertices

i 1 < i 2 < • • • < i r k are covered by A i 1 ∪ • • • ∪ A i r . (A point
gets label i if it belongs to A i .) Sperner's famous combinatorial lemma (see for example the Wikipedia) implies that in any Sperner labeling, there is a simplex whose vertices are labeled with all k colors.

To apply the Sperner's lemma, note that our closed sets A i satisfy the rules of Sperner coloring. Sperner's lemma guarantees the existence of a simplex that has all possible labels on its vertices. In this way we can get arbitrarily small simplices with this property; compactness then shows that all A i have a common point.

Randomness in a metric space

Most of the theory presented above for infinite binary sequences generalizes to infinite sequences of natural numbers. Much of it generalizes even further, to an arbitrary metric space. In what follows below we not only generalize; some of the results are new also for the binary sequence case.

Constructive metric spaces

We rely on the definition of a constructive metric space, and the space of measures on it, as defined in [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF] and [START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF] (the lecture notes [START_REF] Gács | Lecture notes on descriptional complexity and randomness[END_REF] are also recommended). Definition 7.1. A constructive metric space is a tuple X = (X, d, D, α) where (X, d) is a complete separable metric space, with a countable dense subset D and an enumeration α of D. It is assumed that the real function d(α(v), α(w)) is computable. Open balls with center in D and rational radius are called ideal balls, or basic open sets, or basic balls. The (countable) set of basic balls will also be called the canonical basis in the topology of the metric space.

An infinite sequence s 1 , s 2 , . . . with s i ∈ D is called a strong Cauchy sequence if for all m < n we have d(s m , s n ) 2 -m . Since the space is complete, such a sequence always has a (unique) limit, which we will say is represented by the sequence.

We will generally use the notational convention of this definition: if there is a constructive metric space with an underlying set X then the we will use X (boldface) to denote the whole structure (X, d, D, α). But frequently, we just use X when the structure is automatically understood. 3. The real line R with the distance d(x, y) = |x -y| is a constructive metric space, and so is R + = [0, ∞). We can add the element ∞ to get R + = [0, ∞]. This is not a metric space now, but is still equipped with a natural constructive topology (see Remark 7.4 below). It could be equipped with a new metric in a way that would not change this constructive topology.

4. If X, Y are constructive metric spaces, then we can define a constructive metric space Z = X × Y with one of its natural metrics, for example the sum of distances in both coordinates. In case when

X = Y = R, this is called the L 1 metric. Let D Z be the product = D X × D Y .
5. Let X be a finite or countable (enumerated) alphabet, with a fixed numbering, and let X N be the set of infinite sequences x = (x(1), x(2), . . . ) with distance function d N (x, y) = 2 -n where n is the first i with x(i) = y(i). This space generalizes the binary Cantor space of Definition 2.1, to the case mentioned in Remark 5.15. The balls in it are cylinder sets: for a given finite sequence z, we take all continuations of z.

Remark 7.3. Each point x of a constructive metric space X can be viewed as an "approximation mass problem": the set of total functions that for any given rational ε > 0 produce a ε-approximation to x by a point of the canonical dense set D. This is a mass problem in the sense of [20]. One can also note that this mass problem is Medvedev equivalent to the enumeration problem: enumerate all basic balls that contain x.

Remark 7.4. A constructive metric space is special case of a more general concept, which is often useful: a constructive topological space.

A constructive topological space X = (X, τ, ν) is a topological space over a set X with a basis τ effectively enumerated (not necessarily without repetitions) as a list τ = {ν(1), ν(2), . . .}.

For every nonempty subset Z of the space X, we can equip Z with a constructive topology: we intersect all basic sets with Z, without changing their numbering. On the other hand, not every subset of a constructive metric space naturally has the structure of a constructive metric space (the everywhere dense set D is not inherited).

But instead of introducing constructive topological spaces formally, we prefer not to burden the present paper with more abstractions, and will speak about some concepts like effective open sets and continuous functions, as defined on an arbitrary subset Z of the constructive metric space X.

set V such that U ∩ A = V ∩ A.
Note that in the last definition, U is not necessarily part of A, but only its intersection with A matters.

Computable functions can be defined in terms of effectively open sets.

: X → [-∞, ∞] is lower semicontinuous if the sets { x : f (x) > r }
are open, for every rational number r (from here it follows that they are open for all r, not only rational).

It is lower semicomputable if these sets are effectively open, uniformly in the rational number r. It is upper semicomputable iff is lower semicomputable.

A partial function f : X → Y defined at least on a set A is lower semicomputable on A if the sets { x : f (x) > r } are effectively open in A, uniformly for every rational number r.

It is easy to check that a real function over a constructive metric space is computable if and only if it is lower and upper semicomputable. As before, one can define semicomputability equivalently with the help of basic functions.

Let us introduce an everywhere dense set of simple functions.

Definition 7.11 (Hat functions, basic functions). We define an enumerated list of basic functions E = {e 1 , e 2 , . . . } in the constructive metric space X = (X, d, D, α) as follows. For each point u ∈ D and positive rational numbers r, ε let us define the hat function g u,r,ε : its value in point x is determined by the distance of x to u and is equal to 1, if this distance is at most r, equal to zero, if the distance is not less than r + ε, and varies linearly as the distance runs through the segment [r, r + ε]: see Figure 1. Let E be the smallest set of functions containing all hat functions that is closed under min, max and rational linear combinations.

Proposition 7.12. A function f : X → [0, ∞] defined on a constructive metric space is lower semicomputable if and only if it is the limit of a computable increasing sequence of basic functions.

Note that the above characterization holds also for lower semicontinous functions, if we just omit the requirement that the sequence g n be computable. Definition 7.13. We can introduce the notion of lower semicomputability from z 0 , or z 0 -lower semicomputability, similarly to the z 0 -computability of Definition 7.6, as lower semicomputability of a function defined on the set X × {z 0 }.

Sometimes two metrics on a space are equivalent from the point of view of computability questions. Let us formalize this notion. Definition 7.14 (Uniform continuity, equivalence). Let X, Y be two metric spaces, and f : X → Y a function. We say that f is uniformly continuous if for each ε > 0 there is a δ > 0 such that d

X (x, y) δ implies d Y ( f (x), f (y)) ε.
If X, Y are constructive metric spaces and function f is computable, we will call it effectively uniformly continuous if δ can be computed from ǫ effectively.

Two metrics d 1 , d 2 over the same space are (effectively) equivalent if the identity map is (effectively) continuous in both directions.

For example, the Euclidean metric and the L 1 metric introduced in Example 7.2.4 are equivalent in the space R 2 .

Effective compactness was introduced in Definition 5.4: this generalizes immediately to arbitrary metric spaces. A weaker notion, local compactness, also has an effective version. 2. The segment [0, 1] is effectively compact. The line R is effectively locally compact.

3. If the alphabet X is finite then the space X N of infinite sequences is effectively compact. Otherwise it is not even locally compact.

4. Let α ∈ [0, 1] be a lower semicomputable real number that is not computable.

(It is known that there are such numbers, for example ∑ x∈N 2 -Kp(x) .) The lower semicomputability of α allows to enumerate the rationals less than α and allows for the segment [0, α] to inherit the constructive metric (and topology) from the real line. This space is compact, but not effectively so.

The following is a useful characerization of effective compactness. Proof. Assume that for all ε we can show a finite covering S ε of the set C by balls of radius ε. Along with such a covering, we can enumerate all coverings with guaranteedly large balls (this means that for all balls B(x, ε) from the covering S ε there is a ball B(y, σ) from the new covering with σ > ε + d(x, y)). The compactness of C guarantees that while S ε runs through all ε-coverings of C, this way all coverings of C will be enumerated. (Indeed, if there is some covering S ′ not falling into the enumeration, then for all ε there is a ball of the covering S ε not guaranteedly contained in any ball of S ′ . Applying compactness and taking a limit point of the centers of these non-contained balls, we obtain contradiction.)

The remaining statements are proved quite easily.

The following statement generalizes Proposition 5.5, with the same proof.

Proposition 7.18. Every effectively closed subset E of an effectively compact set C is also effectively compact.

As earlier, the converse also holds: every effectively compact subset of a constructive metric space is effectively closed. Indeed, we can consider all possible coverings of this set by basic balls, and also outside balls that manifestly (by the relation of the distances of their centerse and their radiuses) are disjoint from the balls of the covering. The union of all these outside balls provide the complement of our effectively compact set.

It is known that a continuous function maps compact sets into compact ones. This statement also has a constructive counterpart, also provable by a standard argument: Proposition 7.19. Let C be an effectively compact subset of a constructive metric space X, and f a computable function from X into another constructive metric space Y. Then f (C) is effectively compact.

The statement that a lower semicontinuous function on a compact set reaches its minimum has also a computable analog (we provide a parametrized variant): is lower semicomputable from below (and the inf can be replaced with min due to compactness).

Proposition 7.20 (Parametrized minimum). Let Y, Z be constructive metric spaces, let f : Y × Z → [0, ∞]
Instead of effective compactness of C, it is sufficient to require that its projection C Y = { y : ∃z (y, z) ∈ C } is effectively closed and covered by an enumerated sequence of basic balls B k such that B k × Z ∩C is effectively compact, uniformly in k.

The weaker condition formulated at the end holds for example if Y is effectively locally compact and Z is effectively compact.

Proof. For start, we reproduce the classical proof of lower semicontinuity. One needs to check that the set { y : r < g(y) } is open for all r. This set can be represented in the form of a union, noting that the condition r < g(y) is equivalent to the condition

(∃r ′ > r)∀z [(y, z) ∈ C ⇒ f (y, z) > r ′ ],
and it is sufficient to check the openness of the set

U = { y : ∀z [(y, z) ∈ C ⇒ f (y, z) > r ′ ] }. Now, U = (Y \C Y ) ∪ k (B k ∩ U). Since Y \C Y is assumed to be open, it is suffi- cient to show that each B k ∩U is open. Let F k = B k ×Z, then by the assumptions, F k ∩C is compact. The condition f (y, z) > r ′ by the assumption defines a certain open set V of pairs, hence F k ∩ C \ V is closed,
and as a subset of a compact set, compact. It follows that its projection { y ∈ B k : ∃z (y, z) ∈ F k ∩ C \ V }, as a continuous image of a compact set, is also compact, and so closed. Its complement in B k , which is B k ∩ U, is then open. Now this argument must be translated to an effective language. First of all note that it is sufficient to consider rational r and r ′ . Then the set V is effectively open, the set F k ∩ C \ V is effectively closed, and as a subset of an effectively compact set, also effectively compact. Its projection, as a computable image of an effectively compact set, is also effectively compact, and as such, effectively closed. The complement of the projection is then effectively open.

The following lemma is an application: Lemma 7.21. Let X, Z, Z ′ be metric spaces, where X is locally compact and Z is compact. Let f : Z → Z ′ be continuous and surjective, and t : X × Z → [0, ∞] a lower semicontinuous function. Then the function t f : X × Z ′ → [0, ∞] defined by the formula

t f (x, z ′ ) = inf z: f (z)=z ′ t(x, z) is lower semicontinuous.
If X, Z, Z ′ are constructive metric spaces, X is effectively locally compact, Z is effectively compact and f is computable, further t is lower semicomputable, then t f is lower semicomputable.

Proof. We will prove just the effective version. We will apply Proposition 7.20 with Y = X × Z ′ , and

C = X × { ( f (z), z) : z ∈ Z }. Then t f (x, z ′ ) = inf (x,z ′ ,z)∈C t(x, z).
The set Y is effectively locally compact, as the product of an effectively locally compact set and an effectively compact set. The projection of the set C onto Y is the whole set Y, and hence it is closed. Hence the proposition is applicable, according to the remark following it.

Measures over a constructive metric space

On a metric space, the Borel sets are the smallest σ-algebra containing the open sets. We can define measures on Borel sets. These measures have the following regularity property: Proposition 7.22 (Regularity). Let P be a measure over a complete separable metric space. Then every measureable set A can be approximated by large open sets:

P(A) = inf G⊇A P(G), where G is open.
It is possible to introduce a metric over measures: Definition 7.23 (Prokhorov distance). For a set A and point x let us define the distance of x from A as d(x, A) = inf y∈A d(x, y). The ε-neighborhood of a set A is defined as

A ε = { x : d(x, A) < ε }.
The Prokhorov distance ρ(P, Q) of two measures is the greatest lower bound of all those ε for which, for all Borel sets A we have

P(A) Q(A ε ) + ε and Q(A) P(A ε ) + ε.
It is known that ρ(P, Q) is indeed a metric, and it turns the set of probability measures over metric space X into a metric space. There is a number of other metrics for measures that are equivalent, in the sense of Definition 7.14. Definition 7.24 (Space of measures). For a constructive metric space, X, let M = M (X) define the metric space of the set of probability measures over X, with the metric ρ(P, Q). The dense set D M is the set of those probability measures that are concentrated on finitely many points of D X and assign rational values to them. Let α M be a natural enumeration of D M , this turns M into a constructive metric space, too.

A probability measure is called computable when it is a computable element of the space M.

Computability of measures is a particularly simple property for the Cantor space of binary sequences in Definition 2.8 (which is easily shown to be equivalent to the definition given here); it is just as simple for the Baire space of sequences over a countable alphabet.

The analogue of Proposition 4.17 holds again: the integral f (ω, P)P(dω) of a basic function is computable as a function of the measure P, uniformly in the code of the basic function. Here is a closely related result: Proposition 7.25. If f is a bounded, effectively uniformly continuous function then its integral by the measure P is an effectively uniformly continuous function of P.

Proof. It can be assumed without loss of generality that f is nonnegative (add a constant). Let measures P and P ′ be close. Then P ′ (A) P(A ε ) + ε, where A ε denotes the ε-neighborhood of A. Then

f dP ′ f ε dP + ε,
where f ε (x) is the least upper bound of f on the ε-neighborhood of x. (The integral of a nonnegative function g is defined by the measures of the sets G t = { x : g(x) t }; by Fubini's theorem on the change of the order of integration, this measure must be integrated by t as a function of t. Now, if f (x) t then f ε (x) t in the ε-neighborhood of point x.) It remains to apply the effective uniform continuity of f to find out the precision by which the measure must be given in order to obtain a given precision in the integral.

On the other hand, the measure of P(B) of a basic ball B is not necessarily computable, only lower semicomputable. It is shown in [START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF] that this property also characterizes the computability of measures: P is computable if and only if P(B) is lower semicomputable, uniformly in the basic ball B.

It is known that if a complete separable metric space is compact then so is the set of measures with the described metric. The following constructive version is proved by standard means: Proposition 7.26. If a constructive metric space X is effectively compact then its space of probability measures M (X) is also effectively compact.

For the binary Cantor space, this was proved in Proposition 5.5. There, the topology of the space of measures was simply derived from the topology of the space [0, 1] × [0, 1] × • • • . It can be seen that the Prokhorov metric leads to the same topology.

Example 7.27. Another interesting simple metric space is the infinite discrete space, say on the set of natural numbers N. This is not a compact space, and the set of measures, namely the set of all functions P(x) 0 with ∑ x∈N P(x) = 1, is not compact either.

On the other hand, the set of semimeasures (see Definition 2.19) is compact. Indeed, recall that the space

[0, 1]×[0, 1]ו • • , of functions P : N → [0, 1] is com- pact.
Hence also for each n the subset F n of this set of consisting of functions P obeying the restriction P(0)+ P(1)+• • •+ P(n) 1 is compact, as the product of a compact finite-dimensional set { (P(0), P(1), . . . , P(n)) ∈ [0, 1] n : P(0) + • • • + P(n) 1 } and the compact infinite product set { (P(n + 1), P(n + 1), . . . ) : 0 P(x) 1 for x > n }. The intersection of all sets F n is then also compact, and is equal to the set of semimeasures.

Equivalently, we can consider the one-point compactification N of N given in Example 7.2.2. Measures P on this space can be identified with semimeasures over N: we simply set P(∞) = 1 -∑ n<∞ P(n).

Randomness in a metric space

In the Cantor space Ω of infinite binary sequences we defined • randomness with respect to computable measures (in the sense of Martin-Löf); see Definition 2.9;

• uniform randomness with respect to arbitrary measures (when the test is a function of the sequence and the measure), Definition 5.2;

• Randomness with respect to an effectively compact class of measures, Definition

• Blind (oracle-free) randomness in Definition 5.37;

All these notions carry over with minor changes to an arbitrary constructive metric space. In the present section we discuss these generalizations and their properties, and then consider in more detail randomness with respect to an orthogonal class of measures.

For computable measures, a test is defined as a lower semicomputable function on a constructive metric space, whose integral is bounded by 1. Among such tests, there is a maximal one to within a multiplicative constant. As earlier, this is proved with the help of trimming: we list all lower semicomputable functions, forcing them into tests or almost tests, and then add them up with coefficients from a converging series. This is done as before, by considering lower semicomputable functions as monotonic limits of basic ones. It is used that the integral of a basic function by a measure is computable as a function of the measure: see Propositions 7.25 and the discussion preceding it.

The uniform tests introduced in Definition 5.2 generalize immediately to the case of constructive metric spaces. Such a test is a lower semicomputable function of two arguments t(x, P), where x is a point of our metric space, and P is a measure over this space. The integral condition has the same form as earlier:

t(x, P) P(dx) 1.

As earlier, there exists a universal test, and this can be proved by the technique of trimming: Theorem 7.28 (Trimming in metric spaces). Let u(x, P) be a lower semicomputable function whose first argument is a point of a constructive metric space, and the second one is measure over this space. Then there exists a uniform tests t(x, P) satisfying u(x, Q) 2t(x, Q) for all Q such that the function u

Q : x → u(x, Q) is a test by the measure Q, that is u(x, Q) Q(dx) 1.
The proof repeats the reasoning of the proof of Theorem 5.7, while using the fact that for a basic function b(x, P) on the product space the integral b(x, P) P(dx) is a computable (continuous) function of P (which is proved analogously to our above argument on the computability of the integral).

We will denote the universal uniform test again by t(x, P). Strictly speaking, it depends also on the constructive metric space on which it is defined, but in general it is evident, which space is being considered, therefore it is not shown in the notation. Definition 5.11 and Proposition 5.12 extend without difficulty.

Definition 7.29 (Tests for arbitrary measures). Let X = (X, d, D, α) be a constructive metric space. For a measure P ∈ M (X), a P-test of randomness is a function f : X → [0, ∞] lower semicomputable from P with the property f (x) dP 1.

It seems as if a P-test may capture some nonrandomnesses that uniform tests cannot-however, this is not so, since trimming (see Theorem 5.7) generalizes: Theorem 7.30 (Uniformization). Let P be some measure over a constructive metric space X, along with some P-test t P (x). There is a uniform test t ′ (•, •) with t P (x) 2t ′ (x, P).

Theorem 5.36 generalizes to the case of constructive metric spaces. Let us mention one of the facts that generalize to uniform tests. Proposition 7.31 (Kurtz tests, uniformly). Let S be an effectively open subset of the space X × M (X). If the set S P = { x : (x, P) ∈ S }, has P-measure 1 for some measure P, then the set S (P) contains all uniformly P-random points.

Proof. The indicator function 1 S (x, P) of the set S , that is equal to unity on S and to zero outside, is lower semicomputable. According to Proposition 7.12, it can be written as the limit of a computable increasing sequence of basic functions 0 g n (x, P) 1. The sequence G n : P → g n (x, P) dP is an increasing sequence of functions computable uniformly in n. The motonone convergence theorem implies G n (P) → 1 for all P ∈ C . Let us define for each measure P the numbers n K (P) as the minimal values of n for which G n (P) > 1 -2 k . These numbers are upper semicomputable as functions of P (in a natural sense; for measures P with P(S P ) < 1, some of these n k (P) are infinite). Correspondingly, the functions 1g n k (P) (x, P), as functions of x and P (define such a function to be zero for infinite n k (P), independently of x) are lower semicomputable, uniformly in k. Then t(x, P) = ∑ k>0 (1g n k (P) (x, P)) is a uniform test, since at a given P, if its kth addend is zero if n k (P) is infinite, and is not greater than 2 -k for finite n k (P).

The conditions of the theorem talk about a measures P with P(S P ) = 1. Then all numbers n k (P) are finite. Consider an x outside S P : then g n k (P) (x, P) = 0 by definition. Therefore all addends of the test sum are equal to unity, thus x is is not P-random point. Consequently, S P includes all uniformly P-random points.

Apriori probability, with an oracle

In Section 5.2 we defined apriori probability with a condition whose role was played by a measure over the Cantor space Ω. Now, having introduced the notion of a constructive metric space, we can note that this definition extends naturally to an arbitrary such space X: we consider nonnegative lower semicomputable functions m : N × X → [0, ∞] for which ∑ i m(i, x) 1, for all x ∈ X.

Among such functions, there is a maximal one to within a multiplicative constant. This is proved by the method of trimming: the lower semicomputable function m(i, x) can be obtained as a sum of a series of basic functions each of which differs form zero only for one i; these basic functions must be multiplied by correcting coefficients that depend on the sum over all i. (In each stage, this sum has only finitely many members.)

We will call the maximal function of this kind apriori probability with condition x, and denote it m(i | x). We consider the first argument a natural number, but this is not essential: it is possible to consider words (or any other discrete constructive objects). As a special case we obtain the definition of apriori probability conditioned on a measure (Section 5.2), and also the standard notions of apriori probability with an oracle (which corresponds to X = Ω, the Cantor space of infinite sequences), and the conditional apriori probability (corresponding to X = N).

In analogy with Martin-Löf's theorem, the apriori probability with a condition is expressible, in an arbitrary effectively compact constructive metric space X by apriori probability with an oracle. Proposition 7.32. Let F : Ω → X be a computable map whose image is the whole space X. Then

m(i | x) * = min π:F(π)=x m(i | π).
Proof. We reason as in the proof of Theorem 5.36. The function (i, π) → m(i | F(π)) is lower semicomputable on N × Ω, hence the * <-inequality. In order to obtain the reverse inequality, we use Lemma 7.21 and note that the function on the right-hand side is correctly defined (the minimum is achieved) and is lower semicomputable.

Note that the apriori probability with an oracle on the right-hand side of Proposition 7.32 is expressible by prefix complexity with an oracle. For the case of prefix complexity with condition in metric spaces it is not clear, how to define prefix complexity with such a condition (one can speak of functions whose graph is enumerable with respect to x, but it is not clear how to build a universal one). But one can define formally Kp(i | x) as max π:F(π)=x Kp(i | π), and then Kp(i | x) + =log m(i | x), but it is questionable whether this can be considered a satisfactory definition of prefix complexity (say, the usual arguments using the self-delimiting property of programs are not applicable at such a definition). It is more honest to simply speak of the logarithm of apriori probability. Many results still stay true: for example the formula Kp(i, j | x) + < Kp(i | x) + Kp( j | x) can be proved, without introducing self-delimiting programs, just reasoning about probabilities.

Remark 7.33. Analogously, it is possible to supply points in constructive metric spaces as conditions in some of our other definitions. For example, we can consider uniform tests over the Cantor space Ω of infinite binary sequences, with condition in an arbitrary constructive metric space X: these will be lower semicomputable functions t(ω, P, x) with t(ω, P, x) P(dω) 1 for all P, x. It is also possible to fix a computable measure P, say the uniform one, and define tests with respect to this measure with conditions in X.

Classes of orthogonal measures

The definition of a class test for an effectively compact class of measures, as well as Theorem 5.23 about the expression of a class test, generalizes, with the same proof.

The set of Bernoulli measures has an important property shared by many classes considered in practice: namely that a random sequence determines the measure to which it belongs. A consequence of this was spelled out in Theorem 5.41. This section explores the topic in a more general setting.

There are some examples naturally generalizing the Bernoulli case: finite or infinite ergodic Markov chains, and ergodic stationary processes. Below, we will dwell a little more on the latter, since it brings up a rich complex of new questions.

We will consider orthogonal classes in the general setting of metric spaces: from now on, our measureable space is the one obtained from a constructive metric space X = (X, d, D, α). The following classical concept is analogous to effective orthogonality, introduced in Definition 5.40. Definition 8.1 (Orthogonal measures). Let P, Q be two measures over a measureable space (X, A ), that is a space X with a σ-algebra A of measureable sets on it. We say that they are orthogonal if the space can be partitioned into measureable sets U, V with the property P(V) = Q(U) = 0.

Let C be a class of measures. We say that C is orthogonal if there is a measureable function ϕ : X → C with the property P(ϕ -1 (P)) = 1.

Note that the space M (X), as a metric space, also allows the definition of Borel sets, and it is in this sense that we can talk about f being measureable.

Examples 8.2. 1. In an orthogonal class, any two (different) measures P and Q are orthogonal. Indeed, the sets {P} and {Q} are Borel (since closed), hence their preimages are measureable (and obviously disjoint). The converse statement is false: A class C of mutually orthogonal probability measures is not necessarily orthogonal, even if the class is effectively compact. For example, let λ be the uniform distribution over the interval [0, 1], and let for each x ∈ [0, 1] the probability measure δ x be concentrated on x. Then the class {λ} ∪ { δ x : x ∈ [0, 1] } is effectively compact, and its elements are mutually orthogonal. But the whole class is not orthogonal: the orthogonality condition requires φ(x) = δ x , but then φ -1 (λ) will be empty.

2. Let P, Q be two probability measures. Of course, if Randoms(P) and Randoms(Q) are disjoint, then P and Q are orthogonal. The converse is not always true: for example it fails if λ, δ x are as above, where x is random with respect to λ.

The following definition introduces the important example of stationary ergodic processes.

Definition 8.3. The Cantor space Ω of infinite binary sequences is equipped with an operation T : ω(1)ω(2)ω(3) . . . → ω(2)ω(3)ω(4) . . . called the shift. A probability distribution P over Ω is stationary if for every Borel subset A of Ω we have P(A) = P(T -1 (A)). It is easy to see that this property is equivalent to requiring P(x) = P(0x) + P(1x) for every binary string x.

A Borel set A ⊆ Ω is called invariant with respect to the shift operation if T (A) ⊆ A. For example the set of all sequences in which the relative frequency converges to 1/2 is an invariant set. A stationary distribution is called ergodic if every invariant Borel set has measure 0 or 1.

Here is a new example of a stationary process (all Bernoulli measures and stationary Markov chains are also examples).

Example 8.4. Let Z 1 , Z 2 , . . . be a sequence of independent, identically distributed random variables taking values 0, 1 with probabilities 0.9 an 0.1 respectively. Let X 0 , X 1 , X 2 , . . . be defined as follows: X 0 takes values 0, 1, 2 with equal probabilities, and independently of all Z i , further X n = X 0 + ∑ n i=1 Z i mod 3. Finally, let Y n = 0 if X n = 0 and 1 otherwise. The process Y 0 , Y 1 , . . . is clearly stationary, and can also be proved to be ergodic. As a function of the Markov chain X 0 , X 1 , . . . , it is also called a hidden Markov chain.

The following theorem is a consequence of Birkhoff's pointwise ergodic theorem. For each binary string x let

g x (ω) = 1 xΩ (ω)
be the indicator function of the set xΩ: it is 1 if and only if x is a prefix of ω.

Proposition 8.5. Let P be a stationary process over the Cantor space Ω.

(a) With probability 1, the average

A x,n (ω) = 1 n (g x (ω) + g x (T ω) + • • • + g x (T n-1 ω)) (10)
converges.

(b) If the process is ergodic then the sequence converges to P(x).

(For non-ergodic processes, the limit may depend on ω.) Birkhoff's theorem is more general, talking about more general spaces and measure-preserving transformations T , arbitrary integrable functions in place of g x , and convergence to the expected value in the ergodic case. But the proposition captures its essence (and can also be used in the derivation of the more general versions).

Part (b) of Proposition 8.5 implies that the class C of ergodic measures is an orthogonal class. Indeed, let us call a sequence ω "stable" if for all strings x, the averages A x,n (ω) of ( 10) converge. It is easy to see that in this case, the numbers P(x) determine some probability measure Q ω . Now, let ϕ : Ω → C be a function that assigns to each stable sequence ω the measure Q ω provided Q ω is ergodic. If the sequence is not stable or Q ω is not ergodic, then let ϕ(ω) be some arbitrary fixed ergodic measure. It can be shown that ϕ is a measureable function: here, we use the fact that the set of stable sequences is a Borel set. By part (b) of Proposition 8.5, the relation P(ϕ -1 (P)) = 1 holds for all ergodic measures.

Note that the class of all ergodic measures is not closed, but we did not rely on the closedness of this class in the definition.

Example 8.2.2 shows that two measures can be orthogonal and still have common random sequences. But, for computable measures, as we will show right away, this is not possible.

We called a class of measures P effectively orthogonal in Definition 5.40, if all sets of random sequences Randoms(P) for measures P in the class are disjoint from each other.

Theorem 8.6. Two computable probability measures on a constructive metric space are orthogonal if and only they are effectively orthogonal.

Speaking of the effective orthogonality of two measures, we mean that they have no common (uniform) random sequences. In the effective case, pairwise orthogonality within the class and the orthogonality of the whole class are equivalent by definition.

Proof. We only need to prove one direction. Assume that P, Q are orthogonal, that is there is a measureable set A with P(A) = 1, Q(A) = 0. By Proposition 7.22, these measures are regular, so there is a sequence G n ⊇ A of open sets with Q(G n ) < 2 -n . Then for every n there is also a finite union H n of basic balls with P(H n ) > 1 -2 -n and Q(H n ) < 2 -n ; moreover, there is a computable sequence H n with this property. Let U m = n>m H n . By Proposition 7.31, m U m contains all random points of P. On this other hand, the sets U m form a Martin-Löf test for measure Q, so the intersection contains no random points of Q.

We have shown above that ergodic measures form an orthogonal class. Careful analysis shows that this is also true effectively.

Theorem 8.7. The set of ergodic measures over the Cantor set Ω forms an effectively orthogonal class.

Proof. The paper [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF] (more precisely, an analysis of it that will create uniform tests) shows that (a) Sequences uniformly random with respect to some stationary measure are stable (in the sense that the above indicated limit of averages exists for them).

(b) Uniformly random sequences with respect to an ergodic measure are "typical" in the sense that these averages converge to P(x). To show (a), the paper introduces the function σ(ω, α, β) for rationals 0 < α < β, which is the maximum number of times that A x,n (ω) crosses from below α to above β. This function is lower semicomputable, uniformly in the rationals α, β. Then it shows

(1 + α -1 )(β -α) σ(ω, α, β) dP 1, that is that (1 + α -1 )(β -α)σ(ω, α, β
) is an average-bounded test, implying that for Martin-Löf-random sequences, the average A x,n (ω) crosses from below α to above β only a finite number of times. Now one can combine all these tests, for all strings x and all rational 0 < α < β, into a single test. This test is uniform in P: we did not rely on the computability of P.

To express (b), in view of part (a), it is sufficient, for each x, to prove

lim inf n A x,n (ω) P(x) lim sup n A x,n (ω) (11)
for random ω. Take for example the statement for the lim inf. It is sufficient to show for each k, m that inf n m A x,n (ω) P(x) + 2 -k for a random ω. The set

S x,k,m = { (ω, P) : ∃n m A x,i (ω) < P(x) + 2 -k }
is effectively open, and the Birkhoff theorem implies P(S x,k,m (P)) = 1 for for all ergodic measures P, for the set S x,k,m (P) = { x : (x, P) ∈ S x,k,m }. Proposition 7.31 implies that then for each P, the set S x,k,m (P) contains all P-random points.

Another approach is a proof that just shows (b) for computable ergodic measures (in a relativizable way), without an explicit test, as done in [2]. Then a reference to Theorem 5.16 allows us to conclude the same about uniformly random sequences.

It is convenient to treat orthogonality of a class in terms of separator functions. For this, note that by a measureable real function we mean a Borelmeasureable real function, that is a function with the property that the inverse images of Borel sets are Borel sets. Definition 8.8 (Separator function). Let C be a class of measures over the metric space X. A measureable function s : X × M (X) → [0, ∞], is called a separator function for the class C if for all measures P we have s(x, P) dP 1, further for P, Q ∈ C , P = Q implies that only one of the values s(x, P), s(x, Q) is finite.

In case we have a constructive metric space X, a separator function s(x, P) is called a separator test if it is lower semicomputable in (x, P).

We could have required the integral to be bounded only for measures on the class, since trimming allows the extension of the boundedness property to all measures, just as in the remark after Definition 7.29.

The following observation connects orthogonality with separator functions and also shows that in case of effective orthogonality, each measure can be effectively reconstructed from any of its random elements. The converse of part (a) might not hold: this needs further investigation.

Proof. Let us prove (a). If ϕ(x) is a measureable function assigning measure P ∈ C to each element x ∈ X as required in the definition of orthogonality, then by a general theorem of topological measure theory (see [14]), its graph is measureable. This allows the following definition: for P ∈ C set s(x, P) = 1, further for P ∈ C , set s(x, P) = 1 if ϕ(x) = P, and s(x, P) = ∞ otherwise.

Let us prove now (b). If C is effectively orthogonal then the uniform test t(x, P) is a separator test for the class C . Suppose now that there is a separator test s for the class C , and let P, Q ∈ C , P = Q, x ∈ Randoms(P). Since s is a randomness test, s(x, P) < ∞, which implies s

(x, Q) = ∞, hence x ∈ Randoms(Q).
The following result is less expected: it shows that if the class of measures is effectively compact then the existence of a lower semicontinuous separator function implies the existence of a lower semicomputable one (that is a separator test).

Theorem 8.10. If for an effectively compact class of measures there is a lower semicontinuous separator function s(x, P), then this class is effectively orthogonal.

Proof. Let C be an effectively compact class of measures on a constructive metric space. We need to show that under the conditions of the theorem, for any two distinct measures P 1 , P 2 in C , the sets of random sequences are disjoint: Randoms(P 1 ) ∩ Randoms(P 2 ) = / 0.

Take two disjoint closed basic balls B 1 and B 2 in the constructive metric space M of measures, containing the measures P 1 , P 2 . The classes

C i = C ∩ B i , i = 1,
k = { x : t 1 (x) > 2 k }. Since t 1 is a C 1 - test, then P(S k ) < 2 -k
for all P ∈ C 1 . On the other hand, since for all x one of the two values t 1 (x), t 2 (x) is infinite, P(S k ) = 1 for all P ∈ C 2 . The indicator function 1 S k (x) of the set S k is lower semicontinuous, therefore it can be written as the limit of an increasing sequence (now not necessarily computable!) of basic functions g k,n (x). We conclude as in the proof of Proposition 7.31, that for each P there is an n = n k (P) with g k,n (x) dP > 1 -2 -k for all P ∈ C 2 . The effective compactness of C implies then that there is an n independent of P with the same property. In summary, for each k > 0 a basic function h k is found with

h k dP < 2 -k for all P ∈ C 1 , h k dP > 1 -2 -k for all P ∈ C 2 .
Such a basic function h k can be found effectively from k, by complete enumeration. Now we can construct a lower semicomputble function

t ′ 1 (x) = ∑ k h k (x). It is a test for the class C 1 , while t ′ 2 (x) = ∑ k (1 -h k (x)
) is a test for all P ∈ C 2 for the same reasons. These tests must be finite for elements random for P 1 and P 2 , and this cannot happen simultaneously for both tests.

The meaning of separator tests introduced above introduced notion of can be clarified as follows. Due to effective orthogonality of C , the universal uniform test t(ω, P) allows to separate the sequences into random ones according to different measures of the class C : looking at a sequence ω, random with respect to some measure of this class (=random with respect to the class), we are looking for a P ∈ C for which t(ω, P) is finite. This measure is unique in the class C (by the definition of effective orthogonality).

This separation property, however, can be satisfied also by a non-universal test, and we called such tests separator tests. The non-universal test is less demanding about the idea of randomness, giving it, so to say, a "first approximation": it might accept a sequence as random that will be rejected by a more serious test. (The converse is impossible, since the universal test is maximal.) What matters is only that this preliminary crude triage separates the measures of the class C , that is that no sequence should appear "random" even "in first approximation", with respect to two measures at the same time.

For brevity, just for the purposes of the present paper, we will call "typicality" this "randomness in first approximation": Definition 8.11. Given a separator test s(x, P) we call an element x typical for P ∈ C (with respect to the test s) if s(x, P) < ∞.

A typical element determines uniquely the measure P for which it is typical. For an example, consider the class of B of Bernoulli measures. For a test in "first approximation", we may recall von Mises, who called the first property of a random sequence ("Kollektiv" in his words) the stability of its relative frequencies. The stability of relative frequencies (strong law of large numbers in today's terminology) means S n (ω)/n → p. Here S n (ω) is the number of ones in the initial segment of length n of the sequence ω, and p is the parameter of the Bernoulli measure B p .

There are several requirements close to this in this spirit: (1) S n (ω)/n → p with a certain convergence speed.

(2) S n (ω)/n → p.

(3) For the case when C is the class of all ergodic stationary measures over the Cantor space Ω, convert the proof of Theorem 8.7 into a test, implying A x,n (ω) → P(x) for all x. Among these requirements, the one that seems most natural to a mathematician, namely (2), is not expressible in a semicomputable way. Requirement (1) has many possible formulations, depending on the convergence speed: we will show an example below.

Requirement (3) is significantly more complicated to understand, but is still much simpler than a universal test. It does not imply a computable convergence speed directly; indeed, as Vyugin showed in [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF], a computable convergence speed does not exist for the case of computable non-ergodic measures. But later works, starting with [START_REF] Avigad | Local stability of ergodic averages[END_REF], have shown that the the convergence for ergodic measures has a speed computable from P.

Here is an example of a test expressing requirement [START_REF] Avigad | Local stability of ergodic averages[END_REF]. (For simplicity, we obtain the convergence of relative frequencies not on all segments, only on lengths that are powers of two. With more care, one could obtain similar bounds on all initial segments.) By Chebyshev's inequality

B p ({ x ∈ {0, 1} n : | ∑ i x(i) -np| λn 1/2 (p(1 -p)) 1/2 }) λ -2 . Since p(1 -p) 1/4, this implies B p ({ x ∈ {0, 1} n : | ∑ i x(i) -np > λn 1/2 /2 }) < λ -2 .
Setting λ = n 0.1 and ignoring the factor 1/2 gives

B p ({ x ∈ {0, 1} n : | ∑ i x(i) -np| > n 0.6 }) < n -0.2 . Setting n = 2 k : B p ({ x ∈ {0, 1} 2 k : | ∑ i x(i) -2 k p| > 2 0.6k }) < 2 -0.2k . (12)
Now, for a sequence ω in B N , and for p ∈ [0, 1] let

g(ω, B p ) = sup{ k : | 2 k ∑ i=1 ω(k) -2 k p| > 2 0.6k }. Then g(ω, B p ) B p (dω) ∑ k k • 2 -0.2k = c < ∞.
Dividing by c, we obtain a test. This is a separator test, since g(ω, B p ) < ∞ implies that 2 -k S 2 k (ω) converges to p, and this cannot happen for two different p. Theorem 5.41 generalizes, with essentially the same proof (using basic balls instead of initial sequences): it says that in an effectively compact, effectively orthogonal class of measures, blind randomness is the same as uniform Martin-Löf randomness. This raises the question whether every ergodic measure belongs to some effectively compact class. The answer is negative: Theorem 8.12. Consider stationary measures over Ω (with the shift transformation). Among these, there are some ergodic measures that do not belong to any effectively compact class of ergodic measures.

Before proving the theorem, let us prove some preparatory statements. Proposition 8.13. Both the ergodic measures and the nonergodic measures are dense in the set of stationary measures M (Ω) over Ω.

Proof. First we will show how to approximate an arbitrary stationary measure P by ergodic measures. Without loss of generality assume that all probabilities P(x) for finite strings x are positive. (If not, then we can mix in a little of the uniform measure.) For a fixed n, consider the values P(x) on strings x of length at most n. There is a process that reproduces these probabilities and that is isomorphic to an ergodic Markov process on {0, 1} n-1 . In this process, for an arbitrary x ∈ {0, 1} n-2 , b, b ′ ∈ {0, 1} the transition probability from bx to xb ′ is P(bxb ′ )/P(bx). Since both transition probabilities are positive, this Markov process is ergodic. Now we show how to approximate an arbitrary ergodic measure by nonergodic measures. Let P be ergodic. Let us fix some n > 0 and ε > 0. By the pointwise ergodic theorem, there is a sequence in which the limiting frequencies of all words converge to the measure (almost all sequences-with respect to this measure-are such). Taking a long piece of this sequence and repeating it leads to a periodic sequence in which the frequencies of words of length not exceeding n differ from the measure P by at most ε (for any given n and ε > 0). (The repetition forms new words on the boundaries, but at a large length, this effect is negligible.) Consider now the measure concentrated on the shifts of this sequence, assigning the same weight to each of them (their number is equal to the minimum period). This measure is not ergodic, but is close to P.

Proposition 8.14. The set of ergodic measures is a G δ set in the metric space of all stationary measures over Ω.

Proof. We can restrict attention to the (closed) set of stationary measures. Let P be a stationary probability measure over Ω. Consider the function A x,n over Ω, defining A x,n (ω) to be equal to the average number of occurrences of the word x in the n first possible positions of ω. By the ergodic theorem, the sequence of functions A x,1 , A x,2 , . . . converges in the L 1 sense. Moreover, the stationary measure P is ergodic if and only if the limit of this convergence is the constant function with value P(x).

Since the limit exists for all stationary measures, it is sufficient to check that the constant P(x) is a limit point. For each x, N and each rational ε the set S x,N,ε of those P for which there is an n N with

|A x,n (ω) -P(x)|P(dω) < ε
is open, and set of ergodic stationary measures is the intersection of these sets for all x, N, ε.

Proof of Theorem 8.12. The union of all effectively compact classes of ergodic measures is F σ . Suppose that it is equal to the set of all ergodic measures.

Then the set of nonergodic measures is a G δ set which is also dense by Proposition 8.13.

As shown in Propositions 8.13 and 8.14, the set of ergodic measures is a dense G δ set. But by the Baire category theorem, two dense G δ sets cannot have an empty intersection. This contradiction proves the theorem. On the other hand, let us show that if t C (x) and s(x, P) are finite, then t(x, P) does not exceed the greater one of them (to within a multiplicative constant). The finiteness of the first test guarantees that min Q∈C t(x, Q) is finite: this minimum is equal to t C (x) to within a constant factor. If this minimum was achieved on some measure Q = P, then both values s(x, Q) and s(x, P) would be finite, contradicting to the definition of a separator. (Note that we proved a statement slightly stronger than promised: in place of "greater of the two", one can write "the first of the two, if the second one is finite".)

The above theorem separates the randomness test into two parts (points at two possible causes of non-randomness). First, we must convince ourselves that x is random with respect to the class C . For example in the case of a measure B p , in the class B of Bernoulli measures, we must first be convinced that t B (ω) is finite. This encompasses all the irregularity criteria. If the independence of the sequence is taken for granted, we may assume that the class test is satisfied.

After this, we know that our sequence is Bernoulli, and some kind of simple test of the type of the law of large numbers is sufficient to find out, by just which Bernoulli measure is it random: B p or some other one. This second part, typicality testing, is analogous to parameter testing in statistics.

Separation is the only requirement of the separator test: its numerical value is irrelevant. For example in the Bernoulli test case, no matter how crude the convergence criterion expressed by the separator test s(x, P), the maximum is always (essentially) the same universal test.

9 Are uniform tests too strong?

Monotonicity and/or quasi-convexity

Uniform tests may seem too strong, in case P is a non-computable measure. In particular, randomness with respect to computable measures (in the sense of Martin-Löf or in the uniform sense, they are the same for computable measures) has certain intuitively desireable properties that uniform randomness lacks. One of these is monotonicity: roughly, if Q is greater than P then if x is random with respect to P, it should also be random with respect to Q. Proposition 9.1. For computable measures P, Q, for all rational λ > 0, if λP(A) Q(A) for all A, then

m(λ) • λt(x, Q) * < t(x, P). ( 13
)
Here m(λ) is the discrete apriori probability of the rational λ. To make the constant in * < independent of P, Q, one needs also to multiply the left-hand side by * = m(P, Q).

Proof. We have 1 t(x, Q) dQ λt(x, Q) dP, hence λt(x, Q) is a P-test. Using the trimming method of Theorem 7.28 in finding universal tests, one can show that the sum

∑ λ:λ t(x,Q) dP<2 m(λ) • λt(x, Q)
is a P-test, and hence * < t(x, P). Therefore this is true of each member of the sum, which is just what the theorem claims. It is easy to see that the multiplicative constants depend here on P, Q only via inserting a factor m(P, Q).

The intuitive motivation for monotonicity is this: if there are two devices with internal randomness generators, outputting numbers with distributions P and Q, and if λP Q, then it can be imagined that the second device simulates the first one with probability λ, and does its own thing otherwise. Then every outcome intuitively plausible as the outcome of the first device, must also be deemed a plausible outcome of the second one, since this could have simulated the first one by chance. (The numerical value of the randomness deficiency may be, of course, somewhat larger, since we must believe in addition that the λprobability event occurred.)

Uniform randomness violates, alas, this property: if measure Q is larger, but computationally more complex, then the randomness tests with respect to Q can exploit this additional information, to make nonrandom some outcomes that were random with respect to P (see the proof of Theorem 5.39). This is just the reason of the difference between uniform and blind (oracle-free) randomness, for which the analogous monotonicity property is obviously satisfied.

Another situation for which we have some intuition on randomness is the mixture (convex combination) of measures. Imagine two devices with output measures P and Q, and an outer box which triggers one of them with some probabilities λ, 1λ. As a whole, we obtain a system whose outcome is distributed by the measure λP + (1λ)Q. About which outcomes can we assert that are obtained randomly as a result of this experiment? Clearly both the outcomes random with respect to P and those random with respect to Q must be accepted (with the understanding that if the coefficient is small then some additional, but finite suspicion is added). And there should not be any other outcomes. A quantitative elaboration of this result (which in one direction follows from monotonicity) is given below. Proposition 9.2. Let P and Q be two computable measures. (a) For a rational 0 < λ < 1, m(λ) • t(x, λP + (1λ)Q) * < max(t(x, P), t(x, Q)).

(b) For arbitrary 0 < λ < 1, t(x, λP + (1λ)Q) * > min(t(x, P), t(x, Q)).

The constants in * < depend on the length of the shortest programs defining P and Q (their complexities), but not on λ (or other aspects of P, Q).

Statement (a) could be called the quasi-convexity of randomness tests (to within a multiplicative constant). For a test with an exact quasi-convexity property (without any multiplicative constants) there is a lower semicomputable semimeasure that is neutral (after extending tests to semimeasures see [START_REF] Levin | Uniform tests of randomness[END_REF]8]).

Statement (b) implies that no other random outcomes exist for the mixture of P and Q. This could be called the quasi-concavity of randomness tests (to within a multiplicative constant). It is easy to see that all these statements exploit the computability of the measures and the mixing coefficients in an essential way. The corresponding counterexamples are easy to build once it is recognized that the mixture of measures can be stronger from an oracle-computational point of view than any of them, as well as in the other way. For example, let us divide the segment 1] into two halves and consider the measures P and Q that are uniformly distributed over these halves. Their mixture with coefficients λ and 1λ will make the number λ obviously non-random (since it can be computed from this measure), though with respect to one of the measures in can very well be random. Taking instead of P and Q their mixtures, say, with coefficients 1/3 and 2/3 and then reversed, one can make λ random with respect to both measures.

In this example the mixture contains more information than each of the original measures. It can also be the other way: bend the interval [0, 1] with the uniform measure into a circle, and cut it into two half-circles by the points p and p + 1/2. Then the uniform measures on these half-circles make p computable with respect to them and thus non-random, while the average of these measures is the uniform measure on the circle, with respect to which p can very well be random.

Let us note that for blind (oracle-free) randomness, we can guarantee without any restrictions that the set of points random with respect to the mixture of P and Q is the union of points random with respect to P and Q. (In one direction this follows from monotonicity, which we already mentioned. In the other one: if an outcome is not random with respect to P and not random with respect to Q, then there are two tests proving this, and their minimum will a lower semicomputable test proving its non-randomness with respect to the mixture.)

These are strong motives to modify the concept of randomness test in order to reproduce these properties, while conserving other desireable properties (say the existence of a universal test and with it the notion of a deficiency of randomness). Some such modifications can be seen in [START_REF] Levin | Uniform tests of randomness[END_REF]8,[START_REF] Levin | Randomness conservation inequalities: Information and independence in mathematical theories[END_REF].

Locality

Imagine that some sequence ω is uniformly random with respect to measure P and starts with 0. Change the values of the measure on sequences that start with 1. It is not guaranteed that ω remains uniformly random since now the measure may become stronger as an oracle (allowing to compute more). But this looks strange since the changes in measure are in the part of the universe that does not touch ω.

For blind (oracle-free) randomness, specifically this example is impossible (one can force the test to zero on sequences beginning with unity), but in principle the concept of test depends not only on the measure along the sequence (not only on the probabilities of occurrences of nulls and ones after its start).

For randomness with respect to computable measures, the situation is again better.

Proposition 9.3 (Prequentiality). Let P, Q be two computable measures on the space Ω of binary sequences, coinciding on all initial segments of some sequence ω. Then this sequence is simultaneously random or non-random with respect to P and Q.

Proof. This follows immediately from the randomness criterion in terms of the complexity of the inital segments (Levin-Schnorr Theorem) in any of its variants (Theorem 2.24, Proposition 2.30, Corollary 2.32).

On the other hand, it is easy to modify one of the counterexamples in 9.1 to violate prequentiality as well.

In case of an arbitrary constructive metric space an analogous statement holds, though with a stronger requirement: we assume that two computable measures are equal on all sets contained in some neighborhood of the outcome ω. (In this case it is possible to multiply the test by a basic function without changing it in ω, and making it zero outside the neighborhood of coincidence).

Here is yet another way to obtain a clearly prequential definition of randomness, in which the randomness deficiency is a function of the sequence itself and the measures of its initial segments. For a given sequence ω and a given sequence {q(i)} of real numbers with 1 = q(0) q(1) q(2) • • • 0, let t ′ (ω, q) = inf t(ω, P), where the minimum is taken over all measures P with P(ω(1 : n)) = q(n). The corresponding sets are effectively compact, so that this minimum will be a lower semicomputable function of ω and the sequence q. If for the sequence ω and the measures q(i) of its initial segments, the value t ′ (ω, q) is finite, then the sequence ω can be called prequentially random.

In other words, sequence ω is prequentially random with respect to measure P if there is a (in general different) measure Q with respect to which ω is random and which coincides with P on all initial segments of ω.

The requirement of prequentiality has been invoked in connection with a theory that extends probability theory and statistics to models of forecasting: see for example [START_REF] Chernov | On-line probability, complexity and randomness[END_REF] and [START_REF] Kh | Prequential randomness and probability[END_REF]. An example situation is the following. Let ω(n) = 1 mean that there is rain on day n and 0 otherwise. Suppose that a forecasting office makes daily forecasts p(1), p(2), . . . of the probability of rain. It is not necessarily proposing a coherent probability model of global weather (a global probability distribution). It just provides forecasts for the conditional probabilities along the path corresponding to the weather that actually takes place.

Is it possible to estimate the quality of the forecast? It seems that in some situations, yes: if say, all forecasts are close to zero (say, less than 10%), and the majority of days (say more than 90%) is rainy. (It is said that the forecast is poorly calibrated.) Naturally, there are other possible inconsistencies, not related to the frequencies: the general question is whether the given sequence can be accepted as randomly obtained with the predicted probabilities. (Such a question arises also in the situation of estimating the quality of a random number generator each of whose output values is claimed to occur with whatever distribution the customer requires at that time of the process, for that particular bit.)

An additional circumstance to consider at the estimation of the quality of forecasts is that the forecaster can use a variety of information accessible to her at the moment of prediction (say, the evening of the preceding day), and not only the members of the sequence ω. The presence of such information must also be taken into account at the estimation of the quality of the forecast.

The paper [START_REF] Kh | Prequential randomness and probability[END_REF] proposes several different approaches to this question, which turn out to be equivalent. One involves a generalization of the notion of martingale (see Definition 3.8). It would be interesting to establish a connection with uniform randomness tests in the spirit of the above defined prequential deficiency. (Admittedly, in place of probabilities of initial segments, one must deal here with conditional probabilities, which is not quite the same, if these are not separated from zero.) 10 Questions for future discussion

We have already noted some questions that (in our view) would be interesting to study. In this section we collected a few more such questions.

1. Consider the following method for generating a sequence ω ∈ Ω using an arbitrary distribution P on Ω in which the probabilities of all words are positive. Take a random sequence ρ of independent reals ρ(1), ρ(2), . . . uniformly distributed over [0, 1]. At stage n, after outputting ξ(1 : n -1), set ξ(n) = 1 if ρ(n) < P(ξ(1 : n -1)1)/P(ξ(1 : n -1)).

Considering this as a random process, the output distribution will be exactly P. What sequences can be obtained on the ouput, from a Martin-Löf-random sequence of real numbers on the input? (It can be verified that for computable measures P one gets exactly the sequences that are Martin-Löf-random with respect to P.)

2. Recall the formula for the deficiency for computable measures:

t(ω, P) * = ∑ x⊑ω m(x) P(x) . (14)
Both sides make sense for non-computable P, but this formula is no more true. Indeed, the right-hand side does not change significantly if a measure P is replaced by some other one that is close to P but is much more powerful as an oracle; and the left-hand side can become infinite while it was finite for P. Denote the righ-hand side by t ′ (ω, P). Does it make sense to take the finiteness of t ′ (ω, P) as a definition of randomness by a non-computable measure?

It will be at least monotonic (an increase of the measure will only increase randomness). With respect to mixtures of measures, we can say that it is quasi-convex; moreover, it is proved in [START_REF] Gács | Complexity and Randomness[END_REF] that 1/t ′ (ω, P) is a concave function of P.

Another possibility is to define the randomness deficiency for an infinite sequence ω as log sup x⊑ω M(x)/P(x) (and consider the corresponding definition of randomness). For computable measures we obtain a definition equivalent to Martin-Löf's standard one. Paper [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF] shows that the uniform tests defined by this expression (whether to use m(x) or M(x)) do not obey randomness conservation, while the universal uniform test does. The work [START_REF] Gács | Complexity and Randomness[END_REF] shows that, on the other hand, an expression related to the right-hand side of ( 14), whith the summation running over all positive basic functions instead of only the functions 1 xΩ (ω), obeys randomness conservation.

3. Can we define a reasonable class of tests with the property in Proposition 9.1 holding for all measures P (or some stronger version of it) so that there exists an universal class? For example, one may require

P c • Q ⇒ t(ω, P) t(ω, Q)/c
(motivation: this is true for the right-hand side of formula ( 14). Could one also require the quasi-convexity, as in Proposition 9.2? Papers [START_REF] Levin | Uniform tests of randomness[END_REF] and [8] provide some such examples, as well as [START_REF] Levin | Randomness conservation inequalities: Information and independence in mathematical theories[END_REF]. How about the quasi-concavity of Proposition 9.2? A uniform test with this property seems less likely, since our counterexample seems more robust.

4. Relativization in recursion theory means that we take some set A and artificially declare it "decidable" by adding some oracle that tells us whether x ∈ A for any given x. Almost all the theorems of classical recursion theory can be relativized. It is more delicate to declare some set E "enumerable". This means that we have some enumeration-oracle that enumerates the set E. The problem is, of course, that there are many enumerations. Still we can give the definition of an E-enumerable set. Let W be a set of pairs of the form (x, S ) where x is an integer and S is a finite set of integers; assume W to be enumerable in the classical sense. Then consider the set S (E, W) of all x such that (x, S ) ∈ W for some S ⊂ E. The sets S (E, W) (for fixed E and all enumerable W) are called enumerable with respect to the enumeration-oracle E.

(The relation (x, S ) ∈ E means that we add x to the E-enumeration as soon as we see all elements of S in E.) A standard (decision) oracle for a set A can be considered a special case of an enumeration oracle (say, for the set {2n : n ∈ A} ∪ {2n + 1 : n / ∈ A}.

For some purposes, an enumeration oracle is as meaningful as a decision oracle: for example, we can speak about a lower semicomputable function with respect to enumeration oracle E, since it can be defined in terms of enumerable sets. But what can be proved for this kind of relativized notions? For example, is there (for an arbitrary E) a maximal lower E-semicomputable semimeasure? Can one define prefix complexity with oracle E, and will it coincide with the logarithm of the maximal semimeasure lower semicomputable relative to E (if the latter exists)? What if we assume, in addition, that E is the set of all basic balls in a constructive metric space, containing a given point? (For comparison: we could define an E-computable function as a function whose graph is E-enumerable. Then some familiar properties will hold; say, the composition of E-computable functions is again E-computable. On the other hand, we cannot guarantee that every non-empty E-enumerable set is the range of a total E-computable function: for some E this is not so.) 5. We may try do extend the definition of randomness in a different direction:

to lower semicomputable semimeasures (that is output distributions of probabilistic machines that generate output sequence bit by bit). Levin's motivation for his definition was his goal to define the independence of the pair (x, η) of infinite sequences as randomness with respect to the semimeasure M × M. Correspondingly, the the deficiency of randomness of the pair (ξ, η) with respect to M × M could be called the quantity of mutual information between the sequences ξ and η. This is motivated by the fact that the algorithmic mutual information Kp(x) + Kp(y) -Kp(x, y) =log(m(x) × m(y)) -Kp(x, y) between finite objects x, y indeed looks like deficiency of randomness with respect to m × m. One possibility is to require that M(z)/Q(z) is bounded, where M is a priori probability on the tree and Q is the semimeasure in question. The other possibility is to use random sequences for unbiased coin tossing and consider the output sequences in all these cases. It is not clear whether these two definitions coincide or if the second notion is well-defined (that is for two different machines with the same output distribution the image of the set of random sequences is the same). For computable measures it is indeed the case. 6. (Steven Simpson) Can we use uniform tests (modified in a proper way) for defining, say, 2-randomness? (The standard definition uses nonsemicontinuous tests, but maybe it can be reformulated.)

  we have b a/2 (for large enough a), hence log a log b + 1, and then a + < b + 2 log a + < b + 2 log b.

Proposition 4 . 5 .

 45 Every extended Bernoulli test generates a Bernoulli test over Ω. On the other hand, every Bernoulli test over Ω is generated by some extended Bernoulli test.

Notation 4 . 6 .

 46 Let B(n, k) denote the set of binary strings of length n with k ones (and nk zeroes).

Definition 4 . 7 .

 47 A combinatorial Bernoulli test is a function f : {0, 1} * → [0, ∞] with the following constraints: (a) It is lower semicomputable. (b) It is monotonic with respect to the prefix relation. (c) For all integer n, k with 0 k n the average of the function f on the set B(n, k) remains below 1:

Definition 4 . 10 .

 410 Let us fix a universal combinatorial Bernoulli test b(x) and extend it to infinite sequences ω by b(ω) = sup x⊑ω b(x).

Proposition 4 . 17 .

 417 Let f : Ω × [0, 1] → R be a basic function. The integral f (ω, p) B p (dω) is a computable function of the parameter p, uniformly in the code of the basic function f .

Definition 5 .

 5 3. An (open) interval (basic open set) in the space of measures is given by a finite set of conditions of type u < P(y) < v where y is some binary string and u, v are some rational numbers; the basic open set consists of the measures P that satisfy these conditions. A basic open set in Ω × M (Ω) has the form xΩ × β, (product of intervals in Ω and M (Ω)) where β is a basic open set of measures. Now lower and upper semicomputability and computability are defined in terms of these basic open sets just as they were defined for Ω × [0, 1] in Definition 4.13.

Proposition 5 . 5 .

 55 Every effectively closed subset of M (Ω) is effectively compact. Proof. Let an effectively closed subset C of M (Ω). be the complement of the union of a list B 1 , B 2 , . . . of basic open sets. Then a finite set S of basic open sets covers C if and only if together with a finite set of the B i , it covers the whole space. And this property is decidable. Effective compactness implies effective closedness. This follows from the following two properties of our space and our basic open sets: (a) For every closed set F and every point x outside F there are two disjoint open sets containing F and x. (b) For every pair of basic open sets, it is uniformly decidable whether they are disjoint. Let F be an effectively compact set. We call a basic open set B manifestly disjoint of F, if there is a finite set of basic open sets S disjoint of B covering F. Due to the effective compactness of F and property (b), the set of all basic open sets manifestly disjoint of F is enumerable. Property (a) implies that it covers the complement of F.

Theorem 5 . 23 .

 523 Let C be an effectively compact class of measures. (a) There exists a universalC -test t C (•). (b) t C (ω) = inf P∈C t(ω, P).Proof. Both of these statements are proved analogously to Lemmas 4.20 and 4.21.

Examples 7 .

 7 2. 1. A set X = {s 1 , s 2 , . . . } can be turned into a constructive discrete metric space by making the distance between any two different points equal to 1. The set D consists of all points α(i) = s i .2. The set N = N ∪ {∞} can be turned into a constructive metric space by making the distance between any two different points with the distance functiond(x, y) = | 1 x -1 y |, where of course, 1 ∞ = 0.The set D consists of all points of N. This metric space is called the one-point compactification, in a topological sense, of the discrete metric space N of Example 1.

Definition 7 . 5 .

 75 An open subset of a constructive metric space is lower semicomputable open (or r.e. open, or c.e. open), or effectively open if it is the union of an enumerable set of elements of the canonical basis. It is upper semicomputable closed, or effectively closed if its complement is effectively open. Given any set A ⊆ X, a set U is effectively open on A if there is an effective open

Definition 7 . 6 (

 76 Computable function). Let X, Y be constructive metric spaces and f: X → Y a function. Then f is continuous if for each element U of the canonical basis of Y the set f -1 (U) is an open set. It is computable if f -1 (U)is also an effectively open set, uniformly in U. A partial function f : X → Y defined at least on a set A is computable if for each element U of the canonical basis of Y the set f -1 (U) is effectively open on A, uniformly in U.

Figure 1 :

 1 Figure 1: A hat function

Definition 7 .

 7 15 (Effective compactness and local compactness). A compact subset C of a constructive metric space X = (X, d, D, α) is called effectively compact if the set { S : S is a finite set of basic open sets and E∈S E ⊇ C } is enumerable. A subset C of a metric space is called locally compact if it is covered by the union of a set of balls B such that B ∩ C is compact. Here B is the closure of B. It is effectively locally compact if it is covered by the union of an enumerated sequence of basic balls B k such that B k ∩ C is effectively compact, uniformly in k. Examples 7.16. 1. The countable discrete space of Example 7.2.1 is effectively compact if it is finite, and effectively locally compact otherwise.

Proposition 7 . 17 .

 717 (a) A compact subset C of a constructive metric space X = (X, d, D, α) is effectively compact if and only if from each (rational) ε one can compute a finite set of ε-balls covering C. (b) For an effectively compact subset C of a constructive metric space, in every enumerable set of basic open sets covering C one can effectively find a finite covering.

  be a lower semicomputable function, and C an effectively closed subset of Y × Z. If it is also effectively compact, then the function g(y) = inf z:(y,z)∈C f (y, z)

Theorem 8. 9 .

 9 Let C be a class of measures. (a) If class C is Borel and orthogonal then there is a separator function for it. (b) Class C is effectively orthogonal if and only if there is a separator test for it.

  Proof. Part (a) follows from Proposition 9.1. Indeed, if λ 1/2 then Proposition 9.1 implies m(λ)• t(x, λP + (1λ)Q) * < t(x, P) (absorbing 1/2 into the * <). If λ < 1/2 then it implies m(1λ) • t(x, λP + (1λ)Q) * < t(x, Q) similarly,and we just recall m(λ) *= m(1λ). Part (b) follows from the fact that the right-hand side is a test with respect to an arbitrary mixture of the measures P and Q, and trimming can convert it into uniform test.

  Definition 2.2. An open set G ⊆ Ω is called effectively open, or lower semicomputable open, or c.e. open, or r.e. open if it is the union of a computable sequence x i Ω of basic elements. A set is upper semicomputable closed, or effectively closed if its complement is effectively open. A set Γ is called effectively G δ if there is a sequence of sets U k , k = 1, 2, . . . effectively open uniformly in k such that Γ = k U k .

  RANDOMNESS ON SEQUENCES, FOR COMPUTABLE MEASURES 7 s 1 , s 2 , . . . of real numbers is a strong Cauchy sequence if for all m < n we have |s ms n | 2 -m .

x 1 , x 2 , . . . for which |x nx n+k | 2 -n . An infinite sequence 2.

  p) for all ω.Proof. By Proposition 4.16, we can represent ϕ(ω, p) as a sum of a series of basic functions ϕ(ω, p) = ∑ n h n (ω, p). The integral ∑ i n h i (ω, p)B p (dω) is computable by Proposition 4.17, as a function of p (uniformly in n), therefore the set S n of all p where this integral is less than 2 is effectively open, uniformly in n.Define now h ′ n (ω, p) as h n (ω, p) for all p ∈ S n , and 0 otherwise. The function h ′ n (ω, p) is lower semicomputable, and the integral ∑ i n h ′ i (ω, p)B p (dω) will be less than 2 for all p. Defining ϕ ′ = ∑ n h ′ n we obtain a lower semicomputable function, and the theorem on the integral of monotonic limits gives that ϕ ′ (ω, p)B p (dω) is less than 2 for all p.It remains to note that if for some p the integral ϕ(ω, p)B p (dω) does not exceed 1, then this p enters all sets S n , and the change from h n to h ′ n as well as the change from ϕ to ϕ ′ does not change it. Now we are ready to introduce tests depending explicitly on p: Definition 4.19. A uniform test for Bernoulli measures is a function t of two arguments ω ∈ Ω and p ∈ [0, 1]; informally, t(ω, p) measures the amount of nonrandomness ("regularity") in the sequence ω with respect to distribution B p . We require the following: (a) t(ω, p) is lower semicomputable jointly as a function of the pair (ω, p). This lemma implies that ω is a Bernoulli sequence iff t ′ (ω) is finite, that is t(ω, p) is finite for some p ∈ [0, 1].Proof ofLemma 4.20. Generate all lower semicomputable functions; using Proposition 4.18, they can be then trimmed to guarantee that all expectations do not exceed, say, 2, and all uniform tests should get through unchanged. Sum up all the trimmed functions with coefficients whose sum is less than 1/2. Proof of Lemma 4.21. Let us show that t ′ (ω) is a universal Bernoulli test. The integral of this function with respect to B p does not exceed 1 since this function does not exceed t(ω, p) for that p. The statement that this function is lower semicomputable (as a function of ω) is analogous to Proposition 2.7, and the proof is also analogous, relying on compactness. Both are special cases of the general theorem given in Proposition 7.20. Therefore the function inf p t(ω, p) is a Bernoulli test. The universality (maximality) follows obviously, since any Bernoulli test can be considered a uniform Bernoulli test of two variables that does not depend on variable p.

	Lemma 4.22. For a fixed p the function t p (ω) = t(ω, p) coincides (to within a
	bounded factor) with the universal randomness test with respect to B p relativized
	with oracle p.

(b) For every p ∈ [0, 1] the expected value of t(ω, p) (that is t(ω, p)B p (dω))

does not exceed 1.

It remains to prove the three assertions promised earlier: Lemma 4.20. There exists a universal uniform test t(ω, p), that is a test that multiplicatively dominates all uniform tests for Bernoulli measures. Lemma 4.21. For the universal uniform test t of lemma 4.20, the function t ′ (ω) = inf p t(ω, p) coincides (to within a bounded factor in both directions) with the universal Bernoulli test of Definition 4.3.

  For all x at least one of the values t 1 (x), t 2 (x) is infinite. By (a version of) Proposition 7.20, the functions t i (x) are lower semicontinuous, and hence C 1and C 2 -tests respectively. Now we follow some of the reasoning of the proof of Proposition 7.31. For integer k > 1, consider the open set S

		2
	of measures are disjoint effectively compact classes of measures, containing P 1
	and P 2 . Consider the functions
	t i (x) = inf P∈C i	s(x, P).

  Returning to arbitrary effectively compact, effectively orthogonal classes, we can connect the universal tests with class tests of Theorem 5.23 and separator tests.Theorem 8.15. Let C be an effectively compact, effectively orthogonal class of measures, let t(x, P) be the universal uniform test and let t C (x) be a universal class test for C . Assume that s(x, P) is a separator test for C . Then we have the representation

	The following question still remains open:
	Question 6. Is there an ergodic measure over Ω for which uniform and blind
	randomness are different?
	t(x, P)

* = max(t C (x), s(x, P)) for all P ∈ C , x ∈ X.

Proof. Let is note first that t C (x) and s(x, P) do not exceed the universal uniform test t(x, P). Indeed s(x, P) is a uniform test by definition. Also by definition, the universal class test t C (x) is a uniform test.

Acknowledgements

The authors are thankful to their colleagues with them they have discussed the questions considered in the paper: first to L. Levin with whom many of the concepts of the paper originate, to A. Bufetov and A. Klimenko, and also to V. V'yugin and other participants of the Kolmogorov seminar (at the Mechanico-Mathematical school of Moscow State University). The paper was written with the financial support of the grants NAFIT ANR-08-EMER-008-01, RFBR 0901-00709-a, . . . .

An element x ∈ X is called computable if the function f : {0} → X with f (0) = x is computable.

When f (x) is defined only in a single point x 0 then we say that the element

There are several alternative characterizations of a computable element.

Proposition 7.7. The following statements are equivalent for an element x of a constructive metric space X = (X, d, D, α).

(i) x is computable.

(ii) the set of basic balls containing x is enumerable.

The following proposition connects computability with a more intuitive concept based on representation by strong Cauchy sequences. Proposition 7.8. Let X, Y be constructive metric spaces and f : X → Y a function. Then f is computable if and only if there is a computable transformation that turns each strong Cauchy sequence s 1 , s 2 , . . . with s i ∈ D X converging to a point x ∈ X into a strong Cauchy sequence t 1 , t 2 , . . . with t i ∈ D Y converging to f (x).

If f is a partial function with domain Z then f is computable if and only if there is a computable transformation that turns each strong Cauchy sequence s 1 , s 2 , . . . with s i ∈ D X converging to some point x ∈ Z into a strong Cauchy sequence t 1 , t 2 , . . . with t i ∈ D Y converging to f (x).

We omit the-not difficult-proof of this statement. Remark 7.9. Though x 0 -computability means computability from a strong Cauchy sequence s 1 , s 2 , . . . converging to x 0 , it should not be considered the same as computability using a machine that treats this sequence as an "oracle". In case of x 0 -computability, the resulting output must be independent of the strong Cauchy sequence s 1 , s 2 , . . . representing x 0 .

The following definition of lower semicomputability is also a straightforward generalization of the special case in Definition 2.2.