Back to search

Boston University

Some results on Kolmogorov-Loveland randomness

Abstract

dc:description.abstract

Whether Kolmogorov-Loveland randomness is equal to the Martin-Löf randomness is a well known open question in the field of algorithmic information theory. Randomness of infinite binary sequences can be defined in terms of betting strategies, a string is non-random if a computable betting strategy wins unbounded capital by successive betting on the sequence. For Martin-Löf randomness, a betting strategy makes a bet by splitting a set of sequences into any two clopen sets, and placing a portion of capital on one of them as a wager. Kolmogorov-Loveland betting strategies are more restricted, they bet on a value of the bit at some position they choose, which splits a set of sequences into two clopen sets, the sequences that have 0 at the chosen position and the sequences that have 1. In this thesis we consider betting strategies that when making a bet are restricted to split a set of sequences into two sets of equal uniform Lebesgue measure. We call this generalization of Kolmogorov-Loveland betting strategies the half-betting strategies. We show that there is a pair of such betting strategies such that for every non-Martin-Löf random sequence one of them wins unbounded capital (the pair is universal). Next, we define a finite betting game where the betting strategies bet on finite binary strings, and show that in this game Kolmogorov-Loveland betting strategies cannot increase capital by more than an arbitrary small amount on all strings on which the unrestricted betting strategy achieves arbitrary large capital. We also look at another relaxation of Kolmogorov-Loveland betting, where a betting strategy is allowed to access bits of the sequence within a set of positions a bounded number of times. We show that if this bound is less than ℓ - log ℓ for the first ℓ positions then a pair of such betting strategies cannot be universal. Furthermore, we show that, at least for some universal betting strategies, this bound is exponential.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Petrovic, Tomislav
Advisors dc:contributor.advisor
  • Gacs, Peter
  • Bauwens, Bruno F.

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/45309

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Petrovic, Tomislav. Some results on Kolmogorov-Loveland randomness. doctoral thesis, Boston University, 2022. https://hdl.handle.net/2144/45309