Φράγματα τύπου Chernoff και εφαρμογές

• Κύριος συγγραφέας: Σαββάτης, Δημήτριος
• Άλλοι συγγραφείς: Πιπερίγκου, Βιολέττα
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2016
• Θέματα: Πιθανότητα επιβίωσης; Ροπές περί την αρχή; Παραγοντικές ροπές; Ροπογεννήτριες; Πιθανογεννήτριες; Ανισότητα Markov; Φράγμα Chernoff; Δοκιμές Bernoulli; Δοκιμές Poisson; Διακριτές κατανομές; Συνεχείς κατανομές; Εξισορρόπηση συνόλου; Δρομολόγηση πακέτου; Survivor probability; Moments about the origin; Factorial moments; Moment generating function; Markov inequality; Chernoff bound; Bernoulli trials; Poisson trials; Continuous distributions; Discrete distributions; Set balancing; Packet routing; 519.7

Συχνά χρειάζεται να υπολογίσουμε την πιθανότητα επιβίωσης P(X > = t) για μια μη αρνητική τυχαία μεταβλητή X. Σε αρκετές περιπτώσεις, που μας ενδιαφέρουν, η πιθανότητα αυτή δεν μπορεί να δοθεί σε κλειστή μορφή και έτσι αρκούμαστε στην εύρεση άνω φραγμάτων για αυτήν. Στην παρούσα διπλωματική εργασία, στο Κεφάλαιο 1 ορίζονται διάφορα τέτοια φράγματα, που έχουν αναπτυχθεί στην βιβλιογραφία με την χρήση της τεχνικής του Chernoff, στα οποία αξιοποιείται η ανισότητα Markov για τη συνάρτηση της ροπογεννήτριας. Έτσι, οι ροπές περί την αρχή ή οι παραγοντικές ροπές της τυχαίας μεταβλητής, εμφανίζονται κατά περίπτωση στα φράγματα αυτά, τα οποία υπολογίζονται για τυχαίες μεταβλητές που ακολουθούν κάποιες από τις γνωστές συνεχείς και διακριτές κατανομές. Στο Κεφάλαιο 2 παρουσιάζονται φράγματα τύπου Chernoff για αθροίσματα τυχαίων μεταβλητών, όπως αθροίσματα δοκιμών Poisson ή γεωμετρικών τυχαίων μεταβλητών ή μεταβλητών με στήριγμα το (0 , 1). Τα φράγματα αυτά χρησιμοποιούνται ευρέως, και στο Κεφάλαιο 3 παρουσιάζονται εφαρμογές των φραγμάτων αυτών σε περιπτώσεις τυχαιοποιημένων αλγορίθμων, όπου οι μεταβλητές που μας ενδιαφέρουν μπορούν να μοντελοποιηθούν ως αθροίσματα τυχαίων μεταβλητών. Τέλος στο Κεφάλαιο 4 παρουσιάζεται η σύγκριση των φραγμάτων που έχουν δοθεί στο Κεφάλαιο 1. Εστιάζοντας σε διακριτές τυχαίες μεταβλητές, με στήριγμα τους μη αρνητικούς ακεραίους, η απόδειξη της υπεροχής του φράγματος των παραγοντικών ροπών γίνεται με έναν εναλλακτικό και σύντομο τρόπο. Χρησιμοποιώντας αυτό το φράγμα προτείνεται κάποια, κατά περίπτωση, βελτίωση του φράγματος για το άθροισμα δοκιμών Poisson, που παρουσιάστηκε στο Κεφάλαιο 2.