Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

21Kansrekening op aftelbare ruimten

De laatste drie hoofdstukken ontwikkelen de moderne kansrekening: kansmaten op aftelbare uitkomstenruimten, discrete toevalsveranderlijken en genererende functies. De eindige theorie van het bovenbouwvolume krijgt haar volledige infrastructuur: $\sigma$ -additiviteit vervangt de eindige additiviteit, en de machinerie van de sommeerbare families uit Hoofdstuk 7 is precies wat oneindige uitkomstenruimten hanteerbaar maakt. De kernresultaten hier zijn de continuïteit van de kans langs monotone rijen gebeurtenissen en het lemma van Borel–Cantelli.

21.1 Kansruimten

Definitie 21.1 (Aftelbare kansruimte)

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

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

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

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

Opmerking 21.2

Op een aftelbare $\Omega$ mogen wij alle deelverzamelingen als gebeurtenissen nemen; op overaftelbare ruimten (zoals nodig voor continue modellen in bachelorjaar 3) kan dat niet meer, en beperkt men $\P$ tot een geschikte collectie gebeurtenissen, een $\sigma$ -algebra. Alle formules van dit hoofdstuk overleven die veralgemening woordelijk.

Propositie 21.3 (Elementaire regels)

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

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

Bewijs. De $\sigma$ -additiviteit toepassen 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 vereniging met lege verzamelingen opvullen geeft dan de eindige additiviteit. De rest volgt als in het eindige geval (bovenbouwvolume): $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 ontbinden in drie disjuncte stukken geeft

\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 de in- en uitsluiting is; de algemene versie met $n$ verzamelingen is Oefening 21.4. ∎

Propositie 21.4 (Verdelingen op een aftelbare ruimte)

Een kansmaat geven op een aftelbare $\Omega = \{\omega_0, \omega_1, \dots\}$ komt precies neer op het geven van gewichten $p_i = \P(\{\omega_i\}) \geq 0$ met $\sum_i p_i = 1$ ; dan is 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 singletons $\{\omega\}$ , $\omega \in A$ , een aftelbare disjuncte overdekking van $A$ , dus dwingt de $\sigma$ -additiviteit af dat

\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 is $\sum_ip_i = \P(\Omega) = 1$ . Omgekeerd, gegeven niet-negatieve gewichten met totale som $1$ , definieer $\P(A) = \sum_{\omega \in A}p_\omega$ : de familie is sommeerbaar, en de $\sigma$ -additiviteit is precies de stelling over sommeren in pakketten uit Hoofdstuk 7, toegepast op de partitie van $\bigcup A_n$ in de $A_n$ . ∎

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

Werp herhaaldelijk met een munt met kanskop $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 kansmaat omdat $\sum_{k\geq1}(1-p)^{k-1}p = \frac{p}{1 - (1-p)} = 1$ : met kans $1$ eindigt het spel — maar de uitkomstenruimte moet toch de mogelijkheid bevatten dat het niet eindigt. De aftelbare additiviteit is wat ons toelaat te beweren dat $\P(\text{het spel eindigt}) = \sum_k \P(\{k\})$ .

Stelling 21.6 (Monotone continuïteit)

Zij $(A_n)$ een rij gebeurtenissen.

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

Bewijs. 1. Maak disjunct: zij $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$ . Volgens de $\sigma$ -additiviteit en de eindige additiviteit is

\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 de complementen: $(A_n^c)$ is stijgend met vereniging $\bigl(\bigcap A_n\bigr)^c$ ; pas deel 1 toe: $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$ . ∎

Gevolg 21.7 (Aftelbare subadditiviteit)

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

Bewijs. De eindige subadditiviteit $\P(A_0 \cup \dots \cup A_N) \leq \sum_0^N \P(A_n)$ volgt met inductie uit de in- en uitsluiting (of uit de additiviteit over de disjunct gemaakte $B_n \subseteq A_n$ ). Laat $N \to \infty$ : het linkerlid convergeert naar $\P(\bigcup_n A_n)$ wegens de monotone continuïteit toegepast op de stijgende rij $C_N = A_0 \cup \dots \cup A_N$ . ∎

Voorbeeld 21.8 (De somgrens: ruw maar onverwoestbaar)

De subadditiviteit met eindig veel gebeurtenissen — de somgrens — ruilt nauwkeurigheid in voor universaliteit. Voor het verjaardagsprobleem met $23$ mensen geeft de kans op een botsing begrenzen door de som over de paren

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

tegenover de werkelijke $0.507$ : er ruim naast, omdat botsingen elkaar overlappen. Toch heeft de grens geen onafhankelijkheid nodig, geen gezamenlijke verdeling, niets dan de kansen op de paren — en daarom is in de weekendopgave en overal in Hoofdstuk 22 de somgrens het eerst getrokken wapen: blijkt zij klein te zijn, dan is de zaak beslecht zonder verdere modellering.

Voorbeeld 21.9 (Een zes komt, uiteindelijk)

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

