Average convergence rate of the first return time

Geon Choe¹ ; Dong Kim¹

¹

Colloquium Mathematicum, Tome 84 (2000) no. 1, pp. 159-171

Résumé

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.

Détail

DOI : 10.4064/cm-84/85-1-159-171

Keywords: entropy, the first return time, period of an irreducible matrix, Wyner-Ziv-Ornstein-Weiss theorem, data compression, Markov chain