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

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.