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

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

Определение [ править ]

Предположим , G некоторый граф и некоторый путь длины п на G . Другими словами, это такие вершины графа G , что и соединены ребром. Тогда стирание цикла - это новый простой путь, созданный путем стирания всех циклов в хронологическом порядке. Формально индексы мы определяем индуктивно, используя${\ displaystyle \ gamma}$${\ Displaystyle \ гамма (1), \ точки, \ гамма (п)}$${\ Displaystyle \ гамма (я)}$${\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" здесь означает до длины пути . Индукция прекращается, когда для некоторых мы имеем . Предположим, это происходит в точке J, т.е. последней . Тогда стирание цикла , обозначаемое - это простой путь длины J, определяемый формулой${\displaystyle \gamma }$${\displaystyle i_{j}}$${\displaystyle \gamma (i_{j})=\gamma (n)}$${\displaystyle i_{J}}$${\displaystyle i_{j}}$${\displaystyle \gamma }$${\displaystyle \mathrm {LE} (\gamma )}$

${\displaystyle \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 ^2, а R - случайное блуждание, начинающееся из точки (0,0). Пусть T будет временем, когда R впервые попадает в круг радиуса 100 (мы, конечно, подразумеваем здесь дискретный круг). LE ( R ) называется случайным блужданием с удалением цикла, начиная с точки (0,0) и заканчивая кругом.

Единое остовное дерево [ править ]

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

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

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

Лапласовское случайное блуждание [ править ]

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

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

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

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

Если f определено, выберите использование f для соседей с весами. Другими словами, если это соседи, выбирайте с вероятностью${\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})}}.}$

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

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

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

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

Сетки [ править ]

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

Высокие размеры [ править ]

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

Два измерения [ править ]

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

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

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

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

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

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

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

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

Три измерения [ править ]

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

• Ричард Кеньон, Асимптотический определитель дискретного лапласиана , Acta Math. 185: 2 (2000), 239-286, онлайн-версия .
• Ричард Кеньон, Конформная инвариантность мозаики домино , Ann. Вероятно. 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. DOI : 10.1215 / S0012-7094-80-04741-9 .
• Грегори Ф. Лоулер, Логарифмическая поправка для случайного блуждания со стиранием петли в четырех измерениях , Труды конференции в честь Жан-Пьера Кахана ( Орсе , 1993). Специальный выпуск J. Fourier Anal. Appl., 347-362.
• Грегори Ф. Лоулер, Одед Шрамм, Венделин Вернер , Конформная инвариантность плоских случайных блужданий со стиранием петель и однородных остовных деревьев , Ann. Вероятно. 32: 1B (2004), 939-995, онлайн-версия .
• Робин Пемантл, Выбор остовного дерева для целочисленной решетки равномерно , Ann. Вероятно. 19: 4 (1991), 1559–1574.
• Одед Шрамм , пределы масштабирования случайных блужданий со стиранием петель и равномерные остовные деревья , Israel J. Math. 118 (2000), 221-288.
• Дэвид Брюс Уилсон, Генерация случайных остовных деревьев быстрее, чем время покрытия , Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений (Филадельфия, Пенсильвания, 1996), 296-303, ACM, Нью-Йорк, 1996.