Average convergence rate of the first return time

Geon Choe; Dong Kim

Colloquium Mathematicae (2000)

  • Volume: 84/85, Issue: 1, page 159-171
  • ISSN: 0010-1354

Abstract

top
The convergence rate of the expectation of the logarithm of the first return time R n , after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have l o g [ R n ( x ) P n ( x ) ] = o ( n β ) a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have - ( 1 + ε ) l o g n ≤ l o g [ R n ( x ) P n ( x ) ] ≤ l o g l o g n eventually, a.s., where P n ( x ) is the probability of the initial n-block in x. In this paper we prove that E [ l o g R ( 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.

How to cite

top

Choe, Geon, and Kim, Dong. "Average convergence rate of the first return time." Colloquium Mathematicae 84/85.1 (2000): 159-171. <http://eudml.org/doc/210794>.

@article{Choe2000,
abstract = {The convergence rate of the expectation of the logarithm of the first return time $R_\{n\}$, after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have $log[R_\{n\}(x)P_\{n\}(x)] =o(n^\{β\})$ a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have $-(1 + ε)log n ≤ log[R_\{n\}(x)P_\{n\}(x)] ≤ loglog n$ eventually, a.s., where $P_\{n\}(x)$ is the probability of the initial n-block in x. In this paper we prove that $ E[log R_\{(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.},
author = {Choe, Geon, Kim, Dong},
journal = {Colloquium Mathematicae},
keywords = {entropy; the first return time; period of an irreducible matrix; Wyner-Ziv-Ornstein-Weiss theorem; data compression; Markov chain; ergodic Markov chains; modified first return time},
language = {eng},
number = {1},
pages = {159-171},
title = {Average convergence rate of the first return time},
url = {http://eudml.org/doc/210794},
volume = {84/85},
year = {2000},
}

TY - JOUR
AU - Choe, Geon
AU - Kim, Dong
TI - Average convergence rate of the first return time
JO - Colloquium Mathematicae
PY - 2000
VL - 84/85
IS - 1
SP - 159
EP - 171
AB - The convergence rate of the expectation of the logarithm of the first return time $R_{n}$, after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have $log[R_{n}(x)P_{n}(x)] =o(n^{β})$ a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have $-(1 + ε)log n ≤ log[R_{n}(x)P_{n}(x)] ≤ loglog n$ eventually, a.s., where $P_{n}(x)$ is the probability of the initial n-block in x. In this paper we prove that $ E[log R_{(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.
LA - eng
KW - entropy; the first return time; period of an irreducible matrix; Wyner-Ziv-Ornstein-Weiss theorem; data compression; Markov chain; ergodic Markov chains; modified first return time
UR - http://eudml.org/doc/210794
ER -

References

top
  1. [1] A. Dembo and I. Kontoyiannis, The asymptotics of waiting times between stationary processes, allowing distortion, Ann. Appl. Probab. 9 (1999), 413-429. Zbl0940.60033
  2. [2] M. Kac, On the notion of recurrence in discrete stochastic processes, Bull. Amer. Math. Soc. 53 (1947), 1002-1010. Zbl0032.41802
  3. [3] J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer, New York, 1976. Zbl0328.60035
  4. [4] I. Kontoyiannis, Asymptotic recurrence and waiting times for stationary processes, J. Theoret. Probab. 11 (1998), 795-811. Zbl0912.60051
  5. [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. Zbl1026.94516
  6. [6] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, 1995. Zbl1106.37301
  7. [7] G. Louchard and W. Szpankowski, On the average redundancy rate of the Lempel-Ziv code, IEEE Trans. Inform. Theory 43 (1997), 2-8. Zbl0873.94009
  8. [8] U. Maurer, A universal statistical test for random bit generators, J. Cryptology 5 (1992), 89-105. Zbl0790.94014
  9. [9] D. Ornstein and B. Weiss, Entropy and data compression schemes, IEEE Trans. Inform. Theory 39 (1993), 78-83. Zbl0764.94003
  10. [10] C. Shannon, The mathematical theory of communication, Bell Sys. Tech. J. 27 (1948), 379-423 and 623-656. Zbl1154.94303
  11. [11] P. C. Shields, The Ergodic Theory of Discrete Sample Paths, Grad. Stud. Math. 13 Amer. Math. Soc., 1996. 
  12. [12] W. Szpankowski, Asymptotic properties of data compression and suffix trees, IEEE Trans. Inform. Theory 39 (1993), 1647-1659. Zbl0802.94007
  13. [13] F. M. J. Willems, Universal data compression and repetition times, ibid. 35 (1989), 54-58. Zbl0671.94005
  14. [14] A. J. Wyner, Strong matching theorems and applications to data compression and statistics, Ph.D. thesis, Stanford Univ., 1993. 
  15. [15] A. J. Wyner, More on recurrence and waiting times, Ann. Appl. Probab., to appear. Zbl0955.60031
  16. [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. Zbl0695.94003
  17. [17] J. Ziv and A. Lempel, A universal algorithm for sequential data compression, ibid. 23 (1977), 337-343. Zbl0379.94010
  18. [18] J. Ziv and A. Lempel, Compression of individual sequences via variable rate coding, ibid. 24 (1978), 530-536. Zbl0392.94004

NotesEmbed ?

top

You must be logged in to post comments.