Перколяция первого прохода - First passage percolation

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

Вступление

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

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

Математика

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

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

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

Учитывая две вершины ${\displaystyle x,y}$ из ${\displaystyle G}$ затем устанавливает

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

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

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

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

Приложения

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

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

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

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