Matematika Universitas — Tahun 3 · Bachelor Year 3

22Peluang: Landasan dan Hukum Bilangan Besar

Tahun 2 membangun peluang pada ruang terbilang; kini teori ukuran melenyapkan setiap pembatasannya. Sebuah ruang peluang adalah ruang ukuran bermassa total $1$ , peubah acak adalah pemetaan terukur, nilai harapan adalah integral Lebesgue — dan seketika seluruh gudang senjata analitisnya (Bab 9, 10 dan 11) berlaku bagi kebetulan. Bab ini memasang kamusnya, membangun barisan tak berhingga peubah acak yang bebas (pada $\intcc01$ , dari digit binernya: sebab keacakan bersembunyi di dalam ukuran Lebesgue), membuktikan lema Borel–Cantelli dan hukum nol–satu Kolmogorov, membereskan jenis-jenis konvergensinya, lalu membuktikan hukum bilangan besar — yakni teorema yang membuat frekuensi konvergen ke peluang dan membuat statistika mungkin. Sedangkan soal akhir pekannya menyajikan bukti Etemadi bagi hukum kuatnya dalam bentuk $L^1$ -nya yang definitif.

22.1 Kamusnya

Definisi 22.1

Sebuah ruang peluang adalah ruang ukuran $(\Omega, \mathcal A, \P)$ dengan $\P(\Omega) = 1$ ; unsur $\mathcal A$ disebut kejadian, dan sebuah sifat berlaku hampir pasti (h.p.) jika kejadiannya berpeluang $1$ . Sebuah peubah acak adalah pemetaan terukur $X \colon \Omega \to \R$ (atau ke $\R^d$ : yakni vektor acak); sedangkan distribusi miliknya adalah ukuran peluang dorongan-maju $\P_X = X_*\P$ pada $\R$ (Latihan 11.9), yang ditentukan oleh fungsi distribusi $F_X(t) = \P(X \leq t)$ (Latihan 9.3). Lalu $X$ mempunyai kepadatan $f$ jika $\P_X = f\,\dd\lambda$ ; dan ia diskret jika $\P_X$ merupakan kombinasi terbilang massa Dirac. Adapun nilai harapan adalah

\E[X] = \int_\Omega X\,\dd\P \qquad (X \geq 0 \text{ atau } X \in L^1(\P)),

dan teorema transfer (Latihan 11.9) menghitungnya di dalam distribusinya: $\E[g(X)] = \int_\R g\,\dd\P_X$ — yakni $= \sum g(x_k)p_k$ pada kasus diskretnya, $= \int g(x)f(x)\dd x$ pada kasus kepadatannya: yakni rumus Tahun 2, kini menjadi teorema satu teori. Sedangkan variansnya adalah $\V(X) = \E[(X - \E X)^2] = \E[X^2] - (\E X)^2$ bagi $X \in L^2$ .

Contoh 22.2

Distribusi bakunya dan transformasi yang patut dicatat: Bernoulli $\mathcal B(p)$ , binomial $\mathcal B(n, p)$ , geometrik, Poisson $\mathcal P(\lambda)$ (yang diskret: tabel Tahun 2 tetap sahih); seragam pada $\intcc01$ (yakni ukuran Lebesgue itu sendiri); eksponensial $\mathcal E(\lambda)$ (berkepadatan $\lambda\eu^{-\lambda x}\mathbf 1_{x>0}$ ); dan Gauss $\mathcal N(m, \sigma^2)$ yang berkepadatan $\frac1{\sigma\sqrt{2\pi}}\exp\bigl(-\frac{(x - m)^2}{2\sigma^2}\bigr)$ — yakni kepadatan peluang menurut Soal 10.1, dengan rata-rata $m$ dan varians $\sigma^2$ (yakni momen Gauss, Latihan 11.10).

Proposisi 22.3 (Markov dan Chebyshev)

Untuk $X \geq 0$ dan $a > 0$ : $\P(X \geq a) \leq \frac{\E X}{a}$ ; sedangkan untuk $X \in L^2$ : $\P\bigl(\abs{X - \E X} \geq a\bigr) \leq \frac{\V(X)}{a^2}$ .

Bukti. Latihan 10.5(a); sedangkan Chebyshev adalah Markov yang diterapkan pada $(X - \E X)^2$ . ∎

22.2 Kebebasan

Definisi 22.4

Sub- $\sigma$ -aljabar $\mathcal A_1, \dots, \mathcal A_n \subseteq \mathcal A$ disebut bebas jika $\P(A_1\cap\dots\cap A_n) = \prod\P(A_i)$ bagi setiap $A_i \in \mathcal A_i$ ; kejadian disebut bebas jika $\sigma$ -aljabar $\{\varnothing, A_i, A_i^c, \Omega\}$ bebas; sedangkan peubah acak $X_1, \dots, X_n$ bebas jika $\sigma$ -aljabar $\sigma(X_i) = X_i^{-1}(\mathcal B(\R))$ bebas. Sebuah keluarga tak berhingga disebut bebas jika setiap subkeluarga berhingganya bebas.

Teorema 22.5

Variabel $X_1, \dots, X_n$ bebas jika dan hanya jika distribusi vektor $(X_1, \dots, X_n)$ adalah ukuran hasil kali $\P_{X_1}\otimes\cdots\otimes\P_{X_n}$ . Dalam hal itu, bagi $g_i \geq 0$ (atau yang hasil kalinya terintegralkan):

\E\Bigl[\prod_ig_i(X_i)\Bigr] = \prod_i\E[g_i(X_i)],

khususnya $\E[XY] = \E X\,\E Y$ dan $\V(X_1 + \dots + X_n) = \sum\V(X_i)$ bagi variabel $L^2$ yang bebas.

Bukti. Jika $X_i$ bebas, maka kedua ukuran peluangnya $\P_{(X_1,\dots,X_n)}$ dan $\bigotimes\P_{X_i}$ sama pada semua hasil kali $B_1\times\dots\times B_n$ himpunan Borel — yakni $\pi$ -sistem yang membangkitkan $\mathcal B(\R^n)$ (Proposisi 11.2(b)) — sehingga sama di mana-mana (Teorema 9.7). Sebaliknya, distribusi hasil kali memfaktorkan setiap kejadian $\bigcap_iX_i^{-1}(B_i)$ : yakni kebebasannya. Lalu rumus nilai harapannya adalah Tonelli/Fubini (Teorema 11.5) lewat teorema transfernya; sedangkan $\E[XY] = \E X\E Y$ adalah kasus $g_i = \mathrm{id}$ , dan menguraikan kuadratnya memberikan keaditifan variansnya (sebab suku silangnya $\E[(X_i - \E X_i)(X_j - \E X_j)] = 0$ ). ∎

Teorema 22.6 (Keberadaan barisan bebas)

Pada $\bigl(\intcc01, \mathcal L, \lambda\bigr)$ ada sebuah barisan $(U_n)_{n\geq1}$ berisi peubah acak yang bebas, masing-masing seragam pada $\intcc01$ . Akibatnya, bagi sembarang distribusi $(\mu_n)$ pada $\R$ yang ditentukan, ada $(X_n)$ bebas dengan $\P_{X_n} = \mu_n$ .

Bukti. Digitnya. Untuk $\omega \in \intcc01$ , misalkan $(b_k(\omega))$ digit binernya (dengan $\omega = \sum b_k2^{-k}$ ; pilihlah uraian yang tak berakhir dengan semua $1$ — sebab ketaktentuannya hanya menyangkut himpunan terbilang, jadi nol). Setiap $b_k$ merupakan peubah acak (sebab $\{b_k = 1\}$ gabungan berhingga selang diadik) dan vektor $(b_1, \dots, b_m)$ mengambil setiap nilai di $\{0,1\}^m$ pada selang diadik berpanjang $2^{-m}$ : sehingga $b_k$ merupakan Bernoulli $(\frac12)$ yang bebas.

Pengelompokan ulangnya. Belahlah $\N^*$ menjadi tak berhingga banyak himpunan tak berhingga yang saling lepas $(I_n)$ (misalnya lewat pangkat prima, atau diagonalnya); lalu biarkanlah $(k^n_j)_j$ mencacah $I_n$ dan tetapkan

U_n = \sum_{j\geq1} b_{k^n_j}\,2^{-j} .

Setiap $U_n$ seragam: sebab digit binernya berupa bit adil yang bebas, sehingga $\P(U_n \in [l2^{-m}, (l+1)2^{-m})) = 2^{-m}$ bagi setiap selang diadik, sedangkan selang diadik menentukan distribusinya (Teorema 9.7). Lalu $U_n$ saling bebas: sebab semuanya fungsi blok saling lepas dari keluarga $(b_k)$ yang bebas — secara formal, kejadian $\{U_n \in D_n\}$ bagi $D_n$ yang diadik bergantung pada berhingga banyak digit dari himpunan yang saling lepas, sehingga memfaktor; lalu argumen $\pi$ -sistemnya menaikkannya ke semua himpunan Borel.

Distribusi sembarang. Ambillah $G_n(u) = \inf\{t : F_{\mu_n}(t) \geq u\}$ (yakni fungsi kuantil bagi fungsi distribusi $F_{\mu_n}$ ); lalu kesetaraan kuncinya $G_n(u) \leq t \iff u \leq F_{\mu_n}(t)$ (menurut kekontinuan kanan $F$ dan kemonotonannya) menunjukkan bahwa $X_n = G_n(U_n)$ terukur dengan $\P(X_n \leq t) = \P(U_n \leq F_{\mu_n}(t)) = F_{\mu_n}(t)$ : jadi berdistribusi $\mu_n$ ; sedangkan kebebasannya diwarisi (sebab fungsi variabel yang bebas, Latihan 22.3). ∎

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

p_n = \prod_{k=1}^{n-1}\Bigl(1 - \frac kN\Bigr),

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

\ln p_n = -\frac{n(n-1)}{2N} + O\Bigl(\frac{n^3}{N^2}\Bigr), \qquad\text{sehingga}\qquad p_n \approx \eu^{-n^2/2N} .

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

22.3 Borel–Cantelli dan hukum nol–satu

Teorema 22.8 (Borel–Cantelli)

Misalkan $(A_n)$ kejadian dan $\limsup A_n = \bigcap_N \bigcup_{n\geq N}A_n$ (“ $A_n$ terjadi tak berhingga kali”).

Jika $\sum\P(A_n) < \infty$ , maka $\P(\limsup A_n) = 0$ .
Jika $\sum\P(A_n) = \infty$ dan $A_n$ saling bebas, maka $\P(\limsup A_n) = 1$ .

Bukti. (1) adalah Latihan 9.4. (2): untuk $N \leq M$ , kebebasan komplemennya (Latihan 22.3) memberikan

\P\Bigl(\bigcap_{n=N}^{M}A_n^c\Bigr) = \prod_{n=N}^M\bigl(1 - \P(A_n)\bigr) \leq \exp\Bigl(-\sum_{n=N}^M\P(A_n)\Bigr) \xrightarrow[M \to \infty]{} 0

(sebab $1 - x \leq \eu^{-x}$ ; dan deretnya divergen). Jadi $\P\bigl(\bigcup_{n\geq N}A_n\bigr) = 1$ bagi setiap $N$ , sedangkan irisan menurun atas $N$ tetap berpeluang $1$ (menurut kekontinuan dari atas, Proposisi 9.6). ∎

Teorema 22.9 (Hukum nol–satu Kolmogorov)

Misalkan $(X_n)$ bebas dan $\mathcal T = \bigcap_N\sigma(X_N, X_{N+1}, \dots)$ merupakan $\sigma$ -aljabar ekor (yakni kejadian yang tak peka terhadap berhingga banyak $X_n$ mana pun: konvergensi $\sum X_n$ , konvergensi $\frac{S_n}n$ , nilai $\limsup$ , …). Maka setiap $T \in \mathcal T$ mempunyai $\P(T) \in \{0, 1\}$ .

Bukti. Tetapkanlah $N$ . Kedua $\sigma$ -aljabar $\sigma(X_1, \dots, X_N)$ dan $\sigma(X_{N+1}, \dots)$ saling bebas: sebab kejadian yang bergantung pada blok saling lepas memfaktor pada $\pi$ -sistem pembangkitnya (yakni silinder $\bigcap_{i\leq N}\{X_i \in B_i\}$ , dan berturut-turut syarat berhingga atas variabel berikutnya), lalu Dynkin (Teorema 9.4, yang diterapkan dua kali, satu sisi setiap kali) memperluas pemfaktorannya. Sedangkan kejadian ekor $T$ terletak di $\sigma(X_{N+1}, \dots)$ bagi setiap $N$ : sehingga $T$ bebas dari setiap $\sigma(X_1, \dots, X_N)$ , jadi bebas dari $\sigma$ -aljabar yang dibangkitkannya, $\sigma(X_1, X_2, \dots)$ (yakni Dynkin sekali lagi: sebab gabungan $\sigma(X_1,\dots,X_N)$ merupakan $\pi$ -sistem yang membangkitkannya). Padahal $T \in \sigma(X_1, X_2, \dots)$ juga: jadi $T$ bebas dari dirinya sendiri, sehingga $\P(T) = \P(T\cap T) = \P(T)^2$ : jadi $\P(T) \in \{0, 1\}$ . ∎

22.4 Jenis konvergensi

Definisi 22.10

Berlaku $X_n \to X$ hampir pasti jika $\P(X_n \to X) = 1$ ; dalam peluang jika $\P(\abs{X_n - X} \geq \varepsilon) \to 0$ bagi setiap $\varepsilon > 0$ ; dan dalam $L^p$ jika $\E\abs{X_n - X}^p \to 0$ .

Proposisi 22.11

(a) konvergensi h.p. mengakibatkan konvergensi dalam peluang; (b) konvergensi $L^p$ mengakibatkan konvergensi dalam peluang; (c) konvergensi dalam peluang mengakibatkan konvergensi h.p. sepanjang sebuah subbarisan; (d) tak ada implikasi lain yang berlaku secara umum.

Bukti. (a) $\P(\abs{X_n - X} \geq \varepsilon) \leq \P\bigl(\sup_{m\geq n}\abs{X_m - X} \geq \varepsilon\bigr) \downarrow \P\bigl(\limsup\{\abs{X_m - X} \geq \varepsilon\}\bigr) = 0$ di bawah konvergensi h.p. (menurut kekontinuan dari atas; sebab kejadian limsupnya mengecualikan konvergensinya). (b) Markov: $\P(\abs{X_n - X} \geq \varepsilon) \leq \varepsilon^{-p}\,\E\abs{X_n - X}^p$ . (c) Pilihlah $n_k$ dengan $\P(\abs{X_{n_k} - X} \geq 2^{-k}) \leq 2^{-k}$ ; lalu Borel–Cantelli (1) membuat $\abs{X_{n_k} - X} < 2^{-k}$ pada akhirnya, secara h.p. (d) Mesin tiknya (Latihan 12.3) pada $(\intcc01, \lambda)$ konvergen dalam $L^1$ dan dalam peluang tetapi tak di mana pun secara titik demi titik; sedangkan $n\mathbf 1_{\intoo0{1/n}} \to 0$ secara h.p. tetapi tidak dalam $L^1$ ; rinciannya dan sisa contoh tandingnya ada di Latihan 22.6. ∎

22.5 Hukum bilangan besar

Sepanjang bagian ini, $(X_n)$ bebas dan berdistribusi sama (i.i.d.), dengan $S_n = X_1 + \dots + X_n$ .

Teorema 22.12 (Hukum lemah bilangan besar)

Jika $X_1 \in L^2$ , dengan $m = \E X_1$ :

\P\Bigl(\Bigl|\frac{S_n}{n} - m\Bigr| \geq \varepsilon\Bigr) \leq \frac{\V(X_1)}{n\,\varepsilon^2} \xrightarrow[n\to\infty]{} 0 :

sehingga $\frac{S_n}n \to m$ dalam peluang (dan dalam $L^2$ ).

Bukti. Berlaku $\E\frac{S_n}n = m$ dan $\V\bigl(\frac{S_n}n\bigr) = \frac{n\V(X_1)}{n^2}$ (Teorema 22.5); lalu Chebyshev. ∎

Teorema 22.13 (Hukum kuat bilangan besar)

Jika $X_1 \in L^1$ , maka

\frac{S_n}{n} \xrightarrow[n\to\infty]{\text{h.p.}} \E[X_1].

Kita buktikan di sini di bawah hipotesis yang lebih kuat $X_1 \in L^4$ ; sedangkan kasus umumnya ( $L^1$ : yakni bukti Etemadi) adalah soal akhir pekannya.

Bukti di bawah $\E X_1^4 < \infty$ . Dengan memusatkannya ( $X_i \mapsto X_i - m$ ), anggaplah $m = 0$ . Lalu uraikan:

\E[S_n^4] = \sum_{i,j,k,l}\E[X_iX_jX_kX_l] = n\,\E[X_1^4] + 3n(n-1)\,\bigl(\E[X_1^2]\bigr)^2 \leq C\,n^2 ,

sebab kebebasan dan pemusatannya membunuh setiap suku yang memuat faktor terpencil ( $\E[X_iX_jX_kX_l] = \E[X_i]\E[\cdots] = 0$ kecuali indeksnya berpasangan: sehingga yang bertahan hanyalah $n$ suku $i=j=k=l$ dan $3n(n-1)$ suku dengan dua pasangan berbeda). Lalu Markov:

\P\Bigl(\Bigl|\frac{S_n}n\Bigr| \geq \varepsilon\Bigr) = \P\bigl(S_n^4 \geq n^4\varepsilon^4\bigr) \leq \frac{Cn^2}{n^4\varepsilon^4} = \frac{C}{\varepsilon^4n^2},

yang terjumlahkan: sehingga Borel–Cantelli (1) memberikan, bagi setiap $\varepsilon$ rasional, bahwa $\abs{S_n/n} < \varepsilon$ pada akhirnya, secara h.p.; lalu mengirisnya atas $\varepsilon \in \Q_+^*$ (yakni terbilang banyak kejadian berpeluang- $1$ ): jadi $S_n/n \to 0$ secara h.p. ∎

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.

Metode 22.15

Urutan kerja bagi pernyataan asimtotik tentang barisan acak: (1) Apakah kejadiannya kejadian ekor? Jika ya, peluangnya $0$ atau $1$ (Teorema 22.9) dan tinggal diputuskan yang mana. (2) Untuk membuktikan pernyataan h.p.: Borel–Cantelli — yakni peluang yang terjumlahkan bagi kejadian yang “buruk”, lewat batas bertipe Markov/Chebyshev atas momen apa pun yang ada; sedangkan kebebasannya hanya diperlukan bagi arah konversnya. (3) Subbarisan + apitan: buktikanlah konvergensinya sepanjang subbarisan yang terkelola, lalu kendalikanlah ayunan di antaranya lewat kemonotonan atau ketaksamaan maksimal — yakni kerangka bukti Etemadi. (4) Untuk limit distribusinya, tunggulah Bab 23.

22.6 Latihan

Latihan 22.1 ★

(a) Misalkan $X$ berfungsi distribusi $F$ yang kontinu dan naik sejati. Tunjukkanlah bahwa $F(X)$ seragam pada $\intcc01$ , dan bahwa $G(U) \sim F$ bagi $U$ yang seragam, dengan $G = F^{-1}$ : yakni simulasi lewat pembalikan. (b) Hitunglah fungsi distribusi dan kepadatan $X^2$ bagi $X$ yang seragam pada $\intcc{-1}1$ , dan bagi $-\frac1\lambda\ln U$ dengan $U$ yang seragam pada $\intoo01$ .

Solusi

Solusi Latihan 22.1.

(a) Untuk $u \in \intoo01$ : $\P(F(X) \leq u) = \P(X \leq F^{-1}(u)) = F(F^{-1}(u)) = u$ (sebab kekontinuan dan kemonotonan sejatinya menjadikan $F$ bijeksi ke $\intoo01$ dengan $\{F(X) \leq u\} = \{X \leq F^{-1}(u)\}$ ): jadi $F(X)$ seragam. Sebaliknya $\P(G(U) \leq t) = \P(U \leq F(t)) = F(t)$ : jadi untuk menyimulasikan sebuah distribusi, terapkanlah fungsi distribusi balikannya pada cuplikan seragam.

(b) Ambillah $Y = X^2$ dengan $X$ seragam pada $\intcc{-1}1$ : bagi $t \in \intcc01$ , $F_Y(t) = \P(-\sqrt t \leq X \leq \sqrt t) = \sqrt t$ : jadi kepadatannya $\frac1{2\sqrt t}\mathbf 1_{\intoo01}$ . Sedangkan $\P\bigl(-\frac1\lambda\ln U \leq t\bigr) = \P(U \geq \eu^{-\lambda t}) = 1 - \eu^{-\lambda t}$ : yakni eksponensial $\mathcal E(\lambda)$ — yakni pembalikan dalam aksi.

Latihan 22.2 ★

(a) Hitunglah rata-rata dan varians distribusi Poisson $\mathcal P(\lambda)$ dan geometrik lewat teorema transfernya. (b) Tunjukkanlah bahwa peubah acak positif $T$ dengan $\P(T > t) > 0$ bagi setiap $t$ memenuhi sifat tanpa ingatan $\P(T > t + s \mid T > t) = \P(T > s)$ bagi setiap $s, t \geq 0$ jika dan hanya jika $T$ eksponensial. (Sebab fungsi kesintasannya memenuhi persamaan fungsional Cauchy; sedangkan kemonotonannya menggantikan kekontinuannya.)

Solusi

Solusi Latihan 22.2.

(a) Poisson: $\E X = \sum_{k\geq0}k\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \lambda$ , $\E[X(X-1)] = \lambda^2$ , sehingga $\V = \lambda^2 + \lambda - \lambda^2 = \lambda$ . Geometrik (dengan $\P(X = k) = p(1-p)^{k-1}$ ): $\E X = \frac1p$ , $\V = \frac{1-p}{p^2}$ (turunkanlah deret geometriknya dua kali).

(b) Fungsi $G(t) = \P(T > t)$ tak naik dengan $G(0^+)\dots$ $G \colon \intco0\infty \to \intoc01$ ; dan ketiadaan ingatannya berbunyi $G(t + s) = G(t)G(s)$ . Maka $G(n t) = G(t)^n$ dan $G(t/n) = G(t)^{1/n}$ : sehingga $G(q) = G(1)^q$ bagi $q \geq 0$ yang rasional; lalu dengan menulis $G(1) = \eu^{-\lambda}$ (dengan $\in \intoo01$ : sebab $G(1) = 1$ akan memaksa $G \equiv 1$ , yang mustahil bagi peubah acak berhingga; sedangkan $G(1) = 0$ terkecualikan oleh hipotesisnya) lalu mengapit sembarang $t$ di antara bilangan rasional (menurut kemonotonannya): $G(t) = \eu^{-\lambda t}$ — yakni distribusi eksponensialnya. Sedangkan konversnya sebuah perhitungan.

Latihan 22.3 ★★

(a) Tunjukkanlah bahwa jika $X_1, \dots, X_n$ bebas dan $f_i$ fungsi Borel, maka $f_i(X_i)$ bebas. (b) Tunjukkanlah bahwa kejadian $A_1, \dots, A_n$ bebas jika dan hanya jika komplemennya bebas, jika dan hanya jika indikator $\mathbf 1_{A_i}$ merupakan peubah acak yang bebas. (c) (Bebas berpasangan itu lebih lemah) Dua koin adil: $A =$ yang pertama gambar, $B =$ yang kedua gambar, $C =$ keduanya sama. Tunjukkanlah bahwa $A, B, C$ bebas berpasangan tetapi tidak bebas.

Solusi

Solusi Latihan 22.3.

(a) Berlaku $\sigma(f_i(X_i)) = f_i(X_i)^{-1}(\mathcal B) \subseteq X_i^{-1}(\mathcal B) = \sigma(X_i)$ (sebab $f_i$ Borel), sedangkan sub- $\sigma$ -aljabar dari $\sigma$ -aljabar yang bebas juga bebas (sebab identitas pendefinisinya berlaku lebih-lebih lagi).

(b) Berlaku $\sigma(A_i) = \{\varnothing, A_i, A_i^c, \Omega\} = \sigma(A_i^c) = \sigma(\mathbf 1_{A_i})$ : sehingga ketiga pernyataannya menegaskan kebebasan $\sigma$ -aljabar yang sama. (Bahwa pemfaktoran atas $A_i$ merambat ke komplemennya adalah argumen $\lambda$ -sistem di dalam kesetaraan Definisi 22.4 — atau inklusi-eksklusi langsung.)

(c) Berlaku $\P(A) = \P(B) = \P(C) = \frac12$ ; sedangkan $A\cap B = A\cap C = B\cap C$ pada pasangannya: sebab setiap irisannya adalah “keduanya gambar” atau yang serupa, berpeluang $\frac14$ : jadi bebas berpasangan. Padahal $\P(A\cap B\cap C) = \P(\text{GG}) = \frac14 \neq \frac18$ : jadi tidak bebas — sebab $C$ ditentukan oleh $A$ dan $B$ .

Latihan 22.4 ★★

(a) (Monyet tak berhingga) Barisan i.i.d. ketukan tombol seragam pada abjad berhingga secara h.p. memuat setiap teks berhingga tak berhingga kali: buktikanlah dengan Borel–Cantelli (2) pada blok yang saling lepas. (b) (Rentetan) Bagi bit adil i.i.d., misalkan $R_n$ panjang rentetan angka satu yang mulai di posisi $n$ . Tunjukkanlah bahwa secara h.p. $R_n \geq (1+\varepsilon)\log_2n$ hanya berhingga kali, sedangkan $R_n \geq \log_2 n$ tak berhingga kali (lewat kedua paruh Borel–Cantelli; dan untuk yang kedua, berpindahlah ke blok saling lepas demi memperoleh kebebasan): sehingga rentetan terpanjang pada $n$ digit pertamanya tumbuh seperti $\log_2n$ .

Solusi

Solusi Latihan 22.4.

(a) Misalkan teks $T$ berpanjang $L$ dan $q = a^{-L}$ (dengan $a$ sebagai ukuran abjadnya). Kejadian $E_k = \{$ posisi $kL+1, \dots, (k+1)L$ mengeja $T\}$ saling bebas (sebab blok huruf i.i.d. yang saling lepas), masing-masing berpeluang $q > 0$ : jadi $\sum\P(E_k) = \infty$ , sehingga Borel–Cantelli (2) memberikan tak berhingga banyak kemunculan secara h.p.

(b) Untuk yang atas: $\P\bigl(R_n \geq (1+\varepsilon)\log_2n\bigr) \leq 2^{-(1+\varepsilon)\log_2n} = n^{-(1+\varepsilon)}$ , yang terjumlahkan: jadi menurut Borel–Cantelli (1), secara h.p. hanya berhingga banyak $n$ semacam itu. Untuk yang bawah: kemaslah blok saling lepas — yang ke- $j$ berpanjang $\ell_j = \lceil\log_2s_j\rceil$ dan mulai di $s_j = \sum_{i<j}\ell_i$ ; lalu kejadian “blok $j$ seluruhnya satu” saling bebas dengan peluang $2^{-\ell_j} \asymp \frac1{s_j} \asymp \frac1{j\log_2 j}$ , yang jumlahnya divergen: sehingga Borel–Cantelli (2) memberikan tak berhingga banyak blok seluruhnya satu, yakni $R_{s_j} \geq \log_2 s_j$ tak berhingga kali. Bersama-sama: panjang rentetan maksimal pada $n$ digit pertamanya adalah $(1 + o(1))\log_2n$ secara h.p.

Latihan 22.5 ★★

Misalkan $(X_n)$ bebas. (a) Tunjukkanlah bahwa jari-jari konvergensi $\sum X_n z^n$ merupakan konstanta h.p. (mungkin $0$ atau $\infty$ ). (b) Tunjukkanlah bahwa $\P(\sum X_n \text{ konvergen}) \in \{0, 1\}$ dan $\P(S_n/n \to m) \in \{0,1\}$ . (c) Berikanlah kejadian tentang $(X_n)$ yang bukan kejadian ekor, lalu periksalah bahwa hukum nol–satunya bisa gagal padanya.

Solusi

Solusi Latihan 22.5.

(a) Nilai $R = \bigl(\limsup\abs{X_n}^{1/n}\bigr)^{-1}$ tak berubah jika berhingga banyak $X_n$ diubah: sehingga bagi setiap $N$ , $R$ terukur- $\sigma(X_N, X_{N+1}, \dots)$ , yakni terukur-ekor. Maka setiap kejadian $\{R \leq c\}$ berpeluang $0$ atau $1$ (Teorema 22.9), sehingga fungsi distribusi $R$ hanya mengambil nilai $0, 1$ : jadi ia melompat pada satu titik $c_0 \in \intcc0{+\infty}$ , dan $R = c_0$ secara h.p.

(b) Konvergensi $\sum X_n$ dan konvergensi $\frac{S_n}n$ tak peka terhadap perubahan berhingga banyak sukunya (untuk yang kedua: sebab suku yang diubah menyumbang $O(1/n) \to 0$ ): jadi keduanya kejadian ekor; lalu hukum nol–satunya berlaku.

(c) Kejadian $\{X_1 > 0\}$ bergantung pada $X_1$ : bagi tanda i.i.d. (dengan $\P(X_1 = \pm1) = \frac12$ ), peluangnya $\frac12 \notin \{0,1\}$ — dan tak ada pertentangan, sebab ia bukan kejadian ekor.

Latihan 22.6 ★★

Pada $(\intcc01, \lambda)$ , tunjukkanlah — beserta buktinya — peubah acak sedemikian sehingga: (a) $X_n \to 0$ dalam peluang dan dalam setiap $L^p$ , tetapi tak di mana pun secara h.p.; (b) $X_n \to 0$ secara h.p. tetapi tak dalam $L^p$ mana pun; (c) $X_n \to 0$ dalam $L^1$ tetapi tak dalam $L^2$ ; (d) lalu tunjukkanlah: jika $X_n \to X$ dalam peluang dan $\abs{X_n} \leq Y \in L^1$ , maka $X_n \to X$ dalam $L^1$ (lewat subbarisan + konvergensi terdominasi + kiat subsubbarisannya).

Solusi

Solusi Latihan 22.6.

Bekerjalah pada $(\intcc01, \lambda)$ . (a) Mesin tiknya $\mathbf 1_{I_n}$ (Latihan 12.3): $\norm{X_n}_p^p = \lambda(I_n) \to 0$ (bagi setiap $p < \infty$ ), sehingga juga dalam peluang; padahal pada setiap $\omega$ nilai $0$ dan $1$ keduanya berulang: jadi tak ada konvergensi titik demi titik di mana pun. (b) Berlaku $X_n = n\mathbf 1_{\intoo0{1/n}} \to 0$ di luar $0$ , tetapi $\norm{X_n}_p \geq n^{1 - 1/p} \geq 1$ . (c) Ambillah $X_n = \sqrt n\,\mathbf 1_{\intoo0{1/n}}$ : maka $\E\abs{X_n} = n^{-1/2} \to 0$ , sedangkan $\E X_n^2 = 1$ . (d) Dari sembarang subbarisan sarikanlah (menurut konvergensi dalam peluangnya) subbarisan lebih lanjut yang konvergen secara h.p. (Proposisi 22.11(c)); lalu konvergensi terdominasinya memberikan konvergensi $L^1$ sepanjangnya, dengan limit yang sama $X$ . Jadi setiap subbarisan barisan numerik $\E\abs{X_n - X}$ mempunyai subsubbarisan yang menuju $0$ : sehingga seluruh barisannya menuju $0$ .

Latihan 22.7 ★★

Sebuah jajak pendapat menaksir proporsi $p$ yang tak diketahui lewat frekuensi empiris $\hat p_n$ atas $n$ penarikan yang bebas. (a) Chebyshev: tunjukkanlah $\P(\abs{\hat p_n - p} \geq \varepsilon) \leq \frac1{4n\varepsilon^2}$ (pakailah $p(1-p) \leq \frac14$ ). (b) Berapa banyak penarikan yang menjamin galat $\leq 3\%$ dengan peluang $\geq 95\%$ menurut batas ini? (Jawaban sebenarnya, lewat Bab 23, kira-kira $1070$ : jadi Chebyshev jujur tetapi kasar.)

Solusi

Solusi Latihan 22.7.

(a) Berlaku $\hat p_n = \frac{S_n}n$ dengan $S_n$ yang binomial: sehingga $\V(\hat p_n) = \frac{p(1-p)}n \leq \frac1{4n}$ , lalu Chebyshev (Proposisi 22.3) memberikan batasnya. (b) Selesaikanlah $\frac1{4n(0.03)^2} \leq 0.05$ : $n \geq \frac{1}{4\cdot0.0009\cdot0.05} \approx 5556$ . Sedangkan teorema limit pusatnya akan membenarkan $n \approx 1070$ bagi jaminan yang sama: jadi Chebyshev membayar keumumannya dengan faktor $\approx 5$ .

Latihan 22.8 ★★★

(Bernstein) Untuk $f \in \mathcal C(\intcc01)$ definisikanlah polinomial Bernstein $B_nf(x) = \sum_{k=0}^n\binom nkx^k(1-x)^{n-k}f\bigl(\frac kn\bigr)$ . (a) Kenalilah $B_nf(x) = \E\bigl[f\bigl(\frac {S_n}n\bigr)\bigr]$ bagi $S_n$ yang binomial $\mathcal B(n, x)$ . (b) Buktikanlah $B_nf \to f$ secara seragam pada $\intcc01$ : belahlah pada $\{\abs{\frac{S_n}n - x} \leq \delta\}$ dan komplemennya, dengan memakai kekontinuan seragam dan Chebyshev beserta batas seragam $\V(\frac{S_n}n) \leq \frac1{4n}$ . (c) Simpulkanlah: yakni bukti kedua yang bersifat peluang bagi teorema hampiran Weierstrass (Akibat 7.16), dengan laju eksplisit $\norm{B_nf - f}_\infty \leq \frac32\,\omega_f(n^{-1/2})$ bagi modulus kekontinuan $\omega_f$ — buktikanlah setidaknya bentuk $O(\omega_f(n^{-1/2}))$ -nya.

Solusi

Solusi Latihan 22.8.

(a) Jika $S_n \sim \mathcal B(n, x)$ , maka teorema transfernya memberikan $\E\bigl[f(\frac{S_n}n)\bigr] = \sum_k\binom nkx^k(1-x)^{n-k}f(\frac kn) = B_nf(x)$ .

(b)–(c) Misalkan $\omega = \omega_f$ modulus kekontinuannya (dengan $\abs{f(u) - f(v)} \leq \omega(\abs{u - v})$ , dan $\omega(c \delta) \leq (1 + c)\,\omega(\delta)$ lewat perantaian langkahnya). Maka, bagi sembarang $\delta > 0$ ,

\abs{f(u) - f(x)} \leq \Bigl(1 + \frac{(u - x)^2}{\delta^2}\Bigr)\omega(\delta)

(jika $\abs{u - x} \leq \delta$ , jelas; sedangkan jika tidak $\omega(\abs{u-x}) \leq (1 + \frac{\abs{u-x}}\delta) \omega(\delta) \leq (1 + \frac{(u-x)^2}{\delta^2}) \omega(\delta)$ ). Lalu ambillah nilai harapannya di $u = \frac{S_n}n$ :

\abs{B_nf(x) - f(x)} \leq \Bigl(1 + \frac{\V(S_n/n)}{\delta^2}\Bigr)\omega(\delta) \leq \Bigl(1 + \frac{1}{4n\delta^2}\Bigr)\omega(\delta) ;

dengan $\delta = n^{-1/2}$ : $\norm{B_nf - f}_\infty \leq \frac54\,\omega\bigl(n^{-1/2}\bigr) \leq \frac32\,\omega\bigl(n^{-1/2}\bigr) \to 0$ (menurut kekontinuan seragamnya pada kompak): yakni teorema Weierstrass yang bersifat peluang, dengan laju yang eksplisit dan seragam.

Latihan 22.9 ★★★

(Pengumpul kupon) Kartu dari $n$ jenis ditarik secara seragam dengan pengembalian; misalkan $T_n$ banyaknya penarikan sampai semua jenisnya terlihat. (a) Tulislah $T_n = \sum_{k=1}^{n}\tau_k$ dengan $\tau_k$ yang geometrik berparameter $\frac{n - k + 1}n$ , dan $\tau_k$ yang bebas, lalu simpulkanlah $\E T_n = n\,H_n \sim n\ln n$ (dengan $H_n$ bilangan harmoniknya) dan $\V(T_n) \leq \frac{\pi^2}6n^2$ . (b) Chebyshev: $\frac{T_n}{n\ln n} \to 1$ dalam peluang. (c) Pertajamlah dengan Borel–Cantelli: tunjukkanlah secara langsung $\P(T_n > \beta n\ln n) \leq n^{1 - \beta}$ bagi $\beta > 1$ (lewat batas gabungan atas kejadian bahwa suatu jenis terlewat setelah $\beta n\ln n$ penarikan, dengan memakai $1 - x \leq \eu^{-x}$ ), lalu simpulkanlah bahwa sepanjang $n = 2^m$ , secara h.p. $T_n \leq \beta n\ln n$ pada akhirnya, bagi setiap $\beta > 2$ .

Solusi

Solusi Latihan 22.9.

(a) Setelah $k - 1$ jenis terkumpul, setiap penarikan bersifat baru dengan peluang $p_k = \frac{n-k+1}n$ : jadi $\tau_k$ geometrik $(p_k)$ , dan $\tau_k$ saling bebas (sebab penarikannya bebas). Lalu jumlahnya: $\E T_n = \sum_k\frac n{n-k+1} = nH_n \sim n\ln n$ ; $\V(T_n) = \sum\frac{1 - p_k}{p_k^2} \leq n^2\sum_{j=1}^n\frac1{j^2} \leq \frac{\pi^2}6n^2$ .

(b) Chebyshev: $\P\bigl(\abs{T_n - nH_n} \geq \varepsilon n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2n} \to 0$ , sedangkan $\frac{nH_n}{n\ln n} \to 1$ : sehingga $\frac{T_n}{n\ln n} \to 1$ dalam peluang.

(c) Lewat batas gabungannya: $T_n > t$ berarti suatu jenis tak terlihat setelah $\lceil t\rceil$ penarikan, sehingga $\P(T_n > t) \leq n(1 - \frac1n)^{t} \leq n\,\eu^{-t/n}$ ; lalu di $t = \beta n\ln n$ : $\leq n^{1 - \beta}$ . Untuk $\beta > 1$ , $\sum_m 2^{m(1-\beta)} < \infty$ : sehingga Borel–Cantelli memberikan, sepanjang $n = 2^m$ , secara h.p. $T_n \leq \beta n\ln n$ pada akhirnya — khususnya bagi setiap $\beta > 2$ seperti yang dinyatakan (dan sembarang $\beta > 1$ berhasil sepanjang subbarisannya).

Latihan 22.10 ★★

Dengan memakai konstruksi digitnya (Teorema 22.6): (a) periksalah lewat perhitungan langsung bahwa $U = \sum b_{2k}2^{-k}$ (yakni digit berindeks genap milik $\omega$ yang seragam) bersifat seragam dan bebas dari $V = \sum b_{2k-1}2^{-k}$ ; (b) simpulkanlah adanya bijeksi terukur sampai himpunan nol antara $\intcc01$ dan $\intcc01^2$ yang mengawetkan ukuran, lalu berilah komentar: bahwa satu bilangan acak seragam memuat dua (bahkan terbilang banyak) bilangan bebas — bandingkanlah dengan kurva Peano (Soal 6.1), yang mencapai kesurjektifan tetapi tidak pengawetan ukuran ataupun keinjektifan.

Solusi

Solusi Latihan 22.10.

(a) Digit berindeks genap $(b_{2k})_k$ merupakan bit adil i.i.d. (yakni subkeluarga keluarga digitnya yang bebas), sehingga $U = \sum_kb_{2k}2^{-k}$ memberi setiap selang diadik peluangnya yang benar (seperti pada Teorema 22.6): jadi seragam; demikian pula $V$ ; sedangkan $(U, V)$ bergantung pada blok digit yang saling lepas: jadi bebas (lewat pemfaktoran pada persegi panjang diadiknya, lalu Dynkin).

(b) Pemetaan $\Phi(\omega) = (U(\omega), V(\omega))$ terukur dengan $\Phi_*\lambda = \lambda\otimes\lambda = \lambda_2$ (menurut kesamaannya pada persegi panjang diadik + ketunggalannya). Lalu menyelang-nyelingkan digitnya mendefinisikan sebuah balikan yang terdefinisi di luar himpunan (nol) berisi bilangan rasional diadik pada salah satu faktornya: yakni bijeksi yang mengawetkan ukuran antara himpunan bagian berukuran penuh $\intcc01$ dan $\intcc01^2$ . Bandingkanlah dengan Peano (Soal 6.1): sebab kekontinuannya memaksa kesurjektifan tanpa keinjektifan; sedangkan menukar kekontinuan dengan sekadar keterukuran membeli isomorfisma-ukuran — jadi dimensi tak terlihat oleh teori ukuran, tetapi terlihat oleh topologi.

Latihan 22.11 ★★

(Rekor) Misalkan $(X_n)_{n\geq1}$ i.i.d. dengan fungsi distribusi yang kontinu, dan katakanlah sebuah rekor terjadi pada waktu $n$ jika $X_n > \max(X_1, \dots, X_{n-1})$ (dan waktu $1$ adalah rekor). Misalkan $R_n$ indikator rekornya. (a) Tunjukkanlah $\P(R_n = 1) = \frac1n$ (sebab menurut kesetangkupannya, masing-masing dari $n!$ pengurutan $X_1, \dots, X_n$ sama mungkinnya sedangkan seri berpeluang $0$ ). (b) Tunjukkanlah bahwa $R_n$ bersifat bebas (cacahlah pengurutan yang cocok dengan posisi rekor yang ditentukan, atau berargumenlah bahwa urutan relatif $X_1, \dots, X_{n-1}$ bersifat bebas dari peringkat $X_n$ di antaranya). (c) Simpulkanlah dari Borel–Cantelli (Teorema 22.8, kedua paruhnya) bahwa tak berhingga banyak rekor terjadi secara h.p., tetapi rekor pada waktu berurutan $n, n+1$ terjadi tak berhingga kali dengan peluang — putuskanlah yang mana! — lalu hitunglah $\sum_n\P(R_n = 1, R_{n+1} = 1)$ .

Solusi

Solusi Latihan 22.11.

(a) Kekontinuan distribusinya menjadikan seri sebagai kejadian nol (seperti pada argumen statistik terurut di babnya), sedangkan $n!$ pengurutan relatif $(X_1, \dots, X_n)$ bersifat tertukarkan, sehingga sama mungkinnya. Lalu $R_n = 1$ berarti maksimumnya duduk pada posisi terakhir: jadi berpeluang $\frac{(n-1)!}{n!} = \frac1n$ .

(b) Tetapkanlah $n$ lalu syaratkan pada urutan relatif $X_1, \dots, X_{n-1}$ : menyisipkan $X_n$ ke $n$ celah peringkat yang mungkin bersifat seragam dan bebas dari urutan itu (menurut ketertukaran $n$ -tupelnya). Karena itu $R_n$ (yakni kejadian “ $X_n$ menempati celah teratas”) bebas dari seluruh riwayat rekornya $(R_1, \dots, R_{n-1})$ , yang merupakan fungsi urutan relatif $n - 1$ variabel pertamanya. Lalu induksinya memberikan kebebasan penuh dengan $\P(R_n = 1) = \frac1n$ .

(c) Berlaku $\sum\P(R_n = 1) = \sum\frac1n = \infty$ beserta kebebasannya: sehingga paruh kedua Borel–Cantelli memberikan rekor tak berhingga kali secara h.p. (rekornya tak pernah berhenti — tetapi menipis secara logaritmik: $\E[\#\text{rekor} \leq n] = H_n \approx \ln n$ ). Untuk rekor berurutan: $\P(R_n = R_{n+1} = 1) = \frac1{n(n+1)}$ (menurut kebebasannya), dan

\sum_n\frac1{n(n+1)} = \sum_n\Bigl(\frac1n - \frac1{n+1}\Bigr) = 1 < \infty :

sehingga paruh pertama Borel–Cantelli berlaku — jadi hanya berhingga banyak pasangan rekor berurutan yang terjadi, secara h.p.

Latihan 22.12 ★★

(Rentetan gambar terpanjang) Lemparkanlah koin adil tak berhingga kali, lalu misalkan $L_n$ panjang rentetan terpanjang sisi gambar yang berurutan di dalam $n$ lemparan pertamanya. (a) Tunjukkanlah bahwa bagi setiap $\varepsilon > 0$ , secara h.p. $L_n \leq (1 + \varepsilon)\log_2n$ pada akhirnya (sebab peluang bahwa suatu rentetan berpanjang $\ell$ mulai di antara $n$ lemparan pertamanya paling banyak $n2^{-\ell}$ ; lalu Borel–Cantelli sepanjang $n = 2^k$ ). (b) Tunjukkanlah bahwa secara h.p. $L_n \geq (1 - \varepsilon)\log_2n$ pada akhirnya (potonglah $n$ lemparan pertamanya menjadi $\lfloor n/\ell\rfloor$ blok saling lepas berpanjang $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ ; blok itu saling bebas, masing-masing seluruhnya gambar dengan peluang $2^{-\ell}$ , sedangkan peluang bahwa tak satu pun seluruhnya gambar paling banyak $\exp(-n2^{-\ell}/\ell)$ ; lalu jumlahkanlah sepanjang $n = 2^k$ lagi). (c) Simpulkanlah $\frac{L_n}{\log_2n} \to 1$ secara h.p.: bahwa dalam sejuta lemparan adil kita patut menantikan rentetan sekitar $20$ gambar — dan sekumpulan data tanpa itu boleh jadi dikarang.

Solusi

Solusi Latihan 22.12.

(a) Sebuah rentetan berpanjang $\ell$ yang mulai di posisi $i \leq n$ berpeluang $2^{-\ell}$ ; lalu lewat batas gabungannya: $\P(L_n \geq \ell) \leq n2^{-\ell}$ . Dengan $\ell_n = (1 + \varepsilon)\log_2n$ : $\P(L_n \geq \ell_n) \leq n^{-\varepsilon}$ . Lalu sepanjang $n = 2^k$ : $\sum_k2^{-k\varepsilon} < \infty$ , sehingga secara h.p. $L_{2^k} < (1+\varepsilon)k$ pada akhirnya (menurut Borel–Cantelli); sedangkan bagi $n$ yang umum ambillah $2^{k-1} < n \leq 2^k$ lalu pakailah kemonotonan $L_n$ ditambah $\log_22^{k-1} \leq \log_2n$ : $L_n \leq L_{2^k} < (1 + \varepsilon)k \leq (1 + \varepsilon)\frac{k}{k-1} \log_2n$ , dan faktor tambahannya terserap dengan sedikit membesarkan $\varepsilon$ .

(b) Dengan $\ell = \lceil(1 - \varepsilon)\log_2n\rceil$ dan $m = \lfloor n/\ell\rfloor$ blok saling lepas: bloknya saling bebas, masing-masing seluruhnya gambar dengan peluang $2^{-\ell} \geq n^{-(1-\varepsilon)}/2$ , sehingga

\P(L_n < \ell) \leq \bigl(1 - 2^{-\ell}\bigr)^{m} \leq \exp\bigl(-m2^{-\ell}\bigr) \leq \exp\Bigl(-c\,\frac{n^{\varepsilon}}{\log_2n}\Bigr)

bagi sebuah konstanta $c > 0$ dan $n$ yang besar. Peluang ini terjumlahkan sepanjang $n = 2^k$ (bahkan sepanjang semua $n$ ): sehingga Borel–Cantelli memberikan secara h.p. $L_n \geq (1 - \varepsilon)\log_2n$ pada akhirnya (sedangkan kemonotonannya mengisi di antara $2^k$ seperti pada (a), tanpa bahaya).

(c) Kedua batasnya sepanjang barisan $\varepsilon = \frac1j$ , lalu dengan mengiriskan terbilang banyak kejadian berukuran penuh: $\frac{L_n}{\log_2n} \to 1$ secara h.p. Untuk $n = 10^6$ : $\log_2n \approx 19.9$ — jadi rentetan $\approx 20$ gambar bukanlah anomali yang mencurigakan melainkan kepastian matematis, sedangkan ketiadaannya justru bukti bahwa manusia memalsukan “keacakan” (sebab manusia jarang berani menulis lebih dari $5$ atau $6$ gambar berturut-turut).

22.7 Soal: bukti Etemadi bagi hukum kuatnya

Soal 22.1

Soal akhir pekan — hukum kuat bilangan besar bagi variabel i.i.d. yang terintegralkan

Hukum kuat Kolmogorov — $\frac{S_n}n \to \E X_1$ secara h.p. bagi $X_n \in L^1$ yang i.i.d. — lama hanya mempunyai bukti yang berbelit; lalu pada 1981 N. Etemadi menemukan satu bukti yang sangat hemat, tanpa memakai apa pun di luar bab ini (bahkan dengan melemahkan kebebasannya menjadi kebebasan berpasangan). Kita ikuti buktinya. Misalkan $(X_n)$ bebas berpasangan, berdistribusi identik, dan terintegralkan; dengan $m = \E X_1$ , $S_n = X_1 + \dots + X_n$ .

Bagian I — Reduksinya.

Tunjukkanlah bahwa cukup ditangani $X_n \geq 0$ (belahlah $X_n = X_n^+ - X_n^-$ : lalu periksalah bahwa kedua paruhnya kembali bebas berpasangan, i.i.d., dan terintegralkan). Selanjutnya anggaplah $X_n \geq 0$ .
(Pemenggalan) Misalkan $Y_n = X_n\,\mathbf 1_{X_n \leq n}$ dan $S_n^* = Y_1 + \dots + Y_n$ . Tunjukkanlah

$\sum_{n\geq1}\P(X_n \neq Y_n) = \sum_{n\geq1}\P(X_1 > n) \leq \E[X_1] < \infty$

(Latihan 11.3), lalu simpulkanlah lewat Borel–Cantelli bahwa $\frac{S_n - S_n^*}{n} \to 0$ secara h.p.: sehingga cukup dibuktikan $\frac{S^*_n}n \to m$ secara h.p.
Tunjukkanlah $\E Y_n = \E\bigl[X_1\mathbf 1_{X_1\leq n}\bigr] \to m$ (menurut konvergensi monoton), sehingga $\frac1n\sum_{k\leq n}\E Y_k \to m$ (Cesàro): jadi cukup dibuktikan $\frac{S_n^* - \E S_n^*}{n} \to 0$ secara h.p.

Bagian II — Taksiran variansnya.

Tunjukkanlah

$\V(Y_n) \leq \E[Y_n^2] = \E\bigl[X_1^2\,\mathbf 1_{X_1 \leq n}\bigr]$

lalu, dengan memakai kue berlapisnya (Proposisi 11.8), batas kuncinya

$\sum_{n\geq1}\frac{\V(Y_n)}{n^2} \leq \sum_{n\geq1}\frac1{n^2}\, \E\bigl[X_1^2\mathbf 1_{X_1\leq n}\bigr] \leq C\,\E[X_1] < \infty$

(tukarlah jumlahnya dengan nilai harapannya — yakni Tonelli bagi deret — lalu batasilah $\sum_{n \geq x}\frac1{n^2} \leq \frac2{\max(x,1)}$ bagi taksiran dalamnya $x^2\sum_{n\geq x}n^{-2} \leq 2x$ ).

Bagian III — Konvergensi sepanjang subbarisan geometrik. Tetapkanlah $\alpha > 1$ lalu misalkan $k_j = \lfloor\alpha^j\rfloor$ .

Dengan memakai kebebasan berpasangannya (sebab variansnya menjumlah, Teorema 22.5 — periksalah bahwa keaditifan variansnya hanya memerlukan kebebasan berpasangan) dan Chebyshev, tunjukkanlah bagi setiap $\varepsilon > 0$ :

$\sum_{j\geq1}\P\Bigl(\Bigl| \frac{S^*_{k_j} - \E S^*_{k_j}}{k_j}\Bigr| \geq \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j\geq1}\frac1{k_j^2} \sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_{n\geq1}\V(Y_n) \sum_{j\,:\,k_j\geq n}\frac1{k_j^2} .$
Tunjukkanlah $\sum_{j : k_j \geq n}k_j^{-2} \leq \frac{C_\alpha}{n^2}$ (lewat deret geometrik; dan waspadalah pada fungsi lantainya: yakni kehati-hatian bertipe $k_j \geq \frac{\alpha^j}2$ bagi $\alpha^j \geq 2$ ), lalu simpulkanlah dengan pertanyaan 4 dan Borel–Cantelli:

$\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \xrightarrow[j\to\infty]{\text{h.p.}} 0, \qquad\text{sehingga}\qquad \frac{S^*_{k_j}}{k_j} \to m \ \text{h.p.}$

Bagian IV — Apitan dan kesimpulannya.

Untuk $k_j \leq n \leq k_{j+1}$ , pakailah kemonotonan $S^*_n$ (sebab sukunya tak negatif!) untuk menunjukkan

$\frac{k_j}{k_{j+1}}\,\frac{S^*_{k_j}}{k_j} \;\leq\; \frac{S^*_n}{n} \;\leq\; \frac{k_{j+1}}{k_j}\,\frac{S^*_{k_{j+1}}}{k_{j+1}},$

lalu simpulkanlah, secara h.p.:

$\frac m\alpha \leq \liminf\frac{S^*_n}n \leq \limsup\frac{S^*_n}n \leq \alpha\,m .$
Biarkanlah $\alpha \downarrow 1$ sepanjang sebuah barisan lalu simpulkanlah $\frac{S_n^*}n \to m$ secara h.p., sehingga (menurut Bagian I) hukum kuat bilangan besar:

$\boxed{\ \frac{S_n}{n} \xrightarrow[n\to\infty]{\text{h.p.}} \E[X_1].\ }$
Di manakah persisnya kebebasan berpasangan (alih-alih kebebasan penuh) sudah mencukupi? Daftarkanlah ketiga tempat yang hipotesis bertipe kebebasan dipanggil di sana.

Bagian V — Dividennya.

(Bilangan normal Borel) Tunjukkanlah bahwa menurut $\lambda$ , hampir setiap $x \in \intcc01$ bersifat normal pada setiap basis $b \geq 2$ : yakni setiap digit $0, \dots, b-1$ muncul dengan frekuensi asimtotik $\frac1b$ (tetapkanlah $b$ dan sebuah digit, lalu terapkan hukum kuatnya pada variabel indikatornya — benarkanlah bahwa digit basis- $b$ sebuah variabel seragam bersifat seragam i.i.d. pada $\{0,\dots,b-1\}$ seperti pada Teorema 22.6 — lalu iriskanlah terbilang banyak kejadian berpeluang satu itu). Tunjukkanlah satu bilangan tak normal yang eksplisit, lalu renungkanlah: bahwa teoremanya menegaskan kenormalan hampir semua bilangan, padahal membuktikan kenormalan $\sqrt2$ atau $\pi$ tetap terbuka.
(Monte Carlo, terjamin) Benarkanlah selengkapnya metode Contoh 22.14(b) bagi $g \in L^1(\intcc01^d)$ : bangunlah cuplikan seragam i.i.d. pada $\intcc01^d$ dari Teorema 22.6 dan Latihan 22.10, lalu nyatakanlah apa yang diberikan hukum kuatnya.

Bagian VI — Apa yang dibeli kebebasan penuh: ketaksamaan maksimal dan deret acak. Etemadi hanya membelanjakan kebebasan berpasangan; sedangkan bagian sisanya memanfaatkan versi penuhnya (yang bersama). Misalkan $(Z_n)$ variabel $L^2$ terpusat yang bebas dan $S_k = Z_1 + \dots + Z_k$ (yakni notasi baru, yang tak berkaitan dengan $X_n$ di atas).

(Ketaksamaan maksimal Kolmogorov) Untuk $\varepsilon > 0$ buktikanlah

$\P\Bigl(\max_{1\leq k\leq n}\abs{S_k} \geq \varepsilon\Bigr) \;\leq\; \frac1{\varepsilon^2}\sum_{k=1}^n\V(Z_k) :$

Ongkos Chebyshev membeli maksimumnya (partisikanlah kejadiannya menurut indeks pertama $k$ yang $\abs{S_k} \geq \varepsilon$ ; lalu pada keping itu tulislah $S_n^2 \geq S_k^2 + 2S_k(S_n - S_k)$ dan pakailah kebebasan koalisi $(Z_1, \dots, Z_k)$ dan $(Z_{k+1}, \dots, Z_n)$ , Teorema 22.5). Tunjukkanlah langkah yang kebebasan berpasangannya tak lagi mencukupi di sana.
(Teorema satu deret Khinchin–Kolmogorov) Simpulkanlah: bahwa jika $\sum_n\V(Z_n) < \infty$ , maka $\sum_nZ_n$ konvergen hampir pasti (tunjukkanlah bahwa secara h.p. jumlah parsialnya membentuk barisan Cauchy: biarkanlah $m \to \infty$ pada ketaksamaan maksimal yang diterapkan pada $Z_{N+1}, \dots, Z_{N+m}$ , lalu biarkan $N \to \infty$ ).
(Deret Rademacher) Misalkan $(\varepsilon_n)$ tanda i.i.d., dengan $\P(\varepsilon_n = \pm1) = \frac12$ (Teorema 22.6), dan misalkan $(x_n)$ bilangan real. Tunjukkanlah bahwa $\sum_nx_n\varepsilon_n$ konvergen secara h.p. begitu $\sum_nx_n^2 < \infty$ ; tunjukkanlah pula bahwa, apa pun $(x_n)$ -nya, peluang bahwa $\sum_nx_n\varepsilon_n$ konvergen adalah $0$ atau $1$ (Teorema 22.9).
Konversnya, secara elementer. Tetapkanlah $T_n = \sum_{k\leq n}x_k\varepsilon_k$ dan $s_n^2 = \sum_{k\leq n}x_k^2$ , lalu andaikanlah $s_n \to \infty$ . (a) Buktikanlah ketaksamaan Paley–Zygmund: bahwa bagi $Z \geq 0$ dengan $\E Z^2 < \infty$ dan $0 < \theta < 1$ ,

$\P\bigl(Z > \theta\,\E Z\bigr) \;\geq\; (1 - \theta)^2\,\frac{(\E Z)^2}{\E Z^2}$

(belahlah $\E Z$ pada aras $\theta\E Z$ lalu terapkanlah Cauchy–Schwarz pada keping atasnya). (b) Tunjukkanlah $\E T_n^4 \leq 3s_n^4$ . (c) Simpulkanlah $\P\bigl(\abs{T_n} > \frac{s_n}2\bigr) \geq \frac3{16}$ lalu simpulkanlah bahwa $\sum_nx_n\varepsilon_n$ divergen secara h.p.; sehingga dikotominya

$\sum_nx_n\varepsilon_n\ \text{konvergen h.p.} \iff \sum_nx_n^2 < \infty .$
(Deret harmonik acak) Simpulkanlah bahwa $\sum_n\frac{\varepsilon_n}{n^s}$ konvergen secara h.p. jika dan hanya jika $s > \frac12$ . Untuk $\frac12 < s \leq 1$ deretnya konvergen secara h.p. padahal $\sum_nn^{-s} = \infty$ : sebab tanda acak menghasilkan peniadaan sekuat akar kuadrat — bandingkanlah dengan deret berselang-seling $\sum_n\frac{(-1)^n}{n^s}$ , yang konvergen bagi setiap $s > 0$ .

Bagian VII — Pemusatan: ketaksamaan Hoeffding. Hukum kuatnya mengatakan $\frac{S_n}n \to m$ ; sedangkan ketaksamaan pemusatan mengatakan betapa tak mungkinnya sebuah simpangan pada setiap $n$ yang tetap.

(Lema Hoeffding) (a) Tunjukkanlah $\cosh\lambda \leq \eu^{\lambda^2/2}$ bagi setiap $\lambda \in \R$ , dengan membandingkan kedua deretnya suku demi suku. (b) Misalkan $Z$ terpusat dengan $a \leq Z \leq b$ , $a < b$ . Tunjukkanlah

$\E\,\eu^{\lambda Z} \leq \exp\Bigl(\frac{\lambda^2(b - a)^2}8\Bigr)$

(batasilah $\eu^{\lambda z}$ pada $\intcc ab$ oleh talinya, ambillah nilai harapannya, lalu pelajarilah $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ dengan $p = \frac{-a}{b-a}$ dan $t = \lambda(b - a)$ : tunjukkanlah $\varphi(0) = \varphi'(0) = 0$ dan $\varphi'' \leq \frac14$ ).
(Ketaksamaan Hoeffding) Misalkan $X_1, \dots, X_n$ bebas dengan $a_i \leq X_i \leq b_i$ dan $S_n = X_1 + \dots + X_n$ . Buktikanlah, bagi $t > 0$ ,

$\P\bigl(S_n - \E S_n \geq t\bigr) \leq \exp\Bigl(\frac{-2t^2}{\sum_{i=1}^n(b_i - a_i)^2}\Bigr),$

beserta batas yang sama bagi ekor bawahnya (lewat Chebyshev eksponensial: batasilah $\E\,\eu^{\lambda(S_n - \E S_n)}$ dengan memakai kebebasannya dan pertanyaan 17, lalu optimumkanlah atas $\lambda > 0$ ).
(Hukum kuatnya, kasus terbatas, dengan laju) Misalkan $X_i$ i.i.d. dengan nilai di $\intcc ab$ dan $m = \E X_1$ . Tunjukkanlah

$\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b - a)^2}\Bigr)$

lalu perolehlah kembali $\frac{S_n}n \to m$ secara h.p. lewat Borel–Cantelli: yakni bukti kedua bagi hukum kuatnya bagi variabel terbatas — tanpa pemenggalan, dengan laju eksponensial pada setiap $n$ berhingga, tetapi dengan suku terbatas dan kebebasan penuh. Bandingkanlah hipotesisnya dengan hipotesis Etemadi.
(Monte Carlo, terjamin pada $n$ yang tetap) Misalkan $g \colon \intcc01^d \to \intcc01$ terukur dan $(U_k)$ cuplikan seragam i.i.d. pertanyaan 11. Diberikan $\varepsilon, \delta > 0$ , tunjukkanlah

$n \geq \frac{\log(2/\delta)}{2\varepsilon^2} \implies \P\Bigl(\Bigl|\frac1n\sum_{k=1}^ng(U_k) - \int g\,\dd\lambda_d\Bigr| \geq \varepsilon\Bigr) \leq \delta,$

lalu hitunglah ambangnya bagi $\varepsilon = \delta = 10^{-2}$ . Batasnya tak melibatkan $d$ : bandingkanlah dengan pertanyaan 11 dan dengan kisi deterministiknya.

Bagian VIII — Seberapa besar jalan acak? Menuju logaritma teriterasi. Misalkan $S_n = \varepsilon_1 + \dots + \varepsilon_n$ jalan acak sederhana yang dibangun dari tanda adil i.i.d.

(Ekor sub-Gauss) Tunjukkanlah $\E\,\eu^{\lambda S_n} = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ lalu simpulkanlah, bagi $x > 0$ ,

$\P(S_n \geq x) \leq \eu^{-x^2/(2n)}, \qquad \P(\abs{S_n} \geq x) \leq 2\,\eu^{-x^2/(2n)} .$
Simpulkanlah, lewat Borel–Cantelli,

$\limsup_{n\to\infty}\frac{\abs{S_n}} {\sqrt{2n\log n}} \leq 1 \quad\text{h.p.}$

(bagi $\eta > 0$ , jumlahkanlah batas ekornya di $x = (1 + \eta)\sqrt{2n\log n}$ , lalu iriskanlah atas $\eta = \frac1p$ ). Khususnya jalan acaknya hidup pada skala teorema limit pusatnya $\sqrt n$ sampai faktor logaritmik — jauh di bawah batas kasarnya $\abs{S_n} \leq n$ .
Sepanjang subbarisan penggandaan $n_j = 2^j$ , tunjukkanlah

$\limsup_{j\to\infty}\frac{S_{n_j}} {\sqrt{2n_j\log\log n_j}} \leq 1 \quad\text{h.p.},$

lalu renungkanlah: bahwa hukum logaritma teriterasi (Khinchin; dan Hartman–Wintner bagi suku $L^2$ terpusat yang umum) menyatakan bahwa

$\limsup_{n\to\infty}\frac{S_n} {\sqrt{2n\log\log n}} = 1 \quad\text{h.p.}$

Jelaskanlah dengan tepat apa yang memisahkan taksiran subbarisan yang baru dibuktikan itu dari paruh atas pernyataan ini (sebab orang harus mengendalikan $\max_{n_j \leq n \leq n_{j+1}}S_n$ di dalam setiap bloknya, dan itu menuntut ketaksamaan maksimal pada skala eksponensial) lalu periksalah secara kuantitatif bahwa ketaksamaan pertanyaan 12 terlalu lemah untuk maksud itu. Sedangkan paruh bawahnya bersandar pada lema Borel–Cantelli kedua yang diterapkan pada blok yang bebas; kedua paruhnya merupakan bahan Tahun 3 yang jujur bagi kuliah peluang tersendiri.
(Simpangan seragam atas kelas berhingga) Misalkan $A_1, \dots, A_N$ kejadian pada sebuah percobaan yang dapat diulang, lalu taksirlah setiap peluangnya lewat frekuensi empirisnya $\hat p_i$ atas $n$ pengulangan i.i.d. Dengan menggabungkan ketaksamaan Hoeffding dan batas gabungan, tunjukkanlah

$\P\Bigl(\max_{i\leq N}\,\abs{\hat p_i - \P(A_i)} > \varepsilon\Bigr) \;\leq\; 2N\,\eu^{-2n\varepsilon^2},$

lalu simpulkanlah kaidah ukuran cuplikannya: bahwa $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ menjamin seluruh $N$ taksirannya sekaligus akurat- $\varepsilon$ dengan peluang $\geq 1 - \delta$ . Hitunglah $n$ bagi $N = 10^6$ , $\varepsilon = 0.01$ , $\delta = 0.05$ : yakni harga logaritmik bagi keseragamannya.
(Jendela harmonik acaknya) Dengan menggabungkan kedua paruh teori deret acaknya, tunjukkanlah bahwa bagi tanda i.i.d. $(\varepsilon_n)$ deret $\sum_n\frac{\varepsilon_n}{n^\alpha}$ konvergen secara h.p. jika $\alpha > \frac12$ dan divergen secara h.p. jika $\alpha \leq \frac12$ ; lalu pertentangkanlah dengan konvergensi mutlaknya (yang menuntut $\alpha > 1$ ): sebab pada jendela $\alpha \in \intoc{\frac12}1$ , konvergensinya merupakan gejala yang sungguh bersifat peluang — yakni peniadaan, bukan ukuran.

Solusi

Solusi Soal 22.1.

1. Variabel $X_n^{\pm}$ merupakan fungsi Borel $X_n$ : sehingga keduanya tetap bebas berpasangan (Latihan 22.3(a)) dan berdistribusi identik, terintegralkan, dengan $\E X_1 = \E X_1^+ - \E X_1^-$ . Lalu jika teoremanya berlaku bagi variabel tak negatif, terapkanlah pada kedua paruhnya lalu kurangkan: $\frac{S_n}n = \frac{S_n^+}n - \frac{S_n^-}n \to \E X_1^+ - \E X_1^- = m$ secara h.p.

2. Berlaku $\P(X_n \neq Y_n) = \P(X_n > n) = \P(X_1 > n)$ (menurut distribusinya yang identik), dan $\sum_n\P(X_1 > n) \leq \sum_n\P(X_1 \geq n) \leq \E X_1 < \infty$ (Latihan 11.3(a)). Lalu Borel–Cantelli (1): secara h.p. $X_n = Y_n$ bagi setiap $n$ yang besar, sehingga $S_n - S_n^*$ akhirnya konstan terhadap $n$ : jadi $\frac{S_n - S_n^*}n \to 0$ secara h.p., dan kedua jumlah ternormalkannya berbagi perilaku asimtotiknya.

3. Berlaku $X_1\mathbf 1_{X_1 \leq n} \nearrow X_1$ : sehingga teorema konvergensi monotonnya memberikan $\E Y_n \to m$ ; sedangkan rata-rata Cesàro sebuah barisan konvergen menuju limit yang sama: $\frac{\E S_n^*}n = \frac1n\sum_{k\leq n}\E Y_k \to m$ . Karena itu cukup dibuktikan $\frac{S^*_n - \E S^*_n}{n} \to 0$ secara h.p.

4. Berlaku $\V(Y_n) \leq \E Y_n^2 = \E[X_1^2\mathbf 1_{X_1\leq n}]$ . Lalu menurut Tonelli bagi deret,

\sum_n\frac{\E[X_1^2\mathbf 1_{X_1\leq n}]}{n^2} = \E\Bigl[X_1^2\!\!\sum_{n \geq \max(X_1, 1)}\!\frac1{n^2} \Bigr] \leq \E\Bigl[X_1^2\cdot\frac{4}{\max(X_1,1)}\Bigr] \leq 4\,\E[X_1] < \infty,

dengan memakai $\sum_{n\geq x}n^{-2} \leq \frac4x$ bagi $x \geq 1$ (sebab bagi $x \geq 2$ : $\leq \frac1{x-1} \leq \frac2x$ ; sedangkan bagi $1 \leq x < 2$ : $\leq \frac{\pi^2}6 \leq \frac4x$ karena $\frac4x > 2$ ), dan $X_1^2/\max(X_1, 1) \leq X_1$ pada kedua kasus $X_1 \gtrless 1$ .

5. Kebebasan berpasangannya memberikan $\E[(Y_i - \E Y_i)(Y_j - \E Y_j)] = 0$ bagi $i \neq j$ (yakni rumus hasil kali bagi dua variabel), sehingga variansnya menjumlah: $\V(S^*_k) = \sum_{n\leq k}\V(Y_n)$ . Lalu Chebyshev pada setiap $k_j$ lalu menjumlahkannya:

\sum_j\P\Bigl(\abs{S^*_{k_j} - \E S^*_{k_j}} \geq \varepsilon k_j\Bigr) \leq \frac1{\varepsilon^2}\sum_j\frac1{k_j^2}\sum_{n\leq k_j}\V(Y_n) = \frac1{\varepsilon^2}\sum_n\V(Y_n)\!\!\sum_{j : k_j\geq n}\!\frac1{k_j^2}

(menurut Tonelli bagi deret ganda tak negatifnya).

6. Berlaku $k_j = \lfloor\alpha^j\rfloor \geq \frac{\alpha^j}2$ (yang sahih begitu $\alpha^j \geq 1$ , yakni bagi setiap $j \geq 0$ : sebab $\lfloor x\rfloor \geq \frac x2$ bagi $x \geq 1$ ). Karena itu

\sum_{j : k_j \geq n}\frac1{k_j^2} \leq 4\sum_{j : \alpha^j \geq n}\alpha^{-2j} \leq \frac{4}{1 - \alpha^{-2}}\cdot\frac1{n^2} = \frac{C_\alpha}{n^2},

(lewat deret geometrik dari $j$ pertama yang $\alpha^j \geq n$ ). Lalu dengan menggabungkannya dengan pertanyaan 4–5, jumlah gandanya berhingga; sehingga Borel–Cantelli (1), yang diterapkan bagi setiap $\varepsilon$ rasional lalu diiriskan, memberikan $\frac{S^*_{k_j} - \E S^*_{k_j}}{k_j} \to 0$ secara h.p., dan bersama pertanyaan 3: $\frac{S^*_{k_j}}{k_j} \to m$ secara h.p.

7. Karena $Y_n \geq 0$ , maka $n \mapsto S^*_n$ tak turun: sehingga bagi $k_j \leq n \leq k_{j+1}$ ,

\frac{S^*_{k_j}}{k_{j+1}} \leq \frac{S^*_n}{n} \leq \frac{S^*_{k_{j+1}}}{k_j},

yang merupakan apitan yang ditampilkan itu setelah menyisipkan $\frac{k_j}{k_{j+1}}$ dan $\frac{k_{j+1}}{k_j}$ . Lalu karena $\frac{k_{j+1}}{k_j} \to \alpha$ , pertanyaan 6 memberikan secara h.p.

\frac m\alpha \leq \liminf_n\frac{S^*_n}n \leq \limsup_n\frac{S^*_n}n \leq \alpha m .

8. Terapkanlah pertanyaan 7 bagi $\alpha = 1 + \frac1p$ , dengan $p \in \N^*$ : yakni terbilang banyak kejadian h.p.; lalu pada irisannya, dengan membiarkan $p \to \infty$ : $\lim\frac{S^*_n}n = m$ secara h.p. Bersama pertanyaan 1–3, $\frac{S_n}n \to \E X_1$ secara h.p.: yakni hukum kuat bilangan besar, di bawah kebebasan berpasangan.

9. Hipotesis bertipe kebebasan muncul tiga kali: (i) keaditifan variansnya (pertanyaan 5) — di sana berpasangan sudah cukup; (ii) distribusi yang identik, pada jumlah pemenggalannya (pertanyaan 2) dan perhitungan rata-ratanya (pertanyaan 3) — di sana tak ada kebebasan sama sekali; (iii) Borel–Cantelli (1) (pertanyaan 2 dan 6) — yang sahih tanpa kebebasan apa pun. Jadi kebebasan bersama yang penuh tak pernah dipanggil: itulah pengamatan Etemadi.

10. Tetapkanlah sebuah basis $b$ dan sebuah digit $r$ . Maka digit basis- $b$ $(d_k)$ milik $\omega$ yang seragam bersifat seragam i.i.d. pada $\{0, \dots, b-1\}$ (sebab setiap nilai vektor digitnya menempati selang berpanjang $b^{-m}$ : yakni argumen Teorema 22.6 kata demi kata). Lalu hukum kuatnya yang diterapkan pada variabel terbatas i.i.d. $\mathbf 1_{d_k = r}$ memberikan: secara h.p., frekuensi digit $r$ menuju $\frac1b$ . Lalu dengan mengiriskan terbilang banyak pasangan $(b, r)$ : hampir setiap bilangan bersifat normal sederhana pada setiap basis. Adapun satu bilangan tak normal yang eksplisit: $x = 0.100100100\ldots_2$ (dengan frekuensi angka satu $\frac13 \neq \frac12$ ). Pertentangannya merendahkan hati: sebab hampir semua bilangan normal, padahal bagi $\sqrt2$ , $\eu$ , atau $\pi$ kenormalannya tetap tak terbukti — jadi teori ukuran mencacah tanpa menunjukkan.

11. Menurut Latihan 22.10 yang diiterasi, satu variabel seragam menghasilkan barisan vektor seragam i.i.d. $U_k$ pada $\intcc01^d$ (belahlah himpunan digit setiap $U_n$ dari Teorema 22.6 menjadi $d$ subkeluarga). Lalu bagi $g \in L^1(\intcc01^d)$ , variabel $g(U_k)$ bersifat i.i.d. dan terintegralkan dengan rata-rata $\int g\,\dd\lambda_d$ (menurut transfernya): sehingga hukum kuatnya memberikan

\frac1n\sum_{k=1}^ng(U_k) \xrightarrow[n\to\infty]{\text{h.p.}} \int_{\intcc01^d}g\,\dd\lambda_d :

sehingga pengintegralan Monte Carlo konvergen hampir pasti, pada setiap dimensi — sedangkan besarnya galatnya adalah urusan teorema limit pusatnya (Bab 23).

12. Ambillah $A_k = \{\abs{S_k} \geq \varepsilon\} \cap \bigcap_{j<k}\{\abs{S_j} < \varepsilon\}$ : maka $A_k$ saling lepas dengan gabungan $A = \{\max_{k\leq n}\abs{S_k} \geq \varepsilon\}$ . Lalu

\E S_n^2 \geq \sum_{k=1}^n\E\bigl[S_n^2\mathbf 1_{A_k}\bigr] = \sum_{k=1}^n\E\Bigl[\bigl(S_k^2 + 2S_k(S_n - S_k) + (S_n - S_k)^2\bigr)\mathbf 1_{A_k}\Bigr] \geq \sum_{k=1}^n\E\bigl[S_k^2\mathbf 1_{A_k}\bigr],

sebab suku silangnya lenyap: $S_k\mathbf 1_{A_k}$ merupakan fungsi Borel koalisi $(Z_1, \dots, Z_k)$ , yang bebas dari $S_n - S_k$ , yakni fungsi $(Z_{k+1}, \dots, Z_n)$ (Teorema 22.5), sehingga $\E[S_k\mathbf 1_{A_k}(S_n - S_k)] = \E[S_k\mathbf 1_{A_k}]\,\E[S_n - S_k] = 0$ . Sedangkan pada $A_k$ , $S_k^2 \geq \varepsilon^2$ , sehingga $\E S_n^2 \geq \varepsilon^2\sum_k\P(A_k) = \varepsilon^2\P(A)$ ; dan $\E S_n^2 = \sum_{k\leq n}\V(Z_k)$ (sebab variansnya menjumlah). Adapun langkah yang menentukan adalah pemfaktorannya: sebab $S_k\mathbf 1_{A_k}$ merupakan fungsi taklinear seluruh blok pertamanya, dan kebebasannya dari blok kedua adalah kebebasan koalisi — sedangkan kebebasan berpasangan $Z_i$ hanya menghilangkan korelasi pasangan dan takkan membenarkannya.

13. Tetapkanlah $N$ lalu terapkan pertanyaan 12 pada $Z_{N+1}, \dots, Z_{N+m}$ :

\P\Bigl(\max_{N < k \leq N+m}\abs{S_k - S_N} > \varepsilon\Bigr) \leq \frac1{\varepsilon^2}\sum_{j=N+1}^{N+m}\V(Z_j) \leq \frac{r_N}{\varepsilon^2}, \qquad r_N = \sum_{j>N}\V(Z_j) .

Kejadiannya naik terhadap $m$ ; sehingga kekontinuan dari bawah memberikan $\P(\sup_{k>N}\abs{S_k - S_N} > \varepsilon) \leq r_N/\varepsilon^2$ , sedangkan $r_N \to 0$ menurut hipotesisnya. Karena itu bagi setiap $p \in \N^*$ , $\P\bigl(\bigcap_N\{\sup_{k>N} \abs{S_k - S_N} > \frac1p\}\bigr) \leq \inf_Np^2r_N = 0$ : jadi hampir pasti, bagi setiap $p$ ada $N$ dengan $\sup_{k>N}\abs{S_k - S_N} \leq \frac1p$ (iriskanlah terbilang banyak kejadian h.p. atas $p$ ), sehingga $\abs{S_k - S_l} \leq \frac2p$ bagi setiap $k, l > N$ : jadi jumlah parsialnya Cauchy secara h.p., sehingga konvergen secara h.p.

14. Variabel $Z_n = x_n\varepsilon_n$ bersifat bebas (sebab fungsi Borel variabel yang bebas, Latihan 22.3(a)), terpusat, dengan $\V(Z_n) = x_n^2$ : sehingga pertanyaan 13 berlaku bila $\sum_nx_n^2 < \infty$ dan memberikan konvergensi h.p. Secara umum, bagi setiap $N$ konvergensi $\sum_nx_n\varepsilon_n$ tak terpengaruh oleh nilai $\varepsilon_1, \dots, \varepsilon_N$ : sehingga kejadian konvergensinya terletak pada $\sigma$ -aljabar ekor barisan bebas $(\varepsilon_n)$ , jadi hukum nol–satu Kolmogorov (Teorema 22.9) memaksa peluangnya menjadi $0$ atau $1$ .

15. (a) Dengan membelahnya pada aras $\theta\E Z$ lalu memakai Cauchy–Schwarz pada keping atasnya,

\E Z = \E\bigl[Z\mathbf 1_{Z \leq \theta\E Z}\bigr] + \E\bigl[Z\mathbf 1_{Z > \theta\E Z}\bigr] \leq \theta\,\E Z + \sqrt{\E Z^2}\, \sqrt{\P(Z > \theta\E Z)} ,

sehingga $(1 - \theta)\E Z \leq \sqrt{\E Z^2\,\P(Z > \theta\E Z)}$ ; lalu kuadratkanlah. (b) Uraikanlah $T_n^4 = \sum_{i,j,k,l}x_ix_jx_kx_l\, \E[\varepsilon_i\varepsilon_j\varepsilon_k\varepsilon_l]$ : nilai harapannya $1$ bila indeksnya berpasangan (yakni keempatnya sama, atau dua pasangan berbeda, yang terakhir dalam $3$ susunan) dan $0$ selainnya (sebab tanda yang tak berpasangan berrata-rata nol dan terfaktorkan keluar oleh kebebasannya). Karena itu

\E T_n^4 = \sum_kx_k^4 + 3\sum_{i\neq j}x_i^2x_j^2 = 3s_n^4 - 2\sum_kx_k^4 \leq 3s_n^4 .

\P\Bigl(\abs{T_n} > \frac{s_n}2\Bigr) = \P\Bigl(T_n^2 > \frac{s_n^2}4\Bigr) \geq \Bigl(\frac34\Bigr)^2 \frac{s_n^4}{3s_n^4} = \frac3{16} .

Seandainya deretnya konvergen dengan peluang positif, maka ia akan konvergen secara h.p. (pertanyaan 14), sehingga $\sup_n\abs{T_n} < \infty$ secara h.p., dan suatu $M$ akan memenuhi $\P(\sup_n\abs{T_n} > M) < \frac3{16}$ ; padahal begitu $s_n > 2M$ , $\P(\abs{T_n} > M) \geq \P(\abs{T_n} > \frac{s_n}2) \geq \frac3{16}$ : yakni kontradiksi. Jadi divergensinya hampir pasti, dan bersama pertanyaan 14 dikotominya lengkap.

16. Di sini $x_n = n^{-s}$ dan $\sum_nn^{-2s} < \infty$ tepat saat $s > \frac12$ : jadi menurut pertanyaan 14–15, $\sum_n\frac{\varepsilon_n}{n^s}$ konvergen secara h.p. jika dan hanya jika $s > \frac12$ (sedangkan bagi $s \leq \frac12$ , ia divergen secara h.p.). Untuk $\frac12 < s \leq 1$ konvergensinya tak pernah mutlak. Perbandingannya mendidik: sebab tanda yang berselang-seling sempurna meniadakan diri sekuat $n^{-s}$ bagi setiap $s > 0$ , sedangkan tanda acak yang khas meniadakan diri hanya sekuat akar kuadrat — sebab jalan acak pertanyaan 21 tumbuh seperti $\sqrt n$ , dan penjumlahan Abel mengubah persis pertumbuhan itu menjadi konvergensi $\sum\varepsilon_nn^{-s}$ bagi $s > \frac12$ .

17. (a) Berlaku $\cosh\lambda = \sum_k\frac{\lambda^{2k}}{(2k)!}$ dan $\eu^{\lambda^2/2} = \sum_k\frac{\lambda^{2k}}{2^kk!}$ ; sedangkan $(2k)! \geq 2^kk!$ berlaku suku demi suku, sebab $\frac{(2k)!}{k!} = \prod_{i=1}^k(k + i) \geq \prod_{i=1}^k(2i) = 2^kk!$ (karena setiap faktornya memenuhi $k + i \geq 2i$ bagi $i \leq k$ ), sehingga sesungguhnya $(2k)! \geq 2^k(k!)^2 \geq 2^kk!$ . (b) Perhatikanlah $a \leq 0 \leq b$ (sebab $Z$ terpusat), lalu menurut kecembungan $z \mapsto \eu^{\lambda z}$ , bagi $z \in \intcc ab$ :

\eu^{\lambda z} \leq \frac{b - z}{b - a}\,\eu^{\lambda a} + \frac{z - a}{b - a}\,\eu^{\lambda b}, \qquad\text{sehingga}\qquad \E\,\eu^{\lambda Z} \leq \frac{b\,\eu^{\lambda a} - a\,\eu^{\lambda b}}{b - a} = (1 - p)\eu^{-pt} + p\,\eu^{(1-p)t} = \eu^{\varphi(t)}

dengan $p = \frac{-a}{b-a} \in \intcc01$ , $t = \lambda(b - a)$ , $\varphi(t) = -pt + \log(1 - p + p\eu^t)$ . Maka $\varphi(0) = 0$ , $\varphi'(t) = -p + \frac{p\eu^t}{1 - p + p\eu^t}$ lenyap di $0$ , dan $\varphi''(t) = \rho(1 - \rho) \leq \frac14$ bagi $\rho = \frac{p\eu^t}{1 - p + p\eu^t} \in \intcc01$ : sehingga Taylor pada orde $2$ memberikan $\varphi(t) \leq \frac{t^2}8 = \frac{\lambda^2(b-a)^2}8$ .

18. Untuk $\lambda > 0$ , Markov yang diterapkan pada variabel positif $\eu^{\lambda(S_n - \E S_n)}$ (Proposisi 22.3) dan rumus hasil kali bagi variabel yang bebas memberikan

\P(S_n - \E S_n \geq t) \leq \eu^{-\lambda t}\prod_{i=1}^n\E\,\eu^{\lambda(X_i - \E X_i)} \leq \exp\Bigl(-\lambda t + \frac{\lambda^2}8\sum_i(b_i - a_i)^2\Bigr),

menurut pertanyaan 17(b) yang diterapkan pada setiap $X_i - \E X_i \in \intcc{a_i - \E X_i}{b_i - \E X_i}$ yang terpusat (dengan lebar yang sama). Lalu meminimumkan eksponennya di $\lambda = \frac{4t}{D}$ , dengan $D = \sum_i(b_i - a_i)^2$ , menghasilkan $-\frac{2t^2}D$ . Sedangkan ekor bawahnya menyusul dengan menerapkan hasilnya pada $(-X_i)$ .

19. Ambillah $t = n\varepsilon$ dan $D = n(b - a)^2$ :

\P\Bigl(\Bigl|\frac{S_n}n - m\Bigr| \geq \varepsilon\Bigr) \leq 2\exp\Bigl(\frac{-2n^2\varepsilon^2}{n(b-a)^2}\Bigr) = 2\exp\Bigl(\frac{-2n\varepsilon^2}{(b-a)^2}\Bigr),

yang terjumlahkan terhadap $n$ (yakni deret bertipe geometrik): sehingga Borel–Cantelli (Teorema 22.8) memberikan bahwa secara h.p. $\abs{\frac{S_n}n - m} < \varepsilon$ pada akhirnya; lalu mengiriskannya atas $\varepsilon = \frac1p$ menghasilkan $\frac{S_n}n \to m$ secara h.p. Perbandingannya: Etemadi meminta hanya $X_1 \in L^1$ dan kebebasan berpasangan, lalu tak memberikan laju; sedangkan Hoeffding meminta keterbatasan dan kebebasan penuh, lalu memberikan jaminan eksponensial yang eksplisit pada setiap $n$ berhingga — jadi kedua teoremanya menjawab pertanyaan yang berbeda tentang limit yang sama.

20. Variabel $g(U_k)$ bersifat i.i.d. dengan nilai di $\intcc01$ dan berrata-rata $\int g\,\dd\lambda_d$ (menurut transfernya), sehingga pertanyaan 18 dengan $b_i - a_i = 1$ , $t = n\varepsilon$ memberikan batas dua sisinya $2\eu^{-2n\varepsilon^2} \leq \delta$ begitu $\eu^{2n\varepsilon^2} \geq \frac2\delta$ , yakni $n \geq \frac{\log(2/\delta)}{2\varepsilon^2}$ . Untuk $\varepsilon = \delta = 10^{-2}$ :

n \geq \frac{\log 200}{2\cdot10^{-4}} = \frac{5.2983\ldots}{0.0002} \approx 26\,492 :

jadi sekitar $26\,500$ cuplikan menjamin ketelitian $1\%$ dengan keyakinan $99\%$ — pada setiap dimensi $d$ , bagi setiap integran terukur yang bernilai di $\intcc01$ . Sedangkan hukum kuat pertanyaan 11 menjanjikan konvergensi tanpa jaminan pada $n$ berhingga; lalu kisi deterministik dengan $k$ titik per sumbu memakan $k^d$ evaluasi, yang eksponensial terhadap $d$ . Jadi pemusatannyalah yang menjadikan Monte Carlo sebuah metode alih-alih sekadar angan-angan.

21. Lewat kebebasan dan rumus hasil kalinya: $\E\,\eu^{\lambda S_n} = (\E\,\eu^{\lambda\varepsilon_1})^n = (\cosh\lambda)^n \leq \eu^{n\lambda^2/2}$ menurut pertanyaan 17(a). Lalu Markov pada $\eu^{\lambda S_n}$ :

\P(S_n \geq x) \leq \eu^{-\lambda x + n\lambda^2/2} = \eu^{-x^2/(2n)} \qquad\text{pada optimumnya } \lambda = \frac xn,

sedangkan batas setangkupnya bagi $-S_n$ (yang berdistribusi sama) menggandakan konstantanya bagi $\abs{S_n}$ .

22. Tetapkanlah $\eta > 0$ lalu tetapkan $x_n = (1 + \eta)\sqrt{2n\log n}$ bagi $n \geq 2$ :

\P(\abs{S_n} \geq x_n) \leq 2\exp\bigl(-(1 + \eta)^2\log n\bigr) = \frac{2}{n^{(1+\eta)^2}},

yang terjumlahkan sebab $(1 + \eta)^2 > 1$ . Lalu Borel–Cantelli: secara h.p. $\abs{S_n} < (1 + \eta)\sqrt{2n\log n}$ bagi setiap $n$ yang besar, sehingga $\limsup_n\frac{\abs{S_n}}{\sqrt{2n\log n}} \leq 1 + \eta$ secara h.p.; lalu mengiriskan kejadian h.p.-nya bagi $\eta = \frac1p$ , $p \in \N^*$ , memberikan klaimnya. Jadi jalan acak berukuran $n$ beramplitudo khas $\sqrt n$ (yakni variansnya), sedangkan bahkan gerak jauhnya yang terburuk melampaui skala itu paling banyak sebesar $\sqrt{2\log n}$ .

23. Dengan $n_j = 2^j$ dan $x = (1 + \eta)\sqrt{2n_j\log\log n_j}$ (yang terdefinisi bagi $j \geq 2$ ), pertanyaan 21 memberikan

\P\bigl(S_{n_j} \geq x\bigr) \leq \exp\bigl(-(1 + \eta)^2\log\log n_j\bigr) = (j\log 2)^{-(1+\eta)^2},

yang terjumlahkan terhadap $j$ sebab $(1 + \eta)^2 > 1$ : sehingga Borel–Cantelli dan $\eta = \frac1p$ memberikan $\limsup_jS_{n_j}/\sqrt{2n_j \log\log n_j} \leq 1$ secara h.p. Adapun yang kurang bagi paruh atasnya yang penuh adalah jembatan antara pos pemeriksaannya: sebab orang harus menunjukkan bahwa $\max_{n_j\leq n\leq n_{j+1}}S_n$ melampaui $(1+\eta)\sqrt{2n_j\log\log n_j}$ hanya berhingga kali, dan itu menuntut ketaksamaan maksimal berekor Gauss (yakni ketaksamaan pantulan Lévy atau ketaksamaan Ottaviani, yang tak dibuktikan di sini). Sedangkan pertanyaan 12 secara kuantitatif terlalu lemah: sebab ia membatasi peluangnya oleh

\frac{n_j}{(1+\eta)^2\,2n_j\log\log n_j} = \frac{1}{2(1+\eta)^2\log(j\log2)},

yang menuju $0$ tetapi tak terjumlahkan terhadap $j$ : sehingga Borel–Cantelli tak dapat menyimpulkan. Adapun paruh bawah hukum logaritma teriterasinya menerapkan lema Borel–Cantelli kedua pada pertambahan yang bebas $S_{n_{j+1}} - S_{n_j}$ , dengan memakai batas bawah yang sepadan bagi ekor bertipe Gauss. Kedua pertajaman itu merupakan peluang Tahun 3 yang sejati, satu kuliah lebih jauh; sedangkan yang diberikan soal ini tanpa bantuan adalah skala logaritma-teriterasi yang tepat sepanjang waktu geometriknya.

24. Setiap $\hat p_i$ merupakan rata-rata $n$ variabel indikator i.i.d. yang bernilai di $\intcc01$ dan berrata-rata $\P(A_i)$ : sehingga Hoeffding memberikan $\P(\abs{\hat p_i - \P(A_i)} > \varepsilon) \leq 2\eu^{-2n\varepsilon^2}$ . Lalu batas gabungannya mengalikannya dengan $N$ . Lalu menyelesaikan $2N\eu^{-2n\varepsilon^2} \leq \delta$ : $n \geq \frac{\ln(2N/\delta)}{2\varepsilon^2}$ . Secara numerik: $\ln\frac{2\cdot10^6}{0.05} = \ln(4\cdot10^7) \approx 17.5$ , sehingga $n \geq \frac{17.5}{2\cdot10^{-4}} \approx 87\,600$ : jadi menaksir satu peluang sampai $\pm1\%$ memakan sekitar $18\,500$ cuplikan (yakni $\ln(2/\delta)/2\varepsilon^2$ ), sedangkan sejuta peluang hanya $\approx 4.7$ kali lebih banyak — jadi keseragamannya berharga $\ln N$ , bukan $N$ : yakni pengamatan yang menjadikan peminimuman risiko empiris, dan bersamanya pembelajaran mesin, mungkin secara statistik.

25. Variabel $X_n = \frac{\varepsilon_n} {n^\alpha}$ bersifat bebas, terpusat, terbatas, dengan $\sum_n\V(X_n) = \sum_nn^{-2\alpha}$ . Jika $\alpha > \frac12$ : maka deret variansnya konvergen, sehingga teorema satu deretnya (Bagian VI) memberikan konvergensi h.p. $\sum X_n$ . Sedangkan jika $\alpha \leq \frac12$ : deret variansnya divergen, sehingga paruh konversnya (yakni argumen Paley–Zygmund Bagian VI, yang berlaku sebab sukunya terbatas oleh $1$ ) memberikan divergensi h.p. Adapun konvergensi mutlaknya meminta $\sum n^{-\alpha} < \infty$ : yakni $\alpha > 1$ . Jadi pada $\intoc{\frac12}1$ , deretnya konvergen secara h.p. walaupun $\sum\abs{X_n} = \infty$ secara pasti: sebab tandanya bersekongkol untuk meniadakan diri, dengan peluang satu — yakni konvergensi lewat peniadaan, yang tak terlihat oleh uji mutlak mana pun, dan (menurut hukum nol–satunya) dengan vonis yang deterministik pula.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium