5.2 - Classificação de Estados em uma Cadeia de Markov

Você está aqui

Uma importante caracterização da cadeia de markov seria a classificação dos estados.

Definição 5.2.1:

O estado j é dito acessível pelo estado i se j pode ser alcançado a partir do estado i por um número finito de passos. Se dois estados i e j são acessíveis ou seja j é acessível a i e i é acessível a j então dizemos são comunicado.

Probabilisticamente temos que essa definição implica que

$ i \rightarrow j $ (j é acessível de i) se para algum $ 0\leq n\textless \infty $,  $ \mathbb{P}_{i,j}^n \textgreater 0 $

$ j \rightarrow i $ (i é acessível de j) se para algum $ 0\leq n\textless \infty $,  $ \mathbb{P}_{j,i}^n \textgreater 0 $

$ i \leftrightarrow j $ (i e j são comunicados) se para algum $ 0\leq n\textless \infty $, e se para algum $ 0\leq m\textless \infty $  $ \mathbb{P}_{i,j}^n \textgreater 0 $  $ \mathbb{P}_{j,i}^m \textgreater 0 $

Reciprocamente temos que

$ i \rightarrow j $ (j não é acessível de i) se para todo $ 0\leq n\textless \infty $,  $ \mathbb{P}_{i,j}^n = 0 $

$ j \rightarrow i $ (i não é acessível de j) se para todo $ 0\leq n\textless \infty $,  $ \mathbb{P}_{j,i}^n = 0 $

$ i \leftrightarrow j $ (i e j não são comunicados) se para todo $ 0\leq n\textless \infty $, e se para todo $ 0\leq m\textless \infty $  $ \mathbb{P}_{i,j}^n=0 $  $ \mathbb{P}_{j,i}^m= 0 $.

Notemos que como consequência desta definição temos que a relação de comunicação é uma relação de equivalência:

i) Reflexiva

De fato é reflexiva pois $ i\leftrightarrow i $ basta tomarmos n=0.

ii) Simétrica

Se $ i\leftrightarrow j $, então $ j\leftrightarrow i $

iii) Transitividade

Se $ i\leftrightarrow j $, e $ j\leftrightarrow k $, então $ i\leftrightarrow k $

Sabemos que existe dois inteiros r e s tal que:

$$\mathbb{P}_{i,j}^r\textgreater 0,~\mathbb{P}_{j,k}^s\textgreater 0.$$

 

Mas temos que

$$\mathbb{P}^{r+s}_{i,k}=\displaystyle \sum_{\ell}\mathbb{P}^{r}_{i,\ell}\mathbb{P}^{s}_{\ell,k}\geq \mathbb{P}^{r}_{i,j}\mathbb{P}^{s}_{j,k}\textgreater 0$$

 

Logo temos que $ i\rightarrow k $. Similarmente mostramos que existe um inteiro n tal que

$$\mathbb{P}^{n}_{k,i}\textgreater 0$$

 

Portanto $ k\rightarrow i $. Combinando esses dois resultados temos que $ i\leftrightarrow k $.

Definição 5.2.2:

Se a cadeia de markov tem todos os estados pertence a uma única classe de equivalência, então ele é dito irredutível.

Definição 5.2.3:

Um estado é dito recorrente se e somente se, partindo deste estado eventualmente retornamos ao mesmo estado, ou seja, um estado é recorrente é

se existe um $ n\textgreater 0 $ tal que $ f^{\star}_{i,i}=1 $, no qual $ f^{\star}_{i,i}=1 $ é definido da seguinte forma

$$f^{n}_{i,i}=\mathbb{P}[X_n=i,X_r\neq i|X_0=i]$ $r\in\{1,2,\cdots,n-1\}$$

 

então

$$f^{\star}_{i,i}=\displaystyle \sum_{n=1}^{\infty}f^{n}_{i,i}$$

 

note que $ f^{n}_{i,i} $ é a probabilidade de começarmos em i e retornarmos para i, em um tempo n.

