Floris Persiau's PhD thesis on imprecise probabilities in algorithmic randomness

Posted on April 28, 2025 by Floris Persiau (edited by Alexander Erreygers)
[ go back to blog ]

On 13 December 2024, Floris Persiau obtained his doctoral degree after successfully defending his doctoral dissertation entitled “Imprecise probabilities in algorithmic randomness”. He worked on this dissertation under the supervision of Gert de Cooman and Jasper De Bock, on a PhD fellowship from the Research Foundation – Flanders — after an initial year funded by Ghent University’s Special Research Fund. In this post on the SIPTA blog, he treats us to a brief summary of his doctoral research.

Introduction

My PhD research builds upon the foundational work by Gert de Cooman and Jasper De Bock [1], and can be seen as a continued exploration of how to allow for Imprecise probabilities in algorithmic randomness. As a central topic, the field of algorithmic randomness studies what it means for an infinite outcome sequence to be random for an uncertainty model. Assuming that you—the reader—are already familiar with imprecise probabilities, I’ll start by explaining what the answer to that question looks like in a precise-probabilistic context. To set the stage and gain some intuition, let’s consider the prototypical example of an infinite binary sequence that’s generated by flipping a fair coin—which corresponds to probability ½: the infinite binary sequence 0101010… doesn’t seem random at all whereas the sequence 10001011… seems more random. A notion of algorithmic randomness tries to formalise our intuition behind random sequences by defining what it means for an infinite sequence to be random for an uncertainty model. Generally speaking, there are three standard algorithmic randomness paradigms [2]:

1. The incompressibility paradigm: an infinite sequence is incompressible if none of its initial segments can be produced by an algorithm much shorter than that initial segment itself; the alternating sequence 01010101… clearly fails this principle because the whole sequence can be described as `repeatedly print 01’.
2. The unpredictability paradigm: no effective gambling strategy should be able to gain unbounded capital by betting against an unpredictable sequence; the alternating sequence fails this principle since you can get arbitrarily rich by alternatingly betting on the next outcome to be 0 and 1.
3. The measure-theoretic typicality paradigm: a measure-theoretically typical sequence should satisfy all statistical laws that can be effectively specified, that is, a random sequence should not be contained in any effectively specifiable null set; the alternating sequence fails this principle since it is contained in the null set that consists of all infinite sequences that equal 0 (or 1) on odd (or even) positions.

Surprisingly, these three approaches lead to equivalent randomness notions: an infinite binary sequence is incompressible if and only if it’s unpredictable if and only if it’s measure-theoretically typical.

Classically, algorithmic randomness notions don’t only allow one to define the randomness of an infinite binary sequence w.r.t. probability ½. They also allow for (computable) precise forecasting systems, which associate with every possible finite outcome sequence a possibly different probability for the next outcome to be 1. A forecasting system can thus be thought of as representing the consecutive flipping of possibly unfair coins, where the coin at hand depends on the observed finite outcome sequence so far. For those readers who are used to working with probability measures, it’s worth mentioning that every such forecasting system defines a unique probability measure on the elements of the standard Borel (sigma) algebra over the set of all infinite sequences. Vice versa, for every probability measure on this algebra there’s at least one forecasting system that generates it; the connection is one-to-one when restricting attention to positive measures and to forecasting systems that never assign a probability zero. Consequently, forecasting systems are slightly more expressive in this sense, since they provide/contain full conditional information.

It’s a defining characteristic of the field of imprecise probabilities to question whether precise-probabilistic uncertainty models are always sufficient to capture one’s uncertainty, and to put forward alternative and more general uncertainty models. On that account, it’s natural to wonder whether precise-probabilistic uncertainty models always suffice to capture the randomness of an infinite sequence, and to study whether imprecise probabilities can be allowed for in the field of algorithmic randomness.

In 2017, Gert and Jasper provide a first answer to the second question by generalising the unpredictability paradigm to allow for imprecise forecasting systems, which associate with every possible finite outcome sequence a possibly different probability interval for the next outcome to be 1; in the spirit of Bruno de Finetti [3], these probability intervals are equipped with a betting interpretation. Furthermore, they also provide an answer to the first question by showing the existence of infinite sequences that are unpredictable for an imprecise forecasting system, but not for any computable precise one.

Contributions

In 2019, I started my PhD at the Foundations Lab for imprecise probabilities and had the pleasure to continue working on the aforementioned foundational work by Gert and Jasper. Below, I provide a cherrypicked assortment of results that can be found in my thesis.

I generalised the work by Gert and Jasper by moving from binary to arbitrary finite state spaces, and by considering imprecise forecasting systems that take credal sets instead of probability intervals. Besides the betting interpretation that’s adopted in the unpredictability paradigm, I showed that imprecise forecasting systems also entail a sensitivity analysis interpretation: an infinite sequence is unpredictable for an imprecise forecasting system if and only if it’s unpredictable for a compatible precise forecasting system. This result nicely parallels the aforementioned result showing the existence of infinite sequences that are unpredictable for an imprecise forecasting system, but not for any computable precise one; this result is also generalised from binary to arbitrary finite state spaces. Namely, both results imply the existence of infinite sequences whose randomness can be described by either (computable) imprecise forecasting systems or necessarily non-computable precise forecasting systems. Thus, there’s a trade-off between imprecision and computability: if you insist on precise uncertainty models, then you are forced to consider/adopt precise forecasting systems that cannot be described by any finite algorithm, that is, for which there is no finite description.

Together we succeeded at allowing for imprecise forecasting systems in the measure-theoretic typicality paradigm, thereby generalising the original randomness notion by Per Martin-Löf [5]; it’s an open question whether this is also possible in the incompressibility paradigm. When restricting attention to computable forecasting systems that don’t specify probability zero, we showed that the unpredictability and measure-theoretic typicality paradigm lead to equivalent randomness notions: an infinite sequence is unpredictable if and only if it’s measure-theoretically typical; this generalises a classical equivalence result by Claus-Peter Schnorr [6]. Furthermore, restricting attention to computable forecasting systems, I showed that the generalised randomness notion also coincides with Levin’s measure-theoretically typical notion of `uniform randomness’ [7]—which allows testing whether an infinite sequence is random w.r.t. a member of a so-called effectively compact class of probability measures. This provides additional evidence for the naturalness of giving a sensitivity analysis interpretation to imprecise forecasting systems in an algorithmic randomness context, because you can do so both in the unpredictability and the measure-theoretic typicality paradigm.

