Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

23Kansgenererende functies

De machtreeksen van Hoofdstuk 11 keren terug met een kansrekenkundige opdracht: aan een toevalsveranderlijke met waarden in $\N$ hangen wij de machtreeks met coëfficiënten $\P(X = n)$ . Die genererende functie zet sommen van onafhankelijke veranderlijken om in producten, momenten in afgeleiden in $1$ , en moeilijke combinatorische identiteiten in vermenigvuldigingen van één regel. Het hoofdstuk sluit het boek af met twee pronkstukken: de poisson-benadering van zeldzame gebeurtenissen, en het uitstervingscriterium voor vertakkingsprocessen — een werkelijk oneindige kansberekening, volledig opgelost door de meetkunde van een convexe kromme.

23.1 Definitie en eerste eigenschappen

Definitie 23.1 (Kansgenererende functie)

Zij $X$ een toevalsveranderlijke met waarden in $\N$ en $p_n = \P(X = n)$ . De kansgenererende functie van $X$ is de som van de machtreeks

G_X(t) = \E\bigl(t^X\bigr) = \sum_{n=0}^{\infty} p_n\,t^n .

Voorbeeld 23.2 (Eerste reflexen)

Een constante veranderlijke $X = c$ heeft $G_X(t) = t^c$ ; een verschuiving voldoet aan $G_{X+c}(t) = t^c\,G_X(t)$ ; en evalueren in bijzondere punten leest informatie af zonder enige ontwikkeling: $G_X(0) = \P(X = 0)$ , $G_X(1) = 1$ en $G_X(-1) = \P(X\text{ even}) - \P(X\text{ oneven})$ , de pariteitsbalans die in Oefening 23.10 wordt uitgebuit. Deze eenregelige feiten worden hieronder stilzwijgend overal gebruikt — en de evaluatie $G_X(0)$ is precies hoe aan het eind van het hoofdstuk uitstervingskansen uit geïtereerde genererende functies zullen worden gehaald.

Propositie 23.3 (Straal en eerste eigenschappen)

De reeks die $G_X$ definieert, heeft convergentiestraal $\geq 1$ ; $G_X$ is gedefinieerd en continu op $\intcc{-1}{1}$ , van klasse $\mathcal{C}^\infty$ op $\intoo{-1}{1}$ , met $G_X(1) = 1$ en $\abs{G_X(t)} \leq 1$ daar. Bovendien legt $G_X$ de verdeling van $X$ vast:

p_n = \frac{G_X^{(n)}(0)}{n!} .

Bewijs. Omdat $\sum p_n = 1$ convergeert, zijn de termen $p_n\,1^n$ begrensd, dus is de straal $\geq 1$ (het lemma van Abel, Hoofdstuk 11); in $t = \pm1$ convergeert de reeks absoluut ( $\sum p_n = 1$ domineert); sterker nog, op het hele interval $\intcc{-1}1$ is

\sup_{\abs t\leq1}\,\abs{p_nt^n} = p_n \quad\text{met}\quad \sum_np_n < \infty :

de reeks convergeert normaal op $\intcc{-1}1$ , dus is haar som daar continu (Stellingen 10.16 en 10.4). De gladheid binnenin en de formule voor de coëfficiënten zijn de algemene theorie van de machtreeksen; omdat de coëfficiënten terugvindbaar zijn, hebben twee veranderlijken met dezelfde genererende functie dezelfde verdeling. ∎

Voorbeeld 23.4 (De klassieke verdelingen)

Bernoulli $\mathcal{B}(p)$ : $G(t) = 1 - p + pt$ .
Binomiaal $\mathcal{B}(n, p)$ : $G(t) = \sum_k \binom nk (pt)^k(1-p)^{n-k} = (1 - p + pt)^n$ (binomium).
Meetkundig $\mathcal{G}(p)$ : $G(t) = \sum_{k\geq1}(1-p)^{k-1}p\,t^k = \dfrac{pt}{1 - (1-p)t}$ (straal $\frac{1}{1-p} > 1$ ).
Poisson $\mathcal{P}(\lambda)$ : $G(t) = \sum_k e^{-\lambda}\frac{(\lambda t)^k}{k!} = e^{\lambda(t - 1)}$ (straal $\infty$ ).

Voorbeeld 23.5 (De genererende functie integreren)

Afgeleiden van $G_X$ in $1$ geven positieve momenten; de integraal geeft een negatief moment. Uit $\int_0^1t^k\dd t = \frac1{k+1}$ en termsgewijze integratie (normale convergentie op $\intcc01$ ):

\int_0^1G_X(t)\,\dd t = \sum_{k\geq0}\frac{\P(X = k)}{k+1} = \E\Bigl(\frac1{1+X}\Bigr).

Voor $X \sim \mathcal P(\lambda)$ :

\E\Bigl(\frac1{1+X}\Bigr) = \int_0^1\eu^{\lambda(t-1)}\,\dd t = \frac{1 - \eu^{-\lambda}}{\lambda},

waarmee de reeksberekening van Voorbeeld 22.10 in één regel wordt teruggevonden. De genererende functie is een instrument dat beide kanten op werkt: differentieer in $1$ voor de momenten $\E(X)$ en $\E(X(X-1))$ , integreer over $\intcc01$ voor $\E\bigl(\frac1{1+X}\bigr)$ — één analytisch object, bevraagd in de richting die het probleem vraagt.

Voorbeeld 23.6 (Een verdeling met straal precies één)

Zij $\P(X = k) = \dfrac{6}{\pi^2k^2}$ voor $k \geq 1$ — een kansverdeling wegens de identiteit van Basel (Voorbeeld 14.12). Haar genererende functie $G(t) = \frac6{\pi^2}\sum_{k\geq1}\frac{t^k}{k^2}$ heeft convergentiestraal precies $1$ : de algemene grens “straal $\geq 1$ ” van Propositie 23.3 kan niet worden verbeterd. En het gemiddelde is

\sum_{k\geq1}k\,\P(X = k) = \frac6{\pi^2}\sum_{k\geq1}\frac1k = \infty :

$G$ is continu op $\intcc{-1}1$ en glad binnenin, maar haar afgeleide explodeert in $1^-$ — de grafiek komt met een verticale raaklijn in het punt $(1, 1)$ aan. Zware staarten zijn meetkundig zichtbaar op de genererende functie, in het ene punt $t = 1$ ; de stelling over de momenten hieronder maakt die overeenkomst exact.

Stelling 23.7 (Momenten uit de genererende functie)

$X$ heeft een verwachtingswaarde dan en slechts dan als $G_X$ differentieerbaar is in $1^-$ (eindige linkerafgeleide), en dan is $\E(X) = G_X'(1)$ . Evenzo heeft $X$ een tweede moment dan en slechts dan als $G_X$ tweemaal differentieerbaar is in $1^-$ , en dan is

\E\bigl(X(X - 1)\bigr) = G_X''(1), \qquad V(X) = G_X''(1) + G_X'(1) - G_X'(1)^2 .

Bewijs. Voor $t \in \intoo{0}{1}$ geeft termsgewijs differentiëren binnen de schijf $G_X'(t) = \sum_{n\geq1} np_n t^{n-1}$ , een reeks met niet-negatieve coëfficiënten: $t \mapsto G_X'(t)$ is niet-dalend op $\intoo{0}{1}$ , en wegens de monotone convergentie van de partiaalsommen (of de stelling van Abel voor niet-negatieve coëfficiënten, Hoofdstuk 11) is

\lim_{t \to 1^-} G_X'(t) = \sum_{n\geq1} n\,p_n \in \intcc{0}{+\infty} ,

waarbij elk lid eindig is precies wanneer het andere dat is. Is het eindig, dan klemt de middelwaardestelling de differentiequotiënten $\frac{G_X(1) - G_X(t)}{1 - t}$ tussen waarden van $G_X'$ , zodat $G_X$ differentieerbaar is in $1^-$ met $G_X'(1) = \sum np_n = \E(X)$ (wegens de overdracht). De uitspraak van tweede orde herhaalt het argument één niveau hoger: $G''_X(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ is niet-dalend op $\intoo01$ met monotone limiet $\sum_nn(n-1)p_n = \E(X(X-1))$ , eindig precies wanneer $X$ een tweede moment heeft. De formule voor de variantie volgt dan uit König–Huygens:

V(X) = \E(X^2) - \E(X)^2 = \E\bigl(X(X-1)\bigr) + \E(X) - \E(X)^2 = G''_X(1) + G'_X(1) - G'_X(1)^2 .

∎

Voorbeeld 23.8

Poisson: $G'(t) = \lambda e^{\lambda(t-1)}$ , dus $\E(X) = \lambda$ ; $G''(1) = \lambda^2$ , dus $V(X) = \lambda^2 + \lambda - \lambda^2 = \lambda$ — de berekeningen van Hoofdstuk 22, elk in één regel.

Voorbeeld 23.9 (De modus van een poisson-verdeling)

Waar is $\P(X = k)$ het grootst voor $X \sim \mathcal P(\lambda)$ ? Opeenvolgende gewichten vergelijkt men met de verhouding

\frac{\P(X = k+1)}{\P(X = k)} = \frac{\lambda}{k + 1} ,

die groter is dan $1$ zolang $k < \lambda - 1$ en onder $1$ zakt zodra $k > \lambda - 1$ : de gewichten stijgen en dalen dan, met modus $\floor\lambda$ (en een gelijkspel tussen $\lambda - 1$ en $\lambda$ wanneer $\lambda$ geheel is: voor $\lambda = 3$ is $\P(X = 2) = \P(X = 3) = \frac92\eu^{-3} \approx 0.224$ ). Verhoudingstesten op de coëfficiënten zijn vaak de snelste weg naar kwalitatieve feiten over een discrete verdeling — geen genererende functie nodig, maar de coëfficiënten zijn de genererende functie, term voor term gelezen.

23.2 Sommen van onafhankelijke veranderlijken

Stelling 23.10 (Multiplicativiteit)

Zijn $X$ en $Y$ onafhankelijke toevalsveranderlijken met waarden in $\N$ , dan is

G_{X + Y}(t) = G_X(t)\,G_Y(t) \qquad (\abs t \leq 1),

en met inductie $G_{X_1 + \dots + X_n} = \prod_i G_{X_i}$ voor onafhankelijke $X_1, \dots, X_n$ .

Bewijs. Twee bewijzen, beide leerzaam. Via verwachtingswaarden: $t^X$ en $t^Y$ zijn onafhankelijke begrensde veranderlijken, dus (Stelling 22.11)

G_{X+Y}(t) = \E\bigl(t^{X+Y}\bigr) = \E\bigl(t^X t^Y\bigr) = \E\bigl(t^X\bigr)\E\bigl(t^Y\bigr) .

Via Cauchy-producten: de verdeling van $X + Y$ is de convolutie $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$ , en de stelling over het Cauchy-product voor absoluut convergente reeksen (Hoofdstuk 7) vermenigvuldigt de twee machtreeksen precies langs deze convolutie. ∎

Voorbeeld 23.11 (Stabiliteit van de klassieke verdelingen)

Onafhankelijke binomiale verdelingen met dezelfde $p$ tellen op: $(1 - p + pt)^m(1 - p + pt)^n = (1 - p + pt)^{m+n}$ , dus $\mathcal{B}(m, p) + \mathcal{B}(n, p) = \mathcal{B}(m + n, p)$ — in het bijzonder is een som van $n$ onafhankelijke bernoulli-veranderlijken binomiaal, wat de verdeling van het aantal successen opnieuw bewijst. Onafhankelijke poisson-verdelingen tellen op: $e^{\lambda(t-1)}e^{\mu(t-1)} = e^{(\lambda + \mu)(t-1)}$ , dus $\mathcal{P}(\lambda) + \mathcal{P}(\mu) = \mathcal{P}(\lambda + \mu)$ — de convolutieberekening van Oefening 22.2, nu zonder berekening.

Voorbeeld 23.12 (Twee dobbelstenen, één veelterm gekwadrateerd)

Voor één eerlijke dobbelsteen is $G(t) = \frac{t + t^2 + \dots + t^6}{6}$ ; voor de som van twee is

G(t)^2 = \frac{1}{36}\bigl(t^2 + 2t^3 + 3t^4 + 4t^5 + 5t^6 + 6t^7 + 5t^8 + 4t^9 + 3t^{10} + 2t^{11} + t^{12}\bigr) :

de driehoekige verdeling van de dobbelsteensommen ( $7$ is de modus, met kans $\frac6{36} = \frac16$ ), afgelezen van een gekwadrateerde veelterm die men eens in zijn leven uitwerkt. De convolutieformule zou elf afzonderlijke telargumenten hebben vereist; de genererende functie doet ze alle tegelijk, omdat veeltermen vermenigvuldigen is coëfficiënten convolueren. Deze mechanische vertaling — verdelingen naar coëfficiënten, sommen naar producten — is het hele verdienmodel van het hoofdstuk, en Oefening 23.11 drijft haar tot de verrassende dobbelstenen van Sicherman.

Voorbeeld 23.13 (Drie dobbelstenen en een coëfficiënt eruit halen)

Voor de som $S$ van drie eerlijke dobbelstenen is $\P(S = 10)$ de coëfficiënt van $t^{10}$ in $\bigl(\frac{t + \dots + t^6}6\bigr)^3$ . Ontbind en werk uit met het binomium en de meetkundige reeks:

\Bigl(\frac{t(1 - t^6)}{6(1 - t)}\Bigr)^{\!3} = \frac{t^3}{216}\,\bigl(1 - 3t^6 + 3t^{12} - t^{18}\bigr)\sum_{j\geq0}\binom{j+2}2t^j .

De coëfficiënt van $t^{10}$ vraagt $t^7$ uit het product: $j = 7$ met de term $1$ , en $j = 1$ met de term $-3t^6$ :

\P(S = 10) = \frac{1}{216}\Bigl(\binom92 - 3\binom32\Bigr) = \frac{36 - 9}{216} = \frac{27}{216} = \frac18 .

De $27$ drietallen rechtstreeks opsommen is foutgevoelig; de algebra is mechanisch en schaalt naar elk aantal dobbelstenen — de in- en uitsluiting zichtbaar in $(1 - t^6)^3$ doet het gevalsonderscheid vanzelf.

Voorbeeld 23.14 (Een verdeling van haar genererende functie aflezen)

Welke verdeling heeft $G(t) = \dfrac1{2 - t}$ ? Ontwikkel tot een machtreeks:

\frac{1}{2 - t} = \frac12\cdot\frac1{1 - t/2} = \sum_{k\geq0}\frac{t^k}{2^{k+1}} :

niet-negatieve coëfficiënten die tot $G(1) = 1$ sommeren, dus is dit een echte verdeling, $\P(X = k) = 2^{-(k+1)}$ op $\N$ — een meetkundige verdeling die in $0$ begint. Wegens de eenduidigheid (Propositie 23.3) deelt geen andere verdeling deze $G$ . Verdelingen herkennen aan hun genererende functies is een vaardigheid die het oefenen waard is: zo wordt de kritieke iterant $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ van de weekendopgave ontmaskerd als een meetkundige verdeling onder de voorwaarde van overleven.

Opmerking 23.15

De stabiliteit werkt maar één kant op: sommen van onafhankelijke poisson-veranderlijken zijn poisson, maar verschillen niet — $X - Y$ neemt negatieve waarden aan, dus heeft zij helemaal geen genererende functie, en haar verdeling (de verdeling van Skellam) ligt buiten de gereedschapskist van dit hoofdstuk. Evenmin is $\mathcal B(m, p) + \mathcal B(n, p')$ met $p \neq p'$ binomiaal: het product $(1 - p + pt)^m(1 - p' + p't)^n$ heeft twee verschillende plaatsen voor zijn nulpunten, terwijl elke binomiale genererende functie één herhaald nulpunt heeft. Stabiliteit aflezen van de patronen van de nulpunten is een kleine voorproef van hoeveel structuur de veelterm codeert.

Opmerking 23.16 (Het filter met de eenheidswortels)

Evalueren in $-1$ scheidt even van oneven; evalueren in alle $m$ -de eenheidswortels scheidt elke restklasse: met $\omega = \eu^{2\iu\pi/m}$ is

\P(X \equiv r \bmod m) = \frac1m\sum_{j=0}^{m-1}\omega^{-jr}\,G_X(\omega^j),

omdat $\omega^{j(k-r)}$ over $j$ middelen $1$ oplevert als $k \equiv r$ en $0$ anders. Voorbeelddividend: voor de som $S$ van twee eerlijke dobbelstenen is elke $G(\omega^j) = \frac16\sum_{k=1}^6 \omega^{jk} = -\frac16$ voor $j \neq 0$ (de zeven zevende eenheidswortels sommeren tot nul), dus

\P(7 \mid S) = \frac17\Bigl(1 + 6\cdot\frac1{36}\Bigr) = \frac16 ,

wat de telling uit Voorbeeld 23.12 bevestigt — en de methode schaalt naar vragen waar rechtstreeks tellen dat niet doet.

Stelling 23.17 (Toevallige sommen: de identiteit van Wald voor genererende functies)

Zij $(X_k)_{k\geq1}$ een rij onafhankelijke veranderlijken met waarden in $\N$ , dezelfde verdeling en genererende functie $G_X$ , en zij $N$ een veranderlijke met waarden in $\N$ , onafhankelijk van de $X_k$ , met genererende functie $G_N$ . Dan heeft de toevallige som $S = X_1 + \dots + X_N$ (met $S = 0$ wanneer $N = 0$ ) als genererende functie

G_S = G_N \circ G_X .

Hebben $N$ en $X_1$ in het bijzonder verwachtingswaarden, dan is $\E(S) = \E(N)\,\E(X_1)$ .

Bewijs. Stel voorwaardelijk op $N$ (totale kans, Stelling 21.14): voor $\abs t \leq 1$ is

G_S(t) = \sum_{n=0}^\infty \P(N = n)\, \E\bigl(t^{X_1 + \dots + X_n}\bigr) = \sum_{n=0}^\infty \P(N = n)\,G_X(t)^n = G_N\bigl(G_X(t)\bigr),

met de multiplicativiteit voor elke vaste $n$ en de sommeerbaarheid van de hele dubbele familie ( $\abs{G_X(t)} \leq 1$ ). De verwisseling van de sommaties is Fubini voor sommeerbare families (Hoofdstuk 7). Differentiëren in $1^-$ met de kettingregel en Stelling 23.7: $\E(S) = G_N'(G_X(1))\,G_X'(1) = G_N'(1)G_X'(1) = \E(N)\E(X_1)$ . ∎

Voorbeeld 23.18 (Samengestelde Poisson: jaarlijkse verzekeringsschade)

Een verzekeraar ontvangt $N \sim \mathcal P(\lambda)$ claims per jaar, elk met kosten $X_k$ (gehele eenheden, onafhankelijk en identiek verdeeld, genererende functie $G_X$ , gemiddelde $\mu$ , onafhankelijk van $N$ ). Volgens Stelling 23.17 heeft de totale schade $S$

G_S(t) = \eu^{\lambda(G_X(t) - 1)}, \qquad \E(S) = \lambda\mu ,

en tweemaal differentiëren in $1^-$ geeft

V(S) = \lambda\,G_X''(1) + \lambda^2\mu^2 + \lambda\mu - (\lambda\mu)^2 = \lambda\,\E(X^2) .

De variantie betreft het tweede moment van één claim, niet haar variantie: een samengestelde poisson-som voelt de af en toe grote claim tweemaal — eenmaal via hoeveel, eenmaal via hoe groot. Voor $\lambda = 10$ claims met een meetkundige verdeling met gemiddelde $2$ ( $\E X^2 = 6$ ): $\E S = 20$ , $V(S) = 60$ , en Chebyshev (Hoofdstuk 22) levert al bruikbare solvabiliteitsmarges. Dit patroon van de “toevallig gestopte som” is hetzelfde dat de vertakkingsrecursie van Propositie 23.23 zal aandrijven: de samenstelling van genererende functies is de algebra van toevallige populaties.

Opmerking 23.19

De onafhankelijkheid van $N$ van de termen is niet decoratief. Neem $X_k \in \{0, 2\}$ met gelijke kansen en zij $N = X_1$ (flagrant afhankelijk): dan is $S = X_1 + \dots + X_N$ gelijk aan $0$ wanneer $X_1 = 0$ , en aan $2 + X_2$ wanneer $X_1 = 2$ , dus $\E(S) = \frac12(2 + 1) = \frac32$ , terwijl $\E(N)\E(X_1) = 1\cdot1 = 1$ : de identiteit van Wald faalt. Zodra het aantal termen op de termen zelf mag reageren, stort de nette productstructuur in — de volledige theorie van zulke “stopregels” is het hoofdstuk over martingalen van het volume van bachelorjaar 3.

23.3 Poisson-benadering

Stelling 23.20 (Wet van de zeldzame gebeurtenissen)

Zij $X_n \sim \mathcal{B}(n, p_n)$ met $n\,p_n \to \lambda > 0$ . Dan geldt voor elke $k \in \N$

\P(X_n = k) \xrightarrow[n\to\infty]{} e^{-\lambda}\frac{\lambda^k}{k!} :

de binomiale verdeling van veel zeldzame onafhankelijke gebeurtenissen convergeert naar de poisson-verdeling met parameter $\lambda$ .

Bewijs. Rechtstreekse berekening met $p_n = \frac{\lambda_n}{n}$ , $\lambda_n \to \lambda$ :

\P(X_n = k) = \binom nk p_n^k(1 - p_n)^{n-k} = \frac{n(n-1)\cdots(n-k+1)}{n^k}\cdot \frac{\lambda_n^k}{k!}\, \bigl(1 - \tfrac{\lambda_n}{n}\bigr)^{n-k} .

Als $n \to \infty$ met vaste $k$ : de eerste factor streeft naar $1$ (een product van $k$ factoren $\to 1$ ); $\lambda_n^k \to \lambda^k$ ; en $\bigl(1 - \frac{\lambda_n}{n}\bigr)^{n-k} = \exp\bigl((n-k)\ln(1 - \frac{\lambda_n}{n})\bigr) \to e^{-\lambda}$ omdat $(n - k)\ln\bigl(1 - \frac{\lambda_n}{n}\bigr) \sim -\lambda_n \to -\lambda$ (Hoofdstuk 6). Alternatief, op het niveau van de genererende functies: $G_{X_n}(t) = \bigl(1 + \frac{\lambda_n(t-1)}{n}\bigr)^n \to e^{\lambda(t - 1)} = G_{\mathcal{P}(\lambda)}(t)$ voor elke vaste $t \in [0, 1]$ — convergentie van genererende functies, wat (voor veranderlijken met waarden in $\N$ ) gelijkwaardig is met de convergentie van elke $\P(X_n = k)$ ; zie Oefening 23.9. ∎

Opmerking 23.21

Daarom modelleren poisson-verdelingen tellingen van zeldzame gebeurtenissen — tikfouten per bladzijde, radioactieve vervallen per seconde, ongevallen per dag op een kruispunt: elke gelegenheid is bijna verwaarloosbaar, de gelegenheden zijn talrijk, en alleen het gemiddelde tempo $\lambda$ overleeft in de limiet.

Voorbeeld 23.22 (De poisson-limiet zien convergeren)

Houd $\lambda = 2$ vast en zij $X_n \sim \mathcal B(n, 2/n)$ . De kans op geen enkele gebeurtenis is precies $\P(X_n = 0) = (1 - 2/n)^n$ :

n = 10:\ 0.107, \qquad n = 20:\ 0.122, \qquad n = 50:\ 0.130, \qquad n = 100:\ 0.133,

tegenover de limiet $\eu^{-2} \approx 0.135$ . De convergentie is monotoon en van snelheid $O(1/n)$ — uitwerken geeft $(1 - 2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — zodat het poisson-model voor $n$ in de honderdtallen al tot op het derde cijfer nauwkeurig is. Dat is de praktische inhoud van de wet van de zeldzame gebeurtenissen: de modelleerder kent $n$ en $p$ nooit afzonderlijk (hoeveel micro-gelegenheden voor een tikfout bevat een bladzijde?), maar alleen hun product $\lambda$ , en de limietverdeling hangt genadig van niets anders af.

23.4 Vertakkingsprocessen

Beschouw een populatie die met één voorouder begint; elk individu krijgt onafhankelijk een toevallig aantal kinderen met verdeling $(p_k)_{k \in \N}$ en genererende functie $G$ (de nakomelingenverdeling). Zij $Z_n$ de grootte van generatie $n$ ( $Z_0 = 1$ ), en zij $m = G'(1) = \E(Z_1)$ het gemiddelde aantal nakomelingen.

Propositie 23.23

De genererende functie van $Z_n$ is de $n$ -de iterant $G_{Z_n} = G \circ G \circ \dots \circ G$ ( $n$ maal), en de uitstervingskansen $q_n = \P(Z_n = 0)$ voldoen aan

q_0 = 0, \qquad q_{n+1} = G(q_n),

en stijgen naar de kans $q$ op uiteindelijk uitsterven, die een vast punt van $G$ is.

Bewijs. Generatie $n + 1$ is de toevallige som van de nakomelingen van de $Z_n$ leden van generatie $n$ , met aantallen die onafhankelijk zijn van elkaar en van $Z_n$ : Stelling 23.17 geeft $G_{Z_{n+1}} = G_{Z_n} \circ G$ , en inductie vanaf $G_{Z_0}(t) = t$ levert de $n$ -voudige iterant — die wegens de associativiteit van de samenstelling evengoed als $G_{Z_{n+1}} = G \circ G_{Z_n}$ kan worden gelezen. Die tweede vorm in $0$ evalueren geeft $q_{n+1} = G_{Z_{n+1}}(0) = G\bigl(G_{Z_n}(0)\bigr) = G(q_n)$ . De gebeurtenissen $\{Z_n = 0\}$ stijgen (uitgestorven populaties blijven uitgestorven), dus $q_n \uparrow q = \P\bigl(\bigcup_n\{Z_n = 0\}\bigr)$ wegens de monotone continuïteit (Stelling 21.6), en de continuïteit van $G$ op $[0, 1]$ maakt van $q_{n+1} = G(q_n)$ in de limiet $q = G(q)$ . ∎

Voorbeeld 23.24 (Het uitsterven zien convergeren)

Voor de nakomelingenverdeling $(p_0, p_1, p_2) = (\tfrac14, \tfrac14, \tfrac12)$ van Voorbeeld 23.27 is $G(t) = \tfrac14 + \tfrac14t + \tfrac12t^2$ , en geeft de iteratie $q_{n+1} = G(q_n)$

q_1 = 0.25, \quad q_2 = 0.34375, \quad q_3 \approx 0.39502, \quad q_4 \approx 0.42678, \quad q_5 \approx 0.44776,

klimmend naar de uitstervingskans $q = \tfrac12$ . De gaten $q - q_n$ zijn $0.25$ , $0.156$ , $0.105$ , $0.073$ , $0.052$ : elk is ruwweg $\tfrac34$ van het vorige, en inderdaad geeft de middelwaardestelling $q - q_{n+1} = G'(c_n)(q - q_n)$ met $G'(q) = \tfrac14 + q = \tfrac34$ . Twee lessen: een familielijn die in generatie $n$ nog leeft, heeft volgens dezelfde berekening kans $q - q_n$ om later alsnog te sterven; en het convergentietempo van de trap in de figuur hieronder is de afgeleide in het vaste punt — de weekendopgave maakt van beide waarnemingen stellingen.

Stelling 23.25 (Uitstervingscriterium)

Neem aan dat $p_1 \neq 1$ . De uitstervingskans $q$ is het kleinste vaste punt van $G$ in $\intcc{0}{1}$ , en:

is $m \leq 1$ (subkritisch of kritisch), dan $q = 1$ : het uitsterven is zeker;
is $m > 1$ (superkritisch), dan $q < 1$ : de populatie overleeft voor altijd met positieve kans $1 - q$ .

Bewijs. $G$ is convex op $\intcc{0}{1}$ (een machtreeks met niet-negatieve coëfficiënten: $G'' \geq 0$ ), niet-dalend, met $G(1) = 1$ .

Kleinste vaste punt: zij $r \in \intcc{0}{1}$ een willekeurig vast punt. Dan is $q_0 = 0 \leq r$ , en met inductie $q_{n+1} = G(q_n) \leq G(r) = r$ (monotonie): dus $q = \lim q_n \leq r$ .

Geval $m \leq 1$ : stel dat $r < 1$ een vast punt is. Volgens de middelwaardestelling op $[r, 1]$ is er een $c \in \intoo{r}{1}$ met $G'(c) = \frac{G(1) - G(r)}{1 - r} = \frac{1 - r}{1 - r} = 1$ . Maar $G'$ is niet-dalend (convexiteit) met $\lim_{t\to1^-}G'(t) = m \leq 1$ , dus $G' \leq 1$ op $\intoo{0}{1}$ ; de gelijkheid $G'(c) = 1$ dwingt dan af dat $G'$ constant gelijk aan $1$ is op $\intco{c}{1}$ , en dus dat $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ daar. Een machtreeks met niet-negatieve coëfficiënten die op een interval verdwijnt, heeft al die coëfficiënten nul: $p_n = 0$ voor $n \geq 2$ , dus $G(t) = p_0 + p_1t$ en $1 = G'(c) = p_1$ — in tegenspraak met de hypothese $p_1 \neq 1$ . Dus is $1$ het enige vaste punt: $q = 1$ .

Geval $m > 1$ : nabij $1$ heeft $G(t) - t$ afgeleide $G'(t) - 1 \to m - 1 > 0$ als $t \to 1^-$ , dus $G(t) - t < G(1) - 1 = 0$ op een zeker interval $\intoo{1 - \delta}{1}$ : de continue functie $G(t) - t$ is $\geq 0$ in $t = 0$ ( $G(0) = p_0 \geq 0$ ) en $< 0$ net onder $1$ , dus verdwijnt zij in een zekere $r < 1$ (tussenwaardestelling). Het kleinste vaste punt is dan $q \leq r < 1$ . ∎

Uitstervingskansen als een vastepuntsiteratie q_n+1 = G(q_n) startend in q_0 = 0 (de rode trap). Links: een subkritische nakomelingenverdeling — de convexe kromme blijft boven de diagonaal en de iteratie klimt naar het unieke vaste punt 1. Rechts: een superkritische verdeling — de kromme kruist de diagonaal in q < 1, waar de iteratie stopt: overleven heeft kans 1 - q > 0. — **Figuur 23.1.** Uitstervingskansen als een vastepuntsiteratie $q_{n+1} = G(q_n)$ startend in $q_0 = 0$ (de rode trap). Links: een subkritische nakomelingenverdeling — de convexe kromme blijft boven de diagonaal en de iteratie klimt naar het unieke vaste punt $1$ . Rechts: een superkritische verdeling — de kromme kruist de diagonaal in $q < 1$ , waar de iteratie stopt: overleven heeft kans $1 - q > 0$ .

Opmerking 23.26 (Hoe je het spinnenwebdiagram leest)

In de figuur past een verticale beweging $G$ toe (van $(q_n, q_n)$ omhoog naar $(q_n, G(q_n))$ ), en zet een horizontale beweging naar de diagonaal de uitvoer om in invoer: de trap is de recursie $q_{n+1} = G(q_n)$ . De convexiteit van $G$ en $G(1) = 1$ laten maar twee meetkundes toe. Ofwel blijft de kromme op $\intco01$ boven de diagonaal (gemiddelde $m \leq 1$ ): de trap heeft nergens om te stoppen vóór $1$ . Ofwel kruist de kromme haar in een zekere $q < 1$ ( $m > 1$ ): de trap zit onder het kruispunt gevangen en convergeert ernaartoe, met het meetkundige tempo $G'(q) < 1$ dat in Voorbeeld 23.24 werd gekwantificeerd. De hele analyse van de uitstervingsstelling is in dit ene beeld zichtbaar — en daarom is het de moeite waard het te tekenen voordat je rekent.

Voorbeeld 23.27

Nakomelingenverdeling: geen kind, één kind, twee kinderen met kansen $\frac14, \frac14, \frac12$ . Dan is $m = \frac14 + 1 = \frac54 > 1$ en $G(t) = \frac14 + \frac14 t + \frac12 t^2$ . Vaste punten: $\frac12 t^2 - \frac34 t + \frac14 = 0$ , dat wil zeggen $2t^2 - 3t + 1 = (2t - 1)(t - 1) = 0$ : $q = \frac12$ . De familielijn sterft uit met kans $\frac12$ — en met kans $\frac12$ leeft zij voor altijd voort.

Opmerking 23.28 (Vooruitblik binnen dit volume)

Het hoofdstuk is het kruispunt van het boek, en elk ingrediënt kwam van een met naam genoemde plaats: de algebra van de reeksen uit Hoofdstuk 7 en Hoofdstuk 11, de kansrekening uit Hoofdstuk 21 (de monotone continuïteit bewijst $q_n \uparrow q$ ) en Hoofdstuk 22 ( $G_X = \E(t^X)$ is een verwachtingswaarde, de multiplicativiteit is de productstelling), de convexiteit uit Hoofdstuk 8 via Hoofdstuk 17. Zelfs de pathologieën met zware staarten sluiten aan: de Sint-Petersburgveranderlijke van het vorige hoofdstuk heeft $G(t) = \sum_k2^{-k}t^{2^k}$ , een volmaakt convergente reeks op $\intcc01$ waarvan de afgeleide in $1^-$ divergeert — een oneindig gemiddelde, in één oogopslag zichtbaar. Eén object, elk gereedschap van het jaar: een passend laatste hoofdstuk.

Opmerking 23.29 (Klassieke valkuilen)

(i) Genererende functies zijn alleen van toepassing op veranderlijken met waarden in $\N$ : voor veranderlijken met tekens of niet-gehele waarden verliest het object $\E(t^X)$ zijn structuur als machtreeks (bachelorjaar 3 vervangt haar door transformaties die aan $\R$ zijn aangepast). (ii) De eerste verstandscontrole van elke berekende $G$ is $G(1) = 1$ ; de tweede is dat de coëfficiënten niet-negatief zijn — een negatieve coëfficiënt betekent een algebrafout, geen nieuwe verdeling. (iii) Bij toevallige sommen doet de volgorde van de samenstelling ertoe: $G_S = G_N \circ G_X$ , met de buitenste functie die de termen telt; andersom samenstellen is zinloos ( $G_X \circ G_N$ zou voorwerpen van voorwerpen tellen). (iv) De multiplicativiteit vereist onafhankelijkheid en verschillende bronnen van toeval: $G_{2X}(t) = G_X(t^2)$ , niet $G_X(t)^2$ . (v) Differentiëren in $1$ is een randbewerking: is de straal precies $1$ , zoals in Voorbeeld 23.6, dan kan $G'(1^-)$ oneindig zijn, en is de formulering met de monotone limiet in de stelling over de momenten geen muggenzifterij maar de eerlijke uitspraak.

Het volume afsluiten

De genererende functie is een passend laatste object voor dit boek: zij is tegelijk een machtreeks (Hoofdstuk 11), een gereedschap van de sommeerbare families (Hoofdstuk 7), een verwachtingswaarde (Hoofdstuk 22), een convexe functie waarvan de meetkunde over het uitsterven beslist (Hoofdstuk 8), en een vastepuntsiteratie (Hoofdstuk 4). De wiskunde van bachelorjaar 2 is één vak. Het volume van bachelorjaar 3 zal de deuren openen die hier opzettelijk gesloten bleven: de integraal van Lebesgue (die de stelling van de gedomineerde convergentie uit Hoofdstuk 9 kwijt), de maattheoretische kansrekening op overaftelbare ruimten, en het volledige bewijs van de stelling van de inverse functie (Hoofdstuk 15) in het kader van de differentiaalmeetkunde.

23.5 Oefeningen

Oefening 23.1 ★

Bereken de genererende functie van de uniforme verdeling op $\{1, 2, \dots, 6\}$ (een eerlijke dobbelsteen). Toon aan dat de som van twee eerlijke dobbelstenen niet uniform kan zijn op $\{2, \dots, 12\}$ : ontbind $G_{X+Y}$ en tel nulpunten. (Een uniforme som zou $G_X(t)G_Y(t) = \frac{t^2}{11}\sum_{k=0}^{10}t^k$ afdwingen, waarvan de nulpunten ongelijk aan nul de elfde eenheidswortels behalve $1$ zijn — geen enkele daarvan reëel — terwijl $G_X/t$ en $G_Y/t$ reële veeltermen van graad $5$ zijn, die elk minstens één reëel nulpunt bezitten.)

Oplossing

Oplossing van Oefening 23.1.

Eerlijke dobbelsteen: $G(t) = \frac16(t + t^2 + \dots + t^6) = \frac t6(1 + t + \dots + t^5)$ . Was de som van twee eerlijke dobbelstenen uniform op $\{2, \dots, 12\}$ , dan zou

G(t)^2 = \frac{t^2}{36}\,h(t)^2 = \frac{t^2}{11}\sum_{k=0}^{10}t^k , \qquad h(t) = 1 + t + \dots + t^5 .

Nu is $h$ een reële veelterm van oneven graad $5$ , dus heeft zij een reëel nulpunt (tussenwaardestelling; concreet $h(-1) = 0$ ), en dus heeft $h^2$ een reëel nulpunt. Maar $\sum_{k=0}^{10}t^k$ heeft er geen: zij is positief voor $t \geq 0$ , en voor $t < 0$ is zij gelijk aan $\frac{t^{11} - 1}{t - 1}$ , een quotiënt van twee negatieve getallen. Tegenspraak — de som van twee eerlijke dobbelstenen is nooit uniform (zoals de vertrouwde driehoekige verdeling van dobbelsteensommen bevestigt).

Oefening 23.2 ★

Vind met genererende functies $\E$ en $V$ terug voor de binomiale en de meetkundige verdeling (Stelling 23.7).

Oplossing

Oplossing van Oefening 23.2.

Binomiaal: $G(t) = (1 - p + pt)^n$ , $G'(t) = np(1 - p + pt)^{n-1}$ , $G''(t) = n(n-1)p^2(1 - p + pt)^{n-2}$ , dus

\E(X) = G'(1) = np, \qquad V(X) = G''(1) + G'(1) - G'(1)^2 = n(n-1)p^2 + np - n^2p^2 = np(1-p).

Meetkundig ( $q = 1 - p$ ): $G(t) = \frac{pt}{1 - qt}$ , dus $G'(t) = \frac{p}{(1 - qt)^2}$ en $G''(t) = \frac{2pq}{(1 - qt)^3}$ ; in $t = 1$ (met $1 - q = p$ ):

\E(X) = \frac{p}{p^2} = \frac1p, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{2q + p - 1}{p^2} = \frac{q}{p^2} ,

in overeenstemming met Oefening 22.1, met minder werk.

Oefening 23.3 ★

Twee verzwaarde dobbelstenen: is het mogelijk twee dobbelstenen zo te verzwaren (onafhankelijk, identiek of niet) dat hun som uniform is op $\{2, \dots, 12\}$ ? (Dezelfde obstructie via de ontbinding als in Oefening 23.1: het antwoord is nee, zelfs met verschillende verzwaringen, omdat elke factor $G_X(t)/t$ oneven graad $5$ heeft en dus een reëel nulpunt, terwijl het doel er geen heeft.)

Oplossing

Oplossing van Oefening 23.3.

Nee, zelfs niet met verschillende verzwaringen. Stel dat $X, Y$ verdelingen op $\{1, \dots, 6\}$ zijn met een uniforme som. Dan is $G_X(t) = t\,a(t)$ en $G_Y(t) = t\,b(t)$ met $a, b$ reële veeltermen van graad hoogstens $5$ — en hun graden moeten tot $10$ sommeren (de som bereikt $12$ met positieve kans), dus $\deg a = \deg b = 5$ , beide oneven. Als in Oefening 23.1 zou

a(t)\,b(t) = \frac{1}{11}\sum_{k=0}^{10}t^k

links een reëel nulpunt afdwingen (elke reële veelterm van oneven graad heeft er een) en rechts geen. Geen enkele verzwaring van twee onafhankelijke dobbelstenen — gelijk of niet — brengt dus een uniforme som voort.

Oefening 23.4 ★★

Zijn $X_1, X_2, \dots$ onafhankelijke bernoulli-veranderlijken $\mathcal{B}(p)$ en $N \sim \mathcal{P}(\lambda)$ onafhankelijk van hen. Toon met Stelling 23.17 aan dat $S = X_1 + \dots + X_N \sim \mathcal{P}(\lambda p)$ : een poisson-aantal voorwerpen, elk met kans $p$ bewaard, laat een poisson-aantal over — uitdunning. Bereken ook de verdeling van het weggegooide aantal en bewonder: zij is $\mathcal{P}(\lambda(1-p))$ , en men kan aantonen dat zij onafhankelijk is van $S$ .

Oplossing

Oplossing van Oefening 23.4.

Volgens Stelling 23.17 met $G_N(s) = e^{\lambda(s-1)}$ en $G_X(t) = 1 - p + pt$ :

G_S(t) = e^{\lambda(1 - p + pt - 1)} = e^{\lambda p(t - 1)} :

$S \sim \mathcal{P}(\lambda p)$ . Het weggegooide aantal $D = N - S$ telt dezelfde voorwerpen, bewaard met kans $1 - p$ , dus is volgens dezelfde berekening $D \sim \mathcal{P}(\lambda(1 - p))$ . Onafhankelijkheid, rechtstreeks: voor $j, k \in \N$ is

\begin{align*} \P(S = j,\ D = k) &= \P(N = j + k)\,\binom{j+k}{j}p^jq^k = e^{-\lambda}\frac{\lambda^{j+k}}{(j+k)!}\, \frac{(j+k)!}{j!\,k!}\,p^jq^k\\ &= \Bigl(e^{-\lambda p}\frac{(\lambda p)^j}{j!}\Bigr) \Bigl(e^{-\lambda q}\frac{(\lambda q)^k}{k!}\Bigr) \end{align*}

met $q = 1 - p$ : de gezamenlijke verdeling ontbindt als $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$ . Een poisson-stroom die willekeurig wordt gesplitst, levert onafhankelijke poisson-stromen op — een klein wonder dat in de wachtrijtheorie voortdurend wordt gebruikt.

Oefening 23.5 ★★

(Negatief binomiaal) Zij $T_r$ het aantal worpen om $r$ maal kop te verkrijgen (kanskop $p$ ). Schrijf $T_r$ als een som van $r$ onafhankelijke meetkundige veranderlijken, leid af dat

G_{T_r}(t) = \Bigl(\frac{pt}{1 - (1-p)t}\Bigr)^{r}, \qquad \E(T_r) = \frac rp, \qquad V(T_r) = \frac{r(1-p)}{p^2},

en ontwikkel $G_{T_r}$ om $\P(T_r = n) = \binom{n-1}{r-1} p^r(1-p)^{n-r}$ te vinden.

Oplossing

Oplossing van Oefening 23.5.

De wachttijden tussen opeenvolgende koppen zijn onafhankelijke meetkundige veranderlijken $\mathcal{G}(p)$ (geheugenloosheid: na elke kop begint het spel opnieuw), dus $T_r = W_1 + \dots + W_r$ en geeft de multiplicativiteit (Stelling 23.10)

G_{T_r}(t) = \Bigl(\frac{pt}{1 - qt}\Bigr)^{r}, \qquad \E(T_r) = r\,\E(W_1) = \frac rp, \qquad V(T_r) = r\,V(W_1) = \frac{rq}{p^2}

( $q = 1 - p$ ; de varianties tellen op wegens de onafhankelijkheid). Ontwikkeling: volgens de veralgemeende binomiale reeks (Hoofdstuk 11) is $(1 - qt)^{-r} = \sum_{m\geq0} \binom{m + r - 1}{r - 1}q^mt^m$ , dus is de coëfficiënt van $t^n$ in $p^rt^r(1 - qt)^{-r}$ (met $m = n - r$ )

\P(T_r = n) = \binom{n-1}{r-1}p^r(1-p)^{n-r}, \qquad n \geq r ,

de negatief binomiale verdeling — combinatorisch: de $r$ -de kop valt op worp $n$ dan en slechts dan als de vorige $r - 1$ koppen hun plaatsen kiezen onder de eerste $n - 1$ worpen.

Oefening 23.6 ★★

Bereken voor de nakomelingenverdeling $p_0 = \frac18$ , $p_1 = \frac38$ , $p_2 = \frac38$ , $p_3 = \frac18$ het gemiddelde $m$ , beslis over de superkritikaliteit, en bereken de uitstervingskans $q$ exact. (Zonder het nulpunt $t = 1$ van $G(t) - t$ af.)

Oplossing

Oplossing van Oefening 23.6.

$m = 1\cdot\frac38 + 2\cdot\frac38 + 3\cdot\frac18 = \frac{3 + 6 + 3}{8} = \frac32 > 1$ : superkritisch. De genererende functie is

G(t) = \frac{1 + 3t + 3t^2 + t^3}{8} = \frac{(1 + t)^3}{8} ,

dus lossen de vaste punten $(1 + t)^3 = 8t$ op, dat wil zeggen $t^3 + 3t^2 - 5t + 1 = 0$ . Het gewaarborgde nulpunt $t = 1$ afzonderen geeft

t^3 + 3t^2 - 5t + 1 = (t - 1)\bigl(t^2 + 4t - 1\bigr),

en $t^2 + 4t - 1 = 0$ geeft $t = -2 \pm \sqrt5$ . Het nulpunt in $\intco{0}{1}$ is $\sqrt5 - 2 \approx 0.236$ : volgens Stelling 23.25 is

q = \sqrt 5 - 2 .

(Een aangename controle: de nakomelingenverdeling is die van $3$ onafhankelijke eerlijke munten, $Z_1 \sim \mathcal{B}(3, \frac12)$ .)

Oefening 23.7 ★★★

(Totale nakomelingschap) Zij in een subkritisch vertakkingsproces ( $m < 1$ ) $Y = \sum_{n\geq0} Z_n$ het totale aantal individuen dat ooit geboren wordt. Toon aan dat $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (verantwoord de verwisseling van de sommaties), en bewijs dat de genererende functie $H = G_Y$ voldoet aan de functionaalvergelijking $H(t) = t\,G(H(t))$ . (De voorouder, plus de totale nakomelingschappen van elk van haar kinderen, die onafhankelijke kopieën van $Y$ zijn.)

Oplossing

Oplossing van Oefening 23.7.

Verwachtingswaarde. Eerst $\E(Z_n) = m^n$ : volgens Stelling 23.17 is $\E(Z_{n+1}) = \E(Z_n)\,m$ , en $\E(Z_0) = 1$ . De familie $\bigl(Z_n(\omega)\P(\{\omega\}) \bigr)_{n, \omega}$ is niet-negatief, dus is Fubini voor families onvoorwaardelijk van toepassing:

\E(Y) = \sum_{n=0}^{\infty}\E(Z_n) = \sum_{n=0}^\infty m^n = \frac{1}{1 - m} < \infty

(in het bijzonder is $Y$ bijna zeker eindig: in overeenstemming met het zekere uitsterven in het subkritische geval).

Functionaalvergelijking. Ontbind de populatie naar de kinderen van de voorouder: heeft de voorouder $Z_1 = k$ kinderen, dan is de totale nakomelingschap $Y = 1 + Y_1 + \dots + Y_k$ , waarbij $Y_i$ de totale nakomelingschap van de lijn van het $i$ -de kind is — en de $Y_i$ zijn onafhankelijke kopieën van $Y$ , onafhankelijk van $Z_1$ (verschillende lijnen gebruiken disjuncte, onafhankelijke voortplantingsgebeurtenissen). Voorwaardelijk stellen op $Z_1$ als in Stelling 23.17 geeft

H(t) = \E\bigl(t^Y\bigr) = t\sum_{k=0}^\infty \P(Z_1 = k)\,H(t)^k = t\,G\bigl(H(t)\bigr),

waarbij de factor $t$ de voorouder zelf verantwoordt. (Voor de verdeling $p_0 = 1 - p$ , $p_2 = p$ van de binaire vertakking kan deze kwadratische vergelijking in $H$ expliciet worden opgelost en ontwikkeld — de Catalangetallen van Hoofdstuk 11 tellen de stambomen.)

Oefening 23.8 ★★★

Zij $X$ met genererende functie $G$ met convergentiestraal $> 1$ . Bewijs de exponentiële staartgrens: er zijn een $C > 0$ en een $\rho \in \intoo{0}{1}$ met $\P(X \geq n) \leq C\rho^n$ . (Markov toegepast op $t^X$ voor een vaste $t > 1$ binnen de schijf.) Toon omgekeerd aan dat als $\P(X \geq n) \leq C\rho^n$ met $\rho < 1$ , de straal van $G$ minstens $1/\rho > 1$ is.

Oplossing

Oplossing van Oefening 23.8.

Zij $R > 1$ de straal en houd $t \in \intoo{1}{R}$ vast. Dan is $\E(t^X) = G(t) < \infty$ , en de ongelijkheid van Markov (Stelling 22.15) toegepast op de niet-negatieve veranderlijke $t^X$ op niveau $t^n$ geeft

\P(X \geq n) = \P\bigl(t^X \geq t^n\bigr) \leq \frac{G(t)}{t^n} = C\rho^n, \qquad C = G(t),\quad \rho = \frac1t \in \intoo{0}{1}.

Omkering: geldt $\P(X \geq n) \leq C\rho^n$ , dan is $p_n \leq \P(X \geq n) \leq C\rho^n$ , dus wordt voor $\abs t < \frac1\rho$ de reeks $\sum p_n\abs t^n$ gedomineerd door de convergente meetkundige reeks $C\sum(\rho\abs t)^n$ : de straal is minstens $\frac1\rho > 1$ . De straal van de genererende functie en het meetkundige verval van de staart zijn twee gezichten van dezelfde eigenschap.

Oefening 23.9 ★★★

(Continuïteitsstelling, elementair geval) Zijn $X, X_1, X_2, \dots$ veranderlijken met waarden in $\N$ met $G_{X_n}(t) \to G_X(t)$ voor elke $t \in \intco{0}{1}$ . Toon aan dat $\P(X_n = k) \to \P(X = k)$ voor elke $k$ . (Inductie naar $k$ : voor $k = 0$ laat je $t \to 0$ gaan — zorgvuldig: houd $t$ klein vast en gebruik $\abs{\P(X_n = 0) - G_{X_n}(t)} \leq \frac{t}{1-t}$ , geldig omdat de staart $\sum_{j \geq 1}p_jt^j \leq \frac{t}{1 - t}$ is; en diagonaliseer dan. Beschouw voor de inductiestap $\frac{G(t) - \P(X = 0)}{t}$ , de genererende functie van een verschoven verdeling.)

Oplossing

Oplossing van Oefening 23.9.

Schrijf $p_k^{(n)} = \P(X_n = k)$ en $p_k = \P(X = k)$ .

Geval $k = 0$ . Voor $t \in \intoo{0}{1}$ en elke verdeling $(q_j)$ met $\sum_j q_j \leq 1$ is

\Bigl|\,q_0 - \sum_j q_jt^j\Bigr| = \sum_{j \geq 1} q_j t^j \leq \sum_{j\geq1}t^j = \frac{t}{1 - t} .

Bijgevolg is

\abs{p_0^{(n)} - p_0} \leq \frac{2t}{1 - t} + \abs{G_{X_n}(t) - G_X(t)} .

Gegeven $\varepsilon > 0$ , kies $t$ met $\frac{2t}{1-t} < \frac\varepsilon2$ , en dan $n_0$ zodanig dat de laatste term $< \frac\varepsilon2$ is voor $n \geq n_0$ : dus $p_0^{(n)} \to p_0$ .

Inductiestap. Neem aan dat $p_j^{(n)} \to p_j$ voor $j < k$ . Beschouw de verschoven functies

g_n(t) = \frac{G_{X_n}(t) - p^{(n)}_0}{t} = \sum_{j\geq0} p^{(n)}_{j+1}t^j, \qquad g(t) = \frac{G_X(t) - p_0}{t} ,

genererende functies van de rijen deelkansen $(p^{(n)}_{j+1})_j$ (totale massa $\leq 1$ , en meer gebruikte het argument voor $k = 0$ niet). Voor vaste $t \in \intoo{0}{1}$ is $g_n(t) \to g(t)$ wegens de hypothese en het geval $k = 0$ . Het argument voor $k = 0$ toepassen op $g_n$ geeft $p_1^{(n)} \to p_1$ ; de verschuiving $k$ maal herhalen geeft $p_k^{(n)} \to p_k$ voor elke $k$ . (Dit is het discrete, elementaire geval van de continuïteitsstelling van Lévy, waarvan de algemene vorm — voor karakteristieke functies — een mijlpaal van bachelorjaar 3 is.)

Oefening 23.10 ★

(Pariteitstruc) Toon aan dat voor een veranderlijke $X$ met waarden in $\N$

\P(X \text{ even}) = \frac{1 + G_X(-1)}{2}

geldt, en bereken deze kans voor $X \sim \mathcal P(\lambda)$ en $X \sim \mathcal B(n, p)$ . Wat betekent $G_X(-1) \to 0$ in kansrekenkundige termen?

Oplossing

Oplossing van Oefening 23.10.

Puntsgewijs is $\frac{1 + (-1)^X}{2}$ gelijk aan $1$ wanneer $X$ even is en $0$ wanneer zij oneven is, dus geeft verwachtingswaarden nemen (overdracht)

\P(X \text{ even}) = \frac{1 + \E\bigl((-1)^X\bigr)}2 = \frac{1 + G_X(-1)}2 .

Poisson: $\frac{1 + \eu^{-2\lambda}}2 \to \frac12$ als $\lambda$ groeit. Binomiaal: $\frac{1 + (1 - 2p)^n}2$ . In beide gevallen zegt $G_X(-1) \to 0$ dat de pariteit van $X$ een eerlijke munt wordt: de verdeling spreidt zich over veel gehele getallen uit en vergeet haar pariteit.

Oefening 23.11 ★★

(Dobbelstenen van Sicherman) Ga de ontbinding van de genererende functie van de eerlijke dobbelsteen na,

\frac{t + t^2 + \dots + t^6}{6} = \frac{t\,(1 + t)(1 + t + t^2)(1 - t + t^2)}{6},

en toon aan dat de twee dobbelstenen met zijden $\{1, 2, 2, 3, 3, 4\}$ en $\{1, 3, 4, 5, 6, 8\}$ als genererende functies $\frac{t(1+t)(1+t+t^2)}6$ en $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6$ hebben, waarvan het product dat van twee gewone dobbelstenen is: deze exotische dobbelstenen brengen elke som $2, \dots, 12$ voort met precies de gewone kansen.

Oplossing

Oplossing van Oefening 23.11.

$t + \dots + t^6 = t\,\frac{1 - t^6}{1 - t}$ en $1 - t^6 = (1 - t)(1 + t)(1 + t + t^2)(1 - t + t^2)$ , wat de gestelde ontbinding geeft. Voor de eerste dobbelsteen is $(1 + t)(1 + t + t^2) = 1 + 2t + 2t^2 + t^3$ , dus $\frac{t(1+t)(1+t+t^2)}6 = \frac{t + 2t^2 + 2t^3 + t^4}6$ : zijden $\{1, 2, 2, 3, 3, 4\}$ . Voor de tweede geeft uitwerken

(1 + 2t + 2t^2 + t^3)(1 - t + t^2)^2 = 1 + t^2 + t^3 + t^4 + t^5 + t^7,

dus $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6 = \frac{t + t^3 + t^4 + t^5 + t^6 + t^8}6$ : zijden $\{1, 3, 4, 5, 6, 8\}$ . Het product van de twee genererende functies hergroepeert de zes factoren tot $\bigl(\frac{t(1+t)(1+t+t^2)(1-t+t^2)}6 \bigr)^2$ , het kwadraat van de functie van de gewone dobbelsteen: het paar van Sicherman heeft voor de som precies de gewone verdeling — genererende functies klasseren al zulke hergroeperingen.

Oefening 23.12 ★★★

(Wachten op twee maal kop op rij) Met een munt met kanskop $p$ wordt geworpen tot er tweemaal achter elkaar kop verschijnt; zij $T$ het aantal worpen (het spel van Oefening 21.6). Leid, door voorwaardelijk op de eerste worpen te stellen, een lineair stelsel af voor de genererende functies vanuit de toestanden “geen lopende kop” en “één lopende kop”, en besluit dat

G_T(t) = \frac{p^2t^2}{1 - qt - pqt^2} \qquad (q = 1 - p);

ga $G_T(1) = 1$ en $\E(T) = \dfrac{1 + p}{p^2}$ na ( $= 6$ voor een eerlijke munt).

Oplossing

Oplossing van Oefening 23.12.

Zijn $A$ en $B$ de genererende functies van de resterende duur vanuit “geen lopende kop” en “één lopende kop”. Eén worp gaat eraan op, en dan: vanuit toestand $0$ keert munt terug naar toestand $0$ en gaat kop naar toestand $1$ ; vanuit toestand $1$ beëindigt kop het spel en keert munt terug naar toestand $0$ :

A(t) = t\bigl(q\,A(t) + p\,B(t)\bigr), \qquad B(t) = t\bigl(p + q\,A(t)\bigr).

Substitueren geeft $A(1 - qt) = pt\,B = pt(pt + qtA)$ , dus

G_T(t) = A(t) = \frac{p^2t^2}{1 - qt - pq\,t^2} .

In $t = 1$ is de noemer $1 - q - pq = p(1 - q) = p^2$ : $G_T(1) = 1$ , het spel eindigt bijna zeker (zoals Oefening 21.6 met een recursie toonde). Logaritmisch differentiëren in $1$ : $\E(T) = 2 - \frac{D'(1)}{D(1)}$ met $D(t) = 1 - qt - pqt^2$ en $D'(1) = -q - 2pq$ :

\E(T) = 2 + \frac{q + 2pq}{p^2} = \frac{2p^2 + q + 2pq}{p^2} = \frac{1 + p}{p^2},

wat $6$ is voor $p = \frac12$ .

23.6 Probleem: het proces van Galton en Watson, opgelost

Probleem 23.1

Weekendopgave — groeitempo’s, exacte oplossingen, totale nakomelingschap en de kritieke schatting van Kolmogorov

Het uitstervingscriterium (Stelling 23.25) splitst vertakkingsprocessen in subkritisch, kritisch en superkritisch — maar het zegt niets over tempo’s: hoe snel een gedoemde lijn sterft, hoe groot een overlevende wordt. Deze opgave berekent ze. Wij houden de notatie van het hoofdstuk aan: nakomelingenverdeling $(p_k)$ met genererende functie $G$ , gemiddelde $m = G'(1)$ , generatiegroottes $Z_n$ ( $Z_0 = 1$ ), iteranten $G_n = G_{Z_n}$ , en uitstervingskansen $q_n = \P(Z_n = 0) \uparrow q$ ; wij nemen altijd $p_1 \neq 1$ aan en, waar tweede momenten optreden, $G''(1) < \infty$ , en wij schrijven $\sigma^2 = V(Z_1)$ .

Deel I — Momenten van de generaties.

Toon aan dat $\E(Z_n) = m^n$ (kettingregel op $G_n = G \circ G_{n-1}$ in $1^-$ , met $G_{n-1}(1) = 1$ en Stelling 23.7).
Stel de recursie $G_n''(1) = G''(1)\,m^{2(n-1)} + m\,G_{n-1}''(1)$ op en los haar op: $G_n''(1) = G''(1)\,m^{n-1}\dfrac{m^n - 1}{m - 1}$ voor $m \neq 1$ , en $G_n''(1) = n\,G''(1)$ voor $m = 1$ .
Leid af dat

$V(Z_n) = \sigma^2m^{n-1}\,\frac{m^n - 1}{m - 1} \quad (m \neq 1), \qquad V(Z_n) = n\,\sigma^2 \quad (m = 1).$
(Subkritisch tempo, bovengrens) Toon voor $m < 1$ aan dat $\P(Z_n > 0) \leq m^n$ (Markov op de geheeltallige $Z_n$ ): het uitsterven is zeker, met een meetkundig tempo — een kwantitatieve verfijning van het criterium van het hoofdstuk.
(Subkritisch tempo, ondergrens) Toon met Cauchy–Schwarz op $Z_n\mathbf 1_{Z_n > 0}$ aan dat

$\P(Z_n > 0) \geq \frac{\E(Z_n)^2}{\E(Z_n^2)} \geq c\,m^{n} \quad\text{met}\quad c = \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1} :$

het meetkundige tempo $m^n$ is op constanten na exact.

Deel II — De meetkundige familie, exact opgelost. Zij de nakomelingenverdeling meetkundig op $\N$ : $p_k = qp^k$ ( $k \geq 0$ ), met $0 < p < 1$ en $q = 1 - p$ .

Bereken $G(t) = \dfrac{q}{1 - pt}$ en $m = \dfrac pq$ ; lokaliseer de drie regimes in termen van $p$ .
Los $G(t) = t$ op: toon aan dat de vaste punten $1$ en $q/p = 1/m$ zijn, en vind de uitstervingskans $q_{\mathrm{uit}} = \min(1, 1/m)$ terug.
Bewijs met inductie de gesloten vormen

$q_n = \frac{m^n - 1}{m^{n+1} - 1} \quad (m \neq 1), \qquad q_n = \frac{n}{n+1} \quad (m = 1).$
Leid de exacte tempo’s af: $1 - q_n \sim (1 - m)\,m^n$ in het subkritische geval, en $q_{\mathrm{uit}} - q_n \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ in het superkritische geval; ga na dat de superkritische contractieverhouding $G'(q_{\mathrm{uit}}) = 1/m$ is.
Kritiek geval ( $p = \tfrac12$ ): bereken $\sigma^2 = 2$ en merk op dat $1 - q_n = \frac1{n+1}$ : het overleven vervalt als $\frac1n$ — noch meetkundig, noch sommeerbaar.
Nog steeds kritiek: bewijs met inductie de volledige iterant

$G_n(t) = \frac{n - (n-1)t}{n + 1 - nt},$

en leid af dat $Z_n$ , onder de voorwaarde van overleven, meetkundig is op $\N^*$ met parameter $\frac1{n+1}$ :

$\P(Z_n = k \mid Z_n > 0) = \frac1{n+1} \Bigl(\frac{n}{n+1}\Bigr)^{k-1}, \qquad \E(Z_n \mid Z_n > 0) = n + 1 .$

De gemiddelde lijn sterft, maar de overlevende lijnen hebben een grootte van de orde $n$ .

Deel III — Totale nakomelingschap. Zij $Y = \sum_{n\geq0}Z_n \in \N^* \cup \{\infty\}$ het totale aantal individuen dat ooit geboren wordt, en $H(t) = \sum_{k\geq1}\P(Y = k)t^k$ .

Verantwoord dat $\P(Y < \infty) = q_{\mathrm{uit}}$ , en herinner je uit Oefening 23.7 de functionaalvergelijking $H(t) = t\,G(H(t))$ (waarvan de afleiding $m < 1$ niet gebruikte).
(Binaire vertakking) Los voor $p_0 = p_2 = \frac12$ (kritiek) de functionaalvergelijking op:

$H(t) = \frac{1 - \sqrt{1 - t^2}}{t},$

en ontwikkel haar met Voorbeeld 11.21 om

$\P(Y = 2k + 1) = \frac{C_k}{2^{2k+1}}, \qquad C_k = \frac1{k+1}\binom{2k}k$

te krijgen; ga de waarden $\P(Y = 1) = \frac12$ en $\P(Y = 3) = \frac18$ door rechtstreeks tellen na.
Toon, door de functionaalvergelijking in $1^-$ te differentiëren, aan dat $\E(Y) = \frac{1}{1-m}$ voor $m < 1$ , terwijl de kritikaliteit $\E(Y) = \infty$ afdwingt: de kritieke totale nakomelingschap is bijna zeker eindig met oneindig gemiddelde.
Toon met de asymptotiek van de centrale binomiaalcoëfficiënt (Voorbeeld 6.14) aan dat

$\P(Y = 2k+1) \sim \frac{1}{2\sqrt\pi\,k^{3/2}},$

een zware staart $k^{-3/2}$ , en leid af dat $\P(Y > n) \asymp n^{-1/2}$ (boven- en ondergrenzen van deze orde volstaan).
Vergelijk met de eerlijke toevalswandeling (de weekendopgave van Hoofdstuk 21): daar zekere terugkeertijden met oneindig gemiddelde, hier een zekere totale nakomelingschap met oneindig gemiddelde, beide met lokale verdelingen $n^{-3/2}$ . Eén alinea over waarom de kritikaliteit dit handschrift voortbrengt.

Deel IV — De schatting van Kolmogorov bij kritikaliteit. Neem aan dat $m = 1$ en $0 < \sigma^2 = G''(1) < \infty$ .

Toon aan dat $G''$ zich continu uitbreidt tot $\intcc01$ (niet-negatief en stijgend met eindige limiet) en leid de ontwikkeling van Taylor in $1$ af:

$G(t) = t + b\,(1-t)^2 + o\bigl((1-t)^2\bigr), \qquad b = \frac{G''(1)}2 = \frac{\sigma^2}2 .$
Zet voor $t \in \intco01$ de functie $h(t) = \dfrac1{1 - G(t)} - \dfrac1{1 - t}$ . Toon aan dat

$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)} \xrightarrow[t\to1^-]{} b .$
Telescopeer langs de iteratie $q_{j+1} = G(q_j)$ :

$\frac1{1 - q_n} = 1 + \sum_{j=0}^{n-1}h(q_j),$

en besluit met een argument van Cesàro dat

$\P(Z_n > 0) = 1 - q_n \sim \frac{2}{\sigma^2\,n}$

— de schatting van Kolmogorov: elk kritiek vertakkingsproces sterft met het universele tempo $1/n$ , waarbij alleen de constante zich de nakomelingenverdeling herinnert.
Toets de schatting aan het kritieke meetkundige geval van vraag 10.
Leid af dat $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n} \sim \dfrac{\sigma^2 n}{2}$ (merk op dat $\E(Z_n \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$ ), en toets dit aan vraag 11: onder de voorwaarde van overleven groeit de populatie lineair — het kritieke koorddansen tussen dood en explosie.

Deel V — Toepassingen en synthese.

(Epidemieën, kettingreacties) Schrijf voor een poisson-nakomelingenverdeling $\mathcal P(\lambda)$ — elk geval besmet $\mathcal P(\lambda)$ nieuwe gevallen — de uitstervingsvergelijking $q = \eu^{\lambda(q-1)}$ op en los haar numeriek op voor $\lambda = 1.5$ ( $q \approx 0.417$ ) en $\lambda = 2$ ( $q \approx 0.203$ ): vanaf één geval is een grote uitbraak niet zeker, zelfs niet wanneer $\lambda > 1$ . Leg uit waarom de iteratie $q_{n+1} = \eu^{\lambda(q_n - 1)}$ vanaf $q_0 = 0$ naar het juiste nulpunt convergeert.
Toon aan dat de uitstervingskans, uitgaande van $k$ voorouders in plaats van één, gelijk is aan $q^k$ . Toepassing: hoeveel beginnende gevallen maken bij $\lambda = 1.5$ een uitbraak minstens $99\%$ waarschijnlijk?
(Een superkritisch proces voorwaardelijk stellen op uitsterven) Bewijs voor $m > 1$ met uitstervingskans $q \in \intoo01$ eerst met de convexiteit dat $G'(q) < 1$ in het kleinste vaste punt, en leid af dat $q_{\mathrm{uit}} - q_n = O\bigl(G'(q)^n\bigr)$ (meetkundige convergentie, zoals vraag 9 illustreerde). Toon vervolgens aan dat $\widehat G(t) = G(qt)/q$ de genererende functie is van een echte nakomelingenverdeling, met gemiddelde $\widehat m = G'(q) < 1$ : een subkritisch begeleidend proces. Ga dit na op de meetkundige familie: het superkritische $(p, q)$ -proces voorwaardelijk stellen op uitsterven verwisselt $p$ en $q$ . (De volledige uitspraak — het voorwaardelijk gestelde proces is het begeleidende proces — wordt in het volume van bachelorjaar 3 bewezen; hier heb je haar schaduw op de genererende functies nagegaan.)
Synthese: stel de tabel van de driedeling op — voor $m < 1$ , $m = 1$ , $m > 1$ : de waarde van $q$ ; het tempo van $\P(Z_n > 0)$ of van $q - q_n$ ; $\E(Y)$ ; de grootte van een overlevende generatie. Formuleer in één zin per gereedschap hoe de samenstelling van genererende functies, de convexiteit, Taylor in $1^-$ en het middelen volgens Cesàro de hele opgave hebben gedragen, en wat het volume van bachelorjaar 3 toevoegt (de martingaal $Z_n/m^n$ en de exponentiële limietverdeling van Jaglom).

