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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.