CAPÍTULO 3

CADEIAS DE MARKOV
¾ Propriedades da Cadeia de Markov:
¾ Igualdade de Markov
¾ Classificação dos Estados numa Cadeia de Markov
¾ Probabilidades do Estado Estacionário
¾ Tempos de Primeira Passagem
¾ Exemplos de Cálculo
¾ Exercícios Propostos

47
3. CADEIAS DE MARKOV
Às vezes interessa-nos saber como é que uma variável aleatória varia com o tempo. O
estudo sobre como uma variável aleatória varia com o tempo inclui processos
estocásticos, anteriormente discutidos. Neste capítulo focar-se-á num tipo de processo
estocástico conhecido como uma Cadeia de Markov.
Um processo estocástico {XE} possui a propriedade markoviana quando a
probabilidade condicional de qualquer “acontecimento” futuro dado qualquer
“acontecimento” passado e o estado presente xt = 1, é independente do acontecimento
passado e só depende do estado presente do processo. Em outras palavras, a
propriedade markoviana traduz o facto de o conhecimento do fenómeno em
determinado instante do tempo fornecer toda a informação sobre a estrutura
probabilística da sua evolução futura, independentemente do conhecimento desse
fenómeno em instantes anteriores. A propriedade condicional representa uma previsão
ao processo daquilo que vai acontecer.

P{xt +1 = j xt = i} = p ij

onde pij é a probabilidade que dado o sistema no estado i no tempo t, estará no estado
j no tempo t+1.
Se o sistema se mover do estado i durante um período para estado j durante o período
seguinte, dissemos que ocorreu uma transição do estado i para estado j.

A probabilidade condicional
Transição a 1 passo P{xt +1 = j xt = i}

Transição em 2 passos pij2 = P{xt + 2 = j xt = i} = {x3 = j x1 = i}

Transição em n passos pijn = P{xt + n = j xt = i} = {xn +1 = j x1 = i}

A equação P{xt +1 = j xt = i} = pij dá-nos a entender que a lei de probabilidade que

relaciona o estado seguinte ao estado corrente não muda (ou permanece estacionária)
ao longo do tempo. Qualquer cadeia de Markov que satisfaça essa equação é chamada
cadeia de Markov estacionária.

48
3.1. Propriedades da Cadeia de Markov:
Um determinado sistema diz-se que é uma cadeia de Markov se:
ƒ Tem um número finito de estados
ƒ Satisfaz a propriedade Markoviana
ƒ As probabilidades transitórias são estacionárias
ƒ Tem um conjunto de probabilidades iniciais.

Em muitas aplicações, as probabilidades de transição são apresentadas como uma

matriz de probabilidade de transição P, ou seja, matriz de passagem do sistema para
um processo com k estados possíveis.
p11 p12 ... p1k
p21 p22 ... p2 k
P1 =
... ... ... ...
pk 1 pk 2 ... pkk

Dado que o estado no tempo t é i, o processo pode estar num outro estado no tempo
t+1. Isso significa que para cada i,
j =k

∑ P{x
j =1
t +1 = j ( xt = i )} = 1

j =k

∑p
j =1
ij =1 (i = 1, 2,...k)

Importa salientar que cada elemento da matriz de transição deve ser não negativo.

3.2. Igualdade de Markov

Suponha que estamos a estudar uma cadeia de Markov com uma matriz de
probabilidade de transição conhecida P. A questão que se coloca é: se uma cadeia de
Markov estiver no estado i no tempo m, qual é a probabilidade de que n períodos mais
tarde a cadeia de Markov esteja no estado j? A equação de Chapman-Kolmagorov
permite relacionar as probabilidades condicionadas de transição de estado para
intervalos de tempos quaisquer. Desde que estejamos a lidar com uma cadeia de
Markov estacionária, essa probabilidade será independente de m, e deste modo pode-
se escrever
P{xm+ n = j xm = i} = P{xn = j xo = i} = pij (n)

onde pij(n) é chamada probabilidade de n etapas de uma transição do estado i para

49
estado j. A equação acima pode ser escrita da seguinte forma
k
Pij( n ) = ∑ pir( m ) * prj( n − m )
r =1

que é chamada Igualdade de Markov.

Nessa equação:
n – número de passos;
r – estado intermediário;
i – estado inicial;
j – estado final;
k – número de estados possíveis; e
m – etapas intermediárias.
Da igualdade de Markov, para n = 1, vê-se claramente que Pij(1)=pij. Para determinar
Pij(2), note que se o sistema se encontra agora no estado i, então para o sistema
terminar no estado j dois períodos a partir de agora, temos de ir do estado i para
qualquer estado k e depois ir do estado k para estado j. Portanto, isso permite-nos
escrever
k
Pij( 2 ) = ∑ pir(1) . p rj( 2 −1) = pi1 p1 j + pi 2 p 2 j + ... + pik p kj
r =1

A equação acima pode ser representada esquematicamente como se mostra a seguir:

Pi1 P1j
1
Estado
pi2 P2j
2
:
i pir . prj
j
r
pik :
. pkj

Tempo 0 Tempo 1 Tempo 2

Sob a forma de matriz temos: P2 = P1.P1 = P12

Genericamente: Pn = P1n

50
 p11( n ) p12( n ) ... p1(kn )
(n) (n)
p21 p22 ... p2( nk)
Pn =
... ... ... ...
(n) (n)
p k1 p k2 ... pkk( n )

3.3. Classificação dos Estados numa Cadeia de Markov

¾ Estado recorrente – Se uma vez o processo no estado i ele retorna ao estado
∞
i.
∑p
n =1
ii =1

¾ Estado absorvente - Uma vez o processo no estado absorvente ele nunca sai
deste estado.

pii = 1

¾ Estado transiente - Uma vez o processo no estado i existe uma probabilidade

estritamente positiva que ele nunca retorna ao estado i.
∞

∑p
n =1
ii <1

¾ Acessibilidade - Estado j diz-se acessível a partir do estado i se Pij>0 para

qualquer n>0.
¾ Se o estado j é acessível a partir do estado i e em adição o estado i acessível a
partir de j, então os estados i e j dizem-se comunicáveis.
¾ Se o estado i é comunicável com j e este comunicável com k, então o estado i é
comunicável com k.
¾ Periodicidade - Um estado diz-se periódico com (t>1) se Pii=0 quando n não
é divisível por t, e t é o menor número inteiro com esta propriedade. Se um
estado recorrente não é periódico diz-se a este estado de aperiódico.

¾ Ergódica – Se todos os estados na cadeia são recorrentes, não periódicos, e

comunicáveis entre eles.

51
3.4. Probabilidades do Estado Estacionário
Seja P a matriz de transição para uma cadeia ergódica de k etapas. Então existe um
vector π = [π1 π2 ... πk] tal que
⎡π 1 π 2 ... π k ⎤
⎢π π ... π k ⎥⎥
lim P =⎢ 1
n
⎢: :
2

: ⎥
= lim pij (n) =π
n →∞
n →∞
⎢ ⎥
⎣π 1 π 2 ... π k ⎦

O vector π = [π1 π2 ... πk] é muitas vezes chamado de vector de distribuição do

estado estacionário ou vector de distribuição de equilíbrio, para a cadeia de
Markov.
Repare que para n grande, Pn se aproxima a uma matriz com linhas idênticas. Ou seja,
a probabilidade de encontrar o processo num certo estado, digamos j, depois de
muitas transições tende para um valor πj (chamado probabilidade do estado
estacionário) , que é independente da distribuição das probabilidades iniciais definida
para todos os estados.

3.5. Tempos de Primeira Passagem

Tempo de primeira passagem - Para uma cadeia ergódica, seja µij o número
esperado de transições antes de atingirmos o estado j, dado que agora nos
encontramos no estado i; µij é chamado tempo de primeira passagem a partir do estado
i até ao estado j. Em outras palavras, tempo de primeira passagem é o número de
etapas necessárias para que o processo transite do estado i para o estado j pela
primeira vez..

Tempo de recorrência - É o número de transições necessárias para que o processo

retorne ao estado inicial, ou seja, ele passa do estado i para o estado i. O tempo de
recorrência é o inverso da probabilidade do estado estacionário.
1
µ ii =
πi

52
3.6. Exemplos de Cálculo
Exemplo de cálculo 3.1.
Considere que a probabilidade de chover amanhã é 0.7 se hoje está a chover e a
probabilidade de um dia sem nuvens é de 0.8 se hoje é dia sem nuvens.
Determine a matriz de transição considerando que o processo se comporta como uma
cadeia de Markov.
Determine o estado mais provável do tempo daqui a 3 dias se hoje está a chover.
Resolução
a) Determinação da matriz de transição em um estado:
Estados possíveis:
Estado1: dia com chuva
Estado 2: dia sem nuvens
Portanto k=2
p11 p12
P1 =
p21 p22

p11=0.7 Æ p12=0.3
p22=0.8 Æ p21=0.2
Portanto a matriz de transição será:
0.7 0.3
p1 =
0.2 0.8
Estado mais provável de tempo dentro de 3 dias se hoje está a chover.
k=2
n=3
Æ i=1 e j=2
O estado mais provável dentro de 3 dias é obtido pela matriz de transição em 3 etapas,
p1k(3) se for em termos de matriz, ou então, p1j(3) se usarmos a igualdade de Markov.
Sob a forma de matriz teremos:
0.475 0.525
p n = p3 = p1 . p1 . p1 =
0.35 0.65
Assim, o estado mais provável dentro de 3 dias é dado por p12=0.525, portanto a
probabilidade de chover dentro de 3 dias se hoje está a chover é de não chover.
Chega-se ao mesmo resultado usando a Igualdade de Markov como a seguir se
mostra:

53
 2
P12( 3) = ∑ p1(r1) * pr( 22) = p11(1) * p12( 2) + p12(1) * p22
( 2)

r =1

Mas
p12( 2) = p11(1) * p12(1) + p12(1) * p22
(1)
= 0.7 * 0.3 + 0.3 * 0.8 = 0.450
( 2)
p22 = p21
(1)
* p12(1) + p22
(1) (1)
* p22 = 0.2 * 0.3 + 0.8 * 0.8 = 0.700
Logo
2
P ( 3)
12 = ∑ p1(r1) * pr( 22) = p11(1) * p12( 2) + p12(1) * p22
( 2)
= 0.7 * 0.450 + 0.3 * 0.700 = 0.525
r =1

Exemplo de cálculo 3.2.

Numa fábrica de açúcar estabeleceu-se a política de verificar todas as bombas em
cada paragem. Dessa verificação podem tomar-se 3 decisões:
ƒ Enviar a bomba à oficina de manutenção para a reparação geral
ƒ Fazer reparações menores no próprio local
ƒ Não fazer nada
A partir de dados históricos sabe-se o seguinte:
Se na verificação anterior ao inspeccionar a bomba não se fez nada, na próxima
verificação há uma probabilidade 0.5 de se fazer reparações menores no local, de 0.3
de ser enviada à oficina de manutenção e 0.2 de não fazer nada.
Se na última verificação se fizeram pequenas reparações no local, haverá uma
probabilidade de 0.3 que se faça reparações no local, de 0.2 de envia-la na oficina e
0.5 de não fazer nada.
Se na última verificação se mandou à oficina, há uma probabilidade de 0.2 de não
fazer nada, de 0.3 de fazer pequenas reparações no local e 0.5 de mandar a bomba à
oficina de manutenção.
Considerando que neste processo a sequência de decisões se comporta como uma
cadeia de Markov, determine:
a) A matriz de transição
b) Desenhe o diagrama de transição
c) Se numa verificação não se fez nada, calcule a probabilidade dentro de 3
verificações tenha de ser enviada à oficina de manutenção e que não se faz nada.

Resolução

54
a) Determinação da matriz de transição
Estados possíveis:
Estado 1: Enviar a bomba à oficina de manutenção para a reparação geral.
Estado 2: Fazer reparações menores no local.
Estado 3: Não fazer nada.
Portanto, k=3
Do enunciado podem-se tirar os valores da matriz de transição p1:
0 .5 0 .3 0 .2
P1 = 0.2 0.3 0.5
0.3 0.5 0.2

b) Diagrama de Transição

0.3

0.5
0.2 2
0.5
0.5 0.3
0.2
1 3 0.2
0.3

c) Estado mais provável dentro de 3 revisões:

A expressão “se numa verificação não se fez nada” nos diz que qualquer previsão
deve ser feita a partir do estado 3, portanto, a probabilidade dentro de 3 verificações
tenha de ser enviada à oficina de manutenção é p31(3) e a probabilidade dentro de 3
verificações de não se fazer nada é p33(3).

k=3
n=3

Recorde-se que:
p11( n ) p12( n ) p13( n )
Pn = p21
(n) (n)
p22 (n)
p23
(n) (n) (n)
p31 p32 p33

Portanto

55
 p11(3) p12( 3) p13(3)
P3 = p21
( 3) ( 3)
p22 ( 3)
p23
( 3) ( 3) ( 3)
p31 p32 p33
3
0.5 0.3 0.2 0.34 0.358 0.302
Pn = P3 = P1 .P1 .P1 = 0.2 0.3 0.5 = 0.322 0.358 0.320
0.3 0.5 0.2 0.328 0.370 0.302

Portanto, se numa verificação não se fez nada, a probabilidade de dentro de três

verificações a bomba ser enviada à oficina de manutenção é dada por p31(3)=0.328 e a
probabilidade de não se fazer nada é igual a p33(3)=0.302

Exemplo de cálculo 3.3.

A partir de um estudo preliminar estabeleceu-se que a temperatura dum processo varia
ao longo do tempo de acordo com a figura abaixo. Determine o estado mais provável
na:
a) 20a hora
b) 21a hora
c) 23a hora
d) Determine as probabilidades no estado estacionário
T
70

60

50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Resolução
Estados possíveis:
Estado 1 – 70 oC
Estado 2 – 60 oC
Estado 3 – 50 oC

Do historial verificamos que o processo esteve sete vezes no estado 1, oito vezes no
estado 2 e três vezes no estado 3. Verifica-se também que das sete vezes que esteve

56
no estado 1, o processo transitou quatro vezes para o estado 2, permaneceu três vezes
no mesmo estado e nenhuma vez transitou para o estado 3. Das oito vezes que esteve
no estado 2, o processo permaneceu três vezes no mesmo estado, transitou três vezes
para o estado 1 e transitou para o estado 3 duas vezes. Das três vezes que esteve no
estado 3, o processo transitou uma vez para o estado1, uma vez para o estado 2 e uma
vez permaneceu neste estado.
Portanto, a partir da informação acima podem-se formar as probabilidades de
transição no estado inicial.
p11 = 3/7, p12 = 4/7 e p13 = 0/7
p21 = 3/8, p22 = 3/8 e p23 = 2/8
p31 = 1/3, p32 = 1/3 e p33 = 1/3

Assim, a matriz de transição será dada por:

p11(1) p12(1) p13( n ) 3/ 7 4 / 7 0 / 7 0.429 0.571 0
P1 = p (1)
21 p (1)
22 p (1)
23 = 3 / 8 3 / 8 2 / 8 = 0.375 0.375 0.250
(1) (1) (1)
p 31 p 32 p 33 1/ 3 1/ 3 1/ 3 0.333 0.333 0.333

a) O estado mais provável na 20a hora será dado pela probabilidade p1j(n) = p1j(1) ou
p1k(1)
Reparando para o diagrama verificamos que na 20a hora, o processo dá um passo
(n=1), partindo do estado 1 e portanto, teremos que determinar P1 e depois escolher
a probabilidade de maior valor entre p11(1), p12(1) e p13(1), uma vez que o processo
começa no estado 1.
Mas P1 é a matriz de transição e da primeira linha desta matriz podemos ver que a
probabilidade de maior valor é p12(1) = 0.571. Portanto, o estado mais provável é de
o processo transitar de estado 1 para o estado 2, ou seja, o estado mais provável na
20a hora é de o processo se encontrar a uma temperatura de 60 oC (transição de 70
o
C para 60 oC).

b) O estado mais provável na 21a hora é dado pela probabilidade p1j(n) = p1j(2), ou
p1k(2), uma vez que o processo nessa altura ja terá dado dois passos (n=2).
Portanto, temos que determina a matriz P2=P1.P1= P12 ou então, as

57
 probabilidades p11(2), p12(2) e p13(2), usando a igualdade de Markov e lembrando
que a previsão tem que ser feita a partir do estado 1.

3
P112 = ∑ p1(1r ) . p r(11) = p11 . p11 + p12 . p 21 + p13 . p31 = 0.398
i =1

P12( 2 ) = p11 . p12 + p12 . p 22 + p13 . p32 = 0.459

P13( 2 ) = p11 . p13 + p12 . p 23 + p13 . p33 = 0.143

Portanto, das probabilidades acima calculadas, verifica-se que p12(2) = 0.459 é a maior
probabilidade de transição.
Assim, o estado mais provável na 21a hora é o estado 2, T=60 oC.

c) O estado mais provável na 23a hora, será dado pela probabilidade p1k(4), uma vez
que nessa altura o processo já terá dado quatro passos.
Para obter essa probabilidade será necessário obter a matriz de transição P4.
Mas P4 = P2.P2 = P22 = P14

2
0.429 0.571 0 0.398 0.459 0.143
P2 = P1.P1 = P1 = 0.375 0.375 0.250 = 0.385 0.438 0.177
2

0.333 0.333 0.333 0.379 0.426 0.194

2
0.398 0.459 0.143 0.389 0.445 0.166
P4 = P2 .P2 = 0.385 0.438 0.177 = 0.389 0.444 0.167
0.379 0.426 0.194 0.388 0.426 0.169

Analisando a matriz de transição em quatro etapas, verifica-se que a maior

probabilidade de transição a partir do estado 1 é p12(4) = 0.445. Portanto, o estado mais
provável na 23a hora é o estado 2, T = 60 oC.

d) Determinação das probabilidades para o estado estacionário Лj:

Para este processo temos de calcular pelo menos mais duas matrizes de transição em
relação a última (P4).

58
 p11( 6) p12( 6 ) p13( 6 )
P6 = P2 .P2 .P2 = P2( 3) = p21
( 6) (6)
p22 (6)
p23
( 6) (6) (6)
p31 p32 p33

Determinemos apenas os elementos da diagonal

0.380 0.377
P6 = 0.441 e P8 = 0.438
0.175 0.175

Depois de várias etapas do processo os valores para uma mesma linha e coluna de
duas ou mais matrizes de transição são quase constantes, ou seja, o processo tende a
estacionar.
A comparação é feita usando-se as diagonais, onde para as mesmas, os valores são
constantes.
p11(6) = p11(8) = 0.38
p22(6) = p22(8) = 0.44
p33(6) = p33(8) = 0.18
Portanto, as probabilidades do estado estacionário são:
Л1=0.38
Л2=0.44
Л3=0.18
Tempos de recorrência µij:
µ11 = 1/π1 = 1/0.38 = 2.63
µ22 = 1/π2 = 1/0.44 = 2.27
µ33 = 1/π3 = 1/0.18 = 5.56

Exemplo de cálculo 3.4

Uma indústria de refrigerantes produz dois tipos de produtos, Coca-cola, e Fanta. Se
um cliente comprou Coca-cola, há 90% de chances de na próxima compra ele vir a
comprar Coca-cola. Se um cliente comprou Fanta, há 80% de chances de na próxima
compra ele vir a comprar Fanta.
a) Se actualmente o cliente é comprador de Fanta, qual é a probabilidade de
nas duas próximas vezes ele vir a comprar Coca-cola?

59
 b) Se actualmente o cliente é comprador de Coca-cola, qual é a probabilidade
de nas três próximas vezes ele vir a comprar Coca-cola?
c) Desenhe o respectivo diagrama de transição.
Resolução
Estados do processo
Estado 1 – Comprar Coca-cola
Estado 2 – Comprar Fanta
Matriz de Transição
p11 p12 0.90 0.10
P1 = = P1 =
p21 p22 0.20 0.80

a) A probabilidade de nas duas próximas vezes ele comprar Coca-cola

( 2)
se actualmente é comprador de Fanta é dada por p 21
2
p11 p12 0.83 0.17
P2 = =
p 21 p 22 0.34 0.66
( 2)
Assim, p 21 = 0.34

b) A probabilidade de nas três próximas vezes ele comprar Coca-cola

se actualmente é comprador de Coca-cola é dada por p11( 3)
3
p p12 0.781 0.219
P3 = 11 =
p 21 p 22 0.438 0.562

Assim, p11( 3) = 0.781

c) Diagrama de transição

P12 =0.10

Cola Fant
P11 =0.90 - a P22 =0.80
cola
P21 =0.20

60
3.7. Exercícios Propostos
1. A investigação de um processo estocástico permitiu concluir que a pressão varia
com o tempo de acordo com os seguintes dados observados:
- das 6 horas que esteve à pressão de 220 kPa 3 vezes manteve-se; 2 vezes passou
para 200, e uma vez passou para 180 kPa.
- estando a 200 kPa, 5 vezes manteve-se, 2 vezes passou para 220 e uma vez passou
para 180 kPa.
- estando a 180 kPa, 3 vezes passou para 200, uma vez manteve-se e uma vez passou
para 220 kPa.
a) Determinar os estados possíveis do sistema e a matriz de transição em uma etapa.
b) Desenhe o diagrama de transição
c) Supondo que o processo se encontra a 220 kPa determine a probabilidade de:
- estar a 220 kPa dentro de 2 horas
- estar a 200 kPa dentro de 3 horas
- estar a 180 kPa dentro de 4 horas

2. A variação da temperatura dum processo ao longo do tempo é dada pela figura:

60

50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 tempo, h

a) Determinar os estados possíveis do sistema e a matriz de transição em uma

etapa
b) Desenhe o diagrama de transição.
c) Determine o estado mais provável ao longo da 13a, 14a e 15a horas.

61
3. A investigação de um processo permitiu concluir que a temperatura varia com o
tempo de acordo com o seguinte gráfico:

T
140

120

100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 horas

a) Quais os estados possíveis do sistema?

b) Determine a matriz de transição
c) Determine qual a probabilidade de na 19a hora o sistema estar a 100 e 120
graus

4. Uma companhia possui duas máquinas. Durante o dia, cada máquina que entra em
funciona no princípio do dia tem 1/3 de chance de avariar. Se uma máquina avaria
durante o dia, ela é enviada a oficina para a sua reparação e volta a entrar em
funcionamento dois dias depois da sua avaria. (Assim, se uma máquina avariar
durante o dia 3, ela voltará a entrar em funcionamento no princípio do dia 5.)
Seja o número de máquinas que entram em funcionamento no princípio do dia o
estado do sistema, formule a matriz de transição para esta situação.

5. No problema 1, suponha que uma máquina que avariou num certo dia volte a entrar
em funcionamento três dias mais tarde (por exemplo, uma máquina que avariou no dia
3 venha a entrar em funcionamento no dia 6). Determine a matriz de transição para
esta situação.

6. Cada família moçambicana é classificada como estando a viver numa zona urbana,
rural, ou suburbano. Num dado ano, 15% de todas as famílias urbanas mudaram-se
para uma zona suburbana, e 5% mudaram-se para uma zona rural; também, 6% de
todas as famílias suburbanas mudaram-se para uma zona urbana, e 4% mudaram-se
para uma zona rural; finalmente, 4% de todas as famílias rurais mudaram-se para uma

62
zona urbana, e 6% mudaram-se para uma zona suburbana.
a) Se uma família vive actualmente numa zona urbana, qual é a probabilidade de
dentro de dois anos viver numa zona urbana a partir de agora? Numa zona suburbana?
Numa zona rural?
b) Suponha que actualmente, 40% de todas as famílias vive numa zona urbana, 35%
vive numa zona suburbana, e 25% numa zona rural. Qual é a percentagem das
famílias moçambicanas viverá numa zona urbana dois anos mais tarde a partir de
agora?

7. A cidade A produz 1000 ton de ar poluído por dia, cidade B 100 ton, e cidade C 50
ton. Cada dia, 1/3 do ar poluído da cidade A sopra para cidade C, 1/3 dissipa, e 1/3
permanece na cidade A. Cada dia, 1/3 do ar poluído da cidade B sopra para cidade A,
1/3 permanece na cidade B e 1/3 sopra para cidade C. Cada dia, 1/3 do ar poluído da
cidade C permanece na cidade C, e o resto sopra para cidade B. Num dia típico, qual
das cidades será a mais poluída?

63