Caminho autoevitante

Três exemplos em um grafo de grade quadrada 8x8.

Em matemática, um caminho autoevitante é uma sequência de movimentos em um retículo que não visita o mesmo ponto mais de uma vez. Este é um caso especial da noção de caminho da teoria dos grafos. Um polígono autoevitante é um caminho autoevitante fechado em um retículo. O termo caminho autoevitante foi introduzido pelo químico Paul Flory,^[1] a fim de modelar o comportamento real de entidades de configuração em cadeia, tais como solventes e polímeros, cujos volumes físicos proíbem múltiplas ocupações do mesmo ponto espacial. Muito pouco é conhecido rigorosamente a respeito dos caminhos auto-evitantes a partir de uma perspectiva matemática, apesar de que físicos terem provido numerosas conjecturas que são acreditadas serem verdade e fortemente apoiadas por simulações matemáticas, e que existam diversas conjecturas que foram obtidas por meio de simulações computacionais.

Em física computacional um caminho autoevitante é um caminho em cadeia em ${\text{R}}^{2}$ ou ${\text{R}}^{3}$ com um certo número de nós, tipicamente um passo de tamanho fixo e com uma propriedade imperativa de que ele não cruza a si mesmo ou outro caminho. Um sistema de caminhos autoevitantes satisfaz a chamada condição do volume excluído. Em dimensões mais altas, acredita-se que um caminho autoevitante deve se comportar de modo bastante próximo de um passeio aleatório. Caminhos autoevitantes e polígonos autoevitantes ocupam um papel central em modelagem topológica e teoria dos nós no comportamento de moléculas em forma de filamentos e loops, como proteínas. Caminhos autoevitantes são fractais.^[2]^[3] Por exemplo, em $d=2$ a dimensão fractal é $4/3$ , para $d=3$ é próxima a $5/3$ enquanto para $d\geq 4$ , a dimensão fractal é $2$ . A dimensão é chamada dimensão crítica superior quando acima dela o volume excluído é insignificante. Um caminho autoevitante que não satisfaz a condição de volume excluído foi recentemente estudado para modelar superfícies geométricas explícitas resultante da expansão do caminho autoevitante.^[4]

As propriedades dos caminhos autoevitantes não podem ser calculadas analiticamente, então simulações numéricas são empregadas. O algoritmo de pivô é um método comum para simulações de Monte Carlo via Cadeias de Markov (MCMC) para medidas uniformes em caminhos autoevitantes de n passos. O algoritmo de pivô trabalha pegando um caminho autoevitante e aleatoriamente escolhendo um ponto desse caminho, e então aplicando uma operação simétrica (rotações e reflexões) no caminho depois do enésimo passo para criar um novo caminho. Calcular o número de caminhos autoevitantes em cada rede é um problema computacional comum. Não existe nenhuma fórmula conhecida para determinar o número de caminhos autoevitantes, embora existam métodos rigorosos para a aproximação.^[5]^[6] Conjectura-se que achar o número de caminhos dessa espécie seja um problema NP-difícil. Para caminhos autoevitantes, do fim de uma diagonal a outra, com apenas movimentos em posição positiva, existem exatamente ${m+n \choose m,n}$ caminhos para um retículo retangular $m \times n$ .

Universalidade

Um dos fenômenos associados com caminhos autoevitantes e modelos estatísticos físicos bidimensionais em geral é a noção de universalidade, isto é, independência de observáveis macroscópicos a partir de detalhes microscópicos, assim como a escolha do retículo. Uma quantidade importante que aparece em conjecturas para leis universais é a constante conectiva, definida como segue:

Seja $c_{n}$ o número de caminhos autoevitantes de n passos. Uma vez que todo caminho autoevitante de (n+m) passos pode ser decomposto em um caminho autoevitante de n passos e um caminho autoevitante de m passos, segue que $c n + m \leq c n c m$ . Portanto, a sequência {log( $c_{n}$ )} é subaditiva e podemos aplicar o lema de Fekete para mostrar que o seguinte limite existe:

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

Sendo $μ$ a constante conectiva, uma vez que $c n$ depende do retículo escolhido para o caminho, assim também é com $μ$ . O valor exato para $μ$ só é conhecido para o retículo hexagonal, onde é igual a :^[7]

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

Para outros retículos, $μ$ só foi aproximado numericamente, e não se acredita tratar de acredita de um número algébrico. Conjectura-se que

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

quando $n \to \infty$ , onde $μ$ depende do retículo, mas a correção da lei de potência $n^{\frac {11}{32}}$ não; em outras palavras, acredita-se que essa lei seja universal.

Caminhos autoevitantes em redes

Caminhos autoevitantes também têm sido estudados no contexto da análise de rede.^[8] Nesse contexto, é comum tratar caminhos autoevitantes como um processo dinâmico, de modo que a cada passo temporal um andarilho aleatoriamente salta entre nós vizinhos na rede. A caminhada acaba quando o andarilho atinge um estado sem saída, de modo que não pode mais avançar para nós vizinhos não visitados. Constatou-se recentemente que nas redes Erdős–Rényi, a distribuição do comprimento de caminho de tais caminhos autoevitantes com crescimento dinâmico podem ser calculados analiticamente, e segue a distribuição de Gompertz.^[9]

Limites

Considere a medida uniforme em um caminho autoevitante de n passos em todo o plano. Atualmente é desconhecido se o limite da medida uniforme quando $n \to \infty$ induz uma medida em caminhos infinitos. Contudo, Harry Kesten tem mostrado que assim como uma medida existe para caminhos autoevitantes na metade do plano. Uma questão importante envolvendo caminhos autoevitantes é a existência e invariância conforme do limite de escala, isso é, o limite de tamanho do caminho vai para o infinito, e a malha do retículo vai para zero. Se conjectura que o limite de escala para caminhos autoevitantes seja descrito por uma evolução Schramm–Loewner com parâmetro $κ = 83 .$

Referências

↑ P. Flory (1953). Principles of Polymer Chemistry. [S.l.]: Cornell University Press. 672 páginas. ISBN 9780801401343
↑ S. Havlin, D. Ben-Avraham (1982). «New approach to self-avoiding walks as a critical phenomenon». J. Phys. A. 15. 321 páginas. doi:10.1088/0305-4470/15/6/013
↑ S. Havlin, D. Ben-Avraham (1982). «Theoretical and numerical study of fractal dimensionality in self-avoiding walks». Phys. Rev. A. 26 (3). 1728 páginas. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728
↑ A. Bucksch, G. Turk, J.S. Weitz (2014). «The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion». PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585
↑ Hayes B (julho–agosto de 1998). «How to Avoid Yourself». American Scientist. 86 (4). doi:10.1511/1998.31.3301
↑ Liśkiewicz M; Ogihara M; Toda S (julho de 2003). «The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes». Theoretical Computer Science. 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X
↑ Duminil-Copin, Hugo; Smirnov, Stanislav (1 de maio de 2012). «The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)». Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14
↑ Carlos P. Herrero (2005). «Self-avoiding walks on scale-free networks». Phys. Rev. E. 71 (3). 1728 páginas. doi:10.1103/PhysRevE.71.016103
↑ Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

Bibliografia

Madras, N.; Slade, G. (1996). The Self-Avoiding Walk. [S.l.]: Birkhäuser. ISBN 978-0-8176-3891-7
Lawler, G. F. (1991). Intersections of Random Walks. [S.l.]: Birkhäuser. ISBN 978-0-8176-3892-4
Madras, N.; Sokal, A. D. (1988). «The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk». Journal of Statistical Physics. 50. doi:10.1007/bf01022990
Fisher, M. E. (1966). «Shape of a self-avoiding walk or polymer chain». Journal of Chemical Physics. 44 (2). 616 páginas. Bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734

Ligações externas

OEIS A007764 : o número de caminhos autoevitantes unindo cantos opostos de um grid N x N, com N indo de 0 a 12. Também inclui uma lista estendida até N = 21.
Weisstein, Eric W. «Self-Avoiding Walk». MathWorld (em inglês)
Java applet of a 2D self-avoiding walk
Generic python implementation to simulate SAWs and expanding FiberWalks on a square lattices in n-dimensions.
Software Norris para gerar caminhos autoevitantes em um diamante cúbico.

[1] P. Flory (1953). Principles of Polymer Chemistry. [S.l.]: Cornell University Press. 672 páginas. ISBN 9780801401343

[2] S. Havlin, D. Ben-Avraham (1982). «New approach to self-avoiding walks as a critical phenomenon». J. Phys. A. 15. 321 páginas. doi:10.1088/0305-4470/15/6/013

[3] S. Havlin, D. Ben-Avraham (1982). «Theoretical and numerical study of fractal dimensionality in self-avoiding walks». Phys. Rev. A. 26 (3). 1728 páginas. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728

[4] A. Bucksch, G. Turk, J.S. Weitz (2014). «The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion». PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585

[5] Hayes B (julho–agosto de 1998). «How to Avoid Yourself». American Scientist. 86 (4). doi:10.1511/1998.31.3301

[6] Liśkiewicz M; Ogihara M; Toda S (julho de 2003). «The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes». Theoretical Computer Science. 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X

[7] Duminil-Copin, Hugo; Smirnov, Stanislav (1 de maio de 2012). «The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)». Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14

[8] Carlos P. Herrero (2005). «Self-avoiding walks on scale-free networks». Phys. Rev. E. 71 (3). 1728 páginas. doi:10.1103/PhysRevE.71.016103

[9] Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

[10] Madras, N.; Slade, G. (1996). The Self-Avoiding Walk. [S.l.]: Birkhäuser. ISBN 978-0-8176-3891-7

[11] Lawler, G. F. (1991). Intersections of Random Walks. [S.l.]: Birkhäuser. ISBN 978-0-8176-3892-4

[12] Madras, N.; Sokal, A. D. (1988). «The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk». Journal of Statistical Physics. 50. doi:10.1007/bf01022990

[13] Fisher, M. E. (1966). «Shape of a self-avoiding walk or polymer chain». Journal of Chemical Physics. 44 (2). 616 páginas. Bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v d e Processos estocásticos
Tempo discreto	Cadeias de Markov Passeio aleatório Autoevitante Processo de Bernoulli Processo de Galton–Watson Processo de Moran Variáveis aleatórias independentes e identicamente distribuídas
Tempo contínuo	Processo de Bessel Movimento browniano Ponte Excursão Fracionário Geométrico Meander Processo de Cauchy Processo de Cox Processo de Feller Processo de Fleming–Viot Processo de Hunt Difusão de Itô Processo de Itô Processo Lévy Tempo local Processo aditivo de Markov Processo de McKean–Vlasov Processo Ornstein–Uhlenbeck Processo de Poisson Evolução de Schramm–Loewner Processo de Wiener Processo de nascimento e morte Processo de contato Passeio aleatório de tempo contínuo Processo empírico Difusão de salto
Ambos	Processo gaussiano Modelo Galves-Löcherbach Cadeias estocásticas com memória de alcance variável Modelo oculto de Markov Processo de Markov Martingale Ruído branco Processo regenerativo
Campos e outros	Processo de Dirichlet Medida de Gibbs Modelo de Hopfield Modelo de Ising Modelo de Potts Campo aleatório de Markov Processo de Pitman–Yor Grafo aleatório
Modelos de série temporal	Modelos ARCH ARIMA ARMA
Modelos financeiros	Black–Derman–Toy Black–Karasinski Chen Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Modelos atuariais	Bühlmann Cramér–Lundberg Sparre–Anderson
Modelos de filas	Fila M/M/1
Propriedades	Càdlàg Processo contínuo de Feller Gauss–Markov Markov Contínuo Reversível no tempo
Teoremas limites	Teorema central do limite Teorema de Donsker Teoria ergódica Teorema de Fisher–Tippett–Gnedenko Lei dos grandes números Lei do logaritmo iterado Teorema de Sanov
Desigualdades	Burkholder–Davis–Gundy Kunita–Watanabe Martingale de Doob
Ferramentas	Fórmula de Cameron–Martin Convergência de variáveis aleatórias Exponencial de Doléans-Dade Teorema da decomposição de Doob–Meyer Fórmula de Dynkin Fórmula de Feynman–Kac Teorema de Girsanov Integral de Itô Lema de Itō Teorema da continuidade de Kolmogorov Teorema da extensão de Kolmogorov Métrica de Lévy–Prokhorov Teorema de Prokhorov Integral de Skorokhod Teorema da representação de Skorokhod Espaço de Skorokhod Equação diferencial estocástica Tanaka Integral de Stratonovich Espaço de Wiener Clássico Abstrato Princípio da reflexão
Disciplinas	Ciências atuariais Econometria Teoria ergódica Matemática financeira Teoria das probabilidades Teoria das filas Estatística Cálculo estocástico Série temporal Aprendizado de máquina
Categoria:Processos estocásticos