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 é
ainda \(\pi\). Então \(\pi\) é chamada uma distribuição estacionária.
Definição IV.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
\begin{equation}
\sum_x \pi(x) p_{x,y}=\pi(y), \qquad y\in S
\end{equation}
então \(\pi\) é chamada de distribuição estacionária.
Suponha que a distribuição estacionária \(\pi\) exista e satisfaça que
\begin{equation}
\lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y), \qquad y\in S \cdot
\end{equation}
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\) é, 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 IV.1.
No caso de uma Cadeia de Markov com espaço de estados \(S=\{0,1\}\) e matriz de transição
\begin{equation}
\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}
\end{equation}
se \(p+q>0\), esta cadeia tem uma única distribuição estacionária \(\pi\), dada por
\begin{equation*}
\pi(0)=\frac{q}{p+q} \quad \mbox{e} \quad \pi(1)=\frac{p}{p+q} \cdot
\end{equation*}
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.
Mostraremos que esta cadeia tem uma única distribuição estacionária \(\pi\) e a encontraremos.
A expressão na definição 26 fornece, nesta situação, as seguintes três equações:
\begin{equation}
\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}
\end{equation}
e, pelo fato de, \(\sum_x \gamma(x)=1\), temos a quarta equação
\begin{equation}
\pi(0)+\pi(1)+\pi(2)=1 \cdot
\end{equation}
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\).
Concluímos a partir da primeira equação que \(\pi(2)=3\pi(0)/2\). Da quarta equação, agora vemos que
\begin{equation*}
\pi(0)\left(1+\frac{5}{3}+\frac{3}{2}\right)=1,
\end{equation*}
e, portanto, que \(\pi(0)=\frac{6}{25}\).
Assim,
\begin{equation*}
\pi(1)=\frac{5}{3}\times \frac{6}{25}=\frac{2}{5}
\end{equation*}
e
\begin{equation*}
\pi(2)=\frac{3}{2}\times \frac{6}{25}=\frac{9}{25} \cdot
\end{equation*}
É facilmente 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
\begin{equation*}
\pi=\left(\dfrac{6}{25},\dfrac{2}{5},\dfrac{9}{25}\right)\cdot
\end{equation*}
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 podem ser mais facilmente resolvidas.
Exemplo IV.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{equation*}
\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}
\end{equation*}
Similar ao exemplo anterior, encontramos que a distribuição estacionária é única e dada por
\begin{equation*}
\pi=\left(\dfrac{1}{8},\dfrac{3}{8},\dfrac{3}{8},\dfrac{1}{8}\right)\cdot
\end{equation*}
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 IV.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 IV.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 IV.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 é repetido indefinidamente e as seleções sã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\}\).
Para ver por que \(\mathcal{P}\) é dado 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}\) é a probabilidade de que a bola selecionada seja da caixa 1 e que a caixa selecionada seja a 2. Assim
\begin{equation}
p_{1,0}=\frac{1}{3}\times \frac{1}{2}=\frac{1}{6} \cdot
\end{equation}
Em segundo lugar, \(p_{1,2}\) é a probabilidade de que a bola selecionada seja da caixa 2 e a caixa selecionada é a 1. Assim
\begin{equation}
p_{1,2}=\frac{2}{3}\times \frac{1}{2}=\frac{1}{3} \cdot
\end{equation}
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}\) é 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
\begin{equation}
p_{1,1}=\frac{1}{3}\times \frac{1}{2}+\frac{2}{3}\times \frac{1}{2}=\frac{1}{2} \cdot
\end{equation}
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
\begin{equation*}
\pi=\left(\dfrac{1}{8},\dfrac{3}{8},\dfrac{3}{8},\dfrac{1}{8}\right)\cdot
\end{equation*}
Provaremos posteriormente que \(\displaystyle \lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y)\), \(\forall y\in S\) é válida neste exemplo.
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 IV.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
\begin{equation}
p_{_{A, \,A^c}}=\sum_{x\in A}\sum_{y\in A^c} \pi(x) p_{x,y}\cdot
\end{equation}
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 é útil para caracterizar a distribuição
estacionária, resultado apresentado a continuação.
Teorema IV.1
Seja \(p_{_{A, \, A^c}}\) a probabilidade de fluxo 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
\begin{equation}
p_{_{A, \, A^c}} \, = \, p_{_{A^c, \, A}},
\end{equation}
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{equation*}
\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}
\end{equation*}
Então
\begin{equation}
p_{_{A,\, A^c}} \, = \, \sum_{y\in A^c} \pi(y)-p_{_{A^c,\, A^c}}\cdot
\end{equation}
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\),
\begin{equation}
p_{_{A,\, A^c}} \, = \, p_{_{A^c,\, A}}\cdot
\end{equation}
Em particular, se \(A=\{a\}\), \(A^c=\mathcal{S}\setminus \{a\}\), qualquer seja \(a\in S\). Então,
\begin{equation*}
\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}
\end{equation*}
do qual obtemos que
\begin{equation*}
\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}
\end{equation*}
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 IV.5.
No Exemplo IV.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 IV.1 se satisfaz. Por exemplo, se \(A=\{0\}\), \(A^c=\{1,2\}\) e então
\begin{equation*}
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}
\end{equation*}
e
\begin{equation*}
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
\end{equation*}
Assim podemos construir a tabela a seguir
\(A\)
\(A^c\)
\(p_{_{A,\, A^c}}\)
\(p_{_{A^c,\, A}}\)
\(\{0\}\)
\(\{1,2\}\)
\(\pi(0)(p_{0,1}+p_{0,2})=\dfrac{4}{25}\)
\(\pi(1)p_{1,0}+\pi(2)p_{2,0}=\dfrac{4}{25}\)
\(\{1\}\)
\(\{0,2\}\)
\(\pi(1)(p_{1,0}+p_{1,2})=\dfrac{1}{5}\)
\(\pi(0)p_{0,1}+\pi(2)p_{2,1}=\dfrac{1}{5}\)
\(\{2\}\)
\(\{0,1\}\)
\(\pi(2)(p_{2,0}+p_{2,1})=\dfrac{9}{50}\)
\(\pi(0)p_{0,2}+\pi(1)p_{1,2}=\dfrac{9}{50}\)
As outras situações são redundantes. Desta forma verificamos que
\begin{equation*}
\pi=\left(\dfrac{6}{25},\dfrac{2}{5},\dfrac{9}{25}\right)
\end{equation*}
é, 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 IV.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
\begin{equation}
\sum_{x\in S} \pi(x) p^{(n)}_{x,y} \, = \, \pi(y), \qquad y\in S \cdot
\end{equation}
Demonstração.
Dado que \(\pi\) é a distribuição estacionária da Cadeia de Markov, então
\begin{equation*}
\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
\end{equation*}
Similarmente, por indução com base na fórmula
\begin{equation*}
p^{(n+1)}_{x,y} \, = \, \sum_z p^{(n)}_{x,z}p_{z,y},
\end{equation*}
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\)
\begin{equation}
P(C_n=y) \, = \, \pi(y), \qquad y\in S,
\end{equation}
e, portanto, a distribuição de \(C_n\) é independente de \(n\). Suponhamos, por outro lado, que a distribuição de \(C_n\) é independente
de \(n\), então a distribuição inicial é tal que
\begin{equation*}
\pi_0(y) \, = \, P(C_0=y) \, = \, P(C_t=y) \, = \, \sum_{x\in S} \pi_0(x)p_{x,y} \cdot
\end{equation*}
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
\begin{equation}
P(C_n=y)=\sum_{x\in S} \pi_0(x)p^{(n)}_{x,y}, \qquad y\in S
\end{equation}
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, obtém-se que
\begin{equation}
\lim_{n\to\infty} P(C_n=y)=\sum_{x\in S} \pi_0(x)\pi(y) \cdot
\end{equation}
Desde que \(\displaystyle \sum_x\pi_0(x)=1\), concluímos que
\begin{equation}
\lim_{n\to\infty} P(C_n=y)=\pi(y), \qquad y\in S \cdot
\end{equation}
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
\begin{equation*}
Y_n=C_{n+n_0}, \qquad n\ge 0 \cdot
\end{equation*}
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.
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
\begin{equation*}
\lim_{n\to\infty} p^{(n)}_{x,y} = \pi(y), \qquad y\in S,
\end{equation*}
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
\begin{equation}
\lim_{n\to\infty} a_n=L,
\end{equation}
para algum número finito \(L\), então
\begin{equation}
\lim_{n\to\infty} \dfrac{1}{n}\sum_{m=1}^n a_m=L \cdot
\end{equation}
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
\begin{equation}
\lim_{n\to\infty} \dfrac{1}{n} \sum_{m=1}^n a_m=\dfrac{1}{2} \cdot
\end{equation}
Nesta seção vamos demonstrar que
\begin{equation}
\lim_{n\to\infty} \dfrac{1}{n} \sum_{m=1}^n p^{(m)}_{x,y}
\end{equation}
existe para cada par de estados \(x,y\) de uma Cadeia de Markov arbitrária. Na Seção IV.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
\begin{equation}
\pmb{1}_y(z)=\left\{ \begin{array}{cr} 1, & \quad z=y \\ 0, & \quad z\neq y \end{array} \right.,
\end{equation}
é a função indicadora e que
\begin{equation}
\mbox{E}_x\big(\pmb{1}_y(C_n)\big) \, = \, P_x(C_n=y)=p^{(n)}_{x,y},
\end{equation}
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 IV.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
\begin{equation}
N_n(y)=\sum_{m=1}^n \pmb{1}_y(C_m) \cdot
\end{equation}
Seja agora
\begin{equation}
G_n(x,y)=\sum_{m=1}^n p^{(m)}_{x,y},
\end{equation}
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
\begin{equation}
\mbox{E}_x\big(N_n(y)\big)=G_n(x,y) \cdot
\end{equation}
Se \(y\) for um estado transiente, então
\begin{equation}
\lim_{n\to\infty} N_n(y)=N(y) < \infty \qquad \mbox{com probabilidade um},
\end{equation}
e
\begin{equation}
\lim_{n\to\infty} G_n(x,y)=G(x,y) < \infty, \qquad x\in S\cdot
\end{equation}
Segue então que
\begin{equation}
\lim_{n\to\infty} \dfrac{N_n(y)}{n}=0 \qquad \mbox{com probabilidade um}
\end{equation}
e que
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=0, \qquad x\in S\cdot
\end{equation}
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 IV.6.
No exemplo da compra de pasta de dentes, Exemplo 22, 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{equation}
\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}
\end{equation}
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\) é 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 IV.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
\begin{equation}
\lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{\pmb{1}_{\{T_y<\infty\}}}{m_y} \qquad \mbox{com probabilidade um}
\end{equation}
e
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{\rho_{x,y}}{m_y}, \qquad x\in S \cdot
\end{equation}
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
\begin{equation}
T_y^r=\min\{n\ge 1: \, N_n(y)=r\} \cdot
\end{equation}
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
\begin{equation}
T_y^r=W_y^1+\cdots+W_y^r \cdot
\end{equation}
As variáveis aleatórias \(W_y^1,W_y^2,\cdots\) são independentes e igualmente distribuídas e, então, tem média comum \(\mbox{E}_y(W_y^1)=\mbox{E}_y(T_y)=m_y\).
Este resultado é intuitivamente óbvio, já 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
\begin{equation}
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})
\end{equation}
e em seguida, mostrado por indução que
\begin{equation}
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
\end{equation}
O Teorema dos Grandes Números implica que
\begin{equation}
\lim_{n\to\infty} \dfrac{W_y^1+W_y^2+\cdots+W_y^k}{k}=m_y,
\end{equation}
com probabilidade um, isto é, que
\begin{equation}
\lim_{k\to\infty} \dfrac{T_y^k}{k}=m_y,
\end{equation}
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 é,
\begin{equation}
T_y^{N_n(y)}\le n < T_y^{N_n(y)+1},
\end{equation}
e então
\begin{equation}
\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)},
\end{equation}
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
\begin{equation}
\lim_{n\to\infty} \dfrac{n}{N_n(y)}=m_y,
\end{equation}
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
\begin{equation}
\dfrac{N_n(y)}{n}\to \dfrac{1_{\{T_y < \infty\}}}{m_y}
\end{equation}
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
\begin{equation}
0\le \dfrac{N_n(y)}{n}\le 1 \cdot
\end{equation}
O Teorema da Convergência Dominada, permite-nos concluir que
\begin{equation}
\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},
\end{equation}
Isto completa a demonstração do Teorema 29.
▉
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\) é grande, a proporção de vezes em que a cadeia está no estado \(y\) deve ser de cerca \(1/m_y\) unidades, nas primeiras
\(n\) unidades de tempo. Observemos também que a expressão
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{\rho_{x,y}}{m_y},
\end{equation}
\(x\in S\) se obtém tomando esperança em
\begin{equation}
\lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{\pmb{1}_{\{T_y<\infty\}}}{m_y},
\end{equation}
a qual acontece com probabilidade um.
Corolário IV.4.
Seja \(F\) um conjunto fechado irredutível de estados recorrentes. Então
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(x,y)}{n}=\dfrac{1}{m_y}, \qquad x,y\in F
\end{equation}
e se \(P(C_0\in F)=1\), então com probabilidade um
\begin{equation}
\lim_{n\to\infty} \dfrac{N_n(y)}{n}=\dfrac{1}{m_y}, \qquad y\in F\cdot
\end{equation}
Demonstração.
Lembremos que se \(y\) é um estado recorrente, então \(\rho_{x,y}=1\) (Teorema III.1) e que \(P(T_y < \infty)=1\).
Observamos que
\begin{equation}
\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}
\end{equation}
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
30
\begin{equation*}
\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}
\end{equation*}
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 6: 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.
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 IV.4 (Estado recorrente nulo).
Um estado recorrente \(y\) é chamado de recorrente nulo se \(m_y=\infty\).
Do Teorema IV.3 podemos perceber que, se \(y\) é um estado recorrente nulo, então
\begin{equation}
\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
\end{equation}
Teorema IV.5.
Seja \(y\) é um estado recorrente nulo, então
\begin{equation}
\lim_{n\to\infty} p_{x,y}^{(n)}=0, \qquad x\in S\cdot
\end{equation}
Demonstração.
Consequência do Teorema IV.3 e do fato de \(m_y=\infty\).
▉
Este é um resultado mais forte do que àquele
\begin{equation*}
\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
\end{equation*}
Não o vamos provar uma vez que não será necessário mais tarde, e sua prova é bastante difícil.
Definição IV.5 (Estado recorrente positivo).
Um estado recorrente \(y\) é chamado de recorrente positivo se \(m_y < \infty\).
Do Teorema IV.3 podemos perceber que, se \(y\) é um estado recorrente positivo, então
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(x,y)}{n} \, = \, \dfrac{1}{m_y}>0, \qquad x\in S\cdot
\end{equation}
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 IV.3 que, se \(y\) é 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 IV.6.
Seja \(x\) um estado recorrente positivo e suponha que \(x\) conduz a \(y\). Então, \(y\) é um estado recorrente positivo.
Demonstração.
Segue do Teorema III.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
\begin{equation}
p_{y,x}^{(n_1)}>0 \qquad \mbox{e} \qquad p_{x,y}^{(n_2)}>0\cdot
\end{equation}
Agora,
\begin{equation}
p^{(n_1+m+n_2)}_{y,y}\ge p^{(n_1)}_{y,x}p^{(m)}_{x,x}p^{(n_2)}_{x,y},
\end{equation}
e somando em \(m=1,2,,\cdots,n\) e dividindo por \(n\), concluímos que
\begin{equation}
\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
\end{equation}
Quando \(n\to\infty\), o termo à esquerda da desigualdade acima converge a \(1/m_y\) e o termo à direita converge a
\begin{equation}
\dfrac{p^{(n_1)}_{y,x}p^{(n_2)}_{x,y}}{m_x} \cdot
\end{equation}
Portanto
\begin{equation}
\dfrac{1}{m_y}\ge \dfrac{p^{(n_1)}_{y,x}p^{(n_2)}_{x,y}}{m_x}>0,
\end{equation}
e, por consequência, \(m_y < \infty\). Isto mostra que \(y\) é um estado recorrente positivo.
▉
A partir deste teorema e do Teorema III.1, vemos que, se \(F\) é 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 IV.6 (Cadeia recorrente nula e recorrente positiva).
Uma Cadeia de Markov é chamada de cadeia recorrente nula se todos os seus estados são recorrentes nulos. Uma Cadeia de Markov é chamada de cadeia recorrente
positiva se todos os seus estados são 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\) é um conjunto fechado finito de estados então \(F\) tem, pelo menos, um estado recorrente positivo. Por causa de
\begin{equation}
\sum_{y\in F} p^{(m)}_{x,y}=1, \qquad x\in F,
\end{equation}
somando em \(m=1,\cdots,n\) e dividindo por \(n\) encontramos que
\begin{equation}
\sum_{y\in F} \dfrac{G_n(x,y)}{n}=1, \qquad x\in F\cdot
\end{equation}
Caso \(F\) tiver finitos elementos e cada estado em \(F\) for transiente ou recorrente nulo, então vale
\begin{equation}
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}
\end{equation}
uma contradição.
Teorema IV.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 IV.6.
▉
Corolário IV.8.
Uma Cadeia de Markov ergódica com um número finito de estados é recorrente positiva.
Demonstração.
Segue imediatamente do Teorema IV.6 e do Teorema IV.7.
▉
Corolário IV.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 III.1 \(y\) está contido em um conjunto irredutível fechado \(F\) de estados recorrentes. Como \(F\) é necessariamente
finito, se segue do Teorema IV.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 IV.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{equation*}
\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}
\end{equation*}
Não é difícil perceber que esta é uma cadeia ergódica logo, pelos Corolários IV.8 e IV.9 nesta cadeia todos os estados são recorrentes
positivos. O cálculo de sua distribuição estacionária fornece como resultado
\begin{equation*}
\pi=\left(\dfrac{8}{13},\dfrac{3}{13},\dfrac{2}{13}\right)\cdot
\end{equation*}
Bastante inesperadamente, o estudante passa a maior parte do tempo no bar.
Nesta seção vamos determinar quais Cadeias de Markov 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
\begin{equation}
\sum_{z\in S} \pi(z) p^{(m)}_{z,x}=\pi(x),
\end{equation}
qualquer seja o valor de \(m\). Somando em \(m=1,2,\cdots,n\) e dividindo por \(n\), concluímos que
\begin{equation}
\sum_{z\in S} \pi(z)\dfrac{G_n(z,x)}{n}=\pi(x), \qquad x\in S\cdot
\end{equation}
Aceitemos que a distribuição estacionária seja \(\pi=(0.25,0.50,0.25)\). Então, com os comandos a seguir, vamos mostrar que
\begin{equation}
\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\cdot
\end{equation}
> library(markovchain)
> 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.
A função Soma serve para calcular \(G_n(z,x)\) e como podemos perceber, os dois produtos fornecem o mesmo resultado.
Esta é uma situação atípica, no sentido que com \(n,m=1\) conseguimos identificar a distribuição estacionária.
Teorema IV.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
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=0, \qquad x\in S\cdot
\end{equation}
Segue então, das expressões anteriores e do Teorema da Convergência Dominada que
\begin{equation}
\pi(x)=\lim_{n\to\infty} \sum_{z\in S} \pi(z)\dfrac{G_n(z,x)}{n}=0,
\end{equation}
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 IV.11 (Existência da distribuição estacionária).
Uma Cadeia de Markov irredutível positiva tem distribuição estacionária única \(\pi\), dada por
\begin{equation}
\pi(x)=\dfrac{1}{m_x}, \qquad x\in S\cdot
\end{equation}
Demonstração.
Segue do Teorema IV.3 e da suposição deste teorema que
\begin{equation}
\lim_{n\to\infty} \dfrac{G_n(z,x)}{n}=\dfrac{1}{m_x}, \qquad z,x\in S\cdot
\end{equation}
Suponha que \(\pi\) seja a distribuição estacionária. De expressões anteriores e do Teorema da Convergência Dominada, temos que
\begin{equation}
\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}
\end{equation}
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
\begin{equation}
\sum_{x\in S} \dfrac{1}{m_x}=1
\end{equation}
e que
\begin{equation}
\sum_{x\in S} \dfrac{1}{m_x} p_{x,y}=\dfrac{1}{m_y}, \qquad y\in S\cdot
\end{equation}
Para este fim, observamos primeiro que
\begin{equation}
\sum_{x\in S} p^{(m)}_{z,x}=1, \qquad m\geq 1 \cdot
\end{equation}
Somando em \(m=1,\cdots,n\) e dividindo por \(n\), concluímos que
\begin{equation}
\sum_{x\in S} \dfrac{G_n(z,x)}{n}=1, \qquad z\in S\cdot
\end{equation}
Agora observemos que
\begin{equation}
\sum_{x\in S} p^{(m)}_{z,x}p_{x,y} \, = \, p^{(m+1)}_{z,y}\cdot
\end{equation}
Novamente, somando em \(m=1,\cdots,n\) e dividindo por \(n\), concluímos que
\begin{equation}
\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
\end{equation}
Caso \(S\) seja finito, concluímos que
\begin{equation*}
1=\lim_{n\to\infty} \sum_{x\in S} \dfrac{G_n(z,x)}{n}=\sum_{x\in S} \dfrac{1}{m_x},
\end{equation*}
ou seja, concluímos que \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x}=1\) vale. De maneira similar concluímos que o resultado
\begin{equation}
\sum_{x\in S} \dfrac{1}{m_x} p_{x,y}=\dfrac{1}{m_y}, \qquad y\in S,
\end{equation}
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\) 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
\begin{equation}
\sum_{x\in S_1} \dfrac{G_n(z,x)}{n}\le 1, \qquad z\in S\cdot
\end{equation}
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}\), \(z,x\in S\) que
\begin{equation}
\sum_{x\in S_1} \dfrac{1}{m_x}\le 1\cdot
\end{equation}
Pois, se a soma de \(1/m_x\) sobre \(x\in S\) 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
\begin{equation}
\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
\end{equation}
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
\begin{equation}
\sum_{x\in S_1} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}, \qquad y\in S\cdot
\end{equation}
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
\begin{equation}
\sum_{x\in S} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}, \qquad y\in S\cdot
\end{equation}
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
\begin{equation*}
\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},
%\begin{array}{rcl}
% \displaystyle \sum_{y\in\Es} \dfrac{1}{m_y} & \le & \displaystyle \sum_y \left(\sum_x \dfrac{1}{m_x}p_{x,y} \right) \\[0.8em]
% & = & \displaystyle \sum_x \dfrac{1}{m_x}\left(\sum_y p_{x,y} \right) \quad = \quad \sum_x \dfrac{1}{m_x},
%\end{array}
\end{equation*}
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
\begin{equation}
c=\dfrac{1}{\displaystyle \sum_x \dfrac{1}{m_x}}\cdot
\end{equation}
Então, pelo resultado \(\displaystyle \sum_{x\in S} \dfrac{1}{m_x} p_{x,y}\le \dfrac{1}{m_y}\), \(y\in S\),
\begin{equation}
\pi(x)=\dfrac{c}{m_x}, \qquad x\in S,
\end{equation}
define uma distribuição estacionária. Então, pela primeira parte da demonstração deste teorema
\begin{equation}
\dfrac{c}{m_x}=\dfrac{1}{m_x},
\end{equation}
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 IV.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 IV.10 e IV.11.
▉
Corolário IV.13.
Se uma Cadeia de Markov com um número finito de estados é irredutível então tem distribuição estacionária única.
Demonstração.
É uma consequência do Corolário IV.9 e do Teorema IV.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 IV.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
\begin{equation}
\lim_{n\to\infty} \dfrac{N_x(x)}{n} \, = \, \pi(x), \qquad x\in S\cdot
\end{equation}
Demonstração.
É uma consequência do Corolário IV.4 e do Teorema IV.11.
▉
Cadeias redutí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 IV.7.
Dizemos que \(\pi\), uma função de probabilidade, está concentrada em \(F\subset S\) se
\begin{equation}
\pi(x)=0 \qquad \forall x\notin F\cdot
\end{equation}
Teorema IV.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
\begin{equation}
\pi(x)=\left\{ \begin{array}{cc} \dfrac{1}{m_x}, & x\in F \\[0.8em] 0, & \mbox{caso contrário} \end{array}\right.
\end{equation}
Demonstração.
Essencialmente o mesmo argumento utilizado na demonstração do Teorema 37.
▉
Suponhamos que \(F_0\) e \(F_1\) sejam conjuntos de estados recorrentes positivos, fechados, distintos e irredutíveis. Segue do Teorema 41 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,
a distribuição \(\pi_\alpha\), definida para \(0\le\alpha\le 1\) como
\begin{equation}
\pi_\alpha(x)=(1-\alpha)\pi_0(x)+\alpha\pi_1(x), \qquad x\in S,
\end{equation}
aão distribuições estacionárias distintas (Veja o Exercício 12).
Teorema IV.16 (Unicidade da distribuição estacionária).
Seja \(S_P\) o conjunto dos estados recorrentes positivos em uma Cadeia de Markov.
(a) Se \(S_P\) é vazio, a cadeia no possui distribuição estacionária.
(b) Se \(S_P\) é não vazio irredutível, a cadeia têm distribuição estacionária única.
(c) Se \(S_P\) é 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 36, 37 e 41.
▉
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 IV.10 (Continuação do Exemplo III.2)
Queremos encontrar a distribuição estacionária concentrada em cada um dos conjuntos fechados irredutíveis.
No Exemplo III.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{equation}
\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}
\end{equation}
Das primeiras duas destas equações encontramos que \(\pi(4)=\pi(3)/3\) e \(\pi(5)=8\pi(3)/3\). Assim
\begin{equation}
\pi(3)\left(1+1/3+8/3\right)=1,
\end{equation}
do qual concluímos que \(\pi(3)=1/4\), \(\pi(4)=1/12\) e \(\pi(5)=2/3\). Por consequência
\begin{equation}
\pi_1=\left(0,0,0,1/4,1/12,2/3\right)
\end{equation}
é a distribuição estacionária concentrada em \(\{3,4,5\}\).
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
\begin{equation}
\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
\end{equation}
Aqui vamos ver quando o resultado mais forte
\begin{equation}
\lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y), \qquad x,y\in S,
\end{equation}
é 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\) é um número inteiro.
Definição IV.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 \(n\in \mbox{I}\).
Segue-se imediatamente que
\begin{equation}
1\le \mbox{m.d.c.} \, \mbox{I} \le \mbox{min}\{n: n\in \mbox{I}\} \cdot
\end{equation}
Em particular, se \(1\in \mbox{I}\), em seguida temos que m.d.c. \(\mbox{I}=1\). Um outro detalhe interessante é que o mínimo divisor comum de um conjunto de
inteiros positivos pares é 2.
Definição IV.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
\begin{equation}
d_x=\mbox{m.d.c.}\{n\ge 1: \, p^{(n)}_{x,x}>0\} \cdot
\end{equation}
Desta definição vemos que
\begin{equation}
1\le d_x \le \min\{n\ge 1: \, p^{(n)}_{x,x}>0\} \cdot
\end{equation}
Também, se \(p_{x,x}>0\), então \(d_x=1\).
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 IV.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
\begin{equation}
p^{(n_1)}_{x,y}>0 \qquad \mbox{e} \qquad p^{(n_2)}_{y,x}>0\cdot
\end{equation}
Então temos que
\begin{equation}
p^{(n_1+n_2)}_{x,x}\ge p^{(n_1)}_{x,y}p^{(n_2)}_{y,x}>0,
\end{equation}
e por isso \(d_x\) é o divisor de \(n_1+n_2\). Se \(p^{(n)}_{y,y}>0\), então
\begin{equation}
p^{(n_1+n_2)}_{x,x}\ge p^{(n_1)}_{x,y}p^{(n)}_{y,y}p^{(n_2)}_{y,x}>0,
\end{equation}
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 IV.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 proposição 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 pii> 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 IV.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
\begin{equation}
\lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y), \qquad x,y\in S\cdot
\end{equation}
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 r< d\) tal que \(p^{(n)}_{x,y}=0\)
a não ser que \(n=md+r\) para algum inteiro não negativo \(m\) e
\begin{equation}
\lim_{m\to\infty} p^{(md+r)}_{x,y}=d\pi(y), \qquad x,y\in S\cdot
\end{equation}
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 I o conjunto dos inteiros positivos definidos por
\begin{equation}
\mbox{I}=\{n>0: \, p^{(n)}_{a,a}>0\} \cdot
\end{equation}
Então
(a) O máximo divisor comum de I é 1 e,
(b) Se \(m,n\in \) I, então \(m+n\in \) I.
O resultado em (b) obtém-se da desigualdade
\begin{equation}
p^{(m+n)}_{a,a}\geq p^{(m)}_{a,a}p^{(n)}_{a,a}\cdot
\end{equation}
As propriedades (a) e (b) implicam na existência de um número inteiro positivo \(n_1\) tal que \(n\in \) 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
\begin{equation}
p^{(n_2)}_{x,a}>0 \qquad \mbox{e} \qquad p^{(n_3)}_{a,y}>0\cdot
\end{equation}
Então, para \(n\geq n_1\) temos que
\begin{equation}
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
\end{equation}
Provamos que, para qualquer par de estados \(x,y\in S\), existe um inteiro positivo \(n_0\) tal que
\begin{equation}
p^{(n)}_{x,y}>0 \qquad n\geq n_0\cdot
\end{equation}
Seja agora
\begin{equation}
S^2=\{(x,y): \, x,y\in S\}\cdot
\end{equation}
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
\begin{equation}
p_{2_{(x_0,y_0),(x,y)}} \, = \, p_{x_0,x}p_{y_0,y}\cdot
\end{equation}
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\cdot\) exite um \(n_0>0\) tal que
\begin{equation}
p^{(n)}_{x_0,x}>0 \qquad \mbox{e} \qquad p^{(n)}_{y_0,y}>0, \quad n\geq n_0\cdot
\end{equation}
Então
\begin{equation}
p_{2_{(x_0,y_0),(x,y)}} \, = \, p^{(n)}_{x_0,x}p^{(n)}_{y_0,y}, \quad n\geq n_0\cdot
\end{equation}
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{equation}
\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}
\end{equation}
Então, a cadeia em \(S^2\) é recorrente positiva, em particular, é recorrente.
Seja
\begin{equation}
T=\min\{n>0: \, C_n=D_n\}\cdot
\end{equation}
Escolhemos \(a\in S\). Dado que \((C_n,D_n)\) é recorrente,
\begin{equation}
T_{(a,a)}=\min\{n>0: \, (C_n,D_n)=(a,a)\},
\end{equation}
é 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)\),
\begin{equation}
P(C_n=y,T\leq n)=P(D_n=y, T\leq n), \qquad y\in S\cdot
\end{equation}
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\)
\begin{equation}
{P(C_n=y|T=m,C_m=D_m=z)=} \, = \, P(D_n=y|T=m,C_m=D_m=z),
\end{equation}
dado que ambas probabilidades condicionais são iguais a \(p^{(n-m)}_{z,y}\). Agora, o evento \(\{T\leq n\}\) pode ser escrito como
\begin{equation}
\{T\leq n\}=\bigcup_{1\leq m\leq n} \{T=m, C_m=D_m=z\}, \qquad z\in S,
\end{equation}
sendo os eventos \(\{T=m, C_m=D_m=z\}\) disjuntos. Segue que
\begin{equation}
P(C_n=y|T\leq n)=P(D_n=y|T\leq n)
\end{equation}
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{equation}
\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}
\end{equation}
e, de maneira similar, implica que
\begin{equation}
P(D_n=y)\leq P(C_n=y)+P(T>n)\cdot
\end{equation}
Portanto, para \(n>1\)
\begin{equation}
\big|P(C_n=y)-P(D_n=y)\big|\leq P(T>n), \qquad y\in S\cdot
\end{equation}
Dado que \(T\) é finito com probabilidade um,
\begin{equation}
\lim_{n\to\infty} P(T>n)=0\cdot
\end{equation}
Concluímos que
\begin{equation}
\lim_{n\to\infty} \big(P(C_n=y)-P(D_n=y)\big)=0, \qquad y\in S\cdot
\end{equation}
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
\begin{equation}
P(D_0=y_0)=\pi(y_0), \qquad y_0\in S\cdot
\end{equation}
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
\begin{equation}
P(C_n=y)=p^{(n)}_{x,y}, \qquad y\in S
\end{equation}
e
\begin{equation}
P(D_n=y)=\pi(y), \qquad y\in S
\end{equation}
Por conseguinte, temos que
\begin{equation}
\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
\end{equation}
e, portanto, a conclusão do Teorema 44 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\) tenho período 1 e
seja \(\pi\) a distribuição estacionária única concentrada em \(F\). Nestas condições concluímos que
\begin{equation}
\lim_{n\to\infty} p^{(n)}_{x,y}=\pi(y)=\dfrac{1}{m_y}, \qquad x,y\in F\cdot
\end{equation}
Em particular, se \(y\) é um estado recorrente positivo com período 1 então, sendo \(F\) o conjunto irredutível fechado que contém \(y\), vemos que
\begin{equation}
\lim_{n\to\infty} p^{(n)}_{y,y}=\dfrac{1}{m_y}\cdot
\end{equation}
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{equation}
\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}
\end{equation}
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
\begin{equation}
\lim_{m\to\infty} q^{(m)}_{y,y}=\dfrac{d}{m_y}=d\pi(y),
\end{equation}
e, portanto, que
\begin{equation}
\lim_{m\to\infty} p^{(md)}_{y,y}=d\pi(y), \qquad y\in S\cdot
\end{equation}
Sejam agora \(x\) e \(y\) um par de estados em \(S\) e seja
\begin{equation}
r_1=\min\{n: \, p^{(n)}_{x,y}>0\}\cdot
\end{equation}
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
\begin{equation}
p^{(r_1+n_1)}_{y,y}\geq p^{(n_1)}_{y,x}p^{(r_1)}_{x,y}>0,
\end{equation}
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
\begin{equation}
p^{(n)}_{x,y}=0 \; \mbox{a menos que} \; n=md+r,
\end{equation}
para algum inteiro não negativo \(m\). Segue então, da expressão acima e do Teorema II.5, que
\begin{equation}
p^{(md+r)}_{x,y} \, = \, \sum_{k=0}^m P_x(T_y=kd+r)p^{(m-k)d}_{y,y}\cdot
\end{equation}
Seja
\begin{equation}
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
\end{equation}
Então, para cada \(k\) fixo
\begin{equation}
\lim_{m\to\infty} a_m(k)=d\pi(y)\cdot
\end{equation}
Aplicando o Teorema da Convergência Dominada, concluímos que
\begin{equation}
\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}
\end{equation}
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 IV.12.
No exemplo de modelo de genes (Exemplo I.9) temos uma situação de cadeia periódica, como pode ser apreciado olhando a matriz de probabilidades de transição
\begin{equation*}
\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}
\end{equation*}
Pode ser observado também que esta é uma cadeia regular, devido a que
\begin{equation*}
\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}
\end{equation*}
do qual deduzimos que o período desta cadeia é \(d=2\). Não é difícil obter que
\begin{equation*}
\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}
\end{equation*}
Exemplo IV.13.
Seja \(S_n\) a soma dos resultados que se obtém al lançar um dado balanceado \(n\) vezes. Queremos encontrar
\begin{equation}
\lim_{n\to\infty} P(\{S_n \, \mbox{ser divisível por 7}\}) \cdot
\end{equation}
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,
\begin{equation}
\lim_{n\to\infty} P(C_n=0)=\dfrac{1}{7}\cdot
\end{equation}
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.
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
\begin{equation}
\pi\mathcal{P} =\pi,
\end{equation}
onde \(\mathcal{P}\) é 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}\).
Pode ser mostrado (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 menos 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
\begin{equation*}
\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
\end{equation*}
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
\begin{equation}
\pi(\mathcal{P}-\mbox{I}) \, = \, \pmb{0},
\end{equation}
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
\begin{equation}
\pi G=(0,0,\cdots,1)
\end{equation}
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
\begin{equation}
G^{-1}G=GG^{-1}=\mbox{I}\cdot
\end{equation}
A solução de \(\pi G=(0,0,\cdots,1)\) será então
\begin{equation}
\pi=(0,0,\cdots,1)G^{-1},
\end{equation}
que é facilmente visto ser a linha inferior da matriz \(G^{-1}\). Vejamos estes métodos em exemplos.
Exemplo IV.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 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{equation*}
\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}
\end{equation*}
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.
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.
Agora apresentamos a resolução 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 nesta situação não existe distribuição estacionária.
Exemplo IV.15 (Experimento de criação de plantas).
Um botânico está estudando uma certa variedade de planta que é monoecious (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 está 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 é:
\begin{equation}
S=\{ \{AA, AA\}, \{AA, Aa\}, \{AA, aa\}, \{Aa, Aa\}, \{Aa, aa\}, \{aa, aa\} \}\cdot
\end{equation}
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 7 ilustra a possível
herança à descendência deste estado.
Figura 7: Grafo de algumas probabilidades de transição no experimento de criação de plantas.
Cada seta que vai para baixo na Figura 7 é 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 ambos 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 é nula.
> steadyStates(ProbT)
AA, AA AA, Aa AA, aa Aa, Aa Aa, aa aa, aa
[1,] 1 0 0 0 0 0
[2,] 0 0 0 0 0 1
Percebemos que os estados recorrentes são estados absorventes, logo recorrentes nulos. Nestes casos a distribuição estacionária é também nula.
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
> c(0,0,0,0,0,1)%*%solve(G)
Error in solve.default(G) :
Lapack routine dgesv: system is exactly singular: U[5,5] = 0
Por último apresentamos mais um exemplo no qual a distribuição estacionária não existe.
Exemplo IV.16 (Ruína do jogador).
Suponha que dois jogadores \(A\) e \(B\) estão jogando um jogo um contra o outro. Seja \(p\) um determinado núúmero \((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\) é \(p\) e a probabilidade de que jogador \(B\) vai ganhar um Real do jogador
\(A\) é \(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\) são 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 vão 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 é favorável a ele; caso \(p < 1/2\) o jogo é
desfavorável a ele; e se \(p=1/2\) o jogo é 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\) atinge 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 coordenar \(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 estacioá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\).
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 with 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
Seja \(\{C_n\}_{n\ge 0}\) uma Cadeia de Markov em \(S\) com função de transição \(\mathcal{P}\). Mostre que
\begin{equation}
G_n(x,y)\le G_n(y,y), \; \forall n \quad \mbox{e para} \quad x,y\in S \cdot
\end{equation}
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.
Uma matriz de probabilidades de transição \(\mathcal{P}\) é dita ser duplamente estocástica e a soma por colunas é também 1, isto é, se
\begin{equation}
\sum_{x\in S} p_{_{x,y}}=1 \quad \forall y\in S\cdot
\end{equation}
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
\begin{equation*}
\pi(y)=\dfrac{1}{M+1}, \quad y\in S\cdot
\end{equation*}
Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2\}\) e matriz de probabilidades de transição
\begin{equation*}
\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}
\end{equation*}
Mostre que esta cadeia tem uma única distribuição estacionária \(\pi\) e encontre-a.
Seja \(\pi\) a distribuição estacionária de uma Cadeia de Markov. Prove que se \(\pi(x)>0\) e, se \(y\) é alcançável a partir de \(x\),
então \(\pi(y)>0\).
Seja \(\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
\begin{equation}
p_{x,y}=c \, p_{x,z}, \qquad x\in S\cdot
\end{equation}
Mostre que \(\pi(y)=c\pi(z)\).
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 é única.
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 é de
1/3 de que ele vai escolher a mesma marca que ele escolheu em sua compra anterior e a probabilidade é 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 é a probabilidade de que ambas: as seas primeira e segunda aquisições será
a marca A e ambas as terceira e quarta compras serão a marca B?
Um sistema consiste de dois componentes que operam em paralelo: o sistema funciona se pelo menos um dos componentes está operando. Em qualquer período, se
os dois componentes estão 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\). Há uma única oficina para
realizar os reparos e leva dois períodos para reparar um componente.
(a) Especifique a matriz de probabilidades de transição em termos de \(\alpha\) e \(\beta\).
(b) Caso \(\alpha=0.1\) e \(\beta=0.2\), num período longo prazo de tempo, qual é a probabilidade do sistema permanecer operacional?
Sejam \(\pi_0\) e \(\pi_1\) duas distribuições estacionárias distintas para uma Cadeia de Markov.
(a) Prove que para \(0\le \alpha\le 1\), a função \(\pi_\alpha\), definida como
\begin{equation*}
\pi_\alpha(x)=(1-\alpha)\pi_0(x)+\alpha\pi_1(x), \qquad x\in S,
\end{equation*}
é uma distribuição estacionária.
(b) 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\).
Uma partícula se move 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.
(a) Encontre a matriz de probabilidades de transição.
(b) Encontre a distribuição estacionária.
Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,2,\cdots\}\) e função de transição:
\begin{equation}
p_{0,j}=f_j \quad \mbox{e} \quad p_{j,j-1}=1,
\end{equation}
onde \(1=f_1+f_2+\cdots+f_j+\cdots\).
(a) Esboçar o grafo da matriz de transição.
(b) Determine se a cadeia é irredutível.
(c) Determine se o estado 0 é transiente, recorrente nulo ou recorrente positivo.
(d) Encontre a expressão da distribuição estacionária, se existir.
Considere uma Cadeia de Markov com espaço de estados \(S=\{1,2,\cdots\}\) e como função de transição a seguinte:
\begin{equation}
p_{j,j+1}=a_j \quad \mbox{e} \quad p_{j,1}=1-a_j, \quad 0< a_j < 1\cdot
\end{equation}
(a) Esboçar o grafo da matriz de transição.
(b) Determine se a cadeia é irredutível.
(c) Determine se o estado 1 é transiente, recorrente nulo ou recorrente positivo.
(d) Encontre a expressão da distribuição estacionária, se existir.
(e) Forneça respostas específicas aos itens (c) e (d) se:
