Κατεύθυνση Στατιστική και Επιχειρησιακή Έρευνα
Library of the School of Science

2019-07-09

2019

Kafetzopoulos Anastasis

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

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

English

Concentration of measure for the analysis of randomized algorithms and random graphs

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.

Science

probabilities, concentration of measure, concentration inequalities, randomized algorithms, random graphs

Yes

2

Yes

19

82

File access is restricted only to the intranet of UoA.

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