bc1414 – Distribuição invariante de uma cadeia de Markov

— Representação matricial —

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, que não depende de {t} por homogeneidade temporal, 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} é a matriz de transição em {k} passos

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

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.

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

Exemplo 130 No caso do exemplo 119 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}.

No exemplo acima, se fizermos {\pi^{(0)} = \varrho}, a distribuição inicial, então {\pi^{(1)} = \pi^{(0)}P} é a função de massa de probabilidade de {X_1}, na posição {i} do vetor lemos {\pi^{(1)}_i=\mathop{\mathbb P}(X_i=i)}. Por exemplo, para

\displaystyle \pi^{(0)} = \begin{pmatrix} 1/4 & 1/4 & 1/4 & 1/4 \end{pmatrix}

a distribuição uniforme em {S}, então temos

\displaystyle \pi^{(1)} = \begin{pmatrix} 0,285 & 0,15 & 0,165 & 0,4 \end{pmatrix}

Analogamente, {\pi^{(2)}} é a função de massa de {X_2} e, em geral, para {n\in {\mathbb N}}

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

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

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

— Distribuição invariante —

Um vetor de probabilidades {\pi = (\pi_j)_{j\in S}} que satisfaz

\displaystyle   \pi_j = \sum_{k\in S} \pi_k p_{k,j} \ \ \ \ \ (56)

ou, na forma matricial,

\displaystyle \pi=\pi P

é chamado de distribuição invariante ou distribuição estacionária da cadeia de Markov com matriz de transições {P}.

No último exemplo,

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

é invariante, como o leitor pode verificar. No caso do modelo de Ehrenfest vimos que

\displaystyle  \pi(k) = \frac 1{2^N}\binom Nk \qquad 0\leq k\leq N

é invariante.

Quando {S} é finito temos que se

\displaystyle p_{i,j}^{(n)} \rightarrow \pi_j \text{ quando }n\rightarrow\infty\text{ para todo estado }j

então {\pi=(\pi_j)_j} é invariante. De fato

\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 125, temos {p_{i,j}^{(n)}\rightarrow 0} pois a cadeia é transiente e então o vetor limite {\pi} não é um vetor de probabilidades. Também, no caso {S} finito a existência de um vetor invariante é 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| \ \ \ \ \ (57)

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\}. \ \ \ \ \ (58)

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

Teorema 26 Uma cadeia de Markov irredutível tem distribuição invariante se, e só se, a cadeia for recorrente positiva. Nesse caso,

\displaystyle \pi_j= \frac 1{\mu_j}

para cada estado {j} é a única distribuição estacionária

Demonstracao: Consideremos uma cadeia de Markov irredutível e recorrente positiva {\{X_t\}_{t\in {\mathbb N}}} com distribuição inicial {\varrho} e matriz de transição {P=(p_{i,j})_{i,j\in S}} e vamos construir uma distribuição invariante {\pi=(\pi_j)_{j\in S}.}

Fixemos um estado {k} e seja {\gamma_i = \gamma_i(k)} o número de visitas ao estado {i} entre duas visitas a {k}, em média, ou seja

\displaystyle  \gamma_i(k) \stackrel{\text{\tiny def}}{=} \mathop{\mathbb E} \left( \sum_{t=1}^{T_k} 1_{[X_t=i]}~\bigg|~X_0=k \right) = \sum_{t\geq 1} \mathop{\mathbb P} (X_t = i, t \geq T_k~|~X_0=k)

donde {\gamma_k(k) =1}. Vamos mostrar que o vetor {\gamma = \gamma(k)} dado por

\displaystyle  \gamma = ( \gamma_i )_{i\in S}

é um vetor invariante.

Primeiro, notemos que pela propriedade de Markov, condicionado ao evento {[X_{t-1}=j]}, o processo estocástico {X_{t-1},X_t,\dots} é uma cadeia de Markov com respeito ao estado inicial {j} e matriz de transição {P} independente das variáveis aleatórias {X_0,X_1,X_2,\dots,X_{t-1}}, também o evento {[t \leq T_k ]} depende somente de {X_0,X_1,X_2,\dots,X_{t-1}} portanto, como {T_k<\infty}

\displaystyle   \mathop{\mathbb P} ( {X_{t-1} = j, X_t=i, t \leq T_k}~|~{X_0=k}) = \mathop{\mathbb P} ( {X_{t-1} = j, t \leq T_k}~|~{X_0=k}) p_{j,i} \ \ \ \ \ (59)

e segue da definição de {\gamma_i} que

\displaystyle \gamma_i= \sum_{j\in S}\sum_{t\geq 1} \mathop{\mathbb P} ( {X_{t-1} = j, X_t=i, t \leq T_k}~|~{X_0=k})

logo

