Premium
Exact Expressions for Some Randomness Tests
Author(s) -
Gács Peter
Publication year - 1980
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
ISBN - 3-540-09118-1
DOI - 10.1002/malq.19800262502
Subject(s) - randomness , citation , computer science , information retrieval , library science , mathematics , statistics
For a computable probability distribution P over the set of infinite binary sequences Martin-Löf defined a test d(x|P) measuring the degree of nonrandomness of the sequence x with respect of P. We give some expressions in terms of Kolmogorov's and other complexities of the initial segments of x whose difference from d(x|P) is bounded by a constant.