Algorithmically random closed sets and probability

Algorithmic randomness in Cantor space has recently become the subject of intense study. Originally defined in terms of the fair coin measure, algorithmic randomness has since been extended, for example by Reimann and Slaman, to more general measures. Others have meanwhile developed definitions of algorithmic randomness for different spaces, for example the space of continuous functions on the unit interval (Fouche), more general topological spaces (Hertling and Weihrauch), and the closed subsets of Cantor space (Barmpalias et al., Kjos-Hanssen and Diamondstone). Our work has also been to develop a definition of algorithmically random closed subsets. We take a very different approach, however, from that taken by Barmpalias et al. and Kjos-Hanssen and Diamondstone.

One of the central definitions of algorithmic randomness in Cantor space is Martin-Lof randomness. We use the probability theory of random closed sets (RACS) to prove that Martin-Lof randomness can be defined in the space of closed subsets of any locally compact, Hausdorff, second countable space.

We then explore the Martin-Lof random closed subsets of the natural numbers, Cantor space, and the real numbers under different measures. In the case of the natural numbers we prove that the Martin-Lof random subsets are exactly those with Martin-Lof random characteristic functions. In the case of Cantor space we prove that the definitions of Barmpalias et al. and Kjos-Hanssen and Diamondstone are compatible with our approach. In the case of the real numbers we investigate the Martin-Lof random closed sets under generalized Poisson processes. This leads to a characterization of the Martin-Lof random reals as exactly those reals contained in some Martin-Lof random closed subset.