A informação mais frequentemente procurada num modelo deste tipo é a probabilidade de estar num determinado estado ou subconjunto de estados num determinado momento após o sistema se tornar operacional. Frequentemente, este tempo é considerado suficientemente longo para que toda a influência do estado inicial de partida tenha sido apagada. As probabilidades assim obtidas são designadas por probabilidades estacionárias ou de longo prazo. As probabilidades num determinado momento t são designadas probabilidades transitórias.
Quando o número de estados é pequeno, é relativamente fácil obter soluções transientes e estacionárias de forma rápida e exacta e, a partir delas, prever o comportamento do sistema. No entanto, à medida que os modelos se tornam mais complexos - e esta é cada vez mais a tendência - o processo de obtenção destas soluções torna-se muito mais difícil. É para este aspeto que o presente texto está orientado. O objetivo da introdução à Solução Numérica de Cadeias de Markov é explorar e explicar todos os aspectos da computação numérica de soluções de cadeias de Markov, especialmente quando o espaço de estados é enorme.
A matriz de transição, que descreve a progressão natural da cadeia, é o objetivo deste capítulo.
Queremos agora classificar os estados segundo a possibilidade de atingir cada estado a partir de qualquer outro. Uma vez classificados os estados, teremos como resultado as direções que pode tomar a cadeia com o passar do tempo.
Definição 2.1: Estado absorvente.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O estado \(a\in S\) é chamado de estado absorvente se \(p_{a,a}=1\) ou, equivalentemente, se \(p_{a,y}=0\), para todo \(y\neq a\).
Observemos que isto quer dizer que, um estado é absorvente se for um estado do qual a cadeia não pode fugir uma vez que chegou nele, por isso é chamado de estado absorvente, absorve a cadeia. Isto acontece no caso do Exemplo 1.6, o exemplo do Fast food, nesse caso o estado 4 é absorvente, isto devido a que \(p_{4,4}=1\).
Exemplo 2.1:
Vamos mostrar que se \(a\) é um estado absorvente, então \[ p^{(n)}_{x,a}=P_x(T_a\le n), \] para \(n\ge 1\).
Se \(a\) é um estado absorvente, então \(p^{(n-m)}_{a,a}=1\) se \(1\le m\le n\) e então \[ \begin{array}{rcl} p^{(n)}_{x,a} & = & \displaystyle \sum_{m=1}^n P_x(T_a=m)p^{(n-m)}_{a,a} \, = \, \displaystyle \sum_{m=1}^n P_x(T_a=m) \, = \, P_x(T_a\le n) \cdot \end{array} \]
Exemplo 2.2: Experiência de criação de plantas.
Continuando com o Exemplo 1.9, vamos observar a matriz de probabilidades de transição fornecida. Claramente temos dois estados absorventes: \(\{AA,AA\}\) e \(\{aa,aa\}\). A dúvida é se existe algum outro estado que seja absorvente, ou seja, pelo que demonstramos no Exemplo 1.6 se partirmos de qualquer estado \(x\), com probabilidade positiva vamos chegar à \(a\), o estado absorvente num tempo finito \(n\). Isto acontece nesta cadeia? com os seguintes comandos R vamos demonstrar que isso não acontece:
library(markovchain)
estados = c("{AA,AA}","{AA,Aa}","{AA,aa}","{Aa,Aa}","{Aa,aa}","{aa,aa}")
Prob.T=matrix(c(1,0,0,0,0,0,0.25,0.5,0,0.25,0,0,
0,0,0,1,0,0,0.0625,0.25,0.125,0.25,0.25,0.0625,
0,0,0,0.25,0.5,0.25,0,0,0,0,0,1),
nrow=6,ncol=6,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T,
name="Exemplo 1.9 - Experiência de criação de plantas")
ProbT## Exemplo 1.9 - Experiência de criação de plantas
## A 6 - dimensional discrete Markov Chain defined by the following states:
## {AA,AA}, {AA,Aa}, {AA,aa}, {Aa,Aa}, {Aa,aa}, {aa,aa}
## The transition matrix (by rows) is defined as follows:
## {AA,AA} {AA,Aa} {AA,aa} {Aa,Aa} {Aa,aa} {aa,aa}
## {AA,AA} 1.0000 0.00 0.000 0.00 0.00 0.0000
## {AA,Aa} 0.2500 0.50 0.000 0.25 0.00 0.0000
## {AA,aa} 0.0000 0.00 0.000 1.00 0.00 0.0000
## {Aa,Aa} 0.0625 0.25 0.125 0.25 0.25 0.0625
## {Aa,aa} 0.0000 0.00 0.000 0.25 0.50 0.2500
## {aa,aa} 0.0000 0.00 0.000 0.00 0.00 1.0000ProbT^100## Exemplo 1.9 - Experiência de criação de plantas^100
## A 6 - dimensional discrete Markov Chain defined by the following states:
## {AA,AA}, {AA,Aa}, {AA,aa}, {Aa,Aa}, {Aa,aa}, {aa,aa}
## The transition matrix (by rows) is defined as follows:
## {AA,AA} {AA,Aa} {AA,aa} {Aa,Aa} {Aa,aa} {aa,aa}
## {AA,AA} 1.00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 0.00
## {AA,Aa} 0.75 1.635836e-10 3.124169e-11 2.022004e-10 1.635836e-10 0.25
## {AA,aa} 0.50 2.499335e-10 4.773305e-11 3.089348e-10 2.499335e-10 0.50
## {Aa,Aa} 0.50 2.022004e-10 3.861685e-11 2.499335e-10 2.022004e-10 0.50
## {Aa,aa} 0.25 1.635836e-10 3.124169e-11 2.022004e-10 1.635836e-10 0.75
## {aa,aa} 0.00 0.000000e+00 0.000000e+00 0.000000e+00 0.000000e+00 1.00Podemos utilizar a função absorbingStates, no pacote R de funções markovchain, para identificar os estados absorventes:
absorbingStates(ProbT)## [1] "{AA,AA}" "{aa,aa}"A pergunta que fica é: como é possível identificar de maneira automática quais estados são absorventes? a resposta será dada na Seção 3.1.1, na qual apresentamos o algoritmo de melhor sucesso na identificação desses estados e de outros que serão estudados posteriormente.
Observe que \[ P_x(T_y=1)=P_x(C_1=y)=p_{x,y}, \] e que \[ P_x(T_y=2)=\sum_{z\neq y} P_x(C_1=z,C_2=y)=\sum_{z\neq y} p_{x,z}p_{z,y} \cdot \]
Na situação de altos valores de \(n\), as probabilidades \(P_x(T_y=n)\) podem ser encontradas utilizando a expressão \[ P_x(T_y=n+1)=\sum_{z\neq y} p_{x,z}P_z(T_y=n) \] caso \(n\ge 1\).
Para chegar ao estado \(y\) partindo do estado \(x\), pela primeira vez no tempo \(n+1\), é necessário ir a algum estado \(z\neq y\) num primeiro passo e então ir do estado \(z\) ao estado \(y\) pela primeira vez no final de \(n\) passos adicionais.
Definição 2.2: Estados recorrentes e transientes.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). O estado \(y\in S\) é chamado de recorrente se \(\rho_{y,y}=1\) caso contrário, isto é, se \(\rho_{y,y}<1\) o estado \(y\) é chamado de transiente.
Se o estado \(y\) for recorrente, a Cadeia de Markov partindo de \(y\) retorna a \(y\) com probabilidade 1. Se o estado \(y\) for transiente, a Cadeia de Markov partindo de \(y\) tem probabilidade positiva \(1-\rho_{y,y}\) de nunca voltar ao estado \(y\). Se \(y\) for um estado absorvente, então \(P_y(T_y=1)=p_{y,y}=1\) e, então \(\rho_{y,y}=1\), portanto um estado absorvente é necessariamente recorrente.
Definição 2.3.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). Definimos a variável aleatória \(N(y)\) como o número de vezes \(n\ge 1\), que a cadeia está no estado \(y\in S\).
A variável aleatória indicadora foi definida anterioemente e utilizando-a, vemos que \(\pmb{1}_y(C_n)=1\) se a cadeia está no estado \(y\) no tempo \(n\) e \(\pmb{1}_y(C_n)=0\) caso contrário, vemos que \[ N(y)=\sum_{n=1}^\infty 1_y(C_n) \cdot \] Também observamos que o evento \(\{N(y)\ge 1\}\) é o mesmo do que o evento \(\{T_y<\infty\}\). Então \[ P_x(N(y)\ge 1)=P_x(T_y<\infty)=\rho_{x,y} \cdot \]
Sejam \(m\) e \(n\) dois números inteiros positivos. Sabemos que a probabilidade com a qual a Cadeia de Markov, começando em \(x\) visitar pela primeira vez o estado \(y\) no tempo \(m\) e visitar novamente \(y\), \(n\) unidades de tempo depois é \[ P_x(T_y=m)P_y(T_y=n)\cdot \]
Então, \[ \begin{array}{rcl} P_x\big(N(y)\ge 2\big) & = & \displaystyle \sum_{m=1}^\infty \sum_{n=1}^\infty P_x(T_y=m)P_y(T_y=n) \\[0.6em] & = & \displaystyle \left[\sum_{m=1}^\infty P_x(T_y=m)\right]\left[\sum_{m=1}^\infty P_y(T_y=n)\right] \\ & = & \rho_{x,y}\rho_{y,y} \cdot \end{array} \] Similarmente, concluímos que \[ P_x(N(y)\ge m)=\rho_{x,y}\rho_{y,y}^{m-1}, \qquad m\ge 1\cdot \]
Agora estamos em condições de encontrar a expressão da probabilidade de que uma cadeia visite um estado um determinado número de vezes. Como veremos posteriormente, utilizando estas relações vamos obter resultados mais poderosos que nos permitirão encontrar as probabilidades de atingirmos um determinado estado.
Teorema 2.1.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). Então \[ P_x(N(y)=m)=\rho_{x,y}\rho_{y,y}^{m-1}(1-\rho_{y,y}), \qquad m\ge 1\cdot \]
Demonstração.
Observemos que \[ P_x\big(N(y)=m\big)=P_x\big(N(y)\ge m\big)-P_x\big(N(y)\ge m+1\big)\cdot \]Também, \[ P_x\big(N(y)=0\big)=1-P_x\big(N(y)\ge 1\big), \] de maneira que \[ P_x\big(N(y)=0\big)=1-\rho_{x,y}\cdot \]
Para perceber porque o resultado do teorema deve ser verdade observemos, por exemplo, que uma cadeia começando em \(x\) visita o estado \(y\) exatamente \(m\) vezes se, e somente se, a cadeia visita ao estado \(y\) por uma primeira vez, retorna a \(y\) \(m-1\) vezes adicionais e depois nunca mais volta a \(y\).
Definição 2.4
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Definimos por \(\mbox{E}_x(C_n)\) a esperança da variável aleatória \(C_n\) na cadeia começando no estado \(x\).
Por exemplo, \[ \mbox{E}_x\big(1_y(C_n)\big)=P_x(C_n=y)=p^{(n)}_{x,y}\cdot \] Segue da expressão acima que \[ \begin{array}{rcl} \mbox{E}_x\big(N(y)\big) & = & \displaystyle \mbox{E}_x\left(\sum_{n=1}^\infty 1_y(C_n)\right) \, = \, \displaystyle \sum_{n=1}^\infty \mbox{E}_x\left(1_y(C_n)\right) \, = \, \displaystyle \sum_{n=1}^\infty p^{(n)}_{x,y}, \end{array} \] sendo que \[ \mbox{E}_x\big(N(y)\big)=\sum_{n=1}^\infty p^{(n)}_{x,y}, \] constitui uma forma prática para encontrar o número esperado de vezes que a cadeia visita o estado \(y\) partindo do estado \(x\).
Exemplo 2.3: Fast food.
Lembremos o Exemplo 1.6: Fast food. Vamos verificar se hexistem estados absorventes, transientes e recorrentes e vamos identificá-los:
estados = c("0","1","2","3","4")
Prob.T=matrix(c(0,1,0,0,0,0,1/4,3/4,0,0,
0,0,1/2,1/2,0,0,0,0,3/4,1/4,0,0,0,0,1),
nrow=5,ncol=5,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T, name="Fast food")
absorbingStates(ProbT)## [1] "4"Podemos utilizar as funções transientStates e recurrentStates, no pacote R de funções markovchain, para identificarmos quais estados são transientes e quais recorrentes. Da mesma forma que dizemos anteriormente, vamos responder o porquê estas funções funcionam na Seção 3.1.1, na qual apresentamos o algoritmo de melhor sucesso na identificação desses estados e de outros que serão estudados posteriormente.
transientStates(ProbT)## [1] "0" "1" "2" "3"recurrentStates(ProbT)## [1] "4"Observe que aqui acontece o comentádo após a Definição 2.4, todo estado absorvente é recorrente e, nesta situação, o estado absorvente é o único estado recorrente.
Encontremos agora o número esperado de vezes que a cadeia assume o valor 1 partido de 1. Utilizando a expressão \[ \mbox{E}_1\big(N(1)\big)=\sum_{n=1}^\infty p^{(n)}_{1,1}, \] temos que \(\mbox{E}_1\big(N(1)\big)=0.3333333\). Por outro lado \(\mbox{E}_1\big(N(2)\big)=2\). Como foram obtidos estes números?
Utilizando a linguagem de programação R podemos fazer os cálculos necessários para encontrar \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in S\). Com os comandos mostrados acima, introduzimos a forma de construir a matriz de probabilidades de transição para sua posterior utilização em nossos cálculos.
No Exemplo 2.2 aprendemos a encontrar as probabilidades \(p^{(n)}_{x,y}\), qualquer seja o valor finito de \(n\). Agora necessitamos mais um passo, somar essas probabilidades. Para isso definimos a função Soma, de argumentos a matriz \(\mathcal{P}\) e o número de somas.
Soma = function(M,n=10){ mm=0; for(i in 1:n){mm=mm+(M^i)[]}; mm}Obtemos por resultado uma matriz que constitui uma boa aproximação de \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in S\) e que justifica os valores anteriormente apresentados de \(\mbox{E}_1\big(N(1)\big)\) e \(\mbox{E}_1\big(N(2)\big)\).
Assim
Soma(ProbT,60)## 0 1 2 3 4
## 0 0 1.3333333 2 4 52.66667
## 1 0 0.3333333 2 4 53.66667
## 2 0 0.0000000 1 4 55.00000
## 3 0 0.0000000 0 3 57.00000
## 4 0 0.0000000 0 0 60.00000Um detalhe interessante é que se aumentarmos o número de somas, os valores de \(\mbox{E}_x\big(N(y)\big)\), \(\forall x,y\in\{0,1,2,3\}\) não mudam.
Soma(ProbT,80)## 0 1 2 3 4
## 0 0 1.3333333 2 4 72.66667
## 1 0 0.3333333 2 4 73.66667
## 2 0 0.0000000 1 4 75.00000
## 3 0 0.0000000 0 3 77.00000
## 4 0 0.0000000 0 0 80.00000Podemos afirmar então que o número esperado de vezes que a cadeia visita o estado 3 partindo de 0 é \(\mbox{E}_0\big(N(3)\big)=4\).
Qual será o número médio de refeições necessárias para completar a coleção?
A resposta é indireta, no sentido de que seriam necessárias, pelo menos 8 \[ \mbox{E}_0\big(N(1)\big) \, + \, \mbox{E}_0\big(N(2)\big) \, + \, \mbox{E}_0\big(N(3)\big) \] refeições para completar a coleção.
Teorema 2.2.
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Temos duas situações:
Se \(y\in S\) for transiente, então \(P_x\big(N(y)<\infty\big)=1\) e \[ \mbox{E}_x\big(N(y)\big)=\dfrac{\rho_{x,y}}{1-\rho_{x,y}}, \] a qual é finita \(\forall x\in S\).
Se \(y\in S\) for recorrente, então \(P_y\big(N(y)=\infty\big)=1\) e \(\mbox{E}_y\big(N(y)\big)=\infty\). Também \[ P_x\big(N(y)=\infty\big)=P_x(T_y<\infty)=\rho_{x,y}, \qquad x\in S \cdot \] Se \(\rho_{x,y}=0\), então \(\mbox{E}_x\big(N(y)\big)=0\), enquanto se \(\rho_{x,y}>0\), \(\mbox{E}_x\big(N(y)\big)=\infty\).
Demonstração.
Seja \(y\) um estado transiente. Dado que \(0\le\rho_{y,y}<1\), segue que \[ P_x\big(N(y)=\infty\big)=\lim_{m\to\infty} P_x\big(N(y)\ge m\big)=\lim_{m\to\infty} \rho_{x,y}\rho_{y,y}^{m-1}=0\cdot \] Agora, \[ \mbox{E}_x\big(N(y)\big) \, = \, \displaystyle \sum_{m=1}^\infty mP_x\big(N(y)=m\big) \, = \, \displaystyle \sum_{m=1}^\infty m\rho_{x,y}\rho_{y,y}^{m-1}(1-\rho_{y,y}) \cdot \] Observemos que \(\displaystyle \mbox{E}_x\big(N(y)\big)=\rho_{x,y}(1-\rho_{y,y})\sum_{m=1}^\infty m\rho_{y,y}^{m-1}\), e que a série de potências na expressão anterior é convergente, de soma \[ \sum_{m=1}^\infty m\rho_{y,y}^{m-1}=\dfrac{1}{(1-\rho_{y,y})^2}, \] do qual concluímos que \[ \mbox{E}_x\big(N(y)\big)=\dfrac{\rho_{x,y}}{1-\rho_{x,y}}, \] e provamos o item 1. Seja agora \(yK\) um estado recorrente. Então \(\rho_{y,y}=1\) e segue que \[ \begin{array}{rcl} P_x\big(N(y)=\infty\big) & = & \displaystyle \lim_{m\to\infty} P_x\big(N(y)\ge m\big) \\[0.8em] & = & \displaystyle \lim_{m\to\infty} \rho_{x,y}=\rho_{x,y}\cdot \end{array} \] Em particular, \(P_y\big(N(y)=\infty\big)=1\). Se uma variável aleatória não negativa tem probabilidade positiva de ser infinita, então sua esperança é infinita. Logo \[ \mbox{E}_y\big(N(y)\big)=\infty\cdot \] Se \(\rho_{x,y}=0\), então \(P_x\big(T_y=m\big)=0\) para todo inteiro positivo finito \(m\), implica que \(p^{(n)}_{x,y}=0\), para \(n\ge 1\) e, portanto, \(\mbox{E}_x\big(N(y)\big)=0\) neste caso. Se \(\rho_{x,y}>0\), então \(P_x\big(N(y)=\infty\big)=\rho_{x,y}>0\) e, por isso, \(\mbox{E}_x\big(N(y)\big)=\infty\).Este teorema descreve a diferença fundamental entre um estado transiente e um estado recorrente. Se \(y\) é um estado transiente, então não importa onde a Cadeia de Markov começou, ela fará apenas um número finito de visitas a \(y\) e o número esperado de visitas ao \(y\) é finito. Suponha, ao invés disso, que \(y\) seja um estado recorrente. Se a Cadeia de Markov começa em \(y\), ela voltará ao \(y\) infinitas vezes. Se a cadeia começa em algum outro estado \(x\), pode ser impossível para ela sempre atingir \(y\). Se for possível, no entanto, e a cadeia não visitar \(y\) pelo menos uma vez, então o fará infinitamente vezes.
Definição 2.5: Cadeia transiente.
Uma Cadeia de Markov \(\{C_n\}\) é chamada de cadeia transiente se todos os seus estados forem estados transientes.
Exemplo 2.4
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(\mathbb{N}\), os números naturais e probabilidades de transição \(p_{x,x+1}=3/4\) e \(p_{x,x-1}=1/4\), \(\forall x\in\mathbb{N}\). Demonstremos que esta é uma cadeia transiente.
Uma das formas de percebermos que esta é uma cadeia transiente será observando que \[ C_n=C_0+\xi_1+\cdots+\xi_n, \] onde \(\xi_i=1\) com probabilidade 3/4 e \(\xi_i=-1\) com probabilidade 1/4, \(i=1,\cdots\).
Estas podem ser consideradas como os resultados dos lançamentos de moedas viciadas, constituindo variáveis aleatórias independentes e igualmente distribuídas.
Pela Lei dos Grandes Números temos que \(C_n/n\) converge para \(\mbox{E}(C_n)\), quando \(n\to\infty\). Desde que \(\mbox{E}(C_n)=1/2\), então \(C_n/n\to 1/2\), quando \(n\to\infty\). Isto significa que não podemos visitar qualquer estado infinitas vezes.
Teorema 2.3.
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). Então, se o espaço de estados \(S\) for finito a cadeia deve ter pelo menos um estado recorrente e, portanto, não pode ser uma cadeia transiente.
Demonstração.
Corolário 2.4.
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). Se \(y\in S\) for um estado transiente, então \[ \lim_{n\to\infty} p_{x,y}^{(n)}=0\cdot \]
Demonstração.
Exemplo 2.5
Considere uma Cadeia de Markov com matriz de transição: \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 1 \quad & \;\, 2 \; & \quad 3 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} & \begin{pmatrix} \; 1/3 \, & \; 1/3 \; & \; 1/3 \; \\ \; 1/4 \; & \; 3/4 & 0 \\ \; 0 \; & \; 0 & 1 \end{pmatrix}\cdot \end{matrix} \] Queremos encontrar \(P_1(T_1<\infty)\) e \(P_1(T_2<\infty)\).
Devemos observar que o Corolário 2.11 permite-nos caracterizar os estados transientes. Observemos que \[ \mathcal{P}^{1000}=\begin{pmatrix} 2.703815e^{-48} & 6.103413e^{-48} & 1 \\ 4.577560e^{-48} & 1.033308e^{-47} & 1 \\ 0 & 0 & 1 \end{pmatrix}, \] com o qual fica claro que os estados 1 e 2 são transientes e o estado 3 é absorvente, portanto, recorrente.
Também, te mos que \(\mbox{E}_1\big(N(1)\big)=1/2\) e \(\mbox{E}_1\big(N(2)\big)=1/3\). Agora, pelo Teorema 2.2 chegamos a que \(\rho_{1,1}=1/3\) e \(\rho_{1,2}=1/4\).
Definição 2.6: Cadeia recorrente.
Uma Cadeia de Markov \(\{C_n\}\) é chamada de cadeia recorrente se todos os seus estados forem estados recorrentes.
Exemplo 2.6: Fast food.
Observemos que nesta situação os estados 0, 1, 2 e 3 são transientes e o estado 4 é recorrente. Logo, este é um exemplo de uma cadeia que não é recorrente nem transiente. Ainda podemos observar em quais estados \[ \displaystyle \lim_{n\to\infty} p_{x,y}^{(n)}=0 \] e, termos assim, mais uma caracterização de estados transientes.
ProbT^100## Fast food^100
## A 5 - dimensional discrete Markov Chain defined by the following states:
## 0, 1, 2, 3, 4
## The transition matrix (by rows) is defined as follows:
## 0 1 2 3 4
## 0 0 2.489206e-60 4.733165e-30 1.282881e-12 1
## 1 0 6.223015e-61 2.366583e-30 9.621607e-13 1
## 2 0 0.000000e+00 7.888609e-31 6.414404e-13 1
## 3 0 0.000000e+00 0.000000e+00 3.207202e-13 1
## 4 0 0.000000e+00 0.000000e+00 0.000000e+00 1Percebemos com este exemplo que nem todas as cadeias devem ser ou transientes ou recorrentes. Pelo Teorema 2.3 sabemos que cadeias transientes, se existirem, devem ter espaço de estados infinito. O seguinte exemplo nos mostra que cadeias recorrentes existem.
Exemplo 2.7: Compras de pasta de dentes.
Consideramos um cliente que escolhe entre duas marcas de pasta de dentes \(A\) ou \(B\), em várias ocasiões. Vamos considerar \(C_n=A\) se o cliente escolhe a marca \(A\) na \(n\)-ésima compra e \(C_n=B\), se o cliente escolhe a marca \(B\) na \(n\)-ésima compra. Nesta situação, a sequência de estados \(C_1,C_2,\cdots\) constitui um processo estocástico com dois estados possíveis em cada tempo.
As probabilidades de compra foram especificadas, dizendo que o cliente vai escolher a mesma marca que na compra anterior com probabilidade 1/3 e vai mudar de marca com probabilidade 2/3. Desde que isso acontece independentemente das compras anteriores, vemos que este processo estocástico é uma Cadeia de Markov estacionária com matriz de transição \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & \;\, B \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} A \\ B \end{matrix} & \begin{pmatrix} \; 1/3 \, & \; 2/3 \; \\ \; 2/4 \; & \; 1/3 \end{pmatrix}\cdot \end{matrix} \] Este é um exemplo de Cadeia de Markov recorrente, devido a que os estados \(A\) e \(B\) são ambos recorrentes.
Para verificar esta afirmação utilizamos a função Soma, obtendo-se
Soma(ProbT,1000)## 0 1 2 3 4
## 0 0 1.3333333 2 4 992.6667
## 1 0 0.3333333 2 4 993.6667
## 2 0 0.0000000 1 4 995.0000
## 3 0 0.0000000 0 3 997.0000
## 4 0 0.0000000 0 0 1000.0000ou ainda
Soma(ProbT,3000)## 0 1 2 3 4
## 0 0 1.3333333 2 4 2992.667
## 1 0 0.3333333 2 4 2993.667
## 2 0 0.0000000 1 4 2995.000
## 3 0 0.0000000 0 3 2997.000
## 4 0 0.0000000 0 0 3000.000Isto mostra que \[ \mbox{E}_A\big(N(A)\big) \, = \, \mbox{E}_A\big(N(B)\big) \, = \, \mbox{E}_B\big(N(A)\big) \, = \, \mbox{E}_B\big(N(B)\big) \, = \, \infty\cdot \] Logo, os estados desta cadeia são recorrentes, pelo Teorema 2.2, item ii.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e função de transição \(p\). Vamos mostrar aqui como diversas probabilidades condicionais podem ser expressas em termos de \(p\) e definiremos também a função de transição em \(m\) passos da Cadeia de Markov.
Teorema 2.5.
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de trnasição \(\mathcal{P}=\big(p_{x,y}\big)\). Então \[ P\big(C_{n+1}=c_{_{n+1}},\cdots,C_{n+m}=c_{_{n+m}} \, | \, C_{0}=c_{_{0}},\cdots,C_{n}=c_{_{n}}\big) \, = \, p_{c_{_{n}},c_{_{n+1}}}\cdots p_{c_{_{n+m-1}},c_{_{n+m}}}\cdot \]
Demonstração.
Para demonstrar esta relação, utilizamos a definição de probabilidade condicional na parte esquerda como \[ \dfrac{P\big(C_0=c_{_{0}},\cdots, C_{n+m}=c_{_{n+m}}\big)}{P\big(C_0=c_{_{0}},\cdots,C_n=c_{_{n}} \big)} \, = \, \dfrac{\pi_0(c_{_0})p_{c_{_{0}},c_{_{1}}}\cdots p_{c_{_{n+m-1}},c_{_{n+m}}}}{\pi_0(c_{_0})p_{c_{_{0}},c_{_{1}}}\cdots p_{c_{_{n-1}},c_{_{n}}}}, \] do qual deduzimos a expressão à direita acima.Escrevendo convenientemente o resultado do Teorema 1.2 temos que \[ P\big( C_{n+1}=y_{_{1}}, \cdots, C_{n+m}=y_{_{m}} \, | \, C_0=c_{_{0}}, \cdots, C_{n-1}=c_{_{n-1}},C_n=x\big) \, = \, p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \] Utilizemos este resultado para provar uma propriedade mais geral. Consideremos \(\mathcal{A}_0,\mathcal{A}_1,\cdots,\mathcal{A}_{n-1}\) subconjuntos do espaço de estados \(S\). Segue então, da expressão acima, que \[ P\big( C_{n+1}=y_{_{1}}, \cdots, C_{n+m}=y_{_{m}} \, | \, C_0\in\mathcal{A}_0, \cdots, C_{n-1}\in\mathcal{A}_{n-1},C_n=x\big) \, = \, p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \]
Mais ainda, se \(\mathcal{B}_1,\cdots,\mathcal{B}_m\) forem subconjuntos de \(S\), segue que \[ \begin{array}{l} P\big( C_{n+1}\in\mathcal{B}_1, \cdots, C_{n+m}\in\mathcal{B}_m \, | \, C_0\in\mathcal{A}_0, \cdots, C_{n-1}\in\mathcal{A}_{n-1},C_n=x\big) \, = \\[0.8em] \displaystyle \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad = \sum_{y_{_{1}}\in\mathcal{B}_1}\cdots\sum_{y_{_{m}}\in\mathcal{B}_m} p_{x,y_{_{1}}}p_{y_{_{1}},y_{_{2}}}\cdots p_{y_{_{m-1}},y_{_{n}}}\cdot \end{array} \]
Definição 2.7.
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de transição \(\mathcal{P}=\big(p_{x,y}\big)\). A função de transição em \(m\)-passos \(p_{x,y}^{(m)}\), a qual fornece a probabilidade de transição do estado \(x\) ao estado \(y\) em \(m\) passos, define-se como \[ p_{x,y}^{(m)} \, = \, \displaystyle \sum_{y_{_1}}\cdots\sum_{y_{_{m-1}}} p_{x,y_{_1}}p_{y_{_1},y_{_2}}\cdots p_{y_{_{m-2}},y_{_{m-1}}}p_{y_{_{m-1}},y}, \] para \(m\geq 2\), como \(p_{x,y}^{(1)}=p_{x,y}\) e como \[ p_{x,y}^{(0)} \, = \, \left\{ \begin{array}{cc} 1, & \mbox{se} \; x=y \\ 0, & \mbox{caso contrário} \end{array}\right.\cdot \]
Exemplo 2.8: Fila de servidor único.
Um gerente normalmente verifica o vendedor em sua loja a cada 5 minutos para ver se está ocupado ou não. Ele modela o estado do vendedor como 1 se está ocupado ou 2 caso não esteja ocupado. Consideremos a sequência de estados resultantes nas verificações como uma Cadeia de Markov com dois estados possíveis e função de transição estacionária dada pela seguinte matriz: \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; Ocupado \; & \quad Não \; ocupado \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} Ocupado \\ Não \; ocupado \end{matrix} & \begin{pmatrix} \qquad 0.9 \qquad & \qquad 0.1 \qquad \\ 0.6 & 0.4 \end{pmatrix}, \end{matrix} \]
O gerente percebe que, no final do dia, estará afastado por 10 minutos e vai perder uma vistoria do vendedor. Ele quer calcular a distribuição condicional dois períodos de tempo no futuro dado cada um dos estados possíveis.
O raciocínio é da seguinte forma: se \(C_n = 1\), por exemplo, o estado terá que ser 1 ou 2 no tempo \(n + 1\), mesmo que ele não se importe agora sobre o estado no tempo \(n + 1\). Mas, se ele calcula a distribuição condicional conjunta de \(C_{n+1}\) e \(C_{n+2}\) dado \(C_{n}= 1\), ele pode somar sobre os possíveis valores de \(C_{n+1}\) para obter a distribuição condicional de \(C_{n+2}\) dado \(C_n=1\).
Em símbolos, \[ \begin{array}{l} P(C_{n+2}=1 \, | \, C_n=1) \, = \, P(C_{n+2}=1, \, C_{n+1}=1 \, | \, C_n=1) \, + \\[0.8em] \displaystyle \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + P(C_{n+2}=1, \, C_{n+1}=2 \, | \, C_n=1)\cdot \end{array} \]
Pelo Teorema 2.1 temos que \[ \begin{array}{l} P(C_{n+2}=1, \, C_{n+1}=1 \, | \, C_n=1) \, = \\[0.8em] \displaystyle \qquad \qquad \qquad \qquad P(C_{n+1}=1 \, | \, C_n=1)\times P(C_{n+2}=1 \, | \, C_{n+1}=1) \, = \, 0.9\times 0.9 \, = \, 0.81\cdot \end{array} \] Similarmente \[ \begin{array}{l} P(C_{n+2}=1, \, C_{n+1}=2 \, | \, C_n=1) \, = \\[0.8em] \displaystyle \qquad \qquad \qquad \qquad P(C_{n+1}=2 \, | \, C_n=1)\times P(C_{n+2}=1 \, | \, C_{n+1}=2) \, = \, 0.1\times 0.6 \, = \, 0.06\cdot \end{array} \]
Segue que \[ P(C_{n+2}=1 \, | \, C_n =1) \, = \, 0.81+0.06=0.87 \] e, portanto, \[ P(C_{n+2}=2 \, | \, C_{n}=1) \, = \, 1-0.87=0.13\cdot \] De maneira similar, se \(C_n=2\), \[ P(C_{n+2}=1 \, | \, C_n=2) \, = \, 0.06\times 0.9+0.4\times 0.6 \, = \, 0.78 \] e \[ P(C_{n+2}=2 \, | \, C_n=2) \, = \, 1-0.78 \, = \, 0.22\cdot \]
Estes cálculos podem ser feitos também utilizando a Definição 2.1. Assim, \[ p_{1,2}^{(2)} \, = \, p_{1,1}p_{1,2}+p_{1,2}p_{2,2} \, = \, 0.9\times 0.1+0.1\times 0.4 \, = \, 0.09+0.04 \, = \, 0.13 \] e \[ p_{2,2}^{(2)} \, = \, p_{2,1}p_{1,2}+p_{2,2}p_{2,2} \, = \, 0.6\times 0.1+0.4\times 0.4 \, = \, 0.06+0.16 \, = \, 0.22\cdot \]
Podemos utilizar expressões anteriores para esclarecer ainda o conceito de função de transição em \(m\) passos. Escolhendo \(\mathcal{B}_1,\cdots,\mathcal{B}_{m-1}=S\) e \(\mathcal{B}_m=\{y\}\) segue que \[ P(C_{n+m}=y \, | \, C_0\in \mathcal{A}_0,\cdots,C_{n-1}\in\mathcal{A}_{n-1}, C_n=x ) \, = \, p_{x,y}^{(m)}\cdot \] Em particular, assumindo \(\mathcal{A}_0,\cdots,\mathcal{A}_{n-1}=S\), vemos que \(P(C_{n+m}=y \, | \, C_n=x)=p_{x,y}^{(m)}\).
Teorema 2.6: Chapman–Kolmogorov.
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária, \(S\) o espaço de estados e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Então, a probabilidade de transição em \(n+m\) passos pode ser escrita em termos das probabilidades de transição em \(m\) passos como \[ p_{x,y}^{(n+m)} \, = \, \sum_{z\in S} p_{x,z}^{(n)}p_{z,y}^{(m)}\cdot \]
Demonstração.
Observemos que \[ P(C_{n+m}=y \, | \, C_0=x, C_n=z) \, = \, p_{z,y}^{(m)}\cdot \] Dado que \[ \begin{array}{rcl} p_{z,y}^{(m)} & = & P(C_{n+m}=y \, | \, C_0=x) \\ & = & \displaystyle \sum_{z\in S} P(C_n=z \, | \, C_0=x)\times P(C_{n+m}=y \, | \, C_0=0, C_n=z) \\ & = & \displaystyle \sum_{z\in S} p_{x,z}^{(n)} P(C_{n+m}=y \, | \, C_0=x, C_n=z)\cdot \end{array} \]E em termos da distribuição inicial? como escrever a distribuição de \(C_n\) em termos da distribuição inicial \(\pi_0\) e da probabilidade em \(n\)-passos? A resposta é fornecida pelo seguinte teorema.
Teorema 2.7.
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Então, podemos escrever a distribuição de \(C_n\) da seguinte maneira \[ P(C_n=y) \, = \, \sum_{x\in S} \pi_0(x)p_{x,y}^{(n)}\cdot \]
Demonstração.
Um método alternativo de calcularmos a distribuição de \(C_n\) é obtido da seguinte maneira. Observe que \[ P(C_{n+1}=y) \, = \, \displaystyle \sum_{x\in S} P(C_n=x, C_{n+1}=y) \, = \, \sum_{x\in S} P(C_n=x)\times P(C_{n+1}=y \, | \, C_n=x), \] do qual obtemos que \[ P(C_{n+1}=y) \, = \, \sum_{x\in S} P(C_n=x)p_{x,y}\cdot \]
Se conhecemos a distribuição de \(C_0\), podemos usar o resultado acima para encontrar a distribuição de \(C_1\). Em seguida, sabendo a distribuição de \(C_1\), utilizamos o resultado acima novamente para encontrar a distribuição de \(C_2\). Da mesma forma, podemos encontrar a distribuição de \(C_n\) aplicando \(n\) vezes este resultado.
Generalizando os cálculos no Exemplo 2.1 a três ou mais transições pode parecer entediante. No entanto, quando se examinam os cálculos com cuidado, vê-se um padrão que vai permitir um cálculo compacto das probabilidades de transição para diversas etapas. Considere uma Cadeia de Markov estacionária com \(N\) estados possíveis \(1,\cdots,N\) e matriz de transição \(\mathcal{P}=\big(p_{x,y}\big)\).
Assumindo-se que a cadeia está no estado \(x\) num determinado momento \(n\), vamos agora determinar a probabilidade de que a cadeia irá estar no estado \(y\) no tempo \(n+2\). Em outras palavras, vamos determinar a probabilidade condicional \[ (C_{n+2}=y \, | \, C_n=x)\cdot \] A notação para esta probabilidade é \(p_{x,y}^{(2)}\).
Argumentamos o que o gerente fez no Exemplo 2.1. Seja \(r\) o valor de \(C_{n+1}\) que não é de interesse primordial, mas será útil para o cálculo. Depois \[ \begin{array}{rcl} p_{x,y}^{(2)} & = & P(C_{n+2}=y \, | \, C_n=x) \, = \, \displaystyle \sum_{r=1}^N P(C_{n+1}=r, C_{n+2}=y \, | \, C_n=x) \\ & = & \displaystyle \sum_{r=1}^N P(C_{n+1}=r \, | \, C_n=x)\times P(C_{n+2}=y \, | \, C_{n+1}=r) \, = \, \sum_{r=1}^N p_{x,r}p_{r,y}, \end{array} \] em que a terceira igualdade segue do Teorema 2.1 e a quarta igualdade segue a partir da defnição de uma Cadeia de Markov estacionária.
O valor de \(p_{x,y}^{(2)}\) pode ser determinado da seguinte maneira: se a matriz de transição \(\mathcal{P}\) é elevada ao quadrado, ou seja, se a matriz \(\mathcal{P}^2=\mathcal{P}\times \mathcal{P}\) for calculada, o elemento da fila \(x\) e coluna \(y\) da matriz \(\mathcal{P}\) será \[ \sum_{r=1}^N p_{x,r}p_{r,y}\cdot \] Portanto, \(p_{x,y}^{(2)}\) será o elemento da fila \(x\) e a coluna \(y\) de \(\mathcal{P}^2\).
Por um argumento semelhante, a probabilidade de que a cadeia vai passar do estado \(x\) para o estado \(y\) em três etapas ou \(p_{x,y}^{(3)}=P(C_{n+3}=y \, | \, C_n=x)\), pode ser encontrada através da construção da matriz \(\mathcal{P}^3=\mathcal{P}^2\mathcal{P}\). A probabilidade \(p_{x,y}^{(3)}\) será o elemento da fila \(x\) com a coluna \(y\) da matriz \(\mathcal{P}^3\). Em geral, temos o seguinte resultado.
Teorema 2.8.
Seja \(\{C_n \, : \, n\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) finito e matriz de transição \(\mathcal{P}=\big(p_{x,y}\big)\). Para cada \(m=2,3,\cdots\) a \(m\)-ésima potência \(\mathcal{P}^m\) da matriz \(\mathcal{P}\) tem na linha \(x\) e coluna \(y\) a probabilidade \(p_{x,y}^{(m)}\), a probabiilidade da cadeia passar do estado \(x\) para o estado \(y\) em \(m\) passos.
Demonstração.
Exercício.Em resumo, a linha \(x\) da matriz de trnasição em \(m\)-passos fornece a distribuição condicional de \(C_{n+m} \, | \, C_n=x\) para todo \(x=1,2,\cdots,N\) e todos os \(n,m=1,2,\cdots\).
Exemplo 2.9.
Continuando com o Exemplo 1.1, utilizando o Teorema 2.4, podemos calcular \[ \mathcal{P}^2 \, = \, \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix}\times \begin{pmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{pmatrix} \, = \, \begin{pmatrix} 0.87 & 0.13 \\ 0.78 & 0.22 \end{pmatrix}\cdot \]
Uma outra forma de fazer os cálculos será utilizando um dos pacotes de funções disponíveis na linguagem de programação R:
print(citation(), style = "text")## R Core Team (2025). _R: A Language and Environment for Statistical
## Computing_. R Foundation for Statistical Computing, Vienna, Austria.
## <https://www.R-project.org/>.version[['version.string']]## [1] "R version 4.5.1 (2025-06-13)"Utilizaremos o pacote de funções markovchain:
print(citation("markovchain"), style = "text")## Spedicato G (2017). "Discrete Time Markov Chains with R." _The R
## Journal_, *9*(2), 84-104.
## <https://journal.r-project.org/archive/2017/RJ-2017-036/index.html>.Definimos a matriz de probabilidades de transição como:
estados = c("Ocupado","Não ocupado")
Prob.T=matrix(c(0.9,0.1,0.6,0.4),nrow=2, ncol=2,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T, name="Fila de servidor único")Com as linhas de comando acima fazemos a leitura do pacote de funções escolhido (markovchain), definimos os nomes dos estados e a matriz de probabilidades de transição. Temos por resultado um objeto de nome ProbT contendo a matriz no formato requerido. Basta agora digitar ProbT na linha de comandos do R e temos por resposta a matriz de probabilidades de transição.
ProbT## Fila de servidor único
## A 2 - dimensional discrete Markov Chain defined by the following states:
## Ocupado, Não ocupado
## The transition matrix (by rows) is defined as follows:
## Ocupado Não ocupado
## Ocupado 0.9 0.1
## Não ocupado 0.6 0.4Para calcularmos as probabilidades de transição em duas e três etapas fazemos:
ProbT^2## Fila de servidor único^2
## A 2 - dimensional discrete Markov Chain defined by the following states:
## Ocupado, Não ocupado
## The transition matrix (by rows) is defined as follows:
## Ocupado Não ocupado
## Ocupado 0.87 0.13
## Não ocupado 0.78 0.22ProbT^3## Fila de servidor único^3
## A 2 - dimensional discrete Markov Chain defined by the following states:
## Ocupado, Não ocupado
## The transition matrix (by rows) is defined as follows:
## Ocupado Não ocupado
## Ocupado 0.861 0.139
## Não ocupado 0.834 0.166Significa que, partindo do estado “Ocupado”, temos probabilidade 0.87 de permanecermos nesse estado depois de duas etapas da cadeia, ou seja, se a cadeia tiver \(C_0\) = “Ocupado” como valor inicial, depois de duas transições temos \(C_2\) = “Ocupado”, com probabilidade 0.87, não importado os valores intermediários que a cadeia possa assumir.
Ainda podemos calcular a função de probabilidade da resposta para cada instante de tempo, isto utilizando o Teorema 2.3. Assumindo que o estado inicial desta cadeia seja \((0,1)\), temos que:
estadoInicial = c(0,1)
estadoInicial*(ProbT^2)## Ocupado Não ocupado
## [1,] 0.78 0.22Assim, podemos afirmar que, após duas etapas, a probabilidade de observarmos o estado “Ocupado” será de 0.78 e estaremos no estado “Não ocupado” com probabilidade 0.22.
A longo prazo, temos por esultado:
estadoInicial*(ProbT^10)## Ocupado Não ocupado
## [1,] 0.8571378 0.1428622Significando que devemos permanecer ocupados 86% do tempo.
A potência \(m\)-ésima da matriz de probabilidades de transição de uma Cadeia de Markov fornece as probabilidades de transição de um estado para outro em \(m\) finitas unidades de tempo. Será útil para estender este conceito aprendermos como fazer os cálculos para intervalos de tempo mais longos.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\), matriz de transição \(\mathcal{P}\) e \(A\) um subconjunto de \(S\). Nesta seção, estamos interessados em saber qual é a probabilidade da cadeia atingir um estado em \(A\). Especificamente, queremos derivar uma expressão para a probabilidade de que o tempo para atingir um estado em \(A\) seja finito, bem como a esperança desse tempo.
Definição 2.8: Tempo de primeira visita.
Seja \(A\subseteq S\). O tempo de primeira visita \(T_A\), da Cadeia de Markov \(\{C_n\}\) ao conjunto \(A\), é definido como \[ T_A =\min\big\{n\geq 0 \, : \, C_n\in A\big\}, \] e como \(T_A=\infty\) se \(A=\emptyset\).
Em outras palavras, \(T_A\) é uma variável aleatória com valores inteiros não negativos assumindo o primeiro tempo positivo em que a Cadeia de Markov atinge \(A\). Denotaremos o tempo de primeira visita ao ponto \(x\in S\) por \(T_x\). Utilizaremos a notação \(P_x(\cdot)\) para denotar a probabilidade de vários eventos definidos em termos da Cadeia de Markov começando em \(x\). Então \[ P_x(C_1\neq y,C_2\neq y, C_3=y), \] denota a probabilidade de que a Cadeia de Markov começando no estado \(x\) esteja no estado \(y\) no tempo 3, mas não nos tempos 1 e 2. Observe que a probabilidade acima significa que \[ P_x(C_1\neq y,C_2\neq y, C_3=y) = P(C_0=x,C_1\neq y, C_2\neq y,C_3=y)\cdot \]
Teorema 2.9.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e sejam \(x,y\in S\). Então \[ p^{(n)}_{x,y}=\sum_{m=1}^n P_x(T_y=m)p^{(n-m)}_{y,y}, \] para \(n\ge 1\).
Demonstração.
Definição 2.9.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\). A probabilidade de começar no estado \(x\in S\) e atingir \(A\subset S\), em um tempo finito, é definida como \[ \rho_{x,A}=P_x(T_A<\infty) \cdot \]
Então \(\rho_{x,y}\), quando escolhemos \(A=\{y\}\), denota a probabilidade da Cadeia de Markov partindo do estado \(x\) chegar o estado \(y\) en algum tempo finito. Em particular, \(\rho_{y,y}\) denota a probabilidade de que a Cadeia de Markov partindo de \(y\) retorne a \(y\). Devemos esclarecer que temos definido dois conceitos diferentes. Um é a probabilidade de, partindo de um estado \(x\) a cadeia retornar num tempo finito a um conjuntos de estados \(A\), esta probabilidade a chamamos de \(\rho_{x,A}\). Outro conceito é a probabilidade de que a cadeia, partindo de um estado \(x\), atingir um outro estado \(y\) num tempo finito \(n\), chamada de \(P_x(T_y=n)\).
Observemos também que o tempo médio da cadeia atingir \(A\) é dado por \[ \mbox{E}_x(T_A)=\sum_{n<\infty} n P_x(T_A=n)\cdot \] Dois resultados posteriores nos permitirão calcular explicitamente as quantidades \(\rho_{x,y}\) e \(\mbox{E}_x(T_A)\) por meio de certas equações lineares associadas à matriz de transição.
Exemplo 2.10:
Consideremos a situação de uma Cadeia de Markov com matriz de transição \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]
Começando em 2, qual será a probabilidade de atingir o estado 4? Quanto tempo demora até que a cadeia estar no estado 1 ou no 4?
Observemos que \[ \rho_{1,4}=P_x(T_4<\infty)=0, \; \rho_{4,4}=P_x(T_4<\infty)=1, \; \mbox{E}_1(T_{\{1,4\}})=0 \; \mbox{e} \; \mbox{E}_4(T_{\{1,4\}})=0\cdot \] Suponhamos agora que começamos no estado 2 e consideraremos a situação depois de fazer um passo. Com probabilidade 1/2 pulamos ao estado 1 e com probabilidade 1/2 pulamos ao estado 3. Assim, \[ \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\rho_{3,4} \] e \[ \mbox{E}_2(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_1(T_{\{1,4\}})+\dfrac{1}{2}\mbox{E}_3(T_{\{1,4\}})\cdot \]
O valor 1 aparece nesta última expressão porque contamos o tempo do primeiro passo. Similarmente, \[ \rho_{3,4}=\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\rho_{4,4} \] e \[ \mbox{E}_3(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_2(T_{\{1,4\}})+\dfrac{1}{2}\mbox{E}_4(T_{\{1,4\}})\cdot \] Consequentemente \[ \rho_{2,4}=\dfrac{1}{2}\rho_{3,4}=\dfrac{1}{2}\left( \dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\right) \] e \[ \mbox{E}_2(T_{\{1,4\}})=1+\dfrac{1}{2}\mbox{E}_3(T_{\{1,4\}})=1+\dfrac{1}{2}\left[ 1+\dfrac{1}{2}\mbox{E}_2(T_{\{1,4\}})\right] \cdot \]
Assim, a partir de 2, a probabilidade de acertar o estado 4 é 1/3 e o tempo médio para chegar é 2 assim como é dois também o tempo médio para chegar ao estado 1. Note que, ao escrever as equações para \(\rho_{2,4}\) e \(\mbox{E}_2(T_{\{1,4\}})\) temos feito uso implícito da propriedade markoviana, em assumir que a cadeia começa novamente de sua nova posição após o primeiro salto.
Teorema 2.10.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O vetor de probabilidades \(\{\rho_{x,A}, \; x\in S\}\), as probabilidades do tempo de primeira visita ao conjunto \(A\) a partir de qualquer estado \(x\in S\), é a solução não negativa mínima do sistema de equações lineares \[ \begin{array}{ll} \rho_{x,A} = 1, & \forall x\in A \\[0.8em] \rho_{x,A} = \displaystyle \sum_{y\in S} p_{x,y}\rho_{y,A}, & \forall x\notin A\cdot \end{array} \]
Solução mínima neste teorema significa que, se \(\rho^*_{x,A}\) for uma outra solução não negativa do sistema, então \(\rho^*_{x,A}\geq \rho_{x,A}\), \(\forall x\in S\).
Demonstração.
Primeiro provemos que o sistema \(\{\rho_{x,A}, \; x\in S\}\) satisfaz o Teorema 2.6. Se \(C_0=x\in A\), então \(T_A=0\) e \(\rho_{x,A}=1\). Caso \(C_0=x\notin A\), então \(T_A\geq 1\) e pela propriedade markoviana \[ P_x(T_A < \infty \, | \, C_1=y)=P_y(T_A < \infty)=\rho_{y,A} \] e \[ \begin{array}{rcl} \displaystyle \rho_{x,A}=P_x(T_A < \infty) & = & \displaystyle \sum_{y\in S} P_x(T_A < \infty,C_1=y) \\[0.8em] & = & \displaystyle \sum_{y\in S} P_x(T_A < \infty \, | \, C_1=y)\times P_x(C_1=y) \, = \, \sum_{y\in S} p_{x,y}\rho_{y,A}\cdot \end{array} \] Suponhamos agora que \(\rho^*_{x,A}\) seja uma solução do sistema. Então \(\rho_{x,A}=\rho^*_{x,A}=1\) para \(x\in A\). Caso \(x\notin A\), então \[ \rho^*_{x,A}=\sum_{y\in S} p_{x,y}\rho^*_{y,A}=\sum_{y\in A} p_{x,y}+\sum_{y\notin A} p_{x,y}\rho^*_{y,A}\cdot \] Substituindo a expressão de \(\rho^*_{y,A}\), temos que \[ \begin{array}{rcl} \rho^*_{x,A} & = & \displaystyle \sum_{y\in A} p_{x,y}+\sum_{y\notin A} p_{x,y} \left(\sum_{z\in A}p_{y,z}+\sum_{z\notin A}p_{y,z}\rho^*_{z,A} \right) \\[0.8em] & = & \displaystyle P_x(C_1\in A)+P_x(C_1\notin A,C_2\in A)+\sum_{y\notin A}\sum_{z\notin A} p_{x,y}p_{y,z}\rho^*_{z,A} \cdot \end{array} \] Repetindo a substituição para \(\rho^*_{z,A}\) obtemos, depois de \(n\) substituições, que \[ \begin{array}{rcl} \displaystyle \rho^*_{x,A} & = & P_x(C_1\in A)+\cdots+P_x(C_1\notin A,\cdots,C_{n-1}\notin A,C_n\in A) \\[0.8em] & = & \displaystyle \sum_{z_1\notin A}\cdots \sum_{z_n\notin A} p_{x,z_1}p_{z_1,z_2}\cdots p_{z_{n-1},z_n}\rho^*_{z_n,A}\cdot \end{array} \] Agora, se \(\rho^*_{x,A}\) é não negativo assim também o é o último termo da direita. O termo remanescente de somas fornece o valor de \(P_x(T_A\leq n)\). Desta forma, vemos que, \(\rho^*_{x,A}\geq P_x(T_A\leq n)\) para todo \(n\) e então \[ \rho^*_{x,A}\geq \lim_{n\to\infty} P_x(T_A\leq n)=P_x(T_A<\infty)=\rho_{x,A}\cdot \]Exemplo 2.11.
Continuando o Exemplo 2.3. O sistema de equações lineares no Teorema 2.6 para \(\rho_{2,4}\) é dado aqui por \(\rho_{4,4}=1\) e \[ \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\rho_{3,4}, \qquad \rho_{3,4}=\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\rho_{4,4} \] de maneira que \[ \rho_{2,4}=\dfrac{1}{2}\rho_{1,4}+\dfrac{1}{2}\left(\dfrac{1}{2}\rho_{2,4}+\dfrac{1}{2}\right) \] e \[ \rho_{2,4}=\dfrac{1}{3}+\dfrac{2}{3}\rho_{1,4}, \qquad \rho_{3,4}=\dfrac{2}{3}+\dfrac{1}{3}\rho_{1,4}\cdot \]
O valor de \(\rho_{1,4}\) não é determinado pelo sistema, mas a condição mínima agora nos faz assumir \(\rho_{1,4}=0\), portanto, obtemos \(\rho_{2,4}=1/3\) como antes. Naturalmente, a condição de contorno \(\rho_{1,4}=0\) era óbvia desde o início para construir nosso sistema de equações e não temos de preocuparmos sobre soluções mínimas não negativos.
Nos casos em que o espaço de estados é infinito, pode não ser possível escrever uma condição de contorno correspondente. Então, como veremos em exercícios, a condição mínima é essencial. Agora vamos apresentar um resultado geral do tempo médio para atingir um conjunto de estados \(A\). Recordemos que \(\mbox{E}_x(T_A)\) foi definida, onde \(T_A\) é o tempo mínimo da primeira vez que \(\{C_n\}_{n\ge 1}\) atinge \(A\).
Na demonstração do seguinte teorema a seguir vamos utilizar a função indicadora do conjunto \(\{y\}\), \(\pmb{1}_{y}(z)\), \(z\in S\), definida por \[ \pmb{1}_y(z) \, = \, \left\{ \begin{array}{cc} 1, & z=y \\ 0, & z\neq y \end{array}\right.\cdot \]
Teorema 2.7.
Seja \(\{C_n\}\) uma Cadeia de Markov com espaço de estados \(S\) e matriz de probabilidades de transição \(\mathcal{P}=\big(p_{x,y}\big)\). O vetor de tempos médios \(\{\mbox{E}_x(T_A), \; x\in S\}\), os tempos médios de primeira visita ao conjunto \(A\) a partir de qualquer estado \(x\in S\), é a solução não negativa mínima do sistema de equações lineares \[ \begin{array}{ll} \mbox{E}_x(T_A) = 0, & \forall x\in A \\[0.8em] \mbox{E}_x(T_A) = \displaystyle 1+\sum_{y\notin A} p_{x,y}\mbox{E}_y(T_A), & \forall x\notin A\cdot \end{array} \]
Demonstração.
Primeiro vamos provar que o sistema \(\{\mbox{E}_x(T_A), \; x\in S\}\) satisfaz o Teorema 2.7. Se \(C_0=x\in A\), então \(T_A=0\) e, portanto, \(\mbox{E}_x(T_A)=0\). Caso \(C_0=x\notin A\), então \(T_A\geq 1\) de forma que, pela propriedade markoviana, \[ \mbox{E}_x(T_A \, | \, C_1=y) \, = \, 1+\mbox{E}_y(T_A) \] e \[ \mbox{E}_x(T_A) \, = \, \displaystyle \sum_{y\in S} \mbox{E}_x\big(T_A\pmb{1}_y(C_1)\big) \, = \, 1+ \displaystyle \sum_{y\in S} \mbox{E}_x(T_A \, | \, C_1=y)P_x(C_1=y) \, = \, 1+\sum_{y\notin A} p_{x,y}\mbox{E}_y(T_A)\cdot \] Suponhamos agora que \(\mbox{E}^*_x(T_A)\), \(x\in S\), seja uma outra solução do sistema. Então \(\mbox{E}^*_x(T_A)=0\) para \(x\in A\). Se \(x\notin A\), então \[ \begin{array}{rcl} \mbox{E}^*_x(T_A) & = & \displaystyle 1+\sum_{y\notin A} p_{x,y}\mbox{E}^*_y(T_A) \, = \, \displaystyle 1+\sum_{y\notin A} p_{x,y}\left( 1+\sum_{z\notin A}p_{y,z}\mbox{E}^*_z(T_A) \right) \\[0.8em] & = & \displaystyle P_x(T_A\geq 1)+P_x(T_A\geq 2)+\sum_{y\notin A}\sum_{z\notin A}p_{x,y}p_{y,z}\mbox{E}^*_z(T_A)\cdot \end{array} \] Depois de repetir diversas vezes a substituição da expressão de \(\mbox{E}^*_x(T_A)\) do termo final obtemos que, depois de \(n\) passos \[ \mbox{E}^*_x(T_A) \, = \, P_x(T_A\geq 1)+\cdots+P_x(T_A\geq n)+ \sum_{z_1\notin A}\cdots \sum_{z_n\notin A}p_{x,z_1}p_{z_1,z_2}\cdots p_{z_{n-1},z_n}\mbox{E}^*_{z_n}(T_A)\cdot \] Logo, se \(\mbox{E}^*_x(T_A)\) for não negativo, \[ \mbox{E}^*_x(T_A)\geq P_x(T_A\geq 1)+\cdots+P_x(T_A\geq n) \] e, fazendo \(n\to\infty\), \[ \mbox{E}^*_x(T_A)\geq \sum_{n=1}^\infty P_x(T_A\geq n) \, = \, \mbox{E}_x(T_A)\cdot \]Exemplo 2.5.
Continuando com o Exemplo 2.4, perguntamos: quanto tempo demora até que a cadeia atinja o conjunto \(\{1,4\}\)? Vejamos o sistema de equações para \(\mbox{E}_x(T_{\{1,4\}})\), \(x\in\{1,2,3,4\}\).
Primeiro \[ \mbox{E}_1(T_{\{1,4\}})=\mbox{E}_4(T_{\{1,4\}})=0\cdot \] Também \[ \mbox{E}_2(T_{\{1,4\}}) \, = \,1+p_{2,2}\mbox{E}_2(T_{\{1,4\}})+p_{2,3}\mbox{E}_3(T_{\{1,4\}}) \] e \[ \mbox{E}_3(T_{\{1,4\}})=1+p_{3,2}\mbox{E}_2(T_{\{1,4\}})+p_{3,3}\mbox{E}_3(T_{\{1,4\}})\cdot \] Não é difícil obter que \(\mbox{E}_2(T_{\{1,4\}})=\mbox{E}_3(T_{\{1,4\}})=2\).
Encontre as matrizes \(\mathcal{P}^2\), \(\mathcal{P}^3\), \(\mathcal{P}^4\) e \(\mathcal{P}^n\) para uma Cadeia de Markov
com matriz de probabilidades de transição \[
\mathcal{P}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\cdot
\] Faça o mesmo se a matriz de transição fosse \(\mathcal{P}=\begin{pmatrix} 0 & 1 \\ 1 & 0
\end{pmatrix}\). Interprete o que acontece em cada um destes
processos.
Prove que \(P(C_{n+m}=y \, | \, C_0=x,
C_n=z) \, = \, p_{z,y}^{(m)}\).
Seja \(\{C_n: n\ge 0\}\) uma Cadeia de Markov com dois estados.
Encontre \(P_0(T_0=n)\)
Encontre \(P_0(T_1=n)\)
Considere a Cadeia de Markov com estados \(\{0, 1, 2\}\) e matriz de probabilidades de
transição \[
\mathcal{P} = \begin{pmatrix} 0.3 & 0.3 & 0.4 \\ 0.2 & 0.7
& 0.1 \\ 0.2 & 0.3 & 0.5 \end{pmatrix}\cdot
\] Encontre as probabilidadaes \(P(C_{16}=2 \, | \, C_0=0)\) e \(P(C_{12}=2, C_{16}=2 \, | \, C_0=0)\).
Uma Cadeia de Markov a três estados tem a seguinte como matriz de probabilidades de transição: \[ \mathcal{P} = \begin{pmatrix} 0.25 & 0.5 & 0.25 \\ 0.4 & 0.6 & 0 \\ 1 & 0 & 0 \end{pmatrix} \]
Qual é o valor aproximado de \(p^{(100)}_{1,3}\)? Que interpretação você dá a esse resultado?
Qual é a probabilidade de que, após o terceiro passo, a cadeia esteja no estado 3 se o vector de probabilidade inicial for \((1/3,1/3,1/3)\)?
Seja \(y\) um estado transiente.
Mostre que, para todo \(x\) \[
\sum_{n=0}^\infty p^{(n)}_{x,y}\le \sum_{n=0}^\infty p^{(n)}_{y,y} \cdot
\]
Prove que se o estado \(x\) é
absorvente e \(p_{y,x}> 0\), então o
estado \(y\) é transiente.
Prove que se o estado \(x\) é
transiente e \(p_{y,x}> 0\), então o
estado \(y\) é transiente.
Sete meninos estão brincando com uma bola. O primeiro menino sempre a lança para o segundo menino. O segundo menino tem a mesma probabilidade de jogá-la para o terceiro ou o sétimo. O terceiro rapaz mantém a bola, se ele a receber. O quarto menino sempre a joga para o sexto. O quinto menino tem a mesma probabilidade de jogá-la para o quarto, sexto ou sétimo menino. O sexto menino sempre lança-a para o quarto. O sétimo menino tem a mesma probabilidade de jogá-la para o primeiro ou quarto do menino.
Escreva a matriz de transição \(\mathcal{P}\).
Classifique os estados.
A bola é dada ao quinto menino. Encontrar a esperança do número de vezes que o sétimo menino terá a bola.
Mostre que \(\rho_{x,y}>0\)
se, e somente se, \(p^{(n)}_{x,y}>0\) para algum inteiro
positivo \(n\).
Considere uma Cadeia de Markov com espaço de estados \(S=\{0,1,\cdots,6\}\) e matriz 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 \\ 1/2 & 0 & 1/8 & 1/4 & 1/8 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 1/2 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]
Determine quais estados são transientes e quais recorrentes.
Encontre \(\rho_{0,y}\), para \(y=0,\cdots,6\).
Um processo se move no espaço de estados \(S=\{1,2,3,4,5\}\). Inicia-se em 1 e, em
cada passo sucessivo, move-se para um número inteiro maior do que a sua
posição atual, movendo-se com igual probabilidade para cada um dos
restantes números inteiros maiores. O estado 5 é um estado absorvente.
Encontre o número esperado de passos para chegar ao estado 5.
Sejam \(\{C_n\}\) e \(\{D_n\}\) duas Cadeias de Markov
independentes, cada uma om o mesmo espaço de estados \(S\) e mesma função de transição. Defina o
processo \(\{Z_n\}=\{(C_n,D_n)\}\) com
espaço de estados \(S\times S\). Mostre
que \(\{Z_n\}\) é uma Cadeia de Markov
e encontre a matriz de probabilidadaes de transição do processo.
Para cada uma das seguintes matrizes de transição, encontrar as cinco primeiras potências da matriz. Em seguida, encontrar a probabilidade de que o estado 2 mude para o estado 4 após 5 repetições do experimento.
\[ \mathcal{P} =\begin{pmatrix} 0.1 & 0.2 & 0.2 & 0.3 & 0.2 \\ 0.2 & 0.1 & 0.1 & 0.2 & 0.4 \\ 0.2 & 0.1 & 0.4 & 0.2 & 0.1 \\ 0.3 & 0.1 & 0.1 & 0.2 & 0.3 \\ 0.1 & 0.3 & 0.1 & 0.1 & 0.4 \end{pmatrix}\cdot \]
\[ \mathcal{P} =\begin{pmatrix} 0.3 & 0.2 & 0.3 & 0.1 & 0.1 \\ 0.4 & 0.2 & 0.1 & 0.2 & 0.1 \\ 0.1 & 0.3 & 0.2 & 0.2 & 0.2 \\ 0.2 & 0.1 & 0.3 & 0.2 & 0.2 \\ 0.1 & 0.1 & 0.4 & 0.2 & 0.2 \end{pmatrix}\cdot \]
\[ \mathcal{P} = \begin{pmatrix} 0.15 & 0.05 & 0.8 \\ 0 & 1 & 0 \\ 0.4 & 0.6 & 0 \end{pmatrix}\cdot \]
\[ \mathcal{P} = \begin{pmatrix} 0.4 & 0 & 0.6 \\ 0 & 1 & 0 \\ 0.9 & 0 & 0.1 \end{pmatrix}\cdot \]
\[ \mathcal{P} = \begin{pmatrix} 0.32 & 0.41 & 0.16 & 0.11 \\ 0.42 & 0.30 & 0 & 0.28 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}\cdot \]
\[ \mathcal{P} = \begin{pmatrix} 0.2 & 0.5 & 0.1 & 0.2 \\ 0 & 1 & 0 & 0 \\ 0.9 & 0.02 & 0.04 & 0.04 \\ 0 & 0 & 0 & 1 \end{pmatrix}\cdot \]
Classifique os estados da Cadeia de Markov com matriz de
transição \[
\mathcal{P} = \begin{pmatrix} p & q & 0 & 0 \\ 0 & 0
& p & q \\ p & q & 0 & 0 \\ 0 & 0 & p &
q \end{pmatrix}\cdot
\] onde \(p+q=1\) e \(p,q\ge 0\).
Seja \(\{C_n: n\ge 0\}\) uma Cadeia de Markov com espaço de estados \(S\subset \{0,1,2,\cdots\}\) e cuja matriz de transição \(\mathcal{P}\) é tal que \[ \sum_x y \, p_{x,y} \,= \, \alpha \, x+\beta, \qquad x\in S, \] para algumas constantes \(\alpha\) e \(\beta\).
Mostre que \(\mbox{E}(C_{n+1}) \, = \, \alpha \, \mbox{E}(C_n)+\beta\).
Mostre que se \(\alpha\neq 1\), então \[ \mbox{E}(C_n) \, = \, \dfrac{\beta}{1-\alpha}+\alpha^n\left(\mbox{E}(C_0)-\dfrac{\beta}{1-\alpha}\right) \cdot \]
Qual será a proporção dos coelhos no grupo 1 que ainda estavam no grupo 1 cinco semanas mais tarde?
Na primeira semana, havia nove coelhos do primeiro grupo, 4 no segundo e nenhum nos terceiro e quarto grupos. Quantos coelhos seria de esperar em cada grupo após 4 semanas?
Ao investigar a matriz de transição elevada a potências cada vez maiores, faça uma suposição razoável para a probabilidade a longo tempo que um coelho no grupo 1 ou 2 ainda estar no grupo 1 ou 2 depois de um tempo arbitrariamente longo. Explique por que esta resposta é razoável.
Para um criminoso que comete roubo, qual será a probabilidade de que o seu próximo crime também seja um roubo?
Para um criminoso que comete roubo, qual será a probabilidade de que seu segundo crime depois do atual também seja um roubo?
Se essas tendências continuarem, quais serão as probabilidades de longo prazo para cada tipo de crime?
Seja \(S=\{0,1,2,\cdots\}\) o
conjunto de estados de uma Cadeia de Markov com probabilidades de
transição \(p_{i,i+1}=p\) e \(p_{i,0}=q\), sendo que \(0 < p < 1\) e \(q=1-p\). Classifique os estados sa cadeia
como transientes ou recorrentes.
Três tanques de guerra lutam um duelo. O tanque A atinge seu alvo
com probabilidade 2/3, o tanque B com probabilidade 1/2 e o tanque C com
probabilidade 1/3. Os tiros são disparados simultaneamente e, uma vez
atingido, o tanque fica fora de ação. Como estado, escolhemos o conjunto
de tanques ainda em ação. Se em cada etapa cada tanque disparar contra
seu oponente mais forte., Verifique se a seguinte matriz de transição
está correta: \[
\begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \,
\mbox{E} \; & \, \mbox{A} \; & \; \mbox{B} \; & \; \mbox{C}
& \mbox{AC} & \mbox{BC} & \mbox{ABC} \end{matrix} \\
\mathcal{P} \, = \, \begin{matrix} \mbox{A} \\ \mbox{A} \\ \mbox{B} \\
\mbox{C} \\ \mbox{AC} \\ \mbox{BC} \\ \mbox{ABC} \end{matrix} &
\begin{pmatrix} \, 1 & \, 0 & \, 0 & \, 0 & \, 0 &
\, 0 & \, 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 \\
2/9 & 4/9 & 0 & 1/9 & 2/9 & 0 & 0
\\
1/6 & 0 & 1/3 & 1/6 & 0 & 1/3 & 0
\\
0 & 0 & 0 & 4/9 & 2/9 & 2/9 & 1/9
\end{pmatrix}\cdot
\end{matrix}
\]
Modifique a matriz de transição no exercício anterior, assumindo
que quando todos os tanques estão em ação, A dispara em \(\mbox{B}\), \(\mbox{B}\) em \(\mbox{C}\) e \(\mbox{C}\) em \(\mbox{A}\).
Para a seguinte Cadeia de Markov, forneça uma classificação completa dos estados: \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \, s_1 & \, s_2 & \, s_3 & \, s_4 & \, s_5 & \, s_6 & \, s_7 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} s_1 \\ s_2 \\ s_3 \\ s_4 \\ s_5 \\ s_6 \\ s_7 \end{matrix} & \begin{pmatrix} \, 0 & \, 0 & \, 0 & \, 1 & \, 0 & \, 0 & \, 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 \end{pmatrix}\cdot \end{matrix} \]