Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

23Kansgenererende functies

De machtreeksen van Hoofdstuk 11 keren terug met een probabilistische missie: aan een $\N$ -waardige stochastische variabele koppelen we de machtreeks met coëfficiënten $\P(X = n)$ . Deze genererende functie zet sommen van onafhankelijke variabelen om in producten, momenten in afgeleiden in $1$ , en harde combinatorische identiteiten in één-regel-vermenigvuldigingen. Het hoofdstuk sluit het boek af met twee pronkstukken: de Poisson-benadering van zeldzame gebeurtenissen, en het uitstervingscriterium voor vertakkingsprocessen — een werkelijk oneindige probabilistische berekening, geheel opgelost door de meetkunde van een convexe curve.

23.1 Definitie en basiseigenschappen

Definitie 23.1 (Kansgenererende functie)

Zij $X$ een $\N$ -waardige stochastische variabele, $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 variabele $X = c$ heeft $G_X(t) = t^c$ ; een verschuiving gehoorzaamt $G_{X+c}(t) = t^c\,G_X(t)$ ; en evalueren in speciale 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 uitgebuit in Oefening 23.10. Deze één-regels worden overal hieronder stilzwijgend gebruikt — en de evaluatie $G_X(0)$ is precies hoe uitsterfkansen uit geïtereerde genererende functies aan het eind van het hoofdstuk geëxtraheerd worden.

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}$ , $\mathcal{C}^\infty$ op $\intoo{-1}{1}$ , met $G_X(1) = 1$ en $\abs{G_X(t)} \leq 1$ daar. Bovendien bepaalt $G_X$ de wet van $X$ :

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

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

\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 haar som is daar continu (Stellingen 10.16 en 10.4). Gladheid binnenin en de coëfficiëntenformule zijn de algemene theorie van machtreeksen; omdat de coëfficiënten terugwinbaar zijn, hebben twee variabelen met dezelfde genererende functie dezelfde wet. ∎

Voorbeeld 23.4 (De klassieke wetten)

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 van Newton).
Geometrisch $\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. Uit $\int_0^1t^k\dd t = \frac1{k+1}$ en term-voor-term-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},

in één regel de reeksberekening van Voorbeeld 22.10 herstellend. De genererende functie is een tweerichtingsinstrument: differentieer in $1$ voor de momenten $\E(X)$ , $\E(X(X-1))$ , integreer over $\intcc01$ voor $\E\bigl(\frac1{1+X}\bigr)$ — één analytisch object, bevraagd in welke richting het probleem nodig heeft.

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

Laat $\P(X = k) = \dfrac{6}{\pi^2k^2}$ voor $k \geq 1$ — een waarschijnlijkheidswet door 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 verbeterd worden. 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$ , glad binnenin, maar haar afgeleide blaast op in $1^-$ — de grafiek arriveert in het punt $(1, 1)$ met een verticale raaklijn. Zware staarten zijn meetkundig zichtbaar op de genererende functie, in het enige punt $t = 1$ ; de momentenstelling hieronder maakt deze correspondentie exact.

Stelling 23.7 (Momenten uit de genererende functie)

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

\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 term-voor-term-differentiatie 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 door monotone convergentie van deelsommen (of de stelling van Abel voor niet-negatieve coëfficiënten, Hoofdstuk 11),

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

elke zijde eindig precies wanneer de andere is. Wanneer eindig, knijpt 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)$ (door overdracht). De tweede-orde-uitspraak 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 variantieformule 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 in één regel elk.

Voorbeeld 23.9 (De modus van een Poisson-wet)

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

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

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

23.2 Sommen van onafhankelijke variabelen

Stelling 23.10 (Multiplicativiteit)

Als $X$ en $Y$ onafhankelijke $\N$ -waardige stochastische variabelen zijn, dan

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

en door 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 verwachtingen: $t^X$ en $t^Y$ zijn onafhankelijke begrensde variabelen, 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 wet van $X + Y$ is de convolutie $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$ , en de Cauchy-productstelling voor absoluut convergente reeksen (Hoofdstuk 7) vermenigvuldigt de twee machtreeksen precies langs deze convolutie. ∎

Voorbeeld 23.11 (Stabiliteit van de klassieke wetten)

Onafhankelijke binomialen 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-variabelen binomiaal, wat de wet van het aantal successen opnieuw bewijst. Onafhankelijke Poissons 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 polynoom gekwadrateerd)

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

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 wet van dobbelsteensommen ( $7$ is de modus, met waarschijnlijkheid $\frac6{36} = \frac16$ ), afgelezen van een polynoomkwadraat dat men één keer in een leven uitvermenigvuldigt. De convolutieformule zou elf aparte telargumenten geëist hebben; de genererende functie doet ze allemaal tegelijk, omdat polynomen vermenigvuldigen is coëfficiënten convolueren. Deze mechanische vertaling — wetten naar coëfficiënten, sommen naar producten — is het hele bedrijfsmodel van het hoofdstuk, en Oefening 23.11 duwt haar tot de verrassende Sicherman-dobbelstenen.

Voorbeeld 23.13 (Drie dobbelstenen en een coëfficiëntenextractie)

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$ . Factoriseer en ontwikkel met de binomiale en geometrische 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}$ eist $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 .

Directe enumeratie van de $27$ triples is foutgevoelig; de algebra is mechanisch en schaalt naar elk aantal stenen — de inclusie–exclusie zichtbaar in $(1 - t^6)^3$ doet de gevalsanalyse automatisch.

Voorbeeld 23.14 (Een wet aflezen van haar genererende functie)

Welke wet 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 sommerend tot $G(1) = 1$ , dus dit is een echte wet, $\P(X = k) = 2^{-(k+1)}$ op $\N$ — een geometrische wet startend in $0$ . Door uniciteit (Propositie 23.3) deelt geen andere wet deze $G$ . Wetten herkennen aan hun genererende functies is een vaardigheid die oefening verdient: zo wordt de kritieke vertakkingsiteratie $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ van het weekendprobleem ontmaskerd als een geometrische wet geconditioneerd op overleving.

Opmerking 23.15

Stabiliteit gaat maar één kant op: sommen van onafhankelijke Poissons zijn Poisson, maar verschillen niet — $X - Y$ neemt negatieve waarden, dus heeft helemaal geen genererende functie, en haar wet (de Skellam-verdeling) ligt buiten de gereedschapskist van dit hoofdstuk. Evenzo is $\mathcal B(m, p) + \mathcal B(n, p')$ met $p \neq p'$ niet binomiaal: het product $(1 - p + pt)^m(1 - p' + p't)^n$ heeft twee verschillende wortellocaties, terwijl elke binomiale pgf één herhaalde wortel heeft. Stabiliteit aflezen van wortelpatronen is een kleine vooruitblik op hoeveel structuur het polynoom codeert.

Opmerking 23.16 (Het wortels-van-eenheid-filter)

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

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

omdat middelen van $\omega^{j(k-r)}$ over $j$ $1$ oplevert als $k \equiv r$ en $0$ anders. Voorbeelddividend: voor de som $S$ van twee eerlijke dobbelstenen, 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 van Voorbeeld 23.12 bevestigt — en de methode schaalt naar vragen waar direct tellen dat niet doet.

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

Zij $(X_k)_{k\geq1}$ onafhankelijke $\N$ -waardige variabelen met dezelfde wet en genererende functie $G_X$ , en zij $N$ een $\N$ -waardige variabele onafhankelijk van de $X_k$ , met genererende functie $G_N$ . Dan heeft de stochastische som $S = X_1 + \dots + X_N$ (met $S = 0$ wanneer $N = 0$ ) genererende functie

G_S = G_N \circ G_X .

In het bijzonder, als $N$ en $X_1$ verwachtingen hebben, $\E(S) = \E(N)\,\E(X_1)$ .

Bewijs. Conditioneer op $N$ (totale waarschijnlijkheid, Stelling 21.14): voor $\abs t \leq 1$ ,

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 multiplicativiteit voor elke vaste $n$ en de sommeerbaarheid van de hele dubbele familie ( $\abs{G_X(t)} \leq 1$ ). De verwisseling van sommaties is Fubini voor sommeerbare families (Hoofdstuk 7). Differentiëren in $1^-$ door 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 verzekeringsverliezen)

Een verzekeraar ontvangt $N \sim \mathcal P(\lambda)$ claims in een jaar, elke claim kostend $X_k$ (gehele eenheden, i.i.d., pgf $G_X$ , gemiddelde $\mu$ , onafhankelijk van $N$ ). Door Stelling 23.17 heeft het totale verlies $S$

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

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

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

De variantie betrekt het tweede moment van een enkele claim, niet haar variantie: een samengestelde Poissonsom voelt de occasionele grote claim tweemaal — één keer via hoeveel, één keer via hoe groot. Voor $\lambda = 10$ claims van geometrische wet met gemiddelde $2$ ( $\E X^2 = 6$ ): $\E S = 20$ , $V(S) = 60$ , en Chebyshev (Hoofdstuk 22) levert al bruikbare solvabiliteitsmarges. Dit “willekeurig gestopte som”-patroon is hetzelfde dat de vertakkingsrecursie van Propositie 23.23 zal drijven: compositie van genererende functies is de algebra van stochastische populaties.

Opmerking 23.19

De onafhankelijkheid van $N$ van de sommanden is niet decoratief. Neem $X_k \in \{0, 2\}$ met gelijke waarschijnlijkheden en laat $N = X_1$ (flagrant afhankelijk): dan is $S = X_1 + \dots + X_N$ gelijk aan $0$ wanneer $X_1 = 0$ , en $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. Wanneer het aantal termen mag reageren op de termen zelf, stort de schone productstructuur in — de volle theorie van zulke “stop”-regels is het martingaalhoofdstuk van het Bachelor jaar 3-volume.

23.3 Poisson-benadering

Stelling 23.20 (Wet van zeldzame gebeurtenissen)

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

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

de binomiale wet van vele zeldzame onafhankelijke gebeurtenissen convergeert naar de Poisson-wet van parameter $\lambda$ .

Bewijs. Directe 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 $k$ vast: de eerste factor neigt naar $1$ (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 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, die (voor $\N$ -waardige variabelen) equivalent is aan convergentie van elke $\P(X_n = k)$ ; zie Oefening 23.9. ∎

Opmerking 23.21

Dit is waarom Poisson-wetten tellingen van zeldzame gebeurtenissen modelleren — typefouten per pagina, radioactieve vervallen per seconde, ongelukken per dag op een kruising: elke kans is bijna verwaarloosbaar, kansen zijn talrijk, en alleen het gemiddelde tempo $\lambda$ overleeft in de limiet.

Voorbeeld 23.22 (De Poisson-limiet zien convergeren)

Fixeer $\lambda = 2$ en laat $X_n \sim \mathcal B(n, 2/n)$ . De geen-gebeurtenis-waarschijnlijkheid 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)$ — ontwikkelend, $(1 - 2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — dus voor $n$ in de honderden is het Poisson-model al accuraat tot op de derde cijfer. Dit is de praktische inhoud van de wet van zeldzame gebeurtenissen: de modelleerder kent $n$ en $p$ nooit apart (hoeveel micro-kansen voor een typefout houdt een pagina?), maar alleen hun product $\lambda$ , en de limietwet hangt genadig van niets anders af.

23.4 Vertakkingsprocessen

Beschouw een populatie startend van één voorouder; elk individu heeft, onafhankelijk, een willekeurig aantal kinderen met wet $(p_k)_{k \in \N}$ en genererende functie $G$ (de nakomelingenverdeling). Laat $Z_n$ de grootte van generatie $n$ zijn ( $Z_0 = 1$ ), en laat $m = G'(1) = \E(Z_1)$ het gemiddelde nakomelingenaantal zijn.

Propositie 23.23

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

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

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

Bewijs. Generatie $n + 1$ is de stochastische som van de nakomelingen van de $Z_n$ leden van generatie $n$ , met tellingen onafhankelijk 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 iterate — die, door associativiteit van compositie, even goed gelezen kan worden als $G_{Z_{n+1}} = G \circ G_{Z_n}$ . Evalueren van deze tweede vorm in $0$ : $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)$ door monotone continuïteit (Stelling 21.6), en continuïteit van $G$ op $[0, 1]$ zet $q_{n+1} = G(q_n)$ om in $q = G(q)$ in de limiet. ∎

Voorbeeld 23.24 (Uitsterven zien convergeren)

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

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 uitsterfkans $q = \tfrac12$ . De gaten $q - q_n$ zijn $0.25$ , $0.156$ , $0.105$ , $0.073$ , $0.052$ : elk is ongeveer $\tfrac34$ van de vorige, en inderdaad geeft de middelwaardestelling $q - q_{n+1} = G'(c_n)(q - q_n)$ met $G'(q) = \tfrac14 + q = \tfrac34$ . Twee moralen: een familielijn nog levend in generatie $n$ heeft, ingebouwd in dezelfde berekening, waarschijnlijkheid $q - q_n$ later gedoemd te zijn; en de convergentiesnelheid van de trap in de figuur hieronder is de afgeleide in het vast punt — het weekendprobleem zet beide observaties om in stellingen.

Stelling 23.25 (Uitstervingscriterium)

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

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

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

Kleinste vast punt: laat $r \in \intcc{0}{1}$ enig vast punt zijn. Dan $q_0 = 0 \leq r$ , en inductief $q_{n+1} = G(q_n) \leq G(r) = r$ (monotoniciteit): dus $q = \lim q_n \leq r$ .

Geval $m \leq 1$ : veronderstel $r < 1$ is een vast punt. Door de middelwaardestelling op $[r, 1]$ bestaat $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 $G'$ constant gelijk aan $1$ op $\intco{c}{1}$ , vandaar $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ daar. Een machtreeks met niet-negatieve coëfficiënten die verdwijnt op een interval 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$ — tegensprekend de hypothese $p_1 \neq 1$ . Dus $1$ is het enige vast 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 enig 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 enig $r < 1$ (tussenwaardestelling). Het kleinste vast punt is dan $q \leq r < 1$ . ∎

Uitsterfkansen als een vastpuntiteratie q_n+1 = G(q_n) startend in q_0 = 0 (rode trap). Links: een subkritische nakomelingenwet — de convexe curve blijft boven de diagonaal, de iteratie klimt naar het unieke vast punt 1. Rechts: een superkritische wet — de curve kruist de diagonaal in q < 1, waar de iteratie stopt: overleving heeft waarschijnlijkheid 1 - q > 0. — **Figuur 23.1.** Uitsterfkansen als een vastpuntiteratie $q_{n+1} = G(q_n)$ startend in $q_0 = 0$ (rode trap). Links: een subkritische nakomelingenwet — de convexe curve blijft boven de diagonaal, de iteratie klimt naar het unieke vast punt $1$ . Rechts: een superkritische wet — de curve kruist de diagonaal in $q < 1$ , waar de iteratie stopt: overleving heeft waarschijnlijkheid $1 - q > 0$ .

Opmerking 23.26 (Hoe de cobweb te lezen)

In de figuur past een verticale beweging $G$ toe (van $(q_n, q_n)$ omhoog naar $(q_n, G(q_n))$ ), een horizontale beweging naar de diagonaal zet output om in input: de trap is de recursie $q_{n+1} = G(q_n)$ . Convexiteit van $G$ en $G(1) = 1$ laten slechts twee meetkunden over. Ofwel blijft de curve boven de diagonaal op $\intco01$ (gemiddelde $m \leq 1$ ): de trap heeft nergens te stoppen vóór $1$ . Of de curve kruist in enig $q < 1$ ( $m > 1$ ): de trap is gevangen onder de kruising en convergeert ernaar, met de geometrische snelheid $G'(q) < 1$ gekwantificeerd in Voorbeeld 23.24. Alle analyse van de uitstervingsstelling is zichtbaar in dit ene plaatje — waarom het waard is te tekenen vóór te rekenen.

Voorbeeld 23.27

Nakomelingenwet: geen kind, één kind, twee kinderen met waarschijnlijkheden $\frac14, \frac14, \frac12$ . Dan $m = \frac14 + 1 = \frac54 > 1$ en $G(t) = \frac14 + \frac14 t + \frac12 t^2$ . Vastpunten: $\frac12 t^2 - \frac34 t + \frac14 = 0$ , d.w.z. $2t^2 - 3t + 1 = (2t - 1)(t - 1) = 0$ : $q = \frac12$ . De familielijn sterft uit met waarschijnlijkheid $\frac12$ — en met waarschijnlijkheid $\frac12$ leeft zij voor altijd.

Opmerking 23.28 (Perspectieven binnen dit volume)

Het hoofdstuk is het kruispunt van het boek, en elk ingrediënt kwam van een genoemde plek: de reeksalgebra van Hoofdstuk 7 en Hoofdstuk 11, de waarschijnlijkheid van Hoofdstuk 21 (monotone continuïteit bewijst $q_n \uparrow q$ ) en Hoofdstuk 22 ( $G_X = \E(t^X)$ is een verwachting, multiplicativiteit is de productstelling), de convexiteit van Hoofdstuk 8 via Hoofdstuk 17. Zelfs de zware-staartpathologieën verbinden: de Sint-Petersburgvariabele van het vorige hoofdstuk heeft $G(t) = \sum_k2^{-k}t^{2^k}$ , een perfect convergente reeks op $\intcc01$ waarvan de afgeleide in $1^-$ divergeert — oneindig gemiddelde, in één oogopslag zichtbaar. Eén object, elk gereedschap van het jaar: een passend laatste hoofdstuk.

Opmerking 23.29 (Gangbare valkuilen)

(i) Genererende functies gelden alleen voor $\N$ -waardige variabelen: voor getekende of niet-gehele variabelen verliest het object $\E(t^X)$ haar machtreeksstructuur (Bachelor jaar 3 vervangt haar door transformen aangepast aan $\R$ ). (ii) De eerste sanity-check 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, niet een nieuwe wet. (iii) Bij stochastische sommen telt de compositievolgorde: $G_S = G_N \circ G_X$ , de buitenste functie tellend de termen; de andere kant om is zinloos ( $G_X \circ G_N$ zou items van items tellen). (iv) Multiplicativiteit eist 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 randoperatie: wanneer de straal precies $1$ is, zoals in Voorbeeld 23.6, kan $G'(1^-)$ oneindig zijn, en de monotone-limietformulering van de momentenstelling is geen pedante fijnheid maar de eerlijke uitspraak.

Het volume afsluiten

De genererende functie is een passend eindobject voor dit boek: zij is tegelijk een machtreeks (Hoofdstuk 11), een gereedschap van sommeerbare families (Hoofdstuk 7), een verwachting (Hoofdstuk 22), een convexe functie waarvan de meetkunde uitsterven beslist (Hoofdstuk 8), en een vastpuntiteratie (Hoofdstuk 4). De wiskunde van Bachelor jaar 2 is één vak. Het Bachelor jaar 3-volume zal de deuren openen die hier opzettelijk gesloten gelaten zijn: Lebesgue-integratie (ontladen van de gedomineerde convergenstiestelling van Hoofdstuk 9), maattheoretische waarschijnlijkheid op onaftelbare ruimten, en het volle bewijs van de inverse-functiestelling (Hoofdstuk 15) in de setting van differentiaalmeetkunde.

23.5 Oefeningen

Oefening 23.1 ★

Bereken de genererende functie van de uniforme wet op $\{1, 2, \dots, 6\}$ (een eerlijke dobbelsteen). Toon dat de som van twee eerlijke dobbelstenen niet uniform op $\{2, \dots, 12\}$ kan zijn: factoriseer $G_{X+Y}$ en tel wortels. (Een uniforme som zou $G_X(t)G_Y(t) = \frac{t^2}{11}\sum_{k=0}^{10}t^k$ forceren, waarvan de niet-nul-wortels de $11$ -de eenheidswortels anders dan $1$ zijn — geen van hen reëel — terwijl $G_X/t$ en $G_Y/t$ reële polynomen van graad $5$ zijn, elk minstens één reële wortel bezittend.)

Oplossing

Oplossing van Oefening 23.1.

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

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ëel polynoom van oneven graad $5$ , dus heeft het een reële wortel (tussenwaardestelling; concreet $h(-1) = 0$ ), vandaar heeft $h^2$ een reële wortel. 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 ★

Herstel met genererende functies $\E$ en $V$ voor de binomiale en geometrische wetten (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).

Geometrisch ( $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} ,

overeenkomend met Oefening 22.1 met minder werk.

Oefening 23.3 ★

Twee valse dobbelstenen: is het mogelijk twee dobbelstenen te beladen (onafhankelijk, identiek of niet) zodat hun som uniform is op $\{2, \dots, 12\}$ ? (Zelfde factorisatie-obstructie als in Oefening 23.1: het antwoord is nee zelfs met verschillende beladingen, omdat elke factor $G_X(t)/t$ oneven graad $5$ heeft, dus een reële wortel, terwijl het doel er geen heeft.)

Oplossing

Oplossing van Oefening 23.3.

Nee, zelfs met verschillende beladingen. Veronderstel $X, Y$ zijn wetten op $\{1, \dots, 6\}$ met uniforme som. Dan $G_X(t) = t\,a(t)$ en $G_Y(t) = t\,b(t)$ met $a, b$ reële polynomen van graad ten hoogste $5$ — en hun graden moeten tot $10$ sommeren (de som bereikt $12$ met positieve waarschijnlijkheid), dus $\deg a = \deg b = 5$ , beide oneven. Zoals in Oefening 23.1,

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

zou een reële wortel links forceren (elk reëel polynoom van oneven graad heeft er één) en geen rechts. Dus geen belading van twee onafhankelijke dobbelstenen — gelijk of niet — produceert een uniforme som.

Oefening 23.4 ★★

Zij $X_1, X_2, \dots$ onafhankelijke Bernoulli $\mathcal{B}(p)$ en $N \sim \mathcal{P}(\lambda)$ onafhankelijk van hen. Toon, via Stelling 23.17, dat $S = X_1 + \dots + X_N \sim \mathcal{P}(\lambda p)$ : een Poisson-aantal items, elk gehouden met waarschijnlijkheid $p$ , laat een Poisson-aantal over — verdunning. Bereken ook de wet van de verworpen telling en bewonder: zij is $\mathcal{P}(\lambda(1-p))$ , en men kan tonen dat zij onafhankelijk is van $S$ .

Oplossing

Oplossing van Oefening 23.4.

Door 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)$ . De verworpen telling $D = N - S$ telt dezelfde items gehouden met waarschijnlijkheid $1 - p$ , dus door dezelfde berekening $D \sim \mathcal{P}(\lambda(1 - p))$ . Onafhankelijkheid, direct: voor $j, k \in \N$ ,

\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 wet factort als $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$ . Een Poisson-stroom willekeurig gesplitst levert onafhankelijke Poisson-stromen — een klein wonder constant gebruikt in wachtrijtheorie.

Oefening 23.5 ★★

(Negatief binomiaal) Laat $T_r$ het aantal worpen zijn om $r$ kop te verkrijgen (kopkans $p$ ). Schrijf $T_r$ als som van $r$ onafhankelijke geometrische variabelen, leid af

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 geometrische $\mathcal{G}(p)$ -variabelen (geheugenloosheid: na elke kop herstart het spel), dus $T_r = W_1 + \dots + W_r$ en multiplicativiteit (Stelling 23.10) geeft

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$ ; varianties tellen op door onafhankelijkheid). Ontwikkeling: door de veralgemeende binomiale reeks (Hoofdstuk 11), $(1 - qt)^{-r} = \sum_{m\geq0} \binom{m + r - 1}{r - 1}q^mt^m$ , dus de coëfficiënt van $t^n$ in $p^rt^r(1 - qt)^{-r}$ is (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 wet — combinatorisch: de $r$ -de kop valt op worp $n$ iff de vorige $r - 1$ koppen hun plaatsen kiezen onder de eerste $n - 1$ worpen.

Oefening 23.6 ★★

Voor de nakomelingenwet $p_0 = \frac18$ , $p_1 = \frac38$ , $p_2 = \frac38$ , $p_3 = \frac18$ : bereken $m$ , beslis superkriticiteit, en bereken de uitsterfkans $q$ exact. (Factoriseer de wortel $t = 1$ van $G(t) - t$ uit.)

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 vastpunten lossen $(1 + t)^3 = 8t$ op, d.w.z. $t^3 + 3t^2 - 5t + 1 = 0$ . De gegarandeerde wortel $t = 1$ uitfactoriseren:

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$ . De wortel in $\intco{0}{1}$ is $\sqrt5 - 2 \approx 0.236$ : door Stelling 23.25,

q = \sqrt 5 - 2 .

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

Oefening 23.7 ★★★

(Totale nakomelingschap) In een subkritisch vertakkingsproces ( $m < 1$ ), laat $Y = \sum_{n\geq0} Z_n$ het totale aantal ooit geboren individuen zijn. Toon $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (rechtvaardig de verwisseling van 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 zijn kinderen, die onafhankelijke kopieën van $Y$ zijn.)

Oplossing

Oplossing van Oefening 23.7.

Verwachting. Eerst $\E(Z_n) = m^n$ : door Stelling 23.17, $\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 Fubini voor families past onvoorwaardelijk toe:

\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: consistent met zeker uitsterven in het subkritische geval).

Functionaalvergelijking. Ontbind de populatie naar de kinderen van de voorouder: als de voorouder $Z_1 = k$ kinderen heeft, is de totale nakomelingschap $Y = 1 + Y_1 + \dots + Y_k$ , waar $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). Conditioneren op $Z_1$ zoals in Stelling 23.17:

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

de factor $t$ die de voorouder zelf meerekent. (Voor de wet $p_0 = 1 - p$ , $p_2 = p$ van binaire vertakking kan deze kwadratische vergelijking in $H$ expliciet opgelost en ontwikkeld worden — de Catalan-getallen van Hoofdstuk 11 tellen de familiestambomen.)

Oefening 23.8 ★★★

Zij $X$ genererende functie $G$ hebben met convergentiestraal $> 1$ . Bewijs de exponentiële staartgrens: er bestaan $C > 0$ en $\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.) Omgekeerd, toon dat als $\P(X \geq n) \leq C\rho^n$ met $\rho < 1$ , de straal van $G$ $\geq 1/\rho > 1$ is.

Oplossing

Oplossing van Oefening 23.8.

Laat $R > 1$ de straal zijn en fixeer $t \in \intoo{1}{R}$ . Dan $\E(t^X) = G(t) < \infty$ , en de ongelijkheid van Markov (Stelling 22.15) toegepast op de niet-negatieve variabele $t^X$ op niveau $t^n$ :

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

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

Oefening 23.9 ★★★

(Continuïteitsstelling, elementair geval) Zij $X, X_1, X_2, \dots$ $\N$ -waardig met $G_{X_n}(t) \to G_X(t)$ voor elke $t \in \intco{0}{1}$ . Toon dat $\P(X_n = k) \to \P(X = k)$ voor elke $k$ . (Inductie op $k$ : voor $k = 0$ neem $t \to 0$ — zorgvuldig: fixeer $t$ klein, 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}$ ; diagonaliseer dan. Voor de inductiestap, beschouw $\frac{G(t) - \P(X = 0)}{t}$ , de genererende functie van een verschoven wet.)

Oplossing

Oplossing van Oefening 23.9.

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

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

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

Dus

\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$ , dan $n_0$ zodat de laatste term $< \frac\varepsilon2$ is voor $n \geq n_0$ : dus $p_0^{(n)} \to p_0$ .

Inductiestap. Neem aan $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 sub-waarschijnlijkheidsrijen $(p^{(n)}_{j+1})_j$ (totale massa $\leq 1$ , wat het $k = 0$ -argument allemaal gebruikte). Voor vaste $t \in \intoo{0}{1}$ , $g_n(t) \to g(t)$ door de hypothese en het geval $k = 0$ . Het $k = 0$ -argument toepassen op $g_n$ geeft $p_1^{(n)} \to p_1$ ; de verschuiving $k$ keer itereren geeft $p_k^{(n)} \to p_k$ voor elke $k$ . (Dit is het discrete, elementaire geval van de continuïteitsstelling van Lévy, wier algemene vorm — voor karakteristieke functies — een mijlpaal van Bachelor jaar 3 is.)

Oefening 23.10 ★

(Pariteitstruc) Toon dat voor een $\N$ -waardige variabele $X$ ,

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

en bereken deze waarschijnlijkheid voor $X \sim \mathcal P(\lambda)$ en $X \sim \mathcal B(n, p)$ . Wat betekent $G_X(-1) \to 0$ probabilistisch?

Oplossing

Oplossing van Oefening 23.10.

Puntsgewijs is $\frac{1 + (-1)^X}{2}$ gelijk aan $1$ wanneer $X$ even is en $0$ wanneer oneven, dus verwachtingen nemend (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 wet spreidt over vele gehelen en vergeet haar pariteit.

Oefening 23.11 ★★

(Sicherman-dobbelstenen) Verifieer de factorisatie van de genererende functie van de eerlijke dobbelsteen

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

en toon dat de twee dobbelstenen met vlakken $\{1, 2, 2, 3, 3, 4\}$ en $\{1, 3, 4, 5, 6, 8\}$ 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 standaarddobbelstenen is: deze exotische dobbelstenen produceren elk totaal $2, \dots, 12$ met precies de standaardkansen.

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 factorisatie geeft. Voor de eerste steen, $(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$ : vlakken $\{1, 2, 2, 3, 3, 4\}$ . Voor de tweede, ontwikkelen

(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$ : vlakken $\{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 standaardsteen: het Sicherman-paar heeft precies de standaardwet voor het totaal — genererende functies classificeren alle zulke hergroeperingen.

Oefening 23.12 ★★★

(Wachten op twee kop op een rij) Een munt met kopkans $p$ wordt gegooid tot twee opeenvolgende koppen verschijnen; laat $T$ het aantal worpen zijn (het spel van Oefening 21.6). Conditionerend op de eerste worpen, leid een lineair stelsel af voor de genererende functies vanuit de toestanden “geen huidige kop” en “één huidige kop”, en concludeer

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

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

Oplossing

Oplossing van Oefening 23.12.

Laat $A$ en $B$ de genererende functies zijn van de resterende duur startend vanuit “geen huidige kop” en “één huidige kop”. Eén worp wordt besteed, dan: vanuit toestand $0$ keert munt terug naar toestand $0$ , kop beweegt naar toestand $1$ ; vanuit toestand $1$ eindigt kop het spel, munt keert 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: $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 door recursie toonde). Logaritmische differentiatie in $1$ : $\E(T) = 2 - \frac{D'(1)}{D(1)}$ met $D(t) = 1 - qt - pqt^2$ , $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 Galton–Watson-proces, opgelost

Probleem 23.1

Weekendprobleem — groeitempi, exacte oplossingen, totale nakomelingschap, en de kritieke schatting van Kolmogorov

Het uitstervingscriterium (Stelling 23.25) splitst vertakkingsprocessen in subkritisch, kritiek en superkritisch — maar zegt niets over tempi: hoe snel een gedoemde lijn sterft, hoe groot een overlevende groeit. Dit probleem berekent ze. We houden de notatie van het hoofdstuk: nakomelingenwet $(p_k)$ met pgf $G$ , gemiddelde $m = G'(1)$ , generatiegroottes $Z_n$ ( $Z_0 = 1$ ), iteraten $G_n = G_{Z_n}$ , uitsterfkansen $q_n = \P(Z_n = 0) \uparrow q$ ; we nemen altijd aan $p_1 \neq 1$ en, waar tweede momenten verschijnen, $G''(1) < \infty$ , en we schrijven $\sigma^2 = V(Z_1)$ .

Deel I — Momenten van de generaties.

Toon $\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

$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) Voor $m < 1$ , toon $\P(Z_n > 0) \leq m^n$ (Markov op de geheelwaardige $Z_n$ ): uitsterven is zeker met een geometrisch tempo — een kwantitatieve verfijning van het criterium van het hoofdstuk.
(Subkritisch tempo, ondergrens) Gebruik makend van Cauchy–Schwarz op $Z_n\mathbf 1_{Z_n > 0}$ , toon

$\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 geometrische tempo $m^n$ is exact tot op constanten.

Deel II — De geometrische familie, exact opgelost. Laat de nakomelingenwet geometrisch op $\N$ zijn: $p_k = qp^k$ ( $k \geq 0$ ), met $0 < p < 1$ , $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 dat de vastpunten $1$ en $q/p = 1/m$ zijn, en herstel de uitsterfkans $q_{\mathrm{ext}} = \min(1, 1/m)$ .
Bewijs door 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 tempi af: $1 - q_n \sim (1 - m)\,m^n$ in het subkritische geval, en $q_{\mathrm{ext}} - q_n \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ in het superkritische geval; controleer dat de superkritische contractieverhouding $G'(q_{\mathrm{ext}}) = 1/m$ is.
Kritiek geval ( $p = \tfrac12$ ): bereken $\sigma^2 = 2$ en noteer $1 - q_n = \frac1{n+1}$ : overleving daalt als $\frac1n$ — noch geometrisch noch sommeerbaar.
Nog steeds kritiek: bewijs door inductie de volle iterate

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

en leid af dat geconditioneerd op overleving, $Z_n$ geometrisch 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 grootte van orde $n$ .

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

Rechtvaardig $\P(Y < \infty) = q_{\mathrm{ext}}$ , en herinner uit Oefening 23.7 de functionaalvergelijking $H(t) = t\,G(H(t))$ (wier afleiding $m < 1$ niet gebruikte).
(Binaire vertakking) Voor $p_0 = p_2 = \frac12$ (kritiek), los de functionaalvergelijking op:

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

en ontwikkel met Voorbeeld 11.21 om te krijgen

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

controleer de waarden $\P(Y = 1) = \frac12$ en $\P(Y = 3) = \frac18$ door direct tellen.
Differentiëren van de functionaalvergelijking in $1^-$ toont dat $\E(Y) = \frac{1}{1-m}$ voor $m < 1$ , terwijl kriticiteit $\E(Y) = \infty$ forceert: de kritieke totale nakomelingschap is bijna zeker eindig met oneindig gemiddelde.
Met de centrale binomiale asymptotiek (Voorbeeld 6.14), toon

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

een zware $k^{-3/2}$ -staart, en leid af $\P(Y > n) \asymp n^{-1/2}$ (boven- en ondergrenzen van deze orde volstaan).
Vergelijk met de eerlijke toevalswandeling (het weekendprobleem van Hoofdstuk 21): zekere maar oneindig-gemiddelde terugkeertijden daar, zekere maar oneindig-gemiddelde totale nakomelingschap hier, beide met $n^{-3/2}$ -lokale wetten. Eén alinea over waarom kriticiteit deze signatuur produceert.

Deel IV — De schatting van Kolmogorov in kriticiteit. Neem aan $m = 1$ , $0 < \sigma^2 = G''(1) < \infty$ .

Toon dat $G''$ continu uitbreidt tot $\intcc01$ (niet-negatief stijgend met eindige limiet) en leid de Taylor-ontwikkeling 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 .$
Voor $t \in \intco01$ , stel $h(t) = \dfrac1{1 - G(t)} - \dfrac1{1 - t}$ . Toon

$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)} \xrightarrow[t\to1^-]{} b .$
Telescoop 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 Cesaro-argument 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$ , met alleen de constante die de nakomelingenwet onthoudt.
Controleer de schatting tegen het kritieke geometrische geval van vraag 10.
Leid af $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n} \sim \dfrac{\sigma^2 n}{2}$ (noteer $\E(Z_n \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$ ), en controleer tegen vraag 11: geconditioneerd op overleving groeit de populatie lineair — het kritieke slappe koord tussen dood en explosie.

Deel V — Toepassingen en synthese.

(Epidemieën, kettingreacties) Voor een Poisson- nakomelingenwet $\mathcal P(\lambda)$ — elk geval infecteert $\mathcal P(\lambda)$ nieuwe gevallen — schrijf de uitstervingsvergelijking $q = \eu^{\lambda(q-1)}$ en los haar numeriek op voor $\lambda = 1.5$ ( $q \approx 0.417$ ) en $\lambda = 2$ ( $q \approx 0.203$ ): startend van één geval is een grote uitbraak niet zeker zelfs wanneer $\lambda > 1$ . Leg uit waarom de iteratie $q_{n+1} = \eu^{\lambda(q_n - 1)}$ vanaf $q_0 = 0$ naar de juiste wortel convergeert.
Startend van $k$ voorouders in plaats van één, toon dat de uitsterfkans $q^k$ is. Toepassing: met $\lambda = 1.5$ , hoeveel begingevallen maken een uitbraak minstens $99\%$ waarschijnlijk?
(Een superkritisch proces conditioneren op uitsterven) Voor $m > 1$ met uitsterfkans $q \in \intoo01$ : bewijs eerst door convexiteit dat $G'(q) < 1$ in het kleinste vast punt, en leid af $q_{\mathrm{ext}} - q_n = O\bigl(G'(q)^n\bigr)$ (geometrische convergentie, zoals vraag 9 illustreerde). Toon dan dat $\widehat G(t) = G(qt)/q$ de pgf is van een bona fide nakomelingenwet, met gemiddelde $\widehat m = G'(q) < 1$ : een subkritisch metgezelproces. Verifieer op de geometrische familie: conditioneren van het superkritische $(p, q)$ -proces op uitsterven verwisselt $p$ en $q$ . (De volle uitspraak — het geconditioneerde proces is het metgezelproces — wordt bewezen in het Bachelor jaar 3-volume; hier hebt u haar genererende-functieschaduw geverifieerd.)
Synthese: stel de trichotomietabel op — voor $m < 1$ , $m = 1$ , $m > 1$ : waarde van $q$ ; tempo van $\P(Z_n > 0)$ of van $q - q_n$ ; $\E(Y)$ ; grootte van een overlevende generatie. Stel in één zin per gereedschap hoe compositie van pgf’s, convexiteit, Taylor in $1^-$ , en Cesaro-middeling het hele probleem droegen, en wat het Bachelor jaar 3-volume toevoegt (de martingaal $Z_n/m^n$ en de exponentiële limietwet van Yaglom).

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^-$ , $G_{n-1}(t) \uparrow 1$ , en $G'$ is niet-dalend met linkerlimiet $m$ in $1$ , dus de eerste factor neigt naar $m$ ; door inductie neigt de tweede naar $m^{n-1}$ . Door Stelling 23.7, $\E(Z_n) = G_n'(1^-) = m^n$ .

2. Nog eens differentiëren,

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

en $t \to 1^-$ : $a_n = G''(1)m^{2(n-1)} + m\, a_{n-1}$ met $a_n = G_n''(1)$ , $a_1 = G''(1)$ . Voor $m \neq 1$ controleert men door inductie dat $a_n = G''(1)\,m^{n-1}\frac{m^n - 1}{m - 1}$ (de recursie voegt $G''(1)m^{2n-2}$ toe aan $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$ , $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, wat $V(Z_n) = \sigma^2m^{n-1}\frac{m^n-1}{m-1}$ overlaat. Voor $m = 1$ : $V(Z_n) = nG''(1) = n\sigma^2$ .

4. $Z_n$ is een niet-negatieve geheelwaardige variabele, dus $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ door Markov (Stelling 22.15). Voor $m < 1$ daalt dit geometrisch — en sommeerbaar, dus geeft Borel–Cantelli zelfs dat slechts eindig veel generaties niet-leeg zijn, wat opnieuw 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}$ delend door deze grens en vereenvoudigend met $m^n$ ,

\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. 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$ , kritiek voor $p = \frac12$ , superkritisch voor $p > \frac12$ .

7. $G(t) = t$ leest $pt^2 - t + q = 0$ , met wortels $\frac{1 \pm \abs{p - q}}{2p}$ , d.w.z. $1$ en $\frac qp = \frac1m$ . De uitsterfkans is het kleinste vast punt in $\intcc01$ (Stelling 23.25): $q_{\mathrm{ext}} = 1$ als $m \leq 1$ , en $\frac1m$ als $m > 1$ .

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

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 basgeval $q_0 = 0$ houdt. 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$ neigt de noemer naar $-1$ : $1 - q_n \sim (1 - m)\,m^n$ . Voor $m > 1$ :

q_{\mathrm{ext}} - 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{ext}}) = \frac qp = \frac1m$ : de waargenomen verhouding $m^{-1}$ is precies de afgeleide in het aantrekkende vast 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 daalt als $1/n$ — te traag om sommeerbaar te zijn, in tegenstelling tot 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

\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 pgf van de geometrische wet $\mathcal G\bigl(\frac1{n+1} \bigr)$ op $\N^*$ (Voorbeeld 23.4): gegeven overleving, $\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. Als de lijn uitsterft in generatie $n$ , dan is $Y = Z_0 + \dots + Z_{n-1}$ eindig; als zij nooit uitsterft, $Y \geq \sum_n 1 = \infty$ . Dus is $\{Y < \infty\}$ de uitsterfgebeurtenis en $\P(Y < \infty) = q_{\mathrm{ext}}$ . De afleiding van $H(t) = tG(H(t))$ in Oefening 23.7 — de voorouder draagt de factor $t$ bij, zijn 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$ leest de vergelijking $tH^2 - 2H + t = 0$ , dus $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (de wortel met $H(0) = 0$ ). Vergelijkend met de Catalan-reeks $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}}$ , d.w.z. $\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. Differentiëren van $H = tG(H)$ op $\intoo01$ en $t \to 1^-$ (monotone limieten zoals in Stelling 23.7): $H'(1)\bigl(1 - G'(H(1))\bigr) = G(H(1))$ . In het subkritische geval $H(1) = 1$ en $\E(Y) = H'(1) = \frac1{1 - m}$ . In het kritieke geval maakt $G'(1) = 1$ de linkerfactor verdwijnen terwijl de rechterzijde $1$ is: geen eindige $H'(1)$ kan bestaan, dus $\E(Y) = \infty$ — toch $\P(Y < \infty) = q = 1$ .

15. $C_k = \frac1{k+1}\binom{2k}k \sim \frac{4^k}{\sqrt\pi\,k^{3/2}}$ door 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}$ , boven en onder): $\P(Y > 2K) \asymp K^{-1/2}$ , d.w.z. $\P(Y > n) \asymp n^{-1/2}$ — een zware staart met oneindig gemiddelde, die vraag 14 kwantificeert.

16. Beide kritieke objecten — de terugkeertijd van de eerlijke wandeling (het weekendprobleem van Hoofdstuk 21) en de kritieke totale nakomelingschap — zijn bijna zeker eindig met oneindig gemiddelde, met lokale wetten van exponent $-3/2$ en staarten van exponent $-1/2$ . Dit is geen toeval: een familiestamboom kind voor kind verkennen produceert een $\pm1$ -pad (één stap omhoog per geboorte, één omlaag per dood) dat precies een eerlijke wandeling is, en $Y$ wordt een eerste-passagetijd. Kriticiteit betekent nul drift: het proces is altijd op de rand van zowel uitsterven als explosie, en de $\sqrt{}$ -schaalfluctuaties van nul-drift-toeval produceren precies deze exponenten.

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$ (kriticiteit maakt $\E Z_1(Z_1 - 1) = \sigma^2$ ); een niet-dalende functie met limiet gelijk aan de randwaarde is continu in $1$ . Taylor met integraalrestterm 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. Reducerend tot een gemeenschappelijke noemer, $h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}$ . Door 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. Uit de definitie van $h$ in $t = q_j$ en $G(q_j) = q_{j+1}$ : $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$ ; sommeren van $j = 0$ ( $q_0 = 0$ ) geeft de display. Omdat het kritieke proces uitsterft, $q_j \uparrow 1$ , dus $h(q_j) \to b$ en het Cesaro-gemiddelde $\frac1n\sum_{j<n}h(q_j) \to b$ : $\frac1{1-q_n} \sim bn$ , d.w.z.

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

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

21. Omdat $Z_n\mathbf 1_{Z_n > 0} = Z_n$ , $\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 geometrische geval is dit $n + 1$ , exact overeenkomend met vraag 11 ( $\sigma^2 = 2$ ). Het kritieke beeld: uitsterven is zeker, de gemiddelde grootte is bevroren op $1$ , en de zeldzame overlevende lijnen hebben lineair groeiende grootte — elke factor de andere balancerend.

22. Voor $\mathcal P(\lambda)$ -nakomelingen, $G(t) = \eu^{\lambda(t-1)}$ en de uitsterfkans is de kleinste wortel 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$ . Dus één indexgeval ontsteekt een grote uitbraak met waarschijnlijkheid $58\%$ ( $\lambda = 1.5$ ) of $80\%$ ( $\lambda = 2$ ) — waarschijnlijk, niet zeker. De iteratie vanaf $q_0 = 0$ convergeert naar de kleinste wortel omdat $G$ niet-dalend is: door inductie $q_n \leq r$ voor elk vast punt $r$ , en $(q_n)$ stijgt (het is $\P(Z_n = 0)$ ), dus haar limiet is een vast punt onder alle anderen.

23. De $k$ voorouders stichten onafhankelijke familiestambomen, en totale uitsterving is de doorsnede van $k$ onafhankelijke uitsterfgebeurtenissen: waarschijnlijkheid $q^k$ . Voor $\lambda = 1.5$ : uitbraakkans $1 - q^k \geq 0.99$ eist $q^k \leq 0.01$ , d.w.z. $k \geq \frac{\ln 0.01}{\ln 0.417} \approx 5.3$ : zes begingevallen maken de uitbraak $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$ ; als $G'(q) = 1$ , zou de raaklijn in $q$ (die convexiteit onder $G$ plaatst) $G(t) \geq t$ forceren op $\intcc q1$ , vandaar $G \equiv \mathrm{id}$ daar, alle coëfficiënten $p_n$ ( $n \geq 2$ ) dodend en $m > 1$ tegensprekend. Geometrische 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$ . Metgezelproces: $\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 pgf; haar gemiddelde is $\widehat G'(1) = G'(q) < 1$ : subkritisch. Geometrische familie: $G(t) = \frac{q}{1-pt}$ , $q_{\mathrm{ext}} = \frac qp$ , en

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

de geometrische nakomelingenwet met $p$ en $q$ verwisseld — het superkritische proces gezien op haar uitsterfgebeurtenis is de spiegel-subkritische.

25. De tabel: $m < 1$ : $q = 1$ , $\P(Z_n > 0) \asymp m^n$ (vragen 4–5), $\E(Y) = \frac1{1-m}$ , overlevende generaties van 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}$ , overlevers van grootte $\sim \frac{\sigma^2n}2$ . $m > 1$ : $q < 1$ is het kleinste vast punt, $q - q_n = O(G'(q)^n)$ , $\E(Z_n) = m^n$ -groei, en geconditioneerd op sterven is het proces de subkritische metgezel (vraag 24). De gereedschappen: compositie van pgf’s zette populatierecursie om in functie-iteratie; convexiteit fixte de meetkunde van de vastpunten; Taylor in $1^-$ zette momenthypothesen om in lokale ontwikkelingen; en Cesaro-middeling extraheerde Kolmogorovs $1/n$ uit een telescoperende som. Het Bachelor jaar 3-volume voegt de martingaal $Z_n/m^n$ toe — wier bijna-zekere limiet $\E(Z_n) = m^n$ verfijnt tot een traject-per-traject- groeitempo — en de stelling van Yaglom, de limietwet achter de voorwaardelijke meetkunde geobserveerd in vraag 11.