\P(\text{er verschijnt uiteindelijk 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 de eindige additiviteit, en de monotone continuïteit — dat wil zeggen de $\sigma$ -additiviteit — is precies het axioma dat er een kans aan toekent. Elke uitspraak “bijna zeker” in de rest van dit boek gaat door deze ene smalle deur.

21.2 Voorwaardelijkheid en onafhankelijkheid

Definitie 21.10 (Voorwaardelijke kans)

Voor gebeurtenissen $A, B$ met $\P(B) > 0$ is de voorwaardelijke kans 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 kansmaat op $\Omega$ .

Opmerking 21.11

Dat $A \mapsto \pcond BA$ opnieuw een kansmaat is, verdient een ogenblik: $\pcond B\Omega = 1$ en de $\sigma$ -additiviteit gaan door het quotiënt heen omdat doorsnijden met $B$ disjuncte verenigingen eerbiedigt. Het praktische gevolg: elke identiteit van dit hoofdstuk — in- en uitsluiting, monotone continuïteit, Borel–Cantelli — mag na het voorwaardelijk stellen worden toegepast, zonder nieuwe bewijzen. Kansrekenaars “werken onder $\pcond B{\cdot}$ ” precies om die reden voortdurend.

Voorbeeld 21.12 (Voorwaardelijk stellen kan uniformiteit scheppen)

Gooi met twee eerlijke dobbelstenen en stel voorwaardelijk dat de som $7$ is: voor elke $k \in \intint16$ is

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

gegeven een som van $7$ is de eerste dobbelsteen precies uniform — $7$ is de enige som die met elk aantal ogen verenigbaar is, dus wist het voorwaardelijk stellen alle informatie over $X$ uit. Elke andere som scheeftrekt de verdeling (gegeven $S = 4$ is de eerste dobbelsteen alleen uniform op $\{1, 2, 3\}$ ). Een voorwaardelijke verdeling berekenen betekent de gezamenlijke gewichten langs de voorwaardelijke gebeurtenis hernormaliseren, meer niet.

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

Een urne bevat $3$ witte en $2$ zwarte ballen; trek er twee zonder teruglegging. Iedereen is het erover eens dat $\P(W_1) = \frac35$ ; wat is $\P(W_2)$ ? Totale kans 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: wegens de symmetrie heeft elke bal evenveel kans om als tweede te worden getrokken, dus heeft de tweede trekking — onvoorwaardelijk — dezelfde verdeling als de eerste. Voorwaardelijk stellen op de eerste uitkomst verandert de kansen; haar niet kennen niet. Dit argument met verwisselbaarheid keert in het volgende hoofdstuk terug voor het steekproeven zonder teruglegging, waar het het hypergeometrische gemiddelde $np$ geeft, zonder enige binomiale identiteit.

Stelling 21.14 (Samengestelde kansen, totale kans, Bayes)

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

$\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 kans) Is $(B_i)_{i \in I}$ een eindige of aftelbare partitie van $\Omega$ met $\P(B_i) > 0$ , dan is voor elke gebeurtenis $A$

$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$
(Bayes) Onder dezelfde hypothesen geldt, 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 kans als een quotiënt: het rechterlid 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 voorgaande teller op, en $\P(A_1 \cap \dots \cap A_n)$ blijft over. Alle noemers zijn $\geq \P(A_1 \cap \dots \cap A_{n-1}) > 0$ wegens de monotonie, dus verdwijnt er niets. (De hypothese bewaakt precies dit: voorwaardelijk stellen op een gebeurtenis met kans nul is niet gedefinieerd.) 2. De verzamelingen $A \cap B_i$ zijn paarsgewijs disjunct met vereniging $A$ ; pas de ( $\sigma$ -)additiviteit en de definitie van het voorwaardelijk stellen toe. 3. Beide leden 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 werk $\P(A)$ uit met de totale kans. ∎

Voorbeeld 21.15 (De verjaardagsbotsing, met de kettingregel)

Met $n$ mensen wier verjaardagen onafhankelijk en uniform over $365$ dagen verdeeld zijn, zij $D_n = {}$ “alle $n$ verjaardagen verschillen”. Persoon voor persoon voorwaardelijk stellen (kettingregel) geeft

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

waarbij elke nieuwe persoon de $k$ reeds bezette dagen moet 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 nemen geeft $-\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, met Bayes)

Achter een van drie deuren zit uniform verdeeld een prijs. Je kiest deur $1$ ; de presentator, die weet waar de prijs is, opent een van de andere deuren, altijd een lege (uniform kiezend wanneer hij de keuze heeft), zeg deur $3$ . Zij $B_i = {}$ “prijs achter deur $i$ ” en $A = {}$ “de presentator opent deur $3$ ”. Dan is $\pcond{B_1}{A} = \frac12$ , $\pcond{B_2}{A} = 1$ en $\pcond{B_3}{A} = 0$ , dus geeft Bayes (Stelling 21.14)

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

van deur wisselen wint twee keer op drie. 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 boekhoudkundige hulpmiddel dat die asymmetrie in de $\frac23$ omzet. Voorwaardelijk stellen op “wat werd gezien” 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 weddenschappen uit de zeventiende eeuw, 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 dubbele 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}$ zouden moeten overeenkomen met $4$ worpen met kans $\frac16$ (dezelfde verhouding $\frac{24}{36} = \frac46$ ); het falen van deze evenredigheid — kansen op verenigingen schalen niet lineair — zou zijn brief aan Pascal hebben uitgelokt, en daarmee de geboorte van de kansrekening. De juiste vergelijking gaat via logaritmen: $n$ pogingen met kans $p$ slagen minstens eenmaal met kans $1 - (1-p)^n \approx 1 - \eu^{-np}$ , dus is de eerlijke invariant $np$ : hier $4\cdot\frac16 = \frac23$ tegenover $24\cdot\frac1{36} = \frac23$ — gelijk! De twee weddenschappen verschillen pas op de tweede orde in $p$ , en net genoeg om er één over de vijftig-procent lijn te duwen: kleine kansen vormen een gebied waar de intuïtie de exponentiële functie nodig heeft, niet de liniaal.

Opmerking 21.18 (Klassieke drogredenen bij het voorwaardelijk stellen)

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\%$ nauwkeurig 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}}$ noemen waar $\pcond{\text{positief}}{ \text{ziek}}$ wordt bedoeld, is de drogreden van het basispercentage. (ii) Voorwaardelijk stellen op de verkeerde gebeurtenis: bij Monty Hall is de juiste voorwaardelijke gebeurtenis “de presentator opende deur $3$ ”, niet “de prijs zit niet achter deur $3$ ”; die twee dragen verschillende informatie, en de hele $\frac23$ hangt van het verschil af. (iii) Disjunct tegenover onafhankelijk: disjuncte gebeurtenissen met positieve kans zijn nooit onafhankelijk ( $\P(A\cap B) = 0 \neq \P(A)\P(B)$ ) — onafhankelijkheid is verenigbaarheid van informatie, niet afwezigheid van overlap.

Definitie 21.19 (Onafhankelijkheid)

Gebeurtenissen $A$ en $B$ heten onafhankelijk wanneer $\P(A \cap B) = \P(A)\P(B)$ . Een familie $(A_i)_{i \in I}$ gebeurtenissen heet (onderling) onafhankelijk wanneer voor elke eindige deelverzameling $J \subseteq I$ geldt

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

Opmerking 21.20

Onderlinge onafhankelijkheid is strikt sterker dan paarsgewijze onafhankelijkheid: bij twee eerlijke muntworpen zijn de gebeurtenissen “de eerste is kop”, “de tweede is kop” en “beide stemmen overeen” paarsgewijs onafhankelijk (elk paar heeft doorsnedekans $\frac14 = \frac12\cdot\frac12$ ), en toch heeft de drievoudige doorsnede kans $\frac14 \neq \frac18$ . Merk ook op dat als $A, B$ onafhankelijk zijn, ook $A, B^c$ dat zijn (reken na: $\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 met twee eerlijke dobbelstenen: $\Omega = \intint16^2$ met uniforme gewichten. Zij $A = {}$ “eerste dobbelsteen even” en $B = {}$ “tweede dobbelsteen 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$ legt alleen de eerste coördinaat vast, $B$ alleen de tweede, en de uniforme maat op een productverzameling laat de coördinaattellingen vermenigvuldigen. Elke bewering van het type “gebeurtenissen die van disjuncte groepen worpen afhangen, zijn onafhankelijk” (massaal gebruikt in de weekendopgave) is deze berekening, met meer indices.

Voorbeeld 21.22 (Analyse van de eerste stap)

Wat is voor het meetkundige model van Voorbeeld 21.5 de kans $u$ dat de eerste kop op een even rang valt? Stel voorwaardelijk op de eerste worp: met kans $p$ is de rang $1$ (oneven); met kans $q = 1 - p$ begint het spel opnieuw met alle pariteiten omgekeerd, dus

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

Eén regel, geen reeks — en het stemt overeen met de rechtstreekse sommatie van Oefening 21.9, die $1 - u = \frac1{1+q}$ geeft. Deze techniek van de “eerste stap” (voorwaardelijk stellen op het eerste experiment, en een verschoven kopie van het probleem herkennen) is de kansrekenkundige vorm van een recursie, en zij is de motor achter de vergelijkingen voor de speelduur van Oefening 21.6 en de berekeningen van de eerste doorgang in de weekendopgave.

21.3 Het lemma van Borel–Cantelli

Definitie 21.23 (Limes superior van gebeurtenissen)

Voor een rij $(A_n)$ 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” vertaald)

Het complement van $\limsup_nA_n$ is volgens 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 zijn “ $A_n$ oneindig vaak” en “ $A_n^c$ uiteindelijk” complementair — dit woordenboek recht houden voorkomt de meeste ongelukken met kwantoren. Voorbeeldvertalingen voor het muntwerpen: “oneindig veel kop” is $\limsup\{X_n = H\}$ ; “slechts eindig veel reeksen van $100$ maal 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\}$ — overal aftelbare bewerkingen, zodat dit alle eerlijke gebeurtenissen zijn.

Stelling 21.25 (Borel–Cantelli)

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

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

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

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

2. Het volstaat aan te tonen dat $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ voor elke $N$ : hebben immers gebeurtenissen $B_N$ alle kans $1$ , dan is

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

wegens de aftelbare subadditiviteit (Gevolg 21.7), zodat de aftelbare doorsnede $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ nog altijd kans $1$ heeft. Houd $N$ vast 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 de onafhankelijkheid van de complementen en de convexiteitsgrens $1 - x \leq e^{-x}$ . Als $M \to \infty$ streeft de exponent naar $-\infty$ wegens de divergentie van de reeks, dus geeft de monotone continuïteit (dalende rij) dat $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$ , dat wil zeggen $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$ . ∎

Voorbeeld 21.26 (Oneindige reeksen kop)

Werp eeuwig met een eerlijke munt, en zij $A_n$ de gebeurtenis “de worpen $n, n+1, \dots, n + k - 1$ zijn alle kop” (een reeks van $k$ maal kop die op tijdstip $n$ begint), voor vaste $k$ . De gebeurtenissen $A_{jk}$ ( $j = 1, 2, \dots$ ), die van disjuncte blokken worpen afhangen, zijn onafhankelijk, elk met kans $2^{-k}$ , en $\sum_j 2^{-k} = \infty$ : volgens Borel–Cantelli 2 zijn met kans $1$ oneindig veel blokken volledig kop — elk vast patroon keert bijna zeker oneindig vaak terug. Laten wij omgekeerd de lengte van de reeks groeien, dan heeft $B_n = {}$ “een reeks van $2\log_2 n$ maal kop begint in $n$ ” de kans $\P(B_n) = n^{-2}$ , sommeerbaar, dus beginnen er bijna zeker slechts eindig veel van zulke lange reeksen: Borel–Cantelli ijkt precies hoe lang de langste reeksen zijn.

Voorbeeld 21.27 (De oneindige aap, gekwantificeerd)

Een aap typt onafhankelijke uniforme letters uit een alfabet van $26$ letters. Snijd het typoscript 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$ : volgens Borel–Cantelli 2 typt de aap bijna zeker oneindig vaak MATH — en hetzelfde geldt voor elke vaste tekst van elke lengte, met aangepaste blokken. De kwantitatieve voetnoot ontnuchtert het wonder: $26^4 = 456\,976$ , dus vergt de eerste MATH gemiddeld ongeveer een half miljoen aanslagen, en een toneelstuk van Shakespeare met $10^5$ tekens wacht op de orde van $26^{10^5}$ blokken — bijna zeker is een uitspraak over de horizon $\infty$ , niet over enige horizon die een aap zal ontmoeten. Borel–Cantelli bevestigt de limiet; de grootte van de termen vertelt het verhaal op menselijke schaal.

Opmerking 21.28

In Voorbeeld 21.26 is de onderliggende uitkomstenruimte (oneindige rijen worpen) overaftelbaar, dus leeft het voorbeeld strikt genomen in het maattheoretische kader van bachelorjaar 3; de berekeningen gebruiken echter alleen de regels die in dit hoofdstuk zijn bewezen, toegepast op gebeurtenissen die door eindig veel worpen worden bepaald en op hun aftelbare combinaties. Dat is de gebruikelijke afspraak op dit niveau: de theorie wordt op aftelbare ruimten geformuleerd, en voorbeelden met oneindige spelen worden met hetzelfde gereedschap behandeld.

Opmerking 21.29 (Vooruitblik binnen dit volume)

De machinerie van dit hoofdstuk wordt door de volgende twee in haar geheel verbruikt. Indicatoren maken van gebeurtenissen toevalsveranderlijken, en de $\sigma$ -additiviteit wordt de sommeerbaarheid die de verwachtingswaarde definieert (Hoofdstuk 22); Borel–Cantelli plus een sommeerbare staartgrens is precies hoe de sterke wet van de grote aantallen voor munten daar wordt bewezen. In Hoofdstuk 23 duikt de monotone continuïteit op het beslissende ogenblik weer op: de uitstervingskans van een vertakkingsproces wordt gedefinieerd als de monotone limiet $\lim\P(Z_n = 0)$ , en de vastepuntsvergelijking waaraan zij voldoet, wordt verkregen door in die stijgende rij naar de limiet over te gaan — de laatste stelling van het boek staat op de eerste stelling van dit hoofdstuk.

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

