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 .TnE[T]nlnnVar(T)n2Pr(T>nlnn+cn)<ec

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

Moje pytanie brzmi: czy istnieje odpowiednia lepsza niż Chebyshev dolna granica dla T ? (np. coś takiego jak Pr(T<nlnncn)<ec )?

David
źródło
Oczywista dolna granica to Pr(T<n)=0 , ale myślę, że zdajesz sobie z tego sprawę ...
onestop

Odpowiedzi:

14

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

Twierdzenie dla c>0 i n1 ,

P(T<nlogncn)<ec.

Pomysł na dowód jest prosty:

  1. Reprezentują czas do zebrania wszystkich kuponów jako T=i=1nTi , gdzie Ti jest czasem, w którym zbierany jest i (dotychczas) unikalny kupon. Ti są geometryczne zmiennymi losowymi średnich czasach nni+1 .
  2. Zastosuj wersję związanej z Chernoffem i uprość.

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

P(T<t)=P(esT>est)estEesT.

Ponieważ i są niezależne, możemy napisać T i E e - s T = n i = 1 E e - s T iT=iTiTi

EesT=i=1nEesTi

Ponieważ jest geometryczne, powiedzmy z prawdopodobieństwem sukcesu , wówczas proste obliczenia pokazują p i E e - s T i = p iTipi

EesTi=pies1+pi.

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 / npip1=1p2=11/np3=12/n

i=1nEesTi=i=1ni/nes1+i/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 / n1 + 1 / n n i = 1 i / ns=1/nt=nlogncnc>0

est=nec
es=e1/n1+1/n
i=1ni/nes1+i/ni=1nii+1=1n+1.

Podsumowując, otrzymujemy

P(T<nlogncn)nn+1ec<ec

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 :-). s = 1 / nis=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. e s t = n e - cs=1/nest=nec
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 )c > π 2

Pr(Tnlogncn)exp(3c2π2).
c>π23

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 iTTipi=1i/nE[Ti]=1/piE[T]=i=1nE[Ti]=ni=1n1inlogn

Zdefiniuj teraz nowe zmienne i . Następnie możemy napisać Si:=TiE[Ti]S:=iSi

Pr(Tnlogncn)Pr(TE[T]cn)=Pr(Scn)
=Pr(exp(sS)exp(scn))escnE[esS]

Obliczamy średnie, mamy

E[esS]=iE[esSi]=ies/pi1+1pi(es1)e12s2ipi2
gdzie nierówność wynika z faktów, że a także dla .es1sez1+ze12z2z0

Zatem, ponieważ , możemy napisać ipi2=n2i=1n11i2n2π2/6

Pr(Tnlogncn)e112(nπs)2scn.

Minimalizując , w końcu otrzymujemy s>0

Pr(Tnlogncn)e3c2π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. (Tnlogn)/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ćccssE[esS]ies/pi1spiez1zexp(z22(1z))
E[esS]e12s2ipi2(1s/pi)
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=iTiTipiipi2A<
Pr(TE[T]a)ea22A
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 n


Obowiązują następujące asymptotyczne wyniki

P(T>nlogn+cn)1eec

i

P(Tnlogncn)eec.

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 ccRnc

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
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). " i n log n + c n P ( τ > n log n + c n ) = P ( i A i ) Aiinlogn+cnP(τ>nlogn+cn)=P(iAi)iP(Ai)1n1ii(11/n)nlogn+cnnexp(nlogn+cnn)=ec
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 n{T<tn}tn
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 .TPr[T(1ϵ)(n1)lnn]enϵ

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 . XiitPr[Xi=1]=(11/n)tXiI[n]Pr[iI,Xi=1]iIPr[Xi=1]ittjt

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 poprzedniegoIPr[iI,Xi=1|Xj=1]Pr[iI,Xi=1]jIj I I k | Ja | - kPr[iI,Xi=1|Xj=0]Pr[iI,Xi=1]jIIk | Ja| -k|I|kn1 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).jI

Biorąc pod uwagę tę ujemną korelację, wynika z tego, że , co daje pożądane ograniczenie . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[T(1ϵ)(n1)lnn](1(11/n)t)nt=(1ϵ)(n1)lnn

Miforbes
źródło