V.M. Zakharov* , S.V. Shalagin** , B.F. Eminov***
A.N. Tupolev Kazan National Research Technical University, Kazan, 420111 Russia
E-mail: *gilvv@mail.ru,**sshalagin@mail.ru, ***bulfami@mail.ru
Received May 28, 2019
DOI: 10.26907/2541-7746.2019.3.456-467
For citation: Zakharov V.M., Shalagin S.V., Eminov B.F. Representation of the stochastic matrix sets with given properties based on autonomous automatic models. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 3, pp. 456–467. doi: 10.26907/2541-7746.2019.3.456-467. (In Russian)
Abstract
This paper considers the methods of construction (presentation) of the sets of ergodic stochastic matrices using automaton models and determination of the power estimates of the generated sets. The research aimed at developing algorithms for constructing the sets of ergodic stochastic matrices with rational elements with given structures and limit vector based on the automaton probabilistic and deterministic models represented by autonomous automata, as well as at estimating the power of the obtained sets of stochastic matrices depending on the dimensions of the given automaton models. The constructed sets of ergodic stochastic matrices are focused on solving the problem of classification of automaton probabilistic models according to certain criteria (parameters) of similarities or differences between the structures of ergodic matrices by the methods of applied multidimensional mathematical statistics. The developed algorithms enable to form a variety of sets of stochastic matrices by changing the transition functions in the considered automata, output functions in autonomous deterministic automaton, and random entry of probabilistic automaton. It was shown that the transition function of autonomous probabilistic automaton allows makes it possible to develop, based on the proposed functioning algorithm, a set of ergodic stochastic matrices with different probabilistic automaton powers and structures based on the permutations of a set of states with repetitions and changes in the probability distribution of the input random variable. It was demonstrated that the sets of ergodic stochastic matrices with different power characteristics and a limit vector based on rearrangements in a set of output letters with repetitions can be formed by changing the functions of the the autonomous deterministic automaton with the help of the developed algorithm. The estimates of the powers of the sets of ergodic stochastic matrices with rational elements represented by autonomous probabilistic and deterministic automata for given restrictions were provided. These estimates reflect the dependencies of the values of powers of the generated sets of stochastic matrices on the dimension characteristics of the automaton models. The proposed construction algorithms of the sets of ergodic stochastic matrices are complementary with respect to the solved problems.
Keywords: set of stochastic matrices, structure, limit vector, autonomous automatic models, set power estimates
Acknowledgments. The study was supported by the Russian Foundation for Basic Research (project no. 18-01-00120).
References
1. Katehakis M., Smit L. A successive lumping procedure for a class of Markov chains. Probab. Eng. Inf. Sci., 2012, vol. 26, no. 4, pp. 483–508. doi: 10.1017/S0269964812000150.
2. Deundyak V.M., Zhdanova M.A. Polynomial representation of hidden semi-Markov model of the Ferguson type. Vestn. VGU: Sist. Anal. Inf. Tekhnol., 2013, no. 2, pp. 71–78. (In Russian)
3. Pogorelov B.A., Pudovkina M.A. On generalizations of Markov's approach to research of block ciphers. Prikl. Diskr. Mat. Prilozh., 2014, no. 7, pp. 51–52. (In Russian)
4. Geiger B., Temmel C. Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability. Adv. Appl. Probab., 2014, vol. 51, no. 4, pp. 1114–1132. doi: 10.1239/jap/1421763331.
5. Raikhlin V.A., Vershinin I.S., Gibadullin R.F., Pystogov S.V. Reliable recognition of masked cartographic scenes during transmission over the network. Proc. 2016 Int. Sib. Conf. on Control and Communications (SIBCON). IEEE, 2016, pp. 1–5. doi: 10.1109/SIBCON.2016.7491657.
6. Bukharaev R.G. Osnovy teorii veroyatnostnykh avtomatov [Fundamentals of the Theory of Probabilistic Automata]. Moscow, Nauka, 1985. 287 p. (In Russian)
7. Levin B.R., Schwartz V. Veroyatnostnye modeli i metody v sistemakh svyazi i upravleniya [Probabilistic Models and Methods in Communication and Management Systems]. Moscow, Radio Svyaz', 1985. 312 p. (In Russian)
8. Glova V.I., Zakharov V.M., Pesoshin V.A., Shalagin S.V. Modelirovanie. Veroyatnostnye diskretnye modeli [Modeling. Probabilistic Discrete Models]. Zakharov V.M. (Ed.). Kazan, ABAK, 1998. 52 p. (In Russian)
9. Zakharov V.M., Nurmeev N.N., Salimov F.I., Shalagin S.V. Classification of stochastic ergodic matrices by cluster and discriminant analysis methods. In: Issledovaniya po informatike [Computer Science Research]. Kazan, Otechestvo, 2000, pp. 91–106. (In Russian)
10. Nurutdinova A.R., Shalagin S.V. Multi-parametric classification of automaton Markov models based on the sequences they generate. Prikl. Diskr. Mat., 2010, no.4, pp. 41–54. (In Russian)
11. Borovikov V.P. Statistica: iskusstvo analiza dannykh na komp'yutere [Statistica: Art of Computer-Aided Data Analysis]. St. Petersburg, Piter, 2003. 700 p. (In Russian)
12. Kemeny J.G., Snell J.L. Finite Markov Chains. Princeton, New Jersey, Toronto, London, New York, D. van Nostrand Co. Inc. VIII, 1960. 210 p.
13. Zakharov V.M., Eminov B.F., Shalagin S.V. Representing lumped Markov chains by minimal polynomials over field GF(q). J. Phys.: Conf. Ser., 2018, vol. 2015, pp. 1–6. doi: 10.1088/1742-6596/1015/3/032033.
14. Bukharaev R.G., Zakharov V.M. Upravlyaemye generatory sluchainykh kodov [Managed Random Code Generators]. Kazan, Kazan. Gos. Univ., 1978. 160 p. (In Russian)
15. Chentsov V.M. On a method for the synthesis of an autonomous stochastic automaton. Kibernetika, 1968, no. 3, pp. 32–35. (In Russian)
16. Eminov B.F., Zakharov V.M. Analysis of decomposition algorithms binary rational stochastic matrices on a combination of Boolean matrices. Inf. Tekhnol., 2008, no. 3, pp. 54–59. (In Russian)
17. Bronstein I.N., Semendyaev K.A. Spravochnik po matematike dlya inzhenerov i uchashchikhsya vtuzov [A Guide on Mathematics for Engineers and Students of Technical Universities]. Moscow, Nauka, 1986. 544 p. (In Russian)
18. Stolov E.L. A class of generators of pseudo-Markov chains. Issled. Prikl. Mat., 1980, no. 8, pp. 66–71. (In Russian)
19. Alferov A.P., Zubov A.Yu. Osnovy kriptografii [Cryptography Basics]. Moscow, Gelios ARV, 2002. 480 p. (In Russian)
20. Carvate D.B., Pursley M.B. Cross-correlation properties of pseudorandom and related sequences. Zh. Inst. Inzh. Elektrotekh. Radioelektron., 1980, vol. 68, no. 5, pp. 59–90. (In Russian)
21. Nechaev V.I. Elementy kriptografii. Osnovy teorii zashchity informatsii [Elements of Cryptography. Fundamentals of Information Security Theory]. Moscow, Vyssh. Shk., 1999. 109 p. (In Russian)
22. Latypov R.Kh. Matematicheskie osnovy kodirovaniya informatsii i kriptografii [The Mathematical Basis of Information Coding and Cryptography]. Kazan, Kazan. Gos. Univ., 2005. 60 p. (In Russian)
The content is available under the license Creative Commons Attribution 4.0 License.