--- title: "Discrete toevalsveranderlijken" book: "Universitaire wiskunde — Bachelor jaar 2" subject: math language: nl chapter: 22 exercises: 12 source: https://one-course.com/books/math/4/nl/chapter/22-discrete-toevalsveranderlijken --- # Hoofdstuk 22 — Discrete toevalsveranderlijken [Toevalsveranderlijken](#def-b2-randomvar-law) ordenen kansberekeningen rond functies in plaats van rond [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space). Op [aftelbare](https://one-course.com/books/math/4/nl/chapter/1-verzamelingen-en-structuren#def-b2-structures-countable) ruimten wordt de theorie aangedreven door de [sommeerbare families](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) van [Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series): de [verwachtingswaarde](#def-b2-randomvar-expectation) is de som van een familie geïndexeerd door de [uitkomstenruimte](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space), en al haar eigenschappen — lineariteit, overdracht, de productformule voor [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) veranderlijken — zijn stellingen over [sommeerbare families](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable). Het hoofdstuk bewijst de sleutelongelijkheden van Markov, Chebyshev, Cauchy–Schwarz en Jensen, en eindigt met de klassieke [verdelingen](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/nl/chapter/1-verzamelingen-en-structuren#def-b2-structures-countable) [kansruimte](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space). 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\P_X$ op de [aftelbare verzameling](https://one-course.com/books/math/4/nl/chapter/1-verzamelingen-en-structuren#def-b2-structures-countable) $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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) . - *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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) bernoulli-experimenten (bovenbouwvolume; hieronder opnieuw bewezen via sommen van [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#ex-b2-proba-geometric) ). - *Poisson* $\mathcal{P}(\lambda)$ : $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ , $k \in \N$ — een [kansmaat](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) wegens de exponentiële reeks. De [verdeling](#def-b2-randomvar-law) van de zeldzame [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) ( [Hoofdstuk 23](https://one-course.com/books/math/4/nl/chapter/23-kansgenererende-functies#ch-b2-genfun) ). **Opmerking 22.3 (Welke verdeling modelleert wat).** De vier [verdelingen](#def-b2-randomvar-law) beantwoorden vier oervragen: Bernoulli, “is het gebeurd?”; binomiaal, “hoe vaak in $n$ pogingen?”; meetkundig, “hoe lang tot de eerste keer?”; Poisson, “hoeveel [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) op de [poisson-verdeling](#def-b2-randomvar-law) — waarbij de overgang van binomiaal naar Poisson door de [verdeling](#def-b2-randomvar-law) van de zeldzame [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) in [Hoofdstuk 23](https://one-course.com/books/math/4/nl/chapter/23-kansgenererende-functies#ch-b2-genfun) 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](#def-b2-randomvar-law) zijn de enige [verdelingen](#def-b2-randomvar-law) 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](#def-b2-randomvar-law) $\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](#def-b2-randomvar-law) 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](#def-b2-randomvar-law) $X$ op $(\Omega, \P)$ *heeft een verwachtingswaarde* wanneer de familie $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ [sommeerbaar](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) is ([Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)); haar *verwachtingswaarde* is dan $$ \E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) . $$ **Stelling 22.7 (Overdrachtsstelling).** $X$ heeft een [verwachtingswaarde](#def-b2-randomvar-expectation) dan en slechts dan als de familie $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ [sommeerbaar](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) 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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) ([Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)) is de familie $(X(\omega)\P(\{\omega\}))_\omega$ [sommeerbaar](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) 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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) 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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) van de ene familie gelijkwaardig is met die van de andere. ∎ **Stelling 22.8 (Eigenschappen van de verwachtingswaarde).** Op de verzameling [toevalsveranderlijken](#def-b2-randomvar-law) met [verwachtingswaarde](#def-b2-randomvar-expectation): 1. (Lineariteit) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ . 2. (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)$ . 3. (Dominatie) Is $\abs X \leq Z$ en heeft $Z$ een [verwachtingswaarde](#def-b2-randomvar-expectation) , dan heeft $X$ er ook een. **Bewijs.** Alle zijn eigenschappen van sommen van [sommeerbare families](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) ([Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)): de lineariteit van de som, de positiviteit term voor term, en het dominatiecriterium voor de [sommeerbaarheid](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable). (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](https://one-course.com/books/math/4/nl/chapter/11-machtreeksen#ch-b2-powerseries)). $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](#def-b2-randomvar-law) 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](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-expectation) van [convexe](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-convex) 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](#def-b2-randomvar-law) $X, Y$ heten *[onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence)* wanneer $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ voor alle $x, y$ — gelijkwaardig: wanneer de [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\{X \in A\}$ en $\{Y \in B\}$ [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) zijn voor alle $A, B$. Zijn $X$ en $Y$ [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) reële veranderlijken met [verwachtingswaarden](#def-b2-randomvar-expectation), dan heeft $XY$ een [verwachtingswaarde](#def-b2-randomvar-expectation) en is $$ \E(XY) = \E(X)\,\E(Y) . $$ **Bewijs.** De gelijkwaardigheid van de twee formuleringen volgt door de [puntsgewijze](https://one-course.com/books/math/4/nl/chapter/10-rijen-en-reeksen-van-functies#def-b2-funcseq-def) 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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable), want volgens Fubini voor families ([Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#def-b2-randomvar-law) in beide scenario’s, verschillende gezamenlijke [verdelingen](#def-b2-randomvar-law), verschillende [verwachtingswaarden](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-variance) $\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](#def-b2-randomvar-expectation) 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: 1. $V(aX + b) = a^2\,V(X)$ ; 2. $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) ;$$ 3. zijn $X, Y$ [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) , dan is $\operatorname{Cov}(X, Y) = 0$ (het omgekeerde is onwaar), zodat de [varianties](#def-b2-randomvar-variance) van [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) veranderlijken optellen. **Bewijs.** *1* en *2* zijn het uitwerken van kwadraten plus de lineariteit; de producten $X_iX_j$ hebben [verwachtingswaarden](#def-b2-randomvar-expectation) volgens Cauchy–Schwarz hieronder (of wegens $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$). *3* is [Stelling 22.11](#thm-b2-randomvar-product) 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).** 1. (Markov) Heeft $X \geq 0$ een [verwachtingswaarde](#def-b2-randomvar-expectation), dan is voor elke $a > 0$ $$\P(X \geq a) \leq \frac{\E(X)}{a} .$$ 2. (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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) is het linkerlid $a \leq X$; erbuiten $0 \leq X$). Neem [verwachtingswaarden](#def-b2-randomvar-expectation): $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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\{(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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), en zet $S = X + Y$, $D = X - Y$. Wegens de bilineariteit van de [covariantie](#def-b2-randomvar-variance) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence)? 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](#def-b2-randomvar-variance). (Voor dit paar had de nulcovariantie $V(X) = V(Y)$ nodig: gelijke [verdelingen](#def-b2-randomvar-law), niet de [onafhankelijkheid](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), 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](#def-b2-randomvar-variance) — 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](#exo-b2-randomvar-7) voorproeft en de weekendopgave van dit hoofdstuk stelselmatig ontwikkelt. **Stelling 22.19 (Cauchy–Schwarz en Jensen).** 1. (Cauchy–Schwarz) Hebben $X, Y$ tweede momenten, dan heeft $XY$ een [verwachtingswaarde](#def-b2-randomvar-expectation) en is $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; bijgevolg $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ . 2. (Jensen) Is $\varphi \colon I \to \R$ [convex](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-convex) op een interval dat $X(\Omega)$ bevat, en hebben $X$ en $\varphi(X)$ [verwachtingswaarden](#def-b2-randomvar-expectation), dan is $$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$$ **Bewijs.** *1.* [Sommeerbaarheid](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) van $XY$: $\abs{XY} \leq \frac{X^2 + Y^2}2$. De afbeelding $(X, Y) \mapsto \E(XY)$ is een positieve [symmetrische bilineaire vorm](https://one-course.com/books/math/4/nl/chapter/12-kwadratische-vormen#def-b2-quadratic-def) op de ruimte van veranderlijken met tweede momenten, dus is de abstracte ongelijkheid van Cauchy–Schwarz uit [Hoofdstuk 12](https://one-course.com/books/math/4/nl/chapter/12-kwadratische-vormen#ch-b2-quadratic) van toepassing (positief *semi*definiet volstaat voor de ongelijkheid). Haar toepassen op de gecentreerde veranderlijken geeft de grens voor de [covariantie](#def-b2-randomvar-variance). *2.* Ten eerste ligt $m = \E(X)$ in $I$: $I$ is een interval dat alle waarden van $X$ bevat, en de [verwachtingswaarde](#def-b2-randomvar-expectation) is monotoon, dus ligt $m$ tussen $\inf X(\Omega)$ en $\sup X(\Omega)$. Volgens de stelling over de steunrechte voor convexe functies ([Hoofdstuk 8](https://one-course.com/books/math/4/nl/chapter/8-functies-van-een-reele-veranderlijke#ch-b2-realfun)) 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](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-variance); 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) (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](#def-b2-randomvar-variance) tellen alleen op over [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) (of ongecorreleerde) termen. (iii) $\E(f(X))$ is niet $f(\E(X))$; voor [convexe](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-convex) $f$ vertelt Jensen zelfs de richting van de fout, als in [Voorbeeld 22.10](#ex-b2-randomvar-transferex). (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](#def-b2-randomvar-expectation), en er bestaat geen eerlijke inzet voor het spel. De [sommeerbaarheid](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) in de definitie van $\E$ is geen boekhoudkundige muggenzifterij — het is waar zware staarten worden opgespoord. (v) Ten slotte heeft de overdrachtsstelling *absolute* [sommeerbaarheid](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) nodig voordat enige herschikking van de som over de waarden geoorloofd is ([Hoofdstuk 7](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)). **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](#def-b2-randomvar-variance) — hetzelfde certificaat geldt woordelijk voor elke veranderlijke met $\E = 50$ en $V = 25$, hoe exotisch ook, en [Voorbeeld 22.18](#ex-b2-randomvar-chebsharp) toont dat een zekere zulke veranderlijke haar verzadigt. Universaliteit heeft een prijs; is de [verdeling](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), identiek verdeelde $X, Y$ met [variantie](#def-b2-randomvar-variance) $\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](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-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](#def-b2-randomvar-law) kiezen is slechts een boekhoudkundig hulpmiddel voor [convexe](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-convex) combinaties — opnieuw het barycentrische standpunt van [Hoofdstuk 17](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#ch-b2-affine), 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) [toevalsveranderlijken](#def-b2-randomvar-law) met dezelfde [verdeling](#def-b2-randomvar-law), 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](#thm-b2-randomvar-variancerules) (de paarsgewijze [onafhankelijkheid](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) doodt de [covarianties](#def-b2-randomvar-variance)) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $A$ in [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/nl/chapter/10-rijen-en-reeksen-van-functies#ch-b2-funcseq) 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](#exo-b2-randomvar-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](#exo-b2-randomvar-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 nnn 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-randomvar/fig-340511e0f8ad.svg) *De wet van de grote aantallen als beeld: de [verdeling](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/nl/chapter/23-kansgenererende-functies#ch-b2-genfun): de [verwachtingswaarde](#def-b2-randomvar-expectation) $\E(t^X)$ van één listige functie van $X$ pakt de hele [verdeling](#def-b2-randomvar-law) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) veranderlijken wordt de multiplicativiteit van [genererende functies](https://one-course.com/books/math/4/nl/chapter/11-machtreeksen#ex-b2-powerseries-fibonacci). Terugkijkend is de [verwachtingswaarde](#def-b2-randomvar-expectation) een [barycentrum](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#def-b2-affine-barycenter) met kansgewichten ([Hoofdstuk 17](https://one-course.com/books/math/4/nl/chapter/17-affiene-ruimten#ch-b2-affine)), is de ongelijkheid van Jensen de meetkunde van de steunrechte van convexe functies ([Hoofdstuk 8](https://one-course.com/books/math/4/nl/chapter/8-functies-van-een-reele-veranderlijke#ch-b2-realfun)), 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 van Oefening 22.1.** *Binomiaal:* $X = \sum_{i=1}^n X_i$ met [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) bernoulli-veranderlijken $X_i$; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$, en [varianties](#def-b2-randomvar-variance) van [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) veranderlijken tellen op ([Stelling 22.14](#thm-b2-randomvar-variancerules)): $$ \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](https://one-course.com/books/math/4/nl/chapter/11-machtreeksen#ch-b2-powerseries)) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence). Toon aan dat $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolutie van de gewichten; binomium), en dat de voorwaardelijke [verdeling](#def-b2-randomvar-law) van $X$ gegeven $X + Y = n$ binomiaal $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ is. **Oplossing van Oefening 22.2.** *Som:* voor $n \in \N$ geldt, wegens de disjunctheid en de [onafhankelijkheid](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), $$ \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](#def-b2-randomvar-law):* 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](#def-b2-randomvar-law) $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$: gegeven het totale aantal “kiest” elke [gebeurtenis](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) haar eerste bron met een kans evenredig aan haar tempo. **Oefening 22.3 ★.** (Plaatjesverzamelaar, [verwachtingswaarde](#def-b2-randomvar-expectation)) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/6-vergelijking-van-functies#ch-b2-comparison)). **Oplossing van Oefening 22.3.** Wanneer er nog $k$ speeltjes ontbreken, brengt elke nieuwe doos met kans $\frac kn$ een nieuw speeltje, [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/6-vergelijking-van-functies#ch-b2-comparison)). 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](#def-b2-randomvar-law) terug. **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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#ch-b2-series)) 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](#def-b2-randomvar-law)). 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 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) nodig. *[Covariantie](#def-b2-randomvar-variance):* 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](#thm-b2-randomvar-variancerules) 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](#def-b2-randomvar-variance) dan met teruglegging (gelijkheid alleen voor $n = 1$), waarbij de negatieve correlaties als stabilisator werken. Voor $n = N$ verdwijnt de [variantie](#def-b2-randomvar-variance): 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](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-continuity), [Stelling 21.6](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-continuity).)* **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](#def-b2-randomvar-expectation) 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](#thm-b2-randomvar-markov)) dat $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ voor elke $n$; de [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ stijgen naar $\{X \neq m\}$, dus levert de monotone [continuïteit](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-continuity) ([Stelling 21.6](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-continuity)) 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 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-continuity) 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](https://one-course.com/books/math/4/nl/chapter/10-rijen-en-reeksen-van-functies#ch-b2-funcseq) opnieuw af in deze kansrekenkundige taal (splits op $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ en gebruik Chebyshev). **Oplossing van Oefening 22.8.** Volgens de overdrachtsstelling ([Stelling 22.7](#thm-b2-randomvar-transfer)) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $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](#def-b2-randomvar-expectation) 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](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-continuity) 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](https://one-course.com/books/math/4/nl/chapter/10-rijen-en-reeksen-van-functies#ch-b2-funcseq), waarvan de “telhulpstelling” nu herkenbaar is als de ongelijkheid van Chebyshev voor de binomiale [verdeling](#def-b2-randomvar-law). **Oefening 22.9 ★★★.** (Sterke wet bij vierde momenten) Zij $(X_k)$ [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-borelcantelli)) dat $S_n/n \to 0$ bijna zeker, in de volgende passende formulering: de [gebeurtenis](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ heeft kans $1$. **Oplossing van Oefening 22.9.** Werk $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ uit en neem [verwachtingswaarden](#def-b2-randomvar-expectation). Wegens de [onafhankelijkheid](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) reeks. Volgens Borel–Cantelli 1 ([Stelling 21.25](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-borelcantelli)) heeft voor elke $j$ de [gebeurtenis](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $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](https://one-course.com/books/math/4/nl/chapter/1-verzamelingen-en-structuren#def-b2-structures-countable) 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](#exo-b2-randomvar-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 van Oefening 22.10.** $\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (beide dobbelstenen hoogstens $k$, [onafhankelijk](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence)), 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](#def-b2-randomvar-variance) precies $1$, wat $n$ ook is. **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](#def-b2-randomvar-variance) ([Stelling 22.14](#thm-b2-randomvar-variancerules)) 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](#def-b2-randomvar-variance) $1$, onafhankelijk van $n$ — in overeenstemming met de poisson-limiet van het probleem van de overeenkomsten ([Oefening 21.5](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#exo-b2-proba-5)). **Oefening 22.12 ★★★.** (Plaatjesverzamelaar, concentratie) Toon in de situatie van [Oefening 22.3](#exo-b2-randomvar-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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) van de meetkundige fasen en $V(\mathcal G(p)) = \frac{1-p}{p^2}$ ([Oefening 22.1](#exo-b2-randomvar-1); de waarde $\pi^2/6$ is [Voorbeeld 14.12](https://one-course.com/books/math/4/nl/chapter/14-fourierreeksen#ex-b2-fourier-basel)). 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 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/14-fourierreeksen#ex-b2-fourier-basel). Met $\E(T_n) = nH_n$ en $H_n = \sum_1^n\frac1k$ ([Oefening 22.3](#exo-b2-randomvar-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](#ex-b2-randomvar-chebsharp) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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}$. 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? 2. Chebyshev: toon met de symmetrie van de eerlijke binomiale [verdeling](#def-b2-randomvar-law) 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. 3. (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](#exo-b2-randomvar-7) teruggeeft. 4. (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](#def-b2-randomvar-law) 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} .$$ 5. 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.** 6. (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!$). 7. Leid af, voor [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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)} .$$ 8. 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$ . 9. (Hulpstelling van Hoeffding) Zij $X \in \intcc01$ met $\E X = p$, en $\psi(t) = \ln\E(\eu^{tX})$. Verantwoord dat $\psi$ tweemaal [differentieerbaar](https://one-course.com/books/math/4/nl/chapter/15-differentiaalrekening#def-b2-diffcalc-differential) 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](#def-b2-randomvar-variance)* van een herwogen veranderlijke die nog altijd waarden in $\intcc01$ aanneemt; begrens haar door $\frac14$ (het minimaliteitsargument van [Oefening 22.6](#exo-b2-randomvar-6)) en besluit met Taylor: $$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$$ 10. (Ongelijkheid van Hoeffding) Leid voor [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) $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).$$ 11. 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence), uniform gekozen kiezers; elk antwoordt eerlijk; $p$ is de werkelijke score en $\widehat p_n$ het cijfer van de peiling. 12. 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} .$$ 13. 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. 14. 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](#exo-b2-randomvar-5) : de [variantie](#def-b2-randomvar-variance) krimpt met $\frac{N-n}{N-1}$ ). 15. (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. 16. Wat de wiskunde *niet* dekt: som de aannames van het model op ( [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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.** 17. (Mediaan van gemiddelden: exponentieel verval uit twee momenten) Verdeel een budget van $km$ waarnemingen over $k$ [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#def-b2-randomvar-variance). 18. (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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) ook *afdwingen* . 19. (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. 20. 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. 21. Stel de tabel van de gereedschapskist op: geef voor Markov, Chebyshev, de grens met het vierde moment van [Oefening 22.9](#exo-b2-randomvar-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.** 22. (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. 23. (Zeldzame [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) 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](#def-b2-randomvar-variance) $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](https://one-course.com/books/math/4/nl/chapter/23-kansgenererende-functies#ch-b2-genfun) ) vandaan zal komen. 24. (Sterke wet voor munten) Bewijs uit $\sum_n 2\eu^{-2n\delta^2} < \infty$ en Borel–Cantelli ( [Stelling 21.25](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-borelcantelli) ) dat $\widehat p_n \to p$ bijna zeker voor [onafhankelijke](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) muntworpen: formuleer de bijna-zekere [gebeurtenis](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) als $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ zoals in [Oefening 22.9](#exo-b2-randomvar-9) , en besluit. (De begrensdheid vervangt het vierde moment dat daar werd gebruikt.) 25. 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 van Probleem 22.1.** **1.** $\E(S_n) = \frac n2$ en Markov ([Stelling 22.15](#thm-b2-randomvar-markov)) 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](#def-b2-randomvar-law) is [symmetrisch](https://one-course.com/books/math/4/nl/chapter/12-kwadratische-vormen#def-b2-quadratic-adjoint) om $n/2$ ($S_n$ en $n - S_n$ hebben dezelfde [verdeling](#def-b2-randomvar-law)), dus zijn met $x = n(a - \frac12) > 0$ de twee [gebeurtenissen](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $\{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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#exo-b2-randomvar-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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) 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](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-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](https://one-course.com/books/math/4/nl/chapter/10-rijen-en-reeksen-van-functies#thm-b2-funcseq-differentiation)) is zij tweemaal [differentieerbaar](https://one-course.com/books/math/4/nl/chapter/15-differentiaalrekening#def-b2-diffcalc-differential), en de quotiëntregel geeft $\psi' = \E_t(X)$ en $\psi'' = \E_t(X^2) - \E_t(X)^2$, waarbij $\E_t$ de [verwachtingswaarde](#def-b2-randomvar-expectation) 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](#def-b2-randomvar-variance) van een veranderlijke met waarden in $\intcc01$ is hoogstens $\frac14$: volgens [Oefening 22.6](#exo-b2-randomvar-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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#def-b2-randomvar-variance) 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](#def-b2-randomvar-variance) met $\frac{N - n}{N-1} < 1$ vermenigvuldigd ([Oefening 22.5](#exo-b2-randomvar-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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](https://one-course.com/books/math/4/nl/chapter/4-topologie-van-metrische-ruimten#def-b2-metric-topology) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-independence) 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](#def-b2-randomvar-variance) — nuttig precies wanneer de termen onbegrensd zijn en Hoeffding niet beschikbaar is. **18.** Cauchy–Schwarz ([Stelling 22.19](#thm-b2-randomvar-jensen)): $$ \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](https://one-course.com/books/math/4/nl/chapter/12-kwadratische-vormen#def-b2-quadratic-adjoint) 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](#ex-b2-randomvar-chebsharp)), en het beste gereedschap bij vraag 23. Vierde moment ([Oefening 22.9](#exo-b2-randomvar-9)): verval $C/n^2$, net genoeg [sommeerbaarheid](https://one-course.com/books/math/4/nl/chapter/7-rijen-en-reeksen#def-b2-series-summable) 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](#def-b2-randomvar-variance) $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](#def-b2-randomvar-variance) 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space), de poisson-benadering bewezen in [Hoofdstuk 23](https://one-course.com/books/math/4/nl/chapter/23-kansgenererende-functies#ch-b2-genfun), 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](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#thm-b2-proba-borelcantelli)) dat $\P(\abs{\widehat p_n - p} \geq \delta \text{ oneindig vaak}) = 0$, dat wil zeggen dat de [gebeurtenis](https://one-course.com/books/math/4/nl/chapter/21-kansrekening-op-aftelbare-ruimten#def-b2-proba-space) $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ voor elke $j$ kans $1$ heeft. De [aftelbare](https://one-course.com/books/math/4/nl/chapter/1-verzamelingen-en-structuren#def-b2-structures-countable) 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](#exo-b2-randomvar-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](#def-b2-randomvar-variance) 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.