Parte II · Cadeias de Markov — dependência, e a matemática que prevê quase tudo

draft

Uma única ideia — o futuro depende do presente, e de nada anterior a ele — acaba por ranquear a web, simular reatores nucleares, embaralhar cartas e prever a próxima palavra que você digita. Este capítulo é a teoria dessa ideia, da disputa que a criou aos teoremas que a fazem funcionar. Seus dois companheiros põem a teoria em ação: Monte Carlo & MCMC e PageRank.

1. A disputa: uma briga sobre livre-arbítrio que criou um campo

As cadeias de Markov nasceram de uma discussão. Por volta de 1902, Pavel Nekrasov — um ex-seminarista à frente da escola matemática conservadora e religiosa de Moscou — pôs a probabilidade a serviço do debate sobre o livre-arbítrio. Seu silogismo: atos humanos voluntários são como os eventos independentes da teoria da probabilidade; a lei dos grandes números se aplica apenas a eventos independentes; estatísticas sociais (taxas de crime, casamento, colheita) de fato obedecem à lei dos grandes números; logo, atos humanos devem ser independentes — evidência do livre-arbítrio. Em resumo, Nekrasov afirmava que "médias estáveis de longo prazo ⇒ independência."

Andrey Markov (1856–1922) — aluno de Chebyshev, professor na São Petersburgo secular e liberal, e ateu combativo — leu isso como um abuso da matemática. (Em 1912 Markov requereu a própria excomunhão da Igreja Ortodoxa em solidariedade a Tolstói; em 1908 recusou uma ordem do governo para espionar estudantes.) Ele se propôs a destruir a premissa de Nekrasov construindo sequências de eventos dependentes que ainda assim obedecem à lei dos grandes números. Essas sequências são o que hoje chamamos de cadeias de Markov (artigos de 1906 até 1912). A querela teológica foi a provocação; o teorema — *a lei dos grandes números não requer independência* — foi o resultado duradouro.

2. A lei dos grandes números, e a fenda que Markov abriu nela

A lei dos grandes números (LGN) foi provada pela primeira vez por Jacob Bernoulli em *Ars Conjectandi, publicado postumamente em *1713 — ele a chamou de seu "teorema de ouro". Sua forma fraca* para ensaios independentes com probabilidade de sucesso \(p\), a frequência empírica \(S_n/n\) converge em probabilidade para \(p\):

\[\forall\varepsilon>0:\quad \Pr\!\left(\left|\tfrac{S_n}{n}-p\right|>\varepsilon\right)\xrightarrow[n\to\infty]{}0.\]

A lei forte (Borel 1909; Kolmogorov, anos 1930) reforça isso para convergência quase certa, \(\Pr(\lim_n S_n/n = p)=1\). (O nome "lei dos grandes números" é de Poisson, 1837.)

Todo enunciado clássico assumia independência. A contribuição de Markov foi provar que a LGN sobrevive à dependência: para uma sequência adequada de variáveis dependentes — em particular uma cadeia de Markov bem-comportada — a média amostral \(\frac1n\sum_i X_i\) ainda converge, agora para a média estacionária da cadeia. Essa única generalização é a refutação matemática de Nekrasov: observar médias estáveis não diz nada sobre se os eventos subjacentes são independentes.

3. Eugene Onegin: a primeira cadeia de Markov ajustada a dados reais

Para mostrar dependência com médias estáveis no mundo real, Markov recorreu à poesia. Em um discurso à Academia de São Petersburgo em 23 de janeiro de 1913 (juliano; = 5 de fevereiro gregoriano), ele tomou as primeiras 20.000 letras de Eugene Onegin, de Pushkin, descartou espaços e pontuação, e rotulou cada letra como vogal (V) ou consoante (C). Então, à mão, contou letras isoladas e pares consecutivos.

  • 8.638 vogais / 11.362 consoantes → \(P(V)\approx 0.43\), \(P(C)\approx 0.57\).
  • Pares de vogal-seguida-de-vogal: 1.104 observados, contra *.698 esperados sob

    independência — mal um terço. As letras são fortemente dependentes*

A matriz de transição de dois estados que ele estimou:

de ＼ para vogal consoante
vogal 0.128 0.872
consoante 0.663 0.337

Sua distribuição estacionária é ≈ 43% vogais / 57% consoantes — casando com as marginais observadas. Letras dependentes, frequência estável de longo prazo: exatamente o ponto. Esta é a primeira aplicação de cadeias de Markov a dados empíricos, e possivelmente o primeiro modelo estatístico de texto em linguagem natural — o ancestral direto da teoria da informação de Shannon e dos modelos de linguagem n-grama (Compêndio de IA, cap. 35).

4. O objeto formal

Uma cadeia de Markov de tempo discreto é uma sequência de variáveis aleatórias \(X_0, X_1, X_2,\dots\) sobre um espaço de estados \(S\) enumerável (finito: \(S=\{1,\dots,N\}\)) satisfazendo a propriedade de Markov / ausência de memória:

\[\Pr(X_{n+1}=j \mid X_n=i, X_{n-1}=\dots,\dots,X_0=\dots) = \Pr(X_{n+1}=j \mid X_n=i).\]

O futuro depende do passado apenas através do estado presente.

Matriz de transição. \(P=(p_{ij})\), \(p_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), é estocástica por linhas: \(p_{ij}\ge0\) e cada linha soma 1. Cadeias homogêneas no tempo têm um único \(P\) para todos os passos.

Chapman–Kolmogorov & \(n\) passos. As probabilidades de \(m\) passos se compõem: \(P^{(m+r)}=P^{(m)}P^{(r)}\), então a matriz de transição de \(n\) passos é simplesmente a potência de matriz \(P^n\). Se \(\mu_0\) é a distribuição inicial (em linha), a distribuição após \(n\) passos é \(\mu_n = \mu_0 P^n\). Predição é multiplicação de matrizes.

Classificando estados.

  • Irredutível — todo estado alcança todo outro; uma única classe de comunicação.
  • Período \(d(i)=\gcd\{n\ge1: p_{ii}^{(n)}>0\}\); aperiódico se \(d(i)=1\).
  • Recorrente — o retorno é certo; transiente — probabilidade de retorno \(<1\).
  • Positivo recorrente — recorrente com tempo médio de retorno finito. (Em uma cadeia finita

    irredutível, todo estado é automaticamente positivo recorrente.)

  • Ergódico — aperiódico e positivo recorrente. Finito + irredutível + aperiódico

    \(\Rightarrow\) ergódico.

5. Distribuição estacionária e o teorema fundamental

Um vetor de probabilidade \(\pi\) é estacionário se permanece inalterado por um passo:

\[\pi P = \pi, \qquad \textstyle\sum_i \pi_i = 1.\]

\(\pi\) é o autovetor à esquerda de \(P\) com autovalor 1 — o equilíbrio de longo prazo da cadeia.

Perron–Frobenius garante que ele existe e é bem-comportado: para uma \(P\) estocástica todo autovalor tem \(|\lambda|\le1\) e \(\lambda=1\) está presente. Se \(P\) é irredutível, esse autovalor é simples e seu autovetor \(\pi\) é único e estritamente positivo. Se também aperiódica, \(1\) é o único autovalor no círculo unitário, o que força a convergência.

O teorema fundamental das cadeias de Markov (teorema ergódico). Para uma cadeia finita, irredutível e aperiódica:

  1. existe uma distribuição estacionária \(\pi\) única, com \(\pi_i = 1/M_i\) (inverso do

    tempo médio de retorno);

  2. ela esquece de onde partiu: \(\lim_{n\to\infty}p_{ij}^{(n)} = \pi_j\) para todo

    \(i\) — cada linha de \(P^n\) converge para \(\pi\);

  3. média temporal = média espacial (a LGN de Markov para variáveis dependentes):

    \(\frac1n\sum_{k=1}^n f(X_k) \to \sum_i \pi_i f(i)\) quase certamente.

O ponto 3 é a história inteira das aplicações deste compêndio: rode uma longa trajetória e faça a média, e você recupera uma esperança sob \(\pi\). A integração de Monte Carlo (cap. 02) é este teorema; o PageRank (cap. 03) é o \(\pi\) de uma cadeia do tamanho da web.

Quão rápido? O gap espectral. A convergência \(\|\mu_0 P^n - \pi\|\) decai como \(|\lambda_2|^n\), onde \(\lambda_2\) é o módulo do segundo maior autovalor. Um gap grande (\(\lambda_2\) pequeno) significa mistura rápida. (Uma cadeia irredutível periódica ainda tem um \(\pi\) único, mas \(P^n\) nunca se assenta — ele cicla.)

6. Tempo de mistura: quanto tempo até ficar "aleatório"?

Para medir a distância ao equilíbrio, use a distância de variação total:

\[\|\mu-\nu\|_{\mathrm{TV}} = \tfrac12\sum_{x}|\mu(x)-\nu(x)| = \max_{A\subseteq S}|\mu(A)-\nu(A)| \in[0,1].\]

Com \(d(t)=\max_x\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\), o tempo de mistura é \(t_{\mathrm{mix}}(\varepsilon)=\min\{t: d(t)\le\varepsilon\}\), convencionalmente em \(\varepsilon=\tfrac14\). Algumas cadeias exibem um fenômeno de cutoff: \(d(t)\) permanece perto de 1, então despenca para perto de 0 ao longo de uma janela desprezível ao lado de \(t_{\mathrm{mix}}\) — a aproximação da aleatoriedade é um degrau abrupto, não um esmaecimento suave. É exatamente isso que torna o próximo exemplo famoso.

7. Sete embaralhamentos: o cutoff que você pode segurar nas mãos

Quantos embaralhamentos riffle randomizam um baralho de 52 cartas? David Bayer e Persi Diaconis responderam com precisão em "Trailing the Dovetail Shuffle to its Lair" (*Annals of Applied Probability, 1992), modelando o riffle pelo processo *Gilbert–Shannon–Reeds*(corte binomial, intercalação proporcional aos tamanhos dos maços; \(k\) riffles se compõem em um único \(2^k\)-embaralhamento). A distância de variação total a um baralho perfeitamente embaralhado:

embaralhamentos \(k\) 1 2 3 4 5 6 7 8
distância TV 1.00 1.00 1.00 1.00 0.92 0.61 0.33 0.17

O baralho permanece essencialmente não embaralhado (TV ≈ 1) ao longo de quatro embaralhamentos, colapsa entre cinco e seis, e cai abaixo de \(\tfrac12\) pela primeira vez em sete — o clássico "sete embaralhamentos riffle bastam", um cutoff que você pode ver na tabela. Assintoticamente o tempo de mistura obedece \(t_{\mathrm{mix}} \sim \tfrac32\log_2 n\) embaralhamentos (para \(n=52\) essa fórmula dá ≈8.5; o cálculo finito exato cruza \(\tfrac12\) em 7 — mantenha ambos, eles respondem perguntas ligeiramente diferentes).

O contraste deixa o ponto claro: o desajeitado embaralhamento overhand mistura em \(\Theta(n^2\log n)\) passos (Pemantle; Jonasson 2006) — na ordem de milhares de embaralhamentos overhand para um baralho de 52 cartas atingir o que sete riffles alcançam. Mesmo baralho, mesmo objetivo; um método \(O(\log n)\) contra um \(O(n^2\log n)\). Escolher a cadeia certa é tudo.

8. Aonde a cadeia leva

A caminhada sem memória é um substrato, não um único algoritmo. Daqui o compêndio segue dois de seus usos mais consequentes:

  • Monte Carlo & MCMC — projete uma cadeia cuja *distribuição

    estacionária seja um alvo que você quer amostrar*, então deixe o teorema ergódico fazer a integração. O motor da física estatística e do ML bayesiano.

  • PageRank — faça dos estados páginas web e

    da caminhada um surfista aleatório; a distribuição estacionária é o ranqueamento.

E no Compêndio de IA, a mesma cadeia sobre texto se torna o modelo de linguagem n-grama — o ancestral sem memória do LLM. Onde as cadeias de Markov têm dificuldade é exatamente onde a memória importa: sistemas com longos laços de realimentação (o clima, com sua amplificação composta CO₂→temperatura→vapor-d'água) quebram a suposição de um passo, e é por isso que existem modelos mais ricos. Mas o alcance da ideia pura — futuro só a partir do presente — é a razão de ela prever quase tudo.

Por que importa pra Stack

Ranqueamento (busca do Hub/kode-rag), amostragem (qualquer estimativa probabilística no kdb ou na camada de IA) e predição de sequências se reduzem todos a uma cadeia de Markov mais sua distribuição estacionária. Este capítulo é o solo enciclopédico que essas decisões citam — um fato, um lar (referência-vs-decisão, conforme o INDEX principal).

Fontes

  • Seneta, E. (2007). Markov and the Creation of Markov Chains.
  • Hayes, B. (2013). First Links in the Markov Chain. American Scientist 101(2):92.
  • Bernoulli, J. (1713). Ars Conjectandi; Seneta, E. (2013). A Tricentenary History of the Law of Large Numbers (arXiv:1309.6488).
  • Markov, A. A. (1913). An Example of Statistical Investigation of the Text Eugene Onegin… (Eng. trans. Link, Science in Context, 2006).
  • Levin, D., Peres, Y. & Wilmer, E. (2009). Markov Chains and Mixing Times, AMS.
  • Bayer, D. & Diaconis, P. (1992). Trailing the Dovetail Shuffle to its Lair. Ann. Appl. Probab. 2(2):294–313.
  • Jonasson, J. (2006). The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps. Ann. Appl. Probab. (arXiv:math/0501401).