Квазиметрики на графах

В статье рассмотрены свойства квазиметрики среднего времени первого прохода (обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова), построенной на основе нескольких графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.
Во введении представлена история вопроса, дан обзор основных идей и результатов работы.
Во втором разделе собраны основные понятия теории цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент. Даны базовые определения, необходимые для рассмотрения роли графовых моделей в представлении и исследовании эргодических однородных цепей Маркова. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина $i$ имеет степень (полустепень исхода) $k$, то все выходящие из нее ребра (дуги) превращаются в дуги с весами $\frac{1}{k}$. Дано определение среднего времени первого прохода для однородной эргодической цепи Маркова. Проанализирован алгоритм нахождения среднего времени первого прохода с помощью использования сходящихся деревьев ориентированного графа, связанного с матрицей перехода эргодической однородной цепи Маркова. Матрица среднего времени первого прохода рассмотрена как квазиметрика $m$ среднего времени первого прохода на множестве вершин $V=\{1, 2, ..., n\}$ ориентированного графа, соответствующего матрице перехода эргодической однородной цепи Маркова: $m(i,j)$ – ожидаемое количество шагов (дуг) для случайного блуждания на орграфе $\Gamma$, начинающегося с $i$, для достижения $j$ в первый раз. Эта квазиметрика обладает рядом важных теоретических и прикладных свойств.
В третьем разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для неориентированного цикла $C_n$, $n\geq 3$. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для неориентированного цикла для малых значений $n$. Приведены иллюстрации "графовой" процедуры построения матрицы $M$. Проанализированы свойства получающиеся при этом обобщенных метрических структур.
В четвертом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для неориентированного пути $P_n$, $n\geq 2$.
В пятом разделе рассмотрены вопросы построения и исследования квазиметрики среднего времени первого прохода для ориентированного цикла $\overrightarrow{C_{n}}$, $n\geq 3$. Рассмотрены примеры построения квазиметрики среднего времени первого прохода для ориентированного цикла для малых значений $n$. Приведены иллюстрации "графовой" процедуры построения матрицы $M$. Проанализированы свойства получающихся при этом обобщенных метрических структур.
В шестом разделе аналогичные рассуждения проведены для квазиметрики среднего времени первого прохода для ориентированного пути $\overrightarrow{P_{n}}$, $n\geq 2$.
В заключении подведены итоги работы и намечены возможные пути дальнейших исследований.