Cadeias de Markov

Prévia do material em texto

Cadeias de Markov
PROF.: ME. OCTÁVIO TORRES
Aplicações
 Uma companhia telefônica está interessada em analisar a sua
situação de mercado. Mais especificamente ela está interessada em
analisar a sua situação em frente as duas maiores concorrentes.
Utilizando o banco de dados sobre os seus clientes nos últimos anos o
analista construiu a tabela abaixo. Considerando que um usuário é
cliente da Escuro, qual a probabilidade de que ele ainda seja cliente
desta companhia daqui a 5 anos?
Prof.: Me. Octávio Torres
2
Escuro Tchau Morto Outras
Escuro 0,60 0,10 0,25 0,05
Tchau 0,15 0,5 0,3 0,05
Morto 0,06 0,02 0,85 0,07
Outras 0,15 0,1 0,5 0,25
Aplicações
 A cervejaria líder da Costa Oeste (chamada A) contratou um analista 
de PO para analisar sua posição de mercado. Fizeram uma pesquisa 
de mercado e os resultados foram resumidos na tabela a seguir:
 Se um cliente tomou cerveja A hoje, qual a probabilidade que volte a 
tomar a cerveja A daqui a 10 rodadas?
Prof.: Me. Octávio Torres
3
A B C
A 0,8 0,15 0,05
B 0,25 0,7 0,05
C 0,15 0,05 0,8
Conceitos 
básicos
1. PROCESSO ESTOCÁSTICO: 
CONJUNTO INDEXADO DE 
VARIÁVEIS ALEATÓRIAS {XT} EM QUE 
O ÍNDICE T PERCORRE UM DADO 
CONJUNTO T.
2. TEMPO: PODE SER DISCRETO OU 
CONTÍNUO
3. ESTADOS: RESULTADOS/SITUAÇÕES 
QUE O PROCESSO PODE SE 
ENCONTRAR.
Prof.: Me. Octávio Torres
4
Definição
 Define-se processo estocástico como um conjunto indexado de
variáveis aleatórias 𝑋𝑡 , em que o índice t percorre dado conjunto T.
Normalmente, admite-se que T seja o conjunto de inteiros não
negativos e 𝑋𝑡 represente uma característica mensurável de interesse
no instante t.
Prof.: Me. Octávio Torres
5
Exemplo do clima
 O tempo na cidade de Centerville pode mudar de maneira bastante
rápida de um dia para o outro. Entretanto, as chances de se ter
tempo seco (sem chuvas) amanhã são ligeiramente maiores, caso
esteja seco hoje do que se chover hoje. Particularmente, a
probabilidade de termos tempo seco amanhã é de 0,8, caso hoje
esteja seco, porém, é de apenas 0,6 caso chova hoje. Essas
probabilidades não mudam, caso as informações sobre o tempo
antes de hoje também forem levadas em consideração.
Prof.: Me. Octávio Torres
6
Exemplo do clima
 A evolução do tempo, dia a dia, em Centerville é um processo
estocástico, começando em dado dia inicial (chamado aqui de dia
0), o tempo é observado em cada dia t, para t=0, 1, 2,... O estado do
sistema no dia t pode ser:
Estado 0 = Dia t é seco
Estado 1 = Dia t é chuvoso
Prof.: Me. Octávio Torres
7
Exemplo do clima
Portanto, para t=0,1,2..., a variável aleatória Xt assume os seguintes 
valores:
𝑋𝑡 = ቊ
0 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑠𝑒𝑐𝑜
1 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑐ℎ𝑢𝑣𝑜𝑠𝑜
Assim dizemos que o processo estocástico 𝑋𝑡 = 𝑋0, 𝑋1, 𝑋2, … fornece
uma representação matemática de como o estado do tempo em
Centerville evolui ao longo do tempo.
Prof.: Me. Octávio Torres
8
Cadeias de 
Markov
1. CADEIAS DE MARKOV: OS RESULTADOS 
PASSADOS NÃO INTERFEREM NO 
RESULTADO FUTURO.
2. PROBABILIDADE DE TRANSIÇÃO: É A 
PROBABILIDADE DE MUDANÇA DE UM 
ESTADO PARA OUTRO, PODEM SER:
3. ESTACIONÁRIAS: SE FOREM 
CONSTANTES AO LONGO DO TEMPO, 
OU:
4. NÃO ESTACIONÁRIAS: SE NÃO FOREM 
CONSTANTES (VARIAM NO TEMPO).
Prof.: Me. Octávio Torres
9
Propriedade Markoviana
 Essa propriedade diz que a probabilidade condicional de qualquer 
evento futuro, dados quaisquer eventos passados e o estado atual, é 
independente dos eventos passados e depende apenas do estado 
atual. Ou seja:
𝑃 𝑋𝑡+1 = 𝑗|𝑋0 = 𝐾0, 𝑋1 = 𝐾1, …𝑋𝑡 = 𝑖, = 𝑃 𝑋𝑡+1 = 𝑗|𝑋𝑡 = 𝑖,
Prof.: Me. Octávio Torres
10
Cadeias de Markov
 Um processo estocástico Xt é dito ter a propriedade Markoviana se o
resultado anterior for válido ao longo de todo o processo, ou seja,
para todo T.
 Um processo estocástico é uma cadeia de Markov se possuir a
propriedade markoviana.
Prof.: Me. Octávio Torres
11
Probabilidades de transição
 As propriedades condicionais 𝑃 𝑋𝑡+1 = 𝑗|𝑋𝑡 = 𝑖, para uma cadeia de 
Markov são chamadas probabilidades de transição (em uma etapa).
 Estas probabilidades de transição são consideradas estacionárias se 
não mudarem ao longo do tempo, ou seja, se forem constantes.
 E, pode ser consideradas não estacionárias caso contrário. 
Prof.: Me. Octávio Torres
12
Exemplo do clima
 Para o exemplo anterior vimos que a evolução diária do tempo em 
Centerville foi formulada como um processo estocástico 𝑋𝑡 em que:
𝑋𝑡 = ቊ
0 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑠𝑒𝑐𝑜
1 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑐ℎ𝑢𝑣𝑜𝑠𝑜
 E 𝑃 𝑋𝑡+1 = 0|𝑋𝑡 = 0 = 0,8
𝑃 𝑋𝑡+1 = 0|𝑋𝑡 = 1 = 0,6
Além disso, vimos que as probabilidades de chuva ou não amanhã 
dependem apenas do tempo hoje. Ou seja, este processo possui a 
propriedade markoviana, logo, é uma cadeia de Markov.
Prof.: Me. Octávio Torres
13
Ferramentas de 
análise
8. MATRIZ DE TRANSIÇÕES: MATRIZ 
MXM QUE DESCREVE AS 
PROBABILIDADES DE TODAS AS 
TRANSIÇÕES POSSÍVEIS DE UM 
ESTADO I PARA OUTRO J.
9. DIAGRAMA DE TRANSIÇÃO DE 
ESTADOS: IMAGEM/DIAGRAMA QUE 
REPRESENTA TODOS OS ESTADOS 
POSSÍVEIS DA CADEIA DE MARKOV, 
BEM COMO, AS RESPECTIVAS 
PROBABILIDADES DE TRANSIÇÃO 
ENTRE OS ESTADOS.
Prof.: Me. Octávio Torres
14
Matriz de transição
 Uma ferramenta muito útil para estudar as cadeias de Markov é a 
Matriz de transição. Esta matriz é quadrada (M linhas e M colunas) e 
representa a probabilidade de transição do estado i (linha) para o 
estado j (coluna). Por exemplo, uma Cadeia de Markov com apenas 
dois estados a matriz de transição fica como abaixo:
𝑃 =
𝑝00 𝑝01
𝑝10 𝑝11
Vale observar que o somatório das linhas deve ser sempre 1 (100%).
Prof.: Me. Octávio Torres
15
Exemplo do clima
 No exemplo do clima a matriz de transições é dada por:
𝑃 =
0,8 0,2
0,6 0,4
Ou seja, se a probabilidade de amanhã estar seco dado que hoje está 
seco é de 0,8, automaticamente a probabilidade de chover, dado que 
hoje está seco é 0,2. O somatório da linha é 1.
Se a probabilidade de amanhã estar seco dado que hoje choveu é 0,6, 
automaticamente a probabilidade de chover é 0,4. soma da linha é 1
Prof.: Me. Octávio Torres
16
Diagrama de transição
 O diagrama de transição é uma representação gráfica da matriz de 
transição. Esta ferramenta utiliza círculos para representar os estados e 
setas para representar as transições entre os estados. Sendo que cada 
seta é acompanhada pela probabilidade relacionada àquela 
transição.
Prof.: Me. Octávio Torres
17
Exemplo do clima
 No exemplo do clima temos apenas dois estados: Seco ou chuvoso, 
logo, o diagrama terá apenas dois círculos como abaixo:
Prof.: Me. Octávio Torres
18
0 1
0,2
0,6
0,40,8
Exemplo das ações
 Considere o seguinte modelo para o valor de uma ação. No final de 
determinado dia, o preço é registrado. Se a ação subiu, a 
probabilidade de que ela subirá amanhã é de 0,7. se a ação tiver 
caído, a probabilidade de que ela subirá amanhã é apenas 0,5. Para 
fins de simplificação, classificaremos o caso da ação permanecer 
estável como uma queda. Considerando que o processo estocástico 
é uma cadeia de Markov, responda:
a) Quantos são e quais são os estados envolvidos neste processo?
b) Monte a matriz e o diagrama de transições.
Prof.: Me. Octávio Torres
19
Aplicações
 A cervejaria líder da Costa Oeste (chamada A) contratou um analista 
de PO para analisar sua posição de mercado. Fizeram uma pesquisa 
de mercado e osresultados foram resumidos na tabela a seguir:
 Construa o diagrama de estados.
Prof.: Me. Octávio Torres
20
A B C
A 0,8 0,15 0,05
B 0,25 0,7 0,05
C 0,15 0,05 0,8
Exemplo da companhia telefonica
 Uma companhia telefônica está interessada em analisar a sua
situação de mercado. Mais especificamente ela está interessada em
analisar a sua situação em frente as duas maiores concorrentes.
Utilizando o banco de dados sobre os seus clientes nos últimos anos o
analista construiu a tabela abaixo. Construa o diagrama de transição.
Prof.: Me. Octávio Torres
21
Escuro Tchau Morto Outras
Escuro 0,60 0,10 0,25 0,05
Tchau 0,15 0,5 0,3 0,05
Morto 0,06 0,02 0,85 0,07
Outras 0,15 0,1 0,5 0,25
Exercícios
Prof.: Me. Octávio Torres
22
Exercício manutenção de máquinas
 A condição de uma máquina na ocasião da manutenção preventiva 
mensal é caracterizada como razoável, boa ou excelente. Para o mês 
t, o processo estocástico para essa situação pode ser representado 
como:
𝑋𝑡 = ൞
0 𝑠𝑒 𝑎 𝑐𝑜𝑛𝑑𝑖çã𝑜 𝑓𝑜𝑟 𝑟𝑢𝑖𝑚
1 𝑠𝑒 𝑎 𝑐𝑜𝑛𝑑𝑖çã𝑜 𝑓𝑜𝑟 𝑟𝑎𝑧𝑜á𝑣𝑒𝑙
2 𝑠𝑒 𝑎 𝑐𝑜𝑛𝑑𝑖çã𝑜 𝑓𝑜𝑟 𝑏𝑜𝑎
A figura a seguir representa o digrama de transição para esta situação:
Prof.: Me. Octávio Torres
23
 Monte a tabela de transição a partir do diagrama abaixo. Qual a 
probabilidade deste processo partir do estado 0 para o estado 1?
Prof.: Me. Octávio Torres
24
0 1
1,0
0,3
0,1
0,9
2
0,7
Compra de computadores
 Um professor de engenharia compra um novo computador a cada 
dois anos e tem preferencia por três modelos: M1, M2 e M3. Se o 
modelo atual por M1, o próximo computador pode ser M2 com 
probabilidade 0,2 ou M3 com probabilidade 0,15. Se o modelo atual 
for M2, as probabilidade de trocar para M1 e M3 são 0,6 e 0,25, 
respectivamente, e, se o modelo atual for M3, entã as probabilidades 
de trocar para M1 e M2 são 0,5 e 0,1, respectivamente. 
a) Represente a situação como uma cadeia de Markov.
b) Monte a matriz e o diagrama de transição.
Prof.: Me. Octávio Torres
25
Hemodiálise
 Pacientes que sofrem de falência renal podem fazer um transplante 
ou diálise periódica. Durante qualquer ano, 30% conseguem 
transplantes de pessoas que morreram e 10% recebem rins de um 
doador vivo. No ano seguinte a um transplante, 30% dos 
transplantados com rins de pessoas mortas e 15% dos que receberam 
rins de doadores vivos voltam à diálise. As porcentagens de óbitos 
entre os dois grupos são 20% e 10%, respectivamente. Entre os que 
continuam com a diálise, 10% morrem, e, entre os que sobrevivem 
mais de um ano após o transplante, 5% morrem e 5% voltam à diálise. 
Represente a situação como uma cadeia de Markov.
Prof.: Me. Octávio Torres
26
Probabilidade de transição em 
n etapas
Prof.: Me. Octávio Torres
27
Aplicação
 Como apresentado no início deste material, às vezes pode ser de 
interesse calcular a probabilidade de transição entre os estados de 
uma cadeia de Markov em duas ou mais etapas.
 No exemplo da companhia telefônica, a companhia está interessada 
em saber se, dado que uma pessoa é cliente da companhia hoje, 
qual a probabilidade de que daqui a 5 anos ele seja cliente?
 No exemplo da cervejaria, a empresa está interessada em saber qual 
a probabilidade de que, dado que um cliente tomou a cerveja A 
hoje, qual a probabilidade que volte a toma-la daqui a 10 rodadas?
Prof.: Me. Octávio Torres
28
Equações de Chapman-Kolmogorov
 A partir das equações de Chapman-Kolmogorov:
É possível demonstrar que para calcular a probabilidade de transição 
em n etapas, basta utilizarmos a matriz de probabilidades de transição e 
elevá-la à quantidade de etapas, ou seja:
𝑃(𝑛) = 𝑃𝑛
Prof.: Me. Octávio Torres
29
Exemplo do clima
 NO inicio deste material o tempo na cidade de Centerville foi 
modelado como uma cadeia de Markov e, a matriz de transição é 
dada por:
𝑃 =
0,8 0,2
0,6 0,4
Logo, se quisermos obter a matriz de transição em duas etapas, basta 
elevarmos esta matriz ao quadrado, ou seja:
𝑃(2) = 𝑃2 ou seja: 𝑃(2) =
0,8 0,2
0,6 0,4
×
0,8 0,2
0,6 0,4
′
=
0, 76 0,24
0,72 0,28
Podemos dizer então que, se choveu hoje, a probabilidade de que 
também chova depois de amanhã é de 0,28 (28%).Prof.: Me. Octávio Torres
30
Exercícios
Prof.: Me. Octávio Torres
31
Companhia telefônica
 Uma companhia telefônica está interessada em analisar a sua
situação de mercado. Mais especificamente ela está interessada em
analisar a sua situação em frente as duas maiores concorrentes.
Utilizando o banco de dados sobre os seus clientes nos últimos anos o
analista construiu a tabela abaixo. Considerando que um usuário é
cliente da Escuro, qual a probabilidade de que ele ainda seja cliente
desta companhia daqui a 2 anos?
Prof.: Me. Octávio Torres
32
Escuro Tchau Morto Outras
Escuro 0,60 0,10 0,25 0,05
Tchau 0,15 0,5 0,3 0,05
Morto 0,06 0,02 0,85 0,07
Outras 0,15 0,1 0,5 0,25
Cervejaria
 A cervejaria líder da Costa Oeste (chamada A) contratou um analista de 
PO para analisar sua posição de mercado. Fizeram uma pesquisa de 
mercado e os resultados foram resumidos na tabela a seguir:
 Se um cliente tomou cerveja A hoje, qual a probabilidade que volte a 
tomar a cerveja A daqui a 3 rodadas?
 Se um cliente tomou a cerveja B hoje, qual a probabilidade que ele tome a 
cerveja A daqui a 3 rodadas?
33
A B C
A 0,8 0,15 0,05
B 0,25 0,7 0,05
C 0,15 0,05 0,8
Ações
 Considere o seguinte modelo para o valor de uma ação. No final de 
determinado dia, o preço é registrado. Se a ação subiu, a 
probabilidade de que ela subirá amanhã é de 0,7. se a ação tiver 
caído, a probabilidade de que ela subirá amanhã é apenas 0,5. Para 
fins de simplificação, classificaremos o caso da ação permanecer 
estável como uma queda. Considerando que o processo estocástico 
é uma cadeia de Markov, responda:
 Se ação subiu segunda-feira, qual a probabilidade que ela também 
suba na quinta-feira?
Prof.: Me. Octávio Torres
34
Compra de computadores
 Um professor de engenharia compra um novo computador a cada 
dois anos e tem preferencia por três modelos: M1, M2 e M3. Se o 
modelo atual por M1, o próximo computador pode ser M2 com 
probabilidade 0,2 ou M3 com probabilidade 0,15. Se o modelo atual 
for M2, as probabilidade de trocar para M1 e M3 são 0,6 e 0,25, 
respectivamente, e, se o modelo atual for M3, então as 
probabilidades de trocar para M1 e M2 são 0,5 e 0,1, respectivamente. 
 Se o professor comprou hoje um computador M1, qual a 
probabilidade de que ele compre um computador M3 em 2021?
Prof.: Me. Octávio Torres
35
Hemodiálise
 Pacientes que sofrem de falência renal podem fazer um transplante ou 
diálise periódica. Durante qualquer ano, 30% conseguem transplantes de 
pessoas que morreram e 10% recebem rins de um doador vivo. No ano 
seguinte a um transplante, 30% dos transplantados com rins de pessoas 
mortas e 15% dos que receberam rins de doadores vivos voltam à diálise. As 
porcentagens de óbitos entre os dois grupos são 20% e 10%, 
respectivamente. Entre os que continuam com a diálise, 10% morrem, e, 
entre os que sobrevivem mais de um ano após o transplante, 5% morrem e 
5% voltam à diálise. 
Se hoje um paciente aguarda um transplante, qual a probabilidade de que 
ele também se encontre neste estado daqui a 3 anos? 
36