Estudo do efeito da dimensionalidade do espaço em buscas aleatórias

Abstract

Neste trabalho investigamos a dependência com a dimensão do espaço de busca de pro- priedades estatísticas do problema do caminhante aleatório em 1D e 2D realizando uma busca por sítios-alvo cuja localização é desconhecida (problema da busca aleatória ou random se- arch). Um dos nossos principais objetivos foi analisar se a dimensionalidade do espaço de busca tem influência direta no mecanismo que controla alguns parâmetros importantes do sistema. Estudamos três quantidades estatísticas (eficiência η, probabilidades do caminhante encontrar o último alvo visitado P0 e de encontrar os demais sítios PL e a entropia de Shannon S) rele- vantes ao problema da busca aleatória. Utilizando técnicas de Física Estatística conseguimos modelar o problema de random search, sendo a nossa principal fonte de inspiração a questão ecológica da busca por alimentos feita por várias espécies de animais (problema do foraging). Realizamos o estudo descrito para duas distribuições de probabilidades de tamanhos de passos do buscador: a distribuição do tipo lei de potência e a distribuição α-estável de Lévy, com 0 < α ≤ 2. Revisamos para o caso 1D a obtenção de uma expressão analítica para a distân- cia média percorrida entre dois encontros sucessivos e consequentemente para a eficiência da busca. Além disso, calculamos as probabilidades P0 e PL, as quais permitem obter a entropia de Shannon S associada ao problema. Descobrimos que as probabilidades P0 e PL, bem como a entropia S, se comportam em função de α de forma bem diferente em uma dimensão e em duas dimensões, um resultado surpreendente até então inédito na literatura. Enquanto em 1D sempre se tem P0 ≥ PL, em 2D ocorre um cruzamento interessante que separa os regimes de busca com P0 > PL para os maiores valores de α e P0 < PL para os pequenos valores de α, dependendo da distância inicial até o último alvo encontrado. Também obtemos em 2D um máximo na entropia S para α ∈ (0, 2], não observado em 1D, com exceção do limite balístico α → 0. Nosso trabalho aprimora a compreensão do papel relevante da dimensionalidade do espaço em buscas aleatórias em diversos contextos, como, por exemplo, no problema das taxas de encontro em biologia e ecologia.