Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity

Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entrop...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2010-04, Vol.46 (3), p.598-617
Main Author: Bienvenu, Laurent
Format: Article
Language:English
Subjects:
Algorithms
Bias
Binary system
Codes
Computer Science
Mathematical analysis
Random variables
Stochastic models
Studies
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:Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ . We also prove an analogous result for finite strings.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-009-9232-4