1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
\documentclass[11pt]{article}
\usepackage[english,greek]{babel}
\usepackage[utf8x]{inputenc}
\newcommand{\en}[1]{\textlatin{#1}}
\setlength\topmargin{-0.5in}
\setlength\textheight{23cm}
\setlength\oddsidemargin{-0.4in}
\setlength\textwidth{17cm}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{theorem}
\usepackage{graphicx}
\usepackage{pdfsync}
%\usepackage{showlabels}
\usepackage{bbm}
\theorembodyfont{\upshape}
\newtheorem{exercise}{Άσκηση}
\newtheorem{theorem}{Θεώρημα}
\newtheorem{example}{Παράδειγμα}
\newtheorem{corollary}{Πόρισμα}
\newtheorem{lemma}{Λήμμα}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\X{\mathbb{X}}
\def\P{\mathbb{P}}
\def\E{\mathbb{E}}
\def\R{\mathbb{R}}
\def\MX{{\cal M}(\X)}
\def\xn{\{X_n\}_{n\in\N_0}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\bea{\begin{align}}
\def\ea{\end{align}}
\def\bea*{\begin{align*}}
\def\ea*{\end{align*}}
\def\CQFD{\hfill\hbox{\vrule\vbox to 8pt{\hrule width 8pt\vfill\hrule}\vrule}}
\def\half{\frac{1}{2}}
\def\IP{{\cal I}(P)}
\newcommand{\PP}[1]{\P\big[#1\big]}
\newcommand{\Px}[1]{\P_x\big[#1\big]}
\newcommand{\EE}[1]{\E\big[#1\big]}
\newcommand{\Ex}[1]{\E_x\big[#1\big]}
\begin{document}
\begin{center}
\Large {\bf KΕΦΑΛΑΙΟ \en{VI}. ΑΣΥΜΠΤΩΤΙΚΗ ΘΕΩΡΗΜΑΤΑ}
\end{center}
\noindent
\vspace{3mm}
\noindent
Στο κεφάλαιο αυτό θα μελετήσουμε την ασυμπτωτική συμπεριφορά μαρκοβιανών αλυσίδων, πώς δηλαδή συμπεριφέρονται σε βάθος χρόνου. Η κατανόηση της ασυμπτωτικής συμπεριφοράς τους είναι σημαντική για δύο κυρίως λόγους. Αφενός, υπάρχουν συστήματα που μοντελοποιούνται από μαρκοβιανές αλυσίδες και τα οποία, αφού περάσουν μια παροδική φάση, τελικά λειτουργούν σε μια κατάσταση ισορροπίας. Αφετέρου, αν θέλουμε να χρησιμοποιήσουμε ιδέες από τις μαρκοβιανές αλυσίδες για να φτιάξουμε υπολογιστικούς αλγορίθμους, είναι σημαντικό να ξέρουμε την συμπεριφορά του αλγορίθμου μετά από πολλές επαναλήψεις, να μπορούμε να εκτιμήσουμε πόσο γρήγορα συκλίνει, και πώς εξαρτάται το σφάλμα της προσέγγισης από το πλήθος των επαναλήψεων που θα εκτελέσουμε.
\section{Περιοδικότητα}\label{periodicity}
Ας θεωρήσουμε μια αλυσίδα που κινείται στις κορυφές ενός τετραγώνου ΑΒΓΔ. Ξεκινώντας από την κορυφή Α, σε κάθε βήμα μεταβαίνει σε μια από τις δύο γειτονικές της κορυφές με πιθναότητα 1/2. Εύκολα βλέπει κανείς ότι η μοναδική αναλλοίωτη κατανομή αυτής της αλυσίδας είναι η ομοιόμορφη κατανομή $\pi=(1/4,1/4,1/4,1/4)$, και όπως είδαμε στο προηγούμενο κεφάλαιο αυτό είναι μόνο υποψήφιο όριο της κατανομής $\pi_n$ της αλυσίδας μετά από $n$ βήματα. Δεν είναι δύσκολο να δει κανείς όμως ότι $\pi_n\not\rightarrow\pi$. Πράγματι, εφόσον η αλυσίδα ξεκινά από το Α, θα βρίσκεται οπωσδήποτε στο B ή στο Δ μετά από περιττό αριθμό βημάτων, και στο Α ή στο Γ μετά από άρτιο αριθμό βημάτων. Έτσι, π.χ.
\[
\pi_{2n}(B)=\PP{X_{2n}=B\,|\,X_0=A}=0\not\rightarrow 1/4.
\]
Βλέπουμε λοιπόν ότι στο παράδειγμά μας υπάρχουν υποσύνολα του χώρου καταστάσεων που είναι προσβάσιμα μόνο σε συγκεκριμένες χρονικές στιγμές. Αυτή η ιδιότητα αποτελεί κατά κάποιον τρόπο μια παθολογία που εμποδίζει την σύγκλιση της κατανομής της αλυσίδας $\pi_n$, και σε αυτήν την παράγραφο θα προσπαθήσουμε να την κατανοήσουμε.\\
\noindent
{\bf Ορισμός:} Για μια κατάσταση $x\in\X$ ορίζουμε το σύνολο των δυνατών χρόνων επιστροφής στο $x$
\[
R(x)=\{n\in\N: p^{n}(x,x)>0\},\quad \text{όπου θυμίζουμε } p^{(n)}(x,x)=\PP{X_n=x\,|\,X_0=x}.
\]
Θα ονομάζουμε τον μέγιστο κοινό διαιρέτη του συνόλου $R(x)$ {\em περίοδο} της κατάστασης $x$, και θα τον συμβολίζουμε με $d(x)$.
Στην ειδική περίπτωση που $d(x)=1$, θα λέμε ότι η κατάσταση $x$ είναι απεριοδική.\\
\noindent
Παρατηρήστε ότι για κάθε $x\in\X$ το σύνολο $R(x)$ είναι ένα υποσύνολο του $\N$ που είναι κλειστό ως προς την πρόσθεση, δηλαδή
\[
m,n\in\R(x)\Rightarrow m+n\in R(x).
\]
Διαισθητικά αυτό σημαίνει ότι αν είναι δυνατόν να επιστρέψουμε στο $x$ μετά από $m$ βήματα, αλλά και μετά από $n$ βήματα, τότε είναι δυνατόν να επιστρέψουμε στο $x$ και μετά από $m+n$ βήματα. Πράγματι, από τις εξισώσεις \en{Chapman-Kolmogorov} έχουμε
\[
p^{(m+n)}(x,x)=\sum_{y\in\X}p^{(m)}(x,y)p^{(n)}(y,x)\ge p^{(m)}(x,x)p^{(n)}(x,x)>0,
\]
εφόσον $m,n\in\R(x)$. Για τέτοια σύνολα έχουμε το ακόλουθο λήμμα.
\begin{lemma}
Αν ένα σύνολο $R\subset\N$ είναι κλειστό ως προς την πρόσθεση, τότε το $R$ περιέχει τελικά όλους τους φυσικούς (δηλαδή υπάρχει $n_0\in\N$ τέτοιο ώστε $\{n_0,n_0+1,n_0+2,\ldots\}\subset R$) αν και μόνο αν ο μέγιστος κοινός διαιρέτης $d$ του $R$ είναι 1.
\end{lemma}
\end{document}
|
