Was ist eine enge Untergrenze für die Kuponsammelzeit?

20

In dem klassischen Coupon Collector-Problem ist bekannt, dass die Zeit erforderlich ist, um einen Satz von zufällig ausgewählten Coupons zu vervollständigen, , und .TnE[T]nlnnVar(T)n2Pr(T>nlnn+cn)<ec

Diese Obergrenze ist besser als die durch die Chebyshev-Ungleichung gegebene, die ungefähr 1/c2 .

Meine Frage ist: Gibt es eine entsprechende Untergrenze für T, die besser ist als Tschebyschew T? (zB so etwas wie Pr(T<nlnncn)<ec )?

David
quelle
Eine offensichtliche Untergrenze ist Pr(T<n)=0 , aber ich
nehme

Antworten:

14

Ich gebe dies als zweite Antwort, da die Analyse vollständig elementar ist und genau das gewünschte Ergebnis liefert.

Satz Für c>0 und n1 ist

P(T<nlogncn)<ec.

Die Idee hinter dem Beweis ist einfach:

  1. Stellen Sie die Zeit dar, bis alle Coupons als T = \ sum_ {i = 1} ^ n T_i gesammelt wurden T=i=1nTi, wobei Ti die Zeit ist, zu der der i te (bisher) eindeutige Coupon gesammelt wurde. Die Ti sind geometrische Zufallsvariablen mit mittleren Zeiten von nni+1 .
  2. Wenden Sie eine Version des gebundenen Chernoff an und vereinfachen Sie.

Beweis

Für jedes und jedes gilt: t s>0

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

Da und unabhängig sind, können wir schreiben: T=iTiTi

EesT=i=1nEesTi

Nun, da geometrisch ist, sagen wir mit Erfolgswahrscheinlichkeit , dann zeigt eine einfache Berechnung Tipi

EesTi=pies1+pi.

Die für unser Problem sind , , usw. Daher ist pip1=1p2=11/np3=12/n

i=1nEesTi=i=1ni/nes1+i/n.

Wählen wir für und . Dann ist und , was ergibt. s=1/nt=nlogncnc>0

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

Wenn wir dies zusammenfassen, erhalten wir

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

wie gewünscht.

Kardinal
quelle
Das ist sehr schön und genau das, was der Arzt bestellt hat. Vielen Dank.
David
@ David, nur neugierig: Was ist die beabsichtigte Anwendung?
Kardinal
Lange Geschichte. Ich versuche, eine Untergrenze für die Mischzeit einer Markov-Kette zu beweisen, die ich ausgearbeitet habe, um die Laufzeit eines Algorithmus zu analysieren, an dem ich interessiert bin Sammlerproblem. Übrigens, ich hatte versucht, genau diese Art von Chernoff-Bindung zu finden, aber ich hatte nicht herausgefunden, wie ich dieses Produkt in loswerden sollte . Guter Anruf bei Wahl von :-). is=1/n
David
@David, , obwohl mit ziemlicher Sicherheit suboptimal, schien der Versuch naheliegend, da dies ergab , was derselbe Ausdruck ist, der in der Herleitung für erhalten wurde die obere Schranke. e s t = n e - cs=1/nest=nec
Kardinal
1
Bitte : Der Beweis, den ich oben gegeben habe, ist mein eigener. Ich habe aus Vergnügen daran gearbeitet, da mich das Problem faszinierte. Ich erhebe jedoch keinen Anspruch auf Neuheit. In der Tat kann ich mir nicht vorstellen, dass ein ähnlicher Beweis mit einer ähnlichen Technik noch nicht in der Literatur existiert. Wenn jemand eine Referenz kennt, posten Sie diese bitte hier als Kommentar. Es würde mich sehr interessieren, von einem zu wissen.
Kardinal
9

Obwohl @cardinal bereits eine Antwort gegeben hat, die genau die gesuchte Grenze angibt, habe ich ein ähnliches Argument im Chernoff-Stil gefunden, das eine stärkere Grenze geben kann:

Satz : (Dies ist stärker für )c > π 2

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

Beweis :

Wie in der Antwort von @ cardinal können wir die Tatsache verwenden, dass eine Summe unabhängiger geometrischer Zufallsvariablen mit Erfolgswahrscheinlichkeiten . Daraus folgt, dass und .T i p i = 1 - i / n E [ T i ] = 1 / p i E [ T ] = n i = 1 E [ T i ] = n n i = 1 1TTipi=1i/nE[Ti]=1/piE[T]=i=1nE[Ti]=ni=1n1inlogn

