2.1 Εισαγωγή

Σ' αυτό το κεφάλαιο θα αναλύσουμε τις βασικές ιδιότητες μιας μαρκοβιανής αλυσίδας. Θα δούμε πώς μπορούμε να βρούμε την κατανομή της κατάστασής της οποιαδήποτε χρονική στιγμή και πώς μπορούμε να απλοποιήσουμε την ανάλυση μιας μαρκοβιανής αλυσίδας, διαμερίζοντας τον χώρο καταστάσεων σε κλάσεις επικοινωνίας. Στη συνέχεια θα εισαγάγουμε την έννοια του χρόνου διακοπής και θα δείξουμε την ιδιότητα που έχουν οι μαρκοβιανές αλυσίδες να ανανεώνονται έπειτα από τέτοιους χρόνους, ξεχνώντας το παρελθόν τους. Τέλος, θα δούμε κάποιες βασικές ιδιότητες που έχουν οι τροχιές της αλυσίδας, όπως η επαναληπτικότητα και η παροδικότητα. Μια πολύ καλή αναφορά που περιέχει παρόμοιο υλικό είναι το [Norris98] . Για την προσομοίωση μαρκοβιανών αλυσίδων μπορείτε να δείτε και το [Haggstrom02] .

2.2 Πιθανότητες μετάβασης ανώτερης τάξης

Ας θεωρήσουμε μια μαρκοβιανή αλυσίδα \(\{X_n\}_{n\in\N_0}\) με τιμές σ' έναν αριθμήσιμο χώρο καταστάσεων \(\X\), που έχει αρχική κατανομή \(\pi_0\) και πίνακα πιθανοτήτων μετάβασης \(P=\{p(x,y)\}_{x,y\in\X}\). Ο στόχος μας σε αυτή την παράγραφο είναι να μάθουμε να υπολογίζουμε την κατανομή της κατάστασης της αλυσίδας \(X_n\), για κάθε \(n\in\N\).

Μπορούμε να αναγάγουμε τον υπολογισμό της κατανομής της \(X_{n+1}\) στον υπολογισμό της κατανομής της \(X_n\), χρησιμοποιώντας τον τύπο της ολικής πιθανότητας. Αν για \(n\in\N_0\) συμβολίζουμε με \(\pi_n\) τη σ.μ.π. της \(X_n\), τότε για κάθε \(y\in\X\) έχουμε

\begin{align} \pi_{n+1}(y)&=\PP{X_{n+1}=y}=\sum_{x\in\X}\PP{X_n=x}\PP{X_{n+1}=y\big|X_n=x}=\sum_{x\in\X} \pi_n(x)p(x,y). \end{align}

Παρατηρήστε ότι, αν o \(\X\) είναι πεπερασμένος, με \(\X=\{v_1,v_2,\ldots,v_N\}\), μπορούμε να αναπαριστούμε μια σ.κ.π. \(\pi\) ως ένα διάνυσμα γραμμή \[ \pi=\big(\pi(v_1),\pi(v_2),\ldots,\pi(v_N)\big) \] και τον πίνακα πιθανοτήτων μετάβασης \(P\) ως ένα \(N\times N\) τετραγωνικό πίνακα, όπως στην (1.7). Η (2.1) μας δίνει τότε ότι

\begin{equation} \pi_{n+1}=\pi_n P, \quad\text{για κάθε }n\in\N_0, \end{equation}

όπου η πράξη στο δεξί μέλος είναι ο συνήθης πολλαπλασμός πινάκων. Oρμώμενοι από αυτή την παρατήρηση, μπορούμε να ορίσουμε, για έναν αριθμήσιμο χώρο καταστάσεων \(\X\), τον πολλαπλασιαμό μιας σ.μ.π. \(\pi\) με ένα στοχαστικό πίνακα \(P=\{p(x,y)\}_{x,y\in\X}\), ως \[ \pi P(y)=\sum_{x\in\X}\pi(x)p(x,y), \quad\text{για κάθε } y\in\X. \] Το αποτέλεσμα αυτού του πολλαπλασιασμού είναι μια σ.κ.π., αφού \(\pi P(y)\ge 0\), για κάθε \(y\in\X\), ενώ χρησιμοποιώντας το θεώρημα Fubini-Tonelli για να εναλλάξουμε τα δύο αθροίσματα μη αρνητικών όρων \[ \sum_{y\in\X}\pi P(y)=\sum_{y\in\X}\sum_{x\in\X}\pi(x)p(x,y)=\sum_{x\in\X}\pi(x)\sum_{y\in\X}p(x,y)=\sum_{x\in\X}\pi(x)=1. \] Ανάλογα μπορούμε να ορίσουμε τον πολλαπλασιασμό δύο στοχαστικών πινάκων, \(P=\{p(x,y)\}_{x,y\in\X}\) και \(Q=\{q(x,y)\}_{x,y\in\X}\), ως \(PQ=\{r(x,y)\}_{x,y\in\X}\), με\[ r(x,y)=\sum_{z\in\X}p(x,z)q(z,y), \quad\text{για κάθε } y\in\X. \] Το αποτέλεσμα είναι ένας στοχαστικός πίνακας, αφού \(r(x,y)\ge 0\), για κάθε \(x,y\in\X\), ενώ από το Θεώρημα Fubini-Tonelli, για κάθε \(x\in\X\), έχουμε \[ \sum_{y\in\X} r(x,y)=\sum_{y\in\X}\sum_{z\in\X}p(x,z)q(z,y)=\sum_{z\in\X}p(x,z)\sum_{y\in\X}q(z,y)=\sum_{z\in\X}p(x,z)=1. \] Οι πράξεις αυτές γενικεύουν τον συνήθη πολλαπλασιασμό πινάκων και μπορεί εύκολα να ελεγχθεί ότι έχουν την προσεταιριστική ιδιότητα, δηλαδή \[ (\pi P)Q=\pi (PQ) \quad\text{και}\quad (PQ)R=P(QR) \] για κάθε σ.μ.π. \(\pi\) και οποιουσδήποτε στοχαστικούς πίνακες \(P,Q,R\). Ο στοχαστικός πίνακας \(I=\{i(x,y)\}_{x,y\in\X}\), με στοιχεία \(i(x,y)=\delta_x(y)\) είναι ταυτοτικό στοιχείο αυτού του πολλαπλασιασμού. Για κάθε στοχαστικό πίνακα \(P\), έχουμε \(PI=IP=P\).

Ορίζουμε τη δύναμη \(P^n=\{p^{(n)}(x,y)\}_{x,y\in\X}\) ενός στοχαστικού πίνακα \(P\) για \(n\in\N_0\) αναδρομικά ως εξής. \(P^0=Ι\) και \(P^n=P^{n-1}P\), για \(n\in\N\).

Με αυτούς τους ορισμούς η (2.2) παραμένει σε ισχύ ακόμα κι αν ο \(\X\) είναι άπειρος και εύκολα ελέγχεται επαγωγικά ότι

\begin{equation} \pi_n=\pi_0P^n. \end{equation}

Από τον ορισμό του πολλαπλασιασμού πινάκων,

\begin{equation} p^{(n)}(x,y)=\underset{x_1,\ldots,x_{n-1}\in\X}{\sum\cdots \sum} p(x,x_1)\cdots p(x_{n-1},y),\quad\text{για κάθε }x,y\in\X. \end{equation}

Με τη βοήθεια της προηγούμενης σχέσης η (2.3) γράφεται και ως \[ \pi_n(y)=\sum_{x_0\in\X}\pi_0(x_0)p^{(n)}(x_0,y)=\underset{x_0,\ldots,x_{n-1}\in\X}{\sum\cdots \sum}\pi_0(x_0)p(x_0,x_1)\cdots p(x_{n-1},y),\quad\text{για κάθε }y\in\X. \] Στην ίδια σχέση θα μπορούσαμε να είχαμε καταλήξει και από την (1.11). H \(\pi_n\) είναι η σ.μ.π. της \(X_n\), επομένως μπορεί να βρεθεί αθροίζοντας την από κοινού σ.μ.π. των \((X_0,X_1,\ldots,X_n)\) ως προς όλες τις τιμές που μπορούν να πάρουν οι \(X_0,X_1,\ldots,X_{n-1}\).

Ας θεωρήσουμε τώρα ένα \(k\in\N_0.\) Από τη μαρκοβιανή ιδιότητα (Θεώρημα 1.1), δεδομένου ότι \(X_k=x\), η διαδικασία \(\{X_{n+k}\}_{n\in\N_0}\) έχει αρχική κατανομή \(\delta_x\) και πίνακα πιθανοτήτων μετάβασης \(P\). Έτσι, η (2.3) δίνει ότι

\begin{equation} \PP{X_{n+k}=y\big|X_k=x}=p^{(n)}(x,y),\qquad\text{για κάθε }k\in\N_0,\ x,y\in\X. \end{equation}

Ορισμός: Αν ο \(P\) είναι ο πίνακας πιθανοτήτων μετάβασης μιας μαρκοβιανής αλυσίδας \(\{X_n\}_{n}\), ονομάζουμε τα στοιχεία \(p^{(n)}(x,y)\) του \(P^n\) πιθανότητες μετάβασης \(n\)- οστής τάξης της αλυσίδας.

Από την προσεταιριστική ιδιότητα του πολλαπλασιασμού έχουμε ότι \(P^{m+n}=P^mP^n\), για κάθε \(m,n\in\N_0\). Αν γράψουμε αυτή την ταυτότητα για τα στοιχεία των παραπάνω στοχαστικών πινάκων, παίρνουμε ότι οι πιθανότητες μετάβασης ανώτερης τάξης μιας μαρκοβιανής αλυσίδας ικανοποιούν τις εξισώσεις Chapman-Kolmogorov (Chapman-Kolmogorov equations):

\begin{equation} p^{(m+n)}(x,y)=\sum_{z\in\X}p^{(m)}(x,z)p^{(n)}(z,y),\qquad\text{για κάθε }m,n\in\N_0,\ x,y\in\X. \end{equation}

Λαμβάνοντας υπόψιν την (2.5), οι εξισώσεις Chapman-Kolmogorov είναι ο τύπος της ολικής πιθανότητας για το ενδεχόμενο \(\{X_{m+n}=y\}\), ανάλογα με την κατάσταση της αλυσίδας την ενδιάμεση χρονική στιγμή \(m\). Πράγματι, αν θυμηθούμε ότι η δεσμευμένη πιθανότητα \(\PP{\cdot\big|X_0=x}\) είναι κι αυτή ένα μέτρο πιθανότητας, τότε ο τύπος ολικής πιθανότητας δίνει \begin{align*} \PP{X_{m+n}=y\big|X_0=x}&=\sum_{z\in\X}\PP{X_m=z\big|X_0=x} \PP{X_{m+n}=y\big|X_m=z,X_0=x}\\ &=\sum_{z\in\X}\PP{X_m=z\big|X_0=x} \PP{X_{m+n}=y\big|X_m=z} \end{align*} από τη μαρκοβιανή ιδιότητα. Σύμφωνα με την (2.5), αυτές είναι ακριβώς οι εξισώσεις Chapman-Kolmogorov .

2.3 Δομή του χώρου των καταστάσεων

Σε αυτή την παράγραφο θα δούμε πώς μπορούμε να οργανώσουμε τις καταστάσεις του χώρου μιας μαρκοβιανής αλυσίδας έτσι ώστε να διευκολύνουμε την κατανόηση της συμπεριφοράς της. Θα δούμε ότι ο χώρος διαμερίζεται σε κλάσεις επικοινωνίας (communication classes) εντός των οποίων η αλυσίδα είναι πιο εύκολο να αναλυθεί. Ας θεωρήσουμε λοιπόν μια μαρκοβιανή αλυσίδα \(\{X_n\}_{n\in\N_0}\) στον χώρο καταστάσεων \(\X\) με πίνακα πιθανοτήτων μετάβασης \(P=\{p(x,y)\}_{x,y\in\X}\).

Ορισμός: Θα λέμε ότι η κατάσταση \(y\in\X\) είναι προσβάσιμη από την κατάσταση \(x\in\X\) και θα συμβολίζουμε \(x\to y\), αν υπάρχει \(n\ge 0\) τέτοιο ώστε \(p^{(n)}(x,y)>0\).

Ορισμός: Θα λέμε ότι δύο καταστάσεις \(x,y\in\X\) επικοινωνούν και θα συμβολίζουμε \(x\leftrightarrow y\), αν \(x\to y\) και \(y\to x\).

Πρόταση: Η σχέση \(\leftrightarrow\) είναι μια σχέση ισοδυναμίας, έχει δηλαδή τις παρακάτω ιδιότητες:

1. Αυτοπαθής: \(x\leftrightarrow x\), για κάθε \(x\in\X\).
2. Συμμετρική: \(x\leftrightarrow y\Rightarrow y\leftrightarrow x\), για κάθε \(x,y\in\X\).
3. Μεταβατική: \(\big(x \leftrightarrow u\) και \(u\leftrightarrow y \big)\Rightarrow x\leftrightarrow y\), για κάθε \(x,y,u\in\X\).

\(\Box\)

Ορισμός: Μια κλάση επικοινωνίας \({\cal C}\) θα λέγεται ανοιχτή, αν υπάρχουν καταστάσεις \(x\in{\cal C}\) και \(y\notin{\cal C}\) τέτοιες ώστε \(x\to y\). Αν μια κλάση δεν είναι ανοιχτή, θα λέγεται κλειστή .

Σύμφωνα με τον παραπάνω ορισμό, ανοιχτές είναι οι κλάσεις από τις οποίες η μαρκοβιανή αλυσίδα μπορεί να φύγει προς άλλες κλάσεις. Μάλιστα, αν η αλυσίδα φύγει από μια ανοιχτή κλάση, δεν μπορεί να ξαναγυρίσει σε αυτήν (Άσκηση 2.4). Αντίθετα, η αλυσίδα δεν μπορεί να φύγει από μια κλειστή κλάση. Αν η αλυσίδα ξεκινήσει ή βρεθεί, προϊόντος του χρόνου, σε μια κλειστή κλάση, θα παραμείνει σε αυτή την κλάση για πάντα. Αυτό μπορεί να απλοποιήσει την ανάλυση της αλυσίδας, αφού προκειμένου να καταλάβουμε τι θα συμβεί από τότε και μετά, αρκεί να μελετήσουμε την αλυσίδα περιορισμένη στην κλειστή κλάση.

Ορισμός: Μια μαρκοβιανή αλυσίδα λέγεται μη υποβιβάσιμη (irreducible), αν ολόκληρος ο χώρος καταστάσεων είναι μια (κλειστή αναγκαστικά) κλάση.

Παρατηρήστε ότι, αν περιορίσουμε μια μαρκοβιανή αλυσίδα σε μια κλειστή κλάση της \({\cal C}\), αν δηλαδή θεωρήσουμε τη μαρκοβιανή αλυσίδα με χώρο καταστάσεων την \({\cal C}\) και τις ίδιες πιθανότητες μετάβασης, αυτή η αλυσίδα είναι μη υποβιβάσιμη.

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

Παρατήρηση: Αν \(x,y\in\X\) και \(x\neq y\), τότε \(x\to y\), αν και μόνο αν υπάρχει μονοπάτι \[ x=x_0,x_1,x_2,\ldots,x_{n-1},x_n=y\in\X, \text{ τέτοιo ώστε } p(x_i,x_{i+1})>0, \text{ για } i=0,1,\ldots,n-1. \] Πράγματι, από την (2.4) έχουμε για κάθε \(n\in\N\) \[ p^{(n)}(x,y)=\underset{x_1,\ldots,x_{n-1}\in\X}{\sum\cdots \sum} p(x,x_1)\cdots p(x_{n-1},y). \] Επειδή όλοι οι προσθετέοι στο δεξί μέλος είναι μη αρνητικοί, έχουμε \(p^{(n)}(x,y)>0\), αν και μόνο αν κάποιος από αυτούς είναι αυστηρά θετικός. Αυτό όμως είναι προφανώς ισοδύναμο με τον ισχυρισμό της παρατήρησης.

Μπορούμε τώρα να κατασκευάσουμε έναν γράφο με κορυφές τα σημεία του \(\X\), προσθέτοντας την προσανατολισμένη ακμή από την \(u\) στην \(v\neq u\), όταν \(p(u,v)>0.\) Με βάση την παραπάνω παρατήρηση, μια κατάσταση \(y\) είναι προσβάσιμη από την \(x\), αν και μόνο αν υπάρχει προσανατολισμένο μονοπάτι του γράφου που οδηγεί από την \(x\) στην \(y\).

Παράδειγμα 2.3 Μια μαρκοβιανή αλυσίδα εξελίσσεται στον χώρο καταστάσεων \(\X=\{1,2,3,4,5,6,7,8\}\) και έχει πίνακα πιθανοτήτων μετάβασης \[ P=\left(\begin{array}{cccccccc}1/2&0&1/2&0&0&0&0&0\\1/4&1/4&0&1/2&0&0&0&0\\0&0&0&0&2/3&1/3&0&0\\ 0&0&0&1/2&0&0&1/2&0\\0&0&0&0&1/3&0&1/3&1/3\\0&1/6&1/6&0&1/2&0&1/6&0\\ 0&0&0&0&0&0&1/4&3/4\\0&0&0&0&1/2&0&0&1/2 \end{array}\right). \] Για να βρούμε τις κλάσεις επικοινωνίας της αλυσίδας, κατασκευάζουμε τον γράφο των δυνατών μεταβάσεων που περιγράψαμε παραπάνω, όπως στο Σχήμα 2.1. Έχουμε π.χ. \(1\to 2\), μέσω του μονοπατιού 1,3,6,2. Επίσης \(2\to 1\), άμεσα. Επομένως \(1\leftrightarrow 2\). Όμοια, βρίσκουμε ότι η κατάσταση 1 επικοινωνεί με τις 3 και 6, ενώ δεν επικοινωνεί με καμία άλλη κατάσταση. Άρα η κλάση επικοινωνίας που περιέχει την κατάσταση 1 είναι η \({\cal C}_1=\{1,2,3,6\}\). H κατάσταση 4 δεν επικοινωνεί με καμία άλλη, επομένως είναι το μόνο στοιχείο της κλάσης της \({\cal C}_2=\{4\}\). Τέλος, οι καταστάσεις 5,7 και 8 επικοινωνούν μεταξύ τους, και αποτελούν την κλάση \({\cal C}_3=\{5,7,8\}\). Έτσι, στο παράδειγμά μας, η διαμέριση του \(\X\) σε κλάσεις επικοινωνίας είναι \[ \X={\cal C}_1\cup{\cal C}_2\cup{\cal C}_3=\{1,2,3,6\}\cup\{4\}\cup\{5,7,8\}. \] Οι κλάσεις \({\cal C}_1\) και \({\cal C}_2\) είναι ανοιχτές, αφού \(6\to 7\) και \(4\to 7\), αντίστοιχα. Αντίθετα, η \({\cal C}_3\) είναι κλειστή.

