Tomáš Gonda

The Glivenko–Cantelli theorem is a uniform version of the strong law of large numbers. It states that for every IID sequence of random variables, the empirical measure converges to the underlying distribution (in the sense of uniform convergence of the CDF). In this work, we provide tools to study such limits of empirical measures in categorical probability. We propose two axioms, namely permutation invariance and empirical adequacy, that a morphism of type X^\mathbbN \to X should satisfy to be interpretable as taking an infinite sequence as input and producing a sample from its empirical measure as output. Since not all sequences have a well-defined empirical measure, such \textitempirical sampling morphisms live in quasi-Markov categories, which, unlike Markov categories, allow for partial morphisms. Given an empirical sampling morphism and a few other properties, we prove representability as well as abstract versions of the de Finetti theorem, the Glivenko–Cantelli theorem and the strong law of large numbers. We provide several concrete constructions of empirical sampling morphisms as partially defined Markov kernels on standard Borel spaces. Instantiating our abstract results then recovers the standard Glivenko–Cantelli theorem and the strong law of large numbers for random variables with finite first moment. Our work thus provides a joint proof of these two theorems in conjunction with the de Finetti theorem from first principles.

We present a novel proof of de Finetti’s Theorem characterizing permutation-invariant probability measures of infinite sequences of variables, so-called exchangeable measures. The proof is phrased in the language of Markov categories, which provide an abstract categorical framework for probability and information flow. The diagrammatic and abstract nature of the arguments makes the proof intuitive and easy to follow. We also show how the usual measure-theoretic version of de Finetti’s Theorem for standard Borel spaces is an instance of this result.

Quantum theory has an epistemic horizon, i.e. exact values cannot be assigned simultaneously to incompatible physical quantities. As shown by Spekkens’ toy theory, positing an epistemic horizon akin to Heisenberg’s uncertainty principle in a classical mechanical setting also leads to a plethora of quantum phenomena. We introduce a deterministic theory - nomic toy theory - in which information gathering agents are explicitly modelled as physical systems. Our main result shows the presence of an epistemic horizon for such agents. They can only simultaneously learn the values of observables whose Poisson bracket vanishes. Therefore, nomic toy theory has incompatible measurements and the complete state of a physical system cannot be known. The best description of a system by an agent is via an epistemic state of Spekkens’ toy theory. Our result reconciles us to measurement uncertainty as an aspect of the inseparability of subjects and objects. Significantly, the claims follow even though nomic toy theory is essentially classical. This work invites further investigations of epistemic horizons, such as the one of (full) quantum theory.

Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.

A central problem in the study of resource theories is to find functions that are nonincreasing under resource conversions - termed monotones - in order to quantify resourcefulness. Various constructions of monotones appear in many different concrete resource theories. How general are these constructions? What are the necessary conditions on a resource theory for a given construction to be applicable? To answer these questions, we introduce a broad scheme for constructing monotones. It involves finding an order-preserving map from the preorder of resources of interest to a distinct preorder for which nontrivial monotones are previously known or can be more easily constructed; these monotones are then pulled back through the map. In one of the two main classes we study, the preorder of resources is mapped to a preorder of sets of resources, where the order relation is set inclusion, such that monotones can be defined via maximizing or minimizing the value of a function within these sets. In the other class, the preorder of resources is mapped to a preorder of tuples of resources, and one pulls back monotones that measure the amount of distinguishability of the different elements of the tuple (hence its information content). Monotones based on contractions arise naturally in the latter class, and, more surprisingly, so do weight and robustness measures. In addition to capturing many standard monotone constructions, our scheme also suggests significant generalizations of these. In order to properly capture the breadth of applicability of our results, we present them within a novel abstract framework for resource theories in which the notion of composition is independent of the types of the resources involved (i.e., whether they are states, channels, combs, etc.).