\displaystyle  \begin{array}{rcl}  \gamma_i & = & \sum_{j\in S}\sum_{t\geq 1} \mathop{\mathbb P} ( {X_{t-1} = j, t \leq T_k}~|~{X_0=k})p_{j,i} \\ & = & \sum_{j\in S} p_{j,i}\sum_{t\geq 1} \mathop{\mathbb P}( {X_{t-1} = j, t \leq T_k}~|~{X_0=k})\\ & = & \sum_{j\in S} p_{j,i}\sum_{t\geq 0} \mathop{\mathbb P}( {X_{t} = j, t \leq T_k-1}~|~{X_0=k})\\ &= & \sum_{j\in S} p_{j,i}\gamma_j \end{array}

o que dá a invariância do vetor {\gamma=\gamma(k)}. Ademais, para o estado {k} fixado, pela irredutibilidade da cadeia para todo estado {j} devem existir {n,m >0} tais que {p_{j,k}^{(n)} >0} e {p_{k,j}^{(m)} >0}. Logo

\displaystyle  \begin{array}{rcl}  1= \gamma_k = & \sum_{i\in S} p_{i,k}^{(n)}\gamma_i\\ \geq & p_{j,k}^{(n)}\gamma_j \end{array}

portanto {\gamma_j=\gamma_j(k)} é finito. Também,

\displaystyle  \begin{array}{rcl}  \gamma_j &= & \sum_{i\in S} p_{i,j}^{(m)}\gamma_i\\ &\geq & p_{k,j}^{(m)}\gamma_k \end{array}

portanto {\gamma_j=\gamma_j(k) > 0 }.

Agora, para termos uma distribuição invariante podemos normalizar o vetor, para todo estado {j}

\displaystyle \pi_j \stackrel{\text{\tiny def}}{=} \frac{\gamma_j}{\sum_{i\in S} {\gamma_i}}

define uma distribuição invariante para a cadeia de Markov. Recordemos que

\displaystyle \mu_k = \mathop{\mathbb E} ( {T_k}~|~{X_0=k} )

que é o número esperados de visitas a outros estados, que não o estado {k}, quando o estado inicial é {k} até a próxima visita ao estado {k}, logo {\mu_k = \sum_{i} \gamma_i} e

\displaystyle \pi_k= \frac{\gamma_k(k)}{\mu_k} = \frac 1{\mu_k}

para qualquer estado {k\in S}.

Para provar a unicidade de {\pi = (\pi_k)_{k\in S}}, suponhamos {\nu} um vetor qualquer com {\nu=\nu P} e todas as entradas positivas. Vamos mostrar que {\nu_j\mu_j=1}. Primeiro, notemos que

\displaystyle  \begin{array}{rcl}  \nu_j\mu_j &=& \nu_j\sum_{n\> 1} \mathop{\mathbb P}({T_j\>n}~|~{X_0=j}) \\ &=& \sum_{n\> 1} \mathop{\mathbb P} ({T_j\>n}~|~{X_0=j}) \mathop{\mathbb P}(X_0=j)\\ &=& \sum_{n\> 1} \mathop{\mathbb P} ( T_j\>n, X_0=j) \\ &=& \sum_{n\> 1} \mathop{\mathbb P}(X_{n-1}\neq j, \cdots,X_1\neq j) - \mathop{\mathbb P} (X_{n-1}\neq j, \cdots,X_1\neq j, X_0\neq j) \\ &=& \sum_{n\> 1} \mathop{\mathbb P} (X_{n-2}\neq j, \cdots,X_0\neq j) - \mathop{\mathbb P}(X_{n-1}\neq j, \cdots,X_1\neq j, X_0\neq j) \\ &=& \mathop{\mathbb P}(X_0 = j) + \mathop{\mathbb P}( X_0\neq j) - \lim_{n\rightarrow\infty} \mathop{\mathbb P}(X_{n}\neq j, \cdots,X_0\neq j) \end{array}

como o limite é {0}, por causa da recorrência de {j}, o resultado é que {\nu_j\mu_j =1}, ou seja, {\nu_j =1/\mu_j = \pi_j}, ou seja, .

Até aqui estabelecemos que uma cadeia de Markov recorrente positiva e irredutível tem uma distribuição estacionária única que satisfaz~{ \pi_k = 1/{\mu_k}} para todo ~{k\in S}.

Agora, se uma cadeia irredutível admite uma distribuição estacionária {\pi}, então {\pi = \pi P^n} e podemos escolher {n} tal que

\displaystyle  \pi_k = \sum_j \pi_jp_{j,k}^{(n)} >0

pois a cadeia é irredutível. Assim {\lambda_i = \pi_i/\pi_k}, para todo {i\in S}, define um vetor invariantepara {P} e não-negativo tal que {\lambda_k=1}. Vamos assumir, por ora que

\displaystyle  \lambda_j \> \gamma_j(k) \ \ \ \ \ (60)

para todo {j}, em que {\gamma_j} é como definido no começo da demonstração. Então

\displaystyle  \mu_k = \sum_i \gamma_i(k) \leq \sum_i \frac{\pi_i}{\pi_k} =\frac 1{\pi_k} < \infty

o que mostra que {k} é recorrente positivo. \Box

Exercicio 108 Verifique que se {P} é estocástica então {P^n} também é estocástica.

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