bc1414 – Classificação de cadeias de Markov

A condição {p_{i,j}^{(n)}>0} para algum {n} equivale a {f_{i,j}>0} e significa que a partir do estado {i} a cadeia eventualmente atinge o estado {j}; nesse caso dizemos que {j} é acessível a partir de {i} e escrevemos {i\rightarrow j}. Quando {j} não é acessível a partir de {i} a probabilidade da cadeia chegar em {j} saindo de {i} é

\displaystyle  \mathop{\mathbb P}\left( \bigcup_{n\geq 0}[X_n=j] ~\big|~X_0=i \right)\leq \sum_{n\geq 0}\mathop{\mathbb P}\left( X_n=j ~|~X_0=i \right) =0.

Escrevemos {i \leftrightarrow j} se {i\rightarrow j} e {j\rightarrow i} e dizemos que os estados {i} e {j} se comunicam. Deixamos para o leitor a verificação de que { \leftrightarrow} define uma relação de equivalência sobre {S}, i.e.,

  1. {i \leftrightarrow i},
  2. se {i \leftrightarrow j}, então {j \leftrightarrow i},
  3. se {i \leftrightarrow k} e {k \leftrightarrow j} então {i \leftrightarrow j},

portanto, ela particiona {S} em classes de equivalência, que chamaremos classe de comunicação. A importância dessa partição é pelo fato enunciado no exercício a seguir.

Lema 25 Recorrência, transiência e período são propriedades de classe de equivalência de {\leftrightarrow}, isto é, dois estados que se comunicam tem a mesma classificação.

Demonstração: Sejam {i} e {j} estados que se comunicam e sejam {n} e {m} inteiros positivos tais que {p_{i,j}^{(n)}>0} e {p_{j,i}^{(m)}>0}. Para todo {t}

\displaystyle  p_{i,i}^{(t+n+m)} \geq p_{i,j}^{(n)}p_{j,j}^{(t)}p_{j,i}^{(m)}\ \ \ \ \ (54)

portanto, {p_{i,i}^{(t+n+m)} > 0} sempre que {p_{j,j}^{(t)}>0}.

Se fizermos {t=0} na equação (54), resulta que {p_{i,i}^{(n+m)}>0} portanto {\tau(i)} divide {n+m}. O lado esquerdo da equação (54) é nulo a menos nos períodos múltiplos de {\tau(i)}, portanto {p_{j,j}^{(t)}>0} só quando {t} é múltiplo de {\tau(i)}, portanto {\tau(j)} divide {\tau(i)}. Trocando os papéis de {i} e {j} concluiremos que {\tau(i)} divide {\tau(j)}. Portanto, os períodos são iguais.

Se somamos os dois lados (54) sobre todo natural {t} temos que se {\sum_t p_{j,j}^{(t)}} não converge, então também não converge o lado esquerdo, portanto se {j} é recorrente então também será o estado {i}. Trocando os papéis de {i} e {j} concluiremos que se {i} é recorrente então {j} é recorrente. Ademais, se {j} é transiente então também será {i} e vice-versa. \Box

Um conjunto {C\subset S} é irredutível se {i\leftrightarrow j} para todos {i,~j\in C}, portanto, cada classe de comunicação é um subconjunto irredutível maximal. Quando um conjunto não é irredutível, dizemos redutível. Quando há uma única classe de comunicação dizemos que a cadeia é uma cadeia de Markov irredutível. Dizemos que {C} é fechado se {p_{i,j} = 0} para {i\in C} e {j\not\in C}.

Exercício 104 Prove a seguinte afirmação. Se {i\in S} é recorrente então existe um único {C\subset S} fechado e irredutível ao qual {i} pertence. Ademais, para quaisquer {j,k\in C} vale que {f_{j,k}=f_{k,j}=1}.

No exemplo 119 é fácil ver a partir do diagrama que a cadeia é irredutível. A cadeia do exemplo 117, claramente, não é irredutível por causa dos estados absorventes {0} e {n}. Toda cadeia com pelo menos dois estados e com pelo menos um deles absorvente é uma cadeia redutível.

Num conjunto irredutível de estados todos os estados são do mesmo tipo, logo podemos classificar um conjunto de estados, ou a própria cadeia de Markov, irredutível como

  • aperiódica se todos os seus estados o forem;
  • periódica se todos os seus estados o forem;
  • transiente se todos os seus estados o forem;
  • recorrente se todos os seus estados o forem.

Observação 8 Notemos que a Observação 7 se aplica a uma classe de comunicação, ou a uma cadeia irredutível, pois os estados dela têm o mesmo período.

Exemplo 123

periodica4

Exemplo 124 No caso da cadeia representada abaixo

corrigido

A cadeia é redutível e o conjunto dos estados têm três classes de equivalência de comunicação {S=\big\{\{1,2\},\{3,4\},\{5,6\}\big\}}. Os conjuntos {\{1,2\}} e {\{5,6\}} são irredutíveis e recorrentes; {\{3,4\}} é transiente pois uma vez que a cadeia deixa o conjunto ela não volta mais a ele. Todos os estados têm período {1}, pois {p_{i,i}>0}, portanto a cadeia é aperiódica.

Exemplo 125 (passeio aleatório) Vejamos o caso do passeio aleatório não-simétrico em uma dimensão, onde

\displaystyle  p_{i,i+1}=p=1-p_{i,i-1}.

Claramente, a cadeia é irredutível logo todos os estados são ou recorrentes ou transientes. Fixemo-nos no estado {0} e vamos determinar {\displaystyle \sum_{n\geq 0} p_{0,0}^{(n)}}.

É impossível estar num estado par com um número ímpar de movimentos

\displaystyle p_{0,0}^{(2n-1)}=0,~\textrm{ para }n\geq 1.

Após {2n} passos a cadeia estará de volta em {0} se e só se metade dos passo foi num sentido (e.g., do estado atual para o maior, o que ocorre com probabilidade {p}) e metade no sentido oposto, portanto

\displaystyle  p_{0,0}^{(2n)} = \binom{2n}n p^n(1-p)^n = \frac{(2n)!}{n!}{n!} p^n(1-p)^n \sim \frac{(4p(1-p))^n}{\sqrt{\pi n}}

onde {a_n\sim b_n} significa que {\displaystyle \lim_{n\rightarrow\infty}(a_n/b_n)=1} e {n!\sim n^{n}\mathrm{e}^{-n}\sqrt{2\pi n}}. Agora, se {a_n\sim b_n} então {\sum_n a_n} converge se, e só se, {\sum_n b_n} converge, portanto precisamos estudar a convergência de

\displaystyle  \sum_{n\geq 1} \frac{(4p(1-p))^n}{\sqrt{\pi n}}.

No numerador {4p(1-p) \leq 1} e vale a igualdade se e somente se {p=1/2}. Portanto a série é infinita se e só se {p=1/2} e como a cadeia é irredutível e o {0} recorrente, a cadeia é recorrente. Se {p\neq 1/2} então a cadeia é transiente.

Exercício 105 Prove que toda classe de comunicação com estados recorrentes é fechada.

Exercício 106 Prove que toda classe de comunicação fechada e finita é recorrente.

Exercício 107 (Teorema de decomposição) O conjunto de estados {S} pode ser particionado como

\displaystyle S= T\cup C_1\cup C_2 \cup \cdots

de modo que {T} é o subconjunto dos estados transientes da cadeia e {C_i}, para todo {i}, são conjuntos fechados e irredutíveis de estados recorrentes. Prove essa afirmação.

Essa classificação diz-nos que quando estamos interessado no comprtamento de longo prazo basta estudarmos as cadeias irredutíveis. Se {X_0} está em alguma classe de equivalência de comunicação { C_\ell} que é recorrente, então a evolução da cadeia se restringe a essa classe pois, assumindo que {i \in C_\ell} e {j\not\in C_\ell} de modo que {i\rightarrow j}, por conseguinte {j\not\rightarrow i}, temos de {[X_1=j] \subset \bigcup_{n\geq 1}[X_n\neq i]}

\displaystyle  \mathop{\mathbb P}\left(\bigcup_{n\geq 1}[X_n\neq i] ~\bigg|~ X_0=i \right) \geq p_{i,j} >0

contrariando o fato de {i} ser recorrente. Se, por outro lado, {X_0} no conjunto {T} dos estados transientes implica em ou a cadeia ficar em {T} (consulte seção XV.8 do Feller para a probabilidade desse evento) ou se mover para algum { C_\ell} e não sair mais dessa classe.

Exemplo 126 Uma cadeia de Markov com estados {\{1,2\}} e matriz de transições

\displaystyle  P= \begin{pmatrix} 1&0\\1/2&1/2 \end{pmatrix}

não corresponde a uma cadeia irredutível pois para todo inteiro {k>0}

\displaystyle  P^k= \begin{pmatrix} 1&0\\\frac {2^{k}-1}{2^k}& \frac 1{2^k} \end{pmatrix}

portanto {1\not\rightarrow 2}.

Exemplo 127 Uma cadeia com estados {\{1,2,3\}} e matriz de transições

\displaystyle  P= \begin{pmatrix} 1/3&2/3&0\\ 1&0&0\\ 0&0&1 \end{pmatrix}

é redutível pois {P^k} é da forma

\displaystyle  \begin{pmatrix} \frac x{3^k}& \frac{3^k-x}{3^k} &0\\ \frac y{3^{k-1}}& \frac{3^{k-1}- y}{3^k} &0\\ 0&0&1 \end{pmatrix}

com {0<x<3^k} e com {0<y<3^{k-1}} e para todo inteiro {k>0}.

Exemplo 128 Uma cadeia com 4 estados e matriz de transições

\displaystyle  P= \begin{pmatrix} 0& 4/5& 0& 1/5\\ 1& 0 & 0& 0\\ 0& 2/3& 0& 1/3\\ 0& 0 & 1& 0 \end{pmatrix}

é periódica pois {P^k} na posição {(1,1)} é diferente de zero somente para {k} par, em outras palavras, a partir do estado {1} a cadeia somente volta ao estado {1} em número par de passos.

Exemplo 129 Considere uma cadeia de Markov com matriz de transição

\displaystyle  P= \begin{pmatrix} 1/2 & 1/2 & 0 & 0\\ 1/4 & 3/4 & 0 & 0\\ 1/4 & 1/4 & 1/4 & 1/4\\ 0 & 0 & 0 & 1\\ \end{pmatrix}

cujas classes de comunicação são {\{0,1\}} que é recorrente, {\{3\}} que é absorvente e {\{2\}} que é transiente. Se o inicio é no estado {2}, então a probabilidade {p} com que a cadeia entra na classe recorrente {\{0,1\}} é, condicionando em {X_1}, dada por

\displaystyle p = \frac 14 1 + \frac 14 1+ \frac 14 p + \frac 14 0 = \frac 12 + \frac 14 p

logo {p=\frac 23}; e com probabilidade {\frac 13} a cadeia é absorvida em {3}.

No caso da matriz de transição

\displaystyle  Q= \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0\\ 1/3 & 2/3 & 0 & 0 & 0 & 0\\ 1/3 & 0 & 0 & 1/3 & 1/6 & 1/6\\ 1/6 & 1/6 & 1/6 & 0 & 1/3 & 1/6\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0\\ \end{pmatrix}

as classes de comunicação são {\{0,1\}}, {\{2,3\}} e {\{4,5\}}, respectivamente, recorrente aperiódica, transiente e recorrente periódica. Se {p_i} é a probabilidade de entrar na primeira classe descrita acima a partir do estado {i}, {i=2,3}, então, condicionando em {X_1},

\displaystyle  \begin{array}{rcl}  p_2 &=& \frac 121 + 0\cdot 1 + 0 p_2 + \frac 13 p_3 + \frac 16 0 + \frac 16 0 \\ p_3 &=& \frac 161 + \frac 161 + \frac 16 p_2 + 0 p_3 + \frac 13 0 + \frac 16 0 \\ \end{array}

cuja solução é {p_2 = \frac 8{17}} e {p_3 = \frac 7{17}}.

Uma resposta em “bc1414 – Classificação de cadeias de Markov

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s