Caminhada aleatória - Random walk

Cinco caminhadas aleatórias de oito passos a partir de um ponto central. Alguns caminhos parecem menores do que oito etapas onde a rota dobrou de volta sobre si mesma. ( versão animada )

Em matemática , um passeio aleatório é um objeto matemático , conhecido como processo estocástico ou aleatório , que descreve um caminho que consiste em uma sucessão de etapas aleatórias em algum espaço matemático , como os inteiros .

Um exemplo elementar de passeio aleatório é o passeio aleatório na linha de número inteiro , que começa em 0 e a cada passo se move +1 ou -1 com igual probabilidade . Outros exemplos incluem o caminho traçado por uma molécula conforme ela viaja em um líquido ou gás (ver movimento browniano ), o caminho de busca de um animal forrageiro , o preço de um estoque flutuante e a situação financeira de um jogador : tudo pode ser aproximado por modelos de passeio aleatório, embora eles possam não ser verdadeiramente aleatórios na realidade.

Conforme ilustrado por esses exemplos, passeios aleatórios têm aplicações para engenharia e muitos campos científicos, incluindo ecologia , psicologia , ciência da computação , física , química , biologia , economia e sociologia . Caminhadas aleatórias explicam os comportamentos observados de muitos processos nesses campos e, portanto, servem como um modelo fundamental para a atividade estocástica registrada. Como uma aplicação mais matemática, o valor de π pode ser aproximado pelo uso de um passeio aleatório em um ambiente de modelagem baseado em agente . O termo passeio aleatório foi introduzido pela primeira vez por Karl Pearson em 1905.

Vários tipos de passeios aleatórios são de interesse, que podem diferir de várias maneiras. O próprio termo geralmente se refere a uma categoria especial de cadeias de Markov , mas muitos processos dependentes do tempo são chamados de passeios aleatórios, com um modificador indicando suas propriedades específicas. Passeios aleatórios (Markov ou não) também podem ocorrer em uma variedade de espaços: os comumente estudados incluem gráficos , outros nos inteiros ou na linha real, no plano ou em espaços vetoriais de dimensão superior, em superfícies curvas ou Riemanniana de dimensão superior variedades , e também em grupos finitos, finitamente gerados ou Lie . O parâmetro de tempo também pode ser manipulado. No contexto mais simples, a caminhada está em tempo discreto, ou seja, uma sequência de variáveis ​​aleatórias ( X
t
) = ( X
1
, X
2
, ...)
indexados pelos números naturais. No entanto, também é possível definir passeios aleatórios que dão seus passos em momentos aleatórios, e nesse caso, a posição X
t
tem que ser definido para todos os tempos t ∈ [0, + ∞) . Casos específicos ou limites de passeios aleatórios incluem o voo de Lévy e modelos de difusão como o movimento browniano .

Passeios aleatórios são um tópico fundamental nas discussões dos processos de Markov. Seu estudo matemático foi extenso. Várias propriedades, incluindo distribuições de dispersão, primeira passagem ou tempos de acerto, taxas de encontro, recorrência ou transitoriedade, foram introduzidas para quantificar seu comportamento.

Caminhada aleatória de treliça

Um modelo de passeio aleatório popular é o de um passeio aleatório em uma rede regular, onde a cada passo o local salta para outro local de acordo com alguma distribuição de probabilidade. Em um passeio aleatório simples , o local só pode saltar para locais vizinhos da rede, formando um caminho de rede . Em um passeio aleatório simétrico simples em uma rede localmente finita, as probabilidades de a localização saltar para cada um de seus vizinhos imediatos são as mesmas. O exemplo mais bem estudado é o passeio aleatório na rede inteira d- dimensional (às vezes chamada de rede hipercúbica) .

Se o espaço de estado é limitado a dimensões finitas, o modelo de passeio aleatório é chamado de passeio aleatório simétrico com borda simples, e as probabilidades de transição dependem da localização do estado porque nos estados de margem e canto o movimento é limitado.

Passeio aleatório unidimensional

Um exemplo elementar de passeio aleatório é o passeio aleatório na linha de número inteiro , que começa em 0 e a cada passo se move +1 ou -1 com igual probabilidade.

