---
title: "Peluang pada Ruang Terbilang"
book: "Matematika Universitas — Tahun 2"
subject: math
language: id
chapter: 21
exercises: 12
source: https://one-course.com/books/math/4/id/chapter/21-peluang-pada-ruang-terbilang
---

# Bab 21 — Peluang pada Ruang Terbilang

Ketiga bab terakhir mengembangkan teori peluang modern: yakni [ukuran peluang](#def-b2-proba-space) pada [ruang sampel](#def-b2-proba-space) yang [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable), peubah acak diskret, dan [fungsi pembangkit](https://one-course.com/books/math/4/id/chapter/11-deret-pangkat#ex-b2-powerseries-fibonacci). Adapun teori berhingga pada jilid Kelas 10–12 memperoleh infrastruktur penuhnya: sebab keaditifan-$\sigma$ menggantikan keaditifan berhingga, dan perkakas [keluarga terjumlahkan](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable) pada [Bab 7](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series) persis merupakan yang membuat [ruang sampel](#def-b2-proba-space) tak hingga dapat dikerjakan. Adapun hasil utamanya di sini adalah kekontinuan peluang sepanjang barisan [kejadian](#def-b2-proba-space) 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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) (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:

1. $\P(\Omega) = 1$ ;
2. (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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable)).

**Catatan 21.2.**

Pada $\Omega$ yang [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) kita boleh mengambil semua himpunan bagiannya sebagai [kejadian](#def-b2-proba-space); sedangkan pada ruang yang tak [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) (sebagaimana diperlukan bagi model [kontinu](https://one-course.com/books/math/4/id/chapter/4-topologi-ruang-metrik#def-b2-metric-continuity) pada Tahun ke-3) hal ini tak lagi mungkin, jadi kita membatasi $\P$ pada sebuah koleksi [kejadian](#def-b2-proba-space) 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](#def-b2-proba-space) $A, B$ dan [ukuran peluang](#def-b2-proba-space) $\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](#exo-b2-proba-4). ∎

**Proposisi 21.4 (Distribusi pada ruang terbilang).**

Memberikan sebuah [ukuran peluang](#def-b2-proba-space) pada $\Omega =
\{\omega_0, \omega_1, \dots\}$ yang [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-def)) keluarga $(p_i)$.

**Bukti.** Diberikan $\P$, singleton $\{\omega\}$ dengan $\omega \in A$ membentuk peliput lepas yang [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) bagi $A$, jadi keaditifan-$\sigma$ memaksa

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

yakni subjumlah tanpa syarat keluarga taknegatif yang [terjumlahkan](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable) $(p_i)$ — sebab penataan ulangnya tak berbahaya persis karena sukunya taknegatif ([Bab 7](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series)); 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable), dan keaditifan-$\sigma$-nya persis merupakan teorema penjumlahan lewat paket pada [Bab 7](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series) 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](#def-b2-proba-space) karena $\sum_{k\geq1}(1-p)^{k-1}p =
\frac{p}{1 - (1-p)} = 1$: jadi dengan peluang $1$ permainannya berakhir — tetapi [ruang sampelnya](#def-b2-proba-space) 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](#def-b2-proba-space).

1. 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)$ .
2. 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](#def-b2-proba-space) 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](#def-b2-proba-space) — 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](https://one-course.com/books/math/4/id/chapter/22-peubah-acak-diskret#ch-b2-randomvar), 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](#def-b2-proba-space) 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](#def-b2-proba-space) 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](#def-b2-proba-space) $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](#def-b2-proba-space) pada $\Omega$.

**Catatan 21.11.**

Bahwa $A \mapsto \pcond BA$ kembali merupakan [ukuran peluang](#def-b2-proba-space) 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](#def-b2-proba-space) 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).**

1. (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}) .$$
2. (Peluang total) Bila $(B_i)_{i \in I}$ merupakan pemartisian $\Omega$ yang berhingga atau [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) dengan $\P(B_i) > 0$, maka untuk setiap [kejadian](#def-b2-proba-space) $A$: $$\P(A) = \sum_{i \in I} \P(A \mid B_i)\,\P(B_i) .$$
3. (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](#def-b2-proba-conditional) 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](#def-b2-proba-space) 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](#thm-b2-proba-bayes)),

$$
\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](#exo-b2-proba-3)); sehingga mengutip $\pcond{\text{sakit}}{
\text{positif}}$ ketika yang dimaksud $\pcond{\text{positif}}{
\text{sakit}}$ adalah kekeliruan laju-dasarnya. (ii) *Menyaratkan pada [kejadian](#def-b2-proba-space) yang keliru*: sebab pada Monty Hall, [kejadian](#def-b2-proba-space) 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](#def-b2-proba-independence)*: sebab [kejadian](#def-b2-proba-space) yang saling lepas dan berpeluang positif tak pernah [saling bebas](#def-b2-proba-independence) ($\P(A\cap B) = 0 \neq \P(A)\P(B)$) — jadi kebebasan adalah keserasian informasi, bukan ketiadaan tumpang tindih.

**Definisi 21.19 (Kebebasan).**

[Kejadian](#def-b2-proba-space) $A$ dan $B$ disebut *saling bebas* bila $\P(A \cap B) =
\P(A)\P(B)$. Adapun keluarga [kejadian](#def-b2-proba-space) $(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](#def-b2-proba-space) “yang pertama gambar”, “yang kedua gambar”, dan “keduanya sepakat” [saling bebas](#def-b2-proba-independence) 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](#def-b2-proba-independence), 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](#def-b2-proba-independence), 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](#def-b2-proba-space) yang bergantung pada kelompok lemparan yang saling lepas bersifat [saling bebas](#def-b2-proba-independence)” (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](#ex-b2-proba-geometric), 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](#exo-b2-proba-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](#exo-b2-proba-6) beserta perhitungan singgahan pertama pada soal akhir pekan.

## 21.3 Lema Borel–Cantelli

**Definisi 21.23 (Limit superior kejadian).**

Untuk sebuah barisan [kejadian](#def-b2-proba-space) $(A_n)$, [kejadian](#def-b2-proba-space)

$$
\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](#def-b2-proba-space) “$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](#def-b2-proba-space) “*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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) di seluruhnya, sehingga semuanya [kejadian](#def-b2-proba-space) yang jujur.

**Teorema 21.25 (Borel–Cantelli).**

1. Bila $\sum_{n} \P(A_n) < \infty$ , maka $\P\bigl(\limsup_n A_n\bigr) = 0$ .
2. Bila [kejadian](#def-b2-proba-space) $A_n$ [saling bebas](#def-b2-proba-independence) 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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) ([Akibat 21.7](#cor-b2-proba-subadd))

$$
\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](#thm-b2-proba-continuity)) 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](#def-b2-proba-space) $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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) ([Akibat 21.7](#cor-b2-proba-subadd)), jadi irisan [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) $\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](#def-b2-proba-space) “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](#def-b2-proba-space) $A_{jk}$ (dengan $j =
1, 2, \dots$), yang bergantung pada blok lemparan yang saling lepas, bersifat [saling bebas](#def-b2-proba-independence), 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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) deretannya kita biarkan tumbuh, $B_n = {}$“sebuah deretan $2\log_2 n$ gambar bermula di $n$” punya $\P(B_n) = n^{-2}$ yang [terjumlahkan](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable), jadi hampir pasti hanya berhingga banyak deretan [panjang](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) semacam itu bermula: sehingga Borel–Cantelli menakar persis *seberapa [panjang](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length)* deretan terpanjangnya.

**Contoh 21.27 (Monyet tak hingga, dikuantifikasi).**

Seekor monyet mengetik huruf seragam yang [saling bebas](#def-b2-proba-independence) dari abjad berhuruf $26$. Potonglah ketikannya menjadi blok lepas berisi empat huruf; maka [kejadian](#def-b2-proba-space) $A_j = {}$“blok $j$ mengeja MATH” [saling bebas](#def-b2-proba-independence) 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](#ex-b2-proba-runs) [ruang sampel](#def-b2-proba-space) yang mendasarinya (yakni barisan lemparan yang tak hingga) bersifat tak [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable), 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](#def-b2-proba-space) yang ditentukan berhingga banyak lemparan dan kombinasi [terbilangnya](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable). Inilah konvensi baku pada tingkat ini: teorinya dinyatakan pada ruang [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable), 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](#def-b2-proba-space) menjadi peubah acak, dan keaditifan-$\sigma$ menjadi keterjumlahan yang mendefinisikan nilai harapan ([Bab 22](https://one-course.com/books/math/4/id/chapter/22-peubah-acak-diskret#ch-b2-randomvar)); sedangkan Borel–Cantelli ditambah batas ekor yang [terjumlahkan](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable) persis merupakan cara hukum bilangan besar yang kuat bagi koin dibuktikan di sana. Adapun pada [Bab 23](https://one-course.com/books/math/4/id/chapter/23-fungsi-pembangkit-peluang#ch-b2-genfun), 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](#def-b2-proba-space) sebagai gabungan yang naik (atau irisan yang turun) atas [kejadian](#def-b2-proba-space) bercakrawala berhingga yang peluangnya terhitung ([Contoh 21.9](#ex-b2-proba-sixeventually)). *Gabungan nol*: sebab gabungan [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) atas [kejadian](#def-b2-proba-space) berpeluang nol bernilai nol (berkat kesubaditifan [terbilangnya](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable)), jadi cukuplah membunuh tiap [kejadian](#def-b2-proba-space) buruknya secara terpisah — dan begitulah “untuk setiap $j$, akhirnya $\abs{\widehat p_n - p} < 1/j$” terangkai menjadi kekonvergenan. *Borel–Cantelli*: ketika [kejadiannya](#def-b2-proba-space) 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](#pb-b2-proba-1) pada soal akhir pekan bab ini, sisi hampir pasti hukum bilangan besar ([Bab 22](https://one-course.com/books/math/4/id/chapter/22-peubah-acak-diskret#ch-b2-randomvar)), dan analisis kepunahan proses bercabang ([Bab 23](https://one-course.com/books/math/4/id/chapter/23-fungsi-pembangkit-peluang#ch-b2-genfun)). Adapun jilid Tahun ke-3 membangun ulang teorinya atas aljabar-$\sigma$ dan pengintegralan Lebesgue, tempat [ruang sampel](#def-b2-proba-space) tak [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) 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 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](#def-b2-proba-space) 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](#def-b2-proba-space), 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series).)*

**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](#def-b2-proba-space). 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series)),

$$
\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 Latihan 21.3.**

Misalkan $S$ = sakit dan $+$ = uji positif. Maka Bayes ([Teorema 21.14](#thm-b2-proba-bayes)) 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](#def-b2-proba-space). 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 Latihan 21.4.**

[Titik demi titik](https://one-course.com/books/math/4/id/chapter/10-barisan-dan-deret-fungsi#def-b2-funcseq-def) 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable) — mengubah tiap indikatornya menjadi peluang [kejadiannya](#def-b2-proba-space), 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](#exo-b2-proba-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 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 Latihan 21.6.**

Syaratkanlah pada awalnya (yakni aturan rantai / [Teorema 21.14](#thm-b2-proba-bayes)):

- 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](#def-b2-proba-space) “permainannya berlangsung lebih dari $n$” turun ke “permainannya tak pernah berakhir”; jadi kekontinuan monoton ([Teorema 21.6](#thm-b2-proba-continuity)) 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](#def-b2-proba-independence), 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](#def-b2-proba-space) $R_n$ [saling bebas](#def-b2-proba-independence) 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 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](#def-b2-proba-space) 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](#def-b2-proba-independence) (yang diterima saja), jadi Borel–Cantelli 2 ([Teorema 21.25](#thm-b2-proba-borelcantelli)) 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](#def-b2-proba-space) yang [saling bebas](#def-b2-proba-independence) 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](#def-b2-proba-space) (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 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](#exo-b2-proba-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](#def-b2-proba-space) 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 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](#def-b2-proba-independence) 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 Latihan 21.10.**

[Kejadian](#def-b2-proba-space) $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](#thm-b2-proba-continuity)) 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 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](#def-b2-proba-independence), jadi [kejadian](#def-b2-proba-space) 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](#def-b2-proba-space) 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 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-proba/fig-1c561d473a2b.svg)

*Dua puluh empat langkah sebuah [jalan acak sederhana](#pb-b2-proba-1); 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](#ex-b2-proba-runs), semua [kejadian](#def-b2-proba-space) di bawah ditentukan oleh berhingga banyak lemparan atau berupa kombinasi [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) [kejadian](#def-b2-proba-space) semacam itu, dan kebebasan [kejadian](#def-b2-proba-space) 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.**

1. 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?
2. Tunjukkan $S_{2n+1} \neq 0$ dan $u_n =  \binom{2n}{n}4^{-n}$ , lalu hitunglah $u_1, u_2, u_3$ .
3. Buktikan $u_n = \frac{2n-1}{2n}\,u_{n-1}$; lalu turunkan bahwa $(u_n)$ turun ke $0$, dan dari [Contoh 6.14](https://one-course.com/books/math/4/id/chapter/6-perbandingan-fungsi#ex-b2-comparison-centralbinomial) bahwa $$u_n \sim \frac{1}{\sqrt{\pi n}},  \qquad\text{jadi}\qquad  \sum_n u_n = \infty .$$
4. (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)$ .
5. (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.**

6. 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}$)*.
7. Turunkan dari kekontinuan monoton ([Teorema 21.6](#thm-b2-proba-continuity)) 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 .$$
8. Tunjukkan bahwa $\sum_n 2n\,f_n = \infty$ : jadi kepulangannya pasti, tetapi deret yang akan menghitung waktu tunggu reratanya divergen (dalam kosakata [Bab 22](https://one-course.com/books/math/4/id/chapter/22-peubah-acak-diskret#ch-b2-randomvar) , waktu kepulangannya bernilai harapan tak hingga).
9. 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](#pb-b2-proba-1) pada $\Z$ bersifat *rekuren*.
10. 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](#def-b2-proba-independence); dan sebuah ekskursi positif mengunjungi $1$.)*

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

11. [Kejadian](#def-b2-proba-space) $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.)
12. 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.
13. 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* .
14. 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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) tetapi lebih langka daripada dugaan gerak hati.
15. (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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length).**

16. (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$.
17. 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](#def-b2-proba-space) yang berbeda, satu peluang.
18. (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$.
19. 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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) , seri terakhirnya cenderung sangat awal atau sangat lambat — jadi keunggulan yang [panjang](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) adalah aturannya, bukan kekecualiannya.
20. 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.**

21. 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](https://one-course.com/books/math/4/id/chapter/11-deret-pangkat#ch-b2-powerseries)).
22. 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).
23. (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](#def-b2-proba-independence)* 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.
24. (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](#pb-b2-proba-1) bersifat rekuren pada dimensi $1$ dan $2$ , dan transien pada dimensi $3$ ke atas.
25. 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 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](https://one-course.com/books/math/4/id/chapter/6-perbandingan-fungsi#ex-b2-comparison-centralbinomial), $\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](#def-b2-proba-space) $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](https://one-course.com/books/math/4/id/chapter/22-peubah-acak-diskret#ch-b2-randomvar).

**9.** [Kejadian](#def-b2-proba-space) “sekurangnya $k$ kepulangan” merupakan gabungan [terbilang](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) yang lepas, atas $0 < n_1 < \dots < n_k$, bagi [kejadian](#def-b2-proba-space) “$k$ kepulangan pertamanya terjadi tepat pada waktu $2n_1, \dots, 2n_k$”. Adapun [kejadian](#def-b2-proba-space) semacam itu adalah irisan $k$ [kejadian](#def-b2-proba-space) 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#ch-b2-series), sebab semua sukunya taknegatif):

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

[Kejadiannya](#def-b2-proba-space) 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](#def-b2-proba-space) $A_n = \{S_{2n} = 0\}$ jauh dari [saling bebas](#def-b2-proba-independence) (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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#def-b2-series-summable) 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](#def-b2-proba-space) nol kekecualiannya tetap nol (berkat kesubaditifan [terbilangnya](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable)). 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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length) — 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](#def-b2-proba-space) 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](#def-b2-proba-space) 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](#def-b2-proba-space) bergantung pada blok lemparan yang saling lepas, jadi keduanya [saling bebas](#def-b2-proba-independence); 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](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length), penyamaan terakhirnya paling mungkin di dekat awal sekali atau akhir sekali: sehingga satu pemain biasanya unggul untuk rentang yang sangat [panjang](https://one-course.com/books/math/4/id/chapter/18-kurva#def-b2-curves-length), 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](#def-b2-proba-independence): 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](https://one-course.com/books/math/4/id/chapter/7-barisan-dan-deret#thm-b2-series-fubini) ([Bab 11](https://one-course.com/books/math/4/id/chapter/11-deret-pangkat#ch-b2-powerseries)) 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](#def-b2-proba-independence) 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](#pb-b2-proba-1) 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](https://one-course.com/books/math/4/id/chapter/20-integral-garis-dan-integral-lipat#def-b2-multint-exact) ($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](https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur#def-b2-structures-countable) 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}$.