В этой статье рассмотрим теоретические основы случайных блужданий.

Первая часть доступна тут.

Введение

Случайное блуждание на графе представляет собой процесс, при котором на каждом шаге изменяется состояние случайного процесса, заключающееся в перемещении из текущей вершины в одну из соседних вершин, выбранную независимым образом с равной вероятностью.

Цель изучения случайных блужданий заключается в их универсальности и применимости к широкому спектру задач в науке и технике.
Они предоставляют мощные инструменты для моделирования, анализа и решения сложных проблем, связанных с неопределенностью и случайностью.

Теоретические основы случайных блужданий

Рассмотрим однородное случайное блуждание, при котором вероятность перехода из вершины в любую соседнюю вершину одинакова и равна (1/d(x)),
где - степень вершины .

Для начала определим сценарий, который будет полезен в доказательстве нескольких теорем.

Сценарий A: Подадим на каждый узел сети ток, равный количеству связей этого узла. Выберем узел и получим из него ток, равный , где - количество связей в сети.

Выбор количества тока обусловлен тем фактом, что сумма количества связей каждой вершины даст число, равное удвоенному количеству связей в цепи.

Для любых двух вершин и графа время попадания (hitting time, ) определяется, как математическое ожидание или же среднее количество шагов (steps) случайного блуждания, необходимое для достижения вершины из вершины .

Время возвращения (commute time) между двумя вершинами и в графе равно сумме времени попадания из вершины в вершину и времени попадания из в .

Теорема о времени первого попадания

При сценарии А разность потенциалов между узлами и равна среднему времени попадания в вершину из вершины ():

Доказательство

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

Разложим сумму разности на разность сумм. Заметим, что не зависит от индекса z. Следовательно, суммирование будет производиться столько раз, какую степень имеет вершина . Тогда,формула перепишется так:

Решая уравнение, относительно , получим следующее:

Введем дополнительное условие для случая :

Из курса теории вероятности очевидно, что среднее время попадания из вершины в вершину () равно среднему времени попадания из смежных с вершин до вершины плюс один (один шаг до смежной вершины).

Установим условие для

Заметим, что формулы для напряжения и hitting time идентичны, т.к. являются линейными системами с единственным решением.

Следовательно, получим:

Что и требовалось доказать.

Введём следующие определения.

Сценарий B: Сценарий B является схожим со сценарием A, за исключением того, что стоком будет являться вершина . Обозначим разность потенциалов сценария B за , где .
Используя теорему о времени первого попадания, сценарий B можно записать, как

Сценарий C: Подадим ток, равный на узел , где - количество связей цепи. Стоком будут являться все узлы сети. Обозначим разность потенциалов сценария C за , где .
Данный сценарий является обратным к сценарию B, т.к. изменение затронуло направление тока в сети. Поэтому мы получили:

Основываясь на этих определениях и теореме о времени первого попадания докажем следующую теорему.

Теорема о времени возвращения

Время возвращения из вершины через вершину графа равно удвоенному количеству ребер графа , умноженному на сопротивление .

Доказательство

Для доказательства этой теоремы используем сумму сценариев A и C. Другими словами, подадим ток на вершину и получим его с вершины . Обозначим разность потенциалов в этом случае за :

По теореме о времени попадания и исходя из определения сценариев A и C получим:

Заметим, что является разностью потенциалов для перемещения тока из узла в узел . Используя закон Ома имеем:

Тогда получаем:

Что и требовалось доказать.

Теперь, разобравшись с теоретическими аспектами изучаемых предметов, можно приступить к программной реализации. Этому и будет посвящена следующая глава.