Besides addressing the issue of whether precise forecasting systems always suffice to capture an infinite sequence’s randomness, I also addressed the issue of whether it’s always opportune to define the randomness of an infinite sequence with respect to a forecasting system, which associates a credal set with every finite outcome sequence that could have been observed instead of merely those that actually have been observed (namely the finite precursors of the infinite sequence whose randomness we are actually considering). Why should the randomness of an infinite outcome sequence depend on forecasts for finite outcome sequences that have never been observed? Building upon the work by Philip Dawid and Vladimir Vovk [8, 9, 10], I addressed this issue by adopting a so-called prequential approach that defines the randomness of an infinite outcome sequence only with respect to the credal sets that are specified along the sequence. I succeeded at doing so both in the unpredictability and measure-theoretic typicality paradigm, showed that both prequential randomness notions coincide, and proved that they also coincide in a specific sense with the previously introduced (more standard) imprecise-probabilistic randomness notions.

All excited after having this small bite? Don’t hesitate to read the whole cake [11], or to reach out to me.

References

[1] Gert de Cooman & Jasper De Bock. Computable randomness is inherently imprecise. In: Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications. Vol. 62. Proceedings of Machine Learning Research. 2017, pp. 133–144

[2] Rodney G. Downey & Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010

[3] Bruno de Finetti. Teoria delle probabilità. Einaudi, 1970

[4] Bruno de Finetti. Theory of Probability: A Critical Introductory Treatment. English translation of [4]. John Wiley & Sons, 2017

[5] Per Martin-Löf. The definition of random sequences. In: Information and Control 9.6 (1966), pp. 602–619

[6] Claus-Peter Schnorr. A unified approach to the definition of random sequences. In: Mathematical Systems Theory 5 (1971), pp. 246–258

[7] Laurent Bienvenu et al. Algorithmic tests and randomness with respect to a class of measures. In: Computing Research Repository 274 (2011), pp. 34–89

[8] A. Philip Dawid. Prequential analysis. In: Encyclopedia of Statistical Sciences. Vol. 1 (update). Wiley-Interscience, 1997, pp. 464–470

[9] A. Philip Dawid & Vladimir G. Vovk. Prequential probability: principles and properties. In: Bernoulli 5 (1999), pp. 125–162

[10] Vladimir G. Vovk & Alexander Shen. Prequential randomness and probability. In: Theoretical Computer Science 411.29 (2010), pp. 2632–2646

[11] Floris Persiau. Imprecise Probabilities in Algorithmic Randomness. PhD thesis. Ghent University, 2024

About the author

After finishing his engineering physics education at Ghent University, Floris Persiau pursued a doctoral degree in engineering mathematics at the same university’s Foundations Lab for imprecise probabilities. His predoctoral research situated in the intersection of two research fields: imprecise probabilities and algorithmic randomness.

Floris is currently a postdoctoral BAEF fellow at Carnegie Mellon University, and his research interests expand to the union of both research fields. He recently finished (i) a joint project with Francesca Zaffora Blando on the characterisation of several canonical precise randomness notions in terms of the stable satisfaction of various minimal randomness properties, and (ii) a joint project with Jasper De Bock and Alexander Erreygers on convergent limit-behaviour of imprecise Markov chains.