Capítulo 2

Cadeias de Markov finitas

Nas cadeias de Markov, o futuro depende do presente, não do caminho percorrido até ele.

Um jogo termina ao atingir uma barreira; uma rede de memória procura corrigir uma entrada; um usuário pode voltar a um serviço ou abandoná-lo. A descrição de cada sistema começa pela escolha do estado, que deve conservar a informação necessária para prever o próximo passo.

Os modelos finitos permitem construir matrizes de transição, classificar estados e estudar retornos e saídas por meio de contas explícitas. O equilíbrio e a convergência serão tratados no capítulo seguinte. Os modelos ocultos de Markov encerram o percurso como aplicação complementar; PageRank e colônias de formigas acompanham o estudo do comportamento limite.

Uma rede que recupera uma lembrança

Reconhecemos uma letra mesmo quando alguns traços estão apagados. Uma memória associativa recebe uma configuração incompleta ou corrompida e a modifica para aproximá-la de um padrão armazenado. Um modelo mínimo desse mecanismo introduz a escolha do estado e sua evolução aleatória.

Representamos cada neurônio por uma unidade que pode estar inativa ou ativa. A configuração de uma rede com $N$ unidades neuronais no instante $n$ é o vetor

\[ s(n)=(s_1(n),\ldots ,s_N(n)),\qquad s_i(n)\in \{ -1,+1\} . \]

Essa variável binária também é chamada de spin, por analogia com modelos da física. O peso $w_{ij}$ mede a influência de $j$ sobre $i$; nesta primeira versão, $w_{ij}=w_{ji}$ e $w_{ii}=0$. O campo local na unidade $i$ é

\[ h_i(s(n))=\sum _{j\ne i}w_{ij}s_j(n). \]

Ilustração: Uma rede que recupera uma lembrança

Figura 2.1 Uma configuração possível de uma rede com cinco unidades. Os números nas arestas são os pesos não nulos das interações; cada peso vale nos dois sentidos, pois $w_{ij}=w_{ji}$. Os rótulos junto aos vértices mostram os spins da configuração $s=(+1,-1,+1,+1,-1)$.

Em cada passo, escolhemos aleatoriamente uma das $N$ unidades, todas com probabilidade $1/N$, independentemente das escolhas anteriores. Apenas a unidade escolhida é atualizada: essa é uma dinâmica assíncrona. Se ela é a unidade $i$, tomamos $s_i(n+1)=+1$ quando $h_i(s(n))\gt 0$ e $s_i(n+1)=-1$ quando $h_i(s(n))\lt 0$; se $h_i(s(n))=0$, conservamos o valor anterior, $s_i(n+1)=s_i(n)$. Para $j\ne i$, fazemos $s_j(n+1)=s_j(n)$.

A escolha aleatória da unidade a atualizar determina, a partir da configuração atual, a distribuição da configuração seguinte.

Aprendizado e recuperação são tarefas distintas. No aprendizado, escolhemos os pesos a partir dos padrões que desejamos guardar. Na recuperação, fixamos esses pesos e deixamos a configuração evoluir a partir da entrada recebida. A rede não precisa consultar uma lista de padrões a cada atualização: a informação foi incorporada às interações.

Para guardar o padrão $\xi =(+1,+1,+1)$ em três unidades, tomemos $w_{ij}=1/3$ para $i\ne j$. Se a entrada é $s(0)=(-1,+1,+1)$, então

\[ h_1(s(0))=\tfrac 13(+1)+\tfrac 13(+1)=\tfrac 23\gt 0. \]

A atualização da primeira unidade corrige o spin errado. Podemos acompanhar essa correção por uma energia,

\[ E(s)=-\sum _{i\lt j}w_{ij}s_is_j. \]

As energias antes e depois da correção são

\[ E(s(0))=E(-1,+1,+1)=\tfrac 13, \qquad E(s(1))=E(+1,+1,+1)=-1. \]

A mudança é $-4/3$. Mais geralmente, ao alterar apenas a unidade $i$, a simetria dos pesos dá

\[ E(s(n+1))-E(s(n))=-(s_i(n+1)-s_i(n))h_i(s(n))\leq 0. \]

A energia não aumenta com a atualização. Isso não garante que toda entrada chegue ao padrão desejado: podem existir outros estados estáveis, e o armazenamento de muitos padrões pode gerar interferência entre eles.

Ilustração: Uma rede que recupera uma lembrança

Figura 2.2 Atualização da primeira unidade na rede de três spins. A configuração passa de $s(0)=(-1,+1,+1)$ para $s(1)=(+1,+1,+1)$, e a energia diminui de $1/3$ para $-1$. Na escolha uniforme da unidade, essa correção tem probabilidade $1/3$ no próximo passo.

Conhecida a configuração $s(n)$, a escolha aleatória da unidade determina a lei de $s(n+1)$ sem depender das configurações anteriores. O processo $(s(n))_{n\geq 0}$ é, portanto, uma cadeia de Markov no espaço $\{ -1,+1\} ^N$.

O estudo da rede envolve a identificação de configurações estáveis, os tempos de chegada a essas configurações e a influência da aleatoriedade. O capítulo de MCMC retomará a rede de Hopfield com a definição completa, a demonstração de descida da energia, um exemplo com duas letras e a passagem para atualizações de Gibbs.

2.1 Definições e exemplos

As definições e vários resultados também valem para espaços enumeráveis, mas neste capítulo privilegiaremos os modelos finitos. O Capítulo 4 estudará os fenômenos próprios dos espaços infinitos. A seção opcional sobre colônias de formigas, no Capítulo 3, apresenta uma dinâmica com estado contínuo.

A distribuição inicial e as probabilidades de transição determinam a lei da trajetória. O estado $X_n$ deve reunir a informação do passado relevante para prever o passo seguinte. Quando essa informação é insuficiente, pode ser necessário ampliar o estado.

Definição 2.1

Cadeia de Markov Considere um processo estocástico em tempo discreto $(X_n)_{n\geq 0}$ com valores no espaço de estados $S$. Dizemos que $(X_n)$ é uma cadeia de Markov se, para todo $n\geq 0$ e quaisquer estados $i_0,\ldots ,i_n,j$ tais que o evento $\{ X_0=i_0,\ldots ,X_n=i_n\} $ tenha probabilidade positiva,

\begin{equation} \begin{aligned} & \mathbb {P}(X_{n+1}=j\mid X_n=i_n,X_{n-1}=i_{n-1},\ldots ,X_0=i_0)\\ & \qquad =\mathbb {P}(X_{n+1}=j\mid X_n=i_n). \end{aligned} \label{eq:propriedade-markov} \tag{2.1} \end{equation}

Assim, uma vez conhecido o estado atual, o histórico não fornece informação adicional sobre o próximo estado.

Definição 2.2

Cadeia homogênea e matriz de transição A cadeia é homogênea no tempo quando

\[ p(i,j)=\mathbb {P}(X_{n+1}=j\mid X_n=i) \]

não depende de $n$. A matriz $P=(p(i,j))_{i,j\in S}$ é sua matriz de transição. Suas entradas são não negativas e cada linha soma $1$.

Na entrada $p(i,j)$, a linha $i$ representa o estado atual e a coluna $j$ representa o próximo estado. Portanto,

\[ \sum _{j\in S}p(i,j)=1 \]

para cada $i$: partindo de $i$, a cadeia precisa estar em algum estado no passo seguinte.

A matriz descreve uma transição. Para calcular a probabilidade de uma trajetória inteira, basta aplicar repetidamente a regra do produto para probabilidades condicionais.

Proposição 2.1

Probabilidade de um caminho Se $(X_n)$ é uma cadeia de Markov homogênea com distribuição inicial $\mu $ e matriz de transição $P$, então, para $i_0,\ldots ,i_n\in S$,

\[ \mathbb P(X_0=i_0,\ldots ,X_n=i_n) =\mu (i_0)\prod _{k=1}^{n}p(i_{k-1},i_k). \]

Para $n=0$, o produto vazio vale $1$.

Demonstração ▼

Para $n=0$, a igualdade é a definição de $\mu $. Suponha que ela valha até o instante $n$. Quando a história $X_0=i_0,\ldots ,X_n=i_n$ tem probabilidade positiva, a regra do produto e a propriedade de Markov dão

\[ \begin{aligned} & \mathbb P(X_0=i_0,\ldots ,X_{n+1}=i_{n+1})\\ & \quad =\mathbb P(X_0=i_0,\ldots ,X_n=i_n)\, p(i_n,i_{n+1}). \end{aligned} \]

Se a história tem probabilidade zero, a trajetória mais longa também tem probabilidade zero, e o produto no enunciado já é nulo. Isso conclui a indução.

O mesmo cálculo explica por que podemos condicionar em informações parciais do passado, sem precisar conhecer todos os estados visitados.

Corolário 2.2

Markov para eventos do passado Fixe $n\geq 0$ e um evento $A$ determinado pelos estados $X_0,\ldots ,X_{n-1}$. Se $\mathbb P(A,X_n=i)\gt 0$, então, para $j_1,\ldots ,j_m\in S$ e $m\geq 1$,

\[ \begin{aligned} & \mathbb P(X_{n+1}=j_1,\ldots ,X_{n+m}=j_m \mid A,X_n=i)\\ & \qquad =p(i,j_1)p(j_1,j_2)\cdots p(j_{m-1},j_m). \end{aligned} \]

Para $n=0$, entendemos $A$ como o evento certo.

Demonstração ▼

Primeiro considere uma história completa $X_0=i_0,\ldots ,X_n=i$. A regra do produto aplicada à história e à sua continuação mostra que a probabilidade condicional dos próximos $m$ estados é o produto anunciado; os fatores anteriores ao instante $n$ se cancelam.

Como $S$ é finito, o evento $A\cap \{ X_n=i\} $ é união disjunta de histórias completas até $n$. Em cada história de probabilidade positiva, a probabilidade condicional da continuação é a mesma. Somando sobre essas histórias, obtemos a igualdade para $A$, sem depender dos estados anteriores a $n$.

Proposição 2.3

Homogeneidade em vários passos Se $(X_n)_{n\geq 0}$ é uma cadeia de Markov homogênea, então, para todo $m\geq 1$ e quaisquer estados $i,j$,

\[ \mathbb {P}(X_{n+m}=j\mid X_n=i) \]

não depende de $n$, sempre que o condicionamento estiver definido.

Demonstração ▼

A prova é por indução em $m$. Para $m=1$, a afirmação é exatamente a definição de homogeneidade.

Suponha agora que, para algum $m\geq 1$, as probabilidades

\[ p^{(m)}(i,k)=\mathbb {P}(X_{n+m}=k\mid X_n=i) \]

não dependam de $n$. Condicionando no estado intermediário $X_{n+m}$ e usando o Corolário 2.2 para o passado $X_n=i$,

\[ \begin{aligned} \mathbb {P}(X_{n+m+1}=j\mid X_n=i) & =\sum _{k\in S} p(k,j)\, \mathbb {P}(X_{n+m}=k\mid X_n=i)\\ & =\sum _{k\in S} p(k,j)\, p^{(m)}(i,k). \end{aligned} \]

Pela hipótese de indução, o lado direito não depende de $n$. Isso conclui a indução.

A homogeneidade em um passo estende-se, portanto, a qualquer número fixo de passos.

Exemplo 2.1 (Um sapo em quatro folhas)

Um sapo ocupa uma de quatro folhas, que chamaremos de $A$, $B$, $C$ e $D$. Nem toda folha está ao alcance de qualquer outra: as ligações possíveis são as indicadas no grafo abaixo. A cada passo, o sapo escolhe uniformemente uma das folhas ligadas à folha em que se encontra. Se $X_n$ indica a folha ocupada depois do $n$-ésimo salto, então $(X_n)$ é uma cadeia de Markov: conhecida a folha atual, o próximo salto não depende do caminho percorrido antes.

Figura 2.3 O sapo escolhe uniformemente uma folha vizinha. Assim, $A$ e $B$ têm duas opções, $C$ tem três e, partindo de $D$, o salto para $C$ é obrigatório.

Na ordem $(A,B,C,D)$, as probabilidades são obtidas contando os vizinhos de cada folha. A matriz de transição é

\[ P=\begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 1/3 & 1/3 & 0 & 1/3 \\ 0 & 0 & 1 & 0 \end{pmatrix}. \]

Daqui em diante, salvo indicação contrária, consideraremos cadeias homogêneas no tempo. Nas fórmulas de probabilidades condicionais, entenderemos sempre que o evento condicionado tem probabilidade positiva. A matriz de transição especifica a dinâmica a partir de cada estado, inclusive daqueles que têm probabilidade inicial zero.

Exemplo 2.2 (Ruína do jogador)

Considere um jogo com rodadas independentes. Em cada rodada, o jogador ganha uma unidade monetária com probabilidade $p=0{,}4$ ou perde uma unidade com probabilidade $1-p=0{,}6$. O jogo termina quando sua fortuna atinge $0$ ou $N$ unidades monetárias.

Se $X_n$ é a fortuna depois de $n$ rodadas, então, para $0\lt i\lt N$ e qualquer histórico compatível,

\[ \mathbb {P}\left(X_{n+1}=i+1 \mid X_n=i, X_{n-1}=i_{n-1}, \ldots ,X_0=i_0\right)=0{,}4. \]

O lado direito depende apenas da fortuna presente, de modo que a propriedade de Markov vale. As transições são

\[ \begin{aligned} & p(i,i+1)=0{,}4, \quad p(i,i-1)=0{,}6, \quad \text{se }0\lt i\lt N, \\ & p(0,0)=1, \qquad p(N,N)=1. \end{aligned} \]

Para $N=5$, o grafo de transição torna visíveis as duas possibilidades em cada estado interior e as duas barreiras absorventes:

Figura 2.4 Grafo da ruína do jogador com barreiras $0$ e $5$. As barreiras são absorventes; nos estados interiores, a fortuna sobe uma unidade com probabilidade $0{,}4$ e desce uma unidade com probabilidade $0{,}6$.

A matriz correspondente é

	0	1	2	3	4	5
0	1{,}0	0	0	0	0	0
1	0{,}6	0	0{,}4	0	0	0
2	0	0{,}6	0	0{,}4	0	0
3	0	0	0{,}6	0	0{,}4	0
4	0	0	0	0{,}6	0	0{,}4
5	0	0	0	0	0	1{,}0

Os estados 0 e $N$ são absorventes: quando a fortuna atinge uma das barreiras, o jogo termina.

Para distinguir um caminho particular de uma probabilidade de transição, considere a trajetória

\[ 2\longrightarrow 3\longrightarrow 2\longrightarrow 1\longrightarrow 0. \]

Ela tem probabilidade $0{,}4(0{,}6)^3=0{,}0864$. A figura mostra essa realização; outras sequências também podem levar à ruína.

Figura não resolvida: figuras/ruina-trajetoria.tikz

Figura 2.5 Uma realização da ruína do jogador com $N=5$, começando com fortuna $2$ e sendo absorvida em $0$ no quarto passo.

Exemplo 2.3 (Cadeia de Ehrenfest)

Esta cadeia surgiu na física como um modelo simplificado da troca de partículas entre dois recipientes. Na versão matemática, distribuímos $N\geq 1$ bolas entre duas urnas. A cada passo, escolhemos uma das $N$ bolas ao acaso e a transferimos para a outra urna.

Ilustração: Definições e exemplos

Figura 2.6 Na cadeia de Ehrenfest, escolhemos uma das $N$ bolas e a transferimos para a outra urna. Se há $i$ bolas à esquerda, o número de bolas nessa urna diminui com probabilidade $i/N$ e aumenta com probabilidade $(N-i)/N$.

Seja $X_n$ o número de bolas na urna esquerda depois do $n$-ésimo passo. Conhecer $X_n=i$ basta para determinar as probabilidades do passo seguinte: há $N-i$ bolas na urna direita e $i$ na esquerda. Assim, para $0\leq i\lt N$,

\[ \mathbb {P}\left(X_{n+1}=i+1 \mid X_{n}=i, X_{n-1}=i_{n-1}, \ldots ,X_{0}=i_{0}\right) =\frac{N-i}{N}, \]

pois $X_n$ aumenta quando a bola escolhida está na urna direita. Do mesmo modo, $X_n$ diminui em uma unidade com probabilidade $i/N$. Logo,

\[ p(i,i+1)=\frac{N-i}{N}\quad (0\leq i\lt N), \qquad p(i,i-1)=\frac{i}{N}\quad (0\lt i\leq N), \]

e $p(i,j)=0$ nos demais casos. Quando $N=4$, por exemplo, a matriz é

	0	1	2	3	4
0	0	1	0	0	0
1	1/4	0	3/4	0	0
2	0	2/4	0	2/4	0
3	0	0	3/4	0	1/4
4	0	0	0	1	0

Nos exemplos da ruína do jogador e de Ehrenfest, partimos de uma descrição verbal e extraímos as probabilidades de transição. Reciprocamente, qualquer família $p(i,j)$ que satisfaça

$p(i,j)\geq 0$ para todos os estados $i,j$;
$\sum _jp(i,j)=1$ para cada estado $i$,

define uma matriz de transição. Para construir a cadeia, estando em $i$, sorteamos o próximo estado $j$ segundo a distribuição dada pela linha $i$ da matriz.

Outra maneira de descrever uma cadeia é por uma recorrência aleatória:

\[ X_{n+1}=f(X_n,Z_{n+1}), \]

em que $Z_1,Z_2,\ldots $ são novas entradas aleatórias, independentes e com a mesma distribuição, também independentes de $X_0$. O próximo sorteio independe do passado; portanto, a lei de $X_{n+1}$ depende apenas de $X_n$, e a cadeia é homogênea.

Exemplo 2.4 (Uma oficina de reparos)

Seja $X_n$ o número de máquinas aguardando reparo no início do dia $n$. A oficina conserta uma máquina por dia, quando há alguma esperando. Ao final do dia, chegam $Z_{n+1}$ novas máquinas com defeito. A regra é

\[ \boxed {X_{n+1}=(X_n-1)^++Z_{n+1}}, \qquad x^+=\max \{ x,0\} . \]

Suponha que as chegadas de dias diferentes sejam independentes, com

\[ \mathbb P(Z_n=0)=\frac12,\qquad \mathbb P(Z_n=1)=\frac14,\qquad \mathbb P(Z_n=2)=\frac14. \]

Se $X_n=2$, a oficina conserta uma máquina e resta uma antes das novas chegadas. Logo,

\[ p(2,1)=\frac12,\qquad p(2,2)=\frac14,\qquad p(2,3)=\frac14. \]

Já se $X_n=0$ ou $X_n=1$, não sobra nenhuma máquina depois do reparo, e $X_{n+1}=Z_{n+1}$. Assim, as linhas de transição correspondentes a $0$ e $1$ são iguais.

A recorrência determina o próximo estado a partir do número atual de máquinas e das novas chegadas, sem exigir a escrita de uma matriz infinita.

Exemplo 2.6 (A vida de um computador)

Um computador de escritório pode estar funcionando ($F$), em reparo ($R$) ou definitivamente descartado ($D$). Ao final de um dia de funcionamento, permanece funcionando no dia seguinte com probabilidade $0{,}995$ e entra em reparo com probabilidade $0{,}005$. Se está em reparo, volta a funcionar com probabilidade $0{,}90$, continua em reparo com probabilidade $0{,}05$ e é descartado com probabilidade $0{,}05$. Depois do descarte, não retorna ao serviço.

\[ P=\begin{array}{c|ccc}& F& R& D\\ \hline F& 0{,}995& 0{,}005& 0\\ R& 0{,}90& 0{,}05& 0{,}05\\ D& 0& 0& 1 \end{array}. \]

Figura não resolvida: figuras/computador-manutencao.tikz

Figura 2.8 Funcionamento e reparo podem alternar; o descarte é um estado absorvente.

A condição atual determina a lei do dia seguinte. Mais adiante veremos como calcular o número esperado de dias em cada condição antes do descarte.

Exemplo 2.7 (Um canal de comunicação com ruído)

Um dígito binário atravessa sucessivas etapas de transmissão. Em cada etapa, um $0$ é trocado por $1$ com probabilidade $a$, enquanto um $1$ é trocado por $0$ com probabilidade $b$, independentemente do que ocorreu antes. Se $X_n\in \{ 0,1\} $ é o dígito que entra na etapa $n$, então $(X_n)$ é uma cadeia de Markov com matriz

\[ P=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}. \]

Interessa calcular $\mathbb {P}(X_n=X_0)$ e examinar se a informação sobre o bit original desaparece quando $n$ cresce. O canal simétrico corresponde ao caso $a=b=1-p$, em que cada etapa preserva o dígito com probabilidade $p$.

Exemplo 2.8 (Quando uma soma perde informação)

Sejam $Y_0,Y_1,\ldots $ Bernoulli independentes, com parâmetro $1/2$, e ponha $Z_n=Y_{n-1}+Y_n$ para $n\geq 1$. Conhecer $Z_2=1$ deixa duas possibilidades equiprováveis para $(Y_1,Y_2)$, de modo que

\[ \mathbb {P}(Z_3=0\mid Z_2=1)=1/4. \]

Mas, se sabemos também que $Z_1=0$, então $Y_1=0$ e $Y_2=1$; portanto

\[ \mathbb {P}(Z_3=0\mid Z_2=1,Z_1=0)=0. \]

Os eventos condicionados têm probabilidade positiva. Assim, $(Z_n)$ não é uma cadeia de Markov: a soma esconde informação que o passado ajuda a reconstruir. O processo dos pares $(Y_{n-1},Y_n)$ tem a propriedade de Markov, pois o próximo par é $(Y_n,Y_{n+1})$ e a nova variável $Y_{n+1}$ é independente das anteriores.

Escrevendo $W_n=(Y_{n-1},Y_n)$, enumeramos os estados na ordem $00,01,10,11$. Como $W_{n+1}=(Y_n,Y_{n+1})$, apenas o segundo algarismo do estado atual e o novo sorteio importam. A matriz de transição é

\[ P_W=\begin{array}{c|cccc}& 00& 01& 10& 11\\ \hline 00& 1/2& 1/2& 0& 0\\ 01& 0& 0& 1/2& 1/2\\ 10& 1/2& 1/2& 0& 0\\ 11& 0& 0& 1/2& 1/2 \end{array}. \]

Por exemplo, para passar de $00$ a $11$ em dois passos, o único caminho possível é $00\to 01\to 11$; logo,

\[ P_W^2(00,11)=\frac12\cdot \frac12=\frac14. \]

A soma $Z_n$ pode ser recuperada de $W_n$, mas não o contrário: $Z_n=1$ não distingue $01$ de $10$, que levam a distribuições diferentes para o próximo valor da soma. A distinção entre esses estados conserva a informação necessária ao próximo passo.

2.2 Probabilidades de transição em vários passos

A matriz $P$ descreve um passo. Para descrever $m$ passos, precisamos somar sobre todos os estados intermediários possíveis. A multiplicação de matrizes faz exatamente essa contabilidade.

Notação

Distribuição inicial e lei da cadeia A matriz de transição descreve como a cadeia se move, mas ainda é preciso dizer onde ela começa. A distribuição inicial é a distribuição $\mu $ de $X_0$:

\[ \mu (x)=\mathbb {P}(X_0=x),\qquad x\in S. \]

Escrevemos $\mathbb {P}_\mu $ para a lei da trajetória quando $X_0$ tem distribuição $\mu $ e $E_\mu $ para a esperança correspondente.

Quando o estado inicial é fixo, usamos uma notação mais curta: $\mathbb {P}_x$ é a lei da cadeia que começa em $x$, isto é, $\mathbb {P}_x(X_0=x)=1$, e $E_x$ é a esperança sob essa lei. Assim, para qualquer evento $A$ determinado pela trajetória,

\[ \mathbb {P}_\mu (A) =\sum _{x\in S}\mathbb {P}_\mu (A\mid X_0=x)\, \mathbb {P}_\mu (X_0=x) =\sum _{x\in S}\mu (x)\mathbb {P}_x(A). \]

A fórmula apenas separa os casos possíveis para o estado inicial. Quando $\mu (x)\gt 0$, $\mathbb {P}_x$ também pode ser visto como a lei condicional $\mathbb {P}_\mu (\, \cdot \mid X_0=x)$.

Definição 2.3

Probabilidades de transição em $m$ passos Para $m\geq 0$, a probabilidade de transição de $i$ para $j$ em $m$ passos é $\mathbb {P}_i(X_m=j)$. Denotaremos por $P^m$ a matriz dessas probabilidades, com $P^0=I$. O próximo teorema mostrará que ela coincide com a potência matricial usual.

Pela Proposição 2.3 e pela propriedade de Markov,

\[ \mathbb {P}(X_{n+m}=j\mid X_n=i)=\mathbb {P}_i(X_m=j), \]

sempre que o condicionamento estiver definido.

Exemplo 2.9 (O sapo em dois e três passos)

Voltemos ao sapo do Exemplo 2.1. Se ele começa em $A$, para estar novamente em $A$ depois de dois saltos há exatamente duas possibilidades:

\[ A\to B\to A \qquad \text{ou}\qquad A\to C\to A. \]

As probabilidades desses caminhos são, respectivamente,

\[ \frac12\frac12=\frac14 \qquad \text{e}\qquad \frac12\frac13=\frac16. \]

Portanto,

\[ P^2(A,A)=\frac14+\frac16=\frac5{12}. \]

Para o sapo partir de $A$ e chegar a $B$ depois de três saltos, há três caminhos possíveis:

\[ A\to B\to A\to B, \qquad A\to B\to C\to B, \qquad A\to C\to A\to B. \]

Desta vez os caminhos não têm todos a mesma probabilidade:

\[ \frac12\frac12\frac12=\frac18,\qquad \frac12\frac12\frac13=\frac1{12},\qquad \frac12\frac13\frac12=\frac1{12}. \]

Logo,

\[ P^3(A,B) =\frac18+\frac1{12}+\frac1{12} =\frac7{24}. \]

A equação de Chapman–Kolmogorov reúne essas contribuições: fixado um instante intermediário, os caminhos são separados segundo o estado ocupado nesse instante.

Teorema 2.4

Equação de Chapman–Kolmogorov Para $m,n\geq 0$,

\begin{equation} P^{m+n}(i,j) =\sum _{k\in S}P^{m}(i,k)P^{n}(k,j). \label{eq:chapman-kolmogorov-discreta} \tag{2.2} \end{equation}

Em notação matricial, $P^{m+n}=P^mP^n$. Em particular, as probabilidades em $m$ passos são as entradas da potência usual $P^m$.

Demonstração ▼

Condicionamos pelo estado ocupado após os primeiros $m$ passos. Os eventos $\{ X_m=k\} $, para $k\in S$, são disjuntos e cobrem todas as possibilidades, de modo que

\[ \begin{aligned} \mathbb {P}_i(X_{m+n}=j) & =\sum _{k\in S}\mathbb {P}_i(X_m=k,\, X_{m+n}=j)\\ & =\sum _{\substack {k\in S:\\ { P_i(X_m=k)\gt 0 }}} \mathbb {P}_i(X_m=k)\, \mathbb {P}_i(X_{m+n}=j\mid X_m=k). \end{aligned} \]

O primeiro fator é, por definição, $P^m(i,k)$. Para o segundo, o Corolário 2.2 permite esquecer os estados anteriores a $m$ depois que conhecemos $X_m=k$; pela homogeneidade, podemos ainda deslocar a origem do tempo. Portanto,

\[ \mathbb {P}_i(X_{m+n}=j\mid X_m=k) =\mathbb {P}_k(X_n=j)=P^n(k,j). \]

Substituindo esses dois fatores obtemos

\[ P^{m+n}(i,j)=\sum _k P^m(i,k)P^n(k,j). \]

Se $\mathbb {P}_i(X_m=k)=0$, o termo correspondente já é zero, por isso esses estados podem ser incluídos sem restrição na soma final.

Ilustração: Probabilidades de transição em vários passos

Figura 2.9 Para chegar de $i$ a $j$ em $m+n$ passos, somamos sobre o estado ocupado no instante $m$. Os eventos correspondentes aos diferentes valores de $X_m$ são disjuntos. As setas representam percursos de $m$ e $n$ passos, respectivamente.

Exemplo 2.10 (Ehrenfest: duas trocas de urna)

Voltemos à urna de Ehrenfest do Exemplo 2.3, agora com $N=4$ bolas. Suponha que todas estejam inicialmente na urna da direita, isto é, $X_0=0$. No primeiro passo uma bola vai obrigatoriamente para a esquerda, e $X_1=1$. No segundo, a bola escolhida pode ser a única que está à esquerda, com probabilidade $1/4$, ou uma das outras três, com probabilidade $3/4$. Logo,

\[ \boxed {P^2(0,0)=\frac14,\qquad P^2(0,2)=\frac34.} \]

Nenhum outro estado é possível no segundo passo. A mesma urna será retomada no estudo do equilíbrio e da periodicidade.

Exemplo 2.11 (Dois passos no canal binário)

Para o canal do Exemplo 2.7,

\[ P=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}, \]

e portanto

\[ P^2= \begin{pmatrix} (1-a)^2+ab & a(2-a-b) \\ b(2-a-b) & (1-b)^2+ab \end{pmatrix}. \]

Por exemplo, para começar em 0 e terminar em 1 depois de duas transmissões, há dois caminhos: $0\to 0\to 1$ e $0\to 1\to 1$. Suas probabilidades somam

\[ (1-a)a+a(1-b)=a(2-a-b), \]

que é a entrada $(0,1)$ de $P^2$.

Exemplo 2.13 (A loja: estoque depois de dois dias)

Uma loja acompanha seu estoque no fim do dia, entre $0$ e $3$ unidades. Se terminou o dia com $0$ ou $1$, repõe o estoque até $3$ antes de vender novamente; se terminou com $2$ ou $3$, não encomenda nada. A demanda diária, independente de um dia para outro, é $0$, $1$ ou $2$ unidades, com probabilidades $1/4$, $1/2$ e $1/4$, respectivamente.

Começando com $X_0=2$, qual é a chance de o estoque ser exatamente zero no fim do segundo dia? Para terminar com zero, a loja precisa começar esse segundo dia com $2$ unidades e vender as duas. Se a primeira demanda foi $1$ ou $2$, haverá reposição a $3$ e não será possível terminar em zero, pois a demanda máxima é $2$. Assim, há somente o caminho $2\to 2\to 0$, que exige demanda zero no primeiro dia e demanda dois no segundo:

\[ \boxed {P^2(2,0)=\frac14\cdot \frac14=\frac1{16}.} \]

Mais adiante, no Exemplo 3.5, estudaremos a mesma política para calcular o estoque e o lucro médios no longo prazo.

Exemplo 2.14 (Duas salas e uma saída: calculando $P^n$)

Uma pessoa circula por duas salas, representadas pelos estados $1$ e $2$. A cada passo, ela permanece na mesma sala com probabilidade $1/2$, passa para a outra com probabilidade $1/4$ ou sai do edifício com probabilidade $1/4$. A saída é definitiva e corresponde ao estado absorvente $3$. A matriz de transição é

\[ P=\begin{pmatrix} \frac12 & \frac14 & \frac14 \\ \frac14 & \frac12 & \frac14 \\ 0 & 0 & 1 \end{pmatrix}. \]

Figura não resolvida: figuras/duas-salas-saida.tikz

Figura 2.10 As duas salas permitem permanências e mudanças de sala; de qualquer uma delas é possível chegar à saída, que é absorvente.

Por Chapman–Kolmogorov, para estar na sala $2$ após dois passos, começando na sala $1$, a pessoa pode permanecer primeiro na sala $1$ ou passar imediatamente à sala $2$. Assim,

\[ P^2(1,2) =\frac12\cdot \frac14+\frac14\cdot \frac12 =\frac14. \]

A diagonalização permite calcular $P^n$ para um número qualquer de passos. Os vetores

\[ v_1=\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix},\qquad v_2=\begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix},\qquad v_3=\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \]

são autovetores de $P$, com autovalores $3/4$, $1/4$ e $1$, respectivamente. Tomando-os como colunas, obtemos

\[ S=\begin{pmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \\ 0 & 0 & 1 \end{pmatrix}, \qquad S^{-1}=\begin{pmatrix} \frac12 & \frac12 & -1 \\ \frac12 & -\frac12 & 0 \\ 0 & 0 & 1 \end{pmatrix}. \]

Portanto, $P=S\, \operatorname {diag}(3/4,1/4,1)\, S^{-1}$ e

\[ P^n =S\, \operatorname {diag}\bigl((3/4)^n,(1/4)^n,1\bigr)\, S^{-1} =\begin{pmatrix} \frac{a_n+b_n}{2} & \frac{a_n-b_n}{2} & 1-a_n \\[1mm] \frac{a_n-b_n}{2} & \frac{a_n+b_n}{2} & 1-a_n \\[1mm] 0 & 0 & 1 \end{pmatrix}, \]

onde $a_n=(3/4)^n$ e $b_n=(1/4)^n$.

Em cada passo anterior à saída, a chance de continuar no edifício é $3/4$. Logo,

\[ \mathbb P_1(X_n=3)=1-\left(\frac34\right)^n: \]

esta é a probabilidade de já ter saído até o instante $n$. Além disso,

\[ P^n(1,1)-P^n(1,2)=\left(\frac14\right)^n. \]

A diferença entre as probabilidades de ocupar as duas salas diminui rapidamente: a cadeia perde a preferência pela sala em que começou. Como $a_n,b_n\to 0$, a probabilidade de estar no estado $3$ tende a $1$. Voltaremos a esta cadeia para contar quantas vezes a pessoa visita uma das salas antes de sair.

Se a distribuição inicial é o vetor-linha $\mu _0$, então a distribuição de $X_m$ é $\mu _0P^m$. Essa identidade será o ponto de partida para o estudo do comportamento de longo prazo.

2.2.1 Estimação de transições e retenção de usuários

Em aplicações, a matriz de transição costuma ser estimada a partir de observações. Suponha que registremos, ao fim de cada semana, o número de dias em que cada usuário acessou um serviço. Fixamos antes da análise os estados $A=$ ativo (quatro ou mais dias), $P=$ pouco ativo (um a três dias), $I=$ inativo (nenhum acesso) e $B=$ abandono (conta encerrada). Aqui o encerramento é definitivo; inatividade, por si só, permite retorno.

Exemplo 2.15 (Das observações à previsão de abandono)

Considere a seguinte tabela didática de contagens, obtida a partir de pares de semanas consecutivas de vários usuários acompanhados no mesmo período:

\[ \begin{array}{c|rrrr|r} N_{ij}& A& P& I& B& \text{total}\\ \hline A& 70& 20& 10& 0& 100\\ P& 10& 25& 10& 5& 50\\ I& 2& 4& 8& 6& 20 \end{array}. \]

Os estados $A$, $P$, $I$ e $B$ representam, respectivamente, usuários ativos, pouco ativos, inativos e que abandonaram o serviço. A entrada $N_{ij}$ conta quantas vezes foi observada uma transição do estado $i$ para o estado $j$:

\[ N_{ij} = \# \{ \text{transições observadas de }i\text{ para }j\} . \]

Um mesmo usuário pode contribuir com vários pares de semanas consecutivas. A última observação de um usuário não é ligada à primeira de outro, e uma semana sem observação não deve ser registrada como inatividade.

A tabela permite estimar diretamente as probabilidades de transição. Se

\[ N_i=\sum _k N_{ik} \]

é o número total de transições observadas a partir do estado $i$, tomamos

\[ \widehat p_{ij} = \frac{N_{ij}}{N_i}. \]

Essa estimativa é a frequência das transições de $i$ para $j$ entre todas as transições iniciadas em $i$.

Por exemplo, das $100$ transições observadas a partir de $A$, $70$ terminaram novamente em $A$, $20$ em $P$ e $10$ em $I$. Assim,

\[ \widehat p_{AA}=0{,}7, \qquad \widehat p_{AP}=0{,}2, \qquad \widehat p_{AI}=0{,}1. \]

Procedendo da mesma forma nas demais linhas, obtemos

\[ \widehat P= \begin{pmatrix} 0{,}7 & 0{,}2 & 0{,}1 & 0 \\ 0{,}2 & 0{,}5 & 0{,}2 & 0{,}1 \\ 0{,}1 & 0{,}2 & 0{,}4 & 0{,}3 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \]

As três primeiras linhas foram estimadas a partir das observações. A última é uma hipótese do modelo: depois do abandono não são coletadas novas transições, e consideramos $B$ um estado absorvente.

Suponha agora que um usuário esteja ativo no instante inicial. Sua distribuição inicial é $(1,0,0,0)$ e, portanto,

\[ \begin{aligned} (1,0,0,0)\widehat P^2 & =(0{,}54,0{,}26,0{,}15,0{,}05),\\ (1,0,0,0)\widehat P^3 & =(0{,}445,0{,}268,0{,}166,0{,}121). \end{aligned} \]

A última coordenada da primeira expressão pode também ser obtida diretamente. Para que um usuário inicialmente ativo tenha abandonado o serviço em até dois passos, ele deve seguir um dos caminhos

\[ A\to P\to B \qquad \text{ou}\qquad A\to I\to B. \]

Logo,

\[ 0{,}2\cdot 0{,}1+0{,}1\cdot 0{,}3 = 0{,}05. \]

Como $B$ é absorvente, a última coordenada de $(1,0,0,0)\widehat P^3$ representa a probabilidade estimada de abandono até o terceiro passo:

\[ 0{,}121. \]

O abandono de usuários ou clientes é frequentemente chamado de churn. A fração ou probabilidade de abandono em um período é a taxa de churn, usada em serviços por assinatura e plataformas digitais para acompanhar a permanência dos usuários. O modelo relaciona a atividade observada nas semanas anteriores à probabilidade de abandono nas semanas seguintes.

Há mais de uma maneira de definir retenção. Se consideramos retido todo usuário que ainda não atingiu $B$, então a retenção até o terceiro passo é

\[ 1-0{,}121=0{,}879. \]

Se quisermos medir apenas a probabilidade de o usuário estar ativo ou pouco ativo exatamente no terceiro passo, obtemos

\[ 0{,}445+0{,}268=0{,}713. \]

As duas quantidades respondem a perguntas diferentes: a primeira mede a permanência no serviço, enquanto a segunda mede a presença de alguma atividade no período considerado.

Se uma linha não contém transições observadas, sua distribuição não é identificada pelos dados: não podemos dividir por zero nem concluir que o estado seja absorvente. Uma suavização simples, para $d_i$ destinos admissíveis, substitui as proporções por

\[ \widetilde p_{ij}=\frac{N_{ij}+\eta }{N_i+d_i\eta },\qquad \eta \gt 0, \]

nesses destinos, conservando os zeros estruturais. Ela evita previsões nulas baseadas em poucas observações, mas acrescenta uma escolha ao modelo; já não é o estimador de máxima verossimilhança sem restrições adicionais.

A hipótese de Markov pode ser examinada comparando a atividade na semana seguinte entre usuários com o mesmo estado atual, mas estados anteriores distintos. Diferenças persistentes sugerem que o estado resume mal o histórico. Para examinar a homogeneidade, podem-se estimar matrizes em períodos separados e comparar suas previsões em semanas posteriores, inclusive a fração de contas encerradas. Uma campanha, uma mudança no produto ou diferenças entre coortes podem alterar as probabilidades de transição. Nesses casos, uma única matriz fixa deixa de representar bem a evolução dos usuários. Mesmo quando o ajuste é razoável, as probabilidades obtidas são previsões do modelo: não expressam a incerteza da estimação nem demonstram o efeito causal de uma intervenção voltada à retenção.

2.3 Classificação dos estados

Para compreender as trajetórias, surgem duas perguntas diferentes: quando a cadeia visita $y$ pela primeira vez e quando volta a $y$ depois do instante inicial. Se começamos em $y$, a entrada já ocorreu, mas o retorno ainda está por acontecer.

Definição 2.4

Tempos de entrada e de retorno Para um estado $y$, definimos o tempo de entrada por

\[ H_y=\min \{ n\geq 0:X_n=y\} . \]

Esse tempo admite o instante inicial. Na literatura, $H_y$ também aparece como tempo de atingimento (hitting time) e, em algumas convenções, como tempo de primeira passagem. Usaremos “tempo de entrada” para salientar nossa convenção. O tempo de primeiro retorno é

\[ T_{y}^{+}=\min \{ n\geq 1:X_n=y\} . \]

Adotamos $\min \varnothing =\infty $ e escrevemos

\[ \rho _{xy}=\mathbb {P}_x(T_{y}^{+}\lt \infty ). \]

Quando a cadeia começa em $y$, $T_y^+$ é o primeiro retorno: o instante inicial não conta. Quando ela começa em $x\ne y$, temos $T_y^+=H_y$. Assim, $\rho _{xy}$ é a probabilidade de atingir $y$ em tempo positivo e $\rho _{yy}$ é a probabilidade de retornar a $y$.

Definição 2.5

Tempo de parada Uma variável aleatória $T$ com valores em $\mathbb N_0\cup \{ \infty \} $ é um tempo de parada para a informação gerada pela cadeia se, para cada $n$, é possível decidir se $T\leq n$ observando somente $X_0,\ldots ,X_n$. Equivalentemente, como $T$ assume valores inteiros, podemos exigir que seja possível decidir se $T=n$ usando apenas a informação disponível até o instante $n$.

Retornos, entradas e saídas fornecem exemplos básicos de tempos de parada.

Exemplo 2.16 (Tempo de primeiro retorno)

Para $n\geq 1$,

\[ \{ T_{y}^{+}=n\} =\{ X_1\neq y,\ldots ,X_{n-1}\neq y,X_n=y\} . \]

Assim, no instante $n$ já sabemos se o primeiro retorno ocorreu exatamente ali, e $T_y^+$ é um tempo de parada.

Exemplo 2.17 (Entrada em um conjunto)

Se $A\subseteq S$, defina

\[ H_A=\min \{ n\geq 0:X_n\in A\} . \]

Para decidir se $H_A=n$, basta observar se $X_0,\ldots ,X_{n-1}$ estão fora de $A$ e $X_n\in A$. Logo $H_A$ é um tempo de parada.

Exemplo 2.18 (Saída de um conjunto)

Se $A\subseteq S$, o primeiro instante de saída,

\[ \tau _A=\min \{ n\geq 0:X_n\notin A\} , \]

também é um tempo de parada: no instante $n$ podemos verificar se a cadeia permaneceu em $A$ até $n-1$ e saiu de $A$ em $n$.

Exemplo 2.19 (Última visita a um estado)

Como a cadeia pode visitar $y$ infinitas vezes, o último tempo de visita pode não existir. Podemos formalizar essa ideia por

\[ L=\sup \{ n\geq 0:X_n=y\} , \]

permitindo $L=\infty $ e adotando uma convenção quando $y$ nunca é visitado. Em geral, $L$ não é um tempo de parada: para decidir no instante $n$ que $L=n$, seria necessário saber que a cadeia nunca mais visitará $y$, isto é, consultar o futuro.

A regra de parada depende apenas da informação já observada.

A propriedade forte de Markov diz que a cadeia pode ser reiniciada em um tempo de parada: dali em diante, importa o estado em que ela parou, e não o caminho usado para chegar até ele.

Teorema 2.5

Propriedade forte de Markov Se $T$ é um tempo de parada, então, no evento $\{ T\lt \infty \} $ e condicionalmente ao estado $X_T=y$, a trajetória futura $(X_{T+k})_{k\geq 0}$ tem a lei da cadeia iniciada em $y$ e é independente do caminho observado até $T$. Mais precisamente, se $A$ é um evento determinado pelo caminho observado até $T$, então, para $r\geq 1$,

\[ \begin{aligned} & \mathbb {P}(X_{T+1}=z_1,\ldots ,X_{T+r}=z_r \mid A,\, X_T=y,\, T\lt \infty )\\ & \qquad =\mathbb {P}_y(X_1=z_1,\ldots ,X_r=z_r) =p(y,z_1)\prod _{k=1}^{r-1}p(z_k,z_{k+1}), \end{aligned} \]

sempre que o condicionamento estiver definido.

Em particular, para $m\geq 0$,

\[ \mathbb {P}(X_{T+m}=j\mid X_T=i,\, T\lt \infty ) =\mathbb {P}_i(X_m=j), \]

sempre que o condicionamento estiver definido.

A hipótese de parada é essencial: uma escolha baseada em acontecimentos futuros poderia favorecer certas trajetórias e alterar a lei do processo reiniciado.

Demonstração ▼

Fixe $r\geq 1$, estados $z_1,\ldots ,z_r$ e um evento $A$ determinado pelo caminho observado até $T$, no sentido de que, para cada $n$, o evento $A\cap \{ T=n\} $ é determinado por $X_0,\ldots ,X_n$. O argumento tem três passos.

1. Fixar o valor da parada. No evento $\{ T=n\} $, a regra que determina a parada já pode ser decidida com a informação disponível até o instante $n$. Assim,

\[ A\cap \{ T=n,X_n=y\} \]

é um evento determinado por $X_0,\ldots ,X_n$. O instante aleatório foi, portanto, reduzido a um instante determinístico.

2. Aplicar a propriedade de Markov em $n$. Como no Corolário 2.2, podemos somar sobre as histórias completas compatíveis com $A\cap \{ T=n,X_n=y\} $. Em cada uma, a probabilidade do bloco futuro depende apenas do estado $X_n=y$. Logo,

\[ \begin{aligned} & \mathbb {P}(A,T=n,X_T=y,X_{T+1}=z_1,\ldots ,X_{T+r}=z_r)\\ & \quad =\mathbb {P}(A,T=n,X_T=y)\, p(y,z_1) \prod _{j=1}^{r-1}p(z_j,z_{j+1}). \end{aligned} \]

O segundo fator é exatamente a probabilidade de a cadeia iniciada em $y$ seguir o caminho $y,z_1,\ldots ,z_r$; em particular, ele não depende de $A$ nem de $n$.

3. Somar sobre os valores possíveis de $T$. Somando a identidade anterior em $n$ e usando que os eventos $\{ T=n\} $ são disjuntos, obtemos

\[ \begin{aligned} & \mathbb {P}(A,T\lt \infty ,X_T=y,X_{T+1}=z_1,\ldots ,X_{T+r}=z_r)\\ & \quad =\mathbb {P}(A,T\lt \infty ,X_T=y)\, p(y,z_1) \prod _{j=1}^{r-1}p(z_j,z_{j+1}). \end{aligned} \]

Quando a probabilidade condicionante é positiva, a divisão mostra que a lei do futuro, dado $X_T=y$, não depende do caminho observado até $T$. Como as probabilidades de blocos finitos determinam a lei da trajetória futura, obtemos a propriedade forte de Markov.

Exemplo 2.20 (Recomeçando em um tempo de entrada)

Considere a ruína do jogador nos estados $\{ 0,1,2,3\} $, com $0$ e $3$ absorventes e, nos estados interiores,

\[ p(i,i+1)=0{,}6, \qquad p(i,i-1)=0{,}4. \]

Parta de $1$ e seja $T=H_2$. O evento $\{ T\lt H_0\} $ diz que a cadeia alcançou $2$ antes da ruína. Como $T$ é um tempo de parada e $X_T=2$ nesse evento, a propriedade forte de Markov permite esquecer como e quando a cadeia chegou a $2$. Em particular,

\[ \mathbb P_1\bigl(X_{T+1}=3\mid T\lt H_0\bigr) =\mathbb {P}_2(X_1=3)=0{,}6. \]

Do mesmo modo,

\[ \mathbb P_1\bigl(X_{T+1}=1,\, X_{T+2}=2\mid T\lt H_0\bigr) =0{,}4\cdot 0{,}6=0{,}24. \]

O instante $T$ é aleatório, mas a cadeia passa a evoluir como uma cópia iniciada em $2$. Esse reinício permite decompor trajetórias em trechos delimitados por entradas e retornos.

Definição 2.6

Tempos de retorno sucessivos Definimos o instante do primeiro retorno por

\[ T_y^{(1)}=T_y^+, \]

e, recursivamente, o instante do $k$-ésimo retorno a $y$ por

\begin{equation} T_y^{(k)}=\min \{ n\gt T_y^{(k-1)}:X_n=y\} ,\qquad k\geq 2. \label{eq:retornos-sucessivos} \tag{2.3} \end{equation}

Assim, $T_y^{(k)}\lt \infty $ significa que a cadeia visita $y$ pelo menos $k$ vezes em tempos positivos.

Pela propriedade forte de Markov, após cada retorno a cadeia recomeça em $y$ sob a lei $\mathbb {P}_y$. Portanto,

\begin{equation} \mathbb {P}_y\bigl(T_y^{(k)}\lt \infty \bigr)=\rho _{yy}^{k}. \label{eq:prob-k-retornos} \tag{2.4} \end{equation}

Se $\rho _{yy}=1$, cada retorno $T_y^{(k)}$ é finito com probabilidade um; como isso vale para todo $k$, a cadeia retorna a $y$ infinitas vezes quase certamente. Se $\rho _{yy}\lt 1$, a probabilidade de ocorrerem pelo menos $k$ retornos é $\rho _{yy}^k$, que tende a zero. Nesse caso, o número de retornos é finito quase certamente.

Ilustração: Classificação dos estados

Figura 2.11 A entrada inclui o instante inicial; o retorno exige tempo positivo. Fora de $y$, temos $H_y=T_y^+$. No painel B, a entrada ocorre em zero e o primeiro retorno em três. Os círculos destacam as visitas a $y=1$; no painel A, a permanência do instante 4 para o 5 conta como novo retorno. As chaves medem intervalos em passos, e as linhas apenas guiam a leitura dos tempos discretos.

Definição 2.7

Estados recorrentes e transientes Um estado $y$ é recorrente se $\rho _{yy}=1$; nesse caso, a cadeia iniciada em $y$ retorna a $y$ infinitas vezes com probabilidade $1$. O estado é transiente se $\rho _{yy}\lt 1$; nesse caso, o número de visitas a $y$ é finito com probabilidade $1$.

Exemplo 2.21 (Um triângulo recorrente)

Considere a cadeia em $\{ 1,2,3\} $ que, a cada passo, salta para cada um dos outros dois vértices com probabilidade $1/2$:

\[ P= \begin{pmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{pmatrix}. \]

Figura 2.12 Grafo de transições do triângulo recorrente. De cada vértice, a cadeia salta para cada um dos outros dois com probabilidade $1/2$.

Partindo de $1$, depois do primeiro passo a cadeia está em $2$ ou $3$. Enquanto não retorna a $1$, em cada passo há probabilidade $1/2$ de continuar no outro vértice sem visitar $1$. Portanto, para $n\geq 1$,

\[ \mathbb P_1(T_1^+\gt n)=\left(\frac12\right)^{n-1}\longrightarrow 0. \]

Logo $\mathbb P_1(T_1^+\lt \infty )=1$, e o estado $1$ é recorrente. Por simetria, os três estados são recorrentes.

Assim, recorrência não significa “permanecer perto” de $y$: ela afirma apenas que, partindo de $y$, a cadeia retorna a $y$ com probabilidade um. A definição, por si só, não impõe que esse retorno seja rápido. Transiência significa que, partindo de $y$, há probabilidade positiva de nunca mais retornar.

A diferença aparece já na ruína do jogador: os estados absorventes são recorrentes, enquanto os estados internos são transientes.

Exemplo 2.22 (Ruína do jogador)

No jogo do Exemplo 2.2 com $N=5$, os estados 0 e 5 são absorventes e, portanto, recorrentes. Os estados internos são transientes. De fato, a partir de cada um deles existe um caminho de probabilidade positiva até uma barreira absorvente sem retornar ao ponto de partida:

\[ 1\to 0, \qquad 2\to 1\to 0, \qquad 3\to 4\to 5, \qquad 4\to 5. \]

Por exemplo,

\[ \mathbb {P}_2(T_2^+=\infty )\geq p(2,1)p(1,0)=0{,}36\gt 0. \]

O mesmo argumento vale para 1, 3 e 4. Assim, cada estado interno tem probabilidade positiva de nunca retornar.

A estrutura do grafo fornece critérios para identificar estados transientes e recorrentes.

Duas noções do grafo de transições serão usadas repetidamente. A primeira é orientada: pergunta se existe algum caminho possível de $x$ até $y$. A segunda exige caminhos nos dois sentidos.

Definição 2.8

Acessibilidade e comunicação Dizemos que $y$ é acessível a partir de $x$, e escrevemos $x\to y$, se

\[ \mathbb {P}_x(H_y\lt \infty )\gt 0. \]

Equivalentemente, $x\to y$ se e somente se $P^m(x,y)\gt 0$ para algum $m\geq 0$: atingir $y$ em tempo finito com probabilidade positiva equivale à existência de um caminho finito de $x$ até $y$ cujas transições tenham probabilidade positiva. Usaremos as duas formulações indistintamente.

Dizemos que $x$ e $y$ se comunicam, e escrevemos $x\leftrightarrow y$, se $x\to y$ e $y\to x$. Os conjuntos de estados que se comunicam entre si são chamados de classes de comunicação da cadeia.

Lema 2.6

Transitividade da acessibilidade Se $x\to y$ e $y\to z$, então $x\to z$.

Demonstração ▼

Existem $m,n$ tais que $P^{m}(x,y)\gt 0$ e $P^{n}(y,z)\gt 0$. Por Chapman–Kolmogorov,

\[ P^{m+n}(x,z)\geq P^{m}(x,y)P^{n}(y,z)\gt 0. \]

Como $H_x=0$ sob $\mathbb P_x$, temos $x\to x$ para todo estado $x$. A comunicação é simétrica por definição e, pelo lema, também é transitiva. Portanto, $\leftrightarrow $ é uma relação de equivalência: as classes de comunicação formam uma partição do espaço de estados.

Teorema 2.7

Um caminho sem retorno Se $\rho _{xy}\gt 0$ e $\rho _{yx}\lt 1$, então $x$ é transiente.

Demonstração ▼

Se $x=y$, a hipótese $\rho _{xx}\lt 1$ já afirma que $x$ é transiente. Suponha, portanto, $x\ne y$. Seja $K\geq 1$ o menor comprimento de um caminho de probabilidade positiva de $x$ até $y$. Escreva esse caminho como

\[ x=x_0,x_1,\ldots ,x_K=y, \qquad \prod _{i=0}^{K-1}p(x_i,x_{i+1})\gt 0. \]

Pela minimalidade de $K$, nenhum dos estados $x_1,\ldots ,x_{K-1}$ é igual a $x$: caso contrário, poderíamos eliminar o trecho entre duas visitas a $x$ e obter um caminho mais curto até $y$. Depois de chegar a $y$, há probabilidade $1-\rho _{yx}\gt 0$ de nunca atingir $x$. Logo,

\[ \mathbb {P}_x(T_x^+=\infty ) \geq \left(\prod _{i=0}^{K-1}p(x_i,x_{i+1})\right)(1-\rho _{yx})\gt 0, \]

e $x$ é transiente.

Uma consequência imediata é a seguinte.

Lema 2.8

Retorno a partir de estados alcançáveis Se $x$ é recorrente e $\rho _{xy}\gt 0$, então $\rho _{yx}=1$.

Demonstração ▼

Se $\rho _{y x}\lt 1$, então o Teorema 2.7 implicaria que $x$ é transiente, uma contradição.

Definição 2.9

Conjuntos fechados e irredutibilidade Um conjunto $A\subseteq S$ é fechado se não é possível sair dele:

\[ i\in A,\ j\notin A \quad \Longrightarrow \quad p(i,j)=0. \]

Um conjunto $B\subseteq S$ é irredutível se quaisquer dois estados de $B$ se comunicam. A cadeia é irredutível quando o próprio espaço $S$ é irredutível.

Um conjunto fechado é uma região da qual a cadeia não sai. A irredutibilidade significa que cada estado pode ser alcançado a partir de qualquer outro. Na definição de um subconjunto $B$, os caminhos são considerados na cadeia original; quando $B$ também é fechado, esses caminhos permanecem em $B$. Em uma cadeia finita, veremos que as classes fechadas são exatamente as regiões recorrentes da cadeia.

Exemplo 2.23 (Duas classes fechadas em quatro estados)

Considere a cadeia em $\{ 0,1,2,3\} $, com matriz

\[ P=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/2 & 0 \\ 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 1/3 & 2/3 \end{pmatrix}. \]

Figura não resolvida: figuras/classificacao-quatro-estados.tikz

Figura 2.13 O estado $1$ pode alcançar duas classes fechadas, $\{ 0\} $ e $\{ 2,3\} $, mas nenhuma delas permite retornar a $1$.

O estado $0$ é absorvente; os estados $2$ e $3$ se comunicam e formam uma classe fechada. Já o estado $1$ é transiente: depois de chegar a $0$, $2$ ou $3$, a cadeia não volta a $1$.

Podemos calcular a probabilidade $h$ de alcançar $0$ antes de entrar em $\{ 2,3\} $, partindo de $1$. No primeiro passo, a cadeia vai a $0$ com probabilidade $1/4$, fica em $1$ com probabilidade $1/4$ ou entra em $2$ com probabilidade $1/2$. Logo,

\[ h=\frac14+\frac14 h,\qquad \text{portanto}\qquad \boxed {h=\frac13}. \]

A chance de entrar primeiro na classe $\{ 2,3\} $ é $2/3$. A decomposição em classes reduziu o cálculo a uma equação de primeiro passo.

As classes fechadas podem ser reconhecidas diretamente no grafo de transições, como na cadeia a seguir.

Exemplo 2.24 (Uma cadeia de sete estados)

Considere a matriz de transição:

\[ \begin{array}{c|ccccccc}& \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} \\ \hline \mathbf{1} & 0{,}7 & 0 & 0 & 0 & 0{,}3 & 0 & 0 \\ \mathbf{2} & 0{,}1 & 0{,}2 & 0{,}3 & 0{,}4 & 0 & 0 & 0 \\ \mathbf{3} & 0 & 0 & 0{,}5 & 0{,}3 & 0{,}2 & 0 & 0 \\ \mathbf{4} & 0 & 0 & 0 & 0{,}5 & 0 & 0{,}5 & 0 \\ \mathbf{5} & 0{,}6 & 0 & 0 & 0 & 0{,}4 & 0 & 0 \\ \mathbf{6} & 0 & 0 & 0 & 0 & 0 & 0{,}2 & 0{,}8 \\ \mathbf{7} & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{array} \]

Desenhe uma seta de $i$ para $j$ quando $p(i,j)\gt 0$ e $i\ne j$. Os laços correspondentes a $p(i,i)\gt 0$ foram omitidos: eles não alteram quais estados são alcançáveis, embora sejam relevantes para a periodicidade.

A Figura 2.14 destaca as duas classes fechadas.

Figura 2.14 Grafo da cadeia de sete estados, com as classes fechadas destacadas. Os laços não estão desenhados.

O estado 2 alcança 1, mas 1 não alcança 2; pelo Teorema 2.7, o estado 2 é transiente. Do mesmo modo, 3 alcança 4, mas 4 não alcança 3, e portanto 3 é transiente.

As classes $\{ 1,5\} $ e $\{ 4,6,7\} $ são fechadas e irredutíveis. Há conjuntos fechados maiores — por exemplo, a união $\{ 1,4,5,6,7\} $ e o espaço inteiro —, mas são as classes fechadas que determinam os estados recorrentes. A recorrência dessas classes será demonstrada por meio de tentativas repetidas.

Antes de aplicar a estimativa de tentativas repetidas, recordemos a continuidade das probabilidades e uma regra de somação não negativa. Essas ferramentas também serão usadas na contagem de visitas e em espaços enumeráveis.

Uma série de números não negativos é o supremo de suas somas parciais; seu valor pode ser $+\infty $. Para uma família $a_{ij}\geq 0$, podemos somar por linhas ou por colunas:

\[ \sum _{i=1}^{\infty }\sum _{j=1}^{\infty }a_{ij} =\sup _{r,s\geq 1}\sum _{i=1}^{r}\sum _{j=1}^{s}a_{ij} =\sum _{j=1}^{\infty }\sum _{i=1}^{\infty }a_{ij}. \]

Proposição 2.9

Continuidade das probabilidades Se os eventos $A_m$ crescem, isto é,

\[ A_1\subseteq A_2\subseteq A_3\subseteq \cdots , \]

então

\[ \mathbb {P}\left(\bigcup _{m=1}^{\infty }A_m\right) =\lim _{m\to \infty }\mathbb {P}(A_m). \]

Se os eventos $A_m$ decrescem, isto é,

\[ A_1\supseteq A_2\supseteq A_3\supseteq \cdots , \]

então

\[ \mathbb {P}\left(\bigcap _{m=1}^{\infty }A_m\right) =\lim _{m\to \infty }\mathbb {P}(A_m). \]

Em particular, se $T$ é um tempo de parada, então

\[ \mathbb {P}(T\lt \infty ) =\lim _{n\to \infty }\mathbb {P}(T\leq n), \qquad \mathbb {P}(T=\infty ) =\lim _{n\to \infty }\mathbb {P}(T\gt n). \]

Assim, se $T\lt \infty $ quase certamente, então $\mathbb {P}(T\gt n)\to 0$.

Demonstração ▼

Para verificar a afirmação sobre eventos crescentes, escreva $D_1=A_1$ e $D_m=A_m\setminus A_{m-1}$ para $m\geq 2$. Esses eventos são disjuntos, e a aditividade enumerável dá

\[ \mathbb {P}\left(\bigcup _{m=1}^{\infty }A_m\right) =\sum _{m=1}^{\infty }\mathbb {P}(D_m) =\lim _{r\to \infty }\sum _{m=1}^{r}\mathbb {P}(D_m) =\lim _{r\to \infty }\mathbb {P}(A_r). \]

Aplicando essa identidade aos complementares, obtemos a continuidade para eventos decrescentes. Para um tempo de parada $T$, os eventos $\{ T\leq n\} $ crescem para $\{ T\lt \infty \} $, enquanto $\{ T\gt n\} $ decrescem para $\{ T=\infty \} $. As duas identidades finais seguem das duas formas de continuidade.

Lema 2.10

Tentativas repetidas Seja $D\subseteq S$ um conjunto fechado. Suponha que existam $k\geq 1$ e $\alpha \gt 0$ tais que

\[ \mathbb {P}_x(T_{y}^{+}\leq k)\geq \alpha \]

para todo $x\in D$. Então, para todo $x\in D$ e $n\geq 0$,

\[ \mathbb {P}_{x}\left(T_{y}^{+}\gt n k\right) \leq (1-\alpha )^{n}. \]

Em particular, $\mathbb {P}_x(T_{y}^{+}\lt \infty )=1$ para todo $x\in D$.

Demonstração ▼

Fixe $x\in D$ e, para $n\geq 0$, escreva

\[ A_n=\{ T_y^+\gt nk\} . \]

O evento $A_n$ significa que a cadeia chegou ao instante $nk$ sem visitar $y$ em tempo positivo. Como $D$ é fechado e a cadeia começou em $D$, no evento $A_n$ temos necessariamente

\[ X_{nk}\in D. \]

Reiniciamos a análise no instante $nk$. Fixe $z\in D$ e suponha que o condicionamento abaixo esteja definido. O instante determinístico $nk$ é um tempo de parada, e $A_n$ é determinado pelo caminho observado até esse instante. Pela propriedade forte de Markov,

\[ \mathbb P_x\bigl(A_{n+1}\mid A_n,\, X_{nk}=z\bigr) =\mathbb P_z(T_y^+\gt k). \]

Sabendo que a cadeia sobreviveu até $nk$ e que está em $z$, a probabilidade de evitar $y$ durante os próximos $k$ passos é a mesma que para uma nova cadeia iniciada em $z$. O caminho percorrido antes de $nk$ não entra mais no cálculo.

Pela hipótese do lema,

\[ \mathbb P_z(T_y^+\leq k)\geq \alpha \qquad \text{para todo }z\in D. \]

Tomando complementares,

\[ \mathbb P_z(T_y^+\gt k)\leq 1-\alpha \qquad \text{para todo }z\in D. \]

Portanto, qualquer que seja o estado ocupado no instante $nk$, a probabilidade de sobreviver ao próximo bloco de $k$ passos é no máximo $1-\alpha $.

Se $\mathbb P_x(A_n)=0$, então também $\mathbb P_x(A_{n+1})=0$ e a desigualdade que queremos é imediata. Suponha, pois, $\mathbb P_x(A_n)\gt 0$. Condicionando pelos possíveis valores de $X_{nk}$ no evento $A_n$, obtemos

\[ \begin{aligned} \mathbb P_x(A_{n+1}\mid A_n) & = \sum _{z\in D} \mathbb P_x(A_{n+1}\mid A_n,\, X_{nk}=z)\, \mathbb P_x(X_{nk}=z\mid A_n)\\ & \leq (1-\alpha ) \sum _{z\in D}\mathbb P_x(X_{nk}=z\mid A_n)\\ & =1-\alpha . \end{aligned} \]

Assim, como $A_{n+1}\subseteq A_n$,

\[ \begin{aligned} \mathbb P_x(T_y^+\gt (n+1)k) & =\mathbb P_x(A_{n+1})\\ & =\mathbb P_x(A_{n+1}\mid A_n)\, \mathbb P_x(A_n)\\ & \leq (1-\alpha )\mathbb P_x(T_y^+\gt nk). \end{aligned} \]

Iterando essa desigualdade e usando $\mathbb P_x(T_y^+\gt 0)\leq 1$, concluímos que

\[ \mathbb P_x(T_y^+\gt nk)\leq (1-\alpha )^n, \qquad n\geq 0. \]

Por fim, os eventos $\{ T_y^+\gt nk\} $ decrescem para $\{ T_y^+=\infty \} $. Pela continuidade das probabilidades (pela Proposição 2.9),

\[ \mathbb P_x(T_y^+=\infty ) =\lim _{n\to \infty }\mathbb P_x(T_y^+\gt nk) \leq \lim _{n\to \infty }(1-\alpha )^n =0. \]

Logo $\mathbb P_x(T_y^+\lt \infty )=1$.

Ilustração: Classificação dos estados

Figura 2.15 A ideia das tentativas repetidas. No evento $A_n$, a cadeia chega ao instante $nk$ sem visitar $y$ e ocupa algum estado $z\in D$. Pela propriedade forte de Markov, a análise recomeça em $z$; a hipótese garante probabilidade pelo menos $\alpha $ de visitar $y$ nos próximos $k$ passos e, portanto, probabilidade no máximo $1-\alpha $ de sobreviver ao bloco seguinte.

Dentro de uma classe finita sem saída, há sempre uma nova oportunidade de voltar a qualquer estado fixado. A finitude permite tornar essa oportunidade uniforme, independentemente do ponto de partida.

Teorema 2.11

Classes fechadas finitas Se $C$ é um conjunto finito, fechado e irredutível, todos os seus estados são recorrentes.

Demonstração ▼

Fixe $y\in C$. Para cada $x\in C$, escolha um caminho de probabilidade positiva que, partindo de $x$, visite $y$ em tempo positivo. Quando $x\ne y$, isso é possível pela irredutibilidade. Para $x=y$, precisamos de um caminho de retorno: se $C=\{ y\} $, o fato de $C$ ser fechado implica $p(y,y)=1$; se $C$ tem mais de um estado, podemos ir de $y$ a outro estado da classe e depois voltar a $y$.

Denote por $\ell _x\geq 1$ o comprimento do caminho escolhido e por $q_x\gt 0$ a probabilidade de segui-lo. Como $C$ é finito,

\[ k=\max _{x\in C}\ell _x\lt \infty , \qquad \alpha =\min _{x\in C}q_x\gt 0. \]

Consequentemente,

\[ \mathbb P_x(T_y^+\leq k)\geq \alpha \qquad \text{para todo }x\in C. \]

Como $C$ é fechado, o Lema 2.10 se aplica e dá

\[ \mathbb P_y(T_y^+\lt \infty )=1. \]

Logo $y$ é recorrente. Como $y$ foi arbitrário, todos os estados de $C$ são recorrentes.

No exemplo de sete estados, isso mostra imediatamente que todos os estados das classes $\{ 1,5\} $ e $\{ 4,6,7\} $ são recorrentes.

Em uma cadeia finita, as classes fechadas são precisamente as classes recorrentes. Isso permite decompor o espaço de estados.

Teorema 2.12

Decomposição de uma cadeia finita Se $S$ é finito e não vazio, ele se decompõe na união disjunta

\[ S=\mathcal T\cup R_1\cup \cdots \cup R_k, \]

onde $\mathcal T$ é o conjunto dos estados transientes e $R_1,\ldots ,R_k$ são as classes de comunicação fechadas. Todos os estados de cada $R_i$ são recorrentes.

Demonstração ▼

Contraia cada classe de comunicação a um único vértice e mantenha uma seta entre duas classes distintas quando existe uma transição de probabilidade positiva da primeira para a segunda. O grafo resultante é finito e não possui circuitos dirigidos: se várias classes formassem um circuito, seus estados se comunicariam e pertenceriam à mesma classe.

As classes sem seta de saída são exatamente as classes fechadas. Como o grafo é finito e não possui circuitos dirigidos, seguindo sucessivamente as setas a partir de qualquer classe chegamos, após um número finito de passos, a uma classe da qual não sai nenhuma seta. Portanto, existe pelo menos uma classe fechada. Pelo Teorema 2.11, todos os estados dessas classes são recorrentes.

Considere agora uma classe $C$ que não é fechada. Seguindo setas no grafo das classes, chegamos depois de um número finito de passos a alguma classe fechada $R$. Assim, para $x\in C$ e algum $y\in R$, temos $x\to y$. Por outro lado, $y\not\to x$: caso contrário, $x$ e $y$ se comunicariam e pertenceriam à mesma classe. Pelo Teorema 2.7, $x$ é transiente. Como $x$ era arbitrário em $C$, toda classe não fechada é formada por estados transientes.

As classes de comunicação particionam $S$. Reunindo as classes não fechadas em $\mathcal T$ e enumerando as classes fechadas como $R_1,\ldots ,R_k$, obtemos a decomposição afirmada.

Figura não resolvida: figuras/classes-comunicacao.tikz

Figura 2.16 Grafo das classes de comunicação após contrair cada classe a um vértice. As classes fechadas não têm setas de saída.

2.4 Contagem de visitas e critério de recorrência

A probabilidade de retorno informa se a cadeia volta a um estado; agora queremos contar quantas vezes ela volta. A fórmula da cauda liga essa contagem à esperança.

Lema 2.13

Fórmula da cauda Se $Z$ assume valores em $\mathbb N_0\cup \{ \infty \} $, então

\[ E Z=\sum _{k=1}^{\infty }\mathbb {P}(Z\geq k) =\sum _{n=0}^{\infty }\mathbb {P}(Z\gt n), \]

com a possibilidade de ambos os lados serem infinitos.

Demonstração ▼

Se $\mathbb {P}(Z=+\infty )\gt 0$, a esperança é infinita e cada termo da primeira série é pelo menos essa probabilidade. A identidade vale nesse caso.

Suponha agora $\mathbb {P}(Z=+\infty )=0$ e escreva $p_j=\mathbb {P}(Z=j)$. Pela definição de esperança de uma variável discreta, $E Z=\sum _{j\geq 1}j p_j$. Para cada $M$, uma soma finita dá

\[ \sum _{j=1}^{M}j p_j =\sum _{k=1}^{M}\sum _{j=k}^{M}p_j \leq \sum _{k=1}^{\infty }\mathbb {P}(Z\geq k). \]

Tomando o supremo em $M$, obtemos uma das desigualdades. Na direção oposta, para cada $K$, particionamos os resultados em $Z=1,\ldots ,K-1$ e $Z\geq K$:

\[ \begin{aligned} \sum _{k=1}^{K}\mathbb {P}(Z\geq k) & =\sum _{j=1}^{K-1}j p_j+K\mathbb {P}(Z\geq K)\\ & =\sum _{j=1}^{K-1}j p_j+K\sum _{j=K}^{\infty }p_j \leq \sum _{j=1}^{\infty }j p_j=E Z. \end{aligned} \]

Tomar o supremo em $K$ fornece a desigualdade restante. A segunda série do enunciado é a primeira com o índice deslocado, pois $Z$ assume valores inteiros.

A versão truncada é a identidade finita

\[ Z\wedge M=\sum _{k=1}^{M}\mathbf1_{\{ Z\geq k\} }, \qquad E(Z\wedge M)=\sum _{k=1}^{M}\mathbb {P}(Z\geq k). \]

Cada nível alcançado por $Z$ contribui uma unidade para a esperança truncada.

Retomemos agora os tempos de retorno sucessivos definidos em (2.3). Pela propriedade forte de Markov, para $x,y\in S$ e $k\geq 1$,

\begin{equation} \mathbb {P}_{x}\left(T_{y}^{(k)}\lt \infty \right) =\rho _{x y}\rho _{y y}^{k-1}. \label{eq:retorno-k-partindo-x} \tag{2.5} \end{equation}

Seja $N(y)$ o número de visitas a $y$ nos instantes $n\geq 1$. A identidade acima permite calcular $E_xN(y)$.

Lema 2.14

Número esperado de visitas Vale

\[ E_xN(y)= \begin{cases} 0, & \rho _{xy}=0,\\[1mm] \dfrac {\rho _{xy}}{1-\rho _{yy}}, & \rho _{xy}\gt 0,\ \rho _{yy}\lt 1,\\[2mm] +\infty , & \rho _{xy}\gt 0,\ \rho _{yy}=1. \end{cases} \]

Se $y$ não pode ser alcançado, não há visitas a contar, ainda que $y$ seja recorrente quando a cadeia começa nele. Separar os casos evita o quociente indeterminado $0/0$.

Demonstração ▼

Aplicaremos a fórmula da cauda do Lema 2.13 à contagem $N(y)$, que pode ser infinita. Para cada $k\geq 1$,

\[ \{ N(y)\geq k\} =\{ T_y^{(k)}\lt \infty \} . \]

Usando (2.5), obtemos

\[ E_xN(y)=\sum _{k=1}^{\infty }\mathbb {P}_x(T_y^{(k)}\lt \infty ). \]

Se $\rho _{xy}=0$, cada parcela é zero. Se $\rho _{xy}\gt 0$ e $\rho _{yy}\lt 1$, então

\[ \begin{aligned} E_xN(y) & =\sum _{k=1}^{\infty }\rho _{xy}\rho _{yy}^{k-1}\\ & =\rho _{xy}\sum _{j=0}^{\infty }\rho _{yy}^{j}\\ & =\frac{\rho _{xy}}{1-\rho _{yy}}, \end{aligned} \]

pela soma da série geométrica. Se $\rho _{xy}\gt 0$ e $\rho _{yy}=1$, todas as parcelas valem $\rho _{xy}\gt 0$ e, portanto, a soma é infinita.

Exemplo 2.25 (Duas salas e uma saída: contando visitas)

Retomemos a cadeia do Exemplo 2.14. Quantas vezes, em média, a pessoa visita a sala $2$ quando começa na sala $1$? Primeiro, precisamos da probabilidade $\rho _{12}$ de alcançar a sala $2$. Condicionando pelo primeiro passo, ela pode ir diretamente à sala $2$ ou permanecer na sala $1$ e tentar novamente:

\[ \rho _{12}=\frac14+\frac12\rho _{12}, \qquad \text{portanto}\qquad \rho _{12}=\frac12. \]

Para retornar à sala $2$ começando nela, a pessoa pode permanecer nessa sala no primeiro passo ou ir à sala $1$ e depois alcançar a sala $2$. Assim,

\[ \rho _{22}=\frac12+\frac14\rho _{12}=\frac58. \]

Aplicando o lema,

\[ E_1N(2)=\frac{\rho _{12}}{1-\rho _{22}} =\frac{1/2}{1-5/8}=\boxed {\frac43}. \]

Embora a probabilidade de chegar à sala $2$ seja somente $1/2$, a esperança é maior que $1$: quem chega pode visitar a sala várias vezes antes de sair. De fato, entre as trajetórias que chegam à sala $2$, o número esperado de visitas é $(4/3)/(1/2)=8/3$.

Lema 2.15

Visitas e probabilidades de transição O número esperado de visitas também satisfaz

\[ E_xN(y)=\sum _{n=1}^{\infty }P^{n}(x,y). \]

Demonstração ▼

Conte primeiro as visitas até o instante $m$:

\[ N_m(y)=\sum _{n=1}^{m}\mathbf1_{\{ X_n=y\} }, \qquad E_xN_m(y)=\sum _{n=1}^{m}P^n(x,y), \]

pela linearidade da esperança de uma soma finita. Para cada $k\geq 1$, os eventos $\{ N_m(y)\geq k\} $ crescem para $\{ N(y)\geq k\} $. Pela continuidade das probabilidades, $\mathbb P_x(N(y)\geq k)=\sup _m\mathbb P_x(N_m(y)\geq k)$. Essas probabilidades são não negativas e crescem com $m$; por isso, os supremos que definem as somas podem ser tomados em qualquer ordem:

\[ \begin{aligned} E_xN(y) & =\sum _{k\geq 1}\sup _m\mathbb P_x(N_m(y)\geq k)\\ & =\sup _m\sum _{k\geq 1}\mathbb P_x(N_m(y)\geq k) =\sup _m E_xN_m(y)\\ & =\sum _{n=1}^{\infty }P^n(x,y). \end{aligned} \]

Usamos apenas a fórmula da cauda e o princípio de que uma soma de termos não negativos é o supremo de suas somas finitas. O argumento também vale quando a esperança é infinita.

Exemplo 2.26 (Duas salas e uma saída: somando as probabilidades)

Podemos conferir o resultado do Exemplo 2.25 de outra maneira. A diagonalização feita no Exemplo 2.14 nos deu, para $n\geq 1$,

\[ P^n(1,2) =\frac12\left[\left(\frac34\right)^n -\left(\frac14\right)^n\right]. \]

Pelo lema anterior e pela soma das séries geométricas,

\[ \begin{aligned} E_1N(2) & =\sum _{n=1}^{\infty }P^n(1,2)\\ & =\frac12\left[ \sum _{n=1}^{\infty }\left(\frac34\right)^n -\sum _{n=1}^{\infty }\left(\frac14\right)^n\right]\\ & =\frac12\left(3-\frac13\right)=\boxed {\frac43}. \end{aligned} \]

Obtivemos o mesmo número de duas formas: antes contamos as visitas pela chegada inicial e pelos retornos sucessivos; agora somamos, instante a instante, as probabilidades de ocupar a sala $2$.

Teorema 2.16

Critério de recorrência Um estado $y$ é recorrente se, e somente se,

\[ \sum _{n=1}^{\infty }P^{n}(y,y)=\infty . \]

Demonstração ▼

Pelos Lemas 2.14 e 2.15, a série é $E_yN(y)$, que é infinita exatamente quando $\rho _{yy}=1$.

Lema 2.17

Recorrência em uma classe Se $x$ é recorrente e $x\to y$, então $y$ é recorrente.

Demonstração ▼

Se $x=y$, nada há a provar. Caso contrário, o Lema 2.8 garante $y\to x$. Escolha $j,\ell \geq 1$ tais que $P^{j}(y,x)\gt 0$ e $P^{\ell }(x,y)\gt 0$. Por Chapman–Kolmogorov,

\[ P^{j+n+\ell }(y,y) \geq P^{j}(y,x)P^n(x,x)P^{\ell }(x,y) \qquad (n\geq 0). \]

Somando em $n$,

\[ \sum _{n=0}^{\infty }P^{j+n+\ell }(y,y) \geq P^{j}(y,x) \left(\sum _{n=0}^{\infty }P^{n}(x,x)\right) P^{\ell }(x,y). \]

Como $x$ é recorrente, o critério anterior mostra que $\sum _{n\geq 1}P^n(x,x)=\infty $; acrescentar o termo $P^0(x,x)=1$ não altera a divergência. Logo a série no lado direito é infinita. Portanto a série de retornos a $y$ também diverge, e o mesmo critério implica que $y$ é recorrente.

A recorrência informa se voltamos a um estado; a periodicidade descreve em quais instantes esses retornos são possíveis.

2.5 Periodicidade dos estados

Definição 2.10

Período e aperiodicidade Para um estado $x$, considere o conjunto dos possíveis tempos de retorno

\[ I_x=\{ n\geq 1:P^{n}(x,x)\gt 0\} . \]

Quando $I_x$ é não vazio, o período de $x$ é o máximo divisor comum de seus elementos. Se $I_x=\varnothing $, não há retorno possível e não atribuímos período ao estado. O estado é aperiódico quando seu período é $1$.

O período não mede quanto tempo a cadeia costuma levar para voltar. Ele detecta um ritmo obrigatório: período $d\gt 1$ significa que todo retorno só pode ocorrer em tempos múltiplos de $d$.

Exemplo 2.27 (Periodicidade na cadeia de Ehrenfest)

Na cadeia de Ehrenfest, uma bola muda de urna a cada passo. Portanto, o número de bolas na urna esquerda troca de paridade em todos os instantes: de um estado par a cadeia vai para um estado ímpar, e vice-versa.

Consequentemente, um retorno ao estado inicial só pode ocorrer após um número par de passos. Por outro lado, de qualquer estado há probabilidade positiva de mover uma bola e devolvê-la no passo seguinte. Assim,

\[ P^{2}(x,x)\gt 0 \qquad \text{e}\qquad P^{2m+1}(x,x)=0, \]

para todo estado $x$. Como $2$ é um tempo possível de retorno e todos os tempos de retorno são pares, o período é $2$.

Exemplo 2.28 (Triângulo e quadrado)

Considere a cadeia da Figura 2.17. A partir de 0, escolhemos com probabilidade $1/2$ um circuito de comprimento 3 ou um circuito de comprimento 4; depois de escolhido o circuito, o percurso de volta a 0 é determinístico.

Figura 2.17 Dois circuitos de comprimentos três e quatro. A cadeia pode voltar a zero em tempos de máximo divisor comum um.

Temos $P^{3}(0,0)\gt 0$ e $P^{4}(0,0)\gt 0$. Como o máximo divisor comum de 3 e 4 é 1, o estado 0 é aperiódico, mesmo que $p(0,0)=0$. O exemplo mostra que a existência de uma permanência é suficiente, mas não necessária, para aperiodicidade.

Lema 2.18

Períodos em uma classe Estados que se comunicam e admitem retorno em tempo positivo têm o mesmo período.

Demonstração ▼

Escolha $k,m$ tais que $P^{k}(x,y)\gt 0$ e $P^{m}(y,x)\gt 0$. Então

\[ P^{k+m}(x,x) \geq P^{k}(x,y)P^{m}(y,x)\gt 0. \]

Logo, o período de $x$ divide $k+m$. Para qualquer $\ell \in I_y$,

\[ P^{k+\ell +m}(x,x) \geq P^{k}(x,y)P^{\ell }(y,y)P^{m}(y,x)\gt 0, \]

de modo que $k+\ell +m\in I_x$. Subtraindo $k+m$, concluímos que o período de $x$ divide todo $\ell \in I_y$; portanto, ele divide o período de $y$. Trocando $x$ e $y$, obtemos a divisibilidade oposta. Os dois períodos são iguais.

Lema 2.19

Permanência e aperiodicidade Se $p(x,x)\gt 0$, então $x$ tem período $1$.

Demonstração ▼

Nesse caso, $1\in I_x$, e o máximo divisor comum de um conjunto que contém $1$ só pode ser $1$.

No canal de comunicação do Exemplo 2.7, se $0\lt a,b\lt 1$, ambos os estados possuem permanência positiva; portanto, a cadeia é aperiódica. Em uma cadeia irredutível, basta encontrar um único estado aperiódico, pois o Lema 2.18 transfere o período para toda a classe.

Voltaremos à periodicidade no próximo capítulo, ao investigar o comportamento das potências $P^n$.

A classificação descreve a possibilidade de retorno. Em problemas de saída, interessa identificar por qual parte da fronteira a cadeia deixa uma região.

2.6 Distribuições de saída

Se $A\subseteq S$, definimos o tempo de entrada em $A$ por

\[ H_A=\min \{ n\geq 0:X_n\in A\} . \]

Se $A$ e $B$ são disjuntos, escrevemos $C=S\setminus (A\cup B)$. Partindo de $x\in C$, a cadeia pode visitar vários estados de $C$ antes de entrar em $A$ ou em $B$. Queremos saber qual conjunto ela atinge primeiro, e não onde estará em um instante fixo.

Figura não resolvida: figuras/distribuicoes-saida-esquema.tikz

Figura 2.18 Partindo de $x\in C$, a cadeia pode circular entre os estados interiores antes de sair por $A$ ou por $B$. As setas coloridas indicam as duas possibilidades de primeira saída; não supomos que $A$ e $B$ sejam absorventes.

A probabilidade de atingir $A$ primeiro é $h(x)=\mathbb P_x(H_A\lt H_B)$. Ela vale $1$ em $A$ e $0$ em $B$; dentro de $C$, o valor é determinado pela análise do primeiro passo. O próximo teorema torna essas condições precisas.

Teorema 2.20

Problema de Dirichlet para cadeias de Markov Sejam $A,B\subseteq S$ disjuntos e suponha que $C=S\setminus (A\cup B)$ seja finito. Admita que $H_A\wedge H_B\lt \infty $ quase certamente a partir de todo estado de $C$. Então

\[ h(x)=\mathbb {P}_x(H_A\lt H_B) \]

é a única função que satisfaz

\[ \begin{cases} h(x)=1, & x\in A,\\ h(x)=0, & x\in B,\\ h(x)=\displaystyle \sum _y p(x,y)h(y), & x\in C. \end{cases} \]

Demonstração ▼

As condições na fronteira são imediatas: se a cadeia começa em $A$, já atingiu $A$ antes de $B$; se começa em $B$, ocorre o contrário. Para $x\in C$, condicionando pelo primeiro passo e usando a propriedade de Markov,

\[ \mathbb {P}_x(H_A\lt H_B) =\sum _y p(x,y)\mathbb {P}_y(H_A\lt H_B). \]

Logo, $h$ satisfaz as equações do enunciado.

Para a unicidade, seja $u$ outra solução e ponha $T=H_A\wedge H_B$. Mostraremos primeiro que, para todo $n\geq 0$,

\[ u(x)=E_x\bigl[u(X_{T\wedge n})\bigr]. \]

Para $n=0$, isso é simplesmente $u(x)=u(X_0)$. Para passar de $n$ a $n+1$, distinguimos dois casos. Se $T\leq n$, a cadeia já chegou à fronteira e o valor observado em $T\wedge (n+1)$ é o mesmo observado em $T\wedge n$. Se $T\gt n$, então $X_n\in C$ e podemos usar a equação harmônica $u(X_n)=\sum _y p(X_n,y)u(y)$. Essa passagem pode ser justificada sem introduzir esperança condicional em relação a toda a trajetória. Para $z\in C$ e qualquer $y$, o evento $\{ T\gt n,X_n=z\} $ depende apenas dos estados até o instante $n$, de modo que a propriedade de Markov fornece

\[ \mathbb P_x(T\gt n,X_n=z,X_{n+1}=y) =\mathbb P_x(T\gt n,X_n=z)\, p(z,y). \]

Somando sobre $z$ e $y$, e separando o evento $\{ T\leq n\} $, obtemos

\[ \begin{aligned} E_x\bigl[u(X_{T\wedge (n+1)})\bigr] & =E_x\bigl[\mathbf1_{\{ T\leq n\} }u(X_T)\bigr]\\ & \quad + E_x\left[\mathbf1_{\{ T\gt n\} }\sum _y p(X_n,y)u(y)\right]\\ & =E_x\bigl[u(X_{T\wedge n})\bigr]. \end{aligned} \]

A identidade segue, portanto, por indução.

Como $u=1$ em $A$, $u=0$ em $B$ e $C$ é finito, existe $M\lt \infty $ tal que $|u(z)|\leq M$ em todos os estados. Em $\{ T\leq n\} $ temos $u(X_{T\wedge n})=u(X_T)$; em $\{ T\gt n\} $, a diferença entre esses valores é no máximo $2M$. Portanto,

\[ \left|E_x[u(X_{T\wedge n})]-E_x[u(X_T)]\right| \leq 2M\, \mathbb {P}_x(T\gt n)\longrightarrow 0. \]

A última passagem usa $T\lt \infty $ quase certamente e a continuidade das probabilidades para eventos decrescentes. Como $X_T$ pertence a $A\cup B$,

\[ u(x)=E_x[u(X_T)] =\mathbb P_x(X_T\in A) =\mathbb P_x(H_A\lt H_B)=h(x). \]

Assim, a solução é única.

O adjetivo harmônica descreve a terceira equação: em cada estado interior, o valor de $h$ é a média dos valores depois de um passo. Se $R$ é a submatriz de $P$ com linhas e colunas em $C$ e

\[ v(x)=\sum _{a\in A}p(x,a), \]

a contribuição da fronteira é exatamente $v(x)$, pois $h=1$ em $A$ e $h=0$ em $B$. Assim, as equações interiores podem ser escritas como

\[ (I-R)h_C=v. \]

Exemplo 2.29 (Quatro estados e duas barreiras absorventes)

Um jogador começa com $2$ unidades. Em cada rodada, ganha ou perde uma unidade com probabilidades iguais e para ao atingir $0$ (ruína) ou $3$ (meta). A matriz da cadeia, na ordem $(0,1,2,3)$, é

\[ P=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \]

Figura não resolvida: figuras/passeio-quatro-estados.tikz

Figura 2.19 O passeio termina ao chegar a $0$ ou $3$. Em cada estado interior, as duas direções têm probabilidade $1/2$.

Escreva $u_i=\mathbb P_i(H_3\lt H_0)$, a probabilidade de alcançar a meta partindo de $i$ unidades. As condições na fronteira são $u_0=0$ e $u_3=1$. Condicionando pelo primeiro passo nos estados interiores,

\[ u_1=\frac12u_2,\qquad u_2=\frac12u_1+\frac12. \]

Substituindo a primeira equação na segunda,

\[ u_2=\frac14u_2+\frac12 \quad \Longrightarrow \quad \boxed {u_2=\frac23},\qquad u_1=\frac13. \]

Portanto, a probabilidade de alcançar a meta antes da ruína é precisamente $2/3$, e não $1$. Voltaremos a essa cadeia para calcular a duração média do jogo.

Exemplo 2.30 (O rato, o gato e o queijo)

Um rato percorre cinco salas ligadas pelas passagens indicadas na figura. A cada passo ele escolhe uniformemente uma das salas vizinhas. Na sala $3$ está um gato; na sala $5$, um pedaço de queijo. O passeio termina assim que o rato entra em uma dessas duas salas. Se ele começa na sala $1$, qual é a probabilidade de encontrar o queijo antes do gato?

Figura não resolvida: figuras/rato-gato-queijo.tikz

Figura 2.20 O rato começa na sala $1$. As arestas são passagens possíveis; as salas $3$ (gato) e $5$ (queijo) encerram o passeio. A sala $4$ tem três vizinhas, enquanto $1$ e $2$ têm duas.

Escreva $u(i)=\mathbb P_i(H_5\lt H_3)$. As condições de fronteira são $u(3)=0$ e $u(5)=1$. Pelas passagens desenhadas, a análise do primeiro passo fornece

\[ \begin{aligned} u(1)& =\frac12u(2)+\frac12u(4),\\ u(2)& =\frac12u(1)+\frac12u(3)=\frac12u(1),\\ u(4)& =\frac13\bigl(u(1)+u(3)+u(5)\bigr) =\frac{u(1)+1}{3}. \end{aligned} \]

Substituindo as duas últimas expressões na primeira,

\[ u(1)=\frac14u(1)+\frac{u(1)+1}{6} =\frac5{12}u(1)+\frac16, \]

e portanto

\[ \boxed {\mathbb P_1(H_5\lt H_3)=u(1)=\frac27}. \]

Embora existam duas salas de destino, a chance de sucesso não é $1/2$: ela depende das passagens entre as salas. O desenho permite montar as equações sem escrever a matriz de transição completa.

Este problema é uma adaptação de um exemplo de Brémaud (2020).

Exemplo 2.31 (Um saldo mensal: atingir zero em quatro meses)

Uma pessoa acompanha um saldo mensal limitado aos valores $0,1,2,3$. A cada mês recebe uma unidade e tem uma despesa $D_n$ independente dos meses anteriores, com

\[ \mathbb P(D_n=0)=\frac14,\qquad \mathbb P(D_n=1)=\frac12,\qquad \mathbb P(D_n=2)=\frac14. \]

O saldo do fim do mês é limitado inferiormente por $0$ e superiormente por $3$:

\[ X_{n+1}=\min \{ 3,\max \{ 0,X_n+1-D_{n+1}\} \} . \]

Figura não resolvida: figuras/saldo-mensal.tikz

Figura 2.21 Em cada mês, um recebimento fixo é seguido de uma despesa aleatória. O saldo é limitado aos quatro estados indicados.

Começando com saldo $2$, qual é a probabilidade de atingir $0$ em algum dos próximos quatro meses? Não basta calcular $\mathbb P_2(X_4=0)$: a pessoa pode chegar a zero e depois voltar a ter saldo positivo. Para registrar se a falta de saldo já ocorreu, modificamos a cadeia tornando $0$ absorvente. A matriz da cadeia assim parada, na ordem $(0,1,2,3)$, é

\[ Q=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1/4 & 1/2 & 1/4 & 0 \\ 0 & 1/4 & 1/2 & 1/4 \\ 0 & 0 & 1/4 & 3/4 \end{pmatrix}. \]

Por exemplo, partindo de $1$, chegar a zero no próximo mês exige $D_{n+1}=2$, o que ocorre com probabilidade $1/4$. Elevando a matriz à quarta potência, obtemos a linha de interesse:

\[ Q^4(2,\cdot )= \left(\frac{23}{128},\frac{49}{256}, \frac{77}{256},\frac{21}{64}\right). \]

Como $0$ é absorvente na nova cadeia,

\[ \boxed {\mathbb P_2(H_{\{ 0\} }\leq 4)=Q^4(2,0) =\frac{23}{128}\approx 0{,}180}. \]

Transformar em absorvente o conjunto cuja visita queremos registrar converte uma pergunta sobre toda a trajetória em uma probabilidade de transição em tempo fixo.

Exemplo 2.32 (Conclusão de um curso de dois anos)

Considere os estados $1=$ primeiro ano, $2=$ segundo ano, $G=$ conclusão e $D=$ abandono, com matriz

\[ P= \begin{pmatrix} 0{,}25 & 0{,}60 & 0 & 0{,}15 \\ 0 & 0{,}20 & 0{,}70 & 0{,}10 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \]

Se $h(i)$ é a probabilidade de concluir o curso antes de abandonar, então $h(G)=1$, $h(D)=0$ e

\[ h(1)=0{,}25h(1)+0{,}60h(2), \qquad h(2)=0{,}20h(2)+0{,}70. \]

Da segunda equação, $h(2)=7/8$; substituindo na primeira, obtemos $h(1)=7/10$. Assim, nesse modelo, $70\% $ dos estudantes que iniciam o primeiro ano concluem o curso.

Exemplo 2.33 (Ruína do jogador por análise de primeiro passo)

Voltemos ao jogo em que, a cada aposta, o capital aumenta uma unidade com probabilidade $p\in (0,1)$ ou diminui uma unidade com probabilidade $q=1-p$. O jogo termina ao atingir $0$ (ruína) ou $N$ (meta), com $N\geq 2$. Seu tempo de término é $H_{\{ 0,N\} }=H_0\wedge H_N$.

Se o capital inicial é $i$, com $0\leq i\leq N$, escrevemos

\[ u_i=\mathbb P_i(H_N\lt H_0), \]

a probabilidade de alcançar a meta antes da ruína. Como a absorção em uma das barreiras é quase certa, a probabilidade de ruína é seu complemento, $1-u_i$.

A análise de primeiro passo, demonstrada a seguir, fornece

\[ u_i= \begin{cases} \dfrac {i}{N}, & p=q=\dfrac 12,\\[2mm] \dfrac {1-(q/p)^i}{1-(q/p)^N}, & p\ne q. \end{cases} \]

No jogo justo, a chance de atingir a meta é a proporção do capital inicial em relação a ela, e não necessariamente $1/2$. Quando há deriva, as diferenças sucessivas dessa chance formam uma progressão geométrica.

Demonstração por primeiro passo ▼

De qualquer estado interior, uma sequência de $N$ perdas leva a uma barreira com probabilidade pelo menos $q^N\gt 0$. Em blocos de $N$ passos,

\[ \mathbb {P}_i(H_{\{ 0,N\} }\gt kN)\leq (1-q^N)^k. \]

Assim, a absorção ocorre quase certamente e tem esperança finita. Pelo problema de Dirichlet,

\[ u_0=0,\qquad u_N=1,\qquad u_i=pu_{i+1}+qu_{i-1}\quad (0\lt i\lt N). \]

A equação de primeiro passo pode ser reescrita como

\[ p(u_{i+1}-u_i)=q(u_i-u_{i-1}). \]

Para aproveitar essa relação, ponha $d_i=u_i-u_{i-1}$, a variação da probabilidade de sucesso quando a fortuna inicial aumenta de $i-1$ para $i$. Então

\[ d_{i+1}=\frac qp\, d_i,\qquad 1\leq i\lt N. \]

Portanto, as diferenças sucessivas formam uma progressão geométrica.

Se $p=q=1/2$, temos $d_{i+1}=d_i$, ou seja, todas as diferenças são iguais a $d_1$. Como $u_0=0$,

\[ u_i=\sum _{k=1}^{i}d_k=i\, d_1. \]

A condição $u_N=1$ determina $d_1=1/N$, e assim $u_i=i/N$: no jogo justo, a probabilidade cresce linearmente com a fortuna inicial.

Se $p\ne q$, escreva $r=q/p\ne 1$. Pela recorrência, $d_k=d_1r^{k-1}$ e, somando as diferenças,

\[ u_i=u_0+\sum _{k=1}^{i}d_k =d_1\sum _{k=0}^{i-1}r^k =d_1\, \frac{1-r^i}{1-r}. \]

Falta determinar $d_1$. Usando a outra condição de fronteira,

\[ 1=u_N=d_1\, \frac{1-r^N}{1-r} \qquad \Longrightarrow \qquad d_1=\frac{1-r}{1-r^N}. \]

Substituindo na expressão de $u_i$, encontramos

\[ \boxed {u_i=\frac{1-r^i}{1-r^N} =\frac{1-(q/p)^i}{1-(q/p)^N}.} \]

Como a absorção em $0$ ou $N$ ocorre quase certamente, a probabilidade de ruína é $1-u_i$.

2.7 Tempos de saída

Probabilidades de saída resolvem um problema de fronteira harmônico. Tempos esperados de saída resolvem uma equação quase igual, mas com um termo $1$: cada passo realizado antes de atingir o conjunto de destino acrescenta uma unidade de tempo.

Se $C=S\setminus A$ e começamos em $x\in C$, a cadeia pode visitar vários estados de $C$ antes de entrar em $A$. O relógio para na primeira entrada, no instante $H_A$.

Figura não resolvida: figuras/tempos-saida-esquema.tikz

Figura 2.22 Uma trajetória ilustrativa do tempo de chegada a $A$. O percurso destacado começa em $x\in C$, atravessa estados de $C$ e termina na primeira entrada em $A$. Não é necessário que $A$ seja absorvente.

Teorema 2.21

Equação de Poisson para o tempo de saída Seja $A\subseteq S$, suponha que $C=S\setminus A$ seja finito e que $H_A\lt \infty $ quase certamente a partir de todo $x\in C$. Então

\[ g(x)=E_x(H_A) \]

é a única solução de

\[ \begin{cases} g(x)=0,& x\in A,\\ g(x)=1+\displaystyle \sum _y p(x,y)g(y),& x\in C. \end{cases} \]

Demonstração ▼

Se $C$ é vazio, a afirmação é imediata. Suponha $C$ não vazio e escreva $T=H_A$. Mostraremos primeiro que $E_xT$ é finita. Para cada $z\in C$, a hipótese de chegada quase certa permite escolher $k_z\geq 1$ tal que $\mathbb P_z(T\leq k_z)\gt 1/2$. Como $C$ é finito, podemos tomar $k=\max _{z\in C}k_z$, de modo que

\[ \mathbb P_z(T\gt k)\leq \frac12 \qquad \text{para todo }z\in C. \]

Se a cadeia ainda não chegou a $A$ no instante $jk$, ela está em algum estado de $C$. Condicionando nesse estado e usando a propriedade de Markov,

\[ \begin{aligned} \mathbb P_x(T\gt (j+1)k) & =\sum _{z\in C}\mathbb P_x(T\gt jk,X_{jk}=z)\, \mathbb P_z(T\gt k)\\ & \leq \frac12\mathbb P_x(T\gt jk). \end{aligned} \]

Repetindo a desigualdade, obtemos $\mathbb P_x(T\gt jk)\leq 2^{-j}$. Agrupando os instantes $j k,\ldots ,(j+1)k-1$ na fórmula da cauda,

\[ E_xT=\sum _{n=0}^{\infty }\mathbb P_x(T\gt n) \leq k\sum _{j=0}^{\infty }2^{-j}=2k\lt \infty . \]

Como $T\geq 1$ quando $x\in C$, a análise do primeiro passo dá

\[ E_xT=1+\sum _y p(x,y)E_yT,\qquad x\in C, \]

e $E_xT=0$ em $A$. Portanto, $g$ satisfaz as equações.

Para provar a unicidade, seja $u$ outra solução real, com $u=0$ em $A$. A equação de primeiro passo pode ser iterada enquanto a cadeia não atingiu $A$. Mais precisamente, para cada $n\geq 0$,

\[ u(x)=E_x\left[ \sum _{j=0}^{n-1}\mathbf1_{\{ T\gt j\} } +u(X_{T\wedge n})\right]. \]

No instante inicial a identidade é trivial. Para passar de $n$ a $n+1$, em $\{ T\leq n\} $ não há outro passo a contar; em $\{ T\gt n\} $ temos $X_n\in C$. Particionando esse evento segundo $X_n=z\in C$, a propriedade de Markov dá

\[ \mathbb P_x(T\gt n,X_n=z,X_{n+1}=y) =\mathbb P_x(T\gt n,X_n=z)p(z,y). \]

A equação $u(z)=1+\sum _y p(z,y)u(y)$ acrescenta então uma unidade e substitui $u(X_n)$ pela média de $u(X_{n+1})$. Isso estabelece a identidade por indução. Como a soma das indicadoras conta exatamente os instantes anteriores a $T$,

\[ \sum _{j=0}^{n-1}\mathbf1_{\{ T\gt j\} }=T\wedge n, \qquad u(x)=E_x(T\wedge n)+E_x[u(X_{T\wedge n})]. \]

Como $u=0$ em $A$ e $C$ é finito, existe $M\lt \infty $ tal que $|u|\leq M$. No evento $\{ T\leq n\} $, o valor $u(X_{T\wedge n})$ é zero. Assim,

\[ \left|E_x[u(X_{T\wedge n})]\right| \leq M\, \mathbb P_x(T\gt n)\longrightarrow 0. \]

Para o primeiro termo, a identidade de caudas truncadas dá

\[ E_x(T\wedge n) =\sum _{j=0}^{n-1}\mathbb P_x(T\gt j) \longrightarrow \sum _{j=0}^{\infty }\mathbb P_x(T\gt j) =E_xT. \]

É o limite das somas parciais de uma série não negativa de soma finita. Logo, $u(x)=E_xT=g(x)$, o que prova a unicidade.

Exemplo 2.34 (Quanto dura o passeio de quatro estados?)

Retomemos o Exemplo 2.29. Escreva $g(i)=E_i H_{\{ 0,3\} }$. Como o jogo termina nas barreiras, $g(0)=g(3)=0$. Cada rodada realizada acrescenta uma unidade de tempo, e a análise de primeiro passo fornece

\[ g(1)=1+\frac12g(2),\qquad g(2)=1+\frac12g(1). \]

Substituindo a primeira equação na segunda,

\[ g(2)=\frac32+\frac14g(2) \quad \Longrightarrow \quad \boxed {g(2)=2},\qquad g(1)=2. \]

Assim, começando com duas unidades, o jogador disputa, em média, duas rodadas. As equações se parecem com as do exemplo anterior, mas o termo $1$ tem um papel novo: ele contabiliza o passo que acaba de ser dado.

Além da duração média até a saída, interessa o número esperado de visitas a cada estado antes de atingir $A$. A matriz fundamental reúne essas contagens.

Definição 2.11

Matriz fundamental Nas hipóteses do Teorema 2.21, suponha $C=S\setminus A$ não vazio e finito. Considere a submatriz de transições entre os estados de $C$,

\[ R=(p(x,y))_{x,y\in C}. \]

A matriz fundamental antes da saída de $C$ é

\[ \boxed {N=I+R+R^2+\cdots =\sum _{n=0}^{\infty }R^n.} \]

Ao formar $R$, conservamos apenas as transições entre estados de $C$. Partindo de $x\in C$, a cadeia pode permanecer em $C$ no próximo passo ou entrar em $A$. Por isso,

\[ \sum _{y\in C}R(x,y)=\mathbb P_x(X_1\in C)\leq 1. \]

A diferença entre essa soma e $1$ é a probabilidade de entrar em $A$ no primeiro passo. Assim, as linhas de $R$ podem somar menos que $1$.

Isso é importante ao calcular as potências de $R$. Por exemplo,

\[ R^2(x,y)=\sum _{z\in C}p(x,z)p(z,y). \]

Só aparecem caminhos que, no primeiro passo, passam por um estado $z$ de $C$ e, no segundo, chegam a $y$. Um caminho que entrasse em $A$ e depois retornasse a $C$ ficaria de fora. De modo geral, pela propriedade de Markov,

\[ R^n(x,y)=\mathbb P_x(X_n=y,\ H_A\gt n), \qquad n\geq 0,\quad x,y\in C. \]

Portanto, $R^n(x,y)$ é a probabilidade de estar em $y$ no instante $n$ sem ter atingido $A$ até esse instante. A fórmula inclui $n=0$: como a cadeia começa em $x\in C$, temos $H_A\gt 0$ e $R^0(x,y)=I(x,y)$.

Convergência da série. Pelo teorema anterior, $E_xH_A\lt \infty $ para todo $x\in C$. Como

\[ 0\leq R^n(x,y)\leq \mathbb P_x(H_A\gt n), \]

a fórmula da cauda fornece

\[ \sum _{n=0}^{\infty }R^n(x,y) \leq \sum _{n=0}^{\infty }\mathbb P_x(H_A\gt n) =E_xH_A\lt \infty . \]

Logo, a série que define $N$ converge entrada por entrada. A mesma desigualdade mostra que $R^n\to 0$. Para cada $m$, a multiplicação de uma soma finita de matrizes dá

\[ (I-R)(I+R+\cdots +R^m)=I-R^{m+1}. \]

Passando ao limite, obtemos $(I-R)N=I$. Como $I-R$ é uma matriz quadrada, isso mostra que é inversível e que

\[ \boxed {N=(I-R)^{-1}.} \]

Interpretação das entradas. Fixemos um estado $y\in C$. Antes de chegar a $A$, a cadeia pode visitar $y$ nenhuma, uma ou várias vezes. O número dessas visitas é a variável aleatória

\[ V_y=\sum _{n=0}^{H_A-1}\mathbf1_{\{ X_n=y\} }. \]

Somamos apenas os instantes $0,1,\ldots ,H_A-1$: o estado ocupado no instante $H_A$ já pertence a $A$ e não entra na contagem. Em particular, quando $x=y$, a observação inicial é uma visita. Esta contagem difere de $N(y)$, usada no estudo da recorrência: aquela começa em $n=1$ e não é interrompida na saída; aqui contamos desde o instante inicial até a primeira chegada a $A$.

Para passar das probabilidades às visitas esperadas, lembremos que a esperança de uma indicadora é a probabilidade do evento correspondente: $E_x\mathbf1_B=\mathbb P_x(B)$. Além disso,

\[ \mathbf1_{\{ X_n=y,H_A\gt n\} } =\mathbf1_{\{ X_n=y\} }\mathbf1_{\{ H_A\gt n\} }. \]

O segundo fator faz com que uma visita só seja contada quando ocorre antes da chegada a $A$. De fato, ele vale $1$ exatamente para $n=0,\ldots ,H_A-1$ e vale $0$ depois disso. Consequentemente,

\[ \sum _{n=0}^{\infty }\mathbf1_{\{ X_n=y,H_A\gt n\} } =\sum _{n=0}^{H_A-1}\mathbf1_{\{ X_n=y\} }=V_y. \]

Podemos agora passar das probabilidades às visitas esperadas:

\[ \begin{aligned} N(x,y) & =\sum _{n=0}^{\infty }\mathbb P_x(X_n=y,H_A\gt n)\\ & =\sum _{n=0}^{\infty }E_x\mathbf1_{\{ X_n=y,H_A\gt n\} }\\ & =E_x\left[\sum _{n=0}^{\infty } \mathbf1_{\{ X_n=y,H_A\gt n\} }\right]\\ & =E_x\left[\sum _{n=0}^{H_A-1}\mathbf1_{\{ X_n=y\} }\right]\\ & =\boxed {E_xV_y}. \end{aligned} \]

A troca da soma pela esperança é permitida porque as indicadoras são não negativas (Lema 2.15). A última igualdade usa a identidade anterior, isto é, a definição de $V_y$. Portanto, a entrada $N(x,y)$ é o número esperado de visitas a $y$ antes de atingir $A$, quando partimos de $x$. Ela não é, em geral, uma probabilidade.

Da contagem de visitas ao tempo de saída. Em cada instante $n\lt H_A$, a cadeia ocupa exatamente um estado de $C$. Nesse instante, portanto, exatamente uma das indicadoras $\mathbf1_{\{ X_n=y\} }$, com $y\in C$, vale $1$; todas as outras valem $0$. Assim, somar as visitas a todos os estados de $C$ conta uma vez cada instante anterior à saída:

\[ \sum _{y\in C}V_y =\sum _{n=0}^{H_A-1}\ \sum _{y\in C}\mathbf1_{\{ X_n=y\} } =H_A. \]

Tomando esperanças, encontramos

\[ \boxed {E_xH_A=\sum _{y\in C}N(x,y).} \]

Em outras palavras, somar a linha de $N$ correspondente ao estado inicial $x$ fornece o tempo médio até a chegada a $A$.

Também podemos reunir as equações de primeiro passo em notação matricial. Escrevamos $C=\{ x_1,\ldots ,x_m\} $, na mesma ordem das linhas e colunas de $R$, e definamos os vetores-coluna

\[ g_C= \begin{pmatrix} E_{x_1}H_A \\ \vdots \\ E_{x_m}H_A \end{pmatrix}, \qquad \mathbf1= \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}. \]

Assim, $g_C$ não é uma matriz de transição: cada uma de suas $m$ coordenadas é a duração média da cadeia até $A$ para um estado inicial diferente. Para $x\in C$, a equação de primeiro passo é

\[ E_xH_A=1+\sum _{y\in C}R(x,y)E_yH_A. \]

O termo $1$ representa o primeiro passo; se ele levar a $A$, o tempo restante será zero. Reunindo essas equações e usando $N=(I-R)^{-1}$, temos

\[ g_C=\mathbf1+Rg_C \quad \Longleftrightarrow \quad (I-R)g_C=\mathbf1 \quad \Longrightarrow \quad \boxed {g_C=N\mathbf1.} \]

A coordenada de $N\mathbf1$ associada a $x$ é justamente a soma da linha de $N$ correspondente a $x$, como já havíamos obtido pela contagem de visitas.

Exemplo 2.35 (Uma matriz, três perguntas: conclusão, visitas e duração)

Retomemos o curso de dois anos do Exemplo 2.32. Os estados $1$ e $2$ são transientes; $G$ (conclusão) e $D$ (abandono) são absorventes. Separemos a matriz de transição em dois blocos: $R$ reúne as transições dentro dos estados transientes, e $K$ registra as transições desses estados para $G$ e $D$:

\[ R=\begin{pmatrix} 1/4 & 3/5 \\ 0 & 1/5 \end{pmatrix}, \qquad K=\begin{array}{c|cc}& G& D\\ \hline 1& 0& 3/20\\ 2& 7/10& 1/10 \end{array}. \]

A matriz fundamental pode ser calculada invertendo $I-R$:

\[ N=(I-R)^{-1} =\begin{pmatrix} 4/3 & 1 \\ 0 & 5/4 \end{pmatrix}. \]

A primeira linha de $N$ responde a duas perguntas: partindo do primeiro ano, quantas vezes, em média, o estudante estará em cada ano antes de concluir ou abandonar? Temos $N(1,1)=4/3$ visitas esperadas ao primeiro ano, incluindo a observação inicial, e $N(1,2)=1$ visita esperada ao segundo ano.

O valor $N(1,2)=1$ é uma contagem média, não uma probabilidade. A chance de alcançar o segundo ano antes de abandonar é

\[ \mathbb P_1(H_2\lt H_D) =\frac{3/5}{1-1/4}=\frac45. \]

Uma vez no segundo ano, o número médio de visitas a ele, incluindo a primeira, é $1/(1-1/5)=5/4$, porque em cada passo há probabilidade $1/5$ de permanecer nesse estado. O produto

\[ \frac45\cdot \frac54=1=N(1,2) \]

mostra como uma probabilidade de chegada pode se transformar num número esperado de visitas.

Para calcular a probabilidade de terminar em cada estado absorvente, podemos sair de um estado transiente após $0,1,2,\ldots $ transições dentro do conjunto $\{ 1,2\} $. Somando essas possibilidades, obtemos

\[ B=(I+R+R^2+\cdots )K=NK =\begin{array}{c|cc}& G& D\\ \hline 1& 7/10& 3/10\\ 2& 7/8& 1/8 \end{array}. \]

Assim, começando no primeiro ano, a probabilidade de conclusão é $7/10$, como havíamos encontrado por análise de primeiro passo, e a de abandono é $3/10$.

Finalmente, a soma das entradas de cada linha de $N$ dá o tempo esperado até chegar a $G$ ou $D$:

\[ E_1 H_{\{ G,D\} }=\frac43+1=\boxed {\frac73}, \qquad E_2 H_{\{ G,D\} }=\boxed {\frac54}. \]

A mesma matriz fornece, portanto, visitas esperadas, probabilidades de absorção e duração média.

Exemplo 2.36 (O computador revisitado: dias de uso e de reparo)

Voltemos ao computador do Exemplo 2.6. Antes do descarte, ele pode estar funcionando ($F$) ou em reparo ($R$). A matriz das transições entre esses dois estados é

\[ Q=\begin{pmatrix} 0{,}995 & 0{,}005 \\ 0{,}90 & 0{,}05 \end{pmatrix}. \]

O descarte ocorre quase certamente. De fato, partindo de $F$, há probabilidade positiva de passar por $F\to R\to D$ em dois dias; partindo de $R$, há probabilidade $0{,}05$ de ser descartado no próximo. Como o conjunto $\{ F,R\} $ é finito, essas possibilidades permitem uma cota geométrica uniforme para o tempo de absorção.

A matriz fundamental é

\[ N=(I-Q)^{-1} =\begin{pmatrix} 3800 & 20 \\ 3600 & 20 \end{pmatrix}. \]

Por exemplo, a primeira linha mostra que um computador inicialmente em funcionamento passa, em média, $\boxed {3800}$ dias funcionando e $\boxed {20}$ dias em reparo antes do descarte, contando também a observação inicial. Assim,

\[ E_F H_D=3800+20=\boxed {3820}\ \text{dias}. \]

Se começamos com o computador em reparo, a segunda linha fornece $E_RH_D=3600+20=3620$ dias.

Como verificação independente, as equações de primeiro passo para $g_F=E_FH_D$ e $g_R=E_RH_D$ são

\[ \begin{cases} g_F=1+0{,}995g_F+0{,}005g_R,\\ g_R=1+0{,}90g_F+0{,}05g_R. \end{cases} \]

A primeira dá $g_F=g_R+200$; a segunda então dá $g_R=3620$ e $g_F=3820$, confirmando a matriz fundamental. O mesmo modelo fornece dois tipos de informação: duração total e tempo passado em cada estado.

Exemplo 2.37 (Contando visitas antes da ruína)

Retomemos o passeio justo com barreiras $0$ e $3$ dos Exemplos 2.29 e 2.34. Agora calcularemos quantas vezes cada estado interior é visitado antes da absorção. Os estados transientes são $C=\{ 1,2\} $ e a submatriz correspondente é

\[ R=\begin{pmatrix} 0 & 1/2 \\ 1/2 & 0 \end{pmatrix}. \]

Logo,

\[ I-R= \begin{pmatrix} 1 & -1/2 \\ -1/2 & 1 \end{pmatrix}, \qquad (I-R)^{-1}= \begin{pmatrix} 4/3 & 2/3 \\ 2/3 & 4/3 \end{pmatrix}. \]

Partindo de $1$, a cadeia visita em média $4/3$ vezes o próprio estado $1$ e $2/3$ vez o estado $2$ antes de atingir $\{ 0,3\} $. A soma da primeira linha é

\[ \frac43+\frac23=2, \]

portanto $E_1H_{\{ 0,3\} }=2$. Partindo de $2$, a simetria fornece o mesmo tempo médio, com os papéis dos dois estados trocados. Assim, a mesma matriz registra tanto visitas esperadas a estados específicos quanto o tempo esperado total antes da absorção.

Exemplo 2.38 (Duração do jogo)

Nas condições do Exemplo 2.33, defina

\[ v_i=E_iH_{\{ 0,N\} }, \qquad 0\leq i\leq N. \]

Assim, $v_i$ é o número médio de rodadas até o jogo terminar, quando o capital inicial é $i$. Retomemos também $u_i=\mathbb P_i(H_N\lt H_0)$, a probabilidade de atingir a meta antes da ruína. Mostraremos que

\[ v_i= \begin{cases} i(N-i),& p=q=\dfrac 12,\\[2mm] \dfrac {Nu_i-i}{p-q},& p\ne q. \end{cases} \]

No jogo justo, dobrar simultaneamente o capital inicial e a meta conserva a probabilidade de sucesso, mas multiplica por quatro a duração média. Quando há deriva, a duração depende também da direção favorecida pelas apostas.

Demonstração ▼

Já verificamos que o tempo $H_{\{ 0,N\} }$ tem esperança finita. Como nenhuma rodada é necessária quando o jogo começa numa barreira, $v_0=v_N=0$. Nos estados interiores, o primeiro passo consome uma rodada e deixa o capital em $i+1$ ou $i-1$. Portanto,

\[ v_i=1+pv_{i+1}+qv_{i-1}, \qquad 0\lt i\lt N. \]

Jogo justo: $p=q=1/2$. Reorganizando a equação, obtemos

\[ v_{i+1}-2v_i+v_{i-1}=-2. \]

A segunda diferença é constante; por isso, procuramos uma solução quadrática $v_i=-i^2+Ai+B$. De $v_0=0$ vem $B=0$ e, de $v_N=0$,

\[ 0=-N^2+AN \qquad \Longrightarrow \qquad A=N. \]

Assim,

\[ \boxed {v_i=i(N-i).} \]

Jogo com deriva: $p\ne q$. A equação homogênea associada é $w_i=pw_{i+1}+qw_{i-1}$. Reescrevendo-a como

\[ p(w_{i+1}-w_i)=q(w_i-w_{i-1}), \]

vemos que, quando $p\ne q$, suas soluções são $w_i=A+B(q/p)^i$. Precisamos ainda de uma solução particular da equação que contém o termo $1$. A função

\[ v_i^{(p)}=-\frac{i}{p-q} \]

serve, pois uma substituição direta fornece

\[ 1+p\left(-\frac{i+1}{p-q}\right) +q\left(-\frac{i-1}{p-q}\right) =-\frac{i}{p-q}. \]

Portanto, a solução geral pode ser escrita como

\[ v_i=A+B\left(\frac qp\right)^i-\frac{i}{p-q}. \]

Impondo $v_0=0$, obtemos $A=-B$, isto é,

\[ v_i=B\left[\left(\frac qp\right)^i-1\right] -\frac{i}{p-q}. \]

A outra fronteira, $v_N=0$, determina a constante:

\[ 0=B\left[\left(\frac qp\right)^N-1\right] -\frac{N}{p-q} \quad \Longrightarrow \quad B=\frac{N}{(p-q)((q/p)^N-1)}. \]

Substituindo essa expressão em $v_i$, chegamos a

\[ \begin{aligned} v_i& =\frac1{p-q} \left[N\, \frac{1-(q/p)^i}{1-(q/p)^N}-i\right]\\ & =\boxed {\frac{Nu_i-i}{p-q}}, \end{aligned} \]

pois a fração é exatamente a probabilidade $u_i$ encontrada no exemplo anterior. A unicidade da equação de Poisson garante que essa solução é a esperança procurada.

No capítulo de martingais, obteremos essas probabilidades por uma segunda demonstração. A nova ferramenta conservará esperanças até a saída e evitará resolver novamente as equações de diferenças.

Exemplo 2.39 (Esperando cara seguida de coroa)

Lançamos repetidamente uma moeda justa, com lançamentos independentes, e paramos quando aparece o padrão cara–coroa. Use os estados $0=$ nenhum prefixo útil, $C=$ o último resultado foi cara e $F=$ padrão completo. Se $g_0$ e $g_C$ são os tempos esperados restantes, então

\[ g_0=1+\frac12g_0+\frac12g_C, \qquad g_C=1+\frac12g_C+\frac12\cdot 0. \]

A segunda equação dá $g_C=2$ e a primeira dá $g_0=4$. Portanto, são necessários, em média, quatro lançamentos para observar cara seguida de coroa.

2.8 Problemas de síntese

O sapo em quatro folhas, uma rede elétrica e a manutenção de um computador reúnem as técnicas de transição, chegada e absorção. As soluções a seguir mostram como as mesmas equações respondem a perguntas sobre percursos, tempos e custos.

Exemplo 2.40 (O sapo precisa chegar à última folha)

Retomemos o sapo do Exemplo 2.1. As folhas $A$, $B$ e $C$ formam um triângulo, e a folha $D$ está ligada somente a $C$. O sapo parte de $A$, escolhe uniformemente uma folha vizinha em cada salto e quer chegar a $D$.

Figura não resolvida: figuras/sintese-sapo-alvo.tikz

Figura 2.23 O mesmo grafo das quatro folhas, agora com a partida em $A$ e a folha $D$ destacada como alvo.

Quanto tempo levará, em média, para chegar a $D$? Escreva $e_x=E_xH_D$. O problema de Poisson dá $e_D=0$ e

\[ \begin{aligned} e_A& =1+\frac{e_B+e_C}{2},\\ e_B& =1+\frac{e_A+e_C}{2},\\ e_C& =1+\frac{e_A+e_B+e_D}{3}. \end{aligned} \]

Os estados $A$ e $B$ desempenham papéis simétricos, logo $e_A=e_B=t$. Se escrevermos $e_C=v$, as equações se reduzem a

\[ t=1+\frac{t+v}{2},\qquad v=1+\frac{2t}{3}. \]

A primeira fornece $t=2+v$. Substituindo na segunda,

\[ v=1+\frac23(2+v) \quad \Longrightarrow \quad v=7,\qquad t=9. \]

Portanto,

\[ \boxed {E_AH_D=9\ \text{saltos}.} \]

E qual é a chance de atingir $D$ antes de voltar pela primeira vez a $A$? Comecemos em $B$ ou $C$ e definamos $u_x=\mathbb P_x(H_D\lt H_A)$. As condições de fronteira são $u_A=0$, $u_D=1$; pelo problema de Dirichlet,

\[ u_B=\frac{u_A+u_C}{2}=\frac{u_C}{2}, \qquad u_C=\frac{u_A+u_B+u_D}{3}=\frac{u_B+1}{3}. \]

Daí $u_C=2/5$ e $u_B=1/5$. Partindo de $A$, o primeiro salto vai para $B$ ou $C$, cada um com probabilidade $1/2$. Assim,

\[ \boxed {\mathbb P_A(H_D\lt T_A^+) =\frac12u_B+\frac12u_C=\frac3{10}.} \]

O tempo médio até o alvo e a chance de alcançá-lo antes do primeiro retorno descrevem aspectos distintos do percurso nesse grafo.

Exemplo 2.41 (Passeios aleatórios resolvem circuitos elétricos)

Considere o grafo à esquerda da figura: entre $a$ e $b$ existem dois caminhos de comprimento dois, passando por $x$ e $y$. Em cada vértice o passeio escolhe um vizinho uniformemente. Perguntamos pela probabilidade de voltar a $a$ antes de atingir $b$.

Ilustração: Problemas de síntese

Figura 2.24 Uma rede física de resistores, fios e bateria. Os grafos idealizados da figura seguinte permitem transformar potenciais elétricos em probabilidades de chegada.

Figura não resolvida: figuras/redes-eletricas.tikz

Figura 2.25 Duas redes com resistores de $1\, \Omega $. No painel B, a ligação $y$–$b$ foi removida. Os valores assinalados são potenciais, que também representam probabilidades de atingir $a$ antes de $b$.

Seja $h(z)=\mathbb P_z(H_a\lt H_b)$, de modo que $h(a)=1$ e $h(b)=0$. No grafo A, pela análise de primeiro passo,

\[ h(x)=\frac{h(a)+h(b)}2=\frac12, \qquad h(y)=\frac12. \]

Partindo de $a$, a primeira transição chega a $x$ ou $y$ com probabilidade $1/2$. Portanto,

\[ \boxed {\mathbb P_a(T_a^+\lt H_b) =\frac12h(x)+\frac12h(y)=\frac12}. \]

Substitua agora cada aresta por um resistor de $1\, \Omega $ e mantenha os potenciais $v(a)=1$ e $v(b)=0$. A lei de Kirchhoff nos vértices interiores exige que a soma das correntes seja zero:

\[ \sum _{w\sim z}(v(z)-v(w))=0 \quad \Longleftrightarrow \quad v(z)=\frac1{d(z)}\sum _{w\sim z}v(w). \]

São exatamente as equações satisfeitas por $h$. Logo, os potenciais são as probabilidades de atingimento. Os dois caminhos possuem resistência $2\, \Omega $ cada e estão em paralelo; a resistência efetiva entre $a$ e $b$ é, assim, $1\, \Omega $.

Na rede B, eliminamos a aresta $y$–$b$. A partir de $y$, a próxima transição leva obrigatoriamente a $a$, de modo que $h(y)=1$, enquanto $h(x)=1/2$ permanece igual. Consequentemente,

\[ \boxed {\mathbb P_a(T_a^+\lt H_b) =\frac12\cdot \frac12+\frac12\cdot 1=\frac34}. \]

A resistência efetiva passa a ser $2\, \Omega $: o ramo que termina em $y$ não conduz corrente até $b$.

Podemos tornar exata a conexão entre resistência e probabilidade, para qualquer um desses grafos com resistores de $1\, \Omega $. Com potenciais $v(a)=1$ e $v(b)=0$, a corrente total que sai de $a$ é

\[ I=\sum _{z\sim a}(1-v(z)). \]

Como $v(z)=\mathbb P_z(H_a\lt H_b)$, a análise do primeiro passo fornece

\[ \begin{aligned} I& =d(a)\left[1-\frac1{d(a)} \sum _{z\sim a}\mathbb P_z(H_a\lt H_b)\right]\\ & =d(a)\bigl[1-\mathbb P_a(T_a^+\lt H_b)\bigr]. \end{aligned} \]

A diferença de potencial entre $a$ e $b$ é uma unidade; pela definição de resistência efetiva, $R_{\mathrm{ef}}(a,b)=1/I$. Portanto,

\[ \boxed {\mathbb P_a(T_a^+\lt H_b) =1-\frac1{d(a)R_{\mathrm{ef}}(a,b)}.} \]

Nos dois grafos, $d(a)=2$. Com resistência $1\, \Omega $ recuperamos a probabilidade $1/2$; com resistência $2\, \Omega $, obtemos $3/4$. Retirar a ligação aumentou a resistência e a chance de voltar a $a$ antes de atingir $b$. A identidade explica a relação, em vez de apenas compará-las.

Exemplo 2.42 (O computador: vale contratar manutenção?)

Retomemos o computador do Exemplo 2.6. Em cada dia ele está funcionando ($F$), em reparo ($R$) ou definitivamente descartado ($D$). Antes do descarte, a submatriz das transições é

\[ Q=\begin{pmatrix} 0{,}995 & 0{,}005 \\ 0{,}90 & 0{,}05 \end{pmatrix}, \qquad N=(I-Q)^{-1} =\begin{pmatrix} 3800 & 20 \\ 3600 & 20 \end{pmatrix}. \]

As entradas de $N$ contam os dias esperados em cada estado antes do descarte, incluindo o dia inicial. Assim, começando em funcionamento, o computador passa, em média, $3800$ dias em $F$ e $20$ dias em $R$.

Suponha que cada dia de funcionamento produza um resultado líquido de R\$ $5$, cada dia em reparo custe R\$ $120$ e o descarte tenha custo fixo de R\$ $500$. A empresa pode pagar os reparos por dia ou contratar, no início, um plano de R\$ $2000$ que cobre todos os dias de reparo até o descarte. Admitimos que a contratação não altere as probabilidades de transição nem os demais custos.

Figura não resolvida: figuras/sintese-computador-contrato.tikz

Figura 2.26 Duas formas de pagamento para os mesmos tempos aleatórios de funcionamento e reparo. A comparação é feita pelo custo esperado.

Sem contrato, o valor esperado do resultado acumulado é

\[ \begin{aligned} E_F L_{\mathrm{avulso}} & =5\, N(F,F)-120\, N(F,R)-500\\ & =5\cdot 3800-120\cdot 20-500 =\boxed {\text{R\$ }16100}. \end{aligned} \]

Com o plano de manutenção, pagamos uma única vez pelos reparos, de modo que

\[ E_F L_{\mathrm{contrato}} =5\cdot 3800-2000-500 =\boxed {\text{R\$ }16500}. \]

Portanto, segundo o critério do resultado esperado, o contrato é preferível por R\$ $400$. A vantagem não se repete necessariamente em cada trajetória, pois o número efetivo de dias em reparo é aleatório.

A comparação desconsidera juros, inflação, aversão ao risco e mudanças na qualidade dos reparos. Para comparar com a compra imediata de outro computador, precisaríamos também modelar seu custo e seu funcionamento. A comparação econômica obtida pela matriz fundamental permanece condicionada a essas hipóteses.

A análise de primeiro passo relaciona, assim, percursos, tempos e custos. A interpretação das respostas acompanha a modelagem de cada situação.

2.9 Modelos ocultos de Markov^*

O engajamento de um usuário não é observado diretamente: registramos ações, como cliques ou dias sem acesso. Um usuário engajado pode passar um dia sem clicar, e um usuário pouco engajado pode clicar por acaso. O modelo distingue, assim, o estado que evolui da observação imperfeita desse estado.

Definição 2.12

Modelo oculto de Markov Um modelo oculto de Markov, abreviado HMM, do inglês hidden Markov model, é formado por uma cadeia de Markov $(X_n)$, com distribuição inicial $\mu _0$ e matriz de transição $P$, e por uma sequência de observações $(Y_n)$. Os estados $X_n$ não são observados diretamente; em seu lugar, observamos $Y_n$. Condicionadas à trajetória dos estados, as observações são independentes, e a lei de $Y_n$ depende apenas do estado $X_n$:

\[ \mathbb {P}(Y_n=y\mid X_0,X_1,\ldots )=b_{X_n}(y). \]

As funções $b_i$ são as probabilidades de emissão. Para manter a notação simples, trabalharemos nesta seção com observações discretas; para observações contínuas, as probabilidades de emissão são substituídas por densidades.

Ilustração: Modelos ocultos de Markov *

Figura 2.27 Os estados ocultos formam uma cadeia de Markov. Cada observação depende do estado oculto do mesmo instante. Dada a trajetória dos estados, as observações são independentes; sem esse condicionamento, elas podem ser dependentes.

Se observássemos $X_n$, bastaria usar a matriz $P$ para prever o próximo estado. Como vemos apenas $Y_n$, não sabemos com certeza onde a cadeia está. Em vez de um estado, precisamos carregar uma distribuição sobre os estados possíveis.

A descrição acima determina a lei conjunta. A Proposição 2.1 fornece a probabilidade da trajetória oculta; multiplicamos essa probabilidade pelas emissões condicionalmente independentes. Escrevendo $x_{0:n}=(x_0,\ldots ,x_n)$ e analogamente $y_{0:n}$,

\[ \mathbb {P}(x_{0:n},y_{0:n}) =\mu _0(x_0)\prod _{k=1}^n p_{x_{k-1}x_k} \prod _{k=0}^n b_{x_k}(y_k). \]

Os fatores correspondem à distribuição inicial, às transições e às emissões. Essa fatoração permite calcular a distribuição do estado oculto a partir das observações.

O problema de filtragem é o seguinte: depois de observar $Y_0,\ldots ,Y_n$, qual é a nossa distribuição para o estado atual $X_n$? Definimos

\[ r_n(j) =\mathbb {P}(X_n=j\mid Y_0=y_0,\ldots ,Y_n=y_n). \]

Quando chega uma nova observação, a atualização ocorre em dois movimentos. Primeiro deixamos a cadeia evoluir, sem ainda olhar o novo dado. Depois usamos o novo dado para corrigir a previsão:

\[ r_n \; \xrightarrow {\ \text{previsão pela cadeia}\ }\; \widetilde r_{n+1} \; \xrightarrow {\ \text{correção pela observação}\ }\; r_{n+1}. \]

O primeiro passo combina as transições da cadeia com a hipótese de que cada emissão depende apenas do estado oculto do mesmo instante; o segundo usa a regra de Bayes para incorporar a nova observação.

Proposição 2.22

Filtragem: previsão e correção Suponha que

\[ r_n(i)=\mathbb {P}(X_n=i\mid Y_{0:n}=y_{0:n}). \]

Antes de observar $Y_{n+1}$, a distribuição prevista do novo estado é

\[ \widetilde r_{n+1}(j) =\mathbb {P}(X_{n+1}=j\mid Y_{0:n}=y_{0:n}) =\sum _i r_n(i)p_{ij}. \]

Depois de observar $Y_{n+1}=y_{n+1}$, corrigimos essa distribuição por

\[ r_{n+1}(j) =\frac{b_j(y_{n+1})\, \widetilde r_{n+1}(j)}{\displaystyle \sum _k b_k(y_{n+1})\, \widetilde r_{n+1}(k)}. \]

No instante inicial,

\[ r_0(j) =\frac{\mu _0(j)b_j(y_0)}{\displaystyle \sum _k\mu _0(k)b_k(y_0)}. \]

Demonstração ▼

Comecemos pela previsão. Condicionamos segundo o estado atual:

\[ \begin{aligned} \mathbb {P}(X_{n+1}=j\mid Y_{0:n}=y_{0:n}) & = \sum _i \mathbb {P}(X_{n+1}=j\mid X_n=i,Y_{0:n}=y_{0:n})\\ & \hspace{3.2em}\times \mathbb {P}(X_n=i\mid Y_{0:n}=y_{0:n}). \end{aligned} \]

A propriedade de Markov descreve a relação entre os estados ocultos. Para incluir as observações, usamos também a hipótese de emissão. Na fatoração da lei conjunta, com $x_n=i$, o fator final é $p_{ij}$, que não depende dos estados ou das observações anteriores. Para $n\geq 1$,

\[ \begin{aligned} & \mathbb P(X_{n+1}=j,X_n=i,Y_{0:n}=y_{0:n})\\ & =\sum _{x_0,\ldots ,x_{n-1}} \mu _0(x_0)b_{x_0}(y_0) \left(\prod _{m=1}^{n}p_{x_{m-1}x_m}b_{x_m}(y_m)\right)p_{ij}\\ & =p_{ij}\, \mathbb P(X_n=i,Y_{0:n}=y_{0:n}). \end{aligned} \]

Para $n=0$, a mesma igualdade é simplesmente $\mu _0(i)b_i(y_0)p_{ij}=p_{ij}\mathbb P(X_0=i,Y_0=y_0)$. Quando o evento condicionado tem probabilidade positiva, a divisão mostra que o primeiro fator da soma anterior é $p_{ij}$; o segundo é $r_n(i)$. Estados com $r_n(i)=0$ não contribuem para a soma. Obtemos, portanto,

\[ \widetilde r_{n+1}(j)=\sum _i r_n(i)p_{ij}. \]

Agora chega a observação $Y_{n+1}=y_{n+1}$. Pela regra de Bayes,

\[ \begin{aligned} r_{n+1}(j) & = \frac{ \mathbb {P}(Y_{n+1}=y_{n+1}\mid X_{n+1}=j,Y_{0:n}=y_{0:n}) \, \widetilde r_{n+1}(j)}{\mathbb {P}(Y_{n+1}=y_{n+1}\mid Y_{0:n}=y_{0:n})}. \end{aligned} \]

A hipótese de emissão transforma o primeiro fator do numerador em $b_j(y_{n+1})$. Para obter o denominador, somamos o numerador sobre todos os estados possíveis. Surge exatamente

\[ \sum _k b_k(y_{n+1})\, \widetilde r_{n+1}(k). \]

A fórmula para $r_0$ é o mesmo argumento de Bayes aplicado à primeira observação.

A multiplicação por $P$ faz a previsão: mesmo sem receber informação nova, nossa crença sobre o estado muda porque o próprio sistema evolui. A multiplicação por $b_j(y_{n+1})$ faz a correção: estados que explicam melhor a observação recebem mais peso. A normalização final apenas faz esses novos pesos somarem um.

Toda a história $y_0,\ldots ,y_n$ influencia o futuro através de $r_n$. Depois de calcular essa distribuição, não precisamos refazer os cálculos desde o início quando chega o próximo dado. O vetor $r_n$ é o nosso estado de conhecimento sobre a cadeia oculta. Essa recursão é frequentemente chamada de algoritmo forward.

Exemplo 2.43 (Engajamento latente e cliques observados)

Tome $X_n\in \{ E,D\} $, onde $E$ significa engajado e $D$, desengajado, e $Y_n\in \{ C,S\} $, onde $C$ significa clique e $S$, silêncio no dia. Suponha

\[ P=\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}, \qquad \mu _0=(1/2,1/2), \qquad \begin{array}{c|cc}& C& S\\ \hline E& 0{,}9& 0{,}1\\ D& 0{,}2& 0{,}8 \end{array}. \]

Considere a sequência de observações

\[ C,\qquad S,\qquad C. \]

Antes de qualquer observação, atribuímos probabilidades iguais aos dois estados. O primeiro dado é um clique. Como um clique é muito mais provável em $E$ do que em $D$, Bayes produz

\[ r_0 =\frac{(0{,}5\cdot 0{,}9,\; 0{,}5\cdot 0{,}2)}{0{,}5\cdot 0{,}9+0{,}5\cdot 0{,}2} =\left(\frac9{11},\frac2{11}\right). \]

Assim, depois do clique, a probabilidade de engajamento é aproximadamente $0{,}818$.

No dia seguinte, antes de observar qualquer ação, fazemos a previsão:

\[ \widetilde r_1=r_0P =\left(\frac{39}{55},\frac{16}{55}\right). \]

A probabilidade prevista de engajamento é agora aproximadamente $0{,}709$. Ela mudou mesmo antes de chegar um novo dado: o estado oculto também pode ter mudado.

Observamos então silêncio. Sob $E$, essa observação tem probabilidade $0{,}1$; sob $D$, probabilidade $0{,}8$. Multiplicamos a previsão por esses dois pesos:

\[ \left(\frac{39}{55}\cdot 0{,}1,\; \frac{16}{55}\cdot 0{,}8\right) =\left(\frac{39}{550},\frac{128}{550}\right). \]

Normalizando,

\[ r_1 =\left(\frac{39}{167},\frac{128}{167}\right). \]

A probabilidade de engajamento cai para aproximadamente $0{,}234$. Ela não cai a zero: silêncio é evidência contra engajamento, não uma observação direta do estado.

Antes da terceira observação,

\[ \widetilde r_2=r_1P =\left(\frac{348}{835},\frac{487}{835}\right). \]

A probabilidade prevista de engajamento sobe para aproximadamente $0{,}417$, pois a matriz permite que um usuário desengajado volte a se engajar. Agora observamos um clique. A correção dá

\[ r_2 = \frac{\left(\frac{348}{835}\cdot 0{,}9,\; \frac{487}{835}\cdot 0{,}2\right)}{\frac{348}{835}\cdot 0{,}9+ \frac{487}{835}\cdot 0{,}2} = \left(\frac{1566}{2053},\frac{487}{2053}\right). \]

A probabilidade de engajamento volta a aproximadamente $0{,}763$.

O percurso completo pode ser lido em duas etapas:

\[ \begin{aligned} 0{,}5 & \xrightarrow [\text{clique}]{\text{correção}}0{,}818 \xrightarrow {\text{previsão}}0{,}709 \xrightarrow [\text{silêncio}]{\text{correção}}0{,}234\\[2pt] 0{,}234 & \xrightarrow {\text{previsão}}0{,}417 \xrightarrow [\text{clique}]{\text{correção}}0{,}763. \end{aligned} \]

Entre observações, a matriz de transição atualiza a previsão; cada nova observação a corrige. A filtragem repete essas duas operações.

Em uma cadeia observada, registramos o próprio $X_n$. No HMM, registramos $Y_n$ e mantemos uma distribuição sobre $X_n$. Por isso, $(Y_n)$ em geral não é uma cadeia de Markov: saber apenas a última observação pode perder informação que as observações anteriores forneceram sobre o estado oculto.

Para ir além. A filtragem é apenas uma das perguntas possíveis em modelos ocultos de Markov. Podemos usar observações futuras para rever o que acreditávamos sobre estados passados (smoothing), procurar uma trajetória oculta particularmente plausível (problema associado ao algoritmo de Viterbi) ou estimar a matriz de transição e as probabilidades de emissão a partir dos próprios dados, por exemplo com o algoritmo de Baum–Welch. Esses temas são tratados em Rabiner (1989) e, com numerosos exemplos de séries temporais, em Zucchini et al. (2016).

2.10 Exercícios

Os exercícios retomam a construção de matrizes, a probabilidade de trajetórias, os critérios de recorrência, a propriedade forte de Markov e os problemas de absorção.

Exercício 2.1

Probabilidades de caminhos e histórias parciais Considere uma cadeia em $\{ 1,2,3\} $ com distribuição inicial $\mu =(1/2,1/4,1/4)$ e matriz

\[ P=\begin{pmatrix} 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1/2 & 1/2 \end{pmatrix}. \]

Calcule $\mathbb P(X_0=1,X_1=2,X_2=3)$ e $\mathbb P(X_1=2,X_2=3)$. Depois encontre

\[ \mathbb P(X_2=3\mid X_0\in \{ 1,3\} ,X_1=2). \]

Explique por que a informação parcial sobre $X_0$ não muda a última probabilidade depois de conhecido $X_1$.

Exercício 2.2

Contar visitas e decidir recorrência Seja $0\lt r\lt 1$ e considere a cadeia nos estados $\{ 0,1\} $ com

\[ P=\begin{pmatrix} 1 & 0 \\ 1-r & r \end{pmatrix}. \]

Partindo de $1$, calcule $P^n(1,1)$ e a esperança do número total de visitas ao estado $1$, incluindo o instante inicial. Encontre $\mathbb P_1(T_1^+\lt \infty )$ e use o critério de contagem de visitas para classificar os dois estados.

Exercício 2.3

Um estado que guarda dois dias Um serviço registra $Y_n=1$ quando há sobrecarga no dia $n$ e $Y_n=0$ caso contrário. A probabilidade de sobrecarga amanhã depende apenas do par $(Y_{n-1},Y_n)$ e vale $0{,}1$, $0{,}6$, $0{,}3$ e $0{,}8$ nos pares $00$, $01$, $10$ e $11$, respectivamente. Suponha que todos esses históricos tenham probabilidade positiva. Explique por que registrar apenas $Y_n$ não produz uma cadeia de Markov e construa a matriz do processo dos pares, nessa ordem de estados.

Exercício 2.4

Três passos e caminhos intermediários Na ruína com barreiras $0$ e $4$, use probabilidade de ganho $p=0{,}6$. Construa $P$ e calcule $P^3(1,4)$ e $P^3(1,0)$. Confira as entradas por Chapman–Kolmogorov e pela enumeração dos caminhos, lembrando que as barreiras são absorventes.

Exercício 2.5

Meta, risco e duração Um jogador começa com duas unidades e encerra o jogo ao chegar a zero ou seis. Calcule a chance de atingir seis e a duração média quando $p=1/2$ e quando $p=3/5$. Explique por que aumentar a chance de sucesso não obriga a duração média a diminuir.

Exercício 2.6

Recomeçar ao atingir um nível No passeio justo com barreiras absorventes $0$ e $5$, comece em $X_0=2$ e defina

\[ T=\min \{ n\geq 0:X_n\in \{ 0,3\} \} , \qquad \tau =\min \{ n\geq 0:X_n\in \{ 0,5\} \} . \]

Explique por que $T$ é um tempo de parada e calcule $\mathbb P_2(X_T=3)$. Use a propriedade forte de Markov para calcular $\mathbb P_2(X_\tau =5\mid X_T=3)$ e $E_2[\tau -T\mid X_T=3]$, indicando de qual estado a cadeia recomeça. Deduza $\mathbb P_2(X_\tau =5)$ por esse caminho intermediário e compare com a fórmula direta da ruína.

Exercício 2.7

Visitas antes da absorção No jogo justo com barreiras $0$ e $5$, comece com duas unidades. Use a matriz fundamental dos estados $1,2,3,4$ para calcular o número esperado de visitas ao estado $3$ antes da absorção, incluindo o instante inicial na contagem quando cabível. Some a linha correspondente ao estado inicial e compare com a fórmula da duração média.

2.11 Exercícios complementares^*

Exercício 2.8

Filtragem com dois dias^* No modelo da Seção 2.9, observe silêncio no dia 0 e um clique no dia 1. Calcule a distribuição filtrada em cada dia e a probabilidade do clique no dia 1 dada a primeira observação.

Exercício 2.9

Emissões que não distinguem estados^* Suponha que $b_E(y)=b_D(y)$ para todo $y$. Mostre, pela atualização de Bayes, que a nova observação não muda a distribuição prevista do estado. Mostre também que, nesse modelo, a lei da sequência de observações não depende da matriz de transição dos estados ocultos. Por que essa matriz não pode ser identificada apenas a partir das observações?

Exercício 2.10

Dependência entre observações^* No exemplo de engajamento, calcule $\mathbb {P}(Y_1=C\mid Y_0=C)$ e $\mathbb {P}(Y_1=C\mid Y_0=S)$. Explique por que valores diferentes são compatíveis com a independência condicional das emissões exigida pelo HMM.

Cadeias de Markov finitas

Uma rede que recupera uma lembrança

2.1 Definições e exemplos

2.2 Probabilidades de transição em vários passos

2.2.1 Estimação de transições e retenção de usuários

2.3 Classificação dos estados

2.4 Contagem de visitas e critério de recorrência

2.5 Periodicidade dos estados

2.6 Distribuições de saída

2.7 Tempos de saída

2.8 Problemas de síntese

2.9 Modelos ocultos de Markov*

2.10 Exercícios

2.11 Exercícios complementares*

2.9 Modelos ocultos de Markov^*

2.11 Exercícios complementares^*