4 Distribuição estacionária


Se todos os estados em uma Cadeia de Markov forem transientes, as probabilidades de estado em \(n\) passos se aproximam de zero e, se a cadeia tiver alguns estados transientes e outros recorrentes, eventualmente, o processo entra e permanece mudando entre os estados recorrentes. Portanto, podemos nos concentrar na classe dos estados recorrentes ao estudar as probabilidades limites de uma cadeia.

Suponha uma função de probabilidade definida em \(S\) tal que, se a nossa Cadeia de Markov começa com distribuição inicial \(\pi_0=\pi\), então nós também temos \(\pi_1=\pi\). Isto é, se a distribuição no tempo 0 é \(\pi\), então a distribuição no tempo 1 será ainda \(\pi\). Então \(\pi\) é chamada uma distribuição estacionária.

Os resultados apresentados aqui foram consultados de diversos livros, dentre eles destacamos Hoel, Port, and Stone (1972), Kemeny and Snell (1976) e Doob (1953).


Definição 4.1.

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)\). Se \(\pi(x)\), com \(x\in S\) satisfaz que é formada de números não negativos que somam um e se \[ \sum_x \pi(x) p_{x,y}=\pi(y), \qquad y\in S \] então \(\pi\) será chamada de distribuição estacionária.


Suponha que a distribuição estacionária \(\pi\) exista e satisfaça que \[ \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y), \qquad y\in S \cdot \] Então, como veremos em breve, independentemente da distribuição inicial da cadeia, a distribuição de \(C_n\) se aproxima de \(\pi\) quando \(n\to\infty\). Em tais casos, \(\pi\) será, por vezes, chamada de distribuição de estado estacionária.

Nesta seção vamos determinar qual Cadeia de Markov tem distribuição estacionária, quando esta distribuição é única e quando o limite acima se cumpre.


Exemplo 4.1.

No caso de uma Cadeia de Markov com espaço de estados \(S=\{0,1\}\) e matriz de transição \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; 0 \quad & \quad 1 \; \end{matrix} \\ \Gamma \, = \, \begin{matrix} 0 \\ 1 \end{matrix} & \begin{pmatrix} \; 1-p & \, p \; \\ q & 1-q \end{pmatrix} \end{matrix}, \] com \(p+q>0\), esta cadeia tem uma única distribuição estacionária \(\pi\), dada por \[ \pi(0)=\frac{q}{p+q} \quad \mbox{e} \quad \pi(1)=\frac{p}{p+q} \cdot \]

Podemos mostrar também que se \(0 < p+q < 2\), a expressão no limite acima é válida.


Para Cadeias de Markov tendo um número finito de estados, as distribuições estacionárias podem ser encontradas resolvendo um sistema de equações lineares finito.


Exemplo 4.2.

Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2\}\) e matriz de probabilidades de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 \\ 1/3 & 1/3 & 1/3 \\ 1/4 & 1/2 & 1/4 \\ 1/6 & 1/3 & 1/2 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

Mostraremos que esta cadeia tem uma única distribuição estacionária \(\pi\) e a encontraremos.

A expressão na Definição 4.1 fornece, nesta situação, as seguintes três equações: \[ \begin{array}{rcl} \dfrac{\pi(0)}{3}+\dfrac{\pi(1)}{4}+\dfrac{\pi(2)}{6} & = & \pi(0), \\[1.2em] \dfrac{\pi(0)}{3}+\dfrac{\pi(1)}{2}+\dfrac{\pi(2)}{3} & = & \pi(1), \\[1.2em] \dfrac{\pi(0)}{3}+\dfrac{\pi(1)}{4}+\dfrac{\pi(2)}{2} & = & \pi(2), \end{array} \] e, pelo fato de, \(\sum_x \gamma(x)=1\), temos a quarta equação \[ \pi(0)+\pi(1)+\pi(2)=1 \cdot \]

Multiplicando por dois a primeira equação e subtraindo-a da segunda equação conseguimos eliminar \(\pi(2)\) e descobrir que \(\pi(1)= 5\pi(0)/3\). Concluimos a partir da primeira equação que \(\pi(2)=3\pi(0)/2\). Da quarta equação, agora vemos que \[ \pi(0)\left(1+\frac{5}{3}+\frac{3}{2}\right)=1, \] e, portanto, que \(\pi(0)=\frac{6}{25}\). Assim, \[ \pi(1)=\frac{5}{3}\times \frac{6}{25}=\frac{2}{5} \] e \[ \pi(2)=\frac{3}{2}\times \frac{6}{25}=\frac{9}{25} \cdot \]

Pode ser visto que estes números satisfazem todas as quatro equações. Uma vez que são não-negativos, a distribuição estacionária única é dada por \[ \pi=\left(\dfrac{6}{25},\dfrac{2}{5},\dfrac{9}{25}\right)\cdot \] Embora não seja fácil ver diretamente, a expressão no limite logo depois da definição é válida para esta cadeia.


Escrevendo as equações desta forma nem sempre é a melhor coisa a fazer. Em vez de eliminar equações, introduzimos mais, esperando ser capazes de escolher, dentre elas, um conjunto de equações linearmente independentes que possam ser mais facilmente resolvidas.


Exemplo 4.3.

Considere a cadeia de Ehrenfest descrita no Exemplo 8 e suponha que \(d=3\). Encontremos a distribuição estacionária. Nestas condições, a matriz de probabilidades de transição é \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 \\ 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 1 & 0 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 12 \end{matrix} } \right ) \end{matrix} \]

Similar ao exemplo anterior, encontramos que a distribuição estacionária é única e dada por \[ \pi=\left(\dfrac{1}{8},\dfrac{3}{8},\dfrac{3}{8},\dfrac{1}{8}\right)\cdot \]


A expressão \[ \displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y), \] \(y\in S\) não se cumpre para a cadeia no Exemplo 4.3, dado que \(p^{(n)}_{x,x}=0\) para todo valor impar de \(n\). Por exemplo, mostramos o comportamento da matriz e probabilidades de transição do Exemplo 4.3 com os comandos R abaixo:

library(markovchain)
Estados = c("0", "1", "2", "3")
Prob.T=matrix(c(0,1,0,0,1/3,0,2/3,0,0,2/3,0,1/3,0,0,1,0), 
              nrow = 4, ncol = 4,byrow=T, dimnames=list(Estados,Estados))
ProbT = new("markovchain", states=Estados, transitionMatrix=Prob.T, name="Exemplo")
ProbT^2
## Exemplo^2 
##  A  4 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3 
##  The transition matrix  (by rows)  is defined as follows: 
##           0         1         2         3
## 0 0.3333333 0.0000000 0.6666667 0.0000000
## 1 0.0000000 0.7777778 0.0000000 0.2222222
## 2 0.2222222 0.0000000 0.7777778 0.0000000
## 3 0.0000000 0.6666667 0.0000000 0.3333333
ProbT^3
## Exemplo^3 
##  A  4 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3 
##  The transition matrix  (by rows)  is defined as follows: 
##           0         1         2         3
## 0 0.0000000 0.7777778 0.0000000 0.2222222
## 1 0.2592593 0.0000000 0.7407407 0.0000000
## 2 0.0000000 0.7407407 0.0000000 0.2592593
## 3 0.2222222 0.0000000 0.7777778 0.0000000
ProbT^4
## Exemplo^4 
##  A  4 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3 
##  The transition matrix  (by rows)  is defined as follows: 
##           0         1         2         3
## 0 0.2592593 0.0000000 0.7407407 0.0000000
## 1 0.0000000 0.7530864 0.0000000 0.2469136
## 2 0.2469136 0.0000000 0.7530864 0.0000000
## 3 0.0000000 0.7407407 0.0000000 0.2592593
ProbT^5
## Exemplo^5 
##  A  4 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3 
##  The transition matrix  (by rows)  is defined as follows: 
##           0         1         2         3
## 0 0.0000000 0.7530864 0.0000000 0.2469136
## 1 0.2510288 0.0000000 0.7489712 0.0000000
## 2 0.0000000 0.7489712 0.0000000 0.2510288
## 3 0.2469136 0.0000000 0.7530864 0.0000000

Podemos modificar a cadeia Ehrenfest um pouco e evitar esse tipo de comportamento periódico.


Exemplo 4.4: Cadeia de Ehrenfest modificada.

Suponha que temos duas caixas rotuladas 1 e 2 e também \(d\) bolas rotuladas por \(1,2,\cdots,d\). Inicialmente, algumas das bolas estão na caixa 1 e as restantes estão na caixa 2. Um número inteiro é escolhido aleatoriamente de \(1,2,\cdots,d\) e a bola marcada por esse inteiro é removida de sua caixa.

Vamos agora selecionar aleatoriamente uma das duas caixas e colocar a bola removida nessa caixa. O procedimento será repetido indefinidamente e as seleções serão realizadas de forma independente. Definamos \(C_n\) como o número de bolas na caixa 1 após o \(n\)-ésimo experimento. Então, \(\{C_n\}_{n\ge 0}\), é uma Cadeia de Markov no espaço de estados \(S=\{0,1,\cdots,d\}\).

Encontremos a distribuição estacionária desta cadeia para \(d=3\). A matriz de probabilidades de transição, nesta situação, é \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 \\ 1/2 & 1/2 & 0 & 0 \\ 1/6 & 1/2 & 1/3 & 0 \\ 0 & 1/3 & 1/2 & 1/6 \\ 0 & 0 & 1/2 & 1/2 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 12 \end{matrix} } \right ) \end{matrix} \]

Para ver por que \(\mathcal{P}\) é dada como indicado, vamos encontrar \(p_{1,y}\), \(0\le y\le 3\). Começamos com uma bola na caixa 1 e duas bolas na caixa 2. Então \(p_{1,0}\) será a probabilidade de que a bola selecionada seja da caixa 1 e que a caixa selecionada seja a 2. Assim \[ p_{1,0}=\frac{1}{3}\times \frac{1}{2}=\frac{1}{6} \cdot \] Em segundo lugar, \(p_{1,2}\) será a probabilidade de que a bola selecionada seja da caixa 2 e a caixa selecionada seja a 1. Assim \[ p_{1,2}=\frac{2}{3}\times \frac{1}{2}=\frac{1}{3} \cdot \] Logicamente \(p_{1,3}=0\), dado que, no máximo, uma bola é transferido de cada vez. Finalmente, \(p_{1,1}\) pode ser obtido por subtração de \(p_{1,0}+p_{1,2}+p_{1,3}\) de 1. Alternativamente, \(p_{1,1}\) será a probabilidade de que tanto a bola selecionada quanto a caixa selecionado sejam a caixa 1 ou a bola selecionada é da caixa 2 e a caixa selecionada também seja a caixa 2. Assim \[ p_{1,1}=\frac{1}{3}\times \frac{1}{2}+\frac{2}{3}\times \frac{1}{2}=\frac{1}{2} \cdot \] As outras probabilidades são calculados de forma semelhante.

Vê-se facilmente que \(\pi(x)\), \(0\le x\le 3\), são os mesmos que no exemplo anterior e, portanto, a distribuição estacionária é novamente dada por \[ \pi=\left(\dfrac{1}{8},\dfrac{3}{8},\dfrac{3}{8},\dfrac{1}{8}\right)\cdot \] Provaremos posteriormente que \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y)\), \(\forall y\in S\) será válida neste exemplo.


4.1 Propriedades


Vamos introduzir a noção de “fluxo de probabilidade” de um conjunto \(A\) de estados para o seu complemento sob uma distribuição.


Definição 4.2: Probabilidade de fluxo.

Seja \(\{C_n\}\) uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\) e espaço de estados \(S\). Definimos a probabilidade de fluxo do conjunto de estados \(A\subset S\) ao seu complemento, baixo a distribuição \(\pi\) como \[ p_{_{A, \,A^c}}=\sum_{x\in A}\sum_{y\in A^c} \pi(x) p_{x,y}\cdot \] Dizemos que \(\pi(x) p_{x,y}\) é o fluxo de probabilidade entre \(x\) e \(y\). Assim \(p_{_{A, \, A^c}}\) é o fluxo de probabilidades totais entre cada elemento de \(A\) e \(A^c\).


Observemos que ao mencionarmos \(\pi\) como uma distribuição na definição anterior nos referimos a uma função de probabilidade definida em \(S\), não necessariamente sendo a distribuição estacionária. Este conceito será útil para caracterizar a distribuição estacionária, resultado apresentado a continuação.


Teorema 4.1

Seja \(p_{_{A, \, A^c}}\) o fluxo de probabilidade de uma Cadeia de Markov com espaço de estados \(S\). A função \(\pi\) é a distribuição estacionária se, e somente se, \(\sum_{x\in S} \pi(x)=1\) e \[ p_{_{A, \, A^c}} \, = \, p_{_{A^c, \, A}}, \] para todo \(A\subset S\).


Demonstração.

Seja \(\pi\) a distribuição estacionária, sabemos que \(\sum_x \pi(x)=1\) e ainda \(\sum_x \pi(x)p_{x,y}=\pi(y)\). Por outro lado, qualquer seja \(A\subset S\) \[ \begin{array}{rcl} p_{_{A,\, A^c}}+\gamma_{_{A^c,\, A^c}} & = & \displaystyle \sum_{x\in A}\sum_{y\in A^c} \pi(x)p_{x,y}+ \sum_{x\in A^c}\sum_{y\in A^c} \pi(x)p_{x,y} \\[0.2em] & = & \displaystyle \sum_{y\in A^c} \left( \sum_{x\in A} \pi(x)p_{x,y}+\sum_{x\in A^c} \pi(x)p_{x,y} \right) \, = \, \displaystyle \sum_{y\in A^c} \pi(y)\cdot \end{array} \] Então \[ p_{_{A,\, A^c}} \, = \, \sum_{y\in A^c} \pi(y)-p_{_{A^c,\, A^c}}\cdot \] Similarmente \(p_{_{A^c,\, A^c}}+p_{_{A^c,\, A}}=\sum_{x\in A^c} \pi(x)\) ou \(p_{_{A^c,\, A^c}}=\sum_{x\in A^c} \pi(x)-p_{_{A^c,\, A}}\), do qual \(p_{_{A,\, A^c}}=p_{_{A^c,\, A}}\).

Suponhamos agora que \(\sum_x \pi(x)=1\) e que \(\forall A\subset S\), \[ p_{_{A,\, A^c}} \, = \, p_{_{A^c,\, A}}\cdot \] Em particular, se \(A=\{a\}\), \(A^c=\mathcal{S}\setminus \{a\}\), qualquer seja \(a\in S\). Então, \[ \begin{array}{rcl} \displaystyle \sum_{x\in A}\sum_{y\in A^c} \pi(x)p_{x,y} & = & \displaystyle \sum_{x\in A}\sum_{y\in A^c} \pi(x)p_{x,y}\\[0.2em] \displaystyle \sum_{y\in A^c} \pi(a)p_{a,y} & = & \displaystyle \sum_{x\in A^c} \pi(x) p_{x,a}, \end{array} \] do qual obtemos que \[ \begin{array}{rcl} \displaystyle \pi(a)\sum_{y\in A^c} p_{a,y} & = & \displaystyle \sum_{x\in A^c} \pi(x)p_{x,a} \\[0.2em] \pi(a)\big(1-p_{a,a}\big) & = & \displaystyle \sum_{x\in A^c} \pi(x)p_{x,a} \\[0.2em] \pi(a) & = & \displaystyle \sum_{x\in A^c} \pi(x)p_{x,a} +\pi(a)p_{a,a} \\[0.2em] \pi(a) & = & \displaystyle \sum_{x\in\mathcal{S}} \pi(x)p_{x,a}\cdot \end{array} \] Portanto, \(\pi\) é a distribuição estacionária.


Logicamente, no caso de cadeias com um número de estados razoavelmente grande, utilizar o resultado deste teorema não é a melhor forma de verificar se a função de probabilidade \(\pi\) é a distribuição estacionária. O trabalho de utilizar este resultado fica mais claro com o exemplo a seguir.


Exemplo 4.5.

No Exemplo 4.2 vemos que \(S=\{0,1,2\}\), o espaço de estados, é pequeno; deste espaço de estados definimos 6 subconjuntos \(\{0\},\{1\},\{2\},\{0,1\},\{0,2\}\) e \(\{1,2\}\), nos quais devemos verificar se a igualdade no Teorema 4.1 se satisfaz. Por exemplo, se \(A=\{0\}\), \(A^c=\{1,2\}\) e então \[ p_{_{A,\, A^c}}=\pi(0)(p_{0,1}+p_{0,2})=\dfrac{6}{25}\left(\dfrac{1}{3}+\dfrac{1}{3}\right)=\dfrac{4}{25} \] e \[ p_{_{A^c,\, A}}=\pi(1)p_{1,0}+\pi(2)p_{2,0}=\dfrac{2}{5}\times \dfrac{1}{4}+\dfrac{9}{25}\times \dfrac{1}{6}=\dfrac{4}{25}\cdot \]

Assim podemos construir a tabela a seguir \[ \begin{array}{|c|c|c|c|}\hline A & A^c & p_{_{A,\, A^c}} & p_{_{A^c,\, A}}\\\hline \{0\} & \{1,2\} & \pi(0)(p_{_{0,1}}+p_{_{0,2}})=\frac{4}{25} & \pi(1)p_{_{1,0}}+\pi(2)p_{_{2,0}})=\frac{4}{25} \\[0.8em] \{1\} & \{0,2\} & \pi(1)(p_{_{1,0}}+p_{_{1,2}})=\frac{1}{5} & \pi(0)p_{_{0,1}}+\pi(2)p_{_{2,1}})=\frac{1}{5} \\[0.8em] \{2\} & \{0,1\} & \pi(2)(p_{_{2,0}}+p_{_{2,1}})=\frac{9}{50} & \pi(0)p_{_{0,2}}+\pi(1)p_{_{1,2}})=\frac{9}{50} \\\hline \end{array} \]

As outras situações são redundantes. Desta forma verificamos que \[ \pi=\left(\dfrac{6}{25},\dfrac{2}{5},\dfrac{9}{25}\right) \] é, efetivamente, a distribuição estacionária da cadeia.


A definição de distribuição estacionária tem a ver com a probabilidade em um passo. Surge então a pergunta, o que acontece com a distribuição estacionária se utilizarmos alguma potência da probabilidade de transição?


Teorema 4.2

Seja \(\{C_n\}\) uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\) e distribuição estacionária \(\pi\). Então \[ \sum_{x\in S} \pi(x) p^{(n)}_{x,y} \, = \, \pi(y), \qquad y\in S \cdot \]

Demonstração.

Dado que \(\pi\) é a distribuição estacionária da Cadeia de Markov, então \[ \displaystyle \sum_{x\in S} \pi(x) p^{(2)}_{x,y} \, = \, \sum_{x\in S} \pi(x) \sum_{z\in S} p_{x,z}p_{z,y} \, = \, \sum_{z\in S} \left( \sum_{x\in S} \pi(x)p_{x,z}\right) p_{z,y} \, = \, \sum_{z\in S} \pi(z)p_{z,y} = \pi(y) \cdot \] Similarmente, por indução com base na fórmula \[ p^{(n+1)}_{x,y} \, = \, \sum_z p^{(n)}_{x,z}p_{z,y}, \] concluímos que para todo \(n\) vale a expressão no teorema.


Se \(C_0\) tem \(\pi\), a distribuição estacionária da cadeia, como sua distribuição inicial, temos que a igualdade no teorema implica que para todo \(n\) \[ P(C_n=y) \, = \, \pi(y), \qquad y\in S, \] e, portanto, a distribuição de \(C_n\) é independente de \(n\). Suponhamos, por outro lado, que a distribuição de \(C_n\) seja independente de \(n\), então a distribuição inicial é tal que \[ \pi_0(y) \, = \, P(C_0=y) \, = \, P(C_t=y) \, = \, \sum_{x\in S} \pi_0(x)p_{x,y} \cdot \]

Consequentemente, \(\pi_0\) é a distribuição estacionária. Em resumo, a distribuição de \(C_n\) é independente de \(n\) se, e somente se, a distribuição inicial é a distribuição estacionária.

Suponhamos agora que \(\pi\) seja a distribuição estacionária e que \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y)\), \(y\in S\) se satisfaça. Seja \(\pi_0\) a distribuição inicial. Então \[ P(C_n=y)=\sum_{x\in S} \pi_0(x)p^{(n)}_{x,y}, \qquad y\in S \] Utilizando o fato de \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y)\), \(y\in S\) e o teorema da convergência limitada, podemos fazer \(n\to\infty\) na relação acima, obtendo-se que \[ \lim_{n\to\infty} P(C_n=y)=\sum_{x\in S} \pi_0(x)\pi(y) \cdot \] Desde que \(\displaystyle \sum_x\pi_0(x)=1\), concluímos que \[ \lim_{n\to\infty} P(C_n=y)=\pi(y), \qquad y\in S \cdot \]

A expressão acima estabelece que, independentemente da distribuição inicial, para grandes valores de \(n\) a distribuição de \(C_n\) é aproximadamente igual à distribuição estacionária \(\pi\). Implica que \(\pi\) é a distribuição estacionária única. Se houvesse alguma outra distribuição estacionária poderíamos usá-la como \(\pi_0\), a distribuição inicial. Podemos concluir que \(\pi_0(y)=\pi(y)\), para \(y\in S\).

Considere um sistema descrito por uma Cadeia de Markov tendo única distribuição estacionária \(\pi\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Suponha que começamos a observar o sistema depois que ele vem acontecendo há algum tempo, digamos \(n_0\) unidades de tempo, para algum grande inteiro positivo \(n_0\). Efetivamente, observa-se \(Y_n\), \(n\ge 0\), em que \[ Y_n=C_{n+n_0}, \qquad n\ge 0 \cdot \]

As variáveis aleatórias \(Y_n\), onde \(n\ge 0\), também formam uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Para determinar probabilidades univocas para eventos definidos em termos da cadeia \(Y_n\), precisamos saber a sua distribuição inicial, que é a mesma distribuição inicial de \(C_{{n_0}}\). Na maioria das aplicações práticas, é muito difícil determinar exatamente essa distribuição. Podemos não ter escolha a não ser assumir que \(Y_n\), \(n\ge 0\), tem a distribuição estacionária \(\pi\) como sua distribuição inicial. Esta é uma suposição razoável se \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y)\), \(y\in S\) é válida para \(n_0\) grande.

4.2 Número esperado de visitas


Nesta seção, vamos considerar duas quantidades descritivas estreitamente relacionadas de interesse para as cadeias ergódicas: o tempo médio de retorno ao estado e o tempo médio para ir de um estado para outro estado.

Considere uma cadeia irredutível de nascimento e morte com distribuição estacionária \(\pi\). Suponha que \(p_{x,x}=0\), \(x\in S\), como na cadeia de Ehrenfest de ruína do jogador. Então, em cada transição a cadeia de nascimento e morte se move ou um passo para a direita ou um passo para a esquerda. Assim, a cadeia pode regressar ao ponto de partida somente após um número par de transições.

Em outras palavras, \(p_{x,x}^{(n)}=0\) para valores ímpares de \(n\). Para tais cadeias a expressão \[ \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y), \qquad y\in S, \] não se satisfaz.

Existe uma maneira de lidar com tais situações. Seja \(a_n\), \(n\ge 0\), uma sequencia de números. Se \[ \lim_{n\to\infty} a_n=L, \] para algum número finito \(L\), então \[ \lim_{n\to\infty} \dfrac{1}{n}\sum_{m=1}^n a_m=L \cdot \] A expressão anterior pode ser válida, inclusive, se \(\lim_{n\to\infty} a_n\ne L\), ou seja, se o limite não vale. Por exemplo, se \(a_n=0\) para \(n\) par e \(a_n=1\) caso \(n\) for ímpar, então \(a_n\) não tem limite quando \(n\to\infty\), porém \[ \lim_{n\to\infty} \dfrac{1}{n} \sum_{m=1}^n a_m=\dfrac{1}{2} \cdot \]

Nesta seção vamos demonstrar que \[ \lim_{n\to\infty} \dfrac{1}{n} \sum_{m=1}^n p^{(m)}_{x,y} \] existe para cada par de estados \(x,y\) de uma Cadeia de Markov arbitrária. Na Seção 4.4 usaremos a existência desses limites para determinar qual Cadeia de Markov têm distribuição estacionária e quando há uma distribuição estacionária única.

Recordemos que \[ \pmb{1}_y(z)=\left\{ \begin{array}{cr} 1, & \quad z=y \\ 0, & \quad z\neq y \end{array} \right., \] é a função indicadora e que \[ \mbox{E}_x\big(\pmb{1}_y(C_n)\big) \, = \, P_x(C_n=y)=p^{(n)}_{x,y}, \] ou seja, a esperança da função indicadora do evento \(\{C_n=y\}\) é a probabilidade de estarmos no estado \(y\) partindo do estado \(x\) depois de \(n\) passos.

Vejamos agora uma nova forma de calcular o número de visitas a um estado. O número médio de visitas a um estado é uma quantidade importante estreitamente relacionada com a distribuição estacionária.


Definição 4.3: Número de visitas.

O número de visitas da Cadeia de Markov \(\{C_n \}_{n\ge 0}\) ao estado \(y\) nos tempos \(m=1,\cdots,n\) é definido como \[ N_n(y)=\sum_{m=1}^n \pmb{1}_y(C_m) \cdot \]


Seja agora \[ G_n(x,y)=\sum_{m=1}^n p^{(m)}_{x,y}, \] então o número esperado de visitas ao estado \(y\) a partir de \(x\) é determinado de acordo com a definição acima e é dado por \[ \mbox{E}_x\big(N_n(y)\big)=G_n(x,y) \cdot \]

Se \(y\) for um estado transiente, então \[ \lim_{n\to\infty} N_n(y)=N(y) < \infty \qquad \mbox{com probabilidade um}, \] e \[ \lim_{n\to\infty} G_n(x,y)=G(x,y) < \infty, \qquad x\in S\cdot \] Segue então que \[ \lim_{n\to\infty} \dfrac{N_n(y)}{n}=0 \qquad \mbox{com probabilidade um} \] e que \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=0, \qquad x\in S\cdot \] Observe-se que \(N_n(y)/n\) é a proporção de vezes que a cadeia está no estado \(y\) nas primeiras \(n\) unidades de tempo e que \(G_n(x,y)/n\) é o valor esperado de esta proporção para uma cadeia partindo do estado \(x\).


Exemplo 4.6.

No exemplo da compra de pasta de dentes, Exemplo 2.7, vamos calcular aproximadamente o valor esperado da proporção de vezes que esta cadeia está em cada estado. A matriz de probabilidades de transição é \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; A\; & \; B \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} A \\ B \end{matrix} & \begin{pmatrix} 1/3 & 2/3 \\ 2/3 & 1/3 \end{pmatrix} \end{matrix} \]

Utilizando as linhas de comando R a seguir conseguimos calcular aproximadamente, isto é, para um valor de \(n\) finito o valor da função \(G_n(x,y)\) acima definida.

library(markovchain)
estados = c("Marca A","Marca B")
Prob.T=matrix(c(1/3,2/3,2/3,1/3), nrow=2,ncol=2,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T, 
            name="Compras de pasta de dentes")
Soma = function(M,n=10){
  mm=0;
  for(i in 1:n){mm=mm+(M^i)[]}
  mm
}


