Em matemática , economia e física teórica , um passeio aleatório é um modelo matemático de um sistema com uma dinâmica discreta composta por uma sucessão de etapas aleatórias , ou tomadas "ao acaso". Também são frequentemente utilizadas as expressões passeio aleatório , passeio aleatório ou passeio aleatório em inglês. Além disso, essas etapas aleatórias são totalmente decorrelacionadas umas das outras; esta última propriedade fundamental é chamada de caráter markoviano do processo, em homenagem ao matemático Markov . Intuitivamente, significa que, a cada momento, o futuro do sistema depende de seu estado atual, mas não de seu passado, mesmo o mais próximo. Em outras palavras, o sistema "perde memória" à medida que evolui com o tempo. Por esse motivo, um passeio aleatório às vezes também é chamado de “passeio bêbado”.
Essa modelagem matemática permite dar conta de certos fenômenos naturais, cujo exemplo mais famoso é o movimento browniano , correspondendo, por exemplo, aos movimentos aparentemente aleatórios das partículas presentes no fluido interno de um grão de pólen.
Em matemática ou ciência da computação, muitas vezes estudamos passeios aleatórios em redes regulares ou em gráficos mais complexos. Este é, por exemplo, o método utilizado pelo motor de busca Google para navegar, identificar e classificar as páginas da rede Internet .
Tecnicamente, passeios aleatórios são o domínio da teoria da probabilidade . Um passeio aleatório é de fato um processo estocástico do tipo de cadeia de Markov . Ele é dividido em unidades elementares chamadas degraus , cujo comprimento pode ser constante, aleatório ou fixo pela rede ou pelo gráfico em que estamos viajando. Em cada etapa, há, portanto, uma gama de possibilidades para selecionar aleatoriamente a direção e o tamanho da etapa. Essa gama de possibilidades pode ser discreta (escolha entre um número finito de valores) ou contínua .
A ideia do passeio aleatório foi introduzida (sem o nome) em 1905 pelo bioestatístico Karl Pearson para explicar as migrações de uma população de mosquitos em uma floresta. Pearson faz a seguinte pergunta:
“Um homem parte do ponto O e percorre 1 jarda (0,914 m ) em linha reta; ele vira em qualquer ângulo e caminha novamente os metros em linha reta. Ele repete esse processo n vezes. Eu pergunto a probabilidade de que após n dessas viagens, ele esteja a uma distância entre r e r + dr de seu ponto de partida. "
A resposta a esta pergunta é fornecida uma semana depois por Lord Rayleigh na seguinte edição da revista Nature : quando n é grande o suficiente, essa probabilidade é:
.Se Rayleigh fornece a resposta tão rapidamente, é porque ele próprio estudou um problema relacionado em 1880: o comportamento de uma superposição de ondas acústicas todas da mesma amplitude, mas de fases aleatórias. Pearson conhece Rayleigh em10 de agosto :
“Eu deveria saber, mas minha leitura nos últimos anos mudou para outras áreas de interesse, e você não esperaria encontrar o primeiro passo em um problema de biometria em uma dissertação sobre acústica. "
Pearson então continua:
“A lição da solução de Lord Rayleigh é que em um campo aberto, o lugar mais provável para encontrar um bêbado que ainda consegue se manter em pé é em algum lugar próximo ao seu ponto de partida. "
O termo "passeio aleatório" não foi introduzido até por volta de 1919-1921 pelo matemático húngaro George Pólya , que usou a palavra alemã " Irrfahrt ".
O modelo de passeio aleatório mais simples é o passeio aleatório discreto unidimensional na rede periódica ℤ. Para dar um exemplo concreto, podemos imaginar um indivíduo (ou "partícula") em uma escada, que joga uma moeda para decidir se o próximo degrau será para cima ou para baixo. Em cada etapa, existem apenas duas possibilidades: neste exemplo, um passo à frente ou um passo atrás. O único parâmetro livre do problema é a probabilidade de que a partícula salte para a frente (em vez de saltar para trás).
Se nomearmos essa probabilidade pelo número real p tal que: 0 < p <1 , então q = 1 - p representa a probabilidade de que a partícula volte .
O caso mais simples, que corresponde por exemplo ao movimento browniano, consiste em fazer a hipótese de isotropia espacial . As direções "para frente / para trás" do espaço físico sendo a priori equivalentes, definimos a equiprobabilidade :
É notável que as leis destacadas neste caso se estendam a problemas de passeio aleatório muito mais complexos.
Cada um dos disparos ao acaso para escolher o movimento constitui um teste de Bernoulli com resultados igualmente prováveis : aqui a probabilidade de subida ou descida é 1/2.
A figura ao lado mostra uma amostra de três simulações numéricas independentes de passeios aleatórios para uma partícula: traçamos as posições sucessivas x ( t ) da partícula nos tempos t = 1, 2, ..., a partir da condição inicial x ( 0) = 0 .
Após n passos no total, o número de vezes que desenhamos "caudas" segue a distribuição binomial B ( n , 1/2) , de modo que a probabilidade é:
onde é o número de combinações de k elementos retirados de n .
Podemos determinar a posição após n iterações, tomando o valor 0 para o início, adicionando 1 para cada passo à frente (cauda), subtraindo 1 para cada passo para trás (face). Assim, a posição é dada por: . Em comparação com a lei binomial clássica, é, portanto, suficiente deslocar os resultados por n ⁄ 2 e multiplicar por 2, assim:
Concretamente, se repetirmos a experiência com um grande número de participantes, e se permitirmos que eles evoluam durante um número suficientemente grande de etapas (da ordem de n = 100, por exemplo), esperamos que a nuvem de posições finais esteja aproximadamente centrada em a caminhada inicial. Isso pode ser quantitativo: ao nos colocarmos no regime assintótico n >> 1 , demonstramos usando a fórmula de Stirling que a lei binomial se comporta assintoticamente como uma distribuição gaussiana . Em particular, uma ordem de magnitude da propagação da nuvem de participantes é obtida: por exemplo, espera-se que aproximadamente 95% dos participantes tenham permanecido a 20 passos ou menos da posição inicial (20 = 2 √ 100 ).
ExemplosA galeria abaixo contém quatro espécimes de passeios aleatórios isotrópicos na rede ℤ após 1000 passos da origem. As linhas pontilhadas indicam respectivamente os valores máximo e mínimo da posição alcançada (após 1000 passos).
De acordo com a fórmula acima, a probabilidade de retornar à origem após 2 n passos vale (é claro que é zero após um número ímpar de passos).
O equivalente obtido pela fórmula de Stirling mostra que essa probabilidade tende lentamente para 0, o que significa intuitivamente que quanto mais tempo, menos provável estaremos no ponto de partida. Porém, veremos que qualquer caminhada retorna pelo menos uma vez à origem, sabendo que a média dos tempos do primeiro retorno à origem é infinita.
Probabilidade de passagem para a origemNos perguntamos qual é a probabilidade de termos retornado pelo menos uma vez à origem durante uma viagem de comprimento 2n ; é notável que o evento oposto também tem uma probabilidade e que, portanto, tende para 1 quando n tende para o infinito: um passeio aleatório isotrópico na linha quase certamente retorna pelo menos uma vez ao seu ponto de partida (portanto, na verdade y se repete uma infinidade de vezes ), e isso se aplica até mesmo a qualquer ponto por onde passe. Veremos mais tarde que isso permanece verdadeiro na dimensão 2, mas se torna falso na dimensão superior.
Demonstração da fórmula anterior:
Por uma questão de simetria, o número de passos aleatórios de comprimento que não passam é o dobro do número daqueles que permanecem .
Nosso problema é contar os passos que vão de a em traços e estar, à parte , estritamente à direita de .
O primeiro segmento da etapa tal necessariamente indo para , basta contar o número de caminhos que vão em em tiros ignorando .
Em geral, o número de caminhos que ir em em acidentes vasculares cerebrais é (o caminho é inteiramente determinada pelo movimento para a direita (ou movimento para a esquerda)) para escolher entre as totais deslocamentos. Então, o número total de etapas que vão de até vale a pena
A parte difícil é determinar o número de passos em com tiros que atravessam 0. Isso é feito usando o princípio de reflexão (ver o artigo sobre a questão eleitoral ).
Para tal etapa, podemos substituir bijetivamente a parte entre o início e o primeiro retorno por sua simétrica em relação a : este número é, portanto, o mesmo que as etapas indo de para em movimentos, ou seja,
Portanto, vale a pena o número de passos que vão de até ao comprimento sem passar pelo eixo . Observe que este resultado é equivalente ao do teorema da votação .
Deduzimos o número de passos evitando : ; doação telescópica da soma , o que precisava ser demonstrado.
Outra interpretação do mesmo resultado: o número de palavras binárias de comprimento das quais todas as subpalavras começando à esquerda (resp. À direita) apresentam estritamente mais de 1 do que 0 (resp. O reverso) vale (não para confundir com as palavras de Dyck ).
Um cálculo semelhante mostra que, no caso ímpar, a probabilidade de retorno à origem durante uma caminhada longa também é válida (ver a sequência A063886 do OEIS e a sequência A307768 do OEIS ).
Hora do primeiro retorno à origemUsando os resultados acima, a probabilidade pode ser obtida como caminhar de volta à origem pela primeira vez : . Deduzimos que a expectativa do tempo de primeiro retorno à origem é infinita desde então .
Demonstração da fórmula anterior:
Um passo que retorna à origem no momento passa necessariamente por 1 ou por -1 no momento anterior e, sempre por simetria, há tantos passos chegando em 1 quanto em -1; o número de passos retornando à origem pela primeira vez vale, portanto, o dobro do número de passos de comprimento terminando em 1 e permanecendo> 0; podemos refazer um raciocínio do tipo anterior ou aplicar diretamente a fórmula do voto com , de onde , o que queríamos.
Observe que é o dobro do número de pedidos catalães .
Consideramos um passeio aleatório na rede plana ℤ 2 . Existem quatro movimentos possíveis aqui em cada site: para frente, para trás, direita, esquerda. A figura ao lado mostra uma amostra de três simulações numéricas independentes de passeios aleatórios para uma partícula: traçamos as três trajetórias obtidas.
Para caminhadas longas, a distribuição da posição final do caminhante se comporta assintoticamente como uma distribuição gaussiana . Essa convergência é ilustrada abaixo: traçamos as distribuições das probabilidades de presença na rede após 10 etapas e, em seguida, após 60 etapas:
EspécimesA galeria abaixo contém quatro espécimes de passeios aleatórios isotrópicos na rede ℤ 2 após 10.000 passos da origem.
Consideramos um passeio aleatório na rede cúbica ℤ 3 . Existem seis movimentos possíveis aqui em cada site: para frente, para trás, direita, esquerda, para cima, para baixo.
A figura ao lado mostra uma amostra de três simulações numéricas independentes de passeios aleatórios para uma partícula: traçamos as três trajetórias obtidas.
EspécimesA galeria abaixo contém quatro espécimes de passeios aleatórios isotrópicos na rede ℤ 3 após 10.000 passos da origem.
Consideramos o passeio aleatório no plano ℝ 2 definido pelo seguinte processo:
Cada direção de salto é completamente independente da direção do salto anterior.
A figura ao lado mostra uma amostra de três simulações numéricas independentes de passeios aleatórios para uma partícula: traçamos as três trajetórias obtidas.
EspécimesA galeria abaixo contém quatro espécimes de etapas aleatórias isotrópicas no plano ℝ 2 após 10.000 etapas da origem.
Considere um passeio aleatório isotrópico na rede ℤ d com d dimensões espaciais. Sempre podemos escolher tomar o ponto de partida desta caminhada como a origem O do sistema de coordenadas cartesianas. A questão da recorrência consiste então em perguntar se podemos encontrar pelo menos um instante positivo finito t para o qual a partícula passa pela origem O novamente .
O passeio aleatório será considerado recorrente se e somente se a probabilidade de que a partícula retorne à origem O para um certo instante posterior finito t for igual a um.
Esta propriedade de recorrência depende fortemente da dimensão do espaço; podemos de fato demonstrar que (Pólya - 1921):
Algumas pessoas às vezes brincam que esse teorema é a base do provérbio: "Todos os caminhos levam a Roma" . O leitor notará que, se incluirmos caminhos "cósmicos", o provérbio está errado.
Probabilidade de retorno à origem em dimensão maior ou igual a trêsNa verdade, sabemos calcular a probabilidade de que o caminhante, inicialmente partindo da origem, volte à origem, e isso para todas as dimensões d > 2 . Esta probabilidade p ( d ) admite a seguinte expressão:
onde u ( d ) é uma integral dimensional d :
, que pode ser expressa usando a função de Bessel de primeiro tipo : .O número representa o número médio de retornos à origem antes de ir ao infinito (ver lei geométrica ).
O caso especial d = 3 na verdade já havia sido obtido anteriormente por Watson, Mc Crea e Whipple, e Domb. Uma expressão analítica da integral só foi obtida em 1977 por Glasser e Zucker:
onde Γ é a função gama . As expressões analíticas de u ( d ) não são conhecidas na dimensão d maior ou igual a 4.
Obtemos os seguintes valores numéricos:
Consideramos um grupo aqui assumido como multiplicativo, sem que isso seja essencial para a definição de um passeio aleatório sobre um grupo. Damos a nós mesmos uma série de variáveis aleatórias independentes com a mesma lei (lei chamada aqui, por exemplo), variáveis aleatórias todas com valores em . Também nos damos uma variável aleatória com valores em , de qualquer lei e independente de . Em seguida, posamos, para
A sequência é então uma cadeia de Markov e é chamada de passeio aleatório em G , de etapas . Esta classificação também se aplica a qualquer sequência aleatória da mesma distribuição que X . Alternativamente, aceitamos como passeio aleatório uma sequência definida pela relação de recorrência:
Para distinguir os dois tipos de cadeias de Markov assim definidas, às vezes falamos de passeio aleatório à direita e passeio aleatório à esquerda . O termo geral da matriz de transição desta cadeia de Markov é definido, para , por
dependendo se o passeio aleatório é para a direita ou para a esquerda. Podemos verificar facilmente que
uma vez e são bijeções de G em G . Assim, uma medição uniforme terminada é uma medição estacionária .
Exemplo:os passeios aleatórios mencionadas acima são as esferas aleatórios no aditivo grupos ℤ d e ℝ 2 .
Amplamente utilizado na modelagem de séries temporais contínuas, um passeio aleatório pode ser escrito:
Este é um caso especial de um processo autorregressivo (ou seja, “regrediu sobre si mesmo”) com ρ = 1 . O valor do parâmetro ρ é muito importante porque muda fundamentalmente a propriedade da série:
Recursivamente, um passeio aleatório é simplesmente a soma do ruído branco. Nós escrevemos: