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 . $T$ $n$ $E[T] \sim n \ln n$ $Var(T) \sim n^2$ $\Pr(T > n \ln n + cn) < e^{-c}$

Diese Obergrenze ist besser als die durch die Chebyshev-Ungleichung gegebene, die ungefähr $1/c^2$ .

Meine Frage ist: Gibt es eine entsprechende Untergrenze für besser ist als Tschebyschew $T$ ? (zB so etwas wie $\Pr(T < n \ln n - cn) < e^{-c}$ )?

probability probability-inequalities coupon-collector-problem David
quelle

Eine offensichtliche Untergrenze ist

Pr (T < n) = 0

$\Pr(T<n) = 0$ , aber ich

nehme

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 $n \geq 1$ ist

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

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

Die Idee hinter dem Beweis ist einfach:

Stellen Sie die Zeit dar, bis alle Coupons als gesammelt wurden $T = \sum_{i=1}^n T_i$ , wobei $T_i$ die Zeit ist, zu der der $i$ te (bisher) eindeutige Coupon gesammelt wurde. Die $T_i$ sind geometrische Zufallsvariablen mit mittleren Zeiten von $\frac{n}{n-i+1}$ .
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 (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} \> .$

Da und unabhängig sind, können wir schreiben: $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}$

Nun, da geometrisch ist, sagen wir mit Erfolgswahrscheinlichkeit , dann zeigt eine einfache Berechnung $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} .$

Die für unser Problem sind , , usw. Daher ist $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}.$

Wählen wir für und . Dann ist und , was ergibt. $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} \> .$

Wenn wir dies zusammenfassen, erhalten wir

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

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 :-).

i

$i$

s = 1 / n

$s = 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.

s = 1 / n

$s = 1/n$

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

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

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 )

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

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

Definieren Sie nun neue Variablen und . Wir können dann schreiben $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]$

Wir haben die Durchschnittswerte berechnet

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}}$ wobei die Ungleichung aus den Tatsachen folgt, dass und auch für .

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$

Da also , wir können schreiben $\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*}$

Wenn wir , erhalten wir schließlich $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
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.

(T - n \log n) / n

$(T-n\log n)/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

$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

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 = \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

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 \to \infty$ $n$

Die folgenden asymptotischen Ergebnisse gelten

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

und

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

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. $c \in \mathbb{R}$ $n \to \infty$ $c$

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

$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). "

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, 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 < t_{n}}

$\{T < t_n\}$

t_{n}

$t_n$

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 . $T$ $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le e^{-n^{\epsilon}}$

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$ $\epsilon$

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

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 vorherigen $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}$ . 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. $j$ $I$

In Anbetracht dieser negativen Korrelation folgt, dass , was das ergibt gewünschte Bindung mit . $\Pr[T\le (1-\epsilon)(n-1)\ln n]\le (1-(1-1/n)^t)^n$ $t=(1-\epsilon)(n-1)\ln n$

miforbes
quelle

Was ist eine enge Untergrenze für die Kuponsammelzeit?

Antworten: