В математике , петля-стерто блуждание является моделью для случайного простого пути с важными приложениями в комбинаторике , и в физике , квантовой теорией поля . Он тесно связан с однородным остовным деревом , моделью случайного дерева . См. Также случайное блуждание для более общей трактовки этой темы.
Определение
Предположим, что G - некоторый граф инекоторый путь длины п на G . Другими словами,- вершины графа G такие, что а также связаны ребром. Затем цикл стирания из это новый простой путь, созданный стиранием всех циклов в хронологическом порядке. Формально мы определяем индексы индуктивно используя
где "max" здесь означает до длины пути . Индукция прекращается, когда для некоторых у нас есть . Предположим, что это происходит в точке J ie. последний . Затем циклическое стирание, обозначаемый - простой путь длины 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, удовлетворяющая
- для всех а также
- f дискретно гармоничен всюду
Где функция f на графике дискретно гармонична в точке x, если f ( x ) равна среднему значению f на соседях x .
С определенным f выберитеиспользуя f у соседейкак веса. Другими словами, если это соседи, выбирайте с вероятностью
Продолжая этот процесс, пересчитывая f на каждом шаге, в результате получается случайный простой путь от v к w ; распределение этого пути идентично распределению случайного блуждания со стиранием цикла от v до w .
Альтернативная точка зрения состоит в том, что распределение случайного блуждания с удаленным циклом, при условии, что оно начинается на некотором пути β, идентично стиранию цикла случайного блуждания с условием, чтобы оно не достигало β. Это свойство часто называют марковским свойством случайного блуждания со стиранием петель (хотя связь с обычным марковским свойством несколько расплывчата).
Важно отметить, что, хотя доказательство эквивалентности довольно просто, модели, которые включают динамически изменяющиеся гармонические функции или меры, обычно чрезвычайно трудно анализировать. Практически ничего не известно о p-лапласовском блуждании или агрегации, ограниченной диффузией . Другая несколько родственная модель - это исследователь гармоник .
Наконец, следует упомянуть еще одну ссылку: теорема Кирхгофа связывает количество остовных деревьев графа G с собственными значениями дискретного лапласиана . Подробности см. В связующем дереве .
Сетки
Пусть d - размерность, которую мы будем считать не менее 2. Рассмотрим Z d, т.е. все точки. с целым числом . Это бесконечный граф со степенью 2 d, когда вы соединяете каждую точку с ее ближайшими соседями. С этого момента мы будем рассматривать случайное блуждание со стиранием петель на этом графе или его подграфах.
Высокие габариты
Самый простой для анализа случай - размерность 5 и выше. В этом случае оказывается, что там пересечения только локальные. Расчет показывает, что если взять случайное блуждание длиной n , его стирание цикла будет иметь длину того же порядка величины, то есть n . При соответствующем масштабировании оказывается, что случайное блуждание со стиранием цикла сходится (в соответствующем смысле) к броуновскому движению, когда n стремится к бесконечности. Размерность 4 более сложная, но общая картина все еще верна. Оказывается, что стирание петель случайного блуждания длины n имеет примерно вершин, но опять же, после масштабирования (с учетом логарифмического фактора) обход без петель сходится к броуновскому движению.
Два измерения
В двух измерениях аргументы конформной теории поля и результаты моделирования привели к ряду захватывающих гипотез. Пусть D некоторый односвязный домен в плоскости и х есть точка D . Возьмем граф G как
то есть, сетка длиной стороны Е ограничена D . Пусть v вершина из G , ближайшего к й . Проверьте теперь петлю стертым блуждание , начиная с V и остановился при ударе «граница» из G , то есть вершины G , которые соответствуют границе D . Тогда предположения таковы.
- Когда ε стремится к нулю, распределение пути сходится к некоторому распределению на простых путях от x до границы D (конечно, в отличие от броуновского движения - в двух измерениях пути броуновского движения непросты). Это распределение (обозначим его через) называется пределом масштабирования случайного блуждания со стиранием цикла.
- Эти распределения конформно инвариантны . А именно, если φ - отображение Римана между D и второй областью E, то
- Хаусдорфову этих путей является 5/4 почти наверняка .
Первая атака на эти предположения произошла со стороны мозаики домино . Принимая остовного дерева G и добавляя к нему свою плоскую двойственную один получает домино разбиении специального производного графа (назовем его Н ). Каждая вершина H соответствует вершине, ребру или грани G , а ребра H показывают, какая вершина лежит на каком ребре и какое ребро на какой грани. Оказывается, что , принимая равномерное остове G приводит к равномерно распределенному случайному Домино черепицы из H . Количество домино-мозаик графа можно вычислить с помощью определителя специальных матриц, которые позволяют связать его с дискретной функцией Грина, которая приблизительно конформно инвариантна. Эти аргументы позволили показать, что некоторые измеримые величины случайного блуждания со стиранием цикла являются (в пределе) конформно-инвариантными, и что ожидаемое количество вершин в случайном блуждании со стиранием цикла, остановленном на окружности радиуса r, имеет порядок. [1]
В 2002 году эти гипотезы были разрешены (положительно) с помощью стохастической эволюции Лёвнера . Грубо говоря, это стохастическое конформно-инвариантное обыкновенное дифференциальное уравнение, которое позволяет уловить марковское свойство случайного блуждания со стиранием петель (и многих других вероятностных процессов).
Три измерения
Предел масштабирования существует и инвариантен относительно поворотов и растяжений. [2] Еслиобозначает ожидаемое количество вершин в случайном блуждании со стиранием цикла, пока оно не достигнет расстояния r , тогда
где ε, c и C - некоторые положительные числа [3] (числа в принципе можно вычислить из доказательств, но автор этого не сделал). Это предполагает, что предел масштабирования должен иметь размерность Хаусдорфа междуи 5/3 почти наверняка. Численные эксперименты показывают, что это должно быть. [4]
Заметки
- Перейти ↑ Kenyon, R. (2000). Асимптотический определитель дискретного лапласиана. Acta Mathematica, 185 (2), 239-286.
- ^ Козьма, Гэди (2007) "Предел масштабирования случайного блуждания со стиранием цикла в трех измерениях", Acta Mathematica , 199 (1), 29–152 doi : 10.1007 / s11511-007-0018-8 препринт
- ↑ Лоулер, Грегори Ф. (1999) «Случайное блуждание со стиранием петель», в сбивчивых проблемах вероятности: Festschrift в честь Гарри Кестена (М. Брамсон и Р. Т. Дарретт, ред.), Progr. Вероятн., Т. 44, Birkhäuser Boston, Boston, MA, 1999, стр. 197–217.
- ^ Уилсон, Дэвид Б. (2010) «Измерение случайного блуждания со стиранием петли в 3D», Physical Review E , 82 (6): 062102.
Рекомендации
- Ричард Кеньон, Асимптотический определитель дискретного лапласиана , 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.