{'fraction_non_alphanumeric': 0.06785588781606118, 'fraction_numerical': 0.014709081477267023, 'mean_word_length': 3.4480833643468554, 'pattern_counts': {'":': 1, '<': 81, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithmic randomness for Doob's martingale convergence theorem in continuous time

We study Doob's martingale convergence theorem for computable continuous time martingales on Brownian motion, in the context of algorithmic randomness. A characterization of the class of sample points for which the theorem holds is given. Such points are given the name of Doob random points. It is shown that a point is Doob random if its tail is computably random in a certain sense. Moreover, Doob randomness is strictly weaker than computable randomness and is incomparable with Schnorr randomness.

This material is based upon work supported by the National Science Foundation under Grant No. 0901020 (Kjos-Hanssen and Rute) and under Grant No. 0841223 (Nguyen). This work was partially supported by a grant from the Simons Foundation (#315188 to Bjørn Kjos-Hanssen). We would like to thank the anonymous referees for their helpful feedback.

Introduction
This paper is concerned with computable continuous-time gambling strategies, and their corresponding capital value functions, referred to as martingales. First developed by Ville in the 1930's, martingales are a central tool in the study of both algorithmic randomness and classical probability theory.
The classic example of a martingale is as follows. A gambler, who has a starting capital of M 0 , places a wager on the outcome of a fair coin toss. If she wins, her capital increases. If she looses, it decreases by the same amount she would have won. This new capital value is denoted M 1 . She continues to place bets on new coin tosses, giving rise to the capital values M 2 , M 3 , . . .. Since the capital value M n at time n depends on the sequence of coin tosses, we write it as a function M n : 2 N → R. This sequence of capital value functions (M n ) is what is known as a martingale. If the martingale is nonnegative (i.e., the gambler never goes into debt), then Doob's martingale convergence theorem says that (M n ) converges with probability one as n → ∞ (Theorem A.2).
Schnorr used martingales to define what is now known as computable randomness. Namely, α ∈ 2 N is computably random if lim sup n M n (α) < ∞ for all computable nonnegative martingales (M n ). By a folklore result, α ∈ 2 N is computably random iff M n (α) converges as n → ∞ for all computable nonnegative martingales (M n ), thereby giving an effective version of Doob's martingale convergence theorem.
Martingale theory is an important tool in modern probability theory and financial mathematics. The process of flipping coins can also be thought of as a random walk on the integers (move +1 on heads and −1 on tails). By decreasing both the time step and increment amount to be infinitesimally small, this random walk converges to a continuous process known as Brownian motion. A Brownian motion sample path is almost-surely continuous, nondifferentiable, and has high complexity. Brownian motion can be used to model many real-world processes. Doob developed a rigorous theory of continuoustime martingales (M t ) t∈[0,∞) , including martingales which bet on Brownian motion. (The reader may choose to think of Brownian motion as the value of a stock over time and the martingale (M t ) as the value, at time t, of a stock portfolio which buys and sells that stock according to a certain strategy.) Doob's martingale convergence theorem still holds: if (M t ) is a nonnegative right-continuous martingale, then (M t ) converges with probability one as t → ∞ (Theorem A.7).
The purpose of this paper is to study a new randomness notion on Brownian motion, which we call Doob randomness. Namely, a Brownian motion sample path W ∈ C[0, ∞) is Doob random (Definition 6.6) if M t (W ) converges as t → ∞ for all computable nonnegative martingales (M t ). The reader may be tempted to think of Doob randomness as the continuous-time analogue of computable randomness. However, computable randomness already has a more natural definition on Brownian motion [20], and we show that Doob randomness is a strictly weaker notion than computable randomness. This weakness has an intuitive explanation: because our martingales are computable, M t must be finite at all times t. Hence a martingale cannot gain more than a finite amount of money solely based on the non-randomness of some proper initial segment of the Brownian motion. Indeed, we show there are Doob random paths which are constant in the interval [0, 1], whereas this property cannot hold for a computably random Brownian motion path. For similar reasons, Doob randomness is incomparable with Schnorr randomness (another randomness notion weaker than computable randomness).
Instead, Doob randomness depends on the limiting behavior of the Brownian path as time goes to infinity. This means that a path is Doob random if and only if "the tail of the path is computably random" in some sense.
We believe Doob randomness is interesting because it adds a new dimension to the study of randomness. When a Brownian path fails to be Doob random, it is not just because the path contains nonrandom information, but also because there is enough time available to exploit that information to gain capital. In other words, the order in which we process information now matters in our randomness test. The space of Brownian motion paths is not just a probability space, but instead it is a probability space with an implicit "time structure". 1 Our paper is structured as follows. In Section 2, we provide background on computable analysis and computable measure theory. In Section 3, we introduce expectation and martingales on 2 N and define computable randomness.
Before studying Brownian motion, we look at two spaces that also have an interesting implicit notion of "time", (2 N ) N and 2 N×N . We find that these two spaces provide a nice simplified setting for studying Brownian motion. In Section 4, for a sequence of sequences ω = (ω n ) ∈ (2 N ) N , we consider computable martingales which bet on the entire sequence ω n at time n. Again, the resulting notion of randomness depends on the limiting behavior of (ω n ) as n → ∞.
In Section 5, we look at martingales which bet on bits of 2 N×N using the lexicographic order of N × N, thereby introducing limit stages into our martingales. This leads to a characterization of Doob randomness via a strategy where the gambler is only allowed to bet on finitely many bits of one row 2 , before moving to the next. This latter characterization is closely related to a result of Miyabe [15] generalizing van Lambalgen's theorem to the space (2 N ) N . We show that his result holds for Schnorr randomness.
In Section 6, we use the results of Sections 4 and 5 to characterize Doob randomness on Brownian motion. We decompose a Brownian path W on the infinite time interval 0 ≤ t < ∞ into countably many independent Brownian paths, each on the time interval 0 ≤ t ≤ 1. Then we represent each of these by a sequence in 2 N , thereby representing our original path W as a sequence in (2 N ) N . Using this correspondence, we prove that Doob randomness is strictly weaker than computable randomness and that Doob randomness is incomparable with Schnorr randomness. This paper brings together a number of fields including algorithmic randomness, computable analysis, measure theory, martingale theory, and Brownian motion. In an effort to make this paper more accessible to a broad audience, we have tried to limit the use of 1 This time structure can be made explicit using filtrations. See Appendix A. Another type of probability space with additional structure is a measure preserving system. It would be interesting to explore definitions of randomness which take this structure into account. 2 We say that (i, j) ∈ N × N belongs to row i + 1 and column j + 1, i.e., we think in terms of matrices rather than cartesian planes.
advanced probability theory. The reader does not need to be familiar with stochastic calculus, Brownian motion, or even martingale theory. Instead our proofs use basic computable analysis and measure theory, and we carefully spell out the few facts we will need about conditional expectation, martingales, and Brownian motion. This elementary exposition is most apparent in our definitions of conditional expectation and martingales. Instead of giving one general definition of a martingale (as is done in probability texts), we give a handful of similar definitions. For example, we separately define N-indexed martingales on (2 N ) N , N × N-indexed martingales on 2 N×N , and [0, ∞)indexed martingales on the space of Brownian motion. This allows us to present elementary proofs of our results, at the cost of a little extra notation. These definitions also make it easier for us to reason computably about conditional expectation. However, for the reader who wants to know more about the probabilistic background, we provide Appendix A.
There we give further background on conditional expectation, filtrations, martingales, and Brownian motion. We also derive our characterization of conditional expectation from the standard definitions.

Background
In this section, we will present relevant background about computable analysis and algorithmic randomness. We assume the reader is familiar with basic computability theory as well as computability on the real numbers, including computable functions between the spaces 2 N , N N , and R. We also assume the reader has a basic grasp of analysis, including basic measure theory. The setting of computable analysis is a computable metric space, that is a metric space (M, d) with a countable set of points {a n } ⊆ M (called the simple points) such that d(a m , a n ) is uniformly computable from the pair (m, n). The spaces 2 N , C([0, 1]), and C([0, ∞)) are computable metric spaces under the usual metrics d(α, β) = inf{2 −n : α n = β n }, d(f, g) = f − g ∞ , and d(f, g) = n 2 −n min{ (f − g) ↾ [0, n] ∞ , 1} (using any reasonable choice of simple points). A Cauchy name is an element f ∈ N N such that for all n ≥ m we have |a f (n) − a f (m) | ≤ 2 −m . A computable point of M is a point with a computable Cauchy name. For two computable metric spaces, M 1 , M 2 , a continuous map of type f : M 1 → M 2 is called computable if there is a partial computable map of type N N → N N which maps each name of x to a name of f (x). We say that y ∈ M 2 is uniformly computable from x ∈ M 1 if there is a total computable map f : M 1 → M 2 such that f (x) = y. (We sometimes drop the "uniformly" if it is clear.) For example, on the compact space [0, 1] (and the same for 2 N ), the maximum and minimum values of a continuous function f ∈ C([0, 1]) are uniformly computable from f . The computable points of C([0, 1]) and C([0, ∞)) are exactly the computable functions of type [0, 1] → R and [0, ∞) → R, respectively. For more information on these results see the book by Weihrauch [25].
There are other computable structures that are not necessarily objects in a computable metric space. For example, a lower semicomputable function f : M → [0, ∞] is the supremum of a computable sequence (f n ) of nonnegative computable functions. An upper semicomputable function is the infimum. We say r ∈ [0, ∞] is lower semicomputable from x ∈ M if there is a lower semicomputable function f : M → [0, ∞] such that f (x) = r. An effectively open or Σ 0 1 set is a computable union of balls B(a, r) where a ∈ M is a simple point and r ∈ Q. Similarly an effectively closed or Π 0 1 set is the complement of a Σ 0 1 set. The computable functions, lower semicomputable functions, upper semicomputable functions, Σ 0 1 sets, and Π 0 1 sets are, respectively, the computable points in the spaces of continuous functions, lower semicontinuous functions, upper semicontinuous functions, open sets, and closed sets. Each of these spaces have a natural representation which assigns to each object in the space a set of names in N N . This also allows us to talk about, say, computable maps from the open sets to the reals. (See Weihrauch and Grubba [26] for more details.) Now we turn to computable measure theory. More more information see the paper by Hoyrup and Rojas [11] and the lecture notes by Gács [8].
Definition 2.1. A computable probability space (Ω, P) is a computable metric space Ω equipped with a computable Borel probability measure P, that is P is a Borel probability measure on Ω which satisfies any of the following equivalent properties (see [11]).
(1) The map f → f dP is lower semicomputable, where f ranges over nonnegative continuous functions on Ω. (2) The map f, c → f dP is computable, where f ranges over continuous functions bounded above by c ∈ R and bounded below by −c. For example, property (3) in the previous definition implies that the measure of Σ 0 1 sets is lower semicomputable, and the measure of Π 0 1 sets is upper semicomputable. Also for the compact space 2 N (or [0, 1]), since the maximum and minimum operations are computable, f → f dP is a computable map of type C(2 N ) → R.
We will have occasion to use both of these randomness notions. (Computable randomness will be defined in Section 3, when we introduce martingales.) For more information, see Downey and Hirschfelt [6] for randomness on 2 N and see [11,9,20] for randomness in a computable metric space.
(1) A Martin-Löf test is a computable sequence of Σ 0 1 sets U n such that P(U n ) ≤ 2 −n . (2) A Schnorr test is a Martin-Löf test such that P(U n ) is uniformly computable from n. (3) A point ω ∈ Ω is Martin-Löf random (resp. Schnorr random) if ω / ∈ n U n for all Martin-Löf tests (resp. Schnorr tests).
All computable functions f on 2 N are integrable 3 and the expectation E(f ) = f dP is computable uniformly from f (Definition 2.2 and the following paragraph). We can define conditional expectation as follows.
Definition 3.1. Given an integrable function f : 2 N → R define E n (f ) as the function given by Note, if f is computable, then E n (f )(α) is computable uniformly from f and α <n .
Conditional expectation is an important concept in probability theory. See Appendix A for more information. We will introduce a number of different variations of Definition 3.1 for different spaces and different choices of indices. Nonetheless, they will all satisfy the following five important properties which are straightforward from the definition of E n (compare with Proposition A.1). Let f and g be integrable functions.
(1) If f (α) only depends on α <n for all α, then E n (f ) = f . Here is another characterization of computable martingales. Proof. Assume (M n ) is a computable martingale. Then clearly (1) and (2) hold. Conversely, assume that (1) and (2) hold. Then M n is a computable function uniformly in n. Further, M n (α) = (E n M n+1 )(α) and is therefore computable from α <n and n. Also, the more general property m ≤ n, E m M n = M m follows by (2) and induction.
Remark 3.5. The more standard notation in computability theory is to write a martingale as a function d : 2 * → R (where 2 * is the set of finite binary sequences) such that . These are the same using M n (α) = d(α <n ).  (1) α is not computably random.
(3) (M n (α)) diverges as n → ∞ for some computable nonnegative martingale (M n ). Theorem 3.7 is an effective version of Doob's martingale convergence theorem (Theorem A.2), which says that nonnegative martingales converge almost surely. More information about computable randomness on 2 N is available in, for instance, Downey and Hirschfeldt's monograph [6].

Doob random sequences of sequences
In this section, we consider the space (2 N ) N with the uniform 4 probability measure P. We use the variables ω, ξ and ψ for sequences in (2 N ) N . Each ω ∈ (2 N ) N is an infinite sequence of infinite sequences ω n , and we write ω = (ω 0 , ω 1 , . . . ). Then we let ω <n = (ω 0 , . . . , ω n−1 ), ω ≥n = (ω n , ω n+1 , . . . ), and let ⌢ be concatenation of strings. The space ((2 N ) N , P) is isomorphic to 2 N with the fair coin measure by the computable isomorphism ω → n∈N ω n . 5 Therefore all computable functions f on (2 N ) N are integrable and the expectation E(f ) = f dP is computable uniformly from f . 6 As before we can define conditional expectation and martingales as follows.
Definition 4.1. The conditional expectation E n for an integrable function f : Again, E n (f )(ω) is computable uniformly from f and ω <n and the properties of Remark 3.2 still hold.  Another way to define E n and martingales is as follows. Let the projections X n : (2 N ) N → 2 N be given by X n (ω) = ω n . Let F n = σ(X 0 , . . . , X n−1 ), i.e., the σ-algebra generated by the first n projections. For a function f : that is the conditional expectation of f given F n . This agrees with our definition of E n up to a.e. equivalence. A martingale adapted to (F n ) is a sequence (M n ) of integrable functions such that M n is F n -measurable and E(M n | F m ) = M m . Again, this definition of martingale agrees with ours (up to a.e. equivalence). See Appendix A.
A Schnorr test can be encoded by a function f ∈ N N which encodes a listing of basic open sets for each n which union up to U n , and also encodes a fast Cauchy sequence of rationals converging to each measure µ(U n ) [14]. This allows us to make the following definition. 4 To be clear, P is the product measure on (2 N ) N of the product measure on 2 N of the fair-coin measure on 2 = {0, 1}. 5 As usual n∈N ωn n,k = (ωn) k where ·, · is a computable bijective pairing function. 6 By this we mean that the map f → E(f ) is a total computable map of type C((2 N ) . Let α, β ∈ 2 N . We say that α is Schnorr random uniformly relative to β if there is no uniform Schnorr test such that α ∈ n U β n . Similarly, a collection (M γ ) γ∈2 N of martingales on 2 N is a uniform martingale test if there is some total computable function Φ : 2 N → N N such that each Φ(γ) encodes a martingale. Let α, β ∈ 2 N . We say that α is computably random uniformly relative to β if there is no uniform martingale test such that lim sup n M γ n (α) = ∞.
(2) ω is e.c.u. random (eventually computably uniformly random) if there is some n such that ω ≥n is computably random uniformly relative to ω <n .  This is not true of the definitions of E n , martingale, e.c.u. randomness, and Doob randomness. They depend on an implicit notion of time in the space. For us, time is expressed as the index n in the conditional expectation E n . (One could also use the probabilistic notion of a filtration to define time. See Appendix A.) Fix a standard enumeration of the rationals {q n } n∈N = Q. We define a computable rational-valued function to be a function f : from finitely many bits of ω. In particular, there is some n computable from the index for f such that f (ω) is uniformly computable from ω <n . Hence, the range of f is finite and computable from f . 7 Lemma 4.7. If f is a computable rational-valued function, then E n (f ) is a computable rational-valued function uniformly from f .

Proof.
Recall that by definition, E n (f )(ω) = E(g) for some rational-valued function g computable uniformly from f and ω. Further, from g we may compute a single number in N which codes (1) the finitely-many possible rational values a 1 , . . . , a k that g may take, (2) the clopen sets A 0 , . . . , A k such that A i = g −1 (q i ), and (3) the rational values of P(A i ) for each i.
Then we may compute the rational value of E(g) = k i=1 a i · P(A i ). 7 Note that a computable rational-valued function is not the same as a computable function taking rational values. An example of the latter is f (α) = inf{2 −n | α<n = 0 n }.
It is not too hard to obtain the following analogue of Theorem 3.7.
Fix k. From the index for each M n , we may effectively find a rational-valued function N n depending only on ω <n such that N n − M n ∞ ≤ 2 −(n+k+2) . However, (N n ) may not be a martingale. To make it such, let L 0 = N 0 and recursively define (L n ) as This function L n remains rational-valued by Lemma 4.7.
We have that (L n ) is a computable martingale as follows. For each n, . By the definition of E n as well as the definition of martingale, we have Hence by the induction hypothesis, as desired.
For ω, there are infinitely many upcrossings.
Note that for any ξ ∈ (2 N ) . The same holds for σ down k (ξ). We define our new martingale recursively as follows. The idea is that N increases on the upcrossings and is constant on the downcrossings. Let N 0 = M 0 and .
It is easy to see that each N n is rational-valued uniformly in n.
Next we shall show that (N n ) is a computable nonnegative martingale. Fix n. We can simulate the cases in the definition by multiplying by indicator functions. Let . Also, let k(ξ) be the corresponding k for each case. Notice, these functions depend only on ξ <n . (Even though, these functions talk about events at time n + 1, their values are determined at time n.) Then by the properties of Remark 3.2, we have The last line follows by using the definition of N n and considering the following four cases individually: n > σ up k , n = σ up k , n > σ down k , n = σ up k . Therefore (N n ) is a computable martingale.
One can see that the martingale is nonnegative by showing (using induction) that on the upcrossing phase, is finite for all k since there are infinitely many upcrossings of M n (ω). Then using the definitions of (N n ), σ down k and σ up k , it follows by induction that Hence lim sup n N n (ω) = ∞. 8 That is: if it is finite, we can compute it; if it is infinite, we can determine that it is above each finite number.
(3) ⇒ (4): Assume lim sup n M n (ω) = ∞. We will apply the "savings property method": every time our martingale doubles in value, we keep half of the capital and only bet with the remaining half. Let τ 0 = 0 and τ k+1 = inf{n > τ k : It is easy to see that each N n is rational-valued uniformly in n. Now we show (N n ) is a computable nonnegative martingale. The proof is similar to the "upcrossing method" above. Fix n. Let k(ξ) be such that n + 1 ∈ (τ k , τ k+1 ]. This function depends only on ξ <n . By the properties of Remark 3.2, we have The last line follows by using the definition of N n and considering the following two cases individually: n > τ k , n = τ k . Therefore (N n ) is a computable martingale.
One can see that the martingale in nonnegative by induction.
is finite for all k since M n (ω) is unboundedly large. Then using the definitions of (N n ) and τ k , we have (4) ⇒ (1): Immediate.

4.1.
Almost everywhere computable martingales. Up till now, it has sufficed to work with total computable martingales. However, this will not be the case when we transition to Brownian motion in Section 6. This subsection will culminate in a characterization of Doob randomness (under the assumption of Schnorr randomness) in terms of a.e. computable martingales in Theorem 4.16 below. The proofs in this subsection are general enough that they will also apply to Brownian motion in Theorem 6.7 and Lemma 6.8. , see also [20]). An a.e. computable function f : (Equivalently, f is a partial computable function given by an partial computable map g which maps ω to a name for f (ω). In this case the domain of f is the Π 0 2 domain of g.) Note that the domain of an a.e. lower semi-computable function is the intersection of a uniformly Π 0 2 sequence of sets and therefore Π 0 2 . Proposition 4.12. Assume f is nonnegative and a.e. computable. Then E n f is a.e. lower semicomputable in n and f . As for L 1 -computability, if Ef is computable and f is nonnegative, then f is L 1computable [10]. Let (g k ) be the sequence of bounded computable functions from the definition of L 1 -computability. Then h k := E n g k is computable uniformly from g k (and its bound). Further, we have by Remark 3 We now come to a lemma that will be used on three separate occasions, a very useful generalization of [17,Lemma 3.11].
Lemma 4.13. Given (the name of ) an a.e. computable function f (respectively, (the name of ) a sequence of a.e. computable functions (f i )), one can effectively find a dense sequence of points {a n } n∈N ⊆ R such that P{ω | f (ω) = a n } = 0 (respectively, P{ω | ∀i f i (ω) = a n } = 0) for all n. This implies that for any such a n , the measure P{ω | f i (ω) ≤ a n } is uniformly computable from n and i. Moreover, this result also holds for L 1 -computable functions in place of a.e. computable functions.
Proof. Consider a computable sequence (f i ) of a.e. computable functions (or L 1 -computable functions). Consider the push-forward measures µ i given by These are computable from f i [10]. Fix k. Now, enumerate all rationals intervals [q i , r i ] such that max{µ 0 ([q i , r i ]), . . . , µ k ([q i , r i ])} < 2 −k . This is enumerable, since the measure of a Π 0 1 set is upper semicomputable [11,Proposition 4.3.1]. Now let U k = i (q i , r i ). The sequence (U k ) is a uniformly Σ 0 1 sequence of dense sets. Therefore, one can compute a dense sequence of points a n in the intersection k U k . 9 Notice that any such a n cannot be an atom of the push-forward measure µ i , and therefore P{ω | f i (ω) = a n } = 0. To see that P{ω | f i (ω) ≤ a n } is computable, just notice that since a n is not an atom of µ i we have P{ω | f i (ω) ≤ a n } = µ i ((−∞, a n ]) = µ i ((−∞, a n )). Since µ i ((−∞, a n ]) is the measure of a Π 0 1 set it is upper semicomputable, while µ i ((−∞, a n )) is the measure of a Σ 0 1 set and is lower semicomputable [11,Proposition 4 Lemma 4.14. Given ǫ > 0, δ > 0, n ∈ N, and a nonnegative a.e. computable function f with a computable expectation, we can find a computable function g, a Σ 0 1 set U of computable measure, and a number d (all uniformly computable from the names for ε, δ, n, f , and Ef ) such that P Proof. A nonnegative a.e. computable function f with a computable expectation is L 1computable [10]. By the definition of L 1 -computable, we can find a nonnegative bounded computable function g with a bound d such that f − g L 1 ≤ δ · ǫ/8(n + 1). Unfortunately, since f may not be bounded, E m f may not be a.e. computable. Instead we have that E m f is L 1 -computable and a.e. lower semicomputable (Proposition 4.12). Let h = min{f, d}.
Since h and g are bounded by d, we have E m g and E m h are a.e. computable. Therefore Let a ∈ {a n } be from Lemma 4.13 such that ε/4 < a < ε/2. We have by Markov's inequality that By Lemma 4.13, the set V 0 m has computable measure, but we would also like V 0 m to be Σ 0 1 . This depends on which undefined points of This set is Σ 0 1 with a computable measure satisfying the desired properties.  (1) (M n (ω)) diverges as n → ∞ for some computable nonnegative martingale (M n ) with a computable bound on the growth d : N → R such that M n ∞ ≤ d(n).
(2) ⇒ (3): This direction is immediate from the fact that a computable martingale is a.e. computable.
By Lemma 4.14, from k and from the code for each M n , we may effectively find a computable function N n (depending on k) such that |N n (ξ) − M n (ξ)| ≤ 2 −(n+k+2) and measure at most 2 −(n+k+1) . Further, by Lemma 4.14, we may assume N n ∞ < d(n) for a computable bound d(n). (Also, the value of N n (ξ) depends only on ξ <n .) Then n U k n n∈N,k∈N is a total Solovay test 10 and therefore there is some large k such that ω / ∈ U k n for all n. However, (N n ) may not be a martingale. To make it such, let L 0 = N 0 and recursively define L n as Similarly to the proof of Theorem 4.8 ((1) ⇒ (2)), (L n ) is an a.e. computable martingale. Also, L n ∞ ≤ n 2d(n).
To see that |L n (ξ) − M n (ξ)| ≤ 2 −k , we must do calculations similar to that of Theorem 4.8 ((1) ⇒ (2)). To show |L n (ω) − M n (ω)| ≤ (2 − 2 −n )2 −(k+1) < 2 −k by induction, we will repeat the same calculations as in Theorem 4.8 ((1) ⇒ (2)), with the following adjustment. Since there is no global bound, we will show the bound directly for ω. We have . Hence by the induction hypothesis, as desired. 10 A total Solovay test is a sequence (or in this case a doubly-indexed sequence) of Σ 0 1 sets U k n such that n k µ(U k n ) is finite and computable. By [6, Theorem 7.1.10], every Schnorr random ω is in only finitely many U k n .
We will naturally identify the spaces (2 N ) N and 2 N×N by denoting the m + 1st sequence of ω as the row ω m = (ω m,0 , ω m,1 , . . . ). Then we may associate ω <m with ω <(m,0) and ω ≥m with ω ≥(m,0) . The definitions of conditional expectations E n and martingales (M n ) n∈N carry over from Definitions 4.1 and 4.2, except that we now refer to such martingales as N-indexed martingales. The definitions of computable, ecu, Doob, and Schnorr randomness also carry over. All the conditional expectation properties of Remark 3.2 still hold. This next proposition shows that these N × N-indexed conditional expectations and martingales are just extensions of the N-indexed ones. Proof. To see that E m,0 = E m , take an integrable function f . Then by the identification of 2 N×N and (2 N ) N , As for N m = M m,0 , first notice that M m,0 is determined by ω <m,0 = ω <m . Then for  (1) ω is not Doob random.
(3) ⇒ (4): Let (M m,n ) be as in (3). Since each M m+1,0 (ξ) is a computable rationalvalued function, it can only depend on finitely many bits of ξ <(m+1,0) = ξ <m+1 . Hence there is some k = k(m, ξ) such that M m+1,0 (ξ) only depends on ξ <(m,k) . Since ξ → k(m, ξ) is a computable function uniformly in m on the effectively compact space 2 N×N , it has a maximum which is uniformly computable from m. So we may assume k = k(m) is that maximum. Since M m+1,0 only depends on the bits with index below (m, k) we have M m+1,0 = E m,k (M m+1,0 ) = M m,k , and the same for all n ≥ k.
We can modify (M m,n ) to a martingale (L m,n ) with the same properties, but also such that lim inf L m,n (ω) = ∞. To do this, we can just use the upcrossing and savings techniques in the proofs in Theorem 4.8. The proofs are the same, except with the following changes to the indices. Use the indices (m, n) such that n < k(m). Since the order type of this set of indices is that of N, the proofs are the same. Remark 5.5. Using (4) of Theorem 5.4 we can characterize Doob randomness in terms of a gambling strategy on bits. The gambler starts by betting on the bits of ω 0,0 , ω 0,1 , . . . . At some stage of the gambler's choosing, she must progress to the next row and start betting on the bits of ω 1,0 , ω 1,1 , . . . in order. However, now the gambler may use all the bits of ω 0 = (ω 0,0 , ω 0,1 , . . . ), including the bits she never bet on, as an oracle for future betting. This process continues, with the condition that the gambler must eventually progress to each row ω n (where she can then use ω <n as an oracle). Her strategy must be total, in that she must specify for all possible ω how to bet and when to progress from ω n to ω n+1 for all n. While the choice of when to progress to the next row may be adaptive (depending on the bits seen so far), Theorem 5.4 shows that it is sufficient for it to be independent of the array being bet on.

Doob randomness via computable randomness.
We can also characterize Doob randomness entirely in terms of computable randomness.
Definition 5.6. Let C be an infinite, computable subset of N × N. For ω ∈ 2 N×N , define ω C ∈ 2 N to be the bits of ω with indices in C listed in some fixed computable ordering of C. Given a computable function f : N → N, let (A for "above", B for "below".) This definition will also be extended to noncomputable functions f . In this case, A f and B f are ordered by an ordering computable from f . Lemma 5.7. Computable randomness is preserved by computable permutations. Moreover, assume α ∈ 2 N is computably random uniformly relative to β ∈ 2 N . Then any computable permutation of the bits in α is still computably random uniformly relative to β.
Proof. See [2, Introduction] and [4] for the result that computable randomness is preserved by permutations. The proof indicated there can be uniformly relativized to an oracle β. Remark 5.9. This can again be characterized as a game similar to Remark 5.5. Now the gambler may bet on any bit he chooses. However, as before, for each row he must decide when to stop betting on that row. Yet, as before, he may still use the other bits in that row as an oracle for future bets.
For the proof of Theorem 5.8, we will need yet another generalization of conditional expectation and martingales, this time indexed by subsets of N × N.
Definition 5.10. Given a computable set D ⊆ N × N with complement D c , define the concatenation operator ⌢ D to be the unique computable operator 2 N × 2 N → 2 N×N such that for all α, β ∈ 2 N , if ω = α ⌢ D β, then ω D = α and ω D c = β. For an integrable function f : 2 N×N → R, define Notice that E m,n = E D where D = {(k, ℓ) | (k, ℓ) < (m, n)}. We will abbreviate this set as {<(m, n)}. The corresponding properties of Remark 3.2 still hold-for example, if C ⊆ D, then E C (E D f ) = E C (f ). For a sequence C 0 ⊆ C 1 ⊆ . . . of computable sets, define a martingale (M C i ) as a sequence of integrable functions such that (1) M C i only depends on C i and ω C i and (2) for all i < j, Proof of Theorem 5.8. (⇐): Assume ω is not Doob random. Let (M m,n ) and k : N → N be as is (3) of Theorem 5.4. As mentioned in Remark 5.5, (M m,n ) bets on the bits of ω B k using ω A k (uniformly) as an oracle. A little thought reveals that the order that (M n,m ) bets on the bits of ω B k is of order-type N. (That is, there are no limit stages.) Therefore, we can use (M m,n ) to construct an N-indexed martingale which bets on ω B k (in some order) using ω A k uniformly as an oracle. Thereby, ω B k is not computably random uniformly relative to ω A k . (Lemma 5.7 shows that the choice of ordering of A k and B k is not important.) (⇒): Assume ω B f is not computably random uniformly relative to ω A f . By Lemma 5.7 we may assume that B f is ordered using the lexicographical ordering of N × N. Then there is a uniformly computable rational-valued martingale (N β n ) (i.e. for all β ∈ 2 N , (N β n ) is a martingale on 2 N uniformly computable from β) such that lim inf n N ω A f n (ω B f ) = ∞. We may assume for every β that (N β n ) has a savings property such that N β n ≥ N β m /2 for all m ≤ n.
Our goal is to convert this class of martingales (N β n ) into a martingale (K m,n ) on 2 N×N . This is complicated by the fact that our uniform martingale (N β n ) looks at the bits in a different order than the lexicographical ordering on N × N. The advantage of martingales indexed by sets is that it gives us a language for talking about betting on bits in a different order.
We will convert the class of martingales (N β n ) as a single martingale indexed by sets. Let B = B f and A = A f . Let A = {a n } and B = {b n } be computable enumerations of A and B. Let A n = {a 0 , . . . , a n−1 } and B n = {b 0 , . . . , b n−1 }. Then we define the martingale M A∪Bn (ξ) = N ξ A n (ξ B ). We will first show that (M n ) is a computable martingale. Notice is uniformly computable from ξ A and (ξ B ) <n , or equivalently, ξ A∪Bn . Lastly, for m ≤ n, we can unwrap the definitions to Since M A∪Bn is rational-valued, it only depends on finitely many bits of ξ. In fact, M A∪Bn is truth-table computable in the following sense: There is some computable function ℓ : N → N such that M A∪Bn (ξ) is computable uniformly from n, ξ A ℓ(n) , and ξ Bn .
Recall our assumption that B = b n is ordered lexicographically. Define C n = {(m, k) | (m, k) < b n } ∈ N × N. Then A ℓn ∪ C n are the infinitely many positions C m that come before b n as well as the finitely many positions in A ℓn C n which represent oracle bits looked at in the future. The goal is get rid of the dependence on Let L A ℓ(n) ∪Cn (ξ) = M A∪Bn (ξ). Now we can show that (L A ℓ(n) ∪Cn ) is also a martingale. For m < n we have (M A∪Bm only depends on the bits in A ℓ(m) ∪ C m ) Last, we define a martingale on 2 N×N by The following calculation shows that K m,n is a martingale. Let K m,n be as in the previous formula. Assume (m ′ , n ′ ) ≤ (m, n) and k ′ ≤ k such that k = min{i : (m, n) ≤ b i ∈ B} and k ′ = min{i : Finally, we show that lim sup m,n L m,n (ω) = ∞. Pick a large number c > 0. Since lim inf k N ω A k (ω B ) = ∞, there is an k 0 such that N k 0 (ω) ≥ 2c. Let k > k 0 . Then by the above definitions as well as the savings property, Hence lim sup m,n L m,n (ω) = ∞ as desired and ω is not Doob random.

Doob, Schnorr, and computable randomness.
Here we show that Doob randomness is strictly weaker than computable randomness and incomparable with Schnorr randomness.
Proof. This is the same proof as in [16] uniformly relativized to γ.
Corollary 5.12. Let ω ∈ 2 N×N and let D ⊂ N × N be an infinite computable set. If ω is computably random (uniformly relative to γ) then ω D is computably random uniformly relative to ω D c (respectively, uniformly relative to ω D c and γ).
Proof. Follows from Theorem 5.11 and Lemma 5.7.
(2) ⇒ (3): Assume that ω ≥n is computably random uniformly relative to ω <n for some n. Fix a computable function f : N → N. By Theorem 5.8, it suffices to show that ω B f is computably random uniformly relative to ω A f . We may assume that f (k) = 0 for each k < n, since it would only add and remove finitely many bits to/from ω A f and ω B f . Let C = {(k, ℓ) ∈ A f | k ≥ n} be the coordinates of A f for which the first coordinate is ≥ n, and let ω C be the corresponding bits of ω listed in a computable order. Note that ω A ⊕ ω B is a computable permutation of the bits in ω ≥n and that computable randomness is preserved under computable permutations (Lemma 5.7). Then ω A ⊕ ω B is computably random uniformly relative to ω <n . Hence by Theorem 5.11, ω B is computable random uniformly relative to ω C ⊕ ω <n which is just a computable permutation of ω A f .
(3) ⇒ (2): Let g be a function which dominates all computable functions f , that is g(n) > f (n) for all but finitely many n. Define ω as follows. Choose α ∈ 2 N to be Martin-Löf random relative to g. 11 Let B g be the set of coordinates below g. Give B g an ordering computable from g. Then let ω Bg be the bits of α put into the positions in B g using the ordering on B g . Let ω Ag , i.e., ω in the positions above g, be all 0s. Then each row ω n ends in 0s. First, we show that ω is not e.c.u. random. By Corollary 5.12, if ω ≥n is computably random, then ω n would be computably random which it is not. So ω is not e.c.u. random. Now, we show that ω is Doob random using the characterization in Theorem 5.8. The proof is similar to (2) ⇒ (3). Choose a computable function f . Let A f and B f , respectively, be the coordinates above and below f . Let C f,g be the coordinates above f and below g. Without loss of generality, we may assume f < g for all values, for this only changes finitely many bits of ω A f and ω B f . 11 We could let α be computably random uniformly relative to g instead. However, computable randomness uniformly relative to an oracle in N N is not in the existing literature. Therefore, we used a stronger notion of randomness, (defined in, e.g., [6,Section 6.4]).
We want to show that ω B f is computably random uniformly relative to ω A f . Recall that ω Bg is Martin-Löf random relative to g. By van Lambalgen's theorem for Martin-Löf randomness relativized to g (similar in form to Theorem 5.11, see [6, Theorem 6.9.1]), we have that ω B f is Martin-Löf random relative to ω C f,g and g.
Hence ω B f is also Martin-Löf random relative to ω A f , since ω A f is computable from ω C f,g and g. Then, ω B f is also computably random uniformly relative to ω A f (see [16,14]).
(3) ω is Doob random and Schnorr random. (2) ⇒ (1): Let ω be such that ω 0 is Schnorr random, but not computably random (such a sequence exists by a result of Wang [24]) and such that ω ≥1 is computably random uniformly relative to ω 0 (there are measure one many such possibilities for ω ≥1 ). Then ω is e.c.u. random. Since ω 0 is not computably random, neither is ω.
Furthermore, ω ≥1 is Schnorr random uniformly relative to ω 0 , which in turn is Schnorr random. Recall that van Lambalgen's theorem for Schnorr randomness states that for α, β ∈ 2 N , α ⊕ β is Schnorr random if and only if α is Schnorr random and β is Schnorr random uniformly relative to α [16,14]. Hence ω is Schnorr random.
Then ω (0) is not computably random, and so there is a martingale (M n ) on 2 N such that lim sup n M n (ω (0) ) = ∞. Convert this to a martingale (N n ) on 2 N×N using N n (ξ) = M n (ξ (0) ). Therefore lim sup n N n (ω) = ∞ and ω is not Doob random.

5.4.
In the context of Schnorr randomness. As we saw in Theorem 5.8, the real ω is Doob random if for each computable f , ω B f is uniformly computably random relative to ω A f . For fixed f , we may call ω f -Doob random in this case, and speak of a test for Doob randomness parametrized by f . We shall prove that for each fixed f , there exists an f -Doob random, Schnorr random ω that is not e.c.u. random. However, the stronger statement of Conjecture 5.16 would more properly complete Theorem 5.14: Conjecture 5.16. There is a Doob random, Schnorr random ω that is not e.c.u. random.
We will need some lemmas.
Proposition 5.17. For every α ∈ 2 N , there is a β ∈ 2 N which is Schnorr random uniformly relative to α, but not computably random uniformly relative to α. (We can even show that β is not Schnorr random relative to α in the usual sense.) Proof. Relativize the construction and proof of Wang [24]. Namely, his argument naturally relativizes to give a class of martingales F α and a class of sequences ξ α such that the following holds. (We use the terminology and notation in his paper.) (1) F α is uniformly computable from the oracle α.
Proof. Let X be Schnorr random. Then by [3,Theorem 9, direction (ii)-implies-(i)], some tail of X belongs to C, and we are done.
The following is a Schnorr randomness version of Miyabe's theorem extending van Lambalgen's theorem to infinitely many reals [15]. N . If ω n is Schnorr random uniformly relative to ω <n for all n, then there is ξ ∈ (2 N ) N such that ξ is Schnorr random and for each n, ξ n is a tail of ω n . (In other words, there is a k n such that ξ n = α ≥kn for α = ω n .) Proof. Given a set U ⊆ (2 N ) N and ξ <n in (2 N ) n , we will use the notation We will use angle brackets to denote singleton sequences. For example, for α ∈ 2 N , The set U |ξ <n can be read as "U given the initial segment ξ <n " and its measure has the convenient notation P(U |ξ <n ).
Enumerate (noneffectively) all the Schnorr tests (U s n ) on (2 N ) N . Recall each U s n is effectively open uniformly in n and µ(U s n ) is computable uniformly in n and at most 2 −n . Fix ω as in the statement of the proposition. We closely follow the construction in [1, Theorem 13]. At stage s we construct the rows ξ s ∈ 2 N of ξ (along with the effectively open helper sets V s , W s ) to satisfy these requirements: For the sth Schnorr test (U s n ), we have V s = U s n for some n and P(V s |ξ <s ) ≤ 2 −(2s+1) .
By R s 2 , ξ / ∈ i V i . For if ξ ∈ V i for some i, then since V i is open, there is some s for which all sequences extending ξ <s in V i . Since s can be arbitrary large, assume s > i. Then by R s 2 , 1 = P(V i |ξ <s ) ≤ P(W s−1 |ξ <s ) ≤ 1 − 2 −(2s+2) . A contradiction. Therefore, ξ is Schnorr random, and R s 3 is the desired tail property. Construction at stage s: Assume ξ <s = (ξ 0 , . . . , ξ s−1 ) has been constructed as well as W s−1 = i<s V i (for s = 0 let ξ <0 be the empty string and W −1 = ∅). Assume they satisfy R i 1 , R i 2 , and R i 3 for i < s. Let (U s n ) be the sth Schnorr test. For any Schnorr random α, it follows from the proof of van Lambalgen's theorem for uniformly relative Schnorr randomness in [14] that . This is a nonnegative lower semicomputable function on 2 N × (2 N ) N with a computable integral. Then [14, Proof of Theorem 4.1] shows that for any Schnorr random α, the function β → t(α, β) has a finite integral. For our t, this integral is n P(U s n | α ).) Similarly, n P(U s n |ξ <s ) < ∞. Hence there is some n such that P(U s n |ξ <s ) ≤ 2 −(2s+1) . Let V s = U s n , thereby satisfying requirement R s 1 . Recall W s from the requirements. Since it is a finite union of Σ 0 1 sets of computable measure, W s also is a Σ 0 1 set of computable measure. Define is chosen as follows so that the effectively closed set C has computable measure. To choose c, use Lemma 4.13 and the function f (α) := P(W s |ξ <s ⌢ α ). It remains to show that f is L 1 -computable. We do this by showing f is a nonnegative lower semicomputable function with computable integral [14]. First, f is lower semicomputable since the measures of Σ 0 1 sets are lower semicomputable. Second, we have f (α) dα = P(W s |ξ <s ). To compute P(W s |ξ <s ), we will use [17, Corollary 6.10]. Namely, the value of a nonnegative lower semicomputable function, in this case g(ψ <s ) = P(W s |ψ <s ), with a computable integral, g(ψ) dψ = P(W s ), is computable when evaluated at a Schnorr random point, ψ <s = ξ <s .
By Markov's inequality, Therefore, P(C) > 0 and we can apply Lemma 5.18 to find some α ∈ C such that α is a tail of ω s . Let ξ s = α, thereby satisfying requirement R s 3 . Finally, by the definition of C and the choice of c we have P(W s | ξ <s+1 ) ≤ 1 − 2 −(2s+2) , satisfying R s 2 .

5.4.2.
Schnorr randomness and f -Doob randomness does not imply e.c.u. randomness. Theorem 5.20. Fix a computable function f . There exists a Schnorr random ω which is f -Doob random but not e.c.u. random.
Proof. Fix f and give A f and B f a computable ordering. By Propositions 5.17 and 5.19, there is a Schnorr random ξ ∈ 2 N×N such that for each n, ξ n is Schnorr random uniformly relative to ξ <n , but ξ n is not computably random uniformly relative to ξ <n . Let α ∈ 2 N be Martin-Löf random relative to ξ. Let ω be defined by • ω B f is the bits of α put into the positions in B f using the ordering on B f . Note that each ω n is Schnorr random, but not computably random. Then • ω is Schnorr random: Since ξ is Schnorr random, so is ξ A f = ω A f . Since α is Martin-Löf random relative to ξ, α is uniformly Schnorr random relative to ξ. Therefore ω B f is uniformly Schnorr random relative to ξ A f = ω A f . By van Lambalgen's theorem for uniform Schnorr randomness [14], ω is Schnorr random. • ω is not e.c.u. random: By Corollary 5.12, if ω ≥n is computably random uniformly relative to ω <n , then ω n would be computably random relative to ω <n which it is not.
• ω is f -Doob random using the characterization in Theorem 5.8. By the choice of α, we have that ω B f is Martin-Löf random relative to ω A f . Then, ω B f is also computably random uniformly relative to ω A f (see [16,14]).

Doob random paths of Brownian motion
In this section we work with the space Ω = {f ∈ C([0, ∞)) : f (0) = 0}, where P is the Wiener measure, i.e. the probability measure of Brownian motion. The martingale convergence theorem for Brownian motion goes back to Doob [5] and is discussed in Appendix A. We will use the variables W , X, Y and Z for elements of Ω. Let W t denote the value of W at time t. Similar to the previous sections, we will use W ≤s to denote W restricted to [0, s]. Also, W ≥s denotes the function t → W s+t − W s (hence W ≥s ∈ Ω). Assume W, X ∈ Ω. Then define concatenation (at time s) as The concatenated path W ≤s ⌢ X is computable from W ≤s , s, and X. 13 Notice that W ≤s ⌢ W ≥s = W .
Our definition of conditional expectation relies on these three properties of (Ω, P). (The second two properties, which come from the definition of Brownian motion (Defintion A.8), are needed to establish that the properties of Remark 3.2 still hold.) • (Ω, P) is a computable probability space. 13 Since C([0, s]) may not be a computable metric space, we say that something is computable from W ≤s and s if it is computable from the function X ∈ C([0, 1]) given by Xt = Ws·t. Similarly, we can say that W ≤s is computable from s and W , since the corresponding X ∈ C([0, 1]) is computable uniformly from s and W .
• (Ω, P) has independent increments, that is the map W → W ≥t is independent of the map W → W ≤t . Since (Ω, P) is a computable probability space, if f : Ω → R is a computable function and f ∞ ≤ C then E(f ) is computable uniformly from f and C [11,Corollary 4.3.2]. Conditional expectation can be defined similarly to what was done in previous sections, as follows.
Definition 6.1. Given an integrable function f : Ω → R define E t (f ) as the function given by Notice, if f is computable and f ∞ ≤ C then E t (f )(W ) is computable uniformly from t, f , W ≤t , and C. (See Remark 6.2 for why the bound C is needed.) Also, if f is a.e. computable and f ∞ ≤ C, then W ≤t → E t (f )(W ) is an a.e. computable function uniformly from t, f , and C. The properties of Remark 3.2 still hold.
Remark 6.2. Unlike the situation in Section 5, here Ω is not compact. Hence a continuous function f may be unbounded. One can show that E t (f )(W ) is not computable from t, f and W , even when f is integrable. We shall now present a function f : where α(y) = e y 2 /2 .
Let n(x) = e −x 2 /2 / √ 2π, the p.d.f. of a standard N (0, 1) random variable. 14 Note that g(x, y)n(x)n(y) = 1 2π exp −(xα(y)) 2 2 and g(0, y)n(y) = 1 √ 2π , Treating W as a random variable we have that W 1 and W 2 − W 1 are independent random variables each with an N (0, 1) normal distribution (Definition A.8). Thus And conditioning on W 1 = 0, we have Definition 6.3. Say a sequence (M t ) t∈[0,∞) of real-valued functions on Ω is a martingale if both of the following hold almost surely.
Say that (M t ) t∈[0,∞) is a computable martingale if, furthermore, it is computably adapted, that is M t (W ) is uniformly computable from t and W ≤t . Let S = {s n } n∈N be an unbounded set given by a computable sequence of nonnegative computable reals, for example N or Q + . Define S-indexed martingales (M t ) t∈S similarly, that is, restrict the martingale definition to the indices t ∈ S. An S-indexed computable martingale, (respectively, an S-indexed a.e. computable martingale) is an S-indexed martingale such that (M sn ) n∈N is a computable sequence of computable functions (respectively, a.e. computable functions). Lemma 6.5. Consider an S-indexed computable martingale (M t ) t∈S such that there is a computable bound on the growth d : S → R, that is to say, d(s n ) is computable uniformly from n and |M s (W )| ≤ d(s) for all W ∈ Ω and s ∈ S. Then (M t ) t∈S uniquely extends to a computable martingale (N t ) t∈[0,∞) . The latter is computable uniformly from the former martingale and the function d. 15 Proof. If there is such a martingale (N t ) extending (M s ), then for all s ∈ S and all 0 < t < s it must satisfy It remains to show that the martingale (N t ) is a computable martingale. We show N t (W ) is uniformly computable from t and W ≤t as follows. Fix a Cauchy-name for t and use it to effectively find some n such that s n > t (where S = {s n } n∈N ). Recall that N t (W ) = E t M sn (W ), and that this conditional expectation is uniformly computable from t, W t , M sn and the bound d(s n ). Definition 6.6. Let W ∈ Ω. Say that W is Doob random (respectively, S-Doob random) if (M t (W )) converges as t → ∞ for all nonnegative computable martingales (M t ) t∈[0,∞) (respectively, (M t ) t∈S ).
The definition of Schnorr randomness naturally extends to any computable probability space (see for example [9]). Theorem 6.7. Let W ∈ Ω be Schnorr random. Let S = {s 0 < s 1 < . . . } be the set formed by a computable, increasing, unbounded sequence of computable reals. Then the following are equivalent: (1) (M s (W )) diverges as s → ∞ for some computable nonnegative martingale (M s ) s∈S and some computable d : (3) (M s (W )) diverges as s → ∞ for some a.e. computable nonnegative martingale (M s ) s∈S . Proof.
(2) ⇒ (3): This is immediate from the fact that a computable martingale is a.e. computable.
We need the following lemma about a.e. computable martingales.
(1) Let {q i } be a computable enumeration of the rationals. The doubly indexed sequence of local minimums (min t∈[q i ,q j ] M t (W )) i∈N,j∈N is a.e. computable from W . The same is true for the sequence of local maximums. (2) From a name for (M t ), we can compute a dense sequence of reals {a n } which are almost-surely not local maximums or local minimums of the paths in (M t ). That is for all i and j, we have P W a n = min M t (W ) = P W a n = max M t (W ) = 0.
(3) Let a n be from part (2). Let τ : Ω → [0, ∞] be an a.e. computable function. 16 Further assume M τ (W ) (W ) almost-surely does not equal a n . Then let σ : Ω → [0, ∞] be the first hitting time after τ (W ), that is This σ is an a.e. computable function. (3) It is enough to compute σ(W ) from the path f := t → M t (W ) and from the starting point t 0 := τ (W ) for a.e. W . We assumed with measure one that f (t 0 ) = a n . Without loss of generality, f (t 0 ) > a n . Using part (1), enumerate all rational intervals [q i , q j ] containing t 0 such that min t∈[q i ,q j ] f (t) > a n . Then τ (W ) is the supremum of the left endpoints of these intervals. Hence τ (W ) is a.e. lower semicomputable. We show the time τ (W ) is also upper semicomputable as follows. By part (2), we may assume a n is not a local maximum of f . As before, enumerate all rational intervals [q i , q j ] such that q i > t 0 and max t∈[q i ,q j ] f (t) < a n . Then τ (W ) is the infimum of the left endpoints of these intervals since a n is not a local maximum. (It is possible that τ (W ) is the infimum of the empty set, in which case τ (W ) = ∞.) Hence τ (W ) is a.e. upper semicomputable, and therefore, a.e computable.
Theorem 6.9. Let W ∈ Ω be Schnorr random. Let S be an enumerable unbounded set of nonnegative computable reals. Then the following are equivalent: (1) W is not Doob random.
(2) ⇒ (3): The proof is similar to the "upcrossing method" used in Theorem 4.8. Assume a and b are such that they are in the set {a n } from part (2) of Lemma 6.8 and such that lim inf t M t (W ) ≤ a < b ≤ lim sup t M t (W ). Define the upcrossing and downcrossing times as before: These times are a.e. computable by part (3) of Lemma 6.8. Also, since the paths of (M t ) are almost-surely continuous, we have that lim k σ down k = lim k σ up k = ∞ almost-surely. Now define the new martingale as follows. Let N 0 = M 0 and .
Similarly to Theorem 4.8, this is a well-defined martingale. Moreover, the paths t → N t (X) are almost-surely computable from X, since σ up k (X), σ down k (X), and t → M t (X) are almostsurely computable from X. (Notice the paths are continuous, which lets us compute N t (X) when t is on the boundary of the upcrossing/downcrossing intervals.) Hence, (N t ) is an a.e. computable martingale. Similarly to before, we have lim sup t→∞ N t (W ) = ∞.
(3) ⇒ (4): Follow the "savings property method" used in Theorem 4.8 with the same adaptions to the continuous setting that we made in (2) ⇒ (3) of this theorem.
(4) ⇒ (5): Because lim inf t→∞ M t (W ) = ∞, it is enough to restrict (M t ) to indices from the unbounded set S.
(5) ⇒ (6): Choose an unbounded increasing subsequence S ′ = {s 0 < s 1 < . . . } ⊆ S. By Theorem 6.7, we can find a computable S ′ -indexed martingale (N s ) s∈S ′ with some computable d such that M s ≤ d(s) for all s ∈ S ′ and such that lim inf s→∞ N s (W ) = ∞. Then extend (N s ) to an S-indexed martingale by using the proof of Lemma 6.5.
We extend B to an a.e. computable isomorphism B : (2 N ) N → Ω as follows. Let us denote concatenation of functions f ∈ C[0, a] and g ∈ C[0, b] by ⌢ , i.e., We note that this makes ⌢ associative. Let  We have already mentioned Schnorr randomness on (Ω, P). For computable randomness on (Ω, P), we will use the definition in [20]. Say that W is e.c.u. random if there is an n ∈ N such that B −1 (W ≥n ) is computably random uniformly relative to B −1 (W ≤n ). Lemma 6.11. Let W ∈ Ω be Schnorr random. Then ω = B −1 (W ) is Schnorr random. Further W is, respectively, computably random, e.c.u. random, or Doob random, if and only if ω = B −1 (W ) is.
Proof. For Schnorr and computable randomness, this follows from the fact that a.e. computable isomorphisms preserve Schnorr and computable randomness [20]. For e.c.u. randomness, this follows from the definition. For Doob randomness, by Theorem 6.9, it is enough to replace Doob randomness with N-Doob randomness. We will prove one direction. The other is the same. Assume W is not N-Doob random. Then there is a martingale (M n ) n∈N on Ω such that (M n (W )) diverges as n → ∞. Define a new martingale (N n ) on (2 N ) N by N n (ξ) = M n (B(ξ)). Since B is a.e.
computable, so is (N n ). It remains to show it is a martingale. N n (ξ) is a.e. computable from B(ξ) ≤n = B(ξ <n ) which is computable from ξ <n . Also for m ≤ n, which completes the proof.
Theorem 6.12. For a W ∈ Ω, consider the the following: (1) W is computably random.
(3) W is Doob random and Schnorr random.
Proof. Doob ⇒ Schnorr: Let 0 be the constant zero function. Let Y = 0 ≤1 ⌢ X ≥1 where X ∈ Ω is Doob random. Clearly, Y is not Schnorr random, but we claim it is Doob random. Assume not. Then by Theorem 6.9 there is a computable martingale (M n ) n∈N,n≥1 such that lim n M n (Y ) = ∞. Define a new martingale N n (W ) = M n (0 ≤1 ⌢ W ≥1 ). To see that this is a martingale, for m < n, Then lim n N n (X) = ∞ which contradicts that X is Doob random. Schnorr ⇒ Doob: This is (4) ⇒ (3) of Theorem 6.12.
future given the past is the same as the current capital.) Doob's martingale convergence theorem is as follows.
Notice if (M n ) is a nonnegative martingale, then E|M n | = EM n = EM 0 , and therefore the convergence theorem applies.
Given a random variable (a measurable function) X : Ω → X (where X is a Polish space), denote E(f | X) = E(f | σ(X)) where σ(X) is the smallest σ-algebra containing the sets X −1 (B) for all Borel sets B ⊆ X . The distribution P X of X is the push-forward measure on the space X given by P X (A) = P(X −1 (A)). Two random variables, X and Y , are said to be independent if their joint distribution P (X,Y ) (i.e., the distribution of the pair (X, Y )) is equal to the product measure P X × P Y .
We will use the following lemma to give a more explicit computation of the conditional expectation operator, arriving at the definitions used in this paper. . Let X and Y be independent random variables. Let ϕ be a function with E|ϕ(X, Y )| < ∞ and let g(x) = E(ϕ(x, Y )). Then E(ϕ(X, Y ) | X) = g(X) a.s.
The main idea is that X encodes the past, and Y encodes the future. An integrable random variable f can be expressed as a function of the past and the future, ϕ(X, Y ). If the past X and future Y are independent (as is the case with repeated coin-flipping), then Lemma A.3 gives us an explicit formula for the conditional expectation.
Then X n and Y n are independent, and P Yn = P. Given an integrable f , let ϕ(x, y) = f (x ⌢ y).
Let F n be the augmentation of σ(X n ). Then (F) n∈N is a filtration since σ(Z 0 , . . . , Z n−1 ) ⊆ σ(Z 0 , . . . , Z n−1 , Z n ). An integrable function f is F n -measurable if and only if for a.e. α the value of f (α) depends only on X n (α) = α <n . Therefore, (M n ) is a martingale in the sense of Definition 4.2 exactly if it is a martingale adapted to the filtration F n . A similar result holds for the martingales on 2 N that were introduced in Section 3.
More generally, given a partial order (J, ≤), a filtration (F j ) j∈J is a J-indexed family of σ-algebras F j ⊆ B such that F i ⊆ F j whenever i ≤ j. A martingale (M j ) j∈J adapted to the filtration (F j ) j∈J is a sequence of integrable functions M j : Ω → R such that M j is F j measurable and E(M j | F i ) = M i a.s. whenever i ≤ j.