Uitspraken “bijna zeker” worden met drie hefbomen bewezen, in stijgende volgorde van kracht. Monotone continuïteit: geef de gebeurtenis als een stijgende vereniging (of dalende doorsnede) van gebeurtenissen met eindige horizon en berekenbare kansen (Voorbeeld 21.9). Nulverenigingen: een aftelbare vereniging van gebeurtenissen met kans nul is nul (aftelbare subadditiviteit), dus volstaat het elke slechte gebeurtenis afzonderlijk te doden — zo voegt “voor elke $j$ is uiteindelijk $\abs{\widehat p_n - p} < 1/j$ ” zich samen tot convergentie. Borel–Cantelli: is de gebeurtenis een limsup, sommeer dan de kansen; convergentie doodt haar (zonder onafhankelijkheid nodig te hebben), en divergentie plus onafhankelijkheid bevestigt haar. De juiste hefboom kiezen is meestal het hele bewijs; de weekendopgave laat alle drie in één argument lopen.

Opmerking 21.31 (Waar dit wordt gebruikt)

De monotone continuïteit en Borel–Cantelli zijn de twee hefbomen van elke uitspraak “bijna zeker”: zij drijven de recurrentie van de toevalswandeling in de weekendopgave van dit hoofdstuk aan, de bijna-zekere kant van de wet van de grote aantallen (Hoofdstuk 22) en de analyse van het uitsterven van vertakkingsprocessen (Hoofdstuk 23). Het volume van bachelorjaar 3 bouwt de theorie opnieuw op met $\sigma$ -algebra’s en de integraal van Lebesgue, waar de overaftelbare uitkomstenruimten die hier informeel worden gebruikt, volledig streng worden.

21.4 Oefeningen

Oefening 21.1 ★

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

Oplossing

Oplossing van Oefening 21.1.

Wegens de symmetrie: de trekvolgorde brengt een uniform willekeurige onderlinge volgorde op de ballen $1$ en $2$ voort, dus $\P(1 \text{ vóór } 2) = \frac12$ . Formeel: de posities van de ballen $1$ en $2$ in een trekrij verwisselen is een bijectie van de (even waarschijnlijke) uitkomsten die de gebeurtenis met haar complement verwisselt. Onder de ballen $1, \dots, k$ : de onderlinge volgorde van deze $k$ ballen is uniform over de $k!$ rangschikkingen, en bal $1$ staat in $(k-1)!$ daarvan vooraan: kans $\frac{(k-1)!}{k!} = \frac1k$ .

Oefening 21.2 ★

Toon aan dat de gewichten $p_k = \frac{1}{k(k+1)}$ op $\Omega = \N^*$ een kansmaat definiëren, en bereken $\P(2\N^*)$ (even uitkomsten) als reeks; toon aan dat zij gelijk is aan $1 - \ln 2$ . (Telescopeer $\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 telescopeert $\sum_{k\geq1} p_k$ tot $1$ : een kansmaat. 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 zonder haar eerste term en met omgekeerde tekens: omdat $\ln 2 = 1 - \frac12 + \frac13 - \frac14 + \cdots$ (Hoofdstuk 7), is

\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 spoort haar met kans $0.99$ op bij de zieken, en geeft met kans $0.01$ een vals-positief bij de gezonden. Bereken de kans ziek te zijn gegeven een positieve test, en geef commentaar.

Oplossing

Oplossing van Oefening 21.3.

Zij $S$ = ziek en $+$ = 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\%$ nauwkeurig” is, laat een positieve uitslag je met ongeveer $99\%$ kans gezond: de vals-positieven onder de enorme gezonde meerderheid overspoelen de echte positieven uit de piepkleine zieke minderheid. Screeningtests voor zeldzame aandoeningen moeten altijd door deze berekening met het basispercentage worden gelezen.

Oefening 21.4 ★★

Zijn $A_1, \dots, A_n$ gebeurtenissen. Bewijs de formule van de in- en uitsluiting

\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 (dat wil zeggen: te sommeren met gewichten $\P(\{\omega\})$ ).

Oplossing

Oplossing van Oefening 21.4.

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

\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 uit te werken en de $1$ over te brengen. Nu is $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J} A_i}$ , en sommeren tegen de gewichten $\P(\{\omega\})$ — geoorloofd: eindig veel begrensde termen, elke familie sommeerbaar — maakt van elke indicator de kans op haar gebeurtenis, wat de formule geeft.

Oefening 21.5 ★★

(Het probleem van de overeenkomsten, via in- en uitsluiting) $n$ brieven worden uniform willekeurig in $n$ enveloppen gestopt, één per envelop. Toon met Oefening 21.4 aan dat de kans op geen enkele juiste overeenkomst gelijk is aan $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$ , en leid de kans op precies één overeenkomst af.

Oplossing

Oplossing van Oefening 21.5.

Zij $A_i$ = “brief $i$ zit in de juiste envelop”. Voor $J$ van grootte $k$ is $\P\bigl(\bigcap_{i\in J}A_i\bigr) = \frac{(n-k)!}{n!}$ (leg $k$ brieven vast, permuteer de rest). Volgens de in- en uitsluiting is

\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 overeenkomst}) = 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 overeenkomst: een permutatie met precies één vast punt wordt bepaald door de keuze van de vaste brief ( $n$ manieren) en een derangement (rangschikking zonder overeenkomst) van de andere $n - 1$ ; schrijven wij $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ voor het aantal derangementen (het eerste deel, met $(n-1)!$ geschaald), dan is

\P(\text{precies één overeenkomst}) = \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 overeenkomst” en “precies één overeenkomst” even waarschijnlijk, elk met kans $e^{-1}$ .

Oefening 21.6 ★★

Met een scheve munt (kanskop $p \in \intoo{0}{1}$ ) wordt geworpen tot er tweemaal achter elkaar kop verschijnt. Zij $q_n$ de kans dat het spel langer dan $n$ worpen duurt. Toon, door voorwaardelijk te stellen op de eerste worp(en), aan dat $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ voor $n \geq 2$ , en leid af dat het spel met kans $1$ eindigt. (Toon $q_n \to 0$ aan door met een meetkundige rij te vergelijken: beide nulpunten van de karakteristieke vergelijking hebben absolute waarde in $\intoo{0}{1}$ .)

Oplossing

Oplossing van Oefening 21.6.

Stel voorwaardelijk op het begin (kettingregel / Stelling 21.14):

eerste worp M (kans $1 - p$ ): het spel begint opnieuw; langer duren dan $n$ betekent van daar af langer duren dan $n - 1$ : bijdrage $(1-p)\,q_{n-1}$ ;
eerste worpen KM (kans $p(1-p)$ ): opnieuw beginnen na twee worpen: bijdrage $p(1-p)\,q_{n-2}$ ;
eerste worpen KK: het spel is geëindigd (binnen $n$ worpen, $n \geq 2$ ): bijdrage $0$ .

