Случайное блуждание со стиранием цикла

Случайное блуждание со стиранием цикла в 2D для $10^{6}$ шаги.

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

Определение

Предположим, что G — некоторый граф и $\gamma$ некоторый путь длины n на G. — Другими словами, $\gamma (1),\dots ,\gamma (n)$ являются вершинами графа G такими, что $\gamma (i)$ и $\gamma (i+1)$соединены ребром. Затем стирание циклическое $\gamma$ — это новый простой путь, созданный путем стирания всех петель $\gamma$в хронологическом порядке. Формально определим индексы $i_{j}$ индуктивно с использованием

$i_{1}=1\,$

$i_{j+1}=\max\{k:\gamma (k)=\gamma (i_{j})\}+1\,$

где «макс» здесь означает длину пути $\gamma$. Индукция прекращается, когда в течение некоторого времени $i_{j}$ у нас есть $\gamma (i_{j})=\gamma (n)$.

Словом, найти $i_{j+1}$, мы держим $\gamma (i_{j})$ в одной руке, а другой рукой прослеживаем с конца: $\gamma (n),\gamma (n-1),...$, пока мы либо не нажмем что-нибудь $\gamma (k)=\gamma (i_{j})$, и в этом случае мы устанавливаем $i_{j+1}=k$, или мы окажемся в $\gamma (i_{j})$, и в этом случае мы устанавливаем $i_{j+1}=i_{j}+1$.

Предположим, что это происходит в точке J ie $i_{J}$ это последний $i_{j}$. Затем циклическое стирание $\gamma$, обозначенный $\mathrm {LE} (\gamma )$ — простой путь длины J, определяемый формулой

$\mathrm {LE} (\gamma )(j)=\gamma (i_{j}).\,$

Теперь пусть G — некоторый граф, пусть v — вершина G и R — случайное блуждание по G, начиная с v . Пусть T некоторое время остановки для R. — Затем случайное блуждание со стиранием цикла до тех пор, пока время T не станет LE( R ([1, T ])). Другими словами, возьмите R от его начала до T — это (случайный) путь — сотрите все петли в хронологическом порядке, как указано выше — вы получите случайный простой путь.

Время остановки T может быть фиксированным, т.е. можно выполнить n шагов, а затем выполнить циклическое стирание. Однако обычно более естественно принять T за время попадания в некотором наборе. Например, пусть G — граф Z ² и пусть 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 . Стирание цикла случайного блуждания и обратное блуждание, как правило, не дают одного и того же результата, но согласно этому результату распределения двух блужданий со стиранием цикла идентичны.

Лапласовское случайное блуждание

Другое представление случайного блуждания со стертым циклом вытекает из решений дискретного уравнения Лапласа . Пусть G снова является графом, а и w — двумя вершинами в G. v Постройте случайный путь от v до w индуктивно, используя следующую процедуру. Предположим, мы уже определили $\gamma (1),...,\gamma (n)$. Пусть f — функция из G в R , удовлетворяющая

$f(\gamma (i))=0$ для всех $i\leq n$ и $f(w)=1$

f дискретно гармоничен везде

Где функция f на графике является дискретно гармонической в ​​точке x , если f ( x ) равна среднему значению f на соседях x .

Если f определено, выберите $\gamma (n+1)$ используя f у соседей $\gamma (n)$как весы. Другими словами, если $x_{1},...,x_{d}$ это соседи, выбирай $x_{i}$ с вероятностью

${\frac {f(x_{i})}{\sum _{j=1}^{d}f(x_{j})}}.$

Продолжая этот процесс, пересчитывая f на каждом шаге, в результате получаем случайный простой путь от v до w ; распределение этого пути идентично распределению случайного блуждания со стиранием цикла от v до w .

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

Важно отметить, что, хотя доказательство эквивалентности довольно просто, модели, включающие динамически изменяющиеся гармонические функции или меры, обычно чрезвычайно сложны для анализа. Практически ничего не известно о p-лапласовом блуждании или диффузионно-ограниченной агрегации . Еще одна несколько связанная модель — Harmonic Explorer .

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

Сетки

Пусть d — размерность, которую мы будем считать не менее 2. Исследуйте Z ^д то есть все точки $(a_{1},...,a_{d})$ с целым числом $a_{i}$. Это бесконечный граф степени 2d, если каждую точку соединить с ближайшими соседями. С этого момента мы будем рассматривать случайное блуждание со стиранием цикла на этом графе или его подграфах.

Большие размеры

Самый простой случай для анализа — размерность 5 и выше. В этом случае получается, что пересечения там только локальные. Расчет показывает, что если взять случайное блуждание длиной n , его циклическое стирание будет иметь длину того же порядка, то есть n . При соответствующем масштабировании оказывается, что случайное блуждание со стиранием цикла сходится (в соответствующем смысле) к броуновскому движению при стремлении n к бесконечности. Измерение 4 сложнее, но общая картина остается верной. Оказывается, циклическое стирание случайного блуждания длины n имеет примерно $n/\log ^{1/3}n$ вершин, но опять-таки после масштабирования (учитывающего логарифмический коэффициент) блуждание со стертым циклом сходится к броуновскому движению.

Два измерения

В двух измерениях аргументы конформной теории поля и результаты моделирования привели к ряду интересных гипотез. Предположим, что D — некоторая односвязная область на плоскости, а — точка в D. x граф G Возьмем

$G:=D\cap \varepsilon \mathbb {Z} ^{2},$

