priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2023-66-12-1035-1049pribor-183Research ArticleСИСТЕМНЫЙ АНАЛИЗ, УПРАВЛЕНИЕ И ОБРАБОТКА ИНФОРМАЦИИSYSTEM ANALYSIS, MANAGEMENT AND INFORMATION PROCESSINGАналитический подход к выборочному поиску функций вероятностей состояний в марковских цепяхAnalytical Approach to Selective Search for State Probability Functions in Markov ChainsЗемсковА. В.ZemskovА. V.

Алексей Викторович Земсков — д-р техн. наук, профессор; кафедра математического моделирования и прикладной информатики; профессор

Alexey V. Zemskov — Dr. Sci., Professor; Department of Mathematical Modeling and Applied Computer Science; Professor

aleksei.zemskov@yandex.ruГосударственный университет морского и речного флота им. адмирала С. О. МакароваAdmiral Makarov State University of Maritime and Inland Shipping202330112024661210351049Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/183

Предлагается аналитический подход к исследованию счетных однородных марковских цепей. Приводится алгоритм выборочного поиска операторов „вход—выход“ в z-форме. Описываются простые аналитические процедуры получения функций вероятностей при вещественных и комплексно-сопряженных собственных значениях матрицы переходных вероятностей. Даются оценки для границ наступления установившегося режима в тактовом времени. Приводятся дополнительные результаты для установившегося режима с помощью алгоритма развертывания характеристических определителей. Основные выкладки иллюстрируются оценкой характеристик марковских цепей с учетом влияния переходной динамики при изменении вероятностей состояний на интервале функционирования в тактовом времени. Также рассматриваются аспекты надежности вычислений при оценке значений вероятностей с помощью предлагаемого подхода.

An analytical approach to studying countable homogeneous Markov chains is proposed. An algorithm for selective search of input-output operators in z-form is presented. Simple analytical procedures for obtaining probability functions for real and complex conjugate eigenvalues of the transition probability matrix are described. Estimates are given for the boundaries of the onset of a steady state in clock time. Additional results are presented for the steady state using an algorithm for expanding the characteristic determinants. The main calculations are illustrated by assessing the characteristics of Markov chains taking into account the influence of transient dynamics when changing the probabilities of states over the operating interval in clock time. Aspects of calculation reliability when estimating probability values using the proposed approach are also considered.

