Cadeias de Markov

Prévia do material em texto

Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
CADEIAS DE MARKOV
Geise dos Santos
Graciela Sturm
Jefferson Peruzzo
7 de maio de 2015
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
1 Introduca˜o
2 Cadeias de Markov
3 Exemplo
4 Definic¸o˜es
5 Aplicac¸o˜es
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Eventos e Estados
Alguns eventos sa˜o chamados independentes porque sua ocorreˆncia
na˜o depende da ocorreˆncia de eventos anteriores. Por exemplo, o
lanc¸amento de uma moeda.
Outros eventos podem depender exclusivamente do estado em que
o sistema se encontra num momento imediatamente anterior. Um
exemplo e´ dado no v´ıdeo.
Cada pote pode ser considerado um estado. A possibilidade de
mudanc¸a de estado e´ dado pelos nu´meros indicados.
Pode ocorrer uma mudanc¸a de estado ou uma permaneˆncia no
mesmo estado.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
A probabilidade de mudanc¸a de estado na˜o e´ independente, pois
depende da bolinha retirada no estado imediatamente anterior. O
que ocorre e´ que, independentemente do estado inicial (de qual
pote a primeira bolinha e´ retirada), depois de um nu´mero grande
de retiradas, a probabilidade de se observar cada estado converge
para um determinado valor.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Cadeia de Markov
Esse conceito de modelar sequeˆncias de eventos aleato´rios usando
estados e transic¸a˜o entre estados ficou conhecido como Cadeia de
Markov.
Andrei Markov (1856 -1922)
Foi um matema´tico russo. Era interessado na teoria dos nu´meros,
ana´lise, e teoria das frac¸o˜es cont´ınuas, a qual aplicava na teoria da
probabilidade.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Exemplo - Retirado de Poole (2004)
E´ realizada uma pesquisa de mercado para determinar a
prefereˆncia das pessoas em relac¸a˜o a duas marcas de pasta de
dente. A amostra consiste em 200 pessoas; cada uma experimenta
duas marcas durantes va´rios meses. Baseada nas respostas do
levantamento, a equipe de pesquisa compila a seguinte estat´ıstica:
Dos que usaram a marca A em qualquer meˆs, 70% se
mantiveram fie´is no meˆs seguinte e 30% mudaram para a
marca B;
Dos que usaram a marca B em qualquer meˆs, 80% se
mantiveram fie´is no meˆs seguinte e 20% mudaram para a
marca A.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Convertendo as porcentagens para decimais e as considerando com
probabilidade, temos:
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
A figura representa uma Cadeia de Markov, pois:
Ha´ um nu´mero finito de estados (marcas A e B);
A cada passo o processo pode estar em qualquer dos estados,
podendo permanecer ou mudar no passo seguinte;
O estado para o qual o processo muda no passo seguinte, e a
possibilidade disso ocorrer depende apenas do estado
imediatamente anterior, e na˜o da histo´ria pela qual o processo
passou.
Obs.: essas probabilidades de transic¸a˜o dizem respeito a`
probabilidade de transic¸a˜o do estado i para o estado j.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Supondo que no primeiro meˆs 120 pessoas estejam usando a marca
A e 80 pessoas a marca B, quantas pessoas estara˜o usando cada
uma das marcas um meˆs depois?
A = 0.7 · (120) + 0.2 · (80)→ A = 100
B = 0.3 · (120) + 0.8 · (80)→ B = 100
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Notemos que essas operac¸o˜es podem ser descritas como a seguinte
equac¸a˜o matricial:[
0.7 0.2
0.3 0.8
]
·
[
120
80
]
=
[
100
100
]
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Matriz de transic¸a˜o
A matriz P =
[
0.7 0.2
0.3 0.8
]
e´ chamada matriz de transic¸a˜o e os
elementos pij representam a probabilidade de transic¸a˜o do estado j
para o estado i. Por exemplo, p11 = 0.7 significa que 70% dos
usua´rios permanecera˜o no estado 1 (Marca A); p12 e´ probabilidade
de transic¸a˜o do estado 2 (Marca B) para o estado 1 (Marca A).
Note que a soma dos elementos das colunas e´ 1. Cada coluna
dessa matriz e´ chamada vetor de probabilidade.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Formalmente
Dados os k estados poss´ıveis de uma cadeia de Markov, a
probabilidade de o sistema estar no estado i em qualquer
observac¸a˜o se na observac¸a˜o imediatamente precedente estava no
estado j , e´ denotado por pij e e´ chamada probabilidade de
transic¸a˜o do estado j ao estado i. A matriz P = pij e´ a matriz de
transic¸a˜o (HOWARD & RORRES, 2001).
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Vetor estado
Os vetores x0 =
[
120
80
]
e x1 =
[
100
100
]
sa˜o denominados
vetores estados da cadeia de Markov.
Formalmente
Um vetor de estado de uma observac¸a˜o com k estados de uma
cadeia de Markov e´ um vetor coluna x cujo o i-e´simo componente
xi e´ a probabilidade do sistema estar, naquela observac¸a˜o, no
i-e´simo estado (HOWARD & RORRES, 2001).
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Propriedades
Sendo k um estado arbitra´rio, os vetores estado obedecem a`
seguinte relac¸a˜o:
xk+1 = P · xk
E´ poss´ıvel encontrar encontrar o vetor estado para qualquer k por
um processo iterativo.
Mas. . . x2 = Px1 e x1 = Px0
Substituindo, obtemos: x2 = P(Px0) = P
2x0.
Assim, para encontrar o vetor estado em qualquer momento k,
utiza-se a relac¸a˜o
xk = P
kx0
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Vetor de Estado Estaciona´rio
Depois de um certo nu´mero de processos, os vetores de estado
convergem para uma certa probabilidade, e uma vez alcanc¸ada
essa distribuic¸a˜o, ela jamais mudara´.
No exemplo em estudo:
x10 =
[
0.4001
0.5998
]
e x11 =
[
0.4000
0.5999
]
Parece que os vetores de estado se aproximam do vetor
[
0.4
0.6
]
, o
que significa que futuramente, 40% da amostra usara´ a pasta A e
60% a pasta B.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Utilizando a relac¸a˜o xk+1 = P · xk , e´ poss´ıvel perceber que[
0.7 0.2
0.3 0.8
]
·
[
0.4
0.6
]
=
[
0.4
0.6
]
ou seja: x = P · x .
Um vetor com essa caracter´ıstica e´ chamado de vetor estaciona´rio.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Na˜o e´ nessa´rio calcular uma iterac¸a˜o k muito grande para descobrir
qual e´ o vetor de estado estaciona´rio.
Podemos utilizar a equac¸a˜o matricial
Px = x reescrevendo-a como Px = Ix . Esta pode ser reescrita
como (I − P)x = 0. Reca´ımosnum sistema linear homogeˆneo de
coeficentes I-P. A soluc¸a˜o do sistema e´ o vetor de estado
estaciona´rio.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
As Cadeias de Markov teˆm diversas aplicac¸o˜es na Engenharia,
Cieˆncias Naturais, da Computac¸a˜o entre outras. Alguns exemplos
sa˜o:
Gene´tica;
Crescimento Populacional;
. . .
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Outro exemplo
Um psico´logo coloca um rato em uma gaiola de treˆs
compartimentos, como mostra a Figura.
O rato foi treinado para selecionar uma porta aleatoriamente
sempre que tocarem um sinal, e dirigir-se atrave´s dela ao pro´ximo
compartimento.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Item a
Se o rato esta´ incialmente no compartimento 1, qual a
probabilidade de ele estar no compartimento 2 depois de tocarem o
sinal duas vezes? E depois de treˆs vezes?
Quais sa˜o as probabilidades do rato passar de um estado a outro?
p21 = p31 =
1
2 , p12 = p13 =
1
3 , p12 = p13 =
2
3 , p11 = p22 =
p33 = 0
Enta˜o a matriz de probabilidade e´ 0 1/3 1/31/2 0 2/3
1/2 2/3 0

O vetor estado inicial e´ x0 =
 10
0

Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Apo´s dois toques do sinal, temos
x2 = P
2 · x0 que nos da´ x2 ≈
 0.3330.333
0.333

Apo´s treˆs toques: x3 = P
3 · x0 que nos da´ x3 ≈
 0.2220.389
0.389

Enta˜o, apo´s dois toques, a probabilidade do rato estar no
compartimento 2 e´ 13 , e apo´s treˆs toques, 0.389.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
Introduca˜o
Cadeias de Markov
Exemplo
Definic¸o˜es
Aplicac¸o˜es
Item b
Em um prazo longo, quanto tempo o rato passara´ em cada
compartimento?
Podemos utilizar a relac¸a˜o (I − P)x = 0 que nos da´
x3 = t livre, x1 =
2
3 t e x2 = t.
Mas x1 + x2 + x3 = 1, porque e´ um vetor probabilidade. Enta˜o
x =
 1/43/8
3/8
, que nos diz, em longo prazo, quanto tempo o rato
passara´ em cada compartimento.
Geise dos SantosGraciela Sturm Jefferson Peruzzo CADEIAS DE MARKOV
	Introducão
	Cadeias de Markov
	Exemplo
	Definições
	Aplicações