2022/12/29 by Tomislav Petrović, Petrović, Tomislav
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2212.14279
openalex publication_date 2022/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that a pair of Kolmogorov-Loveland betting strategies cannot win on every non-Martin-Löf random sequence if either of the two following conditions is true: (I) There is an unbounded computable function g such that both betting strategies, when betting on an infinite binary sequence, almost surely, for almost all ℓ, bet on at most ℓ-g(ℓ) positions among the first ℓ positions of the sequence. (II) There is a sublinear function g such that both betting strategies, when betting on an infinite binary sequence, almost surely, for almost all ℓ, bet on at least ℓ-g(ℓ) positions among the first ℓ positions of the sequence.