<p>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</p>

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

<p>where $K = \max \left \{ K(x), K(y) \right \}$</p>

<p>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.</p>

CC BY-SA 3.0
2012-11-17T20:19:48.633Z
I suppose this raises the obvious question: why not work entirely without the star to begin with?
Jeremy Kun
CC BY-SA 3.0
2012-12-01T01:31:44.820Z
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)$.
Jeremy Kun
CC BY-SA 3.0
2012-11-17T20:17:41.400Z
2012-11-30T18:26:26.183Z
2012-11-30T18:26:26.183Z
Jeremy Kun
<p>In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as </p>

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

<p>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 </p>

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

<p>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?</p>

CC BY-SA 3.0
2012-11-17T00:05:51.827Z
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 :)
Marzio De Biasi
CC BY-SA 3.0
2012-11-17T05:15:57.380Z
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.
Jeremy Kun
CC BY-SA 3.0
2012-11-17T10:42:03.617Z
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)$)?
Marzio De Biasi
<it.information-theory><kolmogorov-complexity>
Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$
Jeremy Kun
# Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

(Asked by: username_0 on 2012-11-16)

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?

**Tags:** it.information-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: 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 :)  
> **username_0**: 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.  
> **username_1**: 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)$)?  

---

## 1 answers

### Answer by username_0 on 2012-11-17. Score: 4

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.

> **Comments:**
> **username_0**: I suppose this raises the obvious question: why not work entirely without the star to begin with?  
> **username_0**: 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)$.  

---

