Conference paper, presentation, and poster: Computable randomness is inherently imprecise

by gertekoo

Computable randomness is inherently imprecise
Gert de Cooman and Jasper De Bock
Proceedings of Machine Learning Research, vol. 62, pp. 133–144, 2017

A conference version of one of the papers I am perhaps most proud of. Research for this paper started with discussions between Philip Dawid and myself about what prequential interval forecasting would look like, during a joint stay at Durham University in late 2014. Jasper who joined in late 2015, and I wrote an early prequential version of the present paper during a joint research visit to the Universities of Strathclyde and Durham in May 2016, trying to extend results by Volodya Vovk to make them allow for interval forecasts. In an email exchange, Volodya pointed out a number of difficulties with our approach, which we were able to resolve by letting go of its prequential emphasis, at least for the time being. This was done during research visits of mine to Jasper at IDSIA in late 2016 and early 2017.

Abstract: We use the martingale-theoretic approach of game-theoretic probability to incorporate imprecision into the study of randomness. In particular, we define a notion of computable randomness associated with interval, rather than precise, forecasting systems, and study its properties. The richer mathematical structure that thus arises lets us better understand and place existing results for the precise limit. When we focus on constant interval forecasts, we find that every infinite sequence of zeroes and ones has an associated filter of intervals with respect to which it is computably random. It may happen that none of these intervals is precise, which justifies the title of this paper. We illustrate this by showing that computable randomness associated with non-stationary precise forecasting systems can be captured by a stationary interval forecast, which must then be less precise: a gain in model simplicity is thus paid for by a loss in precision.

This paper was presented at the ISIPTA 2017 symposium in Lugano, Switzerland. Besides the actual paper, you can also download our presentation, and our poster.