Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 67, Issue 11, Pages 7568-7578Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3109779
Keywords
Kolmogorov complexity; statistics
Ask authors/readers for more resources
There is no computable, randomized method to produce a sample that does not contain outliers of a given computable probability measure P. Additionally, the minimum length of a program that computes a complete extension of a binary predicate gamma is bounded by the size of the domain of gamma and the information it has with the halting sequence.
Given a computable probability measure P over natural numbers or infinite binary sequences, there is no computable, randomized method that can produce an arbitrarily large sample such that none of its members are outliers of P. In addition, given a binary predicate gamma, the length of the smallest program that computes a complete extension of gamma is less than the size of the domain of gamma plus the amount of information that gamma has with the halting sequence.
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