(The) first return time and entropy of Markov chains

Abstract

The convergence rate of the expectation of the logarithm of the first return time is investigated. An algorithm for obtaining the probability distribution of the first return time for the initial n-block with overlapping is presented. For a Markov chain it is shown that $R_n(x)P_n(x)$ converges to exponential distribution in distribution and that $E[log(R_n(x)P_n(x))]$ converges to Euler`s constant, where $R_n(x)$ is the first return time of the initial n-block $x_1…x_n$ and $P_n(x)$ is the probability of $x_1…x_n$. The nonoverlapping first return time $R_(n)$ for ψ-mixing processes holds the same formula. A formula is proposed for measuring entropy for the given Markov chain and some simulation is done to show the accuracy of it. Finally, the algorithm for the probability distribution is applied to test the performance of pseudorandom number generators.