A função Soma serve como aproximação ao valor de \(G_n(x,y)\), quanto maior seja o número de somandos mais aprimorado será o resultado obtido. Por isso, utilizamos esta função com \(n=600\), a qual produz o seguinte resultado.

Soma(ProbT,600)/600
##           Marca A   Marca B
## Marca A 0.4997917 0.5002083
## Marca B 0.5002083 0.4997917


Como resultados temos que em 50% dos casos a cadeia estará em cada um dos estados partindo de qualquer um deles.


Suponha agora que \(y\) seja um estado recorrente. Seja \(m_y=\mbox{E}_y(T_y)\) o tempo de retorno médio a \(y\) para uma cadeia a partir de \(y\), se este tempo de retorno tiver esperança finita e \(m_y=\infty\) caso contrário. Vamos denotar por \(\pmb{1}_{\{T_y < \infty\}}\) a variável aleatória indicadora do evento \(\{T_y < \infty\}\), assumindo valor 1 se \(T_y < \infty\) e 0 se \(T_y=\infty\).


Teorema 4.3.

Seja \(\{C_n\}_{n\geq 0}\) uma Cadeia de Markov com espaço de estados \(S\). Seja agora \(y\in S\) um estado recorrente. Então \[ \lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{\pmb{1}_{\{T_y<\infty\}}}{m_y} \qquad \mbox{com probabilidade um} \] e \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{\rho_{x,y}}{m_y}, \qquad x\in S \cdot \]


Demonstração.

Se \(m_y=\infty\) a direita na primeira expressão acima é zero e então \(\lim_{n\to\infty} N_n(y)/n=0\), com probabilidade um e \(\lim_{n\to\infty} G_n(x,y)/n=0\), \(x\in S\) são válidas.

Logo, somente é de interesse o caso \(m_y\) finita. Para demonstrar este teorema devemos considerar algumas variáveis aleatórias adicionais. Seja uma Cadeia de Markov qualquer começando no estado recorrente \(y\). Com probabilidade um retorna ao estado \(y\) infinitas vazes. Para \(r\ge 1\) seja \(T_y^r\) o tempo mínimo da \(r\)-ésima vez que reteorna ao estado \(y\), de modo que \[ T_y^r=\min\{n\ge 1: \, N_n(y)=r\} \cdot \] Seja \(W_y^1=T_y^1=T_y\) e para \(r\ge 2\) seja \(W_y^r=T_y^r-T_y^{r-1}\) denotando o tempo de espera entre a \((r-1)\)-ésima visita a \(y\) e a \(r\)-ésima visita a \(y\). Claramente \[ T_y^r=W_y^1+\cdots+W_y^r \cdot \] As variáveis aleatórias \(W_y^1,W_y^2,\cdots\) são independentes e igualmente distribuídas e, por tanto, tem esperança comum \(\mbox{E}_y(W_y^1)=\mbox{E}_y(T_y)=m_y\). Este resultado é intuitivamente óbvio, devido a que cada vez que a cadeia retorna a \(y\) comporta-se, a partir de então, como faria uma cadeia que tivesse começando inicialmente em \(y\). Pode-se dar uma prova rigorosa deste resultado.

Para \(r\ge 1\), temos que \[ P(W_y^{r+1}=m_{r+1}|W_y^1=m_1,\cdots,W_y^r=m_r)=P_y(W_y^1=m_{r+1}) \] e em seguida, mostrado por indução que \[ P_y(W_y^1=m_1,\cdots,W_y^r=m_y)=P_y(W_y^1=m_1)\times \cdots \times P_y(W_y^1=m_r) \cdot \] O Teorema dos Grandes Números implica que \[ \lim_{n\to\infty} \dfrac{W_y^1+W_y^2+\cdots+W_y^k}{k}=m_y, \] com probabilidade um, isto é, que \[ \lim_{k\to\infty} \dfrac{T_y^k}{k}=m_y, \] com probabilidade um.

Seja \(N_n(y)=r\). Isto significa que no tempo \(n\) a cadeia fez exatamente \(r\) visitas a estado \(y\). Assim, a \(r\)-ésima visita a \(y\) ocorre no instante de tempo \(n\) ou antes e a \((r+1)\)-ésima visita a \(y\) ocorre após o instante \(n\), isto é, \[ T_y^{N_n(y)}\le n < T_y^{N_n(y)+1}, \] e então \[ \dfrac{T_y^{N_n(y)}}{N_n(y)}\le \dfrac{n}{N_n(y)}\le \dfrac{T_y^{N_n(y)+1}}{N_n(y)}, \] ou, pelo menos, estes resultados são válidos para \(n\) suficientemente grande de modo que \(N_n(y)\ge 1\).

Dado que \(N_n(y)\to\infty\) com probabilidade um quando \(n\to\infty\), estas desigualdades e \(\lim_{k\to\infty} T_y^k/k=m_y\) juntas implicam em \[ \lim_{n\to\infty} \dfrac{n}{N_n(y)}=m_y, \] com probabilidade um.

Seja \(y\) um estado recorrente como antes mas \(C_0\) tendo uma distribuição arbitrária. Isto significa que a cadeia pode nunca chegar a \(y\). Se ela alcança \(y\), no entanto, o argumento anterior é válido e, portanto \[ \dfrac{N_n(y)}{n}\to \dfrac{1_{\{T_y < \infty\}}}{m_y} \] com probabilidade um. Então a primeira afirmação do teorema é válida.

Por definição \(0\le N_n(y)\le n\), e então \[ 0\le \dfrac{N_n(y)}{n}\le 1 \cdot \] O Teorema da Convergência Dominada, permite-nos concluir que \[ \lim_{n\to\infty} \mbox{E}_x\left(\dfrac{N_n(y)}{n}\right)=\mbox{E}_x\left(\dfrac{\pmb{1}_{\{T_y < \infty\}}}{m_y}\right)= \dfrac{P_x(T_y < \infty)}{m_y}=\dfrac{\rho_{xy}}{m_y}, \] Isto completa a demonstração do Teorema 4.3.


Estas fórmulas são intuitivamente muito razoáveis. Uma vez que a cadeia atinge \(y\), retornará a \(y\) em média a cada \(m_y\) unidades de tempo. Assim, se \(T_y < \infty\) e \(n\) for grande, a proporção de vezes em que a cadeia estará no estado \(y\) deve ser de cerca \(1/m_y\) unidades, nas primeiras \(n\) unidades de tempo.

Observemos também que a expressão \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{\rho_{x,y}}{m_y}, \] para \(x\in S\), se obtém tomando esperança em \[ \lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{\pmb{1}_{\{T_y<\infty\}}}{m_y}, \] a qual acontece com probabilidade um.


Corolário 4.4.

Seja \(F\) um conjunto fechado irredutível de estados recorrentes. Então \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{1}{m_y}, \qquad x,y\in F \] e se \(P(C_0\in F)=1\), então com probabilidade um \[ \lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{1}{m_y}, \qquad y\in F\cdot \]


Demonstração.

Lembremos que se \(y\) é um estado recorrente, então \(\rho_{x,y}=1\) (Teorema 3.1) e que \(P(T_y < \infty)=1\).


Exemplo 4.7.

Seja \(\{C_n\}\) uma Cadeia de Markov com matriz de probabilidades de transição \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; 0 \;\, & \;\, 1 \;\, & \;\, 2 \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \\ 2 \end{matrix} & \begin{pmatrix} 0.90 & 0.01 & 0.09 \\ 0.01 & 0.90 & 0.09 \\ 0.01 & 0.09 & 0.90 \end{pmatrix}\cdot \end{matrix} \]

Observamos que \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 0 \qquad & \qquad 1 \qquad & \qquad 2 \end{matrix} \\ \displaystyle \lim_{n\to\infty} \mathcal{P}^n \, = \, \begin{matrix} 0 \\ 1 \\ 2 \end{matrix} & \begin{pmatrix} 0.0909090 & 0.4354067 & 0.4736842 \\ 0.0909090 & 0.4354067 & 0.4736842 \\ 0.0909090 & 0.4354067 & 0.4736842 \end{pmatrix}\cdot \end{matrix} \]

Isto faz dela uma cadeia regular, ou seja, alguma potência da matriz de transição não têm zeros e isso implica que nenhum estado é absorvente, também significa que a cadeia é ergódica e, portanto, todos os estados são recorrente.

Ainda temos que, segundo a primeira expressão, no Corolário 4.4 \[ \begin{array}{c} \displaystyle \lim_{n\to\infty} \dfrac{G_n(x,0)}{n}=\dfrac{1}{m_0}=0.1644622, \\[0.8em] \displaystyle \lim_{n\to\infty} \dfrac{G_n(x,1)}{n}=\dfrac{1}{m_1}=0.3820475, \\[0.8em] \displaystyle \lim_{n\to\infty} \dfrac{G_n(x,2)}{n}=\dfrac{1}{m_2}=0.4534903, \end{array} \] qualquer seja \(x\in\{0,1,2\}\).

Deste resultado concluímos que \(m_0=6.080426\), \(m_1=2.617475\) e \(m_2=2.205119\).

Figura 4.1: Convergência ao tempo de retorno médio.

A Figura acima mostra a velocidade de convergência ao tempo de retorno médio, percebemos que, com \(n\) relativamente pequeno nos aproximamos, com grande acuracidade, à probabilidade da cadeia ir a cada estado.


4.3 Recorrentes nulos e positivos


Estudamos aqui duas classes de estados recorrentes de interesse para a distribuição estacionária: os estados recorrentes nulos e os estados recorrentes positivos.


Definição 4.4: Estado recorrente nulo.

Um estado recorrente \(y\) é chamado de recorrente nulo se \(m_y=\infty\).


Do Teorema 4.3 podemos perceber que, se \(y\) for um estado recorrente nulo, então \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n} \, = \, \displaystyle \lim_{n\to\infty} \sum_{m=1}^n\dfrac{p_{x,y}^{(m)}}{n}=0, \qquad x\in S\cdot \]


Teorema 4.5.

Seja \(y\) um estado recorrente nulo, então \[ \lim_{n\to\infty} p_{x,y}^{(n)}=0, \qquad x\in S\cdot \]


Demonstração.

Consequência do Teorema 4.3 e do fato de \(m_y=\infty\).


Este é um resultado mais forte do que àquele \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\lim_{n\to\infty} \sum_{m=1}^n \dfrac{p_{x,y}^{(m)}}{n}=0, \qquad x\in S\cdot \] Não o vamos provar uma vez que não será necessário mais tarde e sua demonstração é bastante difícil.


Definição 4.5: Estado recorrente positivo.

Um estado recorrente \(y\) é chamado de recorrente positivo se \(m_y < \infty\).


Do Teorema 4.3 podemos perceber que, se \(y\) for um estado recorrente positivo, então \[ \lim_{n\to\infty} \dfrac{G_n(x,y)}{n} \, = \, \dfrac{1}{m_y}>0, \qquad x\in S\cdot \] Assim, limites anteriores não são válidos para estados recorrentes positivos.

Considere uma Cadeia de Markov começando no estado recorrente \(y\). Se segue do Teorema 4.3 que, se \(y\) for um estado recorrente nulo, então com probabilidade um, a proporção de tempo que a cadeia está no estado \(y\) durante as primeiras \(n\) unidades de tempo se aproxima de zero quando \(n\to\infty\). Por outro lado, sendo \(y\) um estado recorrente positivo, com probabilidade um, a proporção de tempo que a cadeia está em \(y\) durante as primeiras \(n\) unidades de tempo se aproxima de \(1/m_y\), um número positivo, quando \(n\to\infty\).


Teorema 4.6.

Seja \(x\) um estado recorrente positivo e suponha que \(x\) conduz a \(y\). Então, \(y\) é também um estado recorrente positivo.


Demonstração.

Segue do Teorema 3.1 que \(y\) conduz a \(x\) e, então, \(x\) e \(y\) se comunicam. Então, existem inteiros \(n_1\) e \(n_2\) tais que \[ p_{y,x}^{(n_1)}>0 \qquad \mbox{e} \qquad p_{x,y}^{(n_2)}>0\cdot \] Agora, \[ p^{(n_1+m+n_2)}_{y,y}\ge p^{(n_1)}_{y,x}p^{(m)}_{x,x}p^{(n_2)}_{x,y}, \] e, somando em \(m=1,2,,\cdots,n\) e dividindo por \(n\), concluímos que \[ \dfrac{G_{n_1+n+n_2}(y,y)}{n}-\dfrac{G_{n_1+n_2}(y,y)}{n}\ge p^{(n_1)}_{y,x}p^{(n_2)}_{x,y}\dfrac{G_n(x,x)}{n} \cdot \] Quando \(n\to\infty\), o termo à esquerda da desigualdade acima converge a \(1/m_y\) e o termo à direita converge a \[ \dfrac{p^{(n_1)}_{y,x}p^{(n_2)}_{x,y}}{m_x} \cdot \] Portanto \[ \dfrac{1}{m_y}\ge \dfrac{p^{(n_1)}_{y,x}p^{(n_2)}_{x,y}}{m_x}>0, \] e, por consequência, \(m_y<\infty\). Isto mostra que \(y\) é um estado recorrente positivo.


A partir deste teorema e do Teorema 3.1, vemos que, se \(F\) for um conjunto fechado irredutível, então cada estado em \(F\) é transiente, cada estado em \(F\) é recorrente nulo ou cada estado em \(F\) é recorrente positivo.


Definição 4.6: Cadeia recorrente nula e recorrente positiva.

Uma Cadeia de Markov será chamada de cadeia recorrente nula se todos os seus estados forem recorrentes nulos. Uma Cadeia de Markov será chamada de cadeia recorrente positiva se todos os seus estados forem recorrentes positivos.


Vemos, portanto, que uma Cadeia de Markov irredutível é, ou uma cadeia transiente, ou uma cadeia recorrente nula ou uma cadeia recorrente positiva.

