How powerful are integer-valued martingales?

DOI10.1007/s00224-011-9362-3zbMath1283.68171arXiv1004.0838MaRDI QIDQ693070

Frank Stephan, Jason Teutsch, Laurent Bienvenu

Publication date: 7 December 2012

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

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

zbMATH Keywords

Bernoulli measures; computability theory; genericity; algorithmic randomness; martingale process; integer-valued martingales; non-monotonic betting strategies; unpredicatability paradigm

Mathematics Subject Classification ID

60G42: Martingales with discrete parameter

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D32: Algorithmic randomness and dimension

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Lowness for integer-valued randomness, Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, How to build a probability-free casino, How to gamble against all odds, Effective martingales with restricted wagers, Computability theory. Abstracts from the workshop held January 7--13, 2018, Granularity of wagers in games and the possibility of saving, A savings paradox for integer-valued gambling strategies, Things that can be made into themselves, Integer valued betting strategies and Turing degrees

Cites Work

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