RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat. Suppl.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat. Suppl., 2019, Issue 12, Pages 18–21 (Mi pdma419)

Theoretical Foundations of Applied Discrete Mathematics

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

N. M. Mezhennaya

Bauman Moscow State Technical University

Abstract: $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$(s \lambda_s/n+e^{u s} \sqrt{\lambda_s})$ 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-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.

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

DOI: https://doi.org/10.17223/2226308X/12/4

Full text: PDF file (632 kB)
References: PDF file   HTML file

UDC: 519.214

Citation: N. M. Mezhennaya, “On the number of $f$-recurrent runs and tuples in a finite Markov chain”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 18–21

Citation in format AMSBIB
\Bibitem{Mez19} \by N.~M.~Mezhennaya \paper On the number of $f$-recurrent runs and tuples in a finite Markov chain \jour Prikl. Diskr. Mat. Suppl. \yr 2019 \issue 12 \pages 18--21 \mathnet{http://mi.mathnet.ru/pdma419} \crossref{https://doi.org/10.17223/2226308X/12/4}