MBA: Caminhante aleatório

Anterior: Por que usar e o que são modelos baseados em indivíduos | Índice: Ecologia | Próximo: Contexto

Caminhante aleatório

O problema do caminhante aleatório pode ser definido da seguinte forma: Um homem começa de um ponto $0$ e caminha 1 metro em uma linha reta, então ele vira um ângulo qualquer e anda outro $1$ metro em uma linha reta. Ele repete esse processo $n$ vezes, qual é a probabilidade de após estes $N$ passos que o homem esteja a uma distância entre $r$ e $r+\delta r$ da origem.

Inspirado por este problema, propõe-se uma situação bidimensional similar. A principal diferença constitui-se no fato de que o ângulo não é mais aleatório. Reescrevendo o problema, agora em cada um dos eixos, nos quais o homem se move de maneira independe, há uma probabilidade $p$ de se mover $1$ metro em um sentido e uma probabilidade $q=1-p$ de se mover no sentido contrário.

Trabalhando inicialmente apenas com uma dimensão, executando $N$ passos, um caminho possível para o homem terminar a simulação em uma posição $m=n_1-n_2$ tendo dado $n_1$ passos à direita e $n_2$ passos à esquerda, é dado por:

$$p^{n_1}{q}^{n_2}=p^{\frac{N+m}{2}}{q}^{\frac{N-m}{2}}$$Pois sendo $N=n_1+n_2$ podemo escrever: $$n_1=\frac{N+m}{2},n_2=\frac{N-m}{2}$$Porém, está é a probabilidade de obtermos apenas um dos caminhos que leva o homem a $m$. O número total de caminhos indistinguíveis com $n_1$ passos à direita e $n_2$ passos a esquerda é dado por: $$\frac{N!}{n_1!n_2!}=\frac{N!}{n_1!(N-n_1)!}=\frac{N!}{\left(\frac{N+m}{2}\right)!\left(\frac{N-m}{2}\right)!}$$ Temos então que a probabilidade estar na posição $m$ após $N$ passos é dado por: $$p(m,N)=\frac{N!}{\left(\frac{N+m}{2}\right)!\left(\frac{N-m}{2}\right)!}{p}^{\frac{N+m}{2}}{q}^{\frac{N-m}{2}}$$ Ou reescrevendo $n_1=n$ para facilitar, e lembrando que $n_1=\frac{N+m}{2}$ e $N=n_1+n_2$: $$p\left(n\right)=\frac{N!}{n!(N-n)!}{p}^n{q}^{N-n}=\left(\begin{array}{c}N\\ n\end{array}\right)p^n{q}^{N-n}$$ Onde $\left(\begin{array}{c}N\\ n\end{array}\right)=C_n^N$ também é chamado de combinatória. Utilizando o binômio de Newton: $${(x+y)}^n=\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^k$$Temos a normalização: $$\sum _{n=0}^{n}p\left(n\right)=\sum _{n=0}^n\left(\begin{array}{c}N\\ n\end{array}\right)q^{N-n}{p}^n={(p+q)}^N=1$$Uma vez que $p+q=1$. E lembrando que $p\left(n\right)$ é a probabilidade de estar em $m=2n-N$, ou seja de obtermos $n$ vezes passo a direita em $N$ passos no total, então o valor médio de $n$ pode ser dado por: $$⟨n⟩=\sum _{n=0}^{N}np\left(n\right)$$Derivando o binômio de Newton: $$\begin{array}{c}p\frac{d}{dp}{(p+q)}^N=pN{(p+q)}^{N-1}=pN\end{array}$$E também: $$\begin{array}{rl}p\frac{d}{dp}{(p+q)}^N& =p\frac{d}{dp}\left[\sum _{n=0}^n\left(\begin{array}{c}N\\ n\end{array}\right)q^{N-n}{p}^n\right]\\ & =p\sum _{n=0}^{n}n\left(\begin{array}{c}N\\ n\end{array}\right)q^{N-n}{p}^{n-1}\\ & =\sum _{n=0}^{n}n\left(\begin{array}{c}N\\ n\end{array}\right)q^{N-n}{p}^n\\ & =\sum _{n=0}^{n}np\left(n\right)\end{array}$$Então: $$pN=\sum _{n=0}^{n}np\left(n\right)=⟨n⟩$$E com isso podemos obter a posição final média $⟨m⟩$. Utilizando a notação anterior posição final exata é $m=n_1-n_2$, ou ainda podemos rescrever como $m=2n-N$, pois: $$n_1-n_2=n_1-(N-n_1)=2n_1-N$$ A partir destes resultados podemos obter: $$\begin{array}{rl}⟨m⟩& =\sum _{n=0}^{N}mp\left(n\right)\\ & =\sum _{n=0}^N(2n-N)p\left(n\right)\\ & =2\sum _{n=0}^{N}np\left(n\right)-\sum _{n=0}^{N}Np\left(n\right)\\ & =2⟨n⟩-N\sum _{n=0}^{N}p\left(n\right)\\ & =2⟨n⟩-N\end{array}$$ A princípio, não temos motivos para dar preferência para o movimento em nenhuma direção, logo é razoável utilizar $p=q=1/2$, o que resulta em $⟨n⟩=N/2$ consequentemente $⟨m⟩=0$. O que pode parecer contra-intuitivo para nosso modelo, mas além de distribuirmos animais por todo o espaço, o que resultado implica é a posição final média, mas é preciso entender que não impede que ao longo da simulação cada indivíduo percorra diferentes áreas do espaço.

