{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2878250"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2878250","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων","abstract":"Στο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.","abstract_html":"Στο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.","abstract_has_math":false,"creators":["Καφετζόπουλος Αναστάσης","Kafetzopoulos Anastasis"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-19T05:35:44Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2878250"],"render_values":[{"text":"uoadl:2878250","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2878250","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2878250","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2878250","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Καφετζόπουλος Αναστάσης","Kafetzopoulos Anastasis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2878250","https://pergamos.lib.uoa.gr/uoa/dl/object/2878250"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.","In the first part of this thesis, we derive the Chernoff-Hoeffding bounds for random variables that can be expressed as a summation of other (often simpler) random variables. The first part is then split into two topics. Firstly, we analyse the C-H bounds for independent summands and then for dependent summands for which the dependency graph plays a crucial role. A lot of applications are given into both topics. In the second part we analyse more complicated functions of random variables that can’t be expressed as a summation of other, simpler, random variables. For these functions, we use the martingale techniques, to firstly, expose these easier random variables, and secondly make a martingale filtration on them. A crucial role here plays the Doob martingale that lets us make this filtration and derive bounds through the Azuma-Hoeffding inequality by setting some conditions on the filtration. A lot of examples are also given in this part and we are set to see these two techniques in action and in real-world problems."]},{"key":"dc:title","label":"Title","values":["Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων"]}]}],"canonical_facts":{"dc:creator":["Καφετζόπουλος Αναστάσης","Kafetzopoulos Anastasis"],"dc:date":["2019"],"dc:description":["Στο πρώτο μέρος της εργασίας αυτής, αποδεικνύουμε τα φράγματα Chernoff-Hoeffding για τυχαίες μεταβλητές που μπορούν να εκφραστούν ως αθροίσματα άλλων (συνήθως απλούστερων) τυχαίων μεταβλητών. Το πρώτο μέρος μετά χωρίζεται σε δύο θέματα. Στο πρώτο θέμα, αναλύουμε τα φράγματα C-H για ανεξάρτητες αθροιστικές ποσότητες και στο δεύτερο για εξαρτημένες, στις οποίες παίζει καθοριστικό ρόλο το γράφημα εξάρτησης. Αρκετές εφαρμογές δίνονται και στα δύο θέματα. Στο δεύτερο μέρος αναλύουμε πιο περίπλοκες συναρτήσεις τυχαίων μεταβλητών οι οποίες δε μπορούν να γραφούν ως αθροίσματα από άλλες απλούστερες τυχαίες μεταβλητές. Για τις συναρτήσεις αυτές, χρησιμοποιούμε τεχνικές των martingales, ώστε πρώτα να αναδείξουμε τις απλούστερες τυχαίες μεταβλητές οι οποίες υπάρχουν στις συναρτήσεις και μετά να κάνουμε μια διήθηση martingale σε αυτές. Σημαντικό ρόλο εδώ παίζει το martingale του Doob που μας δίνει τη δυνατότητα να κάνουμε τη διήθηση αυτή και να παράγουμε φράγματα μέσω της ανισότητας Azuma-Hoeffding αφού θέσουμε κάποιες επιπλέον ιδιότητες στη διήθηση. Στη συνέχεια δίνονται αρκετές εφαρμογές και βλέπουμε πως εφαρμόζονται οι τεχνικές αυτές σε υπαρκτά προβλήματα.","In the first part of this thesis, we derive the Chernoff-Hoeffding bounds for random variables that can be expressed as a summation of other (often simpler) random variables. The first part is then split into two topics. Firstly, we analyse the C-H bounds for independent summands and then for dependent summands for which the dependency graph plays a crucial role. A lot of applications are given into both topics. In the second part we analyse more complicated functions of random variables that can’t be expressed as a summation of other, simpler, random variables. For these functions, we use the martingale techniques, to firstly, expose these easier random variables, and secondly make a martingale filtration on them. A crucial role here plays the Doob martingale that lets us make this filtration and derive bounds through the Azuma-Hoeffding inequality by setting some conditions on the filtration. A lot of examples are also given in this part and we are set to see these two techniques in action and in real-world problems."],"dc:identifier":["uoadl:2878250","https://pergamos.lib.uoa.gr/uoa/dl/object/2878250"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Συγκέντρωση του μέτρου για την ανάλυση τυχαιοποιημένων αλγορίθμων και τυχαίων γραφημάτων"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:35:44Z"}