ArticleOriginal scientific text

Title

Average convergence rate of the first return time

Authors 1, 1

Affiliations

  1. 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 Rn, after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have log[Rn(x)Pn(x)]=o(nβ) a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have -(1+ε)lognlog[Rn(x)Pn(x)]loglogn eventually, a.s., where Pn(x) is the probability of the initial n-block in x. In this paper we prove that E[logR(L,S)-(L-1)h] converges to a constant depending only on the process where R(L,S) 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

  1. A. Dembo and I. Kontoyiannis, The asymptotics of waiting times between stationary processes, allowing distortion, Ann. Appl. Probab. 9 (1999), 413-429.
  2. M. Kac, On the notion of recurrence in discrete stochastic processes, Bull. Amer. Math. Soc. 53 (1947), 1002-1010.
  3. J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer, New York, 1976.
  4. I. Kontoyiannis, Asymptotic recurrence and waiting times for stationary processes, J. Theoret. Probab. 11 (1998), 795-811.
  5. 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.
  6. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995.
  7. G. Louchard and W. Szpankowski, On the average redundancy rate of the Lempel-Ziv code, IEEE Trans. Inform. Theory 43 (1997), 2-8.
  8. U. Maurer, A universal statistical test for random bit generators, J. Cryptology 5 (1992), 89-105.
  9. D. Ornstein and B. Weiss, Entropy and data compression schemes, IEEE Trans. Inform. Theory 39 (1993), 78-83.
  10. C. Shannon, The mathematical theory of communication, Bell Sys. Tech. J. 27 (1948), 379-423 and 623-656.
  11. P. C. Shields, The Ergodic Theory of Discrete Sample Paths, Grad. Stud. Math. 13 Amer. Math. Soc., 1996.
  12. W. Szpankowski, Asymptotic properties of data compression and suffix trees, IEEE Trans. Inform. Theory 39 (1993), 1647-1659.
  13. F. M. J. Willems, Universal data compression and repetition times, ibid. 35 (1989), 54-58.
  14. A. J. Wyner, Strong matching theorems and applications to data compression and statistics, Ph.D. thesis, Stanford Univ., 1993.
  15. A. J. Wyner, More on recurrence and waiting times, Ann. Appl. Probab., to appear.
  16. 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.
  17. J. Ziv and A. Lempel, A universal algorithm for sequential data compression, ibid. 23 (1977), 337-343.
  18. J. Ziv and A. Lempel, Compression of individual sequences via variable rate coding, ibid. 24 (1978), 530-536.
Pages:
159-171
Main language of publication
English
Received
1999-06-11
Accepted
2000-01-18
Published
2000
Exact and natural sciences