Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

22Discrete toevalsveranderlijken

Toevalsveranderlijken ordenen kansberekeningen rond functies in plaats van rond gebeurtenissen. Op aftelbare ruimten wordt de theorie aangedreven door de sommeerbare families van Hoofdstuk 7: de verwachtingswaarde is de som van een familie geïndexeerd door de uitkomstenruimte, en al haar eigenschappen — lineariteit, overdracht, de productformule voor onafhankelijke veranderlijken — zijn stellingen over sommeerbare families. Het hoofdstuk bewijst de sleutelongelijkheden van Markov, Chebyshev, Cauchy–Schwarz en Jensen, en eindigt met de klassieke verdelingen en de zwakke wet van de grote aantallen, waarvan het bewijs twee regels lang is zodra Chebyshev beschikbaar is.

22.1 Toevalsveranderlijken en hun verdelingen

Definitie 22.1 (Discrete toevalsveranderlijke; verdeling)

Zij $(\Omega, \P)$ een aftelbare kansruimte. Een toevalsveranderlijke is een afbeelding $X \colon \Omega \to E$ ( $E$ een willekeurige verzameling; reële toevalsveranderlijke wanneer $E = \R$ ). Haar verdeling (of kansverdeling) is de kansmaat $\P_X$ op de aftelbare verzameling $X(\Omega)$ gedefinieerd door

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

Voorbeeld 22.2 (De klassieke verdelingen)

Bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . De indicator van een gebeurtenis.
Binomiaal $\mathcal{B}(n, p)$ : $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ , $0 \leq k \leq n$ : het aantal successen in $n$ onafhankelijke bernoulli-experimenten (bovenbouwvolume; hieronder opnieuw bewezen via sommen van onafhankelijke veranderlijken).
Meetkundig $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : de rang van het eerste succes (Voorbeeld 21.5).
Poisson $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — een kansmaat wegens de exponentiële reeks. De verdeling van de zeldzame gebeurtenissen (Hoofdstuk 23).

Opmerking 22.3 (Welke verdeling modelleert wat)

De vier verdelingen beantwoorden vier oervragen: Bernoulli, “is het gebeurd?”; binomiaal, “hoe vaak in $n$ pogingen?”; meetkundig, “hoe lang tot de eerste keer?”; Poisson, “hoeveel gebeurtenissen bij een gegeven tempo, wanneer er veel pogingen zijn die elk onwaarschijnlijk zijn?”. De vraag herkennen is negen tiende van het modelleren: sommen van indicatoren wijzen op de binomiale, wachttijden op de meetkundige, en tellingen van zeldzame gebeurtenissen op de poisson-verdeling — waarbij de overgang van binomiaal naar Poisson door de verdeling van de zeldzame gebeurtenissen in Hoofdstuk 23 precies wordt gemaakt.

Propositie 22.4 (Geheugenloosheid van de meetkundige verdeling)

Is $X \sim \mathcal{G}(p)$ , dan geldt voor alle $m, n \in \N$

\P(X > m + n \mid X > m) = \P(X > n) ,

en de meetkundige verdelingen zijn de enige verdelingen op $\N^*$ met deze eigenschap.

Bewijs. De meetkundige gewichten sommeren geeft $\P(X > n) = (1-p)^n$ . Bijgevolg is

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

Omgekeerd, voldoet $G(n) = \P(X > n)$ aan $G(m + n) = G(m)G(n)$ met $G(0) = 1$ , dan is $G(n) = G(1)^n$ met inductie; $q = G(1) \in \intco{0}{1}$ , en ofwel is $q = 0$ ofwel is de verdeling $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Voorbeeld 22.5 (Geen enkel getal is ooit “aan de beurt”)

Gooi met een dobbelsteen en wacht op een zes: de wachttijd is $X \sim \mathcal G(1/6)$ . De geheugenloosheid zegt dat na $10$ vruchteloze worpen de resterende wachttijd $X - 10$ , gegeven $X > 10$ , opnieuw $\mathcal G(1/6)$ is: de voorwaardelijke verwachte wachttijd is nog altijd $6$ worpen, precies als bij het begin. De dobbelsteen onthoudt niets, en geen zes is ooit “aan de beurt” — de drogreden van de gokker is het geloof dat de voorwaardelijke verdeling verschoven zou moeten zijn. Omgekeerd zegt de eenduidigheidshelft van de propositie dat deze onverschilligheid meetkundige wachttijden karakteriseert: elke wachttijd waarvan de voorspelling zich nooit bijstelt, is meetkundig. Echte wachtrijen en levensduren stellen zich meestal wél bij, en precies zo merkt men dat zij niet meetkundig zijn.

22.2 Verwachtingswaarde

Definitie 22.6 (Verwachtingswaarde)

Een reële toevalsveranderlijke $X$ op $(\Omega, \P)$ heeft een verwachtingswaarde wanneer de familie $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ sommeerbaar is (Hoofdstuk 7); haar verwachtingswaarde is dan

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

Stelling 22.7 (Overdrachtsstelling)

$X$ heeft een verwachtingswaarde dan en slechts dan als de familie $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ sommeerbaar is, en dan is

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

Algemener heeft voor $f \colon X(\Omega) \to \R$ de veranderlijke $f(X)$ een verwachtingswaarde dan en slechts dan als $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , en dan is $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Bewijs. Partitioneer $\Omega$ in de niveauverzamelingen $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Volgens de stelling over sommeren in pakketten voor sommeerbare families (Hoofdstuk 7) is de familie $(X(\omega)\P(\{\omega\}))_\omega$ sommeerbaar dan en slechts dan als elk pakket dat is (automatisch: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) en de familie van pakketsommen $\bigl(x\,\P(X = x)\bigr)_x$ sommeerbaar is — en dan stemmen de totale sommen overeen. Voor $f(X)$ : pas de bewezen uitspraak toe op de veranderlijke $Y = f \circ X$ , waarvan de niveauverzamelingen $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ zijn; een tweede sommatie in pakketten zet $\sum_y y\,\P(Y = y)$ om in $\sum_x f(x)\,\P(X = x)$ , waarbij de pakketten nu de waarden $x$ groeperen naar hun beeld $f(x)$ , en de absolute sommeerbaarheid van de ene familie gelijkwaardig is met die van de andere. ∎

Stelling 22.8 (Eigenschappen van de verwachtingswaarde)

Op de verzameling toevalsveranderlijken met verwachtingswaarde:

(Lineariteit) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positiviteit en monotonie) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; en $\abs{\E(X)} \leq \E(\abs X)$ .
(Dominatie) Is $\abs X \leq Z$ en heeft $Z$ een verwachtingswaarde, dan heeft $X$ er ook een.

Bewijs. Alle zijn eigenschappen van sommen van sommeerbare families (Hoofdstuk 7): de lineariteit van de som, de positiviteit term voor term, en het dominatiecriterium voor de sommeerbaarheid. (Merk op dat de lineariteit onmiddellijk is op de definitie over $\Omega$ , terwijl zij op de overdrachtsformule onhandig zou zijn — één voordeel van $\E$ stroomopwaarts te definiëren.) ∎

Voorbeeld 22.9

$X \sim \mathcal{B}(n, p)$ : schrijf $X = X_1 + \dots + X_n$ als een som van bernoulli-indicatoren en gebruik de lineariteit: $\E(X) = np$ — geen binomiaalcoëfficiënten nodig. $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ , door de meetkundige reeks binnen haar schijf te differentiëren (Hoofdstuk 11). $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

Voorbeeld 22.10 (Overdracht in actie)

Bereken voor $X \sim \mathcal P(\lambda)$ de waarde $\E\bigl(\frac1{1+X}\bigr)$ — de verdeling van $\frac1{1+X}$ zelf is onhandig, maar de overdracht vraagt er nooit naar:

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

