Matematika Universitas — Tahun 2 · Bachelor Year 2

22Peubah Acak Diskret

Peubah acak menata perhitungan peluang di sekitar fungsi alih-alih kejadian. Pada ruang terbilang teorinya digerakkan keluarga terjumlahkan pada Bab 7: sebab nilai harapan adalah jumlah sebuah keluarga yang diindeks ruang sampelnya, dan semua sifatnya — kelinearan, pemindahan, rumus hasil kali bagi peubah yang saling bebas — merupakan teorema tentang keluarga yang terjumlahkan. Bab ini membuktikan ketaksamaan kunci Markov, Chebyshev, Cauchy–Schwarz dan Jensen, lalu berakhir dengan hukum klasiknya beserta hukum bilangan besar yang lemah, yang buktinya dua baris begitu Chebyshev tersedia.

22.1 Peubah acak dan hukumnya

Definisi 22.1 (Peubah acak diskret; hukumnya)

Misalkan $(\Omega, \P)$ ruang peluang yang terbilang. Sebuah peubah acak adalah pemetaan $X \colon \Omega \to E$ (dengan $E$ sembarang himpunan; dan disebut real bila $E = \R$ ). Adapun hukum (atau distribusi) peubahnya adalah ukuran peluang $\P_X$ pada himpunan terbilang $X(\Omega)$ yang didefinisikan lewat

\P_X(\{x\}) = \P(X = x) = \P\bigl(\{\omega : X(\omega) = x\}\bigr) .

Contoh 22.2 (Hukum klasiknya)

