En matemáticas , una caminata de auto-evitación ( SAW ) es una secuencia de movimientos en una celosía (un camino de celosía ) que no visita el mismo punto más de una vez. Este es un caso especial de la noción teórica gráfica de una trayectoria . Un polígono de autoevitación ( SAP ) es un paseo cerrado de autoevitación sobre una celosía. Se sabe muy poco de forma rigurosa acerca de la caminata autodidacta desde una perspectiva matemática, aunque los físicos han proporcionado numerosas conjeturas que se cree que son ciertas y están fuertemente respaldadas por simulaciones numéricas.
En física computacional , una caminata autodirigida es una ruta en forma de cadena en R 2 o R 3 con un cierto número de nodos, generalmente una longitud de paso fija y tiene la propiedad de que no se cruza ni se cruza con otra caminata. Un sistema de SAW satisface la llamada condición de volumen excluido . En dimensiones más altas, se cree que el SAW se comporta de manera muy similar a la caminata aleatoria ordinaria .
Los SAW y SAP desempeñan un papel central en el modelado del comportamiento topológico y teórico de los nudos de moléculas con forma de hilo y bucle, como las proteínas . De hecho, los SAW pueden haber sido introducidos por primera vez por el químico Paul Flory [1] [ dudoso ] para modelar el comportamiento de la vida real de entidades en forma de cadena como disolventes y polímeros , cuyo volumen físico prohíbe la ocupación múltiple de los mismos. punto espacial.
Los SAW son fractales . [2] [3] Por ejemplo, en d = 2 la dimensión fractal es 4/3, para d = 3 está cerca de 5/3 mientras que para d ≥ 4 la dimensión fractal es 2 . La dimensión se denomina dimensión crítica superior por encima de la cual el volumen excluido es insignificante. Recientemente se estudió un SAW que no satisface la condición de volumen excluido para modelar la geometría de superficie explícita resultante de la expansión de un SAW. [4]
Las propiedades de los SAW no se pueden calcular analíticamente, por lo que se emplean simulaciones numéricas . El algoritmo de pivote es un método común para las simulaciones de Monte Carlo de la cadena de Markov para la medida uniforme en caminatas autodirigidas de n pasos. El algoritmo de pivote funciona dando una caminata auto-evitada y eligiendo al azar un punto en esta caminata, y luego aplicando transformaciones simétricas (rotaciones y reflejos) en la caminata después del paso n para crear una nueva caminata.
Calcular el número de paseos que se evitan por sí mismos en cualquier celosía dada es un problema computacional común . Actualmente no existe una fórmula conocida, aunque existen rigurosos métodos de aproximación. [5] [6]
Universalidad
Uno de los fenómenos asociados con los paseos de auto-evitación y los modelos de física estadística en general es la noción de universalidad , es decir, la independencia de los observables macroscópicos de los detalles microscópicos, como la elección de la red. Una cantidad importante que aparece en las conjeturas de las leyes universales es la constante conectiva , definida como sigue. Sea c n el número de caminatas autodirigidas de n pasos. Dado que cada ( n + m ) paso de autoevitación se puede descomponer en una caminata de autoevitación de n pasos y una caminata de autoevitación de m pasos, se deduce que c n + m ≤ c n c m . Por lo tanto, la secuencia {log c n } es subaditiva y podemos aplicar el lema de Fekete para mostrar que existe el siguiente límite:
μ se llama la constante conectiva , ya que c n depende de la red particular elegida para la caminata, también lo hace μ . El valor exacto de μ solo se conoce para la red hexagonal, donde es igual a: [7]
Para otras redes, μ solo se ha aproximado numéricamente y se cree que ni siquiera es un número algebraico . Se conjetura que [ cita requerida ]
como n → ∞ , donde μ depende de la red, pero la corrección de la ley de potenciano es; en otras palabras, se cree que esta ley es universal.
En redes
Las caminatas para evitar uno mismo también se han estudiado en el contexto de la teoría de redes . [8] En este contexto, es habitual tratar el SAW como un proceso dinámico, de modo que en cada paso de tiempo un caminante salta aleatoriamente entre los nodos vecinos de la red. La caminata termina cuando el caminante llega a un estado de callejón sin salida, de modo que ya no puede avanzar a nuevos nodos no visitados. Recientemente se descubrió que en las redes Erdős-Rényi , la distribución de las longitudes de trayectoria de estos SAW de crecimiento dinámico se puede calcular analíticamente y sigue la distribución de Gompertz . [9]
Limites
Considere la medida uniforme en caminatas autodirigidas de n pasos en el plano completo. Actualmente se desconoce si el límite de la medida uniforme cuando n → ∞ induce una medida en infinitas caminatas de plano completo. Sin embargo, Harry Kesten ha demostrado que existe una medida de este tipo para las caminatas en el semiplano que se evitan por sí mismas. Una cuestión importante relacionada con los paseos que se evitan por sí mismos es la existencia y la invariancia conforme del límite de escala , es decir, el límite a medida que la longitud del camino llega al infinito y la malla de la celosía llega a cero. Se conjetura que el límite de escala de la caminata autodirigida será descrito por la evolución de Schramm-Loewner con el parámetro κ =8/3.
Ver también
- Fenómenos críticos
- Camino hamiltoniano
- Tour de caballeros
- Caminata aleatoria
- Snake (género de videojuegos)
- Universalidad (sistemas dinámicos)
Referencias
- ^ P. Flory (1953). Principios de la química de polímeros . Prensa de la Universidad de Cornell. pag. 672. ISBN 9780801401343.
- ^ S. Havlin ; D. Ben-Avraham (1982). "Nueva aproximación a los paseos de auto-evitación como fenómeno crítico" . J. Phys. Una . 15 (6): L321 – L328. Código bibliográfico : 1982JPhA ... 15L.321H . doi : 10.1088 / 0305-4470 / 15/6/013 .
- ^ S. Havlin ; D. Ben-Avraham (1982). "Estudio teórico y numérico de la dimensionalidad fractal en paseos autoevitantes" . Phys. Rev. A . 26 (3): 1728-1734. Código Bibliográfico : 1982PhRvA..26.1728H . doi : 10.1103 / PhysRevA.26.1728 .
- ^ A. Bucksch; G. Turk ; JS Weitz (2014). "La caminata de fibra: un modelo de crecimiento impulsado por la punta con expansión lateral" . PLOS ONE . 9 (1): e85585. arXiv : 1304.3521 . Código bibliográfico : 2014PLoSO ... 985585B . doi : 10.1371 / journal.pone.0085585 . PMC 3899046 . PMID 24465607 .
- ^ Hayes B (julio-agosto de 1998). "Cómo evitarse a sí mismo" (PDF) . Científico estadounidense . 86 (4): 314. doi : 10.1511 / 1998.31.3301 .
- ^ Liśkiewicz M; Ogihara M; Toda S (julio de 2003). "La complejidad de contar caminatas de auto-evitación en subgrafos de cuadrículas bidimensionales e hipercubos". Informática Teórica . 304 (1-3): 129–56. doi : 10.1016 / S0304-3975 (03) 00080-X .
- ^ Duminil-Copin, Hugo; Smirnov, Stanislav (1 de mayo de 2012). "La constante conectiva de la celosía de panal es igual a sqrt (2 + sqrt 2)". Annals of Mathematics . 175 (3): 1653–1665. arXiv : 1007.0575 . doi : 10.4007 / annals.2012.175.3.14 .
- ^ Carlos P. Herrero (2005). "Caminatas autodirigidas en redes libres de escala". Phys. Rev. E . 71 (3): 1728. arXiv : cond-mat / 0412658 . Código Bibliográfico : 2005PhRvE..71a6103H . doi : 10.1103 / PhysRevE.71.016103 . PMID 15697654 .
- ^ Tishby, I .; Biham, O .; Katzav, E. (2016). "La distribución de las longitudes de las rutas de autoevitación camina en las redes Erdős-Rényi". Revista de Física A: Matemática y Teórica . 49 (28): 285002. arXiv : 1603.06613 . Código Bibliográfico : 2016JPhA ... 49B5002T . doi : 10.1088 / 1751-8113 / 49/28/285002 .
Otras lecturas
- Madras, N .; Slade, G. (1996). La caminata de auto-evitación . Birkhäuser. ISBN 978-0-8176-3891-7.
- Lawler, GF (1991). Intersecciones de caminatas aleatorias . Birkhäuser. ISBN 978-0-8176-3892-4.
- Madras, N .; Sokal, AD (1988). "El algoritmo de pivote - Un método de Monte-Carlo altamente eficiente para el caminar sin uno mismo". Revista de física estadística . 50 (1-2): 109-186. Código Bibliográfico : 1988JSP .... 50..109M . doi : 10.1007 / bf01022990 .
- Fisher, ME (1966). "Forma de un andador o cadena de polímero que se evita a sí mismo". Revista de Física Química . 44 (2): 616–622. Código bibliográfico : 1966JChPh..44..616F . doi : 10.1063 / 1.1726734 .
enlaces externos
- Secuencia OEIS A007764 (Número de caminos de torres que no se intersectan (o que se evitan automáticamente) que se unen a esquinas opuestas de una cuadrícula n X n): el número de caminos que se evitan automáticamente unen esquinas opuestas de una cuadrícula N × N , para N de 0 a 12. También incluye una lista ampliada hasta N = 21.
- Weisstein, Eric W. "Caminata para evitar uno mismo" . MathWorld .
- Applet de Java de una caminata en 2D para evitar uno mismo
- Implementación de Python genérico para simular SAW y expandir FiberWalks en celosías cuadradas en n dimensiones.
- Software Norris para generar SAWs en Diamond cubic .