2016/08/29 by Gleb Novikov, Novikov, Gleb
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Evolutionary Algorithms and Applications #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.1608.08246
openalex publication_date 2016/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The notion of random sequence was introduced by Martin-Loef in 1966. At the same time he defined the so-called randomness deficiency function that shows how close are random sequences to non-random (in some natural sense). Other deficiency functions can be obtained from the Levin-Schnorr theorem, that describes randomness in terms of Kolmogorov complexity. The difference between all of these deficiencies is bounded by a logarithmic term. In this paper we show that the difference between some deficiencies can be as large as possible.