×

Predictive stochastic complexity and model estimation for finite-state processes. (English) Zbl 0804.62008

Summary: It is shown that the predictive and nonpredictive stochastic complexities relative to the class of finite-state models are asymptotically equivalent in a probabilistic sense. To this end, a universal, sequential, noiseless coding scheme attaining the minimum description length (MDL) of the data with respect to this class is presented and investigated. It relies on an MDL-based estimator of the model structure, which is proved to be strongly consistent.
An interpretation of this result is that a process ‘close’ to every process in the class, regardless of the model structure, can be constructed. This universal process can be employed in the solution of sequential decision problems like coding, prediction, and gambling, in an asymptotically optimal manner.

MSC:

62B10 Statistical aspects of information-theoretic topics
94A29 Source coding
62A01 Foundations and philosophical topics in statistics
62F12 Asymptotic properties of parametric estimators
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akaike, H., A new look at the statistical model identification, IEEE Trans. Automat. Control., AC-19, 716-723 (1974) · Zbl 0314.62039
[2] Anderson, T. W., Determination of the order of dependence in normally distributed time series, (Rosenblatt, M., Proc. Symp. on Time Series Analysis (1963), Wiley: Wiley New York), 425-446
[3] Blackwell, D.; Koopmans, L., On the identifiability problem for functions of finite Markov chains, Ann. Math. Statist., 28, 1011-1015 (1957) · Zbl 0080.34901
[4] Cox, D. R.; Miller, H. D., The Theory of Stochastic Processes (1967), Methuen: Methuen London · Zbl 0149.12902
[5] Csiszar, I.; Cover, T. M.; Choi, B., Conditional limit theorems under Markov conditioning, IEEE Trans. Inform. Theory, IT-33, 788-801 (1987) · Zbl 0628.60037
[6] Davisson, L. D., Minimax noiseless universal coding for Markov sources, IEEE Trans. Inform. Theory, IT-29, 211-215 (1983) · Zbl 0502.94002
[7] Feder, M., Gambling using a finite state machine, IEEE Trans. Inform. Theory, IT-37, 1459-1465 (1991)
[8] Feder, M.; Merhav, N.; Gutman, M., Universal prediction of individual sequences, IEEE Trans. Inform. Theory, IT-38, 1258-1270 (1992) · Zbl 0775.94076
[9] L. Finesso (1993). private communication.; L. Finesso (1993). private communication.
[10] Hannan, E. J.; Quinn, B. G., The determination of the order of an autoregression, J. Roy. Statist. Soc. Ser. B, 41, 190-195 (1979) · Zbl 0408.62076
[11] Kieffer, J. C., Strongly consistent MDL-based selection of a model class for a finite-alphabet source (1992), (preprint).
[12] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1, 4-7 (1965) · Zbl 0271.94018
[13] Krichevsky, R. E.; Trofimov, V. K., The performance of universal encoding, IEEE Trans. Inform. Theory, IT-27, 199-207 (1981) · Zbl 0469.94004
[14] Merhav, N.; Gutman, M.; Ziv, J., On the estimation of the order of a Markov chain and universal data compression, IEEE Trans. Inform. Theory, IT-35, 1014-1019 (1989) · Zbl 0683.94004
[15] Rissanen, J., A universal prior for integers and estimation by minimum description length, Ann. Statist., 11, 416-431 (1983) · Zbl 0513.62005
[16] Rissanen, J., Universal coding, information, prediction, and estimation, IEEE Trans. Inform. Theory, IT-30, 629-636 (1984) · Zbl 0574.62003
[17] Rissanen, J., Stochastic complexity and modeling, Ann. Statist., 14, 1080-1100 (1986) · Zbl 0602.62008
[18] Rissanen, J., Complexity of strings in the class of Markov sources, IEEE Trans. Inform. Theory, IT-32, 526-532 (1986) · Zbl 0621.94005
[19] Rudich, S., Inferring the structure of a Markov chain from its output, Proc. 26th IEEE Symp. on Foundations of Computer Science, 321-326 (1985)
[20] Schwartz, G., Estimating the dimension of a model, Ann. Statist., 6, 461-464 (1978) · Zbl 0379.62005
[21] Solomonoff, R. J., A formal theory of inductive inference I, II, Inform. Control, 7, 224-254 (1964) · Zbl 0259.68038
[22] Weinberger, M. J.; Merhav, N.; Feder, M., Optimal sequential probability assignment for individual sequences, IEEE Trans. Inform. Theory (1993), (accepted for publication).
[23] Weinberger, M. J.; Lempel, A.; Ziv, J., A sequential algorithm for the universal of coding finite-memory sources, IEEE Trans. Inform. Theory, IT-38, 1002-1014 (1992) · Zbl 0749.94007
[24] Weinberger, M. J.; Rissanen, J.; Feder, M., A universal finite memory source, IEEE Trans. Inform. Theory (1993), (submitted).
[25] Whittle, P., Tests of fit in time series, Biometrika, 39, 309-318 (1952) · Zbl 0049.37303
[26] Ziv, J.; Merhav, N., Estimating the number of states of a finite-state source, IEEE Trans. Inform. Theory, IT-38, 61-65 (1992) · Zbl 0745.94006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.