Случайные блуждания: связь с резистивным расстоянием (часть 2)
В этой статье рассмотрим теоретические основы случайных блужданий.
Первая часть доступна тут.
Введение
Случайное блуждание на графе представляет собой процесс, при котором на каждом шаге изменяется состояние случайного процесса, заключающееся в перемещении из текущей вершины в одну из соседних вершин, выбранную независимым образом с равной вероятностью.
Цель изучения случайных блужданий заключается в их универсальности и применимости к широкому спектру задач в науке и технике.
Они предоставляют мощные инструменты для моделирования, анализа и решения сложных проблем, связанных с неопределенностью и случайностью.
Теоретические основы случайных блужданий
Рассмотрим однородное случайное блуждание, при котором вероятность перехода из вершины в любую соседнюю вершину одинакова и равна (1/d (x)),
где — степень вершины
.
Для начала определим сценарий, который будет полезен в доказательстве нескольких теорем.
Сценарий A: Подадим на каждый узел сети ток, равный количеству связей этого узла. Выберем узел
и получим из него ток, равный
, где
— количество связей в сети.
Выбор количества тока обусловлен тем фактом, что сумма количества связей каждой вершины даст число, равное удвоенному количеству связей в цепи.
Для любых двух вершин и
графа
время попадания (hitting time,
) определяется, как математическое ожидание или же среднее количество шагов (steps) случайного блуждания, необходимое для достижения вершины
из вершины
.
Время возвращения (commute time) между двумя вершинами
и
в графе
равно сумме времени попадания из вершины
в вершину
и времени попадания из
в
.
Теорема о времени первого попадания
При сценарии А разность потенциалов между узлами
и
равна среднему времени попадания в вершину
из вершины
(
):
Доказательство
Выберем начальный узел и конечный узел
. В соответствии со вторым законом Кирхгофа, законом Ома и тем фактом, что все сопротивления проводников равны единице, имеем следующее:
Разложим сумму разности на разность сумм. Заметим, что не зависит от индекса z. Следовательно, суммирование
будет производиться столько раз, какую степень имеет вершина
. Тогда, формула перепишется так:
Решая уравнение, относительно , получим следующее:
Введем дополнительное условие для случая :
Из курса теории вероятности очевидно, что среднее время попадания из вершины в вершину
(
) равно среднему времени попадания из смежных с
вершин до вершины
плюс один (один шаг до смежной вершины).
Установим условие для
Заметим, что формулы для напряжения и hitting time идентичны, т.к. являются линейными системами с единственным решением.
Следовательно, получим:
Что и требовалось доказать.
Введём следующие определения.
Сценарий B: Сценарий B является схожим со сценарием A, за исключением того, что стоком будет являться вершина . Обозначим разность потенциалов сценария B за
, где
.
Используя теорему о времени первого попадания, сценарий B можно записать, как
Сценарий C: Подадим ток, равный на узел
, где
— количество связей цепи. Стоком будут являться все узлы сети. Обозначим разность потенциалов сценария C за
, где
.
Данный сценарий является обратным к сценарию B, т.к. изменение затронуло направление тока в сети. Поэтому мы получили:
Основываясь на этих определениях и теореме о времени первого попадания докажем следующую теорему.
Теорема о времени возвращения
Время возвращения из вершины через вершину
графа
равно удвоенному количеству ребер
графа
, умноженному на сопротивление
.
Доказательство
Для доказательства этой теоремы используем сумму сценариев A и C. Другими словами, подадим ток на вершину
и получим его с вершины
. Обозначим разность потенциалов в этом случае за
:
По теореме о времени попадания и исходя из определения сценариев A и C получим:
Заметим, что является разностью потенциалов для перемещения тока
из узла
в узел
. Используя закон Ома имеем:
Тогда получаем:
Что и требовалось доказать.
Теперь, разобравшись с теоретическими аспектами изучаемых предметов, можно приступить к программной реализации. Этому и будет посвящена следующая глава.