- (16) 3376-2047
- [email protected]
- Portfólio de Serviços
- AT
Uma importante caracterização da cadeia de markov seria a classificação dos estados.
O estado j é dito acessível pelo estado i se j pode ser alcançado a partir do estado i por um número finito de passos. Se dois estados i e j são acessíveis ou seja j é acessível a i e i é acessível a j então dizemos são comunicado.
Probabilisticamente temos que essa definição implica que
$i \rightarrow j $ (j é acessível de i) se para algum $0\leq n\textless \infty$, $\mathbb{P}_{i,j}^n \textgreater 0$
$j \rightarrow i $ (i é acessível de j) se para algum $0\leq n\textless \infty$, $\mathbb{P}_{j,i}^n \textgreater 0$
$i \leftrightarrow j $ (i e j são comunicados) se para algum $0\leq n\textless \infty$, e se para algum $0\leq m\textless \infty$ $\mathbb{P}_{i,j}^n \textgreater 0$ $\mathbb{P}_{j,i}^m \textgreater 0$
Reciprocamente temos que
$i \rightarrow j $ (j não é acessível de i) se para todo $0\leq n\textless \infty$, $\mathbb{P}_{i,j}^n = 0$
$j \rightarrow i $ (i não é acessível de j) se para todo $0\leq n\textless \infty$, $\mathbb{P}_{j,i}^n = 0$
$i \leftrightarrow j $ (i e j não são comunicados) se para todo $0\leq n\textless \infty$, e se para todo $0\leq m\textless \infty$ $\mathbb{P}_{i,j}^n=0$ $\mathbb{P}_{j,i}^m= 0$.
Notemos que como consequência desta definição temos que a relação de comunicação é uma relação de equivalência:
i) Reflexiva
De fato é reflexiva pois $i\leftrightarrow i$ basta tomarmos n=0.
ii) Simétrica
Se $i\leftrightarrow j$, então $j\leftrightarrow i$
iii) Transitividade
Se $i\leftrightarrow j$, e $j\leftrightarrow k$, então $i\leftrightarrow k$
Sabemos que existe dois inteiros r e s tal que:
$$\mathbb{P}_{i,j}^r\textgreater 0,~\mathbb{P}_{j,k}^s\textgreater 0.$$
Mas temos que
$$\mathbb{P}^{r+s}_{i,k}=\displaystyle \sum_{\ell}\mathbb{P}^{r}_{i,\ell}\mathbb{P}^{s}_{\ell,k}\geq \mathbb{P}^{r}_{i,j}\mathbb{P}^{s}_{j,k}\textgreater 0$$
Logo temos que $i\rightarrow k$. Similarmente mostramos que existe um inteiro n tal que
$$\mathbb{P}^{n}_{k,i}\textgreater 0$$
Portanto $k\rightarrow i$. Combinando esses dois resultados temos que $i\leftrightarrow k$.
Se a cadeia de markov tem todos os estados pertence a uma única classe de equivalência, então ele é dito irredutível.
Um estado é dito recorrente se e somente se, partindo deste estado eventualmente retornamos ao mesmo estado, ou seja, um estado é recorrente é
se existe um $n\textgreater 0$ tal que $f^{\star}_{i,i}=1$, no qual $f^{\star}_{i,i}=1$ é definido da seguinte forma
$$f^{n}_{i,i}=\mathbb{P}[X_n=i,X_r\neq i|X_0=i]$ $r\in\{1,2,\cdots,n-1\}$$
então
$$f^{\star}_{i,i}=\displaystyle \sum_{n=1}^{\infty}f^{n}_{i,i}$$
note que $f^{n}_{i,i}$ é a probabilidade de começarmos em i e retornarmos para i, em um tempo n.
Em termos de probabilidade temos temos que um estado é dito recorrente se e somente se $f_{i,i}^{\star}=1$.
Quando o estado i é recorrente podemos definir,
$$\mu_i=\sum_{n=1}^{\infty}n f_{i,i}^{n}$$
note que $\mu$ define o valor esperado do numero de passos necessários para que retorne ao estado i. O qual é chamado de tempo de recorrência. Portanto $\mu_i$ pode ser chamado de média de recorrência do estado i.
Usando a média de recorrência podemos classificar o seu estado recorrência nula ou recorrência
Dizemos que um estado recorrente é dito se um estado recorrente nulo se e somente se o tempo média recorrente é $\infty$, ou seja, se $\mu_i$.
Dizemos que um estado tem recorrência positiva se, e somente se, o tempo médio recorrente é finito, ou seja, $\mu_{i}$.
Um estado é dito ser transiente se, e somente se, partindo do estado i, existe uma probabilidade positiva do processo não eventualmente retornar a este estado.
Isto implica que $f^{\star}_{i,i}\textless 1$.
Outra forma de classificarmos os estados em recorrente e transiente pode ser dado em termos das probabilidade $\mathbb{P}_{i,i}^{n}$ que é a probabilidade do processo ocupar o estado i depois de n passos, dado que o estado inicial também foi i.
i) Um estado i é recorrente se
$$\displaystyle \sum_{n=1}^{\infty}\mathbb{P}_{i,i}^{n}=\infty$$
ii) Um estado i é transiente se
$$\displaystyle \sum_{n=1}^{\infty}\mathbb{P}_{i,i}^{n}\textless \infty$$
Os estados de equivalência $\displaystyle \sum_{n}f_{i,i}^{n}=1$ e $\displaystyle \sum_{n}\mathbb{P}_{i,i}^{n}=\infty$ o que nos mostra claramente a distinção entre $f_{i,i}^{n}$ e $\mathbb{P}^{n}_{i,i}$. $f_{i,i}^{n}$ nos refere a probabilidade do primeiro retorno de i em n passos e $\displaystyle \sum_{n}f_{i,i}^{n}$ é a probabilidade do processo retornar a i eventualmente.
Por outro lado temos que $\mathbb{P}_{i,i}^{n}$ se refere a probabilidade do evento ocupar o estado i depois de n passos. Se o processo retorna ao estado i pelo menos uma vez, então ele vai retornar outras vezes assim temos que $\displaystyle \sum_{n} \mathbb{P}_{ii}^{(n)}$ é uma soma infinita de números positivos. E portanto temos que essa soma é infinita, e portanto o resultado segue.
Seja $Q_{ii}^{(N)}$ a probabilidade de partindo do estado i que a cadeia de markov retorne a este estado pelo menos N vezes. Então se tomarmos $N\rightarrow \infty$ é a probabilidade de retornar infinita vezes no estado i. É claro que se o estado é recorrente então temos que
$$\displaystyle \lim_{N\rightarrow \infty}Q_{ii}^{(N)}=1$$
e por outro lado se o estado é dito ser transiente então temos que
$$\displaystyle \lim_{N\rightarrow \infty}Q_{ii}^{(N)}=0$$
O período de um estado i é definido como sendo o maior divisor comum de todos os inteiros $n\geq 1$, para o qual $\mathbb{P}_{ii}^{n}\textgreater 0$. Quando o período é 1, o estado é dito ser aperiódico.
$$\mathbb{P}_k=\left( \begin{array}{c} ~~0/2 ~~ 1/2 ~~ 1/2 ~~\\ ~~ 1/2 ~~ 0/2 ~~ 1/2 ~~\\~~1/2 ~~ 1/2 ~~ 0/2 ~~ \\ \end{array}\right)$$
Analisando a matriz podemos ver que os todos os estados se interligam além disso $\mathbb{P}_{ii}^{n}\textgreater 0$, para $n\geq 1$, portanto o período que é o máximo divisor comum é 1.
Como todos os estados comunicam-se temos que existe uma única classe de equivalência.
$$\mathbb{P}_k=\left( \begin{array}{c} ~~0/2 ~~ 0/2 ~~ 0/2 ~~2/2 ~~\\ ~~ 0/2 ~~ 0/2 ~~ 0/2 ~~2/2~~\\~~1/2 ~~ 1/2 ~~ 0/2 ~~ 0/2~~ \\~~ 0/2 ~~ 0/2 ~~ 2/2 ~~ 0/2 ~~\\ \end{array}\right)$$
Observando a matriz que todos os estados se comunicam, pois $1\rightarrow 4\rightarrow 3\rightarrow 1$ ou $1\rightarrow 4\rightarrow 2\rightarrow 4\rightarrow 3 \rightarrow 1$.
Portanto todos os estados pertencem a mesma classe de equivalência. Além disso temos que $\mathbb{P}_{ii}^{n}\textgreater 0$ é válido apenas para n=3, n=6 ou múltiplos de deles e portanto temos que o período que é o máximo divisor comum é 3.
Um exemplo clássico de um processo Markoviano, seria o chamado passeio aleatório nos inteiros. Nesse exemplo podemos imaginar uma partícula qualquer, que se movimenta de acordo com a seguinte lei:
$$p(i,i+1)=p e p(i,i-1)=1-p$$
Note que essa partícula apenas se movimenta para frente dando um passo ou para trás dando apenas um passo. A respeito desse exemplo podemos nos fazer diversas perguntas, como por exemplo o sobre quais condições o passeio aleatório é recorrente ?
Note que o passeio aleatório é uma cadeia irredutível. Assim basta mostrarmos que um estado é recorrente que os demais também serão recorrentes. Vamos considerar a origem observe que para a partícula saindo da origem voltar a ela, necessitará de um número par de passos, pois nossa cadeia dá apenas um passo para frente ou para trás. Assim se n é ímpar $\mathbb{P}^n_{0,0}=0$, então
$$\displaystyle \mathbb{P}^{2n}_{0,0}=\left(\begin{array}{c}2n \\n\\ \end{array}\right) p^{n}(1-p)^n=\frac{(2n)!}{n!n!}p^n q^n$$
Podemos usar a formula de Stirling
$$\displaystyle \lim_{n\rightarrow \infty}\frac{n!}{n^ne^n\sqrt{2\pi n}}=1$$
Com alguma manipulação algebrica, temos que
$$\displaystyle \lim_{n\rightarrow \infty}\frac{\mathbb{P}^{2n}(0,0)}{(4pq)^n/\sqrt{\pi n}}=1$$
Observe que quando $p\neq 1/2$ temos que $4pq\textless 1$ e que quando $p=1/2$ temos que $4pq=1$. Assim quando $p=1/2$ a série $\displaystyle\sum_{n=1}^{\infty}\mathbb{P}^{2n}_{0,0}$ diverge e quando $p\neq 1/2$ a serie converge pois é basicamente a serie geométrica. Logo pelo Teorema 5.2.1, temos que o passeio aleatório é recorrente se, e somente se p=1/2.
Suponha que tenhamos 10 bolas, 5 pretas e 5 brancas e duas urnas A e B nas quais, são colocadas aleatoriamente 5 bolas em cada uma. Em cada passo 1 bola de cada urna é retirada e colocada na outra. Seja $X_n=$número de bolas brancas na urna A, na etapa n. Qual a matriz de transição da cadeia.
Primeiramente note que temos um processo markoviano, pois claramente
$$\mathbb{P}(X_{n+1}=j|X_n=i_n,\cdots,X_0=i_0)=\mathbb{P}(X_{n+1}=j|X_n=i_n)$$
Calculemos nossa matriz de transição. Observe que para que o número de bolas se mantenha é necessário retirar duas bolas de mesma cor em cada urna. Assim
$$\mathbb{P}_{i,i}=\displaystyle \frac{i}{5}\frac{5-i}{5}+\frac{5-i}{5}\frac{i}{5}=\frac{2}{25}i(5-i)$$
Para que o número de bolas brancas aumente na urna A devemos pegar uma bola preta nela e uma bola branca na urna B. Então
$$\mathbb{P}{i,i+1}=\frac{5-i}{5}\frac{5-i}{5}=\frac{(5-i)^2}{25}$$
Para que o número de bolas brancas diminua na urna A devemos pegar uma bola branca nela e uma bola preta na urna B. Então
$$\mathbb{P}_{i,i-1}=\frac{i}{5}\frac{i}{5}=\frac{i^2}{25}$$
Logo a matriz de transição é dada por:
$$\mathbb{P}=\left( \begin{array}{c} ~00/25~~~25/25~~~00/25~~~00/25~~~00/25~~~00/25~\\ ~01/25~~~08/25~~~16/25~~~00/25~~~00/25~~~00/25~ \\ ~00/24~~~04/25~~~12/25~~~09/25~~~00/25~~~00/25~ \\ ~00/25~~~00/25~~~09/25~~~12/25~~~04/25~~~00/25~ \\ ~00/25~~~00/25~~~00/25~~~16/25~~~08/25~~~01/25~ \\ ~00/25~~~00/25~~~00/25~~~00/25~~~25/25~~~00/25~\\ \end{array}\right)$$
Considere r bolas rotuladas de 1 a r. Algumas estão na caixa 1 e outras na caixa 2. A cada passo um número é escolhido aleatoriamente e a bola correspondente é movida de sua caixa para a outra. Seja $X_n=$número de bolas na caixa 1 após n passos. Qual a matriz de transição deste processo ?
Primeiramente temos que
$$\mathbb{P}_{0,1}=1$$
$$\mathbb{P}_{r,r-1}=1$$
Para $0\textless i \textless r$ temos que
$$\mathbb{P}{i,i}=0$$
$$\displaystyle \mathbb{P}{i,i-1}=\frac{i}{r}$$
$$\displaystyle \mathbb{P}_{i,i+1}=\frac{(r-i)}{r}$$
Como exemplo tomemos r=4, então
$$\left(\begin{array}{c} ~0/4~~~4/4~~~0/4~~~0/4~~~0/4~\\ ~1/4~~~0/4~~~3/4~~~0/4~~~0/4~\\ ~0/4~~~0/4~~~3/4~~~0/4~~~0/4\\ ~0/4~~~1/2~~~0/4~~~1/2~~~0/4~\\ ~0/4~~~0/4~~~3/4~~~0/4~~~1/4~\\ ~0/4~~~0/4~~~0/4~~~4/4~~~0/4~\\ \end{array}\right)$$
Dizemos que o estado i é fechado se ele pertence a uma classe $\mathcal{C}$ fechada. Equivalentemente dizemos que $i\in\mathcal{C}$ é um estado fechado se para todo $j\nin \mathcal{C}$, temos que:
$$\mathbb{P}(T_j\textless \infty|X_0=i)=0$$
com $T_j=\inf\{n\geq 1 |X_n=j\}$.
Um classe finita é recorrente se, e somente se é fechado.
Iremos provar por contradição, assim seja $\mathcal{C}$ uma classe finita fechada e transiente. Seja i e j em $\mathcal{C}$. Pelo Teorema 5.2.1 temos que
$$\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}^{n}_{i,j}=0$$
e então
$$\displaystyle \sum_{j\in\mathcal{C}}\lim_{n\rightarrow \infty}\mathbb{P}^{n}_{i,j}=0$$
Como $\mathcal{C}$ é uma classe finita, podemos permutar o limite com a somatória.
$$\displaystyle \lim_{n\rightarrow \infty}\sum_{j\in \mathcal{C}}\mathbb{P}_{i,j}^{n}=0$$
mas $\displaystyle \sum_{j\in\mathcal{C}}\mathbb{P}^n_{i,j}=\mathbb{P}(X_n\in \mathcal{C}|X_0=i) $. Desde que a classe é fechada temos que a soma das probabilidades dever ser igual a 1. O que contradiz a equação acima. Assim temos que $\mathcal{C}$ é recorrente. O que mostra o resultado.
Seja $S=\{1,2,3,4,5,6\}$ e a matriz de transição
$$\mathbb{P}=\left(\begin{array}{c} ~1/6~~~5/6~~~0/6~~~0/6~~~0/6~~~0/6~\\ ~1/3~~~2/3~~~0/3~~~0/3~~~0/3~~~0/3~\\ ~0/2~~~0/2~~~1/2~~~0/2~~~1/2~~~0/2~\\ ~1/4~~~1/4~~~0/4~~~0/4~~~1/4~~~1/4~\\ ~0/2~~~0/2~~~1/2~~~0/2~~~1/2~~~0/2~\\ ~0/6~~~1/6~~~0/6~~~1/6~~~1/6~~~1/2~\\ \end{array} \right) $$
Encontre todas as classes e determine qual é transiente e qual é recorrente.
Primeiramente observe o diagrama que nos ajuda a identificar as classes.
Pelo diagrama podemos identificar as seguinte classes:
$$C_1=\{1,2\}\text{ recorrente}$$
$$C_2=\{3,5\}\text{ recorrente}$$
$$C_3=\{4,6\}\text{ transiente}$$
$C_1$ e $C_2$ são classes recorrentes, pois são fechadas pelo Teorema 5.2.2.
$C_3$ é transiente, pois não é fechada e portanto não recorrente.
Dê um exemplo de uma classe fechada infinita a qual é transiente.
Um exemplo é o passeio aleatório, é fácil ver que este é fechado, pois todos os estados pertence a mesma classe.
Além disso, como $S=\mathbb{Z}$ que é infinito enumerável, então temos uma classe fechada e infinita.
Como todos os estados pertence a mesma classe para mostrar que é transiente basta mostrar que
$$\sum_{n=0}^{\infty}p_n(0,0)\textgreater \infty$$
pela contra-positiva do Teorema 5.2.1.
Assim defina o passeio aleatório da seguinte forma:
$$p(i,i+1)=p$$
$$p(i,i-1)=1-p=q$$
Pelo exemplo 5.2.3, temos que
$$\sum_{n=0}^{\infty}p_n(0,0)\textgreater \infty$$
se, e somente se $p\neq 1/2$. Logo para $p\neq 1/2$ o passeio aleatório é transiente.
O Portal Action é mantido pela Estatcamp - Consultoria Estatística e Qualidade, com o objetivo de disponibilizar uma ferramenta estatística em conjunto com uma fonte de informação útil aos profissionais interessados.