On the number of $f$-recurrent runs and tuples in a finite Markov chain

N. M. Mezhennaya

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 18-21

Résumé

$f$-Recurrent tuple is a segment of a discrete sequence with the letters obtained by sequential applying a function $f$ to $l$ previous letters, and $f$-recurrent run is a tuple that cannot be extended in both directions while maintaining the $f$-recurrence property. Using the Chen–Stein method, we obtain the estimate for the total variation distance between the distribution of the number $\xi$ of $f$-recurrent runs of at least $s$ length in a segment of a finite stationary ergodic Markov chain of length $n$ and the accompanying Poisson distribution, i.e., Poisson distribution with parameter $\lambda_s=\mathsf{E} \xi$, of the order O$\left(s \lambda_s/n+\text{e}^{u s} \sqrt{\lambda_s}\right)$ for some $u>0$. The Poisson and normal limit theorems for the random variable $\xi$ are derived from the estimate by standard methods (as the length $n$ of a segment of a Markov chain and parameter $s$ tend to infinity). Moreover, the estimate results in that the probability for the presence of $f$-recurrent tuples of at least $s$ length tends to $1-\text{e}^{\lambda}$ if $n,s\to \infty$ such as $s/n\to 0$, $\lambda_s/n \to 0$, and $\lambda_s\to \lambda$. The properties of distributions of frequencies of $f$-recurrent runs or tuples with certain parameters can be used in the development of statistical tests for the quality of pseudo-random sequences.

Détail

Mots-clés : Markov chain, Poisson limit theorem
Keywords: $f$-recurrent run, $f$-recurrent tuple, normal limit theorem, Chen–Stein method.