Στοχαστικές Ανελίξεις
Μεταπτυχιακό Μάθημα

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

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

E-mail: kolount@member.ams.org

Ανοιξη 2002-03

1 Ωράριο

ΡΑ 105: Δε 1-3, Τε 11-1.

2 Βιβλίο

Θα ακολουθήσουμε, κατ' αρχήν, το βιβλίο των Z. Brzezniak και T. Zastawniak, με τίτλο Basic Stochastic Processes (Springer, 1998).

3 Βαθμολογικό Σύστημα

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

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

4.1 Δε, 17/2/03: Εισαγωγή

Σήμερα είπαμε μερικές γενικότητες για το μάθημα και αρχίσαμε να κοιτάμε το παράδειγμα του τυχαίου περίπατου (random walk). Δείξαμε ότι στη μία διάσταση ο συμμετρικός τυχαίος περίπατος (στους ακεραίους) επανέρχεται άπειρες φορές στο 0, σχεδόν σίγουρα.

4.2 Τε, 19/2/03: Εισαγωγή. Δεσμευμένη μέση τιμή

Δείξαμε (σε συνέχεια του προηγουμένου) ότι ο συμμετρικόες τυχαίος περίπατος σε 2 διαστάσεις επανέρχεται άπειρες φορές σχεδόν σίγουρα. Επίσης ότι στις 3 και πάνω διαστάσεις σχεδόν σίγουρα επανέρχεται μόνο πεπερασμένες φορές (στο 0).

Ορίσαμε την ΤΜ ${{\bf E}\left[{X {\ \vert\ }Y}\right]}$ όταν $Y$ είναι μια διακριτή ΤΜ και είδαμε μερικές ιδιότητες αυτού του νέου συμβόλου.

4.3 Δε, 24/2/03: ${{\bf E}\left [{X{\ \vert\ }{\cal G}}\right ]}$ για $\sigma$-άλγεβρα ${\cal G}$. Martingales.

Ορίσαμε το τι σημαίνει να δεσμεύσουμε μια ΤΜ ως προς μια $\sigma$-άλγεβρα, η οποία συνήθως είναι η άλγεβρα που ορίζει μια άλλη (ή περισσότερες) ΤΜ. Δεν αποδείξαμε το θεώρημα που ισχυρίζεται ότι αυτή η νέα ΤΜ υπάρχει πάντα και έχει τις ζητούμενες ιδιότητες.

Είδαμε πότε μια ακολουθία από ΤΜ ονομάζεται martingale και είδαμε διάφορα παραδείγματα από τέτοιες ακολουθίες.

4.4 Τε, 26/2/03: -

Το μάθημα δεν έγινε.

4.5 Δε και Τε, 3 και 5/3/03: Gambling strategies, stopping times, optional stopping theorem και εφαρμογές

4.6 Δε και Τε, 7 και 9/4/03: πεπερασμένες αλυσίδες Markov.

Δείτε εδώ.

4.7 Πα, 11/4/03: Ανέλιξη Poisson.

Είδαμε την ανέλιξη Poisson, η οποία είναι μια ανέλιξη $N(t)$ σε συνεχή χρόνο ( $t \in [0,\infty)$) και με διακριτές τιμές $N(t) = 0, 1, 2, \ldots$. Η ανέλιξη αυτή προκύπτει ως το πλήθος των ``γεγονότων'' που έχουν συμβεί μέχρι χρόνο $t$, όταν υποθέσουμε ότι ο χρόνος ανάμεσα σε δύο διαδοχικά γεγονότα ακολουθεί την εκθετική κατανομή και οι ενδιάμεσοι αυτοί χρόνοι είναι μεταξύ τους ανεξάρτητοι.

Είδαμε την ιδιότητα ``έλλειψης μνήμης'' της εκθετικής κατανομής και πώς αυτή μεταφράζεται σε ``ανεξάρτητες και στάσιμες προσαυξήσεις'' της $N(t)$.

4.8 Δε, Τε και Πα, 14, 16 και 18/4/03: Η ανέλιξη Wiener (κίνηση Brown)

Λύστε τις ασκήσεις που βρίσκονται εδώ σε μορφή Postscript.

4.9 Υπόλοιπο του μαθήματος, συγκεντρωτικά

4.9.1 Στοχαστικός λογισμός

Ορίσαμε το στοχαστικό ολοκλήρωμα ως προς την κίνηση Brown. Μέσω αυτού ορίσαμε το στοχαστικό διαφορικό και είδαμε το λήμμα του Itô.

4.9.2 Εφαρμογές: Τιμολόγηση παραγώγων προϊόντων

Ασχοληθήκαμε με εφαρμογές του στοχαστικού λογισμού σε χρηματοικονομικά μαθηματικά και ειδικότερα στην τιμολόγηση (pricing) παραγώγων προϊόντων (derivative products).

• Είδαμε τη βασική μέθοδο τιμολόγησης προϊόντων μέσω του ``αξιώματος'' έλλειψης arbitrage.
• Είδαμε πώς αυτή η μέθοδος εφαρμόζεται στην τιμολόγηση ενός European call option όταν το μοντέλο για την τιμή $S$ της μετοχής (stock) στην οποία αναφέρεται είναι η λεγόμενη γεωμετρική κίνηση Brown:
  $${dS \over S} = \mu dt + \sigma dW.$$
  Η έλλειψη arbitrage οδηγεί στην εξίσωση με μερικές παραγώγους των Black, Scholes και Merton, της οποίας η λύση μας δίνει την τιμή του παραγώγου προϊόντος.
• Είδαμε τη λεγόμενη διωνυμική μέθοδο τιμολόγησης (binomial pricing method) στην οποία υποθέτουμε ότι ο χρόνος είναι διακριτός και ότι η τιμή της μετοχής αλλάζει κάθε χρονική στιγμή είτε επαυξανόμενη κατά ένα προκαθορισμένο ποσοστό είτε μειούμενη κατά ένα ποσοστό. Όταν το βήμα του χρόνου $\Delta t$ τείνει στο 0 αυτό το μοντέλο προσεγγίζει τη γεωμετρική κίνηση Brown (όπως ακριβώς ένας τυχαίος περίπατος προσεγγίζει την κίνηση Brown). Η μέθοδος αυτή τιμολόγησης είναι μάλλον πιο ευέλικτη, αν και ενδεχομένως υπολογιστικά πιο χρονοβόρα, από τη λύση της εξίσωσης Black-Scholes-Merton. Είδαμε πώς να τιμολογούμε European αλλά και American options με τη μέθοδο αυτή.

4.9.3 Εφαρμογές: σε αλγορίθμους

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

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

• Έστω το πλήρες γράφημα $K_n$, μια συλλογή δηλ. από $n$ κόμβους και ${n \choose 2}$ ακμές που συνδέουν όλους τους κόμβους ανά δύο. Ζητάμε τρόπο να χρωματίσουμε τις ακμές του $K_n$ με δύο χρώματα, ας πούμε κόκκινο και μπλέ, έτσι ώστε να μην έχουμε πολλά μονοχρωματικά τρίγωνα (ένα μονοχρωματικό τρίγωνο είναι μια τριάδα κόμβων πού και οι τρείς ακμές που τους συνδέουν ανά δύο είναι το ίδιο χρώμα).

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

  Είδαμε τη ``μέθοδο των πιθανοτήτων υπό συνθήκη'' για τη ντετερμινιστικοποίηση του πιθανοτικού αυτού αλγορίθμου. Αυτή η μέθοδος συνίσταται στο να επιλέγει κανείς τις τιμές των τυχαίων μεταβλητών που χρησιμοποιεί η πιθανοτικός αλγόριθμος (στην προκειμένη περίπτωση του χρωματισμού των ακμών του $K_n$ αυτό σημαίνει ότι επιλέγει κανείς τα χρώματα των ακμών), τη μία μετά την άλλη, με τρόπο ώστε να μην μειώνει την πιθανότητα επιτυχίας του πιθανοτικού αλγορίθμου δεδομένων των μέχρι τώρα επιλογών του. Αυτό συνεπάγεται ότι όταν έχουν πλέον προσδιοριστεί οι τιμές όλων τυχαίων μεταβλητών τότε έχουμε βρεί μια λύση του προβλήματος.

• Ένα άλλο πρόβλημα για το οποίο είδαμε ένα πιθανοτικό αλγόριθμο και την ντετερμινιστικοποίησή του είναι το πρόβλημα της έυρεσης sum-free υποσυνόλου. Ένα σύνολο $A$ ακεραίων λέγεται sum-free αν $x+y\neq z$ για κάθε επιλογή των $x, y, z \in A$. Είδαμε ένα θεώρημα του Erdos ότι κάθε σύνολο ακεραίων με $N$ στοιχεία έχει ένα sum-free υποσύνολο με τουλάχιστον $N/3$ στοιχεία. Η απόδειξη του θεωρήματος αυτού αποτελεί ταυτόχρονα και ένα πιθανοτικό αλγόριθμο για την εύρεση του υποσυνόλου. Είδαμε και την ντετερμινιστικοποίηση αυτού του αλγορίθμου, χωρίς ο αλγόριθμος που προκύπτει να είναι ιδιαίτερα πιο αργός. Αυτή τη φορά η ντετερμινιστικοποίηση βασίστηκε στο ότι ο χώρος πιθανοτήτων που χρησιμοποιούνταν στον αρχικό πιθανοτικό αλγόριθμο ήταν ``μικρός'' και άρα μπορούσαμε να τον ψάξουμε πλήρως, χωρίς μεγάλο κόστος σε χρόνο.
• Τέλος είδαμε τα πολύ βασικά στοιχεία της μεθόδου Markov Chain Monte Carlo (MCMC). Πολλά προβλήματα επιλύονται με μεθόδους Monte Carlo, που απαιτούν την παραγωγή τυχαίων στοιχείων ενός συνόλου A με ομοιόμορφο μέτρο πιθανότητας. Για παράδειγμα, μπορεί κανείς ``εύκολα'' να υπολογίζει μια καλή προσέγγιση στο ολοκλήρωμα $\int_A f(x) dx$ αν μπορεί να πάρει $n$ ανεξάρτητα αντίγραφα $X_1,\ldots,X_n$, για μεγάλο $n$, μιας τυχαίας μεταβλητής ομοιόμορφα κατανεμημένης στο σύνολο $A$. Προσεγγίζει τότε το ολοκλήρωμα $\int_A f(x) dx$ με το μέσο όρο ${\left\vert{A}\right\vert}/n(X_1+\cdots+X_n)$.

  Δεν είναι όμως πάντα εύκολο να παράγει κανείς τυχαία στοιχεία του $A$ με την ομοιόμορφη (ή οποιαδήποτε άλλη δεδομένη) κατανομή. Πώς θα παραγάγετε για παράδειγμα τυχαία στοιχεία του $S_n$, του συνόλου όλων των μεταθέσεων του συνόλου ${\left\{{1,\ldots,n}\right\}}$ με την ομοιόμορφη κατανομή; Η MCMC μέθοδος που είδαμε πετυχαίνει αυτό ξεκινώντας από κάποιο, σταθερό, σημείο του $A$ και ακολουθώντας ένα τυχαίο περίπατο πάνω σε ένα κατάλληλο γράφημα με κορυφές τα στοιχεία του $A$. Το γράφημα αυτό πρέπει έτσι να έχει επιλεγεί ώστε να υπάρχει μόνο μια στάσιμη κατανομή (υπό την μετάβαση του τυχαίου περιπάτου) πάνω στο $A$, η επιθυμητή (ομοιόμορφη ή άλλη) κατανομή. Πρέπει επίσης η ``σύγκλιση'' στην στάσιμη αυτή κατανομή να είναι ταχεία. Έτσι, μετά από σύντομο χρόνο τυχαίας κίνησης πάνω στο γράφημα, σταματάμε και δηλώνουμε το τρέχον στοιχείο ως το τυχαίο στοιχείο του $A$.

4.10 Ασκήσεις

Λύστε τις ασκήσεις που βρίσκονται εδώ σε μορφή Postscript.