Em termos de probabilidade temos temos que um estado é dito recorrente se e somente se $ f_{i,i}^{\star}=1 $.

Quando o estado i é recorrente podemos definir,

$$\mu_i=\sum_{n=1}^{\infty}n f_{i,i}^{n}$$

 

note que $ \mu $ define o valor esperado do numero de passos necessários para que retorne ao estado i. O qual é chamado de tempo de recorrência. Portanto $ \mu_i $ pode ser chamado de média de recorrência do estado i.

Usando a média de recorrência podemos classificar o seu estado recorrência nula ou recorrência

Dizemos que um estado recorrente é dito se um estado recorrente nulo se e somente se o tempo média recorrente é $ \infty $, ou seja, se $ \mu_i $.

Dizemos que um estado tem recorrência positiva se, e somente se, o tempo médio recorrente  é finito, ou seja, $ \mu_{i} $.

Definição 5.2.4:

Um estado é dito ser transiente se, e somente se, partindo do estado i, existe uma probabilidade positiva do processo não eventualmente retornar a este estado.

Isto implica que $ f^{\star}_{i,i}\textless 1 $.

Outra forma de classificarmos os estados em recorrente e transiente pode ser dado em termos das probabilidade $ \mathbb{P}_{i,i}^{n} $ que é a probabilidade do processo ocupar o estado i depois de n passos, dado que o estado inicial também foi i.

Teorema 5.2.1:

i) Um estado i é recorrente se

$$\displaystyle \sum_{n=1}^{\infty}\mathbb{P}_{i,i}^{n}=\infty$$

 

ii) Um estado i é transiente se

$$\displaystyle \sum_{n=1}^{\infty}\mathbb{P}_{i,i}^{n}\textless \infty$$

 

Demonstração:

Os estados de equivalência $ \displaystyle \sum_{n}f_{i,i}^{n}=1 $ e $ \displaystyle \sum_{n}\mathbb{P}_{i,i}^{n}=\infty $ o que nos mostra claramente a distinção entre $ f_{i,i}^{n} $ e $ \mathbb{P}^{n}_{i,i} $. $ f_{i,i}^{n} $ nos refere a probabilidade do primeiro retorno de i em n passos e $ \displaystyle \sum_{n}f_{i,i}^{n} $ é a probabilidade do processo retornar a i eventualmente.

Por outro lado temos que $ \mathbb{P}_{i,i}^{n} $ se refere a probabilidade do evento ocupar o estado i depois de n passos. Se o processo retorna ao estado i pelo menos uma vez, então ele vai retornar outras vezes assim temos que $ \displaystyle \sum_{n} \mathbb{P}_{ii}^{(n)} $ é uma soma infinita de números positivos. E portanto temos que essa soma é infinita, e portanto o resultado segue.

Seja $ Q_{ii}^{(N)} $ a probabilidade de partindo do estado i que a cadeia de markov retorne a este estado pelo menos N vezes. Então se tomarmos $ N\rightarrow \infty $ é a probabilidade de retornar infinita vezes no estado i. É claro que se o estado é recorrente então temos que

$$\displaystyle \lim_{N\rightarrow \infty}Q_{ii}^{(N)}=1$$

 

e por outro lado se o estado é dito ser transiente então  temos que

$$\displaystyle \lim_{N\rightarrow \infty}Q_{ii}^{(N)}=0$$

 

Definição 5.2.5:

O período de um estado i é definido como sendo o maior divisor comum de todos os inteiros $ n\geq 1 $, para o qual $ \mathbb{P}_{ii}^{n}\textgreater 0 $. Quando o período é 1, o estado é dito ser aperiódico.

Exemplo 5.2.1:

$$\mathbb{P}_k=\left( \begin{array}{c} ~~0/2 ~~ 1/2 ~~ 1/2 ~~\\ ~~ 1/2 ~~ 0/2 ~~ 1/2 ~~\\~~1/2 ~~ 1/2 ~~ 0/2 ~~ \\ \end{array}\right)$$

 

