127
Inferência para Cadeias de Markov Nancy L. Garcia 1 1 UNICAMP, Brasil 2o. Semestre de 2012

Inferência para cadeias de markov

Embed Size (px)

Citation preview

Page 1: Inferência para cadeias de markov

Inferência para Cadeias de Markov

Nancy L. Garcia1

1UNICAMP, Brasil

2o. Semestre de 2012

Page 2: Inferência para cadeias de markov

Inferência clássica

Seja uma amostra aleatória X0,X1,X2, . . . ,Xn:I X0,X1,X2, . . . ,Xn são i.i.d.I distribuição de probabilidade conjunta:

P(X0 ∈ A0, . . . ,Xn ∈ An) =n∏

i=0

P(Xi ∈ Ai) =n∏

i=0

P(X ∈ Ai),

onde X tem a mesma distribuição das Xi ’s.Considere a sequência de v.a’s Xi.j onde Xi,j = 1 se chove noi-ésimo dia do j-ésimo ano e Xi,j = 0 se não chove no i-ésimodia do j-ésimo ano.Faz sentido pensar que estas v.a’s são i.i.d.?

Page 3: Inferência para cadeias de markov

Processos Estocásticos

Um processo estocástico é uma coleção de v.a’s

{Xt , α ∈ T}

onde T é um conjunto de índices que pode ser discretocontínuo. Em geral, T = N ou [0,∞).Neste caso, sempre é possível escrever a distribuição conjuntade um número finito destas v.a.’s

P(Xt0 ∈ A0, . . . ,Xtn ∈ An) =

P(Xt0 ∈ A0)n∏

i=1

P(Xti ∈ Ai |Xt0 ∈ A0, . . . ,Xti−1 ∈ Ai−1).

Page 4: Inferência para cadeias de markov

A teoria de Processos Estocásticos estuda diversasespecificações para as probabilidades condicionais acima eobtém resultados similares aos clássicos:

I Lei dos Grandes Números (Teorema Ergódico);I Teorema Central do Limite;I Lei Assintótica;I Estimação de máxima verossimilhança;I Testes de hipóteses;I Estimação não paramétrica.

Page 5: Inferência para cadeias de markov

I Xt : número de terremotos com magnitude maior que 5 queocorrem na região de São Francisco no período de (0, t ],onde 0 é o início do registro, por exemplo, 0:00hs do dia01/01/1950. Processo a tempo contínuo com espaço deestados discreto.

I (Xk ,Yk ): número de nascimento e mortes,respectivamente, ocorridos no dia k em uma colônia devetores trnsmissores de doença de Chagas. Processo atempo discreto com espaço de estados discreto.

I Xy ,t : espessura da camada de ozônio na locação y notempo t . Aqui temos T = R2 × [0,∞). Processo a tempocontínuo com espaço de estados contínuo.

Page 6: Inferência para cadeias de markov

I Xt : número de terremotos com magnitude maior que 5 queocorrem na região de São Francisco no período de (0, t ],onde 0 é o início do registro, por exemplo, 0:00hs do dia01/01/1950. Processo a tempo contínuo com espaço deestados discreto.

I (Xk ,Yk ): número de nascimento e mortes,respectivamente, ocorridos no dia k em uma colônia devetores trnsmissores de doença de Chagas. Processo atempo discreto com espaço de estados discreto.

I Xy ,t : espessura da camada de ozônio na locação y notempo t . Aqui temos T = R2 × [0,∞). Processo a tempocontínuo com espaço de estados contínuo.

Page 7: Inferência para cadeias de markov

I Xt : número de terremotos com magnitude maior que 5 queocorrem na região de São Francisco no período de (0, t ],onde 0 é o início do registro, por exemplo, 0:00hs do dia01/01/1950. Processo a tempo contínuo com espaço deestados discreto.

I (Xk ,Yk ): número de nascimento e mortes,respectivamente, ocorridos no dia k em uma colônia devetores trnsmissores de doença de Chagas. Processo atempo discreto com espaço de estados discreto.

I Xy ,t : espessura da camada de ozônio na locação y notempo t . Aqui temos T = R2 × [0,∞). Processo a tempocontínuo com espaço de estados contínuo.

Page 8: Inferência para cadeias de markov

I Xt : a intensidade de um sinal a uma distância t da origem.Processo a tempo contínuo com espaço de estadoscontínuo. além disso, “tempo” é a distância.

I Clientes chegam a uma fila de supermercado de acordocom um processo de Poisson. Os clientes são atendidospor um caixa que atende cada cliente de acordo a umadistribuição exponencial de parâmetro 1. Seja Xt o númerode clientes na fila. Processo a tempo contínuo comespaço de estados discreto.

I Temos duas caixas com um total de d bolas numeradas de1 a d . Em cada experimento selecionamos uma bola aoacaso e a trocamos de caixa. Seja Xt o número de bolasna caixa 1 no instante t . Processo a tempo discreto comespaço de estados discreto.

Page 9: Inferência para cadeias de markov

I Xt : a intensidade de um sinal a uma distância t da origem.Processo a tempo contínuo com espaço de estadoscontínuo. além disso, “tempo” é a distância.

I Clientes chegam a uma fila de supermercado de acordocom um processo de Poisson. Os clientes são atendidospor um caixa que atende cada cliente de acordo a umadistribuição exponencial de parâmetro 1. Seja Xt o númerode clientes na fila. Processo a tempo contínuo comespaço de estados discreto.

I Temos duas caixas com um total de d bolas numeradas de1 a d . Em cada experimento selecionamos uma bola aoacaso e a trocamos de caixa. Seja Xt o número de bolasna caixa 1 no instante t . Processo a tempo discreto comespaço de estados discreto.

Page 10: Inferência para cadeias de markov

I Xt : a intensidade de um sinal a uma distância t da origem.Processo a tempo contínuo com espaço de estadoscontínuo. além disso, “tempo” é a distância.

I Clientes chegam a uma fila de supermercado de acordocom um processo de Poisson. Os clientes são atendidospor um caixa que atende cada cliente de acordo a umadistribuição exponencial de parâmetro 1. Seja Xt o númerode clientes na fila. Processo a tempo contínuo comespaço de estados discreto.

I Temos duas caixas com um total de d bolas numeradas de1 a d . Em cada experimento selecionamos uma bola aoacaso e a trocamos de caixa. Seja Xt o número de bolasna caixa 1 no instante t . Processo a tempo discreto comespaço de estados discreto.

Page 11: Inferência para cadeias de markov

Aplicações de Cadeias de Markov

I Física, química, biologia, ciências sociais, jogos, música,linguística, neurociência, bioinformática, reconhecimentode imagens, reconhecimento de assinaturas, etc.

I Por exemplo, o “PageRank” de uma página da web comousado pelo Google é completamente definido através deuma cadeia de Markov.

Page 12: Inferência para cadeias de markov

Propriedade de Markov

I Espaço de estados discreto e tempo discretoI X0,X1, . . . v.a.’s discretas com valores possíveis I

enumerável.

P(Xn = x |X0 = x0,X1 = x1, . . . ,Xn−1 = xn−1) =

P(Xn = x |Xn−1 = xn−1)

para todo n ≥ 1 e todos os valores de x , x0, x1, . . . , xn−1 ∈ I.

Page 13: Inferência para cadeias de markov

Exemplo 1: Sejam Y0,Y1, . . . v.a.’s discretas i.i.d.. Defina

Sn = Y0 + . . .+ Yn

Neste caso,

P(Sn = x |S0 = x0,S1 = x1, . . . ,Sn−1 = xn−1)

= P(Sn−1 + Yn = x |S0 = x0,S1 = x1, . . . ,Sn−1 = xn−1)

= P(xn−1 + Yn = x |S0 = x0,S1 = x1, . . . ,Sn−1 = xn−1)

= P(xn−1 + Yn = x) = P(Sn = x |Sn−1 = xn−1).

Page 14: Inferência para cadeias de markov

Propriedade de Markov

Definições equivalentes

P(Xn = x |Xn0 = x0,Xn1 = x1, . . . ,Xnk = xk ) = P(Xn = x |Xnk = xk )

para todo n ≥ 1 e n0 < n1 < . . . < nk ≤ n − 1.

P(Xn+m = x |X0 = x0,X1 = x1, . . . ,Xn = xn) = P(Xn = x |Xn = xn)

para todo n ≥ 1 e todos os valores de x , x0, x1, . . . , xn−1 ∈ I.

Page 15: Inferência para cadeias de markov

I Cadeia de Markov homogênea

P(Xn = j |Xn−1 = i) = P(X1 = j |X0 = i) := pij

para todo n ≥ 1 e todos os valores de i , j ∈ I.I Matriz de transição

P = (pij)

A matriz de transição é uma matriz estocástica, i.e.,

pij ≥ 0, ,∑

j

pij = 1.

I Matriz de transição em n-passos

Pn = (pij(n))

ondepij(n) = P(Xn = j |X0 = i)

Page 16: Inferência para cadeias de markov

Note que P1 = P, mais ainda

pij(2) = P(X2 = j |X0 = i)

=∑k∈I

P(X2 = j ,X1 = k |X0 = i)

=∑k∈I

P(X2 = j |X1 = k)P(X1 = k |X0 = i)

=∑k∈I

pkjpik .

Portanto, P2 = P2.

Page 17: Inferência para cadeias de markov

Equações de Chapman-Kolmogorov

pij(n + m) =∑

k pkj(n)pik (m)

Consequentemente, Pn+m = PnPm e Pn = Pn.

Page 18: Inferência para cadeias de markov

Distribuições marginais

Definaµ(n)i = P(Xn = i).

eµ(n) = (µ

(n)i , i ∈ I).

Note que

µ(1)i = P(X1 = i) =

∑k

P(X1 = i ,X0 = k)

=∑

k

P(X1 = i |X0 = k)P(X0 = k)

=∑

k

pkiµ(0)k

Page 19: Inferência para cadeias de markov

µ(2)i = P(X2 = i) =

∑j

P(X2 = i ,X1 = j)

=∑

j

P(X2 = i |X1 = j)P(X1 = j)

=∑

j

pjiµ(1)j =

∑j

pji∑

k

pkjµ(0)k

Em geral,

µ(n+m) = µ(m)Pn e µ(n) = µ(0)Pn

Page 20: Inferência para cadeias de markov

Exemplo: Snoqualmie FallsI dados diários para se choveu ou não, pelo menos, 0,01 cmI 36 anosI Janeiro para obter um sistema homogêneo e estacionário.I = {0,1} Matriz de transição

P =

[p00 p01p10 p11

]Será que os dados não são independentes?

Page 21: Inferência para cadeias de markov

Hoje0 1

0 186 (91) 123 (223) 309Ontem

1 128 (223) 643 (543) 771314 766 1080

Os valores entre parenteses são os valores esperados sob ahipótese de independência. X 2 = 202,89 e χ2

1;1% = 6,63.

Page 22: Inferência para cadeias de markov

Função de verossimilhança

L(P,x) = P(X0 = x0)n−1∏i=0

P(Xi+1 = xi+1|Xi = xi)

= P(X0 = x0)n−1∏i=0

pxi ,xi+1

= P(X0 = x0)∏

k ,l∈Ipnk,l

k ,l

onde nk ,l = número de vezes em que Xi = k ,Xi+1 = l .

Page 23: Inferência para cadeias de markov

No exemplo de Snoqualmie Falls,

L(P,x) =

36∏j=1

P(X0,j = x0,j)

p18600 p123

01 p12810 p643

11 .

Assuma que os x0,j são fixos e P(X0,j = x0,j) = 1, se não,podemos usar as 36 amostras para estimar esta probabilidade.• p00 + p01 = 1 e p10 + p11 = 1,

P1,0 = n1,0/(n0,0 + n1,0)

eP1,1 = n1,1/(n0,1 + n1,1)

As estimativas de MV são dadas por:

p1,0 = 123/309 = 0,398 p1,1 = 643/771 = 0,834

Page 24: Inferência para cadeias de markov

Exemplo - Ferrugem asiática:

I Doença que está atacando as culturas de soja causandomuito prejuízo aos produtores e demanda aplicações defungicida causando danos ao meio ambiente e excessivosgastos.

I Um dos fatores que influenciam para a ocorrência dadoença é o molhamento foliar superior a oito horas.

I Molhamento foliar – acúmulo de água líquida causado porprecipitação ou condensação da umidade atmosférica naforma de orvalho - superior a 8 horas.

Page 25: Inferência para cadeias de markov

Exemplo - Ferrugem asiática:

I Doença que está atacando as culturas de soja causandomuito prejuízo aos produtores e demanda aplicações defungicida causando danos ao meio ambiente e excessivosgastos.

I Um dos fatores que influenciam para a ocorrência dadoença é o molhamento foliar superior a oito horas.

I Molhamento foliar – acúmulo de água líquida causado porprecipitação ou condensação da umidade atmosférica naforma de orvalho - superior a 8 horas.

Page 26: Inferência para cadeias de markov

Exemplo - Ferrugem asiática:

I Doença que está atacando as culturas de soja causandomuito prejuízo aos produtores e demanda aplicações defungicida causando danos ao meio ambiente e excessivosgastos.

I Um dos fatores que influenciam para a ocorrência dadoença é o molhamento foliar superior a oito horas.

I Molhamento foliar – acúmulo de água líquida causado porprecipitação ou condensação da umidade atmosférica naforma de orvalho - superior a 8 horas.

Page 27: Inferência para cadeias de markov

As variáveis coletadas:1. molhamento foliar (codificada como 1 se há molhamento

superior a oito horas e 0 caso contrário),2. velocidade do vento em m/s,3. umidade relativa do ar,4. precipitação em mm e temperatura média em oC.

Quatro estações meteorológicas:I Lucas do Rio verde (MT),I Rio Verde (GO),I Passo Fundo (RS) eI Holambra (SP)

Dados enviados diariamente para o CEPAGRI - Unicamp(Centro de Pesquisas Meteorológicas e Climáticas Aplicadas àAgricultura).

Page 28: Inferência para cadeias de markov

Fonsechi (2006)

I Modelo de Regressão Logístico para variáveis bináriasI variáveis dependem do tempo anterior, por exemplo, se

choveu no tempo t − 1 influencia se haverá molhamentoou não no tempo t . Obviamente não podemos esperarindependência de um tempo para o outro.

Modelo

P(Y | X) =n∏

i=1

P(Yi | Y1, . . . ,Yi−1,X)

onde Y é a variável resposta e X é a matriz de covariáveis.

Page 29: Inferência para cadeias de markov

Pode-se definir o i-ésimo logito como:

θi = log[

P(Yi = 1|Y1, . . . ,Yi−1,Xi)

P(Yi = 0|Y1, . . . ,Yi−1,Xi)

]e assumir que θi é função linear de Y1, . . . ,Yi−1,Xi .

Temos, então, um problema de regressão no qual a resposta Yié binária, mas o conjunto de valores da variável explicativamuda de acordo com i .

Page 30: Inferência para cadeias de markov

Para introduzir dependência no modelo é necessário criarvariáveis auxiliares que são funções lineares dos Y ′i s:

Zi =

{2Yi − 1 se Yi = 0 ou 10 se Yi desconhecido

Definimos a regressão logística da seguinte forma:

θ1 = α + βX1

θi = α +i−1∑j=1

γjZj + βXi , i = 1, . . . ,n

em que α, β e γ′s são parâmetros que variam no intervalo(−∞,∞) e a dependência foi introduzida no modelo atravésdas variáveis Z ′i s presentes nos logitos.

Page 31: Inferência para cadeias de markov

Temos

P(Y|X) =n∏

i=1

eθi

(1 + eθi ).

Para (j < i)I Yj =1, a chance do dia i ter molhamento (Yi = 1) aumenta

em eγj ,I Yj desconhecido não muda a chance,I Yj=0 diminui a chance em eγj

I um aumento de uma unidade em Xi aumenta a chance dodia i ter molhamento em eβ.

Page 32: Inferência para cadeias de markov

O modelo na forma matricial fica:

θ = [θ1 . . . θn]′ ,

Z = [Z1 . . .Zn]′ ,

λ = [α γ1 γ2 . . . γn−1 β]′ ,

A =

1 0 0 . . . 0 X11 Z1 0 . . . 0 X21 Z1 Z2 . . . 0 X3...

......

......

...1 Z1 Z2 . . . Zn−1 Xn

.

Então o modelo torna-se:

θ = Aλ (1)

Page 33: Inferência para cadeias de markov

Estruturas Markovianas de Dependência

Com a estrutura de primeira ordem o modelo torna-se:

P(Y|X) = P(Y1|X )n∏

i=2

P(Yi |Yi−1,X ).

Com a estrutura de segunda ordem o modelo torna-se:

P(Y|X) = P(Y1|X)P(Y2|Y1,X)Pn∏

i=3

P(Yi |Yi−1,Yi−2,X).

Portanto, a probabilidade de ter molhamento foliar no dia i sódepende da resposta do dia imediatamente anterior (ou doisdias). Nesse caso, os logitos podem ser escritos como:

θi = α + γZi−1 + βXi .

Page 34: Inferência para cadeias de markov

Método de análise

I Foi utilizado o software livre R (www.r-project.org)I Para as quatro estações testou-se o modelo com estrutura

Markoviana de dependência de primeira e segunda ordemI Ajustou-se primeiramente um modelo com todas as

covariáveis (Modelo completo) e depois utilizou-sestepwise para selecior as covariáveis que realmente sãosignificativas ao modelo (Modelo reduzido). Critério AIC.

I Para verificar a adequação do modelo foi utilizado aestatística “deviance” (−2logL, sendo L a funcão deverossimilhança), essa estatística tem distribuição χ2

n−p−1,sendo n − p − 1 o graus de liberdade, n é o número deobservações e p é o número de parâmetros.

Page 35: Inferência para cadeias de markov

Passo Fundo - Estrutura Markoviana de 1a ordem

Tabela: Modelo Completo

Parâmetro Estimação teste-tIntercepto -13.80594 6.03e-06Z 0.68004 0.00104UR 0.15166 2.50e-08Temp média 0.0995 0.12957Velocidade Vento -0.24003 0.28894Chuva 0.05070 0.28251

Page 36: Inferência para cadeias de markov

Passo Fundo - Estrutura Markoviana de 1a ordem

Tabela: Modelo Reduzido

Parâmetro Estimação teste-tIntercepto -15.67279 5.97e-08Z 0.66143 0.00103UR 0.16491 4.24e-11Temp média 0.10751 0.09699

Para Passo Fundo, com estrutura markoviana comdependência de primeira ordem a deviance foi 161,1 e o valortabelado da χ2

223 é 189.43, ou seja, pelo teste de bondade deajuste esse modelo é adequado.

Page 37: Inferência para cadeias de markov

Passo Fundo - Estrutura Markoviana de segundaordem

Tabela: Modelo Completo

Parâmetro Estimação teste-tIntercepto -13.80594 8.99e-06Z1 0.52782 0.0197Z2 0.36670 0.0960UR 0.15069 4.24e-08Temp média 0.10047 0.1332Velocidade Vento -0.25198 0.2793Chuva 0.055070 0.2512

Page 38: Inferência para cadeias de markov

Tabela: Modelo Reduzido

Parâmetro Estimação teste-tIntercepto -15.79363 6.88e-08Z1 0.51292 0.0204Z2 0.34475 0.1150UR 0.16604 5.61e-11Temp média 0.10841 0.100

Apesar de ter utilizado o método stepwise para selecionar omelhor modelo ainda há variáveis não significativas no modeloao nível de significância de 10%, sendo ela a variável querepresenta a estrutura de dependência de segunda ordem, ouseja, o modelo para passo fundo, com dependência deprimeira ordem é o mais adequado para o conjunto de dadosde Passo Fundo.

Page 39: Inferência para cadeias de markov

Conclusão

I Verificou-se a eficiência da utilização do Modelo LogísticoRegressivo para a estimação de molhamento foliar nacultura da soja.

I Para as quatro estações testadas, o modelo que melhorajusta aos dados meteorológicos é o logístico regressivocom estrutura markoviana de primeira ordem, ou seja, omodelo que leva em consideração a dependência do diaanterior para a ocorrência de molhamento foliar.

I Com as previsões meteorológicas e o uso do modeloproposto será possível um melhor monitoramento dacultura da soja, acionando os produtores de soja paraalertá-los quando houver indícios da ocorrência demolhamento foliar superior a 8 horas, ajudando assim omomento certo para aplicação de fungicida.

Page 40: Inferência para cadeias de markov

Urna de Ehrenfest

I Modelo para troca de calor ou gases entre dois corposisolados.

I Temos duas caixas com um total de d bolas numeradas de1 a d .

I Inicialmente algumas destas bolas estão na caixa 1 e orestante na caixa 2.

I Em cada experimento selecionamos uma bola ao acaso(i.e, selecionamos ao acaso um número entre 1 e d) e atrocamos de caixa.

I Repita o procedimento sequencialmente. Seja Xn onúmero de bolas na caixa 1 no instante n.

Page 41: Inferência para cadeias de markov

Urna de Ehrenfest

I Modelo para troca de calor ou gases entre dois corposisolados.

I Temos duas caixas com um total de d bolas numeradas de1 a d .

I Inicialmente algumas destas bolas estão na caixa 1 e orestante na caixa 2.

I Em cada experimento selecionamos uma bola ao acaso(i.e, selecionamos ao acaso um número entre 1 e d) e atrocamos de caixa.

I Repita o procedimento sequencialmente. Seja Xn onúmero de bolas na caixa 1 no instante n.

Page 42: Inferência para cadeias de markov

Urna de Ehrenfest

I Modelo para troca de calor ou gases entre dois corposisolados.

I Temos duas caixas com um total de d bolas numeradas de1 a d .

I Inicialmente algumas destas bolas estão na caixa 1 e orestante na caixa 2.

I Em cada experimento selecionamos uma bola ao acaso(i.e, selecionamos ao acaso um número entre 1 e d) e atrocamos de caixa.

I Repita o procedimento sequencialmente. Seja Xn onúmero de bolas na caixa 1 no instante n.

Page 43: Inferência para cadeias de markov

Urna de Ehrenfest

I Modelo para troca de calor ou gases entre dois corposisolados.

I Temos duas caixas com um total de d bolas numeradas de1 a d .

I Inicialmente algumas destas bolas estão na caixa 1 e orestante na caixa 2.

I Em cada experimento selecionamos uma bola ao acaso(i.e, selecionamos ao acaso um número entre 1 e d) e atrocamos de caixa.

I Repita o procedimento sequencialmente. Seja Xn onúmero de bolas na caixa 1 no instante n.

Page 44: Inferência para cadeias de markov

Urna de Ehrenfest

I Modelo para troca de calor ou gases entre dois corposisolados.

I Temos duas caixas com um total de d bolas numeradas de1 a d .

I Inicialmente algumas destas bolas estão na caixa 1 e orestante na caixa 2.

I Em cada experimento selecionamos uma bola ao acaso(i.e, selecionamos ao acaso um número entre 1 e d) e atrocamos de caixa.

I Repita o procedimento sequencialmente. Seja Xn onúmero de bolas na caixa 1 no instante n.

Page 45: Inferência para cadeias de markov

Xn é uma cadeia de Markov com espaço de estados{0,1, . . . ,d} e matriz de transição

P(x , y) =

(x/d), y = x − 1,

1− (x/d), y = x + 1,0, caso contrário

Page 46: Inferência para cadeias de markov

Ruína do jogador

Definição: Um estado a de uma cadeia de Markov é dito serabsorvente se P(a, y) = 0, para y 6= a.

I Um jogador começa com um capital inicial de i reais e fazuma sequência de apostas de R$ 1,00.

I Assuma que ele tem probabilidade p de ganhar eprobabilidade 1− q de perder a cada apostaindependentemente das apostas anteriores.

I Se seu capital chegar a zero ele se arruinará e seu capitalcontinuará zero para sempre.

Page 47: Inferência para cadeias de markov

Ruína do jogador

Definição: Um estado a de uma cadeia de Markov é dito serabsorvente se P(a, y) = 0, para y 6= a.

I Um jogador começa com um capital inicial de i reais e fazuma sequência de apostas de R$ 1,00.

I Assuma que ele tem probabilidade p de ganhar eprobabilidade 1− q de perder a cada apostaindependentemente das apostas anteriores.

I Se seu capital chegar a zero ele se arruinará e seu capitalcontinuará zero para sempre.

Page 48: Inferência para cadeias de markov

Ruína do jogador

Definição: Um estado a de uma cadeia de Markov é dito serabsorvente se P(a, y) = 0, para y 6= a.

I Um jogador começa com um capital inicial de i reais e fazuma sequência de apostas de R$ 1,00.

I Assuma que ele tem probabilidade p de ganhar eprobabilidade 1− q de perder a cada apostaindependentemente das apostas anteriores.

I Se seu capital chegar a zero ele se arruinará e seu capitalcontinuará zero para sempre.

Page 49: Inferência para cadeias de markov

Esta é uma CM com espaço de estados {0,1, . . .}onde 0 é um estado absorvente e para x ≥ 1

P(x , y) =

1− p, y = x − 1,

p, y = x + 1,0, caso contrário

Se houver um adversário que inicia o jogo comd − i reais e o jogo termina quando o capital do1o. jogador atinge 0 ou d o espaço de estados é{0,1, . . .} onde 0 e d são estado absorventes epara 1 ≤ x ≤ d − 1

P(x , y) =

1− p, y = x − 1,

p, y = x + 1,0, caso contrário

Page 50: Inferência para cadeias de markov

Esta é uma CM com espaço de estados {0,1, . . .}onde 0 é um estado absorvente e para x ≥ 1

P(x , y) =

1− p, y = x − 1,

p, y = x + 1,0, caso contrário

Se houver um adversário que inicia o jogo comd − i reais e o jogo termina quando o capital do1o. jogador atinge 0 ou d o espaço de estados é{0,1, . . .} onde 0 e d são estado absorventes epara 1 ≤ x ≤ d − 1

P(x , y) =

1− p, y = x − 1,

p, y = x + 1,0, caso contrário

Page 51: Inferência para cadeias de markov

Cadeias de nascimento e morte

I Considere uma CM com espaço de estados I = {0,1, . . .}ou I = {0,1, . . . ,d}.

I Estando no estado x no próximo passo somente poderáestar em x , x + 1 ou x − 1.

I Considere que a matriez de transição seja:

P(x , y) =

qx , y = x − 1,px , y = x + 1,rx , y = x ,0, caso contrário

onde para cada x , px ,qx , rx ≥ 0, px + qx + rx = 1.

Page 52: Inferência para cadeias de markov

Classificação de estados:

Seja A um subconjunto do espaço de estados I. O tempo dechegada a A é definido como:

TA =

{min{n > 0; Xn ∈ A}, se Xn atinge A,

∞, caso contrário

Notaçao:A = {a} usamos a notação: Ta.Denotaremos por Px (·) as probabilidades dosdiversos eventos quando o estado inicial dacadeia for x . Assim,

Px (X1 = a,X2 = b) = P(X1 = a,X2 = b|X0 = x).

Page 53: Inferência para cadeias de markov

Uma identidade importante:

Pn(x , y) =∑n

m=1 Px (Ty = m)Pn−m(y , y), n ≥ 1

Se a é um estado absorvente então

Pn−m(a,a) = 1, para1 ≤ m ≤ n.

e

Pn(x ,a) =n∑

m=1

Px (Ta = m)Pn−m(a,a)

=n∑

m=1

Px (Ta = m) = Px (Ta ≤ n).

Page 54: Inferência para cadeias de markov

Observe que

Px (Ty = 1) = Px (X1 = y) = P(x , y)

e que

Px (Ty = 2) =∑z 6=y

Px (X1 = z,X2 = y) =∑z 6=y

P(x , z)P(z, y).

Em geral,

Px (Ty = n + 1) =∑

z 6=y P(x , z)Pz(Ty = n), n ≥ 1

Page 55: Inferência para cadeias de markov

Estados recorrentes e transientes

I ρxy = Px (Ty <∞) = probabilidade que uma CMcomeçando em x consiga atingir o estado y em tempofinito.

I ρyy = probabilidade que uma CM começando em y algumavez retorne a y .

I Um estado y é dito ser:1. recorrente se ρyy = 1;2. transiente se ρyy < 1.

I Se y é um estado absorvente, então Py (T1 = y) = 1 eρyy = 1 e y é recorrente.

Page 56: Inferência para cadeias de markov

Estados recorrentes e transientes

I ρxy = Px (Ty <∞) = probabilidade que uma CMcomeçando em x consiga atingir o estado y em tempofinito.

I ρyy = probabilidade que uma CM começando em y algumavez retorne a y .

I Um estado y é dito ser:1. recorrente se ρyy = 1;2. transiente se ρyy < 1.

I Se y é um estado absorvente, então Py (T1 = y) = 1 eρyy = 1 e y é recorrente.

Page 57: Inferência para cadeias de markov

Estados recorrentes e transientes

I ρxy = Px (Ty <∞) = probabilidade que uma CMcomeçando em x consiga atingir o estado y em tempofinito.

I ρyy = probabilidade que uma CM começando em y algumavez retorne a y .

I Um estado y é dito ser:1. recorrente se ρyy = 1;2. transiente se ρyy < 1.

I Se y é um estado absorvente, então Py (T1 = y) = 1 eρyy = 1 e y é recorrente.

Page 58: Inferência para cadeias de markov

Estados recorrentes e transientes

I ρxy = Px (Ty <∞) = probabilidade que uma CMcomeçando em x consiga atingir o estado y em tempofinito.

I ρyy = probabilidade que uma CM começando em y algumavez retorne a y .

I Um estado y é dito ser:1. recorrente se ρyy = 1;2. transiente se ρyy < 1.

I Se y é um estado absorvente, então Py (T1 = y) = 1 eρyy = 1 e y é recorrente.

Page 59: Inferência para cadeias de markov

Para cada estado y ∈ I defina a v.a.

N(y) =∞∑

n=1

1y (Xn)

o número de vezes que a CM visita o estado y .Note que:

Px (N(y) ≥ 1) = Px (Ty <∞) = ρxy .

É fácil ver que a propriedade de Markov diz que: aprobabilidade da cadeia começando em x visitar pela primeiravez y após m passos e retornar a y n passos depois é

Px (Ty = m)Py (Ty = n).

Page 60: Inferência para cadeias de markov

Portanto,

Px (N(y) ≥ 2) =∞∑

m=1

∞∑n=1

Px (Ty = m)Py (Ty = n)

=

( ∞∑m=1

Px (Ty = m)

)( ∞∑n=1

Py (Ty = n)

)= ρxyρyy .

Similarmente,

Px (N(y) ≥ m) = ρxyρm−1yy , m ≥ 1.

Usando o fato quePx (N(y) = m) = Px (N(y) ≥ m)− Px (N(y) ≥ m + 1).

Px (N(y) = m) = ρxyρm−1yy (1− ρyy ), m ≥ 1.

e

Px (N(y) = 0) = (1− ρxy ).

Page 61: Inferência para cadeias de markov

Observe que

Ex (N(y)) = Ex

( ∞∑n=1

1y (Xn)

)

=∞∑

n=1

Ex (1y (Xn))

=∞∑

n=1

Pn(x , y).

Defina

G(x , y) = Ex (N(y)) =∑∞

n=1 Pn(x , y).

Page 62: Inferência para cadeias de markov

O seguinte teorema descreve a diferença fundamental entreestados transientes e estados recorrentes:Teorema: (i) Seja y um estado transiente. Então:

Px (N(y) <∞) = 1

eG(x , y) =

ρxy

1− ρyy.

(ii) Seja y um estado recorrente. Então:

Py (N(y) =∞) = 1 e G(y , y) = 1.

Mais ainda,

Px (N(y) =∞) = Px (Ty <∞) = ρxy .

Se ρxy = 0 então G(x , y) = 0 enquanto que ρxy > 0 implicaque G(x , y) =∞.

Page 63: Inferência para cadeias de markov

Seja y um estado transiente. Como

∞∑n=1

Pn(x , y) = G(x , y) <∞ ⇒ limn

Pn(x , y) = 0.

Uma CM é dita ser transiente se todos os seus estados sãotransientes e recorrente se todos os seus estados sãorecorrentes.É fácil ver que toda CM finita precisa ter pelo menos um estadorecorrente, i.e. não pode ter todos os seus estados transientes:

0 =∑y∈I

limn

Pn(x , y)

CM finita = limn

∑y∈I

Pn(x , y)

= limn

Px (Xn ∈ I)

= 1.

Page 64: Inferência para cadeias de markov

Decomposição do espaço de estados:

Sejam x e y ∈ I

x → y , se ρxy > 0.

I x → y se, e somente se, Pn(x , y) > 0 para algum n.I x → y e y → z então x → z.I Teorema: Seja x um estado recorrente e suponha que

x → y . Então y é recorrente e ρxy = ρyx = 1.

Page 65: Inferência para cadeias de markov

I Um conjunto não vazio C ⊂ I é dito ser fechado senenhum estado de dentro de C leva a um estado fora deC, i.e., se

ρxy = 0, x ∈ C, y 6∈ C.

I Equivalentemente, C é fechado se, e somente se,

Pn(x , y) = 0, x ∈ C, y 6∈ C, para todo n ≥ 1.

I Se C é um conjunto fechado então uma CM começandoem C ficará em C com probabilidade 1.

I Se A é um estado absorvente, então {a} é fechado.

Page 66: Inferência para cadeias de markov

I Um conjunto fechado é dito ser irredutível se x → y paratodos x , y ∈ C.

I Segue do Teorema anterior que se C é uma classefechada e irredutível, então ou todo estado de C érecorrente, ou todo estado de C é recorrente.

I Seja C uma classe fechada irredutível de estadosrecorrentes. então ρxy = 1, Px (N(y) =∞) = 1 eG(x , y) =∞ para todas as escolhas de x , y ∈ C.

I Uma cadeia de Markov irredutível é uma cadeia cujoespaço de estados I é fechado e irredutível. Segue quetais cadeias ou são transientes ou são recorrentes.

Page 67: Inferência para cadeias de markov

Teorema: Seja C um conjunto finito de estados. Então todosos estados em C são recorrentes.

Considere uma CM com um número finito de estados.I Se a CM é irredutível, deve ser recorrente.I Se a CM não é irredutível verificamos quais são as classes

irredutíveis e quais estados são recorrentes e transientes.

Page 68: Inferência para cadeias de markov

Exemplo: I = {0,1,2,3,4,5}

1 0 0 0 0 014

12

14 0 0 0

0 15

25

15 0 1

50 0 0 1

613

12

0 0 0 12 0 1

20 0 0 1

4 0 34

Page 69: Inferência para cadeias de markov

Note que a matriz abaixo traz os valores + e 0 de acordo comx → y , i.e, ρxy > 0.

+ 0 0 0 0 0+ + + + + ++ + + + + +0 0 0 + + +0 0 0 + + +0 0 0 + + +

Obviamente, se P(x , y) > 0 então ρxy > 0, mas a recíprocanão é verdadeira pois P(2,0) = 0 e ρ20 > 0 pois

P2(2,0) = P(2,1)P(1,0) =15

14

=1

20> 0.

Page 70: Inferência para cadeias de markov

I 0 é um estado absorvente, portanto é recorrente.I Também vemos pela matriz acima que {3,4,5} é uma

classe finita, fechada e irredutível portanto todos os seusestados são recorrentes.

I 2→ 0 e 1→ 0 mas 0 6→ 2 e 0 6→ 1, sendo assim 1 e 2 temque ser estados transientes.

Page 71: Inferência para cadeias de markov

Sejam:IT o conjunto de estados transientes;IR o conjunto de estados recorrentes.

Neste exemplo, IT = {1,2} e IR = {0} ∪ {3,4,5}.Sempre é possível decompor IR numa união disjunta (finita ouenumerável) de classes irredutíveis.

Page 72: Inferência para cadeias de markov

Probabilidades de absorção

Seja C uma das classes fechadas irredutíveis de estadosrecorrentes e defina:

ρC(x) := Px (TC <∞)

a probabilidade de que a CM começando em x eventualmenteatinja C ( e permaneça em C para sempre). Claramente,

ρC(x) = 1, se x ∈ C ρC(x) = 0, se x é recorrente, mas x 6∈ C

Como calcular ρC(x) se x for transiente?

Page 73: Inferência para cadeias de markov

I Se temos somente um número finito de estadostransientes, em particular se I é finito, pode-se encontrarρC(x), x ∈ IT através de um sistema linear de equações.

I Observe que se x ∈ IT , uma cadeia somente pode serabsorvido em C se, (i) for absorvindo em C no instante 1;ou (ii) continuar em IT no instante 1 e ser absorvido em Cem um tempo futuro.

I O evento (i) tem probabilidade∑

y∈C P(x , y) e o evento (ii)tem probabilidade

∑y∈IT

P(x , y)ρC(y).

Page 74: Inferência para cadeias de markov

ρC(x) =∑

y∈C P(x , y) +∑

y∈ITP(x , y)ρC(y), x ∈ IT .

A equação acima pode ser resolvida se IT é finito. No caso deIT não é claro como resolver o sistema, nem mesmo garantirque o sistema tenha solução única.

Page 75: Inferência para cadeias de markov

Exemplo: Encontre ρ10 = ρ{0}(1) e ρ20 = ρ{0}(2). Montando osistema de equções temos,

ρ10 = 1/4 + (1/2)ρ10 + (1/4)ρ20

ρ20 = (1/5)ρ10 + (2/5)ρ20

A solução é: ρ10 = (3/5) e ρ20 = (1/5).Note que uma vez que uma CM começando em um estadotransiente x entra em uma classe fechada, irredutível deestados recorrentes, visita todos os estados de C comprobabilidade 1. Assim,

ρxy = ρC(x), para todo y ∈ C.

Portanto,ρ13 = ρ14 = ρ15 = 2/5,

ρ23 = ρ24 = ρ25 = 4/5.

Page 76: Inferência para cadeias de markov

Cadeias de nascimento e morte

I CM irredutível: ou todos os estados recorrentes, ou todosestados transientes.

I CM irredutível finita: todos os estados recorrentes.I O que fazer no caso I infinito?

Page 77: Inferência para cadeias de markov

I Considere uma CM com espaço de estados I = {0,1, . . .}ou I = {0,1, . . . ,d}.

I Estando no estado x no próximo passo somente poderáestar em x , x + 1 ou x − 1.

I Considere que a matriez de transição seja:

P(x , y) =

qx , y = x − 1,px , y = x + 1,rx , y = x ,0, caso contrário

onde para cada x , px ,qx , rx ≥ 0, px + qx + rx = 1. Noteque q0 = 0 e pd = 0 se d <∞.

I Assuma que px ,qx > 0 para 0 < x < d .

Page 78: Inferência para cadeias de markov

Para a < b ∈ I, seja

u(x) = Px (Ta < Tb), a < x < b

eu(a) = 1, u(b) = 0.

Portanto, é fácil ver que

u(y) = qyu(y − 1) + ryu(y) + pyu(y + 1), a < y < b.

Como ry = 1− py − qy temos

u(y + 1)− u(y) =qy

py(u(y)− u(y − 1)), a < y < b.

Page 79: Inferência para cadeias de markov

Defina γ0 = 1 e

γy =q1···qyp1···py

, 0 < y < d .

Temos,

u(x) =

∑b−1y=x γy∑b−1y=a γy

, a < x < b.

Portanto, da definição de u(x) temos

Px (Ta < Tb) =∑b−1

y=x γy∑b−1y=a γy

, a < x < b.

Px (Tb < Ta) =∑x−1

y=a γy∑b−1y=a γy

, a < x < b.

Page 80: Inferência para cadeias de markov

Exemplo:I Um jogador na roleta faz uma sequência de apostas de

$1.00.I Ele tem probabilidades 9/19 e 10/19 de ganhar e perder

respectivamente.I O jogador decide que ele pára de jogar se ele lucra $25.00

ou se ele perde $10.00.(a) Ache a probabilidade dele parar de jogar ganhando.(b) Ache sua perda esperada.

Page 81: Inferência para cadeias de markov

I Xn: capital do jogador no tempo n com X0 = 10.I Xn é uma cadeia de nascimento e morte comI = {0,1, . . . ,35}

I taxas px = 9/19,0 < x < 35 e qx = 10/19,0 < x < 35.I Os estados 0 e 35 são aobsorventes.

Aplicar a fórmula para a = 0, x = 10,b = 35. Portanto,

γy = (10/9)y , 0 ≤ y ≤ 34,

Probabilidade de ganhar:

P10(T35 < T0) =

∑9y=0(10/9)y∑34y=0(10/9)y

=(10/9)10 − 1(10/9)35 − 1

= 0.047.

Perda esperada: 10− 35× (0.047) = 8.36.

Page 82: Inferência para cadeias de markov

Distribuição estacionária

I Seja Xn,n ≥ 0 uma CM com espaço de estados I e matrizde transição P.

I Uma distribuição estacionária π(x), x ∈ I satisfaz:1. π(x) ≥ 0, x ∈ I;2.∑

x∈I π(x) = 1;3.

∑x∈I π(x)P(x , y) = π(y), y ∈ I.

Page 83: Inferência para cadeias de markov

Distribuição limite

I Suponha que temos

limn→∞

Pn(x , y) = π(y), y ∈ I.

I Neste capítulo queremos determinar quando temosdistribuição estacionária, quando temos distribuição limitee quando elas são iguais.

Page 84: Inferência para cadeias de markov

Propriedades de distribuições estacionáriasSeja π uma distribuição estacionária para P. Então:∑

x∈Iπ(x)P2(x , y) =

∑x∈I

π(x)∑

z

P(x , z)P(z, y)

=∑

z

(∑x

π(x)P(x , z)

)P(z, y)

=∑

z

π(z)P(z, y) = π(y).

Portanto, por indução, usando a fórmula

Pn+1(x , y) =∑

z

Pn(x , z)P(z, y),

temos ∑x∈I π(x)Pn(x , y) = π(y), y ∈ I.

Page 85: Inferência para cadeias de markov

I Se π0 = π temos que

P(Xn = y) = π(y), y ∈ I

e a distribuição de Xn é independente de n.I Suponha reciprocamente que πn não dependa de n, então

a distribuição de X0 e X1 são idênticas eπ0(y) = π1(y) =

∑x π0(x)P(x , y). Consequentemente,

π0 é distribuição estacionária.I A distribuição de Xn é independente de n se, e

somente se, π0 é estacionária.

Page 86: Inferência para cadeias de markov

Suponha que π é distribuição estacionária e

limn→∞

Pn(x , y) = π(y), y ∈ I.

então P(Xn = y) =∑

x π0(x)Pn(x , y), y ∈ I.Tirando o limite nos dois lados da equação e passando o limitedentro do somatório, temos

limn→∞

Pn(x , y) =∑

x

π0(x)π(y), y ∈ I.

Como∑

x π0(x) = 1 temos

limn→∞ Pn(x , y) = π(y), y ∈ I.

Page 87: Inferência para cadeias de markov

I Temos que se π é uma distribuição estacionária e

limn→∞

Pn(x , y) = π(y), y ∈ I

, a distribuição πn se aproxima de π independemtementeda distribuição inicial.

I Portanto, π é a única distribuição estacionária, senãousaríamos a outra distribuição para π0 e teríamos π = π0.

I Suponha que observamos nosso sistema por um tempolongo, digamos n0 passos e seja

Yn = Xn0+n,

As v.a.’s Yn formam uma CM com a mesma matriz detransição P. Se N0 for suficientemente grande, podemossupor que a distribuição marginal de Yn é a mesma dadistribuição estacionária π.

Page 88: Inferência para cadeias de markov

Exemplo 1:

P =

[1− p p

q 1− q

]Se p + q > 0 temos

π(0) =q

p + qπ(1) =

pp + q

.

Page 89: Inferência para cadeias de markov

Cadeias de nascimento e morte

Considere uma cadeia de nascimento e morte comI = {0,1, . . .}. Vamos assumir que a cadeia é irredutível i.e.,

px > 0, 0 ≤ x <∞

qx > 0, 0 < x <∞.

O sistema de equações∑x

π(x)P(x , y) = π(y)

será:r0π(0) + q1π(1) = π(0)

py−1π(y − 1) + ryπ(y) + qy+1π(y + 1) = π(y), y ≥ 1.

Page 90: Inferência para cadeias de markov

Como px + rx + q + x = 1, temos

(1− p0)π(0) + q1π(1) = π(0)

py−1π(y−1)+(1−py−qy )π(y)+qy+1π(y +1) = π(y), y ≥ 1.

Portanto,

qy+1π(y + 1)− pyπ(y) = qyπ(y)− py−1π(y − 1), y ≥ 1

e consequentemente, por indução

qy+1π(y + 1)− pyπ(y) = 0, y ≥ 0.

Neste caso, obtemos

π(y + 1) =py

qy+1π(y).

Page 91: Inferência para cadeias de markov

Usando novamente indução é fácil ver que:

π(x) =p0 · p1 · · · px−1

q1 · q2 · · · qxπ(0).

Finalmente, se chamamos

π0 = 1, , πx =p0 · p1 · · · px−1

q1 · q2 · · · qx, x ≥ 1,

temos

π(x) = πxπ(0), x ≥ 0.

Page 92: Inferência para cadeias de markov

Temos que verificar se as soluções de (1) satisfazem∑x π(x) = 1.

Caso 1:∑

x πx <∞.

1 =∑

x

π(x) =

(∑x

πx

)π(0)

Portanto,

π(0) = 1∑x πx

, π(x) = πx∑x πx

x ≥ 1.

Caso 2:∑

x πx =∞.

∑x

π(x) =

(∑x

πx

)π(0) =

{0, se π(0) = 0∞, se π(0) > 0

Portanto, não existe distribuição estacionária.Todas as deduções anteriores valem para o caso de cadeiasde nascimento e morte finitas, i.e. d <∞.

Page 93: Inferência para cadeias de markov

Urna de Ehrenfest

d = 3

P =

0 1 0 0

1/3 0 2/3 00 2/3 0 1/30 0 1 0

Esta é uma cadeia de nascimento e morte irredutível com

π0 = 1, π1 = 3, π2 = 3, π3 = 1.

Portanto, a única distribuição estacionária é dada por:

π(0) = 1/8, π(1) = 3/8, π(2) = 3/8, π(3) = 1/8.

Note que neste caso, Pn(x , y) = 0 para valores ímpares de n.Assim,

Pn(x , x) 6→ π(x).

Page 94: Inferência para cadeias de markov

Urna de Ehrenfest modificada: Suponha que temos omesmo esquema da urna de Ehrenfest, mas a cada trocajogamos independentemente uma moeda e se esta sair caradecidimos não mudar a bola de urna.

P =

1/2 1/ 0 01/6 1/2 2/6 00 2/ 1/2 1/60 0 1/2 1/2

Entretanto, π0 = 1, π1 = 3, π2 = 3, π3 = 1.Portanto, a única distribuição estacionária é dada por:

π(0) = 1/8, π(1) = 3/8, π(2) = 3/8, π(3) = 1/8.

Neste caso, veremos mais tarde,

Pn(x , y)→ π(y), para todo y, quando n→∞.

Page 95: Inferência para cadeias de markov

Condições de balanço detalhado

π(x)p(x , y) = π(y)p(y , x) ⇒ π(y) =∑

x

π(x)p(x , y)

pois∑

x p(y , x) = 1.

Page 96: Inferência para cadeias de markov

Estados recorrentes positivos e recorrentes nulos

Um estado é recorrente se

ρyy = Py (Ty < +∞) = 1

Se y é recorrente então:y é recorrente positivo se my = Ey (Ty ) < +∞;y é recorrente nulo se my = Ey (Ty ) = +∞;

Page 97: Inferência para cadeias de markov

Número médio de visitas a um estado recorrente:

Defina Nn(y) o número de visitas ao estado y nos instantes1,2, . . . ,n. Isto é, Nn(y) =

∑nm=1 1y (Xm).

Defina Gn(x , y) o número médio de visitas ao estado y dadoque X0 = x durante os instantes 1,2, . . . ,n

Gn(x , y) =n∑

m=1

Ex [1y (Xm)] =n∑

m=1

Pm(x , y).

Page 98: Inferência para cadeias de markov

1.- Seja y um estado transiente. então

limn

Nn(y) = N(y) <∞ com probabilidade 1,

elim

nGn(x , y) = G(x , y) < +∞.

Portanto,

limn

Nn(y)

n= 0 com probabilidade 1,

elim

n

Gn(x , y)

n= 0, x ∈ S.

Page 99: Inferência para cadeias de markov

Seja y um estado recorrente. Então:

limn

Nn(y)

n=

1Ty<∞

mycom probabilidade 1,

elim

n

Gn(x , y)

n=ρxy

my, x ∈ S.

Intuição: Uma vez que a cadeia chega ao estado y ela retornaa y , “em média uma vez a cada my unidades de tempo”.Assim, se y pode ser alcançado eventualmente e n é grande, aproporção de tempo que a cadeia gasta no estado y éaproximadamente 1/my .

Page 100: Inferência para cadeias de markov

Corolário: Seja C um conjunto fechado irredutível de estadosrecorrentes. Então,

limn

Gn(x , y)

n=

1my

, x , c ∈ C

e se P(X0 ∈ C) = 1,

limn

Nn(y)

n=

1my

com probabilidade 1.

Note que as fórmulas valem para my = +∞.

Page 101: Inferência para cadeias de markov

Teorema: Seja x um estado recorrente positivo e suponha quex → y . então y é recorrente positivo.Portanto, em uma classe de estados fechada, irredutível outodos os estados são transientes, ou todos os estados sãorecorrentes positivos ou todos os estados são recorrentesnulos.

Page 102: Inferência para cadeias de markov

I Se C é uma classe fechada e finita então C tem pelomenos um estado recorrente positivo.

I Se C é uma classe fechada, irredutível e finita de estadosentão todo estado é recorrente positivo.

I Uma cadeia de Markov irredutível com um número finitode estados é recorrente positiva.

I Uma cadeia de Markov tendo um número finito de estadosnão tem estados recorrentes nulos.Note que se y é um estado recorrente, então y estácontido numa classe fechada de estados recorrentes.Como esta classe é necessariamente finita, ela contémpelo menos um estado recorrente positivo e portanto todossão recorrentes positivos.

Page 103: Inferência para cadeias de markov

Existência e unicidade das distribuições estacionáriasTeorema: Seja π uma distribução estacionária. Se x étransiente ou recorrente nulo, então π(x) = 0.Prova: Se x é transiente ou recorrente nulo então

limn

Gn(z, x)

n= 0, z ∈ S.

Portanto, se pudermos trocar a ordem da soma e do limite:

π(x) limn

∑z

π(z) limn

Gn(z, x)

n= 0.

Teorema: Seja uma cadeia de Markov irredutível, recorrentepositiva então existe uma única distribuição estacionária πdada por:

π(y) =1

my, y ∈ S.

Page 104: Inferência para cadeias de markov

Consequências:Uma cadeia de Markov é positiva recorrente éirredutível se, e somente se tem uma únicadistribuição estacionária.Se uma cadeia de Markov tem um número finitode estados e é irredutível então ela tem uma únicadistribuição estacionária.Seja Xn,n ≥ 0 uma cadeia de Markov irredutível,recorrente positiva com distribuição estacionáriaπ. então com probabilidade 1,

minn

Nn(y)

n= π(y), y ∈ S.

Page 105: Inferência para cadeias de markov

Cadeia redutíveis:

Teorema: Seja C um conjunto irredutível fechado de estadosrecorrentes positivos. Então a cadeia de Markov tem umaúnica distribuição estacionária concentrada em C, isto é,π(x) = 0, se x 6∈ C e π(x) = 1/mx se x ∈ C.Suponha que a cadeia tenha dois conjuntos irredutíveisfechados de estados recorrentes positivos C0 e C1. então acadeia tem uma distribuição estacionária π0 concentrada emC0 e uma distribuição estacionária π1 concentrada em C1.Mais ainda, as distribuições

πα(x) = (1− α)π0(x) + απ1(x)

também são estacionárias para a CM.

Page 106: Inferência para cadeias de markov

Teorema Central do Limite

Referências: Doeblin (1938) e Kendall (1957)Considere uma cadeia de Markov X0,X1, . . . compossivelmente infinitos estados I = {1,2, . . .} ergódica. Assim,todos os tempos de retorno my são finitos.Seja f : I → R e defina

Sn =n∑

m=1

f (Xm).

Sejam as v.a’s T (1)y < T (2)

y < . . . os tempos de visita a y . Isto é,

T (k)y = min{n > T (k−1)

y ; Xn = y}

Page 107: Inferência para cadeias de markov

Teorema ergódico

Assim, as v.a’s

f (XT (k)

y +1) + · · ·+ f (X

T (k+1)y

), k = 1,2, . . .

são iid com esperança finita

µf ,y = E(

f (XT (k)

y +1) + · · ·+ f (X

T (k+1)y

)).

O Teorema ergódico diz que

Sn

n→

µy

myem probabilidade.

Page 108: Inferência para cadeias de markov

CLT - cont.

Agora escreva,

Zk =

T (k+1)y∑

m=T (k)y +1

f (Xm)−µy

my

(T (k+1)

y − T (k)y

).

Assim, Z1,Z2, . . . são iid E(Zi) = 0 e defina

σ2y = Var(Z1).

Teorema: Se µy existe e σy é finita e não nulas e os tempos derecorrencia T (k)

y tem segundo momento finito então

Sn − (µy/my )n√σ2

y n/my

⇒ N(0,1).

Page 109: Inferência para cadeias de markov

Teoria de verossimilhança para Cadeias de Markov

Função de verossimilhança

L(P,x) = P(X0 = x0)n−1∏i=0

P(Xi+1 = xi+1|Xi = xi)

= P(X0 = x0)n−1∏i=0

pxi ,xi+1

= P(X0 = x0)∏

k ,l∈IpNk,l (n)

k ,l

onde Nk ,l(n) = número de vezes em que Xi = k ,Xi+1 = l nosinstantes 1, . . . ,n.

Page 110: Inferência para cadeias de markov

Notação: Nij(n) = Nij e nij(n) = nij ,

L(π0,P,x) = π0(x0)n−1∏i=0

P(Xi+1 = xi+1|Xi = xi)

= π0(x0)n−1∏i=0

pxi ,xi+1 = π0(x0)∏

k ,l∈IpNk,l (n)

k ,l

= π0(x0)∏k∈I

Lk (P)

onde Lk (P) =∏

l∈I pNk,l (n)k ,l depende somente dos elementos

na k -ésima linha da matrix P.Seja l(π0,P,x) = log L(π0,P,x). Então temos as equações,

l(π0,P,x) = l0(π0, x0) +∑k∈I

lk (P,x).

Page 111: Inferência para cadeias de markov

Queremos maximizar l sujeita a condições que∑x

π0(x) = 1e que∑j∈I

P(k , j) = 1

para todo k ∈ I. Usando multiplicadores de Lagrange eescrevendo ni =

∑j∈I temos as estimativas de MV

pij =nij

niquando ni > 0 π0(i) = 1(i = x0).

Se ni = 0 colocamos pij = 0, j 6= i .Seja

I = {i ∈ I : ni > 0}

a porção observada do espaço de estados. Obviamente, I éfinito. Note que (pij , i , j ∈ I) é uma matriz estocástica sobre I.Denote esta matriz por P.

Page 112: Inferência para cadeias de markov

Teorema: Se (Xn) é uma cadeia de Markov ergódica(irredutível, recorrente positiva), então Pij → pij comprobabilidade 1 para todo i , j ∈ S independentemente dadistribuição inicial.Lembre-se que

1n

Nij(n)→ π(i)pij

e1n

Ni(n)→ π(i).

Page 113: Inferência para cadeias de markov

Teorema: Se (Xn) é uma cadeia de Markov ergódica, entãoindependentemente da distribuição inicial[√

Ni(n)(Pij(n)− pij)]

i,j∈I→ N(0,Σ)

onde

σij,kl =

pij(1− pij), (i .j) = (k , l)−pijpil , i = k , j 6= l

0, caso contrário.

Obs.: A covariância assintótica tem uma estrutura multinomialdentro das linhas e independência entre as linhas.

Page 114: Inferência para cadeias de markov

Aplicação a Snoqualmie FallsUsando o resultado do Teorema anterior vemos que P01 e P11são assintóticamente independentes. Mais ainda

P11 ≈ N(p11,p11(1− p11)/nπ(1))

onde π é a distribuição estacionária da CM.Podemos estimar a variância usando

P11 =N11

N1e π(1) =

N1

n

onde

N11 =36∑

i=1

N(i)11 , . . .

Como n11 = 643, n1 = 771, n01 = 123, n0 = 309 e n = 1080,intervalos de confiança assintóticos de 95%:

IC(p11,95%) = (0.808; 0.860) IC(p01,95%) = (0.343; .453).

Page 115: Inferência para cadeias de markov

Note que cada intervalo tem 95% de confiança, masconjuntamente, usando a independência assintótica,(.95)2 = .903. a fim de encontrar uma região de confiança com95% devemos usar intervalos individuais com 97.5%, obtendoo retângulo:

(.775; .893)× (.272; .524).

Algumas vezes, é natural parametrizar o modelo.

Page 116: Inferência para cadeias de markov

Eugen OneginO próprio Markov deu um exemplo de Cadeia de Markov em1924. Markov estudou um extrato de um poema de Puskinchamado Eugen Onegin e classificou 20.000 caracteresconsecutivos em vogais e consoantes.

Vogal seguinte Consoante seguinte TotalVogal 1106 7536 8638

Consoante 7533 3829 11362Total 8639 11361 20000

Page 117: Inferência para cadeias de markov

É bastante óbvio que a escolha de vogal e consoante para aletra seguinte não é independente da letra atual. Um modelomuito simples é assumir que a troca se faz de forma constante,isto é a matrix de transição é:

P =

[1− p p

p 1− p

]

Page 118: Inferência para cadeias de markov

Teoria assintóticaPor simplicidade no caso paramétrico vamos assumir espaçode estados finito. Assuma que as probabilidades de transiçãodependam somente de um parâmetro θ, tomando valores emum espaço paramétrico Θ ⊂ Rr . Vamos assumir as seguintescondições de regularidade:

1. D = {(i , j); pij > 0} não depende de θ.2. Cada pij(θ) é 3-vezes continuamente diferenciável.3. A matriz de dimensão d × r , ∂pij(θ)/∂θk , i , j ∈ D,

k = 1, . . . , r e d é a cardinalidade de D, tem posto r .4. Para cada θ existe somente uma classe ergódica e

nenhum estado transiente.

Page 119: Inferência para cadeias de markov

Podemos escrver a verossimilhança como

l(θ,x) =∑

D

nij log pij(θ).

Diferenciando esta expressão obtemos as equações deverossimilhança:

∂θkln(θ) =

∑D

ni jpij(θ)

∂pij(θ)

∂θk= 0, k = 1, . . . , k .

Seja θ0 o verdadeiro valor do parâmtro.

Page 120: Inferência para cadeias de markov

Teorema: Assuma as condições de regularidade:(i) Existe uma solução θ das equações de verossimilhança queé consistente;(ii)√

n(θ − θ0)→ N(0, I−1(θ0)), onde I é a matriz deinformação:

Iuv (θ0) =∑

(i,j)∈D

π(i ,θ0)

pij(θ0)

∂pij(θ0)

∂θu

∂pij(θ0)

∂θv.

(iii) Var√

n(θ − θ0) pode ser estimada de forma consistentepelo inverso da informação observada[

−Nij

n∇2 log pij(θ)

]−1

.

Page 121: Inferência para cadeias de markov

Exemplo: Eugen Onegin Estimamos p pela equação:

l(p) = (n00 + n11) log(1− p) + (n01 + n10) log p,

onde 0 = vogal e 1 = consoante. O máximo é obtido em:

P =N01 + N10

ne p =

7532 + 753320000

= 0.753.

A segunda derivada da verossimilahnça é:

l ′′(p) = −n00 + n11

(1− p)2 +n01 + n10

p2

Portanto, o erro padrão assintótico estimado é(−l ′′(p))−1/2 = (p(1− p)/n)1/2 = (.753× .247/20000)1/2. Oque nos dá um IC de nível 95% como:

(.747; .759)

Note que nem p01 = .872 nem p10 = .663 pertence a esteintervalo, indicando que o modelo de um parmâmetro não éadequado.

Page 122: Inferência para cadeias de markov

Teorema: Assuma as condições de regularidade. Seja θ oEMV sob a hipótse paramétrica H0. Também, seja P o EMVnão paramétrico e θ0 o verdadeiro valor do parâmetro, quandoH0 é verdadeira. Então:(i) 2

(l(θ)− l(θ0)

)D→ χ2(r);

(ii) 2(

l(P)− l(θ))D→ χ2(d(d − 1)− r);

(iii) As estatísticas em (i) e (ii) são assintóticqamenteindependentes.

Page 123: Inferência para cadeias de markov

Teorema: Assuma as condições de regularidade. Sejam θ0 oEMV sob a hipótese paramétrica H0 : θ ∈ Θ0 e θ1 o EMV sob ahipótese θ ∈ Θ0 ∪Θ1. Então para se testar H0 : θ ∈ Θ0 vs.H1 : θ ∈ Θ1 a estatística do teste a ser utilizada é:

−2(

l(θ0)− l(θ1))D→ χ2(s)

onde s = dim(Θ1 ∪Θ0)− dim(Θ0).

Page 124: Inferência para cadeias de markov

Teste para independência: Suponha que queremos testar ahipótese de que a seqüência X1,X2, . . . tomando valores emI = {0,1, . . . ,K} é independente vs. a hipótese de quepertença a uma CM de ordem 1. Em termos de parametrizaçãosimplesmente colocamos: H0 : pij = θj para todo i , j ∈ I.Neste caso, precisamos calcular o máximo sob as duashipóteses (independência e CM de ordem 1).

Page 125: Inferência para cadeias de markov

CM de ordem 1: Pij = Nij/Ni .Sob a hipótese de independência temos uma distribuiçãomultinomial, com n.j =

∑i nij observações da categoria com

probabilidade θj . A verossimilhança é:

l(θ) =K−1∑j=0

n.jθj + n.K (1−K−1∑j=0

θj),

a qual é maximizada por θj = N.j/n. Portanto, a estatística darazão de verossimilhança é dada por:

2(

l(P)− l(θ))

= 2∑i,j

Nij logNij/Ni

N.j/n

a qual assintoticamente tem uma distribuição χ2 comK (K + 1)− K = K 2 graus de liberdade. No modelo deSnoqualmie Falls K = 1.

Page 126: Inferência para cadeias de markov

Em Inferência usamos o teste chi-quadrado de Pearson:

X =∑ (Nij − Nip0

ij )2

Nip0ij

Eugen Onegin Queremos testar a hipótese H0 : p01 = p10Os valores esperados para a estatística de Pearson sãocalculados multiplicando-se as somas das linhas(n0,n1) = (8.638; 11.362) pela matriz de transição estimadasob H0:

P =

(0.247 0.7530.753 0.247

)obtendo

(Eij) =

(2131.4 6506.68558.4 2803.6

)

Page 127: Inferência para cadeias de markov

A Estatística chiquadrado para testar a hipóteseuni-dimensional é:

χ2 =∑

ij

(nij − ni p0ij )

2

ni p0ij

= 1217.7.

O valor exato da estatística exata da verossimilhança é 1217.7.(Aproximação excelente!!!)