Paperlane

no. 2 · Monday 26 October 2026

The universal measure of nonstochastic objects

Vladimir Vovk

math.LO · v3 · 37 pp

Abstract

The usual settings for discussing the notion of stochastic objects are very different from Kolmogorov's original structure-free setting, in which there is no predefined external structure on the objects (such as the lengths of binary strings). A natural modification of stochasticity, obtained by replacing finite sets as models with probability measures, is quasi-stochasticity. The structure-free setting is common in studies of quasi-stochasticity, and known results show that the universal machine generates non-quasi-stochastic objects with exponentially small probability. This paper shows that, on the other hand, the universal machine generates nonstochastic objects surprisingly often. It also systematically explores numerous connections between stochasticity and quasi-stochasticity in the structure-free setting. In particular, the definition of quasi-stochasticity can be modified in a natural way modelled on Kolmogorov's definition so that non-quasi-stochastic objects are produced as often as nonstochastic ones; the results for this modification imply all the results of this paper showing that nonstochastic objects are frequent.

comments
37 pages; several new results have been added in this version
fields
Logic
pdf ↗ page arXiv:2608.27098 ↗