Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

21Waarschijnlijkheid op aftelbare ruimten

De laatste drie hoofdstukken ontwikkelen de kansrekening van het moderne MP*-programma: waarschijnlijkheidsmaten op aftelbare uitkomstenruimten, discrete stochastische variabelen, en genererende functies. De eindige theorie van het middelbareschoolvolume krijgt haar volledige infrastructuur: $\sigma$ -additiviteit vervangt eindige additiviteit, en de machine van sommeerbare families uit Hoofdstuk 7 is precies wat oneindige uitkomstenruimten werkbaar maakt. De centrale resultaten hier zijn de continuïteit van de waarschijnlijkheid langs monotone rijen gebeurtenissen en het lemma van Borel–Cantelli.

21.1 Waarschijnlijkheidsruimten

Definitie 21.1 (Aftelbare waarschijnlijkheidsruimte)

Zij $\Omega$ een niet-lege eindige of aftelbare verzameling (de uitkomstenruimte). Een waarschijnlijkheidsmaat op $\Omega$ is een afbeelding $\P$ van de verzameling $\mathcal{P}(\Omega)$ van alle deelverzamelingen van $\Omega$ (gebeurtenissen) naar $[0, 1]$ zodat:

$\P(\Omega) = 1$ ;
( $\sigma$ -additiviteit) voor elke rij $(A_n)_{n\in\N}$ van paarsgewijs disjuncte gebeurtenissen,

$\P\Bigl(\,\bigcup_{n \in \N} A_n\Bigr) = \sum_{n=0}^{\infty} \P(A_n) .$

Het paar $(\Omega, \P)$ is een (aftelbare) waarschijnlijkheidsruimte.

Opmerking 21.2

Op een aftelbare $\Omega$ mogen we alle deelverzamelingen als gebeurtenissen nemen; op onaftelbare ruimten (nodig voor continue modellen in Bachelor jaar 3) is dat niet meer mogelijk, en beperkt men $\P$ tot een geschikte collectie gebeurtenissen, een $\sigma$ -algebra. Alle formules van dit hoofdstuk overleven die generalisatie letterlijk.

Propositie 21.3 (Elementaire regels)

Voor gebeurtenissen $A, B$ en een waarschijnlijkheidsmaat $\P$ : $\P(\emptyset) = 0$ ; $\P$ is eindig additief; $\P(A^c) = 1 - \P(A)$ ; als $A \subseteq B$ dan $\P(A) \leq \P(B)$ ; en

\P(A \cup B) = \P(A) + \P(B) - \P(A \cap B) .

Bewijs. Toepassing van $\sigma$ -additiviteit op $A_0 = \Omega$ , $A_n = \emptyset$ ( $n \geq 1$ ) geeft $1 = 1 + \sum_{n\geq1}\P(\emptyset)$ , dus $\P(\emptyset) = 0$ ; een eindige disjuncte unie opvullen met lege verzamelingen geeft dan eindige additiviteit. De rest volgt als in het eindige geval (middelbareschoolvolume): $1 = \P(A) + \P(A^c)$ uit $\Omega = A \sqcup A^c$ ; $\P(B) = \P(A) + \P(B \setminus A) \geq \P(A)$ wanneer $A \subseteq B$ ; en door ontbinding in drie disjuncte stukken,

\begin{align*} \P(A \cup B) &= \P(A \setminus B) + \P(B \setminus A) + \P(A \cap B)\\ &= \bigl(\P(A) - \P(A\cap B)\bigr) + \bigl(\P(B) - \P(A\cap B)\bigr) + \P(A \cap B), \end{align*}

wat inclusie–exclusie is; de algemene $n$ -verzamelingenversie is Oefening 21.4. ∎

Propositie 21.4 (Verdelingen op een aftelbare ruimte)

Een waarschijnlijkheidsmaat geven op een aftelbare $\Omega = \{\omega_0, \omega_1, \dots\}$ komt precies neer op gewichten $p_i = \P(\{\omega_i\}) \geq 0$ geven met $\sum_i p_i = 1$ ; dan geldt voor elke $A \subseteq \Omega$ ,

\P(A) = \sum_{\omega \in A} \P(\{\omega\}) ,

een (absoluut convergente) deelsom van de familie $(p_i)$ .

Bewijs. Gegeven $\P$ , vormen de singletonen $\{\omega\}$ , $\omega \in A$ , een aftelbare disjuncte overdekking van $A$ , zodat $\sigma$ -additiviteit dwingt

\P(A) = \sum_{\omega\in A}\P(\{\omega\}),

een onvoorwaardelijke deelsom van de niet-negatieve sommeerbare familie $(p_i)$ — herschikken is onschadelijk precies omdat de termen niet-negatief zijn (Hoofdstuk 7); in het bijzonder $\sum_ip_i = \P(\Omega) = 1$ . Omgekeerd, gegeven niet-negatieve gewichten van totale som $1$ , definieer $\P(A) = \sum_{\omega \in A}p_\omega$ : de familie is sommeerbaar, en $\sigma$ -additiviteit is precies de stelling over sommatie per pakketten uit Hoofdstuk 7 toegepast op de partitie van $\bigcup A_n$ in de $A_n$ . ∎

Voorbeeld 21.5 (Geometrisch model: wachten op de eerste kop)

Gooi herhaaldelijk een munt met kopkans $p \in \intoo{0}{1}$ , en laat $\Omega = \N^* \cup \{\infty\}$ de rang van de eerste kop registreren. De natuurlijke gewichten zijn

\P(\{k\}) = (1 - p)^{k-1}p \quad (k \in \N^*), \qquad \P(\{\infty\}) = 0 ,

een waarschijnlijkheidsmaat omdat $\sum_{k\geq1}(1-p)^{k-1}p = \frac{p}{1 - (1-p)} = 1$ : met waarschijnlijkheid $1$ eindigt het spel — maar de uitkomstenruimte moet toch de mogelijkheid bevatten dat het niet eindigt. Aftelbare additiviteit is wat ons laat stellen $\P(\text{het spel eindigt}) = \sum_k \P(\{k\})$ .

Stelling 21.6 (Monotone continuïteit)

Zij $(A_n)$ een rij gebeurtenissen.

