\(\newcommand{\PP}[1]{\P\big[#1\big]} \newcommand{\Px}[1]{\P_x\big[#1\big]} \newcommand{\EE}[1]{\E\big[#1\big]} \newcommand{\Ex}[1]{\E_x\big[#1\big]} \newcommand{\en}[1]{\textlatin{#1}} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\X{\mathbb{X}} \def\Y{\mathbb{Y}} \def\P{\mathbb{P}} \def\Q{\mathbb{Q}} \def\E{\mathbb{E}} \def\R{\mathbb{R}} \def\MX{{\cal M}(\X)} \def\F{{\cal F}} \def\xn{\{X_n\}_{n\in\N_0}} \def\half{\frac{1}{2}} \def\IP{{\cal I}(P)} \def\mrtx{\E_x\big[T_x^+\big]} \def\ma{\en{martingale}} \)
Οι αναλλοίωτες κατανομές είναι κατά κάποιο τρόπο οι φυσικές καταστάσεις μιας μαρκοβιανής αλυσίδας. Αν μια αλυσίδα ξεκινήσει από μια αναλλοίωτη κατανομή της, θα παραμείνει σε αυτήν για πάντα, ενώ η ασυμπτωτική συμπεριφορά μιας αλυσίδας μπορεί να χαρακτηριστεί μέσω αυτών. Επίσης, οι απαντήσεις σε πολλά προβλήματα μπορούν εύκολα να εκφραστούν μέσω των αναλλοίωτων κατανομών. Σε αυτό το κεφάλαιο θα δούμε ικανές και αναγκαίες συνθήκες για την ύπαρξη αναλλοίωτων κατανομών, θα μελετήσουμε τις ιδιότητες και τη δομή τους. Παρόμοιο υλικό μπορείτε να βρείτε στις αναφορές [Norris98] και [Levin09] .
Θα συμβολίζουμε το σύνολο των κατανομών στον \(\X\) με \(\MX\). Έτσι \[ \pi\in\MX\Leftrightarrow \text{ η } \pi \text{ είναι μια συνάρτηση }\pi:\X\to[0,1]\ \text{ με } \sum_{x\in\X}\pi(x)=1. \] Έστω \(\{X_n\}_{n\in\N}\) μια μαρκοβιανή αλυσίδα με αρχική κατανομή \(\pi_0\) και πιθανότητες μετάβασης \(\{p(x,y)\}_{x,y\in\X}\). Θα συμβολίζουμε την κατανομή της τυχαίας μεταβλητής \(X_n\) με \(\pi_n\), δηλαδή
\begin{equation} \pi_n(x)=\PP{X_n=x},\quad\text{για }x\in\X. \end{equation}
Το κεντρικό ερώτημα αυτού του κεφαλαίου είναι αν η \(\pi_n\) συγκλίνει καθώς \(n\to\infty\) και, αν ναι, ποιο είναι το όριό της.
Ορισμός Αν \(\{\pi_n\}_n\)
είναι μια ακολουθία κατανομών στο \(\MX\), θα λέμε ότι συγκλίνει στην
κατανομή \(\pi\in\MX\) αν και μόνο h πιθανότητα που αποδίδει η
\(\pi_n\) σε κάθε κατάσταση συγκλίνει στην αντίστοιχη πιθανότητα που
αποδίδει η \(\pi\). Δηλαδή,
\begin{equation} \pi_n\to\pi\in\MX\Leftrightarrow \pi_n(x)\to\pi(x),\quad\text{για κάθε }x\in\X. \end{equation}
Παρατήρηση: Από ένα αποτέλεσμα της θεωρίας μέτρου, το λήμμα του Scheffe (βλ. [Williams91] , παρ. 5.10), o παραπάνω ορισμός είναι ισοδύναμος με το φαινομενικά ισχυρότερο αποτέλεσμα
\begin{equation} \pi_n\to\pi\in\MX\Leftrightarrow \sum_{x\in\X}|\pi_n(x)-\pi(x)|\to 0. \end{equation}
Ορισμός: Αν η \(\{\pi_n\}_n\)
είναι η ακολουθία των κατανομών μιας μαρκοβιανής αλυσίδας \(\{X_n\}\),
αν δηλαδή η \(\pi_n\) ορίζεται όπως στην (5.1) για κάθε
\(n\in\N_0\) και \(\pi_n\to\pi\in\MX\), θα λέμε ότι η \(\pi\) είναι η
κατανομή ισορροπίας (ή εναλλακτικά η
ασυμπτωτική κατανομή) της \(\{X_n\}\).
Το πρώτο μας αποτέλεσμα χαρακτηρίζει τις υποψήφιες κατανομές
ισορροπίας μαρκοβιανών αλυσίδων.
\begin{equation} \pi=\pi P,\quad\text{δηλαδή}\quad \pi(x)=\sum_{y\in\X}\pi(y)p(y,x),\quad\text{για κάθε }x\in\X. \end{equation}
Απόδειξη: Είδαμε στο δεύτερο κεφάλαιο ότι η κατανομή \(\pi_n\) μιας μαρκοβιανής αλυσίδας \(\{X_n\}_{n}\) μετά από \(n\) βήματα, δηλαδή η κατανομή της τυχαίας μεταβλητής \(X_n\), δίνεται από την \[ \pi_n=\pi_0P^n. \] Επομένως, για κάθε \(n\in\N\) έχουμε \[ \pi_n=\pi_0(P^{n-1}P)=(\pi_0P^{n-1})P=\pi_{n-1}P, \] δηλαδή \[ \pi_n(x)=\sum_{y\in\X}\pi_{n-1}(y)p(y,x)\quad\text{για κάθε }x\in\X. \] Παίρνοντας το όριο καθώς \(n\to\infty\) στα δύο μέλη της προηγούμενης σχέσης, το αριστερό μέλος συγκλίνει στην \(\pi(x)\), ενώ για το δεξί μέλος έχουμε \[ |\sum_{y\in\X}\pi_{n-1}(y)p(y,x)-\sum_{y\in\X}\pi(y)p(y,x)|\le\sum_{y\in\X}|\pi_{n-1}(x)-\pi(x)|p(y,x)\le\sum_{y\in\X}|\pi_{n-1}(x)-\pi(x)|\to 0 \] από την (5.3). Επομένως, \(\pi(x)=\sum_{y\in\X}\pi(y)p(y,x)\), για κάθε \(x\in X\).
\(\square\)
Σύμφωνα με το προηγούμενο Θεώρημα τα μόνα υποψήφια όρια των κατανομών μιας μαρκοβιανής αλυσίδας με πίνακα πιθανοτήτων μετάβασης \(P\) είναι εκείνες οι \(\pi:\X\to[0,1]\) για τις οποίες\begin{equation} \begin{cases}&\pi=\pi P\\ &\sum_{x\in\X}\pi(x)=1.\end{cases} \end{equation}
Ορισμός: Αν μια κατανομή
\(\pi\in\MX\) ικανοποιεί την (5.4), θα λέμε ότι
είναι
αναλλοίωτη (ή
στάσιμη) κατανομή για την αλυσίδα \(\{X_n\}_n\) με πίνακα
πιθανοτήτων μετάβασης \(P\).
Μπορούμε να το αναδιατυπώσουμε το Θεώρημα
5.1 ως εξής.
Οι μόνες δυνατές κατανομές ισορροπίας μιας μαρκοβιανής
αλυσίδας είναι οι αναλλοίωτες κατανομές της. Η ορολογία αναλλοίωτη και
στάσιμη εξηγείται από το παρακάτω Θεώρημα.
\(\square\)
Στη συνέχεια θα εξετάσουμε αν μπορούμε να βρούμε αναλλοίωτες κατανομές για μια αλυσίδα και, στην περίπτωση που μπορούμε, ποιες είναι αυτές. Θα συμβολίζουμε με \(\IP\) το σύνολο των αναλλοίωτων κατανομών μιας αλυσίδας με πίνακα πιθανοτήτων μετάβασης \(P\), δηλαδή \[ \IP=\{\pi\in\MX: \pi=\pi P\}. \] Το επόμενο λήμμα θα μας φανεί πολύ χρήσιμο.
\begin{equation} \pi(y)\ge\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big]. \end{equation}
Απόδειξη: Έστω \(\pi\in\IP\). Για κάθε \(x,y\in\X\) έχουμε \begin{align*} \pi(y)&=\sum_{z\in\X}\pi(z)p(z,y)=\pi(x)p(x,y)+\sum_{z\neq x}\pi(z)p(z,y)\\ &=\pi(x)p(x,y)+\sum_{z\neq x}\Big(\sum_{u\in\X}\pi(u)p(u,z)\Big)p(z,y)\\ &=\pi(x)\Big(p(x,y)+\sum_{z\neq x}p(x,z)p(z,y)\Big)+\sum_{z,u\neq x}\pi(u)p(u,z)p(z,y). \end{align*} Aς επαναλάβουμε την παραπάνω διαδικασία ακόμα μια φορά γράφοντας \[ \pi(u)=\sum_{w\in\X}\pi(w)p(w,u)=\pi(x)p(x,u)+\sum_{w\neq x}\pi(w)p(w,u). \] Παίρνουμε τότε ότι
\begin{align} \pi(y)&=\pi(x)\Big(p(x,y)+\sum_{z\neq x}p(x,z)p(z,y)+\sum_{z,u\neq x}p(x,u)p(u,z)p(z,y)\Big)\notag\\&\quad+\sum_{z,u,w\neq x}\pi(w)p(w,u)p(u,z)p(z,y). \end{align}
Προσέξτε ότι στον όρο \(\sum_{z,u\neq x}p(x,u)p(u,z)p(z,y)\) αθροίζουμε τις πιθανότητες όλων των μονοπατιών μήκους 3 που ξεκινούν από το \(x\) και καταλήγουν στο \(y\) χωρίς ενδιάμεσα να έχουν ξαναπεράσει από το \(x\). Άρα \[ \sum_{z,u\neq x}p(x,u)p(u,z)p(z,y)=\Px{X_1\neq x,\ X_2\neq x,\ X_3=y}=\Px{X_3=y,\ T_x^+\ge 3}. \] Αντίστοιχα έχουμε \[ \sum_{z\neq x}p(x,z)p(z,y)=\Px{X_1\neq x,\ X_2=y}=\Px{X_2=y,\ T_x^+\ge 2} \] ενώ \[ p(x,y)=\Px{X_1=y}=\Px{X_1=y,\ T_x^+\ge 1}. \] Με αυτή την παρατήρηση μπορούμε να ξαναγράψουμε την (5.7) ως \[ \pi(y)=\pi(x)\Big(\sum_{k=1}^3\Px{X_k=y,\ T_x^+\ge k}\Big)+\sum_{z,u,w\neq x}\pi(w)p(w,u)p(u,z)p(z,y). \] Θα πρέπει να είναι τώρα φανερό ότι, αν επαναλάβουμε αυτήν τη διαδικασία \(n\) φορές, έχουμε ότι
\begin{align} \pi(y)&=\pi(x)\Big(\sum_{k=1}^n\Px{X_k=y,\ T_x^+\ge k}\Big)+\sum_{x_1,\ldots,x_n\neq x}\pi(x_1)p(x_1,x_2)\cdots p(x_n,y)\\ &\ge\pi(x) \Big(\sum_{k=1}^n\Px{X_k=y,\ T_x^+\ge k}\Big),\qquad\text{για κάθε }n\in\N.\notag \end{align}
Περνώντας στο όριο \(n\to\infty\) έχουμε λοιπόν \begin{align*} \pi(y)&\ge \pi(x) \Big(\sum_{k=1}^\infty\Px{X_k=y,\ T_x^+\ge k}\Big)\\ &=\pi(x)\ \Big(\sum_{k=1}^\infty\Ex{1\!\!1\{X_k=y,\ T_x^+\ge k\}}\Big). \end{align*} Εφόσον οι δείκτριες συναρτήσεις που εμφανίζονται παραπάνω είναι μη αρνητικές, από το Θεώρημα Fubini-Tonelli μπορούμε να εναλλάξουμε την άθροιση ως προς \(k\) και την αναμενόμενη τιμή, παίρνοντας \begin{align*} \pi(y)&\ge\pi(x)\ \E_x\Big[\sum_{k=1}^\infty1\!\!1\{X_k=y,\ T_x^+\ge k\}\Big]\\ &=\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big].\ \end{align*}\(\square\)
Ορισμός: Θα λέμε μια κατάσταση
\(x\in\X\)
γνησίως επαναληπτική αν \(\Ex{T_x^+}<+\infty\).
Η γνήσια επαναληπτικότητα είναι μια έννοια ισχυρότερη της
επαναληπτικότητας, αφού αν \(\Ex{T_x^+}<+\infty\), τότε αναγκαστικά
έχουμε \(\Px{T_x^+<\infty}=1\) και άρα η \(x\) είναι επαναληπτική. Το
ακόλουθο Πόρισμα μας εγγυάται ότι οποιαδήποτε αναλλοίωτη κατανομή μιας
αλυσίδας στηρίζεται σε γνησίως επαναληπτικές καταστάσεις.
Απόδειξη: Αθροίζοντας τις ανισότητες (5.6) για όλα τα \(y\in\X\) έχουμε \[ 1=\sum_{y\in\X}\pi(y)\ge \pi(x)\ \sum_{y\in\X}\E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big]=\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\sum_{y\in\X}1\!\!1\{X_k=y\}\Big], \] όπου χρησιμοποιήσαμε το Θεώρημα Fubini-Tonelli για να εναλλάξουμε τη σειρά των αθροίσεων και της αναμενόμενης τιμής. Προσέξτε όμως ότι στο άθροισμα ως προς \(y\) υπάρχει ακριβώς ένας όρος \(1\!\!1\{X_k=y\}\) που είναι ίσος με 1 (αυτός που αντιστοιχεί στην κατάσταση της \(X_k\)), ενώ όλοι οι υπόλοιποι είναι μηδέν. Επομένως, η παραπάνω ανισότητα γίνεται \[ 1\ge \pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\Big]=\pi(x)\ \Ex{T_x^+}, \] απ' όπου έπεται ο ισχυρισμός μας.
\(\square\)
Απόδειξη: Αν \(\pi\in\IP\), τότε \(\pi(y)\ge 0\) για κάθε \(y\in\X\) και \(\sum_{y\in\X}\pi(y)=1\). Θα υπάρχει επομένως κάποια κατάσταση \(x\) για την οποία \(\pi(x)>0\) και άρα από το Πόρισμα 5.1 θα πρέπει \(\Ex{T_x^+}<\infty.\)
\(\square\)
Στο επόμενο θεώρημα θα δείξουμε ότι και το αντίστροφο του προηγούμενου πορίσματος είναι σωστό. Δηλαδή, αν μια αλυσίδα έχει μια γνησίως επαναληπτική κατάσταση \(x\) τότε έχει και αναλλοίωτη κατανομή, κατασκευάζοντας μια εκπεφρασμένα. Η ιδέα προέρχεται από το Λήμμα 5.1.
\begin{equation} \pi_x(x)=\frac{1}{\Ex{T_x^+}}. \end{equation}
Παρατήρηση: Μπορούμε να σκεφτούμε την κατανομή \(\pi_x\) ως εξής. Ξεκινώντας από τη \(x\) κάνουμε μια εκδρομή μέχρι να επιστρέψουμε πάλι στην κατάσταση \(x\), δηλαδή μέχρι τον χρόνο διακοπής \(T_x^+\). Κατά τη διάρκεια αυτής της εκδρομής σημειώνουμε πόσες επισκέψεις κάναμε στην κατάσταση \(y\in\X\). Το πλήθος αυτών των επισκέψεων είναι
\[ \sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\} \]
και είναι βέβαια μια τυχαία
μεταβλητή. Το βάρος που δίνει η \(\pi_x\) στην κατάσταση \(y\) είναι
ανάλογο προς το αναμενόμενο πλήθος των επισκέψεών μας στην κατάσταση
\(y\) κατά τη διάρκεια αυτής της εκδρομής γύρω από τη \(x\). Η σταθερά
αναλογίας \(\frac{1}{\Ex{T_x^+}}\) που εμφανίζεται είναι απλά ένας
παράγοντας κανονικοποίησης ώστε η \(\pi_x\) να είναι κατανομή.
Απόδειξη: Ας δούμε πρώτα ότι
\(\pi_x\in\MX.\) Πράγματι, είναι φανερό από τον ορισμό ότι
\(\pi_x(y)\ge 0\) για κάθε \(y\in\X\), ενώ \[ \sum_{y\in\X}\pi_x(y)=
\frac{1}{\Ex{T_x^+}}\
\sum_{y\in\X}\E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big]=
\frac{1}{\Ex{T_x^+}}\
\E_x\Big[\sum_{k=1}^{T_x^+}\sum_{y\in\X}1\!\!1\{X_k=y\}\Big]=
\frac{\Ex{T_x^+}}{\Ex{T_x^+}}=1. \] Ο ισχυρισμός της (5.9) προκύπτει
άμεσα από τον ορισμό του χρόνου \(T_x^+=\inf\{k\ge 1: X_k=x\}\), αφού
κατά τη διάρκεια της εκδρομής γύρω από τη \(x\), δηλαδή για
\(k\in\{1,2,\ldots,T_x^+\}\), η αλυσίδα μας βρίσκεται στη \(x\) μόνο
τη χρονική στιγμή \(T_x^+\).
Θα δείξουμε τώρα ότι η \(\pi_x\) είναι αναλλοίωτη. Πράγματι,
για κάθε \(y\in\X\) έχουμε
\begin{align} \pi_x(y)&=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big]\notag\\ &=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{\infty}1\!\!1\{X_k=y,\ T_x^+\ge k\}\Big]\notag\\ &=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{\infty}\sum_{z\in\X}1\!\!1\{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k\}\Big]\notag\\ &=\pi_x(x)\ \sum_{z\in\X}\sum_{k=1}^{\infty}\ \E_x\Big[1\!\!1\{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k\}\Big] \quad \text{(Θεώρημα Fubini-Tonelli) }\notag\\ &=\pi_x(x)\ \sum_{z\in\X}\sum_{k=1}^{\infty}\ \Px{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k}. \end{align}
Παρατηρήστε τώρα ότι \(1\!\!1\{T_x^+\ge k\}=1\!\!1\{X_1\neq x,\ X_2\neq x,\cdots,X_{k-1}\neq x\}\), επομένως το ενδεχόμενο \(\{T_x^+\ge k\}\) ανήκει στην κλάση \({\cal F}_{k-1}\). Έτσι, από τη μαρκοβιανή ιδιότητα έχουμε \[ \Px{X_k=y\, |\, X_{k-1}=z,\, T_x^+\ge k}=\Px{X_k=y\, |\, X_{k-1}=z}=p(z,y) \] και η σχέση (5.10) γίνεται
\begin{align} \pi_x(y)&=\pi_x(x)\ \sum_{z\in\X}p(z,y)\sum_{k=1}^{\infty}\Px{X_{k-1}=z,\, T_x^+\ge k}\notag\\ &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\sum_{k=1}^{\infty}\Ex{1\!\!1\{X_{k-1}=z,\, T_x^+\ge k\}}\notag\\ &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\ \E_x\Big[\sum_{k=1}^{\infty}1\!\!1\{X_{k-1}=z,\, T_x^+\ge k\}\Big]\quad \text{(Θεώρημα Fubini-Tonelli) }\notag\\ &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_{k-1}=z\}\Big]. \end{align}
Παρατηρήστε τέλος ότι \[ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_{k-1}=z\}\Big]\stackrel{m=k-1}{=}\E_x\Big[\sum_{m=0}^{T_x^+-1}1\!\!1\{X_{m}=z\}\Big]=\E_x\Big[\sum_{m=1}^{T_x^+}1\!\!1\{X_{m}=z\}\Big], \] όπου η τελευταία ισότητα προκύπτει γιατί η αλυσίδα μας με \(\P_x\)-πιθανότητα 1 βρίσκεται στη \(x\) τόσο τη χρονική στιγμή 0, όσο και τη χρονική στιγμή \(T_x^+\). Έτσι, η (5.11) γίνεται \[ \pi_x(y)=\sum_{z\in\X}p(z,y)\pi_x(x)\ \E_x\Big[\sum_{m=1}^{T_x^+}1\!\!1\{X_{m}=z\}\Big]=\sum_{z\in\X}p(z,y)\pi_x(z) \] και επομένως \(\pi_x\in\IP\).
\(\square\)
Όπως είδαμε μια γνησίως επαναληπτική κατάσταση \(x\in\X\) είναι επαναληπτική και άρα ανήκει αναγκαστικά σε μια κλειστή κλάση \(C_x\). Από την κατασκευή της κατανομής \(\pi_x\) είναι φανερό ότι \[ y\notin{C}_x\Rightarrow \pi_x(y)=0, \] αφού αν \(y\notin{C}_x\) η αλυσίδα που ξεκινά από τη \(x\) αποκλείεται να επισκεφτεί την κατάσταση \(y\) ποτέ και ειδικότερα αποκλείεται να επισκεφτεί την \(y\) μέχρι να επιστρέψει στη \(x\). Θα δείξουμε τώρα ότι η \(\pi_x\) δίνει θετικό βάρος σε όλες τις καταστάσεις της κλάσης \({C}_x\).
Απόδειξη: Εφόσον η \(y\) είναι προσβάσιμη από τη \(x\) υπάρχει \(m\in\N\) τέτοιο ώστε \(p^{(m)}(x,y)>0\). Επίσης εύκολα μπορούμε να δείξουμε επαγωγικά ότι \[ \pi_x\in\IP\Rightarrow \pi_x=\pi_x P\Rightarrow \pi_x=\pi_xP^m. \] Επομένως \[ \pi_x(y)=\sum_{z\in\X}\pi_x(z)p^{(m)}(z,y)\ge \pi_x(x)p^{(m)}(x,y)>0. \]
Απόδειξη: Προκύπτει αμέσως από το Πόρισμα 5.1 αφού \[ \pi_x\in\IP \quad\text{και}\quad \pi_x(y)>0\ \Rightarrow\ \E_y\big[T_y^+\big]<+\infty. \]
\(\square\)
Με βάση το παραπάνω Πόρισμα έχει νόημα να κάνουμε λόγο για γνησίως επαναληπτικές κλάσεις. Σημειώστε ότι, εφόσον οι ανοιχτές κλάσεις μιας αλυσίδας είναι παροδικές, τότε κάθε γνησίως επαναληπτική κλάση είναι κλειστή. Το ακόλουθο Πόρισμα συνοψίζει μια ικανή και αναγκαία συνθήκη για το πότε μια κλειστή κλάση είναι γνησίως επαναληπτική και αποτελεί συχνά έναν εύκολο τρόπο για να αποδείξει κανείς τη γνήσια επαναληπτικότητα μιας κλειστής κλάσης. Σημειώστε ότι για τον σκοπό αυτό αρκεί να περιορίσουμε την αλυσίδα σε αυτή την κλειστή κλάση, οπότε η αλυσίδα που θα προκύψει θα είναι μη υποβιβάσιμη.
Απόδειξη: Το Θεώρημα 5.3 εξασφαλίζει την ύπαρξη μιας αναλλοίωτης κατανομής \(\pi_x\) αν υπάρχει μια επαναληπτική κατάσταση \(x\). Αντίστροφα, αν η αλυσίδα έχει αναλλοίωτη κατανομή \(\pi\), τότε, από το Πόρισμα 5.2, η αλυσίδα θα έχει μια γνησίως επαναληπτική κατάσταση. Εφόσον η αλυσίδα είναι μη υποβιβάσιμη, από το Πόρισμα 5.3 όλες οι καταστάσεις της θα είναι γνησίως επαναληπτικές.
\(\square\)
Απόδειξη: Θεωρούμε ένα \(x\in\X\) και ορίζουμε \(T_x^+=\inf\{k>0: X_k=x\}\) τον χρόνο πρώτης επιστροφής στην κατάσταση \(x\). Εφόσον η αλυσίδα είναι μη υποβιβάσιμη, ολόκληρος ο \(\X\) είναι μια κλειστή και πεπερασμένη, άρα επαναληπτική κλάση. Έτσι, \(\Px{T_x^+<\infty}=1\). Ορίζουμε την \(\lambda:\X\to[0,\infty]\) με \[ \lambda(y)=\ \E_x\Big[\sum_{k=1}^{T_x^+}1\!\!1\{X_k=y\}\Big]. \] Από την απόδειξη του Θεωρήματος 5.3 έχουμε ότι \(\lambda=\lambda P\), ενώ \(\lambda(x)=1\). Θα δείξουμε ότι \(\lambda(y)<\infty\) για κάθε \(y\in\X\). Εφόσον η \(x\) είναι προσβάσιμη από την \(y\), επιλέγουμε \(m\in\N\) τέτοιο ώστε \(p^{(m)}(y,x)>0\). Έτσι \[ 1=\lambda(x)=\sum_{z\in\X} \pi(z)p^{(m)}(z,x)\ge \lambda(y)p^{(m)}(y,x)\Rightarrow \lambda(y)<\frac{1}{p^{(m)}(y,x)}<+\infty. \] Αν ορίσουμε τώρα \(Z=\sum_{y\in\X}\lambda(y)\in(1,+\infty)\) και \(\pi(y)=\lambda(y)/Z\) για κάθε \(y\in\X\), εύκολα επιβεβαιώνουμε ότι \(\pi\in\IP\) και άρα, από το Πόρισμα 5.4, η αλυσίδα είναι γνησίως επαναληπτική.
\(\square\)
Έχουμε ως τώρα δει ότι οποιαδήποτε αναλλοίωτη κατανομή δίνει μηδενικό βάρος σε κλάσεις που δεν είναι γνησίως επαναληπτικές (Πόρισμα 5.1), ενώ για κάθε γνησίως επαναληπτική κλάση έχουμε κατασκευάσει μια αναλλοίωτη κατανομή \(\pi_x\) που στηρίζεται στις καταστάσεις αυτής της κλάσης (Θεωρήματα 5.3 και 5.4). Θα δείξουμε στη συνέχεια ότι η αναλλοίωτη κατανομή που στηρίζεται σε μια γνησίως επαναληπτική κλάση είναι μοναδική. Όπως και στο προηγούμενο Πόρισμα, περιορίζοντας την αλυσίδα σε μια γνησίως επαναληπτική και επομένως κλειστή κλάση, αρκεί να υποθέσουμε ότι η αλυσίδα μας είναι μη υποβιβάσιμη.
Απόδειξη: H ύπαρξη μιας
τουλάχιστον αναλλοίωτης κατανομής εξασφαλίζεται από το Θεώρημα
5.3. Θα
αποδείξουμε εδώ τη μοναδικότητα. Έστω λοιπόν \(\pi\) μια αναλλοίωτη
κατανομή της \(\xn\).
Θεωρούμε ένα \(x\in\X\) και ορίζουμε την αναλλοίωτη κατανομή
\(\pi_x\) όπως στο Θεώρημα
5.3. Θα
δείξουμε ότι \(\pi(y)=\pi_x(y)\) για κάθε κατάσταση \(y\in\X\). Εφόσον
η αλυσίδα είναι μη υποβιβάσιμη, η \(x\) θα είναι προσβάσιμη από την
\(y\). Υπάρχει επομένως \(m\in\N\) τέτοιο ώστε \(p^{(m)}(y,x)>0\).
Έχουμε τώρα \begin{align*}
0&=\pi(x)-\pi(x)=\pi(x)-\frac{\pi(x)}{\pi_x(x)}\pi_x(x)\\
&=\sum_{z\in\X}\pi(z)p^{(m)}(z,x)-\frac{\pi(x)}{\pi_x(x)}\sum_{z\in\X}\pi_x(z)p^{(m)}(z,x)\quad
(\pi,\pi_x\in\IP)\\
&=\sum_{z\in\X}\Big(\pi(z)-\pi(x)\frac{\pi_x(z)}{\pi_x(x)}\Big)p^{(m)}(z,x).
\end{align*} Από το Λήμμα
5.1 κάθε
προσθετέος στο παραπάνω άθροισμα είναι μεγαλύτερος ή ίσος του μηδενός.
Για να είναι το άθροισμα 0 θα πρέπει όλοι οι προσθετέοι να είναι ίσοι
με 0. Ειδικότερα, \[
\Big(\pi(y)-\frac{\pi_x(y)}{\pi_x(x)}\pi(x)\Big)p^{(m)}(y,x)=0\Rightarrow
\pi(y)=\frac{\pi(x)}{\pi_x(x)}\pi_x(y). \] Εφόσον η \(y\) είναι
αυθαίρετα επιλεγμένη έχουμε ότι
\begin{equation} \pi(y)=\frac{\pi(x)}{\pi_x(x)}\pi_x(y), \quad\text{για κάθε }y\in\X. \end{equation}
Αθροίζοντας τις παραπάνω σχέσεις σε όλα τα \(y\in\X\) έχουμε \[ 1=\sum_{y\in\X}\pi(y)=\sum_{y\in\X}\frac{\pi(x)}{\pi_x(x)}\pi_x(y)=\frac{\pi(x)}{\pi_x(x)} \] και άρα η (5.12) γίνεται \(\pi(y)=\pi_x(y)\), για κάθε \(y\in\X\).\(\square\)
Παρατήρηση: Μια άμεση συνέπεια του Θεωρήματος 5.5 είναι ότι, αν οι καταστάσεις \(x,y\) ανήκουν σε μια γνησίως επαναληπτική κλάση \({C}\), τότε \(\pi_x\equiv\pi_y\). Έχει λοιπόν νόημα να μιλάμε για την μοναδική αναλλοίωτη κατανομή \(\pi_{C}\) που αντιστοιχεί στην κλάση \({C}\). Το τελικό συμπέρασμα αυτής της παραγράφου είναι ότι κάθε αναλλοίωτη κατανομή είναι ένας κυρτός συνδυασμός τέτοιων κατανομών.
Απόδειξη: Ας υποθέσουμε πρώτα ότι \(\pi=\sum_{C\in{\cal R}}\alpha(C)\pi_C\) με \(\alpha(C)\ge 0\) και \(\sum_{C\in{\cal R}}\alpha(C)=1\). Είναι φανερό ότι \(\pi(x)\ge 0\) για κάθε \(x\in\X\) ενώ \[ \sum_{x\in\X}\pi(x)=\sum_{x\in\X}\sum_{C\in{\cal R}}\alpha(C)\pi_C(x)=\sum_{C\in{\cal R}}\alpha(C)\sum_{x\in\X}\pi_C(x)=\sum_{C\in{\cal R}}\alpha(C)=1. \] Επομένως \(\pi\in\MX\). Για να δείξουμε ότι \(\pi\in\IP\) και άρα \(co\{\pi_{C}: {C}\in{\cal R}\}\subset\IP\) παρατηρούμε ότι \[ \pi P=\Big(\sum_{C\in{\cal R}}\alpha(C)\pi_C\Big)P=\sum_{C\in{\cal R}}\alpha(C)(\pi_CP)=\sum_{C\in{\cal R}}\alpha(C)\pi_C=\pi. \] Θα δείξουμε τώρα ότι \(\IP\subset co\{\pi_{C}: {C}\in{\cal R}\}\). Για \(\mu\in\IP\) και \(C\in{\cal R}\) τέτοια ώστε \(\mu[C]>0\), θεωρούμε τον περιορισμό \(\left.\mu\right|_C\) του \(\mu\) στην κλάση \(C\). Συγκεκριμένα, για κάθε \(A\subset\X\) έχουμε \[ \left.\mu\right|_C\big[A\big]=\mu\big[A\,|\,C\big]=\frac{\mu\big[A\cap C\big]}{\mu\big[C\big]}. \] Θα δείξουμε ότι \(\left.\mu\right|_C=\pi_C\). Η \(\left.\mu\right|_C\) είναι μια κατανομή που στηρίζεται στην κλειστή κλάση \(C\) και, από το Θεώρημα 5.5, για να την ταυτίσουμε με την \(\pi_C\), αρκεί να δείξουμε ότι είναι αναλλοίωτη. Πράγματι, για κάθε \(x\in C\) έχουμε \(p(y,x)=0\) για κάθε \(y\notin C\) και άρα \[ \left.\mu\right|_C(x)=\frac{\mu(x)}{\mu\big[C\big]}=\frac{1}{\mu\big[C\big]}\sum_{y\in\X}\mu(y)p(y,x)=\sum_{y\in C}\frac{\mu(y)}{\mu\big[C\big]}p(y,x)=\sum_{y\in C}\left.\mu\right|_C(y)p(y,x). \] Δείξαμε λοιπόν ότι αν \(\mu\big[C\big]>0\), τότε \(\left.\mu\right|_C\equiv\pi_C\). Αν \(\mu\big[C\big]=0\), ορίζουμε \(\left.\mu\right|_C=\pi_C\). Από το Πόρισμα 5.1 έχουμε ότι \[ \mu\big[\bigcup_{C\in{\cal R}}C\big] = 1. \] Έτσι, για κάθε \(A\subset\X\) \[ \mu\big[A\big]=\mu\Big[\bigcup_{C\in{\cal R}}(A\cap C)\Big]=\sum_{C\in{\cal R}}\mu\big[A\cap C]=\sum_{C\in{\cal R}}\mu\big[C\big]\left.\mu\right|_C\big[A\big]=\sum_{C\in{\cal R}}\mu\big[C\big]\pi_C\big[A\big] \] και άρα \[ \mu=\sum_{C\in{\cal R}}\mu\big[C\big]\pi_C\, . \] Παρατηρήστε ότι \(\mu\big[C\big]\ge 0\) για κάθε \(C\in{\cal R}\) και \(\sum_{C\in{\cal R}}\mu\big[C\big]=\mu\big[\bigcup_{C\in{\cal R}}C\big] = 1.\) Έχουμε γράψει το \(\mu\) ως κυρτό συνδυασμό των \(\pi_C\), άρα \(\IP\subset co\{\pi_{C}: {C}\in{\cal R}\}\).
\(\square\)
Στην προηγούμενη παράγραφο μελετήσαμε τη δομή των αναλλοίωτων κατανομών μιας μαρκοβιανής αλυσίδας. Είδαμε ότι, για κάθε γνησίως επαναληπτική κλάση \(C\), υπάρχει μια μοναδική αναλλοίωτη κατανομή \(\pi_C\) της αλυσίδας που στηρίζεται στη \(C\) (δηλαδή \(x\notin C\Rightarrow \pi_C(x)=0\)) και ότι κάθε αναλλοίωτη κατανομή της αλυσίδας μπορεί να γραφτεί ως κυρτός συνδυασμός των κατανομών \(\pi_C\). Είδαμε όμως και αρκετούς τρόπους για να χαρακτηρίσουμε τις \(\pi_C\). Έτσι, αν έχουμε μια μη υποβιβάσιμη γνησίως επαναληπτική μαρκοβιανή αλυσίδα \(\xn\) με πίνακα πιθανοτήτων μετάβασης \(P\) (όπως είναι οποιαδήποτε μαρκοβιανή αλυσίδα περιορισμένη σε μια γνησίως επαναληπτική της κλάση), έχουμε τους ακόλουθους χαρακτηρισμούς για τη μοναδική αναλλοίωτη κατανομή της \(\pi\).
Μπορεί κανείς να χρησιμοποιήσει έναν τρόπο για να υπολογίσει την αναλλοίωτη κατανομή της αλυσίδας και να πάρει από τους άλλους τρόπους ενδεχομένως χρήσιμες πληροφορίες.
\(\square\)
Το προηγούμενο παράδειγμα μπορεί να γενικευτεί κατά τον
ακόλουθο τρόπο. Θα λέμε ότι ένας στοχαστικός πίνακας \(P\) είναι
διπλά στοχαστικός αν \(\sum_{x\in\X}p(x,y)=1\) για κάθε \(y\in\X\).
Έτσι σε έναν διπλά στοχαστικό πίνακα, εκτός από το άθροισμα των στοιχείων του κατά γραμμή, και το άθροισμα των στοιχείων του
κατά στήλη είναι ίσο με 1. Παρατηρήστε ότι ένας συμμετρικός πίνακας
πιθανοτήτων μετάβασης είναι πάντα διπλά στοχαστικός.
\(\square\)
\begin{align} \pi(ABC)&=p\pi(ABC)+p\pi(BAC)+p\pi(BCA)\\ \pi(ACB)&=p\pi(ACB)+p\pi(CAB)+p\pi(CBA). \end{align}
Αν \(S_A=\{ABC,ACB\},\) προσθέτοντας κατά μέλη βρίσκουμε \(\pi(S_A)=p\sum_{x\in\X}\pi(x)=p.\) Όμοια, αν \(\ S_B=\{BAC,BCA\}\) και \(\ S_C=\{CAB,CBA\}\), τότε \(\pi(S_B)=q,\ \pi(S_C)=r\). Από τις (5.13), (5.14) παίρνουμε τελικά ότι
\begin{equation} \pi(ABC)=\frac{p}{1-p} \pi(S_B)=\frac{pq}{1-p} \qquad\text{και}\qquad \pi(ACB)=\frac{p}{1-p}\pi(S_C)=\frac{pr}{1-p}. \end{equation} Οι πιθανότητες των άλλων καταστάσεων βρίσκονται με ανάλογο τρόπο, οπότε τελικά \[ \pi=(\frac{pq}{1-p}, \frac{rp}{1-r}, \frac{qr}{1-q}, \frac{qp}{1-q}, \frac{pr}{1-p}, \frac{rq}{1-r}). \] Έχοντας βρει την αναλλοίωτη κατανομή της αλυσίδας, μπορούμε εύκολα να απαντήσουμε τα υπόλοιπα ερωτήματα. Έτσι, αν \(T_{ABC}^+=\inf\{k>0: X_k=ABC\}\), τότε \[ \E\big[T_{ABC}^+\,|\,X_0=ABC\big]=\frac{1}{\pi(ABC)}=\frac{1-p}{pq}. \] Κάθε φορά που διαβάζετε το βιβλίο Calculus το τοποθετείτε αριστερά οπότε η αλυσίδα περνά από μία από της καταστάσεις του \(S_C\). Έτσι, \[ \E \Big[ \sum_{k=1}^{ T_{ ABC }^+ } 1\!\!1 \big \{ X_k \in S_C \big \} \, \Big | \, X_0 = ABC \Big] = \frac{ \pi[S_C] }{ \pi(ABC) }= \frac{ (1-p) r }{ pq }.\qquad \]
\(\square\)
Ας θεωρήσουμε μια μαρκοβιανή αλυσίδα \(\{X_n\}_{n\in\N_0}\) που εξελίσσεται σε έναν αριθμήσιμο χώρο καταστάσεων \(\X\) και βρίσκεται στην κατάσταση ισορροπίας της με κατανομή \(\pi\). Όπως έχουμε εξηγήσει, η κατάσταση ισορροπίας μιας μαρκοβιανής αλυσίδας είναι μια κατάσταση δυναμικής ισορροπίας. Η αλυσίδα εξελίσσεται στον χρόνο αλλά με τέτοιο τρόπο ώστε η κατανομή της να μένει σταθερή. Ας κάνουμε τώρα το ακόλουθο νοητικό πείραμα. Ας υποθέσουμε πως κινηματογραφούμε την αλυσίδα για κάποιο χρόνο και έπειτα αναπαράγουμε την ταινία που τραβήξαμε ανάποδα. Πώς μοιάζει η δυναμική της αλυσίδας όταν ο χρόνος κυλάει ανάποδα; Την απάντηση σε αυτό το ερώτημα δίνει το παρακάτω θεώρημα.
\begin{equation} \hat{p}(x,y)=\frac{\pi(y)}{\pi(x)}\ p(y,x),\ \forall x,y\in\X. \end{equation}
Απόδειξη: Οι \(\hat{p}\) είναι καλά ορισμένες, αφού, όπως έχουμε δει, για την αναλλοίωτη κατανομή \(\pi\) μιας στάσιμης αλυσίδας έχουμε \(\pi(x)>0\), για κάθε \(x\in\X\). Επίσης, είναι πιθανότητες μετάβασης, αφού \(\hat{p}(x,y)\ge 0\) για κάθε \(x,y\in\X\), ενώ \[ \sum_{y\in\X}\hat{p}(x,y)=\frac{1}{\pi(x)}\sum_{y\in\X}\pi(y)p(y,x)=1, \quad\forall x\in\X, \] αφού η \(\pi(\cdot)\) είναι αναλλοίωτη κατανομή για τη \(\{X_n\}_n\). Θα δούμε τώρα ότι οι \(\hat{p}\) είναι οι πιθανότητες μετάβασης για την \(\{Y_n\}\). Πράγματι, για \(k\in\{1,2,\ldots,N\}\), έχουμε \begin{align*} &\P\big[Y_0=y_0,\ Y_1=y_1,\ \ldots,\ Y_k=y_k\big] =\P\big[X_{N-k}=y_k,\ \ldots, X_{N-1}=y_1,\ X_N=y_0\big]\\ &\qquad\qquad =\P\big[X_{N-k}=y_k\big]\ \P\big[X_{N-k+1}=y_{k-1} |X_{N-k}=y_k\big]\cdots\P\big[X_N=y_0\ | X_{N-1}=y_1\big]\\ &\qquad\qquad = \pi(y_k)\ p(y_k,y_{k-1})\cdots \ p(y_1,y_0)=\pi(y_0)\ \hat{p}(y_0,y_1)\cdots\ \hat{p}(y_{k-1},y_k), \end{align*} όπου η τελευταία ισότητα προκύπτει από τον ορισμό (5.16) των \(\hat{p}\). Τέλος, για κάθε \(x\in\X\), έχουμε \[ \sum_{y\in\X}\pi(y)\ \hat{p}(y,x)=\pi(x)\sum_{y\in\X}p(x,y)=\pi(x), \] άρα η κατανομή \(\pi\) είναι αναλλοίωτη για την \(\{Y_n\}_n\) και, εφόσον η κατανομή της \(Y_k=X_{N-k}\) για κάθε \(k\in\{1,2,\ldots,N\}\) είναι \(\pi\), η \(\{Y_n\}_n\) είναι στάσιμη. \(\quad \Box\) Αν η κατανομή \(\pi\) ικανοποιεί την
\begin{equation} \pi(x)\ p(x,y)=\pi(y)\ p(y,x),\quad \forall x,y \in \X, \end{equation}
τότε, από τη σχέση (5.16), έχουμε ότι
\(\hat{p}=p\) και άρα η \(\{Y_n\}_n\), η χρονική αντιστροφή της
\(\{X_n\}_n\), έχει την ίδια στάσιμη κατανομή και τις ίδιες πιθανότητες
μετάβασης όπως και η \(\{X_n\}_n\). Με άλλα λόγια, αν κινηματογραφήσουμε
τη \(\{X_n\}_n\), δεν θα μπορούμε με την αναπαραγωγή του φιλμ να
διακρίνουμε τη φορά του χρόνου. Όταν ικανοποιείται h (5.17), λέμε ότι η
κατανομή \(\pi\) και οι πιθανότητες μετάβασης \(p\) βρίσκονται σε
ακριβή ισορροπία (detailed balance) και ότι η αλυσίδα είναι
χρονικά αντιστρέψιμη (time reversible).
Τα περισσότερα ενδιαφέροντα φυσικά συστήματα ικανοποιούν τις
συνθήκες ακριβούς ισορροπίας (5.17). Ένας από
τους λόγους για τους οποίους οι συνθήκες αυτές είναι ιδιαίτερα χρήσιμες
είναι ότι, όταν ικανοποιούνται, μας επιτρέπουν να εντοπίσουμε μια
αναλλοίωτη κατανομή \(\pi\) πιο εύκολα από τις συνθήκες ορισμού της
\begin{equation} \pi(x)=\sum_{y\in\X}\pi(y)\ p(y,x),\quad\forall x\in \X. \end{equation}
Πράγματι, όπως φαίνεται από την (5.17), οδηγούν σε
απλούστερες εξισώσεις για την \(\pi\), που σύμφωνα με το ακόλουθο Λήμμα
όταν έχουν λύση, αυτή είναι πάντα αναλλοίωτη κατανομή.
Απόδειξη: Για κάθε \(x\in\X\) έχουμε \[ \sum_{ y \in \X } \pi (y) p (y, x) \stackrel{(5.17)}{=} \sum_{ y \in \X } \pi(x) \ p(x,y) = \pi (x) \sum_{ y \in \X } p(x,y) = \pi (x). \quad\Box \]
Αν \(\{X_n\}_{n\in\N_0}\) είναι η μαρκοβιανή αλυσίδα στον χώρο
καταστάσεων \(\X=\{0,1,\ldots,N\}\) που περιγράφει το πλήθος των
σωματιδίων στο διαμέρισμα Α, τότε οι πιθανότητες μετάβασης αυτής της
αλυσίδας είναι \[ p(k,k+1)=\frac{N-k}{N} \quad \text{και}\quad
p(k,k-1)=\frac{k}{N}, \quad\forall k\in\X. \] Πράγματι, για να αυξηθεί
κατά 1 το πλήθος των σωματιδίων στο διαμέρισμα Α θα πρέπει να
επιλέξουμε ένα από τα σωματίδια του διαμερίσματος Β για να του
αλλάξουμε διαμέρισμα. Αν στο διαμέρισμα Α υπάρχουν \(k\) σωματίδια, τότε
στο διαμέρισμα Β υπάρχουν \(N-k\) και άρα η πιθανότητα να επιλέξουμε
ένα από τα σωματίδια του Β είναι \(\frac{N-k}{N}\). Ομοίως για να
μειωθεί κατά 1 το πλήθος των σωματιδίων στο διαμέρισμα Α θα πρέπει το
σωματίδιο που θα επιλέξουμε για να του αλλάξουμε διαμέρισμα να
προέρχεται από το Α, ενδεχόμενο που έχει πιθανότητα \(\frac{k}{N}\)
όταν στο Α υπάρχουν \(k\) σωματίδια.
Είναι φανερό ότι η \(\{X_n\}_n\) είναι μη υποβιβάσιμη και άρα
θα έχει μοναδική αναλλοίωτη κατανομή \(\pi\). Αν επιχειρήσουμε να
προσδιορίσουμε την \(\pi\) από τις εξισώσεις (5.18), θα οδηγηθούμε
σε μια μη γραμμική αναδρομική εξίσωση δεύτερης τάξης που θέλει αρκετό
κόπο για να λυθεί. Δοκιμάστε το για εξάσκηση. Αν αντίθετα επιχειρήσουμε
να βρούμε κάποια κατανομή \(\pi\) στον \(\X\) που βρίσκεται σε ακριβή
ισορροπία με τις πιθανότητες μετάβασης \(p\), θα πάρουμε τις εξισώσεις
\[ \pi(k)\ p(k,k+1)=\pi(k+1)\ p(k+1,k)\quad k\in\{0,1,\ldots,N-1\}, \]
ή ισοδύναμα \[ \frac{\pi(k+1)}{\pi(k)}=\frac{N-k}{k}\quad
k\in\{0,1,\ldots,N-1\}. \] Πολλαπλασιάζοντας τις σχέσεις αυτές για
\(k=0,1,\ldots,n-1\) λαμβάνουμε ότι \[ \pi(n)=\pi(0){N\choose
n},\quad\forall n\in\X, \] ενώ από τη συνθήκη κανονικοποίησης
\(\displaystyle\sum_{n\in\X}\pi(n)=1\) έχουμε ότι
\(\displaystyle\pi(0)\sum_{n=0}^N{N\choose n}=\pi(0)2^N=1\). Επομένως,
\[ \pi(n)=2^{-N}{N\choose n},\quad\forall n\in\X.\quad\Box \]
Αν ο περιπατητής μας βρίσκεται σε μια κορυφή \(x\in V\) με βαθμό \(v(x)\), τότε όλες οι \(v(x)\) κορυφές που συνδέονται με την κορυφή \(x\) είναι ισοπίθανες ως επόμενος προορισμός. Επομένως, αν \(E\) είναι το σύνολο των ακμών του γράφου, οι πιθανότητες μετάβασης της αλυσίδας δίνονται από την
\begin{equation} p(x,y)=\begin{cases} \frac{1}{v(x)},&\text{ αν } (x,y)\in E\\0, &\text{ αν } (x,y)\notin E.\end{cases} \end{equation}
Εφόσον ο γράφος είναι συνεκτικός (ανάμεσα σε οποιεσδήποτε δυο κορυφές υπάρχει ένα μονοπάτι, του οποίου οι διαδοχικές κορυφές συνδέονται με ακμές), η αλυσίδα είναι μη υποβιβάσιμη και έχει επομένως μοναδική αναλλοίωτη κατανομή \(\pi\), την οποία θέλουμε να προσδιορίσουμε. Από την (5.19) προκύπτει άμεσα ότι \[ v(x)\ p(x,y)=v(y)\ p(y,x)=\chi_E(x,y), \quad\forall x,y\in V, \] όπου \(\chi_E(x,y)=1\) αν \((x,y)\in E\) και 0 διαφορετικά. Επομένως, αν για κάποια σταθερά \(c\) έχουμε \(\pi(x)=cv(x),\ \forall x\in V\), τότε η \(\pi\) βρίσκεται σε ακριβή ισορροπία με τις πιθανότητες μετάβασης \(p\). Η σταθερά \(c\) θα προσδιοριστεί από τη συνθήκη κανονικοποίησης \[ 1=\sum_{x\in V}\pi(x)=c\sum_{x\in V}v(x)=2c|E|, \] όπου \(|E|\) είναι το πλήθος των ακμών του γράφου. Η τελευταία ισότητα προκύπτει γιατί κάθε ακμή προστίθεται στο άθροισμα δύο φορές, μία για κάθε κορυφή στην οποία καταλήγει. Άρα
\[ \pi(x)=\frac{v(x)}{2|E|},\quad \forall x\in V.\quad \Box \]Ένας ακόμα πολύ σημαντικός λόγος για τον οποίο οι συνθήκες ακριβούς ισορροπίας είναι πολύ χρήσιμες είναι ότι μας δίνουν τη δυνατότητα να κατασκευάσουμε μια μαρκοβιανή αλυσίδα με επιθυμητή αναλλοίωτη κατανομή, όπως θα δούμε παρακάτω στον αλγόριθμο Metropolis-Hastings.
a,b = np.polyfit(newx,newy,1)
print "The fitted line is y=%.2f*x+%.2f " % (a,b)
ώστε αυτές να μετατραπούν από σχόλια σε μέρος του εκτελέσιμου προγράμματος.
H πρώτη υπολογίζει τους συντελεστές της ευθείας \(y=ax+b\) που
προσαρμόζεται καλύτερα στα σημεία
(newx,newy). Η παράμετρος 1 δηλώνει ότι θέλουμε να προσαρμόσουμε ένα
πολυώνυμο βαθμού 1, δηλαδή μια ευθεία. Η δεύτερη γραμμή απλά τυπώνει
το αποτέλεσμα (με δύο δεκαδικά ψηφία) για τον χρήστη. Ξανατρέξτε το
πρόγραμμα. sample_mean = float(sum(mcestimates)) / M
squared_distance_from_mean = [ (e - sample_mean)**2 for
e in mcestimates ]
sample_variance= float(sum (squared_distance_from_mean)) / (M-1)
που βρίσκονται στο τέλος του προγράμματος.