Journal
THEORETICAL COMPUTER SCIENCE
Volume 341, Issue 1-3, Pages 91-137Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2005.03.054
Keywords
algorithmic information theory; algorithmic entropy; randomness test; Kolmogorov complexity; description complexity
Categories
Ask authors/readers for more resources
The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. These restrictions seem artificial. Some progress has been made to extend the theory to arbitrary Bernoulli distributions (by Martin-Lof) and to arbitrary distributions (by Levin). We recall the main ideas and problems of Levin's theory, and report further progress in the same framework. The issues are the following: Allow non-compact spaces (like the space of continuous functions, underlying the Brownian motion). The uniform test (deficiency of randomness) d p (x) (depending both on the outcome x and the measure P) should be defined in a general and natural way. See which of the old results survive: existence of universal tests, conservation of randomness, expression of tests in terms of description complexity, existence of a universal measure, expression of mutual information as deficiency of independence. The negative of the new randomness test is shown to be a generalization of complexity in continuous spaces; we show that the addition theorem survives. The paper's main contribution is introducing an appropriate framework for studying these questions and related ones (like statistics for a general family of distributions). (c) 2005 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available