Apa yang dimaksud dengan batas bawah ketat pada waktu pengumpul kupon?

20

Dalam masalah klasik Kupon Kolektor , diketahui bahwa waktu diperlukan untuk menyelesaikan satu set kupon yang dipilih secara acak memenuhi , , dan . $T$ $n$ $E[T] \sim n \ln n$ $Var(T) \sim n^2$ $\Pr(T > n \ln n + cn) < e^{-c}$

Batas atas ini lebih baik daripada yang diberikan oleh ketidaksetaraan Chebyshev, yang kira-kira $1/c^2$ .

Pertanyaan saya adalah: apakah ada yang sesuai yang lebih baik dari Chebyshev batas bawah untuk $T$ ? (mis. sesuatu seperti $\Pr(T < n \ln n - cn) < e^{-c}$ )?

probability probability-inequalities coupon-collector-problem David
sumber

Batas bawah yang jelas adalah

Pr (T < n) = 0

$\Pr(T<n) = 0$ , tapi saya rasa Anda tahu itu ...

onestop

14

Saya memberikan ini sebagai jawaban kedua karena analisisnya benar-benar dasar dan memberikan hasil yang diinginkan.

Proposisi Untuk $c > 0$ dan $n \geq 1$ ,

P (T < n \log n - c n) < e^{- c} .

$\mathbb{P}(T < n \log n - c n ) < e^{-c} \>.$

Gagasan di balik buktinya sederhana:

waktu sampai semua kupon dikumpulkan sebagai $T = \sum_{i=1}^n T_i$ , di mana $T_i$ adalah waktu di mana kupon unik ke- $i$ (sampai sekarang) dikumpulkan. The adalah variabel acak geometris dengan waktu rata-rata . $T_i$ $\frac{n}{n-i+1}$
Terapkan versi Chernoff terikat dan sederhanakan.

Bukti

Untuk dan sembarang , kita memiliki itu $t$ $s > 0$

P (T < t) = P (e^{- s T} > e^{- s t}) \leq e^{s t} E e^{- s T} .

$\mathbb{P}(T < t) = \mathbb{P}( e^{-s T} > e^{-s t} ) \leq e^{s t} \mathbb{E} e^{-s T} \> .$

Karena dan independen, kita dapat menulis $T = \sum_i T_i$ $T_i$

E e^{- s T} = \prod_{saya = 1}^{n} E e^{- s T_{saya}}

$\mathbb{E} e^{-s T} = \prod_{i=1}^n \mathbb{E} e^{- s T_i}$

Sekarang karena adalah geometris, katakanlah dengan probabilitas keberhasilan , maka perhitungan sederhana menunjukkan $T_i$ $p_i$

E e^{- s T_{saya}} = \frac{{hal}_{saya}}{e^{s} - 1 + {hal}_{saya}} .

$\mathbb{E} e^{-s T_i} = \frac{p_i}{e^s - 1 + p_i} .$

The untuk masalah kita adalah , , , dll Oleh karena itu, $p_i$ $p_1 = 1$ $p_2 = 1 - 1/n$ $p_3 = 1 - 2/n$

\prod_{saya = 1}^{n} E e^{- s T_{saya}} = \prod_{saya = 1}^{n} \frac{saya / n}{e^{s} - 1 + saya / n} .

$\prod_{i=1}^n \mathbb{E} e^{-s T_i} = \prod_{i=1}^n \frac{i/n}{e^s - 1 + i/n}.$

Mari kita pilih dan untuk beberapa . Kemudian dan , menghasilkan $s = 1/n$ $t = n \log n - c n$ $c > 0$

e^{s t} = n e^{- c}

$e^{s t} = n e^{-c}$

e^{s} = e^{1 / n} \geq 1 + 1 / n

$e^s = e^{1/n} \geq 1 + 1/n$

\prod_{saya = 1}^{n} \frac{saya / n}{e^{s} - 1 + saya / n} \leq \prod_{saya = 1}^{n} \frac{saya}{saya + 1} = \frac{1}{n + 1} .