Bijgevolg is $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 nulpunten

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

met $\abs{r_\pm} < 1$ : inderdaad voldoet de veelterm $\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 nulpunt in $\intoo{-1}{0}$ , één in $\intoo{0}{1}$ . Dus $q_n = \alpha r_+^n + \beta r_-^n \to 0$ . De gebeurtenissen “het spel duurt langer dan $n$ ” dalen naar “het spel eindigt nooit”; de 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 onderlinge volgorde van de eerste $n$ trekkingen uniform over de $n!$ mogelijkheden, en $R_n = {}$ “de $n$ -de trekking is een record (groter dan alle vorige)”. Aangenomen dat de gebeurtenissen $R_n$ onafhankelijk zijn met $\P(R_n) = 1/n$ (bewijs minstens deze laatste gelijkheid met de symmetrie), toon met Borel–Cantelli aan dat er bijna zeker oneindig veel records optreden, maar dat records op opeenvolgende tijdstippen $n, n+1$ oneindig vaak optreden met kans — bereken $\sum_n \P(R_n \cap R_{n+1})$ en besluit 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$ onderlinge posities van de laatste trekking even waarschijnlijk (uniformiteit van de onderlinge volgorde), en $R_n$ is de gebeurtenis dat zij de grootste is: kans $1/n$ .

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

Opeenvolgende records: wegens de onafhankelijkheid is

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

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

Oefening 21.8 ★★★

(In de stijl van Kochen–Stone, eenvoudiger versie) Zij $(A_n)$ een rij onafhankelijke gebeurtenissen met $\P(A_n) = \frac{1}{n+1}$ . Toon aan dat $\P(\limsup A_n) = 1$ , hoewel $\P(A_n) \to 0$ : “afzonderlijk zeldzaam, samen zeker”. Geef omgekeerd een rij (afhankelijke) gebeurtenissen met $\sum\P(A_n) = \infty$ en $\P(\limsup A_n) = 0$ , wat aantoont dat de onafhankelijkheid in Borel–Cantelli 2 niet mag vervallen.

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 afzonderlijke $A_n$ is steeds onwaarschijnlijker, en 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 is

\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$ . De divergentie van $\sum\P(A_n)$ alleen waarborgt niets wanneer de gebeurtenissen zich op een krimpend deel van de ruimte opstapelen — de onafhankelijkheid is wat die samenzwering verbiedt.

Oefening 21.9 ★

Met een munt met kanskop $p \in \intoo01$ wordt geworpen tot de eerste kop. Bereken de kans dat dit op een oneven rang gebeurt, en evalueer haar voor een eerlijke munt.

Oplossing

Oplossing van Oefening 21.9.

Met $q = 1 - p$ valt de eerste kop op rang $2j + 1$ met kans $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$ . (Verstandscontrole: oneven rangen moeten waarschijnlijker zijn, want rang $1$ komt als eerste — en inderdaad is $\frac1{1+q} > \frac12$ altijd.)

Oefening 21.10 ★★

Zij $(A_n)_{n\geq1}$ een rij onafhankelijke gebeurtenissen met $\P(A_n) = p_n < 1$ . Toon aan 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$ . Breng dit in overeenstemming met Borel–Cantelli: is $\sum p_n = \infty$ , dan treedt niet alleen een zekere $A_n$ bijna zeker op — er treden er oneindig veel op.

Oplossing

Oplossing van Oefening 21.10.

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

Oefening 21.11 ★★

(De luciferdoosjes van Banach) Een roker houdt in elke zak een doosje met $n$ lucifers en grijpt telkens in een uniform willekeurige zak. Wanneer hij voor het eerst een doosje leeg aantreft, wat is dan de kans dat het andere doosje precies $k$ lucifers bevat? Toon aan dat het antwoord $\binom{2n-k}{n}2^{-(2n-k)}$ is en ga na dat deze kansen voor $n = 1$ tot $1$ sommeren.

Oplossing

Oplossing van Oefening 21.11.

Zeg dat doosje $A$ het doosje is dat het eerst leeg wordt aangetroffen, terwijl het andere er $k$ bevat. Dat betekent: onder de eerste $2n - k$ grepen gingen er precies $n$ naar $A$ en $n - k$ naar $B$ (in een zekere volgorde), en greep nummer $2n - k + 1$ ging opnieuw naar $A$ , dat leeg bleek. De grepen zijn onafhankelijke eerlijke keuzes, dus heeft deze gebeurtenis kans $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$ ; verdubbelen (het lege doosje kan er een van beide zijn) geeft

