Nilai yang Diharapkan dari membalik-balik buku
Misalkan sebuah buku memiliki $N$halaman, dan kami membaca buku sebagai berikut. Kita mulai dari halaman 0, dan jika kita berada di halaman$i$, kami membalik halaman secara acak $i + 1, i + 2, ..., N$ dengan probabilitas yang sama.
- Berapa nilai yang diharapkan dari jumlah membalik yang kita butuhkan untuk menyelesaikan buku?
Intuisi memberi tahu saya bahwa kita bisa, rata-rata, berharap untuk mengurangi setengah dari jumlah halaman yang tersisa. Ini hasil$\log_2(N)$, tapi saya kesulitan memformalkannya.
- Jika $N = 26$, berapa probabilitas kita beralih ke halaman 13 pada suatu saat? Asumsikan kita mulai dari halaman 0.
Saya biarkan $P_i$ jadilah kemungkinan kita sampai di halaman 13 pada akhirnya, mulai dari halaman $i$. Kemudian,$P_{13} = 1$, dan secara umum, $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$
Mengevaluasi istilah seperti $P_{12}, P_{11}, P_{10}$, Saya melihat bahwa semua nilai ini $\frac{1}{14}$, termasuk $P_0$. Apakah ada alasan yang lebih intuitif untuk jawaban yang begitu sederhana?
Jawaban
Mari pertimbangkan masalah yang setara di mana kita mulai dari halaman $n$ dan membalikkan buku ke belakang, membuka setiap halaman $0, 1, ..., n - 1$dengan probabilitas yang sama. Membiarkan$E_n$menjadi jumlah membalik yang diharapkan. Lalu kita punya$E_0 = 0$ dan
$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$
Kemudian secara khusus kami miliki
\ begin {persamaan} \ begin {split} E_ {n + 1} & = 1 + \ frac {1} {n + 1} \ sum \ limit_ {i = 0} ^ {n} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} \ frac {1} {n} \ sum \ limit_ {i = 0} ^ {n - 1} E_i \\ & = 1 + \ frac {E_n} {n + 1} + \ frac {n} {n + 1} (1 + \ frac {1} {n} \ sum \ limit_ {i = 0} ^ {n - 1} E_i) - \ frac {n} {n + 1} \\ & = 1 - \ frac {n} {n + 1} + \ frac {1} {n + 1} E_n + \ frac {n} {n + 1} E_n \\ & = \ frac {1} {n + 1} + E_n \ end {split} \ end {persamaan}
kapanpun $n \geq 1$ (dan identitas mudah diverifikasi bila $n = 0$ demikian juga).
Kemudian dengan induksi, kita punya $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, itu $n$nomor harmonik. Ini akan sangat dekat secara asimtotik$\log_e(n)$.
Membiarkan $P_n$ menjadi jumlah membalik yang diharapkan dalam buku dengan $n$halaman. Kemudian$P_0=0,\ P_1=1$ dan $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ karena kita harus membuat satu flip, dan kemudian kita sama-sama cenderung memiliki sejumlah halaman dari $0$ untuk $n-1$ kiri untuk membalik.
Kita mendapatkan $$\begin{align} P_1&=1\\ P_2&=\frac32\\ P_3&=\frac{11}6\\ P_4&=\frac{50}{24}\\ P_5&=\frac{174}{120} \end{align}$$
Penyebutnya jelas $n!$, jadi kami mencari pembilangnya di OEIS dan menemukan A000254 , nomor Stirling yang tidak bertanda tangan dari jenis pertama.
OESI memberikan pengulangan $$a_{n+1}=(n+1)a_n+n!$$ untuk nomor Stirling unsigned dari jenis pertama, dan membaginya dengan $(n+1)!$ kita mendapatkan $$P_{n+1}=P_n+\frac1{n+1}$$ yang dengan jelas memberi $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ itu $n$nomor harmonik. Untuk menyelesaikan masalah, kita harus menunjukkan bahwa bilangan harmonik memenuhi pengulangan$(1)$.
Giliranmu.
Inilah cara saya mendekati bagian pertama dari masalah tersebut. Pertimbangkan buku dengan tepat$n$halaman. Membiarkan$P_1$ menunjukkan halaman pertama yang Anda buka, dan biarkan $X_n$mewakili jumlah halaman yang Anda balik sampai Anda mencapai halaman terakhir. Catatan$P_1$ didistribusikan secara seragam di lokasi syuting $\{1,...,n\}$ dan $E(X_1)=1$. Menggunakan hukum ekspektasi total yang kita dapatkan$n\geq2$ bahwa $$E(X_n)=\sum_{k=1}^{n}E(X_n|P_1=k)P(P_1=k)=\frac{1}{n}\sum_{k=1}^{n}E(X_n|P_1=k)$$
Memperhatikan $E(X_n|P_1=k)=1+E(X_{n-k})$ sehingga $$E(X_n)=\frac{1}{n}\sum_{k=1}^{n}\Big[1+E(X_{n-k})\Big]=1+\frac{E(X_0)+\dots+E(X_{n-1})}{n}$$ Menggantikan $n$ dengan $n+1$ mendapatkan $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ Menggabungkan dua persamaan sebelumnya mengungkap relasinya $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ yang setara dengan ucapan $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ Jadi akhirnya $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$