\(\Box\)

2.4 Ισχυρή μαρκοβιανή ιδιότητα

Είδαμε στο Κεφάλαιο 1 ότι, αν γνωρίζουμε τη θέση \(x\in\X\) μιας μαρκοβιανής αλυσίδας κάποια χρονική στιγμή \(n\in\N_0\), από τότε και μετά η αλυσίδα θα εξελιχθεί ως μια μαρκοβιανή αλυσίδα που ξεκινά από το \(x\), έχει τις ίδιες πιθανότητες μετάβασης και είναι ανεξάρτητη από ό,τι έχει προηγηθεί. Η ιδιότητα αυτή συνεχίζει να ισχύει, αν αντικαταστήσουμε την καθορισμένη χρονική στιγμή \(n\) με οποιαδήποτε στρατηγική διακοπής \(T\) που δεν μπορεί να χρησιμοποιήσει πληροφορία από το μέλλον. Ονομάζουμε αυτές τις στρατηγικές χρόνους διακοπής και την ιδιότητα μιας μαρκοβιανής αλυσίδας να ανανεώνεται σε αυτούς τους χρόνους, ισχυρή μαρκοβιανή ιδιότητα (strong Markov property). Αυτές οι έννοιες είναι το αντικείμενο της παρούσας παραγράφου.

Θεωρήστε μια μαρκοβιανή αλυσίδα \(\{X_n\}_{n\in\N_0}\) με τιμές σ' έναν αριθμήσιμο χώρο καταστάσεων \(\X\).

Ορισμός: Θα λέμε ότι ένα ενδεχόμενο \(A\) ανήκει στην οικογένεια ενδεχομένων \(\F_n\), αν η δείκτρια συνάρτησή του \[ 1\!\!1_A(\omega)=\begin{cases} 1, &\text{ αν }\omega\in A\\ 0,& \text{ αν }\omega\notin A\end{cases} \] είναι μια συνάρτηση των \(X_0,X_1,\ldots,X_n\).

Με βάση τον παραπάνω ορισμό, ένα ενδεχόμενο \(A\) ανήκει στην κλάση \(\F_n\) όταν, προκειμένου να αποφασίσουμε αν συμβαίνει, αρκεί να ξέρουμε τις τιμές των \(X_0,X_1,\ldots,X_n\), δηλαδή την τροχιά της ανέλιξης μέχρι την στιγμή \(n\).

Πρόταση: Οι οικογένειες ενδεχομένων \(\{\F_n\}_{n\in\N_0}\) έχουν τις παρακάτω ιδιότητες:

1. Για κάθε \(n\in\N_0\) έχουμε \(\F_n\subset\F_{n+1}\).
2. \(\Omega\in\F_n\), για κάθε \(n\in\N_0\).
3. Αν \(A\in\F_n\), τότε \(A^c\in\F_n\).
4. Αν \(A,B\in\F_n\), τότε \(A\cap B\in\F_n\).
5. Αν \(A,B\in\F_n\), τότε \(A\cup B\in\F_n\).

Απόδειξη: Η (1) είναι προφανής, αφού μια συνάρτηση των \(X_0,\ldots,X_n\) είναι και συνάρτηση των \(X_0,\ldots,X_{n+1}\), που δεν εξαρτάται από την τελευταία μεταβλητή. Για την (2) παρατηρήστε ότι η \(1\!\!1_\Omega\) είναι σταθερή και ίση με 1, επομένως είναι (με τετριμμένο τρόπο) συνάρτηση των \(X_0,\ldots,X_n\) για κάθε \(n\in\N_0\). Η ιδιότητα (3) ισχύει γιατί \(1\!\!1_{A^c}=1-1\!\!1_A\), ενώ η (4) γιατί \(1\!\!1_{A\cap B}=1\!\!1_{A}1\!\!1_{B}.\) Τέλος, η (5) προκύπτει από την ταυτότητα \(A\cup B=(A^c\cap B^c)^c\) και τις ιδιότητες (3) και (4), που ήδη αποδείξαμε.

\(\Box\)

Μπορούμε να φανταζόμαστε έναν χρόνο διακοπής μιας μαρκοβιανής αλυσίδας ως μια στρατηγική σταματήματος της αλυσίδας που απαγορεύεται να δει το μέλλον. Η στρατηγική αυτή μπορεί να εξαρτάται από την τροχιά της αλυσίδας (αφού ένας χρόνος διακοπής είναι μια τυχαία μεταβλητή), αλλά ο ορισμός επιβάλλει ότι η απόφαση για το αν θα σταματήσουμε τη στιγμή \(n\) ή όχι, μπορεί να εξαρτάται μόνο από τις \(X_0,\ldots,X_n\) και όχι από τις μετέπειτα καταστάσεις της αλυσίδας.

Απόδειξη: Έστω ότι ο \(T\) είναι χρόνος διακοπής. Για κάθε \(n\in\N_0\) έχουμε \[ \{T\le n\}=\bigcup_{k=0}^n\{T=k\}. \] Όμως \(\{T=k\}\in\F_k\subset\F_n\), για \(k=0,1,\ldots,n\). Εφόσον η \(\F_n\) είναι κλειστή ως προς τις ενώσεις, έχουμε ότι \(\{T\le n\}\in\F_n\).

Για το αντίστροφο, ας υποθέσουμε ότι \(\{T\le n\}\in\F_n\), για κάθε \(n\in\N_0\). Έχουμε \(\{T=0\}=\{T\le 0\}\in\F_0\), ενώ για \(n\in\N\) \[ \{T=n\}=\{T\le n\}\cap \{T\le n-1\}^c\in\F_n, \] αφού όλες οι \(\F_n\) είναι κλειστές ως προς συμπληρώματα και τομές. Επομένως ο \(T\) είναι χρόνος διακοπής.

Απόδειξη: Ο ισχυρισμός προκύπτει άμεσα από το Λήμμα 2.1 και την κλειστότητα της \(\F_n\) σε ενώσεις και τομές, αφού \[ \{T\wedge S\le n\}=\{T\le n\}\cup\{S\le n\}\qquad\text{και}\qquad\{T\vee S\le n\}=\{T\le n\}\cap\{S\le n\}.\qquad\qquad\Box \] Θα εξετάσουμε τώρα την ισχυρή μαρκοβιανή ιδιότητα (strong Markov property) των μαρκοβιανών αλυσίδων, την ιδιότητά τους δηλαδή να ανανεώνονται έπειτα από κάθε χρόνο διακοπής και να εξελίσσονται ανεξάρτητα από το παρελθόν. Τι σημαίνει όμως το παρελθόν του χρόνου διακοπής; Αυτό δεν είναι σαφές, αφού ένας χρόνος διακοπής είναι μια τυχαία μεταβλητή, επομένως μπορεί να έχει διαφορετικές τιμές σε διαφορετικά σημεία του \(\Omega\).

Ορισμός: Αν \(T\) είναι ένας χρόνος διακοπής, θα λέμε ότι το ενδεχόμενο \(A\) ανήκει στο παρελθόν του \(T\) και θα συμβολίζουμε \(A\in\F_T\), αν για κάθε \(n\in\N_0\) το ενδεχόμενο \(A\cap\{T=n\}\) ανήκει στην \(\F_n\).

Σύμφωνα με τον παραπάνω ορισμό, ένα ενδεχόμενο \(A\) ανήκει στο παρελθόν του χρόνου διακοπής \(T\), αν στις εκβάσεις \(\omega\in\Omega\) που o \(T\) παίρνει την τιμή \(n\), μπορούμε να προσδιορίσουμε αν το \(A\) συμβαίνει, γνωρίζοντας μόνο τις καταστάσεις \(X_0,\ldots,X_n\).

Απόδειξη: Χρειάζεται να δείξουμε ότι για κάθε \(y=(y_0,\ldots,y_n)\in\X^{n+1}\) και κάθε \(A\in\F_T\), \[ \PP{\{(Y_0,\ldots,Y_n)=y\}\cap A\,\big|\,T<\infty,X_T=x}=\P_x\big[(X_0,\ldots,X_n)=y\big]\ \PP{A\,\big|\,T<\infty,X_T=x}. \] Έχουμε ότι \begin{align*} \PP{\{(Y_0,\ldots,Y_n)=y\}\cap A\cap&\{T<\infty,\, X_T=x\}}=\sum_{k=0}^\infty\PP{\{(Y_0,\ldots,Y_n)=y\}\cap A\cap\{T=k,X_k=x\}}\\ &=\ \sum_{k=0}^\infty\PP{\{(X_k,\ldots,X_{k+n})=y\}\cap A\cap\{T=k\}\big|\, X_k=x}\ \PP{X_k=x}. \end{align*} Ορίζουμε \(A_k=A\cap\{T=k\}\). Από τον ορισμό του παρελθόντος του \(T\) έχουμε ότι \(A_k\in\F_k\) για κάθε \(k\in\N_0\). Επομένως, το \(A_k\) προσδιορίζεται από τις τιμές των \(X_0,\ldots,X_k\) και από την μαρκοβιανή ιδιότητα (Θεώρημα 1.1) παίρνουμε ότι \[ \PP{\{(X_k,\ldots,X_{k+n})=y\}\cap A_k\,\big|\, X_k=x}=\P_x\big[(X_0,\ldots,X_n)=y\big]\ \PP{A_k\,\big|\,X_k=x}. \] Αντικαθιστώντας την παραπάνω ισότητα στην προηγούμενή της, παίρνουμε ότι \begin{align*} \PP{\{(Y_0,\ldots,Y_n)=y\}\cap A\cap\{T<\infty,\, X_T&=x\}}=\sum_{k=0}^\infty\P_x\big[(X_0,\ldots,X_n)=y\big]\ \PP{A_k\cap\{X_k=x\}}\\ &=\P_x\big[(X_0,\ldots,X_n)=y\big]\ \sum_{k=0}^\infty\PP{A\cap\{T=k, X_T=x\}}\\ &=\P_x\big[(X_0,\ldots,X_n)=y\big]\ \PP{A\cap\{T<\infty, X_T=x\}}. \end{align*} Το ζητούμενο τώρα προκύπτει από τον ορισμό της δεσμευμένης πιθανότητας.

\(\Box\)

2.5 Επαναληπτικότητα - Παροδικότητα

Ας θεωρήσουμε μια μαρκοβιανή αλυσίδα \(\{X_n\}_{n\in\N_0}\) με τιμές σ' έναν αριθμήσιμο χώρο καταστάσεων \(\X\). Για \(x\in\X\) ορίζουμε το συνολικό πλήθος των επισκέψεων της αλυσίδας στην κατάσταση \(x\) \[ V(x)=\sum_{k=0}^\infty1\!\!1\{X_k=x\}. \] Η \(V(x)\) είναι τυχαία μεταβλητή με τιμές στο \(\N_0\cup\{\infty\}\). Στις εκβάσεις \(\omega\in\Omega\) για τις οποίες \(V(x)<\infty\) η αλυσίδα τελικά εγκαταλείπει την κατάσταση \(x\) και δεν επιστρέφει ποτέ σ' αυτήν. Αντίθετα, στις εκβάσεις \(\omega\in\Omega\) για τις οποίες \(V(x)=\infty\) η αλυσίδα δεν σταματά ποτέ να επιστρέφει στην \(x\).

Ορισμός: Θα λέμε μια κατάσταση \(x\in\X\) επαναληπτική (recurrent), αν \(\P_x\big[V(x)<\infty\big]=0.\) Θα λέμε μια κατάσταση \(x\in\X\) παροδική (transient), αν \(\P_x\big[V(x)<\infty\big]=1.\)

Από τον ορισμό που δώσαμε δεν προκύπτει ότι κάθε κατάσταση \(x\in\X\) μπορεί να χαρακτηριστεί ως επαναληπτική ή παροδική. Υπάρχει θεωρητικά η δυνατότητα η \(\P_x\big[V(x)<\infty\big]\) να είναι μικρότερη του 1 αλλά θετική. Θα δούμε όμως ότι κάτι τέτοιο δεν μπορεί να συμβεί. Η εξήγηση γι' αυτό είναι απλή. Κάθε φορά που η αλυσίδα βρίσκεται στην κατάσταση \(x\) έχει την ευκαιρία να δραπετεύσει και να μην ξαναγυρίσει. Από την ισχυρή μαρκοβιανή ιδιότητα, έχει κάθε φορά την ίδια πιθανότητα (έστω \(p\)) να τα καταφέρει, ανεξάρτητα από τις προηγούμενες προσπάθειες. Επομένως το \(\{V(x)<\infty\}\) είναι στην ουσία το ενδεχόμενο να έχουμε επιτυχία σε πεπερασμένο χρόνο, σε μια σειρά από ανεξάρτητες δοκιμές Bernoulli, με πιθανότητα επιτυχίας \(p\). Κάτι τέτοιο όμως μπορεί να συμβεί είτε με πιθανότητα 1, αν \(p>0\), είτε με πιθανότητα 0, αν \(p=0\). Η απόδειξη του Θεωρήματος 2.2 που ακολουθεί, επαναλαμβάνει με αυστηρότητα το παραπάνω επιχείρημα.

Ορίζουμε τoν χρόνο πρώτης επιστροφής στη \(x\) ως \(T_x^+=\inf\{k>0: X_k=x\}\). Ορίζουμε επίσης αναδρομικά τους χρόνους της \(n\)-οστής επιστροφής της αλυσίδας \(\{X_n\}_{n\in\N_0}\) στην κατάσταση \(x\) ως εξής.

\begin{equation} Τ_0=0,\quad Τ_{n+1}=\inf\{k>T_{n}: X_k=x\},\qquad\text{για }n\in\N_0. \end{equation}

Απόδειξη: Από την Άσκηση 2.7 ο \(T_n\) είναι χρόνος διακοπής, για κάθε \(n\in\N\). Από τον ορισμό του \(T_n\) αν \(T_n<\infty\), έχουμε \(X_{T_n}=x\). Από την ισχυρή μαρκοβιανή ιδιότητα, δεδομένου ότι \(T_n<\infty\), η στοχαστική διαδικασία \(\{Y_k\}_{k\in\N_0}\) με \(Y_k=X_{T_{n}+k}\) είναι μια μαρκοβιανή αλυσίδα που ξεκινά από το \(x\), έχει τις ίδιες πιθανότητες μετάβασης όπως η \(\{X_n\}_{n\in\N_0}\) και είναι ανεξάρτητη από ενδεχόμενα στο παρελθόν του \(T_n\). Ειδικότερα, είναι ανεξάρτητη από τον \(Τ_n\). Παρατηρήστε τώρα ότι, για κάθε \(n\in\N\), έχουμε \[ Τ_{n+1}=Τ_{n}+\inf\{k>0: X_{Τ_{n}+k}=x\}=Τ_n+\inf\{k>0: Y_k=x\}. \] Επομένως, δεδομένου ότι \(Τ_n<\infty\), η \(Τ_{n+1}-Τ_n=\inf\{k>0: Y_k=x\}\) είναι ανεξάρτητη από οποιοδήποτε ενδεχόμενο στο παρελθόν του \(T_n\) και έχει την ίδια κατανομή όπως ο χρόνος της πρώτης επιστροφής στο \(x\) όταν η αλυσίδα ξεκινά από το \(x\), δηλαδή \[ \PP{T_{n+1}-T_n=k\,\big|\, T_n<\infty}=\P_x\big[T_x^+=k\big],\quad \text{για κάθε } k\in\N.\qquad\qquad\Box \] Αν μια αλυσίδα \(\{X_n\}\) ξεκινά από την επαναληπτική κατάσταση \(x\in\X\), τότε με πιθανότητα 1 όλοι οι χρόνοι \(\{T_n\}_{n\in\N}\) της (2.8) είναι πεπερασμένοι, αφού, από τον ορισμό της επαναληπτικότητας, η αλυσίδα επισκέπτεται άπειρες φορές τη \(x\). Παίρνουμε λοιπόν το το ακόλουθο πόρισμα του Λήμματος 2.2 .

Απόδειξη: Θα δείξουμε πρώτα επαγωγικά ότι για κάθε \(n\in\N_0\)

\begin{equation} \P_x\big[V(x)>n\big]=f(x)^n. \end{equation}

Για \(n=0\) και τα δύο μέλη είναι ίσα με 1, αφού, αν \(X_0=x\), τότε \(V(x)\ge 1\). Έστω τώρα ότι ο ισχυρισμός μας ισχύει για κάποιο \(n\in\N_0\). Τότε, \begin{align*} \P_x\big[V(x)>n+1\big]&=\P_x\big[T_{n+1}<\infty\big]\\ &=\P_x\big[\{T_n<\infty\}\cap\{T_{n+1}-T_n<\infty\}\big]\\ &=\P_x\big[T_{n+1}-T_n<\infty\big|T_n<\infty\big]\ \P_x\big[T_n<\infty\big]\\ &=f(x)f(x)^n, \end{align*} όπου το τελευταίο βήμα προκύπτει από το Λήμμα 2.2 και την επαγωγική υπόθεση. Επομένως, η (2.9) αληθεύει για κάθε \(n\in\N_0\). Παρατηρήστε τώρα ότι η ακολουθία ενδεχομένων \(C_n=\{V(x)>n\}\) είναι φθίνουσα. Επομένως, \begin{eqnarray*} &\P_x\big[V(x)=\infty\big]=\P_x\big[\bigcap_n\{V(x)>n\}\big]=\lim_{n\to\infty}\P_x\big[V(x)>n\big]=\lim_{n\to\infty}f(x)^n\\ &=\begin{cases} 1,&\text{αν } f(x)=1\\ 0, &\text{αν } f(x)<1.\qquad\qquad\Box\end{cases} \end{eqnarray*} Εφαρμόζοντας τον τύπο της ολικής πιθανότητας ανάλογα με το πρώτο βήμα της αλυσίδας έχουμε ότι \[ f(x)=\sum_{y\in\X}\PP{T_x^+<\infty|X_0=x,X_1=y}p(x,y). \] Από τη μαρκοβιανή ιδιότητα, δεδομένου ότι \(X_1=y\), η μαρκοβιανή διαδικασία \(\{Y_n\}_{n\in\N_0}\), με \(Y_n=X_{n+1}\), είναι μια μαρκοβιανή αλυσίδα που ξεκινά από το \(y\), με πιθανότητες μετάβασης \(\{p(x,y)\}_{x,y\in\X}\). Επιπλέον, \[ T_x^+=\inf\{k>0: X_k=x\}=1+\inf\{k\ge 0: Y_k=x\}. \] Έχουμε επομένως ότι \(T_x^+<\infty\), ακριβώς όταν ο χρόνος άφιξης της \(\{Y_n\}_{n\in\N_0}\) στο \(x\) είναι πεπερασμένος. Έτσι,

\begin{equation} f(x)=\sum_{y\in\X} p(x,y)\P_y\big[T_x<\infty\big]. \end{equation}

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

Απόδειξη: Από την απόδειξη του Θεωρήματος 2.2, φαίνεται ότι, αν η κατάσταση \(x\) είναι παροδική, το πλήθος των επισκέψεων της αλυσίδας στην κατάσταση \(x\) ακολουθεί εκθετική κατανομή, με παράμετρο \(1-f(x)>0\). Πράγματι, \[ \P_x\big[V(x)=n\big]=\P_x\big[V(x)>n-1\big]-\P_x\big[V(x)>n\big]=f(x)^{n-1}-f(x)^n=f(x)^{n-1}\big(1-f(x)\big). \] Επομένως, ο αναμενόμενος αριθμός επισκέψεων σε μια παροδική κατάσταση \(x\), όταν η αλυσίδα ξεκινά από την \(x\), είναι \[ \E_x\big[V(x)\big]=\frac{1}{1-f(x)}<+\infty. \] Επιπλέον, αν η κατάσταση \(x\) είναι επαναληπτική, τότε \(\P_x\big[V(x)=\infty\big]=1\), άρα \(\E_x\big[V(x)\big]=\infty.\) Άρα, μια κατάσταση είναι επαναληπτική ή παροδική, ανάλογα με το αν η \(\E_x\big[V(x)\big]\) είναι πεπερασμένη ή άπειρη. Όμως, αν υπολογίσουμε την \(\E_x\big[V(x)\big]\) από τον ορισμό της \(V\), έχουμε \[ \E_x\big[V(x)\big]=\E_x\Big[\sum_{n=0}^\infty 1\!\!1\{X_k=x\}\Big]=\sum_{n=0}^\infty\E_x\big[ 1\!\!1\{X_k=x\}\big]=\sum_{n=0}^\infty\P_x\big[X_k=x\big]=\sum_{n=0}^\infty p^{(n)}(x,x), \] απ' όπου έπεται ο ισχυρισμός του θεωρήματος.

\(\Box\)

Απόδειξη: Ας θεωρήσουμε μια επαναληπτική κατάσταση \(x\), και μια κατάσταση \(y\in\X\) τέτοια ώστε \(x\leftrightarrow y\). Εφόσον \(x\to y\), υπάρχει \(j\ge 0\), τέτοιο ώστε \(p^{(j)}(x,y)>0\). Ομοίως, εφόσον \(y\to x\), υπάρχει \(k\ge 0\), τέτοιο ώστε \(p^{(k)}(y,x)>0.\) Παρατηρήστε τώρα ότι για κάθε \(n\ge 0\), οι εξισώσεις Chapman-Kolmogorov δίνουν \[ p^{(j+n+k)}(x,x)=\sum_{u,v\in\X}p^{(j)}(x,u)p^{(n)}(u,v)p^{(k)}(v,x)\ge p^{(j)}(x,y)p^{(n)}(y,y)p^{(k)}(y,x). \] Αθροίζοντας αυτές τις ανισότητες ως προς \(n\) έχουμε ότι \[ \sum_{n=0}^\infty p^{(n)}(y,y)\le \frac{1}{p^{(j)}(x,y)p^{(k)}(y,x)}\sum_{n=j+k}^\infty p^{(n)}(x,x). \] Από το Θεώρημα 2.3 η σειρά στο δεξί μέλος συγκλίνει, επομένως συγκλίνει και η σειρά στο αριστερό μέλος, άρα και η \(y\) είναι επαναληπτική.

Αν μια κατάσταση \(x\) είναι παροδική και \(x\leftrightarrow y\), τότε η \(y\) θα είναι κι αυτή παροδική, αφού, αν ήταν επαναληπτική, τότε η \(x\) θα ήταν επαναληπτική, όπως δείξαμε παραπάνω.

\(\Box\)

Με βάση το προηγούμενο λήμμα έχει νοήμα να μιλάμε για επαναληπτικές κλάσεις (όταν οι καταστάσεις της κλάσης είναι επαναληπτικές) και για παροδικές κλάσεις (όταν οι καταστάσεις της κλάσης είναι παροδικές). Μπορούμε επίσης να χαρακτηρίσουμε μια μη υποβιβάσιμη μαρκοβιανή αλυσίδα ως επαναληπτική ή παροδική, ανάλογα με το τι είναι η μοναδική της κλάση.

Απόδειξη: Αν μια κλάση \({\cal C}\) είναι ανοιχτή, υπάρχουν \(x\in{\cal C}\) και \(y\notin{\cal C}\) τέτοια ώστε \(p(x,y)>0.\) Θα πρέπει τότε να έχουμε \(p^{(n)}(y,x)=0\), για κάθε \(n\in\N\), αφού διαφορετικά οι \(x,y\) θα ανήκαν στην ίδια κλάση. Έτσι, \[ \E_y\big[V(x)\big]=\E_y\Big[\sum_{n=0}^\infty 1\!\!1\{X_k=x\}\Big]=\sum_{n=0}^\infty\P_y\big[X_k=x\big]=\sum_{n=0}^\infty p^{(n)}(y,x)=0. \] Εφόσον η \(V(x)\) είναι μια μη αρνητική τυχαία μεταβλητή, η παραπάνω σημαίνει ότι \(\P_y\big[V(x)=0\big]=1\). Από τον τύπο της ολικής πιθανότητας, ανάλογα με το πρώτο βήμα της αλυσίδας, έχουμε τώρα ότι

\begin{equation} \P_x\big[V(x)<\infty\big]=\sum_{z\in\X}\P_x\big[V(x)<\infty\big|\, X_1=z\big] p(x,z) =\sum_{z\in\X}\P_z\big[V(x)<\infty\big]p(x,z), \end{equation}

όπου η τελευταία ισότητα προκύπτει από τη μαρκοβιανή ιδιότητα. Αν από το τελευταίο άθροισμα κρατήσουμε μόνο τον όρο για \(z=y\), παίρνουμε ότι \[ \P_x\big[V(x)<\infty\big]\ge\P_y\big[V(x)<\infty\big]p(x,y)=p(x,y)>0. \] Επομένως η \(x\) δεν είναι επαναληπτική και από το Θεώρημα 2.2 είναι παροδική. Λόγω του Λήμματος 2.3 , η \({\cal C}\) είναι κι αυτή παροδική.

\(\Box\)

Απόδειξη: Εφόσον \(y\to x\), υπάρχει \(n\ge 0\) τέτοιο ώστε \(p^{(n)}(y,x)>0\). Επειδή η \(y\) είναι παροδική κατάσταση έχουμε, κατ' αναλογία με την (2.11), \[ 0=\P_y\big[V(y)=\infty\big]=\sum_{z\in\X}\P_y\big[V(y)=\infty\big|\ X_n=z\big]\ p^{(n)}(y,z)\ge \P_x\big[V(y)=\infty\big]\ p^{(n)}(y,x). \] Έχουμε όμως \(p^{(n)}(y,x)>0\), άρα θα πρέπει \(\P_x\big[V(y)=\infty\big]=0\Leftrightarrow\P_x\big[V(y)<+\infty\big]=1\). Ομοίως, αν η \({\cal C}\) είναι επαναληπτική, έχουμε \[ 0=\P_y\big[V(y)<\infty\big]=\sum_{z\in\X}\P_y\big[V(y)<\infty\big|\ X_n=z\big]\ p^{(n)}(y,z)\ge \P_x\big[V(y)<\infty\big]\ p^{(n)}(y,x). \] Επομένως, αν επιλέξουμε το \(n\) ώστε \(p^{(n)}(y,x)>0\), παίρνουμε ότι \(\P_x\big[V(y)<+\infty\big]=0.\)

\(\Box\)

Βλέπουμε από το παραπάνω λήμμα ότι μια μη υποβιβάσιμη, επαναληπτική αλυσίδα εξερευνά ολόκληρο τον χώρο καταστάσεων και μάλιστα με πιθανότητα 1 επισκέπτεται κάθε κατάσταση άπειρες φορές.

Απόδειξη: Έστω \({\cal C}\) πεπερασμένη και κλειστή κλάση. Κάθε αλυσίδα που ξεκινάει από κάποιο \(x\in{\cal C}\) παραμένει στο \({\cal C}\) για πάντα. Επομένως, θα υποθέσουμε χωρίς βλάβη ότι η αλυσίδα είναι μη υποβιβάσιμη. Τώρα, \[ \sum_{y\in{\cal C}}V(y)=\sum_{y\in{\cal C}}\sum_{n=0}^\infty1\!\!1\{X_n=y\}=\sum_{n=0}^\infty\sum_{y\in{\cal C}}1\!\!1\{X_n=y\}=\sum_{n=0}^\infty 1\!\!1_{{\cal C}}(X_n)=\sum_{n=0}^\infty 1=\infty. \]

Εφόσον η \({\cal C}\) είναι πεπερασμένη, θα υπάρχει κάποιο \(y\in{\cal C}\) τέτοιο ώστε \(\P_x\big[V(y)=\infty\big]>0\). Από το προηγούμενο λήμμα όμως αυτό σημαίνει ότι η \({\cal C}\) δεν είναι παροδική.

\(\Box\)

Τα Θεωρήματα 2.4 και 2.5 απλοποιούν πολύ τον χαρακτηρισμό των κλάσεων σε πεπερασμένους χώρους καταστάσεων \(\X\). Είναι εν γένει εύκολο να βρούμε αν μια κλάση είναι ανοιχτή ή κλειστή και, αν o \(\X\) είναι πεπερασμένος, οι ανοιχτές κλάσεις είναι παροδικές και οι κλειστές κλάσεις είναι επαναληπτικές. Όταν ο \(\X\) είναι άπειρος, οι ανοιχτές κλάσεις είναι παροδικές, μια κλειστή κλάση όμως μπορεί να είναι επαναληπτική ή παροδική, όπως θα δούμε στα παραδείγματα.

Θα χρησιμοποιήσουμε κάποιες ιδιότητες της συνάρτησης Γάμμα \[ \Gamma(p)=\int_0^\infty x^{p-1}e^{-x}dx,\ p>0. \] Εύκολα μπορούμε να δούμε ότι \(\Gamma(1)=1\), ενώ με μια ολοκλήρωση κατά μέλη βλέπουμε ότι \(\Gamma(p+1)=p\Gamma(p)\), για κάθε \(p>0\). Από τις δύο αυτές ιδιότητες προκύπτει με επαγωγή ότι \(\Gamma(n)=(n-1)!\) για κάθε \(n\in\N\). Με την αλλαγή μεταβλητής \(z=\sqrt{2x}\) βρίσκουμε επίσης ότι \(\Gamma(\frac{1}{2})=\sqrt{\pi}\). Τέλος, από την ανισότητα Cauchy-Schwarz, έχουμε

\begin{equation} \Gamma(p+\frac{1}{2})=\int_0^{\infty}\sqrt{x}\, x^{p-1}e^{-x} dx\le \left(\int_0^{\infty}x^{p}e^{-x} dx\int_0^{\infty}x^{p-1}e^{-x} dx\right)^{\frac{1}{2}}=\sqrt{\Gamma(p+1)\Gamma(p)}=\sqrt{p}\Gamma(p). \end{equation}

Έχουμε τώρα όλα τα υλικά που χρειαζόμαστε από τη συνάρτηση Γάμμα και προχωράμε στην εκτίμηση που θέλουμε να κάνουμε. \begin{align*} {2n\choose n}\frac{1}{2^{2n}}&=\frac{1\cdot 3\cdot 5\cdots (2n-1)}{2^n}\ \frac{2\cdot 4\cdot 6\cdots (2n)}{2^n(n!)^2}=\left(\frac{1}{2}\right)\left(\frac{3}{2}\right)\left(\frac{5}{2}\right)\cdots\left(\frac{2n-1}{2}\right)\frac{2^nn!}{2^n(n!)^2}\\ &=\Gamma(\frac{1}{2})\left(\frac{1}{2}\right)\left(\frac{3}{2}\right)\left(\frac{5}{2}\right)\cdots(n-\frac{1}{2})\ \frac{1}{\Gamma(\frac{1}{2})n!}=\frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi}n!}. \end{align*} Από την (2.14) έχουμε τώρα ότι \[ {2n\choose n}\frac{1}{2^{2n}}=\frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi}n!}\le \frac{\sqrt{n}\Gamma(n)}{\sqrt{\pi}n\Gamma(n)}=\frac{1}{\sqrt{\pi n}}, \] και \[ {2n\choose n}\frac{1}{2^{2n}}=\frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi}\Gamma(n+1)}\ge\frac{\Gamma(n+\frac{1}{2})}{\sqrt{\pi(n+\frac{1}{2})}\Gamma(n+\frac{1}{2})}=\frac{1}{\sqrt{\pi(n+\frac{1}{2})}}.\qquad\Box \]

2.6 Ασκήσεις

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

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