next up previous
Next: Complexity Up: Unknown model Previous: Optimality

MDL behavior

So far we have only compared the CTW codeword length resulting from our source sequence tex2html_wrap_inline2693 to the ideal codeword length relative to the actual source. We have shown that this codeword length is upper bounded by the ideal codeword length plus an upper bound for the individual redundancy in terms of the sequence length T and the number of parameters tex2html_wrap_inline3205 of the actual source.

If however this tex2html_wrap_inline2693 was generated by some other tree source the same bound on the codeword length applies but now with the ideal codelength and redundancy as determined by the other source. Hence upper bounds like this, for all tree sources, hold for the CTW codeword length and the CTW algorithm minimizes, over all tree sources, the sum of the corresponding ideal codeword length and redundancy. This can be considered as minimum description length (MDL) behavior, if we realize that the redundancy is needed to describe the source model and parameters.



Ramesh Rao
Fri May 2 08:36:00 PDT 1997