5 - Cadeia de Markov

A cadeia de markov é um processo estocástico caracterizado por seu estado futuro depender apenas do seu estado atual, sendo que os estados passados não influenciam no estado futuro. O nome cadeia de markov foi dado em homenagem ao matemático russo Andrey Markov.

Definição 5.1:

Um processo de Markov ${X_t}$ é um processo estocástico com a propriedade de que, dado o valor de $X_t$ os valores de $X_s$, para $t \ \textless \ s$ não são influenciados pelos valores de $X_u$ para $u \ \textless \ t$. Ou seja, a probabilidade de qualquer comportamento futuro do processo, quando o seu estado atual é conhecida exatamente, não é alterada pela conhecimento adicional sobre seu comportamento passado.

Se o conjunto de índice for discreto então a propriedade da cadeia de markov é dada da seguinte forma

$\mathbb{P}[X_{n}=x_n|X_0=x_0, \cdots, X_{n-1}=x_{n-1}]=\mathbb{P}[X_{n}=x_{n}|X_{n-1}=x_{n-1}]=$

$\mathbb{P}(x_{n-1},x_{n})$.

Vamos trabalhar apenas com o conjunto de índice discreto, assim notamos que a cadeia e markov é um processo de estados

Definimos a probabilidade de transição de n-passos como:

\[p_n (i, j ) = \mathbb{P} (X_{n+m} = j | X_m = i ) \] 

Exemplo 5.1:

Seja $\{X_t\}$ um processo estocástico com $X_i: \Omega \rightarrow\mathbb{N}$, no qual $\mathbb{N}$ é o conjuntos dos naturais com o zero. Definamos o seguinte que:

$$\mathbb{P}_k(i,i+1)=\mathbb{P}[X_k=i+1|X_{k-1}=i]=p$$

$$\mathbb{P}_k(i,i-1)=\mathbb{P}[X_k=i-1|X_{k-1}=i]=q$$

$$\mathbb{P}_k(i,i)=\mathbb{P}[X_k=i|X_{k-1}=i]=1-(p+q)$$

 

Esse processo é chamado de processo de nascimento e morte, pois no fundo estamos dizendo que existem apenas 3 possibilidades em cada instantes

• Nascer - acrescentar um novo elemento com probabilidade de que isso ocorra sendo p.
• Morrer - diminuir um novo elemento com probabilidade de que isso ocorra sendo q.
• Nada - não acrescentar, nem diminuir com probabilidade $1-(p+q)$.

Notemos que no processo de nascimento e morte, a probabilidade de acrescentar, diminuir ou nada acontecer não depende do tamanho atual da população, ou seja, não depende de i.

Teorema 5.1(Chapman - Kolmogorov) :

Dado uma cadeia de Markov $\{X_t\}$ com o espaço de estados E, ou seja, E é o conjunto dos possíveis valores de $X_i$ e a probabilidade de transição $\mathbb{P}_k(\cdot,\cdot)$. Para $ n \textless m $ temos que

$$\displaystyle \mathbb{P}[X_{m}= j|X_{n} = i]=\sum_{m=1}^{\infty}\mathbb{P}_{m-k} [x_m , j] \mathbb{P}_{k-n}[i ,x_m]$$

 

Demonstração:

Primeiramente lembremos que $\displaystyle \mathbb{P}[A|B]=\mathbb{P}[A\cap \Omega|B]=\frac{\mathbb{P}[A\cap \Omega ;B]}{\mathbb{P}[B]}$, podemos encontrar mais detalhes sobre a probabilidade condicional na apostila de probabilidade.

Assim, temos que

$$\displaystyle \mathbb{P}[X_{m}=j|X_{n}=y]=\mathbb{P}\left[\{X_{m}=j\}\bigcap \left(\bigcup_{p=1}^{\infty}\{X_k=x_p\}\right)|X_{n}=i\right]$$

 

Observe que $(\{X_{m}=j\}\cap\{X_k=x_p\})\cap(\{X_{m}=j\}\cap\{X_k=x_p\})=\emptyset$, se $j\neq i$, ou seja eles são dois a dois disjuntos assim:

$$\displaystyle \mathbb{P}[X_{m}=j|X_{n}=i]=\sum_{p=1}^{\infty}\mathbb{P}\left[\{X_{m}=j\}\cap\{X_k=x_p\}|X_{n}=i\right]$$

$$\displaystyle \sum_{p=1}^{\infty}\mathbb{P}[X_{m}=j|\{X_k=x_p\}\cap X_{n}=i]\mathbb{P}[X_k=x_p|X_{n}=i]$$

$$\displaystyle \sum_{p=1}^{\infty}\mathbb{P}[X_{m}=j|X_k=x_p]\mathbb{P}_{k}(i,x_p)=\sum_{p=1}^{\infty}\mathbb{P}_{k-n}(i, x_p)\mathbb{P}_{m-k} (x_p , j)$$

 

E portanto o resultado segue.

Uma notação muito usada e útil é a notação matricial que nos fornece toda informação sobre os estados de transição.

$$\mathbb{P}_k=\{\mathbb{P}_k(y,x): x,y \in E\}$$

$$\mathbb{P}_k=\left( \begin{array}{c} \mathbb{P}_k (e_1,e_1) ~~ \mathbb{P}_k (e_1,e_2) ~~ \mathbb{P}_k (e_1,e_3) ~~ \cdots \\ \mathbb{P}_k (e_2,e_1) ~~ \mathbb{P}_k (e_2,e_2) ~~ \mathbb{P}_k (e_2,e_3) ~~ \cdots \\\mathbb{P}_k (e_3,e_1) ~~ \mathbb{P}_k (e_3,e_2) ~~ \mathbb{P}_k (e_3,e_3) ~~ \cdots \\ ~~~~~~~~ \vdots ~~~~~~~~~~\vdots~~~~~~~~~~~~~~ \vdots~~~~~~~~~~ \vdots \ddots \\ \end{array}\right)$$

 

Essa matriz é conhecida como matriz de transição.

Exemplo 5.2:

Usando a notação matricial qual seria a matriz de transição do exemplo 5.1. A matrix de transição do processo de nascimento e morte é dada por:

$$\mathbb{P}_k=\mathbb{P}=\left( \begin{array}{c} 1-p ~~~~~~~~~~~~ p ~~~~~~~~~~~~~~~~~~~~ 0 ~~~~~~~~~ \cdots \\ ~~q ~~~~~~~~~ 1-(p+q) ~~~~~~~~~~~~~~~ p ~~~~~~~~~ \cdots \\ ~~0 ~~~~~~~~~~~~~~~~~ q ~~~~~~~~~~~~~ 1-(p+q) ~~~~~~ \cdots \\ ~~~~~\vdots ~~~~~~~~~~~~ \vdots ~~~~~~~~~~~~~~~ \vdots ~~~~~~~~~~~~~~~~ \vdots \ddots \\ \end{array}\right)$$

 

Exemplo 5.3:

Suponha que uma concessionária tem a seguinte estratégia para um determinado veículo modelo de veículo de seu estoque. Todo sexta-feira a noite quando a concessionária fecha ela contabiliza o número de veículos deste modelo e faz um pedido para o fornecedor que lhe entrega na segunda-feira pela manhã antes da concessionária abrir novamente.

• Se há veículos no estoque, a concessionária não faz nenhum pedido
• Se não há veículos no estoque, a concessionária pede 3 veículos ao fornecedor
• Caso durante a semana este modelo de veículo termine no estoque, ele não será vendido até a semana seguinte.

Assim definamos nosso processo $X_n$ como sendo o número de veículos na sexta feira da semana n, e $X_0$ como sendo o número inicial de veículos.

Definimos $D_i$ a demanda da semana i. Suponha que $D_1,D_2, D_3, \cdots \sim Po(\lambda)$ e sejam independentes, ou seja, $D_i$ tem distribuição poisson com parâmetro $\lambda$. Para mais detalhes sobre a distribuição poisson consulte apostila de probabilidade.

Desta forma nossa variável

$$\displaystyle X_{n+1} = \left\{ \begin{array}{c} max(3-D_{n+1};0),~~~ X_n=0 \\ max(X_n-D_{n+1};0),~~~ X_n\textgreater 0.\end{array} \right.$$

 

A primeira coisa que devemos fazer é verificar se esse processo é uma cadeia de markov se a resposta for afirmativa então devemos encontrar sua matriz de transição.

Notemos que nosso processo tem apenas 4 fases possíveis, ou seja, nosso espaço de fase é dado por:

$$E=\{0,1,2,3\}$$

$$\mathbb{P}[X_{n+1}=x_{n+1}|X_0=x_0,X_1=x_1,\cdots, X_{n}=x_n]$$

 

Se $x_n=0$, então

$$\mathbb{P}[X_{n+1}=x_{n+1}|X_0=x_0,X_1=x_1,\cdots, X_{n}=0]=$$

$$\mathbb{P}[max(3-D_{n+1},0)x_{n+1}|X_0=x_0,X_1=x_1,\cdots, X_{n}=0]=$$

$$\mathbb{P}[max(3-D_{n+1},0)x_{n+1}| X_{n}=0]$$

 

Se $x_n\textgreater 0$

$$\mathbb{P}[X_{n+1}=x_{n+1}|X_0=x_0,X_1=x_1,\cdots, X_{n}=x_{n}]=$$

$$\mathbb{P}[max(x_n-D_{n+1},0)=x_{n+1}|X_0=x_0,X_1=x_1,\cdots, X_{n}=x_n]=$$

$$\mathbb{P}[max(x_n-D_{n+1},0)x_{n+1}| X_{n}=x_{n}]$$.

 

Agora estamos em posição de calcular a matriz de transição.

$$\mathbb{P}_n=\mathbb{P}=\left( \begin{array}{c} \mathbb{P}(D_n\geq 3)~~~ \mathbb{P}(D_n= 2) ~~~ \mathbb{P}(D_n\= 1) ~~~ \mathbb{P}(D_n= 0)\\ \mathbb{P}(D_n\geq 2) ~~~\mathbb{P}(D_n=0)~~~~~~~~~~~~~ 0 ~~~~~~~~~~~~ 0 \\ \mathbb{P}(D_n\geq 1)~~~\mathbb{P}(D_n= 1)~~~ \mathbb{P}(D_n=0)~~~~~~~~~~~ 0 \\ ~~~ \mathbb{P}(D_n\geq 3)~~~ \mathbb{P}(D_n=2)~~~ \mathbb{P}(D_n=1)~~~ \mathbb{P}(D_n=0) \\ \end{array}\right)$$

 

Agora vamos supor que no instante inicial a concessionária tinha 3 automóveis do modelo estudado. Então

$$\displaystyle \mathbb{P}[X_1=x_1|X_0=3] = \left\{ \begin{array}{c} \mathbb{P}[D_1\geq 3]=1-\sum_{k=1}^{2}\frac{e^{-\lambda}\lambda^k}{k!},~~~ x_1=0 \\ \mathbb{P}[D_1=2]=\frac{\lambda^2 e^{-\lambda}}{2},~~~ x_1=1 \\ \mathbb{P}[D_1=1]=\lambda e^{-\lambda}, ~~~ x_1=2 \\ \mathbb{P}[D_1=0]=e^{-\lambda}, ~~~x_1=3.\end{array} \right.$$

 

O interessante da cadeia de markov é que dado um estado inicial, podemos calcular a distribuição assintótica do sistema.

Definição 5.2:

Uma cadeia de markov é dita ser homogênea se a probabilidade de transição for estacionária, ou seja, se a probabilidade de transição não depender da etapa n.

Teorema 5.2:

Seja ${X_n}$ um processo markoviano, então dado um estado inicial $\mu_0$ temos que

$$\displaystyle \mu_n=\mu_0\prod_{i=1}^{n}\mathbb{P}_i$$

 

Se o a cadeia de markov for homogênea então $\mu_n=\mu_0 \mathbb{P}^{n}$.

Demonstração:

Como $\mu_0$ é o estado inicial então temos que $\mu_0=(\mathbb{P}[X_0=0], \mathbb{P}[X_0=1], \mathbb{P}[X_0=2], \cdots)$. Assim

$$\mu_1=(\mathbb{P}[X_1=0|X_0], \mathbb{P}[X_1=1|X_0], \mathbb{P}[X_1=2|X_0], \cdots)$$

 

Agora usando a equação de Chapman-Kolmogorov, temos que

$$\mu_1=\mu_0 \mathbb{P}_1$$.

 

Assim por indução temos que

$$\mu_n=\mu_0 \prod_{j=1}^{n}\mathbb{P}_j$$

 

E portanto o resultado segue.

Exemplo 5.4:

Seja uma cadeia de markov $\{X_t\}$ homogênea com o espaço de transição $E=\{0,1,2\}$ e a seguinte matriz de transição:

$$\mathbb{P}=\left( \begin{array}{c} ~~0,73 ~~0,17~~ 0,10\\ ~~0,90 ~~0,10~~ 0,00 \\ ~~0,68~~0,00~~0,32\\ \end{array}\right)$$

 

Calcule $\mathbb{P}[X_2=1; X_3=1|X_1=0]$ e $\mathbb{P}[X_1=0; X_2=0|X_0=2]$.

Basta observarmos que:

$$\displaystyle \mathbb{P}[X_2=1; X_3=1|X_1=0]=\frac{\mathbb{P}[X_2=1; X_3=1|X_1=0]}{\mathbb{P}[X_2=1;X_1=0]}=$$

$$\frac{\mathbb{P}[X_3=1|X_2=1;X_1=0]}{\mathbb{P}[X_2=1;X_1=0]}\mathbb{P}[X_2=1|X_1=0]$$

$$\displaystyle \mathbb{P}[ X_3=1|X_2=1;X_1=0]\mathbb{P}[X_2=1|X_1=0]=$$

$$\mathbb{P}[ X_3=1|X_2=1]\mathbb{P}[X_2=1|X_1=0]=(0,1)(0,17)=0,017$$

 

Da mesma forma temos que

$$\mathbb{P}[X_1=0; X_2=0|X_0=2]=\mathbb{P}[X_2=0|X_1=0]\mathbb{P}[X_1=0|X_0=2]=(0,73)(0,68)=0,4964 $$

 

Exemplo 5.5:

Seja uma cadeia de markov $\{X_t\}$ homogênea com o espaço de transição $E=\{0,1,2\}$ e a seguinte matriz de transição:

$$\mathbb{P}=\left( \begin{array}{c} ~~0,70 ~~0,20~~ 0,10\\ ~~0,55~~0,10~~ 0,35\\ ~~0,60~~0,00~~0,40\\ \end{array}\right)$$

 

E com a seguinte condição inicial $\mu_{0}=[0,2; 0,8; 0]$

Calcule $\mathbb{P}[X_0=1; X_1=0; X_2=2]$

Observemos que

$\mathbb{P}[X_0=1; X_1=0; X_2=2]=\mathbb{P}[X_2=2| X_1=0; X_0=1]\mathbb{P}[X_0=1; X_1=0]=\mathbb{P}[X_2=2| X_1=0]\mathbb{P}[X_1=0| X_0=1]\mathbb{P}[X_0=1]=(0,1)(0,55)(0,8)=0,044$

 

Exemplo 5.6:

Suponha que 3 bolas brancas e 3 bolas pretas são distribuídas em uma urna de tal forma que cada urna tenha exatamente 3 bolas. Suponha que em cada etapa uma bola de cada urna é selecionada e trocada de urna. Seja $X_n$ o numero de bolas brancas na urna 1. Seja $\{X_t\}$ o processo estocástico associado.

i) Esse processo é um processo markoviano?

ii) Se o estado inicial do sistema é $X_0=1$, ou seja, $\mu_0=(0, 1, 0, 0)$. Qual a probabilidade de $X_2$ ser igual a 0?

iii) Se $\mu_0=(1/4, 1/4, 1/4, 1/4)$ calcule $\mu_{10}$

iv) Se $\mu_{1/4,2/4, 0, 1/4}$ calcule $\mu_{10}$.

 

i) Primeiramente definíamos as seguintes variáveis aleatórias

$B_{n}^1$={Pegar uma bola branca na urna um na etapa n.}

$B_{n}^2$={Pegar uma bola branca na urna dois na etapa n.}

Notemos que $B_n^1, B_{n}^2$, pode assumir apenas o valor 0 ou 1, pois vamos pegar uma única bola em cada etapa. Assim $B_n^1$ será 1 se pegarmos uma bola branca na urna 1 e zero caso contrário e o mesmo vale para $B_n^{2}$ só que para a urna 2.

Portanto temos que o nosso processo $X_n$ será dado da seguinte forma:

$$X_n=X_{n-1}-B_n^1+B_n^2$$

 

Ou seja o número de bolas brancas na etapa n depende do numero de bolas que tínhamos na etapa anterior, menos o $B_n^1$ que é o número de bolas brancas que tiramos da urna 1, mais $B_n^2$ que é o número de bolas brancas que tiramos da urna 2. Assim temos que:

$$\mathbb{P}[X_n=x_n| X_{n-1}=x_{n-1}]=\mathbb{P}[X_{n-1}-B_n^1+B_n^2=x_n| X_{n-1}=x_{n-1}]=$$

$$\mathbb{P}[B_n^2-B_n^1=x_n-X_{n-1}| X_{n-1}=x_{n-1}]=$$

$$\mathbb{P}[B_n^2-B_n^1=x_n-x_{n-1}| X_{n-1}=x_{n-1}]$$

 

Como $B_n^1$ e $B_n^2$ assumem apenas valores 0 ou 1, então temos que $B_n^2-B_n^1$ pode assumir apenas o valores -1, 0 e 1.

Calculemos primeiramente então

$$\displaystyle \mathbb{P}[B_n^1=x|X_{n-1}=x_{n-1}] = \left\{ \begin{array}{c} 1-\frac{x_{n-1}}{3},~~~ x=0 \\ \frac{x_{n-1}}{3}~~~ x_1=1 .\end{array} \right.$$

$$\displaystyle \mathbb{P}[B_n^2=x|X_{n-1}=x_{n-1}] = \left\{ \begin{array}{c} \frac{x_{n-1}}{3},~~~ x=0 \\ 1-\frac{x_{n-1}}{3}~~~ x_1=1 .\end{array} \right.$$

 

Notemos que:

$$\mathbb{P}[B_n^{2}=0;B_n^{1}=1|X_{n-1}=x_{n-1}]=\mathbb{P}[B_n^{2}=0|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=1|X_{n-1}=x_{n-1}]=\left(\frac{x_{n-1}}{3}\right)^2$$

$$\mathbb{P}[B_n^{2}=0;B_n^{1}=0|X_{n-1}=x_{n-1}]+\mathbb{P}[B_n^{2}=1;B_n^{1}=1|X_{n-1}=x_{n-1}]=$$

$$\mathbb{P}[B_n^{2}=0|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=0|X_{n-1}=x_{n-1}]+\mathbb{P}[B_n^{2}=1|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=1|X_{n-1}=x_{n-1}]$$

$$=\left[2\frac{x_{n-1}}{3}\left(1-\frac{x_{n-1}}{3}\right)\right]$$

$$\mathbb{P}[B_n^{2}=1;B_n^{1}=0|X_{n-1}=x_{n-1}]=\mathbb{P}[B_n^{2}=1|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=0|X_{n-1}=x_{n-1}]=\left(1-\frac{x_{n-1}}{3}\right)^2$$

 

Desta forma temos que:

$$\mathbb{P}[B_n^2-B_n^1=x_{n}-x_{n-1}|X_{n-1}=x_{n-1}] =$$

$$\displaystyle \left\{ \begin{array}{c} \mathbb{P}[B_n^{2}=0;B_n^{1}=1|X_{n-1}=x_{n-1}]=\left(\frac{x_{n-1}}{3}\right)^2,~~~ x_{n}-x_{n-1}= -1 \\ \mathbb{P}[B_n^{2}=0;B_n^{1}=0|X_{n-1}=x_{n-1}]+\mathbb{P}[B_n^{2}=1;B_n^{1}=1|X_{n-1}=x_{n-1}]=\\=\left[2\frac{x_{n-1}}{3}\left(1-\frac{x_{n-1}}{3}\right)\right],x_{n}-x_{n-1}=0 \\ \mathbb{P}[B_n^{2}=1;B_n^{1}=0|X_{n-1}=x_{n-1}]=\left(1-\frac{x_{n-1}}{3}\right)^2~~~ x_{n}-x_{n-1}=1\\  0,~~~~~~~~~~~~~~~~~~~~~~~~~~ \mbox{caso contrário} .\end{array} \right.$$

 

Assim a matriz de transição do processo $X_n$ é dada

$$\mathbb{P}=\left( \begin{array}{c} ~0/9 ~~9/9~~ 0/9 ~~ 0/9\\ ~1/9~~4/9~~4/9 ~~ 0/9 \\~0/9~~ 4/9~~4/9 ~~ 1/9\\~0/9~~0/9~~ 9/9~~ 0/9\\ \end{array}\right)$$

 

Portanto concluímos que $X_n$ é de fato uma cadeia de markov homogênea.

ii) Por definição temos que

$$\mu_n=(\mathbb{P}[X_n=0], \mathbb{P}[X_n=1], \mathbb{P}[X_n=2], \mathbb{P}[X_n=3])$$

 

Assim para encontrarmos $\mathbb{P}[X_2=0]$, basta encontrarmos $\mu_2$. Entretanto pela equação de Chapman-Kolmogorov temos que

$$\mu_2=\mu_0 \mathbb{P}^2$$

$$\mathbb{P}^2=\left( \begin{array}{c} ~09/81~~ 36/81 ~~ 36/81 ~~ 00/81 \\ ~04/81 ~~ 41/81 ~~ 02/81 ~~ 04/81 \\ ~~04/81 ~~ 31/81 ~~ 41/81 ~~ 04/81 \\ ~~00/81 ~~ 36/81 ~~ 36/81 ~~ 09/81 \\ \end{array}\right)$$

 

Lembrando que nosso $\mu_0=[0, 1, 0, 0]$ assim temos que:

$$\mu_2(4/81, 41/81, 32/81, 4/81)$$

 

Portanto temos que, $\mathbb{P}[X_2=0]=41/81$

iii) Para encontrarmos $\mu_{10}$ basta utilizarmos a equação de Chapman-Kolmogorov, desta forma temos que

$$\mu_{10}=\mu_0 \mathbb{P}^{10}$$

 

Para encontrarmos $\mathbb{P}^10$ usamos métodos computacionais, com $\mu_0=(1/4, 1/4, 1/4, 1/4)$

$$\mu_{10}=(0,05; 0,45; 0,45; 0,05)$$

 

iv) Idêntico ao item anterior, basta mudarmos $\mu_0=(1/4, 2/4, 0, 1/4)$

$$\mu_{10}=(0,05; 0,45; 0,45; 0,05)$$

 

Notemo que o resultado foi o mesmo do item anterior apesar de ter uma condição inicial distinta. Isso nos indica que após um determinado número de etapas nossa $\mu_n$ passa a não depender mais da sua condição inicial.

Exemplo 5.7:

Generalize o exemplo 5.6 para o caso de N bolas brancas e N bolas pretas.

Primeiramente definíamos as seguintes variáveis aleatórias

$B_{n}^1$={Pegar uma bola branca na urna um na etapa n.}

$B_{n}^2$={Pegar uma bola branca na urna dois na etapa n.}

Notemos que $B_n^1, B_{n}^2$, pode assumir apenas o valor 0 ou 1, pois vamos pegar uma única bola em cada etapa. Assim $B_n^1$ será 1 se pegarmos uma bola branca na urna 1 e zero caso contrário e o mesmo vale para $B_n^{2}$ só que para a urna 2.

Portanto temos que o nosso processo $X_n$ será dado da seguinte forma:

$$X_n=X_{n-1}-B_n^1+B_n^2$$

 

Ou seja o número de bolas brancas na etapa n depende do numero de bolas que tínhamos na etapa anterior, menos o $B_n^1$ que é o número de bolas brancas que tiramos da urna 1, mais $B_n^2$ que é o número de bolas brancas que tiramos da urna 2. Assim temos que:

$$\mathbb{P}[X_n=x_n| X_{n-1}=x_{n-1}]=\mathbb{P}[X_{n-1}-B_n^1+B_n^2=x_n| X_{n-1}=x_{n-1}]=$$

$$\mathbb{P}[B_n^2-B_n^1=x_n-X_{n-1}| X_{n-1}=x_{n-1}]=\mathbb{P}[B_n^2-B_n^1=x_n-x_{n-1}| X_{n-1}=x_{n-1}]$$

 

Como $B_n^1$ e $B_n^2$ assumem apenas valores 0 ou 1, então temos que $B_n^2-B_n^1$ pode assumir apenas o valores -1, 0 e 1.

Calculemos primeiramente então

$$\displaystyle \mathbb{P}[B_n^1=x|X_{n-1}=x_{n-1}] = \left\{ \begin{array}{c} 1-\frac{x_{n-1}}{N},~~~ x=0 \\ \frac{x_{n-1}}{3}~~~ x_1=1 .\end{array} \right.$$

$$\displaystyle \mathbb{P}[B_n^2=x|X_{n-1}=x_{n-1}] = \left\{ \begin{array}{c} \frac{x_{n-1}}{N},~~~ x=0 \\ 1-\frac{x_{n-1}}{3}~~~ x_1=1 .\end{array} \right.$$

 

Notemos que:

$$\mathbb{P}[B_n^{2}=0;B_n^{1}=1|X_{n-1}=x_{n-1}]=\mathbb{P}[B_n^{2}=0|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=1|X_{n-1}=x_{n-1}]=\left(\frac{x_{n-1}}{N}\right)^2$$

$$\mathbb{P}[B_n^{2}=0;B_n^{1}=0|X_{n-1}=x_{n-1}]+\mathbb{P}[B_n^{2}=1;B_n^{1}=1|X_{n-1}=x_{n-1}]=$$

$$\mathbb{P}[B_n^{2}=0|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=0|X_{n-1}=x_{n-1}]+ \mathbb{P}[B_n^{2}=1|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=1|X_{n-1}=x_{n-1}]$$

$$=\left[2\frac{x_{n-1}}{N}\left(1-\frac{x_{n-1}}{3}\right)\right]$$

$$\mathbb{P}[B_n^{2}=1;B_n^{1}=0|X_{n-1}=x_{n-1}]=\mathbb{P}[B_n^{2}=1|X_{n-1}=x_{n-1}]\mathbb{P}[B_n^{1}=0|X_{n-1}=x_{n-1}]=\left(1-\frac{x_{n-1}}{N}\right)^2$$

 

Desta forma temos que:

$$\displaystyle \mathbb{P}[B_n^2-B_n^1=x_{n}-x_{n-1}|X_{n-1}=x_{n-1}] = $$

$$\left\{ \begin{array}{c} \mathbb{P}[B_n^{2}=0;B_n^{1}=1|X_{n-1}=x_{n-1}]=\left(\frac{x_{n-1}}{N}\right)^2,~~~ x_{n}-x_{n-1}= -1 \\ \mathbb{P}[B_n^{2}=0;B_n^{1}=0|X_{n-1}=x_{n-1}]+\mathbb{P}[B_n^{2}=1;B_n^{1}=1|X_{n-1}=x_{n-1}]=\\ =\left[2\frac{x_{n-1}}{3}\left(1-\frac{x_{n-1}}{N}\right)\right],~ x_{n}-x_{n-1}=0 \\ \mathbb{P}[B_n^{2}=1;B_n^{1}=0|X_{n-1}=x_{n-1}]=\left(1-\frac{x_{n-1}}{N}\right)^2~~~ x_{n}-x_{n-1}=1\\ 0,~~~~~~~~~~~~~~~~~~~~~~~~~~ \mbox{caso contrário} .\end{array} \right.$$

 

Assim a matriz de transição do processo $X_n$ é dada

$$\mathbb{P}^2=\left( \begin{array}{c} ~~~0~~~~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~0~~~~~~~~~~~~0~~~~~~~~~~~~~~0 ~~~~~~~~~~~~~~~~~~~\cdots ~~~~~~~~~~~~0 \\ ~(1/N)^2~~~~~~~~~~~~~(2/N)(N-1)~~~~~~~(1-(1/N))^2~~~~~~~~~0~~~~~~~~~~~~~~0 ~~~~~~~~~ \cdots ~~~~~~~~ 0 \\ ~~0 ~~~~~~~~ (2/N)^2 ~~~~~~ (4/N^2)(N-2) ~~~~~~ (1-(2/N))^2 ~~~~~~~~~ 0 ~~~~~~~~~~ \cdots ~~~~~~~~ 0 \\ ~~0 ~~~~~~~~ 0 ~~~~~~~(3/N)^2 ~~~~~~~~ (8/N^2)(N-3) ~~~~~~ (1-(3/N))^2 ~~~~~~\cdots ~~~~ 0\\ ~~0 ~~~~~~~~ 0 ~~~~~~~~ 0 ~~~~~~~~ (4/N)^2 ~~~~~~~~~ (16/N^2)(N-4) ~~~~~~~~\cdots ~~~~~~ 0 \\ ~~~~\vdots ~~~~~~~~~~~~~~~~\vdots ~~~~~~~~~~~~~~~~ \vdots ~~~~~~~~~~~~ \vdots ~~~~~~~~~~ \vdots ~~~~~~~~~~~~~~~~ \vdots ~~~~~~~~~~~~ \vdots~ \\ 0 ~~~~~~~~~~~~ 0 ~~~~~~~~~~~~ 0 ~~~~~~~~~~ 0 ~~~~~~~~ 0 ~~~~ N/N)^2 ~~ (2N/N^2)(N-N)\\\end{array}\right)$$

 

Concluímos também que para o caso geral de N bolas a matriz permanece homogênea.

Exemplo 5.8:

Talvez o exemplo mais simples de cadeia de markov seja o exemplo de um movimento completamente determinado, o qual pode ser definido da seguinte forma seja $\mathbb{P}$ uma matriz de transição com apenas zeros e uns. Assim para cada estado i existe um estado g(i) tal que

$\mathbb{P}({i,g(i)})=1$ , $\mathbb{P}({i,j})=0,~~\forall j \neq g(i)$

Notemos que isso significa que se estamos no estado i necessariamente no próximo estado estaremos no estado g(i). Notemos que nesse caso basta sabermos o instante inicial e então saberemos todo o futuro, pois se $X_0=i$ então

$X_1=g(1)$, $X_2=g(g(1))=g^{(2)}(1),~~~~\cdots X_{n}=g^{(n)}(1)$

Observação:

Muitas vezes apenas olhando para a matriz de transição podemos verificar se as variáveis são $X_0, X_1, X_2,\cdots$ formão variáveis independentes e identicamente distribuídas, ou seja, com distribuição comum. Basta apenas que a matriz de transição seja homogênea e suas linhas sejam idênticas.