Co jest ściśle dolną granicą czasu kolekcjonera kuponów?

20

W klasycznym problemie kolekcjonera kuponów dobrze wiadomo, że czas niezbędny do ukończenia zestawu losowo wybranych kuponów spełnia , i . $T$ $n$ $E[T] \sim n \ln n$ $Var(T) \sim n^2$ $\Pr(T > n \ln n + cn) < e^{-c}$

Ta górna granica jest lepsza od tej podanej przez nierówność Czebyszewa, która wynosiłaby około $1/c^2$ .

Moje pytanie brzmi: czy istnieje odpowiednia lepsza niż Chebyshev dolna granica dla $T$ ? (np. coś takiego jak $\Pr(T < n \ln n - cn) < e^{-c}$ )?

probability probability-inequalities coupon-collector-problem

— David
źródło

Oczywista dolna granica to

Pr (T < n) = 0

$\Pr(T<n) = 0$ , ale myślę, że zdajesz sobie z tego sprawę ...

— onestop

14

Podaję to jako drugą odpowiedź, ponieważ analiza jest całkowicie elementarna i zapewnia dokładnie pożądany wynik.

Twierdzenie dla $c > 0$ i $n \geq 1$ ,

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

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

Pomysł na dowód jest prosty:

Reprezentują czas do zebrania wszystkich kuponów jako $T = \sum_{i=1}^n T_i$ , gdzie $T_i$ jest czasem, w którym zbierany jest $i$ (dotychczas) unikalny kupon. $T_i$ są geometryczne zmiennymi losowymi średnich czasach $\frac{n}{n-i+1}$ .
Zastosuj wersję związanej z Chernoffem i uprość.

Dowód

Dla każdego i dowolnej , mamy tę $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} \> .$

Ponieważ i są niezależne, możemy napisać $T = \sum_i T_i$ $T_i$

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

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

Ponieważ jest geometryczne, powiedzmy z prawdopodobieństwem sukcesu , wówczas proste obliczenia pokazują $T_i$ $p_i$

E e^{- s T_{i}} = \frac{p_{i}}{e^{s} - 1 + p_{i}} .

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

naszego problemu są , , , itp Stąd $p_i$ $p_1 = 1$ $p_2 = 1 - 1/n$ $p_3 = 1 - 2/n$

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

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

Załóżmy wyboru i dla pewnego . Następnie i , dając $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_{i = 1}^{n} \frac{i / n}{e^{s} - 1 + i / n} \leq \prod_{i = 1}^{n} \frac{i}{i + 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} \> .$

Podsumowując, otrzymujemy

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}$

zgodnie z życzeniem.

— kardynał
źródło

To bardzo miłe i właśnie to zlecił lekarz. Dziękuję Ci.

— David

@David, po prostu ciekawy: jaka jest zamierzona aplikacja?

— kardynał

Długa historia. Próbuję udowodnić dolną granicę dla czasu mieszania łańcucha Markowa, który ugotowałem, aby przeanalizować czas działania algorytmu, który mnie interesuje - co okazuje się redukować do dolnej granicy c . problem z kolektorem. BTW, ja zostały gry z starając się znaleźć dokładnie tego rodzaju Chernoffa stylu związanego, ale nie zorientowali się, jak pozbyć się tego produktu w . Dobry wybór połączenia :-).

i

$i$

s = 1 / n

$s = 1/n$

— David

@David, , chociaż prawie na pewno nieoptymalny, wydawał się oczywistą rzeczą do wypróbowania, ponieważ dało to , co jest tym samym terminem, jak ten uzyskany w wyprowadzeniu dla górna granica.

s = 1 / n

$s = 1/n$

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

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

— kardynał

1

Prośba : dowód, który podałem powyżej, jest mój. Pracowałem nad tym z przyjemności, ponieważ problem mnie zaintrygował. Nie twierdzę jednak, że jest nowością. Rzeczywiście nie mogę sobie wyobrazić, że podobny dowód wykorzystujący podobną technikę jeszcze nie istnieje w literaturze. Jeśli ktoś wie o odwołanie, proszę pisać je jako komentarz tutaj. Byłbym bardzo zainteresowany, aby wiedzieć o jednym.

— kardynał

9

Chociaż @cardinal już udzielił odpowiedzi, która dokładnie określa poszukiwaną granicę, znalazłem podobny argument w stylu Chernoffa, który może dać silniejszą granicę:

Twierdzenie : (jest to silniejsze dla )

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}$

Dowód :

Jak w odpowiedzi @ kardynała, możemy wykorzystać fakt, że jest sumą niezależnych geometrycznych zmiennych losowych z prawdopodobieństwem sukcesu . Wynika z tego, że i . $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$

Zdefiniuj teraz nowe zmienne i . Następnie możemy napisać $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]$

Obliczamy średnie, mamy

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}}

$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}}$ gdzie nierówność wynika z faktów, że a także dla .

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$

Zatem, ponieważ , możemy napisać $\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*}$

Minimalizując , w końcu otrzymujemy $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
źródło

1

(+1) Modulo kilka drobnych literówek, to jest miłe. Rozwijanie wokół czegoś zbliżonego do średniej, jak to robiłeś, często działa lepiej. Nie jestem zaskoczony, widząc konwergencję wyższego rzędu w świetle wyników asymptotycznych. Teraz, jeśli wykażesz podobną taką górną granicę, to okaże się, że jest podwykonawczy w terminologii Vershynin, co ma wiele implikacji dotyczących koncentracji pomiaru.

(T - n \log n) / n

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

— kardynał

1

Argument nie wydaje się generalizować bezpośrednio do górnej granicy. Wymieniając na (i na ), można wykonać te same kroki do obliczenia . W tym momencie jednak najlepsze, co mogę zrobić, to użyć , który wciąż pozostawia i nie nie wiem, co z tym zrobić

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_{i} \frac{p_{i}^{2}}{(1 - s / p_{i})}}

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

— David

2

Co ciekawe, cały argument (dla dolnej granicy) wydaje się działać nie tylko dla problemu kolektora kuponów, ale dla dowolnej sumy nieidentycznych, niezależnych zmiennych geometrycznych z ograniczoną wariancją. W szczególności: biorąc pod uwagę , gdzie każdy jest niezależnym GV z prawdopodobieństwem sukcesu , a gdzie , a następnie

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] - a) \leq e^{- \frac{a^{2}}{2 A}}

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

— David

4

Ważna uwaga : postanowiłem usunąć dowód, który podałem pierwotnie w tej odpowiedzi. Był dłuższy, bardziej obliczeniowy, używał większych młotków i okazał się słabszym wynikiem w porównaniu z innym dowodem, który podałem. Ogólnie rzecz biorąc, gorsze podejście (moim zdaniem). Jeśli jesteś naprawdę zainteresowany, przypuszczam, że możesz spojrzeć na zmiany.

Wyniki asymptotyczne, które pierwotnie zacytowałem i które nadal znajdują się poniżej w tej odpowiedzi, pokazują, że jako możemy zrobić trochę lepiej niż granica udowodniona w drugiej odpowiedzi, która dotyczy wszystkich . $n \to \infty$ $n$

Obowiązują następujące asymptotyczne wyniki

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}}$

i

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

Stała i limity są przyjmowane jako . Zauważ, że chociaż są one podzielone na dwa wyniki, są one prawie takie same, ponieważ nie jest ograniczone do nieujemnego w obu przypadkach. $c \in \mathbb{R}$ $n \to \infty$ $c$

Zobacz np. Motwani i Raghavan, Randomized Al Algorytmy , s. 60--63, aby uzyskać dowód.

Ponadto : David uprzejmie przedstawia dowód na swoją górną granicę w komentarzach do tej odpowiedzi.

— kardynał
źródło

Tak, dotyczy każdej ustalonej liczby . (Bardzo prosty) dowód można znaleźć na przykład w książce Levina, Peresa i Wilmera Łańcuchy Markowa i czasy mieszania, Propozycja 2.4. Dowód nie działa jednak dla dolnej granicy.

n

$n$

— David

1

W rzeczywistości równie dobrze mógłbym przepisać tutaj dowód: „Niech będzie zdarzeniem, że ty [kupon] nie pojawia się wśród pierwszych wylosowanych kuponów. Zauważ najpierw, że . Ponieważ każda próba ma prawdopodobieństwo nie losowania kuponu próby są niezależne, prawa strona powyżej jest ograniczona przez , dowodzenie (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, to miłe i proste. Szybko zacząłem grać z rozszerzeniem formuły wykluczania o inny termin, ale nigdzie nie dotarłem szybko i nie miałem czasu na dalsze jej analizowanie. Zdarzenie jest równoważne zdarzeniu, że po testach nie pozostały żadne kupony . Powinny być z tym związane martyngały. Czy próbowałeś nierówności Hoeffdinga na (przypuszczalnie) związanym z Martingale? Wynik asymptotyczny sugeruje silną koncentrację miary.

{T < t_{n}}

$\{T < t_n\}$

t_{n}

$t_n$

— kardynał

@David, na twoim dowodzie widnieje napis flip, ale jestem pewien, że jest to oczywiste także dla innych czytelników.

— kardynał

@ David, zobacz moją inną opublikowaną odpowiedź na twoje pytanie. Metoda jest inna niż górna granica, którą podajesz, ale zastosowane narzędzia są prawie tak podstawowe, w przeciwieństwie do odpowiedzi, którą tu podałem.

— kardynał

2

Benjamin Doerr podaje (w rozdziale „Analiza heurystyk wyszukiwania losowego: narzędzia z teorii prawdopodobieństwa” w książce „Teoria heurystyki wyszukiwania losowego”, patrz link do pliku PDF w Internecie), dość prosty dowód

Twierdzenie Niech będzie czasem zatrzymania procesu zbierania kuponów. Następnie . $T$ $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le e^{-n^{\epsilon}}$

Wydaje się, że daje to pożądaną asymptotykę (z drugiej odpowiedzi @ kardynała), ale ma tę zaletę, że jest prawdziwa dla wszystkich i . $n$ $\epsilon$

Oto szkic próbny.

Szkic : Niech będzie wydarzeniem, w którym ty kupon jest zbierany podczas pierwszych losowań. Zatem . Kluczowym faktem jest to, że są ujemnie skorelowane, dla każdego , . Intuicyjnie jest to dość jasne, ponieważ wiedząc, że ty kupon w pierwszych losowaniach mniej prawdopodobne jest, że ty kupon jest również losowany w pierwszych losowaniach . $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$

Można to udowodnić, ale powiększając zestaw o 1 na każdym kroku. Następnie zmniejsza się pokazując, że , dla . Równolegle, poprzez uśrednianie, sprowadza się to do pokazania, że . Doerr podaje tylko intuicyjny argument. Jedna droga do dowodu jest następująca. Można zauważyć, że pod warunkiem, że kupon nadchodzi po wszystkich kuponach w , że prawdopodobieństwo wyciągnięcia nowego kuponu z po losowaniu wynosi teraz , zamiast poprzedniego $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}$ . Tak więc rozkładając czas na zebranie wszystkich kuponów jako sumę geometrycznych zmiennych losowych, widzimy, że warunkowanie na kuponie po zwiększa prawdopodobieństwo sukcesu, a zatem wykonanie warunkowania tylko zwiększa prawdopodobieństwo wcześniejszego zebrania kuponów ( przez dominację stochastyczną: każda geometryczna zmienna losowa jest zwiększana, w kategoriach dominacji stochastycznej, przez warunkowanie, a ta dominacja może być następnie zastosowana do sumy). $j$ $I$

Biorąc pod uwagę tę ujemną korelację, wynika z tego, że , co daje pożądane ograniczenie . $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le (1-(1-1/n)^t)^n$ $t=(1-\epsilon)(n-1)\ln n$

— Miforbes
źródło