Distribuição Gaussiana

Quando $N\to \mathrm{\infty }$ tendo $p\approx ̸1$ temos a distribuição Gaussiana: $$p\left(n\right)=\left(\begin{array}{c}N\\ n\end{array}\right)p^n{q}^{N-n}\approx \frac{1}{\sqrt{2\pi Npq}}\exp \left(\frac{-{(n-Np)}^2}{2Npq}\right)$$

Foi realizada uma simulação utilizando Python e o módulo Mesa, grande parte do código segue a mesma discussão feita anteriormente no Jogo da Vida. A figura ilustra uma simulação com 10.000 caminhantes aleatórios em uma grade 100 X 100, iniciando na posição P=(50,50).

Resultado da simulação com a distribuição gaussiana sobreposta para N=100 para ambas as coordenadas.

Código

#Bibliotecas necessárias
from mesa import Agent, Model                                      #Classes Agente e Modelo
from mesa.time import SimultaneousActivation                       #Agendador simultâneo
from mesa.space import MultiGrid                                   #Malha multigrid
import random                                                      #Número aleatórios

#AGENTE---------------------------------------------------------------------------------
class Agente(Agent):
    """Classe do agente"""
    def __init__(self,modelo):
      """Bibliotecas necessárias"""
      #modelo     - Modelo que ao qual o agente pertence
      super().__init__(self,modelo)             #Necessário para funcionar o modelo
      self.ppos=(0,0)
      
    def step(self):
      """Método obrigatório que prepara as mudanças"""
      dx = (+1) if (random.random()<0.5) else(-1)
      dy = (+1) if (random.random()<0.5) else (-1)
      self.ppos = (self.pos[0]+dx,self.pos[1]+dy)                                 #Próxima posição
          
    def advance(self):
        """Método obrigatório que aplica as mudanças"""
        self.model.grid.move_agent(self, self.ppos)

#MODELO
class Modelo(Model):
    """Modelo geral"""

    def __init__(self, modelo,N,seed=None):
        """Função chamada quando o modelo é inicializazdo"""
        # Modelo   - Dicionário com especificações do modelo
        # N        - Quantiade de caminhantes
        # seed     - Seed dos números aleatórios do modelo do mesa
        
        largura = modelo["Largura"];altura=modelo["Altura"];seed_random=modelo["Seed"]
        random.seed(seed_random)                                 #Seed dos números aleatórios
        self.grid     = MultiGrid(largura, altura, True)         #Configura a grade
        self.schedule = SimultaneousActivation(self)             #Configura o agendador
        self.running  = True                                     #Condiçao para seguir executando o modelo
        for n in range(N):
          a = Agente(self)
          self.schedule.add(a)
          X= 50
          Y= 50
          self.grid.place_agent(a, (X, Y))
            
    def step(self):
        """Avançar um passo do modelo"""
        self.schedule.step()                              #Avançamos os agentes


MAX =100
N=10000
modelo  = {"Largura":100   ,"Altura":100       ,"Seed":0} 
M = Modelo(modelo,N)
for i in range(MAX):
    M.step()
    if ((i+1)%(MAX/100)==0):
      print(str(100*(1+i)/MAX)+"%")

E o gráfico foi gerado utilizando:

import numpy as np
import matplotlib.pyplot as plt


x=[];y=[]
for a in M.schedule.agents:
  x.append(a.pos[0])
  y.append(a.pos[1])

a,b,c=plt.hist(x, 70, density=True, facecolor='g', alpha=0.75)
m=1
K=100
X=np.arange(0,100, 0.1)
sigma = 2*np.pi*K*0.5*0.5
plt.plot(X,np.exp(-((X-K*0.5)**2)/sigma)/(np.sqrt(sigma)))

Acima fazendos um histograma das posições em x, uma alteração simples permite visualizarmos o equivalente em y.

Principais materiais utilizados:

• The Problem of the Random Walk. (Karl Pearson, Nature)
• A Modern Course in Statistical Physics (L.E. Reichl)

Anterior: Por que usar e o que são modelos baseados em indivíduos | Índice: Ecologia | Próximo: Contexto