Dans le problème classique du collecteur de coupons , il est bien connu que le temps nécessaire pour terminer un ensemble de coupons choisis au hasard satisfait , , et .
Cette limite supérieure est meilleure que celle donnée par l'inégalité de Tchebychev, qui serait d'environ .
Ma question est la suivante: existe-t-il une borne inférieure correspondante meilleure que celle de Tchebychev pour ? (par exemple, quelque chose comme )?
Réponses:
Je fournis cela comme une deuxième réponse car l'analyse est complètement élémentaire et fournit exactement le résultat souhaité.
Proposition Pourc > 0 et n ≥ 1 ,
L'idée derrière la preuve est simple:
Preuve
Pour tout et tout , nous avons que s > 0 P ( T < t ) = P ( e - s T > e - s t ) ≤ e s t E e - s Tt s > 0
Puisque et sont indépendants, nous pouvons écrire T i E e - s T = n ∏ i = 1 E e - s T iT= ∑jeTje Tje
Maintenant que est géométrique, disons avec une probabilité de succès , alors un calcul simple montre p i E e - s T i = p iTje pje
Les pour notre problème sont , , , etc. Par conséquent, p 1 = 1 p 2 = 1 - 1pje p1= 1 p 3 = 1 - 2 / n n ∏ i = 1 E e - s T i = n ∏ i = 1 i / np2= 1 - 1 / n p3= 1 - 2 / n
Nous allons choisir et pour certains . Alors et , donnant t = n log n - c n cs = 1 / n t = n logn - c n e s t = n e - c e s = e 1 / n ≥ 1 + 1 / n n ∏ i = 1 i / nc > 0
Ensemble, nous obtenons que
comme voulu.
la source
Bien que @cardinal ait déjà donné une réponse qui donne précisément la limite que je cherchais, j'ai trouvé un argument similaire à Chernoff qui peut donner une limite plus forte:
Proposition : (c'est plus fort pour )
Preuve :
Comme dans la réponse de @ cardinal, nous pouvons utiliser le fait que est une somme de variables aléatoires géométriques indépendantes avec des probabilités de succès . Il s'ensuit que et .T i p i = 1 - i / n E [ T i ] = 1 /T Tje pje= 1 - i / n E[ Tje] = 1 / pje E[ T] = ∑ni = 1E[ Tje] = n ∑ni = 11je≥ n logn
Définissez maintenant de nouvelles variables , et . On peut alors écrire S : = ∑ i S i Pr (Sje: = Tje- E[ Tje] S: = ∑jeSje
En calculant les moyennes, nous avons
Ainsi, puisque , nous pouvons écrire∑jep- 2je= n2∑n - 1i = 11je2≤ n2π2/ 6
En minimisant sur , on obtient enfins > 0
la source
Remarque importante : j'ai décidé de supprimer la preuve que j'ai donnée à l'origine dans cette réponse. Il était plus long, plus computationnel, utilisait des marteaux plus gros, et s'est avéré un résultat plus faible par rapport à l'autre preuve que j'ai donnée. Tout autour, une approche inférieure (à mon avis). Si vous êtes vraiment intéressé, je suppose que vous pouvez regarder les modifications.
Les résultats asymptotiques que j'ai cités à l'origine et qui se trouvent encore ci-dessous dans cette réponse montrent qu'en tant que nous pouvons faire un peu mieux que la limite prouvée dans l'autre réponse, qui vaut pour tout .n→∞ n
Les résultats asymptotiques suivants sont valables
et
La constante et les limites sont considérées comme . Notez que, bien qu'ils soient séparés en deux résultats, ils sont à peu près le même résultat puisque n'est pas contraint d'être non négatif dans les deux cas. n → ∞ cc∈R n→∞ c
Voir, par exemple, Motwani et Raghavan, Randomized Algorithms , pp.60-63 pour une preuve.
Aussi : David fournit aimablement une preuve de sa limite supérieure indiquée dans les commentaires de cette réponse.
la source
Benjamin Doerr donne (dans le chapitre "Analyse de l'heuristique de recherche aléatoire: outils de la théorie des probabilités" dans le livre "Théorie de l'heuristique de recherche aléatoire", voir le lien pour un PDF en ligne) une preuve assez simple de
Proposition Soit l'heure d'arrêt du processus de collecte des coupons. Alors .T Pr[T≤(1−ϵ)(n−1)lnn]≤e−nϵ
Cela semble donner l'asymptotique souhaitée (d'après la deuxième réponse de @ cardinal), mais avec l'avantage d'être vrai pour tous les et .n ϵ
Voici un croquis de preuve.
Esquisse de preuve: Soit l'événement où le ème coupon est collecté lors des premiers tirages. Ainsi, . Le fait clé est que les sont corrélés négativement, pour tout , . Intuitivement, cela est assez clair, car sachant que le ème coupon dans les premiers tirages rendrait moins probable que le ème coupon soit également tiré dans les premiers tirages.Xi i t Pr[Xi=1]=(1−1/n)t Xi I⊆[n] Pr[∀i∈I,Xi=1]≤∏i∈IPr[Xi=1] i t j t
On peut prouver la revendication, mais en agrandissant l'ensemble de 1 à chaque étape. Ensuite , il se réduit à montrer que , pour . De manière équivalente, en faisant la moyenne, cela revient à montrer que . Doerr ne donne qu'un argument intuitif pour cela. Une voie vers une preuve est la suivante. On peut observer que conditionnée par le coupon venant après tous les coupons dans , que la probabilité de tirer un nouveau coupon de après avoir tiré jusqu'à présent soit maintenant , au lieu du précédentI Pr[∀i∈I,Xi=1|Xj=1]≤Pr[∀i∈I,Xi=1] j∉I j I I k | Je | - kPr[∀i∈I,Xi=1|Xj=0]≥Pr[∀i∈I,Xi=1] j I I k | Je| -k|I|−kn−1 jI|I|−kn . Ainsi, en décomposant le temps de collecte de tous les coupons sous la forme d'une somme de variables géométriques aléatoires, nous pouvons voir que le conditionnement sur le -coupon à venir après augmente les probabilités de succès, et donc faire le conditionnement ne fait que rendre plus probable la collecte des coupons plus tôt ( par dominance stochastique: chaque variable géométrique aléatoire est augmentée, en termes de dominance stochastique, par le conditionnement, et cette dominance peut alors être appliquée à la somme).j I
Compte tenu de cette corrélation négative, il s'ensuit que , ce qui donne la borne souhaitée avec . t = ( 1 - ϵ ) ( n - 1 ) ln nPr[T≤(1−ϵ)(n−1)lnn]≤(1−(1−1/n)t)n t=(1−ϵ)(n−1)lnn
la source