Введение

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

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

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

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

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

Сценарий A: Подадим на каждый узел сети ток, равный количеству связей этого узла d(x) . Выберем узел и получим из него ток, равный $2m = \sum_x d(x)$ , где - количество связей в сети.

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

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

$H_{xy} = {\mathbb{E}} [\text{steps}]$

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

$C_{xy} = H_{xy} + H_{yx}$

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

При сценарии А разность потенциалов $\phi_{xy}$ между узлами и равна среднему времени попадания в вершину из вершины ( $H_{xy}$ ):

$\phi_{xy} = H_{xy}$

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

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

$d(x) = \sum_{z}^{\sim x} (\phi_{xy} - \phi_{zy})$

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

$d(x) = d(x) \cdot \phi_{xy} - \sum_{z}^{\sim x} \phi_{zy}$

Решая уравнение, относительно $\phi_{xy}$ , получим следующее:

$\phi_{xy} = 1 + \frac{1}{d(x)} \sum_{z}^{\sim x} \phi_{zy}$

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

$\phi_{xy} = \begin{cases} 0 & x = y \\ 1 + \frac{1}{d(x)} \sum\limits_{z}^{\sim x} \phi_{zy} & x \neq y \end{cases}$

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

$H_{xy} = 1 + \frac{1}{d(x)} \sum_{z}^{\sim x} H_{zy}$

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

$H_{xy} = \begin{cases} 0 & x = y \\ 1 + \frac{1}{d(x)} \sum\limits_{z}^{\sim x} H_{zy} & x \neq y \end{cases}$

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

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

$H_{xy} = \phi_{xy}$

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

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

Сценарий B: Сценарий B является схожим со сценарием A, за исключением того, что стоком будет являться вершина . Обозначим разность потенциалов сценария B за $\phi_{yx}'$ , где $x,y \in V(G)$ .
Используя теорему о времени первого попадания, сценарий B можно записать, как

$\phi_{yx}' = H_{yx}$

Сценарий C: Подадим ток, равный на узел , где - количество связей цепи. Стоком будут являться все узлы сети. Обозначим разность потенциалов сценария C за $\phi_{xy}''$ , где $x,y \in V(G)$ .
Данный сценарий является обратным к сценарию B, т.к. изменение затронуло направление тока в сети. Поэтому мы получили:

$\phi_{xy}''=\phi_{yx}' = H_{yx}$

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

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

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

$C_{xy} = 2mR_{xy}$

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

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

$\phi_{xy} '''= \phi_{xy} + \phi_{yx}''$

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

$\phi_{xy} '''= H_{xy} + H_{yx}$

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

$\phi_{xy}''' = 2mR_{xy}$

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

$H_{xy} + H_{yx} = 2mR_{xy} \Rightarrow C_{xy} = 2mR_{xy}$

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

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

Случайные блуждания: связь с резистивным расстоянием (часть 2)