Logic Seminar
Sean Walsh
UCLA
Algorithmic randomness and the weak merging of computable probability measures
Abstract: We characterize Martin-Löf randomness and Schnorr randomness in terms of the merging of opinions, along the lines of the Blackwell-Dubins Theorem. After setting up a general framework for defining notions of merging randomness, we focus on finite horizon events, that is, on weak merging in the sense of Kalai-Lehrer. In contrast to Blackwell-Dubins and Kalai-Lehrer, we consider not only the total variational distance but also the Hellinger distance and the Kullback-Leibler divergence. Our main result is a characterization of Martin-Löf randomness and Schnorr randomness in terms of weak merging and the summable Kullback-Leibler divergence. The main proof idea is that the Kullback-Leibler divergence between μ and ν, at a given stage of the learning process, is exactly the incremental growth, at that stage, of the predictable process of the Doob decomposition of the ν-submartingale L(σ)=−lnμ(σ)ν(σ). These characterizations of algorithmic randomness notions in terms of the Kullback-Leibler divergence can be viewed as global analogues of Vovk's theorem on what transpires locally with individual Martin-Löf μ- and ν-random points and the Hellinger distance between μ,ν. This is joint work with Simon Huttegger (UC Irvine) and Francesca Zaffora Blando (CMU). Preprint at: https://arxiv.org/abs/2504.00440
Tuesday November 25, 2025 at 3:00 PM in 636 SEO