Matematika Universitas — Tahun 2 · Bachelor Year 2

23Fungsi Pembangkit Peluang

Deret pangkat pada Bab 11 kembali dengan misi peluang: pada peubah acak bernilai- $\N$ kita lekatkan deret pangkat berkoefisien $\P(X = n)$ . Fungsi pembangkit ini mengubah jumlah peubah yang saling bebas menjadi hasil kali, momen menjadi turunan di $1$ , dan kesamaan kombinatorik yang sukar menjadi perkalian satu baris. Bab ini menutup buku dengan dua pertunjukan: hampiran Poisson bagi kejadian langka, dan kriteria kepunahan bagi proses percabangan — sebuah perhitungan peluang yang sungguh tak hingga, yang terpecahkan seluruhnya oleh geometri sebuah kurva cembung.

23.1 Definisi dan sifat dasarnya

Definisi 23.1 (Fungsi pembangkit peluang)

Misalkan $X$ peubah acak bernilai- $\N$ , dengan $p_n = \P(X = n)$ . Adapun fungsi pembangkit peluang bagi $X$ adalah jumlah deret pangkatnya

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

Contoh 23.2 (Refleks pertama)

Peubah konstan $X = c$ punya $G_X(t) = t^c$ ; sebuah geseran menuruti $G_{X+c}(t) = t^c\,G_X(t)$ ; dan mengevaluasinya di titik istimewa membaca informasinya tanpa penguraian apa pun: $G_X(0) = \P(X = 0)$ , $G_X(1) = 1$ , dan $G_X(-1) = \P(X\text{ genap}) - \P(X\text{ ganjil})$ , yakni neraca keparitasan yang dimanfaatkan pada Latihan 23.10. Kalimat sebaris ini dipakai secara diam-diam di mana-mana di bawah — dan evaluasi $G_X(0)$ itu persis cara peluang kepunahan kelak diperas dari fungsi pembangkit yang teriterasi pada akhir bab ini.

Proposisi 23.3 (Jari-jari dan sifat pertamanya)

Deret yang mendefinisikan $G_X$ berjari-jari kekonvergenan $\geq 1$ ; $G_X$ terdefinisi dan kontinu pada $\intcc{-1}{1}$ , $\mathcal{C}^\infty$ pada $\intoo{-1}{1}$ , dengan $G_X(1) = 1$ dan $\abs{G_X(t)} \leq 1$ di sana. Lebih jauh, $G_X$ menentukan hukum $X$ :

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

Bukti. Karena $\sum p_n = 1$ konvergen, sukunya $p_n\,1^n$ terbatas, jadi jari-jarinya $\geq 1$ (lema Abel, Bab 11); di $t = \pm1$ deretnya konvergen mutlak ( $\sum p_n = 1$ mendominasinya); lebih baik lagi, pada seluruh selang $\intcc{-1}1$ ,

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

deretnya konvergen normal pada $\intcc{-1}1$ , jadi jumlahnya kontinu di sana (Teorema 10.16 dan 10.4). Adapun kemulusan di dalamnya dan rumus koefisiennya merupakan teori umum deret pangkat; karena koefisiennya dapat dipulihkan, dua peubah dengan fungsi pembangkit yang sama berhukum sama. ∎

Contoh 23.4 (Hukum klasiknya)

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

Contoh 23.5 (Mengintegralkan fungsi pembangkitnya)

Turunan $G_X$ di $1$ memberi momen positif; adapun integralnya memberi yang negatif. Dari $\int_0^1t^k\dd t = \frac1{k+1}$ dan pengintegralan suku demi suku (kekonvergenan normal pada $\intcc01$ ):

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

Untuk $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},

yang memulihkan dalam satu baris perhitungan deret pada Contoh 22.10. Fungsi pembangkitnya merupakan alat dua arah: turunkan di $1$ untuk memperoleh momen $\E(X)$ , $\E(X(X-1))$ , integralkan pada $\intcc01$ untuk memperoleh $\E\bigl(\frac1{1+X}\bigr)$ — satu objek analitik, yang ditanyai ke arah mana pun yang diperlukan masalahnya.

Contoh 23.6 (Sebuah hukum yang jari-jarinya persis satu)

Ambil $\P(X = k) = \dfrac{6}{\pi^2k^2}$ untuk $k \geq 1$ — sebuah hukum peluang menurut kesamaan Basel (Contoh 14.12). Fungsi pembangkitnya $G(t) = \frac6{\pi^2}\sum_{k\geq1}\frac{t^k}{k^2}$ berjari-jari kekonvergenan persis $1$ : batas umum “jari-jari $\geq 1$ ” pada Proposisi 23.3 tak dapat diperbaiki. Adapun reratanya adalah

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

$G$ kontinu pada $\intcc{-1}1$ , mulus di dalamnya, tetapi turunannya meledak di $1^-$ — grafiknya tiba di titik $(1, 1)$ dengan singgung tegak. Ekor yang berat terlihat secara geometrik pada fungsi pembangkitnya, di satu titik $t = 1$ saja; adapun teorema momen di bawah membuat padanan ini menjadi persis.

Teorema 23.7 (Momen dari fungsi pembangkitnya)

$X$ punya nilai harapan bila dan hanya bila $G_X$ terdiferensialkan di $1^-$ (turunan kirinya, berhingga), dan lalu $\E(X) = G_X'(1)$ . Serupa itu $X$ punya momen kedua bila dan hanya bila $G_X$ dua kali terdiferensialkan di $1^-$ , dan lalu

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

Bukti. Untuk $t \in \intoo{0}{1}$ , penurunan suku demi suku di dalam cakramnya memberi $G_X'(t) = \sum_{n\geq1} np_n t^{n-1}$ , yakni deret berkoefisien taknegatif: $t \mapsto G_X'(t)$ tidak turun pada $\intoo{0}{1}$ , dan menurut kekonvergenan monoton jumlah parsialnya (atau teorema Abel bagi koefisien taknegatif, Bab 11),

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

dengan setiap ruasnya berhingga persis ketika ruas satunya berhingga. Bila berhingga, teorema nilai rata-rata mengapit hasil bagi selisihnya $\frac{G_X(1) - G_X(t)}{1 - t}$ di antara nilai $G_X'$ , jadi $G_X$ terdiferensialkan di $1^-$ dengan $G_X'(1) = \sum np_n = \E(X)$ (menurut pemindahannya). Pernyataan orde keduanya mengulangi hujahnya satu tingkat lebih atas: $G''_X(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ juga tidak turun pada $\intoo01$ dengan limit monoton $\sum_nn(n-1)p_n = \E(X(X-1))$ , yang berhingga persis ketika $X$ punya momen kedua. Rumus ragamnya lalu menyusul dari 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 .

∎

Contoh 23.8

Poisson: $G'(t) = \lambda e^{\lambda(t-1)}$ , jadi $\E(X) = \lambda$ ; $G''(1) = \lambda^2$ , jadi $V(X) = \lambda^2 + \lambda - \lambda^2 = \lambda$ — yakni perhitungan pada Bab 22 yang masing-masing menjadi satu baris.

Contoh 23.9 (Modus sebuah hukum Poisson)

Di mana $\P(X = k)$ terbesar untuk $X \sim \mathcal P(\lambda)$ ? Bobot berurutannya dibandingkan lewat nisbah

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

yang melampaui $1$ selama $k < \lambda - 1$ lalu jatuh di bawah $1$ begitu $k > \lambda - 1$ : bobotnya naik lalu turun, dengan modus $\floor\lambda$ (dan seri antara $\lambda - 1$ dan $\lambda$ ketika $\lambda$ sebuah bilangan bulat: untuk $\lambda = 3$ , $\P(X = 2) = \P(X = 3) = \frac92\eu^{-3} \approx 0.224$ ). Uji nisbah atas koefisiennya kerap menjadi jalan yang tercepat menuju fakta kualitatif tentang sebuah hukum diskret — tanpa perlu fungsi pembangkit, tetapi koefisiennya adalah fungsi pembangkitnya, yang dibaca suku demi suku.

23.2 Jumlah peubah yang saling bebas

Teorema 23.10 (Kemultiplikatifan)

Bila $X$ dan $Y$ peubah acak bernilai- $\N$ yang saling bebas, maka

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

dan menurut induksi $G_{X_1 + \dots + X_n} = \prod_i G_{X_i}$ bagi $X_1, \dots, X_n$ yang saling bebas.

Bukti. Dua bukti, keduanya mendidik. Lewat nilai harapan: $t^X$ dan $t^Y$ merupakan peubah terbatas yang saling bebas, jadi (Teorema 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) .

Lewat hasil kali Cauchy: hukum $X + Y$ adalah konvolusi $\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k)$ , dan teorema hasil kali Cauchy bagi deret yang konvergen mutlak (Bab 7) mengalikan kedua deret pangkatnya persis sepanjang konvolusi itu. ∎

Contoh 23.11 (Kestabilan hukum klasiknya)

Binomial saling bebas dengan $p$ yang sama itu menjumlah: $(1 - p + pt)^m(1 - p + pt)^n = (1 - p + pt)^{m+n}$ , jadi $\mathcal{B}(m, p) + \mathcal{B}(n, p) = \mathcal{B}(m + n, p)$ — khususnya jumlah $n$ peubah Bernoulli yang saling bebas itu binomial, yang membuktikan ulang hukum banyaknya keberhasilan. Poisson yang saling bebas pun menjumlah: $e^{\lambda(t-1)}e^{\mu(t-1)} = e^{(\lambda + \mu)(t-1)}$ , jadi $\mathcal{P}(\lambda) + \mathcal{P}(\mu) = \mathcal{P}(\lambda + \mu)$ — yakni perhitungan konvolusi pada Latihan 22.2, kini tanpa perhitungan.

Contoh 23.12 (Dua dadu, satu suku banyak dikuadratkan)

