Перколяция первого прохода

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

Введение

Перколяция первого прохода — одна из наиболее классических областей теории вероятностей . Впервые она была представлена Джоном Хаммерсли и Домиником Уэлшем в 1965 году как модель течения жидкости в пористой среде. ^[1] Это часть теории перколяции, и классическую перколяцию Бернулли можно рассматривать как подмножество перколяции первого прохода.

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

Математика

Как и в теории перколяции в целом, многие проблемы, связанные с перколяцией первого прохода, включают поиск оптимальных маршрутов или оптимального времени. Модель определяется следующим образом. ^[2] Позволять $G$ быть графиком . Помещаем неотрицательную случайную величину $t(e)$ , называемое временем прохождения ребра $e$ , на каждом ближайшем ребре графа $G$ . Коллекция $t(e)$ обычно предполагается независимым, одинаково распределенным, но существуют варианты модели. Случайная величина $t(e)$ интерпретируется как время или стоимость, необходимые для прохождения ребра $e$ .

Поскольку каждое ребро в перколяции первого прохода имеет свой собственный вес (или время), мы можем записать общее время пути как сумму весов каждого ребра на пути. ^[3]

T(\gamma )=\sum _{i\in \gamma }t(e_{i}).

Даны две вершины $x,y$ из $G$ затем один устанавливает

T(x,y)=\inf _{\gamma }T(\gamma ),

где нижняя грань проходит по всем конечным путям, начинающимся с $x$ и закончить на $y$ .Функция $T$ индуцирует случайную псевдометрику на $G$ .

Самая известная модель перколяции первого прохода находится на решетке. $\mathbb {Z} ^{d}$ . Один из самых громких вопросов: «Как выглядит шар большого радиуса?». Этот вопрос был поднят в оригинальной статье Хаммерсли и Уэлша в 1969 году и породил теорему Кокса-Дарретта о предельной форме в 1981 году. ^[4] Хотя теорема Кокса-Дарретта обеспечивает существование предельной формы, известны не многие свойства этого набора. Например, ожидается, что при мягких предположениях это множество должно быть строго выпуклым. По состоянию на 2016 год лучшим результатом является существование точки дифференцируемости Оффингера-Дамрона в случае плоского края Кокса-Лиггетта. ^[5]

Есть также несколько конкретных примеров перколяции первого прохода, которые можно смоделировать с помощью цепей Маркова . Например: полный граф можно описать с помощью цепей Маркова и рекурсивных деревьев. ^[6] а полосы шириной 2 можно описать с помощью цепи Маркова и решить с помощью цепи Харриса . ^[7]

Приложения

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

Помимо математики, модель роста Идена используется для моделирования роста бактерий и отложения материала. Другой пример - сравнение минимизированной стоимости аукциона Викри-Кларка-Гроувса (аукцион VCG) с минимизированным путем от перколяции первого прохода, чтобы оценить, насколько пессимистичным является аукцион VCG на своем нижнем пределе. Обе проблемы решаются одинаково, и можно найти распределения, которые можно использовать в теории аукционов.

Ссылки

^ Хаммерсли, Дж. М.; Валлийский, DJA (1965). «Перколяция первого прохода, субаддитивные процессы, стохастические сети и обобщенная теория восстановления». Бернулли 1713 Байес 1763 Лаплас 1813 . стр. 61–110. дои : 10.1007/978-3-642-99884-3_7 . ISBN 978-3-540-03260-1 .
^ Ауффингер, А.; Дамрон, М.; Хэнсон, Дж. (2016). «50 лет просачивания первого прохода». arXiv : 1511.03262 [ мат.PR ].
^ Кестен, Х. (1987). «Теория перколяции и перколяция первого прохода» . Анналы вероятности . 15 (4): 1231–1271. дои : 10.1214/аоп/1176991975 .
^ Кокс, Дж.; Дарретт, Рик (1981). «Некоторые предельные теоремы для перколяции с необходимыми и достаточными условиями» . Анналы вероятности . 9 (4): 583–603. дои : 10.1214/aop/1176994364 .
^ Ауффингер, А.; Дамрон, М. (2013). «Дифференцируемость на краю предельной формы и связанные с ней результаты при перкоалгировании при первом прохождении». Теория вероятностей и смежные области . 156 : 193–227. arXiv : 1105.4172 . дои : 10.1007/s00440-012-0425-4 . S2CID 119643007 .
^ Ван Дер Хофстад, Р.; Хугимстра, Г.; Ван Мигем, П. «Перколяция первого прохода на случайном графе» (PDF) . ewi.tudelft.nl . Делфтский технологический университет . Проверено 17 ноября 2014 г.
^ Флаксман, А.; Гамарник Д.; Соркин, Г. «Просачивание при первом проходе на полосе шириной 2 и стоимость пути на аукционе VCG» (PDF) . math.cmu.edu . КМУ . Проверено 15 ноября 2014 г.

[1] Хаммерсли, Дж. М.; Валлийский, DJA (1965). «Перколяция первого прохода, субаддитивные процессы, стохастические сети и обобщенная теория восстановления». Бернулли 1713 Байес 1763 Лаплас 1813 . стр. 61–110. дои : 10.1007/978-3-642-99884-3_7 . ISBN 978-3-540-03260-1 .

[2] Ауффингер, А.; Дамрон, М.; Хэнсон, Дж. (2016). «50 лет просачивания первого прохода». arXiv : 1511.03262 [ мат.PR ].

[3] Кестен, Х. (1987). «Теория перколяции и перколяция первого прохода» . Анналы вероятности . 15 (4): 1231–1271. дои : 10.1214/аоп/1176991975 .

[4] Кокс, Дж.; Дарретт, Рик (1981). «Некоторые предельные теоремы для перколяции с необходимыми и достаточными условиями» . Анналы вероятности . 9 (4): 583–603. дои : 10.1214/aop/1176994364 .

[5] Ауффингер, А.; Дамрон, М. (2013). «Дифференцируемость на краю предельной формы и связанные с ней результаты при перкоалгировании при первом прохождении». Теория вероятностей и смежные области . 156 : 193–227. arXiv : 1105.4172 . дои : 10.1007/s00440-012-0425-4 . S2CID 119643007 .

[6] Ван Дер Хофстад, Р.; Хугимстра, Г.; Ван Мигем, П. «Перколяция первого прохода на случайном графе» (PDF) . ewi.tudelft.nl . Делфтский технологический университет . Проверено 17 ноября 2014 г.

[7] Флаксман, А.; Гамарник Д.; Соркин, Г. «Просачивание при первом проходе на полосе шириной 2 и стоимость пути на аукционе VCG» (PDF) . math.cmu.edu . КМУ . Проверено 15 ноября 2014 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]