Прогулка с самоизбеганием

Последовательность перемещений на решетке, которая не посещает одну и ту же точку более одного раза.

Самоизбегающее блуждание по квадратной решетке 15×15

Самоизбегающее блуждание по квадратной решетке 20x20, смоделированное с помощью последовательного Монте-Карло

Нерешенная задача по математике :

Существует ли формула или алгоритм, позволяющий вычислить количество самоизбегающих блужданий в любой заданной решетке?

(еще нерешенные проблемы по математике)

В математике самоизбегающий обход ( SAW ) — это последовательность ходов на решетке ( путь решетки ), которая не посещает одну и ту же точку более одного раза. Это особый случай теоретико -графового понятия пути . Самоизбегающий многоугольник ( SAP ) — это замкнутый самоизбегающий обход на решетке. Очень мало известно строго о самоизбегающем обходе с математической точки зрения, хотя физики выдвинули многочисленные гипотезы, которые считаются верными и убедительно подкреплены численным моделированием.

В вычислительной физике самоизбегающий блуждание — это цепообразный путь в R ² или R ³ с определенным числом узлов, обычно с фиксированной длиной шага и обладающий свойством не пересекать себя или другой блуждание. Система ПАВ удовлетворяет так называемому условию исключенного объема . В более высоких измерениях ПАВ, как полагают, ведет себя во многом как обычное случайное блуждание .

SAW и SAP играют центральную роль в моделировании топологического и теоретического поведения узлов нитевидных и петлеобразных молекул, таких как белки . Действительно, SAW, возможно, впервые были введены химиком Полом Флори ^{[1] [ сомнительно – обсудить ]} для моделирования реального поведения цепообразных сущностей, таких как растворители и полимеры , физический объем которых запрещает многократное занятие одной и той же пространственной точки.

SAW являются фракталами . Например, при d = 2 фрактальная размерность равна 4/3, при d = 3 она близка к 5/3, а при d ≥ 4 фрактальная размерность равна 2. Размерность называется верхней критической размерностью, выше которой исключенный объем пренебрежимо мал. SAW, которая не удовлетворяет условию исключенного объема, была недавно изучена для моделирования явной геометрии поверхности, возникающей в результате расширения SAW. ^{[2] [ необходимо разъяснение ]}

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

Вычисление числа самоизбегающих блужданий в любой заданной решетке является распространенной вычислительной проблемой . В настоящее время не существует известной формулы, хотя существуют строгие методы аппроксимации. ^{[3] [4]}

Универсальность

Одним из явлений, связанных с самоизбегающими блужданиями и моделями статистической физики в целом, является понятие универсальности , то есть независимости макроскопических наблюдаемых от микроскопических деталей, таких как выбор решетки. Одной из важных величин, которая появляется в гипотезах для универсальных законов, является константа связности , определяемая следующим образом. Пусть c _n обозначает число n -шаговых самоизбегающих блужданий. Поскольку каждое ( n + m ) -шаговое самоизбегающее блуждание может быть разложено на n -шаговое самоизбегающее блуждание и m -шаговое самоизбегающее блуждание, отсюда следует, что c _{n + m} ≤ c _n c _m . Следовательно, последовательность {log c _n } является субаддитивной , и мы можем применить лемму Фекете , чтобы показать, что существует следующий предел:

${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}.}$

μ называется константой связности , поскольку c _n зависит от конкретной решетки, выбранной для блуждания, так же как и μ . Точное значение μ известно только для гексагональной решетки, где оно равно: ^[5]

${\displaystyle {\sqrt {2+{\sqrt {2}}}}.}$

Для других решеток μ было только приближено численно и, как полагают, даже не является алгебраическим числом . Предполагается, что ^[6]

${\displaystyle c_{n}\approx \mu ^{n}n^{\frac {11}{32}}}$

при n → ∞ , где μ зависит от решетки, а поправка к степенному закону — нет; иными словами, этот закон считается универсальным. ${\displaystyle n^{\frac {11}{32}}}$

В сетях

Самоизбегающие блуждания также изучались в контексте теории сетей . ^[7] В этом контексте принято рассматривать SAW как динамический процесс, такой, что на каждом временном шаге гуляющий случайным образом прыгает между соседними узлами сети. Блуждание заканчивается, когда гуляющий достигает тупикового состояния, так что он больше не может продвигаться к новым непосещенным узлам. Недавно было обнаружено, что в сетях Эрдеша–Реньи распределение длин путей таких динамически выращенных SAW может быть вычислено аналитически и следует распределению Гомпертца . ^[8] Для произвольных сетей распределение длин путей блуждания, распределение степеней непосещенной сети и распределение времени первого попадания в узел могут быть получены путем решения набора связанных рекуррентных уравнений. ^[9]

Пределы

Рассмотрим равномерную меру на n -шаговых самоизбегающих блужданиях в полной плоскости. В настоящее время неизвестно, индуцирует ли предел равномерной меры при n → ∞ меру на бесконечных полноплоскостных блужданиях. Однако Гарри Кестен показал, что такая мера существует для самоизбегающих блужданий в полуплоскости. Одним из важных вопросов, связанных с самоизбегающими блужданиями, является существование и конформная инвариантность предела масштабирования , то есть предела, когда длина блуждания стремится к бесконечности, а сетка решетки стремится к нулю. Предполагается, что предел масштабирования самоизбегающего блуждания описывается эволюцией Шрамма–Лёвнера с параметром κ = ⁠8/3⁠ .

Смотрите также

• Критические явления  – Физика, связанная с критическими точками
• Гамильтонов путь  — путь в графе, который посещает каждую вершину ровно один раз.
• Ход конем  – Математическая задача, поставленная на шахматной доске
• Случайное блуждание  – процесс формирования пути из множества случайных шагов.
• Змейка  – Жанр видеоигр
• Универсальность  – свойства систем, не зависящие от динамических деталей.Страницы, отображающие описания викиданных в качестве резерва
• Кривые, заполняющие пространство – Все они являются самоизбегающими.

Ссылки

1. П. Флори (1953). Принципы химии полимеров . Издательство Корнеллского университета. стр. 672. ISBN 9780801401343.
2. A. Bucksch; G. Turk ; JS Weitz (2014). «Прогулка по волокну: модель роста, управляемого кончиком, с боковым расширением». PLOS ONE . 9 (1): e85585. arXiv : 1304.3521 . Bibcode : 2014PLoSO...985585B. doi : 10.1371 /journal.pone.0085585 . PMC 3899046. PMID  24465607. 
3. Хейс Б. (июль–авг. 1998 г.). «Как избежать себя» (PDF) . American Scientist . 86 (4): 314. doi :10.1511/1998.31.3301.
4. Лискевич М.; Огихара М.; Тода С. (июль 2003 г.). «Сложность подсчета самоизбегающих блужданий в подграфах двумерных сеток и гиперкубов». Теоретическая информатика . 304 (1–3): 129–56. doi : 10.1016/S0304-3975(03)00080-X .
5. Дюминиль-Копен, Гюго; Смирнов, Станислав (1 мая 2012 г.). «Константа связности сотовой решетки равна sqrt(2+sqrt 2)». Annals of Mathematics . 175 (3): 1653–1665. arXiv : 1007.0575 . doi :10.4007/annals.2012.175.3.14. S2CID  59164280.
6. Лоулер, Грегори Ф.; Шрамм, Одед ; Вернер, Венделин (2004). «О пределе масштабирования планарного самоизбегающего блуждания». Труды симпозиумов по чистой математике . 72 (2). Американское математическое общество: 339–364. arXiv : math/0204277 . doi : 10.1090/pspum/072.2/2112127. ISBN 0-8218-3638-2. S2CID  16710180.
7. Карлос П. Херреро (2005). «Самоизбегающие прогулки по сетям без масштабирования». Phys. Rev. E. 71 ( 3): 1728. arXiv : cond-mat/0412658 . Bibcode : 2005PhRvE..71a6103H. doi : 10.1103/PhysRevE.71.016103. PMID  15697654. S2CID  2707668.
8. Тишби, И.; Бихам, О.; Кацав, Э. (2016). «Распределение длин путей самоизбегающих прогулок в сетях Эрдёша–Реньи». Журнал физики A: Математическое и теоретическое . 49 (28): 285002. arXiv : 1603.06613 . Bibcode :2016JPhA...49B5002T. doi :10.1088/1751-8113/49/28/285002. S2CID  119182848.
9. Коломбани, Дж.; Бертаньолли, Дж.; Артиме, О. (2023). «Эффективное исследование сети с помощью сброса самоизбегающих случайных блужданий». Журнал физики: Сложность . 4 (4). arXiv : 2310.03203 . doi : 10.1088/2632-072X/acff33 .

Дальнейшее чтение

1. Мадрас, Н.; Слэйд, Г. (1996). Самоизбегающая прогулка . Биркхойзер. ISBN 978-0-8176-3891-7.
2. Лоулер, ГФ (1991). Пересечения случайных блужданий . Биркхойзер. ISBN 978-0-8176-3892-4.
3. Мадрас, Н.; Сокал, А.Д. (1988). «Алгоритм поворота – высокоэффективный метод Монте-Карло для самоизбегающего блуждания». Журнал статистической физики . 50 (1–2): 109–186. Bibcode : 1988JSP....50..109M. doi : 10.1007/bf01022990. S2CID  123272694.
4. Фишер, М. Э. (1966). «Форма самоизбегающего блуждания или полимерной цепи». Журнал химической физики . 44 (2): 616–622. Bibcode : 1966JChPh..44..616F. doi : 10.1063/1.1726734.

Внешние ссылки

• Последовательность OEIS A007764 (Число непересекающихся (или самоизбегающих) ладейных путей, соединяющих противоположные углы сетки n X n) — число самоизбегающих путей, соединяющих противоположные углы сетки N × N , для N от 0 до 12. Также включает расширенный список до N = 21.
• Вайсштейн, Эрик В. «Прогулка с самоизбеганием». MathWorld .
• Java-апплет двумерного самоизбегающего блуждания
• Общая реализация Python для моделирования SAW и расширения FiberWalks на квадратных решетках в n-мерном пространстве.
• Программное обеспечение Norris для генерации ПАВ на кубическом алмазе .