Cadeias de Markov e aplicações

Abstract

Este trabalho tem como principal objetivo resolver alguns problemas científicos via simula- ções, com ênfase aos problemas de decodificar um texto criptografado, escolher um vértice uniformemente ao acaso em um grafo com estrutura global desconhecida (como o grafo da internet, por exemplo) e o problema de retirar uma amostra de coloração para um grafo com distribuição uniforme dentre todas as colorações próprias. Com a finalidade de fornecer a fundamentação matemática necessária, apresenta-se a teoria clássica de Cadeias de Markov, suas propriedades básicas e teoria assintótica, destacando-se a convergência para a distribuição estacionária. Em sequência, foram realizadas simulações pelo método de Monte Carlo via Cadeias de Markov. Finalmente, foi discutido o tempo de convergência do algoritmo de Metropolis, conhecido como tempo de mistura