arXiv:1210.5968v9 [cs.DS] 22 Dec 2015

A pair of universal sequence-set betting
strategies
Tomislav Petrović
February 25, 2018
Abstract
We introduce the sequence-set betting game, a generalization
of An. A. Muchnik’s non-monotonic betting game [2]. Instead of
successively partitioning the infinite binary strings by their value
of a bit at a chosen position, as in the non-monotonic game, the
player is allowed to partition the strings into any two clopen sets
with equal measure. We show that, while there is no single computable sequence-set betting strategy that predicts all non-MartinLöf random strings, we can construct two strategies such that every
non-Martin-Löf random string is predicted by at least one of them.

1

Introduction

There is a long history of studying the nature of randomness, even the
formal study goes back to at least von Mises [4]. One way of defining randomness is via a kind of a betting game, a martingale, first used by J. Ville
[5]. Winning in a game against infinite string can be viewed as predictability of a string. The predictability of a string is formally defined in terms of
betting games and computable strategies. A string is said to be predictable
iff there is a computable strategy that, starting with unit capital, by successive betting, wins an unbounded amount of capital when betting against the
string. In [2], An. A. Muchnik et al., introduce the non-monotonic-betting
game. In this game, the player bets on the bits of the string, each bet
consisting of the index (position) of the bit, wagered amount of capital and

the value of the bit she is betting on. If the value of the bit at the chosen
position was guessed correctly the wagered amount is doubled, otherwise it
is lost. The strings for which there is no computable non-monotonic betting strategy that can predict them are called Kolmogorov-Loveland random, since they both independently proposed non-monotonic inspection of
bits in a string [6, 7]. P. Martin-Löf gives his definition of randomness in
terms of computably enumerable statistical tests in [8]. His seminal paper marks a point of departure from the unpredictability paradigm towards
the incompressibility paradigm in defining the random strings. To define
incompressibility, we use the prefix-free variant of Kolmogorov complexity,
K, see [1]. An incompressible infinite string is such that for some constant
c and all of its prefixes p, K(p) ≥ ℓ(p) − c, with ℓ(p) denoting the length
of the prefix. It can be shown that Martin-Löf random strings are precisely
the incompressible ones. Whether Kolmogorov-Loveland random sequences
are a proper subset of Martin-Löf random strings is unknown, and is considered a major open problem in the field of algorithmic information theory
[1, 9, 10, 11, 12, 13]. A characterization of Martin-Löf randomness can be
given in terms of a certain betting game, we’ll call it prefix-betting. In this
game in each iteration the player bets on a segment s of a string extending
the known prefix of a string, p, and if the string she’s playing against starts
with the prefix ps, she wins some money, if not, the wagered amount is
lost. Since prefix-betting is a fair game, if the segment she bets on has
length l, if she is right she wins 2l times the wagered amount. It is known
that a single computable prefix-betting strategy can be constructed that
predicts all compressible strings [3]. Note however, that in the case of a
correct guess, we learn something about the string we are playing against,
namely the next segment of its prefix. But in case we were wrong, we learn
very little, only that it doesn’t begin with the prefix we had bet on. This
asymmetry is twofold. Firstly, if the guess was correct, the measure of the
set that we know contains the sequence reduces by a factor of 2−l , and if
the guess was incorrect it is reduced by a factor of only (1 − 2−l ). Secondly,
if we make an infinite number of correct guesses, we learn all of the bits of
the string. On the other hand, if we make an infinite sequence of wrong
guesses, we still might not learn a single bit of the string. To address the
first kind of asymmetry we introduce a generalization of the non-monotonic
betting game called the sequence-set betting game. This is a game where
the player, initially starting with the set of all strings and unit capital, partitions the set of strings into two clopen sets of equal measure, and bets on
2

one of them. To see that there is no single computable sequence-set-betting
strategy that predicts all compressible strings, at each bet choose the set on
which the strategy looses and obtain a computable sequence of nested sets,
each having a measure of 12 the previous set. The strings in the intersection
of these sets are compressible since we obtained them by a computable procedure, have measure 0, and, by construction, the strategy doesn’t predict
them. On the other hand, we show that it is possible to construct two such
strategies such that every compressible string is predicted by at least one
of them.

2

Definitions and main theorem

Our base space is always the space Ω of infinite binary sequences, with the
Lebesgue measure λ defined on it. For a set U ⊆ Ω with λ(U) > 0 we will
define the conditional measure λU on U as usual by
λU (A) =

λ(A ∩ U)
.
λ(U)

Definition 2.1 (Mass placement). A mass placement is a triple P =
(U, A, µ) where A is a finite partition of the clopen ground set U ⊆ Ω
into clopen sets, with a mass function µ : A → R+ defined on them. We
will call A the partition of P . The above mass placement is called atomic
if its partition consists of a single element.
The mass function is extended to all unions of elements of A: µ(A1 ∪
· · · ∪ Ai ) = µ(A1 ) + · · · + µ(Ai ). The minimum capital of P is
capi(P ) = min
A∈A

µ(A)
.
λ(A)

The grain bound of P is maxA∈A λ(A).
We will say that a mass placement Q = (U, B, ν) is a refinement of a
mass placement P = (U, A, µ), writing Q  P , if each B ∈ B is subset of
some A ∈ A, further µ(A) = ν(A) for all A ∈ A.
y
Definition 2.2 (Grid). Consider a pair of mass placements P = (P 0 , P 1 ),
P j = (U, Aj , µj ), j = 0, 1 with the same ground set U = UP . We will call
such an object a grid. In general, for any grid P we will denote its ground
3

set by UP , its partitions by AjP , and its mass functions by µjP for j = 0, 1.
So
P = (P 0 , P 1), P j = (UP , AjP , µjP ), j = 0, 1.
Let capi(P) = min(capi(P 0 ), capi(P 1 )). The grain bound of P is the maximum of the grain bounds of P 0 and P 1. A grid is atomic if both of its
elements are. We will say that grid P is a refinement of grid Q and write
P  Q if P j  Qj for j = 0, 1.
A set S is compatible with the grid P if it is the union of sets of the
y
form E 0 ∩ E 1 with E j ∈ AjP .
Definition 2.3 (Sum). Let P, Q be grids with disjoint ground sets. Consider the mass placement R with
UR = UP ∪ UQ ,
AjR = AjP ∪ AjQ ,
with µjR (E) = µjP (E) for E ∈ AjP and µjQ (E) for E ∈ AjQ , j = 0, 1. We will
denote R = P + Q. Of course, capi(R) = min(capi(P), capi(Q)). A sum
of three or more elements is defined similarly. A grid P is called diagonal
y
if A0P = A1P , or equivalently, if it is a sum of atomic grids.
Definition 2.4 (Orthogonality). Somewhat dual to diagonality is the concept of orthogonality. The grid P is called orthogonal if for all A ∈ A0P and
B ∈ A1P we have
λU (A ∩ B) = λU (A)λU (B).
(This means that the two algebras, defined by A0 and A1 are conditionally
independent on UP .) Let P be a grid. Let j ∈ {0, 1}. We can replace
an arbitrary element A ∈ AjP with 2 disjoint subsets A = A1 ∪ A2 with
1−j
λ(Ai ∩ B) = λ(A ∩ B)/2 for all B ∈ AP
, and choose µjP (Ai ) = µjP (A)/2.
The new grid will be said to be obtained by an even split from P. Of course
it has the same ground set and min and max capital and as the original
one. Also, splitting conserves orthogonality.
y
Definition 2.5 (Mass placement test). We call a mass placement
(Ω, {Ω}, µ(Ω) = 1) a unit mass placement and an infinite sequence of mass
4

placement refinements T = T0  T1  ... a mass placement test iff T0 is a
unit mass placement.
S
Denote with AT = i ATi . The mass function µT : AT → R+ is defined
by the mass placements Ti , for A ∈ ATi , µT (A) = µS
The mass
Ti (A). P
function is extended to all unions of disjoint B ⊆ AT : µT ( B) =
µT (B).
B∈B
S
For brevity, we drop and write just µT (B).
The capital of A ∈ AT is
c(A) =

µT (A)
λ(A)

For α ∈ Ω, denote with Tα , a set of elements of AT that contain α. We say
that α fails the test T iff
sup c(A) = ∞
A∈Tα

We call a mass placement test a granular test iff the grain bound of Ti
goes to zero in the limit.
y
Definition 2.6 (Sequence-set betting strategy). A mass placement test S
is a sequence-set betting strategy if for all A ∈ ASi , λ(A) = 2−i .
y
Clearly, a sequence set betting strategy is a granular test.
Definition 2.7 (Martin-Löf test). A nested sequence of open sets N =
N1 ⊇ N2 ⊇ . . . with λ(Ni ) ≤ 2−i and Ni computably enumerable uniformly
in i is called
T a Martin-Löf test. An infinite binary sequence α fails the test
N iff α ∈ i∈N Ni . A Martin-Löf test M is called universal if every α that
fails some Martin-Löf test N also fails M.
y
It is well-known that there is an universal Martin-Löf test [8, 1].
Theorem 1. For a Martin-Löf test M, there are two computable sequenceset betting strategies S 0 , S 1 such that for every infinite binary sequence α
that fails M, α fails at least one of S 0 , S 1 .
5

3

Proof

Lemma 3.1. Consider a diagonal grid P with cP= capi(P), and a sequence
2
of disjoint clopen sets E1 , E2 , . . ., Ei ⊆ UP ,
i λ(Ei ) ≤ p λ(UP ) for a
certain p < 1. Let K > 1 be a constant with Kp < 1. We can compute a
sequence of disjoint diagonal grids Q1 , Q2 , . . . with UQi = Ei , and for each
n > 0 a mass placement Rn disjoint from
Q1 , Q2 , . . . , Qn , an even splitting Pn of P and even splittings Qi,n of
Qi such that the following holds:
Q1,n + · · · + Qn,n + Rn  Pn ,
Qn+1 + Rn+1  Rn ,
and for each i, for each atomic part T of Qi we have
max(capi(T 0 ), capi(T 1 )) = cK,
min(capi(T 0 ), capi(T 1 )) = capi(T) ≥ c′ ,

(1)
(2)

where c′ = c(1 − pK). Also the grain bound of Pn is ≤ 2−n .
The 2−n grain bound is arbitrary, it only matters that it converges to 0
constructively.
Proof. We construct the grids Qi and Rn explicitly and recursively. Suppose that Qi , Ri and Pi have been defined already for all i < n. Let
R = Rn−1 , S = Rn (this is still to be defined). Denote
Vn = E1 ∪ · · · ∪ En .
Of course, US = UP \ Vn . It is possible to replace Pn−1 with a Pn obtained
by repeated even splittings in such a way that it becomes compatible with
the clopen set En (and also satisfies the grain bound). We obtain each Qi,n
from Qi and R̃ from R similarly. Note that since Pn−1 was orthogonal, so
is Pn . With these splittings we can achieve the following: for each j = 0, 1,
for each B ∈ AjPn , and i < n we have
B ∩ Ei ∈ AjQi,n , B \ Vn−1 ∈ AjR̃ .
Now, as En is compatible with Pn , it can be written as a disjoint union
En = F1 ∪ · · · ∪ Fm , where each Fk has the form B 0 ∩ B 1 , with B j ∈ AjPn .
6

The (diagonal) grid Qn will be a sum of atomic grids T1 + · · · + Tm , with
UTk = Fk . Of course, US = UR \ En , and
AjS = {A \ Vn : A ∈ AjPn } = {B \ En : B ∈ AjR̃ }.
The interesting part is the definition of the new mass functions µjTk and
µjS . Note that there is a common refinement P̂n of Pn and Q1,n , . . . , Qn,n ,
Rn . (We use P̂n only for the calculations in this proof, not the actual
construction.) Wherever µjTk and µjS are defined, they are identical to µjP̂ .
n

Therefore from now on, we omit the subscript of µj when it signifies µjP̂

n

(which is essentially in all cases). For j = 0, 1, for each B ∈ AjR̃ , we need
to redistribute the mass µj (B) into B ∩ Vn and B \ Vn . The mass assigned
to B ∩ Vn will be distributed among all the Fk with Fk ⊆ B, and the mass
remaining is given to B \ Vn . Let
M = {A ∈ A0Pn : λ(A ∩ Vn ) > pλ(A)}.
First we determine the values of µ0 (·). Suppose A ∈
/ M. Recalling A∩UR =
(A \ Vn ) ∪ (A ∩ En ), a disjoint union, for Fk ⊆ A we set
(
cKλ(Fk ) if A ∈
/ M,
µ0 (Fk ) =
′
c λ(Fk )
otherwise,
(3)
µ0 (A \ Vn ) = µ0 (A ∩ UR ) − µ0 (A ∩ En ).

In other words, for each Fk ⊆ A, if A ∈
/ M then we satisfy the require0
ment (1) by by capi(Tk ) = cK, otherwise we satisfy (2).
Now we determine the values of µ1 (·). Let B ∈ A1Pn . Let Fk = A ∩ B
with A ∈ A0Pn . We set
(
cKλ(Fk ) if A ∈ M,
µ1 (Fk ) =
c′ λ(Fk )
otherwise,

(4)

µ1 (B \ Vn ) = µ1 (B ∩ UR ) − µ1 (B ∩ En ).
These definitions satisfy conditions (2), (1) by design; what remains to
prove is that they provide µj (A \ Vn ) ≥ 0 for A ∈ AjPn . We will actually
prove the stronger inequality µj (A \ Vn ) ≥ c′ λ(A \ Vn ).
7

Consider the case j = 0, and first the case A ∈
/ M. We will prove,
inductively, the stronger statement


λ(A ∩ Vn )
0
µ (A \ Vn ) ≥ c 1 − K
λ(A) = cλ(A) − cKλ(A ∩ Vn ).
(5)
λ(A)
If A ∈
/ M = Mn then for all i < n, for A′ ⊇ A with A′ ∈ A0Pi we had
A′ ∈
/ Mi . Therefore by inductive assumption, for i = n − 1,
µ0 (A′ \ Vn−1 ) ≥ cλ(A′ ) − cKλ(A′ ∩ Vn−1 ).
This linear inequality is conserved by the splittings, therefore also
µ0 (A \ Vn−1 ) ≥ cλ(A) − cKλ(A ∩ Vn−1 ).

(6)

Now by definition (3)
µ0 (A \ Vn ) = µ0 (A \ Vn−1 ) − µ0 (A ∩ En ) = µ0 (A \ Vn−1 ) − cKλ(A ∩ En ),
which together with (6) proves (5).
Now consider the case A ∈ M. Let l be the last i < n where for A′ ⊇ A
with A′ ∈ A0Pi we had A′ ∈
/ Mi . If there is no such i then set l = 0, this
case is trivial. Then by the above proof, for such A′ we have
µ0 (A′ \ Vl−1 ) ≥ cλ(A′ ) − cKλ(A′ ∩ Vl−1 ) ≥ c′ λ(A′ ∩ Vl−1 ).
From now on the process for all i > l will either split evenly or assign
µ0 (A ∩ Ei ) = c′ λ(A ∩ Ei ) and µ0 (A \ Vi ) = µ0 (A \ Vi−1 ) − c′ λ(A ∩ Ei ). Both
kinds of step conserve the lower bound c′ > 0 on capital.
Now consider theS case j = 1; we want to prove µ1 (B \ Vn ) ≥ 0 for
B ∈ A1Pn . Let M = M. We claim
λ(B ∩ M) ≤ pλ(B).

(7)

For this, we will use the orthogonality of Pn and the assumption λ(Vn ) ≤
p2 λ(UP ) of the lemma. For every A ∈ M we have by definition of M,
λ(A ∩ Vn ) > pλ(A). Let u = λ(UPn ). Then
p2 u ≥ λ(Vn ) ≥ λ(M ∩ Vn ) > pλ(M),
8

implying λ(M) < pu. By orthogonality,
λ(B ∩ M)/u = (λ(B)/u)(λ(M)/u) ≤ pλ(B)/u,
implying (7). By definition (4), and using (7),
µ1 (B ∩ M ∩ Vn ) ≤ cKλ(B ∩ M ∩ Vn ) ≤ cKpλ(B),
hence
µ1 (B \ (M ∩ Vn )) ≥ µ1 (B) − cKλ(B ∩ M)
≥ cλ(B)(1 − Kp) = c′ λ(B) ≥ c′ λ(B \ (M ∩ Vn )).
By definition (4), µ1 (B ∩ Vn \ M) = c′ λ(B ∩ Vn \ M), hence
µ1 (B \ Vn ) ≥ c′ λ(B \ (M ∩ Vn )) − c′ λ(B ∩ Vn \ M) = c′ λ(B \ Vn ),
finishing the proof.
Lemma 3.2. For any Martin-Löf test N we can computably construct two
granular tests P 0 , P 1 such that every infinite binary sequence α that fails
N, α fails P 0 or α fails P 1.
Proof. We construct the granular tests explicitly and recursively.
For some i, suppose that Q is a diagonal grid with UQ = H for some
H ∈ Ni . Recall that a diagonal grid is a sum of atomic grids and let
T1 , . . . , Tn be atomic grids such that T1 + · · ·+ Tn = Q. Let Tk = (Tk0 , Tk1 )
Denote
m(Q) = min max(capi(Tk0 ), capi(Tk1 ))
k

and let c = capi(Q), K = 2m(Q)/c and r such that 2−r ≤ 1/(cK)2 .
Let E1 , E2 , . . . be an enumeration of elements of Nr ∩ H. By Lemma 3.1,
there is a sequence of disjoint diagonal grids QT,Q = Q1 , Q2 , . . . and a
sequence of mass placements RT,Q = R1 , R2 , . . ., such that Ri is disjoint
from Q1 , . . . , Qi , Q  Q1 + · · · + Qi + Ri , UQj = Ej , and
m(Qj ) = Kc = 2m(Q).
9

Denote by P0 a grid consisting of a pair of unit mass placements. Let
Q = P0 , denote with Qi1 ,...,in ,k the k-th element of QT,Qi1 ,...,in and with
Ri1 ,...,in ,k the k-th element of RT,Qi1 ,...,in . Denote by
X
Pk =
Qi1 ,...,in + Ri1 ,...,in
i1 +···+in =k

a sum of disjoint grids. We have that Pk  Pk+1 since Ri1 ,...,in  Qi1 ,...,in +1 +
Ri1 ,...,in +1 and Qi1 ,...,in  Qi1 ,...,in ,1 + Ri1 ,...,in ,1 . We have obtained a sequence
of grid refinements
P0  P1  . . .. Note that since T is a test, N0 = {Ω}
S
and UP0 = N0 . Then for every sequence of clopen sets E = E0 ⊇ E1 ⊇
. . ., Ei ∈ Ni , there is an infinite subsequence E ′ = E0′ ⊇ E1′ ⊇ . . ., chosen
in the following way: let E0′ = E0 and if for some i1 , . . . , in , Ei′ = UQi1 ,...,in ,
′
then there is some k such that UQi1 ,...,in ,k ∈ E. Let Ei+1
= UQi1 ,...,in ,k .
′
a
diagonal
grid
Then for every Ei there is a refinement Pi′ that contains
T
′
i
Q with UQ = Ei and m(Q) = 2 . Then for α ∈ i∈N Ei for at least one
j ∈ {0, 1} we’ll have
sup µj (A)/λ(A) = ∞. Let P 0 = P00  P10  . . .
1

and P =

P01



P11

A∈AjP ,α∈A

 . . . . We have that P 0 , P 1 satisfy the lemma.

Lemma 3.3. For any granular test P we can computably construct a
sequence-set betting strategy S such that for every infinite binary sequence
α that fails P , α fails S.
Proof. In this proof ⊂ means strict inclusion. Let h > 1, A ∈ AS for some
sequence-set betting strategy S and B a finite, disjoint
S subset of AP . We’ll
say A corresponds to B, and write A ∼ B iff A ⊆ B and two conditions
are satisfied:
µP (B) < hµS (A)
(8)
∀B ∈ B

max c(B ′ ) < 2h max
c(A′ ).
′

B⊂B ′ ∈AP

A⊆A ∈AS

(9)

We’ll explicitly and recursively construct S with the property
∀A ∈ AS ∃B ⊆ AP A ∼ B

(10)

We claim that any sequence-set betting strategy with the property (10)
satisfies the theorem. We prove the claim by contradiction. Suppose there
is some infinite binary sequence α that fails P and passes S. For any α the
following statement is either true or false:
∀B ∈ Pα ∀∞ A ∈ Sα ∀B ⊆ AP A ∼ B ⇒ B 6∈ B
10

(11)

Suppose (11) is false. Then there is some B ∈ Pα such that for infinitely
many A ∈ Sα there is some B ⊆ AP that contains B and A ∼ B. We cannot
have that µP (B) = 0 as this is contrary to the assumption that α fails P .
If µP (B) > 0 then since lim λ(A) = 0, by (8) we have that sup c(A) = ∞
A∈Sα

A∈Sα

contrary to the assumption that α passes S.
Suppose (11) is true. Note that for any two elements of AP they are
either disjoint or one contains the other. Then for every B ∈ Pα and
A ∈ Sα let A ∼ BA for some BA ⊆ AP . For almost all A, then B 6∈ BA .
But α ∈ B ′ for some B ′ ∈ BA , and then either B ⊂ B ′ or B ′ ⊂ B. Since
there are finitely many B ′ ⊃ B in AP , and they can be only in BA for
finitely many A’s, for all but finitely many A we have B ′ ⊂ B. From (9)
there is some A′ ⊇ A with c(B) < 2hc(A′ ) and by the assumption that
α fails P we have that sup c(A) = ∞, contrary to the assumption that α
A∈Sα

passes S. This proves the claim.
Now to the construction of S. Since both P and S are tests, we have
that S0 corresponds to {P0 }. Let A be the part of AS already constructed,
and assume it satisfies (10). Then for all A ∈ A there is some B ⊆ AP with
A ∼ B. Denote CB = {B ∈ B : c(B) < 2h max
c(A′ )}. Then CB 6= ∅,
′
A⊆A ∈AS

since

1
λ(B \ CB ) ≤ λ(A)
2

(12)

is implied by (8).
Let k be such that B ∈ CB , B ∈ APk−1 and B 6∈ APk . Replacing
BS
with
S
′
′
it’s partitions in APk we obtain B . We have A ∼ B since B = B′ ,
satisfying (8), and (9) is satisfied for elements B ′ 6= B of B′ due to (9)
for B, and for B itself is due to B ∈ CB . Applying iteratively, since P is
granular, for any ǫ we can obtain B′ such that for any B ∈ CB′ , λ(B) < ǫ.
Note that there is at least one M ∈ CB′ with c(M) ≤ c(B′ ) and A ∩ M 6= ∅
since for all B ∈ B′ \ CB′ , c(B) ≥ c(B′ ). Note that (12) holds also for B′ .
We now partition B′ into three sets B0′ , {M}, B1′ , having B′ \ CB′ ⊆ B0′ , and
distributing
the elements of CB′ \ {M} among B0′ , B1′ so that for j ∈ {0, 1},
S ′
λ( Bj ∩ A) ≤ 21 λ(A). Furthermore, we can partition M into M0 , M1 so
that the sets A0 , A1
Aj = A ∩ (

[

Bj′ ∪ Mj ) for j = 0, 1
11

have λ(Aj ) = 21 λ(A). Let Bj = Bj′ ∪ {M} and
µS (Aj ) =

µP (Bj )
µS (A)
µP (B0 ) + µP (B1 )

We have µP (B0 ) + µP (B1 ) = µP (B′ ) + µP (M) < (1 + ǫ)µP (B′ ). Let h′ =
µP (B′ )/µS (A). Then µP (Bj ) < h′ (1 + ǫ)µS (Aj ), from (8) h′ < h, and by
choosing small enough ǫ, (8) is satisfied for Aj , Bj . We have that (9) is
satisfied for Aj , Bj since it is satisfied for A, B′ . We have shown from the
inductive assumption that A ∼ B for some B ⊆ AP , we obtain two subsets
of AP , B0 , B1 , a partition of A into two sets of equal measure, A0 , A1 , and
their mass assignments such that A0 ∼ B0 and A1 ∼ B1 , proving that S has
property (10).

Proof of Theorem 1. By Lemmas 3.2 and 3.3 for any Martin-Löf test, and in
particular the universal one, M, we can computably construct two sequenceset betting strategies S 0 , S 1 such that every infinite binary sequence that
fails M also fails at least one of S 0 , S 1 .

Acknowledgements
I thank Wolfgang Merkle for our discussions and support, Jason Rute for
his suggestions on improving the readability, Mark Lemay for proof reading
and corrections, and Peter Gács for his most generous help in improving
and streamlining the proof and helping form the final version of the paper.

Bibliography
[1] Ming Li, Paul M. B. Vitányi: An Introduction to Kolmogorov Complexity and Its Applications, Third Edition. Texts in Computer Science,
Springer 2008, ISBN 978-0-387-33998-6, pp. i-xxiii, 1-790 1, 2
[2] Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky: Mathematical Metaphysics of Randomness. Theor. Comput. Sci. 207(2): 263317 (1998) (document), 1
12

[3] C.P. Schnorr. Zufälligkeit und Wahrscheinlichkeit; Eine algorithmische
Begründung der Wahrscheinlichkeitstheorie, volume 218 of Lect. Notes
Math. Springer-Verlag, Berlin, 1971. 1
[4] R. von Mises. Grundlagen der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 5:52–99, 1919. [xviii, 229] 1
[5] J. Ville. Etude Critique de la Notion de Collectif. Gauthier-Villars,
Paris, 1939. 1
[6] A.N. Kolmogorov. On tables of random numbers. Sankhya , The Indian
Journal of Statistics, Ser. A, 25:369–376, 1963. 1
[7] D.W. Loveland. A new interpretation of von Mises’ concept of a random
sequence. Z. Math. Logik und Grundlagen Math., 12:279–294, 1966. 1
[8] P. Martin-Löf. The definition of random sequences. Inform. Contr.,
9:602–619, 1966. 1, 2
[9] Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank
Stephan: Kolmogorov-Loveland randomness and stochasticity. Ann. Pure
Appl. Logic 138(1-3): 183-210 (2006) 1
[10] Rodney G. Downey, Denis R. Hirschfeldt: Algorithmic Randomness
and Complexity. Theory and Applications of Computability, Springer
2010, ISBN 978-0-387-95567-4, pp. 1-766 1
[11] Joseph S. Miller, André Nies: Randomness and Computability: Open
Questions. Bulletin of Symbolic Logic 12(3): 390-410 (2006) 1
[12] K. Ambos-Spies and A. Kučera. Randomness in computability theory.
In P. Cholak, S. Lempp, M. Lerman, and R.A. Shore, editors, Computability Theory and Its Applications: Current Trends and Open Problems, vol- ume 257 of Contemporary Mathematics, pages 1–14. American
Math. Society, 2000. 1
[13] Rodney G. Downey, Denis R. Hirschfeldt, André Nies, Sebastiaan Terwijn: Calibrating Randomness. Bulletin of Symbolic Logic 12(3): 411-491
(2006) 1

13

