Title :
Rarity for Semimeasures
Author :
Levin, Leonid A.
Abstract :
The notion of Kolmogorov-Martin-Lof Random sequences is extended from computable to enumerable distributions. This allows definitions of various other properties, such as mutual information in infinite sequences. Enumerable distributions (as well as distributions faced in some finite multi-party settings) are semi measures, handling those requires care.
Keywords :
computability; computational complexity; random sequences; set theory; statistical distributions; Kolmogorov complexity; Kolmogorov-Martin-Lof random sequences; enumerable distributions; finite multiparty settings; infinite sequences; mutual information; probability distribution; semimeasures; Complexity theory; Computer science; Educational institutions; Lattices; Mutual information; Nickel; Probability distribution; complexity;
Conference_Titel :
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
978-1-4673-4383-1
DOI :
10.1109/FOCS.2012.50