Bernoulli $\mathcal{B}(p)$ : dengan $X \in \{0, 1\}$ dan $\P(X = 1) = p$ . Yakni indikator sebuah kejadian.
Binomial $\mathcal{B}(n, p)$ : dengan $\P(X = k) = \binom nk p^k(1-p)^{n-k}$ untuk $0 \leq k \leq n$ : yakni banyaknya keberhasilan pada $n$ percobaan Bernoulli yang saling bebas (jilid Kelas 10–12; yang dibuktikan ulang di bawah lewat jumlah peubah yang saling bebas).
Geometri $\mathcal{G}(p)$ : dengan $\P(X = k) = (1-p)^{k-1}p$ untuk $k \in \N^*$ : yakni pangkat keberhasilan pertamanya (Contoh 21.5).
Poisson $\mathcal{P}(\lambda)$ : dengan $\P(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$ untuk $k \in \N$ — yakni sebuah ukuran peluang berkat deret eksponensialnya. Inilah hukum kejadian langka (Bab 23).

Catatan 22.3 (Hukum mana memodelkan apa)

Keempat hukumnya menjawab empat pertanyaan purba: Bernoulli, “apakah ia terjadi?”; binomial, “berapa kali dalam $n$ percobaan?”; geometri, “berapa lama sampai kali pertamanya?”; dan Poisson, “berapa banyak kejadian pada laju tertentu, ketika percobaannya banyak dan masing-masing tak mungkin?”. Jadi mengenali pertanyaannya adalah sembilan persepuluh pemodelannya: sebab jumlah indikator menunjuk ke binomialnya, waktu tunggu ke geometrinya, dan cacah kejadian langka ke Poissonnya — dengan peralihan dari binomial ke Poisson dipersis oleh hukum kejadian langka pada Bab 23.

Proposisi 22.4 (Sifat tanpa ingatan pada hukum geometri)

Bila $X \sim \mathcal{G}(p)$ , maka untuk setiap $m, n \in \N$ :

\P(X > m + n \mid X > m) = \P(X > n) ,

dan hukum geometri adalah satu-satunya hukum pada $\N^*$ yang bersifat demikian.

Bukti. Menjumlahkan bobot geometrinya memberi $\P(X > n) = (1-p)^n$ . Karena itu

\P(X > m + n \mid X > m) = \frac{\P(X > m + n)}{\P(X > m)} = \frac{(1-p)^{m+n}}{(1-p)^m} = (1-p)^n = \P(X > n).

Sebaliknya, bila $G(n) = \P(X > n)$ memenuhi $G(m + n) = G(m)G(n)$ dengan $G(0) = 1$ , maka $G(n) = G(1)^n$ secara induktif; lalu $q = G(1) \in \intco{0}{1}$ , dan $q = 0$ atau hukumnya adalah $\mathcal{G}(1 - q)$ : sebab $\P(X = k) = G(k-1) - G(k) = q^{k-1}(1 - q)$ . ∎

Contoh 22.5 (Tak ada angka yang pernah “jatuh tempo”)

Lemparkan sebuah dadu sambil menunggu enam: maka waktu tunggunya $X \sim \mathcal G(1/6)$ . Adapun sifat tanpa ingatannya mengatakan bahwa sesudah $10$ lemparan yang sia-sia, tunggu sisanya $X - 10$ , jika diketahui $X > 10$ , kembali berhukum $\mathcal G(1/6)$ : jadi nilai harapan tunggu bersyaratnya masih $6$ lemparan, persis seperti pada awalnya. Dadunya tak mengingat, dan tak ada enam yang pernah “jatuh tempo” — jadi kekeliruan penjudi adalah kepercayaan bahwa hukum bersyaratnya sepatutnya bergeser. Sebaliknya, paruh ketunggalan proposisinya mengatakan bahwa ketidakpedulian ini mencirikan waktu tunggu geometri: sebab sembarang waktu tunggu yang ramalannya tak pernah diperbarui bersifat geometri. Adapun antrean dan umur pakai yang nyata biasanya memperbarui, dan persis begitulah kita mendeteksi bahwa keduanya tak geometri.

22.2 Nilai harapan

Definisi 22.6 (Nilai harapan)

Sebuah peubah acak real $X$ pada $(\Omega, \P)$ disebut punya nilai harapan bila keluarga $\bigl(X(\omega)\,\P(\{\omega\})\bigr)_{\omega \in \Omega}$ bersifat terjumlahkan (Bab 7); dan nilai harapannya lalu

\E(X) = \sum_{\omega \in \Omega} X(\omega)\,\P(\{\omega\}) .

Teorema 22.7 (Teorema pemindahan)

Peubah $X$ punya nilai harapan bila dan hanya bila keluarga $\bigl(x\,\P(X = x)\bigr)_{x \in X(\Omega)}$ terjumlahkan, dan lalu

\E(X) = \sum_{x \in X(\Omega)} x\,\P(X = x) .

Lebih umum, untuk $f \colon X(\Omega) \to \R$ , peubah $f(X)$ punya nilai harapan bila dan hanya bila $\sum_x \abs{f(x)}\,\P(X = x) < \infty$ , dan lalu $\E(f(X)) = \sum_x f(x)\,\P(X = x)$ .

Bukti. Partisikanlah $\Omega$ menjadi himpunan arasnya $\Omega_x = \{X = x\}$ dengan $x \in X(\Omega)$ . Menurut teorema penjumlahan lewat paket bagi keluarga yang terjumlahkan (Bab 7), keluarga $(X(\omega)\P(\{\omega\}))_\omega$ terjumlahkan bila dan hanya bila tiap paketnya terjumlahkan (yang otomatis: sebab $\sum_{\omega \in \Omega_x}\abs{x}\P(\{\omega\}) = \abs x\,\P(X = x)$ ) dan keluarga jumlah paketnya $\bigl(x\,\P(X = x)\bigr)_x$ terjumlahkan — dan lalu jumlah totalnya sepakat. Adapun untuk $f(X)$ : terapkanlah pernyataan yang terbukti itu pada peubah $Y = f \circ X$ , yang himpunan arasnya $\{Y = y\} = \bigsqcup_{x : f(x) = y}\{X = x\}$ ; lalu penjumlahan lewat paket yang kedua mengubah $\sum_y y\,\P(Y = y)$ menjadi $\sum_x f(x)\,\P(X = x)$ , dengan paketnya kini mengelompokkan nilai $x$ menurut petanya $f(x)$ , dan keterjumlahan mutlak satu keluarganya setara dengan keterjumlahan yang lain. ∎

Teorema 22.8 (Sifat nilai harapan)

Pada himpunan peubah acak yang punya nilai harapan:

(Kelinearan) $\E(aX + bY) = a\,\E(X) + b\,\E(Y)$ .
(Kepositifan dan kemonotonan) $X \geq 0 \Rightarrow \E(X) \geq 0$ ; $X \leq Y \Rightarrow \E(X) \leq \E(Y)$ ; dan $\abs{\E(X)} \leq \E(\abs X)$ .
(Dominasi) Bila $\abs X \leq Z$ dan $Z$ punya nilai harapan, maka $X$ juga.

Bukti. Semuanya merupakan sifat jumlah keluarga yang terjumlahkan (Bab 7): yakni kelinearan jumlahnya, kepositifan suku demi suku, dan kriteria dominasi bagi keterjumlahannya. (Perhatikan bahwa kelinearannya seketika pada definisinya atas $\Omega$ , sedangkan ia akan janggal pada rumus pemindahannya — yakni satu keuntungan mendefinisikan $\E$ di hulu.) ∎

Contoh 22.9

Untuk $X \sim \mathcal{B}(n, p)$ : dengan menulis $X = X_1 + \dots + X_n$ sebagai jumlah indikator Bernoulli lalu memakai kelinearannya, $\E(X) = np$ — tanpa perlu koefisien binomial. Untuk $X \sim \mathcal{G}(p)$ : $\E(X) = \sum_{k\geq1}k(1-p)^{k-1}p = p\cdot\frac{1}{(1 - (1-p))^2} = \frac1p$ , lewat menurunkan deret geometrinya di dalam cakramnya (Bab 11). Untuk $X \sim \mathcal{P}(\lambda)$ : $\E(X) = \sum_{k\geq1}k e^{-\lambda}\frac{\lambda^k}{k!} = \lambda e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda$ .

Contoh 22.10 (Pemindahan beraksi)

Untuk $X \sim \mathcal P(\lambda)$ , hitunglah $\E\bigl(\frac1{1+X}\bigr)$ — sebab hukum $\frac1{1+X}$ sendiri janggal, tetapi pemindahannya tak pernah memintanya:

\E\Bigl(\frac1{1+X}\Bigr) = \sum_{k\geq0}\frac{1}{k+1}\,\eu^{-\lambda} \frac{\lambda^k}{k!} = \frac{\eu^{-\lambda}}{\lambda}\sum_{k\geq0} \frac{\lambda^{k+1}}{(k+1)!} = \frac{\eu^{-\lambda}}{\lambda}\bigl(\eu^\lambda - 1\bigr) = \frac{1 - \eu^{-\lambda}}{\lambda} .

Ada dua pelajaran. Secara hitungan: mengenali deret eksponensial yang tergeser adalah seluruh kerjanya — sebab pemindahan menyusutkan nilai harapan $f(X)$ menjadi manipulasi deret. Secara struktural: nilai colok naifnya adalah $\frac1{1 + \E X} = \frac1{1 + \lambda}$ , sedangkan jawaban benarnya lebih besar,

\frac{1 - \eu^{-\lambda}}{\lambda} \geq \frac{1}{1 + \lambda},

persis seperti dituntut ketaksamaan Jensen bagi fungsi cembung $t \mapsto \frac1{1+t}$ . Jadi nilai harapan peta cembung duduk di atas nilai colok naifnya, dan pemindahan ditambah pemeriksaan deret membuat ketaksamaan abstraknya menjadi konkret.

Teorema 22.11 (Kebebasan dan hasil kali)

Peubah acak $X, Y$ disebut saling bebas bila $\P(X = x, Y = y) = \P(X = x)\P(Y = y)$ untuk setiap $x, y$ — setara dengan itu, bila kejadian $\{X \in A\}$ dan $\{Y \in B\}$ saling bebas untuk setiap $A, B$ . Bila $X$ dan $Y$ merupakan peubah real yang saling bebas dan punya nilai harapan, maka $XY$ punya nilai harapan dan

\E(XY) = \E(X)\,\E(Y) .

Bukti. Kesetaraan kedua perumusannya menyusul dengan menjumlahkan kesamaan titik demi titiknya atas $(x, y) \in A \times B$ (lewat keaditifan- $\sigma$ dua kali). Adapun untuk hasil kalinya: keluarga gandanya $\bigl(xy\,\P(X = x)\P(Y = y)\bigr)_{(x,y)}$ terjumlahkan, sebab menurut Fubini bagi keluarga (Bab 7)

\sum_{x, y}\abs x \abs y\,\P(X{=}x)\P(Y{=}y) = \Bigl(\sum_x \abs x \P(X{=}x)\Bigr) \Bigl(\sum_y \abs y \P(Y{=}y)\Bigr) < \infty ;

lalu berkat kebebasannya keluarga ini persis $\bigl(xy\,\P(X = x, Y = y)\bigr)$ , yang jumlahnya adalah $\E(XY)$ menurut pemindahan yang diterapkan pada peubah $(X, Y) \mapsto xy$ ; dan Fubini lagi menilai jumlah tak bertandanya sebagai hasil kali $\E(X)\E(Y)$ . ∎

Contoh 22.12 (Hasil kali, dengan dan tanpa kebebasan)

Lemparkan dua dadu setimbang. Bila $Y$ adalah dadu kedua (yang bebas dari yang pertama), maka $\E(XY) = \E(X)\E(Y) = 3.5^2 = 12.25$ . Sedangkan bila $Y = X$ (yakni “hasil kali” sebuah dadu dengan dirinya sendiri),

\E(X^2) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17 \neq 12.25 :

jadi hukum marginal yang sama pada kedua skenarionya, hukum bersama yang berbeda, dan nilai harapan hasil kali yang berbeda. Adapun pelajarannya, yang layak dipahat: $\E(XY)$ adalah fungsional pasangannya, bukan kedua marginalnya — dan senjangnya $\E(X^2) - \E(X)^2 \approx 2.92$ persis, menurut König–Huygens, merupakan ragam $\frac{35}{12}$ dadunya.

22.3 Ragam, kovariansi, dan ketaksamaan klasiknya

Definisi 22.13 (Momen, ragam)

Peubah $X$ disebut punya momen orde 2 bila $X^2$ punya nilai harapan (dan lalu $X$ juga, berkat dominasi: sebab $\abs X \leq \frac{1 + X^2}{2}$ ). Adapun ragam dan simpangan baku peubahnya lalu

V(X) = \E\bigl((X - \E(X))^2\bigr) = \E(X^2) - \E(X)^2 , \qquad \sigma(X) = \sqrt{V(X)} ,

(yakni bentuk keduanya — rumus König–Huygens — lewat menguraikan kuadratnya lalu memakai kelinearannya:

\E\bigl((X - \E X)^2\bigr) = \E\bigl(X^2 - 2X\,\E X + \E(X)^2\bigr) = \E(X^2) - 2\,\E(X)^2 + \E(X)^2 ,

dengan suku tengahnya memakai bahwa $\E X$ sebuah konstanta). Adapun untuk $X, Y$ yang bermomen kedua, kovariansi keduanya adalah

\operatorname{Cov}(X, Y) = \E\bigl((X - \E X)(Y - \E Y)\bigr) = \E(XY) - \E(X)\E(Y) .

Teorema 22.14 (Perkakas ragam)

Untuk peubah yang bermomen kedua:

$V(aX + b) = a^2\,V(X)$ ;
$V(X + Y) = V(X) + V(Y) + 2\operatorname{Cov}(X, Y)$ , dan lebih umum

$V\Bigl(\sum_{i=1}^n X_i\Bigr) = \sum_{i=1}^n V(X_i) + 2\sum_{i < j}\operatorname{Cov}(X_i, X_j) ;$
bila $X, Y$ saling bebas, maka $\operatorname{Cov}(X, Y) = 0$ (sedangkan konversnya salah), jadi ragam peubah yang saling bebas bertambah.

Bukti. Butir 1 dan 2 merupakan penguraian kuadrat ditambah kelinearannya; sedangkan hasil kali $X_iX_j$ punya nilai harapan berkat Cauchy–Schwarz di bawah (atau berkat $\abs{X_iX_j} \leq \frac{X_i^2 + X_j^2}{2}$ ). Adapun butir 3 adalah Teorema 22.11 yang diterapkan pada peubah yang dipusatkan. Contoh tandingan baku bagi konversnya: $X$ yang berhukum seragam pada $\{-1, 0, 1\}$ dan $Y = X^2$ tak berkorelasi (sebab $\E(XY) = \E(X^3) = 0 = \E X \cdot \E Y$ ) tetapi jelas bergantungan. ∎

Teorema 22.15 (Ketaksamaan Markov dan Chebyshev)

(Markov) Bila $X \geq 0$ punya nilai harapan, maka untuk setiap $a > 0$ :

$\P(X \geq a) \leq \frac{\E(X)}{a} .$
(Chebyshev) Bila $X$ bermomen kedua, maka untuk setiap $\varepsilon > 0$ :

$\P\bigl(\abs{X - \E(X)} \geq \varepsilon\bigr) \leq \frac{V(X)}{\varepsilon^2} .$

Bukti. 1. Titik demi titik berlaku $a\,\mathbf{1}_{X \geq a} \leq X$ (sebab pada kejadiannya ruas kirinya $a \leq X$ ; sedangkan di luarnya $0 \leq X$ ). Lalu ambillah nilai harapannya: $a\,\P(X \geq a) \leq \E(X)$ berkat kemonotonannya dan $\E(\mathbf{1}_A) = \P(A)$ . 2. Terapkan Markov pada peubah taknegatif $(X - \E X)^2$ di aras $a = \varepsilon^2$ : sebab kejadian $\{(X - \E X)^2 \geq \varepsilon^2\}$ persis merupakan $\{\abs{X - \E X} \geq \varepsilon\}$ . ∎

Contoh 22.16 (Tak berkorelasi tetapi terlem bersama)

Lemparkan dua dadu setimbang, dengan $X$ dan $Y$ saling bebas, lalu tetapkan $S = X + Y$ dan $D = X - Y$ . Menurut kebilinearan kovariansinya,

\operatorname{Cov}(S, D) = V(X) - V(Y) + \operatorname{Cov}(Y, X) - \operatorname{Cov}(X, Y) = V(X) - V(Y) = 0 :

jadi jumlah dan selisihnya tak berkorelasi. Saling bebas? Tentu tidak: sebab $S = 12$ memaksa $D = 0$ , sedangkan $\P(D = 0) = \frac16$ tanpa syarat. Jadi korelasi hanya menguji bagian linear sebuah kebergantungan; sebab di sini kebergantungannya diusung kendala bahwa $S$ dan $D$ berparitas sama, yang tak terlihat oleh kovariansinya. (Adapun bagi pasangan ini, kovariansi nolnya menuntut $V(X) = V(Y)$ : jadi distribusi yang identik, bukan kebebasan, yang mengerjakannya.)

Contoh 22.17 (Ketika Markov eksak)

Ketaksamaan Markov menjadi kesamaan persis ketika tak ada yang terbuang pada batas $a\,\mathbf 1_{X\geq a} \leq X$ : yakni peubahnya hanya boleh mengambil nilai $0$ dan $a$ . Secara konkret, bila $\P(X = a) = \pi$ dan $\P(X = 0) = 1 - \pi$ , maka $\E(X) = a\pi$ dan

\P(X \geq a) = \pi = \frac{\E(X)}{a} .

Adapun pembacaan realistisnya: pada sebuah populasi yang kekayaan rata-ratanya $100$ dan kekayaannya entah $0$ entah $10^6$ , proporsi jutawannya persis $10^{-4}$ — yakni batas Markov, yang tercapai persis lewat ketaksamaan maksimalnya. Jadi setiap kali $X$ menyebar atas nilai antaranya batasnya menjadi tegas, kerap secara liar; tetapi seperti ditunjukkan kasus ekstremnya, tak ada ketaksamaan yang lebih baik yang dapat disarikan dari rerataannya sendirian.

Contoh 22.18 (Chebyshev bersifat tajam — tanpa hipotesis lebih lanjut)

Tetapkan $\varepsilon > 0$ dan $q \in \intoc01$ , lalu biarkanlah $X$ mengambil nilai $\pm\varepsilon$ masing-masing berpeluang $\frac q2$ dan $0$ berpeluang $1 - q$ . Maka $\E(X) = 0$ , $V(X) = q\varepsilon^2$ , dan

\P\bigl(\abs{X - \E X} \geq \varepsilon\bigr) = q = \frac{V(X)}{\varepsilon^2} :

yakni kesamaan pada Chebyshev. Jadi ketaksamaannya tak dapat diperbaiki dengan memakai ragamnya saja — sebab peluruhan $1/\varepsilon^2$ -nya adalah harga persis informasi momen keduanya. Adapun peluruhan yang lebih cepat menuntut hipotesis yang lebih kuat: sebab keterbatasan peubahnya membeli pemusatan eksponensial, sebagaimana dipratinjau Latihan 22.7 dan dikembangkan secara sistematis oleh soal akhir pekan bab ini.

Teorema 22.19 (Cauchy–Schwarz dan Jensen)

(Cauchy–Schwarz) Bila $X, Y$ bermomen kedua, maka $XY$ punya nilai harapan dan $\E(XY)^2 \leq \E(X^2)\,\E(Y^2)$ ; sehingga $\operatorname{Cov}(X,Y)^2 \leq V(X)V(Y)$ .
(Jensen) Bila $\varphi \colon I \to \R$ cembung pada sebuah interval yang memuat $X(\Omega)$ , dan $X$ serta $\varphi(X)$ punya nilai harapan, maka

$\varphi\bigl(\E(X)\bigr) \leq \E\bigl(\varphi(X)\bigr) .$

Bukti. 1. Keterjumlahan $XY$ : sebab $\abs{XY} \leq \frac{X^2 + Y^2}2$ . Adapun pemetaan $(X, Y) \mapsto \E(XY)$ merupakan bentuk bilinear simetrik yang positif pada ruang peubah yang bermomen kedua, jadi ketaksamaan Cauchy–Schwarz abstrak pada Bab 12 berlaku (sebab semidefinit positif sudah cukup bagi ketaksamaannya). Lalu menerapkannya pada peubah yang dipusatkan memberi batas kovariansinya.

2. Pertama, $m = \E(X)$ terletak di $I$ : sebab $I$ merupakan interval yang memuat semua nilai $X$ , dan nilai harapan bersifat monoton, jadi $m$ berada di antara $\inf X(\Omega)$ dan $\sup X(\Omega)$ . Lalu menurut teorema garis penyangga bagi fungsi cembung (Bab 8), ada $\alpha, \beta$ dengan $\varphi(t) \geq \alpha t + \beta$ untuk setiap $t \in I$ dan $\varphi(m) = \alpha m + \beta$ . Maka, titik demi titik pada $\Omega$ , $\varphi(X) \geq \alpha X + \beta$ ; jadi setelah nilai harapannya diambil,

\E\bigl(\varphi(X)\bigr) \geq \alpha\,\E(X) + \beta = \varphi\bigl(\E(X)\bigr). \qedhere

∎

Contoh 22.20

Jensen dengan $\varphi(t) = t^2$ memberi $\E(X)^2 \leq \E(X^2)$ — yakni kepositifan ragamnya; sedangkan dengan $\varphi(t) = 1/t$ pada $\intoo{0}{\infty}$ : $\frac{1}{\E X} \leq \E\bigl(\frac1X\bigr)$ — yakni rerata harmoniknya di bawah rerata aritmetikanya, kini dalam bentuk acak.

Catatan 22.21 (Jebakan yang sering muncul)

(i) Rumus $\E(XY) = \E(X)\E(Y)$ menuntut kebebasan (atau sekurangnya kovariansi nol): sebab mengambil $Y = X$ memberi $\E(X^2) \neq \E(X)^2$ setiap kali $V(X) > 0$ . (ii) Demikian pula $V(X + X) = 4V(X)$ , bukan $2V(X)$ : sebab ragam hanya bertambah antar suku yang saling bebas (atau yang tak berkorelasi). (iii) Nilai $\E(f(X))$ bukanlah $f(\E(X))$ ; dan untuk $f$ yang cembung Jensen bahkan memberitahukanmu arah galatnya, seperti pada Contoh 22.10. (iv) Keberadaannya sebuah hipotesis yang sejati: sebab untuk peubah St Petersburg $X = 2^K$ dengan $\P(K = k) = 2^{-k}$ (untuk $k \geq 1$ ),

\sum_{k\geq1}2^k\cdot2^{-k} = \sum_{k\geq1}1 = \infty :

jadi $X$ berhingga hampir pasti namun tak punya nilai harapan, sehingga tak ada harga masuk yang adil bagi permainannya. Jadi keterjumlahan pada definisi $\E$ bukanlah kerewelan tata buku — melainkan tempat ekor yang berat terdeteksi. (v) Akhirnya, teorema pemindahannya menuntut keterjumlahan mutlak sebelum sembarang penataan ulang jumlahnya atas nilainya menjadi sah (Bab 7).

Contoh 22.22 (Chebyshev pada seratus lemparan)

Untuk $X \sim \mathcal B(100, \frac12)$ : berlaku $\E X = 50$ dan $V(X) = 25$ . Lalu Chebyshev dengan $\varepsilon = 6$ :

\P(45 \leq X \leq 55) = \P(\abs{X - 50} < 6) \geq 1 - \frac{25}{36} \approx 0.31 ,

sedangkan jumlah binomial eksaknya memberi $\approx 0.73$ . Jadi jaminan $31\%$ -nya jauh dari kebenarannya, tetapi ia hanya menuntut rerataannya dan ragamnya saja — sebab sertifikat yang sama berlaku kata demi kata bagi sembarang peubah dengan $\E = 50$ dan $V = 25$ , seeksotis apa pun, dan Contoh 22.18 menunjukkan bahwa suatu peubah semacam itu menjenuhkannya. Jadi keuniversalannya berharga; sedangkan ketika distribusinya sungguh binomial, perkakas eksponensial pada soal akhir pekan menutup sebagian besar senjangnya.

Contoh 22.23 (Korelasi sebuah bagian dengan keseluruhannya)

Untuk $X, Y$ yang saling bebas dan berdistribusi identik dengan ragam $\sigma^2 > 0$ , seberapa berkorelasikah satu sukunya dengan jumlahnya $S = X + Y$ ? Hitunglah

\operatorname{Cov}(X, S) = \operatorname{Cov}(X, X) + \operatorname{Cov}(X, Y) = \sigma^2 + 0 = \sigma^2, \qquad V(S) = 2\sigma^2,

jadi koefisien korelasinya adalah

\rho(X, S) = \frac{\operatorname{Cov}(X, S)}{\sigma(X)\,\sigma(S)} = \frac{\sigma^2}{\sigma\cdot\sigma\sqrt2} = \frac{1}{\sqrt2} \approx 0.707 ,

apa pun hukum bersamanya — dadu, koin, atau cacah Poisson. Adapun dengan $n$ suku perhitungan yang sama memberi $\rho(X_1, S_n) = 1/\sqrt n$ : jadi pengaruh tiap suku individualnya pada totalnya mengencer seperti akar kuadrat, dan itulah bayangan korelasional bagi skala fluktuasi $\sqrt n$ . Adapun Cauchy–Schwarz menjamin $\abs\rho \leq 1$ selalu; dan di sini batasnya tercapai persis pada kasus merosot $n = 1$ lalu meluruh secara terduga sesudahnya.

Contoh 22.24 (AM–GM terbobot dari Jensen)

Misalkan $Y$ mengambil nilai positif $a_1, \dots, a_k$ dengan peluang $\lambda_1, \dots, \lambda_k$ . Adapun fungsi $-\ln$ cembung pada $\intoo0\infty$ , jadi Jensen memberi $-\ln\E(Y) \leq \E(-\ln Y)$ , yakni

a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_k^{\lambda_k} \;\leq\; \lambda_1a_1 + \lambda_2a_2 + \dots + \lambda_ka_k :

yaitu ketaksamaan aritmetika–geometri yang terbobot, dengan kesamaan bila dan hanya bila $Y$ tetap. Adapun bobot yang sama $\lambda_i = \frac1k$ memulihkan AM–GM klasiknya. Jadi peluang diam-diam telah membuktikan sebuah teorema yang murni aljabar: sebab memilih sebuah hukum peluang tak lain alat tata buku bagi kombinasi cembung — yakni sudut pandang barisentrik Bab 17 sekali lagi, kini dengan Jensen sebagai mesinnya.

22.4 Hukum bilangan besar yang lemah

Teorema 22.25 (Hukum bilangan besar yang lemah)

Misalkan $(X_k)_{k \geq 1}$ peubah acak yang saling bebas berpasangan dan berhukum sama, serta bermomen kedua; lalu tulislah $m = \E(X_1)$ dan $S_n = X_1 + \dots + X_n$ . Maka untuk setiap $\varepsilon > 0$ :

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

Bukti. Berkat kelinearannya $\E(S_n/n) = m$ ; lalu menurut Teorema 22.14 (sebab kebebasan berpasangannya membunuh kovariansinya) $V(S_n) = n\,V(X_1)$ , jadi $V(S_n/n) = V(X_1)/n$ . Sehingga ketaksamaan Chebyshev yang diterapkan pada $S_n/n$ memberi batasnya. ∎

Catatan 22.26

Inilah teorema yang menghubungkan peluang dengan frekuensi: sebab untuk $X_k$ berupa indikator sebuah kejadian $A$ pada pengulangan yang saling bebas, $S_n/n$ merupakan frekuensi $A$ yang teramati, dan hukum bilangan besar mengatakan bahwa ia memusat di sekitar $\P(A)$ dengan laju $\frac{p(1-p)}{n\varepsilon^2}$ . Adapun hukum yang kuat (yakni $S_n/n \to m$ hampir pasti) merupakan teorema Tahun ke-3 — namun buktinya untuk momen keempat sudah terjangkau: lihat Latihan 22.9, yang menjalankan Borel–Cantelli pada batas bertipe Chebyshev. Adapun taksiran Chebyshev yang sama menggerakkan bukti polinomial Bernstein bagi teorema hampiran Weierstrass pada Bab 10 — sebab lema pencacahan di sana adalah hukum bilangan besar yang lemah yang menyamar.

Contoh 22.27 (Mengumpulkan lima puluh kupon)

Pengumpul kupon pada Latihan 22.3 dengan $n = 50$ mainan berbeda: maka total yang diharapkan adalah

\E(T_{50}) = 50\,H_{50} = 50\sum_{k=1}^{50}\frac1k \approx 50 \times 4.499 \approx 225

kotak — yakni empat setengah kali tebakan naifnya $50$ . Adapun pertumbuhan harmoniknya seluruh ceritanya: sebab $25$ mainan pertamanya tiba dalam sekitar $50\ln2 \approx 35$ kotak, sedangkan mainan terakhirnya sendirian berharga $50$ kotak secara rata-rata (yakni tunggu geometri berparameter $\frac1{50}$ ). Jadi masalah penyelesaian didominasi babak akhirnya, dan itulah sebabnya Latihan 22.12 menemukan fluktuasi berorde $n$ — yakni besarnya tunggu geometri terakhir itu — di sekitar rerataannya $n\ln n$ .

Contoh 22.28 (Seberapa besar $n$ harus?)

Untuk memaku frekuensi teramatinya dalam $\varepsilon = 0.01$ dari $\P(A)$ dengan kepercayaan $95\%$ , batas Chebyshev menuntut

\frac{p(1-p)}{n\varepsilon^2} \leq \frac{1}{4n\varepsilon^2} \leq 0.05, \qquad\text{yakni}\qquad n \geq \frac{1}{4\cdot0.05\cdot(0.01)^2} = 50\,000 .

Kebergantungannya brutal dalam $\varepsilon$ (yakni kuadratik) dan lunak dalam kepercayaannya (yakni linear dalam $1/\alpha$ ). Adapun kedua ciri itu merupakan sifat batasnya, bukan sifat kebenarannya: sebab ketaksamaan eksponensial pada soal akhir pekan menurunkan harga kepercayaannya dari $1/\alpha$ menjadi $\ln(1/\alpha)$ — jadi spesifikasi yang sama kelak berharga sekitar $18\,500$ cuplikan di sana — sedangkan skala $1/\varepsilon^2$ -nya sejati dan tak terperbaiki. Jadi mengetahui bagian mana sebuah batas yang longgar sama bergunanya dengan batasnya sendiri.

Hukum bilangan besar sebagai gambar: sebab hukum S_n/n (yang digambar secara skematis) mempertahankan pusatnya m tetapi menyempit ketika n tumbuh, jadi peluang di luar pita [m- , m+ ] — yakni kedua ekornya — menciut ke nol. Adapun Chebyshev membatasi ekornya oleh V(X_1)/(n 2); sedangkan soal akhir pekan menunjukkan bahwa keduanya sebenarnya kecil secara eksponensial. — Hukum bilangan besar sebagai gambar: sebab hukum $S_n/n$ (yang digambar secara skematis) mempertahankan pusatnya $m$ tetapi menyempit ketika $n$ tumbuh, jadi peluang di luar pita $\intcc{m-\varepsilon}{m+\varepsilon}$ — yakni kedua ekornya — menciut ke nol. Adapun Chebyshev membatasi ekornya oleh $V(X_1)/(n\varepsilon^2)$ ; sedangkan soal akhir pekan menunjukkan bahwa keduanya sebenarnya kecil secara eksponensial.

Catatan 22.29 (Pandangan ke depan di dalam jilid ini)

Ke depan, segalanya di sini menyuapi Bab 23: sebab nilai harapan $\E(t^X)$ bagi satu fungsi $X$ yang cerdik memampatkan seluruh hukumnya menjadi sebuah deret pangkat, momennya menjadi turunan di $1$ , dan kesamaan bertipe Wald bagi jumlah acak mengusung teori proses bercabangnya; sedangkan teorema hasil kali bagi peubah yang saling bebas menjadi kemultiplikatifan fungsi pembangkitnya. Ke belakang, nilai harapan adalah barisentrum dengan bobot peluang (Bab 17), ketaksamaan Jensen adalah geometri garis penyangga bagi fungsi cembung (Bab 8), dan metode momen eksponensial pada soal akhir pekan bab ini adalah Markov yang diterapkan pada $\eu^{tX}$ — jadi satu ketaksamaan, yang ditingkatkan oleh satu penggantian peubah yang baik, membentang tiga bab.

22.5 Latihan

Latihan 22.1 ★

Hitunglah $\E(X)$ dan $V(X)$ untuk $X \sim \mathcal{B}(n, p)$ (lewat indikator), $X \sim \mathcal{P}(\lambda)$ (tunjukkan $V(X) = \lambda$ ), dan $X \sim \mathcal{G}(p)$ (tunjukkan $V(X) = \frac{1-p}{p^2}$ ; pakailah $\E(X(X-1))$ beserta turunan kedua deret geometrinya).

Solusi

Solusi Latihan 22.1.

Binomial: $X = \sum_{i=1}^n X_i$ dengan Bernoulli $X_i$ yang saling bebas; $V(X_i) = \E(X_i^2) - \E(X_i)^2 = p - p^2$ , dan ragam peubah yang saling bebas itu menjumlah (Teorema 22.14):

\E(X) = np, \qquad V(X) = np(1-p) .

Poisson: $\E\bigl(X(X-1)\bigr) = \sum_{k\geq2}k(k-1)e^{-\lambda}\frac{\lambda^k}{k!} = \lambda^2 e^{-\lambda}\sum_{j\geq0}\frac{\lambda^j}{j!} = \lambda^2$ , jadi

V(X) = \E(X^2) - \E(X)^2 = \lambda^2 + \lambda - \lambda^2 = \lambda .

Geometrik ( $q = 1 - p$ ): dengan menurunkan $\sum_{k\geq0}q^k = \frac{1}{1-q}$ dua kali di dalam cakramnya (Bab 11), $\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2}{(1-q)^3}$ , jadi

\E\bigl(X(X-1)\bigr) = pq\sum_{k\geq2}k(k-1)q^{k-2} = \frac{2q}{p^2}, \qquad V(X) = \frac{2q}{p^2} + \frac1p - \frac{1}{p^2} = \frac{q}{p^2} = \frac{1-p}{p^2} .

Latihan 22.2 ★

Misalkan $X \sim \mathcal{P}(\lambda)$ dan $Y \sim \mathcal{P}(\mu)$ saling bebas. Tunjukkan bahwa $X + Y \sim \mathcal{P}(\lambda + \mu)$ (lewat konvolusi bobotnya dan teorema binomial), dan bahwa hukum bersyarat $X$ jika diketahui $X + Y = n$ bersifat binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda + \mu}\bigr)$ .

Solusi

Solusi Latihan 22.2.

Jumlah: untuk $n \in \N$ , menurut kesalinglepasan dan kesalingbebasannya,

\P(X + Y = n) = \sum_{k=0}^n \P(X = k)\P(Y = n - k) = e^{-(\lambda + \mu)}\frac{1}{n!} \sum_{k=0}^n \binom nk \lambda^k\mu^{n-k} = e^{-(\lambda+\mu)}\frac{(\lambda + \mu)^n}{n!}

menurut teorema binomial: $X + Y \sim \mathcal{P}(\lambda + \mu)$ . Hukum bersyarat: untuk $0 \leq k \leq n$ ,

\P(X = k \mid X + Y = n) = \frac{\P(X = k)\P(Y = n - k)}{\P(X + Y = n)} = \binom nk \Bigl(\frac{\lambda}{\lambda+\mu}\Bigr)^{k} \Bigl(\frac{\mu}{\lambda+\mu}\Bigr)^{n-k} ,

yakni hukum binomial $\mathcal{B}\bigl(n, \frac{\lambda}{\lambda+\mu}\bigr)$ : bila cacah totalnya diketahui, setiap kejadian secara saling bebas “memilih” sumber pertamanya dengan peluang yang sebanding dengan lajunya.

Latihan 22.3 ★

(Pengumpul kupon, nilai harapannya) Sebuah merek sereal menyembunyikan satu dari $n$ mainan berbeda, secara seragam, di tiap kotaknya. Misalkan $T_n$ banyaknya kotak yang diperlukan untuk mengumpulkan seluruh $n$ mainannya. Dengan menulis $T_n$ sebagai jumlah peubah geometri yang saling bebas (yakni waktu melihat mainan baru ketika $k$ masih hilang), tunjukkanlah

\E(T_n) = n\sum_{k=1}^{n}\frac{1}{k} \sim n\ln n

(yang setara lewat pembandingan deret–integral pada Bab 6).

Solusi

Solusi Latihan 22.3.

Ketika $k$ mainan masih kurang, setiap kotak baru membawa mainan baru dengan peluang $\frac kn$ , bebas dari masa lalunya: waktu tunggu $W_k$ sampai mainan baru berikutnya berhukum geometrik $\mathcal{G}\bigl(\frac kn\bigr)$ , dengan $\E(W_k) = \frac nk$ , dan $T_n = W_n + W_{n-1} + \dots + W_1$ (kotak pertama selalu memberi mainan baru: $W_n = 1$ , sesuai dengan $\E = n/n$ ). Menurut kelinearannya,

\E(T_n) = \sum_{k=1}^n \frac nk = n\sum_{k=1}^n\frac1k \sim n\ln n ,

dengan memakai $\sum_{k\leq n}\frac1k = \ln n + \gamma + o(1)$ (Bab 6). Mengumpulkan segelintir mainan terakhirlah yang mahal: separuh kotaknya habis untuk sisa yang sedikit itu.

Latihan 22.4 ★★

Misalkan $X \geq 0$ bernilai bulat. Buktikan rumus ekornya

\E(X) = \sum_{n=1}^{\infty} \P(X \geq n)

(ketika salah satu ruasnya berhingga), dengan menulis $X = \sum_{n\geq1}\mathbf{1}_{X \geq n}$ lalu menukarkan penjumlahannya (lewat Fubini bagi keluarga taknegatif). Lalu perolehlah $\E(X) = \frac1p$ bagi hukum geometrinya.

Solusi

Solusi Latihan 22.4.

Secara titik demi titik, $X(\omega) = \#\{n \geq 1 : X(\omega) \geq n\} = \sum_{n\geq1}\mathbf{1}_{X \geq n}(\omega)$ . Keluarga rangkap $\bigl(\mathbf{1}_{X \geq n}(\omega)\,\P(\{\omega\})\bigr)_{n, \omega}$ taknegatif, jadi Fubini untuk keluarga (Bab 7) berlaku tanpa syarat: menjumlah dahulu atas $n$ memberi $\E(X)$ , menjumlah dahulu atas $\omega$ memberi $\sum_n \P(X \geq n)$ ; keduanya berhingga serentak dan sama. Untuk $X \sim \mathcal{G}(p)$ : $\P(X \geq n) = q^{n-1}$ ( $q = 1-p$ ), jadi $\E(X) = \sum_{n\geq1}q^{n-1} = \frac{1}{1 - q} = \frac1p$ .

Latihan 22.5 ★★

(Pencuplikan tanpa pengembalian lebih memusat) Sebuah guci berisi $N$ bola, dan $M$ di antaranya putih. Tariklah $n \leq N$ tanpa pengembalian lalu misalkan $X$ mencacah yang putihnya (yakni hukum hipergeometrik). Dengan memakai indikator $X = \sum_{i=1}^n Y_i$ dengan $Y_i$ menyatakan tarikan ke- $i$ : tunjukkanlah bahwa tiap $Y_i$ bersifat Bernoulli berparameter $p = M/N$ (berkat kesimetriannya!), lalu simpulkan $\E(X) = np$ persis seperti dengan pengembalian, kemudian tunjukkan $\operatorname{Cov}(Y_i, Y_j) = -\frac{p(1-p)}{N-1} < 0$ untuk $i \neq j$ , sehingga $V(X) = np(1-p)\frac{N - n}{N - 1} \leq np(1-p)$ .

Solusi

Solusi Latihan 22.5.

Kesetangkupan: bola ke- $i$ yang terambil merupakan bola seragam acak dari gucinya (setiap dari $N$ bolanya sama mungkin menempati kedudukan $i$ pada urutan pengambilannya), jadi $\P(Y_i = 1) = \frac MN = p$ dan $\E(X) = np$ menurut kelinearannya — tanpa perlu kesalingbebasan.

Kovariansi: untuk $i \neq j$ , $\E(Y_iY_j) = \P(\text{pengambilan } i, j \text{ sama-sama putih}) = \frac{M(M-1)}{N(N-1)}$ (pasangan terurut kedudukan yang berbeda memperoleh pasangan terurut bola yang berbeda, secara seragam). Jadi

\operatorname{Cov}(Y_i, Y_j) = \frac{M(M-1)}{N(N-1)} - \frac{M^2}{N^2} = \frac{M(N - M)}{N^2}\cdot\frac{-1}{N-1} = -\frac{p(1-p)}{N-1} < 0 :

mengambil satu bola putih membuat yang putih makin langka bagi pengambilan lainnya. Menurut Teorema 22.14,

V(X) = np(1-p) + n(n-1)\Bigl(-\frac{p(1-p)}{N-1}\Bigr) = np(1-p)\,\frac{N - n}{N - 1} \leq np(1-p) :

pencuplikan tanpa pengembalian punya rerata yang sama tetapi ragam yang lebih kecil daripada dengan pengembalian (kesamaannya hanya untuk $n = 1$ ), dengan korelasi negatifnya berperan sebagai penstabil. Untuk $n = N$ ragamnya lenyap: cacahnya lalu bersifat deterministik.

Latihan 22.6 ★★

Misalkan $X$ bermomen kedua. Tunjukkan bahwa $c \mapsto \E\bigl((X - c)^2\bigr)$ minimum persis di $c = \E(X)$ , dengan minimum $V(X)$ . Lalu tunjukkan bahwa $\P(X = \E(X)) = 1$ bila dan hanya bila $V(X) = 0$ . (Untuk butir keduanya: bila $V(X) = 0$ , pakailah Chebyshev dengan $\varepsilon = 1/n$ beserta kekontinuan monoton, Teorema 21.6.)

Solusi

Solusi Latihan 22.6.

Dengan menguraikan di sekitar $m = \E(X)$ :

\E\bigl((X - c)^2\bigr) = \E\bigl((X - m)^2\bigr) + 2(m - c)\,\E(X - m) + (m - c)^2 = V(X) + (m - c)^2 ,

yang minimum persis di $c = m$ dengan nilai $V(X)$ — nilai harapan merupakan penduga konstan terbaik dalam rerata kuadrat.

Bila $\P(X = m) = 1$ maka $(X - m)^2$ lenyap dengan peluang $1$ , jadi $V(X) = 0$ (keluarga pendefinisinya bersuku nol kecuali pada himpunan nol). Sebaliknya, bila $V(X) = 0$ , Chebyshev (Teorema 22.15) memberi $\P\bigl(\abs{X - m} \geq \frac1n\bigr) \leq n^2\,V(X) = 0$ untuk setiap $n$ ; kejadian $\bigl\{\abs{X - m} \geq \frac1n\bigr\}$ naik menuju $\{X \neq m\}$ , jadi kekontinuan monoton (Teorema 21.6) memberikan $\P(X \neq m) = 0$ .

Latihan 22.7 ★★★

(Pemusatan mengalahkan Markov) Misalkan $S_n \sim \mathcal{B}(n, \frac12)$ (yakni banyaknya gambar pada $n$ lemparan setimbang). Bandingkanlah batas yang diberikan Markov (yakni $\P(S_n \geq \frac{3n}{4})$ ), Chebyshev, dan metode eksponensial (Chernoff):

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \E\bigl(e^{tS_n}\bigr)e^{-3nt/4} = \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} \quad (t > 0),

lalu optimumkan $t$ untuk memperoleh batas yang kecil secara eksponensial. (Di $t = \ln 3$ : batasnya $\bigl(2\cdot 3^{-3/4}\bigr)^n \approx (0.877)^n$ .)

Solusi

Solusi Latihan 22.7.

$\E(S_n) = \frac n2$ dan $V(S_n) = \frac n4$ . Markov: $\P\bigl(S_n \geq \frac{3n}4\bigr) \leq \frac{n/2}{3n/4} = \frac23$ — sebuah batas konstan, tak berguna untuk $n$ yang besar. Chebyshev: kejadiannya mengakibatkan $\abs{S_n - \frac n2} \geq \frac n4$ , jadi peluangnya $\leq \frac{n/4}{(n/4)^2} = \frac4n$ — meluruh, tetapi hanya secara suku banyak. Chernoff: menurut kesalingbebasannya, $\E(e^{tS_n}) = \prod_{i=1}^n\E(e^{tX_i}) = \bigl(\frac{1 + e^t}{2}\bigr)^n$ , dan Markov yang diterapkan pada $e^{tS_n} \geq e^{3nt/4}$ memberi, untuk setiap $t > 0$ ,

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{1 + e^t}{2}\Bigr)^n e^{-3nt/4} = \exp\Bigl(n\bigl(\ln\tfrac{1 + e^t}{2} - \tfrac{3t}4\bigr)\Bigr).

Minimumkan pangkatnya: $\frac{\dd}{\dd t}\ln\frac{1+e^t}{2} = \frac{e^t}{1 + e^t} = \frac34$ di $e^t = 3$ , yakni $t = \ln 3$ , sehingga

\P\Bigl(S_n \geq \frac{3n}4\Bigr) \leq \Bigl(\frac{4}{2}\Bigr)^n 3^{-3n/4} = \bigl(2 \cdot 3^{-3/4}\bigr)^n \approx (0.877)^n ,

yang kecil secara eksponensial. Hierarki Markov $\to$ Chebyshev $\to$ Chernoff merupakan tangga bakunya: setiap anak tangganya menerapkan Markov pada fungsi peubahnya yang tumbuh lebih cepat.

Latihan 22.8 ★★★

(Weierstrass lagi, secara peluang) Misalkan $f \colon [0,1] \to \R$ kontinu dan $S_n \sim \mathcal{B}(n, x)$ . Tunjukkan bahwa polinomial Bernstein $B_nf(x) = \sum_{k=0}^n f\bigl(\frac kn\bigr)\binom nk x^k(1-x)^{n-k}$ sama dengan $\E\bigl[f\bigl(\frac{S_n}{n}\bigr)\bigr]$ , lalu turunkan ulang taksiran $\abs{B_nf(x) - f(x)} \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2}$ pada Bab 10 dalam bahasa peluang ini (yakni pecahlah pada $\bigl|\frac{S_n}{n} - x\bigr| \geq \delta$ lalu pakailah Chebyshev).

Solusi

Solusi Latihan 22.8.

Menurut teorema pemindahan (Teorema 22.7) yang diterapkan pada $f\bigl(\frac{S_n}{n}\bigr)$ dengan $S_n \sim \mathcal{B}(n, x)$ :

\E\Bigl[f\Bigl(\frac{S_n}{n}\Bigr)\Bigr] = \sum_{k=0}^n f\Bigl(\frac kn\Bigr)\binom nk x^k(1-x)^{n-k} = B_nf(x) .

Tetapkan $\delta > 0$ lalu pisahkan $\abs{f(S_n/n) - f(x)}$ pada kejadian $D = \bigl\{\abs{\frac{S_n}{n} - x} \geq \delta\bigr\}$ : di luar $D$ , selisihnya paling besar sama dengan modulus kekontinuannya $\omega_f(\delta) = \sup_{\abs{s - t}\leq\delta}\abs{f(s) - f(t)}$ ; pada $D$ , paling besar $2\norm f_\infty$ . Dengan mengambil nilai harapannya lalu memakai Chebyshev dengan $V\bigl(\frac{S_n}{n}\bigr) = \frac{x(1-x)}{n} \leq \frac{1}{4n}$ :

\abs{B_nf(x) - f(x)} \leq \E\,\abs{f(S_n/n) - f(x)} \leq \omega_f(\delta) + 2\norm f_\infty\,\P(D) \leq \omega_f(\delta) + \frac{2\norm f_\infty}{4n\delta^2} .

Kekontinuan seragam $f$ pada $[0, 1]$ membuat $\omega_f(\delta) \to 0$ : pilih $\delta$ lalu $n$ , maka $B_nf \to f$ secara seragam — itulah teorema hampiran Weierstrass pada Bab 10, yang “lema pencacahannya” kini terkenali sebagai ketaksamaan Chebyshev bagi hukum binomialnya.

Latihan 22.9 ★★★

(Hukum kuat di bawah momen keempat) Misalkan $(X_k)$ saling bebas, berdistribusi identik, terpusat (dengan $\E X_1 = 0$ ), dan $\E(X_1^4) < \infty$ . Dengan menguraikan $\E(S_n^4)$ lalu mencacah suku yang bertahan (yakni hanya suku $\E(X_i^4)$ dan $\E(X_i^2X_j^2)$ dengan $i \neq j$ ), tunjukkanlah $\E(S_n^4) \leq C n^2$ untuk sebuah konstanta $C$ . Lalu turunkan $\sum_n \P\bigl(\abs{S_n/n} \geq \varepsilon\bigr) < \infty$ untuk tiap $\varepsilon > 0$ (lewat Markov pada orde 4) kemudian rampungkan dengan Borel–Cantelli (Teorema 21.25) bahwa $S_n/n \to 0$ hampir pasti dalam perumusan yang sesuai: yakni bahwa kejadian $\bigcap_{j}\bigcup_N\bigcap_{n \geq N}\{\abs{S_n/n} < \frac1j\}$ berpeluang $1$ .

Solusi

Solusi Latihan 22.9.

Uraikan $S_n^4 = \sum_{i,j,k,l}X_iX_jX_kX_l$ lalu ambil nilai harapannya. Menurut kesalingbebasan dan pemusatannya, setiap suku yang memuat satu indeks yang muncul tepat sekali akan lenyap ( $\E(X_i) = 0$ terfaktorkan keluar). Suku yang bertahan: $n$ suku diagonal $\E(X_i^4)$ , dan suku yang memasangkan dua pasang indeks yang sama, $\E(X_i^2X_j^2) = \E(X_1^2)^2$ untuk $i \neq j$ , yang muncul $3n(n-1)$ kali: pilih pasangan takterurut nilainya ( $\binom n2$ cara), lalu $\frac{4!}{2!\,2!} = 6$ cara menempatkannya pada keempat lubangnya — $6\binom n2 = 3n(n-1)$ . Jadi, dengan $\E(X_1^2)^2 \leq \E(X_1^4)$ (Jensen atau Cauchy–Schwarz),

\E(S_n^4) = n\,\E(X_1^4) + 3n(n-1)\,\E(X_1^2)^2 \leq C n^2, \qquad C = 4\,\E(X_1^4) .

Markov pada orde 4:

\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}{n^2\varepsilon^4} ,

yakni deret yang terjumlahkan. Menurut Borel–Cantelli 1 (Teorema 21.25), untuk setiap $j$ kejadian $B_j = \limsup_n\bigl\{\abs{S_n/n} \geq \frac1j\bigr\}$ berpeluang $0$ , jadi $\P\bigl(\bigcup_j B_j\bigr) = 0$ menurut kesubaditifan terbilang. Pada komplemennya — yang berpeluang $1$ — untuk setiap $j$ ada $N$ dengan $\abs{S_n/n} < \frac1j$ bagi semua $n \geq N$ : itu persis $S_n/n \to 0$ . Hukum kuat bilangan besar berlaku di bawah momen keempat; menyingkirkan hipotesis itu (teorema Kolmogorov) merupakan pekerjaan Tahun ke-3.

Latihan 22.10 ★

Dua dadu setimbang dilempar; misalkan $M$ yang lebih besar di antara kedua hasilnya. Dengan memakai rumus ekor pada Latihan 22.4 (versi berhingganya), tunjukkanlah

\E(M) = \sum_{k=1}^{6}\P(M \geq k) = 6 - \sum_{j=0}^5\Bigl(\frac j6\Bigr)^2 = \frac{161}{36} \approx 4.47 .

Solusi

Solusi Latihan 22.10.

$\P(M \leq k) = \bigl(\frac k6\bigr)^2$ (kedua dadunya paling besar $k$ , secara saling bebas), jadi $\P(M \geq k) = 1 - \bigl(\frac{k-1}6\bigr)^2$ dan

\E(M) = \sum_{k=1}^6\P(M \geq k) = 6 - \frac{0 + 1 + 4 + 9 + 16 + 25}{36} = 6 - \frac{55}{36} = \frac{161}{36} \approx 4.47 ,

yang cukup jauh di atas rerata $3.5$ satu dadu tunggal, sebagaimana layaknya sebuah maksimum.

Latihan 22.11 ★★

Misalkan $F_n$ banyaknya titik tetap sebuah permutasi acak seragam atas $\{1, \dots, n\}$ (dengan $n \geq 2$ ). Dengan menulis $F_n = \sum_i\mathbf 1_{\sigma(i) = i}$ , hitunglah $\E(F_n) = 1$ dan $\operatorname{Cov}(\mathbf 1_{\sigma(i)=i}, \mathbf 1_{\sigma(j)=j}) = \frac1{n^2(n-1)}$ untuk $i \neq j$ , lalu simpulkan $V(F_n) = 1$ : jadi rata-rata satu huruf tetap, dengan ragam persis $1$ , berapa pun $n$ .

Solusi

Solusi Latihan 22.11.

Dengan $I_i = \mathbf 1_{\sigma(i) = i}$ : $\P(\sigma(i) = i) = \frac{(n-1)!}{n!} = \frac1n$ , jadi $\E(F_n) = n\cdot\frac1n = 1$ . Untuk $i \neq j$ : $\P(\sigma(i) = i, \sigma(j) = j) = \frac{(n-2)!}{n!} = \frac1{n(n-1)}$ , sehingga

\operatorname{Cov}(I_i, I_j) = \frac1{n(n-1)} - \frac1{n^2} = \frac{1}{n^2(n-1)} .

Menurut perkakas ragamnya (Teorema 22.14),

V(F_n) = n\cdot\frac1n\Bigl(1 - \frac1n\Bigr) + n(n-1)\cdot\frac1{n^2(n-1)} = 1 - \frac1n + \frac1n = 1 .

Rerata $1$ , ragam $1$ , tak bergantung pada $n$ — sesuai dengan limit Poisson pada masalah pencocokannya (Latihan 21.5).

Latihan 22.12 ★★★

(Pengumpul kupon, pemusatannya) Pada latar Latihan 22.3, tunjukkanlah

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq n^2\sum_{k=1}^n\frac{1}{k^2} \leq \frac{\pi^2}{6}n^2,

dengan memakai kebebasan tahap geometrinya beserta $V(\mathcal G(p)) = \frac{1-p}{p^2}$ (Latihan 22.1; dan nilai $\pi^2/6$ -nya adalah Contoh 14.12). Lalu turunkan dengan Chebyshev bahwa $\dfrac{T_n}{n\ln n} \to 1$ dalam peluang: jadi total waktu pengumpulnya adalah $n\ln n$ hingga fluktuasi berorde $n$ .

Solusi

Solusi Latihan 22.12.

$T_n = \sum_{k=1}^nG_k$ dengan $G_k \sim \mathcal G(k/n)$ menyatakan waktu sampai terlihat mainan baru ketika $k$ mainan masih kurang, dan tahapannya saling bebas. Jadi

V(T_n) = \sum_{k=1}^n\frac{1 - k/n}{(k/n)^2} \leq \sum_{k=1}^n\frac{n^2}{k^2} \leq \frac{\pi^2}6\,n^2 ,

menurut Contoh 14.12. Dengan $\E(T_n) = nH_n$ , $H_n = \sum_1^n\frac1k$ (Latihan 22.3), Chebyshev memberi, untuk $\varepsilon > 0$ ,

\P\bigl(\abs{T_n - nH_n} \geq \varepsilon\,n\ln n\bigr) \leq \frac{\pi^2n^2/6}{\varepsilon^2n^2\ln^2 n} = \frac{\pi^2}{6\,\varepsilon^2\ln^2n} \xrightarrow[n\to\infty]{} 0 .

Karena $H_n \sim \ln n$ , membaginya dengan $n\ln n$ menunjukkan $T_n/(n\ln n) \to 1$ dalam peluang: fluktuasi $T_n$ berorde $n$ , yang dapat diabaikan terhadap reratanya $n\ln n$ .

22.6 Soal: kotak perkakas pemusatan, dari Markov ke Hoeffding

Soal 22.1

Soal akhir pekan — pemusatan eksponensial dengan tangan, dan berapa orang yang harus ditanya sebuah jajak pendapat

Ketaksamaan Markov berharga satu momen dan membeli peluruhan $1/a$ ; sedangkan Chebyshev berharga dua momen dan membeli $1/\varepsilon^2$ — dan Contoh 22.18 menunjukkan bahwa itulah semua yang dapat dibeli momen tersebut. Soal ini mendaki sisa tangganya: yakni metode eksponensial (Chernoff) dengan lajunya yang eksak bagi lemparan koin, ketaksamaan Hoeffding bagi semua peubah yang terbatas, dan panennya — yakni ukuran cuplikan yang gamblang dan jujur bagi jajak pendapat, penetapan pemenang pemilu, dan pengujian koin. Di sepanjang soal ini, $S_n \sim \mathcal B(n, p)$ merupakan jumlah $n$ peubah Bernoulli yang saling bebas dan $\widehat p_n = S_n/n$ frekuensi empirisnya.

Bagian I — Penakaran pada koin yang setimbang. Di sini $p = \frac12$ dan $a \in \intoo{\frac12}{1}$ .

Markov di aras $an$ : tunjukkan $\P(S_n \geq an) \leq \frac1{2a}$ , yakni batas yang bahkan tak menuju $0$ . Lalu di mana Markov kehilangan sebanyak itu?
Chebyshev: dengan memakai kesetangkupan binomial setimbangnya terhadap $n/2$ , tunjukkanlah

$\P(S_n \geq an) = \tfrac12\, \P\bigl(\abs{S_n - \tfrac n2} \geq n(a - \tfrac12)\bigr) \leq \frac{1}{8n(a - 1/2)^2},$

yakni $\frac2n$ di $a = \frac34$ : jadi peluruhan polinomial pada akhirnya.
(Chernoff, aras umum) Hitunglah $\E(\eu^{tS_n}) = \bigl(\frac{1 + \eu^t}2\bigr)^n$ lalu optimumkan $\P(S_n \geq an) \leq \E(\eu^{tS_n})\eu^{-tan}$ atas $t > 0$ : tunjukkan bahwa $t$ optimumnya adalah $\ln\frac{a}{1-a}$ dan

$\P(S_n \geq an) \leq \eu^{-n\,I(a)}, \qquad I(a) = \ln 2 + a\ln a + (1-a)\ln(1-a) > 0 .$

Lalu periksalah bahwa $a = \frac34$ memulihkan batas $\bigl(2\cdot3^{-3/4}\bigr)^n$ pada Latihan 22.7.
(Eksponennya eksak) Misalkan $k = an$ bilangan bulat. Dari fakta bahwa $\binom nk a^k(1-a)^{n-k}$ merupakan yang terbesar di antara $n + 1$ suku sebuah distribusi peluang, buktikanlah $\binom nk \geq \frac{\eu^{nH(a)}}{n+1}$ dengan $H(a) = -a\ln a - (1-a)\ln(1-a)$ , lalu turunkan batas bawah yang bersesuaian

$\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \frac{\eu^{-n\,I(a)}}{n + 1} .$
Tabelkan ketiga batasnya di $n = 100$ dan $a = \frac34$ : yakni Markov $\frac23$ , Chebyshev $0.02$ , dan Chernoff $\approx 2.1\cdot10^{-6}$ (sedangkan nilai benarnya $\approx 2.8\cdot10^{-7}$ ). Lalu pelajarannya, dalam satu kalimat?

Bagian II — Ketaksamaan Hoeffding.

(Kasus Rademacher) Untuk $\varepsilon = \pm1$ yang masing-masing berpeluang $\frac12$ , buktikanlah

$\E(\eu^{t\varepsilon}) = \cosh t \leq \eu^{t^2/2} \qquad (t \in \R)$

dengan membandingkan kedua deretnya suku demi suku (sebab $(2k)! \geq 2^kk!$ ).
Turunkan, untuk peubah Rademacher yang saling bebas $\varepsilon_1, \dots, \varepsilon_n$ dan setiap $s > 0$ :

$\P\Bigl(\sum_{i=1}^n\varepsilon_i \geq s\Bigr) \leq \eu^{-s^2/(2n)} .$
Terjemahkan ke koin setimbang (dengan $X_i = \frac{1+\varepsilon_i}2$ ): $\P\bigl(\widehat p_n - \tfrac12 \geq \delta\bigr) \leq \eu^{-2n\delta^2}$ , beserta versi dua sisinya dengan faktor $2$ .
(Lema Hoeffding) Misalkan $X \in \intcc01$ dengan $\E X = p$ , dan $\psi(t) = \ln\E(\eu^{tX})$ . Benarkanlah bahwa $\psi$ terdiferensialkan dua kali dengan

$\psi''(t) = \E_t(X^2) - \E_t(X)^2, \qquad \E_t(Y) := \frac{\E(Y\eu^{tX})}{\E(\eu^{tX})},$

yakni sebuah ragam bagi peubah terbobot ulang yang masih bernilai di $\intcc01$ ; lalu batasilah ia dengan $\frac14$ (lewat hujah keminimalan Latihan 22.6) kemudian rampungkan lewat Taylor:

$\E\bigl(\eu^{t(X - p)}\bigr) \leq \eu^{t^2/8} .$
(Ketaksamaan Hoeffding) Untuk $X_i \in \intcc01$ yang saling bebas dengan rerataan bersama $p$ , turunkanlah

$\P\bigl(\abs{\widehat p_n - p} \geq \delta\bigr) \leq 2\,\eu^{-2n\delta^2} \qquad (\delta > 0).$
Bandingkan laju Chebyshev $\frac{p(1-p)}{n\delta^2}$ dengan laju Hoeffding $2\eu^{-2n\delta^2}$ : hipotesis mana yang dituntut masing-masingnya, dan mulai dari $n$ yang mana (secara kasar) batas eksponensialnya menang di $\delta = 0.03$ dan $p = \frac12$ ?

Bagian III — Berapa orang yang harus ditanya sebuah jajak pendapat? Sebuah jajak pendapat menanyai $n$ pemilih yang saling bebas dan dipilih seragam; masing-masing menjawab jujur; dengan $p$ menyatakan skor benarnya dan $\widehat p_n$ angka jajak pendapatnya.

Tunjukkan bahwa jajak pendapatnya akurat sampai $\pm\delta$ dengan kepercayaan $1 - \alpha$ (yakni $\P(\abs{\widehat p_n - p} \geq \delta) \leq \alpha$ ) segera setelah

$n \;\geq\; \frac{\ln(2/\alpha)}{2\,\delta^2} .$
Hitunglah $n$ yang dituntut bagi spesifikasi baku “tiga poin, sembilan puluh lima persen” (dengan $\delta = 0.03$ dan $\alpha = 0.05$ ): yakni $n \geq 2050$ ; dan bagi satu poin: $n \geq 18\,445$ . Amatilah — lalu jelaskanlah — fakta yang mencolok bahwa jawabannya tak melibatkan besarnya populasi.
Kerjakan ulang pertanyaan 13 lewat Chebyshev (dengan $V(X_1) = p(1-p) \leq \frac14$ ): yakni $n \geq \frac1{4\alpha\delta^2} = 5556$ pada tiga poin. Perhatikan bahwa pencuplikan tanpa pengembalian hanya membantu (Latihan 22.5: sebab ragamnya menciut sebesar $\frac{N-n}{N-1}$ ).
(Menetapkan pemenang pemilu) Skor benar seorang kandidat adalah $p = 0.52$ . Berapa banyak pemilih yang harus dijajaki agar $\P(\widehat p_n \leq \tfrac12) \leq 0.01$ ? Tunjukkanlah $n \geq \frac{\ln 100}{2\cdot(0.02)^2} \approx 5757$ — jadi menetapkan pemenang perlombaan yang ketat jauh lebih mahal daripada menaksir sebuah skor.
Apa yang tak diliput matematikanya: daftarkanlah asumsi pemodelan yang dipakai (yakni pencuplikan seragam yang saling bebas, jawaban yang jujur, dan $p$ yang tetap), lalu jelaskanlah dalam satu paragraf pendek mengapa galat jajak pendapat yang nyata didominasi bias (yakni pencuplikan yang tak seragam dan ketakresponsan), yang tak dikurangi oleh kenaikan $n$ mana pun.

Bagian IV — Lebih tajam dan lebih murah.

(Median rerata: peluruhan eksponensial dari dua momen) Pecahlah sebuah anggaran berisi $km$ cuplikan menjadi $k$ kelompok saling bebas berisi $m$ ; lalu misalkan $\widehat p^{(1)}, \dots, \widehat p^{(k)}$ rerata kelompoknya dan $M$ mediannya. Pilihlah $m$ sedemikian sehingga tiap kelompoknya memenuhi $\P(\abs{\widehat p^{(i)} - p} \geq \delta) \leq \frac18$ (lewat Chebyshev: sebab $m \geq \frac2{\delta^2}$ sudah cukup). Tunjukkanlah bahwa bila $\abs{M - p} \geq \delta$ maka sekurangnya $k/2$ kelompoknya keliru, lalu turunkan

$\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil}\Bigl(\frac18 \Bigr)^{k/2} \leq 2^k\cdot 8^{-k/2} = 2^{-k/2} :$

jadi pemusatan eksponensial dengan memakai apa pun yang tak melampaui ragamnya.
(Paley–Zygmund) Untuk $X \geq 0$ yang bermomen kedua, buktikanlah $\P(X > 0) \geq \dfrac{\E(X)^2}{\E(X^2)}$ (lewat Cauchy–Schwarz pada $X\mathbf 1_{X>0}$ ): yakni perkakas arah baliknya — sebab momen juga dapat memaksa kejadian untuk terjadi.
(Pinsker ringan) Tunjukkan $I(a) \geq 2\bigl(a - \tfrac12\bigr)^2$ pada $\intoo{\frac12}1$ (sebab selisihnya lenyap sampai orde dua di $\frac12$ dan turunan keduanya $\frac1{a(1-a)} - 4 \geq 0$ ): jadi eksponen eksak Chernoff selalu mengalahkan eksponen kuadratik Hoeffding.
Uraikan $I\bigl(\tfrac12 + \delta\bigr) = 2\delta^2 + O(\delta^4)$ lalu gabungkan dengan pertanyaan 4: jadi untuk simpangan yang kecil eksponen Hoeffding $2n\delta^2$ bersifat eksak secara asimtotik — sehingga tak ada metode yang dapat mengalahkannya lebih daripada faktor polinomial.
Susunlah tabel kotak perkakasnya: yakni bagi Markov, Chebyshev, batas momen keempat pada Latihan 22.9, Hoeffding, dan Chernoff dengan eksponen $I$ , nyatakanlah dalam satu baris masing-masing: hipotesis yang dituntut, peluruhan yang diperoleh, dan pertanyaan pada soal ini tempat ia paling tajam.

Bagian V — Panennya.

(Menguji sebuah koin) Sebuah koin entah setimbang entah berat sebelah dengan $p = 0.55$ . Kamu melemparnya $n$ kali lalu mengumumkan “berat sebelah” ketika $\widehat p_n > 0.525$ . Tunjukkanlah bahwa kedua peluang galatnya paling banyak $\eu^{-2n(0.025)^2}$ , dan bahwa $n \geq 3685$ lemparan menjamin keduanya di bawah $1\%$ .
(Kejadian langka menuntut batas yang sadar ragam) Misalkan $p = 0.01$ lalu ambillah spesifikasi relatifnya $\delta = p/2 = 0.005$ dan $\alpha = 0.05$ . Bandingkanlah ukuran cuplikan yang dituntut Hoeffding (yakni $n \approx 74\,000$ ) dan yang dituntut Chebyshev dengan ragam benarnya $p(1-p)$ (yakni $n \approx 7920$ ): jadi batas eksponensial yang buta ragam kalah oleh momen kedua yang sederhana. Nyatakanlah pelajarannya, dan dari mana perkakas yang hilangnya (yakni batas eksponensial yang sadar ragam; dan hampiran Poisson pada Bab 23) kelak datang.
(Hukum kuat bagi koin) Dari $\sum_n 2\eu^{-2n\delta^2} < \infty$ dan Borel–Cantelli (Teorema 21.25), buktikanlah bahwa $\widehat p_n \to p$ hampir pasti bagi lemparan koin yang saling bebas: yakni rumuskanlah kejadian hampir pastinya sebagai $\bigcap_j\bigcup_N\bigcap_{n\geq N} \{\abs{\widehat p_n - p} < \tfrac1j\}$ seperti pada Latihan 22.9, lalu simpulkan. (Adapun keterbatasannya menggantikan momen keempat yang dipakai di sana.)
Rangkuman. Dalam lima kalimat: apa yang diharga dan dibeli tiap anak tangganya (yakni momen satu, dua, empat; eksponensial yang terbatas; dan eksponen yang eksak); mengapa menjajaki $2050$ orang sudah cukup bagi sebuah negeri sebesar apa pun; dan batas mana di antaranya yang kelak dipertajam jilid Tahun ke-3 menjadi konstanta eksak teorema limit pusat.

Solusi

Solusi Soal 22.1.

1. $\E(S_n) = \frac n2$ dan Markov (Teorema 22.15) memberi $\P(S_n \geq an) \leq \frac{n/2}{an} = \frac1{2a}$ . Markov hanya mengenal reratanya: ia tak dapat membedakan peubah yang memusat di $n/2$ dari peubah yang tersebar antara $0$ dan $n$ , jadi ia menghargai ekornya seolah-olah seluruh massanya boleh berada di sana.

2. Binomial setimbangnya setangkup terhadap $n/2$ ( $S_n$ dan $n - S_n$ berhukum sama), jadi dengan $x = n(a - \frac12) > 0$ kedua kejadian $\{S_n - \frac n2 \geq x\}$ dan $\{S_n - \frac n2 \leq -x\}$ saling lepas dan sama peluangnya: $\P(S_n \geq an) = \frac12\P(\abs{S_n - \frac n2} \geq x)$ . Chebyshev dengan $V(S_n) = \frac n4$ :

\P(S_n \geq an) \leq \frac12\cdot\frac{n/4}{n^2(a - 1/2)^2} = \frac1{8n(a - 1/2)^2},

yang bernilai $\frac2n$ di $a = \frac34$ .

3. Menurut kesalingbebasan dan teorema hasil kalinya, $\E(\eu^{tS_n}) = \bigl(\E \eu^{tX_1}\bigr)^n = \bigl(\frac{1 + \eu^t}2\bigr)^n$ . Markov yang diterapkan pada $\eu^{tS_n}$ :

\P(S_n \geq an) \leq \eu^{-tan}\Bigl(\frac{1 + \eu^t}2\Bigr)^{\!n} = \exp\Bigl(n\bigl(\ln\tfrac{1 + \eu^t}2 - ta\bigr)\Bigr).

Turunan pangkatnya terhadap $t$ adalah $\frac{\eu^t}{1 + \eu^t} - a$ , yang lenyap di $\eu^t = \frac a{1-a}$ , yakni $t^* = \ln\frac a{1-a} > 0$ ; di sana $\frac{1 + \eu^{t^*}}2 = \frac1{2(1-a)}$ dan pangkatnya sama dengan

n\Bigl(-\ln 2 - \ln(1-a) - a\ln\frac a{1-a}\Bigr) = -n\bigl(\ln2 + a\ln a + (1-a)\ln(1-a)\bigr) = -n\,I(a),

dengan $I(\frac12) = 0$ dan $I'(a) = \ln\frac a{1-a} > 0$ pada $\intoo{\frac12}1$ : $I(a) > 0$ . Di $a = \frac34$ : $\eu^{-I(3/4)} = \frac12(\tfrac34)^{-3/4}(\tfrac14)^{-1/4} = 2\cdot3^{-3/4}$ , yakni batas pada Latihan 22.7.

4. Sebanyak $n + 1$ bilangan $\binom nja^j(1-a)^{n-j}$ berjumlah $1$ , dan yang terbesar adalah yang di $j = k = an$ (modus $\mathcal B(n, a)$ di sini adalah $\floor{(n+1)a} = k$ ). Maksimum dari $n + 1$ bilangan yang berjumlah $1$ paling kecil adalah $\frac1{n+1}$ :

\binom nk a^k(1-a)^{n-k} \geq \frac1{n+1} \quad\Longrightarrow\quad \binom nk \geq \frac{a^{-an}(1-a)^{-n(1-a)}}{n+1} = \frac{\eu^{nH(a)}}{n+1}.

Jadi $\P(S_n \geq an) \geq \binom{n}{an}2^{-n} \geq \eu^{n(H(a) - \ln2)}/(n+1) = \eu^{-nI(a)}/(n+1)$ : sampai faktor suku banyaknya $n + 1$ , pangkat Chernoff itulah kebenarannya.

5. $n = 100$ , $a = \frac34$ : Markov $\frac23$ ; Chebyshev $\frac2{100} = 0.02$ ; Chernoff $(2\cdot3^{-3/4})^{100} = \eu^{-100\,I(3/4)} \approx 2.1\cdot10^{-6}$ , terhadap nilai persisnya $2.8\cdot10^{-7}$ . Pelajarannya: setiap momen informasi membagi batasnya secara suku banyak; adapun momen eksponensialnya mengubah sifatnya.

6. $\cosh t = \sum_{k\geq0}\frac{t^{2k}}{(2k)!}$ dan $\eu^{t^2/2} = \sum_{k\geq0}\frac{t^{2k}}{2^kk!}$ ; klaimnya menyusul suku demi suku dari $(2k)! \geq 2^kk!$ , yang berlaku menurut induksi: $(2k)! = 2k(2k-1)\cdot(2k-2)! \geq 2k\cdot 2^{k-1}(k-1)! = 2^kk!\cdot(2k-1) \geq 2^kk!$ .

7. Menurut kesalingbebasannya, $\E\bigl(\eu^{t\sum\varepsilon_i} \bigr) = (\cosh t)^n \leq \eu^{nt^2/2}$ , jadi Markov memberi $\P(\sum\varepsilon_i \geq s) \leq \eu^{nt^2/2 - ts}$ ; dengan meminimumkannya di $t = s/n$ diperoleh $\eu^{-s^2/(2n)}$ .

8. Dengan $X_i = \frac{1 + \varepsilon_i}2$ , $\widehat p_n - \frac12 = \frac1{2n}\sum\varepsilon_i$ , jadi $\{\widehat p_n - \frac12 \geq \delta\} = \{\sum\varepsilon_i \geq 2n\delta\}$ dan pertanyaan 7 memberi batas $\eu^{-(2n\delta)^2/(2n)} = \eu^{-2n\delta^2}$ . Kejadian setangkupnya berbatas sama, dari situlah faktor $2$ bagi $\abs{\widehat p_n - \frac12} \geq \delta$ .

9. $\E(\eu^{tX}) = \sum_x\eu^{tx}\P(X = x)$ merupakan deret fungsi mulus dari $t$ yang turunan suku demi sukunya terdominasi, pada setiap selang- $t$ kompak, oleh $\eu^{\abs t}\P(X = x)$ (sebab $0 \leq x \leq 1$ ): menurut teorema penurunan bagi deret yang konvergen normal (Teorema 10.7) ia dua kali terdiferensialkan, dan aturan hasil baginya memberi $\psi' = \E_t(X)$ dan $\psi'' = \E_t(X^2) - \E_t(X)^2$ , dengan $\E_t$ menyatakan nilai harapan bagi bobot yang ditimbang ulang $\eu^{tx}\P(X{=}x)/\E(\eu^{tX})$ — taknegatif, berjumlah $1$ , ditopang oleh nilai yang sama $x \in \intcc01$ . Ragam sebuah peubah bernilai- $\intcc01$ paling besar $\frac14$ : menurut Latihan 22.6, ia sama dengan $\min_c\E_t((X - c)^2) \leq \E_t\bigl((X - \tfrac12)^2\bigr) \leq \tfrac14$ . Taylor dengan sisa integral, memakai $\psi(0) = 0$ , $\psi'(0) = p$ :

\psi(t) = tp + \int_0^t(t - s)\,\psi''(s)\,\dd s \leq tp + \frac{t^2}2\cdot\frac14,

yakni $\E(\eu^{t(X - p)}) \leq \eu^{t^2/8}$ untuk semua $t$ real.

10. Menurut kesalingbebasannya, $\E\bigl(\eu^{t(S_n - np)}\bigr) \leq \eu^{nt^2/8}$ ; Markov dan pengoptimuman $t = 4\delta$ memberi

\P(\widehat p_n - p \geq \delta) \leq \eu^{nt^2/8 - tn\delta}\Big|_{t = 4\delta} = \eu^{-2n\delta^2};

adapun penerapannya pada peubah $1 - X_i$ (yang juga di $\intcc01$ ) membatasi ekor lainnya, dari situlah batas dua sisi $2\eu^{-2n\delta^2}$ .

11. Chebyshev hanya perlu momen kedua lalu memberi $\frac{p(1-p)}{n\delta^2}$ ; Hoeffding perlu keterbatasan lalu memberi $2\eu^{-2n\delta^2}$ . Di $p = \frac12$ , $\delta = 0.03$ : batasnya adalah $\frac{278}{n}$ (kira-kira) berbanding $2\eu^{-0.0018n}$ ; keduanya berpotongan dekat $n \approx 1200$ , dan setelah itu batas eksponensialnya menang, bahkan menang telak ( $n = 5000$ : $0.056$ berbanding $2.5\cdot10^{-4}$ ).

12. Menurut Hoeffding (pertanyaan 10), $\P(\abs{\widehat p_n - p} \geq \delta) \leq 2\eu^{-2n\delta^2} \leq \alpha$ segera setelah $2n\delta^2 \geq \ln\frac2\alpha$ , yakni $n \geq \frac{\ln(2/\alpha)}{2\delta^2}$ .

13. $\delta = 0.03$ , $\alpha = 0.05$ : $n \geq \frac{\ln 40}{2\cdot0.0009} \approx 2049.4$ : $2050$ orang. Untuk $\delta = 0.01$ : $n \geq \frac{\ln40}{0.0002} \approx 18\,445$ . Ukuran populasinya tak pernah muncul sebab setiap pemilih yang tercuplik dimodelkan sebagai pengambilan Bernoulli $(p)$ yang baru: kesulitan jajak pendapatnya terletak pada ragam sekeping koin, bukan pada besarnya negerinya. Memotong separuh galat batasnya berharga empat kali lipat cuplikannya — itulah hukum $1/\delta^2$ .

14. Chebyshev: $\P(\abs{\widehat p_n - p} \geq \delta) \leq \frac{p(1-p)}{n\delta^2} \leq \frac1{4n\delta^2} \leq \alpha$ untuk $n \geq \frac1{4\alpha\delta^2}$ , yakni $5556$ pada tiga poin — sekitar $2.7$ kali kebutuhan Hoeffding. Tanpa pengembalian, ragamnya terkalikan $\frac{N - n}{N-1} < 1$ (Latihan 22.5), jadi $n$ yang sama hanya bisa lebih baik: perhitungan dengan pengembaliannyalah yang konservatif.

15. $\{\widehat p_n \leq \frac12\} \subseteq \{\widehat p_n - 0.52 \leq -0.02\}$ , jadi menurut batas Hoeffding satu sisi $\P(\widehat p_n \leq \tfrac12) \leq \eu^{-2n(0.02)^2} \leq 0.01$ segera setelah $n \geq \frac{\ln 100}{2\cdot0.0004} \approx 5756.5$ : $5757$ pemilih. Biayanya berskala seperti kuadrat kebalikan keunggulannya, bukan kebalikan ketelitian yang diinginkan: pemilihan yang ketat itu mahal.

16. Yang dipakai: cuplikannya diambil secara seragam dan saling bebas dari kumpulan pemilihnya; setiap orang yang tercuplik menjawab, dengan jujur, dan $p$ tak bergerak selama penjajakannya. Jajak pendapat nyata melanggar ketiganya: responden yang terjangkau dan bersedia bukanlah cuplikan seragam (bias pemilihan dan bias tanpa jawaban), dan jawabannya bisa tak jujur atau tak stabil. Semuanya galat bias: ia menggeser $\E(\widehat p_n)$ menjauhi $p$ sebesar suatu jumlah yang tak bergantung pada $n$ , jadi tak ada ukuran cuplikan yang menguranginya — matematika pada Bagian ini hanya mengendalikan suku fluktuasinya.

17. Chebyshev untuk satu kelompok berukuran $m$ : $\P(\abs{ \widehat p^{(i)} - p} \geq \delta) \leq \frac{1}{4m\delta^2} \leq \frac18$ untuk $m \geq \frac2{\delta^2}$ . Bila kelompok yang keliru kurang dari $k/2$ , maka lebih dari $k/2$ di antara nilai $\widehat p^{(i)}$ terletak pada selang buka $\intoo{p - \delta}{p + \delta}$ , begitu pula mediannya; jadi $\{\abs{M - p} \geq \delta\}$ memaksa sedikitnya $\lceil k/2\rceil$ kekeliruan di antara $k$ kelompok yang saling bebas. Batas gabungan atas $\binom k{\lceil k/2\rceil}$ himpunan kelompok keliru yang mungkin memberi

\P(\abs{M - p} \geq \delta) \leq \binom{k}{\lceil k/2\rceil} \Bigl(\frac18\Bigr)^{k/2} \leq 2^k\,8^{-k/2} = 2^{-k/2} :

yakni peluruhan eksponensial terhadap banyaknya kelompok, yang ditebus dengan ragam belaka — berguna justru ketika sukunya takterbatas dan Hoeffding tak tersedia.

18. Cauchy–Schwarz (Teorema 22.19):

\E(X) = \E(X\,\mathbf 1_{X>0}) \leq \sqrt{\E(X^2)}\sqrt{\E(\mathbf 1_{X>0}^2)} = \sqrt{\E(X^2)\,\P(X > 0)} ;

kuadratkan lalu bagi.

19. Ambil $h(a) = I(a) - 2(a - \tfrac12)^2$ . Maka $h(\tfrac12) = 0$ , $h'(a) = \ln\frac a{1-a} - 4(a - \tfrac12)$ lenyap di $\tfrac12$ , dan

h''(a) = \frac1a + \frac1{1-a} - 4 = \frac{1}{a(1-a)} - 4 \geq 0

sebab $a(1-a) \leq \frac14$ . Jadi $h'$ naik dari $0$ pada $\intco{\frac12}1$ , sehingga $h' \geq 0$ dan $h \geq 0$ : $I(a) \geq 2(a - \tfrac12)^2$ .

20. $I(\tfrac12) = I'(\tfrac12) = 0$ , $I''(a) = \frac1{a(1-a)}$ memberi $I''(\tfrac12) = 4$ , dan $I'''(\tfrac12) = 0$ (fungsinya setangkup terhadap $\tfrac12$ ), jadi $I(\tfrac12 + \delta) = 2\delta^2 + O(\delta^4)$ . Pertanyaan 4 lalu membatasi ekor sejatinya dari bawah oleh $\eu^{-n(2\delta^2 + O(\delta^4))}/(n+1)$ : untuk $\delta$ yang kecil pangkat Hoeffding $2n\delta^2$ persis secara asimtotik — hanya perbaikan suku-banyak-dalam- $n$ yang mungkin.

21. Markov: satu momen, peluruhan $1/a$ , berguna hanya sebagai mesin di balik yang lain (pertanyaan 1 menunjukkannya datar). Chebyshev: dua momen, peluruhan $\frac{V}{n\delta^2}$ , tajam tanpa hipotesis tambahan (Contoh 22.18), sekaligus perkakas terbaik pada pertanyaan 23. Momen keempat (Latihan 22.9): peluruhan $C/n^2$ , keterjumlahannya pas cukup untuk sebuah hukum kuat. Hoeffding: peubah terbatas, peluruhan $2\eu^{-2n\delta^2}$ , kuda beban Bagian III. Chernoff dengan laju persisnya $I(a)$ : momen eksponensial penuh, pangkat yang tak terkalahkan (pertanyaan 4, 20), titik acuan bagi segala yang lain.

22. Bila koinnya setimbang: $\P(\widehat p_n > 0.525) \leq \P(\widehat p_n - \tfrac12 \geq 0.025) \leq \eu^{-2n(0.025)^2}$ . Bila $p = 0.55$ : $\P(\widehat p_n \leq 0.525) \leq \P(\widehat p_n - 0.55 \leq -0.025) \leq \eu^{-2n(0.025)^2}$ . Kedua galatnya di bawah $0.01$ ketika $2n(0.025)^2 \geq \ln 100$ , yakni $n \geq 3684.2$ : $3685$ lemparan. (Membedakan hipotesis yang terpaut $2.5$ poin berharga sama dengan menaksir sampai ketelitian $\pm2.5$ poin.)

23. Hoeffding: $n \geq \frac{\ln 40}{2(0.005)^2} \approx 73\,778$ . Chebyshev dengan ragam sejatinya $p(1-p) = 0.0099$ : $n \geq \frac{0.0099}{0.05\cdot(0.005)^2} = 7920$ — sembilan kali lebih murah. Pangkat Hoeffding $2n\delta^2$ menghargai ragamnya pada kasus terburuknya $\frac14$ , yang pesimistis secara ganjil ketika $p = 0.01$ ; adapun momen kedua yang sederhana itu lebih tahu. Perkakas yang hilang adalah batas eksponensial yang sadar-ragam (ketaksamaan Bernstein, Tahun ke-3) — atau, untuk kejadian langka, hampiran Poisson yang dibuktikan pada Bab 23, yang bekerja pada skala nisbi yang alami.

24. Tetapkan $\delta > 0$ : $\sum_n 2\eu^{-2n\delta^2} < \infty$ (deret bertipe geometrik), jadi Borel–Cantelli 1 (Teorema 21.25) memberi $\P(\abs{\widehat p_n - p} \geq \delta \text{ tak hingga kali}) = 0$ , yakni kejadian $E_j = \bigcup_N\bigcap_{n\geq N}\{\abs{\widehat p_n - p} < \tfrac1j\}$ berpeluang $1$ untuk setiap $j$ . Irisan terbilang $\bigcap_jE_j$ tetap berpeluang $1$ (kesubaditifan pada komplemennya), dan padanya $\widehat p_n \to p$ : itulah hukum kuat bilangan besar untuk lemparan koin, dengan keterbatasan memainkan peran yang dimainkan momen keempat pada Latihan 22.9.

25. Satu momen membeli batas yang datar; dua membeli $1/(n\delta^2)$ , tak lebih (contoh ketajamannya); empat membeli $1/n^2$ , cukup untuk meneleskopkannya menjadi hukum hampir pasti; keterbatasan membeli $\eu^{-2n\delta^2}$ ; dan momen eksponensial penuh membeli laju persisnya $I$ , yang tak terkalahkan oleh metode mana pun. Menjajaki $2050$ orang memadai bagi negeri mana pun sebab fluktuasi cuplikannya dikendalikan oleh ragam koinnya, bukan oleh besarnya populasi — banderol $1/\delta^2$ dan $\ln(1/\alpha)$ berlaku semesta. Teorema limit pusat pada jilid Tahun ke-3 menggantikan ketaksamaan ini, pada skala $\sqrt n$ , dengan hukum limit persis berkonstanta eksplisit — yang mengubah setiap batas pada masalah ini menjadi kesamaan asimtotik.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium