All Sampling Methods Produce Outliers
Samuel Epstein · IEEE Transactions on Information Theory · 2021
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.