Случайное блуждание со стиранием цикла - Loop-erased random walk

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

Определение

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

${\displaystyle i_{1}=1\,}$

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

где "max" здесь означает до длины пути ${\displaystyle \gamma }$. Индукция прекращается, когда для некоторых ${\displaystyle i_{j}}$ у нас есть ${\displaystyle \gamma (i_{j})=\gamma (n)}$. Предположим, это происходит в J т.е. ${\displaystyle i_{J}}$ последний ${\displaystyle i_{j}}$. Затем стирание цикла ${\displaystyle \gamma }$, обозначаемый ${\displaystyle \mathrm {LE} (\gamma )}$ это простой путь длины J определяется

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

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

Время остановки Т может быть фиксированным, т.е. можно выполнить п шаги, а затем цикл-стирание. Однако обычно более естественно принимать Т быть время удара в каком-то наборе. Например, пусть грамм быть графиком Z² и разреши р - случайное блуждание из точки (0,0). Позволять Т быть тем временем, когда р сначала попадает в круг радиуса 100 (мы, конечно, имеем в виду дискретизированный круг). LE (р) называется случайным блужданием с удалением цикла, начиная с точки (0,0) и заканчивая кругом.

Равномерное остовное дерево

Для любого графика грамм, а остовное дерево из грамм это подграф из грамм содержащий все вершины и некоторые ребра, что является дерево, т.е. связаны и без циклы. А остовное дерево выбирается случайным образом из всех возможных остовных деревьев с равной вероятностью называется равномерным остовным деревом. Обычно существует экспоненциально много остовных деревьев (слишком много, чтобы сгенерировать их все, а затем выбрать одно случайным образом); вместо этого однородные остовные деревья могут быть сгенерированы более эффективно с помощью алгоритма, называемого алгоритмом Вильсона, который использует случайные блуждания со стиранием цикла.

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

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

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

Другое представление случайного блуждания со стиранием петель происходит из решений дискретный Уравнение лапласа. Позволять грамм снова будет графом и пусть v и ш быть двумя вершинами в грамм. Построить случайный путь из v к ш индуктивно, используя следующую процедуру. Предположим, мы уже определили ${\displaystyle \gamma (1),...,\gamma (n)}$. Позволять ж быть функцией от грамм к р удовлетворение

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

ж дискретно гармонический где-либо еще

Где функция ж на графе дискретно гармонична в точке Икс если ж(Икс) равно среднему ж на соседей Икс.

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

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

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

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

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

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

Сетки

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

Высокие габариты

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

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

В двух измерениях аргументы из конформная теория поля и результаты моделирования привели к ряду захватывающих предположений. Предполагать D есть некоторые односвязный домен в самолете и Икс это точка в D. Возьмите график грамм быть

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

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

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

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

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

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

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

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

Предел масштабирования существует и инвариантен относительно поворотов и растяжений.^[2] Если ${\displaystyle L(r)}$ обозначает ожидаемое количество вершин в случайном блуждании с удалением цикла, пока оно не достигнет расстояния р, тогда

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

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

Примечания

1. Кеньон, Р. (2000). Асимптотический определитель дискретного лапласиана. Acta Mathematica, 185 (2), 239-286.
2. Козьма, Гади (2007) "Предел масштабирования случайного блуждания со стиранием цикла в трех измерениях", Acta Mathematica, 199 (1), 29–152 Дои:10.1007 / s11511-007-0018-8 препринт
3. Лоулер, Грегори Ф. (1999) «Случайное блуждание со стиранием цикла», в Непонятные проблемы вероятности: Festschrift в честь Гарри Кестена (М. Брамсон и Р. Т. Даррет, ред.), Progr. Вероятн., Т. 44, Birkhäuser Boston, Boston, MA, 1999, стр. 197–217.
4. Уилсон, Дэвид Б. (2010) «Измерение случайного блуждания со стиранием петель в 3D», Физический обзор E,82(6):062102.

Рекомендации

• Ричард Кеньон, Асимптотический определитель дискретного лапласиана, Acta Math. 185:2 (2000), 239-286, онлайн-версия.
• Ричард Кеньон, Конформная инвариантность мозаики домино, Анна. Вероятно. 28:2 (2000), 759-795, онлайн-версия.
• Ричард Кеньон, Дальнобойные свойства остовных деревьев, Вероятностные методы в равновесной и неравновесной статистической физике, J. Math. Phys. 41:3 (2000), 1338-1363, онлайн-версия.
• Гады Козьма, Предел масштабирования случайного блуждания со стиранием цикла в трех измерениях, Acta Math. 199:1 (2007), 29-152, онлайн-версия.
• Лоулер, Грегори Ф. (сентябрь 1980 г.). «Случайное блуждание с самоустраниением». Математический журнал герцога. 47 (3): 655–693. Дои:10.1215 / S0012-7094-80-04741-9.
• Грегори Ф. Лоулер, Логарифмическая поправка для случайного блуждания со стиранием петель в четырех измерениях, Материалы конференции в честь Жан-Пьера Кахана (Орсе, 1993). Специальный выпуск J. Fourier Anal. Appl., 347-362.
• Грегори Ф. Лоулер, Одед Шрамм, Венделин Вернер, Конформная инвариантность плоских случайных блужданий со стиранием петель и однородных остовных деревьев, Анна. Вероятно. 32: 1Б (2004), 939-995, онлайн-версия.
• Робин Пемантл, Выбор остовного дерева для целочисленной решетки равномерно, Анна. Вероятно. 19:4 (1991), 1559-1574.
• Одед Шрамм, Пределы масштабирования случайных блужданий со стиранием петель и однородных остовных деревьев, Израиль J. Math. 118 (2000), 221-288.
• Дэвид Брюс Уилсон, Генерация случайных остовных деревьев быстрее, чем время покрытия, Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений (Филадельфия, Пенсильвания, 1996), 296-303, ACM, Нью-Йорк, 1996.