Universitaire wiskunde — Bachelor jaar 3 · Bachelor Year 3

22Kansrekening: fundamenten en de wet van de grote aantallen

Het volume van bachelorjaar 2 bouwde de kansrekening op aftelbare ruimten; de maattheorie neemt nu elke beperking weg. Een kansruimte is een maatruimte met totale massa $1$ , toevalsveranderlijken zijn meetbare afbeeldingen, de verwachtingswaarde is de lebesgue-integraal — en meteen is het hele analytische arsenaal (Hoofdstukken 9, 10 en 11) op het toeval van toepassing. Dit hoofdstuk installeert het woordenboek, construeert oneindige rijen onafhankelijke toevalsveranderlijken (op $\intcc01$ , uit binaire cijfers: het toeval zit verstopt in de lebesguemaat), bewijst de lemma’s van Borel–Cantelli en de nul-een-wet van Kolmogorov, sorteert de convergentiewijzen uit, en bewijst de wet van de grote aantallen — de stelling die frequenties naar kansen laat convergeren en de statistiek mogelijk maakt. De weekendopgave geeft het bewijs van Etemadi van de sterke wet in haar definitieve $L^1$ -vorm.

22.1 Het woordenboek

Definitie 22.1

Een kansruimte is een maatruimte $(\Omega, \mathcal A, \P)$ met $\P(\Omega) = 1$ ; de elementen van $\mathcal A$ heten gebeurtenissen, en een eigenschap geldt bijna zeker (b.z.) als haar gebeurtenis kans $1$ heeft. Een toevalsveranderlijke is een meetbare afbeelding $X \colon \Omega \to \R$ (of $\R^d$ : een toevalsvector); haar verdeling is de beeldkansmaat $\P_X = X_*\P$ op $\R$ (Oefening 11.9), vastgelegd door de verdelingsfunctie $F_X(t) = \P(X \leq t)$ (Oefening 9.3). $X$ heeft dichtheid $f$ als $\P_X = f\,\dd\lambda$ ; ze heet discreet als $\P_X$ een aftelbare combinatie van diracmassa’s is. De verwachtingswaarde is

\E[X] = \int_\Omega X\,\dd\P \qquad (X \geq 0 \text{ of } X \in L^1(\P)),

en de overdrachtsformule (Oefening 11.9) berekent haar in de verdeling: $\E[g(X)] = \int_\R g\,\dd\P_X$ — $= \sum g(x_k)p_k$ in het discrete geval, $= \int g(x)f(x)\dd x$ in het geval met een dichtheid: de formules uit het volume van bachelorjaar 2, nu stellingen van één theorie. De variantie is $\V(X) = \E[(X - \E X)^2] = \E[X^2] - (\E X)^2$ voor $X \in L^2$ .

Voorbeeld 22.2

De standaardverdelingen en hun opmerkelijke transformaties: bernoulli $\mathcal B(p)$ , binomiaal $\mathcal B(n, p)$ , meetkundig, poisson $\mathcal P(\lambda)$ (discreet: de tabellen uit het volume van bachelorjaar 2 blijven geldig); uniform op $\intcc01$ (de lebesguemaat zelf); exponentieel $\mathcal E(\lambda)$ (dichtheid $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); de gaussische verdeling $\mathcal N(m, \sigma^2)$ met dichtheid $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — een kansdichtheid volgens Probleem 10.1, met gemiddelde $m$ en variantie $\sigma^2$ (de gaussische momenten, Oefening 11.10).

Propositie 22.3 (Markov en Chebyshev)

Voor $X \geq 0$ en $a > 0$ is $\P(X \geq a) \leq \frac{\E X}{a}$ ; voor $X \in L^2$ is $\P\bigl(\abs{X - \E X} \geq a\bigr) \leq \frac{\V(X)}{a^2}$ .

Bewijs. Oefening 10.5(a); Chebyshev is Markov toegepast op $(X - \E X)^2$ . ∎

22.2 Onafhankelijkheid

Definitie 22.4

Deel- $\sigma$ -algebra’s $\mathcal A_1, \dots, \mathcal A_n \subseteq \mathcal A$ heten onafhankelijk als $\P(A_1\cap\dots\cap A_n) = \prod\P(A_i)$ voor alle $A_i \in \mathcal A_i$ ; gebeurtenissen zijn onafhankelijk als de $\sigma$ -algebra’s $\{\varnothing, A_i, A_i^c, \Omega\}$ dat zijn; en toevalsveranderlijken $X_1, \dots, X_n$ als de $\sigma$ -algebra’s $\sigma(X_i) = X_i^{-1}(\mathcal B(\R))$ dat zijn. Een oneindige familie is onafhankelijk als elke eindige deelfamilie dat is.

Stelling 22.5

$X_1, \dots, X_n$ zijn onafhankelijk dan en slechts dan als de verdeling van de vector $(X_1, \dots, X_n)$ de productmaat $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ is. In dat geval is voor $g_i \geq 0$ (of zodanig dat de producten integreerbaar zijn)

\E\Bigl[\prod_ig_i(X_i)\Bigr] = \prod_i\E[g_i(X_i)],

in het bijzonder $\E[XY] = \E X\,\E Y$ en $\V(X_1 + \dots + X_n) = \sum\V(X_i)$ voor onafhankelijke veranderlijken in $L^2$ .

Bewijs. Zijn de $X_i$ onafhankelijk, dan vallen de twee kansmaten $\P_{(X_1,\dots,X_n)}$ en $\bigotimes\P_{X_i}$ samen op alle producten $B_1\times\dots\times B_n$ van borelverzamelingen — een $\pi$ -systeem dat $\mathcal B(\R^n)$ voortbrengt (Propositie 11.2(b)) — en dus overal (Stelling 9.7). Omgekeerd ontbindt een productverdeling alle gebeurtenissen $\bigcap_iX_i^{-1}(B_i)$ : onafhankelijkheid. De formule voor de verwachtingswaarde is dan Tonelli of Fubini (Stelling 11.5) via de overdrachtsformule; $\E[XY] = \E X\E Y$ is het geval $g_i = \mathrm{id}$ , en het kwadraat ontwikkelen geeft de additiviteit van de varianties (de kruistermen $\E[(X_i - \E X_i)(X_j - \E X_j)] = 0$ ). ∎

Stelling 22.6 (Bestaan van onafhankelijke rijen)

Op $\bigl(\intcc01, \mathcal L, \lambda\bigr)$ bestaat er een rij $(U_n)_{n\geq1}$ onafhankelijke toevalsveranderlijken, elk uniform op $\intcc01$ . Bijgevolg bestaan er voor elke voorgeschreven verdelingen $(\mu_n)$ op $\R$ onafhankelijke $(X_n)$ met $\P_{X_n} = \mu_n$ .

Bewijs. Cijfers. Zij voor $\omega \in \intcc01$ $(b_k(\omega))$ haar binaire cijfers ( $\omega = \sum b_k2^{-k}$ ; kies de ontwikkeling die niet op louter enen eindigt — de dubbelzinnigheid betreft slechts een aftelbare, dus verwaarloosbare verzameling). Elke $b_k$ is een toevalsveranderlijke ( $\{b_k = 1\}$ is een eindige vereniging van dyadische intervallen) en de vector $(b_1, \dots, b_m)$ neemt elke waarde in $\{0,1\}^m$ aan op een dyadisch interval van lengte $2^{-m}$ : de $b_k$ zijn onafhankelijk en bernoulli $(\frac12)$ .

Hergroeperen. Splits $\N^*$ in oneindig veel disjuncte oneindige verzamelingen $(I_n)$ (bijvoorbeeld met priemmachten, of met diagonalen); zij $(k^n_j)_j$ een opsomming van $I_n$ en stel

U_n = \sum_{j\geq1} b_{k^n_j}\,2^{-j} .

Elke $U_n$ is uniform: haar binaire cijfers zijn onafhankelijke eerlijke bits, dus $\P(U_n \in [l2^{-m}, (l+1)2^{-m})) = 2^{-m}$ voor elk dyadisch interval, en de dyadische intervallen leggen de verdeling vast (Stelling 9.7). De $U_n$ zijn onafhankelijk: het zijn functies van disjuncte blokken van de onafhankelijke familie $(b_k)$ — formeel hangen de gebeurtenissen $\{U_n \in D_n\}$ voor dyadische $D_n$ af van eindig veel cijfers uit disjuncte verzamelingen, en ontbinden ze; het argument met het $\pi$ -systeem tilt dat op tot alle borelverzamelingen.

Willekeurige verdelingen. Zij $G_n(u) = \inf\{t : F_{\mu_n}(t) \geq u\}$ (de kwantielfunctie van de verdelingsfunctie $F_{\mu_n}$ ); de sleutelgelijkwaardigheid $G_n(u) \leq t \iff u \leq F_{\mu_n}(t)$ (rechtscontinuïteit van $F$ , monotonie) toont dat $X_n = G_n(U_n)$ meetbaar is met $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) = F_{\mu_n}(t)$ : dus verdeling $\mu_n$ ; de onafhankelijkheid wordt geërfd (functies van onafhankelijke veranderlijken, Oefening 22.3). ∎

Voorbeeld 22.7 (Het verjaardagsprobleem, eerlijk)

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

p_n = \prod_{k=1}^{n-1}\Bigl(1 - \frac kN\Bigr),

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

\ln p_n = -\frac{n(n-1)}{2N} + O\Bigl(\frac{n^3}{N^2}\Bigr), \qquad\text{dus}\qquad p_n \approx \eu^{-n^2/2N} .

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

22.3 Borel–Cantelli en de nul-een-wet

Stelling 22.8 (Borel–Cantelli)

Zij $(A_n)$ gebeurtenissen en $\limsup A_n = \bigcap_N \bigcup_{n\geq N}A_n$ (“ $A_n$ treedt oneindig vaak op”).

Is $\sum\P(A_n) < \infty$ , dan is $\P(\limsup A_n) = 0$ .
Is $\sum\P(A_n) = \infty$ en zijn de $A_n$ onafhankelijk, dan is $\P(\limsup A_n) = 1$ .

Bewijs. (1) is Oefening 9.4. (2): voor $N \leq M$ geeft de onafhankelijkheid van de complementen (Oefening 22.3)

\P\Bigl(\bigcap_{n=N}^{M}A_n^c\Bigr) = \prod_{n=N}^M\bigl(1 - \P(A_n)\bigr) \leq \exp\Bigl(-\sum_{n=N}^M\P(A_n)\Bigr) \xrightarrow[M \to \infty]{} 0

( $1 - x \leq \eu^{-x}$ ; de reeks divergeert). Dus is $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ voor elke $N$ , en heeft de dalende doorsnede over $N$ nog steeds kans $1$ (continuïteit van boven, Propositie 9.6). ∎

Stelling 22.9 (Nul-een-wet van Kolmogorov)

Zij $(X_n)$ onafhankelijk en $\mathcal T = \bigcap_N\sigma(X_N, X_{N+1}, \dots)$ de staart- $\sigma$ -algebra (gebeurtenissen die ongevoelig zijn voor elk eindig aantal van de $X_n$ : de convergentie van $\sum X_n$ , van $\frac{S_n}n$ , waarden van $\limsup$ ’s, …). Dan heeft elke $T \in \mathcal T$ $\P(T) \in \{0, 1\}$ .

Bewijs. Leg $N$ vast. De $\sigma$ -algebra’s $\sigma(X_1, \dots, X_N)$ en $\sigma(X_{N+1}, \dots)$ zijn onafhankelijk: gebeurtenissen die van disjuncte blokken afhangen, ontbinden op de voortbrengende $\pi$ -systemen (cilinders $\bigcap_{i\leq N}\{X_i \in B_i\}$ respectievelijk eindige voorwaarden op latere veranderlijken), en Dynkin (Stelling 9.4, tweemaal toegepast, telkens aan één kant) breidt de ontbinding uit. Een staartgebeurtenis $T$ ligt voor elke $N$ in $\sigma(X_{N+1}, \dots)$ : dus is $T$ onafhankelijk van elke $\sigma(X_1, \dots, X_N)$ , en dus van de $\sigma$ -algebra die ze voortbrengen, $\sigma(X_1, X_2, \dots)$ (nog eens Dynkin: de vereniging van de $\sigma(X_1,\dots,X_N)$ is een $\pi$ -systeem dat haar voortbrengt). Maar $T \in \sigma(X_1, X_2, \dots)$ eveneens: $T$ is onafhankelijk van zichzelf, dus $\P(T) = \P(T\cap T) = \P(T)^2$ : $\P(T) \in \{0, 1\}$ . ∎

22.4 Convergentiewijzen

Definitie 22.10

$X_n \to X$ bijna zeker als $\P(X_n \to X) = 1$ ; in kans als $\P(\abs{X_n - X} \geq \varepsilon) \to 0$ voor elke $\varepsilon > 0$ ; in $L^p$ als $\E\abs{X_n - X}^p \to 0$ .

Propositie 22.11

(a) b.z. convergentie impliceert convergentie in kans; (b) $L^p$ -convergentie impliceert convergentie in kans; (c) convergentie in kans impliceert b.z. convergentie langs een deelrij; (d) geen enkele andere implicatie geldt in het algemeen.

Bewijs. (a) $\P(\abs{X_n - X} \geq \varepsilon) \leq \P\bigl(\sup_{m\geq n}\abs{X_m - X} \geq \varepsilon\bigr) \downarrow \P\bigl(\limsup\{\abs{X_m - X} \geq \varepsilon\}\bigr) = 0$ bij b.z. convergentie (continuïteit van boven; de limsup-gebeurtenis sluit convergentie uit). (b) Markov: $\P(\abs{X_n - X} \geq \varepsilon) \leq \varepsilon^{-p}\,\E\abs{X_n - X}^p$ . (c) Kies $n_k$ met $\P(\abs{X_{n_k} - X} \geq 2^{-k}) \leq 2^{-k}$ ; Borel–Cantelli (1) maakt dat uiteindelijk b.z. $\abs{X_{n_k} - X} < 2^{-k}$ . (d) De schrijfmachine (Oefening 12.3) op $(\intcc01, \lambda)$ convergeert in $L^1$ en in kans maar nergens puntsgewijs; $n\mathbf 1_{\intoo0{1/n}} \to 0$ b.z. maar niet in $L^1$ ; de details en de overige tegenvoorbeelden staan in Oefening 22.6. ∎

22.5 De wet van de grote aantallen

Overal zijn $(X_n)$ onafhankelijk met dezelfde verdeling (i.i.d.), en $S_n = X_1 + \dots + X_n$ .

Stelling 22.12 (Zwakke wet van de grote aantallen)

Is $X_1 \in L^2$ , met $m = \E X_1$ , dan is

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

$\frac{S_n}n \to m$ in kans (en in $L^2$ ).

Bewijs. $\E\frac{S_n}n = m$ en $\V\bigl(\frac{S_n}n\bigr) = \frac{n\V(X_1)}{n^2}$ (Stelling 22.5); Chebyshev. ∎

Stelling 22.13 (Sterke wet van de grote aantallen)

Is $X_1 \in L^1$ , dan is

\frac{S_n}{n} \xrightarrow[n\to\infty]{\text{b.z.}} \E[X_1].

We bewijzen dat hier onder de sterkere hypothese $X_1 \in L^4$ ; het algemene geval ( $L^1$ : het bewijs van Etemadi) is de weekendopgave.

Bewijs onder $\E X_1^4 < \infty$ . Na centreren ( $X_i \mapsto X_i - m$ ) mogen we $m = 0$ aannemen. Ontwikkel:

\E[S_n^4] = \sum_{i,j,k,l}\E[X_iX_jX_kX_l] = n\,\E[X_1^4] + 3n(n-1)\,\bigl(\E[X_1^2]\bigr)^2 \leq C\,n^2 ,

want de onafhankelijkheid en het centreren doden elke term met een geïsoleerde factor ( $\E[X_iX_jX_kX_l] = \E[X_i]\E[\cdots] = 0$ tenzij de indices paren vormen: de enige overlevenden zijn de $n$ termen met $i=j=k=l$ en de $3n(n-1)$ termen met twee verschillende paren). Markov:

\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}{\varepsilon^4n^2},

sommeerbaar: Borel–Cantelli (1) geeft voor elke rationale $\varepsilon$ dat uiteindelijk b.z. $\abs{S_n/n} < \varepsilon$ ; doorsnijden over $\varepsilon \in \Q_+^*$ (aftelbaar veel gebeurtenissen met kans $1$ ) geeft $S_n/n \to 0$ b.z. ∎

Voorbeeld 22.14 (Wat de sterke wet oplevert)

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

Methode 22.15

De werkvolgorde voor asymptotische uitspraken over toevallige rijen: (1) Is de gebeurtenis een staartgebeurtenis? Dan is haar kans $0$ of $1$ (Stelling 22.9) en hoef je enkel te beslissen welke van beide. (2) Om b.z. uitspraken te bewijzen: Borel–Cantelli — sommeerbare kansen voor de “slechte” gebeurtenissen, via afschattingen van het type Markov of Chebyshev op de momenten die bestaan; de onafhankelijkheid is enkel voor de omgekeerde richting nodig. (3) Deelrij plus insluiting: bewijs de convergentie langs een hanteerbare deelrij en beheers de oscillatie ertussen met monotonie of maximaalongelijkheden — het skelet van het bewijs van Etemadi. (4) Voor limieten in verdeling: wacht op Hoofdstuk 23.

22.6 Oefeningen

Oefening 22.1 ★

(a) Zij $X$ met een continue strikt stijgende verdelingsfunctie $F$ . Toon aan dat $F(X)$ uniform is op $\intcc01$ , en dat $G(U) \sim F$ voor $U$ uniform en $G = F^{-1}$ : simulatie door inversie. (b) Bereken de verdelingsfunctie en de dichtheid van $X^2$ voor $X$ uniform op $\intcc{-1}1$ , en van $-\frac1\lambda\ln U$ voor $U$ uniform op $\intoo01$ .

Oplossing

Oplossing van Oefening 22.1.

(a) Voor $u \in \intoo01$ : $\P(F(X) \leq u) = \P(X \leq F^{-1}(u)) = F(F^{-1}(u)) = u$ (de continuïteit en de strikte monotonie maken $F$ een bijectie op $\intoo01$ met $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$ ): dus is $F(X)$ uniform. Omgekeerd is $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$ : om een verdeling te simuleren, pas je de inverse verdelingsfunctie toe op een uniforme steekproef.

(b) $Y = X^2$ met $X$ uniform op $\intcc{-1}1$ : voor $t \in \intcc01$ is $F_Y(t) = \P(-\sqrt t \leq X \leq \sqrt t) = \sqrt t$ : dichtheid $\frac1{2\sqrt t}\mathbf 1_{\intoo01}$ . En $\P\bigl(-\frac1\lambda\ln U \leq t\bigr) = \P(U \geq \eu^{-\lambda t}) = 1 - \eu^{-\lambda t}$ : de exponentiële verdeling $\mathcal E(\lambda)$ — de inversie in actie.

Oefening 22.2 ★

(a) Bereken het gemiddelde en de variantie van de poissonverdeling $\mathcal P(\lambda)$ en van de meetkundige verdeling met de overdrachtsformule. (b) Toon aan dat een positieve toevalsveranderlijke $T$ met $\P(T > t) > 0$ voor alle $t$ de geheugenloosheid $\P(T > t + s \mid T > t) = \P(T > s)$ voor alle $s, t \geq 0$ bezit dan en slechts dan als $T$ exponentieel is. (De overlevingsfunctie voldoet aan de functionaalvergelijking van Cauchy; de monotonie vervangt de continuïteit.)

Oplossing

Oplossing van Oefening 22.2.

(a) Poisson: $\E X = \sum_{k\geq0}k\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \lambda$ en $\E[X(X-1)] = \lambda^2$ , dus $\V = \lambda^2 + \lambda - \lambda^2 = \lambda$ . Meetkundig ( $\P(X = k) = p(1-p)^{k-1}$ ): $\E X = \frac1p$ en $\V = \frac{1-p}{p^2}$ (differentieer de meetkundige reeks tweemaal).

(b) $G(t) = \P(T > t)$ is niet-stijgend met $G(0^+)\dots$ ; $G \colon \intco0\infty \to \intoc01$ , en de geheugenloosheid luidt $G(t + s) = G(t)G(s)$ . Dan is $G(n t) = G(t)^n$ en $G(t/n) = G(t)^{1/n}$ : dus $G(q) = G(1)^q$ voor rationale $q \geq 0$ ; met $G(1) = \eu^{-\lambda}$ ( $\in \intoo01$ : $G(1) = 1$ zou $G \equiv 1$ afdwingen, onmogelijk voor een eindige toevalsveranderlijke, en $G(1) = 0$ is door de hypothese uitgesloten) en een willekeurige $t$ tussen rationale getallen inklemmen (monotonie): $G(t) = \eu^{-\lambda t}$ — de exponentiële verdeling. De omkering is een berekening.

Oefening 22.3 ★★

(a) Toon aan dat als $X_1, \dots, X_n$ onafhankelijk zijn en de $f_i$ borelfuncties, de $f_i(X_i)$ onafhankelijk zijn. (b) Toon aan dat gebeurtenissen $A_1, \dots, A_n$ onafhankelijk zijn dan en slechts dan als hun complementen dat zijn, en dan en slechts dan als de indicatoren $\mathbf 1_{A_i}$ onafhankelijke toevalsveranderlijken zijn. (c) (Paarsgewijs is zwakker) Twee eerlijke munten: $A =$ de eerste is kop, $B =$ de tweede is kop, $C =$ de twee stemmen overeen. Toon aan dat $A, B, C$ paarsgewijs onafhankelijk zijn maar niet onafhankelijk.

Oplossing

Oplossing van Oefening 22.3.

(a) $\sigma(f_i(X_i)) = f_i(X_i)^{-1}(\mathcal B) \subseteq X_i^{-1}(\mathcal B) = \sigma(X_i)$ ( $f_i$ is borel), en deel- $\sigma$ -algebra’s van onafhankelijke $\sigma$ -algebra’s zijn onafhankelijk (de definiërende identiteit geldt a fortiori).

(b) $\sigma(A_i) = \{\varnothing, A_i, A_i^c, \Omega\} = \sigma(A_i^c) = \sigma(\mathbf 1_{A_i})$ : alle drie de uitspraken beweren de onafhankelijkheid van dezelfde $\sigma$ -algebra’s. (Dat de ontbinding over de $A_i$ zich naar de complementen voortplant, is het argument met het $\lambda$ -systeem binnen de gelijkwaardigheid in Definitie 22.4 — of rechtstreeks in- en uitsluiting.)

(c) $\P(A) = \P(B) = \P(C) = \frac12$ ; en op paren is $A\cap B = A\cap C = B\cap C$ : elke doorsnede is “twee keer kop” of analoog, met kans $\frac14$ : paarsgewijs onafhankelijk. Maar $\P(A\cap B\cap C) = \P(\text{KK}) = \frac14 \neq \frac18$ : niet onafhankelijk — $C$ ligt door $A$ en $B$ vast.

Oefening 22.4 ★★

(a) (De oneindige aap) Een i.i.d. rij uniforme toetsaanslagen op een eindig alfabet bevat b.z. elke eindige tekst oneindig vaak: bewijs dat met Borel–Cantelli (2) op disjuncte blokken. (b) (Reeksen) Zij voor i.i.d. eerlijke bits $R_n$ de lengte van de reeks enen die op plaats $n$ begint. Toon aan dat b.z. $R_n \geq (1+\varepsilon)\log_2n$ slechts eindig vaak, en $R_n \geq \log_2 n$ oneindig vaak (beide helften van Borel–Cantelli; ga voor de tweede over op disjuncte blokken om onafhankelijkheid te winnen): de langste reeks in de eerste $n$ cijfers groeit als $\log_2n$ .

Oplossing

Oplossing van Oefening 22.4.

(a) Zij de tekst $T$ van lengte $L$ en $q = a^{-L}$ ( $a$ de grootte van het alfabet). De gebeurtenissen $E_k = \{$ de plaatsen $kL+1, \dots, (k+1)L$ spellen $T\}$ zijn onafhankelijk (disjuncte blokken i.i.d. letters), elk met kans $q > 0$ : dus $\sum\P(E_k) = \infty$ , en Borel–Cantelli (2) geeft b.z. oneindig veel voorkomens.

(b) Boven: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr) \leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$ , sommeerbaar: volgens Borel–Cantelli (1) zijn er b.z. slechts eindig veel zulke $n$ . Onder: pak disjuncte blokken — het $j$ -de van lengte $\ell_j = \lceil\log_2s_j\rceil$ beginnend in $s_j = \sum_{i<j}\ell_i$ ; de gebeurtenissen “blok $j$ bestaat enkel uit enen” zijn onafhankelijk met kans $2^{-\ell_j} \asymp \frac1{s_j} \asymp \frac1{j\log_2 j}$ , waarvan de som divergeert: Borel–Cantelli (2) geeft oneindig veel blokken met enkel enen, dat wil zeggen $R_{s_j} \geq \log_2 s_j$ oneindig vaak. Samen: de maximale reekslengte in de eerste $n$ cijfers is b.z. $(1 + o(1))\log_2n$ .

Oefening 22.5 ★★

Zij $(X_n)$ onafhankelijk. (a) Toon aan dat de convergentiestraal van $\sum X_n z^n$ b.z. een constante is (mogelijk $0$ of $\infty$ ). (b) Toon aan dat $\P(\sum X_n \text{ convergeert}) \in \{0, 1\}$ en $\P(S_n/n \to m) \in \{0,1\}$ . (c) Geef een gebeurtenis over $(X_n)$ die geen staartgebeurtenis is, en ga na dat de nul-een-wet er kan falen.

Oplossing

Oplossing van Oefening 22.5.

(a) $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ blijft ongewijzigd als eindig veel $X_n$ worden aangepast: voor elke $N$ is $R$ dus $\sigma(X_N, X_{N+1}, \dots)$ -meetbaar, dat wil zeggen staartmeetbaar. Dan heeft elke gebeurtenis $\{R \leq c\}$ kans $0$ of $1$ (Stelling 22.9), zodat de verdelingsfunctie van $R$ enkel de waarden $0$ en $1$ aanneemt: ze springt in één enkel punt $c_0 \in \intcc0{+\infty}$ , en $R = c_0$ b.z.

(b) De convergentie van $\sum X_n$ en van $\frac{S_n}n$ is ongevoelig voor het wijzigen van eindig veel termen (voor de tweede: de gewijzigde termen dragen $O(1/n) \to 0$ bij): staartgebeurtenissen; nul-een-wet.

(c) $\{X_1 > 0\}$ hangt van $X_1$ af: voor i.i.d. tekens ( $\P(X_1 = \pm1) = \frac12$ ) is haar kans $\frac12 \notin \{0,1\}$ — geen tegenspraak, want het is geen staartgebeurtenis.

Oefening 22.6 ★★

Geef op $(\intcc01, \lambda)$ — met bewijzen — toevalsveranderlijken zodat: (a) $X_n \to 0$ in kans en in elke $L^p$ , maar nergens b.z.; (b) $X_n \to 0$ b.z. maar in geen enkele $L^p$ ; (c) $X_n \to 0$ in $L^1$ maar niet in $L^2$ ; (d) en toon aan: convergeert $X_n \to X$ in kans met $\abs{X_n} \leq Y \in L^1$ , dan is $X_n \to X$ in $L^1$ (deelrijen + gedomineerde convergentie + de truc met de deeldeelrij).

Oplossing

Oplossing van Oefening 22.6.

Werk op $(\intcc01, \lambda)$ . (a) De schrijfmachine $\mathbf 1_{I_n}$ (Oefening 12.3): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (alle $p < \infty$ ), en dus ook in kans; in elke $\omega$ keren de waarden $0$ en $1$ allebei terug: nergens puntsgewijze convergentie. (b) $X_n = n\mathbf 1_{\intoo0{1/n}} \to 0$ buiten $0$ , maar $\norm{X_n}_p \geq n^{1 - 1/p} \geq 1$ . (c) $X_n = \sqrt n\,\mathbf 1_{\intoo0{1/n}}$ : $\E\abs{X_n} = n^{-1/2} \to 0$ en $\E X_n^2 = 1$ . (d) Haal uit elke deelrij (convergentie in kans) een verdere deelrij die b.z. convergeert (Propositie 22.11(c)); de gedomineerde convergentie geeft er $L^1$ -convergentie langs, met dezelfde limiet $X$ . Elke deelrij van de getallenrij $\E\abs{X_n - X}$ heeft dus een deeldeelrij die naar $0$ gaat: de hele rij gaat naar $0$ .

Oefening 22.7 ★★

Een opiniepeiling schat een onbekende verhouding $p$ met de empirische frequentie $\hat p_n$ van $n$ onafhankelijke trekkingen. (a) Chebyshev: toon aan dat $\P(\abs{\hat p_n - p} \geq \varepsilon) \leq \frac1{4n\varepsilon^2}$ (gebruik $p(1-p) \leq \frac14$ ). (b) Hoeveel trekkingen waarborgen met deze grens een fout $\leq 3\%$ met kans $\geq 95\%$ ? (Het ware antwoord, via Hoofdstuk 23, is ongeveer $1070$ : Chebyshev is eerlijk maar grof.)

Oplossing

Oplossing van Oefening 22.7.

(a) $\hat p_n = \frac{S_n}n$ met $S_n$ binomiaal: $\V(\hat p_n) = \frac{p(1-p)}n \leq \frac1{4n}$ , en Chebyshev (Propositie 22.3) geeft de grens. (b) Los $\frac1{4n(0.03)^2} \leq 0.05$ op: $n \geq \frac{1}{4\cdot0.0009\cdot0.05} \approx 5556$ . De centrale limietstelling zal $n \approx 1070$ rechtvaardigen voor dezelfde waarborg: Chebyshev betaalt haar algemeenheid met een factor $\approx 5$ .

Oefening 22.8 ★★★

(Bernstein) Definieer voor $f \in \mathcal C(\intcc01)$ de bernsteinveelterm $B_nf(x) = \sum_{k=0}^n\binom nkx^k(1-x)^{n-k}f\bigl(\frac kn\bigr)$ . (a) Herken $B_nf(x) = \E\bigl[f\bigl(\frac {S_n}n\bigr)\bigr]$ voor $S_n$ binomiaal $\mathcal B(n, x)$ . (b) Bewijs dat $B_nf \to f$ uniform op $\intcc01$ : splits op $\{\abs{\frac{S_n}n - x} \leq \delta\}$ en haar complement, met de uniforme continuïteit en Chebyshev met de uniforme grens $\V(\frac{S_n}n) \leq \frac1{4n}$ . (c) Besluit: een tweede, kanstheoretisch bewijs van de benaderingsstelling van Weierstrass (Gevolg 7.16), met de expliciete snelheid $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ voor de continuïteitsmodulus $\omega_f$ — bewijs minstens de vorm $O(\omega_f(n^{-1/2}))$ .

Oplossing

Oplossing van Oefening 22.8.

(a) Is $S_n \sim \mathcal B(n, x)$ , dan geeft de overdrachtsformule $\E\bigl[f(\frac{S_n}n)\bigr] = \sum_k\binom nkx^k(1-x)^{n-k}f(\frac kn) = B_nf(x)$ .

(b)–(c) Zij $\omega = \omega_f$ de continuïteitsmodulus ( $\abs{f(u) - f(v)} \leq \omega(\abs{u - v})$ , en $\omega(c \delta) \leq (1 + c)\,\omega(\delta)$ door stappen aaneen te schakelen). Dan is voor elke $\delta > 0$

\abs{f(u) - f(x)} \leq \Bigl(1 + \frac{(u - x)^2}{\delta^2}\Bigr)\omega(\delta)

(is $\abs{u - x} \leq \delta$ , dan duidelijk; anders is $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta) \omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2}) \omega(\delta)$ ). Neem verwachtingswaarden in $u = \frac{S_n}n$ :

\abs{B_nf(x) - f(x)} \leq \Bigl(1 + \frac{\V(S_n/n)}{\delta^2}\Bigr)\omega(\delta) \leq \Bigl(1 + \frac{1}{4n\delta^2}\Bigr)\omega(\delta) ;

met $\delta = n^{-1/2}$ : $\norm{B_nf - f}_\infty \leq \frac54\,\omega\bigl(n^{-1/2}\bigr) \leq \frac32\,\omega\bigl(n^{-1/2}\bigr) \to 0$ (uniforme continuïteit op de compacte verzameling): een kanstheoretische stelling van Weierstrass, met een expliciete en uniforme snelheid.

Oefening 22.9 ★★★

(Plaatjesverzamelaar) Kaarten van $n$ soorten worden uniform met teruglegging getrokken; zij $T_n$ het aantal trekkingen tot alle soorten gezien zijn. (a) Schrijf $T_n = \sum_{k=1}^{n}\tau_k$ met $\tau_k$ meetkundig met parameter $\frac{n - k + 1}n$ en de $\tau_k$ onafhankelijk, en leid af dat $\E T_n = n\,H_n \sim n\ln n$ ( $H_n$ het harmonische getal) en $\V(T_n) \leq \frac{\pi^2}6n^2$ . (b) Chebyshev: $\frac{T_n}{n\ln n} \to 1$ in kans. (c) Verfijn met Borel–Cantelli: toon rechtstreeks aan dat $\P(T_n > \beta n\ln n) \leq n^{1 - \beta}$ voor $\beta > 1$ (de somgrens op de gebeurtenis dat een soort na $\beta n\ln n$ trekkingen wordt gemist, met $1 - x \leq \eu^{-x}$ ), en leid af dat langs $n = 2^m$ b.z. uiteindelijk $T_n \leq \beta n\ln n$ voor elke $\beta > 2$ .

Oplossing

Oplossing van Oefening 22.9.

(a) Zijn $k - 1$ soorten verzameld, dan is elke trekking nieuw met kans $p_k = \frac{n-k+1}n$ : $\tau_k$ is meetkundig $(p_k)$ , en de $\tau_k$ zijn onafhankelijk (dat zijn de trekkingen). Sommen: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$ ; en $\V(T_n) = \sum\frac{1 - p_k}{p_k^2} \leq n^2\sum_{j=1}^n\frac1{j^2} \leq \frac{\pi^2}6n^2$ .

(b) Chebyshev: $\P\bigl(\abs{T_n - nH_n} \geq \varepsilon n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2n} \to 0$ , en $\frac{nH_n}{n\ln n} \to 1$ : dus $\frac{T_n}{n\ln n} \to 1$ in kans.

(c) Somgrens: $T_n > t$ betekent dat een soort na $\lceil t\rceil$ trekkingen ongezien is, dus $\P(T_n > t) \leq n(1 - \frac1n)^{t} \leq n\,\eu^{-t/n}$ ; bij $t = \beta n\ln n$ geeft dat $\leq n^{1 - \beta}$ . Voor $\beta > 1$ is $\sum_m 2^{m(1-\beta)} < \infty$ : Borel–Cantelli geeft langs $n = 2^m$ b.z. uiteindelijk $T_n \leq \beta n\ln n$ — in het bijzonder voor elke $\beta > 2$ zoals gevraagd (langs de deelrij werkt elke $\beta > 1$ ).

Oefening 22.10 ★★

Met de constructie met cijfers (Stelling 22.6): (a) ga met een rechtstreekse berekening na dat $U = \sum b_{2k}2^{-k}$ (de cijfers met even index van een uniforme $\omega$ ) uniform is en onafhankelijk van $V = \sum b_{2k-1}2^{-k}$ ; (b) leid een meetbare bijectie op nulverzamelingen na af tussen $\intcc01$ en $\intcc01^2$ die de maat behoudt, en becommentarieer: één uniform toevalsgetal bevat er twee (en aftelbaar veel) onafhankelijke — vergelijk met de peanokromme (Probleem 6.1), die wel surjectiviteit haalde maar geen maatbehoud of injectiviteit.

Oplossing

Oplossing van Oefening 22.10.

(a) De cijfers met even index $(b_{2k})_k$ zijn i.i.d. eerlijke bits (een deelfamilie van de onafhankelijke cijferfamilie), dus geeft $U = \sum_kb_{2k}2^{-k}$ aan elk dyadisch interval de juiste kans (als in Stelling 22.6): uniform; en evenzo $V$ ; en $(U, V)$ hangen van disjuncte cijferblokken af: onafhankelijk (ontbinding op dyadische rechthoeken, dan Dynkin).

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ is meetbaar met $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (overeenstemming op dyadische rechthoeken plus uniciteit). De cijfers afwisselen definieert een inverse buiten de (verwaarloosbare) verzameling dyadische rationale getallen in een van beide factoren: een maatbehoudende bijectie tussen deelverzamelingen van volle maat van $\intcc01$ en $\intcc01^2$ . Contrast met Peano (Probleem 6.1): de continuïteit dwong surjectiviteit af zonder injectiviteit; de continuïteit inruilen voor louter meetbaarheid koopt een maatisomorfisme — de dimensie is onzichtbaar voor de maattheorie en zichtbaar voor de topologie.

Oefening 22.11 ★★

(Records) Zij $(X_n)_{n\geq1}$ i.i.d. met continue verdelingsfunctie, en zeg dat er op tijdstip $n$ een record optreedt als $X_n > \max(X_1, \dots, X_{n-1})$ (tijdstip $1$ is een record). Zij $R_n$ de recordindicator. (a) Toon aan dat $\P(R_n = 1) = \frac1n$ (wegens de symmetrie is elk van de $n!$ ordeningen van $X_1, \dots, X_n$ even waarschijnlijk, en gelijke waarden hebben kans $0$ ). (b) Toon aan dat de $R_n$ onafhankelijk zijn (tel de ordeningen die met voorgeschreven recordposities verenigbaar zijn, of beargumenteer dat de onderlinge volgorde van $X_1, \dots, X_{n-1}$ onafhankelijk is van de rang van $X_n$ ertussen). (c) Leid met Borel–Cantelli (Stelling 22.8, beide helften) af dat er b.z. oneindig veel records optreden, maar dat records op opeenvolgende tijdstippen $n, n+1$ oneindig vaak optreden met kans — beslis welke! — en bereken $\sum_n\P(R_n = 1, R_{n+1} = 1)$ .

Oplossing

Oplossing van Oefening 22.11.

(a) De continuïteit van de verdeling maakt gelijke waarden tot nulgebeurtenissen (als in de argumenten met ordestatistieken uit het hoofdstuk), en de $n!$ onderlinge ordeningen van $(X_1, \dots, X_n)$ zijn verwisselbaar, dus even waarschijnlijk. $R_n = 1$ betekent dat het maximum op de laatste plaats zit: kans $\frac{(n-1)!}{n!} = \frac1n$ .

(b) Leg $n$ vast en conditioneer op de onderlinge ordening van $X_1, \dots, X_{n-1}$ : $X_n$ in een van de $n$ mogelijke rangplaatsen invoegen is uniform en onafhankelijk van die ordening (de verwisselbaarheid van het $n$ -tal). Dus is $R_n$ (de gebeurtenis “ $X_n$ neemt de bovenste plaats in”) onafhankelijk van de hele recordgeschiedenis $(R_1, \dots, R_{n-1})$ , die een functie is van de onderlinge ordening van de eerste $n - 1$ veranderlijken. Inductie geeft de volledige onafhankelijkheid met $\P(R_n = 1) = \frac1n$ .

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ met onafhankelijkheid: de tweede helft van Borel–Cantelli geeft b.z. oneindig veel records (records houden nooit op — maar ze worden logaritmisch zeldzamer: $\E[\#\text{records} \leq n] = H_n \approx \ln n$ ). Opeenvolgende records: $\P(R_n = R_{n+1} = 1) = \frac1{n(n+1)}$ (onafhankelijkheid), en

\sum_n\frac1{n(n+1)} = \sum_n\Bigl(\frac1n - \frac1{n+1}\Bigr) = 1 < \infty :

de eerste helft van Borel–Cantelli is van toepassing — er treden b.z. slechts eindig veel paren opeenvolgende records op.

Oefening 22.12 ★★

(De langste reeks kop) Werp oneindig vaak met een eerlijke munt, en zij $L_n$ de lengte van de langste reeks opeenvolgende koppen binnen de eerste $n$ worpen. (a) Toon aan dat voor elke $\varepsilon > 0$ b.z. uiteindelijk $L_n \leq (1 + \varepsilon)\log_2n$ (de kans dat er onder de eerste $n$ worpen een reeks van lengte $\ell$ begint, is hoogstens $n2^{-\ell}$ ; Borel–Cantelli langs $n = 2^k$ ). (b) Toon aan dat b.z. uiteindelijk $L_n \geq (1 - \varepsilon)\log_2n$ (hak de eerste $n$ worpen in $\lfloor n/\ell\rfloor$ disjuncte blokken van lengte $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ ; de blokken zijn onafhankelijk, elk volledig kop met kans $2^{-\ell}$ , en de kans dat geen enkel blok volledig kop is, is hoogstens $\exp(-n2^{-\ell}/\ell)$ ; sommeer opnieuw langs $n = 2^k$ ). (c) Besluit $\frac{L_n}{\log_2n} \to 1$ b.z.: in een miljoen eerlijke worpen mag je een reeks van ongeveer $20$ koppen verwachten — en een gegevensverzameling zonder zo’n reeks is waarschijnlijk verzonnen.

Oplossing

Oplossing van Oefening 22.12.

(a) Een reeks van lengte $\ell$ die op plaats $i \leq n$ begint, heeft kans $2^{-\ell}$ ; somgrens: $\P(L_n \geq \ell) \leq n2^{-\ell}$ . Met $\ell_n = (1 + \varepsilon)\log_2n$ : $\P(L_n \geq \ell_n) \leq n^{-\varepsilon}$ . Langs $n = 2^k$ is $\sum_k2^{-k\varepsilon} < \infty$ , dus b.z. uiteindelijk $L_{2^k} < (1+\varepsilon)k$ (Borel–Cantelli); voor algemene $n$ kies je $2^{k-1} < n \leq 2^k$ en gebruik je de monotonie van $L_n$ plus $\log_22^{k-1} \leq \log_2n$ : $L_n \leq L_{2^k} < (1 + \varepsilon)k \leq (1 + \varepsilon)\frac{k}{k-1} \log_2n$ , en de extra factor wordt opgeslorpt door $\varepsilon$ licht te vergroten.

(b) Met $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ en $m = \lfloor n/\ell\rfloor$ disjuncte blokken: de blokken zijn onafhankelijk, elk volledig kop met kans $2^{-\ell} \geq n^{-(1-\varepsilon)}/2$ , dus is

\P(L_n < \ell) \leq \bigl(1 - 2^{-\ell}\bigr)^{m} \leq \exp\bigl(-m2^{-\ell}\bigr) \leq \exp\Bigl(-c\,\frac{n^{\varepsilon}}{\log_2n}\Bigr)

voor een constante $c > 0$ en grote $n$ . Die kansen zijn sommeerbaar langs $n = 2^k$ (zelfs over alle $n$ ): Borel–Cantelli geeft b.z. uiteindelijk $L_n \geq (1 - \varepsilon)\log_2n$ (de monotonie vult de gaten tussen de $2^k$ op als in (a), zonder schade).

(c) Beide grenzen langs een rij $\varepsilon = \frac1j$ , met de aftelbaar vele gebeurtenissen van volle maat doorsneden: $\frac{L_n}{\log_2n} \to 1$ b.z. Voor $n = 10^6$ is $\log_2n \approx 19.9$ — een reeks van $\approx 20$ koppen is geen verdachte anomalie maar een wiskundige zekerheid, en haar afwezigheid is een aanwijzing dat een mens “toeval” heeft nagebootst (mensen durven zelden meer dan $5$ of $6$ koppen op rij op te schrijven).

22.7 Probleem: het bewijs van Etemadi van de sterke wet

Probleem 22.1

Weekendopgave — de sterke wet van de grote aantallen voor i.i.d. integreerbare veranderlijken

De sterke wet van Kolmogorov — $\frac{S_n}n \to \E X_1$ b.z. voor i.i.d. $X_n \in L^1$ — had lang enkel ingewikkelde bewijzen; in 1981 vond N. Etemadi er een van opvallende zuinigheid, dat niets voorbij dit hoofdstuk gebruikt (en de onafhankelijkheid zelfs verzwakt tot paarsgewijze onafhankelijkheid). Wij volgen het. Zij $(X_n)$ paarsgewijs onafhankelijk, identiek verdeeld en integreerbaar; $m = \E X_1$ en $S_n = X_1 + \dots + X_n$ .

Deel I — Herleidingen.

Toon aan dat het volstaat $X_n \geq 0$ te behandelen (splits $X_n = X_n^+ - X_n^-$ : ga na dat de twee helften opnieuw paarsgewijs onafhankelijk, identiek verdeeld en integreerbaar zijn). Neem voortaan $X_n \geq 0$ aan.
(Afknotting) Zij $Y_n = X_n\,\mathbf 1_{X_n \leq n}$ en $S_n^* = Y_1 + \dots + Y_n$ . Toon aan dat

$\sum_{n\geq1}\P(X_n \neq Y_n) = \sum_{n\geq1}\P(X_1 > n) \leq \E[X_1] < \infty$

(Oefening 11.3), en leid met Borel–Cantelli af dat $\frac{S_n - S_n^*}{n} \to 0$ b.z.: het volstaat dus $\frac{S^*_n}n \to m$ b.z. te bewijzen.
Toon aan dat $\E Y_n = \E\bigl[X_1\mathbf 1_{X_1\leq n}\bigr] \to m$ (monotone convergentie), en dus $\frac1n\sum_{k\leq n}\E Y_k \to m$ (Cesàro): het volstaat dus $\frac{S_n^* - \E S_n^*}{n} \to 0$ b.z. te bewijzen.

Deel II — De variantieafschatting.

Toon aan dat

$\V(Y_n) \leq \E[Y_n^2] = \E\bigl[X_1^2\,\mathbf 1_{X_1 \leq n}\bigr]$

en, met de laagjesformule (Propositie 11.8), de sleutelgrens

$\sum_{n\geq1}\frac{\V(Y_n)}{n^2} \leq \sum_{n\geq1}\frac1{n^2}\, \E\bigl[X_1^2\mathbf 1_{X_1\leq n}\bigr] \leq C\,\E[X_1] < \infty$

(verwissel de som en de verwachtingswaarde — Tonelli voor reeksen — en schat $\sum_{n \geq x}\frac1{n^2} \leq \frac2{\max(x,1)}$ af voor de inwendige schatting $x^2\sum_{n\geq x}n^{-2} \leq 2x$ ).

Deel III — Convergentie langs meetkundige deelrijen. Leg $\alpha > 1$ vast en zij $k_j = \lfloor\alpha^j\rfloor$ .

Toon met de paarsgewijze onafhankelijkheid (de varianties tellen op, Stelling 22.5 — ga na dat de additiviteit van de varianties enkel paarsgewijze onafhankelijkheid vergt) en Chebyshev aan dat voor elke $\varepsilon > 0$

$\sum_{j\geq1}\P\Bigl(\Bigl| \frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}\Bigr| \geq \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j\geq1}\frac1{k_j^2} \sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_{n\geq1}\V(Y_n) \sum_{j\,:\,k_j\geq n}\frac1{k_j^2} .$
Toon aan dat $\sum_{j : k_j \geq n}k_j^{-2} \leq \frac{C_\alpha}{n^2}$ (meetkundige reeksen; pas op met het gehele deel: zorg voor iets als $k_j \geq \frac{\alpha^j}2$ zodra $\alpha^j \geq 2$ ), en besluit met vraag 4 en Borel–Cantelli:

$\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \xrightarrow[j\to\infty]{\text{b.z.}} 0, \qquad\text{en dus}\qquad \frac{S^*_{k_j}}{k_j} \to m \ \text{b.z.}$

Deel IV — Insluiting en besluit.

Toon voor $k_j \leq n \leq k_{j+1}$ met de monotonie van $S^*_n$ (niet-negatieve termen!) aan dat

$\frac{k_j}{k_{j+1}}\,\frac{S^*_{k_j}}{k_j} \;\leq\; \frac{S^*_n}{n} \;\leq\; \frac{k_{j+1}}{k_j}\,\frac{S^*_{k_{j+1}}}{k_{j+1}},$

en leid b.z. af:

$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq \limsup\frac{S^*_n}n \leq \alpha\,m .$
Laat $\alpha \downarrow 1$ gaan langs een rij en besluit $\frac{S_n^*}n \to m$ b.z., en dus (Deel I) de sterke wet van de grote aantallen:

$\boxed{\ \frac{S_n}{n} \xrightarrow[n\to\infty]{\text{b.z.}} \E[X_1].\ }$
Waar precies volstond de paarsgewijze (in plaats van de volledige) onafhankelijkheid? Som de drie plaatsen op waar hypothesen van het onafhankelijkheidstype werden ingeroepen.

Deel V — Dividenden.

(De normale getallen van Borel) Toon aan dat $\lambda$ -bijna elke $x \in \intcc01$ normaal is in elke basis $b \geq 2$ : elk cijfer $0, \dots, b-1$ verschijnt met asymptotische frequentie $\frac1b$ (leg $b$ en een cijfer vast, pas de sterke wet toe op de indicatorveranderlijken — verantwoord dat de cijfers in basis $b$ van een uniforme veranderlijke i.i.d. uniform op $\{0,\dots,b-1\}$ zijn, als in Stelling 22.6 — en snijd daarna de aftelbaar vele gebeurtenissen met kans één). Geef één expliciet niet-normaal getal, en bedenk: de stelling beweert de normaliteit van bijna alle getallen, en toch blijft de normaliteit van $\sqrt2$ of $\pi$ bewijzen een open probleem.
(Monte carlo, gewaarborgd) Verantwoord de methode van Voorbeeld 22.14(b) volledig voor $g \in L^1(\intcc01^d)$ : construeer de i.i.d. uniforme steekproef op $\intcc01^d$ met Stelling 22.6 en Oefening 22.10, en formuleer wat de sterke wet oplevert.

Deel VI — Wat volledige onafhankelijkheid oplevert: maximaalongelijkheden en toevallige reeksen. Etemadi geeft enkel paarsgewijze onafhankelijkheid uit; de resterende delen buiten de volledige (onderlinge) versie uit. Zij $(Z_n)$ onafhankelijke gecentreerde veranderlijken in $L^2$ en $S_k = Z_1 + \dots + Z_k$ (een nieuwe notatie, los van de $X_n$ hierboven).

(Maximaalongelijkheid van Kolmogorov) Bewijs voor $\varepsilon > 0$ dat

$\P\Bigl(\max_{1\leq k\leq n}\abs{S_k} \geq \varepsilon\Bigr) \;\leq\; \frac1{\varepsilon^2}\sum_{k=1}^n\V(Z_k) :$

de prijs van Chebyshev koopt het maximum (deel de gebeurtenis op naar de eerste index $k$ met $\abs{S_k} \geq \varepsilon$ ; schrijf op dat stuk $S_n^2 \geq S_k^2 + 2S_k(S_n - S_k)$ en gebruik de onafhankelijkheid van de coalities $(Z_1, \dots, Z_k)$ en $(Z_{k+1}, \dots, Z_n)$ , Stelling 22.5). Wijs de stap aan waar paarsgewijze onafhankelijkheid niet langer zou volstaan.
(Eenreeksstelling van Khinchin–Kolmogorov) Leid af: is $\sum_n\V(Z_n) < \infty$ , dan convergeert $\sum_nZ_n$ bijna zeker (toon aan dat de partiële sommen b.z. een cauchyrij vormen: laat $m \to \infty$ gaan in de maximaalongelijkheid toegepast op $Z_{N+1}, \dots, Z_{N+m}$ , en daarna $N \to \infty$ ).
(Rademacherreeksen) Zij $(\varepsilon_n)$ i.i.d. tekens met $\P(\varepsilon_n = \pm1) = \frac12$ (Stelling 22.6), en zij $(x_n)$ een rij reële getallen. Toon aan dat $\sum_nx_n\varepsilon_n$ b.z. convergeert zodra $\sum_nx_n^2 < \infty$ ; toon ook aan dat, wat $(x_n)$ ook is, de kans dat $\sum_nx_n\varepsilon_n$ convergeert $0$ of $1$ is (Stelling 22.9).
De omkering, elementair. Stel $T_n = \sum_{k\leq n}x_k\varepsilon_k$ en $s_n^2 = \sum_{k\leq n}x_k^2$ , en neem aan dat $s_n \to \infty$ . (a) Bewijs de ongelijkheid van Paley–Zygmund: voor $Z \geq 0$ met $\E Z^2 < \infty$ en $0 < \theta < 1$ is

$\P\bigl(Z > \theta\,\E Z\bigr) \;\geq\; (1 - \theta)^2\,\frac{(\E Z)^2}{\E Z^2}$

(splits $\E Z$ op het niveau $\theta\E Z$ en pas Cauchy–Schwarz toe op het bovenste stuk). (b) Toon aan dat $\E T_n^4 \leq 3s_n^4$ . (c) Leid $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr) \geq \frac3{16}$ af en besluit dat $\sum_nx_n\varepsilon_n$ b.z. divergeert; en dus de dichotomie

$\sum_nx_n\varepsilon_n\ \text{convergeert b.z.} \iff \sum_nx_n^2 < \infty .$
(Toevallige harmonische reeks) Besluit dat $\sum_n\frac{\varepsilon_n}{n^s}$ b.z. convergeert dan en slechts dan als $s > \frac12$ . Voor $\frac12 < s \leq 1$ convergeert de reeks b.z. terwijl $\sum_nn^{-s} = \infty$ : toevallige tekens brengen opheffing ter sterkte van een vierkantswortel voort — vergelijk met de alternerende reeks $\sum_n\frac{(-1)^n}{n^s}$ , die voor elke $s > 0$ convergeert.

Deel VII — Concentratie: de ongelijkheid van Hoeffding. De sterke wet zegt dat $\frac{S_n}n \to m$ ; concentratieongelijkheden zeggen hoe onwaarschijnlijk een afwijking is bij elke vaste $n$ .

(Lemma van Hoeffding) (a) Toon aan dat $\cosh\lambda \leq \eu^{\lambda^2/2}$ voor alle $\lambda \in \R$ , door de twee reeksen term voor term te vergelijken. (b) Zij $Z$ gecentreerd met $a \leq Z \leq b$ en $a < b$ . Toon aan dat

$\E\,\eu^{\lambda Z} \leq \exp\Bigl(\frac{\lambda^2(b - a)^2}8\Bigr)$

(begrens $\eu^{\lambda z}$ op $\intcc ab$ met haar koorde, neem verwachtingswaarden, en bestudeer $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ met $p = \frac{-a}{b-a}$ en $t = \lambda(b - a)$ : toon aan dat $\varphi(0) = \varphi'(0) = 0$ en $\varphi'' \leq \frac14$ ).
(Ongelijkheid van Hoeffding) Zij $X_1, \dots, X_n$ onafhankelijk met $a_i \leq X_i \leq b_i$ en $S_n = X_1 + \dots + X_n$ . Bewijs voor $t > 0$

$\P\bigl(S_n - \E S_n \geq t\bigr) \leq \exp\Bigl(\frac{-2t^2}{\sum_{i=1}^n(b_i - a_i)^2}\Bigr),$

en dezelfde grens voor de onderste staart (exponentiële Chebyshev: begrens $\E\,\eu^{\lambda(S_n - \E S_n)}$ met de onafhankelijkheid en vraag 17, en optimaliseer daarna over $\lambda > 0$ ).
(De sterke wet, begrensd geval, met een snelheid) Zij de $X_i$ i.i.d. met waarden in $\intcc ab$ en $m = \E X_1$ . Toon aan dat

$\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b - a)^2}\Bigr)$

en vind $\frac{S_n}n \to m$ b.z. terug met Borel–Cantelli: een tweede bewijs van de sterke wet voor begrensde veranderlijken — geen afknotting, een exponentiële snelheid bij elke eindige $n$ , maar begrensde termen en volledige onafhankelijkheid. Vergelijk de hypothesen met die van Etemadi.
(Monte carlo, gewaarborgd bij vaste $n$ ) Zij $g \colon \intcc01^d \to \intcc01$ meetbaar en $(U_k)$ de i.i.d. uniforme steekproef uit vraag 11. Toon voor gegeven $\varepsilon, \delta > 0$ aan dat

$n \geq \frac{\log(2/\delta)}{2\varepsilon^2} \implies \P\Bigl(\Bigl|\frac1n\sum_{k=1}^ng(U_k) - \int g\,\dd\lambda_d\Bigr| \geq \varepsilon\Bigr) \leq \delta,$

en evalueer de drempel voor $\varepsilon = \delta = 10^{-2}$ . De grens bevat $d$ niet: vergelijk met vraag 11 en met deterministische roosters.

Deel VIII — Hoe groot is een toevalswandeling? Op weg naar de geïtereerde logaritme. Zij $S_n = \varepsilon_1 + \dots + \varepsilon_n$ de eenvoudige toevalswandeling, opgebouwd uit i.i.d. eerlijke tekens.

(Subgaussische staarten) Toon aan dat $\E\,\eu^{\lambda S_n} = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ en leid voor $x > 0$ af dat

$\P(S_n \geq x) \leq \eu^{-x^2/(2n)}, \qquad \P(\abs{S_n} \geq x) \leq 2\,\eu^{-x^2/(2n)} .$
Leid met Borel–Cantelli af dat

$\limsup_{n\to\infty}\frac{\abs{S_n}} {\sqrt{2n\log n}} \leq 1 \quad\text{b.z.}$

(sommeer voor $\eta > 0$ de staartgrenzen in $x = (1 + \eta)\sqrt{2n\log n}$ , en snijd daarna over $\eta = \frac1p$ ). In het bijzonder leeft de wandeling op de schaal $\sqrt n$ van de centrale limietstelling, op een logaritmische factor na — ver onder de grove grens $\abs{S_n} \leq n$ .
Toon langs de verdubbelende deelrij $n_j = 2^j$ aan dat

$\limsup_{j\to\infty}\frac{S_{n_j}} {\sqrt{2n_j\log\log n_j}} \leq 1 \quad\text{b.z.},$

en bedenk: de wet van de geïtereerde logaritme (Khinchin; Hartman–Wintner voor algemene gecentreerde termen in $L^2$ ) zegt dat

$\limsup_{n\to\infty}\frac{S_n} {\sqrt{2n\log\log n}} = 1 \quad\text{b.z.}$

Leg precies uit wat de zonet bewezen schatting langs een deelrij scheidt van de bovenste helft van die uitspraak (men moet $\max_{n_j \leq n \leq n_{j+1}}S_n$ binnen elk blok beheersen, wat een maximaalongelijkheid op de exponentiële schaal vergt) en ga kwantitatief na dat de ongelijkheid van vraag 12 daarvoor te zwak is. De onderste helft berust op het tweede lemma van Borel–Cantelli toegepast op onafhankelijke blokken; beide helften zijn eerlijk materiaal van bachelorjaar 3 voor een aparte cursus kansrekening.
(Uniforme afwijking over een eindige klasse) Zij $A_1, \dots, A_N$ gebeurtenissen in een herhaalbaar experiment, en schat elke kans met haar empirische frequentie $\hat p_i$ over $n$ i.i.d. herhalingen. Toon door de ongelijkheid van Hoeffding met een somgrens te combineren aan dat

$\P\Bigl(\max_{i\leq N}\,\abs{\hat p_i - \P(A_i)} > \varepsilon\Bigr) \;\leq\; 2N\,\eu^{-2n\varepsilon^2},$

en leid de regel voor de steekproefgrootte af: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ waarborgt dat alle $N$ schattingen tegelijk $\varepsilon$ -nauwkeurig zijn met kans $\geq 1 - \delta$ . Bereken $n$ voor $N = 10^6$ , $\varepsilon = 0.01$ en $\delta = 0.05$ : de logaritmische prijs van de uniformiteit.
(Het toevallige harmonische venster) Toon door de twee helften van de theorie van de toevallige reeksen te combineren aan dat voor i.i.d. tekens $(\varepsilon_n)$ de reeks $\sum_n\frac{\varepsilon_n}{n^\alpha}$ b.z. convergeert als $\alpha > \frac12$ en b.z. divergeert als $\alpha \leq \frac12$ ; contrasteer met de absolute convergentie (die $\alpha > 1$ vergt): op het venster $\alpha \in \intoc{\frac12}1$ is de convergentie een werkelijk kanstheoretisch verschijnsel — opheffing, geen grootte.

Oplossing

Oplossing van Probleem 22.1.

1. $X_n^{\pm}$ zijn borelfuncties van $X_n$ : ze blijven paarsgewijs onafhankelijk (Oefening 22.3(a)) en identiek verdeeld en integreerbaar, met $\E X_1 = \E X_1^+ - \E X_1^-$ . Geldt de stelling voor niet-negatieve veranderlijken, pas haar dan toe op beide helften en trek af: $\frac{S_n}n = \frac{S_n^+}n - \frac{S_n^-}n \to \E X_1^+ - \E X_1^- = m$ b.z.

2. $\P(X_n \neq Y_n) = \P(X_n > n) = \P(X_1 > n)$ (gelijke verdelingen), en $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1 \geq n) \leq \E X_1 < \infty$ (Oefening 11.3(a)). Borel–Cantelli (1): b.z. is $X_n = Y_n$ voor alle grote $n$ , dus is $S_n - S_n^*$ uiteindelijk constant in $n$ : $\frac{S_n - S_n^*}n \to 0$ b.z., en de twee genormeerde sommen delen hun asymptotische gedrag.

3. $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$ : de monotone convergentie geeft $\E Y_n \to m$ ; en de cesàrogemiddelden van een convergente rij convergeren naar dezelfde limiet: $\frac{\E S_n^*}n = \frac1n\sum_{k\leq n}\E Y_k \to m$ . Het volstaat dus $\frac{S^*_n - \E S^*_n}{n} \to 0$ b.z. te bewijzen.

4. $\V(Y_n) \leq \E Y_n^2 = \E[X_1^2\mathbf 1_{X_1\leq n}]$ . Met Tonelli voor reeksen:

\sum_n\frac{\E[X_1^2\mathbf 1_{X_1\leq n}]}{n^2} = \E\Bigl[X_1^2\!\!\sum_{n \geq \max(X_1, 1)}\!\frac1{n^2} \Bigr] \leq \E\Bigl[X_1^2\cdot\frac{4}{\max(X_1,1)}\Bigr] \leq 4\,\E[X_1] < \infty,

met $\sum_{n\geq x}n^{-2} \leq \frac4x$ voor $x \geq 1$ (voor $x \geq 2$ : $\leq \frac1{x-1} \leq \frac2x$ ; voor $1 \leq x < 2$ : $\leq \frac{\pi^2}6 \leq \frac4x$ , want $\frac4x > 2$ ), en $X_1^2/\max(X_1, 1) \leq X_1$ in beide gevallen $X_1 \gtrless 1$ .

5. De paarsgewijze onafhankelijkheid geeft $\E[(Y_i - \E Y_i)(Y_j - \E Y_j)] = 0$ voor $i \neq j$ (de productformule voor twee veranderlijken), dus tellen de varianties op: $\V(S^*_k) = \sum_{n\leq k}\V(Y_n)$ . Chebyshev op elke $k_j$ en sommeren:

\sum_j\P\Bigl(\abs{S^*_{k_j} - \E S^*_{k_j}} \geq \varepsilon k_j\Bigr) \leq \frac1{\varepsilon^2}\sum_j\frac1{k_j^2}\sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_n\V(Y_n)\!\!\sum_{j : k_j\geq n}\!\frac1{k_j^2}

(Tonelli voor de niet-negatieve dubbele reeks).

6. $k_j = \lfloor\alpha^j\rfloor \geq \frac{\alpha^j}2$ (geldig zodra $\alpha^j \geq 1$ , dus voor alle $j \geq 0$ : $\lfloor x\rfloor \geq \frac x2$ voor $x \geq 1$ ). Bijgevolg is

\sum_{j : k_j \geq n}\frac1{k_j^2} \leq 4\sum_{j : \alpha^j \geq n}\alpha^{-2j} \leq \frac{4}{1 - \alpha^{-2}}\cdot\frac1{n^2} = \frac{C_\alpha}{n^2},

(meetkundige reeks vanaf de eerste $j$ met $\alpha^j \geq n$ ). Samen met de vragen 4 en 5 is de dubbele som eindig; en Borel–Cantelli (1), voor elke rationale $\varepsilon$ toegepast en doorsneden, geeft $\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \to 0$ b.z., en met vraag 3: $\frac{S^*_{k_j}}{k_j} \to m$ b.z.

7. $Y_n \geq 0$ maakt $n \mapsto S^*_n$ niet-dalend: voor $k_j \leq n \leq k_{j+1}$ is

\frac{S^*_{k_j}}{k_{j+1}} \leq \frac{S^*_n}{n} \leq \frac{S^*_{k_{j+1}}}{k_j},

wat na $\frac{k_j}{k_{j+1}}$ en $\frac{k_{j+1}}{k_j}$ in te voegen de weergegeven insluiting is. Omdat $\frac{k_{j+1}}{k_j} \to \alpha$ , geeft vraag 6 b.z.

\frac m\alpha \leq \liminf_n\frac{S^*_n}n \leq \limsup_n\frac{S^*_n}n \leq \alpha m .

8. Pas vraag 7 toe voor $\alpha = 1 + \frac1p$ met $p \in \N^*$ : aftelbaar veel b.z.-gebeurtenissen; op hun doorsnede geeft $p \to \infty$ dat $\lim\frac{S^*_n}n = m$ b.z. Met de vragen 1 tot 3 is $\frac{S_n}n \to \E X_1$ b.z.: de sterke wet van de grote aantallen, onder paarsgewijze onafhankelijkheid.

9. Hypothesen van het onafhankelijkheidstype doken driemaal op: (i) de additiviteit van de varianties (vraag 5) — paarsgewijs volstaat; (ii) de gelijke verdeling, in de sommen bij de afknotting (vraag 2) en de berekening van de verwachtingswaarde (vraag 3) — helemaal geen onafhankelijkheid; (iii) Borel–Cantelli (1) (vragen 2 en 6) — geldig zonder enige onafhankelijkheid. De volledige onderlinge onafhankelijkheid werd nooit ingeroepen: de waarneming van Etemadi.

10. Leg een basis $b$ en een cijfer $r$ vast. De cijfers $(d_k)$ in basis $b$ van een uniforme $\omega$ zijn i.i.d. uniform op $\{0, \dots, b-1\}$ (elke waarde van de cijfervector beslaat een interval van lengte $b^{-m}$ : woordelijk het argument van Stelling 22.6). De sterke wet toegepast op de i.i.d. begrensde veranderlijken $\mathbf 1_{d_k = r}$ geeft: b.z. gaat de frequentie van het cijfer $r$ naar $\frac1b$ . De aftelbaar vele paren $(b, r)$ doorsnijden: bijna elk getal is eenvoudig normaal in elke basis. Een expliciet niet-normaal getal: $x = 0.100100100\ldots_2$ (de frequentie van de enen is $\frac13 \neq \frac12$ ). Het contrast is ontnuchterend: bijna alle getallen zijn normaal, en toch is de normaliteit van $\sqrt2$ , $\eu$ of $\pi$ onbewezen — de maattheorie telt zonder te tonen.

11. Door Oefening 22.10 te itereren levert één uniforme veranderlijke een rij i.i.d. uniforme vectoren $U_k$ op $\intcc01^d$ op (splits de cijferverzameling van elke $U_n$ uit Stelling 22.6 in $d$ deelfamilies). Voor $g \in L^1(\intcc01^d)$ zijn de veranderlijken $g(U_k)$ i.i.d. en integreerbaar met gemiddelde $\int g\,\dd\lambda_d$ (overdracht): de sterke wet geeft

\frac1n\sum_{k=1}^ng(U_k) \xrightarrow[n\to\infty]{\text{b.z.}} \int_{\intcc01^d}g\,\dd\lambda_d :

de monte-carlo-integratie convergeert bijna zeker, in elke dimensie — de grootte van de fout is de zaak van de centrale limietstelling (Hoofdstuk 23).

12. Zij $A_k = \{\abs{S_k} \geq \varepsilon\} \cap \bigcap_{j<k}\{\abs{S_j} < \varepsilon\}$ : de $A_k$ zijn disjunct met vereniging $A = \{\max_{k\leq n}\abs{S_k} \geq \varepsilon\}$ . Dan is

\E S_n^2 \geq \sum_{k=1}^n\E\bigl[S_n^2\mathbf 1_{A_k}\bigr] = \sum_{k=1}^n\E\Bigl[\bigl(S_k^2 + 2S_k(S_n - S_k) + (S_n - S_k)^2\bigr)\mathbf 1_{A_k}\Bigr] \geq \sum_{k=1}^n\E\bigl[S_k^2\mathbf 1_{A_k}\bigr],

want de kruisterm verdwijnt: $S_k\mathbf 1_{A_k}$ is een borelfunctie van de coalitie $(Z_1, \dots, Z_k)$ , die onafhankelijk is van $S_n - S_k$ , een functie van $(Z_{k+1}, \dots, Z_n)$ (Stelling 22.5), dus $\E[S_k\mathbf 1_{A_k}(S_n - S_k)] = \E[S_k\mathbf 1_{A_k}]\,\E[S_n - S_k] = 0$ . Op $A_k$ is $S_k^2 \geq \varepsilon^2$ , waaruit $\E S_n^2 \geq \varepsilon^2\sum_k\P(A_k) = \varepsilon^2\P(A)$ ; en $\E S_n^2 = \sum_{k\leq n}\V(Z_k)$ (de varianties tellen op). De beslissende stap is de ontbinding: $S_k\mathbf 1_{A_k}$ is een niet-lineaire functie van het hele eerste blok, en haar onafhankelijkheid van het tweede blok is onafhankelijkheid van coalities — de paarsgewijze onafhankelijkheid van de $Z_i$ ontkoppelt enkel paren en zou dat niet rechtvaardigen.

13. Leg $N$ vast en pas vraag 12 toe op $Z_{N+1}, \dots, Z_{N+m}$ :

\P\Bigl(\max_{N < k \leq N+m}\abs{S_k - S_N} > \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j=N+1}^{N+m}\V(Z_j) \leq \frac{r_N}{\varepsilon^2}, \qquad r_N = \sum_{j>N}\V(Z_j) .

De gebeurtenissen stijgen met $m$ ; de continuïteit van onderen geeft $\P(\sup_{k>N}\abs{S_k - S_N} > \varepsilon) \leq r_N/\varepsilon^2$ , en $r_N \to 0$ volgens de hypothese. Bijgevolg is voor elke $p \in \N^*$ $\P\bigl(\bigcap_N\{\sup_{k>N} \abs{S_k - S_N} > \frac1p\}\bigr) \leq \inf_Np^2r_N = 0$ : bijna zeker is er voor elke $p$ een $N$ met $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (snijd de aftelbaar vele b.z.-gebeurtenissen over $p$ door), zodat $\abs{S_k - S_l} \leq \frac2p$ voor alle $k, l > N$ : de partiële sommen zijn b.z. cauchy, en dus b.z. convergent.

14. De veranderlijken $Z_n = x_n\varepsilon_n$ zijn onafhankelijk (borelfuncties van onafhankelijke veranderlijken, Oefening 22.3(a)) en gecentreerd, met $\V(Z_n) = x_n^2$ : vraag 13 is van toepassing zodra $\sum_nx_n^2 < \infty$ en geeft b.z. convergentie. In het algemeen wordt voor elke $N$ de convergentie van $\sum_nx_n\varepsilon_n$ niet beïnvloed door de waarden van $\varepsilon_1, \dots, \varepsilon_N$ : de convergentiegebeurtenis ligt in de staart- $\sigma$ -algebra van de onafhankelijke rij $(\varepsilon_n)$ , zodat de nul-een-wet van Kolmogorov (Stelling 22.9) haar kans tot $0$ of $1$ dwingt.

15. (a) Splitsen op het niveau $\theta\E Z$ en Cauchy–Schwarz op het bovenste stuk geeft

\E Z = \E\bigl[Z\mathbf 1_{Z \leq \theta\E Z}\bigr] + \E\bigl[Z\mathbf 1_{Z > \theta\E Z}\bigr] \leq \theta\,\E Z + \sqrt{\E Z^2}\, \sqrt{\P(Z > \theta\E Z)} ,

dus $(1 - \theta)\E Z \leq \sqrt{\E Z^2\,\P(Z > \theta\E Z)}$ ; kwadrateer. (b) Ontwikkel $T_n^4 = \sum_{i,j,k,l}x_ix_jx_kx_l\, \E[\varepsilon_i\varepsilon_j\varepsilon_k\varepsilon_l]$ : de verwachtingswaarde is $1$ wanneer de indices paren vormen (alle vier gelijk, of twee verschillende paren, dat laatste in $3$ schikkingen) en $0$ anders (een ongepaard teken heeft gemiddelde nul en splitst wegens de onafhankelijkheid af). Bijgevolg is

\E T_n^4 = \sum_kx_k^4 + 3\sum_{i\neq j}x_i^2x_j^2 = 3s_n^4 - 2\sum_kx_k^4 \leq 3s_n^4 .

\P\Bigl(\abs{T_n} > \frac{s_n}2\Bigr) = \P\Bigl(T_n^2 > \frac{s_n^2}4\Bigr) \geq \Bigl(\frac34\Bigr)^2 \frac{s_n^4}{3s_n^4} = \frac3{16} .

Convergeerde de reeks met positieve kans, dan convergeerde ze b.z. (vraag 14), dus was $\sup_n\abs{T_n} < \infty$ b.z., en zou een $M$ voldoen aan $\P(\sup_n\abs{T_n} > M) < \frac3{16}$ ; maar zodra $s_n > 2M$ is $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2) \geq \frac3{16}$ : tegenspraak. De divergentie is dus bijna zeker, en met vraag 14 is de dichotomie volledig.

16. Hier is $x_n = n^{-s}$ en $\sum_nn^{-2s} < \infty$ precies wanneer $s > \frac12$ : volgens de vragen 14 en 15 convergeert $\sum_n\frac{\varepsilon_n}{n^s}$ b.z. dan en slechts dan als $s > \frac12$ (voor $s \leq \frac12$ b.z. divergentie). Voor $\frac12 < s \leq 1$ is de convergentie nooit absoluut. De vergelijking is leerzaam: volmaakt alternerende tekens heffen op met sterkte $n^{-s}$ voor elke $s > 0$ , terwijl typische toevallige tekens enkel op wortelsterkte opheffen — de toevalswandeling van vraag 21 groeit als $\sqrt n$ , en de sommatie van Abel zet precies die groei om in de convergentie van $\sum\varepsilon_nn^{-s}$ voor $s > \frac12$ .

17. (a) $\cosh\lambda = \sum_k\frac{\lambda^{2k}}{(2k)!}$ en $\eu^{\lambda^2/2} = \sum_k\frac{\lambda^{2k}}{2^kk!}$ ; en $(2k)! \geq 2^kk!$ geldt term voor term, want $\frac{(2k)!}{k!} = \prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (elke factor voldoet aan $k + i \geq 2i$ voor $i \leq k$ ), zodat zelfs $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$ . (b) Merk op dat $a \leq 0 \leq b$ ( $Z$ is gecentreerd), en dat wegens de convexiteit van $z \mapsto \eu^{\lambda z}$ voor $z \in \intcc ab$

\eu^{\lambda z} \leq \frac{b - z}{b - a}\,\eu^{\lambda a} + \frac{z - a}{b - a}\,\eu^{\lambda b}, \qquad\text{dus}\qquad \E\,\eu^{\lambda Z} \leq \frac{b\,\eu^{\lambda a} - a\,\eu^{\lambda b}}{b - a} = (1 - p)\eu^{-pt} + p\,\eu^{(1-p)t} = \eu^{\varphi(t)}

met $p = \frac{-a}{b-a} \in \intcc01$ , $t = \lambda(b - a)$ en $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ . Dan is $\varphi(0) = 0$ , verdwijnt $\varphi'(t) = -p + \frac{p\eu^t}{1 - p + p\eu^t}$ in $0$ , en is $\varphi''(t) = \rho(1 - \rho) \leq \frac14$ voor $\rho = \frac{p\eu^t}{1 - p + p\eu^t} \in \intcc01$ : Taylor tot orde $2$ geeft $\varphi(t) \leq \frac{t^2}8 = \frac{\lambda^2(b-a)^2}8$ .

18. Voor $\lambda > 0$ geven Markov toegepast op de positieve veranderlijke $\eu^{\lambda(S_n - \E S_n)}$ (Propositie 22.3) en de productformule voor onafhankelijke veranderlijken

\P(S_n - \E S_n \geq t) \leq \eu^{-\lambda t}\prod_{i=1}^n\E\,\eu^{\lambda(X_i - \E X_i)} \leq \exp\Bigl(-\lambda t + \frac{\lambda^2}8\sum_i(b_i - a_i)^2\Bigr),

volgens vraag 17(b) toegepast op elke gecentreerde $X_i - \E X_i \in \intcc{a_i - \E X_i}{b_i - \E X_i}$ (dezelfde breedte). De exponent minimaliseren in $\lambda = \frac{4t}{D}$ met $D = \sum_i(b_i - a_i)^2$ levert $-\frac{2t^2}D$ . De onderste staart volgt door het resultaat op $(-X_i)$ toe te passen.

19. Neem $t = n\varepsilon$ en $D = n(b - a)^2$ :

\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n^2\varepsilon^2}{n(b-a)^2}\Bigr) = 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b-a)^2}\Bigr),

wat sommeerbaar is in $n$ (een reeks van meetkundig type): Borel–Cantelli (Stelling 22.8) geeft dat b.z. uiteindelijk $\abs{\frac{S_n}n - m} < \varepsilon$ ; doorsnijden over $\varepsilon = \frac1p$ levert $\frac{S_n}n \to m$ b.z. Vergelijking: Etemadi vraagt enkel $X_1 \in L^1$ en paarsgewijze onafhankelijkheid, en levert geen snelheid; Hoeffding vraagt begrensdheid en volledige onafhankelijkheid, en levert bij elke eindige $n$ een expliciete exponentiële waarborg — de twee stellingen beantwoorden verschillende vragen over dezelfde limiet.

20. De $g(U_k)$ zijn i.i.d. met waarden in $\intcc01$ en gemiddelde $\int g\,\dd\lambda_d$ (overdracht), dus geeft vraag 18 met $b_i - a_i = 1$ en $t = n\varepsilon$ de tweezijdige grens $2\eu^{-2n\varepsilon^2} \leq \delta$ zodra $\eu^{2n\varepsilon^2} \geq \frac2\delta$ , dat wil zeggen $n \geq \frac{\log(2/\delta)}{2\varepsilon^2}$ . Voor $\varepsilon = \delta = 10^{-2}$ :

n \geq \frac{\log 200}{2\cdot10^{-4}} = \frac{5.2983\ldots}{0.0002} \approx 26\,492 :

ongeveer $26\,500$ trekkingen waarborgen een nauwkeurigheid van $1\%$ met $99\%$ vertrouwen — in elke dimensie $d$ , voor elke meetbare integrand met waarden in $\intcc01$ . De sterke wet van vraag 11 beloofde convergentie zonder enige waarborg bij eindige $n$ ; een deterministisch rooster met $k$ punten per as kost $k^d$ evaluaties, exponentieel in $d$ . De concentratie is wat van monte carlo een methode maakt in plaats van een hoop.

21. Onafhankelijkheid en de productformule: $\E\,\eu^{\lambda S_n} = (\E\,\eu^{\lambda\varepsilon_1})^n = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ volgens vraag 17(a). Markov op $\eu^{\lambda S_n}$ :

\P(S_n \geq x) \leq \eu^{-\lambda x + n\lambda^2/2} = \eu^{-x^2/(2n)} \qquad\text{in het optimum } \lambda = \frac xn,

en de symmetrische grens voor $-S_n$ (dezelfde verdeling) verdubbelt de constante voor $\abs{S_n}$ .

22. Leg $\eta > 0$ vast en stel $x_n = (1 + \eta)\sqrt{2n\log n}$ voor $n \geq 2$ :

\P(\abs{S_n} \geq x_n) \leq 2\exp\bigl(-(1 + \eta)^2\log n\bigr) = \frac{2}{n^{(1+\eta)^2}},

sommeerbaar omdat $(1 + \eta)^2 > 1$ . Borel–Cantelli: b.z. is $\abs{S_n} < (1 + \eta)\sqrt{2n\log n}$ voor alle grote $n$ , dus $\limsup_n\frac{\abs{S_n}}{\sqrt{2n\log n}} \leq 1 + \eta$ b.z.; de b.z.-gebeurtenissen voor $\eta = \frac1p$ met $p \in \N^*$ doorsnijden geeft de bewering. De wandeling van grootte $n$ heeft een typische amplitude $\sqrt n$ (haar variantie), en zelfs haar ergste uitstapjes overschrijden die schaal met hoogstens $\sqrt{2\log n}$ .

23. Met $n_j = 2^j$ en $x = (1 + \eta)\sqrt{2n_j\log\log n_j}$ (gedefinieerd voor $j \geq 2$ ) geeft vraag 21

\P\bigl(S_{n_j} \geq x\bigr) \leq \exp\bigl(-(1 + \eta)^2\log\log n_j\bigr) = (j\log 2)^{-(1+\eta)^2},

sommeerbaar in $j$ omdat $(1 + \eta)^2 > 1$ : Borel–Cantelli en $\eta = \frac1p$ geven $\limsup_jS_{n_j}/\sqrt{2n_j \log\log n_j} \leq 1$ b.z. Wat voor de volledige bovenste helft ontbreekt, is de brug tussen de ijkpunten: men moet aantonen dat $\max_{n_j\leq n\leq n_{j+1}}S_n$ slechts eindig vaak $(1+\eta) \sqrt{2n_j\log\log n_j}$ overschrijdt, wat een maximaalongelijkheid met gaussische staarten vergt (de spiegelingsongelijkheid van Lévy of die van Ottaviani, hier niet bewezen). Vraag 12 is kwantitatief te zwak: ze begrenst de kans door

\frac{n_j}{(1+\eta)^2\,2n_j\log\log n_j} = \frac{1}{2(1+\eta)^2\log(j\log2)},

wat naar $0$ gaat maar niet sommeerbaar is in $j$ : Borel–Cantelli kan niet besluiten. De onderste helft van de wet van de geïtereerde logaritme past het tweede lemma van Borel–Cantelli toe op de onafhankelijke aangroeiingen $S_{n_{j+1}} - S_{n_j}$ , met bijpassende ondergrenzen voor staarten van gaussisch type. Beide verfijningen zijn echte kansrekening van bachelorjaar 3, één cursus verderop; wat deze opgave zonder hulp levert, is de exacte schaal van de geïtereerde logaritme langs meetkundige tijdstippen.

24. Elke $\hat p_i$ is een gemiddelde van $n$ i.i.d. indicatorveranderlijken met waarden in $\intcc01$ en gemiddelde $\P(A_i)$ : Hoeffding geeft $\P(\abs{\hat p_i - \P(A_i)} > \varepsilon) \leq 2\eu^{-2n\varepsilon^2}$ . De somgrens vermenigvuldigt met $N$ . $2N\eu^{-2n\varepsilon^2} \leq \delta$ oplossen: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ . Numeriek: $\ln\frac{2\cdot10^6}{0.05} = \ln(4\cdot10^7) \approx 17.5$ , dus $n \geq \frac{17.5}{2\cdot10^{-4}} \approx 87\,600$ : één kans schatten tot op $\pm1\%$ vergt ongeveer $18\,500$ trekkingen ( $\ln(2/\delta)/2\varepsilon^2$ ), en een miljoen kansen slechts $\approx 4.7$ keer zoveel — de uniformiteit kost $\ln N$ , niet $N$ : de waarneming die de minimalisering van het empirische risico, en daarmee het machinaal leren, statistisch mogelijk maakt.

25. De veranderlijken $X_n = \frac{\varepsilon_n} {n^\alpha}$ zijn onafhankelijk, gecentreerd en begrensd, met $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$ . Is $\alpha > \frac12$ , dan convergeert de variantiereeks, en geeft de eenreeksstelling (Deel VI) de b.z. convergentie van $\sum X_n$ . Is $\alpha \leq \frac12$ , dan divergeert de variantiereeks, en geeft de omgekeerde helft (het argument van Paley–Zygmund uit Deel VI, toepasbaar omdat de termen door $1$ begrensd zijn) b.z. divergentie. De absolute convergentie vraagt $\sum n^{-\alpha} < \infty$ : $\alpha > 1$ . Op $\intoc{\frac12}1$ convergeert de reeks b.z. hoewel $\sum\abs{X_n} = \infty$ zeker is: de tekens spannen samen om op te heffen, met kans één — convergentie door opheffing, onzichtbaar voor elke absolute test, en (wegens de nul-een-wet) toch met een deterministisch vonnis.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst