ArticleOriginal scientific text
Title
Average convergence rate of the first return time
Authors 1, 1
Affiliations
- Department of Mathematics, Korea Advanced Institute of Science and Technology, Taejon, South Korea
Abstract
The convergence rate of the expectation of the logarithm of the first return time , after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have eventually, a.s., where is the probability of the initial n-block in x. In this paper we prove that converges to a constant depending only on the process where is the modified first return time with block length L and gap size S. In the last section a formula is proposed for measuring entropy sharply; it may detect periodicity of the process.
Keywords
entropy, the first return time, period of an irreducible matrix, Wyner-Ziv-Ornstein-Weiss theorem, data compression, Markov chain
Bibliography
- A. Dembo and I. Kontoyiannis, The asymptotics of waiting times between stationary processes, allowing distortion, Ann. Appl. Probab. 9 (1999), 413-429.
- M. Kac, On the notion of recurrence in discrete stochastic processes, Bull. Amer. Math. Soc. 53 (1947), 1002-1010.
- J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer, New York, 1976.
- I. Kontoyiannis, Asymptotic recurrence and waiting times for stationary processes, J. Theoret. Probab. 11 (1998), 795-811.
- I. Kontoyiannis, P. H. Algoet, Yu. M. Suhov and A. J. Wyner, Nonparametric entropy estimation for stationary processes and random fields, with applications to English text, IEEE Trans. Inform. Theory 44 (1998), 1319-1327.
- D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995.
- G. Louchard and W. Szpankowski, On the average redundancy rate of the Lempel-Ziv code, IEEE Trans. Inform. Theory 43 (1997), 2-8.
- U. Maurer, A universal statistical test for random bit generators, J. Cryptology 5 (1992), 89-105.
- D. Ornstein and B. Weiss, Entropy and data compression schemes, IEEE Trans. Inform. Theory 39 (1993), 78-83.
- C. Shannon, The mathematical theory of communication, Bell Sys. Tech. J. 27 (1948), 379-423 and 623-656.
- P. C. Shields, The Ergodic Theory of Discrete Sample Paths, Grad. Stud. Math. 13 Amer. Math. Soc., 1996.
- W. Szpankowski, Asymptotic properties of data compression and suffix trees, IEEE Trans. Inform. Theory 39 (1993), 1647-1659.
- F. M. J. Willems, Universal data compression and repetition times, ibid. 35 (1989), 54-58.
- A. J. Wyner, Strong matching theorems and applications to data compression and statistics, Ph.D. thesis, Stanford Univ., 1993.
- A. J. Wyner, More on recurrence and waiting times, Ann. Appl. Probab., to appear.
- A. J. Wyner and J. Ziv, Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression, IEEE Trans. Inform. Theory 35 (1989), 1250-1258.
- J. Ziv and A. Lempel, A universal algorithm for sequential data compression, ibid. 23 (1977), 337-343.
- J. Ziv and A. Lempel, Compression of individual sequences via variable rate coding, ibid. 24 (1978), 530-536.