Matematika Universitas — Tahun 2 · Bachelor Year 2

21Peluang pada Ruang Terbilang

Ketiga bab terakhir mengembangkan teori peluang modern: yakni ukuran peluang pada ruang sampel yang terbilang, peubah acak diskret, dan fungsi pembangkit. Adapun teori berhingga pada jilid Kelas 10–12 memperoleh infrastruktur penuhnya: sebab keaditifan- $\sigma$ menggantikan keaditifan berhingga, dan perkakas keluarga terjumlahkan pada Bab 7 persis merupakan yang membuat ruang sampel tak hingga dapat dikerjakan. Adapun hasil utamanya di sini adalah kekontinuan peluang sepanjang barisan kejadian yang monoton beserta lema Borel–Cantelli.

21.1 Ruang peluang

Definisi 21.1 (Ruang peluang terbilang)

Misalkan $\Omega$ himpunan tak kosong yang berhingga atau terbilang (yakni ruang sampelnya). Sebuah ukuran peluang pada $\Omega$ adalah pemetaan $\P$ dari himpunan $\mathcal{P}(\Omega)$ berisi semua himpunan bagian $\Omega$ (yakni kejadian) ke $[0, 1]$ sedemikian sehingga:

$\P(\Omega) = 1$ ;
(keaditifan- $\sigma$ ) untuk setiap barisan $(A_n)_{n\in\N}$ berisi kejadian yang saling lepas berpasangan,

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

Adapun pasangan $(\Omega, \P)$ disebut ruang peluang (yang terbilang).

Catatan 21.2

Pada $\Omega$ yang terbilang kita boleh mengambil semua himpunan bagiannya sebagai kejadian; sedangkan pada ruang yang tak terbilang (sebagaimana diperlukan bagi model kontinu pada Tahun ke-3) hal ini tak lagi mungkin, jadi kita membatasi $\P$ pada sebuah koleksi kejadian yang sesuai, yakni sebuah aljabar- $\sigma$ . Adapun semua rumus bab ini bertahan pada penyamarataan itu kata demi kata.

Proposisi 21.3 (Aturan dasar)

Untuk kejadian $A, B$ dan ukuran peluang $\P$ berlaku: $\P(\emptyset) = 0$ ; $\P$ bersifat aditif berhingga; $\P(A^c) = 1 - \P(A)$ ; bila $A \subseteq B$ maka $\P(A) \leq \P(B)$ ; dan

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

Bukti. Menerapkan keaditifan- $\sigma$ pada $A_0 = \Omega$ dan $A_n = \emptyset$ (untuk $n \geq 1$ ) memberi $1 = 1 + \sum_{n\geq1}\P(\emptyset)$ , jadi $\P(\emptyset) = 0$ ; lalu mengganjal gabungan lepas yang berhingga dengan himpunan kosong memberi keaditifan berhingganya. Adapun sisanya menyusul seperti pada kasus berhingganya (jilid Kelas 10–12): sebab $1 = \P(A) + \P(A^c)$ dari $\Omega = A \sqcup A^c$ ; lalu $\P(B) = \P(A) + \P(B \setminus A) \geq \P(A)$ ketika $A \subseteq B$ ; dan setelah diuraikan menjadi tiga keping yang saling lepas,

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

yang tak lain inklusi–eksklusi; sedangkan versi $n$ himpunannya yang umum adalah Latihan 21.4. ∎

Proposisi 21.4 (Distribusi pada ruang terbilang)

Memberikan sebuah ukuran peluang pada $\Omega = \{\omega_0, \omega_1, \dots\}$ yang terbilang persis sama dengan memberikan bobot $p_i = \P(\{\omega_i\}) \geq 0$ dengan $\sum_i p_i = 1$ ; lalu untuk setiap $A \subseteq \Omega$ ,

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

yakni subjumlah (yang konvergen mutlak) keluarga $(p_i)$ .

Bukti. Diberikan $\P$ , singleton $\{\omega\}$ dengan $\omega \in A$ membentuk peliput lepas yang terbilang bagi $A$ , jadi keaditifan- $\sigma$ memaksa

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

yakni subjumlah tanpa syarat keluarga taknegatif yang terjumlahkan $(p_i)$ — sebab penataan ulangnya tak berbahaya persis karena sukunya taknegatif (Bab 7); khususnya $\sum_ip_i = \P(\Omega) = 1$ . Sebaliknya, diberikan bobot taknegatif yang berjumlah total $1$ , definisikanlah $\P(A) = \sum_{\omega \in A}p_\omega$ : maka keluarganya terjumlahkan, dan keaditifan- $\sigma$ -nya persis merupakan teorema penjumlahan lewat paket pada Bab 7 yang diterapkan pada pemartisian $\bigcup A_n$ menjadi $A_n$ . ∎

Contoh 21.5 (Model geometri: menunggu gambar pertama)

Lemparkan sekeping koin yang berpeluang gambar $p \in \intoo{0}{1}$ berulang kali, lalu misalkan $\Omega = \N^* \cup \{\infty\}$ mencatat pangkat gambar pertamanya. Adapun bobot alaminya adalah

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

yakni sebuah ukuran peluang karena $\sum_{k\geq1}(1-p)^{k-1}p = \frac{p}{1 - (1-p)} = 1$ : jadi dengan peluang $1$ permainannya berakhir — tetapi ruang sampelnya tetap harus memuat kemungkinan bahwa ia tidak berakhir. Dan keaditifan terbilangnyalah yang memungkinkan kita menegaskan $\P(\text{permainannya berakhir}) = \sum_k \P(\{k\})$ .

Teorema 21.6 (Kekontinuan monoton)

Misalkan $(A_n)$ barisan kejadian.

