Effective martingales with restricted wagers

DOI10.1016/J.IC.2015.10.001MaRDI QIDQ897654zbMATHOpenAlexFDO

Authors Ron Peretz

Publication date 7 December 2015

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

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)

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.

Recommendations

• Uniform van Lambalgen's theorem fails for computable randomness
• Probabilistic Algorithmic Randomness
• How to gamble against all odds

Cites work

• scientific article; zbMATH DE number 1232374 (Why is no real title available?)
• A savings paradox for integer-valued gambling strategies
• A unified approach to the definition of random sequences
• Algorithmic randomness and complexity.
• Computability and randomness
• How to build a probability-free casino
• How to gamble against all odds

Cited in

(10)

• How to gamble against all odds
• A computable analysis of majorizing martingales
• Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
• Why computational complexity requires stricter martingales
• scientific article; zbMATH DE number 2086651 (Why is no real title available?)
• Lowness for integer-valued randomness
• Algorithmic randomness and splitting of supermartingales
• Computable randomness is about more than probabilities
• How to build a probability-free casino
• Granularity of wagers in games and the possibility of saving

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)