Marcha Aleatória
Introdução
Matematicamente, a marcha aleatória traduz a ideia de uma trajectória composta por passos consecutivos, cada um dado numa direcção aleatória.
A marcha aleatória é um processo estocástico simples com aplicações em campos muito diversos, que vão desde:
- a física, modelizando o movimento aleatório de partículas microscópicas imersas num fluido composto por moléculas muito mais pequenas - fenómeno conhecido como movimento browniano;
- à economia, o exemplo simples do jogo da moeda ao ar pode ser visto como a marcha aleatória num espaço a 1 dimensão;
- passando pela biologia, propagação de estímulos dentro do cérebro; etc.
Neste programa, pretende-se estudar a marcha aleatória numa rede regular bidimensional. Partindo de um ponto inicial, cada passo tem um comprimento constante lp, e só 4 direcções aleatórias - norte, sul, este e oeste são permitidas.
Uma das características principais da marcha aleatória vai ser aqui colocada em evidência. Em média, o número de passos necessários para que a trajectória atinja uma circunferência de raio r (a partir do seu centro) é
N=(r/lp)^2 (1).
Esta relação está também presente nos fenómenos de difusão de partículas em fluidos, se admitirmos que N é proporcional ao tempo decorrido. A título de curiosidade podemos mencionar que Einstein (no ano milagroso de 1905) utilizou a teoria cinética de fluidos para calcular a constante de proporcionalidade entre o tempo e a distância quadrática percorrida, em termos de constantes fundamentais das partículas e do fluido. Pouco mais tarde, a relação de Einstein permitiu a Perrin determinar experimentalmente o número de Avogadro.
A relação (1) é indicativa que a trajectória percorrida, apesar da sua forma complexa, tem na verdade dimensão 2 - a dimensão de uma área. No entanto, o número de pontos da fronteira da mesma trajectória são em média proporcionais a r^(4/3), um facto previsto por Mandelbrot através de simulações numéricas e provado rigorosamente apenas em 2001.
Neste programa, poder-se-á visualizar a complexidade da fronteira da trajectória da marcha aleatória numa rede regular bidimensional, que tal como os fractais geométricos e os atractores estranhos, exibem uma estrutura não trivial em escalas cada vez mais pequenas, e com uma dimensão fractal não inteira.
Início
Utilização
Para inicializar o programa de marcha aleatória, deve em primeiro lugar seleccionar o número de turtles ("ntartarugas") que vão executar as trajectórias, todas a partir do mesmo ponto central inicial.
Pode ainda seleccionar o comprimento do passo da rede bidimensional ("passos") da marcha aleatória.
Se quiser que as trajectórias parem ao atingir uma determinada circunferência limite, deve colocar o botão "limite?" em "on" e definir o raio da circunferência desejado ("raio-limite").
Caso contrário, se quiser que as trajectórias continuem indefinidamente, basta colocar o botão "limite?" em "off".
Depois de ter escolhido todos estes parâmetros, deve seleccionar "Preparar" e finalmente "Iniciar/Parar" para começar o procedimento da marcha aleatória.
No gráfico pode visualizar a distância (em relação ao ponto inicial central) quadrática média de todas as trajectórias (cujo número foi definido em ntartarugas) em função do número de passos ou iterações.
Se "limite?=on", cada uma das trajectórias é interrompida no momento em que atinge a circunferência limite. O gráfico da distância quadrática média deixa de ser actualizado assim que a primeira tartaruga é eliminada. Por fim, depois de todas as turtles terem sido eliminadas, o programa pára e o número médio de iterações necessário para atingir a circunferência é indicado automaticamente no "Command Center".
É possível visualizar a forma da fronteira da(s) trajectória(s) com o botão "Seleccionar Fronteira".
A imagem final pode ser gravada seleccionando "Exportar Mundo", e poderá ser analisada posteriormente no programa "calcula-dimensao.nlogo".
Início
Questões
1. Escolha um pequeno número de turtles (cada uma desenhará uma trajectória diferente) e um grande raio limite. Observe a evolução da distância quadrática média no gráfico. Compare com a evolução esperada. Aumente o número de tartarugas e comente os novos resultados obtidos.
2. Qual seria a evolução esperada, não para a distância quadrática mas para a abcissa quadrática média das trajectórias,
3. Escolha um grande número de tartarugas e diferentes passos/raios-limite. Corra o procedimento de marcha aleatória até todas as tartarugas serem eliminadas. Qual é em média o número de iterações necessário para atingir a circunferência limite que espera encontrar ? Compare com o resultado obtido, indicado na janela "Command Center" assim que o programa termina. (Sugestão: para acelerar as trajectórias clique no botão "on/off" do ecrã de visualização - as trajectórias deixam de ser actualizadas no ecrã.)
4. Com "limite?=off", uma só tartaruga e passo=1, correspondente à resolução máxima do ecrã, corra o procedimento de marcha aleatória durante algum tempo, de modo a obter uma imagem razoavelmente preenchida. Comente a estrutura final obtida à luz dos conceitos introduzidos neste módulo "Fractais". Comente também a estrutura da fronteira da trajectória (utilize o botão "Seleccionar Fronteira").
5. Com base na questão anterior, estime a probabilidade que uma dada casa da rede tem de permanecer para sempre livre do percurso da marcha aleatória. Justifique.
Início
Breve Análise do Código
Conceito Geral
Como em todos os outros modelos, o núcleo deste modelo encontra-se na função principal executar. Cada vez que esta função é executada deslocam-se todas as tartarugas numa direcção aleatória (cima, baixo, esquerda ou direita) e traça-se o caminho percorrido. No fim desta movimentação calcula-se a distância quadrática média a que as partículas se encontram do centro e marca-se o ponto no gráfico.
No caso de uma partícula atingir o raio limite, elimina-se essa partícula somando o valor ponderado das iterações até aí efectuadas, para no final da simulação quando todas as partículas forem eliminadas se obter o valor médio das iterações necessárias para uma partícula atingir o raio limite.
Variáveis globais
| itermed | mantem o valor das iterações médias efectuadas pelas partículas até ao raio limite |
| dist2med | registo da distância quadrática média para todas as partículas |
| turtles: dist | propriedade das turtles que mantem a sua distância ao centro |
| turtles: iter | propriedade das turtles que mantem o número de iterações até aí efectuadas |
| patches: remover? | utilizada pela função selec-fronteira para definir quais os patches a remover |
Funções principais
| preparar | limpa e inicializa todas as variáveis, criando e inicializando tambem as tartarugas. |
| executar | chamada pelo botão com o mesmo nome, esta função itera até que todas as tartarugas sejam eliminadas (quando atingem o raio limite) ou o utilizador interrompa a simulação. |
Funções auxiliares
| plot-dist2med | marca no gráfico a distância quadrática média dada no argumento |
| selec-fronteira | pinta de preto todos os pontos cujos 4 primeiros vizinhos estão pintados, mostrando assim a fronteira da imagem |
| verif-fronteira | utilizada pela função selec-fronteira, verifica para um dado patch se deve ser removido ou não |
| exportarmundo | exporta a imagem existente na caixa de visualização para poder ser importada pelo modelo calcula-dimensao |
Código
Variáveis globais
globals[ itermed dist2med ] turtles-own [ dist iter ] patches-own [ remover? ]
Funções Principais
preparar
to preparar
ca
set itermed 0
crt ntartarugas
ask turtles [
setxy 0 0
set dist 0
set iter 0
pd
set heading 0
set shape "bee"
set size 15
]
if limite? [
ask patches[
if (int (distancexy 0 0) = raio-limite)
[ set pcolor 3 ]
]
]
end
executar
to executar
if count turtles = 0 [
show "Número de iterações médio: "+ itermed
stop
]
set dist2med 0
ask turtles [
rt 90 * (random 4)
fd passos
set dist sqrt (xcor * xcor + ycor * ycor)
set dist2med dist2med + dist * dist
if limite? and dist >= raio-limite [
set itermed itermed + iter / ntartarugas
die
]
set iter iter + 1
]
set dist2med dist2med / ntartarugas
if count turtles = ntartarugas [
plot-dist2med dist2med
]
end
Funções auxiliares
plot-dist2med
to plot-dist2med [ d2med ] set-current-plot "Quadrado da Distância Média" plot d2med end
selec-fronteira
to selec-fronteira
if passos != 1 [
user-message "Para efectuar esta operação deve escolher passo = 1"
stop
]
if limite? [
ask patches[
if (int (distancexy 0 0) = raio-limite)
[ set pcolor black ]
]
]
ask patches [ set remover? false ]
ask patches with [ pcolor != black ][
verif-fronteira
]
ask patches with [ remover? ] [
set pcolor black
]
end
verif-fronteira
to verif-fronteira
locals [ remc ]
set remc 0
ask patches at-points [ [1 0] [0 1] [-1 0] [0 -1] ] [
if pcolor != black [
set remc remc + 1
]
]
if remc = 4 [
set remover? true
]
end
exportarmundo
;exporta o mundo (escreve o valor de todas as variáveis)
;para um ficheiro de nome nomeficheiro
to exportarmundo
locals [nomeficheiro ax ay]
set nomeficheiro user-input "Nome do ficheiro da saída:"
file-open nomeficheiro
file-print screen-size-x
file-print screen-size-y
show "sx: "+ screen-size-x + " sy: "+ screen-size-y
set ay (- screen-edge-y)
repeat screen-size-y
[
set ax (- screen-edge-x)
repeat screen-size-x
[
ask patch ax ay [
file-print pxcor
file-print pycor
file-print pcolor
]
set ax ax + 1
]
set ay ay + 1
]
file-close
end
Início
Variantes e Extensões
Faça uma análise estatística mais detalhada da marcha aleatória, incluindo a observação da média das trajectórias, desvio padrão, etc.
Implemente e analise as extensões mais conhecidas da marcha aleatória: marcha aleatória sem auto-intersecção ("self avoiding random walk"); marcha aleatória sem regresso ("no returning random walk"); etc.
Início