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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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}


Linking options:
  • http://mi.mathnet.ru/eng/pdma419
  • http://mi.mathnet.ru/eng/pdma/y2019/i12/p18

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Prikladnaya Diskretnaya Matematika. Supplement
    Number of views:
    This page:64
    Full text:9
    References:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020