Κατεύθυνση Στατιστική και Επιχειρησιακή Έρευνα
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2019-07-09

2019

Καφετζόπουλος Αναστάσης

Χελιώτης Δημήτριος (αναπληρωτής καθηγητής, τμήμα Μαθηματικών, ΕΚΠΑ)
Γιαννόπουλος Απόστολος (καθηγητής, τμήμα Μαθηματικών, ΕΚΠΑ)
Παπαδάτος Νικόλαος (αναπληρωτής καθηγητής, τμήμα Μαθηματικών, ΕΚΠΑ)

Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων

Αγγλικά

Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων

Στο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.

Θετικές Επιστήμες

πιθανότητες, συγκέντρωση του μέτρου, συγκεντρωτικές ανισότητες, τυχαιοποιημένοι αλγόριθμοι, τυχαία γραφήματα

Ναι

2

Ναι

19

82

Δεν επιτρέπεται η πρόσβαση στο αρχείο. H πρόσβαση επιτρέπεται μόνο εντός του δικτύου του ΕΚΠΑ.

https://pergamos.lib.uoa.gr/uoa/dl/object/2878250