Esta caminhada pode ser ilustrada da seguinte maneira. Um marcador é colocado em zero na linha numérica e uma moeda justa é lançada. Se cair em cara, o marcador é movido uma unidade para a direita. Se cair na cauda, ​​o marcador é movido uma unidade para a esquerda. Depois de cinco lançamentos, o marcador agora poderia estar em -5, -3, -1, 1, 3, 5. Com cinco lançamentos, três caras e duas coroas, em qualquer ordem, ele pousará em 1. Existem 10 maneiras de pousando em 1 (lançando três cabeças e duas caudas), 10 maneiras de pousar em -1 (lançando três caudas e duas cabeças), 5 maneiras de pousar em 3 (lançando quatro cabeças e uma cauda), 5 maneiras de pousar em −3 (lançando quatro caudas e uma cabeça), 1 forma de pouso em 5 (lançando cinco cabeças) e 1 forma de pouso em −5 (lançando cinco caudas). Veja a figura abaixo para uma ilustração dos resultados possíveis de 5 flips.

Todos os resultados de passeio aleatório possíveis após 5 lançamentos de uma moeda justa
Passeio aleatório em duas dimensões ( versão animada )
Passeio aleatório em duas dimensões com 25 mil passos ( versão animada )
Caminhada aleatória em duas dimensões com dois milhões de passos ainda menores. Esta imagem foi gerada de forma que os pontos mais frequentemente atravessados ​​fiquem mais escuros. No limite, para passos muito pequenos, obtém-se o movimento browniano .

Para definir esta caminhada formalmente, pegue variáveis ​​aleatórias independentes , onde cada variável é 1 ou -1, com uma probabilidade de 50% para qualquer um dos valores, e defina e A série é chamada de caminhada aleatória simples em . Esta série (a soma da sequência de −1s e 1s) dá a distância líquida percorrida, se cada parte da caminhada tiver um comprimento. A expectativa de é zero. Ou seja, a média de todos os lançamentos de moeda se aproxima de zero à medida que o número de lançamentos aumenta. Isso segue pela propriedade de aditividade finita da expectativa:

Um cálculo semelhante, usando a independência das variáveis ​​aleatórias e o fato de que , mostra que:

Isso sugere que , a distância de translação esperada após n passos, deve ser da ordem de . Na verdade,


Este resultado mostra que a difusão é ineficaz para a mistura por causa da maneira como a raiz quadrada se comporta para grandes .

Quantas vezes uma caminhada aleatória cruzará uma linha de fronteira se for permitido continuar caminhando para sempre? Um passeio aleatório simples cruzará cada ponto um número infinito de vezes. Esse resultado tem muitos nomes: fenômeno de passagem de nível , recorrência ou ruína do jogador . A razão para o sobrenome é a seguinte: um jogador com uma quantia finita de dinheiro acabará perdendo ao jogar um jogo justo contra um banco com uma quantia infinita de dinheiro. O dinheiro do jogador fará um passeio aleatório e chegará a zero em algum momento, e o jogo terminará.

Se um e b são inteiros positivos, então o número esperado de passos até um unidimensional passeio aleatório simples a partir de 0 primeiros sucessos b ou - um é ab . A probabilidade de que esse passeio acerte b antes de - a é , o que pode ser derivado do fato de que o passeio aleatório simples é um martingale .

Alguns dos resultados mencionados acima podem ser derivados das propriedades do triângulo de Pascal . O número de caminhadas diferentes de n etapas em que cada etapa é +1 ou -1 é 2 n . Para a caminhada aleatória simples, cada uma dessas caminhadas é igualmente provável. Para que S n seja igual a um número k é necessário e suficiente que o número de +1 no passeio exceda o de -1 em k . Segue-se que +1 deve aparecer ( n  +  k ) / 2 vezes entre n passos de uma caminhada, portanto, o número de caminhadas que satisfazem é igual ao número de maneiras de escolher ( n  +  k ) / 2 elementos de um conjunto de n elementos, denotado . Para que isso tenha significado, é necessário que n  +  k seja um número par, o que implica que n e k são ambos pares ou ímpares. Portanto, a probabilidade de que é igual a . Representando entradas do triângulo de Pascal em termos de fatoriais e usando a fórmula de Stirling , pode-se obter boas estimativas para essas probabilidades para grandes valores de .

Se o espaço for confinado a + por brevidade, o número de maneiras em que um passeio aleatório vai pousar em qualquer número com cinco voltas pode ser mostrado como {0,5,0,4,0,1}.

Essa relação com o triângulo de Pascal é demonstrada para pequenos valores de n . Em zero voltas, a única possibilidade será permanecer em zero. No entanto, em um turno, há uma chance de pousar em -1 ou uma chance de pousar em 1. Em dois turnos, um marcador em 1 pode mover-se para 2 ou voltar a zero. Um marcador em -1 pode mover-se para -2 ou voltar a zero. Portanto, há uma chance de pousar em -2, duas chances de pousar em zero e uma chance de pousar em 2.

k -5 -4 -3 -2 -1 0 1 2 3 4 5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

O teorema do limite central e a lei do logaritmo iterado descrevem aspectos importantes do comportamento de passeios aleatórios simples . Em particular, o primeiro implica que à medida que n aumenta, as probabilidades (proporcionais aos números em cada linha) se aproximam de uma distribuição normal .

Como uma generalização direta, pode-se considerar passeios aleatórios em redes cristalinas (gráficos de cobertura abeliana de dobras infinitas sobre gráficos finitos). Na verdade, é possível estabelecer o teorema do limite central e o teorema do grande desvio nesta configuração.

Como uma cadeia de Markov

Um passeio aleatório unidimensional também pode ser visto como uma cadeia de Markov cujo espaço de estado é dado pelos inteiros. Para algum número p satisfatório , as probabilidades de transição (a probabilidade P i, j de se mover do estado i para o estado j ) são dadas por

Generalização heterogênea

Dimensões superiores

Três passeios aleatórios em três dimensões

Em dimensões superiores, o conjunto de pontos percorridos aleatoriamente tem propriedades geométricas interessantes. Na verdade, obtém-se um fractal discreto , ou seja, um conjunto que exibe auto-similaridade estocástica em grandes escalas. Em pequenas escalas, pode-se observar "irregularidades" resultantes da grade em que a caminhada é realizada. Dois livros de Lawler mencionados abaixo são uma boa fonte sobre este tópico. A trajetória de um passeio aleatório é o conjunto de pontos visitados, considerado um conjunto que desconsidera quando o passeio chegou ao ponto. Em uma dimensão, a trajetória é simplesmente todos os pontos entre a altura mínima e a altura máxima que a caminhada alcançou (ambas são, em média, da ordem de ).

Para visualizar o caso bidimensional, pode-se imaginar uma pessoa caminhando ao acaso pela cidade. A cidade é efetivamente infinita e organizada em uma grade quadrada de calçadas. Em cada cruzamento, a pessoa escolhe aleatoriamente uma das quatro rotas possíveis (incluindo aquela de onde originalmente viajou). Formalmente, este é um passeio aleatório no conjunto de todos os pontos no plano com coordenadas inteiras .

A pessoa algum dia voltará ao ponto inicial da caminhada? Este é o equivalente bidimensional do problema de passagem de nível discutido acima. Em 1921, George Pólya provou que a pessoa quase certamente faria em um passeio aleatório bidimensional, mas para três dimensões ou mais, a probabilidade de retorno à origem diminui à medida que o número de dimensões aumenta. Em 3 dimensões, a probabilidade diminui para cerca de 34%. O matemático Shizuo Kakutani era conhecido por referir-se a esse resultado com a seguinte citação: "Um homem bêbado encontrará o caminho de casa, mas um pássaro bêbado pode se perder para sempre".

Outra variação dessa pergunta que também foi feita por Pólya é: se duas pessoas saem do mesmo ponto de partida, elas se encontrarão novamente? Pode-se mostrar que a diferença entre suas localizações (duas caminhadas aleatórias independentes) também é uma caminhada aleatória simples, então quase certamente eles se encontram novamente em uma caminhada bidimensional, mas para 3 dimensões e superiores a probabilidade diminui com o número de dimensões. Paul Erdős e Samuel James Taylor também mostraram em 1960 que para dimensões menores ou iguais a 4, dois passeios aleatórios independentes começando de quaisquer dois pontos dados têm infinitas interseções quase seguras, mas para dimensões superiores a 5, quase certamente se cruzam apenas finitamente .

A função assintótica para um passeio aleatório bidimensional conforme o número de passos aumenta é dada por uma distribuição de Rayleigh . A distribuição de probabilidade é uma função do raio da origem e o comprimento do passo é constante para cada passo.


Relação com o processo Wiener

