We study the maximum depth of context tree estimates, i.e., the maximum Markov order attainable by an estimated tree model given an input sequence of length n. We consider two classes of estimators:

1) Penalized maximum likelihood (PML) estimators where a context tree T is obtained by minimizing a cost of the form -log P_T(x^n) + f(n)|S_T|, where P_T(x^n) is the ML probability of the input sequence x^n under a tree model T, S_T is the set of states defined by T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n)= (A-1)/2 log n, where A is the size of the input alphabet).

2) MDL estimators based on the KT probability assignment. In each case we derive an asymptotic upper bound, n^{1/2 + o(1)}, and we exhibit explicit input sequences that show that this bound is asymptotically tight up to the term o(1) in the exponent.

It is based on joint work with Gadiel Seroussi.

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Kartik Venkat. To suggest speakers, please contact any of the students.