next up previous
Next: Optimality Up: Unknown model Previous: CTW algorithm

Analysis

We start this subsection by taking a look at an example.

Example:Suppose that tex2html_wrap_inline2961 is the model of the actual source. The depth D of our context tree is 3. Then for the leaves of this model we can lower bound the weighted probabilities tex2html_wrap_inline3187 by the tex2html_wrap_inline3083 -terms, i.e.

  eqnarray1903

while for the internal nodes we use the tex2html_wrap_inline3201 -term as lower bound, hence

  eqnarray1925

From the example we may conclude that we loose a factor 1/2 in all tex2html_wrap_inline3205 leaves and tex2html_wrap_inline3207 internal nodes of the actual model, hence

  equation1957

Using (8) we find that

  equation1968

which is tex2html_wrap_inline3209 bits more than the bound in (14), where the model was known. Therefore also the bound on the individual redundancy is tex2html_wrap_inline3209 bits larger than the bound in (15), i.e.:

  equation1977

The increase of tex2html_wrap_inline3209 bits can be considered as the cost of not knowing the model, i.e. the model redundancy. Note that (26) holds for all tex2html_wrap_inline2693 and all tex2html_wrap_inline3003 for tex2html_wrap_inline2955 for all models tex2html_wrap_inline2915 that fit in our context tree.



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