Cadeia de Markov e Probabilidade em Grafos - Lista de Exercícios

Figure 1 Grafo de busca Questão 6 Considere o problema do rato no labirinto definido da seguinte maneira Inicialmente o rato está na célula 1 A cada minuto as portas são destravadas um alarme é disparado e o rato muda de célula escolhendo uma célula vizinha aleatoriamente Na célula 6 há comida queijo e na célula 8 um dispositivo que dá um choque não letal no rato Estes dois estados são absorventes encerrando o experimento A configuração é apresentada a seguir Figure 2 Labirinto Pedese a Defina uma Cadeia de Markovo para este problema Escreva a matriz de transição de probabilidade do sistema b Determine o tempo médio de passos para o fim do processo c Determine o numero médio de visitas em cada estado lugar célula do labirinto d Determine a probabilidade do experimento se encerrar na célula 6 a Construa a matriz de transição e grafo de transição para esse modelo b Suponha que um coelho inicie no grupo 1 Qual a probabilidade de quatro semanas depois ele estar no grupo 2 Questão 5 Os motores de busca surgiram logo após o aparecimento da Internet com a intenção de prestar um serviço extremamente importante a busca de qualquer informação na rede apresentando os resultados de uma forma organizada e também com a proposta de fazer isto de uma maneira rápida e eficiente A partir deste preceito básico diversas empresas se desenvolveram chegando algumas a valer milhões ou bilhões de dólares Entre as maiores empresas encontramse Google Yahoo Lycos Cadê e outras Os buscadores se mostraram imprescindíveis para o fluxo de acesso e a conquista de novos visitantes Suponha que o internauta navega por páginas da Web em um universo de cinco páginas como mostrado na Figura 1 sendo cada página um dos elementos do espaço de estados E O internauta escolhe a próxima página para ver selecionando com igual probabilidade a partir das páginas apontadas pela página atual Se uma página não tem qualquer ligação de saída por exemplo página 2 em seguida o interessado seleciona qualquer uma das páginas do universo com igual probabilidade Poderíamos estar interessados em encontrar a probabilidade de que o internauta veja a iésima página O comportamento de visualização pode ser modelado por uma Cadeia de Markov em que o estado representa a página atualmente visualizada Se a página atual aponta para k páginas então a próxima página é selecionada a partir desse grupo com probabilidade 1k Se a página atual não aponta para nenhuma página então a próxima página pode ser qualquer uma das cinco páginas com probabilidade de transição 15 a Com base nas informações do texto e no grafo de busca da Figura 1 não confunda com o grafo de transição de uma Cadeia de Markov construa uma Cadeia de Markov para este problema b Construa o grafo de transição para essa Cadeia e verifique se a cadeia é irredutível e aperiódica c Obtenha a proporção de visitas a longo prazo a cada página Interprete o resultado d Calcule o tempo médio de retorno a cada pagina