$\prod_{i=1}^n \frac{i/n}{e^s - 1 + i/n} \leq \prod_{i=1}^n \frac{i}{i+1} = \frac{1}{n+1} \> .$

Menyatukan ini, kita mendapatkan

P (T < n \log n - c n) \leq \frac{n}{n + 1} e^{- c} < e^{- c}

$P(T < n \log n - c n) \leq \frac{n}{n+1} e^{-c} < e^{-c}$

seperti yang diinginkan.

kardinal
sumber

Itu sangat bagus dan hanya apa yang diperintahkan dokter. Terima kasih.

David

@ David, hanya ingin tahu: Apa aplikasi yang dimaksud?

kardinal

Cerita panjang. Saya mencoba untuk membuktikan batas bawah untuk waktu pencampuran rantai Markov yang telah saya buat untuk menganalisis waktu berjalan suatu algoritma yang saya minati - yang ternyata berkurang hingga batas yang lebih rendah dari c masalah kolektor. BTW, saya telah bermain-main dengan mencoba menemukan dengan tepat jenis gaya Chernoff terikat ini, tetapi belum menemukan cara untuk menyingkirkan produk itu di . Panggilan bagus memilih :-).

i

$i$

s = 1 / n

$s = 1/n$

David

@ David, , sementara hampir pasti suboptimal, sepertinya hal yang jelas untuk dicoba karena memberi , yang merupakan istilah yang sama dengan yang diperoleh dalam derivasi untuk batas atas.

s = 1 / n

$s = 1/n$

e^{s t} = n e^{- c}

$e^{s t} = n e^{-c}$

kardinal

1

Permintaan : Bukti yang saya berikan di atas adalah milik saya. Saya mengerjakannya karena senang, karena masalahnya membuat saya penasaran. Namun, saya tidak mengklaim hal-hal baru. Memang, saya tidak bisa membayangkan bahwa bukti yang sama menggunakan teknik yang sama belum ada dalam literatur. Jika ada yang tahu referensi, silakan posting sebagai komentar di sini. Saya akan sangat tertarik untuk mengetahui satu.

kardinal

9

Meskipun @ cardinal telah memberikan jawaban yang memberikan batasan tepat yang saya cari, saya telah menemukan argumen gaya Chernoff yang serupa yang dapat memberikan batasan yang lebih kuat:

Proposisi : (ini lebih kuat untuk )

P r (T \leq n \log n - c n) \leq \exp (- \frac{3 c^{2}}{π^{2}}) .

$Pr (T \leq n \log n - c n) \leq \exp(- \frac{3c^2}{\pi^2} ) \> .$

c > \frac{π^{2}}{3}

$c > \frac{\pi^2}{3}$

Bukti :

Seperti dalam jawaban @ cardinal, kita dapat menggunakan fakta bahwa adalah jumlah variabel acak geometris independen dengan probabilitas keberhasilan . Oleh karena itu, dan . $T$ $T_i$ $p_i = 1 - i/n$ $E[T_i] = 1/p_i$ $E[T] = \sum_{i=1}^{n} E[T_i] = n \sum_{i=1}^n \frac{1}{i}\geq n \log n$

Tentukan sekarang variabel baru , dan . Kita kemudian dapat menulis $S_i : = T_i - E[T_i]$ $S : = \sum_i S_i$

Pr (T \leq n \log n - c n) \leq Pr (T \leq E [T] - c n) = Pr (S \leq - c n)

$\Pr (T \leq n \log n - c n) \leq \Pr (T \leq E[T] - c n) = \Pr (S \leq - c n)$

= Pr (\exp (- s S) \geq \exp (s c n)) \leq e^{- s c n} E [e^{- s S}]

$= \Pr\left(\exp(-s S ) \geq \exp( s cn) \right) \leq e^{-s c n} E\left[ e^{-s S} \right]$

Menghitung rata-rata, yang kita miliki

