Topics in Algorithmic Randomness and Effective Probability

This dissertation contains the results from three related projects, each within the fields of algorithmic randomness and probability theory. The first project we undertake, which can be found in Chapter 2, contains the definition a natural, computable Borel probability measure on the space of Borel probability measures over 2ω that allows us to study algorithmically random measures. The main results here are as follows. Every (algorithmically) random measure is atomless yet mutually singular with respect to the Lebesgue measure. The random reals of a random measure are random for the Lebesgue measure, and every random real for the Lebesgue measure is random for some random measure. However, for a fixed Lebesgue-random real, the set of random measures for which that real is random is small. Relatively random measures, though mutually singular, always share a random real that is in fact computable from the join of the measures. Random measures fail Kolmogorov’s 0-1 law. The shift of a random real for a random measure is no longer random for that measure. In our second project, which makes up Chapter 3, we study algorithmically random closed subsets of 2ω , algorithmically random continuous functions from 2ω to 2ω , and the algorithmically random Borel probability measures on 2ω from Chapter 2, especially the interplay among these three classes of objects. Our main tools are preservation of randomness and its converse, the “no randomness ex nihilo principle,” which together say that given an almost-everywhere defined computable map from 2ω to itself, a real is Martin Lo¨f random for the pushforward measure if and only if its preimage is random with respect to the measure on the domain. These tools allow us to prove new facts, some of which answer previously open questions, and reprove some known results more simply. The main results of Chapter 3 are the following. We answer an open question in [3] by showing that X ⊆ 2ω is a random closed set if and only if it is the set of zeros of a random continuous function on 2ω . As a corollary, we obtain the result that the collection of random continuous functions on 2ω is not closed under composition. We construct a computable measure Q on the space of measures on 2ω such that X ⊆ 2ω is a random closed set if and only if X is the support of a Q-random measure. We also establish a correspondence between random closed sets and the random measures studied in Chapter 2. Lastly, we study the ranges of random continuous functions, showing that the Lebesgue measure of the range of a random continuous function is always strictly between 0 and 1. In Chapter 4 we effectivize a theorem of Erd¨os and R´enyi [11], which says that for c ≥ 1, if a fair coin is used to generate a length-N string of 1’s and −1’s, which are interpreted as gain and loss, then the maximal average gain over lc log NJ-length substrings converges almost surely (in N ) to the same limit α(c). We show that if the 1’s and −1’s are determined by the bits of a Martin Lo¨f random, then the convergence holds.