Computable randomness and betting for computable probability spaces
From MaRDI portal
Publication:2827949
DOI10.1002/MALQ.201200089zbMATH Open1364.03064arXiv1203.5535OpenAlexW2963803153MaRDI QIDQ2827949FDOQ2827949
Authors: Jason Rute 
Publication date: 24 October 2016
Published in: Mathematical Logic Quarterly (MLQ) (Search for Journal in Brave)
Abstract: Unlike Martin-L"of randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting "bit-wise" definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness---endomorphism randomness---which the author hopes will shed light on the open question of whether Kolmogorov-Loveland randomness is equivalent to Martin-L"of randomness. The last section contains ideas for future research.
Full work available at URL: https://arxiv.org/abs/1203.5535
Recommendations
- Randomness on computable probability spaces -- a dynamical point of view
- Randomness on computable probability spaces -- a dynamical point of view
- Computable randomness is about more than probabilities
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Probabilistic Algorithmic Randomness
Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Foundations of probability theory (60A99)
Cites Work
- Algorithmic randomness and complexity.
- Probability with Martingales
- Title not available (Why is that?)
- Ergodic theorems for individual random sequences
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Algorithmic tests and randomness with respect to a class of measures
- Kolmogorov-Loveland randomness and stochasticity
- Truth-table Schnorr randomness and truth-table reducible randomness
- Exact Expressions for Some Randomness Tests
- Title not available (Why is that?)
- Randomness on computable probability spaces -- a dynamical point of view
- Computability and Randomness
- A unified approach to the definition of random sequences
- Mathematical metaphysics of randomness
- Strong reductions in effective randomness
- Some results on effective randomness
- Schnorr randomness and the Lebesgue differentiation theorem
- The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
- Title not available (Why is that?)
- Algorithmic Randomness of Closed Sets
- Uniform test of algorithmic randomness over a general space
- Effective dimension of points visited by Brownian motion
- \(K\)-triviality in computable metric spaces
- Degrees of unsolvability of continuous functions
- Constructive equivalence relations on computable probability measures
- Why computational complexity requires stricter martingales
- Randomness and differentiability
- Title not available (Why is that?)
- Admissible representations for probability measures
- Computable de Finetti measures
- Effective metric spaces and representations of the reals.
- Comparing notions of randomness
- On Schnorr and computable randomness, martingales, and machines
- Title not available (Why is that?)
- Random elements in effective topological spaces with measure.
- General random sequences and learnable sequences
- Title not available (Why is that?)
- Uniform distribution and algorithmic randomness
- Algorithmic randomness over general spaces
- Separations of non-monotonic randomness notions
Cited In (18)
- Process and truth-table characterisations of randomness
- Computability on random events and variables in a computable probability space
- Integer valued betting strategies and Turing degrees
- Effective notions of weak convergence of measures on the real line
- Notions of Probabilistic Computability on Represented Spaces
- Constructive Equivalence Relations on Computable Probability Measures
- A computational definition of financial randomness
- Randomness and differentiability of convex functions
- Randomness on computable probability spaces -- a dynamical point of view
- When does randomness come from randomness?
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Title not available (Why is that?)
- Computable randomness is about more than probabilities
- Computable Measure Theory and Algorithmic Randomness
- Strong reductions in effective randomness
- A universal pair of 1/2-betting strategies
- Randomness on computable probability spaces -- a dynamical point of view
- Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
This page was built for publication: Computable randomness and betting for computable probability spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827949)
