Unikający spacer

Unikający spacer po siatce kwadratowej 15 × 15
Samounikający spacer po siatce kwadratowej 20x20, symulowany za pomocą sekwencyjnego Monte Carlo


W matematyce samounikający spacer ( SAW ) to sekwencja ruchów na siatce ( ścieżce kraty ), która nie odwiedza tego samego punktu więcej niż raz. Jest to szczególny przypadek pojęcia ścieżki w grafie . Samounikający wielokąt ( SAP ) to zamknięty samounikający spacer po siatce. Z matematycznego punktu widzenia bardzo niewiele wiadomo na temat samounikającego spaceru, chociaż fizycy przedstawili liczne przypuszczenia, które uważa się za prawdziwe i są silnie poparte symulacjami numerycznymi.

W fizyce obliczeniowej spacer samounikający to podobna do łańcucha ścieżka w R 2 lub R 3 z pewną liczbą węzłów, zwykle o stałej długości kroku, i ma tę właściwość, że nie przecina siebie ani innego spaceru. Układ SAWs spełnia tzw. objętości wykluczonej . Uważa się, że w wyższych wymiarach SAW zachowuje się podobnie jak zwykłe błądzenie losowe .

SAW i SAP odgrywają kluczową rolę w modelowaniu topologicznego i opartego na teorii węzłów zachowania cząsteczek przypominających nitki i pętle, takich jak białka . Rzeczywiście, SAW mogły zostać po raz pierwszy wprowadzone przez chemika Paula Flory'ego [ wątpliwe – dyskutuj ] w celu modelowania rzeczywistego zachowania podobnych do łańcuchów bytów, takich jak rozpuszczalniki i polimery , których fizyczna objętość uniemożliwia wielokrotne zajmowanie tego samego punktu przestrzennego.

SAW to fraktale . Na przykład dla d = 2 wymiar fraktalny wynosi 4/3, dla d = 3 jest bliski 5/3, natomiast dla d ≥ 4 wymiar fraktalny wynosi 2 . Wymiar nazywany jest górnym wymiarem krytycznym, powyżej którego wykluczona objętość jest pomijalna. SAW, który nie spełnia wykluczonego warunku objętości, został niedawno zbadany w celu modelowania jawnej geometrii powierzchni wynikającej z ekspansji SAW.

Właściwości SAW nie można obliczyć analitycznie, dlatego stosuje się symulacje numeryczne. Algorytm obrotu jest powszechną metodą symulacji Monte Carlo łańcucha Markowa dla jednolitej miary na n -krokowych spacerach samounikających. Algorytm Pivot działa na zasadzie samounikającego spaceru i losowego wybierania punktu na tym spacerze, a następnie stosowania symetrycznych transformacji (obrotów i odbić) na spacerze po n- tym kroku w celu utworzenia nowego spaceru.

Obliczanie liczby spacerów samounikających w dowolnej sieci jest częstym problemem obliczeniowym . Obecnie nie jest znany wzór, chociaż istnieją rygorystyczne metody aproksymacji.

Uniwersalność

Jednym ze zjawisk związanych z samounikającymi spacerami i ogólnie statystycznymi modelami fizycznymi jest pojęcie uniwersalności , czyli niezależności makroskopowych obserwabli od mikroskopowych szczegółów, takich jak wybór sieci. Jedną z ważnych wielkości, która pojawia się w przypuszczeniach dotyczących praw uniwersalnych, jest stała łącząca , zdefiniowana w następujący sposób. Niech c n oznacza liczbę n -krokowych samounikających spacerów. Ponieważ każdy ( n + m ) -krok samounikający spacer można rozłożyć na n -krokowy samounikający spacer i m -krokowy samounikający spacer, wynika z tego, że c n + m ≤ c n cm m . Zatem ciąg {log c n } jest subaddytywny i możemy zastosować lemat Feketego , aby pokazać, że istnieje następująca granica:

μ nazywa się stałą łączącą , ponieważ c n zależy od konkretnej sieci wybranej dla spaceru, podobnie jak μ . Dokładna wartość μ jest znana tylko dla sieci heksagonalnej, gdzie jest równa:

W przypadku innych sieci μ zostało tylko przybliżone liczbowo i uważa się, że nie jest nawet liczbą algebraiczną . Domniemywa się, że

jak n → ∞ gdzie μ zależy od sieci, ale poprawka nie innymi słowy, uważa się, że to prawo jest uniwersalne.

W sieciach

Samounikające spacery były również badane w kontekście teorii sieci . W tym kontekście zwyczajowo traktuje się SAW jako proces dynamiczny, taki, że w każdym kroku czasowym walker losowo przeskakuje między sąsiednimi węzłami sieci. Spacer kończy się, gdy chodzik osiągnie stan ślepej uliczki, tak że nie może już przejść do nowo nieodwiedzonych węzłów. Niedawno odkryto, że w Erdős – Rényi rozkład długości ścieżek takich dynamicznie rosnących SAW można obliczyć analitycznie i jest on zgodny z rozkładem Gompertza .

Granice

Rozważmy jednostajną miarę na n -stopniowych spacerach samounikających w pełnej płaszczyźnie. Obecnie nie wiadomo, czy granica jednolitej miary jako n → ∞ indukuje miarę na nieskończonych spacerach w całej płaszczyźnie. Jednak Harry Kesten wykazał, że taka miara istnieje dla samounikających się spacerów w półpłaszczyźnie. Jednym z ważnych pytań dotyczących samounikających się spacerów jest istnienie i konforemna niezmienność granicy skalowania , to znaczy granicy, gdy długość spaceru dąży do nieskończoności, a siatka siatki dąży do zera. Granica skalowania Przypuszcza się, że spacer samounikający jest opisany przez ewolucję Schramma-Loewnera z parametrem κ = 8 / 3 .

Zobacz też

Dalsza lektura

  1.   Madras, N.; Slade, G. (1996). Spacer samounikający . Birkäuser. ISBN 978-0-8176-3891-7 .
  2.   Lawler, GF (1991). Skrzyżowania przypadkowych spacerów . Birkäuser. ISBN 978-0-8176-3892-4 .
  3.   Madras, N.; Sokal, AD (1988). „Algorytm przestawny - wysoce wydajna metoda Monte-Carlo do samodzielnego unikania spaceru”. Dziennik fizyki statystycznej . 50 (1–2): 109–186. Bibcode : 1988JSP....50..109M . doi : 10.1007/bf01022990 . S2CID 123272694 .
  4. Fisher, ja (1966). „Kształt samounikającego spaceru lub łańcucha polimerowego”. Journal of Chemical Physics . 44 (2): 616–622. Bibcode : 1966JChPh..44..616F . doi : 10.1063/1.1726734 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Self-avoiding_walk&oldid=1130672690 ”