E [e^{- s S}] = \prod_{saya} E [e^{- s S_{saya}}] = \prod_{saya} \frac{e^{s / {hal}_{saya}}}{1 + \frac{1}{{hal}_{saya}} (e^{s} - 1)} \leq e^{\frac{1}{2} s^{2} \sum_{saya} {hal}_{saya}^{- 2}}

$E[e^{-s S}] = \prod_i E[e^{-s S_i}] = \prod_i \frac{e^{s / p_i} } {1 + \frac{1}{p_i} (e^s -1)} \leq e^{\frac{1}{2}s^2\sum_i p_i^{-2}}$ mana ketidaksetaraan mengikuti dari fakta bahwa dan juga untuk .

e^{s} - 1 \geq s

$e^s - 1\geq s$

\frac{e^{z}}{1 + z} \leq e^{\frac{1}{2} z^{2}}

$\frac{e^z}{1+z}\leq e^{\frac{1}{2}z^2}$

z \geq 0

$z\geq 0$

Jadi, karena , kita dapat menulis $\sum_i p_i ^{-2} = n^2 \sum_{i=1}^{n-1} \frac{1}{i^2} \leq n^2 \pi^2/6$

\begin{aligned} Pr (T \leq n \log n - c n) \leq e^{\frac{1}{12} (n π s)^{2} - s c n} . \end{aligned}

$\begin{align*} \Pr( T \leq n \log n - c n ) \leq e^{\frac{1}{12} (n \pi s)^2 - s c n}. \end{align*}$

Meminimalkan lebih dari , kami akhirnya memperoleh $s>0$

Pr (T \leq n \log n - c n) \leq e^{- \frac{3 c^{2}}{π^{2}}}

$\Pr( T \leq n\log n -cn ) \leq e^{-\frac{3 c^2 }{\pi^2}}$

David
sumber

1

(+1) Modulo beberapa kesalahan ketik kecil, ini bagus. Memperluas sekitar sesuatu yang dekat dengan rata-rata seperti yang telah Anda lakukan seringkali bekerja lebih baik. Saya tidak terkejut melihat konvergensi tatanan yang lebih tinggi mengingat hasil asimptotik. Sekarang, jika Anda menunjukkan serupa seperti batas atas, yang membuktikan adalah subexponential dalam terminologi Vershynin, yang memiliki banyak implikasi mengenai konsentrasi ukuran.

(T - n \log n) / n

$(T-n\log n)/n$

kardinal

1

Argumen itu tampaknya tidak menggeneralisasi langsung ke batas atas. Sambil menukar untuk (dan untuk ), seseorang dapat mengikuti langkah-langkah yang sama hingga titik menghitung . Namun, pada titik ini, yang terbaik yang bisa saya lakukan adalah menggunakan , yang masih menyisakan dan saya tidak tidak tahu harus berbuat apa dengan ini

c

$c$

- c

$-c$

s

$s$

- s

$-s$

E [e^{s S}] \leq \prod_{i} \frac{e^{- s / p_{i}}}{1 - \frac{s}{p_{i}}}

$E[e^{sS}] \leq \prod_i \frac{e^{-s/p_i}}{1 - \frac{s}{p_i}}$

\frac{e^{- z}}{1 - z} \leq \exp (\frac{z^{2}}{2 (1 - z)})

$\frac{e^{-z}}{1-z} \leq \exp( \frac{z^2}{2(1-z)} )$

E [e^{s S}] \leq e^{\frac{1}{2} s^{2} \sum_{saya} \frac{{hal}_{saya}^{2}}{(1 - s / {hal}_{saya})}}

$E[e^{sS}] \leq e^{\frac{1}{2} s^2\sum_i \frac{p_i^2}{(1-s/p_i)}}$

David

2

Yang cukup menarik, meskipun, seluruh argumen (untuk batas bawah) tampaknya bekerja tidak hanya untuk masalah kupon kolektor, tetapi untuk setiap jumlah non-identik, variabel geometri independen dengan varians terbatas. Khususnya: diberikan , di mana setiap adalah GV independen dengan probabilitas keberhasilan , dan di mana , kemudian

T = \sum_{i} T_{i}

$T = \sum_i T_i$

T_{i}

$T_i$

p_{i}

$p_i$

\sum_{i} p_{i}^{- 2} \leq A < \infty

$\sum_i p_i^{-2} \leq A < \infty$

Pr (T \leq E [T] - Sebuah) \leq e^{- \frac{{Sebuah}^{2}}{2 SEBUAH}}

$\Pr ( T \leq E[T] - a ) \leq e^{-\frac{a^2}{2A}}$

David

4

Catatan Penting : Saya telah memutuskan untuk menghapus bukti yang saya berikan pada awalnya di jawaban ini. Itu lebih lama, lebih komputasional, menggunakan palu yang lebih besar, dan membuktikan hasil yang lebih lemah dibandingkan dengan bukti lain yang saya berikan. Di sekitar, pendekatan yang lebih rendah (dalam pandangan saya). Jika Anda benar - benar tertarik, saya kira Anda dapat melihat hasil edit.

Hasil asimptotik yang saya kutip semula dan yang masih ditemukan di bawah dalam jawaban ini menunjukkan bahwa sebagai kita dapat melakukan sedikit lebih baik daripada yang dibuktikan dalam jawaban lain, yang berlaku untuk semua . $n \to \infty$ $n$

Hasil asimptotik berikut ini berlaku

P (T > n \log n + c n) \to 1 - e^{- e^{- c}}

$\mathbb{P}(T > n \log n + c n ) \to 1 - e^{-e^{-c}}$

dan

P (T \leq n \log n - c n) \to e^{- e^{c}} .

$\mathbb{P}(T \leq n \log n - c n ) \to e^{-e^c} \>.$

Konstanta dan batasannya diambil sebagai . Perhatikan bahwa, meskipun dipisahkan menjadi dua hasil, hasilnya hampir sama karena tidak dibatasi menjadi tidak negatif dalam kedua kasus. $c \in \mathbb{R}$ $n \to \infty$ $c$

Lihat, misalnya, Motwani dan Raghavan, Randomized Algorithms , hal. 60--63 untuk bukti.

Juga : David dengan ramah memberikan bukti untuk batas atas yang dinyatakan dalam komentar untuk jawaban ini.

kardinal
sumber

Ya, itu berlaku untuk setiap tetap . Bukti (sangat sederhana) dapat ditemukan, misalnya dalam buku Levin, Peres dan Wilmer, Markov Chains and Mixing Times, Proposisi 2.4. Buktinya tidak bekerja untuk batas bawah.

n

$n$

David

1

Bahkan, saya mungkin juga menuliskan bukti di sini: "Biarkan menjadi peristiwa bahwa tipe [kupon] ke- tidak muncul di antara kupon pertama yang diambil. Perhatikan dulu bahwa . Karena setiap percobaan memiliki probabilitas tidak menggambar kupon dan uji coba independen, sisi kanan di atas dibatasi di atas oleh , membuktikan (2.7). "

A_{i}

$A_i$

i

$i$

n \log n + c n

$n \log n + cn$

P (τ > n \log n + c n) = P (\cup_{i} A_{i}) \leq \sum_{i} P (A_{i})

$P(\tau >n\log n+cn )=P (\cup_{i} A_i ) \leq \sum_i P(A_i)$

1 - n^{- 1}

$1 − n^{−1}$

i

$i$

\sum_{i} (1 - 1 / n)^{n \log n + c n} \leq n \exp (\frac{n \log n + c n}{n}) = e^{- c}

$\sum_i (1 - 1/n)^{n \log n + cn} \leq n \exp(\frac{n \log n + cn}{n} ) = e^{-c}$

David

@ David, itu bagus dan cukup sederhana. Saya dengan cepat bermain dengan memperluas formula inklusi-eksklusi oleh istilah lain, tetapi tidak sampai ke mana-mana dengan cepat dan belum punya waktu untuk melihatnya lebih jauh. Acara setara dengan acara yang tidak ada kupon yang tersisa setelah uji coba . Harus ada martingale yang terkait dengan itu. Apakah Anda mencoba ketidaksetaraan Hoeffding pada martingale terkait (dianggap)? Hasil asimptotik menunjukkan konsentrasi ukuran yang kuat.