Untuk satu dadu setimbang, $G(t) = \frac{t + t^2 + \dots + t^6}{6}$ ; adapun untuk jumlah dua dadu,

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

yakni hukum segitiga jumlah dadu ( $7$ adalah modusnya, dengan peluang $\frac6{36} = \frac16$ ), yang terbaca dari sebuah suku banyak kuadrat yang orang kalikan sekali seumur hidup. Rumus konvolusinya akan menuntut sebelas hujah pencacahan terpisah; adapun fungsi pembangkitnya mengerjakan semuanya serentak, sebab mengalikan suku banyak adalah mengonvolusikan koefisien. Pengalihbahasaan mekanis ini — hukum menjadi koefisien, jumlah menjadi hasil kali — merupakan seluruh model usaha bab ini, dan Latihan 23.11 mendorongnya sampai ke dadu Sicherman yang mengejutkan.

Contoh 23.13 (Tiga dadu dan sebuah pemerasan koefisien)

Untuk jumlah $S$ tiga dadu setimbang, $\P(S = 10)$ adalah koefisien $t^{10}$ pada $\bigl(\frac{t + \dots + t^6}6\bigr)^3$ . Faktorkan lalu uraikan dengan deret binomial dan deret geometrik:

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

Koefisien $t^{10}$ menuntut $t^7$ dari hasil kalinya: $j = 7$ dengan suku $1$ , dan $j = 1$ dengan suku $-3t^6$ :

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

Pencacahan langsung atas $27$ tripelnya rawan keliru; adapun aljabarnya mekanis dan berskala ke berapa pun banyaknya dadu — inklusi–eksklusi yang terlihat pada $(1 - t^6)^3$ sedang mengerjakan telaah kasusnya secara otomatis.

Contoh 23.14 (Membaca sebuah hukum dari fungsi pembangkitnya)

Hukum mana yang punya $G(t) = \dfrac1{2 - t}$ ? Uraikan menjadi deret pangkat:

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

yakni koefisien taknegatif yang berjumlah $G(1) = 1$ , jadi ini sebuah hukum sejati, $\P(X = k) = 2^{-(k+1)}$ pada $\N$ — sebuah hukum geometrik yang bermula di $0$ . Menurut ketunggalannya (Proposisi 23.3), tak ada hukum lain yang berbagi $G$ ini. Mengenali hukum dari fungsi pembangkitnya merupakan keterampilan yang layak dilatih: begitulah iterat percabangan kritis $G_n(t) = \frac{n - (n-1)t}{n+1 - nt}$ pada soal akhir pekan itu tersingkap sebagai hukum geometrik yang disyaratkan pada kesintasannya.

Catatan 23.15

Kestabilannya berlaku satu arah saja: jumlah Poisson yang saling bebas itu Poisson, tetapi selisihnya tidak — $X - Y$ mengambil nilai negatif, jadi ia sama sekali tak punya fungsi pembangkit, dan hukumnya (distribusi Skellam) terletak di luar perkakas bab ini. Begitu pula $\mathcal B(m, p) + \mathcal B(n, p')$ dengan $p \neq p'$ bukanlah binomial: hasil kali $(1 - p + pt)^m(1 - p' + p't)^n$ punya dua letak akar yang berbeda, sedangkan setiap fungsi pembangkit binomial punya satu akar berulang tunggal. Membaca kestabilan dari pola akarnya merupakan cuplikan kecil tentang betapa banyak struktur yang disandikan suku banyaknya.

Catatan 23.16 (Tapis akar satuan)

Mengevaluasinya di $-1$ memisahkan yang genap dari yang ganjil; mengevaluasinya di semua akar satuan ke- $m$ memisahkan setiap kelas sisanya: dengan $\omega = \eu^{2\iu\pi/m}$ ,

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

sebab merata-ratakan $\omega^{j(k-r)}$ atas $j$ menghasilkan $1$ bila $k \equiv r$ dan $0$ bila tidak. Contoh hasilnya: untuk jumlah $S$ dua dadu setimbang, setiap $G(\omega^j) = \frac16\sum_{k=1}^6 \omega^{jk} = -\frac16$ untuk $j \neq 0$ (ketujuh akar satuan ketujuh berjumlah nol), jadi

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

yang membenarkan cacahan pada Contoh 23.12 — dan metodenya berskala ke pertanyaan yang tak terjangkau pencacahan langsung.

Teorema 23.17 (Jumlah acak: kesamaan Wald bagi fungsi pembangkit)

Misalkan $(X_k)_{k\geq1}$ peubah bernilai- $\N$ yang saling bebas dengan hukum dan fungsi pembangkit $G_X$ yang sama, dan misalkan $N$ sebuah peubah bernilai- $\N$ yang bebas dari $X_k$ , dengan fungsi pembangkit $G_N$ . Maka jumlah acak $S = X_1 + \dots + X_N$ (dengan $S = 0$ ketika $N = 0$ ) punya fungsi pembangkit

G_S = G_N \circ G_X .

Khususnya, bila $N$ dan $X_1$ punya nilai harapan, maka $\E(S) = \E(N)\,\E(X_1)$ .

Bukti. Syaratkanlah pada $N$ (peluang total, Teorema 21.14): untuk $\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),

dengan memakai kemultiplikatifannya bagi setiap $n$ yang tetap dan keterjumlahan seluruh keluarga rangkapnya ( $\abs{G_X(t)} \leq 1$ ). Adapun pertukaran penjumlahannya adalah Fubini bagi keluarga yang terjumlahkan (Bab 7). Menurunkannya di $1^-$ dengan aturan rantai dan Teorema 23.7: $\E(S) = G_N'(G_X(1))\,G_X'(1) = G_N'(1)G_X'(1) = \E(N)\E(X_1)$ . ∎

Contoh 23.18 (Poisson majemuk: kerugian asuransi setahun)

Sebuah penanggung menerima $N \sim \mathcal P(\lambda)$ klaim dalam setahun, dengan setiap klaim berbiaya $X_k$ (satuan bulat, berhukum sama dan saling bebas, fungsi pembangkit $G_X$ , rerata $\mu$ , bebas dari $N$ ). Menurut Teorema 23.17, kerugian total $S$ punya

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

dan dengan menurunkannya dua kali di $1^-$ :

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

Ragamnya melibatkan momen kedua sebuah klaim tunggal, bukan ragamnya: jumlah Poisson majemuk merasakan klaim besar yang sesekali itu dua kali — sekali lewat berapa banyaknya, sekali lewat berapa besarnya. Untuk $\lambda = 10$ klaim berhukum geometrik dengan rerata $2$ ( $\E X^2 = 6$ ): $\E S = 20$ , $V(S) = 60$ , dan Chebyshev (Bab 22) sudah memberikan marjin solvabilitas yang terpakai. Pola “jumlah yang terhenti secara acak” ini sama dengan pola yang kelak menggerakkan rekursi percabangan pada Proposisi 23.23: komposisi fungsi pembangkit adalah aljabar populasi acak.

Catatan 23.19

Kebebasan $N$ dari sukunya bukanlah hiasan. Ambil $X_k \in \{0, 2\}$ dengan peluang sama lalu tetapkan $N = X_1$ (yang terang-terangan bergantung): maka $S = X_1 + \dots + X_N$ bernilai $0$ ketika $X_1 = 0$ , dan $2 + X_2$ ketika $X_1 = 2$ , jadi $\E(S) = \frac12(2 + 1) = \frac32$ , sedangkan $\E(N)\E(X_1) = 1\cdot1 = 1$ : kesamaan Wald gagal. Ketika banyaknya suku dibiarkan bereaksi terhadap sukunya sendiri, struktur hasil kali yang rapi itu runtuh — adapun teori lengkap kaidah “penghentian” semacam itu merupakan bab martingal pada jilid Tahun ke-3.

23.3 Hampiran Poisson

Teorema 23.20 (Hukum kejadian langka)

Misalkan $X_n \sim \mathcal{B}(n, p_n)$ dengan $n\,p_n \to \lambda > 0$ . Maka untuk setiap $k \in \N$ :

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

yakni hukum binomial bagi banyak kejadian langka yang saling bebas konvergen ke hukum Poisson berparameter $\lambda$ .

Bukti. Perhitungan langsung dengan $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} .

Ketika $n \to \infty$ dengan $k$ tetap: faktor pertamanya menuju $1$ (hasil kali $k$ faktor $\to 1$ ); $\lambda_n^k \to \lambda^k$ ; dan $\bigl(1 - \frac{\lambda_n}{n}\bigr)^{n-k} = \exp\bigl((n-k)\ln(1 - \frac{\lambda_n}{n})\bigr) \to e^{-\lambda}$ sebab $(n - k)\ln\bigl(1 - \frac{\lambda_n}{n}\bigr) \sim -\lambda_n \to -\lambda$ (Bab 6). Sebagai gantinya, pada tataran fungsi pembangkit: $G_{X_n}(t) = \bigl(1 + \frac{\lambda_n(t-1)}{n}\bigr)^n \to e^{\lambda(t - 1)} = G_{\mathcal{P}(\lambda)}(t)$ untuk setiap $t \in [0, 1]$ yang tetap — yakni kekonvergenan fungsi pembangkit, yang (bagi peubah bernilai- $\N$ ) setara dengan kekonvergenan setiap $\P(X_n = k)$ ; lihat Latihan 23.9. ∎

Catatan 23.21

Itulah sebabnya hukum Poisson dipakai untuk memodelkan kejadian langka — salah ketik per halaman, peluruhan radioaktif per detik, kecelakaan per hari di sebuah persimpangan: setiap kesempatannya nyaris dapat diabaikan, kesempatannya banyak, dan hanya laju reratanya $\lambda$ yang bertahan pada limitnya.

Contoh 23.22 (Menyaksikan limit Poisson konvergen)

Tetapkan $\lambda = 2$ lalu ambil $X_n \sim \mathcal B(n, 2/n)$ . Adapun peluang tanpa kejadian persis $\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,

terhadap limitnya $\eu^{-2} \approx 0.135$ . Kekonvergenannya monoton dan berlaju $O(1/n)$ — dengan menguraikannya, $(1 - 2/n)^n = \eu^{-2}\bigl(1 - \tfrac2n + O(n^{-2})\bigr)$ — jadi untuk $n$ yang bernilai ratusan model Poissonnya sudah tepat sampai digit ketiga. Itulah isi praktis hukum kejadian langka: pemodelnya tak pernah mengetahui $n$ dan $p$ secara terpisah (berapa banyak kesempatan mikro salah ketik yang dimuat satu halaman?), melainkan hanya hasil kalinya $\lambda$ , dan hukum limitnya dengan murah hati tak bergantung pada apa pun yang lain.

23.4 Proses percabangan

Tinjaulah sebuah populasi yang bermula dari satu leluhur; setiap individu, secara saling bebas, punya banyak anak yang acak dengan hukum $(p_k)_{k \in \N}$ dan fungsi pembangkit $G$ (yakni distribusi keturunan). Misalkan $Z_n$ ukuran generasi $n$ ( $Z_0 = 1$ ), dan misalkan $m = G'(1) = \E(Z_1)$ rerata banyaknya keturunan.

Proposisi 23.23

Fungsi pembangkit $Z_n$ adalah iterat ke- $n$ $G_{Z_n} = G \circ G \circ \dots \circ G$ (sebanyak $n$ kali), dan peluang kepunahan $q_n = \P(Z_n = 0)$ memenuhi

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

lalu naik menuju peluang $q$ kepunahan pada akhirnya, yang merupakan titik tetap $G$ .

Bukti. Generasi $n + 1$ merupakan jumlah acak keturunan dari $Z_n$ anggota generasi $n$ , dengan cacahnya saling bebas satu sama lain dan bebas dari $Z_n$ : Teorema 23.17 memberi $G_{Z_{n+1}} = G_{Z_n} \circ G$ , dan induksi dari $G_{Z_0}(t) = t$ menghasilkan iterat $n$ lapisnya — yang, menurut keasosiatifan komposisinya, dapat pula dibaca sebagai $G_{Z_{n+1}} = G \circ G_{Z_n}$ . Dengan mengevaluasi bentuk kedua ini di $0$ : $q_{n+1} = G_{Z_{n+1}}(0) = G\bigl(G_{Z_n}(0)\bigr) = G(q_n)$ . Kejadian $\{Z_n = 0\}$ naik (populasi yang punah tetap punah), jadi $q_n \uparrow q = \P\bigl(\bigcup_n\{Z_n = 0\}\bigr)$ menurut kekontinuan monoton (Teorema 21.6), dan kekontinuan $G$ pada $[0, 1]$ mengubah $q_{n+1} = G(q_n)$ menjadi $q = G(q)$ pada limitnya. ∎

Contoh 23.24 (Menyaksikan kepunahan konvergen)

Untuk hukum keturunan $(p_0, p_1, p_2) = (\tfrac14, \tfrac14, \tfrac12)$ pada Contoh 23.27, $G(t) = \tfrac14 + \tfrac14t + \tfrac12t^2$ dan iterasi $q_{n+1} = G(q_n)$ memberi

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,

yang memanjat menuju peluang kepunahan $q = \tfrac12$ . Selisihnya $q - q_n$ adalah $0.25$ , $0.156$ , $0.105$ , $0.073$ , $0.052$ : masing-masing kira-kira $\tfrac34$ kali sebelumnya, dan memang teorema nilai rata-rata memberi $q - q_{n+1} = G'(c_n)(q - q_n)$ dengan $G'(q) = \tfrac14 + q = \tfrac34$ . Dua pelajarannya: sebuah garis keluarga yang masih hidup pada generasi $n$ punya, terpasang dalam perhitungan yang sama, peluang $q - q_n$ untuk punah kemudian; dan laju kekonvergenan tangga pada gambar di bawah adalah turunannya di titik tetapnya — adapun soal akhir pekannya mengubah kedua pengamatan itu menjadi teorema.

Teorema 23.25 (Kriteria kepunahan)

Andaikan $p_1 \neq 1$ . Peluang kepunahan $q$ merupakan titik tetap terkecil $G$ pada $\intcc{0}{1}$ , dan:

bila $m \leq 1$ (subkritis atau kritis), maka $q = 1$ : kepunahannya pasti;
bila $m > 1$ (superkritis), maka $q < 1$ : populasinya sintas selamanya dengan peluang positif $1 - q$ .

Bukti. $G$ cembung pada $\intcc{0}{1}$ (deret pangkat berkoefisien taknegatif: $G'' \geq 0$ ), tidak turun, dengan $G(1) = 1$ .

Titik tetap terkecil: ambil $r \in \intcc{0}{1}$ sebarang titik tetap. Maka $q_0 = 0 \leq r$ , dan secara induktif $q_{n+1} = G(q_n) \leq G(r) = r$ (kemonotonannya): jadi $q = \lim q_n \leq r$ .

Kasus $m \leq 1$ : andaikan $r < 1$ sebuah titik tetap. Menurut teorema nilai rata-rata pada $[r, 1]$ , ada $c \in \intoo{r}{1}$ dengan $G'(c) = \frac{G(1) - G(r)}{1 - r} = \frac{1 - r}{1 - r} = 1$ . Padahal $G'$ tidak turun (kecembungannya) dengan $\lim_{t\to1^-}G'(t) = m \leq 1$ , jadi $G' \leq 1$ pada $\intoo{0}{1}$ ; kesamaan $G'(c) = 1$ lalu memaksa $G'$ konstan bernilai $1$ pada $\intco{c}{1}$ , sehingga $G'' = \sum n(n-1)p_nt^{n-2} \equiv 0$ di sana. Deret pangkat berkoefisien taknegatif yang lenyap pada sebuah selang punya semua koefisien itu nol: $p_n = 0$ untuk $n \geq 2$ , jadi $G(t) = p_0 + p_1t$ dan $1 = G'(c) = p_1$ — yang bertentangan dengan hipotesis $p_1 \neq 1$ . Jadi $1$ satu-satunya titik tetapnya: $q = 1$ .

Kasus $m > 1$ : di dekat $1$ , $G(t) - t$ berturunan $G'(t) - 1 \to m - 1 > 0$ ketika $t \to 1^-$ , jadi $G(t) - t < G(1) - 1 = 0$ pada suatu selang $\intoo{1 - \delta}{1}$ : fungsi kontinu $G(t) - t$ bernilai $\geq 0$ di $t = 0$ ( $G(0) = p_0 \geq 0$ ) dan $< 0$ tepat di bawah $1$ , jadi ia lenyap di suatu $r < 1$ (teorema nilai antara). Titik tetap terkecilnya lalu $q \leq r < 1$ . ∎

Peluang kepunahan sebagai iterasi titik tetap q_n+1 = G(q_n) yang bermula di q_0 = 0 (tangga merah). Kiri: sebuah hukum keturunan subkritis — kurva cembungnya tetap di atas diagonalnya, dan iterasinya memanjat ke titik tetap tunggal 1. Kanan: sebuah hukum superkritis — kurvanya memotong diagonalnya di q < 1, tempat iterasinya berhenti: kesintasannya berpeluang 1 - q > 0. — **Gambar 23.1.** Peluang kepunahan sebagai iterasi titik tetap $q_{n+1} = G(q_n)$ yang bermula di $q_0 = 0$ (tangga merah). Kiri: sebuah hukum keturunan subkritis — kurva cembungnya tetap di atas diagonalnya, dan iterasinya memanjat ke titik tetap tunggal $1$ . Kanan: sebuah hukum superkritis — kurvanya memotong diagonalnya di $q < 1$ , tempat iterasinya berhenti: kesintasannya berpeluang $1 - q > 0$ .

Catatan 23.26 (Cara membaca sarang laba-labanya)

Pada gambarnya, langkah tegak menerapkan $G$ (dari $(q_n, q_n)$ naik ke $(q_n, G(q_n))$ ), sedangkan langkah mendatar menuju diagonalnya mengubah keluaran menjadi masukan: tangganya adalah rekursi $q_{n+1} = G(q_n)$ . Kecembungan $G$ dan $G(1) = 1$ menyisakan dua geometri saja. Entah kurvanya tetap di atas diagonalnya pada $\intco01$ (rerata $m \leq 1$ ): tangganya tak punya tempat berhenti sebelum $1$ . Entah kurvanya memotong di suatu $q < 1$ ( $m > 1$ ): tangganya terperangkap di bawah perpotongannya lalu konvergen ke sana, dengan laju geometrik $G'(q) < 1$ yang dikuantifikasi pada Contoh 23.24. Seluruh telaah teorema kepunahannya terlihat pada satu gambar ini — itulah sebabnya ia layak digambar sebelum dihitung.

Contoh 23.27

Hukum keturunan: tanpa anak, satu anak, dua anak dengan peluang $\frac14, \frac14, \frac12$ . Maka $m = \frac14 + 1 = \frac54 > 1$ dan $G(t) = \frac14 + \frac14 t + \frac12 t^2$ . Titik tetapnya: $\frac12 t^2 - \frac34 t + \frac14 = 0$ , yakni $2t^2 - 3t + 1 = (2t - 1)(t - 1) = 0$ : $q = \frac12$ . Garis keluarganya punah dengan peluang $\frac12$ — dan dengan peluang $\frac12$ ia hidup selamanya.

Catatan 23.28 (Perspektif di dalam jilid ini)

Bab ini merupakan persimpangan buku ini, dan setiap bahannya datang dari tempat yang bernama: aljabar deretnya dari Bab 7 dan Bab 11, peluangnya dari Bab 21 (kekontinuan monoton membuktikan $q_n \uparrow q$ ) dan Bab 22 ( $G_X = \E(t^X)$ sebuah nilai harapan, kemultiplikatifannya adalah teorema hasil kali), kecembungannya dari Bab 8 sampai Bab 17. Bahkan kepatologian ekor beratnya pun terhubung: peubah St Petersburg pada bab sebelumnya punya $G(t) = \sum_k2^{-k}t^{2^k}$ , yakni deret yang konvergen sempurna pada $\intcc01$ yang turunannya di $1^-$ divergen — rerata tak hingga, terlihat sekilas pandang. Satu objek, segala perkakas tahun ini: sebuah bab penutup yang pantas.

Catatan 23.29 (Jebakan yang lazim)

(i) Fungsi pembangkit hanya berlaku bagi peubah bernilai- $\N$ : bagi peubah bertanda atau tak bulat, objek $\E(t^X)$ kehilangan struktur deret pangkatnya (Tahun ke-3 menggantinya dengan transformasi yang disesuaikan dengan $\R$ ). (ii) Pemeriksaan kewarasan pertama atas setiap $G$ yang terhitung adalah $G(1) = 1$ ; yang kedua adalah bahwa koefisiennya taknegatif — koefisien negatif berarti kekeliruan aljabar, bukan hukum baru. (iii) Pada jumlah acak, urutan komposisinya penting: $G_S = G_N \circ G_X$ , dengan fungsi luarnya mencacah sukunya; menyusunnya dengan cara sebaliknya tak bermakna ( $G_X \circ G_N$ akan mencacah benda dari benda). (iv) Kemultiplikatifannya perlu kesalingbebasan dan sumber keacakan yang berbeda: $G_{2X}(t) = G_X(t^2)$ , bukan $G_X(t)^2$ . (v) Menurunkannya di $1$ merupakan operasi perbatasan: ketika jari-jarinya persis $1$ , seperti pada Contoh 23.6, $G'(1^-)$ boleh jadi tak hingga, dan perumusan limit monoton pada teorema momennya bukanlah kerewelan bertele-tele melainkan pernyataan yang jujur.

Menutup jilid ini

Fungsi pembangkit merupakan objek penutup yang pantas bagi buku ini: ia sekaligus sebuah deret pangkat (Bab 11), sebuah perkakas keluarga yang terjumlahkan (Bab 7), sebuah nilai harapan (Bab 22), sebuah fungsi cembung yang geometrinya memutuskan kepunahan (Bab 8), dan sebuah iterasi titik tetap (Bab 4). Matematika Tahun ke-2 adalah satu pokok bahasan. Adapun jilid Tahun ke-3 akan membuka pintu yang sengaja dibiarkan tertutup di sini: integral Lebesgue (yang melunasi teorema kekonvergenan terdominasi pada Bab 9), peluang berteori ukuran pada ruang yang takterbilang, dan bukti lengkap teorema fungsi invers (Bab 15) dalam latar geometri diferensial.

23.5 Latihan

Latihan 23.1 ★

Hitunglah fungsi pembangkit hukum seragam pada $\{1, 2, \dots, 6\}$ (sebuah dadu setimbang). Tunjukkan bahwa jumlah dua dadu setimbang tak mungkin seragam pada $\{2, \dots, 12\}$ : faktorkan $G_{X+Y}$ lalu cacah akarnya. (Jumlah yang seragam akan memaksa $G_X(t)G_Y(t) = \frac{t^2}{11}\sum_{k=0}^{10}t^k$ , yang akar taknolnya adalah akar satuan ke- $11$ selain $1$ — dan tak satu pun real — sedangkan $G_X/t$ dan $G_Y/t$ merupakan suku banyak real berderajat $5$ , yang masing-masing memiliki sedikitnya satu akar real.)

Solusi

Solusi Latihan 23.1.

Dadu setimbang: $G(t) = \frac16(t + t^2 + \dots + t^6) = \frac t6(1 + t + \dots + t^5)$ . Andaikan jumlah dua dadu setimbang seragam pada $\{2, \dots, 12\}$ , maka

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 .

Padahal $h$ merupakan suku banyak real berderajat ganjil $5$ , jadi ia punya akar real (teorema nilai antara; secara nyata $h(-1) = 0$ ), sehingga $h^2$ punya akar real. Namun $\sum_{k=0}^{10}t^k$ tak punya: ia positif untuk $t \geq 0$ , dan untuk $t < 0$ ia sama dengan $\frac{t^{11} - 1}{t - 1}$ , yakni hasil bagi dua bilangan negatif. Kontradiksi — jadi jumlah dua dadu setimbang tak pernah seragam (sebagaimana dibenarkan distribusi segitiga jumlah dadu yang sudah kita kenal).

Latihan 23.2 ★

Dengan memakai fungsi pembangkit, pulihkan $\E$ dan $V$ bagi hukum binomial dan hukum geometrik (Teorema 23.7).

Solusi

Solusi Latihan 23.2.

Binomial: $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}$ , jadi

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

Geometrik ( $q = 1 - p$ ): $G(t) = \frac{pt}{1 - qt}$ , jadi $G'(t) = \frac{p}{(1 - qt)^2}$ dan $G''(t) = \frac{2pq}{(1 - qt)^3}$ ; di $t = 1$ (dengan memakai $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} ,

yang cocok dengan Latihan 22.1 dengan kerja yang lebih sedikit.

Latihan 23.3 ★

Dua dadu yang dicurangi: mungkinkah mencurangi dua dadu (secara saling bebas, seidentik atau tidak) sehingga jumlahnya seragam pada $\{2, \dots, 12\}$ ? (Halangan pemfaktoran yang sama seperti pada Latihan 23.1: jawabannya tidak, bahkan dengan kecurangan yang berbeda, sebab setiap faktor $G_X(t)/t$ berderajat ganjil $5$ , sehingga punya akar real, sedangkan sasarannya tak punya.)

Solusi

Solusi Latihan 23.3.

Tidak, bahkan dengan kecurangan yang berbeda. Andaikan $X, Y$ hukum pada $\{1, \dots, 6\}$ yang jumlahnya seragam. Maka $G_X(t) = t\,a(t)$ dan $G_Y(t) = t\,b(t)$ dengan $a, b$ suku banyak real berderajat paling besar $5$ — dan derajatnya wajib berjumlah $10$ (jumlahnya mencapai $12$ dengan peluang positif), jadi $\deg a = \deg b = 5$ , keduanya ganjil. Seperti pada Latihan 23.1,

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

akan memaksa adanya akar real di ruas kirinya (setiap suku banyak real berderajat ganjil punya satu) dan tak ada di ruas kanannya. Jadi tak ada kecurangan atas dua dadu yang saling bebas — sama atau tidak — yang menghasilkan jumlah seragam.

Latihan 23.4 ★★

Misalkan $X_1, X_2, \dots$ Bernoulli $\mathcal{B}(p)$ yang saling bebas dan $N \sim \mathcal{P}(\lambda)$ bebas darinya. Tunjukkan, lewat Teorema 23.17, bahwa $S = X_1 + \dots + X_N \sim \mathcal{P}(\lambda p)$ : sebanyak Poisson benda, yang masing-masing disimpan dengan peluang $p$ , menyisakan sebanyak Poisson pula — yakni penipisan. Hitunglah pula hukum cacah yang terbuang lalu kagumilah: ia $\mathcal{P}(\lambda(1-p))$ , dan dapat ditunjukkan bahwa ia bebas dari $S$ .

Solusi

Solusi Latihan 23.4.

Menurut Teorema 23.17 dengan $G_N(s) = e^{\lambda(s-1)}$ dan $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)$ . Adapun cacah yang terbuang $D = N - S$ mencacah benda yang sama yang disimpan dengan peluang $1 - p$ , jadi menurut perhitungan yang sama $D \sim \mathcal{P}(\lambda(1 - p))$ . Kesalingbebasannya, secara langsung: untuk $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*}

dengan $q = 1 - p$ : hukum gabungannya terfaktorkan menjadi $\mathcal{P}(\lambda p) \otimes \mathcal{P}(\lambda q)$ . Sebuah arus Poisson yang terbelah secara acak menghasilkan arus Poisson yang saling bebas — mukjizat kecil yang terus-menerus dipakai dalam teori antrean.

Latihan 23.5 ★★

(Binomial negatif) Misalkan $T_r$ banyaknya lemparan untuk memperoleh $r$ gambar (peluang gambar $p$ ). Tuliskan $T_r$ sebagai jumlah $r$ peubah geometrik yang saling bebas, lalu simpulkan

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

lalu uraikan $G_{T_r}$ untuk memperoleh $\P(T_r = n) = \binom{n-1}{r-1} p^r(1-p)^{n-r}$ .

Solusi

Solusi Latihan 23.5.

Waktu tunggu antara gambar yang berurutan merupakan peubah geometrik $\mathcal{G}(p)$ yang saling bebas (sifat tanpa ingatannya: sesudah setiap gambar permainannya mulai lagi), jadi $T_r = W_1 + \dots + W_r$ dan kemultiplikatifannya (Teorema 23.10) memberi

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$ ; ragamnya menjumlah menurut kesalingbebasannya). Penguraiannya: menurut deret binomial yang diperumum (Bab 11), $(1 - qt)^{-r} = \sum_{m\geq0} \binom{m + r - 1}{r - 1}q^mt^m$ , jadi koefisien $t^n$ pada $p^rt^r(1 - qt)^{-r}$ adalah (dengan $m = n - r$ )

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

yakni hukum binomial negatif — secara kombinatorik: gambar ke- $r$ jatuh pada lemparan $n$ bila dan hanya bila $r - 1$ gambar sebelumnya memilih tempatnya di antara $n - 1$ lemparan pertamanya.

Latihan 23.6 ★★

Untuk hukum keturunan $p_0 = \frac18$ , $p_1 = \frac38$ , $p_2 = \frac38$ , $p_3 = \frac18$ : hitunglah $m$ , putuskanlah kesuperkritisannya, lalu hitunglah peluang kepunahan $q$ secara persis. (Faktorkan keluar akar $t = 1$ dari $G(t) - t$ .)

Solusi

Solusi Latihan 23.6.

$m = 1\cdot\frac38 + 2\cdot\frac38 + 3\cdot\frac18 = \frac{3 + 6 + 3}{8} = \frac32 > 1$ : superkritis. Fungsi pembangkitnya adalah

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

jadi titik tetapnya memecahkan $(1 + t)^3 = 8t$ , yakni $t^3 + 3t^2 - 5t + 1 = 0$ . Dengan memfaktorkan keluar akar terjaminnya $t = 1$ :

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

dan $t^2 + 4t - 1 = 0$ memberi $t = -2 \pm \sqrt5$ . Akar pada $\intco{0}{1}$ adalah $\sqrt5 - 2 \approx 0.236$ : menurut Teorema 23.25,

q = \sqrt 5 - 2 .

(Pemeriksaan yang menyenangkan: hukum keturunannya adalah hukum $3$ koin setimbang yang saling bebas, $Z_1 \sim \mathcal{B}(3, \frac12)$ .)

Latihan 23.7 ★★★

(Total keturunan) Pada sebuah proses percabangan subkritis ( $m < 1$ ), misalkan $Y = \sum_{n\geq0} Z_n$ jumlah seluruh individu yang pernah lahir. Tunjukkan $\E(Y) = \sum_n m^n = \frac{1}{1 - m}$ (sahkanlah pertukaran penjumlahannya), lalu buktikan bahwa fungsi pembangkit $H = G_Y$ memenuhi persamaan fungsional $H(t) = t\,G(H(t))$ . (Leluhurnya, ditambah total keturunan masing-masing anaknya, yang merupakan salinan bebas dari $Y$ .)

Solusi

Solusi Latihan 23.7.

Nilai harapannya. Mula-mula $\E(Z_n) = m^n$ : menurut Teorema 23.17, $\E(Z_{n+1}) = \E(Z_n)\,m$ , dan $\E(Z_0) = 1$ . Keluarga $\bigl(Z_n(\omega)\P(\{\omega\}) \bigr)_{n, \omega}$ taknegatif, jadi Fubini untuk keluarga berlaku tanpa syarat:

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

(khususnya $Y$ berhingga hampir pasti: sesuai dengan kepunahan yang pasti pada kasus subkritisnya).

Persamaan fungsionalnya. Uraikan populasinya menurut anak leluhurnya: bila leluhurnya punya $Z_1 = k$ anak, maka total keturunannya adalah $Y = 1 + Y_1 + \dots + Y_k$ , dengan $Y_i$ menyatakan total keturunan garis anak ke- $i$ — dan $Y_i$ merupakan salinan $Y$ yang saling bebas, bebas pula dari $Z_1$ (garis yang berbeda memakai kejadian perkembangbiakan yang saling lepas dan saling bebas). Dengan menyaratkan pada $Z_1$ seperti pada Teorema 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),

dengan faktor $t$ memperhitungkan leluhurnya sendiri. (Untuk hukum $p_0 = 1 - p$ , $p_2 = p$ pada percabangan biner, persamaan kuadrat dalam $H$ ini dapat dipecahkan secara eksplisit lalu diuraikan — dan bilangan Catalan pada Bab 11 mencacah pohon keluarganya.)

Latihan 23.8 ★★★

Misalkan $X$ berfungsi pembangkit $G$ dengan jari-jari kekonvergenan $> 1$ . Buktikanlah batas ekor eksponensialnya: ada $C > 0$ dan $\rho \in \intoo{0}{1}$ dengan $\P(X \geq n) \leq C\rho^n$ . (Markov yang diterapkan pada $t^X$ untuk sebuah $t > 1$ yang tetap di dalam cakramnya.) Sebaliknya, tunjukkan bahwa bila $\P(X \geq n) \leq C\rho^n$ dengan $\rho < 1$ , maka jari-jari $G$ adalah $\geq 1/\rho > 1$ .

Solusi

Solusi Latihan 23.8.

Misalkan $R > 1$ jari-jarinya lalu tetapkan $t \in \intoo{1}{R}$ . Maka $\E(t^X) = G(t) < \infty$ , dan ketaksamaan Markov (Teorema 22.15) yang diterapkan pada peubah taknegatif $t^X$ pada aras $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}.

Konversnya: bila $\P(X \geq n) \leq C\rho^n$ , maka $p_n \leq \P(X \geq n) \leq C\rho^n$ , jadi untuk $\abs t < \frac1\rho$ deret $\sum p_n\abs t^n$ terdominasi oleh deret geometrik yang konvergen $C\sum(\rho\abs t)^n$ : jari-jarinya sedikitnya $\frac1\rho > 1$ . Jari-jari fungsi pembangkitnya dan peluruhan geometrik ekornya merupakan dua muka satu sifat yang sama.

Latihan 23.9 ★★★

(Teorema kekontinuan, kasus dasarnya) Misalkan $X, X_1, X_2, \dots$ bernilai- $\N$ dengan $G_{X_n}(t) \to G_X(t)$ untuk setiap $t \in \intco{0}{1}$ . Tunjukkan bahwa $\P(X_n = k) \to \P(X = k)$ untuk setiap $k$ . (Induksi atas $k$ : untuk $k = 0$ ambil $t \to 0$ — dengan hati-hati: tetapkan $t$ yang kecil, pakailah $\abs{\P(X_n = 0) - G_{X_n}(t)} \leq \frac{t}{1-t}$ , yang sah sebab ekornya $\sum_{j \geq 1}p_jt^j \leq \frac{t}{1 - t}$ ; lalu diagonalkan. Untuk langkah induksinya, tinjaulah $\frac{G(t) - \P(X = 0)}{t}$ , yakni fungsi pembangkit sebuah hukum yang tergeser.)

Solusi

Solusi Latihan 23.9.

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

Kasus $k = 0$ . Untuk $t \in \intoo{0}{1}$ dan sebarang hukum $(q_j)$ dengan $\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} .

Jadi

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

Diberikan $\varepsilon > 0$ , pilihlah $t$ dengan $\frac{2t}{1-t} < \frac\varepsilon2$ , lalu $n_0$ sedemikian sehingga suku terakhirnya $< \frac\varepsilon2$ untuk $n \geq n_0$ : jadi $p_0^{(n)} \to p_0$ .

Langkah induksinya. Andaikan $p_j^{(n)} \to p_j$ untuk $j < k$ . Tinjaulah fungsi yang tergeser

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

yakni fungsi pembangkit barisan subpeluang $(p^{(n)}_{j+1})_j$ (bermassa total $\leq 1$ , dan hanya itulah yang dipakai hujah $k = 0$ ). Untuk $t \in \intoo{0}{1}$ yang tetap, $g_n(t) \to g(t)$ menurut hipotesisnya dan kasus $k = 0$ . Menerapkan hujah $k = 0$ pada $g_n$ memberi $p_1^{(n)} \to p_1$ ; dengan mengiterasi geserannya $k$ kali diperoleh $p_k^{(n)} \to p_k$ untuk setiap $k$ . (Inilah contoh diskret dan dasar teorema kekontinuan Lévy, yang bentuk umumnya — bagi fungsi karakteristik — merupakan tonggak Tahun ke-3.)

Latihan 23.10 ★

(Kiat keparitasan) Tunjukkan bahwa untuk peubah bernilai- $\N$ bernama $X$ ,

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

lalu hitunglah peluang ini untuk $X \sim \mathcal P(\lambda)$ dan $X \sim \mathcal B(n, p)$ . Apakah makna $G_X(-1) \to 0$ secara peluang?

Solusi

Solusi Latihan 23.10.

Secara titik demi titik, $\frac{1 + (-1)^X}{2}$ bernilai $1$ ketika $X$ genap dan $0$ ketika ganjil, jadi dengan mengambil nilai harapannya (pemindahan),

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

Poisson: $\frac{1 + \eu^{-2\lambda}}2 \to \frac12$ ketika $\lambda$ membesar. Binomial: $\frac{1 + (1 - 2p)^n}2$ . Pada kedua kasusnya $G_X(-1) \to 0$ berarti keparitasan $X$ menjadi koin yang setimbang: hukumnya menyebar ke banyak bilangan bulat lalu melupakan keparitasannya.

Latihan 23.11 ★★

(Dadu Sicherman) Sahkanlah pemfaktoran fungsi pembangkit dadu setimbangnya

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

lalu tunjukkan bahwa kedua dadu bermuka $\{1, 2, 2, 3, 3, 4\}$ dan $\{1, 3, 4, 5, 6, 8\}$ punya fungsi pembangkit $\frac{t(1+t)(1+t+t^2)}6$ dan $\frac{t(1+t)(1+t+t^2)(1-t+t^2)^2}6$ , yang hasil kalinya sama dengan hasil kali dua dadu baku: dadu eksotis ini menghasilkan setiap total $2, \dots, 12$ dengan peluang yang persis sama dengan peluang bakunya.

Solusi

Solusi Latihan 23.11.

$t + \dots + t^6 = t\,\frac{1 - t^6}{1 - t}$ dan $1 - t^6 = (1 - t)(1 + t)(1 + t + t^2)(1 - t + t^2)$ , yang memberikan pemfaktoran yang dinyatakan itu. Untuk dadu pertamanya, $(1 + t)(1 + t + t^2) = 1 + 2t + 2t^2 + t^3$ , jadi $\frac{t(1+t)(1+t+t^2)}6 = \frac{t + 2t^2 + 2t^3 + t^4}6$ : bermuka $\{1, 2, 2, 3, 3, 4\}$ . Untuk yang kedua, dengan menguraikan

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

jadi $\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$ : bermuka $\{1, 3, 4, 5, 6, 8\}$ . Adapun hasil kali kedua fungsi pembangkitnya menyusun ulang keenam faktornya menjadi $\bigl(\frac{t(1+t)(1+t+t^2)(1-t+t^2)}6 \bigr)^2$ , yakni kuadrat fungsi dadu bakunya: pasangan Sicherman itu berhukum persis sama dengan yang baku bagi totalnya — dan fungsi pembangkit mengelompokkan semua penyusunan ulang semacam itu.

Latihan 23.12 ★★★

(Menunggu dua gambar berturut-turut) Sekeping koin dengan peluang gambar $p$ dilempar sampai muncul dua gambar berurutan; misalkan $T$ banyaknya lemparan (permainan pada Latihan 21.6). Dengan menyaratkan pada lemparan pertamanya, turunkan sistem linear bagi fungsi pembangkit dari keadaan “belum ada gambar” dan “sudah satu gambar”, lalu simpulkan

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

periksalah $G_T(1) = 1$ dan $\E(T) = \dfrac{1 + p}{p^2}$ ( $= 6$ untuk koin yang setimbang).

Solusi

Solusi Latihan 23.12.

Misalkan $A$ dan $B$ fungsi pembangkit sisa lamanya permainan yang bermula dari “belum ada gambar” dan “sudah satu gambar”. Satu lemparan terpakai, lalu: dari keadaan $0$ , angka mengembalikannya ke keadaan $0$ , sedangkan gambar memindahkannya ke keadaan $1$ ; dari keadaan $1$ , gambar mengakhiri permainannya, sedangkan angka mengembalikannya ke keadaan $0$ :

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

Dengan menyubstitusikannya: $A(1 - qt) = pt\,B = pt(pt + qtA)$ , jadi

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

Di $t = 1$ penyebutnya adalah $1 - q - pq = p(1 - q) = p^2$ : $G_T(1) = 1$ , jadi permainannya berakhir hampir pasti (sebagaimana ditunjukkan Latihan 21.6 lewat rekursi). Penurunan logaritmik di $1$ : $\E(T) = 2 - \frac{D'(1)}{D(1)}$ dengan $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},

yang bernilai $6$ untuk $p = \frac12$ .

23.6 Soal: proses Galton–Watson, terpecahkan

Soal 23.1

Soal akhir pekan — laju tumbuh, pemecahan persis, total keturunan, dan taksiran kritis Kolmogorov

Kriteria kepunahan (Teorema 23.25) membelah proses percabangan menjadi subkritis, kritis, dan superkritis — tetapi ia tak berkata apa pun tentang lajunya: seberapa cepat garis yang tertakdir punah itu mati, seberapa besar garis yang sintas itu tumbuh. Soal ini menghitungnya. Kita pertahankan notasi babnya: hukum keturunan $(p_k)$ dengan fungsi pembangkit $G$ , rerata $m = G'(1)$ , ukuran generasi $Z_n$ ( $Z_0 = 1$ ), iterat $G_n = G_{Z_n}$ , peluang kepunahan $q_n = \P(Z_n = 0) \uparrow q$ ; kita selalu mengandaikan $p_1 \neq 1$ dan, di tempat momen kedua muncul, $G''(1) < \infty$ , lalu kita tuliskan $\sigma^2 = V(Z_1)$ .

Bagian I — Momen generasinya.

Tunjukkan $\E(Z_n) = m^n$ (aturan rantai pada $G_n = G \circ G_{n-1}$ di $1^-$ , dengan memakai $G_{n-1}(1) = 1$ dan Teorema 23.7).
Tegakkan rekursi $G_n''(1) = G''(1)\,m^{2(n-1)} + m\,G_{n-1}''(1)$ lalu pecahkan: $G_n''(1) = G''(1)\,m^{n-1}\dfrac{m^n - 1}{m - 1}$ untuk $m \neq 1$ , dan $G_n''(1) = n\,G''(1)$ untuk $m = 1$ .
Simpulkan

$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).$
(Laju subkritis, batas atas) Untuk $m < 1$ , tunjukkan $\P(Z_n > 0) \leq m^n$ (Markov pada $Z_n$ yang bernilai bulat): kepunahannya pasti dengan laju geometrik — yakni penghalusan kuantitatif atas kriteria babnya.
(Laju subkritis, batas bawah) Dengan memakai Cauchy–Schwarz pada $Z_n\mathbf 1_{Z_n > 0}$ , tunjukkan

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

laju geometriknya $m^n$ persis sampai konstantanya.

Bagian II — Keluarga geometrik, terpecahkan persis. Ambil hukum keturunan yang geometrik pada $\N$ : $p_k = qp^k$ ( $k \geq 0$ ), dengan $0 < p < 1$ , $q = 1 - p$ .

Hitunglah $G(t) = \dfrac{q}{1 - pt}$ dan $m = \dfrac pq$ ; lalu letakkan ketiga rezimnya dalam $p$ .
Pecahkan $G(t) = t$ : tunjukkan bahwa titik tetapnya $1$ dan $q/p = 1/m$ , lalu pulihkan peluang kepunahannya $q_{\mathrm{ext}} = \min(1, 1/m)$ .
Buktikan menurut induksi bentuk tertutupnya

$q_n = \frac{m^n - 1}{m^{n+1} - 1} \quad (m \neq 1), \qquad q_n = \frac{n}{n+1} \quad (m = 1).$
Simpulkan laju persisnya: $1 - q_n \sim (1 - m)\,m^n$ pada kasus subkritisnya, dan $q_{\mathrm{ext}} - q_n \sim \dfrac{m - 1}{m^{2}}\cdot m^{-n}$ pada kasus superkritisnya; periksalah bahwa nisbah pengerutan superkritisnya adalah $G'(q_{\mathrm{ext}}) = 1/m$ .
Kasus kritisnya ( $p = \tfrac12$ ): hitunglah $\sigma^2 = 2$ lalu catat $1 - q_n = \frac1{n+1}$ : kesintasannya meluruh seperti $\frac1n$ — tak geometrik dan tak terjumlahkan.
Masih kritis: buktikan menurut induksi iterat penuhnya

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

lalu simpulkan bahwa dengan disyaratkan pada kesintasannya, $Z_n$ geometrik pada $\N^*$ dengan 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 .$

Garis rata-ratanya mati, tetapi garis yang sintas berukuran orde $n$ .

Bagian III — Total keturunan. Misalkan $Y = \sum_{n\geq0}Z_n \in \N^* \cup \{\infty\}$ jumlah seluruh individu yang pernah lahir, dan $H(t) = \sum_{k\geq1}\P(Y = k)t^k$ .

Sahkanlah $\P(Y < \infty) = q_{\mathrm{ext}}$ , lalu ingat kembali dari Latihan 23.7 persamaan fungsional $H(t) = t\,G(H(t))$ (yang penurunannya tak memakai $m < 1$ ).
(Percabangan biner) Untuk $p_0 = p_2 = \frac12$ (kritis), pecahkan persamaan fungsionalnya:

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

lalu uraikan dengan Contoh 11.21 untuk memperoleh

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

periksalah nilai $\P(Y = 1) = \frac12$ dan $\P(Y = 3) = \frac18$ lewat pencacahan langsung.
Dengan menurunkan persamaan fungsionalnya di $1^-$ , tunjukkan bahwa $\E(Y) = \frac{1}{1-m}$ untuk $m < 1$ , sedangkan kekritisannya memaksa $\E(Y) = \infty$ : total keturunan kritisnya berhingga hampir pasti dengan rerata tak hingga.
Dengan asimtotik binomial pusatnya (Contoh 6.14), tunjukkan

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

yakni ekor berat $k^{-3/2}$ , lalu simpulkan $\P(Y > n) \asymp n^{-1/2}$ (batas atas dan bawah berorde ini sudah memadai).
Bandingkan dengan jalan acak setimbang (soal akhir pekan pada Bab 21): waktu pulang yang pasti tetapi dengan rerata tak hingga di sana, total keturunan yang pasti tetapi dengan rerata tak hingga di sini, keduanya dengan hukum lokal $n^{-3/2}$ . Satu paragraf tentang mengapa kekritisannya menghasilkan tanda tangan ini.

Bagian IV — Taksiran Kolmogorov pada kekritisannya. Andaikan $m = 1$ , $0 < \sigma^2 = G''(1) < \infty$ .

Tunjukkan bahwa $G''$ meluas secara kontinu ke $\intcc01$ (taknegatif dan naik dengan limit yang berhingga) lalu simpulkan uraian Taylornya di $1$ :

$G(t) = t + b\,(1-t)^2 + o\bigl((1-t)^2\bigr), \qquad b = \frac{G''(1)}2 = \frac{\sigma^2}2 .$
Untuk $t \in \intco01$ , tetapkan $h(t) = \dfrac1{1 - G(t)} - \dfrac1{1 - t}$ . Tunjukkan

$h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)} \xrightarrow[t\to1^-]{} b .$
Teleskopkan sepanjang iterasi $q_{j+1} = G(q_j)$ :

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

lalu rampungkan dengan hujah Cesàro bahwa

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

— yakni taksiran Kolmogorov: setiap proses percabangan kritis mati dengan laju semesta $1/n$ , dan hanya konstantanya yang mengingat hukum keturunannya.
Periksalah taksiran itu terhadap kasus geometrik kritis pada pertanyaan 10.
Simpulkan $\E(Z_n \mid Z_n > 0) = \dfrac{1}{1 - q_n} \sim \dfrac{\sigma^2 n}{2}$ (catat $\E(Z_n \mathbf 1_{Z_n>0}) = \E(Z_n) = 1$ ), lalu periksalah terhadap pertanyaan 11: dengan disyaratkan pada kesintasannya, populasinya tumbuh secara linear — itulah tali kritis antara kematian dan ledakan.

Bagian V — Terapan dan sintesisnya.

(Wabah, reaksi berantai) Untuk hukum keturunan Poisson $\mathcal P(\lambda)$ — setiap kasus menulari $\mathcal P(\lambda)$ kasus baru — tuliskan persamaan kepunahannya $q = \eu^{\lambda(q-1)}$ lalu pecahkan secara numerik untuk $\lambda = 1.5$ ( $q \approx 0.417$ ) dan $\lambda = 2$ ( $q \approx 0.203$ ): bermula dari satu kasus, wabah besar itu tidak pasti bahkan ketika $\lambda > 1$ . Jelaskan mengapa iterasi $q_{n+1} = \eu^{\lambda(q_n - 1)}$ dari $q_0 = 0$ konvergen ke akar yang benar.
Bermula dari $k$ leluhur alih-alih satu, tunjukkan bahwa peluang kepunahannya adalah $q^k$ . Terapannya: dengan $\lambda = 1.5$ , berapa banyak kasus awal yang membuat wabah berkemungkinan sedikitnya $99\%$ ?
(Menyaratkan proses superkritis pada kepunahannya) Untuk $m > 1$ dengan peluang kepunahan $q \in \intoo01$ : buktikan dahulu lewat kecembungannya bahwa $G'(q) < 1$ di titik tetap terkecilnya, lalu simpulkan $q_{\mathrm{ext}} - q_n = O\bigl(G'(q)^n\bigr)$ (kekonvergenan geometrik, sebagaimana dicontohkan pertanyaan 9). Lalu tunjukkan bahwa $\widehat G(t) = G(qt)/q$ merupakan fungsi pembangkit sebuah hukum keturunan yang sahih, dengan rerata $\widehat m = G'(q) < 1$ : yakni proses pendamping yang subkritis. Sahkanlah pada keluarga geometriknya: menyaratkan proses $(p, q)$ yang superkritis pada kepunahannya menukar $p$ dan $q$ . (Pernyataan lengkapnya — bahwa proses yang disyaratkan itu adalah proses pendampingnya — dibuktikan pada jilid Tahun ke-3; di sini yang telah disahkan barulah bayangan fungsi pembangkitnya.)
Sintesis: susunlah tabel trikotominya — untuk $m < 1$ , $m = 1$ , $m > 1$ : nilai $q$ ; laju $\P(Z_n > 0)$ atau laju $q - q_n$ ; $\E(Y)$ ; ukuran sebuah generasi yang sintas. Nyatakan dalam satu kalimat per perkakas bagaimana komposisi fungsi pembangkit, kecembungan, Taylor di $1^-$ , dan perata-rataan Cesàro membawa seluruh soal ini, dan apa yang ditambahkan jilid Tahun ke-3 (martingal $Z_n/m^n$ dan hukum limit eksponensial Yaglom).

Solusi

Solusi Soal 23.1.

1. Untuk $t \in \intoo01$ , aturan rantai pada $G_n = G \circ G_{n-1}$ memberi $G_n'(t) = G'\bigl(G_{n-1}(t)\bigr)G_{n-1}'(t)$ . Ketika $t \to 1^-$ , $G_{n-1}(t) \uparrow 1$ , dan $G'$ tidak turun dengan limit kiri $m$ di $1$ , jadi faktor pertamanya menuju $m$ ; menurut induksi faktor keduanya menuju $m^{n-1}$ . Menurut Teorema 23.7, $\E(Z_n) = G_n'(1^-) = m^n$ .

2. Dengan menurunkannya sekali lagi,

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

lalu dengan membiarkan $t \to 1^-$ : $a_n = G''(1)m^{2(n-1)} + m\, a_{n-1}$ dengan $a_n = G_n''(1)$ , $a_1 = G''(1)$ . Untuk $m \neq 1$ orang memeriksa menurut induksi bahwa $a_n = G''(1)\,m^{n-1} \frac{m^n - 1}{m - 1}$ (rekursinya menambahkan $G''(1)m^{2n-2}$ pada $m\cdot G''(1)m^{n-2}\frac{m^{n-1}-1}{m-1}$ , dan $m^{n-1} + \frac{m^{n-1}-1}{m-1} = \frac{m^n - 1}{m-1}$ ); untuk $m = 1$ , $a_n = a_{n-1} + G''(1) = n\,G''(1)$ .

3. $V(Z_n) = a_n + m^n - m^{2n}$ dan $G''(1) = \sigma^2 + m^2 - m$ . Untuk $m \neq 1$ , potongan $(m^2 - m)m^{n-1}\frac{m^n-1}{m-1} = m^n(m^n - 1)$ meniadakan $m^n - m^{2n}$ secara persis, sehingga tersisa $V(Z_n) = \sigma^2m^{n-1}\frac{m^n-1}{m-1}$ . Untuk $m = 1$ : $V(Z_n) = nG''(1) = n\sigma^2$ .

4. $Z_n$ merupakan peubah bulat taknegatif, jadi $\P(Z_n > 0) = \P(Z_n \geq 1) \leq \E(Z_n) = m^n$ menurut Markov (Teorema 22.15). Untuk $m < 1$ ini meluruh secara geometrik — dan terjumlahkan, jadi Borel–Cantelli bahkan memberi bahwa hanya berhingga banyak generasinya yang takkosong, dan itu pun kepunahan lagi.

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)$ . Dengan pertanyaan 3 dan $m < 1$ :

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

jadi, dengan membagi $m^{2n}$ oleh batas ini lalu menyederhanakannya oleh $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 ,

dengan memakai $m^n \leq 1$ pada penyebutnya. Dengan pertanyaan 4: $\P(Z_n > 0) \asymp m^n$ .

6. $G(t) = q\sum_k(pt)^k = \frac{q}{1 - pt}$ , dan $m = G'(1) = \frac{pq}{(1-p)^2} = \frac pq$ . Subkritis untuk $p < \frac12$ , kritis untuk $p = \frac12$ , dan superkritis untuk $p > \frac12$ .

7. $G(t) = t$ berbunyi $pt^2 - t + q = 0$ , dengan akar $\frac{1 \pm \abs{p - q}}{2p}$ , yakni $1$ dan $\frac qp = \frac1m$ . Peluang kepunahannya adalah titik tetap terkecil pada $\intcc01$ (Teorema 23.25): $q_{\mathrm{ext}} = 1$ bila $m \leq 1$ , dan $\frac1m$ bila $m > 1$ .

8. Untuk $m \neq 1$ , dengan $p = \frac m{m+1}$ , $q = \frac1{m+1}$ : bila $q_n = \frac{m^n - 1}{m^{n+1} - 1}$ , maka

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

jadi $q_{n+1} = \frac{q}{1 - pq_n} = \frac{m^{n+1} - 1}{m^{n+2} - 1}$ ; dan kasus dasarnya $q_0 = 0$ berlaku. Untuk $m = 1$ : $G(t) = \frac1{2 - t}$ dan $q_{n+1} = \frac1{2 - \frac{n}{n+1}} = \frac{n+1}{n+2}$ , dengan $q_0 = 0$ .

9. $1 - q_n = \frac{m^n(m - 1)}{m^{n+1} - 1}$ . Untuk $m < 1$ penyebutnya menuju $-1$ : $1 - q_n \sim (1 - m)\,m^n$ . Untuk $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} .

Adapun $G'(t) = \frac{pq}{(1 - pt)^2}$ yang dievaluasi di $t = \frac qp$ (tempat $1 - pt = 1 - q = p$ ) memberi $G'(q_{\mathrm{ext}}) = \frac qp = \frac1m$ : nisbah teramatinya $m^{-1}$ persis merupakan turunannya di titik tetap penariknya.

10. Untuk $p = \frac12$ : $G''(t) = \frac{1/4}{(1 - t/2)^3}$ , jadi $G''(1) = 2$ dan $\sigma^2 = G''(1) + m - m^2 = 2$ . Bentuk tertutupnya memberi $1 - q_n = \frac1{n+1}$ : adapun peluang kesintasannya meluruh seperti $1/n$ — terlalu pelan untuk terjumlahkan, tak seperti laju subkritis mana pun.

11. Induksi: $G_1(t) = \frac1{2-t}$ cocok dengan rumusnya untuk $n = 1$ , dan

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

Lalu

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

yakni fungsi pembangkit hukum geometrik $\mathcal G\bigl(\frac1{n+1} \bigr)$ pada $\N^*$ (Contoh 23.4): bila kesintasannya diketahui, $\P(Z_n = k \mid Z_n > 0) = \frac1{n+1}\bigl(\frac n{n+1}\bigr)^{k-1}$ , dengan rerata bersyarat $n + 1$ . Adapun rerata tanpa syaratnya $1 = \E(Z_n)$ merupakan hasil kali peluang kesintasan yang melenyap dan ukuran bersyarat yang tumbuh secara linear.

12. Bila garisnya punah pada generasi $n$ , maka $Y = Z_0 + \dots + Z_{n-1}$ berhingga; bila ia tak pernah punah, maka $Y \geq \sum_n 1 = \infty$ . Jadi $\{Y < \infty\}$ merupakan kejadian kepunahannya dan $\P(Y < \infty) = q_{\mathrm{ext}}$ . Adapun penurunan $H(t) = tG(H(t))$ pada Latihan 23.7 — leluhurnya menyumbang faktor $t$ , sedangkan anaknya mendirikan salinan $Y$ yang saling bebas dan tercacah lewat $G$ — hanya memakai Teorema 23.17, yang sah pada setiap rezimnya.

13. Dengan $G(s) = \frac{1 + s^2}2$ persamaannya berbunyi $tH^2 - 2H + t = 0$ , jadi $H = \frac{1 - \sqrt{1 - t^2}}{t}$ (yakni akar dengan $H(0) = 0$ ). Dengan membandingkannya dengan deret Catalan $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$ (Contoh 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}}$ , yakni $\P(Y = 2k+1) = C_k2^{-2k-1}$ . Pemeriksaannya: $\P(Y = 1) = C_0/2 = \frac12$ (leluhurnya tak punya anak); $\P(Y = 3) = C_1/8 = \frac18$ (dua anak, keduanya tanpa anak: $\frac12\cdot\frac12\cdot \frac12$ ).

14. Dengan menurunkan $H = tG(H)$ pada $\intoo01$ lalu membiarkan $t \to 1^-$ (limit monotonnya seperti pada Teorema 23.7): $H'(1)\bigl(1 - G'(H(1))\bigr) = G(H(1))$ . Pada kasus subkritisnya $H(1) = 1$ dan $\E(Y) = H'(1) = \frac1{1 - m}$ . Pada kasus kritisnya $G'(1) = 1$ membuat faktor kirinya lenyap sedangkan ruas kanannya bernilai $1$ : tak ada $H'(1)$ berhingga yang mungkin ada, jadi $\E(Y) = \infty$ — padahal $\P(Y < \infty) = q = 1$ .

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

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

Dengan menjumlahkan ekornya (perbandingan dengan $\int_K^\infty k^{-3/2}\dd k = 2K^{-1/2}$ , dari atas dan dari bawah): $\P(Y > 2K) \asymp K^{-1/2}$ , yakni $\P(Y > n) \asymp n^{-1/2}$ — sebuah ekor berat dengan rerata tak hingga, yang mengkuantifikasi pertanyaan 14.

16. Kedua objek kritisnya — waktu pulang jalan setimbang (soal akhir pekan pada Bab 21) dan total keturunan kritisnya — berhingga hampir pasti dengan rerata tak hingga, dengan hukum lokal bereksponen $-3/2$ dan ekor bereksponen $-1/2$ . Ini bukan kebetulan: menjelajahi sebuah pohon keluarga anak demi anak akan menghasilkan lintasan $\pm1$ (satu langkah naik per kelahiran, satu langkah turun per kematian) yang persis merupakan jalan setimbang, dan $Y$ menjadi waktu lintas pertamanya. Kekritisannya berarti hanyutan nol: prosesnya selalu berada di ambang kepunahan sekaligus ledakan, dan fluktuasi berskala $\sqrt{}$ dari keacakan yang berhanyutan nol menghasilkan persis eksponen ini.

17. $G''(t) = \sum_{n\geq2}n(n-1)p_nt^{n-2}$ bersuku taknegatif, jadi ia tidak turun pada $\intco01$ dengan limit berhingga $G''(1) = \sigma^2$ (kekritisannya membuat $\E Z_1(Z_1 - 1) = \sigma^2$ ); dan fungsi yang tidak turun dengan limit yang sama dengan nilai perbatasannya itu kontinu di $1$ . Taylor dengan sisa integral di titik $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),

sebab $G''(s) = G''(1) + o(1)$ ketika $s \to 1^-$ .

18. Dengan menyamakan penyebutnya, $h(t) = \frac{G(t) - t}{(1 - G(t))(1 - t)}$ . Menurut pertanyaan 17 pembilangnya adalah $b(1-t)^2 + o((1-t)^2)$ dan $1 - G(t) = (1 - t)\bigl(1 - b(1-t) + o(1-t)\bigr)$ , jadi $h(t) \to b$ .

19. Menurut definisi $h$ di $t = q_j$ dan $G(q_j) = q_{j+1}$ : $\frac1{1 - q_{j+1}} - \frac1{1-q_j} = h(q_j)$ ; menjumlahkannya dari $j = 0$ ( $q_0 = 0$ ) memberikan paparannya. Karena proses kritisnya punah, $q_j \uparrow 1$ , jadi $h(q_j) \to b$ dan rerata Cesàro $\frac1n\sum_{j<n}h(q_j) \to b$ : $\frac1{1-q_n} \sim bn$ , yakni

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

20. Kasus geometrik kritisnya: $\sigma^2 = 2$ (pertanyaan 10), jadi Kolmogorov meramalkan $1 - q_n \sim \frac1n$ — dan nilai persisnya adalah $\frac1{n+1}$ .

21. Karena $Z_n\mathbf 1_{Z_n > 0} = Z_n$ , maka $\E(Z_n \mid Z_n > 0) = \frac{\E(Z_n)}{\P(Z_n > 0)} = \frac1{1 - q_n} \sim \frac{\sigma^2n}2$ . Pada kasus geometriknya ini bernilai $n + 1$ , yang cocok persis dengan pertanyaan 11 ( $\sigma^2 = 2$ ). Adapun gambaran kritisnya: kepunahannya pasti, ukuran reratanya membeku di $1$ , dan garis sintas yang langka itu berukuran tumbuh secara linear — masing-masing faktornya mengimbangi yang lain.

22. Untuk keturunan $\mathcal P(\lambda)$ , $G(t) = \eu^{\lambda(t-1)}$ dan peluang kepunahannya adalah akar terkecil $q = \eu^{\lambda(q-1)}$ . Secara numerik: $\lambda = 1.5$ memberi $q \approx 0.417$ (iterasikan $q \mapsto \eu^{1.5(q-1)}$ : $0, 0.223, 0.312, 0.356, \dots \to 0.4172$ ); $\lambda = 2$ memberi $q \approx 0.203$ . Jadi satu kasus indeks memantik wabah besar dengan peluang $58\%$ ( $\lambda = 1.5$ ) atau $80\%$ ( $\lambda = 2$ ) — mungkin, tetapi tak pasti. Iterasi dari $q_0 = 0$ konvergen ke akar terkecilnya sebab $G$ tidak turun: menurut induksi $q_n \leq r$ bagi sebarang titik tetap $r$ , dan $(q_n)$ naik (ia adalah $\P(Z_n = 0)$ ), jadi limitnya merupakan titik tetap di bawah semua yang lain.

23. Ke- $k$ leluhurnya mendirikan pohon keluarga yang saling bebas, dan kepunahan totalnya adalah irisan $k$ kejadian kepunahan yang saling bebas: peluangnya $q^k$ . Untuk $\lambda = 1.5$ : peluang wabah $1 - q^k \geq 0.99$ menuntut $q^k \leq 0.01$ , yakni $k \geq \frac{\ln 0.01}{\ln 0.417} \approx 5.3$ : jadi enam kasus awal membuat wabahnya $99\%$ pasti.

24. $G'(q) < 1$ : $G - \mathrm{id}$ cembung dan lenyap di $q$ dan $1$ , jadi ia $\leq 0$ pada $\intcc q1$ ; bila $G'(q) = 1$ , maka singgungnya di $q$ (yang oleh kecembungannya diletakkan di bawah $G$ ) akan memaksa $G(t) \geq t$ pada $\intcc q1$ , sehingga $G \equiv \mathrm{id}$ di sana, yang mematikan semua koefisien $p_n$ ( $n \geq 2$ ) dan bertentangan dengan $m > 1$ . Kekonvergenan geometriknya: $q_n < q$ untuk semua $n$ (induksi, dengan $G$ naik), dan teorema nilai rata-rata memberi $q - q_{n+1} = G'(c_n)(q - q_n)$ dengan $c_n \in \intoo{q_n}q$ , jadi $G'(c_n) \leq G'(q) < 1$ dan $q - q_n \leq q\,G'(q)^n$ . Proses pendampingnya: $\widehat G(t) = G(qt)/q = \sum_kp_kq^{k-1}t^k$ berkoefisien taknegatif dan $\widehat G(1) = G(q)/q = 1$ : sebuah fungsi pembangkit; reratanya adalah $\widehat G'(1) = G'(q) < 1$ : subkritis. Keluarga geometriknya: $G(t) = \frac{q}{1-pt}$ , $q_{\mathrm{ext}} = \frac qp$ , dan

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

yakni hukum keturunan geometrik dengan $p$ dan $q$ tertukar — proses superkritis yang dipandang pada kejadian kepunahannya adalah cerminan subkritisnya.

25. Tabelnya: $m < 1$ : $q = 1$ , $\P(Z_n > 0) \asymp m^n$ (pertanyaan 4–5), $\E(Y) = \frac1{1-m}$ , dan generasi sintas dengan rerata bersyarat yang terbatas. $m = 1$ : $q = 1$ , $\P(Z_n > 0) \sim \frac2{\sigma^2n}$ (Kolmogorov), $\E(Y) = \infty$ dengan $\P(Y > n) \asymp n^{-1/2}$ , dan penyintas berukuran $\sim \frac{\sigma^2n}2$ . $m > 1$ : $q < 1$ merupakan titik tetap terkecilnya, $q - q_n = O(G'(q)^n)$ , pertumbuhan $\E(Z_n) = m^n$ , dan dengan disyaratkan pada kematiannya prosesnya adalah pendamping subkritisnya (pertanyaan 24). Adapun perkakasnya: komposisi fungsi pembangkit mengubah rekursi populasi menjadi iterasi fungsi; kecembungannya memancangkan geometri titik tetapnya; Taylor di $1^-$ mengubah hipotesis momen menjadi uraian lokal; dan perata-rataan Cesàro memeras $1/n$ Kolmogorov dari sebuah jumlah teleskopik. Adapun jilid Tahun ke-3 menambahkan martingal $Z_n/ m^n$ — yang limit hampir pastinya menghaluskan $\E(Z_n) = m^n$ menjadi laju tumbuh lintasan demi lintasan — dan teorema Yaglom, yakni hukum limit di balik geometri bersyarat yang teramati pada pertanyaan 11.

Istilah yang didefinisikan dalam bab ini

Fungsi pembangkit peluang

Lihat semua 395 istilah di glosarium