Als $A_n \subseteq A_{n+1}$ voor alle $n$ (stijgend), dan $\P\bigl(\bigcup_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .
Als $A_n \supseteq A_{n+1}$ voor alle $n$ (dalend), dan $\P\bigl(\bigcap_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .

Bewijs. 1. Disjunctificeer: laat $B_0 = A_0$ en $B_n = A_n \setminus A_{n-1}$ . De $B_n$ zijn paarsgewijs disjunct met $\bigcup_{k \leq n} B_k = A_n$ en $\bigcup_n B_n = \bigcup_n A_n$ . Door $\sigma$ -additiviteit en eindige additiviteit,

\P\Bigl(\bigcup_n A_n\Bigr) = \sum_{n=0}^\infty \P(B_n) = \lim_{N\to\infty}\sum_{n=0}^N \P(B_n) = \lim_{N\to\infty}\P(A_N) .

2. Ga over op complementen: $(A_n^c)$ is stijgend met unie $\bigl(\bigcap A_n\bigr)^c$ , en pas deel 1 toe: $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$ . ∎

Gevolg 21.7 (Aftelbare subadditiviteit)

Voor elke rij gebeurtenissen, $\P\bigl(\bigcup_n A_n\bigr) \leq \sum_{n=0}^{\infty} \P(A_n)$ .

Bewijs. Eindige subadditiviteit $\P(A_0 \cup \dots \cup A_N) \leq \sum_0^N \P(A_n)$ volgt uit inclusie–exclusie door inductie (of uit additiviteit over de disjunctificeerde $B_n \subseteq A_n$ ). Laat $N \to \infty$ : de linkerzijde convergeert naar $\P(\bigcup_n A_n)$ door monotone continuïteit toegepast op de stijgende rij $C_N = A_0 \cup \dots \cup A_N$ . ∎

Voorbeeld 21.8 (De unie-ongelijkheid: grof maar onverwoestbaar)

Subadditiviteit met eindig veel gebeurtenissen — de unie-ongelijkheid — ruilt precisie in voor universaliteit. Voor het verjaardagsprobleem met $23$ personen geeft een bovengrens van de botsingskans door de som over paren

\P(\text{botsing}) \leq \binom{23}2\cdot\frac1{365} = \frac{253}{365} \approx 0.693 ,

tegenover de ware $0.507$ : ruim ernaast, omdat botsingen overlappen. Toch heeft de grens geen onafhankelijkheid nodig, geen gezamenlijke wet, niets behalve de paarkansen — daarom is, in het weekendprobleem en doorheen Hoofdstuk 22, de unie-ongelijkheid het eerste instrument dat men trekt: wanneer ze toevallig klein is, is de zaak afgedaan zonder verder modelleren.

Voorbeeld 21.9 (Er komt een zes, uiteindelijk)

Gooi eeuwig een eerlijke dobbelsteen en laat $B_n = {}$ “minstens één zes onder de eerste $n$ worpen”, een stijgende rij gebeurtenissen met $\P(B_n) = 1 - (5/6)^n$ . Monotone continuïteit geeft

\P(\text{uiteindelijk verschijnt een zes}) = \P\Bigl(\bigcup_nB_n\Bigr) = \lim_n\bigl(1 - (5/6)^n\bigr) = 1 .

Het punt is niet de (voor de hand liggende) limiet maar de logische stap: “uiteindelijk” is een gebeurtenis over oneindig veel worpen, buiten het bereik van eindige additiviteit, en monotone continuïteit — dat wil zeggen $\sigma$ -additiviteit — is precies het axioma dat er een waarschijnlijkheid aan toekent. Elke bijna-zekere uitspraak in de rest van dit boek gaat door deze zelfde smalle deur.

21.2 Conditionering en onafhankelijkheid

Definitie 21.10 (Voorwaardelijke waarschijnlijkheid)

Voor gebeurtenissen $A, B$ met $\P(B) > 0$ is de voorwaardelijke waarschijnlijkheid van $A$ gegeven $B$

\P(A \mid B) = \frac{\P(A \cap B)}{\P(B)} .

De afbeelding $A \mapsto \P(A \mid B)$ is zelf een waarschijnlijkheidsmaat op $\Omega$ .

Opmerking 21.11

Dat $A \mapsto \pcond BA$ opnieuw een waarschijnlijkheidsmaat is, verdient een moment: $\pcond B\Omega = 1$ en $\sigma$ -additiviteit gaan door de quotiënt omdat doorsnede met $B$ disjuncte unies respecteert. Het praktische gevolg: elke identiteit van dit hoofdstuk — inclusie–exclusie, monotone continuïteit, Borel–Cantelli — mag na conditionering worden toegepast, zonder nieuwe bewijzen. Probabilisten werken voortdurend “onder $\pcond B{\cdot}$ ” precies om die reden.

Voorbeeld 21.12 (Conditionering kan uniformiteit creëren)

Gooi twee eerlijke dobbelstenen en conditioneer op de som $7$ : voor elke $k \in \intint16$ ,

\pcond{\{S = 7\}}{X = k} = \frac{\P(X = k,\ Y = 7 - k)}{\P(S = 7)} = \frac{1/36}{6/36} = \frac16 :

gegeven som $7$ is de eerste steen precies uniform — $7$ is het enige totaal dat met elk vlak compatibel is, zodat de conditionering alle informatie over $X$ wist. Elk ander totaal vertekent de wet (gegeven $S = 4$ is de eerste steen uniform op $\{1, 2, 3\}$ alleen). Een voorwaardelijke wet berekenen betekent de gezamenlijke gewichten renormaliseren langs de conditioneringsgebeurtenis, niets meer.

Voorbeeld 21.13 (De tweede trekking is even goed als de eerste)

Een urn bevat $3$ witte en $2$ zwarte ballen; trek er twee zonder teruglegging. Iedereen is het eens dat $\P(W_1) = \frac35$ ; wat is $\P(W_2)$ ? Totale waarschijnlijkheid langs de eerste trekking:

\P(W_2) = \pcond{W_1}{W_2}\,\P(W_1) + \pcond{B_1}{W_2}\,\P(B_1) = \frac24\cdot\frac35 + \frac34\cdot\frac25 = \frac{12}{20} = \frac35 :

precies $\P(W_1)$ . Er was geen berekening nodig: door symmetrie is elke bal even waarschijnlijk de tweede getrokken, zodat de tweede trekking — onvoorwaardelijk — dezelfde wet heeft als de eerste. Conditioneren op het eerste resultaat verandert de kansen; het niet kennen ervan doet dat niet. Dit uitwisselbaarheidsargument keert terug in het volgende hoofdstuk bij steekproeftrekking zonder teruglegging, waar het het hypergeometrische gemiddelde $np$ geeft zonder enige binomiale identiteiten.

Stelling 21.14 (Samengestelde kansen, totale waarschijnlijkheid, Bayes)

(Kettingregel) Als $\P(A_1 \cap \dots \cap A_{n-1}) > 0$ ,

$\P(A_1 \cap \dots \cap A_n) = \P(A_1)\,\P(A_2 \mid A_1)\cdots \P(A_n \mid A_1 \cap \dots \cap A_{n-1}) .$
(Totale waarschijnlijkheid) Als $(B_i)_{i \in I}$ een eindige of aftelbare partitie van $\Omega$ is met $\P(B_i) > 0$ , dan voor elke gebeurtenis $A$ :

$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$
(Bayes) Onder dezelfde hypothesen, als bovendien $\P(A) > 0$ :

$\P(B_j \mid A) = \frac{\P(A \mid B_j)\,\P(B_j)} {\sum_{i \in I} \P(A \mid B_i)\,\P(B_i)} .$

Bewijs. 1. Schrijf elke voorwaardelijke waarschijnlijkheid als quotiënt: de rechterzijde is

\P(A_1)\cdot\frac{\P(A_1 \cap A_2)}{\P(A_1)}\cdot \frac{\P(A_1 \cap A_2 \cap A_3)}{\P(A_1 \cap A_2)}\cdots \frac{\P(A_1 \cap \dots \cap A_n)}{\P(A_1 \cap \dots \cap A_{n-1})},

een telescoperend product: elke noemer heft de vorige teller op en laat $\P(A_1 \cap \dots \cap A_n)$ over. Alle noemers zijn $\geq \P(A_1 \cap \dots \cap A_{n-1}) > 0$ door monotoniciteit, dus niets verdwijnt. (De hypothese bewaakt precies dit: conditioneren op een gebeurtenis van waarschijnlijkheid nul is ongedefinieerd.) 2. De verzamelingen $A \cap B_i$ zijn paarsgewijs disjunct met unie $A$ ; pas ( $\sigma$ -)additiviteit en de definitie van conditionering toe. 3. Beide zijden van $\P(B_j \mid A)\P(A) = \P(A \mid B_j)\P(B_j)$ zijn gelijk aan $\P(A \cap B_j)$ ; deel door $\P(A)$ en ontwikkel $\P(A)$ via totale waarschijnlijkheid. ∎

Voorbeeld 21.15 (De verjaardagsbotsing, via de kettingregel)

Met $n$ personen wier verjaardagen onafhankelijk en uniform over $365$ dagen zijn, laat $D_n = {}$ “alle $n$ verjaardagen verschillen”. Conditioneer persoon per persoon (kettingregel):

\P(D_n) = \prod_{k=1}^{n-1}\Bigl(1 - \frac{k}{365}\Bigr),

elke nieuwe persoon moet de $k$ al ingenomen dagen vermijden. Voor $n = 23$ : $\P(D_{23}) \approx 0.493$ — een gedeelde verjaardag is al waarschijnlijker dan niet. De heuristiek die de kleinheid van $23$ verklaart: logaritmen nemend, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$ , en $\binom{23}2 = 253$ geeft $253/365 \approx 0.693 \approx \ln 2$ . Wat telt is het aantal paren, dat kwadratisch groeit: botsingsproblemen leven op de schaal $n \sim \sqrt{365}$ , niet $n \sim 365$ — de verjaardagsparadox is een vierkantswortel in vermomming.

Voorbeeld 21.16 (Monty Hall, via Bayes)

Een prijs zit achter één van drie deuren, uniform. U kiest deur $1$ ; de presentator, die weet waar de prijs is, opent één van de andere deuren, altijd leeg (kiest uniform wanneer hij de keuze heeft), zeg deur $3$ . Laat $B_i = {}$ “prijs achter deur $i$ ” en $A = {}$ “presentator opent deur $3$ ”. Dan $\pcond{B_1}{A} = \frac12$ , $\pcond{B_2}{A} = 1$ , $\pcond{B_3}{A} = 0$ , dus door Bayes (Stelling 21.14),

\P(B_2 \mid A) = \frac{1\cdot\frac13} {\frac12\cdot\frac13 + 1\cdot\frac13 + 0\cdot\frac13} = \frac23 :

wisselen van deur wint twee van de drie keer. De berekening lokaliseert de populaire verwarring precies: de zet van de presentator is informatief (hij kon deur $2$ niet openen als de prijs daar zat), en de formule van Bayes is het boekhoudkundig hulpmiddel dat deze asymmetrie omzet in de $\frac23$ . Conditioneren op “wat men zag” in plaats van op “wat waar is” is de hele kunst van de formule.

Voorbeeld 21.17 (De twee weddenschappen van de Chevalier de Méré)

Twee zeventiende-eeuwse weddenschappen, beslecht door onafhankelijkheid. Weddenschap één: minstens één zes in $4$ worpen met een dobbelsteen,

\P = 1 - \Bigl(\frac56\Bigr)^{\!4} \approx 0.518 > \frac12 .

Weddenschap twee: minstens één dubbel-zes in $24$ worpen met twee dobbelstenen,

\P = 1 - \Bigl(\frac{35}{36}\Bigr)^{\!24} \approx 0.491 < \frac12 .

De Méré redeneerde dat $24$ worpen met kans $\frac1{36}$ moesten overeenkomen met $4$ worpen met kans $\frac16$ (zelfde verhouding $\frac{24}{36} = \frac46$ ); het falen van deze proportionaliteit — kansen van unies schalen niet lineair — zou zijn brief aan Pascal hebben uitgelokt, en daarmee de geboorte van de kansrekening. De juiste vergelijking loopt via logaritmen: $n$ proeven met kans $p$ slagen minstens één keer met waarschijnlijkheid $1 - (1-p)^n \approx 1 - \eu^{-np}$ , zodat de eerlijke invariant $np$ is: hier $4\cdot\frac16 = \frac23$ versus $24\cdot\frac1{36} = \frac23$ — gelijk! De twee weddenschappen verschillen alleen in de tweede orde in $p$ , en net genoeg om er één over de vijftigprocentlijn te duwen: kleine kansen zijn een domein waar intuïtie de exponentiële nodig heeft, niet de liniaal.

Opmerking 21.18 (Gangbare drogredenen van conditionering)

Drie terugkerende verwarringen, alle zichtbaar in de voorbeelden hierboven. (i) Omkering: $\pcond BA$ en $\pcond AB$ verschillen met de factor $\P(A)/\P(B)$ — een test die $99\%$ accuraat is op de zieken kan een positieve patiënt toch bijna zeker gezond laten wanneer de ziekte zeldzaam is (Oefening 21.3); $\pcond{\text{ziek}}{ \text{positief}}$ citeren waar $\pcond{\text{positief}}{ \text{ziek}}$ bedoeld is, is de basispercentage-drogreden. (ii) Conditioneren op de verkeerde gebeurtenis: bij Monty Hall is de correcte conditioneringsgebeurtenis “de presentator opende deur $3$ ”, niet “de prijs zit niet achter deur $3$ ”; de twee dragen verschillende informatie, en de hele $\frac23$ hangt af van dat verschil. (iii) Disjunct versus onafhankelijk: disjuncte gebeurtenissen van positieve waarschijnlijkheid zijn nooit onafhankelijk ( $\P(A\cap B) = 0 \neq \P(A)\P(B)$ ) — onafhankelijkheid is compatibiliteit van informatie, niet afwezigheid van overlapping.

Definitie 21.19 (Onafhankelijkheid)

Gebeurtenissen $A$ en $B$ zijn onafhankelijk als $\P(A \cap B) = \P(A)\P(B)$ . Een familie $(A_i)_{i \in I}$ van gebeurtenissen is (wederzijds) onafhankelijk als voor elke eindige deelverzameling $J \subseteq I$ ,

\P\Bigl(\bigcap_{i \in J} A_i\Bigr) = \prod_{i \in J} \P(A_i) .

Opmerking 21.20

Wederzijdse onafhankelijkheid is strikt sterker dan paarsgewijze onafhankelijkheid: bij twee eerlijke muntworpen zijn de gebeurtenissen “eerste is kop”, “tweede is kop”, “beide stemmen overeen” paarsgewijs onafhankelijk (elk paar heeft doorsnedekans $\frac14 = \frac12\cdot\frac12$ ), maar de driedubbele doorsnede heeft waarschijnlijkheid $\frac14 \neq \frac18$ . Merk ook op dat als $A, B$ onafhankelijk zijn, dat ook $A, B^c$ zijn (bereken: $\P(A \cap B^c) = \P(A) - \P(A\cap B) = \P(A)(1 - \P(B))$ ), en dus ook $A^c, B^c$ .

Voorbeeld 21.21 (Onafhankelijkheid afgelezen van een productstructuur)

Gooi twee eerlijke dobbelstenen: $\Omega = \intint16^2$ met uniforme gewichten. Laat $A = {}$ “eerste steen even” en $B = {}$ “tweede steen minstens $5$ ”. Tellen: $\abs A = 3\cdot6 = 18$ , $\abs B = 6\cdot2 = 12$ , $\abs{A\cap B} = 3\cdot2 = 6$ , dus

\P(A\cap B) = \frac6{36} = \frac{18}{36}\cdot\frac{12}{36} = \P(A)\,\P(B) :

onafhankelijk, en het mechanisme is zichtbaar — $A$ beperkt alleen de eerste coördinaat, $B$ alleen de tweede, en de uniforme maat op een productverzameling laat coördinaattellingen vermenigvuldigen. Elke bewering van het type “gebeurtenissen die afhangen van disjuncte groepen worpen zijn onafhankelijk” (massaal gebruikt in het weekendprobleem) is deze berekening, met meer indices.

Voorbeeld 21.22 (Eerste-stapanalyse)

Voor het geometrische model van Voorbeeld 21.5, wat is de waarschijnlijkheid $u$ dat de eerste kop op een even rang valt? Conditioneer op worp één: met waarschijnlijkheid $p$ is de rang $1$ (oneven); met waarschijnlijkheid $q = 1 - p$ herstart het spel met alle pariteiten omgeklapt, dus

u = p\cdot0 + q\,(1 - u) \qquad\Longrightarrow\qquad u = \frac{q}{1 + q} .

Eén regel, geen reeks — en het komt overeen met de directe sommatie van Oefening 21.9, die $1 - u = \frac1{1+q}$ geeft. Deze “eerste-stap”-techniek (conditioneer op het eerste experiment, herken een verschoven kopie van het probleem) is de probabilistische vorm van een recursie, en zij is de motor achter de spelduurvergelijkingen van Oefening 21.6 en de eerste-passageberekeningen van het weekendprobleem.

21.3 Het lemma van Borel–Cantelli

Definitie 21.23 (Limes superior van gebeurtenissen)

Voor een rij $(A_n)$ van gebeurtenissen is de gebeurtenis

\limsup_n A_n = \bigcap_{N=0}^{\infty}\ \bigcup_{n \geq N} A_n = \{\omega \in \Omega : \omega \in A_n \text{ voor oneindig veel } n\}

de gebeurtenis “ $A_n$ treedt oneindig vaak op”.

Voorbeeld 21.24 (“Oneindig vaak” en “uiteindelijk” vertalen)

Het complement van $\limsup_nA_n$ is, via de Morgan,

\Bigl(\bigcap_N\bigcup_{n\geq N}A_n\Bigr)^{\!c} = \bigcup_N\bigcap_{n\geq N}A_n^c = \{\omega : \omega \notin A_n \text{ voor alle grote }n\},

de gebeurtenis “uiteindelijk faalt $A_n$ ” (geschreven $\liminf_nA_n^c$ ). Dus “ $A_n$ oneindig vaak” en “ $A_n^c$ uiteindelijk” zijn complementair — dit woordenboek recht houden voorkomt de meeste kwantorongelukken. Voorbeeldvertalingen bij muntworpen: “oneindig veel kop” is $\limsup\{X_n = H\}$ ; “slechts eindig veel reeksen van $100$ kop” is het complement van een limsup; “de lopende frequentie convergeert naar $\frac12$ ” is $\bigcap_j\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - \tfrac12} < \tfrac1j\}$ — aftelbare operaties doorheen, dus dit zijn allemaal eerlijke gebeurtenissen.

