Самоизбегающая прогулка

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

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

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

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

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

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

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

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

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

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

{\sqrt {2+{\sqrt {2}}}}.

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

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

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

В сетях

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

Пределы

Рассмотрим равномерную меру на $n$ -шагах самоизбегающих блужданий в полной плоскости. В настоящее время неизвестно, индуцирует ли предел равномерной меры при $n \to \infty$ меру на бесконечных блужданиях по всей плоскости. Однако Гарри Кестен показал, что такая мера существует для самоизбегающих блужданий в полуплоскости. Одним из важных вопросов, связанных с самоизбегающими блужданиями, является существование и конформная инвариантность предела масштабирования , то есть предела, когда длина блуждания стремится к бесконечности, а сетка решетки стремится к нулю. Предполагается, что масштабный предел самоизбегающего блуждания описывается эволюцией Шрамма – Лёвнера с параметром $κ = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 8 / 3 ⁠ .$

См. также

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

Ссылки

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

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

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

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

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

[1] П. Флори (1953). Основы химии полимеров . Издательство Корнельского университета. п. 672. ИСБН 9780801401343 .

[2] А. Букш; Г. Тюрк ; Дж. С. Вайц (2014). «Прогулка по волокнам: модель роста, обусловленного кончиками, с боковым расширением» . ПЛОС ОДИН . 9 (1): е85585. arXiv : 1304.3521 . Бибкод : 2014PLoSO...985585B . дои : 10.1371/journal.pone.0085585 . ПМК 3899046 . ПМИД 24465607 .

[3] Хейс Б. (июль – август 1998 г.). «Как избежать себя» (PDF) . Американский учёный . 86 (4): 314. дои : 10.1511/1998.31.3301 .

[4] Лискевич М; Огихара М; Тода С. (июль 2003 г.). «Сложность подсчета самоизбегающих блужданий в подграфах двумерных сеток и гиперкубов» . Теоретическая информатика . 304 (1–3): 129–56. дои : 10.1016/S0304-3975(03)00080-X .

[5] Думинил-Копен, Гюго; Смирнов, Станислав (1 мая 2012 г.). «Константа связи сотовой решетки равна sqrt(2+sqrt 2)». Анналы математики . 175 (3): 1653–1665. arXiv : 1007.0575 . дои : 10.4007/анналы.2012.175.3.14 . S2CID 59164280 .

[6] Лоулер, Грегори Ф.; Шрамм, Одед ; Вернер, Венделин (2004). «О пределе масштабирования плоского самоизбегающего блуждания». Труды симпозиумов по чистой математике . 72 (2). Американское математическое общество: 339–364. arXiv : math/0204277 . дои : 10.1090/pspum/072.2/2112127 . ISBN 0-8218-3638-2 . S2CID 16710180 .

[7] Карлос П. Эрреро (2005). «Самоизбегающие блуждания по безмасштабным сетям». Физ. Преподобный Е. 71 (3): 1728. arXiv : cond-mat/0412658 . Бибкод : 2005PhRvE..71a6103H . дои : 10.1103/PhysRevE.71.016103 . ПМИД 15697654 . S2CID 2707668 .

[8] Тишби, И.; Бихам, О.; Кацав, Э. (2016). «Распределение длин путей самоизбегающих блужданий в сетях Эрдеша – Реньи». Физический журнал A: Математический и теоретический . 49 (28): 285002. arXiv : 1603.06613 . Бибкод : 2016JPhA...49B5002T . дои : 10.1088/1751-8113/49/28/285002 . S2CID 119182848 .

[9] Коломбани, Г.; Бертаньолли, Дж.; Артиме, О. (2023). «Эффективное исследование сети посредством сброса самоизбегающих случайных блуждающих» . Физический журнал: Сложность . 4 (4). arXiv : 2310.03203 . дои : 10.1088/2632-072X/acff33 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т и Фракталы
Характеристики	Фрактальные измерения Ассуад Подсчет коробок Хигучи Корреляция Хаусдорф Упаковка Топологический Рекурсия Самоподобие
Итерированная функция система	Папоротник Барнсли Канторовский набор Снежинка Коха Моя губка Ковер Серпинского Треугольник Серпинского Аполлоническая прокладка Слово Фибоначчи Кривая заполнения пространства Кривая Бланманже Кривая Де Рама Минковский Кривая дракона Кривая Гильберта кривая Коха Кривая Леви C Кривая Мура Кривые Пеано Кривая Серпинского Кривая Z-порядка Нить Т-квадрат н-хлопья Фрактальные шутки шестихлопьевидный Кривая Госпера Дерево Пифагора Функция Вейерштрасса
Странный аттрактор	Мультифрактальная система
L-система	Фрактальный навес Кривая заполнения пространства H-дерево
Время побега фракталы	Фрактал горящего корабля Джулия сет Заполненный Ньютон фрактал Кролик Дуади Ляпунов фрактал Набор Мандельброта точка Мисюревича Набор Мультиброт Ньютон фрактал Треуголка Мандельбокс Мандельбулба
рендеринга Методы	Буддадброт Орбитальная ловушка Пиковерный стебель
Случайные фракталы	Броуновское движение Броуновское дерево Броуновский двигатель Фрактальный пейзаж полет Леви Теория перколяции Самоизбегающая прогулка
Люди	Майкл Барнсли Георг Кантор Билл Госпер Феликс Хаусдорф Десмонд Пол Генри Гастон Джулия Хельге фон Кох Пол Леви Aleksandr Lyapunov Бенуа Мандельброт Хамид Надери Йегане Льюис Фрай Ричардсон Вацлав Серпиньский
Другой	« Какова длина побережья Британии? » Парадокс береговой линии Фрактальное искусство Список фракталов по размерности Хаусдорфа Фрактальная геометрия природы (книга 1982 г.) Красота фракталов (книга 1986 г.) Хаос: создание новой науки (книга 1987 г.) Калейдоскоп Теория хаоса

v т и Случайные процессы
Дискретное время	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding Biased Maximal entropy
Continuous time	Additive process Bessel process Birth–death process pure birth Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Dyson Brownian motion Empirical process Feller process Fleming–Viot process Gamma process Geometric process Hawkes process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage
Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process Stochastic chains with memory of variable length White noise
Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph
Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model
Financial models	Binomial options pricing model Black–Derman–Toy Black–Karasinski Black–Scholes Chan–Karolyi–Longstaff–Sanders (CKLS) Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White Korn-Kreer-Lenssen LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c
Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise-deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible
Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem Zero–one laws (Blumenthal, Borel–Cantelli, Engelbert–Schmidt, Hewitt–Savage, Kolmogorov, Lévy)
Inequalities	Burkholder–Davis–Gundy Doob's martingale Doob's upcrossing Kunita–Watanabe Marcinkiewicz–Zygmund
Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Karhunen–Loève theorem Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Control theory Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Signal processing Statistics Stochastic analysis Time series analysis Machine learning
List of topics Category