How powerful are integer-valued martingales?

DOI10.1007/s00224-011-9362-3zbMath1283.68171arXiv1004.0838OpenAlexW2484159992MaRDI 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 measurescomputability theorygenericityalgorithmic randomnessmartingale processinteger-valued martingalesnon-monotonic betting strategiesunpredicatability paradigm

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item