bc1414 – Cadeias de Markov a tempo discreto

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. Como todas as cadeias desse capítulo são homogêneas nós omitiremos esse adjetivo daqui em diante.

— Elementos básicos —

Uma sequência {(\varrho_i)_{i\in S}} com {\varrho_i \geq 0}, de modo que {\sum_{i\in S} \varrho_i =1} é chamada vetor de probabilidades ou distribuição da v.a. {X} no caso em que {\varrho_i = \mathop{\mathbb P}(X=i)}. Chamamos {X_0} de estado inicial e sua função de massa de distribuição inicial.

Uma cadeia de Markov é caracterizada por

  1. conjuntos de estados {S},
  2. distribuição inicial {(\varrho_i)_{i\in S}},
  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 um o processo estocástico {\{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}.

Da distribuição conjunta temos

\displaystyle  \begin{array}{rcl}  \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}) \end{array}

e

\displaystyle  \begin{array}{rcl}  \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{ \sum_{s_0,\dots,s_{n-1}} \varrho_{s_0} \prod_{i=0}^np(s_i,s_{i+1})} { \sum_{s_0,\dots,s_{n-1}} \varrho_{s_0} \prod_{i=0}^{n-1}p(s_i,s_{i+1})} \\ &=& p(s_n,s_{n+1}) \end{array}

que é a condição de Markov (46). Da condição de Markov, eq. (46), deduzimos a distribuição conjunta, eq. (47), pelo exercício 35 (regra generalizada do produto). Ademais, fixado {n}, temos a partir dos itens 2 e 3 acima que

\displaystyle  \begin{array}{rcl}  \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) = \\ \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 \end{array}

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).

Exercicio 100 (Propriedade de Markov) Prove que se {\{X_t\}_{t\in{\mathbb N}}} é uma cadeia de Markov com respeito ao conjunto de estados {S}, distribuição inicial {(\varrho_i)_{i\in S}} e probabilidades de transição {\{p(i,j)\}_{i,j\in S}}, então condicionado a {[X_m=i]} o processo {\{X_{t+m}\}_{t\in{\mathbb N}}} é uma cadeia de Markov com respeito a {\big(\delta_i(j)\big)_{i\in S}} e {\{p(i,j)\}_{i,j\in S}} e independente de {X_0,\dots,X_m}. Acima, {\delta_i(j)=1} se e só se {i=j}.

— Identidade de Chapman–Kolmogorov —

Convencionamos que {p_{i,j}^{(0)} = \delta_i(j)} e para {n>0}

\displaystyle  p_{i,j}^{(n)} \stackrel{\text{\tiny def}}{=} \mathop{\mathbb P}\big(X_{n}=j~|~X_0=i\big)

é a transição do estado {i} para o estado {j} em {n} passos.

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_{i,s}^{(k)}p_{s,j}^{(t)} \end{array}

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

Lema 23 (Identidade de Chapman–Kolmogorov) Se {p_{i,j}} são as probabilidades de transição de uma cadeia de Markov então

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

para quaisquer {i,~j\in S}.

— Exemplos —

Convencionamos que quando é dada uma definição de uma cadeia de Markov, as probabilidades das transições 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 no interesse do momento ou é trivial (i.e., {\mathop{\mathbb P}(X_0=s)=1} para algum {s}).

Exemplo 110 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 111 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 112 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 113 (passeio aleatório em uma dimensão) 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 114 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 115 (Cadeia de Markov não-homogênea) Suponha {Y_1,Y_3,\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 116 (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 117 (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.

Exemplo 118 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 (18), 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}.

Exemplo 119 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.

screenshot-11

Exercicio 101 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}.

Exercicio 102 (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 Z_i \right) = \mathop{\mathbb E}(N)\mathop{\mathbb E}(Z). \ \ \ \ \ (50)

No exemplo 117, 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}.

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