1.3. Cadeias de Markov
1.3.1. Cadeias de Markov em tempo discreto
Consideremos
um
processo
estocástico
discreto
{Xn : n = 0, 1, 2, . . . } que assume um número finito ou infinito numerável de estados.
Se Xn = i, dizemos que o processo se encontra no estado i
no instante n .
Admitiremos que existe uma probabilidade fixa pij do processo
transitar para o estado j a partir do estado i, isto é,
pij = P [Xn+1 = j|Xn = i],
n ≥ 0.
1
Definição
1.3.1.1
Um
processo
estocástico
{Xn : n = 0, 1, 2, . . . } é uma cadeia de Markov, ou possui
a propriedade markoviana, se
P [Xn+1 = j|Xn = i, Xn−1 = in−1, . . . , X1 = i1, X0 = i0]
= P [Xn+1 = j|Xn = i] = pij ,
para quaisquer estados i0, i1, . . . , in−1, i, j e n ≥ 0.
A propriedade markoviana pode ser interpretada do seguinte
modo: a probabilidade condicional de qualquer estado futuro,
conhecidos os estados do presente e do passado, é independente
dos estados do passado, ou seja, para predizer o futuro só precisamos de conhecer o presente.
2
As probabilidades condicionais pij , i, j ≥ 0 são chamadas probabilidades de transição (a um passo).
Como consequência imediata temos
pij ≥ 0, , i, j ≥ 0
e
∞
X
pij = 1.
j=0
Por outro lado, as probabilidades de transição não dependem
do instante n, ou seja,
pij = P [Xn+1 = j|Xn = i] = P [X1 = j|X0 = i] ,
n ≥ 1,
pelo que se dizem estacionárias ou homogéneas.
3
As probabilidades de transição são dispostas numa matriz P denominada matriz de transição

p00 p01 p02
p
p
p

P =  10 11 12
p20 p21 p22
...
...
...

...
. . .


