National and Kapodistrian University of Athens
Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων
Abstract
dc:descriptionΣτο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Καφετζόπουλος Αναστάσης
- Kafetzopoulos Anastasis
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:2878250