Estimating the Number of States of a Finite-State Source

We study the problem of estimating the number of states in a finite-state, finite-alphabet source. The following performance criterion is adopted: Minimize the probability of estimating the number of states while keeping the overestimation probability exponent at a given prescribed level. A universal asymptotically optimal estimator, in the sense just defined, is proposed first, for the general class of finite state sources, and later for several important subclasses. The optimal estimator proposed relies on the Lempel-Ziv (LZ) data compression algorithm in an intuitively appealing manner.