3.1 Εισαγωγή

Είδαμε στο προηγούμενο κεφάλαιο πώς μπορούμε να διαμερίσουμε τον χώρο καταστάσεων μιας μαρκοβιανής αλυσίδας σε κλάσεις επικοινωνίας και πώς μπορούμε να ταξινομήσουμε τις κλάσεις αυτές σε ανοιχτές και κλειστές. Είδαμε επίσης ότι, αν η αλυσίδα ξεκινήσει ή βρεθεί κάποια στιγμή σε μία από τις κλειστές κλάσεις, τότε θα παραμείνει σε αυτήν για πάντα. Αν η αλυσίδα ξεκινά από μια ανοιχτή κλάση και υπάρχουν περισσότερες από μία κλειστές κλάσεις, ποια είναι η πιθανότητα να απορροφηθεί από καθεμία από τις κλειστές κλάσεις; Και πόσο χρόνο θα πάρει μέχρι να συμβεί αυτό; Αυτά είναι ερωτήματα που θα μπορέσουμε να απαντήσουμε με τις τεχνικές που θα μάθουμε στο παρόν κεφάλαιο. Παρόμοιο υλικό μπορείτε να βρείτε και στις αναφορές [Bremaud99] και [Norris98] και στην ελληνική βιβλιογραφία στη [Χρυσαφίνου12] .

3.2 Πιθανότητες απορρόφησης

Θεωρούμε μια μαρκοβιανή αλυσίδα \(\xn\) με τιμές σ' έναν χώρο καταστάσεων \(\X\) και πιθανότητες μετάβασης \(p(\cdot,\cdot)\). Θεωρούμε ακόμα ένα σύνολο \(A\subset\X\) και ορίζουμε τον χρόνο πρώτης άφιξης στο \(A\) την τυχαία μεταβλητή \(T_A:\Omega\to\N_0\cup\{+\infty\}\) με \[ T_A(\omega)=\inf\{k\ge 0: X_k(\omega)\in A\}. \]

Όταν το σύνολο \(Α\) είναι ένα μονοσύνολο \(\{x\}\), θα συμβολίζουμε εναλλακτικά τον χρόνο άφιξης στο \(Α\) και ως \(T_x\).

Όπως στο παραπάνω παράδειγμα, μας ενδιαφέρει συχνά το εξής πρόβλημα: αν \(A,B\subset\X\) με \(A\cap B=\emptyset\) και \(X_0=x\notin A\cup B\), ποια είναι η πιθανότητα \(\PP { T_A < T_B \, |\, X_0 = x } = \Px{ T_A < T_B } \); Παρότι το πρόβλημα που έχουμε να λύσουμε απαιτεί τον υπολογισμό ενός αριθμού, είναι πιο εύκολο να λύσουμε ένα φαινομενικά πολυπλοκότερο πρόβλημα, του οποίου το αρχικό μας πρόβλημα αποτελεί μέρος. Συγκεκριμένα, θα αναζητήσουμε την τιμή αυτής της πιθανότητας ταυτόχρονα για όλα τα \(x \in \X \). Θα θεωρήσουμε λοιπόν αυτή την πιθανότητα ως μια συνάρτηση της αρχικής κατάστασης

\begin{equation} \Phi_{A,B} (x) = \Px{ T_A < T_B }. \end{equation}

Για λόγους που θα εξηγήσουμε στη συνέχεια η συνάρτηση αυτή καλείται συχνά συνάρτηση δυναμικού (potential) από το \(A\) στο \(B\). Όπως και στην περίπτωση του χρόνου πρώτης άφιξης, αν το \(A\) είναι μονοσύνολο με \(A=\{u\}\), θα συμβολίζουμε το δυναμικό \(\Phi_{\{u\},B}\) και ως \(\Phi_{u,B}\). Aντίστοιχα θα κάνουμε στην περίπτωση που το \(B\) είναι μονοσύνολο. Ορίζουμε επίσης τον γεννήτορα \(L\) της αλυσίδας ως έναν τελεστή που δρα σε συναρτήσεις \(h:\X\to\R\) επιστρέφοντας μια καινούργια συνάρτηση \(Lh:\X\to\R\) με τύπο \[ Lh(x)=\sum_{y\in\X} p(x,y) \big(h(y)-h(x)\big),\qquad \text{για κάθε }x\in\X. \]

Απόδειξη: Αν \(x\in A\), στο ενδεχόμενο \(\{\omega: X_0(\omega)=x\}\) έχουμε \(T_A(\omega)=\inf\{k\ge 0: X_k(\omega)\in A\}=0\), ενώ \(T_B(\omega)>0\), αφού \(A\cap B=\emptyset\). Eπομένως, \[ x \in A \Rightarrow \Phi_{A,B} (x) = \Px{ T_A < T_B } = 1. \] Με εντελώς αντίστοιχο τρόπο έχουμε ότι \(x \in B \Rightarrow \Phi_{A,B}(x)= \Px{ T_A < T_B } = 0.\)

