Tong Zhang
Perfect Memory Context Trees in Time Series Modeling
The
Stochastic Context Tree (SCOT) is a useful tool for studying infinite random
sequences generated by an m-Markov
Chain (m-MC). It captures the phenomenon that the probability distribution of
the next state sometimes depends on less than m of the preceding states. This allows compressing the information
needed to describe an m-MC. The SCOT construction has been earlier used under
various names: VLMC, VOMC, PST, CTW. In this paper we
study the possibility of reducing the m-MC to a 1-MC on the leaves of the SCOT.
Such context trees are called perfect-memory.
We give various combinatorial characterizations of perfect-memory context trees
and an efficient algorithm to find the minimal perfect-memory extension of a
SCOT.
КЛЮЧЕВЫЕ СЛОВА: context tree, VLMC, SCOT, m-MC, memory
structure, dimension reduction