On the (dis)similarities between stationary imprecise and non-stationary
precise uncertainty models in algorithmic randomness
Floris Persiau, Jasper De Bock, Gert de Cooman

Ghent University, Foundations Lab for imprecise probabilities,
Technologiepark–Zwijnaarde 125, 9052 Zwijnaarde, Belgium

Abstract
The field of algorithmic randomness studies, amongst other things, what it
means for infinite binary sequences to be random for some given uncertainty
model. Classically, martingale-theoretic notions of randomness involve precise
uncertainty models, and it is only recently that imprecision has been
introduced into this context. As a consequence, the investigation into how
imprecision alters our view on martingale-theoretic random sequences has only
just begun. In this contribution, where we allow for non-computable
uncertainty models, we establish a close and surprising connection between
precise and imprecise uncertainty models in this randomness context. In
particular, we show that there are stationary imprecise models and non-
computable non-stationary precise models that have the exact same set of
random sequences. We also give a preliminary discussion of the possible
implications of our result for a statistics based on imprecise probabilities,
and shed some light on the practical (ir)relevance of both imprecise and non-
computable precise uncertainty models in that context.

Keywords: algorithmic randomness, imprecise probabilities, computability
theory, probability intervals, supermartingales, non-stationarity

##  1 Introduction

What does it mean for an infinite binary sequence, such as $011001100\cdots$,
to be random? This is a highly non-trivial question that has led to numerous
investigations. First of all, it is important to realise that randomness is
typically defined with respect to some uncertainty model. So, our opening
question only makes sense once such a model has been specified. Uncertainty
models can be stationary or non-stationary, computable or non-computable, as
well as precise or imprecise [1, 2, 3, 4, 5, 6, 7, 8]. It is between the non-
computable non-stationary precise and the stationary imprecise uncertainty
models that we will reveal a remarkably close connection: we will show that
for every stationary imprecise model there are non-computable non-stationary
precise models that have the exact same set of random sequences.

The earliest notions of randomness only considered precise probability models
that assign a probability $p\in[0,1]$ to the outcome $1$. For instance, in
1919 Von Mises suggested considering an infinite binary sequence to be random
for $p$ if the relative frequencies of ones along the sequence, and along all
infinite subsequences selected by selection rules, converge to $p$ [9]. In
1939, Wald proved that for any $p\in(0,1)$, such random sequences do exist if
we restrict our attention to a countable set of selection rules [10, 11]. This
result, however, left open which countable set to consider. In 1940, based on
Wald’s work, Church suggested adopting the countable set of computable
selection rules [10, 12]; an infinite binary sequence is then Church random
for $p$ if the relative frequency of ones along every computably selectable
infinite subsequence converges to $p$, where ‘computably selectable’
essentially means that there is some finite algorithm that decides which
elements to keep and which to discard.

However, there are infinite sequences that satisfy this requirement, but for
which the running frequency of ones along the sequence converges to $p$ from
below. Such sequences disobey the law of the iterated logarithm. For this
reason, Jean Ville criticised this type of randomness definition, and argued
that besides the law of large numbers, a random sequence also ought to satisfy
other statistical laws [10]. Arguments of this kind led to the development of
many other randomness notions. Some of the most well-known and well-studied
amongst these are Martin-Löf randomness, computable randomness and Schnorr
randomness [13, 14]. The reason for this is twofold: they have an intuitive
interpretation and they can be defined in several equivalent ways [15, 8].
From a measure-theoretic point of view, for example, an infinite binary
sequence is random for a computable real $p\in[0,1]$ if it passes all
implementable statistical tests that are associated with $p$. On the other
hand, if we adopt the martingale-theoretic approach, then a sequence is random
for a computable $p$ if there is no implementable betting strategy for getting
arbitrarily rich along this sequence without borrowing, where the bets that
are allowed are determined by $p$, where the betting strategy specifies the
possible accumulated capital in the betting game, and where the meaning of
‘implementable’ depends on the notion of randomness at hand; for instance, in
the case of computable randomness, ‘implementable’ means that there is a
finite algorithm that yields the strategy.

There is more to randomness, however, than the simple case of a single
computable probability $p$. As mentioned above, more general uncertainty
models, such as non-stationary precise ones or imprecise ones, can also be
used to define notions of randomness [4, 7, 5, 6]; these models need not
necessarily be computable either. In a measure-theoretic context, most of the
classical approaches impose computability [13, 14, 8], but non-computable
uncertainty models have been studied too. One approach, for example, is to
consider the implementable statistical tests that are associated with a non-
computable measure, but that do not access it as a resource; this notion of
randomness is known as _Hippocratic_ or _Blind randomness_ [16, 17, 7].
Another measure-theoretic notion of randomness that allows for non-computable
uncertainty models was put forward by Levin in 1973 and is nowadays known as
_uniform randomness_ [5, 6, 7]. This notion of uniform randomness also allows
for imprecision by considering so-called ‘effectively compact classes of
probability measures’; in particular, there are tests such that a sequence
passes this test if and only if it is uniformly random with respect to some
probability measure in the considered class.

In the context of this paper, however, we focus on the martingale-theoretic
approach to randomness, for which imprecise-probabilistic uncertainty models
have been considered only recently. To be more precise, in the past few years,
De Cooman and De Bock put forward a martingale-theoretic approach that
associates (weak) Martin-Löf, computable and Schnorr randomness with imprecise
rather than precise probability models [1, 2, 3]. These imprecise models take
the form of so-called forecasting systems, and need not be computable. This
recent work still leaves room for many open questions on how allowing for
imprecision (and letting go of computable uncertainty models) changes our
understanding of random sequences. In the present paper, we try and contribute
to this understanding by proving a remarkable relation between randomness for
precise and imprecise probability models. In particular, for every non-
vanishing closed interval $I\subseteq[0,1]$ and each of the above-mentioned
four martingale-theoretic notions of randomness, we will show that there is a
non-stationary precise but then necessarily non-computable uncertainty model
for which the set of random paths is the same as for $I$. So, for the results
in this paper, allowing for non-computable uncertainty models is of crucial
importance. We leave aside whether using non-computable uncertainty models in
algorithmic randomness is defensible on philosophical or theoretical grounds;
we simply let go of the classical computability restriction on uncertainty
models, and investigate what happens if we do so. Nevertheless, in our
conclusions, we do argue why computable uncertainty models are to be favoured
on practical grounds.

Our contribution is structured as follows. Sections 2–4 provide a short
overview of relevant earlier work. We start by introducing interval forecasts
and the associated coherent upper expectations in Section 2, where we also
explain how their interpretation leads to a convex cone of gambles that a
subject is willing to offer. Section 3 explains how to bet on a single
variable in a way that agrees with an interval forecast, and extends this idea
to a betting game/protocol on an infinite sequence of variables by defining
betting strategies—which are basically supermartingales—that again agree with
such interval forecasts, and that avoid borrowing. After clarifying in Section
4 when such betting strategies are implementable, we present in Section 5 the
imprecise-probabilistic martingale-theoretic notions of (weak) Martin-Löf,
computable and Schnorr randomness introduced in earlier work [2, 18], and we
discuss some of their properties. At this point, in Section 6, we are ready to
formulate our central claim/result: for each of the above-mentioned
martingale-theoretic notions of randomness, an infinite sequence is random for
an interval forecast if and only if it is random for some specific related
non-computable non-stationary precise uncertainty model. We complement this
result with a reflection on what it tells us about allowing for imprecision
and non-computability in a martingale-theoretic approach to algorithmic
randomness. Moreover, we explain that our result has implications for the
interpretation of imprecise randomness, and that it finds a reflection in
results for the measure-theoretic approach. In the subsequent three sections,
we work towards the proof of our main claim. In Section 7, we use betting
strategies to introduce global upper expectations and define almost sure
events. In Section 8 we introduce, inspired by Wald’s work, a very general
imprecise-probabilistic frequentist notion of randomness in terms of countable
sets of selection processes, and highlight the particular imprecise-
probabilistic frequentist notions of (weak) Church randomness that we
introduced elsewhere [2, 19]. In Section 9 then, we employ all this
mathematical machinery in the ‘construction’ of the specific non-stationary
precise uncertainty models that we can use to prove our main theorem. We
conclude this paper with a discussion in Section 10 on the possible
implications of our main result for a prospective statistics based on
imprecise probabilities.

##  2 Local uncertainty models: interval forecasts and gambles

We begin our discussion by considering a single variable $X$ that may assume
some value in the binary outcome space $\\{0,1\\}$. To describe a subject’s
uncertainty about the unknown value of $X$, we use a closed interval
$I\subseteq[0,1]$. We collect all such closed intervals in the set
$\mathscr{I}$ and call them _interval forecasts_. One way to interpret an
interval forecast $I\in\mathscr{I}$ is to regard its elements $p\in I$ as
possible values for the probability that $X$ equals $1$, or equivalently, for
the expectation of, or fair price for, the uncertain reward $X$. In this
paper, however, where betting will play a central role, we prefer to adopt a
different interpretation. We interpret the lower and upper bound of $I$ as a
subject’s largest acceptable buying and smallest acceptable selling price,
respectively,111Traditionally, in a so-called imprecise probabilities context,
the lower and upper bound of $I$ are interpreted as a subject’s supremum
acceptable buying and infimum acceptable selling price for the uncertain pay-
off $X$. However, as was proved in [2, Appendix A], our four imprecise-
probabilistic martingale-theoretic notions of randomness are the same under
both interpretations. We adopt the former interpretation, because it
simplifies some of our proofs. for the uncertain pay-off $X\in\\{0,1\\}$,
expressed in units of some linear utility scale.

Consequently, if $I=[\underline{p},\overline{p}]$, our subject is willing to
accept the uncertain pay-off $X-p$ for any buying price $p\leq\underline{p}$,
and is willing to accept the uncertain pay-off $q-X$ for any selling price
$q\geq\overline{p}$. Due to the assumed linearity of the utility scale, this
implies that he is willing to _accept_ the uncertain pay-off
$\alpha(X-p)+\beta(q-X)$ for any $p\leq\underline{p}$, $q\geq\overline{p}$ and
$\alpha,\beta\geq 0$. From the perspective of an opponent who bets against our
subject, this means that our subject is willing to _offer_ her any uncertain
reward of the form

$\alpha(p-X)+\beta(X-q)\text{ with~{}$p\leq\underline{p}$, $q\geq\overline{p}$
and~{}$\alpha,\beta\geq 0$}.$ (1)

To manipulate these uncertain rewards mathematically, it will be convenient to
identify them with maps on $\\{0,1\\}$, whose value in $x\in\\{0,1\\}$ is
obtained by replacing $X$ with $x$. The reward $X$, for example, then
corresponds to the identity map on $\\{0,1\\}$. We will call any such map
$f\colon\\{0,1\\}\to\mathbb{R}$ from the binary sample space to the _real_
numbers a _gamble_ , and we denote the set of all gambles by
$\mathscr{L}(\\{0,1\\})$. Since $|\\{0,1\\}|=2$, gambles can be drawn in a
two-dimensional space. This allows us to visualise the set of all gambles of
the type (1), which are offered by our subject to an opponent as a result of
the commitments implicit in his specifying the interval forecast
$I=[\underline{p},\overline{p}]$. It is clear from Figure 1 that this set is a
convex cone that includes the third quadrant.

Figure 1: Let $\underline{p}\coloneqq\nicefrac{{1}}{{4}}$ and
$\overline{p}\coloneqq\nicefrac{{3}}{{4}}$. The green region depicts all
gambles $f\in\mathscr{L}(\\{0,1\\})$ that correspond to an uncertain reward
$\alpha(p-X)+\beta(X-q)$, with $p\leq\underline{p}$, $q\geq\overline{p}$ and
$\alpha,\beta\geq
0$.$f(1)$$f(0)$$-2$$-1$$1$$-2$$-1$$1$$0$$\\{\alpha(\underline{p}-X)\colon\alpha\geq
0\\}$$\\{\beta(X-\overline{p})\colon\beta\geq 0\\}$

It will be useful to have an analytical condition that, for a subject with
interval forecast $I\in\mathscr{I}$, characterises the gambles he is willing
to offer to an opponent. To this end, we introduce upper (and lower)
expectation operators. When $I=p\in\mathbb{R}$, i.e., when $I$ reduces to a
single number, we consider the _linear expectation_ $E_{p}$ defined by

$E_{p}(f)\coloneqq pf(1)+(1-p)f(0)\text{ for all }f\in\mathscr{L}(\\{0,1\\}).$
(2)

This is a most informative—or least conservative—model for a subject’s
uncertainty. When $I=[\underline{p},\overline{p}]\notin\mathbb{R}$, we
consider the _upper expectation_ $\overline{E}_{I}$ defined by

$\overline{E}_{I}(f)\coloneqq\max_{p\in
I}E_{p}(f)=\max\\{E_{\underline{p}}(f),E_{\overline{p}}(f)\\}\text{ for all
}f\in\mathscr{L}(\\{0,1\\}).$ (3)

As a closely related operator, we consider the _lower expectation_
$\underline{E}_{I}\colon\mathscr{L}(\\{0,1\\})\to\mathbb{R}$ defined by

$\underline{E}_{I}(f)\coloneqq\min_{p\in
I}E_{p}(f)=\min\\{E_{\underline{p}}(f),E_{\overline{p}}(f)\\}\text{ for
all~{}$f\in\mathscr{L}(\\{0,1\\})$.}$ (4)

It is clear that lower and upper expectations are related to each other
through the following conjugacy relationship:
$\overline{E}_{I}(f)=-\underline{E}_{I}(-f)$ for all
$f\in\mathscr{L}(\\{0,1\\})$.

It is a matter of straightforward verification that the upper expectation
$\overline{E}_{I}$ satisfies the following so-called _coherence_ properties
[20].

######  Proposition 1.

Consider any interval forecast $I\in\mathscr{I}$. Then for all gambles
$f,g\in\mathscr{L}(\\{0,1\\})$, and all $\mu\in\mathbb{R}$ and
$\lambda\in\mathbb{R}_{\geq 0}$:222$\mathbb{R}_{\geq 0}$ denotes the set of
non-negative real numbers, whereas $\mathbb{R}_{>0}$ denotes the set of
positive real numbers.

  1. C1.

$\min f\leq\overline{E}_{I}(f)\leq\max f$ [boundedness]

  2. C2.

$\overline{E}_{I}(\lambda f)=\lambda\overline{E}_{I}(f)$ [non-negative
homogeneity]

  3. C3.

$\overline{E}_{I}(f+g)\leq\overline{E}_{I}(f)+\overline{E}_{I}(g)$
[subadditivity]

  4. C4.

$\overline{E}_{I}(f+\mu)=\overline{E}_{I}(f)+\mu$ [constant additivity]

  5. C5.

if $f\leq g$ then $\overline{E}_{I}(f)\leq\overline{E}_{I}(g)$ [monotonicity]

These coherence properties C1–C4 allow us to show fairly directly that the
upper expectation $\overline{E}_{I}$ indeed characterises the gambles that are
offered by our subject.

######  Proposition 2.

Consider any gamble $f\in\mathscr{L}(\\{0,1\\})$ and any interval forecast
$I=[\underline{p},\overline{p}]\in\mathscr{I}$. Then $\overline{E}_{I}(f)\leq
0$ if and only if there are $p\leq\underline{p}$, $q\geq\overline{p}$ and
$\alpha,\beta\geq 0$ such that $f=\alpha(p-X)+\beta(X-q)$.

###### Proof.

To prove the direct implication, assume that $\overline{E}_{I}(f)\leq 0$. We
will consider three cases: $f(1)>f(0)$, $f(1)<f(0)$ and $f(1)=f(0)$. If
$f(1)>f(0)$, then $f$ can always be written as $f=\beta(X-q)$, with
$\beta=f(1)-f(0)\in\mathbb{R}_{>0}$ and
$q=\nicefrac{{f(0)}}{{(f(0)-f(1))}}\in\mathbb{R}$. Since $\beta>0$, it now
suffices to prove that $q\geq\overline{p}$. To do so, observe that by Equation
(3) it holds that $\overline{E}_{I}(X)=\overline{p}$. Consequently, it follows
from C2 and C4 that

$\displaystyle
0\geq\overline{E}_{I}(f)=\overline{E}_{I}(\beta(X-q))=\beta(\overline{E}_{I}(X)-q)=\beta(\overline{p}-q),$

and hence, since $\beta>0$, that $q\geq\overline{p}$. If $f(1)<f(0)$, then $f$
can always be written as $f=\alpha(p-X)$, with
$\alpha=f(0)-f(1)\in\mathbb{R}_{>0}$ and
$p=\nicefrac{{f(0)}}{{(f(0)-f(1))}}\in\mathbb{R}$. Since $\alpha>0$, it now
suffices to prove that $p\leq\underline{p}$. To do so, observe that by
Equation (4) it holds that $\underline{E}_{I}(X)=\underline{p}$. Consequently,
it follows from conjugacy, C2 and C4 that

$\displaystyle
0\geq\overline{E}_{I}(f)=-\underline{E}_{I}(-f)=-\underline{E}_{I}(\alpha(X-p))=-\alpha\underline{E}_{I}(X-p)=-\alpha(\underline{E}_{I}(X)-p)=\alpha(p-\underline{E}_{I}(X))=\alpha(p-\underline{p}),$

and hence, since $\alpha>0$, that $p\leq\underline{p}$. If $f(1)=f(0)$, then
$f(1)=f(0)=\overline{E}_{I}(f)\leq 0$ by C1, and hence, $f$ can always be
written as $f=\overline{E}_{I}(f)=\alpha(0-X)+\beta(X-1)$, with
$\alpha=\beta=-\overline{E}_{I}(f)\geq 0$, $0\leq\underline{p}$ and
$1\geq\overline{p}$.

To prove the converse implication, assume that $f=\alpha(p-X)+\beta(X-q)$,
with $p\leq\underline{p}$, $q\geq\overline{p}$ and $\alpha,\beta\geq 0$. From
C2-C4, conjugacy and by recalling that $\overline{E}_{I}(X)=\overline{p}$ and
$\underline{E}_{I}(X)=\underline{p}$, it then immediately follows that

$\displaystyle\overline{E}_{I}(f)$
$\displaystyle=\overline{E}_{I}(\alpha(p-X)+\beta(X-q))\leq\overline{E}_{I}(\alpha(p-X))+\overline{E}_{I}(\beta(X-q))=\alpha\overline{E}_{I}(p-X)+\beta\overline{E}_{I}(X-q)$
$\displaystyle=\alpha(p+\overline{E}_{I}(-X))+\beta(\overline{E}_{I}(X)-q)=\alpha(p-\underline{E}_{I}(X))+\beta(\overline{E}_{I}(X)-q)=\alpha(p-\underline{p})+\beta(\overline{p}-q)\leq
0,$

which completes the proof. ∎

##  3 Forecasting systems and betting strategies

We can better describe the correspondence between a subject’s interval
forecasts, which specify his beliefs about the unknown outcomes of binary
variables, and actual outcome sequences, by taking him up on a specific
betting game.

We first introduce the betting game for a single binary variable $X$. There
are three players involved: _Forecaster_ (who will take up our subject’s
part), _Sceptic_ (who is his opponent) and _Reality_. Forecaster initiates the
game by providing an interval forecast $I\subseteq[0,1]$, which describes, as
we explained in the previous section, his beliefs about—and betting
commitments related to—the uncertain outcome $X\in\\{0,1\\}$. Next, Sceptic,
being Forecaster’s opponent, is allowed to pick any gamble
$f\in\mathscr{L}(\\{0,1\\})$ that Forecaster is willing to offer, in the
specific sense that $\overline{E}_{I}(f)\leq 0$. This leads to an uncertain
(possibly negative) gain $f(X)$ for Sceptic and $-f(X)$ for Forecaster.
Finally, Reality reveals the outcome $x\in\\{0,1\\}$, which leads to an actual
(possibly negative) gain $f(x)$ for Sceptic and $-f(x)$ for Forecaster.

In order to extend these ideas to an infinite betting game involving a
sequence of successively revealed binary variables $X_{1}$, …, $X_{n}$, …, we
require a bit more terminology.

In what follows, $\mathbb{N}$ denotes the set of natural numbers, and
${\mathbb{N}_{0}}\coloneqq\mathbb{N}\cup\\{0\\}$ denotes the set of non-
negative integers. An infinite outcome sequence $(x_{1},\dots,x_{n},\dots)$ is
called a _path_ and is also denoted by $\omega$. All such paths are collected
in the set $\Omega\coloneqq\\{0,1\\}^{\mathbb{N}}$, and for every path
$\omega=(x_{1},\dots,x_{n},\dots)\in\Omega$, we let
$\omega_{1:n}\coloneqq(x_{1},\dots,x_{n})$ and $\omega_{n+1}\coloneqq x_{n+1}$
for all $n\in{\mathbb{N}_{0}}$. A finite outcome sequence
$x_{1:n}\coloneqq(x_{1},\dots,x_{n})\in\\{0,1\\}^{n}$ is called a _situation_
and is also denoted by $s$, with length $|s|\coloneqq n$, for any
$n\in{\mathbb{N}_{0}}$. All situations are collected in the set
$\mathbb{S}\coloneqq\bigcup_{n\in{\mathbb{N}_{0}}}\\{0,1\\}^{n}$. For any
$s=(x_{1},\dots,x_{n})\in\mathbb{S}$ and $x\in\\{0,1\\}$, we write $sx$ as a
shorthand notation for $(x_{1},\dots,x_{n},x)$. We call the empty sequence
$\square\coloneqq x_{1:0}=()$ the _initial situation_. Note that for every
path $\omega\in\Omega$, we have that $\omega_{1:0}=\square$.

It will also be useful to be able to deal with objects that depend on the
situations. Formally, we define a _process_ $F$ as a map on the set
$\mathbb{S}$ of all situations. In particular, a _real_ process
$F\colon\mathbb{S}\to\mathbb{R}$ is a map from situations to real numbers. A
real process $F$ is called _non-negative_ if $F(s)\geq 0$ for all
$s\in\mathbb{S}$; it is called _positive_ if $F(s)>0$ for all
$s\in\mathbb{S}$. We call a non-negative real process $F$ a _test process_ if
additionally $F(\square)=1$. A zero-one valued process $S$—with
$S(s)\in\\{0,1\\}$ for all $s\in\mathbb{S}$—is called a _selection process_.
If a process $F$ depends only on the situations $s\in\mathbb{S}$ through their
length $|s|$, we call it _temporal_ , and then also write $F(n)$ instead of
$F(s)$ for all $n\in{\mathbb{N}_{0}}$ and $s\in\mathbb{S}$ with $n=|s|$.

Forecaster’s part in the game now consists in providing an interval-valued
process. That is, he provides an interval forecast $I_{s}\in\mathscr{I}$ for
every finite outcome sequence $s\in\mathbb{S}$, in order to describe his
beliefs about the binary variable $X_{|s|+1}$ after observing the outcome $s$
for the previous $|s|$ variables. The interval-valued process that summarises
these interval forecasts, we call a forecasting system.

######  Definition 1 (Forecasting system).

A _forecasting system_ is a map $\varphi\colon\mathbb{S}\to\mathscr{I}$ that
associates with every situation $s\in\mathbb{S}$ an interval forecast
$\varphi(s)\in\mathscr{I}$. A forecasting system $\varphi$ is called _precise_
if $\varphi(s)\in\mathbb{R}$ for all $s\in\mathbb{S}$. We denote the set
$\smash{\mathscr{I}^{\mathbb{S}}}$ of all forecasting systems by $\Phi$.

With every forecasting system $\varphi\in\Phi$, we associate two real
processes $\underline{\varphi}$ and $\overline{\varphi}$ defined by
$\underline{\varphi}(s)\coloneqq\min\varphi(s)$ and
$\overline{\varphi}(s)\coloneqq\max\varphi(s)$ for all $s\in\mathbb{S}$.
Clearly, a forecasting system $\varphi\in\Phi$ is precise if and only if
$\underline{\varphi}(s)=\overline{\varphi}(s)$ for all $s\in\mathbb{S}$. If a
forecasting system $\varphi\in\Phi$ uses the very same interval forecast
$I\in\mathscr{I}$ in all situations, i.e., $\varphi(s)=I$ for all
$s\in\mathbb{S}$, then we call it _stationary_ , and we simplify the notation
by writing $I$ instead of $\varphi$. If for two forecasting systems
$\varphi,\varphi^{*}\in\Phi$ it holds that $\varphi(s)\subseteq\varphi^{*}(s)$
for all $s\in\mathbb{S}$, then we say that $\varphi^{*}$ is less
informative—or more conservative—than $\varphi$, and denote this by
$\varphi\subseteq\varphi^{*}$. In this case, if $\varphi$ is precise, then we
also say that $\varphi$ is _compatible_ with $\varphi^{*}$, and denote this by
$\varphi\in\varphi^{*}$. It is also worth noting that, through the Kolmogorov
extension theorem, every precise forecasting system uniquely determines a
corresponding probability measure on the algebra (of sets of paths) generated
by the situations. In measure-theoretic notions of randomness, one will
typically focus on this measure instead of its forecasting system. In our
game-theoretic approach, however, the forecasting system takes the center
stage.

Once Forecaster has specified a forecasting system $\varphi\in\Phi$, Sceptic
is allowed to adopt any betting strategy that, for every situation
$s\in\mathbb{S}$, selects one of the gambles that Forecaster is bound to offer
by his specification of the interval forecast $\varphi(s)\in\mathscr{I}$,
i.e., some gamble $f_{s}\in\mathscr{L}(\\{0,1\\})$ for which
$\overline{E}_{\varphi(s)}(f_{s})\leq 0$. Afterwards, Reality reveals the
successive outcomes $X_{n}=x_{n}$ at each successive _time instant_
$n\in\mathbb{N}$, leading to the sequence $\omega=(x_{1},\dots,x_{n},\dots)$.
At every time instant $n$, after Reality has revealed the outcome $x_{n}$,
Sceptic uses the gamble $f_{x_{1:n}}$ that corresponds to her betting
strategy. Next, Reality reveals the subsequent outcome
$X_{n+1}=x_{n+1}\in\\{0,1\\}$ and the reward $f_{x_{1:n}}(x_{n+1})$ goes to
Sceptic. Moreover, we will prohibit Sceptic from borrowing.

In order to formalise these betting strategies for Sceptic, we define a
_gamble process_ as a map from situations to gambles. In particular, we
associate with every real process $F$ a _process difference_ $\Delta
F\colon\mathbb{S}\to\mathscr{L}(\\{0,1\\})$, which is the gamble process that
maps any $s\in\mathbb{S}$ to the gamble $\Delta F(s)\coloneqq
F(s\,\bullet)-F(s)$, where we use $F(s\,\bullet)$ to denote the gamble on
$\\{0,1\\}$ whose value, for any $x\in\\{0,1\\}$, is given by $F(sx)$. Note
that $F(x_{1:n})=F(\square)+\sum_{k=0}^{n-1}\Delta F(x_{1:k})(x_{k+1})$ for
all $x_{1:n}\in\mathbb{S}$, with $n\in{\mathbb{N}_{0}}$.

Given a forecasting system $\varphi\in\Phi$, we call a real process $M$ a
_supermartingale_ for $\varphi$ if $\overline{E}_{\varphi(s)}(\Delta M(s))\leq
0$ for all $s\in\mathbb{S}$. A real process $M$ is called a _submartingale_
for $\varphi$ if $-M$ is a supermartingale for $\varphi$, meaning that
$\underline{E}_{\varphi(s)}(\Delta M(s))\geq 0$ for all $s\in\mathbb{S}$. All
supermartingales and submartingales for $\varphi$ are respectively collected
in the sets $\overline{\mathbb{M}}(\varphi)$ and
$\underline{\mathbb{M}}(\varphi)$.

Supermartingales correspond to Sceptic’s allowed betting strategies. Indeed,
assume that Forecaster adopts the forecasting system $\varphi\in\Phi$,
consider a time instant $n\in{\mathbb{N}_{0}}$, and consider the situation
where Reality has revealed a finite outcome sequence $x_{1:n}\in\mathbb{S}$. A
supermartingale $M$ for $\varphi$ then specifies a gamble $\Delta
M(x_{1:n})\in\mathscr{L}(\\{0,1\\})$ that Sceptic is allowed to pick. If she
does, and Reality reveals the outcome $x_{n+1}\in\\{0,1\\}$, the (possibly
negative) amount $\Delta M(x_{1:n})(x_{n+1})$ goes to Sceptic and her total
capital becomes

$\displaystyle M(x_{1:n+1})=M(x_{1:n})+\Delta
M(x_{1:n})(x_{n+1})=M(\square)+\sum_{k=0}^{n}\Delta M(x_{1:k})(x_{k+1}),$

with $M(\square)$ her initial capital. By focusing on non-negative
supermartingales, we additionally prevent Sceptic from borrowing.

As an important special case, we consider _test supermartingales_
$T\colon\mathbb{S}\to\mathbb{R}$ for $\varphi$. These are non-negative
supermartingales for $\varphi$ for which $T(\square)\coloneqq 1$. We collect
all test supermartingales for $\varphi$ in the set
$\overline{\mathbb{T}}(\varphi)$. In one of our notions of randomness, we will
adopt a particular way of defining such test supermartingales by focusing on
multiplicative rather than additive betting strategies. For this reason, we
introduce the notion of a _multiplier process_ , which is a non-negative
gamble process. With every such multiplier process $D$, we associate a test
process $D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}$, defined by the
‘initial condition’
$D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}(\square)\coloneqq 1$ and,
for all $s\in\mathbb{S}$ and $x\in\\{0,1\\}$, by the recursion equation
$D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}(sx)\coloneqq
D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}(s)D(s)(x)$, and we say that
$D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}$ is _generated by_ $D$. In
particular, we say that a test supermartingale
$T\in\overline{\mathbb{T}}(\varphi)$ is _generated by a multiplier process_ if
there is some non-negative gamble process $D_{T}$ such that
$T(x_{1:n})=\prod_{k=0}^{n-1}D_{T}(x_{1:k})(x_{k+1})$ for all
$x_{1:n}\in\mathbb{S}$, with $n\in{\mathbb{N}_{0}}$.

##  4 Computable forecasting systems and implementable betting strategies

Sceptic will not be allowed to adopt just any non-negative supermartingale as
a betting strategy. We will also require that it should be implementable [10,
21]. Loosely speaking, this means that for each of her betting strategies,
there is some finite description that specifies how to approximate it (to
arbitrary precision). In order to be able to formalise when a supermartingale
is implementable, we turn to computability theory.

As a basic building block, this theory considers _recursive_ natural functions
$\phi\colon{\mathbb{N}_{0}}\to{\mathbb{N}_{0}}$, which are maps that can be
computed by a Turing machine [22]. By the Church–Turing thesis, this is
equivalent to the existence of a finite algorithm that, given the input
$n\in{\mathbb{N}_{0}}$, outputs $\phi(n)\in{\mathbb{N}_{0}}$. For example,
since a path $\omega\in\Omega$ is a function from $\mathbb{N}$ to $\\{0,1\\}$,
we call it recursive if there is some finite algorithm that, given the input
$n\in\mathbb{N}$, outputs $\omega_{n}\in\\{0,1\\}$. Instead of
${\mathbb{N}_{0}}$, we will also consider functions whose domain equals
$\mathbb{N}$, $\mathbb{S}$, $\mathbb{S}\times\\{0,1\\}$,
$\mathbb{S}\times{\mathbb{N}_{0}}$ or any other countably infinite set
$\mathscr{D}$ whose elements can be encoded by the natural numbers. A function
$\phi\colon\mathscr{D}\to{\mathbb{N}_{0}}$ is then called _recursive_ if there
is a Turing machine that, when given the natural-valued encoding of an element
$d\in\mathscr{D},$333The choice of encoding is not important provided
different encodings can be translated into each other. The latter means that
we can algorithmically decide whether a natural number is an encoding of an
object and, if this is the case, that we can find an encoding of the same
object with respect to the other encoding [23]. outputs $\phi(d)$. Also in
this more general case, by the Church–Turing thesis, this is equivalent to the
existence of a finite algorithm that, given the input $d\in\mathcal{D}$,
outputs $\phi(d)\in{\mathbb{N}_{0}}$. In fact, throughout this paper and its
proofs, it is this alternative, more intuitive, characterisation that we will
be using. For example, we will call a selection process $S$ recursive if there
is a finite algorithm that, given the input $s\in\mathbb{S}$, outputs the
binary digit $S(s)\in\\{0,1\\}$.

More generally, for any countable domain $\mathscr{D}$ that can be encoded by
the natural numbers, a _rational_ map $q\colon\mathscr{D}\to\mathbb{Q}$ is
called _recursive_ if there are three recursive natural maps
$a,b,c\colon\mathscr{D}\to{\mathbb{N}_{0}}$ such that

$b(d)\neq 0\text{ and }q(d)=\smash{(-1)^{c(d)}\frac{a(d)}{b(d)}}\text{ for all
}d\in\mathscr{D}.$

Since a finite number of finite algorithms can always be combined into one
finite algorithm [24], this is equivalent to the existence of a finite
algorithm that outputs $q(d)$ when given $d\in\mathscr{D}$ as input. In
particular, a rational process $F\colon\mathbb{S}\to\mathbb{Q}$ is called
recursive if there is a recursive rational map
$q\colon\mathbb{S}\to\mathbb{Q}$ such that $F(s)=q(s)$ for all
$s\in\mathbb{S}$.

Computability theory not only considers recursive objects, but also uses them
to introduce _lower semicomputable_ ones. The simplest case is that of a lower
semicomputable real number: a real number $x\in\mathbb{R}$ is called lower
semicomputable if there is a recursive rational map
$q\colon{\mathbb{N}_{0}}\to\mathbb{Q}$ such that $q(n)\leq q(n+1)$ for all
$n\in{\mathbb{N}_{0}}$, and $x=\lim_{m\to\infty}q(m)$. More generally, for any
countable domain $\mathscr{D}$ that can be encoded by the natural numbers, a
real map $r\colon\mathscr{D}\to\mathbb{R}$ is called lower semicomputable if
there is a recursive rational map
$q\colon\mathscr{D}\times{\mathbb{N}_{0}}\to\mathbb{Q}$ such that $q(d,n)\leq
q(d,n+1)$ and $r(d)=\lim_{m\to\infty}q(d,m)$ for all $d\in\mathscr{D}$ and
$n\in{\mathbb{N}_{0}}$. A real map $r$ is thus lower semicomputable if there
is some finite algorithm that, for every element $d\in\mathscr{D}$ of the
domain, can provide an increasing sequence $(q(d,n))_{n\in{\mathbb{N}_{0}}}$
of rational numbers that approaches the real number $r(d)$ from below—but
without necessarily knowing how good the lower bounds $q(d,n)$ are. In
particular, a real process $F$ is called lower semicomputable if there is a
recursive rational map $q\colon\mathbb{S}\times{\mathbb{N}_{0}}\to\mathbb{Q}$
such that $q(s,n)\leq q(s,n+1)$ and $F(s)=\lim_{m\to\infty}q(s,m)$ for all
$s\in\mathbb{S}$ and $n\in{\mathbb{N}_{0}}$. Similarly, a real multiplier
process $D$ is called lower semicomputable if there is a recursive rational
map $q\colon\mathbb{S}\times\\{0,1\\}\times{\mathbb{N}_{0}}\to\mathbb{Q}$ such
that $q(s,x,n)\leq q(s,x,n+1)$ and $D(s)(x)=\lim_{m\to\infty}q(s,x,m)$ for all
$s\in\mathbb{S}$, $x\in\\{0,1\\}$ and $n\in{\mathbb{N}_{0}}$. Two types of
lower semicomputable (gamble) processes that we will make frequent use of, are
lower semicomputable test supermartingales and lower semicomputable multiplier
processes that generate test supermartingales.

We call a real map $r\colon\mathscr{D}\to\mathbb{R}$ _upper semicomputable_ if
$-r$ is lower semicomputable. If a real map $r$ is both lower and upper
semicomputable, then we call it _computable_. Equivalently [1], a real map
$r\colon\mathscr{D}\to\mathbb{R}$ is computable if and only if there is a
recursive rational map $q\colon\mathscr{D}\times{\mathbb{N}_{0}}\to\mathbb{Q}$
such that

$|r(d)-q(d,n)|<2^{-n}\text{ for all }d\in\mathscr{D}\text{ and
}n\in{\mathbb{N}_{0}}.$

This means that there is a finite algorithm that, for every $d\in\mathscr{D}$
and $n\in{\mathbb{N}_{0}}$, outputs a rational number $q(d,n)$ that
approximates the real number $r(d)$ with a precision of at least $2^{-n}$. In
particular, a real number $x\in\mathbb{R}$ is called computable if there is a
recursive rational map $q\colon{\mathbb{N}_{0}}\to\mathbb{Q}$ such that
$|x-q(n)|<2^{-n}$ for all $n\in{\mathbb{N}_{0}}$. An interval forecast
$I\in\mathscr{I}$ is called computable if the real numbers $\min I$ and $\max
I$ are both computable. Moreover, a real process
$F\colon\mathbb{S}\to\mathbb{R}$ is called computable if there is a recursive
rational map $q\colon\mathbb{S}\times{\mathbb{N}_{0}}\to\mathbb{Q}$ such that
$|F(s)-q(s,n)|<2^{-n}$ for all $s\in\mathbb{S}$ and $n\in{\mathbb{N}_{0}}$.
Finally, a forecasting system $\varphi\in\Phi$ is called computable if the
real processes $\underline{\varphi}$ and $\overline{\varphi}$ are both
computable.

So, a real process $F\colon\mathbb{S}\to\mathbb{R}$ can be implementable by
being recursive, lower semicomputable, upper semicomputable or computable, but
also, if it is generated by a multiplier process $D$, by $D$ being of one of
these four types. In what follows, it will be useful to have the following
sets of implementable real processes at our notational disposal:

$\mathscr{F}_{\textnormal{ML}}$ | all lower semicomputable test processes;
---|---
$\mathscr{F}_{\textnormal{wML}}$ | all test processes generated by
| lower semicomputable multiplier processes;
$\mathscr{F}_{\textnormal{C}}=\mathscr{F}_{\textnormal{S}}$ | all recursive positive rational test processes.

From the discussion above, it is clear that if $F$ is recursive, then it is
computable and hence lower semicomputable as well; so
$\mathscr{F}_{\textnormal{S}}=\mathscr{F}_{\textnormal{C}}\subseteq\mathscr{F}_{\textnormal{ML}}$.
It follows from discussions elsewhere [2, Section 5] that all four sets are in
fact nested:
$\mathscr{F}_{\textnormal{S}}=\mathscr{F}_{\textnormal{C}}\subseteq\mathscr{F}_{\textnormal{wML}}\subseteq\mathscr{F}_{\textnormal{ML}}$.
As a result, for any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
it also holds that the set $\mathscr{F}_{\textnormal{R}}$ is countably
infinite, because the lower semicomputable test processes are countable in
number; see for example [4, Lemma 13].

##  5 Several martingale-theoretic notions of randomness

Now that we know in what different ways Sceptic’s betting strategies can be
implementable, we are ready to introduce four different martingale-theoretic
notions of randomness: Martin-Löf (ML) randomness, weak Martin-Löf (wML)
randomness, computable (C) randomness and Schnorr (S) randomness; except for
wML-randomness, these are all generalisations to interval forecasts of
classical notions of randomness. We recall from the Introduction that, in the
martingale-theoretic setting, a path $\omega\in\Omega$ is random for a
forecasting system $\varphi$ if Sceptic has no implementable betting strategy
that is allowed by $\varphi$ and that makes her arbitrarily rich on $\omega$
without borrowing. This is true for each of the above-mentioned four notions
of randomness. The difference between them lies in the way the allowed betting
strategies are implementable, and in the way Sceptic should not be able to
become arbitrarily rich. The allowed betting strategies for the notions of
ML-, wML-, C- and S-randomness are gathered in the following sets:

$\overline{\mathbb{T}}_{\textnormal{ML}}(\varphi)\coloneqq\mathscr{F}_{\textnormal{ML}}\cap\overline{\mathbb{T}}(\varphi)$ | all lower semicomputable test supermartingales for $\varphi$;
---|---
$\overline{\mathbb{T}}_{\textnormal{wML}}(\varphi)\coloneqq\mathscr{F}_{\textnormal{wML}}\cap\overline{\mathbb{T}}(\varphi)$ | all test supermartingales for $\varphi$ generated by
| lower semicomputable multiplier processes;
$\overline{\mathbb{T}}_{\textnormal{C}}(\varphi)\coloneqq\mathscr{F}_{\textnormal{C}}\cap\overline{\mathbb{T}}(\varphi)$ | all recursive positive rational test supermartingales for $\varphi$;
$\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)\coloneqq\mathscr{F}_{\textnormal{S}}\cap\overline{\mathbb{T}}(\varphi)$ | all recursive positive rational test supermartingales for $\varphi$.

By recalling that
$\mathscr{F}_{\textnormal{S}}=\mathscr{F}_{\textnormal{C}}\subseteq\mathscr{F}_{\textnormal{wML}}\subseteq\mathscr{F}_{\textnormal{ML}}$,
it readily follows that the above sets of betting strategies satisfy the
following relations for any forecasting system $\varphi$:
$\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)=\overline{\mathbb{T}}_{\textnormal{C}}(\varphi)\subseteq\overline{\mathbb{T}}_{\textnormal{wML}}(\varphi)\subseteq\overline{\mathbb{T}}_{\textnormal{ML}}(\varphi)$.

Now, for any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C}\\}$, we
will consider a path $\omega\in\Omega$ to be R-random for a forecasting system
$\varphi$ if Sceptic can adopt no betting strategy
$T\in\overline{\mathbb{T}}_{\textnormal{R}}(\varphi)$ that is _unbounded_ on
$\omega$, in the sense that $\limsup_{n\to\infty}T(\omega_{1:n})=\infty$.

######  Definition 2 ([2, Definition 2][18, Definition 5 and Proposition 6]).

For any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C}\\}$, a
path $\omega\in\Omega$ is R-random for a forecasting system $\varphi\in\Phi$
if no test supermartingale
$T\in\overline{\mathbb{T}}_{\textnormal{R}}(\varphi)$ is unbounded on
$\omega$.

We want to emphasise here that, contrary to what is typically done in the
literature for algorithmic randomness associated with precise forecasts, we
don’t necessarily impose computability requirements on the forecasting systems
$\varphi$.

In the case of C-randomness, it may initially seem rather unintuitive that we
consider recursive rational test supermartingales instead of computable real
non-negative supermartingales, since the naming suggests the latter. However,
as we have discussed in [25, Section 5], both sets of betting strategies
result in the same notion of randomness; we use the former here for
mathematical convenience. In what follows, we will also implicitly use this
equivalence when referring to results proven elsewhere.

To introduce S-randomness, we require the additional notion of a _real growth
function_ $\tau\colon{\mathbb{N}_{0}}\to\mathbb{R}_{\geq 0}$, which is a
computable map from non-negative integers to non-negative reals that is non-
decreasing—so $\tau(n+1)\geq\tau(n)$ for all $n\in{\mathbb{N}_{0}}$—and
unbounded—so $\lim_{n\to\infty}\tau(n)=\infty$. Now, a path $\omega\in\Omega$
is considered to be S-random for a forecasting system $\varphi$ if no test
supermartingale $T\in\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$ is
_computably unbounded_ on $\omega$, meaning that there is some real growth
function $\tau$ such that $\limsup_{n\to\infty}[T(\omega_{1:n})-\tau(n)]\geq
0$. Intuitively, and analogously to computable randomness, this means that
Sceptic should not be able to adopt a recursive (positive rational) betting
strategy
$T\in\overline{\mathbb{T}}_{\textnormal{C}}(\varphi)=\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$
that allows her to get arbitrarily rich, but now at some computable rate.

######  Definition 3.

A path $\omega\in\Omega$ is S-random for a forecasting system $\varphi\in\Phi$
if no test supermartingale
$T\in\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$ is computably unbounded
on $\omega$.

Interestingly, and similarly to C-randomness, we can replace the set of
allowable betting strategies $\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$
by the set of computable test supermartingales for $\varphi$, without changing
the set of S-random paths for $\varphi$. That is, a path $\omega\in\Omega$ is
S-random for a forecasting system $\varphi\in\Phi$ if and only if there is no
computable betting strategy that starts with unit capital, is allowed by
$\varphi$ and makes Sceptic arbitrarily rich along $\omega$ at some computable
rate; here too, we will implicitly use this equivalence when referring to
results proven elsewhere.

######  Proposition 3.

A path $\omega\in\Omega$ is S-random for a forecasting system $\varphi\in\Phi$
if and only if no computable non-negative supermartingale
$M\in\overline{\mathbb{M}}(\varphi)$ is computably unbounded on $\omega$.

###### Proof.

The reverse implication holds trivially since every recursive positive
rational test supermartingale
$T\in\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$ is a computable non-
negative supermartingale for $\varphi$ as well.

For the direct implication, we assume _ex absurdo_ that there is a computable
non-negative supermartingale $M\in\overline{\mathbb{M}}(\varphi)$ that is
computably unbounded on $\omega$, meaning that there is a real growth function
$\tau$ such that $\limsup_{n\to\infty}[M(\omega_{1:n})-\tau(n)]\geq 0$. By
[25, Lemma 24], we know there is some recursive positive rational test
supermartingale $T\in\overline{\mathbb{T}}(\varphi)$ and a positive rational
number $\alpha>0$ such that $|\alpha T(s)-M(s)|\leq 7$ for all
$s\in\mathbb{S}$, and therefore also $\nicefrac{{(M(s)-7)}}{{\alpha}}\leq
T(s)$ for all $s\in\mathbb{S}$. If we introduce the real growth function
$\tilde{\tau}$ defined by
$\tilde{\tau}(n)\coloneqq\max\\{\nicefrac{{(\tau(n)-7)}}{{\alpha}},0\\}$ for
all $n\in{\mathbb{N}_{0}}$, then it readily follows from
$\limsup_{n\to\infty}[M(\omega_{1:n})-\tau(n)]\geq 0$ that
$\limsup_{n\to\infty}[T(\omega_{1:n})-\tilde{\tau}(n)]\geq 0$. Hence,
$T\in\overline{\mathbb{T}}_{\textnormal{S}}(\varphi)$ is computably unbounded
on $\omega$, contradicting the assumption that $\omega$ is S-random for
$\varphi$. ∎

If the forecasting system $\varphi$ is stationary in any of the above
randomness notions R, that is, if $\varphi(s)=I$ for all $s\in\mathbb{S}$,
then we will simply say that a path $\omega\in\Omega$ is R-random for the
interval forecast $I$, instead of saying that it is R-random for the
stationary forecasting system $\varphi$.

We refer the reader to [1, 2] for more information about these imprecise-
probabilistic notions of randomness, and here mention only those results that
are relevant to our present purposes. Let us first mention that Definitions 2
and 3 are meaningful, in the sense that every forecasting system
$\varphi\in\Phi$ has at least one R-random path, with
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.

######  Proposition 4 ([2, Corollary 20]).

For any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any forecasting system $\varphi\in\Phi$, there is at least one path
$\omega\in\Omega$ that is R-random for $\varphi$.

Conversely, there is for every path $\omega\in\Omega$ at least one forecasting
system $\varphi\in\Phi$ for which it is R-random, with
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.
The reason is that all paths are R-random with respect to the vacuous
forecasting system $[0,1]$. To understand why this perhaps surprising result
holds, it suffices to realise that the supermartingales that correspond to
$[0,1]$ can never increase. These betting strategies therefore do not allow
Skeptic to increase her capital, let alone become arbitrarily rich.

######  Proposition 5 ([2, Proposition 25]).

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.
Then any path $\omega\in\Omega$ is R-random for the vacuous forecasting system
$[0,1]$.

Moreover, any path $\omega\in\Omega$ that is R-random for $\varphi\in\Phi$ is
also R-random for any forecasting system that is less informative—or more
conservative—than $\varphi$.

######  Proposition 6 ([2, Propositions 10 and 18]).

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any two forecasting systems $\varphi,\varphi^{*}\in\Phi$ such that
$\varphi\subseteq\varphi^{*}$. Then any path $\omega\in\Omega$ that is
R-random for $\varphi$ is also R-random for $\varphi^{*}$.

When we keep the forecasting system $\varphi$ fixed, there is also an ordering
on our four martingale-theoretic notions of randomness. To describe this
ordering, we introduce, for every
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and every forecasting system $\varphi$, the corresponding set of R-random
paths
$\Omega_{\textnormal{R}}(\varphi)\coloneqq\\{\omega\in\Omega\colon\omega\text{
is {R}-random for }\varphi\\}$.

######  Proposition 7 ([2, Section 6]).

For any forecasting system $\varphi$,
$\Omega_{\textnormal{ML}}(\varphi)\subseteq\Omega_{\textnormal{wML}}(\varphi)\subseteq\Omega_{\textnormal{C}}(\varphi)\subseteq\Omega_{\textnormal{S}}(\varphi)$.

Thus, if a path $\omega\in\Omega$ is ML-random for a forecasting system
$\varphi$, then it is also wML-, C- and S-random for $\varphi$. Consequently,
for any given forecasting system $\varphi$, it is for example easier for a
path $\omega\in\Omega$ to be S-random than for it to be ML-random. This makes
us say that ML-randomness is a _stronger_ notion of randomness than wML-, C-
and S-randomness. Conversely, we say that that S-randomness is a _weaker_
notion of randomness than C-, wML- and ML-randomness.

##  6 A remarkable equivalence: non-stationary precise forecasting systems vs
interval forecasts

For didactic reasons, we will now put a temporal halt to our rather technical
but necessary introduction of mathematical concepts. After all, now that we
have these four martingale-theoretic notions of randomness and some of their
properties at our disposal, we can start to address our central question in
this paper: How does allowing for imprecision change our understanding of
random sequences? Is it for example ‘easier’ to capture the randomness of some
paths by imprecise forecasting systems? Are there paths whose randomness can
only be described by imprecise uncertainty models?

To start the discussion, we fix any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and recall from Proposition 6 that if a path $\omega\in\Omega$ is R-random for
some precise forecasting system $\varphi\in\Phi$, then it is also R-random for
any forecasting system that is less informative. Hence, in particular, for any
real numbers $p,q\in[0,1]$ such that $p<q$, if $\omega$ is R-random for the
forecasting system $\varphi_{p,q}$, defined by

$\displaystyle\varphi_{p,q}(s)\coloneqq\begin{cases}p&\text{if $|s|$ is
odd}\\\ q&\text{if $|s|$ is even}\end{cases}\text{ for all }s\in\mathbb{S},$

then it is also R-random for the interval forecast $[p,q]$. So we see that
$[p,q]$ can be used as a simpler—because stationary—yet imprecise alternative
for $\varphi_{p,q}$. In many cases, this procedure of replacing a precise non-
stationary forecasting system by a stationary imprecise one will result in a
larger set of R-random paths, and therefore lead to a less informative
description of the R-randomness associated with $\omega$. However, interval
forecasts do not merely serve as an alternative for non-stationary precise
forecasts. Indeed, as was shown by De Cooman and De Bock [2, Section 10],
there are paths $\omega$ that are R-random for $[p,q]$, but not R-random for
any (more) precise (possibly non-stationary) computable forecasting system
$\varphi$.

######  Theorem 8 ([2, Theorem 37]).

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any interval forecast $[p,q]\in\mathscr{I}$. Then there is a path
$\omega\in\Omega$ that is R-random for the interval forecast $[p,q]$, but that
is never R-random for any computable forecasting system $\varphi\in\Phi$ whose
highest imprecision is smaller than that of $[p,q]$, in the specific sense
that
$\sup_{s\in\mathbb{S}}[\overline{\varphi}(s)-\underline{\varphi}(s)]<q-p$.

Theorem 8 led them to claim that R-randomness is inherently imprecise, because
the randomness of the paths $\omega$ in Theorem 8 can only be captured by an
imprecise forecasting system. The following corollary, which is essentially a
less technical formulation of our main result—Theorem 24 further on in Section
9—shows that the assumption that $\varphi$ is computable is crucial for this
claim: indeed, Corollary 9 shows that there is a precise forecasting system
$\varphi$—so with
$\sup_{s\in\mathbb{S}}[\overline{\varphi}(s)-\underline{\varphi}(s)]=0$—such
that $\omega$ is R-random for $[p,q]$ if and only if it is R-random for
$\varphi$. Hence, for this particular $\varphi$, there is no path
$\omega\in\Omega$ that is R-random for $[p,q]$ but not for $\varphi$. We
postpone an exact formulation and proof of Theorem 24 to Section 9, since that
requires even more mathematical technicalities.

######  Corollary 9.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any interval forecast $[p,q]\in\mathscr{I}$ with $p<q$. Then there is a
precise forecasting system $\varphi\in\Phi$, with $\varphi\subseteq[p,q]$,
such that any path $\omega\in\Omega$ is R-random for $\varphi$ if and only if
it is R-random for $[p,q]$.

###### Proof.

It is an immediate consequence of Theorem 24 that there is some precise
forecasting system $\varphi\in\Phi$, with $\varphi\subseteq[p,q]$, such that a
path $\omega\in\Omega$ is R-random for $[p,q]$ if and only if it is R-random
for $\varphi$. ∎

By Theorem 8, the precise forecasting system $\varphi$ in Corollary 9 is then
necessarily non-computable, as well as non-stationary.

######  Corollary 10.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
any precise forecasting system $\varphi\in\Phi$ and any interval forecast
$[p,q]\in\mathscr{I}$ with $p<q$. If
$\Omega_{\textnormal{R}}(\varphi)=\Omega_{\textnormal{R}}([p,q])$, then
$\varphi$ must be non-computable and non-stationary.

###### Proof.

Since $q-p>0$ by assumption, and since
$\sup_{s\in\mathbb{S}}[\overline{\varphi}(s)-\underline{\varphi}(s)]=0<q-p$
due to the precision of $\varphi$, it follows from Theorem 8 that $\varphi$
must be non-computable, because, otherwise, this theorem would guarantee that
there is some some path $\omega\in\Omega$ that is R-random for $[p,q]$ but not
R-random for $\varphi$.

To conclude, we prove that the precise forecasting system $\varphi$ can’t be
stationary either. Indeed, assume _ex absurdo_ that $\varphi(s)=r\in[0,1]$ for
all $s\in\mathbb{S}$. Theorem 8 guarantees that there is some path
$\omega\in\Omega$ that is R-random for $[p,q]$, but that is not R-random for
any computable forecasting system whose highest imprecision is smaller than
that of $[p,q]$. By our assumption, however, $\omega$ must also be R-random
for $\varphi$, or in other words, for $r$. Now, there always is some
computable interval forecast $[\underline{r},\overline{r}]$ such that
$r\in[\underline{r},\overline{r}]$ and $\overline{r}-\underline{r}<q-p$. Since
$\omega$ is R-random for $r$ by assumption, it is also R-random for
$[\underline{r},\overline{r}]$ by Proposition 6, and this contradicts the
assumption that $\omega$ is not R-random for any computable forecasting system
whose highest imprecision is smaller than that of $[p,q]$. ∎

We repeat that, in the martingale-theoretic setting, our main result
complements Theorem 8 by showing the importance of the computability
assumption on the precise forecasting systems. It turns out that our main
result is also interesting from a measure-theoretic randomness perspective,
since we’ll see below it readily leads to corollaries that are reminiscent of
existing measure-theoretic randomness results. The measure-theoretic
randomness notion that we consider for this purpose is _uniform randomness_ ,
which, as mentioned in the Introduction, allows us to consider the randomness
of a path with respect to an effectively closed—or compact—class of measures.
In particular, there is a test such that a path $\omega$ passes this test if
and only if it is uniformly random with respect to at least one member of the
considered class of measures [7, Theorem 5.23 and Remark 5.24]. Our next
result shows that our martingale-theoretic notion of randomness satisfies a
similar property: a path $\omega\in\Omega$ is random for a stationary interval
forecast if and only if it is random for at least one compatible precise
forecasting system.

######  Corollary 11.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any stationary interval forecast $[p,q]\in\mathscr{I}$. Then a path
$\omega\in\Omega$ is R-random for $[p,q]$ if and only if it is R-random for at
least one compatible precise forecasting system $\varphi\in\Phi$.

###### Proof.

By Proposition 6, the ‘if’ part is straightforward, so we proceed to the ‘only
if’ part. Assume that $\omega$ is R-random for the interval forecast $[p,q]$.
If $p=q$, then $\omega$ is clearly R-random for the compatible price
forecasting system $p=[p,q]$. If $p<q$, then it follows from Corollary 9 that
there is some precise compatible forecasting system $\varphi\in\Phi$ for which
$\omega$ is R-random. ∎

Another measure-theoretic result that we can now show has a martingale-
theoretic counterpart, is the existence of a so-called _neutral_ measure for
which all paths $\omega\in\Omega$ are random. In a measure-theoretic context,
this is true for uniform randomness [7, Theorem 6.2]. We here obtain a similar
result for any of the four martingale-theoretic notions of randomness that we
consider.

######  Corollary 12.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.
Then there is a precise—but necessarily non-stationary and non-
computable—forecasting system $\varphi\in\Phi$ for which all paths
$\omega\in\Omega$ are R-random.

###### Proof.

From Corollary 9, it immediately follows that there is some precise
forecasting system $\varphi\in\Phi$ such that
$\Omega_{\textnormal{R}}(\varphi)=\Omega_{\textnormal{R}}([0,1])$, and hence,
by Proposition 5, $\Omega_{\textnormal{R}}(\varphi)=\Omega$. Corollary 10 then
implies that $\varphi$ is necessarily non-stationary and non-computable. ∎

We find this result to be particularly intriguing. Proposition 5 guarantees
that every path $\omega\in\Omega$ is random for the vacuous forecasting
system. But since all precise forecasting systems are compatible with the
vacuous forecasting system, Corollary 11 then tells us that this amounts to
every path $\omega\in\Omega$ being random for at least one precise forecasting
system. The result above strengthens this, by showing that there is in fact
one single precise forecasting system for wich all paths are random.

Where does this discussion leave us? Corollaries 9 and 10 show that the
randomness of a path $\omega\in\Omega$ with respect to an interval forecast
$[p,q]\in\mathscr{I}$ with $p<q$, be it computable or not, can be equivalently
described by a precise forecasting system that is then necessarily _non-
computable_ and non-stationary. This furthermore implied, as we have seen in
Corollary 11, that randomness with respect to a stationary interval forecast
can be equivalently described in terms of the compatible precise forecasting
systems. It may therefore seem that, on purely theoretical grounds, stationary
imprecise forecasting systems are not needed in the study of algorithmic
randomness. However, if we want to maintain our claim that randomness is
inherently imprecise, Corollaries 10 and 12 tell us we need only explain why
we believe that non-computable forecasting systems are non-satisfactory, and
even fairly useless. We will come to that in Section 10, where we argue why
the computability assumption on the forecasting system is justified on
practical grounds. But before getting to that, we now devote ourselves to the
formulation and proof of Theorem 24, and to introducing the requisite
mathematical machinery.

##  7 Global uncertainty models and almost sure events

We will not only consider ‘local’ gambles on the sample space $\\{0,1\\}$, as
we did in Section 2, but also ‘global’ gambles $f\colon\Omega\to\mathbb{R}$,
which are bounded maps from the set $\Omega$ of all paths to the real numbers.
We collect all such gambles in the set $\mathscr{L}(\Omega)$. With every
subset $A\subseteq\Omega$, which we call an _event_ , we associate the gamble
$\mathbb{I}_{A}\in\mathscr{L}(\Omega)$ which assumes the value $1$ on $A$ and
$0$ elsewhere, and call it the _indicator_ of $A$; observe that, since
$0\leq\mathbb{I}_{A}(\omega)\leq 1$ for any $\omega\in\Omega$,
$\mathbb{I}_{A}$ is bounded and hence indeed a gamble. The complement
$\Omega\setminus A$ of an event $A\in\Omega$ is denoted by $A^{c}$ and its
indicator $\mathbb{I}_{A^{c}}$ satisfies
$\mathbb{I}_{A}=1-\mathbb{I}_{A^{c}}$.

Similarly to considering upper and lower expectations of local gambles with
respect to interval forecasts in Section 2, we can also associate global upper
and lower expectations with global gambles $f\in\mathscr{L}(\Omega)$, but now
with respect to forecasting systems $\varphi\in\Phi$. We do so by adopting the
so-called game-theoretic [2, Equations (6) and (7)]444Several versions of
these definitions exist, which differ only in the type of supermartingales
that are used (real-valued, extended real-valued, unbounded, bounded, bounded
below) [2, 26, 27, 28, 29]. For gambles, however, all these definitions are
equivalent. We adopt the version in [2] for reasons of simplicity, as it
allows us to use the same supermartingales we introduced in Section 3. upper
expectation $\overline{E}^{\varphi}$ and lower expectation
$\underline{E}^{\varphi}$, which are defined by

$\displaystyle\overline{E}^{\varphi}(f)$
$\displaystyle\coloneqq\inf\big{\\{}M(\square)\colon
M\in\overline{\mathbb{M}}(\varphi)\text{ and
}\liminf_{n\to\infty}M(\omega_{1:n})\geq f(\omega)\text{ for
all~{}$\omega\in\Omega$}\big{\\}}\text{ for all }f\in\mathscr{L}(\Omega),$ and
$\displaystyle\underline{E}^{\varphi}(f)$
$\displaystyle\coloneqq\sup\big{\\{}M(\square)\colon
M\in\underline{\mathbb{M}}(\varphi)\text{ and
}\limsup_{n\to\infty}M(\omega_{1:n})\leq f(\omega)\text{ for
all~{}$\omega\in\Omega$}\big{\\}}\text{ for all }f\in\mathscr{L}(\Omega).$

These global upper and lower expectations are related to each other through
the following conjugacy relationship [2, Equation (8)]:
$\overline{E}^{\varphi}(f)=-\underline{E}^{\varphi}(-f)$ for all
$f\in\mathscr{L}(\Omega)$.

The global upper expectation $\overline{E}^{\varphi}(f)$ is the infimum
initial capital for which Sceptic can adopt a betting strategy that guarantees
her ending up with a higher capital than the reward that is associated with
$f$, along all paths. Moreover, $\overline{E}^{\varphi}$ satisfies the
following properties, which resemble C1–C5.

######  Proposition 13 ([2, Proposition 2]).

Consider any forecasting system $\varphi\in\Phi$. Then for all gambles
$f,g\in\mathscr{L}(\Omega)$ and all $\mu\in\mathbb{R}$ and
$\lambda\in\mathbb{R}_{\geq 0}$:

  1. E1.

$\inf f\leq\overline{E}^{\varphi}(f)\leq\sup f$ [boundedness]

  2. E2.

$\overline{E}^{\varphi}(\lambda f)=\lambda\overline{E}^{\varphi}(f)$ [non-
negative homogeneity]

  3. E3.

$\overline{E}^{\varphi}(f+g)\leq\overline{E}^{\varphi}(f)+\overline{E}^{\varphi}(g)$
[subadditivity]

  4. E4.

$\overline{E}^{\varphi}(f+\mu)=\overline{E}^{\varphi}(f)+\mu$ [constant
additivity]

  5. E5.

if $f\leq g$ then $\overline{E}^{\varphi}(f)\leq\overline{E}^{\varphi}(g)$
[monotonicity]

For any event $A\subseteq\Omega$ and any forecasting system $\varphi$, global
upper and lower expectations allow us to also define their corresponding
_lower and upper probabilities_ :
$\underline{P}^{\varphi}(A)\coloneqq\underline{E}^{\varphi}(\mathbb{I}_{A})$
and
$\overline{P}^{\varphi}(A)\coloneqq\overline{E}^{\varphi}(\mathbb{I}_{A})$. We
say that an event $A$ is _almost sure_ for a forecasting system $\varphi$ if
$\underline{P}^{\varphi}(A)=1$; if the forecasting system $\varphi$ is not
important, or clear from the context, we simply say that $A$ is almost sure.
Observe that by E4 and conjugacy,

$\overline{P}^{\varphi}(A^{c})=\overline{E}^{\varphi}(\mathbb{I}_{A^{c}})=\overline{E}^{\varphi}(1-\mathbb{I}_{A})=1+\overline{E}^{\varphi}(-\mathbb{I}_{A})=1-\underline{E}^{\varphi}(\mathbb{I}_{A})=1-\underline{P}^{\varphi}(A)\text{
for all }A\subseteq\Omega.$

Hence, an event $A$ is almost sure if and only if
$\overline{P}^{\varphi}(A^{c})=0$. This alternative characterisation is often
more convenient in proofs, and we will use it implicitly.

There are two features of almost sure events that will be useful to us. The
first is that they are never empty.

######  Proposition 14.

Any almost sure event $A\subseteq\Omega$ is non-empty.

###### Proof.

Assume _ex absurdo_ that $A$ is empty. This would imply that $A^{c}=\Omega$
and therefore, since $A$ is almost sure, that
$\overline{P}^{\varphi}(\Omega)=0$. But it follows from property E1 that,
actually, $\overline{P}^{\varphi}(\Omega)=\overline{E}^{\varphi}(1)=1$. ∎

The second feature is that countable intersections of almost sure events are
still almost sure. We start with finite intersections.

######  Lemma 15.

Consider two almost sure events $A,B\subseteq\Omega$, then $A\cap B$ is almost
sure as well.

###### Proof.

Since $A$ and $B$ are almost sure events, we know that
$\overline{P}^{\varphi}(A^{c})=0$ and $\overline{P}^{\varphi}(B^{c})=0$. By
invoking properties E1, E3 and E5, it follows that

$\displaystyle
0\overset{\text{\ref{prop:globalbound}}}{\leq}\overline{E}^{\varphi}(\mathbb{I}_{(A\cap
B)^{c})})=\overline{E}^{\varphi}(\mathbb{I}_{A^{c}\cup
B^{c}})\overset{\text{\ref{prop:increasingness}}}{\leq}\overline{E}^{\varphi}(\mathbb{I}_{A^{c}}+\mathbb{I}_{B^{c}})\overset{\text{\ref{prop:subadditivity}}}{\leq}\overline{E}^{\varphi}(\mathbb{I}_{A^{c}})+\overline{E}^{\varphi}(\mathbb{I}_{B^{c}})=\overline{P}^{\varphi}(A^{c})+\overline{P}^{\varphi}(B^{c})=0.$

So $\overline{P}^{\varphi}((A\cap B)^{c})=0$ and, therefore, $A\cap B$ is
almost sure. ∎

By combining this result with the following lemma, we obtain the version for
countable intersections.

######  Lemma 16.

Consider any non-decreasing sequence $(f_{n})_{n\in{\mathbb{N}_{0}}}$ in
$\mathscr{L}(\Omega)$ that converges pointwise to a gamble
$f\in\mathscr{L}(\Omega)$. Then
$\overline{E}^{\varphi}(f)=\lim_{n\to\infty}\overline{E}^{\varphi}(f_{n})$.

###### Proof.

From [27, Equation (5) and Proposition 10], it follows that the global upper
expectation $\overline{E}^{\varphi}(f)$, with $f\in\mathscr{L}(\Omega)$, can
be equivalently defined in terms of bounded below supermartingales. By [26,
Proposition 36], this equivalence continues to hold when considering extended
real-valued bounded below supermartingales. Consequently, this lemma follows
from [26, Theorem 23]. ∎

######  Corollary 17.

For any sequence $(A_{n})_{n\in{\mathbb{N}_{0}}}$ of almost sure events,
$\bigcap_{n\in{\mathbb{N}_{0}}}A_{n}$ is almost sure.

###### Proof.

For any $n\in{\mathbb{N}_{0}}$, we know from Lemma 15 that the event
$\bigcap_{k=0}^{n}A_{k}$ is almost sure and, therefore, that
$0=\overline{P}^{\varphi}((\bigcap_{k=0}^{n}A_{k})^{c})=\overline{P}^{\varphi}(\bigcup_{k=0}^{n}A^{c}_{k})$.
Since the sequence
$(\mathbb{I}_{\bigcup_{k=0}^{n}A^{c}_{k}})_{n\in{\mathbb{N}_{0}}}$ in
$\mathscr{L}(\Omega)$ is non-decreasing and converges pointwise to the gamble
$\mathbb{I}_{\bigcup_{n\in{\mathbb{N}_{0}}}A^{c}_{n}}\in\mathscr{L}(\Omega)$,
it follows from Lemma 16 that

$\displaystyle\overline{P}^{\varphi}((\bigcap_{n\in{\mathbb{N}_{0}}}A_{n})^{c})=\overline{P}^{\varphi}(\bigcup_{n\in{\mathbb{N}_{0}}}A^{c}_{n})=\overline{E}^{\varphi}(\mathbb{I}_{\bigcup_{n\in{\mathbb{N}_{0}}}A^{c}_{n}})=\lim_{n\to\infty}\overline{E}^{\varphi}(\mathbb{I}_{\bigcup_{k=0}^{n}A^{c}_{k}})=\lim_{n\to\infty}\overline{P}^{\varphi}(\bigcup_{k=0}^{n}A^{c}_{k})=0,$

so $\bigcap_{n\in{\mathbb{N}_{0}}}A_{n}$ is indeed almost sure. ∎

##  8 Several frequentist notions of randomness

Inspired by von Mises and Wald’s work [11, 10, 9], which we mentioned in the
Introduction, we will also consider a number of very general frequentist
notions of randomness, in addition to the four martingale-theoretic randomness
notions mentioned in Section 5. In particular, we will consider a path
$\omega\in\Omega$ to be random for a forecasting system $\varphi\in\Phi$ and a
countable set of selection processes $\mathscr{S}$ if the frequencies of ones
along all infinite subsequences of $\omega$ selected by these selection
processes are bounded by $\varphi$, in the following sense.

######  Definition 4.

Consider any countable set of selection processes $\mathscr{S}$. Then a path
$\omega\in\Omega$ is $\mathscr{S}$-random for a forecasting system
$\varphi\in\Phi$ if for every selection process $S\in\mathscr{S}$ for which
$\lim_{n\to\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=\infty$,

$\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\underline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\geq
0\text{ and
}\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\overline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq
0.$

For a stationary forecasting system $I\in\mathscr{I}$, the conditions in this
definition simplify to the perhaps more intuitive requirement that

$\min
I\leq\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq\max
I.$

If we restrict our attention to the set of all recursive selection
processes—which, as mentioned in the Introduction [10, 12], is countable—then
the above randomness notion coincides with the notion of Church (CH)
randomness that we introduced elsewhere, and similarly for recursive temporal
selection processes and weak Church (wCH) randomness [19].

######  Definition 5 ([19, Definition 6]).

A path $\omega\in\Omega$ is CH-random (wCH-random) for a forecasting system
$\varphi\in\Phi$ if for every recursive (recursive temporal) selection process
$S$ for which $\lim_{n\to\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=\infty$,

$\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\underline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\geq
0\text{ and
}\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\overline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq
0.$

In order to establish that Definition 4 is meaningful, and therefore
Definition 5 as well, we proceed as in Section 5 and prove that for every
forecasting system $\varphi$ and every countable set of selection processes
$\mathscr{S}$, there is at least one $\mathscr{S}$-random path for $\varphi$.
Observe that this extends the work of Wald that we mentioned in the
Introduction. We will make use of the following lemma.

######  Lemma 18 ([2, Theorem 21]).

For any forecasting system $\varphi$, any selection process $S$ and any gamble
$f\in\mathscr{L}(\\{0,1\\})$, the event

$\displaystyle\bigg{\\{}\omega\in\Omega\colon\text{if
}\lim_{n\to\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=\infty\text{ then
}\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})\big{[}f(\omega_{k+1})-\underline{E}_{\varphi(\omega_{1:k})}(f)\big{]}}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\geq
0\bigg{\\}}$

is almost sure for $\varphi$.

From Lemma 18 and Corollary 17, it will readily follow that for any
forecasting system $\varphi$ and any countable set of selection processes
$\mathscr{S}$, the corresponding set of $\mathscr{S}$-random paths is almost
sure for $\varphi$, and hence, by Proposition 14, there will be at least one
path that is $\mathscr{S}$-random for $\varphi$.

######  Proposition 19.

Consider any forecasting system $\varphi$ and any countable set of selection
processes $\mathscr{S}$. Then the event $\\{\omega\in\Omega\colon\omega\text{
is $\mathscr{S}$-random for }\varphi\\}$ is almost sure for $\varphi$.

###### Proof.

We start by associating two events $A^{+}_{S},A^{-}_{S}\subseteq\Omega$ with
every selection process $S\in\mathscr{S}$, defined by

$\displaystyle A^{+}_{S}$
$\displaystyle\coloneqq\bigg{\\{}\omega\in\Omega\colon\text{if
}\lim_{n\to\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=\infty\text{ then
}\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\underline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\geq
0\bigg{\\}}$ and $\displaystyle A^{-}_{S}$
$\displaystyle\coloneqq\bigg{\\{}\omega\in\Omega\colon\text{if
}\lim_{n\to\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=\infty\text{ then
}\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})[\omega_{k+1}-\overline{\varphi}(\omega_{1:k})]}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq
0\bigg{\\}}.$

Lemma 18 with $f=X$ implies that the event $A^{+}_{S}$ is almost sure for
$\varphi$, and similarly, Lemma 18 with $f=-X$ implies that the event
$A^{-}_{S}$ is almost sure for $\varphi$.

Since the set of selection processes $\mathscr{S}$ is countable, and since we
associated with every selection process $S\in\mathscr{S}$ two events
$A^{+}_{S}$ and $A^{-}_{S}$, the set of all these events is countable as well,
and hence, by Corollary 17, the event
$\bigcap_{S\in\mathscr{S},z\in\\{+,-\\}}A^{z}_{S}$ is almost sure for
$\varphi$. By Definition 4, the set
$\bigcap_{S\in\mathscr{S},z\in\\{+,-\\}}A^{z}_{S}$ is the set of paths that
are $\mathscr{S}$-random for $\varphi$. Hence, indeed, the event
$\\{\omega\in\Omega\colon\omega\text{ is $\mathscr{S}$-random for }\varphi\\}$
is almost sure for $\varphi$. ∎

######  Corollary 20.

For any forecasting system $\varphi$ and any countable set of selection
processes $\mathscr{S}$, there is at least one path $\omega\in\Omega$ that is
$\mathscr{S}$-random for $\varphi$.

###### Proof.

This is an immediate consequence of Propositions 14 and 19. ∎

If we restrict our attention to interval forecasts $I\in\mathscr{I}$ that stay
away from zero and one, in the sense that $I\subseteq(0,1)$, and only consider
notions of $\mathscr{S}$-randomness that are stronger than wCH-randomness—so
with $\mathscr{S}$ a superset of the recursive temporal selection
processes—then we can also say something about the character of the
$\mathscr{S}$-random paths for $I$: they are non-recursive.

######  Proposition 21.

Consider any path $\omega\in\Omega$ and any interval forecast
$I\subseteq(0,1)$. If $\omega$ is wCH-random for $I$, then it is non-
recursive. The same is true if $\omega$ is $\mathscr{S}$-random for $I$, with
$\mathscr{S}$ a countable superset of the recursive temporal selection
processes, or if $\omega$ is R-random for $I$, for any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.

###### Proof.

Assume _ex absurdo_ that $\omega$ is recursive. Then the temporal selection
processes $S_{0},S_{1}~{}\in~{}\smash{\mathscr{S}}$, defined by
$S_{0}(n)\coloneqq 1-\smash{\omega_{n+1}}$ and
$S_{1}(n)\coloneqq\smash{\omega_{n+1}}$ for all $n\in{\mathbb{N}_{0}}$, are
recursive. Clearly, since $\omega$ is a binary infinite sequence, it holds
that $\lim_{n\to\infty}\smash{\sum_{k=0}^{n-1}}S_{0}(\omega_{1:k})=\infty$ or
$\lim_{n\to\infty}\smash{\sum_{k=0}^{n-1}}S_{1}(\omega_{1:k})=\infty$, and
therefore that

$\displaystyle\lim_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{0}(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S_{0}(\omega_{1:k})}=0\quad\text{or}\quad\lim_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{1}(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S_{1}(\omega_{1:k})}=1.$

However, due to our assumptions about $I$, we also know—using Definition 5 if
$\omega$ is wCH-random, Definition 4 if $\omega$ is $\mathscr{S}$-random, or
[2, Corollary 29] if $\omega$ is R-random—that every recursive temporal
selection process $S$ for which
$\lim_{n\to+\infty}\sum_{k=0}^{n-1}S(\omega_{1:k})=+\infty$ satisfies

$\displaystyle 0<\min
I\leq\liminf_{n\to+\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\quad\text{and}\quad\limsup_{n\to+\infty}\frac{\sum_{k=0}^{n-1}S(\omega_{1:k})\omega_{k+1}}{\sum_{k=0}^{n-1}S(\omega_{1:k})}\leq\max
I<1,$

a contradiction. ∎

In other words, if a path is recursive, meaning that it has a finite
description, then it cannot be random—in any of the senses considered in the
result—with respect to an interval forecast $I$ that stays away from both zero
and one. Consider for example the path that takes the value zero at even
positions and one at the others. Due to the above result, this path cannot be
random with respect to an interval $[p,q]$, unless either $p=0$ or $q=1$. In
fact, it is easy to see that this particular path is only random for the
interval $[0,1]$.

In the next section, we will use an $\mathscr{S}$-random path
$\omega\in\Omega$ to finally craft the special precise forecasting systems we
have been constantly talking about. Due to the above result, this path will
necessarily be non-recursive, and hence not describable in any finite way.

##  9 Proof of the main result

At this point, we have introduced the mathematical apparatus that is necessary
for proving the main result of this paper; we intend to show that for any
interval forecast $[p,q]\in\mathscr{I}$ and any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
there is some (non-stationary non-computable) precise forecasting system
$\varphi\in\Phi$ that has the exact same set of R-random paths as $[p,q]$.

To this end, we consider a special type of precise forecasting system. Fix any
two real numbers $p,q\in[0,1]$ and any path $\varpi\in\Omega$, and consider
the associated temporal precise forecasting system
$\varphi^{\varpi}_{p,q}\in\Phi$, defined by

$\varphi^{\varpi}_{p,q}(n)\coloneqq\begin{cases}p&\text{if }\varpi_{n+1}=0\\\
q&\text{if }\varpi_{n+1}=1\end{cases}\text{ for all }n\in{\mathbb{N}_{0}}.$
(5)

In our main result, Theorem 24 below, we will in particular use paths $\varpi$
that are $\mathscr{S}$-random for an interval forecast $I\subseteq(0,1)$,
where the countable set of selection processes $\mathscr{S}$ is of a special
type. To make clear what such $\mathscr{S}$ are like, we start by associating
with every real process $F$ and every real number $r\in[0,1]$ a temporal
selection process $S^{r}_{F}$, defined by

$S^{r}_{F}(n)\coloneqq\begin{cases}1&\text{if $E_{r}(\Delta F(s))>0$ for some
$s\in\mathbb{S}$ with $|s|=n$}\\\ 0&\text{if $E_{r}(\Delta F(s))\leq 0$ for
all $s\in\mathbb{S}$ with $|s|=n$}\end{cases}\text{ for all
$n\in{\mathbb{N}_{0}}$.}$ (6)

We use these temporal selection processes to associate with every countable
set $\mathscr{F}$ of real processes and every two real numbers $p,q\in[0,1]$
the clearly countable set $\mathscr{S}^{p,q}_{\mathscr{F}}$ of temporal
selection processes, defined by

$\mathscr{S}^{p,q}_{\mathscr{F}}\coloneqq\big{\\{}S^{r}_{F}\colon
F\in\mathscr{F}\text{ and }r\in\\{p,q\\}\big{\\}}.$ (7)

Since $\mathscr{S}^{p,q}_{\mathscr{F}}$ is countable, Corollary 20 guarantees
that there is at least one path that is
$\mathscr{S}^{p,q}_{\mathscr{F}}$-random for a given interval forecast
$I\subseteq(0,1)$.

In this construction of the sets $\mathscr{S}^{p,q}_{\mathscr{F}}$, the
specific countable sets $\mathscr{F}$ of real processes that we will consider,
are the sets $\mathscr{F}_{\textnormal{S}}$, $\mathscr{F}_{\textnormal{C}}$,
$\mathscr{F}_{\textnormal{wML}}$ and $\mathscr{F}_{\textnormal{ML}}$
introduced in Section 4. If we recall that
$\mathscr{F}_{\textnormal{S}}=\mathscr{F}_{\textnormal{C}}\subseteq\mathscr{F}_{\textnormal{wML}}\subseteq\mathscr{F}_{\textnormal{ML}}$,
Equation (7) tells us that

$\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{S}}}=\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{C}}}\subseteq\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{wML}}}\subseteq\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{ML}}}\text{
for all $p,q\in[0,1]$.}$ (8)

The sets $\mathscr{S}^{p,q}_{\mathscr{F}}$ might look a bit artificial, but if
we restrict our attention to _rational_ numbers $p,q\in\mathbb{Q}$ and to
$\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$, then as our next
results shows, the corresponding
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$ are in fact the set of all
recursive temporal selection processes. Since this is exactly the set of
selection processes used in Definition 5 to define wCH-randomness, we conclude
from this that in those particular cases, for any forecasting system
$\varphi$, a path $\varpi\in\Omega$ is
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$-random for $\varphi$ if and
only if it is wCH-random for $\varphi$.

######  Proposition 22.

Consider any two rational numbers $p,q\in[0,1]$ and any
$\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$. Then
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$ consists of all recursive
temporal selection processes.

###### Proof.

We start by proving that every selection process
$S\in\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$ is recursive and
temporal. By Equation (7), we know that $S=S^{r}_{F}$ for some
$F\in\mathscr{F}_{\textnormal{R}}$ and $r\in\\{p,q\\}$. Hence, by Equation
(6), $S=S^{r}_{F}$ is temporal. Furthermore, since the rational process $F$ is
recursive, since $p,q\in\mathbb{Q}$ and since there is a finite algorithm
that, for every $k\in{\mathbb{N}_{0}}$, can enumerate the finite number of
situations $s\in\mathbb{S}$ for which $|s|=k$, it immediately follows that
there is a finite algorithm that can check the inequalities in Equation (6),
so the temporal selection process $S=S^{r}_{F}$ is also recursive.

That, conversely, every recursive temporal selection process belongs to
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$, follows directly from our
next result, Proposition 23. ∎

More generally, for any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$
and any two _real_ numbers $p,q\in[0,1]$, the set
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$ will actually include all
recursive temporal selection processes. Therefore, if a path $\varpi\in\Omega$
is $\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$-random for a forecasting
system $\varphi\in\Phi$, it will in particular also be wCH-random for
$\varphi$. Further on, we will restrict our attention to stationary
forecasting systems $\varphi\in\Phi$ that stay away from zero and one, in the
sense that $\varphi(s)=I\subseteq(0,1)$ for all $s\in\mathbb{S}$, and the
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$-random paths for $I$ will
then necessarily be non-recursive, due to Proposition 21.

######  Proposition 23.

Consider any two real numbers $p,q\in[0,1]$ and any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$.
Then every recursive temporal selection process belongs to
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$.

###### Proof.

Fix any recursive temporal selection process $S$ and consider the temporal
rational test process $F$ defined by $F(n)\coloneqq 1+\sum_{k=0}^{n-1}S(k)$
for all $n\in{\mathbb{N}_{0}}$. Since $S$ is recursive and non-negative, it
readily follows that the rational test process $F$ is recursive and positive,
and therefore $F\in\mathscr{F}_{\textnormal{S}}$. Since
$\mathscr{F}_{\textnormal{S}}=\mathscr{F}_{\textnormal{C}}\subseteq\mathscr{F}_{\textnormal{wML}}\subseteq\mathscr{F}_{\textnormal{ML}}$,
this implies that $F\in\mathscr{F}_{\textnormal{R}}$, and therefore, that
$\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$ contains the temporal
selection process $S^{p}_{F}$.

We conclude the argument by showing that $S^{p}_{F}=S$. To do so, fix any
$n\in{\mathbb{N}_{0}}$. If $S(n)=1$, then for all $s\in\mathbb{S}$ and
$x\in\\{0,1\\}$ with $|s|=n$, we have that $\Delta
F(s)(x)=F(n+1)-F(n)=S(n)=1$, and hence, by C1, $E_{p}(\Delta F(s))=1>0$.
Consequently, by Equation (6), $S^{p}_{F}(n)=1=S(n)$. Otherwise, if $S(n)=0$,
then for all $s\in\mathbb{S}$ and $x\in\\{0,1\\}$ with $|s|=n$, we have that
$\Delta F(s)(x)=F(n+1)-F(n)=S(n)=0$, and hence, by C1, $E_{p}(\Delta F(s))=0$.
As a consequence, by Equation (6), $S^{p}_{F}(n)=0=S(n)$. ∎

Let us now move on to our main result, where we use the special countable sets
of selection processes $\mathscr{S}^{p,q}_{\mathscr{F}}$ and the special
forecasting systems $\varphi^{\varpi}_{p,q}$ to reveal a surprisingly close
connection between non-stationary precise forecasting systems and interval
forecasts.

######  Theorem 24.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
any two real numbers $p,q\in[0,1]$ such that $p<q$, any interval forecast
$I\subseteq(0,1)$, any countable set of selection processes
$\mathscr{S}\supseteq\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{R}}}$, and
any path $\varpi\in\Omega$ that is $\mathscr{S}$-random for $I$. Then a path
$\omega\in\Omega$ is R-random for $\varphi_{p,q}^{\varpi}$ if and only if it
is R-random for $[p,q]$.

In our proof for this result, we make use of the following two lemmas to prove
the implementability of a number of real processes.

######  Lemma 25.

Consider any lower semicomputable real process $F$ and any two natural numbers
$N,K\in\mathbb{N}$. Then the real process $\tilde{F}$, defined by

$\tilde{F}(s)\coloneqq\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}F(s)&\text{if }|s|>N\end{cases}\text{ for all }s\in\mathbb{S},$

is lower semicomputable as well.

###### Proof.

Since the real process $F$ is lower semicomputable, there is a recursive
rational map $q\colon\mathbb{S}\times{\mathbb{N}_{0}}\to\mathbb{Q}$ such that
$q(s,n+1)\geq q(s,n)$ and $F(s)=\lim_{m\to\infty}q(s,m)$ for all
$s\in\mathbb{S}$ and $n\in{\mathbb{N}_{0}}$. Consider now the recursive
rational map $\tilde{q}\colon\mathbb{S}\times{\mathbb{N}_{0}}\to\mathbb{Q}$
defined by

$\tilde{q}(s,n)\coloneqq\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}q(s,n)&\text{if }|s|>N\end{cases}\text{ for all
}s\in\mathbb{S}\text{ and }n\in{\mathbb{N}_{0}}.$

Then for all $s\in\mathbb{S}$ and $n\in{\mathbb{N}_{0}}$,

$\tilde{q}(s,n+1)=\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}q(s,n+1)&\text{if }|s|>N\end{cases}\geq\begin{cases}1&\text{if
}|s|\leq N\\\ \frac{1}{K}q(s,n)&\text{if }|s|>N\end{cases}=\tilde{q}(s,n)$

and

$\lim_{m\to\infty}\tilde{q}(s,m)=\begin{cases}1&\text{if }|s|\leq N\\\
\lim_{m\to\infty}\frac{1}{K}q(s,m)&\text{if
}|s|>N\end{cases}=\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}F(s)&\text{if }|s|>N\end{cases}=\tilde{F}(s),$

and therefore, $\tilde{F}$ is lower semicomputable as well. ∎

######  Lemma 26.

Consider any test process $F$ that is generated by a lower semicomputable
multiplier process, and any two natural numbers $N,K\in\mathbb{N}$. Then the
test process $\tilde{F}$, defined by

$\tilde{F}(s)\coloneqq\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}F(s)&\text{if }|s|>N\end{cases}\text{ for all }s\in\mathbb{S},$

is generated by a lower semicomputable multiplier process as well.

###### Proof.

Let $D$ be the lower semicomputable multiplier process that generates $F$,
meaning that $F=D^{\raisebox{0.5pt}{$\scriptstyle\circledcirc$}}$.

Since $D$ is lower semicomputable, there is a recursive rational map
$q\colon\mathbb{S}\times\\{0,1\\}\times{\mathbb{N}_{0}}\to\mathbb{Q}$ such
that $q(s,x,n+1)\geq q(s,x,n)$ and $D(s)(x)=\lim_{m\to\infty}q(s,x,m)$ for all
$s\in\mathbb{S}$, $x\in\\{0,1\\}$ and $n\in{\mathbb{N}_{0}}$. Since $D$ is a
multiplier process, it is non-negative, and hence, we can safely assume that
the recursive rational map $q$ is non-negative as well; otherwise, we just
replace it by the recursive rational map $\max\\{q,0\\}$. Moreover, since $F$
is generated by the multiplier process $D$, it readily follows that
$\tilde{F}$ is generated by the multiplier process $\tilde{D}$ defined by

$\tilde{D}(s)(x)\coloneqq\begin{cases}1&\text{if }|s|<N\\\
\frac{1}{K}F(sx)&\text{if }|s|=N\\\ D(s)(x)&\text{if }|s|>N\end{cases}\text{
for all }s\in\mathbb{S}\text{ and }x\in\\{0,1\\}.$

So it suffices to prove that $\tilde{D}$ is lower semicomputable. To that end,
consider the recursive rational map
$\tilde{q}\colon\mathbb{S}\times\\{0,1\\}\times{\mathbb{N}_{0}}\to\mathbb{Q}$
defined by

$\tilde{q}(s,x,n)\coloneqq\begin{cases}1&\text{if }|s|<N\\\
\frac{1}{K}\Big{(}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n)\Big{)}q(s,x,n)&\text{if
}|s|=N\\\ q(s,x,n)&\text{if }|s|>N\end{cases}\text{ for all
$s=x_{1:m}\in\mathbb{S}$, $x\in\\{0,1\\}$ and $n\in{\mathbb{N}_{0}}$}.$

Then for all $s=x_{1:m}\in\mathbb{S}$, $x\in\\{0,1\\}$ and
$n\in{\mathbb{N}_{0}}$,

$\displaystyle\tilde{q}(s,x,n+1)$ $\displaystyle=\begin{cases}1&\text{if
}|s|<N\\\
\frac{1}{K}\Big{(}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n+1)\Big{)}q(s,x,n+1)&\text{if
}|s|=N\\\ q(s,x,n+1)&\text{if }|s|>N\end{cases}$
$\displaystyle\geq\begin{cases}\mathrlap{1}\hphantom{\frac{1}{K}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n+1)q(s,x,n+1)}&\text{if
}|s|<N\\\
\frac{1}{K}\Big{(}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n)\Big{)}q(s,x,n)&\text{if
}|s|=N\\\ q(s,x,n)&\text{if }|s|>N\end{cases}$
$\displaystyle=\tilde{q}(s,x,n),$

where the inequality holds because $K>0$ and $q\geq 0$, and

$\displaystyle\lim_{m\to\infty}\tilde{q}(s,x,m)$
$\displaystyle=\begin{cases}\mathrlap{1}\hphantom{\frac{1}{K}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n+1)q(s,x,n+1)}&\text{if
}|s|<N\\\
\frac{1}{K}\lim_{m\to\infty}\Big{(}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},m)\Big{)}q(s,x,m)&\text{if
}|s|=N\\\ \lim_{m\to\infty}q(s,x,m)&\text{if }|s|>N\end{cases}$
$\displaystyle=\begin{cases}\mathrlap{1}\hphantom{\frac{1}{K}\prod_{k=0}^{N-1}q(x_{1:k},x_{k+1},n+1)q(s,x,n+1)}&\text{if
}|s|<N\\\
\frac{1}{K}\Big{(}\prod_{k=0}^{N-1}D(x_{1:k})(x_{k+1})\Big{)}D(s)(x)&\text{if
}|s|=N\\\ D(s)(x)&\text{if }|s|>N\end{cases}$
$\displaystyle=\begin{cases}1&\text{if }|s|<N\\\ \frac{1}{K}F(sx)&\text{if
}|s|=N\\\ D(s)(x)&\text{if }|s|>N\end{cases}$ $\displaystyle=\tilde{D}(s)(x),$

so we see that $\tilde{D}$ is lower semicomputable, as needed. ∎

###### Proof of Theorem 24.

We begin with the direct implication. Assume that $\omega\in\Omega$ is
R-random for $\varphi_{p,q}^{\varpi}$. Since
$\varphi_{p,q}^{\varpi}(n)\subseteq[p,q]$ for all $n\in{\mathbb{N}_{0}}$, it
follows from Proposition 6 that $\omega$ is also R-random for $[p,q]$.

To prove the converse implication, assume that $\omega\in\Omega$ is R-random
for $[p,q]$. Taking into account Definitions 2 and 3, in order to prove that
$\omega$ is R-random for $\varphi_{p,q}^{\varpi}$, we consider any test
supermartingale
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{R}}(\varphi_{p,q}^{\varpi})}$
and prove that it isn’t unbounded on $\omega$ when
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C}\\}$, and
that it isn’t computably unbounded on $\omega$ when
$\textnormal{R}=\textnormal{S}$.

To this end, consider the two temporal selection processes $S_{T}^{p}$ and
$S_{T}^{q}$ as defined by Equation (6). We will take a closer look at the
temporal selection process $S_{T}^{p}$ and prove that there is only a finite
number of non-negative integers $n\in{\mathbb{N}_{0}}$ for which
$S_{T}^{p}(n)=1$. To this end, assume _ex absurdo_ that there is an infinite
number of them, and therefore that
$\lim_{n\to\infty}\sum_{k=0}^{n-1}S_{T}^{p}(k)=\infty$. Consider any
$k\in{\mathbb{N}_{0}}$ such that $S_{T}^{p}(k)=1$, then it follows from
Equation (6) that there is some $s\in\mathbb{S}$ with $|s|=k$ such that
$E_{p}(\Delta T(s))>0$. Since $E_{\varphi_{p,q}^{\varpi}(s)}(\Delta T(s))\leq
0$ (because $\Delta T$ is a supermartingale for $\varphi_{p,q}^{\varpi}$),
this implies that necessarily $\varphi_{p,q}^{\varpi}(s)=q$ and therefore,
since $|s|=k$, we infer from Equation (5) that $\varpi_{k+1}=1$. Since this is
true for every $k\in{\mathbb{N}_{0}}$ such that $S_{T}^{p}(k)=1$, it follows
that

$\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{T}^{p}(k)\varpi_{k+1}}{\sum_{k=0}^{n-1}S_{T}^{p}(k)}=\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{T}^{p}(k)}{\sum_{k=0}^{n-1}S_{T}^{p}(k)}=1.$
(9)

Since
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{R}}(\varphi_{p,q}^{\varpi})}$,
and therefore also $T\in\mathscr{F}_{\textnormal{R}}$, we can infer from
Equation (7) that
$S_{T}^{p}\in\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{R}}}\subseteq\mathscr{S}$.
Consequently, since $\varpi$ is $\mathscr{S}$-random for $I$ by assumption and
since $\lim_{n\to\infty}\sum_{k=0}^{n-1}S_{T}^{p}(k)=\infty$, we find [see
Definition 4] that

$\max
I\geq\limsup_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{T}^{p}(k)\varpi_{k+1}}{\sum_{k=0}^{n-1}S_{T}^{p}(k)}\overset{\eqref{eq:helpiewelpie}}{=}1,$

contradicting the assumption that $I\subseteq(0,1)$. We conclude that, indeed,
there is only a finite number of non-negative integers $n\in{\mathbb{N}_{0}}$
for which $S_{T}^{p}(n)=1$.

In a completely similar manner, it can be shown that there is only a finite
number of non-negative integers $n\in{\mathbb{N}_{0}}$ for which
$S_{T}^{q}(n)=1$. Indeed, assume _ex absurdo_ that there is an infinite number
of them. Then, by adopting a similar argument, it follows that
$\lim_{n\to\infty}\sum_{k=0}^{n-1}S_{T}^{q}(k)=\infty$, that
$S_{T}^{q}\in\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{R}}}\subseteq\mathscr{S}$,
and that for all $k\in{\mathbb{N}_{0}}$, if $S_{T}^{q}(k)=1$, then
$\varpi_{k+1}=0$. That being so, it follows from Definition 4, since $\varpi$
is $\mathscr{S}$-random for $I$ by assumption, that

$\min
I\leq\liminf_{n\to\infty}\frac{\sum_{k=0}^{n-1}S_{T}^{q}(k)\varpi_{k+1}}{\sum_{k=0}^{n-1}S_{T}^{q}(k)}=0,$

contradicting the assumption that $I\subseteq(0,1)$.

Since there are only a finite number of non-negative integers
$n\in{\mathbb{N}_{0}}$ for which $S_{T}^{p}(n)=1$ or $S_{T}^{q}(n)=1$, and
since for each such $n$, there is only a finite number of situations
$s\in\mathbb{S}$ such that $|s|=n$, it follows from Equation (6) that there
are only a finite number of situations $s\in\mathbb{S}$ for which
$E_{p}(\Delta T(s))>0$ or $E_{q}(\Delta T(s))>0$. Hence, there is some
$N\in\mathbb{N}$ such that $\overline{E}_{[p,q]}(\Delta
T(s))=\max\\{E_{p}(\Delta T(s)),E_{q}(\Delta T(s))\\}\leq 0$ for all
$s\in\mathbb{S}$ such that $|s|>N$.

Let $K\in\mathbb{N}$ be any positive natural number such that $K>T(s)$ for all
$s\in\mathbb{S}$ with $|s|=N+1$, and consider the test process
$\tilde{T}\colon\mathbb{S}\to\mathbb{R}$ defined by

$\displaystyle\tilde{T}(s)\coloneqq\begin{cases}1&\text{if }|s|\leq N\\\
\frac{1}{K}T(s)&\text{if }|s|>N\end{cases}\text{ for all }s\in\mathbb{S}.$

We intend to prove that
$\tilde{T}\in\overline{\mathbb{T}}_{\textnormal{R}}([p,q])$. We will do so by
consecutively showing that it is a supermartingale for $[p,q]$, that it is
positive if $\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$, that it is
implementable in the same way as $T$ is, and that $\tilde{T}(\square)=1$.

To prove that $\tilde{T}$ is a supermartingale for $[p,q]$, we fix some
$s\in\mathbb{S}$, and consider three mutually exclusive possibilities:
$|s|<N$, $|s|=N$ and $|s|>N$. If $|s|<N$, then

$\overline{E}_{[p,q]}\big{(}\Delta\tilde{T}(s)\big{)}=\overline{E}_{[p,q]}(0)\overset{\text{\ref{axiom:coherence:bounds}}}{=}0.$

If $|s|=N$, then

$\overline{E}_{[p,q]}(\Delta\tilde{T}(s))=\overline{E}_{[p,q]}\big{(}\tilde{T}(s\,\bullet)-\tilde{T}(s)\big{)}=\overline{E}_{[p,q]}\Big{(}\frac{1}{K}T(s\,\bullet)-1\Big{)}\overset{\text{\ref{axiom:coherence:increasingness}}}{\leq}\overline{E}_{[p,q]}(1-1)\overset{\text{\ref{axiom:coherence:bounds}}}{=}0,$

where the inequality holds because $K>T(t)\geq 0$ for all $t\in\mathbb{S}$
with $|t|=N+1$. Finally, if $|s|>N$, then

$\overline{E}_{[p,q]}(\Delta\tilde{T}(s))=\overline{E}_{[p,q]}\Big{(}\frac{1}{K}\Delta
T(s)\Big{)}\overset{\text{\ref{axiom:coherence:homogeneity}}}{=}\frac{1}{K}\overline{E}_{[p,q]}(\Delta
T(s))\leq 0,$

where in the second equality and final inequality, we also used the fact that
$K>0$.

Observe that $\tilde{T}$ is positive if
$\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$, because then
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{R}}(\varphi_{p,q}^{\varpi})}\subseteq\mathscr{F}_{\textnormal{R}}$
is positive and because $K>0$.

Let us now prove that $\tilde{T}$ is implementable in the same way as $T$ is.
If $\textnormal{R}=\textnormal{ML}$, then
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{ML}}(\varphi_{p,q}^{\varpi})}\subseteq\mathscr{F}_{\textnormal{ML}}$
is lower semicomputable, so it follows from Lemma 25 that $\tilde{T}$ is lower
semicomputable as well. If $\textnormal{R}=\textnormal{wML}$, then
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{wML}}(\varphi_{p,q}^{\varpi})}\subseteq\mathscr{F}_{\textnormal{wML}}$
is generated by a lower semicomputable multiplier process, so it follows from
Lemma 26 that $\tilde{T}$ is generated by a lower semicomputable multiplier
process as well. And finally, if $\textnormal{R}=\textnormal{C}$ or
$\textnormal{R}=\textnormal{S}$, then
$T\in\smash{\overline{\mathbb{T}}_{\textnormal{C}}(\varphi_{p,q}^{\varpi})}=\smash{\overline{\mathbb{T}}_{\textnormal{S}}(\varphi_{p,q}^{\varpi})}\subseteq\mathscr{F}_{\textnormal{C}}=\mathscr{F}_{\textnormal{S}}$
is a rational and recursive process, and it is therefore obvious that this is
true for $\tilde{T}$ as well.

Since also $\tilde{T}(\square)=1$, we conclude that
$\tilde{T}\in\overline{\mathbb{T}}_{\textnormal{R}}([p,q])$. We now consider
two possibilities. If
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C}\\}$, then
since $\omega$ is R-random for $[p,q]$ by assumption, $\tilde{T}$ can’t be
unbounded on $\omega$ by Definition 2. Since also

$\displaystyle\limsup_{n\to\infty}\tilde{T}(\omega_{1:n})<\infty\Rightarrow\limsup_{n\to\infty}\frac{T(\omega_{1:n})}{K}<\infty\overset{K>0}{\Rightarrow}\limsup_{n\to\infty}T(\omega_{1:n})<\infty,$

it then follows that $T$ does not become unbounded on $\omega$.

If $\textnormal{R}=\textnormal{S}$, then since $\omega$ is R-random for
$[p,q]$ by assumption, $\tilde{T}$ can’t be computably unbounded on $\omega$
by Definition 3. Consider now any real growth function $\tau$ and an
associated real growth function $\tilde{\tau}$ defined by
$\tilde{\tau}(n)\coloneqq\nicefrac{{\tau(n)}}{{K}}$ for all
$n\in{\mathbb{N}_{0}}$. It then holds that

$\limsup_{n\to\infty}[\tilde{T}(\omega_{1:n})-\tilde{\tau}(n)]<0\Rightarrow\limsup_{n\to\infty}\bigg{[}\frac{T(\omega_{1:n})}{K}-\frac{\tau(n)}{K}\bigg{]}<0\overset{K>0}{\Rightarrow}\limsup_{n\to\infty}\bigg{[}T(\omega_{1:n})-\tau(n)\bigg{]}<0,$

and hence, since $\tilde{T}$ is not computably unbounded on $\omega$ for the
real growth function $\tilde{\tau}$, $T$ does not become computably unbounded
on $\omega$ for $\tau$. Since this holds for any real growth function $\tau$,
we conclude that $T$ does not become computably unbounded on $\omega$. ∎

According to Theorem 24, for every choice of R in
$\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$, there
is some path $\varpi\in\Omega$ such that the R-random paths for the interval
forecast $[p,q]$ and for the temporal precise forecasting system
$\varphi_{p,q}^{\varpi}$ coincide. Interestingly, there is also a single path
$\varpi\in\Omega$ that does this job for all four notions of randomness that
we consider here. Basically, this is true because the weaker the notion of
randomness, the weaker the conditions on $\varpi$ that are required in Theorem
24, in the sense that the minimally required countable set of selection
processes $\mathscr{S}$ becomes smaller.

######  Corollary 27.

Consider any two real numbers $p,q\in[0,1]$ such that $p<q$, any interval
forecast $I\subseteq(0,1)$, any countable set of selection processes
$\mathscr{S}\supseteq\mathscr{S}_{\mathscr{F}_{\textnormal{ML}}}^{p,q}$, and
any path $\varpi\in\Omega$ that is $\mathscr{S}$-random for $I$. Then, for any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
a path $\omega\in\Omega$ is R-random for $\varphi_{p,q}^{\varpi}$ if and only
if it is R-random for $[p,q]$.

###### Proof.

Since
$\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{S}}}=\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{C}}}\subseteq\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{wML}}}\subseteq\mathscr{S}^{p,q}_{\mathscr{F}_{\textnormal{ML}}}$
by Equation (8), this follows readily from Theorem 24. ∎

If we restrict our attention to rational numbers $p,q\in\mathbb{Q}$ and to
$\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$, then, as proved in
Proposition 22, the set $\mathscr{S}_{\mathscr{F}_{\textnormal{R}}}^{p,q}$
consists of the recursive temporal selection processes, and hence, by
comparing Definitions 4 and 5, the conditions on $\varpi$ that are required in
Theorem 24 translate into $\varpi$ being wCH-random for an interval forecast
$I\subseteq(0,1)$.

######  Corollary 28.

Consider any $\textnormal{R}\in\\{\textnormal{C},\textnormal{S}\\}$, any two
rational numbers $p,q\in[0,1]$ such that $p<q$, any interval forecast
$I\subseteq(0,1)$, and any path $\varpi\in\Omega$ that is wCH-random for $I$.
Then a path $\omega\in\Omega$ is R-random for $\varphi_{p,q}^{\varpi}$ if and
only if it is R-random for $[p,q]$.

##  10 Theoretical and practical necessity of interval forecasts in statistics

Let’s now zoom out and move away from the technicalities in the previous
sections, in order to better understand the implications of Theorem 24 and its
Corollary 9. In trying to come to a better understanding, we have found it
useful to look at these results from the point of view of statistics, whose
aim it is to learn an uncertainty model from data. Regarding the data, we will
consider a finite sequence $\omega_{1:n}$ and assume that it is an initial
segment of an idealised (and unobserved) path $\omega$ that is (ML-, wML-, C-
or S-)random; there are clearly a multitude of forecasting systems for which
this is the case. Under this assumption, we will examine what forecasting
systems—that make the path $\omega$ random—can be learned from the finite
initial segment $\omega_{1:n}$. Notice that, whilst doing so, we have changed
our point of view: instead of focusing on the paths that are random for a
forecasting system $\varphi\in\Phi$, as we have done before, we have a look at
the forecasting systems that make a path $\omega\in\Omega$ random. Even though
it is commonly assumed that the uncertainty model $\varphi$ to be estimated or
identified from the data $\omega_{1:n}$ is precise, we have put forward
elsewhere [2] a number of arguments that question the assumption that a path’s
randomness should always be described by a precise forecasting system
$\varphi$. So, in the discussion below, we want to remain open about that
possibility, and see what can be said if we don’t assume a priori that the
sequence $\omega$ is necessarily random for a precise forecasting system.

From Proposition 5, we know that there is at least one candidate (stationary)
interval forecast that makes $\omega$ random: all paths are random for the
unit interval $[0,1]$. In fact, interestingly, there is (almost always) a
smallest (stationary) interval forecast $[p,q]$ that makes $\omega$ random
[19]. Meanwhile, it is not guaranteed that there is a stationary precise
forecast $p$ that makes $\omega$ random; the smallest (stationary) interval
forecast $[p,q]$ that makes $\omega$ random needn’t be a singleton [2, Section
9.1]. Hence, generally speaking, imprecision is needed if we insist on a
stationary uncertainty model to describe a path’s randomness. If we also allow
for non-stationary uncertainty models however, then Theorem 24 shows that we
could replace $[p,q]$ by a non-stationary precise forecasting system
$\varphi_{p,q}^{\varpi}$, with $\varpi$ chosen as in Theorem 24. In fact,
there is an even more (theoretically) straightforward way to associate a non-
stationary precise forecasting system with a path $\omega$: the temporal
forecasting system $\varphi_{0,1}^{\omega}$ that assigns probability $1$ to
the actual next value, and hence, makes a perfect prediction.

######  Proposition 29.

Consider any
$\textnormal{R}\in\\{\textnormal{ML},\textnormal{wML},\textnormal{C},\textnormal{S}\\}$,
then any path $\omega\in\Omega$ is R-random for the precise forecasting system
$\varphi_{0,1}^{\omega}$.

###### Proof.

Consider any test supermartingale
$T\in\overline{\mathbb{T}}_{\textnormal{R}}(\varphi_{0,1}^{\omega})$. Since
$T$ is a supermartingale for $\varphi_{0,1}^{\omega}$, it holds for any
$n\in{\mathbb{N}_{0}}$ that

$\displaystyle 0\geq E_{\varphi_{0,1}^{\omega}(\omega_{1:n})}(\Delta
T(\omega_{1:n}))$ $\displaystyle=\begin{cases}E_{0}(\Delta
T(\omega_{1:n}))&\text{if }\omega_{n+1}=0\\\ E_{1}(\Delta
T(\omega_{1:n}))&\text{if }\omega_{n+1}=1\end{cases}$
$\displaystyle=\begin{cases}\mathrlap{\Delta
T(\omega_{1:n})(0)}\hphantom{E_{0}(\Delta T(\omega_{1:n}))}&\text{if
}\omega_{n+1}=0\\\ \Delta T(\omega_{1:n})(1)&\text{if
}\omega_{n+1}=1\end{cases}=\Delta T(\omega_{1:n})(\omega_{n+1}),$

and therefore,

$\displaystyle T(\omega_{1:n})=T(\square)+\sum_{k=0}^{n-1}\Delta
T(\omega_{1:k})(\omega_{k+1})\leq T(\square)=1.$

Consequently, all test supermartingales
$T\in\overline{\mathbb{T}}_{\textnormal{R}}(\varphi_{0,1}^{\omega})$ are
bounded above by $1$ along $\omega$. It therefore holds [see Definitions 2 and
3] that $\omega$ is R-random for $\varphi_{0,1}^{\omega}$. ∎

Hence, if $\omega$ is random for $[p,q]$, then it is also random for at least
two non-stationary precise models. We won’t risk getting bogged down into a
discussion on what uncertainty models are best associated with a path
$\omega$; that would require a paper on its own. But we do want to point out
that the uncertainty models that correspond with $\omega$ typically do not
contain the same information; that is, they do not share the same set of
random paths. Interestingly, however, as we know from Theorem 24, $[p,q]$ and
$\varphi_{p,q}^{\varpi}$ do have the same set of random paths and are, in that
sense, equally expressive. On that ground, theoretically, one might argue that
the imprecision in $[p,q]$ is not needed.

We believe that this story changes when moving to more practical grounds. If
we are given an initial finite segment $\omega_{1:n}$ of a path
$\omega\in\Omega$ and want to learn a forecasting system $\varphi$ for which
$\omega$ is random, we will have to do so by adopting a finite algorithm that,
given the data $\omega_{1:n}$, outputs a forecasting system $\varphi^{\prime}$
whose set of random paths is then believed to contain $\omega$. A candidate
for $\varphi^{\prime}$ could be the forecasting system
$\varphi_{0,1}^{\omega}$ that is generated by $\omega$ itself. However, it is
unfeasible to learn this forecasting system, or to even approximate it, as it
basically requires us to know the entire path $\omega$ itself.

Another candidate for $\varphi^{\prime}$ could be the non-computable
forecasting system $\varphi_{p,q}^{\varpi}$. Here too, however, it seems
impossible to learn or even approximate this model because it requires us to
learn the path $\varpi$, which is non-recursive by Proposition 21. At the same
time, learning a stationary interval forecast $[p,q]$—which is as expressive
as $\varphi_{p,q}^{\varpi}$—seems a much less daunting, and practically more
feasible, task, especially if $[p,q]$ is computable.

In summary, it is one thing to associate precise uncertainty models with a
path $\omega$ that has no precise stationary forecast, but it is another thing
to actually learn them. When it comes to the latter, computable stationary
interval forecasts seem more promising than non-computable non-stationary
precise ones.

##  11 Conclusions and future work

We conclude that precision and computability are not always compatible when
describing a path’s randomness. Indeed, if you require computability, then
Theorem 8 shows that you should allow for imprecision as there is at least one
path $\omega\in\Omega$ whose randomness can be described by a computable
interval forecast $[p,q]$, but not by any computable precise forecasting
system $\varphi\in\Phi$. On the other hand, if you require precision, then
Theorem 8 and 24 show that you should allow for non-computability since the
path $\omega$ is random for the non-computable precise forecasting system
$\varphi_{p,q}^{\varpi}$, but not for any computable precise one. We repeat
that the above holds because interval forecasts $[p,q]$ have the same sets of
martingale-theoretically random paths as the related non-computable non-
stationary precise forecasting systems $\varphi_{p,q}^{\varpi}$, while being
simpler and stationary. Moreover, our preliminary analysis suggests that the
stationary character of interval forecasts will be of the utmost importance
when moving to the field of statistics. In particular, it seems neither
possible nor opportune to try and learn—or even approximate—the non-computable
non-stationary precise forecasting systems $\varphi_{p,q}^{\varpi}$, which—by
definition—cannot be described by a finite algorithm, from a finite initial
path segment $\omega_{1:n}$.

In our future work, we plan to further explore these preliminary ideas about a
randomness-based approach to statistics, and try to develop new statistical
methods based on them.

Moreover, we want to explore whether the theorems and ideas for martingale-
theoretic randomness in this paper apply equally well to frequentist notions
of randomness, like the ones in Section 8. Our preliminary investigation seems
to indicate that, similarly to what Theorem 8 states, there are paths that are
Church random for an interval forecast $I\in\mathscr{I}$, but not for any
computable (more) precise forecasting system; it is an open question whether a
similar property holds for weak Church randomness. Meanwhile, and in contrast
with Theorem 24, we suspect that if there is a precise forecasting system that
has the exact same set of (weak) Church random paths as a non-vanishing
interval forecast, then it must be non-temporal, and therefore can’t be of the
form $\varphi_{p,q}^{\varpi}$.

Lastly, we intend to explore whether the proof of Theorem 24 can be modified
to allow for arbitrary forecasting systems $\varphi$ rather than only
stationary interval forecasts.

##  12 Acknowledgements

Work on this paper was supported by the Research Foundation – Flanders (FWO),
project numbers 11H5521N (for Floris Persiau) and 3G028919 (for Jasper De Bock
and Gert de Cooman).

## References

  * [1] Gert De Cooman and Jasper De Bock.  Computable randomness is inherently imprecise.  In Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications, volume 62 of Proceedings of Machine Learning Research, pages 133–144, 2017.
  * [2] Gert De Cooman and Jasper De Bock.  Randomness is inherently imprecise.  International Journal of Approximate Reasoning, 141:28–68, 2022\.  URL: https://www.sciencedirect.com/science/article/pii/S0888613X21000992.
  * [3] Gert De Cooman and Jasper De Bock.  Randomness and imprecision: A discussion of recent results.  In Proceedings of the Twelfth International Symposium on Imprecise Probability: Theories and Applications, volume 147 of Proceedings of Machine Learning Research, pages 110–121, 2021.
  * [4] Vladimir Vovk and Alexander Shen.  Prequential randomness and probability.  Theoretical Computer Science, 411(29):2632–2646, 2010.
  * [5] L. A. Levin.  On the notion of a random sequence.  In Soviet Math. Dokl., volume 14, pages 1413–1416, 1973.
  * [6] L. A. Levin.  Uniform tests of randomness.  In Soviet Math. Dokl., volume 17, pages 337–340, 1976.
  * [7] Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas, and Alexander Shen.  Algorithmic tests and randomness with respect to a class of measures.  Computing Research Repository - CORR, 274, 03 2011.  doi:10.1134/S0081543811060058.
  * [8] Rodney G. Downey and Denis R. Hirschfeldt.  Algorithmic Randomness and Complexity.  Springer, New York, 2010.
  * [9] R. Von Mises.  Grundlagen der Wahrscheinlichkeitsrechnung.  Mathematische Zeitschrift, 5:52–99, 1919.
  * [10] Klaus Ambos-Spies and Antonín Kucera.  Randomness in computability theory.  Contemporary Mathematics, 257:1–14, 2000.
  * [11] Abraham Wald.  Die widerspruchsfreiheit des kollektivbegriffess der wahrscheinlichkeitsrechnung.  Ergebnisse eines Math, 8:38–72, 1937.
  * [12] Alonzo Church.  On the concept of a random sequence.  Bulletin of the American Mathematical Society, 46(2):130 – 135, 1940.
  * [13] Per Martin-Löf.  The definition of random sequences.  Information and Control, 9(6):602–619, 1966.  URL: https://www.sciencedirect.com/science/article/pii/S0019995866800189, doi:https://doi.org/10.1016/S0019-9958(66)80018-9.
  * [14] Claus P. Schnorr.  Zufälligkeit und Wahrscheinlichkeit: Eine algorithmische Begründung der Wahrscheinlichkeitstheorie.  Springer, Berlin, 1971.
  * [15] Klaas Landsman and Ellen van Wolde.  The Challenge of Chance: A Multidisciplinary Approach from Science and the Humanities.  Springer Open, Switzerland, 2016.
  * [16] Bjørn Kjos-Hanssen.  The probability distribution as a computational resource for randomness testing.  Journal of Logic and Analysis, 2:1–13, 2010.
  * [17] Bjørn Kjos-Hanssen, Antoine Taveneaux, and Neil Thapen.  How much randomness is needed for statistics?  In How the World Computes, pages 395–404, Berlin, Heidelberg, 2012\. Springer Berlin Heidelberg.
  * [18] Floris Persiau, Jasper De Bock, and Gert De Cooman.  Computable randomness is about more than probabilities.  Lecture Notes in Computer Science, 12322:172–186, 2020.  see [25] for an extended version.
  * [19] Floris Persiau, Jasper De Bock, and Gert De Cooman.  The smallest probability interval a sequence is random for: a study for six types of randomness.  In Symbolic and Quantitative Approaches to Reasoning with Uncertainty, pages 442–454. Springer International Publishing, 2021.  URL: https://arxiv.org/abs/2107.07808.
  * [20] Thomas Augustin, Frank P.A. Coolen, Gert De Cooman, and Matthias C.M. Troffaes, editors.  Introduction to imprecise probabilities.  Wiley Series in Probability and Statistics. John Wiley and Sons, 2014\.
  * [21] Laurent Bienvenu, Glenn Shafer, and Alexander Shen.  On the history of martingales in the study of randomness.  Electronic Journal for History of Probability and Statistics, 5:1–40, 2009.
  * [22] Marian Boykan Pour-El and Jonathan Ian Richards.  Computability in Analysis and Physics.  Cambridge University Press, 2016.
  * [23] A. Shen, V. A. Uspensky, and N. Vereshchagin.  Kolmogorov Complexity and Algorithmic Randomness, volume 220 of Mathematical surveys and monographs.  American Mathematical Society, 2017.
  * [24] Michael Sipser.  Introduction to the Theory of Computation.  Thomson Course Technology, Massachusetts, 2006.
  * [25] Floris Persiau, Jasper De Bock, and Gert De Cooman.  Computable randomness is about more than probabilities.  2020\.  extended arXiv version of [18].  URL: https://arxiv.org/abs/2005.00471.
  * [26] Natan T’Joens, Jasper De Bock, and Gert de Cooman.  Game-theoretic upper expectations for discrete-time finite-state uncertain processes.  Journal of Mathematical Analysis and Applications, 504(2):125399, 2021.  URL: https://www.sciencedirect.com/science/article/pii/S0022247X21004789, doi:https://doi.org/10.1016/j.jmaa.2021.125399.
  * [27] Gert De Cooman, Jasper De Bock, and Stavros Lopatatzidis.  Imprecise stochastic processes in discrete time: global models, imprecise Markov chains, and ergodic theorems.  International Journal Of Approximate Reasoning, 76:18–46, 2016\.
  * [28] Glenn Shafer and Vladimir Vovk.  Game-Theoretic Foundations for Probability and Finance.  Wiley, Hoboken, NJ, 2019.
  * [29] Natan T’Joens, Jasper De Bock, and Gert de Cooman.  A particular upper expectation as global belief model for discrete-time finite-state uncertain processes.  International Journal Of Approximate Reasoning, 131:30–55, 2021\.