A Rigorous Take on Randomness: Defining 1-Randomness using Complexity, Measure Theory, and Martingales

By flipping a coin repeatedly and recording the result, we can create a sequence that intuitively is random. This paper presents a formal definition of 1-randomness widely (but not universally) thought to capture this informal notion. The attempt builds on the success and spirit of work from the 20th century that formalized the notion of computability with Turing machines. We will begin by presenting some of the characteristics of Turing machines. With that background, we will first use universal prefix-free Kolmogorov complexity to characterize randomness. The exploration of complexity will involve a thorough proof of the KC Theorem and an introduction to information content measures. Next, we will approach randomness using measure theory together with Σ 01 classes. And third, we will characterize randomness using left computably enumerable functions called martingales and supermartingales. Finally, we will prove that each of these characterizations is equivalent; i.e., the same sequences are random according to each of them