# Randomness and initial segment complexity for measures

André Nies and Frank Stephan

###### Abstract.

We study algorithmic randomness properties for probability measures on Cantor
space. We say that a measure $\mu$ on the space of infinite bit sequences is
Martin-Löf absolutely continuous if the non-Martin-Löf-random bit sequences
form a null set with respect to $\mu$. We think of this as a weak randomness
notion for measures.

We begin with examples, and provide a robustness property related to Solovay
tests. The initial segment complexity of a measure $\mu$ at a length $n$ is
defined as the $\mu$-average over the descriptive complexity of strings of
length $n$, in the sense of either $C$ or $K$. We relate this weak randomness
notion for a measure to the growth of its initial segment complexity. We show
that a maximal growth implies the weak randomness property, but also that both
implications of the Levin-Schnorr theorem fail. We discuss $C$-triviality and
$K$-triviality for measures and relate these two notions with each other.
Here, triviality means that the initial segment complexity grows as slowly as
possible.

We show that full Martin-Löf randomness of a measure implies Martin-Löf
absolute continuity; the converse fails because only the latter property is
compatible with having atoms. In a final section we consider weak randomness
relative to a general ergodic computable measure. We seek appropriate
effective versions of the Shannon-McMillan-Breiman theorem and the Brudno
theorem where the bit sequences are replaced by measures. We conclude with
several open questions.

###### 1991 Mathematics Subject Classification:

03D32,68Q30

André Nies is partially supported by the Marsden Fund of the Royal Society of
New Zealand, 13-UOA-184 and 19-UOA-346. Address: Department of Computer
Science, University of Auckland, Private Bag 92019, Auckland, New Zealand.
Email<EMAIL_ADDRESS>
Frank Stephan is partially supported by supported by the Singapore Ministry of
Education Academic Research Fund Tier 2 grants MOE2016-T2-1-019 /
R146-000-234-112 (2017–2020) and MOE2019-T2-2-121 / R146-000-304-112
(2020–2023). Address: Department of Mathematics and Department of Computer
Science, National University of Singapore, 10 Lower Kent Ridge Road, Block
S17, Singapore 117690, Republic of Singapore. Email<EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
  2. 2 Measures and Randomness
  3. 3 A fast growing initial segment complexity implies being ML-a.c.
  4. 4 Both implications of the Levin-Schnorr Theorem fail for measures
  5. 5 $K$\- and $C$-triviality for measures
  6. 6 Full Martin-Löf randomness of measures
  7. 7 Being ML-a.c. relative to computable ergodic measures
  8. 8 Conclusions and open questions

##  1\. Introduction

The theory of algorithmic randomness is usually developed for bit sequences,
or equivalently, reals in the unit interval. A central randomness notion based
on algorithmic tests is the one due to Martin-Löf [15].

Let $\\{0,1\\}^{{\mathbb{N}}}$ denote the topological space of infinite bit
sequences. A probability measure $\mu$ on $\\{0,1\\}^{{\mathbb{N}}}$ can be
seen as a statistical superposition of bit sequences. A single bit sequence
$Z$ forms an extreme case: the corresponding measure $\mu$ is the Dirac
measure $\delta_{Z}$, i.e., $\mu$ is concentrated on $\\{Z\\}$. At the
opposite extreme is the uniform measure $\mathbf{\lambda}$ which independently
gives each bit value the probability $1/2$. The uniform measure represents
maximum disorder as no bit sequence is preferred over any other.

Recall that a measure $\mu$ on $\\{0,1\\}^{{\mathbb{N}}}$ is called absolutely
continuous if each $\mathbf{\lambda}$-null set is a $\mu$-null set. We
introduce Martin-Löf absolute continuity, an algorithmic randomness notion for
probability measures that is a _weakening_ of absolute continuity: we require
that the $\mathbf{\lambda}$-null set in the hypothesis be effective in the
sense of Martin-Löf. Given that there is a universal Martin-Löf test, and
hence a largest effective null set, all we have to require is that
$\mu(\mathcal{C})=0$ where $\mathcal{C}$ is the class of bit sequences that
are not Martin-Löf random. (By a “measure” we mean a probability measure on
Cantor space unless otherwise stated.)

Our research is motivated in part by a recent definition of Martin-Löf
randomness for quantum states corresponding to infinitely many qubits, due to
the first author and Scholz [24]. Let $M_{n}$ be the algebra of complex
$2^{n}\times 2^{n}$ matrices. Using the terminology there, measures correspond
to the quantum states $\rho$ where the matrix $\rho\\!\upharpoonright_{M_{n}}$
is diagonal for each $n$. For such diagonal states, subsequent work of Tejas
Bhojraj has shown that the randomness notion defined there is equivalent to
the one proposed here for measures. So the measures form a useful intermediate
case to test conjectures in the subtler setting of quantum states. This
applies, for instance, to the Shannon-McMillan-Breiman theorem discussed
below, which is studied in the setting of quantum states by the first author
and Tomamichel (see the post in [23]).

_Growth of the initial segment complexity._ Given a binary string $x$, by
$C(x)$ we denote its plain descriptive complexity, and by $K(x)$ its prefix-
free descriptive complexity. Some of our motivation is derived from the
classical theory. Randomness of infinite bit sequences is linked to the growth
of the descriptive complexity of their initial segments. For instance, the
Levin-Schnorr theorem intuitively says that randomness of $Z$ means
incompressibility (up to the same constant $b$) of all the initial segments of
$Z$. We want to study how much of this is retained in the setting of measures
$\mu$. The formal growth condition in the Levin-Schnorr theorem says that
$K(x)\geq|x|-b$ for each initial segment $x$ of $Z$. The “$n$-th initial
segment” of a measure $\mu$ is given by its values $\mu[x]$ for all strings
$x$ of length $n$, where $[x]$ denotes the set of infinite sequences extending
$x$. We define the complexities $C(\mu\\!\upharpoonright_{n})$ and
$K(\mu\\!\upharpoonright_{n})$ of such an initial segment as the $\mu$-average
of the individual complexities of the strings of length $n$. With this
definition, in Section 4 we show that both implications of the analog of the
Levin-Schnorr theorem fail. However by Proposition 7.4 discussed below, for
measures that are random in our weak sense, $C(\mu\\!\upharpoonright_{n})/n$,
or equivalently $K(\mu\\!\upharpoonright_{n})/n$, converges to $1$. Thus, such
measures have effective dimension 1; see Downey and Hirschfeldt [8, Section
12.3] for background on effective dimension.

It turns out that interesting new growth behaviour is possible for measures.
We verify in Fact 3.3 that the uniform measure $\mathbf{\lambda}$ has maximal
growth behaviour in the sense of $K$, namely
$K(\mathbf{\lambda}\\!\upharpoonright_{n})\geq^{+}n+K(n)$. This implies that
$\mathbf{\lambda}$ also has maximal growth in the sense of $C$. For bit
sequences, such a growth rate is ruled out by a result of Katseff. We use
that, in a sense to be made precise, most strings of a given length are
incompressible. We also provide an example of such a measure other than
$\mathbf{\lambda}$. On the other hand, we show that maximal growth in the
sense of $C$ implies ML absolute continuity.

_$K$ -trivial and $C$-trivial measures._ Opposite to random bit sequences lie
the $K$-trivial sequences $A$, where the initial segment complexity grows no
faster than that of a computable set, in the sense that
$K(A\\!\upharpoonright_{n})\leq^{+}K(n)$. Chaitin [6] proved that each
$C$-trivial sequence is computable, while Solovay [34] showed that a
$K$-trivial can be noncomputable. For background see e.g. [22, Section 5.3].
In Section 5 we extend these notions to statistical superpositions of bit
sequences: we introduce $C$\- and $K$-trivial measures. We first show that
such measures have a countable support. This means that they are countable
convex combinations of Dirac measures (based on bit sequences that necessarily
satisfy the same notion of triviality). Thereafter, again guided by the case
of bit sequences, we provide closure properties of the two notions: downward
closure under truth-table reducibility, and closure under products.

We leave the question open whether each $C$-trivial measure is $K$-trivial. In
Prop. 5.8 we study three conditions relating $C$-complexity and
$K$-complexity, and show that they are all equivalent. If these conditions
hold then each $C$-trivial measure is $K$-trivial. (Whether they indeed hold
was discussed at length in a working group at the 2020 American Institute of
Mathematics workshop on randomness and applications. A weaker version of such
a condition was considered in Bruno Bauwen’s thesis [1].)

We will also consider slightly stronger forms of the notions of $C$\- and
$K$-triviality, for which this implication holds, and is proper.

_Martin-Löf random measures._ Measures can be viewed as points in a canonical
computable probability space, in the sense of [11]. This yields a notion of
Martin-Löf randomness for measures. Bienvenu and Culver (see [7, Theorem
2.7.1]) have shown that no measure $\mu$ that is Martin-Löf random is
absolutely continuous; in fact $\mu$ is orthogonal to $\lambda$ in the sense
that some $\mathbf{\lambda}$-null set is co-null with respect to $\mu$. In
contrast, in Section 6 we show that this notion implies our weak notion of
randomness, Martin-Löf absolute continuity. The stronger randomness notion
forces the measure to be atomless, so the converse implication fails. Further
questions can be asked about the relationships between the different
randomness notions for measures we have discussed. For instance, does the
randomness notion studied by Culver imply that the initial segment complexity
for the measure (in the sense of $C$ or of $K$) is maximal infinitely often?

_Shannon-McMillan-Breiman Theorem._ This theorem from the 1950s says
informally that for an ergodic measure $\rho$ on $\\{0,1\\}^{{\mathbb{N}}}$,
outside of an appropriate null set, every bit sequence $Z$ reflects the
entropy of the measure $\rho$ by the limit of the weighted information content
w.r.t. $\rho$ of initial segments of $Z$, namely,
$-\frac{1}{n}\log_{2}\rho[Z\\!\upharpoonright_{n}]$. See e.g. [32], where the
result is called the Entropy Theorem. In the short Section 7, we replace $Z$
by a measure $\mu$ that is Martin-Löf a.c. with respect to $\rho$, and take
the $\mu$-average of the information contents of strings of the same length.
We only obtain a partial analog of the theorem. We use as a hypothesis that
the weighted information content of strings w.r.t. $\rho$ is bounded, and also
provide an example showing that this hypothesis is necessary. However, in a
similar vein, in Proposition 7.4 we establish an analog for measures of the
effective Brudno’s theorem [9, 10], which states that the entropy of $\rho$ is
given as the limit of $C(Z\\!\upharpoonright_{n})/n$, for any $Z$ that is
$\rho$-ML-random. We show that one can take the limit of
$C(\mu\\!\upharpoonright_{n})/n$ for any $\mu$ that is ML absolutely
continuous in $\rho$.

We conclude the paper with conclusions and open questions.

For general background on recursion theory and algorithmic randomness we refer
the readers to the textbooks of Calude [4], Downey and Hirschfeldt [8], Li and
Vitányi [14], Nies [22], Odifreddi [27, 28] and Soare [33]. Lecture notes on
recursion theory are also available online, e.g. [35].

An 11-page conference version of the paper has appeared in STACS 2020 [26].
The present paper is a much improved and expanded version, in particular
Sections 3 and 5.

##  2\. Measures and Randomness

In this section we will formally define one of our main notions, Martin-Löf
absolute continuity (Definition 2.3), and collect some basic facts concerning
it. In particular, we verify that the well-known equivalence of Martin-Löf
test and Solovay tests extends to measures. We begin by briefly discussing
algorithmic randomness for bit sequences [8, 22]. We use standard notation:
letters $Z,X,\ldots$ denote elements of the space of infinite bit sequences
$\\{0,1\\}^{{\mathbb{N}}}$, $\sigma,\tau$ denote finite bit strings, and
$[\sigma]=\\{Z\colon\,Z\succ\sigma\\}$ is the set of infinite bit sequences
extending $\sigma$. $Z\\!\upharpoonright_{n}$ denotes the string consisting of
the first $n$ bits of $Z$. For quantities $r,s$ depending on the same
parameters, one writes $r\leq^{+}s$ for $r\leq s+O(1)$. A subset $G$ of
$\\{0,1\\}^{{\mathbb{N}}}$ is called _effectively open_ if
$G=\bigcup_{i}[\sigma_{i}]$ for a computable sequence
${\left\langle{\sigma_{i}}\right\rangle}_{i\in{\mathbb{N}}}$ of strings. A
measure $\rho$ on $\\{0,1\\}^{{\mathbb{N}}}$ is computable if the map
$\\{0,1\\}^{<\omega}\to{\mathbb{R}}$ given by $\sigma\mapsto\rho[\sigma]$ is
computable. That is, each real $\rho[\sigma]$ is computable, uniformly in
$\sigma$.

######  Definition 2.1.

Let $\rho$ be a computable measure on $\\{0,1\\}^{{\mathbb{N}}}$. A
$\rho$-Martin-Löf test ($\rho$-ML-test, for short) is a sequence
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ of uniformly
effectively open sets such that $\rho G_{m}\leq 2^{-m}$ for each $m$. A bit
sequence $Z$ _fails_ the test if $Z\in\bigcap_{m}G_{m}$; otherwise it _passes_
the test. A bit sequence $Z$ is $\rho$-Martin-Löf random ($\rho$-ML-random for
short) if $Z$ passes each $\rho$-Martin-Löf-test.

By $\mathbf{\lambda}$ one denotes the uniform measure on
$\\{0,1\\}^{{\mathbb{N}}}$. So $\mathbf{\lambda}[\sigma]=2^{-|\sigma|}$ for
each string $\sigma$. If no measure $\rho$ is provided it will be tacitly
assumed that $\rho=\mathbf{\lambda}$, and we will use the term “Martin-Löf-
random” instead of “$\mathbf{\lambda}$-Martin-Löf-random” etc. Let $K(x)$
denote the prefix free version of descriptive (i.e., Kolmogorov) complexity of
a bit string $x$.

######  Theorem 2.2 (Levin [13], Schnorr [30]).

$Z$ is Martin-Löf-random $\Leftrightarrow$ $\exists b\,\forall
n\,[K(Z\\!\upharpoonright_{n})\geq n-b]$.

Using the notation of [22, Chapter 3], let $\mathcal{R}_{b}$ denote the set of
bit sequences $Z$ such that $K(Z\\!\upharpoonright_{n})<n-b$ for some $n$. It
is easy to see that
${\left\langle{\mathcal{R}_{b}}\right\rangle}_{b\in{\mathbb{N}}}$ forms a
Martin-Löf test. The Levin-Schnorr theorem says that this test is universal:
$Z$ is Martin-Löf-random iff it passes the test.

Recall that unless otherwise stated, all measures are probability measures on
Cantor space. We use the letters $\mu,\nu,\rho$ for measures (and recall that
$\lambda$ denotes the uniform measure). We now provide the formal definition
of our weak randomness notion for measures.

######  Definition 2.3.

Let $\rho$ be a measure. A measure $\mu$ is called _Martin-Löf absolutely
continuous in $\rho$_ if $\inf_{m}\mu(G_{m})$ $=$ $0$ for each $\rho$-Martin-
Löf-test ${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$. We denote
this by $\mu\ll_{ML}\rho$.

If $\inf_{m}\mu(G_{m})=0$ we say that $\mu$ _passes_ the test. If
$\inf_{m}\mu(G_{m})\geq\delta$ where $\delta>0$ we say $\mu$ _fails the test
at level_ $\delta$.

In the case that $\rho=\mathbf{\lambda}$, we say that $\mu$ is ML absolutely
continuous, for short.

Martin-Löf absolute continuity is a _weakening_ of the usual notion that $\mu$
is absolutely continuous in $\rho$, usually written $\mu\ll\rho$. In fact,
$\mu\ll\rho$ holds iff $\mu$ is $\rho$-$ML^{X}$ absolutely continuous for each
oracle $X$.

In the definition it suffices to consider $\rho$-ML tests
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ such that
$G_{m}\supseteq G_{m+1}$ for each $m$, because we can replace
${\left\langle{G_{m}}\right\rangle}$ by the $\rho$-ML test given by
$\widehat{G}_{m}=\bigcup_{k>m}G_{k}$, and of course
$\inf_{m}\mu(\widehat{G}_{m})=0$ implies that $\inf_{m}\mu(G_{m})=0$. So we
can change the definition above, replacing the condition $\inf_{m}G_{m}=0$ by
the only apparently stronger condition that $\lim_{m}G_{m}=0$.

It is well known that there is a universal $\rho$-ML test. The intersection of
all the components of such a test consists of the non-$\rho$-ML-random
sequences. This implies:

######  Fact 2.4.

$\mu\ll_{ML}\rho$ iff the sequences that are not $\rho$-ML-random form a
$\mu$-null set.

We have already mentioned the two diametrically opposite types of examples of
measure that are ML absolutely continuous in a measure $\rho$:

######  Example 2.5.

(a) $\rho\ll_{ML}\rho$ for each measure $\rho$.

(b) For a Dirac measure $\delta_{Z}$, we have $\delta_{Z}\ll_{ML}\rho$ iff $Z$
is $\rho$-ML-random.

Next we provide a source of non-examples where $\rho=\mathbf{\lambda}$.

######  Example 2.6.

A Bernoulli measure on $\\{0,1\\}^{{\mathbb{N}}}$ assigns a fixed probability
$p$ to a $0$, independently of the position. Such a measure is not ML
absolutely continuous in the case that $p\neq 1/2$. To see this, note that
each Martin-Löf-random sequence $Z$ satisfies the law of large numbers

$\lim_{n}\frac{1}{n}|\\{i<n\colon Z(i)=1\\}|=1/2;$

see e.g. [22, Proposition 3.2.19]. So if $\mu$ is ML absolutely continuous,
then $\mu$-almost surely, $Z$ satisfies the law of large numbers. This is not
the case when $\mu$ is a Bernoulli measures for $p\neq 1/2$, because $\mu$
a.e. $Z$ satisfies the law of large numbers for $p$ instead of $1/2$.

######  Definition 2.7.

For a measure $\nu$ and string $\sigma$ with $\nu[\sigma]>0$, let
$\nu_{\sigma}$ denote the localisation to $[\sigma]$:

$\nu_{\sigma}(A)=\nu(A\cap[\sigma])/\nu[\sigma].$

Clearly if $\nu$ is ML absolutely continuous then so is $\nu_{\sigma}$.

A set $S$ of probability measures is called _convex_ if $\mu_{i}\in S$ for
$i\leq k$ implies that the convex combination $\mu=\sum_{i}\alpha_{i}\mu_{i}$
is in $S$, where the $\alpha_{i}$ are reals in $[0,1]$ and
$\sum_{i}\alpha_{i}=1$. The _extreme points_ of $S$ are the ones that can only
be written as convex combinations of length 1 of elements of $S$.

######  Proposition 2.8.

The ML absolutely continuous probability measures form a convex set. Its
extreme points are the ML absolutely continuous Dirac measures, i.e. the
measures $\delta_{Z}$ where $Z$ is a ML-random bit sequence.

###### Proof.

Let $\mu=\sum_{i}\alpha_{i}\mu_{i}$ as above where the $\mu_{i}$ are ML
absolutely continuous measures. Suppose ${\left\langle{G_{m}}\right\rangle}$
is a Martin-Löf test. Then $\lim_{m}\mu_{i}(G_{m})=0$ for each $i$, and hence
$\lim_{m}\mu(G_{m})=0$.

Suppose that $\mu$ is Martin-Löf a.c. If $\mu$ is a Dirac measure then it is
an extreme point of the Martin-Löf a.c. measures. Conversely, if $\mu$ is not
Dirac, there is a least number $t$ such that the decomposition

$\mu=\sum_{|\sigma|=t,\mu[\sigma]>0}\mu[\sigma]\cdot\mu_{\sigma}$

is nontrivial. Hence $\mu$ is not an extreme point. ∎

Recall that a $\rho$-_Solovay-test_ , for a computable probability measure
$\rho$, is a sequence ${\left\langle{S_{k}}\right\rangle}_{k\in{\mathbb{N}}}$
of uniformly $\Sigma^{0}_{1}$ sets such that $\sum_{k}\rho(S_{k})<\infty$. If
$\rho=\mathbf{\lambda}$ we will simply use the term _Solovay test_. A bit
sequence $Z$ passes such a test if $Z\not\in S_{k}$ for almost every $k$.
(Each Martin-Löf-test is also a Solovay test, but Solovay tests have a
stronger passing condition). A basic fact from the theory of algorithmic
randomness (e.g. [22, Theorem 3.2.9]) states that $Z$ is Martin-Löf-random iff
$Z$ passes each Solovay test. This is usually asserted only relative to the
uniform measure $\mathbf{\lambda}$, but in fact carries over to arbitrary
measures $\rho$.

The following characterises the ML absolutely continuous measures with
countable support.

######  Fact 2.9.

Let $\mu=\sum_{k}c_{k}\delta_{Z_{k}}$ where $0<c_{k}\leq 1$ for each $k$, and
$\sum_{k}c_{k}=1$. Then $\mu$ is ML absolutely continuous iff all the $Z_{k}$
are Martin-Löf random.

###### Proof.

The implication from left to right is immediate. For the converse implication,
given a Martin-Löf test ${\left\langle{G_{m}}\right\rangle}$, note that the
$Z_{k}$ pass this test as a Solovay test. Hence for each $r$, there is $M$
such that for each $k\leq r$ and each $m\geq M$ we have $Z_{k}\not\in G_{m}$ .
This implies that $\mu(G_{m})\leq\sum_{k>r}c_{k}$ for each $m\geq M$. So
$\lim_{m}\mu(G_{m})=0$. ∎

We say that a measure $\mu$ _passes_ a Solovay test
${\left\langle{S_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ if
$\lim_{k}\mu(S_{k})=0$. The fact that passing all Martin-Löf tests is
equivalent to passing all Solovay tests generalises from bit sequences to
measures. We note that Tejas Bhojraj (in preparation) proved such a result in
even greater generality in the setting of quantum states, where the proof is
more involved.

######  Proposition 2.10.

For probability measures $\mu,\rho$ such that $\rho$ is computable, we have

$\mu\ll_{ML}\rho$ iff $\mu$ passes each $\rho$-Solovay-test.

###### Proof.

Relative to $\rho$, each Martin-Löf test is a Solovay test, and the passing
condition $\lim_{m}\mu(G_{m})=0$ works for both types of tests by the remark
after Definition 2.3. This yields the implication from right to left.

For the implication from left to right, suppose that $\mu\ll_{ML}\rho$, and
let ${\left\langle{S_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ be a
$\rho$-Solovay-test. By $\limsup_{k}S_{k}$ one denotes the set of bit
sequences $Z$ such that $\exists^{\infty}k\,[Z\in S_{k}]$, that is, the
sequences that fail the test. By the basic fact (e.g. [22, Theorem 3.2.9])
mentioned above, the set of $\rho$-Martin-Löf-random sequences is disjoint
from $\limsup_{k}S_{k}$. Hence, by hypothesis on $\mu$, we have
$\mu(\limsup_{k}S_{k})=0$. By Fatou’s Lemma,
$\limsup_{k}\mu(S_{k})\leq\mu(\limsup_{k}S_{k})$. So $\mu$ passes the Solovay
test. ∎

##  3\. A fast growing initial segment complexity implies being ML-a.c.

In this section we formally define our two variants of initial segment
complexity for measures, and first their connections with ML absolute
continuity.

Recall that in this paper we use $C(x)$ to denote the plain Kolmogorov
complexity of a binary string $x$ and $K(x)$ to denote the prefix-free
Kolmogorov complexity. Note that other letters are also used in the
literature; for example, the textbook by Calude [4] uses $K$ and $H$, a
notation going back to Chaitin.

Recall the upper bounds $C(x)\leq^{+}n$ and $K(x)\leq^{+}n+K(n)$ for all
strings $x$ of length $n$. We assume for notational convenience the strict
lower bounds that $C(n)\leq C(x)$ and $K(n)\leq K(x)$. This convention reduces
the number of constants needed in the statements and proofs of our results. To
achieve this, we replace some given universal machine $V$ by a new universal
machine $U$ such that whenever $V(p)=x$ then $U(0p)=0^{|x|}$ and $U(1p)=x$
with $0^{n}$ standing for $n$, and $U$ is undefined on all other inputs. It is
easy to see that if $V$ is universal by adjunction, so is $U$; if $V$ is
prefix-free so is $U$. The descriptions for $U$ are only by one bit longer
than those for $V$ and universality requires only that the length of the
shortest descriptions for some $x$ goes up at most by a constant.

######  Definition 3.1.

Let $K(\mu\\!\upharpoonright_{n}):=\sum_{|x|=n}K(x)\mu[x]$ be the
$\mu$-average of all the $K(x)$ over all strings $x$ of length $n$. In a
similar way we define $C(\mu\\!\upharpoonright_{n})$. We also define the
descriptive complexity conditioned on $n$, namely
$C(\mu\\!\upharpoonright_{n}\mid n)$, as expected.

It may help to think of $K(\mu\\!\upharpoonright_{n})$ as $\int K_{n}d\mu_{n}$
where $K_{n}$ and $\mu_{n}$ are the respective functions restricted to the set
of strings of length $n$. Note that for each bit sequence $Z$, we have
$K(\delta_{Z}\\!\upharpoonright_{n})=K(Z\\!\upharpoonright_{n})$.

In this section we tacitly rely on standard inequalities such as
$C(x)\leq^{+}K(x)$, $K(x)\leq^{+}|x|+2\log|x|$ and $K(0^{n})\leq^{+}2\log n$.
We also use that for each $r\in{\mathbb{N}}$, there are at most $2^{r}-1$
strings such that $C(x)<r$. See e.g. [22, Chapter 2].

Note that for each string $x$ of length $n$, the deviations from the upper
bounds are related by the inequality $n-C(x)\leq^{+}2(n+K(n)-K(x))$. For this,
see e.g. [22, 2.2.5] which yields the inequality after some elementary
algebraic manipulation. Taking the $\mu$-average, this implies the
corresponding inequality for the initial segment complexity of measures on
Cantor space:

######  Fact 3.2.

Let $\mu$ be a measure. For each $n$ one has

$n-C(\mu\\!\upharpoonright_{n})\leq^{+}2(n+K(n)-K(\mu\\!\upharpoonright_{n})).$

The following says that the uniform measure $\mathbf{\lambda}$ on
$\\{0,1\\}^{{\mathbb{N}}}$ has the fastest growing initial segment complexity
that is possible in the sense of $K$, and therefore also of $C$.

######  Fact 3.3.

$K(\mathbf{\lambda}\\!\upharpoonright_{n})\geq^{+}n+K(n)$, and therefore also
$C(\mathbf{\lambda}\\!\upharpoonright_{n})\geq^{+}n$.

###### Proof.

Chaitin [5] showed that there is a constant $c$ (dependent only on the
universal prefix-free machine) such that, for all $d$, among the strings of
length $n$, there are at most $2^{n+c-d}$ strings with $K(x)\leq n+K(n)-d$;
also see [22, Thm. 2.2.26].

Fix $n$. For $d\in{\mathbb{N}}-\\{0\\}$ let $A_{d}$ be the set of strings of
length $n$ such that $K(x)\leq n+K(n)-d$. Identifying sets of strings of the
same length and the clopen sets they generate, by Chaitin’s result we have
$\mathbf{\lambda}A_{d}\leq 2^{c-d}$.

Clearly $K(x)=n+K(n)-\sum_{d>0}1_{A_{d}}(x)$ whenever $|x|=n$. Taking the
$\mathbf{\lambda}$-average over all strings of length $n$ we obtain

$2^{-n}\sum_{|x|=n}\geq n+K(n)-\sum_{d>0}\mathbf{\lambda}(A_{d})\geq
n+K(n)-\sum_{d>0}2^{c-d}=n-2^{c+1}$.

∎

We provide an example of a computable probability measure
$\mu\neq\mathbf{\lambda}$ that satisfies the hypothesis of Fact 3.3.
Informally, along a string, $\mu$ puts $1/3$ on $0$ until it hits the first
$1$; from then on $\mu$ behaves like the uniform measure $\mathbf{\lambda}$.

Recall from 2.7 on the localization $\nu_{\sigma}$ of a measure $\nu$ to a
string $\sigma$. For $r\in{\mathbb{N}}-\\{0\\}$ let $\sigma(r)$ denote the
string $0^{r-1}1$. Note that for a string $y$ of length $n-r$ one has
$K(\sigma(r)\hat{\ }y)\geq^{+}K(y)$ (where the additive constant is
independent of both $n$ and $r$). So by Fact 3.3 for $n\geq r$ one has
$K(\mathbf{\lambda}_{\sigma(r)})\geq^{+}n-r+K(n-r)$.

######  Fact 3.4.

The computable measure $\mu=2\sum_{r>0}3^{-r}\mathbf{\lambda}_{\sigma(r)}$
satisfies $K(\mu\\!\upharpoonright_{n})\geq^{+}n+K(n)$.
Moreover, $\mu$ is absolutely continuous.

###### Proof.

$\displaystyle K(\mu\\!\upharpoonright_{n})$ $\displaystyle=$ $\displaystyle
2\sum_{r=1}^{\infty}3^{-r}K(\mathbf{\lambda}_{\sigma(r)})$
$\displaystyle\geq^{+}$ $\displaystyle 2\sum_{r=1}^{n}3^{-r}(n-r+K(n-r))$
$\displaystyle\geq^{+}$ $\displaystyle n-2\sum_{r=1}^{n}r\cdot
3^{-r}+2\sum_{r=1}^{n}3^{-r}K(n-r)$ $\displaystyle\geq^{+}$ $\displaystyle
n+K(n)$

The last inequality holds because $2\sum_{r=1}^{\infty}r\cdot 3^{-r}$ is
finite, and because $K(n-r)\geq^{+}K(n)+2\log r$.

Clearly $\mu$ is computable; $\mu$ is absolutely continuous because when
viewed as a measure on the unit interval we have $d\mu=gd\mathbf{\lambda}$
where the function $g\colon[0,1]\to{\mathbb{R}}$ is given by $g(0)=0$,
$g(x)=2\cdot(\frac{2}{3})^{r}$ for $x$ in the interval $(2^{-r-1},2^{-r}]$
where $r>0$ (this interval corresponds to $\sigma_{r}$).∎

Li and Vitanyi [14] called a bit sequence $Z\in\\{0,1\\}^{{\mathbb{N}}}$
Kolmogorov random if there is $r$ such that $C(Z\\!\upharpoonright_{n})\geq
n-r$ for infinitely many $n$. One says that $Z$ is strongly Chaitin random if
there is $r$ such that $K(Z\\!\upharpoonright_{n})\geq n+K(n)-r$ for
infinitely many $n$. For bit sequences these notions are equivalent to
2-randomness (i.e., ML-randomness relative to the halting problem) by [25] and
[17], respectively; also see [22, Theorem 8.1.14] or [8].

One can extend these notions to measures. We call $\mu$ strongly Chaitin
random if $K(\mu\\!\upharpoonright_{n})\geq^{+}n+K(n)$ for infinitely many
$n$. Similarly we define Kolmogorov randomness of a measure. By Fact 3.2 the
following is immediate:

######  Fact 3.5.

If a measure $\mu$ is strongly Chaitin random, then $\mu$ is Kolmogorov
random.

We leave it open whether the reverse implication holds. The potentially weaker
notion already implies being ML absolutely continuous:

######  Theorem 3.6.

Suppose that $\mu$ is a Kolmogorov random measure. Then $\mu$ is ML absolutely
continuous.

###### Proof.

By hypothesis there is $r\in{\mathbb{N}}$ such that
$C(\mu\\!\upharpoonright_{n})\geq n-r$ for infinitely many $n$. Assume for a
contradiction that $\mu$ is not ML absolutely continuous. So there is a
Martin-Löf test ${\left\langle{G_{d}}\right\rangle}_{d\in{\mathbb{N}}}$ and
$\delta>0$ such that $\mu(G_{d})\geq\delta$ for each $d$. We view $G_{d}$ as
given by an enumeration of strings, uniformly in $d$; thus
$G_{d}=\bigcup_{i}[\sigma_{i}]$ for a sequence
${\left\langle{\sigma_{i}}\right\rangle}_{i\in{\mathbb{N}}}$ that is
computable uniformly in $d$. Let $G_{d}^{\leq n}$ denote the clopen set
generated by the strings in this enumeration of length at most $n$. (Note that
this set is not effectively given as a clopen set, but we effectively have a
description of it as a $\Sigma^{0}_{1}$ set). Let $c$ be a constant such that,
for each $x$ of length $n$, one has $C(x)\leq n+c$.

######  Lemma 3.7.

If $x$ is a string of length $n$ such that $[x]\subseteq G_{d}^{\leq n}$ then
$C(x\mid d)\leq^{+}n-d$.

To verify this, let $N$ be a fixed plain machine that on input $y$ and
auxiliary input $d$ prints out the $y$-th string $x$ of length $n=|y|+d$ such
that the enumeration of $G_{d}^{\leq n}$ asserts that $[x]\subseteq
G_{d}^{\leq n}$. (Here we view $y$ as the binary representation of a number,
with leading zeros allowed.) Since $\mathbf{\lambda}G_{d}\leq 2^{-d}$,
sufficiently many strings are available to print all such $x$. This machine
shows that $C(x\mid d)\leq^{+}n-d$ for any $x$ such that $[x]\subseteq
G_{d}^{\leq n}$, as required. This verifies the lemma.

Note that (after possibly increasing the constant $c$) any $x$ as above
satisfies $C(x)\leq n-d+2\log d+c$. For each $d,n$, letting $x$ range over
strings of length $n$, we have

$C(\mu\\!\upharpoonright_{n})=\sum_{|x|=n}C(x)\mu[x]=\sum_{[x]\subseteq
G_{d}^{\leq n}}C(x)\mu[x]+\sum_{[x]\not\subseteq G_{d}^{\leq n}}C(x)\mu[x].$

The first summand is bounded above by $\mu(G_{d}^{\leq n})(n-d+2\log d+c)$ via
the lemma, the second by $(1-\mu(G_{d}^{\leq n}))(n+c)$. We obtain

$C(\mu\\!\upharpoonright_{n})\leq n+c-\mu(G_{d}^{\leq n})d/2.$

Now for each $d$, for sufficiently large $n$ we have $\mu(G_{d}^{\leq
n})\geq\delta$. So given $r$ letting, $d=2r/\delta$, for large enough $n$ we
have $C(\mu\\!\upharpoonright_{n})\leq n+c-r$. This contradicts the hypothesis
on $\mu$. ∎

It would be interesting to find out whether the above-mentioned coincidences
of randomness notions for bit sequences lift to measures; for instance, do the
conditions in the theorem above actually imply that the measure is ML
absolutely continuous relative to the halting problem ${\emptyset^{\prime}}$?

##  4\. Both implications of the Levin-Schnorr Theorem fail for measures

We will show that both implications of the analog of the Levin-Schnorr Theorem
2.2 fail for measures. The implication from left to right would say that a ML
absolutely continuous measure cannot have an initial segment complexity in the
sense of $K$ growing slower than $n-O(1)$. This can be disproved by a simple
example of a measure with countable support.

Note that, by Proposition 7.4 below, we have
$\lim_{n}K(\mu\\!\upharpoonright_{n})/n=1$ for each ML absolutely continuous
measure $\mu$, which provides a lower bound on the growth.

######  Example 4.1.

There is a ML absolutely continuous measure $\mu$ such that for each
$\theta\in(0,1)$, one has $K(\mu\\!\upharpoonright_{n})\leq^{+}n-n^{\theta}$.

###### Proof.

We let $\mu=\sum_{k}c_{k}\delta_{Z_{k}}$ where $Z_{k}$ is Martin-Löf random
and $0^{n_{k}}\prec Z_{k}$ for a sequence
${\left\langle{c_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ of reals in $[0,1]$
that add up to $1$, and a sufficiently fast growing computable sequence
${\left\langle{n_{k}}\right\rangle}_{k\in{\mathbb{N}}}$ to be determined
below. Then $\mu$ is ML absolutely continuous by Fact 2.9.

For $n$ such that $n_{k}\leq n<n_{k+1}$ we have

$\displaystyle K(\mu\\!\upharpoonright_{n})$ $\displaystyle\leq^{+}$
$\displaystyle(\sum_{l=0}^{k}c_{l})\cdot(n+2\log
n)+(\sum_{l=k+1}^{\infty}c_{l})\cdot 2\log n$ $\displaystyle\leq^{+}$
$\displaystyle(1-c_{k+1})n+2\log n.$

Hence, to achieve $K(\mu\\!\upharpoonright_{n})\leq^{+}n-n^{\theta}$ it
suffices to ensure that $c_{k+1}n_{k}\geq n_{k+1}^{\theta}+2\log n_{k+1}$ for
almost all $k$. For instance, we can let $c_{k}=\frac{1}{(k+1)(k+2)}$ and
$n_{k}=2^{k+4}$. ∎

To disprove the implication from right to left in a potential generalisation
to measures of the Levin-Schnorr Theorem, we need to provide a measure $\mu$
such that $\mu$ is not Martin-Löf a.c. yet
$K(\mu\\!\upharpoonright_{n})\geq^{+}n$. This is immediate from the following
fact on the growth of the initial segment complexity for certain bit sequences
$X,Y$, letting $\mu=(\delta_{X}+\delta_{Y})/2$.

######  Theorem 4.2.

There are a Martin-Löf random bit sequence $X$ and a non-Martin-Löf-random bit
sequence $Y$ such that, for all $n$,
$K(X\\!\upharpoonright_{n})+K(Y\\!\upharpoonright_{n})\geq^{+}2n$.

###### Proof.

Let $X$ be a low Martin-Löf random set (i.e.,
$X^{\prime}\equiv_{T}\emptyset^{\prime}$). We claim that there is a strictly
increasing function $f$ such that the complement of the range of $f$ is a
recursively enumerable set $E$, and $K(X\\!\upharpoonright_{m})\geq m+3n$ for
all $m\geq f(n)$. To see this, recall that
$\lim_{n}K(X\\!\upharpoonright_{n})-n=\infty$. Since $X$ is low there is a
computable function $p$ such that for all $n$, $\lim_{s}p(n,s)$ is the maximal
$m$ such that $K(X\\!\upharpoonright_{m})\leq m+3n$.

Define $f(n,s)$ for $n\leq s$ as follows. $f(n,0)=n$; for $s>0$ let $n$ be
least such that $p(n,s)\geq f(n,s-1)$ or $n=s$. If $m\geq n$ and $n<s$ then
let $f(m,s)=s+m-n$ else let $f(m,s)=f(m,s-1)$.

Note that for each $n$ there are only finitely many $s>0$ with $f(n,s)\neq
f(n,s-1)$ and that almost all $s$ satisfy $f(n,s)>p(n,s)$, as otherwise
$f(n,s)$ would be modified either at $n$ or some smaller value. Furthermore,
$f(n,s)\neq f(n,s-1)$ can only happen if there is an $m\leq n$ with
$f(m,s-1)\leq p(m,s)$ and that happens only finitely often, as all the
$p(m,s)$ converge to a fixed value and every change of an $f(m,s)$ at some
time $s$ leads to a value above $s$. Furthermore, once an element is outside
the range of $f$, it will never return, and so the complement of the range of
$f$ is recursively enumerable. So $f(n)=\lim_{s}f(n,s)$ is a function as
required, which verifies the claim. (The complement $E$ of the range of $f$ is
called a Dekker deficiency set in the literature [27].)

Now let $g(n)=\max\\{m:f(m)\leq n\\}$ (with the convention that
$\max(\emptyset)=0$). Since $g$ is unbounded, by a result of Miller and Yu
[20, Corollary 3.2] there is a Martin-Löf random $Z$ such that there exist
infinitely many $n$ with $K(Z\\!\upharpoonright_{n})\leq n+g(n)/2$; note that
the result of Miller and Yu does not make any effectivity requirements on $g$.
Let

$Y=\\{n+g(n):n\in Z\\}.$

Note that $K(Z\\!\upharpoonright_{n})\leq
K(Y\\!\upharpoonright_{n})+g(n)+K(g(n))$, as one can enumerate the set $E$
until there are, up to $n$, only $g(n)$ many places not enumerated and then
one can reconstruct $Z\\!\upharpoonright_{n}$ from $Y\\!\upharpoonright_{n}$
and $g(n)$ and the last $g(n)$ bits of $Z\\!\upharpoonright_{n}$. As $Z$ is
Martin-Löf random, $K(Z\\!\upharpoonright_{n})\geq^{+}n$, so

$K(Y\\!\upharpoonright_{n})\geq^{+}n-g(n)-K(g(n))\geq^{+}n-2g(n).$

The definitions of $X,f,g$ give $K(X\\!\upharpoonright_{n})\geq n+3g(n)$. This
shows that, for almost all $n$,
$K(X\\!\upharpoonright_{n})+K(Y\\!\upharpoonright_{n})\geq 2n$.

However, the set $Y$ is not Martin-Löf random, because there are infinitely
many $n$ such that
$K(Z\\!\upharpoonright_{n})\linebreak[3]\leq^{+}\linebreak[3]n+g(n)/2$. Now
$Y\\!\upharpoonright_{n+g(n)}$ can be computed from $Z\\!\upharpoonright_{n}$
and $g(n)$, as one needs only to enumerate $E$ until the $g(n)$ nonelements of
$E$ below $n$ are found, and they allow to see where the zeroes have to be
inserted into the string $Z\\!\upharpoonright_{n}$ in order to obtain
$Y\\!\upharpoonright_{n+g(n)}$. We have $K(g(n))\leq g(n)/4$ for almost all
$n$ and thus $K(Y\\!\upharpoonright_{n+g(n)})\leq^{+}n+3/4\cdot g(n)$ for
infinitely many $n$. So the set $Y$ is not Martin-Löf random, as required. ∎

_Failing a strong Solovay test implies non-complex initial segments._ In
contrast to the negative results above, we show that failing a stronger type
of tests leads to considerable dips in the intitial segment complexity of a
measure in the sense of $C$ (and hence, also in the sense of $K$ by Fact 3.2).

We say that a Solovay test
${\left\langle{S_{r}}\right\rangle}_{r\in{\mathbb{N}}}$ is _strong_ if each
$S_{r}$ is clopen and there is a recursive function $g$ such that $g(r)$ is a
strong index for a finite set of strings $X_{r}$ such that
$[X_{r}]^{\prec}=S_{r}$. For bit sequences, this means no restriction of the
corresponding randomness notion: in that case any Solovay test
${\left\langle{G_{m}}\right\rangle}$ can be replaced by a strong Solovay test,
listing strings that make up the uniformly $\Sigma^{0}_{1}$ sets $G_{m}$ one-
by-one. We conjecture that this equivalence of test notions no longer holds
for measures.

The following is a weak version for measures of one implication of the Miller-
Yu theorem [19, Theorem 7.1]. We show that if a measure $\mu$ is far from ML
absolutely continuous, then its initial segment complexity
$C(\mu\\!\upharpoonright_{n}|n)$ defined in Definition 3.1 has infinitely many
dips of size $\delta f(n)$ for some positive constant $\delta$ and a
computable function $f$ that grows somewhat fast in that
$\sum_{n}2^{-f(n)}<\infty$. We use elements of its proof in Bienvenu, Merkle
and Shen [3]. We note that the result is a variation on (the contrapositive
of) Theorem 3.6(a), proving a stronger conclusion from a stronger hypothesis.
A version of the result for quantum states is [24, Thm. 4.4].

######  Proposition 4.3.

Suppose that $\mu$ fails a strong Solovay test
${\left\langle{S_{r}}\right\rangle}_{r\in{\mathbb{N}}}$ at level $\delta$,
namely $\exists^{\infty}r\,[\mu(S_{r})\geq\delta]$. Then there is a computable
function $f$ such that $\sum_{n}2^{-f(n)}<\infty$ and

$\exists^{\infty}n\,[C(\mu\\!\upharpoonright_{n}\mid n)\leq^{+}n-\delta
f(n)].$

###### Proof.

Let ${\left\langle{X_{r}}\right\rangle}$ be as in the definition of a strong
Solovay test. We may assume that $\sum\mathbf{\lambda}S_{r}\leq 1/2$, and all
strings in $X_{r}$ have the same length $n_{r}$, where $n_{r}<n_{r+1}$ for
each $r$. We write $\mu(X_{r})$ for $\mu[X_{r}]^{\prec}$. Let $f$ be the
computable function such that

$2^{-f(n_{r})}\geq\mu(X_{r})>2^{-f(n_{r})-1}$

and $f(m)=m$ for each $m$ that is not of the form $n_{r}$. There is a constant
$d$ such that each bit string $x$ in the set $X_{r}$ satisfies (where
$n=n_{r}$)

(1) $C(x\mid n)\leq n-f(n)+d=:g(r).$

For, $r$ can be computed from $n=n_{r}$, and each string $x\in X_{r}$ is
determined by $r$ and its position $i<2^{n}\mathbf{\lambda}(X_{r})$ in the
lexicographical listing of $X_{r}$. We can determine $i$ by
$\log(2^{n}\mathbf{\lambda}(X_{r}))\leq n-f(n)+d$ bits for some fixed $d$. In
fact we may assume the description has exactly that many bits. Thus, there is
a Turing machine $L$ with two inputs such that for each $\sigma\in X_{r}$, we
have $L(v_{\sigma};n)=\sigma$ for some bit string $v_{\sigma}$ of length
$g(r)$.

Let $c$ be a constant such that $C(x)\leq|x|+c$ for each string $x$. Now
suppose that $\mu(X_{r})\geq\delta$. Then for $n=n_{r}$, where $\sigma$ ranges
over strings of length $n$,

$\displaystyle C(\mu\\!\upharpoonright_{n}\mid n)$ $\displaystyle\leq^{+}$
$\displaystyle\sum_{\sigma\in X_{r}}(n-f(n))\mu[\sigma]+\sum_{\sigma\not\in
X_{r}}(n+c)\mu[\sigma]$ $\displaystyle\leq^{+}$ $\displaystyle
n-f(n)\sum_{\sigma\in X_{r}}\mu[\sigma]$ $\displaystyle\leq^{+}$
$\displaystyle n-\delta f(n).$

There are infinitely many such $r$ by hypothesis. This completes the proof. ∎

##  5\. $K$\- and $C$-triviality for measures

Recall from the third paragraph of Section 3 that our choice of universal
machines implies that $C(n)\leq C(x)$ and $K(n)\leq K(x)$ for all strings $x$
of length $n$.

######  Definition 5.1.

A measure $\mu$ is called $K$-trivial if
$K(\mu\\!\upharpoonright_{n})\leq^{+}K(n)$ for each $n$;

$\mu$ is called $C$-trivial if $C(\mu\\!\upharpoonright_{n})\leq^{+}C(n)$ for
all $n$.

Suppose $\mu$ is a Dirac measures $\delta_{A}$. Then $\mu$ is $K$-trivial iff
$A$ is $K$-trivial in the usual sense, and $\mu$ is $C$-trivial iff $A$ is $C$
trivial in the usual sense, which is equivalent to being recursive by a well-
known result of Chaitin [6] (for a more recent proof see e.g. [22, 5.2.20]).
More generally, any finite convex combination of $K$-trivial Dirac measures is
$K$-trivial, and similarly for $C$. Now if $\alpha,\beta$ are any positive
real numbers such that $\alpha+\beta=1$, then
$\alpha\cdot\delta_{\emptyset}+\beta\cdot\delta_{\mathbb{N}}$ is a $C$-trivial
and $K$-trivial measure such that any measure representation in the sense of
[22, 1.9.2] computes $\alpha$. Thus one cannot bound the computational
complexity of $K$-trivial or of $C$-trivial measures in any way.

For a further example, let ${\left\langle{R_{i}}\right\rangle}$ be a sequence
of uniformly recursive sets, and let ${\left\langle{\alpha_{i}}\right\rangle}$
be a sequence of uniformly recursive positive real numbers such that
$\sum_{i}\alpha_{i}=1$ and $S=\sum_{i}\alpha_{i}\log i$ is finite. Let
$\mu=\sum_{i}\alpha_{i}\delta_{R_{i}}$. Since
$K(R_{i}\\!\upharpoonright_{n})\leq^{+}K(n)+K(i)$ and $K(i)\leq^{+}2\log i$,
for each $n$ we have
$K(\mu\\!\upharpoonright_{n})=\sum_{i}\alpha_{i}K(R_{i}\\!\upharpoonright_{n})\leq^{+}K(n)+2S$.
Hence $\mu$ is $K$-trivial.

Atoms and Triviality. We show that both $K$-trivial and $C$-trivial measures
are discrete in the sense of [31]; namely, they are concentrated on the set of
their atoms. Such measures were further studied by Kautz [12], where they were
called “trivial measures”, and more recently by Porter [29].

######  Proposition 5.2.

If a measure $\mu$ is $K$-trivial, then $\mu$ is supported by its set of
atoms.

In fact the weaker hypothesis $\exists
p\,\exists^{\infty}n\,[K(\mu\\!\upharpoonright_{n})\leq K(n)+p]$ suffices for
this. A similar statement holds for $C$.

###### Proof.

For a set $R\subseteq\\{0,1\\}^{*}$, by $[R]^{\prec}$ one denotes the open set
$\\{Z\colon\,\exists n\,Z\\!\upharpoonright_{n}\in R]\\}$.

Assume for a contradiction that $\mu$ gives a measure greater than
$\varepsilon>0$ to the set of its non-atoms. Fix $c$ arbitrary with the goal
of showing that $K(\mu\\!\upharpoonright_{n})\geq K(n)+\varepsilon c/2$ for
large enough $n$.

There is a constant $d$ (in fact $d=O(2^{c})$) such that for each $n$ there
are at most $d$ strings $x$ of length $n$ with $K(x)\leq K(n)+c$ (see e.g.
[22, Theorem 2.2.26]).

Let $S_{n}=\\{x\colon\,|x|=n\,\land\,\mu[x]\leq\varepsilon/2d\\}$. By
hypothesis we have $\mu[S_{n}]^{\prec}\geq\varepsilon$ for large enough $n$.
Therefore by choice of $d$ we have

$\mu[S_{n}\cap\\{x\colon\,K(x)>K(|x|)+c\\}]^{\prec}\geq\varepsilon/2.$

Now we can give a lower bound for the $\mu$-average of $K(x)$ over all strings
$x$ of length $n$:

$\sum_{|x|=n}K(x)\mu[x]\geq(1-\frac{\varepsilon}{2}K(n)+\frac{\varepsilon}{2}(K(n)+c)\geq
K(n)+\varepsilon c/2,$

as required. Notice that we have only used the weaker hypothesis. ∎

Thus, if $\mu$ is $K$-trivial for constant $p$, then $\mu$ has the form
$\sum_{r<N}\alpha_{r}\delta_{A_{r}}$ where $N\leq\infty$ and each $\alpha_{r}$
is positive and $\sum_{r<N}\alpha_{r}=1$. The following observation will show
that in addition all the $A_{r}$ are $K$-trivial. In particular, $K$-trivial
measures are not Martin-Löf almost continuous.

######  Fact 5.3.

Suppose $\mu=\sum_{r}\alpha_{r}\delta_{A_{r}}$ is $K$-trivial for constant
$p$. Then each $A_{r}$ is $K$-trivial for the constant $p/\alpha_{r}$.
Similarly, if $\mu$ is $C$-trivial with constant $p$, then each $A_{r}$ is
$C$-trivial with constant $p/\alpha_{r}$.

###### Proof.

We have

$K(n)+p\geq
K(\mu\\!\upharpoonright_{n})=\sum_{s}\alpha_{s}K(A_{s}\\!\upharpoonright_{n})\geq
K(n)+\alpha_{r}(K(A_{r}\\!\upharpoonright_{n})-K(n)).$

Therefore, $K(A_{r}\\!\upharpoonright_{n})-K(n)\leq p/\alpha_{r}$, as
required. The proof for $C$ is obtained via replacing $K$ by $C$ everywhere. ∎

Above we built a computable $K$-trivial measure with infinitely many atoms. On
the other hand, the following example shows that not every infinite convex
combination $\mu=\sum_{k}\alpha_{k}\delta_{A_{k}}$ of $K$-trivial Dirac
measures for constants $b_{k}$ yields a $K$-trivial measure, even if there is
a finite bound on the values $\alpha_{k}b_{k}$. Let
$A_{k}=\\{\ell:\ell\in\Omega\wedge\ell<k\\}$ and
$\alpha_{k}=(k+1)^{-1/2}-(k+2)^{-1/2}$. All sets $A_{k}$ are finite and thus
$K$-trivial for constant $2k+O(1)$. Furthermore, the sum of all $\alpha_{k}$
is $1$ and $\alpha_{k}=O(1/k)$. We have

$K(\mu\\!\upharpoonright_{n})=\sum_{|x|=n}K(x)\mu(x)\geq(\sum_{m\geq
n}\alpha_{m})\cdot K(\Omega\upharpoonright
n)\geq(n+2)^{-1/2}\cdot(n+2)=\sqrt{n+2}$

for almost all $n$, and thus the average grows faster than $K(n)+c$. So the
measure is not $K$-trivial.

In a sense, an atomless measure can be arbitrarily close to being $C$-trivial
and $K$-trivial.

######  Proposition 5.4.

For each nondecreasing unbounded function $f$ which is recursively
approximable from above there is a non-atomic measure $\mu$ such that
$C(\mu\\!\upharpoonright_{n})\leq^{+}C(n)+f(n)$ and
$K(\mu\\!\upharpoonright_{n})\leq^{+}K(n)+f(n)$.

###### Proof.

The proof for $C$ and $K$ is essentially the same; we present the one for $K$
first.

There is a recursively enumerable set $A$ such that, for all $n$,
$A\cap\\{0,\ldots,n\\}$ has up to a constant $f(n)/2$ non-elements. One lets
$\mu$ be the measure such that $\mu(x)=2^{-m}$ in the case that all ones in
$x$ are not in $A$ and $\mu(x)=0$ otherwise, where $m$ is the number of non-
elements of $A$ below $|x|$. One can see that when $\mu(x)=2^{-m}$ then $x$
can be computed from $|x|$ and the string $b_{0}b_{1}\ldots b_{m-1}$ which
describes the bits at the non-elements of $A$. Thus

$K(x)\leq^{+}K(|x|)+K(b_{0}b_{1}\ldots b_{m-1})\leq^{+}K(|x|)+2m.$

It follows that $K(\mu\\!\upharpoonright_{n})\leq^{+}K(n)+f(n)$, as the
$\mu$-average of strings $x\in\\{0,1\\}^{n}$ with $K(x)\leq^{+}K(n)+f(n)$ is
at most $K(n)+f(n)$ plus a constant.

Now the bound for $C$ follows along the same lines; note that for $C$ one
gives a prefix-free coding of the string $b_{0}b_{1}\ldots b_{m-1}$ above
followed by a $C$-description for $|x|$ plus a constant-length coding prefix –
assuming that the universal machine is universal by adjunction. Again the
length of the code is $C(n)+f(n)$ plus a constant. ∎

Closure properties of $C$\- and of $K$-triviality. In the following suppose
$\Gamma$ is a total Turing reduction, that is, a truth-table reduction,
mapping $\\{0,1\\}^{{\mathbb{N}}}$ to $\\{0,1\\}^{{\mathbb{N}}}$. Given a
measure $\nu$, let $\mu=\Gamma(\nu)$ denote the image measure, defined as
usual by $\mu({\mathcal{A}})=\nu(\Gamma^{-1}({\mathcal{A}}))$, where
$\mathcal{A}$ is a subset of $\\{0,1\\}^{{\mathbb{N}}}$. As $\Gamma$ is a
truth-table reduction, some strictly increasing computable function $f$ bounds
the use of $\Gamma$.

######  Proposition 5.5.

Let $\mu=\Gamma(\nu)$ as above. We have
$K(\mu\\!\upharpoonright_{n})\leq^{+}K(\nu\\!\upharpoonright_{f(n)})$ and
similarly for $C$. In particular, if $\nu$ is $K$-trivial then so is $\mu$,
and if $\nu$ is $C$-trivial so is $\mu$.

###### Proof.

Let $x$ range over strings of length $n$ and $y$ over strings of length
$f(n)$. Since $K(\Gamma^{y})\leq K(y)$ we have

$\displaystyle K(\mu\\!\upharpoonright_{n})$ $\displaystyle=$
$\displaystyle\sum_{x}K(x)\sum_{\Gamma^{y}\succeq x}\nu[y]\ =\
\sum_{x}\sum_{\Gamma^{y}\succeq x}K(x)\nu[y]$ $\displaystyle\leq^{+}$
$\displaystyle\sum_{x}\sum_{\Gamma^{y}\succeq x}K(y)\nu[y]\ =\
K(\nu\\!\upharpoonright_{f(n)}).$

Using that $n$ and $f(n)$ have, up to a constant, the same descriptive
complexity in the sense of $K$, this completes the proof. The proof for $C$ is
similar to the proof for $K$ with only the obvious changes. ∎

Note that $\\{0,1\\}^{{\mathbb{N}}}\times\\{0,1\\}^{{\mathbb{N}}}$ is
effectively isomorphic to $\\{0,1\\}^{{\mathbb{N}}}$ via the map $A,B\to
A\oplus B$. So a product of two measures on $\\{0,1\\}^{{\mathbb{N}}}$ can
itself be viewed as a measure on $\\{0,1\\}^{{\mathbb{N}}}$. We show that
$K$\- and $C$-triviality of measures is closed under taking products,
generalising well-known facts for bit sequences. The following fact will be
needed for the case of $C$.

######  Fact 5.6.

$K(x\mid\,n,C(n))\leq^{+}2(C(x)-C(n))$ for each $n$ and each
$x\in\\{0,1\\}^{n}$.

###### Proof.

One suffices to show that there is a constant $d$ such that for each $b$,

$C(x)\leq C(n)+b\rightarrow K(x|n,C(n))\leq 2b+d.$

Following an argument of Chaitin [6], Nies [22, Proof of Lemma 5.2.21] showed
that for every plain machine $M$ there are at most $O(b^{2}\cdot 2^{b})$
descriptions $p$ with $M(p)=n$ and $|p|\leq C(n)+b$. Consider the machine $M$
such that $M(p)=0^{|U(p)|}$ where $U$ is the universal plain machine. There
are at most $O(b^{2}\cdot 2^{b})$ many $x\in\\{0,1\\}^{n}$ with $C(x)\leq
C(n)+b$, because any such $x$ has the form $U(p)$ for some $p$ with $M(p)=n$
and $|p|\leq C(n)+b$. Uniformly in $b$, $n$ and $C(n)$, the set of such $x$ is
recursively enumerable. Hence one can provide a prefix-free code of length up
to $2b$ plus constant for any pair $\langle b,a\rangle$ with $a\in
O(b^{2}\cdot 2^{b})$ selecting the $a$-th such $x$. This shows that a constant
$d$ as above exists. ∎

######  Theorem 5.7.

Let $\mu$ and $\nu$ be measures.
(a) If $\mu$ and $\nu$ are $K$-trivial then $\mu\times\nu$ is $K$-trivial.
(b) If $\mu$ and $\nu$ are $C$-trivial then $\mu\times\nu$ is $C$-trivial.

###### Proof.

We assume in both cases (a) and (b) that $\mu$ and $\nu$ are trivial with
respect to the corresponding descriptive string complexity and then show that
$\mu\times\nu$ is trivial for the same complexity notion.

For (a), by Prop 5.2 one may assume that $\mu=\sum_{i}\alpha_{i}A_{i}$ and
$\nu=\sum_{j}\beta_{j}B_{j}$ with $1=\sum_{i}\alpha_{i}$ and
$1=\sum_{j}\beta_{j}$, where the $A_{i}$ and $B_{j}$ are $K$-trivial sets. For
a string $x$ of length $n$ and a shortest description $p$ of (a code for) $n$,
$K(x)=^{+}K(x|p)+|p|$; this follows easily from [14, Theorem 3.9.1]. Note that

$K(A_{i}\oplus
B_{j}\\!\upharpoonright_{2n})\leq^{+}K(n)+K(A_{i}\\!\upharpoonright_{n}|p)+K(B_{j}\\!\upharpoonright_{n}|p).$

Since $\mu$ and $\nu$ are $K$-trivial we have
$K(A_{i}\\!\upharpoonright_{n})=^{+}K(n)+K(A_{i}\\!\upharpoonright_{n}|p)$ and
$K(B_{j}\\!\upharpoonright_{n})=^{+}K(n)+K(B_{j}\\!\upharpoonright_{n}|p)$, so
$\sum_{i}\alpha_{i}K(A_{i}\\!\upharpoonright_{n}|p)$ and
$\sum_{j}\beta_{j}K(B_{j}\\!\upharpoonright_{n}|p)$ are both bounded by some
constant independent of $n$. Let $c$ be a common upper bound of such
constants. Now, for some constant $d$,

$\displaystyle K(\mu\times\nu\\!\upharpoonright_{2n})$ $\displaystyle=$
$\displaystyle\sum_{i,j}\alpha_{i}\cdot\beta_{j}\cdot K(A_{i}\oplus
B_{j}\\!\upharpoonright_{2n})$ $\displaystyle\leq$
$\displaystyle\sum_{i,j}\alpha_{i}\cdot\beta_{j}\cdot(K(n)+K(A_{i}\\!\upharpoonright_{n}|p)+K(B_{j}\\!\upharpoonright_{n}|p)+d)$
$\displaystyle=$ $\displaystyle K(n)+d+(\sum_{i}\alpha_{i}\cdot
K(A_{i}\\!\upharpoonright_{n}|p)\cdot(\sum_{j}\beta_{j})$ $\displaystyle\mbox{
}\ \ \ \ \ \ \ \ +\ (\sum_{i}\alpha_{i})\cdot(\sum_{j}\beta_{j}\cdot
K(B_{j}\\!\upharpoonright_{n}|p)$ $\displaystyle\leq$ $\displaystyle
K(n)+2c+d.$

Since $K(n)=^{+}K(2n)$, one can conclude that $\forall
n\,[K(\mu\times\nu\\!\upharpoonright_{2n})\leq^{+}K(2n)].$ The same can be
proven for $2n+1$ with only a slight more notational complexity. Thus
$\mu\times\nu$ is $K$-trivial.

For (b), as in (a), assume that $\mu=\sum_{i}\alpha_{i}A_{i}$ and
$\nu=\sum_{j}\beta_{j}B_{j}$ with $1=\sum_{i}\alpha_{i}$ and
$1=\sum_{j}\beta_{j}$, where now $A_{i},B_{j}$ are $C$-trivial sets. Let $c$
be the supremum over $n$ of all
$\sum_{i}\alpha_{i}\cdot(C(A_{i}\\!\upharpoonright_{n})-C(n))$ and
$\sum_{j}\beta_{j}\cdot(C(B_{j}\\!\upharpoonright_{n})-C(n))$. Note that
$c<\infty$ because $\mu$ and $\nu$ are $C$-trivial.

One can produce descriptions for $A_{i}\\!\upharpoonright_{n}$ and
$B_{j}\\!\upharpoonright_{n}$ from prefix-free conditional descriptions for
$A_{i}\\!\upharpoonright_{n}$ and $B_{j}\\!\upharpoonright_{n}$, given $n$ and
$C(n)$ together with a coding of these two parameters $n$ and $C(n)$. Note
that $n,C(n)$ can be given by a shortest $C$-description of $n$ in one go,
which needs $C(n)$ bits. With the other two prefix-free conditional
descriptions appended, one obtains for a suitable constant $d^{\prime}$ that

$C(A_{i}\oplus B_{j}\\!\upharpoonright_{2n})\leq
C(n)+K(A_{i}\\!\upharpoonright_{n}|n,C(n))+K(B_{j}\\!\upharpoonright_{n}|n,C(n))+d^{\prime}.$

Now one uses this to show the following as in (a):

$\displaystyle C(\mu\times\nu\\!\upharpoonright_{2n})$ $\displaystyle=$
$\displaystyle\sum_{i,j}\alpha_{i}\cdot\beta_{j}\cdot C(A_{i}\oplus
B_{j}\\!\upharpoonright_{2n})$ $\displaystyle\leq$
$\displaystyle\sum_{i,j}\alpha_{i}\cdot\beta_{j}\cdot(C(n)+K(A_{i}\\!\upharpoonright_{n}|n,C(n))+K(B_{j}\\!\upharpoonright_{n}|n,C(n))+d^{\prime})$
$\displaystyle\leq$
$\displaystyle\sum_{i,j}\alpha_{i}\cdot\beta_{j}\cdot(C(n)\\!+\\!2\\!\cdot\\!((C(A_{i}\\!\upharpoonright_{n})\\!-\\!C(n))\\!+\\!(C(B_{j}\\!\upharpoonright_{n})\\!-\\!C(n)))\\!+\\!2d\\!+\\!d^{\prime})$
$\displaystyle=$ $\displaystyle
C(n)+2d+d^{\prime}+2\cdot(\sum_{i}\alpha_{i}\cdot(C(A_{i}\\!\upharpoonright_{n})-C(n)))\cdot(\sum_{j}\beta_{j})$
$\displaystyle\mbox{ }\ \ \ \ \ \ \ \ +\
2\cdot(\sum_{i}\alpha_{i})\cdot(\sum_{j}\beta_{j}\cdot(C(B_{j}\\!\upharpoonright_{n})-C(n)))$
$\displaystyle\leq$ $\displaystyle C(n)+4c+2d+d^{\prime}.$

The inequality from the first to the second line follows from the definition
of $d^{\prime}$; the inequality from the second to the third line follows from
Fact 5.6.

Thereafter, one uses the distributivity of absolutely converging sums, and the
definition of $c$. The same can be proven for $2n+1$ with only a slight
increase in notational complexity. ∎

The next proposition shows that three conditions involving the descriptive
complexities of strings are equivalent. It is unknown whether these equivalent
conditions are true. These conditions relate fundamental properties of plain
and prefix-free Kolmogorov complexity; properties of similar type have been
investigated quite a lot in algorithmic information theory; fairly recent
sample references are [1, 2, 18, 14]. The last condition states informally
that there are finitely many potential ways to compute $C(n)$ from $n$ and
$K(n)$, and for each $n$ one of them succeeds. (In fact at present it is
unknown whether there is a single way.)

######  Proposition 5.8.

The following conditions are equivalent:

  1. (a)

There is a constant $c$ such that for all $n$ and all $x\in\\{0,1\\}^{n}$,

$K(x)-K(n)\leq 2\cdot(C(x)-C(n))+c$;

  2. (b)

For each $c^{\prime}$ there is $d^{\prime}$ such that for all $n$ and all
$x\in\\{0,1\\}^{n}$,

if $C(x)-C(n)\leq c^{\prime}$ then $K(x)-K(n)\leq d^{\prime}$;

  3. (c)

There is a constant $c^{\prime\prime}$ with $K(C(n)|n,K(n))\leq
c^{\prime\prime}$ for all $n$.

###### Proof.

The implication (a) to (b) is straightforward: if $c^{\prime}$ bounds
$C(x)-C(n)$ then $d^{\prime}=2c^{\prime}+c$ bounds $K(x)-K(n)$.

The implication (b) to (c) can be seen as follows: Note that for almost all
$n$ it holds that $C(n)<n$. So given $n$ sufficiently large, one considers the
string $x_{n}=(\\{C(n)\\}\\!\upharpoonright_{n})$; this string has plain
Kolmogorov complexity satisfying $C(x_{n})=^{+}C(n)$, let $c^{\prime}$ be such
that $C(x_{n})\leq C(n)+c^{\prime}$. Thus $K(x_{n})\leq K(n)+d^{\prime}$ for
all $n$ where $x_{n}$ is defined by condition (b). By [22, Theorem 2.2.26]
there are at most $O(2^{d^{\prime}})$ strings $y\in\\{0,1\\}^{n}$ with
$K(y)\leq K(n)+d^{\prime}$ and one can enumerate the first, the second,
$\ldots$, the $k$-th until $x_{n}$ comes up, let $k$ be the corresponding
sequence-number. Now $k\leq 2^{d^{\prime\prime}}$ for some constant
independent of $n$ and therefore $K(x_{n}|n,K(n))\leq^{+}d^{\prime\prime}$. As
one can compute $C(n)$ from $x_{n}$, there is a further constant
$c^{\prime\prime}$ with $K(C(n)|n,K(n))\leq c^{\prime\prime}$ for all $n$.

The implication (c) to (a) can be derived as in Theorem 5.7 (b): for a string
$x$ of length $n$ with $C(x)-C(n)\leq b$ one has $K(x|n,C(n))\leq^{+}2b$. Now
by condition (c) it holds that $K(C(n)|n,K(n))$ is bounded by a constant;
hence so is $K(x|n,K(n))\leq^{+}2\cdot(C(x)-C(n))$. This yields condition (a).
∎

If these conditions are true then the question whether all $C$-trivial
measures are $K$-trivial has an affirmative answer. To see this note that if
$\mu=\sum_{r}\alpha_{r}\cdot\delta_{A_{r}}$ is $C$-trivial then there is a
constant $b$ such that
$\sum_{r}\alpha_{r}\cdot(C(A_{r}\\!\upharpoonright_{n})-C(n))\leq b$ for all
$n$. It follows from Condition (a) that

$\displaystyle K(\mu\\!\upharpoonright_{n})$ $\displaystyle=$ $\displaystyle
K(n)+\sum_{r}\alpha_{r}\cdot(K(A_{r}\\!\upharpoonright_{n})-K(n))$
$\displaystyle\leq$ $\displaystyle
K(n)+\sum_{r}\alpha_{r}\cdot(2\cdot(C(A_{r}\\!\upharpoonright_{n})-C(n))+c)$
$\displaystyle\leq$ $\displaystyle
K(n)+c+2\cdot\sum_{r}\alpha_{r}\cdot(C(A_{r}\\!\upharpoonright_{n})-C(n))\leq
K(n)+2b+c.$

Strong $C$\- and strong $K$-triviality for measures.

Given the examples above we consider a strengthening of our notions.

######  Definition 5.9.

Call a measure $\mu$ strongly $C$-trivial if it can be written as a convex
combination $\sum_{s}\alpha_{s}\delta_{A_{s}}$ such that the $A_{s}$ are
$C$-trivial via constants $b_{s}$ such that $\sum_{s}\alpha_{s}\cdot b_{s}$ is
finite. Similarly, one defines strongly $K$-trivial measures.

######  Fact 5.10.

Every strongly $C$-trivial measure is $C$-trivial. Every strongly $K$-trivial
measure is $K$-trivial.

###### Proof.

By hypothesis $\mu=\sum_{s}\alpha_{s}\cdot\delta_{A_{s}}$ where each $A_{s}$
is $C$-trivial with constant $b_{s}$, and $\sum\alpha_{s}\cdot b_{s}<c$. For
all $n$ we have $C(\mu\\!\upharpoonright_{n})=\sum_{s}\alpha_{s}\cdot
C(A_{s}\\!\upharpoonright_{n})\leq\sum_{s}\alpha_{s}\cdot(C(n)+b_{s})\leq
C(n)+\sum_{s}\alpha_{s}\cdot b_{s}\leq C(n)+c$. The proof is analogous for
$K$. ∎

While we ignore whether every $C$-trivial measure is $K$-trivial, we show that
this implication holds for the strong versions of the two notions. For this we
prove a lemma about sets of interest on its own. Its proof owes to the proof
that each $C$-trivial is recursive (Chaitin [6], also see [22, Proof of Thm
5.2.20(i)]).

######  Lemma 5.11.

There is an absolute constant $d$ such that every set that is $C$-trivial via
a constant $b$ is $K$-trivial via the constant $2b+d$.

###### Proof.

As mentioned in the proof of Fact 5.6, there are only $O(b^{2}\cdot 2^{b})$
binary strings $x$ of length $n$ with $C(x)\leq C(n)+b$. Now one considers the
following recursively enumerable tree $T_{b}$ of binary strings: a string $x$
of length $n$ is in $T_{b}$ iff there is an $y$ extending $x$ of length
$2^{n+1}$ such that for all $m\leq 2^{n+1}$ it holds that
$C(y\\!\upharpoonright_{m})\leq\log(m)+b+1$.

Note that there is an $m$ with $2^{n}\leq m\leq 2^{n+1}$ such that $C(m)>n$.
Thus for that length $m$, there are only $O(b^{2}\cdot 2^{b})$ strings which
qualify and therefore, for length $n$, there are at most $O(b^{2}\cdot 2^{b})$
many strings in $T_{b}$. Furthermore, note that the membership in $T_{b}$ is
closed under prefixes and therefore $T_{b}$ is a recursively enumerable tree.

For each length $n$, one can enumerate from given $n,b$ the $O(b^{2}\cdot
2^{b})$ strings of that length in $T_{b}$. So one can describe these strings
by any description of $n$ plus prefix-free codes of size $2b+d$ which compute
the strings given $n,b$. Note that these codes just say “the first string of
length $n$ enumerated into $T_{b}$”, “the second string of length $n$
enumerated into $T_{b}$” and so on. As there are $O(2^{b}\cdot b^{2})$ of
these strings, one can represent them and $b$ in a prefix-free way with $2b$
plus constant bits. Thus they can be described in a prefix-free way with a
description of size $K(n)+2b+d$ where $d$ is a constant independent of $b,n$.
Hence $K(A\\!\upharpoonright_{n})\leq K(n)+2b+d$. ∎

######  Proposition 5.12.

Every strongly $C$-trivial measure is strongly $K$-trivial.

###### Proof.

Suppose that a measure $\mu$ is given as a convex combination
$\sum_{s}\alpha_{s}\cdot\delta_{A_{s}}$ where each $A_{s}$ has the
$C$-triviality constant $b_{s}$, and $\sum_{s}\alpha_{s}\cdot b_{s}$ is
finite. By the foregoing lemma every $A_{s}$ is $K$-trivial via the constant
$d+2b_{s}$. Clearly
$\sum_{s}\alpha_{s}\cdot(d+2b_{s})=d+2\cdot\sum_{s}\alpha_{s}b_{s}$ is finite.
So $\mu$ is strongly $K$-trivial. ∎

One might ask whether every $K$-trivial measure is strongly $K$-trivial, and
whether every $C$-trivial measure is strongly $C$-trivial. The answer to this
question is “no” as the following result shows.

######  Proposition 5.13.

There is a measure $\mu$ which is $C$-trivial and $K$-trivial but not strongly
$K$-trivial (and hence not strongly $C$-trivial).

###### Proof.

For each $n$, let $p_{n}$ be the descripikjtion of length up to $2^{n}$ for
the prefix-free universal machine which produces the longest output string of
form $0^{m_{n}}$; here recall that $m_{n}$ and $0^{m_{n}}$ are identified with
each other. Note that $K(p_{n})$ and $|p_{n}|$ are both approximately $2^{n}$.
Now one defines the sets $A_{n}=\\{m_{n}+k:1p_{n+1}$ has a $1$ at position
$k\\}$. The sets $A_{n}$ are uniformly limit recursive and the approximations
converge in time $m_{n+1}$ to $A_{n}$; furthermore, $\max(A_{n})\leq
m_{n}+2^{n+1}$. Every set $A_{n}$ is finite and thus $K$-trivial. Let
$\mu=\sum_{n}2^{-n-1}\cdot\delta_{A_{n}}$.

We show that $\mu$ is $K$-trivial. One sees that for
$\mu\\!\upharpoonright_{\ell}$ with $m_{n}\leq\ell<m_{n+1}$, $2^{-n-1}$ of the
mass is concentrated on $\emptyset\\!\upharpoonright_{\ell}$ and for
$h=0,1,\ldots,n$, $2^{-h-1}$ of the mass is concentrated on
$A_{h}\\!\upharpoonright_{\ell}$. For $h<n$, the string
$A_{h}\\!\upharpoonright_{\ell}$ can be computed from $h$ and $\ell$. Thus it
has prefix-free complexity $K(\ell)+O(\log(h))$ which contributes to the
average measure $K(\mu\\!\upharpoonright_{\ell})$ a term bounded by
$2^{-h-1}\cdot K(\ell)+2^{-h-1}\cdot 2\log(h)$. As the sum $2^{-h-1}\cdot
2\cdot\log(h)$ converges to a constant $c$, one can estimate the overall sum
as

$K(\ell)+c+2^{-n-1}\cdot(K(A_{n}\\!\upharpoonright_{\ell})-K(\ell)),$

and the latter is bounded by $K(\ell)+c+2$, as
$K(A_{n}\\!\upharpoonright_{\ell})\leq K(\ell)+2^{n+2}$. Thus $\mu$ is
$K$-trivial. By a similar argument, $\mu$ is $C$-trivial.

The $K$-triviality constant $b_{n}$ for $A_{n}$ is bounded from below by
$K(A_{n}\\!\upharpoonright_{m_{n}+2^{n+1}})-K(m_{n}+2^{n+1})$ and that term is
at least $2^{n}$, as $K(p_{n+1})=^{+}2^{n+1}$ and $K(m_{n})=^{+}2^{n}$. It
follows that $\sum_{n}2^{-n-1}b_{n}\geq\sum_{n}1/2=\infty$. Thus $\mu$ is not
strongly $K$-trivial. ∎

By the facts and propositions above, in Proposition 5.5 the condition that
$\Gamma$ be a truth-table reduction is necessary; downward closure of the
$K$-trivial measures does not hold for Turing reductions in general.

######  Proposition 5.14.

There are measures $\mu,\nu$ and a Turing reduction $\Gamma$ such that $\nu$
is strongly $K$-trivial, $\Gamma$ is defined on all the atoms of $\nu$ and
$\mu=\Gamma(\nu)$ is not $K$-trivial.

###### Proof.

Consider the set $\Omega\oplus\overline{\Omega}$, that is, the join of
$\Omega$ with its complment. This set is left-r.e. and initial segments of
length $2m$ have approximately complexity $m$. Now let

$A_{m}=\\{x\in\Omega\oplus\overline{\Omega}:x<2n_{m}\\}$

and $\gamma_{m}=\frac{1}{(m+1)\cdot(m+2)}=\frac{1}{m+1}-\frac{1}{m+2}$.
Furthermore, let $n_{m}$ be the least integer greater than $(m+2)^{3/2}$ and
let $k_{m}=\langle m,c_{\Omega}(n_{m})\rangle$ where $c_{\Omega}(n_{m})$ is
the time to follow the recursive left-enumeration of $\Omega$ until the first
$n_{m}$ bits are correct (and therefore remain correct from then on). Note
that $k_{m}$ can be computed from $A_{m}\\!\upharpoonright_{2n_{m}+2}$ and
$A_{m}\\!\upharpoonright_{2n_{m}+2}$ can be computed from $k_{m}$. Let
$B_{m}=\\{k_{m}\\}$ and $\nu=\sum_{m}\gamma_{m}\cdot\delta_{B_{m}}$ and
$\mu=\sum_{m}\gamma_{m}\cdot\delta_{A_{m}}$.

Note that for $\ell\geq k_{m}$, $k_{m}$ can be computed from $\ell$ and $m$,
as $\ell$ is an upper bound of $c_{\Omega}(n_{m})$; for $\ell<k_{m}$,
$B_{m}\\!\upharpoonright_{\ell}=0^{\ell}$. Thus the coding constant of $B_{m}$
is $2\log(m)$ plus some constant. As $\sum_{m}\gamma_{m}\cdot 2\cdot\log(m)$
is a convergent sum – almost all terms are bounded by $(m+2)^{-3/2}$ which is
a convergent sum – the measure $\nu$ is $K$-trivial by Fact 5.10. Actually it
is by definition even strongly $K$-trivial.

The measure $\mu$ is not $K$-trivial, as all $A_{k}$ with $k\geq m$ have the
common prefix $u=\Omega\oplus\overline{\Omega}\\!\upharpoonright_{2n_{m}}$ of
length $2n_{m}$ and that prefix has, for almost all $m$, the Kolmogorov
complexity $(m+2)^{3/2}$ or more. Note that
$\mu(\\{u\\}\times\\{0,1\\}^{{\mathbb{N}}})$ is at least $\frac{1}{m+2}$, so
this string contributes to the average $\mu\\!\upharpoonright_{2n_{m}}$ at
least $(m+2)^{1/2}$. Thus $\mu$ is not $K$-trivial, as the function $m\mapsto
K(2n_{m})$ cannot be bounded from below by any increasing unbounded recursive
function.

Now one defines a Turing functional $\Gamma$ that translates each $B_{m}$ to
$A_{m}$: the functional searches in the oracle $B_{m}$ for the first element
$x$ of $B_{m}$; as long as the oracle is not empty, such an element is found.
Then it determines the $m,s$ with $x=\langle m,s\rangle$ and computes the
corresponding entry in the set
$\\{x\in\Omega_{s}\oplus\overline{\Omega}_{s}:x<2n_{m}\\}$. In the case that
the oracle has the set $B_{m}$, the search gives $k_{m}$ and this Turing
reduction provides the set $A_{m}$. Thus $\Gamma$ has the desired properties.
Note that $\Gamma$ is undefined only on $\emptyset$, and the measure of
$\\{\emptyset\\}$ with respect to $\nu$ is $0$. ∎

While we know that every strongly $C$-trivial measure is strongly $K$-trivial,
we ignore whether every $C$-trivial measure is $K$-trivial. The converse
implication fails even for Dirac measures because each $C$-trivial sequence is
computable by the aforementioned result of Chaitin. We next show that this
failure of the converse implication can be witnessed by a strongly $K$-trivial
measure where all the atoms are recursive, and thus $C$-trivial (as
sequences).

######  Proposition 5.15.

There is a strongly $K$-trivial measure which is not $C$-trivial, and has only
recursive atoms.

###### Proof.

Let $A$ be an r.e. $K$-trivial set which is not $C$-trivial, that is, which is
not recursive. Let $a_{k,s}$be the least number $m\leq s$ such that either
$m=s$ or $C_{s}(A_{s}\\!\upharpoonright_{m})\geq C_{s}(m)+4^{k}$; as $A$ is
not $C$-trivial, each $a_{k,s}$ converges to $a_{k}$, the least value $m$
satisfying $C(A\\!\upharpoonright_{m})\geq C(m)+4^{k}$; note that from some
stage on, $A_{s}$ and $C_{s}$ have converged up to $a_{k}$ and from then
onwards $a_{k,s}=a_{k}$; thus for each $k$ the sequence of the $a_{k,s}$ is
uniformly recrusive and converges to $a_{k}$.

One next defines a sequence $b_{k,s}$ such that $b_{k,0}=0$ and
$b_{k,s+1}\in\\{b_{k,s},s+1\\}$ where the value $s+1$ is taken if either
$a_{k,s}\not\leq b_{k,s}$ or there is $h<k$ with $b_{h,s}=b_{k,s}$. Note that
the definition of these values implies that $a_{k,s}\leq a_{h,s}$ and
$b_{k,s}\leq b_{h,s}$ whenever $k\leq h$.

Now let $A_{k}=\\{a\in A:a<b_{k}\\}$. The set $A_{k}$ has the $K$-triviality
constant $2\log(k)$, as $A_{k}$ below $b_{k}$ equals the fixed $K$-trivial set
$A$ and for $s\geq b_{k}$, if one knows $k$ then one can compute
$b_{k}=b_{k,s}$ and $A_{k}\\!\upharpoonright_{s}$ can then be computed from
$k$ and $A\\!\upharpoonright_{s}$, as $s$ is the length of
$A\\!\upharpoonright_{s}$.

Having these ingredients, one chooses
$\mu=\sum_{k}2^{-k-1}\cdot\delta_{A_{k}}$. This measure is strongly
$K$-trivial by Fact 5.10, since the sum over $2^{-k-1}\cdot 2\log(k)$
converges. However, $\mu$ is not $C$-trivial, as
$\mu\\!\upharpoonright_{a_{k}}$ satisfies for $h\geq k$ that
$A_{h}\\!\upharpoonright_{a_{k}}=A\\!\upharpoonright_{a_{k}}$ and

$C(\mu\\!\upharpoonright_{a_{k}})\geq
C(a_{k})+2^{-k}\cdot(C(A\\!\upharpoonright_{a_{k}})-C(a_{k}))\geq
C(a_{k})+2^{k},$

and the values $2^{k}$ are obviously not bounded by a constant. ∎

##  6\. Full Martin-Löf randomness of measures

Let $\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$ be the space of probability
measures on Cantor space (which is canonically a compact topological space).
Probability measures on this space have been defined by Mauldin and Monticino
[16]. A special case it the uniform measure $\mathbb{P}$ on
$\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$.

To define $\mathbb{P}$, first let $\mathcal{R}$ be the closed set of
representations of probability measures; namely, $\mathcal{R}$ consists of the
functions $X\colon\\{0,1\\}^{*}\to[0,1]$ such that $X_{\emptyset}=1$ and
$X_{\sigma}=X_{\sigma 0}+X_{\sigma 1}$ for each string $\sigma$. $\mathbb{P}$
is the unique measure on $\mathcal{R}$ such that for each string $\sigma$ and
$r,s\in[0,1]$, we have $\mathbb{P}(X_{\sigma 0}\leq r\mid
X_{\sigma}=s)=\min(1,r/s)$. Intuitively, we choose $X_{\sigma 0}$ at random
w.r.t. the uniformly distribution on the interval $[0,X_{\sigma}]$, and the
choices made at different strings are independent. In the language of [16],
the transition kernel $\tau$ takes the value $\mathbf{\lambda}$ for each
dyadic rational (corresponding to a string $\sigma$).

We remark that for $n>0$ and a string $\sigma$ of length $n$, the function
$v_{n}$ on $[0,1]$ given by $x\to\mathbb{P}(\\{\mu[\sigma]\leq x\\})$ only
depends on $n=|\sigma|$. In fact, the $v_{n}$ are given by the recursion
$v_{1}(x)=x$ and $v_{n+1}(x)=x+\int_{x}^{1}v_{n}(x/t)dt$. E.g.,
$v_{2}(x)=x(1-\ln x)$.

Culver’s thesis [7] shows that this measure is computable in the sense of
Hoyrup and Rojas [11]. So the framework provided in [11] yields a notion of
Martin-Löf randomness for points in the space
$\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$.

######  Proposition 6.1.

Every probability measure $\mu$ that is Martin-Löf random wrt $\mathbb{P}$ is
Martin-Löf absolutely continuous.

For the duration of this proof let $\mu$ range over
${\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})}$. For an open set
$G\subseteq\\{0,1\\}^{{\mathbb{N}}}$, let

$r_{G}=\int\mu(G)d\mathbb{P}(\mu).$

Our proof of Proposition 6.1 is based on two facts.

######  Fact 6.2.

$r_{G}=\mathbf{\lambda}(G)$.

###### Proof.

Clearly, for each $n$ we have

$\sum_{|\sigma|=n}r_{[\sigma]}=\int\sum_{|\sigma|=n}\mu([\sigma])d\mathbb{P}(\mu)=1.$

Furthermore, $r_{\sigma}=r_{\eta}$ whenever $|\sigma|=|\eta|=n$ because by the
remark above there is a $\mathbb{P}$-preserving transformation $T$ of
$\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$ such that
$\mu([\sigma])=T(\mu)([\eta])$. Therefore $r_{[\sigma]}=2^{-|\sigma|}$.

If $\sigma,\eta$ are incompatible then
$r_{[\sigma]\cup[\eta]}=r_{[\sigma]}+r_{[\eta]}$. Now it suffices to write
$G=\bigcup_{i}[\sigma_{i}]$ where the strings $\sigma_{i}$ are incompatible,
so that $\mathbf{\lambda}G=\sum_{i}2^{-|\sigma_{i}|}$. ∎

######  Fact 6.3.

Let $\mu\in\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$ and let
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ be a Martin-Löf-test
such that there is $\delta\in{\mathbb{Q}}^{+}$ with $\forall
m\,[\mu(G_{m})>\delta]$. Then $\mu$ is not Martin-Löf-random w.r.t.
$\mathbb{P}$.

###### Proof.

Observe that by the foregoing fact

$\delta\cdot\mathbb{P}(\\{\mu\colon\mu(G_{m})\geq\delta\\})\leq\int\mu(G_{m})d\mathbb{P}(\mu)=\mathbf{\lambda}(G_{m})\leq
2^{-m}.$

Let $\mathcal{G}_{m}=\\{\mu\colon\mu(G_{m})>\delta\\}$ which is uniformly
effectively open in the space of measures
$\mathcal{M}(\\{0,1\\}^{{\mathbb{N}}})$. Fix $k$ such that $2^{-k}\leq\delta$.
By the inequality above, we have $\mathbb{P}(\mathcal{G}_{m})\leq
2^{-m}/\delta\leq 2^{-m+k}$. Hence
${\left\langle{\mathcal{G}_{m+k}}\right\rangle}_{m\in{\mathbb{N}}}$ is a
Martin-Löf-test w.r.t. $\mathbb{P}$ that succeeds on $\mu$. ∎

This argument also works for randomness notions stronger than Martin-Löf’s.
For instance, if there is a weak-2 test
${\left\langle{G_{m}}\right\rangle}_{m\in{\mathbb{N}}}$ such that $\mu
G_{m}>\delta$ for each $m$, then $\mu$ is not weakly 2-random with respect to
$\mathbb{P}$. The converse of Proposition 6.1 fails. Culver [7] shows that
each measure $\mu$ that is Martin-Löf-random w.r.t. $\mathbb{P}$ is non-
atomic. So a measure $\delta_{Z}$ for a Martin-Löf-random bit sequences $Z$ is
ML absolutely continuous but not Martin-Löf-random with respect to
$\mathbb{P}$.

##  7\. Being ML-a.c. relative to computable ergodic measures

We review some notions from the field of symbolic dynamics, a mathematical
area closely related to Shannon information theory. See See e.g. [32] for more
detail. Thereafter we will consider effective “almost-everywhere theorems”
related to that area in the framework of randomness for measures.

In symbolic dynamics it can be useful to admit alphabets other than the binary
one. Let $\mathbb{A}^{\infty}$ denote the topological space of one-sided
infinite sequences of symbols in an alphabet $\mathbb{A}$. Randomness notions
etc. carry over from the case of $\mathbb{A}=\\{0,1\\}$. A dynamics on
$\mathbb{A}^{\infty}$ is given by the shift operator $T$, which erases the
first symbol of a sequence. A measure $\rho$ on $\mathbb{A}^{\infty}$ is
called _shift invariant_ if $\rho(G)=\rho(T^{-1}(G))$ for each open (and hence
each measurable) set $G$. The _empirical entropy_ of a measure $\rho$ along
$Z\in\mathbb{A}^{\infty}$ is given by the sequence of random variables

$h^{\rho}_{n}(Z)=-\frac{1}{n}\log_{|\mathbb{A}|}\rho[Z\\!\upharpoonright_{n}].$

A shift invariant measure $\rho$ on $\mathbb{A}^{\infty}$ is called _ergodic_
if every $\rho$ integrable function $f$ with $f\circ T=f$ is constant
$\rho$-almost surely. The following equivalent condition can be easier to
check: for any strings $u,v\in\mathbb{A}^{*}$,

$\lim_{N}\frac{1}{N}\sum_{k=0}^{n-1}\rho([u]\cap T^{-k}[v])=\rho[u]\rho[v].$

For ergodic $\rho$, the entropy $H(\rho)$ is defined as $\lim_{n}H_{n}(\rho)$,
where

$H_{n}(\rho)=-\frac{1}{n}\sum_{|w|=n}\rho[w]\log\rho[w].$

Thus, $H_{n}(\rho)=\mathbb{E}_{\rho}h^{\rho}_{n}$ is the expected value with
respect to $\rho$. by concavity of the logarithm function the limit exists and
equals the infimum of the sequence. This limit is denoted $H(\rho)$, the
entropy of $\rho$.

A well-known result from the 1950s due to Shannon, McMillan and Breiman states
that for an ergodic measure $\rho$, for $\rho$-a.e. $Z$ the empirical entropy
along $Z$ converges to the entropy of the measure. See e.g. [32, Chapter 1],
but note that the result is called the Entropy Theorem there.

######  Theorem 7.1 (SMB theorem).

Let $\rho$ be an ergodic measure on the space $\mathbb{A}^{\infty}$. For
$\rho$-almost every $Z$ we have $\lim_{n}h^{\rho}_{n}(Z)=H(\rho)$.

Recall from Fact 2.4 that a measure $\mu$ is _ML absolutely continuous with
respect to $\rho$_ iff $\mu(\mathcal{C})=0$ where $\mathcal{C}$ is the class
of sequences in $\mathbb{A}^{\infty}$ that are not Martin-Löf-random with
respect to $\rho$.

If a computable measure $\rho$ is shift invariant, then
$\lim_{n}h^{\rho}_{n}(Z)$ exists for each $\rho$-Martin-Löf-random $Z$ by a
result of Hochman [9]. Hoyrup [10, Theorem 1.2] gave an alternative proof for
ergodic $\rho$, and also showed that in that case we have
$\lim_{n}h^{\rho}_{n}(Z)=H(\rho)$ for each $\rho$-ML-random $Z$. We extend
this result to measures $\mu$ that are ML absolutely continuous with respect
to $\rho$, under the additional hypothesis that the $h_{n}^{\rho}$ are
uniformly bounded. This holds e.g. for Bernoulli measures and the measures
given by a Markov process.

######  Proposition 7.2.

Let $\rho$ be a computable ergodic measure on the space $\mathbb{A}^{\infty}$
such that for some constant $D$, each $h_{n}^{\rho}$ is bounded above by $D$.
Suppose the measure $\mu$ is ML absolutely continuous with respect to $\rho$.
Write $s=H(\rho)$. We have $\lim_{n}E_{\mu}|h^{\rho}_{n}-s|=0$.

###### Proof.

By Hoyrup’s result, $\lim_{n}h^{\rho}_{n}(Z)=s$ for each $\rho$-ML-random $Z$.
Since the sequences that are not Martin-Löf-random w.r.t. $\rho$ form a null
set w.r.t. $\mu$, we infer that $\lim_{n}|h^{\rho}_{n}(Z)-s|=0$ for $\mu$-a.e.
$Z$. Since the exception set is measurable and the $h_{n}\rho$ are bounded,
the Dominated Convergence Theorem now shows that
$\lim_{n}\mathbb{E}_{\mu}|h_{n}^{\rho}-s|=0$, as required. ∎

We now given an example showing that the boundedness hypothesis on the
$h_{n}^{\rho}$ is necessary. We provide a computable ergodic measure $\rho$
such that some finite measure $\mu\ll\rho$ makes the sequence
$E_{\mu}h_{n}^{\rho}$ converge to $\infty$.

######  Proposition 7.3.

There is an ergodic computable measure $\rho$ (associated to a binary renewal
process) and a computable measure $\mu\ll\rho$ such that
$\lim_{n}\mathbb{E}_{\mu}h^{\rho}_{n}=\infty$. (We can then normalise $\mu$ to
become a probability measure, while maintaining the same conclusion.)

###### Proof.

Let $k$ range over positive natural numbers. The real $c=\sum_{k}2^{-k^{4}}$
is computable. Let $p_{k}=2^{-k^{4}}/c$ so that $\sum p_{k}=1$. Let
$b=\sum_{k}k\cdot p_{k}$ which is also computable.

Let $\rho$ be the measure associated with the corresponding binary renewal
process, which is given by the conditions

$\rho[Z_{0}=1]=1/b$ and $\rho(10^{k}1\prec Z\mid Z_{0}=1)=p_{k}$.

Informally, the process has initial value $1$ with probability $1/b$, and
after each $1$, with probability $p_{k}$ it takes $k$ many 0s until it reaches
the next 1. See again e.g. [32, Chapter 1] where it is shown that $\rho$ is
ergodic. Write $v_{k}=10^{k}1$. Note that $\rho[v_{k}]=p_{k}/b$.

Define a function $f$ in $L_{1}(\rho)$ by $f(v_{k}\hat{\ }Z)=k^{-2}/p_{k}$ and
$f(X)=0$ for any $X$ not extending any $v_{k}$. It is clear that $f$ is
$L_{1}(\rho)$-computable, in the usual sense that there is an effective
sequence of basic functions ${\left\langle{f_{n}}\right\rangle}$ converging
effectively to $f$: let $f_{n}(X)=f(X)$ in case $v_{k}\prec X$, $k\leq n$, and
$f_{n}(X)=0$ otherwise. Define the measure $\mu$ by $d\mu=fd\rho$, i.e.
$\mu(A)=\int_{A}fd\rho$. Thus $\mu[v_{k}]=k^{-2}/b$. Since $\rho$ is
computable and $f$ is $L_{1}(\rho)$-computable, $\mu$ is computable. Also note
that $\mu(\\{0,1\\}^{{\mathbb{N}}})=\int fd\rho$ is finite.

For any $n>2$, letting $k=n-2$, we have

$E_{\mu}h_{n}^{\rho}\geq-\frac{1}{n}\mu[v_{k}]\log\rho[v_{k}]=-\frac{1}{nk^{2}b}(k^{4}-bc)\geq\frac{k^{2}}{nb}-O(1).$

This completes the proof. ∎

The next observation shows that the asymptotic initial segment complexity of a
ML absolutely continuous measure relative to $\rho$ obeys some lower bound.
Note that $H(\mathbf{\lambda})=1$. So for $\rho=\mathbf{\lambda}$, this shows
that in Example 4.1 we cannot subtract, say, $n/4$ instead of $n^{\theta}$.

######  Proposition 7.4.

Let $\rho$ be a computable ergodic measure, and suppose $\mu$ is a ML
absolutely continuous measure with respect to $\rho$. Then

$\lim_{n}\frac{1}{n}K(\mu\\!\upharpoonright_{n})=\lim_{n}\frac{1}{n}C(\mu\\!\upharpoonright_{n})=H(\rho).$

###### Proof.

We can use $K$ and $C$ interchangeably because
$C(x)\leq^{+}K(x)\leq^{+}C(x)+K(C(x))$ [22, Proposition 2.4.1]. We settle on
$K$.

Let $k_{n}(Z)=K(Z\\!\upharpoonright_{n})/n$. The argument is very similar to
the one in Proposition 7.2 above, replacing the functions $h_{n}$ by the
$k_{n}$. Note that $k_{n}$ is bounded above by a constant because
$K(x)\leq^{+}|x|+2\log|x|$. Hoyrup’s result [10, Theorem 1.2] states that
$\lim_{n}k_{n}(Z)=H(\rho)$ for each $\rho$-ML-random $Z$. Now we can apply the
Dominated Convergence Theorem as in the proof of Proposition 7.2. ∎

##  8\. Conclusions and open questions

In the present paper, we studied algorithmic randomness, and triviality
properties for probability measures on Cantor space.

A main property we studied was that a measure $\mu$ is ML absolutely
continuous: for every Martin-Löf test the $\mu$-measure of its components
converges to $0$. We provided several examples and showed a robustness
property related to Solovay tests. In Section 4.2 we introduced strong Solovay
tests for measures. We leave the following question open.

######  Question 8.1.

Does every measure that passes every _strong_ Solovay test, pass every Solovay
test?

Thereafter, we studied growth behaviour of the $\mu$-averages of the
descriptive string complexities $C(x)$ and $K(x)$ over strings $x$ of length
$n$. We asked what can be said for measures where the growth is as slow as
possible and for those where it is as fast as possible. We looked at $C$\- and
at $K$-trivial measures, where the averages are bounded up to a constant by
$C(n)$ or $K(n)$, respectively. Such measures are atomic, that is, they are
weighted, possibly infinite sums of Dirac measures. The atoms of such measure
satisfy the corresponding triviality property; furthermore, the weighted sum
of the atoms has to converge fast, though we could not find a precise
criterion for this. In this context, we mention two open questions.

######  Question 8.2.

Is every $C$-trivial measure also $K$-trivial?

An affirmative answer to the next question would lead to an affirmative answer
to Question 8.2; Proposition 5.8 provided more detail.

######  Question 8.3.

Is there a constant bound on the function $n\mapsto K(C(n)|n,K(n))$?

Measures $\mu$ on the upper end of the growth spectrum are ML absolutely
continuous. However, we showed that also here there is no exact correspondence
between the growth-rate of the $\mu$ averages of the string complexity and the
property of being ML absolutely continuous; instead, in the border area, there
are measures that are smaller with respect to the growth-rate of the averages
which are ML absolutely continuous and measures that are larger but which are
not. In particular, an analogue of the Levin-Schnorr Theorem does not hold for
measures. We noted that near the upper end of the growth spectrum for $C$ are
the Kolmogorov random measures $\mu$: there is a constant $d$ with
$C(\mu\\!\upharpoonright_{n})\geq n-d$ for infinitely many $n$. Besides the
usual uniform measure, there are other examples, such as Dirac measure of sets
which are 2-random. While $C$-trivial and $K$-trivial measures are closed
under finite convex combinations, this is not known for the measures on the
upper end of the growth spectrum.

######  Question 8.4.

Assume that measure $\mu,\nu$ are Kolmogorov random. Is every convex
combination of $\mu$ and $\nu$ Kolmogorov random as well?

As mentioned in Section 3, a sequence $X$ is 2-random iff it is Kolmogorov
randomness as defined in [14]). So an affirmative answer to the question above
implies an affirmative answer to the following:

######  Question 8.5.

If $X,Y\in\\{0,1\\}^{{\mathbb{N}}}$ are both 2-random, does there exist a
constant $d$ such that infinitely many $n$ satisfy both
$C(X\\!\upharpoonright_{n})\geq n-d$ and $C(Y\\!\upharpoonright_{n})\geq n-d$?

Besides the trivial case when $X=Y$, this also holds if $X\oplus Y$ is
2-random. This can be seen using that 2-randomness coincides with Kolmogorov
randomness. Clearly for strings $x,y$ of length $n$ one has $C(x\oplus
y)\leq^{+}C(x)+n$: on input $\tau$ a plain machine $M$ searches for a
decomposition $\tau=\sigma\hat{\ }y$ such that the universal plain machine on
input $\sigma$ outputs a string $x$ of the same length as $y$; then $M$
outputs $x\oplus y$. So if $C(X\oplus Y\\!\upharpoonright_{2n})\geq^{+}2n$ for
infinitely many $n$, then $C(X\\!\upharpoonright_{n})\geq^{+}n$ for the same
witnesses $n$. By symmetry, also $C(Y\\!\upharpoonright_{n})\geq^{+}n$ for the
same witnesses $n$.

The following diagram summarizes the implications obtained between (weak)
randomness notions for measures. Non-labelled implication arrows are trivial.
We ignore at present whether the implications given by the arrows labelled 3.5
and 3.2 are proper. All the other implication arrows are proper. In most cases
this can be seen already for Dirac measures. For instance, full Martin-Löf
randomness of a measure implies that the measure has no atoms, so the converse
of the implication labeled Prop. 6.1 fails. We can rule out two further
implications. Each fully ML-random $\mu$ is orthogonal to $\mathbf{\lambda}$
by Bienvenu and Culver [7, Section 2.6], and hence not absolutely continuous.
We ignore whether full ML-randomness implies one of the condition stronger
than ML-a.c. displayed in the lower part of the diagram.

$\textstyle{\mu\text{ is abs.\
continuous}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mu\text{
is fully ML random }\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Prop. 6.1$\textstyle{\mu\text{ is ML
a.c.}}$$\textstyle{\exists^{\infty}n\,K(\mu\\!\upharpoonright_{n})\geq^{+}n+K(n)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
3.5$\textstyle{\exists^{\infty}n\,C(\mu\\!\upharpoonright_{n})\geq^{+}n\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Thm. 3.6$\textstyle{\forall
n\,K(\mu\\!\upharpoonright_{n})\geq^{+}n+K(n)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
3.2$\textstyle{\forall
n\,C(\mu\\!\upharpoonright_{n})\geq^{+}n\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

In Section 7 we considered weak randomness relative to a general ergodic
computable measure. We proved appropriate effective versions of the Shannon-
McMillan-Breiman theorem and the Brudno theorem where the bit sequences are
replaced by measures; the former needed an additional boundedness hypothesis.

One possible effective version of the Birkhoff ergodic theorem states that for
an ergodic computable $\rho$, if $f\\{0,1\\}^{{\mathbb{N}}}\to{\mathbb{R}}$ is
$\rho$-integrable and lower semicomputable and $Z$ is $\rho$-Martin-Löf-
random, then the limit of the usual ergodic averages
$A_{n}f(Z)=\frac{1}{n}\sum_{k<n}(f\circ T^{k})(Z)$ equals $\int fd\rho$. For
background see e.g. [21] which contains references to original work. If in
addition the $A_{n}f$ are bounded then an argument similar to the one in the
proof of Proposition 7.2 shows that $\lim_{n}\int(A_{n}f)d\mu=\int fd\rho$ for
any measure $\mu\ll_{ML}\rho$. However, it is unknown whether this additional
hypothesis is necessary.

Acknowledgements. The authors would like to thank the anonymous referees of
STACS 2020 for useful suggestions. Furthermore, they would like to thank
Benjamin Weiss and Bruno Bauwens for helpful correspondence.

Some problems from this paper were presented at the 2020 AIM workshop on
randomness and applications, for instance Question 8.3. The authors thank the
participants, in particular J. Miller, S. Shen and E. Mayordomo, for their
interest and useful comments.

## References

  * [1] Bruno Bauwens.  Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity.  PhD Thesis, Universiteit Gent, Faculteit Ingenieurswetenschappen, February 2010. https://biblio.ugent.be/publication/1107852/file/4335294
  * [2] Bruno Bauwens.  Relating and contrasting plain and prefix Kolmogorov complexity.  Theory of Computing Systems, 58(3):482–501, 2016.
  * [3] Laurent Bienvenu, Wolfgang Merkle and Alexander Shen.  A simple proof of the Miller-Yu Theorem.  Fundamenta Informaticae, 83(1-2):21–24, 2008.
  * [4] Cristian S. Calude.  Information and Randomness - An Algorithmic Perspective. Second Edition, Springer, Heidelberg, 2002.
  * [5] Gregory J. Chaitin.  A theory of program size formally identical to information theory.  Journal of the Association for Computing Machinery, 22:329-340, 1975.
  * [6] Gregory J. Chaitin.  Information-theoretical characterizations of recursive infinite strings.  Theoretical Computer Science, 2:45–48, 1976.
  * [7] Quinn Culver.  Topics in Algorithmic Randomness and Effective Probability.  PhD thesis, University of Notre Dame, 2015.
  * [8] Rodney G. Downey and Denis Hirschfeldt.  Algorithmic Randomness and Complexity.  Springer-Verlag, Berlin, 2010.  855 pages.
  * [9] Michael Hochman.  Upcrossing inequalities for stationary sequences and applications.  Annals of Probability, 37(6):2135–2149, 2009.
  * [10] Mathieu Hoyrup.  The dimension of ergodic random sequences.  In Christoph Dürr and Thomas Wilke, editors, STACS 2012, pages 567–576, 2012.
  * [11] Mathieu Hoyrup and Cristóbal Rojas.  Computability of probability measures and Martin-Löf randomness over metric spaces.  Information and Computation, 207(7):830–847, 2009.
  * [12] Steven M. Kautz, Degrees of random sets, PhD thesis, Cornell University, August 1991.
  * [13] Leonid A. Levin.  The concept of a random sequence.  Doklady Akademii Nauk SSSR, 212:548–550, 1973.
  * [14] Ming Li and Paul Vitányi.  An Introduction to Kolmogorov Complexity and its Applications.  Texts in Computer Science. Springer, New York, third edition, 2008.
  * [15] Per Martin-Löf.  The definition of random sequences.  Information and Control, 9:602–619, 1966.
  * [16] Daniel Mauldin and Michael Monticino.  Randomly generated distributions.  Israel Journal of Mathematics, 91(1-3):215–237, 1995.
  * [17] Joeseph S. Miller.  The $K$-degrees, low for $K$-degrees, and weakly low for $K$ sets.  Notre Dame Journal of Formal Logic, 50(4):381–391, 2009.
  * [18] Joseph S. Miller.  Contrasting plain and prefix-free Kolmogorov complexity.  Research Note on the author’s homepage.
  * [19] Joseph S. Miller and Liang Yu.  On initial segment complexity and degrees of randomness.  Transactions of the American Mathematical Society, 360:3193–3210, 2008.
  * [20] Joseph S. Miller and Liang Yu.  Oscillation in the initial segment complexity of random reals.  Advances in Mathematics, 226(6):4816–4840, 2011.
  * [21] Kenshi Miyabe, André Nies and Jing Zhang.  Using almost-everywhere theorems from analysis to study randomness.  Bull. Symb. Logic, 22:305–331, 2016.
  * [22] André Nies.  Computability and Randomness, volume 51 of Oxford Logic Guides.  Oxford University Press, Oxford, 2009.  444 pages. Paperback version 2011.
  * [23] André Nies (editor).  Logic Blog 2017.  Available at http://arxiv.org/abs/1804.05331, 2017.
  * [24] André Nies and Volkher Scholz.  Martin-Löf random quantum states.  Journal of Mathematical Physics, 60(9):092201, 2019.  available at doi.org/10.1063/1.5094660.
  * [25] André Nies, Frank Stephan and Sebastiaan Terwijn.  Randomness, relativization and Turing degrees.  The Journal of Symbolic Logic, 70(2):515–535, 2005.
  * [26] André Nies and Frank Stephan.  Randomness and Initial Segment Complexity for Probability Measures.  In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:14, Dagstuhl, Germany, 2020.
  * [27] Piergiorgio Odifreddi.  Classical Recursion Theory.  North-Holland, Amsterdam, 1989.
  * [28] Piergiorgio Odifreddi.  Classical Recursion Theory, Volume II.  Elsevier, Amsterdam, 1999.
  * [29] Christopher P. Porter.  Trivial measures are not so trivial.  Theory of Computing Systems, 56(3):487–512, 2015.
  * [30] Claus-Peter Schnorr.  Process complexity and effective random tests.  Journal on Computer and System Sciences, 7:376–388, 1973.
  * [31] Claus-Peter Schnorr.  A survey of the theory of random sequences.  Basic Problems in Methodology and Linguistics,  (Proceedings of the Fifth International Congress on Logic, Methodology and Philosophy of Science, Part III, University Western Ontario, London, Ontario, 1975), University Western Ontario Series Philosophy of Science, volume 11, pages 193–211. Reidel, Dordrecht, 1977.
  * [32] Paul C. Shields.  The Ergodic Theory of Discrete Sample Paths.  Graduate Studies in Mathematics 13. American Mathematical Society, 1996\.
  * [33] Robert I. Soare.  Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets.  Springer, Heidelberg, 1987.
  * [34] Robert Solovay.  Handwritten manuscript related to Chaitin’s work.  IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975\.
  * [35] Frank Stephan.  Recrsuion Theory. Lecture notes, School of Computing, National University of Singapore, Technical Report TR10/12, 2012.