Έστω τώρα \(x\notin A\cup B\). Θα επιχειρήσουμε να υπολογίσουμε την \(\Px{ T_A < T_B } \) κάνοντας ανάλυση πρώτου βήματος. Αυτό πολύ απλά σημαίνει ότι θα εφαρμόσουμε τον τύπο της ολικής πιθανότητας για τη διαμέριση του \(\Omega\) που επάγει το πρώτο βήμα της αλυσίδας, \[ \Omega = \bigcup_{ y \in \X} \{ X_1 =y \}. \] Συγκεκριμένα, \begin{align*} \Phi_{ A, B} (x) &= \Px{ T_A < T_B } = \sum_{ y \in \X } \PP{ X_1=y \, | \, X_0 = x } \times \PP{ T_A < T_B\, | \, X_0=x, X_1=y}\\ &=\sum_{ y \in \X } p(x,y) \ \PP{ T_A^+ < T_B^+ \, | \, X_0=x, X_1=y }, \end{align*} όπου \(T_A^+(\omega)=\inf\{k\ge 1: X_k(\omega)\in A\}\) και αντίστοιχα ορίζεται ο \(T_B^+\). Προσέξτε ότι η διαφορά του \(T_A\) από τον \(T_A^+\) έγκειται στο ότι για τον μεν \(T_A\) εξετάζουμε αν η αλυσίδα είναι αρχικά στο \(Α\), ενώ για τον \(T_A^+\) όχι. Στην τελευταία ισότητα παραπάνω, αντικαταστήσαμε το ενδεχόμενο \(\{ T_A < T_B \} \) από το \(\{ T_A^+ < T_B^+ \} \), γιατί για \(x \notin A\cup B\) στο ενδεχόμενο \(\{ X_0 = x \}\) έχουμε \(Τ_A(\omega) = T_A^+ (\omega) \) και \(Τ_B(\omega)= T_B^+ (\omega)\). Όμως από τη μαρκοβιανή ιδιότητα έχουμε \begin{align*} \PP{ T_A^+ < T_B^+ \, | & X_0=x, X_1=y} = \PP{ T_A^+ < T_B^+ \,| X_1=y}\\ &=\PP{ T_A < T_B \, | \, X_0 = y } = \Phi_{A,B}(y), \end{align*} αφού η \(\{Y_n\}_{n\in\N_0}\) με \(Y_n=X_{n+1}\) είναι μια μαρκοβιανή αλυσίδα με τις ίδιες πιθανότητες μετάβασης όπως η \(\xn\), ενώ \(T_A^+=\inf\{k\ge 0: Y_n\in A\}+1\) και αντίστοιχα \(T_B^+=\inf\{k\ge 0: Y_n\in B\}+1\). Έχουμε λοιπόν ότι για \(x\notin A\cup B\)

\begin{equation} \Phi_{A,B}(x)=\sum_{y\in\X}p(x,y)\ \Phi_{A,B}(y)\Leftrightarrow L\Phi_{A,B}(x)=0. \end{equation}

\(\square\)

Παρατήρηση: Στην περίπτωση των μαρκοβιανών αλυσίδων με διακριτό χώρο καταστάσεων \(\X\), το ΠΣΤ (3.2) δεν είναι παρά ένα σύστημα από τόσες γραμμικές εξισώσεις, όσες και οι καταστάσεις στο \((A\cup B)^c\). Τόσες είναι και οι τιμές της \(\Phi_{A,B}\) που ψάχνουμε, αφού για \(x\in A\), έχουμε \(\Phi_{A,B}(x)=1\), ενώ για \(x\in B\) έχουμε \(\Phi_{A,B}(x)=0\). Όπως θα δούμε στο επόμενο κεφάλαιο, αν ο \(\X\) είναι πεπερασμένος και το σύνολο \((A\cup B)\) είναι προσβάσιμο από κάθε σημείο του \((A\cup B)^c,\) τότε το ΠΣΤ (3.2) έχει πάντα μοναδική λύση, κάτι που μας επιτρέπει να υπολογίσουμε την \(\Phi_{A,B}\), όπως θα δούμε στα επόμενα παραδείγματα.

Παράδειγμα 3.2 Στο Παράδειγμα 3.1 ας υποθέσουμε ότι η πιθανότητα νίκης του παίκτη Α σε κάθε πόντο είναι \(p\), ενώ η πιθανότητα νίκης του παίκτη Β είναι \(q\), ανεξάρτητα από το αποτέλεσμα των άλλων πόντων. Ο πίνακας πιθανοτήτων μετάβασης της αλυσίδας είναι επομένως o

Aς υποθέσουμε ότι αυτή τη στιγμή το γκέιμ είναι ισόπαλο, δηλαδή \(X_0=\iota\). Θα υπολογίσουμε την πιθανότητα να είναι νικητής του γκέιμ ο παίκτης Α ως συνάρτηση του \(p\), δηλαδή τη \[ \Phi_{A,B}(\iota) = \PP{ T_A < T_B \, | \, X_0 = \iota }. \]

Από το Θεώρημα 3.1 έχουμε ότι η \(\Phi_{A,B}\) λύνει το ΠΣΤ (3.2). Αν \(h:\X\to\R\) είναι μια λύση αυτού του προβλήματος, θα πρέπει \(h(A)=1,\ h(B)=0\), ενώ γράφοντας την εξίσωση \(Lh(x)=0\) διαδοχικά για \(x=\alpha,\iota,\beta\) έχουμε: \begin{eqnarray*} &x=\alpha: &\qquad h(\alpha)=ph(A)+(1-p)h(\iota)=p+(1-p)h(\iota)\\ &x=\iota: & \qquad h(\iota)=ph(\alpha)+(1-p)h(\beta)\\ &x=\beta: & \qquad h(\beta)=ph(\iota)+(1-p)h(B)=ph(\iota). \end{eqnarray*} Λύνοντας τις παραπάνω εξισώσεις βρίσκουμε ότι το σύστημα έχει μοναδική λύση την \[ h(\alpha)=\frac{p(1-p+p^2)}{p^2+(1-p)^2},\quad h(\iota)=\frac{p^2}{p^2+(1-p)^2}, \quad h(\beta)=\frac{p^3}{p^2+(1-p)^2} \] και άρα \(\displaystyle \Phi_{A,B}(\iota)=\frac{p^2}{p^2+(1-p)^2}\).

\(\square\)

Παράδειγμα 3.3

Δύο παίκτες Α,Β στρίβουν ένα τίμιο κέρμα μέχρι να εμφανιστεί η ακολουθία κεφαλή-γράμματα-κεφαλή (ΚΓΚ) ή να έρθουν τρεις διαδοχικές φορές γράμματα (ΓΓΓ). Στην πρώτη περίπτωση νικητής αναδεικνύεται ο Α, ενώ στη δεύτερη περίπτωση ο Β. Ποια είναι η πιθανότητα νίκης κάθε παίκτη;

Όπως στο Παράδειγμα 1.6, θα περιγράψουμε την κατάσταση του παιχνιδιού χρησιμοποιώντας το αποτέλεσμα των δύο τελευταίων στριψιμάτων και δύο ακόμα καταστάσεις \(Α,Β\), που θα αντιστοιχούν σε νίκη του παίκτη Α και σε νίκη του παίκτη Β. Πιο συγκεκριμένα, μπορούμε να περιγράψουμε το παιχνίδι μας ως μια μαρκοβιανή αλυσίδα στον χώρο καταστάσεων \[\X=\{KK,K\Gamma,\Gamma K,\Gamma\Gamma,A,B\}.\] Εάν για παράδειγμα κάποια στιγμή η αλυσίδα βρεθεί στην κατάσταση \(\Gamma K\), αυτό σημαίνει ότι καμία από τις δύο ακολουθίες τερματισμού δεν έχει εμφανιστεί ακόμη, ενώ τα δύο τελευταία στριψίματα ήταν γράμματα (το προτελευταίο) και κεφαλή (το τελευταίο). Σε αυτή την περίπτωση η επόμενη κατάσταση της αλυσίδας μπορεί να είναι είτε η \(ΚΚ\) (με πιθανότητα 1/2), αν φέρουμε κεφαλή στο επόμενο στρίψιμο, είτε η \(Κ\Gamma\) (με πιθανότητα 1/2), αν φέρουμε γράμματα. Αν κάποια στιγμή η αλυσίδα βρεθεί στην κατάσταση \(K\Gamma\), τότε η επόμενη κατάστασή της θα είναι είτε η \(\Gamma\Gamma\), αν φέρουμε γράμματα, είτε η \(Α\), αν φέρουμε κεφαλή, αφού σε αυτή την περίπτωση θα έχει σχηματιστεί η ακολουθία κεφαλή-γράμματα-κεφαλή και το παιχνίδι θα έχει τελειώσει με νικητή τον Α. Με παρόμοιους συλλογισμούς μπορούμε να γράψουμε τον πίνακα πιθανοτήτων μετάβασης αυτής της αλυσίδας.

Η αρχική κατάσταση αυτής της αλυσίδας εξαρτάται από τα αποτελέσματα των δύο πρώτων στριψιμάτων. Επειδή στρίβουμε ένα τίμιο κέρμα, καθεμία από τις καταστάσεις \(KK, K\Gamma,\Gamma K,\Gamma\Gamma\) έχει πιθανότητα 1/4 να είναι η αρχική κατάσταση της αλυσίδας. Μπορούμε λοιπόν από τον τύπο της ολικής πιθανότητας να γράψουμε

\begin{align} \PP{ T_A < T_B } &= \sum_{ x \in \X } \PP{ T_A < T_B \, | \, X_0=x} \PP{ X_0= x } \notag\\ &= \frac{1}{4} \Big(\Phi_{A,B}(KK) + \Phi_{A,B}(K \Gamma) + \Phi_{A,B}(\Gamma K) + \Phi_{A,B}(\Gamma \Gamma) \Big). \end{align}

Αρκεί λοιπόν να βρούμε τη συνάρτηση δυναμικού \(\Phi_{A,B}\), κάτι που μπορούμε να κάνουμε με τη βοήθεια του Θεωρήματος 3.1. Έστω \(h:\X\to\R\) μία λύση του ΠΣΤ (2). Τότε θα έχουμε \(h(A)=1,\ h(B)=0\), ενώ η εξίσωση \(Lh(x)=0\) για \(x=KK,K\Gamma,\Gamma K,\Gamma\Gamma\) δίνει αντίστοιχα: \begin{eqnarray*} &x=ΚΚ: &\qquad h(ΚΚ)=\half h(KK)+\half h(K\Gamma)\Leftrightarrow h(KK)= h(K\Gamma)\\ &x=K\Gamma: & \qquad h(K\Gamma)=\half h(A)+\half h(\Gamma\Gamma)\Leftrightarrow 2h(K\Gamma)=1+h(\Gamma\Gamma)\\ &x=\Gamma K: & \qquad h(\Gamma K)=\half h(KK)+\half h(K\Gamma)\\ &x=\Gamma\Gamma: & \qquad h(\Gamma\Gamma)=\half h(\Gamma K)+\half h(B)\Leftrightarrow h(\Gamma K)=2h(\Gamma\Gamma). \end{eqnarray*} To σύστημα των τεσσάρων αυτών εξισώσεων έχει μοναδική λύση την \[ h(KK)=h(K\Gamma)=h(\Gamma K)=\frac{2}{3} \quad \text{και}\quad h(\Gamma\Gamma)=\frac{1}{3}, \] οπότε από τη σχέση (3.4) λαμβάνουμε ότι \(\displaystyle \PP{ T_A < T_B }= \frac{7}{12} \). Μπορείτε να βρείτε μια διαισθητική εξήγηση, γιατί η πιθανότητα αυτή είναι μεγαλύτερη από 1/2, γιατί δηλαδή είναι πιο πιθανό να εμφανιστεί πρώτα η ακολουθία ΚΓΚ παρά η ακολουθία ΓΓΓ;

\(\square\)

Η περιουσία σας στο συγκεκριμένο παιχνίδι μπορεί να περιγραφεί από μια μαρκοβιανή αλυσίδα στον χώρο καταστάσεων \(\X=\{0,1,2,\ldots,N\}\). Σε κάθε γύρο είτε θα κερδίσετε (με πιθανότητα \(p\)) και η περιουσία σας θα αυξηθεί κατά 1, είτε θα χάσετε (με πιθανότητα \(1-p\)) και η περιουσία σας θα μειωθεί κατά 1. Επομένως αν \(z\in\{1,2,\ldots,N-1\}\), οι πιθανότητες μετάβασης αυτής της αλυσίδας είναι \[ p(z,z+1)=p,\quad p(z,z-1)=1-p, \quad p(z,w)=0, \text{ για } |z-w|\neq 1. \] Αν ορίσουμε \(T_u=\inf\{k\ge 0: X_k=u\}\) τον χρόνο πρώτης άφιξης στην κατάσταση \(u\), τότε το ενδεχόμενο νίκης σας είναι το \(\{ T_N < T_0 \} \), επομένως ψάχνουμε την πιθανότητα \(\Px{ T_N < T_0 } = \Phi_{ N, 0}(x)\). Από την (3.2) έχουμε ότι για \(z\in\{1,2,\ldots,N-1\}\) \begin{align*} 0=L\Phi_{N,0}(z)&=\sum_{u\in\X} p(z,u)\big(\Phi_{N,0}(u)-\Phi_{N,0}(z)\big)\\ &=p\big(\Phi_{N,0}(z+1)-\Phi_{N,0}(z)\big)+(1-p)(\Phi_{N,0}(z-1)-\Phi_{N,0}(z)\big). \end{align*} Ξαναγράφουμε την παραπάνω σχέση ως

\begin{equation} \Phi_{N,0}(z+1)-\Phi_{N,0}(z)= \frac{1-p}{p}\ \big(\Phi_{N,0}(z)-\Phi_{N,0}(z-1)\big),\quad z\in\{1,2,\ldots,N-1\}. \end{equation}

Στην περίπτωση όπου \(p=\frac{1}{2}\) η (3.5) σημαίνει ότι η \(\{\Phi_{N,0}(n)\}_{n\in\X}\) είναι μια αριθμητική πρόοδος και άρα \[ \Phi_{N,0}(n)=\Phi_{N,0}(0)+ cn=cn, \quad \text{για } n\in\X. \] Η διαφορά της προόδου \(c\) μπορεί να βρεθεί θέτοντας \(n=N\) στην παραπάνω σχέση, οπότε \[ 1=cN\Rightarrow c=\frac{1}{N} \] και άρα

\begin{equation} \Phi_{N,0}(x)=\frac{x}{N}. \end{equation}

Επομένως, όταν το παιχνίδι είναι δίκαιο, η πιθανότητα νίκης σας σε αυτό είναι απλά το κλάσμα της αρχικής σας περιουσίας στη συνολική περιουσία.

Αν τώρα έχουμε \(p\neq \frac{1}{2}\), η (3.5) δίνει ότι η \(\Phi_{N,0}(n+1)-\Phi_{N,0}(n)\) είναι γεωμετρική πρόοδος, άρα \[ \Phi_{N,0}(n+1)-\Phi_{N,0}(n)=\Big(\frac{1-p}{p}\Big)^n\big(\Phi_{N,0}(1)-\Phi_{N,0}(0)\big)=\Big(\frac{1-p}{p}\Big)^n\Phi_{N,0}(1) ,\quad\text{για } n=0,1,\ldots,N-1. \] Προσθέτοντας κατά μέλη τις παραπάνω σχέσεις για \(n=0,1,\ldots,z-1\), το άθροισμα στο αριστερό μέλος τηλεσκοπεί, ενώ στο δεξί μέλος έχουμε το άθροισμα των \(z\) πρώτων όρων μιας γεωμετρικής προόδου με λόγο \((1-p)/p\), οπότε παίρνουμε

\begin{equation} \Phi_{N,0}(z)=\frac{\big(\frac{1-p}{p}\big)^z-1}{\frac{1-p}{p}-1}\Phi_{N,0}(1)=\frac{p}{1-2p}\Big(\big(\frac{1-p}{p}\big)^z-1\Big)\Phi_{N,0}(1),\quad z\in\X. \end{equation}

Η \(\Phi_{N,0}(1)\) μπορεί τώρα να υπολογιστεί από την τελική συνθήκη \(\Phi_{N,0}(N)=1\) επιλέγοντας \(z=N\) στην (3.7). Συγκεκριμένα, \[ 1=\Phi_{N,0}(N)=1=\frac{p}{1-2p}\Big(\big(\frac{1-p}{p}\big)^N-1\Big)\Phi_{N,0}(1). \] Αντικαθιστώντας την τιμή που προκύπτει για την \(\Phi_{N,0}(1)\) πίσω στην (3.7) βρίσκουμε ότι

\begin{equation} \Phi_{N,0}(x)=\frac{\big(\frac{1-p}{p}\big)^x-1}{\big(\frac{1-p}{p}\big)^N-1}\ . \end{equation}

Παρατηρήστε ότι αν \(p<1/2\), αν δηλαδή το παιχνίδι που παίζουμε είναι εις βάρος μας, τότε \(\frac{1-p}{p}>1\) και από τη στοιχειώδη ανισότητα \[ \frac{ \alpha^n -1 }{ \alpha^N -1 } \leq \alpha^{n-N} \quad \text{ για } \alpha \neq 1, n \le N \] έχουμε ότι \[ \Px{ T_N < T_0 } \leq \big(\frac{ 1-p }{ p } \big)^{ x-N }. \]

H πιθανότητα νίκης πέφτει λοιπόν εκθετικά με την αρχική περιουσία του αντιπάλου σας. Αξίζει τον κόπο να συγκρίνουμε τα αποτελέσματα των (3.6) και (3.8) για διάφορες τιμές του \(p\). Παίρνοντας \(N=100\) και \( x=50\) βρίσκουμε ότι αν \(p=4/10\), η πιθανότητα νίκης μας είναι μικρότερη από \(10^{-8}\), αν \(p=1/2\), η πιθανότητα νίκης μας είναι ακριβώς 1/2, ενώ αν \(p=6/10\), η πιθανότητα νίκης μας είναι μεγαλύτερη από \(1-10^{-8}\).

Παρατήρηση: Αν στο Θεώρημα 1 πάρουμε την ειδική περίπτωση \(B=\emptyset\), τότε η συνθήκη \(A\cap B=\emptyset\) ικανοποιείται αυτόματα. Επιπλέον,

Ας θυμηθούμε σ' αυτό το σημείο τη σχέση (2.10). Το να μπορούμε να υπολογίζουμε την πιθανότητα \(\P_y\big[T_x<\infty\big]\) μας επιτρέπει να αποφανθούμε αν μια κατάσταση είναι επαναληπτική ή παροδική. Παρότι σε πεπερασμένους χώρους καταστάσεων το ερώτημα αυτό είναι εύκολο να απαντηθεί, όπως είδαμε στο Παράδειγμα 2.9, τα πράγματα περιπλέκονται. Ας δούμε τώρα πώς μπορούμε να ξαναβρούμε το αποτέλεσμα εκείνου του παραδείγματος, χρησιμοποιώντας τις μεθόδους αυτού του κεφαλαίου.

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

\(\Box\)

Στα παραδείγματα που είδαμε ως τώρα τα ΠΣΤ (3.2) και (3.9) είχαν μοναδική λύση και προσδιόριζαν επομένως τη συνάρτηση δυναμικού. Στην περίπτωση που τα παραπάνω ΠΣΤ έχουν περισσότερες από μία λύσεις, θα θέλαμε να έχουμε ένα κριτήριο που να μας επιτρέπει να επιλέγουμε εκείνη που μας ενδιαφέρει, δηλαδή τη συνάρτηση δυναμικού. Είναι πολλές φορές εύκολο να απορρίψουμε κάποιες λύσεις γιατί π.χ. παίρνουν αρνητικές τιμές, ενώ η συνάρτηση δυναμικού είναι εξ ορισμού μη αρνητική. Κι αυτό όμως δεν είναι πάντα αρκετό, γιατί τα ΠΣΤ ενδέχεται να έχουν περισσότερες από μία μη αρνητικές λύσεις. Το ακόλουθο θεώρημα είναι χρήσιμο σε τέτοιες περιπτώσεις.

Απόδειξη: Ο ισχυρισμός ισχύει κατά τετριμμένο τρόπο, αν \(x\in A\), οπότε \(\Phi_{A,B}(x)=w(x)=1\), ή \(x\in B\), οπότε \(\Phi_{A,B}(x)=w(x)=0\). Αν πάλι \(x\notin A\cup B\), τότε από την (3.2) έχουμε

\begin{equation} 0=Lw(x)\Leftrightarrow w(x)=\sum_{y\in\X}p(x,y)w(y). \end{equation}

Χωρίζοντας τους προσθετέους στο παραπάνω άθροισμα ανάλογα με το αν η \(y\) είναι στα \(A,B\) ή στο \((A\cup B)^c\) και χρησιμοποιώντας τις συνοριακές συνθήκες για την \(w\) στα \(A,B\) παίρνουμε \begin{align*} w(x) &= \sum_{ y \in A} p(x,y) w(y) + \sum_{ y \in B} p(x,y) w(y) + \sum_{ y \notin A \cup B} p(x,y) w(y) \\ &=\sum_{y\in A} p(x,y)+0+\sum_{y\notin A\cup B}p(x,y)w(y)\\ &=\Px{ 1 = T_A < T_B} + \sum_{ y \notin A\cup B} p(x,y) w(y). \end{align*} Εφόσον το τελευταίο άθροισμα εκτείνεται σε όρους \(y\notin A\cup B\) μπορούμε να γράψουμε την \(w(y)\) με τη βοήθεια της (3.11) ώστε να πάρουμε \begin{align*} w(x) &= \Px{ 1 = T_A < T_B }+\sum_{ y \notin A \cup B \atop z \in \X} p(x,y) p(y,z) w(z)\\ &=\Px{ 1= T_A < T_B }+\sum_{y \notin A\cup B \atop z\in A} p(x,y) p(y,z)+ \sum_{y, z \notin A \cup B} p(x,y) p(y,z) w(z)\\ &=\Px{ 1 = T_A < T_B} + \Px{ 2 = T_A < T_B}+\sum_{y, z \notin A \cup B} p(x,y) p(y,z) w(z)\\ &=\Px{ T_A \le 2, \ T_A < T_B }+\sum_{ y, z \notin A \cup B} p(x,y) p(y,z) w(z). \end{align*} Επαναλαμβάνοντας το παραπάνω επιχείρημα \(n\) φορές, λαμβάνουμε \begin{align*} w(x)&=\Px{ T_A \le n,\ T_A < T_B }+ \sum_{ x_1, \ldots, x_n \notin A\cup B} p(x,x_1) p(x_1,x_2) \cdots p(x_{n-1},x_n) w(x_n)\\ &\ge \Px{ T_A \le n , \ T_A < T_B }, \end{align*} αφού η \(w\) παίρνει μη αρνητικές τιμές. Η παραπάνω ανισότητα ισχύει για κάθε \(n \in \N \), ενώ τα ενδεχόμενα \(R_n = \{ T_A \le n \} \cap \{ T_A < T_B \} \) σχηματίζουν μια αύξουσα ακολουθία ενδεχομένων. Παίρνοντας το όριο καθώς \(n\to\infty\) έχουμε \begin{align*} w(x)&\ge \lim_{n\to\infty}\Px{ T_A \le n,\ T_A < T_B}\\ &=\Px{ \bigcup_n\{ T_A \le n\}\cap \{ T_A < T_B \}}\\ &=\Px{ T_A < T_B } = \Phi_{A,B}(x). \end{align*} Επομένως, σε κάθε περίπτωση το δυναμικό \(\Phi_{A,B}(x)\) είναι μικρότερο από οποιαδήποτε μη αρνητική λύση της (3.2).

\(\square\)

3.3 Στατιστικά του χρόνου άφιξης

Ας υποθέσουμε ότι το σύνολο \(A\subset\X\) είναι τέτοιο ώστε \(\Px{T_A<+\infty}=1\). Μπορούμε να πούμε κάτι παραπάνω για την κατανομή του χρόνου άφιξης στο \(A\); Ποια είναι η αναμενόμενη τιμή του; Η κατανομή του; Σε αυτή την παράγραφο θα δούμε ότι μπορούμε να απαντήσουμε σε τέτοια ερωτήματα με μεθόδους ανάλογες με αυτές που αναπτύξαμε στην προηγούμενη παράγραφο.

Απόδειξη: Ας θεωρήσουμε μια \(g:\X\to[0,\infty)\) που λύνει το (3.13).

Αν \(x\in A\), τότε \(T_A(\omega)=0\) για κάθε \(\omega\) στο ενδεχόμενο \(\{X_0=x\}\). Επομένως, \(G_A(x)=0=g(x)\).

Έστω τώρα \(x\notin A\). Tότε μπορούμε να γράψουμε την \(Lg(x)=-1\) ως \begin{equation} g(x)=\sum_{y\in\X} p(x,y)g(y)+1=\sum_{y\notin A}p(x,y)g(y)+1, \end{equation} όπου η τελευταία ισότητα προκύπτει από τη συνοριακή συνθήκη για την \(g\) στο \(A\). Επαναλαμβάνοντας το προηγούμενο επιχείρημα έχουμε \begin{align*} g(x)&=1+\sum_{y\notin A}p(x,y)\Big(\sum_{z\notin A}p(y,z)g(z)+1\Big)\\ &=1+\sum_{y\notin A}p(x,y)+\sum_{y,z\notin A}p(x,y)p(y,z)g(z)\\ &=1+\sum_{y\notin A}p(x,y)+\sum_{y,z\notin A}p(x,y)p(y,z)\Big(\sum_{u\notin A}p(z,u)g(u)+1\Big)\\ &=1+\sum_{y\notin A}p(x,y)+\sum_{y,z\notin A}p(x,y)p(y,z)+\sum_{y,z,u\notin A} p(x,y)p(y,z)p(z,u)g(u)\\ &=\Px{T_A>0}+\Px{T_A>1}+\Px{T_A>2}+\sum_{y,z,u\notin A} p(x,y)p(y,z)p(z,u)g(u). \end{align*} Έπειτα από \(n\in\N\) επαναλήψεις καταλήγουμε στην \begin{align*} g(x)&=\sum_{k=0}^{n-1}\Px{T_A>k}+\sum_{x_1,\ldots,x_n\notin A}p(x,x_1)p(x_1,x_2)\cdots p(x_{n-1},x_n)g(x_n)\\ &\ge \sum_{k=0}^{n-1}\Px{T_A>k}, \end{align*} αφού η \(g\) παίρνει μη αρνητικές τιμές. Παίρνοντας το όριο \(n\to\infty\) έχουμε \[ g(x)\ge\sum_{k=0}^\infty\Px{T_A>k}=\Ex{T_A}=G_A(x). \] Αποδείξαμε ως τώρα ότι αν το (3.13) έχει μία μη αρνητική και πεπερασμένη λύση \(g\), τότε \(G_A(x)\le g(x)<+\infty\) για κάθε \(x\in\X\). Μένει να αποδείξουμε ότι η \(G_A\) λύνει και αυτή το ΠΣΤ (3.13). Με ανάλυση πρώτου βήματος έχουμε διαδοχικά

\begin{align} G_A(x)&=\Ex{T_A}=\sum_{y\in\X}\PP{X_1=y\,|\,X_0=x}\EE{T_A\,|\,X_0=x,\, X_1=y}\notag\\ &=\sum_{y\in\X}p(x,y)\ \EE{T_A^+\,|\,X_0=x,\, X_1=y}, \end{align}

\begin{align} G_A(x)&=\sum_{y\in\X} p(x,y) \EE{T_A^+|X_1=y}=\sum_{y\in\X}p(x,y)) \EE{T_A+1|Y_0=y}\notag\\ &=\sum_{y\in\X}p(x,y) \big(G_A(y)+1\big)=1+\sum_{y\in\X}p(x,y) G_A(y). \end{align}

\(\square\)

Παράδειγμα 3.9 Ποιος είναι ο αναμενόμενος αριθμός ζαριών που πρέπει να ρίξουμε με ένα τίμιο ζάρι μέχρι να εμφανιστούν τέσσερα διαδοχικά εξάρια; Μέχρι να εμφανιστεί για πρώτη φορά η ακολουθία 6,5,4,3;

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

Μπορούμε να περιγράψουμε το πρώτο πείραμα με μια μαρκοβιανή αλυσίδα στο σύνολο \(\X=\N_0\). Διαισθητικά, η κατάσταση της αλυσίδας θα δείχνει το τρέχον σερί μας από εξάρια. Πιο συγκεκριμένα, αν \(\{\zeta_n\}_{n\in\N}\) είναι τα αποτελέσματα των ζαριών μας μπορούμε να ορίσουμε \(X_0=0\), ενώ για \(n\in\N\) να θέσουμε \[ X_n=k\Leftrightarrow \zeta_{n-k}\neq 6\quad\text{και}\quad \zeta_j=6, \text{ για κάθε } j\in\{n-k+1,\ldots,n\}. \] Διαπιστώνει κανείς ότι η \(\{X_n\}_n\) είναι μια μαρκοβιανή αλυσίδα με πιθανότητες μετάβασης \[ p(k,k+1)=\frac{1}{6}\quad\text{και}\quad p(k,0)=\frac{5}{6},\quad\text{για κάθε }k\in\N_0. \] Πράγματι, αν έχουμε ήδη σχηματίσει ένα σερί από \(k\) εξάρια και αν στην επόμενη ζαριά μας φέρουμε 6, τότε το σερί μας θα διευρυνθεί σε \(k+1\), ενώ αν φέρουμε οτιδήποτε άλλο, το τρέχον σερί μας θα πέσει στο μηδέν. Με τον συμβολισμό που αναπτύξαμε, αν ορίσουμε \[ Τ_4=\inf\{n\ge 0:\ X_n=4\} \] τότε η απάντηση στο ερώτημά μας είναι η \(\EE{T_4\,|\,X_0=0}\). Θα υπολογίσουμε αυτή την αναμενόμενη τιμή λύνοντας το ΠΣΤ \[ \begin{cases} \quad Lg(x)=-1, & \text{ αν } x\in \{0,1,2,3\} \\ \quad g(x)=0, &\text{ αν } x=4.\end{cases} \] Γράφουμε τις εξισώσεις που προκύπτουν διαδοχικά για \(x=0,1,2,3\). \begin{eqnarray*} &x=0:& g(0)=\frac{1}{6}g(1)+\frac{5}{6}g(0)+1\\ &x=1:& g(1)=\frac{1}{6}g(2)+\frac{5}{6}g(0)+1\\ &x=2:& g(2)=\frac{1}{6}g(3)+\frac{5}{6}g(0)+1\\ &x=3:& g(3)=\frac{1}{6}g(4)+\frac{5}{6}g(0)+1=\frac{5}{6}g(0)+1. \end{eqnarray*} Το παραπάνω σύστημα έχει μοναδική λύση \(g(0)=1.554,\ g(1)=1.548,\ g(2)=1.512,\ g(3)=1.296\), επομένως από το Θεώρημα 3.3 θα έχουμε \[ \EE { T_4 \, | \, X_0 = 0 } = 1.554. \] Σε ό,τι αφορά στο δεύτερο πείραμα, μπορούμε πάλι να το περιγράψουμε με τη βοήθεια μιας μαρκοβιανής αλυσίδας στον χώρο \(\X=\{0,1,2,3,4\}\) που θα μας δείχνει πόσα από τα ψηφία της ακολουθίας-στόχου έχουμε σχηματίσει. Την πρώτη φορά που θα εμφανιστεί η ακολουθία ζαριών 6,5,4,3 η αλυσίδα αυτή θα φτάσει για πρώτη φορά στην κατάσταση 4 και θα παραμείνει στην κατάσταση αυτή εφεξής. Δεν είναι δύσκολο να βρει κανείς τον πίνακα πιθανοτήτων μετάβασης της αλυσίδας

Για παράδειγμα, αν κάποια στιγμή η αλυσίδα είναι στην κατάσταση 2, αυτό σημαίνει ότι η προτελευταία ζαριά ήταν 6, ενώ η τελευταία 5. Αν στην επόμενη ζαριά φέρουμε 4 (πιθανότητα 1/6) η επόμενη κατάσταση της αλυσίδας θα είναι η 3, αφού θα έχουμε σχηματίσει 3 από τα 4 ψηφία της ακολουθίας στόχου. Αν φέρουμε 6 (πιθανότητα 1/6) τότε το σερί μας θα έχει σπάσει, αλλά θα έχουμε ήδη έτοιμο το πρώτο ψηφίο (6) της ακολουθίας στόχου, οπότε επόμενη κατάσταση της αλυσίδας θα είναι η 1. Αν τέλος φέρουμε 1, 2, 3, ή 5 (πιθανότητα 2/3), η επόμενη κατάσταση της αλυσίδας θα είναι το 0. Με ανάλογα επιχειρήματα μπορεί κανείς να γεμίσει και τις υπόλοιπες γραμμές του πίνακα πιθανοτήτων μετάβασης. Όπως και πριν, η \(\EE{T_4\,|\,X_0=0}\) μπορεί να βρεθεί λύνοντας το ΠΣΤ \[ \begin{cases} \quad Lg(x)=-1, & \text{ αν } x\in \{0,1,2,3\} \\ \quad g(x)=0, &\text{ αν } x=4.\end{cases} \] Γράφουμε τις εξισώσεις που προκύπτουν διαδοχικά για \(x=0,1,2,3\). \begin{eqnarray*} &x=0:& g(0)=\frac{1}{6}g(1)+\frac{5}{6}g(0)+1\\ &x=1:& g(1)=\frac{1}{6}g(2)+\frac{1}{6}g(1)+\frac{2}{3}g(0)+1\\ &x=2:& g(2)=\frac{1}{6}g(3)+\frac{1}{6}g(1)+\frac{2}{3}g(0)+1\\ &x=3:& g(3)=\frac{1}{6}g(4)+\frac{1}{6}g(1)+\frac{2}{3}g(0)+1=\frac{1}{6}g(1)+\frac{2}{3}g(0)+1. \end{eqnarray*} Το παραπάνω σύστημα έχει μοναδική λύση \(g(0)=1.296,\ g(1)=1.290,\ g(2)=1.260,\ g(3)=1.080\), επομένως από το Θεώρημα 3.3 θα έχουμε \(\EE{ T_4 \, | \, X_0 = 0 } = 1.296.\)

\(\square\)

3.4 Ασκήσεις

Άσκηση 3.3 Δίνεται ο πίνακας πιθανοτήτων μετάβασης \(\mathbf{P}\) μιας μαρκοβιανής αλυσίδας στον \(\X=\{s_1,\ldots,s_5\},\ p\in(0,1)\) .

α) Αν \(T_i=\inf\{k\ge 0:\ X_k=s_i\}\) είναι ο χρόνος πρώτης άφιξης στην κατάσταση \(s_i\), υπολογίστε την πιθανότητα \[ \P \big [ T_1 < T_5 \ | \ X_0 = s_3 \big ].\] β) Αν έχετε ένα κέρμα που φέρνει κορώνα με πιθανότητα \(p\neq 1/2\), μπορείτε με τη βοήθεια της παραπάνω αλυσίδας να φτιάξετε έναν αλγόριθμο που μιμείται το στρίψιμο ενός τίμιου κέρματος; Συγκεκριμένα θέλουμε ο αλγόριθμος να τερματίζει με πιθανότητα 1 σε πεπερασμένο χρόνο και με πιθανότητα 1/2 σε καθεμία από τις δύο δυνατές τελικές καταστάσεις.

Άσκηση 3.4 Ένα διωνυμικό δέντρο με ρίζα είναι ένας άπειρος γράφος, χωρίς κλειστά μονοπάτια, με μία διακεκριμένη κορυφή \(R\) (τη ρίζα) από την οποία διέρχεται μία ακμή, ενώ από κάθε άλλη κορυφή του διέρχονται τρεις ακμές όπως στο διπλανό σχήμα. Ένας τυχαίος περίπατος σ' αυτόν το γράφο είναι μια μαρκοβιανή αλυσίδα στο σύνολο \(V\) των κορυφών του γράφου, που επιλέγει σε κάθε βήμα τυχαία μία από τις κορυφές με τις οποίες συνδέεται με ακμή και μετακινείται εκεί. Αν ξεκινήσουμε από την κορυφή που συνδέεται με τη ρίζα, ποια είναι η πιθανότητα να φτάσουμε κάποια στιγμή στη ρίζα; Είναι αυτός ο περίπατος παροδικός ή επαναληπτικός;

Άσκηση 3.9 Απαντήστε τα παρακάτω ερωτήματα για τη μαρκοβιανή αλυσίδα της Άσκησης 1.6.
α) Αν αρχικά ο ρήγας βρίσκεται στο κέντρο, ποια είναι η πιθανότητα να βρίσκεται στο κέντρο μετά από 4 βήματα;
β) Αν αρχικά ο ρήγας είναι αριστερά, ποιος είναι ο αναμενόμενος αριθμός κινήσεων μέχρι να βρεθεί για πρώτη φορά δεξιά;

Άσκηση 3.10 Θεωρούμε μια μαρκοβιανή αλυσίδα \(\{X_n\}\) στον \(\X=\N\) με πιθανότητες μετάβασης \[ p_{k,k-1}=\frac{k-1}{2k}=\frac{1}{2}-\frac{1}{2k},\ p_{k,k+1}=\frac{k+1}{2k}=\frac{1}{2}+\frac{1}{2k},\ \text{για}\ k\in\N. \] H \(X_n\) έχει μια τάση να πηγαίνει δεξιά αλλά η τάση αυτή εξασθενεί όσο απομακρινόμαστε από το 1, οπότε συμπεριφέρεται σχεδόν όπως ένας απλός, συμμετρικός τυχαίος περίπατος. Για τον απλό, συμμετρικό τυχαίο περίπατο γνωρίζουμε ότι απ' όπου κι αν ξεκινήσει θα φτάσει στο 1 με πιθανότητα 1. Αν \(T_1=\inf\{n\ge 0: X_n=1\}\) υπολογίστε την πιθανότητα \(\P_k\big[T_1<+\infty\big]\).

Άσκηση 3.11 Μια αράχνη κινείται τυχαία στον ιστό της, που αποτελείται από \(N\) ομόκεντρα εξάγωνα και τις ακτίνες τους. Πόσο χρόνο κατά μέσο όρο θα της πάρει για να φτάσει στο κέντρο του ιστού;

Άσκηση 3.12 Μια μαρκοβιανή αλυσίδα κινείται ανάμεσα σε έξι καταστάσεις. Οι δυνατές μεταβάσεις εικονίζονται σαν ακμές στο διπλανό σχήμα. Οι πιθανότητες μετάβασης είναι συμμετρικές, δηλ. \(p(x,y)=p(y,x)\) για κάθε \(x,y\in\{A,B,C,D,E,F\}\) και δίνονται και αυτές στο σχήμα. Π.χ. \(p(\{C,D\})=p(\{D,C\}) = \varepsilon \), με \(0 < \varepsilon < 1.\)
α) Ορίζουμε \(T_\varepsilon = \inf \big\{ m \ge 0: X_m\in\{D,E,F\} \big\} \) τον χρόνο εισόδου στο \(\{ D, E, F \} \). Υπολογίστε για \(x\in\{A,B,C\}\) την \(\E \big [\ T_\epsilon\ |\ X_0=x\big].\)
β) Υπολογίστε την \(\psi(x) =\E\big[e^{-s\varepsilon T_\varepsilon}\ | X_0=x\big ] \) για \(x=A,B,C\) και βρείτε ποιο είναι το όριό της, καθώς \(\varepsilon\to 0\). Συμπεράνετε ότι η τυχαία μεταβλητή \(\varepsilon T_\varepsilon\) συγκλίνει κατά κατανομή σε μια εκθετική τυχαία μεταβλητή, με ρυθμό \(\lambda=3\).

3.5 Αριθμητικά πειράματα

Για τις παρακάτω ασκήσεις μπορείτε να χρησιμοποιήσετε τη βασική ρουτίνα προσομοίωσης πεπερασμένων μαρκοβιανών αλυσίδων simple_markov_chain_lib.py , που είδαμε στο Kεφάλαιο 1. Χρησιμοποιήστε τη ρουτίνα αυτή ως βιβλιοθήκη, όπως κάναμε στον κώδικα ex1.py, ώστε να γράψετε κώδικες σε python που θα λύνουν αριθμητικά τα ακόλουθα προβλήματα.

3.6 Βιβλιογραφία

• [Norris98] Norris, James R. Markov chains.
  Cambridge series in statistical and probabilistic mathematics, Cambridge, UK. Cambridge University Press, 1998.
• [Bremaud99] Bremaud, Pierre. Markov chains : Gibbs fields, Monte Carlo simulation and queues.
  Texts in applied mathematics. Springer, New York, NY, 1999.
• [Χρυσαφίνου12] Ουρανία Χρυσαφίνου. Εισαγωγή στις Στοχαστικές Ανελίξεις, β' έκδοση.
  Σοφία, Θεσσαλονίκη, 2012.