• [36] Let the information distance for multisets ID(X) be defined as in Definition 8.5.1 on page 698 either with the plain Kolmogorov complexity or with the prefix Kolmogorov complexity. Show that the maximal overlap, metricity, universality, and minimal overlap properties holding for the information distance between two strings (Section 8.3 on page 663) generalize mutatis mutandis to the information distance for multisets. The subadditive property does not hold.

Comments. Source: using prefix Kolmogorov complexity [P.M.B. Vit´anyi, Ibid.]. Hint: for maximum overlap it can be shown that the information to go from any x0 ∈ X to X can be divided in two parts: a single string of length k = minx∈X{C(X|x, d(X))} and a string of length at most ID(X)−k possibly depending on x0, everything up to an additive logarithmic term. For metricity one shows that ID(X) is a metric up to an additive logarithmic term in the metric inequalities. A metric d for multisets is a function from multisets to the real numbers satisfying

(i) positive definitenes: d(X) = 0 if all members of X are equal and d(X) > 0 otherwise; (ii) symmetry: d(X) is invariant under permutation of X; (iii) triangle inequality: d(X  Y ) ≤ d(X  Z) + d(Z  Y ) where X, Y, Z are multisets of strings. Universality follows from an extension of the argument used in the two-string case as does minimal overlap. The function ID is not subaddtive and one can show that ID(X) + ID(Y )
can be greater, equal, or smaller than ID(X  Y ) up to a logarithmic additive term for different multisets X and Y .