Back to search

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 × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:2878250

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Καφετζόπουλος Αναστάσης; Kafetzopoulos Anastasis. Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων. 2019. https://pergamos.lib.uoa.gr/uoa/dl/object/2878250