7
$\begingroup$

In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), K(y) \right \}}$

where $x^*$ is the shortest program outputting $x$. I.e. $K(x) = |x^*|$. In most future papers they drop the star notation, turning the metric into

$\displaystyle d(x,y) = \frac{\max \left \{ K(x|y), K(y|x) \right \}}{\max \left \{ K(x), K(y) \right \}}$

I'm unclear on the relationship between the two quantities $K(x|y^*)$ and $K(x|y)$. It seems to me that the former is quite different from the latter, as the latter is providing both $y$ and $K(y)$ as an input to the program computing $x$. However, I can't find any justification as to how these metrics are the same (up to whatever sufficiently sloppy additive precision you like). Could someone point me to an explanation or a reference that clarifies this?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Perhaps Example 3.9.1 of Li and Vitani book "An introduction to Kolmogorov complexity and its applications" is relevant: $K(x|y) \leq K(x|y^*) + c_{K(\cdot|y^*)}$ ... but it is far beyond my knowledge :) $\endgroup$
    – Marzio De Biasi
    Nov 17, 2012 at 0:05
  • 1
    $\begingroup$ I mean this inequality is clear: there is a fixed program which will simulate $y^*$ and output $y$, which can then be used as the auxiliary input to whatever program produces $x$ from $y$. My point is that this inequality should change the nature of the metric. In particular, the theorems proved give inequalities up to $O(1/K)$ additive precision where $K = \max{K(x), K(y)}$. But this is in general smaller than constant additive precision. $\endgroup$
    – Jeremy Kun
    Nov 17, 2012 at 5:15
  • 2
    $\begingroup$ the two conditional complexities are indeed different: exists $n$ for which $K(K(x)|x) \geq \log n + 2 \log \log n + O(1)$, but $K(K(x)|x^*) = O(1)$. I didn't read the proofs of the theorems in the paper, do they hold for both conditional complexities ($K(\cdot|x^*)$ and $K(\cdot|x)$)? $\endgroup$
    – Marzio De Biasi
    Nov 17, 2012 at 10:42

1 Answer 1

Reset to default
4
$\begingroup$

As per the comment, $K(x|y) \leq K(x|y^*) + O(1)$. Now denoting the first metric (with the *) by $d_1$ and the second by $d_2$, we have

$\displaystyle \begin{align*} d_2(x,y) &= \frac{\max \left \{ K(x|y), K(y|x) \right \} }{\max \left \{ K(x), K(y) \right \}} \\ &\leq \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \} + O(1) }{\max \left \{ K(x), K(y) \right \}} \\ &= d_1(x,y) + O(1/K) \end{align*}$

where $K = \max \left \{ K(x), K(y) \right \}$

All of the theorems in the paper give the metric inequalities and universality claims up to an additive factor of $O(1/K)$, so this fits.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I suppose this raises the obvious question: why not work entirely without the star to begin with? $\endgroup$
    – Jeremy Kun
    Nov 17, 2012 at 20:19
  • $\begingroup$ Actually now I'm not so sure. Since the "constant" $O(1)$ depends on $K(y^*)$, it won't be the case that $K(y^*)/K(y) = O(1/K(y))$. If $y^*$ is incompressible, this would be $O(1)$. $\endgroup$
    – Jeremy Kun
    Dec 1, 2012 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.