{T < t_{n}}

$\{T < t_n\}$

t_{n}

$t_n$

kardinal

@ David, ada flip tanda di bukti Anda di atas, tapi saya yakin itu jelas bagi pembaca lain juga.

kardinal

@ David, silakan lihat jawaban saya yang diposting untuk pertanyaan Anda. Metodenya berbeda dari batas atas yang Anda berikan, tetapi alat yang digunakan hampir sama mendasar, berbeda dengan jawaban yang saya berikan di sini.

kardinal

2

Benjamin Doerr memberikan (dalam bab "Menganalisis Heuristik Pencarian Acak: Alat dari Teori Probabilitas" dalam buku "Teori Heuristik Pencarian Acak", lihat tautan untuk PDF online) bukti yang agak sederhana dari

Proposisi Biarkan menjadi waktu berhenti dari proses pengumpulan kupon. Kemudian . $T$ $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le e^{-n^{\epsilon}}$

Ini tampaknya memberikan asimptotik yang diinginkan (dari jawaban kedua @ cardinal), tetapi dengan keuntungan berlaku untuk semua dan . $n$ $\epsilon$

Ini sketsa bukti.

Sketsa Bukti: Misalkan adalah peristiwa di mana kupon ke- dikumpulkan di undian pertama . Dengan demikian, . Fakta kuncinya adalah bahwa berkorelasi negatif, untuk setiap , . Secara intuitif, ini cukup jelas, karena mengetahui bahwa kupon -th di pertama menarik akan membuat kecil kemungkinan bahwa kupon -th juga ditarik dalam pertama menarik. $X_i$ $i$ $t$ $\Pr[X_i=1]=(1-1/n)^t$ $X_i$ $I\subseteq[n]$ $\Pr[\forall i\in I, X_i=1]\le\prod_{i\in I}\Pr[X_i=1]$ $i$ $t$ $j$ $t$

Satu dapat membuktikan klaim, tetapi memperbesar set dengan 1 pada setiap langkah. Kemudian mengurangi untuk menunjukkan bahwa , untuk . Secara ekuivalen, dengan rata-rata, itu mengurangi untuk menunjukkan bahwa . Doerr hanya memberikan argumen intuitif untuk ini. Satu jalan ke bukti adalah sebagai berikut. Orang dapat mengamati bahwa dikondisikan pada kupon datang setelah semua kupon di , bahwa probabilitas menggambar kupon baru dari setelah menggambar sejauh ini sekarang , bukannya sebelumnya $I$ $\Pr[\forall i\in I, X_i=1|X_j=1]\le\Pr[\forall i\in I,X_i=1]$ $j\notin I$ $\Pr[\forall i\in I, X_i=1|X_j=0]\ge\Pr[\forall i\in I,X_i=1]$ $j$ $I$ $I$ $k$ $\frac{|I|-k}{n-1}$ $\frac{|I|-k}{n}$ . Jadi mendekomposisi waktu untuk mengumpulkan semua kupon sebagai jumlah variabel acak geometrik, kita dapat melihat bahwa pengkondisian pada -coupon datang setelah meningkatkan probabilitas keberhasilan, dan dengan demikian pengkondisian hanya membuatnya lebih mungkin untuk mengumpulkan kupon sebelumnya ( oleh dominasi stokastik: setiap variabel acak geometris meningkat, dalam hal dominasi stokastik, oleh pengkondisian, dan dominasi ini kemudian dapat diterapkan ke jumlah). $j$ $I$

Dengan korelasi negatif ini, berarti , yang memberikan diinginkan terikat dengan . $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le (1-(1-1/n)^t)^n$ $t=(1-\epsilon)(n-1)\ln n$

miforbes
sumber

Apa yang dimaksud dengan batas bawah ketat pada waktu pengumpul kupon?

Jawaban: