Lempar 100 koin cantik dan singkirkan ekornya; lempar koin yang tersisa dan ambil ekornya. Lanjutkan sampai tidak ada koin yang tersisa. [duplikat]

Question

100 peserta masing-masing memiliki koin yang adil, pada putaran tertentu, peserta yang belum dibuang membalik koin mereka, mereka yang membalikkan ekor akan dibuang dari permainan, sisanya terus bermain sampai tidak ada yang tersisa (semua orang telah dibuang).

1. Berapa jumlah rata-rata percobaan (di mana setiap percobaan terdiri dari melempar dan melepaskan ekor) yang diharapkan dari melakukan percobaan ini?

2. Apakah ekspektasi bersyarat berhasil untuk sesuatu seperti ini?

Saya tahu bahwa setiap koin individu mengikuti distribusi Geometris, tetapi saya mencoba mencari jumlah mereka untuk menentukan jumlah rata-rata percobaan untuk permainan seperti ini.

Proses Logika / Pemikiran Saya: Saya mulai mencoba memikirkan kemungkinan bahwa koin tertentu bisa berputar $r$ yang mana $\frac{1}{2^m}$. Saya kemudian menyadari bahwa setiap hasil koin dapat dimodelkan oleh variabel acak geometris dengan$p = 0.5$. Saya sekarang tidak yakin bagaimana cara mengambil lompatan dari kasing tunggal ini ke kasing dengan 100 koin. Saya menganggap ini ada hubungannya dengan menjumlahkan variabel acak geometris, tetapi saya tidak yakin.

Answer 1

Ini pada dasarnya sama dengan menghitung nilai maksimum yang diharapkan$n=100$variabel acak geometris iid , untuk$p=\frac12$

(BTW: Pertanyaan terkait termasuk rekursi yang diberikan oleh jawaban @ saulspatz)

Tidak ada solusi bentuk tertutup, tetapi perkiraan ini besar $n$ (dengan batas) diberikan:

$$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n$$

dimana $\lambda = - \log(1-p)=0.69314718\cdots$ dan $H_n$ adalah nomor harmonik.

Misalnya untuk $n=3$ ini memberi $E_3 \approx 3.14494$ , sangat dekat persis $E_3=22/7=3.14285$

Untuk $n=100$ ini memberi $E_{100} \approx 7.98380382$.

Lebih lanjut dalam "Namun aplikasi lain dari statistik urutan pengulangan binomial", W. Szpankowski; V.Rego, Komputasi, 1990, 43, 4, 401-410.

Answer 2

Saya ragu ada ekspresi sederhana untuk ekspektasi itu. Membiarkan$E_n$ menjadi jumlah percobaan yang diharapkan saat $n$ koin tetap ada, jadi kita diminta untuk menghitung $E_{100}$. Kami tahu itu$E_0=0$ dan itu $E_1=2$. Sekarang$$E_2=1+\frac14E_2+\frac12E_1+\frac14E_0$$ karena kita harus melakukan satu percobaan, dan dengan kemungkinan $\frac14$ kita melempar dua kepala dan masih memiliki dua koin, dengan kemungkinan $\frac12$ kita melempar kepala dan ekor, dan dengan probabilitas $\frac14$, kami melempar dua ekor, dan eksperimen berakhir. Ini memberi$E_2=\frac83$.

Kami dapat melanjutkan dengan cara ini: $$E_3=1+\frac18E_3+\frac38E_2+\frac38E_1+\frac18E_0$$ yang memberikan $E_3=\frac{22}7$ jika aku tidak salah.

Seseorang dapat dengan mudah menulis program komputer untuk dikerjakan kembali $E_{100}$, tetapi akan lebih mudah untuk melanjutkan dengan simulasi.

EDIT

Saya menulis naskah yang saya sarankan. Nilai pasti jika pecahan yang pembilangnya memiliki$894$ angka desimal dan penyebutnya memiliki $893$. Nilai perkiraannya adalah$7.98380153515692$.

Answer 3

Mencari OEIS dengan nilai pertama @saulspatz, kita dapat menemukan bahwa:

$$E_n = \frac{a(n)}{b(n)}$$

dimana $a(n)$adalah OEIS A158466 dan$b(n)$adalah OEIS A158467 . Di OEIS A158466 Anda juga dapat menemukan rumus berikut:

$$E_n = -\sum_{k=1}^n (-1)^k \frac{{n \choose k}}{1-\frac{1}{2^k}}$$

$$E_n = \sum_{k=1}^{\infty} k \left(\left(1-\frac{1}{2^k}\right)^n - \left(1-\frac{1}{2^{k-1}}\right)^n\right)$$

dan dengan demikian (lihat di sini ):

$$E_{100} \approx 7.983801535$$

Answer 4

Set $N_0=100$ dan ambil $N_k$ menjadi jumlah koin yang tersisa setelah $k^\text{th}$uji coba dalam proses ini. Jadi kita bisa mengatakan sesuatu seperti$$P(N_1=81|N_0=100)={100 \choose 19}\Big(\frac{1}{2}\Big)^{100}$$

Sekarang untuk $i\in \{0,1,\ldots, 100\}$ dan $j\in \{0,1,\ldots ,i\}$ kita punya $$P(N_{k+1}=j|N_{k}=i)={i \choose j-i}\Big(\frac{1}{2}\Big)^i$$ Memperhatikan $\{N_k\}_{k=0}^{\infty}$ adalah rantai Markov yang menyerap dengan $0$sebagai keadaan menyerap. Anda ingin menghitung jumlah uji coba yang diharapkan dalam proses acak ini sebelum diserap dalam status$0$ mulai dari negara bagian $100$. Ada banyak cara untuk menghitung nilai yang diharapkan ini, yang paling efisien mungkin dengan memanfaatkan matriks fundamental yang dapat Anda pelajari di sini