Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e função de transição \(p\). Vamos mostrar aqui como diversas probabilidades condicionais podem ser expressas em termos de \(p\) e definiremos também a função de transição em \(m\) passos da Cadeia de Markov.
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de trnasição \(\mathcal{P}=\big(p_{x,y}\big)\). Então \begin{equation} P\big(C_{n+1}=c_{_{n+1}},\cdots,C_{n+m}=c_{_{n+m}} \, | \, C_{0}=c_{_{0}},\cdots,C_{n}=c_{_{n}}\big) \, = \, p_{c_{_{n}},c_{_{n+1}}}\cdots p_{c_{_{n+m-1}},c_{_{n+m}}}\cdot \end{equation}
Para demonstrar esta relação, utilizamos a definição de probabilidade condicional na parte esquerda como \begin{equation} \dfrac{P\big(C_0=c_{_{0}},\cdots, C_{n+m}=c_{_{n+m}}\big)}{P\big(C_0=c_{_{0}},\cdots,C_n=c_{_{n}} \big)} \, = \, \dfrac{\pi_0(c_{_0})p_{c_{_{0}},c_{_{1}}}\cdots p_{c_{_{n+m-1}},c_{_{n+m}}}}{\pi_0(c_{_0})p_{c_{_{0}},c_{_{1}}}\cdots p_{c_{_{n-1}},c_{_{n}}}}, \end{equation} do qual deduzimos a expressão à direita acima.
▉Escrevendo convenientemente o resultado do Teorema 4 temos que \begin{equation} P\big( C_{n+1}=y_{_{1}}, \cdots, C_{n+m}=y_{_{m}} \, | \, C_0=c_{_{0}}, \cdots, C_{n-1}=c_{_{n-1}},C_n=x\big) \, = \, p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \end{equation} Utilizemos este resultado para provar uma propriedade mais geral. Consideremos \(\mathcal{A}_0,\mathcal{A}_1,\cdots,\mathcal{A}_{n-1}\) subconjuntos do espaço de estados \(S\). Segue então, da expressão acima, que \begin{equation} P\big( C_{n+1}=y_{_{1}}, \cdots, C_{n+m}=y_{_{m}} \, | \, C_0\in\mathcal{A}_0, \cdots, C_{n-1}\in\mathcal{A}_{n-1},C_n=x\big) \, = \, p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \end{equation}
Mais ainda, se \(\mathcal{B}_1,\cdots,\mathcal{B}_m\) forem subconjuntos de \(S\), segue que \begin{equation} P\big( C_{n+1}\in\mathcal{B}_1, \cdots, C_{n+m}\in\mathcal{B}_m \, | \, C_0\in\mathcal{A}_0, \cdots, C_{n-1}\in\mathcal{A}_{n-1},C_n=x\big) \, = \, \displaystyle \sum_{y_{_{1}}\in\mathcal{B}_1}\cdots\sum_{y_{_{m}}\in\mathcal{B}_m} p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \end{equation}
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de transição \(\mathcal{P}=\big(p_{x,y}\big)\). A função de transição em \(m\)-passos \(p_{x,y}^{(m)}\), a qual fornece a probabilidade de transição do estado \(x\) ao estado \(y\) em \(m\)-passos, define-se como \begin{equation} p_{x,y}^{(m)} \, = \, \displaystyle \sum_{y_{_1}}\cdots\sum_{y_{_{m-1}}} p_{x,y_{_1}}p_{y_{_1},y_{_2}}\cdots p_{y_{_{m-2}},y_{_{m-1}}}p_{y_{_{m-1}},y}, \end{equation} para \(m\geq 2\), como \(p_{x,y}^{(1)}=p_{x,y}\) e como \begin{equation} p_{x,y}^{(0)} \, = \, \left\{ \begin{array}{cc} 1, & \mbox{se} \; x=y \\ 0, & \mbox{caso contrário} \end{array}\right.\cdot \end{equation}
Um gerente normalmente verifica o vendedor em sua loja a cada 5 minutos para ver se está ocupado ou não. Ele modela o estado do vendedor como 1 se está ocupado ou 2 caso não esteja ocupado. Consideremos a sequência de estados resultantes nas verificações como uma Cadeia de Markov com dois estados possíveis e função de transição estacionária dada pela seguinte matriz: \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; Ocupado \; & \quad Não \; ocupado \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} Ocupado \\ Não \; ocupado \end{matrix} & \begin{pmatrix} \qquad 0.9 \qquad & \qquad 0.1 \qquad \\ 0.6 & 0.4 \end{pmatrix}, \end{matrix} \end{equation}
O gerente percebe que, no final do dia, estará afastado por 10 minutos e vai perder uma vistoria do vendedor. Ele quer calcular a distribuição condicional dois períodos de tempo no futuro dado cada um dos estados possíveis. O raciocínio é da seguinte forma: se \(C_n = 1\), por exemplo, o estado terá que ser 1 ou 2 no tempo \(n + 1\), mesmo que ele não se importe agora sobre o estado no tempo \(n + 1\). Mas, se ele calcula a distribuição condicional conjunta de \(C_{n+1}\) e \(C_{n+2}\) dado \(C_{n}= 1\), ele pode somar sobre os possíveis valores de \(C_{n+1}\) para obter a distribuição condicional de \(C_{n+2}\) dado \(C_n=1\). Em símbolos, \begin{equation} P(C_{n+2}=1 \, | \, C_n=1) \, = \, P(C_{n+2}=1, \, C_{n+1}=1 \, | \, C_n=1) \, + \, P(C_{n+2}=1, \, C_{n+1}=2 \, | \, C_n=1)\cdot \end{equation}
Pelo Teorema II.1 temos que \begin{equation} P(C_{n+2}=1, \, C_{n+1}=1 \, | \, C_n=1) \, = \, P(C_{n+1}=1 \, | \, C_n=1)\times P(C_{n+2}=1 \, | \, C_{n+1}=1) \, = \, 0.9\times 0.9 \, = \, 0.81\cdot \end{equation} Similarmente \begin{equation} P(C_{n+2}=1, \, C_{n+1}=2 \, | \, C_n=1) \, = \, P(C_{n+1}=2 \, | \, C_n=1)\times P(C_{n+2}=1 \, | \, C_{n+1}=2) \, = \, 0.1\times 0.6 \, = \, 0.06\cdot \end{equation}
Segue que \(P(C_{n+2}=1 \, | \, C_n =1) \, = \, 0.81+0.06=0.87\) e, portanto, \(P(C_{n+2}=2 \, | \, C_{n}=1) \, = \, 1-0.87=0.13\). De maneira similar, se \(C_n=2\), \begin{equation} P(C_{n+2}=1 \, | \, C_n=2) \, = \, 0.06\times 0.9+0.4\times 0.6 \, = \, 0.78 \end{equation} e \begin{equation} P(C_{n+2}=2 \, | \, C_n=2) \, = \, 1-0.78 \, = \, 0.22\cdot \end{equation}
Estes cálculos podem ser feitos também utilizando a Definição 10. Assim, \begin{equation} p_{1,2}^{(2)} \, = \, p_{1,1}p_{1,2}+p_{1,2}p_{2,2} \, = \, 0.9\times 0.1+0.1\times 0.4 \, = \, 0.09+0.04 \, = \, 0.13 \end{equation} e \begin{equation} p_{2,2}^{(2)} \, = \, p_{2,1}p_{1,2}+p_{2,2}p_{2,2} \, = \, 0.6\times 0.1+0.4\times 0.4 \, = \, 0.06+0.16 \, = \, 0.22\cdot \end{equation}
Podemos utilizar expressões anteriores para esclarecer ainda o conceito de função de transição em \(m\)-passos. Escolhendo \(\mathcal{B}_1,\cdots,\mathcal{B}_{m-1}=S\) e \(\mathcal{B}_m=\{y\}\) segue que \begin{equation} P(C_{n+m}=y \, | \, C_0\in \mathcal{A}_0,\cdots,C_{n-1}\in\mathcal{A}_{n-1}, C_n=x ) \, = \, p_{x,y}^{(m)}\cdot \end{equation} Em particular, assumindo \(\mathcal{A}_0,\cdots,\mathcal{A}_{n-1}=S\), vemos que \(P(C_{n+m}=y \, | \, C_n=x)=p_{x,y}^{(m)}\).
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária, \(S\) o espaço de estados e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Então, a probabilidade de transição em \(n+m\)-passos pode ser escrita em termos das probabilidades de transição em \(m\)-passos como \begin{equation} p_{x,y}^{(n+m)} \, = \, \sum_{z\in S} p_{x,z}^{(n)}p_{z,y}^{(m)}\cdot \end{equation}
Observemos que \begin{equation} P(C_{n+m}=y \, | \, C_0=x, C_n=z) \, = \, p_{z,y}^{(m)}\cdot \end{equation} Dado que \begin{equation} \begin{array}{rcl} p_{z,y}^{(m)} & = & P(C_{n+m}=y \, | \, C_0=x) \\ & = & \displaystyle \sum_{z\in S} P(C_n=z \, | \, C_0=x)\times P(C_{n+m}=y \, | \, C_0=0, C_n=z) \\ & = & \displaystyle \sum_{z\in S} p_{x,z}^{(n)} P(C_{n+m}=y \, | \, C_0=x, C_n=z)\cdot \end{array} \end{equation}
▉E em termos da distribuição inicial? como escrever a distribuição de \(C_n\) em termos da distribuição inicial \(\pi_0\) e da probabilidade em \(n\)-passos? A resposta é fornecida pelo seguinte teorema.
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Então, podemos escrever a distribuição de \(C_n\) da seguinte maneira \begin{equation} P(C_n=y) \, = \, \sum_{x\in S} \pi_0(x)p_{x,y}^{(n)}\cdot \end{equation}
Dado que \begin{equation} P(C_{n}=y ) \, = \, \displaystyle \sum_{x\in S} P(C_0=x, C_n=y), \end{equation} então \begin{equation} P(C_n=y) \, = \, \displaystyle \sum_{x\in S} P(C_0=x)\times P(C_n=y \, | \, C_0=x)\cdot \end{equation}
▉Um método alternativo de calcularmos a distribuição de \(C_n\) é obtido da seguinte maneira. Observe que \begin{equation} P(C_{n+1}=y) \, = \, \displaystyle \sum_{x\in S} P(C_n=x, C_{n+1}=y) \, = \, \sum_{x\in S} P(C_n=x)\times P(C_{n+1}=y \, | \, C_n=x), \end{equation} do qual obtemos que \begin{equation} P(C_{n+1}=y) \, = \, \sum_{x\in S} P(C_n=x)p_{x,y}\cdot \end{equation}
Se conhecemos a distribuição de \(C_0\), podemos usar o resultado acima para encontrar a distribuição de \(C_1\). Em seguida, sabendo a distribuição de \(C_1\), utilizamos o resultado acima novamente para encontrar a distribuição de \(C_2\). Da mesma forma, podemos encontrar a distribuição de \(C_n\) aplicando \(n\) vezes este resultado.
Generalizando os cálculos no Exemplo II.1 a três ou mais transições pode parecer entediante. No entanto, quando se examinam os cálculos com cuidado, vê-se um padrão que vai permitir um cálculo compacto das probabilidades de transição para várias etapas. Considere uma Cadeia de Markov estacionária com \(N\) estados possíveis \(1,\cdots,N\) e matriz de transição \(\mathcal{P}=\big(p_{x,y}\big)\).
Assumindo-se que a cadeia está no estado \(x\) num determinado momento \(n\), vamos agora determinar a probabilidade de que a cadeia irá estar no estado \(y\) no tempo \(n+2\). Em outras palavras, vamos determinar a probabilidade condicional de \(C_{n+2}=y\) dado \(C_n=x\). A notação para esta probabilidade é \(p_{x,y}^{(2)}\).
Argumentamos o que o gerente fez no Exemplo II.1. Seja \(r\) o valor de \(C_{n+1}\) que não é de interesse primordial, mas é útil para o cálculo. Depois \begin{equation*} \begin{array}{rcl} p_{x,y}^{(2)} & = & P(C_{n+2}=y \, | \, C_n=x) \, = \, \displaystyle \sum_{r=1}^N P(C_{n+1}=r, C_{n+2}=y \, | \, C_n=x) \\ & = & \displaystyle \sum_{r=1}^N P(C_{n+1}=r \, | \, C_n=x)\times P(C_{n+2}=y \, | \, C_{n+1}=r) \, = \, \sum_{r=1}^N p_{x,r}p_{r,y}, \end{array} \end{equation*} em que a terceira igualdade segue do Teorema II.1 e a quarta igualdade segue a partir da defnição de uma Cadeia de Markov estacionária.
O valor de \(p_{x,y}^{(2)}\) pode ser determinado da seguinte maneira: se a matriz de transição \(\mathcal{P}\) é elevada ao quadrado, ou seja, se a matriz \(\mathcal{P}^2=\mathcal{P}\times \mathcal{P}\) for calculada, o elemento da fila \(x\) e coluna \(y\) da matriz \(\mathcal{P}\) será \(\sum_{r=1}^N p_{x,r}p_{r,y}\). Portanto, \(p_{x,y}^{(2)}\) será o elemento da fila \(x\) e a coluna \(y\) de \(\mathcal{P}^2\). Por um argumento semelhante, a probabilidade de que a cadeia vai passar do estado \(x\) para o estado \(y\) em três etapas ou \(p_{x,y}^{(3)}=P(C_{n+3}=y \, | \, C_n=x)\), pode ser encontrada através da construção da matriz \(\mathcal{P}^3=\mathcal{P}^2\mathcal{P}\). A probabilidade \(p_{x,y}^{(3)}\) será o elemento da fila \(x\) com a coluna \(y\) da matriz \(\mathcal{P}^3\). Em geral, temos o seguinte resultado.
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) finito e matriz de trnasição \(\mathcal{P}=\big(p_{x,y}\big)\). Para cada \(m=2,3,\cdots\) a \(m\)-ésima potência \(\mathcal{P}^m\) da matriz \(\mathcal{P}\) tem na linha \(x\) e coluna \(y\) a probabilidade \(p_{x,y}^{(m)}\), a probabiilidade da cadeia passar do estado \(x\) para o estado \(y\) em \(m\) passos.
Exercício.
▉Em resumo, a linha \(x\) da matriz de trnasição em \(m\)-passos dá a distribuição condicional de \(C_{n+m} \, | \, C_n=x\) para todo \(x=1,2,\cdots,N\) e todos os \(n,m=1,2,\cdots\).
Utilizando o Teorema II.4, podemos facilmente calcular \begin{equation} \mathcal{P}^2 \, = \, \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix}\times \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix} \, = \, \begin{pmatrix} 0.87 & 0.13 \\ 0.78 & 0.22 \end{pmatrix}\cdot \end{equation}
Uma outra forma de fazer os cálculos é utilizando um dos pacotes de funções disponíveis na linguagem de programação R (R Core Team, 2014). Utilizaremos o pacote de funções markovchain (Giorgio, 2015).
Com as linhas de comando acima fazemos a leitura do pacote de funções escolhido (markovchain), definimos os nomes dos estados e a matriz de probabilidades de transição. Temos por resultado um objeto de nome ProbT contendo a matriz no formato requerido. Basta agora digitar ProbT na linha de comandos do R e temos por resposta a matriz de probabilidades de transição.
Para calcularmos as probabilidades de transição em duas e três etapas fazemos:
Significa que, partindo do estado Ocupado, temos probabilidade 0.87 de permanecermos nesse estado depois de duas etapas da cadeia, ou seja, se cadeia tiver \(C_0 =\, "Ocupado"\) como valor inicial, depois de duas transições temos que \(C_2 =\, "Ocupado"\), com probabilidade 0.87, não importado os valores intermediários que a cadeia possa assumir.
Ainda podemos calcular a função de probabilidade da resposta para cada instante de tempo, isto utilizando o Teorema II.3. Assumindo que o estado inicial desta cadeia seja \((0,1)\), temos que:
A potência \(m\)-ésima da matriz de probabilidades de transição de uma Cadeia de Markov dá as probabilidades de transição de um estado para outro em \(m\) finitas unidades de tempo. Será útil para estender este conceito aprendermos como fazer os cálculos para intervalos de tempo mais longos.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\), matriz de transição \(\mathcal{P}\) e \(A\) um subconjunto de \(S\). Nesta seção, estamos interessados em saber qual é a probabilidade da cadeia atingir um estado em \(A\). Especificamente, queremos derivar uma expressão para a probabilidade de que o tempo para atingir um estado em \(A\) seja finito, bem como a esperança desse tempo.
Seja \(A\subseteq S\). O tempo de primeira visita \(T_A\), da Cadeia de Markov \(\{C_n\}\) ao conjunto \(A\), é definido como \begin{equation} T_A =\min\big\{n\geq 0 \, : \, C_n\in A\big\}, \end{equation} e como \(T_A=\infty\) se \(A=\emptyset\).
Em outras palavras, \(T_A\) é uma variável aleatória com valores inteiros não negativos assumindo o primeiro tempo positivo em que a Cadeia de Markov atinge \(A\). Denotaremos o tempo de primeira visita ao ponto \(x\in S\) por \(T_x\). Utilizaremos a notação \(P_x(\cdot)\) para denotar a probabilidade de vários eventos definidos em termos da Cadeia de Markov começando em \(x\). Então \begin{equation*} P_x(C_1\neq y,C_2\neq y, C_3=y), \end{equation*} denota a probabilidade de que a Cadeia de Markov começando no estado \(x\) esteja no estado \(y\) no tempo 3, mas não nos tempos 1 e 2. Observe que a probabilidade acima significa que \begin{equation*} P_x(C_1\neq y,C_2\neq y, C_3=y) = P(C_0=x,C_1\neq y, C_2\neq y,C_3=y)\cdot \end{equation*}
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e sejam \(x,y\in S\). Então \begin{equation} p^{(n)}_{x,y}=\sum_{m=1}^n P_x(T_y=m)p^{(n-m)}_{y,y}, \end{equation} para \(n\ge 1\).
Note que os eventos \(\{T_y=m,C_n=y\}\) para \(1\le m\le n\), são eventos disjuntos e que \begin{equation} \{C_n=y\}=\bigcup_{m=1}^n\{T_y=m,C_n=y\} \cdot \end{equation} Temos a rigor decomposto o evento \(\{C_n=y\}\) de acordo com o tempo de primeira visita a \(y\). Vemos a partir desta decomposição que \begin{equation} \begin{array}{rcl} p^{(n)}_{x,y} & = & \displaystyle P_x(C_n=y) \, = \, \sum_{m=1}^n P_x(T_y=m,C_n=y) \\ & = & \displaystyle \sum_{m=1}^n P_x(T_y=m)\times P(C_n=y \, | \, C_0=x,T_y=m) \\ & = & \displaystyle \sum_{m=1}^n P_x(T_y=m)\times P(C_n=y \, | \, C_0=x,C_1\ne y,\cdots, C_{m-1}\neq y,C_m=y) \\ & = & \displaystyle \sum_{m=1}^n P_x(T_y=m)p^{(n-m)}_{y,y}\cdot \end{array} \end{equation}
▉Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). A probabilidade de começar no estado \(x\in S\) e atingir \(A\subset S\), em um tempo finito, é definida como \begin{equation} \rho_{x,A}=P_x(T_A<\infty) \cdot \end{equation}
Consideremos a situação de uma Cadeia de Markov com matriz de transição \begin{equation*} \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*} Começando em 2, qual é a probabilidade de atingir o estado 4? Quanto tempo demora até que a cadeia estar no estado 1 ou no 4?
Observemos que \begin{equation*} \rho_{1,4}=P_x(T_4<\infty)=0, \; \rho_{4,4}=P_x(T_4<\infty)=1, \; \mbox{E}_1(T_{\{1,4\}})=0 \; \mbox{e} \; \mbox{E}_4(T_{\{1,4\}})=0\cdot \end{equation*} Suponhamos agora que começamos no estado 2 e consideraremos a situação depois de fazer um passo. Com probabilidade 1/2 pulamos ao estado 1 e com probabilidade 1/2 pulamos ao estado 3. Assim, \begin{equation*} \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\rho_{3,4} \end{equation*} e \begin{equation*} \mbox{E}_2(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_1(T_{\{1,4\}})+\dfrac{1}{2}\mbox{E}_3(T_{\{1,4\}})\cdot \end{equation*} O 1 aparece nesta última expressão porque contamos o tempo do primeiro passo. Similarmente, \begin{equation*} \rho_{3,4}=\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\rho_{4,4} \end{equation*} e \begin{equation*} \mbox{E}_3(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_2(T_{\{1,4\}})+\dfrac{1}{2}\mbox{E}_4(T_{\{1,4\}})\cdot \end{equation*} Consequentemente \begin{equation*} \rho_{2,4}=\dfrac{1}{2}\rho_{3,4}=\dfrac{1}{2}\left( \dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\right) \end{equation*} e \begin{equation*} \mbox{E}_2(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_3(T_{\{1,4\}})=1+\dfrac{1}{2}\left[ 1+\dfrac{1}{2}\mbox{E}_2(T_{\{1,4\}})\right] \cdot \end{equation*} Assim, a partir de 2, a probabilidade de acertar o estado 4 é 1/3 e o tempo médio para chegar é 2 assim como é dois também o tempo médio para chegar ao estado 1. Note que, ao escrever as equações para \(\rho_{2,4}\) e \(\mbox{E}_2(T_{\{1,4\}})\) temos feito uso implícito da propriedade markoviana, em assumir que a cadeia começa novamente de sua nova posição após o primeiro salto.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O vetor de probabilidades \(\{\rho_{x,A}, \; x\in S\}\), as probabilidades do tempo de primeira visita ao conjunto \(A\) a partir de qualquer estado \(x\in S\), é a solução não negativa mínima do sistema de equações lineares \begin{equation} \begin{array}{ll} \rho_{x,A} = 1, & \forall x\in A \\[0.8em] \rho_{x,A} = \displaystyle \sum_{y\in S} p_{x,y}\rho_{y,A}, & \forall x\notin A\cdot \end{array} \end{equation}
Solução mínima neste teorema significa que, se \(\rho^*_{x,A}\) for uma outra solução não negativa do sistema, então \(\rho^*_{x,A}\geq \rho_{x,A}\), \(\forall x\in S\).
Primeiro provemos que o sistema \(\{\rho_{x,A}, \; x\in S\}\) satisfaz o teorema. Se \(C_0=x\in A\), então \(T_A=0\) e \(\rho_{x,A}=1\). Caso \(C_0=x\notin A\), então \(T_A\geq 1\) e pela propriedade markoviana \begin{equation} P_x(T_A < \infty \, | \, C_1=y)=P_y(T_A < \infty)=\rho_{y,A} \end{equation} e \begin{equation} \displaystyle \rho_{x,A}=P_x(T_A < \infty) \, = \, \sum_{y\in S} P_x(T_A < \infty,C_1=y) \, = \, \displaystyle \sum_{y\in S} P_x(T_A < \infty \, | \, C_1=y)\times P_x(C_1=y) \, = \, \sum_{y\in S} p_{x,y}\rho_{y,A}\cdot \end{equation} Suponhamos agora que \(\rho^*_{x,A}\) seja uma solução do sistema. Então \(\rho_{x,A}=\rho^*_{x,A}=1\) para \(x\in A\). Caso \(x\notin A\), então \begin{equation} \rho^*_{x,A}=\sum_{y\in S} p_{x,y}\rho^*_{y,A}=\sum_{y\in A} p_{x,y}+\sum_{y\notin A} p_{x,y}\rho^*_{y,A}\cdot \end{equation} Substituindo a expressão de \(\rho^*_{y,A}\), temos que \begin{equation} \begin{array}{rcl} \rho^*_{x,A} & = & \displaystyle \sum_{y\in A} p_{x,y}+\sum_{y\notin A} p_{x,y} \left(\sum_{z\in A}p_{y,z}+\sum_{z\notin A}p_{y,z}\rho^*_{z,A} \right) \\[0.8em] & = & \displaystyle P_x(C_1\in A)+P_x(C_1\notin A,C_2\in A)+\sum_{y\notin A}\sum_{z\notin A} p_{x,y}p_{y,z}\rho^*_{z,A} \cdot \end{array} \end{equation} Repetindo a substituição para \(\rho^*_{z,A}\) obtemos, depois de \(n\) substituições, que \begin{equation} \displaystyle \rho^*_{x,A}=P_x(C_1\in A)+\cdots+P_x(C_1\notin A,\cdots,C_{n-1}\notin A,C_n\in A) \, = \, \displaystyle +\sum_{z_1\notin A}\cdots \sum_{z_n\notin A} p_{x,z_1}p_{z_1,z_2}\cdots p_{z_{n-1},z_n}\rho^*_{z_n,A}\cdot \end{equation} Agora, se \(\rho^*_{x,A}\) é não negativo assim também o é o último termo da direita. O termo remanescente de somas fornece o valor de \(P_x(T_A\leq n)\). Desta forma, vemos que, \(\rho^*_{x,A}\geq P_x(T_A\leq n)\) para todo \(n\) e então \begin{equation} \rho^*_{x,A}\geq \lim_{n\to\infty} P_x(T_A\leq n)=P_x(T_A<\infty)=\rho_{x,A}\cdot \end{equation}
▉O sistema de equações lineares no Teorema II.6 para \(\rho_{2,4}\) é dado aqui por \(\rho_{4,4}=1\) e \begin{equation} \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\rho_{3,4}, \qquad \rho_{3,4}=\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\rho_{4,4} \end{equation} de maneira que \begin{equation} \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\left(\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\right) \end{equation} e \begin{equation} \rho_{2,4}=\dfrac{1}{3}+\dfrac{2}{3}\rho_{1,4}, \qquad \rho_{3,4}=\dfrac{2}{3}+\dfrac{1}{3}\rho_{1,4}\cdot \end{equation} O valor de \(\rho_{1,4}\) não é determinado pelo sistema, mas a condição mínima agora nos faz assumir \(\rho_{1,4}=0\), portanto, obtemos \(\rho_{2,4}=1/3\) como antes. Naturalmente, a condição de contorno \(\rho_{1,4}=0\) era óbvia desde o início para construir nosso sistema de equações e não temos de preocuparmos sobre soluções mínimas não negativos.
Nos casos em que o espaço de estados é infinito, pode não ser possível escrever uma condição de contorno correspondente. Então, como veremos em exercícios, a condição mínima é essencial. Agora vamos apresentar um resultado geral do tempo médio para atingir um conjunto de estados \(A\). Recordemos que \(\mbox{E}_x(T_A)\) foi definida, onde \(T_A\) é o tempo mínimo da primeira vez que \(\{C_n\}_{n\ge 1}\) atinge \(A\).
Na demonstração do seguinte teorema a seguir vamos utilizar a função indicadora do conjunto \(\{y\}\), \(\pmb{1}_{y}(z)\), \(z\in S\), definida por \begin{equation} \pmb{1}_y(z) \, = \, \left\{ \begin{array}{cc} 1, & z=y \\ 0, & z\neq y \end{array}\right.\cdot \end{equation}
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O vetor de tempos médios \(\{\mbox{E}_x(T_A), \; x\in S\}\), os tempos médios de primeira visita ao conjunto \(A\) a partir de qualquer estado \(x\in S\), é a solução não negativa mínima do sistema de equações lineares \begin{equation} \begin{array}{ll} \mbox{E}_x(T_A) = 0, & \forall x\in A \\[0.8em] \mbox{E}_x(T_A) = \displaystyle 1+\sum_{y\notin A} p_{x,y}\mbox{E}_y(T_A), & \forall x\notin A\cdot \end{array} \end{equation}
Primeiro vamos provar que o sistema \(\{\mbox{E}_x(T_A), \; x\in S\}\) satisfaz o teorema. Se \(C_0=x\in A\), então \(T_A=0\) e portanto \(\mbox{E}_x(T_A)=0\). Caso \(C_0=x\notin A\), então \(T_A\geq 1\) de forma que, pela propriedade markoviana, \begin{equation} \mbox{E}_x(T_A \, | \, C_1=y) \, = \, 1+\mbox{E}_y(T_A) \end{equation} e \begin{equation} \mbox{E}_x(T_A) \, = \, \displaystyle \sum_{y\in S} \mbox{E}_x\big(T_A1_y(C_1)\big) \, = \, 1+ \displaystyle \sum_{y\in S} \mbox{E}_x(T_A \, | \, C_1=y)P_x(C_1=y) \, = \, 1+\sum_{y\notin A} p_{x,y}\mbox{E}_y(T_A)\cdot \end{equation} Suponhamos agora que \(\mbox{E}^*_x(T_A)\), \(x\in S\), seja uma outra solução do sistema. Então \(\mbox{E}^*_x(T_A)=0\) para \(x\in A\). Se \(x\notin A\), então \begin{equation} \begin{array}{rcl} \mbox{E}^*_x(T_A) & = & \displaystyle 1+\sum_{y\notin A} p_{x,y}\mbox{E}^*_y(T_A) \, = \, \displaystyle 1+\sum_{y\notin A} p_{x,y}\left( 1+\sum_{z\notin A}p_{y,z}\mbox{E}^*_z(T_A) \right) \\[0.8em] & = & \displaystyle P_x(T_A\geq 1)+P_x(T_A\geq 2)+\sum_{y\notin A}\sum_{z\notin A}p_{x,y}p_{y,z}\mbox{E}^*_z(T_A)\cdot \end{array} \end{equation} Depois de repetir diversas vezes a substituição da expressão de \(\mbox{E}^*_x(T_A)\) do termo final obtemos que, depois de \(n\) passos \begin{equation} \mbox{E}^*_x(T_A) \, = \, P_x(T_A\geq 1)+\cdots+P_x(T_A\geq n)+ \sum_{z_1\notin A}\cdots \sum_{z_n\notin A}p_{x,z_1}p_{z_1,z_2}\cdots p_{z_{n-1},z_n}\mbox{E}^*_{z_n}(T_A)\cdot \end{equation} Logo, se \(\mbox{E}^*_x(T_A)\) for não negativo, \begin{equation} \mbox{E}^*_x(T_A)\geq P_x(T_A\geq 1)+\cdots+P_x(T_A\geq n) \end{equation} e, fazendo \(n\to\infty\), \begin{equation*} \mbox{E}^*_x(T_A)\geq \sum_{n=1}^\infty P_x(T_A\geq n) \, = \, \mbox{E}_x(T_A)\cdot \end{equation*}
▉Quanto tempo demora até que a cadeia atinja o conjunto \(\{1,4\}\)?
Vejamos o sistema de equações para \(\mbox{E}_x(T_{\{1,4\}})\), \(x\in\{1,2,3,4\}\).
Primeiro \begin{equation} \mbox{E}_1(T_{\{1,4\}})=\mbox{E}_4(T_{\{1,4\}})=0\cdot \end{equation} Também \begin{equation*} \mbox{E}_2(T_{\{1,4\}}) \, = \,1+p_{2,2}\mbox{E}_2(T_{\{1,4\}})+p_{2,3}\mbox{E}_3(T_{\{1,4\}}) \end{equation*} e \begin{equation*} \mbox{E}_3(T_{\{1,4\}})=1+p_{3,2}\mbox{E}_2(T_{\{1,4\}})+p_{3,3}\mbox{E}_3(T_{\{1,4\}})\cdot \end{equation*} Não é difícil obter que \(\mbox{E}_2(T_{\{1,4\}})=\mbox{E}_3(T_{\{1,4\}})=2\).Queremos agora classificar os estados segundo a possibilidade de atingir cada estado a partir de qualquer outro. Uma vez classificados os estados, teremos como resultado as direções que pode tomar a cadeia com o passar do tempo.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O estado \(a\in S\) é chamado de estado absorvente se \(p_{a,a}=1\) ou, equivalentemente, se \(p_{a,y}=0\), para todo \(y\neq a\).
Observemos que isto quer dizer que um estado do qual a cadeia não pode fugir uma vez que chegou nele, por isso é chamado de estado absorvente, absorve a cadeia. Isto acontece no caso do Exemplo I.6, o exemplo do Fast food, nesse caso o estado 4 é absorvente, isto devido a que \(p_{4,4}=1\).
Vamos mostrar que se \(a\) é um estado absorvente, então \begin{equation} p^{(n)}_{x,a}=P_x(T_a\le n), \end{equation} para \(n\ge 1\). Se \(a\) é um estado absorvente, então \(p^{(n-m)}_{a,a}=1\) se \(1\le m\le n\) e então \begin{equation} \begin{array}{rcl} p^{(n)}_{x,a} & = & \displaystyle \sum_{m=1}^n P_x(T_a=m)p^{(n-m)}_{a,a} \, = \, \displaystyle \sum_{m=1}^n P_x(T_a=m) \, = \, P_x(T_a\le n) \cdot \end{array} \end{equation}
Observemos a matriz de probabilidades de transição fornecida no Exemplo I.9. Claramente temos dois estados absorventes: \(\{AA,AA\}\) e \(\{aa,aa\}\). A dúvida é se existe algum outro estado que seja absorvente, ou seja, pelo que demonstramos no Exemplo II.6 se partirmos de qualquer estado \(x\), com probabilidade positiva vamos chegar à \(a\), o estado absorvente num tempo finito \(n\). Isto acontece nesta cadeia? com os seguintes comandos R vamos demonstrar que isso não acontece:
Observe que \begin{equation} P_x(T_y=1)=P_x(C_1=y)=p_{x,y}, \end{equation} e que \begin{equation} P_x(T_y=2)=\sum_{z\neq y} P_x(C_1=z,C_2=y)=\sum_{z\neq y} p_{x,z}p_{z,y} \cdot \end{equation}
Na situação de altos valores de \(n\), as probabilidades \(P_x(T_y=n)\) podem ser encontradas utilizando a expressão \begin{equation} P_x(T_y=n+1)=\sum_{z\neq y} p_{x,z}P_z(T_y=n) \end{equation} caso \(n\ge 1\). Para chegar ao estado \(y\) partindo do estado \(x\), pela primeira vez no tempo \(n+1\), é necessário ir a algum estado \(z\neq y\) num primeiro passo e então ir do estado \(z\) ao estado \(y\) pela primeira vez no final de \(n\) passos adicionais.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). O estado \(y\in S\) é chamado de recorrente se \(\rho_{y,y}=1\) caso contrário, isto é, se \(\rho_{y,y}<1\) o estado \(y\) é chamado de transiente.
Se o estado \(y\) for recorrente, a Cadeia de Markov partindo de \(y\) retorna a \(y\) com probabilidade 1. Se o estado \(y\) é transiente, a Cadeia de Markov partindo de \(y\) tem probabilidade positiva \(1-\rho_{y,y}\) de nunca voltar ao estado \(y\). Se \(y\) for um estado absorvente, então \(P_y(T_y=1)=p_{y,y}=1\) e, então \(\rho_{y,y}=1\), portanto um estado absorvente é necessariamente recorrente.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). Definimos a variável aleatória \(N(y)\) como o número de vezes \(n\ge 1\), que a cadeia está no estado \(y\in S\).
A variável aleatória indicadora foi definida anterioemente e utilizando-a, vemos que \(1_y(C_n)=1\) se a cadeia está no estado \(y\) no tempo \(n\) e \(1_y(C_n)=0\) caso contrário, vemos que \begin{equation} N(y)=\sum_{n=1}^\infty 1_y(C_n) \cdot \end{equation} Também observamos que o evento \(\{N(y)\ge 1\}\) é o mesmo do que o evento \(\{T_y<\infty\}\). Então \begin{equation} P_x(N(y)\ge 1)=P_x(T_y<\infty)=\rho_{x,y} \cdot \end{equation}
Sejam \(m\) e \(n\) dois números inteiros positivos. Sabemos que a probabilidade com a qual a Cadeia de Markov, começando em \(x\) visitar pela primeira vez o estado \(y\) no tempo \(m\) e visitar novamente \(y\), \(n\) unidades de tempo depois é \begin{equation} P_x(T_y=m)P_y(T_y=n)\cdot \end{equation} Então, \begin{equation*} \begin{array}{rcl} P_x\big(N(y)\ge 2\big) & = & \displaystyle \sum_{m=1}^\infty \sum_{n=1}^\infty P_x(T_y=m)P_y(T_y=n) \\[0.6em] & = & \displaystyle \left[\sum_{m=1}^\infty P_x(T_y=m)\right]\left[\sum_{m=1}^\infty P_y(T_y=n)\right] \\ & = & \rho_{x,y}\rho_{y,y} \cdot \end{array} \end{equation*} Similarmente, concluímos que \begin{equation} P_x(N(y)\ge m)=\rho_{x,y}\rho_{y,y}^{m-1}, \qquad m\ge 1\cdot \end{equation}
Agora estamos em condições de encontrar a expressão da probabilidade de que uma cadeia visite um estado um determinado número de vezes. Como veremos posteriormente, utilizando estas relações vamos obter resultados mais poderosos que nos permitirão encontrar as probabilidades de atingirmos um determinado estado.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). Então \begin{equation} P_x(N(y)=m)=\rho_{x,y}\rho_{y,y}^{m-1}(1-\rho_{y,y}), \qquad m\ge 1\cdot \end{equation}
Observemos que \begin{equation} P_x\big(N(y)=m\big)=P_x\big(N(y)\ge m\big)-P_x\big(N(y)\ge m+1\big)\cdot \end{equation}
▉Também, \begin{equation} P_x\big(N(y)=0\big)=1-P_x\big(N(y)\ge 1\big), \end{equation} de maneira que \begin{equation} P_x\big(N(y)=0\big)=1-\rho_{x,y}\cdot \end{equation}
Para perceber porque o resultado do teorema deve ser verdade observemos, por exemplo, que uma cadeia começando em \(x\) visita o estado \(y\) exatamente \(m\) vezes se, e somente se, a cadeia visita ao estado \(y\) por uma primeira vez, retorna a \(y\) \(m-1\) vezes adicionais e depois nunca mais volta a \(y\).
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Definimos por \(\mbox{E}_x(C_n)\) a esperança da variável aleatória \(C_n\) na cadeia começando no estado \(x\).
Por exemplo, \begin{equation} \mbox{E}_x\big(1_y(C_n)\big)=P_x(C_n=y)=p^{(n)}_{x,y}\cdot \end{equation} Segue da expressão acima que \begin{equation*} \begin{array}{rcl} \mbox{E}_x\big(N(y)\big) & = & \displaystyle \mbox{E}_x\left(\sum_{n=1}^\infty 1_y(C_n)\right) \, = \, \displaystyle \sum_{n=1}^\infty \mbox{E}_x\left(1_y(C_n)\right) \, = \, \displaystyle \sum_{n=1}^\infty p^{(n)}_{x,y}, \end{array} \end{equation*} sendo que \begin{equation} \mbox{E}_x\big(N(y)\big)=\sum_{n=1}^\infty p^{(n)}_{x,y}, \end{equation} constitui uma forma prática para encontrar o número esperado de vezes que a cadeia visita o estado \(y\) partindo do estado \(x\).
Lembremos o Exemplo I.6 (Fast food). Vamos verificar se há estados absorventes, transientes e recorrentes e identificá-los:
Encontremos agora o número esperado de vezes que a cadeia assume o valor 1 partido de 1. Utilizando a expressão \begin{equation*} \mbox{E}_1\big(N(1)\big)=\sum_{n=1}^\infty p^{(n)}_{1,1}, \end{equation*} temos que \(\mbox{E}_1\big(N(1)\big)=0.3333333\). Por outro lado \(\mbox{E}_1\big(N(2)\big)=2\). Como foram obtidos estes números?
Utilizando a linguagem de programação R podemos fazer os cálculos necessários para encontrar \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in S\). No Exemplo II.1 foi introduzido a forma de construir a matriz de probabilidades de transição para sua posterior utilização em nossos cálculos. Aprendemos a encontrar as probabilidades \(p^{(n)}_{x,y}\), qualquer seja o valor finito de \(n\). Agora necessitamos mais um passo, somar essas probabilidades. Para isso definimos a função Soma, de argumentos a matriz \(\mathcal{P}\) e o número de somas.
Obtemos por resultado uma matriz que constitui uma boa aproximação de \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in S\) e que justifica os valores anteriormente apresentados de \(\mbox{E}_1\big(N(1)\big)\) e \(\mbox{E}_1\big(N(2)\big)\).
AssimUm detalhe interessante é que se aumentarmos o número de somas, os valores de \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in\{0,1,2,3\}\) não mudam.
Podemos afirmar então que o número esperado de vezes que a cadeia visita o estado 3 partindo de 0 é \(\mbox{E}_0\big(N(3)\big)=4\).
Qual é o número médio de refeições necessário para completar a coleção?
A resposta é indireta, no sentido de que seriam necessários pelo menos 8, seriam necessários pelo menos \begin{equation} \mbox{E}_0\big(N(1)\big) \, + \, \mbox{E}_0\big(N(2)\big) \, + \, \mbox{E}_0\big(N(3)\big) \end{equation} refeições para completar a coleção.
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Temos duas situações:
Seja \(y\) um estado transiente. Dado que \(0\le\rho_{y,y}<1\), segue que \begin{equation} P_x\big(N(y)=\infty\big)=\lim_{m\to\infty} P_x\big(N(y)\ge m\big)=\lim_{m\to\infty} \rho_{x,y}\rho_{y,y}^{m-1}=0\cdot \end{equation} Agora, \begin{equation} \mbox{E}_x\big(N(y)\big) \, = \, \displaystyle \sum_{m=1}^\infty mP_x\big(N(y)=m\big) \, = \, \displaystyle \sum_{m=1}^\infty m\rho_{x,y}\rho_{y,y}^{m-1}(1-\rho_{y,y}) \cdot \end{equation} Observemos que \(\displaystyle \mbox{E}_x\big(N(y)\big)=\rho_{x,y}(1-\rho_{y,y})\sum_{m=1}^\infty m\rho_{y,y}^{m-1}\), e que a série de potências na expressão anterior é convergente, de soma \begin{equation} \sum_{m=1}^\infty m\rho_{y,y}^{m-1}=\dfrac{1}{(1-\rho_{y,y})^2}, \end{equation} do qual concluímos que \begin{equation*} \mbox{E}_x\big(N(y)\big)=\dfrac{\rho_{x,y}}{1-\rho_{x,y}}, \end{equation*} e provamos o item 1. Seja agora \(y\) um estado recorrente. Então \(\rho_{y,y}=1\) e segue que \begin{equation} \begin{array}{rcl} P_x\big(N(y)=\infty\big) & = & \displaystyle \lim_{m\to\infty} P_x\big(N(y)\ge m\big) \\[0.8em] & = & \displaystyle \lim_{m\to\infty} \rho_{x,y}=\rho_{x,y}\cdot \end{array} \end{equation} Em particular, \(P_y\big(N(y)=\infty\big)=1\). Se uma variável aleatória não negativa tem probabilidade positiva de ser infinita, então sua esperança é infinita. Logo \begin{equation*} \mbox{E}_y\big(N(y)\big)=\infty\cdot \end{equation*} Se \(\rho_{x,y}=0\), então \(P_x\big(T_y=m\big)=0\) para todo inteiro positivo finito \(m\), implica que \(p^{(n)}_{x,y}=0\), para \(n\ge 1\) e, portanto, \(\mbox{E}_x\big(N(y)\big)=0\) neste caso. Se \(\rho_{x,y}>0\), então \(P_x\big(N(y)=\infty\big)=\rho_{x,y}>0\) e, por isso, \(\mbox{E}_x\big(N(y)\big)=\infty\).
▉Este teorema descreve a diferença fundamental entre um estado transiente e um estado recorrente. Se \(y\) é um estado transiente, então não importa onde a Cadeia de Markov começou, ela fará apenas um número finito de visitas a \(y\) e o número esperado de visitas ao \(y\) é finito. Suponha, ao invés disso, que \(y\) seja um estado recorrente. Se a Cadeia de Markov começa em \(y\), ela voltará ao \(y\)infinitas vezes. Se a cadeia começa em algum outro estado \(x\), pode ser impossível para ela sempre atingir \(y\). Se for possível, no entanto, e a cadeia não visitar \(y\) pelo menos uma vez, então o fará infinitamente vezes.
Uma Cadeia de Markov \(\{C_n\}\) é chamada de cadeia transiente se todos os seus estados forem estados transientes.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(\mathbb{N}\), os números naturais e probabilidades de transição \(p_{x,x+1}=3/4\) e \(p_{x,x-1}=1/4\), \(\forall x\in\mathbb{N}\). Demonstremos que esta é uma cadeia transiente.
Uma das formas de percebermos que esta é uma cadeia transiente é observando que \begin{equation*} C_n=C_0+\xi_1+\cdots+\xi_n, \end{equation*} onde \(\xi_i=1\) com probabilidade 3/4 e \(\xi_i=-1\) com probabilidade 1/4, \(i=1,\cdots\). Estas podem ser consideradas como os resultados dos lançamentos de moedas viciadas, constituindo variáveis aleatórias independentes e igualmente distribuídas.
Pela Lei dos Grandes Números temos que \(C_n/n\) converge para \(\mbox{E}(C_n)\), quando \(n\to\infty\). Desde que \(\mbox{E}(C_n)=1/2\), então \(C_n/n\to 1/2\), quando \(n\to\infty\). Isto significa que não podemos visitar qualquer estado infinitas vezes.
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). Então, se o espaço de estados \(S\) for finito a cadeia deve ter pelo menos um estado recorrente e, portanto, não pode ser uma cadeia transiente.
Primeiro observemos que se \(y\in S\) for um estado transiente, então \begin{equation} \mbox{E}_x\big(N(y)\big)=\sum_{n=1}^\infty p^{(n)}_{x,y}<\infty, \qquad x\in S \end{equation} do qual concluímos que \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y}=0\), \(x\in S\). Se \(S\) for finito e com todos os estados transientes, temos que \begin{equation} 0 \, = \, \displaystyle \sum_{y\in S} \lim_{n\to\infty} p^{(n)}_{x,y} \, = \, \displaystyle \lim_{n\to\infty} \sum_{y\in S} p^{(n)}_{x,y} \, = \, \displaystyle \lim_{n\to\infty} P_x(C_n\in S) \, = \,\lim_{n\to\infty} 1=1, \end{equation} o qual é uma contradição.
▉Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). Se \(y\in S\) for um estado transiente, então \begin{equation} \lim_{n\to\infty} p_{x,y}^{(n)}=0\cdot \end{equation}
Exercício.
▉Considere uma Cadeia de Markov com matriz de transição \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 1 \quad & \;\, 2 \; & \quad 3 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} & \begin{pmatrix} \; 1/3 \, & \; 1/3 \; & \; 1/3 \; \\ \; 1/4 \; & \; 3/4 & 0 \\ \; 0 \; & \; 0 & 1 \end{pmatrix}\cdot \end{matrix} \end{equation} Queremos encontrar \(P_1(T_1<\infty)\) e \(P_1(T_2<\infty)\).
Devemos observar que o Corolário permite-nos caracterizar os estados transientes. Observemos que \begin{equation*} \mathcal{P}^{1000}=\begin{pmatrix} 2.703815e^{-48} & 6.103413e^{-48} & 1 \\ 4.577560e^{-48} & 1.033308e^{-47} & 1 \\ 0 & 0 & 1 \end{pmatrix}, \end{equation*} com o qual fica claro que os estados 1 e 2 são transientes e o estado 3 é absorvente, portanto, recorrente. Também, temos que \(\mbox{E}_1\big(N(1)\big)=1/2\) e \(\mbox{E}_1\big(N(2)\big)=1/3\). Agora, pelo Teorema 12 chegamos a que \(\rho_{1,1}=1/3\) e \(\rho_{1,2}=1/4\).
Uma Cadeia de Markov \(\{C_n\}\) é chamada de cadeia recorrente se todos os seus estados forem estados recorrentes.
Observemos que nesta situação os estados 0, 1, 2 e 3 são transientes e o estado 4 é recorrente. Logo, este é um exemplo de uma cadeia que não é recorrente nem transiente. Ainda podemos observar em quais estados \(\displaystyle \lim_{n\to\infty} p_{x,y}^{(n)}=0\) e, termos assim, mais uma caracterização de estados transientes.
Percebemos com este exemplo que nem todas as cadeias devem ser ou transientes ou recorrentes. Pelo Teorema II.10 sabemos que cadeias transientes, se existirem, devem ter espaço de estados infinito. O seguinte exemplo nos mostra que cadeias recorrentes existem.
Consideramos um cliente que escolhe entre duas marcas de pasta de dentes \(A\) ou \(B\), em várias ocasiões. Vamos considerar \(C_n=A\) se o cliente escolhe a marca \(A\) na \(n\)-ésima compra e \(C_n=B\), se o cliente escolhe a marca \(B\) na \(n\)-ésima compra. Nesta situação, a sequência de estados \(C_1,C_2,\cdots\) é um processo estocástico com dois estados possíveis em cada tempo.
As probabilidades de compra foram especificadas, dizendo que o cliente vai escolher a mesma marca que na compra anterior com probabilidade 1/3 e vai mudar de marca com probabilidade 2/3. Desde que isso acontece independentemente das compras anteriores, vemos que este processo estocástico é uma Cadeia de Markov estacionária com matriz de transição \begin{equation} \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & \;\, B \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} A \\ B \end{matrix} & \begin{pmatrix} \; 1/3 \, & \; 2/3 \; \\ \; 2/4 \; & \; 1/3 \end{pmatrix}\cdot \end{matrix} \end{equation} Este é um exemplo de Cadeia de Markov recorrente, devido a que os estados \(A\) e \(B\) ambos são recorrentes.
Para verificar esta afirmação utilizamos a função Soma, obtendo-se
Isto mostra que \begin{equation} \mbox{E}_A\big(N(A)\big) \, = \, \mbox{E}_A\big(N(B)\big) \, = \, \mbox{E}_B\big(N(A)\big) \, = \, \mbox{E}_B\big(N(B)\big) \, = \, \infty\cdot \end{equation} Logo, os estados desta cadeia são recorrentes, pelo Teorema II.9, item 2.
De uma semana para a seguinte, os coelhos alteram a classificação de um grupo para o outro, de acordo com a seguinte matriz de transição: \begin{equation*} \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 1 & 2 & 3 & 4 \\ 5/7 & 2/7 & 0 & 0 \\ 0 & 1/2 & 1/3 & 1/6 \\ 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 1/4 & 3/4 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \end{equation*}