. . .
...
As cadeias de Markov são importantes porque conseguem modelar vários fenómenos reais.
Exemplo 1.3.1.1 Suponhamos que a probabilidade de chover
num determinado dia depende apenas das condições meteorológicas do dia anterior, mais especificamente se choveu ou
não no dia anterior. Admitamos que se chover hoje, a probabilidade de chover amanhã é α, enquanto se não chover hoje, a
probabilidade de chover amanhã é β.
4
Se
Xn = estado do tempo no dia n
e consideramos os estados
0 : chove
e
1 : não chove,
então {Xn : n ∈ IN } é uma cadeia de Markov discreta com matriz
de transição
P = 0
1
0
α
β
1
1−α
1−β
5
Exemplo 1.3.1.2 Se admitirmos que num segmento de ADN
(ou ARN) o nucleótido que aparece numa determinada posição
depende apenas do nucleótido na posição anterior, então
estamos perante uma cadeia de Markov com quatro estados: A,
C, G e T (U ).
Exercı́cio 1.3.1.1 Num determinado dia o Evaristo pode sentirse contente, assim assim ou triste. Suponhamos que se o Evaristo está hoje contente, amanhã estará contente, assim assim ou
triste com probabilidade 0.5, 0.4 e 0.1, respectivamente. Caso
hoje se sinta assim assim, amanhã estará contente, assim assim
ou triste com probabilidade 0.3, 0.4 e 0.3, respectivamente; e
se estiver hoje triste, amanhã estará contente, assim assim ou
triste com probabilidade 0.2, 0.3 e 0.5, respectivamente.
Caracterize o processo.
6
Os últimos exemplos são exemplos de cadeias de Markov de
primeira ordem porque a probabilidade de um estado depende
apenas do estado imediatamente anterior.
Exemplo 1.3.1.3 Suponhamos que o estado do tempo num
determinado dia depende apenas das condições meteorológicas
dos dois dias anteriores. Admitamos que se choveu ontem e hoje,
a probabilidade de chover amanhã é 0.7; se não choveu ontem
mas hoje sim, a probabilidade de chover amanhã é 0.5; se choveu
ontem mas hoje não, a probabilidade de chover amanhã é 0.4;
e se não choveu ontem nem hoje, a probabilidade de chover
amanhã é 0.2.
Caracterizemos o processo descrito.
7
Se quisermos uma cadeia com mais “memória”, ou seja, que
a probabilidade de um estado dependa dos n estados imediatamente anteriores, então estamos perante uma cadeia de Markov de ordem n. Estas são transformáveis em cadeias de Markov de primeira ordem.
Exemplo 1.3.1.4 Uma cadeia de Markov de 3a ordem para modelar o ADN é tratado como uma cadeia de Markov de 1a ordem
com 64 = 43 estados. Por exemplo, partindo do terno GCT , os
estados seguintes são
CT A
CT C
CT G
ou
CT T ,
em que as probabilidades de transição correspondentes são, respectivamente,
P (A|GCT )
P (C|GCT )
P (G|GCT )
e
P (T |GCT ) .
8
Existem vários problemas em Biologia que podem ser modelados
por cadeias de Markov. Por exemplo,
• quando os dados e os padrões não são tão claros;
• quando se pretende arranjar um método que seja capaz de
reconhecer um padrão, pelo que há que aprender com os
dados.
Definição 1.3.1.2 Uma cadeia de Markov cujo espaço dos estados é constituı́do pelos inteiros i = 0, ±1, ±2, . . . , é um passeio
aleatório se para algum 0 < p < 1,
pi,i+1 = p
e
pi,i−1 = 1 − p ,
i = 0, ±1, ±2, . . .
9
Exercı́cio 1.3.1.2 Consideremos um jogador que ganha ou
perde um euro em cada aposta com probabilidade p e 1 − p,
respectivamente. Determine a matriz de transição, sabendo que
o jogador inicia o jogo com um euro e que decide parar de jogar
quando ficar sem dinheiro ou quando tiver em seu poder três
euros.
Nota. Os estados 0 e 3 do exercı́cio anterior são denominados
estados absorventes porque uma vez atingidos não será
possı́vel sair deles. Trata-se de um exemplo de um passeio
aleatório com barreiras.
Definição 1.3.1.3 Um estado i diz-se absorvente se pii = 1.
10
Consideremos
(n)
pij
= P [Xm+n = j|Xm = i] ,
i, j ≥ 0
e
n ≥ 1,
(n)
ou seja, pij é a probabilidade condicional do processo transitar
para o estado j no instante m + n, encontrando-se no estado i
no instante m.
Do facto de uma cadeia de Markov ter falta de memória, resulta
que
(n)
pij
= P [Xn = j|X0 = i] ,
i, j ≥ 0
e
n ≥ 1.
11
Prova-se que
(2)
pij = P [Xn+2 = j|Xn = i] = P [X2 = j|X0 = i]
=
∞
X
pik pkj .
k=0
Exercı́cio 1.3.1.3 Considerando o exercı́cio 1.3.1.1, determine
a probabilidade do Evaristo depois de amanhã se encontrar
contente dado que hoje está triste.
12
Generalizando,
∞
X
(m+n)
(m) (n)
pij
= P [Xm+n = j|X0 = i] =
pik pkj , m, n ≥ 0 e i, j ≥ 0.
k=0
As equações anteriores são conhecidas pelas equações de
Chapman-Kolmogorov e permitem determinar as probabilidades de transição a n passos.
Por exemplo,
∞
X
(3)
(2+1)
(2)
pij = pij
=
pik pkj
k=0
ou
∞
X
(2)
(3)
(1+2)
pik pkj .
pij = pij
=
k=0
13
Se P (n) denotar a matriz de transição a n passos, isto é,

(n)
(n)
(n)
p
p
p
01
02
 00
 (n)
(n)
(n)
p10 p11 p12
(n)
P
=
 (n)
(n)
(n)
p20 p21 p22
...
...
...

. . .
. . .


. . .
...

então as equações de Chapman-Kolmogorov permitem concluir
que
P (m+n) = P (m) × P (n),
pelo que
P (n) = P × P (n−1) = P × P × P (n−2) = . . . = P × P × · · · × P = P n.
14
Exercı́cio 1.3.1.4 Suponha que as transições entre nucleótidos
no ADN se fazem segundo uma cadeia de Markov com matriz
de transição
A
C
G
T
A
0.25
0.12
0.16
0.26
C
0.16
0.38
0.34
0.33
G
0.33
0.34
0.38
0.16
T
0.26
0.16
0.12
0.25
Se um segmento de ADN começar com a citosina, qual a probabilidade do quarto nucléotido, a contar do inı́cio, ser a timina?
15
Pode interessar-nos conhecer P (Xn = j), a probabilidade absoluta do processo se encontrar no estado j no instante n, independentemente do estado inicial.
Para o efeito, precisamos da distribuição inicial da cadeia, ou
seja, das probabilidades
P (X0 = i) ,
em que
i = 0, 1, 2, . . . ,
P∞
i=0 P (X0 = i) = 1.
Exemplo 1.3.1.5 Suponhamos que na análise de um segmento
de ADN temos a seguinte distribuição inicial
P (X0 = A) = 0.3,
P (X0 = G) = 0.2,
P (X0 = C) = 0.4,
P (X0 = T ) = 0.1
16
Prova-se que
P (Xn = j) =
∞
X
(n)
P (X0 = i)pij
j = 0, 1, 2, . . .
i=0
Exercı́cio 1.3.1.5 Considerando o exercı́cio 1.3.1.4 e as probabilidades do exemplo anterior, determine a probabilidade de num
segmento de ADN o quarto nucleótido ser a timina.
17
• Classificação dos estados de uma cadeia de Markov
Definição 1.3.1.4 Dizemos que o estado j é acessı́vel a partir
(n)
do estado i se pij > 0 para algum n ≥ 0.
No exercı́cio 1.3.1.4, todos os estados são acessı́veis a partir dos
outros, pois pij > 0.
Exemplo 1.3.1.6 A cadeia de Markov com matriz de transição

1/2 1/2
0



P = 1/2 1/4 1/4
0
1/3 2/3
tem todos os estados acessı́veis a partir dos outros.
18
Neste caso verificamos que

1/2
3/8
1/8



P (2) = 3/8 19/48 11/48 .
1/6 11/36 19/36
Definição 1.3.1.5 Dois estados i e j dizem-se comunicantes
se qualquer um deles é acessı́vel a partir do outro, e escrevemos
i ↔ j.
A relação “comunicação”verifica as propriedades:
i) i ↔ i;
ii) se i ↔ j, então j ↔ i;
iii) se i ↔ j e j ↔ k, então i ↔ k.
19
Os estados comunicantes formam uma classe de equivalência.
Definição 1.3.1.6 Uma cadeia é irredutı́vel se todos os seus
estados são comunicantes.
Exemplo 1.3.1.7 A cadeia de Markov com matriz de transição


1/2 1/2 0


P = 1/2 1/4 1/4
0 1/3 2/3
é irredutı́vel.
20
Exercı́cio 1.3.1.6 Determine os estados comunicantes da cadeia
de Markov com matriz de transição


1/2 1/2 0
0
1/2 1/2
0
0 


P =
.
1/4 1/4 1/4 1/4
0
0
0
1
Seja
fii = P(processo revista o estado i a partir do estado i)
Definição 1.3.1.7 Se fii = 1, o estado i diz-se recorrente. Se
fii < 1, o estado i diz-se transeunte.
Nota. Os estados absorventes são casos particulares de estados
recorrentes.
21
Um estado recorrente será visitado um número infinito de vezes,
enquanto um estado transeunte será visitado um número finito
de vezes.
Seja
Ni = no
de instantes em que o processo se encontra no estado i, partindo deste estado.
Então
Ni _ Geométrica(1 − fii).
Assim sendo,

