Explicação intuitiva da periodicidade nas cadeias de Markov

16

Alguém pode me explicar de maneira intuitiva qual é a periodicidade de uma cadeia de Markov?

É definido da seguinte forma:

Para todos os estados em SEuS

= gcd { n N | p ( n ) i i > 0 } = 1dEu{nN|pEuEu(n)>0 0}=1

Obrigado pelo seu esforço!

Chris
fonte
1
Achei o artigo da Wikipedia sucinto e claro. Faz o trabalho para você?
Ciano
2
A definição em OP é chamada "aperioidic".
Jack

Respostas:

27

Primeiro de tudo, sua definição não está totalmente correta. Aqui está a definição correta da wikipedia, conforme sugerido por Cyan.


Periodicidade (fonte: wikipedia )

Um estado i possui o período k, se algum retorno ao estado i deve ocorrer em múltiplos de k etapas de tempo. Formalmente, o período de um estado é definido como

k = gcd{n:Pr(Xn=Eu|X0 0=Eu)>0 0}

(onde "gcd" é o maior divisor comum). Observe que, embora um estado tenha o período k, talvez não seja possível alcançá-lo em k etapas. Por exemplo, suponha que seja possível retornar ao estado em {6, 8, 10, 12, ...} intervalos de tempo; k seria 2, mesmo que 2 não apareça nesta lista.

Se k = 1, diz-se que o estado é aperiódico: retornos ao estado i podem ocorrer em momentos irregulares. Em outras palavras, um estado i é aperiódico se houver n tal que para todos n '≥ n,

Pr(Xn=Eu|X0 0=Eu)>0

Caso contrário (k> 1), o estado é considerado periódico com o período k. Uma cadeia de Markov é aperiódica se todos os estados forem aperiódicos.


Minha explicação

O termo periodicidade descreve se algo (um evento ou aqui: a visita de um determinado estado) está acontecendo em um intervalo de tempo regular. Aqui, o tempo é medido no número de estados que você visita.

Primeiro exemplo:

insira a descrição da imagem aqui

Agora imagine que o relógio representa uma cadeia de markov e a cada hora marca um estado, então temos 12 estados. Cada estado é visitado pelo ponteiro das horas a cada 12 horas (estados) com probabilidade = 1, portanto, o maior divisor comum também é 12.

Portanto, todo estado (hora) é periódico com o período 12.

Segundo exemplo:

stumartheumadstumaEueus

insira a descrição da imagem aqui

heumadsstumarttumaEueusstumart em que é 0.

heumadsheumadsheumadsheumads

tumaEueusstumartstumart

Steffen
fonte
0

n>0 0PEuEun=0 0PEuEuEu

>1gcdnPPEuEun=0 0gcd

Dilawar
fonte
Você está confundindo periodicidade com redutibilidade. Se a cadeia for irredutível, é possível ir de qualquer estado para qualquer outro estado. A periodicidade é importante no MCMC porque, mesmo que todos os estados possam ser alcançados (irredutibilidade), a convergência (as) para a distribuição de destino depende da propriedade adicional da aperiodicidade. Veja, por exemplo, "Variação assintótica e taxas de convergência de algoritmos MCMC quase periódicos" por Rosenthal (2001).
Anne van Rossum