Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

22Discrete stochastische variabelen

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

22.1 Stochastische variabelen en hun wetten

Definitie 22.1 (Discrete stochastische variabele; wet)

Zij $(\Omega, \P)$ een aftelbare waarschijnlijkheidsruimte. Een stochastische variabele is een afbeelding $X \colon \Omega \to E$ ( $E$ willekeurige verzameling; reële stochastische variabele wanneer $E = \R$ ). Haar wet (of verdeling) is de waarschijnlijkheidsmaat $\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 wetten)

Bernoulli $\mathcal{B}(p)$ : $X \in \{0, 1\}$ , $\P(X = 1) = p$ . 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$ : aantal successen in $n$ onafhankelijke Bernoulli-proeven (middelbareschoolvolume; hieronder opnieuw bewezen via sommen van onafhankelijke variabelen).
Geometrisch $\mathcal{G}(p)$ : $\P(X = k) = (1-p)^{k-1}p$ , $k \in \N^*$ : 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 waarschijnlijkheidsmaat door de exponentiële reeks. De wet van zeldzame gebeurtenissen (Hoofdstuk 23).

Opmerking 22.3 (Welke wet modelleert wat)

De vier wetten beantwoorden vier primitieve vragen: Bernoulli, “is het gebeurd?”; binomiaal, “hoe vaak in $n$ pogingen?”; geometrisch, “hoe lang tot de eerste keer?”; Poisson, “hoeveel gebeurtenissen bij een gegeven tempo, wanneer pogingen talrijk en individueel onwaarschijnlijk zijn?”. De vraag herkennen is negen tiende van het modelleren: sommen van indicatoren wijzen naar de binomiaal, wachttijden naar de geometrische, zeldzame-gebeurtenistellingen naar Poisson — met de overgang van binomiaal naar Poisson precies gemaakt door de wet van zeldzame gebeurtenissen in Hoofdstuk 23.

Propositie 22.4 (Geheugenloosheid van de geometrische wet)

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

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

en de geometrische wetten zijn de enige wetten op $\N^*$ met deze eigenschap.

Bewijs. Sommeren van de geometrische gewichten geeft $\P(X > n) = (1-p)^n$ . Dus

\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, als $G(n) = \P(X > n)$ voldoet aan $G(m + n) = G(m)G(n)$ met $G(0) = 1$ , dan $G(n) = G(1)^n$ door inductie; $q = G(1) \in \intco{0}{1}$ , en $q = 0$ of de wet is $\mathcal{G}(1 - q)$ : $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Voorbeeld 22.5 (Geen getal is ooit “verschuldigd”)

Gooi een dobbelsteen, wachtend op een zes: de wachttijd is $X \sim \mathcal G(1/6)$ . Geheugenloosheid zegt dat na $10$ vruchteloze worpen de resterende wacht $X - 10$ , gegeven $X > 10$ , opnieuw $\mathcal G(1/6)$ is: de voorwaardelijke verwachte wacht is nog steeds $6$ worpen, precies als bij de start. De dobbelsteen herinnert zich niets, en geen zes is ooit verschuldigd: de gokkersdrogreden is precies het geloof dat de voorwaardelijke wet had moeten verschuiven. Omgekeerd zegt de uniciteitshelft van de propositie dat deze onverschilligheid geometrische wachttijden karakteriseert: elke wachttijd waarvan de voorspelling nooit bijwerkt is geometrisch. Echte wachtrijen en levensduren werken hun voorspelling meestal wél bij, wat precies is hoe men detecteert dat ze niet geometrisch zijn.

22.2 Verwachting

Definitie 22.6 (Verwachting)

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

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

Stelling 22.7 (Overdrachtsstelling)

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

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

Algemener, voor $f \colon X(\Omega) \to \R$ heeft de variabele $f(X)$ een verwachting iff $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , en dan $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Bewijs. Partitioneer $\Omega$ in de niveausets $\Omega_x = \{X = x\}$ , $x \in X(\Omega)$ . Door de sommatie-per-pakketten-stelling voor sommeerbare families (Hoofdstuk 7) is de familie $(X(\omega)\P(\{\omega\}))_\omega$ sommeerbaar iff elk pakket dat is (automatisch: $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) en de familie van paksommen $\bigl(x\,\P(X = x)\bigr)_x$ sommeerbaar is — en dan stemmen de totalsommen overeen. Voor $f(X)$ : pas de bewezen uitspraak toe op de variabele $Y = f \circ X$ , wier niveausets $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ zijn; een tweede sommatie per 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)$ , met absolute sommeerbaarheid van de ene familie equivalent aan die van de andere. ∎

Stelling 22.8 (Eigenschappen van de verwachting)

Op de verzameling stochastische variabelen met verwachting:

(Lineariteit) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Positiviteit en monotoniciteit) $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) Als $\abs X \leq Z$ en $Z$ een verwachting heeft, dan ook $X$ .

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

Voorbeeld 22.9

$X \sim \mathcal{B}(n, p)$ : schrijvend $X = X_1 + \dots + X_n$ als som van Bernoulli-indicatoren en lineariteit gebruikend, $\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 differentiatie van de geometrische reeks binnen haar schijf (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)

Voor $X \sim \mathcal P(\lambda)$ , bereken $\E\bigl(\frac1{1+X}\bigr)$ — de wet van $\frac1{1+X}$ zelf is onhandig, maar overdracht vraagt er nooit om:

\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. Computationeel: een verschoven exponentiële reeks herkennen is het hele werk — overdracht reduceert verwachtingen van $f(X)$ tot reeksmanipulatie. Structureel: de naïeve inplugwaarde zou $\frac1{1 + \E X} = \frac1{1 + \lambda}$ zijn, en het ware 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. Verwachtingen van convexe beelden zitten boven de naïeve inplugwaarde, en overdracht plus een reekscontrole maakt de abstracte ongelijkheid concreet.

Stelling 22.11 (Onafhankelijkheid en producten)

Stochastische variabelen $X, Y$ zijn onafhankelijk als $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ voor alle $x, y$ — equivalent, de gebeurtenissen $\{X \in A\}$ en $\{Y \in B\}$ zijn onafhankelijk voor alle $A, B$ . Als $X$ en $Y$ onafhankelijke reële variabelen met verwachting zijn, dan heeft $XY$ een verwachting en

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

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

\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 ;

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

Voorbeeld 22.12 (Producten, met en zonder onafhankelijkheid)

Gooi twee eerlijke dobbelstenen. Als $Y$ de tweede steen is (onafhankelijk van de eerste), $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . Als in plaats daarvan $Y = X$ (het “product” van een steen met zichzelf),

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

zelfde marginale wetten in beide scenario’s, verschillende gezamenlijke wetten, verschillende productverwachtingen. De moraal, het graveren waard: $\E(XY)$ is een functionaal van het paar, niet van de twee marginalen — en de kloof $\E(X^2) - \E(X)^2 \approx 2.92$ is, door König–Huygens, precies de variantie $\frac{35}{12}$ van de steen.

22.3 Variantie, covariantie en de klassieke ongelijkheden

Definitie 22.13 (Momenten, variantie)

$X$ heeft een moment van orde 2 als $X^2$ een verwachting heeft (dan ook $X$ , door 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 König–Huygens-formule — door het kwadraat te ontwikkelen en 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 ,

de middelste term gebruikmakend van 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 (Variantiegereedschap)

Voor variabelen 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) ;$
als $X, Y$ onafhankelijk zijn, $\operatorname{Cov}(X, Y) = 0$ (het omgekeerde is onwaar), dus varianties van onafhankelijke variabelen tellen op.

Bewijs. 1 en 2 zijn ontwikkelingen van kwadraten plus lineariteit; de producten $X_iX_j$ hebben verwachtingen door Cauchy–Schwarz hieronder (of door $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). 3 is Stelling 22.11 toegepast op de gecentreerde variabelen. Een standaardtegenvoorbeeld van 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) Als $X \geq 0$ een verwachting heeft, dan voor elke $a > 0$ :

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

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

Bewijs. 1. Puntsgewijs, $a\,\mathbf{1}_{X \geq a} \leq X$ (op de gebeurtenis is de linkerzijde $a \leq X$ ; erbuiten, $0 \leq X$ ). Neem verwachtingen: $a\,\P(X \geq a) \leq \E(X)$ door monotoniciteit en $\E(\mathbf{1}_A) = \P(A)$ . 2. Pas Markov toe op de niet-negatieve variabele $(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 vastgeplakt)

Gooi twee eerlijke dobbelstenen, $X$ en $Y$ onafhankelijk, en stel $S = X + Y$ , $D = X - Y$ . Door bilineariteit van de covariantie,

\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$ , terwijl $\P(D = 0) = \frac16$ onvoorwaardelijk. Correlatie test alleen het lineaire deel van een afhankelijkheid; hier wordt de afhankelijkheid gedragen door de constraint dat $S$ en $D$ dezelfde pariteit hebben, onzichtbaar voor covariantie. (Voor dit paar had nul-covariantie $V(X) = V(Y)$ nodig: identieke verdelingen, niet onafhankelijkheid, deden het werk.)

Voorbeeld 22.17 (Wanneer Markov exact is)

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

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

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

Voorbeeld 22.18 (Chebyshev is scherp — zonder verdere hypothesen)

Fixeer $\varepsilon > 0$ , $q \in \intoc01$ , en laat $X$ de waarden $\pm\varepsilon$ aannemen met waarschijnlijkheid $\frac q2$ elk en $0$ met waarschijnlijkheid $1 - q$ . Dan $\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. Dus de ongelijkheid kan niet verbeterd worden met alleen de variantie — het $1/\varepsilon^2$ -verval is de exacte prijs van tweede-momentinformatie. Sneller verval eist sterkere hypothesen: begrensdheid van de variabele koopt exponentiële concentratie, zoals Oefening 22.7 vooruitkijkt en het weekendprobleem van dit hoofdstuk systematisch ontwikkelt.

Stelling 22.19 (Cauchy–Schwarz en Jensen)

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

$\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 variabelen met tweede momenten, dus de abstracte Cauchy–Schwarz-ongelijkheid van Hoofdstuk 12 past toe (positief semi-definiet volstaat voor de ongelijkheid). Toepassing op de gecentreerde variabelen geeft de covariantiegrens.

2. Eerst ligt $m = \E(X)$ in $I$ : $I$ is een interval dat alle waarden van $X$ bevat, en verwachting is monotoon, dus $m$ ligt tussen $\inf X(\Omega)$ en $\sup X(\Omega)$ . Door de steunlijnstelling voor convexe functies (Hoofdstuk 8) bestaan $\alpha, \beta$ met $\varphi(t) \geq \alpha t + \beta$ voor alle $t \in I$ en $\varphi(m) = \alpha m + \beta$ . Dan, puntsgewijs op $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; verwachtingen nemend,

\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)$ — 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 stochastische vorm.

Opmerking 22.21 (Gangbare valkuilen)

(i) $\E(XY) = \E(X)\E(Y)$ eist onafhankelijkheid (of minstens nul-covariantie): $Y = X$ nemen geeft $\E(X^2) \neq \E(X)^2$ wanneer $V(X) > 0$ . (ii) Evenzo $V(X + X) = 4V(X)$ , niet $2V(X)$ : varianties tellen alleen op over onafhankelijke (of ongecorreleerde) sommanden. (iii) $\E(f(X))$ is niet $f(\E(X))$ ; voor convexe $f$ vertelt Jensen u zelfs de richting van de fout, zoals in Voorbeeld 22.10. (iv) Bestaan is een echte hypothese: voor de Sint-Petersburgvariabele $X = 2^K$ met $\P(K = k) = 2^{-k}$ ( $k \geq 1$ ),

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

$X$ is bijna zeker eindig maar heeft geen verwachting, en er bestaat geen eerlijke instapprijs voor het spel. Sommeerbaarheid in de definitie van $\E$ is geen boekhoudkundige pedanterie — het is waar zware staarten gedetecteerd worden. (v) Tenslotte eist de overdrachtsstelling absolute sommeerbaarheid voordat enige herschikking van de som over waarden legitiem 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 gegarandeerde $31\%$ ligt ver van de waarheid, maar eiste alleen het gemiddelde en de variantie — hetzelfde certificaat past letterlijk toe op elke variabele met $\E = 50$ , $V = 25$ , hoe exotisch ook, en Voorbeeld 22.18 toont dat enige zulke variabele haar verzadigt. Universaliteit heeft een prijs; wanneer de verdeling werkelijk binomiaal is, dichten de exponentiële gereedschappen van het weekendprobleem het grootste deel van de kloof.

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

Voor onafhankelijke identiek verdeelde $X, Y$ met variantie $\sigma^2 > 0$ , hoe gecorreleerd is één sommand 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,

dus de correlatiecoëfficiënt is

\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 ,

ongeacht de gemeenschappelijke wet — dobbelstenen, munten, Poisson-tellingen. Met $n$ sommanden geeft dezelfde berekening $\rho(X_1, S_n) = 1/\sqrt n$ : de invloed van elke individuele term op het totaal verdunt als een vierkantswortel, wat de correlationele schaduw is van de $\sqrt n$ -schaal van fluctuaties. Cauchy–Schwarz garandeert $\abs\rho \leq 1$ altijd; hier wordt de grens exact geraakt in het ontaarde geval $n = 1$ en daalt voorspelbaar erna.

Voorbeeld 22.24 (Gewogen AM–GM uit Jensen)

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

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 rekenkundig–meetkundige ongelijkheid, met gelijkheid iff $Y$ constant is. Gelijke gewichten $\lambda_i = \frac1k$ herstellen de klassieke AM–GM. Kansrekening heeft stilzwijgend een zuiver algebraïsche stelling bewezen: een waarschijnlijkheidswet kiezen is slechts een boekhoudkundig hulpmiddel voor convexe combinaties — het barycentrische standpunt van Hoofdstuk 17 opnieuw, 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}$ paarsgewijs onafhankelijke stochastische variabelen met dezelfde wet, met een tweede moment; schrijf $m = \E(X_1)$ en $S_n = X_1 + \dots + X_n$ . Dan 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. Door lineariteit $\E(S_n/n) = m$ ; door Stelling 22.14 (paarsgewijze onafhankelijkheid doodt de covarianties) $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 waarschijnlijkheid met 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 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 Bachelor jaar 3-stelling — haar bewijs voor vierde momenten is echter binnen bereik: zie Oefening 22.9, die Borel–Cantelli op de Chebyshev-achtige grens draait. Dezelfde Chebyshev-schatting dreef het Bernstein-polynoom-bewijs van de Weierstrass-benaderingsstelling in Hoofdstuk 10 — het tellemma daar was de zwakke wet van de grote aantallen in vermomming.

Voorbeeld 22.27 (Vijftig coupons verzamelen)

De couponverzamelaar van Oefening 22.3 met $n = 50$ verschillende speeltjes: de verwachte total is

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

dozen — vier en een half keer de naïeve gok $50$ . De harmonische groei is het hele verhaal: de eerste $25$ speeltjes arriveren in ongeveer $50\ln2 \approx 35$ dozen, terwijl het laatste speeltje alleen al gemiddeld $50$ dozen kost (een geometrische wacht van parameter $\frac1{50}$ ). Voltooiingsproblemen worden gedomineerd door hun eindspel, waarom Oefening 22.12 fluctuaties van orde $n$ vindt — de grootte van die finale geometrische wacht — rond het gemiddelde $n\ln n$ .

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

Om de waargenomen frequentie binnen $\varepsilon = 0.01$ van $\P(A)$ te pinnen met vertrouwen $95\%$ , eist de grens van Chebyshev

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

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

De wet van de grote aantallen als plaatje: de wet van S_n/n (schematisch getekend) houdt haar centrum m maar vernauwt als n groeit, zodat de waarschijnlijkheid buiten de band [m- , m+ ] — de twee staarten — naar nul krimpt. Chebyshev begrenst de staarten door V(X_1)/(n 2); het weekendprobleem toont dat zij in feite exponentieel klein zijn. — De wet van de grote aantallen als plaatje: de wet van $S_n/n$ (schematisch getekend) houdt haar centrum $m$ maar vernauwt als $n$ groeit, zodat de waarschijnlijkheid 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)$ ; het weekendprobleem toont dat zij in feite exponentieel klein zijn.

Opmerking 22.29 (Perspectieven binnen dit volume)

Voorwaarts voedt alles hier Hoofdstuk 23: de verwachting $\E(t^X)$ van één listige functie van $X$ pakt de hele wet in een machtreeks, momenten worden afgeleiden in $1$ , en Wald-achtige identiteiten voor stochastische sommen dragen de vertakkingsprocentheorie; de productstelling voor onafhankelijke variabelen wordt multiplicativiteit van genererende functies. Achterwaarts is verwachting een barycentrum met waarschijnlijkheidsgewichten (Hoofdstuk 17), de ongelijkheid van Jensen is de steunlijnmeetkunde van convexe functies (Hoofdstuk 8), en de exponentiële-momentmethode van het weekendprobleem van dit hoofdstuk is Markov toegepast op $\eu^{tX}$ — één ongelijkheid, opgewaardeerd door één goede variabelesubstitutie, over drie hoofdstukken.

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 $V(X) = \lambda$ ), en $X \sim \mathcal{G}(p)$ (toon $V(X) = \frac{1-p}{p^2}$ ; gebruik $\E(X(X-1))$ en de tweede afgeleide van de geometrische reeks).

Oplossing

Oplossing van Oefening 22.1.

Binomiaal: $X = \sum_{i=1}^n X_i$ met onafhankelijke Bernoulli $X_i$ ; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , en varianties van onafhankelijke variabelen 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 .

Geometrisch ( $q = 1 - p$ ): differentiëren van $\sum_{k\geq0}q^k = \frac{1}{1-q}$ tweemaal binnen de schijf (Hoofdstuk 11), $\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 ★

Zij $X \sim \mathcal{P}(\lambda)$ en $Y \sim \mathcal{P}(\mu)$ onafhankelijk. Toon dat $X + Y \sim \mathcal{P}(\lambda + \mu)$ (convolutie van de gewichten; binomium van Newton), en dat de voorwaardelijke wet 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$ , door disjunctheid en 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!}

door het binomium van Newton: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Voorwaardelijke wet: voor $0 \leq k \leq n$ ,

\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 wet $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : gegeven de totale telling “kiest” elke gebeurtenis onafhankelijk de eerste bron met waarschijnlijkheid evenredig aan haar tempo.

Oefening 22.3 ★

(Couponverzamelaar, verwachting) Een ontbijtgranenmerk verbergt één van $n$ verschillende speeltjes, uniform, in elke doos. Laat $T_n$ het aantal dozen zijn dat nodig is om alle $n$ speeltjes te verzamelen. Schrijvend $T_n$ als som van onafhankelijke geometrische variabelen (tijd tot een nieuw speeltje wanneer er nog $k$ ontbreken), toon

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

(equivalent via de reeks–integraalvergelijking van Hoofdstuk 6).

Oplossing

Oplossing van Oefening 22.3.

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

\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 finale handvol.

Oefening 22.4 ★★

Zij $X \geq 0$ geheelwaardig. Bewijs de staartformule

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

(wanneer één van beide zijden eindig is), door $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ te schrijven en sommaties te verwisselen (Fubini voor niet-negatieve families). Herstel $\E(X) = \frac1p$ voor de geometrische wet.

Oplossing

Oplossing van Oefening 22.4.

Puntsgewijs, $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 Fubini voor families (Hoofdstuk 7) past onvoorwaardelijk toe: eerst in $n$ sommeren geeft $\E(X)$ , eerst in $\omega$ sommeren geeft $\sum_n \P(X \geq n)$ ; de twee zijn gelijktijdig 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 ★★

(Steekproef zonder teruglegging is meer geconcentreerd) Een urn heeft $N$ ballen, waarvan $M$ wit. Trek $n \leq N$ zonder teruglegging en laat $X$ de witten tellen (hypergeometrische wet). Gebruik makend van indicatoren $X = \sum_{i=1}^n Y_i$ met $Y_i$ de $i$ -de trekking: toon dat elke $Y_i$ Bernoulli is van parameter $p = M/N$ (symmetrie!), concludeer $\E(X) = np$ precies als met teruglegging, en toon $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ voor $i \neq j$ , dus $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 van de urn (elk van de $N$ ballen is even waarschijnlijk in positie $i$ van de trekvolgorde te landen), dus $\P(Y_i = 1) = \frac MN = p$ en $\E(X) = np$ door lineariteit — geen onafhankelijkheid nodig.

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

\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 witten schaarser voor de andere trekkingen. Door Stelling 22.14,

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) :

steekproef zonder teruglegging heeft hetzelfde gemiddelde maar kleinere variantie dan met teruglegging (gelijkheid alleen voor $n = 1$ ), de negatieve correlaties werkend als stabilizer. Voor $n = N$ verdwijnt de variantie: de telling is dan deterministisch.

Oefening 22.6 ★★

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

Oplossing

Oplossing van Oefening 22.6.

Ontwikkelen 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)$ — verwachting is de beste constante voorspeller in kwadratisch gemiddelde.

Als $\P(X = m) = 1$ dan verdwijnt $(X - m)^2$ met waarschijnlijkheid $1$ , dus $V(X) = 0$ (de definiërende familie heeft nultermen behalve op een nulverzameling). Omgekeerd, als $V(X) = 0$ , geeft Chebyshev (Stelling 22.15) $\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 monotone continuïteit (Stelling 21.6) levert $\P(X \neq m) = 0$ .

Oefening 22.7 ★★★

(Concentratie verslaat Markov) Zij $S_n \sim \mathcal{B}(n, \frac12)$ (aantal 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 (Chernoff-)methode:

\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 verkrijgen. (Bij $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 de waarschijnlijkheid is hoogstens $\frac{n/4}{(n/4)^2} = \frac4n$ — die daalt, maar alleen polynomiaal. Chernoff: door onafhankelijkheid, $\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$ bij $e^t = 3$ , d.w.z. $t = \ln 3$ , wat geeft

\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 ,

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 variabele.

Oefening 22.8 ★★★

(Weierstrass opnieuw, probabilistisch) Zij $f \colon [0,1] \to \R$ continu en $S_n \sim \mathcal{B}(n, x)$ . Toon dat het Bernstein-polynoom $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 herleid de schatting $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ van Hoofdstuk 10 in deze probabilistische taal (splits op $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ en gebruik Chebyshev).

Oplossing

Oplossing van Oefening 22.8.

Door 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) .

Fixeer $\delta > 0$ 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 ten hoogste de continuïteitsmodulus $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; op $D$ , ten hoogste $2\norm f_\infty$ . Verwachtingen nemend en Chebyshev gebruikend 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} .

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

Oefening 22.9 ★★★

(Sterke wet onder vierde momenten) Zij $(X_k)$ onafhankelijk, identiek verdeeld, gecentreerd ( $\E X_1 = 0$ ), met $\E(X_1^4) < \infty$ . Ontwikkel $\E(S_n^4)$ en tel de overlevende termen (alleen $\E(X_i^4)$ - en $\E(X_i^2X_j^2)$ -termen, $i \neq j$ ), toon $\E(S_n^4) \leq C n^2$ voor een constante $C$ . Leid af $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ voor elke $\varepsilon > 0$ (Markov van orde 4) en concludeer met Borel–Cantelli (Stelling 21.25) dat $S_n/n \to 0$ bijna zeker langs een geschikte formulering: de gebeurtenis $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ heeft waarschijnlijkheid $1$ .

Oplossing

Oplossing van Oefening 22.9.

Ontwikkel $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ en neem verwachtingen. Door onafhankelijkheid en centrering verdwijnt elke term die een index bevat die precies één keer verschijnt ( $\E(X_i) = 0$ factort uit). Overlevende termen: de $n$ diagonaaltermen $\E(X_i^4)$ , en de termen die twee paren gelijke indices paren, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ voor $i \neq j$ , verschijnend $3n(n-1)$ keer: kies het ongeordende paar waarden ( $\binom n2$ manieren), dan de $\frac{4!}{2!\,2!} = 6$ manieren om ze in de vier slots te plaatsen — $6\binom n2 = 3n(n-1)$ . Dus, 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 van 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. Door Borel–Cantelli 1 (Stelling 21.25) heeft voor elke $j$ de gebeurtenis $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ waarschijnlijkheid $0$ , dus $\P\bigl(\bigcup_j B_j\bigr) = 0$ door aftelbare subadditiviteit. Op het complement — van waarschijnlijkheid $1$ — bestaat 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 verwijderen (stelling van Kolmogorov) is Bachelor jaar 3-werk.

Oefening 22.10 ★

Twee eerlijke dobbelstenen worden gegooid; laat $M$ de grotere van de twee resultaten zijn. Gebruik de staartformule van Oefening 22.4 (eindige versie) om te tonen

\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 stenen ten hoogste $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 ,

comfortabel boven het gemiddelde $3.5$ van een enkele steen, zoals een maximum behoort te zijn.

Oefening 22.11 ★★

Laat $F_n$ het aantal vaste punten zijn van een uniform willekeurige permutatie van $\{1, \dots, n\}$ ( $n \geq 2$ ). Schrijvend $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , bereken $\E(F_n) = 1$ , $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ voor $i \neq j$ , en concludeer $V(F_n) = 1$ : gemiddeld is één letter vast, met variantie precies $1$ , ongeacht $n$ .

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)}$ , dus

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

Door het variantiegereedschap (Stelling 22.14),

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$ — consistent met de Poisson-limiet van het matchingprobleem (Oefening 21.5).

Oefening 22.12 ★★★

(Couponverzamelaar, concentratie) In de setting van Oefening 22.3, toon

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 onafhankelijkheid van de geometrische stadia 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 waarschijnlijkheid: de totale tijd van de verzamelaar is $n\ln n$ op fluctuaties van orde $n$ na.

Oplossing

Oplossing van Oefening 22.12.

$T_n = \sum_{k=1}^nG_k$ waar $G_k \sim \mathcal G(k/n)$ de tijd is tot een nieuw speeltje wanneer er nog $k$ ontbreken, de stadia onafhankelijk. Dus

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 ,

door Voorbeeld 14.12. Met $\E(T_n) = nH_n$ , $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 waarschijnlijkheid: de fluctuaties van $T_n$ zijn van orde $n$ , verwaarloosbaar tegen het gemiddelde $n\ln n$ .

22.6 Probleem: de concentratiegereedschapskist, van Markov tot Hoeffding

Probleem 22.1

Weekendprobleem — exponentiële concentratie met de hand, en hoeveel mensen een peiling moet vragen

De ongelijkheid van Markov kost één moment en koopt een $1/a$ -verval; Chebyshev kost twee momenten en koopt $1/\varepsilon^2$ — en Voorbeeld 22.18 toont dat dat alles is wat die momenten kunnen kopen. Dit probleem klimt de rest van de ladder: de exponentiële (Chernoff-)methode met haar exacte tempo voor muntworpen, de ongelijkheid van Hoeffding voor alle begrensde variabelen, en de beloning — expliciete, eerlijke steekproefgroottes voor peilingen, verkiezingsuitspraken en muntentesten. Doorheen is $S_n \sim \mathcal B(n, p)$ een som van $n$ onafhankelijke Bernoulli-variabelen en $\widehat p_n = S_n/n$ de empirische frequentie.

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

Markov op niveau $an$ : toon $\P(S_n \geq an) \leq \frac1{2a}$ , een grens die niet eens naar $0$ neigt. Waar verliest Markov zoveel?
Chebyshev: gebruik makend van de symmetrie van de eerlijke binomiaal om $n/2$ , toon

$\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},$

d.w.z. $\frac2n$ bij $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 dat de optimale $t$ $\ln\frac{a}{1-a}$ is en

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

Controleer dat $a = \frac34$ de grens $\bigl(2\cdot3^{-3/4}\bigr)^n$ van Oefening 22.7 herstelt.
(De exponent is exact) Laat $k = an$ een geheel getal zijn. Uit het feit dat $\binom nk a^k(1-a)^{n-k}$ de grootste is van de $n + 1$ termen van een waarschijnlijkheidsverdeling, bewijs $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ met $H(a) = -a\ln a - (1-a)\ln(1-a)$ , en leid de passende ondergrens af

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

Deel II — De ongelijkheid van Hoeffding.

(Rademacher-geval) Voor $\varepsilon = \pm1$ met waarschijnlijkheid $\frac12$ elk, bewijs

$\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-variabelen $\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$ .
(Lemma van Hoeffding) Zij $X \in \intcc01$ met $\E X = p$ , en $\psi(t) = \ln\E(\eu^{tX})$ . Rechtvaardig 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 variabele die nog waarden in $\intcc01$ aanneemt; begrens haar door $\frac14$ (minimaliteitsargument van Oefening 22.6) en besluit door Taylor:

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

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

Deel III — Hoeveel mensen moet een peiling vragen? Een peiling vraagt $n$ onafhankelijke, uniform gekozen kiezers; elk antwoord is eerlijk; $p$ is de ware score, $\widehat p_n$ het peilingscijfer.

Toon dat de peiling accuraat is tot $\pm\delta$ met vertrouwen $1 - \alpha$ (d.w.z. $\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 standaard “drie punten, vijfennegentig procent”-specificatie ( $\delta = 0.03$ , $\alpha = 0.05$ ): $n \geq 2050$ ; en voor één punt: $n \geq 18\,445$ . Observeer — en leg uit — het opvallende feit dat het antwoord de populatiegrootte niet bevat.
Doe vraag 13 over met Chebyshev ( $V(X_1) = p(1-p) \leq \frac14$ ): $n \geq \frac1{4\alpha\delta^2} = 5556$ bij drie punten. Merk op dat steekproef zonder teruglegging alleen helpt (Oefening 22.5: de variantie krimpt met $\frac{N-n}{N-1}$ ).
(Een verkiezing uitroepen) De ware score van een kandidaat is $p = 0.52$ . Hoeveel kiezers moeten gepolld worden zodat $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Toon $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — een nipte race uitroepen kost veel meer dan een score schatten.
Wat de wiskunde niet dekt: noem de modelleringsaannames gebruikt (onafhankelijke uniforme steekproef, eerlijke antwoorden, vaste $p$ ), en leg in een korte alinea uit waarom echte peilingsfouten gedomineerd worden door vertekening (niet-uniforme steekproef, non-respons), die geen verhoging van $n$ reduceert.

Deel IV — Scherper en goedkoper.

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

$\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 buiten varianties.
(Paley–Zygmund) Voor $X \geq 0$ met een tweede moment, bewijs $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (Cauchy–Schwarz op $X\mathbf 1_{X>0}$ ): het omgekeerde-richtingsgereedschap — momenten kunnen ook gebeurtenissen forceren te gebeuren.
(Pinsker-lite) Toon $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ op $\intoo{\frac12}1$ (het verschil verdwijnt tot 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 Hoeffding-exponent $2n\delta^2$ asymptotisch exact — geen methode kan haar met meer dan polynomiale factoren verslaan.
Stel de gereedschapstabel op: voor Markov, Chebyshev, de vierde-momentgrens van Oefening 22.9, Hoeffding, en Chernoff met exponent $I$ , noem in één regel elk: vereiste hypothese, verkregen verval, en de vraag in dit probleem waar zij het scherpst was.

Deel V — Dividenden.

(Een munt testen) Een munt is ofwel eerlijk ofwel vertekend met $p = 0.55$ . U gooit haar $n$ keer en verklaart “vertekend” wanneer $\widehat p_n > 0.525$ . Toon dat beide foutkansen ten hoogste $\eu^{-2n(0.025)^2}$ zijn, en dat $n \geq 3685$ worpen beide onder $1\%$ garanderen.
(Zeldzame gebeurtenissen hebben een variantie-bewuste grens nodig) Laat $p = 0.01$ en neem de relatieve specificatie $\delta = p/2 = 0.005$ , $\alpha = 0.05$ . Vergelijk de steekproefgroottes geëist door Hoeffding ( $n \approx 74\,000$ ) en door Chebyshev met de ware variantie $p(1-p)$ ( $n \approx 7920$ ): de variantie-blinde exponentiële grens verliest van het nederige tweede moment. Stel de moraal, en waar het ontbrekende gereedschap (een variantie-bewuste exponentiële grens; de Poisson-benadering van Hoofdstuk 23) vandaan zal komen.
(Sterke wet voor munten) Uit $\sum_n 2\eu^{-2n\delta^2} < \infty$ en Borel–Cantelli (Stelling 21.25), bewijs 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 concludeer. (Begrensdheid vervangt het vierde moment daar gebruikt.)
Synthese. In vijf zinnen: wat elke sport van de ladder (momenten één, twee, vier; begrensde exponentieel; exacte exponent) kost en koopt; waarom peilen van $2050$ mensen volstaat voor een land van elke grootte; en welke van deze grenzen het Bachelor jaar 3-volume zal aanscherpen tot de exacte constanten van de centrale limietstelling.

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 variabele geconcentreerd in $n/2$ niet onderscheiden van één gespreid tussen $0$ en $n$ , dus prijst zij de staart alsof alle massa daar kon zitten.

2. De eerlijke binomiaal is symmetrisch om $n/2$ ( $S_n$ en $n - S_n$ hebben dezelfde wet), dus met $x = n(a - \frac12) > 0$ zijn de twee gebeurtenissen $\{S_n - \frac n2 \geq x\}$ en $\{S_n - \frac n2 \leq -x\}$ disjunct en equiprobable: $\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 bij $a = \frac34$ .

3. Door onafhankelijkheid en de productstelling, $\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 in $t$ is $\frac{\eu^t}{1 + \eu^t} - a$ , nul in $\eu^t = \frac a{1-a}$ , d.w.z. $t^* = \ln\frac a{1-a} > 0$ ; daar $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ en de exponent is 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$ . Bij $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 de grootste is die bij $j = k = an$ (de modus van $\mathcal B(n, a)$ is $\floor{(n+1)a} = k$ hier). 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}.

Dus $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : tot op de polynomiale factor $n + 1$ 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 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!$ , wat door 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. Door onafhankelijkheid, $\E\bigl(\eu^{t\sum\varepsilon_i}\bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , dus Markov geeft $\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$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , dus $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ en vraag 7 geeft de grens $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . De symmetrische gebeurtenis heeft dezelfde grens, vandaar 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 term-voor-term-afgeleiden, op elk compact $t$ -interval, gedomineerd worden door $\eu^{\abs t}\P(X = x)$ (omdat $0 \leq x \leq 1$ ): door 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$ , waar $\E_t$ de verwachting is voor de herwogen gewichten $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — niet-negatief, sommerend tot $1$ , gedragen door dezelfde waarden $x \in \intcc01$ . Een variantie van een $\intcc01$ -waardige variabele is ten hoogste $\frac14$ : door Oefening 22.6 is zij $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor met integraalrestterm, met $\psi(0) = 0$ , $\psi'(0) = p$ :

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

d.w.z. $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ voor alle reële $t$ .

10. Door onafhankelijkheid, $\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 variabelen $1 - X_i$ (ook in $\intcc01$ ) begrenst de andere staart, vandaar de tweezijdige $2\eu^{-2n\delta^2}$ .

11. Chebyshev eist alleen een tweede moment en geeft $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding eist begrensdheid en geeft $2\eu^{-2n\delta^2}$ . Bij $p = \frac12$ , $\delta = 0.03$ : de grenzen zijn $\frac{278}{n}$ (ongeveer) versus $2\eu^{-0.0018n}$ ; zij kruisen nabij $n \approx 1200$ , waarna de exponentiële grens wint, en wild zo ( $n = 5000$ : $0.056$ versus $2.5\cdot10^{-4}$ ).

12. Door Hoeffding (vraag 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ zodra $2n\delta^2 \geq \ln\frac2\alpha$ , d.w.z. $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 populatiegrootte verschijnt nooit omdat elke bemonsterde kiezer gemodelleerd is als een verse Bernoulli $(p)$ -trekking: de moeilijkheid van de peiling is de variantie van een munt, niet de grootte van het land. De marge halveren kost vier keer de steekproef — de $1/\delta^2$ -wet.

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}$ , d.w.z. $5556$ bij drie punten — ongeveer $2.7$ keer de Hoeffding-eis. Zonder teruglegging wordt de variantie vermenigvuldigd met $\frac{N - n}{N-1} < 1$ (Oefening 22.5), dus dezelfde $n$ kan alleen beter doen: de met-teruglegging-berekening is de conservatieve.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , dus door de eenzijdige Hoeffding-grens $\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 kost schaalt als het omgekeerde kwadraat van de voorsprong, niet van de gewenste precisie: nipte races zijn duur.

16. Gebruikt: de steekproef is uniform en onafhankelijk uit het electoraat getrokken; elke bemonsterde persoon antwoordt, eerlijk, en $p$ beweegt niet tijdens peilen. Echte peilingen schenden alle drie: bereikbare en willige respondenten zijn geen uniforme steekproef (selectie- en non-responsvertekening), en antwoorden kunnen onwaarachtig of onstabiel zijn. Dit zijn vertekeningsfouten: zij verschuiven $\E(\widehat p_n)$ weg van $p$ met een bedrag onafhankelijk van $n$ , dus geen steekproefgrootte reduceert ze — de wiskunde van dit Deel controleert alleen de fluktuatieterm.

17. Chebyshev voor één groep van grootte $m$ : $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ voor $m \geq \frac2{\delta^2}$ . Als minder dan $k/2$ groepen fout gaan, liggen meer dan $k/2$ van de waarden $\widehat p^{(i)}$ in het open interval $\intoo{p - \delta}{p + \delta}$ , en dus ook hun mediaan; dus dwingt $\{\abs{M - p} \geq \delta\}$ minstens $\lceil k/2\rceil$ fouten onder $k$ onafhankelijke groepen. De unie-ongelijkheid over de $\binom k{\lceil k/2\rceil}$ mogelijke verzamelingen foutgaande 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 sommanden 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. Laat $h(a) = I(a) - 2(a - \tfrac12)^2$ . Dan $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ verdwijnt in $\tfrac12$ , en

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

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

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

21. Markov: één moment, verval $1/a$ , nuttig alleen als motor achter de anderen (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 variabelen, verval $2\eu^{-2n\delta^2}$ , het werkpaard van Deel III. Chernoff met het exacte tempo $I(a)$ : volle exponentiële momenten, onverslaanbare exponent (vragen 4, 20), het referentiepunt voor al het andere.

22. Als de munt eerlijk is: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Als $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$ , d.w.z. $n \geq 3684.2$ : $3685$ worpen. (Hypothesen $2.5$ punten uit elkaar onderscheiden kost wat schatten tot $\pm2.5$ punten kost.)

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

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

25. Eén moment koopt een platte grens; twee kopen $1/(n\delta^2)$ , en niet meer (het scherptevoorbeeld); vier kopen $1/n^2$ , genoeg om tot een bijna-zekere wet te telescoperen; begrensdheid koopt $\eu^{-2n\delta^2}$ ; en het volle exponentiële moment koopt het exacte tempo $I$ , dat geen methode verslaat. Peilen van $2050$ mensen volstaat voor elk land omdat de fluctuatie van de steekproef geregeerd wordt door de variantie van de munt, niet de grootte van de populatie — de $1/\delta^2$ - en $\ln(1/\alpha)$ -prijskaartjes zijn universeel. De centrale limietstelling van het Bachelor jaar 3-volume vervangt deze ongelijkheden, op de $\sqrt n$ -schaal, door een exacte limietwet met expliciete constanten — elke grens van dit probleem omzettend in een asymptotische gelijkheid.