\P(\text{het andere doosje bevat }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$ : samen $1$ , zoals het moet.

Oefening 21.12 ★★★

( $\sigma$ -additiviteit is een echt axioma) (a) Toon aan dat er geen kansmaat op $(\N, \mathcal P(\N))$ bestaat die aan alle singletons hetzelfde gewicht geeft. (b) Zij voor $A \subseteq \N^*$ de grootheid $d(A) = \lim_n\frac{\abs{A\cap\intint1n}}{n}$ wanneer de limiet bestaat (de natuurlijke dichtheid). Toon aan dat $d$ eindig additief is op paren waarvoor alle drie de dichtheden bestaan, dat zij aan elk singleton dichtheid $0$ en aan $\N^*$ dichtheid $1$ geeft — en besluit dat $d$ niet $\sigma$ -additief is. (c) Geef een verzameling zonder dichtheid. (Neem de blokken $\intint{2^{2k}}{2^{2k+1}-1}$ afwisselend wel en niet mee.)

Oplossing

Oplossing van Oefening 21.12.

(a) Is $\P(\{n\}) = c$ voor alle $n$ , dan dwingt de $\sigma$ -additiviteit $1 = \sum_nc$ af: onmogelijk, of $c = 0$ is (som $0$ ) of $c > 0$ (som oneindig). Er bestaat geen uniforme kans op $\N$ .

(b) Is $A \cap B = \emptyset$ en bestaan $d(A)$ en $d(B)$ , dan is $\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. Elk singleton heeft een telfunctie die uiteindelijk constant is, en dus dichtheid $0$ , terwijl $d(\N^*) = 1$ . Was $d$ $\sigma$ -additief, dan zou $\N^* = \bigsqcup_k\{k\}$ geven dat $1 = \sum_k 0 = 0$ : de dichtheid is eindig additief maar niet $\sigma$ -additief — het axioma heeft inhoud.

(c) Zij $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (blokken van $4^k$ tot $2\cdot4^k - 1$ ). In $n = 2\cdot4^K - 1$ is de telling $\sum_{k\leq K}4^k \sim \frac43 4^K$ , wat een verhouding $\to \frac23$ geeft; in $n = 4^{K+1} - 1$ is de telling onveranderd, wat een verhouding $\to \frac13$ geeft. De verhouding oscilleert tussen de 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 terugkeren naar de oorsprong. De opgave toont dat deze stippen met kans 1 nooit ophouden te verschijnen — en toch heeft de wachttijd ertussen een divergent gemiddelde. — Vierentwintig stappen van een eenvoudige toevalswandeling; de rode stippen markeren de terugkeren naar de oorsprong. De opgave toont dat deze stippen met kans $1$ nooit ophouden te verschijnen — en toch heeft de wachttijd ertussen een divergent gemiddelde.

Probleem 21.1

Weekendopgave — de recurrentiestelling van Pólya op $\Z$ , met onderweg het stemmenprobleem en een vleugje arcsinus

Werp eeuwig met een eerlijke munt; zij $X_i = \pm1$ de $i$ -de stap en $S_n = X_1 + \dots + X_n$ de eenvoudige toevalswandeling op $\Z$ , met $S_0 = 0$ . Zoals in Voorbeeld 21.26 worden alle gebeurtenissen hieronder door eindig veel worpen bepaald of zijn zij aftelbare combinaties van zulke gebeurtenissen, en de onafhankelijkheid van gebeurtenissen die van disjuncte blokken worpen afhangen, hoort bij het model. Wij 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 aan dat $N_n(k) = \binom{n}{(n+k)/2}$ wanneer $n + k$ even is en $\abs k \leq n$ , en $0$ anders; leid af dat $\P(S_n = k) = N_n(k)\,2^{-n}$ . Waarom is elk afzonderlijk pad van lengte $n$ even waarschijnlijk?
Toon aan dat $S_{2n+1} \neq 0$ en $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{zodat}\qquad \sum_n u_n = \infty .$
(Spiegelingsprincipe) Toon voor $k \geq 1$ aan 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$ dat na tijdstip $0$ boven $0$ blijft, gelijk is aan $N_{n-1}(k-1) - N_{n-1}(k+1)$ .
(Stemmenstelling) 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 waarin de winnaar met $k$ van de $n$ stemmen voorstaat, is de kans dat hij gedurende de hele telling voorstond gelijk aan $k/n$ . Ga dit met de hand na 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$

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

$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1}, \qquad \sum_{n\geq1}f_n = 1 .$
Toon aan 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 een oneindige verwachtingswaarde).
Bewijs dat voor elke $k \geq 1$ geldt $\P(\text{minstens } k\text{ terugkeren naar }0) = 1$ (ontbind over de tijdstippen van de eerste $k$ terugkeren: de bijbehorende blokken worpen zijn disjunct, dus vermenigvuldigen de kansen en sommeren zij tot $(\sum_nf_n)^k$ ); besluit met de monotone continuïteit:

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

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

Deel III — Borel–Cantelli en de scheve 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. (Dat is de strategie van het hele deel.)
Laat de munt nu een scheefheid $p \neq \frac12$ hebben, $q = 1 - p$ . Toon aan dat $\P(S_{2n} = 0) = \binom{2n}n(pq)^n = u_n\,(4pq)^n$ met $4pq < 1$ , leid af dat $\sum_n\P(S_{2n} = 0) < \infty$ , en besluit met Borel–Cantelli 1 dat de scheve wandeling bijna zeker slechts eindig vaak naar $0$ terugkeert.
Nog steeds voor $p \neq \frac12$ : toon aan dat $\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 wordt bezocht, en besluit dat $\abs{S_n} \to \infty$ bijna zeker: de scheve wandeling is transiënt.
Terug naar de eerlijke munt: bereken met vraag 6 de kans dat $200$ worpen geen enkele gelijkstand opleveren ( $S_n \neq 0$ voor $1 \leq n \leq 200$ ), numeriek $u_{100} \approx 0.056$ . Geef commentaar op het trage verval $1/\sqrt{\pi n}$ : gelijkstanden zijn op de lange duur zeker, maar zeldzamer dan de intuïtie doet vermoeden.
(Eerste doorgang) Zij $T_1$ het eerste tijdstip waarop de wandeling $1$ raakt. Toon met het spiegelingsprincipe voor het maximum $M_n = \max_{i\leq n}S_i$ (bewezen in vraag 16, die niet van deze afhangt), of rechtstreeks uit vraag 7 door voorwaardelijk op de eerste stap te stellen, aan dat $\P(T_1 = 2n - 1) = f_n$ ; leid af dat $\P(T_1 < \infty) = 1$ , terwijl de reeks $\sum(2n-1)f_n$ voor de gemiddelde tijd divergeert.

Deel IV — Maxima, laatste nulpunt, lange voorsprongen.

(Spiegeling voor het maximum) Bewijs voor $k \geq 1$ dat

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

door het pad na zijn eerste bezoek aan niveau $k$ te spiegelen.
Leid af dat $\P(M_{2n} \geq 1) = 1 - u_n$ , dat wil zeggen $\P(S_i \leq 0 \text{ voor alle } i \leq 2n) = u_n$ : de kans om nooit voor te staan is gelijk aan de kans om nooit op nul te zijn (vraag 6) — twee verschillende gebeurtenissen, één kans.
(Laatste nulpunt) Zij $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (even). Toon, door vraag 6 met de onafhankelijkheid van disjuncte blokken worpen te combineren, aan dat

$\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 aan dat de verdeling van $L_{2n}$ symmetrisch is ( $\P(L = 2k) = \P(L = 2n - 2k)$ ) en, met $u_j \sim 1/\sqrt{\pi j}$ , dat haar uitersten haar meest waarschijnlijke waarden zijn. Zet dit voor $n = 5$ in een tabel: $\P(L_{10} = 0) = u_5 \approx 0.246$ tegenover $\P(L_{10} = 4) = u_2u_3 \approx 0.117$ . Interpreteer: in een lang eerlijk spel valt de laatste gelijkstand meestal heel vroeg of heel laat — lange voorsprongen zijn de regel, niet de uitzondering.
Zet de vragen 16–19 in elkaar tot een alinea over het beeld van de fluctuaties van de eerlijke wandeling: de diffusieve schaal die vraag 3 suggereert, de zekerheid van de terugkeer tegenover de divergente gemiddelde wachttijd, en de volharding van voorsprongen met haar arcsinusaroma.

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

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

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

waarbij $U(x) = \sum_{n\geq0}u_nx^n$ en $F(x) = \sum_{n\geq1}f_nx^n$ (verantwoord de stralen en het product van de reeksen met Hoofdstuk 11).
Leid de recurrentietweedeling af: met $x \to 1^-$ (monotone limieten van reeksen met niet-negatieve coëfficiënten) is

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

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

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

en besluit met de vragen 21–22 (waarvan de bewijzen woordelijk overgaan) dat de wandeling op $\Z^2$ recurrent is.
(Dimensie $3$ ) Neem voor de eenvoudige wandeling op $\Z^3$ de lokale schatting $\P(S^{(3)}_{2n} = 0) \leq C\,n^{-3/2}$ aan (bewezen met de lokale limietstelling in het volume van bachelorjaar 3). Leid met Borel–Cantelli 1 af dat de wandeling op $\Z^3$ transiënt is, en formuleer het volledige resultaat: de stelling van Pólya — de eenvoudige toevalswandeling is recurrent in de dimensies $1$ en $2$ , en transiënt in dimensie $3$ en hoger.
Synthese. Som de exacte rol op van: het tellen van paden en de spiegeling; de monotone continuïteit; de onafhankelijkheid van disjuncte blokken worpen; Borel–Cantelli 1; de vernieuwingsidentiteit. Welk enkel analytisch feit ( $u_n \sim 1/\sqrt{\pi n}$ , dus $\sum u_n = \infty$ maar ook $\sum u_n^2 = \infty$ en $\sum n^{-3/2} < \infty$ ) beslist in elke dimensie tussen recurrentie en transiëntie?

Oplossing

Oplossing van Probleem 21.1.

1. Een pad van lengte $n$ wordt bepaald door de verzameling van zijn opwaartse stappen; in $k$ eindigen betekent $u$ opwaartse en $n - u$ neerwaartse stappen met $u - (n - u) = k$ , dat wil zeggen $u = \frac{n+k}2$ : mogelijk dan en slechts dan als $n + k$ even is en $\abs k \leq n$ , en wel op $\binom{n}{(n+k)/2}$ manieren. Elk specifiek pad is één punt van de eerlijke productmaat op $n$ worpen: kans $2^{-n}$ . Bijgevolg is $\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. Volgens Voorbeeld 6.14 is $\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, spiegel je zijn beginstuk (tot aan het eerste bezoek aan $0$ ) in de horizontale as: het resultaat is een pad van $-1$ naar $k$ , en de bewerking is een involutie — elk pad van $-1$ naar $k \geq 1$ moet $0$ kruisen, en zijn beginstuk terugspiegelen geeft het oorspronkelijke terug. Bijgevolg zijn er $N_{n-1}(k + 1)$ paden die raken (van $-1$ naar $k$ is de verplaatsing $k + 1$ ). Een pad van $0$ naar $k$ dat na tijdstip $0$ boven $0$ blijft, begint met een opwaartse stap en gaat dan in $n - 1$ stappen van $1$ naar $k$ zonder $0$ te raken: daarvan zijn er $N_{n-1}(k-1) - N_{n-1}(k+1)$ .

5. Met $m = \frac{n+k}2$ en $\binom{n-1}{m-1} = \frac mn\binom nm$ , $\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 op tijdstip $2$ naar $0$ terug): één op drie, en $\frac kn = \frac13$ .

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

\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 is $N_{2n-1}(1) = \binom{2n-1}{n}$ en $2\binom{2n-1}n = \binom{2n}n$ (Pascal), dus is de getoonde kans $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 als doorsnede “nooit een terugkeer”; volgens de monotone continuïteit en vraag 6 is $\P(\text{geen terugkeer}) = \lim u_n = 0$ : de wandeling keert bijna zeker terug. Bovendien is $f_n = \P(D_{n-1}) - \P(D_n) = u_{n-1} - u_n$ , en volgens 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 nulrecurrent, in de woordenschat die Hoofdstuk 22 zal leveren.

9. De gebeurtenis “minstens $k$ terugkeren” is de disjuncte aftelbare vereniging, over $0 < n_1 < \dots < n_k$ , van de gebeurtenissen “de eerste $k$ terugkeren gebeuren precies op de tijdstippen $2n_1, \dots, 2n_k$ ”. Zulk een gebeurtenis is de doorsnede van $k$ gebeurtenissen die van de disjuncte blokken worpen $\intint1{2n_1}$ , $\intint{2n_1+1}{2n_2}$ , …afhangen, waarbij elk blok van een verse wandeling vraagt dat zij haar eerste terugkeer precies na het toegemeten aantal stappen maakt; wegens de onafhankelijkheid van de blokken is haar kans $f_{n_1}f_{n_2-n_1}\cdots f_{n_k-n_{k-1}}$ . Sommeren in pakketten (Hoofdstuk 7, alle termen niet-negatief) geeft

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

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

10. Volgens vraag 9 maakt de wandeling oneindig veel uitstapjes weg van $0$ . De eerste stap van elk uitstapje is een verse munt, onafhankelijk van alles ervoor: de kans dat de eerste $m$ uitstapjes alle neerwaarts beginnen, is $2^{-m}$ . Om $1$ te bereiken heeft de wandeling maar één opwaarts beginnend uitstapje nodig (vanuit $<0$ moet zij door $0$ voordat zij $1$ bereikt, want de stappen zijn $\pm1$ ), dus is $\P(\text{nooit }1\text{ raken}) \leq 2^{-m}$ voor elke $m$ : de wandeling raakt $1$ bijna zeker. Ontbinden we over de (bijna zeker eindige) raaktijd, dan is de daar herstarte wandeling een verse wandeling die in $1$ begint: met inductie raakt zij bijna zeker elke $k \geq 1$ , en wegens de symmetrie elke $k \leq -1$ . Herstarten wij ten slotte bij het eerste bezoek aan $k$ , dan is vraag 9 van toepassing op de verse wandeling: elke plaats wordt bijna zeker oneindig vaak bezocht.

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

12. Een terugkeer op tijdstip $2n$ vergt $n$ opwaartse en $n$ neerwaartse stappen: $\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 meetkundige $\sum(4pq)^n$ : convergent. Volgens Borel–Cantelli 1 is $\P(S_{2n} = 0 \text{ oneindig vaak}) = 0$ : bijna zeker eindig veel terugkeren.

13. Voor $n + k$ even is $\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 hoogstens 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 bijna zeker eindig vaak bezocht; de vereniging over $k \in \Z$ van de uitzonderlijke nulgebeurtenissen is nog altijd nul (aftelbare subadditiviteit). Bijna zeker wordt elke plaats eindig vaak bezocht, dus verlaat de rij gehele getallen $(S_n)$ elk begrensd venster voorgoed: $\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 kans op twintig dat $200$ eerlijke worpen nooit een gelijkstand geven. Het verval $1/\sqrt{\pi n}$ is tergend traag: de zekerheid van een gelijkstand (vraag 7) is verenigbaar met heel lange stukken zonder gelijkstand — een eerste voorproefje van de arcsinusverschijnselen van Deel IV.

15. Stel voorwaardelijk op de eerste stap. Is $X_1 = +1$ , dan is $T_1 = 1$ , en $f_1 = \frac12$ klopt. Is $X_1 = -1$ , dan moet de wandeling van $-1$ naar $1$ klimmen; volgens de ontbinding in blokken splitst een eerste terugkeer naar $0$ op tijdstip $2n$ als: één stap omlaag, en dan een verse wandeling die vanuit $-1$ voor het eerst $0$ bereikt — gelijkwaardig: een verse wandeling die voor het eerst $+1$ bereikt — in $2n - 1$ stappen, of de symmetrische gebeurtenis omhoog. Beide tekens dragen evenveel bij:

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

Bijgevolg is $\P(T_1 < \infty) = \sum f_n = 1$ , terwijl $\sum_n(2n - 1)f_n = \sum_n u_n = \infty$ volgens 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$ spiegel je 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 dat in $2k - m > k$ eindigt, bezoekt $k$ ; terugspiegelen is de inverse). Bijgevolg is

\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 het even tijdstip $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 staat in de eerste $2n$ stappen precies even vaak nooit voor als zij nooit gelijk staat (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 nulpunt}\}$ . De twee gebeurtenissen hangen van disjuncte blokken worpen af en zijn dus onafhankelijk; de eerste heeft kans $u_k$ , de tweede $u_{n-k}$ volgens vraag 6 toegepast op de verse wandeling van $2n-2k$ stappen. Bijgevolg is $\P(L_{2n} = 2k) = u_ku_{n-k}$ . Omdat $L_{2n}$ precies de waarden $0, 2, \dots, 2n$ aanneemt, sommeren deze kansen tot $1$ : $\sum_{k=0}^nu_ku_{n-k} = 1$ , een binomiale identiteit geleverd door een kansrekenkundige partitie.

19. De 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 in de uitersten $k \in \{0, n\}$ , waar het gelijk is aan $u_n$ ; kwantitatief is $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ in het midden, 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 valt de laatste gelijkstand het waarschijnlijkst vlakbij het begin of vlakbij het einde: één speler staat meestal gedurende enorme stukken voor, zonder enige scheefheid in de munt.

20. Het beeld: op tijdstip $n$ leeft de wandeling op de 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 met kans $1$ oneindig vaak naar $0$ terug (Deel II), en toch heeft de wachttijd tussen de terugkeren een divergent gemiddelde (vraag 8), en daarom kunnen afzonderlijke uitstapjes een positief aandeel van elke horizon innemen; navenant is de laatste gelijkstand van een spel met $2n$ stappen uitgesmeerd met de uiterste waarden als de waarschijnlijkste (vragen 18–19), en heeft nooit voorstaan dezelfde traag vervallende kans $u_n$ als nooit gelijk staan (vraag 17). Zekerheid in de limiet, volharding op elke eindige horizon: dat is de eerlijke wandeling.

21. Partitioneer $\{S_{2n} = 0\}$ ( $n \geq 1$ ) naar de eerste terugkeertijd $2k$ , $1 \leq k \leq n$ : het eerste blok van $2k$ worpen verwezenlijkt een eerste terugkeer, de overige $2n - 2k$ worpen verwezenlijken 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$ en $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{dat wil zeggen}\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 partiaalsom $\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$ . Is $\sum u_n = \infty$ , dan $1 - F(x) = 1/U(x) \to 0$ , dus $f = 1$ . Is $\sum u_n = S < \infty$ , dan $1 - f = 1/S > 0$ , dus $f < 1$ . Controles: eerlijke wandeling, $\sum u_n = \infty$ en $f = 1$ (vragen 3, 7); scheve wandeling, $\sum u_n(4pq)^n < \infty$ en navenant $f = 1 - 1/\sum_{n\geq0}u_n(4pq)^n < 1$ , in overeenstemming met de bijna-zekere eindigheid van het aantal terugkeren (vraag 12).

23. Voor de vier stappen $(\pm1, 0), (0, \pm1)$ van de wandeling op $\Z^2$ zijn de aangroeiingen van $U = X + Y$ en $V = X - Y$ : $(+,+)$ voor $(1,0)$ , $(+,-)$ voor $(0,1)$ , $(-,+)$ voor $(0,-1)$ en $(-,-)$ voor $(-1,0)$ — elk tekenpaar met kans $\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$ , is

\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 tweedeling van vraag 22 gebruikten niets eendimensionaals (alleen de ontbinding over de eerste terugkeer en de onafhankelijkheid van disjuncte blokken), dus geeft $\sum u_n^{(2)} = \infty$ dat $f^{(2)} = 1$ , en het argument van vraag 9 verscherpt het: de wandeling op $\Z^2$ keert bijna zeker oneindig vaak naar de oorsprong terug.

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

25. Het tellen van paden en de spiegeling brachten de exacte verdelingen voort ( $u_n$ , de stemmenstelling, $f_n$ , het maximum, het laatste nulpunt); de monotone continuïteit zette elke uitspraak over een limiet (“keert minstens eenmaal terug”, “oneindig vaak”) om in een limiet van kansen met eindige horizon; de onafhankelijkheid van disjuncte blokken dreef de vernieuwingsontbindingen aan (vragen 9, 18, 21) — zij is het aftelbare skelet van de markov-eigenschap; Borel–Cantelli 1 was het wapen voor de transiëntie (vragen 12–13, 24), zonder onafhankelijkheid nodig te hebben; en de vernieuwingsidentiteit ordende alles tot de tweedeling $\sum u_n = \infty \iff$ recurrentie. Het enige analytische ingrediënt is de lokale schatting $u_n \sim 1/\sqrt{\pi n}$ : haar kwadraat $1/(\pi n)$ divergeert nog altijd (dimensie $2$ , recurrent), terwijl $n^{-3/2}$ convergeert (dimensie $3$ , transiënt) — de stelling van Pólya is uiteindelijk een uitspraak over de divergentie van $\sum n^{-d/2}$ .

21.1 Kansruimten

21.2 Voorwaardelijkheid 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