Twee lessen. Rekenkundig: een verschoven exponentiële reeks herkennen is het hele werk — de overdracht herleidt verwachtingswaarden van $f(X)$ tot het hanteren van reeksen. Structureel: de naïeve invulwaarde zou $\frac1{1 + \E X} = \frac1{1 + \lambda}$ zijn, en het echte antwoord is groter,

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

precies zoals de ongelijkheid van Jensen voor de convexe functie $t \mapsto \frac1{1+t}$ eist. Verwachtingswaarden van convexe beelden liggen boven de naïeve invulwaarde, en de overdracht plus een reekscontrole maakt de abstracte ongelijkheid concreet.

Stelling 22.11 (Onafhankelijkheid en producten)

Toevalsveranderlijken $X, Y$ heten onafhankelijk wanneer $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ voor alle $x, y$ — gelijkwaardig: wanneer de gebeurtenissen $\{X \in A\}$ en $\{Y \in B\}$ onafhankelijk zijn voor alle $A, B$ . Zijn $X$ en $Y$ onafhankelijke reële veranderlijken met verwachtingswaarden, dan heeft $XY$ een verwachtingswaarde en is

\E(XY) = \E(X)\,\E(Y) .

Bewijs. De gelijkwaardigheid van de twee formuleringen volgt door de puntsgewijze identiteit over $(x, y) \in A \times B$ te sommeren (tweemaal $\sigma$ -additiviteit). Voor het product: de dubbele familie $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ is sommeerbaar, want volgens Fubini voor families (Hoofdstuk 7) is

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

wegens de onafhankelijkheid is deze familie precies $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , waarvan de som $\E(XY)$ is volgens de overdracht toegepast op de veranderlijke $(X, Y) \mapsto xy$ ; Fubini evalueert de ongetekende som opnieuw als het product $\E(X)\E(Y)$ . ∎

Voorbeeld 22.12 (Producten, met en zonder onafhankelijkheid)

Gooi met twee eerlijke dobbelstenen. Is $Y$ de tweede dobbelsteen (onafhankelijk van de eerste), dan is $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . Is daarentegen $Y = X$ (het “product” van een dobbelsteen met zichzelf), dan is

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

dezelfde marginale verdelingen in beide scenario’s, verschillende gezamenlijke verdelingen, verschillende verwachtingswaarden van het product. De moraal, het onthouden waard: $\E(XY)$ is een functionaal van het paar, niet van de twee marginalen — en het gat $\E(X^2) - \E(X)^2 \approx 2.92$ is volgens König–Huygens precies de variantie $\frac{35}{12}$ van de dobbelsteen.

22.3 Variantie, covariantie en de klassieke ongelijkheden

Definitie 22.13 (Momenten, variantie)

$X$ heeft een moment van orde 2 wanneer $X^2$ een verwachtingswaarde heeft (dan ook $X$ , wegens de dominatie: $\abs X \leq \frac{1 + X^2}{2}$ ). Haar variantie en standaardafwijking zijn dan

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(de tweede vorm — de formule van König–Huygens — door het kwadraat uit te werken en de lineariteit te gebruiken:

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

waarbij de middelste term gebruikt dat $\E X$ een constante is). Voor $X, Y$ met tweede momenten is de covariantie

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

Stelling 22.14 (Gereedschapskist van de variantie)

Voor veranderlijken met tweede momenten:

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ , en algemener

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
zijn $X, Y$ onafhankelijk, dan is $\operatorname{Cov}(X, Y) = 0$ (het omgekeerde is onwaar), zodat de varianties van onafhankelijke veranderlijken optellen.

Bewijs. 1 en 2 zijn het uitwerken van kwadraten plus de lineariteit; de producten $X_iX_j$ hebben verwachtingswaarden volgens Cauchy–Schwarz hieronder (of wegens $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 is Stelling 22.11 toegepast op de gecentreerde veranderlijken. Een standaardtegenvoorbeeld voor het omgekeerde: $X$ uniform op $\{-1, 0, 1\}$ en $Y = X^2$ zijn ongecorreleerd ( $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) maar duidelijk afhankelijk. ∎

Stelling 22.15 (Ongelijkheden van Markov en Chebyshev)

(Markov) Heeft $X \geq 0$ een verwachtingswaarde, dan is voor elke $a > 0$

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) Heeft $X$ een tweede moment, dan is voor elke $\varepsilon > 0$

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

Bewijs. 1. Puntsgewijs is $a\,\mathbf{1}_{X \geq a} \leq X$ (op de gebeurtenis is het linkerlid $a \leq X$ ; erbuiten $0 \leq X$ ). Neem verwachtingswaarden: $a\,\P(X \geq a) \leq \E(X)$ wegens de monotonie en $\E(\mathbf{1}_A) = \P(A)$ . 2. Pas Markov toe op de niet-negatieve veranderlijke $(X - \E X)^2$ op niveau $a = \varepsilon^2$ : de gebeurtenis $\{(X - \E X)^2 \geq \varepsilon^2\}$ is precies $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Voorbeeld 22.16 (Ongecorreleerd maar aan elkaar vastgelijmd)

Gooi met twee eerlijke dobbelstenen, $X$ en $Y$ onafhankelijk, en zet $S = X + Y$ , $D = X - Y$ . Wegens de bilineariteit van de covariantie is

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

som en verschil zijn ongecorreleerd. Onafhankelijk? Zeker niet: $S = 12$ dwingt $D = 0$ af, terwijl $\P(D = 0) = \frac16$ is zonder voorwaarde. De correlatie toetst alleen het lineaire deel van een afhankelijkheid; hier wordt de afhankelijkheid gedragen door de voorwaarde dat $S$ en $D$ dezelfde pariteit hebben, onzichtbaar voor de covariantie. (Voor dit paar had de nulcovariantie $V(X) = V(Y)$ nodig: gelijke verdelingen, niet de onafhankelijkheid, deden het werk.)

Voorbeeld 22.17 (Wanneer Markov exact is)

De ongelijkheid van Markov is een gelijkheid precies wanneer er niets verloren gaat in de grens $a\,\mathbf 1_{X\geq a} \leq X$ : de veranderlijke moet alleen de waarden $0$ en $a$ aannemen. Concreet, is $\P(X = a) = \pi$ en $\P(X = 0) = 1 - \pi$ , dan is $\E(X) = a\pi$ en

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

Een realistische lezing: in een bevolking waar het gemiddelde vermogen $100$ is en het vermogen ofwel $0$ ofwel $10^6$ bedraagt, is het aandeel miljonairs precies $10^{-4}$ — de grens van Markov, exact bereikt door een maximale ongelijkheid. Zodra $X$ zich over tussenliggende waarden uitspreidt, is de grens strikt, vaak wild; maar zoals het extreme geval toont, kan uit het gemiddelde alleen geen betere ongelijkheid worden gehaald.

Voorbeeld 22.18 (Chebyshev is scherp — zonder verdere hypothesen)

Houd $\varepsilon > 0$ en $q \in \intoc01$ vast, en laat $X$ de waarden $\pm\varepsilon$ elk met kans $\frac q2$ aannemen en $0$ met kans $1 - q$ . Dan is $\E(X) = 0$ , $V(X) = q\varepsilon^2$ en

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

gelijkheid in Chebyshev. De ongelijkheid kan dus niet worden verbeterd met alleen de variantie — het verval $1/\varepsilon^2$ is de exacte prijs van informatie over het tweede moment. Sneller verval vereist sterkere hypothesen: begrensdheid van de veranderlijke koopt exponentiële concentratie, zoals Oefening 22.7 voorproeft en de weekendopgave van dit hoofdstuk stelselmatig ontwikkelt.

Stelling 22.19 (Cauchy–Schwarz en Jensen)

(Cauchy–Schwarz) Hebben $X, Y$ tweede momenten, dan heeft $XY$ een verwachtingswaarde en is $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; bijgevolg $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) Is $\varphi \colon I \to \R$ convex op een interval dat $X(\Omega)$ bevat, en hebben $X$ en $\varphi(X)$ verwachtingswaarden, dan is

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

Bewijs. 1. Sommeerbaarheid van $XY$ : $\abs{XY} \leq \frac{X^2 + Y^2}2$ . De afbeelding $(X, Y) \mapsto \E(XY)$ is een positieve symmetrische bilineaire vorm op de ruimte van veranderlijken met tweede momenten, dus is de abstracte ongelijkheid van Cauchy–Schwarz uit Hoofdstuk 12 van toepassing (positief semidefiniet volstaat voor de ongelijkheid). Haar toepassen op de gecentreerde veranderlijken geeft de grens voor de covariantie.

2. Ten eerste ligt $m = \E(X)$ in $I$ : $I$ is een interval dat alle waarden van $X$ bevat, en de verwachtingswaarde is monotoon, dus ligt $m$ tussen $\inf X(\Omega)$ en $\sup X(\Omega)$ . Volgens de stelling over de steunrechte voor convexe functies (Hoofdstuk 8) bestaan er $\alpha, \beta$ met $\varphi(t) \geq \alpha t + \beta$ voor alle $t \in I$ en $\varphi(m) = \alpha m + \beta$ . Dan is puntsgewijs op $\Omega$ $\varphi(X) \geq \alpha X + \beta$ ; verwachtingswaarden nemen geeft

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

Voorbeeld 22.20

Jensen met $\varphi(t) = t^2$ geeft $\E(X)^2 \leq \E(X^2)$ — de positiviteit van de variantie; met $\varphi(t) = 1/t$ op $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — het harmonisch gemiddelde ligt onder het rekenkundig gemiddelde, nu in toevallige gedaante.

Opmerking 22.21 (Klassieke valkuilen)

(i) $\E(XY) = \E(X)\E(Y)$ vereist onafhankelijkheid (of minstens een nulcovariantie): met $Y = X$ krijgt men $\E(X^2) \neq \E(X)^2$ zodra $V(X) > 0$ . (ii) Evenzo is $V(X + X) = 4V(X)$ , niet $2V(X)$ : varianties tellen alleen op over onafhankelijke (of ongecorreleerde) termen. (iii) $\E(f(X))$ is niet $f(\E(X))$ ; voor convexe $f$ vertelt Jensen zelfs de richting van de fout, als in Voorbeeld 22.10. (iv) Het bestaan is een echte hypothese: voor de Sint-Petersburgveranderlijke $X = 2^K$ met $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ) is

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

$X$ is bijna zeker eindig en heeft toch geen verwachtingswaarde, en er bestaat geen eerlijke inzet voor het spel. De sommeerbaarheid in de definitie van $\E$ is geen boekhoudkundige muggenzifterij — het is waar zware staarten worden opgespoord. (v) Ten slotte heeft de overdrachtsstelling absolute sommeerbaarheid nodig voordat enige herschikking van de som over de waarden geoorloofd is (Hoofdstuk 7).

Voorbeeld 22.22 (Chebyshev op honderd worpen)

Voor $X \sim \mathcal B(100, \frac12)$ : $\E X = 50$ , $V(X) = 25$ . Chebyshev met $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

terwijl de exacte binomiale som $\approx 0.73$ geeft. De gewaarborgde $31\%$ ligt ver van de waarheid, maar zij vergde alleen het gemiddelde en de variantie — hetzelfde certificaat geldt woordelijk voor elke veranderlijke met $\E = 50$ en $V = 25$ , hoe exotisch ook, en Voorbeeld 22.18 toont dat een zekere zulke veranderlijke haar verzadigt. Universaliteit heeft een prijs; is de verdeling werkelijk binomiaal, dan dichten de exponentiële gereedschappen van de weekendopgave het grootste deel van het gat.

Voorbeeld 22.23 (De correlatie van een deel met zijn geheel)

Hoe sterk is voor onafhankelijke, identiek verdeelde $X, Y$ met variantie $\sigma^2 > 0$ één term gecorreleerd met de som $S = X + Y$ ? Bereken

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

zodat de correlatiecoëfficiënt

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707

is, wat de gemeenschappelijke verdeling ook is — dobbelstenen, munten, poisson-tellingen. Met $n$ termen geeft dezelfde berekening $\rho(X_1, S_n) = 1/\sqrt n$ : de invloed van elke afzonderlijke term op het totaal verdunt als een vierkantswortel, wat de schaduw in de correlatie is van de schaal $\sqrt n$ van de fluctuaties. Cauchy–Schwarz waarborgt altijd $\abs\rho \leq 1$ ; hier wordt de grens precies bereikt in het ontaarde geval $n = 1$ en vervalt zij daarna voorspelbaar.

Voorbeeld 22.24 (Gewogen ongelijkheid tussen rekenkundig en meetkundig gemiddelde uit Jensen)

Laat $Y$ de positieve waarden $a_1, \dots, a_k$ aannemen met kansen $\lambda_1, \dots, \lambda_k$ . De functie $-\ln$ is convex op $\intoo0\infty$ , dus geeft Jensen dat $-\ln\E(Y) \leq \E(-\ln Y)$ , dat wil zeggen

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

de gewogen ongelijkheid tussen het rekenkundig en het meetkundig gemiddelde, met gelijkheid dan en slechts dan als $Y$ constant is. Gelijke gewichten $\lambda_i = \frac1k$ geven de klassieke versie terug. De kansrekening heeft stilletjes een zuiver algebraïsche stelling bewezen: een kansverdeling kiezen is slechts een boekhoudkundig hulpmiddel voor convexe combinaties — opnieuw het barycentrische standpunt van Hoofdstuk 17, nu met Jensen als motor.

22.4 De zwakke wet van de grote aantallen

Stelling 22.25 (Zwakke wet van de grote aantallen)

Zij $(X_k)_{k \geq 1}$ een rij paarsgewijs onafhankelijke toevalsveranderlijken met dezelfde verdeling, die een tweede moment toelaat; schrijf $m = \E(X_1)$ en $S_n = X_1 + \dots + X_n$ . Dan is voor elke $\varepsilon > 0$

\P\Bigl(\,\Bigl|\frac{S_n}{n} - m\Bigr| \geq \varepsilon\Bigr) \;\leq\; \frac{V(X_1)}{n\,\varepsilon^2} \xrightarrow[n \to \infty]{} 0 .

Bewijs. Wegens de lineariteit is $\E(S_n/n) = m$ ; volgens Stelling 22.14 (de paarsgewijze onafhankelijkheid doodt de covarianties) is $V(S_n) = n\,V(X_1)$ , dus $V(S_n/n) = V(X_1)/n$ . De ongelijkheid van Chebyshev toegepast op $S_n/n$ geeft de grens. ∎

Opmerking 22.26

Dit is de stelling die de kans met de frequentie verbindt: voor $X_k$ de indicator van een gebeurtenis $A$ in onafhankelijke herhalingen is $S_n/n$ de waargenomen frequentie van $A$ , en de wet van de grote aantallen zegt dat zij zich rond $\P(A)$ concentreert met tempo $\frac{p(1-p)}{n\varepsilon^2}$ . De sterke wet ( $S_n/n \to m$ bijna zeker) is een stelling voor bachelorjaar 3 — haar bewijs bij vierde momenten is nochtans binnen bereik: zie Oefening 22.9, dat Borel–Cantelli op de grens van het type Chebyshev laat lopen. Dezelfde schatting van Chebyshev dreef het bewijs met de veeltermen van Bernstein van de benaderingsstelling van Weierstrass in Hoofdstuk 10 aan — de telhulpstelling daar was de zwakke wet van de grote aantallen in vermomming.

Voorbeeld 22.27 (Vijftig plaatjes verzamelen)

De plaatjesverzamelaar van Oefening 22.3 met $n = 50$ verschillende speeltjes: het verwachte totaal is

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

dozen — viereneenhalf maal de naïeve schatting $50$ . De harmonische groei is het hele verhaal: de eerste $25$ speeltjes komen in ongeveer $50\ln2 \approx 35$ dozen binnen, terwijl het laatste speeltje alleen al gemiddeld $50$ dozen kost (een meetkundige wachttijd met parameter $\frac1{50}$ ). Voltooiingsproblemen worden door hun eindspel beheerst, en daarom vindt Oefening 22.12 fluctuaties van de orde $n$ — de grootte van die laatste meetkundige wachttijd — rond het gemiddelde $n\ln n$ .

Voorbeeld 22.28 (Hoe groot moet $n$ zijn?)

Om de waargenomen frequentie tot op $\varepsilon = 0.01$ van $\P(A)$ vast te pinnen met een betrouwbaarheid van $95\%$ , eist de grens van Chebyshev

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{dat wil zeggen}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

De afhankelijkheid is bruut in $\varepsilon$ (kwadratisch) en mild in de betrouwbaarheid (lineair in $1/\alpha$ ). Beide kenmerken zijn eigenschappen van de grens, niet van de waarheid: de exponentiële ongelijkheden van de weekendopgave verlagen de prijs van betrouwbaarheid van $1/\alpha$ tot $\ln(1/\alpha)$ — dezelfde specificatie zal daar ongeveer $18\,500$ waarnemingen kosten — terwijl de schaal $1/\varepsilon^2$ echt en onverbeterlijk is. Weten welk deel van een grens los zit, is even nuttig als de grens zelf.

De wet van de grote aantallen als beeld: de verdeling van S_n/n (schematisch getekend) behoudt haar middelpunt m maar versmalt naarmate n groeit, zodat de kans buiten de band [m- , m+ ] — de twee staarten — naar nul krimpt. Chebyshev begrenst de staarten door V(X_1)/(n 2); de weekendopgave toont dat zij in werkelijkheid exponentieel klein zijn. — De wet van de grote aantallen als beeld: de verdeling van $S_n/n$ (schematisch getekend) behoudt haar middelpunt $m$ maar versmalt naarmate $n$ groeit, zodat de kans buiten de band $\intcc{m-\varepsilon}{m+\varepsilon}$ — de twee staarten — naar nul krimpt. Chebyshev begrenst de staarten door $V(X_1)/(n\varepsilon^2)$ ; de weekendopgave toont dat zij in werkelijkheid exponentieel klein zijn.

Opmerking 22.29 (Vooruitblik binnen dit volume)

Vooruit voedt alles hier Hoofdstuk 23: de verwachtingswaarde $\E(t^X)$ van één listige functie van $X$ pakt de hele verdeling in een machtreeks, momenten worden afgeleiden in $1$ , en identiteiten van het type Wald voor toevallige sommen dragen de theorie van de vertakkingsprocessen; de productstelling voor onafhankelijke veranderlijken wordt de multiplicativiteit van genererende functies. Terugkijkend is de verwachtingswaarde een barycentrum met kansgewichten (Hoofdstuk 17), is de ongelijkheid van Jensen de meetkunde van de steunrechte van convexe functies (Hoofdstuk 8), en is de methode van het exponentiële moment uit de weekendopgave van dit hoofdstuk Markov toegepast op $\eu^{tX}$ — één ongelijkheid, verscherpt met één goede verandering van veranderlijke, over drie hoofdstukken heen.

22.5 Oefeningen

Oefening 22.1 ★

Bereken $\E(X)$ en $V(X)$ voor $X \sim \mathcal{B}(n, p)$ (via indicatoren), $X \sim \mathcal{P}(\lambda)$ (toon aan dat $V(X) = \lambda$ ) en $X \sim \mathcal{G}(p)$ (toon aan dat $V(X) = \frac{1-p}{p^2}$ ; gebruik $\E(X(X-1))$ en de tweede afgeleide van de meetkundige reeks).

Oplossing

Oplossing van Oefening 22.1.

Binomiaal: $X = \sum_{i=1}^n X_i$ met onafhankelijke bernoulli-veranderlijken $X_i$ ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , en varianties van onafhankelijke veranderlijken tellen op (Stelling 22.14):

\E(X) = np, \qquad V(X) = np(1-p) .

Poisson: $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ , dus

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

Meetkundig ( $q = 1 - p$ ): $\sum_{k\geq0}q^k = \frac{1}{1-q}$ tweemaal binnen de schijf differentiëren (Hoofdstuk 11) geeft $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , dus

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

Oefening 22.2 ★

Zijn $X \sim \mathcal{P}(\lambda)$ en $Y \sim \mathcal{P}(\mu)$ onafhankelijk. Toon aan dat $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolutie van de gewichten; binomium), en dat de voorwaardelijke verdeling van $X$ gegeven $X + Y = n$ binomiaal $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ is.

Oplossing

Oplossing van Oefening 22.2.

Som: voor $n \in \N$ geldt, wegens de disjunctheid en de onafhankelijkheid,

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

volgens het binomium: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Voorwaardelijke verdeling: voor $0 \leq k \leq n$ is

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

de binomiale verdeling $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : gegeven het totale aantal “kiest” elke gebeurtenis onafhankelijk haar eerste bron met een kans evenredig aan haar tempo.

Oefening 22.3 ★

(Plaatjesverzamelaar, verwachtingswaarde) Een ontbijtgraanmerk verstopt in elke doos uniform een van $n$ verschillende speeltjes. Zij $T_n$ het aantal dozen dat nodig is om alle $n$ speeltjes te verzamelen. Schrijf $T_n$ als een som van onafhankelijke meetkundige veranderlijken (de tijd tot een nieuw speeltje wanneer er nog $k$ ontbreken) en toon aan dat

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(equivalent volgens de vergelijking van reeks en integraal uit Hoofdstuk 6).

Oplossing

Oplossing van Oefening 22.3.

Wanneer er nog $k$ speeltjes ontbreken, brengt elke nieuwe doos met kans $\frac kn$ een nieuw speeltje, onafhankelijk van het verleden: de wachttijd $W_k$ tot het volgende nieuwe speeltje is meetkundig $\mathcal{G}\bigl(\frac kn\bigr)$ , met $\E(W_k) = \frac nk$ , en $T_n = W_n + W_{n-1} + \dots + W_1$ (de eerste doos geeft altijd een nieuw speeltje: $W_n = 1$ , in overeenstemming met $\E = n/n$ ). Wegens de lineariteit is

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

met $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (Hoofdstuk 6). De laatste paar speeltjes verzamelen is wat kost: de helft van de dozen gaat naar de laatste handvol.

Oefening 22.4 ★★

Zij $X \geq 0$ met gehele waarden. Bewijs de staartformule

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(wanneer een van beide leden eindig is), door $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ te schrijven en de sommaties te verwisselen (Fubini voor niet-negatieve families). Vind $\E(X) = \frac1p$ voor de meetkundige verdeling terug.

Oplossing

Oplossing van Oefening 22.4.

Puntsgewijs is $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . De dubbele familie $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ is niet-negatief, dus is Fubini voor families (Hoofdstuk 7) onvoorwaardelijk van toepassing: eerst in $n$ sommeren geeft $\E(X)$ , eerst in $\omega$ sommeren geeft $\sum_n \P(X \geq n)$ ; de twee zijn tegelijk eindig en gelijk. Voor $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), dus $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Oefening 22.5 ★★

(Steekproeven zonder teruglegging zijn sterker geconcentreerd) Een urne bevat $N$ ballen, waarvan $M$ wit. Trek er $n \leq N$ zonder teruglegging en laat $X$ de witte tellen (hypergeometrische verdeling). Toon met indicatoren $X = \sum_{i=1}^n Y_i$ , waarbij $Y_i$ de $i$ -de trekking is, aan dat elke $Y_i$ bernoulli met parameter $p = M/N$ is (symmetrie!), besluit dat $\E(X) = np$ precies als met teruglegging, en toon aan dat $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ voor $i \neq j$ , zodat $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Oplossing

Oplossing van Oefening 22.5.

Symmetrie: de $i$ -de getrokken bal is een uniform willekeurige bal uit de urne (elke van de $N$ ballen heeft evenveel kans om op positie $i$ van de trekvolgorde te belanden), dus $\P(Y_i = 1) = \frac MN = p$ en $\E(X) = np$ wegens de lineariteit — geen onafhankelijkheid nodig.

Covariantie: voor $i \neq j$ is $\E(Y_iY_j) = \P(\text{trekkingen } i, j \text{ beide wit}) = \frac{M(M-1)}{N(N-1)}$ (geordende paren verschillende posities krijgen uniform een geordend paar verschillende ballen). Bijgevolg is

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

een witte bal trekken maakt wit schaarser voor de andere trekkingen. Volgens Stelling 22.14 is

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

steekproeven zonder teruglegging hebben hetzelfde gemiddelde maar een kleinere variantie dan met teruglegging (gelijkheid alleen voor $n = 1$ ), waarbij de negatieve correlaties als stabilisator werken. Voor $n = N$ verdwijnt de variantie: de telling is dan deterministisch.

Oefening 22.6 ★★

Zij $X$ met een tweede moment. Toon aan dat $c \mapsto \E\bigl((X - c)^2\bigr)$ precies in $c = \E(X)$ minimaal is, met minimum $V(X)$ . Toon vervolgens aan dat $\P(X = \E(X)) = 1$ dan en slechts dan als $V(X) = 0$ . (Voor het tweede punt: is $V(X) = 0$ , gebruik dan Chebyshev met $\varepsilon = 1/n$ en de monotone continuïteit, Stelling 21.6.)

Oplossing

Oplossing van Oefening 22.6.

Uitwerken rond $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

minimaal precies in $c = m$ met waarde $V(X)$ — de verwachtingswaarde is de beste constante voorspeller in kwadratisch gemiddelde.

Is $\P(X = m) = 1$ , dan verdwijnt $(X - m)^2$ met kans $1$ , dus $V(X) = 0$ (de definiërende familie heeft nultermen behalve op een nulverzameling). Omgekeerd, is $V(X) = 0$ , dan geeft Chebyshev (Stelling 22.15) dat $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ voor elke $n$ ; de gebeurtenissen $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ stijgen naar $\{X \neq m\}$ , dus levert de monotone continuïteit (Stelling 21.6) dat $\P(X \neq m) = 0$ .

Oefening 22.7 ★★★

(Concentratie verslaat Markov) Zij $S_n \sim \mathcal{B}(n, \frac12)$ (het aantal keer kop in $n$ eerlijke worpen). Vergelijk de grenzen gegeven door Markov ( $\P(S_n \geq \frac{3n}{4})$ ), door Chebyshev, en door de exponentiële methode (Chernoff):

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

en optimaliseer $t$ om een exponentieel kleine grens te krijgen. (In $t = \ln 3$ : grens $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Oplossing

Oplossing van Oefening 22.7.

$\E(S_n) = \frac n2$ en $V(S_n) = \frac n4$ . Markov: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — een constante grens, nutteloos voor grote $n$ . Chebyshev: de gebeurtenis impliceert $\abs{S_n - \frac n2} \geq \frac n4$ , dus is de kans $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — zij vervalt, maar slechts polynomiaal. Chernoff: wegens de onafhankelijkheid is $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ , en Markov toegepast op $e^{tS_n} \geq e^{3nt/4}$ geeft voor elke $t > 0$

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

Minimaliseer de exponent: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ in $e^t = 3$ , dat wil zeggen $t = \ln 3$ , wat

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n

geeft, exponentieel klein. De hiërarchie Markov $\to$ Chebyshev $\to$ Chernoff is de standaardladder: elke sport past Markov toe op een sneller groeiende functie van de veranderlijke.

Oefening 22.8 ★★★

(Weierstrass opnieuw, kansrekenkundig) Zij $f \colon [0,1] \to \R$ continu en $S_n \sim \mathcal{B}(n, x)$ . Toon aan dat de veelterm van Bernstein $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ gelijk is aan $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ , en leid de schatting $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ uit Hoofdstuk 10 opnieuw af in deze kansrekenkundige taal (splits op $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ en gebruik Chebyshev).

Oplossing

Oplossing van Oefening 22.8.

Volgens de overdrachtsstelling (Stelling 22.7) toegepast op $f\bigl(\frac{S_n}{n}\bigr)$ met $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

Houd $\delta > 0$ vast en splits $\abs{f(S_n/n) - f(x)}$ op de gebeurtenis $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : buiten $D$ is het verschil hoogstens de continuïteitsmodulus $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; op $D$ hoogstens $2\norm f_\infty$ . Verwachtingswaarden nemen en Chebyshev gebruiken met $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

De uniforme continuïteit van $f$ op $[0, 1]$ maakt $\omega_f(\delta) \to 0$ : kies $\delta$ en dan $n$ , en $B_nf \to f$ uniform — de benaderingsstelling van Weierstrass uit Hoofdstuk 10, waarvan de “telhulpstelling” nu herkenbaar is als de ongelijkheid van Chebyshev voor de binomiale verdeling.

Oefening 22.9 ★★★

(Sterke wet bij vierde momenten) Zij $(X_k)$ onafhankelijk, identiek verdeeld en gecentreerd ( $\E X_1 = 0$ ), met $\E(X_1^4) < \infty$ . Toon, door $\E(S_n^4)$ uit te werken en de overlevende termen te tellen (alleen termen $\E(X_i^4)$ en $\E(X_i^2X_j^2)$ met $i \neq j$ ), aan dat $\E(S_n^4) \leq C n^2$ voor een constante $C$ . Leid af dat $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ voor elke $\varepsilon > 0$ (Markov op orde 4) en besluit met Borel–Cantelli (Stelling 21.25) dat $S_n/n \to 0$ bijna zeker, in de volgende passende formulering: de gebeurtenis $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ heeft kans $1$ .

Oplossing

Oplossing van Oefening 22.9.

Werk $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ uit en neem verwachtingswaarden. Wegens de onafhankelijkheid en het centreren verdwijnt elke term met een index die precies eenmaal voorkomt ( $\E(X_i) = 0$ zondert zich af). Overlevende termen: de $n$ diagonale termen $\E(X_i^4)$ , en de termen die twee paren gelijke indices koppelen, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ voor $i \neq j$ , die $3n(n-1)$ maal voorkomen: kies het ongeordende paar waarden ( $\binom n2$ manieren), en dan de $\frac{4!}{2!\,2!} = 6$ manieren om hen over de vier plaatsen te verdelen — $6\binom n2 = 3n(n-1)$ . Bijgevolg is, met $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen of Cauchy–Schwarz),

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

Markov op orde 4:

\P\Bigl(\Bigl|\frac{S_n}{n}\Bigr| \geq \varepsilon\Bigr) = \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr) \leq \frac{Cn^2}{n^4\varepsilon^4} = \frac{C}{n^2\varepsilon^4} ,

een sommeerbare reeks. Volgens Borel–Cantelli 1 (Stelling 21.25) heeft voor elke $j$ de gebeurtenis $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ kans $0$ , dus $\P\bigl(\bigcup_j B_j\bigr) = 0$ wegens de aftelbare subadditiviteit. Op het complement — met kans $1$ — is er voor elke $j$ een $N$ met $\abs{S_n/n} < \frac1j$ voor alle $n \geq N$ : precies $S_n/n \to 0$ . De sterke wet van de grote aantallen geldt onder een vierde moment; die hypothese schrappen (de stelling van Kolmogorov) is werk voor bachelorjaar 3.

Oefening 22.10 ★

Er wordt met twee eerlijke dobbelstenen geworpen; zij $M$ de grootste van de twee uitkomsten. Toon met de staartformule van Oefening 22.4 (eindige versie) aan dat

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

Oplossing

Oplossing van Oefening 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (beide dobbelstenen hoogstens $k$ , onafhankelijk), dus $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ en

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

ruim boven het gemiddelde $3.5$ van één dobbelsteen, zoals het een maximum betaamt.

Oefening 22.11 ★★

Zij $F_n$ het aantal vaste punten van een uniform willekeurige permutatie van $\{1, \dots, n\}$ ( $n \geq 2$ ). Bereken, door $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ te schrijven, dat $\E(F_n) = 1$ en $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ voor $i \neq j$ , en besluit dat $V(F_n) = 1$ : gemiddeld blijft één letter vast, met variantie precies $1$ , wat $n$ ook is.

Oplossing

Oplossing van Oefening 22.11.

Met $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , dus $\E(F_n) = n\cdot\frac1n = 1$ . Voor $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ , en dus

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

Volgens de gereedschapskist van de variantie (Stelling 22.14) is

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

Gemiddelde $1$ , variantie $1$ , onafhankelijk van $n$ — in overeenstemming met de poisson-limiet van het probleem van de overeenkomsten (Oefening 21.5).

Oefening 22.12 ★★★

(Plaatjesverzamelaar, concentratie) Toon in de situatie van Oefening 22.3 aan dat

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

met de onafhankelijkheid van de meetkundige fasen en $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Oefening 22.1; de waarde $\pi^2/6$ is Voorbeeld 14.12). Leid met Chebyshev af dat $\dfrac{T_n}{n\ln n} \to 1$ in kans: de totale tijd van de verzamelaar is $n\ln n$ , op fluctuaties van de orde $n$ na.

Oplossing

Oplossing van Oefening 22.12.

$T_n = \sum_{k=1}^nG_k$ , waarbij $G_k \sim \mathcal G(k/n)$ de tijd is tot een nieuw speeltje wanneer er $k$ ontbreken, en de fasen onafhankelijk zijn. Bijgevolg is

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

volgens Voorbeeld 14.12. Met $\E(T_n) = nH_n$ en $H_n = \sum_1^n\frac1k$ (Oefening 22.3) geeft Chebyshev voor $\varepsilon > 0$

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

Omdat $H_n \sim \ln n$ , toont delen door $n\ln n$ dat $T_n/(n\ln n) \to 1$ in kans: de fluctuaties van $T_n$ zijn van de orde $n$ , verwaarloosbaar tegenover het gemiddelde $n\ln n$ .

22.6 Probleem: de gereedschapskist van de concentratie, van Markov tot Hoeffding

Probleem 22.1

Weekendopgave — exponentiële concentratie met de hand, en hoeveel mensen een peiling moet bevragen

De ongelijkheid van Markov kost één moment en koopt een verval $1/a$ ; Chebyshev kost twee momenten en koopt $1/\varepsilon^2$ — en Voorbeeld 22.18 toont dat dit alles is wat die momenten kunnen kopen. Deze opgave beklimt de rest van de ladder: de exponentiële methode (Chernoff) met haar exacte tempo voor muntworpen, de ongelijkheid van Hoeffding voor alle begrensde veranderlijken, en de opbrengst — expliciete, eerlijke steekproefomvangen voor peilingen, verkiezingsuitspraken en het testen van munten. Overal is $S_n \sim \mathcal B(n, p)$ een som van $n$ onafhankelijke bernoulli-veranderlijken en $\widehat p_n = S_n/n$ de empirische frequentie.

Deel I — IJken op de eerlijke munt. Hier is $p = \frac12$ en $a \in \intoo{\frac12}{1}$ .

Markov op niveau $an$ : toon aan dat $\P(S_n \geq an) \leq \frac1{2a}$ , een grens die niet eens naar $0$ streeft. Waar verliest Markov zo veel?
Chebyshev: toon met de symmetrie van de eerlijke binomiale verdeling om $n/2$ aan dat

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

dat wil zeggen $\frac2n$ in $a = \frac34$ : eindelijk polynomiaal verval.
(Chernoff, algemeen niveau) Bereken $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ en optimaliseer $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ over $t > 0$ : toon aan dat de optimale $t$ gelijk is aan $\ln\frac{a}{1-a}$ en dat

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

Ga na dat $a = \frac34$ de grens $\bigl(2\cdot3^{-3/4}\bigr)^n$ van Oefening 22.7 teruggeeft.
(De exponent is exact) Zij $k = an$ een geheel getal. Bewijs uit het feit dat $\binom nk a^k(1-a)^{n-k}$ de grootste van de $n + 1$ termen van een kansverdeling is, dat $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ met $H(a) = -a\ln a - (1-a)\ln(1-a)$ , en leid de bijpassende ondergrens af:

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Zet de drie grenzen in een tabel voor $n = 100$ , $a = \frac34$ : Markov $\frac23$ , Chebyshev $0.02$ , Chernoff $\approx 2.1\cdot10^{-6}$ (de werkelijke waarde is $\approx 2.8\cdot10^{-7}$ ). De moraal, in één zin?

Deel II — De ongelijkheid van Hoeffding.

(Geval van Rademacher) Bewijs voor $\varepsilon = \pm1$ met elk kans $\frac12$ dat

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

door de twee reeksen term voor term te vergelijken ( $(2k)! \geq 2^kk!$ ).
Leid af, voor onafhankelijke rademacher-veranderlijken $\varepsilon_1, \dots, \varepsilon_n$ en elke $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Vertaal naar eerlijke munten ( $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , en de tweezijdige versie met een factor $2$ .
(Hulpstelling van Hoeffding) Zij $X \in \intcc01$ met $\E X = p$ , en $\psi(t) = \ln\E(\eu^{tX})$ . Verantwoord dat $\psi$ tweemaal differentieerbaar is met

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

een variantie van een herwogen veranderlijke die nog altijd waarden in $\intcc01$ aanneemt; begrens haar door $\frac14$ (het minimaliteitsargument van Oefening 22.6) en besluit met Taylor:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(Ongelijkheid van Hoeffding) Leid voor onafhankelijke $X_i \in \intcc01$ met gemeenschappelijk gemiddelde $p$ af dat

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Vergelijk het tempo $\frac{p(1-p)}{n\delta^2}$ van Chebyshev met $2\eu^{-2n\delta^2}$ van Hoeffding: welke hypothese vereist elk, en vanaf welke $n$ (ruwweg) wint de exponentiële grens bij $\delta = 0.03$ , $p = \frac12$ ?

Deel III — Hoeveel mensen moet een peiling bevragen? Een peiling bevraagt $n$ onafhankelijke, uniform gekozen kiezers; elk antwoordt eerlijk; $p$ is de werkelijke score en $\widehat p_n$ het cijfer van de peiling.

Toon aan dat de peiling tot op $\pm\delta$ nauwkeurig is met betrouwbaarheid $1 - \alpha$ (dat wil zeggen $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) zodra

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Bereken de vereiste $n$ voor de gebruikelijke specificatie “drie punten, vijfennegentig procent” ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; en voor één punt: $n \geq 18\,445$ . Merk het opvallende feit op — en verklaar het — dat het antwoord de omvang van de bevolking niet bevat.
Doe vraag 13 opnieuw met Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ bij drie punten. Merk op dat steekproeven zonder teruglegging alleen maar helpen (Oefening 22.5: de variantie krimpt met $\frac{N-n}{N-1}$ ).
(Een verkiezing uitroepen) De werkelijke score van een kandidaat is $p = 0.52$ . Hoeveel kiezers moeten worden bevraagd opdat $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Toon aan dat $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — een nek-aan-nekrace uitroepen kost veel meer dan een score schatten.
Wat de wiskunde niet dekt: som de aannames van het model op (onafhankelijke uniforme steekproeven, eerlijke antwoorden, vaste $p$ ), en leg in een korte alinea uit waarom echte peilingsfouten door vertekening worden beheerst (niet-uniforme steekproeven, weigeringen), die geen enkele verhoging van $n$ verkleint.

Deel IV — Scherper en goedkoper.

(Mediaan van gemiddelden: exponentieel verval uit twee momenten) Verdeel een budget van $km$ waarnemingen over $k$ onafhankelijke groepen van $m$ ; zijn $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ de groepsgemiddelden en $M$ hun mediaan. Kies $m$ zo dat elke groep voldoet aan $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (Chebyshev: $m \geq \frac2{\delta^2}$ volstaat). Toon aan dat als $\abs{M - p} \geq \delta$ , dan minstens $k/2$ groepen fout zitten, en leid af dat

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

exponentiële concentratie met niets meer dan varianties.
(Paley–Zygmund) Bewijs voor $X \geq 0$ met een tweede moment dat $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz op $X\mathbf 1_{X>0}$ ): het gereedschap in de omgekeerde richting — momenten kunnen gebeurtenissen ook afdwingen.
(Pinsker, lichte versie) Toon aan dat $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ op $\intoo{\frac12}1$ (het verschil verdwijnt tot op tweede orde in $\frac12$ en zijn tweede afgeleide is $\frac1{a(1-a)} - 4 \geq 0$ ): de exacte exponent van Chernoff verslaat altijd de kwadratische van Hoeffding.
Ontwikkel $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ en combineer met vraag 4: voor kleine afwijkingen is de exponent $2n\delta^2$ van Hoeffding asymptotisch exact — geen enkele methode kan hem met meer dan polynomiale factoren verslaan.
Stel de tabel van de gereedschapskist op: geef voor Markov, Chebyshev, de grens met het vierde moment van Oefening 22.9, Hoeffding en Chernoff met exponent $I$ telkens in één regel: de vereiste hypothese, het verkregen verval, en de vraag in deze opgave waar zij het scherpst was.

Deel V — Dividenden.

(Een munt testen) Een munt is ofwel eerlijk ofwel scheef met $p = 0.55$ . Je werpt haar $n$ maal en verklaart haar “scheef” wanneer $\widehat p_n > 0.525$ . Toon aan dat beide foutkansen hoogstens $\eu^{-2n(0.025)^2}$ zijn, en dat $n \geq 3685$ worpen beide onder $1\%$ waarborgen.
(Zeldzame gebeurtenissen hebben een variantiebewuste grens nodig) Zij $p = 0.01$ en neem de relatieve specificatie $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Vergelijk de steekproefomvangen die Hoeffding ( $n \approx 74\,000$ ) en Chebyshev met de echte variantie $p(1-p)$ ( $n \approx 7920$ ) eisen: de variantieblinde exponentiële grens verliest van het bescheiden tweede moment. Formuleer de moraal, en waar het ontbrekende gereedschap (een variantiebewuste exponentiële grens; de poisson-benadering van Hoofdstuk 23) vandaan zal komen.
(Sterke wet voor munten) Bewijs uit $\sum_n 2\eu^{-2n\delta^2} < \infty$ en Borel–Cantelli (Stelling 21.25) dat $\widehat p_n \to p$ bijna zeker voor onafhankelijke muntworpen: formuleer de bijna-zekere gebeurtenis als $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ zoals in Oefening 22.9, en besluit. (De begrensdheid vervangt het vierde moment dat daar werd gebruikt.)
Synthese. In vijf zinnen: wat elke sport van de ladder (momenten één, twee, vier; begrensd exponentieel; exacte exponent) kost en koopt; waarom $2050$ mensen bevragen volstaat voor een land van welke omvang ook; en welke van deze grenzen het volume van bachelorjaar 3 tot de exacte constanten van de centrale limietstelling zal aanscherpen.

Oplossing

Oplossing van Probleem 22.1.

1. $\E(S_n) = \frac n2$ en Markov (Stelling 22.15) geven $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov kent alleen het gemiddelde: zij kan een veranderlijke die zich rond $n/2$ concentreert niet onderscheiden van een die tussen $0$ en $n$ is uitgesmeerd, en beprijst de staart dus alsof alle massa daar zou kunnen zitten.

2. De eerlijke binomiale verdeling is symmetrisch om $n/2$ ( $S_n$ en $n - S_n$ hebben dezelfde verdeling), dus zijn met $x = n(a - \frac12) > 0$ de twee gebeurtenissen $\{S_n - \frac n2 \geq x\}$ en $\{S_n - \frac n2 \leq -x\}$ disjunct en even waarschijnlijk: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Chebyshev met $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

wat $\frac2n$ is in $a = \frac34$ .

3. Wegens de onafhankelijkheid en de productstelling is $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . Markov toegepast op $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

De afgeleide van de exponent naar $t$ is $\frac{\eu^t}{1 + \eu^t} - a$ , die verdwijnt in $\eu^t = \frac a{1-a}$ , dat wil zeggen $t^* = \ln\frac a{1-a} > 0$ ; daar is $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ en is de exponent gelijk aan

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

met $I(\frac12) = 0$ en $I'(a) = \ln\frac a{1-a} > 0$ op $\intoo{\frac12}1$ : $I(a) > 0$ . In $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , de grens van Oefening 22.7.

4. De $n + 1$ getallen $\binom nja^j(1-a)^{n-j}$ sommeren tot $1$ , en het grootste is dat in $j = k = an$ (de modus van $\mathcal B(n, a)$ is hier $\floor{(n+1)a} = k$ ). Een maximum van $n + 1$ getallen die tot $1$ sommeren, is minstens $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

Bijgevolg is $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : op de polynomiale factor $n + 1$ na is de exponent van Chernoff de waarheid.

5. $n = 100$ , $a = \frac34$ : Markov $\frac23$ ; Chebyshev $\frac2{100} = 0.02$ ; Chernoff $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ , tegenover de exacte $2.8\cdot10^{-7}$ . Moraal: elk moment aan informatie deelt de grens polynomiaal; het exponentiële moment verandert haar aard.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ en $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; de bewering volgt term voor term uit $(2k)! \geq 2^kk!$ , dat met inductie geldt: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. Wegens de onafhankelijkheid is $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , dus geeft Markov dat $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; minimaliseren in $t = s/n$ levert $\eu^{-s^2/(2n)}$ .

8. Met $X_i = \frac{1 + \varepsilon_i}2$ is $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , dus $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ en geeft vraag 7 de grens $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . De symmetrische gebeurtenis heeft dezelfde grens, waaruit de factor $2$ voor $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ is een reeks van gladde functies van $t$ waarvan de termsgewijze afgeleiden op elk compact $t$ -interval worden gedomineerd door $\eu^{\abs t}\P(X = x)$ (want $0 \leq x \leq 1$ ): volgens de differentiatiestelling voor normaal convergente reeksen (Stelling 10.7) is zij tweemaal differentieerbaar, en de quotiëntregel geeft $\psi' = \E_t(X)$ en $\psi'' = \E_t(X^2) - \E_t(X)^2$ , waarbij $\E_t$ de verwachtingswaarde voor de herwogen gewichten $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ is — niet-negatief, sommerend tot $1$ , gedragen door dezelfde waarden $x \in \intcc01$ . Een variantie van een veranderlijke met waarden in $\intcc01$ is hoogstens $\frac14$ : volgens Oefening 22.6 is zij $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor met integraalrest, met $\psi(0) = 0$ en $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

dat wil zeggen $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ voor alle reële $t$ .

10. Wegens de onafhankelijkheid is $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov en de optimalisatie $t = 4\delta$ geven

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

dit toepassen op de veranderlijken $1 - X_i$ (ook in $\intcc01$ ) begrenst de andere staart, waaruit de tweezijdige $2\eu^{-2n\delta^2}$ .

11. Chebyshev heeft alleen een tweede moment nodig en geeft $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding heeft begrensdheid nodig en geeft $2\eu^{-2n\delta^2}$ . In $p = \frac12$ , $\delta = 0.03$ zijn de grenzen (bij benadering) $\frac{278}{n}$ tegenover $2\eu^{-0.0018n}$ ; zij kruisen elkaar rond $n \approx 1200$ , waarna de exponentiële grens wint, en dat overtuigend ( $n = 5000$ : $0.056$ tegenover $2.5\cdot10^{-4}$ ).

12. Volgens Hoeffding (vraag 10) is $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ zodra $2n\delta^2 \geq \ln\frac2\alpha$ , dat wil zeggen $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ , $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : $2050$ mensen. Voor $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . De omvang van de bevolking komt nooit voor omdat elke bevraagde kiezer als een verse trekking uit $\mathcal B(p)$ wordt gemodelleerd: de moeilijkheid van de peiling is de variantie van een munt, niet de grootte van het land. De marge halveren kost viermaal de steekproef — de wet $1/\delta^2$ .

14. Chebyshev: $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ voor $n \geq \frac1{4\alpha\delta^2}$ , dat wil zeggen $5556$ bij drie punten — ongeveer $2.7$ maal de eis van Hoeffding. Zonder teruglegging wordt de variantie met $\frac{N - n}{N-1} < 1$ vermenigvuldigd (Oefening 22.5), dus kan dezelfde $n$ het alleen beter doen: de berekening met teruglegging is de behoudende.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , dus geeft de eenzijdige grens van Hoeffding dat $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ zodra $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ kiezers. De kosten schalen met het omgekeerde kwadraat van de voorsprong, niet van de gewenste nauwkeurigheid: nek-aan-nekraces zijn duur.

16. Gebruikt: de steekproef wordt uniform en onafhankelijk uit het kiezerskorps getrokken; elke bevraagde antwoordt, en eerlijk; en $p$ beweegt niet tijdens de peiling. Echte peilingen schenden alle drie: bereikbare en bereidwillige respondenten vormen geen uniforme steekproef (selectie- en non-responsvertekening), en antwoorden kunnen onwaar of onstabiel zijn. Dat zijn vertekeningsfouten: zij verschuiven $\E(\widehat p_n)$ weg van $p$ met een hoeveelheid die niet van $n$ afhangt, dus verkleint geen enkele steekproefomvang hen — de wiskunde van dit deel beheerst alleen de fluctuatieterm.

17. Chebyshev voor één groep van omvang $m$ : $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ voor $m \geq \frac2{\delta^2}$ . Zitten minder dan $k/2$ groepen fout, dan liggen meer dan $k/2$ van de waarden $\widehat p^{(i)}$ in het open interval $\intoo{p - \delta}{p + \delta}$ , en hun mediaan dus ook; bijgevolg dwingt $\{\abs{M - p} \geq \delta\}$ minstens $\lceil k/2\rceil$ fouten onder $k$ onafhankelijke groepen af. De somgrens over de $\binom k{\lceil k/2\rceil}$ mogelijke verzamelingen foute groepen geeft

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

exponentieel verval in het aantal groepen, gekocht met niets dan varianties — nuttig precies wanneer de termen onbegrensd zijn en Hoeffding niet beschikbaar is.

18. Cauchy–Schwarz (Stelling 22.19):

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

kwadrateer en deel.

19. Zij $h(a) = I(a) - 2(a - \tfrac12)^2$ . Dan is $h(\tfrac12) = 0$ , verdwijnt $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ in $\tfrac12$ , en is

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

omdat $a(1-a) \leq \frac14$ . Dus stijgt $h'$ vanaf $0$ op $\intco{\frac12}1$ , waardoor $h' \geq 0$ en $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , en $I''(a) = \frac1{a(1-a)}$ geeft $I''(\tfrac12) = 4$ , terwijl $I'''(\tfrac12) = 0$ (de functie is symmetrisch om $\tfrac12$ ), dus $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . Vraag 4 begrenst de werkelijke staart dan van onder door $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : voor kleine $\delta$ is de exponent $2n\delta^2$ van Hoeffding asymptotisch exact — alleen verbeteringen polynomiaal in $n$ zijn mogelijk.

21. Markov: één moment, verval $1/a$ , alleen nuttig als motor achter de andere (vraag 1 toont haar vlak). Chebyshev: twee momenten, verval $\frac{V}{n\delta^2}$ , scherp zonder verdere hypothesen (Voorbeeld 22.18), en het beste gereedschap bij vraag 23. Vierde moment (Oefening 22.9): verval $C/n^2$ , net genoeg sommeerbaarheid voor een sterke wet. Hoeffding: begrensde veranderlijken, verval $2\eu^{-2n\delta^2}$ , het werkpaard van Deel III. Chernoff met het exacte tempo $I(a)$ : volledige exponentiële momenten, een onverslaanbare exponent (vragen 4, 20), het ijkpunt voor al het overige.

22. Is de munt eerlijk: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Is $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . Beide fouten liggen onder $0.01$ wanneer $2n(0.025)^2 \geq \ln 100$ , dat wil zeggen $n \geq 3684.2$ : $3685$ worpen. (Hypothesen die $2.5$ punten uit elkaar liggen onderscheiden kost wat schatten tot op $\pm2.5$ punten kost.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev met de echte variantie $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — negen maal goedkoper. De exponent $2n\delta^2$ van Hoeffding beprijst de variantie op haar slechtste geval $\frac14$ , absurd pessimistisch wanneer $p = 0.01$ ; het bescheiden tweede moment weet beter. Het ontbrekende gereedschap is een variantiebewuste exponentiële grens (de ongelijkheid van Bernstein, bachelorjaar 3) — of, voor zeldzame gebeurtenissen, de poisson-benadering bewezen in Hoofdstuk 23, die op de natuurlijke relatieve schaal werkt.

24. Houd $\delta > 0$ vast: $\sum_n 2\eu^{-2n\delta^2} < \infty$ (een reeks van meetkundig type), dus geeft Borel–Cantelli 1 (Stelling 21.25) dat $\P(\abs{\widehat p_n - p} \geq \delta \text{ oneindig vaak}) = 0$ , dat wil zeggen dat de gebeurtenis $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ voor elke $j$ kans $1$ heeft. De aftelbare doorsnede $\bigcap_jE_j$ heeft nog altijd kans $1$ (subadditiviteit op de complementen), en daarop is $\widehat p_n \to p$ : de sterke wet van de grote aantallen voor muntworpen, waarbij de begrensdheid de rol speelt die het vierde moment in Oefening 22.9 speelde.

25. Eén moment koopt een vlakke grens; twee kopen $1/(n\delta^2)$ , en niet meer (het voorbeeld van de scherpte); vier kopen $1/n^2$ , genoeg om tot een bijna-zekere wet te telescoperen; begrensdheid koopt $\eu^{-2n\delta^2}$ ; en het volledige exponentiële moment koopt het exacte tempo $I$ , dat geen enkele methode verslaat. $2050$ mensen bevragen volstaat voor elk land omdat de fluctuatie van de steekproef door de variantie van de munt wordt bestuurd, niet door de omvang van de bevolking — de prijskaartjes $1/\delta^2$ en $\ln(1/\alpha)$ zijn universeel. De centrale limietstelling van het volume van bachelorjaar 3 vervangt deze ongelijkheden op de schaal $\sqrt n$ door een exacte limietverdeling met expliciete constanten — waarmee elke grens van deze opgave in een asymptotische gelijkheid verandert.