Figura III.1: Representação gráfica de uma Cadeia de Markov de 6 estados; um arco direcionado de \(i\) para \(j\) é incluído no gráfico se, e somente se, \(p_{i,j}> 0\).
Seja \(\{C_t\}\) Cadeia de Markov estacionária com espaço de estados \(S\) e sejam \(x,y\in S\), estados da cadeia.
Dizemos que o estado \(y\) é acessível do estado \(x\) se \(\rho_{x,y} > 0\). Escrevemos \(x \rightarrow y\).
Por exemplo, na Figura III.1, há uma caminhada do nó 1 ao nó 3, passando pelo nó 2, então o estado 3 é acessível a partir de 1. Não há nenhuma caminhada do nó 5 ao 3, então o estado 3 não é acessível a partir de 5. O estado 2 é acessível a partir de si mesmo, mas o estado 6 não é acessível a partir de si mesmo. Para ver o significado probabilístico de acessibilidade, suponha que um passeio \(i_0, i_1,\cdots, i_n\) exista do nó \(i_0\) para \(i_n\). Então, condicionado em \(C_0 = i_0\), há uma probabilidade positiva, \(p_{{i_0},{i_1}}\), de que \(C_1 = i_1\) e, conseqüentemente uma vez que \(p_{{i_0},{i_1}}> 0\), há uma probabilidade positiva de \(C_2 = i_2\). Continuando esse argumento, há uma probabilidade positiva de que \(C_n = i_n\), de modo que \(P(C_n = i_n | C_0 = i_0)> 0\). Da mesma forma, se \(P(C_n = i_n | C_0 = i_0)> 0\), então deve existir uma caminhada de \(n\) passos de \(i_0\) a \(i_n\). Para concluir o exemplo da Figura III.1, \(p_{1,3}^{(2)} = p_{1,2}p_{2,3}> 0\). Por outro lado, \(p_{5,3}^{(n)} = 0\) para todo \(n\geq 1\).
Figura III.1: Representação gráfica de uma Cadeia de Markov de 6 estados; um arco direcionado de \(i\) para \(j\) é incluído no gráfico se, e somente se, \(p_{i,j}> 0\).
Pode-se demonstrar que \(y\) é acessível desde \(x\) se, e somente se, \(p_{x,y}^{(n)}>0\), para algum \(n\geq 1\). Também é possível mostrar que se \(y\) for acessível de \(x\) e se \(z\) for acessível de \(y\), então \(z\) é acessível desde \(x\). Isto implica que esta propriedade dos estados é transitiva e, assim, se \begin{equation*} p_{x,y}^{(n)} >0 \qquad \mbox{e} \qquad p_{y,z}^{(m)}>0 \qquad \mbox{então} \qquad p_{x,z}^{(n+m)}>0\cdot \end{equation*}
Dizemos que o estado \(x\) se comunica com o estado \(y\) se \(x\) é acessível do estado \(y\) e se \(y\) for acessível do estado \(x\), ou seja, se \(x \rightarrow y\) e \(y \rightarrow x\). Escrevemos \(x \rightleftharpoons y\).
Esta definição introduz uma relação de equivalência no conjunto de estados. Isso significa, que esta relação satisfaz as seguintes propriedades:
No Exemplo I.7 temos que a potência 1000 da matriz de probabilidades de transição é da forma:
Assim percebemos que nesta cadeia todos os estados se comunicam.
A relação de equivalência no conjunto \(S\) o decompõe em classes de equivalência. Se \(S\) for enumerável, isso significa que \(S\) pode ser particionado em subconjuntos \(S_1, S_2, S_3,\cdots\) de \(S\) de modo que; dois elementos \(x, y\in S\) tais que \(x \rightleftharpoons y\) se, e somente se, eles pertencerem ao mesmo subconjunto da partição.
Se um estado \(x\) pertence a \(S_u\) para algum \(u\), dizemos que \(x\) é um representante da classe de equivalência \(S_u\). Para a relação de equivalência específica que estamos considerando aqui, chamamos cada conjunto \(S_u\) de uma classe comunicante de \(\mathcal{P}\). Observe, em particular, que quaisquer duas classes comunicantes são iguais ou disjuntas, e sua união é o conjunto completo de estados.
Uma classe de comunicação é considerada fechada se nenhum estado fora da classe puder ser alcançado a partir de qualquer estado dentro dela. Portanto, uma vez que a cadeia de Markov atinge uma classe de comunicação fechada, ela não pode mais escapar dela. Se o conjunto de pontos únicos {i} compreende uma classe de comunicação fechada, dizemos que i é um estado absorvente. A cadeia de Markov, ou matriz estocástica, é chamada de irredutível se S consiste em uma única classe comunicante.
Seja \(x\) um estado recorrente e suponha que \(x\) se comunica com \(y\). Então, \(y\) é recorrente e \(\rho_{x,y}=\rho_{y,x}=1\).
Consideremos \(y\neq x\), caso contrário não teríamos nada a provar. Dado que \begin{equation} P_x(T_y < \infty) \, = \, \rho_{x,y} > 0, \end{equation} vemos que \(P_x(T_y=n) > 0\) para algum inteiro positivo \(n\). Seja \(n_0\) o menor de tais inteiros positivos, isto é, seja \begin{equation} n_0 \, = \, \min\big\{ n\geq 1 \, : \, P_x(T_y=n) > 0 \big\}\cdot \end{equation} Segue das expressões acima que \(p_{x,y}^{(n_0)} > 0\) e \begin{equation} p_{x,y}^{(m)} \, = \, 0, \qquad 1\leq m < n_0\cdot \end{equation} Dado que \(p_{x,y}^{(m)} > 0\), podemos encontrar estados \(y_1,\cdots,y_{n_0-1}\) tais que \begin{equation*} P_x(C_1=y_1,\cdots,C_{n_0-1}=y_{n_0-1},C_{n_0}=y)=p_{x,y_1}\cdots p_{y_{n_0-1},y}>0\cdot \end{equation*} Nenhum dos estados \(y_1,\cdots,y_{n_0-1}\) iguais a \(x\) ou \(y\). Se algum deles fosse igual \(x\) ou \(y\), seria possível ir de \(x\) para \(y\) com probabilidade positiva em menos de \(n_0\) passos, em contradição com \(p_{x,y}^{(m)} \, = \, 0\), \(1\leq m < n_0\). Vamos agora mostrar que \(\rho_{y,x}=1\). Suponha que, ao contrário disso, \(\rho_{y,x}< 1\). Então, se a cadeia partir de \(y\) tem probabilidade positiva \(1-\rho_{y,x}\) de nunca atingir \(x\). Mais ao ponto, uma Cadeia de Markov partindo do estado \(x\) tem a probabilidade positiva \(p_{x,y_1}\cdots p_{y_{n_0-1},y}(1-\rho_{y,x})\) de visitar os estados \(y_1,\cdots,y_{n_0-1},y\) sucessivamente nos primeiros \(n_0\) tempos e nunca retornar a \(x\) depois do tempo \(n_0\). Mas, se isso acontecer, a Cadeia de Markov nunca retornará a \(x\) a qualquer tempo \(n\ge 1\), portanto temos uma contradição com a suposição de que \(x\) é um estado recorrente.
Dado que \(\rho_{y,x}=1\), existe um inteiro positivo \(n_1\) tal que \(\gamma^{(n_1)}_{y,x}>0\). Agora \begin{equation*} \begin{array}{rcl} p^{(n_1+n+n_0)}_{y,y} & = & \displaystyle P_y(C_{n_1+n+n_0}=y) \\[0.6em] & \ge & \displaystyle P_y(C_{n_1}=x,C_{n_1+n}=x,C_{n_1+n+n_0}=y) \\[0.6em] & = & \displaystyle p^{(n_1)}_{y,x}p^{(n)}_{x,x}p^{(n_0)}_{x,y}\cdot \end{array} \end{equation*} Portanto, \begin{equation*} \begin{array}{rcl} \mbox{E}_y\big(N(y)\big) & \ge & \displaystyle \sum_{n=n_1+1+n_0}^\infty p^{(n)}_{y,y} \,= \, \displaystyle \sum_{n=1}^\infty p^{(n_1+n+n_0)}_{y,y} \\[1.1em] & \ge & \displaystyle p^{(n_1)}_{y,x}p^{(n_0)}_{x,y}\sum_{n=1}^\infty p^{(n)}_{x,x} \, = \, \displaystyle p^{(n_1)}_{y,x}p^{(n_0)}_{x,y}\mbox{E}_x\big(N(x)\big) \, = \, \infty, \end{array} \end{equation*} do qual segue que \(y\) é também um estado recorrente.
Desde que \(y\) é recorrente e \(y\) se comunica com \(x\), vemos da primeira parte da demonstração do teorema que \(\rho_{x,y}=1\). Isto completa a prova do teorema.
▉Um conjunto \(F\subset S\) de estados é dito ser um conjunto fechado se não existirem estados dentro de \(F\) que se comuniquem com qualquer estado fora de \(F\).
Esta definição significa que se \(F\) é um conjunto fechado, então \begin{equation} \rho_{x,y} \, = \, 0, \qquad x\in F \quad \mbox{e} \quad y\notin F\cdot \end{equation} De maneira equivalente, \(F\) é um conjunto de estados fechado se, e somente se, \begin{equation} p_{x,y}^{(n)} \, = \, 0, \qquad x\in F, \quad y\notin F \quad \mbox{e} \quad n\geq 1\cdot \end{equation}
Mais ainda, da condição fraca que \begin{equation} p_{x,y} \, = \, 0, \qquad x\in F \quad \mbox{e} \quad y\notin F, \end{equation} podemos demonstrar que \(F\) seja um conjunto de estados fechado. Se a expressão acima se cumpre, então para \(\in F\) e \(y\notin F\) temos que \begin{equation} p_{x,y}^{(2)} \, = \, \sum_{z\in S} p_{x,z}p_{z,y} \, = \, \sum_{z\in F} p_{x,z}p_{z,y} \, = \, 0, \end{equation} e a condição \(p_{x,y}^{(n)} = 0, \, x\in F, \, y\notin F, \, n\geq 1\) se cumpre por indução. Significa que, se \(F\) for um conjunto de estados fechados, então a Cadeia de Markov começando em \(F\), estará em \(F\) o tempo todo com probabilidade um. Se \(a\) é um estado absorvente então o conjunto \(\{a\}\) é fechado.
Um conjunto \(F\subseteq S\) de estados é dito ser um conjunto irredutível se cada estado \(x\in F\) se comunica com qualquer outro estado \(y\in F\).
Deduzimos, pelo Teorema III.1, que se \(F\) for um conjunto de estados irredutível fechado; então um ou outro: ou todo estado em \(F\) é recorrente ou todo estado em \(F\) é transiente.
Seja \(F\) um conjunto irredutível fechado de estados recorrentes. Então:
Consequência imediata do Teorema III.1.
▉Uma Cadeia de Markov irredutível é uma cadeia cujo espaço de estados é irredutível, ou seja, uma cadeia em que cada estado se comunica de volta consigo e também com todos os outros estados. Tal Cadeia de Markov é necessariamente quer uma cadeia transiente ou uma cadeia recorrente. O Teorema III.2 implica, em particular, que uma Cadeia de Markov irredutível recorrente visita todos seus estados infinitas vezes com probabilidade um.
Seja \(F\) um conjunto finito e fechado de estados irredutíveis. Então cada estado em \(F\) é recorrente.
Sabemos, pelo Teorema II.10 que se \(S\) é finito contém pelo menos um estado recorrente. O mesmo argumento mostra que qualquer conjunto finito de estados contém, ao menos, um estado recorrente. Seja agora \(F\) finito irredutível fechado. Sabemos que todo estado em \(F\) é transiente ou todo estado em \(F\) é recorrente e que \(F\) tem, ao menos, um estado recorrente. Segue então que todo estado em \(F\) é recorrente.
▉Faremos um resumo dos resultados até agora para Cadeias de Markov com espaço de estados finito. O Teorema III.3 nos disse que se a cadeia for irredutível ela deve ser recorrente. Se a cadeia não for irredutível, podemos utilizar os Teoremas III.1 e III.3 para identificar quais estados são recorrentes e quais são transientes. Com o exemplo a seguir mostramos o procedimento de identificação de estados recorrentes e transientes de duas formas: de maneira teórica e também de maneira numérica.
Considere uma Cadeia de Markov com espeço de estados \(S=\{0,1,2,3,4,5\}\) e matriz de transição: \begin{equation} \mathcal{P} \, = \, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 & 0 & 0 \\ 0 & \frac{1}{5} & \frac{2}{5} & \frac{1}{5} & 0 & \frac{1}{5} \\ 0 & 0 & 0 & \frac{1}{6} & \frac{1}{3} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{4} & 0 & \frac{3}{4} \end{pmatrix}\cdot \end{equation}
Queremos determinar quais estados são recorrentes e quais estados são transientes.
Como primeiro passo no estudo, vamos determinar por inspeção quais estados se comunicam com quais outros. Isto pode ser realizado indicando a matriz da seguinte forma: \begin{equation} \mathcal{P} \, = \, \begin{pmatrix} + & 0 & 0 & 0 & 0 & 0 \\ + & + & + & + & + & + \\ + & + & + & + & + & + \\ 0 & 0 & 0 & + & + & + \\ 0 & 0 & 0 & + & + & + \\ 0 & 0 & 0 & + & + & + \end{pmatrix}\cdot \end{equation}
O elemento \((x,y)\) desta matriz é \(+\infty\) ou \(0\) de acordo com \(\rho_{x,y}\), se for positivo ou zero. Isto é, de acordo se \(x\) se comunica ou não com \(y\). Claro que, se \(p_{x,y}>0\) então \(\rho_{x,y}>0\). O contrário não é verdade em geral. Por exemplo, \(p_{2,0}=0\) mas \begin{equation} p^{(2)}_{2,0} \, = \, p_{2,1}p_{1,0} \, = \, \frac{1}{5}\times \frac{1}{4} \, = \, = \, \frac{1}{20}\, > \,0, \end{equation} portanto, \(\rho_{2,0}>0\).
O estado \(0\) é absorvente, logo recorrente. Vemos da matriz de \(+\) e zeros que \(\{3,4,5\}\) é um conjunto de estados fechado irredutível. Pelo Teorema III.3 este resultado implica que os estados 3, 4 e 5 são recorrentes. Os estados 1 e 2 se comunicam com o 0, mas nenhum deles pode ser alcançado desde o 0. Do Teorema III.1, por negação, temos que os estados 1 e 2 devem ser transientes. Resumindo, os estados 1 e 2 são transientes e os estados 0, 3, 4 e 5 são recorrentes.
Neste exemplo, o primeiro tabalho foi identificar quais estados se comunicam. Isto pode ser realizado utilizando as linhas de comando a seguir:
Uma outra forma de identificar quais estados são transientes e quais recorrentes é calculando uma potência elevada da matriz de transição, por exemplo \begin{equation*} \mathcal{P}^{2000} \, = \, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0.6 & 0 & 0 & 0.1 & 0.03 & 0.27 \\ 0.2 & 0 & 0 & 0.2 & 0.07 & 0.53 \\ 0 & 0 & 0 & 0.25 & 0.08 & 0.67 \\ 0 & 0 & 0 & 0.25 & 0.08 & 0.67 \\ 0 & 0 & 0 & 0.25 & 0.08 & 0.67 \end{pmatrix} \end{equation*}
Identificamos que os estados 0, 3, 4 e 5 são recorrentes e, por negação do Teorema III.1, vemos que se \(x\) for recorrente e \(y\) transiente, então \(x\) não se comunica com \(y\). Justamente é isso que observamos na matriz anterior dos estados 1 e 2, por isso concluímos que estes estados são transientes.
Mais ainda, podemos auxiliarmos do pacote de funções markovchain. Neste pacote, a função transientStates, identifica quais estados são transientes, basta somente digitar:
Para construirmos o objeto markovchain. Nosso objetivo é identificar os estados transientes, então digitamos:
Na primeira linha, onde aparecer um valor zero ou próximo de zero significa que o estado correspondente não é recorrente. Ou seja, identificamos que os estados 0, 3, 4 e 5 são recorrentes.
Seja \(S\) o espaço de estados de uma Cadeia de Markov. Denotaremos por \(S_T\) o conjuntos dos estados transientes em \(S\) e por \(S_R\) o conjunto dos estados recorrentes em \(S\). No Exemplo III.2, \begin{equation} S_T=\{1,2\} \qquad \mbox{e} \qquad S_R=\{0,3,4,5\}\cdot \end{equation} Ainda o conjunto \(S_R\) pode ser decomposto nos conjuntos fechados disjuntos e irredutíveis de estados \(F_1=\{0\}\) e \(F_2=\{3,4,5\}\). O teorema a seguir mostra que esta decomposição sempre é possível qualquer seja \(S_R\) não vazio.
Suponha que o conjunto \(S_R\) de estados recorrentes em \(S\), seja não vazio. Então, \(S_R\) é a união finita ou enumerável de conjuntos fechados disjuntos e irredutíveis \(F_1,F_2,\cdots\).
Escolhemos \(x\in S_R\) e seja \(F\) o conjunto de todos os estados \(y\in S_R\) tais que \(x\) comunica \(y\). Devido a \(x\) ser recorrente \(\rho_{x,x}=1\) e, portanto, \(x\in F\). Verifiquemos agora se \(F\) é um conjunto fechado e irredutível. Suponhamos que \(y\) pertence a \(F\) que \(y\) se comunica com \(z\). Devido a \(y\) ser recorrente, segue pelo Teorema III.1 que \(z\) é recorrente. Logo, \(z\in F\). Isto mostra que \(F\) é fechado. Suponhamos agora que \(y\) e \(z\) estejam ambos em \(F\). Foi nossa escolha que \(x\) fosse recorrente e que se comunica com \(y\), segue do Teorema 15 que \(y\) se comunica com \(x\). Dado que \(y\) se comunica com \(x\) e \(x\) se comunica com \(z\), concluímos que \(y\) se comunica com \(z\). Isto mostra que \(F\) é irredutível.
Para concluir a demonstração devemos provar que se \(F\) e \(D\) forem dois subconjuntos fechados irredutíveis de \(S_R\) então ou são disjuntos ou são idênticos. Suponhamos que não sejam disjuntos e que exista um estado \(x\) que pertença a ambos, \(x\in F\) e \(x\in D\). Escolhemos um \(y\in F\). Sabemos que \(x\) se comunica com \(y\), devido a \(x\) pertencer a \(F\) e \(F\) ser um conjunto irredutível. Dado que \(D\) é fechado, \(x\) que está em \(D\) e se comunica com \(y\), implica que \(y\) está também em \(D\). Logo, todo estado em \(F\) está tamb&eeacuém;m em \(D\). Similarmente, todo estado em \(D\) está também em \(F\) logo, \(F\) e \(D\) são idênticos.
▉Podemos usar nossa decomposição do espaço de estados de uma Cadeia de Markov para entender o comportamento de um sistema deste tipo. Se a Cadeia de Markov começa em um dos conjuntos de estados recorrentes fechados irredutíveis \(F_i\), ela permanece em \(F_i\) para sempre e, com probabilidade um, visita todos os estados \(F_i\) infinitas vezes. Se a Cadeia de Markov começa no conjunto de estados transientes \(S_T\), ou ela permanece em \(S_T\) para sempre ou, em algum momento, entra num dos conjuntos \(F_i\) e permanece lá a partir desse momento, mais uma vez visitando todos os estados em \(F_i\) infinitas vezes.
Queremos saber qual a probabilidade de uma cadeia, começando em qualquer estado \(x\), chegar a um destes conjuntos fechados irredutíveis de estados recorrentes?
Sabemos, pela Definição II.3, que se \(F\) for um conjunto fechado de estados irredutíveis recorrentes então \begin{equation} \rho_{_{x,F}} \, = \, P_x(T_F < \infty), \end{equation} é a probabilidade de que uma Cadeia de Markov a partir de \(x\), eventualmente, visite o conjunto \(F\).
Desde que a cadeia continue permanentemente em \(F\), uma vez que atinge este conjunto, chamamos de \(\rho_{_{x,F}}\) a probabilidade que uma cadeia a partir de \(x\) seja absorvida pelo conjunto \(F\). Logico que \(\rho_{_{x,F}}=1\), \(x\in F\) e \(\rho_{_{x,F}}=0\) se \(x\) for um estado recorrente que não esteja em \(F\). Ele não é tão claro como calcular \(\rho_{_{x,F}}\) para \(x\in S_T\), o conjunto de estados transientes.
Se houver apenas um número finito de estados transientes e, em particular, se \(S\) em si for finito é sempre possível calcular \(\rho_{_{x,F}}\), \(x\in S_T\) resolvendo um sistema de equações lineares em que há tantas equações como incógnitas, ou seja, os elementos de \(S_T\).
Para entender por que este é o caso, observemos que, se a cadeia partir de \(x\), pode entrar em \(F\) apenas entrando em \(C\) no tempo 1 ou por estar em \(S_T\) no tempo 1 e entrando em \(F\) em algum momento futuro. O primeiro evento tem probabilidade \(\sum_{y\in F} p_{x,y}\) e o último evento tem probabilidade \(\sum_{y\in S_T} p_{x,y}\rho_{_{y,F}}\). Assim \begin{equation} \rho_{_{x,F}} \, = \, \sum_{y\in F} p_{x,y}+\sum_{y\in S_T} p_{x,y}\rho_{_{y,F}}, \qquad x\in S_T\cdot \end{equation}
A equação acima se cumpre sempre que \(S_T\) seja finito ou infinito, mas está longe de ser claro como a resolver para as incógnitas \(\rho_{_{x,F}}\), \(x\in S_T\) quando \(S_T\) é infinito. Uma dificuldade adicional ao fato de \(S_T\) ser infinto acontece quando a equação acima não necessariamente tem solução única. Afortunadamente esta dificuldade não acontece quando \(S_T\) é finito.
Suponhamos que o conjunto dos estados transientes \(S_T\) seja finito e que \(F\) seja o conjunto fechado irredutível dos estados recorrentes da cadeia. Então, o sistema de equações \begin{equation} f(x)=\sum_{y\in F} p_{x,y}+\sum_{y\in S_T} p_{x,y}\, f(y), \qquad x\in S_T, \end{equation} tem por solução única \begin{equation} f(x)=\rho_{_{x,F}}, \qquad x\in S_T\cdot \end{equation}
Se a primeira expressão no teorema for válida, então \begin{equation} f(y)=\sum_{z\in F} p_{y,z}+\sum_{z\in S_T} p_{y,z}\, f(z), \qquad y\in S_T\cdot \end{equation} Substituindo-a, temos que \begin{equation} \begin{array}{rcl} f(x) & = & \displaystyle \sum_{y\in F} p_{x,y}+\sum_{y\in S_T} \sum_{z\in F} p_{x,y}p_{y,z} \, + \, \displaystyle \sum_{y\in S_T} \sum_{z\in S_T} p_{x,y}p_{y,z}\, f(z)\cdot \end{array} \end{equation} A soma dos primeiros dois termos é justamente \(P_x(T_F\le 2)\) e o terceiro termo se reduz a \(\sum_{z\in S_T} p^{(2)}_{x,z} \, f(z)\), o qual é o mesmo do que \(\sum_{y\in S_T} p^{(2)}_{x,y}\, f(y)\). Então \begin{equation} f(y)=P_x(T_F\le 2)+\sum_{y\in S_T} p^{(2)}_{x,y}\, f(y)\cdot \end{equation} Repetindo este argumento infinitas vezes ou utilizando a indução matemática, concluímos que para todos os inteiros positivos \(n\) se satisfaz que \begin{equation} f(y)=P_x(T_F\le n)+\sum_{y\in S_T} p^{(n)}_{x,y}\, f(y), \qquad x\in S_T\cdot \end{equation} Dado que cada \(y\in S_T\) é transiente, segue que \begin{equation} \lim_{n\to\infty} p^{(n)}_{x,y}=0, \qquad x\in S \quad \mbox{e} \quad y\in S_T \cdot \end{equation} De acordo com as suposições do teorema, \(S_T\) é um conjunto finito. Resulta, portanto, que do resultado acima a soma naterior se aproxima de zero quando \(n\to\infty\). Por consequência, para \(x\in S_T\) \begin{equation} f(x)=\lim_{n\to\infty} P_x(T_F\le n) = P_x(T_C<\infty)=\rho_{_{x,F}}, \end{equation} como desejado.
▉No Exemplo III.2 foi obtido que o conjunto \(F=\{0,2,4,5\}\) é de estados recorrentes. Queremos encontrar as probabilidades da cadeia visitar o conjunto \(F\) partindo dos estados transientes 1 e 2. Encontremos \begin{equation} \rho_{1,0}=\rho_{{1,\{0\}}} \qquad \mbox{e} \qquad \rho_{2,0}=\rho_{{2,\{0\}}}\cdot \end{equation} Da matriz de transição no Exemplo III.2, temos que \(\rho_{1,0}\) e \(\rho_{2,0}\) são determinados pelas equações \begin{equation} \rho_{1,0}=\frac{1}{4}+\frac{1}{2}\rho_{1,0}+\frac{1}{4}\rho_{2,0} \qquad \mbox{e} \qquad \rho_{2,0}=\frac{1}{5}\rho_{1,0}+\frac{2}{5}\rho_{2,0}\cdot \end{equation} Resolvendo este sistema encontramos que \(\rho_{1,0}=\frac{3}{5}\) e \(\rho_{2,0}=\frac{1}{5}\). De maneira similar encontramos que \(\rho_{{1,\{3,4,5\}}}=\frac{2}{5}\) e \(\rho_{{2,\{3,4,5\}}}=\frac{4}{5}\).
Alternativamente, podemos encontrar as probabilidades no exemplo pela subtração de \(\rho_{\{0\}}(1)\) e \(\rho_{\{0\}}(2)\) de 1, devido a que existe somente um número finito de estados transientes. Isto é possível segundo o teorema a seguir.
Seja \(S_T\) finito, isto é, o número de estados transientes na Cadeia de Markov é finito. Então, \begin{equation} \sum_{i=1}^\infty \rho_{_{x,F_i}}=1, \qquad x\in S_T, \end{equation} onde \(F_1,F_2,\cdots\) é a coleção, finita ou infinita enumerável, de conjuntos disjuntos fechados e irredutíveis de estados recorrentes da cadeia.
Para verificar a afirmação notemos que para \(x\in S_T\) \begin{equation} \sum_{i=1}^\infty \rho_{_{x,F_i}} \, = \, \sum_{i=1}^\infty P_x(T_{F_i} <\infty) \, = \, P_x(T_{S_R}<\infty)\cdot \end{equation} Dado que existe somente um número finito de estados transientes e cada estado transiente é visitado somente um número finito de vezes, a probabilidade \(P_x(T_{S_R}<\infty)\) de que um estado recorrente acabará por ser atingido é 1, portanto a afirmação se verifica.
Uma vez que a Cadeia de Markov, começando no estado transiente \(x\) entra em um conjunto fechado irredutível \(F\) de estados recorrentes, ela visita então todos os estados em \(F\). Assim \begin{equation} \rho_{x,y}=\rho_{_{x,F}},\qquad x\in S_T \quad \mbox{e} \quad y\in F\cdot \end{equation}
▉Da demonstração do Teorema III.6, temos que em nosso prévio exemplo \begin{equation*} \rho_{1,3}=\rho_{1,4}=\rho_{1,5}=\rho_{1,\{3,4,5\}}=\frac{2}{5} \qquad \mbox{e} \qquad \rho_{2,3}=\rho_{2,4}=\rho_{2,5}=\rho_{2,\{3,4,5\}}=\frac{4}{5}, \end{equation*} são as probabilidades de atingirmos o estado de conjuntos recorrentes \(F=\{3,4,5\}\) a partir dos estados transientes.
O tema das Cadeias de Markov é melhor estudado considerando-se tipos especiais: o primeiro tipo que vamos estudar são as chamadas Cadeias de Markov absorventes, depois estudaremos as Cadeias de Markov regulares e as ergódicas.
Ao fazer a decomposição do espaço de estado podemos identificar tipos especiais de Cadeias de Markov. O primeiro tipo especial que vamos estudar é a chamada Cadeia de Markov absorvente.
Uma Cadeia de Markov é absorvente se tiver pelo menos um estado absorvente e se, a partir de cada estado, é possível ir para um estado absorvente.
Em uma Cadeia de Markov absorvente, um estado que não éé absorvente é transiente. Devemos esclarecer que nestas cadeias é possível atingir um estado absorvente não necessariamente em uma única etapa.
Figura 5: Grafo das probabilidades de transição na caminhada do bêbado.
Um homem caminha ao longo de um trecho de quatro quarteirões segundo o grafo na Figura 5. Se ele está no nodo 1, 2 ou 3, então ele caminha para a esquerda ou para a direita com a mesma probabilidade. Ele continua até que ele chegar ao nodo 4, que é um bar, ou ao nodo 0, que é a sua casa. Se ele atinge ou sua casa ou o bar, ele permanece lá. Podemos então construir uma Cadeia de Markov com estados em \(S=\{0,1,2,3,4\}\). Observamos que os estados 0 e 4 são absorventes. A matriz de transição é então \begin{equation*} \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 & 4 \\ 1 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*}
Os estados 1, 2, e 3 são transientes e a partir destes é possível alcançar os estados absorventes 0 e 4. Assim, a cadeia é uma Cadeia de Markov absorvente. Quando um processo chega a um estado absorvente, diremos que ele é absorvido.
A pergunta mais óbvia que pode ser feita sobre a cadeia é: Qual é a probabilidade de que o processo vai eventualmente atingir um estado absorvente? Outras questões interessantes incluem: (a) Qual é a probabilidade de que o processo vai acabar em um determinado estado absorvente? (b) Em média, quanto tempo será necessário para que o processo seja absorvido? (c) Em média, quantas vezes o processo estará, em cada estado transiente? As respostas a todas estas questões dependem, em geral, no estado a partir do qual o processo é iniciado, bem como as probabilidades de transição.
O seguinte exemplo têm como base o artigo de Sox, H., Blatt, M., Higgins, M. e Marton, K. de 1988 publicado na Medical Decision Making, Butterworth Publishing, Boston nas páginas 191 a 193.
Os médicos que diagnosticam cálculos biliares assintomáticos são confrontados com a decisão: remover imediatamente a vesícula biliar para evitar possíveis complicações com risco de vida ou adiar a cirurgia até que as complicações ocorram. Qual é a tendência de longo prazo de cada estratégia?
Na ausência de um estudo clínico, a análise da Cadeia de Markov que descreve o comportamento desta situação é muitas vezes a única forma eficaz de avaliar os riscos e benefícios das várias estratégias de tratamento médico. Cadeias de Markov podem ser usadas para modelar este cenário.
Suponha que, na muito simplificada a estratégia de adiar a cirurgia, o paciente vai continuar a ter cálculos biliares assintomáticos (estado \(A\)) num período de 4 meses para o próximo com probabilidade 0.95. Uma das duas principais complicações (estado \(C\)), colecistite ou complicações biliares, podem surgir necessitando de cirurgia, com probabilidade de 0.04. Por causa da idade específica do paciente, ele terá probabilidade 0.01 de morte natural (estado \(D\)).
Se a doença evoluir e se tornar sintomática, em seguida será realizada a cirurgia, com um risco de morte de 0.005 devido a complicações devido a esta. Uma vez bem sucedida a cirurgia realizada, o paciente entra em estado de recuperação (estado \(R\)). Noventa por cento dos pacientes passam para o estado bom (\(W\)), enquanto 9% permanecem no estado de recuperação de cada ano e 1% morrem de causas naturais. Uma vez que um paciente entra no estado bom, ele continua lá até a morte, com probabilidade de 0.99.
A matriz a seguir é a matriz de transição de probabilidades para a estratégia de adiar a cirurgia até que ocorram complicações. \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \quad & \; D \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} A \\ C \\ R \\ W \\ D \end{matrix} & \begin{pmatrix} \; 0.95 \, & \; 0.04 \; & \; 0 \; & \; 0 \; & \; 0.01 \; \\ \; 0 & 0 & 0.995 & 0 & 0.005 \\ 0 & 0 & 0.09 & 0.90 & 0.01 \\ 0 & 0 & 0 & 0.99 & 0.01 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}\cdot \end{matrix} \end{equation}
Observemos que o estado \(D\) é absorvente. Uma vez que o paciente chega a este estado é impossível sair. Para entendermos as consequências da estratégia a longo prazo vamos encontrar várias potências da matriz de transição. Assim \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \quad & \; D \; \end{matrix} \\ \mathcal{P}^8 \, = \, \begin{matrix} A \\ C \\ R \\ W \\ D \end{matrix} & \begin{pmatrix} \; 0.66 \, & \; 0.03 \; & \; 0.03 \; & \; 0.20 \; & \; 0.08 \; \\ \; 0 & 0 & 0 & 0.93 & 0.07 \\ 0 & 0 & 0 & 0.92 & 0.08 \\ 0 & 0 & 0 & 0.92 & 0.08 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}\cdot \end{matrix} \end{equation} e \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \quad & \; D \; \end{matrix} \\ \mathcal{P}^{32} \, = \, \begin{matrix} A \\ C \\ R \\ W \\ D \end{matrix} & \begin{pmatrix} \; 0.19 \, & \; 0.01 \; & \; 0.01 \; & \; 0.51 \; & \; 0.27 \; \\ \; 0 & 0 & 0 & 0.73 & 0.27 \\ 0 & 0 & 0 & 0.72 & 0.28 \\ 0 & 0 & 0 & 0.72 & 0.28 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}\cdot \end{matrix} \end{equation}
Como este resultado sugere, quando \(\mathcal{P}\) é elevada a potências mais e mais elevadas, o sistema tenderá para o estado absorvente de modo que com probabilidade 1 os pacientes acabarão por morrer.
Este exemplo sugere as seguintes propriedades de Cadeias de Markov absorventes:
A terceira propriedade distingue as cadeias absorventes das cadeias regulares (ver Definição 25), onde o resultado final é independente do estado inicial. Esta propriedade não é ilustrada no Exemplo 28 uma vez que existe apenas um estado absorvente. Em situações onde existam mais do que um estado absorventes esta propriedade é aparente.
Considere uma Cadeia de Markov arbitrária absorvente. Vamos numerar os estados de modo que os estados transientes venham em primeiro lugar. Se houverem \(r\) estados absorventes e \(t\) estados transientes, a matriz de probabilidades de transição terá a seguinte forma canônica \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} Transiente \quad & Absorvente \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} Transiente \\ Absorvente \end{matrix} & \begin{pmatrix} \qquad Q \qquad & \qquad R \qquad \\ 0 & \mbox{I} \end{pmatrix}\cdot \end{matrix} \end{equation} sendo \(\mbox{I}\) uma matriz identidade de ordem \(r\times r\), \(0\) é uma matriz \(r\times t\) de zeros, \(R\) é uma matriz \(t\times r\) diferente de zero e \(Q\) é uma matriz \(t\times t\). Escrita a cadeia desta forma temos que os primeiros \(t\) estados são transientes e os últimos \(r\) estados serão absorventes.
Sabemos que \(p^{(n)}_{x,y}\) é a probabilidade do processo estar no estado \(y\) após \(n\) passos, quando iniciou-se no estado \(x\). Um procedimento de álgebra matricial mostra que \(\mathcal{P}^n\) é da forma \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} Transiente \quad & Absorvente \end{matrix} \\ \mathcal{P}^{n} \, = \, \begin{matrix} Transiente \\ Absorvente \end{matrix} & \begin{pmatrix} \qquad Q^n \qquad & \qquad R^* \qquad \\ 0 & \mbox{I} \end{pmatrix}\cdot \end{matrix} \end{equation} onde \(R^*\) representa a matriz \(t\times r\), no canto superior do lado direito de \(\mathcal{P}^n\). Esta submatriz pode ser escrita em termos de \(Q\) e \(R\), mas a expressão é complicada e não é necessária neste momento. A forma de \(\mathcal{P}^n\) mostra que as componentes de \(Q^n\) fornecem as probabilidades de passar de um estado transiente inicial a um outro estado transiente após \(n\) passos.
Numa Cadeia de Markov absorvente, a probabilidade de que o processo vai ser absorvido é 1, isto é, \begin{equation} \lim_{n\to\infty} Q^n=0 \cdot \end{equation}
Dado que a cadeia é absorvente, de cada estado \(x\) transiente é possível chegar a um estado absorvente. Seja \(m_x\) o número mínimo de passos necessários para atingir um estado absorvente, a partir de \(x\). Seja \(p_x\) a probabilidade de que, a partir de \(x\), o processo não atingirá um estado absorvente em \(m_x\) passos. Então \(p_x <1\).
Seja \(m\) o maior dos \(m_x\) e seja \(p\) o maior dos \(p_x\). A probabilidade de não serem absorvidos em \(m\) passos é inferior ou igual a \(p\), em \(2n\) passos é menor ou igual a \(p^2\), etc. Uma vez que \(p < 1\) estas probabilidades tendem a 0. Dado que a probabilidade de não serem absorvidos em \(n\) passos é monótona decrescente, estas probabilidades também tendem a 0 e, então, \(\displaystyle \lim_{n\to\infty}Q^n=0\).
▉Utilizando os comandos R a seguir podemos identificar a forma canônica numa cadeia absorvente.
Identificamos então que a matriz de transição entre estados transientes é \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \; \end{matrix} \\ Q \, = \, \begin{matrix} A \\ C \\ R \\ W \end{matrix} & \begin{pmatrix} \; 0.95 \, & \; 0.04 \; & \; 0.000 \; & \; 0.00 \\ \; 0.00 & 0.00 & 0.995 & 0.00 \\ 0.00 & 0.00 & 0.090 & 0.90 \\ 0.00 & 0.00 & 0.000 & 0.99 \end{pmatrix}\cdot \end{matrix} \end{equation} Elevando a uma potência elevada a forma canônica, podemos verificar a afirmação do Teorema III.7.
Anteriormente foi obtido que a probabilidade de permanecer em estados transientes numa cadeia absorvente converge a zero, mas a pergunta agora é: Qual seria a probabilidade de permanecer em estados transientes, em tais cadeias, em \(n\) passos finitos? o seguinte teorema fornece essa resposta.
Para uma Cadeia de Markov absorvente a matriz \(\mbox{I}-Q\) tem como inversa \begin{equation} (\mbox{I}-Q)^{-1}=\mbox{I}+Q+Q^2+\cdots \cdot \end{equation} O elemento \((x,y)\) da matriz \((\mbox{I}-Q)^{-1}\) fornece o número esperado de vezes que a cadeia visita o estado \(y\), uma vez que começa no estado \(x\). O estado inicial é contado se \(x=y\).
Seja \((\mbox{I}-Q)x=0\), isto é, \(x=Qx\). Então, repetindo \(n\) vezes, vemos que \(x=Q^nx\). Desde \(\displaystyle \lim_{n\to\infty} Q^n=0\), temos \(\displaystyle \lim_{n\to\infty} Q^nx=0\), então \(x=0\). Assim, a matriz \((\mbox{I}-Q)^{-1}\) existe. Observemos que \begin{equation} (\mbox{I}-Q)(\mbox{I}+Q+Q^2+\cdots+Q^n)=\mbox{I}-Q^{n+1} \cdot \end{equation} Então, multiplicando ambos os lados por \((\mbox{I}-Q)^{-1}\) temos \begin{equation} \mbox{I}+Q+Q^2+\cdots+Q^n=(\mbox{I}-Q)^{-1}(\mbox{I}-Q^{n+1}) \cdot \end{equation} Fazendo \(n\) tender ao infinito temos \begin{equation} (\mbox{I}-Q)^{-1}=\mbox{I}+Q+Q^2+\cdots \cdot \end{equation}
Sejam \(x\) e \(y\) dois estados transientes fixos. Definamos \(\pmb{1}_y(k)\) uma variável aleatória indicadora igual a 1 se a cadeia está no estado \(y\) após \(k\) passos e 0 caso contrário. Para cada \(k\), esta variável aleatória depende tanto de \(x\) quanto de \(y\). Temos então que \begin{equation} P\big(\pmb{1}_y(k)=1\big)=q_{x,y}^k \end{equation} e \begin{equation} P\big(\pmb{1}_y(k)=0\big)=1-q_{x,y}^k, \end{equation} onde \(q_{x,y}^k\) é o \((x,y)\)-ésimo elemento da matriz \(Q^k\). Estas equações valem tambéém para \(k=0\), desde que \(Q^0=\mbox{I}\). Portanto, dado que \(\pmb{1}_y(k)\) assume somente os valores 0 ou 1, \(\mbox{E}\big(\pmb{1}_y(k)\big)=q_{x,y}^k\).
O número esperado de vezes que a cadeia está no estado \(y\), nos primeiros \(n\) passos, uma vez que se inicia no estado \(x\), é claramente \begin{equation} \mbox{E}\big(\pmb{1}_y(0)+\pmb{1}_y(1)+\cdots+\pmb{1}_y(n)\big)=q_{x,y}^0+q_{x,y}^1+\cdots+q_{x,y}^n \cdot \end{equation} Fazendo então \(n\) tender ao infinito obtemos \begin{equation} \mbox{E}\big(\pmb{1}_y(0)+\pmb{1}_y(1)+\cdots\big)=q_{x,y}^0+q_{x,y}^1+\cdots=(\mbox{I}-Q)^{-1}_{x,y} \cdot \end{equation}
▉Para uma Cadeia de Markov absorvente, a matriz \(\mbox{I}-Q\) é chamada de matriz fundamental. Os elementos de \((\mbox{I}-Q)^{-1}_{x,y}\) fornecem o número esperado de vezes que o processo está no estado transiente \(y\) se for iniciado o processo no estado transiente \(x\).
No exemplo do andar do bêbado, a matriz de transição na forma canônica é \begin{equation*} \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 0 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 1 & 2 & 3 & 0 & 4 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*} da qual vemos que a matriz \(Q\) é \begin{equation*} Q=\begin{pmatrix} 0 & 1/2 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1/2 & 0 \end{pmatrix}, \end{equation*} e que \begin{equation} \mbox{I}-Q=\begin{pmatrix} 1 & -1/2 & 0 \\ -1/2 & 1 & -1/2 \\ 0 & -1/2 & 1 \end{pmatrix}\cdot \end{equation} Calculando \((\mbox{I}-Q)^{-1}\), obtemos \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 1 \; & \; 2 \; & \;\; 3 \end{matrix} \\ (\mbox{I}-Q)^{-1} \, = \, \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} & \begin{pmatrix} \; 3/2 \, & \; 1 \; & \; 1/2 \\ 1 & 2 & 1 \\ 1/2 & 1 & 3/2 \end{pmatrix}\cdot \end{matrix} \end{equation}
A partir da linha do meio de \((\mbox{I}-Q)^{-1}\) vemos que, se a cadeia inicia-se no estado 2, o número esperado de visitas aos estados 1, 2 e 3 antes de ser absorvido é 1, 2 e 1, respectivamente.
Esta é mais uma situação de cadeias na qual não exitem estados transientes.
Uma Cadeia de Markov é chamada uma cadeia regular, se alguma potencia da matriz de transição tem apenas elementos positivos.
Em outras palavras, numa cadeia regular, para algum \(n\) é possível ir de qualquer estado para qualquer estado em exatamente \(n\) passos. É claro a partir desta definição que cada cadeia regular é ergódica. Por outro lado, uma cadeia ergódica não é necessariamente regular, como mostram os seguintes exemplos.
Considere uma Cadeia de Markov com matriz de transição definida por \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 0 & 1 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \end{matrix} & \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\cdot \end{matrix} \end{equation}
Então, é claro que é possível mover-se a partir de qualquer estado para qualquer estado, de modo que a cadeia é ergódica. No entanto, se \(n\) for ímpar, não é possível passar do estado 0 ao estado 0 em \(n\) passos e, se \(n\) for par, não é possível passar do estado 0 ao estado 1 em \(n\) passos, pelo que a cadeia não é regular. Por exemplo \begin{equation*} \mathcal{P}^{100}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \qquad \mbox{e} \qquad \mathcal{P}^{101}=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\cdot \end{equation*}
Um exemplo mais interessante do que este de Cadeia de Markov não regular ergódica é fornecido pelo modelo Ehrenfest.
Lembre-se que no modelo de urna Ehrenfest (Exemplo I.8), a matriz de transição para este exemplo é \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \, 0 & \, 1 & \, 2 & \, 3 & \, 4 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} & \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{3}{4} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{3}{4} & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}\cdot \end{matrix} \end{equation}
Nesta situaçã, se iniciarmos no estado 0 iremos, depois de qualquer número par de passos, estarmos nos estados 0, 2 ou 4 e depois de qualquer número ímpar de etapas estaremos nos estados 1 ou 3. Assim, esta cadeia é ergódica, mas não regular. Isto pode ser observado nas potências 100 e 101 da matriz de transição, as quais assumem os valores \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \, 0 & \, 1 & \, 2 & \, 3 & \, 4 \end{matrix} \\ \mathcal{P}^{100} \, = \, \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} & \begin{pmatrix} \frac{1}{8} & 0 & \frac{6}{8} & 0 & \frac{1}{8} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{8} & 0 & \frac{6}{8} & 0 & \frac{1}{8} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{8} & 0 & \frac{6}{8} & 0 & \frac{1}{8} \end{pmatrix} \end{matrix} \qquad \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \, 0 & \, 1 & \, 2 & \, 3 & \, 4 \end{matrix} \\ \mathcal{P}^{101} \, = \, \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} & \begin{pmatrix} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{8} & 0 & \frac{6}{8} & 0 & \frac{1}{8} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{8} & 0 & \frac{6}{8} & 0 & \frac{1}{8} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{pmatrix}\cdot \end{matrix} \end{equation}
Qualquer matriz de transição que não tem zeros determina uma cadeia de Markov regular. No entanto, é possível que uma Cadeia de Markov regular tenha zeros na matriz de transição. Vejamos o seguinte exemplo.
De acordo com Kemeny, J.G., Snell, J.L and Thompson, G.L. (1974). Introduction to Finite Mathematics, 3rd ed. Englewood Cliffs, NJ: Prentice-Hall., a Terra de Oz é um excelente lugar para morar por muitas coisas, mas não por um bom tempo por causa do tempo.
Eles nunca tem dois dias agradáveis seguidos. Se eles têm um bom dia \(B\), eles são tão propensos a ter neve \(N\) quanto chuva \(C\) no dia seguinte. Se tiverem neve ou chuva, tem possibilidade meio de ter o mesmo no dia seguinte. Se não houver mudança de neve ou chuva, tem apenas metade de probabilidade de uma mudança para um bom dia. Com esta informação, formamos a matriz de transição da Cadeia de Markov como segue: \begin{equation*} \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{C} \\ \mbox{B} \\ \mbox{N} \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{C} & \mbox{B} & \mbox{N} \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*}
Podemos observar que esta matriz de transição tem \(p_{B,B}=0\), mas \(\mathcal{P}^2\) não tem zeros, então esta é uma Cadeia de Markov regular.
Exemplos de Cadeia de Markov não regulares são as cadeias absorventes. Por exemplo, seja \begin{equation*} \mathcal{P} = \begin{pmatrix} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} \end{equation*} a matriz de transição de uma Cadeia de Markov. Todas as potências \(\mathcal{P}\) terão um 0 no canto superior direito. Vamos agora discutir dois teoremas importantes relacionados às cadeias regulares.
Primeiro demonstremos um teorema auxiliar.
Seja \(\mathcal{P}\) uma matriz de transição de ordem \(r\) com elementos positivos. Seja \(\epsilon\) o menor valor de \(\mathcal{P}\). Seja \(\pmb{x}\) qualquer vetor coluna de dimensão \(r\), sendo \(M_0\) o máximo e \(m_0\) o mínimo de suas componentes. Sejam agora \(M_1\) e \(m_1\) os valores máximo e mínimo respectivos das componentes do vetor \(\mathcal{P} \pmb{x}\). Então \(M_1\leq M_0\), \(m_1\geq m_0\) e \begin{equation} M_1-m_1\leq (1-2\epsilon)(M_0-m_0)\cdot \end{equation}
Seja \(\pmb{x}'\) o vetor obtido de \(x\) substituindo uma das componentes \(m_0\) por \(M_0\). Então \(\pmb{x}\leq \pmb{x}'\). Cada componente de \(\Gamma \pmb{x}'\) é da forma \begin{equation} a\cdot m_0+(1-a)\cdot M_0=M_0-a(M_0-m_0), \end{equation} onde \(a\geq \epsilon\). Assim, cada componente de \(\mathcal{P} \pmb{x}'\) é menor ou igual do que \begin{equation} M_0-\epsilon(M_0-m_0)\cdot \end{equation} Dado que \(\pmb{x}\leq \pmb{x}'\), temos que \begin{equation} M_1\leq M_0-\epsilon(M_0-m_0)\cdot \end{equation} Aplicando este resultado ao vetor \(-\pmb{x}\) obtemos que \begin{equation} -m_1\leq -m_0-\epsilon(-m_0+M_0)\cdot \end{equation} Somando os resultados anteriores, temos que \begin{equation} \begin{array}{rcl} M_1-m_1 & \leq & M_0-m_0-2\epsilon(M_0-m_0) \\[0.8em] & = & (1-2\epsilon)(M_0-m_0) \cdot \end{array} \end{equation}
▉Devemos observar que \(\epsilon\), o menor valor de \(\mathcal{P}\), é sempre menor ou igual a 1/2. Este teorema nos fornece uma forma mais simples da demonstração do seguinte teorema fundamental para Cadeias de Markov regulares.
Seja \(\mathcal{P}\) a matriz de transição de uma Cadeia de Markov regular. Então, \begin{equation} \lim_{n\to\infty} \mathcal{P}^n=W, \end{equation} onde \(W\) é uma matriz com todas as linhas iguais ao mesmo vetor \(w\). O vector \(w\) é um vector de probabilidades estritamente positivo, isto é, as componentes são todas positivas e somam um.
Primeiro vamos assumir que a matriz \(\Gamma\) não tem zeros. Seja \(\epsilon\) o menor valor em \(\mathcal{P}\). Seja agora \(\rho_j\) um vetor coluna com 1 na \(j\)-ésima componente e zeros nas outras. Sejam \(M_n\) e \(m_n\) os valores máximos e mínimos dos vetores \(\mathcal{P}^n\rho_j\). Dado que \(\Gamma^n\rho_j=\Gamma\cdot \Gamma^{n-1}\rho_j\), temos do Teorema 24 que \(M_1\geq M_2\geq M_3\geq \cdots\), \(m_1\leq m_2\leq m_3\leq \cdots\) e \begin{equation} M_n-m_n\leq (1-2\epsilon)(M_{n-1}-m_{n-1}), \end{equation} para \(n\geq 1\). Fazendo \(d_n=M_n-m_n\) este resultado nos disse que \begin{equation} d_n\leq (1-2\epsilon)^n d_0\cdot \end{equation} Logo \(\lim_{n\to\infty} d_n=0\) e então, \(M_n\) e \(m_n\) tem limite comum. Portanto, \(\mathcal{P}^n\rho_j\) tende a um vetor com todas as componentes iguais. Seja \(\alpha_j\) este valor comum. Logicamente, para todo \(n\), \(m_n\leq \alpha_j\leq M_n\). Em particular, dado que \(0 < m_1\) e \(M_1 <1\), temos que \(0 < \alpha_j < 1\). Agora \(\mathcal{P}^n\rho_j\) é a \(j\)-ésima coluna de \(\Gamma^n\). Então, a \(j\)-ésima coluna de \(\Gamma^n\) tende a um vetor com todas as componentes iguais a \(w_j\). Isto é, \(\mathcal{P}^n\) tende a uma matriz \(W\) com todas as linhas iguais ao vetor \(\pmb{w}=(w_1,w_2,\cdots,w_r)\). Dado que as somas das linhas de \(\mathcal{P}^n\) são sempre 1, o mesmo vale para o limite.Isto completa a demonstração no caso da matriz assumir somente valores positivos. Considerar agora o caso seguinte em que \(\mathcal{P}\) somente é assumida ser regular. Seja \(N\), tal que \(\mathcal{P}^N\) tenha somente valores positivos e aplicamos a primeira parte da demonstração à matriz \(\mathcal{P}^N\).
▉Queremos mostrar que a potência \(\mathcal{P}^n\) de uma matriz de transição regular, isto é, que a matriz de probabilidades de transição de uma cadeia regular tende a uma matriz com todas as linhas da mesma forma. Significa o mesmo de mostrar que \(\mathcal{P}^n\) converge a uma matriz com colunas constantes. Agora, a \(j\)-ésima coluna \(\mathcal{P}^n\) é \(\mathcal{P}^n \rho_j\) onde \(\rho_j\) é um vetor coluna com 1 na \(j\)-ésima linha e 0 nas outras. Assim, precisamos apenas mostrar que para qualquer vetor coluna \(\pmb{\rho}\), \(\mathcal{P}^n \pmb{\rho}\) se aproxima de um vetor constante, quando \(n\) tende ao infinito.
Uma vez que cada linha de \(\mathcal{P}\) é um vector de probabilidades, \(\mathcal{P}\pmb{\rho}\) substitui \(\pmb{\rho}\) pelas médias dos seus componentes. Aqui está um exemplo: \begin{equation*} \begin{pmatrix} 1/2 & 1/4 & 1/4 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/2 & 1/6 \end{pmatrix} \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = \begin{pmatrix} 1/2\cdot 1 + 1/4\cdot 2 + 1/4\cdot 3 \\ 1/3\cdot 1 + 1/3\cdot 2 + 1/3\cdot 3 \\ 1/3\cdot 1 + 1/2\cdot 2 + 1/6\cdot 3 \end{pmatrix} = \begin{pmatrix} 7/4 \\ 2 \\ 11/6 \end{pmatrix} \end{equation*}
O resultado do processo de cálculo da média faz as componentes de \(\mathcal{P}\pmb{\rho}\) mais semelhantes do que as de \(\pmb{\rho}\). Em particular, os máximos decrescem de 3 para 2 e os mínimos aumentos de 1 a 11/6. Na prova mostramos que, como nós fazemos mais e mais desta média para obter \(\mathcal{P}^n\pmb{\rho}\), a diferença entre o máximo e mínimo tende a 0 quando \(n\to\infty\). Isto significa que \(\mathcal{P}^n\pmb{\rho}\) tende a um vector constante. O elemento \((i,j)\) de \(\mathcal{P}^n\), \(p_{i,j}^{(n)}\) é a probabilidade de que o processo esteja no estado \(j\) após \(n\) passos se inicia-se no estado \(i\). Se denotamos a linha comum de \(W\) por \(w\), então o Teorema III.10 afirma que, a probabilidade da cadeia estar no estado \(j\) a longo prazo é de aproximadamente \(w_j\), a \(j\)-ésima componente de \(w\) e é independente do estado inicial.
Lembre-se do exemplo da Terra de Oz (Exemplo III.10), a potência sexta da matriz de transição \(\mathcal{P}\) é, com três casas decimais, \begin{equation*} \begin{matrix} & \\ \mathcal{P}^6 = \begin{matrix} \mbox{C} \\ \mbox{B} \\ \mbox{N} \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{C} & \mbox{B} & \mbox{N} \\ 0.4 & 0.2 & 0.4 \\ 0.4 & 0.2 & 0.4 \\ 0.4 & 0.2 & 0.4 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*}
Assim, para este grau de precisão, a probabilidade de chuva seis dias depois de um dia de chuva é a mesma que a probabilidade de chuva seis dias depois de um dia agradável ou seis dias depois de um dia de neve. O Teorema III.10 prevê que, para grandes valores de \(n\), as linhas de \(\mathcal{P}^n\) vão se aproximar de um vetor comum. É interessante que isso ocorra tão cedo neste exemplo.
Seja \(\mathcal{P}\) a matriz de transição de uma Cadeia de Markov regular, seja \begin{equation} W=\lim_{n\to\infty} \mathcal{P}^n, \end{equation} com componentes comuns \(\pmb{w}\) e seja \(\pmb{x}\) um vetor coluna com todas as componentes iguais a 1. Então
▉
Note-se que uma consequência imediata deste teorema é o fato de que existe apenas um único vetor de probabilidades \(\nu\), tal que a \(\nu\mathcal{P}=\nu\).