Model Selection for Variable Length Markov Chains and Tuning the Context Algorithm

We consider the model selection problem in the class of stationary variable length Markov chains (VLMC) on a finite space. The processes in this class are still Markovian of higher order, but with memory of variable length. Various aims in selecting a VLMC can be formalized with different non-equivalent risks, such as final prediction error or expected Kullback-Leibler information. We consider the asymptotic behavior of different risk functions and show how they can be generally estimated with the same resampling strategy. Such estimated risks then yield new model selection rules: in the special case of classical higher order full Markov chains we obtain a better proposal than the AIC criterion, which has been suggested in the past. Attacking the model selection problem also yields a proposal for tuning Rissanen's context algorithm, which can be used for estimating the minimal state space and in turn the whole probability structure of a VLMC. Key words and phrases. Bootstrap, zero-one ..