Algorithmic Randomness, Effective Disintegrations, and Rates of Convergence to the Truth

The computable Polish spaces with computable probability measures are such an appropriately general class of spaces and measures. In this brief section we collect together the few definitions we need about their theory. The reader already familiar with these concepts can easily skip to the next section (§1.2).

A Polish space is a topological space which is separable and completely metrizable. All the paradigmatic spaces such as the reals and their products and their closed and open subspaces are Polish, and similarly for Cantor space. Descriptive set theory takes as its subject matter the Borel and projective subsets of Polish spaces.¹¹¹¹11[34], [48]. When topological considerations are salient or when one needs i.i.d. sequences with prescribed distributions, it is often assumed in contemporary probability theory that the sample space is a Polish space or a Borel subset thereof.¹²¹²12A Borel subset of a Polish space together with its Borel subsets is known as a standard Borel space in descriptive set theory (cf. §[34, Definition 12.5, Corollary 13.4]). For representative examples of standard Borel spaces within probability, see e.g. [17, p. 51], [33, p. 7, pp. 561 ff]. For a classic probability text that foregrounds standard Borel spaces, see [51, Chapter 1].

A computable Polish space $X$ is a Polish space with a distinguished countable dense set $x_{0},x_{1},\ldots$ and a distinguished complete compatible metric $d$ such that the distance $d(x_{i},x_{j})$ between any two elements of the countable dense set is a computable real, uniformly in $i,j\geq 0$.¹³¹³13A standard reference for computable Polish spaces is [48, Chapter 3]. A comparison to the Weihrauch approach to computable analysis is given in [24]. One can view the treatment of metric spaces in [70] as an axiomatization of Polish spaces and reals which are computable in an oracle. Finally, the study of computable Polish spaces in and of themselves is distinct from effective descriptive set theory, which usually refers to techniques for proving results about all Borel sets by first proving it for lightface Borel sets in Baire space (the most famous example of this is the Glimm-Effros dichotomy (cf. [23, Chapter 6])). (The enumeration of the distinguished countable dense set can contain repetitions, and will need to do so in finite spaces.)

In a computable Polish space, an open set $U$ is c.e. open if there is a computable function $n(\cdot)$ which enumerates a subsequence $x_{n(i)}$ of the countable dense set and a computable sequence $r_{i}$ of rational radii such that $U=\bigcup_{i}B_{d}(x_{n(i)},r_{i})$. In this, $B_{d}(x,r)$ denotes the open ball with centre $x$ and radius $r$ relative to metric $d$ (when the metric $d$ is clear from context, we just write $B(x,r)$). The name “c.e. open” is chosen since the natural numbers are a computable Polish space with the discrete metric, and the c.e. opens in this space are precisely the computably enumerable sets of natural numbers, one of the canonical objects of the contemporary theory of computation.¹⁴¹⁴14See [71], a standard reference. Further, many of the elementary methods of studying c.e. sets (e.g., universal enumerations) extend to c.e. open sets. The complements of c.e. open sets are called effectively closed sets (cf. §2.1).

In a computable Polish space, we say that a sequence $x_{n}\rightarrow x$ at geometric rate $b$ if $d(x,x_{n})\leq b^{-n}$ for all $n\geq 0$. We say that a sequence $x_{n}\rightarrow x$ fast if $x_{n}\rightarrow x$ at geometric rate $b=2$. We then say that a point $x$ is computable if there is a computable function $n(\cdot)$ which enumerates a subsequence $x_{n(i)}$ of the countable dense set such that $x_{n(i)}\rightarrow x$ fast. This subsequence is called a witness to the computability of $x$. In Cantor space with its usual metric, the computable points are precisely the computable subsets of natural numbers.

In the real numbers, the countable dense set is the rationals, and the above definition of computable points is precisely how Turing defined computable real numbers at the outset of the theory of computation nearly a century ago.¹⁵¹⁵15[72]. An equivalent formalisation of computable reals is by Dedekind cuts. A real $x$ is left-c.e. (resp. right-c.e.) if its left Dedekind cut $\{q\in\mathbb{Q}:q<x\}$ in the rationals is a c.e. set (resp. if its right Dedekind cut $\{q\in\mathbb{Q}:x<q\}$ in the rationals is a c.e. set). One can show that a real is computable iff it is both left-c.e. and right-c.e., and uniformly so. (An example of a left-c.e. real that is not computable is $\sum_{n}2^{-f(n)}$, where $f:\mathbb{N}\rightarrow\mathbb{N}$ is an injective computable function with non-computable range.)¹⁶¹⁶16These and other effective aspects of real numbers are treated extensively in e.g. [57], [15, Chapter 5].

These preliminaries in place, one can then quickly define the required core notions from algorithmic randomness and effective probability. These are all needed in order to formally state our main theorems, but one might restrict oneself to (1)-(8) on a first pass and come back to the others as needed.

For the algorithmic randomness notions in (6)-(8), we just write $\mathsf{KR}^{\nu}$ instead of $\mathsf{KR}^{\nu}(X)$ when $X$ is clear from context; and similarly for $\mathsf{SR}^{\nu}$ and $\mathsf{MLR}^{\nu}$. For $\sigma$-algebras $\mathscr{F}$, it is always understood that they are sub-$\sigma$-algebras of the Borel $\sigma$-algebra, and when $\nu$ is clear from context we just say effective instead of $\nu$-effective.

Algorithmic randomness is often formulated in terms of effective null sets, called sequential tests. But the definitions given above in terms of integral tests are easier to work with in our setting and are known to be equivalent to the sequential definitions, by theorems of Levin and Miyabe.²¹²¹21[37], [45, Theorem 3.5].

Before turning to disintegrations, it is helpful to introduce notational conventions regarding versions of integrable functions vs. equivalence classes thereof. In the following definition, the $\sigma$-algebra on $[-\infty,\infty]$ is simply $\{B\cup C:B\subseteq\mathbb{R}\mbox{ Borel},C\subseteq\{-\infty,\infty\}\}$, and similarly for $[0,\infty]$.

Then $\mathbb{L}_{p}(\nu)$ projects onto $L_{p}(\nu)$ by sending a function to its equivalence class, and likewise $\mathbb{L}^{+}_{p}(\nu)$ projects onto $L^{+}_{p}(\nu)$. Note that $L_{p}(\nu)$ Schnorr tests and Martin-Löf tests from Definition 1.1(4)-(5) are elements of $\mathbb{L}_{p}^{+}(\nu)$, and they are elements of $L_{p}^{+}(\nu)$ only after passing to the equivalence class.

We use disintegrations for the versions $\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}]$ of conditional expectation. While, classically, conditional expectation is defined only $\nu$-a.s., in order to characterise algorithmic randomness notions in terms of Lévy’s Upward Theorem, we need to select specific versions of conditional expectation. The concept of a disintegration provides a very general way of making such selections. It is due to Rohlin²²²²22[58], [59], [60]. and is routinely used today in ergodic theory and optimal transport,²³²³23It is often used in the proof of the Ergodic Decomposition Theorem and the Gluing Lemma. See [19, 154], [63, 182]. and it is closely related to conditional probability distributions.²⁴²⁴24[11], [53, §5.3].

Suppose that $X$ is a Polish space, $\nu$ is a probability measure on the Borel sets of $X$ and $\mathscr{F}$ is a countably generated sub-$\sigma$-algebra of the Borel $\sigma$-algebra. Define the equivalence relation $\sim_{\mathscr{F}}$ on $X$ by $x\sim_{\mathscr{F}}x^{\prime}$ iff, for all $A$ in $\mathscr{F}$, one has $x$ in $A$ iff $x^{\prime}$ in $A$, and let $[x]_{\mathscr{F}}$ be the corresponding equivalence class.²⁵²⁵25Since we are focused on Lévy’s Upward Theorem, we are focusing on countably generated sub-$\sigma$-algebras $\mathscr{F}$ of the Borel $\sigma$-algebra. Note that this has the consequence that the relation $\sim_{\mathscr{F}}$ is a smooth Borel equivalence relation (cf. [23, §5.4]). More complicated Borel equivalence relations occur naturally in nearby topics. For instance, Rute examines Lévy’s Downward Theorem (cf. [61, Theorem 11.2], [75, Theorem 14.4]), which in Cantor space results naturally in the sub-$\sigma$-algebra of $E_{0}$-invariant events, where $E_{0}$ is the Borel equivalence relation featuring in the Glimm-Effros dichotomy (cf. [23, Definition 6.1.1]).

Let $\mathcal{M}^{+}(X)$ be the Polish space of non-negative Borel measures on $X$ (cf. §2.2). For Borel measurable $\rho:X\rightarrow\mathcal{M}^{+}(X)$, whose action is written as $x\mapsto\rho_{x}$, we define the partial map

This map is a version, that is, it is partially defined on all pairs $(f,x)$. Note that it is totally defined on $\mathbb{L}_{1}^{+}(\nu)\times X$, with range $[0,\infty]$,²⁶²⁶26Indeed, it is totally defined on all pairs ($f,x)$ where $f$ is non-negative Borel measurable. But for our purpose of defining a version of $\mathbb{E}_{\nu}[\cdot\mid\mathscr{F}]$ we only need to pay attention to when $f$ is in $\mathbb{L}_{1}(\nu)$. and it is totally defined and finite on all simple functions. It is further helpful to keep in mind that whether $\mathbb{E}_{\nu}[f\mid\mathscr{F}](x)$ is finite depends on whether the element $f$ of $\mathbb{L}_{1}(\nu)$ is additionally in $\mathbb{L}_{1}(\rho_{x})$: that is, it is integrability with respect to $\rho_{x}$ rather than $\nu$ which is at issue.

For a Polish space $X$, one says that a map $\rho:X\rightarrow\mathcal{M}^{+}(X)$ is the disintegration of $\mathscr{F}$ with respect to $\nu$ if both the following happen:²⁷²⁷27We are following the treatment of Einsiedler-Ward [19, 135]. Since the main examples of disintegrations involve products (cf. Appendicies A-B), often alternative definitions of disintegrations involve maps that axiomatize the role that the projection operators play in the paradigmatic examples. For an example of definitions along these lines, see [11], [53, §5.3].

• –

  for all $f$ in $\mathbb{L}_{1}(\nu)$, one has that $\mathbb{E}_{\nu}[f\mid\mathscr{F}]$ is a version of the conditional expectation of $f$ with respect to $\mathscr{F}$ and $\nu$.²⁸²⁸28Hence it is in $\mathbb{L}_{1}(\nu)$, and thus it is defined and finite for $\nu$-a.s. many $x$ from $X$.

• –

  For $\nu$-a.s. many $x$ from $X$, one has $\rho_{x}(X)=1$ and $\rho_{x}([x]_{\mathscr{F}})=1$.

A disintegration of $\mathscr{F}$ with respect to $\nu$ exists for any countably generated sub-$\sigma$-algebra $\mathscr{F}$ of the Borel $\sigma$-algebra on $X$.²⁹²⁹29[19, 135]. Indeed, a little more is true: one can replace $X$ by one of its Borel subsets. Further, one can relax the assumption that $\mathscr{F}$ is countably generated, provided that one does not insist on $\rho_{x}([x]_{\mathscr{F}})=1$. Further, it is possible to be more agnostic about the codomain of $\rho$ outside the $\nu$-measure one set on which it outputs probability measures. See Appendix A for two classical examples of disintegrations.

Here is our key definition of effective disintegration:

Technically, it appears possible to, e.g., be a $\mathsf{SR}^{\nu}$ disintegration but not a $\mathsf{KR}^{\nu}$ disintegration. This is due to the universal quantifier over $\mathsf{XR}^{\nu}$ at the outset of (2). But this possibility does not appear to occur naturally among examples.

Due to space constraints, we have opted to focus on theory in the body of the text, and have put a brief discussion of the many interesting examples of effective disintegrations in Appendix B.

Finally, we can define:

In this, $\delta_{x}$ is the Dirac measure centred at $x$. With the limit written as such, by the Portmanteau Theorem one sees that it is a strengthening of the weak convergence of the measures $\rho_{x}^{(n)}\rightarrow\delta_{x}$. Since we use the disintegration to define the conditional expectation, as in equation (1.1) above, the limit in Definition 1.4 can be written equivalently as $\lim_{n}\mathbb{E}_{\nu}[I_{U}\mid\mathscr{F}_{n}](x)=I_{U}(x)$. With respect to the canonical filtration of length $n$-strings on Cantor space and its natural disintegration (cf. Example B.1), density randomness has been a focal topic in recent literature on algorithmic randomness.³⁰³⁰30[3], [47], [35]. In this setting with $\nu$ being the uniform measure, it is known that $\mathsf{DR}^{\nu}_{\rho}$ is a proper subset of $\mathsf{MLR}^{\nu}$. One example which shows this properness is an element $\omega$ of $\mathsf{MLR}^{\nu}$ such that $\{\omega^{\prime}:\omega^{\prime}<_{lex}\omega\}$ is c.e. open, where $<_{lex}$ is the lexicographic order. Definition 1.4 is our suggestion for how to generalise this to the setting of arbitrary effective disintegrations.

Our first main theorem is the following:

In condition (2), $\lim_{n}\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}](x)=f(x)$ means that the limit of $\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}](x)$ exists and is finite and equal to $f(x)$. Likewise in (3)-(4), the existence of the limit means that it is finite. Note that (3) implies that $\mathsf{SR}^{\nu}$ already proves the analogue of density randomness where we restrict to c.e. open $U$ with $0<\nu(U)<1$ computable.

For rates of convergence, we have:

The notion in Theorem 1.6(2) is a classical notion from the theory of computation: a Turing degree is computably dominated if any function from natural numbers to natural numbers that is computable from the degree is dominated by a computable function, in the sense that the computable function is eventually above it.³¹³¹31[71, 124], [50, 27]. A more traditional name for this concept is “of hyperimmune-free degree.” This more traditional name comes from an equivalent definition that emerged in the context of Post’s Problem (cf. [71, 133 ff]). For many but not all computable Polish spaces $X$ and $\nu$ in $\mathcal{P}(X)$ computable, there are non-atoms in $\mathsf{MLR}^{\nu}$ (and hence in $\mathsf{SR}^{\nu}$) of computably dominated degree. This is a consequence of the existence of universal tests for $\mathsf{MLR}^{\nu}$ and the Computably Dominated Basis Theorem (cf. discussion at Proposition 2.18, Example 2.19, Question  2.20).

It is unknown to us whether Theorem 1.6(2) can be improved, in the sense of an affirmative answer to the following question:

We prove Theorems 1.5-1.6 in §8. Theorem 1.5 extends and unifies prior work by Pathak, Rojas, and Simpson, and of Rute (see discussion in §1.4 below), while Theorem-1.6 is entirely new.

Our next theorem pertains to convergence along Martin-Löf tests:

In contrast to Theorem 1.6(2), one has the following, whose proof is a traditional diagonalization argument deploying the halting set:

We prove Theorems 1.8-1.9 in §9. Theorem 1.8 extends work from a paper of Miyabe, Nies, and Zhang, which we discuss in the next section, while Theorem 1.9 is entirely new.

Given Theorem 1.5 and Theorem 1.8, it is natural to try to understand whether there is a convergence to the truth characterisation of $\mathsf{MLR}^{\nu}$, or at least some nearby superset of it (by contrast, $\mathsf{DR}^{\nu}_{\rho}$ is a subset of $\mathsf{MLR}^{\nu}$). We thus isolate a class of Martin-Löf tests $f$ which have approximations $f_{s}$ such that $f_{s}\rightarrow f$ in $L_{p}(\nu)$ at an exponential rate, but not a rate that can necessarily be computed. Hence we define the following, where clauses (1)-(3) mimic the canonical approximations of $L_{p}(\nu)$ Schnorr tests (cf. Proposition 2.16, Lemma 3.2), and where clause (4) pertains to exponential rates:

Our theorem on this is the following:

We prove Theorem 1.11 in §10. The name “Maximal Doob” in Theorem 1.11 and Definition 1.10 comes from the role played by Doob’s Maximal Inequality (cf. Lemma 5.1(1)) in the proofs in §10. In Proposition 10.1, we note that $\mathsf{MLR}^{\nu}\subseteq\mathsf{MDR}^{\nu,p}\subseteq\mathsf{SR}^{\nu}$. But we do not know the answer to the following question:

We add that we do not know the answer to the following:

Theorem 1.5 generalises the result of Pathak, Rojas, and Simpson, who show it for the specific case of $p=1$ and $X=[0,1]^{k}$, $\nu$ being the $k$-fold product of Lebesgue measure on $[0,1]$ with itself, and with $\mathscr{F}_{n}$ being given by dyadic partitions.³⁵³⁵35[52]. They state their result not in terms of $L_{p}(\nu)$ Schnorr tests, but in terms of computable points of $L_{p}(\nu)$. See §11. Under this guise, Lévy’s Upward Theorem just is the Lebesgue Differentiation Theorem. Their proof goes through Tarski’s decidability results on the first-order theory of the reals, and so seems in certain key steps specific to the reals with Lebesgue measure.³⁶³⁶36Such as at [52, Lemma 3.3 p. 339]. However, see Proposition 4.1 below, which generalises rather directly from their setting to the general setting.

In conjunction with the properties of effective disintegrations (cf. §7), one can derive the equivalence of (1)-(2) in Theorem 1.5 from results of Rute.³⁷³⁷37In particular, for the (1) to (2) direction of Theorem 1.5, see Rute’s “Effective Levy 0/1 law” [61, Theorem 6.3 p. 31]. Our Proposition 7.5 and Proposition 2.4 implies that if $f$ is an $L_{1}(\nu)$ Schnorr test, then $\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}]$ is a computable point of $L_{1}(\nu)$, and so Rute’s Theorem 6.3 applies, once one internalises how to translate back and forth between $L_{p}(\nu)$ Schnorr tests and computable points of $L_{p}(\nu)$ (cf. §11). For the (2) to (1) direction of Theorem 1.5, see Rute’s [61, Example 12.1 p. 31]. As for Schnorr randomness, our work then expands on Rute’s primarily by finding a large class of versions of conditional expectations to which his results apply, and by identifying the information on rates of convergence in Theorem 1.6. More generally, the theory we develop is organised around the elementary concept of an integral Schnorr test, and so we hope might be of value to others by virtue of being accessible.³⁸³⁸38In particular, we can avoid appeal to Rute’s theory of a.e. convergence, which is an alternative way to organise effective convergence in $L_{0}(\nu)$ (cf. §2.4). See [61, Proposition 3.15 p. 15] and his Convergence Lemma [61, Lemma 3.19 p. 17].

Further, we are able to strengthen what is, in our view, one of the more foundationally significant parts of Rute’s work. He notes that traditionally “algorithmic randomness is more concerned with success than convergence” and that “only computable randomness has a well-known characterisation in terms of martingale convergence instead of martingale success.”³⁹³⁹39[61, p. 7]. He is referring to what is called a “folklore” characterisation of computable randomness on Cantor space with the uniform measure in [15, Theorem 7.1.3 p. 270]. In Cantor space with the uniform measure, Rute has a characterisation of Schnorr randomness in terms of convergence of $L_{2}(\nu)$ martingales.⁴⁰⁴⁰40See items (1), (4) in his Example 1.5, immediately below the preceding quotation. We have been able to generalise this to all computable measures on computable Polish spaces: see Theorem 12.2. This proof follows Rute’s $L_{2}(\nu)$ Hilbert space proof in broad outline. It seems to us that keeping track of the maximal function, which we can then use in DCT arguments, has been helpful here.

In the setting of Cantor space with the uniform measure and the natural filtration of length $n$-strings and the natural disintegration (cf. Example B.1), our Theorem 1.8 was already known for $p=1$ and hence all computable $p\geq 1$. This result is in a paper of Miyabe, Nies, and Zhang, where it is attributed to the Madison group of Andrews, Cai, Diamondstone, Lempp and Miller.⁴¹⁴¹41[47, Theorem 3.3 p. 312]. Their proof is a little more general, in that it just concerns martingale convergence rather than martingales associated to random variables. Their proof, in the Cantor space setting, also can be modified to give not only convergence but convergence to the truth for random variables. Their argument goes through an auxiliary test notion of Madison test. While we only have it for computable $p>1$, our proof of Theorem 1.8 goes through first principles about density randomness and effective disintegrations. It is not presently clear to us whether the Cantor space proof using Madison tests can be generalised to arbitrary computable probability measures on computable Polish spaces equipped with effective disintegrations.⁴²⁴²42As a final remark about the previous literature, we should mention that Lévy’s Upward Theorem has also been studied in the context of Shafer and Vovk’s game-theoretic probability ([67], [66, Chapter 8]). Their approach conceives of martingales primarily as game-theoretic strategies, and does not treat computational matters explicitly. By contrast, here we are focusing on the martingales $\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}]$ and on effective properties of them conceived of as sequences of random variables. Discerning the relation between our approach and their approach would involve, as a first step, carefully going through their approach and ascertaining the exact levels of effectivity needed to secure their results, and secondly translating back and forth between the strategy and random variable paradigms.

We hope our efforts brings this prior important work on algorithmic randomness to the attention of a broader audience. Bayesianism is an important and increasingly dominant framework in a variety of disciplines, and this prior work and our work hopefully makes vivid the way in which computability theory and algorithmic randomness bears directly on the question of when and how fast Bayesian inductive methods converge to the truth. As its proof makes clear, the non-computable rate of convergence to the truth in Theorem 1.9 is another presentation of the halting set, and so this proof gives the theory of computation a central role in a limitative theorem of inductive inference, similar to its central role in the great limitative theorems of deductive inference like the Incompleteness Theorems. Further, the existence of Schnorr random worlds that are computably dominated, as in Theorem 1.6(2), shows that a central kind of randomness is entirely compatible with there being effective ways of determining how close we are to the truth. This optimistic inductive possibility is not one that would be visible in absence of recent work in algorithmic randomness.

Internal to the discussion about Bayesianism within philosophy, authors such as Belot have voiced the concern that the classical theory only tells us that worlds at which we fail to converge to the truth have probability zero, but otherwise tells us little about when and where the failure happens.⁴³⁴³43[2]. From the perspective of Theorems 1.5, 1.8, 1.11, the probability zero event of non-convergence is not arbitrary, so long as one is insisting on convergence along a broad enough class of effective random variables. Namely, the sequences along which convergence to the truth fails for some element of this class are exactly those that are not random with respect to the underlying computable prior probability measure. In other words, those sequences can be determined by effective means to be atypical from the agent’s point of view.

Finally, we should emphasise that ours is not the only perspective on conditional expectations and its effectivity that one could adopt. In focusing on disintegrations, we are presupposing a framework where pointwise there is a single “formula” for the conditional expectation, namely the one displayed in equation (1.1) (and again see Appendicies A-B for examples). Likewise, the effectivity constraints in Definition 1.3 have the consequence that the conditional expectation operator is a continuous computable function (cf. Proposition 7.5), and so sends computable points to computable points (cf. Proposition 2.4). Both of these presuppositions constrain the applicability of our framework. For instance, Rao points out that conditional expectations are used throughout econometrics, but there one often uses the Dynkin-Doob Lemma as definitional of the conditional expectation,⁴⁴⁴⁴44[55, 376]. For an example, see the presentation of conditional expectation in [20, Chapter 7]. and there is no more hope of having a single formula come out of it than there is of having all variables expressible in linear terms of one another. Likewise, conditional expectations and martingales can be used to prove theorems like the Radon-Nikodym Theorem,⁴⁵⁴⁵45[75, p. 145-146]. which is “computably false” in that there are computable absolutely continuous probability measures with no computable Radon-Nikodym derivative.⁴⁶⁴⁶46[70, p. 396], [77], [31]. That, of course, is not to say that these are not of interest or that determining how non-effective they are is not of interest, but just to say they will not be available in a framework like ours where we restrict to computable continuous conditional expectation operators.⁴⁷⁴⁷47The paper Ackerman et. al. [1] is an important recent paper studying how non-effective, in general, it is to have disintegrations. Our Definition 1.3, by contrast, restricts attention to those disintegrations that are highly effective. This will not be all of them, and we do not claim that it would be all of the interesting ones.

The paper is organised as follows. In §2, we begin with a brief discussion of some aspects of effectively closed sets and computable continuous functions and lsc functions which we need for our proof, and then we go over relevant aspects of the three computable Polish spaces which are central for effective probability theory:

• –

  The computable Polish space $\mathcal{M}^{+}(X)$ of non-negative finite Borel measures on $X$ and its computable Polish subspace $\mathcal{P}(X)$ of probability measures.

• –

  For each computable $\nu$ in $\mathcal{M}^{+}(X)$ and each computable $p\geq 1$, the computable Polish space $L_{p}(\nu)$.

• –

  For each computable $\nu$ in $\mathcal{M}^{+}(X)$ the computable Polish space $L_{0}(\nu)$ of Borel measurable functions which are finite $\nu$-a.s. and whose topology is given by convergence in measure.

The space $L_{0}(\nu)$ is needed since when $f$ is in $L_{p}(\nu)$, the maximal function $f^{\ast}=\sup_{n}\mathbb{E}_{\nu}[f\mid\mathscr{F}_{n}]$ is in $L_{0}(\nu)$, and is guaranteed to be in $L_{p}(\nu)$ iff $p>1$. In addition to being needed in the proofs of the main theorems, the material in §2 also can serve to contextualise many components of Definition 1.1. For instance, we mention in §2.2 a result of Hoyrup-Rojas that an element of $\mathcal{P}(X)$ is computable in the sense of Definition 1.1(3) iff it is computable as an element of the Polish space $\mathcal{P}(X)$. Likewise, in §2.3 we mention a result saying that an $L_{p}(\nu)$ Schnorr test is simply a non-negative lsc function whose equivalence class is a computable element of $L_{p}(\nu)$ (cf. Proposition 2.16). Finally, towards the close of §2.4, we define an $L_{0}(\nu)$ Schnorr test and prove a new characterisation of $\mathsf{SR}^{\nu}$ in terms of these tests (cf. Definition 2.28, Proposition 2.29).

In §3 we present two lemmas on Schnorr randomness. The second of these, called the Self-location Lemma (3.3) is a distinctive feature of Schnorr randomness (vis-à-vis the other algorithmic randomness notions), and is central to our proof of Theorem 1.6. In §4 we present some results on recovering the pointwise values of effective random variables on $\mathsf{SR}^{\nu}$. In §5, we review various classical features of the maximal function which we shall need later. In §6 we present an abstract treatment of Theorem 1.5 in terms of various effective constraints that a version of the conditional expectation may satisfy. In §7 we develop the fundamental properties of effective disintegrations. In §8, we prove Theorems 1.5-1.6, and in §9 we prove Theorems 1.8-1.9 and in §10 we prove Theorem 1.11. In §11, we show how Miyabe’s translation method allows us to recast Theorem 1.5 in terms of computable points of $L_{p}(\nu)$. In §12, we develop the theory of martingales in $L_{2}(\nu)$ and prove the aforementioned generalisation of Rute’s result characterising Schnorr randomness in terms of martingale convergence. In Appendix A we briefly exposit two classical examples of disintegrations, and in Appendix B we present several examples of effective disintegrations.

In a sequel to this paper, we present a similar analysis of the Blackwell-Dubins Theorem,⁴⁸⁴⁸48[5] which is also a “convergence to the truth” result, but wherein the pair “agent and world” is replaced with a pair of agents whose credences are variously absolutely continuous with respect to one another.

In this section, we briefly describe two further concepts from the theory of computable Polish spaces: namely effectively closed subsets and computable continuous functions, and we close by mentioning a few brief aspects of lsc functions.

Before we do that, we mention one elementary proposition on computable Polish spaces which is worth having in hand (for e.g. the Self-location Lemma 3.3):

As mentioned in §1, the complement of a c.e. open set is called an effectively closed set. In Cantor space and Baire space, the effectively closed sets can be represented as paths through computable trees.⁴⁹⁴⁹49[9, p. 41]. The following provides a simple example on the real line of a classically closed set which is not effectively closed:

Effectively closed subsets of a computable Polish space need not themselves have the structure of a computable Polish space, since one in addition needs to produce an enumeration of a countable dense set where the distance between the points is uniformly computable.⁵⁰⁵⁰50By contrast, classically, the Polish subspaces of a Polish space are precisely the $G_{\delta}$ subsets. See [34, p. 17]. Hence, we define: a computable Polish subspace $Y$ of $X$ is given by a an effectively closed subset $Y$ of $X$ and a countable sequence of points $y_{0},y_{1},\ldots$ which are uniformly computable points of $X$ and which are dense in $Y$. One can check that the c.e. opens relative to $Y$ are just the c.e. opens of the space $X$ intersected with $Y$, and further any effectively closed subset of $Y$ is also an effectively closed subset of $X$. Similarly, one can check that a computable point of $Y$ is just a computable point of $X$ which happens to be in $Y$. As a simple example of a Polish subspace which is not a computable Polish subspace, one has:

An effectively closed set $C$ is computably compact if there is a partial computable procedure which, when given an index for a computable sequence of c.e. opens $U_{0},U_{1},\ldots$ in $X$ which covers $C$, returns a natural number $n\geq 0$ such that $U_{0},\ldots,U_{n}$ covers $C$. We further say that $C$ is strongly computably compact if there is a partial computable procedure which, when given an index for a computable sequence of c.e. opens $U_{0},U_{1},\ldots$ in $X$ halts iff this is a cover of $C$, and when it halts returns a natural number $n\geq 0$ such that $U_{0},\ldots,U_{n}$ covers $C$. If $X$ itself is strongly computably compact, then so are all of its effectively closed sets. If $c<d$ is computable, then $[c,d]$ is strongly computably compact. Likewise, Cantor space is strongly computably compact, and if $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable then the computably bounded set $\{\omega\in\mathbb{N}^{\mathbb{N}}:\forall\;n\;\omega(n)\leq f(n)\}$ is a computable Polish subspace of Baire space which is strongly computably compact. Example 2.2 is an example of a compact computable Polish space which is not computably compact, since if it were then we could compute the endpoints using maxs and mins of the centres of finite coverings with fast decreasing radii. For another example of a compact computable Polish space which is not computably compact, one can take the paths through a computable subtree of Baire space which is not computably bounded.⁵¹⁵¹51See [10, Example 2.1.5 p. 59].

If $X,Y$ are two computable Polish spaces, then a function $f:X\rightarrow Y$ is computable continuous if inverse images of c.e. opens are uniformly c.e. open.⁵²⁵²52See Moschovakis [48, 110]. Simpson [70, Exercise II.6.9 p. 88] notes that it is equivalent to his preferred definition at [70, 85]. The following characterisation usefully parameterises each continuous computable function by a single c.e. set, where it is assumed for the sake of simplicity that both countable dense sets are identified with the natural numbers:⁵³⁵³53This is from [26, 1169]. It can be seen as a simplification of Simpson’s definition in [70, 85].

• –

  A function $f:X\rightarrow Y$ is computable continuous iff there is a c.e. set $I\subseteq\mathbb{N}\times\mathbb{Q}^{>0}\times\mathbb{N}\times\mathbb{Q}^{>0}$ such that both (i) if $(i,p,j,q)$ is in $I$ then $B(i,p)\subseteq f^{-1}(B(j,q))$ and (ii) for all $x$ in $X$ and all $\epsilon>0$ there is $(i,p,j,q)$ in $I$ with $x$ in $B(i,p)$ and $q<\epsilon$.

Computable continuous maps are also computable continuous when restricted to computable Polish subspaces. The computable continuous maps preserve computability of points:

There is a partial converse to the previous proposition in the uniformly continuous setting. A computable modulus of uniform continuity for a uniformly continuous function $f:X\rightarrow Y$ is a computable function $m:\mathbb{Q}^{>0}\rightarrow\mathbb{Q}^{>0}$ such that $d(x,x^{\prime})<m(\epsilon)$ implies $d(f(x),f(x^{\prime}))<\epsilon$ for all $\epsilon$ in $\mathbb{Q}^{>0}$. For instance, if $c>0$ is rational, then a $c$-Lipschitz function is just a function with linear modulus of uniform continuity $m(\epsilon)=\frac{c}{2}\cdot\epsilon$. The partial converse to Proposition 2.4 is the following: