Θεωρία Πιθανοτήτων - Μεταπτυχιακό Μάθημα

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης, Λεωφόρος Κνωσού, 714 09 Ηράκλειο, E-mail: kolount@gmail.com

Φθινόπωρο 2006-07

Il faut systématiquement explorer le hasard.

Graffiti, Παρίσι, 5/1968.

Περιεχόμενα

• 1 Ωράριο
• 2 Σημειώσεις
• 3 Βαθμολογικό Σύστημα - Εξετάσεις
• 4 Ημερολόγιο Μαθήματος
  • 4.1 Τρ, 3/10/06: Χώροι πιθανότητας
  • 4.2 Πα, 6/10/06: Οριακά θεωρήματα, κατανομή τυχαίας μεταβλητής, χώροι γινόμενα
  • 4.3 Τρ, 10/10/06: Χαρακτηριστικές συναρτήσεις
  • 4.4 Πα, 13/10/06: Ιδιότητες χαρακτηριστικών συναρτήσεων. Ροπές.
  • 4.5 Τρ, 24/10/06: Ασθενής σύγκλιση και Θ. Helly
    • 4.5.1 Τρ, 24/10/06: ΑΝΑΚΟΙΝΩΣΗ: 1ο Διαγώνισμα
  • 4.6 Πα, 27/10/06: Θ. Lévy. Ασθενής νόμος μεγάλων αριθμών
  • 4.7 Τρ, 31/10/06: Ισχυρός νόμος μεγάλων αριθμών
  • 4.8 Πα, 3/11/06: Πρώτο διαγώνισμα
  • 4.9 Τρ, 7/11/06: Ασκήσεις
  • 4.10 Πα, 9/11/06: Θεώρημα Lévy
    • 4.10.1 Πα, 9/11/06: ΑΝΑΚΟΙΝΩΣΗ: Αναπλήρωση μαθήματος
  • 4.11 Τε, 15/11/06: Θ. τριών σειρών και ισχυρός νόμος μεγάλων αριθμών
  • 4.12 Τρ, 21/11/06: Κεντρικό Οριακό Θεώρημα. Εφαρμογές.
    • 4.12.1 Τε, 22/11/06: ΑΝΑΚΟΙΝΩΣΗ: Δεύτερο διαγώνισμα
  • 4.13 Πα, 24/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)
  • 4.14 Τρ, 28/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)
  • 4.15 Πέ, 30/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)
  • 4.16 Τρ, 5/12/06: Δεύτερο διαγώνισμα.
  • 4.17 Πα, 8/12/06: Εντροπία και πληροφορία
  • 4.18 Τρ, 12/12/06: Εντροπία και πληροφορία
    • 4.18.1 Τρ, 12/12/06: ΑΝΑΚΟΙΝΩΣΗ: Έκτακτο μάθημα
  • 4.19 Τε, 13/12/06: Εντροπία και συμπίεση (κωδικοποίηση) πηγής
  • 4.20 Πα, 15/12/06: Εντροπία στη συνδυαστική. Μετατροπή τυχαίας πηγής σε τυχαία bits
  • 4.21 Τρ, 19/12/06: Το θεώρημα του J. Spencer για discrepancy

1 Ωράριο

Τρίτη 1-3, Παρασκευή 1-3 στην αίθουσα ΡΑ 103. Έναρξη μαθημάτων: 3/10/06.

Ώρες γραφείου: Τε 11-1 (Γ 111, προκατ κτήριο στην Κνωσό)

2 Σημειώσεις

Θα ακολουθήσουμε τις σημειώσεις του S.R.S. Varadhan, τις οποίες μπορείτε να βρέιτε εδώ.

3 Βαθμολογικό Σύστημα - Εξετάσεις

Θα δοθούν τρία (3) υποχρεωτικά διαγωνίσματα κατά τη διάρκεια του εξαμήνου. Κάθε ένα από αυτά θα μετράει για το 1/3 του συνολικού βαθμού.

4 Ημερολόγιο Μαθήματος

Η σελίδα αυτή θα ενημερώνεται τουλάχιστον μετά από κάθε μάθημα και σκοπό έχει να μεταδίδει μερικές βασικές χρήσιμες πληροφορίες για το περιεχόμενο του μαθήματος (π.χ. τι να προσέξετε, υποδείξεις για λύσεις των ασκήσεων, κ.ά.) καθώς και για διαδικαστικά θέματα.

Σπανίως θα βγαίνουν ανακοινώσεις που αφορούν το μάθημα σε χαρτί. Παρακαλώ να συμβουλεύεστε αυτηή τη σελίδα τουλάχιστον 2-3 φορές την εβδομάδα.

4.1 Τρ, 3/10/06: Χώροι πιθανότητας

Αναφερθήκαμε στους χώρους πιθανότητας ως ειδική περίπτωση χώρων μέτρου.

Επαναλάβαμε διάφορες βασικές ιδιότητες του μέτρου και του ολοκληρώματος.

Ασχοληθήκαμε ιδιαίτερα με τη σχέση της σύγκλισης κατά πιθανότητα με τη σύγκλιση σχεδόν παντού.

4.2 Πα, 6/10/06: Οριακά θεωρήματα, κατανομή τυχαίας μεταβλητής, χώροι γινόμενα

Είδαμε τα περιεχόμενα των §1.3 έως §1.6 των σημειώσεων.

4.3 Τρ, 10/10/06: Χαρακτηριστικές συναρτήσεις

Είδαμε τον ορισμό της χαρακτηριστικής συνάρτησης (μετασχηματισμός Fourier) ενός μέτρου πιθανότητας καθώς και ορισμένες ιδιότητες της συνάρτησης αυτής. Είπαμε επίσης και μερικά γενικά πράγματα για το μετασχηματισμό Fourier και μοιράστηκαν ως βοηθητικό κείμενο οι σημειώσεις εισαγωγής στην ανάλυση Fourier (slides) που είχα γράψει πέρυσι για το μάθημα Θεωια Μέτρου (εδώ σε PDF).

4.4 Πα, 13/10/06: Ιδιότητες χαρακτηριστικών συναρτήσεων. Ροπές.

Αποδείξαμε ένα τύπο αντιστροφής για χαρακτηριστικές συναρτήσεις, που μας επιτρέπει να ανακατασκευάσουμε το μέτρο από την χαρακτηριστική συνάρτηση. Επίσης είδαμε ότι η ακολουθία των ροπών ενός μέτρου δεν προσδιορίζει το μέτρο. Γι' αυτό κατασκευάσαμε δύο διαφορετικά μέτρα με την ίδια ακολουθία ροπών. Δεν ακολούθησα τη μέθοδο των σημειώσεών σας, αλλά μια μέθοδο που βρίσκεται στο βιβλίο K. Stromberg, Probability for analysts. Συνιστώ να διαβάσετε προσεκτικά τα δύο πρώτα κεφάλαια αυτού του βιβλίου στα οποία βρίσκεται το απαραίτητο υπόβαθρο της ανάλυσης Fourier που θα χρειαστούμε. Με το δεύτερο κεφάλαιο αυτού (θεώρημα συνέχειας του Lévy) θα ασχοληθούμε την επόμενη φορά.

4.5 Τρ, 24/10/06: Ασθενής σύγκλιση και Θ. Helly

Ορίσαμε την έννοια της ασθενούς σύγκλισης μέτρων πιθανότητας σε κάποιο μέτρο πιθανότητας και είδαμε διάφορους ισοδύναμους τρόπους να εκφράσουμε το ίδιο πράγμα. Αποδείξαμε επίσης (σχεδόν) το Θεώρημα του Helly που λέει ότι tight ακολουθίες μέτρων πιθανότητας έχουν συγκλίνουσα (ασθενώς) υπακολουθία. Δώσαμε πλήρη απόδειξη μόνο στην περίπτωση που όλα τα μέτρα έχουν τον ίδιο συμπαγή φορέα.

4.5.1 Τρ, 24/10/06: ΑΝΑΚΟΙΝΩΣΗ: 1ο Διαγώνισμα

Το πρώτο διαγώνισμα θα γίνει την ώρα του μαθήματος την Παρασκευή 3/11/06. Διαβάστε ότι έχουμε κάνει από τις σημειώσεις του Varadhan καθώς και τα δύο πρώτα κεφάλαια (και τις ασκήσεις) από το βιβλίο του Karl Stromberg, Probability for Analysts.

4.6 Πα, 27/10/06: Θ. Lévy. Ασθενής νόμος μεγάλων αριθμών

Τελειώσαμε την απόδειξη του Θ. Lévy (ότι σύγκλιση κατά σημείο των χαρακτιριστικών συναρτήσεων συνεπάγεται ασθενή σύγκλιση των κατανομών). Είδαμε τη διατύπωση των ασθενών και των ισχυρών νόμων των μεγάλων αριθμών και είδαμε ότι ο ασθενής νόμος των μεγάλων αριθμών είναι μια απλή συνέπεια της ανισότητας του Chebyshev όταν υποθέσουμε ότι έχουμε να κάνουμε με κατανομή που έχει πεπερασμένη δεύτερη ροπή. Έπειτα δείξαμε το ίδιο θεώρημα χωρίς την υπόθεση ότι έχουμε δεύτερη ροπή, μόνο πρώτη. Είδαμε δύο αποδείξεις. Η μια χρησιμοποιούσε το Θ. σύγκλισης του Lévy και η άλλη όχι.

4.7 Τρ, 31/10/06: Ισχυρός νόμος μεγάλων αριθμών

Δείξαμε τον ισχυρό νόμο των μεγαλων αριθμών (σύγκλιση σχεδόν σίγουρα του $S_n/n$ στη μέση τιμή της $X_1$) υπό την προϋπόθεση ότι ${{\bf E}\left[{{\left\vert{X_1}\right\vert}^4}\right]} < \infty$.

Επίσης δείξαμε τις ανισότητες των Kolmogorov και Lévy που αφορούν την πιθανότητα το μέγιστο των ${\left\vert{S_1}\right\vert},\ldots,{\left\vert{S_n}\right\vert}$ να ξεπερνά ένα επίπεδο $\ell$.

4.8 Πα, 3/11/06: Πρώτο διαγώνισμα

Δείτε το εδώ σε PDF.

4.9 Τρ, 7/11/06: Ασκήσεις

Λύσαμε τις ασκήσεις του διαγωνίσματος και επεκταθήκαμε σε διάφορα άλλα προβλήματα έχοντας αυτές ως αφορμή.

4.10 Πα, 9/11/06: Θεώρημα Lévy

Δείξαμε το θ. Lévy που λέει ότι αν $X_i$ είναι ανεξάρτητες και $S_n = X_1+\cdots+X_n$ τότε το να συγκλίνει η $S_n$ ασθενώς, κατά πιθανότητα ή σχεδόν σίγουρα είναι ισοδύναμα.

Σας ζήτησα να μου γράψετε μέχρι την Τετάρτη 15/11/06 τις λύσεις των ασκήσεων 3.11 και 3.12.

4.10.1 Πα, 9/11/06: ΑΝΑΚΟΙΝΩΣΗ: Αναπλήρωση μαθήματος

Το μάθημα της 14/11/06 δε θα γίνει αφού το Πανεπιστήμιο θα είναι κλειστό:

ΠΡΑΚΤΙΚΑ  235ης/26-10-2006  ΣΥΝΕΔΡΙΑΣ  ΤΗΣ ΣΥΓΚΛΗΤΟΥ ΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ ΚΡΗΤΗΣ
	         				
Θέματα Ακαδημαϊκά

Θέμα: 1ο
Kαταλογισμοί σε μέλη ΔΕΠ. Εικοσιτετράωρη αναστολή λειτουργίας του Πανεπιστημίου Κρήτης.

	Τα μέλη της Συγκλήτου, αφού ενημερώθηκαν από τον κ. Πρύτανη και την κ.
Μ. Κεντούρη για την εκδίκαση της υπόθεσης που αφορά τους καταλογισμούς σε μέλη
ΔΕΠ στις 14-11-2006, ενώπιον του Ελεγκτικού Συνεδρίου κατέληξαν:

«ΕΙΚΟΣΙΤΕΤΡΑΩΡΗ ΑΝΑΣΤΟΛΗ ΛΕΙΤΟΥΡΓΙΑΣ 
ΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ ΚΡΗΤΗΣ

Όπως είναι γνωστό, στα μέλη της Επιτροπής Ερευνών του Πανεπιστημίου Κρήτης κατά
την  περίοδο 2002-2004 έχουν καταλογισθεί δαπάνες του Ειδικού Λογαριασμού
Κονδυλίων Έρευνας, των οποίων, χωρίς να αμφισβητείται η νομιμότητα, δεν
αναγνωρίσθηκε η σκοπιμότητα  από τον έλεγχο των Οικονομικών Επιθεωρητών. Οι
δαπάνες αυτές αφορούν σε μισθούς συμβασιούχων υπαλλήλων, οι οποίοι έχουν εν τω
μεταξύ μονιμοποιηθεί διότι κάλυπταν πάγιες και διαρκείς ανάγκες του
Πανεπιστημίου, καθώς και δαπάνη για τη συμπληρωματική ασφάλιση όλου του
προσωπικού που έγινε για να αντιμετωπισθούν σοβαρές ελλείψεις στην κάλυψη που
προσφέρει το Ελληνικό Δημόσιο στους εργαζομένους στο Πανεπιστήμιο.

Το Πανεπιστήμιο Κρήτης  εξ αρχής θεώρησε ότι οι εν λόγω δαπάνες έγιναν μέσα από
νόμιμες διαδικασίες για το συμφέρον του Ιδρύματος, εντός των σκοπών του
Ε.Λ.Κ.Ε. και χωρίς να δημιουργηθεί οποιοδήποτε έλλειμμα. Οι σχετικές αποφάσεις,
που ελήφθησαν από την Επιτροπή Ερευνών με τη συμμετοχή των συναδέλφων, ως
εκπροσώπων των Τμημάτων τους,  σε κάθε περίπτωση είτε είχαν τη σύμφωνη γνώμη
της Συγκλήτου, είτε ακολουθούσαν αποφάσεις της. 

Η ακαδημαϊκή κοινότητα του Πανεπιστημίου Κρήτης εξακολουθεί να στέκεται
αλληλέγγυα στους συναδέλφους που διώκονται, και να θεωρεί ότι στο πρόσωπό τους
διώκεται το Πανεπιστήμιο Κρήτης. Η Σύγκλητος του Πανεπιστημίου Κρήτης αποφάσισε
ομόφωνα να αναστείλει την λειτουργία του Ιδρύματος την 14η Νοεμβρίου 2006,
ημέρα κατά την οποία εκδικάζεται ενώπιον του Ελεγκτικού Συνεδρίου η αίτηση των
συναδέλφων αναστολής της εκτέλεσης της καταλογιστικής πράξης μέχρι η υπόθεση να
εκδικαστεί επί της ουσίας. Το μέτρο αυτό συνιστά ελάχιστη εκδήλωση
συμπαράστασης προς τους συναδέλφους οι οποίοι ανιδιοτελώς και σύννομα ενήργησαν
στο πλαίσιο συλλογικών οργάνων για τους σκοπούς που έχει ταχθεί να υπηρετεί το
Πανεπιστήμιο Κρήτης.»

Ακριβές απόσπασμα
Ρέθυμνο, 6-11-2006
Η Γραμματέας της Συγκλήτου

Μαρία Νεονάκη

Το μάθημα αυτό θα αναπληρωθεί την Τετάρτη 15/11/06, 3-5, στη Ζ 301.

4.11 Τε, 15/11/06: Θ. τριών σειρών και ισχυρός νόμος μεγάλων αριθμών

Ακολουθώντας τις σημειώσεις του Varadhan τελειώσαμε την απόδειξη του ισχυρού νόμου των μεγάλων αριθμών χωρίς υποθέσεις πεπερασμένης ανώτερης ροπής, αφού πρώτα δείξαμε το λεγόμενο θεώρημα τριών σειρών του Kolmogorov.

4.12 Τρ, 21/11/06: Κεντρικό Οριακό Θεώρημα. Εφαρμογές.

Διατυπώσαμε και αποδείξαμε το Κεντρικό Οριακό Θεώρημα ακολουθώντας τις σημειώσεις του Varadhan.

Από δω και πέρα θα βλέπουμε διάφορες εφαρμογές της Θ. Πιθανοτήτων σε άλλους τομείς των Μαθηματικών, και ειδικότερα θα βλέπουμε κυρίως μεθόδους απόδειξης μη πιθανοθεωρητικών θεωρημάτων με μεθόδους που χρησιμοποιούν τη Θ. Πιθανοτήτων.

Ως αρχή είδαμε μια απλή εφαρμογή πιθανοθεωρητικής μεθόδου στην απόδειξη ενός Θεωρήματος του Erdos για την ύπαρξη μεγάλων sum-free υποσυνόλων σε δοσμένα σύνολα ακεραίων. Μπορείτε να το βρείτε ως το Θεώρημα ένα σε αυτό το άρθρο (PDF).

4.12.1 Τε, 22/11/06: ΑΝΑΚΟΙΝΩΣΗ: Δεύτερο διαγώνισμα

Θα γίνει την Τρίτη 5/12/06 την ώρα του μαθήματος (είχαμε πει τη Δευτέρα 4/12/06 αλλά είχα ξεχάσει ότι θα λείπω).

4.13 Πα, 24/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)

Σήμερα είδαμε και νέα εφαρμογή της θ. Πιθανοτήτων σε προβλήματα που δεν προέρχονται από το χώρο των πιθανοτήτων. Συγκεκριμένα είδαμε πώς να κατασκευάσουμε, με ένα κατάλληλο πιθανοθεωρητικό μοντέλο, σύνολα φυσικών αριθμών που αποτελούν ασυμπτωτικές βάσεις με συνάρτηση αναπαράστασης η οποία είναι φραγμένη άνω και κάτω από πολλαπλάσια του $\log n$.

Μπορείτε να διαβάσετε για τη μέθοδο αυτή εφαρμοσμένη στο συγκεκριμένο πρόβλημα εδώ στη σελ. 6.

4.14 Τρ, 28/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)

Είδαμε μερικά παραδείγματα της πιθανοθεωρητικής μεθόδου:

• Δείξαμε ότι αν έχουμε $n$ διανύσματα μήκους 1 στον ${\mathbf R}^n$ τότε μπορούμε να διαλέξουμε πολλαπλασιαστές $\pm 1$ για το καθένα από αυτά ώστε το άθροισμα των διανυσμάτων αυτών με αυτούς τους πολλαπλασιαστές να έχει μήκος $\le \sqrt{n}$.
• Δείξαμε ότι οι περισσότεροι από τους αριθμούς $1,\ldots,n$ έχουν περίπου $\log\log n$ διαφορετικούς πρώτους στο ανάπτυγμά τους.

4.15 Πέ, 30/11/06: Η πιθανοθεωρητική μέθοδος (συνέχεια)

Είδαμε μερικά παραδείγματα της πιθανοθεωρητικής μεθόδου:

• Υπολογίσαμε άνω φράγμα σε υποσύνολα του ${\left\{{1,\ldots,n}\right\}}$ που έχουν τα αθροίσματα που αντιστοιχούν σε όλα τους τα υποσύνολα διαφορετικά.
• Δώσαμε μια πιθανοθεωρητική απόδειξη του θεωρήματος προσέγγισης του Weierstrass που οφείλεται στον Bernstein.
• Δώσαμε ένα εκθετικό άνω φράγμα για το πόσο μεγάλο πρέπει να είναι το $n$ ώστε σε κάθε χρωματισμό του ${\left\{{1,\ldots,n}\right\}}$ να μπορούμε να βρούμε μια αριθμητική πρόοδο μήκους $k$.

4.16 Τρ, 5/12/06: Δεύτερο διαγώνισμα.

Δείτε το εδώ σε PDF.

4.17 Πα, 8/12/06: Εντροπία και πληροφορία

Ορίσαμε την έννοια της εντροπίας $H(X)$ μιας ΤΜ (για την ακρίβεια, της κατανομής της $X$) και είδαμε μερικές βασικές ιδιότητές της και άλλων σχετικών ποσοτήτων.

4.18 Τρ, 12/12/06: Εντροπία και πληροφορία

Συνεχίσαμε σήμερα να βλέπουμε διάφορες ιδιότητες της εντροπίας και άλλων σχετικών εννοιών όπως της σχετικής εντροπίας (απόστασης KL) ή της κοινής πληροφορίας δύο ΤΜ.

4.18.1 Τρ, 12/12/06: ΑΝΑΚΟΙΝΩΣΗ: Έκτακτο μάθημα

Την Τετάρτη 13/12/06, 11-1, στο Γ111.

4.19 Τε, 13/12/06: Εντροπία και συμπίεση (κωδικοποίηση) πηγής

Εξετάσαμε το πρόβλημα του πώς να κωδικοποιήσουμε αποτελεσματικά ένα αλφάβητο $A$ όταν γνωρίζουμε μια κατανομή πιθανότητας στα στοιχεία του. Είδαμε κατ' αρχήν το συνδυαστικό πρόβλημα του πόσο μίκρές μπορούν να είναι οι λέξεις που κωδικοποιούν το αλφάβητο (ανισότητα Kraft) και έπειτα δείξαμε ότι το μέσο μήκος του κωδικοποιημένου συμβόλου του $A$ είναι τουλάχιστον ίσο με την εντροπία της κατανομής και ότι στο βέλτιστο κώδικα δε χρειάζεται να ξεπερνά την εντροπία +1. Τέλος είδαμε του κώδικες Huffman και αποδείξαμε ότι είναι βέλτιστοι (επιτυγχάνουν ελάχιστο μέσο μήκος κωδικοποίησης συμβόλου).

4.20 Πα, 15/12/06: Εντροπία στη συνδυαστική. Μετατροπή τυχαίας πηγής σε τυχαία bits

Είδαμε μερικές εφαρμογές της εντροπίας σε απόδειξη θεωρημάτων στη συνδυαστική. Επίσης αναλύσαμε το πρόβλημα του πώς βρίσκουμε μια συνάρτηση που παίρνει ως είσοδο μια $n$-άδα τυχαίων μεταβλητών $X_1, \ldots, X_n$ και επιστρέφει μια $K$-άδα ΤΜ $Y_1, \ldots, Y_K$, όπου $K$ είναι ακέραια ΤΜ και αν δεσμεύσουμε ως προς $K$ τότε το διάνυσμα $Y_1, \ldots, Y_K$ αποτελείται από ανεξάρτητες Bernoulli($1/2$). Λύσαμε το πρόβλημα όταν $n=1$ και $X_1$ ομοιόμορφη στο ${\left\{{0,\ldots,m-1}\right\}}$ και επίσης όταν $n$ είναι οτιδήποτε και $X_i$ είναι ανεξάρτητες Bernoulli($p$).

4.21 Τρ, 19/12/06: Το θεώρημα του J. Spencer για discrepancy

Δείξαμε ένα θεώρημα που οφείλεται στον J. Spencer και είναι το εξής: αν $A \in {\mathbf C}^{n \times n}$ είναι ένας τετράγωνος πίνακας με στοιχεία που έχουνε μέτρο $\le 1$ τότε υπάρχει διάνυσμα $v \in {\left\{{\pm 1}\right\}}^n$ τ.ώ. ${\left\Vert{Av}\right\Vert _\infty} \le C \sqrt{n}$, όπου $C>0$ απόλυτη σταθερά. Με την απλή πιθαοθεωρητική μέθοδο πετυχαίνουμε μόνο ${\left\Vert{Av}\right\Vert _\infty} \le \sqrt{n \log n}$. Κρίσιμη στην απόδειξη, όπως την παρουσιάσαμε, είναι και η χρήση της εντροπίας.