W klasycznym problemie kolekcjonera kuponów dobrze wiadomo, że czas niezbędny do ukończenia zestawu losowo wybranych kuponów spełnia , i .
Ta górna granica jest lepsza od tej podanej przez nierówność Czebyszewa, która wynosiłaby około .
Moje pytanie brzmi: czy istnieje odpowiednia lepsza niż Chebyshev dolna granica dla ? (np. coś takiego jak )?
Odpowiedzi:
Podaję to jako drugą odpowiedź, ponieważ analiza jest całkowicie elementarna i zapewnia dokładnie pożądany wynik.
Twierdzenie dlac > 0 i n ≥ 1 ,
Pomysł na dowód jest prosty:
Dowód
Dla każdego i dowolnej , mamy tę s > 0 P ( T < t ) = P ( e - s T > e - s t ) ≤ e s t E e - s Tt s > 0
Ponieważ i są niezależne, możemy napisać T i E e - s T = n ∏ i = 1 E e - s T iT.= ∑jaT.ja T.ja
Ponieważ jest geometryczne, powiedzmy z prawdopodobieństwem sukcesu , wówczas proste obliczenia pokazują p i E e - s T i = p iT.ja pja
naszego problemu są , , , itp Stąd p 1 = 1 p 2 = 1 - 1 / n p 3 = 1 - 2 / n n ∏ i = 1 E e - s T i = n ∏ i = 1 i / npja p1= 1 p2)= 1 - 1 / n p3)= 1 - 2 / n
Załóżmy wyboru i dla pewnego . Następnie i , dając t = n log n - c n c > 0 e s t = n e - c e s = e 1 / n ≥ 1 + 1 / n n ∏ i = 1 i / ns = 1 / n t = n logn - c n c > 0
Podsumowując, otrzymujemy
zgodnie z życzeniem.
źródło
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 )c > π 2
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 iT. T.ja pja= 1 - i / n mi[ Tja] = 1 / pja mi[ T] = ∑ni = 1mi[ Tja] = n ∑ni = 11ja≥ n logn
Zdefiniuj teraz nowe zmienne i . Następnie możemy napisaćS.ja: = Tja- E[ Tja] S.: = ∑jaS.ja
Obliczamy średnie, mamy
Zatem, ponieważ , możemy napisać∑jap- 2ja= n2)∑n - 1i = 11ja2)≤ n2)π2)/ 6
Minimalizując , w końcu otrzymujemys > 0
źródło
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 → ∞ n
Obowiązują następujące asymptotyczne wyniki
i
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. n → ∞ cc ∈ R n→∞ 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.
źródło
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≤(1−ϵ)(n−1)lnn]≤e−nϵ
Wydaje się, że daje to pożądaną asymptotykę (z drugiej odpowiedzi @ kardynała), ale ma tę zaletę, że jest prawdziwa dla wszystkich i .n ϵ
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 .Xi i t Pr[Xi=1]=(1−1/n)t Xi I⊆[n] Pr[∀i∈I,Xi=1]≤∏i∈IPr[Xi=1] i t tj 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 poprzedniegoI Pr[∀i∈I,Xi=1|Xj=1]≤Pr[∀i∈I,Xi=1] j∉I j I I k | Ja | - kPr[∀i∈I,Xi=1|Xj=0]≥Pr[∀i∈I,Xi=1] j I I k | Ja| -k|I|−kn−1 jI|I|−kn . 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 . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[T≤(1−ϵ)(n−1)lnn]≤(1−(1−1/n)t)n t=(1−ϵ)(n−1)lnn
źródło