Se \(F\) for um conjunto fechado finito de estados, então \(F\) tem, pelo menos, um estado recorrente positivo. Por causa de \[ \sum_{y\in F} p^{(m)}_{x,y}=1, \qquad x\in F, \] somando em \(m=1,\cdots,n\) e dividindo por \(n\) encontramos que \[ \sum_{y\in F} \dfrac{G_n(x,y)}{n}=1, \qquad x\in F\cdot \]

Caso \(F\) tiver finitos elementos e cada estado em \(F\) for transiente ou recorrente nulo, então vale \[ 1 \, = \, \displaystyle \lim_{n\to\infty} \sum_{y\in F} \dfrac{G_n(x,y)}{n} \, = \, \displaystyle \lim_{n\to\infty} \sum_{y\in F} \dfrac{G_n(x,y)}{n} \; = \; 0, % %\begin{array}{rcl} % 1 & = & \displaystyle \lim_{n\to\infty} \sum_{y\in C} \dfrac{G_n(x,y)}{n} \\[0.8em] % & = & \displaystyle \lim_{n\to\infty} \sum_{y\in C} \dfrac{G_n(x,y)}{n} \; = \; 0, %\end{array} \] uma contradição.


Teorema 4.7.

Seja \(F\) um conjunto fechado irredutível de estados. Então todo estado em \(F\) é recorrente positivo.


Demonstração.

Dado que \(F\) é um conjunto finito fechado, existe ao menos um estado recorrente positivo em \(F\). Dado que \(F\) é irredutível, todo estado em \(F\) é recorrente positivo, pelo Teorema 4.6.



Corolário 4.8.

Uma Cadeia de Markov ergódica com um número finito de estados é recorrente positiva.


Demonstração.

Segue imediatamente do Teorema 4.6 e do Teorema 4.7.

Corolário 4.9.

Uma Cadeia de Markov ergódica com um número finito de estados não tem estados recorrentes nulos.


Demonstração.

Se \(y\) é um estado recorrente, então, pelo Teorema 3.1 \(y\) está contido em um conjunto irredutível fechado \(F\) de estados recorrentes. Como \(F\) é necessariamente finito, se segue do Teorema 4.7, que todos os estados em \(F\), incluindo o próprio \(y\), são recorrentes positivos. Assim, cada estado recorrente é recorrente positivo e, portanto, não há estados recorrentes nulos.


Exemplo 4.8: Festival de música.

Imagine um estudante participando em um festival de música. Podemos considerar quatro possíveis locais onde o estudante possa estar, estes são: “Bar”, “Concerto” e “Danceteria”.

Estabelecemos que as probabilidades de mudança entre as locações seja como apresentadas na matriz de transição a seguir: \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{Bar} \\ \mbox{Concerto} \\ \mbox{Danceteria} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{Bar} & \mbox{Concerto} & \mbox{Danceteria} \\ 1/2 & 1/4 & 1/4 \\ 1/2 & 0 & 1/2 \\ 1 & 0 & 0 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

Não é difícil perceber que esta é uma cadeia ergódica logo, pelos Corolários 4.8 e 4.9 nesta cadeia todos os estados são recorrentes positivos. O cálculo de sua distribuição estacionária fornece como resultado \[ \pi=\left(\dfrac{8}{13},\dfrac{3}{13},\dfrac{2}{13}\right)\cdot \] Bastante inesperadamente, o estudante passa a maior parte do tempo no bar.


4.4 Existência e unicidade


Nesta seção vamos determinar quais cadeias têm distribuição estacionária e quando há uma única tal distribuição. Seja agora \(\pi\) a distribuição estacionária e \(m\) um número positivo inteiro. Então, sabemos que \[ \sum_{z\in S} \pi(z) p^{(m)}_{z,x}=\pi(x), \] qualquer seja o valor de \(m\). Somando em \(m=1,2,\cdots,n\) e dividindo por \(n\), concluímos que \[ \sum_{z\in S} \pi(z)\dfrac{G_n(z,x)}{n}=\pi(x), \qquad x\in S\cdot \]


Exemplo 4.9.

No caso do modelo de genes, Exemplo 1.9, temos que \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{GG} \\ \mbox{Gg} \\ \mbox{gg} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{GG} & \mbox{Gg} & \mbox{gg} \\ 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1/2 & 1/2 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

Aceitemos que a distribuição estacionária seja \(\pi=(0.25,0.50,0.25)\). Então, vamos mostrar que \[ \sum_{z\in S} \pi(z) p_{z,x} \, = \, \sum_{z\in S} \pi(z)\dfrac{G_1(z,x)}{1} \, = \, \pi(x), \qquad x\in S \] e, para isso, vamosutilizar os comandos a continuação.

estados = c("GG","Gg","gg")
Prob.T=matrix(c(1/2,1/2,0,1/4,1/2,1/4,0,1/2,1/2),
              nrow=3,ncol=3,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T, name="Modelo de genes")


Desta forma definimos a matriz de probabilidades de transição. Agora definimos o vetor \(\pi\), da distribuição estacionária.

Pi=c(0.25,0.5,0.25)


Fazemos as contas com as seguintes linhas de comando.

Pi%*%ProbT[]
##        GG  Gg   gg
## [1,] 0.25 0.5 0.25
Soma = function(M,n=10){
  mm=0;
  for(i in 1:n){mm=mm+(M^i)[]}
    mm}
Pi%*%(Soma(ProbT,1)/1)
##        GG  Gg   gg
## [1,] 0.25 0.5 0.25


A função Soma serve para calcular \(G_n(z,x)\) e como podemos perceber, os dois produtos fornecem o mesmo resultado.


Esta foi uma situação atípica, no sentido que com \(n,m=1\) conseguimos identificar a distribuição estacionária.


Teorema 4.10.

Seja \(\pi\) a distribuição estacionária de uma Cadeia de Markov com espaço de estados \(S\). Se \(x\) é um estado transiente ou recorrente nulo, temos que \(\pi(x)=0\).


Demonstração.

Se \(x\) é um estado transiente ou recorrente nulo, temos que \[ \lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=0, \qquad x\in S\cdot \] Segue então, das expressões anteriores e do Teorema da Convergência Dominada que \[ \pi(x)=\lim_{n\to\infty} \sum_{z\in S} \pi(z)\dfrac{G_n(z,x)}{n}=0, \] como desejado.


Decorre deste teorema que uma Cadeia de Markov que não tenha estados recorrentes positivos não tem distribuição estacionária.


Teorema 4.11: Existência da distribuição estacionária.

Uma Cadeia de Markov irredutível positiva tem distribuição estacionária única \(\pi\), dada por \[ \pi(x)=\dfrac{1}{m_x}, \qquad x\in S\cdot \]


Demonstração.

Segue do Teorema 4.3 e da suposição deste teorema que \[ \lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=\dfrac{1}{m_x}, \qquad z,x\in S\cdot \]

Suponha que \(\pi\) seja a distribuição estacionária. De expressões anteriores e do Teorema da Convergência Dominada, temos que \[ \pi(x) \, = \, \displaystyle \lim_{n\to\infty} \sum_{z\in S} \pi(z)\dfrac{G_n(z,y)}{n} \, = \, \displaystyle \dfrac{1}{m_x}\sum_{z\in S} \pi(z) = \dfrac{1}{m_x} \cdot % \begin{array}{rcl} % \pi(x) & = & \displaystyle \lim_{n\to\infty} \sum_{z\in\Es} \pi(z)\dfrac{G_n(z,y)}{n} \\ % & = & \displaystyle \dfrac{1}{m_x}\sum_{z\in\Es} \pi(z) = \dfrac{1}{m_x} \cdot % \end{array} \]

Então, se existe distribuição estacionária deve ser como apresentada no teorema. Para completar a demonstração devemos provar que esta função é, de fato, distribuição estacionária. É claramente de componentes não negativas, por isso precisamos apenas mostrar que \[ \sum_{x\in S} \dfrac{1}{m_x}=1 \] e que \[ \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}=\dfrac{1}{m_y}, \qquad y\in S\cdot \] Para este fim, observamos primeiro que \[ \sum_{x\in S} p^{(m)}_{z,x}=1, \qquad m\geq 1 \cdot \] Somando em \(m=1,\cdots,n\) e dividindo por \(n\), concluímos que \[ \sum_{x\in S} \dfrac{G_n(z,x)}{n}=1, \qquad z\in S\cdot \] Agora observemos que \[ \sum_{x\in S} p^{(m)}_{z,x}p_{x,y} \, = \, p^{(m+1)}_{z,y}\cdot \] Novamente, somando em \(m=1,\cdots,n\) e dividindo por \(n\), concluímos que \[ \sum_{x\in S} \dfrac{G_n(z,x)}{n}p_{x,y} \, = \, \dfrac{G_{n+1}(z,y)}{n}-\dfrac{p_{z,y}}{n}\cdot \]

Caso \(S\) seja finito, concluímos que \[ 1=\lim_{n\to\infty} \sum_{x\in S} \dfrac{G_n(z,x)}{n}=\sum_{x\in S} \dfrac{1}{m_x}, \] ou seja, concluímos que \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x}=1\) vale. De maneira similar concluímos que o resultado \[ \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}=\dfrac{1}{m_y}, \qquad y\in S, \] vale fazendo \(n\to\infty\) em \[ \displaystyle \sum_{x\in S} \dfrac{G_n(z,x)}{n}p_{x,y} \, = \, \dfrac{G_{n+1}(z,y)}{n}-\dfrac{p_{z,y}}{n}\cdot \] Isto completa a demonstração para o caso de \(S\) finito.

O argumento para completar a demonstração para o caso \(S\) seja infinito é mais complicado, uma vez que o Teorema da Convergência Dominada não se aplica e, portanto, não podemos trocar o limite com as somas que nem fizemos no caso finito. Seja agora \(S_1\subset S\) um subconjunto finito de \(S\). Da relação \(\displaystyle \sum_{x\in S} \dfrac{G_n(z,x)}{n}=1\), \(z\in S\), vemos que \[ \sum_{x\in S_1} \dfrac{G_n(z,x)}{n}\le 1, \qquad z\in S\cdot \] Devido ao fato de \(S_1\) ser finito, podemos fazer \(n\to\infty\) nesta desigualdade e concluir de \[ \displaystyle \lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=\dfrac{1}{m_x}, \] para \(z,x\in S\) que \[ \sum_{x\in S_1} \dfrac{1}{m_x}\le 1\cdot \] Pois, se a soma de \(1/m_x\) sobre $xS exceder 1, a soma sobre algum subconjunto finito de \(S\) também irá exceder 1.

Similarmente, concluímos que se \(S_1\) for um subconjunto finito de \(S\), então \[ \sum_{x\in S} \dfrac{G_n(z,x)}{n}p_{x,y}\le \dfrac{G_{n+1}(z,y)}{n}-\dfrac{p_{z,y}}{n}\cdot \] Tomando \(n\to\infty\) nesta desigualdade e utilizando o resultado \(\displaystyle \lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=\dfrac{1}{m_x}\), \(z,x\in S\), obtemos que \[ \sum_{x\in S_1} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}, \qquad y\in S\cdot \] Concluímos que, assim como na demonstração de \(\displaystyle \sum_{x\in S_1} \dfrac{G_n(z,x)}{n}\le 1\), \(z\in S\), que \[ \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}, \qquad y\in S\cdot \]

A seguir vamos provar que a igualdade vale na expressão acima. Segue de \(\displaystyle \sum_{x\in S_1} \dfrac{1}{m_x}\le 1\) que, somando em \(y\) na parte direita da expressão acima a soma é finita. Se a desigualdade estrita se mantém para algum \(y\), seguiria somando a expressão acima em \(y\), que \[ \displaystyle \sum_{y\in S} \dfrac{1}{m_y} \, \le \, \displaystyle \sum_y \left(\sum_x \dfrac{1}{m_x}p_{x,y} \right) \, = \, \displaystyle \sum_x \dfrac{1}{m_x}\left(\sum_y p_{x,y} \right) \quad = \quad \sum_x \dfrac{1}{m_x}, \] o qual é uma contradição. Isto prova que a igualdade em \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}\), \(y\in S\) vale.

Seja agora \[ c=\dfrac{1}{\displaystyle \sum_x \dfrac{1}{m_x}}\cdot \] Então, pelo resultado \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}\), \(y\in S\), \[ \pi(x)=\dfrac{c}{m_x}, \qquad x\in S, \] define uma distribuição estacionária. Então, pela primeira parte da demonstração deste teorema \[ \dfrac{c}{m_x}=\dfrac{1}{m_x}, \] e, portanto, \(c=1\). Isto prova que \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x}=1\) vale e completa a demonstração.

Corolário 4.12.

Uma Cadeia de Markov irredutível é recorrente positiva se, e somente se, ela tiver distribuição estacionária.


Demonstração.

Consequência imediata dos Teoremas 4.10 e 4.11.



Corolário 4.13.

Se uma Cadeia de Markov com um número finito de estados for irredutível, então tem distribuição estacionária única.


Demonstração.

É uma consequência do Corolário 4.9 e do Teorema 4.11.


Recordemos que \(N_n(x)\) denota o número de visitas ao estado \(x\) durante os instantes de tempo \(m=1,\cdots,n\).


Corolário 4.14.

Seja \(\{C_n\}_{n\ge 0}\) uma Cadeia de Markov irredutível recorrente positiva tendo \(\pi\) como distribuição estacionária. Então, com probabilidade um \[ \lim_{n\to\infty} \dfrac{N_x(x)}{n} \, = \, \pi(x), \qquad x\in S\cdot \]


Demonstração.

É uma consequência do Corolário 4.4 e do Teorema 4.11.


4.4.1 Cadeias irredutíveis


Seja \(\pi\) uma função de probabilidades em \(S\), isto é, seja \(\pi(x)\), \(x\in S\) uma função constituída de números não negativos somando um e seja \(F\) um subconjunto de \(S\).


