Cadeia de Markov a Tempo Discreto

Prévia do material em texto

1
Cadeias de Markov em Tempo Discreto
Mauro C. M. Campos
SUMA´RIO
I Processos estoca´sticos em tempo discreto 1
II Cadeias de Markov e a propriedade de Markov 2
III Func¸a˜o de transic¸a˜o e distribuic¸a˜o inicial 2
IV Func¸a˜o de transic¸a˜o em m-passos e distribuic¸o˜es marginais 3
V Classificac¸a˜o dos estados em transientes e recorrentes 3
VI Estrutura de classes e a decomposic¸a˜o do espac¸o de estados 5
VII Distribuic¸o˜es estaciona´rias 7
VIII Nu´mero me´dio de visitas a um estado 7
IX Subclassificac¸a˜o dos estados recorrentes em nulos e positivos 8
X Condic¸a˜o de existeˆncia de distribuic¸o˜es estaciona´rias e condic¸a˜o de unicidade 8
XI Convergeˆncia para a distribuic¸a˜o estaciona´ria 8
XII Cadeias de Markov finitas: resumo dos resultados 8
XIII I´ndice de notac¸o˜es 9
Refereˆncias 9
OBS.: Notas de aula. Em 6 de junho de 2010.
I. PROCESSOS ESTOCA´STICOS EM TEMPO DISCRETO
Definic¸a˜o 1 (Processo estoca´stico em tempo discreto). Seja ϕ um conjunto. Um processo estoca´stico em tempo discreto em
ϕ e´ uma sequeˆncia (Xn)n≥0 de varia´veis aleato´rias (va.a’s) tal que Xn assume valores em ϕ para todo n ≥ 0. O conjunto ϕ
e´ chamado de espac¸o de estados e cada um de seus elementos e´ chamado de estado.
Comenta´rio 1. Probabilidades que ocorrem na teoria de processos estoca´sticos em tempo discreto dependem das probabilidades
P (i0, i1, . . . , in) = Pr(X0 = i0, X1 = i1, . . . , Xn = in) (1)
para todo n ≥ 0 e i0, i1, . . . , in ∈ ϕ. E´ possı´vel calcular (1) conhecendo:
• a distribuic¸a˜o de X0, P (i0) = Pr(X0 = i0)
• e as probabilidades de transic¸a˜o,
– P (i1|i0) = Pr(X1 = i1|X0 = i0)
– P (i2|i0, i1) = Pr(X2 = i2|X0 = i0, X1 = i1)
–
...
– P (in|i0, . . . , in−1) = Pr(Xn = in|X0 = i0, . . . , Xn−1 = in−1).
Departamento de Estatı´stica, Universidade Federal do Espı´rito Santo UFES. Av. Fernando Ferrari 514, Goiabeiras, CEP 29075-910, Vito´ria ES.
2
Isso porque
P (i0, i1, . . . , in) = P (i0)P (i1|i0)P (i2|i0, i1) · . . . · P (in|i0, . . . , in−1). (2)
Definic¸a˜o 2 (Me´dia, variaˆncia e correlac¸a˜o). Descrevemos o valor me´dio, a variabilidade e a estrutura de correlac¸a˜o de um
processo estoca´stico em tempo discreto atrave´s das seguintes func¸o˜es:
1) A func¸a˜o me´dia do processo e´ definida por
µn := E(Xn) n = 0, 1, 2, . . . . (3)
2) A func¸a˜o variaˆncia do processo e´ definida por
σ2n := Var(Xn) = E(X
2
n)− µ2n n = 0, 1, 2, . . . . (4)
3) A func¸a˜o de autocovariaˆncia do processo e´ definida por
γm,n := Cov(Xm, Xn) = E(XmXn)− µmµn m,n = 0, 1, 2, . . . . (5)
4) A func¸a˜o de autocorrelac¸a˜o do processo e´ definida por
%m,n :=
γm,n√
σ2mσ
2
n
m,n = 0, 1, 2, . . . . (6)
Comenta´rio 2. Observe que:
• σ2n = γn,n para todo n
• γm,n = γn,m para todo par m,n
• %m,n = %n,m para todo par m,n.
II. CADEIAS DE MARKOV E A PROPRIEDADE DE MARKOV
Nessa sec¸a˜o, ϕ representa um conjunto finito ou enumera´vel.
Definic¸a˜o 3 (Cadeia de Markov). Nessa sec¸a˜o estudaremos processos em tempo discreto com a propriedade que dado o estado
presente, os estados passados na˜o influenciam o estado futuro. Essa propriedade e´ conhecida como propriedade de Markov e
um processo satisfazendo tal regra e´ chamado de cadeia de Markov (CM). Formalmente, um processo estoca´stico em tempo
discreto (Xn)n≥0 com espac¸o de estados ϕ e´ uma CM (em tempo discreto) em ϕ se
Pr(Xn+1 = j|X0 = i0, . . . , Xn−1 = in−1, Xn = i) = Pr(Xn+1 = j|Xn = i) (7)
para todo n ≥ 0 e i0, . . . , in−1, i, j ∈ ϕ. A equac¸a˜o (7) define precisamente a propriedade de Markov.
Definic¸a˜o 4 (CM finita). (Xn)n≥0 e´ uma CM finita se o espac¸o de estados ϕ e´ finito.
Definic¸a˜o 5 (CM homogeˆnea). (Xn)n≥0 e´ uma CM homogeˆnea se
Pr(Xn+1 = j|Xn = i) = Pr(X1 = j|X0 = i) (8)
para todo n > 0 e i, j ∈ ϕ. Daqui pra frente qualquer discussa˜o sobre CM’s, fica subentendido que as cadeias sa˜o homogeˆneas.
III. FUNC¸A˜O DE TRANSIC¸A˜O E DISTRIBUIC¸A˜O INICIAL
Seja (Xn)n≥0 uma CM em ϕ (ou seja, uma CM com espac¸o de estados ϕ).
Definic¸a˜o 6 (Func¸a˜o de transic¸a˜o). A func¸a˜o P : ϕ× ϕ→ [0, 1] definida por
Pij = Pr(X1 = j|X0 = i) (9)
representa a func¸a˜o de transic¸a˜o da cadeia. Segue imediatamente da definic¸a˜o que
1) Pij ≥ 0 para todo i, j ∈ ϕ
2)
∑
j∈ϕ Pij = 1 para todo i ∈ ϕ.
Ale´m disso, segue das equac¸o˜es (7) e (8) que
Pij = Pr(Xn+1 = j|X0 = i0, . . . , Xn−1 = in−1, Xn = i). (10)
Portanto, se a cadeia esta´ no estado i no tempo n, enta˜o na˜o importa como ela chegou em i, a cadeia possui probabilidade
Pij de visitar o estado j no tempo n+ 1.
Definic¸a˜o 7 (Distribuic¸a˜o inicial). A func¸a˜o pi(0) : ϕ→ [0, 1] definida por
pi
(0)
i = Pr(X0 = i) (11)
3
representa a distribuic¸a˜o inicial da cadeia. Novamente, segue da definic¸a˜o que
1) pi(0)i ≥ 0 para todo i ∈ ϕ
2)
∑
i∈ϕ pi
(0)
i = 1.
Teorema 1 (Distribuic¸o˜es finito-dimensionais de uma CM). Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P e
distribuic¸a˜o inicial pi(0). Enta˜o
Pr(X0 = i0, . . . , Xn = in) = pi
(0)
i0
Pi0,i1Pi1,i2 · . . . · Pin−1,in (12)
para todo n > 0 e i0, . . . , in ∈ ϕ.
IV. FUNC¸A˜O DE TRANSIC¸A˜O EM m-PASSOS E DISTRIBUIC¸O˜ES MARGINAIS
Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P e distribuic¸a˜o inicial pi(0), e seja m um inteiro na˜o-negativo.
Definic¸a˜o 8 (Func¸a˜o de transic¸a˜o em m-passos). A func¸a˜o P (m) : ϕ× ϕ→ [0, 1] definida por
P
(m)
ij = Pr(Xn+m = j|Xn = i) h.h.= Pr(Xm = j|X0 = i) (13)
representa a func¸a˜o de transic¸a˜o em m-passos da cadeia. Em particular
P
(0)
ij =
{
0 se i 6= j
1 se i = j, (14)
e P (1) = P .
Teorema 2 (Equac¸o˜es de Chapman-Kolmogorov). Considere n,m ≥ 0 e i, j ∈ ϕ. Enta˜o
P
(n+m)
ij =
∑
k∈ϕ
P
(n)
ik P
(m)
kj . (15)
Ale´m disso, segue da equac¸a˜o (15) que
P
(m)
ij =
∑
k∈ϕ
PikP
(m−1)
kj
=
∑
k1∈ϕ
· · ·
∑
km−1∈ϕ
Pi,k1Pk1,k2 · . . . · Pkm−1,j . (16)
Teorema 3 (Distribuic¸o˜es marginais). Considere n > 0 e j ∈ ϕ. Enta˜o
pi
(n)
j = Pr(Xn = j) =
∑
i∈ϕ
pi
(0)
i P
(n)
ij . (17)
De forma alternativa, temos que
pi
(n)
j = Pr(Xn = j) =
∑
i∈ϕ
pi
(n−1)
i Pij . (18)
Comenta´rio 3. E´ importante ressaltar que e´ possı´vel pensar em pi(n) e P (n), n ≥ 0, como vetores e matrizes em ϕ e ϕ × ϕ
respectivamente. Nesse caso, podemos ver que P (n) = Pn = P · · ·P (n vezes). Ale´m disso, na notac¸a˜o matricial, as equac¸o˜es
(15), (17) e (18) podem ser escritas como:
• P (n+m) = Pn+m = PnPm = P (n)P (m), onde n,m ≥ 0
• pi(n) = pi(0)Pn, onde n ≥ 0
• pi(n) = pi(n−1)P , onde n > 0.
A equac¸a˜o pi(n) = pi(n−1)P permite interpretar a matriz P como um operador linear que atua no espac¸o das distribuic¸o˜es de
probabilidade em ϕ, atualizando a distribuic¸a˜o marginal da cadeia a cada passo n > 0.
V. CLASSIFICAC¸A˜O DOS ESTADOS EM TRANSIENTES E RECORRENTES
Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P e sejam i e j estados na˜o necessariamente distintos.
Definic¸a˜o 9. Seja Tj uma va.a. definida por
Tj = min{n > 0;Xn = j} (19)
se Xn = j para algum n > 0 e por Tj = ∞ se Xn 6= j para todo n > 0. Em palavras, Tj representa o tempo da primeira
visita ao estado j. Em particular, se o estado inicial da cadeia e´ j, enta˜o Tj representa o tempo do primeiro retorno a j. Ale´m
disso, seja
ρij = Pr(Tj <∞|X0 = i) (20)
4
a probabilidade da cadeia visitar o estado j em algum tempo finito, dado que ela comec¸ou no estado i. Em particular, ρjj
denota a probabilidade da cadeia retornar a j em algum tempo finito, dado que ela comec¸ou no estado j.
Definic¸a˜o 10 (I Crite´rio para classificac¸a˜o dos estados). Um estado j e´:
1) transiente se ρjj < 1
2) recorrente se ρjj = 1.
Comenta´rio 4. Vejamos algumas observac¸o˜es:
• Se j e´ um estado transiente, enta˜o uma cadeia comec¸ando em j tem uma probabilidade positiva de nunca mais retornar
a j. De fato
Pr(Tj =∞|X0 = j) = 1− Pr(Tj <∞|X0 = j) = 1− ρjj> 0. (21)
• Se j e´ um estado recorrente, enta˜o uma cadeia comec¸ando em j retorna a j com probabilidade 1.
• Um estado j e´ absorvente se Pjj = 1. Usando a equac¸a˜o (15), e´ simples ver que Pjj(n) = 1 para todo n ≥ 0. Ale´m
disso, e´ simples verificar que todo estado absorvente e´ recorrente. Basta ver que
1 = Pjj = Pr(Tj = 1|X0 = j) ≤ Pr(Tj <∞|X0 = j) = ρjj . (22)
Portanto ρjj = 1 e o estado absorvente j e´ recorrente.
Definic¸a˜o 11. Seja Nj uma va.a. definida por
Nj =
∑
n≥1
I(Xn = j) (23)
onde I(Xn = j) denota o indicador do evento [Xn = j]. Em palavras, Nj representa o nu´mero de visitas ao estado j. Na˜o e´
difı´cil mostrar que a distribuic¸a˜o de Nj dado [X0 = i] e´
Pr(Nj = m|X0 = i) =
{
1− ρij se m = 0
ρijρ
m−1
jj (1− ρjj) se m > 0. (24)
Ale´m disso, temos que
E(Nj |X0 = i) =
∑
n≥1
P
(n)
ij = Gij . (25)
O pro´ximo teorema descreve as diferenc¸as fundamentais entre um estado transiente e um estado recorrente.
Teorema 4. Seja j um estado transiente. Enta˜o
Pr(Nj <∞|X0 = i) = 1 (26)
e
E(Nj |X0 = i) = Gij = ρij1− ρjj <∞ (27)
para todo i ∈ ϕ. Seja j um estado recorrente. Enta˜o
Pr(Nj =∞|X0 = i) = ρij (28)
e
E(Nj |X0 = i) = Gij =
{
0 se ρij = 0
∞ se ρij > 0 (29)
para todo i ∈ ϕ. Em particular, quando i = j, segue que Pr(Nj =∞|X0 = j) = 1 e E(Nj |X0 = j) = Gjj =∞.
Comenta´rio 5. Se j e´ um estado transiente, enta˜o a cadeia faz somente um nu´mero finito de visitas a j independente do estado
inicial. Ale´m disso, o nu´mero me´dio de visitas a j e´ finito. Suponha agora que j e´ recorrente. Nesse caso, se a cadeia comec¸ou
em j, ela retorna a j infinitas vezes. Por outro lado, se a cadeia comec¸ou em algum outro estado i, pode ser impossı´vel que
ocorra uma visita a j. Entretanto, se a cadeia alcanc¸a j pelo menos uma vez, enta˜o a cadeia visita j infinitas vezes.
Corola´rio 1 (II Crite´rio para classificac¸a˜o dos estados). Um estado j e´ transiente se, e somente se,
Gjj = E(Nj |X0 = j) =
∑
n≥1
P
(n)
jj <∞. (30)
Um estado j e´ recorrente se, e somente se,
Gjj = E(Nj |X0 = j) =
∑
n≥1
P
(n)
jj =∞. (31)
Corola´rio 2. Se j e´ um estado transiente, enta˜o limn→∞ P
(n)
ij = 0 para todo i ∈ ϕ.
5
PROVA. Basta ver que Gij =
∑
n≥1 P
(n)
ij <∞ �
Corola´rio 3. Toda CM finita possui pelo menos um estado recorrente.
PROVA. Suponha que todos os estados em ϕ sa˜o transientes. Enta˜o
0 =
∑
j∈ϕ
lim
n→∞P
(n)
ij = limn→∞
∑
j∈ϕ
P
(n)
ij = limn→∞ 1 = 1, (32)
o que e´ uma contradic¸a˜o. Portanto existe pelo menos um estado em ϕ que e´ recorrente �
VI. ESTRUTURA DE CLASSES E A DECOMPOSIC¸A˜O DO ESPAC¸O DE ESTADOS
Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P .
Definic¸a˜o 12 (Relac¸a˜o→). Dizemos que um estado i alcanc¸a um estado j se P (n)ij > 0 para algum inteiro n ≥ 0. Para denotar
esse fato, usamos o sı´mbolo i→ j. A relac¸a˜o → e´ reflexiva e transitiva, ou seja:
1) i→ i
2) se i→ j e j → k, enta˜o i→ k.
PROVA. De fato, i → i pois P (0)ii = 1 > 0. Ale´m disso, se i → j e j → k, enta˜o existem inteiros n,m ≥ 0 tais que
P
(n)
ij > 0 e P
(m)
jk > 0. Assim
P
(n+m)
ik =
∑
l∈ϕ
P
(n)
il P
(m)
lk ≥ P (n)ij P (m)jk > 0, (33)
portanto i→ k �
Definic¸a˜o 13 (Relac¸a˜o ↔). Dizemos que i se comunica com j se i → j e j → i. Para denotar a relac¸a˜o de comunicac¸a˜o
entre i e j, usamos o sı´mbolo i↔ j. A relac¸a˜o ↔ e´ reflexiva, simetrica e transitiva, ou seja:
1) i↔ i
2) se i↔ j, enta˜o j ↔ i
3) se i↔ j e j ↔ k, enta˜o i↔ k.
PROVA. As duas primeiras sa˜o imediatas da definic¸a˜o e a terceira segue do fato que a relac¸a˜o → e´ transitiva �
Definic¸a˜o 14. O conjunto
Ci = {k ∈ ϕ; i↔ k} (34)
representa a classe de estados que se comunicam com o estado i.
Teorema 5 (A relac¸a˜o ↔ induz uma partic¸a˜o em ϕ). Sejam i, j ∈ ϕ e sejam Ci e Cj suas respectivas classes.
1) Ci = Cj se, e somente se, i↔ j;
2) Se Ci 6= Cj , enta˜o Ci ∩ Cj = ∅.
PROVA. 1; ⇒) Suponha que
Ci = {k ∈ ϕ; i↔ k} = {l ∈ ϕ; j ↔ l} = Cj . (35)
Como i ∈ Ci = Cj , segue i↔ j.
1; ⇐) Agora, suponha que i ↔ j e seja k um elemento arbitra´rio em Ci. Como k ↔ i e i ↔ j, segue que k ↔ j, logo
Ci ⊆ Cj . Por simetria, temos que j ↔ i e de modo ana´lago chegamos na inclusa˜o Cj ⊆ Ci. Portanto Ci = Cj .
2) Suponha que Ci 6= Cj e que existe pelo menos um estado k em Ci∩Cj . Assim k ↔ i e k ↔ j o que implica que i↔ j.
Mas pelo que ja´ foi provado, isso significa que Ci = Cj o que contraria a hipo´tese inicial. Portanto Ci ∩ Cj = ∅ �
Comenta´rio 6. O teorema 5 afirma que dois estados possuem a mesma classe se, e somente se, eles se comunicam. Ale´m
disso, duas classes ou sa˜o ideˆnticas ou sa˜o disjuntas. Em outras palavras, a relac¸a˜o de comunicac¸a˜o ↔ induz uma partic¸a˜o em
ϕ em classes de estados que se comunicam entre si.
Definic¸a˜o 15 (CM irredutı´vel). Dizemos que uma CM e´ irredutı´vel se todos os estados em ϕ se comunicam entre si, ou seja,
todos os estados pertencem a uma u´nica classe de comunicac¸a˜o que e´ exatamente ϕ.
Comenta´rio 7. Daqui pra frente a palavra “classe” significa “classe de estados que se comunicam entre si”. O pro´ximo teorema
afirma que todos os estados que esta˜o numa mesma classe ou sa˜o todos recorrentes ou sa˜o todos transientes. Uma classe de
estados recorrentes sera´ chamada de classe recorrente. Nomeclatura ana´loga vale para uma classe de estados transientes.
Teorema 6. Seja C uma classe. Todos os estados em C ou sa˜o recorrentes ou sa˜o transientes.
6
PROVA. Considere um par arbitra´rio i, j ∈ C e assuma que j e´ transiente. Por definic¸a˜o existem inteiros n,m > 0 tais que
P
(n)
ij > 0 e P
(m)
ji > 0. (36)
Para qualquer inteiro q ≥ 1, temos que
P
(m+q+n)
jj ≥ P (m)ji P (q)ii P (n)ij . (37)
Assim ∑
q≥1
P
(q)
ii ≤
1
P
(m)
ji P
(n)
ij
∑
q≥1
P
(m+q+n)
jj <∞. (38)
Portanto i tambe´m e´ transiente �
Definic¸a˜o 16 (Classe fechada). Seja D um conjunto na˜o-vazio de estados. Dizemos que D e´ fechado se nenhum estado dentro
de D alcanc¸a um estado fora de D. Formalmente, D e´ fechado se P (m)ij = 0 para i ∈ D, j 6∈ D e todo m ≥ 1. Quando um
conjunto na˜o-vazio de estados na˜o e´ fechado, dizemos que ele e´ aberto.
Comenta´rio 8. Agora estamos em posic¸a˜o de estabelecer a relac¸a˜o entre classe recorrente e classe fechada. De fato, o pro´ximo
teorema afirma que se uma classe na˜o e´ fechada, enta˜o ela na˜o pode ser recorrente. Portanto, ser fechada e´ uma condic¸a˜o
necessa´ria (pore´m, na˜o suficiente) para a classe ser recorrente.
Teorema 7. Toda classe recorrente e´ fechada. (“Se uma classe e´ recorrente, enta˜o e´ fechada”; “Se uma classe e´ aberta, enta˜o
e´ transiente”.)
PROVA. Seja C uma classe que na˜o e´ fechada. Enta˜o existem i ∈ C e j 6∈ C tais que
P
(m)
ij = Pr(Xm = j|X0 = i) > 0 (39)
para algum m ≥ 1. Como j 6→ i (pois j 6∈ C) segue que
0 < Pr(Xm = j|X0 = i) ≤ Pr(Ni <∞|X0 = i). (40)
Logo Pr(Ni =∞|X0 = i) < 1 e isto implica que i na˜o pode ser um estado recorrente. Portanto C na˜o pode ser uma classe
recorrente �
Teorema 8 (Decomposic¸a˜o de ϕ em classes). O espac¸o de estados ϕ pode ser particionado unicamente como
ϕ = T ∪ C ′ ∪ C ′′ ∪ · · · (41)
onde T e´ o conjunto dos estados transientes e os C’s sa˜o classes recorrentes (fechadas) e disjuntas.
PROVA. Segue das proposic¸o˜es 5, 6 e 7 �
Comenta´rio 9. E´ importante observar que classe fechada na˜o significa classe recorrente, pois classes fechadas infinitas podem
ser transientes. Entretanto, mostraremos agora que para uma classe finita, e´ suficiente ser fechada para ser recorrente. Em
outras palavras, ser uma classe finita e fechada e´ equivalente a ser uma classe recorrente. Esse resultado e´ u´til para cadeias
com espac¸o de estados finito, pois nesse caso e´ bem mais simples verificar se uma classe e´ ou na˜o e´ fechada.
Teorema 9. Toda classe fechada e finita e´ recorrente.
PROVA. De fato, seja C uma classe fechada e finita e suponhaque C e´ transiente. Sejam i e j estados em C. Temos que
lim
n→∞P
(n)
ij = 0. (42)
Assim
0 =
∑
j∈C
lim
n→∞P
(n)
ij = limn→∞
∑
j∈C
P
(n)
ij = limn→∞Pr(Xn ∈ C|X0 = x) = limn→∞ 1 = 1. (43)
Mas isso e´ uma contradic¸a˜o, portanto C e´ recorrente �
Comenta´rio 10. No caso de uma classe finita, podemos reunir as afirmac¸o˜es dos teoremas 7 e 9 tal como segue.
Teorema 10. Uma classe finita e´ recorrente se, e somente se, e´ fechada. (“Se uma classe finita e´ recorrente, enta˜o e´ fechada”
e “se uma classe finita e´ fechada, enta˜o e´ recorrente”.)
Corola´rio 4. Toda CM finita e irredutı´vel e´ recorrente.
7
VII. DISTRIBUIC¸O˜ES ESTACIONA´RIAS
Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P .
Definic¸a˜o 17 (Distribuic¸a˜o estaciona´ria). Uma func¸a˜o pi : ϕ → [0, 1], ϕ 3 i 7→ pii ≥ 0, e´ uma distribuic¸a˜o estaciona´ria de
(Xn)n≥0 se
1)
∑
i∈ϕ pii = 1
2) pij =
∑
i∈ϕ piiPij para todo j ∈ ϕ. Na notac¸a˜o matricial pi = piP .
Teorema 11. Propriedades de distribuic¸o˜es estaciona´rias:
1) Se pi e´ uma distribuic¸a˜o estaciona´ria de uma CM com func¸a˜o de transic¸a˜o P , enta˜o
pij =
∑
i∈ϕ
piiP
(n)
ij (44)
para todo j ∈ ϕ e n ≥ 0. Na notac¸a˜o matricial pi = piP (n) = piPn para todo n ≥ 0.
2) A distribuic¸a˜o de Xn e´ independente de n se, e somente se, a distribuic¸a˜o inicial e´ uma distribuic¸a˜o estaciona´ria.
3) Se pi e´ uma distribuic¸a˜o estaciona´ria de uma CM com func¸a˜o de transic¸a˜o P e se
lim
n→∞P
(n)
ij = pij (45)
para todo j ∈ ϕ, enta˜o
lim
n→∞pi
(n)
j = limn→∞Pr(Xn = j) = pij . (46)
Comenta´rio 11. A parte 3) do teorema 11 segue do teorema da convergeˆncia limitada, apresentado a seguir.
Teorema 12 (Teorema da convergeˆncia limitada). Sejam (ai : i ∈ ϕ) nu´meros na˜o negativos somando 1 e sejam (b(n)i : i ∈
ϕ, n ≥ 1) nu´meros tais que
1) |b(n)i | ≤ 1 para todo i ∈ ϕ e n ≥ 1 e
2) limn→∞ b
(n)
i = bi para todo i ∈ ϕ.
Enta˜o
lim
n→∞
∑
i∈ϕ
aib
(n)
i =
∑
i∈ϕ
aibi. (47)
VIII. NU´MERO ME´DIO DE VISITAS A UM ESTADO
Seja (Xn)n≥0 uma CM em ϕ com func¸a˜o de transic¸a˜o P .
Definic¸a˜o 18. Seja
Nj(n) =
n∑
m=1
I(Xm = j) (48)
o nu´mero de visitas ao estado j durante os tempos 1, . . . , n. Ale´m disso, seja
Gij(n) = E(Nj(n)|X0 = i) =
n∑
m=1
P
(m)
ij (49)
o nu´mero me´dio de visitas ao estado j durante os tempos 1, . . . , n, saindo do estado i. Observe que
Nj = lim
n→∞Nj(n) Gij = limn→∞Gij(n). (50)
Teorema 13. Seja j um estado transiente. Enta˜o
lim
n→∞
Nj(n)
n
= 0 com probabilidade 1 (51)
e
lim
n→∞
Gij(n)
n
= 0 para todo i ∈ ϕ. (52)
Definic¸a˜o 19. Seja j um estado em ϕ. Defina
mj = E(Tj |X0 = j) (53)
se este tempo me´dio de retorno e´ finito e mj =∞ caso contra´rio.
Teorema 14. Seja j um estado recorrente. Enta˜o
lim
n→∞
Nj(n)
n
=
I(Tj <∞)
mj
com probabilidade 1 (54)
8
e
lim
n→∞
Gij(n)
n
=
ρij
mj
para todo i ∈ ϕ. (55)
Corola´rio 5. Seja C uma classe recorrente (fechada). Se Pr(X0 ∈ C) = 1, enta˜o
lim
n→∞
Nj(n)
n
=
1
mj
com probabilidade 1 (56)
para todo j ∈ C. Ale´m disso,
lim
n→∞
Gij(n)
n
=
1
mj
para todo i, j ∈ C. (57)
IX. SUBCLASSIFICAC¸A˜O DOS ESTADOS RECORRENTES EM NULOS E POSITIVOS
Definic¸a˜o 20. Seja j um estado recorrente. Dizemos que j e´ recorrente nulo se mj = ∞. Caso contra´rio (ou seja, se
mj := E(Tj |X0 = j) <∞), dizemos j e´ recorrente positivo.
Teorema 15. Seja j um estado recorrente nulo. Enta˜o
lim
n→∞
Nj(n)
n
= 0 com probabilidade 1 (58)
e
lim
n→∞
Gij(n)
n
= 0 para todo i ∈ ϕ. (59)
Ale´m disso, limn→∞ P
(n)
ij = 0 para todo i ∈ ϕ.
Teorema 16. Seja C uma classe recorrente (fechada). Todos os estados em C ou sa˜o recorrentes positivos ou sa˜o recorrentes
nulos.
Comenta´rio 12. Portanto uma CM irredutı´vel ou e´ recorrente positiva, ou recorrente nula ou transiente.
Teorema 17. Se D e´ um conjunto (na˜o-vazio) fechado e finito de estados, enta˜o D possui pelo menos um estado recorrente
positivo.
Teorema 18. Toda classe fechada e finita e´ recorrente positiva.
Corola´rio 6. Toda CM finita e irredutı´vel e´ recorrente positiva.
Corola´rio 7. Numa CM finita todo estado recorrente e´ positivo. Ou seja, uma CM finita na˜o possui estados recorrentes que
sa˜o nulos.
X. CONDIC¸A˜O DE EXISTEˆNCIA DE DISTRIBUIC¸O˜ES ESTACIONA´RIAS E CONDIC¸A˜O DE UNICIDADE
Mmmm.
XI. CONVERGEˆNCIA PARA A DISTRIBUIC¸A˜O ESTACIONA´RIA
Mmmm.
XII. CADEIAS DE MARKOV FINITAS: RESUMO DOS RESULTADOS
Segue abaixo um resumo dos resultados para o caso de CM’s com espac¸o de estados finito:
• Toda CM finita possui pelo menos um estado recorrente. Portanto na˜o existe CM finita transiente. Ale´m disso, todo estado
recorrente e´ positivo.
• (Crite´rio para classificac¸a˜o dos estados) Numa CM finita toda classe fechada e´ recorrente (positiva) e toda classe aberta
e´ transiente.
• Toda CM finita e irredutı´vel e´ recorrente (positiva).
• Toda CM finita e irredutı´vel possui uma u´nica distribuic¸a˜o estaciona´ria.
9
XIII. I´NDICE DE NOTAC¸O˜ES
Segue abaixo uma lista da notac¸a˜o utilizada nessa sec¸a˜o:
• (Xn)n≥0 CM em tempo discreto.
• ϕ espac¸o de estados.
• i, j, k, . . . estados em ϕ.
• µn := E(Xn) func¸a˜o me´dia da cadeia.
• σ2n := Var(Xn) func¸a˜o variaˆncia da cadeia.
• γm,n := Cov(Xm, Xn) func¸a˜o de autocovariaˆncia da cadeia.
• %m,n func¸a˜o de autocorrelac¸a˜o da cadeia.
• Pij probabilidade de transic¸a˜o do estado i para o estado j (em 1-passo).
• P = (Pij : i, j ∈ ϕ) matriz de transic¸a˜o (em 1-passo).
• pi(0)i probabilidade de [X0 = i].
• pi(0) = (pi(0)i : i ∈ ϕ) distribuic¸a˜o inicial da cadeia.
• P (n)ij probabilidade de transic¸a˜o do estado i para o estado j em n-passos.
• P (n) = (P (n)ij : i, j ∈ ϕ) matriz de transic¸a˜o em n-passos.
• pi(n)i probabilidade de [Xn = i].
• pi(n) = (pi(n)i : i ∈ ϕ) distribuic¸a˜o de Xn.
• Tj tempo da primeira visita ao estado j ou tempo de alcance do estado j.
• ρij := Pr(Tj <∞|X0 = i) probabilidade de alcanc¸ar o estado j num tempo finita saindo do estado i.
• Nj nu´mero de visitas ao estado j.
• Gij := E(Nj |X0 = i) nu´mero me´dio de visitas ao estado j saindo do estado i.
• ϕ = T ∪ C ′ ∪ C ′′ ∪ · · · onde T e´ o conjunto dos estados-T e os C’s sa˜o classes-R (fechadas) e disjuntas.
• pi distribuic¸a˜o estaciona´rio de uma cadeia.
• Nj(n) nu´mero de visitas ao estado j durante os tempos 1, . . . , n.
• Gij(n) := E(Nj(n)|X0 = i) nu´mero me´dio de visitas ao estado j durante os tempos 1, . . . , n saindo do estado i.
• mj tempo me´dio de retorno ao estado j.
• ϕR conjunto dos estados recorrentes.
• ϕ+ conjunto dos estados recorrentes positivos.
• ϕ0 conjunto dos estados recorrentes nulos.
• di perı´odo do estado i.
• d perı´odo de uma cadeia irredutı´vel.
REFEREˆNCIAS
[1] HOEL, P.; PORT, S.; STONE, C. Introduction to Stochastic Processes. Illinois: Waveland Press, 1987.
[2] GRIMMETT, G.; STIRZAKER, D. Probability and Random Processes, 3rd edition. New York: Oxford University Press, 2001.
[3] ROSS, S. Introduction to Probability Models, 8th edition. San Diego: Academic Press, 2003.
[4] FELLER, W. An Introduction to Probability Theory and its Applications, vol I. New York: John Wiley, 1957.
[5] RIZZO, M. Statistical Computing with R. New York: Chapman & Hall/CRC Press, 2008.