• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Some results on Kolmogorov-Loveland randomness

Petrovic, Tomislav 03 November 2022 (has links)
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.

Page generated in 0.0866 seconds