Method of calculating stationary probability distribution in Markov chain in modeling social and economic processes
https://doi.org/10.34020/2073-6495-2024-3-134-145
Abstract
This article proposes an algorithm for calculating the vector of the stationary probability distribution for the Markov chain. Markov chains are effective for modeling complex systems in dynamics, including socio-economic processes, since instead of deterministic equations and dependencies, various scenarios are taken into account. At the same time, with an increase in the number of options, the complexity of solving the problem of finding a stationary probability distribution increases sharply. The idea of the algorithm is to replace the problem of solving the characteristic equation of the n-th degree for the matrix of probability transitions with the problem of linear programming. The mathematical formulation of the problem is formulated, including the definition of independent variables, finding the type of objective function, restrictions in the form of equalities. To perform calculations, a program was created in the algorithmic language Python. In order to verify and prove its effectiveness, calculations were carried out both for typical tasks of a general nature and for specific socio-economic cases. The obtained results completely coincided with the test ones and showed that the complexity of the algorithm is O(n). The developed technique allows wider application of Markov in the study of socio-economic processes and obtain more reliable results due to an increase in the number of probabilistic states of the system.
About the Author
E. V. Kuligin
Novosibirsk State University of Economics and Management
Russian Federation
Russian Federation
Kuligin Evgeny V. – Candidate of Physical and Mathematical Sciences, Associate Professor
Novosibirsk
References
1. Rjej Brjedberi. I grjanul grom... (sbornik) [Ray Bradbury. And a Sound of Thunder... (collection)]. Moscow, Molodaja gvardija, 1976.
2. Savel’ev I.V. Kurs obshhej fiziki. V 3 t. T. 1. Mehanika. Molekuljarnaja fizika: uchebnik dlja vuzov [General Physics Course. In 3 volumes. Volume 1. Mechanics. Molecular Physics: textbook for universities], 18-e izd., ster. St. Petersburg, Lan’, 2022. 436 p. Available at: https://e.lanbook.com/book/221120 (accessed: 03.03.2024).
3. Kuznecov V.V., Shatrakov A.Ju. Sistemnyj analiz: uchebnik i praktikum dlja vuzov [System Analysis: textbook and workshop for universities], pod obshh. red. V.V. Kuznecova; 2-e izd., pererab. i dop. Moscow, Jurajt, 2024. 333 p. Available at: https://urait.ru/bcode/537575 (accessed: 03.03.2024).
4. Alekseeva M.B., Vetrenko P.P. Teorija sistem i sistemnyj analiz: uchebnik i praktikum dlja vuzov [Systems theory and systems analysis: textbook and workshop for universities]. Moscow, Jurajt, 2024. 298 p. Available at: https://urait.ru/bcode/536569 (accessed: 03.03.2024).
5. Karaev A.K., Mel’nichuk M.V. Finansovaja neustojchivost’ i makrojekonomicheskaja nestabil’nost’: agentno orientirovannoe modelirovanie: monografija [Financial Instability and Macroeconomic Instability: Agent-Based Modeling: monograph]. Moscow, Dashkov i K, 2014. 158 p. Available at: https://e.lanbook.com/book/70597 (accessed: 03.03.2024).
6. Akopov A.S., Hachatrjan N.K. Agentnoe modelirovanie [Agent-based modeling]. Moscow, Central’nyj jekonomiko-matematicheskij institut RAN, 2016. 76 p.
7. Markov A.A. Rasprostranenie zakona bol’shih chisel na velichiny, zavisjashhie drug ot druga [Extension of the law of large numbers to quantities dependent on each other]. Izvestija fiziko-matematicheskogo obshhestva pri Kazanskom universitete. 2-ja serija. Vol. 15. Kazan’, 1906. Pp. 135–156.
8. Bocharov P.P. Stacionarnoe raspredelenie konechnoj ocheredi s rekurrentnym potokom i markovskim obsluzhivaniem [Stationary Distribution of a Finite Queue with a Recurrent Flow and Markov Service], AiT [AiT], 1996, no. 9, pp. 66–78.
9. Bocharov P.P., Pechinkin A.V., D’Apiche Ch., Fong N.H. Odnolinejnaja sistema obsluzhivanija konechnoj emkosti s gruppovym markovskim potokom i polumarkovskim obsluzhivaniem [Single-Line Queueing System of Finite Capacity with a Group Markov Flow and Semi-Markov Service], Vestn. Rossijskogo universiteta druzhby narodov. Serija «Prikladnaja matematika i informatika» [Bulletin of Peoples’ Friendship University of Russia. Series “Applied Mathematics and Informatics”], 2001, no. 1, pp. 64–79.
10. Holod N.I., Efremov A.A. Cepi Markova kak instrument modelirovanija dejatel’nosti predprijatij APK v uslovijah neopredelennosti [Chains as a Tool for Modeling the Activities of Agricultural Enterprises under Uncertainty]. Nauchnye trudy Belorusskogo gosudarstvennogo jekonomicheskogo universiteta. Minsk, BGJeU, 2015. Iss. 8. Pp. 398–405.
11. Shmidt A.V. Primenenie cepej Markova pri opredelenii strategii funkcionirovanija i razvitija predprijatija po kriteriju jekonomicheskoj ustojchivosti [Application of Markov Chains in Determining the Strategy of Operation and Development of an Enterprise Based on the Criterion of Economic Sustainability], Vestnik JuUrGU. Serija «Jekonomika i menedzhment» [Bulletin of SUSU. Series “Economics and Management”], 2011, no. 8 (225), iss. 17, pp. 145–153.
12. Kantorovich L.V. Matematika v jekonomike: dostizhenija, trudnosti, perspektivy [Mathematics in Economics: Achievements, Difficulties, Prospects]. Rostov-na-Donu: Maprekon, 2010. 19 p. (Laureaty Nobelevskoj premii). Available at: https://biblioclub.ru/index.php?page=book&id=614170 (accessed: 09.03.2024).
13. Dmitrusenko N.S., Bulatnikova M.E. Sluchajnye velichiny. Cepi Markova. V 2 ch. Ch. 2. Dvumernye sluchajnye velichiny: uchebnoe posobie [Random Variables. Markov Chains. In 2 Parts. Part 2. Two-Dimensional Random Variables: Tutorial]. Moscow, Rossijskij universitet transporta (MIIT), 2017. 84 p. Available at: https://www.iprbookshop.ru/116081.html (accessed: 12.02.2024).
14. Skorohod A.V. Markovskie processy i verojatnostnye prilozhenija v analize [Markov processes and probabilistic applications in analysis], Itogi nauki i tehniki. VINITI. Sovrem. problemy matematiki. Fundamental’nye napravlenija [Results of science and technology. VINITI. Modern problems of mathematics. Fundamental directions], 1989, no. 43, pp. 147–188.
15. Page L., Brin S., Motwani R. and Winograd T. (1998) The PageRank Citation Ranking: Bringing Order to the Web. Technical Report SIDL-WP-1999-0120, Stanford Digital Library Technologies Project.
16. Dehn E. Algebraic Equations: An Introduction to the Theories of Lagrange and Galois (angl.). New York: Columbia University Press, 1930.
17. Krylov V.I., Bobkov V.V., Monastyrnyj P.I. Vychislitel’nye metody vysshej matematiki: v 2 t. [Computational Methods of Higher Mathematics: in 2 volumes], pod red. I.P. Mysovskih. Minsk, 1972. Vol. 1. 584 p.
18. Tyrtyshnikov E.E. Matrichnyj analiz i linejnaja algebra: ucheb. posobie [Matrix Analysis and Linear Algebra: textbook. manual]. Moscow, 2007. 480 p.
19. Saad Y. Iterative methods for sparse linear systems. 2nd ed. Philadelphia, 2003. 528 p.
20. Sewell G. Computational Methods of Linear Algebra. 2nd ed. New Jersey, 2005. 268 p.
21. Falejchik B.V. Metody vychislenij [Methods of Computation]. Minsk, Izdatel’skij centr Belorusskogo gosudarstvennogo universiteta, 2014. 224 p.
22. Marcel F. Neuts Matrix-geometric solutions in stochastic models. Johns Hopkins University Press, 1981. 332 p.
23. Bandi B. Osnovy linejnogo programmirovanija [Fundamentals of Linear Programming], pod red. V.A. Volynskogo; per. s angl. O.V. Shiheevoj. Moscow, Radio i svjaz’, 1989. 176 p.
24. Karmanov V.G. Matematicheskoe programmirovanie: ucheb. posobie [Mathematical programming: textbook], 5-e izd., stereotip. Moscow, Fizmatlit, 2004. 264 p.
25. Dancig Dzh. Linejnoe programmirovanie, ego primenenija i obobshhenija [Linear programming, its applications and generalizations]. Moscow, Progress. Redakcija literatury po jekonomike, 1966. 600 p.
26. Reshenie zadach linejnogo programmirovanija s ispol’zovaniem Python [Solving linear programming problems using Python]. Available at: https://habr.com/ru/articles/330648/.
27. PuLP 2.9.0. Available at: https://pypi.org/project/PuLP/.
28. CVXOPT. Programmnoe obespechenie Python dlja vypukloj optimizacii [CVXOPT. Python software for convex optimization]. Available at: https://cvxopt.org/.
29. SciPy documentation. Available at: https://docs.scipy.org/doc/scipy/reference/optimize.html.
30. Moiseeva S.P. Teorija sluchajnyh processov. Ch. 2. Markovskie processy: uchebnoe posobie [Theory of random processes. Part 2. Markov processes: a tutorial]. Tomsk, Izdatel’skij Dom Tomskogo gosudarstvennogo universiteta, 2014. 58 p.
31. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134–142, 1991.
32. Gonthier G. A computer-checked proof of the Four Colour Theorem. Microsoft Research Cambridge (2005). Arhivirovano 5 ijunja 2022 goda.
Review
For citations:
Kuligin E.V. Method of calculating stationary probability distribution in Markov chain in modeling social and economic processes. Vestnik NSUEM. 2024;(3):134-145. (In Russ.) https://doi.org/10.34020/2073-6495-2024-3-134-145
Email this article 
