Modulo 2 - Cadeias de Markov - 2024-2

Prévia do material em texto

PESQUISA OPERACIONAL II – A 
Professor: Dr. Edwin B. Mitacc Meza
Cadeias de Markov
Pesquisa Operacional II
3
Introdução
➢ Como foi visto anteriormente, existe uma grande variedade de processos
estocásticos. Estes podem ser classificados como Markovianos e não
Markovianos.
➢ Os processos Markovianos se classificam de acordo ao espaço de estados
(ou simplesmente estados) e ao tipo de parâmetro (tempo).
➢ Se o espaço de estados é discreto o processo recebe o nome de cadeia de
markov, se o espaço de estados é contínuo, se conhece como processo
de markov.
➢ Segundo o parâmetro temporal, em ambos casos dividem-se em
processos ou cadeias de tempo contínuo ou tempo discreto.
➢ Nesta parte da disciplina focaremos a cadeia de markov de tempo
discreto.
Pesquisa Operacional II
4
Definição
➢ Uma cadeia de Markov é um processo estocástico em que a variável t
representa intervalos de tempo, {Xt , t=0, 1, 2, 3, ...}, e que goza da
propriedade de Markov, ou seja, a ocorrência de um estado futuro
depende somente do estado imediatamente precedente.
➢ Isso significa que, dados os tempos cronológicos t0, t1, ..., tn, diz-se que
a família de variáveis aleatórias {Xtn
}={x0, x1, ..., xn,} é de natureza
Markoviana se possuir a seguinte propriedade:
   101 101
,, −− ======
−− ntnttntnt xXxXPxXxXxXP
nnnn

Pesquisa Operacional II
5
Definição
➢ Em uma cadeia Markoviana com n estados (resultados) exaustivos e
mutuamente exclusivos, as probabilidades em um ponto especifico do
tempo t=0, 1, 2,... são habitualmente expressas por:
➢ Isso é conhecido como probabilidade de transição em uma etapa de
passar do estado i em t-1 ao estado j em t.
➢ Cabe ressaltar que estas probabilidades de transição entre estados são
constantes no tempo (cadeia de Markov estacionária).
  ( ) TtnjiiXjXP ttij ,,2,1,0;,,2,1,;1  ===== −
Pesquisa Operacional II
6
Representação
➢ Uma Cadeia de Markov em tempo discreto fica completamente definida
se conhecermos os estados X = {0, 1, 2, …, s} e as probabilidades de
transição entre os estados em um período.
➢ Existem duas formas de representação: graficamente, através do
“diagrama de transições”, ou através da matriz quadrada P que contém as
probabilidades de transição em um período.
Vamos ver um exemplo.
Pesquisa Operacional II
7
Representação
EXEMPLO:
No pequeno país PURO, a bebida tradicional, um estranho licor de flores
silvestres, é produzida apenas por duas famílias concorrentes, a família ICT e
a família IHS. Cada família introduziu, ao longo das gerações, diferentes
alterações na fórmula original, de forma a conferir ao “seu” licor um sabor
especial. Embora as fórmulas sejam guardadas no “segredo dos deuses”,
descobriu-se que uma porção de pétalas de malmequeres pode realmente
“fazer a diferença”, garantindo à família ICT a primazia nas preferências dos
PURO’s. De fato, verificou-se que, para cada pessoa que compre o licor ICT
há 90% de probabilidade do próximo licor que comprar seja licor ICT; já para
cada pessoa que compre o licor IHS há só 80% de probabilidade da essência
de miosótis o tornar tão inesquecível que o próximo licor comprado seja
ainda o licor IHS.
Com base nestes dados, pretende-se construir uma cadeia de
Markov que represente a situação descrita.
Pesquisa Operacional II
8
Representação
➢ Se X(t) representar o tipo de licor comprado por uma pessoa na sua t-
ésima compra, então a cadeia de Markov limita-se a assumir um dos dois
valores seguintes: F (último licor comprado foi o ICT) ou P (último licor
comprado foi o IHS). O espaço de estados será, deste modo, X={F,P}
Vamos representar a 
cadeia de Markov
Pesquisa Operacional II
9
Representação – Matriz de Transições
➢ Na matriz P, cada linha i representa o estado atual e cada coluna j
representa o estado futuro (a ordem dos estados atuais deve ser igual à
dos estados futuros, respectivamente, nas linhas e nas colunas de P).
➢ Deste modo, o elemento pij da matriz representa a probabilidade de
ocorrência da transição do estado i para o estado j em um período. A
matriz P é uma matriz estocástica, sendo os seus elementos
probabilidades, pij 0, e cada linha i uma distribuição de probabilidade,
j pij = 1.
0,90 0,10
0,20 0,80
(F) (P)
(P)
(F)
P=
Pesquisa Operacional II
10
Representação – Diagrama de Transições
➢ Num diagrama de transições cada estado é representado por um vértice,
e cada arco orientado ligando dois vértices representa uma transição
possível entre dois estados em um período, a qual tem uma certa
probabilidade de ocorrência (o coeficiente associado ao arco).
F P
0,10
0,20
0,90 0,80
Pesquisa Operacional II
11
Probabilidades de Transição
➢ O conhecimento das probabilidades de transição entre os estados é de
grande importância nas cadeias de Markov. Conforme foi referido
anteriormente, as probabilidades de transição em um período fazem
parte da “definição” da cadeia de Markov.
➢ É igualmente importante conhecer as probabilidades de transição em n
períodos ou passos.
➢ Define-se a probabilidade de transição em n passos como:
   
Xjit
iXjXPiXjXPP
ntnt
n
ij
=
======
+
,,...,, 210
0
Pesquisa Operacional II
12
Probabilidades de Transição
➢ Uma das formas de obter o valor de pij
(n) é calcular as probabilidades
de cada um dos caminhos que, partindo do estado i, conduzem ao
estado j em n passos, e somá-las.
➢ Apesar da aparente simplicidade deste método, à medida que n aumenta
também aumenta a possibilidade de esquecimento de caminhos
alternativos e o cálculo da probabilidade torna-se mais complexo.
Alternativamente pode-se calcular o elemento (i,j) da matriz Pn,
método bastante mais eficiente.
➢ Para demonstrar a equivalência dos dois métodos, voltemos ao exemplo
do PURO. Suponhamos que se pretende conhecer a probabilidade de a
terceira compra futura de um habitante de PURO ser licor IHS, sabendo
que, no momento presente, comprou licor ICT, ou seja, pFP
(3).
Pesquisa Operacional II
13
Probabilidades de Transição
➢ Uma hipótese seria calcular as probabilidades de todas as seqüências de
compras, de forma que a transição FP ocorra em três aquisições ou
passos.
➢ Assim, verifica-se que só há quatro seqüências diferentes de transições
em três passos tais que, partindo do estado F, se acaba no estado P.
1) F→P →P →P
2) F→F →P →P
3) F→F →F →P
4) F→P →F →P
Pesquisa Operacional II
14
Probabilidades de Transição
➢ Relembrando que, se A e B forem independentes, P{A e B} = P{A}  P{B},
podemos então calcular a probabilidade de cada seqüência:
➢ Do mesmo modo, P{A ou B} = P{A} + P{B}, pelo que
Pesquisa Operacional II
15
Probabilidades de Transição
➢ Houve aqui a aplicação direta das equações de Chapman-Kolmogorov:
➢ De fato, assumindo q = 1 e m = 2 aquisições,
sendo
Pesquisa Operacional II
16
Probabilidades de Transição
➢ Este resultado pode ser obtido por outra via, pois o elemento da linha
que corresponde ao estado F (estado atual) e da coluna que corresponde
ao estado P (estado futuro) da matriz P3 é exatamente 0.219.
➢ Na verdade, a forma usada para calcular o valor anterior (somar as
probabilidades de caminhos alternativos) corresponde exatamente à
operação de multiplicação de matrizes que nos conduz a P3, tendo
correspondência direta com as equações de Chapman-Kolmogorov.
Pesquisa Operacional II
17
Classificação dos Estados
➢ Um caminho do estado i para o estado j é uma seqüência de transições
com probabilidades de ocorrência positivas que ligam os dois estados (do
exemplo anterior: F→P → F → P). Não existe qualquer limite ao número
de transições nem há a obrigação da seqüência ser a mais curta entre os
dois estados.
➢ Diz-se que o estado j é atingível a partir do estado i se e só se houver pelo
menos um caminho de i para j. Dois estados i e j são comunicantes se e
só se j for atingível a partir de i e i for atingível a partir de j.
➢ Diz-se que uma Cadeia de Markov é irredutível se e só se qualquer
estado j for atingível a partir de qualquer estado i, ou seja, se todos os
estados forem comunicantes.Pesquisa Operacional II
18
Classificação dos Estados
➢ Os estados de uma cadeia de Markov podem ser classificados com base
na probabilidade de transição pij de P.
1) Um estado j se diz transiente se existir um estado k que seja atingível a
partir de j, mas não sendo j atingível a partir de k. Por outras palavras, se
j for transiente não há a garantia de, saindo de j, voltar lá.
2) Um estado j se diz recorrente se não for transiente, ou seja, se for
sempre possível regressar a j.
0 1
0,40
1
2 3
0,40
1
0,60
Transiente = 0,1 Recorrente = 2,3
Pesquisa Operacional II
19
Classificação dos Estados
3) Um estado j se diz absorvente se após o processo lá entrar não mais
voltar a sair, ou seja, se pjj = 1.
4) Um estado recorrente j se diz periódico com período k>1 se k for o
menor inteiro tal que todos os caminhos de j para j tiverem um
comprimento múltiplo de k.
Transiente = 1, 2
Absorvente = 0
0
1
0,40
1
2
0,30
0,70
0,60
0 1
0,30
1
2
1
0,70
Periódico = 0, 1, 2
Pesquisa Operacional II
20
Classificação dos Estados
5) Um estado recorrente diz-se aperiódico se k = 1.
➢ Uma cadeia de Markov diz-se ergódica se todos os estados forem
recorrentes, aperiódicos e comunicantes.
0 1
1
0,25
0,75
Pesquisa Operacional II
21
Probabilidades de Estado Estável ou em Equilíbrio 
➢ Numa Cadeia de Markov ergódica, decorrido um número muito elevado
de períodos de tempo (n→), a probabilidade do processo estar no
estado j é constante e independente do estado inicial i.
➢ Isto pode ser observado através da matriz P16, que contém as
probabilidades de transição em dezesseis períodos (exemplo PURO):
➢ A esta probabilidade chama-se probabilidade em equilíbrio do estado j e
representa-se por j. Por outras palavras,
Pesquisa Operacional II
22
Probabilidades de Estado Estável ou em Equilíbrio 
➢ Essas probabilidades podem ser determinadas com base nas equações:
(Uma das equações em = P é redundante) O que = P diz é que as
probabilidades  permanecem inalteradas após uma transição e, por esta
razão, representam a distribuição do estado em equilíbrio.
➢ Relembrando o exemplo que nos acompanha desde o início, quais são as
probabilidades Estacionárias?
 =
=
j
j
P
1

Pesquisa Operacional II
23
Probabilidades de Estado Estável ou em Equilíbrio 
Significa que, após bastante tempo, cerca de dois terços das pessoas,
em média, comprarão o licor RCT, enquanto que só um terço delas irá
comprar o licor RIR. Deste modo as probabilidades de estado estável
podem ser usadas como indicadores das quotas de mercado de cada
marca e ser muito úteis em processos de tomada de decisão.
0,90 0,10
0,20 0,80
(F) (P)
(P)
(F)
P=
( ) ( ) 





==
8020
1090
,,
,,
,,
PFPF
P 



+=
+=
PFP
PFF


8010
2090
,,
,,
11 =+= PF
j
j

33330
66660
,
,
=
=
P
F


Pesquisa Operacional II
24
Tempo Médio de Recorrência (Tempo Médio do primeiro retorno)
➢ Um subproduto direto das probabilidades de estado no equilíbrio (ou
probabilidades de estado estável) é a determinação do número esperado
de transições antes de os sistemas retornarem a um estado j pela
primeira vez.
➢ Isto é conhecido como tempo médio de recorrência, e é calculado em
uma cadeia de Markov de n estados por:
nj
j
jj ,...,2,1,
1
==


Pesquisa Operacional II
25
➢ Considerando o exemplo PURO:
0,90 0,10
0,20 0,80
(F) (P)
(P)
(F)
P= 33330
66660
,
,
=
=
P
F


51
66660
11
,
,
==
F
FF


3
33330
11
==
,
P
PP


Probabilidades de Estado Estável
Se o último licor comprado foi ICT, então, levará 
1,5 transições para voltar a comprar ICT.
Se o último licor comprado foi IHS, então, levará 
3 transições para voltar a comprar IHS.
Tempo Médio de Recorrência (Tempo Médio do primeiro retorno)
Pesquisa Operacional II
26
➢ O número esperado de transições necessárias para chegar ao estado j
pela primeira vez, partindo do estado i, é chamado tempo de transição.
➢ Qualquer que seja a cadeia de Markov, a transição do estado i para o
estado j é feita em um período com probabilidade pij, e em todos os
outros casos (k≠j) o número esperado de períodos será igual a (1+kj)
com probabilidade pik. Então podemos escrever o seguinte sistema de
equações:


+=
jk
kjikij
p  1
Tempo de Transição (Tempo Médio da primeira passagem)
Pesquisa Operacional II
27
➢ Considerando o exemplo PURO:


+=
jk
kjikij
p  10,90 0,10
0,20 0,80
(F) (P)
(P)
(F)
P=
Tempo de Transição (Tempo Médio da primeira passagem)
FPFPFFFP
p  90011 ,+=+= 10=
FP

PFPFPPPF
p  80011 ,+=+= 5=
PF

FP significa que uma pessoa que compre o licor ICT demora, em média, 10
períodos até passar a comprar licor IHS.
Pesquisa Operacional II
28
➢ Um modo mais simples de determinar o tempo médio da primeira
passagem para todos os estados em uma matriz de m transições P, é usar
a seguinte fórmula baseada em matriz:
onde,
I = Matriz identidade (m-1)
Nj = Matriz de transição P menos sua j-ésima linha e sua j-ésima
coluna do estado visado j.
1 = vetor coluna (m-1) com todos os elementos iguais a 1.
( ) ijNI
jij
−=
−
,1
1

Tempo de Transição (Tempo Médio da primeira passagem)
Pesquisa Operacional II
29
➢ Consideremos a seguinte matriz de transições e calcule os tempos de
transição para o estado 1 a partir dos estados 2 e 3.
0,30 0,60 0,10
0,10 0,60 0,30
0,05 0,40 0,55
P=
Tempo de Transição (Tempo Médio da primeira passagem)
?,
3121







=
10
01
I 





=
550400
300600
1 ,,
,,
N 





=
1
1
1
( ) 





=











=











−
−
=−=





−
−
3413
5012
1
1
676676
005507
1
1
45040
3040
1
1
1
31
21
,
,
,,
,,
,,
,,
j
NI


Pesquisa Operacional II
30
Análise de Estados Absorventes
EXEMPLO:
Todo ano no inicio da estação de plantio de mudas (março a setembro), um
jardineiro usa um teste químico para verificar a condição do solo.
Dependendo do resultado do teste, a produtividade para a nova estação cai
em um dos três estados: 1) bom; 2) razoável e 3) ruim. A longo dos anos, o
jardineiro observou que a condição do solo no ano anterior causava um
impacto sobre a produtividade no ano corrente e que a situação poderia ser
descrita pela seguinte cadeia de Markov:










=
100
50500
305020
,,
,,,
P
1 2 3
1
2
3
estado do sistema 
no ano seguinte
estado do sistema 
neste ano
Pesquisa Operacional II
31
Análise de Estados Absorventes
➢ Os estados 1 e 2 (condições do solo boa e razoável) são transientes e o
estado 3 (condição do solo ruim) é absorvente porque, uma vez nesse
estado, o sistema ali permanecerá indefinidamente.
➢ Uma cadeia de Markov pode ter mais de um estado absorvente. Por
exemplo, um profissional pode continuar empregado na mesma empresa
até se aposentar ou pode sair alguns anos antes (dois estados
absorventes) .
➢ Nesse tipo de cadeias, estamos interessados em determinar a
probabilidade de chegar à absorção e o número esperado de
transições até a absorção dado que o sistema começa em um estado
transiente especifico.
Pesquisa Operacional II
32
Análise de Estados Absorventes
➢ No exemplo, se a condição atual do solo for boa, estaremos interessados
em determinar o número médio de estações de plantio de mudas até o
solo tornar-se ruim, e também na probabilidade associada a esta
transição.
➢ A análise de cadeias de Markov com estados absorventes pode ser
executada convenientemente usando matrizes. Em primeiro lugar, a
cadeia de Markov é repartida da seguinte maneira:
o arranjo requer que todos os estados absorventes ocupem o canto
sudeste da nova matriz






=
I
AN
P
0
Pesquisa Operacional II
33
Análise de Estados Absorventes
Por exemplo, considere a seguinte matriz de transição:
A matriz P pode ser rearranjada e repartida como:












=
1000
2003050
0010
10403020
,,,
,,,,
P
1 2 3 41
2
3
4












=
1000
0100
2030050
10304020
,,,
,,,,
'P
1 3 2 4
1
3
2
4
Pesquisa Operacional II
34
Análise de Estados Absorventes
Neste caso, temos:












=
1000
0100
2030050
10304020
,,,
,,,,
'P
1 3 2 4
1
3
2
4






=
050
4020
,
,,
N 





=
2030
1030
,,
,,
A 





=
10
01
I






=
I
AN
P
0
Pesquisa Operacional II
35
Análise de Estados Absorventes
➢ Com as matrizes definidas anteriormente, podemos mostrar que:
Tempo esperado para absorção
Probabilidade de absorção
( ) 1
1−
−= NI
( ) 





=











=



















−





=−
−
−
16672
33332
1
1
3333183330
6667066671
1
1
050
4020
10
01
1
1
1
,
,
,,
,,
,
,,
NI
( ) ANI
1−
−=
( ) 





=











=−
−
350650
300700
2030
1030
3333183330
6667066671
1
,,
,,
,,
,,
,,
,,
ANI
Pesquisa Operacional II
36
Probabilidades de Transição absolutas
➢ Dadas as probabilidades iniciais a(0)={aj
(0)} de iniciar no estado j e a
matriz de transição P de uma cadeia de Markov, as probabilidades
absolutas a(n)={aj
(n)} de estar no estado j após n transições (n>0) são
calculadas da seguinte maneira:
,..2,1,)0()(
3)0(2)0()2()3(
2)0()0()1()2(
)0()1(
==
===
===
=
nPaa
PaPPaPaa
PaPPaPaa
Paa
nn

	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36