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

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

Τμήμα Μαθηματικών
Πανεπιστήμιο Κρήτης
Λεωφόρος Κνωσού
714 09 Ηράκλειο

E-mail: mk@fourier.math.uoc.gr

Άνοιξη 2001-02

Περιεχόμενα

• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
• 3 Βαθμολογικό Σύστημα - Εξετάσεις
• 4 Ημερολόγιο Μαθήματος
  • 4.1 Τρ, 12/2/02: Εισαγωγικά
  • 4.2 1η εργασία
  • 4.3 Τε, 13/2/02: Ανεξαρτησία, $L^2$ Νόμος Μεγάλων Αριθμών
  • 4.4 Τρ, 19/2/02: Εφαρμογές σε άλλους κλάδους των Μαθηματικών
  • 4.5 Τε, 20/2/02: Το πρόβλημα του συλλέκτη κουπονιών. Ο Ασθενής Νόμος των Μεγάλων αριθμών για $L^1$ ΤΜ
  • 4.6 2η εργασία
  • 4.7 Τρ, 26/2/02: Το θεώρημα Borel-Cantelli
  • 4.8 Πέ, 28/2/02: Βελτιωμένο Θ. Borel-Cantelli, μελέτη ακραίων τιμών (record values)
  • 4.9 3η εργασία
  • 4.10 Πέ, 7/03/02: Record Values (ξανά) και Head Runs
  • 4.11 4η εργασία
  • 4.12 Τρ, 12/03/02: Ισχυρός νόμος μεγάλων αριθμών. Εφαρμογές.
  • 4.13 Πέ, 14/03/02: Δεύτερη απόδειξη του Ισχυρού Νόμου με σύγκλιση σειρών
  • 4.14 5η εργασία
  • 4.15 Τρ, 19/3/02: Η ανισότητα Chernoff και εφαρμογές
  • 4.16 6η εργασία
  • 4.17 Πα, 22/3/02: Απόδειξη της ανισότητας Chernoff
  • 4.18 Τρ, 26/3/02: Μετασχηματισμός Fourier σε $d$ διαστάσεις
  • 4.19 Πέ, 28/3/02: Αντιστροφή Μετασχ. Fourier
  • 4.20 7η εργασία
  • 4.21 Τρ, 1/4/02: Θεώρημα Helly για tight ακολουθίες μέτρων πιθανότητας
  • 4.22 Πέ, 3/4/02: Θεώρημα συνέχειας του P. Levy
  • 4.23 8η εργασία
  • 4.24 Τρ, 9/4/02: Τέλος θεωρήματος συνέχειας. Κανονικές Τ.Μ.
  • 4.25 Πα, 12/4/02: Ιδιότητες μέτρων Gauss.
  • 4.26 Τρ, 16/4/02: Απόδειξη Κεντρικού Οριακού Θεωρήματος
  • 4.27 Πέ, 18/4/02: Λύση ασκήσεων
  • 4.28 9η εργασία
  • 4.29 Τρ, 13/5/02: Εφαρμογές σε άλλους τομείς Μαθηματικών
  • 4.30 Πέ, 15/5/02: Εφαρμογές σε άλλους τομείς Μαθηματικών
  • 4.31 Τρ, 21/5/02: Εφαρμογές σε άλλους τομείς των Μαθηματικών
  • 4.32 Πέ, 23/5/02: Εφαρμογές σε άλλους τομείς των Μαθηματικών

1 Ωράριο

Αίθουσα Α 105. Τρ 9-11, Πέ 2-4.

Ώρες γραφείου: Τρ 11-13 (Η 304)

2 Περιγραφή του μαθήματος

Σκοπός του μαθήματος αυτού είναι κυρίως η μελέτη Νόμων των Μεγάλων Αριθμών (Laws of Large Numbers) και Κεντρικών Οριακών Θεωρημάτων (Central Limit Theorems).

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

Το βιβλίο που θα χρησιμοποιηθεί κυρίως θα είναι το Probability: Theory and Examples, 2η έκδοση, του R. Durrett.

Επίσης χρησιμοποιούμε το βιβλίο του K. Stromberg Probability for Analysts.

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

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

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

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

4.1 Τρ, 12/2/02: Εισαγωγικά

Αναφερθήκαμε γρήγορα σε:

• Χώρους και μέτρα πιθανότητας
• Τυχαίες μεταβλητές με τιμές σε ένα χώρο που έχει σ-άλγεβρα (και ειδικότερα στο ${\mathbf R}$.
• Στο μέτρο (κατανομή) που επάγεται στο ${\mathbf R}$ από μια ΤΜ $X:\Omega\to{\mathbf R}$, καθώς και τη συνάρτηση κατανομής της $X$.
• Μέση τιμή της $X$ και της $f(X)$.
• Ανισότητες Jensen, Holder, Markov, Chebyshev

4.2 1η εργασία

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

4.3 Τε, 13/2/02: Ανεξαρτησία, $L^2$ Νόμος Μεγάλων Αριθμών

Ορίσαμε τι σημαίνει ανεξαρτησία ενδεχομένων και επίσης τι σημαίνει ανεξαρτησία μιας οικογένειας ΤΜ (αφού πρωτα ορίσαμε τι σημαίνει ανεξαρτησία μιας οικογένειας από σ-άλγεβρες και ορίσαμε και τι είναι η σ-άλγεβρα μιας ΤΜ $X$).

Δείξαμε τον $L^2$ νόμο των μεγάλων αριθμών, ο οποίος είναι μια απλή συνέπεια της ανισότητας Chebyshev. Ο νόμος αυτός λέει ότι αν έχουμε μια ακολουθία ανά δύο ασυσχέτιστων ΤΜ $X_i$ με κοινή μέση τιμή $\mu$ και ομοιόμορφα φραγμένη διασπορά, και ορίσουμε

$$S_n = X_1 + \cdots + X_n$$

τότε η ΤΜ $S_n / n$ συγκλίνει στη σταθερά $\mu$ κατά $L^2$. Δηλαδή

$${{\bf E}\left[{({1\over n} S_n - \mu)^2}\right]} \to 0. (n\to\infty).$$

Η $L^2$ σύγκλιση συνεπάγεται και σύγκλιση κατά πιθανότητα, δηλ. για κάθε $\epsilon>0$

$${{\bf {Pr}}\left[{{\left\vert{{1\over n} S_n - \mu}\right\vert} > \epsilon }\right]} \to 0.$$

4.4 Τρ, 19/2/02: Εφαρμογές σε άλλους κλάδους των Μαθηματικών

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

Είδαμε σήμερα τα εξής.

1. Χρησιμοποιήσαμε τις ιδιότητες της μέσης τιμής για να δείξουμε ότι κάθε σύνολο $B$ από $N$ διαφορετικούς φυσικούς αριθμούς περιέχει ένα υποσύνολο $A$ με μέγεθος τουλάχιστον $N/3$ μέσα στο οποίο υποσύνολο η εξίσωση $x+y=z$ δεν έχει λύση. Τέτοια σύνολα ονομάζονται sum-free και αυτό είναι ένα θεώρημα του Erdos.
2. Με ιδιότητες της μέσης τιμής μόνο επίσης δείξαμε ότι μπορεί κανείς να χρωματίσει με δύο χρώματα τις ακμές του πλήρους γραφήματος με $n$ κορυφές ώστε ο αριθμός των μονοχρωματικών τριγώνων που προκύπτουν να είναι το πολύ ${n \choose 3} / 4$.
3. Χρησιμοποιήσαμε τον ασθενή νόμο των μεγάλων αριθμών για να δείξουμε το θεώρημα του Weierstrass(κάθε συνεχής συνάρτηση σε κλειστό διάστημα προσεγγίζεται ομοιόμορφα από πολυώνυμα).
4. Δείξαμε ότι για $n\to\infty$ "τα περισσότερα" σημεία του κύβου $Q_n = (-1,1)^n$ έχουν ευκλείδιο μήκος ανάμεσα σε $\sqrt{({1\over 3}-\epsilon)n}$ και $\sqrt{({1\over 3}+\epsilon)n}$. Τα περισσότερα (σε όγκο) δηλαδή σημεία του κύβου βρίσκονται συγκεντρωμένα πολύ κοντά σε μια σφαίρα. Και αυτό ήταν συνέπεια του ασθενή νόμου των μεγάλων αριθμών.

4.5 Τε, 20/2/02: Το πρόβλημα του συλλέκτη κουπονιών. Ο Ασθενής Νόμος των Μεγάλων αριθμών για $L^1$ ΤΜ

Σήμερα, την πρώτη ώρα, μελετήσαμε το εξής πρόβλημα. Τραβούμε από ένα δοχείο με $N$ διαφορετικά αντικείμενα τυχαία ένα και το σημειώνουμε σ'ένα χαρτί. Μετά το επανατοποθετούμε μέσα στο κουτί και συνεχίζουμε να επιλέγουμε και να σημειώνουμε έως ότου έχουμε τραβήξει και τα $N$ διαφορετικά αντικείμενα από μια φορά το καθένα τουλάχιστον. Η ΤΜ που μας ενδιαφέρει εδώ είναι ο αριθμός των λήψεων που συμβαίνουν, έστω $T_N$. Είδαμε ότι ${{\bf E}\left[{T_N}\right]} = N \sum_{k=1}^N {1\over k} \sim N \log N$ και επίσης εκτιμήσαμε και τη διασπορά του $T_N$, πράγμα που μας επέτρεψε να δείξουμε ότι

$$(T_N - {{\bf E}\left[{T_N}\right]})/\sqrt{N \log N} \to 0,$$

κατά πιθανότητα.

Τη δεύτερη ώρα δείξαμε τον εξής νόμο μεγάλων αριθμών: Αν $X_1, X_2, \ldots$, είναι ανεξάρτητες και ισόνομες με ${{\bf E}\left[{{\left\vert{X_i}\right\vert}}\right]}<\infty$, και $S_n = X_1+\cdots+X_n$, τότε $S_n / n \to \mu = {{\bf E}\left[{X_1}\right]}$ κατά πιθανότητα.

4.6 2η εργασία

Από σελ. 46 του βιβλίου λύστε τις 1-4, 7,8.

4.7 Τρ, 26/2/02: Το θεώρημα Borel-Cantelli

Την πρώτη ώρα είδαμε την εφαρμογή του Θ. 5.5 του βιβλίου στη μελέτη του "προβλήματος του St. Petersburg". Αυτό είναι ένα παιχνίδι όπου η μέση τιμή του αναμενόμενου κέρδους ανά παιχνίδι είναι άπειρη, πράγμα που δυσκολεύει την εκτίμηση του πόσο πρέπει κανείς να πληρώσει για να παίξει αυτό το παιχνίδι ώστε "να είναι τίμιο". Αυτό τώρα δεν μπορεί πλέον να ερμηνευτεί ως ένα παιχνίδι του οποίου το κόστος είναι όσο και το μέσο κέρδος, για τον απλούστατο λόγο ότι το μέσο κέρδος είναι άπειρο, αλλά δεν μπορεί φυσικά το παιχνίδι αυτό να αποτιμηθεί ως άπειρο. Η εναλλακτική λύση είναι να δείξουμε με χρήση του Θ. 5.5 ένα ασθενή νόμο μεγάλων αριθμών της μορφής $(S_n - a_n) / b_n \to 0$ κατά πιθανότητα. Η ποσότητα $a_n$ δηλώνει τότε πόσο πρέπει να πληρώσει κανείς για να παίξει $n$ παιχνίδια.

Τη δεύτερη ώρα αποδείξαμε το Θ. Borel-Cantelli:

Θεώρημα 1 (α)   Αν $A_n$ είναι μια ακολουθία από ενδεχόμενα με $\sum_n{{\bf {Pr}}\left[{A_n}\right]}<\infty$ τότε η πιθανότητα να ισχύουν άπειρα από τα $A_n$ είναι 0.
(β) Αν $A_n$ είναι μια ακολουθία από ανεξάρτητα ενδεχόμενα με $\sum_n{{\bf {Pr}}\left[{A_n}\right]}=\infty$ τότε με πιθανότητα 1 ισχύουν άπειρα από αυτά.

4.8 Πέ, 28/2/02: Βελτιωμένο Θ. Borel-Cantelli, μελέτη ακραίων τιμών (record values)

Δείξαμε κατ' αρχήν το θεώρημα 6.7 που συνεπάγεται ότι η ύπαρξη πρώτης ροπής ( ${{\bf E}\left[{{\left\vert{X}\right\vert}}\right]}<\infty$) είναι αναγκαία συνθήκη για να έχουμε κάποιο μεγάλων αριθμών.

Έπειτα δείξαμε το θεώρημα 6.8 που αποτελεί ένα βελτιωμένο και ποσοτικοποημένο Θ. Borel-Cantelli.

Μελετήσαμε και το παράδειγμα 6.2 (record values). Προσέξτε γιατί στο βιβλίο η αιτιολόγηση της ανεξαρτησίας είναι ανεπαρκής. Στο πρόβλημα αυτό κάνουμε δειγματοληψία από ένα πληθυσμό (με συνεχή κατανομή) και τη χρονική στιγμή $k \in {\mathbf N}$ λέμε ότι έχουμε ρεκόρ αν $X_k > X_j$, για $j=1,2,\ldots,k-1$. Έστω $R_n$ το πόσα ρεκόρ έχουμε για χρόνο μέχρι $n$. Κατ'αρχήν υπολογίζουμε

$${{\bf E}\left[{R_n}\right]} = \sum_{k=1}^n {1\over k} \sim \log n.$$

Έπειτα δείχνουμε (και αυτό έχει αρκετή δουλειά που το βιβλίο σας κάπως θεωρεί προφανή) ότι τα ενδεχόμενα

$$A_k = {\left\{{X_k > X_j, \forall j<k}\right\}}, (k\in{\mathbf N}),$$

είναι ανεξάρτητα. Μετά από αυτό χρησιμοποιούμε το Θεώρημα 6.8 (βελτιωμένο Borel-Cantelli) για να δείξουμε ότι

$$R_n / \log n \to 1,$$

σχεδόν σίγουρα.

4.9 3η εργασία

Από σελ. 52 ασκήσεις 6.7 και 6.8, και από σελ. 55 ασκήσεις 6.10 και 6.11.

4.10 Πέ, 7/03/02: Record Values (ξανά) και Head Runs

Επαναλάβαμε τη μελέτη του προβλήματος για τα record values. Επίσης μελετήσαμε το πρόβλημα για τα head runs: ρίχνουμε άπειρες φορές ένα τίμιο νόμισμα και μελετάμε πόσο μεγάλο είναι το μέγιστο συνεχόμενο κομμάτι από κορώνες στις $n$ πρώτες ρίψεις. Δείξαμε ότι σχεδόν σίγουρα η ποσότητα αυτή είναι ασυμπτοτική με $\log n$, δηλ. το πηλίκο αυτής και του $\log n$ τείνει στο 1 για $n\to\infty$.

4.11 4η εργασία

Από σελ. 55 ασκήσεις: 6.9, 6.13-16

4.12 Τρ, 12/03/02: Ισχυρός νόμος μεγάλων αριθμών. Εφαρμογές.

Σήμερα είδαμε ότι με ακριβώς τις ίδιες προϋποθέσεις (για την ακρίβεια, με ασθενέστερες προϋποθέσεις, μια και απαιτείται μόνο ανεξαρτησία ανά δύο) που είχαμε βάλει για τον τελευταίο ασθενή νόμο που είχαμε δει, δηλ. ότι έχουμε $X_i$ ανεξάρτητα ανά δύο και ισόνομα (iid), έχουμε ${{\bf E}\left[{X_1}\right]} < \infty$ και $S_n = X_1+\cdots+X_n$, έπεται ότι $S_n /n \to {{\bf E}\left[{X_1}\right]}$, σχεδόν σίγουρα (και όχι μόνο κατά πιθανότητα, όπως είχαμε στον ασθενή νόμο).

Να θυμίσουμε εδώ ότι σε χώρο μέτρου πεπερασμένο (όπως είναι οι χώροι πιθανοτήτων) η σχεδόν παντού σύγκλιση συνεπάγεται σύγκλιση κατά μέτρο. Στην άλλη κατεύθυνση το μόνο που μπορούμε να πούμε είναι ότι αν μια ακολουθία συναρτήσεων συγκλίνει κατά μέτρο σε κάποιο όριο τότε υπάρχει μια υπακολουθία αυτής που συγκλίνει σχεδόν παντού στο ίδιο όριο. Με βάση αυτά που μόλις διαβάσατε δώστε προσοχή στην άσκηση 7.1 του βιβλίου σας η οποία είναι λάθος. Επίσης, η ανεξαρτησία που απαιτούνταν για τον ασθενή νόμο είναι ισχυρότερη πρϋπόθεση απ΄ ό,τι απαιτείται - η ανεξαρτησία ανά δύο φτάνει για να δώσει τον ισχυρό και συνεπώς και τον ασθενή νόμο.

Ως εφαρμογή νόμων ισχυρών αριθμών (όχι στην πραγματικότητα του τελευταίου αυτού νόμου, αλλά άλλων ασθενέστερων που έχουμε δει πριν, όπως αυτού που υποθέτει την ύπαρξη τέταρτης ροπής) είδαμε ότι σχεδόν όλοι οι πραγματικοί αριθμοί είναι κανονικοί. Αυτό σημαίνει ότι για κάθε βάση αριθμητικού συστήματος $b=2,3,\ldots$ όλα τα δυνατά ψηφία $0,1,\ldots,b-1$ εμφανίζονται ασυμπτοτικά με την ίδια συχνότητα στο $b$-αδικό ανάπτυγμα του αριθμού.

Επίσης είδαμε το θεώρημα Glivenko-Cantelli. Αν κάνουμε δειγματοληψία από ένα οποιοδήποτε πληθυσμό (οποιαδήποτε δηλ. κατανομή $F$) τότε σχεδόν σίγουρα η εμπειρική συνάρτηση κατανομής

$$F_n(x) = {1 \over n} \sum_{k=1}^n {\bf 1}\left( X_k \le x \right),$$

συγκλίνει ομοιόμορφα στο ${\mathbf R}$ στην πραγματική συνάρτηση καανομής $F$. Κάναμε την απόδειξη μόνο όταν η $F$ είναι συνεχής συνάρτηση, αλλά η ουσία δεν αλλάζει ιδιαίτερα και στη γενική περίπτωση.

4.13 Πέ, 14/03/02: Δεύτερη απόδειξη του Ισχυρού Νόμου με σύγκλιση σειρών

Σήμερα είδαμε κατ' αρχήν το 0-1 του Kolmogorov: Αν $X_1, X_2, \ldots$ είναι μια άπειρη ακολουθία ανεξαρτήτων ΤΜ και $A$ είναι ένα ενδεχόμενο που εξαρτάται μόνο τελικά από τα $X_i$ τότε οι μόνες δυνατές τιμές για το ${{\bf {Pr}}\left[{A}\right]}$ είναι 0 ή 1. Για παράδειγμα, μια ακολουθία ανεξαρτήτων ΤΜ έχει όριο με πιθανότητα 0 ή 1, δεν υπάρχουν άλλες δυνατές τιμές για αυτή την πιθανότητα. Δεν δώσαμε αυστηρή απόδειξη του Θεωρήματος αυτού, αλλά περιγραψαμε τα βήματα που απαιτούνται γι' αυτήν.

Έπειτα είδαμε την ανισότητα Kolmogorov: Αν $X_i$ είναι ανεξάρτητες με μέση τιμή 0 και πεπερασμένη δεύτερη ροπή τότε

$${{\bf {Pr}}\left[{\max_{k=1,\ldots,n}{\left\vert{S_k}\right\vert} \ge x}\right]} \le x^{-2}{{\bf Var}\left[{S_n}\right]},$$

όου $S_k = X_1+\cdots+X_k$ και $x>0$. Η ανισότητα Chebyshev μας δίνει την ίδια ανισότητα αλλά μόνο για το τελεαταίο άθροισμα $S_n$.

Χρησιμοποιήσαμε έπειτα την ανισότητα Kolmogorovγια να αποδείξουμε το κύριο θεώρημα για τη σύγκλιση σειρών με ανεξάρτητους όρους: Αν $X_i$ ανεξάρτητες με μέση τιμή 0 και $\sum_{n=1}^\infty {{\bf Var}\left[{X_n}\right]} < \infty$ τότε η σειρά $\sum_{k=1}^\infty X_k$ συγκλίνει σχεδόν σίγουρα.

Αναφέραμε και το Θεώρημα Τριών Σειρών του Kolmogorov το οποίο δίνει τη σύγκλιση τριών συγκεκριμένων σειρών ως αναγκαία και ικανή συνθήκη για τη σύγκλιση της σειράς $\sum_n X_n$. Δείξαμε τη μία μόνο κατεύθυνση του θεωρήματος αυτού (που όμως δε χρησιμοποιήσαμε σήμερα).

Πριν δώσουμε τη νέα απόδειξη του ισχυρού νόμου αποδείξαμε το λήμμα του Kronecker

$$a_{n+1}\ge a_n, a_n \to \infty, \sum{x_n\over a_n} = a \in {\mathbf R} \Longrightarrow {1\over a_n}\sum_{m=1}^n x_m \to 0.$$

Τέλος δώσαμε τη νέα απόδειξη του ισχυρού νόμου χρησιμοποιώντας αυτά που είδαμε σήμερα.

Επίσης δώσαμε την εξής, βελτιωμένη ποσοτικά, έκδοση του ισχυρού νόμου: Αν $X_i$ ανεξάρτητες και ισόνομες με μέση τιμή 0 και ${{\bf E}\left[{X_1^2}\right]} = \sigma^2 < \infty$, και $S_n = X_1+\cdots+X_n$ τότε, για κάθε $\epsilon>0$,

$${S_n \over n^{1/2} \log^{1/2 + \epsilon} n} \to 0,$$

σχεδόν σίγουρα. Παρατηρείστε ότι η προηγούμενη μορφή του ισχυρού νόμου που είχαμε δεί είχε στον παρανομαστή $n$ αντί για $n^{1/2} \log^{1/2 + \epsilon} n$ που έχουμε τώρα, άρα η τωρινή μορφή είναι πολύ καλύτερη ποσοτικά.

4.14 5η εργασία

Ασκήσεις 7.3, 8.1, 8.3, 8.4 και 8.5

4.15 Τρ, 19/3/02: Η ανισότητα Chernoff και εφαρμογές

Διατυπώσαμε το ακόλουθο.

Θεώρημα 2 (Chernoff)   Αν $Y$ είναι άθροισμα ανεξαρτήτων 0-1 μεταβλητών και $\mu = {{\bf E}\left[{Y}\right]}$ τότε

$${{\bf {Pr}}\left[{{\left\vert{Y - \mu}\right\vert} > \epsilon\mu}\right]} < 2 e^{-c_\epsilon \mu},$$ (1)

όπου

$$c_\epsilon = \min{\left\{{\epsilon^2/2, -\log(e^\epsilon(1+\epsilon)^{-(1+\epsilon)})}\right\}}.$$

Παρατήρηση: Όταν $\epsilon \to 0$ έχουμε $c_\epsilon = \epsilon^2/2$ ενώ όταν $\epsilon \to \infty$ έχουμε $c_\epsilon \sim \epsilon\log\epsilon$.

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

Θεώρημα 3 (Erdos, 1956)   Υπάρχει σύνολο θετικών ακεραίων $A$ και σταθερές $n_0, c_1, c_2$ τέτοιες ώστε αν $n \ge n_0$ υπάρχουν τουλάχιστον $c_1\log n$ και το πολύ $c_2 \log n$ διαφορετικές αναπαραστάσεις του $n$ ως άθροισμα δύο στοιχείων του $A$.

4.16 6η εργασία

Γράψτε προσεκτικά και σε όλη της τη λεπτομέρεια την απόδειξη του παραπάνω θεωρήματος του Erdos.

4.17 Πα, 22/3/02: Απόδειξη της ανισότητας Chernoff

Αφιερώσαμε τη σημερινή μέρα στην απόδειξη της ανισότητας Chernoff. Ακολουθήσαμε την απόδειξη στο βιβλίο "The Probabilistic Method" των N. Alon και J. Spencer (Appendix).

4.18 Τρ, 26/3/02: Μετασχηματισμός Fourier σε $d$ διαστάσεις

Σήμερα ορίσαμε το μετασχηματισμό Fourier $L^1$ συναρτήσεων και ολικά πεπερασμένων μέτρων στο ${\mathbf R}^d$. Είδαμε ότι τα $\widehat{\mu}$ και $\widehat{f}$ είναι ομοιόμορφα συνεχείς και φραγμένες συναρτήσεις και ότι (Riemann-Lebesgue) $\lim_{{\left\vert{\xi}\right\vert}\to\infty} \widehat{f}(\xi) = 0$ (το ίδιο δεν ισχύει για το $\widehat{\mu}$).

Ορίσαμε τον πυρήνα του Gauss $G(x)$ και υπολογίσαμε το μετασχηματισμό Fourier του

$$\widehat{G}(t) = (2\pi)^{d/2} G(t).$$

Ορίσαμε τη συνέλιξη $L^1$ συναρτήσεων, μιας συνάρτησης κι ενός μέτρου καθώς και δύο μέτρων και είδαμε τη βασική ανισότητα

$${\left\Vert{\mu*\nu}\right\Vert} \le {\left\Vert{\mu}\right\Vert}\cdot{\left\Vert{\nu}\right\Vert}.$$

Από δω και πέρα θα ακολουθούμε το βιβλίο του K. Stromberg Probability for Analysts.

4.19 Πέ, 28/3/02: Αντιστροφή Μετασχ. Fourier

Είδαμε ιδιότητες της συνέλιξης καθώς και τον ορισμό ασθενούς και ασθενούς * σύγκλισης μέτρων. Είδαμε ότι η συνέλιξη με προσέγγιση της μονάδας συγκλίνει (υπό διάφορες έννοιες) στο αντικείμενο που συνελίσσεται με την προσέγγιση (Θ. 1.9). Μετά είδαμε πώς "αντιστρέφουμε" το μετασχ. Fourier με summability, πράγμα το οποίο μας δίνει και τη μοναδικότητα του μετασχηματισμού. Είδαμε τον τύπο αντιστροφής όταν και ο μετασχ. Fourier είναι ολοκληρώσιμος, καθώς και τον έλεγχο του Dini, που μας δίνει ένα ικανό κριτήριο για να μπορούμε να ανακασκευάσουμε την συνάρτση σε ένα σημείο γνωρίζοντας το μετασχ. Fourier της συνάρτησης. Η αξία του κριτηρίου έγκειται στο ότι αναφέρεται μόνο στην ίδια τη συνάρτηση, και όχι στο μετασχηματισμό της, όπως ο τύπος αντιστροφής (που απαιτεί ο μετασχηματισμός να είναι ολοκληρώσιμος).

4.20 7η εργασία

Από τη σελ. 14 του βιβλίου (Stromberg): 1-4, 6, 7, 10, 11.

4.21 Τρ, 1/4/02: Θεώρημα Helly για tight ακολουθίες μέτρων πιθανότητας

Είδαμε σε ποιες περιπτώσεις μπορούμε να συνάγουμε ότι $\mu_n(A) \to \mu(A)$ γνωρίζοντας ότι $\mu_n \to \mu$ ασθενώς. Ορίσαμε πότε μια ακολουθία $\mu_n$ μέτρων πιθανότητας λέγεται tight (όταν τα μέτρα έχουν μικρή μάζα έξω από μεγάλες σφαίρες ταυτόχρονα για όλα τα $n$. Τέλος είδαμε το θεώρημα του Helly: αν η ακολουθία μέτρων πιθανότητας $\mu_n$ είναι tight τότε έχει ασθενώς συγκλίνουσα υπακολουθία.

Να ξεκαθαρίσω εδώ ποια είναι η μορφή του θεωρήματος αναπαράστασης του Riesz που χρησιμοποιήσαμε στις αποδείξεις: αν $T$ είναι ένα φραγμένο γραμμικό συναρτησοειδές στο χώρο $C_0({\mathbf R}^d)$ (ο οποίος έχει την ομοιόμορφη νόρμα - προσέξτε, ο χώρος δεν είναι πλήρης) τότε υπάρχει ένα μέτρο στο ${\mathbf R}^d$ με φραγμένη ολική κύμανση τέτοιο ώστε για κάθε $\phi \in C_0({\mathbf R}^d)$ έχουμε

$$T(\phi) = \int_{{\mathbf R}^d} \phi(x) d\mu(x).$$

Επιπλέον, αν το $T$ είναι μη αρνητικό (δηλ. $\phi\ge0$ συνεπάγεται $T(\phi)\ge0$) το μέτρο $\mu$ είναι μη αρνητικό.

4.22 Πέ, 3/4/02: Θεώρημα συνέχειας του P. Levy

Σήμερα δείξαμε το κυριότερο μέρος του Θ. συνέχειας του P. Levy. Δείξαμε ότι αν τα $\mu_n$ είναι μέτρα πιθανότητας στο ${\mathbf R}^d$ και $f:{\mathbf R}^d\to{\mathbf C}$ τ.ώ. $\mu_n(t) \to f(t)$ για $t \in {\mathbf R}^d$, τότε αν $f$ συνεχής στο 0 η ακολουθία $\mu_n$ είναι tight.

Για την απόδειξη χρησιμοποιήσαμε φυσικά ανάλυση Fourier. Εισαγάγαμε τον πυρήνα του Fejer $K(x) = (1-{\left\vert{x}\right\vert})^+$ ο οποίος έχει τη σημαντική ιδιότητα να έχει μη αρνητικό $\widehat{K}$. Εκτιμήσαμε τη μάζα του μέτρου $\mu_n$ πάνω σε ένα διάστημα $(-R, R)$ (κάναμε την απόδειξη μόνο στη μία διάσταση-δεν αλλάζει σχεδόν τίποτα στις πολλές) προς τα κάτω από την ποσότητα

$$\int K(x/R) d\mu_n(x)$$

. Αυτή την ποσότητα την εκτιμήσαμε χρησιμοποιώντας δυϊσμό, δηλ. την ταυτότητα

$$\int \widehat{f(x)}  d\mu(x) = \int f(x) \widehat{\mu}(x)  dx.$$

4.23 8η εργασία

Από τη σελ. 26 του βιβλίου (Stromberg): 2, 3, 4, 6, 7, 9.

4.24 Τρ, 9/4/02: Τέλος θεωρήματος συνέχειας. Κανονικές Τ.Μ.

Τελειώσαμε την απόδειξη του Θ. συνέχειας του Levy. Είδαμε ότι αυτό συνεπάγεται ότι αν έχουμε μέτρα πιθανότητας που συγκλίνουν κατά σημείο σε κάποιο άλλο μέτρο πιθανότητας, τότε συγκλίνουν σε αυτό ομοιόμορφα στα συμπαγή του ${\mathbf R}^d$ και ασθενώς.

Αρχίσαμε να συζητάμε για τις αλγεβρικές κυρίως ιδιότητες των κανονικών μέτρων πιθανότητας.

4.25 Πα, 12/4/02: Ιδιότητες μέτρων Gauss.

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

$${{\bf E}\left[{e^{itX}}\right]} = e^{i t\cdot m} e^{-{1\over 2}Q(t)},$$

όπου $m$ είναι η μέση τιμή του τυχαίου διανύσματος $X$ και $Q$ είναι μια θετικά ημιορισμένη τετραγωνική μορφή.

4.26 Τρ, 16/4/02: Απόδειξη Κεντρικού Οριακού Θεωρήματος

Σήμερα δείξαμε πώς μπορούμε να υπολογίσουμε τις παραγώγους της χαρακτηριστικής συνάρτησης $f(t) = {{\bf E}\left[{e^{itX}}\right]}$ μιας ΤΜ $X$ μέσω των ροπών της $X$ (για τιμές της παραγώγου στο $0$).

Χρησιμοποιήσαμε αυτό για να δείξουμε το Κεντρικό Οριακό Θεώρημα Lindeberg-Levy.

4.27 Πέ, 18/4/02: Λύση ασκήσεων

Σήμερα ασχοληθήκαμε με λύση ασκήσεων κατά τη διάρκεια του μαθήματος (αυτές της σελίδας 14 του βιβλίου).

4.28 9η εργασία

Από τη σελ. 106 του βιβλίου (Stromberg): 1, 2, 3, 14, 17, 18, 20, 22.

4.29 Τρ, 13/5/02: Εφαρμογές σε άλλους τομείς Μαθηματικών

Ένα σύνολο $A \subseteq {\mathbf R}$ λέγεται universal in measure αν για κάθε σύνολο $E \subseteq {\mathbf R}$ με θετικό μέτρο υπάρχει ένα $x \in {\mathbf R}$ και $t>0$ τέτοια ώστε $x+tA \subseteq E$. Υπάρχει δηλαδή ένα τουλάχιστον αφφινικό αντίγραφο του $A$ μέσα σε κάθε σύνολο θετικού μέτρου.

Κοιτώντας στη γειτονιά ενός σημείου πυκνότητας ενός συνόλου $E$ με θετικό μέτρο έυκολα βλέπει κανείς πως όλα τα πεπερασμένα σύνολα είναι universal in measure. Υπάρχει μια εικασία του Erdos που λέει ότι δεν υπάρχουν άπειρα σύνολα που να είναι universal. Αυτή δεν έχει αποδειχθεί.

Δείξαμε σήμερα μια πιθανοθεωρητική κατασκευή, δεδομένου ενός άπειρου συνόλου $A$, που κατασκευάζει ένα σύνολο $E$ θετικού μέτρου τ.ώ. το σύνολο

$${\left\{{(x,t): x+tA \subseteq E}\right\}}$$

έχει (διδιάστατο) μέτρο μηδέν. Δοθέντος δηλαδή του $A$ φτιάξαμε ένα σύνολο $E$ που δεν περιέχει σχεδόν κανένα αφφινικό αντίγραφο του $E$.

Μπορείτε να βρείτε τις λεπτομέρειες σε αυτή εδώ την εργασία.

4.30 Πέ, 15/5/02: Εφαρμογές σε άλλους τομείς Μαθηματικών

Δείξαμε κατ'αρχήν το ακόλουθο πολύ χρήσιμο θεώρημα:

Θεώρημα 4   Έστω $a_{ij}, i=1,\ldots,n_1, j=1,\ldots,n_2$, πίνακας μιγαδικών αριθμών, με ${\left\vert{a_{ij}}\right\vert} \le 1$. Έστω επίσης $p_1,\ldots,p_{n_2} \in [0,1]$ και οι ΤΜ $\xi_1,\ldots,\xi_{n_2}$ είναι ανεξάρτητες και

$$\xi_j = \left\{\begin{array}{ll} 1-p_j & \mbox{with probabi... ... -p_j & \mbox{with probability $1-p_j$}, \end{array}\right.$$ (2)

Τότε, με πιθανότητα που τείνει στο 1 όταν $n_1 \to \infty$

$${\left\vert{\sum_{j=1}^{n_2} a_{ij} \xi_j}\right\vert} \le C \sqrt{n_2 \log n_1}, \mbox{for all $i=1,\ldots,n_1$},$$

όπου $C$ είναι μια απόλυτη σταθερά.

Χρησιμοποιώντας αυτό δείξαμε το ακόλουθο Θεώρημα που αφορά σε τριγωνομετρικά πολυώνυμα:

Θεώρημα 5   (Salemκαι Zygmund) Έστω $f_1(x), \ldots , f_n(x)$, τριγωνομετρικά πολυώνυμα βαθμού το πολύ $m$, και $\xi_1, \ldots , \xi_n$ είναι ανεξάρτητες ΤΜ

$$\xi_j = \left\{\begin{array}{ll} 1-p_j & \mbox{with probabi... ... -p_j & \mbox{with probability $1-p_j$}, \end{array}\right.$$ (3)

για κάποια $p_j \in [0,1]$. Γράφουμε

$$f(x) = \sum_{j=1}^n \xi_j f_j(x).$$

Τότε, για κάποιο $C > 0$,

$${{\bf {Pr}}\left[{{\left\Vert{f}\right\Vert _\infty} \le C ... ...log m\right)^{1/2}}\right]} \to 1, \mbox{as $m\to\infty$}.$$

Χρησιμοποιήσαμε τέλος το Θεώρημα Salem- Zygmund για να δώσουμε μια πιθανοθεωρητική κατασκευή για ένα τριγωνομετρικό πολυώνυμο

$$p(x) = M + \sum_{j=1}^{cN} \cos{\lambda_j x} \ge 0$$

με $c>0$ μια απόλυτη σταθερά, τα $\lambda_j$ διαφορετικούς ακεραίους και

$$M \le C \sqrt{N \log N}.$$

με $C > 0$ μια απόλυτη σταθερά.

Περισσότερες λεπτομέρειες εδώ.

4.31 Τρ, 21/5/02: Εφαρμογές σε άλλους τομείς των Μαθηματικών

Σήμερα χρησιμοποιήσαμε μια παραλλαγή του Θ. Salem- Zygmundγια να δείξουμε την εξής πρόταση:

Θεώρημα 6 (Bourgain)   Υπάρχει απόλυτη σταθερά $C > 0$ τέτοια ώστε για κάθε $N$ υπάρχουν θετικοί διαφορετικοί ακέραιοι $\lambda_1,\ldots,\lambda_N$ έτσι ώστε

$${\left\Vert{\sum_{j=1}^N \sin{\lambda_j x}}\right\Vert _\infty} \le C N^{2/3}.$$

Ή τετριμμένη άνω εκτίμηση είναι $N$ και η εκτίμηση που ισχύει από κάτω είναι $\ge N^{1/2}$ μια και η $\infty$-νόρμα φράσσει την 2-νόρμα.

4.32 Πέ, 23/5/02: Εφαρμογές σε άλλους τομείς των Μαθηματικών

Δείξαμε σήμερα τη μέθοδο των πιθανοτήτων υπό συνθήκη (method of conditional probabilities) για την άλγοριθμική κατασκευή αντικειμένων των οποίων η ύπαρξη έχει αποδειχτεί πιθανοθεωρητικά. Είναι μια πολύ γενικής εφαρμογής μέθοδος, και επιτρέπει πολλές φορές να κατασκευάζει κανείς γρήγορα τα αντικείμενα αυτά.