Wat is Onafhankelijkheid?

Voorbeeld 21.21 (Onafhankelijkheid afgelezen van een productstructuur)

Gooi met twee eerlijke dobbelstenen: $\Omega = \intint16^2$ met uniforme gewichten. Zij $A = {}$“eerste dobbelsteen even” en $B = {}$“tweede dobbelsteen minstens $5$”. Tellen: $\abs A = 3\cdot6 = 18$, $\abs B = 6\cdot2 = 12$, $\abs{A\cap B} = 3\cdot2 = 6$, dus

onafhankelijk, en het mechanisme is zichtbaar — $A$ legt alleen de eerste coördinaat vast, $B$ alleen de tweede, en de uniforme maat op een productverzameling laat de coördinaattellingen vermenigvuldigen. Elke bewering van het type “gebeurtenissen die van disjuncte groepen worpen afhangen, zijn onafhankelijk” (massaal gebruikt in de weekendopgave) is deze berekening, met meer indices.

Voorbeeld 21.8 (De somgrens: ruw maar onverwoestbaar)

De subadditiviteit met eindig veel gebeurtenissen — de somgrens — ruilt nauwkeurigheid in voor universaliteit. Voor het verjaardagsprobleem met $23$ mensen geeft de kans op een botsing begrenzen door de som over de paren

tegenover de werkelijke $0.507$: er ruim naast, omdat botsingen elkaar overlappen. Toch heeft de grens geen onafhankelijkheid nodig, geen gezamenlijke verdeling, niets dan de kansen op de paren — en daarom is in de weekendopgave en overal in Hoofdstuk 22 de somgrens het eerst getrokken wapen: blijkt zij klein te zijn, dan is de zaak beslecht zonder verdere modellering.

Voorbeeld 21.15 (De verjaardagsbotsing, met de kettingregel)

Met $n$ mensen wier verjaardagen onafhankelijk en uniform over $365$ dagen verdeeld zijn, zij $D_n = {}$“alle $n$ verjaardagen verschillen”. Persoon voor persoon voorwaardelijk stellen (kettingregel) geeft

waarbij elke nieuwe persoon de $k$ reeds bezette dagen moet vermijden. Voor $n = 23$: $\P(D_{23}) \approx 0.493$ — een gedeelde verjaardag is al waarschijnlijker dan niet. De heuristiek die de kleinheid van $23$ verklaart: logaritmen nemen geeft $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$, en $\binom{23}2 = 253$ geeft $253/365 \approx 0.693 \approx \ln 2$. Wat telt is het aantal paren, dat kwadratisch groeit: botsingsproblemen leven op de schaal $n \sim \sqrt{365}$, niet $n \sim 365$ — de verjaardagsparadox is een vierkantswortel in vermomming.

Voorbeeld 22.7 (Het verjaardagsprobleem, eerlijk)

Onder $n$ mensen met onafhankelijke, uniform over $N = 365$ dagen verdeelde verjaardagen is de kans dat alle verjaardagen verschillen

door herhaald te conditioneren (of rechtstreeks: de gunstige $N(N-1)\cdots(N - n + 1)$ op het totaal $N^n$, een telargument dat de productformule van de onafhankelijkheid streng maakt). Logaritmen nemen en $-\ln(1 - x) = x + O(x^2)$ gebruiken geeft

Het kantelpunt $p_n = \frac12$ ligt bij $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$: voor $N = 365$ is $n = 23$ ($p_{23} = 0.4927$). Twee moralen. Ten eerste duiken botsingen tussen $n$ voorwerpen in $N$ dozen op op de schaal $n \sim \sqrt N$, niet $n \sim N$ — de verjaardagsschaling die de botsingen van hashfuncties en de kostprijs $\sqrt N$ van verjaardagsaanvallen in de cryptografie regeert. Ten tweede is de berekening een sjabloon: de $\binom n2$ gebeurtenissen “dit paar botst” zijn niet onafhankelijk, en toch gedraagt het antwoord zich alsof ze het wel waren ($\eu^{-\binom n2/N}$ is precies de heuristiek met onafhankelijke paren) — een eerste geval van de poissonbenadering die in de weekendopgave van Hoofdstuk 23 streng wordt gemaakt (de ongelijkheid van Le Cam).

Voorbeeld 22.14 (Wat de sterke wet oplevert)

(a) Frequenties: voor i.i.d. muntworpen convergeert de waargenomen frequentie van kop b.z. naar $p$ — de empirische rechtvaardiging van de kansrekening zelf. (b) Monte carlo: voor $g \in L^1(\intcc01)$ en $(U_n)$ i.i.d. uniform (Stelling 22.6) is $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ b.z.: integralen door te bemonsteren, in elke dimensie, met de van de dimensie onafhankelijke snelheid $\sim n^{-1/2}$ die in Hoofdstuk 23 precies wordt gemaakt. (c) Normale getallen: bijna elk reëel getal heeft in zijn binaire ontwikkeling asymptotische frequentie $\frac12$ aan enen (pas de sterke wet toe op de cijferveranderlijken van Stelling 22.6) — de stelling van Borel, een uitspraak over de meest alledaagse getallen bewezen met maat: Probleem 22.1 maakt haar in alle bases af.