Stelling 21.25 (Borel–Cantelli)

Als $\sum_{n} \P(A_n) < \infty$ , dan $\P\bigl(\limsup_n A_n\bigr) = 0$ .
Als de gebeurtenissen $A_n$ onafhankelijk zijn en $\sum_n \P(A_n) = \infty$ , dan $\P\bigl(\limsup_n A_n\bigr) = 1$ .

Bewijs. 1. Laat $C_N = \bigcup_{n \geq N}A_n$ ; de rij $(C_N)$ is dalend met doorsnede $\limsup A_n$ , en door aftelbare subadditiviteit (Gevolg 21.7)

\P(C_N) \leq \sum_{n \geq N}\P(A_n) \xrightarrow[N\to\infty]{} 0

(staart van een convergente reeks). Monotone continuïteit (Stelling 21.6) besluit: $\P(\limsup A_n) = \lim_N \P(C_N) = 0$ .

2. Het volstaat te tonen $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ voor elke $N$ : inderdaad, als gebeurtenissen $B_N$ alle waarschijnlijkheid $1$ hebben, dan

\P\Bigl(\Bigl(\bigcap_NB_N\Bigr)^{\!c}\Bigr) = \P\Bigl(\bigcup_NB_N^c\Bigr) \leq \sum_N\P(B_N^c) = 0

door aftelbare subadditiviteit (Gevolg 21.7), zodat de aftelbare doorsnede $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ nog steeds waarschijnlijkheid $1$ heeft. Fixeer $N$ , en beschouw voor $M > N$ het complement:

\P\Bigl(\bigcap_{n=N}^{M} A_n^c\Bigr) = \prod_{n=N}^{M}\bigl(1 - \P(A_n)\bigr) \leq \prod_{n=N}^{M} e^{-\P(A_n)} = \exp\Bigl(-\sum_{n=N}^M \P(A_n)\Bigr) ,

met gebruik van onafhankelijkheid van de complementen en de convexiteitsgrens $1 - x \leq e^{-x}$ . Als $M \to \infty$ gaat de exponent naar $-\infty$ door divergentie van de reeks, zodat door monotone continuïteit (dalende rij) $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$ , d.w.z. $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$ . ∎

Voorbeeld 21.26 (Oneindige reeksen kop)

Gooi eeuwig een eerlijke munt, en laat $A_n$ de gebeurtenis zijn “worpen $n, n+1, \dots, n + k - 1$ zijn alle kop” (een reeks van $k$ kop beginnend op tijdstip $n$ ), voor vaste $k$ . De gebeurtenissen $A_{jk}$ ( $j = 1, 2, \dots$ ), die afhangen van disjuncte blokken worpen, zijn onafhankelijk, elk van waarschijnlijkheid $2^{-k}$ , en $\sum_j 2^{-k} = \infty$ : door Borel–Cantelli 2 zijn er met waarschijnlijkheid $1$ oneindig veel all-kop-blokken — elk vast patroon keert oneindig vaak terug, bijna zeker. Omgekeerd, als we de reeklengte laten groeien, $B_n = {}$ “een reeks van $2\log_2 n$ kop begint op $n$ ” heeft $\P(B_n) = n^{-2}$ sommeerbaar, zodat bijna zeker slechts eindig veel zulke lange reeksen starten: Borel–Cantelli kalibreert precies hoe lang de langste reeksen zijn.

Voorbeeld 21.27 (De oneindige aap, gekwantificeerd)

Een aap typt onafhankelijke uniforme letters uit een $26$ -letteralfabet. Knip het typescript in disjuncte blokken van vier letters; de gebeurtenissen $A_j = {}$ “blok $j$ spelt MATH” zijn onafhankelijk met $\P(A_j) = 26^{-4}$ , en $\sum_j\P(A_j) = \infty$ : door Borel–Cantelli 2 typt de aap MATH oneindig vaak, bijna zeker — en hetzelfde geldt voor elke vaste tekst van elke lengte, met aangepaste blokken. De kwantitatieve voetnoot holt het wonder uit: $26^4 = 456\,976$ , dus de eerste MATH kost gemiddeld ongeveer een half miljoen toetsaanslagen, en een Shakespeare-stuk van $10^5$ tekens wacht van orde $26^{10^5}$ blokken — bijna zeker is een uitspraak over de horizon $\infty$ , niet over enige horizon die een aap zal ontmoeten. Borel–Cantelli certificeert de limiet; de grootte van de sommanden vertelt het verhaal op menselijke schaal.

Opmerking 21.28

In Voorbeeld 21.26 is de onderliggende uitkomstenruimte (oneindige rijen worpen) onaftelbaar, zodat het voorbeeld strikt genomen in het maattheoretische kader van Bachelor jaar 3 leeft; de berekeningen gebruiken echter alleen de in dit hoofdstuk bewezen regels, toegepast op gebeurtenissen bepaald door eindig veel worpen en hun aftelbare combinaties. Dit is de standaard MP*-conventie: de theorie wordt gesteld op aftelbare ruimten, en oneindige-spelvoorbeelden worden met hetzelfde gereedschap behandeld.

Opmerking 21.29 (Perspectieven binnen dit volume)

De machine van dit hoofdstuk wordt wholesale geconsumeerd door de volgende twee. Indicatoren zetten gebeurtenissen om in stochastische variabelen, en $\sigma$ -additiviteit wordt de sommeerbaarheid die verwachting definieert (Hoofdstuk 22); Borel–Cantelli plus een sommeerbare staartgrens is precies hoe de sterke wet van de grote aantallen voor munten daar bewezen wordt. In Hoofdstuk 23 keert monotone continuïteit terug op het beslissende moment: de uitsterfkans van een vertakkingsproces wordt gedefinieerd als de monotone limiet $\lim\P(Z_n = 0)$ , en de vastpuntvergelijking die zij vervult wordt verkregen door naar de limiet te gaan in die stijgende rij — de laatste stelling van het boek rust op de eerste stelling van dit hoofdstuk.

Opmerking 21.30 (Methode: drie wegen naar waarschijnlijkheid één)

Bijna-zekere uitspraken worden bewezen met drie hendels, in toenemende sterkte. Monotone continuïteit: toon de gebeurtenis als een stijgende unie (of dalende doorsnede) van eindige-horizongebeurtenissen met berekenbare kansen (Voorbeeld 21.9). Nul-unies: een aftelbare unie van nulwaarschijnlijkheidsgebeurtenissen is nul (aftelbare subadditiviteit), zodat het volstaat elke slechte gebeurtenis apart te doden — zo assembleert “voor elke $j$ , uiteindelijk $\abs{\widehat p_n - p} < 1/j$ ” tot convergentie. Borel–Cantelli: wanneer de gebeurtenis een limsup is, sommeer de kansen; convergentie doodt haar (geen onafhankelijkheid nodig), en divergentie plus onafhankelijkheid certificeert haar. De juiste hendel kiezen is meestal het hele bewijs; het weekendprobleem draait alle drie in één argument.

Opmerking 21.31 (Waar dit gebruikt wordt)

Monotone continuïteit en Borel–Cantelli zijn de twee hendels van elke “bijna zeker”-uitspraak: zij drijven de recurrentie van de toevalswandeling in het weekendprobleem van dit hoofdstuk, de bijna-zekere kant van de wet van de grote aantallen (Hoofdstuk 22), en de uitsterfanalyse van vertakkingsprocessen (Hoofdstuk 23). Het Bachelor jaar 3-volume herbouwt de theorie op $\sigma$ -algebra’s en Lebesgue-integratie, waar de hier informeel gebruikte onaftelbare uitkomstenruimten volledig rigoureus worden.

21.4 Oefeningen

Oefening 21.1 ★

Een urn bevat $n$ genummerde ballen. Ballen worden één voor één getrokken zonder teruglegging. Bereken de waarschijnlijkheid dat bal nummer $1$ vóór bal nummer $2$ getrokken wordt. Veralgemeen: de waarschijnlijkheid dat bal $1$ als eerste onder de ballen $1, \dots, k$ getrokken wordt.

Oplossing

Oplossing van Oefening 21.1.

Door symmetrie: de trekvolgorde induceert een uniform willekeurige relatieve orde op de ballen $1$ en $2$ , dus $\P(1 \text{ vóór } 2) = \frac12$ . Formeel: de posities van de ballen $1$ en $2$ in een treksequentie verwisselen is een bijectie van de (equiprobable) uitkomsten die de gebeurtenis met haar complement verwisselt. Onder de ballen $1, \dots, k$ : de relatieve orde van deze $k$ ballen is uniform onder de $k!$ ordeningen, en bal $1$ is eerste in $(k-1)!$ ervan: waarschijnlijkheid $\frac{(k-1)!}{k!} = \frac1k$ .

Oefening 21.2 ★

Toon dat op $\Omega = \N^*$ de gewichten $p_k = \frac{1}{k(k+1)}$ een waarschijnlijkheidsmaat definiëren, en bereken $\P(2\N^*)$ (even uitkomsten) als reeks; toon dat die gelijk is aan $1 - \ln 2$ . (Telescoop $\frac{1}{2j(2j+1)} = \frac{1}{2j} - \frac{1}{2j+1}$ en gebruik de alternerende harmonische reeks, Hoofdstuk 7.)

Oplossing

Oplossing van Oefening 21.2.

$\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$ , dus $\sum_{k\geq1} p_k$ telescopt tot $1$ : een waarschijnlijkheidsmaat. Even uitkomsten:

\P(2\N^*) = \sum_{j=1}^{\infty}\frac{1}{2j(2j+1)} = \sum_{j=1}^{\infty}\Bigl(\frac{1}{2j} - \frac{1}{2j+1}\Bigr) = \frac12 - \frac13 + \frac14 - \frac15 + \cdots

Dit is de alternerende harmonische reeks met haar eerste term verwijderd en tekens omgeklapt: omdat $\ln 2 = 1 - \frac12 + \frac13 - \frac14 + \cdots$ (Hoofdstuk 7),

\P(2\N^*) = -\bigl(\ln 2 - 1\bigr) = 1 - \ln 2 \approx 0.307 .

Oefening 21.3 ★

(Vals-positieven) Een ziekte treft één persoon op $10\,000$ . Een test detecteert haar met waarschijnlijkheid $0.99$ bij de zieken, en geeft een vals-positief met waarschijnlijkheid $0.01$ bij de gezonden. Bereken de waarschijnlijkheid om ziek te zijn gegeven een positieve test, en becommentarieer.

Oplossing

Oplossing van Oefening 21.3.

Laat $S$ = ziek, $+$ = positieve test. Bayes (Stelling 21.14) met de partitie $\{S, S^c\}$ :

\P(S \mid +) = \frac{0.99 \times 10^{-4}} {0.99 \times 10^{-4} + 0.01 \times 0.9999} = \frac{0.000099}{0.000099 + 0.009999} \approx 0.0098 ,

onder $1\%$ . Hoewel de test “ $99\%$ accuraat” is, laat een positief resultaat u ongeveer $99\%$ waarschijnlijk gezond: de vals-positieven onder de enorme gezonde meerderheid overspoelen de ware positieven uit de minuscule zieke minderheid. Screeningstests voor zeldzame aandoeningen moeten altijd via deze basispercentageberekening gelezen worden.

Oefening 21.4 ★★

Zij $A_1, \dots, A_n$ gebeurtenissen. Bewijs de inclusie–exclusieformule

\P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\,\P\Bigl(\bigcap_{i \in J}A_i\Bigr)

door de identiteit $1 - \prod_{i=1}^n(1 - \mathbf{1}_{A_i}) = \mathbf{1}_{\bigcup A_i}$ over $\Omega$ te integreren (d.w.z. te sommeren gewogen met $\P(\{\omega\})$ ).

Oplossing

Oplossing van Oefening 21.4.

Puntsgewijs op $\Omega$ : $\omega \in \bigcup A_i$ dan en slechts dan als enige factor $1 - \mathbf{1}_{A_i}(\omega)$ verdwijnt, dus

\mathbf{1}_{\bigcup A_i} = 1 - \prod_{i=1}^n\bigl(1 - \mathbf{1}_{A_i}\bigr) = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}} (-1)^{\abs J + 1}\prod_{i \in J}\mathbf{1}_{A_i} ,

door het product te ontwikkelen en de $1$ over te brengen. Nu $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J} A_i}$ , en sommeren tegen de gewichten $\P(\{\omega\})$ — legaal: eindig veel begrensde termen, elke familie sommeerbaar — zet elke indicator om in de waarschijnlijkheid van haar gebeurtenis, wat de formule geeft.

Oefening 21.5 ★★

(Matchingprobleem, via inclusie–exclusie) $n$ brieven worden uniform willekeurig in $n$ enveloppen gestopt, één per envelop. Gebruik Oefening 21.4 om te tonen dat de waarschijnlijkheid van geen correcte match $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$ is, en leid de waarschijnlijkheid van precies één match af.

Oplossing

Oplossing van Oefening 21.5.

Laat $A_i$ = “brief $i$ zit in de juiste envelop”. Voor $J$ van grootte $k$ , $\P\bigl(\bigcap_{i\in J}A_i\bigr) = \frac{(n-k)!}{n!}$ (fixeer $k$ brieven, permuteer de rest). Door inclusie–exclusie,

\P\Bigl(\bigcup A_i\Bigr) = \sum_{k=1}^n (-1)^{k+1}\binom nk \frac{(n-k)!}{n!} = \sum_{k=1}^n \frac{(-1)^{k+1}}{k!} ,

dus

\P(\text{geen match}) = 1 - \P\Bigl(\bigcup A_i\Bigr) = \sum_{k=0}^{n}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} \approx 0.368 .

Precies één match: een permutatie met precies één vast punt wordt bepaald door de keuze van de vaste brief ( $n$ manieren) en een derangement (geen-match-arrangement) van de andere $n - 1$ ; schrijvend $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ voor het aantal derangementen (het eerste deel, geschaald met $(n-1)!$ ),

\P(\text{precies één match}) = \frac{n\,D_{n-1}}{n!} = \frac{D_{n-1}}{(n-1)!} = \sum_{k=0}^{n-1}\frac{(-1)^k}{k!} \xrightarrow[n\to\infty]{} e^{-1} :

in de limiet zijn “geen match” en “precies één match” even waarschijnlijk, elk met waarschijnlijkheid $e^{-1}$ .

Oefening 21.6 ★★

Een oneerlijke munt (kopkans $p \in \intoo{0}{1}$ ) wordt gegooid tot twee opeenvolgende koppen verschijnen. Laat $q_n$ de waarschijnlijkheid zijn dat het spel langer duurt dan $n$ worpen. Toon, conditionerend op de eerste worp(en), dat $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ voor $n \geq 2$ , en leid af dat het spel eindigt met waarschijnlijkheid $1$ . (Toon $q_n \to 0$ door vergelijking met een geometrische rij: beide wortels van de karakteristieke vergelijking liggen in absolute waarde in $\intoo{0}{1}$ .)

Oplossing

Oplossing van Oefening 21.6.

Conditioneer op het begin (kettingregel / Stelling 21.14):

eerste worp T (waarschijnlijkheid $1 - p$ ): het spel herstart vers; langer dan $n$ betekent langer dan $n - 1$ vanaf daar: bijdrage $(1-p)\,q_{n-1}$ ;
eerste worpen HT (waarschijnlijkheid $p(1-p)$ ): herstart na twee worpen: bijdrage $p(1-p)\,q_{n-2}$ ;
eerste worpen HH: het spel is geëindigd (binnen $n$ worpen, $n \geq 2$ ): draagt $0$ bij.

Dus $q_n = (1-p)q_{n-1} + p(1-p)q_{n-2}$ . De karakteristieke vergelijking $r^2 = (1-p)r + p(1-p)$ heeft wortels

r_\pm = \frac{(1-p) \pm \sqrt{(1-p)^2 + 4p(1-p)}}{2},

met $\abs{r_\pm} < 1$ : inderdaad voldoet het polynoom $\chi(r) = r^2 - (1-p)r - p(1-p)$ aan $\chi(1) = 1 - (1-p) - p(1-p) = p^2 > 0$ en $\chi(-1) = 1 + (1-p) - p(1-p) > 0$ , terwijl $\chi(0) = -p(1-p) < 0$ : één wortel in $\intoo{-1}{0}$ , één in $\intoo{0}{1}$ . Dus $q_n = \alpha r_+^n + \beta r_-^n \to 0$ . De gebeurtenissen “spel duurt langer dan $n$ ” dalen naar “spel eindigt nooit”; monotone continuïteit (Stelling 21.6) geeft $\P(\text{eindigt nooit}) = \lim q_n = 0$ : het spel eindigt bijna zeker.

Oefening 21.7 ★★★

