Asymptotically Tight Bounds on the Depth of Estimated Context Trees

We study the maximum Markov model order that can be estimated for an (individual) input sequence x of length n over a finite alphabet of size α, for popular estimators of tree models, where the estimated order is determined by the depth of a context tree estimate, and in the special case of plain Markov models, where the tree is constrained to be perfect (with all leaves at the same depth). First, we consider penalized maximum likelihood estimators where a context tree T̂ is obtained by minimizing a cost of the form - log P̂
_τ
(x) + f(n)|S
_τ
|, where P̂
_τ
(x) is the ML of x under a model with context tree T, S
_τ
is the set of leaves of T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator is a special case with f(n) = α-1/2 log n). For plain Markov models, a simple argument yields a known upper bound k̅(n) = O(log n) on the maximum order that can be estimated for x, and we show that, in fact, this simple bound is not far from tight. For general context trees, we derive an asymptotic upper bound, n
^1/2-o(1)
, on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to a multiplicative constant factor. We show that a similar upper bound applies also to MDL estimators based on the KT probability assignment and, moreover, the same example sequences asymptotically approach the upper bound also in this case.