Etapas simuladas aproximando um processo Wiener em duas dimensões

Um processo de Wiener é um processo estocástico com comportamento semelhante ao movimento browniano , o fenômeno físico da difusão de uma partícula minúscula em um fluido. (Às vezes, o processo de Wiener é chamado de "movimento browniano", embora isso seja, estritamente falando, uma confusão de um modelo com o fenômeno que está sendo modelado.)

Um processo Wiener é o limite de escala do passeio aleatório na dimensão 1. Isso significa que se você fizer um passeio aleatório com etapas muito pequenas, obterá uma aproximação de um processo Wiener (e, com menos precisão, do movimento browniano). Para ser mais preciso, se o tamanho do passo é ε, é preciso dar um passeio de comprimento L / ε 2 para aproximar um comprimento Wiener de L . À medida que o tamanho do passo tende a 0 (e o número de passos aumenta proporcionalmente), o passeio aleatório converge para um processo de Wiener em um sentido apropriado. Formalmente, se B é o espaço de todos os caminhos de comprimento L com a topologia máxima, e se M é o espaço de medida sobre B com a topologia da norma, então a convergência é no espaço M . Da mesma forma, um processo de Wiener em várias dimensões é o limite de escala do passeio aleatório no mesmo número de dimensões.

Um passeio aleatório é um fractal discreto (uma função com dimensões inteiras; 1, 2, ...), mas a trajetória de um processo de Wiener é um fractal verdadeiro e há uma conexão entre os dois. Por exemplo, dê um passeio aleatório até atingir um círculo de raio r vezes o comprimento do passo. O número médio de etapas que executa é r 2 . Este fato é a versão discreta do fato de que uma caminhada do processo de Wiener é um fractal da dimensão de Hausdorff  2.

Em duas dimensões, o número médio de pontos que o mesmo passeio aleatório tem no limite de sua trajetória é r 4/3 . Isso corresponde ao fato de que a fronteira da trajetória de um processo de Wiener é um fractal de dimensão 4/3, fato previsto por Mandelbrot por meio de simulações, mas comprovado apenas em 2000 por Lawler , Schramm e Werner .

Um processo de Wiener desfruta de muitas simetrias que o passeio aleatório não tem. Por exemplo, uma caminhada do processo Wiener é invariante às rotações, mas a caminhada aleatória não é, uma vez que a grade subjacente não (a caminhada aleatória é invariante às rotações de 90 graus, mas os processos de Wiener são invariantes às rotações, por exemplo, 17 graus também). Isso significa que, em muitos casos, os problemas em uma caminhada aleatória são mais fáceis de resolver, traduzindo-os em um processo de Wiener, resolvendo o problema ali e, em seguida, traduzindo de volta. Por outro lado, alguns problemas são mais fáceis de resolver com passeios aleatórios devido à sua natureza discreta.

A caminhada aleatória e o processo de Wiener podem ser acoplados , nomeadamente manifestados no mesmo espaço de probabilidade de uma forma dependente que os força a estarem bastante próximos. O mais simples desses acoplamentos é a incorporação de Skorokhod, mas existem acoplamentos mais precisos, como o teorema de aproximação de Komlós-Major-Tusnády .

A convergência de um passeio aleatório em direção ao processo de Wiener é controlada pelo teorema do limite central e pelo teorema de Donsker . Para uma partícula em uma posição fixa conhecida em t  = 0, o teorema do limite central nos diz que depois de um grande número de etapas independentes no passeio aleatório, a posição do caminhante é distribuída de acordo com uma distribuição normal da variância total :

onde t é o tempo decorrido desde o início do passeio aleatório, é o tamanho de uma etapa do passeio aleatório e é o tempo decorrido entre dois passos sucessivos.

Isso corresponde à função de Green da equação de difusão que controla o processo de Wiener, o que sugere que, após um grande número de etapas, o passeio aleatório converge para um processo de Wiener.

Em 3D, a variância correspondente à função de Green da equação de difusão é:

Equalizando essa quantidade com a variância associada à posição do caminhante aleatório, obtém-se o coeficiente de difusão equivalente a ser considerado para o processo Wiener assintótico para o qual o passeio aleatório converge após um grande número de etapas:

(válido apenas em 3D).

Observação: as duas expressões da variância acima correspondem à distribuição associada ao vetor que liga as duas extremidades do passeio aleatório, em 3D. A variância associada a cada componente , ou é apenas um terço desse valor (ainda em 3D).

Para 2D:

Para 1D:

Passeio aleatório gaussiano

Um passeio aleatório com um tamanho de passo que varia de acordo com uma distribuição normal é usado como um modelo para dados de série temporal do mundo real, como mercados financeiros. A fórmula de Black-Scholes para modelar preços de opções, por exemplo, usa um passeio aleatório Gaussiano como uma suposição subjacente.

Aqui, o tamanho do passo é a distribuição normal cumulativa inversa, onde 0 ≤  z  ≤ 1 é um número aleatório distribuído uniformemente e μ e σ são a média e os desvios padrão da distribuição normal, respectivamente.

Se μ for diferente de zero, o passeio aleatório irá variar em torno de uma tendência linear. Se v s é o valor inicial do passeio aleatório, o valor esperado após n passos será v s + n μ.

Para o caso especial em que μ é igual a zero, após n passos, a distribuição de probabilidade da distância de translação é dada por N (0, n σ 2 ), onde N () é a notação para a distribuição normal, n é o número de passos , e σ é da distribuição normal cumulativa inversa conforme dado acima.

Prova: O passeio aleatório gaussiano pode ser pensado como a soma de uma sequência de variáveis ​​aleatórias independentes e distribuídas de forma idêntica, X i da distribuição normal cumulativa inversa com média igual a zero e σ da distribuição normal cumulativa inversa original:

Z = ,

mas temos a distribuição da soma de duas variáveis ​​aleatórias normalmente distribuídas independentes, Z = X + Y, é dada por

X + μ Y , σ 2 X + σ 2 Y ) (veja aqui) .

Em nosso caso, μ X = μ Y = 0 e σ 2 X = σ 2 Y = σ 2 rendimento

(0, 2σ 2 )

Por indução, para n passos, temos

Z ~ (0, n σ 2 ).

Para etapas distribuídas de acordo com qualquer distribuição com média zero e uma variância finita (não necessariamente apenas uma distribuição normal), a distância de translação quadrada média após n etapas é

Mas para o passeio aleatório gaussiano, este é apenas o desvio padrão da distribuição da distância de translação após n passos. Portanto, se μ for igual a zero, e uma vez que a distância de translação RMS (root mean square) é um desvio padrão, há 68,27% de probabilidade de que a distância de translação RMS após n etapas cairá entre ± σ . Da mesma forma, há 50% de probabilidade de que a distância de translação após n etapas cairá entre ± 0,6745σ .

Difusão anômala

Em sistemas desordenados, como meios porosos e fractais, podem não ser proporcionais a, mas a . O expoente é chamado de expoente de difusão anômala e pode ser maior ou menor que 2. A difusão anômala também pode ser expressa como σ r 2 ~ Dt α, onde α é o parâmetro de anomalia. Algumas difusões em ambiente aleatório são até proporcionais a uma potência do logaritmo da época, ver por exemplo a caminhada do Sinai ou difusão de Brox.

Número de sites distintos

O número de locais distintos visitados por um único andador aleatório foi estudado extensivamente para redes quadradas e cúbicas e para fractais. Esta quantidade é útil para a análise de problemas de armadilhas e reações cinéticas. Também está relacionado com a densidade vibracional de estados, processos de reações de difusão e disseminação de populações na ecologia. A generalização deste problema para o número de locais distintos visitados por caminhantes aleatórios,, foi recentemente estudada para redes euclidianas d-dimensionais. O número de locais distintos visitados por N caminhantes não está simplesmente relacionado ao número de locais distintos visitados por cada caminhante.

Taxa de informação

A taxa de informação de um passeio aleatório Gaussiano em relação ao quadrado da distância de erro, ou seja, sua função de distorção de taxa quadrática , é dada parametricamente por

onde . Portanto, é impossível codificar usando um código binário menor que bits e recuperá-lo com erro quadrático médio esperado menor que . Por outro lado, para qualquer um , existe um código grande o suficiente e um código binário de não mais do que elementos distintos, de modo que o erro quadrático médio esperado na recuperação desse código seja no máximo .

Formulários

Antony Gormley 's Nuvem Quantum escultura em Londres foi desenhado por um computador usando um algoritmo de passeio aleatório.

Como mencionado, a gama de fenômenos naturais que foram sujeitos a tentativas de descrição por algum tipo de passeios aleatórios é considerável, em particular em física e química, ciência dos materiais , biologia e vários outros campos. A seguir estão algumas aplicações específicas de passeio aleatório:

Em todos esses casos, o passeio aleatório costuma substituir o movimento browniano.

  • Na pesquisa do cérebro , passeios aleatórios e passeios aleatórios reforçados são usados ​​para modelar cascatas de disparo de neurônios no cérebro.
  • Na ciência da visão , a deriva ocular tende a se comportar como um passeio aleatório. Segundo alguns autores, os movimentos fixadores dos olhos em geral também são bem descritos por um passeio aleatório.
  • Em psicologia , os passeios aleatórios explicam com precisão a relação entre o tempo necessário para tomar uma decisão e a probabilidade de que uma determinada decisão seja tomada.
  • Os passeios aleatórios podem ser usados ​​para obter amostras de um espaço estadual desconhecido ou muito grande, por exemplo, para escolher uma página aleatória da Internet ou, para pesquisa de condições de trabalho, um trabalhador aleatório em um determinado país.
  • Quando esta última abordagem é usada na ciência da computação, ela é conhecida como cadeia de Markov Monte Carlo ou MCMC, abreviadamente. Freqüentemente, a amostragem de algum espaço de estado complicado também permite obter uma estimativa probabilística do tamanho do espaço. A estimativa da permanente de uma grande matriz de zeros e uns foi o primeiro grande problema abordado com essa abordagem.

Variantes

Vários tipos de processos estocásticos foram considerados semelhantes aos passeios aleatórios puros, mas onde a estrutura simples pode ser mais generalizada. A estrutura pura pode ser caracterizada pelas etapas sendo definidas por variáveis ​​aleatórias independentes e distribuídas de forma idêntica .

Em gráficos

Um passeio aleatório de comprimento k em um grafo possivelmente infinito G com uma raiz 0 é um processo estocástico com variáveis ​​aleatórias tais que e é um vértice escolhido uniformemente ao acaso a partir dos vizinhos de . Então, o número é a probabilidade de que um passeio aleatório de comprimento k começando em v termine em w . Em particular, se G for um gráfico com raiz 0 , é a probabilidade de que um passeio aleatório de passos retorne a 0 .

Com base na analogia da seção anterior sobre dimensões superiores, suponha agora que nossa cidade não é mais uma grade quadrada perfeita. Quando nossa pessoa chega a um certo cruzamento, ela escolhe entre as várias estradas disponíveis com igual probabilidade. Assim, se a junção tiver sete saídas, a pessoa irá para cada uma com probabilidade de um sétimo. Este é um passeio aleatório em um gráfico. Nossa pessoa alcançará sua casa? Acontece que, em condições bastante suaves, a resposta ainda é sim, mas dependendo do gráfico, a resposta à pergunta variante "Duas pessoas se encontrarão novamente?" pode não ser que eles se encontrem infinitamente freqüentemente quase certamente.

Um exemplo de caso em que a pessoa chegará a sua casa com quase certeza é quando os comprimentos de todos os blocos estão entre a e b (onde a e b são quaisquer dois números positivos finitos). Observe que não presumimos que o gráfico seja plano , ou seja, a cidade pode conter túneis e pontes. Uma forma de comprovar esse resultado é por meio da conexão a redes elétricas . Pegue um mapa da cidade e coloque um resistor de um ohm em cada quarteirão. Agora meça a "resistência entre um ponto e o infinito". Em outras palavras, escolha algum número R e pegue todos os pontos da rede elétrica com distância maior que R do nosso ponto e conecte-os. Esta é agora uma rede elétrica finita e podemos medir a resistência de nosso ponto até os pontos com fio. Leve R ao infinito. O limite é chamado de resistência entre um ponto e o infinito . Acontece que o seguinte é verdadeiro (uma prova elementar pode ser encontrada no livro de Doyle e Snell):

Teorema : um gráfico é transiente se e somente se a resistência entre um ponto e o infinito é finita. Não é importante qual ponto é escolhido se o gráfico estiver conectado.

Em outras palavras, em um sistema transiente, basta superar uma resistência finita para chegar ao infinito de qualquer ponto. Em um sistema recorrente, a resistência de qualquer ponto ao infinito é infinita.

Esta caracterização de transitoriedade e recorrência é muito útil, e especificamente nos permite analisar o caso de uma cidade desenhada no plano com as distâncias limitadas.

Um passeio aleatório em um gráfico é um caso muito especial de uma cadeia de Markov . Ao contrário de uma cadeia de Markov geral, o passeio aleatório em um gráfico possui uma propriedade chamada simetria ou reversibilidade do tempo . Grosso modo, essa propriedade, também chamada de princípio do equilíbrio detalhado , significa que as probabilidades de percorrer um determinado caminho em uma direção ou em outra têm uma conexão muito simples entre elas (se o gráfico for regular , elas são apenas iguais). Essa propriedade tem consequências importantes.

A partir da década de 1980, muitas pesquisas foram feitas para conectar as propriedades do gráfico a passeios aleatórios. Além da conexão da rede elétrica descrita acima, existem conexões importantes para desigualdades isoperimétricas , veja mais aqui , desigualdades funcionais como as desigualdades de Sobolev e Poincaré e propriedades de soluções da equação de Laplace . Uma parte significativa desta pesquisa foi focada em gráficos de Cayley de grupos gerados finitamente . Em muitos casos, esses resultados discretos são transferidos ou derivados de variedades e grupos de Lie .

No contexto de gráficos aleatórios , particularmente do modelo Erdős – Rényi , resultados analíticos para algumas propriedades de caminhantes aleatórios foram obtidos. Estes incluem a distribuição do primeiro e último tempo de acerto do andador, onde o primeiro tempo de acerto é dado pela primeira vez que o caminhante entra em um local do gráfico anteriormente visitado, e o último tempo de acerto corresponde à primeira vez que o andador não consegue executar um movimento adicional sem revisitar um site visitado anteriormente.

Uma boa referência para passeio aleatório em gráficos é o livro online de Aldous e Fill . Para grupos, consulte o livro de Woess. Se o kernel de transição for aleatório (baseado em um ambiente ), então o passeio aleatório é chamado de "passeio aleatório em ambiente aleatório". Quando a lei do passeio aleatório inclui a aleatoriedade de , a lei é chamada de lei recozida; por outro lado, se for vista como fixa, a lei é chamada de lei extinta. Veja o livro de Hughes, o livro de Revesz ou as notas de aula de Zeitouni.

Podemos pensar em escolher cada aresta possível com a mesma probabilidade de maximizar a incerteza (entropia) localmente. Também poderíamos fazer isso globalmente - no passeio aleatório com entropia máxima (MERW), queremos que todos os caminhos sejam igualmente prováveis, ou em outras palavras: para cada dois vértices, cada caminho de determinado comprimento é igualmente provável. Este passeio aleatório tem propriedades de localização muito mais fortes.

Passeios aleatórios de auto-interação

Existem vários modelos interessantes de caminhos aleatórios em que cada etapa depende do passado de uma maneira complicada. Todos são mais complexos para resolver analiticamente do que o passeio aleatório usual; ainda assim, o comportamento de qualquer modelo de caminhante aleatório pode ser obtido por meio de computadores. Exemplos incluem:

A caminhada autoevitiva de comprimento n on é o caminho aleatório de n passos que começa na origem, faz transições apenas entre locais adjacentes em , nunca revisita um local e é escolhido uniformemente entre todos esses caminhos. Em duas dimensões, devido à auto-armadilha, uma caminhada típica de evitação é muito curta, enquanto nas dimensões superiores ela cresce além de todos os limites. Este modelo tem sido freqüentemente usado na física de polímeros (desde 1960).

Caminhadas correlacionadas de longo alcance

Séries temporais correlacionadas de longo alcance são encontradas em muitos sistemas biológicos, climatológicos e econômicos.

  • Registros de pulsação
  • Sequências de DNA não codificantes
  • Séries temporais de volatilidade de ações
  • Registros de temperatura em todo o mundo

Caminhadas aleatórias tendenciosas em gráficos

Caminhada aleatória de entropia máxima

Caminhada aleatória escolhida para maximizar a taxa de entropia , tem propriedades de localização muito mais fortes.

Caminhadas aleatórias correlacionadas

Caminhadas aleatórias onde a direção do movimento em um momento está correlacionada com a direção do movimento na próxima vez. É usado para modelar os movimentos dos animais.

Veja também

Referências

Bibliografia

links externos