Matrizes de Markov (IST)

Os outros protagonistas são os vetores de estado, que contêm, por exemplo a informação sobre a probabilidade de estar sol ou nuvens num determinado dia, ou ainda a distribuição da população entre a cidade e os arredores numa dada região.

Um dos objetivos deste curso será descrever e simular o procedimento do Google, PageRank, enquanto motor de busca, para ordenar por importância as páginas da Internet quando se faz uma pesquisa sobre um determinado tópico. Com este fim, vamos usar conceitos e propriedades de matrizes e vetores, que são objetos matemáticos associados a Álgebra Linear, mas sobre os quais não precisamos de ter muitos conhecimentos a priori.

No final deste curso, os(as) participantes estarão aptos(as) a:

- construir modelos simples que permitem fazer certos tipos de previsões de tempo e de ocupações de salas num labirinto, entre outros modelos;

- explicar como funciona o algoritmo de ordenação de páginas web do Google;

- saber verificar em que condições (matemáticas) é que uma cadeia de Markov converge para um vetor de estado único (vetor estacionário).

Será de esperar ainda que no final do curso, os participantes saibam usar um software de cálculo numérico para fazer as contas mais trabalhosas destes modelos. Todos os exemplos neste curso correm no software Mathematica que é uma ferramenta de cálculo algébrico.

Pré-requisitos:

- Ao nível de conhecimentos na área de matemática:

. pressupõe-se que o(a) participante tem alguma familiaridade com cálculos algébricos simples;

. facilita ter alguns conhecimentos de operações algébricas com matrizes e vetores.

- Ao nível de utilização de software:

. Mathematica para algumas operações matriciais, mas podem ser usados outros programas (Maple, MATLAB, etc.), calculadoras programáveis com operações matriciais ou recorrer ao motor de busca computacional Wolfram Alpha (Wolfram|Alpha);

. as simulações deste curso correm num software gratuito (Wolfram CDF Player), que pode ser descarregado do site da Wolfram.

Os conceitos a abordar são:

- cadeias de Markov;

- matrizes de transição, i.e. matrizes de Markov;

- vetores estacionários integrados em modelos lineares, que permitem prever estados futuros (ou tempos de ocupação média) da cadeia, ou seja, prever o comportamento estatístico a longo prazo da cadeia.

Os 4 tópicos semanais são dedicados a:

- introduzir os conceitos básicos necessários para prever o longo prazo;

- descrever diferentes modelos de passeios aleatórios em labirintos e grafos (redes), que ajudam a entender o funcionamento geral das cadeias de Markov;

- explicitar os traços gerais de funcionamento do algoritmo do PageRank. Este procedimento será fundamentado por um teorema importante (Teorema de Perron-Frobenius), que é a base matemática que explica o comportamento estatístico dos modelos analisados durante o curso.

——————————————————————————————————————————————————
In this course on Markov matrices the main emphasis will be given to models for the application of Markov chains , where arrays are one of the main protagonists. The other players are the state vectors that contain, for example information about the probability of being sun or clouds on a given day, or the distribution of population between the city and the surrounding area in a given region.

One of the objectives of this course will describe and simulate the Google procedure, PageRank , while search engine to sort by important web pages when you do a search on a particular topic. To this end, we will use concepts and properties of matrices and vectors, which are mathematical objects associated with linear algebra, but on which we do not have much knowledge a priori .

At the end of this course, you will be able to:

- Build simple models that allow to predict the weather and occupation times for rooms in a maze, among other models;

- Explain how the Google search engine algorithm works in order to rank the importance of web pages;

- Know how to verify under which (mathematical) conditions a Markov chain converges to a unique vector state (steady-state vector).

It will be expected that at the end of the course you will be capable of using a numerical software to do the more complicated calculations of these models.

Prerequisites

In what concerns mathematical background:

- We assume that you are familiar with basic algebraic calculations;

- The knowledge of algebraic operations on matrices and vectors helps.

In what concerns numerical software:

- Mathematica software to perform several matrix operations, but it is possible to use other softwares (Maple, MATLAB, etc.), programmable calculators with matrix capabilities or to use the computational search engine Wolfram Alpha (Wolfram|Alpha);

- Simulations of this course run on a free software Wolfram CDF Player) that can be downloaded from Wolfram website.

The concepts to address are:

- Markov chains;

- Transition matrices, i.e. Markov matrices;

- Steady-state vectors integrated in linear models, which allow to predict future states (or occupation times) of the chain, that is, to predict the statistical behavior on the long-run of the chain.

The 4 weekly topics are dedicated to:

- Introduce the basic concepts needed to predict the long-run;

- Describe for a while different models of random walks in mazes and graphs (webs), which help to understand the general functioning of Markov chains;

- Explain the main features of the PageRank algorithm. This procedure will be supported by an important theorem (Perron-Frobenius theorem), which constitutes the mathematical basis for the statistical behavior of the several models analyzed during the course