то есть сетка с длиной стороны ε, ограниченная D . Пусть v вершина графа G. ближайшая к x — Теперь рассмотрим случайное блуждание со стертым циклом, начинающееся с v и остановленное при достижении «границы» G , то есть вершин G которые соответствуют границе D. , Тогда предположения

• Когда ε стремится к нулю, распределение пути сходится к некоторому распределению на простых путях от x до границы D (конечно, в отличие от броуновского движения - в двух измерениях пути броуновского движения не являются простыми). Это распределение (обозначим его через $S_{D,x}$) называется пределом масштабирования случайного блуждания со стиранием цикла.
• Эти распределения конформно инвариантны . А именно, если φ — отображение Римана между D и второй областью E , то

$\phi (S_{D,x})=S_{E,\phi (x)}.\,$

• Хаусдорфова размерность этих путей почти наверняка равна 5/4 .

Первая атака на эти предположения исходила со стороны игры в домино . Взяв остовное дерево G и добавив к нему его планарный двойственный элемент, можно получить мозаику домино специального производного графа (назовем его H ). Каждая вершина H соответствует вершине, ребру или грани G , а ребра H показывают, какая вершина лежит на каком ребре и какое ребро на какой грани. Оказывается, что выбор равномерного остовного дерева G приводит к равномерно распределенному случайному разбиению домино H . Число разбиений графа на домино можно вычислить с помощью определителя специальных матриц, позволяющих связать его с дискретной функцией Грина , которая является приблизительно конформно-инвариантной. Эти аргументы позволили показать, что некоторые измеримые величины случайного блуждания со стиранием цикла (в пределе) конформно инвариантны и что ожидаемое число вершин в случайном блуждании со стиранием цикла, остановленном на круге радиуса r , имеет порядок $r^{5/4}$.

В 2002 году эти гипотезы были решены (положительно) с помощью Stochastic Löwner Evolution . Грубо говоря, это стохастическое конформно-инвариантное обыкновенное дифференциальное уравнение , которое позволяет уловить марковское свойство случайного блуждания со стиранием цикла (и многих других вероятностных процессов).

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

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

$cr^{1+\varepsilon }\leq L(r)\leq Cr^{5/3}\,$

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

Ссылки

• Кеньон, Ричард (2000a), «Асимптотический определитель дискретного лапласиана», Acta Mathematica , 185 (2): 239–286, arXiv : math-ph/0011042 , doi : 10.1007/BF02392811
• Кеньон, Ричард (апрель 2000 г.), «Конформная инвариантность мозаики домино», Annals of Probability , 28 (2): 759–795, arXiv : math-ph/9910002 , doi : 10.1214/aop/1019160260
• Кеньон, Ричард (март 2000 г.), «Дальние свойства остовных деревьев» , Журнал математической физики , 41 (3): 1338–1363, Бибкод : 2000JMP....41.1338K , doi : 10.1063/1.533190 , заархивировано из оригинал от 13 ноября 2004 г.
• Козма, Гади (2007), «Предел масштабирования случайного блуждания со стиранием цикла в трех измерениях», Acta Mathematica , 199 (1): 29–152, arXiv : math.PR/0508344 , doi : 10.1007/s11511-007- 0018-8
• Лоулер, Грегори Ф. (сентябрь 1980 г.), «Случайное блуждание с самоизбеганием», Duke Mathematical Journal , 47 (3): 655–693, doi : 10.1215/S0012-7094-80-04741-9
• Лоулер, Грегори Ф. , «Логарифмическая поправка для случайного блуждания со стиранием цикла в четырех измерениях», Материалы конференции в честь Жана-Пьера Кахане ( Орсе , 1993). Специальный выпуск журнала анализа и приложений Фурье , стр. 347–362, ISBN.  9780429332838
• Лоулер, Грегори Ф. (1999), «Случайное блуждание со стиранием цикла», в Брэмсоне, Мори; Дарретт, Ричард Т. (ред.), Загадочные проблемы вероятности: Festschrift в честь Гарри Кестена , Progress in Probability, vol. 44, Биркхойзер, Бостон, Массачусетс, стр. 197–217, номер документа : 10.1007/978-1-4612-2168-5 , ISBN.  978-1-4612-7442-1
• Лоулер, Грегори Ф .; Шрамм, Одед ; Вернер, Венделин (2004), «Конформная инвариантность плоских случайных блужданий со стиранием цикла и однородных остовных деревьев», Annals of Probability , 32 (1B): 939–995, arXiv : math.PR/0112234 , doi : 10.1214/aop/ 1079021469
• Пемантл, Робин (1991), «Равномерный выбор остовного дерева для целочисленной решетки», Annals of Probability , 19 (4): 1559–1574, arXiv : math/0404043 , doi : 10.1214/aop/1176990223
• Шрамм, Одед (2000), «Пределы масштабирования случайных блужданий со стиранием цикла и однородных остовных деревьев», Israel Journal of Mathematics , 118 : 221–288, arXiv : math.PR/9904022 , doi : 10.1007/BF02803524
• Уилсон, Дэвид Брюс (1996), «Генерация случайных остовных деревьев быстрее, чем время покрытия», STOC '96: Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений (Филадельфия, Пенсильвания, 1996) , Ассоциация вычислительной техники Machinery, Нью-Йорк, стр. 296–303, doi : 10.1145/237814.237880 , S2CID   207198080 .
• Уилсон, Дэвид Брюс (2010), «Размерность случайного блуждания со стиранием цикла в трех измерениях», Physical Review E , 82 (6): 062102, arXiv : 1008.1147 , Bibcode : 2010PhRvE..82f2102W , doi : 10.1103/PhysRevE. 82.062102 , ПМИД   21230692