Oplossing

Oplossing van Probleem 23.1.

1. Voor $t \in \intoo01$ geeft de kettingregel op $G_n = G \circ G_{n-1}$ dat $G_n'(t) = G'\bigl(G_{n-1}(t)\bigr)G_{n-1}'(t)$ . Als $t \to 1^-$ is $G_{n-1}(t) \uparrow 1$ , en $G'$ is niet-dalend met linkerlimiet $m$ in $1$ , dus streeft de eerste factor naar $m$ ; met inductie streeft de tweede naar $m^{n-1}$ . Volgens Stelling 23.7 is $\E(Z_n) = G_n'(1^-) = m^n$ .

2. Nog eens differentiëren geeft

G_n'' = G''(G_{n-1})\,(G_{n-1}')^2 + G'(G_{n-1})\,G_{n-1}'',

en $t \to 1^-$ laten gaan: $a_n = G''(1)m^{2(n-1)} + m\, a_{n-1}$ met $a_n = G_n''(1)$ en $a_1 = G''(1)$ . Voor $m \neq 1$ gaat men met inductie na dat $a_n = G''(1)\,m^{n-1} \frac{m^n - 1}{m - 1}$ (de recursie telt $G''(1)m^{2n-2}$ op bij $m\cdot G''(1)m^{n-2}\frac{m^{n-1}-1}{m-1}$ , en $m^{n-1} + \frac{m^{n-1}-1}{m-1} = \frac{m^n - 1}{m-1}$ ); voor $m = 1$ is $a_n = a_{n-1} + G''(1) = n\,G''(1)$ .

3. $V(Z_n) = a_n + m^n - m^{2n}$ en $G''(1) = \sigma^2 + m^2 - m$ . Voor $m \neq 1$ heft het stuk $(m^2 - m)m^{n-1}\frac{m^n-1}{m-1} = m^n(m^n - 1)$ precies $m^n - m^{2n}$ op, waardoor $V(Z_n) = \sigma^2m^{n-1}\frac{m^n-1}{m-1}$ overblijft. Voor $m = 1$ : $V(Z_n) = nG''(1) = n\sigma^2$ .

4. $Z_n$ is een niet-negatieve geheeltallige veranderlijke, dus $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ volgens Markov (Stelling 22.15). Voor $m < 1$ vervalt dit meetkundig — en sommeerbaar, zodat Borel–Cantelli zelfs geeft dat slechts eindig veel generaties niet leeg zijn, wat opnieuw het uitsterven is.

5. Cauchy–Schwarz: $\E(Z_n)^2 = \E(Z_n\mathbf 1_{Z_n>0})^2 \leq \E(Z_n^2)\,\P(Z_n > 0)$ . Met vraag 3 en $m < 1$ :

\E(Z_n^2) = V(Z_n) + m^{2n} \leq \frac{\sigma^2m^{n-1}}{1-m} + m^{2n},

dus, $m^{2n}$ door deze grens delen en met $m^n$ vereenvoudigen:

\P(Z_n > 0) \geq \frac{m^n}{\frac{\sigma^2}{m(1-m)} + m^n} \geq \Bigl(\frac{\sigma^2}{m(1-m)} + 1\Bigr)^{-1}m^n ,

met $m^n \leq 1$ in de noemer. Samen met vraag 4: $\P(Z_n > 0) \asymp m^n$ .

6. $G(t) = q\sum_k(pt)^k = \frac{q}{1 - pt}$ , en $m = G'(1) = \frac{pq}{(1-p)^2} = \frac pq$ . Subkritisch voor $p < \frac12$ , kritisch voor $p = \frac12$ , superkritisch voor $p > \frac12$ .

7. $G(t) = t$ luidt $pt^2 - t + q = 0$ , met nulpunten $\frac{1 \pm \abs{p - q}}{2p}$ , dat wil zeggen $1$ en $\frac qp = \frac1m$ . De uitstervingskans is het kleinste vaste punt in $\intcc01$ (Stelling 23.25): $q_{\mathrm{uit}} = 1$ als $m \leq 1$ , en $\frac1m$ als $m > 1$ .

8. Voor $m \neq 1$ , met $p = \frac m{m+1}$ en $q = \frac1{m+1}$ : is $q_n = \frac{m^n - 1}{m^{n+1} - 1}$ , dan is

1 - p\,q_n = \frac{(m+1)(m^{n+1} - 1) - m(m^n - 1)} {(m+1)(m^{n+1} - 1)} = \frac{m^{n+2} - 1}{(m+1)(m^{n+1} - 1)},

dus $q_{n+1} = \frac{q}{1 - pq_n} = \frac{m^{n+1} - 1}{m^{n+2} - 1}$ ; het basisgeval $q_0 = 0$ klopt. Voor $m = 1$ : $G(t) = \frac1{2 - t}$ en $q_{n+1} = \frac1{2 - \frac{n}{n+1}} = \frac{n+1}{n+2}$ , met $q_0 = 0$ .

9. $1 - q_n = \frac{m^n(m - 1)}{m^{n+1} - 1}$ . Voor $m < 1$ streeft de noemer naar $-1$ : $1 - q_n \sim (1 - m)\,m^n$ . Voor $m > 1$ :

q_{\mathrm{uit}} - q_n = \frac1m - \frac{m^n - 1}{m^{n+1} - 1} = \frac{m - 1}{m\,(m^{n+1} - 1)} \sim \frac{m - 1}{m^{2}}\;m^{-n} .

En $G'(t) = \frac{pq}{(1 - pt)^2}$ geëvalueerd in $t = \frac qp$ (waar $1 - pt = 1 - q = p$ ) geeft $G'(q_{\mathrm{uit}}) = \frac qp = \frac1m$ : de waargenomen verhouding $m^{-1}$ is precies de afgeleide in het aantrekkende vaste punt.

10. Voor $p = \frac12$ : $G''(t) = \frac{1/4}{(1 - t/2)^3}$ , dus $G''(1) = 2$ en $\sigma^2 = G''(1) + m - m^2 = 2$ . De gesloten vorm geeft $1 - q_n = \frac1{n+1}$ : de overlevingskans vervalt als $1/n$ — te traag om sommeerbaar te zijn, anders dan elk subkritisch tempo.

11. Inductie: $G_1(t) = \frac1{2-t}$ past bij de formule voor $n = 1$ , en

G(G_n(t)) = \cfrac{1}{2 - \cfrac{n - (n-1)t}{n+1 - nt}} = \frac{n + 1 - nt}{2(n+1) - 2nt - n + (n-1)t} = \frac{n+1 - nt}{n + 2 - (n+1)t} .

Dan is

\frac{G_n(t) - q_n}{1 - q_n} = (n+1)\,\Bigl(\frac{n - (n-1)t}{n+1 - nt} - \frac{n}{n+1}\Bigr) = \frac{t}{n + 1 - nt} = \frac{\frac{t}{n+1}}{1 - \frac{n}{n+1}t} ,

de genererende functie van de meetkundige verdeling $\mathcal G\bigl(\frac1{n+1} \bigr)$ op $\N^*$ (Voorbeeld 23.4): gegeven het overleven is $\P(Z_n = k \mid Z_n > 0) = \frac1{n+1}\bigl(\frac n{n+1}\bigr)^{k-1}$ , met voorwaardelijk gemiddelde $n + 1$ . Het onvoorwaardelijke gemiddelde $1 = \E(Z_n)$ is het product van een verdwijnende overlevingskans en een lineair groeiende voorwaardelijke grootte.

12. Sterft de lijn in generatie $n$ uit, dan is $Y = Z_0 + \dots + Z_{n-1}$ eindig; sterft zij nooit uit, dan is $Y \geq \sum_n 1 = \infty$ . Dus is $\{Y < \infty\}$ de uitstervingsgebeurtenis en $\P(Y < \infty) = q_{\mathrm{uit}}$ . De afleiding van $H(t) = tG(H(t))$ in Oefening 23.7 — de voorouder draagt de factor $t$ bij, haar kinderen stichten onafhankelijke kopieën van $Y$ , geteld via $G$ — gebruikte alleen Stelling 23.17, geldig in elk regime.

13. Met $G(s) = \frac{1 + s^2}2$ luidt de vergelijking $tH^2 - 2H + t = 0$ , dus $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (het nulpunt met $H(0) = 0$ ). Vergelijking met de reeks van Catalan $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ (Voorbeeld 11.21): $H(t) = \frac t2\,C\bigl(\frac{t^2}4\bigr) = \sum_{k\geq0}C_k\,\frac{t^{2k+1}}{2^{2k+1}}$ , dat wil zeggen $\P(Y = 2k+1) = C_k2^{-2k-1}$ . Controles: $\P(Y = 1) = C_0/2 = \frac12$ (de voorouder heeft geen kind); $\P(Y = 3) = C_1/8 = \frac18$ (twee kinderen, beide kinderloos: $\frac12\cdot\frac12\cdot \frac12$ ).

14. $H = tG(H)$ differentiëren op $\intoo01$ en $t \to 1^-$ laten gaan (monotone limieten als in Stelling 23.7): $H'(1)\bigl(1 - G'(H(1))\bigr) = G(H(1))$ . In het subkritische geval is $H(1) = 1$ en $\E(Y) = H'(1) = \frac1{1 - m}$ . In het kritieke geval maakt $G'(1) = 1$ de linkerfactor nul terwijl het rechterlid $1$ is: er kan geen eindige $H'(1)$ bestaan, dus $\E(Y) = \infty$ — en toch is $\P(Y < \infty) = q = 1$ .

15. $C_k = \frac1{k+1}\binom{2k}k \sim \frac{4^k}{\sqrt\pi\,k^{3/2}}$ volgens Voorbeeld 6.14, dus

\P(Y = 2k+1) = \frac{C_k}{2\cdot4^{k}} \sim \frac1{2\sqrt\pi\,k^{3/2}} .

De staart sommeren (vergelijking met $\int_K^\infty k^{-3/2}\dd k = 2K^{-1/2}$ , van boven en van onder): $\P(Y > 2K) \asymp K^{-1/2}$ , dat wil zeggen $\P(Y > n) \asymp n^{-1/2}$ — een zware staart met oneindig gemiddelde, wat vraag 14 kwantificeert.

16. Beide kritieke objecten — de terugkeertijd van de eerlijke wandeling (de weekendopgave van Hoofdstuk 21) en de kritieke totale nakomelingschap — zijn bijna zeker eindig met oneindig gemiddelde, met lokale verdelingen van exponent $-3/2$ en staarten van exponent $-1/2$ . Dat is geen toeval: een stamboom kind voor kind verkennen brengt een $\pm1$ -pad voort (één stap omhoog per geboorte, één omlaag per sterfte), dat precies een eerlijke wandeling is, en $Y$ wordt een eerste doorgangstijd. Kritikaliteit betekent drift nul: het proces staat altijd op de rand van zowel uitsterven als explosie, en de fluctuaties op de vierkantswortelschaal van toeval zonder drift brengen precies deze exponenten voort.

17. $G''(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ heeft niet-negatieve termen, dus is zij niet-dalend op $\intco01$ met eindige limiet $G''(1) = \sigma^2$ (de kritikaliteit maakt $\E Z_1(Z_1 - 1) = \sigma^2$ ); een niet-dalende functie waarvan de limiet gelijk is aan de randwaarde, is continu in $1$ . Taylor met integraalrest in het punt $1$ :

G(t) = 1 + (t - 1) + \int_1^t(t - s)G''(s)\,\dd s = t + \frac{G''(1)}2(1-t)^2 + o\bigl((1-t)^2\bigr),

omdat $G''(s) = G''(1) + o(1)$ als $s \to 1^-$ .

18. Onder één noemer brengen geeft $h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}$ . Volgens vraag 17 is de teller $b(1-t)^2 + o((1-t)^2)$ en $1 - G(t) = (1 - t)\bigl(1 - b(1-t) + o(1-t)\bigr)$ , dus $h(t) \to b$ .

19. Per definitie van $h$ in $t = q_j$ en met $G(q_j) = q_{j+1}$ : $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$ ; sommeren vanaf $j = 0$ ( $q_0 = 0$ ) geeft de getoonde formule. Omdat het kritieke proces uitsterft, is $q_j \uparrow 1$ , dus $h(q_j) \to b$ en streeft het gemiddelde van Cesàro $\frac1n\sum_{j<n}h(q_j)$ naar $b$ : $\frac1{1-q_n} \sim bn$ , dat wil zeggen

\P(Z_n > 0) \sim \frac1{bn} = \frac{2}{\sigma^2 n} .

20. Kritiek meetkundig geval: $\sigma^2 = 2$ (vraag 10), dus voorspelt Kolmogorov $1 - q_n \sim \frac1n$ — en de exacte waarde is $\frac1{n+1}$ .

21. Omdat $Z_n\mathbf 1_{Z_n > 0} = Z_n$ , is $\E(Z_n \mid Z_n > 0) = \frac{\E(Z_n)}{\P(Z_n > 0)} = \frac1{1 - q_n} \sim \frac{\sigma^2n}2$ . In het meetkundige geval is dit $n + 1$ , wat precies met vraag 11 overeenstemt ( $\sigma^2 = 2$ ). Het kritieke beeld: het uitsterven is zeker, de gemiddelde grootte staat vast op $1$ , en de zeldzame overlevende lijnen hebben een lineair groeiende grootte — de twee factoren houden elkaar in evenwicht.

22. Voor nakomelingen $\mathcal P(\lambda)$ is $G(t) = \eu^{\lambda(t-1)}$ en is de uitstervingskans het kleinste nulpunt van $q = \eu^{\lambda(q-1)}$ . Numeriek: $\lambda = 1.5$ geeft $q \approx 0.417$ (itereer $q \mapsto \eu^{1.5(q-1)}$ : $0, 0.223, 0.312, 0.356, \dots \to 0.4172$ ); $\lambda = 2$ geeft $q \approx 0.203$ . Eén beginnend geval ontsteekt dus een grote uitbraak met kans $58\%$ ( $\lambda = 1.5$ ) of $80\%$ ( $\lambda = 2$ ) — waarschijnlijk, niet zeker. De iteratie vanaf $q_0 = 0$ convergeert naar het kleinste nulpunt omdat $G$ niet-dalend is: met inductie is $q_n \leq r$ voor elk vast punt $r$ , en $(q_n)$ stijgt (zij is $\P(Z_n = 0)$ ), dus is haar limiet een vast punt onder alle andere.

23. De $k$ voorouders stichten onafhankelijke stambomen, en het totale uitsterven is de doorsnede van $k$ onafhankelijke uitstervingsgebeurtenissen: kans $q^k$ . Voor $\lambda = 1.5$ : een uitbraakkans $1 - q^k \geq 0.99$ vereist $q^k \leq 0.01$ , dat wil zeggen $k \geq \frac{\ln 0.01}{\ln 0.417} \approx 5.3$ : zes beginnende gevallen maken de uitbraak voor $99\%$ zeker.

24. $G'(q) < 1$ : $G - \mathrm{id}$ is convex en verdwijnt in $q$ en $1$ , dus is zij $\leq 0$ op $\intcc q1$ ; was $G'(q) = 1$ , dan zou de raaklijn in $q$ (die de convexiteit onder $G$ legt) $G(t) \geq t$ op $\intcc q1$ afdwingen, en dus $G \equiv \mathrm{id}$ daar, wat alle coëfficiënten $p_n$ ( $n \geq 2$ ) doodt en $m > 1$ tegenspreekt. Meetkundige convergentie: $q_n < q$ voor alle $n$ (inductie, $G$ stijgend), en de middelwaardestelling geeft $q - q_{n+1} = G'(c_n)(q - q_n)$ met $c_n \in \intoo{q_n}q$ , dus $G'(c_n) \leq G'(q) < 1$ en $q - q_n \leq q\,G'(q)^n$ . Begeleidend proces: $\widehat G(t) = G(qt)/q = \sum_kp_kq^{k-1}t^k$ heeft niet-negatieve coëfficiënten en $\widehat G(1) = G(q)/q = 1$ : een genererende functie; haar gemiddelde is $\widehat G'(1) = G'(q) < 1$ : subkritisch. Meetkundige familie: $G(t) = \frac{q}{1-pt}$ , $q_{\mathrm{uit}} = \frac qp$ , en

\widehat G(t) = \frac pq\cdot\frac{q}{1 - p\frac qp t} = \frac{p}{1 - qt} :

de meetkundige nakomelingenverdeling met $p$ en $q$ verwisseld — het superkritische proces, bekeken op zijn uitstervingsgebeurtenis, is het gespiegelde subkritische proces.

25. De tabel: $m < 1$ : $q = 1$ , $\P(Z_n > 0) \asymp m^n$ (vragen 4–5), $\E(Y) = \frac1{1-m}$ , en overlevende generaties met begrensd voorwaardelijk gemiddelde. $m = 1$ : $q = 1$ , $\P(Z_n > 0) \sim \frac2{\sigma^2n}$ (Kolmogorov), $\E(Y) = \infty$ met $\P(Y > n) \asymp n^{-1/2}$ , en overlevenden van grootte $\sim \frac{\sigma^2n}2$ . $m > 1$ : $q < 1$ is het kleinste vaste punt, $q - q_n = O(G'(q)^n)$ , groei $\E(Z_n) = m^n$ , en voorwaardelijk op sterven is het proces het subkritische begeleidende proces (vraag 24). De gereedschappen: de samenstelling van genererende functies maakte van de populatierecursie een iteratie van functies; de convexiteit legde de meetkunde van de vaste punten vast; Taylor in $1^-$ zette hypothesen over momenten om in lokale ontwikkelingen; en het middelen volgens Cesàro haalde de $1/n$ van Kolmogorov uit een telescoperende som. Het volume van bachelorjaar 3 voegt de martingaal $Z_n/m^n$ toe — waarvan de bijna-zekere limiet $\E(Z_n) = m^n$ verfijnt tot een groeitempo baan voor baan — en de stelling van Jaglom, de limietverdeling achter de voorwaardelijke meetkunde die in vraag 11 werd waargenomen.

Begrippen gedefinieerd in dit hoofdstuk

Kansgenererende functie

Bekijk alle 395 begrippen in de begrippenlijst