How powerful are integer-valued martingales?

DOI10.1007/978-3-642-13962-8_7zbMATH Open1283.68171arXiv1004.0838OpenAlexW2484159992MaRDI QIDQ693070FDOQ693070

Authors: Laurent Bienvenu, Frank Stephan, Jason Teutsch 

Publication date: 7 December 2012

Published in: Theory of Computing Systems, Programs, Proofs, Processes (Search for Journal in Brave)

Abstract: In the theory of algorithmic randomness, one of the central notions is that of computable randomness. An infinite binary sequence X is computably random if no recursive martingale (strategy) can win an infinite amount of money by betting on the values of the bits of X. In the classical model, the martingales considered are real-valued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integer-valued martingales are considered, and we study the class of random sequences induced by this model.

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

Recommendations

• How powerful are integer-valued martingales?
• Effective martingales with restricted wagers
• Integer valued betting strategies and Turing degrees
• scientific article; zbMATH DE number 2086651
• Lowness for integer-valued randomness

zbMATH Keywords

martingale processgenericityalgorithmic randomnesscomputability theoryBernoulli measuresinteger-valued martingalesnon-monotonic betting strategiesunpredicatability paradigm

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• The definition of random sequences
• Weighted sums of certain dependent random variables
• Kolmogorov-Loveland randomness and stochasticity
• Title not available (Why is that?)
• A unified approach to the definition of random sequences
• Mathematical metaphysics of randomness
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Title not available (Why is that?)
• A separation of two randomness concepts
• How to build a probability-free casino
• On equivalence of infinite product measures
• On Kurtz randomness
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructive equivalence relations on computable probability measures
• Why computational complexity requires stricter martingales

Cited In (15)

• Granularity of wagers in games and the possibility of saving
• A savings paradox for integer-valued gambling strategies
• Integer valued betting strategies and Turing degrees
• Things that can be made into themselves
• Why computational complexity requires stricter martingales
• Computable randomness is about more than probabilities
• Separations of non-monotonic randomness notions
• Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
• How to build a probability-free casino
• Lowness for integer-valued randomness
• How powerful are integer-valued martingales?
• How to gamble against all odds
• Effective martingales with restricted wagers
• Title not available (Why is that?)
• Computability theory. Abstracts from the workshop held January 7--13, 2018

This page was built for publication: How powerful are integer-valued martingales?

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