марковская цепьоператор „вход—выход“ в z-формесобственные значениясобственные векторыфункция вероятности состоянияMarkov chaininput-output operator in z-formeigenvalueseigenvectorsstate probability functionReferencesТихонов В. И., Миронов М. А. Марковские процессы. М.: Сов. радио, 1977. 485 с.Tikhonov V.I., Mironov M.A. Markovskiye protsessy (Markov Processes), Moscow, 1977, 485 р. (in Russ.)Вентцель Е. С. Исследование операций: задачи, принципы, методология. М.: КноРус, 2010. 190 с.Ventzel E.S. Issledovaniye operatsiy: zadachi, printsipy, metodologiya (Operations Research: Objectives, Principles, Methodology), Moscow, 2010, 190 р. (in Russ.)Нуммелин Э. Общие неприводимые цепи Маркова и неотрицательные операторы. М.: Мир, 1989. 208 с.Nummelin E. General Irreducible Markov Chains and Non-Negative Operators, Cambridge etc., 1984, 156 p.Фурман Я. А., Юрьев А. Н., Яншин В. В. Цифровые методы обработки и распознавания бинарных изображений. Красноярск: Изд-во Краснояр. ун-та, 1992. 245 с.Furman Ya.A., Yuryev A.N., Yanshin V.V. Tsifrovyye metody obrabotki i raspoznavaniya binarnykh izobrazheniy (Digital Methods of Processing and Recognition of Binary Images), Krasnoyarsk, 1992, 245 р. (in Russ.)Harrison P. G. Transient Behaviour of Queueing Networks // J. Appl. Prob. 1981. Vol. 18, N 2. P. 482—490.Harrison P.G. J. Appl. Prob., 1981, no. 2(18), pp. 482–490.Dudin A. N., Karolik A. V. BMAP/SM/1 Queue with Markovian Input of Disasters and Non-instantaneous Recovery // Performance Evaluat. 2001. Vol. 45, N 1. P. 19—32.Dudin A.N., Karolik A.V. Performance Evaluat., 2001, no. 1(45), pp. 19–32.Dharmaraja S., Rakesh Kumar. Transient solution of a Markovian queuing model with heterogeneous servers and catastrophes // OPSEARCH. 2015. Vol. 52, N 4. P. 810—826.Dharmaraja S., Rakesh Kumar, OPSEARCH, 2015, no. 4(52), pp. 810–826.Kumar B. K., Madheshwari S. P., Venkatakrishanan K. S. Transient solution of an M/M/2 queue with heterogeneous servers subject to catastrophes // Intern. J. Inform. Management Sci. 2017. Vol. 18, N 1. P. 63—80.Kumar B. Krishna, Madheshwari S. Pavai, Venkatakrishanan K.S. Int. J. Inform. Management Sci., 2017, no. 1(18), pp. 63–80.Миллер А. Б., Миллер Б. М., Степанян К. В. Одновременное импульсное и непрерывное управление марковской цепью в непрерывном времени // Автоматика и телемеханика. 2020. № 3. С. 114—131. DOI: 10.31857/S0005231020030071.Miller A.B., Miller B.M., and Stepanyan K.V. Automation and Remote Control, 2020, no. 3, рр. 469–482, DOI: 10.31857/S0005231020030071.Вытовтов К. А., Барабанова Е. А. Аналитический метод анализа неоднородных непрерывных марковских процессов с кусочно-постоянными интенсивностями перехода // Автоматика и телемеханика. 2021. № 12. С. 91—104. DOI: 10.31857/S0005231021120060.Vytovtov K.A. and Barabanova E.A. Automation and Remote Control, 2021, no. 12, рр. 2112–2124, DOI: 10.31857/S0005231021120060.Куо Б. Теория и проектирование цифровых систем управления / Пер. с англ. В. Г. Дунаева; под ред. П. И. Попова. М.: Машиностроение, 1986. 448 с.Kuo B.C. Digital Contrоl Systems, NY, Chicago, San Francisco, Holt, Rinehart and Winston, Inc., 1980.Джури Э. Импульсные системы автоматического регулирования / Пер. с англ. М. А. Берманта, Ж. Л. Грина. М.: Физматгиз, 1963. 455 с.Jury E.J. Sampled-Data Control Systems, NY, Wiley, London, Chapmen and Hall, 1958.Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1960. 654 с.Faddeev D.K., Faddeeva V.N. Vychislitel'nyye metody lineynoy algebry (Computational Methods of Linear Algebra), Moscow, 1960, 654 р. (in Russ.)Теория автоматического управления: Учеб. для вузов по спец. „Автоматика и телемеханика“. В 2-х ч. Ч. I. Теория линейных систем автоматического управления / Н. А. Бабаков, А. А. Воронов, А. А. Воронова и др.; Под ред. А. А. Воронова. 2-е изд., перераб. и доп. М.: Высш. шк., 1986. 367 с.Babakov N.A., Voronov A.A., Voronova A.A. et al. Teoriya avtomaticheskogo upravleniya. Ch. I. Teoriya lineynykh sistem avtomaticheskogo upravleniya (Theory of Automatic Control. Part I. Theory of Linear Systems of Automatic Control), Moscow, 1986, 367 р. (in Russ.)Земсков А. В. Метод получения матрицы передаточных функций на ЭВМ // Изв. вузов. Приборостроение. 1989. Т. 32, № 11. С. 20—22.Zemskov A.V. Journal of Instrument Engineering, 1989, no. 11(32), pp. 20–22. (in Russ.)Земсков В. А., Земсков А. В. Метод определения фундаментальных матриц в непрерывных и дискретных системах автоматического управления и его практические приложения // Аналитическая теория автоматического управления и ее приложения: Тр. междунар. науч. конф. Саратов: СГТУ, 2000. С. 17—20.Zemskov V.A., Zemskov A.V. Analiticheskaya teoriya avtomaticheskogo upravleniya i yeye prilozheniya (Analytical Theory of Automatic Control and Its Applications), Proceedings of the International Scientific Conference, Saratov, 2000, рр. 17–20. (in Russ.)Golub G. H. & Uhlig F. The QR algorithm: 50 years later – its genesis by John Francis and Vera Kublanovskaya, and subsequent developments // IMA Journal of Numerical Analysis. 2009. Vol. 29, N 3. Р. 467—485. ISSN 0272-4979.Golub G.H. & Uhlig F. IMA Journal of Numerical Analysis, 2009, no. 3(29), pp. 467–485.Земсков А. В. Метод выборочного поиска для собственных векторов матриц и его практические приложения // Журнал вычислительной математики и математической физики. 1998. Т. 38, № 3. С. 365—375.Zemskov A.V. Computational Mathematical and Mathematical Physics, 1998, no. 3(38), pp. 351–361.Bellman R. E. Adaptive Control Processes. Princeton, NJ: Princeton University Press, 1961. 276 p.Bellman R.E. Adaptive Control Processes, Princeton University Press, Princeton, NJ, 1961, 276 p.Langville A. N., Meyer C. D. Google's PageRank and beyond: the science of search engine rankings. Princeton University Press, 2006. 224 р.Langville A.N., Meyer C.D. Google's PageRank and beyond: the science of search engine rankings, Princeton University Press, 2006, 224 р

The authors declare that there are no conflicts of interest present.