Analisando a matriz podemos ver que os todos os estados se interligam além disso $ \mathbb{P}_{ii}^{n}\textgreater 0 $, para $ n\geq 1 $, portanto o período que é o máximo divisor comum é 1.

Como todos os estados comunicam-se temos que existe uma única classe de equivalência.

Exemplo 5.2.2:

$$\mathbb{P}_k=\left( \begin{array}{c} ~~0/2 ~~ 0/2 ~~ 0/2 ~~2/2 ~~\\ ~~ 0/2 ~~ 0/2 ~~ 0/2 ~~2/2~~\\~~1/2 ~~ 1/2 ~~ 0/2 ~~ 0/2~~ \\~~ 0/2 ~~ 0/2 ~~ 2/2 ~~ 0/2 ~~\\ \end{array}\right)$$

 

Observando a matriz que todos os estados se comunicam, pois $ 1\rightarrow 4\rightarrow 3\rightarrow 1 $ ou $ 1\rightarrow 4\rightarrow 2\rightarrow 4\rightarrow 3 \rightarrow 1 $.

Portanto todos os estados pertencem a mesma classe de equivalência. Além disso temos que $ \mathbb{P}_{ii}^{n}\textgreater 0 $ é válido apenas para n=3, n=6 ou múltiplos de deles e portanto temos que o período que é o máximo divisor comum é 3.

Exemplo 5.2.3:

Um exemplo clássico de um processo Markoviano, seria o chamado passeio aleatório nos inteiros. Nesse exemplo podemos imaginar uma partícula qualquer, que se movimenta de acordo com a seguinte lei:

$$p(i,i+1)=p e p(i,i-1)=1-p$$

 

Note que essa partícula apenas se movimenta para frente dando um passo ou para trás dando apenas um passo. A respeito desse exemplo podemos nos fazer diversas perguntas, como por exemplo o sobre quais condições o passeio aleatório é recorrente ?

Note que o passeio aleatório é uma cadeia irredutível. Assim basta mostrarmos que um estado é recorrente que os demais também serão recorrentes. Vamos considerar a origem observe que para a partícula saindo da origem voltar a ela, necessitará de um número par de passos, pois nossa cadeia dá apenas um passo para frente ou para trás. Assim se n é ímpar $ \mathbb{P}^n_{0,0}=0 $, então

$$\displaystyle \mathbb{P}^{2n}_{0,0}=\left(\begin{array}{c}2n \\n\\ \end{array}\right) p^{n}(1-p)^n=\frac{(2n)!}{n!n!}p^n q^n$$

 

Podemos usar a formula de Stirling

$$\displaystyle \lim_{n\rightarrow \infty}\frac{n!}{n^ne^n\sqrt{2\pi n}}=1$$

 

Com alguma manipulação algebrica, temos que 

$$\displaystyle \lim_{n\rightarrow \infty}\frac{\mathbb{P}^{2n}(0,0)}{(4pq)^n/\sqrt{\pi n}}=1$$

 

Observe que quando $ p\neq 1/2 $ temos que $ 4pq\textless 1 $ e que quando $ p=1/2 $ temos que $ 4pq=1 $. Assim quando $ p=1/2 $ a série $ \displaystyle\sum_{n=1}^{\infty}\mathbb{P}^{2n}_{0,0} $ diverge e quando $ p\neq 1/2 $  a serie converge pois é basicamente a serie geométrica. Logo pelo Teorema 5.2.1, temos que o passeio aleatório é recorrente se, e somente se p=1/2.

Exemplo 5.2.4: 

Suponha que tenhamos 10 bolas, 5 pretas e 5 brancas e duas urnas A e B nas quais, são colocadas aleatoriamente 5 bolas em cada uma. Em cada passo 1 bola de cada urna é retirada e colocada na outra. Seja $ X_n= $número de bolas brancas na urna A, na etapa n. Qual a matriz de transição da cadeia.

Primeiramente note que temos um processo markoviano, pois claramente

$$\mathbb{P}(X_{n+1}=j|X_n=i_n,\cdots,X_0=i_0)=\mathbb{P}(X_{n+1}=j|X_n=i_n)$$

 

Calculemos nossa matriz de transição. Observe que para que o número de bolas se mantenha é necessário retirar duas bolas de mesma cor em cada urna. Assim

$$\mathbb{P}_{i,i}=\displaystyle \frac{i}{5}\frac{5-i}{5}+\frac{5-i}{5}\frac{i}{5}=\frac{2}{25}i(5-i)$$

 

Para que o número de bolas brancas aumente na urna A devemos pegar uma bola preta nela e uma bola branca na urna B. Então

$$\mathbb{P}{i,i+1}=\frac{5-i}{5}\frac{5-i}{5}=\frac{(5-i)^2}{25}$$

 

Para que o número de bolas brancas diminua na urna A devemos pegar uma bola branca nela e uma bola preta na urna B. Então

$$\mathbb{P}_{i,i-1}=\frac{i}{5}\frac{i}{5}=\frac{i^2}{25}$$

 

Logo a matriz de transição é dada por:

$$\mathbb{P}=\left( \begin{array}{c} ~00/25~~~25/25~~~00/25~~~00/25~~~00/25~~~00/25~\\ ~01/25~~~08/25~~~16/25~~~00/25~~~00/25~~~00/25~ \\ ~00/24~~~04/25~~~12/25~~~09/25~~~00/25~~~00/25~ \\ ~00/25~~~00/25~~~09/25~~~12/25~~~04/25~~~00/25~ \\ ~00/25~~~00/25~~~00/25~~~16/25~~~08/25~~~01/25~ \\ ~00/25~~~00/25~~~00/25~~~00/25~~~25/25~~~00/25~\\ \end{array}\right)$$

 

Exemplo 5.2.5: (Cadeia de Ehrenfest.)

Considere r bolas rotuladas de 1 a r. Algumas estão na caixa 1 e outras na caixa 2. A cada passo um número é escolhido aleatoriamente e a bola correspondente é movida de sua caixa para a outra. Seja $ X_n= $número de bolas na caixa 1 após n passos. Qual a matriz de transição deste processo ?

Primeiramente temos que

$$\mathbb{P}_{0,1}=1$$

$$\mathbb{P}_{r,r-1}=1$$

 

Para $ 0\textless i \textless r $ temos que

$$\mathbb{P}{i,i}=0$$

$$\displaystyle \mathbb{P}{i,i-1}=\frac{i}{r}$$

$$\displaystyle \mathbb{P}_{i,i+1}=\frac{(r-i)}{r}$$

 

Como exemplo tomemos r=4, então

$$\left(\begin{array}{c} ~0/4~~~4/4~~~0/4~~~0/4~~~0/4~\\ ~1/4~~~0/4~~~3/4~~~0/4~~~0/4~\\ ~0/4~~~0/4~~~3/4~~~0/4~~~0/4\\ ~0/4~~~1/2~~~0/4~~~1/2~~~0/4~\\ ~0/4~~~0/4~~~3/4~~~0/4~~~1/4~\\ ~0/4~~~0/4~~~0/4~~~4/4~~~0/4~\\ \end{array}\right)$$

 

Definição 5.2.5:

Dizemos que o estado i é fechado se ele pertence a uma classe $ \mathcal{C} $ fechada. Equivalentemente dizemos que $ i\in\mathcal{C} $ é um estado fechado se para todo $ j\nin \mathcal{C} $, temos que:

$$\mathbb{P}(T_j\textless \infty|X_0=i)=0$$

 

com $ T_j=\inf\{n\geq 1 |X_n=j\} $.

Teorema 5.2.2:

Um classe finita é recorrente se, e somente se é fechado.

Demonstração:

Iremos provar por contradição, assim seja $ \mathcal{C} $ uma classe finita fechada e transiente. Seja i e j em $ \mathcal{C} $. Pelo Teorema 5.2.1 temos que

$$\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}^{n}_{i,j}=0$$

 

e então 

$$\displaystyle \sum_{j\in\mathcal{C}}\lim_{n\rightarrow \infty}\mathbb{P}^{n}_{i,j}=0$$

 

Como $ \mathcal{C} $ é uma classe finita, podemos permutar o limite com a somatória.

$$\displaystyle \lim_{n\rightarrow \infty}\sum_{j\in \mathcal{C}}\mathbb{P}_{i,j}^{n}=0$$

 

mas $ \displaystyle \sum_{j\in\mathcal{C}}\mathbb{P}^n_{i,j}=\mathbb{P}(X_n\in \mathcal{C}|X_0=i) $. Desde que a classe é fechada temos que a soma das probabilidades dever ser igual a 1. O que contradiz a equação acima. Assim temos que $ \mathcal{C} $ é recorrente. O que mostra o resultado.

Exemplo 5.2.6:

Seja $ S=\{1,2,3,4,5,6\} $ e a matriz de transição

$$\mathbb{P}=\left(\begin{array}{c} ~1/6~~~5/6~~~0/6~~~0/6~~~0/6~~~0/6~\\ ~1/3~~~2/3~~~0/3~~~0/3~~~0/3~~~0/3~\\ ~0/2~~~0/2~~~1/2~~~0/2~~~1/2~~~0/2~\\ ~1/4~~~1/4~~~0/4~~~0/4~~~1/4~~~1/4~\\ ~0/2~~~0/2~~~1/2~~~0/2~~~1/2~~~0/2~\\ ~0/6~~~1/6~~~0/6~~~1/6~~~1/6~~~1/2~\\ \end{array} \right) $$

 

Encontre todas as classes e determine qual é transiente e qual é recorrente.

Primeiramente observe o diagrama que nos ajuda a identificar as classes.

Pelo diagrama podemos identificar as seguinte classes:

$$C_1=\{1,2\}\text{ recorrente}$$

$$C_2=\{3,5\}\text{ recorrente}$$

$$C_3=\{4,6\}\text{ transiente}$$

 

$ C_1 $ e $ C_2 $ são classes recorrentes, pois são fechadas pelo Teorema 5.2.2.

$ C_3 $ é transiente, pois não é fechada e portanto não recorrente.

Exemplo 5.2.7:

Dê um exemplo de uma classe fechada infinita a qual é transiente.

Um exemplo é o passeio aleatório, é fácil ver que este é fechado, pois todos os estados pertence a mesma classe.

Além disso, como $ S=\mathbb{Z} $ que é infinito enumerável, então temos uma classe fechada e infinita.

Como todos os estados pertence a mesma classe para mostrar que é transiente basta mostrar que

$$\sum_{n=0}^{\infty}p_n(0,0)\textgreater \infty$$

 

pela contra-positiva do Teorema 5.2.1.

Assim defina o passeio aleatório da seguinte forma:

$$p(i,i+1)=p$$

$$p(i,i-1)=1-p=q$$

 

Pelo exemplo 5.2.3, temos que

$$\sum_{n=0}^{\infty}p_n(0,0)\textgreater \infty$$

 

se, e somente se $ p\neq 1/2 $. Logo para $ p\neq 1/2 $ o passeio aleatório é transiente.

Processo Estocástico

Sobre o Portal Action

O Portal Action é mantido pela Estatcamp - Consultoria Estatística e Qualidade, com o objetivo de disponibilizar uma ferramenta estatística em conjunto com uma fonte de informação útil aos profissionais interessados.

Facebook

CONTATO

  •  Maestro Joao Seppe, 900, São Carlos - SP | CEP 13561-180
  • Telefone: (16) 3376-2047
  • E-Mail: [email protected]