Definieren Sie nun neue Variablen und . Wir können dann schreiben S : = i S i Pr ( T n log n - c n ) Pr ( T E [ T ] - c n ) = Pr ( S - c n ) = Pr ( exp ( - s SSi:=TiE[Ti]S:=iSi

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

Wir haben die Durchschnittswerte berechnet

es-1sez

E[esS]=iE[esSi]=ies/pi1+1pi(es1)e12s2ipi2
wobei die Ungleichung aus den Tatsachen folgt, dass und auch für .es1sz0ez1+ze12z2z0

Da also , wir können schreiben Pr(Tnlogn-cn) e 1ipi2=n2i=1n11i2n2π2/6

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

Wenn wir , erhalten wir schließlich Pr ( T n log n - c n ) e - 3 c 2s>0

Pr(Tnlogncn)e3c2π2
David
quelle
1
(+1) Modulo ein paar kleinere Tippfehler, das ist schön. Etwas in der Nähe des Mittelwerts zu erweitern, wie Sie es getan haben, funktioniert oft besser. Ich bin nicht überrascht, die Konvergenz höherer Ordnung im Lichte der asymptotischen Ergebnisse zu sehen. Nun, wenn Sie zeigen eine ähnliche solche Obergrenze, das beweist ist subexponentiellen in der Terminologie der Vershynin, die viele Implikationen in Bezug auf Maß Konzentration hat. (Tnlogn)/n
Kardinal
1
Das Argument scheint nicht direkt auf die obere Grenze zu verallgemeinern. Wenn Sie für (und für ) , können Sie die gleichen Schritte , bis Sie berechnen. . Zu diesem Zeitpunkt kann ich jedoch am besten , was immer noch und ich ziehe an Ich weiß nicht, was ich damit anfangen soll- c s - s E [ e s S ] & Pgr; i e - s / p iccssE[esS]ies/pi1spiez1zexp(z22(1z))
E[esS]e12s2ipi2(1s/pi)
David
2
Interessanterweise scheint das gesamte Argument (für die untere Schranke) nicht nur für das Coupon-Sammler-Problem zu funktionieren, sondern für jede Summe nicht identischer, unabhängiger geometrischer Variablen mit begrenzter Varianz. Insbesondere gilt: , wobei jedes ein unabhängiges GV mit Erfolgswahrscheinlichkeit , und wobei , dann T=iTiTipiipi2A<
Pr(TE[T]a)ea22A
David
4

Wichtiger Hinweis : Ich habe beschlossen, den in dieser Antwort ursprünglich angegebenen Beweis zu entfernen. Es war länger, rechenintensiver, verwendete größere Hämmer und erwies sich als schwächer als die anderen Beweise, die ich gegeben habe. Rundum eine minderwertige Herangehensweise (aus meiner Sicht). Wenn Sie wirklich interessiert sind, können Sie sich die Änderungen ansehen.

Die asymptotischen Ergebnisse, die ich ursprünglich zitiert habe und die unten in dieser Antwort noch zu finden sind, zeigen, dass wir als etwas besser können als die in der anderen Antwort bewiesene Grenze, die für alle .n n


Die folgenden asymptotischen Ergebnisse gelten

P(T>nlogn+cn)1eec

und

P(Tnlogncn)eec.

Die Konstante und die Grenzen werden als . Beachten Sie, dass sie, obwohl sie in zwei Ergebnisse unterteilt sind, fast dasselbe Ergebnis haben, da in beiden Fällen nicht auf Nicht-Negativ beschränkt ist.cRnc

Siehe zB Motwani und Raghavan, Randomized Algorithms , S. 60-63 für einen Beweis.


Außerdem : David liefert freundlicherweise einen Beweis für seine angegebene Obergrenze in den Kommentaren zu dieser Antwort.

Kardinal
quelle
Ja, es gilt für jedes feste . Ein (sehr einfacher) Beweis findet sich beispielsweise in Levin, Peres und Wilmers Buch Markov Chains and Mixing Times, Proposition 2.4. Der Beweis funktioniert jedoch nicht für die untere Schranke. n
David
1
Tatsächlich könnte ich den Beweis genauso gut hier : "Sei der Fall, dass der te [Coupon] -Typ nicht unter den ersten gezogenen Coupons erscheint. Beachten Sie zuerst, dass . Da jeder Versuch die Wahrscheinlichkeit , Coupon nicht zu ziehen, und die Versuche unabhängig sind, die rechte Seite oben ist begrenzt durch , beweise (2.7). " Aiinlogn+cnP(τ>nlogn+cn)=P(iAi)iP(Ai)1n1ii(11/n)nlogn+cnnexp(nlogn+cnn)=ec
David
@ David, das ist nett und einfach genug. Ich spielte schnell damit, die Einschluss- / Ausschlussformel um einen anderen Begriff zu erweitern, kam aber nicht schnell weiter und hatte keine Zeit, mich weiter damit zu beschäftigen. Das Ereignis entspricht dem Ereignis, dass nach Versuchen keine Coupons mehr übrig sind . Damit sollte ein Martingal verbunden sein. Haben Sie Hoeffdings Ungleichung im (vermuteten) assoziierten Martingal ausprobiert? Das asymptotische Ergebnis deutet auf eine starke Messkonzentration hin. {T<tn}tn
Kardinal
@ David, es gibt einen Hinweis in Ihrem Beweis oben, aber ich bin sicher, dass das auch für andere Leser offensichtlich ist.
Kardinal
@ David, bitte sehen Sie meine andere Antwort auf Ihre Frage. Die Methode unterscheidet sich von der von Ihnen angegebenen Obergrenze, aber die verwendeten Werkzeuge sind im Gegensatz zu der hier gegebenen Antwort fast genauso elementar.
Kardinal
2

Benjamin Doerr gibt (im Kapitel "Analysieren randomisierter Suchheuristiken: Werkzeuge aus der Wahrscheinlichkeitstheorie" im Buch "Theory of Randomized Search Heuristics", siehe den Link für ein Online-PDF) einen etwas einfachen Beweis dafür

Proposition Sei die Stoppzeit des Couponsammelprozesses. Dann .TPr[T(1ϵ)(n1)lnn]enϵ

Dies scheint die gewünschte Asymptotik zu liefern (aus der zweiten Antwort von @ cardinal), aber mit dem Vorteil, dass es für alle und .nϵ

Hier ist eine Beweisskizze.

Beweisskizze: Sei der Fall, dass der te Coupon in den ersten Zügen gesammelt wird . Somit ist . Die Schlüsseltatsache ist, dass die für jedes , negativ korreliert sind . Intuitiv ist dies ziemlich klar, da das Wissen, dass der te Coupon in den ersten Zügen es weniger wahrscheinlich machen würde, dass der te Coupon auch in den ersten Zügen gezogen wird. XiitPr[Xi=1]=(11/n)tXiI[n]Pr[iI,Xi=1]iIPr[Xi=1]itjt

Man kann die Behauptung beweisen, aber die Menge bei jedem Schritt um 1 vergrößern . Dann wird gezeigt, dass für . Entsprechend reduziert sich die Mittelung auf das Zeigen von . Doerr gibt dafür nur ein intuitives Argument an. Ein Weg zu einem Beweis ist wie folgt. Man kann beobachten, dass unter der Bedingung, dass der Coupon nach allen Coupons in kommt, die Wahrscheinlichkeit, nach dem bisherigen Zeichnen von einen neuen Coupon von nun ist. anstelle der vorherigenIPr[iI,Xi=1|Xj=1]Pr[iI,Xi=1]jIj I I k | Ich | - kPr[iI,Xi=1|Xj=0]Pr[iI,Xi=1]jIIk | Ich| -k|I|kn1 jich|I|kn . Zerlegt man also die Zeit, um alle Coupons als Summe geometrischer Zufallsvariablen zu sammeln, so kann man sehen, dass die Konditionierung auf den Coupon erfolgt, nachdem die Erfolgswahrscheinlichkeiten erhöht habe, und dies macht es nur wahrscheinlicher, dass die Coupons früher gesammelt werden ( durch stochastische Dominanz: Jede geometrische Zufallsvariable wird in Bezug auf die stochastische Dominanz durch die Konditionierung erhöht, und diese Dominanz kann dann auf die Summe angewendet werden.jI

In Anbetracht dieser negativen Korrelation folgt, dass , was das ergibt gewünschte Bindung mit . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[T(1ϵ)(n1)lnn](1(11/n)t)nt=(1ϵ)(n1)lnn

miforbes
quelle