Universitaire wiskunde — Bachelor jaar 3 · Bachelor Year 3

22Kansrekening: grondslagen en de wet van de grote aantallen

Jaar 2 bouwde kansrekening op aftelbare ruimten; de maattheorie verwijdert nu elke restrictie. Een waarschijnlijkheidsruimte is een maatruimte van totale massa $1$ , stochastische variabelen zijn meetbare afbeeldingen, verwachting is de Lebesgue-integraal — en onmiddellijk past het hele analytische arsenaal (Hoofdstukken 9, 10 en 11) toe op toeval. Dit hoofdstuk installeert het woordenboek, construeert oneindige rijen van onafhankelijke stochastische variabelen (op $\intcc01$ , uit binaire cijfers: toeval verbergt zich in de Lebesgue-maat), bewijst de lemma’s van Borel–Cantelli en de nul–één-wet van Kolmogorov, ordent de convergentiewijzen, en bewijst de wet van de grote aantallen — de stelling die frequenties naar kansen laat convergeren en statistiek mogelijk maakt. Het weekendprobleem geeft het bewijs van Etemadi van de sterke wet in haar definitieve $L^1$ -vorm.

22.1 Het woordenboek

Definitie 22.1

Een waarschijnlijkheidsruimte is een maatruimte $(\Omega, \mathcal A, \P)$ met $\P(\Omega) = 1$ ; elementen van $\mathcal A$ zijn gebeurtenissen, en een eigenschap geldt bijna zeker (b.z.) als haar gebeurtenis kans $1$ heeft. Een stochastische variabele is een meetbare afbeelding $X \colon \Omega \to \R$ (of $\R^d$ : een stochastische vector); haar wet is de pushforward-waarschijnlijkheidsmaat $\P_X = X_*\P$ op $\R$ (Oefening 11.9), bepaald door de verdelingsfunctie $F_X(t) = \P(X \leq t)$ (Oefening 9.3). $X$ heeft dichtheid $f$ als $\P_X = f\,\dd\lambda$ ; zij is discreet als $\P_X$ een aftelbare combinatie van Dirac-massa’s is. De verwachting is

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

en de overdrachtsstelling (Oefening 11.9) berekent haar in de wet: $\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 dichtheidsgeval: de formules van Jaar 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 standaardwetten en hun noemenswaardige transformaties: Bernoulli $\mathcal B(p)$ , binomiaal $\mathcal B(n, p)$ , geometrisch, Poisson $\mathcal P(\lambda)$ (discreet: de tabellen van Jaar 2 blijven geldig); uniform op $\intcc01$ (de Lebesgue-maat zelf); exponentieel $\mathcal E(\lambda)$ (dichtheid $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); de Gaussische $\mathcal N(m, \sigma^2)$ met dichtheid $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — een kansdichtheid door Probleem 10.1, met gemiddelde $m$ en variantie $\sigma^2$ (Gaussische momenten, Oefening 11.10).

Propositie 22.3 (Markov en Chebyshev)

Voor $X \geq 0$ en $a > 0$ : $\P(X \geq a) \leq \frac{\E X}{a}$ ; voor $X \in L^2$ : $\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

Sub- $\sigma$ -algebra’s $\mathcal A_1, \dots, \mathcal A_n \subseteq \mathcal A$ zijn onafhankelijk als $\P(A_1 \cap \dots \cap A_n) = \P(A_1)\cdots\P(A_n)$ voor alle $A_i \in \mathcal A_i$ ; een familie is onafhankelijk als elke eindige deelverzameling dat is. Stochastische variabelen $X_1, \dots, X_n$ zijn onafhankelijk als de $\sigma$ -algebra’s $\sigma(X_i)$ dat zijn; equivalent, $\P(X_1 \in B_1, \dots, X_n \in B_n) = \prod_i\P(X_i \in B_i)$ voor Borel $B_i$ , of (wanneer wetten dichtheden of massa’s hebben) de gezamenlijke wet is het product van de randwetten.

Stelling 22.5

$X_1, \dots, X_n$ zijn onafhankelijk dan en slechts dan als de wet van de vector $(X_1, \dots, X_n)$ de productmaat $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ is. In dat geval, voor $g_i \geq 0$ (of zodat 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 $L^2$ -variabelen.

Bewijs. Als de $X_i$ onafhankelijk zijn, komen de twee waarschijnlijkheidsmaten $\P_{(X_1,\dots,X_n)}$ en $\bigotimes\P_{X_i}$ overeen 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)) — dus overal (Stelling 9.7). Omgekeerd factoriseert een productwet alle gebeurtenissen $\bigcap_iX_i^{-1}(B_i)$ : onafhankelijkheid. De verwachtingsformule is dan Tonelli/Fubini (Stelling 11.5) via de overdrachtsstelling; $\E[XY] = \E X\E Y$ is het geval $g_i = \mathrm{id}$ , en het kwadraat ontwikkelen geeft de additiviteit van varianties (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 een rij $(U_n)_{n\geq1}$ van onafhankelijke stochastische variabelen, elk uniform op $\intcc01$ . Bijgevolg bestaan, voor willekeurige voorgeschreven wetten $(\mu_n)$ op $\R$ , onafhankelijke $(X_n)$ met $\P_{X_n} = \mu_n$ .

Bewijs. Cijfers. Voor $\omega \in \intcc01$ , zij $(b_k(\omega))$ haar binaire cijfers ( $\omega = \sum b_k2^{-k}$ ; kies de ontwikkeling die niet in louter $1$ ’s eindigt — ambigüiteit betreft alleen een aftelbare, dus nul, verzameling). Elk $b_k$ is een stochastische variabele ( $\{b_k = 1\}$ is een eindige unie van dyadische intervallen) en de vector $(b_1, \dots, b_m)$ neemt elke waarde in $\{0,1\}^m$ op een dyadisch interval van lengte $2^{-m}$ : de $b_k$ zijn onafhankelijke Bernoulli $(\frac12)$ .

Herordenen. Splits $\N^*$ in oneindig veel disjuncte oneindige verzamelingen $(I_n)$ (b.v. via priemmachten, of diagonalen); laat $(k^n_j)_j$ $I_n$ opsommen en stel

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

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

Willekeurige wetten. Zij $G_n(u) = \inf\{t : F_{\mu_n}(t) \geq u\}$ (de kwantielfunctie van de verdelingsfunctie $F_{\mu_n}$ ); de sleutel-equivalentie $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)$ : wet $\mu_n$ ; onafhankelijkheid wordt geërfd (functies van onafhankelijke variabelen, Oefening 22.3). ∎

Voorbeeld 22.7 (Het verjaardagsprobleem, eerlijk)

Onder $n$ personen met onafhankelijke, uniforme verjaardagen over $N = 365$ dagen is de kans dat alle verjaardagen verschillen

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

door geïtereerde conditionering (of rechtstreeks: de gunstige $N(N-1)\cdots(N - n + 1)$ over het totaal $N^n$ , een telargument dat de productformule van onafhankelijkheid rigoureus maakt). Logaritmen nemen en $-\ln(1 - x) = x + O(x^2)$ gebruiken:

\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$ zit bij $n \approx \sqrt{2N\ln2} \approx 1{,}18\sqrt N$ : voor $N = 365$ , $n = 23$ ( $p_{23} = 0{,}4927$ ). Twee moraal. Ten eerste verschijnen botsingen onder $n$ items in $N$ dozen op de schaal $n \sim \sqrt N$ , niet $n \sim N$ — de verjaardags-schaling die hashbotsingen en de $\sqrt N$ -kost van verjaardagsaanvallen in cryptografie regeert. Ten tweede is de berekening een sjabloon: de $\binom n2$ paar-botsingsgebeurtenissen zijn niet onafhankelijk, maar het antwoord gedraagt zich alsof zij dat wel waren ( $\eu^{-\binom n2/N}$ is precies de onafhankelijke-paren-heuristiek) — een eerste instantie van de Poisson-benadering, rigoureus gemaakt in het weekendprobleem van Hoofdstuk 23 (ongelijkheid van Le Cam).

22.3 Borel–Cantelli en de nul–één-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”).

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

Bewijs. (1) is Oefening 9.4. (2): voor $N \leq M$ geeft onafhankelijkheid van 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 $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ voor elke $N$ , en de dalende doorsnede over $N$ heeft nog kans $1$ (continuïteit van boven, Propositie 9.6). ∎

Stelling 22.9 (Nul–één-wet van Kolmogorov)

Zij $(X_n)$ onafhankelijk en $\mathcal T = \bigcap_N\sigma(X_N, X_{N+1}, \dots)$ de staart- $\sigma$ -algebra (gebeurtenissen ongevoelig voor enig eindig aantal van de $X_n$ : 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. Fixeer $N$ . De $\sigma$ -algebra’s $\sigma(X_1, \dots, X_N)$ en $\sigma(X_{N+1}, \dots)$ zijn onafhankelijk: gebeurtenissen die van disjuncte blokken afhangen factoriseren op de voortbrengende $\pi$ -systemen (cilinders $\bigcap_{i\leq N}\{X_i \in B_i\}$ , resp. eindige voorwaarden op latere variabelen), en Dynkin (Stelling 9.4, tweemaal toegepast, één kant per keer) breidt de factorisatie uit. Een staartgebeurtenis $T$ ligt in $\sigma(X_{N+1}, \dots)$ voor elke $N$ : $T$ is onafhankelijk van elke $\sigma(X_1, \dots, X_N)$ , dus van de $\sigma$ -algebra die zij voortbrengen, $\sigma(X_1, X_2, \dots)$ (Dynkin nogmaals: de unie van de $\sigma(X_1,\dots,X_N)$ is een $\pi$ -systeem dat haar voortbrengt). Maar $T \in \sigma(X_1, X_2, \dots)$ ook: $T$ is onafhankelijk van zichzelf, $\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 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$ onder 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 $\abs{X_{n_k} - X} < 2^{-k}$ uiteindelijk, b.z. (d) De typewriter (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$ ; details en de resterende tegenvoorbeelden in Oefening 22.6. ∎

22.5 De wet van de grote aantallen

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

Stelling 22.12 (Zwakke wet van de grote aantallen)

Als $X_1 \in L^2$ , met $m = \E X_1$ :

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

Als $X_1 \in L^1$ , dan

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

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

Bewijs onder $\E X_1^4 < \infty$ . Centreren ( $X_i \mapsto X_i - m$ ), neem $m = 0$ aan. 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 ,

aangezien onafhankelijkheid en centreren elke term met een geïsoleerde factor doden ( $\E[X_iX_jX_kX_l] = \E[X_i]\E[\cdots] = 0$ tenzij de indices paren: de enige overlevers zijn de $n$ termen $i=j=k=l$ en de $3n(n-1)$ termen met twee distincte 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 $\abs{S_n/n} < \varepsilon$ uiteindelijk, b.z.; doorsnijden over $\varepsilon \in \Q_+^*$ (aftelbaar veel kans- $1$ -gebeurtenissen): $S_n/n \to 0$ b.z. ∎

Voorbeeld 22.14 (Wat de sterke wet koopt)

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

Methode 22.15

De werkvolgorde voor asymptotische uitspraken over stochastische rijen: (1) Is de gebeurtenis een staartgebeurtenis? Dan is haar kans $0$ of $1$ (Stelling 22.9) en men hoeft alleen te beslissen welke. (2) Om b.z.-uitspraken te bewijzen: Borel–Cantelli — sommeerbare kansen voor de “slechte” gebeurtenissen, via Markov/Chebyshev-type grenzen op welke momenten ook bestaan; onafhankelijkheid alleen nodig voor de omgekeerde richting. (3) Deelrij + sandwich: bewijs convergentie langs een hanteerbare deelrij, controleer de oscillatie ertussen door monotonie of maximaliteitsongelijkheden — het skelet van Etemadi’s bewijs. (4) Voor de CLT en concentratie: karakteristieke functies en exponentiële momenten, in het volgende hoofdstuk.

22.6 Oefeningen

Oefening 22.1 ★

(a) Zij $X$ met continue strikt stijgende verdelingsfunctie $F$ . Toon aan dat $F(X)$ uniform is op $\intcc01$ , en dat $G(U) \sim F$ voor $U$ uniform, $G = F^{-1}$ : simulatie door inversie. (b) Bereken de verdelingsfunctie en 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$ (continuïteit en strikte monotonie maken $F$ tot een bijectie op $\intoo01$ met $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$ ): $F(X)$ is uniform. Omgekeerd $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$ : om een wet te simuleren, pas de inverse verdelingsfunctie toe op een uniforme steekproef.

(b) $Y = X^2$ , $X$ uniform op $\intcc{-1}1$ : voor $t \in \intcc01$ , $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 $\mathcal E(\lambda)$ — inversie in actie.

Oefening 22.2 ★

(a) Bereken gemiddelde en variantie van de Poisson $\mathcal P(\lambda)$ en geometrische wetten via de overdrachtsstelling. (b) Toon aan dat een positieve stochastische variabele $T$ met $\P(T > t) > 0$ voor alle $t$ de geheugenloosheids-eigenschap $\P(T > t + s \mid T > t) = \P(T > s)$ voor alle $s, t \geq 0$ vervult dan en slechts dan als $T$ exponentieel is. (De overlevingsfunctie voldoet aan de functionaalvergelijking van Cauchy; monotonie vervangt continuïteit.)

Oplossing

Oplossing van Oefening 22.2.

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

(b) $G(t) = \P(T > t)$ is niet-stijgend met $G \colon \intco0\infty \to \intoc01$ ; geheugenloosheid leest $G(t + s) = G(t)G(s)$ . Dan $G(n t) = G(t)^n$ en $G(t/n) = G(t)^{1/n}$ : $G(q) = G(1)^q$ voor rationale $q \geq 0$ ; schrijf $G(1) = \eu^{-\lambda}$ ( $\in \intoo01$ : $G(1) = 1$ zou $G \equiv 1$ forceren, onmogelijk voor een eindige stochastische variabele; $G(1) = 0$ is uitgesloten door hypothese) en klem een willekeurige $t$ tussen rationalen (monotonie): $G(t) = \eu^{-\lambda t}$ — de exponentiële wet. De omgekeerde is een berekening.

Oefening 22.3 ★★

(a) Toon aan dat als $X_1, \dots, X_n$ onafhankelijk zijn en $f_i$ Borel-functies, de $f_i(X_i)$ onafhankelijk zijn. (b) Toon aan dat gebeurtenissen $A_1, \dots, A_n$ onafhankelijk zijn desda hun complementen dat zijn, desda de indicatoren $\mathbf 1_{A_i}$ onafhankelijke stochastische variabelen zijn. (c) (Paarsgewijs is zwakker) Twee eerlijke munten: $A =$ eerste is kop, $B =$ tweede is kop, $C =$ de twee komen 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$ Borel), en sub- $\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 uitspraken beweren onafhankelijkheid van dezelfde $\sigma$ -algebra’s. (Dat factorisatie over de $A_i$ doorgaat naar complementen is het $\lambda$ -systeemargument binnen de equivalentie van Definitie 22.4 — of directe inclusie-exclusie.)

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

Oefening 22.4 ★★

(a) (Oneindige aap) Een i.i.d. rij van uniforme toetsaanslagen op een eindig alfabet bevat b.z. elke eindige tekst oneindig vaak: bewijs het met Borel–Cantelli (2) op disjuncte blokken. (b) (Runs) Voor i.i.d. fair bits, zij $R_n$ de lengte van de run van enen startend op positie $n$ . Toon aan dat b.z. $R_n \geq (1+\varepsilon)\log_2n$ eindig vaak, en $R_n \geq \log_2 n$ oneindig vaak (beide helften van Borel–Cantelli; voor de tweede, ga naar disjuncte blokken om onafhankelijkheid te winnen): de langste run 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 alfabetgrootte). De gebeurtenissen $E_k = \{$ posities $kL+1, \dots, (k+1)L$ spellen $T\}$ zijn onafhankelijk (disjuncte blokken van i.i.d. letters), elk van kans $q > 0$ : $\sum\P(E_k) = \infty$ , en Borel–Cantelli (2) geeft oneindig veel voorkomens b.z.

(b) Boven: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr) \leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$ , sommeerbaar: door Borel–Cantelli (1), 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$ is puur 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 puur-enen-blokken, d.w.z. $R_{s_j} \geq \log_2 s_j$ oneindig vaak. Samen: de maximale runlengte in de eerste $n$ cijfers is $(1 + o(1))\log_2n$ b.z.

Oefening 22.5 ★★

Zij $(X_n)$ onafhankelijk. (a) Toon aan dat de convergentiestraal van $\sum X_n z^n$ een b.z.-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 controleer dat de nul–één-wet ervoor kan falen.

Oplossing

Oplossing van Oefening 22.5.

(a) $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ is onveranderd als eindig veel $X_n$ gewijzigd worden: voor elke $N$ is $R$ $\sigma(X_N, X_{N+1}, \dots)$ -meetbaar, d.w.z. staartmeetbaar. Dan heeft elke gebeurtenis $\{R \leq c\}$ kans $0$ of $1$ (Stelling 22.9), dus de verdelingsfunctie van $R$ neemt alleen de waarden $0, 1$ : zij springt in een enkel punt $c_0 \in \intcc0{+\infty}$ , en $R = c_0$ b.z.

(b) Convergentie van $\sum X_n$ en van $\frac{S_n}n$ zijn ongevoelig voor wijziging van eindig veel termen (voor de tweede: de gewijzigde termen dragen $O(1/n) \to 0$ bij): staartgebeurtenissen; nul–één-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 contradictie, het is geen staartgebeurtenis.

Oefening 22.6 ★★

Op $(\intcc01, \lambda)$ , exhibeer — met bewijzen — stochastische variabelen 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 $L^p$ ; (c) $X_n \to 0$ in $L^1$ maar niet in $L^2$ ; (d) en toon aan: als $X_n \to X$ in kans en $\abs{X_n} \leq Y \in L^1$ , dan $X_n \to X$ in $L^1$ (deelrijen + gedomineerde convergentie + de sub-subrij-truc).

Oplossing

Oplossing van Oefening 22.6.

Werk op $(\intcc01, \lambda)$ . (a) De typemachine $\mathbf 1_{I_n}$ (Oefening 12.3): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (alle $p < \infty$ ), dus ook in kans; in elk $\omega$ keren $0$ en $1$ beide 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$ , $\E X_n^2 = 1$ . (d) Uit elke deelrij extraheer (convergentie in kans) een verdere deelrij die b.z. convergeert (Propositie 22.11(c)); gedomineerde convergentie geeft $L^1$ -convergentie langs die, met dezelfde limiet $X$ . Dus elke deelrij van de numerieke rij $\E\abs{X_n - X}$ heeft een subdeelrij die naar $0$ gaat: de hele rij gaat naar $0$ .

Oefening 22.7 ★★

Een opiniepeiling schat een onbekende proportie $p$ door de empirische frequentie $\hat p_n$ over $n$ i.i.d. trekkingen. (a) Chebyshev: toon aan $\P(\abs{\hat p_n - p} \geq \varepsilon) \leq \frac1{4n\varepsilon^2}$ . (b) Hoeveel trekkingen garanderen een fout $\leq 3\%$ met kans $\geq 95\%$ door deze grens? (Het ware antwoord, via Hoofdstuk 23, is ongeveer $1070$ : Chebyshev is eerlijk maar ruw.)

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 op $\frac1{4n(0{,}03)^2} \leq 0{,}05$ : $n \geq \frac{1}{4\cdot0{,}0009\cdot0{,}05} \approx 5556$ . De centrale limietstelling zal $n \approx 1070$ voor dezelfde garantie rechtvaardigen: Chebyshev betaalt voor haar algemeenheid met een factor $\approx 5$ .

Oefening 22.8 ★★★

(Bernstein) Voor $f \in \mathcal C(\intcc01)$ definieer de Bernstein-polynomen $B_n(f)(x) = \sum_{k=0}^n f(\frac k n)\binom nk x^k(1-x)^{n-k}$ . (a) Interpreteer $B_n(f)(x) = \E[f(S_n/n)]$ voor $S_n \sim \mathcal B(n,x)$ . (b) Toon aan $B_n(f) \to f$ uniform op $\intcc01$ door te splitsen op $\{\abs{\frac{S_n}n - x} \leq \delta\}$ en haar complement, met uniforme continuïteit en Chebyshev met de binomiale variantie. (c) Concludeer: een tweede, probabilistisch bewijs van de stelling van Weierstrass (Gevolg 7.16), met de expliciete snelheid $O(\omega_f(n^{-1/2}))$ voor de continuïteitsmodulus $\omega_f$ — bewijs minstens de $O(\omega_f(n^{-1/2}))$ -vorm.

Oplossing

Oplossing van Oefening 22.8.

(a) Als $S_n \sim \mathcal B(n, x)$ , geeft de overdrachtsstelling $\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 te ketenen). Dan, voor elke $\delta > 0$ ,

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

(als $\abs{u - x} \leq \delta$ , duidelijk; anders $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta) \omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2}) \omega(\delta)$ ). Neem verwachtingen 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): een probabilistische stelling van Weierstrass, met een expliciete en uniforme ratio.

Oefening 22.9 ★★★

(Coupon collector) Kaarten van $n$ types worden uniform getrokken met teruglegging; zij $T_n$ het aantal trekkingen tot alle types gezien zijn. (a) Schrijf $T_n = \sum_{k=1}^{n}\tau_k$ met $\tau_k$ geometrisch van parameter $\frac{n - k + 1}n$ , de $\tau_k$ onafhankelijk, en leid af $\E T_n = n\,H_n \sim n\ln n$ ( $H_n$ het harmonische getal) en $\V(T_n) \leq \frac{\pi^2}6 n^2$ . (b) Chebyshev: $\P(T_n > (1+\varepsilon)n\ln n) \to 0$ . (c) Verfijn met Borel–Cantelli: toon rechtstreeks $\P(T_n > \beta n\ln n) \leq n^{1-\beta}$ voor $\beta > 1$ , en leid af dat langs $n = 2^m$ , b.z. $T_n \leq \beta n\ln n$ uiteindelijk, voor elke $\beta > 2$ .

Oplossing

Oplossing van Oefening 22.9.

(a) Nadat $k - 1$ types verzameld zijn, is elke trekking nieuw met kans $p_k = \frac{n-k+1}n$ : $\tau_k$ is geometrisch $(p_k)$ , en de $\tau_k$ zijn onafhankelijk (de trekkingen zijn dat). Sommen: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$ ; $\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$ : $\frac{T_n}{n\ln n} \to 1$ in kans.

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

Oefening 22.10 ★★

Met de cijferconstructie van Stelling 22.6: (a) verifieer door rechtstreekse berekening dat $U = \sum b_{2k}2^{-k}$ (even-geïndexeerde cijfers van een uniforme $\omega$ ) uniform is en onafhankelijk van $V = \sum b_{2k-1}2^{-k}$ ; (b) generaliseer: één uniform stochastisch getal bevat twee (en aftelbaar veel) onafhankelijke — vergelijk met de Peano-kromme (Probleem 6.1), die surjectiviteit bereikte maar geen maatbewaring of injectiviteit.

Oplossing

Oplossing van Oefening 22.10.

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

(b) $\Phi(\omega) = (U(\omega), V(\omega))$ is meetbaar met $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (overeenkomst op dyadische rechthoeken + uniciteit). Interleaving van cijfers definieert een inverse buiten de (null) verzameling van dyadische rationalen in een van de factoren: een maatbewarende bijectie tussen volle-maat-deelverzamelingen van $\intcc01$ en $\intcc01^2$ . Contrast met Peano (Probleem 6.1): continuïteit dwong surjectiviteit zonder injectiviteit; continuïteit laten vallen voor loutere meetbaarheid koopt een maatisomorfisme — dimensie is onzichtbaar voor maattheorie, zichtbaar voor topologie.

Oefening 22.11 ★★

(Records) Zij $(X_n)_{n\geq1}$ i.i.d. met continue verdelingsfunctie, en zeg dat een record optreedt op tijd $n$ als $X_n > \max(X_1, \dots, X_{n-1})$ (tijd $1$ is een record). Zij $R_n$ de recordindicator. (a) Toon aan $\P(R_n = 1) = \frac1n$ (door symmetrie is elk van de $n!$ ordeningen van $X_1, \dots, X_n$ even waarschijnlijk en banden hebben kans $0$ ). (b) Toon aan dat de $R_n$ onafhankelijk zijn (tel ordeningen verenigbaar met voorgeschreven recordposities, of argumenteer dat de relatieve volgorde van $X_1, \dots, X_{n-1}$ onafhankelijk is van de rang van $X_n$ onder hen). (c) Leid af uit Borel–Cantelli (Stelling 22.8, beide helften) dat oneindig veel records b.z. optreden, en dat twee opeenvolgende tijden $n, n+1$ oneindig vaak optreden met kans — beslis welke! — en bereken $\E[\sum_{n\leq N}R_n] \sim \ln N$ .

Oplossing

Oplossing van Oefening 22.11.

(a) Continuïteit van de verdeling maakt gelijke waarden null-gebeurtenissen (zoals in de orde-statistiekargumenten van het hoofdstuk), en de $n!$ relatieve ordeningen van $(X_1, \dots, X_n)$ zijn uitwisselbaar, dus even waarschijnlijk. $R_n = 1$ betekent dat het maximum in de laatste positie zit: kans $\frac{(n-1)!}{n!} = \frac1n$ .

(b) Fixeer $n$ en conditioneer op de relatieve ordening van $X_1, \dots, X_{n-1}$ : $X_n$ invoegen in de $n$ mogelijke rangslots is uniform en onafhankelijk van die ordening (uitwisselbaarheid van de $n$ -tupel). Dus $R_n$ (de gebeurtenis “ $X_n$ neemt de toppositie”) is onafhankelijk van de hele recordgeschiedenis $(R_1, \dots, R_{n-1})$ , die een functie is van de relatieve ordening van de eerste $n - 1$ variabelen. Inductie geeft volledige onafhankelijkheid met $\P(R_n = 1) = \frac1n$ .

(c) $\sum\P(R_n = 1) = \sum\frac1n = \infty$ met onafhankelijkheid: de tweede Borel–Cantelli-helft geeft records oneindig vaak b.z. (records stoppen nooit — maar zij dunnen logaritmisch uit: $\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 Borel–Cantelli-helft past toe — slechts eindig veel opeenvolgende-recordparen treden op, b.z.

Oefening 22.12 ★★

(Langste kop-run) Gooi oneindig vaak met een eerlijke munt, en zij $L_n$ de lengte van de langste run van opeenvolgende koppen binnen de eerste $n$ worpen. (a) Toon aan dat voor elke $\varepsilon > 0$ , b.z. $L_n \leq (1 + \varepsilon)\log_2n$ uiteindelijk (de kans dat enige run van lengte $\ell$ start onder de eerste $n$ worpen is hoogstens $n2^{-\ell}$ ; Borel–Cantelli langs $n = 2^m$ ). (b) Toon aan dat b.z. $L_n \geq (1 - \varepsilon)\log_2n$ uiteindelijk (knip de eerste $n$ worpen in disjuncte blokken van lengte $\ell$ ; de blokken zijn onafhankelijk, elk louter-kop met kans $2^{-\ell}$ , en de kans dat geen louter-kop is is hoogstens $(1-2^{-\ell})^{n/\ell}$ ). Moraal: in $10^6$ eerlijke worpen verwacht men een run van ongeveer $20$ koppen — en een dataset zonder is waarschijnlijk gefabriceerd.

Oplossing

Oplossing van Oefening 22.12.

(a) Een run van lengte $\ell$ beginnend in positie $i \leq n$ heeft kans $2^{-\ell}$ ; uniegrens: $\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$ : $\sum_k2^{-k\varepsilon} < \infty$ , dus b.z. $L_{2^k} < (1+\varepsilon)k$ uiteindelijk (Borel–Cantelli); voor algemene $n$ kies $2^{k-1} < n \leq 2^k$ en gebruik 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 opgenomen door $\varepsilon$ iets te vergroten.

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

\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 $n$ groot. Deze kansen zijn sommeerbaar langs $n = 2^k$ (inderdaad langs alle $n$ ): Borel–Cantelli geeft b.z. $L_n \geq (1 - \varepsilon)\log_2n$ uiteindelijk (monotonie vult tussen de $2^k$ zoals in (a), onschuldig).

(c) Beide grenzen langs een rij $\varepsilon = \frac1j$ , doorsnede van aftelbaar veel volle-maat-gebeurtenissen: $\frac{L_n}{\log_2n} \to 1$ b.z. Voor $n = 10^6$ : $\log_2n \approx 19{,}9$ — een run van $\approx 20$ kop is geen verdachte anomalie maar een wiskundige zekerheid, en haar afwezigheid is bewijs dat een mens “toeval” faket (mensen durven zelden meer dan $5$ of $6$ kop achter elkaar te schrijven).

22.7 Probleem: Etemadi’s bewijs van de sterke wet

Probleem 22.1

Weekendprobleem — de sterke wet van de grote aantallen voor i.i.d. integreerbare variabelen

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 lange tijd alleen ingewikkelde bewijzen; in 1981 vond N. Etemadi er één van treffende zuinigheid, die niets voorbij dit hoofdstuk gebruikt (en zelfs onafhankelijkheid verzwakt tot paarsgewijze onafhankelijkheid). We volgen haar. Zij $(X_n)$ paarsgewijs onafhankelijk, identiek verdeeld, integreerbaar; $m = \E X_1$ , $S_n = X_1 + \dots + X_n$ .

Deel I — Reducties.

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

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

Deel II — De variantieschatting.

Toon aan

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

en, met de lagenkoek (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 verwachting — Tonelli voor reeksen — en schat $\sum_{n \geq x}\frac1{n^2} \leq \frac2{\max(x,1)}$ voor de inwendige schatting $x^2\sum_{n\geq x}n^{-2} \leq 2x$ ).

Deel III — Convergentie langs meetkundige subrijen. Fixeer $\alpha > 1$ en laat $k_j = \lfloor\alpha^j\rfloor$ .

Met paarsgewijze onafhankelijkheid (varianties tellen op, Stelling 22.5 — controleer dat additiviteit van varianties alleen paarsgewijze onafhankelijkheid nodig heeft) en Chebyshev, toon aan 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 $\sum_{j : k_j \geq n}k_j^{-2} \leq \frac{C_\alpha}{n^2}$ (meetkundige reeks; let op de floor: $k_j \geq \frac{\alpha^j}2$ voor $\alpha^j \geq 2$ -type zorg), en concludeer 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{dus}\qquad \frac{S^*_{k_j}}{k_j} \to m \ \text{b.z.}$

Deel IV — Sandwich en conclusie.

Voor $k_j \leq n \leq k_{j+1}$ , gebruik de monotonie van $S^*_n$ (niet-negatieve summanden!) om te tonen

$\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 af, b.z.:

$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq \limsup\frac{S^*_n}n \leq \alpha\,m .$
Laat $\alpha \downarrow 1$ langs een rij en concludeer $\frac{S_n^*}n \to m$ b.z., 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 was paarsgewijze onafhankelijkheid (eerder dan volledige onafhankelijkheid) voldoende? Lijst de drie plaatsen waar onafhankelijkheid-type hypothesen werden aangeroepen.

Deel V — Dividenden.

(Normale getallen van Borel) Toon aan dat $\lambda$ -bijna elke $x \in \intcc01$ normaal in elke basis $b \geq 2$ is: elk cijfer $0, \dots, b-1$ verschijnt met asymptotische frequentie $\frac1b$ (fixeer $b$ en een cijfer, pas de sterke wet toe op de indicatorvariabelen — rechtvaardig dat basis- $b$ -cijfers van een uniforme variabele i.i.d. uniform op $\{0,\dots,b-1\}$ zijn zoals in Stelling 22.6 — doorsnijd dan de aftelbaar veel kans- $1$ - gebeurtenissen). Exhibeer één expliciet niet-normaal getal, en reflecteer: de stelling beweert normaliteit van bijna alle getallen, maar normaliteit van $\sqrt2$ of $\pi$ bewijzen blijft open.
(Monte Carlo, gegarandeerd) Rechtvaardig volledig de methode van Voorbeeld 22.14(b) voor $g \in L^1(\intcc01^d)$ : construeer de i.i.d. uniforme steekproef op $\intcc01^d$ uit Stelling 22.6 en Oefening 22.10, en zeg wat de sterke wet levert.

Deel VI — Wat volledige onafhankelijkheid koopt: maximaliteitsongelijkheden en stochastische reeksen. Etemadi besteedt alleen paarsgewijze onafhankelijkheid; de resterende delen benutten de volle (wederzijdse) versie. Zij $(Z_n)$ onafhankelijke gecentreerde variabelen van $L^2$ en $S_k = Z_1 + \dots + Z_k$ (een verse notatie, ongerelateerd aan de $X_n$ hierboven).

(Maximaliteitsongelijkheid van Kolmogorov) Voor $\varepsilon > 0$ bewijs

$\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 (partitioneer de gebeurtenis naar de eerste index $k$ met $\abs{S_k} \geq \varepsilon$ ; op dat stuk schrijf $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 meer zou volstaan.
(Eén-reeks-stelling van Khinchin–Kolmogorov) Leid af: als $\sum_n\V(Z_n) < \infty$ , dan convergeert $\sum_nZ_n$ bijna zeker (toon aan dat b.z. de partiële sommen een Cauchy-rij vormen: laat $m \to \infty$ in de maximaliteitsongelijkheid toegepast op $Z_{N+1}, \dots, Z_{N+m}$ , laat dan $N \to \infty$ ).
(Rademacher-reeksen) Zij $(\varepsilon_n)$ i.i.d. tekens, $\P(\varepsilon_n = \pm1) = \frac12$ (Stelling 22.6), en zij $(x_n)$ reële getallen. Toon aan dat $\sum_nx_n\varepsilon_n$ b.z. convergeert zodra $\sum_nx_n^2 < \infty$ ; toon ook dat, wat $(x_n)$ ook is, de kans dat $\sum_nx_n\varepsilon_n$ convergeert $0$ of $1$ is (Stelling 22.9).
Het omgekeerde, elementair. Stel $T_n = \sum_{k\leq n}x_k\varepsilon_k$ en $s_n^2 = \sum_{k\leq n}x_k^2$ , en veronderstel $s_n \to \infty$ . (a) Bewijs de ongelijkheid van Paley–Zygmund: voor $Z \geq 0$ met $\E Z^2 < \infty$ en $0 < \theta < 1$ ,

$\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 $\E T_n^4 \leq 3s_n^4$ . (c) Leid af $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr) \geq \frac3{16}$ en concludeer dat $\sum_nx_n\varepsilon_n$ b.z. divergeert; dus de dichotomie

$\sum_nx_n\varepsilon_n\ \text{convergeert b.z.} \iff \sum_nx_n^2 < \infty .$
(Stochastische harmonische reeks) Concludeer 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$ : stochastische tekens produceren vierkantswortel-sterke opheffing — vergelijk met de alternerende reeks $\sum_n\frac{(-1)^n}{n^s}$ , die convergeert voor elke $s > 0$ .

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

(Lemma van Hoeffding) (a) Toon aan $\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$ , $a < b$ . Toon aan

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

(schat $\eu^{\lambda z}$ op $\intcc ab$ door haar koorde, neem verwachtingen, en bestudeer $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ met $p = \frac{-a}{b-a}$ en $t = \lambda(b - a)$ : toon aan $\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: schat $\E\,\eu^{\lambda(S_n - \E S_n)}$ met onafhankelijkheid en vraag 17, optimaliseer dan 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

$\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 herwin $\frac{S_n}n \to m$ b.z. door Borel–Cantelli: een tweede bewijs van de sterke wet voor begrensde variabelen — geen knippen, een exponentiële snelheid bij elke eindige $n$ , maar begrensde summanden en volle onafhankelijkheid. Vergelijk de hypothesen met die van Etemadi.
(Monte Carlo, gegarandeerd bij vaste $n$ ) Zij $g \colon \intcc01^d \to \intcc01$ meetbaar en $(U_k)$ de i.i.d. uniforme steekproef van vraag 11. Gegeven $\varepsilon, \delta > 0$ , toon aan

$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 betrekt $d$ niet: vergelijk met vraag 11 en met deterministische roosters.

Deel VIII — Hoe groot is een random walk? Naar de geïtereerde logaritme. Zij $S_n = \varepsilon_1 + \dots + \varepsilon_n$ de eenvoudige random walk gebouwd uit i.i.d. fair tekens.

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

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

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

(voor $\eta > 0$ , sommeer de staartgrenzen in $x = (1 + \eta)\sqrt{2n\log n}$ , doorsnijd dan over $\eta = \frac1p$ ). In het bijzonder leeft de walk op de CLT-schaal $\sqrt n$ tot op een logaritmische factor — ver onder de ruwe grens $\abs{S_n} \leq n$ .
Langs de verdubbelings-subrij $n_j = 2^j$ , toon aan

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

en reflecteer: de wet van de geïtereerde logaritme (Khinchin; Hartman–Wintner voor algemene gecentreerde $L^2$ -summanden) stelt dat

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

Leg precies uit wat de subrij-schatting zojuist bewezen scheidt van de bovenste helft van deze uitspraak (men moet $\max_{n_j \leq n \leq n_{j+1}}S_n$ binnen elk blok controleren, wat een maximaliteitsongelijkheid op de exponentiële schaal vereist) en controleer kwantitatief dat de ongelijkheid van vraag 12 te zwak is voor dat doel. De onderste helft steunt op het tweede Borel–Cantelli-lemma toegepast op onafhankelijke blokken; beide helften zijn eerlijk Jaar 3-materiaal voor een dedicated kansrekening-cursus.
(Uniforme afwijking over een eindige klasse) Zij $A_1, \dots, A_N$ gebeurtenissen in een herhaalbaar experiment, en schat elke kans door haar empirische frequentie $\hat p_i$ over $n$ i.i.d. herhalingen. Combinerend de ongelijkheid van Hoeffding met een uniegrens, toon aan

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

en leid de steekproefgrootte-regel af: $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ garandeert alle $N$ schattingen tegelijk $\varepsilon$ -accuraat met kans $\geq 1 - \delta$ . Bereken $n$ voor $N = 10^6$ , $\varepsilon = 0.01$ , $\delta = 0.05$ : de logaritmische prijs van uniformiteit.
(Het stochastische harmonische venster) Combinerend de twee helften van de stochastische reeks-theorie, toon 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 absolute convergentie (die $\alpha > 1$ vereist): op het venster $\alpha \in \intoc{\frac12}1$ is convergentie een echt probabilistisch fenomeen — opheffing, niet grootte.

Oplossing

Oplossing van Probleem 22.1.

1. $X_n^{\pm}$ zijn Borelfuncties van $X_n$ : zij blijven paarsgewijs onafhankelijk (Oefening 22.3(a)) en identiek verdeeld, integreerbaar, met $\E X_1 = \E X_1^+ - \E X_1^-$ . Als de stelling voor niet-negatieve variabelen geldt, pas haar 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)$ (identieke wetten), 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. $X_n = Y_n$ voor alle grote $n$ , dus $S_n - S_n^*$ is uiteindelijk constant in $n$ : $\frac{S_n - S_n^*}n \to 0$ b.z., en de twee genormaliseerde sommen delen hun asymptotisch gedrag.

3. $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$ : MCT geeft $\E Y_n \to m$ ; Cesàro-gemiddelden van een convergente rij convergeren naar dezelfde limiet: $\frac{\E S_n^*}n = \frac1n\sum_{k\leq n}\E Y_k \to m$ . Dus volstaat te bewijzen $\frac{S^*_n - \E S^*_n}{n} \to 0$ b.z.

4. $\V(Y_n) \leq \E Y_n^2 = \E[X_1^2\mathbf 1_{X_1\leq n}]$ . Door 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. Paarsgewijze onafhankelijkheid geeft $\E[(Y_i - \E Y_i)(Y_j - \E Y_j)] = 0$ voor $i \neq j$ (de productformule voor twee variabelen), dus varianties optellen: $\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$ , d.w.z. alle $j \geq 0$ : $\lfloor x\rfloor \geq \frac x2$ voor $x \geq 1$ ). Dus

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

(geometrische reeks vanaf de eerste $j$ met $\alpha^j \geq n$ ). Combinerend met vragen 4–5 is de dubbele som eindig; Borel–Cantelli (1), toegepast voor elke rationale $\varepsilon$ 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}$ ,

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

wat de getoonde sandwich is na invoegen van $\frac{k_j}{k_{j+1}}$ en $\frac{k_{j+1}}{k_j}$ . 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$ , $p \in \N^*$ : aftelbaar veel b.z.-gebeurtenissen; op hun doorsnede, $p \to \infty$ : $\lim\frac{S^*_n}n = m$ b.z. Met vragen 1–3, $\frac{S_n}n \to \E X_1$ b.z.: de sterke wet van de grote aantallen, onder paarsgewijze onafhankelijkheid.

9. Onafhankelijkheid-achtige hypotheses verschenen driemaal: (i) optelbaarheid van varianties (vraag 5) — paarsgewijs volstaat; (ii) identieke verdeling, in de afkappingsommen (vraag 2) en de gemiddeldeberekening (vraag 3) — helemaal geen onafhankelijkheid; (iii) Borel–Cantelli (1) (vragen 2 en 6) — geldig zonder enige onafhankelijkheid. Volledige wederzijdse onafhankelijkheid werd nooit ingeroepen: de observatie van Etemadi.

10. Fixeer een grondtal $b$ en een cijfer $r$ . De grondtal- $b$ -cijfers $(d_k)$ van een uniforme $\omega$ zijn i.i.d. uniform op $\{0, \dots, b-1\}$ (elke cijfervectorwaarde beslaat een interval van lengte $b^{-m}$ : het argument van Stelling 22.6 letterlijk). De sterke wet toegepast op de i.i.d. begrensde variabelen $\mathbf 1_{d_k = r}$ geeft: b.z. neigt de frequentie van cijfer $r$ naar $\frac1b$ . Doorsnede over de aftelbaar veel paren $(b, r)$ : bijna elk getal is eenvoudig normaal in elk grondtal. Een expliciet niet-normaal getal: $x = 0{,}100100100\ldots_2$ (frequentie van enen $\frac13 \neq \frac12$ ). Het contrast is vernederend: bijna alle getallen zijn normaal, maar voor $\sqrt2$ , $\eu$ of $\pi$ blijft normaliteit onbewezen — maattheorie telt zonder te tonen.

11. Door Oefening 22.10 geïtereerd levert één uniforme variabele een rij i.i.d. uniforme vectoren $U_k$ op $\intcc01^d$ (splits de cijferverzameling van elke $U_n$ van Stelling 22.6 in $d$ subfamilies). Voor $g \in L^1(\intcc01^d)$ zijn de variabelen $g(U_k)$ i.i.d. 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 :

Monte-Carlo-integratie convergeert bijna zeker, in elke dimensie — de foutgrootte 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 unie $A = \{\max_{k\leq n}\abs{S_k} \geq \varepsilon\}$ . Dan

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

omdat 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$ , $S_k^2 \geq \varepsilon^2$ , vandaar $\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)$ (varianties tellen op). De beslissende stap is de factorisatie: $S_k\mathbf 1_{A_k}$ is een niet-lineaire functie van het hele eerste blok, en haar onafhankelijkheid van het tweede blok is coalitie-onafhankelijkheid — paarsgewijze onafhankelijkheid van de $Z_i$ decorreleert alleen paren en zou het niet rechtvaardigen.

13. Fixeer $N$ 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$ ; 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$ door hypothese. Dus 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, voor elke $p$ is er $N$ met $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (doorsnede van de aftelbaar veel b.z.-gebeurtenissen over $p$ ), zodat $\abs{S_k - S_l} \leq \frac2p$ voor alle $k, l > N$ : de deelsommen zijn b.z. Cauchy, dus b.z. convergent.

14. De variabelen $Z_n = x_n\varepsilon_n$ zijn onafhankelijk (Borelfuncties van onafhankelijke variabelen, Oefening 22.3(a)), gecentreerd, met $\V(Z_n) = x_n^2$ : vraag 13 past toe als $\sum_nx_n^2 < \infty$ en geeft b.z.-convergentie. In het algemeen, voor elke $N$ is de convergentie van $\sum_nx_n\varepsilon_n$ ongevoelig voor de waarden van $\varepsilon_1, \dots, \varepsilon_N$ : de convergentiegebeurtenis ligt in de staart- $\sigma$ -algebra van de onafhankelijke rij $(\varepsilon_n)$ , dus dwingt Kolmogorovs nul–één-wet (Stelling 22.9) haar kans tot $0$ of $1$ .

15. (a) Splitsen op het niveau $\theta\E Z$ en Cauchy–Schwarz op het bovenstuk,

\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 verwachting is $1$ als de indices paarvormig zijn (alle vier gelijk, of twee distincte paren, het laatste in $3$ arrangementen) en $0$ anders (een ongepaard teken heeft nul-gemiddelde en factoriseert door onafhankelijkheid). Dus

\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} .

Als de reeks met positieve kans convergeerde, zou zij b.z. convergeren (vraag 14), dus $\sup_n\abs{T_n} < \infty$ b.z., en zekere $M$ zou $\P(\sup_n\abs{T_n} > M) < \frac3{16}$ voldoen; maar zodra $s_n > 2M$ , $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2) \geq \frac3{16}$ : contradictie. Dus divergentie is bijna zeker, en met vraag 14 is de dichotomie compleet.

16. Hier $x_n = n^{-s}$ en $\sum_nn^{-2s} < \infty$ precies als $s > \frac12$ : door vragen 14–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: perfect alternerende tekens cancelleren op sterkte $n^{-s}$ voor elke $s > 0$ , terwijl typische toevalstekens slechts op vierkantswortelsterkte cancelleren — de random walk van vraag 21 groeit als $\sqrt n$ , en Abel-sommatie zet precies die groei om in 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 termgewijs, want $\frac{(2k)!}{k!} = \prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (elke factor voldoet $k + i \geq 2i$ voor $i \leq k$ ), zodat inderdaad $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$ . (b) Merk op $a \leq 0 \leq b$ ( $Z$ is gecentreerd), en door 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)$ , $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ . Dan $\varphi(0) = 0$ , $\varphi'(t) = -p + \frac{p\eu^t}{1 - p + p\eu^t}$ verdwijnt in $0$ , en $\varphi''(t) = \rho(1 - \rho) \leq \frac14$ voor $\rho = \frac{p\eu^t}{1 - p + p\eu^t} \in \intcc01$ : Taylor van 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 variabele $\eu^{\lambda(S_n - \E S_n)}$ (Propositie 22.3) en de productformule voor onafhankelijke variabelen

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

door vraag 17(b) toegepast op elke gecentreerde $X_i - \E X_i \in \intcc{a_i - \E X_i}{b_i - \E X_i}$ (zelfde breedte). Minimaliseren van de exponent in $\lambda = \frac{4t}{D}$ , $D = \sum_i(b_i - a_i)^2$ , levert $-\frac{2t^2}D$ . De onderstaart volgt door het resultaat toe te passen op $(-X_i)$ .

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 geometrisch-achtige reeks): Borel–Cantelli (Stelling 22.8) geeft dat b.z. $\abs{\frac{S_n}n - m} < \varepsilon$ uiteindelijk; doorsnede over $\varepsilon = \frac1p$ levert $\frac{S_n}n \to m$ b.z. Vergelijking: Etemadi eist alleen $X_1 \in L^1$ en paarsgewijze onafhankelijkheid, en levert geen ratio; Hoeffding eist begrensdheid en volledige onafhankelijkheid, en levert een expliciete exponentiële garantie bij elke eindige $n$ — 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 vraag 18 met $b_i - a_i = 1$ , $t = n\varepsilon$ geeft de tweezijdige grens $2\eu^{-2n\varepsilon^2} \leq \delta$ zodra $\eu^{2n\varepsilon^2} \geq \frac2\delta$ , d.w.z. $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$ samples garanderen $1\%$ nauwkeurigheid met $99\%$ betrouwbaarheid — in elke dimensie $d$ , voor elke meetbare integrand met waarden in $\intcc01$ . De sterke wet van vraag 11 beloofde convergentie zonder eindige- $n$ -garantie; een deterministisch rooster met $k$ punten per as kost $k^d$ evaluaties, exponentieel in $d$ . Concentratie maakt Monte Carlo tot een methode 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}$ door 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$ (zelfde wet) verdubbelt de constante voor $\abs{S_n}$ .

22. Fixeer $\eta > 0$ en zet $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 want $(1 + \eta)^2 > 1$ . Borel–Cantelli: b.z. $\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.; doorsnede van de b.z.-gebeurtenissen voor $\eta = \frac1p$ , $p \in \N^*$ , geeft de bewering. De walk van grootte $n$ heeft typische amplitude $\sqrt n$ (haar variantie), en zelfs haar slechtste 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$ want $(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 ontbreekt voor de volle bovenhelft is de brug tussen checkpoints: men moet tonen dat $\max_{n_j\leq n\leq n_{j+1}}S_n$ de waarde $(1+\eta)\sqrt{2n_j\log\log n_j}$ slechts eindig vaak overschrijdt, wat een maximale ongelijkheid met Gaussische staarten eist (reflectieongelijkheid van Lévy of Ottaviani, hier niet bewezen). Vraag 12 is kwantitatief te zwak: zij 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)},

die naar $0$ gaat maar niet sommeerbaar is in $j$ : Borel–Cantelli kan niet concluderen. De onderhelft van de wet van de geïtereerde logaritme past de tweede Borel–Cantelli-lemma toe op de onafhankelijke increments $S_{n_{j+1}} - S_{n_j}$ , met matchende ondergrenzen voor Gaussisch-achtige staarten. Beide verfijningen zijn echte Jaar-3-kansrekening, één cursus verder; wat dit probleem ongeholpen levert is de exacte geïtereerde-logaritmeschaal langs geometrische tijden.

24. Elke $\hat p_i$ is een gemiddelde van $n$ i.i.d. indicatorvariabelen 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 uniegrens vermenigvuldigt met $N$ . Oplossen $2N\eu^{-2n\varepsilon^2} \leq \delta$ : $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 $\pm1\%$ kost ongeveer $18\,500$ samples ( $\ln(2/\delta)/2\varepsilon^2$ ), en een miljoen kansen slechts $\approx 4{,}7$ maal meer — uniformiteit kost $\ln N$ , niet $N$ : de observatie die empirische-risicominimalisatie, en daarmee machine learning, statistisch mogelijk maakt.

25. De variabelen $X_n = \frac{\varepsilon_n} {n^\alpha}$ zijn onafhankelijk, gecentreerd, begrensd, met $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$ . Als $\alpha > \frac12$ : de variantie-reeks convergeert, en de één-reeks-stelling (Deel VI) geeft b.z.-convergentie van $\sum X_n$ . Als $\alpha \leq \frac12$ : de variantie-reeks divergeert, en de omgekeerde helft (Paley–Zygmund-argument van Deel VI, toepasbaar omdat de termen begrensd zijn door $1$ ) geeft b.z.-divergentie. Absolute convergentie eist $\sum n^{-\alpha} < \infty$ : $\alpha > 1$ . Op $\intoc{\frac12}1$ convergeert de reeks b.z. hoewel $\sum\abs{X_n} = \infty$ zeker: de tekens spannen samen om te cancelleren, met kans één — convergentie door cancellatie, onzichtbaar voor elke absolute test, en (door de nul–één-wet) met een deterministisch vonnis desondanks.