доктор педагогических наук, кандидат физико-математическихнаук
doctor of pedagogical sciences, candidate of physical and mathematical sciences
аспирант
graduate student
В статье рассмотрены свойства квазиметрики среднего времени первого прохода (обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова), построенной на основе нескольких графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.Во введении представлена история вопроса, дан обзор основных идей и результатов работы.Во втором разделе собраны основные понятия теории цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихсятем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент. Даны базовые определения,необходимые для рассмотрения роли графовых моделей в представлении и исследовании эргодических однородных цепей Маркова. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина 𝑖 имеет степень (полустепень исхода) 𝑘, то все выходящие из нее ребра (дуги) превращаются в дуги с весами 1/𝑘 . Дано определение среднего времени первогопрохода для однородной эргодической цепи Маркова. Проанализирован алгоритм нахождения среднего времени первого прохода с помощью использования сходящихся деревьев ориентированного графа, связанного с матрицей перехода эргодической однородной цепи Маркова. Матрица среднего времени первого прохода рассмотрена как квазиметрика 𝑚 среднего времени первого прохода на множестве вершин 𝑉 = {1, 2, ..., 𝑛} ориентированного графа, соответствующего матрице перехода эргодической однородной цепи Маркова: 𝑚(𝑖, 𝑗) – ожидаемое количество шагов (дуг) для случайного блуждания на орграфе Γ,начинающегося с 𝑖, для достижения 𝑗 в первый раз. Эта квазиметрика обладает рядом важных теоретических и прикладных свойств.В третьем разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для неориентированного цикла 𝐶𝑛, 𝑛 ≥ 3. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для неориентированного цикла для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы 𝑀. Проанализированы свойства получающиеся при этом обобщенных метрических структур.В четвертом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для неориентированного пути 𝑃𝑛, 𝑛 ≥ 2.В пятом разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для ориентированного цикла 𝐶𝑛, 𝑛 ≥ 3. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для ориентированного цикла для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы 𝑀. Проанализированы свойства получающихся при этом обобщенных метрических структур.В шестом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для ориентированного пути 𝑃𝑛, 𝑛 ≥ 2.В заключении подведены итоги работы и намечены возможные пути дальнейших исследований.
In this paper we consider some questions of the theory and practice of mean first passage time quasi-metric, a generalized metric structure closely related to ergodic homogeneous Markovchains. In particular, we consider the structure and properties of mean first passage time quasimetrics based on several graph models, including simple cycles, simple paths and their orientedanalogues.The introduction contains the history of the problem and provides an overview of the main ideas and results presented in the article.The second section gives basic concepts of the theory of Markov chains. In fact, a Markov chain is a mathematical model of some random process describing a sequence of possible eventsin which the probability of each event depends only on the state attained in the previous event. This section collects basic definitions needed to consider the role of graph models inthe presentation and study of ergodic homogeneous Markov chains. The Markov chain can be depicted as an oriented weighted graph of transitions whose vertices correspond to the states of the chain and the arcs correspond to the transitions between them. The process will be ergodic if this weighted oriented graph is weakly connected, and the largest common divisor of the lengths of all its cycles is equal to 1. On the other hand, any connected graph can be used as a basis for building a model of the simplest Markov chain: if a vertex 𝑖 has degree 𝑘, all incident edges are converted into arcs with the weights 1/𝑘 . Moreover, in the second section the definition of the mean first passage time for an ergodic homogeneous Markov chain is given. The algorithm of finding the mean first passage time is analyzed in detail by using converging trees of the oriented graph, related to the transition matrix of the ergodic homogeneous Markov chain. At last, a mean first passage time is analyzed as the quasi-metric 𝑚 of mean first passage timeon the vertices 𝑉 = {1, 2, ..., 𝑛} of the oriented graph corresponding to the transition matrix of a given ergodic homogeneous Markov chain: 𝑚(𝑖, 𝑗) is the expected number of steps (arcs) for random wandering on the oriented graph Γ, starting at 𝑖, to reach 𝑗 for the first time. This quasi-metric has a number of important theoretical and applied properties.The third section deals with the construction and research of mean first passage time quasimetrics for the undirected cycles 𝐶𝑛, 𝑛 ≥ 3. Examples of constructions of mean first passagetime quasi-metrics of undirected cycles for small values of 𝑛 are considered. Illustrations of the ”graphical“ procedure of building the matrix 𝑀 are given. Properties of the resulting generalizedmetric structures are analyzed.In the fourth section, similar considerations for mean first passage time quasi-metrics of the undirected paths 𝑃𝑛, 𝑛 ≥ 2, are represented.The fifth section deals with the construction and research of mean first passage time quasimetrics for the directed (oriented) cycles 𝐶𝑛, 𝑛 ≥ 3. Examples of constructions of mean firstpassage time quasi-metrics of undirected (oriented) cycles for small values of 𝑛 are considered.Illustrations of the ”graphical“ procedure of building the matrix 𝑀 are given. Properties of the resulting generalized metric structures are analyzed.In the sixth section, similar considerations for mean first passage time quasi-metrics of the directed (oriented) paths 𝑃𝑛, 𝑛 ≥ 2, are represented.In the conclusion, the results of the work are summed up and possible directions of further research are outlined.
The authors declare that there are no conflicts of interest present.