Чебышевский сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2020, том 21, выпуск 1, страницы 145–164 (Mi cheb865)  

О специальных свойствах некоторых квазиметрик

Е. И. Деза, Б. Мханна

Московский педагогический государственный университет (г. Москва)

Аннотация: В статье рассмотрены свойства квазиметрики среднего времени первого прохода — обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова.
Во введении представлена история вопроса, дан обзор основных идей и результатов работы.
В первом разделе собраны основные понятия теории цепей Маркова — последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Точнее, математическая модель некоторого случайного процесса представляет собой марковскую цепь, если распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент.
Во втором разделе собраны базовые определения, необходимые для рассмотрения роли графовых моделей в представлении и исследовании эргодических однородных цепей Маркова. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги — переходам между ними. Процесс будет эргодическим, если построенный взвешенный орграф является слабо связным, и наибольший общий делитель длин всех его циклов равен единице. С другой стороны, любой связный граф может служить базой для построения модели простейшей цепи Маркова: если вершина $i$ имеет степень $k$, то все выходящие из нее ребра превращаются в дуги с весами $\frac{1}{k}$.
В третьем разделе дано определение среднего времени первого прохода для однородной эргодической цепи Маркова. Представлены несколько способов построения соответствующей матрицы $M$. Подробно проанализирован алгоритм нахождения среднего времени первого прохода с помощью использования сходящихся деревьев ориентированного графа, связанного с матрицей перехода эргодической однородной цепи Маркова. Описана родственная рекуррентная процедура.
В четвертом разделе матрица среднего времени первого прохода рассмотрена как квазиметрика $m$ среднего времени первого прохода на множестве вершин $V=\{1, 2, ..., n\}$ ориентированного графа, соответствующего матрице перехода эргодической однородной цепи Маркова: $m(i,j)$ — ожидаемое количество шагов (дуг) для случайного блуждания на орграфе $\Gamma$, начинающегося с $i$, для достижения $j$ в первый раз. Эта квазиметрика обладает рядом важных теоретических и прикладных свойств. В частности, квазиметрика среднего времени первого прохода для простого случайного блуждания по связному невзвешенному графу $G$, в котором из любой вершины графа существует равная вероятность перемещения в любую соседнюю вершину, является взвешиваемой квазиметрикой, т.е. существует весовая функция $w: V\rightarrow\mathbb{R}_{\ge 0}$, такая, что для всех $i,j\in V$ имеет место сотношение $ m(i,j)+w_i= m(j,i)+w_j. $ Менее изучены, но не менее интересны связи квазиметрики среднего времени первого прохода с другими метрическими структурами на графах, в частности, с $\alpha$-метрикой леса и ее вариациями.
Наконец, в пятом разделе рассмотрены примеры построения и исследования квазиметрики среднего времени первого прохода. Помимо иллюстрации "графовой" процедуры построения матрицы $M$, представлены рекуррентные алгоритмы исследования и проанализированы получающиеся при этом обобщенные метрические структуры.

Ключевые слова: цепь Маркова, среднее время первого прохода, остовной входящий корневой лес ориентированного графа, квазиметрика, квазиметрика среднего времени первого прохода, метрика леса.

DOI: https://doi.org/10.22405/2226-8383-2018-21-1-145-164

Полный текст: PDF файл (706 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.1

Образец цитирования: Е. И. Деза, Б. Мханна, “О специальных свойствах некоторых квазиметрик”, Чебышевский сб., 21:1 (2020), 145–164

Цитирование в формате AMSBIB
\RBibitem{DezMha20}
\by Е.~И.~Деза, Б.~Мханна
\paper О специальных свойствах некоторых квазиметрик
\jour Чебышевский сб.
\yr 2020
\vol 21
\issue 1
\pages 145--164
\mathnet{http://mi.mathnet.ru/cheb865}
\crossref{https://doi.org/10.22405/2226-8383-2018-21-1-145-164}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb865
  • http://mi.mathnet.ru/rus/cheb/v21/i1/p145

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:41
    Полный текст:21
    Литература:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021