Exact Expression For Information Distance

DOI10.1109/TIT.2017.2686883MaRDI QIDQ5369833zbMATH OpenFDO

Authors Paul M. B. Vitányi

Publication date 19 October 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.7328

Mathematics Subject Classification ID

Information theory (general) (94A15) Measures of information, entropy (94A17)

Abstract: Information distance can be defined not only between two strings but also in a finite multiset of strings of cardinality greater than two. We give an elementary proof for expressing the information distance in terms of plain Kolmogorov complexity. It is exact since for each cardinality of the multiset the lower bound for some multiset equals the upper bound for all multisets up to a constant additive term.

Cited in

(2)

• Correct estimate of information distance
• Information Distance in Multiples

This page was built for publication: Exact Expression For Information Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369833)