∞
1
E(Ni) =
=
< ∞
1 − fii
, se fii = 1
.
, se fii < 1
22
Numa cadeia de Markov finita (espaço de estados finito) pelo
menos um estado da cadeia tem que ser recorrrente.
Proposição 1.3.1.1 Se os estados i e j são comunicantes, então:
i) i é recorrrente se e só se j é recorrente;
ii) i é transeunte se e só se j é transeunte.
Da proposição anterior concluimos que uma cadeia de Markov
finita e irredutı́vel só possui estados recorrentes.
23
Exercı́cio 1.3.1.7 Considere as cadeias de Markov com matrizes
de transição


"
a)
#
0 1
1 0
0
1

b) 
0
0

0 1/2 1/2
0 0
0 


1 0
0 
1 0
0
1/4 3/4
0
0

0


1/2 1/2

0
0
0



c)  0
0
1
0 0

 0
0 1/3 2/3 0


1
0
0
0
0
Identifique os estados transeuntes e recorrentes de cada cadeia.
Uma cadeia de Markov com matriz de transição a) tem estados
com perı́odo 2.
Por exemplo, se X0 = 1, então X1 = 0, X2 = 1, X3 = 0, etc.
24
Definição 1.3.1.8 Dizemos que um estado i tem perı́odo d
(n)
(d > 1) se pii = 0 para todo o n 6= d, 2d, 3d, . . . , sendo d o maior
inteiro positivo que verifica a propriedade.
Nota. Afirmar que o estado i tem perı́odo 2 não quer dizer que
(2)
pii = 1.
Um estado que possa ser visitado em dois instantes consecutivos
diz-se aperı́odico (d = 1).
Exemplo 1.3.1.8 Se as transições entre nucleótidos (estados)
no ADN se fizer segundo uma cadeia de Markov com matriz de
transição do exercı́cio 1.3.1.4, então os estados são aperı́odicos.
25
Proposição 1.3.1.2 Se os estados i e j são comunicantes,
então i tem perı́odo d se e só se j tem perı́odo d.
• Probabilidades limites ou estacionárias
Consideremos novamente a matriz de transição que descreve o
estado de espı́rito do Evaristo (exercı́cio 1.3.1.1), ou seja,
P =
0
1
2
0
0.5
0.3
0.2
1
0.4
0.4
0.3
2
0.1
0.3
0.5
26
Então
P (9) =
0
1
2
0
0.3387
0.3387
0.3387
1
0.3710
0.3710
0.3710
2
0.2903
0.2903
0.2903
Tudo indica que existe uma probabilidade limite do Evaristo se
encontrar num estado de espı́rito num futuro distante, independentemente do estado de espı́rito dele hoje.
27
Um resultado importante sobre o comportamento a longo
prazo de uma cadeia de Markov é o
Proposição 1.3.1.3 Numa cadeia de Markov irredutı́vel e
(n)
ergódica existe lim pij e este não depende de i.
n→∞
Nota. Uma cadeia de Markov finita irredutı́vel é ergódica.
Denotando por
(n)
πj = lim pij
n→∞
j ≥ 0,
28
então πj é a única solução não negativa das equações estacionárias
πj =
∞
X
i=0
πipij
com
∞
X
πj = 1
e
j ≥ 0.
j=0
Nota. As probabilidades πj também podem ser interpretadas
como probabilidades estacionárias, isto é, se a distribuição
inicial do estado j for πj = P (X0 = j), então P (Xn = j) = πj ,
n = 1, 2, . . . .
29
As equações estacionárias para o processo que descreve o estado
de espı́rito do Evaristo são


π0




π
1

π2




π
0
= 0.5π0 + 0.3π1 + 0.2π2
= 0.4π0 + 0.4π1 + 0.3π2
= 0.1π0 + 0.3π1 + 0.5π2
+ π 1 + π2 = 1
×
Resolvendo o sistema de equações



π0 = 0.5π0 + 0.3π1 + 0.2π2
π1 = 0.4π0 + 0.4π1 + 0.3π2



π 0 + π 1 + π2 = 1
⇔



0.5π0 − 0.3π1 − 0.2π2 = 0
0.4π0 − 0.6π1 + 0.3π2 = 0
π0 + π1 + π2 = 1



30
obtemos



π0 = 21/62 ≈ 0.3387
π1 = 23/62 ≈ 0.3710



π2 = 9/31 ≈ 0.2903
.
Consequentemente, o Evaristo estará contente em 33,87% dos
dias, assim assim em 37.1% dos dias e triste em 29.03% dos
dias.
31
Exercı́cio 1.3.1.8 Consideremos o exercı́cio 1.3.1.4 em que
A
C
G
T
A
0.25
0.12
0.16
0.26
C
0.16
0.38
0.34
0.33
G
0.33
0.34
0.38
0.16
T
0.26
0.16
0.12
0.25
Determine as probabilidades limite.
• Tempo de primeira passagem e de recorrência
O tempo de primeira passagem entre os estados i e j é o
número de transições que leva o processo a visitar pela primeira
vez o estado j a partir do estado i.
32
Se j = i, o tempo de primeira passagem chama-se tempo de
recorrência do estado i.
Consideremos
fij(n) = P(tempo de 1a passagem entre i e j é n)
(2)
Por exemplo, para calcularmos fij
quema
basta atendermos ao es-
X0
X1
X2
i → 6= j → j
33
As probabilidades de 1a passagem podem ser calculadas recursivamente
(1)
fij
(1)
= pij = pij
(2)
= pij − fij pjj
...
(n)
= pij − fij pjj
fij
fij
(2)
(1)
(n)
(1) (n−1)
(2) (n−2)
− fij pjj
(n−1)
− · · · − fij
pjj
Exercı́cio 1.3.1.9 Considere novamente o exercı́cio 1.3.1.1. Se
o Evaristo estiver hoje contente, qual a probabilidade de ficar
triste pela primeira vez depois de amanhã?
34
O tempo médio de primeira passagem entre i e j, µij , pode ser
calculado resolvendo o sistema
µij = 1 +
X
pik µkj
k6=j
(n)
sem recurso às probabilidades de 1a passagem fij .
Exercı́cio 1.3.1.10 Ao fim de quanto tempo, em média, o Evaristo fica triste quando está contente?
35
Quando j = i, µii é o tempo de recorrência do estado i, e
1
µii =
,
πi
i = 0, 1, 2, . . .
Exercı́cio 1.3.1.11 Determine o tempo médio de recorrência
do estado “triste”para o Evaristo.
36
• Aplicações das cadeias
sequências biológicas
de
Markov
na
análise
de
As cadeias de Markov podem ser usadas para modelar a dependência da posição de um nucleótido (amino ácido) relativamente ao do seu vizinho da esquerda.
Por exemplo,
sequência
qual a probabilidade de observarmos a
ATACGGC
?
37
Neste caso,
P (AT ACGGC) = P (A)pAT × pT A × pAC × pCG × pGG × pGC .
Podemos pensar numa cadeia de Markov como um processo
de geração de sequências de qualquer comprimento finito L
(L ≥ 2), x1x2 . . . xL, em que xi ∈ A.
Assim sendo,
P (x1x2 . . . xL) = P (x1)px1x2 px2x3 · · · px
L−1 xL
38
Nota. As probabilidades iniciais P (xi) (πi) e de transição px x
i j
(pij ) têm que ser conhecidas a priori.
Consideremos, por exemplo, genes de codificação
proteı́nas em organismos procariotas (e.g., em bactérias).
de
Um gene procariota consiste numa região de codificação com
um codão de inicialização (usualmente ATG, mas às vezes
CTG ou TTG) e um codão de finalização (TAA, TAG ou
TGA).
As cadeias de Markov permitem modelar genes procariotas.
(sequências open reading frames, ORF)
39
Nota. Na análise de sequências biológicas é usual considerar
dois outros estados, o estado inicial B e o estado final E
(estado absorvente) que traduzem, por exemplo, o inı́cio e
o fim de um gene, respectivamente. Estes estados também
podem ser representados por 0.
Para gerarmos sequências de letras com uma cadeia de Markov
as probabilidades iniciais e de transição devem ser seleccionadas
de uma certa forma. Para o efeito, podemos usar dados reais
(training data).
Também há que admitir a priori um diagrama de transição
entre os estados.
40
Diagrama de transição entre os estados
41
Suponhamos que para um conjunto de sequências de ADN n genes procariotas foram experimentalmente identificados. Então
Nab
pab = P
c∈A Nac
em que
Nab = no de vezes que b precede a nos dados.
Nota. Se o nucleótido a não figurar nos dados, então estes
são insuficientes para estimar pab. Podemos usar neste caso
pseudocontagens.
Quanto às probabilidades iniciais p0a (πa), a ∈ A,
p0a
no de vezes que a inicia a sequência
=
.
n
42
Exemplo 1.3.1.9 Seja n = 4 e suponhamos que são dadas
sequências que se conhecem serem de genes procariotas:
s1 : ATGCTATTGATTTAA
s2 : GTGAAAGACTTCTAA
s3 : ATGCCCGATGAACGCTAG
s4 : ATGAAGCATGATTAA
Ignorando os codões de inicialização e de finalização (a azul), ou
seja, considerando apenas os ORF correspondentes:
1
p0A = ,
2
1
p0C = ,
2
p0G = 0 ,
p0T = 0.
43
2
2
5
4 , p
pAA = 13
AC = 13 , pAG = 13 , pAT = 13 , pA0 = 0
1,
pCA = 9
pCC = 2
9,
2,
pCG = 9
pCT = 2
9,
2
pC0 = 9
5,
pGA = 7
pGC = 2
7,
pGG = 0 ,
pGT = 0 ,
pG0 = 0
1
3
3
2
1 , p
pT A = 10
T C = 10 , pT G = 10 , pT T = 10 , pT 0 = 10
Consequentemente, se tivéssemos admitido o diagrama de
transição atrás, este teria que ser corrigido em função dos dados.
44
Exemplo 1.3.1.10 Se quisermos estimar as probabilidade P (A),
P (C), P (G) e P (T ) a partir das sequências
ACCGCGCTTA
GCTTAGTGAC
TAGCCGTTAC
as estimativas de máxima verosimilhança são
P (A) =
6
9
7
8
= 0.2 , P (C) =
= 0.3 , P (G) =
= 0.23 , P (T ) =
.
30
30
30
30
45
Suponhamos agora que desejamos usar o modelo obtido para
determinar se uma sequência não identificada de ADN é a
sequência de um gene procariota.
• Procura-se um codão de inicialização e o primeiro codão de
finalização que o segue na esperança de que o segmento
obtido seja um gene.
• Pode acontecer que dois codões de inicialização sejam encontrados sem um codão de finalização entre eles (50% dos
casos). Qual o ORF que corresponde ao gene?
46
A sequência não identificada de ADN s = x1x2 . . . xL é tratada
como se fosse gerada por uma cadeia de Markov, pelo que
P (s) = P (x1x2 . . . xL) = P0x px1x2 px2x3 · · · pxL−1xL px
1
L0
Se P (s) for grande comparativamente a um valor estipulado,
então existe uma boa chance da sequência provir de um gene
procariota (desde que os dados sejam representativos).
Nota. Dada a simplicidade do modelo podemos obter negativos falsos (baixas probabilidades) ou positivos falsos (elevadas
probabilidades).
47
Exemplo 1.3.1.11 Se considerarmos a sequência não identificada de ADN
ATGCTAGTGATTGATTAA
então existem dois possı́veis genes procariotas
s1 : 0CTAGTGATTGAT0
s2 : 0ATTGAT0
Considerando os dados do exemplo 1.3.1.9, vem
P (s1) = 0 ,
(pGT = 0)
e
P (s2) = p0A pAT pT T pT G pGA pAT pT 0
1
5
3
3
5
5
2
2250
= ×
×
×
× ×
×
=
≈ 0.00095
2 13 10 10 7 13 10
2366000
48
A análise de genes para a codificação de proteı́nas em organismos eucariotas é mais complicada porque as regiões codificantes
chamadas exons são interrompidas por regiões não codificantes
denominadas introns. Neste caso, a pesquisa de genes pode ser
feita recorrendo a cadeias de Markov escondidas.
49