( PDF ) Análise comparativa de estimadores da ordem de cadeias de markov

Download PDF

ads:

alise Comparativa de Estimadores da Ordem de

Cadeias de Markov

por

Paulo Angelo Alves Resende

Bras

ılia – DF

2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

alise Comparativa de Estimadores da Ordem de

Cadeias de Markov

Dissertac¸

ao apresentada ao Programa de P

os-

Graduac¸

ao em Matem

atica da Universidade

de Bras

ılia (UnB), como requisito parcial

para obtenc¸

ao do grau de MESTRE EM

MATEM

ATICA.

por

Paulo Angelo Alves Resende

Orientador:

atia Regina Gonc¸alves

UNIVERSIDADE DE BRAS

ILIA

INSTITUTO DE CI

ENCIAS EXATAS

DEPARTAMENTO DE MATEM

ATICA

Bras

ılia – DF

2009

ads:

A minha m

ae, Angela Maria.

Resumo

Neste trabalho estudamos o estimador da ordem de cadeias de Markov usando o crit

erio

EDC (Efﬁcient Determination Criterion) com o termo de penalidade

otimo proposto por

Dorea (2008). Realizamos uma an

alise comparativa das performances dos estimadores EDC

opt

BIC e AIC, baseada nos resultados de simulac¸

oes computacionais realizadas.

Abstract

In what follows we study and analyze the Markov chain order estimator EDC (Efﬁcient

Determination Criterion) with the penalty function proposed by Dorea (2008). We also carry

out extensive numerical simulations based on EDC, BIC and AIC, aiming to a detailed com-

parison of their features as well as their relative performance.

Sum

ario

Introduc¸

ao p.7

1 Fundamentac¸

ao Te

orica dos Estimadores p.11

1.1 Descric¸

ao e Breve Hist

orico . . . . . . . . . . . . . . . . . . . . . . . . p.11

1.2 EDC: Consist

encia e Termo de Penalidade

Otimo . . . . . . . . . . . . . p. 17

1.2.1 Notac¸

oes e Resultados Auxiliares . . . . . . . . . . . . . . . . . p.17

1.2.2 Resultados Principais . . . . . . . . . . . . . . . . . . . . . . . . p.30

1.3 Considerac¸

oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.46

2 An

alise Comparativa dos Estimadores p.50

2.1 Deﬁnic¸

ao dos Experimentos Computacionais . . . . . . . . . . . . . . . p.51

2.2 An

alise dos Resultados Obtidos nas Simulac¸

oes . . . . . . . . . . . . . . p.52

2.2.1 O estimador EDC

opt

e mais eﬁciente que o BIC . . . . . . . . . . p.52

2.2.2 Paran suﬁcientemente pequeno, todosos estimadores t

em tend

encia

a subestimar . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.56

2.2.3 Comportamento do estimador AIC . . . . . . . . . . . . . . . . . p.57

2.3 Um Exemplo de Aplicac¸

ao . . . . . . . . . . . . . . . . . . . . . . . . . p.61

Conclus

ao p.63

Refer

encias Bibliogr

aﬁcas p.64

endice A -- Recursos Computacionais Utilizados p.67

A.1 Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.68

A.1.1 Descric¸

ao das Principais Rotinas . . . . . . . . . . . . . . . . . . p.68

A.2 Estimativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.69

A.3 Ambiente Utilizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.70

Introduc¸

Os processos markovianos, em geral, v

em sendo utilizados como modelos aplicados

em diversas

areas, tais como: economia (Silos 2006), geologia (Li 2007), ecologia (Balzter

2000), gen

etica (Nuel 2007), meteorologia (Martell 1999), ci

encia da informac¸

ao (Beno

ıt

2005) e m

usica (McAlpine, Miranda & Hoggar 1999). Uma boa parte dessas aplicac¸

oes

ao tacitamente model

aveis usando Cadeias de Markov de ordem superior com espac¸os de

estados ﬁnitos. Os casos onde os espac¸os de estados n

ao s

ao ﬁnitos s

ao naturalmente aprox-

imados para o caso discreto/ﬁnito em func¸

ao das limitac¸

oes computacionais e a necessidade

de simpliﬁcac¸

ao do modelo.

Em linhas gerais, uma Cadeia de Markov de ordem r caracteriza-se como um processo

em que a informac¸

ao num dado instante depende no m

aximo das informac¸

oes nos r instantes

anteriores.

Neste cen

ario, conhecer a ordem de depend

encia de um certo procedimento tem funda-

mental import

ancia, n

ao apenas para conhecer a depend

encia em si, mas principalmente para

ser poss

ıvel estimar outros par

ametros e encontrar a Cadeia de Markov superior que melhor

se adapta, em certo sentido, ao problema em an

alise. Dessa forma, a quest

ao da estimac¸

da ordem de depend

encia surge como um problema natural e inevit

avel.

Soma-se ao problema de estimac¸

ao da ordem, a limitac¸

ao dos tamanhos das amostras em

algumas aplicac¸

oes, como por exemplo em sequ

encias de tRNA

que possuem comprimento

entre 74 a 95 amino

acidos (Lewin 2004) e em partituras musicais que s

ao limitadas a poucas

aginas.

Bartlett (1951) publicou um dos primeiros trabalhos sobre o problema de estimac¸

da ordem de uma Cadeia de Markov, propondo um teste de hip

oteses para testar a ordem

axima da cadeia. Seguindo a mesma linha, seu trabalho foi generalizado/aperfeic¸oado por

tRNA (Transfer RNA): Respons

avel por transportar amino

acidos para a s

ıntese de prote

ınas.

Hoel (1954), Good (1955), Anderson & Goodman (1957) e Billingsley (1961).

arias alternativas

as t

ecnicas de testes de hip

oteses t

em sido propostas. Tong (1975)

prop

os a aplicac¸

ao do Crit

erio de Informac¸

ao de Akaike (AIC), apresentado por Akaike

(1974) para selec¸

ao de modelos, para a determinac¸

ao da ordem de uma Cadeia de Markov,

com espac¸o de estados ﬁnito e assumindo a exist

encia de um limitante superior conhecido

para a ordem.

Basicamente, Akaike (1974) considerou o problema da selec¸

ao de um modelo, dentre K

modelos poss

ıveis, que melhor se aproxima do modelo verdadeiro e prop

os um novo crit

erio

de informac¸

ao que tem como base a informac¸

ao m

edia de Kullback-Leibler (Kullback 1959)

e a raz

ao de verossimilhanc¸a de Neyman-Pearson (vide Kendall, Stuart & Ord (1991) e Shao

(2007)).

Apesar da indiscut

ıvel import

ancia do trabalho de Akaike (1974) e da utilizac¸

ao do

estimador AIC, como sugerido por Tong (1975), para estimac¸

ao da ordem de cadeias em

modelos de dados meteorol

ogicos por Gates & Tong (1976) e Chin (1977), n

ao se con-

hecia nenhuma demonstrac¸

ao rigorosa sobre as propriedades do procedimento AIC neste

caso. Finalmente Katz (1981) derivou formalmente a distribuic¸

ao assint

otica do estimador

AIC e demonstrou sua inconsist

encia para estimar a ordem de uma Cadeia de Markov.

Nesse mesmo trabalho foi proposto, como alternativa fracamente consistente, um estimador

baseado no Crit

erio de Informac¸

ao Bayesiano (BIC)

, que foi um crit

erio de informac¸

ao cri-

ado por Schwarz (1978) para selec¸

ao de modelos, usando argumentos bayesianos. O crit

erio

proposto, basicamente, foi uma adaptac¸

ao no termo de penalidade do AIC.

Vale ressaltar que, em um trabalho similar ao Katz, Shibata (1976) tamb

em demonstrou

a inconsist

encia do estimador AIC para a ordem de processos auto-regressivos.

Csiszar & Shields (2000) demonstraram a consist

encia forte do estimador BIC sem a

hip

otese que a ordem desconhecida seja limitada.

Simultaneamente, Zhao, Dorea & Gonc¸alves (2001) generalizaram os estimadores AIC

e BIC para a estimac¸

ao da ordem r de uma Cadeia de Markov X =

{

}

com espac¸o de

estados ﬁnito E, apresentando o estimador EDC (Crit

erio de Informac¸

ao Eﬁciente) baseado

na log-verossimilhanc¸a m

axima e com certa liberdade para a escolha do termo de penalidade.

Tamb

em conhecido por Schwarz Information Criterion (SIC).

Especiﬁcamente, de acordo com o crit

erio proposto por Zhao et al, a ordem r

e estimada

por ˆr

EDC

deﬁnido por

ˆr

EDC

= argmin

{

EDC(k);k = 0, . . . , K

}

(1)

EDC(k) = −2log

L(k) +

(k)c

, (2)

onde

L(k)

e a func¸

ao de m

axima verossimilhanc¸a da amostra (X

, . . . , X

) da cadeia X,

{

}

pode ser tomada como uma sequ

encia de n

umeros positivos e

(k) pode ser qualquer func¸

crescente em k.

No caso particular c

= 2,

(k) = |E|

(|E|−1), o estimador EDC reduz-se ao estimador

AIC, proposto por Akaike. No caso c

= log n e

(k) = |E|

(|E|−1) temos o BIC.

Sob a hip

otese da exist

encia de um limitante superior K, conhecido, para a ordem r e

assumindo que a sequ

encia

{

}

satisfaz:

log log n

→ ∞ e

→ 0,

Zhao et al provaram a consist

encia forte do estimador EDC. Como casos particulares,

obtiveram a consist

encia forte do estimador BIC e a inconsist

encia do AIC.

Posteriormente, Lopes (2005) estendeu o EDC para o caso de espac¸o de estados E enu-

mer

avel. Dorea & Lopes (2006) derivaram taxas de converg

encia para o estimador EDC

e Dorea & Zhao (2004) obtiveram limitantes exponenciais para a probabilidade de erro do

estimador EDC.

Com a ampla possibilidade de escolha do termo de penalidade do EDC produzindo esti-

madores consistentes da ordem da cadeia, uma quest

ao natural

e a escolha do melhor termo

de penalidade, ou seja, aquele que produziria um estimador consistente que, de certa forma,

teria maior chance de acerto, ou ainda, a melhor performance.

Dorea (2008) demonstrou a consist

encia forte dos estimadores EDC sem assumir a ex-

ist

encia de um limitante superior ﬁnito, K, da ordem e sob condic¸

oes mais fracas sobre a

sequ

encia

{

}

liminf

n→∞

log log n

≥

2|E|

|E|−1

e lim

n→∞

= 0.

em disso, prop

os como estimador consistente

otimo, dentre a classe (1) considerada,

aquele baseado no crit

erio

EDC

opt

(k) = −2log

L(k) + 2|E|

k+1

log log n . (3)

Ou seja, prop

os a escolha de

(k) = |E|

(|E|−1) e c

2|E|

|E|−1

log log n em (2).

Dorea mostrou teoricamente que a escolha do termo de penalidade em (3) produz um esti-

mador consistente melhor do que o BIC.

Nosso interesse neste trabalho

e fazer uma an

alise comparativa da performance desses

estimadores atrav

es de simulac¸

oes num

ericas.

Inicialmente, no Cap

ıtulo 1, apresentamos um breve hist

orico, uma descric¸

ao mais minu-

ciosa dos estimadores e estudamos em detalhes o trabalho de Dorea (2008), que nos auxiliar

na an

alise da performance dos estimadores.

No Cap

ıtulo 2 descrevemos primeiramente os experimentos computacionais realizados

com o objetivo de comparar a eﬁci

encia dos estimadores consistentes EDC

opt

e BIC, e de

analisar a performance do estimador n

ao consistente AIC. Em seguida, apresentamos uma

discuss

ao, pautada na teoria estudada, sobre os resultados obtidos nas simulac¸

oes, onde veri-

ﬁcamos principalmente que o estimador

otimo EDC

opt

apresenta uma performance substan-

cialmente melhor que o BIC, e essa vantagem aumenta em func¸

ao da complexidade do mod-

elo considerado. Encerramos o cap

ıtulo, com a aplicac¸

ao desses estimadores, num cen

ario

real, na an

alise de uma pec¸a musical.

Finalmente, apresentamos nossas conclus

oes sobre o trabalho realizado.

As informac¸

oes sobre o programa computacional desenvolvido para as simulac¸

oes, tais

como ferramentas, linguagens e descric¸

ao de rotinas relevantes, est

ao no Ap

endice A.

1 Fundamentac¸

ao Te

orica dos

Estimadores

Neste cap

ıtulo n

os consideramos a classe de estimadores EDC (Crit

erio de Informac¸

Eﬁciente) da ordem de Cadeias de Markov, com espac¸o de estados ﬁnito, baseados na log-

verossimilhanc¸a m

axima penalizada, que foi proposta por Zhao, Dorea & Gonc¸alves (2001)

e que generaliza os estimadores cl

assicos AIC e BIC.

Na sec¸

ao 1.1 apresentamos um breve hist

orico e uma descric¸

ao desses estimadores.

Na sec¸

ao 1.2 estudamos em detalhes o trabalho de Dorea (2008), onde a consist

encia

forte desses estimadores

e demonstrada sob condic¸

oes mais suaves do que as assumidas em

Zhao, Dorea & Gonc¸alves (2001) e um termo de penalidade

otimo

e proposto de tal forma a

obter um estimador fortemente consistente de melhor performance.

1.1 Descric¸

ao e Breve Hist

orico

Considere uma Cadeia de Markov X =

{

}

n≥1

, de ordem desconhecida r, com espac¸o

de estados E =

{

1, 2, . . . , N

}

e probabilidades de transic¸

p(a

r+1

) = P(X

n+1

= a

r+1

n−r+1

= a

) = P(X

n+1

= a

r+1

n−r+1

= a

, . . . , X

= a

(1.1)

onde consideramos a notac¸

= a

= (a

, . . . , a

), se 1 ≤k ≤ r.

Dada uma certa amostra X

= (X

, . . . , X

) desta cadeia, o problema consiste em deter-

minar a ordem r do processo, baseado nesta amostra.

Como hip

otese inicial, assume-se a exist

encia de um limitante superior conhecido para

r, isto

existe K (conhecido) tal que 0 ≤r ≤ K. (1.2)

Inicialmente, assumindo (1.2), foi proposto por Bartlett (1951) e Hoel (1954), utilizar

testes de hip

oteses para a determinac¸

ao da ordem da cadeia.

O teste proposto por Bartlett testa a hip

otese de que a cadeia tenha ordem m

axima k,

enquanto que Hoel testa a hip

otese de que a Cadeia de Markov em quest

ao tenha ordem

axima k−1 contra a hip

otese de que a cadeia tenha ordem m

axima k.

O teste de Hoel

e baseado na estat

ıstica da raz

ao de verossimilhanc¸a de Neyman-Pearson

(vide, por exemplo, Shao (2007)) para testar hip

oteses compostas:

L(k−1)

L(k)

onde

L(k)

e a m

axima verossimilhanc¸a estimada considerando verdadeira a hip

otese r = k,

dada por:

L(k) =

∏

k+1

ˆp(a

k+1

)

N(a

k+1

)

, (1.3)

assumindo 0

= 1, e

N(a

) =

j=n−k+1

∑

j=1

1(X

= a

, . . . , X

j+k−1

= a

). (1.4)

Na sequ

encia, ˆp(a

k+1

)

e o estimador de m

axima verossimilhanc¸a de (1.1). Usando

a semelhanc¸a de (1.3) com o modelo multinomial (Anderson & Goodman 1957), ou uma

simples veriﬁcac¸

ao usando multiplicadores de Lagrange (Billingsley 1961), obt

em-se

ˆp(a

k+1

) =

N(a

k+1

)

N(a

)

. (1.5)

Hoel (1954), supondo verdadeira a hip

otese nula H

: r = k−1, veriﬁcou que

−2log(

) ∼

(|E|

k−1

(|E|−1)

). (1.6)

Isto

e, −2log(

) possui uma distribuic¸

ao assint

otica qui-quadrado com |E|

k−1

(|E|−1)

graus de liberdade, onde |E|

e a cardinalidade do conjunto E. Para isso, utilizou a aproximac¸

normal para distribuic¸

oes multinomiais.

Tong (1975) prop

oe a aplicac¸

ao do Crit

erio de Informac¸

ao de Akaike (AIC), apresentado

por Akaike (1974) para selec¸

ao de modelos, para a determinac¸

ao da ordem de uma Cadeia

de Markov com espac¸o de estados ﬁnito.

Em linhas gerais, em seu trabalho, Akaike questiona a utilidade pr

atica dos procedimen-

tos de testes de hip

oteses como m

etodos para a construc¸

ao ou identiﬁcac¸

ao de um modelo

estat

ıstico. Considerando o problema da selec¸

ao de um dos modelos M

, . . . , M

que melhor

se aproxima do modelo verdadeiro M

, Akaike prop

oe um novo crit

erio de informac¸

ao que

tem como base a informac¸

ao m

edia de Kullback-Leibler (Kullback & Leibler (1951) e Kull-

back (1959)). Para a estimac¸

ao desta diverg

encia s

ao utilizadas as propriedades assint

oticas

da raz

ao de verossimilhanc¸a de Neyman-Pearson para testar hip

oteses compostas e de esti-

madores de m

axima verossimilhanc¸a (vide Billingsley (1961), Kendall, Stuart & Ord (1991)

ou Rao (1973)).

Conforme sugerido por Tong (1975) e seguindo Lopes (2005), o problema de estimac¸

da ordem de uma Cadeia de Markov de ordem desconhecida r, com espac¸o de estados

ﬁnito e assumindo a hip

otese (1.2), pode ser inserido no contexto de selec¸

ao de mode-

los da seguinte forma: denota-se por M

a classe de processos estoc

asticos X =

{

}

n≥1

com espac¸o de estados E =

{

1, 2, . . . , N

}

, para o qual existe k ≥ 1 tal que para todo n ≥ k

P(X

= a

, . . . , X

n−1

= a

n−1

, X

= a

) = P(X

= a

, . . . , X

= a

)

n−k

∏

j=1

j+1

...a

j+k−1

j+k

, para

a matriz de transic¸

ao apropriada P=



...a

k+1



, onde p

...a

k+1

= p

k+1

= p(a

k+1

como denotado em (1.1). A classe de processos i.i.d.

e denotada por M

Desta maneira, a ordem de uma cadeia X =

{

}

n≥1

em M = ∪

e o menor inteiro r

tal que, para algum l ≥ 1, X =

{

}

n≥l

est

a em M

Baseado numa amostra X

= (X

, . . . , X

) de uma cadeia X =

{

}

de ordem descon-

hecida r, pode-se estimar r selecionando-se a classe do modelo M

ˆr

em M = ∪

que melhor

se ajusta

a M

Assumindo (1.2), ou seja, r ≤ K (K conhecido), e admitindo que cada hip

otese H

{

a cadeia de Markov ´e de ordem k

}

represente o modelo M

, com matriz P =



k+1



associada, deseja-se, ent

ao, selecionar sobre M =

{

, M

, . . . , M

}

o modelo M

ˆr

que melhor

se ajusta a M

Sob a hip

otese H

, com k = 0, 1, . . . , K, a func¸

ao de m

axima verossimilhanc¸a

e dada por

(1.3), (1.4) e (1.5), ou seja,

L(k) =

∏

k+1



N(a

k+1

)

N(a

)



N(a

k+1

)

onde N(a

), dado em (1.4), representao n

umero de ocorr

encias de a

na amostra (X

, . . . , X

)

e no caso k = 0 interpreta-se N(a

) = n.

Assim, baseado nesta estat

ıstica, o Crit

erio de Informac¸

ao de Akaike, utilizado por Tong

(1975) para selecionar a ordem que melhor se ajusta

a ordem verdadeira r da cadeia

AIC(k) = −2log

L(k) + 2

(k), (1.7)

onde

(k) = |E|

(|E|−1)

e o n

umero de par

ametros livres a serem estimados em H

. A

estimativa ˆr de r

e aquela que minimiza AIC(k), dentre k = 0, 1, . . . , K, ou seja,

ˆr

AIC

= argmin

{

AIC(k);k = 0, 1, . . . , K

}

. (1.8)

Uma fundamentac¸

ao mais detalhada dos trabalhos de Akaike e Tong pode ser encontrada

em Lopes (2005).

Posteriormente, Katz (1981) obteve a distribuic¸

ao assint

otica do estimador AIC e mostrou

sua inconsist

encia para a estimac¸

ao da ordem da cadeia, com a exist

encia de uma probabil-

idade positiva de superestimar a ordem. Como uma alternativa ao procedimento AIC, Katz

sugere o uso do Crit

erio de Informac¸

ao Bayesiano (BIC) proposto por Schwarz (1978) para

a estimac¸

ao da dimens

ao de um modelo.

O estimador BIC da ordem r de uma Cadeia de Markov X, sob a hip

otese (1.2) e baseado

numa amostra X

= (X

, . . . , X

), pode ser descrito como

ˆr

BIC

= argmin

{

BIC(k);k = 0, 1, . . . , K

}

onde

BIC(k) = −2log

L(k) +

(k)log n ,

com

L(k) e

(k) deﬁnidos como no crit

erio AIC.

Com a substituic¸

ao da constante 2, no termo de penalidade do AIC em (1.7), pelo fator

log n, que depende do tamanho da amostra e converge ao inﬁnito a uma taxa suﬁciente-

mente lenta, foi poss

ıvel obter a consist

encia fraca do estimador ˆr

BIC

, demonstrada por Katz

(1981). No entanto, foi apontado por Katz, atrav

es de alguns experimentos computacionais

modestos, a tend

encia do estimador BIC de subestimar a ordem da cadeia.

Mesmo depois dos trabalhos de Schwarz (1978) e Katz (1981), ﬁcaram duas quest

oes

em aberto – a consist

encia forte do BIC e a possibilidade de se obter termos de penalidade

“melhores”. Csiszar & Shields (2000) responderam a primeira quest

ao apresentando uma

demonstrac¸

ao da consist

encia forte do estimador BIC, sem assumir a priori a exist

encia

de um limitante superior da ordem [hip

otese (1.2)], mas deixaram explicitamente a se-

gunda quest

ao em aberto: “it remains open whether smaller penalty terms sufﬁce for consis-

tency...”.

Paralelamente, Zhao, Dorea & Gonc¸alves (2001), propuseram o estimador EDC (Efﬁ-

cient Determination Criterion) com uma certa liberdade para a escolha do termo de penali-

dade e inclu

ındo como casos particulares os estimadores AIC e BIC. Especiﬁcamente, r ser

estimado por ˆr

EDC

, a estimativa m

ınima de EDC, ou seja,

ˆr = argmin

{

EDC(k);k = 0, . . . , K

}

, (1.9)

onde

EDC(k) = −2log

L(k) +

(k)c

, (1.10)

com c

podendo ser tomada como uma sequ

encia de n

umeros positivos dependendo de n

(ou, mais geral, como uma sequ

encia de vari

aveis aleat

orias positivas) e

(k) podendo ser

tomada como qualquer func¸

ao crescente em k.

Nos casos particulares: c

= 2,

(k) = |E|

(|E|−1) e c

= log n,

(k) = |E|

(|E|−1)

temos os crit

erios AIC e BIC respectivamente.

Zhao, Dorea & Gonc¸alves (2001) provaram a consist

encia forte do estimador ˆr

EDC

para

estimar a ordem r de uma Cadeia de Markov X =

{

}

, cujo processo derivado



(k)

= (X

, . . . , X

n+k−1

)



k≥1

e irredut

ıvel e recorrente positivo, assumindo a hip

otese (1.2) e sob as seguintes condic¸

oes

para a sequ

encia

{

}

no termo de penalidade:

log log n

→ ∞ e

→ 0. (1.11)

Em particular, obtiveram a consist

encia forte de ˆr

BIC

em disso, observaram que se ao inv

es de (1.11) assumirmos que

{

}

e uniformemente

limitada por uma constante, ent

ao ˆr

EDC

e inconsistente. Este

e o caso do estimador ˆr

AIC

Com isso, qualquer c

satisfazendo as condic¸

oes em (1.11), d

a origem a um estimador

fortemente consistente. Dessa forma,

e natural pensar em qual “c

” fornece o estimador com

maior chance de acerto.

Recentemente, Dorea (2008), considerando

(k) = |E|

(|E|−1), prop

os o seguinte

termo de penalidade como sendo

otimo dentro dessa classe de estimadores consistentes:

−1

log log n .

em disso, Dorea (2008) demonstrou, sob algumas condic¸

oes de regularidade sobre

X, a consist

encia forte do estimador EDC sem a hip

otese (1.2) de limitac¸

ao da ordem e

assumindo as seguintes hip

oteses (mais fracas) sobre c

liminf

n→∞

log log n

≥

2|E|

|E|−1

e limsup

n→∞

= 0.

Em particular, Dorea apresentou uma prova alternativa a de Csisz

ar-Shields (2000) para

a consist

encia forte do estimador BIC sem a limitac¸

ao (1.2).

1.2 EDC: Consist

encia e Termo de Penalidade

Otimo

Nesta sec¸

ao, consideramos a classe de estimadores EDC, dados por (1.9) e (1.10), com

(k) = |E|

(|E|−1) e c

> 0 uma sequ

encia de constantes, proposto por Zhao, Dorea &

Gonc¸alves (2001) e que generaliza os estimadores AIC e BIC.

Como mencionamos no ﬁnal da sec¸

ao anterior, Dorea (2008) abordaa quest

ao da escolha

do termo de penalidade

otimo e ainda demonstra a consist

encia forte do estimador EDC, sob

condic¸

oes suaves de regularidade, sem a hip

otese (1.2). A seguir apresentamos um estudo

detalhado de seu trabalho.

1.2.1 Notac¸

oes e Resultados Auxiliares

Suponha X =

{

}

n≥1

, uma Cadeia de Markov de ordem r, com probabilidades de

transic¸

p(a

r+1

) = P(X

n+1

= a

r+1

n−r+1

= a

). (1.12)

Para k ≥ r, considere o processo Y

(k)



(k)



n≥1

, com Y

(k)

= (X

, . . . , X

n+k−1

) ∈ E

Considerando A

= (a

i,1

, . . . , a

i,k

) ∈ E

, temos que

P(Y

(k)

n+1

= A

n+1

(k)

= A

, . . . ,Y

(k)

= A

) =

= P( (X

n+1

, . . . , X

n+k

) = (a

n+1,1

, . . . , a

n+1,k

, . . . , X

n+k−1

) = (a

n,1

, . . . , a

n,k

), . . . , (X

, . . . , X

k−1

) = (a

1,1

, . . . , a

1,k

)).

Considerando apenas os casos poss

ıveis, isto

e, a

i, j

= a

i−1, j+1

, e denotando a

i+ j−1

= a

i, j

ent

P(Y

(k)

n+1

= A

n+1

(k)

= A

, . . . ,Y

(k)

= A

) =

= P(X

n+1

= a

n+1

= a

)

= P(X

n+1

= a

n+1

n−r+1

= a

n−r+1

)

= P(X

n+1

n−r+2

= a

n+1

n−r+2

n−r+1

= a

n−r+1

)

= P(Y

(k)

n+1

= A

n+1

(k)

= A

Assim, conclu

ımos que Y

(k)

e uma Cadeia de Markov homog

enea de primeira ordem,

com probabilidades de transic¸

P(Y

(k)

n+1

= a

k+1

(k)

= a

) = p(a

k+1

) = p(a

k+1

k−r+1

). (1.13)

Assim, se X =

{

}

n≥1

e uma Cadeia de Markov de ordem r e espac¸o de estados

E, ent

ao, para k ≥ r o processo Y

(k)



(k)



n≥1

, onde Y

(k)

= (X

, . . . , X

n+k−1

) ∈ E

chamado Cadeia de Markov k-derivada de X.

Podemos induzir a recorr

encia e aperiodicidade nas cadeias derivadas da seguinte forma:

Proposic¸

ao 1.1. Se as probabilidades de transic¸

ao da Cadeia de Markov X, de ordem r,

ao estritamente positivas e k ≥r, ent

ao a cadeia k-derivada Y

(k)

e irredut

ıvel e aperi

odica.

Consequentemente, erg

odica.

Demonstrac¸

ao. Como o espac¸o de estados, E, de X

e ﬁnito, temos que o espac¸o de estados

da cadeia k-derivada, E

, tamb

e ﬁnito. Por outro lado, para quaisquer dois estados a

(k)

Supostamente, Doob foi o primeiro a sugerir essa adaptac¸

ao em Doob (1966) p

aginas 89 e 185.

e b

(k)

= b

, temos por (1.13)

P(Y

(k)

= a

, . . . ,Y

(k)

= a

k−1

(k)

k+1

= b

(k)

= a

)

= p( b

) ····· p(b

k−1

)



p(b

). . . p(b

r−1

) > 0, para k = r

p(b

k−r+1

). . . p(b

k−1

k−r

) > 0, para k > r.

Assim, todos os estados se comunicam e portanto a Cadeia de Markov

e irredut

ıvel.

Como o espac¸o de estados

e ﬁnito, segue que ela

e recorrente positiva e portanto erg

odica

(vide, por exemplo, Kannan (1979)).

em disso, para todo a ∈ E, A = (a, a, . . . , a), temos que P(Y

(k)

n+1

= A|Y

(k)

= A) > 0,

usando a irredutibilidade, conclu

ımos que Y

(k)

e aperi

odica.

Vale observar que a rec

ıproca da proposic¸

ao anterior n

e verdadeira.

Uma quest

ao natural

e a relac¸

ao entre as cadeias derivadas de X. Quanto a ergodicidade,

podemos ter:

Proposic¸

ao 1.2. Se a cadeia k-derivada de X

e erg

odica, com distribuic¸

ao de equil

ıbrio

(estacion

aria)

), ent

ao a cadeia (k+1)-derivada possui distribuic¸

ao estacion

aria dada

por

k+1

) =

)p(a

k+1

k−r+1

). (1.14)

Demonstrac¸

ao. Como por hip

oteseY

(k)

possui a distribuic¸

ao de equil

ıbrio e estacion

aria

ent

ao temos

) =

∑

)p(a

)

(vide, por exemplo, Kannan (1979)).

Como p(a

) = 0 para a

k−1

= b

) =

∑

k−1

)p(a

k−1

)

∑

k−1

)p(a

k−1

). (1.15)

Para a Cadeia de Markov (k+ 1)-derivada deﬁnimos

k+1

) =

)p(a

k+1

). (1.16)

Ent

ao, substituindo (1.15) em (1.16), temos

k+1

) =

∑

k−1

)p(a

k−1

)p(a

k+1

). (1.17)

ı novamente, aplicando (1.16) em (1.17), com um ajuste nos sub-

ındices, obtemos

k+1

) =

∑

k−1

)p(a

k−1

)p(a

k+1

)

∑

k+1

)p(a

k+1

)

∑

k+1

)p(a

k+1

Logo

k+1

dada por (1.14)

e uma distribuic¸

ao estacion

aria para Y

(k+1)

Para simpliﬁcar a notac¸

ao, vamos utilizar

) =

) e

k+l

) =

k+l

Note que esta notac¸

ao est

a bem deﬁnida pois, atrav

es do dom

ınio,

e poss

ıvel fazer a

distinc¸

ao entre as distribuic¸

oes.

Por induc¸

ao, temos:

Corol

ario 1.3. Se a cadeia r-derivada de X

e erg

odica ent

ao, para l > r, a k-derivada de X

possui distribuic¸

ao estacion

aria dada por

) =

)p(a

r+1

). . . p(a

k−1

k−r

). (1.18)

Das proposic¸

oes 1.1 e 1.2 segue:

Corol

ario 1.4. Se X

e uma Cadeia de Markov, de ordem r, cujas probabilidades de transic¸

ao estritamente positivas, ou seja, p(a

r+1

) > 0, ∀ a

r+1

∈ E

r+1

, ent

ao para todo k ≥ r

a cadeia Y

(k)

possui distribuic¸

ao de equil

ıbrio (estacion

aria) dada por (1.18), onde

)

indica a distribuic¸

ao de equil

ıbrio de Y

(r)

Intuitivamente vemos que uma cadeia de ordem r pode ser modelada por uma cadeia de

ordem k > r sem qualquer perda. Esse resultado (Corol

ario 1.4) mostra que a ergodicidade

e preservada neste caso.

O Lema abaixo

e necess

ario para detalhar os resultados de Dorea (2008). Embora seja

um resultado simples,

e de grande import

ancia, pois com ele

e poss

ıvel relacionar as diversas

formas de contagem de uma determinada sequ

encia de eventos.

Lema 1.5. Considerando a notac¸

ao N(a

) = N(a

), deﬁnida em (1.4), temos que

N(a

) =

∑

N(a

) + 1(X

= a

, . . . , X

= a

)

N(a

) =

∑

k+1

N(a

k+1

) + 1(X

n−k+1

= a

, . . . , X

= a

). (1.19)

Mais ainda, se l > 0, por induc¸

ao segue que:

N(a

) =

∑

1−l

N(a

1−l

) +

l−1

∑

i=0

∑

−i

1(X

i+k+1

= a

−i

)

N(a

) =

∑

k+l

k+1

N(a

k+l

k+1

) +

l−1

∑

i=0

∑

k+1+i

k+1

1(X

n−k−i

= a

k+1+i

k+1

). (1.20)

Demonstrac¸

ao. Usando a deﬁnic¸

ao de N(a

)

N(a

) =

j=n−k+1

∑

j=1

1(X

= a

, . . . , X

j+k−1

= a

)



j=n−k+1

∑

j=2

∑

1(X

j−1

= a

, X

= a

, . . . , X

j+k−1

= a

)



+ 1(X

= a

, . . . , X

= a

)



∑

i=n−k

∑

i=1

1(X

= a

, X

i+1

= a

, . . . , X

i+k

= a

)



+ 1(X

= a

, . . . , X

= a

)



∑

N(a

)



+ 1(X

= a

, . . . , X

= a

Analogamente,

N(a

) =

j=n−k+1

∑

j=1

1(X

= a

, . . . , X

j+k−1

= a

)



j=n−k

∑

j=1

∑

k+1

1(X

= a

, . . . , X

j+k−1

= a

, X

j+k

= a

k+1

)



+ 1(X

n−k+1

= a

, . . . , X

= a

)



∑

k+1

j=n−k

∑

j=1

1(X

= a

, . . . , X

j+k−1

= a

, X

j+k

= a

k+1

)



+ 1(X

n−k+1

= a

, . . . , X

= a

)



∑

k+1

N(a

k+1

)



+ 1(X

n−k+1

= a

, . . . , X

= a

Em resultados subsequentes, tamb

em vamos utilizar a seguinte adaptac¸

ao da desigual-

dade das m

edias.

Lema 1.6 (Desigualdade das M

edias). Supondo a

> 0 e e

> 0, i = 1..l, ent

∑

i=1

≤

∑







∏

i=1

≤

∑

i=1

∑

Nas demonstrac¸

oes dos resultados da pr

oxima sub-sec¸

ao, vamos precisar de algumas

relac¸

oes da func¸

ao verossimilhanc¸a. Essas relac¸

oes est

ao intimamente ligadas aos resultados

apresentados, pois tratam do comportamento local de L e

Lema 1.7. Seja X uma Cadeia de Markov de ordem r com probabilidades de transic¸

dadas em (1.12). Ent

(a) para k ≥ r, log L(k+ 1) = log L(k) + o(

) e log L(k+ 1) = log L(r) + o(

);

(b) log

L(k) =

∑

l+1

N(a

l+1

)log

N(a

l+1

1+l−k

)

N(a

1+l−k

)

+ o(

) para todo l ≥0 e 0 ≤ k < l;

(c)

L(k+ 1) ≥

L(k) + o(

), k ≥0,

onde L(k)

e a func¸

ao verossimilhanc¸ade X supondo a ordem k e

e a m

axima verossimilhanc¸a,

como deﬁnida em (1.3). Al

em disso, o(

) signiﬁca que

)

→0 sempre que

→∞. Neste

caso, o(

)

e limitado em n.

Demonstrac¸

ao. (a) Por deﬁnic¸

L(k+ 1) =

∏

k+2

p(b

k+2

k+1

)

N(b

k+2

)

. (1.21)

Como k ≥r, temos que p(b

k+2

k+1

) = p(b

k+2

k+1

) e substituindo em (1.21) obtemos

L(k+ 1) =

∏

k+2

p(b

k+2

k+1

)

N(b

k+2

)

Agrupando adequadamente e usando o Lema 1.5 obtemos

L(k+ 1) =

∏

k+2

p(b

k+2

k+1

)

∑

N(b

k+2

)

∏

k+2

p(b

k+2

k+1

)

N(b

k+2

)−1(b

k+2

k+1

)





∏

k+2

p(b

k+2

k+1

)

N(b

k+2

)









∏

k+2

p(b

k+2

k+1

)

−1(b

k+2

k+1

)





. (1.22)

Chamando

o segundo fator do

ultimo membro de (1.22) e usando a deﬁnic¸

ao de L(k)

obtemos

L(k+ 1) = L(k) ·

Tomando logaritmo e considerando que

ao depende de n temos

log L(k+ 1) = log L(k) + o(

(b) Por (1.3) e (1.5) temos

L(k) =

∏

k+1



N(b

k+1

)

N(b

)



N(b

k+1

)

e pelo Lema 1.5, segue

L(k) =

∏

k+1



N(b

k+1

)

N(b

)



∑

−(l−k)+1

N(b

−(l−k)+1

l−1

∑

i=0

∑

−i

1(b

−i

i+k+1

)

Considerando a

l+1

= b

k+1

−(l−k)+1

∑∑

1(b

−i

= X

i+k+1

) = c(a

l+1

), temos

L(k) =

∏

l+1



N(a

l+1

1+l−k

)

N(a

1+l−k

)



N(a

l+1

)

∏

l+1



N(a

l+1

1+l−k

)

N(a

1+l−k

)



c(a

l+1

)

. (1.23)

Chamando o segundo fator em (1.23) de

e tomando logaritmo, obtemos

log

L(k) =

∑

l+1

N(a

l+1

)log

N(a

l+1

1+l−k

)

N(a

1+l−k

)

+ o(

L(k+ 1) ≥

L(k) + o(

), seguiremos as ideias da demonstrac¸

ao do

Teorema 1 de Dorea & Zhao (2004), p

aginas 3689-3697.

Para k ≥ 0, temos

log

L(k+ 1) =

∑

k+2

log N(a

k+2

)

N(a

k+2

)

N(a

k+1

)

Como por (1.19) N(a

k+1

) =

∑

k+2

N(a

k+2

) + 1(X

n−k

= a

, . . . , X

= a

k+1

log

L(k) =

∑

k+1

log N(a

k+1

)

N(a

k+1

)

N(a

)

∑

k+2

log N(a

k+2

)

N(a

k+2

)

N(a

k+1

)

+ o(

ı segue

log

L(k) −log

L(k+ 1) =

∑

k+2

N(a

k+2

)log



N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



+ o(

)

∑

k+2

N(a

k+1

)

N(a

k+2

)

N(a

k+1

)

log



N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



+ o(

)

∑

k+1

N(a

k+1

)

∑

k+2

N(a

k+2

)

N(a

k+1

)

log



N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



+ o(

Note que

∑

k+2

N(a

k+2

)

N(a

k+1

)

< ∞. Assim, usando a desigualdade de Jensen temos:

∑

k+2

N(a

k+2

)

N(a

k+1

)

log



N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



+ o(

)

≤ log



∑

k+2

N(a

k+2

)

N(a

k+1

)

N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



+ o(

)

≤ log



∑

k+2

N(a

k+2

)

N(a

k+1

)



+ o(

)

≤ log 1 + o(

) = o(

Assim, conclu

ımos que

log

L(k) −log

L(k+ 1) ≤ o(

Observac¸

ao 1.8. Como

L(k) depende apenas da amostra, que

e conhecida, podemos deter-

minar melhor seu comportamento. Nesse sentido, o item (c) do Lema anterior pode ser mais

espec

ıﬁco:

L(k+ 1) ≥

L(k)

Demonstrac¸

ao. Pela deﬁnic¸

ao e pela demonstrac¸

ao do item (b) do lema, temos respectiva-

mente

L(k+ 1) =

∏

k+2



N(a

k+2

)

N(a

k+1

)



N(a

k+2

)

(1.24)

L(k) =

∏

k+1



N(b

k+1

)

N(b

)



N(b

k+1

)

∏

k+1



N(b

k+1

)

N(b

)



∑

[

N(b

k+1

)+1(X

k+1

)

]

∏

k+1



N(b

k+1

)

N(b

)



N(b

k+1

)

∏

k+1



N(b

k+1

)

N(b

)



1(X

k+1

)

∏

k+2



N(a

k+2

)

N(a

k+1

)



N(a

k+2

)



N(X

k+1

)

N(X

)



. (1.25)

Para mostrar o desejado, basta obter

L(k+1)

L(k)

≥ 1. Usando (1.24) e (1.25), temos

L(k+ 1)

L(k)

∏

k+2



N(a

k+2

)

N(a

k+1

)

N(a

k+1

)

N(a

k+2

)



N(a

k+2

)



N(X

)

N(X

k+1

)



Usando o Lema 1.6, segue

L(k+ 1)

L(k)

≥













∑

k+2

N(a

k+2

)



+ 1

∑

k+2



N(a

k+2

)

N(a

k+1

)N(a

k+2

)

N(a

k+2

)N(a

k+1

)



N(X

k+1

)

N(X

)















∑

k+2

N(a

k+2

)





. (1.26)

Para o numerador (e expoente) do segundo membro de (1.26), usando o Lema 1.5, temos





∑

k+2

N(a

k+2

)





+ 1 =

∑

k+1

∑

k+2

N(a

k+1

k+2

) + 1

∑

k+1



N(a

k+1

) −1(X

n−k

= a

k+1

)



+ 1

∑

k+1

N(a

k+1

) −1+ 1

∑

k+1

N(a

k+1

). (1.27)

Da mesma forma para o denominador, obtemos





∑

k+2

N(a

k+2

)

N(a

k+1

)N(a

k+2

)

N(a

k+2

)N(a

k+1

)





N(X

k+1

)

N(X

)





∑

k+2

N(a

k+1

)N(a

k+2

)

N(a

k+1

)





N(X

k+1

)

N(X

)

∑

k+2

N(a

k+2

)

N(a

k+1

)

∑

N(a

k+1

) +

N(X

k+1

)

N(X

)

∑

k+2

N(a

k+2

)

N(a

k+1

)



N(a

k+1

) −1(X

= a

k+1

)



N(X

k+1

)

N(X

)

∑

k+2

N(a

k+2

) −

∑

k+2

1(X

= a

k+1

)

N(a

k+2

)

N(a

k+1

)

N(X

k+1

)

N(X

)

∑

k+2

N(a

k+2

) −

∑

k+2=X

k+1

N(X

k+2

)

N(X

)

−

N(X

k+1

)

N(X

)

N(X

k+1

)

N(X

)

∑

k+2

N(a

k+2

) −

∑

k+2=X

k+1

N(X

k+2

)

N(X

)

. (1.28)

Aplicando (1.28) e (1.27) em (1.26), segue

L(k+ 1)

L(k)

≥







∑

k+1

N(a

k+1

)

∑

k+2

N(a

k+2

) −

∑

k+2=X

k+1

N(X

k+2

)

N(X

)







∑

k+1

N(a

k+1

)

≥ 1.

Tamb

em ser

ao utilizados os pr

oximos tr

es teoremas, o primeiro pode ser encontrado em

Dacunha-Castelle, Duﬂo & McHale (1986) e os outros em Meyn & Tweedie (1993).

Teorema 1.9 (Lei Forte dos Grandes N

umeros). Suponha Z uma Cadeia de Markov irre-

dut

ıvel, recorrente positiva, com espac¸o de estados ﬁnito E e distribuic¸

ao estacion

aria

Considere ainda f : E → R e g : E → (0, ∞) cont

ınuas, ent

∑

f(Z

)

∑

g(Z

)

→

q.c.

( f(Z

))

(g(Z

))

Teorema 1.10 (Teorema do Limite Central). Se Z

e uma Cadeia de Markov erg

odica com

espac¸o de estados ﬁnito E e distribuic¸

ao estacion

aria

, g : E → R, S

(g) =

∑

j=1

g(Z

) e

= E

)) + 2

∑

j=2

(g(Z

)g(Z

)) > 0, ent

(g) −E

(g))



→

N (0, 1).

Teorema 1.11 (Lei do Logaritmos Iterado). Se Z

e uma Cadeia de Markov erg

odica com

espac¸o de estados ﬁnito E e distribuic¸

ao estacion

aria

, g : E → R, S

(g) =

∑

j=1

g(Z

) e

= E

)) + 2

∑

j=2

(g(Z

)g(Z

)), ent

(a) Se

= 0, quase certamente

lim

n→∞

√

(g) −E

(g))] = 0.

(b) Se

> 0, quase certamente

limsup

n→∞

(g) −E

(g))



nlog log n

= 1

liminf

n→∞

(g) −E

(g))



nlog log n

= −1.

1.2.2 Resultados Principais

Daqui para frente, vamos assumir que X

e uma Cadeia de Markov de ordem r, com

espac¸os de estados E ﬁnito, |E| ≥ 2 e probabilidades de transic¸

ao estritamente positivas, ou

seja,

p(a

r+1

) > 0, ∀a

r+1

= (a

, . . . , a

r+1

) ∈ E

r+1

. (1.29)

Lembremos que pelas proposic¸

oes 1.1, 1.2 e corol

arios 1.3 e 1.4, segue que as cadeias

k-derivadas Y

(k)

, k ≥ r, s

ao irredut

ıveis e erg

odicas e se

)

e a distribuic¸

ao de equil

ıbrio

estacion

aria para a cadeia r-derivadaY

(r)

, ent

ao para k > r a k-derivadaY

(k)

tem distribuic¸

estacion

aria

) =

) dada por (1.18), ou seja,

) =

)p(a

r+1

). . . p(a

k−1

k−r

Lema 1.12. Se X

e uma Cadeia de Markov de ordem r satisfazendo (1.29) ent

ao, ∀ k ≥ r e

∀ a

k+1

∈ E

k+1

, temos

limsup

n→∞



N(a

k+1

) −N(a

)p(a

k+1

)



nlog log n

= 2

k+1

)(1− p(a

k+1

)) (1.30)

quase certamente. Onde

k+1

)

e a distribuic¸

ao estacion

aria da cadeia k-derivada Y

(k)

Demonstrac¸

ao. Considere

g(Y

(k+1)

) = 1(Y

(k+1)

= a

k+1

) −1(Y

(k)

= a

)p(a

+ 1|a

) (1.31)

n−k

(g) =

n−k

∑

j=1

g(Y

(k+1)

Usando a deﬁnic¸

ao de N(a

) e g, obtemos

n−k

(g) = N(a

k+1

) −N(a

)p(a

k+1

) + 1(Y

(k)

n−k+1

= a

n−k+1

)p(a

k+1

)

= N(a

k+1

) −N(a

)p(a

k+1

) + o(

). (1.32)

Indicando por E

a esperanc¸a relativo

a distribuic¸

ao estacion

aria

, ent

ao de (1.31) e

(1.18)

(g(Y

(k+1)

)) =

k+1

) −

)p(a

k+1

)

= 0 ,

e da

n−k

) = 0. (1.33)

Da mesma forma, temos de (1.31) e (1.18)

(k+1)

)) =

k+1

)(1− p(a

k+1

))

)(1− p(a

k+1

))p(a

k+1

)

k+1

)(1− p(a

k+1

))



(1− p(a

k+1

)) + p(a

k+1

)



k+1

)(1− p(a

k+1

)). (1.34)

Paracalcular E(g(Y

(k+1)

)·g(Y

(k+1)

)) com j > 1, consideremos F

j+k−1

, . . . , X

j+k−1

ent

ao, como Y

(k+1)

e F

j+k−1

-mensur

avel, temos



g(Y

(k+1)

) ·g(Y

(k+1)

)



= E



E(g(Y

(k+1)

) ·g(Y

(k+1)

)|F

j+k−1

)



= E



g(Y

(k+1)



1(Y

(k+1)

= a

k+1

) −1(Y

(k)

= a

)p(a

k+1

)|F

j+k−1



.(1.35)

Mas,



1(Y

(k+1)

= a

k+1

)|F

j+k−1



= E



1(Y

(k)

= a

)1(X

j+1

= a

k+1

)|F

j+k−1



= 1(Y

(k)

= a

)p(a

k+1

Logo substituindo em (1.35) segue



g(Y

(k+1)

) ·g(Y

(k+1)

)



= 0. (1.36)

Agora, usando (1.34) e (1.36), obtemos

= E

(k+1)

)) + 2

∑

j=2



g(Y

(k+1)

) ·g(Y

(k+1)

)



k+1

)(1− p(a

k+1

)). (1.37)

Aplicando (1.37), (1.32) e (1.33) no Teorema 1.11, considerando t = n −k, e como

> 0 (por (1.29)) temos

1 = limsup

n→∞

(g)−E(S

(g))

√

tloglogt

= limsup

n→∞

N(a

k+1

)−N(a

)p(a

k+1

)+1(Y

(k)

n−k+1

)



k+1

)(1−p(a

k+1

))tloglogt

= limsup

n→∞

N(a

k+1

)−N(a

)p(a

k+1

)



k+1

)(1−p(a

k+1

))tloglogt

Pela continuidade da func¸

ao h(x) = x

e usando que t =



n−k



n, temos que

1 =



limsup

n→∞

N(a

k+1

)−N(a

)p(a

k+1

)



k+1

)(1−p(a

k+1

))tloglogt



= limsup

n→∞



[

N(a

k+1

)−N(a

)p(a

k+1

)

]

k+1

)(1−p(a

k+1

))tloglogt



= limsup

n→∞



[

N(a

k+1

)−N(a

)p(a

k+1

)

]

k+1

)(1−p(a

k+1

))nloglog

(

n−k

)

n−k



Usando a continuidade de loglogx, e das propriedades de limsup obtemos

1 = limsup

n→∞













N(a

k+1

) −N(a

)p(a

k+1

)



k+1

)(1− p(a

k+1

))nlog log



n−k



n−k













k+1

)(1− p(a

k+1

))



limsup

n→∞













N(a

k+1

) −N(a

)p(a

k+1

)



nlog log n











e portanto temos (1.30).

Observac¸

ao 1.13. Sob as mesmas hip

oteses do Lema 1.12, podemos ainda ter

liminf

n→∞



N(a

k+1

) −N(a

)p(a

k+1

)



nlog log n

= 0. (1.38)

Demonstrac¸

ao. Usando a deﬁnic¸

ao de N(a

), para n > k, podemos veriﬁcar que

n+1

N(a

k+1

n+1

)−N(a

n+1

)p(a

k+1

)

√

(n+1)loglog(n+1)

N(a

k+1

)+1(X

n+1

n−k+1

k+1

)−N(a

)p(a

k+1

)−1(X

n+1

n−k+1

k+1

)p(a

k+1

)

√

(n+1)loglog(n+1)

N(a

k+1

)−N(a

)p(a

k+1

)

√

(n+1)loglog(n+1)

1(X

n+1

n−k+1

k+1

)−1(X

n+1

n−k+1

k+1

)p(a

k+1

)

√

(n+1)loglog(n+1)

ı dado

> 0, para n suﬁcientemente grande,

−

n+1

| =



N(a

k+1

) −N(a

)p(a

k+1

)

√

nlog log n

−

N(a

k+1

) −N(a

)p(a

k+1

)



(n+ 1)log log (n+ 1)

−

1(X

n+1

n−k+1

= a

k+1

) −1(X

n+1

n−k+1

= a

k+1

)p(a

k+1

)



(n+ 1)log log (n+ 1)



≤



N(a

k+1

) −N(a

)p(a

k+1

)

√

nlog log n

−

N(a

k+1

) −N(a

)p(a

k+1

)



(n+ 1)log log (n+ 1)



1(X

n+1

n−k+1

= a

k+1

) −1(X

n+1

n−k+1

= a

k+1

)p(a

k+1

)



(n+ 1)log log (n+ 1)



≤



1(X

n+1

n−k+1

= a

k+1

) −1(X

n+1

n−k+1

= a

k+1

)p(a

k+1

)



(n+ 1)log log (n+ 1)



≤ 2

. (1.39)

Usando racioc

ınio semelhante ao usado na prova do Lema 1.12, mas aplicando o Teo-

rema 1.11 para o liminf, podemos veriﬁcar que

liminf

n→∞

= −



k+1

)(1− p(a

k+1

)). (1.40)

em disso, aplicando o Teorema 1.11 para o limsup obtemos

limsup

n→∞



k+1

)(1− p(a

k+1

)). (1.41)

Assim, dado

> 0, pode-se tomar n

tal que n > n

implica que

−

n+1

. Al

disso, de (1.40) e (1.41), temos que existe n

> n

tal que

> 0 e

≤ 0. Usando

(1.39), obtemos que

−

. Logo

−

−0

0−

−0

Assim conclu

ımos que

liminf

n→∞



N(a

k+1

) −N(a

)p(a

k+1

)



nlog log n

= liminf

n→∞

= 0.

Teorema 1.14. Se X

e uma Cadeia de Markov de ordem r satisfazendo (1.29), ent

ao para

k ≥r temos quase certamente

(a)

limsup

n→∞

log

L(k) −log L(k)

log log n

(k), (1.42)

(b)

log

L(k) −log L(k) ≥ o(

), (1.43)

onde

(k) = |E|

(|E|−1)

e o n

umero de par

ametros livres, considerando o modelo de ordem

Demonstrac¸

ao. (a) Da deﬁnic¸

ao de L(k) e

L(k) temos

log

L(k) −log L(k) =

∑

k+1

N(a

k+1

)log

N(a

k+1

)

N(a

)

−

∑

k+1

N(a

k+1

)log p(a

k+1

)

= −

∑

k+1

N(a

k+1

)log

N(a

)p(a

k+1

)

N(a

k+1

)

= −

∑

k+1

N(a

k+1

)log



1+ z

k+1

)



, (1.44)

onde z

k+1

) =

N(a

)p(a

k+1

)−N(a

k+1

)

N(a

k+1

)

. Notemos que, como

N(a

k+1

)

N(a

)

→

q.c.

p(a

k+1

) ent

k+1

) →

q.c.

Considerando o desenvolvimento em s

erie de Taylor em torno de 1 para log x em (1.44),

temos que

log

L(k) −log L(k) = −

∑

k+1

N(a

k+1

) +

∑

k+1

N(a

k+1

)



k+1

)



−

∑

k+1

R(a

k+1

), (1.45)

com

lim

k+1

)→0

R(a

k+1

)



k+1

)



= 0. (1.46)

Usando o Lema 1.5 na primeira parcela de (1.45), temos

−

∑

k+1

N(a

k+1

) = −

∑

k+1



N(a

)p(a

k+1

) −N(a

k+1

)



= −

∑



N(a

) −



N(a

) −1(X

n−k+1

= a

)



= −

∑

1(X

n−k+1

= a

)

= −1. (1.47)

Agora, como

N(a

k+1

)

→

q.c.

k+1

), usando o Lema 1.12 obtemos

limsup

n→∞

N(a

k+1

)



k+1

)



log log n

= limsup

n→∞

N(a

k+1

) −N(a

)p(a

k+1

)

nlog log n

N(a

)

= 2

k+1

)(1− p(a

k+1

))

k+1

)

= 2(1− p(a

k+1

)) (1.48)

limsup

n→∞



k+1

)



log log n

= limsup

n→∞







N(a

k+1

)



k+1

)



log log n

N(a

k+1

)







= 0. (1.49)

Assim, de (1.48) segue

limsup

∑

k+1

)



k+1

)



nlog log n

∑

k+1

)

k+1

)



1− p(a

k+1

)



∑

k+1



1− p(a

k+1

)



= |E|

(1−|E|)

(k). (1.50)

Por outro lado, de (1.46) e (1.49) segue

limsup

∑

k+1

R(a

k+1

)

log log n

= limsup

∑

k+1

R(a

k+1

)



k+1

)



log log n

R(a

k+1

)

= 0. (1.51)

Logo, de (1.45), (1.47), (1.50) e (1.51) obtemos (1.42).

(b) Temos de (1.45) e (1.47) que

log

L(k) −log L(k) = −1+

∑

k+1

N(a

k+1

)



k+1

)



−

∑

k+1

R(a

k+1

)

≥ −1−

∑

k+1

R(a

k+1

Assim, para provar (1.43) basta mostrarmos que

∑

k+1

R(a

k+1

) = o(

). (1.52)

Paraisto, basta observarmos que, como

N(a

k+1

)

→

q.c.

k+1

), usando (1.38) daObservac¸

1.13 temos que

liminf

n→∞



k+1

)



log log n

= liminf

n→∞













N(a

k+1

) −N(a

)p(a

k+1

)



nlog log n



N(a

k+1

)













= 0.

ı usando (1.46) segue que

liminf

n→∞

∑

k+1

R(a

k+1

)

log log n

= 0. (1.53)

Logo, de (1.46), (1.51) e (1.53) obtemos (1.52) e consequentemente

log

L(k) −log L(k) ≥ o(

Observac¸

ao 1.15. Sob as mesmas hip

oteses do Teorema 1.14 e repetindo o mesmoracioc

ınio

da prova da parte (a) deste teorema, substituindo limsup por liminf e usando a Observac¸

1.13 no lugar do Lema 1.12 podemos mostrar

liminf

n→∞

log

L(k) −log L(k)

log log n

= 0.

Para simpliﬁcar a notac¸

ao utilizada nos pr

oximos resultados, considere:

(k) =

∑

r+1

)p(a

r+1

)log

p(a

r+1

)

q(a

r+1

r−k+1

)

, (1.54)

onde

q(a

r+1

) = p(a

r+1

)

q(a

r+1

r−k+1

) =

∑

r−k

)p(a

r+1

)

∑

r−k

)

, para 0 ≤ k < r. (1.55)

Uma motivac¸

ao para a deﬁnic¸

ao de q(a

r+1

r−k+1

)

e escrever uma probabilidade com

depend

encia menor que r em termos das probabilidades conhecidas. Podemos ainda ver que,

quase certamente,

lim

N(b

k+1

)

N(b

)

= lim

n→∞

∑

−(r−k)+1

N(b

k+1

−(r−k)+1

) + o(

)

∑

−(r−k)+1

N(b

−(r−k)+1

) + o(

)

= lim

n→∞

∑

−(r−k)+1

N(b

−(r−k)+1

)

N(b

k+1

−(r−k)+1

)

N(b

−(r−k)+1

)

∑

−(r−k)+1

N(b

−(r−k)+1

)

= q(a

r+1

r−k+1

). (1.56)

Teorema 1.16. Se X

e uma Cadeia de Markov de ordem r satisfazendo (1.29) ent

ao, se

0 ≤ k < r, temos

lim

n→∞

log

L(r) −log

L(k)

(k), q.c. (1.57)

(k) > 0 e

(k) ≥

(k+ 1). (1.58)

Demonstrac¸

ao. Seja 0 ≤ k < r. Para provar (1.57), notemos que de (1.20) do Lema 1.5

podemos obter

log

L(r) −log

L(k) =

∑

r+1

N(a

r+1

)log

N(a

r+1

)

N(a

)

−

∑

k+1

N(a

k+1

)log

N(a

k+1

)

N(a

)

∑

r+1

N(a

r+1

)log

N(a

r+1

)

N(a

)

−

∑

k+1





∑

r+1

k+2

N(a

k+1

r+1

k+2

) + o(

)





log

N(a

k+1

)

N(a

)

∑

r+1

N(a

r+1

)log

N(a

r+1

)

N(a

)

−

∑

k+1





∑

r+1

k+2

N(a

k+1

r+1

k+2

)





log

N(a

k+1

)

N(a

)

+ o(

)

∑

r+1

N(a

r+1

)log

N(a

r+1

)

N(a

)

N(a

)

N(a

k+1

)

+ o(

). (1.59)

Agora, lim

N(a

)

N(a

k+1

)

N(a

r+1

)

N(a

)

= 1 para algum a

r+1

, caso contr

ario a ordem da Cadeia de

Markov seria menor ou igual a k < r. Como

N(a

r+1

)

→

q.c.

p(a

r+1

N(a

r+1

)

N(a

)

→

q.c.

) (usando

o Teorema 1.9) ent

ao, juntamente com (1.56), segue que

lim

n→∞

log

L(r) −log

L(k)

= lim

n→∞

∑

r+1

N(a

r+1

)

log

N(a

r+1

)

N(a

)

N(a

)

N(a

k+1

)

∑

r+1

p(a

r+1

)

)log

p(a

r+1

)

q(a

r+1

r−k+1

)

(k).

Para provar (1.58), primeiramente segue da desigualdade de Jensen que

(k) =

∑

k+1

p(a

k+1

)

)log

p(a

k+1

)

q(a

k+1

)

= -

∑

)

∑

k+1

p(a

k+1

)log

q(a

k+1

)

p(a

k+1

)

> -

∑

)log



∑

k+1

p(a

k+1

)

q(a

k+1

)

p(a

k+1

)



= -

∑

)log

∑

k+1

q(a

k+1

)

= 0 ,

pois

∑

k+1

q(a

k+1

) = 1.

ultima desigualdade de (1.58) segue de (1.57) e da parte (c) do Lema 1.7, ou seja,

(k) = lim

n→∞

log

L(r) −log

L(k)

= lim

n→∞

log

L(r) −log

L(k) +log

L(k+1) −log

L(k+1)

= lim

n→∞

log

L(r) −log

L(k+1)

+ lim

n→∞

log

L(k+1) −log

L(k)

≥ lim

n→∞

log

L(r) −log

L(k+1)

(k+ 1).

Teorema 1.17. Seja X uma Cadeia de Markov com espac¸o de estados E, tal que |E| ≥ 2 e

satisfazendo (1.29). Considere o crit

erio EDC em (1.9), (1.10) com

(k) = |E|

(|E|−1) e

{

}

uma sequ

encia de constantes reais, c

> 0.

(a) Se k ≥r, ent

ao quase certamente

liminf

n→∞

EDC(k+ 1) −EDC(k)

log log n

= −2

(k+ 1) +



liminf

n→∞

log log n



(|E|−1)

(k)

(1.60)

limsup

n→∞

EDC(k+ 1) −EDC(k)

log log n

= 2

(k) +



limsup

n→∞

log log n



(|E|−1)

(k). (1.61)

(b) Se 0 ≤k < r, ent

ao quase certamente

lim

n→∞

EDC(k) −EDC(r)

= 2

(k) + [

(k) −

(r)] lim

n→∞

. (1.62)

Demonstrac¸

ao. (a) Se k ≥ r, do Lema 1.7 temos log L(k+ 1) = log L(k) + o(

). Ent

da deﬁnic¸

ao (1.10) do EDC segue

EDC(k+1) - EDC(k) = -2 log

L(k+ 1) +

(k+ 1)c

+ 2log

L(k) −

(k)c

= -2



log

L(k+ 1) −log L(k+ 1)



+ 2



log

L(k) −log L(k)



+ c

[

(k+ 1) −

(k)] + o(

Como

(k) = |E|

(|E|−1) segue

EDC(k+1) - EDC(k) = -2



log

L(k+ 1) −log L(k+ 1)



+ 2



log

L(k) −log L(k)



+ c

(k)(|E|−1) + o(

ı, usando (1.42) do Teorema 1.14, temos

liminf

n→∞

EDC(k+1)−EDC(k)

loglogn

= -2 limsup

n→∞

log

L(k+1) −logL(k+1)

loglogn

+2 liminf

n→∞

log

L(k) −logL(k)

loglogn

(k)(|E|−1)liminf

n→∞

loglogn

= -2

(k+ 1) +

(k)(|E|−1)liminf

n→∞

loglogn

e assim (1.60) est

a provado.

Analogamente, usando (1.42) obtemos

limsup

n→∞

EDC(k+1)−EDC(k)

loglogn

= -2 liminf

n→∞

log

L(k+1) −logL(k+1)

loglogn

+2 limsup

n→∞

log

L(k) −logL(k)

loglogn

(k)(|E|−1)limsup

n→∞

loglogn

= 2

(k) +

(k)(|E|−1)liminf

n→∞

loglogn

e segue (1.61).

(b) Para 0 ≤k < r, temos usando (1.57) do Teorema 1.16

lim

n→∞

EDC(k)−EDC(r)

= 2 lim

n→∞

log

L(r) −log

L(k)

+ [

(k) −

(r)] lim

n→∞

= 2

(k) + [

(k) −

(r)] lim

n→∞

e portanto (1.62) est

a provado.

Corol

ario 1.18. Seja X uma Cadeia de Markov, satisfazendo as mesmas hip

oteses do Teo-

rema 1.17 e c

> 0 satisfazendo

liminf

n→∞

log log n

≥

2|E|

|E|−1

e limsup

n→∞

= 0. (1.63)

(a) Se k > r ent

ao, quase certamente

liminf

n→∞

EDC(k) −EDC(r)

log log n

≥ 0 (1.64)

limsup

n→∞

EDC(k) −EDC(r)

log log n

> 2

(r)(k−r)(|E|+ 1) > 2

(r), (1.65)

com o limite em (1.65) mon

otono crescente em k.

(b) Se 0 ≤k < r, ent

ao quase certamente

lim

n→∞

EDC(k) −EDC(r)

= 2

(k), (1.66)

com o limite (1.66) mon

otono decrescente em k.

Demonstrac¸

ao. (a) Seja k > r. Aplicando as hip

oteses (1.64) em (1.60) no Teorema 1.17,

obtemos

liminf

n→∞

EDC(k+ 1) −EDC(k)

log log n

≥ −2

(k+ 1) +

2|E|

|E|−1

(|E|−1)

(k)

= −2

(k+ 1) + 2|E|

(k)

= −2|E|

k+1

(|E|−1) + 2|E||E|

(|E|−1)

= 0. (1.67)

Agora, como EDC(k)−EDC(r) =

k−1

∑

j=r

[EDC( j+ 1) −EDC( j)]. Aplicando (1.67) repeti-

das vezes, obtemos (1.64). De forma semelhante, aplicando (1.63) em (1.61) obtemos

limsup

n→∞

EDC(k+ 1) −EDC(k)

log log n

≥ 2

(k) +

2|E|

|E|−1

(|E|−1)

(k)

= 2

(k)(1+ |E|). (1.68)

Novamente, aplicando repetidas vezes (1.68), como para k > r

(k) >

(r) podemos

obter

limsup

n→∞

EDC(k)−EDC(r)

loglogn

k−1

∑

i=r

limsup

n→∞

EDC(i+1)−EDC(i)

loglogn

≥ 2(1+ |E|)

k−1

∑

i=r

(i)

> 2(1+ |E|)

(r)(k−r)

e (1.65) est

a provado.

(b) Segue de (1.63) e do Teorema 1.16.

Corol

ario 1.19. Sob as mesmas hip

oteses do Teorema 1.17, o estimador EDC, com termo

de penalidade positivo que satisfac¸a (1.63),

e fortemente consistente. Reciprocamente, um

estimador baseado na verossimilhanc¸a penalizada que n

ao satisfac¸a (1.63) n

e fortemente

consistente.

Demonstrac¸

ao. Nessas hip

oteses, usando o Corol

ario 1.18, temos de (a) que, quase certa-

mente, ˆr

EDC

≤ r e por (b) temos que lim ˆr

EDC

≥ r, onde conclu

ımos a igualdade.

Por outro lado, se liminf

loglogn

2|E|

|E|−1

, ent

ao, usando (1.60) do Teorema 1.17, temos

quase certamente

liminf

EDC(r+ 1) −EDC(r)

log log n

= −2

(r+ 1) +



liminf

log log n



(|E|−1)

(r)

< 0,

o que indica que poder

a ocorrer superestimac¸

ao da ordem. Al

em disso, se limsup

= c > 0,

temos por (1.62) do teorema 1.17 que

limsup

EDC(r−1) −EDC(r)

= 2

(r−1) + [

(r−1) −

(r)]c,

que n

ao garante a consist

encia, pois poder

a ter casos em que |[

(r−1) −

(r)]c| > 2

(r−

1).

Segue como consequ

encia imediata o seguinte corol

ario.

Corol

ario 1.20. O estimador AIC n

e fortemente consistente.

Corol

ario 1.21. O estimador BIC

e fortemente consistente.

Demonstrac¸

ao. Para o estimador BIC temos c

= log n e temos

liminf

n→∞

log n

log log n

= ∞ >

2|E|

|E|−1

limsup

n→∞

log n

= 0,

logo as hip

oteses do Corol

ario 1.19 est

ao satisfeitas.

Corol

ario 1.22. Sob as hip

oteses do Corol

ario 1.18, o termo de penalidade

otimo

(k) =

2|E|

|E|−1

log log(n) ·(|E|−1)|E|

. (1.69)

Demonstrac¸

ao. O termo de penalidade deve ser o menor poss

ıvel para evitar subestimac¸

da ordem e grande o suﬁciente para ter a consist

encia forte. Neste caso, pelas condic¸

oes do

Corol

ario 1.18, o menor termo assint

otico

2|E|

|E|−1

log log(n) ·(|E|−1)|E|

Em consequ

encia desse resultado, segue:

Corol

ario 1.23. O estimador BIC penaliza mais que necess

ario.

Como pode ser veriﬁcado na demonstrac¸

ao do Corol

ario 1.22, o fato do BIC penalizar

mais que o necess

ario gera uma maior tend

encia desse estimador a subestimar a ordem.

Vale ressaltar tamb

em que o Corol

ario 1.21

e o teorema da consist

encia forte do BIC,

apresentada por Csiszar & Shields (2000).

1.3 Considerac¸

oes

Se 0 ≤k < r, pela equac¸

ao (1.59) na prova do Teorema 1.16 e pela deﬁnic¸

ao de N(a

r+1

)

em (1.4), temos que

log

L(r) −log

L(k) =

∑

r+1



j−k

∑

j=1

1(X

j+k

= a

k+1

)



log

N(a

r+1

)

N(a

)

N(a

)

N(a

k+1

)

+ o(

Considerando a cadeia (r+ 1)-derivada, Y

(r+1)

e tomando g : E → R,

g(Y

(r+1)

) =

∑

r+1

1(Y

= a

k+1

)log

N(a

r+1

)

N(a

)

N(a

)

N(a

k+1

)

e S

(g) =

∑

j=1

g(Y

temos

log

L(r) −log

L(k) =

j=n

∑

j=1

g(Y

(r+1)

) + o(

) = S

(g) + o(

Assim, segue do Teorema 1.10

log

L(r) −log

L(k) −n

(k)



→

N (0, 1),

onde

∑

r+1

)



log

p(a

r+1

)

q(a

r+1

r−k+1

)



∑

j=2

∑

r+1

P(Y

(k+1)

= a

r+1

)P(Y

(k+1)

= b

r+1

)log

p(a

r+1

)

q(a

r+1

r−k+1

)

log

p(b

r+1

)

q(b

r+1

r−k+1

)

Analisando o comportamento para n suﬁcientemente grande e ﬁxo, podemos ent

ao con-

cluir da argumentac¸

ao acima e do Teorema 1.16: Se X

e uma Cadeia de Markov de ordem r

satisfazendo (1.29) ent

ao, para k < r

(i) −2log

L(k) + 2log

L(r) = 2n

(k) + o(n) e

(ii) −2log

L(k) + 2log

L(r) ∼N (2n

(k), n

Estas conclus

oes despertam o interesse em se conhecer melhor

(k). O Teorema 1.16

mostra que

(k) deve ser positivo para k < r e, pela sua deﬁnic¸

ao,

e poss

ıvel notar que pode

ser arbitrariamente pr

oximo de 0. Entretanto, podemos ter um limitante superior para

(k),

limitando-o no intervalo, relativamente pequeno, (0, log |E|). Isto

e: conforme deﬁnido,

(k) < log |E|.

De fato, usando as deﬁnic¸

oes (1.54) e (1.55) de

(k) e q(a

r+1

r−k+1

), respectivamente,

e o Lema 1.6 podemos obter

(k) = log





∏

r+1



p(a

r+1

)

q(a

r+1

r−k+1

)



p(a

r+1

)





≤ log







∑

r+1







p(a

r+1

)p(a

r+1

)

∑

r−k

r−k+1

)p(a

r+1

r−k

r−k+1

)

∑

r−k

r−k+1

)













= log







∑

r+1

r−k+1







∑

r−k

p(a

r+1

)p(a

r+1

)

∑

r−k

r−k+1

)p(a

r+1

r−k

r−k+1

)

∑

r−k

r−k+1

)













< log







max

r+1

(p(a

r+1

))

∑

r+1

r−k+1







∑

r−k

p(a

r+1

)

∑

r−k

r−k+1

)p(a

r+1

r−k

r−k+1

)

∑

r−k

r−k+1

)













≤ log





∑

r+1

r−k+1

∑

r−k

r−k+1

)





= log |E| . (1.70)

Assim, podemos justiﬁcar a escolha do termo de penalidade

otimo em (1.69) no Corol

ario

1.22 alternativamente da seguinte forma:

Considere X

, uma Cadeia de Markov de ordem r satisfazendo (1.2) e |E|= N ≥ 2. Para

k < r e usando a argumentac¸

ao acima temos que para o estimador indique corretamente a

ordem

e necess

ario a desigualdade

(

(r) −

(k))c

≤ −2log

L(k) + 2log

L(r)

∼ N (2n

(k), n

) (1.71)

Nesse sentido, como

(k) ∈ (0, log |E|)

e arbitr

ario, deve-se tomar o menor c

assintot-

icamente que garanta a consist

encia forte para que a desigualdade ocorra para n pequeno.

Neste caso, c

|E|

|E|−1

log log n .

Por outro lado, um termo pequeno pode causar uma tend

encia a superestimac¸

ao da or-

dem para uma cadeia X

, de ordem d < r. Entretanto, quando (

(r) −

(k))c

> 2n

(k), a

partir de (1.71), o erro de subestimac¸

ao de X

e aproximadamente



N (2n

(k), n

) < (

(r) −

(k))c



> P



N (2n

(k), n

) < 2n

(k)



= 0, 5

enquanto, usando (1.6), X

tem menos de 50% de chance de superestimac¸

ao (erro).

Portanto, tomar o termo menor assintoticamente (que garanta a consist

encia forte)

e uma

boa escolha para antecipar o ﬁm da tend

encia a subestimar e, por outro lado, n

ao induz uma

tend

encia a superestimar.

2 An

alise Comparativa dos

Estimadores

Neste cap

ıtulo s

ao apresentados os resultados obtidos em simulac¸

oes realizadas com

o objetivo de comparar os estimadores fortemente consistentes BIC e EDC

opt

(EDC com

termo de penalidade

otimo) deﬁnidos por (1.9) e (1.69) no cap

ıtulo anterior, al

em de analisar

o comportamento do estimador, inconsistente, AIC dado por (1.8).

Vale ressaltar que, esse tipo de comparac¸

ao seria praticamente imposs

ıvel de ser feita

toda teoricamente. Isso porque levaria a contas exageradamente grandes que dependeriam

das probabilidades de transic¸

ao desconhecidas

. Al

em disso, n

ao faria sentido simpliﬁcar as

express

oes tomando comportamentos assint

oticos.

As simulac¸

oes computacionais foram realizadas considerando os casos em que a ordem

varia de 0 a 6 (r = 0..6) e o tamanho do espac¸o de estados varia de 2 a 10 (N = 2..10),

perfazendo 63 casos. Para cada caso foram consideradas mil cadeias de Markov, geradas

aleatoriamente. E para cada Cadeiade Markov foi gerada 1 amostra de tamanho100 milh

oes.

Foram consideradas “sub-amostras” desta, tomando-se os fragmentos da posic¸

ao inicial at

tamanhos pr

e-deﬁnidos. Isso n

ao s

o d

a uma sensac¸

ao de aproximac¸

ao, do ponto de vista

orico, mas traz um grande benef

ıcio computacional, pois desta forma as contagens de um

fragmento de amostra s

ao feitas a partir das contagens do

ultimo fragmento computado.

Os casos foram escolhidos em func¸

ao das capacidades computacionais. Os tamanhos

das amostras foram determinados empiricamente, na busca de valores mais adequados para

a comparac¸

ao dos estimadores.

Esse fato foi observado por Katz (1981), que diz: “Analytical expressions for exact distributions of

aic

and

bic

(as a function of the sample size n) are not available and, in any event, would probably be too complicated

to be very useful.”

Esses n

umeros, embora n

ao aparentem muita expressividade, s

ao consider

aveis. No caso

de maior complexidade (r = 6 e N = 10), temos uma Cadeia de Markov com (10−1)10

9.000.000 par

ametros e, para este caso, nos testes realizados, os estimadores necessitam de

amostras superiores a 100 milh

oes para acusarem a ordem corretamente!

As simulac¸

oes geraram ao todo 22.050.000

resultados para an

alise. Dessa forma, foram

considerados relat

orios sumarizados, com o foco na comparac¸

ao direta entre os m

etodos, e

distribuic¸

oes dos valores calculados para cada m

etodo.

A seguir, na sec¸

ao 2.1, descrevemos os objetivos e a metodologia dos experimentos real-

izados e na sec¸

ao 2.2 apresentamos uma an

alise dos resultados obtidos nas simulac¸

oes. Para

ﬁnalizar, apresentamos na sec¸

ao 2.3 um exemplo simples de aplicac¸

ao desses estimadores na

alise de pec¸as musicais sugerido por McAlpine, Miranda & Hoggar (1999).

2.1 Deﬁnic¸

ao dos Experimentos Computacionais

Objetivos

• Conhecer o comportamento dos estimadores em amostras “pequenas” e “grandes”;

• Identiﬁcar, para cada caso, os tamanhos em que os estimadores acertam 50%;

• Comparar a eﬁci

encia dos estimadores em relac¸

ao a ordem (r), tamanho do espac¸o de

estados (N) e tamanho da amostra (n);

Metodologia

Para cada (r, N) ∈ {0, . . . , 6}×{2, . . . , 10}, gerar 1000 cadeias de Markov, de forma

aleat

oria. Para cada cadeia, gerar uma amostra de tamanho 100 milh

oes. Para cada “sub-

amostra” desta, calcular e salvar os valores da log-verossimilhanc¸a e ordens indicadas pelos

estimadores ˆr

EDC

, ˆr

BIC

e ˆr

AIC

Usando o banco de dados criado, gerar relat

orios e gr

aﬁcos apropriados, a ﬁm de auferir

conclus

oes.

Resultado de 349∗1000∗63

Utilizar o procedimento proposto por Raftery (1985) para a gerac¸

ao de modelos de

Cadeias de Markov por permitir uma maior representatividade. Na gerac¸

ao das amostras

utilizar a biblioteca/algoritmo de aleatoriedade proposto por Park & Miller (1988).

Indicadores Comparativos

• Porcentagens de acertos para cada caso (r, N, n) considerado;

• Porcentagens de acertos sumarizados, para casos onde s

ao ﬁxados r ou N ou n;

• Porcentagens de acertos para todos os casos, considerados conjuntamente;

• Para os n

ıveis de sumarizac¸

ao descritos nos itens anteriores, considerar as porcenta-

gens de acerto (erro) de um certo estimador, quando os outros acertam (erram) – esse

indicador d

a uma noc¸

ao de quais s

ao plenamente “substitu

ıveis” por outros;

• Gr

aﬁcos para cada caso (r, N), considerando a porcentagem de acerto em func¸

ao do

tamanho da amostra n;

• Gr

aﬁcos das distribuic¸

oes dos estimadores em casos espec

ıﬁcos (r, N, n).

2.2 An

alise dos Resultados Obtidos nas Simulac¸

oes

A seguir apresentamos algumas conclus

oes obtidas ap

os a an

alise dos resultados dos

experimentos realizados.

2.2.1 O estimador EDC

opt

e mais eﬁciente que o BIC

Em todos os casos simulados, o EDC

opt

apresentou maior proporc¸

ao de acertos que o

BIC para qualquer tamanho de amostra. A excec¸

ao foi para os casos onde |E|= 2 e em certo

intervalo do tamanho amostral. Nestes casos, os termos de penalidade do BIC podem ser

menores que os do EDC

opt

, o que justiﬁca o resultado obtido.

alise dos Indicadores

A Tabela 2.1 apresenta resultados obtidos no caso |E| = 4 e r = 1, onde a coluna n rep-

resenta o tamanho da amostra, “<”, “=” e “>”, respectivamente, representam as proporc¸

oes

de subestimac¸

ao, acerto e superestimac¸

ao para cada n.

Tabela 2.1: Distribuic¸

oes de Acertos dos Estimadores EDC

opt

e BIC para o caso |E| = 4 e

r = 1

n EDC

opt

BIC

< = > < = >

10 98,70% 1,30% 0% 99,10% 0,90% 0%

25 90,20% 9,80% 0% 91,40% 8,60% 0%

68 50,60% 49,40% 0% 60,30% 39,70% 0%

775 0% 100,00% 0% 0,10% 99,90% 0%

900 0% 100,00% 0% 0% 100,00% 0%

Da mesma forma, a Tabela 2.2 apresenta os resultados para o caso |E| = 10 e r = 1.

Como pode ser veriﬁcado, em ambos casos, o EDC

opt

apresenta melhor performance que o

BIC. No de menor complexidade (|E| = 4) as proporc¸

oes de acertos s

ao semelhantes, para

o caso de maior complexidade (|E| = 10) o EDC

opt

necessitou de pouco mais da metade

do tamanho da amostra para acertar mais de 50% dos casos [considerando a mediana da

distribuic¸

ao de acertos como indicador de performance]. Esse distanciamento se veriﬁca

a medida que a complexidade (n

umero de par

ametros livres) aumenta. Na Tabela 2.3 est

representado, para cada caso, o tamanho de amostra m

ınimo em que cada estimador acer-

tou pelo menos 50%, a

ultima coluna tem a proporc¸

ao prop :=

n em que BIC acerta 50%

n em que EDC

opt

acerta 50%

, que

indica o “quanto o EDC

opt

e melhor que o BIC”.

Tabela 2.2: Distribuic¸

oes de Acertos dos Estimadores EDC

opt

e BIC para o caso |E| = 10 e

r = 1

n EDC

opt

BIC

< = > < = >

218 99,80% 0,20% 0% 100,00% 0,00% 0%

425 40,90% 59,10% 0% 100,00% 0,00% 0%

450 28,90% 71,10% 0% 99,90% 0,10% 0%

600 3,10% 96,90% 0% 91,10% 8,90% 0%

775 0,10% 99,90% 0% 48,20% 51,80% 0%

950 0% 100,00% 0% 15,40% 84,60% 0%

1812 0% 100,00% 0% 0% 100,00% 0%

Tabela 2.3: Tamanhos de Amostras M

ınimos em que os Estimadores EDC

opt

e BIC acertam

mais que 50%

r |E| n EDC

opt

n BIC prop

2 76 50 0,65

3 53 50 0,94

4 72 85 1,18

5 100 150 1,50

6 143 225 1,57

7 200 337 1,68

8 250 475 1,90

9 337 625 1,85

10 425 775 1,82

2 1125 925 0,82

3 1125 1500 1,33

4 2000 3250 1,62

5 3125 5750 1,84

6 5750 11250 1,95

7 8000 16875 2,10

8 10625 23750 2,23

9 16875 40000 2,37

10 23750 62500 2,63

2 10625 11250 1,05

3 10000 15625 1,56

4 23750 45000 1,89

5 47500 100000 2,10

6 93750 212500 2,26

7 162500 400000 2,46

8 293750 775000 2,63

9 525000 1437500 2,73

10 637500 1812500 2,84

2 32500 37500 1,15

3 81250 137500 1,69

4 225000 475000 2,11

5 600000 1437500 2,39

6 1562500 4250000 2,72

7 2875000 8125000 2,82

8 4750000 13750000 2,89

2 143750 175000 1,21

3 337500 650000 1,92

4 1687500 4000000 2,37

5 5625000 15000000 2,66

2 400000 525000 1,31

3 2000000 4000000 2,00

4 11875000 28750000 2,42

Nota-se que os casos onde |E| = 2 e r ∈

{

1, 2

}

ou |E| = 3 e r = 1 s

ao at

ıpicos – o

estimador BIC apresenta melhor performance que o EDC

opt

– isso

e justiﬁc

avel pois, para

n pequeno (se |E| = 2, n no intervalo [5, 4500]

e suﬁciente, como exemplo, veja o Gr

aﬁco

2.1, com os respectivos termos de penalidade, considerando k = 3 e |E| = 2), o termo de

penalidade do BIC

e menor que o do EDC

opt

e, para as ordens considerados (r = 0, . . . , 6),

o tamanho nessas proporc¸

oes garante uma probabilidade pequena de superestimac¸

ao para

ambos os casos. Assim, o estimador com o menor termo de penalidade tem uma maior

chance de acerto. Esses tr

es casos espec

ıﬁcos n

ao contradizem o Corol

ario 1.22, pois para n

maior, o termo de penalidade do BIC

e maior que o do EDC

opt

, e o corol

ario toma o menor

termo assint

otico.

Figura 2.1: Termos de penalidade do BIC (cont

ınuo) e EDC

opt

(pontilhado) para |E| = 2 e

k = 3 em func¸

ao de n

A medida que aumenta a complexidade (n

umero de par

ametros livres) dos modelos,

aumenta tamb

em a diferenc¸a entre as proporc¸

oes de acerto do EDC

opt

e BIC. Isso ocorre

pois, modelos mais complexos exigem tamanhos de amostras maiores, e nestes casos os

termos de penalidade de ambos se distanciam substancialmente, reﬂetindo essa diferenc¸a

nas proporc¸

oes de acerto. Isso nos leva a concluir que, para casos ainda mais complexos que

os simulados, o EDC

opt

dever

a apresentar uma proporc¸

ao de acerto ainda maior que o BIC.

Para os outros casos considerados de |E| e r, podemos observar que o comportamento

dos estimadores

e semelhante ao descrito aqui no caso r = 1, conforme podemos ver nas

Tabelas 2.4 e 2.5 para os casos (r, |E|) = (3, 4) e (r, |E|) = (4, 5).

Tabela 2.4: Distribuic¸

oes de Acertos dos Estimadores EDC

opt

e BIC para o caso |E| = 4 e

r = 3

n EDC

opt

BIC

< = > < = >

1562 99,90% 0,10% 0,00% 100,00% 0,00% 0,00%

2375 98,80% 1,20% 0,00% 99,90% 0,10% 0,00%

23125 50,20% 49,80% 0,00% 65,10% 34,90% 0,00%

9375000 0,00% 100,00% 0,00% 0,60% 99,40% 0,00%

23750000 0,00% 100,00% 0,00% 0,00% 100,00% 0,00%

Tabela 2.5: Distribuic¸

oes de Acertos dos Estimadores EDC

opt

e BIC para o caso |E| = 4 e

r = 5

n EDC

opt

BIC

< = > < = >

6500 100,00% 0,00% 0,00% 100,00% 0,00% 0,00%

32500 99,80% 0,20% 0,00% 100,00% 0,00% 0,00%

68750 93,60% 6,40% 0,00% 99,70% 0,30% 0,00%

600000 49,80% 50,20% 0,00% 66,40% 33,60% 0,00%

1437500 33,50% 66,50% 0,00% 49,90% 50,10% 0,00%

16875000 7,00% 93,00% 0,00% 13,81% 86,19% 0,00%

100000000 0,00% 100,00% 0,00% 3,40% 96,60% 0,00%

2.2.2 Paransuﬁcientementepequeno,todososestimadores t

emtend

encia

a subestimar

Katz (1981) por tr

es vezessugere que os estimadores BIC e AIC subestimam em amostras

pequenas – “...

BIC

seldom overestimates the true order.”, “...A simple modiﬁcation of the

BIC procedure could reduce this tendency to underﬁt.”, “...except for n = 50, the AIC pro-

cedure virtually never underﬁts...” – Esse comportamento foi veriﬁcado nas simulac¸

oes

para os estimadores considerados.

A explicac¸

ao para esse fato segue da seguinte argumentac¸

ao: 2[log

L(r) −log

L(l)] =

(l) + o(n) se l < r (Teorema 1.16), e portanto EDC(l) −EDC(r) = 2n

(l) + o(n) −

(

(r) −

(l)). Como

(l)

e relativamente pequeno (conforme (1.70)), c

(

(r) −

(l)) >

(l)+ o(n) para n suﬁcientemente pequeno, o que leva

a subestimac¸

ao. Obviamente, isso

ao pode ocorrer para n qualquer. O que justiﬁca a n

ao ocorr

encia de subestimac¸

oes da

ordem para n grande.

A Tabela 2.6 apresenta a distribuic¸

ao de acertos para alguns casos em tamanhos variados.

Observa-se que o comportamento do AIC inverte para certo n que depende da complex-

idade e, como ser

a visto na pr

oxima sec¸

ao, o AIC pode ter probabilidade consideravelmente

pequena de superestimac¸

ao para n grande.

Tabela 2.6: Distribuic¸

oes de Acertos dos Estimadores EDC

opt

, BIC e AIC

r |E| n EDC

opt

BIC AIC

< = > < = > < = >

1 3

10 80,30% 19,70% 0,00% 73,90% 26,10% 0,00% 63,10% 36,90% 0,00%

22 72,20% 27,80% 0,00% 67,40% 32,60% 0,00% 39,80% 59,90% 0,30%

168 15,00% 85,00% 0,00% 15,80% 84,20% 0,00% 3,30% 93,50% 3,20%

1375 0,60% 99,40% 0,00% 0,80% 99,20% 0,00% 0,10% 96,20% 3,70%

3125 0,00% 100,00% 0,00% 0,10% 99,90% 0,00% 0,00% 96,20% 3,80%

5000 0,00% 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 97,10% 2,90%

1 4

10 98,70% 1,30% 0,00% 99,10% 0,90 % 0,00% 96,10% 3,90% 0,00%

131 18,40% 81,60% 0,00% 27,50% 72,50 % 0,00% 1,60% 98,40% 0,00%

212 7,30% 92,70% 0,00% 12,20% 87,80 % 0,00% 0,20% 99,70% 0,10%

975 0,00% 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 99,90% 0,10%

2 3

17 100,00% 0,00 % 0,00% 100,00% 0,00 % 0,00% 99,90% 0,10% 0,00%

137 96,50 % 3,50 % 0,00% 97,30 % 2,70 % 0,00% 58,59% 41,30% 0,10%

175000 1,70 % 98,30 % 0,00% 3,50 % 96,50% 0,00% 0,10% 99,80% 0,10%

4750000 0,00 % 100,00% 0,00% 0,00 % 100,00% 0,00% 0,00% 99,90% 0,10%

2 5

137 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 99,70% 0,30% 0,00%

400 99,90% 0,10% 0,00% 100,00% 0,00% 0,00% 67,00% 33,00% 0,00%

650 99,00% 1,00% 0,00% 100,00% 0,00% 0,00% 50,10% 49,90% 0,00%

750 97,00% 3,00% 0,00% 9990% 0,10% 0,00% 47,00% 53,00% 0,00%

3125 49,90% 50,10% 0,00% 68,10% 31,90% 0,00% 20,90% 79,10% 0,00%

6000 35,80% 64,20% 0,00% 49,00% 51,00% 0,00% 13,70% 86,30% 0,00%

106250 5,40% 94,60% 0,00% 10,60% 89,40% 0,00% 0,50% 99,50% 0,00%

187500 4,10% 95,90% 0,00% 6,40% 93,60% 0,00% 0,00% 100,00% 0,00%

837500 0,00% 100,00% 0,00% 1,50% 98,50% 0,00% 0,00% 100,00% 0,00%

2000000 0,00% 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 100,00% 0,00%

3 10

17500 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 99,39% 0,61% 0,00%

81250 99,39% 0,61% 0,00% 100,00% 0,00% 0,00% 61,26% 38,74% 0,00%

131250 91,49% 8,51% 0,00% 100,00% 0,00% 0,00% 49,24% 50,76% 0,00%

637500 49,94% 50,06% 0,00% 77,07% 22,93% 0,00% 20,62% 79,38% 0,00%

1812500 30,63% 69,37% 0,00% 49,74% 50,26% 0,00% 12,31% 87,69% 0,00%

11250000 10,31% 89,69% 0,00% 19,51% 80,49% 0,00% 0,60% 99,40% 0,00%

13750000 7,90% 92,10% 0,00% 18,21% 81,79% 0,00% 0,00% 100,00% 0,00%

100000000 0,00% 100,00% 0,00% 6,41% 93,59% 0,00% 0,00% 99,20% 0,80%

4 4

2000 100,00% 0,00% 0,00% 100,00% 0,00% 0,00% 99,80% 0,20% 0,00%

9000 99,90% 0,10% 0,00% 100,00% 0,00% 0,00% 81,90% 18,10% 0,00%

15625 98,40% 1,60% 0,00% 99,90% 0,10% 0,00% 68,70% 31,30% 0,00%

37500 88,60% 11,40% 0,00% 96,90% 3,10% 0,00% 49,70% 50,30% 0,00%

225000 49,30% 50,70% 0,00% 64,90% 35,10% 0,00% 20,90% 79,10% 0,00%

475000 36,60% 63,40% 0,00% 49,40% 50,60% 0,00% 13,30% 86,70% 0,00%

16250000 2,80% 97,20% 0,00% 7,60% 92,40% 0,00% 0,00% 100,00% 0,00%

100000000 0,10% 99,90% 0,00% 0,40% 99,60% 0,00% 0,00% 100,00% 0,00%

2.2.3 Comportamento do estimador AIC

Mesmo com a inconsist

encia do estimador AIC e a exist

encia de alternativas fortemente

consistentes, este estimador v

em sendo utilizado em muitas aplicac¸

oes nas mais diferentes

areas (Yamaoka, Nakagawa & Uno (2005), Hoon, Imoto & Miyano (2002), Rose, Dick,

Viken & Kaprio (2001), dentre os mais recentes).

Assim, a quest

ao, j

a levantada por Kuha (2004), por exemplo, sobre a eﬁc

acia da utilizac¸

do estimador AIC merece ainda ser estudada. Neste sentido, realizamos as simulac¸

oes

num

ericas com o objetivo de analisar especialmente a performance do AIC em amostras de

tamanho ﬁnito (n

ao necessariamente grande) e a probabilidade de superestimac¸

ao do AIC,

apontada por Katz (1981).

Em linhas gerais, nos resultados obtidos para todos os casos considerados, veriﬁcou-

se um comportamento padr

ao entre as proporc¸

oes de acertos dos estimadores, sendo que

o AIC subestimava para amostras bem pequenas, apresentava maior quantidade de acertos

para amostras pequenas, mantendo proporc¸

ao de acerto pr

oximo de sua distribuic¸

ao limite.

Os tamanhos das amostras em que esses comportamentos apareciam dependiam substancial-

mente da complexidade dos casos considerados.

Para n grande e casos de menor complexidade, o AIC manteve uma taxa de acerto maior

que 67%. Para casos de maior complexidade, essa taxa se manteve em valores pr

oximos

de 100% – que n

ao contradiz a sua inconsist

encia, pois a probabilidade de superestimac¸

ao,

embora positiva, pode ser pequena.

alise dos Indicadores

A Tabela 2.7 apresenta o caso r = 1 e |E| = 2. Veriﬁca-se que o AIC, EDC

opt

e BIC

acertam, respectivamente, 42, 92%, 28, 65% e 39, 53%, para n = 10. Entretanto, com n =

5000000, o AIC acerta apenas 67, 17%, enquanto ambos outros acertam 100, 00% dos casos.

Mas, para um caso de maior complexidade (Tabela 2.8), r = 1 e |E| = 6, o AIC, EDC

opt

BIC acertam, respectivamente, 43, 92%, 0, 50% e 0, 00%, para n = 45 e para n = 5000000, o

AIC acerta 100, 00%.

Tabela 2.7: Distribuic¸

oes de Acertos dos Estimadores Para o Caso r = 1 e |E| = 2

n EDC

opt

BIC AIC

< = > < = > < = >

10 70,45 28,65 0,89 53,68 39,53 6,78 45,20 42,92 11,87

57 52,99 46,91 0,10 43,40 54,80 1,79 24,95 50,90 24,15

375000 0,59 99,41 0,00 0,59 99,41 0,00 0,30 70,06 29,64

475000 0,59 99,41 0,00 0,59 99,41 0,00 0,00 68,77 31,23

5000000 0,00 100,00 0,00 0,00 100,00 0,00 0,00 67,17 32,83

Cabe observar que o AIC acerta primeiro pois, 2(log

L(r) −log

L(l)) = 2n

(l) + o(n)

se l < r (Teorema 1.16), e portanto EDC(l) −EDC(r) = 2n

(l) + o(n) −c

(

(r) −

(l)).

Tabela 2.8: Distribuic¸

oes de Acertos dos Estimadores Para o Caso r = 1 e |E| = 6

n EDC

opt

BIC AIC

< = > < = > < = >

22 100,00 0,00 0,00 100,00 0,00 0,00 99,80 0,20 0,00

45 99,50 0,50 0,00 100,00 0,00 0,00 56,08 43,92 0,00

200 11,87 88,13 0,00 46,70 53,30 0,00 0,00 100,00 0,00

5000000 0,00 100,00 0,00 0,00 100,00 0,00 0,00 100,00 0,00

Assim,

e necess

ario n suﬁcientemente grande para 2n

(l) + o(n) > c

(

(r) −

(l)) e o esti-

mador n

ao subestimar a ordem. Neste caso, quanto menor o fator c

no termo de penalidade,

menor o n necess

ario para que isso ocorra. Como o AIC tem um termo de penalidade menor

que o EDC

opt

e BIC, ele acerta primeiro.

Por outro lado, o AIC erra mesmo para n substancialmente grande. Isso vem do fato

dele ser inconsistente (Katz 1981). Basicamente, 2[log

L(l) −log

L(r)] ∼

(

(l) −

(r))

se l > r (Billingsley 1961). Enquanto isso, o termo de penalidade do AIC

e constante, resul-

tando em AIC(l) −AIC(r) ∼ −

(

(l) −

(r)) + 2(

(l) −

(r)). Logo, como P(

(

(l) −

(r)) > 2(

(l)−

(r))) > 0, temos uma probabilidade positiva de AIC(l) < AIC(r), levando

a superestimac¸

ao da ordem.

Entretanto, P(

(t) > 2t) pode ser muito pequena se t =

(l) −

(r) for grande, o

que ocorre em modelos mais complexos. Para exempliﬁcar, calculamos alguns valores de

(

(l)−

(r)) > 2(

(l)−

(r))) na Tabela 2.9

Nas simulac¸

oes, consideramos o limitante superior para a ordem igual a 7 (i.e. K = 7).

Utilizando as mesmas contas realizadas por Katz (1981), temos que, assintoticamente,

P(ˆr

aic

> r) =

∑

i=r

P(ˆr

aic

= i) ≤

∑

i=r



2[log

L(i+ 1) −log

L(i)] > 2(

(i+ 1) −

(i))



∼

∑

i=r



[

(i+ 1) −

(i)] > 2(

(i+ 1) −

(i))



Assim, para o caso considerado por Katz, |E|= 2 e r = 1, a probabilidade assint

otica do

AIC superestimar

Foi utilizado o programa R para o c

alculo num

erico.

Tabela 2.9: Probabilidades Calculadas para a Distribuic¸

|E| l

(l) −

(l −1) P(

(

(l) −

(l −1)) > 2(

(l) −

(l −1))) Probabilidade

|E|= 2

2 2 P(

(

(2) −

(1)) > 2(

(2) −

(1))) 0, 135335

3 4 P(

(

(3) −

(2)) > 2(

(3) −

(2))) 0, 0915782

4 8 P(

(

(4) −

(3)) > 2(

(4) −

(3))) 0, 0423801

5 16 P(

(

(5) −

(4)) > 2(

(5) −

(4))) 0, 00999978

6 32 P(

(

(6) −

(5)) > 2(

(6) −

(5))) 0, 000659928

7 64 P(

(

(7) −

(6)) > 2(

(7) −

(6))) 0, 00000361702

|E|= 3

2 12 P(

(

(2) −

(1)) > 2(

(2) −

(1))) 0, 0203410

3 36 P(

(

(3) −

(2)) > 2(

(3) −

(2))) 0, 000340357

4 108 P(

(

(4) −

(3)) > 2(

(4) −

(3))) 0, 00000000333

5 324 P(

(

(5) −

(4)) > 2(

(5) −

(4))) < 10

−10

6 972 P(

(

(6) −

(5)) > 2(

(6) −

(5))) < 10

−10

7 2916 P(

(

(7) −

(6)) > 2(

(7) −

(6))) < 10

−10

|E|> 6

2 150 P(

(

(2) −

(1)) > 2(

(2) −

(1))) < 10

−10

3 900 P(

(

(3) −

(2)) > 2(

(3) −

(2))) < 10

−10

4 5400 P(

(

(4) −

(3)) > 2(

(4) −

(3))) < 10

−10

5 32400 P(

(

(5) −

(4)) > 2(

(5) −

(4))) < 10

−10

6 194400 P(

(

(6) −

(5)) > 2(

(6) −

(5))) < 10

−10

7 1166400 P(

(

(7) −

(6)) > 2(

(7) −

(6))) < 10

−10

∑

i=2

P(ˆr

aic

= i) > P



2[log

L(2) −log

L(1)] > 2[

(2) −

(1)]



= P



(

(2) −

(1)) > 2[

(2) −

(1)]



∼

0, 13

∑

i=2

P(ˆr

aic

= i) <

∑

i=2



2[log

L(i) −log

L(i−1)] > 2[

(i) −

(i−1)]



∑

i=2



(

(i) −

(i−1)) > 2[

(i) −

(i−1)]



∼

0, 13+ 0, 09+ 0, 05 = 0, 27

Por outro lado, se considerarmos o caso |E| = 6 e r = 1, essa probabilidade

∑

i=2

P(ˆr

aic

= i) <

∑

i=2



2[log

L(i) −log

L(i−1)] > 2[

(i) −

(i−1)]



∑

i=2



(

(i) −

(i−1)) > 2[

(i) −

(i−1)]



∼

6·10

−10

Isso justiﬁca os resultados encontrados nas simulac¸

oes, onde o AIC aparenta convergir

para a ordem verdadeira para os modelos mais complexos.

Observa-se que Katz desenvolveu as contas apenas para um caso simples, em que o

AIC apresenta uma probabilidade substancial de superestimac¸

ao. Os outros casos n

ao foram

mencionados. Isso e outras indicac¸

oes induzem ao pensamento err

oneo: “O AIC erra muito

sempre.”

2.3 Um Exemplo de Aplicac¸

Nas simulac¸

oes realizadas foram consideradas amostras geradas por algoritmos, que

representavam modelos markovianos “perfeitos”. Entretanto, como observou Akaike (1974),

a hip

otese da exist

encia de uma Cadeia de Markov, estacion

aria, que gerou a amostra pode

mudar completamente o comportamento dos estimadores. Por isso,

e interessante observar

como os m

etodos se comportam em “dados reais”.

Uma aplicac¸

ao simples e interessante de Cadeias de Markov de ordem superior

e a pro-

posta por McAlpine, Miranda & Hoggar (1999), que sugere a utilizac¸

ao desse procedimento

na modelagem de m

usicas. Isso pode ser utilizado n

ao apenas para gerar m

usicas aleatoria-

mente, mas tamb

em para analisar/classiﬁcar composic¸

oes existentes e gerar novas m

usicas a

partir dessas.

Nesse sentido, foi escolhido, a “Serenata N

13” de Mozart, em func¸

ao da sua grande

quantidade de notas musicais para a voz considerada (total de 21233). Os resultados est

na Tabela 2.10.

Como pode ser observado, os resultados da Tabela 2.10, s

ao satisfat

orios para assumir

a ordem como maior ou igual a 3, mas n

ao para assumi-la como 3. Mesmo assim,

poss

ıvel notar que os comportamentos dos estimadores foram semelhantes aos veriﬁcados

nas simulac¸

oes: para n pequeno todos subestimaram a ordem; o AIC teve melhor perfor-

mance no in

ıcio; o EDC

opt

foi mais eﬁciente que o BIC.

No caso considerado |E| = 7, a probabilidade de superestimac¸

ao do AIC

e pequena e o

tamanho da amostra n

ao foi grande o suﬁciente para a ocorr

encia de superestimac¸

ao.

Tabela 2.10: Ordens Indicadas pelos Estimadores para a “Serenata N

13” de Mozart

n EDC

opt

BIC AIC

91 0 0 0

101 0 0 1

161 1 0 1

171 1 0 1

181 1 1 1

581 1 1 2

1261 2 1 2

2851 2 2 2

4561 2 2 3

12871 3 2 3

21231 3 2 3

Este exemplo de aplicac¸

ao a dados reais

e bastante simples e a an

alise do comportamento

dos estimadores em dados reais mais relevantes, como por exemplo dados meteorol

ogicos,

ser

a objeto de estudos futuros.

Conclus

As simulac¸

oes realizadas indicaram que o estimador EDC

opt

tem melhor performance

que o BIC e que essa diferenc¸a aumenta em func¸

ao da complexidade das Cadeias de Markov

em an

alise.

Como tamb

em veriﬁcado por Katz (1981) para os estimadores AIC e BIC, observou-se

uma tend

encia desses estimadores e do EDC

opt

a subestimar a ordem quando o tamanho da

amostra n

e suﬁcientemente grande.

Vale ressaltar que Katz (1981), argumentando a inconsist

encia do AIC, realizou simulac¸

oes

apenas para o caso |E| = 2 e r = 1, em que o AIC apresenta probabilidade substancial de

superestimac¸

ao. Entretanto, veriﬁcamos no nosso trabalho que para casos de maior complex-

idade essa probabilidade pode ser consideravelmente pequena, at

e mesmo insigniﬁcante.

Refer

encias Bibliogr

aﬁcas

Akaike, H. 1974. “A new look at the statistical model identiﬁcation.” Automatic Control,

IEEE Transactions on 19(6):716–723.

Anderson, T. W. & Leo A. Goodman. 1957. “Statistical Inference about Markov Chains.”

The Annals of Mathematical Statistics 28(1):89–110.

Balzter, Heiko. 2000. “Markov chain models for vegetation dynamics.” Ecological Mod-

elling 126(2-3):139–154.

Bartlett, M. S. 1951. “The frequency goodness of ﬁt test for probability chains.” Proceedings

of the Cambridge Philosophical Society .

Beno

ıt, Gerald. 2005. “Application of Markov chains in an interactive information retrieval

system.” Inf. Process. Manage. 41(4):843–857.

Billingsley, Patrick. 1961. “Statistical Methods in Markov Chains.” The Annals of Mathe-

matical Statistics 32(1):12–40.

Chin, E. H. 1977. “Modelling daily precipitation occurrence process with Markov chain.”

Water Resources Res. 13:949–956.

Csiszar, Imre & Paul C. Shields. 2000. “The Consistency of the BIC Markov Order Estima-

tor.” The Annals of Statistics 28(6):1601–1619.

Dacunha-Castelle, Didier, Marie Duﬂo & David McHale. 1986. Probability and Statistics.

Vol. II Springer.

Doob, J. L. 1966. Stochastic Processes (Wiley Publications in Statistics). John Wiley & Sons

Inc.

Dorea, C. C. Y. 2008. “Optimal penalty term for EDC Markov chain order estimator.” An-

nales de l’Institut de Statistique de l’Universite de Paris (l’ISUP) 52:15–26.

Dorea, C. C. Y. & J. S. Lopes. 2006. “Convergence Rates for Markov Chain Order Estimates

Using EDC Criterion.” Bulletin of the Brazilian Mathematical Society 37:561–570.

Dorea, C. C. Y. & L. Zhao. 2004. “Exponential Bounds for the Rate of Convergence of

the EDC Criterion.” In: IX Congreso LatinoAmericano de Probabilidad y Estadistica

Matematica .

Feller, William. 1968. An Introduction to Probability Theory and Its Applications, Volume

1. Wiley.

Gates, P. & H. Tong. 1976. “On Markov chain modeling to some weather data.” J. Appl.

Meteor. 15:1145–1151.

Good, I. J. 1955. “The Likelihood Ratio Test for Markoff Chains.” Biometrika 42(3/4):531–

533.

Hoel, Paul G. 1954. “A Test for Markoff Chains.” Biometrika 41(3/4):430–433.

Hoon, Michiel J. L., Seiya Imoto & Satoru Miyano. 2002. Inferring Gene Regulatory Net-

works from Time-Ordered Gene Expression Data Using Differential Equations. In DS

’02: Proceedings of the 5th International Conference on Discovery Science. London,

UK: Springer-Verlag pp. 267–274.

Kannan, D. 1979. Introduction to Stochastic Processes. Elsevier Science.

Katz, Richard W. 1981. “On Some Criteria for Estimating the Order of a Markov Chain.”

Technometrics 23(3):243–249.

Kendall, Maurice, Alan Stuart & Keith J. Ord. 1991. Advanced Theory of Statistics: Classi-

cal Inference and Relationship. Vol. 2 6th ed. Oxford, UK: Oxford University Press.

Kuha, Jouni. 2004. “AIC and BIC: Comparisons of Assumptions and Performance.” Socio-

logical Methods Research 33(2):188+.

Kullback, S. 1959. Information theory and statistics. New York: John Wiley and Sons.

Kullback, S. & R. A. Leibler. 1951. “On Information and Sufﬁciency.” The Annals of Math-

ematical Statistics 22(1):79–86.

Lewin, Benjamin. 2004. Genes VIII. Upper Saddle River, NJ: Pearson Prentice Hall.

Li, Weidong. 2007. “A Fixed-Path Markov Chain Algorithm for Conditional Simulation of

Discrete Spatial Variables.” Mathematical Geology .

Lopes, Jaques Silveira. 2005. Determinac¸

ao da Ordem de uma Cadeia de Markov Usando o

Crit

erio EDC PhD thesis Universidade de Bras

ılia, UNB, Brasil.

Martell, David L. 1999. “A Markov chain model of day to day changes in the Canadian

forest ﬁre weather index.” International Jornal of Wildland Fire 9:265–273.

McAlpine, Kenneth, Eduardo Miranda & Stuart Hoggar. 1999. “Making Music with Algo-

rithms: A Case-Study System.” Comput. Music J. 23(2):19–30.

Meyn, S. P. & R. L. Tweedie. 1993. Markov Chains and Stochastic Stability. Springer-

Verlag, London.

Nuel, Gregory. 2007. “Numerical Solutions for Patterns Statistics on Markov Chains.” Sta-

tistical Applications in Genetics and Molecular Biology 5(1):26.

Park, S. K. & K. W. Miller. 1988. “Random number generators: good ones are hard to ﬁnd.”

Commun. ACM 31(10):1192–1201.

Raftery, Adrian E. 1985. “A Model for High-order Markov Chains.” J. R. Statist. Soc. B. .

Rao, C. R. 1973. Linear Statistical Inference and its Applications. 2nd ed. New York: J.

Wiley and Sons.

Rose, R J, D M Dick, R J Viken & J Kaprio. 2001. “Gene-environment interaction in patterns

of adolescent drinking: regional residency moderates longitudinalinﬂuences on alcohol

use.” Clinical and Experimental Research pp. 637–43.

Schwarz, Gideon. 1978. “Estimating the Dimension of a Model.” The Annals of Statistics

6(2):461–464.

Shao, J. 2007. Mathematical Statistics. New York: Springer Verlag.

Shibata, R. 1976. “Selection of the Order of an Autoregressive model by Akaike’s Informa-

tion Criterion.” Biometrika 63:117–126.

Silos, Pedro. 2006. “Assessing Markov chain approximations: A minimal econometric ap-

proach.” Journal of Economic Dynamics and Control 30(6):1063–1079.

Tong, H. 1975. “Determination of the Order of a Markov Chain by Akaike’s Information

Criterion.” Journal of Applied Probability 12(3):488–497.

Yamaoka, Kiyoshi, Terumichi Nakagawa & Toyozo Uno. 2005. “Application of Akaike’s in-

formation criterion (AIC) in the evaluation of linear pharmacokinetic equations.” Jour-

nal of Pharmacokinetics and Pharmacodynamics .

Zhao, L., C. Dorea & C. Gonc¸alves. 2001. “On Determination of the Order of a Markov

Chain.” Statistical Inference for Stochastic Processes 4(3):273–282.

ENDICE A -- Recursos Computacionais

Utilizados

Sem d

uvidas, a grande diﬁculdade em se gerar simulac¸

oes em escala tecnicamente sig-

niﬁcativa se reside na criac¸

ao do ambiente computacional adequado e eﬁciente.

Dentro desse problema, podemos citar:

• A escolha da linguagem – Geralmente linguagens mais f

aceis de utilizar n

ao s

as mais eﬁcientes computacionalmente. Por outro lado, em alguns casos, linguagens

eﬁcientes s

ao de dif

ıcil manutenc¸

ao e programac¸

ao. Para contornar esse problema,

pode-se utilizar diferentes linguagens em rotinas distintas;

• Adequac¸

ao do volume de dados – A gerac¸

ao de muitos dados necessita de maior

espac¸o para armazenagem e maior capacidade computacional para gerenci

a-lo. Deve-

se considerar a quantidade estritamente necess

aria para os resultados desejados.

A seguir, apresentamos uma pequena parcela do trabalho realizado na criac¸

ao dos pro-

gramas e scripts para a gerac¸

ao das simulac¸

oes, relat

orios e gr

aﬁcos. Para isso foi consider-

ado as seguintes premissas:

• Eﬁci

encia – R

apido computacionalmente;

• Escalabilidade – Possibilidade de aumentar a velocidade agregando mais poder de

processamento.

A.1 Programa

Dentre as linguagens avaliadas (“R”, “C”, “C++”, “Perl”, “Python” e “PHP”), notou-se,

indubitavelmente, que a linguagem “C”

e a que melhor atendia as premissas postas. Al

disso, como os procedimentos s

ao relativamente simples, n

ao haveria grande impacto na

facilidade de programac¸

ao. Para a gerac¸

ao de relat

orios foi utilizado a ferramenta “AWK”;

os gr

aﬁcos foram gerados utilizando-se do aplicativo “GnuPlot”; os dados armazenados no

banco de dados “PostgreSQL”.

Para solucionar o problema da escalabilidade, o programa foi dividido em pequenos

odulos

, que podem trabalhar em v

arios computadores em paralelo

No banco de dados, foram criadas tabelas para salvar as seguintes informac¸

oes

• Cadeias de Markov – Com suas respectivas matrizes de transic¸

ao;

• Amostras – Amostras geradas pelas cadeias;

• Log-verossimilhanc¸as Estimadas – Valores de

L(k), k = 0..7, de cada tamanho de

certa amostra;

• Ordens Estimadas – De cada Log-verossimilhanc¸a estimada;

• Tarefas – Utilizadas para orientar os trabalhos dos m

odulos.

Nas simulac¸

oes principais, foram salvas apenas as ordens estimadas para cada estimador

juntamente com alguns valores da log-verossimilhanc¸a.

A.1.1 Descric¸

ao das Principais Rotinas

As rotinas principais criadas foram:

• Simular – Desempenha o trabalho principal, gerando os modelos aleat

orios e salvando

os resultados num

ericos;

Arquitetura dashboard

Trabalho em cluster

Entidades.

• Gerar Relat

orio – Cria os indicadores apresentados nesse trabalho;

• Gerar Gr

aﬁco – Cria ﬁguras para facilitar a identiﬁcac¸

ao de “padr

oes” de comporta-

mento.

em dessas, foram geradas outras rotinas que auxiliaram nos testes e veriﬁcac¸

oes. Estas

ao s

ao enfatizadas nessa dissertac¸

ao, mas tamb

em est

ao dispon

ıveis.

A gerac¸

ao de relat

orios e gr

aﬁcos

e realizada computando diretamente no banco dedados

[usando a linguagem SQL]. A gerac¸

ao do relat

orio em Latex

e feita utilizando o aplicativo

AWK. Como a rotina “Simular”

e a principal nesse trabalho, apresentamos a descric¸

ao do

seu funcionamento abaixo.

1. Recupera no banco de dados uma tarefa a ser executada, obtendo os par

ametros da

ordem e tamanho do espac¸o de estados;

2. Cria na mem

oria a matriz de transic¸

ao. Para cada probabilidade condicionada (linha

da matriz)

e gerada a distribuic¸

ao particionando aleatoriamente, de forma uniforme

o intervalo [0, 1] e considerando as partic¸

oes de forma ordenada (quando utilizado o

modelo proposto por Raftery (1985) a l

ogica

e a mesma);

3. Gera uma amostra na mem

oria com comprimento de 100 milh

oes. Para iniciar a

amostra

e sempre considerado o condicionamento por “000...0”;

4. Para cada “sub-amostra”:

(a) Atualizaa matriz de contagem [aqui h

a o ganho ao considerar as“sub-amostras”];

(b) Calcula os valores da log-verossimilhanc¸a (de 0 a 7) e salva no banco;

edc

, ˆr

bic

e ˆr

aic

, salvando-os no banco;

A.2 Estimativas

O tempo de execuc¸

ao de cada rotina independente varia com o tipo da tarefa e/ou com o

volume de dados envolvido. Para ﬁns comparativos, apresentamos os tempos aproximados

medidos

na Tabela A.1.

Tabela A.1: Tempos de execuc¸

ao das rotinas

Rotina Tempo Aproximado de Execuc¸

Simular 5 a 180 segundos

Gerar Relat

orio 1 segundo a 2 dias

Gerar Gr

aﬁco 1 a 30 segundos

Pode-se rodar diversas rotinas emum mesmo computador, considerando uma por proces-

sador. Al

em disso, as rotinas podem trabalhar em computadores distintos ao mesmo tempo.

Isso aumenta consideravelmente a velocidade dos trabalhos.

A.3 Ambiente Utilizado

Para esse trabalho foi utilizado computadores com processadores AMD Turion 64. O

sistema operacional utilizado foi o Ubuntu Linux. Dentre as principais ferramentas desta-

camos o compilador GCC vers

ao 4.3.1 e a libc6 vers

ao 2.7. Os n

umeros aleat

orios foram

obtidos a partir das bibliotecas propostas por Park & Miller (1988).

Em um computador mono-processado AMD Turion 64 X2 800 Mhz.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 