Chain rule for Kolmogorov complexity: Difference between revisions

Revision as of 21:44, 17 September 2009

Revision as of 16:10, 2 December 2009

Line 1:

The chain rule for [[Kolmogorov complexity]] is an analogue of the chain rule for [[Informationinformation entropy]], which states:

:<math>

Line 9:

:<math>

P(X,Y) = P(X) P(Y|X) \,

</math>

Line 18:

</math>

(An exact version, <math>''KP''(''X'',&nbsp;''Y'') &nbsp;= &nbsp;''KP''(''X'') &nbsp;+ &nbsp;''KP''(''Y''|''X''*) &nbsp;+ &nbsp;O(1)</math>,

holds for the prefix complexty ''KP'', where ''X*'' is a shortest program for ''X''.)

Line 25:

==Proof==

The <math>\le</math>≤ direction is obvious: we can write a program to produce <math>''x</math>'' and <math>''y</math>'' by concatenating a program to produce ''x'', a program to produce ''y'' given

access to <math>''x</math>'', and (whence the log term) the length of one of the programs, so

by concatenating a program to produce <math>x</math>, a program to produce <math>y</math> given

that we know where to separate the two programs for <math>''x</math>'' and <math>''y''|''x</math>'' (log(''K''(''x'',&nbsp;''y'')) upper-bounds this length).

access to <math>x</math>, and (whence the log term) the length of one of the programs, so

that we know where to separate the two programs for <math>x</math> and <math>y|x</math>

(<math>\log(K(x,y))</math> upper bounds this length).

The <math>\ge</math> direction is rather more difficult. The key to the proof is the

Line 40 ⟶ 38:

<math>2^{K(x,y)}</math> programs with length <math>\le K(x,y)</math>. Output each <math>u,z</math> as the

simulated program terminates; eventually, any particular such <math>u,z</math> will be

produced. We can restrict to ''A''<mathsub>A_x''x''</mathsub> simply by ignoring any output where <math>u \ne x</math>. We will assume that the inequality does not hold and derive a contradiction by finding a short description for ''K''(''x'') in terms of its index in the enumeration of a subset of&nbsp;''A''.

x</math>. We will assume that the inequality does not hold and derive a contradiction

by finding a short description for <math>K(x)</math> in terms of its index in the

enumeration of a subset of <math>A</math>.

In particular, we can describe <math>''y</math>'' by giving the index in which ''y'' is output when enumerating ''A''<mathsub>y''x''</mathsub> (which is outputless than or equal to |''A''_''x''|) along with ''x'' and the value of ''K''(''x'',&nbsp;''y''). Thus,

when enumerating <math>A_x</math> (which is less than or equal to <math>|A_x|</math>) along with <math>x</math>

and the value of <math>K(x,y)</math>. Thus,

:<math> K(y|x) \le \log(|A_x|) + O(\log(K(x,y))) + O(1) \, </math>

where the <math>O(1)</math> term is from the overhead of the enumerator, which does not depend on ''x'' or&nbsp;''y''.

depend on <math>x</math> or <math>y</math>.

Assume by way of contradiction

:<math> K(y|x) > K(x,y) - K(x) + O(\log(K(x,y))) \, </math>

for some <math>x,y</math>.

Line 63 ⟶ 55:

:<math>

\log(|A_x|) + O(\log(K(x,y))) + O(1) \ge K(y|x) > K(x,y) - K(x) + O(\log(K(x,y))) \,

</math>

So for any constant <math>''c</math>'' and some <math>&nbsp;''x'',&nbsp;''y</math>'',

:<math> \log(|A_x|) \ge K(x,y) - K(x) + c \log(K(x,y)) \, </math>

Let

Let <math>e = K(x,y) - K(x) + c \log K(x,y)</math>; <math>|A_x| \ge 2^e</math>.

Let: <math>e = K(x,y) - K(x) + c \log K(x,y)</math>;\quad <math>|A_x| \ge 2^e.</math>.

Now, we can enumerate a set of possible values for <math>x</math> by finding all <math>u</math> such