Effective martingales with restricted wagers

DOI10.1016/J.IC.2015.10.001zbMATH Open1332.68098arXiv1301.7465OpenAlexW2963577808MaRDI QIDQ897654FDOQ897654

Ron Peretz

Publication date: 7 December 2015

Published in: Information and Computation (Search for Journal in Brave)

Abstract: The classic model of computable randomness considers martingales that take real or rational values. Recent work by Bienvenu et al. (2012) and Teutsch (2014) shows that fundamental features of the classic model change when the martingales take integer values. We compare the prediction power of martingales whose wagers belong to three different subsets of rational numbers: (a) all rational numbers, (b) rational numbers excluding a punctured neighbourhood of 0, and (c) integers. We also consider three different success criteria: (i) accumulating an infinite amount of money, (ii) consuming an infinite amount of money, and (iii) making the accumulated capital oscillate. The nine combinations of (a)--(c) and (i)--(iii) define nine notions of computable randomness. We provide a complete characterization of the relations between these notions, and show that they form five linearly ordered classes. Our results solve outstanding questions raised in Bienvenu et al. (2012), Teutsch (2014), and Chalcraft et al. (2012), and strengthen existing results.

Full work available at URL: https://arxiv.org/abs/1301.7465

zbMATH Keywords

computable randomness

Mathematics Subject Classification ID

Generalizations of martingales (60G48) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Title not available (Why is that?)
• Algorithmic Randomness and Complexity
• Title not available (Why is that?)
• A unified approach to the definition of random sequences
• A savings paradox for integer-valued gambling strategies
• How to build a probability-free casino
• How powerful are integer-valued martingales?
• How to gamble against all odds

Cited In (5)

• Granularity of wagers in games and the possibility of saving
• Computable randomness is about more than probabilities
• Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
• How to gamble against all odds
• Title not available (Why is that?)

This page was built for publication: Effective martingales with restricted wagers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897654)