Capítulo 3

Distribuições estacionárias e comportamento limite

Uma distribuição pode permanecer inalterada enquanto os estados continuam mudando. A existência desse equilíbrio e a convergência para ele são questões distintas.

A descrição das transições e dos tempos de chegada permite investigar o comportamento da cadeia no longo prazo. Interessa saber se existe uma distribuição estacionária, quando ela é única e sob quais condições a lei e as médias temporais se aproximam dela. As urnas de Ehrenfest, o sapo e os modelos de mobilidade social e estoque reaparecem sob essa perspectiva.

Os resultados gerais são enunciados também para espaços enumeráveis quando suas hipóteses o permitem; no próximo capítulo veremos por que o infinito exige cuidados adicionais.

3.1 Distribuições estacionárias

Uma distribuição preservada pela dinâmica mantém a lei da cadeia inalterada em todos os instantes. Para estudar essa possibilidade, partimos da fórmula da probabilidade total:

\[ \begin{aligned} \mathbb {P}\left(X_{n}=j\right) & =\sum _{i} \mathbb {P}\left(X_{0}=i, X_{n}=j\right) \\ & =\sum _{i} \mathbb {P}\left(X_{0}=i\right) \mathbb {P}\left(X_{n}=j \mid X_{0}=i\right). \end{aligned} \]

Escrevendo \(\mu _0(i)=\mathbb {P}(X_0=i)\), a última equação toma a forma

\begin{equation} \mathbb {P}\left(X_{n}=j\right)=\sum _{i} \mu _0(i) P^{n}(i, j) \label{eq:cap1-distribuicao-no-instante-n} \tag{3.1} \end{equation}

Em notação matricial, a distribuição no instante \(n\) é \(\mu _n=\mu _0P^n\). Usamos vetores-linha: a coordenada \(j\) de \(\mu _0P^n\) é justamente a soma em (3.1).

Definição 3.1

Distribuição estacionária Uma distribuição de probabilidade \(\pi \) em \(S\) é estacionária para a cadeia com matriz de transição \(P\) se

\[ \pi P=\pi , \qquad \text{isto é,}\qquad \pi (j)=\sum _{i\in S}\pi (i)p(i,j) \quad \text{para todo }j. \]

Se \(X_0\sim \pi \), então \(X_n\sim \pi \) para todo \(n\). Isso não significa que a cadeia permaneça no mesmo estado; significa que o movimento redistribui a massa de probabilidade sem alterar sua distribuição total.

Heurística

Uma imagem para a estacionariedade Imagine uma unidade de areia distribuída entre os estados, com massa \(\pi (i)\) em \(i\). Em um passo, a fração \(p(i,j)\) da areia que estava em \(i\) é enviada para \(j\). A igualdade \(\pi P=\pi \) afirma que, depois de todas as transferências, cada estado termina com a mesma quantidade de areia com que começou.

Exemplo 3.1 (Evolução de uma distribuição inicial)

Considere o canal de comunicação do Exemplo 2.7 com \(a=0{,}4\), \(b=0{,}2\) e distribuição inicial \(\mu _0(0)=0{,}3\), \(\mu _0(1)=0{,}7\). Então

\[ (0{,}3\quad 0{,}7) \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}2 & 0{,}8 \end{pmatrix} =(0{,}32\quad 0{,}68). \]

Depois de mais um passo, a distribuição é \(\mu _0P^2=(0{,}328\quad 0{,}672)\). Para compreender o comportamento a longo prazo, não precisamos calcular todas as potências de \(P\). Basta acompanhar a probabilidade de um dos estados.

Seja \(u_n=(\mu _0P^n)(0)\) a probabilidade de estar no estado \(0\) no instante \(n\). A probabilidade de estar no estado \(1\) é, portanto, \(1-u_n\).

Para estar no estado \(0\) no instante seguinte, a cadeia pode permanecer em \(0\), com probabilidade de transição \(0{,}6\), ou passar de \(1\) para \(0\), com probabilidade \(0{,}2\). Assim,

\[ u_{n+1}=0{,}6u_n+0{,}2(1-u_n)=0{,}2+0{,}4u_n. \]

Procuramos um valor que permaneça inalterado por essa atualização. Resolvendo \(u=0{,}2+0{,}4u\), encontramos \(u=1/3\). Subtraindo esse valor da recorrência, obtemos

\[ u_{n+1}-\frac13=0{,}4\left(u_n-\frac13\right). \]

Assim, a distância de \(u_n\) a \(1/3\) é multiplicada por \(0{,}4\) a cada passo e, portanto, tende a zero. Como a probabilidade do outro estado é \(1-u_n\), concluímos que

\[ \mu _0P^n\longrightarrow \left(\frac13\quad \frac23\right). \]

Exemplo 3.2 (Estacionária sem convergência)

Considere agora uma cadeia que alterna entre os estados \(0\) e \(1\), com

\[ P=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \mu _0=(1\quad 0). \]

Como a cadeia troca de estado a cada passo,

\[ \mu _0P^{2n}=(1\quad 0),\qquad \mu _0P^{2n+1}=(0\quad 1). \]

A sequência \(\mu _0P^n\) não converge. No entanto, \(\pi =(\frac12\quad \frac12)\) é estacionária, pois \(\pi P=\pi \). Já a média das \(n\) primeiras distribuições converge:

\[ \frac1n\sum _{k=0}^{n-1}\mu _0P^k\longrightarrow \pi , \]

pois cada par de termos tem média \(\pi \) e a contribuição de um eventual termo restante tende a zero.

Se \(\mu _0P^n\) converge para uma distribuição \(\nu \) em uma cadeia finita, então

\[ \nu P=\lim _{n\to \infty }\mu _0P^{n+1}=\nu . \]

Logo, todo limite é estacionário, mas a existência de uma distribuição estacionária não garante que as distribuições sucessivas convirjam. O segundo exemplo também explica por que vale a pena considerar médias: elas podem convergir mesmo quando as distribuições oscilam. Essa será a ideia usada na demonstração seguinte.

Resta uma pergunta: sob quais condições as potências \(P^n\) convergem? Voltaremos a ela ao estudar o comportamento limite.

Proposição 3.1

Existência de uma estacionária em espaço finito Toda matriz de transição em um espaço finito e não vazio possui pelo menos uma distribuição estacionária.

A cadeia pode ter várias classes fechadas, por isso a afirmação é de existência. Em um espaço infinito, a massa das distribuições pode escapar para estados cada vez mais distantes, e o argumento de compacidade abaixo deixa de valer.

Demonstração ▼

Parta de uma distribuição qualquer \(\mu _0\). As distribuições nos instantes sucessivos são

\[ \mu _0,\ \mu _0P,\ \mu _0P^2,\ldots \]

e considere a média das \(n\) primeiras:

\[ a_n=\frac1n\sum _{j=0}^{n-1}\mu _0P^j. \]

Cada \(a_n\) ainda é uma distribuição de probabilidade, pois é uma média de distribuições. Como o espaço de estados é finito, todas essas distribuições pertencem ao simplex

\[ \left\{ u\in \mathbb R^{|S|}:u(i)\geq 0,\ \sum _i u(i)=1\right\} , \]

que é compacto. Logo existe uma subsequência \((a_{n_r})\) que converge para alguma distribuição \(\pi \).

Resta mostrar que esse limite é preservado por \(P\). Multiplicar a média por \(P\) apenas desloca a sequência em um passo:

\[ a_nP=\frac1n\sum _{j=1}^{n}\mu _0P^j. \]

Consequentemente, todos os termos intermediários se cancelam na diferença e

\[ a_nP-a_n=\frac{\mu _0P^n-\mu _0}{n}\longrightarrow 0. \]

Ao longo da subsequência escolhida, \(a_{n_r}\to \pi \); como a multiplicação por \(P\) é contínua, \(a_{n_r}P\to \pi P\). A diferença entre esses dois limites é zero, portanto

\[ \pi P=\pi . \]

Assim, \(\pi \) é uma distribuição estacionária.

Exemplo 3.3 (Uma cadeia com infinitas distribuições estacionárias)

Retomemos a cadeia de quatro estados do Exemplo 2.23. Suas classes fechadas são \(\{ 0\} \) e \(\{ 2,3\} \); o estado \(1\) é transiente. Busquemos todas as distribuições estacionárias \(\pi =(\pi _0,\pi _1,\pi _2,\pi _3)\).

Da equação \(\pi P=\pi \), a coordenada do estado \(1\) fornece

\[ \pi _1=\frac14\pi _1,\qquad \text{logo}\quad \pi _1=0. \]

As equações dos estados \(2\) e \(3\) dão

\[ \pi _2=\frac12\pi _2+\frac13\pi _3, \qquad \text{isto é,}\qquad \pi _3=\frac32\pi _2. \]

Se \(\pi _0=t\), a normalização \(\pi _0+\pi _2+\pi _3=1\) determina

\[ \boxed {\pi _t= \left(t,\ 0,\ \frac25(1-t),\ \frac35(1-t)\right), \qquad 0\leq t\leq 1.} \]

Cada valor de \(t\) fornece uma estacionária. O vetor \((2/5,3/5)\) é a estacionária da classe fechada \(\{ 2,3\} \), enquanto a massa \(t\) permanece no estado absorvente \(0\). O parâmetro livre reflete a possibilidade de repartir a massa entre duas classes que não se comunicam.

3.2 Cálculo de distribuições estacionárias

3.2.1 Cadeias com dois estados

Considere uma cadeia em \(S=\{ 1,2\} \). Escrever

\[ \begin{array}{ccc}& 1 & 2 \\ 1 & 1-a & a \\ 2 & b & 1-b \end{array} \]

torna visíveis as duas probabilidades de mudança: \(a\) para ir de \(1\) a \(2\) e \(b\) para voltar de \(2\) a \(1\). Se \(a+b\gt 0\), a distribuição estacionária é

\begin{equation} \pi _{1}=\frac{b}{a+b}, \qquad \pi _{2}=\frac{a}{a+b}. \label{eq:cap1-estacionaria-dois-estados} \tag{3.2} \end{equation}

Como primeira verificação, no canal de comunicação do Exemplo 2.7, cuja ordem dos estados é \((0,1)\), com \(a=0{,}4\) e \(b=0{,}2\), obtemos \((1/3,2/3)\). A fórmula também pode ser lida como uma igualdade de fluxos:

\[ \pi _1a=\frac{ab}{a+b}=\pi _2b. \]

Assim, a massa enviada de 1 para 2 é igual à massa enviada de 2 para 1. Algebricamente,

\begin{align*} & \frac{b}{a+b}(1-a)+\frac{a}{a+b} b=\frac{b-b a+a b}{a+b}=\frac{b}{a+b} \\ & \frac{b}{a+b} a+\frac{a}{a+b}(1-b)=\frac{b a+a-a b}{a+b}=\frac{a}{a+b} \end{align*}

A fórmula (3.2) vale sempre que \(a+b\gt 0\), inclusive quando um dos estados é absorvente. Se \(a=b=0\), ambos os estados são absorventes e toda distribuição em \(\{ 1,2\} \) é estacionária.

3.2.2 Um modelo de estoque

Retomemos a política de reposição do Exemplo 2.13, agora para determinar o estoque em equilíbrio e o resultado médio das vendas.

Exemplo 3.5 (Repor ou esperar: um pequeno problema de estoque)

Uma loja vende um produto e acompanha o estoque \(X_n\in \{ 0,1,2,3\} \) no fim de cada dia. Antes das vendas do dia seguinte, se sobraram \(0\) ou \(1\) unidades, a loja repõe o estoque até \(3\); caso contrário não encomenda nada. Denote por \(B_n\) o estoque depois da eventual reposição:

\[ B_n=\begin{cases} 3,& X_n\leq 1,\\ X_n,& X_n\geq 2.\end{cases} \]

A demanda diária independente vale \(0,1,2\) com probabilidades \(1/4,1/2,1/4\), respectivamente. Como \(B_n\geq 2\), todas as unidades demandadas são vendidas e \(X_{n+1}=B_n-D_{n+1}\).

Figura não resolvida: figuras/inventario-politica.tikz

Figura 3.1 A política de reposição depende apenas do estoque do dia anterior; depois da demanda, obtemos o novo estado da cadeia.

Por exemplo, se \(X_n=2\), a demanda \(2\) leva a \(0\) com probabilidade \(1/4\), a demanda \(1\) leva a \(1\) com probabilidade \(1/2\) e a demanda \(0\) mantém \(2\) com probabilidade \(1/4\). Na ordem \((0,1,2,3)\),

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

Resolvendo \(\pi P=\pi \) e \(\sum _i\pi (i)=1\), obtemos

\[ \pi =\left(\frac1{10},\frac7{20}, \frac25,\frac3{20}\right). \]

Para calcular custos e receitas em equilíbrio, suponha que cada unidade vendida renda \(5\), cada unidade encomendada custe \(2\) e cada unidade que sobra no fim do dia custe \(1\) para armazenar. Em equilíbrio, a demanda média é \(1\) unidade, e o número médio de unidades encomendadas por dia é

\[ 3\pi (0)+2\pi (1)=3\cdot \frac1{10} +2\cdot \frac7{20}=1. \]

Essa igualdade não é coincidência: em equilíbrio, \(E_\pi X_{n+1}=E_\pi X_n\). Como o estoque do dia seguinte é o estoque atual mais a reposição e menos a demanda, a reposição média deve igualar \(ED=1\). O estoque médio ao fim do dia vale

\[ \pi (1)+2\pi (2)+3\pi (3)=\frac85. \]

Portanto, o lucro líquido médio por dia, sob essa política, é

\[ \boxed {5\cdot 1-2\cdot 1-\frac85=\frac75}. \]

Essa é a esperança do lucro de um dia em equilíbrio. Para interpretá-la como média temporal do lucro, usamos o teorema ergódico para o estoque e a reposição, que dependem de \(X_n\), e a lei forte para as demandas independentes; voltaremos a essas ferramentas na Subseção 3.4.3.

3.2.3 Cadeias duplamente estocásticas

Definição 3.2

Matriz duplamente estocástica Uma matriz de transição \(P\) é duplamente estocástica quando, além de cada linha somar \(1\), cada coluna também soma \(1\):

\[ \sum _y p(x,y)=1 \qquad \text{e}\qquad \sum _x p(x,y)=1. \]

As somas das linhas já fazem parte da definição de matriz de transição; a condição nova é a das colunas.

Teorema 3.2

Distribuição uniforme Em um espaço com \(N\) estados, a distribuição uniforme, \(\pi (x)=1/N\), é estacionária se e somente se \(P\) é duplamente estocástica.

Demonstração ▼

Se \(P\) é duplamente estocástica, então, para cada estado \(y\),

\[ \sum _{x} \pi (x) p(x, y)=\frac{1}{N} \sum _{x} p(x, y)=\frac{1}{N}=\pi (y). \]

Logo, \(\pi P=\pi \).

Reciprocamente, suponha que a distribuição uniforme seja estacionária. Então, para cada estado \(y\),

\[ \frac{1}{N}=\pi (y)=\sum _x\pi (x)p(x,y)=\frac{1}{N}\sum _x p(x,y). \]

Multiplicando por \(N\), obtemos

\[ \sum _x p(x,y)=1. \]

Portanto, as colunas de \(P\) também somam \(1\), e \(P\) é duplamente estocástica.

Exemplo 3.6 (Passeio aleatório com reflexão nos extremos)

O espaço de estados é \(\{ 0,1,\ldots ,L\} \), com \(L\geq 1\). Nos estados interiores, a cadeia vai para cada vizinho com probabilidade \(1/2\). Adotamos a seguinte reflexão nos extremos: uma tentativa de sair do intervalo é substituída por uma permanência. Assim, \(p(0,0)=p(0,1)=1/2\) e \(p(L,L-1)=p(L,L)=1/2\). Para \(L=4\), a matriz é

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

Cada coluna soma \(1\), e o mesmo argumento vale para qualquer \(L\). Portanto, a distribuição estacionária é uniforme:

\[ \pi (i)=\frac{1}{L+1},\qquad 0\leq i\leq L. \]

3.3 Reversibilidade e balanço detalhado

A estacionariedade equilibra o fluxo total que entra e sai de cada estado. O balanço detalhado impõe uma condição mais forte: o equilíbrio deve ocorrer separadamente em cada par de estados.

Definição 3.3

Balanço detalhado e reversibilidade Uma distribuição \(\pi \) satisfaz o balanço detalhado para \(P\) se

\begin{equation*} \pi (x)p(x,y)=\pi (y)p(y,x) \qquad \text{para todos }x,y\in S. \end{equation*}

Quando existe tal distribuição, dizemos que a cadeia é reversível em relação a \(\pi \).

O produto \(\pi (x)p(x,y)\) é a probabilidade de observar a transição \(x\to y\) quando a cadeia começa com distribuição \(\pi \). A igualdade afirma que essa transição e a transição inversa têm a mesma probabilidade em equilíbrio.

Para verificar que o balanço detalhado implica estacionariedade, fixamos \(y\) e somamos em \(x\):

\[ \sum _{x} \pi (x) p(x, y)=\pi (y) \sum _{x} p(y, x)=\pi (y). \]

Na imagem da areia, o balanço detalhado diz que, para cada par \(x,y\), a massa enviada de \(x\) para \(y\) coincide com a massa enviada de \(y\) para \(x\). A estacionariedade permite compensações globais mais complexas; por isso, nem toda cadeia estacionária é reversível.

Exemplo 3.7 (Estacionária sem balanço detalhado)

Considere a matriz duplamente estocástica

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

A distribuição uniforme é estacionária, mas não satisfaz balanço detalhado: para ela, \(\pi (1)p(1,3)=0\), enquanto \(\pi (3)p(3,1)=1/15\gt 0\).

Exemplo 3.8 (Um triângulo em equilíbrio, mas não reversível)

Uma partícula percorre os vértices de um triângulo. De cada vértice ela avança no ciclo \(1\to 2\to 3\to 1\) com probabilidade \(a\) e percorre a aresta oposta com probabilidade \(1-a\), onde \(0\leq a\leq 1\). Na ordem \((1,2,3)\), a matriz é

\[ P_a=\begin{pmatrix} 0 & a & 1-a \\ 1-a & 0 & a \\ a & 1-a & 0 \end{pmatrix}. \]

Figura não resolvida: figuras/triangulo-reversibilidade.tikz

Figura 3.2 Em cada vértice, a probabilidade no sentido \(1\to 2\to 3\to 1\) é \(a\), e no sentido oposto é \(1-a\).

Cada coluna de \(P_a\) soma \(1\), logo a distribuição \(\pi =(1/3,1/3,1/3)\) é estacionária para todo \(a\in [0,1]\). O balanço detalhado entre \(1\) e \(2\), porém, exige

\[ \pi (1)p(1,2)=\pi (2)p(2,1) \quad \Longleftrightarrow \quad \frac a3=\frac{1-a}{3} \quad \Longleftrightarrow \quad \boxed {a=\frac12}. \]

Quando \(a=1/2\), as outras igualdades de balanço detalhado também valem, e a cadeia é reversível. Para \(a\ne 1/2\), a distribuição uniforme ainda é preservada, mas há uma circulação preferencial em torno do triângulo. Assim, estacionariedade não implica reversibilidade.

Exemplo 3.9 (Pesos de uma cadeia de nascimento e morte)

Uma cadeia de nascimento e morte tem espaço de estados formado por inteiros consecutivos \(\ell ,\ell +1,\ldots ,r\), com \(r\) finito ou \(r=+\infty \), e só pode permanecer no lugar ou mover uma unidade:

\[ p(x,y)=0 \quad \text{quando }|x-y|\gt 1. \]

Escrevemos

\[ \begin{array}{ll} p(x,x+1)=p_x & \text{para }x\lt r, \\ p(x,x-1)=q_x & \text{para }x\gt \ell , \\ p(x,x)=1-p_x-q_x & \text{para }\ell \leq x\leq r. \end{array} \]

Adotamos \(q_\ell =0\) e, quando \(r\) é finito, \(p_r=0\). Supomos \(p_x,q_{x+1}\gt 0\) em cada aresta admissível e \(p_x+q_x\leq 1\). O balanço detalhado entre os vizinhos \(x\) e \(x+1\) exige

\[ \pi (x)p_x=\pi (x+1)q_{x+1}, \]

logo

\begin{equation} \pi (x+1)=\frac{p_{x}}{q_{x+1}} \cdot \pi (x) \label{eq:cap1-recursao-nascimento-morte} \tag{3.3} \end{equation}

Começando em \(\ell \) e aplicando a recursão repetidamente,

\[ \pi (\ell +i)=\pi (\ell ) \cdot \frac{p_{\ell +i-1} \cdot p_{\ell +i-2} \cdots p_{\ell +1} \cdot p_{\ell }}{q_{\ell +i} \cdot q_{\ell +i-1} \cdots q_{\ell +2} \cdot q_{\ell +1}}. \]

Depois, escolhemos \(\pi (\ell )\) para que a soma das probabilidades seja 1. Essa normalização só é possível, no caso infinito, quando a série dos pesos acima converge.

Neste modelo, o balanço detalhado também é necessário para a estacionariedade. De fato, suponha que \(\pi \) seja uma distribuição estacionária e fixe \(x\lt r\). O conjunto \(F=\{ \ell ,\ldots ,x\} \) é finito. Em um passo, a única saída de \(F\) ocorre pela transição \(x\to x+1\), e a única entrada ocorre pela transição inversa. Somando as equações de estacionariedade nos estados de \(F\), obtemos

\[ \pi (F)=\pi (F)-\pi (x)p_x+\pi (x+1)q_{x+1}. \]

Portanto, \(\pi (x)p_x=\pi (x+1)q_{x+1}\) para toda aresta admissível. Toda estacionária precisa, assim, ter os pesos calculados acima. Se a série desses pesos diverge, não existe distribuição estacionária; se converge, sua normalização fornece a única estacionária.

Exemplo 3.10 (Uma fila de atendimento em equilíbrio)

Em cada instante, um serviço recebe uma nova pessoa com probabilidade \(p=2/5\), ou surge uma oportunidade de atendimento com probabilidade \(q=3/5\). Se a fila está vazia, a oportunidade de atendimento não altera seu tamanho. O estado \(X_n\) é o número de pessoas esperando; suas transições são

\[ p(0,0)=q,\quad p(0,1)=p,\qquad p(i,i+1)=p,\quad p(i,i-1)=q\quad (i\geq 1). \]

Figura não resolvida: figuras/fila-reversivel.tikz

Figura 3.3 A fila cresce nas chegadas e diminui nos atendimentos efetivos. No estado zero, uma oportunidade de atendimento produz uma permanência.

É uma cadeia de nascimento e morte. Pelo balanço detalhado, os pesos estacionários precisam satisfazer \(\pi (i+1)q=\pi (i)p\), isto é, \(\pi (i+1)=\tfrac 23\pi (i)\). A normalização da série geométrica fornece

\[ \boxed {\pi (i)=\frac13\left(\frac23\right)^i, \qquad i\geq 0.} \]

Há probabilidade estacionária \(1/3\) de a fila estar vazia. O número médio de pessoas no sistema em equilíbrio é

\[ \sum _{i=0}^{\infty }i\pi (i) =\frac13\sum _{i=0}^{\infty }i\left(\frac23\right)^i =\boxed {2}. \]

Na Seção 3.6, o Exemplo 3.22 retomará essa fila para relacionar a reversibilidade à distribuição dos atendimentos.

Exemplo 3.11 (Cadeia de Ehrenfest)

Considere primeiro o caso de três bolas. A matriz de transição é

\[ \begin{array}{ccccc}& \mathbf{0} & \mathbf{1} & \mathbf{2} & \mathbf{3} \\ \mathbf{0} & 0 & 1 & 0 & 0 \\ \mathbf{1} & 1 / 3 & 0 & 2 / 3 & 0 \\ \mathbf{2} & 0 & 2 / 3 & 0 & 1 / 3 \\ \mathbf{3} & 0 & 0 & 1 & 0 \end{array} \]

Tomando \(\pi (0)=c\) e usando (3.3), obtemos

\[ \pi (1)=3c, \qquad \pi (2)=3c, \qquad \pi (3)=c. \]

A soma é \(8c\), portanto \(c=1/8\) e

\[ \pi (0)=\frac18, \qquad \pi (1)=\frac38, \qquad \pi (2)=\frac38, \qquad \pi (3)=\frac18. \]

Os coeficientes \(1,3,3,1\) sugerem a resposta geral: para \(N\) bolas, a distribuição estacionária é binomial com parâmetros \(N\) e \(1/2\),

\[ \pi (x)=2^{-N}\binom {N}{x}. \]

Verificação da estacionária de Ehrenfest ▼

Para verificar o balanço detalhado,

\[ \begin{aligned} \pi (x) p(x, x+1) & =2^{-N} \frac{N!}{x!(N-x)!} \cdot \frac{N-x}{N} \\ & =2^{-N} \frac{N!}{(x+1)!(N-x-1)!} \cdot \frac{x+1}{N}\\ & =\pi (x+1) p(x+1, x). \end{aligned} \]

Há também uma prova probabilística. Escolha inicialmente, de forma independente e equiprovável, a urna de cada bola. Todas as \(2^N\) configurações são igualmente prováveis. Trocar a urna de uma bola escolhida ao acaso apenas permuta essas configurações, de modo que a distribuição uniforme das configurações — e, portanto, a lei binomial de \(X_n\) — permanece inalterada.

Exemplo 3.12 (Passeio aleatório em um grafo)

Seja \(G=(V,E)\) um grafo finito, simples e não orientado, sem vértices isolados. Sua matriz de adjacência é \(A(u,v)=1\) quando \(\{ u,v\} \in E\) e zero nos demais casos. O grau \(d(u)=\sum _vA(u,v)\) conta os vizinhos de \(u\) e é positivo. Escolher uniformemente um vizinho define

\[ p(u,v)=\frac{A(u,v)}{d(u)}. \]

Essa cadeia é reversível em relação à distribuição estacionária

\[ \pi (u)=\frac{d(u)}{2|E|}. \]

Um vértice com mais vizinhos recebe mais massa no equilíbrio. A verificação não exige conectividade; esta será necessária para que uma única trajetória possa explorar todo o grafo.

Demonstração ▼

Como \(A(u,v)=A(v,u)\), para qualquer constante \(c\gt 0\) os pesos \(cd(u)\) satisfazem

\[ cd(u)p(u,v)=cA(u,v)=cA(v,u)=cd(v)p(v,u). \]

Cada aresta contribui duas unidades para a soma dos graus; logo \(\sum _ud(u)=2|E|\). Tomar \(c=1/(2|E|)\) normaliza os pesos e prova o balanço detalhado.

Ilustração: Reversibilidade e balanço detalhado

Figura 3.4 Os números indicam os graus dos vértices. Sua soma é \(40\), de modo que a massa estacionária de cada vértice é seu grau dividido por \(40\).

Exemplo 3.13 (O sapo retorna: onde passa mais tempo?)

Voltemos ao sapo nas quatro folhas do Exemplo 2.1. Os graus das folhas \(A,B,C,D\) são, respectivamente, \(2,2,3,1\), e a soma é \(8\). Pelo balanço detalhado do passeio aleatório em grafo, uma distribuição estacionária é

\[ \boxed {\pi (A)=\frac14,\qquad \pi (B)=\frac14,\qquad \pi (C)=\frac38,\qquad \pi (D)=\frac18.} \]

Por exemplo, o fluxo entre \(A\) e \(C\) se equilibra:

\[ \pi (A)p(A,C)=\frac14\cdot \frac12 =\frac38\cdot \frac13=\pi (C)p(C,A). \]

A folha \(C\), ligada a três outras, recebe três vezes mais massa estacionária do que \(D\), que tem uma única ligação. Na Figura 2.3, essa diferença pode ser lida nos graus dos vértices.

Os resultados das próximas seções mostrarão que, se o grafo for conexo, a cadeia é irredutível, a estacionária é única e suas massas são também as frequências temporais a partir de qualquer vértice. A convergência das distribuições exigirá ainda aperiodicidade.

Exemplo 3.14 (Um cavalo passeando ao acaso no tabuleiro)

Um cavalo ocupa uma casa de um tabuleiro de xadrez \(8\times 8\). A cada passo, escolhe uniformemente uma das casas alcançáveis por um movimento legal. No centro do tabuleiro há oito opções; num canto há apenas duas.

Figura não resolvida: figuras/cavalo-tabuleiro.tikz

Figura 3.5 A casa inicial \(d4\), destacada em vinho, tem oito vizinhas possíveis, assinaladas em petróleo. O cavalo escolhe cada uma com probabilidade \(1/8\).

Vimos que, num passeio aleatório em um grafo não orientado, a distribuição estacionária é proporcional aos graus. Quantos movimentos legais orientados existem no tabuleiro? Há oito deslocamentos de cavalo possíveis, com sinais e ordens das componentes, e para cada deslocamento existem \(7\cdot 6\) casas iniciais permitidas. Assim, a soma dos graus das casas é \(8\cdot 7\cdot 6=336\). Logo,

\[ \pi (d4)=\frac8{336}=\frac1{42}, \qquad \pi (a1)=\frac2{336}=\frac1{168}. \]

Em equilíbrio, o cavalo ocupa \(d4\) quatro vezes mais frequentemente do que \(a1\). Cada movimento, porém, troca a cor da casa. Por isso a distribuição em um instante fixo não converge à estacionária quando partimos de uma casa determinada. Voltaremos a essa distinção ao estudar periodicidade na Seção 3.4.

3.3.1 Cadeia reversa

Suponha que a cadeia comece em equilíbrio, isto é, \(X_0\sim \pi \). Se gravarmos sua trajetória e exibirmos o filme ao contrário, obteremos novamente uma cadeia de Markov. A fórmula seguinte identifica suas probabilidades de transição.

Teorema 3.3

Cadeia reversa Suponha que \(X_0\sim \pi \), onde \(\pi \) é estacionária, e fixe \(n\). O processo

\[ Y_m=X_{n-m},\qquad 0\leq m\leq n, \]

é uma cadeia de Markov no suporte \(S_\pi =\{ i\in S:\pi (i)\gt 0\} \), cujas transições, para \(0\leq m\lt n\), são dadas pela matriz reversa

\begin{equation*} \widehat p(i,j)=\frac{\pi (j)p(j,i)}{\pi (i)}, \qquad i,j\in S_\pi . \end{equation*}

Demonstração ▼

Primeiro, a cadeia em equilíbrio permanece no suporte \(S_\pi \). De fato, se \(j\notin S_\pi \), a estacionariedade implica

\[ 0=\pi (j)=\sum _i\pi (i)p(i,j). \]

Como os termos são não negativos, \(p(i,j)=0\) para todo \(i\in S_\pi \). Portanto, partindo do suporte, a cadeia não pode sair dele.

Fixe \(0\leq m\lt n\) e escreva \(t=n-m\). Uma história da cadeia reversa com \(Y_m=i\), \(Y_{m-1}=a_1,\ldots ,Y_0=a_m\) corresponde, na cadeia original, a

\[ X_t=i,\quad X_{t+1}=a_1,\ \ldots ,\ X_n=a_m. \]

A história considerada tem probabilidade positiva e, portanto, \(\pi (i)\gt 0\). Denote por

\[ c_i=\mathbb P_i(X_1=a_1,\ldots ,X_m=a_m) \]

a probabilidade desse trecho futuro, com a convenção \(c_i=1\) quando \(m=0\). Pela propriedade de Markov, uma vez conhecido \(X_t=i\), a probabilidade desse futuro é \(c_i\), independentemente do estado ocupado em \(t-1\). Pela estacionariedade, \(\mathbb P(X_{t-1}=j,X_t=i)=\pi (j)p(j,i)\). Assim,

\[ \begin{aligned} & \mathbb P(X_{t-1}=j,X_t=i,X_{t+1}=a_1,\ldots ,X_n=a_m) =\pi (j)p(j,i)c_i,\\ & \mathbb P(X_t=i,X_{t+1}=a_1,\ldots ,X_n=a_m) =\pi (i)c_i. \end{aligned} \]

Dividindo a primeira probabilidade pela segunda, o fator correspondente ao futuro se cancela:

\[ \begin{aligned} & \mathbb P(Y_{m+1}=j\mid Y_m=i,Y_{m-1}=a_1,\ldots ,Y_0=a_m)\\ & \qquad =\frac{\pi (j)p(j,i)c_i}{\pi (i)c_i} =\frac{\pi (j)p(j,i)}{\pi (i)}. \end{aligned} \]

O resultado depende apenas de \(i\) e \(j\), não dos demais estados observados nem do instante \(m\). Isso prova a propriedade de Markov e a homogeneidade da cadeia reversa.

Por fim, a fórmula define uma matriz de transição em \(S_\pi \), pois, para \(i\in S_\pi \),

\[ \sum _{j\in S_\pi }\widehat p(i,j) =\frac1{\pi (i)}\sum _{j\in S_\pi }\pi (j)p(j,i) =\frac{\pi (i)}{\pi (i)}=1. \]

Os termos com \(j\notin S_\pi \) têm peso zero. Se quisermos estender \(\widehat P\) a todo \(S\), basta completar as linhas fora do suporte com distribuições de probabilidade arbitrárias; elas não afetam a cadeia em equilíbrio.

Se \(\pi \) satisfaz o balanço detalhado, então, para \(i,j\in S_\pi \),

\[ \widehat p(i,j)=\frac{\pi (j)p(j,i)}{\pi (i)}=p(i,j). \]

Nesse caso, um filme da cadeia em equilíbrio tem a mesma lei quando exibido de trás para a frente. Essa é a razão para o nome reversível.

Exemplo 3.15 (Um ciclo visto ao contrário)

Nos estados \(1,2,3\), seja \(C\) o ciclo orientado \(1\to 2\to 3\to 1\) e tome \(P=0{,}2I+0{,}8C\). Então

\[ P=\begin{pmatrix} 0{,}2 & 0{,}8 & 0 \\ 0 & 0{,}2 & 0{,}8 \\ 0{,}8 & 0 & 0{,}2 \end{pmatrix}. \]

As colunas somam um, logo \(\pi =(1/3,1/3,1/3)\) é estacionária. A fórmula da cadeia reversa dá \(\widehat P=P^{\mathsf T}\):

\[ \widehat P=\begin{pmatrix} 0{,}2 & 0 & 0{,}8 \\ 0{,}8 & 0{,}2 & 0 \\ 0 & 0{,}8 & 0{,}2 \end{pmatrix}. \]

O filme invertido percorre o ciclo no sentido oposto. Como \(p(1,2)=0{,}8\) e \(p(2,1)=0\), não há balanço detalhado com a estacionária uniforme: equilíbrio não implica reversibilidade.

Ilustração: Cadeia reversa

Figura 3.6 A cadeia original e sua reversa têm a mesma distribuição estacionária, mas percorrem o ciclo em sentidos opostos. Na original, \(\pi (1)p(1,2)=4/15\) e \(\pi (2)p(2,1)=0\): a preservação das massas não exige balanço detalhado em cada par de estados.

3.4 Comportamento limite

A existência de uma distribuição estacionária não assegura que a lei da cadeia convirja para ela. A recorrência e a periodicidade permitem distinguir as situações em que essa aproximação ocorre.

Se \(y\) é transiente, os Lemas 2.14 e 2.15 dão \(\sum _{n=1}^{\infty } P^{n}(x, y)\lt \infty \) para qualquer estado inicial \(x\) e, consequentemente,

\[ P^{n}(x,y) \longrightarrow 0. \]

Assim, a probabilidade de cada estado transiente fixado tende a zero. Em um espaço infinito, isso não impede que toda a massa permaneça no conjunto dos estados transientes, deslocando-se para estados cada vez mais distantes. Para entender a convergência, concentramos a atenção em classes irredutíveis recorrentes. A periodicidade, definida no capítulo anterior, ainda pode impedir que a lei convirja.

Esse comportamento já apareceu no Exemplo 3.2.

Há duas formas de observar o longo prazo: a distribuição em um instante distante e a média calculada ao longo de uma única trajetória.

Heurística

Convergência da lei e média temporal Em uma cadeia irredutível com estacionária \(\pi \), a aperiodicidade garante \(P^n(x,y)\to \pi (y)\). As médias temporais podem convergir mesmo com periodicidade: a cadeia pode passar uma fração bem definida do tempo em cada estado.

3.4.1 Frequências e tempo médio de retorno

As médias ao longo de uma trajetória dispensam a aperiodicidade. Cada retorno ao mesmo estado encerra uma excursão e permite recomeçar com a mesma lei.

Teorema 3.4

Frequência assintótica Suponha que a cadeia em um espaço finito ou enumerável seja irredutível e recorrente. Para

\[ N_n(y)=\sum _{m=1}^n\mathbf1_{\{ X_m=y\} }, \]

vale, sob \(\mathbb {P}_x\) para todo estado inicial \(x\),

\[ \frac{N_n(y)}n\longrightarrow \frac1{E_yT_y^+} \quad \text{quase certamente}, \]

com a convenção \(1/\infty =0\).

O inverso do intervalo médio entre visitas é a frequência de visitas. Se o intervalo tem média infinita, a cadeia ainda retorna infinitas vezes, mas os retornos ocupam uma fração assintótica nula do tempo.

Demonstração ▼

Pela irredutibilidade e recorrência, \(H_y\lt \infty \) quase certamente, qualquer que seja o estado inicial. Ponha \(R_0=H_y\) e seja \(R_k\) o instante do \(k\)-ésimo retorno depois de \(R_0\). Pela propriedade forte de Markov, os intervalos \(L_k=R_k-R_{k-1}\), \(k\geq 1\), são independentes e identicamente distribuídos (i.i.d.), com a lei de \(T_y^+\) sob \(\mathbb {P}_y\).

Se \(a=E_yT_y^+\lt \infty \), a lei forte dos grandes números dá \(R_k/k\to a\). Para \(n\geq H_y\), denote por \(k(n)\) o maior inteiro \(k\geq 0\) tal que \(R_k\leq n\). Pela recorrência, \(k(n)\to \infty \) quase certamente. Para \(k(n)\geq 1\),

\[ \frac{R_{k(n)}}{k(n)} \leq \frac{n}{k(n)} \lt \frac{R_{k(n)+1}}{k(n)+1}\, \frac{k(n)+1}{k(n)}. \]

A lei forte vale também ao longo da subsequência \(k(n)\). Os dois extremos convergem a \(a\), logo \(n/k(n)\to a\) e \(k(n)/n\to 1/a\). A contagem \(N_n(y)\) difere de \(k(n)\) em no máximo uma visita, o que não altera o limite.

Se \(E_yT_y^+=\infty \), aplicamos a lei forte às variáveis limitadas \(L_k\wedge b\). Para cada inteiro \(b\geq 1\),

\[ \liminf _{k\to \infty }\frac{R_k}{k}\geq E_y(T_y^+\wedge b) \quad \text{quase certamente}. \]

Podemos tomar essas desigualdades simultaneamente para todos os inteiros \(b\geq 1\): a união enumerável dos eventos excepcionais ainda tem probabilidade zero. Pela fórmula da cauda do Lema 2.13,

\[ E_y(T_y^+\wedge b)=\sum _{j=1}^{b}\mathbb P_y(T_y^+\geq j), \qquad E_yT_y^+=\sum _{j=1}^{\infty }\mathbb P_y(T_y^+\geq j)=\infty . \]

As esperanças truncadas são, portanto, as somas parciais de uma série divergente de termos não negativos. Dado qualquer número \(M\), podemos escolher \(b\) com \(E_y(T_y^+\wedge b)\gt M\); a desigualdade anterior dá \(\liminf _kR_k/k\gt M\). Como \(M\) é arbitrário, \(R_k/k\to \infty \). Usando o mesmo \(k(n)\), temos \(n/k(n)\geq R_{k(n)}/k(n)\to \infty \); portanto \(N_n(y)/n\to 0\) também nesse caso.

Definição 3.4

Recorrência positiva e recorrência nula Um estado recorrente \(y\) é recorrente positivo se \(E_yT_y^+\lt \infty \) e recorrente nulo se \(E_yT_y^+=\infty \).

A estimativa seguinte permite passar às esperanças para variáveis limitadas, relacionando as frequências observadas nas trajetórias às probabilidades.

Lema 3.5

Esperanças de variáveis entre zero e um Se \(0\leq Z_n\leq 1\) e \(Z_n\to c\) quase certamente, onde \(c\in [0,1]\) é uma constante, então \(EZ_n\to c\).

Demonstração ▼

Fixe \(\varepsilon \gt 0\) e defina

\[ A_N=\bigcup _{n\geq N}\{ |Z_n-c|\gt \varepsilon \} . \]

Os eventos \(A_N\) decrescem com \(N\). Como \(Z_n\to c\) quase certamente, a probabilidade de sua interseção é zero: fora do evento excepcional, somente um número finito dos desvios pode superar \(\varepsilon \). Pela continuidade das probabilidades para eventos decrescentes, \(\mathbb P(A_N)\to 0\). Essa propriedade decorre da aditividade enumerável, como recordado na Proposição 2.9.

Para \(n\geq N\), temos \(|Z_n-c|\leq \varepsilon \) fora de \(A_N\) e \(|Z_n-c|\leq 1\) em \(A_N\). Logo,

\[ |EZ_n-c|\leq E|Z_n-c|\leq \varepsilon +\mathbb P(A_N). \]

Primeiro escolhemos \(N\) para tornar pequena a última probabilidade; depois usamos que \(\varepsilon \) pode ser arbitrariamente pequeno. Isso prova a afirmação.

Como exemplo, considere a cadeia de Ehrenfest. O espaço é finito e a cadeia é irredutível; o Lema 2.10 limita a esperança do retorno por uma série geométrica. Seus estados são, portanto, recorrentes positivos.

Teorema 3.6

Tempo médio de retorno Se uma cadeia irredutível em espaço finito ou enumerável possui distribuição estacionária \(\pi \), então todos os estados são recorrentes positivos e

\[ \pi (y)=\frac1{E_yT_y^+}\gt 0. \]

Em particular, a distribuição estacionária é única.

Um estado com maior massa estacionária reaparece mais cedo, em média. A finitude do espaço garante a existência de alguma estacionária; em um espaço enumerável, essa existência é uma hipótese adicional, que exclui tanto transiência quanto recorrência nula numa cadeia irredutível.

Demonstração ▼

Primeiro, \(\pi (y)\gt 0\) para todo \(y\). De fato, escolha \(z\) com \(\pi (z)\gt 0\) e um caminho de \(z\) a \(y\) em \(r\) passos. Então \(\pi (y)=(\pi P^r)(y)\geq \pi (z)P^r(z,y)\gt 0\).

Pelo Lema 2.17, recorrência ou transiência é propriedade da classe. Se a classe fosse transiente, teríamos \(P^n(x,y)\to 0\) para todo \(x\). Fixe \(\varepsilon \gt 0\) e escolha um conjunto finito \(F\subseteq S\) com \(\sum _{x\notin F}\pi (x)\lt \varepsilon \). Pela estacionariedade e por \(P^n(x,y)\leq 1\),

\[ \pi (y)=\sum _x\pi (x)P^n(x,y) \leq \sum _{x\in F}\pi (x)P^n(x,y)+\varepsilon . \]

A soma à direita é finita e tende a zero. Portanto \(\pi (y)\leq \varepsilon \); como \(\varepsilon \) é arbitrário, teríamos \(\pi (y)=0\), uma contradição. Logo a cadeia é recorrente.

Comece agora com \(X_0\sim \pi \). A estacionariedade dá \(E_\pi [N_n(y)/n]=\pi (y)\). O teorema de frequência vale para todo estado inicial e, portanto, também para essa mistura de leis: se \(\mathcal A\) é o evento de convergência, a probabilidade total dá \(\mathbb P_\pi (\mathcal A)=\sum _x\pi (x)\mathbb P_x(\mathcal A)=1\). Como \(0\leq N_n(y)/n\leq 1\), o Lema 3.5 fornece

\[ \pi (y)=\frac1{E_yT_y^+}. \]

O lado esquerdo é positivo, logo a esperança é finita. A fórmula determina cada coordenada de qualquer distribuição estacionária, provando a unicidade.

No passeio do cavalo do Exemplo 3.14, já calculamos \(\pi (d4)=1/42\) e \(\pi (a1)=1/168\). Portanto,

\[ E_{d4}T_{d4}^+=42, \qquad E_{a1}T_{a1}^+=168. \]

A casa central é visitada, em média, quatro vezes mais frequentemente que o canto. A periodicidade desse passeio não altera a fórmula do tempo médio de retorno.

Para o sapo do Exemplo 3.13,

\[ E_CT_C^+=\frac{1}{3/8}=\frac83, \qquad E_DT_D^+=\frac{1}{1/8}=8. \]

A folha \(D\) tem um tempo médio de retorno três vezes maior que \(C\). Para a fila do Exemplo 3.10, a probabilidade estacionária de estar vazia é \(\pi (0)=1/3\); logo, o tempo médio entre visitas sucessivas à fila vazia é \(E_0T_0^+=3\) instantes.

Reciprocamente, um tempo médio de retorno finito permite construir uma distribuição estacionária a partir das visitas de uma excursão completa. As mesmas contagens serão usadas no estudo das recompensas.

Proposição 3.7

Pesos de ocupação de uma excursão Considere uma cadeia em espaço finito ou enumerável e um estado \(a\) para o qual \(L=T_a^+\) satisfaz \(\ell =E_aL\lt \infty \). Defina

\[ \nu (y)=E_a\sum _{m=0}^{L-1}\mathbf1_{\{ X_m=y\} }. \]

Então \(\sum _y\nu (y)=\ell \), \(\nu P=\nu \) e \(\nu /\ell \) é uma distribuição estacionária.

Demonstração ▼

Como \(E_aL\lt \infty \), o retorno ocorre em tempo finito quase certamente. Cada excursão é uma sequência finita

\[ \gamma =(\gamma _0,\ldots ,\gamma _r), \qquad \gamma _0=\gamma _r=a, \qquad \gamma _m\ne a\quad (1\leq m\lt r), \]

com comprimento \(r=r(\gamma )\geq 1\). O conjunto \(\Gamma \) dessas sequências é enumerável, pois \(S\) é finito ou enumerável. A probabilidade da excursão \(\gamma \) é

\[ q_\gamma =\prod _{m=0}^{r-1}p(\gamma _m,\gamma _{m+1}), \qquad \sum _{\gamma \in \Gamma }q_\gamma =1. \]

Se \(n_y(\gamma )=\sum _{m=0}^{r-1}\mathbf1_{\{ \gamma _m=y\} }\), a definição de esperança para essa distribuição enumerável dá

\[ \nu (y)=\sum _{\gamma \in \Gamma }q_\gamma n_y(\gamma ). \]

Em cada excursão, \(\sum _y n_y(\gamma )=r\). Reagrupando séries de termos não negativos, como explicado no capítulo anterior,

\[ \sum _y\nu (y) =\sum _{\gamma \in \Gamma }q_\gamma \sum _y n_y(\gamma ) =\sum _{\gamma \in \Gamma }q_\gamma r =E_aL=\ell . \]

Também podemos reagrupar as visitas segundo o instante em que ocorrem, obtendo \(\nu (x)=\sum _{m\geq 0}\mathbb P_a(L\gt m,X_m=x)\). O evento \(\{ L\gt m\} \) é determinado pela trajetória até \(m\). Assim, a propriedade de Markov, aplicada em cada instante fixo, fornece

\[ \begin{aligned} \sum _x\nu (x)p(x,y) & =\sum _{m\geq 0}\sum _x\mathbb P_a(L\gt m,X_m=x)p(x,y)\\ & =\sum _{m\geq 0}\mathbb P_a(L\gt m,X_{m+1}=y)\\ & =\sum _{\gamma \in \Gamma }q_\gamma \sum _{m=0}^{r-1}\mathbf1_{\{ \gamma _{m+1}=y\} }. \end{aligned} \]

Todas as parcelas são não negativas; os reagrupamentos são os mesmos de séries numéricas usados acima. Em cada excursão finita, trocar a visita inicial pela final não muda a contagem, pois \(\gamma _0=\gamma _r=a\). A última expressão é, portanto, \(\nu (y)\). Concluímos que \(\nu P=\nu \). Como \(1\leq \ell \lt \infty \), dividir por \(\ell \) normaliza os pesos e produz uma distribuição estacionária.

Teorema 3.8

Recorrência positiva e existência de estacionária Uma cadeia irredutível em espaço finito ou enumerável possui distribuição estacionária se e somente se algum de seus estados é recorrente positivo. Nesse caso, todos os estados são recorrentes positivos e a distribuição estacionária é única.

Demonstração ▼

Se existe uma distribuição estacionária, o Teorema 3.6 dá recorrência positiva de todos os estados e unicidade. Reciprocamente, se \(a\) é recorrente positivo, a Proposição 3.7 constrói uma estacionária a partir de suas excursões. Aplicando novamente o teorema do tempo médio de retorno, obtemos as demais afirmações.

3.4.2 Convergência das distribuições

A convergência das distribuições exige eliminar as oscilações periódicas. O próximo lema mostra como a aperiodicidade permite comparar trajetórias em um mesmo instante.

Lema 3.9

Caminhos com todos os comprimentos suficientemente grandes Em uma cadeia irredutível e aperiódica, para cada par \(x,y\) existe \(n_0(x,y)\) tal que \(P^n(x,y)\gt 0\) para todo \(n\geq n_0(x,y)\).

Podemos inserir voltas num caminho de \(x\) a \(y\). Quando os comprimentos das voltas não compartilham um divisor maior que um, essas inserções acabam preenchendo todos os tempos grandes.

Demonstração ▼

Fixe um estado \(a\). Podemos escolher tempos possíveis de retorno \(r_1,\ldots ,r_j\) cujo máximo divisor comum seja \(1\). Concatenar caminhos de retorno mostra que toda soma positiva desses números com coeficientes inteiros não negativos também é um tempo possível de retorno.

Como o máximo divisor comum é \(1\), a identidade de Bézout permite escrever cada resíduo módulo \(r_1\) como uma combinação inteira de \(r_1,\ldots ,r_j\). Podemos tornar não negativos os coeficientes de \(r_2,\ldots ,r_j\) somando a eles múltiplos suficientemente grandes de \(r_1\); isso não muda o resíduo da combinação. O termo que multiplica \(r_1\) pode ser omitido. Assim, para cada resíduo \(b\), existe uma soma não negativa \(s_b\) dos tempos de retorno que tem esse resíduo.

Seja \(M\) o maior desses representantes. Todo inteiro \(n\gt M\) tem a forma \(s_b+qr_1\), com \(q\geq 0\), e portanto é um tempo possível de retorno a \(a\). Finalmente, concatene um caminho de \(x\) a \(a\), uma dessas voltas e um caminho de \(a\) a \(y\). Isso fornece a afirmação.

Teorema 3.10

Teorema da convergência Suponha que uma cadeia em espaço finito ou enumerável seja irredutível e aperiódica e possua distribuição estacionária \(\pi \). Então, para todos os estados \(x,y\),

\[ P^n(x,y)\longrightarrow \pi (y). \]

A irredutibilidade permite que duas trajetórias se encontrem; a aperiodicidade permite que o encontro ocorra no mesmo relógio. A existência de uma probabilidade estacionária impede que a massa escape para regiões cada vez mais distantes. A demonstração usa um acoplamento: uma construção conjunta de duas cadeias no mesmo espaço de probabilidade que preserva a lei de cada uma separadamente. Construiremos uma cópia iniciada em \(x\) e outra em equilíbrio; depois que elas se encontrarem, passarão a evoluir juntas.

Ilustração: Convergência das distribuições

Figura 3.7 Duas cadeias evoluem separadamente até o primeiro encontro \(H_D\). Daí em diante, usam as mesmas transições e permanecem juntas. Os círculos representam estados em cada instante, sem especificar seus valores.

Demonstração ▼

Comece com duas cadeias independentes de matriz \(P\). A cadeia dos pares tem transição

\[ Q\bigl((u,v),(u',v')\bigr)=p(u,u')p(v,v'). \]

A aperiodicidade permite escolher um mesmo instante para as duas coordenadas. Pelo lema anterior, dados \((u,v)\) e \((u',v')\), existem \(n_1\) e \(n_2\) tais que

\[ P^n(u,u')\gt 0\quad (n\geq n_1), \qquad P^n(v,v')\gt 0\quad (n\geq n_2). \]

Escolhendo o mesmo \(n\geq \max \{ n_1,n_2\} \) para as duas coordenadas,

\[ Q^n\bigl((u,v),(u',v')\bigr) =P^n(u,u')P^n(v,v')\gt 0. \]

Portanto, a cadeia dos pares é irredutível. Além disso, se as duas coordenadas começam independentemente com lei \(\pi \) e usam transições independentes, ambas permanecem independentes e com lei \(\pi \). Assim, a distribuição produto, definida por \((\pi \otimes \pi )(u,v)=\pi (u)\pi (v)\), é estacionária para \(Q\). Pelo teorema do tempo médio de retorno, uma cadeia irredutível que possui essa probabilidade estacionária é recorrente positiva. Em particular, partindo de qualquer par, ela atinge qualquer par fixado, por exemplo \((a,a)\), quase certamente.

Agora tome \(X_0=x\) e \(Y_0\sim \pi \). Seja \(D=\{ (z,z):z\in S\} \) a diagonal e \(H_D=\inf \{ n\geq 0:X_n=Y_n\} \) o primeiro encontro. Antes do encontro, as coordenadas evoluem independentemente; a partir dele, usam a mesma transição sorteada.

Essa mudança altera apenas a dependência entre as coordenadas. Antes ou depois do encontro, dado o estado atual \(z\) de uma coordenada, o seu próximo estado continua sendo sorteado segundo \(p(z,\cdot )\). Assim, cada coordenada conserva sua lei de cadeia de Markov com matriz \(P\): \(X\) começa em \(x\) e \(Y\) permanece em equilíbrio. Até o encontro, a lei é a da cadeia dos pares; como ela chega a \((a,a)\) em tempo finito, \(H_D\lt \infty \) quase certamente.

Se \(X_n\ne Y_n\), o encontro ainda não ocorreu. Para qualquer conjunto \(A\subseteq S\),

\[ \begin{aligned} |\mathbb {P}_x(X_n\in A)-\pi (A)| & =|E(\mathbf1_{\{ X_n\in A\} }-\mathbf1_{\{ Y_n\in A\} })|\\ & \leq \mathbb {P}(X_n\ne Y_n)\leq \mathbb {P}(H_D\gt n)\longrightarrow 0. \end{aligned} \]

Na primeira desigualdade usamos que \(|\mathbf1_{\{ X_n\in A\} }-\mathbf1_{\{ Y_n\in A\} }| \leq \mathbf1_{\{ X_n\ne Y_n\} }\). O último limite usa apenas a continuidade das probabilidades: os eventos \(\{ H_D\gt n\} \) decrescem para \(\{ H_D=\infty \} \), cuja probabilidade é zero. Como a cota vale para todo conjunto \(A\),

\[ \sup _{A\subseteq S} \bigl|\mathbb {P}_x(X_n\in A)-\pi (A)\bigr| \leq \mathbb {P}(H_D\gt n)\longrightarrow 0. \]

Essa é precisamente a cota de variação total que será formalizada adiante. Escolhendo \(A=\{ y\} \), obtemos o enunciado.

Retomemos também a cadeia redutível dos Exemplos 2.23 e 3.3. Começando no estado \(1\), a cadeia sai dele quase certamente, pois a chance de permanecer ali por \(n\) passos é \((1/4)^n\). A probabilidade de entrar primeiro em \(0\) é \(1/3\); a de entrar na classe \(\{ 2,3\} \) é \(2/3\). A classe \(\{ 2,3\} \) é irredutível e aperiódica, e sua lei converge para \((2/5,3/5)\). Aplicando o teorema depois da entrada nessa classe, obtemos

\[ \begin{aligned} \lim _{n\to \infty }P^n(1,\cdot ) & =\frac13(1,0,0,0) +\frac23(0,0,2/5,3/5)\\ & =\boxed {(1/3,\ 0,\ 4/15,\ 2/5)}. \end{aligned} \]

Esta é uma das distribuições estacionárias calculadas anteriormente, com \(t=1/3\). Em uma cadeia redutível, a distribuição limite pode depender do estado inicial: a dinâmica determina quanta massa alcança cada classe fechada.

Exemplo 3.16 (Três modelos revisitados: o que acontece após muitas etapas?)

O sapo. O grafo das folhas é conexo, logo a cadeia é irredutível. Há um retorno possível a \(A\) em dois saltos, \(A\to B\to A\), e outro em três, \(A\to B\to C\to A\). Como \(\gcd (2,3)=1\), a cadeia é aperiódica. Pelo teorema da convergência e pelo Exemplo 3.13,

\[ \lim _{n\to \infty }P^n(A,C)=\frac38, \qquad \lim _{n\to \infty }P^n(A,D)=\frac18. \]

A mobilidade social. Na matriz do Exemplo 2.5, todas as entradas são positivas. Portanto, qualquer classe alcança qualquer outra em um passo e há permanências positivas: a cadeia é irredutível e aperiódica. Sua distribuição de uma geração distante converge para a estacionária que calculamos:

\[ P^n(2,\cdot )\longrightarrow \left(\frac{22}{47},\frac{16}{47},\frac9{47}\right). \]

A ruína do jogador. No jogo do Exemplo 2.2, com \(p=2/5\), barreiras \(0\) e \(5\) e fortuna inicial \(2\), os estados interiores são transientes e a cadeia é absorvida em uma das barreiras. A fórmula de ruína finita fornece

\[ \mathbb P_2(H_5\lt H_0) =\frac{1-(3/2)^2}{1-(3/2)^5} =\frac{40}{211}. \]

Assim,

\[ \lim _{n\to \infty }P^n(2,0)=\frac{171}{211}, \qquad \lim _{n\to \infty }P^n(2,5)=\frac{40}{211}. \]

A distribuição limite é uma mistura das massas absorventes, que depende da fortuna inicial. Os três exemplos mostram duas situações distintas: numa cadeia finita irredutível e aperiódica a lei converge para uma distribuição única; numa cadeia redutível com absorção, o limite registra qual classe fechada foi atingida.

3.4.3 Recompensas ao longo de uma trajetória

Contar visitas corresponde a atribuir recompensa um em um estado e zero nos demais. Custos e observações gerais exigem mais cuidado: num espaço infinito, não basta somar limites de frequências sem controlar a contribuição dos estados raros.

Teorema 3.11

Teorema ergódico Suponha que uma cadeia em espaço finito ou enumerável seja irredutível e possua distribuição estacionária \(\pi \). Se \(f:S\to \mathbb R\) satisfaz \(\sum _x|f(x)|\pi (x)\lt \infty \), então, sob qualquer estado inicial,

\[ \frac1n\sum _{m=1}^nf(X_m)\longrightarrow \sum _x f(x)\pi (x) \quad \text{quase certamente}. \]

Aperiodicidade não é necessária: médias temporais incorporam ciclos completos. A condição de integrabilidade garante que a recompensa média de uma excursão seja finita. No caso finito, toda função real satisfaz essa condição; no enumerável, ela controla a contribuição dos estados raros à soma.

Demonstração ▼

Fixe um estado \(a\) e ponha \(L=T_a^+\) para uma cadeia iniciada em \(a\). Pelo teorema do retorno, \(\ell =E_aL\lt \infty \).

1. Contagens de ocupação de uma excursão. Retome os pesos

\[ \nu (y)=E_a\sum _{m=0}^{L-1}\mathbf1_{\{ X_m=y\} }. \]

A Proposição 3.7 já mostrou que \(\nu /\ell \) é estacionária. Pela unicidade da distribuição estacionária, concluímos que

\[ \nu (y)=\ell \pi (y). \]

Essa identidade relaciona a ocupação de um ciclo à média em equilíbrio.

2. Recompensa por ciclo e lei forte. Seja \(B=\sum _{m=0}^{L-1}f(X_m)\) a recompensa da excursão e \(C=\sum _{m=0}^{L-1}|f(X_m)|\) sua recompensa absoluta. Ambas são finitas em cada excursão, pois \(L\lt \infty \) e \(f\) assume valores reais. Para calcular suas esperanças, use o conjunto enumerável \(\Gamma \) de excursões, suas probabilidades \(q_\gamma \) e as contagens \(n_y(\gamma )\) da Proposição 3.7. Reagrupando uma série numérica de termos não negativos,

\[ \begin{aligned} E_aC & =\sum _{\gamma \in \Gamma }q_\gamma \sum _y|f(y)|n_y(\gamma )\\ & =\sum _y|f(y)|\sum _{\gamma \in \Gamma }q_\gamma n_y(\gamma )\\ & =\sum _y|f(y)|\nu (y) =\ell \sum _y|f(y)|\pi (y)\lt \infty . \end{aligned} \]

Como \(|B|\leq C\), a recompensa \(B\) tem esperança absoluta finita. O mesmo cálculo com \(f(y)\) no lugar de \(|f(y)|\) agora é permitido pela convergência absoluta da série e dá

\[ E_aB=\sum _y f(y)\nu (y)=\ell \sum _y f(y)\pi (y). \]

Nos ciclos sucessivos, os pares comprimento–recompensa são i.i.d., pela propriedade forte de Markov. Se \(L_k\) e \(B_k\) correspondem ao \(k\)-ésimo ciclo, a lei forte fornece

\[ \frac{B_1+\cdots +B_k}{L_1+\cdots +L_k} =\frac{k^{-1}\sum _{j=1}^k B_j}{k^{-1}\sum _{j=1}^k L_j} \longrightarrow \frac{E_aB}{\ell } =\sum _y f(y)\pi (y). \]

Assim, a recompensa acumulada nos ciclos completos, dividida pelo tempo desses ciclos, converge para a média estacionária.

3. O ciclo incompleto. Resta controlar o pedaço da trajetória que pertence ao último ciclo, ainda não encerrado. Se \(C_k\) é a recompensa absoluta do \(k\)-ésimo ciclo, a integrabilidade implica, para cada \(\varepsilon \gt 0\),

\[ \sum _{k\geq 1}\mathbb {P}(C_k\gt \varepsilon k)\lt \infty . \]

De fato, os \(C_k\) têm a mesma lei que \(C\). Considere a variável inteira não negativa

\[ Z_\varepsilon =\sum _{k\geq 1} \mathbf1_{\{ C\gt \varepsilon k\} }\leq \frac C\varepsilon . \]

Pela fórmula da cauda (Lema 2.13),

\[ \sum _{k\geq 1}\mathbb P(C_k\gt \varepsilon k) =\sum _{k\geq 1}\mathbb P(C\gt \varepsilon k) =EZ_\varepsilon \leq \frac{E_aC}\varepsilon \lt \infty . \]

Não precisamos enumerar novamente as excursões: cada termo conta apenas quantos limiares \(\varepsilon k\) ficam abaixo de \(C\). Pelo primeiro lema de Borel–Cantelli, quando a soma das probabilidades é finita, apenas um número finito desses eventos ocorre, quase certamente. Aplicando isso a \(\varepsilon =1,1/2,1/3,\ldots \) e reunindo os eventos excepcionais, obtemos \(C_k/k\to 0\) quase certamente.

Seja \(K(n)\) o número de ciclos completos até \(n\). Pela inversão das contagens usada no Teorema 3.4, \(K(n)/n\to 1/\ell \). A recompensa ainda não contabilizada está contida no ciclo seguinte e seu módulo é limitado por \(C_{K(n)+1}\). Além disso,

\[ \frac{C_{K(n)+1}}{n} =\frac{C_{K(n)+1}}{K(n)+1}\, \frac{K(n)+1}{n} \longrightarrow 0. \]

O tempo dos ciclos completos, dividido por \(n\), também tende a um, pois

\[ \frac{L_1+\cdots +L_{K(n)}}{n} =\frac{L_1+\cdots +L_{K(n)}}{K(n)}\, \frac{K(n)}n \longrightarrow \ell \, \frac1\ell =1. \]

Combinando essa razão com o limite das recompensas dos ciclos completos e a estimativa do resto, provamos o limite para a média até um instante arbitrário.

Partindo de \(x\ne a\), a primeira chegada a \(a\) ocorre em tempo finito quase certamente. A soma anterior a essa chegada é uma soma finita de valores reais e, dividida por \(n\), desaparece; não precisamos que o tempo dessa primeira chegada tenha esperança finita. Mudar a soma de \(m=0,\ldots ,n-1\) para \(m=1,\ldots ,n\) tampouco altera o limite: \(f(X_0)/n\to 0\), e o termo \(|f(X_n)|/n\) é limitado pela recompensa absoluta, dividida por \(n\), do ciclo que contém o instante \(n\). A estimativa anterior mostra que ele também tende a zero.

Exemplo 3.17 (A loja revisitada: lucro médio observado)

Na loja do Exemplo 3.5, a distribuição estacionária foi calculada como

\[ \pi =\left(\frac1{10},\frac7{20},\frac25,\frac3{20}\right). \]

Resta relacionar o lucro esperado em equilíbrio à média observada em uma trajetória longa. Seja \(D_{n+1}\) a demanda do dia seguinte e defina o número de unidades encomendadas quando o estoque atual é \(i\) por

\[ r(i)=(3-i)\mathbf1_{\{ i\leq 1\} }. \]

O lucro líquido durante o dia \(n+1\) é \(L_{n+1}=5D_{n+1}-2r(X_n)-X_{n+1}\): receita menos compra de reposição e custo de armazenamento do estoque restante. Pelo teorema ergódico,

\[ \frac1n\sum _{k=0}^{n-1}r(X_k) \longrightarrow \sum _i r(i)\pi (i) =3\cdot \frac1{10}+2\cdot \frac7{20}=1 \quad \text{quase certamente}, \]

e a média temporal do estoque converge para

\[ \sum _i i\pi (i)=\frac85. \]

Além disso, as demandas diárias são independentes e têm média \(E(D_n)=1\); pela lei forte dos grandes números, \(n^{-1}\sum _{k=1}^nD_k\to 1\) quase certamente. Combinando essas três médias,

\[ \boxed {\frac1n\sum _{k=1}^{n}L_k \longrightarrow 5\cdot 1-2\cdot 1-\frac85 =\frac75\quad \text{quase certamente}.} \]

A conta anterior de lucro estacionário prevê, portanto, a média efetivamente observada ao longo de uma única operação suficientemente longa.

Teorema 3.12

Convergência de Cesàro Se a cadeia é irredutível e possui distribuição estacionária \(\pi \), então

\[ \frac1n\sum _{m=1}^nP^m(x,y)\longrightarrow \pi (y) \]

para quaisquer \(x,y\), mesmo sem aperiodicidade.

Essa média equivale a observar a cadeia em um instante escolhido uniformemente entre \(1\) e \(n\), independentemente da trajetória. Ela suaviza as oscilações periódicas, sem assegurar a convergência da lei em cada instante.

Demonstração ▼

Pelo teorema ergódico aplicado a \(f=\mathbf1_{\{ y\} }\), temos \(N_n(y)/n\to \pi (y)\) quase certamente sob \(\mathbb {P}_x\). Como essa razão está entre zero e um, o Lema 3.5 garante que suas esperanças convergem para \(\pi (y)\). A esperança é exatamente \(n^{-1}\sum _{m=1}^nP^m(x,y)\).

Exemplo 3.18 (Ehrenfest: cinco leituras do equilíbrio)

Para \(N\geq 1\), Ehrenfest tem distribuição estacionária \(\pi (j)=2^{-N}\binom Nj\) e período dois. Partindo de zero, \(X_n\) tem a mesma paridade de \(n\); logo a lei alterna entre estados pares e ímpares e não converge para \(\pi \).

Na versão preguiçosa, \(\widetilde P=(I+P)/2\): com probabilidade \(1/2\), nada muda; caso contrário, uma bola troca de urna. A mesma \(\pi \) é estacionária, e a permanência positiva torna a cadeia aperiódica. Assim, \(\widetilde P^n(x,j)\to \pi (j)\).

Nas duas versões, as frequências temporais e as médias de Cesàro convergem para \(\pi (j)\). O tempo médio de primeiro retorno também tem a mesma fórmula nas duas cadeias:

\[ E_jT_j^+=\frac{2^N}{\binom Nj}. \]

Na versão preguiçosa, permanecer em \(j\) no primeiro passo já conta como retorno; por isso não devemos simplesmente duplicar essa esperança. Com \(N=4\), os tempos médios de retorno a \(0\) e \(2\) são respectivamente \(16\) e \(8/3\) passos. A média temporal de \(X_n\) converge para \(N/2\) em ambas as versões, embora a lei de Ehrenfest usual continue oscilando.

Ilustração: Recompensas ao longo de uma trajetória

Figura 3.8 Na cadeia de Ehrenfest usual, a lei alterna entre estados pares e ímpares. A versão preguiçosa elimina essa alternância e sua lei converge para \(\pi \). Mesmo na cadeia usual, as frequências de uma trajetória longa se aproximam da distribuição estacionária. Nos quatro painéis, \(N=4\) e \(X_0=0\). A–C mostram leis calculadas; D mostra uma realização da cadeia usual.

3.5 Velocidade de convergência e espectro

Saber que uma cadeia converge não diz quanto devemos esperar. Duas dinâmicas podem ter a mesma distribuição estacionária e conservar a influência do estado inicial por tempos muito diferentes. Precisamos de uma distância entre distribuições e, depois, de uma forma de acompanhar sua redução.

Definição 3.5

Distância de variação total Para distribuições \(\mu ,\nu \) em um espaço finito ou enumerável \(S\), defina

\[ \lVert \mu -\nu \rVert _{\mathrm{TV}} =\frac12\sum _{x\in S}|\mu (x)-\nu (x)|. \]

O fator \(1/2\) evita contar duas vezes a massa que precisa ser redistribuída. Se \(A_+=\{ x:\mu (x)\geq \nu (x)\} \), a soma das diferenças positivas coincide com o módulo da soma das negativas. Portanto,

\[ \lVert \mu -\nu \rVert _{\mathrm{TV}} =\sup _{A\subseteq S}|\mu (A)-\nu (A)|. \]

Assim, a distância é o maior erro na probabilidade de um mesmo evento. Aplicar uma transição comum não aumenta esse erro: a desigualdade triangular e \(\sum _y p(x,y)=1\) dão

\[ \lVert \mu P-\nu P\rVert _{\mathrm{TV}} \leq \lVert \mu -\nu \rVert _{\mathrm{TV}}. \]

Exemplo 3.19 (Dois estados: uma taxa exata)

Considere \(P=\left(\begin{smallmatrix} 1-a & a \\ b & 1-b \end{smallmatrix}\right)\), com \(0\lt a,b\lt 1\), nos estados \(0,1\). Já sabemos que \(\pi =(b/(a+b),a/(a+b))\). Para \(u_n=P^n(0,0)\),

\[ u_{n+1}=b+(1-a-b)u_n, \qquad u_n-\pi (0)=(1-a-b)^n(1-\pi (0)). \]

As diferenças nas duas coordenadas têm sinais opostos; logo

\[ \lVert P^n(0,\cdot )-\pi \rVert _{\mathrm{TV}} =\frac{a}{a+b}|1-a-b|^n. \]

Com \(a=0{,}2\) e \(b=0{,}3\), a distância é \(0{,}4(0{,}5)^n\), igual a \(0{,}05\) em três passos. Com \(a=0{,}02\) e \(b=0{,}03\), a estacionária é a mesma, mas o fator de redução é \(0{,}95\): a mistura é mais lenta. Os autovalores são \(1\) e \(1-a-b\).

Ilustração: Velocidade de convergência e espectro

Figura 3.9 Duas cadeias de dois estados têm a mesma distribuição estacionária, \(\pi =(0{,}6,0{,}4)\), mas se aproximam dela em ritmos diferentes. Partindo de 0, a distância fica menor ou igual a \(0{,}05\) pela primeira vez em 3 e 41 passos, respectivamente. Os valores são definidos em tempos inteiros.

Em cadeias reversíveis, a álgebra linear torna esse mecanismo geral. Aqui restringimos a discussão a um espaço finito com pelo menos dois estados e \(\pi (x)\gt 0\) para todo \(x\). Essa positividade é essencial para que

\[ \langle f,g\rangle _\pi =\sum _x f(x)g(x)\pi (x) \]

seja um produto interno. A norma correspondente é

\[ \lVert f\rVert _{2,\pi }=\left(\sum _x f(x)^2\pi (x)\right)^{1/2}. \]

A matriz também atua sobre funções por \((Pf)(x)=\sum _y p(x,y)f(y)\); isso não muda a convenção de distribuições como vetores-linha.

Observação

Recordação de álgebra linear: o teorema espectral Toda matriz real simétrica \(A\) possui autovalores reais e uma base ortonormal de autovetores \(v_1,\ldots ,v_N\). Se \(Av_k=\lambda _kv_k\) e \(v=\sum _k a_kv_k\), então

\[ A^nv=\sum _k a_k\lambda _k^n v_k. \]

Isso separa a evolução em componentes: cada coordenada na base de autovetores é multiplicada por uma potência do autovalor correspondente. Usaremos esse resultado de álgebra linear, admitido aqui, após transformar a matriz reversível em uma matriz simétrica.

Teorema 3.13

Contração espectral reversível Se \(P\) é uma matriz de transição em um espaço finito com pelo menos dois estados, e a cadeia é irredutível, aperiódica e reversível em relação a \(\pi \), seus autovalores são reais. Podemos enumerá-los como \(\lambda _1=1,\lambda _2,\ldots ,\lambda _{|S|}\). O autovalor \(1\) é simples e, escrevendo

\[ \lambda _* = \max _{k\geq 2}|\lambda _k|\lt 1, \]

temos

\[ \lVert P^n(x,\cdot )-\pi \rVert _{\mathrm{TV}} \leq \frac12\sqrt{\frac1{\pi (x)}-1}\, \lambda _*^n. \]

Cada autovetor descreve uma forma de desequilíbrio, multiplicada pelo seu autovalor a cada passo. O modo constante permanece; os demais desaparecem geometricamente. Um autovalor próximo de \(-1\) também decai devagar, com alternância de sinal: importa o segundo maior módulo, não apenas o segundo maior valor.

Demonstração ▼

Seja \(D\) a matriz diagonal com entradas \(\pi (x)\). Como \(\pi (x)p(x,y)=\pi (y)p(y,x)\), a matriz \(M=D^{1/2}PD^{-1/2}\) é simétrica: suas entradas satisfazem

\[ M_{xy}=\sqrt{\frac{\pi (x)}{\pi (y)}}\, p(x,y)=M_{yx}. \]

Como \(P\mathbf1=\mathbf1\), o vetor

\[ u_1=D^{1/2}\mathbf1 =\bigl(\sqrt{\pi (x)}\bigr)_{x\in S} \]

é um autovetor de \(M\) com autovalor \(1\). Ele tem norma euclidiana igual a \(1\), pois \(\sum _x\pi (x)=1\). Pelo teorema espectral, podemos completá-lo em uma base ortonormal \(u_1,\ldots ,u_{|S|}\) de autovetores reais de \(M\). Se \(Mu_k=\lambda _k u_k\), defina \(f_k=D^{-1/2}u_k\). Então

\[ Pf_k=D^{-1/2}Mu_k=\lambda _k f_k, \qquad \langle f_j,f_k\rangle _\pi =\langle D^{1/2}f_j,D^{1/2}f_k\rangle _2 =\langle u_j,u_k\rangle _2=\delta _{jk}. \]

Portanto, os \(f_k\) formam uma base ortonormal para o produto interno ponderado por \(\pi \), e \(f_1=\mathbf1\). Para \(k\geq 2\), a ortogonalidade dá

\[ \pi (f_k):=\sum _x\pi (x)f_k(x) =\langle f_k,\mathbf1\rangle _\pi =0. \]

Pelo teorema de convergência das cadeias finitas irredutíveis e aperiódicas, para cada estado \(x\),

\[ P^n f_k(x)\longrightarrow \pi (f_k)=0. \]

Por outro lado, \(Pf_k=\lambda _k f_k\) implica \(P^n f_k=\lambda _k^n f_k\). Como \(f_k\) não é a função nula, isso só é possível se \(|\lambda _k|\lt 1\). Assim, os modos não constantes desaparecem geometricamente e o autovalor \(1\) é simples.

A densidade da massa inicial em \(x\), em relação a \(\pi \), é \(h_0(y)=\mathbf1_{\{ y=x\} }/\pi (x)\). Pela definição de \(P\) agindo sobre funções,

\[ (P^nh_0)(y)=\sum _zP^n(y,z)h_0(z) =\frac{P^n(y,x)}{\pi (x)} =\frac{P^n(x,y)}{\pi (y)}=:h_n(y). \]

A última igualdade é o balanço detalhado em \(n\) passos. Com efeito,

\[ D^{1/2}P^nD^{-1/2}=M^n, \]

e \(M^n\) também é simétrica, pois \(M\) é simétrica. Portanto, \(\pi (y)P^n(y,x)=\pi (x)P^n(x,y)\). Além disso, \(\langle h_0-1,\mathbf1\rangle _\pi =0\) e \(P\mathbf1=\mathbf1\). A expansão nessa base de autovetores fornece, então,

\[ \lVert h_n-1\rVert _{2,\pi } \leq \lambda _*^n\lVert h_0-1\rVert _{2,\pi }, \qquad \lVert h_0-1\rVert _{2,\pi }^2=\frac1{\pi (x)}-1. \]

Finalmente, Cauchy–Schwarz dá

\[ \sum _y\pi (y)|h_n(y)-1| =\langle |h_n-1|,\mathbf1\rangle _\pi \leq \lVert h_n-1\rVert _{2,\pi }\lVert \mathbf1\rVert _{2,\pi } =\lVert h_n-1\rVert _{2,\pi }, \]

pois \(\sum _y\pi (y)=1\). Como \(\lVert P^n(x,\cdot )-\pi \rVert _{\mathrm{TV}}\) é metade dessa soma, obtemos a cota anunciada.

Exemplo 3.20 (Três estados e dois ritmos de esquecimento)

No caminho \(1\)–\(2\)–\(3\), tome

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

A simetria dá \(\pi =(1/3,1/3,1/3)\). Como \(P\) é simétrica, seus autovetores à direita também são autovetores à esquerda, e podemos decompor vetores-linha na mesma base. Os vetores \((1,1,1)\), \((1,0,-1)\) e \((1,-2,1)\) têm autovalores \(1\), \(3/4\) e \(1/4\), respectivamente. Como

\[ (1,0,0)=\tfrac 13(1,1,1)+\tfrac 12(1,0,-1)+\tfrac 16(1,-2,1), \]

segue que

\[ \begin{aligned} P^n(1,\cdot )-\pi ={}& \tfrac 12(3/4)^n(1,0,-1)\\ & +\tfrac 16(1/4)^n(1,-2,1). \end{aligned} \]

A primeira coordenada é positiva e as outras duas são não positivas; portanto,

\[ \lVert P^n(1,\cdot )-\pi \rVert _{\mathrm{TV}} =\tfrac 12(3/4)^n+\tfrac 16(1/4)^n. \]

Em dois passos, a distância é \(7/24\approx 0{,}2917\). Para tempos grandes, domina o modo de autovalor \(3/4\).

A existência de \(\pi \), a convergência para \(\pi \) e a velocidade dessa convergência respondem a três perguntas diferentes. A lacuna espectral absoluta, também chamada de gap espectral absoluto (absolute spectral gap), \(1-\lambda _*\), controla o decaimento do modo não constante mais lento no caso reversível. Uma distribuição inicial pode não ter componente nesse modo e convergir mais depressa. A versão preguiçosa \((I+P)/2\) transforma cada autovalor \(\lambda \) em \((1+\lambda )/2\) e elimina autovalores negativos, mas pode desacelerar modos positivos. No capítulo de MCMC, essa discussão reaparecerá como tempo de mistura e diagnóstico de simulações.

3.6 Problemas de síntese

As urnas de Ehrenfest, uma fila de atendimento e um ábaco probabilístico oferecem três leituras do equilíbrio: a reversibilidade do tempo, os fluxos de entrada e saída e a conservação de massa.

Exemplo 3.21 (Conseguimos reconhecer um filme exibido ao contrário?)

Voltemos à cadeia de Ehrenfest do Exemplo 2.3. Há \(N\) bolas distribuídas entre duas urnas e, a cada passo, uma delas troca de urna.

Ilustração: Problemas de síntese

Figura 3.10 Uma representação das duas urnas de Ehrenfest. No modelo, as bolas passam de uma urna para a outra, e a cadeia acompanha a quantidade presente na primeira.

Se \(X_n=i\) bolas estão na primeira, então

\[ p(i,i+1)=\frac{N-i}{N},\qquad p(i,i-1)=\frac iN. \]

Já encontramos a distribuição estacionária binomial \(\pi (i)=2^{-N}\binom Ni\). Seria possível assistir a um filme curto do sistema em equilíbrio e descobrir se ele foi exibido no sentido correto?

Figura não resolvida: figuras/ehrenfest-filme.tikz

Figura 3.11 Uma trajetória ilustrativa para \(N=4\) e as mesmas observações na ordem inversa. A reversibilidade afirma igualdade das probabilidades das duas sequências em equilíbrio, não que uma realização seja literalmente simétrica.

O balanço detalhado responde à pergunta. De fato,

\[ \begin{aligned} \pi (i)p(i,i+1) & =2^{-N}\binom Ni\frac{N-i}{N}\\ & =2^{-N}\binom N{i+1}\frac{i+1}{N} =\pi (i+1)p(i+1,i). \end{aligned} \]

Para qualquer sequência admissível \(x_0,x_1,\ldots ,x_m\), aplicar essa igualdade em todas as transições e cancelar os termos intermediários dá

\[ \pi (x_0)\prod _{k=0}^{m-1}p(x_k,x_{k+1}) = \pi (x_m)\prod _{k=0}^{m-1}p(x_{k+1},x_k). \]

Portanto, em equilíbrio, uma sequência e a sequência reversa têm exatamente a mesma probabilidade. Nenhum teste baseado apenas nesse filme pode distinguir estatisticamente os dois sentidos do tempo.

Isso não vale para toda cadeia estacionária: no triângulo do Exemplo 3.8, quando \(a\ne 1/2\), as circulações em sentidos opostos possuem probabilidades diferentes.

Exemplo 3.22 (Uma fila que não se denuncia pelo som)

Retomemos a fila do Exemplo 3.10. A cada instante há uma chegada com probabilidade \(p=2/5\), ou uma oportunidade de atendimento com probabilidade \(q=3/5\); se a fila está vazia, essa última possibilidade não muda o estado.

Ilustração: Problemas de síntese

Figura 3.12 Uma fila com um único posto de atendimento. As transições do modelo estão na Figura 3.3.

Já calculamos sua distribuição estacionária,

\[ \pi (i)=\frac13\left(\frac23\right)^i,\qquad i\geq 0, \]

e verificamos o balanço detalhado \(\pi (i)p=\pi (i+1)q\). Portanto, a fila é reversível. Daqui em diante, supomos \(X_0\sim \pi \), ou seja, observamos a fila em equilíbrio.

Imagine agora que ouvimos um bipe para cada chegada, um clique para cada atendimento efetivo e silêncio quando há oportunidade de atendimento com a fila vazia. Os bipes formam uma sequência de indicadores independentes Bernoulli com parâmetro \(p\), pela própria construção.

Para estudar os cliques, usamos a reversibilidade. Ao inverter um filme da fila em equilíbrio, cada salto para baixo se torna um salto para cima. Pela reversibilidade, a sequência de saltos para baixo lida para trás tem a mesma lei que a sequência de saltos para cima lida para a frente. Como uma sequência de variáveis independentes continua independente quando sua ordem é invertida, os indicadores dos atendimentos efetivos também são independentes Bernoulli com parâmetro \(p\). Assim, em equilíbrio,

\[ \mathbb P(\text{nenhum atendimento nos próximos três passos}) =(1-p)^3=\frac{27}{125}, \]

e o tempo entre atendimentos consecutivos tem distribuição geométrica com esperança \(1/p=5/2\).

Quando há alguém na fila, a chance de atendimento no próximo passo é \(q=3/5\), enquanto a probabilidade de atendimento em equilíbrio é \(p=2/5\). A segunda leva em conta também os instantes em que a fila está vazia. Em tempo contínuo, o resultado correspondente é conhecido como teorema de Burke: numa fila M/M/1 estável e em equilíbrio, as saídas formam um processo de Poisson com a mesma taxa das chegadas.

Exemplo 3.23 (Um ábaco que calcula uma distribuição estacionária)

Duas crianças possuem fichas. Em cada rodada, a primeira distribui metade de suas fichas para si e metade para a segunda; a segunda envia um quarto para a primeira e conserva três quartos.

Ilustração: Problemas de síntese

Figura 3.13 Uma imagem da redistribuição de fichas entre duas crianças. O diagrama de transição abaixo especifica exatamente as frações transferidas em cada rodada.

A regra é dada pela matriz

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

Figura não resolvida: figuras/abaco-probabilistico.tikz

Figura 3.14 Cada criança redistribui suas fichas segundo a linha correspondente de \(P\); as setas representam transferências, não sorteios.

Para todas as divisões produzirem números inteiros, antes de cada rodada a professora completa o estoque da primeira criança até o menor múltiplo de \(2\) maior ou igual à quantidade atual, e o da segunda até o menor múltiplo de \(4\) maior ou igual à sua quantidade. Em seguida, as duas crianças redistribuem simultaneamente as fichas, calculando suas transferências a partir dos estoques já repostos. Começando com \((3,1)\), a evolução é

\[ \begin{array}{c|c|c} \text{antes da reposição}& \text{depois da reposição}& \text{depois da distribuição}\\ \hline (3,1)& (4,4)& (3,5)\\ (3,5)& (4,8)& (4,8)\\ (4,8)& (4,8)& (4,8) \end{array} \]

Por exemplo, na primeira rodada, a criança 1 recebe \(2\) fichas de si mesma e \(1\) da outra, ficando com \(3\); a segunda recebe \(2+3=5\). Depois da segunda rodada, \((4,8)\) já é preservado:

\[ (4,8)P=(4,8). \]

Normalizando o número de fichas, obtemos

\[ \boxed {\pi =\left(\frac13,\frac23\right),\qquad \pi P=\pi .} \]

A redistribuição fornece a mesma proporção que o balanço detalhado, \(\pi (1)/2=\pi (2)/4\).

Esse procedimento é uma versão do ábaco probabilístico: a conservação e a redistribuição de massa permitem encontrar um vetor estacionário. Há algoritmos semelhantes para outras matrizes racionais, cuja terminação exige argumentos adicionais.

Filmes invertidos, atendimentos e fichas redistribuídas traduzem a preservação de massa expressa por \(\pi P=\pi \) em situações distintas.

3.7 PageRank e centralidade^*

Os links que apontam para uma página permitem atribuir-lhe uma medida de importância. Representamos essas ligações por um grafo dirigido: escrevemos \(A_{ij}=1\) quando há um link da página \(i\) para a página \(j\), e \(A_{ij}=0\) caso contrário.

A centralidade por grau de entrada atribui a \(j\) o valor \(d_j^{\mathrm{in}}=\sum _i A_{ij}\). Essa contagem trata todos os links recebidos da mesma maneira: dez links de páginas pouco citadas valem tanto quanto dez links de páginas muito citadas.

A centralidade de autovetor procura pesos não negativos \(c_j\) tais que a importância de \(j\) seja proporcional à soma das importâncias de quem a cita:

\[ c_j=\frac1\kappa \sum _i c_iA_{ij}, \qquad \text{ou, com vetores-linha,}\qquad cA=\kappa c. \]

Mesmo quando existe um vetor estritamente positivo, multiplicá-lo por uma constante positiva preserva a equação. A unicidade deve, portanto, ser entendida a menos desse fator ou depois de uma normalização, como \(\sum _jc_j=1\). Sua existência e unicidade dependem de condições sobre o grafo. Há ainda outra decisão: uma página deve transmitir sua importância inteira por cada link ou repartir um total entre todos os links que oferece?

O passeio aleatório adota a segunda opção. Se \(d_i^{\mathrm{out}}=\sum _j A_{ij}\gt 0\), faça

\[ p(i,j)=\frac{A_{ij}}{d_i^{\mathrm{out}}}. \]

Um visitante escolhe uniformemente um dos links da página atual. Páginas sem saída deixam uma linha por definir; classes fechadas podem aprisionar o passeio e tornar o resultado dependente do ponto de partida.

Definição 3.6

Teletransporte e vetor de PageRank Escolha uma distribuição \(v\), representada por um vetor-linha, com \(v(i)\gt 0\) e \(\sum _i v(i)=1\). Ela determina o destino do teletransporte. Complete cada linha sem saída de \(P\) com \(v\) e defina

\[ G=\alpha P+(1-\alpha )\mathbf1v, \qquad 0\lt \alpha \lt 1, \]

onde \(\mathbf1\) é a coluna de uns. Em cada passo, seguimos \(P\) com probabilidade \(\alpha \) e escolhemos um novo destino segundo \(v\) com probabilidade \(1-\alpha \). O vetor de PageRank é a distribuição \(\pi \) que satisfaz

\[ \pi G=\pi ,\qquad \sum _i\pi (i)=1. \]

Proposição 3.14

Um equilíbrio único e alcançável Em um grafo finito, com \(v(i)\gt 0\) para todo \(i\), \(G\) possui uma única distribuição estacionária \(\pi \), e \(\mu _0G^n\to \pi \) para toda distribuição inicial \(\mu _0\).

Demonstração ▼

Cada entrada satisfaz \(G_{ij}\geq (1-\alpha )v(j)\gt 0\). Portanto, a cadeia é irredutível e aperiódica. Como o espaço é finito, existe uma distribuição estacionária pela Proposição 3.1. A unicidade e a convergência seguem dos Teoremas 3.6 e 3.10.

Exemplo 3.24 (Quatro páginas e uma página sem saída)

Considere os links da Figura 3.15. Os graus de entrada de \(A,B,C,D\) são \((1,1,2,0)\). A página \(D\) não tem links; \(\{ A,B,C\} \) é uma classe fechada da cadeia original.

Figura 3.15 Links entre quatro páginas; a página D não possui links de saída.

Com \(v(i)=1/4\) e \(\alpha =4/5\), na ordem \(A,B,C,D\),

\[ P=\begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 \end{pmatrix},\qquad G=\frac1{20}\begin{pmatrix} 1 & 9 & 9 & 1 \\ 1 & 1 & 17 & 1 \\ 17 & 1 & 1 & 1 \\ 5 & 5 & 5 & 5 \end{pmatrix}. \]

A última linha de \(P\) é a convenção para páginas sem saída, não um conjunto de links observados. Partindo de \(\mu _0=(1/4,1/4,1/4,1/4)\) e iterando \(\mu _{n+1}=\mu _nG\), obtemos

\[ \begin{array}{c|rrrr} n& A& B& C& D\\ \hline 1& 0{,}3000& 0{,}2000& 0{,}4000& 0{,}1000\\ 2& 0{,}3900& 0{,}1900& 0{,}3500& 0{,}0700\\ 3& 0{,}3440& 0{,}2200& 0{,}3720& 0{,}0640\\ 10& 0{,}3600& 0{,}2062& 0{,}3713& 0{,}0625 \end{array}. \]

Embora \(A\) e \(B\) tenham o mesmo grau de entrada, \(A\) recebe todo o fluxo de links de \(C\), enquanto \(B\) recebe apenas metade do fluxo de \(A\). O ranking incorpora essa diferença que o grau não enxerga.

Heurística

A síntese PageRank é uma centralidade de autovetor regularizada por teletransporte. A equação de autovetor agora usa a matriz estocástica \(G\) e o autovalor \(1\).

Os dados observados são as páginas e seus links em uma coleta datada; a matriz é construída dessa coleta, enquanto \(\alpha \) e \(v\) são escolhas do modelo. Se o objetivo fosse descrever navegação real, poderíamos comparar frequências de visitas em sessões reservadas com as previstas, ou estimar as transições pelos cliques observados. Links e cliques são fontes de dados distintas. A formulação original é de Page et al. (1999).

O ranking depende de \(\alpha \), da personalização em \(v\) e de como tratamos as páginas sem saída. Essas escolhas importam, sobretudo quando a rede contém estruturas criadas para manipular os resultados, como fazendas de links: o teletransporte reduz certos efeitos, mas não impede a manipulação. Por isso, convém comparar os rankings obtidos com parâmetros próximos e com novas coletas. A centralidade descreve a posição de uma página na rede segundo um modelo; ela não é, por si só, uma medida universal de qualidade ou relevância.

3.8 Otimização por colônias de formigas^*

Até aqui, as probabilidades de transição foram dadas de antemão. Nos algoritmos de colônias de formigas, as próprias trajetórias modificam as escolhas futuras por meio do reforço de feromônio. Esse mecanismo aproxima cadeias de Markov, urnas reforçadas e otimização. Acompanharemos a escolha do estado, o exemplo com dois caminhos, a cota produzida pela evaporação e a discussão sobre exploração. Sem evaporação, o reforço leva a resultados de convergência surpreendentes: serão enunciados aqui e demonstrados no capítulo de martingais, que dispõe das ferramentas necessárias. Ao final, voltaremos à ciência de dados com uma aplicação à seleção de variáveis.

Uma colônia de formigas pode encontrar um caminho curto entre o formigueiro e uma fonte de alimento sem que nenhuma formiga conheça o mapa completo. Cada indivíduo toma decisões locais, mas deixa no ambiente uma informação que altera as decisões dos indivíduos seguintes: o feromônio. Caminhos percorridos com frequência recebem novos depósitos; caminhos pouco usados perdem feromônio por evaporação. A combinação dessas duas regras produz uma forma simples de memória coletiva.

Os algoritmos de otimização por colônias de formigas abstraem esse mecanismo para procurar boas soluções de problemas combinatórios Dorigo et al. 1996; Dorigo e Stützle 2004. A estrutura probabilística do algoritmo é a seguinte: uma distribuição é usada para construir uma solução aleatória, a qualidade da solução modifica essa distribuição e o procedimento se repete. Assim, o algoritmo fornece um exemplo concreto de processo estocástico com realimentação.

3.8.1 Escolhas aleatórias guiadas pelo feromônio

Considere um grafo finito. A cada aresta \(e\) associamos duas quantidades positivas. O valor \(\tau _e(n)\) representa o feromônio presente na aresta no início da iteração \(n\), enquanto \(\eta _e\) mede sua atratividade definida pelo problema. Em uma aplicação de caminhos mínimos, é comum tomar \(\eta _e=1/\ell _e\), em que \(\ell _e\) é o comprimento da aresta.

Se uma formiga está em um vértice \(v\) e pode escolher uma aresta no conjunto \(A(v)\), a regra usual atribui a \(e\in A(v)\) a probabilidade

\begin{equation} p_n(e\mid v) = \frac{\tau _e(n)^\alpha \eta _e^\beta }{\displaystyle \sum _{f\in A(v)} \tau _f(n)^\alpha \eta _f^\beta }. \label{eq:formigas-regra-escolha} \tag{3.4} \end{equation}

Aqui, \(\alpha \geq 0\) controla a influência do histórico acumulado no feromônio, e \(\beta \geq 0\) controla a influência da informação heurística. Valores grandes de \(\alpha \) tornam o algoritmo mais sensível às escolhas anteriores; valores grandes de \(\beta \) favorecem fortemente as arestas que já parecem vantajosas.

Depois que a formiga completa um caminho \(R_{n+1}\) de custo \(L(R_{n+1})\), uma regra simples de atualização é

\begin{equation} \tau _e(n+1) =(1-\delta )\tau _e(n) +\frac{Q}{L(R_{n+1})}\, \mathbf1_{\{ e\in R_{n+1}\} }, \qquad 0\leq \delta \lt 1, \label{eq:formigas-atualizacao} \tag{3.5} \end{equation}

em que \(Q\gt 0\). O fator \(1-\delta \) representa a evaporação, e o segundo termo reforça as arestas que participaram da solução construída. Como o depósito é inversamente proporcional ao custo total, soluções melhores deixam marcas mais fortes. Nas implementações com várias formigas por iteração, basta somar os depósitos produzidos por elas.

Proposição 3.15

A escolha correta do estado Fixe o grafo, as heurísticas, os custos e os parâmetros. Suponha que cada iteração reinicie o mesmo procedimento de construção dos caminhos, conservando da iteração anterior apenas os feromônios, e que os caminhos sejam concluídos em um número finito de escolhas. As decisões seguem (3.4), com números aleatórios novos, independentes dos empregados anteriormente. Observado apenas nos instantes entre duas iterações, o vetor de feromônios

\[ X_n=(\tau _e(n):e\in E) \]

é uma cadeia de Markov.

Demonstração ▼

Reúna em \(U_{n+1}\) os números aleatórios usados na próxima iteração. Conhecidos \(X_n\) e \(U_{n+1}\), o procedimento determina os caminhos e a atualização dos feromônios. Podemos, portanto, escrever

\[ X_{n+1}=F(X_n,U_{n+1}), \]

com a mesma regra \(F\) em todas as iterações. Como os números em \(U_{n+1}\) são independentes do passado e têm sempre a mesma distribuição, conhecer os feromônios anteriores não acrescenta informação sobre \(X_{n+1}\) quando \(X_n\) já é conhecido. Essa é a propriedade de Markov.

Durante a construção de um caminho, a posição da formiga pode não ser um estado suficiente. No problema do caixeiro-viajante, por exemplo, também precisamos registrar as cidades já visitadas. A propriedade de Markov depende, portanto, da informação escolhida para formar o estado.

3.8.2 Um modelo com dois caminhos

Considere dois caminhos entre o formigueiro e o alimento, com comprimentos \(L_1\) e \(L_2\). Em cada iteração, uma formiga escolhe um dos caminhos por inteiro. Denotando essa escolha por \(J_{n+1}\in \{ 1,2\} \), escrevemos \(\mathcal H_n\) para o histórico da colônia até a iteração \(n\), incluindo os feromônios e as escolhas já realizadas. Estudaremos a regra

\begin{equation} \mathbb {P}(J_{n+1}=i\mid \mathcal H_n) =\frac{\tau _i(n)}{\tau _1(n)+\tau _2(n)}, \qquad i=1,2, \label{eq:formigas-dois-caminhos} \tag{3.6} \end{equation}

e a atualização

\begin{equation} \tau _i(n+1) =(1-\delta )\tau _i(n) +q_i\mathbf1_{\{ J_{n+1}=i\} }, \qquad q_i=\frac{Q}{L_i}. \label{eq:formigas-dois-caminhos-atualizacao} \tag{3.7} \end{equation}

Esse é o caso \(\alpha =1\) e \(\beta =0\). A simplificação retira a preferência explícita pelo comprimento da regra de escolha. Mesmo assim, o comprimento entra no algoritmo por meio do reforço \(q_i\): uma passagem pelo caminho menor produz um depósito maior.

Figura 3.16 Dois caminhos competem pela próxima escolha. O estado registra o feromônio acumulado em cada um deles.

Exemplo 3.25 (Uma primeira atualização)

Suponha que \(L_1=2\), \(L_2=4\), \(Q=1\), \(\delta =0{,}1\) e \(\tau _1(0)=\tau _2(0)=1\). Inicialmente, cada caminho é escolhido com probabilidade \(1/2\). Se a primeira formiga escolhe o caminho 1, então

\[ \tau _1(1)=0{,}9+\frac12=1{,}4, \qquad \tau _2(1)=0{,}9. \]

Consequentemente, a probabilidade de a segunda formiga escolher o mesmo caminho é

\[ \frac{1{,}4}{1{,}4+0{,}9} =\frac{14}{23}\approx 0{,}609. \]

Uma única escolha já altera a distribuição da escolha seguinte. Se a segunda formiga também usar o caminho 1, o reforço será novamente \(1/2\); uma passagem pelo caminho 2 produziria apenas \(1/4\) de unidade de feromônio.

O próximo resultado mostra que a evaporação impede o crescimento ilimitado do feromônio.

Proposição 3.16

Limitação produzida pela evaporação Se \(0\lt \delta \lt 1\), então, para \(i=1,2\),

\begin{equation} \tau _i(n) \leq (1-\delta )^n\tau _i(0) +\frac{q_i}{\delta }\bigl(1-(1-\delta )^n\bigr). \label{eq:formigas-cota-feromonio} \tag{3.8} \end{equation}

Em particular,

\[ \tau _i(n)\leq \max \left\{ \tau _i(0),\frac{q_i}{\delta }\right\} \qquad \text{para todo }n. \]

Demonstração ▼

Da regra de atualização e do fato de que o indicador é no máximo um,

\[ \tau _i(n+1)\leq (1-\delta )\tau _i(n)+q_i. \]

Iterando essa desigualdade e somando a progressão geométrica, obtemos (3.8).

A fórmula também esclarece o papel de \(\delta \). Um depósito feito \(k\) iterações antes é multiplicado por \((1-\delta )^k\), aproximadamente \(e^{-\delta k}\) quando \(\delta \) é pequeno. Assim, \(1/\delta \) fornece uma escala aproximada para o alcance da memória do algoritmo.

3.8.3 Sem evaporação: reforço e seleção

Suponha inicialmente que os dois caminhos recebam o mesmo reforço \(q\gt 0\) e que não haja evaporação. A atualização torna-se

\[ \tau _i(n+1)=\tau _i(n)+q\mathbf1_{\{ J_{n+1}=i\} }. \]

Dividindo os feromônios por \(q\), reconhecemos uma urna de Pólya: a escolha de uma cor aumenta sua chance de ser escolhida novamente. A proporção

\[ Z_n=\frac{\tau _1(n)}{\tau _1(n)+\tau _2(n)} \]

converge quase certamente, mas não necessariamente para \(1/2\). Se \(\tau _1(0)=\tau _2(0)=q\), seu limite \(Z_\infty \) é uniforme em \([0,1]\). Em particular,

\[ \mathbb P(Z_\infty \gt 0{,}9)=0{,}1. \]

Mesmo com regras simétricas, as flutuações iniciais podem deixar uma preferência persistente. A demonstração e a lei Beta para feromônios iniciais gerais aparecerão no capítulo de martingais.

Voltemos agora a \(q_i=Q/L_i\). Se \(L_1\lt L_2\), cada passagem pelo primeiro caminho deposita mais feromônio do que uma passagem pelo segundo. No modelo sem evaporação, essa vantagem determina a preferência assintótica.

Teorema 3.17

Seleção assintótica do caminho menor Considere o modelo de dois caminhos sem evaporação, com feromônios iniciais positivos. Se \(L_1\lt L_2\), então

\[ Z_n\longrightarrow 1 \qquad \text{quase certamente}. \]

Portanto, a proporção do feromônio localizada no caminho menor converge a um, embora cada escolha individual continue sendo aleatória.

A demonstração, baseada na comparação de processos de nascimento em tempo contínuo, será apresentada no capítulo de martingais, juntamente com a análise da deriva de \(Z_n\). O contraste entre os modelos é o seguinte: reforços iguais produzem um limite aleatório, enquanto um reforço estritamente maior leva a uma preferência assintótica pelo caminho menor.

3.8.4 Exploração e concentração prematura

O teorema anterior favorece o caminho correto no modelo idealizado, mas também expõe um risco dos algoritmos reforçados. Se uma solução recebe muito feromônio por acaso nas primeiras iterações, sua probabilidade pode crescer antes que outras regiões tenham sido suficientemente exploradas. Além disso, a evaporação, sozinha, não garante exploração: o feromônio de um caminho nunca escolhido pode decair para valores próximos de zero.

Uma proteção comum consiste em restringir o feromônio a um intervalo \([\tau _{\min },\tau _{\max }]\), com \(0\lt \tau _{\min }\lt \tau _{\max }\lt \infty \). Depois de aplicar (3.5), valores abaixo ou acima desses limites são truncados.

Proposição 3.18

Exploração persistente Suponha que \(\tau _{\min }\leq \tau _i(n)\leq \tau _{\max }\) para \(i=1,2\) e todo \(n\). Sob a regra de escolha proporcional ao feromônio,

\[ \mathbb {P}(J_{n+1}=i\mid \mathcal H_n) \geq \varepsilon , \qquad \varepsilon =\frac{\tau _{\min }}{2\tau _{\max }}\gt 0. \]

Consequentemente, cada caminho é escolhido infinitas vezes com probabilidade um.

Demonstração ▼

Como o numerador é pelo menos \(\tau _{\min }\) e o denominador é no máximo \(2\tau _{\max }\), obtemos a cota uniforme. Condicionado a qualquer história, a probabilidade de evitar o caminho \(i\) durante as próximas \(r\) escolhas é no máximo \((1-\varepsilon )^r\). Fazendo \(r\to \infty \), concluímos que a probabilidade de nunca mais escolher esse caminho é zero. Como isso vale após qualquer instante, o caminho é escolhido infinitas vezes quase certamente.

Os limites fixos preservam a exploração, mas alteram o comportamento assintótico. Com eles,

\[ Z_n\leq \frac{\tau _{\max }}{\tau _{\max }+\tau _{\min }}\lt 1, \]

de modo que o teorema de seleção do caminho menor, enunciado sem truncamento, não se aplica a essa nova regra. O caso sem evaporação torna a diferença particularmente clara: cada visita acrescenta \(q_i\gt 0\) até atingir \(\tau _{\max }\). Como cada caminho é visitado infinitas vezes, ambos os feromônios atingem esse teto em tempo finito quase certamente. A partir daí, as escolhas têm probabilidade \(1/2\), mesmo que os comprimentos sejam diferentes.

Com evaporação, o feromônio pode diminuir entre depósitos e deixar de ficar preso ao teto. Ainda assim, a proposição garante exploração, não seleção do ótimo. O reforço favorece as decisões recompensadas, enquanto os limites impedem que as demais sejam abandonadas. Essa tensão é uma versão do compromisso entre exploração e aproveitamento que aparece em aprendizado de máquina e em algoritmos sequenciais de decisão.

3.8.5 Uma aplicação em ciência de dados: seleção de variáveis

Suponha que desejemos ajustar um modelo preditivo usando apenas algumas das variáveis \(x_1,\ldots ,x_d\). Cada candidato é representado por \(z=(z_1,\ldots ,z_d)\in \{ 0,1\} ^d\): na etapa \(j\), a formiga decide incluir (\(z_j=1\)) ou excluir (\(z_j=0\)) a variável. Associamos feromônios \(\tau _{j,1}\) e \(\tau _{j,0}\) a essas duas decisões. A regra (3.4) torna-se

\[ \mathbb P(z_j=b\mid \text{decisões anteriores}) =\frac{\tau _{j,b}^{\alpha }\eta _{j,b}^{\beta }}{\tau _{j,0}^{\alpha }\eta _{j,0}^{\beta } +\tau _{j,1}^{\alpha }\eta _{j,1}^{\beta }}, \qquad b\in \{ 0,1\} . \]

Podemos tomar \(\eta _{j,b}=1\) ou utilizar informação heurística calculada com os dados de treinamento.

O subconjunto selecionado é \(S(z)=\{ j:z_j=1\} \). Ajustamos o modelo usando essas variáveis e avaliamos, por exemplo, o custo

\begin{equation} C(S)=\widehat R_{\mathrm{val}}(S)+\lambda \frac{|S|}{d}, \label{eq:formigas-selecao-variaveis} \tag{3.9} \end{equation}

onde \(\widehat R_{\mathrm{val}}(S)\) é o erro de validação e \(\lambda \geq 0\) penaliza subconjuntos grandes. As decisões do caminho recebem depósitos proporcionais a \(Q/(\varepsilon +C(S))\), com \(\varepsilon \gt 0\), favorecendo candidatos de menor custo.

O erro usado para selecionar as variáveis não é uma avaliação independente da solução final: consultas repetidas podem ajustar a busca às particularidades da validação. Um conjunto de teste separado, consultado apenas ao final, permite avaliá-la.

O vetor dos \(2d\) feromônios é o estado de Markov entre iterações, desde que a avaliação seja fixa e novos sorteios independentes sejam utilizados em cada passo. Se todos os feromônios ficam entre limites uniformes positivos, as heurísticas são positivas e \(\alpha ,\beta \) são fixos, cada decisão tem probabilidade uniformemente positiva. Como cada candidato requer apenas \(d\) decisões, nenhum subconjunto é abandonado para sempre. Isso garante exploração, mas não assegura a seleção do melhor subconjunto.

O algoritmo admite diversas variantes: várias formigas por iteração, reforço apenas da melhor solução ou busca local. A escolha de um estado suficiente, a memória produzida pelo reforço e a distinção entre exploração e seleção do ótimo permanecem centrais nessas variantes.

3.9 Exercícios

Os exercícios retomam distribuições estacionárias, periodicidade, balanço detalhado, acoplamento e médias temporais.

Exercício 3.1

Acoplar e acompanhar uma média Considere a cadeia nos estados \(\{ 0,1\} \) com

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

Determine sua distribuição estacionária. Se o custo de um passo é \(c(0)=1\) e \(c(1)=4\), calcule o limite quase certo da média temporal dos custos, qualquer que seja o estado inicial. Compare-o com \(E_0[c(X_1)]\).

Para quantificar o esquecimento da partida, construa duas cópias usando a mesma sequência de uniformes \(U_n\): do estado \(0\), o próximo estado é \(1\) se \(U_n\leq 1/4\); do estado \(1\), é \(1\) se \(U_n\leq 1/2\). Comece com \(X_0=0\) e \(Y_0\) distribuído segundo a estacionária, independentemente das uniformes. Se \(T\) é o primeiro encontro, mostre que

\[ \mathbb P(T\gt n)=\frac13\left(\frac14\right)^n \]

e obtenha uma cota para \(\| P^n(0,\cdot )-\pi \| _{\mathrm{TV}}\).

Exercício 3.2

Classes, períodos e estacionárias Na ordem \(1,\ldots ,5\), considere

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

Identifique as classes de comunicação, quais são fechadas, a classificação dos estados e seus períodos. Determine todas as distribuições estacionárias. Por que a lei iniciada em \(1\) não converge, embora existam estacionárias?

Exercício 3.3

Passeio em um caminho Em um grafo com arestas \(\{ 1,2\} \), \(\{ 2,3\} \) e \(\{ 3,4\} \), escolha uniformemente um vizinho em cada passo. Calcule a estacionária, verifique o balanço detalhado, determine o período e os tempos médios de retorno a \(1\) e \(2\). O que muda para \(\widetilde P=(I+P)/2\)?

Exercício 3.4

O estado inicial pode eliminar o modo lento Na cadeia de três estados do Exemplo 3.20, comece no estado \(2\). Decomponha \((0,1,0)\) nos autovetores apresentados, calcule exatamente a distância de variação total depois de \(n\) passos e encontre o primeiro \(n\) para o qual ela é no máximo \(0{,}02\). Compare com a partida em \(1\).

Exercício 3.5

Trocas entre duas urnas Três bolas pretas e três brancas estão divididas entre duas urnas com três bolas cada. Em cada passo, escolha uma bola de cada urna, independentemente e de maneira uniforme, e troque-as. Seja \(X_n\) o número de bolas pretas na primeira urna. Determine as transições e verifique que a distribuição estacionária é

\[ \pi (i)=\frac{\binom 3i^2}{\binom 63},\qquad 0\leq i\leq 3. \]

Dê também uma explicação por contagem de configurações.

3.10 Exercícios complementares^*

Exercício 3.6

Cálculo do equilíbrio^* Confira a segunda linha da tabela de iterações da Seção 3.7. Resolva \(\pi G=\pi \) com normalização e compare sua resposta com a décima iteração.

Exercício 3.7

Os extremos do teletransporte^* O que ocorre com \(G\) e \(\pi \) quando \(\alpha =0\)? Dê um grafo de dois vértices para o qual \(\alpha =1\) destrói a unicidade da distribuição estacionária. Explique o papel de cada hipótese da proposição sobre PageRank.

Exercício 3.8

Personalização dos destinos^* No grafo de quatro páginas, troque \(v\) por \((1/2,1/6,1/6,1/6)\), incluindo essa troca na linha sem saída de \(P\). Partindo da distribuição uniforme, calcule uma iteração com \(\alpha =4/5\). Que parte da mudança se deve à preferência introduzida no modelo, e não a novos links observados?

Exercício 3.9

O teto pode apagar a preferência^* Considere dois caminhos com escolha proporcional ao feromônio, reforços \(q_1\gt q_2\gt 0\), ausência de evaporação e \(\tau _{\min }\leq \tau _i(0)\leq \tau _{\max }\), onde \(0\lt \tau _{\min }\lt \tau _{\max }\lt \infty \). A atualização é

\[ \tau _i(n+1)=\min \left\{ \tau _{\max }, \tau _i(n)+q_i\mathbf1_{\{ J_{n+1}=i\} }\right\} . \]

Mostre que cada caminho é escolhido infinitas vezes e que ambos os feromônios atingem \(\tau _{\max }\) em tempo finito quase certamente. Quais passam a ser as probabilidades de escolha? Explique por que isso não contradiz o teorema de seleção do caminho menor e por que exploração persistente não basta para garantir preferência assintótica pelo melhor caminho.

Distribuições estacionárias e comportamento limite

3.1 Distribuições estacionárias

3.2 Cálculo de distribuições estacionárias

3.2.1 Cadeias com dois estados

3.2.2 Um modelo de estoque

3.2.3 Cadeias duplamente estocásticas

3.3 Reversibilidade e balanço detalhado

3.3.1 Cadeia reversa

3.4 Comportamento limite

3.4.1 Frequências e tempo médio de retorno

3.4.2 Convergência das distribuições

3.4.3 Recompensas ao longo de uma trajetória

3.5 Velocidade de convergência e espectro

3.6 Problemas de síntese

3.7 PageRank e centralidade*

3.8 Otimização por colônias de formigas*

3.8.1 Escolhas aleatórias guiadas pelo feromônio

3.8.2 Um modelo com dois caminhos

3.8.3 Sem evaporação: reforço e seleção

3.8.4 Exploração e concentração prematura

3.8.5 Uma aplicação em ciência de dados: seleção de variáveis

3.9 Exercícios

3.10 Exercícios complementares*

3.7 PageRank e centralidade^*

3.8 Otimização por colônias de formigas^*

3.10 Exercícios complementares^*