How Powerful Are Integer-Valued Martingales?

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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2012-10, Vol.51 (3), p.330-351
Main Authors: Bienvenu, Laurent, Stephan, Frank, Teutsch, Jason
Format: Article
Language:English
Subjects:
Algorithms
Betting
Binary system
Computation
Computer Science
Gambling
Martingales
Numbers
Random variables
Randomized algorithms
Randomness
Real numbers
Recursive
Strategy
Studies
Theory
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-011-9362-3