"Fossies" - the Fresh Open Source Software Archive

Member "hevea-2.35/bugs/008/Chapter_6.tex" (16 Jan 2021, 59621 Bytes) of package /linux/www/hevea-2.35.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) TeX and LaTeX source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

A hint: This file contains one or more very long lines, so maybe it is better readable using the pure text view mode that shows the contents as wrapped lines within the browser window.


    1 \documentclass[11pt]{article}
    2 
    3 \usepackage[english,greek]{babel}
    4 \usepackage[utf8x]{inputenc}
    5 \newcommand{\en}[1]{\textlatin{#1}}
    6 
    7 \setlength\topmargin{-0.5in}
    8 \setlength\textheight{23cm}
    9 \setlength\oddsidemargin{-0.4in}
   10 \setlength\textwidth{17cm}
   11 
   12 \usepackage{latexsym}
   13 \usepackage{amsmath}
   14 \usepackage{amsfonts}
   15 \usepackage{theorem}
   16 \usepackage{graphicx}
   17 \usepackage{pdfsync}
   18 %\usepackage{showlabels}
   19 \usepackage{bbm}
   20 
   21 \theorembodyfont{\upshape}
   22 
   23 \newtheorem{exercise}{Άσκηση}
   24 \newtheorem{theorem}{Θεώρημα}
   25 \newtheorem{example}{Παράδειγμα}
   26 \newtheorem{corollary}{Πόρισμα}
   27 \newtheorem{lemma}{Λήμμα}
   28 
   29 \def\N{\mathbb{N}}
   30 \def\Z{\mathbb{Z}}
   31 \def\X{\mathbb{X}}
   32 \def\P{\mathbb{P}}
   33 \def\E{\mathbb{E}}
   34 \def\R{\mathbb{R}}
   35 \def\MX{{\cal M}(\X)}
   36 \def\xn{\{X_n\}_{n\in\N_0}}
   37 \def\beq{\begin{equation}}
   38 \def\eeq{\end{equation}}
   39 \def\bea{\begin{align}}
   40 \def\ea{\end{align}}
   41 \def\bea*{\begin{align*}}
   42 \def\ea*{\end{align*}}
   43 \def\CQFD{\hfill\hbox{\vrule\vbox to 8pt{\hrule width 8pt\vfill\hrule}\vrule}}
   44 \def\half{\frac{1}{2}}
   45 \def\IP{{\cal I}(P)}
   46 
   47 \newcommand{\PP}[1]{\P\big[#1\big]}
   48 \newcommand{\Px}[1]{\P_x\big[#1\big]}
   49 \newcommand{\EE}[1]{\E\big[#1\big]}
   50 \newcommand{\Ex}[1]{\E_x\big[#1\big]}
   51 
   52 \begin{document}
   53 \begin{center}
   54 \Large {\bf KΕΦΑΛΑΙΟ \en{VI}. ΑΝΑΛΛΟΙΩΤΕΣ ΚΑΤΑΝΟΜΕΣ}
   55 \end{center}
   56 \noindent
   57 \vspace{3mm}
   58 
   59 \noindent
   60 Οι αναλλοίωτες κατανομές είναι κατά κάποιο τρόπο οι φυσικές καταστάσεις μιας μαρκοβιανής αλυσίδας. 
   61 Αν μια αλυσίδα ξεκινήσει από μια αναλλοίωτη κατανομή της θα παραμείνει σε αυτήν για πάντα, ενώ η ασυμπτωτική συμπεριφορά μιας αλυσίδας μπορεί να χαρακτηριστεί μέσω αυτών. Επίσης, οι απαντήσεις σε πολλά προβλήματα μπορούν εύκολα να εκφραστούν μέσω των αναλλοίωτων κατανομών. Σε αυτό το κεφάλαιο θα δούμε ικανές και αναγκαίες συνθήκες για την ύπαρξη αναλλοίωτων κατανομών, θα μελετήσουμε τις ιδιότητές και την δομή τους.
   62 \section{Αναλλοίωτες κατανομές}\label{invdist}
   63 Θα συμβολίζουμε το σύνολο των κατανομών στον $\X$ με $\MX$. Έτσι 
   64 \[
   65 \pi\in\MX\Leftrightarrow \text{ η } \pi \text{ είναι μια συνάρτηση }\pi:\X\to[0,1]\ \text{ με } \sum_{x\in\X}\pi(x)=1.
   66 \]
   67 \noindent
   68 Έστω $\{X_n\}_{n\in\N}$ μια μαρκοβιανή αλυσίδα με αρχική κατανομή $\pi_0$ και πιθανότητες μετάβασης $\{p(x,y)\}_{x,y\in\X}$. Θα συμβολίζουμε την κατανομή της τυχαίας μεταβλητής $X_n$ με $\pi_n$, δηλαδή 
   69 \beq
   70 \pi_n(x)=\PP{X_n=x}\quad\text{για }x\in\X.
   71 \label{mcd}
   72 \eeq
   73 Το κεντρικό ερώτημα αυτού του κεφαλαίου είναι αν η $\pi_n$ συγκλίνει καθώς $n\to\infty$, και αν ναι, ποιο είναι το όριό της $\pi$. \\[2mm]
   74 {\bf Ορισμός} Αν $\{\pi_n\}_n$ είναι μια ακολουθία κατανομών στο $\MX$, θα λέμε ότι συγκλίνει στην κατανομή $\pi\in\MX$ αν και μόνο h πιθανότητα που αποδίδει η $\pi_n$ σε κάθε κατάσταση συγκλίνει στην αντίστοιχη πιθανότητα που αποδίδει η $\pi$. Δηλαδή,
   75 \beq
   76 \label{pwdef}
   77 \pi_n\to\pi\in\MX\Leftrightarrow \pi_n(x)\to\pi(x)\quad\text{για κάθε }x\in\X
   78 \eeq
   79 {\bf Παρατήρηση:} Από ένα αποτέλεσμα της θεωρίας μέτρου, το λήμμα του \en{Scheff\'e} (βλ. \cite{DW}, παρ. 5.10), o παραπάνω ορισμός είναι ισοδύναμος με το φαινομενικά ισχυρότερο αποτέλεσμα
   80 \beq
   81 \label {l1def}
   82 \pi_n\to\pi\in\MX\Leftrightarrow \sum_{x\in\X}|\pi_n(x)-\pi(x)|\to 0.
   83 \eeq
   84 {\bf Ορισμός:} Αν η $\{\pi_n\}_n$ είναι η ακολουθία των κατανομών μιας μαρκοβιανής αλυσίδας $\{X_n\}$, αν δηλαδή η $\pi_n$ ορίζεται όπως στην (\ref{mcd}) για κάθε $n\in\N_0$, και $\pi_n\to\pi\in\MX$, θα λέμε ότι η $\pi$ είναι η {\em κατανομή ισορροπίας} (ή εναλλακτικά η {\em ασυμπτωτική κατανομή}) της $\{X_n\}$.\\[2mm]
   85 Το πρώτο μας αποτέλεσμα χαρακτηρίζει τις υποψήφιες κατανομές ισορροπίας μαρκοβιανών αλυσίδων.
   86  
   87 \begin{theorem}
   88 \label{invcond}
   89 Αν η ακολουθία $\{\pi_n\}_n$ των κατανομών μιας μαρκοβιανής αλυσίδας $\{X_n\}_{n\in\N}$ με πίνακα πιθανοτήτων μετάβασης $P$ συγκλίνει στην κατανομή $\pi\in\MX$ τότε
   90 \beq
   91 \label{piP}
   92 \pi=\pi P,\quad\text{δηλαδή}\quad \pi(x)=\sum_{y\in\X}\pi(y)p(y,x)\quad\text{για κάθε }x\in\X.
   93 \eeq 
   94 \end{theorem}
   95 {\bf Απόδειξη:} Είδαμε στο δεύτερο κεφάλαιο ότι η κατανομή $\pi_n$ μιας μαρκοβιανής αλυσίδας $\{X_n\}_{n}$ μετά από $n$ βήματα, δηλαδή η κατανομή της τυχαίας μεταβλητής $X_n$, δίνεται από την 
   96 \[
   97 \pi_n=\pi_0P^n.
   98 \]
   99 Επομένως για κάθε $n\in\N$ έχουμε
  100 \[
  101 \pi_n=\pi_0(P^{n-1}P)=(\pi_0P^{n-1})P=\pi_{n-1}P,
  102 \]
  103 δηλαδή
  104 \[
  105 \pi_n(x)=\sum_{y\in\X}\pi_{n-1}(y)p(y,x)\quad\text{για κάθε }x\in\X.
  106 \]
  107 Παίρνοντας το όριο καθώς $n\to\infty$ στα δύο μέλη της προηγούμενης σχέσης το αριστερό μέλος συγκλίνει στην $\pi(x)$, ενώ για το δεξί μέλος έχουμε
  108 \[
  109 |\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,
  110 \]
  111 από την (\ref{l1def}). Επομένως $\pi(x)=\sum_{y\in\X}\pi(y)p(y,x)$ για κάθε $x\in X$.\CQFD\\
  112 
  113 \noindent
  114 Σύμφωνα με το προηγούμενο Θεώρημα τα μόνα υποψήφια όρια των κατανομών μιας μαρκοβιανής αλυσίδας με πίνακα πιθανοτήτων μετάβασης $P$ είναι εκείνες οι $\pi:\X\to[0,1]$ για τις οποίες
  115 \beq
  116 \label{pts}
  117 \begin{cases}&\pi=\pi P\\ &\sum_{x\in\X}\pi(x)=1.\end{cases}
  118 \eeq
  119 {\bf Ορισμός:} Αν μια κατανομή $\pi\in\MX$ ικανοποιεί την (\ref{piP}) θα λέμε ότι είναι {\em αναλλοίωτη}{\em στάσιμη}) κατανομή για την αλυσίδα $\{X_n\}_n$ με πίνακα πιθανοτήτων μετάβασης $P$.\\[2mm]
  120 Το Θεώρημα \ref{invcond} μπορούμε να το αναδιατυπώσουμε και ως εξής. {\em Οι μόνες δυνατές κατανομές ισορροπίας μιας μαρκοβιανής αλυσίδας είναι οι αναλλοίωτες κατανομές της.} Η ορολογία αναλλοίωτη και στάσιμη εξηγείται από το παρακάτω Θεώρημα.
  121 \begin{theorem}
  122 \label{invariance}
  123 Αν η αρχική κατανομή $\pi_0\in\MX$ μιας αλυσίδας στον $\X$ με πίνακα πιθανοτήτων μετάβασης $P$ ικανοποιεί την (\ref{piP}) τότε
  124 \[
  125 \pi_n=\pi_0\quad\text{για κάθε }n\in\N.
  126 \]
  127 Επιπλέον, η $\{X_n\}_{n\in\N_0}$ είναι στάσιμη, δηλαδή για κάθε $n,k\in\N_0$ και κάθε $x_0,x_1,\ldots,x_k\in\X$ έχουμε
  128 \[
  129 \PP{X_n=x_0,X_{n+1}=x_1,\ldots,X_{n+k}=x_k}=\PP{X_0=x_0,X_{1}=x_1,\ldots,X_{k}=x_k}.
  130 \]
  131 {\bf Απόδειξη:} Θα δείξουμε τον ισχυρισμό $\pi_n=\pi_0$ για κάθε $n\in\N$ επαγωγικά. Για $n=1$ έχουμε
  132 \[
  133 \pi_1=\pi_0P=\pi_0,\quad
  134 \]
  135 μια και για την $\pi_0$ έχουμε υποθέσει ότι ικανοποιεί την (\ref{piP}). Έστω τώρα ότι για κάποιο $n\in\N$ έχουμε $\pi_n=\pi_0$. Τότε
  136 \[
  137 \pi_{n+1}=\pi_nP=\pi_0P=\pi_0.
  138 \]
  139 Επομένως $\pi_n=\pi_0$ για κάθε $n\in\N$. Για τον δεύτερο ισχυρισμό έχουμε από την μαρκοβιανή ιδιότητα
  140 \begin{align*}
  141 \PP{X_n=x_0,\ldots,X_{n+k}=x_k}&=\PP{X_n=x_0}\PP{X_{n+1}=x_1\,|\,X_n=x_0}\cdots\PP{X_{n+k}=x_k\,|\,X_{n+k-1}=x_{k-1}}\\
  142 &=\pi_n(x_0)p(x_0,x_1)\cdots p(x_{k-1},x_k)\\
  143 &=\pi_0(x_0)p(x_0,x_1)\cdots p(x_{k-1},x_k)\\
  144 &=\PP{X_0=x_0,X_{1}=x_1,\ldots,X_{k}=x_k}.
  145 \end{align*}
  146 \CQFD\\
  147 \end{theorem}
  148 \begin{example}
  149 Έστω $\{X_n\}_n$  μια μαρκοβιανή αλυσίδα σε έναν χώρο με δύο καταστάσεις $\X=\{\alpha,\beta\}$ και πίνακα πιθανοτήτων μετάβασης
  150 \[
  151 {P}=\bordermatrix{&&\cr
  152 &1-p&p\cr
  153 &q&1-q\cr
  154 },
  155 \]
  156 με $p,q\in(0,1)$. Από την (\ref{pts}) προκειμένου η $\pi=(\pi_\alpha,\pi_\beta)$ να είναι αναλλοίωτη κατανομή της αλυσίδας θα πρέπει να ικανοποιεί τις
  157 \[
  158 \begin{cases}&\pi_a=(1-p)\pi_\alpha+q\pi_\beta\\ &\pi_\beta=p\pi_\alpha+(1-q)\pi_\beta\\&\pi_\alpha+\pi_\beta=1.\end{cases}
  159 \]
  160 Λύνοντας το παραπάνω σύστημα βρίσκουμε ότι η
  161 \[
  162 \pi=\big(\frac{q}{p+q},\frac{p}{p+q}\big)
  163 \]
  164 είναι αναλλοίωτη κατανομή της αλυσίδας. Επομένως αν η αρχική κατανομή της αλυσίδας είναι η $\pi$, αν δηλαδή
  165 \[
  166 \PP{X_0=\alpha}=\frac{q}{p+q}\quad\text{και}\quad\PP{X_0=\beta}=\frac{p}{p+q}
  167 \]
  168 τότε $\pi_n=\pi$ για κάθε $n\in\N$. Προσέξτε ότι σε κάθε της βήμα η αλυσίδα αλλάζει κατάσταση με πιθανότητα $p$ αν βρίσκεται στην κατάσταση $\alpha$ ή $q$ αν βρίσκεται στην κατάσταση $\beta$. Αυτό που δεν αλλάζει είναι η κατανομή της $X_n$, δηλαδή η πιθανότητα να βρούμε την αλυσίδα σε καθεμιά από τις δύο καταστάσεις.
  169 \end{example}
  170 \section{Η δομή του $\IP$}
  171 Στην συνέχεια θα εξετάσουμε αν μπορούμε να βρούμε αναλλοίωτες κατανομές για μια αλυσίδα, και στην περίπτωση που μπορούμε ποιες είναι αυτές. Θα συμβολίζουμε με $\IP$ το σύνολο των αναλλοίωτων κατανομών μιας αλυσίδας με πίνακα πιθανοτήτων μετάβασης $P$, δηλαδή
  172 \[
  173 \IP=\{\pi\in\MX: \pi=\pi P\}.
  174 \]
  175 Το επόμενο λήμμα θα μας φανεί πολύ χρήσιμο
  176 \begin{lemma}
  177 \label{idcomparison}
  178 Αν $\xn$ είναι μια μαρκοβιανή αλυσίδα με πίνακα πιθανοτήτων μετάβασης $P$ και $\pi\in\IP$ τότε για κάθε $x,y\in\X$ έχουμε
  179 \beq
  180 \pi(y)\ge\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big].
  181 \label{compleq}
  182 \eeq
  183 \end{lemma}
  184 {\bf Απόδειξη:} Έστω $\pi\in\IP$. Για κάθε $x,y\in\X$ έχουμε
  185 \begin{align*}
  186 \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)\\
  187 &=\pi(x)p(x,y)+\sum_{z\neq x}\Big(\sum_{u\in\X}\pi(u)p(u,z)\Big)p(z,y)\\
  188 &=\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)
  189 \end{align*}
  190 Aς επαναλάβουμε την παραπάνω διαδικασία ακόμα μια φορά, γράφοντας
  191 \[
  192 \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).
  193 \]
  194 Παίρνουμε τότε ότι
  195 \begin{align}
  196 \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).
  197 %&=\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).
  198 \label{iter3}
  199 \end{align}
  200 Προσέξτε ότι στον όρο $\sum_{z,u\neq x}p(x,u)p(u,z)p(z,y)$ αθροίζουμε τις πιθανότητες όλων των μονοπατιών μήκους 3 που ξεκινούν από το $x$ και καταλήγουν στο $y$ χωρίς ενδιάμεσα να έχουν ξαναπεράσει από το $x$. Άρα,
  201 \[
  202 \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}.
  203 \]
  204 Αντίστοιχα έχουμε
  205 \[
  206 \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}
  207 \]
  208 ενώ
  209 \[
  210 p(x,y)=\Px{X_1=y}=\Px{X_1=y,\ T_x^+\ge 1}.
  211 \]
  212 Με αυτήν παρατήρηση μπορούμε να ξαναγράψουμε την (\ref{iter3}) ως
  213 \[
  214 \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).
  215 \]
  216 Θα πρέπει να είναι τώρα φανερό ότι αν επαναλάβουμε αυτήν την διαδικασία $n$ φορές έχουμε ότι
  217 \begin{align}
  218 \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)\label{prelimit}\\
  219 &\ge\pi(x) \Big(\sum_{k=1}^n\Px{X_k=y,\ T_x^+\ge k}\Big)\qquad\text{για κάθε }n\in\N.\notag
  220 \end{align}
  221 Περνώντας στο όριο $n\to\infty$ έχουμε λοιπόν
  222 \begin{align*}
  223 \pi(y)&\ge \pi(x) \Big(\sum_{k=1}^\infty\Px{X_k=y,\ T_x^+\ge k}\Big)\\
  224 &=\pi(x)\  \Big(\sum_{k=1}^\infty\Ex{\mathbbm{1}\{X_k=y,\ T_x^+\ge k\}}\Big).
  225 \end{align*}
  226 Εφόσον οι δείκτριες συναρτήσεις που εμφανίζονται παραπάνω είναι μη αρνητικές, από το θεώρημα \en{Fubini-Tonelli} μπορούμε να εναλλάξουμε την άθροιση ως προς $k$ και την αναμενόμενη τιμή, παίρνοντας
  227 \begin{align*}
  228 \pi(y)&\ge\pi(x)\ \E_x\Big[\sum_{k=1}^\infty\mathbbm{1}\{X_k=y,\ T_x^+\ge k\}\Big]\\
  229 &=\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big].\
  230 \end{align*}
  231 \CQFD\\
  232 \ \\
  233 {\bf Ορισμός:} Θα λέμε μια κατάσταση $x\in\X$ {\em γνησίως επαναληπτική} αν $\Ex{T_x^+}<+\infty$.\\
  234 \ \\
  235 Η γνήσια επαναληπτικότητα είναι μια έννοια ισχυρότερη της επαναληπτικότητας, αφού αν $\Ex{T_x^+}<+\infty$ τότε αναγκαστικά έχουμε $\Px{T_x^+<\infty}=1$, και άρα η $x$ είναι επαναληπτική. Το ακόλουθο Πόρισμα μας εγγυάται ότι οποιαδήποτε αναλλοίωτη κατανομή μιας αλυσίδας στηρίζεται σε γνησίως επαναληπτικές καταστάσεις.
  236 \begin{corollary}\label{support}
  237 Αν $\pi\in\IP$ και $x\in\X$ τότε 
  238 \[
  239 \Ex{T_x^+}=+\infty\Rightarrow \pi(x)=0.
  240 \]
  241 \end{corollary}
  242 {\bf Απόδειξη:} Αθροίζοντας τις ανισότητες (\ref{compleq}) για όλα τα $y\in\X$ έχουμε
  243 \[
  244 1=\sum_{y\in\X}\pi(y)\ge \pi(x)\ \sum_{y\in\X}\E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big]=\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\sum_{y\in\X}\mathbbm{1}\{X_k=y\}\Big],
  245 \]
  246 όπου χρησιμοποιήσαμε το θεώρημα \en{Fubini-Tonelli} για να εναλλάξουμε την σειρά των αθροίσεων και της αναμενόμενης τιμής.
  247 Προσέξτε όμως ότι στο άθροισμα ως προς $y$ υπάρχει ακριβώς ένας όρος $\mathbbm{1}\{X_k=y\}$ που είναι ίσος με 1 (αυτός που αντιστοιχεί στην κατάσταση της $X_k$ ) ενώ όλοι οι υπόλοιποι είναι μηδέν. Επομένως, η παραπάνω ανισότητα γίνεται
  248 \[
  249 1\ge \pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}1\Big]=\pi(x)\ \Ex{T_x^+},
  250 \]
  251 απ' όπου έπεται ο ισχυρισμός μας. \CQFD\ \\
  252 \begin{corollary}\label{prexist}
  253 Αν μια μαρκοβιανή αλυσίδα έχει αναλλοίωτη κατανομή τότε έχει τουλάχιστον μία γνησίως επαναληπτική κατάσταση. 
  254 \end{corollary}
  255 {\bf Απόδειξη:} Αν $\pi\in\IP$ τότε $\pi(y)\ge 0$ για κάθε $y\in\X$ και $\sum_{y\in\X}\pi(y)=1$. Θα υπάρχει επομένως κάποια κατάσταση $x$ για την οποία $\pi(x)>0$ και άρα από το Πόρισμα \ref{support} θα πρέπει $\Ex{T_x^+}<\infty.$\CQFD\\
  256 \ \\
  257 Στο επόμενο θεώρημα θα δείξουμε ότι και το αντίστροφο του προηγούμενου πορίσματος είναι σωστό. Δηλαδή, αν μια αλυσίδα έχει μια γνησίως επαναληπτική κατάσταση $x$ τότε έχει και αναλλοίωτη κατανομή, κατασκευάζοντας μια εκπεφρασμένα. Η ιδέα προέρχεται από το Λήμμα \ref{idcomparison}.
  258 \begin{theorem}\label{explicit}
  259 Έστω $x\in\X$ μια γνησίως επαναληπτική κατάσταση. Ορίζουμε
  260 \[
  261 \pi_x(y)=\frac{1}{\Ex{T_x^+}}\E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big]
  262 \] 
  263 H $\pi_x$ είναι αναλλοίωτη κατανομή της αλυσίδας $\xn$, και 
  264 \beq
  265 \pi_x(x)=\frac{1}{\Ex{T_x^+}}.
  266 \label{invtime}
  267 \eeq
  268 \end{theorem}
  269 {\bf Παρατήρηση:} Μπορούμε να σκεφτούμε την κατανομή $\pi_x$ ως εξής. Ξεκινώντας από την $x$ κάνουμε μια εκδρομή μέχρι να επιστρέψουμε πάλι στην κατάσταση $x$, δηλαδή μέχρι τον χρόνο διακοπής $T_x^+$. Κατά την διάρκεια αυτής της εκδρομής σημειώνουμε πόσες επισκέψεις κάναμε στην κατάσταση $y\in\X$. Το πλήθος αυτών των επισκέψεων είναι
  270 \[
  271 \sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}
  272 \]
  273 και είναι βέβαια μια τυχαία μεταβλητή. Το βάρος που δίνει η $\pi_x$ στην κατάσταση $y$ είναι ανάλογο προς το αναμενόμενο πλήθος τον επισκέψεων μας στην κατάσταση $y$ κατά τη διάρκεια αυτής της εκδρομής γύρω από την $x$. Η σταθερά αναλογίας $\frac{1}{\Ex{T_x^+}}$ που εμφανίζεται είναι απλά ένας παράγοντας κανονικοποίησης ώστε η $\pi_x$ να είναι κατανομή. \\
  274 \ \\
  275 {\bf Απόδειξη:} Ας δούμε πρώτα ότι $\pi_x\in\MX.$ Πράγματι, είναι φανερό από τον ορισμό ότι $\pi_x(y)\ge 0$ για κάθε $y\in\X$,  ενώ
  276 \[
  277 \sum_{y\in\X}\pi_x(y)= \frac{1}{\Ex{T_x^+}}\ \sum_{y\in\X}\E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big]= \frac{1}{\Ex{T_x^+}}\ \E_x\Big[\sum_{k=1}^{T_x^+}\sum_{y\in\X}\mathbbm{1}\{X_k=y\}\Big]= \frac{\Ex{T_x^+}}{\Ex{T_x^+}}=1.
  278 \]
  279 Ο ισχυρισμός της (\ref{invtime}) προκύπτει άμεσα από τον ορισμό του χρόνου $T_x^+=\inf\{k\ge 1: X_k=x\}$, αφού κατά την διάρκεια της εκδρομής γύρω από την $x$, δηλαδή για $k\in\{1,2,\ldots,T_x^+\}$ η αλυσίδα μας βρίσκεται στην $x$ μόνο την χρονική στιγμή $T_x^+$.\\
  280 \ \\
  281 Θα δείξουμε τώρα ότι η $\pi_x$ είναι αναλλοίωτη. Πράγματι, για κάθε $y\in\X$ έχουμε
  282 \begin{align}
  283 \pi_x(y)&=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big]\notag\\
  284 &=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{\infty}\mathbbm{1}\{X_k=y,\ T_x^+\ge k\}\Big]\notag\\
  285 &=\pi_x(x)\ \E_x\Big[\sum_{k=1}^{\infty}\sum_{z\in\X}\mathbbm{1}\{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k\}\Big]\notag\\
  286 &=\pi_x(x)\ \sum_{z\in\X}\sum_{k=1}^{\infty}\ \E_x\Big[\mathbbm{1}\{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k\}\Big] \quad \text{(θ. \en{Fubini-Tonelli)}}\notag\\
  287 &=\pi_x(x)\ \sum_{z\in\X}\sum_{k=1}^{\infty}\ \Px{X_{k-1}=z,\ X_k=y,\ T_x^+\ge k}\label{step1}
  288 \end{align}
  289 Παρατηρήστε τώρα ότι $\mathbbm{1}\{T_x^+\ge k\}=\mathbbm{1}\{X_1\neq x,\ X_2\neq x,\cdots,X_{k-1}\neq x\}$,
  290 επομένως το ενδεχόμενο $\{T_x^+\ge k\}$ ανήκει στην κλάση ${\cal F}_{k-1}$. Έτσι, από την μαρκοβιανή ιδιότητα έχουμε
  291 \[
  292 \Px{X_k=y\, |\, X_{k-1}=z,\, T_x^+\ge k}=\Px{X_k=y\, |\, X_{k-1}=z}=p(z,y),
  293 \]
  294 και η σχέση (\ref{step1}) γίνεται
  295 \begin{align}
  296 \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\\
  297 &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\sum_{k=1}^{\infty}\Ex{\mathbbm{1}\{X_{k-1}=z,\, T_x^+\ge k\}}\notag\\
  298 &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\ \E_x\Big[\sum_{k=1}^{\infty}\mathbbm{1}\{X_{k-1}=z,\, T_x^+\ge k\}\Big]\quad \text{(θ. \en{Fubini-Tonelli)}}\notag\\
  299 &=\pi_x(x)\ \sum_{z\in\X}p(z,y)\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_{k-1}=z\}\Big].\label{step2}
  300 \end{align}
  301 Παρατηρήστε τέλος ότι
  302 \[
  303 \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_{k-1}=z\}\Big]\stackrel{m=k-1}{=}\E_x\Big[\sum_{m=0}^{T_x^+-1}\mathbbm{1}\{X_{m}=z\}\Big]=\E_x\Big[\sum_{m=1}^{T_x^+}\mathbbm{1}\{X_{m}=z\}\Big],
  304 \]
  305 όπου η τελευταία ισότητα προκύπτει γιατί η αλυσίδα μας με $\P_x$-πιθανότητα 1 βρίσκεται στην $x$ τόσο την χρονική στιγμή 0 όσο και την χρονική στιγμή $T_x^+$. Έτσι, η (\ref{step2}) γίνεται 
  306 \[
  307 \pi_x(y)=\sum_{z\in\X}p(z,y)\pi_x(x)\ \E_x\Big[\sum_{m=1}^{T_x^+}\mathbbm{1}\{X_{m}=z\}\Big]=\sum_{z\in\X}p(z,y)\pi_x(z),
  308 \]
  309 και επομένως $\pi_x\in\IP$.\CQFD\\
  310 \ \\
  311 Όπως είδαμε μια γνησίως επαναληπτική κατάσταση $x\in\X$ είναι επαναληπτική και άρα ανήκει αναγκαστικά σε μια κλειστή κλάση $C_x$. Από την κατασκευή της κατανομής $\pi_x$ είναι φανερό ότι 
  312 \[
  313 y\notin{C}_x\Rightarrow \pi_x(y)=0,
  314 \]
  315 αφού αν $y\notin{C}_x$ η αλυσίδα που ξεκινά από το $x$ αποκλείεται να επισκεφτεί την κατάσταση $y$ ποτέ, και ειδικώτερα αποκλείεται να επισκεφτεί την $y$ μέχρι να επιστρέψει στην $x$. Θα δείξουμε τώρα ότι η $\pi_x$ δίνει θετικό βάρος σε όλες τις καταστάσεις της κλάσης ${C}_x$.
  316 \begin{theorem}\label{positiveweight}
  317 Αν η κατάσταση $x$ είναι γνησίως επαναληπτική και $y\in{C}_x$ τότε $\pi_x(y)>0$.
  318 \end{theorem}
  319 {\bf Απόδειξη:} Εφόσον η $y$ είναι προσβάσιμη από την $x$ υπάρχει $m\in\N$ τέτοιο ώστε $p^{(m)}(x,y)>0$. Επίσης εύκολα μπορούμε να δείξουμε επαγωγικά ότι
  320 \[
  321 \pi_x\in\IP\Rightarrow \pi_x=\pi_x P\Rightarrow \pi_x=\pi_xP^m.
  322 \]
  323 Επομένως
  324 \[
  325 \pi_x(y)=\sum_{z\in\X}\pi_x(z)p^{(m)}(z,y)\ge \pi_x(x)p^{(m)}(x,y)>0.
  326 \]
  327 \begin{corollary}\label{precclass}
  328 H γνήσια επαναληπτικότητα είναι ιδιότητα κλάσης, δηλαδή αν η κατάσταση $x$ είναι γνησίως επαναληπτική και $y\in{C}_x$ τότε και η $y$ είναι γνησίως επαναληπτική.
  329 \end{corollary}
  330 {\bf Απόδειξη:} Προκύπτει αμέσως από το Πόρισμα \ref{support} αφού
  331 \[
  332 \pi_x\in\IP \quad\text{και}\quad \pi_x(y)>0\ \Rightarrow\  \E_y\big[T_y^+\big]<+\infty.
  333 \]
  334 \CQFD\\
  335 Με βάση το παραπάνω Πόρισμα έχει νόημα να κάνουμε λόγο για γνησίως επαναληπτικές κλάσεις. Σημειώστε ότι εφόσον οι ανοιχτές κλάσεις μιας αλυσίδας είναι παροδικές τότε κάθε γνησίως επαναληπτική κλάση είναι κλειστή. Το ακόλουθο Πόρισμα 
  336 συνοψίζει μια ικανή και αναγκαία συνθήκη για το πότε μια κλειστή κλάση είναι γνησίως επαναληπτική και είναι συχνά ένας εύκολος τρόπος να αποδείξει κανείς την γνήσια επαναληπτικότητα μιας κλειστής κλάσης. Σημειώστε ότι για τον σκοπό αυτό αρκεί να περιορίσουμε την αλυσίδα σε αυτήν την κλειστή κλάση, οπότε η αλυσίδα που θα προκύψει θα είναι μη υποβιβάσιμη. 
  337 \begin{corollary}\label{nsPR}
  338 Μια μη υποβιβάσιμη μαρκοβιανή αλυσίδα είναι γνησίως επαναληπτική αν και μόνο αν έχει αναλλοίωτη κατανομή.
  339 \end{corollary}
  340 {\bf Απόδειξη:} Το Θεώρημα \ref{explicit} μας εξασφαλίζει την ύπαρξη μιας αναλλοίωτης κατανομής $\pi_x$ αν υπάρχει μια επαναληπτική κατάσταση $x$. Αντίστροφα, αν η αλυσίδα έχει αναλλοίωτη κατανομή $\pi$ τότε από το Πόρισμα \ref{prexist} η αλυσίδα θα έχει μια γνησίως επαναληπτική κατάσταση. Εφόσον η αλυσίδα είναι μη υποβιβάσιμη, από το Πόρισμα \ref{precclass} όλες οι καταστάσεις της θα είναι γνησίως επαναληπτικές.\CQFD
  341 \begin{corollary}\label{finir}
  342 Μια μη υποβιβάσιμη μαρκοβιανή αλυσίδα σ' έναν πεπερασμένο χώρο καταστάσεων είναι γνησίως επαναληπτική.
  343 \end{corollary}
  344 {\bf Απόδειξη:} Θεωρούμε ένα $x\in\X$, και ορίζουμε $T_x^+=\inf\{k>0: X_k=x\}$ τον χρόνο πρώτης επιστροφής στην κατάσταση $x$. Εφόσον η αλυσίδα είναι μη υποβιβάσιμη ολόκληρος ο $\X$ είναι μια κλειστή και πεπερασμένη, και άρα επαναληπτική κλάση. Έτσι, $\Px{T_x^+<\infty}=1$. Ορίζουμε την $\lambda:\X\to[0,\infty]$ με 
  345 \[
  346 \lambda(y)=\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big],
  347 \]
  348 Από την απόδειξη του Θεωρήματος \ref{explicit} έχουμε ότι $\lambda=\lambda P$, ενώ $\lambda(x)=1$. Θα δείξουμε ότι $\lambda(y)<\infty$ για κάθε $y\in\X$. Εφόσον η $x$ είναι προσβάσιμη από την $y$ επιλέγουμε $m\in\N$ τέτοιο ώστε $p^{(m)}(y,x)>0$. Έτσι
  349 \[
  350 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.
  351 \]
  352 Αν ορίσουμε τώρα $Z=\sum_{y\in\X}\lambda(y)\in(1,+\infty)$, και $\pi(y)=\lambda(y)/Z$ για κάθε $y\in\X$, εύκολα επιβεβαιώνουμε ότι $\pi\in\IP$ και άρα από το Πόρισμα \ref{nsPR} η αλυσίδα είναι γνησίως επαναληπτική.\CQFD\\
  353 \ \\
  354 Έχουμε ως τώρα δει ότι οποιαδήποτε αναλλοίωτη κατανομή δίνει μηδενικό βάρος σε κλάσεις που δεν είναι γνησίως επαναληπτικές (Πόρισμα \ref{support}), ενώ για κάθε γνησίως επαναληπτική κλάση έχουμε κατασκευάσει μια αναλλοίωτη κατανομή $\pi_x$ που στηρίζεται στις καταστάσεις αυτής της κλάσης (Θεωρήματα \ref{explicit} και \ref{positiveweight}.) Θα δείξουμε στην συνέχεια ότι η αναλλοίωτη κατανομή που στηρίζεται σε μια γνησίως επαναληπτική κλάση είναι μοναδική. Όπως και στο προηγούμενο Πόρισμα, περιορίζοντας την αλυσίδα σε μια γνησίως επαναληπτική, και επομένως κλειστή κλάση, αρκεί να υποθέσουμε ότι η αλυσίδα μας είναι μη υποβιβάσιμη.
  355 \begin{theorem}\label{uniqueinv}
  356 Αν η $\xn$ είναι μια μη υποβιβάσιμη γνησίως επαναληπτική αλυσίδα τότε έχει μοναδική αναλλοίωτη κατανομή.
  357 \end{theorem}
  358 {\bf Απόδειξη:} H ύπαρξη μιας τουλάχιστον αναλλοίωτης κατανομής εξασφαλίζεται από το Θεώρημα \ref{explicit}. Θα αποδείξουμε εδώ την μοναδικότητα. Έστω λοιπόν $\pi$ μια αναλλοίωτη κατανομή της $\xn$. \\
  359 \ \\
  360 Θεωρούμε ένα $x\in\X$ και ορίζουμε την αναλλοίωτη κατανομή $\pi_x$ όπως στο Θεώρημα \ref{explicit}. Θα δείξουμε ότι $\pi(y)=\pi_x(y)$ για κάθε κατάσταση $y\in\X$. Εφόσον η αλυσίδα είναι μη υποβιβάσιμη η $x$ θα είναι προσβάσιμη από την $y$. Υπάρχει επομένως $m\in\N$ τέτοιο ώστε $p^{(m)}(y,x)>0$. Έχουμε τώρα
  361 \begin{align*}
  362 0&=\pi(x)-\pi(x)=\pi(x)-\frac{\pi(x)}{\pi_x(x)}\pi_x(x)\\
  363 &=\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)\\
  364 &=\sum_{z\in\X}\Big(\pi(z)-\pi(x)\frac{\pi_x(z)}{\pi_x(x)}\Big)p^{(m)}(z,x).
  365 \end{align*}
  366 Από το Λήμμα \ref{idcomparison} κάθε προσθετέος στο παραπάνω άθροισμα είναι μεγαλύτερος ή ίσος του μηδενός. Για να είναι το άθροισμα 0 θα πρέπει όλοι οι προσθετέοι να είναι ίσοι με 0. Ειδικώτερα,
  367 \[
  368 \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).
  369 \]
  370 Εφόσον η $y$ είναι αυθαίρετα επιλεγμένη έχουμε ότι
  371 \beq
  372 \pi(y)=\frac{\pi(x)}{\pi_x(x)}\pi_x(y) \quad\text{για κάθε }y\in\X.
  373 \label{com1}
  374 \eeq
  375 Αθροίζοντας τις παραπάνω σχέσεις σε όλα τα $y\in\X$ έχουμε
  376 \[
  377 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)},
  378 \]
  379 και άρα η (\ref{com1}) γίνεται $\pi(y)=\pi_x(y)$ για κάθε $y\in\X$.\CQFD\\
  380 \ \\
  381 \noindent
  382 {\bf Παρατήρηση:} Μια άμεση συνέπεια του Θεωρήματος \ref{uniqueinv} είναι ότι αν οι καταστάσεις $x,y$ ανήκουν σε μια γνησίως επαναληπτική κλάση ${C}$ τότε $\pi_x\equiv\pi_y$. Έχει λοιπόν νόημα να μιλάμε για την μοναδική αναλλοίωτη κατανομή $\pi_{C}$ που αντιστοιχεί στην κλάση ${C}$. Το τελικό συμπέρασμα αυτής της παραγράφου είναι ότι κάθε αναλλοίωτη κατανομή 
  383 είναι ένας κυρτός συνδυασμός τέτοιων κατανομών.
  384 \begin{theorem}
  385 Έστω ${\cal R}$ το σύνολο των γνησίως επαναληπτικών κλάσεων μιας μαρκοβιανής αλυσίδας $\xn$ με πίνακα πιθανοτήτων μετάβασης $P$. Τότε 
  386 \[
  387 \IP=co\{\pi_{C}: {C}\in{\cal R}\}\equiv\big\{\sum_{C\in{\cal R}}\alpha(C)\pi_C:\ \alpha(C)\ge 0\ \forall C\in{\cal R}, \text{ και } \sum_{C\in{\cal R}}\alpha(C)=1\big\}.
  388 \]
  389 \end{theorem}
  390 {\bf Απόδειξη:} Ας υποθέσουμε πρώτα ότι $\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$ ενώ
  391 \[
  392 \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.
  393 \]
  394 Επομένως $\pi\in\MX$. Για να δείξουμε ότι $\pi\in\IP$ και άρα $co\{\pi_{C}: {C}\in{\cal R}\}\subset\IP$ παρατηρούμε ότι
  395 \[
  396 \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.
  397 \]
  398 Θα δείξουμε τώρα ότι $\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$ έχουμε
  399 \[
  400 \left.\mu\right|_C\big[A\big]=\mu\big[A\,|\,C\big]=\frac{\mu\big[A\cap C\big]}{\mu\big[C\big]}.
  401 \]
  402 Θα δείξουμε ότι $\left.\mu\right|_C=\pi_C$. Η $\left.\mu\right|_C$ είναι μια κατανομή που στηρίζεται στην κλειστή κλάση $C$ και από το Θεώρημα \ref{uniqueinv} για να την ταυτίσουμε με την $\pi_C$ αρκεί να δείξουμε ότι είναι αναλλοίωτη. Πράγματι, για κάθε $x\in C$ έχουμε $p(y,x)=0$ για κάθε $y\notin C$ και άρα
  403 \[
  404 \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).
  405 \]
  406 Δείξαμε λοιπόν ότι αν $\mu\big[C\big]>0$ τότε $\left.\mu\right|_C\equiv\pi_C$. Αν $\mu\big[C\big]=0$ ορίζουμε $\left.\mu\right|_C=\pi_C$. Από το Πόρισμα \ref{support} έχουμε ότι
  407 \[
  408 \mu\big[\bigcup_{C\in{\cal R}}C\big] = 1.
  409 \]
  410 Έτσι, για κάθε $A\subset\X$
  411 \[
  412 \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],
  413 \]
  414 και άρα
  415 \[
  416 \mu=\sum_{C\in{\cal R}}\mu\big[C\big]\pi_C
  417 \]
  418 Παρατηρήστε ότι $\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}\}$.\CQFD
  419 \section{Παραδείγματα}
  420 Στην προηγούμενη παράγραφο μελετήσαμε την δομή των αναλλοίωτων κατανομών μιας μαρκοβιανής αλυσίδας. Είδαμε ότι για κάθε γνησίως επαναληπτική κλάση της $C$ υπάρχει μια μοναδική αναλλοίωτη κατανομή $\pi_C$ της αλυσίδας που στηρίζεται στην $C$ (δηλαδή $x\notin C\Rightarrow \pi_C(x)=0$) και ότι κάθε αναλλοίωτη κατανομή της αλυσίδας μπορεί να γραφτεί σαν ένας κυρτός συνδυασμός των κατανομών $\pi_C$. Είδαμε όμως και αρκετούς τρόπους για να χαρακτηρίσουμε τις $\pi_C$. Έτσι, αν έχουμε μια μη υποβιβάσιμη γνησίως επαναληπτική μαρκοβιανή αλυσίδα $\xn$ με πίνακα πιθανοτήτων μετάβασης $P$ (όπως είναι οποιαδήποτε μαρκοβιανή αλυσίδα περιορισμένη σε μια γνησίως επαναληπτική της κλάση) έχουμε τους ακόλουθους χαρακτηρισμούς για την μοναδική αναλλοίωτη κατανομή της $\pi$.
  421 \begin{enumerate}
  422 \item
  423 Η $\pi$ είναι λύση του προβλήματος
  424 \[
  425 \begin{cases} &\pi=\pi P\\&\sum_{x\in\X}\pi(x)=1\end{cases}
  426 \]
  427 \item Για κάθε $x\in\X$, αν $T_x^+=\inf\{k>0: X_k=x\}$ έχουμε
  428 \[
  429 \pi(x)=\frac{1}{\Ex{T_x^+}}.
  430 \]
  431 \item
  432 Για κάθε $x,y\in\X$ έχουμε
  433 \[
  434 \pi(y)=\pi(x)\ \E_x\Big[\sum_{k=1}^{T_x^+}\mathbbm{1}\{X_k=y\}\Big].
  435 \]
  436 \end{enumerate}
  437 Μπορεί κανείς να χρησιμοποιήσει έναν τρόπο για να υπολογίσει την αναλλοίωτη κατανομή της αλυσίδας και να πάρει από τους άλλους τρόπους  ενδεχομένως χρήσιμες πληροφορίες.
  438 \begin{example}
  439 Ένα έντομο κινείται στις κορυφές $V$ ενός κανονικού $\nu$-γώνου. Σε κάθε βήμα του μετακινείται σε μια από τις δύο γειτονικές κορυφές, με πιθανότητα $p\in(0,1)$ κατά την φορά των δεικτών του ρολογιού και με πιθανότητα $1-p$ αντίστροφα από τους δείκτες του ρολογιού. Ποιος είναι ο αναμενόμενος αριθμός βημάτων μέχρι να επιστρέψει στην αρχική του θέση?\\
  440 \ \\
  441 Η αλυσίδα που καταγράφει την θέση του εντόμου είναι μη υποβιβάσιμη, αφού το έντομο μπορεί να επισκεφτεί όλες τις καταστάσεις και να επιστρέψει στην αρχική του κατάσταση κάνοντας $\nu$ βήματα κατά την φορά των δεικτών του ρολογιού, ενδεχόμενο το οποίο έχει πιθανότητα $p^\nu>0$. Εφόσον $|V|<+\infty$ η αλυσίδα θα είναι γνησίως επαναληπτική και άρα θα έχει μοναδική αναλλοίωτη κατανομή $\pi$. Στο συγκεκριμένο παράδειγμα δεν είναι δύσκολο να μαντέψει κανείς ότι λόγω συμμετρίας η μοναδική αναλλοίωτη κατανομή θα είναι η ομοιόμορφη κατανομή στις κορυφές του $\nu$-γώνου
  442 \[
  443 \pi(x)=\frac{1}{\nu}\quad\text{για κάθε }x\in V.
  444 \]
  445 Πράγματι, για κάθε $x\in V$
  446 \[
  447 \sum_{y\in V}\pi(y)p(y,x)= \sum_{y\in V}\frac{1}{\nu}p(y,x)=\frac{1}{\nu}\big(p+(1-p)\big)=\frac{1}{\nu}=\pi(x).
  448 \]
  449 Επομένως
  450 \[
  451 \Ex{T_x^+}=\frac{1}{\pi(x)}=\nu.
  452 \]
  453 \CQFD\\
  454 Το προηγούμενο παράδειγμα μπορεί να γενικευτεί κατά τον ακόλουθο τρόπο. Θα λέμε ότι ένας στοχαστικός πίνακας $P$ είναι {\em διπλά στοχαστικός} αν $\sum_{x\in\X}p(x,y)=1$ για κάθε $y\in\X$. Έτσι σε έναν διπλά στοχαστικό πίνακα και το άθροισμα των στοιχείων του κατά στήλη είναι ίσο με 1. Παρατηρήστε ότι ένας συμμετρικός πίνακας πιθανοτήτων μετάβασης είναι πάντα διπλά στοχαστικός.
  455 \begin{example}
  456 Μια μη υποβιβάσιμη μαρκοβιανή αλυσίδα που κινείται σε έναν πεπερασμένο χώρο καταστάσεων $\X$ και έχει διπλά στοχαστικό πίνακα πιθανοτήτων μετάβασης έχει μοναδική αναλλοίωτη κατανομή την ομοιόμορφη κατανομή στον $\X$.\\
  457 \ \\
  458 Από το Θεώρημα \ref{uniqueinv}, η αλυσίδα έχει μοναδική αναλλοίωτη κατανομή. Αρκεί λοιπόν να επαληθεύσουμε ότι η ομοιόμορφη κατανομή $\pi:\X\to[0,1]$ με $\pi(x)=\frac{1}{|\X|}$ είναι αναλλοίωτη. Πράγματι, για κάθε $x\in\X$ έχουμε
  459 \[
  460 \sum_{y\in\X} \pi(y)p(y,x)=\frac{1}{|\X|}\sum_{y\in\X}p(y,x)=\frac{1}{|\X|}=\pi(x),
  461 \]
  462 όπου η δεύτερη ισότητα προκύπτει επειδή οπίνακας πιθανοτήτων μετάβασης είναι διπλά στοχαστικός. Επίσης,
  463 \[
  464 \sum_{x\in\X}\pi(x)=\sum_{x\in\X}\frac{1}{|\X|}=\frac{1}{|\X|}|\X|=1,
  465 \]
  466 και άρα $\pi\in\IP$.\CQFD
  467 \end{example}
  468 \end{example}
  469 \begin{example}
  470 Σ' ένα ράφι της βιβλιοθήκης σας υπάρχουν τρία βιβλία: \en{Algebra, Basic Topology, Calculus}, που θα συμβολίζουμε με \en{A,B,C} για συντομία. Κάθε πρωί παίρνετε τυχαία ένα βιβλίο από τη θέση του, με πιθανότητα $p,q,r$ αντίστοιχα. Υποθέτουμε $p,q,r>0$ με $p+q+r=1$. Όταν τελειώνετε το διάβασμά σας για την ημέρα το ξαναβάζετε στο ράφι στην αριστερότερη θέση. Η διάταξη των βιβλίων είναι μια μαρκοβιανή αλυσίδα στο χώρο $\X$ των μεταθέσεων των συμβόλων $\{A,B,C\}$. Αν κάποια στιγμή τα βιβλία είναι τοποθετημένα με αλφαβητική σειρά βρείτε τον αναμενόμενο αριθμό ημερών μέχρι τα βιβλία να ξαναβρεθούν τοποθετημένα με αλφαβητική σειρά. Πόσες κατά μέση τιμή ημέρες θα διαβάσετε το βιβλίο \en{Calculus} ενδιάμεσα σε αυτές τις στιγμές.\\
  471 \ \\ 
  472 Ας απαριθμήσουμε τις δυνατές καταστάσεις με την εξής σειρά $$\X=\{ABC,CAB,BCA,BAC,ACB,CBA\}.$$ Ο πίνακας πιθανοτήτων μετάβασης της αλυσίδας είναι ο
  473 \[
  474 P=\left(\begin{array}{cccccc}p&r&0&q&0&0\\0&r&q&0&p&0\\p&0&q&0&0&r\\p&0&0&q&0&r\\0&r&0&q&p&0\\0&0&q&0&p&r\end{array}\right).
  475 \]
  476 Το ότι η αλυσίδα είναι μη υποβιβάσιμη είναι διαισθητικά φανερό. Μπορείτε να δείτε ότι όποια κι αν είναι η αρχική της κατάσταση, αν επιλέξετε τις δυο πρώτες μέρες το δεξιότερο βιβλίο, την τρίτη μέρα το μεσαίο βιβλίο, και τις δυο επόμενες πάλι το δεξιότερο βιβλίο (ενδεχόμενο το οποίο έχει θετική πιθανότητα) τότε η διάταξη των βιβλίων στο ράφι θα έχει περάσει από όλες τις δυνατές καταστάσεις της. Εφόσον ο χώρος καταστάσεων είναι πεπερασμένος όλες οι καταστάσεις θα είναι γνησίως επαναληπτικές. Για να βρούμε την μοναδική αναλλοίωτη κατανομή $\pi$ λύνουμε το ομογενές σύστημα εξισώσεων $\pi=\pi P$. Ας δούμε τις εξισώσεις που αφορούν σε καταστάσεις με το $A$ ως αριστερότερο βιβλίο:
  477 \begin{align}
  478 \pi(ABC)&=p\pi(ABC)+p\pi(BAC)+p\pi(BCA)\label{bc}\\
  479 %\Leftrightarrow \pi(ABC)=\frac{p}{1-p}\big(\pi(BAC)+\pi(BCA)\big),
  480 \pi(ACB)&=p\pi(ACB)+p\pi(CAB)+p\pi(CBA).\label{cb}
  481 \end{align}
  482 Αν $S_A=\{ABC,ACB\},$  προσθέτοντας κατά μέλη βρίσκουμε $\pi(S_A)=p\sum_{x\in\X}\pi(x)=p.$
  483 Όμοια, αν $\ S_B=\{BAC,BCA\}$ και $\ S_C=\{CAB,CBA\}$ τότε $\pi(S_B)=q,\ \pi(S_C)=r$. Από τις (\ref{bc}), (\ref{cb}) παίρνουμε τελικά ότι 
  484 \begin{equation}
  485 \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}.
  486 \label{A*}
  487 \end{equation}
  488 Οι πιθανότητες των άλλων καταστάσεων βρίσκονται με ανάλογο τρόπο, οπότε τελικά
  489 \[
  490 \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}).
  491 \]
  492 Έχοντας βρει την αναλλοίωτη κατανομή της αλυσίδας μπορούμε εύκολα να απαντήσουμε τα υπόλοιπα ερωτήματα. Έτσι, αν $T_{ABC}^+=\inf\{k>0: X_k=ABC\}$ τότε
  493 \[
  494 \E\big[T_{ABC}^+\,|\,X_0=ABC\big]=\frac{1}{\pi(ABC)}=\frac{1-p}{pq}.
  495 \]
  496 Κάθε φορά που διαβάζετε το βιβλίο \en{Calculus} το τοποθετείτε αριστερά οπότε η αλυσίδα περνά από μια από της καταστάσεις του $S_C$. Έτσι,
  497 \[
  498 \E\Big[\sum_{k=1}^{T_{ABC}^+}\mathbbm{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\CQFD
  499 \]
  500 \end{example}
  501 \section{Ασκήσεις}
  502 \begin{exercise}
  503 H $\{X_n\}_{n\in\N_0}$ είναι μια μαρκοβιανή αλυσίδα στο χώρο καταστάσεων $\X=\{1,2,3,4\}$ με πίνακα μετάβασης 
  504 \[
  505 P=\left(\begin{array}{cccc} 0&1/2&1/3&1/6\\1/2&0&1/4&1/4\\0&1/2&0&1/2\\1/2&1/3&1/6&0\end{array}\right).
  506 \] 
  507 α) Βρείτε την αναλλοίωτη κατανομή της αλυσίδας.\\
  508 β) Αν $X_0=1$ υπολογίστε τον αναμενόμενο χρόνο πρώτης επιστροφής $T_1^+=\inf\{k>0:\ X_k=1\}$ στην κατάσταση 1.\\
  509 γ) Υπολογίστε τον αναμενόμενο αριθμό επισκέψεων στην κατάσταση 3 μέχρι τη συμπλήρωση 93 επιστροφών στην κατάσταση 1.
  510 \end{exercise}
  511 \begin{exercise}
  512 Στο διπλανό σχήμα φαίνεται η κάτοψη ενός σπιτιού με 5 δωμάτια: κουζίνα (Κ), βιβλιοθήκη (Β), σαλόνι (Σ), υπνοδωμάτιο (Υ), και μπάνιο (Μ), και οι πόρτες που τα συνδέουν. \\[1mm]
  513 \begin{minipage}[b]{0.72\linewidth}
  514 Ένα έντομο που ζει στο σπίτι, κάθε βράδυ διασχίζει τυχαία μια από τις πόρτες του δωματίου που βρίσκεται, και παραμένει στο δωμάτιο που οδηγεί η πόρτα μέχρι το επόμενο βράδυ. Αρχικά το έντομο βρίσκεται στο μπάνιο.\\
  515 α) Αν $\{X_n:\ n=0,1,2,\ldots\}$ είναι η μαρκοβιανή αλυσίδα στο χώρο καταστάσεων \{Κ,Β,Σ,Υ,Μ\} που περιγράφει τη θέση του εντόμου κάθε μέρα, βρείτε τον πίνακα πιθανοτήτων μετάβασης ${P}$ της $\{X_n\}$.\\
  516 β) Βρείτε όλες τις αναλλοίωτες κατανομές της $\{X_n\}$.\\
  517 γ) Υπολογίστε τον αναμενόμενο αριθμό ημερών μέχρι την πρώτη επιστροφή του εντόμου στο μπάνιο.\\
  518 \end{minipage}
  519 \begin{minipage}[b]{0.26\linewidth}
  520 \includegraphics[width=0.95\linewidth]{Maze}
  521 \end{minipage}\\
  522 δ) Υπολογίστε τον αναμενόμενο αριθμό ημερών που θα περάσει το έντομο στο σαλόνι μέχρι την πρώτη του επιστροφή στο μπάνιο.\\
  523 ε) Αν ένα άλλο έντομο αρχικά βρίσκεται στην κουζίνα και μετακινείται κάθε μέρα όπως το πρώτο, ποια είναι η πιθανότητα κάποια μέρα τα δύο έντομα να βρεθούν στο ίδιο δωμάτιο? 
  524 \end{exercise}
  525 \begin{exercise}
  526 Ένας παντοπώλης εφοδιάζεται κάθε πρωί με ένα πακέτο μπισκότα. Έχει παρατηρήσει ότι η ημερήσια ζήτηση είναι μια τυχαία μεταβλητή $X$ με κατανομή $\PP{X=0}=\frac{1}{4}$, $\PP{X=1}=\frac{1}{2}$, $\PP{X=2}=\frac{1}{6}$, $\PP{X=3}=\frac{1}{12}$. Περιγράψτε την ποσότητα από μπισκότα που έχει στο παντοπωλείο κάθε βράδυ σαν μια μαρκοβιανή αλυσίδα και βρείτε την αναλλοίωτη κατανομή της. Αν χτες το βράδυ δεν είχε μείνει κανένα πακέτο μπισκότα στο παντοπωλείο, ποιος είναι ο αναμενόμενος αριθμός ημερών μέχρι την επόμενη φορά που το παντοπωλείο θα μείνει χωρίς μπισκότα?
  527 \end{exercise}
  528 \begin{exercise}
  529 Μια μαρκοβιανή αλυσίδα στον $\X=\N_0$ μετατοπίζεται ένα βήμα προς τα αριστερά όταν δεν βρίσκεται στο 0, και όταν φτάσει στο 0 κάνει ένα άλμα που ακολουθεί γεωμετρική κατανομή με παράμετρο $q\ (0<q<1)$. Υπολογίστε την αναλλοίωτη κατανομή της με τρεις διαφορετικούς τρόπους.
  530 \end{exercise}
  531 \begin{exercise}
  532 Μια μαρκοβιανή αλυσίδα στον $\X=\{0,1,2,\ldots\}$ έχει πιθανότητες μετάβασης $p(k,k+1)=p<1,\ p(k,0)=1-p,\ \forall k\in\X$.
  533 Βρείτε την αναλλοίωτη κατανομή της. Ποια είναι η αναμενόμενη τιμή του χρόνου που μεσολαβεί ανάμεσα σε δύο διαδοχικές επισκέψεις στο 3? Ποιος είναι ο αναμενόμενος αριθμός επισκέψεων στο 0 ανάμεσα σε δύο διαδοχικές επισκέψεις στο 3?
  534 \end{exercise}
  535 \begin{exercise}
  536 Ο  κύριος Χ αντιμετωπίζει ένα σοβαρό πρόβλημα μνήμης. Κάθε νύχτα ξεχνά ένα μέρος από τα πρόσωπα που γνωρίζει. Συγκεκριμένα, αν θυμάται $k$ πρόσωπα πριν πέσει για ύπνο, το πλήθος των προσώπων που εξακολουθεί να θυμάται μόλις ξυπνήσει μπορεί να είναι $0,1,2,\ldots,k$, καθένα με πιθανότητα $1/(k+1)$. Ο γιατρός που τον παρακολουθεί του μαθαίνει κάθε μέρα ένα πρόσωπο, διαφορετικό από αυτά που θυμάται. Αν $X_n$ είναι το πλήθος των προσώπων που ο κύριος Χ θυμάται το βράδυ της $n$-στης ημέρας\\[2mm]
  537 α) Βρείτε τις πιθανότητες μετάβασης $p(j,k),\ j,k\in\N$ της αλυσίδας $X_n$.\\
  538 β) Δείξτε ότι η μοναδική αναλλοίωτη κατανομή της $\{X_n\}$ είναι η $\pi:\N\to[0,1]$ με $\pi(k)=\frac{1}{e(k-1)!}$.\\
  539 γ) Αν κάποιο βράδυ ο κύριος Χ θυμάται 3 πρόσωπα πριν πέσει για ύπνος ποιος είναι ο αναμενόμενος χρόνος που θα μεσολαβήσει μέχρι το επόμενο βράδυ που θα θυμάται πάλι 3 πρόσωπα? 
  540 \end{exercise}
  541 \begin{exercise}
  542 Αν ${\cal R}\neq\emptyset$ είναι το σύνολο των γνησίως επαναληπτικών κλάσεων μιας αλυσίδας $\{X_n\}_n$ και $\pi\in\IP$,  δείξτε ότι υπάρχει μόνο ένας τρόπος να γράψουμε την $\pi$ ως
  543 \[
  544 \pi=\sum_{C\in{\cal R}} \alpha(C)\pi_C.
  545 \]
  546 \end{exercise}
  547 \section{Αριθμητικά πειράματα}
  548 \begin{exercise}
  549 Σ' αυτήν την άσκηση θα δούμε πώς μπορούμε να κάνουμε γραφικές παραστάσεις με την \en{Python}. Κατεβάστε το πρόγραμμα 
  550 \en{{\tt example\_plot.py}} και αποθηκεύστε το στον κατάλογο που θα δουλέψετε. Τρέξτε το πρόγραμμα. Το πρόγραμμα τυπώνει 
  551 την γραφική παράσταση της συνάρτησης $x\mapsto 32x^3$ στο διάστημα (0,6) σε κανονική και λογαριθμική (με βάση το 2) κλίμακα.\\
  552 α) Γιατί σε λογαριθμική κλίμακα βλέπουμε μια ευθεία?\\
  553 β) Εκτιμήστε γραφικά την κλίση της ευθείας και το σημείο που τέμνει τον άξονα $y'y$.\\[2mm]
  554 Για τα επόμενα 2 ερωτήματα ίσως σας βοηθήσει να έχετε ανοίξει τον κώδικα με έναν επεξεργαστή κειμένου σε ένα τερματικό, και να εκτελείτε το πρόγραμμα από ένα άλλο τερματικό.\\[2mm]
  555 γ) Αλλάξτε την συνάρτηση σε $x\mapsto 8x^3$ και ξανατρέξτε το πρόγραμμα. Πώς αλλάζει το διάγραμμα σε λογαριθμική κλίμακα?\\
  556 δ) Αλλάξτε την συνάρτηση σε $x\mapsto 8x^2$ και ξανατρέξτε το πρόγραμμα. Πώς αλλάζει το διάγραμμα σε λογαριθμική κλίμακα?\\[2mm]
  557 Κλείστε τώρα το παράθυρο γραφικών και αλλάξτε το πρόγραμμα ώστε να ξαναπάρετε την γραφική παράσταση της $x\mapsto 32x^3$.
  558 Αφαιρέστε το σύμβολο $\#$ που καθιστά σχoλιασμό τις δύο γραμμές στο τέλος του προγράμματος
  559 \selectlanguage{english}
  560 \begin{verbatim} a,b = np.polyfit(newx,newy,1) \end{verbatim} 
  561 \begin{verbatim} print "The fitted line is y=%.2f*x+%.2f " % (a,b) \end{verbatim} 
  562 \selectlanguage{greek}
  563 H πρώτη υπολογίζει τους συντελεστές της ευθείας $y=ax+b$ που προσαρμόζεται καλύτερα 
  564 στα σημεία \en{{\tt (newx,newy)}}. Η παράμετρος 1 δηλώνει ότι θέλουμε να προσαρμόσουμε ένα 
  565 πολυώνυμο βαθμού 1, δηλαδή μια ευθεία. Η δεύτερη γραμμή απλά τυπώνει το αποτέλεσμα (με δύο δεκαδικά ψηφία) για τον χρήστη. Ξανατρέξτε το πρόγραμμα.\\[2mm]
  566 ε) Συμφωνεί το αποτέλεσμα για τα $a,b$ με αυτό που βρήκατε στο ερώτημα (β)?
  567 \end{exercise}
  568 \begin{exercise}
  569 Κατεβάστε το πρόγραμμα \en{{\tt variance.py}} και αποθηκεύστε το στον κατάλογο που θα δουλέψετε. \\[2mm]
  570 Το πρόγραμμα προσομοιώνει μια αλυσίδα στον χώρο καταστάσεων $\X=\{1,2,3,4,5\}$, και υπολογίζει με την μέθοδο \en{Monte Carlo} τον αναμενόμενο χρόνο επιστροφής στην κατάσταση 1, $\EE{T_1^+\,|\,X_0=1}$, όπου
  571 \[
  572 T_1^+=\inf\{k>0: X_k=1\}.
  573 \]
  574 H εκτίμηση για την $\EE{T_1^+\,|\,X_0=1}$ λαμβάνεται προσομοιώνοντας την αλυσίδα $N$ φορές, παίρνοντας $N$ ανεξάρτητα δείγματα $t_1,\ldots,t_N$ του χρόνου επιστροφής στο 1, και παίρνοντας τον μέσο όρο αυτών των δειγμάτων.
  575 O νόμος των μεγάλων αριθμών εγγυάται ότι ο μέσος όρος αυτών των $N$ ανεξάρτητων δειγμάτων της τυχαίας μεταβλητής $T_1^+$ είναι για αρκετά μεγάλο $N$ κοντά στην $\EE{T_1^+\,|\,X_0=1}$ με μεγάλη πιθανότητα. Θα καλούμε την
  576 \[
  577 Ε_N=\frac{t_1+t_2+\cdots+t_N}{N}
  578 \]
  579 εκτιμήτρια \en{Monte Carlo} της αναμενόμενης τιμής $\EE{T_1^+\,|\,X_0=1}$. Φυσικά η $E_N$ είναι μια τυχαία μεταβλητή και αν ξανακάνουμε το πείραμα θα πάρουμε μια διαφορετική εκτίμηση. \\[2mm]
  580 α) Τρέξτε το πρόγραμμα μερικές φορές και δείτε πόσο διαφέρουν οι εκτιμήσεις που παίρνουμε κάθε φορά για την $\EE{T_1^+\,|\,X_0=1}$. Επαναλάβετε για $N=2^6,2^7,\ldots,2^{12}$. Φαίνεται να διαφέρουν λιγότερο οι διαφορετικές εκτιμήσεις καθώς μεγαλώνει το $N$?\\[2mm]
  581 Σκοπός αυτής της άσκησης είναι να βρούμε υπολογιστικά πώς επηρεάζεται η διασπορά της εκτιμήτριας $E_N$ από το πλήθος των επαναλήψεων $N$.\\[2mm]
  582 β) Φτιάξτε έναν βρόχο που θα κάνει $M=30$ εκτιμήσεις της $\EE{T_1^+\,|\,X_0=1}$ για κάθε δεδομένη τιμή του $N$ και αποθηκεύστε αυτές τις $Μ$ εκτιμήσεις στην λίστα \en{mcestimates}.\\[2mm]
  583 γ) Υπολογίστε την δειγματική μέση τιμή και την δειγματική διασπορά αυτών των εκτιμήσεων αφαιρώντας τον σχολιασμό από τις εντολές\\[1mm]
  584 \en{{\tt sample\_mean = float( sum(mcestimates) ) / M}}\\[0.5mm]
  585 \en{{\tt squared\_distance\_from\_mean = [ (e - sample\_mean)**2 for e in mcestimates ]}}\\[0.5mm]
  586 \en{{\tt sample\_variance= float(sum ( squared\_distance\_from\_mean )) / (M-1)}}\\[0.5mm]
  587 %\selectlanguage{greek}
  588 που βρίσκονται στο τέλος του προγράμματος.\\[2mm]
  589 δ) Φτιάξτε έναν βρόχο που κάνει τον παραπάνω υπολογισμό για $N=2^6,2^7,\ldots,2^{14}$ και παραστήστε γραφικά πώς εξαρτάται η δειγματική μέση τιμή και η δειγματική τυπική απόκλιση από το $N$.\\[2mm]
  590 ε) Υπολογίστε θεωρητικά την $\EE{T_1^+\,|\,X_0=1}$. Συμφωνεί το αριθμητικό αποτέλεσμα που βρήκατε με την θεωρητική τιμή?\\[2mm]
  591 στ) Σχεδιάστε σε λογαριθμική κλίμακα πώς εξαρτάται η δειγματική τυπική απόκλιση της εκτιμήτριας \en{Monte Carlo} από το $N$. Ποια είναι η κλίση της ευθείας στο λογαριθμικό διάγραμμα? Συμφωνεί αυτό που βρήκατε με το κεντρικό οριακό θεώρημα?
  592 \end{exercise}
  593 
  594 \end{document}
  595 
  596