Definição 4.7.

Dizemos que \(\pi\), uma função de probabilidade, está concentrada em \(F\subset S\) se \[ \pi(x)=0 \qquad \forall x\notin F\cdot \]



Teorema 4.15.

Seja \(F\) um conjunto fechado irredutível de estados recorrentes positivos. Então a Cadeia de Markov têm distribuição estacionária única concentrada em \(F\). Isto significa que \[ \pi(x)=\left\{ \begin{array}{cc} \dfrac{1}{m_x}, & x\in F \\[0.8em] 0, & \mbox{caso contrário} \end{array}\right. \]


Demonstração.

Essencialmente o mesmo argumento utilizado na demonstração do Teorema 3.7.


Suponhamos que \(F_0\) e \(F_1\) sejam conjuntos de estados recorrentes positivos, fechados, distintos e irredutíveis. Segue do Teorema 4.1 que a Cadeia de Markov têm distribuição estacionária \(\pi_0\) concentrada em \(F_0\), uma outra distribuição estacionária \(\pi_1\) concentrada em \(F_1\).

Ademais, as distribuições \(\pi_\alpha\), definidas para \(0\le\alpha\le 1\) como \[ \pi_\alpha(x)=(1-\alpha)\pi_0(x)+\alpha\pi_1(x), \qquad x\in S, \] são distribuições estacionárias distintas (Veja o Exercício 12).


Teorema 4.16: Unicidade da distribuição estacionária.

Seja \(S_P\) o conjunto dos estados recorrentes positivos em uma Cadeia de Markov.

  1. Se \(S_P\) for vazio, a cadeia no possui distribuição estacionária.

  2. Se \(S_P\) for não vazio irredutível, a cadeia têm distribuição estacionária única.

  3. Se \(S_P\) for não vazio porém não irredut&ível, a cadeia têm um número infinito de distribuições estacionárias distintas.


Demonstração.

Obtém-se combinado os resultados e consequências dos Teoremas 3.6, 3.7 e 4.1.


Consideremos agora uma Cadeia de Markov com um número finito de estados. Então, todo estado recorrente é recorrente positivo. Existem duas possibilidades: quer o conjunto \(S_R\) de estados recorrentes ser irredutível e há uma distribuição estacionária única ou \(S_R\) pode ser decomposto em dois ou mais subconjuntos irredutíveis fechados e existem infinitas distribuições estacionárias distintas.

Esta última possibilidade vale para uma Cadeia de Markov com espaço de estados \(S=\{0,1,\cdots,d\}\) na qual \(d>0\), sendo que os estados 0 e \(d\) são ambos absorventes.


Exemplo 4.10: Continuação do Exemplo 3.2.

Queremos encontrar a distribuição estacionária concentrada em cada um dos conjuntos fechados irredutíveis.

No Exemplo 3.2 vimos que o conjunto de estados recorrentes desta cadeia pode ser decomposto no estado absorvente 0 e no conjunto de estados irredutíveis fechado \(\{3,4,5\}\). Logicamente, a distribuição estacionária única concentrada em \(\{0\}\) é \(\pi_0=(1,0,0,0,0,0)\).

Para encontrarmos a distribuição estacionária única concentrada em \(\{3,4,5\}\), devemos identificar números não negativos \(\pi(3)\), \(\pi(4)\) e \(\pi(5)\) tais que somem um e satisfaçam as equações \[ \begin{array}{lcl} \dfrac{\pi(3)}{6}+\dfrac{\pi(4)}{2}+\dfrac{\pi(5)}{4} & = & \pi(3) \\[0.8em] \dfrac{\pi(3)}{3} & = & \pi(4) \\[0.8em] \dfrac{\pi(3)}{2}+\dfrac{\pi(4)}{2}+\dfrac{3\pi(5)}{4} & = & \pi(5)\cdot \end{array} \]

Das primeiras duas destas equações encontramos que \(\pi(4)=\pi(3)/3\) e \(\pi(5)=8\pi(3)/3\). Assim \[ \pi(3)\left(1+1/3+8/3\right)=1, \] do qual concluímos que \(\pi(3)=1/4\), \(\pi(4)=1/12\) e \(\pi(5)=2/3\). Por consequência \[ \pi_1=\left(0,0,0,1/4,1/12,2/3\right) \] é a distribuição estacionária concentrada em \(\{3,4,5\}\).


4.5 Convergência


Temos visto desde o início deste capítulo que se \(\{C_n\}\) for uma Cadeia de Markov recorrente positiva irredutível, sendo \(\pi\) sua distribuição estacionária, então \[ \lim_{n\to\infty} \dfrac{1}{n}\sum_{m=1}^n p^{(m)}_{x,y}=\lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\pi(y), \qquad x,y\in S \cdot \]

Aqui vamos ver quando o resultado mais forte \[ \lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y), \qquad x,y\in S, \] é válido e o que acontece se deixa de cumprir-se.

Lembremos que um número inteiro positivo \(d\) é dito ser um divisor do inteiro positivo \(n\) se \(n/d\) for um número inteiro.


Definição 4.8: Máximo divisor comum.

Seja \(\mbox{I}\) um conjunto de inteiros positivos não vazio. Definimos o máximo divisor comum de \(\mbox{I}\), denotado por m.d.c. \(\mbox{I}\), o maior inteiro \(d\) tal que \(d\) é um divisor inteiro positivo de cada elemento de \(\mbox{I}\).


Segue-se imediatamente que \[ 1\le \mbox{m.d.c.} \, \mbox{I} \le \mbox{min}\{n: n\in \mbox{I}\} \cdot \] Em particular, se \(1\in \mbox{I}\), em seguida temos que m.d.c. de \(\mbox{I}=1\) um outro detalhe interessante é que o mínimo divisor comum de um conjunto de inteiros positivos pares é 2.


Definição 4.9: Período de um estado.

Seja \(x\) um estado de uma Cadeia de Markov \(\{C_n \}_{n\ge 0}\) tal que \(p^{(n)}_{x,x}>0\) para algum \(n\ge 1\), isto é, tal que \(\rho_{x}=P_x(T_x < \infty)>0\). Definimos o período do estado \(x\), denotado por \(d_x\), como \[ d_x=\mbox{m.d.c.}\{n\ge 1: \, p^{(n)}_{x,x}>0\} \cdot \]


Desta definição vemos que \[ 1\le d_x \le \min\{n\ge 1: \, p^{(n)}_{x,x}>0\} \cdot \] Também, se \(p_{x,x}>0\), então \(d_x=1\).


Exemplo 4.11

No Exemplo 3.2 apresentamos uma Cadeia de Markov com matriz de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1/4 & 1/2 & 1/4 & 0 & 0 & 0 \\ 0 & 1/5 & 2/5 & 1/5 & 0 & 1/5 \\ 0 & 0 & 0 & 1/6 & 1/3 & 1/2 \\ 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1/4 & 0 & 3/4 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \] Queremos identificar o período de cada um dos estados desta cadeia.

Observamos diretamente que \(d_x=1\) para \(x=0,1,2,3,5\) e somente não é possível identificar diretamente o período do estado 4. O trabalho agora é procurar a menor potência de \(\mathcal{P}\) na qual a probabilidade \(p^{(n)}_{4,4}\) seja positiva. Percebemos rapidamente que \(p^{(2)}_{4,4}=1/6\), também obtemos que \(p^{(n)}_{4,4}>0\) para \(n\geq 2\). Logo \(d_4=1\).



Teorema 4.17.

Seja \(\{C_n \}_{n\ge 0}\) uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{P} =\big(p_{x,y}\big)\). Se \(x\) e \(y\) forem dois estados na mesma classe de comunicação da cadeia possivelmente não irredutível, então \(d_x=d_y\).


Demonstração.

Pelo fato dos estados se comunicarem, devem existir \(n_1\) e \(n_2\), números inteiros tais que \[ p^{(n_1)}_{x,y}>0 \qquad \mbox{e} \qquad p^{(n_2)}_{y,x}>0\cdot \] Então temos que \[ p^{(n_1+n_2)}_{x,x}\ge p^{(n_1)}_{x,y}p^{(n_2)}_{y,x}>0, \] e por isso \(d_x\) é o divisor de \(n_1+n_2\). Se \(p^{(n)}_{y,y}>0\), então \[ p^{(n_1+n_2)}_{x,x}\ge p^{(n_1)}_{x,y}p^{(n)}_{y,y}p^{(n_2)}_{y,x}>0, \] de modo que \(d_x\) é um divisor de \(n_1+n+n_2\). Desde que \(d_x\) é divisor de \(n_1+n_2\), ele deve ser um divisor de \(n\). Assim \(d_x\) é um divisor de todos os números no conjunto \(\{n>1:\, p^{(n)}_{y,y}>0\}\). Devido a que \(d_y\) é o maior de tais divisores, concluímos que \(d_x\le d_y\). Similarmente \(d_y\le d_x\) e então \(d_x=d_y\).


Nós mostramos, em outras palavras, que os estados de uma Cadeia de Markov irredutível têm período comum \(d\).


Definição 4.10: Cadeia periódica.

Dizemos que uma Cadeia de Markov irredutível é periódica, com período \(d\), se \(d>1\) e é aperiódica se \(d=1\).


Uma condição suficiente simples para uma Cadeia de Markov irredutível ser aperiódica é que \(p_{x,x}>0\) para algum \(x\in S\).

A teorema mostra que os estados de uma cadeia de Markov irredutível têm todos o mesmo período \(d\), que é chamado de período da Cadeia de Markov. A cadeia é dita aperiódica se seu período for \(d = 1\). Para uma cadeia de Markov irredutível ser aperiódica, é suficiente (mas não necessário) que \(p_{ii}> 0\) para algum \(i\). Por exemplo, o gráfico de transição da figura 3 define uma Cadeia de Markov irredutível e aperiódica.


Teorema 4.18: Distribuição estacionária de uma cadeia recorrente positiva.

Seja \(\{C_n \}_{n\ge 0}\) uma Cadeia de Markov recorrente positiva irredutível com distribuição estacionária \(\pi\). Se a cadeia é aperiódica, então \[ \lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y), \qquad x,y\in S\cdot \] Se a cadeia é periódica com período \(d\), então para cada par de estados \(x,y\in S\) existe um inteiro \(r\), \(0\le < d\) tal que \(p^{(n)}_{x,y}=0\) a não ser que \(n=md+r\) para algum inteiro não negativo \(m\) e \[ \lim_{m\to\infty} p^{(md+r)}_{x,y}=d\pi(y), \qquad x,y\in S\cdot \]


Demonstração.

Provemos primeiro o caso aperiódico. Considere uma Cadeia de Markov aperiódica, irredutível e recorrente positiva com matriz de probabilidades de transição \(\mathcal{P} = \big(p_{x,y}\big)\), espaço de estados \(S\) e distribuição estacionária \(\pi\).

Seja \(a\in S\) e seja \(\mbox{I}\) o conjunto dos inteiros positivos definidos por \[ \mbox{I}=\{n>0: \, p^{(n)}_{a,a}>0\} \cdot \] Então

  1. O máximo divisor comum de \(\mbox{I}\) é 1 e,

  2. Se \(m,n\in\mbox{I}\), então \(m+n\in\mbox{I}\).

O resultado em (b) obtém-se da desigualdade \[ p^{(m+n)}_{a,a}\geq p^{(m)}_{a,a}p^{(n)}_{a,a}\cdot \] As propriedades (a) e (b) implicam na existência de um número inteiro positivo \(n_1\) tal que \(n\in\mbox{I}\), \(\forall n\geq n_1\). Utilizando este resultado concluímos que \(p^{(n)}_{a,a}>0\) para todo \(n\geq n_1\).

Sejam \(x,y\in S\). Devido à cadeia ser irredutível, existem inteiros positivos \(n_2\) e \(n_3\) tais que \[ p^{(n_2)}_{x,a}>0 \qquad \mbox{e} \qquad p^{(n_3)}_{a,y}>0\cdot \] Então, para \(n\geq n_1\) temos que \[ p^{(n_2+n+n_3)}_{x,y}\geq p^{(n_2)}_{x,a}p^{(n)}_{a,a}p^{(n_3)}_{a,y}>0\cdot \] Provamos que, para qualquer par de estados \(x,y\in S\), existe um inteiro positivo \(n_0\) tal que \[ p^{(n)}_{x,y}>0 \qquad n\geq n_0\cdot \]

Seja agora \[ S^2=\{(x,y): \, x,y\in S\}\cdot \] Observemos que \(S^2\) é um conjunto formado por pares ordenados de elementos de \(S\). Consideremos a Cadeia de Markov \((C_n,D_n)\) com espaço de estados \(S^2\) e função de probabilidades de transição \[ p_{2_{(x_0,y_0),(x,y)}} \, = \, p_{x_0,x}p_{y_0,y}\cdot \] Segue que \(\{C_n\}_{n\geq 0}\) e \(\{D_n\}_{n\geq 0}\) são, cada uma, Cadeias de Markov tendo função de probabilidades de transição \(p\) e que as transições sucessivas da cadeia \(C_n\) e da cadeia \(D_n\) acontecem independentemente uma da outra.

Provaremos agora propriedades da Cadeia de Markov \((C_n,D_n)\). Em particular, provaremos que esta cadeia é aperiódica, irredutível e recorrente positiva. Posteriormente a utilizaremos para verificar as conclusões do teorema.

Sejam \((x_0,y_0)\in S^2\) e \((x,y)\in S^2\). Pelo resultado, \(p^{(n)}_{x,y}>0\), \(n\geq n_0\) e exite um \(n_0>0\) tal que \[ p^{(n)}_{x_0,x}>0 \qquad \mbox{e} \qquad p^{(n)}_{y_0,y}>0, \quad n\geq n_0\cdot \] Então \[ p_{2_{(x_0,y_0),(x,y)}} \, = \, p^{(n)}_{x_0,x}p^{(n)}_{y_0,y}, \quad n\geq n_0\cdot \] Concluímos assim que a cadeia é irredutível e aperiódica.

Não é difícil perceber que a distribuição estacionária \(\pi_2\) em \(S^2\) é definida como \(\pi_2(x_0,y_0)=\pi(x_0)\pi(y_0)\). Para \[ \begin{array}{rcl} \displaystyle \sum_{(x_0,y_0)\in S^2} \pi_2(x_0,y_0)p_{2_{(x_0,y_0),(x,y)}} & = & \displaystyle \sum_{x_0\in S} \sum_{y_0\in S} \pi(x_0)\pi(y_0)p_{x_0,x}p_{y_0,y} \\[0.4em] & = & \displaystyle \left(\sum_{x_0\in S} \pi(x_0)p_{x_0,x} \right)\left(\sum_{y_0\in S} \pi(y_0)p_{y_0,y} \right) \\[0.4em] & = & \pi(x)\pi(y) \, = \, \pi_2(x,y)\cdot \end{array} \] Então, a cadeia em \(S^2\) é recorrente positiva, em particular, é recorrente.

Seja \[ T=\min\{n>0: \, C_n=D_n\}\cdot \] Escolhemos \(a\in S\). Dado que \((C_n,D_n)\) é recorrente, \[ T_{(a,a)}=\min\{n>0: \, (C_n,D_n)=(a,a)\}, \] é finito com probabilidade 1. Logicamente \(T\leq T_{(a,a)}\) e, portanto, \(T\) é finito com probabilidade 1.

Para qualquer \(n\geq 1\), independentemente da distribuição de \((C_0,D_0)\), \[ P(C_n=y,T\leq n)=P(D_n=y, T\leq n), \qquad y\in S\cdot \] Este resultado é razoável dado que as duas cadeias são indistinguíveis para \(n\geq T\). Mais especificamente, seja \(1\leq m\leq n\). Para \(z\in S\) \[ {P(C_n=y|T=m,C_m=D_m=z)=} \, = \, P(D_n=y|T=m,C_m=D_m=z), \] dado que ambas probabilidades condicionais são iguais a \(p^{(n-m)}_{z,y}\). Agora, o evento \(\{T\leq n\}\) pode ser escrito como \[ \{T\leq n\}=\bigcup_{1\leq m\leq n} \{T=m, C_m=D_m=z\}, \qquad z\in S, \] sendo os eventos \(\{T=m, C_m=D_m=z\}\) disjuntos. Segue que \[ P(C_n=y|T\leq n)=P(D_n=y|T\leq n) \] e, então, o resultado \(P(C_n=y,T\leq n)=P(D_n=y, T\leq n)\), \(y\in S\) é válido. Esta mesma igualdade implica que \[ \begin{array}{rcl} P(C_n=y) & = & P(C_n=y,T\leq n)+P(C_n=y,T>n) \\[0.4em] & = & P(D_n=y,T\leq n)+P(C_n=y,T>n) \\[0.4em] & \leq & P(D_n=y)+P(T>n) \end{array} \] e, de maneira similar, implica que \[ P(D_n=y)\leq P(C_n=y)+P(T>n)\cdot \] Portanto, para \(n>1\) \[ \big|P(C_n=y)-P(D_n=y)\big|\leq P(T>n), \qquad y\in S\cdot \] Dado que \(T\) é finito com probabilidade um, \[ \lim_{n\to\infty} P(T>n)=0\cdot \] Concluímos que \[ \lim_{n\to\infty} \big(P(C_n=y)-P(D_n=y)\big)=0, \qquad y\in S\cdot \] Utilizando o resultado acima podemos completar a demonstração. Escolhemos \(x\in S\) e a distribuição inicial de \((C_n,D_n)\) de maneira que \(P(C_0=x)=1\) e \[ P(D_0=y_0)=\pi(y_0), \qquad y_0\in S\cdot \] Dado que \(\{C_n\}_{n\geq 0}\) e \(\{D_n\}_{n\geq 0}\) ambas são Cadeias de Markov com matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\), temos que \[ P(C_n=y)=p^{(n)}_{x,y}, \qquad y\in S \] e \[ P(D_n=y)=\pi(y), \qquad y\in S \] Por conseguinte, temos que \[ \lim_{n\to\infty} \big(p^{(n)}_{x,y}-\pi(y)\big) \, = \, \lim_{n\to\infty} \big(P(C_n=y)-P(D_n=y)\big)=0 \] e, portanto, a conclusão do Teorema 4.18 no caso aperiódico.

Vejamos agora o caso periódico. Seja \(F\) um conjunto fechado de estados irredutíveis recorrentes positivos tal que cada estado em \(F\) tenha período 1 e seja \(\pi\) a distribuição estacionária única concentrada em \(F\). Nestas condições concluímos que \[ \lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y)=\dfrac{1}{m_y}, \qquad x,y\in F\cdot \] Em particular, se \(y\) for um estado recorrente positivo com período 1 então, sendo \(F\) o conjunto irredutível fechado que contém \(y\), vemos que \[ \lim_{n\to\infty} p^{(n)}_{y,y}=\dfrac{1}{m_y}\cdot \] Seja \(\{C_n\}_{n\geq 0}\) uma Cadeia de Markov irredutível recorrente positiva com período \(d>1\). Seja agora \(D_m=C_{md}\), \(m\geq 0\). Então, \(\{D_m\}_{m\geq 0}\) é uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{Q}=\mathcal{P}^d\). Se \(y\in S\), então \[ \begin{array}{rcl} m.d.c. \, \{m: \, q^{(m)}_{y,y}>0\} & = & m.d.c \, \{m: \, p^{(md)}_{y,y}>0\} \\[0.4em] & = & \dfrac{1}{d} \, m.d.c.\, \{n: \, p^{(n)}_{y,y}>0\} \\[0.4em] & = & 1\cdot \end{array} \] Assim, todos os estados têm período 1 no que diz respeito à cadeia \(D_m\).

Consideremos agora a cadeia \(C_n\) e, portanto, também a cadeia \(D_m\) começar em \(y\). Uma vez que a cadeia \(C_n\) retorna pela primeira vez a \(y\), em algum múltiplo de \(d\), segue-se que o tempo de retorno esperado a \(y\) para a cadeia \(D_m\) é \(m_y/d\), onde \(m_y\) é o tempo de retorno esperado a \(y\) para a cadeia \(C_n\). Em particular, \(y\) é um estado recorrente positivo para uma Cadeia de Markov com matriz de probabilidades de transição \(\mathcal{Q}\).

Ao aplicar que \(\lim_{n\to\infty} p^{(n)}_{y,y}=1/m_y\) para esta matriz de probabilidades de transição, concluímos que \[ \lim_{m\to\infty} q^{(m)}_{y,y}=\dfrac{d}{m_y}=d\pi(y), \] e, portanto, que \[ \lim_{m\to\infty} p^{(md)}_{y,y}=d\pi(y), \qquad y\in S\cdot \] Sejam agora \(x\) e \(y\) um par de estados em \(S\) e seja \[ r_1=\min\{n: \, p^{(n)}_{x,y}>0\}\cdot \] Então, em particular, \(p^{(r_1)}_{x,y}>0\). Demonstraremos agora que \(p^{(n)}_{x,y}>0\) somente se \(n-r_1\) for um inteiro múltiplo de \(d\).

Escolhemos \(n_1\) de forma que \(p^{(n_1)}_{y,x}>0\). Então \[ p^{(r_1+n_1)}_{y,y}\geq p^{(n_1)}_{y,x}p^{(r_1)}_{x,y}>0, \] e, daqui, \(r_1+n_1\) é um inteiro múltiplo de \(d\). Se \(p^{(n)}_{x,y}>0\), então pelo mesmo argumento \(n+n_1\) é um inteiro múltiplo de \(d\) e, por conseguinte, \(n-r_1\) também o é. Assim, \(n=kd+r_1\) para algum inteiro não negativo \(k\).

Existe um número inteiro não negativo \(m_1\) de maneira que \(r_1=m_1d+r\), onde \(0\leq r < d\). Concluímos que \[ p^{(n)}_{x,y}=0 \; \mbox{a menos que} \; n=md+r, \] para algum inteiro não negativo \(m\). Segue então, da expressão acima e do Teorema 2.5, que \[ p^{(md+r)}_{x,y} \, = \, \sum_{k=0}^m P_x(T_y=kd+r)p^{(m-k)d}_{y,y}\cdot \] Seja \[ a_m(k)=\left\lbrace \begin{array}{lc} p^{(m-k)d}_{y,y}, & \quad 0\leq k\leq m \\[0.4em] 0, & \quad k>m\end{array}\right.\cdot \] Então, para cada \(k\) fixo \[ \lim_{m\to\infty} a_m(k)=d\pi(y)\cdot \] Aplicando o Teorema da Convergência Dominada, concluímos que \[ \begin{array}{rcl} \displaystyle \lim_{m\to\infty} p^{(md+r)}_{x,y} & = & \displaystyle d\pi(y)\sum_{k=0}^\infty P_x(T_y=kd+r) \\[0.8em] & = & d\pi(y)P_x(T_y < \infty) \\[0.8em] & = & d\pi(y), \end{array} \] e, portanto, \(\displaystyle \lim_{m\to\infty} p^{(md+r)}_{x,y}=d\pi(y)\), \(x,y\in S\). Isto completa a demonstração do teorema.


Exemplo 4.12.

No exemplo de modelo de genes (Exemplo 1.9) temos uma situação de cadeia periódica, como pode ser apreciado olhando a matriz de probabilidades de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{GG} \\ \mbox{Gg} \\ \mbox{gg} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{GG} & \mbox{Gg} & \mbox{gg} \\ 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1/2 & 1/2 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

Pode ser observado também que esta é uma cadeia regular, devido a que \[ \begin{matrix} & \\ \mathcal{P}^2 = \begin{matrix} \mbox{GG} \\ \mbox{Gg} \\ \mbox{gg} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{GG} & \mbox{Gg} & \mbox{gg} \\ 0.375 & 0.500 & 0.125 \\ 0.250 & 0.500 & 0.250 \\ 0.125 & 0.500 & 0.375 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \] do qual deduzimos que o período desta cadeia é \(d=2\).

Não é difícil obter que \[ \begin{matrix} & \\ \displaystyle \lim_{n\to\infty} \mathcal{P}^{(n)} = \begin{matrix} \mbox{GG} \\ \mbox{Gg} \\ \mbox{gg} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{GG} & \mbox{Gg} & \mbox{gg} \\ 0.250 & 0.500 & 0.250 \\ 0.250 & 0.500 & 0.250 \\ 0.250 & 0.500 & 0.250 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]


Exemplo 4.13.

Seja \(S_n\) a soma dos resultados que se obtém ao lançar um dado balanceado \(n\) vezes. Queremos encontrar \[ \lim_{n\to\infty} P(\{S_n \, \mbox{ser divisível por 7}\}) \cdot \]

Definamos o processo estocástico \(C_n=\{S_n \mod 7\}\), ou seja, \(S_n\) divisão módulo 7, de espaço de estados \(S=\{0,1,\cdots,6\}\).

Não é difícil perceber que \(\{C_n \}_{n\ge 0}\) é uma Cadeia de Markov com matriz de probabilidades de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 \\ 1/6 & 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 \\ 1/6 & 1/6 & 0 & 1/6 & 1/6 & 1/6 & 1/6 \\ 1/6 & 1/6 & 1/6 & 0 & 1/6 & 1/6 & 1/6 \\ 1/6 & 1/6 & 1/6 & 1/6 & 0 & 1/6 & 1/6 \\ 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 & 1/6 \\ 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right )\cdot \end{matrix} \]

O evento \(\{S_n \, \mbox{ser divisível por 7}\}\) é idêntico ao evento \((C_n=0)\). Desta forma a probabilidade de que \(S_n\) seja divisível por 7, num longo período de tempo, é o tempo de estadia da cadeia a longo prazo no estado 0. Resolvemos o problema encontrando a distribuição limite de \(\mathcal{P}\).

Esta é uma matriz regular e periódica, então, a distribuição estacionária é uniforme. Portanto, \[ \lim_{n\to\infty} P(C_n=0)=\dfrac{1}{7}\cdot \]


Uma observação importante. A distribuição estacionária não significa que a cadeia não está se movendo. É importante notar que \(\sum_{x\in S} \pi(x) p^{(n)}_{x,y}\) fornece as probabilidades da cadeia estar em cada um dos seus estados após \(n\) passos, calculadas antes de ser observado o estado inicial da cadeia ou antes mesmo de quaisquer transições da cadeia serem observadas. Estes são diferentes das probabilidades de estar em vários estados, depois de observar o estado inicial ou depois de observar qualquer das transições intermediárias.

Além disso, uma distribuição estacionária não implica que a Cadeia de Markov vai ficar colocada. Se uma Cadeia de Markov começa em uma distribuição estacionária, em seguida, para cada estado \(x\) a probabilidade da cadeia estar no estado \(x\) após \(n\) passos é a mesma do que a probabilidade de ela estar no estado \(x\) no início. Mas a Cadeia de Markov ainda pode se mover de um estado para o próximo em cada transição. O único caso em que uma Cadeia de Markov vai ficar parada é depois de atingir um estado absorvente. A distribuição que se concentra exclusivamente em estados absorventes será necessariamente estacionária; porque a Cadeia de Markov nunca vai se mover se ela começar de tal distribuição. Em tais casos, toda a incerteza rodeia o estado inicial, que será também o estado depois de cada passagem.

4.6 Métodos automáticos


O título desta seção pode confundir, por isso, vamos esclarecer: todos as formas de encontrar a distribuição estacionária vistos até o momento valem e são úteis. O objetivo agora é apresentar uma outra forma para encontrar a distribuição estacionária, automática e mais suscetível à; programação.

De maneira matricial, podemos escrever a equação que define a distribuição estacionária como \[ \pi\mathcal{P} =\pi, \] onde \(\mathcal{P}\) é a matriz de probabilidades de transição de uma Cadeia de Markov com distribuição estacionária \(\pi\). A matriz \(\mathcal{P}\) tem sempre \(\lambda=1\) como um autovalor e \(e^\top =(1,1,\cdots,1)\) como um autovetor direito, devido a que, \(1e = \mathcal{P} e\). Isso decorre do fato de que todos os elementos de cada linha de \(\mathcal{P}\) somam um.

Por outro lado, a distribuição estacionária \(\pi\) é um autovetor pela esquerda para o autovalor \(\lambda=1\), isto devido a que, \(1\pi = \pi\mathcal{P}\). Foi mostradoi por Gallager (1996) que se \(p\) corresponde a uma Cadeia de Markov irredutível aperiódica, então \(\lambda=1\) é o maior autovalor e que todos os outros autovalores são menores do que 1.

Seja agora \(\mathcal{P}\) a matriz de transição de uma cadeia irredutível aperiódica. Procedendo a encontrar \(\mathcal{P}^n\) nestas situações, primeiro encontramos os autovalores \(1=\lambda_1> |\lambda_2|>\cdots >|\lambda_K|\) e os autovetores direitos \(e_1,e_2,\cdots,e_K\).

Definindo \(E\) como a matriz de autovetores nas colunas, temos que \[ \mathcal{P}=E\Lambda^n E^{-1}=E\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & \lambda_2^n & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & \lambda_K^n \end{pmatrix}E^{-1}\cdot \]

Note, como todos, a menos o elemento \(\Lambda_{1,1}\) da matriz diagonal de autovalores, tende a zero conforme \(n\) aumenta. Observe também que a primeira coluna da matriz \(E\) é um vetor todo de 1. Isto implica que a primeira linha de \(E^{-1}\) contém a distribuição estacionária \(\pi\). Na prática, é mais simples e mais conveniente encontrar \(\mathcal{P}^n\).

A equação \(\pi\mathcal{P} =\pi\) pode ser rescrita como \[ \pi(\mathcal{P}-\mbox{I}) \, = \, \pmb{0}, \] em que \(\mbox{I}\) é a matriz identidade, com mesma dimensão do que \(\mathcal{P}\), ou seja, com dimensão o número de estados em \(S\) e \(\pmb{0}\) é um vector de zeros.

O método automático no comando steadyStates no pacote de funções markovchain resolve o sistema anterior procurando o autovetor da matriz \(\mathcal{P}^\top\) associado ao autovetor 1 e normalizando-o para que some um.

Infelizmente, este sistema de equações tem muitas soluções, mesmo que haja uma distribuição estacionária. A razão disto é que, quando \(\pi\) resolve o sistema, o mesmo acontece com \(c\pi\) para todos os reais \(c\), incluindo \(c=0\). Mesmo que o sistema tenha \(k\) equações para \(k\) variáveis, existe pelo menos uma equação redundante. No entanto, existe também uma equação faltante. Precisamos exigir que a solução, o vector \(\pi\), tenha coordenadas que somem 1. Nós podemos corrigir esses dois problemas, substituindo uma das equações no sistema original pela equação que diz que as coordenadas de \(\pi\) somem 1.

Para ser mais específico, definamos a matriz \(G\) como sendo \(\mathcal{P}-\mbox{I}\) com a sua última coluna substituída por uma coluna de uns. Em seguida, resolvemos a equação \[ \pi G=(0,0,\cdots,1)\cdot \]

Se a Cadeia de Markov for irredutível, existe distribuição estacionária única, a qual vamos encontrá-la resolvendo a equação anterior. Neste caso, a matriz \(G\) terá uma inversa \(G^{-1}\) que satisfaz \[ G^{-1}G=GG^{-1}=\mbox{I}\cdot \]

A solução de \(\pi G=(0,0,\cdots,1)\) será então \[ \pi=(0,0,\cdots,1)G^{-1}, \] que é facilmente visto ser a linha inferior da matriz \(G^{-1}\). Vejamos estes métodos em exemplos.


Exemplo 4.14: Um modelo de mobilidade de classe.

Um problema de interesse para sociólogos é determinar a proporção da sociedade que tem uma ocupação de classe baixa, média ou classe alta e a influência disso nas gerações futuras. Um modelo matemático possível seria supor que as transições entre classes sociais nas sucessivas gerações de uma família podem ser consideradas como transições de uma Cadeia de Markov. Ou seja, assumimos que a futura ocupação de uma criança depende apenas da ocupação de seu pai ou mãe.

Vamos supor que tal modelo seja apropriado e que a matriz de probabilidades de transição seja dada por \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{Baixa} \\ \mbox{Média} \\ \mbox{Alta} \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{Baixa} & \mbox{Média} & \mbox{Alta} \\ 0.45 & 0.48 & 0.07 \\ 0.05 & 0.70 & 0.25 \\ 0.01 & 0.50 & 0.49 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right )\cdot \end{matrix} \]

Ou seja, por exemplo, vamos supor que o filho de um trabalhador de classe média vai atingir a classe de baixa renda, média ou alta renda com probabilidades respectivas de 0.05, 0.70 e 0.25.

A distribuição estacionária nesta situação é \(\pi=(0.07,0.62,0.31)\). Em outras palavras, uma sociedade na qual a mobilidade social entre as classes pode ser descrita por uma Cadeia de Markov com matriz de probabilidade de transição dada acima tem, no longo prazo, 7% da sua população na classe baixa de postos de trabalho, 62% da sua população em empregos de classe média e 31% em empregos de classe alta.

library(markovchain)
estados=c("Baixa","Média","Alta")
Prob.T=matrix(c(0.45,0.48,0.07,
                0.05,0.70,0.25,
                0.01,0.50,0.49), 
              nrow=3, ncol=3, byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T,
              name="Mobilidade de Classe Social")


Queremos encontrar a distribuição estacionária por métodos automáticos. Apresentamos a seguir como encontrar o vetor \(\pi\) das três formas descritas de encontrar a distribuição estacionária.

steadyStates(ProbT)
##           Baixa     Média      Alta
## [1,] 0.06238859 0.6234403 0.3141711
Soma(ProbT,1000)/1000
##            Baixa     Média      Alta
## Baixa 0.06306674 0.6232440 0.3136892
## Média 0.06237333 0.6235364 0.3140903
## Alta  0.06228421 0.6232886 0.3144272


Percebemos que a cadeia é regular e, portanto, ergódica ou irredutível. Sabemos então que esta cadeia é recorrente positiva. Com o comando steadyStates identificamos a distribuição estacionária por um método automático, mais do que identificar simplesmente os estados recorrentes.

Uma segunda forma automática é utilizar a função Soma, a qual nos aproxima também ao valor de \(\pi\). Vamos mostrar a seguir os passos para chegar ao resultado programado no comando steadyStates.

eigen(t(Prob.T))$vectors[,1]
## [1] -0.08901096 -0.88947376 -0.44823374
sum(eigen(t(Prob.T))$vectors[,1])
## [1] -1.426718
eigen(t(Prob.T))$vectors[,1]/sum(eigen(t(Prob.T))$vectors[,1])
## [1] 0.06238859 0.62344029 0.31417112


Agora apresentamos a resolução, ou formas de resolver, da equação \(\pi G=(0,0,\cdots,1)\), a qual constitui o terceiro procedimento comentado para encontrar a distribuição estacionária.

G=Prob.T-diag(dim(Prob.T)[1])
G
##       Baixa Média  Alta
## Baixa -0.55  0.48  0.07
## Média  0.05 -0.30  0.25
## Alta   0.01  0.50 -0.51
G[,3]=1
G
##       Baixa Média Alta
## Baixa -0.55  0.48    1
## Média  0.05 -0.30    1
## Alta   0.01  0.50    1
c(0,0,1)%*%solve(G)
##           Baixa     Média      Alta
## [1,] 0.06238859 0.6234403 0.3141711


Como mencionado nem todas as formas de resolver a equação \(\pi(\mathcal{P}-\mbox{I}) \, = \, \pmb{0}\), acrescentando a restrição de que \(\pi\) some um, funcionam. O seguinte exemplo mostra isso, em particular nessa situação não existe distribuição estacionária.


Exemplo 4.15: Experimento de criação de plantas.

Um botânico está estudando uma certa variedade de planta que é monoecious, ou seja, tem órgãos masculinos e femininos em flores separadas em uma única planta. Ele começa com duas plantas, as quais chamaremos de I e II. Por polinização cruzada: cruzando I do sexo masculino com o sexo feminino de II e I do sexo feminino com II do sexo masculino produz dois descendentes para a próxima geração.

As plantas originais são destruídas e o processo repete-se assim que a nova geração de duas plantas esteja madura. Várias repetições do estudo são executados simultaneamente. O botânico poderia estar interessado, por exemplo, na proporção de plantas que em qualquer geração possuem cada um dos vários genótipos possíveis para um determinado gene.

Suponha-se que o gene tem dois alelos, \(A\) e \(a\). O genótipo de um indivíduo será então uma das três combinações: \(AA\), \(Aa\) ou \(aa\). Quando um novo indivíduo nasce herda um dos dois alelos com probabilidade de 1/2 cada a partir de um dos pais, e a seleção do alelo herdado de cada progenitor é independente. A prole dois obém os seus genótipos independentemente um do outro. Por exemplo, se os pais têm genótipos \(AA\) e \(Aa\), a primeira prole terá \(A\) com certeza no primeiro alelo e vai ter \(A\) ou \(a\) como segundo alelo com probabilidade 1/2 cada um.

Consideremos os estados desta população ser o conjunto de genótipos de dois membros da população atual. Não vamos fazer distinção entre o conjunto \(\{AA, Aa\}\) e \(\{Aa, AA\}\). Há, então, seis estados e o espaço de estados será: \[ S=\{ \{AA, AA\}, \{AA, Aa\}, \{AA, aa\}, \{Aa, Aa\}, \{Aa, aa\}, \{aa, aa\} \}\cdot \]

Para cada estado, podemos calcular a probabilidade de que a próxima geração vai estar em cada um dos seis estados. Por exemplo, se o estado é \(\{AA, AA\}\) ou \(\{aa, aa\}\), a próxima geração estará no mesmo estado com probabilidade 1. Se o estado é \(\{AA, aa\}\), a próxima geração estará no estado \(\{Aa, aa\}\) com probabilidade 1. Os outros três estados têm transições mais complicadas.

Se o estado atual é \(\{Aa, Aa\}\) então todos os outros seis estados são possíveis na próxima geração. Para calcular as probabilidades de transição, ajuda entender a probabilidade de que um determinado descendente venha ter cada uma dos três genótipos. A Figura 4.2 ilustra a possível herança à descendência deste estado.

Figura 4.2: Grafo de algumas probabilidades de transição no experimento de criação de plantas.

Cada seta que vai para baixo na Figura 4.2 é uma possível herança de um alelo e cada combinação de setas que termina num genótipo tem probabilidade 1/4. Segue-se que a probabilidade de \(AA\) e \(aa\) são ambas 1/4, enquanto que a probabilidade de \(Aa\) é 1/2; porque duas combinações diferentes de setas levam a essa prole. Para que o próximo estado seja \(\{AA, AA\}\) ambas proles devem ser \(AA\) independentemente, de modo que a probabilidade de essa transição é 1/16. O mesmo argumento implica que a probabilidade de uma transição a \(\{aa, aa\}\) é 1/16. Uma transição de \(\{AA, Aa\}\) requer uma prole seja \(AA\), com probabilidade 1/4 e o outro seja \(Aa\) com probabilidade 1/2. Mas os dois genótipos diferentes podem ocorrer em qualquer ordem, de modo que a probabilidade de uma tal transição é \(2\times (1/4)\times (1/2) = 1/4\).

Um argumento similar mostra que a transição para \(\{Aa, aa\}\) também tem probabilidade 1/4. Uma transição de \(\{AA, aa\}\) requer uma prole ser \(AA\), com probabilidade 1/4, e o outro para ser \(aa\) com probabilidade 1/4. Mais uma vez, estes podem ocorrer em duas ordens, por isso toda a probabilidade é \(2\times 1/4\times 1/4 = 1/8\). Por subtração, a probabilidade de uma transição para \(\{Aa, Aa\}\) deve ser \(1-1/16-1/16-1/4-1/4-1/8 = 1/4\).

A matriz de transição é apresentada abaixo, utilizando-se do comando matrix, e posteriormente transformado em objeto markovchain.

estados=c("AA, AA","AA, Aa","AA, aa","Aa, Aa","Aa, aa","aa, aa")
Prob.T=matrix(c(1.0000,0.0000,0.0000,0.0000,0.0000,0.0000,
                0.2500,0.5000,0.0000,0.2500,0.0000,0.0000,
                0.0000,0.0000,0.0000,1.0000,0.0000,0.0000,
                0.0625,0.2500,0.1250,0.2500,0.2500,0.0625,
                0.0000,0.0000,0.0000,0.2500,0.5000,0.2500,
                0.0000,0.0000,0.0000,0.0000,0.0000,1.0000),
              nrow=6, ncol=6, byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T,
            name="Experimento de criação de plantas")


Primeiro vamos identificar os estados recorrentes e, portanto, os estados nos quais a distribuição estacionária não será nula.

steadyStates(ProbT)
##      AA, AA AA, Aa AA, aa Aa, Aa Aa, aa aa, aa
## [1,]      0      0      0      0      0      1
## [2,]      1      0      0      0      0      0


Percebemos que os estados recorrentes são todos estados absorventes, logo recorrentes nulos. Nestes casos a distribuição estacionária será também nula.

transientStates(ProbT)
## [1] "AA, Aa" "AA, aa" "Aa, Aa" "Aa, aa"


Não temos mais nada a fazer, identificamos que os estados \(\{AA, AA\}\) e \(\{aa, aa\}\) são absorventes e os outros transientes. Logo, esta cadeia não tem distribuição estacionária. O que queremos agora é mostrar que, neste exemplo, a forma de encontrar a distribuição estacionária utilizando a matriz \(G\), não funciona. Isso deve-se ao fato de que essa matriz aqui é singular e, portanto, não tem inversa.

G=Prob.T-diag(dim(Prob.T)[1])
G[,6]=1
library(MASS)
c(0,0,0,0,0,1)%*%ginv(G)
##      [,1]         [,2]         [,3]         [,4]         [,5] [,6]
## [1,]  0.5 8.326673e-17 1.387779e-16 8.326673e-17 8.326673e-17  0.5


Por último apresentamos mais um exemplo no qual a distribuição estacionária não existe.


Exemplo 4.16: Ruína do jogador.

Suponha que dois jogadores \(A\) e \(B\) estejam jogando um jogo um contra o outro. Seja \(p\) um determinado número de forma que \(0 < p < 1\) e vamos supor que em cada jogada do jogo, a probabilidade de que jogador \(A\) vai ganhar um Real do jogador \(B\) seja \(p\) e a probabilidade de que jogador \(B\) vai ganhar um Real do jogador \(A\) seja \(1-p\). Suponhamos também que a fortuna inicial do jogador \(A\) seja de \(i\) Reais e que a fortuna inicial do jogador \(B\) seja de \(k-i\) Reais, onde tanto \(i\) quanto \(k-i\) sejam números inteiros positivos conhecidos. Assim, a fortuna total dos dois jogadores é \(k\) Reais.

Finalmente, suponha que os jogadores vão jogar o jogo várias vezes e de forma independente até que a fortuna de um deles seja reduzida a 0 (zero) Reais. Outra maneira de pensar sobre o problema é que \(B\) seja um casino e \(A\) um jogador que está determinado a sair assim que ganhar \(k-i\) Reais do casino ou quando ele for à falência, o que ocorrer primeiro.

Vamos agora considerar este jogo a partir do ponto de vista do jogador \(A\). Sua fortuna inicial é \(i\) Reais e em cada jogada do jogo sua fortuna vai ser acrescida de um Real com uma probabilidade \(p\) ou diminuir por um Real com uma probabilidade \(1-p\). Se \(p>1/2\) o jogo será favorável a ele; caso \(p \leq 1/2\) o jogo será desfavorável a ele; e se \(p=1/2\) o jogo será igualmente favorável a ambos os jogadores.

O jogo termina ou quando a fortuna do jogador \(A\) atinge \(k\) Reais, caso em que o jogador \(B\) não terá nenhum dinheiro sobrando, ou quando a fortuna do jogador \(A\) atingir 0 Reais. O problema é determinar a probabilidade de que a fortuna do jogador \(A\) vai chegar a \(k\) Reais antes de atingir 0 Reais. Porque um dos jogadores não terá nenhum dinheiro sobrando no final do jogo, este problema é chamado de Problema da Ruína do Jogador.

A sequência de valores em posse do jogador através do curso de essas jogadas forma uma Cadeia de Markov com dois estados absorventes: 0 e \(k\). Existem \(k-1\) outros estados, ou seja, \(S=\{0,1,,\cdots,k-1,k\}\). A matriz de transição tem primeira e última fila sendo \((1,0,\cdots,0)\) e \((0,0,\cdots,1)\), respectivamente. A \(i\)-ésima linha, para \(i=1,\cdots,k-1\) possui 0 em todos os lugares, exceto na coordenada \(i-1\) onde tem \(1-p\) e na coordenada \(i+1\), onde tem \(p\).

Ao contrário de outras situações, desta vez a sequência de matrizes \(\mathcal{P}^n\) converge mas não há nenhuma distribuição estacionária. O limite de \(\mathcal{P}^n\) tem na sua última coluna os números \(a_0,\cdots,a_k\), onde \(a_i\) é a probabilidade de que a fortuna do jogador que começa com \(i\) Reais atinja \(k\) Reais antes do que atinja 0 Reais. A primeira coluna da matriz limite tem os números \(1-a_0,\cdots,1-a_k\) e o resto da matriz é toda de zeros. Nesta situação acontece o mesmo do exemplo anterior, a distribuição estacionária está concentrada nos estados absorventes.

Com as linhas de comando abaixo exemplificamos a situação particular de um jogador que atingir uma fortuna de 5 Reais, com probabilidade de ganhar em cada jogo de \(p=0.45\).

estados=c("0","1","2","3","4","5")
Prob.T=matrix(c(1.00,0.00,0.00,0.00,0.00,0.00,
                0.55,0.00,0.45,0.00,0.00,0.00,
                0.00,0.55,0.00,0.45,0.00,0.00,
                0.00,0.00,0.55,0.00,0.45,0.00,
                0.00,0.00,0.00,0.55,0.00,0.45,
                0.00,0.00,0.00,0.00,0.00,1.00),
              nrow=6, ncol=6, byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T,
            name="Ruína do jogador")


As probabilidades de ganhar as calculamos elevando a matriz \(\mathcal{P}\) a uma potência elevada, nesta situação 10.000; obtendo-se a resposta mostrada a seguir.

ProbT^10000
## Ruína do jogador^10000 
##  A  6 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3, 4, 5 
##  The transition matrix  (by rows)  is defined as follows: 
##           0 1 2 3 4         5
## 0 1.0000000 0 0 0 0 0.0000000
## 1 0.8713555 0 0 0 0 0.1286445
## 2 0.7141233 0 0 0 0 0.2858767
## 3 0.5219505 0 0 0 0 0.4780495
## 4 0.2870728 0 0 0 0 0.7129272
## 5 0.0000000 0 0 0 0 1.0000000


4.7 Exercícios


  1. Seja \(\{C_n\}_{n\ge 0}\) uma Cadeia de Markov em \(S\) com função de transição \(\mathcal{P}\). Mostre que \[ G_n(x,y)\le G_n(y,y), \; \forall n \quad \mbox{e para} \quad x,y\in S \cdot \]

  2. Considere uma Cadeia de Markov com estados \(S=\{0, 1, 2, 3, 4\}\). Suponha que \(P(C_0=0)=1\) e que quando a cadeia está no estado \(i\), \(i>0\); o próximo estado é igualmente provável dentre os estados \(\{0,1,\cdots,i-1\}\). Encontre a distribuição estacionária desta Cadeia de Markov.

  3. Considere uma Cadeia de Markov finita com matriz de probabilidades de transição \(\mathcal{P}\) e seja \(x\) um estado recorrente. Prove que \(x\) é aperiódico se \(p_{x,x}>0\). Observação: um estado é aperiódico de seu período for 1.

  4. Mostre que em uma Cadeia de Markov finita não há estados recorrentes nulos e nem todos os estados podem ser transientes.

  5. Uma matriz de probabilidades de transição \(\mathcal{P}\) é dita ser duplamente estocástica se a soma por colunas for também 1, isto é, se \[ \sum_{x\in S} p_{_{x,y}}=1 \quad \forall y\in S\cdot \] Considere uma cadeia com matriz de transição duplamente estocástica irredutível, aperiódica e consistindo de \(M+1\) estados, do qual \(S=\{0,1,2,\cdots,M\}\). Prove que a distribuição estacionária é dada por \[ \pi(y)=\dfrac{1}{M+1}, \quad y\in S\cdot \]

  6. Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2\}\) e matriz de probabilidades de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 \\ 0.4 & 0.4 & 0.2 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.4 & 0.4 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \] Mostre que esta cadeia tem uma única distribuição estacionária \(\pi\) e encontre-a.

  7. Seja \(\pi\) a distribuição estacionária de uma Cadeia de Markov. Prove que se \(\pi(x)>0\) e se \(y\) for alcançável a partir de \(x\), então \(\pi(y)>0\).

  8. eja \(\pi\) a distribuição estacionária de uma Cadeia de Markov. Suponha que \(y\) e \(z\) sejam dois estados tais que, para alguma constante \(c\), se satisfaz que \[ p_{x,y}=c \, p_{x,z}, \qquad x\in S\cdot \] Mostre que \(\pi(y)=c\pi(z)\).

  9. Considere uma Cadeia de Markov com espaço de estados os inteiros não negativos, com probabilidade de transição dada por \(p_{x,x+1}=p\) e \(p_{x,0}=1-p\), onde \(0 < p < 1\). Encontre a distribuição estacionária \(\pi\) e prove que esta é única.

  10. Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2\}\) e matriz de probabilidades de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \end{matrix} \left ( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right . \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1/2 & 1/2 & 0 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

    1. Mostre que esta é uma cadeia irredutível.

    2. Encontre o período.

    3. Encontre a distribuiço estacionária.


  1. Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2,3,4\}\) e matriz de probabilidades de transição \[ \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 \\ 0 & 1/3 & 2/3 & 0 & 0 \\ 0 & 0 & 0 & 1/4 & 3/4 \\ 0 & 0 & 0 & 1/4 & 3/4 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left . \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right ) \end{matrix} \]

    1. Mostre que esta é uma cadeia irredutível.

    2. Encontre o período.

    3. Encontre a distribuição estacionáia.


  1. Cada vez que um cliente compra um tubo de pasta de dente, ele escolhe qualquer marca A ou B. Suponha que para cada compra após a primeira, a probabilidade será de 1/3 de que ele vai escolher a mesma marca que ele escolheu em sua compra anterior e a probabilidade será de 2/3 de que ele vai mudar de marca. Se ele têm a mesma probabilidade de escolher qualquer marca A ou B em sua primeira compra, qual será a probabilidade de que ambas: as suas primeira e segunda aquisições sejam a marca A e ambas a terceira e a quarta compras sejam a marca B?

  2. Um sistema consiste de dois componentes que operam em paralelo: o sistema funciona se pelo menos um dos componentes estiver operando. Em qualquer período, se os dois componentes estiverem em funcionamento no inicio do período, podem vir a falhar, independentemente, durante este período com probabilidade \(\alpha\). Quando um componente falha, o componente restante pode falhar durante o período com uma probabilidade mais elevada \(\beta\). Existe uma única oficina para realizar os reparos e leva dois períodos para reparar um componente.

    1. Especifique a matriz de probabilidades de transição em termos de \(\alpha\) e \(\beta\).

    2. Caso \(\alpha=0.1\) e \(\beta=0.2\), num período longo prazo de tempo, qual será a probabilidade do sistema permanecer operacional?


  1. Sejam \(\pi_0\) e \(\pi_1\) duas distribuições estacionárias distintas para uma Cadeia de Markov.

    1. Prove que para \(0\le \alpha\le 1\), a função \(\pi_\alpha\), definida como \[ \pi_\alpha(x)=(1-\alpha)\pi_0(x)+\alpha\pi_1(x), \qquad x\in S, \] é uma distribuição estacionária.

    2. Mostre que distintos valores de \(\alpha\) implicam em distribuições estacionárias \(\pi_\alpha\) distintas. Para demonstrar isso sugere-se escolher \(x_0\in S\) tal que \(\pi_0(x_0)\ne \pi_1(x_0)\) e prove que \(\pi_\alpha(x_0)=\pi_\beta(x_0)\) implica que \(\alpha=\beta\).


  1. Uma partícula move-se sobre um círculo através de pontos que foram marcados 0, 1, 2, 3, 4 no sentido horário. Em cada passo, tem uma probabilidade \(p\) da partícula se mover para a direita, sentido horário e probabilidade \(1-p\) de mover-se para a esquerda, no sentido anti-horário. Seja \(C_n\) a localização da partícula sobre o círculo após o \(n\)-ésimo passo. O processo \(\{C_n\}_{n\ge 0}\) é uma Cadeia de Markov.

    1. Encontre a matriz de probabilidades de transição.

    2. Encontre a distribuição estacionária.


  1. Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2,\cdots\}\) e função de transição: \[ p_{0,j}=f_j \quad \mbox{e} \quad p_{j,j-1}=1, \] onde \(1=f_1+f_2+\cdots+f_j+\cdots\).

    1. Esboçar o grafo da matriz de transição.

    2. Determine se a cadeia é irredutível.

    3. Determine se o estado 0 é transiente, recorrente nulo ou recorrente positivo.

    4. Encontre a expressão da distribuição estacionária, se existir.


  1. Considere uma Cadeia de Markov com espaço de estados \(S=\{1,2,\cdots\}\) e como função de transição a seguinte: \[ p_{j,j+1}=a_j \quad \mbox{e} \quad p_{j,1}=1-a_j, \quad 0 < a_j < 1\cdot \]

    1. Esboçar o grafo da matriz de transição.

    2. Determine se a cadeia é irredutível.

    3. Determine se o estado 1 é transiente, recorrente nulo ou recorrente positivo.

    4. Encontre a expressão da distribuição estacionária, se existir.

    5. Forneça respostas específicas aos itens (c) e (d) se:

      1. \(a_j=1/2\), \(\forall j\),

      2. \(a_j=(j-1)/j\), \(\forall j\),

      3. \(a_j=1/j\), \(\forall j\),

      4. \(a_j=(1/2)^j\), \(\forall j\),

      5. \(a_j=1-(1/2)^j\), \(\forall j\).

4.8 Bibliografia


Doob, J. L. 1953. Stochastic Processes. New York, Wiley.
Gallager, R. G. 1996. Discrete Stochastic Processes. Kluwer Academic Press, Boston.
Hoel, P. G., S. C. Port, and C. J. Stone. 1972. Introduction to Stochastic Processes. Houghton Mifflin Company.
Kemeny, J. G., and L. Snell. 1976. Finite Markov Chains. Springer-Verlag.