Στο εισαγωγικό μάθημα Πιθανοτήτων μαθαίνει κανείς τα βασικά
αντικείμενα της θεωρίας των Πιθανοτήτων, τους χώρους πιθανότητας
(probability spaces) και τις τυχαίες μεταβλητές (random variables). Με
τα αντικείμενα αυτά μπορεί να μελετηθεί η κατάσταση ενός
συστήματος ανάλογα με το αποτέλεσμα ενός πειράματος τύχης και γι' αυτόν
το λόγο η έννοια του χρόνου συνήθως δεν υπεισέρχεται στα προβλήματα
που αναλύονται. Σκοπός αυτών των σημειώσεων είναι να εισαγάγουν τον
αναγνώστη στη μοντελοποίηση και στην ανάλυση φαινομένων τα οποία
εξελίσσονται στον χρόνο με τρόπο που εμφανίζει κάποια τυχαιότητα. Τα
μαθηματικά αντικείμενα που μοντελοποιούν τέτοια φαινόμενα είναι οι
στοχαστικές διαδικασίες (stochastic processes), με την περιγραφή και την κατασκευή των
οποίων θα ασχοληθούμε στο πρώτο κεφάλαιο.
1.2 Κατανομές πεπερασμένης διάστασης
Υπάρχουν διάφοροι ισοδύναμοι τρόποι να ορίσει κανείς μια στοχαστική
διαδικασία. Σε κάθε περίπτωση χρειαζόμαστε ένα σύνολο \(\X \), που ονομάζεται
χώρος καταστάσεων (state space) και στο οποίο ανήκουν οι τιμές που
παίρνει η στοχαστική διαδικασία και ένα σύνολο \( Τ \) που είναι συνήθως-
χωρίς αυτό να είναι κανόνας- ένα σύνολο χρόνων, π.χ. \[ Τ =
[0,+\infty)\quad\text{ ή }\quad T = \N_0= \{0,1,2,\ldots\}. \] Ο
απλούστερος τρόπος να ορίσει κανείς μια στοχαστική διαδικασία,
ορισμένη στο \(T\) και με τιμές στο \(\X \) είναι ως μια συλλογή από
τυχαίες μεταβλητές \(\{X_t\}_{t\in T}\), ορισμένες σε έναν χώρο
πιθανότητας \((\Omega,{\cal F},\P) \), με τιμές στο \(\X\). Σ' αυτήν
την περίπτωση, για κάθε \(t \in T\), η τυχαία μεταβλητή \(X_t : \Omega
\ni \omega \mapsto X_t(\omega) \in \X\) περιγράφει την κατάσταση του
συστήματος που μας ενδιαφέρει την χρονική στιγμή \(t\) και η συλλογή
τους περιγράφει την κατάσταση του συστήματος κάθε χρονική στιγμή στο
σύνολο \(T\).
Ένας άλλος τρόπος να δει κανείς μια στοχαστική διαδικασία
είναι να θεωρήσει για κάθε \(\omega \in \Omega \) την τροχιά της
στοχαστικής διαδικασίας, καθώς ο δείκτης \(t \) μεταβάλλεται στο \(T
\), να δει δηλαδή την \(t \mapsto X_t(\omega) \) ως μια συνάρτηση από
το \(T \) στο \(\X \). Σ' αυτή την περίπτωση η στοχαστική
διαδικασία είναι μια τυχαία συνάρτηση, δηλαδή μια τυχαία μεταβλητή
ορισμένη στο \(\Omega \) με τιμές στο σύνολο \(\X^T \) των
συναρτήσεων από το \(T \) στο \(\X \).
Παράδειγμα 1.1 Στρίβουμε ένα
κέρμα τρεις φορές. Ξεκινώντας από το μηδέν κάνουμε ένα βήμα προς τα
δεξιά κάθε φορά που φέρνουμε κεφαλή και ένα βήμα προς τα αριστερά
κάθε φορά που φέρνουμε γράμματα. Μπορούμε να περιγράψουμε την θέση μας
ως μια στοχαστική διαδικασία ορισμένη στο σύνολο χρόνων \(T =
\{0,1,2,3\} \) με τιμές στον χώρο καταστάσεων \(\Z \). Πράγματι, αν
για \(k=0,1,2,3 \) συμβολίζουμε με \(X_k \) τη θέση μας μετά από
\(k\) στριψίματα, τότε οι \(\{X_k\}_{k \in T} \) είναι τυχαίες
μεταβλητές με τιμές στον \(\Z\), που μπορούμε να τις ορίσουμε στον
δειγματικό χώρο \[ \Omega = \{ KKK, KK\Gamma, K\Gamma K,
K\Gamma\Gamma, \Gamma KK, \Gamma K\Gamma, \Gamma\Gamma K,
\Gamma\Gamma\Gamma \}. \] Έχουμε λοιπόν \(X_0(\omega)=0 \) για κάθε
\(\omega \in \Omega \)και \[ X_1(\omega) = \begin{cases} +1, &
\text{ αν } \omega \in \{ KKK, KK\Gamma, K\Gamma K, K\Gamma\Gamma\}\\
-1, & \text{ αν } \omega \in \{\Gamma KK, \Gamma K\Gamma, \Gamma\Gamma
K, \Gamma\Gamma\Gamma \}, \end{cases} \] \[ X_2(\omega) =
\begin{cases} +2, & \text{ αν } \omega \in \{ KKK, KK\Gamma \} \\ 0, &
\text{ αν } \omega \in \{ K\Gamma K, K\Gamma\Gamma, \Gamma KK, \Gamma
K\Gamma\} \\ -2, & \text{ αν } \omega \in \{\Gamma\Gamma K,
\Gamma\Gamma\Gamma \}, \end{cases} \] \[ X_3(\omega) = \begin{cases}
+3, & \text{ αν } \omega = KKK \\ +1, & \text{ αν } \omega \in \{
KK\Gamma, K\Gamma K, \Gamma KK \} \\ -1, & \text{ αν } \omega \in
\{\Gamma\Gamma K, \Gamma K\Gamma, K\Gamma\Gamma \}\\ -3, & \text{ αν }
\omega = \Gamma\Gamma\Gamma . \end{cases} \]
Αν δούμε την ίδια
στοχαστική διαδικασία ως μια τυχαία μεταβλητή με τιμές στον \(\Z^T \)
έχουμε ότι \[ X_\cdot(KKK) = (0,1,2,3),\quad X_\cdot(KK\Gamma) =
(0,1,2,1),\quad X_\cdot(K\Gamma K) = (0,1,0,1)\quad \text{ κ.λπ.} \]
Παρατηρήστε ότι κάθε \(\omega \in \Omega \) απεικονίζεται σε μια
τροχιά μήκους \(|T|=4 \) στο \(\Z \).
\(\Box\)
Στο προηγούμενο παράδειγμα κατασκευάσαμε μια στοχαστική διαδικασία
περιγράφοντας τον δειγματικό χώρο στον οποίο την έχουμε ορίσει και δίνοντας
τον τύπο της, \(\omega\mapsto X_\cdot(\omega)\in\X^T\). Στην θεωρία
των Πιθανοτήτων όμως τα ερωτήματα που μας ενδιαφέρουν δεν αφορούν το
πού και πώς έχουμε ορίσει μια τυχαία μεταβλητή, αλλά τις στατιστικές
της ιδιότητες, δηλαδή το πόσο πιθανό είναι να βρεθεί η τυχαία
μεταβλητή σε διάφορα υποσύνολα του χώρου εντός του οποίου παίρνει τιμές. Αυτή η
πληροφορία δίνεται από την κατανομή της τυχαίας μεταβλητής. Γι' αυτό και
συνήθως, όταν περιγράφουμε μια τυχαία μεταβλητή, δεν κάνουμε αναφορά
στον δειγματικό χώρο \(\Omega\) στον οποίο είναι ορισμένη και στον
τύπο της, αλλά στην κατανομή της. Αυτό θα προσπαθήσουμε να κάνουμε
τώρα και για μια στοχαστική διαδικασία. Θα προσπαθήσουμε δηλαδή να την
περιγράψουμε μέσω των στατιστικών ιδιοτήτων της.
Θα ήταν άραγε αρκετό να περιγράψουμε την κατανομή της
τυχαίας μεταβλητής \(X_t\), για κάθε \(t\in T\)? Το επόμενο παράδειγμα
μας διδάσκει πως η απάντηση είναι αρνητική.
Παράδειγμα 1.2 Έστω ότι έχουμε
ορίσει σε κάποιον χώρο πιθανότητας μια ακολουθία
\(\{Z_k\}_{k\in\N_0}\) από ανεξάρτητες, ισόνομες τυχαίες μεταβλητές
με τυπική κανονική κατανομή. Ορίζουμε τις παρακάτω δύο διαδικασίες
διακριτού χρόνου \(\{X_n\}_{n\in\N_0}\) και \(\{Y_n\}_{n\in\N_0}\).
\[ X_n=\sqrt{n}Z_0,\quad\text{για }n\in\N_0,\qquad\text{και}\qquad
Y_0=0,\ Y_n=\sum_{k=1}^n Z_k, \quad\text{για } n\in\N. \] Εφόσον
\(Z_0\sim{\cal N}(0,1)\), έχουμε \(X_n=\sqrt{n}Z_0\sim{\cal N}(0,n),\)
για κάθε \(n\in\N.\) Επιπλέον, εφόσον οι \(\{Z_k\}_{k\in\N}\) είναι
ανεξάρτητες τυπικές κανονικές, τότε και η \(Y_n\) θα ακολουθεί
κανονική κατανομή για κάθε \(n\in\N\), με μέση τιμή
\(\EE{Y_n}=n\EE{Z_1}=0\) και διασπορά \(V(Y_n)=nV(Z_1)=n\). Έχουμε
επομένως ότι \(Y_n\sim{\cal N}(0,n)\) για κάθε \(n\in\N\). Παρατηρήστε
ότι κάθε χρονική στιγμή \(n\in\N_0\) οι τυχαίες μεταβλητές \(X_n\)
και \(Y_n\) έχουν την ίδια κατανομή. Από την άλλη πλευρά, το Σχήμα 1.1 είναι ενδεικτικό
του πόσο διαφέρουν οι τροχιές των δύο στοχαστικών διαδικασιών για μια
τυπική πραγματοποίησή τους, \(\omega\in\Omega\). Παρατηρήστε ακόμα ότι, αν
ξέρει κανείς την τιμή \(X_1(\omega)\), μπορεί να ανακατασκευάσει όλη
την τροχιά \(X_\cdot(\omega)\). Αντίθετα, οι προσαυξήσεις της
\(\{Y_n\}_n\) μετά τη χρονική στιγμή \(n=1\) είναι ανεξάρτητες της
\(Y_1\).
\(\Box\)
Σχήμα 1.1 Τυπικές τροχιές των διαδικασιών \(\{X_n\}_n\) και
\(\{Y_n\}\) του Παραδείγματος 1.2.
Είδαμε λοιπόν ότι δύο στοχαστικές διαδικασίες,
που κάθε χρονική στιγμή \(t\in T\) έχουν την ίδια κατανομή, μπορεί να
έχουν τροχιές με πολύ διαφορετικά ποιοτικά χαρακτηριστικά. Αυτό
συμβαίνει γιατί, περιγράφοντας μόνο την κατανομή των \(X_t\), για κάθε
\(t\in T\), δεν δίνουμε καμία πληροφορία για τη μεταξύ τους
εξάρτηση. Η πληροφορία για την αλληλεξάρτηση τυχαίων μεταβλητών
βρίσκεται στην από κοινού κατανομή τους (joint distribution). Επομένως,
οποιαδήποτε πλήρης περιγραφή των στατιστικών ιδιοτήτων μιας
στοχαστικής διαδικασίας θα πρέπει να εμπεριέχει την από κοινού
κατανομή των τυχαίων μεταβλητών \(X_{t_1} ,\ X_{t_2}, \ldots,
X_{t_k}\), για κάθε \(k \in \N\) και για κάθε \(k\)-άδα χρόνων \(F=\{t_1,t_2,\ldots,t_k\} \subset T \). Κάθε τέτοια κατανομή είναι ένα
μέτρο πιθανότητας \(\mu_F\) στον \(\X^k\), που ορίζεται μέσω της
Ορισμός: Ονομάζουμε τη συλλογή \(\{\mu_F\}_{F\in {\cal S}(T)}\)
όλων των κατανομών της (1.1), όπου \({\cal
S}(T)\) είναι το σύνολο των πεπερασμένων υποσυνόλων του \(Τ\), οικογένεια των κατανομών
πεπερασμένης διάστασης
της στοχαστικής διαδικασίας \(\{X_t\}_{t\in T}\).
Μπορεί να αποδειχθεί ότι η οικογένεια των κατανομών
πεπερασμένης διάστασης μιας στοχαστικής διαδικασίας \(\{X_t\}_{t\in
T}\) προσδιορίζει πλήρως τις στατιστικές της ιδιότητες. Αυτό είναι
δύσκολο να γίνει αντιληπτό με μαθηματική αυστηρότητα, χωρίς την
ορολογία της Θεωρίας Μέτρου. Για τις ανάγκες αυτού του μαθήματος
είναι αρκετό να θυμόμαστε ότι μπορούμε να περιγράψουμε την κατανομή
μιας στοχαστικής διαδικασίας προσδιορίζοντας όλες τις κατανομές
πεπερασμένης διάστασης. Αν αυτές είναι γνωστές, μπορούμε να
απαντήσουμε οποιοδήποτε πιθανοθεωρητικό ερώτημα που αφορά τη
διαδικασία, χωρίς να χρειάζεται να γνωρίζουμε σε ποιον δειγματικό χώρο
είναι ορισμένη ή ποιος είναι ο τύπος της.
Παράδειγμα 1.3 Θα
χαρακτηρίζουμε μια στοχαστική διαδικασία ως διαδικασία Gauss , αν κάθε
κατανομή πεπερασμένης διάστασης \(\mu_F\) είναι κανονική σε \(|F|\)
διαστάσεις. Εφόσον κάθε πολυδιάστατη κανονική κατανομή προσδιορίζεται
από το διάνυσμα των μέσων τιμών και τον πίνακα συνδιακυμάνσεων, για να
περιγράψουμε μια διαδικασία Gauss \(\{X_t\}_{t\in T}\), αρκεί να
περιγράψουμε τις συναρτήσεις μέσης τιμής και αυτοσυσχέτισης \[ m:
T\to \R, \quad\text{με } m(t)=\EE{X_t}\qquad\text{και
}\qquad\rho:T\times T\to\R, \quad\text{με }\rho(s,t)=\text{Cov
}(X_s,X_t). \] Η τυπική κίνηση Brown είναι μια διαδικασία
Gauss, ορισμένη στο \(T=[0,+\infty)\) με τιμές στο \(\R\) για την
οποία \[ m(t)=0\qquad\text{και}\qquad\rho(s,t)=s\wedge t=\min\{s,t\},
\quad\text{για κάθε }s,t\ge 0. \] Το ότι υπάρχει τέτοια διαδικασία δεν
είναι καθόλου αυτονόητο. Μεσολάβησαν είκοσι τρία χρόνια ανάμεσα στην πρώτη
ευρετική χρήση αυτής της διαδικασίας από τον Bachelier και στη
μαθηματικά αυστηρή κατασκευή της από τον Wiener το 1923.
Για κάθε \(t\ge 0\), η κατανομή της τυχαίας μεταβλητής
\(X_t\) είναι κανονική, αφού η \(X_t\) είναι διαδικασία Gauss .
Επιπλέον, \(\EE{X_t}=m(t)=0\)και \(V(X_t)=\text{Cov
}(X_t,X_t)=\rho(t,t)=t,\) άρα \(X_t\sim{\cal N}(0,t).\) Ειδικότερα
\(X_0=0\).
Ας δούμε τώρα ποια κατανομή ακολουθεί η προσαύξηση
\(X_t-X_s\) της κίνησης Brown σ' ενα διάστημα \((s,t]\). Το ζεύγος
\((X_s,X_t)\) ακολουθεί κανονική κατανομή σε δύο διαστάσεις, αφού η
\(\{X_t\}_{t\ge 0}\) είναι ανέλιξη Gauss . H \(X_t-X_s\) προκύπτει από
τις \(X_s,X_t\) μέσω ενός γραμμικού μετασχηματισμού, άρα ακολουθεί
κανονική κατανομή. Εύκολα βλέπει κανείς ότι \(\EE{X_t-X_s}=m(t)-m(s)=0\), ενώ \[
V(X_t-X_s)=\text{Cov }(X_t-X_s,X_t-X_s)=\text{Cov
}(X_t,X_t)-2\text{Cov }(X_t,X_s)+\text{Cov }(X_s,X_s)=t-2s+s=t-s. \]
Επομένως \(X_t-X_s\sim{\cal N}(0,t-s).\)
Θεωρήστε τώρα \(0\le r< s< t\). Θα δείξουμε ότι οι
προσαυξησεις \(X_t-X_s\) και \(X_s-X_r\) είναι ανεξάρτητες τυχαίες
μεταβλητές. Η από κοινού κατανομή των \((X_r,X_s,X_t)\) είναι
τριδιάστατη κανονική με διάνυσμα μέσων τιμών
\(\big(\EE{X_r},\EE{X_s},\EE{X_t}\big)=(0,0,0)\)και πίνακα
συνδιακυμάνσεων \[ \Sigma(r,s,t)=\left(\begin{array}{ccc}
r&r&r\\r&s&s\\r&s&t\end{array}\right). \] Εφόσον οι
\((X_t-X_s,X_s-X_r)\) προκύπτουν από τις \((X_r,X_s,X_t)\) μέσω ενός
γραμμικού μετασχηματισμού, ακολουθούν κι αυτές κανονική κατανομή (σε
δύο διαστάσεις). Αρκεί λοιπόν να δείξουμε ότι είναι ασυσχέτιστες. \[
\text{Cov }(X_t-X_s,X_s-X_r)=\text{Cov }(X_t,X_s)-\text{Cov
}(X_t,X_r)-\text{Cov }(X_s,X_s)+\text{Cov }(X_s,X_r)=s-r-s+r=0. \] Στο
Σχήμα 1.2 φαίνεται
μια τυπική τροχιά της κίνησης Brown .
\(\Box\)
Σχήμα 1.2 Τυπική τροχιά της κίνησης Brown.
1.3 Διαδικασίες σε διακριτό χρόνο
και χώρο
Στο μεγαλύτερο μέρος αυτών των σημειώσεων θα μελετήσουμε στοχαστικές
διαδικασίες σε διακριτό χρόνο με τιμές σε έναν αριθμήσιμο χώρο
καταστάσεων \(\X\). Σ' αυτή την παράγραφο θα δούμε πώς μπορούμε να
περιγράψουμε εύκολα τις κατανομές πεπερασμένης διάστασης τέτοιων
στοχαστικών διαδικασιών.
Έχοντας επιλέξει \(T=\N_0\), προκειμένου να περιγράψουμε
όλες τις κατανομές πεπερασμένης διάστασης, αρκεί να περιγράψουμε την
από κοινού κατανομή των τυχαίων μεταβλητών \((X_0,X_1,\ldots,X_n)\)
για κάθε \(n\in\N_0\). Πράγματι, για κάθε
\(F=\{n_1,\ldots,n_k\}\subset\N_0\), αν θέσουμε
\(n=\max\{n_1,\ldots,n_k\}\), τότε μπορούμε να πάρουμε την \(\mu_F\),
δηλαδή την από κοινού κατανομή των \((X_{n_1},\ldots,X_{n_k})\), ως
μια κατάλληλη περιθώρια κατανομή της από κοινού κατανομής των
\((X_0,X_1,\ldots,X_n)\).
Επιπλέον, εφόσον ο \(\X\) είναι αριθμήσιμος, o \(\X^k\)
είναι και αυτός αριθμήσιμος για κάθε \(k\in\N\) και επομένως όλες οι
κατανομές πεπερασμένης διάστασης είναι διακριτές κατανομές. Μπορούμε
λοιπόν να τις περιγράψουμε μέσω της συνάρτησης μάζας πιθανότητάς
(σ.μ.π.) τους. Συγκεκριμένα, αν \(F_n=\{0,1,\ldots,n\}\), η σ.μ.π. της
κατανομής \(\mu_{F_n}\) δίνεται, για κάθε
\(\eta=(x_0,\ldots,x_n)\in\X^{n+1}\), από την
Επομένως, στην περίπτωση που έχουμε μια στοχαστική διαδικασία σε
διακριτό χρόνο \(T=\N_0\) με τιμές σ' έναν αριθμήσιμο χώρο καταστάσεων
\(\X\), προκειμένου να περιγράψουμε όλες τις κατανομές πεπερασμένης
διάστασης της διαδικασίας αρκεί να περιγράψουμε την \(Q_n(\eta)\) της
σχέσης (1.2), για κάθε
\(n\in\N_0\) και κάθε \(\eta\in\X^{n+1}\). Σ' αυτό το σημείο ας
θυμηθούμε τον πολλαπλασιαστικό τύπο για τα μέτρα πιθανότητας. Αν
\(A_0,A_1,\ldots,A_k\) είναι ενδεχόμενα ενός δειγματικού χώρου, τότε
Ο πρώτος όρος του δεξιού μέλους μπορεί να
υπολογιστεί από την κατανομή της τυχαίας μεταβλητής \(X_0\). Ο γενικός
όρος του δεξιού μέλος είναι της μορφής
και μπορεί να υπολογιστεί από τη δεσμευμένη κατανομή της τυχαίας
μεταβλητής \(X_k\), δοθέντων των \(X_0,\ldots,X_{k-1}\). Επομένως για
να περιγράψουμε την \(Q_n(\eta)\) της σχέσης (1.2), για κάθε
\(n\in\N_0\) και κάθε \(\eta\in\X^{n+1}\) και άρα για να ορίσουμε ολόκληρη την
οικογένεια κατανομών πεπερασμένης διάστασης της στοχαστικής
διαδικασίας \(\{X_n\}_{n\in\N_0}\), αρκεί να περιγράψουμε
την κατανομή της \(X_0\) και
τη δεσμευμένη κατανομή της \(X_k\), δοθέντων των
\(X_0,\ldots,X_{k-1}\), για κάθε \(k\in\N.\)
Η πρώτη πληροφορία αφορά την αρχική κατάσταση του συστήματος, ενώ η
δεύτερη αφορά τη δυναμική του, δηλαδή τον νόμο που περιγράφει την
εξέλιξη του συστήματος στον χρόνο. Παρατηρήστε την αναλογία με τα
αιτιοκρατικά δυναμικά συστήματα διακριτού χρόνου, τα οποία μπορούμε να
περιγράψουμε δίνοντας την αρχική τους κατάσταση και έναν κανόνα για
το πώς προκύπτει η επόμενη κατάσταση από τις προηγούμενες.
Είδαμε πώς μπορούμε να περιγράψουμε πλήρως τις στατιστικές
ιδιότητες μιας στοχαστικής διαδικασίας διακριτού χρόνου που έχει ήδη
οριστεί σε κάποιον χώρο πιθανότητας. Αρκεί να ξέρουμε την αρχική της
κατανομή και τη δεσμευμένη κατανομή της επόμενης κατάστασης, δοθέντων
των προηγούμενων. Σ' αυτό το σημείο αξίζει να αναρωτηθούμε για το
αντίστροφο ερώτημα. Είναι πάντα δυνατό να βρούμε έναν κατάλληλο χώρο
πιθανότητας και σ' αυτόν να ορίσουμε μια στοχαστική διαδικασία
\(\{X_n\}_{n\in\N_0}\), ώστε αυτή να έχει μια συγκεκριμένη αρχική
κατανομή και έναν συγκεκριμένο νόμο εξέλιξης με την έννοια που
περιγράψαμε παραπάνω? Η απάντηση σ' αυτό το ερώτημα είναι καταφατική
και βασίζεται στο Θεώρημα Συνέπειας του Kolmogorov (Θεώρημα 3.5 στο
[Varadhan01]).
Η απόδειξη όμως αυτού του ισχυρισμού ξεφεύγει από τους σκοπούς του
μαθήματος. Για την ώρα είναι αρκετό να θυμόμαστε ότι το Θεώρημα
Συνέπειας μας εξασφαλίζει πως οι στοχαστικές διαδικασίες που θα
μελετήσουμε είναι υπαρκτά μαθηματικά αντικείμενα.
1.4 Μαρκοβιανές αλυσίδες
Όταν θέλουμε να μοντελοποιήσουμε πραγματικά συστήματα είναι πολύ συνηθισμένο
ο κανόνας που περιγράφει τη δυναμική του συστήματος να εξαρτάται μόνο
από την τρέχουσα κατάσταση του συστήματος και όχι από το πώς το σύστημα
βρέθηκε εκεί.. Τα στοχαστικά συστήματα που έχουν
αυτή την ιδιότητα χαρακτηρίζονται ως μαρκοβιανά. Ο αναγνώστης είναι
πιθανότατα εξοικειωμένος με τέτοια παραδείγματα μιας και τα
περισσότερα επιτραπέζια παιχνίδια αποτελούν μαρκοβιανά συστήματα. Για
παράδειγμα, αν μπείτε σ' ένα δωμάτιο όπου δύο φίλοι σας παίζουν τάβλι,
για να εκτιμήσετε την πιθανότητα νίκης κάθε παίκτη, αρκεί να δείτε την
τρέχουσα διαμόρφωση των πουλιών. Αν ξέρετε αυτή τη διαμόρφωση, η γνώση
του τι προηγήθηκε δεν θα προσφέρει τίποτα στην πρόβλεψή σας για την
εξέλιξη της παρτίδας.
Ορισμός: Μια
στοχαστική διαδικασία \(\{X_n\}_{n\in\N_0}\) λέγεται
μαρκοβιανή αλυσίδα (Markov chain), αν για κάθε \(n\in\N\), η
δεσμευμένη κατανομή της \(X_{n+1}\) δοθέντων των
\((X_0,\ldots,X_n)\), ταυτίζεται με τη δεσμευμένη κατανομή της
\(X_{n+1}\) με μόνη δοθείσα την \(X_n\). Επομένως, η
\(\{X_n\}_{n\in\N_0}\) με τιμές σε έναν αριθμήσιμο χώρο καταστάσεων
\(\X\) είναι μαρκοβιανή αλυσίδα, αν, για κάθε \(n\in\N\) και κάθε
\(v_0,\ldots,v_{n-1},x,y\in\X\), έχουμε
Στις περισσότερες μαρκοβιανές αλυσίδες που παρουσιάζουν ενδιαφέρον, ο
κανόνας \(\PP{X_{n+1}=\cdot\big|X_n=\cdot}\) που περιγράφει την
εξέλιξη της αλυσίδας, δεν εξαρτάται από τη χρονική παράμετρο \(n\).
Λέμε τότε ότι η αλυσίδα είναι
χρονικά ομοιογενής (time homogeneous) και ορίζουμε τις
πιθανότητες μετάβασης (transition probabilities) της αλυσίδας
Επειδή στις σημειώσεις αυτές θα ασχοληθούμε μόνο με χρονικά
ομοιογενείς αλυσίδες, στο εξής θα παραλείπεται η διευκρίνηση για λόγους οικονομίας.
Η συλλογή \(P=\{p(x,y)\}_{x,y\in\X}\) ονομάζεται
πίνακας πιθανοτήτων μετάβασης (transition matrix) της αλυσίδας. Η
ορολογία προέρχεται από την περίπτωση που ο χώρος καταστάσεων \(\X\)
είναι πεπερασμένος, οπότε μπορούμε να περιγράψουμε μία συνάρτηση με
πεδίο ορισμού το \(\X\times\X\) ως ένα τετραγωνικό πίνακα.
Συγκεκριμένα, αν \(\X=\{v_1,\ldots,v_N\}\), έχουμε
Ως σ.μ.π. της τυχαίας μεταβλητής \(X_0\), η
\(\pi_0\) ικανοποιεί τις παρακάτω συνθήκες
\begin{equation} \pi_0(x)\ge 0, \text{ για κάθε }
x\in\X\quad\text{και}\quad \sum_{x\in\X}\pi_0(x)=1. \end{equation}
Αντίστοιχα, εφόσον η \(p(x,\cdot)\) είναι η
δεσμευμένη σ.μ.π. της \(X_{n+1}\) δεδομένου ότι \(X_n=x\), οι
πιθανότητες μετάβασης της μαρκοβιανής αλυσίδας \(\{X_n\}_{n\in\N_0}\)
ικανοποιούν τις συνθήκες
\begin{equation} p(x,y)\ge 0, \text{ για
κάθε } x,y\in\X\quad\text{και}\quad \sum_{y\in\X}p(x,y)=1,\text{ για
κάθε }x\in\X. \end{equation}
Ορισμός Θα λέμε ότι ο
\(P=\{p(x,y)\}_{x,y\in\X}\) είναι στοχαστικός πίνακας (stochastic
matrix), αν τα στοιχεία του ικανοποιούν τις συνθήκες της (1.10).
Σύμφωνα με όσα είδαμε στην παράγραφο 1.3 , η σ.μ.π.
\(\pi_0\) της (1.8)
και ο στοχαστικός πίνακας \(P=\{p(x,y)\}_{x,y\in\X}\) της (1.6) καθορίζουν
πλήρως τις στατιστικές ιδιότητες της μαρκοβιανής αλυσίδας
\(\{X_n\}_{n\in\N_0}\). Πράγματι, οι κατανομές πεπερασμένης διάστασης
της \(\{X_n\}_{n\in\N_0}\) μπορούν να υπολογιστούν με την βοήθεια της
(1.4). Για κάθε
\(n\in\N_0\) και κάθε \((x_0,\ldots,x_n)\in\X^{n+1}\) έχουμε
Στα επόμενα κεφάλαια θα δούμε ότι για να αναλύσουμε τη συμπεριφορά
μιας αλυσίδας αρκεί να γνωρίζουμε αυτές τις ποσότητες. Όπως και στην
περίπτωση των πραγματικών τυχαίων μεταβλητών που η
κατανομή τους μας είναι γνωστή, ο δειγματικός χώρος \(\Omega\) στον οποίο έχει οριστεί η
αλυσίδα και ο τύπος της απεικόνισης \(\omega\mapsto X_\cdot(\omega)\)
δεν θα παίξουν κανένα ρόλο.
Θα δούμε στα παραδείγματα που ακολουθούν ότι, στη
μοντελοποίηση πραγματικών συστημάτων από μαρκοβιανές αλυσίδες, συνήθως
το πρόβλημα υποδεικνύει την αρχική κατανομή \(\pi_0\) και τον πίνακα
πιθανοτήτων μετάβασης \(P\) που θέλουμε να έχει η αλυσίδα η οποία
περιγράφει το σύστημα. Το Θεώρημα Συνέπειας του Kolmogorov μας
εξασφαλίζει ότι, για κάθε σ.μ.π. \(\pi_0\) και για κάθε στοχαστικό
πίνακα \(P\), μπορούμε να κατασκευάσουμε μια μαρκοβιανή αλυσίδα
\(\{X_n\}_{n\in\N_0}\), η οποία έχει την \(\pi_0\) ως αρχική κατανομή
και τον \(P\) ως πίνακα πιθανοτήτων μετάβασης. Οι λεπτομέρειες αυτής
της κατασκευής είναι αδιάφορες για την ανάλυση του μοντέλου, αφού η
\(\pi_0\) και ο \(P\), όπως είπαμε, καθορίζουν τις στατιστικές
ιδιότητες της αλυσίδας.
Παράδειγμα 1.4 Ένα έντομο
κινείται στις κορυφές του διπλανού γράφου. Ξεκινά από την κορυφή
\(A\). Σε κάθε βήμα, αν βρίσκεται στην κορυφή \(x\), επιλέγει τυχαία
μία από τις κορυφές που συνδέονται με την \(x\) μέσω μιας ακμής του
γράφου και μεταβαίνει εκεί.
Μπορούμε να περιγράψουμε την κίνηση του εντόμου
ως μια μαρκοβιανή αλυσίδα στον χώρο καταστάσεων \(\X=\{A,B,C,D,E\}\).
Εφόσον η αλυσίδα ξεκινά από την κορυφή \(A\), η αρχική κατανομή της
έχει σ.μ.π. \[ \pi_0(x)=\PP{X_0=x}=\delta_A(x)=\begin{cases} 1, &
\text{αν } x=A\\ 0, & \text{αν } x\neq A.\end{cases} \] Μπορούμε να
περιγράψουμε την αρχική κατανομή και ως ένα διάνυσμα γραμμή \[
\pi_0=\big(\pi_0(A),\pi_0(B),\pi_0(C),\pi_0(D),\pi_0(E)\big)=(1,0,0,0,0).
\] O πίνακας πιθανοτήτων μετάβασης \(P\) της αλυσίδας είναι ο \[
P=\left(\begin{array}{ccccc}
0&1/2&0&0&1/2\\1/4&0&1/4&1/4&1/4\\0&1/2&0&1/2&0\\0&1/3&1/3&0&1/3\\
1/3&1/3&0&1/3&0\end{array}\right). \] Κάθε του γραμμή περιγράφει τις
μεταβάσεις από μια κορυφή. Ας δούμε για παράδειγμα πώς προκύπτει η
πρώτη γραμμή του \(P\), που περιγράφει τις μεταβάσεις από την κορυφή
\(Α\). Από την \(A\) μπορούμε να πάμε στις κορυφές \(B\) ή \(Ε\) με
πιθανότητα 1/2 σε κάθε μία. Άρα η πρώτη γραμμή του \(P\) είναι \[
\big(p(A,A),\, p(A,B),\, p(A,C),\, p(A,D),\, p(A,E)\big)=(0,1/2,0,0,{1}/{2}). \]
Παράδειγμα 1.5 Κάνουμε έναν
τυχαίο περίπατο στους ακεραίους ξεκινώντας από το 0. Σε κάθε μας βήμα
στρίβουμε ένα κέρμα που έχει πιθανότητα \(p\in(0,1)\) να φέρει κεφαλή
κάθε φορά που το στρίβουμε, ανεξάρτητα από τις άλλες φορές. Αν το
αποτέλεσμα είναι κεφαλή, μετατοπιζόμαστε μία θέση δεξιά. Αν το
αποτέλεσμα είναι γράμματα, μετατοπιζόμαστε μία θέση αριστερά. Μπορούμε
να περιγράψουμε αυτόν τον περίπατο ως μια μαρκοβιανή αλυσίδα στον
χώρο καταστάσεων \(\Z\). Εφόσον ξεκινάμε από το 0, η αρχική κατανομή
έχει σ.μ.π. \[ \pi_0(x)=\PP{X_0=x}=\delta_0(x)=\begin{cases} 1, &
\text{αν } x=0\\ 0, & \text{αν } x\neq 0.\end{cases} \] Οι πιθανότητες
μετάβασης της αλυσίδας δίνονται από την \[
p(x,y)=\PP{X_{n+1}=y\big|X_n=x}=\begin{cases}p,&\text{αν
}y=x+1\\1-p,&\text{αν }y=x-1\\0,&\text{αν } |y-x|\neq 1.\end{cases},\quad
x,y\in\Z. \]
Παράδειγμα 1.6 Στρίβουμε ένα
τίμιο κέρμα μέχρι να εμφανιστεί για πρώτη φορά η ακολουθία
αποτελεσμάτων ΚΓΚ. Μια πρώτη σκέψη θα ήταν να περιγράψουμε αυτό το
πείραμα ως μια μαρκοβιανή αλυσίδα, που η κατάστασή της είναι το
αποτέλεσμα των τριών τελευταίων στριψιμάτων. Με αυτή την επιλογή ο
χώρος καταστάσεων θα ήταν ο \(\X_1=\{K,\Gamma\}^3\). Η αρχική κατανομή
της αλυσίδας θα προκύψει από το αποτέλεσμα των τριών πρώτων
στριψιμάτων. Εφόσον το κέρμα είναι τίμιο, θα πρέπει να πάρουμε σαν
σ.μ.π. της \(X_0\) την \(\pi_0(x)=1/8\), για κάθε \(x\in\X_1\). Είναι
εύκολο να περιγράψουμε και τις πιθανότητες μετάβασης της αλυσίδας. Για
παράδειγμα, από την κατάσταση ΚΓΓ η αλυσίδα μπορεί να μεταβεί είτε
στην ΓΓΚ με πιθανότητα 1/2 (αν φέρουμε κορώνα) είτε στην ΓΓΓ με
πιθανότητα 1/2 (αν φέρουμε γράμματα). Επειδή το πείραμα τελειώνει όταν
η αλυσίδα φτάσει στην ΚΓΚ, μπορούμε να θεωρήσουμε ότι από την ΚΓΚ
παραμένουμε στην ίδια κατάσταση με πιθανότητα 1. Μπορείτε να
συμπληρώσετε τον πίνακα πιθανοτήτων μετάβασης για εξάσκηση.
Μπορούμε όμως να περιγράψουμε το πείραμα και πιο οικονομικά,
θεωρώντας σαν καταστάση της αλυσίδας που το περιγράφει το αποτέλεσμα
των δύο τελευταίων στριψιμάτων και προσθέτοντας μια κατάσταση στην
οποία η αλυσίδα θα μεταβαίνει, όταν το πείραμα τελειώσει. Με αυτή την
επιλογή ο χώρος καταστάσεων της αλυσίδας είναι ο
\(\X=\{KK,K\Gamma,\Gamma K,\Gamma\Gamma,T\}\), όπου η κατάσταση \(T\)
κωδικοποιεί το τέλος του πειράματος. Η αρχική κατανομή της αλυσίδας θα
προκύψει τώρα από το αποτέλεσμα των δύο πρώτων στριψιμάτων. Εφόσον το
κέρμα είναι τίμιο, η αλυσίδα αρχικά θα βρεθεί σε μία από τις ΚΚ, ΚΓ, ΓΚ
ή ΓΓ με πιθανότητα 1/4 στην κάθε μία. Μπορούμε λοιπόν να περιγράψουμε
την αρχική κατανομή της αλυσίδας ως ένα διάνυσμα γραμμή \[
\pi_0=\big(\pi_0(KK),\, \pi_0(K\Gamma),\, \pi_0(\Gamma
K),\, \pi_0(\Gamma\Gamma),\, \pi_0(T)\big)=(1/4,\, 1/4,\, 1/4,\, 1/4,\, 0). \] Ο πίνακας
πιθανοτήτων μετάβασης της αλυσίδας είναι ο \[
P=\left(\begin{array}{ccccc}
1/2&1/2&0&0&0\\0&0&0&1/2&1/2\\1/2&1/2&0&0&0\\0&0&1/2&1/2&0\\
0&0&0&0&1\end{array}\right). \]
Παράδειγμα 1.7 Το επιτραπέζιο
παιχνίδι φιδάκι ανάμεσα σε δύο παίκτες μπορεί να περιγραφεί
ως μια μαρκοβιανή αλυσίδα στον χώρο καταστάσεων \[
\X=\{1,2,\ldots,100\}\times\{1,2,\ldots,100\}\times\{A,B\}. \] Το
παιχνίδι βρίσκεται στην κατάσταση \((m,n,b)\), αν το πιόνι του παίκτη
\(A\) βρίσκεται στο τετράγωνο \(m\), το πιόνι του παίκτη \(B\)
βρίσκεται στο τετράγωνο \(n\) και είναι η σειρά του παίκτη \(b\) να
ρίξει το ζάρι. Η αρχική κατανομή της αλυσίδας, αν ο παίκτης \(A\)
παίζει πρώτος, είναι η \(\pi_0(x)=\delta_{(1,1,A)}(x)\). Θα ήταν
κοπιώδες να περιγράψουμε τον πίνακα πιθανοτήτων μετάβασης αυτής της
αλυσίδας σαν ένα τετραγωνικό \(20.000\times 20.000\) πίνακα, αλλά οι
πιθανότητες μετάβασης μπορούν να περιγραφούν σαφώς. Για παράδειγμα
\(p\big((1,1,A),(3,1,B)\big)=1/6\), αφού το παιχνίδι θα μεταβεί από
την κατάσταση \((1,1,Α)\) στην κατάσταση \((3,1,Β)\), αν η ζαριά του
παίκτη \(A\) είναι 2.
Παράδειγμα 1.8 Ένας
μπασκετμπολίστας προπονείται στις ελεύθερες βολές. Κάθε φορά που
εκτελεί μια βολή, η πιθανότητα να ευστοχήσει είναι 8/10, αν έχει
ευστοχήσει και στις δύο προηγούμενες προσπάθειές του, 5/10, αν έχει
αστοχήσει και στις δύο προηγούμενες προσπάθειες και 7/10 σε κάθε άλλη περίπτωση.
Ορίζουμε τη στοχαστική διαδικασία \(\{X_n\}_{n\in\N}\), όπου
\(X_n=1\), αν η \(n\)-οστή του προσπάθεια είναι εύστοχη και
\(X_n=0\), αν η \(n\)-οστή του προσπάθεια είναι άστοχη. Είναι η
\(\{X_n\}_{n\in\N}\) μαρκοβιανή αλυσίδα?
Διαισθητικά περιμένει κανείς ότι η απάντηση είναι αρνητική.
Η τιμή της \(X_n\) έχει την πληροφορία μόνο για το αποτέλεσμα της
τελευταίας βολής, ενώ η πιθανότητα ευστοχίας στην επόμενη
προσπάθεια εξαρτάται από το αποτέλεσμα των δύο τελευταίων βολών. Για
να αποδείξουμε αυστηρά ότι η \(\{X_n\}_{n\in\N}\) δεν είναι μαρκοβιανή,
αρκεί να παρατηρήσουμε ότι \[ \PP{X_{n+1}=1\big|
X_{n-1}=X_n=1}=8/10\neq 7/10=\PP{X_{n+1}=1\big| X_{n-1}=0, X_n=1}. \]
Αν όμως η \(\{X_n\}_{n\in\N}\) ήταν μαρκοβιανή, οι δύο πιθανότητες
στην παραπάνω σχέση θα ήταν ίσες, αφού και οι δύο θα συνέπιπταν με την
\(\PP{X_{n+1}=1\big|X_n=1}\).
Το πρόβλημα εδώ είναι ότι ο χώρος καταστάσεων της αλυσίδας
\(\X=\{0,1\}\) είναι πολύ μικρός για να κωδικοποιήσει την πληροφορία
που χρειαζόμαστε για να περιγράψουμε την κατανομή της επόμενης
κατάστασης. Μπορούμε όμως, μεγαλώνοντας τον χώρο καταστάσεων, να
περιγράψουμε την προπόνηση του αθλητή ως μια μαρκοβιανή αλυσίδα.
Αν για παράδειγμα ορίσουμε τη στοχαστική διαδικασία
\(\{Y_n\}_{n\in\N}\), με \(Y_n=(X_n,X_{n+1})\), αυτή είναι μια
μαρκοβιανή αλυσίδα στον χώρο καταστάσεων
\(\X'=\{(0,0),(0,1),(1,0),(1,1)\}\) με πίνακα πιθανοτήτων μετάβασης
\[ P=\left(\begin{array}{cccc}
1/2&1/2&0&0\\0&0&3/10&7/10\\3/10&7/10&0&0\\0&0&2/10&8/10\end{array}\right).\qquad\qquad\qquad\Box
\]
Συνηθίζουμε να λέμε ότι για μια μαρκοβιανή αλυσίδα παρελθόν και
μέλλον είναι ανεξάρτητα, με δεδομένο το παρόν. Η μαρκοβιανή
ιδιότητα (Markov property) είναι η μαθηματική διατύπωση αυτής της
έκφρασης.
Θεώρημα 1.1 (μαρκοβιανή
ιδιότητα) Έστω \(\{X_n\}_{n\in\N_0}\) μαρκοβιανή αλυσίδα σε ένα
αριθμήσιμο χώρο καταστάσεων \(\X\) με πίνακα πιθανοτήτων μετάβασης
\(P\). Για \(k\in\N_0\), ορίζουμε τη στοχαστική διαδικασία
\(\{Y_n\}_{n\in\N_0}\) με τύπο \(Y_n=X_{n+k}\). Δεδομένου ότι
\(X_k=x\in\X\), η διαδικασία \(\{Y_n\}_{n\in\N_0}\) είναι μαρκοβιανή
αλυσίδα στον \(\X\), με αρχική κατανομή \(\delta_x\), πίνακα
πιθανοτήτων μετάβασης \(P\) και είναι ανεξάρτητη από τις
\(X_0,X_1,\ldots,X_k.\)
Απόδειξη: Αρκεί να δείξουμε ότι, δεδομένου ότι \(X_k=x\),
για κάθε \(n\in\N\) οι \((Y_0,Y_1,\ldots,Y_n)\) είναι ανεξάρτητες από
τις \(X_0,X_1,\ldots,X_k\) και η από κοινού τους κατανομή δίνεται από
την (1.11) με
αρχική κατανομή \(\delta_x\). Αρκεί επομένως να δείξουμε ότι, για κάθε
\(y=(y_0,\ldots,y_n)\in\X^{n+1}\) και κάθε
\(z=(z_0,\ldots,z_k)\in\X^{k+1}\) \[ \PP{\{(Y_0,\ldots,Y_n)=y\}\cap
A(z)\big|X_k=x}=\delta_x(y_0)p(y_0,y_1)\cdots
p(y_{n-1},y_n)\PP{A(z)\big|X_k=x}, \] όπου
\(A(z)=\{(X_0,\ldots,X_k)=z\}.\) Πράγματι όμως, \begin{align*}
\PP{\{(Y_0,\ldots,Y_n)=y\}\cap
A(z)&\big|X_k=x}=\delta_x(y_0)\delta_x(z_k)\frac{\PP{X_0=z_0,\ldots,X_k=x,X_{k+1}=y_1,\ldots,X_{n+k}=y_n}}{\PP{X_k=x}}\\
&=\frac{\delta_x(z_k)\pi_0(z_0)p(z_0,z_1)\cdots
p(z_{k-1},x)}{\PP{X_k=x}}\delta_x(y_0)p(x,y_1)\cdots p(y_{n-1},y_n)\\
&=\PP{A(z)\big|X_k=x}\delta_x(y_0)p(y_0,y_1)\cdots
p(y_{n-1},y_n).\qquad\qquad\Box \end{align*} Βλέπουμε λοιπόν ότι, αν
γνωρίζουμε την παρούσα θέση της αλυσίδας, δεδομένου δηλαδή ότι
\(X_k=x\), τότε το μέλλον της αλυσίδας, το οποίο εκφράζεται από την αλυσίδα \(\{Y_n\}_{n\in\N_0}\),
είναι ανεξάρτητο του παρελθόντος της, δηλαδή των τυχαίων μεταβλητών
\(X_0,\ldots,X_{k}\) και έχει μάλιστα τις ίδιες στατιστικές
ιδιότητες όπως μια αλυσίδα που ξεκινά από το \(x\) με τις ίδιες
πιθανότητες μετάβασης, \(P\).
\(\Box\)
Όταν η αλυσίδα \(\{X_n\}_{n\in\N_0}\) ξεκινά από την
κατάσταση \(x\in\X\), θα χρησιμοποιούμε τον συμβολισμό
\(\P_x\big[A\big]\) για την πιθανότητα ενός ενδεχομένου \(Α\) που
εξαρτάται από την τροχιά της αλυσίδας. Για παράδειγμα, αν
\(v=(v_0,\ldots,v_n)\in\X^{n+1}\), έχουμε \[
\P_x\big[(X_0,\ldots,X_n)=v\big]=\delta_x(v_0)p(v_0,v_1)\cdots
p(v_{n-1},v_n). \] Χρησιμοποιώντας τη μαρκοβιανή ιδιότητα για \(k=0\), έχουμε ότι
\(\PP{\cdot\big|X_0=x}=\P_x\big[\cdot\big].\)
1.5 Ασκήσεις
Άσκηση 1.1 Θεωρήστε δύο
ανεξάρτητες τυχαίες μεταβλητές \(A\),\(\Theta\) και ορίστε την
στοχαστική διαδικασία \(\{X_t\}_{t\ge 0}\) με τύπο \[
X_t=A\sin(\omega t+\Theta), \] όπου \(\omega\in\R.\) Αν η \(Α\)
ακολουθεί εκθετική κατανομή με ρυθμό \(\lambda=1\) και η \(\Theta\)
ακολουθεί ομοιόμορφη κατανομή στο \([0,2\pi]\), υπολογίστε τις \(\EE{X_t}\)
και \(\EE{X_tX_s}\), για κάθε \(s,t\ge 0\).
Άσκηση 1.2 Αν \(\{X_t\}_{t\ge
0}\) είναι η στοχαστική διαδικασία του Παραδείγματος 1.3 , ορίζουμε \[
Y_t=e^{-t}X_{e^{2t}}. \] Δείξτε ότι η \(\{Y_t\}_{t\ge 0}\) είναι
διαδικασία Gauss , με \(m(t)=\EE{Y_t}=0\) και \(\rho(s,t)=\text{Cov
}(Y_t,Y_s)=e^{-|t-s|}.\)
Άσκηση 1.3 Θεωρήστε μια
διαδικασία Gauss \(\{X_t\}_{t\ge 0}\), με \(m(t)=\E\big[X_t\big]=0\),
για κάθε \(t\ge 0\) και \[ \rho(s,t)=\text{Cov
}\big(X_t,X_s)=\frac{1}{2}\big(t^{2H}+s^{2H}-|t-s|^{2H}\big),\quad
s,t\ge 0, \] για κάποιο \(H\in(0,1)\). α) Δείξτε ότι για κάθε
\(t\ge 0\) έχουμε \(X_t\sim{\cal N}\big(0,t^{2H}\big)\). β)
Υπολογίστε για \(t\ge 0\) και \(h>0\) τη μέση τιμή και τη διασπορά της
προσαύξησης \(X_{t+h}-X_t\) και δείξτε ότι η \(X_{t+h}-X_t\)
ακολουθεί την ίδια κατανομή με την \(X_h\). γ) Δείξτε ότι για
κάθε \(t,h>0\), η \(X_{t+h}-X_t\) είναι ανεξάρτητη από την \(X_t\), αν
και μόνο αν \(H=1/2\). δ) Ποια γνωστή μας στοχαστική
διαδικασία είναι η \(\{X_t\}_{t\ge 0}\) όταν \(H=1/2\)? ε)
Ορίζουμε για κάθε \(t\ge 0:\ Y_t=\alpha^{-H}X_{\alpha t}\), όπου
\(\alpha\) θετικός πραγματικός αριθμός. Δείξτε ότι
\(\E\big[Y_t\big]=\E\big[X_t\big]\), για κάθε \(t\ge 0\) και
\(\text{Cov }\big(Y_t,Y_s)=\text{Cov }\big(X_t,X_s)\), για κάθε
\(s,t\ge 0.\) Πώς ερμηνεύετε αυτό το αποτέλεσμα?
Άσκηση 1.4 α) Αντικαταστήστε
τα σύμβολα * με αριθμούς, ώστε ο πίνακας \[
P=\left(\begin{array}{ccccc} 0&3/4&*&0&0\\ 3/4&0&0&1/8&*\\
1/2&1/4&1/4&*&*\\ *&3/5&1/5&1/5&*\\ 0&0&1/10&1/5&* \end{array}\right)
\] να είναι πίνακας πιθανοτήτων μετάβασης μιας μαρκοβιανής αλυσίδας
\(\{X_n\}_{n\in\N_0}\) στον χώρο καταστάσεων \(\X=\{1,2,\ldots,7\}\)
με πιθανότητες μετάβασης \(p(i,j)\) για κάθε \(i,j\in\X\).
Άσκηση 1.5 Στο διπλανό σχήμα
φαίνεται η κάτοψη ενός σπιτιού με πέντε δωμάτια: κουζίνα (Κ), βιβλιοθήκη
(Β), σαλόνι (Σ), υπνοδωμάτιο (Υ) και μπάνιο (Μ), καθώς και οι πόρτες που τα
συνδέουν. Ένα έντομο που ζει στο σπίτι κάθε βράδυ διασχίζει τυχαία
μία από τις πόρτες του δωματίου στο οποίο βρίσκεται και παραμένει στο
δωμάτιο που οδηγεί η πόρτα μέχρι το επόμενο βράδυ. Αρχικά το έντομο
βρίσκεται στο μπάνιο. Αν \(\{X_n\}_{n\in\N_0}\) είναι η μαρκοβιανή
αλυσίδα στον χώρο καταστάσεων \(\X=\)\(\{\)Κ, Β, Σ, Υ, Μ\(\}\), που
περιγράφει τη θέση του εντόμου μετά από \(n\) βράδυα, βρείτε τον
πίνακα πιθανοτήτων μετάβασής της.
Άσκηση 1.6 Έχουμε πέντε χαρτιά της
τράπουλας, τα τέσσερα είναι επτά κούπα και το ένα ρήγας σπαθί. Τα
απλώνουμε στη σειρά σε ένα τραπέζι και σε κάθε βήμα επιλέγουμε ένα από
τα δύο ακραία χαρτιά (το αριστερότερο με πιθανότητα 2/3, το δεξιότερο
με πιθανότητα 1/3) και το τοποθετούμε στη μέση. Κατασκευάστε έναν
κατάλληλο χώρο καταστάσεων και τις αντίστοιχες πιθανότητες μετάβασης
μιας μαρκοβιανής αλυσίδας που θα περιέγραφε την θέση του ρήγα.
Άσκηση 1.7 Ρίχνουμε ένα ζάρι
μέχρι να φέρουμε πέντε συνεχόμενες φορές έξι. Περιγράψτε μια μαρκοβιανή
αλυσίδα στον χώρο καταστάσεων \(\X=\{0,1,2,3,4,5\}\) που θα
μοντελοποιούσε αυτό το παιχνίδι. Κάντε το ίδιο για την περίπτωση στην οποία ρίχνουμε το ζάρι
μέχρι να εμφανιστεί η ακολουθία 65656.
Άσκηση 1.8 Επαναλαμβάνουμε
ρίψεις ενός ζαριού και για \(n\in\N\) συμβολίζουμε με \(S_n\) το
άθροισμα των \(n\) πρώτων ζαριών μας. Αν \(X_n=S_n(\text{mod }5)\),
δείξτε ότι η \(\{X_n\}_{n\in\N}\) είναι μια μαρκοβιανή αλυσίδα και
βρείτε τον πίνακα πιθανοτήτων μετάβασής της.
Άσκηση 1.9 Αυτή η άσκηση μας
διδάσκει πώς να προσομοιώσουμε μια κατανομή στον \(\X\) με τη
βοήθεια μιας γεννήτριας τυχαίων αριθμών. Έστω
\(\X=\{v_1,v_2,\ldots\}\) ένας αριθμήσιμος χώρος καταστάσεων. Για μια
σ.μ.π. \(\{p_i\}_{i\in\N}\) στον \(\X\) ορίζουμε τη συνάρτηση \[
\Phi_p: (0,1]\to \X,\qquad \Phi_p(x)=v_k, \quad\text{ αν }
\sum_{j=1}^{k-1} p_i < x \le \sum_{j=1}^{k} p_i . \] Δείξτε ότι, αν η
τυχαία μεταβλητή \(U\) έχει ομοιόμορφη κατανομή στο [0,1], τότε η
\(\Phi_p(U)\) έχει σ.μ.π. \(\{p_i\}_{i\in\N}\).
Άσκηση 1.10 Θεωρήστε έναν
αριθμήσιμο χώρο \(\X\) και μια συνάρτηση \(\Phi: \X\times
[0,1]\to\X\). Αν \(\{U_n\}_{n\in\N}\) είναι μια ακολουθία από
ανεξάρτητες, ισόνομες τυχαίες μεταβλητές, με ομοιόμορφη κατανομή στο
[0,1] και ορίσουμε αναδρομικά τη στοχαστική διαδικασία
\(\{X_n\}_{n\in\N_0}\) ως \[ X_0=x\in\X,\qquad X_{n}=\Phi(X_{n-1},U_n),
\text{ για } n\in\N, \] τότε η \(\{X_n\}_{n\in\N_0}\) είναι μαρκοβιανή
αλυσίδα. Ποιες είναι οι πιθανότητες μετάβασης αυτής της αλυσίδας? Με
τη βοήθεια και της προηγούμενης άσκησης, εξηγήστε πώς μπορούμε να
προσομοιώσουμε μια μαρκοβιανή αλυσίδα με δεδομένες πιθανότητες
μετάβασης.
Άσκηση 1.11 Σ' ένα ράφι της
βιβλιοθήκης σας υπάρχουν τρία βιβλία: Algebra, Basic Topology,
Calculus , που θα συμβολίζουμε με A,B,C για συντομία. Κάθε πρωί
παίρνετε τυχαία ένα βιβλίο από τη θέση του με πιθανότητες \(p,q,r\),
αντίστοιχα. Όταν τελειώνετε το διάβασμά σας για την ημέρα, το
ξαναβάζετε στο ράφι στην αριστερότερη θέση. Η διάταξη των βιβλίων
είναι μια μαρκοβιανή αλυσίδα στον χώρο \(\X\) των μεταθέσεων των
συμβόλων \(\{A,B,C\}\). Ποιος είναι ο πίνακας πιθανοτήτων μετάβασης
αυτής της αλυσίδας?
Άσκηση 1.12 Στο μοντέλο
διάχυσης του Ehrenfest , \(Ν\) σωματίδια τοποθετούνται σε ένα δοχείο
με δύο διαμερίσματα, Α και Β. Σε κάθε βήμα επιλέγουμε τυχαία ένα από
τα \(N\) σωματίδια και του αλλάζουμε διαμέρισμα. Έστω
\(\{X_n\}_{n\in\N_0}\) η μαρκοβιανή αλυσίδα στον χώρο καταστάσεων
\(\X=\{0,1,\ldots,N\}\) που περιγράφει το πλήθος των σωματιδίων στο
διαμέρισμα Α μετά από \(n\) βήματα. Ποιες είναι οι πιθανότητες
μετάβασης της \(\{X_n\}_n\)?
Άσκηση 1.13 Ένας παντοπώλης
εφοδιάζεται κάθε πρωί με ένα πακέτο μπισκότα Alfajor . Η ημερήσια
ζήτηση για τα μπισκότα αυτά είναι μια τυχαία μεταβλητή που ακολουθεί
γεωμετρική κατανομή με παράμετρο \(p=1\). Αν χθες βράδυ δεν είχαν
μείνει καθόλου μπισκότα Alfajor και \(\{X_n\}_{n\in\N}\) είναι το
πλήθος των πακέτων που υπάρχει στο παντοπωλείο το βράδυ της
\(n\)-οστής ημέρας, δείξτε ότι η \(\{X_n\}_{n\in\N}\) είναι μαρκοβιανή
αλυσίδα και βρείτε τις πιθανότητες μετάβασής της.
Άσκηση 1.14 Θεωρήστε δύο
ακολουθίες \(\{X_n,Y_n\}_{0\le n\le N-1}\) από ανεξάρτητα, τυχαία,
δεκαδικά ψηφία. Σχηματίστε τους ακεραίους \[ X=X_0+X_1\times
10+\cdots+X_{N-1}\times 10^{N-1}\qquad Y=Y_0+Y_1\times
10+\cdots+Y_{N-1}\times 10^{N-1} \] και προσθέστε τους, όπως μάθαμε
στο δημοτικό, ξεκινώντας από τα ψηφία των μονάδων \(X_0,Y_0\),
συνεχίζοντας με τα ψηφία των δεκάδων \(X_1,Y_1\) κ.λπ.,
μεταφέροντας το κρατούμενο, όπου χρειάζεται. Αν \(C_n\in\{0,1\}\)
είναι το κρατούμενο της πρόσθεσης που μεταφέρουμε στο \(n\)-οστό βήμα,
δείξτε ότι η \(\{C_n\}_{0\le n\le N-1}\) είναι μια μαρκοβιανή αλυσίδα
στον χώρο καταστάσεων \(\X=\{0,1\}\) και βρείτε τον πίνακα
πιθανοτήτων μετάβασης της αλυσίδας.
1.6 Αριθμητικά πειράματα
Άσκηση 1.15 Κατεβάστε και
εγκαταστήστε τη γλώσσα Python 2.7.7 . Μπορείτε να βρείτε τα σχετικά
αρχεία εδώ. Ανάλογα με το λειτουργικό σύστημα του Η/Υ
σας, μπορείτε να βρείτε και ολοκληρωμένα πακέτα. Αν ο υπολογιστής σας
δεν τρέχει το λειτουργικό σύστημα Linux , πιθανά να βρείτε χρήσιμο να
εγκαταστήσετε έναν εξομοιωτή, σύμφωνα με τις οδηγίες που θα βρείτε
αρχείο εδώ.
Άσκηση 1.16 Κατεβάστε το
πρόγραμμα
simple_markov_chain_lib.py
και αποθηκεύστε το στον κατάλογο που θα
δουλέψετε. Σ' αυτή την φάση δεν χρειάζεται καν να το ανοίξετε. Το
πρόγραμμα αυτό υλοποιεί τον αλγόριθμο της Άσκησης 1.10 . Θα το
χρησιμοποιούμε σαν βιβλιοθήκη στα επόμενα προγράμματα που θα
φτιάξουμε.
Άσκηση 1.17 Κατεβάστε και
τρέξτε το πρόγραμμα
test.py . Το πρόγραμμα αυτό προσομοιώνει τα πρώτα δέκα βήματα μιας
αλυσίδας που κινείται στον χώρο καταστάσεων \(\X=\{1,2,3,4,5\}\) με
πίνακα πιθανοτήτων μετάβασης \[ P=\left(\begin{array}{ccccc}
0&1/2&1/2&0&0\\1/3&0&0&2/3&0\\0&0&1&0&0\\1/2&0&0&1/2&0\\0&0&0&0&1\end{array}\right)
\] ξεκινώντας από την κατάσταση 1. Τρέξτε το πρόγραμμα μερικές φορές
και στη συνέχεια φτιάξτε ένα πρόγραμμα που προσομοιώνει τα είκοσι
πρώτα βήματα της Άσκησης 1.11
.
