Apa itu Kebebasan?

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

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

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

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 22.7 (Masalah ulang tahun, secara jujur)

Di antara $n$ orang yang ulang tahunnya bebas dan seragam atas $N = 365$ hari, peluang bahwa semua ulang tahunnya berbeda adalah

lewat pensyaratan berulang (atau langsung: yakni yang menguntungkan $N(N-1)\cdots(N - n + 1)$ atas total $N^n$, yakni argumen pencacahan yang dijadikan ketat oleh rumus hasil kali kebebasannya). Lalu dengan mengambil logaritma dan memakai $-\ln(1 - x) = x + O(x^2)$:

Titik baliknya $p_n = \frac12$ terletak di $n \approx \sqrt{2N\ln2} \approx 1.18\sqrt N$: untuk $N = 365$, $n = 23$ (dengan $p_{23} = 0.4927$). Ada dua pelajaran. Pertama, tumbukan di antara $n$ benda dalam $N$ kotak muncul pada skala $n \sim \sqrt N$, bukan $n \sim N$ — yakni penskalaan ulang tahun yang mengatur tumbukan hash dan ongkos $\sqrt N$ bagi serangan ulang tahun dalam kriptografi. Kedua, perhitungannya adalah sebuah cetakan: sebab $\binom n2$ kejadian tumbukan berpasangannya tidak bebas, namun jawabannya berperilaku seolah-olah bebas (sebab $\eu^{-\binom n2/N}$ persis merupakan heuristik pasangan-bebasnya) — yakni contoh pertama hampiran Poisson yang dijadikan ketat pada soal akhir pekan Bab 23 (yakni ketaksamaan Le Cam).

Contoh 22.14 (Apa yang dibeli hukum kuatnya)

(a) Frekuensinya: bagi lemparan koin i.i.d., frekuensi sisi gambar yang teramati konvergen secara h.p. ke $p$ — yakni pembenaran empiris bagi peluang itu sendiri. (b) Monte Carlo: bagi $g \in L^1(\intcc01)$ dan $(U_n)$ seragam i.i.d. (Teorema 22.6), $\frac1n\sum_{k\leq n}g(U_k) \to \int_0^1g$ secara h.p.: yakni integral lewat pencuplikan, pada dimensi mana pun, dengan laju yang tak bergantung dimensi $\sim n^{-1/2}$ yang dipertajam pada Bab 23. (c) Bilangan normal: hampir setiap bilangan real mempunyai, pada uraian binernya, frekuensi asimtotik $\frac12$ bagi angka satu (terapkanlah hukum kuatnya pada variabel digit Teorema 22.6) — yakni teorema Borel, sebuah pernyataan tentang bilangan sehari-hari yang dibuktikan lewat ukuran: Soal 22.1 melengkapinya pada semua basis.