Bila $A_n \subseteq A_{n+1}$ untuk setiap $n$ (yakni naik), maka $\P\bigl(\bigcup_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .
Bila $A_n \supseteq A_{n+1}$ untuk setiap $n$ (yakni turun), maka $\P\bigl(\bigcap_n A_n\bigr) = \lim_{n\to\infty} \P(A_n)$ .

Bukti. 1. Lepaskan: misalkan $B_0 = A_0$ dan $B_n = A_n \setminus A_{n-1}$ . Maka $B_n$ saling lepas berpasangan dengan $\bigcup_{k \leq n} B_k = A_n$ dan $\bigcup_n B_n = \bigcup_n A_n$ . Jadi menurut keaditifan- $\sigma$ dan keaditifan berhingganya,

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

2. Beralihlah ke komplemennya: $(A_n^c)$ naik dengan gabungan $\bigl(\bigcap A_n\bigr)^c$ , lalu terapkanlah bagian 1: sehingga $1 - \P(\bigcap A_n) = \lim (1 - \P(A_n))$ . ∎

Akibat 21.7 (Kesubaditifan terbilang)

Untuk sembarang barisan kejadian berlaku $\P\bigl(\bigcup_n A_n\bigr) \leq \sum_{n=0}^\infty \P(A_n)$ .

Bukti. Kesubaditifan berhingganya $\P(A_0 \cup \dots \cup A_N) \leq \sum_0^N \P(A_n)$ menyusul dari inklusi–eksklusi secara induktif (atau dari keaditifan atas $B_n \subseteq A_n$ yang telah dilepaskan). Lalu lewatkan $N \to \infty$ : sebab ruas kirinya konvergen ke $\P(\bigcup_n A_n)$ berkat kekontinuan monoton yang diterapkan pada barisan naik $C_N = A_0 \cup \dots \cup A_N$ . ∎

Contoh 21.8 (Batas gabungan: kasar tetapi tak terhancurkan)

Kesubaditifan dengan berhingga banyak kejadian — yakni batas gabungan — menukar ketepatan dengan keuniversalan. Untuk masalah ulang tahun dengan $23$ orang, membatasi peluang tabrakannya lewat jumlah atas pasangannya memberi

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

terhadap nilai benarnya $0.507$ : jadi meleset dengan selisih lebar, karena tabrakannya bertumpang tindih. Namun batasnya tak menuntut kebebasan, tak menuntut hukum bersama, dan tak menuntut apa pun selain peluang pasangannya — dan itulah sebabnya, pada soal akhir pekan dan di sepanjang Bab 22, batas gabungan menjadi perkakas pertama yang dihunus: sebab ketika ia kebetulan kecil, perkaranya selesai tanpa pemodelan lebih lanjut.

Contoh 21.9 (Sebuah enam datang, cepat atau lambat)

Lemparkan dadu setimbang selamanya lalu misalkan $B_n = {}$ “sekurangnya satu enam di antara $n$ lemparan pertamanya”, yakni barisan kejadian yang naik dengan $\P(B_n) = 1 - (5/6)^n$ . Maka kekontinuan monotonnya memberi

\P(\text{sebuah enam akhirnya muncul}) = \P\Bigl(\bigcup_nB_n\Bigr) = \lim_n\bigl(1 - (5/6)^n\bigr) = 1 .

Yang penting bukanlah limitnya (yang jelas) melainkan langkah logisnya: sebab “akhirnya” merupakan kejadian tentang lemparan yang tak berhingga banyaknya, di luar jangkauan keaditifan berhingga, dan kekontinuan monoton — yakni keaditifan- $\sigma$ — persislah aksioma yang memberinya sebuah peluang. Jadi setiap pernyataan hampir pasti pada sisa buku ini melewati pintu sempit yang sama.

21.2 Penyaratan dan kebebasan

Definisi 21.10 (Peluang bersyarat)

Untuk kejadian $A, B$ dengan $\P(B) > 0$ , peluang bersyarat bagi $A$ jika diketahui $B$ adalah

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

Adapun pemetaan $A \mapsto \P(A \mid B)$ sendiri merupakan ukuran peluang pada $\Omega$ .

Catatan 21.11

Bahwa $A \mapsto \pcond BA$ kembali merupakan ukuran peluang layak direnungkan sejenak: sebab $\pcond B\Omega = 1$ dan keaditifan- $\sigma$ -nya lolos lewat hasil baginya karena irisan dengan $B$ menghormati gabungan yang lepas. Adapun akibat praktisnya: setiap kesamaan pada bab ini — yakni inklusi–eksklusi, kekontinuan monoton, Borel–Cantelli — boleh diterapkan sesudah disyaratkan, tanpa bukti baru. Dan itulah sebabnya para ahli peluang terus-menerus “bekerja di bawah $\pcond B{\cdot}$ ”.

Contoh 21.12 (Penyaratan dapat menciptakan keseragaman)

Lemparkan dua dadu setimbang lalu syaratkan jumlahnya $7$ : maka untuk setiap $k \in \intint16$ ,

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

jadi jika diketahui jumlahnya $7$ , dadu pertamanya persis seragam — sebab $7$ adalah satu-satunya total yang serasi dengan setiap mukanya, jadi penyaratannya menghapus semua informasi tentang $X$ . Adapun total lain memiringkan hukumnya (sebab jika diketahui $S = 4$ , dadu pertamanya seragam pada $\{1, 2, 3\}$ saja). Jadi menghitung hukum bersyarat berarti menormalkan ulang bobot bersamanya sepanjang kejadian penyaratannya, tak lebih.

Contoh 21.13 (Tarikan kedua sama baiknya dengan yang pertama)

Sebuah guci berisi $3$ bola putih dan $2$ bola hitam; tariklah dua tanpa pengembalian. Semua orang sepakat $\P(W_1) = \frac35$ ; lalu berapa $\P(W_2)$ ? Peluang total sepanjang tarikan pertamanya:

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

yakni persis $\P(W_1)$ . Jadi tak ada perhitungan yang diperlukan: sebab berkat kesimetriannya, setiap bolanya sama mungkin menjadi bola kedua yang ditarik, jadi tarikan kedua — tanpa disyaratkan — berhukum sama dengan yang pertama. Adapun menyaratkan pada hasil pertamanya mengubah peluangnya; sedangkan tak mengetahuinya tidak. Hujah keterpertukaran ini kembali pada bab berikutnya bagi pencuplikan tanpa pengembalian, tempat ia memberi rerata hipergeometrik $np$ tanpa satu kesamaan binomial pun.

Teorema 21.14 (Peluang majemuk, peluang total, Bayes)

(Aturan rantai) Bila $\P(A_1 \cap \dots \cap A_{n-1}) > 0$ , maka

$\P(A_1 \cap \dots \cap A_n) = \P(A_1)\,\P(A_2 \mid A_1)\cdots \P(A_n \mid A_1 \cap \dots \cap A_{n-1}) .$
(Peluang total) Bila $(B_i)_{i \in I}$ merupakan pemartisian $\Omega$ yang berhingga atau terbilang dengan $\P(B_i) > 0$ , maka untuk setiap kejadian $A$ :

$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$
(Bayes) Di bawah hipotesis yang sama, bila lebih jauh $\P(A) > 0$ :

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

Bukti. 1. Tulislah tiap peluang bersyaratnya sebagai hasil bagi: maka ruas kanannya adalah

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

yakni hasil kali yang berteleskop: sebab setiap penyebutnya mencoret pembilang sebelumnya, sehingga menyisakan $\P(A_1 \cap \dots \cap A_n)$ . Adapun semua penyebutnya $\geq \P(A_1 \cap \dots \cap A_{n-1}) > 0$ berkat kemonotonannya, jadi tak ada yang lenyap. (Dan hipotesisnya menjaga persis ini: sebab menyaratkan pada kejadian berpeluang nol tak terdefinisi.) 2. Himpunan $A \cap B_i$ saling lepas berpasangan dengan gabungan $A$ ; jadi terapkanlah keaditifan-( $\sigma$ )-nya beserta definisi penyaratannya. 3. Kedua ruas $\P(B_j \mid A)\P(A) = \P(A \mid B_j)\P(B_j)$ sama dengan $\P(A \cap B_j)$ ; jadi bagilah dengan $\P(A)$ lalu uraikan $\P(A)$ lewat peluang totalnya. ∎

Contoh 21.15 (Tabrakan ulang tahun, lewat aturan rantai)

Dengan $n$ orang yang ulang tahunnya saling bebas dan seragam atas $365$ hari, misalkan $D_n = {}$ “semua $n$ ulang tahunnya berbeda”. Lalu dengan menyaratkan orang demi orang (yakni aturan rantai):

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

sebab tiap orang baru harus menghindari $k$ hari yang sudah terpakai. Untuk $n = 23$ : berlaku $\P(D_{23}) \approx 0.493$ — jadi ulang tahun yang sama sudah lebih mungkin daripada tidak. Adapun heuristik yang menjelaskan kekecilan $23$ : dengan mengambil logaritmanya, $-\ln \P(D_n) \approx \sum_{k<n}\frac k{365} = \frac{\binom n2}{365}$ , lalu $\binom{23}2 = 253$ memberi $253/365 \approx 0.693 \approx \ln 2$ . Jadi yang berperan adalah banyaknya pasangan, yang tumbuh kuadratik: sehingga masalah tabrakan hidup pada skala $n \sim \sqrt{365}$ , bukan $n \sim 365$ — jadi paradoks ulang tahun adalah akar kuadrat yang menyamar.

Contoh 21.16 (Monty Hall, lewat Bayes)

Sebuah hadiah bersembunyi di balik satu dari tiga pintu, secara seragam. Kamu memilih pintu $1$ ; lalu pembawa acara, yang tahu tempat hadiahnya, membuka salah satu pintu lainnya yang selalu kosong (dengan memilih seragam ketika ia punya pilihan), katakanlah pintu $3$ . Misalkan $B_i = {}$ “hadiahnya di balik pintu $i$ ” dan $A = {}$ “pembawa acara membuka pintu $3$ ”. Maka $\pcond{B_1}{A} = \frac12$ , $\pcond{B_2}{A} = 1$ , dan $\pcond{B_3}{A} = 0$ , jadi menurut Bayes (Teorema 21.14),

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

jadi berpindah pintu menang dua kali dari tiga. Adapun perhitungannya menemukan kekeliruan populernya dengan tepat: sebab langkah pembawa acaranya bersifat informatif (karena ia tak dapat membuka pintu $2$ bila hadiahnya ada di sana), dan rumus Bayes adalah alat tata buku yang mengubah ketaksetangkupan ini menjadi $\frac23$ . Jadi menyaratkan pada “apa yang terlihat” alih-alih pada “apa yang benar” adalah seluruh seni rumusnya.

Contoh 21.17 (Dua taruhan Chevalier de Méré)

Dua taruhan abad ketujuh belas, yang diselesaikan lewat kebebasan. Taruhan pertama: sekurangnya satu enam dalam $4$ lemparan sebuah dadu,

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

Taruhan kedua: sekurangnya satu enam ganda dalam $24$ lemparan dengan dua dadu,

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

De Méré menalar bahwa $24$ lemparan berpeluang $\frac1{36}$ sepatutnya menyamai $4$ lemparan berpeluang $\frac16$ (sebab nisbahnya sama $\frac{24}{36} = \frac46$ ); dan kegagalan kesebandingan ini — karena peluang gabungan tak menskala secara linear — konon mendorong suratnya kepada Pascal, sehingga melahirkan teori peluang. Adapun pembandingan yang benar lewat logaritma: sebab $n$ percobaan berpeluang $p$ berhasil sekurangnya sekali dengan peluang $1 - (1-p)^n \approx 1 - \eu^{-np}$ , jadi invarian yang jujurnya adalah $np$ : di sini $4\cdot\frac16 = \frac23$ lawan $24\cdot\frac1{36} = \frac23$ — jadi sama! Sehingga kedua taruhannya hanya berselisih pada orde kedua dalam $p$ , dan cukup untuk memindahkan satu di antaranya menyeberangi garis lima puluh persen: jadi peluang kecil adalah ranah tempat gerak hati memerlukan eksponensial, bukan penggaris.

Catatan 21.18 (Kekeliruan yang sering muncul pada penyaratan)

Ada tiga kerancuan yang berulang, yang semuanya terlihat pada contoh di atas. (i) Pembalikan: sebab $\pcond BA$ dan $\pcond AB$ berselisih faktor $\P(A)/\P(B)$ — jadi sebuah uji yang $99\%$ akurat pada yang sakit masih boleh menyisakan pasien yang positif hampir pasti sehat ketika penyakitnya langka (Latihan 21.3); sehingga mengutip $\pcond{\text{sakit}}{ \text{positif}}$ ketika yang dimaksud $\pcond{\text{positif}}{ \text{sakit}}$ adalah kekeliruan laju-dasarnya. (ii) Menyaratkan pada kejadian yang keliru: sebab pada Monty Hall, kejadian penyaratan yang benar adalah “pembawa acara membuka pintu $3$ ”, bukan “hadiahnya tak di balik pintu $3$ ”; karena keduanya mengusung informasi yang berbeda, dan seluruh $\frac23$ -nya bergantung pada selisih itu. (iii) Saling lepas lawan saling bebas: sebab kejadian yang saling lepas dan berpeluang positif tak pernah saling bebas ( $\P(A\cap B) = 0 \neq \P(A)\P(B)$ ) — jadi kebebasan adalah keserasian informasi, bukan ketiadaan tumpang tindih.

Definisi 21.19 (Kebebasan)

Kejadian $A$ dan $B$ disebut saling bebas bila $\P(A \cap B) = \P(A)\P(B)$ . Adapun keluarga kejadian $(A_i)_{i \in I}$ disebut saling bebas (secara bersama) bila untuk setiap himpunan bagian berhingga $J \subseteq I$ ,

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

Catatan 21.20

Kebebasan bersama tegas lebih kuat daripada kebebasan berpasangan: sebab dengan dua lemparan koin setimbang, kejadian “yang pertama gambar”, “yang kedua gambar”, dan “keduanya sepakat” saling bebas berpasangan (sebab tiap pasangannya beririsan dengan peluang $\frac14 = \frac12\cdot\frac12$ ), namun irisan bertiganya berpeluang $\frac14 \neq \frac18$ . Perhatikan pula bahwa bila $A, B$ saling bebas, maka $A, B^c$ juga (hitunglah: $\P(A \cap B^c) = \P(A) - \P(A\cap B) = \P(A)(1 - \P(B))$ ), sehingga $A^c, B^c$ juga.

Contoh 21.21 (Kebebasan yang terbaca dari struktur hasil kali)

Lemparkan dua dadu setimbang: $\Omega = \intint16^2$ dengan bobot seragam. Misalkan $A = {}$ “dadu pertama genap” dan $B = {}$ “dadu kedua sekurangnya $5$ ”. Setelah dicacah: $\abs A = 3\cdot6 = 18$ , $\abs B = 6\cdot2 = 12$ , $\abs{A\cap B} = 3\cdot2 = 6$ , jadi

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

jadi saling bebas, dan mekanismenya kasatmata — sebab $A$ mengendalai koordinat pertamanya saja, $B$ koordinat keduanya saja, dan ukuran seragam pada himpunan hasil kali membuat cacah koordinatnya mengalikan. Jadi setiap klaim bertipe “kejadian yang bergantung pada kelompok lemparan yang saling lepas bersifat saling bebas” (yang dipakai besar-besaran pada soal akhir pekan) adalah perhitungan ini, dengan indeks yang lebih banyak.

Contoh 21.22 (Analisis langkah pertama)

Untuk model geometri pada Contoh 21.5, berapa peluang $u$ bahwa gambar pertamanya jatuh pada pangkat yang genap? Syaratkanlah pada lemparan pertamanya: dengan peluang $p$ pangkatnya $1$ (yang ganjil); sedangkan dengan peluang $q = 1 - p$ permainannya bermula ulang dengan semua paritasnya terbalik, jadi

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

Jadi satu baris, tanpa deret — dan ia sepakat dengan penjumlahan langsung pada Latihan 21.9, yang memberi $1 - u = \frac1{1+q}$ . Adapun teknik “langkah pertama” ini (yakni menyaratkan pada percobaan pertamanya lalu mengenali salinan masalahnya yang tergeser) adalah bentuk peluang bagi sebuah rekursi, dan ia mesin di balik persamaan lama permainan pada Latihan 21.6 beserta perhitungan singgahan pertama pada soal akhir pekan.

21.3 Lema Borel–Cantelli

Definisi 21.23 (Limit superior kejadian)

Untuk sebuah barisan kejadian $(A_n)$ , kejadian

\limsup_n A_n = \bigcap_{N=0}^{\infty}\ \bigcup_{n \geq N} A_n = \{\omega \in \Omega : \omega \in A_n \text{untuk tak berhingga banyak } n\}

adalah kejadian “ $A_n$ terjadi tak berhingga sering”.

Contoh 21.24 (Menerjemahkan “tak berhingga sering” dan “akhirnya”)

Komplemen $\limsup_nA_n$ adalah, menurut de Morgan,

\Bigl(\bigcap_N\bigcup_{n\geq N}A_n\Bigr)^{\!c} = \bigcup_N\bigcap_{n\geq N}A_n^c = \{\omega : \omega \notin A_n \text{ untuk setiap } n \text{ yang besar}\},

yakni kejadian “akhirnya, $A_n$ gagal” (yang ditulis $\liminf_nA_n^c$ ). Jadi “ $A_n$ tak berhingga sering” dan “ $A_n^c$ akhirnya” saling berkomplemen — dan menjaga kamus ini tetap lurus mencegah sebagian besar kecelakaan kuantor. Beberapa terjemahan contoh bagi pelemparan koin: “gambar yang tak berhingga banyaknya” adalah $\limsup\{X_n = H\}$ ; “hanya berhingga banyak deretan $100$ gambar” adalah komplemen sebuah limsup; dan “frekuensi berjalannya konvergen ke $\frac12$ ” adalah $\bigcap_j\bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - \tfrac12} < \tfrac1j\}$ — jadi operasi terbilang di seluruhnya, sehingga semuanya kejadian yang jujur.

Teorema 21.25 (Borel–Cantelli)

Bila $\sum_{n} \P(A_n) < \infty$ , maka $\P\bigl(\limsup_n A_n\bigr) = 0$ .
Bila kejadian $A_n$ saling bebas dan $\sum_n \P(A_n) = \infty$ , maka $\P\bigl(\limsup_n A_n\bigr) = 1$ .

Bukti. 1. Misalkan $C_N = \bigcup_{n \geq N}A_n$ ; maka barisan $(C_N)$ turun dengan irisan $\limsup A_n$ , jadi menurut kesubaditifan terbilangnya (Akibat 21.7)

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

(yakni ekor sebuah deret yang konvergen). Lalu kekontinuan monoton (Teorema 21.6) merampungkannya: $\P(\limsup A_n) = \lim_N \P(C_N) = 0$ .

2. Cukuplah menunjukkan $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ untuk setiap $N$ : sebab bila kejadian $B_N$ semuanya berpeluang $1$ , maka

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

menurut kesubaditifan terbilangnya (Akibat 21.7), jadi irisan terbilang $\limsup A_n = \bigcap_N\bigcup_{n\geq N}A_n$ tetap berpeluang $1$ . Tetapkan $N$ , lalu tinjaulah untuk $M > N$ komplemennya:

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

dengan memakai kebebasan komplemennya beserta batas kecembungan $1 - x \leq e^{-x}$ . Lalu ketika $M \to \infty$ eksponennya menuju $-\infty$ berkat kedivergenan deretnya, jadi menurut kekontinuan monoton (bagi barisan yang turun) $\P\bigl(\bigcap_{n \geq N}A_n^c\bigr) = 0$ , yakni $\P\bigl(\bigcup_{n \geq N}A_n\bigr) = 1$ . ∎

Contoh 21.26 (Deretan gambar yang tak berhingga)

Lemparkan koin setimbang selamanya, lalu misalkan $A_n$ kejadian “lemparan $n, n+1, \dots, n + k - 1$ semuanya gambar” (yakni deretan $k$ gambar yang bermula pada waktu $n$ ), untuk $k$ yang tetap. Maka kejadian $A_{jk}$ (dengan $j = 1, 2, \dots$ ), yang bergantung pada blok lemparan yang saling lepas, bersifat saling bebas, masing-masing berpeluang $2^{-k}$ , dan $\sum_j 2^{-k} = \infty$ : jadi menurut Borel–Cantelli 2, dengan peluang $1$ tak berhingga banyak bloknya seluruhnya gambar — sehingga setiap pola yang tetap berulang tak berhingga sering, secara hampir pasti. Sebaliknya, bila panjang deretannya kita biarkan tumbuh, $B_n = {}$ “sebuah deretan $2\log_2 n$ gambar bermula di $n$ ” punya $\P(B_n) = n^{-2}$ yang terjumlahkan, jadi hampir pasti hanya berhingga banyak deretan panjang semacam itu bermula: sehingga Borel–Cantelli menakar persis seberapa panjang deretan terpanjangnya.

Contoh 21.27 (Monyet tak hingga, dikuantifikasi)

Seekor monyet mengetik huruf seragam yang saling bebas dari abjad berhuruf $26$ . Potonglah ketikannya menjadi blok lepas berisi empat huruf; maka kejadian $A_j = {}$ “blok $j$ mengeja MATH” saling bebas dengan $\P(A_j) = 26^{-4}$ , dan $\sum_j\P(A_j) = \infty$ : jadi menurut Borel–Cantelli 2 monyetnya mengetik MATH tak berhingga sering, secara hampir pasti — dan hal yang sama berlaku bagi sembarang teks tetap sepanjang apa pun, dengan bloknya disesuaikan. Adapun catatan kuantitatifnya mengempiskan keajaibannya: sebab $26^4 = 456\,976$ , jadi MATH pertamanya menuntut sekitar setengah juta ketukan tuts secara rata-rata, dan sebuah lakon Shakespeare berisi $10^5$ karakter menunggu berorde $26^{10^5}$ blok — jadi hampir pasti adalah pernyataan tentang cakrawala $\infty$ , bukan tentang cakrawala mana pun yang akan ditemui seekor monyet. Jadi Borel–Cantelli mengesahkan limitnya; sedangkan ukuran sukunya yang menceritakan pada skala manusia.

Catatan 21.28

Pada Contoh 21.26 ruang sampel yang mendasarinya (yakni barisan lemparan yang tak hingga) bersifat tak terbilang, jadi secara ketat contohnya hidup pada kerangka teori ukuran Tahun ke-3; namun perhitungannya hanya memakai aturan yang dibuktikan pada bab ini, yang diterapkan pada kejadian yang ditentukan berhingga banyak lemparan dan kombinasi terbilangnya. Inilah konvensi baku pada tingkat ini: teorinya dinyatakan pada ruang terbilang, sedangkan contoh permainan tak hingga ditangani dengan perkakas yang sama.

Catatan 21.29 (Pandangan ke depan di dalam jilid ini)

Perkakas bab ini dikonsumsi borongan oleh kedua bab berikutnya. Indikator mengubah kejadian menjadi peubah acak, dan keaditifan- $\sigma$ menjadi keterjumlahan yang mendefinisikan nilai harapan (Bab 22); sedangkan Borel–Cantelli ditambah batas ekor yang terjumlahkan persis merupakan cara hukum bilangan besar yang kuat bagi koin dibuktikan di sana. Adapun pada Bab 23, kekontinuan monotonnya muncul kembali pada saat yang menentukan: sebab peluang kepunahan sebuah proses bercabang didefinisikan sebagai limit monoton $\lim\P(Z_n = 0)$ , dan persamaan titik tetap yang dipenuhinya diperoleh dengan melewatkan limit pada barisan naik itu — jadi teorema terakhir buku ini berdiri di atas teorema pertama bab ini.

Catatan 21.30 (Metode: tiga jalan menuju peluang satu)

Pernyataan hampir pasti dibuktikan lewat tiga tuas, yakni dalam urutan kekuatan yang menaik. Kekontinuan monoton: pamerkanlah kejadiannya sebagai gabungan yang naik (atau irisan yang turun) atas kejadian bercakrawala berhingga yang peluangnya terhitung (Contoh 21.9). Gabungan nol: sebab gabungan terbilang atas kejadian berpeluang nol bernilai nol (berkat kesubaditifan terbilangnya), jadi cukuplah membunuh tiap kejadian buruknya secara terpisah — dan begitulah “untuk setiap $j$ , akhirnya $\abs{\widehat p_n - p} < 1/j$ ” terangkai menjadi kekonvergenan. Borel–Cantelli: ketika kejadiannya berupa limsup, jumlahkanlah peluangnya; sebab kekonvergenannya membunuhnya (tanpa perlu kebebasan), sedangkan kedivergenan ditambah kebebasan mengesahkannya. Jadi memilih tuas yang tepat biasanya seluruh buktinya; dan soal akhir pekan menjalankan ketiganya dalam satu hujah.

Catatan 21.31 (Di mana ini dipakai)

Kekontinuan monoton dan Borel–Cantelli adalah dua tuas bagi setiap pernyataan “hampir pasti”: sebab keduanya menggerakkan kerekurenan jalan acak pada soal akhir pekan bab ini, sisi hampir pasti hukum bilangan besar (Bab 22), dan analisis kepunahan proses bercabang (Bab 23). Adapun jilid Tahun ke-3 membangun ulang teorinya atas aljabar- $\sigma$ dan pengintegralan Lebesgue, tempat ruang sampel tak terbilang yang dipakai secara tak resmi di sini menjadi sepenuhnya ketat.

21.4 Latihan

Latihan 21.1 ★

Sebuah guci berisi $n$ bola bernomor. Bolanya ditarik satu demi satu tanpa pengembalian. Hitunglah peluang bahwa bola bernomor $1$ tertarik sebelum bola bernomor $2$ . Samaratakan: yakni peluang bahwa bola $1$ tertarik pertama di antara bola $1, \dots, k$ .

Solusi

Solusi Latihan 21.1.

Berkat kesimetriannya: urutan penarikannya mengimbaskan urutan relatif yang acak seragam pada bola $1$ dan $2$ , jadi $\P(1 \text{ sebelum } 2) = \frac12$ . Secara formal: mempertukarkan kedudukan bola $1$ dan $2$ pada sebuah barisan penarikan merupakan bijeksi atas hasil (yang berpeluang sama) yang menukar kejadiannya dengan komplemennya. Adapun di antara bola $1, \dots, k$ : urutan relatif $k$ bolanya seragam di antara $k!$ urutannya, dan bola $1$ menjadi yang pertama pada $(k-1)!$ di antaranya: jadi peluangnya $\frac{(k-1)!}{k!} = \frac1k$ .

Latihan 21.2 ★

Tunjukkan bahwa pada $\Omega = \N^*$ bobot $p_k = \frac{1}{k(k+1)}$ mendefinisikan sebuah ukuran peluang, lalu hitunglah $\P(2\N^*)$ (yakni hasil yang genap) sebagai sebuah deret; kemudian tunjukkan bahwa ia sama dengan $1 - \ln 2$ . (Teleskopkan $\frac{1}{2j(2j+1)} = \frac{1}{2j} - \frac{1}{2j+1}$ lalu pakailah deret harmonik yang berselang-seling, Bab 7.)

Solusi

Solusi Latihan 21.2.

Berlaku $\frac{1}{k(k+1)} = \frac1k - \frac1{k+1}$ , jadi $\sum_{k\geq1} p_k$ berteleskop menjadi $1$ : sehingga sebuah ukuran peluang. Adapun hasil yang genap:

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

Ini adalah deret harmonik berselang-seling dengan suku pertamanya dibuang dan tandanya dibalik: jadi karena $\ln 2 = 1 - \frac12 + \frac13 - \frac14 + \cdots$ (Bab 7),

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

Latihan 21.3 ★

(Positif palsu) Sebuah penyakit menjangkiti satu orang dari $10\,000$ . Sebuah uji mendeteksinya dengan peluang $0.99$ pada yang sakit, dan memberi positif palsu dengan peluang $0.01$ pada yang sehat. Hitunglah peluang menjadi sakit jika diketahui ujinya positif, lalu berilah komentar.

Solusi

Solusi Latihan 21.3.

Misalkan $S$ = sakit dan $+$ = uji positif. Maka Bayes (Teorema 21.14) dengan pemartisian $\{S, S^c\}$ memberi

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

yakni di bawah $1\%$ . Jadi walaupun ujinya “akurat 99%”, sebuah hasil positif menyisakan kamu sekitar $99\%$ mungkin sehat: sebab positif palsu di antara mayoritas sehat yang sangat besar menenggelamkan positif benar dari minoritas sakit yang sangat kecil. Jadi uji penapisan bagi kondisi yang langka harus selalu dibaca lewat perhitungan laju-dasar ini.

Latihan 21.4 ★★

Misalkan $A_1, \dots, A_n$ kejadian. Buktikan rumus inklusi–eksklusi

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

dengan mengintegralkan kesamaan $1 - \prod_{i=1}^n(1 - \mathbf{1}_{A_i}) = \mathbf{1}_{\bigcup A_i}$ atas $\Omega$ (yakni menjumlahkannya terbobot oleh $\P(\{\omega\})$ ).

Solusi

Solusi Latihan 21.4.

Titik demi titik pada $\Omega$ : berlaku $\omega \in \bigcup A_i$ bila dan hanya bila suatu faktor $1 - \mathbf{1}_{A_i}(\omega)$ lenyap, jadi

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

setelah hasil kalinya diuraikan lalu $1$ -nya dipindahkan. Kini $\prod_{i\in J}\mathbf{1}_{A_i} = \mathbf{1}_{\bigcap_{i \in J} A_i}$ , jadi menjumlahkannya terhadap bobot $\P(\{\omega\})$ — yang sah: sebab berhingga banyak suku yang terbatas, dan tiap keluarganya terjumlahkan — mengubah tiap indikatornya menjadi peluang kejadiannya, sehingga memberi rumusnya.

Latihan 21.5 ★★

(Masalah pencocokan, lewat inklusi–eksklusi) Sebanyak $n$ surat dimasukkan secara acak seragam ke $n$ amplop, satu per amplop. Dengan memakai Latihan 21.4, tunjukkanlah bahwa peluang tak ada kecocokan adalah $\sum_{k=0}^n \frac{(-1)^k}{k!} \to e^{-1}$ , lalu turunkan peluang tepat satu kecocokan.

Solusi

Solusi Latihan 21.5.

Misalkan $A_i$ = “surat $i$ berada di amplop yang benar”. Untuk $J$ berukuran $k$ berlaku $\P\bigl(\bigcap_{i\in J}A_i\bigr) = \frac{(n-k)!}{n!}$ (yakni tetapkan $k$ suratnya, lalu permutasikan sisanya). Jadi menurut inklusi–eksklusi,

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

jadi

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

Adapun tepat satu kecocokan: sebuah permutasi dengan tepat satu titik tetap ditentukan oleh pemilihan surat yang tetapnya (ada $n$ cara) dan sebuah permutasi kacau (yakni susunan tanpa kecocokan) atas $n - 1$ lainnya; jadi dengan menulis $D_{n-1} = (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}$ bagi banyaknya permutasi kacau (yakni bagian pertamanya, yang diskalakan $(n-1)!$ ),

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

pada limitnya, “tak ada kecocokan” dan “tepat satu kecocokan” sama mungkinnya, masing-masing berpeluang $e^{-1}$ .

Latihan 21.6 ★★

Sekeping koin yang berat sebelah (dengan peluang gambar $p \in \intoo{0}{1}$ ) dilempar sampai dua gambar berurutan muncul. Misalkan $q_n$ peluang bahwa permainannya berlangsung lebih dari $n$ lemparan. Tunjukkan, dengan menyaratkan pada lemparan pertamanya, bahwa $q_n = (1-p)\,q_{n-1} + p(1-p)\,q_{n-2}$ untuk $n \geq 2$ , lalu turunkan bahwa permainannya berakhir dengan peluang $1$ . (Tunjukkan $q_n \to 0$ dengan membandingkannya dengan barisan geometri: sebab kedua akar persamaan karakteristiknya bernilai mutlak di $\intoo{0}{1}$ .)

Solusi

Solusi Latihan 21.6.

Syaratkanlah pada awalnya (yakni aturan rantai / Teorema 21.14):

lemparan pertamanya A (berpeluang $1 - p$ ): permainannya bermula ulang; jadi berlangsung lebih dari $n$ berarti berlangsung lebih dari $n - 1$ dari sana: sehingga sumbangannya $(1-p)\,q_{n-1}$ ;
lemparan pertamanya GA (berpeluang $p(1-p)$ ): bermula ulang sesudah dua lemparan: sumbangannya $p(1-p)\,q_{n-2}$ ;
lemparan pertamanya GG: permainannya telah berakhir (dalam $n$ lemparan, dengan $n \geq 2$ ): jadi menyumbang $0$ .

Karena itu $q_n = (1-p)q_{n-1} + p(1-p)q_{n-2}$ . Adapun persamaan karakteristiknya $r^2 = (1-p)r + p(1-p)$ berakar

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

dengan $\abs{r_\pm} < 1$ : sebab memang polinomial $\chi(r) = r^2 - (1-p)r - p(1-p)$ memenuhi $\chi(1) = 1 - (1-p) - p(1-p) = p^2 > 0$ dan $\chi(-1) = 1 + (1-p) - p(1-p) > 0$ , sedangkan $\chi(0) = -p(1-p) < 0$ : jadi satu akar di $\intoo{-1}{0}$ dan satu di $\intoo{0}{1}$ . Jadi $q_n = \alpha r_+^n + \beta r_-^n \to 0$ . Adapun kejadian “permainannya berlangsung lebih dari $n$ ” turun ke “permainannya tak pernah berakhir”; jadi kekontinuan monoton (Teorema 21.6) memberi $\P(\text{tak pernah berakhir}) = \lim q_n = 0$ : sehingga permainannya berakhir hampir pasti.

Latihan 21.7 ★★★

(Rekor) Tariklah barisan tak hingga berisi peringkat seragam yang saling bebas, dalam pengertian kombinatorik berikut: yakni untuk tiap $n$ , urutan relatif $n$ tarikan pertamanya seragam di antara $n!$ kemungkinannya, dan $R_n = {}$ “tarikan ke- $n$ -nya sebuah rekor (yakni lebih besar daripada semua sebelumnya)”. Dengan menerima bahwa kejadian $R_n$ saling bebas dengan $\P(R_n) = 1/n$ (buktikanlah sekurangnya kesamaan terakhir ini lewat kesimetriannya), tunjukkanlah dengan memakai Borel–Cantelli bahwa tak berhingga banyak rekor terjadi secara hampir pasti, tetapi bahwa rekor pada waktu yang berurutan $n, n+1$ terjadi tak berhingga sering dengan peluang — hitunglah $\sum_n \P(R_n \cap R_{n+1})$ lalu simpulkanlah apa yang diberikan Borel–Cantelli 1.

Solusi

Solusi Latihan 21.7.

Bahwa $\P(R_n) = 1/n$ : di antara $n$ tarikan pertamanya, masing-masing $n$ kedudukan relatif tarikan terakhirnya sama mungkin (berkat keseragaman urutan relatifnya), dan $R_n$ adalah kejadian bahwa ia yang terbesar: jadi peluangnya $1/n$ .

Rekor tak berhingga banyaknya: berlaku $\sum_n \P(R_n) = \sum 1/n = \infty$ dan $R_n$ saling bebas (yang diterima saja), jadi Borel–Cantelli 2 (Teorema 21.25) memberi $\P(\limsup R_n) = 1$ : jadi rekornya tak pernah berhenti, secara hampir pasti — tetapi ia menipis secara logaritmik.

Rekor berurutan: berkat kebebasannya,

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

jadi Borel–Cantelli 1 berlaku: sehingga hampir pasti, hanya berhingga kali sebuah rekor langsung disusul rekor yang lain. Jadi kedua paruh lemanya bekerja bersama: yakni rekor tak berhingga banyaknya, tetapi (hampir pasti) akhirnya tak pernah dua berturut-turut.

Latihan 21.8 ★★★

(Bercita rasa Kochen–Stone, versi yang lebih mudah) Misalkan $(A_n)$ kejadian yang saling bebas dengan $\P(A_n) = \frac{1}{n+1}$ . Tunjukkan bahwa $\P(\limsup A_n) = 1$ , walaupun $\P(A_n) \to 0$ : yakni “langka secara individual, pasti secara kolektif”. Sebaliknya, pamerkanlah barisan kejadian (yang bergantungan) dengan $\sum\P(A_n) = \infty$ dan $\P(\limsup A_n) = 0$ , sehingga menunjukkan kebebasannya tak dapat dilepas pada Borel–Cantelli 2.

Solusi

Solusi Latihan 21.8.

Bagian pertamanya: berlaku $\sum \P(A_n) = \sum\frac{1}{n+1} = \infty$ dengan kebebasannya: jadi Borel–Cantelli 2 memberi $\P(\limsup A_n) = 1$ . Jadi tiap $A_n$ individualnya makin tak mungkin, namun hampir setiap $\omega$ termasuk tak berhingga banyak di antaranya.

Contoh tandingan tanpa kebebasan: ambillah $\Omega = \N^*$ dengan bobot $p_k = \frac{1}{k(k+1)}$ pada Latihan 21.2, dan $A_n = \{k \in \N^* : k \geq n\}$ . Maka

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

tetapi $A_n$ bersifat turun, jadi $\limsup_n A_n = \bigcap_n A_n = \emptyset$ : sehingga $\P(\limsup A_n) = 0$ . Jadi kedivergenan $\sum\P(A_n)$ sendirian tak menjamin apa pun ketika kejadiannya menumpuk pada bagian ruangnya yang menciut — dan kebebasanlah yang melarang persekongkolan itu.

Latihan 21.9 ★

Sekeping koin yang berpeluang gambar $p \in \intoo01$ dilempar sampai gambar pertamanya. Hitunglah peluang bahwa ini terjadi pada pangkat yang ganjil, lalu nilailah ia bagi koin yang setimbang.

Solusi

Solusi Latihan 21.9.

Dengan $q = 1 - p$ , gambar pertamanya jatuh pada pangkat $2j + 1$ dengan peluang $q^{2j}p$ , jadi

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

Untuk koin yang setimbang: berlaku $\frac1{1 + 1/2} = \frac23$ . (Pemeriksaan kewarasannya: pangkat ganjilnya sepatutnya lebih mungkin, karena pangkat $1$ datang lebih dulu — dan memang $\frac1{1+q} > \frac12$ selalu.)

Latihan 21.10 ★★

Misalkan $(A_n)_{n\geq1}$ kejadian saling bebas dengan $\P(A_n) = p_n < 1$ . Tunjukkan bahwa

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

dan bahwa limitnya $> 0$ bila dan hanya bila $\sum p_n < \infty$ . Lalu serasikanlah dengan Borel–Cantelli: bahwa ketika $\sum p_n = \infty$ , bukan hanya sebuah $A_n$ terjadi hampir pasti — melainkan tak berhingga banyak yang terjadi.

Solusi

Solusi Latihan 21.10.

Kejadian $B_N = \bigcap_{n=1}^N A_n^c$ turun ke $\bigcap_nA_n^c$ , dan berkat kebebasan komplemennya berlaku $\P(B_N) = \prod_{n=1}^N(1 - p_n)$ ; jadi kekontinuan monoton (Teorema 21.6) memberi limit pada displainya. Lalu dengan mengambil logaritmanya, $\prod(1 - p_n) > 0$ bila dan hanya bila $\sum-\ln(1 - p_n) < \infty$ . Bila $\sum p_n < \infty$ maka $p_n \to 0$ dan $-\ln(1 - p_n) \sim p_n$ : jadi deret lognya konvergen. Sedangkan bila $\sum p_n = \infty$ , maka $-\ln(1 - p_n) \geq p_n$ memaksa kedivergenannya, jadi hasil kalinya $0$ . Dan ini cocok dengan Borel–Cantelli 2: sebab untuk $\sum p_n = \infty$ , bukan hanya $\P(\text{tak ada }A_n\text{ yang terjadi}) = 0$ , melainkan hampir pasti tak berhingga banyak $A_n$ terjadi.

Latihan 21.11 ★★

(Kotak korek api Banach) Seorang perokok menyimpan satu kotak berisi $n$ batang korek di tiap sakunya lalu merogoh saku yang dipilih acak seragam setiap kalinya. Ketika ia pertama kali menemukan sebuah kotaknya kosong, berapa peluang bahwa kotak lainnya berisi tepat $k$ batang korek? Tunjukkan bahwa jawabannya $\binom{2n-k}{n}2^{-(2n-k)}$ lalu periksalah bahwa peluang itu berjumlah $1$ untuk $n = 1$ .

Solusi

Solusi Latihan 21.11.

Katakanlah kotak $A$ yang pertama ditemukan kosong, dengan kotak lainnya berisi $k$ . Ini berarti: di antara $2n - k$ rogohan pertamanya, tepat $n$ menuju $A$ dan $n - k$ menuju $B$ (dalam suatu urutan), lalu rogohan ke- $2n - k + 1$ menuju $A$ lagi dan menemukannya kosong. Adapun rogohannya berupa pilihan setimbang yang saling bebas, jadi kejadian ini berpeluang $\binom{2n-k}{n}2^{-(2n-k)}\cdot\frac12$ ; lalu melipatduakannya (sebab kotak kosongnya boleh yang mana saja) memberi

\P(\text{kotak lainnya berisi }k) = \binom{2n-k}{n}\,2^{-(2n-k)} .

Untuk $n = 1$ : $k = 1$ memberi $\binom11 2^{-1} = \frac12$ dan $k = 0$ memberi $\binom21 2^{-2} = \frac12$ : jadi totalnya $1$ , sebagaimana mestinya.

Latihan 21.12 ★★★

(Keaditifan- $\sigma$ itu aksioma yang sejati) (a) Tunjukkan bahwa tak ada ukuran peluang pada $(\N, \mathcal P(\N))$ yang memberi semua singletonnya bobot yang sama. (b) Untuk $A \subseteq \N^*$ , misalkan $d(A) = \lim_n\frac{\abs{A\cap\intint1n}}{n}$ ketika limitnya ada (yakni kerapatan alaminya). Tunjukkan bahwa $d$ bersifat aditif berhingga pada pasangan yang ketiga kerapatannya ada, memberi setiap singleton kerapatan $0$ dan $\N^*$ kerapatan $1$ — lalu simpulkan bahwa $d$ tak bersifat aditif- $\sigma$ . (c) Pamerkanlah sebuah himpunan yang tak berkerapatan. (Selang-selingkan blok $\intint{2^{2k}}{2^{2k+1}-1}$ masuk dan keluar.)

Solusi

Solusi Latihan 21.12.

(a) Bila $\P(\{n\}) = c$ untuk setiap $n$ , maka keaditifan- $\sigma$ memaksa $1 = \sum_nc$ : yang mustahil, entah $c = 0$ (sebab jumlahnya $0$ ) atau $c > 0$ (sebab jumlahnya tak hingga). Jadi tak ada peluang seragam pada $\N$ .

(b) Bila $A \cap B = \emptyset$ dan $d(A)$ serta $d(B)$ ada, maka $\abs{(A \sqcup B)\cap\intint1n} = \abs{A\cap\intint1n} + \abs{B\cap\intint1n}$ , jadi $d(A \sqcup B) = d(A) + d(B)$ : yakni keaditifan berhingga pada pasangan semacam itu. Adapun tiap singletonnya punya fungsi pencacah yang akhirnya tetap, jadi berkerapatan $0$ , sedangkan $d(\N^*) = 1$ . Seandainya $d$ bersifat aditif- $\sigma$ , maka $\N^* = \bigsqcup_k\{k\}$ akan memberi $1 = \sum_k 0 = 0$ : jadi kerapatannya aditif berhingga tetapi tak aditif- $\sigma$ — sehingga aksiomanya punya isi.

(c) Misalkan $A = \bigcup_{k\geq0}\intint{4^k}{2\cdot4^k - 1}$ (yakni blok dari $4^k$ sampai $2\cdot4^k - 1$ ). Di $n = 2\cdot4^K - 1$ cacahnya $\sum_{k\leq K}4^k \sim \frac43 4^K$ , sehingga memberi nisbah $\to \frac23$ ; sedangkan di $n = 4^{K+1} - 1$ cacahnya tak berubah, sehingga memberi nisbah $\to \frac13$ . Jadi nisbahnya berayun antara limit $\frac13$ dan $\frac23$ : sehingga tak berkerapatan.

21.5 Soal: jalan acak sederhana pada $\Z$ bersifat rekuren

Dua puluh empat langkah sebuah jalan acak sederhana; adapun titik merahnya menandai kepulangan ke titik asalnya. Soal ini menunjukkan bahwa, dengan peluang 1, titik itu tak pernah berhenti muncul — namun waktu tunggu di antaranya bererata divergen. — Dua puluh empat langkah sebuah jalan acak sederhana; adapun titik merahnya menandai kepulangan ke titik asalnya. Soal ini menunjukkan bahwa, dengan peluang $1$ , titik itu tak pernah berhenti muncul — namun waktu tunggu di antaranya bererata divergen.

Soal 21.1

Soal akhir pekan — teorema kerekurenan Pólya pada $\Z$ , dengan masalah pemungutan suara dan cita rasa arcsinus di sepanjang jalan

Lemparkan koin setimbang selamanya; misalkan $X_i = \pm1$ langkah ke- $i$ -nya dan $S_n = X_1 + \dots + X_n$ jalan acak sederhana pada $\Z$ , dengan $S_0 = 0$ . Seperti pada Contoh 21.26, semua kejadian di bawah ditentukan oleh berhingga banyak lemparan atau berupa kombinasi terbilang kejadian semacam itu, dan kebebasan kejadian yang bergantung pada blok lemparan yang saling lepas merupakan bagian modelnya. Kita menulis $u_n = \P(S_{2n} = 0)$ dan $N_n(k)$ bagi banyaknya lintasan- $\pm1$ berpanjang $n$ dari $0$ ke $k$ .

Bagian I — Mencacah lintasan.

Tunjukkan bahwa $N_n(k) = \binom{n}{(n+k)/2}$ ketika $n + k$ genap dan $\abs k \leq n$ , dan $0$ selain itu; lalu turunkan $\P(S_n = k) = N_n(k)\,2^{-n}$ . Mengapa setiap lintasan individual berpanjang $n$ sama mungkinnya?
Tunjukkan $S_{2n+1} \neq 0$ dan $u_n = \binom{2n}{n}4^{-n}$ , lalu hitunglah $u_1, u_2, u_3$ .
Buktikan $u_n = \frac{2n-1}{2n}\,u_{n-1}$ ; lalu turunkan bahwa $(u_n)$ turun ke $0$ , dan dari Contoh 6.14 bahwa

$u_n \sim \frac{1}{\sqrt{\pi n}}, \qquad\text{jadi}\qquad \sum_n u_n = \infty .$
(Asas pemantulan) Untuk $k \geq 1$ , tunjukkan bahwa lintasan berpanjang $n$ dari $1$ ke $k$ yang menyentuh $0$ berkorespondensi bijektif dengan lintasan dari $-1$ ke $k$ ; lalu turunkan bahwa banyaknya lintasan dari $0$ ke $k$ yang tinggal $> 0$ sesudah waktu $0$ adalah $N_{n-1}(k-1) - N_{n-1}(k+1)$ .
(Teorema pemungutan suara) Turunkan bahwa

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

jadi pada sebuah penghitungan tempat pemenangnya unggul $k$ dari $n$ surat suara, peluang bahwa pemenangnya unggul sepanjang penghitungannya adalah $k/n$ . Periksalah dengan tangan untuk $n = 3$ dan $k = 1$ .

Bagian II — Kepulangan ke titik asal.

Buktikan kesamaan kuncinya

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

(syaratkan pada langkah pertamanya, jumlahkan cacah pada pertanyaan 4 atas titik ujungnya, lalu teleskopkan; kemudian rampungkan dengan $2\binom{2n-1}{n} = \binom{2n}{n}$ ).
Turunkan dari kekontinuan monoton (Teorema 21.6) bahwa jalannya pulang ke $0$ sekurangnya sekali dengan peluang $1$ , dan bahwa $f_n := \P(\text{kepulangan pertama pada waktu }2n)$ memenuhi

$f_n = u_{n-1} - u_n = \frac{u_n}{2n-1}, \qquad \sum_{n\geq1}f_n = 1 .$
Tunjukkan bahwa $\sum_n 2n\,f_n = \infty$ : jadi kepulangannya pasti, tetapi deret yang akan menghitung waktu tunggu reratanya divergen (dalam kosakata Bab 22, waktu kepulangannya bernilai harapan tak hingga).
Buktikan bahwa untuk setiap $k \geq 1$ berlaku $\P(\text{sekurangnya } k\text{ kepulangan ke }0) = 1$ (uraikanlah atas waktu $k$ kepulangan pertamanya: sebab blok lemparan yang bersesuaian saling lepas, jadi peluangnya mengalikan lalu berjumlah $(\sum_nf_n)^k$ ); lalu simpulkan dengan kekontinuan monoton:

$\P(S_n = 0 \text{ untuk tak berhingga banyak } n) = 1 :$

jadi jalan acak sederhana pada $\Z$ bersifat rekuren.
Tunjukkan bahwa jalannya mengunjungi setiap tapak $k \in \Z$ secara hampir pasti, sehingga (berkat kerekurenannya, yang dimulai ulang di kunjungan pertamanya) tak berhingga sering. (Sebab tanda ekskursi berurutan dari $0$ merupakan koin setimbang yang saling bebas; dan sebuah ekskursi positif mengunjungi $1$ .)

Bagian III — Borel–Cantelli dan jalan yang berat sebelah.

Kejadian $A_n = \{S_{2n} = 0\}$ memenuhi $\sum\P(A_n) = \infty$ ; jelaskanlah mengapa Borel–Cantelli 2 tak berlaku padanya, dan apa yang akan diberikan Borel–Cantelli 1 seandainya deretnya konvergen. (Inilah strategi seluruh Bagiannya.)
Kini biarkanlah koinnya berat sebelah dengan $p \neq \frac12$ dan $q = 1 - p$ . Tunjukkan $\P(S_{2n} = 0) = \binom{2n}n(pq)^n = u_n\,(4pq)^n$ dengan $4pq < 1$ , lalu turunkan $\sum_n\P(S_{2n} = 0) < \infty$ , kemudian simpulkan lewat Borel–Cantelli 1 bahwa jalan berat sebelahnya pulang ke $0$ hanya berhingga kali, secara hampir pasti.
Masih untuk $p \neq \frac12$ : tunjukkan $\P(S_n = k) \leq \binom{n}{\floor{n/2}}\,(pq)^{n/2}\,(p/q)^{k/2}$ untuk tiap $k$ yang tetap, lalu turunkan bahwa setiap tapaknya dikunjungi berhingga kali secara hampir pasti, kemudian simpulkan $\abs{S_n} \to \infty$ secara hampir pasti: jadi jalan berat sebelahnya bersifat transien.
Kembali ke koin setimbangnya: dengan memakai pertanyaan 6, hitunglah peluang bahwa $200$ lemparan menghasilkan tak ada seri (yakni $S_n \neq 0$ untuk $1 \leq n \leq 200$ ), yang secara numerik $u_{100} \approx 0.056$ . Berilah komentar tentang peluruhan $1/\sqrt{\pi n}$ yang lambat: bahwa seri itu pasti dalam jangka panjang tetapi lebih langka daripada dugaan gerak hati.
(Singgahan pertama) Misalkan $T_1$ waktu pertama jalannya mengenai $1$ . Dengan memakai asas pemantulan bagi maksimumnya $M_n = \max_{i\leq n}S_i$ (yang dibuktikan pada pertanyaan 16, yang tak bergantung pada pertanyaan ini), atau langsung dari pertanyaan 7 dengan menyaratkan pada langkah pertamanya, tunjukkanlah $\P(T_1 = 2n - 1) = f_n$ ; lalu turunkan $\P(T_1 < \infty) = 1$ sedangkan deret waktu reratanya $\sum(2n-1)f_n$ divergen.

Bagian IV — Maksimum, nol terakhir, unggul panjang.

(Pemantulan bagi maksimumnya) Untuk $k \geq 1$ , buktikanlah

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

dengan memantulkan lintasannya sesudah kunjungan pertamanya ke aras $k$ .
Turunkan $\P(M_{2n} \geq 1) = 1 - u_n$ , yakni $\P(S_i \leq 0 \text{ untuk setiap } i \leq 2n) = u_n$ : jadi peluang tak pernah unggul sama dengan peluang tak pernah berada di nol (pertanyaan 6) — yakni dua kejadian yang berbeda, satu peluang.
(Nol terakhir) Misalkan $L_{2n} = \max\{k \leq 2n : S_k = 0\}$ (yang genap). Dengan menggabungkan pertanyaan 6 dan kebebasan blok lemparan yang saling lepas, tunjukkanlah

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

lalu turunkan, tanpa perhitungan lebih lanjut, kesamaan binomial $\sum_{k=0}^n u_ku_{n-k} = 1$ .
Tunjukkan bahwa hukum $L_{2n}$ bersifat setangkup (yakni $\P(L = 2k) = \P(L = 2n - 2k)$ ) dan, dengan memakai $u_j \sim 1/\sqrt{\pi j}$ , bahwa ekstremnya merupakan nilainya yang paling mungkin. Tabelkanlah untuk $n = 5$ : $\P(L_{10} = 0) = u_5 \approx 0.246$ lawan $\P(L_{10} = 4) = u_2u_3 \approx 0.117$ . Tafsirkanlah: bahwa pada permainan setimbang yang panjang, seri terakhirnya cenderung sangat awal atau sangat lambat — jadi keunggulan yang panjang adalah aturannya, bukan kekecualiannya.
Rangkailah pertanyaan 16–19 menjadi sebuah paragraf tentang gambaran fluktuasi jalan setimbangnya: yakni skala difusif yang disarankan pertanyaan 3, kepastian kepulangannya lawan waktu tunggu reratanya yang divergen, dan keawetan keunggulannya yang bercita rasa arcsinus.

Bagian V — Kesamaan pembaruan dan teorema Pólya.

Buktikan, dengan memartisi $\{S_{2n} = 0\}$ atas waktu kepulangan pertamanya, kesamaan pembaruannya

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

dengan $U(x) = \sum_{n\geq0}u_nx^n$ dan $F(x) = \sum_{n\geq1}f_nx^n$ (lalu benarkanlah jari-jarinya beserta hasil kali deretnya lewat Bab 11).
Turunkan dikotomi kerekurenannya: yakni dengan melewatkan $x \to 1^-$ (lewat limit monoton deret berkoefisien taknegatif),

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

lalu periksalah ia terhadap pertanyaan 3, 7 (jalan setimbangnya) dan 12 (jalan berat sebelahnya).
(Dimensi $2$ ) Jalan sederhana pada $\Z^2$ melangkah $(\pm1, 0)$ dan $(0, \pm1)$ secara seragam. Tunjukkan bahwa koordinat terputarnya $U_n = X_n + Y_n$ dan $V_n = X_n - Y_n$ menjalankan jalan setimbang yang saling bebas pada $\Z$ , lalu turunkan

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

kemudian simpulkan dengan pertanyaan 21–22 (yang buktinya berpindah kata demi kata) bahwa jalannya pada $\Z^2$ bersifat rekuren.
(Dimensi $3$ ) Untuk jalan sederhana pada $\Z^3$ , terimalah taksiran lokalnya $\P(S^{(3)}_{2n} = 0) \leq C\,n^{-3/2}$ (yang dibuktikan lewat teorema limit lokal pada jilid Tahun ke-3). Turunkan dari Borel–Cantelli 1 bahwa jalannya pada $\Z^3$ bersifat transien, lalu nyatakanlah hasil penuhnya: yakni teorema Pólya — bahwa jalan acak sederhana bersifat rekuren pada dimensi $1$ dan $2$ , dan transien pada dimensi $3$ ke atas.
Rangkuman. Daftarkanlah peran persis yang dimainkan: pencacahan lintasan dan pemantulan; kekontinuan monoton; kebebasan blok lemparan yang saling lepas; Borel–Cantelli 1; dan kesamaan pembaruannya. Lalu fakta analitis tunggal mana ( $u_n \sim 1/\sqrt{\pi n}$ , sehingga $\sum u_n = \infty$ tetapi $\sum u_n^2 = \infty$ dan $\sum n^{-3/2} < \infty$ ) yang memutuskan antara kerekurenan dan ketransienan pada tiap dimensinya?

Solusi

Solusi Soal 21.1.

1. Sebuah lintasan berpanjang $n$ ditentukan oleh himpunan langkah naiknya; dan berakhir di $k$ berarti ada $u$ langkah naik dan $n - u$ langkah turun dengan $u - (n - u) = k$ , yakni $u = \frac{n+k}2$ : yang mungkin bila dan hanya bila $n + k$ genap dan $\abs k \leq n$ , dalam $\binom{n}{(n+k)/2}$ cara. Adapun tiap lintasan tertentunya berupa satu titik ukuran hasil kali setimbang pada $n$ lemparan: jadi berpeluang $2^{-n}$ . Karena itu $\P(S_n = k) = N_n(k)2^{-n}$ .

2. Peubah $S_n$ berparitas $n$ , jadi $S_{2n+1} \neq 0$ ; dan $u_n = N_{2n}(0)4^{-n} = \binom{2n}n4^{-n}$ . Adapun nilainya: $u_1 = \frac12$ , $u_2 = \frac6{16} = \frac38$ , dan $u_3 = \frac{20}{64} = \frac5{16}$ .

3. Berlaku $\dfrac{u_n}{u_{n-1}} = \dfrac{\binom{2n}n}{4\binom{2n-2}{n-1}} = \dfrac{(2n)(2n-1)}{4n^2} = \dfrac{2n-1}{2n} < 1$ : jadi turun. Lalu menurut Contoh 6.14, $\binom{2n}n \sim \frac{4^n}{\sqrt{\pi n}}$ , jadi $u_n \sim \frac1{\sqrt{\pi n}} \to 0$ , dan $\sum u_n$ divergen lewat pembandingan dengan $\sum n^{-1/2}$ .

4. Diberikan sebuah lintasan dari $1$ ke $k$ yang menyentuh $0$ , pantulkanlah ruas awalnya (sampai kunjungan pertamanya ke $0$ ) terhadap sumbu mendatarnya: hasilnya sebuah lintasan dari $-1$ ke $k$ , dan operasinya berupa involusi — sebab setiap lintasan dari $-1$ ke $k \geq 1$ mesti menyeberangi $0$ , dan memantulkan ruas awalnya kembali memulihkan aslinya. Karena itu lintasan yang menyentuhnya berjumlah $N_{n-1}(k + 1)$ (sebab dari $-1$ ke $k$ perpindahannya $k + 1$ ). Adapun lintasan dari $0$ ke $k$ yang tinggal $> 0$ sesudah waktu $0$ bermula dengan langkah naik lalu berjalan dari $1$ ke $k$ dalam $n - 1$ langkah tanpa menyentuh $0$ : jadi ada $N_{n-1}(k-1) - N_{n-1}(k+1)$ di antaranya.

5. Dengan $m = \frac{n+k}2$ , dan memakai $\binom{n-1}{m-1} = \frac mn\binom nm$ serta $\binom{n-1}{m} = \frac{n-m}n\binom nm$ :

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

Untuk $n = 3$ dan $k = 1$ : ada $N_3(1) = 3$ lintasan (yakni $++-$ , $+-+$ , $-++$ ), dan hanya $++-$ yang tinggal positif (sebab $+-+$ pulang ke $0$ pada waktu $2$ ): jadi satu dari tiga, dan $\frac kn = \frac13$ .

6. Berkat kesimetriannya peluangnya adalah $2\P(S_i > 0\ \forall i \leq 2n)$ . Lalu menjumlahkannya atas titik ujungnya $2k$ dan memakai pertanyaan 4 (dengan $n$ diganti $2n$ ):

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

yakni sebuah jumlah yang berteleskop. Kini $N_{2n-1}(1) = \binom{2n-1}{n}$ dan $2\binom{2n-1}n = \binom{2n}n$ (menurut Pascal), jadi peluang pada displainya adalah $2\cdot2^{-2n}\binom{2n-1}n = \binom{2n}n4^{-n} = u_n$ .

7. Kejadian $D_n = \{S_i \neq 0,\ i \leq 2n\}$ turun, dengan irisannya “tak pernah pulang”; jadi menurut kekontinuan monoton dan pertanyaan 6, $\P(\text{tak ada kepulangan}) = \lim u_n = 0$ : sehingga jalannya pulang hampir pasti. Lebih jauh $f_n = \P(D_{n-1}) - \P(D_n) = u_{n-1} - u_n$ , dan menurut pertanyaan 3

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

8. Berlaku $2n\,f_n = \frac{2n}{2n-1}u_n \geq u_n$ , dan $\sum u_n = \infty$ (pertanyaan 3): jadi deret $\sum 2nf_n$ divergen. Sehingga kepulangan pertamanya pasti tetapi tak punya waktu tunggu rerata yang berhingga — jadi jalannya bersifat rekuren nol, dalam kosakata yang kelak disediakan Bab 22.

9. Kejadian “sekurangnya $k$ kepulangan” merupakan gabungan terbilang yang lepas, atas $0 < n_1 < \dots < n_k$ , bagi kejadian “ $k$ kepulangan pertamanya terjadi tepat pada waktu $2n_1, \dots, 2n_k$ ”. Adapun kejadian semacam itu adalah irisan $k$ kejadian yang bergantung pada blok lemparan yang saling lepas $\intint1{2n_1}$ , $\intint{2n_1+1}{2n_2}$ , …, dan tiap bloknya menuntut sebuah jalan baru membuat kepulangan pertamanya sesudah tepat sebanyak langkah yang dijatahkan; jadi berkat kebebasan bloknya peluangnya adalah $f_{n_1}f_{n_2-n_1}\cdots f_{n_k-n_{k-1}}$ . Lalu setelah dijumlahkan lewat paket (Bab 7, sebab semua sukunya taknegatif):

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

Kejadiannya turun dalam $k$ , jadi kekontinuan monoton memberi $\P(\text{pulang tak hingga kali}) = 1$ : itulah kerekurenannya.

10. Menurut pertanyaan 9, jalannya membuat tak berhingga banyak ekskursi menjauh dari $0$ . Adapun langkah pertama tiap ekskursinya berupa koin baru yang bebas dari segala sebelumnya: jadi peluang bahwa $m$ ekskursi pertamanya semuanya bermula ke bawah adalah $2^{-m}$ . Lalu untuk mencapai $1$ jalannya hanya menuntut satu ekskursi yang bermula ke atas (sebab dari $<0$ ia mesti melewati $0$ sebelum mencapai $1$ , karena langkahnya $\pm1$ ), jadi $\P(\text{tak pernah mengenai }1) \leq 2^{-m}$ untuk setiap $m$ : sehingga jalannya mengenai $1$ hampir pasti. Lalu dengan menguraikannya atas waktu pengenaannya (yang hampir pasti berhingga), jalan yang dimulai ulang di sana merupakan jalan baru yang bermula di $1$ : jadi secara induktif ia mengenai setiap $k \geq 1$ hampir pasti, dan berkat kesimetriannya setiap $k \leq -1$ . Akhirnya, dengan memulai ulang di kunjungan pertamanya ke $k$ , pertanyaan 9 berlaku bagi jalan barunya: jadi setiap tapaknya dikunjungi tak berhingga sering, dan itu secara hampir pasti.

11. Kejadian $A_n = \{S_{2n} = 0\}$ jauh dari saling bebas (sebab berada di $0$ pada waktu $2n$ membuat berada di $0$ pada waktu $2n + 2$ jauh lebih mungkin daripada $u_{n+1}$ ), jadi Borel–Cantelli 2 tak tersedia, dan memang seluruh kerja Bagian II adalah untuk menggantikannya. Sedangkan arah lainnya tak menuntut kebebasan: sebab bila $\sum\P(A_n)$ konvergen, maka Borel–Cantelli 1 menghasilkan berhingga banyak kepulangan hampir pasti. Dan implikasi itulah mesin setiap bukti ketransienan di bawah.

12. Sebuah kepulangan pada waktu $2n$ menuntut $n$ langkah naik dan $n$ langkah turun: jadi $\P(S_{2n} = 0) = \binom{2n}np^nq^n = u_n(4pq)^n$ , dan $4pq = 1 - (p - q)^2 < 1$ untuk $p \neq \frac12$ . Lalu karena $u_n \leq 1$ , deret $\sum\P(S_{2n} = 0)$ didominasi deret geometri $\sum(4pq)^n$ : jadi konvergen. Sehingga menurut Borel–Cantelli 1, $\P(S_{2n} = 0 \text{ tak berhingga sering}) = 0$ : jadi berhingga banyak kepulangan, secara hampir pasti.

13. Untuk $n + k$ yang genap berlaku $\P(S_n = k) = \binom{n}{\frac{n+k}2}p^{\frac{n+k}2}q^{\frac{n-k}2}$ ; adapun koefisien binomialnya paling banyak sebesar yang pusatnya, dan $p^{\frac{n+k}2}q^{\frac{n-k}2} = (pq)^{n/2}(p/q)^{k/2}$ , sehingga memberi batas yang dinyatakan $\leq 2^n(pq)^{n/2}(p/q)^{k/2} = (4pq)^{n/2}(p/q)^{k/2}$ , yang terjumlahkan dalam $n$ karena $\sqrt{4pq} < 1$ . Jadi Borel–Cantelli 1: tapak $k$ dikunjungi berhingga sering hampir pasti; lalu gabungan atas $k \in \Z$ bagi kejadian nol kekecualiannya tetap nol (berkat kesubaditifan terbilangnya). Jadi hampir pasti setiap tapaknya dikunjungi berhingga sering, sehingga barisan bulat $(S_n)$ meninggalkan setiap jendela terbatasnya untuk selamanya: yakni $\abs{S_n} \to \infty$ .

14. Berlaku $\P(S_n \neq 0,\ 1 \leq n \leq 200) = u_{100} = \binom{200}{100}4^{-100} \approx \frac1{\sqrt{100\pi}} \approx 0.056$ : jadi lebih dari satu peluang dari dua puluh bahwa $200$ lemparan setimbang tak pernah seri. Adapun peluruhan $1/\sqrt{\pi n}$ -nya menyiksa saking lambatnya: sebab kepastian seri (pertanyaan 7) serasi dengan rentang tanpa seri yang sangat panjang — yakni cita rasa pertama gejala arcsinus pada Bagian IV.

15. Syaratkanlah pada langkah pertamanya. Bila $X_1 = +1$ maka $T_1 = 1$ , dan $f_1 = \frac12$ cocok. Sedangkan bila $X_1 = -1$ , jalannya harus mendaki dari $-1$ ke $1$ ; jadi menurut penguraian bloknya, pulang ke $0$ untuk pertama kalinya pada waktu $2n$ terpecah sebagai: satu langkah turun, lalu sebuah jalan baru yang bermula di $-1$ pertama kali mencapai $0$ — yang setara dengan sebuah jalan baru yang pertama kali mencapai $+1$ — dalam $2n - 1$ langkah, atau kejadian setangkupnya ke atas. Kedua tandanya menyumbang sama:

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

Karena itu $\P(T_1 < \infty) = \sum f_n = 1$ , sedangkan $\sum_n(2n - 1)f_n = \sum_n u_n = \infty$ menurut pertanyaan 7: jadi jalannya mencapai $1$ hampir pasti, dalam waktu rerata yang tak hingga.

16. Partisikanlah $\{M_n \geq k\}$ menurut nilai akhirnya $S_n = m$ . Untuk $m \geq k$ syarat $M_n \geq k$ berlaku otomatis. Sedangkan untuk $m < k$ , pantulkanlah lintasannya sesudah kunjungan pertamanya ke aras $k$ : ini merupakan bijeksi antara $\{M_n \geq k, S_n = m\}$ dan $\{S_n = 2k - m\}$ (sebab setiap lintasan yang berakhir di $2k - m > k$ mengunjungi $k$ ; dan memantulkannya kembali adalah baliknya). Karena itu

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

17. Pada waktu genap $2n$ dengan $k = 1$ : berlaku $\P(S_{2n} = 1) = 0$ dan $\P(S_{2n} > 1) = \P(S_{2n} \geq 2)$ , jadi

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

Jadi $\P(S_i \leq 0\ \forall i \leq 2n) = u_n$ : sehingga jalannya tak pernah unggul pada $2n$ langkah pertamanya sesering ia tak pernah seri (pertanyaan 6) — yakni dua kejadian yang cukup berbeda, yang diusung $u_n$ yang sama.

18. Berlaku $\{L_{2n} = 2k\} = \{S_{2k} = 0\} \cap \{\text{jalan atas lemparan } 2k+1, \dots, 2n \text{ tak bernol}\}$ . Adapun kedua kejadiannya bergantung pada blok lemparan yang saling lepas, jadi keduanya saling bebas; yang pertama berpeluang $u_k$ , dan yang kedua $u_{n-k}$ menurut pertanyaan 6 yang diterapkan pada jalan baru berlangkah $(2n-2k)$ . Karena itu $\P(L_{2n} = 2k) = u_ku_{n-k}$ . Lalu karena $L_{2n}$ mengambil persis nilai $0, 2, \dots, 2n$ , peluang itu berjumlah $1$ : yakni $\sum_{k=0}^nu_ku_{n-k} = 1$ , sebuah kesamaan binomial yang diserahkan oleh sebuah pemartisian peluang.

19. Kesetangkupannya seketika: sebab $u_ku_{n-k} = u_{n-k}u_k$ . Lalu karena $u_j$ turun dalam $j$ , hasil kali $u_ku_{n-k}$ terkecil bagi $k$ yang di tengah dan terbesar di ekstremnya $k \in \{0, n\}$ , tempat ia sama dengan $u_n$ ; secara kuantitatif $u_ku_{n-k} \approx \frac1{\pi\sqrt{k(n-k)}}$ di tengahnya, terhadap $u_n \approx \frac1{\sqrt{\pi n}}$ di tepinya. Untuk $n = 5$ : $\P(L_{10} = 0) = \P(L_{10} = 10) = u_5 = \frac{63}{256} \approx 0.246$ , sedangkan $\P(L_{10} = 4) = u_2u_3 = \frac38\cdot\frac5{16} = \frac{15}{128} \approx 0.117$ . Jadi pada permainan setimbang yang panjang, penyamaan terakhirnya paling mungkin di dekat awal sekali atau akhir sekali: sehingga satu pemain biasanya unggul untuk rentang yang sangat panjang, tanpa keberatsebelahan pada koinnya.

20. Gambarannya: pada waktu $n$ jalannya hidup pada skala $\sqrt n$ (yakni rentang binomial pertanyaan 3 — sebab $u_n \sim 1/\sqrt{\pi n}$ adalah tinggi puncak pusatnya); lalu ia pulang ke $0$ tak berhingga sering dengan peluang $1$ (Bagian II), namun waktu tunggu di antara kepulangannya bererata divergen (pertanyaan 8), dan itulah sebabnya satu ekskursi dapat menempati pecahan positif sembarang cakrawala; sepadan dengan itu seri terakhir sebuah permainan berlangkah $2n$ tersebar dengan nilai ekstremnya paling mungkin (pertanyaan 18–19), dan tak pernah unggul berpeluang $u_n$ yang meluruh lambat sama seperti tak pernah seri (pertanyaan 17). Jadi kepastian pada limitnya, keawetan pada setiap cakrawala berhingganya: itulah jalan yang setimbang.

21. Partisikanlah $\{S_{2n} = 0\}$ (dengan $n \geq 1$ ) menurut waktu kepulangan pertamanya $2k$ dengan $1 \leq k \leq n$ : maka blok pertama berisi $2k$ lemparan mewujudkan sebuah kepulangan pertama, sedangkan $2n - 2k$ lemparan sisanya mewujudkan kepulangan sebuah jalan baru, dan bloknya saling bebas: jadi $u_n = \sum_{k=1}^nf_ku_{n-k}$ . Adapun kedua deretnya $U(x) = \sum u_nx^n$ dan $F(x) = \sum f_nx^n$ berjari-jari $\geq 1$ (sebab koefisiennya di $\intcc01$ ), dan hasil kali Cauchynya (Bab 11) memberi, untuk $0 \leq x < 1$ ,

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

22. Ketika $x \uparrow 1$ , fungsi $U(x)$ dan $F(x)$ naik (sebab koefisiennya taknegatif); dan tiap jumlah parsial $\sum_{n\leq N}u_n$ merupakan limit $\sum_{n\leq N}u_nx^n \leq U(x)$ , jadi $U(x) \uparrow \sum u_n \in \intoc0{+\infty}$ , dan demikian pula $F(x) \uparrow f = \sum f_n$ . Bila $\sum u_n = \infty$ : maka $1 - F(x) = 1/U(x) \to 0$ , jadi $f = 1$ . Sedangkan bila $\sum u_n = S < \infty$ : maka $1 - f = 1/S > 0$ , jadi $f < 1$ . Adapun pemeriksaannya: jalan setimbangnya, $\sum u_n = \infty$ dan $f = 1$ (pertanyaan 3, 7); sedangkan jalan berat sebelahnya, $\sum u_n(4pq)^n < \infty$ dan sepadan dengan itu $f = 1 - 1/\sum_{n\geq0}u_n(4pq)^n < 1$ , yang konsisten dengan keberhinggaan hampir pasti banyaknya kepulangan (pertanyaan 12).

23. Untuk keempat langkah $(\pm1, 0), (0, \pm1)$ pada jalan $\Z^2$ , pertambahan $U = X + Y$ dan $V = X - Y$ adalah: $(+,+)$ bagi $(1,0)$ , $(+,-)$ bagi $(0,1)$ , $(-,+)$ bagi $(0,-1)$ , dan $(-,-)$ bagi $(-1,0)$ — dengan tiap pasangan tandanya berpeluang $\frac14 = \frac12\cdot\frac12$ : jadi kedua jalan koordinatnya $(U_n)$ dan $(V_n)$ merupakan jalan setimbang yang saling bebas pada $\Z$ . Lalu karena $S^{(2)}_{2n} = (0,0)$ bila dan hanya bila $U_{2n} = 0$ dan $V_{2n} = 0$ ,

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

Adapun kesamaan pembaruan pertanyaan 21 dan dikotomi pertanyaan 22 tak memakai apa pun yang satu dimensi (melainkan hanya penguraian atas kepulangan pertamanya beserta kebebasan blok yang saling lepas), jadi $\sum u_n^{(2)} = \infty$ memberi $f^{(2)} = 1$ , lalu hujah pertanyaan 9 meningkatkannya: sehingga jalan pada $\Z^2$ pulang ke titik asalnya tak berhingga sering hampir pasti.

24. Dengan batas yang diterima $\P(S^{(3)}_{2n} = 0) \leq Cn^{-3/2}$ , deretnya konvergen, jadi Borel–Cantelli 1 memberi berhingga banyak kepulangan hampir pasti: sehingga jalan pada $\Z^3$ bersifat transien (dan batas yang sama dengan eksponen $-d/2$ menangani setiap $d \geq 3$ ). Jadi semuanya: yakni teorema Pólya — bahwa jalan acak sederhana bersifat rekuren pada $\Z$ dan $\Z^2$ , serta transien pada $\Z^d$ untuk $d \geq 3$ . Seorang pemabuk menemukan jalan pulangnya; sedangkan seekor burung yang mabuk boleh jadi tidak.

25. Pencacahan lintasan dan pemantulan menghasilkan hukum eksaknya ( $u_n$ , teorema pemungutan suara, $f_n$ , maksimumnya, nol terakhirnya); kekontinuan monoton mengubah setiap pernyataan limit (yakni “pulang sekurangnya sekali” dan “tak berhingga sering”) menjadi limit peluang bercakrawala berhingga; kebebasan blok yang saling lepas menggerakkan penguraian pembaruannya (pertanyaan 9, 18, 21) — sebab ia rangka terbilang bagi sifat Markovnya; Borel–Cantelli 1 menjadi senjata ketransienannya (pertanyaan 12–13, 24), yang tak menuntut kebebasan; dan kesamaan pembaruannya menata semuanya menjadi dikotomi $\sum u_n = \infty \iff$ kerekurenan. Adapun satu masukan analitisnya adalah taksiran lokal $u_n \sim 1/\sqrt{\pi n}$ : sebab kuadratnya $1/(\pi n)$ masih divergen (jadi dimensi $2$ rekuren), sedangkan $n^{-3/2}$ konvergen (jadi dimensi $3$ transien) — sehingga teorema Pólya, pada akhirnya, adalah pernyataan tentang kedivergenan $\sum n^{-d/2}$ .

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium

21.1 Ruang peluang

21.2 Penyaratan dan kebebasan

21.3 Lema Borel–Cantelli

21.4 Latihan

21.5 Soal: jalan acak sederhana pada Z\ZZ bersifat rekuren

Istilah yang didefinisikan dalam bab ini

21.5 Soal: jalan acak sederhana pada $\Z$ bersifat rekuren