Editing Algorithmic probability (section)

=== Proof ===

This is an immediate consequence of the [[Kraft-McMillan inequality]].

Kraft's inequality states that given a sequence of strings <math>\{x_i\}_{i=1}^n</math> there exists a prefix code with codewords <math>\{\sigma_i\}_{i=1}^n</math> where <math>\forall i, |\sigma_i|=k_i</math> if and only if:

:<math>
\sum_{i=1}^n s^{-k_i} \leq 1	 
</math>

where <math>s</math> is the size of the alphabet <math>S</math>.

Without loss of generality, let's suppose we may order the <math>k_i</math> such that:

:<math>
k_1 \leq k_2 \leq ... \leq k_n	
</math>

Now, there exists a prefix code if and only if at each step <math>j</math> there is at least one codeword to choose that does not contain any of the previous <math>j-1</math> codewords as a prefix. Due to the existence of a codeword at a previous step <math>i<j, s^{k_j-k_i}</math> codewords are forbidden as they contain <math>\sigma_i</math> as a prefix. It follows that in general a prefix code exists if and only if:

:<math>
\forall j \geq 2, s^{k_j} > \sum_{i=1}^{j-1} s^{k_j - k_i}	
</math>

Dividing both sides by <math>s^{k_j}</math>, we find:

:<math>
\sum_{i=1}^n s^{-k_i} \leq 1	 
</math>

QED.