bc1414 – Recorrência, transiência e período

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 o estado é dito transiente (ou, transitório). Quando o estado é recorrente, a cadeia visita-o infinitas vezes pois uma vez que a cadeia esteja em tal 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.

Além disso, a recorrência pode se dar em instantes que são múltiplos de um inteiro positivo, como no caso do passeio aleatório simétrico em uma dimensão, no qual o retorno à origem se dá só nos instantes múltiplos de {2}. Nesse caso, dizemos que o estado tem período {2}; um estado de período {1} é dito aperiódico.

— Transiência e recorrência —

Para {n\in{\mathbb N}}, seja {f_{i,j}^{(n)}} a probabilidade do evento “primeira passagem pelo estado {j} a partir do estado {i} em {n} passos”

\displaystyle  X_0=i,~ X_1\neq j, ~ X_2\neq j,~ \cdots ,~X_{n-1}\neq j,~X_n=j

com {f_{i,j}^{(0)}=0}, 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 {i}. Com essa definição, um estado {i} é recorrente se e somente se {f_{i,i}=1}, caso contrário {f_{i,i}<1} e chamamos {i} de transiente.

Distribuição do primeiro retorno. No caso em que {i} é recorrente {f_{i,i}=1} e temos uma função de massa probabilidade {\{f_{i,i}^{(n)}\}_{n>0}} para o tempo de retorno ao estado {i} e média dessa v.a., chamado de tempo médio de recorrência (ou, tempo médio de retorno) para {i}, é

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

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

Definimos a v.a.

\displaystyle   T_i \stackrel{\text{\tiny def}}{=} \min \{n\geq 1\colon X_n = i\} \ \ \ \ \ (51)

e fica convencionado que {T_i=\infty} se a cadeia nunca passa por {i}. Claramente, {\mathop{\mathbb P}(T_i=\infty ~|~ X_0=i) > 0} se, e só se, {i} é transiente, ademais

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

Ressalvamos que {\mu_i=\infty} pode ocorrer para {i} recorrente. 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 (ou não-nulo).

Vimos que no passeio aleatório simétrico em uma dimensão o estado {0} é recorrente nulo.

Exemplo 120 No exemplo 112, {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, por continuidade de {\mathop{\mathbb P}}, 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, o estado {1} é recorrente nulo.

Exemplo 121 No caso da cadeia representada no diagrama abaixo

corrigido

\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

\displaystyle  \mu_1 = \frac 12 + \frac 18 \sum_{n\geq 2} n\left( \frac 34 \right)^{n-2} = \frac 12 + \frac 16 \sum_{n\geq 2} n\left( \frac 34 \right)^{n-1}= \frac 12 + \frac 16 15 = 3

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

Exemplo 122 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

periodica2

— Período —

Numa cadeia de Markov que pode ser representada como

periodica1

{p_{0,0}^{(n)}>0} só pode ocorrer na cadeia em instantes {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 7 Suponha que, como no exemplo acima, numa cadeia de Markov todos os estados tenham o mesmo período {t>1} e que para cada par de estados {(i,j)} existe um instante {n} para o qual {p_{i,j}^{(n)}>0} (de fato, essa 2 hipóteses são, em certo sentido, redundantes, como veremos no lema 25).

Para todo estado {k} da cadeia devem existir instantes {m} e {n} tais que

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

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 classes {S_0, S_1, \dots, S_{t-1}} (no exemplo acima {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},S_0}, 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.

Um estado ao qual a cadeia não retorna e considerado aperiódico. Um estado recorrente não-nulo e aperiódico é dito ergódico.

Exercicio 103 Prove que

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

Para tal, deduza da propriedade de Markov que

\displaystyle  \mathop{\mathbb P}\big(X_0=j,~ X_1\neq k, ~ X_2\neq k,~ \cdots ,~X_{t-1}\neq k,~X_t=k,~X_n=k \big) =

\displaystyle  \mathop{\mathbb P}\big(X_0=j,~ X_1\neq k, ~ X_2\neq k,~ \cdots ,~X_{n-1}\neq k,~X_t=k ~\big|~ X_0=j\big)\mathop{\mathbb P}\big(X_n=k~\big|~X_t=k\big).

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

Seja {I_{[X_n=i]}} a v.a. indicadora do evento {[X_n=i]}. Então a soma para todo {n\geq 0} das variáveis {I_{[X_n=i]}} é o número de vezes que a cadeia visita o estado {i},

\displaystyle  V_i \stackrel{\text{\tiny def}}{=} \sum_{n\geq 0} I_{[X_n=i]}

que afirmamos acima ser finito se e só se {n} é transiente. De fato, pelo exercício 49,

\displaystyle  \mathop{\mathbb E} \left( V_i ~\big|~ X_0=i \right)= \sum_{k\geq 1} \mathop{\mathbb P}\big( V_i \geq k ~\big|~ X_0=i \big)

e, saindo de {i}, visitar {j} pelo menos {k} vezes equivale a visitar {j} e em seguida visitar {j} pelo menos {k-1} vezes, o que ocorre com probabilidade {f_{i,j}(f_{j,j})^{k-1}} logo, fazendo {j=i} temos

\displaystyle \mathop{\mathbb E} \left(V_i ~\big|~ 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}

Pela linearidade da esperança,

\displaystyle  \mathop{\mathbb E} \left( V_i~|~X_0=i \right)= \sum_{n\geq 0} \mathop{\mathbb E} \left( I_{[X_n=i]}~\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 as caracterizações seguem das considerações acima a respeito da esperança condicionada: {i} é transiente se e só se {\sum_{n\geq 0} p_{i,i}^{(n)} < \infty}; {i} é recorrente se e só se {\sum_{n\geq 0} p_{i,i}^{(n)} = \infty}. Ademais, o exercício 103 acima implica que no caso {i} transiente {\sum_{n\geq 0} p_{j,i}^{(n)} < \infty} para todo {j}, portanto {\lim_{n\rightarrow\infty} p_{j,i}^{(n)} =0} para todo {j}. No caso {i} recorrente, um resultado que veremos implica em {\sum_{n\geq 0} p_{i,i}^{(n)} = \infty} e {\lim_{n\rightarrow\infty} p_{i,i}^{(n)} = 0} no caso recorrente nulo e aperiódico, e também pelo exercício 103, {\lim_{n\rightarrow\infty} p_{j,i}^{(n)} = 0}, para todo {j}.

Lema 24 O estado {i} é

  • transiente se e só se {\displaystyle\sum_{n\geq 0} p_{i,i}^{(n)} < \infty}. Nesse caso, {\displaystyle\sum_{n\geq 0} p_{j,i}^{(n)} < \infty} para todo {j}, portanto, {p_{j,i}^{(n)}\rightarrow 0} quando {n\rightarrow\infty}, para todo {j}.
  • recorrente se e só se {\displaystyle\sum_{n\geq 0} p_{i,i}^{(n)} = \infty}. Nesse caso {\displaystyle\sum_{n\geq 0} p_{j,i}^{(n)} = \infty} para todo {j} tal que {f_{j,i}>0}. Ainda se {i} é recorrente nulo, então {p_{j,i}^{(n)}\rightarrow 0}, quando {n\rightarrow\infty}, para todo {j}.

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