Στο κεφάλαιο αυτό θα μελετήσουμε την ασυμπτωτική συμπεριφορά μαρκοβιανών αλυσίδων, το πώς δηλαδή αυτές συμπεριφέρονται σε βάθος χρόνου. Η κατανόηση της ασυμπτωτικής συμπεριφοράς τους είναι σημαντική για δύο κυρίως λόγους. Αφενός, υπάρχουν συστήματα που μοντελοποιούνται από μαρκοβιανές αλυσίδες και τα οποία, αφού περάσουν μια παροδική φάση, τελικά λειτουργούν σε μια κατάσταση ισορροπίας. Αφετέρου, αν θέλουμε να χρησιμοποιήσουμε ιδέες από τις μαρκοβιανές αλυσίδες για να φτιάξουμε υπολογιστικούς αλγορίθμους, είναι σημαντικό να ξέρουμε τη συμπεριφορά του αλγορίθμου μετά από πολλές επαναλήψεις, να μπορούμε να εκτιμήσουμε πόσο γρήγορα συκλίνει και πώς εξαρτάται το σφάλμα της προσέγγισης από το πλήθος των επαναλήψεων που θα εκτελέσουμε. Παρόμοιο υλικό μπορείτε να βρείτε στις αναφορές [Norris98] και [Levin09] .
Ας θεωρήσουμε μια αλυσίδα που κινείται στις κορυφές ενός τετραγώνου ΑΒΓΔ. Ξεκινώντας από την κορυφή Α, σε κάθε βήμα μεταβαίνει σε μία από τις δύο γειτονικές της κορυφές με πιθανότητα 1/2. Εύκολα βλέπει κανείς ότι η μοναδική αναλλοίωτη κατανομή αυτής της αλυσίδας είναι η ομοιόμορφη κατανομή \(\pi=(1/4,1/4,1/4,1/4)\) και όπως είδαμε στο προηγούμενο κεφάλαιο αυτό είναι μόνο υποψήφιο όριο της κατανομής \(\pi_n\) της αλυσίδας μετά από \(n\) βήματα. Δεν είναι δύσκολο να δει κανείς όμως ότι \(\pi_n\not\rightarrow\pi\). Πράγματι, εφόσον η αλυσίδα ξεκινά από το Α, θα βρίσκεται οπωσδήποτε στο B ή στο Δ μετά από περιττό αριθμό βημάτων και στο Α ή στο Γ μετά από άρτιο αριθμό βημάτων. Έτσι, π.χ.
\[ \pi_{2n+1}(A)=\PP{X_{2n+1}=A\,|\,X_0=A}=0\not\rightarrow 1/4. \]
Βλέπουμε λοιπόν ότι στο παράδειγμά μας υπάρχουν υποσύνολα του χώρου
καταστάσεων που είναι προσβάσιμα μόνο σε συγκεκριμένες χρονικές
στιγμές. Αυτή η ιδιότητα αποτελεί κατά κάποιον τρόπο μια παθολογία που
εμποδίζει τη σύγκλιση της κατανομής της αλυσίδας \(\pi_n\), και σε
αυτή την παράγραφο θα προσπαθήσουμε να την κατανοήσουμε.
Ορισμός: Για μια κατάσταση
\(x\in\X\) ορίζουμε το σύνολο των δυνατών χρόνων επιστροφής στο \(x\)
Θα ονομάζουμε τον μέγιστο κοινό
διαιρέτη του συνόλου \(R(x)\)
περίοδο της κατάστασης \(x\) και θα τον συμβολίζουμε με
\(d(x)\). Στην ειδική περίπτωση που \(d(x)=1\), θα λέμε ότι η κατάσταση
\(x\) είναι απεριοδική.
Παρατηρήστε ότι, για κάθε \(x\in\X\), το σύνολο \(R(x)\) είναι ένα υποσύνολο του \(\N\) που είναι κλειστό ως προς την πρόσθεση, δηλαδή
\[ m,n\in R(x)\Rightarrow m+n\in R(x). \]Διαισθητικά αυτό σημαίνει ότι, αν είναι δυνατόν να επιστρέψουμε στο \(x\) μετά από \(m\) βήματα, αλλά και μετά από \(n\) βήματα, τότε είναι δυνατόν να επιστρέψουμε στο \(x\) και μετά από \(m+n\) βήματα. Πράγματι, από τις εξισώσεις Chapman-Kolmogorov, έχουμε
\[ p^{(m+n)}(x,x)=\sum_{y\in\X}p^{(m)}(x,y)p^{(n)}(y,x)\ge p^{(m)}(x,x)p^{(n)}(x,x)>0, \]εφόσον \(m,n\in\R(x)\). Για τέτοια σύνολα έχουμε το ακόλουθο λήμμα.
Απόδειξη: Θα συμβολίζουμε με \(d\N\) το σύνολο των φυσικών που είναι πολλαπλάσια του \(d\), δηλαδή \(d\N=\{d,2d,3d,\ldots\}\). Αν \(d\in R\), εφόσον το \(R\) είναι ένα κλειστό ως προς την πρόσθεση υποσύνολο του \(\N\), έχουμε \(R=d\N\). Αν πάλι \(d\notin R\), τότε, εφόσον το \(d\) είναι ο μέγιστος κοινός διαιρέτης του \(R\), θα υπάρχουν \(m_1,\ldots,m_k\in R\) και \(p_1,p_2,\ldots,p_k\in \Z\setminus\{0\}\) τέτοια ώστε
\begin{equation} \sum_{i=1}^kp_im_i=d. \end{equation}
Έστω \(I\subset\{1,2,\ldots,k\}\) το σύνολο των δεικτών \(i\) για τους οποίους \(p_i>0\) και \(I'=\{1,2,\ldots,k\}\setminus I\) το σύνολο των δεικτών \(i\) για τους οποίους \(p_i<0\). Προφανώς, το \(I\) δεν μπορεί να είναι κενό αφού το δεξί μέλος της (6.1) είναι φυσικός αριθμός. Ούτε το \(I'\) μπορεί να είναι κενό όμως, αφού κάθε προσθετέος στo αριστερό μέλος της (6.1) είναι μεγαλύτερος ή ίσος από \(2d\) κατ' απόλυτη τιμή στην περίπτωση \((d\notin R)\) που εξετάζουμε. Μπορούμε επομένως να ξαναγράψουμε την (6.1) ως
\[ \sum_{i\in I} p_im_i-\sum_{i\in I'} (-p_i)m_i =d. \]Εφόσον το \(R\) είναι κλειστό ως προς την πρόσθεση και \(p_i>0\) για \(i\in I\) έχουμε ότι \(m=\sum_{i\in I}p_im_i\in R\). Αντίστοιχα, έχουμε ότι \(n=\sum_{i\in I'} (-p_i)m_i \in R\). Βρήκαμε επομένως δύο στοιχεία \(m,n\in R\) τέτοια ώστε \(m=n+d\). Θα δείξουμε ότι το \(R\) περιέχει κάθε φυσικό της μορφής \(Nd\) για \(Nd\ge n(n-1)\). Πράγματι, αν γράψουμε την ταυτότητα της ακέραιας διαίρεσης του \(Ν\) με το \(n\) έχουμε
\begin{equation} N=qn+\upsilon,\qquad \text{ για κάποια } q\ge \frac{n-1}{d},\ \upsilon\in\{0,1,2,\ldots,n-1\}. \end{equation}
Έχουμε τώρα \[ Nd=qnd+\upsilon d=qnd+\upsilon (m-n)=\upsilon m+ (qd-\upsilon) n. \]Οι \(\upsilon\) και \(qd-\upsilon\) είναι μη αρνητικοί ακέραιοι λόγω της (6.2) και τουλάχιστον ένας από αυτούς είναι διάφορος από το μηδέν αφού έχουν άθροισμα \(qd\). Eφόσον \(m,n\in R\) και το \(R\) είναι κλειστό ως προς την πρόσθεση, θα έχουμε \(Nd\in R\) για κάθε φυσικό \(N\ge n(n-1)/d\).
\(\square\)
Θα χρησιμοποιήσουμε τώρα το Λήμμα 6.1 για να δείξουμε ότι η περίοδος είναι χαρακτηριστικό κλάσης.
Απόδειξη: Aν οι \(x,y\in\X\) επικοινωνούν αμφίδρομα, υπάρχουν \(m,n\in\N\) τέτοια ώστε
\[ p^{(m)}(x,y)>0\quad \text{και}\quad p^{(n)}(y,x)>0. \]Επιπλέον, αν \(\ell\in\R(x)\), τότε θα έχουμε \(m+n+\ell\in R(y)\). Πράγματι,
\[ p^{(m+n+\ell)}(y,y)=\sum_{z,w\in\X}p^{(n)}(y,z)p^{(\ell)}(z,w)p^{(m)}(w,y)\ge p^{(n)}(y,x)p^{(\ell)}(x,x)p^{(m)}(x,y)>0. \]Από το Λήμμα 6.1, υπάρχει κάποιο \(q\in\N\) τέτοιο ώστε \(qd(x), (q+1)d(x)\in \R(x)\). Από την προηγούμενη παρατήρηση, θα έχουμε λοιπόν
\[ m+n+qd(x)\in R(y)\quad\text{και}\quad m+n+(q+1)d(x)\in R(y). \]Επομένως, \(d(y)/ m+n+qd(x)\) και \(d(y)/m+n+(q+1)d(x)\) και άρα \(d(y)/d(x)\). Εναλλάσσοντας τον ρόλο των \(x,y\) στο παραπάνω επιχείρημα, παίρνουμε ότι \(d(x)/d(y)\) και άρα \(d(x)=d(y)\).
\(\square\)
Υπό το φως του Θεωρήματος 6.1 έχει νόημα να μιλάμε για την περίοδο μιας κλάσης ή για την περίοδο μιας μη υποβιβάσιμης αλυσίδας και να χαρακτηρίζουμε μια τέτοια αλυσίδα απεριοδική όταν η περίοδός όλων των καταστάσεών της είναι 1. Το ακόλουθο πόρισμα είναι συχνά χρήσιμο γιατί δίνει μια ικανή συνθήκη ώστε να είναι μια αλυσίδα απεριοδική που μπορεί να ελεγχθεί με απλή επισκόπηση.
Απόδειξη: Εφόσον \(p(x,x)>0\) έχουμε \(1\in R(x)\) και άρα \(d(x)=1\). Επειδή η αλυσίδα είναι μη υποβιβάσιμη, όλες οι καταστάσεις της θα έχουν την ίδια περίδο με την \(x\), δηλαδή 1.
\(\square\)
Το ακόλουθο λήμμα θα μας φανεί επίσης χρήσιμο στις επόμενες παραγράφους.
Απόδειξη: Εφόσον \(d(x)=1\) από το Λήμμα 6.1 υπάρχει ένα \(n_1\in\N\) τέτοιο ώστε \(p^{(n)}(x,x)>0\), για κάθε \(n\ge n_1\). Εφόσον η \(\{X_n\}_n\) είναι μη υποβιβάσιμη υπάρχει ακόμη ένα \(m\in\N\) τέτοιο, ώστε \(p^{(m)}(x,y)>0\). Αν τώρα \(n\ge n_1+m\), έχουμε
\[ p^{(n)}(x,y)=\sum_{z\in\X}p^{(n-m)}(x,z)p^{(m)}(z,y)\ge p^{(n-m)}(x,x)p^{(m)}(x,y)>0. \]\(\square\)
Προσέξτε ότι στο παράδειγμα που είδαμε στην αρχή της παραγράφου, για το οποίο η κατανομή \(\pi_n\) της αλυσίδας μετά από \(n\) βήματα δεν συγκλίνει στην αναλλοίωτη κατανομή της αλυσίδας, η περίοδος της αλυσίδας είναι 2. Ο λόγος που η σύγκλιση αποτυγχάνει είναι γιατί αν μια μη υποβιβάσιμη αλυσίδα έχει περίοδο \(d\), ο χώρος κατάστασεων διαμερίζεται σε \(d\) σύνολα \(\X=\cup_{j=0}^{d-1}C_j\), σε καθένα από τα οποία η αλυσίδα μπορεί να επιστρέψει μόνο μετά από ένα αριθμό βημάτων που είναι πολλαπλάσιο του \(d\). Δηλαδή,
\[ \PP{X_n\in C_j\, |\, X_0 \in C_j}\neq 0\Leftrightarrow d/n. \]Πιο συγκεκριμένα έχουμε το ακόλουθο θεώρημα, του οποίου η απόδειξη αφήνεται σαν άσκηση.
Θεώρημα 6.2 Έστω \(\{X_n\}_{n\in\N_0}\) μια μη υποβιβάσιμη αλυσίδα σε έναν χώρο καταστάσεων \(\X\ni x\) με πιθανότητες μετάβασης \(p(\cdot,\cdot)\) και περίοδο \(d\). Τότε η αλυσίδα \(\{Y_{n}\}_{n\in\N_0}\) με \(Y_n=X_{nd}\) (δηλαδή η αλυσίδα που προκύπτει αν δειγματοληπτούμε την \(\{X_n\}_n\) κάθε \(d\) βήματα) είναι υποβιβάσιμη στις \(d\) απεριοδικές κλάσεις
\[ C_v=\{y\in\X:p^{(dn+v)}(x,y)>0, \text{ για κάποιο } n\in\N_0\},\quad v\in{0,1,2,\ldots d-1}. \]Επιπλέον, αν η αλυσίδα \(\{X_n\}_{n\in\N}\) είναι γνησίως επαναληπτική με αναλλοίωτη κατανομή \(\pi\), τότε η αναλλοίωτη κατανομή \(\pi_v\) της αλυσίδας \(\{Y_{n}\}_{n\in\N_0}\) που στηρίζεται στην κλάση \(C_v\) δίνεται από την
\begin{equation} \pi_v(y)=\begin{cases} d\,\pi(y), & \text{αν }y\in C_v\\ 0, &\text{αν }y\notin C_v.\end{cases} \end{equation}
Στην παράγραφο 6.4 θα δούμε ότι αν μια μη υποβιβάσιμη και γνησίως επαναληπτική αλυσίδα είναι απεριοδική, τότε σε βάθος χρόνου η κατανομή της αλυσίδας \(\pi_n\) θα συγκλίνει στην αναλλοίωτη κατανομή της. Αυτό είναι ένα πολύ χρήσιμο αποτέλεσμα, γιατί εκτός του ότι περιγράφει την ασυμπτωτική συμπεριφορά της αλυσίδας, προσφέρει και έναν υπολογιστικό τρόπο για να πάρουμε δείγματα από μια κατανομή \(\pi\). Χρειάζεται απλώς να κατασκευάσουμε μια μη υποβιβάσιμη, γνησίως επαναληπτική και απεριοδική αλυσίδα που έχει αναλλοίωτη κατανομή την \(\pi\) και να αφήσουμε αυτή την αλυσίδα να κάνει αρκετά βήματα ώστε η κατανομή της να πλησιάσει την \(\pi\). Αυτή η ιδέα είναι η βάση της μεθόδου Markov Chain Monte Carlo (MCMC), που θα μελετήσουμε εκτενέστερα στο Κεφάλαιο 7.
Για την απόδειξη της σύγκλισης \(\pi_n\to\pi\) θα χρησιμοποιήσουμε μια πολύ ισχυρή πιθανοθεωρητική τεχνική, τη σύζευξη (coupling). Λόγω της χρησιμότητας αυτής της τεχνικής θα αφιερώσουμε την επόμενη παράγραφο στο να την περιγράψουμε μέσα από δύο παραδείγματα.
Η σύζευξη είναι μια πολύ γενική μέθοδος με την οποία μπορούμε να πάρουμε χρήσιμα αποτελέσματα για την κατανομή τυχαίων μεταβλητών, ορισμένων εν γένει σε διαφορετικούς χώρους πιθανότητας, θεωρώντας έναν μεγαλύτερο χώρο πιθανότητας στον οποίο μπορούμε να ορίσουμε ταυτόχρονα τις τυχαίες μεταβλητές χωρίς να αλλάξουμε την κατανομή τους. Πιο συγκεκριμένα, αν η τυχαία μεταβλητή \(X\) έχει οριστεί στον χώρο πιθανότητας \((\Omega_1,{\cal F}_1,\P_1)\) και η τυχαία μεταβλητή \(Y\) έχει οριστεί στον χώρο πιθανότητας \((\Omega_2,{\cal F}_2,\P_2)\) μπορούμε να ορίσουμε τις \(\tilde{X},\tilde{Y}\) στον κοινό δειγματικό χώρο \(\Omega=\Omega_1\times\Omega_2\) ως εξής
\[ \tilde{X}(\omega_1,\omega_2)=X(\omega_1), \quad \tilde{Y}(\omega_1,\omega_2)=Y(\omega_2). \]Αν εφοδιάσουμε τον \(\Omega\) με ένα μέτρο πιθανότητας \(\P\) που, περιορισμένο στο \(\Omega_i\), ταυτίζεται με το \(\P_i\) για \(i\in\{1,2\}\), αν δηλαδή
\begin{equation} \PP{A_1\times \Omega_2}=\P_1\big[A_1\big]\quad \text{και}\quad \PP{\Omega_1\times Α_2}=\P_2\big[Α_2\big], \end{equation}
για κάθε \(A_i\subset\Omega_1\) στο πεδίο ορισμού \({\cal F}_i\) του \(\P_i\), τότε οι \(\tilde{X},\tilde{Y}\), που είναι από κοινού ορισμένες στον \(\Omega\), έχουν την ίδια κατανομή με τις \(X\) και \(Y\), αντίστοιχα. Πράγματι,
\[ \PP{\tilde{X}\in C}=\PP{\{X\in C\}\times\Omega_2}=\P_1\big[X\in C\big] \]
και αντίστοιχα για τις
\(\tilde{Y}\) και \(Y\). Ένα μέτρο πιθανότητας \(\P\) που ικανοποιεί
τις (6.4)
ονομάζεται μέτρο σύζευξης των \(\P_1\) και \(\P_2\).
Παρατηρήστε ότι ενώ οι σχέσεις (6.4) που
επιβάλλουμε στο \(\P\) καθορίζουν την κατανομή καθεμιάς από τις
\(\tilde{X}\) και \(\tilde{Y}\), δεν μας δίνουν καμιά πληροφορία για
τον τρόπο που οι \(\tilde{X}\) και \(\tilde{Y}\) συνδέονται μεταξύ
τους. Η τεχνική της σύζευξης συνίσταται στο να επιλέξουμε το μέτρο
σύζευξης \(\P\) με τρόπο ώστε η από κοινού κατανομή των
\(\tilde{X},\tilde{Y}\) κάτω από το \(\P\) να μας οδηγεί σε χρήσιμα
συμπεράσματα.
Ας δούμε πώς μπορούμε να εφαρμόσουμε το παραπάνω γενικό
σχέδιο μέσα από δύο συγκεκριμένα παραδείγματα.
Σε αυτό το σημείο αξίζει να δοκιμάσετε να αποδείξετε τον ισχυρισμό του παραδείγματος χωρίς να χρησιμοποιήσετε την τεχνική της σύζευξης. Θα δείτε ότι δεν είναι καθόλου εύκολο. Θεωρήστε τώρα μια άλλη τυχαία μεταβλητή \(Y\) με την ίδια κατανομή όπως η \(X\) και ανεξάρτητη από τη \(X\). Παρατηρήστε ότι, εφόσον οι \(f,g\) έχουν το ίδιο είδος μονοτονίας, τότε για κάθε \(x,y\in\R\) έχουμε
\[ \big(f(x)-f(y)\big)\big(g(x)-g(y)\big)\ge 0 \]
και επομένως η τυχαία
μεταβλητή \(\big(f(X)-f(Y)\big)\big(g(X)-g(Y)\big)\) παίρνει μόνο μη
αρνητικές τιμές. Ειδικότερα, \begin{align*} 0&\le
\EE{\big(f(X)-f(Y)\big)\big(g(X)-g(Y)\big)}\\
&=\EE{f(X)g(X)}+\EE{f(Y)g(Y)}-\EE{f(X)g(Y)}-\EE{f(Y)g(X)}\\
&=\EE{f(X)g(X)}+\EE{f(Y)g(Y)}-\EE{f(X)}\EE{g(Y)}-\EE{f(Y)}\EE{g(X)}\\
&=2\big(\EE{f(X)g(X)}-\EE{f(X)}\EE{g(X)}\big), \end{align*} όπου η
προτελευταία ισότητα ισχύει επειδή οι \(X,Y\) είναι ανεξάρτητες, ενώ η
τελευταία ισότητα προκύπτει από το ότι οι \(X,Y\) έχουν την ίδια
κατανομή.
Πού ακριβώς χρησιμοποιήσαμε τη σύζευξη στο παραπάνω
επιχείρημα; Λέγοντας ``θεωρήστε τώρα μια άλλη τυχαία μεταβλητή \(Y\) με
την ίδια κατανομή όπως η \(X\) και ανεξάρτητη από τη \(X\)''
αποσιωπήσαμε πώς μπορεί κανείς να ορίσει στον ίδιο χώρο πιθανότητας δύο
τυχαίες μεταβλητές με δεδομένη κατανομή ώστε αυτές να είναι
ανεξάρτητες. Αυτό γίνεται ακριβώς με την τεχνική της σύζευξης. Με τον
συμβολισμό που περιγράψαμε πριν, αν η \(X\) είναι ορισμένη σε έναν χώρο
πιθανότητας \((\Omega_1,{\cal F}_1,\P_1)\) και η \(Y\) είναι ορισμένη
σε έναν χώρο πιθανότητας \((\Omega_2,{\cal F}_2,\P_2)\), εφοδιάζουμε
τον χώρο γινόμενο \(\Omega_1\times\Omega_2\) με το μέτρο γινόμενο
\(\P=\P_1\times\P_2\), που ικανοποιεί την
για κάθε \(A_i\subset\Omega_i\) στο πεδίο ορισμού \({\cal F}_i\) του \(P_i\). Το \(\P\) είναι μέτρο σύζευξης αφού \(\P_i\big[\Omega_i\big]=1\), επομένως οι \(\tilde{X}\) και \(\tilde{Y}\) που είναι ορισμένες στον \(\Omega\) έχουν την κατανομή των \(X\) και \(Y\), αντίστοιχα. Επιπλέον το \(\P\) κάνει τις \(\tilde{X}\) και \(\tilde{Y}\) ανεξάρτητες, αφού
\[ \PP{\tilde{X}\in C_1, \tilde{Y}\in C_2}=\PP{\{{X}\in C_1\}\times\{{Y}\in C_2\}}=\P_1\big[X\in C_1\big]\P_2\big[Y\in C_2\big]=\PP{\tilde{X}\in C_1}\PP{\tilde{Y}\in C_2}. \]
Κατασκευάσαμε
λοιπόν ανεξάρτητες τυχαίες μεταβλητές \(\tilde{X},\tilde{Y}\),
ορισμένες σε έναν κοινό χώρο πιθανότητας, με την ίδια κατανομή όπως οι
\(X\) και \(Y\) αντίστοιχα. Έχοντας πλέον δει πώς γίνεται αυτό,
μπορούμε για χάριν απλότητας να συμβολίζουμε τις
\(\tilde{X},\tilde{Y}\) με \(X\) και \(Y\) αντίστοιχα.
Παρατηρήστε ότι κάθε μέτρο σύζευξης δίνει στις
\(\tilde{X},\tilde{Y}\) την κατανομή των \(X,Y\) αντίστοιχα.
Επιλέγοντας να εφοδιάσουμε τον \(\Omega\) με το μέτρο γινόμενο \(\P\)
καθορίσαμε επιπλέον πώς αυτές συνδέονται μεταξύ τους: είναι
ανεξάρτητες. Στη συνέχεια χρησιμοποιήσαμε την ανεξαρτησία τους στην
πορεία της απόδειξης.
Είναι διαισθητικά αναμενόμενο ότι όσο πιο πιθανό είναι να διαγράψουμε
κάθε ακμή τόσο λιγότερο πιθανό είναι το να παραμείνει συνεκτικός ο
γράφος μετά τις διαγραφές. Παρ' όλα αυτά δεν είναι εύκολο να αποδείξει
κανείς αυστηρά αυτόν τον ισχυρισμό χωρίς να χρησιμοποιήσει την ιδέα της
σύζευξης. Ο λόγος είναι ότι, αν χρησιμοποιήσει κανείς ένα κέρμα που έχει
πιθανότητα να φέρει κεφαλή \(p_1\) και το στρίψει για κάθε ακμή του
γράφου για να αποφασίσει αν θα τη διαγράψει και στη συνέχεια κάνει
το ίδιο με ένα κέρμα που έχει πιθανότητα να φέρει κεφαλή \(p_2>p_1\),
είναι δυνατόν τα αποτελέσματα των στριψιμάτων να είναι τέτοια ώστε στην
πρώτη περίπτωση να καταλήξει με έναν μη συνεκτικό γράφο, ενώ στη
δεύτερη με έναν συνεκτικό γράφο. Θα χρησιμοποιήσουμε την ιδέα της
συζευξης ώστε να κάνουμε τις διαγραφές με πιθανότητα \(p_1\) και
\(p_2\) συντονισμένα και με τρόπο ώστε οι ακμές που διαγράφουμε στην
πρώτη περίπτωση να είναι υποσύνολο εκείνων που διαγράφουμε στη
δεύτερη.
Ο γράφος του πειράματος είναι μια τυχαία μεταβλητή \(G\)
ορισμένη στον δειγματικό χώρο \(\Omega=\{0,1\}^E\) με τιμές στο σύνολο
των γράφων που έχουν κορυφές τα σημεία του \(V\) και ακμές κάποιο
υποσύνολο του \(E\). Πράγματι, το \(\omega=\{\omega_e\}_{e\in
E}\in\Omega\) αντιστοιχεί στον γράφο \(G(\omega)\) με σύνολο ακμών το
\(E(\omega)=\{e\in E: \omega_e=1\}\). Προκειμένου να διαγράφουμε κάθε
ακμή ανεξάρτητα με πιθανότητα \(p\), εφοδιάζουμε τον \(\Omega\) με το
μέτρο γινόμενο \(\P_p\), κάτω από το οποίο οι τυχαίες μεταβητές
\(\{X_e\}_{e\in E}\) με \(X_e(\omega)=\omega_e\) είναι ανεξάρτητες και
ισόνομες με κατανομή Bernoulli(1-p).
Αν στρίψουμε δύο διαφορετικά κέρματα με πιθανότητες να φέρουν κεφαλή \(p_1,p_2\) αντίστοιχα (\(p_1 < p_2 \)), εφοδιάζουμε τον \(\Omega\times \Omega\) με το μέτρο σύζευξης \(\P_{p_1} \times \P_{p_2} \) κάτω από το οποίο οι \(\tilde{X}_e (\omega, \omega ') = \omega_e \) και \(\tilde{Y}_e(\omega,\omega')=\omega'_e\) είναι ανεξάρτητες. Αυτό το μέτρο όμως επιτρέπει σε μια ακμή να διαγραφεί από τον \(G(\omega)\), όχι όμως και από τον \(G(\omega')\).
Πράγματι, \[ \P_{p_1}\times\P_{p_2}\big[\omega_e=0, \omega'_e=1\big]=p_1(1-p_2)>0. \]Για να εξασφαλίσουμε ότι όλες οι ακμές του \(G(\omega')\) περιέχονται στις ακμές του \(G(\omega)\) θα κατασκευάσουμε ένα μέτρο σύζευξης \(\P\) των \(\P_{p_1}\) και \(\P_{p_2}\) στον χώρο γινόμενο \(\Omega\times\Omega\) τέτοιο ώστε
\begin{equation} \PP{\tilde{Y}_e\le \tilde{X}_e \text{ για κάθε } e\in E}=1. \end{equation}
Δεν είναι δύσκολο να δει κανείς ότι για να είναι το \(\P\) μέτρο σύζευξης των \(\P_{p_1}\) και \(\P_{p_2}\) θα πρέπει οι \(\{\tilde{X}_e\}_{e\in E}\) να είναι ανεξάρτητες τυχαίες μεταβλητές με κατανομή Bernoulli \((1-p_1)\) και οι \(\{\tilde{Y}_e\}_{e\in E}\) να είναι ανεξάρτητες τυχαίες μεταβλητές με κατανομή Bernoulli \((1-p_2)\).Παρατηρήστε ότι κάτω από το μέτρο \(\P\) οι \(\{(\tilde{X}_e,\tilde{Y}_e)\}_{e\in E}\) είναι μια ακολουθία από ανεξάρτητες ισόνομες τυχαίες μεταβλητές με κατανομή \(\Q\). Εφόσον \(\PP{\tilde{X}_e=1}=\Q\big[\{(1,0),(1,1)\}\big]=1-p_1\) έχουμε ότι οι \(\{\tilde{X}_e\}_{e\in E}\) είναι ανεξάρτητες, ισόνομες τυχαίες μεταβλητές με κατανομή Bernoulli \((1-p_1)\). Αντίστοιχα, εφόσον \(\PP{\tilde{Y}_e=1}=\Q\big[\{(0,1),(1,1)\}\big]=1-p_2\), οι \(\{\tilde{Y}_e\}_{e\in E}\) είναι ανεξάρτητες, ισόνομες τυχαίες μεταβλητές με κατανομή Bernoulli \((1-p_2)\). Επομένως το \(\P\) είναι πράγματι μέτρο σύζευξης. Κάτω από το \(\P\) οι \(\tilde{X}_e\) και \(\tilde{Y}_e\) δεν είναι μεταξύ τους ανεξάρτητες, αλλά για κάθε \(e\in E\) έχουμε
\[ \PP{\tilde{Y}_e\le\tilde{X}_e}=\Q\big[\{(0,0),(1,0),(1,1)\}\big]=p_1+(p_2-p_1)+(1-p_2)=1. \] Επιπλέον, λόγω της ανεξαρτησίας των \(\{(\tilde{X}_e,\tilde{Y}_e)\}_{e\in E}\), έχουμε ότι \[ \PP{\tilde{Y}_e\le \tilde{X}_e \text{ για κάθε } e\in E}=\PP{\bigcap_{e\in E}\{\tilde{Y}_e\le\tilde{X}_e\}}=\prod_{e\in E}\PP{\tilde{Y}_e\le\tilde{X}_e}=1, \]
οπότε το μέτρο \(\P\) πράγματι
ικανοποιεί την (6.5). Θα
δείξουμε τώρα ότι αν υπάρχει μέτρο σύζευξης \(\P\) των \(\P_{p_1}\) και
\(\P_{p_2}\) που ικανοποιεί την (6.5), τότε
\(\P_{p_1}\big[C\big]\ge \P_{p_2}\big[C\big].\)
Αν ορίσουμε την τυχαία μεταβλητή
Επιπλέον αν \(\omega,\omega'\in\Omega\) και \(\omega'_e\le \omega_e\) για κάθε \(e\in E\), τότε το σύνολο των ακμών του \(G(\omega')\) είναι υποσύνολο των ακμών του \(G(\omega)\) και άρα \(F(\omega')\le F(\omega)\). Ορίζουμε τέλος τις συναρτήσεις \(F_1,F_2\) στον \(\Omega\times\Omega\) με τύπους \(F_1(\omega,\omega')=F(\omega)\) και \(F_2(\omega,\omega')=F(\omega')\). Παρατηρήστε ότι, αν το μέτρο \(\P\) ικανοποιεί την (6.5), τότε
\begin{equation} \PP{F_1\ge F_2}=\PP{\{(\omega,\omega')\in\Omega\times\Omega: F(\omega)\ge F(\omega')\}}\ge\PP{\omega'_e\le\omega_e,\text{ για κάθε }e\in E}=1. \end{equation}
Έχουμε τώρα \[ \P_{p_1}\big[C\big]=\E_{p_1}\big[F\big]=\EE{F_1}\ge \EE{F_2}=\E_{p_2}\big[F\big]=\P_{p_2}\big[C\big], \]
όπου η δεύτερη και
η προτελευταία ισότητα προκύπτουν από το γεγονός ότι το \(\P\) είναι
μέτρο σύζευξης, ενώ η τρίτη ισότητα από την (6.6).
Θα κλείσουμε αυτή την παράγραφο με μια παρατήρηση. Στην
απόδειξη που δώσαμε για τον ισχυρισμό του Παραδείγματος 2,
χρησιμοποιήσαμε συμβολισμό συμβατό με αυτόν της εισαγωγής της
παραγράφου, κατασκευάζοντας ένα κατάλληλο μέτρο σύζευξης στον χώρο
γινόμενο \(\{0,1\}^E\times\{0,1\}^E\). Διαβάζοντας όμως προσεκτικά την
απόδειξη διαπιστώνουμε ότι είναι αρκετό να κατασκευάσουμε τυχαίες
μεταβλητές \(\{X_e,Y_e\}_{e\in E}\) σε έναν κοινό χώρο πιθανότητας
\((\Omega,{\cal F},\P)\) έτσι ώστε: α) οι \(\{X_e\}_{e\in E}\) να είναι
ανεξάρτητες τυχαίες μεταβλητές με κατανομή Bernoulli \((1-p_1)\), β) οι
\(\{Y_e\}_{e\in E}\) να είναι ανεξάρτητες τυχαίες μεταβλητές με κατανομή
Bernoulli \((1-p_2)\) και γ) \(\PP{Y_e\le X_e\text{ για κάθε }e\in
E}=1\).
Αυτό μπορούμε να το πετύχουμε με τον εξής απλούστερο και
ενδεχομένως πιο διδακτικό τρόπο. Θεωρούμε έναν χώρο πιθανότητας
\(({\Omega},{{\cal F}},{\P})\) στον οποίο μπορούμε να ορίσουμε μια
ακολουθία από ανεξάρτητες, ισόνομες τυχαίες μεταβλητές \(\{U_e\}_{e\in
E}\) με ομοιόμορφη κατανομή στο (0,1). Για κάθε \(e\in E\) ορίζουμε τις
\({X}_e,{Y}_e\) με τη βοήθεια της \(U_e\) ως εξής
Λόγω της ανεξαρτησίας των \(\{U_e\}_{e\in E}\) οι \(\{(X_e,Y_e)\}_{e\in E}\) είναι ανεξάρτητες. Επιπλέον
\[ \PP{X_e=1}=\PP{U_e>1-p_1}=1-p_1\quad\text{και}\quad \PP{Y_e=1}=\PP{U_e>1-p_2}=1-p_2, \]άρα πράγματι οι (α) και (β) παραπάνω ικανοποιούνται. Τέλος η (γ) είναι προφανής από την κατασκευή των \(X_e,Y_e\) αφού \(Y_e=1\Leftrightarrow U_e>p_2\Rightarrow X_e=1\).
Απόδειξη: Η απόδειξη βασίζεται στην τεχνική της σύζευξης. Όπως είδαμε στην παράγραφο της σύζευξης, μπορούμε να κατασκευάσουμε στον ίδιο χώρο πιθανότητας την αλυσίδα \(\{X_n\}_{n\in\N_0}\) και μια άλλη ανεξάρτητη αλυσίδα \(\{Y_n\}_{n\in\N}\) με αρχική κατανομή \(\pi\) και τις ίδιες πιθανότητες μετάβασης όπως η \(\{X_n\}_{n\in\N_0}\). Oρίζουμε τον χρόνο
\[ T=\inf\{k\ge 0: X_k=Y_k\} \]
της πρώτης συνάντησης των δύο
ανεξάρτητων αλυσίδων. Το υπόλοιπο της απόδειξης μπορεί να χωριστεί σε
μια σειρά από βήματα.
Βήμα 1 Θα δείξουμε ότι \(\PP{T<+\infty}=1\).
Στον χώρο καταστάσεων \(\X\times\X\) θεωρούμε τη στοχαστική
διαδικασία \(\{W_n\}_{n\in\N_0}\) με \(W_n=(X_n,Y_n)\). Είναι εύκολο να
δει κανείς ότι αυτή είναι μια μαρκοβιανή αλυσίδα με αρχική κατανομή
\(\tilde{\pi}_0\) όπου
και πιθανότητες μετάβασης \begin{align*} \tilde{p}\big((x,u),(y,v)\big)&=\PP{W_{n+1}=(y,v)\,|\, W_n=(x,u)}=\PP{X_{n+1}=y,Y_{n+1}=v\,|\, X_n=x,Y_n=u}\\ &=\PP{X_{n+1}=y\,|\,X_n=x}\PP{Y_{n+1}=v\,|\,Y_n=u}=p(x,y)p(u,v). \end{align*} Επιπλέον η \(\{W_n\}_n\) είναι μη υποβιβάσιμη. Πράγματι, εφόσον η \(\{X_n\}\) είναι απεριοδική, από το Λήμμα 6.2 για κάθε \(x,y,u,v\in\X\) υπάρχει ένα \(n_0\) τέτοιο ώστε
\[ n\ge n_0\Rightarrow p^{(n)}(x,y)>0\text{ και } p^{(n)}(u,v)>0. \]
Έτσι, αν \(n\ge n_0\),
έχουμε \begin{align*}
\tilde{p}^{(n)}\big((x,u),(y,v)\big)&=\PP{W_n=(y,v)\,|\,
W_0=(x,u)}=\PP{X_n=y,Y_n=v\,|\,X_0=x,Y_0=u}\\
&=\PP{X_n=y\,|\,X_0=x}\PP{Y_n=v\,|\, Y_0=u}=p^{(n)}(x,y)p^{(n)}(u,v)>0,
\end{align*} επομένως οποιαδήποτε κατάσταση \((y,v)\in\X\times\X\)
είναι προσβάσιμη από οποιαδήποτε άλλη κατάσταση \((x,u)\in\X\times\X\).
Θα δείξουμε τέλος ότι η \(\tilde{\pi}:\X\times\X\to[0,1]\) με
\(\tilde{\pi}(y,v)=\pi(y)\pi(v)\) είναι αναλλοίωτη κατανομή για τη
\(\{W_n\}_n\). Πράγματι, είναι φανερό ότι \(\tilde{\pi}(y,v)\ge 0\) για
κάθε \((y,v)\in\X\times\X\), ενώ
Τέλος,
\begin{align*}
\sum_{x,u\in\X}\tilde{\pi}(x,u)\tilde{p}\big((x,u),(y,v)\big)&=\sum_{x,u\in\X}\pi(x)\pi(u)p(x,y)p(u,v)\\
&=\sum_{x\in\X}
\pi(x)p(x,y)\sum_{u\in\X}\pi(u)p(u,v)=\pi(y)\pi(v)=\tilde{\pi}(y,v).
\end{align*} Εφόσον η \(\{W_n\}_n\) είναι μια μη υποβιβάσιμη αλυσίδα
που έχει αναλλοίωτη κατανομή \(\tilde{\pi}\), είναι και γνησίως
επαναληπτική. Ο χρόνος \(T\) που ορίσαμε παραπάνω είναι ο χρόνος πρώτης
άφιξης της \(\{W_n\}_n\) στη διαγώνιο του \(\X\times\X\), δηλαδή στο
σύνολο \(\Delta=\{(w,w): w\in\X\}\). Aπό την επαναληπτικότητα της
αλυσίδας προκύπτει ο ισχυρισμός του βήματος.
Βήμα 2: Ορίζουμε τη διαδικασία \(\{Ζ_n\}_{n\in\N_0}\) ως εξής:
Θα δείξουμε ότι η
\(\{Z_n\}_n\) είναι μια μαρκοβιανή αλυσίδα στον \(\X\) με αρχική
κατανομή \(\pi_0\) και πιθανότητες μετάβασης \(p(\cdot,\cdot)\), έχει
δηλαδή την ίδια κατανομή με τη \(\{X_n\}_n\).
Αυτός ο ισχυρισμός είναι διαισθητικά φανερός. Η \(\{Z_n\}\)
παρακολουθεί τη \(\{X_n\}\) μέχρι τον χρόνο \(T\) κατά τον οποίο η
\(\{X_n\}_n\) συναντά για πρώτη φορά την \(\{Y_n\}_n\) και στη
συνέχεια παρακολουθεί την \(\{Y_n\}_n\). Επειδή όμως, από την ισχυρή
μαρκοβιανή ιδιότητα, τόσο η \(\{X_{T+n}\}_{n\in\N_0}\) όσο και η
\(\{Y_{T+n}\}_{n\in\N_0}\) είναι μαρκοβιανές αλυσίδες που ξεκινούν από
το σημείο συνάντησής τους, έχουν πιθανότητες μετάβασης
\(p(\cdot,\cdot)\) και είναι ανεξάρτητες από το παρελθόν του χρόνου
\(T\), περιμένουμε ότι θα είναι αδύνατο να ξεχωρίσει κανείς τη
στατιστική συμπεριφορά των \(\{X_n\}_n\) και \(\{Ζ_n\}_n\).
Το ότι η \(Z_0\) έχει κατανομή \(\pi_0\) είναι φανερό, αφού
\(T\ge 0\) και άρα \(\PP{Z_0=X_0}=1\). Θα δείξουμε ακόμα ότι αν τα
σημεία \(z_0,z_1,\ldots,z_n\in\X\) είναι τέτοια ώστε
\(p(z_i,z_{i+1})>0\) για \(i\in\{0,1,\ldots,n-1\}\), τότε
\begin{equation} \PP{Z_{n+1}=y\,|\, Z_n=z_n,\ldots,Z_0=z_0}= p(z_n,y). \end{equation}
Από τη διαμέριση \(\Omega=\bigcup_{k=0}^n\{T=k\}\cup\{T>n\}\) έχουμε\begin{align} \PP{Z_{n+1}=y\,|\, Z_n=z_n,\ldots,Z_0=z_0}&=\sum_{k=0}^n\PP{Z_{n+1}=y, Τ=k\,|\, Z_n=z_n,\ldots,Z_0=z_0}\nonumber\\ &\qquad+\PP{Z_{n+1}=y, Τ>n\,|\, Z_n=z_n,\ldots,Z_0=z_0} \end{align}
Αν \(k\in\{0,1,\ldots,n\}\), έχουμε \begin{align*} \PP{Z_{n+1}&=y, T=k\,|\, Z_n=z_n,\ldots,Z_0=z_0}\\ &=\frac{\PP{X_0=z_0\neq Y_0,\ldots, X_{k-1}=z_{k-1}\neq Y_{k-1},X_k=Y_k=z_k, Y_{k+1}=z_{k+1},\ldots, Y_n=z_n, Y_{n+1}=y}}{\PP{Z_0=z_0,\ldots,Z_n=z_n}}\\ &=\frac{\PP{Y_{n+1}=y, Y_n=z_n,\ldots,Y_k=z_k,Y_{k-1}\neq z_{k-1},\ldots,Y_0\neq z_0}}{\PP{Z_0=z_0,\ldots,Z_n=z_n}}\PP{X_i=z_i, i=0,\ldots,k}. \end{align*} Από τη μαρκοβιανή ιδιότητα της \(\{Y_n\}_n\) έχουμε περαιτέρω ότι
\begin{align} \PP{Z_{n+1}&=y, T=k\,|\, Z_n=z_n,\ldots,Z_0=z_0}\nonumber\\ &=p(z_n,y)\frac{\PP{X_0=z_0\neq Y_0,\ldots, X_{k-1}=z_{k-1}\neq Y_{k-1},X_k=Y_k=z_k, Y_{k+1}=z_{k+1},\ldots, Y_n=z_n}}{\PP{Z_0=z_0,\ldots,Z_n=z_n}}\nonumber\\ &=p(z_n,y)\PP{T=k\,|Z_0=z_0,\ldots, Z_n=z_n}. \end{align}
Με παρόμοιο τρόπο, έχουμε\begin{align} \PP{Z_{n+1}=y, T>n\,|\, Z_n=z_n,\ldots,Z_0=z_0}&=\frac{\PP{X_i=z_i\neq Y_i, i=0,1,\ldots,n, X_{n+1}=y}}{\PP{Z_0=z_0,\ldots,Z_n=z_n}}\nonumber\\ &=p(z_n,y)\frac{\PP{X_i=z_i\neq Y_i, i=0,1,\ldots,n}}{\PP{Z_0=z_0,\ldots,Z_n=z_n}}\nonumber\\ &=p(z_n,y)\PP{T>n\,|Z_0=z_0,\ldots,Z_n=z_n}. \end{align}
Αντικαθιστώντας τις (6.9) και (6.10) στην (6.8) παίρνουμε την (6.7).\begin{equation} |\pi_n(x)-\pi(x)|\le\PP{T>n}. \end{equation}
Εφόσον οι \(\{X_n\}_n\) και \(\{Z_n\}_n\) έχουν την ίδια κατανομή, έχουμε \[ \pi_n(x)=\PP{X_n=x}=\PP{Z_n=x}, \text{ για κάθε } x\in\X,\ n\in\N_0. \]Eπειδή η αρχική κατανομή \(\pi\) της \(\{Y_n\}_n\) είναι αναλλοίωτη κατανομή έχουμε
\[ \pi(x)=\PP{Y_n=x}, \text{ για κάθε } x\in\X,\ n\in\N_0. \]Συνδυάζοντας τις δύο παραπάνω σχέσεις έχουμε ότι, για κάθε \(x\in\X\) και \(n\in\N_0\), \begin{align*} \big|\pi_n(x)-\pi(x)|&=|\ \PP{Z_n=x}-\PP{Y_n=x}\ \big|\\ &=\big|\ \PP{Z_n=x, T\le n}+\PP{Z_n=x, T>n}-\PP{Y_n=x, T\le n}-\PP{Y_n=x, T>n}\ \big|\\ &=\big|\ \PP{X_n=x, T>n}-\PP{Y_n=x, T>n}\ \big|\\ &\le \PP{T>n}. \end{align*} Η ακολουθία ενδεχομένων \(A_n=\{T>n\}\) είναι φθίνουσα, δηλαδή \(A_{n+1}\subset A_n\), για κάθε \(n\in\N_0\). Έχουμε λοιπόν
\[ \lim_{n\to\infty}\PP{T>n}=\PP{\bigcap_n\{T>n\}}=\PP{T=\infty}=0 \]
από
το αποτέλεσμα του βήματος 1. Συνεπώς, για κάθε \(x\in\X\) έχουμε
\(\pi_n(x)\to\pi(x)\) και άρα \(\pi_n\to\pi\).
Τέλος, για να αποδείξουμε ότι \(p^{(n)}(x,y)\to\pi(y)\) αρκεί
να ξεκινήσουμε την αλυσίδα \(\{X_n\}\) από την κατάσταση \(x\), να
πάρουμε δηλαδή \(\PP{X_0=x}=1\). Τότε
\(p^{(n)}(x,y)=\PP{X_n=y}\to\pi(y)\), μια και ο ισχυρισμός του
θεωρήματος ισχύει για οποιαδήποτε αρχική κατανομή \(\pi_0\).
\(\square\)
Παρατηρήστε πώς χρησιμοποιήσαμε τη συνθήκη της απεριοδικότητας στην απόδειξη στο βήμα 1. Χωρίς την απεριοδικότητα της \(\{X_n\}\) δεν είναι δυνατόν να συμπεράνουμε ότι η \(\{W_n\}_n\) είναι μη υποβιβάσιμη. Αν για παράδειγμα θεωρήσουμε μια αλυσίδα που κινείται στις κορυφές ενός τετραγώνου \(A,B,C,D\) και σε κάθε βήμα μεταβαίνει με πιθανότητα 1/2 σε μία από τις δύο γειτονικές της κορυφές, τότε η κατάσταση \((Α,Α)\) δεν είναι προσβάσιμη για την \(\{W_n\}_n\) από την κατάσταση \((A,B)\). Πράγματι,
\[ \PP{W_n=(A,A)\,|\, W_0=(A,B)}=p^{(n)}(A,A)p^{(n)}(B,A)=0, \]αφού ο πρώτος όρος του γινομένου στο δεξί μέλος είναι 0 αν \(n\) περιττός, ενώ ο δεύτερος όρος είναι 0 αν \(n\) άρτιος. Επομένως, χωρίς την απεριοδικότητα της \(\{X_n\}\) δεν μπορούμε να συμπεράνουμε τη συνθήκη \(\PP{T<+\infty}=1\) που μας δίνει το ζητούμενο με τη βοήθεια της εκτίμησης του βήματος 3.
Σε αυτή την παράγραφο θα αποδείξουμε το εργοδικό θεώρημα για μαρκοβιανές αλυσίδες. Το εργοδικό θεώρημα μας δίνει πληροφορίες για την ασυμπτωτική συμπεριφορά του χρονικού μέσου όρου συναρτησιακών της αλυσίδας και με αυτή την έννοια είναι μια γενίκευση του κλασικού νόμου των μεγάλων αριθμών στην περίπτωση μεταβλητών που δεν είναι ανεξάρτητες. Στην περίπτωση μη αρνητικών τυχαίων μεταβλητών που θα χρειαστούμε παρακάτω ο ισχυρός νόμος των μεγάλων αριθμών διατυπώνεται ως εξής.
Η απόδειξη αυτού του θεωρήματος μπορεί να βρεθεί στην
[Varadhan01]
και στην
[Williams91]
. Προσέξτε ότι για κάθε \(n\in\N\) ο χρονικός μέσος της ακολουθίας
\(\frac{1}{n}\sum_{k=1}^n Ζ_k\) είναι μια τυχαία μεταβλητή. Ο νόμος των
μεγάλων αριθμών μάς δίνει την πληροφορία ότι η κατανομή αυτής της
τυχαίας μεταβλητής συγκεντρώνεται ασυμπτωτικά γύρω από το \(\mu\). Η
ανεξαρτησία των \(\{Ζ_n\}_{N\in\N}\) παίζει αποφασιστικό ρόλο σε αυτό.
Πράγματι, στην ακραία περίπτωση που πάρει κανείς όλες τις μεταβλητές
ίσες με μια τυχαία μεταβλητή \(Ζ\), ο μέσος όρος οσωνδήποτε από αυτές
είναι η πάλι η \(Ζ\) και φυσικά η κατανομή του δεν συγκεντρώνεται γύρω
από έναν αριθμό. Μπορούμε να καταλάβουμε τον μηχανισμό με τον οποίον
υπεισέρχεται η ανεξαρτησία στην περίπτωση \(\mu<\infty\) ως εξής. Για
ένα τυπικό \(\omega\in\Omega\), κάποιες από τις τυχαίες μεταβλητές
παίρνουν τιμές μεγαλύτερες από τη μέση τιμή τους \(\mu\) και κάποιες
μικρότερες. Επειδή οι μεταβλητές είναι ανεξάρτητες, οι προς τα πάνω
αποκλίσεις απο τη μέση τιμή σε μεγάλο βαθμό αλληλοαναιρούνται με τις
προς τα κάτω αποκλίσεις, τόσο που οι αθροιστικές αποκλίσεις \(n\)
προσθετέων είναι πολύ μικρότερες από το \(n\) με το οποίο διαιρούμε,
και στο όριο \(n\to\infty\) εξαφανίζονται.
Αν τώρα \(\{X_n\}_{n\in\N_0}\) είναι μια μη υποβιβάσιμη
μαρκοβιανή αλυσίδα σε έναν χώρο καταστάσεων \(\X\) και \(f:\X\to\R\),
μπορεί κανείς να μελετήσει τον χρονικό μέσο όρο των πραγματικών τυχαίων
μεταβλητών \(Z_n=f(X_n)\). Αυτές βέβαια δεν είναι ανεξάρτητες. Έχουμε
όμως δει ότι η εξάρτηση της κατανομής μιας μη υποβιβάσιμης μαρκοβιανής
αλυσίδας από τις προηγούμενες τιμές της εξασθενεί προϊόντος του χρόνου.
Το εργοδικό θεώρημα μας λέει ότι και σε αυτή την περίπτωση οι
αθροιστικές αποκλίσεις \(n\) προσθετέων είναι πολύ μικρότερες από το
\(n\) και οι χρονικοί μέσοι όροι συγκλίνουν καθώς \(n\to\infty\). Στην
απλούστερη μορφή του που θα δούμε πρώτα, η συνάρτηση \(f\) είναι η
δείκτρια μιας κατάστασης \(x\in\X\) και το εργοδικό θεώρημα μας δίνει
πληροφορία για το ασυμπτωτικό ποσοστό του χρόνου που περνά η αλυσίδα
στη \(x\).
Για \(x\in\X\) oρίζουμε \(V_n(x)\) το πλήθος των επισκέψεων
στη \(x\) μιας αλυσίδας \(\{X_n\}_{n\in\N_0}\) πριν τη χρονική στιγμή
\(n\),
\begin{equation} \P\Big[\ {\frac{V_n(x)}{n}\to \frac{1}{\mrtx}}\Big]=1. \end{equation}
Αξίζει να παρατηρήσουμε ότι το αν υπάρχει το όριο \(V_n(x)/n\) και το ποιο είναι αυτό εξαρτάται μόνο από την τελική συμπεριφορά της αλυσίδας και όχι από τα οσαδήποτε πρώτα βήματά της. Πράγματι, αν \(M\in\N\) και θεωρήσουμε τη διαδικασία \(\{Y_n\}_{n\in\N_0}\) με \(Y_n=X_{M+n}\), έχουμε
\[ \sum_{k=0}^{n-1}1\!\!1\{X_k=x\}-\sum_{k=0}^{n-1}1\!\!1\{Y_k=x\}=\sum_{k=0}^{M-1}\big(1\!\!1\{X_k=x\}-1\!\!1\{X_{n+k}=x\}\big) \] και επομένως \[ \big|\frac{1}{n}\sum_{k=0}^{n-1}1\!\!1\{X_k=x\}-\frac{1}{n}\sum_{k=0}^{n-1}1\!\!1\{Y_k=x\}\big|\le \frac{M}{n}\to 0,\quad\text{καθώς } n\to\infty. \]
Μάλιστα, ακόμα κι αν
η \(M=M(\omega)\) είναι ένας τυχαίος χρόνος με \(\PP{M<+\infty}=1\),
μπορούμε να χρησιμοποιήσουμε αυτό το επιχείρημα για κάθε
\(\omega\in\{\omega\in\Omega: M(\omega)<+\infty\}\).
Αν η \(x\) είναι επαναληπτική κατάσταση και \(T_x=\inf\{k\ge
0: X_k=x\}\), τότε για οποιαδήποτε αρχική κατανομή της αλυσίδας έχουμε
\(\PP{T_x<+\infty}=1\). Επιπλέον, από την ισχυρή μαρκοβιανή ιδιότητα, η
διαδικασία \(\{Y_n\}_{n\in\N_0}\) με \(Y_n=X_{T_x+n}\) είναι μια
αλυσίδα που ξεκινά από το \(x\) και έχει τις ίδιες πιθανότητες
μετάβασης όπως η \(\{X_n\}_{n}\). Σύμφωνα με την προηγούμενη παρατήρησή
μας, για να δείξουμε την (6.12) στην
περίπτωση που η \(x\) είναι επαναληπτική, αρκεί να δείξουμε ότι
\begin{equation} \P_x\Big[\ {\frac{V_n(x)}{n}\to \frac{1}{\mrtx}}\Big]=1. \end{equation}
Ορίζουμε \(S_0=0\) και επαγωγικά για κάθε \(n\in\N\) τον χρόνο της \(n\)-στής επανόδου στην κατάσταση \(x\) ως εξής \[ S_n(\omega)=\inf\{k>S_{n-1}(\omega): X_k=x\}. \]Από την ισχυρή μαρκοβιανή ιδιότητα και την επαναληπτικότητα της \(x\), έχουμε \(\P_x\big[S_n<+\infty\text{ για κάθε }n\in\N\big]=1\). Επιπλέον, όπως είδαμε στο Πόρισμα 2.2 , οι χρόνοι \(\{S_n-S_{n-1}\}_{n\in\N}\), που μεσολαβούν ανάμεσα σε διαδοχικές επισκέψεις στην κατάσταση \(x\) είναι ανεξάρτητες, ισόνομες τυχαίες μεταβλητές με κοινή κατανομή αυτήν της \(S_1-S_0=T_x^+\). Από τον νόμο των μεγάλων αριθμών (Θεώρημα 6.4) έχουμε επομένως
\[ \P_x\Big[\ \lim_{n\to\infty}\frac{S_n}{n}= \mrtx \Big]=1. \]
Από την επαναληπτικότητα της κατάστασης \(x\) έχουμε ακόμα \[ \P_x\big[V_n(x)\to\infty\big]=1. \]Αφού τα παραπάνω ενδεχόμενα συμβαίνουν με \(\P_x\)-πιθανότητα 1 και η τομή τους θα συμβαίνει με \(\P_x\)-πιθανότητα 1, επομένως
\begin{equation} \P_x\Big[\lim_{n\to\infty}\frac{S_{V_n(x)}}{V_n(x)}=\mrtx\Big]=1. \end{equation}
Παρατηρήστε όμως τώρα ότι, για μια αλυσίδα που ξεκινά από το \(x\), ο χρόνος \(S_{V_n(x)}=\inf\{k\ge n: X_k=x\}\) είναι ο χρόνος της πρώτης επίσκεψης στην \(x\) μετά τη χρονική στιγμή \(n\) για κάθε \(n\in\N\), επομένως
\[ \P_x \Big[ S_{ V_n(x) - 1} < n \le S_{ V_n(x) }, \quad \text {για κάθε } n \in \N \Big ] = 1 \]
και άρα η (6.13) προκύπτει από την
(6.14).
Αν η κατάσταση \(x\) είναι παροδική, η απόδειξη της (6.12) είναι
ακόμα πιο εύκολη, αφού τότε \(\mrtx=+\infty\), ενώ
\(\PP{\lim_{n\to\infty}V_n(x)<+\infty}=1\) και άρα
\(\PP{\lim_{n\to\infty}V_n(x)/n=0}=1\).
Ο ισχυρισμός του θεωρήματος προκύπτει τώρα από την (6.12) επειδή ο
\(\X\) έχει το πολύ αριθμήσιμο πλήθος από στοιχεία. Πράγματι, η (6.12) σημαίνει
ότι για κάθε \(x\in\X\) έχουμε \(\PP{U_x}=1\), όπου
Εφόσον καθένα από τα \(U_x\) έχει πιθανότητα 1, το ίδιο θα συμβαίνει και για την αριθμήσιμη τομή τους \(\cap_{x\in\X}U_x\), αφού
\[ \P\Big[\big(\bigcap_{x\in\X} U_x\big)^c\Big]=\P\Big[\bigcup_{x\in\X}U_x^c\Big]\le \sum_{x\in\X}\PP{U_x^c}=\sum_{x\in\X}0=0. \]
\(\square\)
Παρατήρηση: Αν η αλυσίδα \(\{X_n\}\) είναι εκτός από μη υποβιβάσιμη και γνησίως επαναληπτική, θα έχει μοναδική αναλλοίωτη κατανομή \(\pi\), η οποία θα ικανοποιεί όπως είδαμε στο προηγούμενο κεφάλαιο την \[ \pi(x)=\frac{1}{\mrtx},\quad\text{ για κάθε } x\in\X. \]Σε αυτή την περίπτωση το Θεώρημα 6.5 μάς λέει ότι σε βάθος χρόνου το ποσοστό του χρόνου που ξοδεύει η αλυσίδα σε κάθε κατάσταση \(x\in\X\) είναι το βάρος που δίνει στη \(x\) η αναλλοίωτη κατανομή \(\pi\):
\begin{equation} \P\Big[\ {\frac{V_n(x)}{n}\to \pi(x)},\quad\text{για κάθε }x\in\X\Big]=1. \end{equation}
Στην περίπτωση αυτή μπορούμε να διατυπώσουμε το εργοδικό Θεώρημα και με μια διαφορετική μορφή που πολλές φορές είναι πιο χρήσιμη για υπολογισμούς.όπου \(\E^\pi\big[f\big]=\sum_{x\in\X} f(x)\pi(x)\) είναι η μέση τιμή της τυχαίας μεταβλητής \(f(X)\), αν η τυχαία μεταβλητή \(X\) ακολουθεί την αναλλοίωτη κατανομή της αλυσίδας \(\pi\).
Απόδειξη: Επειδή κάθε χρονική στιγμή \(k\in\N_0\) η αλυσίδα βρίσκεται σε ακριβώς μία από τις καταστάσεις του \(\X\) έχουμε
\[ \sum_{x\in\X}1\!\!1\{X_k=x\}=1. \]Μπορούμε τώρα να γράψουμε τον χρονικό μέσο των τιμών της \(f\) κατά μήκος του μονοπατιού της αλυσίδας ως \begin{align*} \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)&= \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)\sum_{x\in\X}1\!\!1\{X_k=x\}\nonumber\\ &=\frac{1}{n}\sum_{x\in\X}\sum_{k=0}^{n-1}f(X_k)1\!\!1\{X_k=x\}\nonumber\\ &=\frac{1}{n}\sum_{x\in\X}\sum_{k=0}^{n-1}f(x)1\!\!1\{X_k=x\}\nonumber\\ &=\sum_{x\in\X}f(x)\frac{1}{n}\sum_{k=0}^{n-1}1\!\!1\{X_k=x\}\nonumber\\ &=\sum_{x\in\X}f(x)\frac{V_n(x)}{n}. \end{align*} Στην περίπτωση που ο \(\X\) είναι πεπερασμένος, ο ισχυρισμός προκύπτει κατευθείαν από το Θεώρημα 6.5. Στην περίπτωση που ο \(\X\) έχει άπειρο αλλά αριθμήσιμο πλήθος από καταστάσεις, θεωρήστε \(M>0\) τέτοιο ώστε \(|f(x)|\le M\), για κάθε \(x\in\X\). Εφόσον η σειρά \(\sum_{x\in\X}\pi(x)\) συγκλίνει (στο 1), για κάθε \(\epsilon>0\) μπορούμε να βρούμε ένα πεπερασμένο σύνολο από καταστάσεις \(A\subset\X\) τέτοιο ώστε \(\sum_{x\notin A}\pi(x)<\frac{\epsilon}{2M}\). Έχουμε
\begin{align} \Big|\, \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)-\E^\pi\big[f\big]\Big|&=\Big|\,\sum_{x\in\X}f(x)\big(\frac{V_n(x)}{n}-\pi(x)\big)\Big|\nonumber\\ &\le M\sum_{x\in\X}\Big|\frac{V_n(x)}{n}-\pi(x)\Big|\nonumber\\ &=M\sum_{x\in A}\Big|\frac{V_n(x)}{n}-\pi(x)\Big|+M\sum_{x\notin A}\Big|\frac{V_n(x)}{n}-\pi(x)\Big|. \end{align}
Για τους προσθετέους του τελευταίου όρου θα χρησιμοποιήσουμε την αλγεβρική ταυτότητα \(|u|=u+2u^-\), που ισχύει για κάθε \(u\in\R\), όπου \(u^-\) είναι το αρνητικό μέρος του \(u\) και δίνεται από την \(u^-=\max\{0,-u\}\). Παίρνουμε έτσι \begin{align*} \sum_{x\notin A}\Big|\frac{V_n(x)}{n}-\pi(x)\Big|&=\sum_{x\notin A}\Big(\frac{V_n(x)}{n}-\pi(x)\Big)+2\sum_{x\notin A}\Big(\frac{V_n(x)}{n}-\pi(x)\Big)^-\\ &= \sum_{x\in A}\Big(\pi(x)-\frac{V_n(x)}{n}\Big)+2\sum_{x\notin A}\Big(\frac{V_n(x)}{n}-\pi(x)\Big)^-\\ &\le \sum_{x\in A}\Big(\pi(x)-\frac{V_n(x)}{n}\Big)+2\sum_{x\notin A}\pi(x)\\ &\le \sum_{x\in A}\Big(\pi(x)-\frac{V_n(x)}{n}\Big)+\frac{\epsilon}{M}, \end{align*} όπου στο δεύτερο βήμα χρησιμοποιήσαμε ότι
\[ \sum_{x\in\X}\frac{V_n(x)}{n}=1=\sum_{x\in\X}\pi(x), \]ενώ στο τρίτο ότι, αν \(u,v>0\), τότε \((u-v)^-\le v\). Με αντικατάσταση της παραπάνω σχέσης στην (6.16) έχουμε
\[ \Big|\, \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)-\E^\pi\big[f\big]\Big|\le 2M\sum_{x\in A}\Big|\frac{V_n(x)}{n}-\pi(x)\Big|+{\epsilon}. \]Εφόσον το σύνολο \(A\) είναι πεπερασμένο, για τα \(\omega\in\Omega\) για τα οποία \(V_n(x)/n\to\pi(x)\) έχουμε
\[ \limsup_{n\to\infty}\Big|\, \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)-\E^\pi\big[f\big]\Big|\le\epsilon \]και άρα από το Θεώρημα 6.5 έχουμε ότι για κάθε \(\epsilon>0\)
\[ \P\Big[\limsup_{n\to\infty}\Big|\, \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)-\E^\pi\big[f\big]\Big|\le\epsilon\Big]=1. \]Αν πάρουμε τώρα \(\epsilon=1/N\), η ακολουθία ενδεχομένων
\[ B_N=\{\omega\in\Omega: \limsup_{n\to\infty}\Big|\, \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)-\E^\pi\big[f\big]\Big|\le\frac{1}{N}\} \]είναι φθίνουσα (\(B_{N+1}\subset B_N\) για κάθε \(N\in\N\)) και \(\PP{B_N}=1\) για κάθε \(N\in\N\). Επομένως,
\[ \P\Big[\ \frac{1}{n}\sum_{k=0}^{n-1}f(X_k)\to \E^\pi\big[f\big]\Big]=\PP{\bigcap_N B_N}=\lim_{N\to\infty}\PP{B_N}=1, \]που είναι και ο ισχυρισμός του θεωρήματος.
\(\square\)
