Введение

Модель случайного простого пути

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

Определение

Предположим, что G – некоторый граф, а – некоторая траектория длины n на G. Другими словами, – это вершины G, такие что и соединены ребром. Тогда стертая петлями траектория – это новый простой путь, созданный путем удаления всех петель из в хронологическом порядке. Формально, мы определяем индексы индуктивно, используя

где "max" здесь означает до длины пути. Индукция останавливается, когда для некоторого у нас есть

Иными словами, чтобы найти , мы держим в одной руке, а другой рукой прослеживаем путь назад от конца: , пока мы либо не достигнем некоторого , в этом случае мы устанавливаем , либо не достигнем , в этом случае мы устанавливаем . Предположим, что это происходит в J, то есть – последний. Тогда стертая петлями траектория , обозначаемая , – это простой путь длины J, определяемый

Теперь пусть G – некоторый граф, v – вершина G, а R – случайное блуждание по G, начинающееся с v. Пусть T – некоторое время остановки для R. Тогда стертое петлями случайное блуждание до времени T – это LE(R([1,T])). Другими словами, возьмем R от начала до T – это (случайный) путь, удалим все петли в хронологическом порядке, как описано выше, – и получим случайный простой путь. Время остановки T может быть фиксированным, то есть можно выполнить n шагов, а затем стереть петли. Однако обычно более естественно выбирать T как время первого попадания в некоторое множество. Например, пусть G – граф Z2, а R – случайное блуждание, начинающееся в точке (0,0). Пусть T – время, когда R впервые достигает окружности радиуса 100 (мы подразумеваем, конечно, дискретизированную окружность). LE(R) называется стертым петлями случайным блужданием, начинающимся в (0,0) и останавливающимся на окружности.

Однородное рассеяние дерева

Для любого графа G, остовное дерево G является подграфом G, содержащим все вершины и некоторые из ребер, который является деревом, то есть связным и без циклов. Остовное дерево, выбранное случайным образом из всех возможных с равной вероятностью, называется однородным остовным деревом. Обычно существует экспоненциально много остовных деревьев (слишком много, чтобы сгенерировать их все, а затем выбрать одно случайным образом); вместо этого однородное остовное дерево может быть сгенерировано более эффективно алгоритмом, называемым алгоритмом Уилсона, который использует случайные блуждания с удалением циклов. Алгоритм выполняется следующим образом. Во-первых, постройте дерево, состоящее из одной вершины T, выбрав (произвольно) одну вершину. Затем, пока построенное до сих пор дерево T не включает все вершины графа, пусть v будет произвольной вершиной, не входящей в T, выполните случайное блуждание с удалением циклов от v до достижения вершины в T и добавьте полученный путь к T. Повторение этого процесса до включения всех вершин приводит к равномерно распределенному дереву, независимо от произвольного выбора вершин на каждом этапе. Верно и обратное утверждение. Если v и w – две вершины в G, то в любом остовном дереве они соединены единственным путем. Проходя по этому пути в однородном остовном дереве, мы получаем случайный простой путь. Оказывается, распределение этого пути идентично распределению случайного блуждания с удалением циклов, начинающегося в v и заканчивающегося в w. Этот факт можно использовать для обоснования корректности алгоритма Уилсона. Другим следствием является то, что случайное блуждание с удалением циклов симметрично относительно начальной и конечной точек. Более точно, распределение случайного блуждания с удалением циклов, начинающегося в v и заканчивающегося в w, идентично распределению обратного случайного блуждания с удалением циклов, начинающегося в w и заканчивающегося в v. Случайное блуждание с удалением циклов и обратное блуждание, как правило, не дают одного и того же результата, но согласно этому результату распределения двух блужданий с удалением циклов идентичны.

Решетки

Пусть d — размерность, которую мы будем считать не меньше 2. Рассмотрим Zd, то есть все точки с целыми координатами. Это бесконечный граф со степенью 2d, если соединить каждую точку с ее ближайшими соседями. Далее мы будем рассматривать случайное блуждание с удалением петель на этом графе или его подграфах.

Высокие размеры

Самый простой случай для анализа – размерность 5 и выше. В этом случае оказывается, что пересечения там только локальные. Расчет показывает, что если взять случайное блуждание длиной n, то его стирание циклов имеет длину того же порядка, то есть n. Соответственно масштабируя, получается, что стирание циклов случайного блуждания сходится (в подходящем смысле) к броуновскому движению при n, стремящемся к бесконечности. Четвертое измерение более сложное, но общая картина остаётся верной. Оказывается, что стирание циклов случайного блуждания длиной n имеет приблизительно вершин, но опять же, после масштабирования (учитывающего логарифмический фактор) стирание циклов блуждания сходится к броуновскому движению.

Двумерность

В двух измерениях аргументы из конформной теории поля и результаты моделирования привели к ряду интересных гипотез. Пусть D — некоторая простосвязная область на плоскости, а x — точка в D. Рассмотрим граф G, то есть сетку с длиной стороны ε, ограниченную областью D. Пусть v — вершина графа G, ближайшая к точке x. Исследуем теперь случайный блуждание со стертыми петлями, начинающееся из вершины v и останавливающееся при достижении "границы" G, то есть вершин G, соответствующих границе D. Тогда гипотезы заключаются в следующем: при стремлении ε к нулю распределение пути сходится к некоторому распределению на простых путях от x до границы D (в отличие от броуновского движения, конечно — в 2 измерениях пути броуновского движения не являются простыми). Это распределение (обозначим его ) называется пределом масштабирования случайного блуждания со стертыми петлями. Эти распределения являются конформно инвариантными. А именно, если φ — риманово отображение между D и другой областью E, то размерность Хаусдорфа этих путей почти наверняка равна 5/4. Первые попытки проверки этих гипотез исходили из области плиток домино. Если взять остовное дерево графа G и добавить к нему его планарный двойственный граф, то получится плитка домино специального производного графа (назовем его H). Каждая вершина H соответствует вершине, ребру или грани графа G, а ребра H показывают, какая вершина лежит на каком ребре и какое ребро на какой грани. Оказывается, что выбор равномерного остовного дерева G приводит к равномерно распределенной случайной плитке домино графа H. Количество плиток домино графа можно вычислить с помощью определителя специальных матриц, что позволяет связать его с дискретной функцией Грина, которая приблизительно конформно инвариантна. Эти аргументы позволили показать, что некоторые измеримые характеристики случайного блуждания со стертыми петлями (в пределе) конформно инвариантны, и что математическое ожидание числа вершин в случайном блуждании со стертыми петлями, остановленном на окружности радиуса r, имеет порядок В 2002 году эти гипотезы были разрешены (подтверждены) с использованием стохастической эволюции Лёнера. В общих чертах, это стохастическое конформно-инвариантное обыкновенное дифференциальное уравнение, которое позволяет уловить марковское свойство случайного блуждания со стертыми петлями (и многих других вероятностных процессов).

Три измерения

Предельное масштабирование существует и инвариантно относительно вращений и дилатаций. Если обозначает ожидаемое число вершин в случайном блуждании с удалением циклов до достижения расстояния r, то

где ε, c и C – некоторые положительные числа (эти числа, в принципе, могут быть вычислены из доказательств, но автор этого не сделал). Это указывает на то, что размерность Хаусдорфа предельного масштабирования должна быть между и 5/3 почти наверное. Численные эксперименты показывают, что она должна быть равна .