O que é Independência?

Exemplo 21.21 (Independência lida numa estrutura de produto)

Lance dois dados honestos: $\Omega = \intint16^2$ com pesos uniformes. Sejam $A = {}$“primeiro dado par” e $B = {}$“segundo dado ao menos $5$”. Contando: $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, logo

independentes, e o mecanismo é visível — $A$ restringe apenas a primeira coordenada, $B$ apenas a segunda, e a medida uniforme num conjunto produto faz as contagens de coordenadas se multiplicarem. Toda afirmação do tipo “eventos que dependem de grupos disjuntos de lançamentos são independentes” (usada massivamente no problema de fim de semana) é esse cálculo, vestindo mais índices.

Exemplo 21.8 (A cota da união: grosseira mas indestrutível)

A subaditividade com finitos eventos — a cota da união — troca precisão por universalidade. Para o problema dos aniversários com $23$ pessoas, majorar a probabilidade de colisão pela soma sobre os pares dá

contra o verdadeiro $0.507$: errado por larga margem, porque as colisões se sobrepõem. Ainda assim, a cota não precisa de independência, de lei conjunta, de nada além das probabilidades de pares — e é por isso que, no problema de fim de semana e ao longo de todo o Capítulo 22, a cota da união é a primeira ferramenta sacada: quando ela por acaso é pequena, a questão está resolvida sem modelagem adicional.

Exemplo 21.15 (A colisão de aniversários, pela regra da cadeia)

Com $n$ pessoas cujos aniversários são independentes e uniformes em $365$ dias, seja $D_n = {}$“todos os $n$ aniversários diferem”. Condicionando pessoa a pessoa (regra da cadeia):

cada nova pessoa tendo de evitar os $k$ dias já ocupados. Para $n = 23$: $\P(D_{23}) \approx 0.493$ — um aniversário compartilhado já é mais provável do que não. A heurística que explica a pequenez de $23$: tomando logaritmos, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$, e $\binom{23}2 = 253$ dá $253/365 \approx 0.693 \approx \ln 2$. O que importa é o número de pares, que cresce quadraticamente: os problemas de colisão vivem na escala $n \sim \sqrt{365}$, e não $n \sim 365$ — o paradoxo dos aniversários é uma raiz quadrada disfarçada.

Exemplo 22.7 (O problema dos aniversários, honestamente)

Entre $n$ pessoas com aniversários independentes e uniformes em $N = 365$ dias, a probabilidade de que todos os aniversários difiram é

por condicionamentos sucessivos (ou diretamente: os $N(N-1)\cdots(N - n + 1)$ casos favoráveis sobre o total $N^n$, um argumento de contagem que a fórmula do produto da independência torna rigoroso). Tomando logaritmos e usando $-\ln(1 - x) = x + O(x^2)$:

O ponto de virada $p_n = \frac12$ fica em $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$: para $N = 365$, $n = 23$ ($p_{23} = 0.4927$). Duas morais. Primeira: as colisões entre $n$ itens em $N$ caixas aparecem na escala $n \sim \sqrt N$, e não $n \sim N$ — o escalamento do aniversário, que governa as colisões de hash e o custo $\sqrt N$ dos ataques de aniversário em criptografia. Segunda: o cálculo é um modelo: os $\binom n2$ eventos de colisão de pares não são independentes e, no entanto, a resposta se comporta como se fossem ($\eu^{-\binom n2/N}$ é exatamente a heurística de pares independentes) — uma primeira instância da aproximação de Poisson, tornada rigorosa no problema de fim de semana do Capítulo 23 (desigualdade de Le Cam).

Exemplo 22.14 (O que a lei forte compra)

(a) Frequências: para lançamentos de moeda i.i.d., a frequência observada de caras converge q.c. a $p$ — a justificativa empírica da própria probabilidade. (b) Monte Carlo: para $g \in L^1(\intcc01)$ e $(U_n)$ i.i.d. uniformes (Teorema 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ q.c.: integrais por amostragem, em qualquer dimensão, à taxa $\sim n^{-1/2}$ independente da dimensão, tornada precisa no Capítulo 23. (c) Números normais: quase todo número real tem, em sua expansão binária, frequência assintótica $\frac12$ de uns (aplique a lei forte às variáveis dígito do Teorema 22.6) — o teorema de Borel, uma afirmação sobre os números de todo dia demonstrada por medida; o Problema 22.1 a completa em todas as bases.