bc1414 Cadeias de Markov

Uma coleção {\{X_i\colon i\in T\}} de variáveis aleatórias que assumem valor num conjunto de estados {S} é um processo estocástico. O índice {i} é interpretado como tempo e o valor de {X_i} é o estado do processo no instante {i}. O processo é dito de tempo-discreto ou tempo-contínuo dependendo de {T} ser enumerável ou não, respectivamente. Cadeias de Markov são um caso particular de processo estocástico de tempo discreto e variávaeis discretas. No que segue fixamos {T={\mathbb N}} e a menos que seja dito o contrário {S\subset {\mathbb N}}. Nessas condições um processo estocástico é uma cadeia de Markov se vale a condição de Markov de que o estado futuro depende somente do estado atual e é independente dos estados passados

\displaystyle  \mathop{\mathbb P}\big(X_{n+1}=j~|~X_n=i, ~X_{n-1}=s_{n-1}, ,\cdots, ~X_{0}=s_{0}\big)= \mathop{\mathbb P}\big(X_{n+1}=j~|~X_n=i \big) \ \ \ \ \ (46)

e ela é dita homogênea se essa probabilidade não depende do tempo {n}, que é o caso que estudaremos a seguir.

Chamamos {X_0} de estado inicial e sua distribuição de distribuição inicial.

Uma cadeia de Markov é caracterizada por

  1. conjuntos de estados {S},
  2. distribuição inicial {\varrho_s \geq 0}, de modo que {\sum_{s\in S} \varrho_s =1},
  3. probabilidades de transição do estado {i} para o estado {j}, para todo {(i,j)\in S^2},

    \displaystyle p(i,j)\geq 0 \quad\textrm{ com }\quad \sum_{j\in S} p(i,j) =1

de modo que uma sequência de v.a. {\{X_t\}_{t\in{\mathbb N}}} com valores em {S} é uma cadeia de Markov homogênea com distribuição inicial {\rho} e probabilidade transição {p} se a distribuição conjunta de {X_0,\dots,X_n}, para todo {n\in{\mathbb N}}, é

\displaystyle  \mathop{\mathbb P} \big( X_0=s_0, X_1=s_1 ,\cdots, X_n=s_n \big) = \varrho_{s_0} \prod_{i=0}^{n-1} p(s_i,s_{i+1})  \ \ \ \ \ (47)

para toda escolha de {s_0,s_1,\dots,s_n\in S}. Dessa distribuição conjunta temos

\displaystyle  \mathop{\mathbb P}\left( X_{n+1}=s_{n+1}~\bigg| ~\bigcap_{\ell = 0}^n [ X_{\ell}=s_{\ell}]\right) = \frac{\mathop{\mathbb P}\left(\bigcap_{\ell = 0}^{n+1} [ X_{\ell}=s_{\ell}]\right)}{\mathop{\mathbb P}\left(\bigcap_{\ell = 0}^n [ X_{\ell}=s_{\ell}]\right)} =\frac{\varrho_{s_0} \prod_{i=0}^{n+1} p(s_i,s_{i+1})} {\varrho_{s_0} \prod_{i=0}^{n} p(s_i,s_{i+1})} = p(s_n,s_{n+1})

e

\displaystyle  \mathop{\mathbb P}\left( X_{n+1}=s_{n+1}~\bigg| ~ X_{n}=s_{n} \right) = \frac{\mathop{\mathbb P}\left( X_{n+1}=s_{n+1},~ X_{n}=s_{n} \right)} { \mathop{\mathbb P}(X_{n}=s_{n})} =\frac{\displaystyle \sum_{s_0,s_1,\dots,s_{n-1}} \varrho_{s_0} \prod_{i=0}^np(s_i,s_{i+1})} {\displaystyle \sum_{s_0,s_1,\dots,s_{n-1}} \varrho_{s_0} \prod_{i=0}^{n-1}p(s_i,s_{i+1})} = p(s_n,s_{n+1})

que é a condição de Markov (46). Ademais , fixado {n}, temos a partir dos itens 2 e 3 acima que

\displaystyle  \sum_{s_0\in S} \sum_{s_1\in S} \cdots \sum_{s_{n-1}\in S} \sum_{s_n\in S} \varrho_{s_0} \prod_{i=0}^{n-1} p(s_i,s_{i+1}) = \sum_{s_0\in S} \sum_{s_1\in S} \cdots \sum_{s_{n-1}\in S} \varrho_{s_0} \prod_{i=0}^{n-2}p(s_i,s_{i+1}) \sum_{s_n\in S} p(s_{n-1},s_n) =

\displaystyle  \sum_{s_0\in S} \sum_{s_1\in S} \cdots \sum_{s_{n-1}\in S} \varrho_{s_0} \prod_{i=0}^{n-2} p(s_i,s_{i+1}) = \cdots= \sum_{s_0\in S} \sum_{s_1\in S} \varrho_{s_0} p(s_0,s_1) = \sum_{s_0\in S} \varrho_{s_0} =1

portanto 47 é uma atribuição de probabilidades válida no espaço das realizações das {n} variáveis. A mesma dedução vale para qualquer valor de {n} portanto a definição da distribuição é consistente (o Teorema de Kolmogorov garante a existência das variáveis).

Exercício 87 Prove que o evento

\displaystyle X_{i_1}=s_{i_1},~X_{i_2}=s_{i_2},~\dots,X_{i_r}=s_{i_r}

ocorre com mesma probabilidade em todo espaço das realizações das variáveis com pelo menos {r} variáveis.

Como todas as cadeias desse capítulo são homogêneas nós omitiremos esse adjetivo daqui em diante.

Convencionamos que quando é dada uma definição de uma cadeia de Markov, as probabilidades de transição que não são dadas explicitamente são iguais a zero. Ademais, usualmente não damos a distribuição inicial {\varrho_s} porque ou esse parâmetro não é relevante ou é trivial (i.e., {\mathop{\mathbb P}(X_0=s)=1} para algum {s}).

A seguir daremos alguns exemplos de cadeias de Markov.

Exemplo 106 Numa pilha com {n} cartas de baralho distintas numeradas de {1} a {n}, definimos uma cadeia de Markov tomando um estado para cada permutação {\pi}, em que {\pi(i)} é a posição da {i}-ésima carta; {X_0} é a permutação identidade com probabilidade {1}.

Uma transição entre estados é obtida retirando a carta topo e colocando-á numa posição arbitrária escolhida uniformemente entre as cartas restantes na pilha, logo

\displaystyle p(\pi,\sigma) = \mathop{\mathbb P}\big( X_{t+1}=\sigma~|~X_t=\pi\big) = \frac 1n

para todo {t\in{\mathbb N}} e com a permutação {\sigma} obtida a partir da permutação {\pi} pelo processo descrito acima (nos casos em que {\sigma} não pode ser obtida pelo processo descrito vale {p(\pi,\sigma)=0}, como convencionamos). Um problema interessante é estimar o valor {n}, caso exista, para o qual a distribuição de {X_n} seja aproximadamente uniforme.

Exemplo 107 Sejam {Y_i\sim \mathrm{Bernoulli}(p)} variáveis aleatórias independentes, {X_0 = 0} e para {i>0}, tomemos {X_i = Y_i + Y_{i-1}}. Então

\displaystyle \mathop{\mathbb P} \big( X_{i+1}= 2 ~|~ X_i=1,~X_{i-1}=2 \big) =0,

enquanto que

\displaystyle \mathop{\mathbb P}\big( X_{i+1}= 2 ~|~ X_i=1,~ X_{i-1}=0 \big) =p,

logo {\{X_i\}} não é uma cadeia de Markov por não satisfazer (46).

Exemplo 108 Definimos uma cadeia de Markov se tomamos o conjunto de estados como sendo os inteiros positivos, {S={\mathbb N}\setminus \{0\}}, o estado inicial {X_0=1} com probabilidade {1} e as transições probabilidades

\displaystyle  \begin{array}{rcl}  && p(i,1) = \frac 1{i+1}\\ && p(i,i+1) = \frac i{i+1} \end{array}

para todo inteiro {i\geq 1}.

Exemplo 109 (passeio aleatório) Tomemos o conjunto de estados como os inteiros, {S={\mathbb Z}}, o estado inicial {X_0=0} com probabilidade {1} e as transições de estados têm as probabilidades

\displaystyle  \begin{array}{rcl}  && p(i,i-1) = 1-p\\ && p(i,i+1) = p \end{array}

para todo inteiro {i} e algum {p\in (0,1)}. Essa cadeia é um passeio aleatório pelos inteiros.

Exemplo 110 Seja {G} um grafo finito. Definimos uma cadeia de Markov tomando {S} como o conjunto de vértices do grafo e as transições são definidas de modo que se {X_t=v} então {X_{t+1}} é qualquer vértice adjacente a {v} com probabilidade uniforme. Esse tipo de cadeia de Markov é conhecida como passeio aleatório num grafo.

Exemplo 111 (Cadeia de Markov não-homogênea) Suponha {Y_1,Y_3,Y_5,\dots,Y_{2i+1},\dots} v.a. independentes e identicamente distribuídas com

\displaystyle  \mathop{\mathbb P}(Y_{2k+1}=1) = \mathop{\mathbb P}(Y_{2k+1}=-1) =\frac 12

para todo {k\geq 0}. Agora, tomemos {Y_{2k} = Y_{2k+1}Y_{2k-1}} para todo {k>0}.

A sequência de v.a. {\{Y_i\}_{i\geq 1}} não define uma cadeia de Markov pois

\displaystyle \mathop{\mathbb P}(Y_{2k+1}=1~|~Y_{2k}=-1) = \frac 12

enquanto que

\displaystyle \mathop{\mathbb P}(Y_{2k+1}=1~|~Y_{2k}=-1,~Y_{2k-1}=-1)=1.

No entanto, {Z_n = (Y_n,Y_{n+1})} é uma cadeia de Markov não homogênea pois, por exemplo

\displaystyle  \mathop{\mathbb P}\big(Z_{n+1} =(1,1)~\big|~Z_n=(1,1) \big)= \begin{cases} 1/2 & \textrm{ se } n \textrm{ par}\\ 1 & \textrm{ se } n \textrm{ \'impar.} \end{cases}

Exemplo 112 (Cadeia de Markov não-homogênea) Consideremos uma caixa com {v} bolas vermelhas e {a} bolas azuis e o processo de retirar aleatoriamente uma bola da caixa sem reposição. Seja {X_i} o número de bolas vermelhas na caixa na {i}-ésima rodada. A probabliade de transição não depende só do número de bolas vermelhas (estado), mas também depende do momento {i}.

Exemplo 113 (ruína do jogador) Em um jogo, o jogador ganha 1 real com probabilidade {p}, ou perde 1 real com probabilidade {1-p}, de modo independente a cada rodada de até que sua fortuna seja {0} ou {n}, nesse momento ele pára de jogar.

Denotamos a quantia do jogador no instante {t} pela variável {X_t} e temos que

\displaystyle  \begin{array}{rcl}  && p(0,0) = p(n,n) = 1\\ && p(i,i+1) = p ~ \textrm{ e }~ p(i,i-1) = 1-p, \end{array}

para {1\leq i \leq n}, são as transições de estado de uma cadeia de Markov.

Um problema interessante para o jogador é conhecer a probabilidade de chegar ao estado {n} antes do estado {0}, esse é um problema clássico da probabilidade conhecido como o problema da ruína do jogador.

Seja {P_i} a probabilidade de o jogador chegar antes ao estado {n} dado que {X_0=i}. Então

\displaystyle  P_i = pP_{i+1}+(1-p)P_{i-1}

para todo {i\in\{1,\dots,n\}}, que equivale a

\displaystyle  pP_{i}+ (1-p)P_{i} = pP_{i+1}+(1-p)P_{i-1}

para todo {i\in\{1,\dots,n\}}. Para facilitar usaremos {q=1-p.} Segue da igualdade acima que

\displaystyle  \begin{array}{rcl}  P_{i+1} - P_i &=& \frac qp (P_i-P_{i-1})\\ &=& \left(\frac qp\right)^2 (P_{i-1}-P_{i-2})\\ &=& \cdots\\ &=& \left(\frac qp\right)^i (P_1-P_0). \end{array}

donde concluímos, usando que {P_0=0}, que

\displaystyle  P_{i+1} = P_i + \left(\frac qp\right)^i P_1  \ \ \ \ \ (48)

para todo {i\in\{1,\dots,n\}}. Iterando

\displaystyle  \begin{array}{rcl}  P_{i+1} &=& P_i + \left(\frac qp\right)^i P_1\\ &=& P_{i-1} + \left( \left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1\\ &=& P_{i-2} + \left( \left(\frac qp\right)^{i-2}+\left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1\\ &=& \cdots \\ &=& \left( 1+\frac qp+\cdots+ \left(\frac qp\right)^{i-2}+\left(\frac qp\right)^{i-1}+\left(\frac qp\right)^i \right)P_1 \end{array}

e de {P_n=1} temos

\displaystyle  1 = \left( 1+\frac qp+\cdots+ \left(\frac qp\right)^{n-2}+\left(\frac qp\right)^{n-1} \right)P_1.

Se {p\neq q} então a soma acima é de uma progresão geométrica cuja valor é {{1-(q/p)}/{1-(q/p)^n}} logo

\displaystyle  P_1 = \begin{cases} \displaystyle\frac 1n & \textrm{ se } p=q\\ \vspace*{-.3cm} \\ \displaystyle \frac {1-(q/p)}{1-(q/p)^n} & \textrm{ se } p\neq q. \end{cases}

e substituindo em (48)

\displaystyle  P_i = \begin{cases} \displaystyle \frac in & \textrm{ se } p=q\\\vspace*{-.3cm} \\ \displaystyle \frac {1-(q/p)^i}{1-(q/p)^n} & \textrm{ se } p\neq q. \end{cases}

Notemos que a probabilidade do jogador ficar “infinitamente rico”, i.e., {P_i(n)} quando {n\rightarrow \infty}, é {0} se {p \leq 1/2} pois {\frac in ,~ \frac {1-(q/p)^i}{1-(q/p)^n}} tendem a {0}. Por outro lado, se {p >1/2} então {(q/p)^n\rightarrow 0} quando {n\rightarrow \infty} logo {P_i \rightarrow 1-(q/p)^i >0}.

Usando R:



simulaRuina=function(n=10,p=1/2,estado=5)
{
  cat(estado)
  m<-0
  while ( estado < n & estado > 0) {
    proxEstado <- estado + sample(x=c(-1,1), size=1, prob=c(1-p,p))
    cat(" -> ",proxEstado)
    m <- m+1
    estado <- proxEstado 
  }
  cat("\n",m," passos","\n")
}

simulaRuina()

simulaRuina(10,1/3,3)



simulaRuina() simula transições aleatórias até atingir o estado 10 ou 0 a partir do 5 com probabilidade de ganho 1/2;

simulaRuina(10,1/3,3) simula até atingir o estado 10 ou 0 a partir do 3 com probabilidade de ganho 1/3;

também devolve o número de passos esfetuados.

Exemplo 114 Consideremos a cadeia de Markov sobre {S=\{0,1,\dots,n\}} com estado inicial {X_0=0} e as transições de estados têm as probabilidades

\displaystyle  \begin{array}{rcl}  &&p(0,1) = 1 = p(n,n) \\ &&p(j,j+1) = 1/2\\ &&p(j,j-1) = 1/2 \end{array}

para todo inteiro {j\geq 1}. Vamos estimar o número esperado de passos até a cadeia chegar ao estado {n}. Seja {Y_j} o número de passos para atingir {n} a partir de {j}. Se o estado atual é {j>0} e o próximo {j-1} então {Y_j = 1+ Y_{j-1}}, senão {Y_j = 1+ Y_{j+1}}, portanto, por (45)

\displaystyle  \mathop{\mathbb E}( Y_j) = \mathop{\mathbb E}\big( Y_{j-1}+1\big) \frac 12 +\mathop{\mathbb E}\big(Y_{j+1}+1\big)\frac 12 = \frac 12 \left( \mathop{\mathbb E} Y_{j-1} +\mathop{\mathbb E} Y_{j+1} \right) +1

e temos

\displaystyle  \begin{cases} 2\mathop{\mathbb E}( Y_j) = \mathop{\mathbb E} (Y_{j-1}) + \mathop{\mathbb E}( Y_{j+1}) +2, &\textrm{ se } 0<j<n\\ \mathop{\mathbb E} (Y_0) = \mathop{\mathbb E} (Y_{1})+1,& \\ \mathop{\mathbb E} (Y_n) = 0. \end{cases}

cuja solução é {\mathop{\mathbb E} (Y_j)=n^2-j^2} (verifique). Finalmente, {\mathop{\mathbb E} (Y_0) = n^2}. Pela desigualdade de Markov, equação (24), a probabilidade da cadeia não chegar no estado {n} em {2n^2} passos é

\displaystyle  \mathop{\mathbb P}\big( Y_0 \geq 2n^2 \big) \leq \frac{\mathop{\mathbb E}( Y_0)}{2n^2} = \frac 12 \ \ \ \ \ (49)

e, analogamente, tende a zero a probabilidade da cadeia não chegar no estado {n} em {n^2\omega(n)} passos qualquer que seja {\omega(n)} que tenda ao infinito com {n}, por exemplo, {\omega(n) = \log\log n}.

Usando R:


simulaMCN = function (n , estado =0)
{
  cat ( estado )
  m <-0
  
  while ( estado < n ) {
    
    if ( estado > 0) {
      proxEstado <- estado + sample (x=c ( -1 ,1) , size =1 , prob =c (1 / 2 ,1 / 2) )}
    else { proxEstado <- 1 }
    cat (" -> " , proxEstado )
    
    m <- m +1
    estado <- proxEstado
  }
  cat ("\ n" ,m ," passos " ," \n")
}







simulaMCN(10) simula até atingir o estado 10 a partir do 0;

simulaMCN(10,3) simula até atingir o estado 10 a partir do 3;

também devolve o número de passos esfetuados.

Exemplo 115 Suponha que a ocorrência de chuva num dia é determinada pela condição do clima nos dois dias anteriores do seguinte modo: amanhã chove com probabilidade {0,7} se chove nos dois dias anteriores; amanhã chove com probabilidade {0,5} se chove hoje mas não choveu ontem; amanhã chove com probabilidade {0,4} se não chove hoje mas choveu ontem; amanhã chove com probabilidade {0,2} se não chove nos dois dias anteriores.

Identificamos cada uma das quatro situações acima com seguintes estados {\mathbf{1}} se choveu hoje e ontem; {\mathbf{2}} se choveu hoje mas não choveu ontem; {\mathbf{3}} se não choveu hoje mas choveu ontem; e {\mathbf{4}} se não choveu nem hoje e nem ontem.

O estado no dia {X_{n+1}} depende da condição nos dias anteriores; assim a transição de {X_n=1} para {X_{n+1}=3}, por exemplo, ocorre quando não chove amanhã ({n+1}) mas choveu hoje, dado que choveu hoje ({n}) e ontem ({n-1)}, nessa configuração a probabilidade de não-chuva amanhã se choveu hoje e ontem é {1-0,7=0,3}. O seguinte diagrama ilustra as transições de estados com suas probabilidades.

Exercício 88 Um dado é lançado repetidamente. Quais das seguintes sequências de variáveis formam um cadeia de Markov?

  1. {X_n} é o maior resultado até a {n}-ésima rodada;
  2. {Y_n} é a quantidade de {6} em {n} rodadas;
  3. no instante {r}, {Z_r} é o tempo desde o {6} mais recente;
  4. no instante {r}, {W_r} é o tempo até o próximo {6}.

Exercício 89 Se {\{X_n\}_n} é uma cadeia de Markov, quais das seguintes sequências é uma cadeia de markov?

  1. {\{X_{m+r}\}_{r\geq 0}}, para {m} fixo;
  2. {\{X_{2m}\}_{m\geq 0}};
  3. {\{(X_{n},X_{n+1})\}_{n\geq 0}}.

Exercício 90 (Equação de Wald e ruína do jogador) Sejam {Z_1,~Z_2,\dots} v.a. independentes, identicamente distribuídas, e com esperança {\mathop{\mathbb E}(Z)} finita. Chamamos a v.a. {N} de tempo de parada para a sequência {\{Z_i\}_{i\geq 1}} se o evento {[N=n]} é independente de {Z_t} para {t>n}, para todo {n}.

Prove que se {N} tem esperança {\mathop{\mathbb E}(N)} finita, então

\displaystyle   \mathop{\mathbb E} \left(\sum_{i=1}^N X_i \right) = \mathop{\mathbb E}(N)\mathop{\mathbb E}(Z). \ \ \ \ \ (50)

No exemplo 113, seja {i} o estado inicial {D_i} o tempo de duração do jogo, ou seja, o tempo esperado até a cadeia atingir o estado {0} ou o estado {n}. Assuma que as esperanças sejam finitas e use a equação (50) para determinar {D_i}.

— Representação matricial, transiência e recorrência —

A matriz {P = (p_{i,j})} definida pelas probabilidades de transição {p_{i,j} = p(i,j)} é dita matriz de transições da cadeia de Markov. Ainda, para {k\in{\mathbb N}}, se

\displaystyle  p_{i,j}^{(k)} \stackrel{\text{\tiny def}}{=} \mathop{\mathbb P}\big(X_{t+k}=j~|~X_t=i\big)

é a transição do estado {i} para o estado {j} em {k} passos então

\displaystyle  p_{i,j}^{(k)} = \sum_{s\in S} p_{i,s} p_{s,j}^{(k-1)}

para todo inteiro {k>1} e com { p_{i,j}^{(1)} = p_{i,j}} e convencionamos { p_{i,j}^{(0)} = \delta_i(j)}. Logo a {k}-ésima potência da matriz {P} é

\displaystyle  P^k = (p_{i,j}^{(k)}). \ \ \ \ \ (50)

Notemos que {\sum_j p_{i,j}^{(k)}=1}, para qualquer {k\in{\mathbb N}}. Uma matriz cujas entradas são não-negativas e as linhas somam {1} é uma matriz estocástica.

Exercício 91 Verifique que se {P} é estocástica então {P^n} também é estocástica.

Notemos que {\mathop{\mathbb P}(A,~B ~|~ C) = \mathop{\mathbb P}(A ~|~B,~ C) \mathop{\mathbb P}(B ~|~ C)} e usando esse fato podemos deduzir

\displaystyle  \begin{array}{rcl}  p_{i,j}^{(k+t)} &=& \mathop{\mathbb P} \big( X_{k+t}=j~|~X_0=i \big) \\ &=& \sum_{s\in S} \mathop{\mathbb P} \big( X_{k+t}=j,~X_k=s~|~X_0=i \big) \\ &=& \sum_{s\in S} \mathop{\mathbb P} \big( X_{k+t}=j~|~X_k=s,~X_0=i \big) \mathop{\mathbb P}\big(X_k=s~|~X_0=i\big)\\ &=& \sum_{s\in S} p_{s,j}^{(t)}p_{i,s}^{(k)} \end{array}

portanto, vale a seguinte identidade que é bastante útil.

Lema 17 (Identidade de Chapman–Kolmogorov) Se {P=(p_{i,j})} é uma matriz de transição,

\displaystyle   p_{i,j}^{(k+t)} = \sum_{s\in S} p_{i,s}^{(k)}p_{s,j}^{(t)} \ \ \ \ \ (51)

para quaisquer {i,~j\in S}, ou ainda, {P^{k+t} = P^kP^t}.

A evolução da cadeia é determinada pela matriz {P} e boa parte dos estudos das cadeias de Markov são reduzidas ao estudo das propriedades algébricas desses elementos.

Exemplo 116 No caso do exemplo 115 dado que choveu na segunda-feira e na terça-feira, qual é a probabilidade de chover na quinta?

A matriz toda está descrita abaixo

\displaystyle  P = \begin{pmatrix} 0,7 & 0 & 0,3 & 0\\ 0,5 & 0 & 0,5 & 0\\ 0 & 0,4 & 0 & 0,6\\ 0 & 0,2 & 0 & 0,8 \end{pmatrix}

A matriz de transição em 2 passos é a matriz

\displaystyle  P^2 = \begin{pmatrix} 0,49 & 0,12 & 0,21 & 0,18\\ 0,35 & 0,20 & 0,15 & 0,30\\ 0,20 & 0,12 & 0,20 & 0,48\\ 0,10 & 0,16 & 0,10 & 0,64 \end{pmatrix}

e chover na quinta equivale ao processo estar no estado {0} ou no estado {1}, logo a probabilidade é {p_{0,0}^{(2)} + p_{0,1}^{(2)}=0,61}.

Usando R:


#Algoritmo para simulacao de cadeia de Markov nos primeiros N passos,
# daodo M[,]  matriz de transicoes
#
#1. Escolha um estado inicial X0 = j de arcordo com a distribuicao inicial.
#2. i <- 1
#3. Repita N vezes
#4.    Gerar Y_j  com distribuicao M[j,]
#5.    Xi <- Yj,
#6.     j <- Xi
#7.     i <- i+1

simulaMC=function(N=100)
{
  # matriz transicao
  trans = matrix(c( 
    0.7,0,0.3,0,
    0.5,0,0.5,0,
    0,0.4,0,0.6,
    0,0.2,0,0.8
    ), ncol=4, byrow=TRUE);

  # estado inicial
  estado =  sample(x=1:ncol(trans), size=1, prob=c(1/4,1/4,1/4,1/4))
  cat(estado)
  
  # N passos da cadeia
  for (i in 1:N) {

    proxEstado <- sample(x=1:ncol(trans), size=1, prob=trans[estado,])
      
    cat(" -> ",proxEstado)

    estado <- proxEstado
    
  }
  cat("\n")
}




simulaMC() simula transições aleatórias até atingir 100 passos; simulaMC(10) simula até atingir 10 passos.

Exercício 92 Se {\{X_n\}_n} é uma cadeia de Markov com matriz de transições

\displaystyle  P = \begin{pmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 1/2 & 0 \\ 1 & 0 & 0 \end{pmatrix}

e {f} é dada por {f(0)=0} e {f(1)=f(2)=1}, então {Y_n = f(X_n)} é uma cadeia de Markov?

Exercício 93 Mostre que a sequência de v.a. {\{Y_i\}_{i\geq 1}} do exemplo 114 é de variáveis independentes 2-a-2, conclua que {p_{i,j}^{(n)} = 1/2} e que vale a identidade de Chapman–Kolmogorov (51) mesmo não sendo uma cadeia de Markov.

Classificação de estados

Os estados de uma cadeia de Markov são classificados em dois tipos fundamentais. Um estado é recorrente (ou, persistente) se, uma vez tendo estado nele, é certo que a cadeia eventualmente volta a ele, caso contrário, i.e. a probabilidade de retorno é menor que {1}, então o estado é dito transiente (ou, transitório). Quando o estado é recorrente, a cadeia visita-o infinitas vezes pois a cada vez que chega no estado é como um reinicio, ela voltará a ele com probabilidade {1}, e no caso transiente o estado é visitado um número finito de vezes. Notemos que isso leva a conclusão de que se {|S|} é finito então pelo menos um estado é recorrente.

Seja {f_{i,j}^{(n)}} a probabilidade do evento “primeira passagem por {j} a partir do {i} em {n} passos”

\displaystyle  [X_0=i]\cap [X_1\neq j] \cap [X_2\neq j] \cap \cdots \cap [X_{n-1}\neq j]\cap [X_n=j]

assim {f_{i,i}^{(n)}} é a probabilidade do primeiro retorno a {i} em {n} passos e definimos

\displaystyle  f_{i,i} \stackrel{\text{\tiny def}}{=} \sum_{n>0} f_{i,i}^{(n)}

que é a probabilidade de eventualmente retornar ao estado de origem {i}. Com essa definição, um estado {i} é recorrente se {f_{i,i}=1}, caso contrário {f_{i,i}<1} e chamamos {i} de transiente.

Seja {I_n} a v.a. indicadora do evento {[X_n=i]}. Então a soma para todo {n\geq 0} das variáveis {I_n} é o número de vezes que a cadeia visita o estado {i}, que afirmamos acima ser finito se e só se {n} é transiente. De fato, pelo exercício 49,

\displaystyle  \mathop{\mathbb E} \left( \sum_{n \geq 0}I_n~\bigg|~ X_0=i \right)= \sum_{k\geq 1} \mathop{\mathbb P}\bigg( \big|\{n\geq 1\colon X_n= i\}\big|\geq k ~\big|~ X_0=i \bigg)

logo

\displaystyle \mathop{\mathbb E} \left( \sum_{n \geq 0}I_n~\bigg|~ X_0=i \right)=\sum_{k\geq 1} (f_{i,i})^k = \begin{cases} \frac{f_{i,i}}{1-f_{i,i}} & \textrm{ se }f_{i,i}<1\\ \infty &\textrm{ se }f_{i,i} =1 \end{cases}

Essa classificação de estados pode ser caracterizada pelas probabilidades de transições da maneira que deduziremos a seguir.

Lema 18 O estado {i} é

  • recorrente se e só se {\displaystyle\sum_{n\geq 0} p_{i,i}^{(n)} = \infty}.

  • transiente se e só se {\displaystyle\sum_{n\geq 0} p_{i,i}^{(n)} < \infty}.

Demonstração: Pela linearidade da esperança,

\displaystyle  \mathop{\mathbb E} \left( \sum_{n\geq 0}I_n~\bigg|~ X_0=i \right)= \sum_{n\geq 0} \mathop{\mathbb E} \left( I_n~\bigg|~ X_0=i \right)= \sum_{n\geq 0} \mathop{\mathbb P} \left( X_n=i~\big|~ X_0=i \right)= \sum_{n\geq 0} p_{i,i}^{(n)}

e o lema segue das considerações acima. \Box

No caso {f_{i,i}=1}, temos uma função de massa de probabilidade {\{f_{i,i}^{(n)}\}_{n>0}} para o tempo de recorrência (ou retorno) para {i}, cuja média é chamada de tempo médio de recorrência (ou tempo médio de retorno) para {i}

\displaystyle  \mu_i = \sum_{n>0}nf_{i,i}^{(n)}.

No caso de {i} transiente convencionamos {\mu_i = \infty}.

Dado que o retorno ao estado inicial {i} é certo, é natural perguntar se o tempo médio de retorno é finito. No caso {\mu_i=\infty} o estado {i} é dito recorrente nulo, no caso de média finita, {\mu_i < \infty}, o estado {i} é dito recorrente positivo.

Exemplo 117 No exemplo 109, {S={\mathbb N}\setminus \{0\}}, {X_0=1}, {p(i,1) = \frac 1{i+1}} e { p(i,i+1) = \frac i{i+1}} para todo inteiro {i\geq 1}. A probabilidade de não retornar ao estado {1} nos {n-1} primeiros passos é

\displaystyle \prod_{j=1}^{n-1} \frac j{j+1} = \frac 1{n}

portanto (exerc. 25) a probabilidade de nunca voltar ao estado {1} é ~{0} e a probabilidade de voltar ao {1} no {n}-ésimo passo é

\displaystyle  f_{1,1}^{(n)} = \frac 1n \frac 1{n+1}

e, a partir disso, o tempo médio de recorrência do estado {1} é

\displaystyle  \mu_1 = \sum_{n>0}nf_{1,1}^{(n)} = \sum_{n>0}\frac 1{n+1} = \infty.

Em resumo, {1} é recorrente nulo.

Exercício 94 Prove que numa cadeia de Markov sobre um conjunto finito de estados, pelo menos um estado é recorrente e todo estado recorrente é positivo

Exercício 95 Prove que

\displaystyle   p_{j,k}^{(n)} = \sum_{t=1}^nf_{j,k}^{(t)}p_{k,k}^{(n-t)}. \ \ \ \ \ (52)

Conclua que se {j} é recorrente, então {\displaystyle\sum_{n\geq 0} p_{i,j}^{(n)} = \infty} para todo {i} tal que {f_{i,j}>0}.

Conclua também que se {j} é transiente, então {\displaystyle\sum_{n\geq 0} p_{i,j}^{(n)} < \infty} para todo {i} e que, portanto, {p_{i,j}^{(n)}\rightarrow 0}, quando {n\rightarrow\infty}, para todo {i}.

Exercício 96 Defina a variável aleatória

\displaystyle   T_j \stackrel{\text{\tiny def}}{=} \min \{n\geq 1\colon X_n = j\} \ \ \ \ \ (53)

com a convenção de que se {j} não é visitado então {T_j=\infty}. Verifique que {j} é transiente se e só se {\mathop{\mathbb P}(T_j=\infty~|~X_0=j)>0} e, nesse caso, {\mathop{\mathbb E}(T_j~|~X_0=j) = \infty}. Verifique também que

\displaystyle \mu_i = \mathop{\mathbb E}(T_i~|~X_0=i).

Exercício 97 Defina a variável aleatória

\displaystyle V_j = \big|\{n\geq 1\colon X_n=j\}\big|

e defina {\eta_{i,j} \stackrel{\text{\tiny def}}{=} \mathop{\mathbb P}(V_j=\infty~|~X_0=j)}. Prove que

\displaystyle  \eta_{i,i} = \begin{cases} 1, & \textrm{ se }i\textrm{ recorrente},\\ 0, & \textrm{ se }i\textrm{ transiente}. \end{cases}

e que

\displaystyle  \eta_{i,j} = \begin{cases} \mathop{\mathbb P}(T_j < \infty~|~X_0=j),& \textrm{ se }i\textrm{ recorrente},\\ 0, & \textrm{ se }i\textrm{ transiente}. \end{cases}

para {T_j} definido no exercício acima.

Exercício 98 Seja {A} um subconjunto de estados e defina

\displaystyle  T_A \stackrel{\text{\tiny def}}{=}\min\{n\geq 1 \colon X_n\in A\}

\displaystyle  \eta_j \stackrel{\text{\tiny def}}{=} \mathop{\mathbb P}\big(T_A<\infty~|~X_0=j\big).

Mostre que {\eta_j=1} se {j\in A} e

\displaystyle  \eta_j = \sum_{s\in S} p_{j,s}\eta_s

se {j\not\in A}. Agora defina

\displaystyle \xi_j \stackrel{\text{\tiny def}}{=} \mathop{\mathbb E}\big(T_A~|~X_0=j\big)

e mostre que {\xi_j =0} se {j\in A} e que

\displaystyle  \xi_j = 1+\sum_{s\in S} p_{j,s}\xi_s

se {j\not\in A}.

Os estados {0} e {n} da cadeia do exemplo 107, quando são atingidos a cadeia não muda mais de estado; nesses casos chamamos tais estados de absorvente, que é um estado recorrente positivo.

Exercício 99 Seja {s} um estado absorvente numa cadeia de Markov tal que para todo estado {i} da cadeia {p_{i,s}^{(n)}>0}, para algum {n=n(i)}. Mostre que todos os estados, a não ser {s}, são transientes.

Exemplo 118 Na cadeia representada pelo esquema abaixo o estado {4} é absorvente, os estados {0} e {3} são transiente e os estados {1} e {2} são recorrentes

Periodicidade

Numa cadeia de Markov que pode ser representada como

se {X_0=0} então {p_{0,0}^{(n)}>0} só pode ocorrer na cadeia em instante {n} da forma {n=2k}, {n=4k}, {n=6k}. Para o estado {1}, as probabilidades de retorno positivas só ocorrem para {n=2k}, {n=4k}. Para o estado {2} ocorre o mesmo fenômeno que no estado {1} e o caso do estado {3} é semelhante ao caso do estado {0}.

O período de um estado {i} numa cadeia de Markov é

\displaystyle \tau(i) = \mathrm{mdc} \left\{ n\colon p_{i,i}^{(n)}>0\right\}

Caso {\tau(i) >1} dizemos que {i} é periódico, nesse caso {p_{i,i}^{(n)}=0} a menos que {n} seja múltiplo de {\tau_i}, e caso {\tau(i)=1} dizemos que {i} é aperiódico . No exemplo acima todos os estados são periódicos de período {t=2}.

Observação 6 Notemos que para todo estado {k} da cadeia devem existir instantes {m} e {n} tais que

\displaystyle   p_{0,k}^{(n)},~ p_{k,0}^{(m)} >0 \ \ \ \ \ (55)

e como {p_{0,0}^{(n+m)} \geq p_{0,k}^{(n)}p_{k,0}^{(m)} >0} devemos ter que {t} divide {n+m}. Fixando {m} concluímos que todo {n} para o qual {p_{0,k}^{(n)}>0} é da forma {a+vt} para {0\leq a < t} inteiro. Assim, podemos particionar {S} em {S_0, S_1, \dots, S_{t-1}} (nesse caso {S_0=\{0,2\}} e {S_1=\{1,3\}}) para os valores de {a} acima de modo que se {k\in S_a} então {p_{0,k}^{(n)}=0} a menos que {n=a+vt}. Agora consideramos os estados na ordem {S_0, \dots, S_{t-1}} ciclicamente e um passo da cadeia sai de um estado para um estado na classe a direita, e a cada {t} passos a cadeia está de volta à mesma classe.

— Classificação das cadeias —

A condição {p_{i,j}^{(n)}>0} para algum {n} significa que a partir do estado {i} a cadeia eventualmente atinge o estado {j} em {n} passos; nesse caso dizemos que {j} é acessível a partir de {i} e escrevemos {i\rightarrow j}. Quando {j} não é acessível a partir de {i} a probabilidade da cadeia chegar em {j} saindo de {i} é

\displaystyle  \mathop{\mathbb P}\left( \bigcup_{n\geq 0}[X_n=j] ~\big|~X_0=i \right)\leq \sum_{n\geq 0}\mathop{\mathbb P}\left( X_n=j ~|~X_0=i \right) =0.

Escrevemos {i \leftrightarrow j} se {i\rightarrow j} e {j\rightarrow i} e dizemos que os estados {i} e {j} se comunicam. Deixamos para o leitor a verificação de que { \leftrightarrow} define uma relação de equivalência sobre {S}, i.e.,

  1. {i \leftrightarrow i},
  2. se {i \leftrightarrow j}, então {j \leftrightarrow i},
  3. se {i \leftrightarrow k} e {k \leftrightarrow j} então {i \leftrightarrow j},

portanto, ela particiona {S} em classes de equivalência. A importância dessa partição é pelo fato enunciado no exercício a seguir.

Exercício 100 Prove que recorrência e transiência são propriedades de classe de equivalência de {\leftrightarrow}, isto é, dois estados que se comunicam tem a mesma classificação. Ademais, estados que se comunicam têm o mesmo período.

Um conjunto {C\subset S} é é irredutível se {i\leftrightarrow j} para todos {i,~j\in C}, portanto, cada classe é um subconjunto irredutível.

Quando um conjunto não é irredutível, dizemos redutível. Quando há uma única classe de equivalência dizemos que a cadeia é uma cadeia de Markov irredutível.

Um cadeia (ou um conjunto de estados) irredutível é

  • aperiódica se todos os seus estados o forem;
  • periódica se todos os seus estados o forem;
  • transiente se todos os seus estados o forem;
  • recorrente se todos os seus estados o forem.

Exemplo 119 Uma cadeia de Markov com estados {\{1,2\}} e matriz de transições

\displaystyle  P= \begin{pmatrix} 1&0\\1/2&1/2 \end{pmatrix}

não corresponde a uma cadeia irredutível pois para todo inteiro {k>0}

\displaystyle  P^k= \begin{pmatrix} 1&0\\\frac {2^{k}-1}{2^k}& \frac 1{2^k} \end{pmatrix}

portanto {1\not\rightarrow 2}.

Exemplo 120 Uma cadeia com estados {\{1,2,3\}} e matriz de transições

\displaystyle  P= \begin{pmatrix} 1/3&2/3&0\\ 1&0&0\\ 0&0&1 \end{pmatrix}

é redutível pois P^k é da forma

\displaystyle  P^k= \begin{pmatrix} a&b&0\\ c&d&0\\ 0&0&1 \end{pmatrix}

para a,b,c,d >0 e todo inteiro {k>0}.

No exemplo 115 é fácil ver a partir do diagrama que a cadeia é irredutível. A cadeia do exemplo 107, claramente, não é irredutível por causa dos estados absorventes {0} e {n}. Toda cadeia com pelo menos dois estados e com pelo menos um deles absorvente é uma cadeia redutível.

Um conjunto {C\subset S} é fechado se {p_{i,j}=0} sempre que {i\in C} e {j\not\in C}.

Exemplo 121 No caso da cadeia com matriz de transições

\displaystyle P = \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/4 & 3/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \end{pmatrix}

A cadeia é redutível e o conjunto dos estados têm três classes de equivalência de comunicação {S=\big\{\{1,2\},\{3,4\},\{5,6\}\big\}}. Os conjuntos {\{1,2\}} e {\{5,6\}} são irredutíveis e fechados. Os estados {3}, e {4} são transientes pois uma vez que a cadeia sai de um deles em direção aos conjuntos fechados, ela não volta mais a esses estados. Todos os estados têm período {1} portanto a cadeia é aperiódica. Ainda

\displaystyle  f_{1,1}^{(1)} = \frac 12 \quad \textrm{ e } \quad f_{1,1}^{(n)} = \frac 12 \left( \frac 34 \right)^{n-2} \frac 14~(n\geq 2)

portanto {\mu_1 = 3}.

Exemplo 122 (passeio aleatório) Vejamos o caso do passeio aleatório do exemplo 110, onde

\displaystyle  p_{i,i+1}=p=1-p_{i,i-1}.

Claramente, a cadeia é irredutível logo todos os estados são ou recorrentes ou transientes. Fixemo-nos no estado {0} e vamos determinar {\displaystyle \sum_{n\geq 1} p_{0,0}^{(n)}}.

Como é impossível estar num estado par com um número ímpar de movimentos

\displaystyle p_{0,0}^{(2n-1)}=0,~\textrm{ para }n\geq 1.

Após {2n} passos a cadeia estará de volta em {0} se e só se metade dos passo foi num sentido (e.g., do estado atual para o maior, o que ocorre com probabilidade {p}) e metade no sentido oposto, portanto

\displaystyle  p_{0,0}^{(2n)} = \binom{2n}n p^n(1-p)^n = \frac{(2n)!}{n!}{n!} p^n(1-p)^n \sim \frac{(4p(1-p))^n}{\sqrt{\pi n}}

onde {a_n\sim b_n} significa que {\displaystyle \lim_{n\rightarrow\infty}(a_n/b_n)=1} e {n!\sim n^{n+1/2}\mathrm{e}^{-n}\sqrt{2\pi}}. Agora, se {a_n\sim b_n} então {\sum_n a_n} converge se, e só se, {\sum_n b_n} converge, portanto precisamos estudar a convergência de

\displaystyle  \sum_{n\geq 1} \frac{(4p(1-p))^n}{\sqrt{\pi n}}.

No numerador {4p(1-p) \leq 1} e vale a igualdade se e somente se {p=1/2}. Portanto a série é infinita se e só se {p=1/2} e como a cadeia é irredutível e o {0} recorrente, a cadeia é recorrente. Se {p\neq 1/2} então a cadeia é transiente.

Exemplo 123

Exercício 101 Se {P} é uma matriz de transição tal que {P^r} tem todas as entradas não-negativas para algum {r}. É verdade que {P^n} tem todas as entradas não-negativas para todo inteiro {n\geq r}?

Exercício 102 Considere a cadeia de Markov com estados {{\mathbb N}} e transições {p_{0,j} = a_j} para todo {j\in{\mathbb N}}, e {p_{i,i} = p}, e {p_{i,i-1}=1-p} para todo {i \neq 0}. Classifique os estados e determine os tempos médios de recorrência.

Essa classificação, num certo sentido, diz-nos que basta estudarmos as cadeias irredutíveis. Se {X_0} está em alguma classe de equivalência de comunicação { C_\ell} que é recorrente, então a evolução da cadeia se restringe a essa classe pois, assumindo que {i \in C_\ell} e {j\not\in C_\ell} de modo que {i\rightarrow j}, por conseguinte {j\not\rightarrow i}, temos de {[X_1=j] \subset \bigcup_{n\geq 1}[X_n\neq i]}

\displaystyle  \mathop{\mathbb P}\left(\bigcup_{n\geq 1}[X_n\neq i] ~\bigg|~ X_0=i \right) \geq p_{i,j} >0

contrariando o fato de {i} ser recorrente. Se, por outro lado, {X_0} no conjunto {T} dos estados transientes implica em ou a cadeia ficar em {T} (consulte seção XV.8 do Feller para a probabilidade desse evento) ou se mover para algum { C_\ell} e não sair mais dessa classe.

Exemplo 124 Considere uma cadeia de Markov com matriz de transição

\displaystyle  P= \begin{pmatrix} 1/2 & 1/2 & 0 & 0\\ 1/4 & 3/4 & 0 & 0\\ 1/4 & 1/4 & 1/4 & 1/4\\ 0 & 0 & 0 & 1\\ \end{pmatrix}

cujas classes de comunicação são {\{0,1\}} que é recorrente, {\{3\}} que é absorvente e {\{2\}} que é transiente. Se o inicio é no estado {2}, então a probabilidade {p} com que a cadeia entra na classe recorrente {\{0,1\}} é, condicionando em $X_1$, dada por

\displaystyle p = \frac 14 1 + \frac 14 1+ \frac 14 p +    \frac 14 0 = \frac 12 + \frac 14 p

logo {p=\frac 23}; e com probabilidade {\frac 13} a cadeia é absorvida em {3}.

No caso da matriz de transição

\displaystyle  Q= \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0\\ 1/3 & 2/3 & 0 & 0 & 0 & 0\\ 1/3 & 0 & 0 & 1/3 & 1/6 & 1/6\\ 1/6 & 1/6 & 1/6 & 0 & 1/3 & 1/6\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0\\ \end{pmatrix}

as classes de comunicação são {\{0,1\}}, {\{2,3\}} e {\{4,5\}}, respectivamente, recorrente aperiódica, transiente e recorrente periódica. Se {p_i} é a probabilidade de entrar na primeira classe descrita acima a partir do estado {i}, {i=2,3}, então

\displaystyle  \begin{array}{rcl}  p_2 &=& \frac 121 + 0\cdot 1 + 0 p_2 + \frac 13 p_3 + \frac 16 0 + \frac 16 0 \\ p_3 &=& \frac 161 + \frac 161 + \frac 16 p_2 + 0 p_3 + \frac 13 0 + \frac 16 0 \\ \end{array}

cuja solução é {p_2 = \frac 8{17}} e {p_3 = \frac 7{17}}.

Uma classe de comunicação é dita fechada se {j\in C} sempre que {i\rightarrow j} e {i\in C}. Acima verificamos que toda classe recorrente é fechada.

Exercício 103 Mostre que toda classe fechada finita é recorrente.

— Distribuição invariante e Convergência ao equilíbrio —

Recordemos a matriz de transição e transição em dois passos do exemplo 116

\displaystyle  P = \begin{pmatrix} 0,7 & 0 & 0,3 & 0\\ 0,5 & 0 & 0,5 & 0\\ 0 & 0,4 & 0 & 0,6\\ 0 & 0,2 & 0 & 0,8 \end{pmatrix} \textrm{ e } P^2= \begin{pmatrix} 0,49 & 0,21 & 0,21 & 0,18\\ 0,35 & 0,20 & 0,15 & 0,30\\ 0,20 & 0,12 & 0,20 & 0,48\\ 0,10 & 0,16 & 0,10 & 0,64 \end{pmatrix}

Se formos um pouco mais adiante obtemos

\displaystyle  P^6= \begin{pmatrix} 0.285709 & 0.144552 & 0.162561 & 0.407178\\ 0.270935 & 0.147320 & 0.156915 & 0.424830\\ 0.240920 & 0.150912 & 0.147320 & 0.460848\\ 0.226210 & 0.153616 & 0.141610 & 0.478564 \end{pmatrix}

\displaystyle  P^{10}= \begin{pmatrix} 0.2553440 & 0.1491648 & 0.1519040 &0.4435872\\ 0.2531733 & 0.1495093 & 0.1511255 &0.4461919\\ 0.2486079 & 0.1502124 & 0.1495093 &0.4516704\\ 0.2464373 & 0.1505568 & 0.1487306 &0.4542752 \end{pmatrix}

\displaystyle  P^{20}= \begin{pmatrix} 0.2500461 & 0.1499928 & 0.1500164 & 0.4499447\\ 0.2500274 & 0.1499957 & 0.1500098 & 0.4499671\\ 0.2499880 & 0.1500019 & 0.1499957 & 0.4500144\\ 0.2499693 & 0.1500048 & 0.1499890 & 0.4500369 \end{pmatrix}

\displaystyle  P^{30}= \begin{pmatrix} 0.2500004 & 0.1499999 & 0.1500001 & 0.4499995\\ 0.2500002 & 0.1500000 & 0.1500001 & 0.4499997\\ 0.2499999 & 0.1500000 & 0.1500000 & 0.4500001\\ 0.2499997 & 0.1500000 & 0.1499999 & 0.4500003 \end{pmatrix}

\displaystyle  P^{34} = \begin{pmatrix} 0.2500001 & 0.15 & 0.15 & 0.4499999\\ 0.2500000 & 0.15 & 0.15 & 0.4500000\\ 0.2500000 & 0.15 & 0.15 & 0.4500000\\ 0.2500000 & 0.15 & 0.15 & 0.4500000 \end{pmatrix}

\displaystyle  P^{35} = P^{36} = \cdots P^{40} = \cdots = \begin{pmatrix} 0.25 & 0.15 & 0.15 & 0.45\\ 0.25 & 0.15 & 0.15 & 0.45\\ 0.25 & 0.15 & 0.15 & 0.45\\ 0.25 & 0.15 & 0.15 & 0.45 \end{pmatrix}

Ainda, se fizermos {\pi^{(0)} = \varrho}, a distribuição inicial, então {\pi^{(1)} = \pi^{(0)}P} é a distribuição de {X_1}. Por exemplo, para {\pi^{(0)} = \begin{pmatrix} 1/4 & 1/4 & 1/4 & 1/4 \end{pmatrix} }, a distribuição uniforme em {S}, então temos {\pi^{(1)} = \begin{pmatrix} 0,285 & 0,15 & 0,165 & 0,4 \end{pmatrix} } de modo que {\pi^{(1)}_i = \mathop{\mathbb P}(X_1=i)}. Analogamente, {\pi^{(2)}} é a distribuição de {X_2} e, em geral, para {n\in {\mathbb N}}

\displaystyle  \pi^{(n+1)} = \pi^{(n)}P

é a distribuição de {X_{n+1}}. Notemos que

\displaystyle  \pi^{(n+1)} = \pi^{(n)}P = (\pi^{(n-1)}P) P = \cdots =\pi^{(0)}P^n

portanto, para {n\geq 36} o vetor {\pi^{(n)}} não muda e é igual a

\displaystyle  \pi = \begin{pmatrix} 0.25 & 0.15 & 0.15 & 0.45 \end{pmatrix}.

Além disso {\pi^{(0)}P^n} na coluna {j} vale

\displaystyle  \begin{array}{rcl}  (\pi^{(0)}P^n)_j &=& \pi^{(0)}_1 p^{(n)}_{1,j} + \pi^{(0)}_2 p^{(n)}_{2,j} + \pi^{(0)}_3 p^{(n)}_{3,j} + \pi^{(0)}_4 p^{(n)}_{4,j}\\ &=& \big( \pi^{(0)}_1+ \pi^{(0)}_2+ \pi^{(0)}_3+ \pi^{(0)}_4 \big)\pi_j \\&=& \pi_j \end{array}

para {n\geq 35} pois { p^{(n)}_{i,j} = \pi_j} para todo {i}. Na última igualdade usamos que {\pi^{(0)}_1+ \pi^{(0)}_2+ \pi^{(0)}_3+ \pi^{(0)}_4 =1}, portanto a conclusão é que {\pi} não depende da distribuição inicial {\pi^{(0)}}, isto é, independentemente do estado inicial, se {n} for suficientemente grande então a probabilidade da cadeia de Markov estar em qualquer um dos estados é dada pelo vetor

\displaystyle  \pi = \begin{pmatrix} 0.25 & 0.15 & 0.15 & 0.45 \end{pmatrix}.

Para {\pi} e {P} acima valem

\displaystyle   \pi P = \pi\quad\textrm{ e }\quad \pi_j = \lim_{n \rightarrow \infty} p_{i,j}^{(n)}. \ \ \ \ \ (57)

Um vetor de probabilidades {\pi = (\pi_j)_{j\in S}} que satisfaz {\pi=\pi P} é chamado de distribuição invariante ou distribuição estacionária da cadeia de Markov com matriz de transições {P}. O limite é o que chamamos de convergência ao equilíbrio.

Exemplo 125 Uma cadeia redutível com matriz de transição

\displaystyle P= \begin{pmatrix} 1&0\\ 0&1 \end{pmatrix}

tem distribuição estacionária {\pi = \begin{pmatrix} p & 1 -p \end{pmatrix}} para qualquer {p\in (0,1)} e, por exemplo, para {p=1/2} temos que {p_{1,1}^{(n)} \not\rightarrow 1/2}. O mesmo acontece com a matriz de transição

\displaystyle \begin{pmatrix} 0&1\\1&0 \end{pmatrix}

e {\pi= \big(\,1/2\quad1/2\,\big)} é estacionário mas não há convergência. A cadeia é periódica. Considere uma cadeia de Markov com quatro estado e matriz de transições

\displaystyle \begin{pmatrix} 0 & 0 & 1 & 0\cr 0 & 0 & 0 & 1\cr 1 & 0 & 0 & 0\cr 0 & 1 & 0 & 0 \end{pmatrix}

nesse caso, {(1,0,1,0)} e {(0,1,0,1)} são vetores estacionários.

Quando {S} é finito não é difícil ver que a convergência e a invariância estão intimamente relacionadas pois se {p_{i,j}^{(n)}\rightarrow \pi_j} então temos uma distribuição invariante pois

\displaystyle  \pi_j = \lim_{n\rightarrow\infty}p_{i,j}^{(n)} = \lim_{n\rightarrow\infty} \sum_{k\in S} p_{i,k}^{(n)}p_{k,j}= \sum_{k\in S} \lim_{n\rightarrow\infty} p_{i,k}^{(n)}p_{k,j}= \sum_{k\in S} \pi_k p_{k,j}

e

\displaystyle  \sum_{i\in S} \pi_i = \sum_{i\in S} \lim_{n\rightarrow\infty} p_{i,j}^{(n)} = \lim_{n\rightarrow\infty} \sum_{i\in S} p_{i,j}^{(n)} = 1.

Quando {S} não é finito isso não vale necessariamente, por exemplo, no caso assimétrico ({p\neq 1/2}) do passeio aleatório em {{\mathbb Z}}, exemplo 123, temos {p_{i,j}^{(n)}\rightarrow 0} pois a cadeia é transiente, entretanto, {\pi} não é uma distribuição.

Teorema 20 Uma cadeia de Markov irredutível tem uma distribuição estacionária {\pi = (\pi_j)_j} se, e somente se, todos os estados são recorrentes positivos. O vetor estacionário é único e satisfaz

\displaystyle   \pi_j = \frac 1{\mu_j}. \ \ \ \ \ (58)

Ainda, se a cadeia for periódica então

\displaystyle   \pi_j = \lim_{n \rightarrow \infty} p_{i,j}^{(n)}. \ \ \ \ \ (59)

A demonstração para o caso S finito é dada no final do post.

Usando R:

 invariante = function() {
# Para determinar pi que satisfaz pi %*% trans = pi resolvemos o
# sistema (t(trans) - I) %* pi = 0 onde t() e' a matriz transposta e
# pi agora e' um vetor coluna. No lado direito trocamos a ultima linha
# por uma linha de 1's, e no lado esquerdo trocamos o vetor nulo por
# (0,0,...0,1), isso representa a restricao da soma das entradas de pi
# ser 1. Entao, resolvemos para pi.

##########################################
  trans <- matrix(c( 
    1/2 , 1/2 , 0 , 0 , 0 , 0 ,
    1/4 , 3/4 , 0 , 0 , 0 , 0 ,
    1/4 , 1/4 , 1/4 , 1/4 , 0 , 0 ,
    1/4 , 0 , 1/4 , 1/4 , 0 , 1/4, 
    0 , 0 , 0 , 0 , 1/2 , 1/2 ,
    0 , 0 , 0 , 0 , 1/2 , 1/2
    ), ncol=6, byrow=TRUE)



  n <- nrow(trans)
  a <- t(trans)
  for(i in 1:n)    {    a[i, i] <- a[i, i] - 1  }
  a[n, ] <- 1
  b <- rep(0, n)
  b[n] <- 1
  solve(a, b)
  
}

No caso da cadeia ser periódica de período {d} então

\displaystyle   \lim_{n \rightarrow \infty} p_{i,i}^{(nd)} = \frac{d}{\mu_i} \ \ \ \ \ (60)

e ser for recorrente

\displaystyle   \lim_{n \rightarrow \infty} \frac 1n\sum_{m=0}^{n-1}p_{i,j}^{(m)} = \frac{1}{\mu_j} =\pi_j \ \ \ \ \ (61)

com {\pi} (único) vetor de estacionário.

Observação 8 Se uma sequência converge {\lim_{n\rightarrow\infty}a_n =a}, então a sequência das médias parciais também converge

\displaystyle  \lim_{n\rightarrow\infty} \frac 1n \sum_{i=0}^{n-1} a_i = a

portanto de (59) temos

\displaystyle  \lim_{n\rightarrow\infty} \frac 1n \sum_{t=0}^{n-1} p_{i,j}^{(t)} = \pi_j

e se {I_t} é a v.a.~indicadora do evento {[X_t=i]} então

\displaystyle  \sum_{t=0}^{n-1} p_{i,j}^{(t)} = \mathop{\mathbb E} \big( V_i^{[0..n-1]}~\big|~ X_0=i\big)

em que { V_i^{[0..n-1]}} é o número de visistas a {i} no intervalo de tempo~ {0,\dots,n-1} (veja o lema 18), ou seja,

\displaystyle \lim_{n\rightarrow\infty} \frac 1n \mathop{\mathbb E} \big( V_i^{[0..n-1]}~\big|~ X_0=i\big) = \pi_j.

Em palavras, {\pi_j} é a fração média de visitas ao estado {i} por unidade de tempo.

Teorema 21 (Teorema ergódico) Para qualquer cadeia de Markov irredutível

\displaystyle  \mathop{\mathbb P} \left( \lim_{n\rightarrow\infty} \frac{ V_i^{[0..n-1]} }n = \frac 1\mu_i \right) =1.

Exercício 104 Uma matriz quadrada com entradas não-negativas é duplamente estocástica se é estocástica e a soma das entradas de cada coluna é {1}. Mostre que se {M} é quadrada de ordem {n} e duplamente estocástica então o vetor uniforme {(1/n,1/n,\dots,1/n)} é invariante para {M}.

Observação 9 No caso finito a existência de um vetor estacionário é garantido para qualquer matriz estocástica. Esse fato decorre do Teorema do Ponto Fixo de Brower: Para toda função contínua {f\colon T\rightarrow T}, onde {T\subset {\mathbb R}^n} é compacto e convexo, existe {x\in T} tal que {f(x)=x}. Agora, consideremos para todo {\mathbf{v}=(v_1,v_2,\dots,v_n)\in{\mathbb R}^n} a norma {L^1}

\displaystyle   \Vert \mathbf{v} \Vert_1 = \sum_{i=1}^n|v_i| \ \ \ \ \ (62)

e o conjunto (compacto e convexo)

\displaystyle   T= \{\mathbf{v}\in {\mathbb R}^n\colon \mathbf{v}\geq 0~\mathrm{e}~\Vert \mathbf{v}\Vert_1 =1\}. \ \ \ \ \ (63)

Seja {P} uma matriz estocástica e considere a função linear de {T} em {T} dada por {\mathbf{x}\mapsto \mathbf{x}P}. Por ser linear a função é contínua, portanto, pelo Teorema da Ponto Fixo de Brower deduzimos a existência de um vetor estacionário.

— Cadeias redutíveis —

Os resultados da seção anterior aplicam-se a qualquer classe de comunicação recorrente. Se { C_\ell} é classe de comunicação recorrente e aperiódica de um processo, então a submatriz formada pelos {i,j \in C_\ell} é estocástica logo {p_{i,j}^{(n)} \rightarrow 1/\mu_j} quando {n\rightarrow\infty}.

Exemplo 126 Por exemplo,

\displaystyle P= \begin{pmatrix} 1/2 & 1/2 & 0 & 0\\ 1/4 & 3/4 & 0 & 0\\ 0 & 0 & 1/3 & 2/3\\ 0 & 0 & 2/3 & 1/3 \end{pmatrix}

tem as classes recorrentes {\{0,1\}} com a submatriz estocástica irredutível

\displaystyle P_1= \begin{pmatrix} 1/2 & 1/2 \\ 1/4 & 3/4 \end{pmatrix}

e {\{2,3\}} com a submatriz estocástica irredutível

\displaystyle P_2= \begin{pmatrix} 1/3 & 2/3\\ 2/3 & 1/3 \end{pmatrix}.

A matriz {P_1} admite o vetor estacionário {\pi^{(1)} = \begin{pmatrix} 1/3 & 2/3 \end{pmatrix}} e a matriz {P_2}, o vetor estacionário {\pi^{(2)} = \begin{pmatrix} 1/2 & 1/2 \end{pmatrix}} e, além disso

\displaystyle \lim_{n\rightarrow\infty} P^n= \begin{pmatrix} \pi_0^{(1)} & \pi_1^{(1)} & 0 & 0\\ \pi_0^{(1)} & \pi_1^{(1)} & 0 & 0\\ 0 & 0 & \pi_0^{(2)} & \pi_1^{(2)}\\ 0 & 0 & \pi_0^{(2)} & \pi_1^{(2)} \end{pmatrix}=\begin{pmatrix} 1/3 & 2/3 & 0 & 0\\ 1/3 & 2/3 & 0 & 0\\ 0 & 0 & 1/2 & 1/2\\ 0 & 0 & 1/2 & 1/2 \end{pmatrix}.

Ainda, se {i,j \in C_\ell}, com { C_\ell} classe de comunicação recorrente e periódica, então

\displaystyle \frac 1n \sum_{m=0}^{n-1}p_{i,j}^{(m)} \rightarrow \frac 1\mu_j

quando {n\rightarrow\infty}.

Por outro lado, se {j} é um estado transiente então {p_{i,j}^{(n)} \rightarrow 0} quando {n\rightarrow\infty} para qualquer estado inicial {i}.

Exemplo 127 De volta ao exemplo 124, a classe recorrente {\{0,1\}} com respeito a matriz {P} tem distribuição estacionária {\pi= \begin{pmatrix} 1/3 & 2/3 \end{pmatrix}}. Ademais essa classe é atingida a partir do estado {2} com probabilidade {p= 2/3}, portanto {p_{2,0}^{(n)} \rightarrow \frac 23 \cdot \frac 13 = \frac 29} e {p_{2,1}^{(n)} \rightarrow \frac 23 \cdot \frac 23 = \frac 49} logo

\displaystyle \lim_{n\rightarrow\infty} P^n = \begin{pmatrix} 1/3 & 2/3 & 0 & 0\\ 1/4 & 3/4 & 0 & 0\\ 2/9 & 4/9 & 0 & 1/3\\ 0 & 0 & 0 & 1 \end{pmatrix}.

No que diz respeito a matriz {Q}, temos {\{0,1\}} recorrente aperiódico com {\pi= \begin{pmatrix} 2/4 & 3/5 \end{pmatrix}}, {\{2,3\}} transiente com probabilidade de sair de {2} (respec., {3}) e ir ser absorvido por {\{0,1\}} sendo {p_2= 8/17} (respec., {7/17}), e {\{4,5\}} recorrente periódico

\displaystyle \lim_{n\rightarrow\infty} Q^n = \begin{pmatrix} 2/5 & 3/5 & 0 & 0 & 0 & 0\\ 2/5 & 3/5 & 0 & 0 & 0 & 0\\ \frac 8{17} \cdot \frac 25 & \frac 8{17}\cdot \frac 35 & 0 & 0 & & \\ \frac 7{17}\cdot \frac 25 & \frac 7{17}\cdot \frac 35 & 0 & 0 & & \\ 0 & 0 & 0 & 0& & \\ 0 & 0 & 0 & 0& & \end{pmatrix}

em que os espaços vazios indicam que o limite não existe. Entretanto,

\displaystyle  \lim_{n\rightarrow\infty} \frac 1n\sum_{m=0}^{n-1} Q^m= \begin{pmatrix} 2/5 & 3/5 & 0 & 0 & 0 & 0\\ 2/5 & 3/5 & 0 & 0 & 0 & 0\\ \frac 8{17} \cdot \frac 25 & \frac 8{17}\cdot \frac 35 & 0 & 0 & \frac 9{17}\cdot \frac 12 & \frac 9{17}\cdot \frac 12\\ \frac 7{17}\cdot \frac 25 & \frac 7{17}\cdot \frac 35 & 0 & 0 & \frac {10}{17}\cdot \frac 12& \frac {10}{17}\cdot \frac 12\\ 0 & 0 & 0 & 0& 1/2 & 1/2\\ 0 & 0 & 0 & 0& 1/2 & 1/2 \end{pmatrix}.

— Exemplo: 2-SAT —

O 2-SAT (2-Satisfiability Problem) é o seguinte problema; dado uma fórmula booleana 2-CNF (cada cláusula é uma conjunção de 2 literais {C_i=\ell_{i_1}\vee \ell_{i_2}}), digamos

\displaystyle \Phi = C_{1}\,\wedge\,C_2\,\wedge \,\cdots\,\wedge\,C_{k}

sobre um conjunto de variáveis {V=\{x_{1},x_{2},\dots,x_{n}\}}, determinar se existe uma valoração {\nu\colon V\rightarrow \{0,1\}} que satisfaça {\Phi}.

É sabido [Aspvall, Plass, Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform. Process. Lett., 1979, no.~3, pg.~121–123] que 2-SAT pode ser resolvido em tempo polinomial. A seguir, daremos um algoritmo aleatorizado bem simples, de tempo polinomial e que responde corretamente com alta probabilidade.


Exercício 105 Por que {\{X_n\}_n} acima não define uma cadeia de Markov?

Exercício 106 Prove a afirmação {\mathop{\mathbb E} X_j \leq \mathop{\mathbb E} Y_j} feita no exemplo acima.

— Exemplo: Modelo de fecundidade —

As mudanças nos padrões sociais afetam a taxa de crescimento populacional. Modelos para analisar os efeitos das mudanças na fecundidade média de uma população levam em conta a idade, a situação conjugal, o número de filhos e várias outras informações a respeito do público feminino da população. Essas características compõem cada estado de um processo cujo interesse é determinar o tempo médio do processo nas categorias de maior fertilidade. As probabilidades de transição são inferidas de dados demográficos.

Num modelo simplificado consideramos os estados {0 \equiv}pré-puberil, {1\equiv}solteira, {2\equiv}casada, {3\equiv}Divorciada, {4\equiv}Viúva, {5\equiv}morte ou emigração.

\displaystyle P = \begin{pmatrix} 0 & 0.9 & 0 & 0 & 0 & 0.1 \\ 0 & 0.5 & 0.4 & 0 & 0 & 0.1 \\ 0 & 0 & 0.6 & 0.2 & 0.1 & 0.1 \\ 0 & 0 & 0.4 & 0.5 & 0 & 0.1 \\ 0 & 0 & 0.4 & 0 & 0.5 & 0.1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}

Denotemos por {e_i} o tempo médio da cadeia no estado {2} dado que {X_0=i}. Então

\displaystyle  \begin{cases} e_0 &= 0.9e_1+0.1e_5 \\ e_1 &= 0.5e_1+0.4e_2+0.1e_5 \\ e_2 &= 1+0.6e_2+0.2e_3+0.1e_4+0.1e_5 \\ e_3 &= 0.4e_2+0.5e_3+0.1e_5 \\ e_4 &= 0.4e_4+0.5e_4+0.1e_5 \\ e_5 &= 0 \end{cases}

cuja (única) solução é {e_0=4.5}, {e_1=5}, {e_2=6.25}, {e_3=e_4=5}.

Notemos que, como esperado, a distribuição estacionária é { \begin{pmatrix} 0&0&0&0&1 \end{pmatrix}}.

— Exemplo: Controle de estoque —

Uma mercadoria é armazenada e ao final dos preíodos {n=0,1,\dots} o estoque é reabastecido. A demanda pela mercadoria no período {n} é uma variável aleatória {Y_n} com {Y_1,Y_2,\dots} independentes e identicamentes distribuídas..

A política de reabastecimento envolve escolher dois parâmetros inteiros e positivos {s} e {S} de modo que se ao final de um período o estoque é no máximo {s} então ele é abastecido até atingir {S}, caso contrário não é abastecido.

A variável aleatória {X_n} é a quantidade de mercadoria ao fim do período {n} antes do reabastecimento e caso seja negativa a demanda é atendida após o reabastecimento.

Os níveis de estoque em dois períodos consecutivos são realcionados por

\displaystyle X_{n+1} = \begin{cases} X_n - Y_{n+1} & s < X_n \leq S\\ S - Y_{n+1} & X_n \leq s\\ \end{cases}

e as probailidades das transições

\displaystyle  p_{i,j} =\mathop{\mathbb P}(X_{n+1}=j~|~X_n=i) = \begin{cases} \mathop{\mathbb P}(Y_{n+1} = i-j)& s < X_n \leq S\\ \mathop{\mathbb P}(Y_{n+1}=S-j) & X_n \leq s\\ \end{cases}

Nesse caso, gostaríamos de saber qual é, a longo prazo, a fração de períodos que a demanda não é atendida

\displaystyle \lim_{n\rightarrow\infty} \sum_{j<0} \mathop{\mathbb P}(X_n=j)

e qual é, a longo prazo, o nível médio de estoque

\displaystyle \lim_{n\rightarrow\infty} \sum_{j>0} j \mathop{\mathbb P}(X_n=j)

e sob certas condições {\mathop{\mathbb P}(X_n=j)} converge.

Para um exemplo numérico tomemos

\displaystyle  \mathop{\mathbb P}(Y_n = 0) =0.5, \quad \mathop{\mathbb P}(Y_n=1) = 0.4, \quad \mathop{\mathbb P}(Y_n=2)=0.1

e {s=0} e {S=2}. Assim, {X_n\in \{-1,0,1,2\}}.

Quando {X_n=1} então não é necessário reabastecimento do estoque, logo {X_{n+1}=0} caso {Y_{n+1}=1}, o que ocorre com probabilidade {0.4}, logo {p_{1,0}=0.4}. Agora, se {X_n=0} então há reabastecimento para {S=2} e {X_{n+1}=0} caso {Y_{n+1}=2} , logo {p_{0,0}=0.1}. A matriz fica da seguinte forma, lembrando que os estados são {\{-1,0,1,2\}}

\displaystyle  P= \begin{pmatrix} 0 & 0.1 & 0.4 & 0.5 \\ 0 & 0.1 & 0.4 & 0.5 \\ 0.1 & 0.4 & 0.5 & 0 \\ 0 & 0.1 & 0.4 & 0.5 \end{pmatrix}

que, claramente, é irredutível, recorrente e aperiódica, cujo vetor estacionário é

\displaystyle  \begin{pmatrix} 4/90 & 21/90 & 40/90 & 25/90 \end{pmatrix}.

— Reversibilidade —

Numa cadeia de Markov, dado o estado presente, o futuro e o passado são independentes. Seja {\{X_i\}_{i\geq 0}} uma cadeia de Markov irredutível com respeito a matriz estocástica {P} e a distribuição inicial {\pi}, e {\pi} uma distribuição invariante. Tomemos a matriz {Q = q_{i,j}} dada por

\displaystyle  q_{i,j} = \frac{\pi_j}{\pi_i}p_{j,i}.

Essa matriz é estocástica pois, pela invariância de {\pi}

\displaystyle  \sum_{j\in S} q_{i,j} = \frac{1}{\pi_i} \sum_{j\in S} \pi_j p_{j,i} =1 .

Ainda,

\displaystyle  \sum_{j\in S} \pi_i q_{i,j} = \sum_{j\in S} \pi_j p_{j,i} = \pi_i

ou seja, {\pi} é invariante com relação a {Q}.

Se tomarmos {Y_n = X_{N-n}} para {0\leq n \leq N} então

\displaystyle  \mathop{\mathbb P}\big( Y_0=i_0,~Y_1=i_1,\dots,Y_N=i_N \big) = \mathop{\mathbb P}\big( X_0=i_N,~X_1=i_{N-1},\dots,X_N=i_0 \big) =

\displaystyle  \pi_{i_N}p_{i_N,i_{N-1}}\cdots p_{i_1,i_0}= \pi_{i_0}q_{i_0,i_1}\cdots q_{i_{N-1},i_{N}}

logo {\{Y_n\}_{0\leq n\leq N}} é uma cadeia de Markov com relação a {Q} e {\pi}. Ademais,

\displaystyle  q_{i_{N},i_{N-1}} \cdots q_{i_1,i_0}= \frac 1{\pi_{i_0}} \pi_{i_N} p_{i_0,i_1}\cdots p_{i_{N-1},i_{N}} >0

portanto, a cadeia é irredutível, chamada tempo-reverso da cadeia {\{X_i\}_{0\leq i\leq N}}.

Exercício 106 Mostre que se {P} é uma matriz estocástica e {\lambda} um vetor não-negativo tal que para todos {i,j}

\displaystyle  \lambda_ip_{i,j}=\lambda_jp_{j,i} \ \ \ \ \ (64)

então {\lambda P= \lambda}.

Exercício 107 Prove que {\{X_n\}_{n\geq 0}} irredutível, com matriz de transições {P} e distribuição inicial {\lambda} é reversível se e só se vale (64).

Exemplo 128 Consideremos um grafo conexo {G} com peso positivo {w_{i,j}} na aresta em cada aresta {\{i,j\}\in E(G)}. Uma partícula move-se sobre o grafo com a seguinte estratégia: se a partícula encontra-se no vértice {i} no instante {t} então no instante {t+1} a partícula estará no estado {j} com probabilidade

\displaystyle  p_{i,j} = \frac{w_{i,j}}{\sum_{j\in V(G)} w_{i,j}}

de modo que {w_{i,j}=0} caso {\{i,j\}} não seja uma aresta. A equação (64) é equivalente a

\displaystyle  \pi_i = \frac{\sum_{j\in V(G)} w_{i,j}}{\sum_{i\in V(G)}\sum_{j\in V(G)} w_{i,j}}.

No caso mais simples, {w_{i,j}\in\{0,1\}} e {w_{i,j}=1} se e só se {\{i,j\}} é aresta,

\displaystyle \pi_i = \frac{d(i)}{2|E(G)|}

em que {d(i)} é o número de arestas incidentes em i. Veremos que esse sempre é o caso, portanto passeios aleatórios em grafos são reversíveis.

— Demonstração do Teorema 13 no caso finito —

Vamos começar considerando o caso em que {P} é uma matriz estocástica positiva. Digamos que {P} é {n\times n} e definimos {\epsilon=\min P >0}. Vamos provar que {\lim_{k\rightarrow \infty}P^k = Q} com {Q} uma matriz estocástica com as colunas constantes.

Exercício 108 Seja {P} uma matriz estocástica com todas entradas positivas. Tomemos {\epsilon=\min P} e {\mathbf{c}} um vetor coluna qualquer com {\min \mathbf{c}=a_0} e {\max \mathbf{c}=b_0}. Sejam {a_1= \min P\mathbf{c}} e {b_1=\max P\mathbf{c}}. Prove que {a_1 \geq a_0}, {b_1\leq b_0} e {b_1-a_1 \leq (1-2\epsilon)(b_0-a_0)}
(Sugestão: tome {\mathbf{c}'} o vetor obtido a partir de {\mathbf{c}} trocando todas as coordenadas por {a_0} menos a coordenada {b_0}; tome {\mathbf{c}''} o vetor obtido a partir de {\mathbf{c}} trocando todas as coordenadas por {b_0} menos a coordenada {a_0}. Use o fato de {P\mathbf{c}' \leq P\mathbf{c} \leq P\mathbf{c}''}.)

Denotemos por {\mathbf{e}_j} o vetor coluna com todas as entradas nulas a menos da posição {j} que é 1. A seguir, vamos usar o exercício anterior para definir um vetor estocástico {\mathbf{\pi}} que são as linhas de {Q}, o qual mostraremos depois ser estacionário.

Fixamos {j\in\{1,2,\dots,n\}}, uma coluna de {P}, e definimos

\displaystyle  \begin{array}{rcl}  a_k &=& \min P^k\mathbf{e}_j \\ b_k &=& \max P^k\mathbf{e}_j \end{array}

o mínimo e o máximo, respectivamente, da {j}-ésima coluna de {P^k}, tomamos {a_0=0} e {b_0=1}. Para {k\in{\mathbb N}} temos

\displaystyle a_{k+1} = \min P^{k+1} \mathbf{e}_j = \min P ( P^k \mathbf{e}_j )~\textrm{ e }~a_k =\min ( P^k \mathbf{e}_j).

Analogamente, temos

\displaystyle b_{k+1} = \max P^{k+1} \mathbf{e}_j = \max P ( P^k \mathbf{e}_j ) ~\textrm{ e }~b_k =\max ( P^k \mathbf{e}_j).

Do exercício 108 temos a sequência de máximos e mínimos

\displaystyle  \begin{array}{rcl}  b_0 \geq b_1 \geq \cdots \geq b_k \geq \cdots \geq a_k \geq a_{k-1} \geq \cdots \geq a_0 \end{array}

de modo que

\displaystyle  b_k-a_k \leq (1-2\epsilon)(b_{k-1}-a_{k-1}) \leq (1-2\epsilon)^k

pois {\epsilon >0}. Da equação anterior {\lim_{k\rightarrow\infty} b_k-a_k = 0} e definimos

\displaystyle  \pi_j = \lim_{k\rightarrow\infty} b_k = \lim_{k\rightarrow\infty} a_k.

Com isso provamos que todas as entradas da {j}-ésima coluna de {P^k} convergem para um valor constante {\pi_j}. Feito isso para cada coluna {j}, o vetor que procuramos é

\displaystyle   \mathbf{\pi}=\big(\pi_1,\pi_2,\dots,\pi_n\big) \ \ \ \ \ (65)

e com isso

\displaystyle   \lim_{k\rightarrow\infty}p_{i,j}^{(k)} = \pi_j \quad (\forall i) \ \ \ \ \ (66)

e tomamos {Q=\mathbf{1}^\mathtt{T}\mathbf{\pi}}, a matriz com cada linha igual a {\mathbf{\pi}} que queríamos provar. Como {P>0} temos {a_1>0}, portanto {\pi_j>0}. Também, {\pi_j<1}.

Exercício 109 Prove que temos {\sum_j \pi_j =1} no vetor dado acima.

Estenderemos esse resultado para matrizes não negativas usando o fato de que para a matriz de uma cadeia de Markov irredutível e aperiódica temos {P^t} positiva para algum {t\in{\mathbb N}}.

Proposição 22 Se uma cadeia Markov é ergódica então existe {K_0\in {\mathbb N}} tal que para todo {i,~j\in S}, se {k\>K_0} então {p_{i,j}^{(k)}>0}.

Demonstração: Da cadeia ser irredutível temos que para cada {i,j\in S} existe {k(i,j)} tal que {p_{i,j}^{(k(i,j))} >0}. Da cadeia ser aperiódica temos que para cada {i\in S} existe {k_0(i)} tal que {p_{i,i}^{(k)} >0} para todo {k\geq k_0(i)}. Com essas constantes, se {t \geq 0} então

\displaystyle  \begin{array}{rcl}  p_{i,i}^{(k_0(i) + t)} > 0~\textrm{ e }~ p_{i,j}^{(k(i,j))} > 0 \end{array}

portanto, por (52), para todo {t\in {\mathbb N}}

\displaystyle  p_{i,j}^{(k(i,j)+k_0(i)+t)} = \sum_{\ell \in S} p_{i,\ell}^{((k_0(i)+t))}p_{\ell,j}^{(k(i,j))} \geq p_{i,i}^{((k_0(i)+t))}p_{i,j}^{(k(i,j))} >0.

Tomamos

\displaystyle  \begin{array}{rcl}  K_0 = \max \{k(i,j)+k_0(i)\: i,j\in S\} \end{array}

o que prova a proposição. \Box

O vetor {\pi} é estacionário

\displaystyle  \pi_j = \lim_{n\rightarrow\infty}p_{i,j}^{(n)} = \lim_{n\rightarrow\infty} \sum_{k\in S} p_{i,k}^{(n)}p_{k,j}= \sum_{k\in S} \lim_{n\rightarrow\infty} p_{i,k}^{(n)}p_{k,j}= \sum_{k\in S} \pi_k p_{k,j}.

Agora, provaremos que se o estado inicial é algum elemento de {S=\{1,2,\dots,n\}} com probabilidade dada por {\varrho=\varrho^{(0)}} então {\varrho P^t\rightarrow \pi} quando {t\rightarrow\infty}, ou seja, qualquer distribuição inicial a longo prazo se aproxima da distribuição estacionária.

Consideremos os vetores de probabilidades

\displaystyle  \varrho^{(0)} = \begin{pmatrix} q_1^{(0)}&\dots&q_n^{(0)} \end{pmatrix}

e

\displaystyle  \varrho^{(t)}= \begin{pmatrix} q_1^{(t)}&\dots&q_n^{(t)} \end{pmatrix}

e a partir de {\varrho^{(t)}} obtemos a distribuição {X_{t+1}} por

\displaystyle  \varrho^{(t+1)}=\varrho^{(t)}P = \varrho P^t.

Agora, seja {K_0=K_0(P)} a constante dada pela proposição 22. Assim, {P^{K_0}} é uma matriz com todas as entradas positivas e para {\epsilon = \min P^{K_0}} e para {t\in{\mathbb N}}

\displaystyle  b_{tK_0} - a_{tK_0}\leq (1-\epsilon)^t

portanto, a subseqüência converge, {\lim_{t\rightarrow\infty}b_{tK_0}-a_{tK_0}=0}. Ademais, as diferenças {b_t -a_t} nunca aumentam com {t}, ou seja, a seqüência {(b_t - a_t)_t} é não-crescente, portanto converge para {0}, portanto, {\lim_{t\rightarrow\infty}P^t=Q}

Seja {\nu} um vetor qualquer com {\nu=\nu P}. Para mostrar a unicidade de {\pi} é suficiente mostrar que {\nu} é um múltiplo escalar de {\pi}.

Se {\nu=\nu P} então {\nu=\nu P^t}, portanto

\displaystyle  \nu= \lim_{t\rightarrow\infty}\nu P^t = \nu\lim_{t\rightarrow\infty}P^t = \nu Q

logo {v_j = \sum_i v_i\pi_j= \pi_j\sum_i v_i} e podemos concluir então que {\nu=\left(\sum_i v_i\right)\pi}.

Agora, vamos provar que {\displaystyle \lim_{t\rightarrow\infty}\varrho P^t = \pi} para qualquer vetor de probabilidades {\varrho=(q_1,q_2,\dots,q_n)}. Como acima,

\displaystyle  \lim_{t\rightarrow\infty}\varrho P^t = \varrho Q

donde {\big(\varrho Q\big)_j = \big(\sum_i q_i\big)\pi_j} é a {j}-ésima coordenada de {\varrho Q}. Como {\varrho} é um vetor de probabilidades a soma das coordenadas é {1}, logo

\displaystyle  \big(\varrho Q \big)_j = \pi_j

ou seja, {\varrho Q = \mathbf{\pi}} como queríamos provar.

Resta provar que {\pi_j = 1/\mu_j}. Como {S} é finito {\mu_j < \infty}.

Primeiro, definimos {\mu_{i,j} = \mathop{\mathbb E}(T_j~|~X_0=i)} para {i\neq j}, e se consideramos o primeiro passo da cadeia temos que vale

\displaystyle  \mu_{i,j} = p_{i,j}+ \sum_{k\neq j} p_{i,k}(\mu_{k,j}+1) = 1+ \sum_{k\neq j} p_{i,k}\mu_{k,j} .

De modo análogo {\mu_{i,i}= \mu_i= 1+\sum_{k} p_{i,k}\mu_{k,j} .} Esse conjunto de equações pode ser escrito de forma matricial como

\displaystyle  M = PM + U - D

em que {U} é a matriz com todas as entradas iguais a {1} e {D=(d_{i,j})} é a matriz diagonal {d_{i,i}=\mu_i}. Reescrevendo temos

\displaystyle  D - U = (P- Id)M

em que {Id} é a matriz identidade. Se multiplicarmos por {\pi} a direita nos dois lados da igualdade temos, no lado direito, que {\pi(P-Id) =0} pois {\pi} é estacionário, portanto {\pi D = \pi U}, mas {\pi U = \begin{pmatrix} 1 & 1 & \cdots & 1 \end{pmatrix}}, logo {(\pi D)_j=1} para cada {j}, isto é,

\displaystyle  \pi_j \mu_j = 1.

— Exercícios complementares —

Exercício 116 Seja {P} uma matriz de transições de uma cadeia de Markov. Defina a matriz {P' = (P+\mathrm{Id})/2}. Prove que a cadeis com matriz de transições {P'} é aperiódica.

Exercício 117 Considere a generalização natural do algoritmo para o 2-SAT, seção 0, para 3-SAT. Prove que tal algoritmo é exponencial, {O(2^n)} em que {n} é o número de variáveis.

Exercício 118 Por dia, uma dentre {n} pessoas é requisitada, a pessoa {i} requisitada com probabilidade {p_i}. As pessoas são organizadas numa lista ordenada e a cada requisição a pessoa escolhida é colocada no topo da lista, o resto da lista fica inalterada.

  1. Numa modelagem com cadeia de Markov, quais são os estados?
  2. Qual é a distribuição invariante? (Dica: Não precisa fazer conta.)

Exercício 119 Uma pessoa tem {n} guarda-chuvas que usa no trajeto de casa ao trabalho e vice-versa. Se ela está em casa no começo de dia e está chovendo então escolhe um guarda-chuva para ir ao escritório, caso haja disponível. Se ela está no escritório no fim do dia e está chovendo então escolhe um guarda-chuva para ir para casa, caso haja disponível. Quando não está chovendo ela não escolhe usa guarda-chuva. Assumindo que no início do dia e no fim do dia chove de modo independente e com probabilidade {p}, qual é a fração das viagens que ela faz sob chuva e sem guarda-chuva?

Exercício 120 Um grupo de {n} processadores é arranjado em lista ordenada e quando uma tarefa chega é atribuída ao primeiro da lista; se ele está ocupado tenta-se o segundo da lista, e assim por diante. Uma vez que a tarefa é processada ou que não é encontrado um processador disponível pra ela, ela deixa o sistema. Nesse momento, podemos reordenar os processadores antes que a próxima tarefa chegue e a estratégia é: se um processador atendeu a tarefa ele avança uma posição na lista, trocando-o com o processador imediatamente a frente; se todos falharam ou o primeiro atendeu a ordem permanece a mesma. Assumamos que no processador {i} atende a tarefa com probabilidade {p_i}.

  1. Defina uma cadeia de Markov para analisar o problema.
  2. Mostre que a cadeia é reversível.
  3. Descubra as probabilidades limite.

Exercício 121 Num tabuleiro de xadrez o cavalo começa num dos quatro cantos e se move com igual probabilidade para qualquer uma das posições legais, de acordo com as regras do seu movimento. Qual é o número esperado de movimentos até voltar para a posição de saída?

Exercício 122 Como podemos gerar valores para vinte variáveis aleatórias independentes e com distribuição uniforme em {(0,1)} condicionadas a soma delas serem menor que dois?

Exercício 123 Uma coloração de um grafo é uma atribuição de cores aos vértices do grafo. Um grafo é {k}-colorível se há um coloração com {k} cores sem que vértices adjacentes recebam a mesma cor. Seja {G} um grafo {3}-colorível.

Mostre que {G} tem uma coloração com 2 cores sem que haja triângulo com os três vértices da mesma cor.

Considere o seguinte algoritmo para achar a coloração afirmada no parágrafo acima: o algoritmo começa com uma coloração de duas cores arbitrária. Enquanto houver triângulo monocromático, escolha um deles e sorteie um de seus vértices, mude a cor do vértice sorteado. Determine um limitante superior para o número esperado de recolorações até oal goritmo terminar.

Exercício 124 Seja {X_n} a soma dos resultados de {n} lançamentos independentes de um dado. Mostre que para {k\geq 2}

\displaystyle \lim_{n\rightarrow\infty} \mathop{\mathbb P} \big( k \textrm{ divide }X_n \big) = \frac 1k.

Exercício 125 Numa cidade com {n+1} habitantes, uma pessoa conta um boato para uma segunda pessoa, que por sua vez conta o boato para uma terceira pessoa e assim por diante. Em cada passo o ouvinte do boato é escolhido aleatoriamente de maneira uniforme dentre as outras pessoas na cidade. Como esse processo pode ser modelado como uma cadeia de Markov? Qual a probabilidade do boato ser contado {r} vezes sem repetir nenhuma pessoa? Escreva um código em {R} para determinar o número de rodadas até que todos tenham ouvido o boato com probabilidade {0.999}, para {n=128}.

Exercício 126 Um gato e um rato passeiam aleatoriamente num grafo conexo e não-bipartido de modo independente. Eles começam ao mesmo tempo em vértices diferentes e ambos dão um passo a cada instante, também de modo independente. O gato come o rato se em algum instante eles estão no mesmo vértice. Mostre que o número esperado de passos até els se encontrarem é {O(m^2 n)}, em que {n} é o número de vértice e {m} o número de arestas de {G}. (Dica: considere a cadeia de Markov com estados {(u,v)} sendo as posições de cada animal no grafo, num instante.)

Exercício 127 O grafo Lollipop é um grafo completo com {n} vértices e um caminho com {n} vértices e um único vértice {u} em comum. Chamamos de {v} o úico vértice de grau um, o vértice final do caminho.

Mostre que se um passeio aleatório começa em {v} então o número esperado de passos até visitar todos os vértices é {O(n^2)}.

Mostre que se um passeio aleatório começa em {u} então o número esperado de passos até visitar todos os vértices é {O(n^3)}.

4 respostas em “bc1414 Cadeias de Markov

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s