Η παρούσα διατριβή ασχολείται με μερικές από τις πιο βασικές πτυχές του προβλήματος του συλλέκτη (Coupon Collector’s Problem (CCP)), ενός εκ των πιο γνωστών προβλημάτων που προέρχονται από τον χώρο των πιθανοτήτων. Θεωρούμε έναν πληθυσμό που αποτελείται από N διαφορετικά αντικείμενα (ψάρια, λέξεις, κάρτες με παίκτες του baseball, ιοί, κτλ.), τα οποία συμβατικά θα αποκαλούμε κουπόνια. Έστω TN ο αριθμός των δοκιμών, που ανεξάρτητα και με επανάθεση απαιτούνται, ώστε ένα συλλέκτης να έχει μία πλήρη συλλογή και από τα N διαφορετικά κουπόνια. Για την τυχαία μεταβλητή TN εγείρονται, φυσιολογικά, ερωτήματα ως προς την μέση τιμή, τις ροπές ανωτέρας τάξεως, την διασπορά και, φυσικά, την κατανομή της, καθώς N → ∞. Τούτη η εργασία αποτελείται από τρία μέρη. Στο πρώτο μέρος παρουσιάζουμε τεχνικές με τις οποίες υπολογίζουμε εις βάθος την ασυμπτωτική συμπεριφορά της πρώτης και δεύτερης ροπής της τ.μ. TN καθώς N → ∞. Στην συνέχεια προκύπτει ο πρωτεύων όρος επί του ασυμπτωτικού αναπτύγματος της διασποράς V[TN] που αποτελεί το κύριο αποτέλεσμα του πρώτου μέρους. Συνδυάζοντας τα αποτελέσματα αυτά με δύο γνωστά –πλην όμως γενικά- θεωρήματα βρίσκουμε την οριακή κατανομή της ποσότητας TN (καταλλήλως κανονικοποιημένη), η οποία για μία μεγάλη κλάση κατανομών αποδεικνύεται ότι είναι η συνήθης κατανομή Gumbel. Στο δεύτερο μέρος και για μία μεγάλη κλάση κατανομών υπολογίζουμε τον πρωτεύοντα όρο επί του ασυμπτωτικού αναπτύγματος όλων των ροπών ανωτέρας τάξεως για την τ.μ. TN. Τέλος, στο τρίτο μέρος παραθέτουμε μερικά γενικά παραδείγματα, μέσω των οποίων παρουσιάζουμε τα αποτελέσματα του πρώτου και δεύτερου μέρους.
This Ph.D. thesis deals with a famous Urn problem. We consider a population whose members are of N different types (e.g. colors, fish, baseball cards, viruses, ants, words, etc.). For 1 ≤ j ≤ N we denote by pj the probability that a member of the population is of type j, where pj > 0 and ΣN j=1 pj = 1: The members of the population are sampled independently with replacement and their types are recorded. The so-called “coupon collector problem” (CCP) deals with questions arising in the above procedure. Some key quantities are the moments of the number TN of trials it takes until all N types are detected (at least once), the variance, and (of course), the distribution of TN. Our work here is divided in three parts. In Part I we develop techniques of computing detailed asymptotics of the first and second moment of the random variable TN of coupons that a collector has to buy in order to find all N existing different coupons as N → ∞. The probabilities (occurring frequencies) of the coupons can be quite arbitrary. From these asymptotics we obtain the leading behavior of the variance V[TN] of TN. Then, we combine our results with the general limit theorems of P. Neal in order to derive the limit distribution of TN (appropriately normalized), which, for a large class of probabilities, turns out to be the standard Gumbel distribution. In Part II, and for a large class of distributions, we arrive at the leading behavior of the rising moments of the random variable TN as N → ∞. We also present various illustrative examples. Finally, in Part III we present several general examples that illustrate the results of the previous chapters.