(Records) Trek een oneindige rij onafhankelijke uniforme rangschikkingen, in de volgende combinatorische zin: voor elke $n$ is de relatieve orde van de eerste $n$ trekkingen uniform onder de $n!$ mogelijkheden, en $R_n = {}$ “de $n$ -de trekking is een record (groter dan alle vorige)”. Toegevend dat de gebeurtenissen $R_n$ onafhankelijk zijn met $\P(R_n) = 1/n$ (bewijs minstens deze laatste gelijkheid door symmetrie), toon met Borel–Cantelli dat oneindig veel records bijna zeker optreden, maar dat records op opeenvolgende tijden $n, n+1$ oneindig vaak optreden met waarschijnlijkheid — bereken $\sum_n \P(R_n \cap R_{n+1})$ en concludeer wat Borel–Cantelli 1 geeft.

Oplossing

Oplossing van Oefening 21.7.

$\P(R_n) = 1/n$ : onder de eerste $n$ trekkingen is elk van de $n$ relatieve posities van de laatste trekking even waarschijnlijk (uniformiteit van de relatieve orde), en $R_n$ is de gebeurtenis dat die de grootste is: waarschijnlijkheid $1/n$ .

Oneindig veel records: $\sum_n \P(R_n) = \sum 1/n = \infty$ en de $R_n$ zijn onafhankelijk (toegegeven), dus Borel–Cantelli 2 (Stelling 21.25) geeft $\P(\limsup R_n) = 1$ : records stoppen nooit, bijna zeker — maar ze dunnen logaritmisch uit.

Opeenvolgende records: door onafhankelijkheid,

\sum_n \P(R_n \cap R_{n+1}) = \sum_n \frac{1}{n(n+1)} < \infty ,

dus Borel–Cantelli 1 past toe: bijna zeker is slechts eindig vaak een record onmiddellijk gevolgd door een ander record. De twee helften van het lemma werken samen: oneindig veel records, maar (b.z.) uiteindelijk nooit twee op een rij.

Oefening 21.8 ★★★

(Kochen–Stone-smaak, eenvoudiger versie) Zij $(A_n)$ onafhankelijke gebeurtenissen met $\P(A_n) = \frac{1}{n+1}$ . Toon dat $\P(\limsup A_n) = 1$ , hoewel $\P(A_n) \to 0$ : “individueel zeldzaam, collectief zeker”. Omgekeerd, geef een rij (afhankelijke) gebeurtenissen met $\sum\P(A_n) = \infty$ en $\P(\limsup A_n) = 0$ , waarmee getoond wordt dat onafhankelijkheid niet mag worden weggelaten in Borel–Cantelli 2.

Oplossing

Oplossing van Oefening 21.8.

Eerste deel: $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ met onafhankelijkheid: Borel–Cantelli 2 geeft $\P(\limsup A_n) = 1$ . Elke individuele $A_n$ wordt steeds onwaarschijnlijker, toch behoort bijna elke $\omega$ tot oneindig veel ervan.

Tegenvoorbeeld zonder onafhankelijkheid: neem $\Omega = \N^*$ met de gewichten $p_k = \frac{1}{k(k+1)}$ van Oefening 21.2, en $A_n = \{k \in \N^* : k \geq n\}$ . Dan

\P(A_n) = \sum_{k \geq n}\Bigl(\frac1k - \frac1{k+1}\Bigr) = \frac1n , \qquad \sum_n \P(A_n) = \infty ,

maar de $A_n$ zijn dalend, dus $\limsup_n A_n = \bigcap_n A_n = \emptyset$ : $\P(\limsup A_n) = 0$ . Divergentie van $\sum\P(A_n)$ alleen garandeert niets wanneer de gebeurtenissen zich opstapelen op een krimpend deel van de ruimte — onafhankelijkheid is wat die samenzwering verbiedt.

Oefening 21.9 ★

Een munt met kopkans $p \in \intoo01$ wordt gegooid tot de eerste kop. Bereken de waarschijnlijkheid dat dit op een oneven rang gebeurt, en evalueer die voor een eerlijke munt.

Oplossing

Oplossing van Oefening 21.9.

Met $q = 1 - p$ valt de eerste kop op rang $2j + 1$ met waarschijnlijkheid $q^{2j}p$ , dus

\P(\text{oneven rang}) = \sum_{j\geq0}q^{2j}p = \frac{p}{1 - q^2} = \frac{1}{1 + q} .

Voor een eerlijke munt: $\frac1{1 + 1/2} = \frac23$ . (Saniteitscontrole: oneven rangen moeten waarschijnlijker zijn, omdat rang $1$ eerst komt — en inderdaad $\frac1{1+q} > \frac12$ altijd.)

Oefening 21.10 ★★

Zij $(A_n)_{n\geq1}$ onafhankelijke gebeurtenissen met $\P(A_n) = p_n < 1$ . Toon dat

\P\Bigl(\bigcap_{n\geq1}A_n^c\Bigr) = \prod_{n\geq1}(1 - p_n) := \lim_{N\to\infty}\prod_{n=1}^N(1 - p_n),

en dat deze limiet $> 0$ is dan en slechts dan als $\sum p_n < \infty$ . Verzoen met Borel–Cantelli: wanneer $\sum p_n = \infty$ , treedt niet alleen enige $A_n$ bijna zeker op — oneindig veel doen dat.

Oplossing

Oplossing van Oefening 21.10.

De gebeurtenissen $B_N = \bigcap_{n=1}^N A_n^c$ dalen naar $\bigcap_nA_n^c$ , en door onafhankelijkheid van de complementen $\P(B_N) = \prod_{n=1}^N(1 - p_n)$ ; monotone continuïteit (Stelling 21.6) geeft de weergegeven limiet. Logaritmen nemend, $\prod(1 - p_n) > 0$ dan en slechts dan als $\sum-\ln(1 - p_n) < \infty$ . Als $\sum p_n < \infty$ dan $p_n \to 0$ en $-\ln(1 - p_n) \sim p_n$ : de logreeks convergeert. Als $\sum p_n = \infty$ , dwingt $-\ln(1 - p_n) \geq p_n$ divergentie, dus het product is $0$ . Dit komt overeen met Borel–Cantelli 2: voor $\sum p_n = \infty$ is niet alleen $\P(\text{geen }A_n\text{ treedt op}) = 0$ , maar treden bijna zeker oneindig veel $A_n$ op.

Oefening 21.11 ★★

(Banachs lucifersdoosje) Een roker houdt in elke zak één doosje met $n$ lucifers en grijpt elke keer in een uniform willekeurige zak. Wanneer hij voor het eerst een leeg doosje vindt, wat is de waarschijnlijkheid dat het andere doosje precies $k$ lucifers bevat? Toon dat het antwoord $\binom{2n-k}{n}2^{-(2n-k)}$ is en controleer dat deze kansen sommeren tot $1$ voor $n = 1$ .

Oplossing

Oplossing van Oefening 21.11.

Zeg doosje $A$ is het eerst leeg aangetroffen, met het andere doosje $k$ houdend. Dit betekent: onder de eerste $2n - k$ grepen gingen er precies $n$ naar $A$ en $n - k$ naar $B$ (in enige volgorde), en greep nummer $2n - k + 1$ ging opnieuw naar $A$ , die leeg vond. De grepen zijn onafhankelijke eerlijke keuzes, dus deze gebeurtenis heeft waarschijnlijkheid $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$ ; verdubbelen (het lege doosje kan elk van beide zijn) geeft

\P(\text{ander doosje heeft }k) = \binom{2n-k}{n}\,2^{-(2n-k)} .

Voor $n = 1$ : $k = 1$ geeft $\binom11 2^{-1} = \frac12$ en $k = 0$ geeft $\binom21 2^{-2} = \frac12$ : totaal $1$ , zoals het moet.

Oefening 21.12 ★★★

( $\sigma$ -additiviteit is een echt axioma) (a) Toon dat er geen waarschijnlijkheidsmaat op $(\N, \mathcal P(\N))$ bestaat die alle singletonen hetzelfde gewicht geeft. (b) Voor $A \subseteq \N^*$ , laat $d(A) = \lim_n\frac{\abs{A\cap\intint1n}}{n}$ wanneer de limiet bestaat (de natuurlijke dichtheid). Toon dat $d$ eindig additief is op paren waar alle drie de dichtheden bestaan, elke singleton dichtheid $0$ en $\N^*$ dichtheid $1$ geeft — en concludeer dat $d$ niet $\sigma$ -additief is. (c) Geef een verzameling zonder dichtheid. (Wissel af blokken $\intint{2^{2k}}{2^{2k+1}-1}$ in en uit.)

Oplossing

Oplossing van Oefening 21.12.

(a) Als $\P(\{n\}) = c$ voor alle $n$ , dwingt $\sigma$ -additiviteit $1 = \sum_nc$ : onmogelijk, ofwel $c = 0$ (som $0$ ) ofwel $c > 0$ (som oneindig). Er is geen uniforme waarschijnlijkheid op $\N$ .

(b) Als $A \cap B = \emptyset$ en $d(A)$ , $d(B)$ bestaan, dan $\abs{(A \sqcup B)\cap\intint1n} = \abs{A\cap\intint1n} + \abs{B\cap\intint1n}$ , dus $d(A \sqcup B) = d(A) + d(B)$ : eindige additiviteit op zulke paren. Elke singleton heeft uiteindelijk constante telfunctie, dus dichtheid $0$ , terwijl $d(\N^*) = 1$ . Was $d$ $\sigma$ -additief, dan zou $\N^* = \bigsqcup_k\{k\}$ geven $1 = \sum_k 0 = 0$ : dichtheid is eindig additief maar niet $\sigma$ -additief — het axioma heeft inhoud.

(c) Laat $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (blokken van $4^k$ tot $2\cdot4^k - 1$ ). Bij $n = 2\cdot4^K - 1$ is de telling $\sum_{k\leq K}4^k \sim \frac43 4^K$ , wat verhouding $\to \frac23$ geeft; bij $n = 4^{K+1} - 1$ is de telling onveranderd, wat verhouding $\to \frac13$ geeft. De verhouding oscilleert tussen limieten $\frac13$ en $\frac23$ : geen dichtheid.

21.5 Probleem: de eenvoudige toevalswandeling op $\Z$ is recurrent

Vierentwintig stappen van een eenvoudige toevalswandeling; de rode stippen markeren de terugkeringen naar de oorsprong. Het probleem toont dat, met waarschijnlijkheid 1, deze stippen nooit ophouden te verschijnen — toch heeft de wachttijd ertussen divergente verwachting. — Vierentwintig stappen van een eenvoudige toevalswandeling; de rode stippen markeren de terugkeringen naar de oorsprong. Het probleem toont dat, met waarschijnlijkheid $1$ , deze stippen nooit ophouden te verschijnen — toch heeft de wachttijd ertussen divergente verwachting.

Probleem 21.1

Weekendprobleem — Pólya’s recurrentiestelling op $\Z$ , met het stembiljetprobleem en de arcsinus-smaak onderweg

Gooi eeuwig een eerlijke munt; laat $X_i = \pm1$ de $i$ -de stap zijn en $S_n = X_1 + \dots + X_n$ de eenvoudige toevalswandeling op $\Z$ , $S_0 = 0$ . Zoals in Voorbeeld 21.26 worden alle gebeurtenissen hieronder bepaald door eindig veel worpen of zijn aftelbare combinaties van zulke gebeurtenissen, en onafhankelijkheid van gebeurtenissen die afhangen van disjuncte blokken worpen hoort bij het model. We schrijven $u_n = \P(S_{2n} = 0)$ en $N_n(k)$ voor het aantal $\pm1$ -paden van lengte $n$ van $0$ naar $k$ .

Deel I — Paden tellen.

Toon dat $N_n(k) = \binom{n}{(n+k)/2}$ wanneer $n + k$ even is en $\abs k \leq n$ , en $0$ anders; leid af $\P(S_n = k) = N_n(k)\,2^{-n}$ . Waarom is elk individueel pad van lengte $n$ even waarschijnlijk?
Toon $S_{2n+1} \neq 0$ , $u_n = \binom{2n}{n}4^{-n}$ , en bereken $u_1, u_2, u_3$ .
Bewijs $u_n = \frac{2n-1}{2n}\,u_{n-1}$ ; leid af dat $(u_n)$ daalt naar $0$ , en uit Voorbeeld 6.14 dat

$u_n \sim \frac{1}{\sqrt{\pi n}}, \qquad\text{dus}\qquad \sum_n u_n = \infty .$
(Reflectieprincipe) Voor $k \geq 1$ , toon dat de paden van lengte $n$ van $1$ naar $k$ die $0$ raken in bijectie staan met de paden van $-1$ naar $k$ ; leid af dat het aantal paden van $0$ naar $k$ die na tijd $0$ $> 0$ blijven $N_{n-1}(k-1) - N_{n-1}(k+1)$ is.
(Stembiljetstelling) Leid af dat

$\P\bigl(S_1 > 0, \dots, S_{n-1} > 0 \bigm| S_n = k\bigr) = \frac kn \qquad (k \geq 1) :$

bij een telling waar de winnaar met $k$ van de $n$ stemmen leidt, is de waarschijnlijkheid dat de winnaar de hele telling heeft geleid $k/n$ . Verifieer met de hand voor $n = 3$ , $k = 1$ .

Deel II — Terugkeer naar de oorsprong.

Bewijs de sleutelidentiteit

$\P(S_1 \neq 0,\ S_2 \neq 0,\ \dots,\ S_{2n} \neq 0) = u_n$

(conditioneer op de eerste stap, sommeer de tellingen van vraag 4 over het eindpunt, en telescoop; eindig met $2\binom{2n-1}{n} = \binom{2n}{n}$ ).
Leid uit monotone continuïteit (Stelling 21.6) af dat de wandeling met waarschijnlijkheid $1$ minstens één keer naar $0$ terugkeert, en dat $f_n := \P(\text{eerste terugkeer op tijd }2n)$ voldoet aan

$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1}, \qquad \sum_{n\geq1}f_n = 1 .$
Toon dat $\sum_n 2n\,f_n = \infty$ : de terugkeer is zeker, maar de reeks die de gemiddelde wachttijd zou berekenen divergeert (in de woordenschat van Hoofdstuk 22 heeft de terugkeertijd oneindige verwachting).
Bewijs dat voor elke $k \geq 1$ , $\P(\text{minstens } k\text{ terugkeringen naar }0) = 1$ (ontbind over de tijden van de eerste $k$ terugkeringen: de bijbehorende worpblokken zijn disjunct, dus de kansen vermenigvuldigen en sommen tot $(\sum_nf_n)^k$ ); besluit met monotone continuïteit:

$\P(S_n = 0 \text{ voor oneindig veel } n) = 1 :$

de eenvoudige toevalswandeling op $\Z$ is recurrent.
Toon dat de wandeling bijna zeker elke plaats $k \in \Z$ bezoekt, en dus (door recurrentie, herstart bij het eerste bezoek) oneindig vaak. (De tekens van de opeenvolgende excursies uit $0$ zijn onafhankelijke eerlijke munten; een positieve excursie bezoekt $1$ .)

Deel III — Borel–Cantelli en de vertekende wandeling.

De gebeurtenissen $A_n = \{S_{2n} = 0\}$ voldoen aan $\sum\P(A_n) = \infty$ ; leg uit waarom Borel–Cantelli 2 er niet op van toepassing is, en wat Borel–Cantelli 1 zou geven als de reeks convergeerde. (Dit is de strategie van heel Deel II.)
Laat nu de munt vertekening $p \neq \frac12$ hebben, $q = 1 - p$ . Toon $\P(S_{2n} = 0) = \binom{2n}n(pq)^n = u_n\,(4pq)^n$ met $4pq < 1$ , leid af $\sum_n\P(S_{2n} = 0) < \infty$ , en concludeer met Borel–Cantelli 1 dat de vertekende wandeling bijna zeker slechts eindig vaak naar $0$ terugkeert.
Nog steeds voor $p \neq \frac12$ : toon $\P(S_n = k) \leq \binom{n}{\floor{n/2}}\,(pq)^{n/2}\,(p/q)^{k/2}$ voor elke vaste $k$ , leid af dat elke plaats bijna zeker eindig vaak bezocht wordt, en concludeer $\abs{S_n} \to \infty$ bijna zeker: de vertekende wandeling is transient.
Terug naar de eerlijke munt: bereken met vraag 6 de waarschijnlijkheid dat $200$ worpen geen gelijkspel produceren ( $S_n \neq 0$ voor $1 \leq n \leq 200$ ), numeriek $u_{100} \approx 0.056$ . Becommentarieer het trage $1/\sqrt{\pi n}$ -verval: gelijkspelen zijn zeker op lange termijn maar zeldzamer dan de intuïtie suggereert.
(Eerste passage) Laat $T_1$ de eerste tijd zijn dat de wandeling $1$ raakt. Gebruik het reflectieprincipe voor het maximum $M_n = \max_{i\leq n}S_i$ (bewezen in vraag 16, die niet van deze afhangt), of direct uit vraag 7 door te conditioneren op de eerste stap, en toon $\P(T_1 = 2n - 1) = f_n$ ; leid af $\P(T_1 < \infty) = 1$ terwijl de gemiddelde-tijdreeks $\sum(2n-1)f_n$ divergeert.

Deel IV — Maxima, laatste nul, lange leads.

(Reflectie voor het maximum) Voor $k \geq 1$ , bewijs

$\P(M_n \geq k) = 2\,\P(S_n > k) + \P(S_n = k)$

door het pad te reflecteren na zijn eerste bezoek aan niveau $k$ .
Leid af $\P(M_{2n} \geq 1) = 1 - u_n$ , d.w.z. $\P(S_i \leq 0 \text{ voor alle } i \leq 2n) = u_n$ : de waarschijnlijkheid om nooit voor te liggen is gelijk aan de waarschijnlijkheid om nooit op nul te zijn (vraag 6) — twee verschillende gebeurtenissen, één waarschijnlijkheid.
(Laatste nul) Laat $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (even). Combineer vraag 6 met onafhankelijkheid van disjuncte worpblokken en toon

$\P(L_{2n} = 2k) = u_k\,u_{n-k} \qquad (0 \leq k \leq n),$

en leid, zonder verdere berekening, de binomiale identiteit $\sum_{k=0}^n u_ku_{n-k} = 1$ af.
Toon dat de wet van $L_{2n}$ symmetrisch is ( $\P(L = 2k) = \P(L = 2n - 2k)$ ) en, met $u_j \sim 1/\sqrt{\pi j}$ , dat zijn extremen de meest waarschijnlijke waarden zijn. Tabuleer voor $n = 5$ : $\P(L_{10} = 0) = u_5 \approx 0.246$ versus $\P(L_{10} = 4) = u_2u_3 \approx 0.117$ . Interpreteer: in een lang eerlijk spel neigt de laatste gelijkstand zeer vroeg of zeer laat te liggen — lange leads zijn de regel, niet de uitzondering.
Assembleer vragen 16–19 tot een alinea over het fluctuatiebeeld van de eerlijke wandeling: de diffusieve schaal gesuggereerd door vraag 3, de zekerheid van terugkeer tegen de divergente gemiddelde wachttijd, en de arcsinus-achtige persistentie van leads.

Deel V — De vernieuwingsidentiteit en de stelling van Pólya.

Bewijs, door $\{S_{2n} = 0\}$ te partitioneren over de tijd van de eerste terugkeer, de vernieuwingsidentiteit

$u_n = \sum_{k=1}^n f_k\,u_{n-k} \quad (n \geq 1), \qquad\text{dus}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 \quad (0 \leq x < 1),$

waar $U(x) = \sum_{n\geq0}u_nx^n$ en $F(x) = \sum_{n\geq1}f_nx^n$ (rechtvaardig de radii en het product van reeksen met Hoofdstuk 11).
Leid de recurrentiedichotomie af: $x \to 1^-$ nemend (monotone limieten van reeksen met niet-negatieve coëfficiënten),

$\sum_n u_n = \infty \iff \sum_n f_n = 1 ,$

en controleer dit tegen vragen 3, 7 (eerlijke wandeling) en 12 (vertekende wandeling).
(Dimensie $2$ ) De eenvoudige wandeling op $\Z^2$ neemt stappen $(\pm1, 0)$ , $(0, \pm1)$ uniform. Toon dat de geroteerde coördinaten $U_n = X_n + Y_n$ en $V_n = X_n - Y_n$ onafhankelijke eerlijke wandelingen op $\Z$ uitvoeren, leid af

$\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_n u_n^2 = \infty ,$

en concludeer met vragen 21–22 (wier bewijzen letterlijk overdraagbaar zijn) dat de wandeling op $\Z^2$ recurrent is.
(Dimensie $3$ ) Voor de eenvoudige wandeling op $\Z^3$ , geef toe de lokale schatting $\P(S^{(3)}_{2n} = 0) \leq C\,n^{-3/2}$ (bewezen met de lokale limietstelling in het Bachelor jaar 3-volume). Leid uit Borel–Cantelli 1 af dat de wandeling op $\Z^3$ transient is, en stel het volledige resultaat: de stelling van Pólya — de eenvoudige toevalswandeling is recurrent in dimensies $1$ en $2$ , transient in dimensie $3$ en hoger.
Synthese. Noem de precieze rol gespeeld door: padentelling en reflectie; monotone continuïteit; onafhankelijkheid van disjuncte worpblokken; Borel–Cantelli 1; de vernieuwingsidentiteit. Welk enkel analytisch feit ( $u_n \sim 1/\sqrt{\pi n}$ , dus $\sum u_n = \infty$ maar $\sum u_n^2 = \infty$ en $\sum n^{-3/2} < \infty$ ) beslist tussen recurrentie en transientie in elke dimensie?

Oplossing

Oplossing van Probleem 21.1.

1. Een pad van lengte $n$ wordt bepaald door de verzameling van zijn opstappen; eindigen op $k$ betekent $u$ opstappen en $n - u$ afstappen met $u - (n - u) = k$ , d.w.z. $u = \frac{n+k}2$ : mogelijk dan en slechts dan als $n + k$ even is en $\abs k \leq n$ , op $\binom{n}{(n+k)/2}$ manieren. Elk specifiek pad is één punt van de eerlijke productmaat op $n$ worpen: waarschijnlijkheid $2^{-n}$ . Dus $\P(S_n = k) = N_n(k)2^{-n}$ .

2. $S_n$ heeft de pariteit van $n$ , dus $S_{2n+1} \neq 0$ ; en $u_n = N_{2n}(0)4^{-n} = \binom{2n}n4^{-n}$ . Waarden: $u_1 = \frac12$ , $u_2 = \frac6{16} = \frac38$ , $u_3 = \frac{20}{64} = \frac5{16}$ .

3. $\dfrac{u_n}{u_{n-1}} = \dfrac{\binom{2n}n}{4\binom{2n-2}{n-1}} = \dfrac{(2n)(2n-1)}{4n^2} = \dfrac{2n-1}{2n} < 1$ : dalend. Door Voorbeeld 6.14, $\binom{2n}n \sim \frac{4^n}{\sqrt{\pi n}}$ , dus $u_n \sim \frac1{\sqrt{\pi n}} \to 0$ , en $\sum u_n$ divergeert door vergelijking met $\sum n^{-1/2}$ .

4. Gegeven een pad van $1$ naar $k$ dat $0$ raakt, reflecteer zijn beginstuk (tot het eerste bezoek aan $0$ ) door de horizontale as: het resultaat is een pad van $-1$ naar $k$ , en de operatie is een involutie — elk pad van $-1$ naar $k \geq 1$ moet $0$ kruisen, en zijn beginstuk terugreflecteren herstelt het origineel. Dus tellen de rakende paden $N_{n-1}(k + 1)$ (van $-1$ naar $k$ is de verplaatsing $k + 1$ ). Een pad van $0$ naar $k$ dat na tijd $0$ $> 0$ blijft begint met een opstap en gaat dan van $1$ naar $k$ in $n - 1$ stappen zonder $0$ te raken: er zijn $N_{n-1}(k-1) - N_{n-1}(k+1)$ ervan.

5. Met $m = \frac{n+k}2$ , gebruikmakend van $\binom{n-1}{m-1} = \frac mn\binom nm$ en $\binom{n-1}{m} = \frac{n-m}n\binom nm$ :

\frac{N_{n-1}(k-1) - N_{n-1}(k+1)}{N_n(k)} = \frac{\binom{n-1}{m-1} - \binom{n-1}{m}}{\binom nm} = \frac{m - (n - m)}{n} = \frac kn .

Voor $n = 3$ , $k = 1$ : $N_3(1) = 3$ paden ( $++-$ , $+-+$ , $-++$ ), waarvan alleen $++-$ positief blijft ( $+-+$ keert terug naar $0$ op tijd $2$ ): één van de drie, en $\frac kn = \frac13$ .

6. Door symmetrie is de waarschijnlijkheid $2\P(S_i > 0\ \forall i \leq 2n)$ . Sommeren over het eindpunt $2k$ en vraag 4 gebruiken (met $n$ vervangen door $2n$ ):

\P(S_i > 0\ \forall i) = 2^{-2n}\sum_{k\geq1} \bigl(N_{2n-1}(2k-1) - N_{2n-1}(2k+1)\bigr) = 2^{-2n}\,N_{2n-1}(1),

een telescoperende som. Nu $N_{2n-1}(1) = \binom{2n-1}{n}$ en $2\binom{2n-1}n = \binom{2n}n$ (Pascal), dus de weergegeven waarschijnlijkheid is $2\cdot2^{-2n}\binom{2n-1}n = \binom{2n}n4^{-n} = u_n$ .

7. De gebeurtenissen $D_n = \{S_i \neq 0,\ i \leq 2n\}$ dalen, met doorsnede “nooit terugkeer”; door monotone continuïteit en vraag 6, $\P(\text{geen terugkeer}) = \lim u_n = 0$ : de wandeling keert bijna zeker terug. Bovendien $f_n = \P(D_{n-1}) - \P(D_n) = u_{n-1} - u_n$ , en door vraag 3

u_{n-1} - u_n = u_n\Bigl(\frac{2n}{2n-1} - 1\Bigr) = \frac{u_n}{2n-1}; \qquad \sum_{n\geq1}f_n = u_0 - \lim u_n = 1 .

8. $2n\,f_n = \frac{2n}{2n-1}u_n \geq u_n$ , en $\sum u_n = \infty$ (vraag 3): de reeks $\sum 2nf_n$ divergeert. De eerste terugkeer is zeker maar heeft geen eindige gemiddelde wachttijd — de wandeling is nul-recurrent, in de woordenschat die Hoofdstuk 22 zal leveren.

9. De gebeurtenis “minstens $k$ terugkeringen” is de disjuncte aftelbare unie, over $0 < n_1 < \dots < n_k$ , van de gebeurtenissen “de eerste $k$ terugkeringen gebeuren precies op tijden $2n_1, \dots, 2n_k$ ”. Zo’n gebeurtenis is de doorsnede van $k$ gebeurtenissen die afhangen van de disjuncte worpblokken $\intint1{2n_1}$ , $\intint{2n_1+1}{2n_2}$ , …, waarbij elk blok van een verse wandeling eist dat die zijn eerste terugkeer maakt na precies het toegewezen aantal stappen; door onafhankelijkheid van de blokken is haar waarschijnlijkheid $f_{n_1}f_{n_2-n_1}\cdots f_{n_k-n_{k-1}}$ . Sommeren per pakketten (Hoofdstuk 7, alle termen niet-negatief):

\P(\text{minstens }k\text{ terugkeringen}) = \Bigl(\sum_{n\geq1}f_n\Bigr)^{\!k} = 1^k = 1 .

De gebeurtenissen dalen in $k$ , dus door monotone continuïteit $\P(\text{oneindig veel terugkeringen}) = 1$ : recurrentie.

10. Door vraag 9 maakt de wandeling oneindig veel excursies weg van $0$ . De eerste stap van elke excursie is een verse munt, onafhankelijk van alles ervoor: de waarschijnlijkheid dat de eerste $m$ excursies alle neerwaarts starten is $2^{-m}$ . Om $1$ te bereiken heeft de wandeling slechts één opwaartse excursiestart nodig (vanuit $<0$ moet zij door $0$ passeren vóór $1$ , stappen zijnde $\pm1$ ), dus $\P(\text{raakt nooit }1) \leq 2^{-m}$ voor elke $m$ : de wandeling raakt $1$ bijna zeker. Ontbindend over de (bijna zeker eindige) raaktijd, is de daar herstarte wandeling een verse wandeling gestart in $1$ : door inductie raakt zij bijna zeker elke $k \geq 1$ , en door symmetrie elke $k \leq -1$ . Tenslotte, herstartend bij het eerste bezoek aan $k$ , past vraag 9 toe op de verse wandeling: elke plaats wordt oneindig vaak bezocht, bijna zeker.

11. De gebeurtenissen $A_n = \{S_{2n} = 0\}$ zijn verre van onafhankelijk (op $0$ zijn op tijd $2n$ maakt op $0$ zijn op tijd $2n + 2$ veel waarschijnlijker dan $u_{n+1}$ ), dus Borel–Cantelli 2 is niet beschikbaar, en inderdaad was heel het werk van Deel II om haar te vervangen. De andere richting heeft geen onafhankelijkheid nodig: als $\sum\P(A_n)$ convergeert, levert Borel–Cantelli 1 eindig veel terugkeringen bijna zeker. Die implicatie is de motor van elk transientiebewijs hieronder.

12. Een terugkeer op tijd $2n$ eist $n$ op- en $n$ afstappen: $\P(S_{2n} = 0) = \binom{2n}np^nq^n = u_n(4pq)^n$ , en $4pq = 1 - (p - q)^2 < 1$ voor $p \neq \frac12$ . Omdat $u_n \leq 1$ , wordt de reeks $\sum\P(S_{2n} = 0)$ gedomineerd door de geometrische $\sum(4pq)^n$ : convergent. Door Borel–Cantelli 1, $\P(S_{2n} = 0 \text{ oneindig vaak}) = 0$ : eindig veel terugkeringen, bijna zeker.

13. Voor $n + k$ even, $\P(S_n = k) = \binom{n}{\frac{n+k}2}p^{\frac{n+k}2}q^{\frac{n-k}2}$ ; de binomiaalcoëfficiënt is ten hoogste de centrale, en $p^{\frac{n+k}2}q^{\frac{n-k}2} = (pq)^{n/2}(p/q)^{k/2}$ , wat de gestelde grens $\leq 2^n(pq)^{n/2}(p/q)^{k/2} = (4pq)^{n/2}(p/q)^{k/2}$ geeft, sommeerbaar in $n$ omdat $\sqrt{4pq} < 1$ . Borel–Cantelli 1: plaats $k$ wordt eindig vaak bezocht bijna zeker; de unie over $k \in \Z$ van de exceptionele nulgebeurtenissen is nog steeds nul (aftelbare subadditiviteit). Bijna zeker wordt elke plaats eindig vaak bezocht, dus verlaat de gehelenrij $(S_n)$ elk begrensd venster definitief: $\abs{S_n} \to \infty$ .

14. $\P(S_n \neq 0,\ 1 \leq n \leq 200) = u_{100} = \binom{200}{100}4^{-100} \approx \frac1{\sqrt{100\pi}} \approx 0.056$ : meer dan één-op-twintig kans dat $200$ eerlijke worpen nooit gelijkspelen. Het verval $1/\sqrt{\pi n}$ is uitermate traag: zekerheid van een gelijkspel (vraag 7) is compatibel met zeer lange gelijkspel-vrije stukken — een eerste smaak van de arcinusfenomenen van Deel IV.

15. Conditioneer op de eerste stap. Als $X_1 = +1$ dan $T_1 = 1$ , en $f_1 = \frac12$ klopt. Als $X_1 = -1$ , moet de wandeling klimmen van $-1$ naar $1$ ; door de blokontbinding splitst terugkeer naar $0$ voor het eerst op tijd $2n$ als: één stap omlaag, dan een verse wandeling gestart in $-1$ die voor het eerst $0$ raakt — equivalent een verse wandeling die voor het eerst $+1$ raakt — in $2n - 1$ stappen, of de symmetrische opwaartse gebeurtenis. Beide tekens dragen evenveel bij:

f_n = 2\cdot\tfrac12\,\P(T_1 = 2n - 1) = \P(T_1 = 2n-1) .

Dus $\P(T_1 < \infty) = \sum f_n = 1$ , terwijl $\sum_n(2n - 1)f_n = \sum_n u_n = \infty$ door vraag 7: de wandeling bereikt $1$ bijna zeker, in oneindige gemiddelde tijd.

16. Partitioneer $\{M_n \geq k\}$ naar de eindwaarde $S_n = m$ . Voor $m \geq k$ is de voorwaarde $M_n \geq k$ automatisch. Voor $m < k$ , reflecteer het pad na zijn eerste bezoek aan niveau $k$ : dit is een bijectie tussen $\{M_n \geq k, S_n = m\}$ en $\{S_n = 2k - m\}$ (elk pad eindigend op $2k - m > k$ bezoekt $k$ ; terugreflecteren is de inverse). Dus

\P(M_n \geq k) = \sum_{m > k}\P(S_n = m) + \P(S_n = k) + \sum_{m < k}\P(S_n = 2k - m) = 2\P(S_n > k) + \P(S_n = k).

17. Op even tijd $2n$ met $k = 1$ : $\P(S_{2n} = 1) = 0$ en $\P(S_{2n} > 1) = \P(S_{2n} \geq 2)$ , dus

\P(M_{2n} \geq 1) = 2\P(S_{2n} \geq 2) = \P(S_{2n} \geq 2) + \P(S_{2n} \leq -2) = 1 - u_n .

Dus $\P(S_i \leq 0\ \forall i \leq 2n) = u_n$ : de wandeling ligt in de eerste $2n$ stappen precies zo vaak nooit voor als zij nooit gelijk speelt (vraag 6) — twee heel verschillende gebeurtenissen, gedragen door dezelfde $u_n$ .

18. $\{L_{2n} = 2k\} = \{S_{2k} = 0\} \cap \{\text{de wandeling van de worpen } 2k+1, \dots, 2n \text{ heeft geen nul}\}$ . De twee gebeurtenissen hangen af van disjuncte worpblokken, dus zijn onafhankelijk; de eerste heeft waarschijnlijkheid $u_k$ , de tweede $u_{n-k}$ door vraag 6 toegepast op de verse $(2n-2k)$ -stappenwandeling. Dus $\P(L_{2n} = 2k) = u_ku_{n-k}$ . Omdat $L_{2n}$ precies de waarden $0, 2, \dots, 2n$ aanneemt, sommen deze kansen tot $1$ : $\sum_{k=0}^nu_ku_{n-k} = 1$ , een binomiale identiteit geleverd door een probabilistische partitie.

19. Symmetrie is onmiddellijk: $u_ku_{n-k} = u_{n-k}u_k$ . Omdat $u_j$ daalt in $j$ , is het product $u_ku_{n-k}$ het kleinst voor centrale $k$ en het grootst aan de extremen $k \in \{0, n\}$ , waar het gelijk is aan $u_n$ ; kwantitatief $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ in de bulk, tegenover $u_n \approx \frac1{\sqrt{\pi n}}$ aan de randen. Voor $n = 5$ : $\P(L_{10} = 0) = \P(L_{10} = 10) = u_5 = \frac{63}{256} \approx 0.246$ , terwijl $\P(L_{10} = 4) = u_2u_3 = \frac38\cdot\frac5{16} = \frac{15}{128} \approx 0.117$ . In een lang eerlijk spel is de laatste gelijkmaking het meest waarschijnlijk dicht bij het allereerste begin of het allerlaatste eind: één speler leidt typisch over enorme stukken, zonder vertekening van de munt.

20. Het beeld: op tijd $n$ leeft de wandeling op schaal $\sqrt n$ (de binomiale spreiding van vraag 3 — $u_n \sim 1/\sqrt{\pi n}$ is de hoogte van de centrale piek); zij keert oneindig vaak naar $0$ terug met waarschijnlijkheid $1$ (Deel II), toch heeft de wachttijd tussen terugkeringen divergente verwachting (vraag 8), waarom enkele excursies een positieve fractie van elke horizon kunnen innemen; dienovereenkomstig is de laatste gelijkstand van een $2n$ -stappenspel gespreid met extreme waarden het meest waarschijnlijk (vragen 18–19), en heeft nooit-voorliggen dezelfde traag dalende waarschijnlijkheid $u_n$ als nooit-gelijkspelen (vraag 17). Zekerheid in de limiet, persistentie op elke eindige horizon: dat is de eerlijke wandeling.

21. Partitioneer $\{S_{2n} = 0\}$ ( $n \geq 1$ ) over de eerste-terugkeertijd $2k$ , $1 \leq k \leq n$ : het eerste blok van $2k$ worpen realiseert een eerste terugkeer, de resterende $2n - 2k$ worpen realiseren een terugkeer van een verse wandeling, en de blokken zijn onafhankelijk: $u_n = \sum_{k=1}^nf_ku_{n-k}$ . Beide reeksen $U(x) = \sum u_nx^n$ , $F(x) = \sum f_nx^n$ hebben straal $\geq 1$ (coëfficiënten in $\intcc01$ ), en het Cauchy-product (Hoofdstuk 11) geeft, voor $0 \leq x < 1$ ,

U(x) - 1 = \sum_{n\geq1}\Bigl(\sum_{k=1}^n f_ku_{n-k}\Bigr)x^n = F(x)\,U(x), \qquad\text{d.w.z.}\qquad U(x)\bigl(1 - F(x)\bigr) = 1 .

22. Als $x \uparrow 1$ , stijgen $U(x)$ en $F(x)$ (niet-negatieve coëfficiënten); elke deelsom $\sum_{n\leq N}u_n$ is een limiet van $\sum_{n\leq N}u_nx^n \leq U(x)$ , dus $U(x) \uparrow \sum u_n \in \intoc0{+\infty}$ , en evenzo $F(x) \uparrow f = \sum f_n$ . Als $\sum u_n = \infty$ : $1 - F(x) = 1/U(x) \to 0$ , dus $f = 1$ . Als $\sum u_n = S < \infty$ : $1 - f = 1/S > 0$ , dus $f < 1$ . Controles: eerlijke wandeling, $\sum u_n = \infty$ en $f = 1$ (vragen 3, 7); vertekende wandeling, $\sum u_n(4pq)^n < \infty$ en dienovereenkomstig $f = 1 - 1/\sum_{n\geq0}u_n(4pq)^n < 1$ , consistent met de bijna-zekere eindigheid van het aantal terugkeringen (vraag 12).

23. Voor de vier stappen $(\pm1, 0), (0, \pm1)$ van de $\Z^2$ -wandeling zijn de incrementen van $U = X + Y$ en $V = X - Y$ : $(+,+)$ voor $(1,0)$ , $(+,-)$ voor $(0,1)$ , $(-,+)$ voor $(0,-1)$ , $(-,-)$ voor $(-1,0)$ — elk tekenspaar met waarschijnlijkheid $\frac14 = \frac12\cdot\frac12$ : de twee coördinaatwandelingen $(U_n)$ en $(V_n)$ zijn onafhankelijke eerlijke wandelingen op $\Z$ . Omdat $S^{(2)}_{2n} = (0,0)$ dan en slechts dan als $U_{2n} = 0$ en $V_{2n} = 0$ ,

\P\bigl(S^{(2)}_{2n} = (0,0)\bigr) = u_n^2 \sim \frac1{\pi n}, \qquad \sum_nu_n^2 = \infty .

De vernieuwingsidentiteit van vraag 21 en de dichotomie van vraag 22 gebruikten niets ééndimensionaals (alleen de ontbinding over de eerste terugkeer en disjunct-blokonafhankelijkheid), dus $\sum u_n^{(2)} = \infty$ geeft $f^{(2)} = 1$ , en het argument van vraag 9 versterkt het: de wandeling op $\Z^2$ keert oneindig vaak bijna zeker naar de oorsprong terug.

24. Met de toegegeven grens $\P(S^{(3)}_{2n} = 0) \leq Cn^{-3/2}$ convergeert de reeks, en Borel–Cantelli 1 geeft eindig veel terugkeringen bijna zeker: de wandeling op $\Z^3$ is transient (en dezelfde grens met exponent $-d/2$ behandelt elke $d \geq 3$ ). Alles bijeen: de stelling van Pólya — de eenvoudige toevalswandeling is recurrent op $\Z$ en $\Z^2$ , transient op $\Z^d$ voor $d \geq 3$ . Een dronken man vindt de weg naar huis; een dronken vogel misschien niet.

25. Padentelling en reflectie produceerden de exacte wetten ( $u_n$ , de stembiljetstelling, $f_n$ , het maximum, de laatste nul); monotone continuïteit zette elke limietuitspraak (“keert minstens één keer terug”, “oneindig vaak”) om in een limiet van eindige-horizonkansen; disjunct-blokonafhankelijkheid dreef de vernieuwingsontbindingen (vragen 9, 18, 21) — zij is het aftelbare skelet van de Markov-eigenschap; Borel–Cantelli 1 was het transientiewapen (vragen 12–13, 24), zonder onafhankelijkheid nodig; de vernieuwingsidentiteit organiseerde alles tot de dichotomie $\sum u_n = \infty \iff$ recurrentie. De enige analytische input is de lokale schatting $u_n \sim 1/\sqrt{\pi n}$ : haar kwadraat $1/(\pi n)$ divergeert nog (dimensie $2$ , recurrent), terwijl $n^{-3/2}$ convergeert (dimensie $3$ , transient) — de stelling van Pólya is, uiteindelijk, een uitspraak over de divergentie van $\sum n^{-d/2}$ .

21.1 Waarschijnlijkheidsruimten

21.2 Conditionering en onafhankelijkheid

21.3 Het lemma van Borel–Cantelli

21.4 Oefeningen

21.5 Probleem: de eenvoudige toevalswandeling op Z\ZZ is recurrent

21.5 Probleem: de eenvoudige toevalswandeling op $\Z$ is recurrent