key: cord-0584721-hhnksh7o
authors: Cooman, Gert de; Bock, Jasper De
title: Randomness is inherently imprecise
date: 2021-02-26
journal: nan
DOI: nan
sha: 73d0c0fd6d73e1caadf9d558330e4d8e0f3a47d2
doc_id: 584721
cord_uid: hhnksh7o

We use the martingale-theoretic approach of game-theoretic probability to incorporate imprecision into the study of randomness. In particular, we define several notions of randomness associated with interval, rather than precise, forecasting systems, and study their properties. The richer mathematical structure that thus arises lets us, amongst other things, better understand and place existing results for the precise limit. When we focus on constant interval forecasts, we find that every sequence of binary outcomes has an associated filter of intervals it is random for. It may happen that none of these intervals is precise -- a single real number -- which justifies the title of this paper. We illustrate this by showing that randomness associated with non-stationary precise forecasting systems can be captured by a constant interval forecast, which must then be less precise: a gain in model simplicity is thus paid for by a loss in precision. But imprecise randomness can't always be explained away as a result of oversimplification: we show that there are sequences that are random for a constant interval forecast, but never random for any {comp} (more) precise forecasting system. We also show that the set of sequences that are random for a non-vacuous interval forecasting system is meagre, as it is for precise forecasting systems.

This paper documents the first steps in our attempt to incorporate imprecision into the study of algorithmic randomness. What this means is that we want to allow for, give a precise mathematical meaning to, and study the mathematical consequences of, associating randomness with interval rather than precise probabilities and expectations. We will see that this is a non-trivial problem, argue that it leads to surprising conclusions about the nature of randomness, and discover that it opens up interesting and hitherto uncharted territory for mathematical and even philosophical investigation. We believe that our work provides (the beginnings of) a satisfactory answer to questions raised by a number of researchers [19, 20, 22, 61] about frequentist and 'objective' aspects of interval, or imprecise, probabilities.

To explain what it is we're after, consider an infinite sequence ω = (z 1 , . . . , z n , . . . ), whose components z k are either zero or one, and are typically considered as successive outcomes of some experiment. When do we call such a sequence random? There are many notions of randomness, and many of them have a number of equivalent definitions [1, 4] . We will focus here essentially on Martin-Löf randomness, computable randomness, and Schnorr randomness.

The randomness of a sequence ω is typically associated with a probability measure on the sample space of all such infinite sequences, or-which is essentially equivalent due to Ionescu Tulcea's extension theorem [5, Theorem II.9 .2]-with a so-called forecasting system ϕ that associates with each finite sequence of outcomes (x 1 , . . . , x n ) the (conditional) expectation ϕ(x 1 , . . . , x n ) = E(X n+1 |x 1 , . . . , x n ) for the next, as yet unknown, outcome X n+1 . 1,2 This ϕ(x 1 , . . . , x n ) is the (precise) forecast for the value of X n+1 after observing the values x 1 , . . . , x n of the respective variables X 1 , . . . , X n . The sequence ω is then typically called 'random' when it passes some countable number of randomness tests, where the collection of such randomness tests depends of the forecasting system ϕ.

An alternative and essentially equivalent approach to defining randomness, going back to Ville [54] , sees each forecast ϕ(x 1 , . . . , x n ) as a fair price for-and therefore a commitment to bet on-the as yet unknown next outcome X n+1 after observing the first n outcomes x 1 , . . . , x n . The sequence ω is then 'random' when there is no 'allowable' strategy for getting infinitely rich by exploiting the bets made available by the forecasting system ϕ along the sequence, without borrowing. Betting strategies that are made available by the forecasting system ϕ are called supermartingales. Which supermartingales are considered 'allowable' differs in various approaches [1, 4, 18, 28, 39] , but typically involves some (semi)computability requirement-we discuss relevant aspects of computability in Section 4. Technically speaking, randomness then requires that all allowable non-negative supermartingales (that start with unit value) should remain bounded on ω.

It is this last, martingale-theoretic, approach that seems to lend itself most easily to allowing for interval rather than precise forecasts, and therefore to allowing for 'imprecision' in the definition of randomness. As we explain in Sections 2 and 3, an interval, or 'imprecise', forecasting system ϕ associates with each finite sequence of outcomes (x 1 , . . . , x n ) a (conditional) expectation interval ϕ(x 1 , . . . , x n ) for the next, as yet unknown, outcome X n+1 . The lower bound of this interval forecast represents a supremum acceptable buying price, and its upper bound an infimum acceptable selling price, for the next outcome X n+1 . This idea rests firmly on the common ground between Walley's [60] theory of coherent lower previsions and Shafer and Vovk's [45, 46] game-theoretic approach to probability that we have helped establishing in recent years, through our research on imprecise stochastic processes [13, 16] ; see also Refs. [2, 53] for more details on socalled 'imprecise probabilities'. These theoretical developments allow us here to associate supermartingales with an interval forecasting system, and therefore in Section 5 to extend a number of existing notions of randomness to allow for interval, rather than precise, forecasts: we include in particular Martin-Löf randomness and computable randomness [1, 4, 18, 39] . In Section 6, we also extend Schnorr randomness [1, 4, 18, 39] to allow for interval forecasts. We then show in Section 7 that our approach allows us to extend to interval forecasting some of Dawid's [7] well-known work on calibration, and to establish a number of interesting 'limiting frequencies' or computable stochasticity results.

We believe the discussion becomes especially interesting in Section 8, where we start restricting our attention to constant, or stationary, interval forecasts. We see this as an extension of the more classical accounts of randomness, which typically consider a forecasting system with constant forecast 1 /2-corresponding to flipping a fair coin. As we have by now come to expect from our experience with so-called imprecise probability models, when we allow for interval forecasts, a mathematical structure appears that is much more interesting than the rather simpler case of precise forecasts would lead us to suspect. In the precise case, a given sequence may not be random for any stationary forecast, but as we will see, in the case of interval forecasting there typically is a filter of intervals that a given sequence is random for. Furthermore, as we show in Section 9 by means of explicit examples, this filter may not have a smallest element, and even when it does, this smallest element may be a non-vanishing interval: this is the first cornerstone for our argument that randomness is inherently imprecise.

The examples in Section 9 all involve sequences that are random for some computable non-stationary precise forecast, but can't be random for a stationary forecast unless it becomes interval-valued, or imprecise. This might lead to the suspicion that this imprecision is perhaps only an artefact, which results from looking at non-stationary phenomena further on, we will assume that this expectation E(X) lies in the unit interval [0,1]. For reasons that will become clear later, we prefer to use the language of expectations in this paper. through an imperfect stationary lens. We show in Section 10 that this suspicion is unfounded: there are sequences that are random for a stationary interval forecast, but that aren't random for any computable (more) precise forecast, be it stationary or not. This further corroborates our claim that randomness is, indeed, inherently imprecise.

Finally, in Section 11, we argue that 'imprecise' randomness is an interesting extension of the existing notions of 'precise' randomness, because it is equally rare: just as for precise stationary forecasts, the set of all sequences that are random for a non-vacuous stationary interval forecast is meagre. This, we will argue, indicates that the essential distinction lies not between precise and imprecise forecasts (or randomness), but between non-vacuous and vacuous ones, and provides further evidence for the essentially 'imprecise' nature of the randomness notion.

We conclude with a short discussion of the significance of our findings, and of possible avenues for further research. In order to maintain focus, we have decided to move all technical proofs of auxiliary results about computability and growth functions to an appendix. We have also, as much as possible, tried to make sure that our more complicated and technical proofs in the main text are preceded by informal arguments, in order to help the reader build some intuition about why and how they work.

The dynamics of making a single forecast can be made very clear, after the fashion first introduced by Shafer and Vovk [45, 46] , by considering a simple game, with three players, namely Forecaster, Sceptic and Reality. The game involves an initially unknown outcome in the set {0, 1}, which we will denote by X. To stress that it is unknown, we call it a variable, and use upper-case notation.

Game (Single forecast of an outcome X). In a first step, the first player, Forecaster, specifies an interval bound I = [p, p] ⊆ [0, 1] for the expectation of an as yet unknown outcome X in {0, 1}-or equivalently, for the probability that X = 1. We interpret this so-called interval forecast I as a commitment, on the part of Forecaster, to adopt p as his supremum acceptable buying price and p as his infimum acceptable selling price for the gamble (with reward function) X. This is taken to mean that the second player, Sceptic, can now in a second step take Forecaster up on any (combination) of the following commitments, whose uncertain pay-offs are expressed in units of a linear utility:

(i) for all real q ≤ p and all real α ≥ 0, Forecaster is committed to accepting the gamble α[X − q], leading to a (possibly negative) uncertain reward −α[X − q] for Sceptic; 3 (ii) for all real r ≥ p and all real β ≥ 0, Forecaster is committed to accepting the gamble β [r − X], leading to a (possibly negative) uncertain reward −β [r − X] for Sceptic. Finally, in a third step, the third player, Reality, determines the value x of X in {0, 1}, and the corresponding rewards −α[x − q] or −β [r − x] are paid by Forecaster to Sceptic. Elements x of {0, 1} are called outcomes, and elements p of the real unit interval [0, 1] will serve as (precise) forecasts. We denote by I the set of non-empty closed subintervals of the real unit interval [0, 1]. Any element I of I will serve as an interval forecast. It has a smallest element min I and a greatest element max I, so I = [min I, max I]. We will use the generic notation I for such an interval forecast, and p := min I and p := max I for its lower and upper bounds, respectively. An interval forecast I = [p, p] is of course precise when p = p =: p, and we will then make no distinction between the singleton interval forecast I = {p} ∈ I and the corresponding precise forecast p ∈ [0, 1].

After Forecaster announces an interval forecast I, what Sceptic can do is essentially to try and increase her capital by taking a gamble on the unknown outcome X. Any such gamble can be considered as a map f : {0, 1} → R, and can therefore be represented as a point or vector ( f (1), f (0)) in the two-dimensional vector space R 2 ; see also Figure 1 below. f (X) is then the (possibly negative) increase in Sceptic's capital after the game has been played, as a function of the outcome variable X. Of course, not every gamble f (X) on the unknown outcome X will be available to Sceptic: which gambles she can take is determined by Forecaster's interval forecast I. As we indicated above, in their most general form, they're given by f (X) = −α[X − q] − β [r − X], where α and β are non-negative real numbers, q ≤ p and r ≥ p. We see that the gambles that are available to Sceptic constitute a closed convex cone A I in R 2 , see also Figure 1 :

where we use R ≥0 to denote the set of non-negative real numbers.

Let us associate with any precise forecast p ∈ [0, 1] the expectation (functional) E p , defined by (1)

If we also consider the so-called lower expectation (functional) E I associated with an interval forecast I ∈ I , defined by

for any gamble f : {0, 1} → R, (2) and similarly, the upper expectation (functional) E I , defined by

for any gamble f :

then it is not difficult to see 4 that the closed convex cone A I of all gambles f (X) that are available to Sceptic after Forecaster announces his interval forecast I is completely determined by the condition E I ( f ) ≤ 0, as depicted by the blue regions in Figure 1 . In fact, the condition E I ( f ) ≤ 0 is equivalent to (∀p ∈ I)E p ( f ) ≤ 0, so the available gambles belong to the intersection of all half-planes determined by E p ( f ) ≤ 0 for all p ∈ I.

The functionals E I and E I are easily shown to have the following so-called coherence properties, typical for the more general lower and upper expectation operators defined on arbitrary gamble spaces [53, 60] : Proposition 1. Consider any forecast interval I ∈ I . Then for all gambles f , g on {0, 1}, all µ ∈ R and all non-negative λ ∈ R:

[monotonicity]

Gambles f available to Sceptic when (a) Forecaster announces I ∈ I with p < p; and when (b) Forecaster announces I ∈ I with p = p =: p.

We now consider a sequence of repeated versions of the forecasting game in the previous section. At each successive stage k ∈ N, Forecaster presents an interval forecast I k = [p k , p k ] for the unknown outcome variable X k . This effectively allows Sceptic to choose any gamble f k (X k ) such that E I k ( f k ) ≤ 0. Finally, Reality then chooses a value x k for X k , resulting in a gain in capital f k (x k ) for Sceptic. This gain f k (x k ) can, of course, be negative, resulting in an actual decrease in Sceptic's capital.

Here and in what follows, N is the set of all natural numbers, without zero. We will also use the notation N 0 := N ∪ {0} and the notation Z for the set of all integer numbers.

3.1. The event tree and its forecasting systems. We call (x 1 , x 2 , . . . , x n , . . . ) an outcome sequence, and we collect all possible outcome sequences in the set Ω := {0, 1} N . We collect the finite outcome sequences x 1:n := (x 1 , . . . , x n ) in the set S := {0, 1} * = n∈N 0 {0, 1} n . The finite outcome sequences s in S and infinite outcome sequences ω in Ω constitute the nodes-also called situations-and paths in an event tree with unbounded horizon, part of which is depicted below. The empty sequence x 1:0 =: is also called the initial situation. From now on, we will systematically use the 'situations' and 'paths' terminology. Keep in mind that any path ω ∈ Ω is an infinite outcome sequence, and can therefore also be identified with-the binary expansion of-a real number in the unit interval In the repeated game described above, Forecaster will only provide interval forecasts I k after observing the actual sequence (x 1 , . . . , x k−1 ) that Reality has chosen, and the corresponding sequence of gambles ( f 1 , . . . , f k−1 ) that Sceptic has chosen. This is the essence of so-called prequential forecasting [7, 8, 11] . But for the purposes of the present discussion, it will be advantageous to consider an alternative, and in some aspects more involved, setting where a forecast I s is specified in each of the possible situations s in the event tree S; see the figure below: 

We can use this idea to extend the notion of a forecasting system in Refs. [9, 59] from precise to interval forecasts.

Definition 1 (Forecasting system). A forecasting system is a map ϕ : S → I , that associates an interval forecast ϕ(s) ∈ I with every situation s in the event tree S. With any forecasting system ϕ we associate two real processes ϕ and ϕ, 5 defined by ϕ(s) := min ϕ(s) and ϕ(s) := max ϕ(s) for all s ∈ S. A forecasting system ϕ is called precise if ϕ = ϕ. Specifying a forecasting system ϕ requires that Forecaster should imagine in advance all the moves that Reality (and Sceptic) could make, and that he should devise in advance what forecast ϕ(s) to give in each imaginable situation s ∈ S. We will use the notation ϕ ⊆ ϕ * to mean that the forecasting system ϕ * is at least as conservative as ϕ, meaning that ϕ(s) ⊆ ϕ * (s) for all s ∈ S.

3.2. Imprecise probability trees and supermartingales. Since in each situation s the interval forecast I s = ϕ(s) corresponds to a so-called local upper expectation E I s , we can use the argumentation in our earlier papers [13, 15, 16] on imprecise stochastic processes to help ϕ turn the event tree into an imprecise probability tree, with an associated global upper expectation on paths, and a corresponding notion of 'almost surely '. In what follows, we recall in some detail how to do this. However, we will limit ourselves to discussing only those aspects that are essential for a proper understanding of our treatment of randomness further on; for a much more extensive discussion, we refer to our earlier papers [13, 15, 16] , based on the seminal work by Shafer and Vovk [45] [46] [47] 56] .

We will denote by Φ the set I S of all forecasting systems, or equivalently, all imprecise probability trees.

For any path ω ∈ Ω, the initial sequence that consists of its first n elements is a situation in {0, 1} n that is denoted by ω 1:n . Its n-th element belongs to {0, 1} and is denoted by ω n . As a convention, we let its 0-th element be the initial situation ω 1:0 = ω 0 = .

For any situation s ∈ S and any path ω ∈ Ω, we say that ω goes through s if there is some n ∈ N 0 such that ω 1:n = s. We denote by Γ(s) the so-called cylinder set of all paths ω ∈ Ω that go through s.

We write that s ⊑ t, and say that the situation s precedes the situation t, when every path that goes through t also goes through s-so s is a precursor of t. An equivalent condition is of course that Γ(t) ⊆ Γ(s). We say that the situation s strictly precedes the situation t, and write s ⊏ t, when s ⊑ t and s = t, or equivalently, when Γ(t) ⊂ Γ(s).

For any situation s = (x 1 , . . . , x n ) ∈ S, we call n = |s| its depth in the tree. Of course, |s| ≥ | | = 0. We will use a similar notational convention for situations as for paths: we 5 For a more concrete definition of a 'process', we refer to the discussion in Section 3.2. let s k := x k and s 1:k := (x 1 , . . . , x k ) for all k ∈ {1, . . . , n}, and s 1:0 = s 0 := . Also, for any x ∈ {0, 1}, we denote by sx the situation (x 1 , . . . , x n , x).

A process F is a map defined on S. A real process is a real-valued process: it associates a real number F(s) ∈ R with every situation s ∈ S. With any real process F, we can always associate a process ∆F, called the process difference. For every situation s ∈ S, ∆F(s) is the gamble on {0, 1} defined by

The initial value of a process F is its value F( ) in the initial situation . Any real process is completely determined by its initial value and its process difference, because

We call a real process non-negative if it is non-negative in all situations. Similarly, a positive real process is (strictly) positive in all situations. We call test process any nonnegative real process F with unit initial value F( ) = 1.

We now look at at number of special real processes. In the imprecise probability tree associated with a given forecasting system ϕ, a supermartingale M for ϕ is a real process such that

In other words, all supermartingale differences have non-positive upper expectation: supermartingales are real processes that Forecaster expects to decrease. A real process M is a submartingale for ϕ if −M is a supermartingale, which means that E ϕ(s) (∆M(s)) ≥ 0 for all s ∈ S: all submartingale differences have non-negative lower expectation, so submartingales are real processes that Forecaster expects to increase. We denote the set of all supermartingales for a given forecasting system ϕ by M ϕ -whether a real process is a supermartingale depends of course on the forecasts in the situations. Similarly, the set M ϕ := −M ϕ is the set of all submartingales for ϕ, and M ϕ := M ϕ ∩ M ϕ is the set of all martingales for ϕ-real processes that are at the same time super-and submartingales, and therefore real processes that Forecaster expects to remain constant. It ought to be clear from the discussion in Section 2 that the supermartingales for ϕ are effectively all the possible capital processes M for a Sceptic who starts with an initial capital M( ), and in each possible subsequent situation s selects a gamble f s = ∆M(s) that is available there because of Forecaster's specification of the interval forecast I s = ϕ(s): E I s ( f s ) ≤ 0. If Reality chooses the successive outcomes x 1 , . . . , x n , then Sceptic will end up in the corresponding situation s = (x 1 , . . . , x n ) with a capital

We call test supermartingale for ϕ any test process that is also a supermartingale for ϕ, or in other words, any non-negative supermartingale M for ϕ with initial value M( ) = 1. It corresponds to Sceptic starting with unit capital and never borrowing. We collect all test supermartingales for ϕ in the set T ϕ .

We will also need to pay attention to a particular way of constructing test supermartingales. We define a gamble process as a map D from S to gambles on {0, 1}. If these gambles D(s) are all non-negative, then we call this D a multiplier process. Given such a multiplier process D, we can construct the test process D ⊚ by the recursion equation . , x k )(x k+1 ) for all n ∈ N 0 and (x 1 , . . . , x n ) ∈ S. We call D ⊚ the test process generated by the multiplier process D.

Any multiplier process D that satisfies the additional condition that E ϕ(s) (D(s)) ≤ 1 for all s ∈ S, is called a supermartingale multiplier for the forecasting system ϕ. It is easy to see that the test process D ⊚ generated by D is then a test supermartingale for ϕ: it suffices to check that

for all s ∈ S, (5) due to the coherence properties C2 and C4 of upper expectation operators.

Upper expectations and null events. In the context of (imprecise) probability trees, we call variable any map defined on the so-called sample space-the set Ω of all paths. When this variable is real-valued and bounded, we call it a gamble on Ω, or also a global gamble. An event A in this context is a subset of Ω, and its indicator I A is the gamble on Ω that assumes the value 1 on A and 0 elsewhere.

The sub-and supermartingales for a forecasting system ϕ can be used to associate socalled global lower and upper expectation operators-defined on global gambles-with the forecasting system ϕ:

for all gambles g on Ω. In these expressions, we have used the notations It is clear that lower and upper expectations are related to each other through the following conjugacy relationship:

These lower and upper expectations satisfy coherence properties that are completely similar to-direct counterparts of-those in Proposition 1, and we list these properties again below. Their proofs are by now fairly well-known [45, 46, 50] , but for the sake of completeness, we repeat them in the Appendix.

Proposition 2. Consider any forecasting system ϕ ∈ Φ. Then for all gambles f , g on Ω, all µ ∈ R and all non-negative λ ∈ R:

For extensive discussion about why the expressions (6) and (7) are interesting and useful, we refer to Refs. [13, 16, 45, 46, [48] [49] [50] 52] . For our present purposes, it may suffice to mention that for precise forecasts, they lead to models that coincide with the ones found in measure-theoretic probability theory; see Refs. [45, Chapter 8] and [46, Chapter 9] , as well as Ref. [52] . In particular, when all I s equal { 1 /2}, these models coincide on all measurable global gambles with the usual uniform (Lebesgue) expectations. More generally, for an imprecise forecast ϕ ∈ Φ, the lower and upper expectation E ϕ and E ϕ provide tight lower and upper bounds on the measure-theoretic expectation of every precise forecasting system ϕ ′ that is compatible with ϕ, in the sense that ϕ ′ ⊆ ϕ [48] .

For an event A ⊆ Ω, the corresponding lower and upper probabilities are defined by P ϕ (A) := E ϕ (I A ) and P ϕ (A) := E ϕ (I A ). The following conjugacy relationship for events follows at once from the property E4 for global lower and upper expectations:

We call an event A ⊆ Ω null for a forecasting system ϕ if P ϕ (A) = 0, or equivalently, if P ϕ (A c ) = 1. As usual, any property that holds, except perhaps on a null event, is said to hold almost surely for the forecasting system ϕ. We will then also say that almost all paths have that property in the imprecise probability tree corresponding to ϕ.

We now give a brief survey of a number of basic notions and results from computability theory, and a few derived results, that are relevant to the developments in this paper. For a much more extensive discussion, we refer, for instance, to Refs. [29, 35] .

A recursive map ψ : N 0 → N 0 is a map that can be computed by a Turing machine. By the Church-Turing (hypo)thesis, this is equivalent to the existence of an algorithm that, upon input of a number n ∈ N 0 , outputs the number ψ(n) ∈ N 0 . All notions of computability that we will need are based on this notion, and we will use the equivalent condition consistently. It is clear that in this definition, we can replace any of the N 0 with any other countable set that is linked with N 0 through a recursive bijection whose inverse is also recursive.

We start with the definition of a computable real number. We call a sequence of rational numbers r n recursive if there are three recursive maps a, b, ς from N 0 to N 0 such that b(n) > 0 and r n = (−1) ς (n) a(n) b(n) for all n ∈ N 0 , and we say that it converges effectively to a real number x if there is some recursive map e : N 0 → N 0 such that n ≥ e(N) ⇒ |r n − x| ≤ 2 −N for all n, N ∈ N 0 .

A real number is then called computable if there is some recursive sequence of rational numbers that converges effectively to it. Of course, every rational number is a computable real.

We also need a notion of computable real processes, or in other words, computable realvalued maps F : S → R defined on the set S of all situations. Because there is an obvious recursive bijection between N 0 and S, whose inverse is also recursive, we can identify real processes and real sequences, and simply import, mutatis mutandis, the definitions for computable real sequences common in the literature [35, Chapter 0, Definition 5]. We call a net of rational numbers r s,n recursive if there are three recursive maps a, b, ς from S × N 0 to N 0 such that b(s, n) > 0 and r s,n = (−1) ς (s,n) a(s, n) b(s, n) for all s ∈ S and n ∈ N 0 .

We call a real process F : S → R computable if there is a recursive net of rational numbers r s,n and a recursive map e : S × N 0 → N 0 such that n ≥ e(s, N) ⇒ |r s,n − F(s)| ≤ 2 −N for all s ∈ S and n, N ∈ N 0 .

Again, there is no problem with the notions 'recursive net of rational numbers' or 'recursive map' in this definition, because we can identify S × N 0 with N 0 through a recursive bijection whose inverse is also recursive. Obviously, it follows from this definition that in particular F(t) is a computable real number for any t ∈ S: fix s = t and consider the sequence r t,n , which converges effectively to the real number F(t) as n → ∞. Also, a constant real process is computable if and only if its constant real value is.

We also need to mention semicomputable real processes; see for instance [29, 39] for more details. A real process F is lower semicomputable if it can be approximated from below by a recursive net of rational numbers, meaning that there is some recursive net of rational numbers r s,n such that (i) r s,n+1 ≥ r s,n for all s ∈ S and n ∈ N 0 ; (ii) F(s) = lim n→∞ r s,n for all s ∈ S. We say that F is upper semicomputable if −F is lower semicomputable. A real number x is lower semicomputable if the real process with constant value x is, or equivalently, if there is some recursive sequence of rational numbers r n such that r n ր x.

In the (semi)computability definitions above, as well as in the results that follow in this section, we can replace the countable set S with any countable set that can be identified with S through a recursive bijection whose inverse is also recursive. Further on in this paper, we will for instance have occasion to replace S with N, N 0 and S × {0, 1}.

Basic results from the literature. We recall the following standard results; see for instance Ref. [35, Chapter 0]. The following propositions apply mutatis mutandis also to computable real numbers and computable real sequences in lieu of computable real processes. Even though they're fairly standard, we give their proofs in the Appendix for the sake of completeness, and to give the reader an idea of why they work.

The condition for computability of a real process can be simplified as follows.

Proposition 3 ([35, Chapter 0, Definition 5a]). A real process F is computable if and only if there is some recursive net of rational numbers r s,n such that |r s,n − F(s)| ≤ 2 −n for all s ∈ S and n ∈ N 0 .

If F and G are computable real processes, then so are −F, F + G, FG, F/G (provided that G(s) = 0 for all s ∈ S), max{F, G}, min{F, G}, exp(F), ln F (provided that F(s) > 0 for all s ∈ S), and F 

New material for the present context. We conclude this section with a number of new definitions and results that are specifically tailored to the discussion further on.

The following definitions should be obvious. A gamble f on {0, 1} is called computable if both its values f (0) and f (1) are computable real numbers.

An interval forecast I = [p, p] ∈ I is called computable if and only if both its lower bound p and upper bound p are computable real numbers.

A forecasting system ϕ is called computable if the associated real processes ϕ and ϕ are computable.

Finally, a process difference ∆F is called (lower/upper semi)computable if the real processes ∆F(·)(0) and ∆F(·)(1) are (lower/upper semi)computable; and similarly for a multiplier process D. 6 We also list a number of useful propositions that are less immediate, and perhaps require explicit proofs. We have gathered these proofs in the Appendix.

Proposition 5. For any I = [p, p] ∈ I , the so-called stationary forecasting system γ I , defined by γ I (s) := I for all s ∈ S, is computable if and only if the interval I is computable, and therefore if and only if p and p are. 6 These definitions can also be seen as special cases of a more general (lower/upper semi)computability condition, where the set S is replaced by the set S × {0,1}. Proposition 6. Consider any real process F, and its process difference ∆F. Then the following statements hold:

(i) if F( ) and ∆F are lower semicomputable then so is F; (ii) if F( ) and ∆F are upper semicomputable then so is F; (iii) F is computable if and only if F( ) and ∆F are.

Proposition 7. Consider any multiplier process D, then the following implications hold:

Proposition 8. Consider a multiplier process D, and the associated real process D ⊚ . If D ⊚ is positive and computable, then so is D. As a consequence, any positive computable real process F has a positive computable multiplier process D, such that F = F( )D ⊚ .

With all the scaffolding now in place, we're finally ready to associate various notions of randomness with a forecasting system ϕ-or in other words, with an imprecise probability tree. We want to be able to introduce and study several versions of randomness, each connected with a particular class of test supermartingales-capital processes for Sceptic when she starts with unit capital and never borrows.

In what follows, we will denote by A any countable set of test processes that includes the countable set of all computable positive test processes, which we denote by A + C . Examples of such sets A are: A + C all computable positive test processes A C all computable test processes A ML all lower semicomputable test processes A ⊚ ML all test processes generated by lower semicomputable multiplier processes. We will call such test processes in A allowable. Observe that,

where the second chain of inclusions follows from Propositions 4, 7 and 8. The test supermartingales for ϕ that belong to this set A will also be called allowable test supermartingales, and collected in the set T 

Randomness. In the rest of this section (and paper), and unless explicitly stated to the contrary, A is an arbitrary but fixed set of allowable test processes. We remind the reader once again that all such sets A and the corresponding sets T ϕ A are countable. Definition 2 (Randomness). Consider any forecasting system ϕ : S → I and path ω ∈ Ω. We call ω A-random for ϕ if all (allowable) test supermartingales T in T ϕ A remain bounded above on ω, meaning that there is some B T ∈ R such that T (ω 1:n ) ≤ B T for all n ∈ N, or equivalently, that sup n∈N T (ω 1:n ) < ∞. We then also say that the forecasting system ϕ makes ω A-random.

In other words, A-randomness of a path means that there is no allowable strategy that starts with unit capital and avoids borrowing, and allows Sceptic to increase her capital without bounds by exploiting the bets on the outcomes along the path that are made available to her by Forecaster's specification of the forecasting system ϕ.

When the forecasting system ϕ is precise and computable, and A is the set A ML of all lower semicomputable test processes, our definition reduces to that of Martin-Löf randomness on the Schnorr-Levin (martingale-theoretic) account [1, 4, 39, 40, 59] , because T ϕ ML is the set of all lower semicomputable test supermartingales for ϕ. We will therefore continue to call A ML -randomness Martin-Löf randomness, also when the forecasting system ϕ is no longer precise or computable.

Similarly, when the forecasting system ϕ is precise and computable, and A is the set A C of all computable test processes, our definition reduces to that of computable randomness [1, 4] , because T ϕ C is the set of all computable test supermartingales for ϕ. We will therefore continue to call A C -randomness computable randomness, also when the forecasting system ϕ is no longer precise or computable.

We denote by

the set of all forecasting systems for which the path ω is A-random. We will also use the special notations Φ + C (ω), Φ C (ω), Φ ⊚ ML (ω) and Φ ML (ω) in the cases that A is equal to A + C , A C , A ⊚ ML and A ML , respectively. As a special, not unimportant but fairly trivial case, the (computable) vacuous forecasting system ϕ v assigns the vacuous forecast ϕ v (s) := [0, 1] to all situations s ∈ S. Recall that we have introduced the notation ϕ ⊆ ϕ * to mean that ϕ * is at least as conservative as ϕ, so ϕ(s) ⊆ ϕ * (s) for all s ∈ S. Then clearly ϕ ⊆ ϕ v for all ϕ ∈ Φ, so ϕ v is the most conservative forecasting system, with local models E ϕ v (s) = max for all s ∈ S. It corresponds to Forecaster making no actual commitments, and the closed convex cone A [0,1] of gambles f ≤ 0 that are then available to Sceptic at each successive stage is depicted in Figure 2 . The following proposition uses this vacuous forecasting system to conclude that no Φ A (ω) is empty.

Proposition 9. All paths are A-random for the vacuous forecasting system, so ϕ v ∈ Φ A (ω) for all ω ∈ Ω.

Proof. In the imprecise probability tree associated with the vacuous forecasting system ϕ v , a real process M is a supermartingale if and only if it is non-increasing: ∆M ≤ 0. All test supermartingales for ϕ v are therefore bounded above by 1 on any path ω ∈ Ω.

The more conservative, or imprecise, the forecasting system, the less stringent is the corresponding randomness notion.

Let ω be A-random for a forecasting system ϕ. Then ω is also A-random for any forecasting system ϕ * such that ϕ ⊆ ϕ * .

A , this follows trivially from Definition 2. The larger the set A of allowable test processes, the more stringent is the corresponding randomness notion, and the 'fewer' A-random paths there are. More precisely:

If ω is A-random for a forecasting system ϕ, then ω is also A ′ -random for ϕ, and therefore

A , this follows trivially from Definition 2. As a fairly direct consequence of Equation (9), we can now infer from Proposition 11 that

where only the equality needs more explanation.

Proof of the equality in Equation (10).

To prove the converse inclusion, assume that the forecasting system ϕ makes ω A + C -random. Consider any computable test supermartingale T for ϕ, so T ∈ T ϕ C , and assume ex absurdo that T is unbounded on ω, then so is the computable positive test supermartingale

ML -randomness is weaker than Martin-Löf randomness, but has a similar flavour, we will also call it weak Martin-Löf randomness.

Real-valued versus extended real-valued supermartingales. Before moving on, we want to comment on a particular aspect of our randomness definition that differs slightly from other approaches, such as for instance described in Refs. [39, 59] , which allow the test supermartingales in their randomness definition to be extended real-valued; we restrict ourselves to real-valued test supermartingales in the present approach. Let us explain what are the differences between these two approaches, and indicate briefly why we prefer ours.

A process M assuming values in R ∪ {∞} that satisfies the extended supermartingale inequality

is called an extended supermartingale for ϕ. The upper expectation E ϕ(s) in Equation (11) is defined on maps f : {0, 1} → R ∪ {∞} by generalising Equation (3): for any I ∈ I ,

taking into account the conventions that 0

. This argumentation, in combination with C1, tells us that

The extended supermartingale inequality (11) imposes no requirements on M(s·) whenever M(s) = ∞. At the same time, it tells us that an extended supermartingale with M(s) ∈ R can't jump to ∞ in s1 unless ϕ(s) = 0, 7 and similarly, it can't jump to ∞ in s0 unless ϕ(s) = 1: infinite jumps upwards in going from one situation to the next are only allowed when the transition between these situations has upper probability zero, and can therefore only occur in situations s whose forecast ϕ(s) is degenerate, meaning that ϕ(s) = 0 or ϕ(s) = 1.

If, contrary to our approach, randomness of a path ω means that all allowable extended test supermartingales must remain bounded, this means that, in addition to the requirements on real supermartingales present in our condition, such extended test supermartingales must not be allowed to jump to ∞ anywhere on the path ω. Now, an extended test supermartingale T starts with the initial value T ( ) = 1 in , so if it is to assume the value ∞ somewhere, there must be at least one situation s ∈ S and outcome x ∈ {0, 1} such that T makes an infinite jump in going from T (s) ∈ R to T (sx) = ∞. As explained above, the extended supermartingale condition (11) tells us that this can only happen when

meaning that the (upper) probability of the transition from s to sx is zero. In other words, there can only be a difference between the two types of randomness definitions when there are degenerate transition probabilities in the (imprecise probability) tree. 8 And in such cases, when there is for instance a transition in some path ω that has upper probability zero, ω can't be random according to the definition with extended test supermartingales. So, in principle, whether a path is random on the 'extended' definition can in that case depend on a single outcome, which is something we find unfortunate. Whether such a path ω will be random according to our definition, will depend on the forecasting system and the transition behaviour on ω.

Next, we concentrate on extending the notion of Schnorr randomness to our present context. We begin with a definition borrowed from Schnorr's seminal work [39, 40] .

We say that a real-valued map µ : N 0 → R is computably unbounded if there is some growth function ρ such that lim sup n→∞ [µ(n) − ρ(n)] > 0, or equivalently,

In what follows, it will often simplify our proofs to work with a more general notion of growth function.

It turns out that working with this more general definition does not really change what is important, namely computable unboundedness. Indeed, we can use it to give a number of equivalent characterisations of this notion that will prove useful further on. The rather technical proof of these alternative characterisations is deferred to the Appendix.

Proposition 12. Consider a real-valued map µ : N 0 → R, then the following statements are equivalent:

there is a real growth function τ such that lim sup n→∞ µ(n) /τ(n) > 0. 9 All of these statements characterise the computable unboundedness of µ.

We will also need the following simple results. Their proofs are fairly obvious, but we have included them in the Appendix for the sake of completeness.

Proposition 13. If a real-valued map µ : N 0 → R is computably unbounded, it is also unbounded above.

If the point-wise product µ 1 µ 2 of real maps µ 1 : N 0 → R and µ 2 : N 0 → R is computably unbounded, then at least one of the factors µ 1 or µ 2 is computably unbounded too.

We can now extend Schnorr's original definition of randomness [39, 40] in a probability tree with a constant precise forecast I = { 1 /2} to imprecise probability trees associated with an arbitrary-and not necessarily precise nor computable-forecasting system.

Definition 5 (Schnorr randomness). Consider any forecasting system ϕ : S → I . We call a path ω ∈ Ω Schnorr random for ϕ if no computable test supermartingale T ∈ T ϕ C for ϕ is computably unbounded on ω, or in other words, if lim sup n→∞ [T (ω 1:n ) − ρ(n)] ≤ 0 for all computable test supermartingales T ∈ T ϕ C for ϕ and all growth functions ρ. We then also say that the forecasting system ϕ makes ω Schnorr random.

In this definition, we can of course also use the alternative characterisations of computable unboundedness listed in Proposition 12. Furthermore, without loss of generality, we can focus on computable positive test supermartingales.

Proposition 15. Consider any forecasting system ϕ : S → I . Then a path ω ∈ Ω is Schnorr random for ϕ if and only if no computable positive test supermartingale T ∈ T ϕ C for ϕ is computably unbounded on ω.

Proof. It clearly suffices to prove the 'if' part. To this end, we consider any path ω ∈ Ω that isn't Schnorr random for ϕ and prove that there is some computable positive test supermartingale for ϕ that is computably unbounded on ω. Since ω ∈ Ω isn't Schnorr random for ϕ, there is a computable test supermartingale T for ϕ that is computably unbounded on ω, meaning that there is some growth function ρ such that lim sup n→∞ [T (ω 1:n )− ρ(n)] > 0. For the real growth function τ := (1 + ρ)/2 and the computable positive test supermartingale T ′ := (1 + T )/2 ∈ T ϕ C , it then follows that lim sup n→∞ [T ′ (ω 1:n ) − τ(n)] > 0, so T ′ is computably unbounded on ω by Proposition 12(ii).

We denote by Φ S (ω) := {ϕ ∈ Φ : ω is Schnorr random for ϕ} the set of all forecasting systems that make the path ω Schnorr random.

The following results are now fairly immediate. The first one shows that Schnorr randomness is the weakest form of randomness that we're considering here.

Proposition 16. Consider any set A of allowable test processes, any forecasting system ϕ : S → I and any path ω ∈ Ω. Then if ω is A-random for ϕ, it is also Schnorr random for ϕ, and therefore Φ A (ω) ⊆ Φ S (ω).

Proof. It follows from Proposition 11 and A + C ⊆ A that it suffices to give a proof for the case that A = A + C . Assume that ω isn't Schnorr random for ϕ. Then it follows from Proposition 15 that there is some positive computable test supermartingale T ∈ T ϕ C for ϕ that is computably unbounded on ω. But then Proposition 13 implies that T is also unbounded on ω, and therefore ω isn't A + C -random for ϕ. Together with Equation (10), this result tells us that

Proposition 17. All paths are Schnorr random for the vacuous forecasting system, so

Proof. This is an immediate consequence of Propositions 9 and 16.

Proposition 18. Let ω be Schnorr random for a forecasting system ϕ. Then ω is also Schnorr random for any forecasting system ϕ * such that ϕ ⊆ ϕ * .

Proof. Since ϕ ⊆ ϕ * implies that T ϕ * C ⊆ T ϕ C , this follows trivially from Definition 5.

We now turn to a number of important consistency results for the various randomness notions we have introduced. In the rest of this section, unless explicitly mentioned to the contrary, A is an arbitrary but fixed set of allowable test processes. 7.1. All paths are almost surely random. We first show that any Forecaster who specifies a forecasting system is consistent in the sense that he believes himself to be wellcalibrated: in the imprecise probability tree generated by his own forecasts, almost all paths will be random, so he is 'almost sure' that Sceptic will not be able to become infinitely rich by exploiting his-Forecaster's-forecasts.

Theorem 19 (The well-calibrated imprecise Bayesian; strong version). Consider any forecasting system ϕ : S → I . Then almost all paths are A-random for ϕ in the imprecise probability tree that corresponds to ϕ. As a consequence, almost all paths are Schnorr random for ϕ in the imprecise probability tree corresponding to ϕ.

Proof. We first prove the result for A-randomness. Consider the event A := {ω ∈ Ω : ω is A-random for ϕ}, then we have to prove that P ϕ (A) = 1, or equivalently, that P ϕ (A c ) = 0: the non-random paths belong to a null set. It follows from the assumptions that, for every ω in A c , there is some allowable test supermartingale T ω ∈ T ϕ A that becomes unbounded on ω. Let (T k ) k∈N be any enumeration of the countable set T ϕ A = A ∩ T ϕ of allowable test supermartingales, and consider any collection of positive real weights (w k ) k∈N such that ∑ k∈N w k = 1. We use these to construct the non-negative extended real process F := ∑ k∈N w k T k , with F( ) = 1. We now construct, for any real α > 1, a test supermartingale T (α ) for ϕ. Let

It is a matter of direct verification to show that T (α ) is indeed a test supermartingale for ϕ. It is clear that, for any ω ∈ A c , some T k becomes unbounded on ω, and therefore F will eventually exceed α on ω. Hence, lim n→∞ T (α) (ω 1:n ) = α for all ω ∈ A c . This implies that lim inf T (α ) (ω) ≥ αI A c (ω) for all ω ∈ Ω, and therefore

Here, the first inequality follows from the property E1 of the upper expectation E ϕ , the second equality from the property E2, the second inequality from Equation (7), and the last equality from the fact that T (α ) is a test supermartingale. Since this statement holds for all real α > 0, this implies that, indeed, P ϕ (A c ) = 0.

To prove the result for Schnorr randomness, it now suffices to recall Proposition 16 and the monotonicity of the upper expectation E ϕ [property E5].

This result is quite powerful, and it guarantees in particular that there always are random paths, for any forecasting system. Corollary 20. For any forecasting system ϕ, there is at least one path that is A-random, and therefore also Schnorr random, for ϕ.

Proof. We give the proof for A-randomness; the result for Schnorr randomness will then follow from Proposition 16. In the proof of Theorem 19, we considered the set A of all paths that are A-random for ϕ, and proved that its complement A c is null for ϕ, or in other words, that P ϕ (A c ) = 0. If, ex absurdo, A were empty, this would imply that A c = Ω and therefore that P ϕ (Ω) = 0. But it follows from property E1 that, actually, P ϕ (Ω) = 1, leading to a contradiction.

In fact, since Theorem 19 tells us that the set of all random paths for a forecasting system has lower probability one, there are many such random paths in a 'measure-theoretic' sense. But we will see in Section 11 that, in a specific topological sense, random paths are few, as they typically constitute only a meagre set. This is a known result for precise randomness, that was, as far as we can judge, first formulated as such in the context of a much more encompassing discussion on the nature of randomness by Muchnik, Semenov and Uspensky [31] . It also appeared in a related form in the wake of discussions [3, 10, 32, 37, 38] of Philip Dawid's papers on calibration [7, 9] , and was foreshadowed by some of Terrence Fine's results [21] .

7.2. The well-calibrated imprecise Bayesian. We now turn to a weaker consistency result that deals with limits (inferior and superior) of relative frequencies. We will see that it generalises to interval forecasts the arguments and conclusions in an earlier paper on calibration by Philip Dawid [7] .

We start with any real process F : S → R. We consider any so-called selection process S : S → {0, 1}, and use it to define the real process F S : S → R as follows:

In words, F S (s) is the arithmetic average of the process differences ∆F(s 1:k ) along the path segment s, where only the actually selected precursor situations s 1:k with S(s 1:k ) = 1 are taken into account. As a particular example that will be useful further on, fix any gamble h on {0, 1}, and consider the real process M ϕ h defined by

On the one hand, we find for the corresponding process difference ∆M

, and therefore we find on the other hand for its lower expectations in the imprecise probability tree that

using the coherence property C4 for the first equality. We conclude that M ϕ h is a submartingale for ϕ. Its process differences ∆M ϕ h (s) are furthermore uniformly bounded, for instance by the variation (semi)norm h v of h:

where the inequality follows from Equation (16) and the coherence property C1. Observe by the way that in this particular case, for all s ∈ S:

We can now apply our law of large numbers for uniformly bounded submartingale differences [16, Theorem 7 ] to get to the following result, which generalises Philip Dawid's well-known consistency result for Bayesian Forecasters [7, General Calibration Theorem], to deal with interval forecasts. In its formulation, we use the following formalised version of notation that we introduced earlier: for any n ∈ N, we consider the variables-maps defined on the sample space Ω-X 1:n and X n , defined by X 1:n : Ω → {0, 1} n : ω → X 1:n (ω) := ω 1:n and X n :

where we also let, by convention, X 1:0 (ω) = X 0 (ω) := for all ω ∈ Ω.

Theorem 21 (The well-calibrated imprecise Bayesian). Let ϕ : S → I be any forecasting system, let S : S → {0, 1} be any selection process, and let h be any gamble on {0, 1}. If lim n→∞ ∑ n−1 k=0 S(X 1:k ) = ∞ then also lim inf n→∞ M ϕ h S (X 1:n ) ≥ 0 almost surely for the forecasting system ϕ.

Proof. For any submartingale M for ϕ whose process differences are uniformly bounded, Theorem 7 in Ref. [16] states that, strictly almost surely, lim n→∞ ∑ n−1 k=0 S(X 1:k ) = ∞ implies that lim inf n→∞ M S (X 1:n ) ≥ 0, where 'strictly almost surely' means that there is some test supermartingale that converges to ∞ on all paths where the statement isn't true. Furthermore, Proposition 4 in Ref. [16] states that any event that holds strictly almost surely, also holds almost surely. The result therefore follows because, as we have seen in the main text above, M ϕ h is a submartingale for ϕ whose process differences are uniformly bounded.

One important step in the proof of this result-or actually, in the proof of Theorem 7 in Ref. [16] on which our proof above relies-is, stripped to its bare essentials, based on a surprisingly elegant and effective idea that goes back to Shafer and Vovk [45, Lemma 3.3] . We repeat it here, suitably adapted to the present context, in the lemma below, because it will next help us prove a related and equally important result-Theorem 23 further onthat will turn out to be crucial for establishing a number of claims in this paper: that randomness is inherently imprecise in Section 9, and that random paths are few, topologically speaking, in Section 11. Lemma 22. Let ϕ : S → I be any forecasting system, and consider any real B > 0 and any 0 < ξ < 1 B . Let M be any submartingale for ϕ such that |∆M| ≤ B. Let S : S → {0, 1} be any selection process. Then the real process F M , defined by

is a positive test supermartingale for ϕ. Moreover, if we consider 0 < ε < B and ξ :

Finally, if ξ and ∆M are computable and S is recursive, then F M is computable as well.

Proof. Let

We first show that D M is a positive supermartingale multiplier for ϕ. To this end, consider any s ∈ S. Then on the one hand, it follows from 0 < ξ B < 1 and

On the other hand, since ξ > 0 and S(s) ∈ {0, 1}, we infer from the coherence [C4 and C2] and conjugacy properties of lower and upper expectations that

where the inequality follows from E ϕ(s) (∆M(s)) ≥ 0, because we assumed that M is a submartingale for ϕ. So, indeed, D M is a positive supermartingale multiplier for ϕ. Comparing Equations (20) and (21), we see that F M = D ⊚ M , or in other words that F M is generated by the multiplier process D M . Hence, F M ( ) = 1 and, since D M is a positive supermartingale multiplier,

For the second statement, consider any 0 < ε < B and let ξ := ε 2B 2 . This implies that 0 < ξ < 1 2B , so we can already conclude that the first statement of the lemma holds for this particular choice of ξ . For all s ∈ S and all real K, since F M and 1 − ξ S∆M = D M are positive, we infer from Equation (20) that

Since |∆M| ≤ B and 0 < ε < B, we find that

We now restrict our attention to those s ∈ S for which

where the first equality holds because S 2 = S. (22) now completes the proof of the second statement.

We now prove the last statement, dealing with the computability of F M . Since ∆M and ξ are assumed to be computable and S is assumed to be recursive, we infer from Equation (21) that the multiplier process D M is computable too. If we now invoke Proposition 7, we find that F M = D ⊚ M is therefore computable as well.

Theorems 19 and 21 provide statements that hold 'almost surely for a forecasting system ϕ': any path is almost surely random, and the limsup average gain for Sceptic along any path-where the average is taken over any recursive selection of situations-for betting on a fixed gamble with rates provided by Forecaster is almost surely non-positive; the corresponding liminf average gain for Forecaster is almost surely non-negative. The following theorem connects these two properties, and at the same time gets rid of their 'almost sure' flavour: if we concentrate on a specific path that is random, then the limsup average gain for Sceptic along that path-where the average is again taken over any recursive selection of situations-for betting on a fixed gamble with rates provided by Forecaster is surely non-positive. Interestingly, and in contrast with Theorems 19 and 21, we need the forecasting system to be computable for our argumentation to work. We're convinced that this computability requirement can be weakened considerably (but not dropped altogether), but we refrain from going in that direction here, because doing so would come at the cost of an even more abstract formulation, and because the version we state below suffices for our present purposes.

Theorem 23 (Relative frequencies for selection processes). Consider a computable forecasting system ϕ : S → I and a path ω ∈ Ω that is A-random for ϕ. Let (I 1 , . . . , I n , . . . ) be the corresponding sequence of interval forecasts I n = [p n , p n ] := ϕ(ω 1:n−1 ) for the path ω.

In short, the proof by contradiction proceeds in two steps. First, we argue that if the inequality isn't satisfied for some gamble h, then we can always find another rationalvalued gamble h ′ close to it for which the inequality also fails. In a second step, we show that we can use the gamble h ′ to construct a positive test supermartingale F M for ϕ of the type considered in Lemma 22 , and that this F M is unbounded on ω. Since this F M is computable because ϕ and h ′ are, this contradicts the A + C -randomness, and therefore also the A-randomness, of ω.

Proof of Theorem 23. By Proposition 11, it suffices to prove the result for the special case that A is the set A + C of all computable positive test processes. Assume ex absurdo that the inequality isn't satisfied for some gamble h on {0, 1}. Then there is some rational 0 < ε < 1 such that

Let h ′ be any rational-valued gamble on {0, 1} such that h ≤ h ′ ≤ h + ε. Then for all k ∈ N 0 , we find that h

, using coherence property C5 for the last inequality. It therefore follows that

where we used Equation (19) for the equality.

Then on the one hand, we infer from Equation (18) 

Now, consider any real R > 0. Since lim n→∞ ∑ n k=0 S(ω 1:k ) = ∞, there is some m R ∈ N 0 such that exp ε 2 4B 2 ∑ m R −1 k=0 S(ω 1:k ) > R. Due to Equation (24) , this implies that F M (ω 1:r R ) > R, with r R := n m R . So, in conclusion, we find that for any R > 0, there is some r R ∈ N 0 such that F M (ω 1:r R ) > R. This tells us that the positive test supermartingale F M is indeed unbounded on ω.

If we can now show that F M is also computable, this will contradict the assumed A + Crandomness of ω for ϕ. Recall from the argumentation above that F M is the positive test supermartingale constructed in Lemma 22, for the particular choices

Hence, since ε is rational, the real numbers B and ξ are rational and therefore definitely computable. Since h ′ is rational, the inequalities h ′ (1) ≥ h ′ (0) and h ′ (1) ≤ h ′ (0) are decidable. Therefore, and because the computability of ϕ means that ϕ and ϕ are computable, Equations (2) and (1) imply that the real process E ϕ(s) (h ′ ), s ∈ S, is computable. For any x ∈ {0, 1}, since we know from Equation (16) If we take a closer look at our argument in this proof, we see that it allows us to derive the desired result for A-randomness, but that it does not work for Schnorr random paths ω. Indeed, it follows from the assumptions that the computable test supermartingale F M from Lemma 22 that does the heavy lifting in the proof, is unbounded on ω, but not necessarily computably so. The argument shows that a sufficient condition for the computable unboundedness of F M on ω is that the map

which gives the number ζ (n) of selected outcomes along the segments ω 1:n of the Schnorr random path ω, should be recursive. But, even though the selection process S is assumed to be recursive, the corresponding ζ in general won't be, simply because the random path ω typically isn't recursive. This analysis points to a fairly direct way of salvaging the result for Schnorr-random paths as well: when we make sure that the selection process S depends not on the situations s themselves, but only on their depth |s| in the event tree, so not on the history of the outcomes but only on the time that has passed, then ζ will be recursive as soon as S is. This brings us to a new formulation, where we replace the selection process S : S → {0, 1} by the simpler notion of a selection function σ : N → {0, 1}. At any 'time point' k ∈ N, if σ (k) = 1, then the outcome ω k is selected along the path ω, and if σ (k) = 0, it isn't.

Theorem 24 (Relative frequencies for selection functions). Consider a computable forecasting system ϕ : S → I and a path ω ∈ Ω that is A-random for ϕ. Let (I 1 , . . . , I n , . . . ) be the corresponding sequence of interval forecasts I n = [p n , p n ] := ϕ(ω 1:n−1 ) for the path ω. If σ is a recursive selection function such that lim n→∞ ∑ n k=1 σ (k) = ∞, then

≥ 0 for any gamble h on {0, 1}.

The same conclusion continues to hold when ω is Schnorr random for ϕ.

Proof. By Proposition 16, it clearly suffices to prove the result for Schnorr randomness. Consider the selection process S : S → {0, 1} defined by S(s) := σ (|s| + 1) for all s ∈ S. Since σ is recursive and lim n→∞ ∑ n k=1 σ (k) = ∞, it also follows that S is recursive and that lim n→∞ ∑ n k=0 S(ω 1:k ) = ∞.

Assume ex absurdo that the inequality isn't satisfied. This implies that there is some rational 0 < ε < 1 such that

.

As we have shown in the proof of Theorem 23, this implies that there is a computable positive test supermartingale F M for ϕ and a computable real number B > 0 such that, for all m ∈ N 0 , there is some n m ≥ m such that

where we have defined the map τ σ :

So for all m ∈ N 0 , there is some n m ≥ m such that F M (ω 1:n m ) ≥ τ σ (n m ), which implies that

Since ε is rational, B > 0 is computable and σ is recursive, we also know that τ σ is computable. Furthermore, τ σ is non-decreasing because ∑ n k=1 σ (k) is non-decreasing in n, and it is unbounded because lim n→∞ ∑ n k=0 σ (k) = ∞ and ε > 0. We conclude that τ σ is a real growth function such that lim sup n→∞ [F M (ω 1:n ) − τ σ (n)] ≥ 0. Proposition 12(ii) then guarantees that the computable test supermartingale F M for ϕ is computably unbounded on ω, which contradicts the assumed Schnorr randomness of ω for ϕ.

From now on, we turn to the special case where the interval forecasts I ∈ I are constant, and don't depend on the already observed outcomes. This leads to a generalisation of the classical case I = { 1 /2} of the randomness associated with a fair coin.

In the rest of this section, unless explicitly stated to the contrary, A is any arbitrary but fixed set of allowable test processes. For any interval I ∈ I , we denote by γ I : S → I the corresponding so-called stationary forecasting system that assigns the same interval forecast I to all situations: γ I (s) := I for all s ∈ S.

In order to investigate the mathematical properties of imprecise randomness, it will be helpful to associate, with any path ω, the collection of all interval forecasts for which the corresponding stationary forecasting system makes ω A-random:

and we use the special notations I + C (ω), I C (ω), I ⊚ ML (ω) and I ML (ω) in the cases that A is equal to A + C , A C , A ⊚ ML and A ML , respectively. Similarly, I S (ω) := {I ∈ I : γ I ∈ Φ S (ω)} = {I ∈ I : γ I makes ω Schnorr random}.

Proposition 16 and Equation (15) imply that

Most of our efforts in this section will be devoted to investigating the mathematical structure of these special sets of interval forecasts. As immediate consequences of the results proved earlier in Sections 5 and 6, we find that all these sets of interval forecasts associated with a random path are non-empty and increasing.

Proposition 25 (Non-emptiness). For all ω ∈ Ω, [0, 1] ∈ I A (ω) ⊆ I S (ω), so any sequence of outcomes ω has at least one stationary forecast that makes it A-random and therefore also Schnorr random: I A (ω) = / 0 and I S (ω) = / 0.

Proof. This is an immediate consequence of Proposition 9, with γ [0,1] = ϕ v ∈ Φ A (ω), and Equation (26).

Proposition 26 (Increasingness). For all ω ∈ Ω and any I, J ∈ I : (i) if I ∈ I A (ω) and I ⊆ J, then J ∈ I A (ω);

(ii) if I ∈ I S (ω) and I ⊆ J, then J ∈ I S (ω).

Proof. This follows from Propositions 10 and 18, because I ⊆ J implies γ I ⊆ γ J .

Proposition 27. Consider two sets A, A ′ of allowable test processes such that A ′ ⊆ A.

Proof. This follows immediately from Proposition 11 and Equation (26). 8.1. Computable stochasticity. Before we continue our study of the structure of the sets of interval forecasts associated with a given random path, it will be helpful to make a small detour, and to consider the behaviour of relative frequencies along random paths. Interestingly, Theorem 23 implies the consistency property in Corollary 28 below, which is a counterpart in our more general context of the notion of computable stochasticity or Church randomness in the precise fair-coin case where I = { 1 /2} [1] . However, quite remarkably, and seemingly in contrast with Theorem 23, this corollary does not impose any computability requirements on the interval forecast I. Computable stochasticity, or Church randomness, is a notion that goes back to Alonzo Church's account of randomness [6] . He required of a random path ω that for any recursive selection process S such that ∑ n k=0 S(ω 1:k ) → ∞,

In other words, the relative frequencies of the ones-the successes-in the outcomes that S selects along the random path ω should converge to the constant probability 1 /2 of a success. It is well-known that all paths that are computably random-and therefore also all Martin-Löf random paths-for a stationary forecast I = { 1 /2} are also computably stochastic, or Church random; see for instance Refs. [1, 62] . In our generalisation, we will see that our notions of randomness no longer necessarily imply such convergence, but we're still able to conclude that the limits inferior and superior of the relative frequencies of the successes in the selected outcomes of a random path must lie in the forecast interval.

Corollary 28 (Church randomness). Consider any path ω ∈ Ω and any constant interval forecast I = [p, p] ∈ I A (ω) that makes ω A-random. Then for any recursive selection process S : S → {0, 1} such that ∑ n k=0 S(ω 1:k ) → ∞:

Proof. First, assume that I is computable. It follows from Proposition 5 that γ I is computable as well. If I isn't computable, then for any ε > 0, since all rational numbers are computable, there is some computable J = [q, q] ∈ I such that p − ε ≤ q ≤ p ≤ p ≤ q ≤ p + ε. Since I ⊆ J, it follows from Proposition 26 that also J ∈ I A (ω). Since, moreover, J is computable, it follows from the first part of the proof that

Since ε > 0 is arbitrary, this completes the proof.

For paths that are (only) Schnorr random, we will discuss below that this result needn't hold, but we can prove a weaker result, whose proof is completely similar-and therefore omitted-but now based on Theorem 24.

Corollary 29 (Weak Church randomness). Consider any path ω ∈ Ω and any constant interval forecast I = [p, p] ∈ I A (ω) that makes ω A-random. Then for any recursive selection function σ such that lim n→∞ ∑ n k=0 σ (k) = ∞:

The same conclusion continues to hold when I makes ω Schnorr random.

That Corollary 28 needn't hold for Schnorr randomness, is in accordance with the fact that, in the particular fair-coin case where I = { 1 /2}, Schnorr randomness is known not to imply computable stochasticity either. This was in fact shown by Yongge Wang [62] , who proved the existence of a Schnorr random pathω and a computable test martingaleM for γ 1/2 such that (i)M is unbounded-but not computably so-onω, also implying thatω isn't computably random; (ii) for all s ∈ S, either (∀x ∈ {0, 1})M(sx) = 2xM(s) or (∀x ∈ {0, 1})M(sx) =M(s); and as a consequence also (iii) ifM(ω 1:n ) = 2ω nM (ω 1:n−1 ) thenω n = 1, for all n ∈ N. One immediate conclusion we can draw from these conditions, is thatM remains positive onω, soM(ω 1:n ) > 0 for all n ∈ N 0 , simply because (ii) implies that ifM ever becomes zero, it remains zero, and can therefore then never become unbounded on ω, contradicting (i). Another conclusion we can draw from (ii), is thatM assumes values in the set {0} ∪ {2 m : m ∈ N 0 }. This implies that, in situations s such thatM(s) > 0, it is decidable which of the two multiplication rules applies in (ii). Hence, the selection processŜ, defined byŜ is recursive. In combination with (iii), this implies that S(ω 1:n−1 ) = 1 ⇒ω n = 1 for all n ∈ N.

Since it follows from (i) that the first multiplication rule in (ii) must apply an infinite number of times onω, we infer from the conclusion (27) thatŜ selects a subsequence of ones fromω, so the corresponding sequence of relative frequencies on this recursively selected subsequence converges to 1, thus violating computable stochasticity: Schnorr randomness does not imply computable stochasticity. It also follows from these considerations thatM either doubles or remains constant onω, and that it doubles precisely in those situationsω 1:n whereŜ(ω 1:n ) = 1. Hence, if we let ζ (n) := ∑ n−1 k=0Ŝ (ω 1:k ) in accordance with Equation (25), then M(ω 1:n ) = 2ζ (n) for all n ∈ N 0 .

The mapζ can't be recursive, because if it were,M would be computably unbounded onω, contradicting the Schnorr randomness ofω. So, we see that the sufficient condition for 'convergence' that we mentioned following the proof of Theorem 23, namely the recursive character of ζ in Equation (25), is perfectly at ease with Wang's example, as it isn't satisfied for this particular case ζ =ζ . Observe, by the way, that the recursive character of ζ in Equation (25) of the selection process S on the random path ω. It should therefore not be surprising that recursive selection functions, such as this σ S,ω , play such an important part in our Theorem 24 and Corollary 29. This also means that if we were to strengthen the requirements on the selection processes S in Theorem 23 and Corollary 28 from 'being recursive' to 'being recursive and displaying recursive behaviour on the path under consideration', then the corresponding (weaker) computable stochasticity result would still hold for all Schnorr random paths. This is essentially what we do in Theorem 24 and Corollary 29. Any criticism of Schnorr randomness along the lines of Wang's argument [62] will therefore have to include an argumentation for why such a strengthening of the requirements on the selection processes is unreasonable or undesirable, or alternatively, why selection processes rather than selection functions appear in the requirements.

The structure of the interval forecasts that make a path random. We return to our study of the mathematical structure behind constant interval forecasts. Our digression about Church randomness around Corollary 28 now displays its usefulness, because it allows us to prove the following consistency result: any collection of constant interval forecasts that make some path random must have a non-empty intersection. 

Proof. It clearly suffices to prove the inclusions in Equation (28) 

Whether the non-empty closed intervals I A (ω) and I S (ω) themselves also make the path ω A-random, respectively Schnorr random, depends on the case at hand: we will come across an example in Section 9 where they do (Section 9.1), and another example where they don't (Section 9.2).

We continue our discussion by introducing the following subsets of [0, 1], which respectively collect the left and right boundaries of the interval forecasts that make a given path ω ∈ Ω random: 

and similarly for the Schnorr variants. Proposition 30 also implies the following consistency property:

All of this is illustrated in Figure 3 for the special, but in no way atypical, case that A = A C . It is obvious that, for any I ∈ I A (ω), we have that min I ∈ L A (ω) and max I ∈ U A (ω), and similarly for the Schnorr randomness variants. We're about to prove, as a result of Propositions 31-33 below, that for weak Martin-Löf randomness, computable randomness and Schnorr randomness, the converse is also true. Therefore, in those cases, where A is equal to A C or A ⊚ ML , I ∈ I A (ω) ⇔ min I ∈ L A (ω) and max I ∈ U A (ω)

I ∈ I S (ω) ⇔ min I ∈ L S (ω) and max I ∈ U S (ω) .

Proof of Equation (29) . We first give a proof of the converse implication for A-randomness. Consider any I = [p, p] ∈ I for which p ∈ L A (ω) and p ∈ U A (ω). That p ∈ L A (ω) implies by Proposition 26 that also [p, 1] ∈ I A (ω). Similarly, p ∈ U A (ω) implies by Proposition 26 that also [0, p] ∈ I A (ω). Propositions 31 and 32 then guarantee that, indeed,

The proof for Schnorr randomness is completely similar, but uses Proposition 33 rather than Propositions 31 and 32. The idea behind the proof is that we show how to write any lower semicomputable supermartingale multiplier for γ I∩J as a product of two lower semicomputable supermartingale multipliers, one for γ I and one for γ J .

Proof of Proposition 31. Let K := I ∩ J. We will prove that K ∈ I ⊚ ML (ω). Let I = [p, p] and J = [q, q]. Because of symmetry, we may assume without loss of generality that q ≤ p. Furthermore, due to Proposition 30, we know that then p ≤ q. If we have that I ⊆ J, then I = I ∩ J and therefore, since I ∈ I ⊚ ML (ω), the result holds trivially. Hence, we may assume without loss of generality that q ≤ p ≤ q < p, which implies that

Consider any test supermartingale T in T γ K ,⊚ ML , then we must show that T remains bounded on ω. We know that there is some lower semicomputable supermartingale multiplier D for γ K such that T = D ⊚ . Furthermore, since we know that D is a supermartingale multiplier for γ K and therefore E K (D(s)) ≤ 1, D(s)(0) > 1 implies that D(s)(1) ≤ 1, again by C1. We therefore find that D(s) = D I (s). By combining these two findings, it follows that indeed here also E I (D I (s)) = E K (D I (s)) = E K (D(s)) ≤ 1.

Since we now know that D I is a supermartingale multiplier for γ I , we may conclude that T I := D ⊚ I is a test supermartingale for γ I . Furthermore, since D is lower semicomputable, so is D I , because taking minima and maxima are continuous and monotone (non-decreasing) operations. Hence, T I belongs to T Proof. The proof is almost completely analogous to that of Proposition 31. After replacing A ⊚ ML and I ⊚ ML (ω) with A + C and I C (ω) = I + C (ω) [the equality follows from Equation (26) ], respectively, the only steps that require changes are those that are concerned with lower semicomputability.

First, since T is here a test supermartingale for γ I∩J that belongs to A + C and is therefore positive and computable, we infer from Proposition 8 that there now is some supermartingale multiplier D that is positive and computable, rather than merely lower semicomputable, such that T = D ⊚ . Secondly, we now need to show that the supermartingale multipliers D I and D J are positive and computable, rather than merely lower semicomputable. But this is trivially implied by the positive and computable character of D.

Proposition 33. For any ω ∈ Ω, I S (ω) is closed under (finite) intersections: for any two interval forecasts I and J in I S (ω), we have that I ∩ J ∈ I S (ω).

Proof. The proof starts from the proof of Proposition 32. Taking into account Proposition 15, the only additional complication is that we now also have to prove that if T I and T J are not computably unbounded on ω, then neither is T = T I T J . But this is an immediate consequence of Proposition 14, with µ 1 (n) := T I (ω 1:n ) and µ 2 (n) := T J (ω 1:n ) for all n ∈ N 0 .

A few examples at the extreme ends. We finish the discussion in this section by giving a few immediate examples of possible sets of interval forecasts.

On the one hand, for any precise forecast p ∈ [0, 1], there always are sequences ω that are A-random, and at least as many that are Schnorr random, for the precise stationary forecasting system γ p ; see Corollary 20. These types of random sequences have received most attention in the literature, thus far. For any such sequence, a constant interval forecast I will make it random if and only if it contains the precise forecast p: I A (ω) = {I ∈ I : p ∈ I}. Hence, L A (ω) = [0, p] and U A (ω) = [p, 0], and therefore also p A (ω) = p A (ω) = p;

and similarly for Schnorr randomness. At the other extreme end, any recursive path with infinitely many zeroes and ones will only be random for the vacuous interval forecast.

Proposition 34. If a path ω ∈ Ω is recursive and has infinitely many zeroes and infinitely many ones, then

Proof. Since ω is recursive, the selection functions σ 0 and σ 1 defined by σ 1 (n) := ω n and σ 0 (n) := 1 − ω n for all n ∈ N, are also recursive. Moreover, since ω has infinitely many zeroes and ones, ∑ n k=1 σ 0 (k) → ∞ and ∑ n k=1 σ 1 (k) → ∞. For any I ∈ I S (ω), we then infer from Corollary 29 that We show by means of a number of concrete examples in the next section that, in between these extremes of total imprecision and maximal precision, there lies a-to the best of our knowledge-previously uncharted realm of sequences, with 'similar' unpredictability to the ones traditionally called 'random', for which the intervals L A (ω) and U A (ω) need not always be closed, and more importantly, for which 0 < p A (ω) < p A (ω) < 1-and similarly for Schnorr randomness. This will provide the first evidence for our claim that 'randomness is inherently imprecise'.

Our work on imprecise Markov chains [12, 14, 16, 25, 51] has taught us that in some cases, we can very efficiently compute tight bounds on expectations in non-stationary precise Markov chains, by replacing them with their stationary imprecise versions. Similarly, in statistical modelling, when learning from data sampled from a distribution with a varying (non-stationary) parameter, it seems hard to estimate the time sequence of its values, but we may be more successful in learning about its (stationary) interval range. Similar ideas were also considered earlier by Fierens et al. [20] , when they argued for a frequentist interpretation of imprecise probability models based on non-stationarity.

In this section, we explore this idea in the context of our study of imprecise randomness, and show in a number of interesting examples that randomness associated with nonstationary precise forecasting systems can be captured by a stationary forecasting system, which must then be less precise: we gain simplicity of representation by going from a non-stationary to a stationary one, but we must then pay for it by losing precision. 9.1. A simple example. Let us begin with a simple example to get some idea of where we want to go to. In what follows, A is any set of allowable test processes. We discuss A-randomness here, but completely analogous arguments and conclusions are valid for Schnorr randomness.

Consider any p and q in [0, 1] with p < q, and any path ω that is A-random for the forecasting system ϕ p,q that is defined by

We know from Corollary 20 that there is at least one such path. We now look for the stationary forecasting systems that make this ω A-random, and we intend to show that for all I ∈ I :

which then also implies that L A (ω) = [0, p], U A (ω) = [q, 1], p A (ω) = p and p A (ω) = q.

Proof of Equation (30) . The converse implication follows at once from Proposition 10 and the fact that for any I ∈ I such that [p, q] ⊆ I, the stationary forecasting system γ I is more conservative than ϕ p,q , in the sense that ϕ p,q ⊆ γ I . For the direct implication, assume that I ∈ I A (ω) and fix any ε > 0. Since all rational numbers are computable, there are computable intervals [p, p] ∈ I and [q, q] ∈ I such that

Consider now the forecasting system ϕ ε , defined by

Then ϕ ε is clearly computable and, since ϕ p,q ⊆ ϕ ε , we know from Proposition 10 that ω is A-random for ϕ ε . Therefore, we find that

where the first and third inequality follow from Corollary 29 and Theorem 24, respectively, for appropriately chosen recursive selection functions, and for h = I {1} . Similarly, but now with h = −I {1} , we also find that

Since ε > 0 is arbitrary, this allows us to conclude that min I ≤ p and max I ≥ q, and, therefore, that [p, q] ⊆ I.

A more complicated example. Next, we turn to a more complicated example, where we look at sequences that are 'nearly' random for the constant precise forecast 1 /2, but not quite. We begin by considering the following sequence {p n } n∈N 0 of precise forecasts:

p n := 1 2 + (−1) n δ n with δ n := 8 n + 33 for all n ∈ N 0 .

Since the sequence {δ n } n∈N 0 decreases towards its limit 0 and δ n ∈ (0, 1 /2) for all n ∈ N 0 , we see that p n → 1 /2 and that p n ∈ (0, 1) for all n ∈ N 0 . In this example, we will focus our attention on an arbitrary but fixed path ω that is A ML -random for the computable precise forecasting system ϕ ∼1/2 defined by ϕ ∼1/2 (s) := p |s| for all s ∈ S.

We know from Corollary 20 that there is at least one such path. We will show, in a number of successive steps, that for all A such that A + C ⊆ A ⊆ A ML : We first prove that [p, p] ∈ I ML (ω) for all [p, p] ∈ I such that p < 1 /2 < p, and therefore also [p, p] ∈ I A (ω) and [p, p] ∈ I S (ω), by Proposition 27.

Proof that [p, p] ∈ I ML (ω) if [p, p] ∈ I and p < 1 /2 < p. We provide a proof by contradiction. Assume ex absurdo that there is some I := [p, p] ∈ I such that p < 1 /2 < p and I / ∈ I ⊚ ML (ω). This implies that there is some lower semicomputable test supermartingale M I for the stationary forecasting system γ I that is unbounded on ω.

Consider any m ∈ N 0 such that p n ∈ [p, p] = I for all n ≥ m; this is always possible because p n converges to 1 /2 and p < 1 /2 < p. Let α > 0 be any rational number such that M I (s) ≤ α for all s ∈ S with |s| = m + 1; there always is such an α because the number of situations of length m + 1 is finite. We now consider a new process M, defined by

which is lower semicomputable because M I is lower semicomputable and because α is rational. This process is furthermore positive because M I and α are, and it has unit initial value M( ) = 1 by definition. Hence, it is a test process. To see that it is also a supermartingale for ϕ ∼1/2 , we verify the condition in Equation (4). Consider any s ∈ S. We distinguish three cases: |s| > m, |s| = m and |s| < m. If |s| > m, then

where the first inequality holds because p |s| ∈ I, the second equality follows from coherence property C2, and the second inequality holds because M I is a supermartingale for γ I . If |s| = m, then M I (s·) ≤ α and therefore

where the first inequality holds because p |s| ∈ I, and the second and third inequalities follow from coherence properties C5 and C1, respectively. Finally, if |s| < m, then E p |s| (M(s·)) = E p |s| (1) = 1 = M(s). So we can conclude that E ϕ ∼1/2 (s) (M(s·)) = E p |s| (M(s·)) ≤ M(s) for all s ∈ S. Hence, M is a lower semicomputable test supermartingale for ϕ ∼1/2 . However, by construction, M is unbounded above on ω, simply because M I is unbounded above on ω and α is positive. This contradicts the fact that ω is A ML -random for ϕ ∼1/2 .

We complete the argument by showing that

Taking into account Proposition 27, this will then also tell us that

, meaning that the sequence isn't Schnorr random in the classical 'fair coin' sense, nor computably random or (weakly) Martin-Löf random.

The proof is based on ideas involving Hellinger-like divergences in a beautiful paper by Volodya Vovk [58] : if the forecast sequences produced by two precise forecasting systems along a path ω lie 'far enough' from each other, then it is possible to construct simple test supermartingales for these respective forecasting systems whose product becomes unbounded on ω, implying that ω can't be random for both forecasting systems. Here, we show that this idea can be extended to the case where one of the forecasting systems is imprecise. We will have occasion to use this proof method again, in our proof of Theorem 37.

Proof that [p, p] / ∈ I S (ω) for any [p, p] ∈ I such that p ≥ 1 /2 or p ≤ 1 /2. We only prove the result for p ≥ 1 /2; the proof for the other case is entirely analogous, the main difference with the argument below being that we then need to focus on the even rather than the odd indices.

Let where, for any α, β ∈ (0, 1), we define the gamble f α,β on {0, 1} by

These gamble processes are computable because the sequence (p n ) n∈N 0 is computable and because checking whether |s| is odd is decidable. Furthermore, due to Lemma 35(i), we also know that they're positive. So we find that D I and D ∼1/2 are computable multiplier processes. We now proceed to show that they're in fact computable supermartingale multipliers for γ I and ϕ ∼1/2 , respectively. To see that D I is a supermartingale multiplier for γ I , observe that

where the odd case follows from Lemma 35(iv) because then p |s| < 1 /2 ≤ p, and the even case follows from coherence property C1. To see that D ∼1/2 is a supermartingale multiplier for ϕ ∼1/2 , observe that

using Lemma 35(i) for the odd case. Taking into account Proposition 7, we conclude from the above that D ⊚ I and D ⊚ ∼1/2 are computable test supermartingales for γ I and ϕ ∼1/2 , respectively.

Let us now take a look at the product of D ⊚ I and D ⊚ ∼1/2 . We start by observing that, for all n ∈ N 0 ,

Because of Lemma 35(v) , this implies that, for all n ∈ N 0 ,

if n is odd 1 if n is even.

Hence, for all n ∈ N,

Because the map τ : N 0 → R ≥0 : n → n+32 32 is a real growth function, Proposition 12(ii) guarantees that the product D ⊚ I D ⊚ ∼1/2 is computably unbounded on ω, so Proposition 14 tells us that at least one of the factor supermartingales D ⊚ I and D ⊚ ∼1/2 must be computably unbounded on ω too. But since D ⊚ ∼1/2 is a computable-and therefore also lower semicomputable due to Proposition 4-test supermartingale multiplier for the forecasting system ϕ ∼1/2 , it follows from the assumed A ML -randomness of ω for ϕ ∼1/2 that D ⊚ ∼1/2 can't be computably unbounded on ω, so D ⊚ I must be. Since D ⊚ I is a computable supermartingale for γ I , we conclude that, indeed, [p, p] = I / ∈ I S (ω).

Lemma 35. For any α, β ∈ (0, 1), we consider the gamble f α,β on {0, 1} defined in Equation (31) . Then for any α, β ∈ (0, 1) and I = [p, p] ∈ I , the following statements hold:

is an immediate consequence of the definition of f α,β and E α and the fact that α, β ∈ (0, 1). For statement (ii), observe that, indeed, since α, β ∈ (0, 1),

For statements (iii) and (iv), first observe that it follows from α < β and statement (ii) that f α,β (1) > f α,β (0) and f β ,α (1) ≤ f β ,α (0). Statement (iii) now follows because

where the first equality and the inequality follow from Equations (3) and (1), respectively, and the fact that f α,β (1) > f α,β (0), and where the last equality follows from statement (i). Statement (iv) follows because

where the first equality and the inequality follow from Equations (3) and (1), respectively, and the fact that f β ,α (1) ≤ f β ,α (0), and where the last equality follows from statement (i) with α and β interchanged. Statement (v) follows from Lemma 36 because

Lemma 36. For any α, β ∈ (0, 1), we have that

Proof. The first inequality follows trivially from α, β ∈ (0, 1). To prove the second, let

First observe that

and

Next, we prove that a − b ≥ 1 4 (α − β ) 2 . On the one hand, since a > 0 and b > 0, we know that a + b > 0. On the other hand, we also know that

We therefore find that

using Equation (33) for the third equality and Equation (34) for the inequality. Combined with Equation (32), it follows that, indeed,

The examples in the previous section illustrate that randomness associated with a nonstationary precise forecasting system can also be 'described' as randomness for a simpler, stationary but then necessarily imprecise, forecasting system. This observation might lead to the suspicion that all stationary imprecise forms of randomness can be 'explained away' as such simpler representations of non-stationary but precise forms of randomness. This would imply that the imprecision-or loss of precision-in the stationary forecasts isn't essential, and can always be dismissed as a mere artefact, a simple effect of using a stationary representation that isn't powerful enough to allow for the ideal representation, which must be, one would suspect, always precise but non-stationary.

We mean to show in this section that this suspicion is misguided, and even flat out wrong when we focus on computable forecasting systems: we will see that there are paths that are random for a computable stationary interval forecasting system that are never random for any computable precise forecasting system, be it stationary or not. This serves to further corroborate our claim that randomness is indeed inherently imprecise, as its imprecision can't be explained away as an effect of oversimplification. The imprecision involved is furthermore non-negligible, and can be made arbitrarily large, because besides excluding the possibility of randomness of such paths for precise computable forecasting systems, we also show they can't be random for any computable forecasting system whose highest imprecision is smaller than that of the original, stationary one.

Theorem 37 (Imprecision can't be explained away). Consider any set of allowable test processes A, and any interval forecast I = [p, p] ∈ I . Then there is path ω ∈ Ω that is A-random-and therefore also Schnorr random-for the stationary interval forecast I, but that is never Schnorr random-and therefore never A-random-for any computable forecasting system ϕ whose highest imprecision is smaller than that of I, in the specific sense that sup s∈S ϕ(s) − ϕ(s) < p − p.

Our argument is crucially inspired by Volodya Vovk, who hit upon the essential idea and provided a first sketch for it. We use the same basic idea, but follow an argumentation and construction that is different in a number of ways, in order to also-contrary to his approach-deal with precise computable forecasts that may be irrational or become zero, and more importantly, with imprecise computable forecasts whose imprecision is smaller than that of the stationary one. Our proof method also has a more constructive flavour than his, which was based on an almost sure convergence argument. Interestingly, our more constructive line of reasoning is inspired by the ideas and techniques he proposed in another paper [58] , and whose extension to our imprecise context we've already used for the example in Section 9.2. Stripped to its bare essentials, the argument is actually quite simple. We construct a precise forecasting system ϕ p,p whose forecasts are included in I and infinitely often lie 'far enough' from each of the countably many computable forecasting systems ϕ m whose highest imprecision is smaller than that of I. This then guarantees that no path can be simultaneously random for ϕ p,p -and therefore for γ Iand for any such ϕ m .

Proof of Theorem 37. To start the argument, we consider any recursive map λ : N 0 → N 0 such that for each m ∈ N 0 there are infinitely many n ∈ N 0 that are mapped to m, meaning that λ (n) = m. For instance, λ (n) could be the number of trailing zeroes in the binary expansion of n + 1, so λ (n) := max{k ∈ N 0 : (n + 1)2 −k ∈ N} for all n ∈ N 0 , and consequently λ −1 ({m}) = {2 m (2ℓ + 1) − 1 : ℓ ∈ N 0 } for all m ∈ N 0 .

We also let ϕ 0 , ϕ 1 , . . . , ϕ n , . . . be any enumeration of the (countably many) computable forecasting systems, and we use this enumeration to let N 0,I := m ∈ N 0 : sup s∈S ϕ m (s) − ϕ m (s) < p − p identify the set of all computable forecasting systems whose highest imprecision is smaller than that of the interval forecast I.

We're now going to fix any m ∈ N 0,I , or in other words, any such computable forecasting system ϕ m . Let 0 < ε m < 1 be any rational number [which there always is] such that

Also, let p m and p m be any two rational numbers [which there always are] such that p < p m < p + ε m and p − ε m < p m < p, and consider any N m ∈ N such that 2 −N m < ε m . Since the real process ϕ m is computable [because the forecasting system ϕ m is], we know from Proposition 3 and the definition of a recursive net of rational numbers that there are three recursive maps a m , b m and ς m from S × N 0 to N 0 such that b m (s, n) > 0 and (−1) ς m (s,n) a m (s, n) b m (s, n) − ϕ m (s) ≤ 2 −n for all s ∈ S and n ∈ N 0 .

Hence, if we let ϕ ′ m be the rational-valued process defined by

then clearly |ϕ ′ m (s) − ϕ m (s)| ≤ 2 −N m < ε m for all s ∈ S. We also establish a number of inequalities that will be important further on in this proof. On the one hand, we have that

where the first inequality holds because I ⊆ [0, 1], the second and third inequalities follow from our choice of p m , the fourth inequality follows from the second, and the fifth inequality follows from the third. On the other hand, we have that

where the last inequality holds because I ⊆ [0, 1], the third and fourth inequalities follow from our choice of p m , the second inequality follows from the fourth, and the first inequality follows from the third. Furthermore, since sup s∈S ϕ m (s) − ϕ m (s) ≥ 0, it follows from Equation (35) that 6ε m < p − p, which implies that p + 2ε m < p + 4ε m < p − 2ε m . Combining these inequalities with the ones in Equations (36) and (37), we finally get that

With this set-up phase completed, we're now ready to use the map λ , and the p m , p m , ε m and ϕ ′ m we have just determined for any m ∈ N 0,I , to define the following precise forecasting system ϕ p,p : 10

for all s ∈ S.

(39) We also consider any path ω ∈ Ω that is A-random-and therefore, due to Proposition 16, also Schnorr random-for this precise forecasting system ϕ p,p . We know from Corollary 20 that there is at least one such path; in fact, we know from Theorem 19 that the set of all such paths has lower probability one in the probability tree associated with the precise forecasting system ϕ p,p .

For any m ∈ N 0,I , we know from Equation (38) that p < p m < p m < p, so it follows from Equation (39) that ϕ p,p (s) ∈ [p, p] = I for all s ∈ S. This implies that ϕ p,p ⊆ γ I , where γ I is the stationary forecasting system associated with the constant interval forecast I. Since ω was assumed to be A-random for ϕ p,p , it follows from Proposition 10 that ω is also A-random for γ I .

We will be done if we can show that the path ω isn't Schnorr random for any computable forecasting system ϕ m whose highest imprecision is less than that of I. That is, if we can show that the path ω isn't Schnorr random for ϕ m for any m ∈ N 0,I . This is what we now set out to do.

To this end, we consider an arbitrary but fixed m ∈ N 0,I and are going to construct a computable test supermartingale for ϕ m that is computably unbounded on ω. Since we know from Equation (38) that 0 < p m < p m + ε m < p m − ε m < p m < 1, we can define a multiplier process D m by where, for any α, β ∈ (0, 1), the gamble f α,β on {0, 1} is defined by Equation (31) in Section 9. For given p m , p m and ε m , this multiplier process D m is computable because p m , p m and ε m are rational and because the recursive character of λ , a m , b m and ς m guarantees that the equalities and inequalities in this expression are decidable. D m is furthermore positive by Lemma 35(i).

To prove that D m is a supermartingale multiplier for ϕ m , we show that E ϕ m (s) (D m (s)) ≤ 1 for all s ∈ S. There are, of course, three possible cases.

If

Finally, we consider the case that λ (|s|) = m and ϕ ′ m (s) > p m − 2ε m . Since Equation (35) implies that ϕ m (s) − ϕ m (s) < p − p − 6ε m , we then find that

where the second inequality holds because |ϕ ′ m (s) − ϕ m (s)| < ε m , the fourth inequality because p m was chosen to make sure that p − ε m < p m , and the fifth inequality because p m was chosen to make sure that p m < p + ε m . It therefore follows from Lemma 35(iv) that, also in this case,

So D m is indeed a supermartingale multiplier for ϕ m . Since we had already established that D m is computable and positive, it follows that D ⊚ m is a positive computable test supermartingale for ϕ m , also taking into account Proposition 7.

We're clearly done if we can show that this D ⊚ m is computably unbounded on ω. To do so, consider the multiplier process D m,p,p defined by We first prove that, for given p m , p m and ε m , this D m,p,p is a positive computable supermartingale multiplier for the forecasting system ϕ p,p . The argumentation is fairly similar to the one given above for D m and ϕ m . Computability follows from the rationality of p m , p m and ε m , and the recursive character of the maps λ , a m , b m and ς m . Positivity follows from Lemma 35(i). To prove that D m,p,p is a supermartingale multiplier for ϕ p,p , we need to show that E ϕ p,p (s) (D m,p,p (s)) ≤ 1 for all s ∈ S.

The case that λ (|s|) = m is again trivial. So, D m,p,p is indeed a positive computable supermartingale multiplier for ϕ p,p . Taking into account Proposition 7, we can conclude that D ⊚ m,p,p is a positive computable test supermartingale for ϕ p,p . This computable test supermartingale D ⊚ m,p,p must furthermore be bounded above on ω, because of the assumed A-randomness of the path ω for ϕ p,p .

The idea for the rest of the proof is now that we're going to show that the product process D ⊚ m,p,p D ⊚ m is computably unbounded on ω, and therefore D ⊚ m must be as well. which is clearly non-decreasing, recursive because λ is, and unbounded because there are infinitely many k ∈ N 0 for which λ (k) = m. Then, for any n ∈ N 0 ,

and therefore, since D ⊚ m,p,p is positive and bounded above by B along ω, also

Now let the map τ m : N 0 → R ≥0 be defined by τ m (n) := B −1 δ ρ m (n) for all n ∈ N 0 . Then τ is computable because ρ m is recursive and because δ and B are rational, and τ is nondecreasing and unbounded because ρ m is non-decreasing and unbounded, and because δ > 1. So, τ m is a real growth function for which D ⊚ m (ω 1:n ) ≥ τ m (n) for all n ∈ N 0 , and therefore also lim sup n→∞ [D ⊚ m (ω 1:n ) − τ m (n)] ≥ 0. We find that the computable test supermartingale D ⊚ m for ϕ m is indeed computably unbounded on ω, by Proposition 12(ii).

For an example showing that the computability condition in this result can't be dropped, and a discussion on the theoretical and practical relevance of this condition, we refer to recent work by Persiau and ourselves [34] .

In yet another beautiful paper we came across while researching this topic, Muchnik, Semenov and Uspensky [31] showed that the set of all paths that correspond to a precise stationary forecast is meagre.

The essence of their argument is the following. They call a path ω lawful if there is some algorithm that, given as input any situation s on the path ω, outputs a non-trivial finite set R(s) of situations t ⊐ s that strictly follow that situation s, such that one of these 'extensions' t is also on the path-meaning that ω ∈ Γ(t). By 'non-trivial', they mean that R(s) is restrictive: it actually eliminates possible extensions. They then go on to show that the set of all lawful paths is meagre, and finally, that random paths, because they satisfy the law of large numbers, are lawful.

In this section, we show that we can extend this argument to imprecise stationary forecasts. This will show that, while, due to Theorem 19, almost all paths are random for a forecasting system-so the random paths are legion-in a measure-theoretic sense, in the specific topological sense of meagreness, they are few.

First of all, let us give a definition of lawfulness that makes the formulation above more precise; see also Figure 4 . A partial function on a domain D is a function that need not be defined on all elements of D, so need not be a map.

Definition 6 (Lawfulness [31, Definition 2.1]). We call algorithm any recursive (partial) function R from S to the collection of finite subsets of S. A path ω ∈ Ω is called lawful for an algorithm R if for all m ∈ N 0 :

(i) R is defined in the situation ω 1:m ; (ii) R(ω 1:m ) is a non-empty finite subset of S such that ω 1:m ⊏ t for all t ∈ R(ω 1:m ); (iii) R(ω 1:m ) is non-trivial: t∈R(ω 1:m ) Γ(t) ⊂ Γ(ω 1:m ); (iv) there is some t ∈ R(ω 1:m ) such that ω ∈ Γ(t).

A path ω ∈ Ω is called lawful if it is lawful for some algorithm R. A path that isn't lawful is called lawless.

· · · ω · · · s FIGURE 4. Visualisation of the main ideas behind the lawfulness of a path ω A set of paths A ⊆ Ω is nowhere dense in Ω [31] if for every s ∈ S, there is some t ∈ S such that s ⊑ t and A ∩ Γ(t) = / 0. A set of paths B ⊆ Ω is then called meagre, or first category, it it is a countable union of nowhere dense sets. We will rely on the following central result in Ref. [31] . To prove that a set of random paths is meagre, it therefore suffices to prove that these random paths are all lawful. This turns out to be not too difficult, because the following proposition shows that relative frequencies along lawless paths behave very 'wildly'. Proof. We give the proof for the lim sup. The proof for the lim inf is completely analogous.

Assume ex absurdo that lim sup n→∞ 

For any given n, r ∈ N with r > 1 and n > 1, we construct an algorithm R n,r as follows. For any s ∈ S with m := |s| ≥ n, we let R n,r (s) be the set of all situations t ∈ S such that |t| = rm and s ⊑ t and rm ∑ k=1 t k < mr − m.

We also let R n,r (s) := R n,r (ω 1:n ) for all s ∈ S with |s| < n. It is clear that R n,r is a recursive map, because the conditions in Equation (41) are decidable. If we can now show that ω is lawful for R n o ,r o , and therefore lawful, we will have a contradiction. To do so, fix any m ∈ N 0 . It follows from the construction of the R n,r that 

so R n o ,r o is indeed defined on ω 1:m , which implies that R n o ,r o satisfies requirement (i) in Definition 6.

Combining Equations (40) and (42) tells us that ω 1:r o max{n o ,m} ∈ R n o ,r o (ω 1:m ), so requirement (iv) in Definition 6 is also satisfied.

We also gather from Equation (42) 

where the inequality follows from t k ≥ 0 for 1 ≤ k ≤ max{n o , m}. This tells us that R n o ,r o satisfies requirement (iii) in Definition 6. We conclude that ω is indeed lawful for R n o ,r o .

So, in order to prove our result, it now suffices to consider that relative frequencies along random paths can't behave so wildly, because they're constrained by our 'weak computable stochasticity' result in Corollary 29. Random paths are typically lawful.

Theorem 40. Let I = [p, p] ∈ I be any closed subinterval of [0, 1] strictly included in [0, 1], so p > 0 or p < 1. Then the set of all paths that are A-random for the stationary forecasting system γ I is meagre. Similarly, the set of all Schnorr random paths for γ I is meagre.

Proof. Consider any ω that is A-random for the stationary forecasting system γ I . Then it clearly suffices to show that ω is lawful, by Theorem 38. Assume ex absurdo that it is lawless. By combining Proposition 39 with Corollary 29 [with recursive selection function σ := 1], we find that p ≤ 0 and p ≥ 1, a contradiction. The proof for Schnorr randomness is identical.

Our argumentation shows that the important distinction for random paths does not lie between precise and imprecise stationary forecasts, but rather between vacuous and nonvacuous forecasts: for any non-vacuous stationary forecast, the set of random paths is meagre, whereas for the vacuous stationary forecast, all paths are random, and therefore the corresponding set of random paths is co-meagre-the complement of a meagre set. We also see that the paths that are random for non-vacuous interval forecasts are 'equally rare' as those that are random for precise forecasts, which, we believe, only adds to their mathematical interest.

The probability of an event is often seen as a precise, or at least ideally precise, number. Apart from a few notable exceptions in earlier accounts [17, 24, 43, 44] , a more determined investigation into reasons for letting go of this idealisation, and into mathematical ways to achieve this, only started in the later decades of the 20th century [26, 27, 41, 42, 45, 60] ; see also Refs. [2, 53] for overviews. Most of this work centred on the decision-theoretic and epistemic aspects of probability [27, 60] , while some contributions were more agnostic in this respect [45, 46] , but a few attempts were also made [19, 20, 22, 61] to justify letting go of precision also for probabilities with a more physical, or frequentist, interpretation.

We believe this paper is the first systematic attempt at reconciling imprecision with the study of (frequency-based or algorithmic) randomness along the lines of von Mises [55] , Church [6] , Kolmogorov [23] , Ville [54] , Martin-Löf [30] , Levin [28] and Schnorr [39, 40] , to name only a few of the early protagonists. We show that this is both possible and interesting. We see that, besides the sequences that are random for precise forecasts, new realms of sequences arise that are random for interval forecasts. They have intriguing properties, and are as topologically rare as their precise counterparts, in the sense that they also constitute meagre sets. Even with the limited number of examples we have examined here, it should be apparent that incorporating imprecision-or interval forecasts-into the study of randomness allows for more mathematical structure to arise. This is relevant in and of itself, but we would argue that our treatment also allows us to better understand and place, as special cases, the existing results in the precise limit. This, by the way, also holds true for the more epistemic accounts of imprecision in probability; see for instance Ref. [53] for a more detailed account.

This leads us to our rather provocative title for this paper. A number of people, while not averse to the idea of allowing for imprecision in the study of randomness, advised us to tone down our claim that 'Randomness is inherently imprecise', and suggested replacing it by something weaker, such as 'Some aspects of randomness cannot be adequately dealt with using precise forecasts only'. Evidently, we have decided against that, and it behoves us here to explain our reasons for doing so, other than the plainly polemic or merely rhetorical ones. Simply stated, we are actually convinced that the statement in our title holds true, and that there is more to randomness than the by now classical account for precise forecasts would have us suspect.

First off, we have seen in Section 9 that on the one hand, 'imprecise randomness' can arise as a useful stationary model simplification when dealing with non-stationarity, which points to practical reasons for allowing imprecision in the study of randomness. But, on the other hand, we've also been led, in Section 10, to the conclusion that imprecise randomness has a more fundamental role, because there are sequences that are random for a given computable interval forecast, but not for any computable (more) precise forecast.

Of course, we agree that the initial ideas for characterising what randomness is, were based on probabilistic limit laws such as the convergence of relative frequencies, which as Corollaries 28 and 29 suggest, are harder to guarantee in exactly the same form in our imprecise context. But the seminal martingale-theoretic accounts of Ville [54] , Schnorr [39, 40] and Levin [28] , as well as the prequential approach by Vovk and Shen [59] , have opened up the path towards useful alternative characterisations, which are much more amenable to letting go of the ideal of precision, as we have shown here.

We see very few reasons for holding on to that perceived ideal, neither from a practical (forecasting and calibration) point of view, nor from a more formal mathematical stance. We have already hinted above at the formal mathematical reasons for allowing for imprecision in the study of randomness: restricting ourselves to precise forecasts hides interesting and useful mathematical structure that, as we see in this paper but also have come to witness in our most recent-still largely unpublished-research efforts, reveals relevant facts even about the precise aspects of randomness. Again, such structural arguments for allowing for imprecision can, incidentally, also be brought to bear in more epistemic and decision-theoretic accounts of uncertainty; see for instance Ref. [53] for examples and related discussion. And as randomness in more recent accounts has been linked with forecasting and calibration, many of the arguments for allowing for imprecision and indecision (see for instance [60, Chapter 5] for extensive discussion) in epistemic uncertainty modelling become relevant to the study of randomness also.

One aspect of what we are saying then, can be summarised as follows: (algorithmic) randomness seems to have acquired a broader meaning and to have become more strongly connected to other issues than only probabilistic convergence laws, and this change of focus makes allowing for imprecision in its foundations much more intuitive and less farfetched than it may once have seemed.

What else do we mean when we say that 'randomness is inherently imprecise'? Randomness, as we perceive it, is about outcome sequences (paths) and forecasting systems 'going together well'. And this going together well has certain implications, which for a given forecasting system, impose restrictions on the behaviour of the successive outcomes in a random path, such as the limit laws in Theorems 23 and 24, and in Corollaries 28 and 29 for stationary forecasts. It is of crucial importance to our argument that these restrictions do not all of a sudden disappear when going from point to interval forecasts. They weaken, perhaps, but don't disappear, as is also made very clear by our discussion in Section 11: the hard cut-off there lies not between precise and imprecise forecasts, but between non-vacuous and vacuous ones. For any non-vacuous stationary forecast, be it precise or imprecise, the restrictions on the corresponding sets of random paths are substantial, and result in these sets being meagre, as Theorem 40 testifies. It is only for vacuous forecasts that the restrictions disappear and that the corresponding randomness notion becomes vacuous as well: all paths are random for such forecasts. Thus, the difference between non-vacuous imprecise and precise randomness may be a matter of degree, perhaps and in certain respects, but not of quality. Why then single out the precise limit case as the only one worthy of the moniker 'randomness'?

This work may seem promising, but we're well aware that it is only a humble beginning. We see many extensions in many directions, so let us briefly discuss a few.

First of all, our preliminary exploration suggests that it will be possible to formulate equivalent randomness definitions in terms of randomness tests, rather than supermartingales. We believe it would be relevant to work this out in much more detail.

Secondly, the approach we follow here is not prequential: we assume that our Forecaster specifies an entire forecasting system ϕ, or in other words an interval forecast in all possible situations (x 1 , . . . , x n ), rather than only interval forecasts in those situations (z 1 , . . . , z n ) of the sequence ω = (z 1 , . . . , z n , . . . ) whose potential randomness we're considering. The prequential approach, which we eventually will want to come to, looks at the randomness of a sequence of interval forecasts and outcomes (I 1 , z 1 , I 2 , z 2 , . . . , I n , z n , . . . ), where each I k is an interval forecast for the as yet unknown X k , which is afterwards revealed to be z k , without the need for a specification of forecasts in other situations that are never reached; see the paper by Vovk and Shen [59] for an account of how this works for precise forecasts and Martin-Löf randomness.

Thirdly, we perceive the need to connect our work more firmly with earlier approaches to associating imprecision with randomness through unstable relative frequencies and nonstationarity, most notably by Terrence Fine's group [19, 20, 61] .

And finally, and perhaps most importantly, we believe this research could be a very early starting point for a more systematic approach to statistics that takes imprecise or set-valued parameters more seriously, when learning from finite amounts of data. Ahead of this, more work must be done to extend our mathematical formulation to non-binary outcomes, to name just one important generalisation; see Ref. [33] for a step in this direction.

As with most of our joint work, there is no telling, after a while, which of us had what idea, or did what, exactly. We have both contributed equally to this paper. But since a paper must have a first author, we decided it should be the one who took the first significant steps: Gert, in this case.

We are grateful to Philip Dawid and Volodya Vovk for their inspiring and helpful comments and guidance, and to Gert Vermeulen for introducing us to the wonders of Archimedes' ancient home town. Teddy Seidenfeld, Glenn Shafer and Alexander Shen, as well as a number of anonymous reviewers, have helped with useful suggestions and constructive criticism. Gert's research and travel were partly funded through project number G012512N of the Research Foundation -Flanders (FWO). Jasper was a Post-Doctoral Fellow of the FWO when much of this research was being done, and he wishes to acknowledge its financial support. In more recent years, Gert and Jasper's work was also supported by H2020-MSCA-ITN-2016 UTOPIAE, grant agreement 722734.

Proof of the claims about infimum/minimum selling prices. In Section 2, we advanced the claim that working with infimum acceptable selling prices is, in the context of this paper, equivalent to working with minimum acceptable selling prices, and similarly for supremum and maximum acceptable buying prices. Let us spend some effort here to understand why that is.

If E I ( f ) is interpreted as a minimum acceptable selling price for f (X), this means that Forecaster is willing to sell the uncertain reward f (X) for any price β down to and including E I ( f ). If, on the other hand, E I ( f ) is only interpreted as an infimum acceptable selling price for f (X), then this means that Forecaster is willing to sell the uncertain reward f (X) for any price β strictly higher than E I ( f ), but nothing is stated about his actual willingness to sell for the price E I ( f ) itself.

To clarify this idea, let us denote by S the set of all gambles f : {0, 1} → R that Forecaster accepts to give away, and that are therefore available to Sceptic. If pay-offs are expressed in units of linear utility, this set S will arguably be a convex cone, and it will include the non-positive gambles f ≤ 0, simply because it is rational for Forecaster to give away a partial loss [36, 53, 60] .

An upper expectation E I ( f ) is typically interpreted as Forecaster's infimum acceptable selling price for the gamble f (X), meaning that [53, 60] E I ( f ) = inf{β ∈ R : Forecaster accepts to sell f (X) for price β }

We then see that the functional E I can be used to characterise the convex cone S , but only up to border behaviour, as Figure 5 and the following argumentation clarify. Indeed, we can readily infer the following implications from Equation (43) and the fact that S is a convex cone that includes all non-positive gambles:

So we see that the marginal gambles g-those gambles for which E I (g) = 0-are the only ones for which the difference in interpretation between infimum and minimum acceptable buying prices matters in the context of this paper. When E I (g) is interpreted as a minimum acceptable selling price, this implies that Forecaster will actually make the marginal gamble g available to Sceptic. But when E I (g) is interpreted only as an infimum acceptable selling price, then the fact that E I (g) = 0 tells us nothing about whether Forecaster will make g available to Sceptic: he may, or he may not. The interpretation of E I ( f ) as a minimum acceptable selling price is essentially reflected in Equation (4), where we define a supermartingale M by requiring that in each situation s its process difference ∆M(s) must be available to Sceptic, because Forecaster is willing to sell it (to Sceptic) for some price lower than or equal to 0:

Were we to interpret E I ( f ) only as an infimum acceptable selling price, this would essentially mean that in each situation s the uncertain reward ∆M(s) − δ must be available to Sceptic for all δ > 0, but not necessarily for δ = 0; but now, of course, as indicated above, we must also take into account that a non-positive ∆M(s) ≤ 0 will also be available to Sceptic. We could have this reflected conservatively in the strict supermartingale condition:

∆M(s) ≤ 0 or E ϕ(s) (∆M(s)) < 0 for all s ∈ S.

We will call any process satisfying this requirement (44) a strict supermartingale for ϕ. Proving our statement about the equivalence of infimum and minimum acceptable selling prices in this randomness context then amounts to showing that our randomness notions 5 . Depiction of the convex cone of gambles that Forecaster accepts to give away, and that are therefore available to Sceptic. The region that is shaded (lighter or darker) blue, with the exclusion of the border (in red), depicts the gambles f that Forecaster will definitely accept to give away, because they have a negative infimum acceptable selling price E I ( f ) < 0 or because they're non-positive (the darker blue ones).

The marginal gambles f (in red) are the ones for which the infimum acceptable selling price E I ( f ) is zero.

remain unaffected by replacing supermartingales with strict supermartingales in their definition.

Because the strict supermartingale condition is stronger than the supermartingale condition, it is clearly enough to show that any path ω that is not random in the supermartingale sense, also can't be random in the strict supermartingale sense. To prove this, consider any test supermartingale T , and define the real process T ′ by , it follows readily [from C2 and C4] that T ′ is a strict test supermartingale. It is moreover (lower semi)computable when T is, and it is (computably) unbounded on the same paths as T . This implies that our notions of Martin-Löf randomness, computable randomness and Schnorr randomness indeed remain unaffected by replacing supermartingales with strict supermartingales in their definition. For weak Martin-Löf randomness, we need a slightly different argument. Consider any lower semicomputable supermartingale multiplier D, and the related multiplier process D ′ defined by D ′ (s) := D(s) (|s| + 1)(|s| + 3) (|s| + 2) 2 for all s ∈ S.

Then D ′ is clearly also lower semicomputable, and E ϕ(s) (D ′ (s)) = (|s| + 1)(|s| + 3) (|s| + 2) 2

E ϕ(s) (D(s)) < 1 for all s ∈ S,

where the equality follows from C2, and the strict inequality from the assumption that D is a supermartingale multiplier, and C1. Hence, D ′ is a supermartingale multiplier as well. Now, consider the real process T ′ defined by T ′ (s) := D ⊚ (s) 1 2

|s| + 2 |s| + 1 for all s ∈ S.

Then T ′ is non-negative since D ⊚ is, and T ′ ( ) = 1, so T ′ is a test process. Also, T ′ (s·) = D ⊚ (s·) 1 2 |s| + 3 |s| + 2 = D ⊚ (s)D(s) 1 2

|s| + 3 |s| + 2 = T ′ (s)D(s) (|s| + 1)(|s| + 3) (|s| + 2) 2 = T ′ (s)D ′ (s) for all s ∈ S, which shows that T ′ is the test supermartingale generated by the supermartingale multiplier D ′ . Equation (5) now tells us that E ϕ(s) (∆T ′ (s)) = T ′ (s) E ϕ(s) (D ′ (s)) − 1 for all s ∈ S.

The same Equation (5) also guarantees that if T ′ (s) = 0, then also ∆T ′ (s) = 0, and therefore it follows readily from Equation (45) that T ′ satisfies the strict supermartingale condition (44) . Finally, Equation (46) guarantees that T ′ and D ⊚ become unbounded on the same paths.

Proof of Proposition 2. We begin by proving that inf f ≤ E ϕ ( f ) ≤ sup f . Conjugacy will then imply that also inf f ≤ E ϕ ( f ) ≤ sup f , and therefore that both E ϕ ( f ) and E ϕ ( f ) are real numbers. This fact will then be used further on. The remainder of statement E1 will be proved further below. Since all constant real processes are supermartingales [by C1], we infer from Equation (7) that, almost trivially,

For the other inequality, consider any supermartingale M ∈ M ϕ such that lim inf M ≥ f .

We derive from Equation (4) and C1 that M(s) ≥ min{M(s0), M(s1)} for all s ∈ S. This implies that there is some path ϖ ∈ Ω such that M( ) ≥ M(ϖ 1:n ) for all n ∈ N 0 , 11 and therefore also that M( ) ≥ lim inf M(ϖ) ≥ f (ϖ) ≥ inf f . Equation (7) In particular, we find for f = 0 that E ϕ (0) = E ϕ (0) = 0.

E3. We prove the third and fourth inequalities; the remaining inequalities will then follow from conjugacy. For the fourth inequality, we consider any real α and β such that α > E ϕ ( f ) and β > E ϕ (g). Then it follows from Equation (7) that there are supermartingales M 1 , M 2 ∈ M ϕ such that lim inf M 1 ≥ f , lim inf M 2 ≥ g, α > M 1 ( ) and β > M 2 ( ).

But then M := M 1 + M 2 is a supermartingale for ϕ with lim inf M = lim inf(M 1 + M 2 ) ≥ lim inf M 1 + lim inf M 2 ≥ f + g, and we therefore infer from Equation (7) that

Since this inequality holds for all real α > E ϕ ( f ) and β > E ϕ (g), and since we have proved above that upper expectations of gambles are real-valued, we find that, indeed,

For the third inequality, observe that g = ( f + g) − f , so we infer from the inequality we have just proved that

whence, indeed, E ϕ ( f + g) ≥ E ϕ ( f ) + E ϕ (g), since we have already proved above that lower and upper expectations are real-valued. E2. We prove the second equality; the first equality then follows from conjugacy. It follows from Equation (47) that we may assume without loss of generality that λ > 0. The desired equality now follows at once from Equation (7) E1. It is only left to prove that E ϕ ( f ) ≤ E ϕ ( f ). Since f − f = 0, we infer from E3 and Equation (47) 

The desired inequality now follows from the fact that lower and upper expectations are real-valued, as proved above.

E4. We prove the first equality; the second will then follow from conjugacy. Infer from E1 that E ϕ (µ) = E ϕ (µ) = µ, and then E3 indeed leads to

E5. We prove the first implication; the second will then follow from conjugacy. Assume that f ≤ g, then inf(g − f ) ≥ 0, so we infer from E1 and E3 that, indeed,

The desired inequality now follows from the fact that lower and upper expectations are real-valued, as proved above.

Proof of Proposition 3. The 'if' part is immediate when we let e(s, N) := N for all s ∈ S and N ∈ N 0 , so we proceed to the 'only if' part. That F is computable means that there is some recursive net of rational numbers r ′ s,n and some recursive map e : S × N 0 → N 0 such that n ≥ e(s, N) implies that |r ′ s,n − F(s)| ≤ 2 −N for all s ∈ S and N ∈ N 0 . The net of rational numbers defined by r s,n := r ′ s,e(s,n) for all s ∈ S and n ∈ N 0 is recursive because the function e is recursive, and it indeed satisfies |r s,n − F(s)| = |r ′ s,e(s,n) − F(s)| ≤ 2 −n for all s ∈ S and n ∈ N 0 .

Proof of Proposition 4. We begin with the 'if' part. Assume that F is both lower and upper semicomputable. This implies that there are two recursive nets of rational numbers r s,n and r s,n such that r t,n ր F(t) and r t,n ց F(t) for any fixed t ∈ S. Consider the recursive nets of rational numbers defined by δ s,n := r s,n − r s,n ≥ 0 and r s,n := (r s,n + r s,n )/2. For any fixed t ∈ S, the sequence δ t,n ց 0, which implies that for any N ∈ N 0 there is some natural number e(t, N) such that δ t,n ≤ 2 −N for all n ≥ e(t, N). Clearly, the map e : S × N 0 → N 0 can be defined recursively, and we see that n ≥ e(s, N) also implies that |F(s) − r s,n | ≤ |r s,n − r s,n | = δ s,n ≤ 2 −N , for all s ∈ S and n, N ∈ N 0 . Hence, the real process F is also computable.

We continue with the 'only if' part. Assume that F is computable, so there is a recursive net of rational numbers r s,n and a recursive map e : S × N 0 → N 0 such that n ≥ e(s, N) implies that |r s,n − F(s)| ≤ 2 −N for all s ∈ S and n, N ∈ N 0 . We prove that F is lower semicomputable; the proof that F is upper semicomputable is completely similar. Consider the recursive net of rational numbers defined by r ′ s,n := r s,e(s,n+2) − 3 · 2 −(n+2) for all s ∈ S and n ∈ N 0 . Then we know that |r ′ s,n + 3 · 2 −(n+2) − F(s)| ≤ 2 −(n+2) and therefore also

for all s ∈ S and n ∈ N 0 , which then tells us that r ′ s,n ≤ F(s) − 2 −(n+1) ≤ r ′ s,n+1 and that |r ′ s,n − F(s)| ≤ 2 −n , again for all s ∈ S and n ∈ N 0 . 12 Hence, we find for the recursive net of rational numbers r ′ s,n that r ′ s,n ր F(s) for all s ∈ S, which implies that F is indeed lower semicomputable.

Proof of Proposition 5. Obviously, the constant real processes γ I (s) := p and γ I (s) := p are computable if and only if their constant values p and p are. 12 Note that this implies that we can always assume without loss of generality from the outset for our original net r s,n that it is non-decreasing as a function of n, that r s,n < F(s) and that e(s,n) = n for all s ∈ S and n ∈ N 0 .

Proof of Proposition 6. We only prove the third statement. The proof for the first and second statements are similar to the proof of the 'if' part of the third one, but simpler. There are a number of ways to prove the third statement, but we will use Proposition 3.

For the 'if' part, we assume that F( ) and ∆F are computable. Proposition 3 then implies that there are a recursive sequence of rational numbers r ,n and two recursive nets of rational numbers r x s,n such that |F( ) − r ,n | ≤ 2 −n and |∆F(s)(x) − r x s,n | ≤ 2 −n for all s ∈ S, n ∈ N 0 and x ∈ {0, 1}. We now define the recursive net of rational numbers r s,n as follows: for any s ∈ S and any n ∈ N 0 , let r s,n := r ,n + |s| ∑ k=1 r s k s 1:k−1 ,n .

Then, since also then n ≥ e(s, N) implies that |F(s) − r s,n | ≤ 2 −N for all s ∈ S and n ∈ N 0 . Hence, F is computable. For the 'only if' part, assume that F is computable. Then definitely in particular also its value F( ) in the initial situation is computable, so it only remains to prove that the process difference ∆F is computable. Consider, to this effect, any x ∈ {0, 1}. It follows from the computability of F and Proposition 3 that there is some recursive net of rational numbers r ′ s,n such that |F(s) − r ′ s,n | ≤ 2 −n and |F(sx) − r ′ sx,n | ≤ 2 −n and therefore also r ′ sx,n − r ′ s,n − 2 −(n−1) ≤ F(sx) − F(s) ≤ r ′ sx,n − r ′ s,n + 2 −(n−1) for all s ∈ S and n ∈ N 0 . If we now let r x s,n := r ′ sx,n+1 − r ′ s,n+1 , then this defines a recursive net of rational numbers r x s,n that satisfies |∆F(s)(x) − r x s,n | ≤ 2 −n for all s ∈ S and all n ∈ N 0 . Hence, the real process ∆F(·)(x) is computable by Proposition 3, and so is, therefore, the process difference ∆F.

Proof of Proposition 7. We only give the proof for the first statement. The proof for the second statement is similar but simpler, and the third statement then follows readily from the first and the second, and Propositions 4 and 6.

Assume that the multiplier process D is lower semicomputable. This implies that there are two recursive nets of rational numbers r x s,n such that r x s,n ր D(s)(x), for x ∈ {0, 1}. Since D(s)(x) ≥ 0, we may assume without loss of generality that r x s,n ≥ 0 too [otherwise replace this recursive net of rational numbers with the recursive net of rational numbers max{0, r x s,n }]. We now construct a recursive net of rational numbers r s,n as follows: for any s ∈ S and for any n ∈ N 0 , we let r s,n := ∏ |s|−1 k=0 r s k+1 s 1:k ,n . Then, since also D ⊚ (s) = ∏ m−1 k=0 D(s 1:k )(s k+1 ) and r s k+1 s 1:k ,n ր D(s 1:k )(s k+1 ) for all k ∈ {0, 1, . . . , |s| − 1}, we find that r s,n ր D ⊚ (s) for all s ∈ S, so D ⊚ is indeed lower semicomputable.

Proof of Proposition 8. Since D ⊚ is positive, it follows trivially that D is positive as well. Consider now any x ∈ {0, 1}. Since D ⊚ is computable, it follows from Proposition 6 that ∆D ⊚ is computable, and therefore, we know that ∆D ⊚ (s)(x) is computable as well. Hence, since D ⊚ is computable and positive, and we find that the real process D(s)(x), s ∈ S is computable, and so is therefore D.

For the second statement, consider any positive computable real process F, and let D(s)(x) := F(sx) F(s) > 0 for all s ∈ S and x ∈ {0, 1}, then D is clearly a positive multiplier process with D ⊚ = F/F( ). This implies that D ⊚ is computable. The first part of the proposition now implies that D is computable.

Proof of Proposition 12. We prove that (i)⇒(ii)⇒(iii)⇒(i).

(i)⇒(ii). Trivial, because for any growth function ρ, the map τ := ρ is a real growth function.

(ii)⇒(iii). Fix any r ∈ N. Because the real growth function τ is non-decreasing and unbounded, there is some m r ∈ N 0 such that τ(m) > 2 /r for all natural m ≥ m r . For any such m ≥ m r , it follows from the assumption that there is some natural n r,m ≥ m for which µ(n r,m ) > τ(n r,m ) − 1 /r, and therefore, since also τ(n r,m ) ≥ τ(m) > 2 /r, µ(n r,m ) τ(n r,m ) > 1 − 1 rτ(n r,m ) > 1 2 .

Randomness in computability theory. Contemporary Mathematics

Introduction to Imprecise Probabilities

Failure of calibration is typical

On the history of martingales in the study of randomness

Probability and Measure

On the concept of a random sequence

The well-calibrated Bayesian

Statistical theory: The prequential approach

Calibration-based empirical probability

Self-calibrating priors do not exist: Comment

Prequential probability: principles and properties

Sum-product laws and efficient algorithms for imprecise Markov chains

Imprecise probability trees: Bridging two theories of imprecise probability

Imprecise Markov chains and their limit behaviour

A pointwise ergodic theorem for imprecise Markov chains

Imprecise stochastic processes in discrete time: global models, imprecise Markov chains, and ergodic theorems

Upper and lower probabilities induced by a multivalued mapping

Algorithmic Randomness and Complexity

An extension of chaotic probability models to real-valued variables

A frequentist understanding of sets of measures

On the apparent convergence of relative frequency and its implications

The Statistical Stability Phenomenon

Three approaches to the quantitative definition of information

The Axioms and Algebra of Intuitive Probability

Imprecise continuous-time Markov chains

Higher order probabilities and intervals

The Enterprise of Knowledge

On the notion of a random sequence

An Introduction to Kolmogorov Complexity and Its Applications

The definition of random sequences

Mathematical metaphysics of randomness

Self-calibrating priors do not exist

Computable randomness is about more than probabilities

A remarkable equivalence between non-stationary precise and stationary imprecise uncertainty models in computable randomness

Computability in Analysis and Physics

Introduction to imprecise probabilities. Chapter Desirability

Calibration-based empirical probability -discussion

Self-calibrating priors do not exist: Comment

Zufälligkeit und Wahrscheinlichkeit: Eine algorithmische Begründung der Wahrscheinlichkeitstheorie

Process complexity and effective random tests

A representation of partially ordered preferences

Rethinking the Foundations of Statistics

A Mathematical Theory of Evidence

Non-additive probabilities in work of Bernoulli and Lambert. Archive for History of Exact Sciences

Probability and Finance: It's Only a Game!

Game-Theoretic Foundations for Probability and Finance

Lévy's zero-one law in game-theoretic probability

Global upper expectations for discrete-time stochastic processes: In practice, they are all the same! Accepted for publication in the proceedings of ISIPTA

Continuity properties of gametheoretic upper expectations

In search of a global belief model for discrete-time uncertain processes

A recursive algorithm for computing inferences in imprecise Markov chains

A particular upper expectation as global belief model for discrete-time finite-state uncertain processes

Étude critique de la notion de collectif

Game-theoretic probability

On a criterion of randomness

Merging of opinions in game-theoretic probability

Prequential randomness and probability

Statistical Reasoning with Imprecise Probabilities

Towards a frequentist theory of upper and lower probability

Randomness and Complexity

This paper has taken a very long time to write. Our research on this topic started with discussions between Gert and Philip Dawid about what prequential interval forecasting would look like, during a joint stay at Durham University in late 2014. Gert, and Jasper who joined in late 2015, wrote an early prequential version of the present paper during a joint research visit to the University of Strathclyde and Durham University in May 2016, trying to extend the results in Refs. [57] [58] [59] to make them allow for interval forecasts. In an email exchange, Volodya Vovk pointed out a number of difficulties with our approach, which we were able to resolve by letting go of its prequential emphasis, at least for the time being. This was done during research visits of Gert to Jasper at IDSIA in Lugano in late 2016 and early 2017. This paper then lay dormant for a while, while Gert took up a position as director of studies between 2016 and 2019, and both of us were more strongly focused on issues dealing with coherent choice functions. We finished the conceptual work on this paper during a joint research stay in Siracusa in January 2020, and wrote it all down later at home during successive Covid-19 lockdowns, in the spring of 2020, and the early months of 2021.

This implies that, indeed, lim sup n→∞ µ(n) /τ(n) > 0.(iii)⇒(i). We begin by showing that there is some real growth function τ ′ such that lim sup n→∞ [µ(n) − τ ′ (n)] > 0. It follows from the assumption that there is some r ∈ N such that lim sup n→∞ µ(n) /τ(n) > 1 /r, and also that there is some n o ∈ N 0 such that τ(n) > 0 for all n ≥ n o . If we now let τ ′ := τ /2r for all n ∈ N 0 , then it is clear that τ ′ is a real growth function, and that lim sup n→∞ µ(n) /τ ′ (n) > 2. This implies that for all n ∈ N 0 with n ≥ n o , there is some m n ≥ n in N 0 such that µ(m n ) /τ ′ (m n ) > 2, and therefore alsoThis implies that, indeed, lim sup n→∞ [µ(n) − τ ′ (n)] ≥ τ ′ (n o ) > 0. Because τ ′ is computable, we know from Proposition 3 [after identifying the countably infinite sets S and N 0 ] that there is some recursive net of rational numbers r ′ k,n such that |r ′ k,n − τ ′ (k)| ≤ 2 −n for all k, n ∈ N 0 .If we now define the sequence of rational numbers r k := r ′ k,k+1 − 3 · 2 −k , then this sequence is clearly a recursive sequence of rational numbers for whichHence alsowhere the strict inequalities follow from Equation (48), and the weak inequality from the non-decreasing character of the real growth function τ ′ . This tells us that the sequence r k is increasing. Equation (48) tells us that it is also unbounded, because τ ′ is. If we therefore define the map ρ ′ : N 0 → Z by letting ρ ′ (k) := ⌊r k ⌋ for all k ∈ N 0 , then this map is recursive because r k is a recursive sequence of rational numbers, non-decreasing because the sequence r k is increasing, and unbounded because the sequence r k is. Sincewhere we have used Equation (48), we find thatand therefore lim sup n→∞ [µ(n) − ρ ′ (n)] ≥ lim sup n→∞ [µ(n) − τ ′ (n)] > 0. The same inequality of course also holds if we replace ρ ′ by the growth function ρ := max{0, ρ ′ }.Proof of Proposition 13. Consider any real R > 0. Since µ is computably unbounded, there is some growth function ρ such that Equation (14) holds. Since ρ is unbounded, there is some m R ∈ N 0 such that ρ(m R ) > R, and then Equation (14) implies that there is some natural n R ≥ m R such that µ(n R ) > ρ(n R ) ≥ ρ(m R ) > R [the weak inequality follows from the non-decreasing character of the growth function ρ]. Hence, µ is unbounded above.Proof of Proposition 14. Assume ex absurdo that both µ 1 and µ 2 are not computably unbounded. That the product µ 1 µ 2 is computably unbounded implies, by Proposition 12(iii), that there is some real growth function τ and some natural number r > 0 such thatIf we consider the real growth functions τ 1 and τ 2 defined by τ 1 (n) = τ 2 (n) := τ(n) for all n ∈ N 0 , then clearly τ(n) = τ 1 (n)τ 2 (n) for all n ∈ N 0 , and therefore Equation (49) guarantees thatBut the assumption that µ 1 and µ 2 are not computably unbounded, in combination with Proposition 12(iii), guarantees in particular that there are m 1 , m 2 ∈ N 0 such that