"Fossies" - the Fresh Open Source Software Archive

Member "hevea-2.35/bugs/008/Chapter_7.tex" (16 Jan 2021, 6614 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 \section{Περιοδικότητα}\label{periodicity}
   62 Ας θεωρήσουμε μια αλυσίδα που κινείται στις κορυφές ενός τετραγώνου ΑΒΓΔ. Ξεκινώντας από την κορυφή Α, σε κάθε βήμα μεταβαίνει σε μια από τις δύο γειτονικές της κορυφές με πιθναότητα 1/2. Εύκολα βλέπει κανείς ότι η μοναδική αναλλοίωτη κατανομή αυτής της αλυσίδας είναι η ομοιόμορφη κατανομή $\pi=(1/4,1/4,1/4,1/4)$, και όπως είδαμε στο προηγούμενο κεφάλαιο αυτό είναι μόνο υποψήφιο όριο της κατανομής $\pi_n$ της αλυσίδας μετά από $n$ βήματα. Δεν είναι δύσκολο να δει κανείς όμως ότι $\pi_n\not\rightarrow\pi$. Πράγματι, εφόσον η αλυσίδα ξεκινά από το Α, θα βρίσκεται οπωσδήποτε στο B ή στο Δ μετά από περιττό αριθμό βημάτων, και στο Α ή στο Γ μετά από άρτιο αριθμό βημάτων. Έτσι,  π.χ. 
   63 \[
   64 \pi_{2n}(B)=\PP{X_{2n}=B\,|\,X_0=A}=0\not\rightarrow 1/4.
   65 \] 
   66 Βλέπουμε λοιπόν ότι στο παράδειγμά μας υπάρχουν υποσύνολα του χώρου καταστάσεων που είναι προσβάσιμα μόνο σε συγκεκριμένες χρονικές στιγμές. Αυτή η ιδιότητα αποτελεί κατά κάποιον τρόπο μια παθολογία που εμποδίζει την σύγκλιση της κατανομής της αλυσίδας $\pi_n$, και  σε αυτήν την παράγραφο θα προσπαθήσουμε να την κατανοήσουμε.\\
   67 
   68 \noindent
   69 {\bf Ορισμός:} Για μια κατάσταση $x\in\X$ ορίζουμε το σύνολο των δυνατών χρόνων επιστροφής στο $x$
   70 \[
   71 R(x)=\{n\in\N: p^{n}(x,x)>0\},\quad \text{όπου θυμίζουμε } p^{(n)}(x,x)=\PP{X_n=x\,|\,X_0=x}.
   72 \]
   73 Θα ονομάζουμε τον μέγιστο κοινό διαιρέτη του συνόλου $R(x)$ {\em περίοδο} της κατάστασης $x$, και θα τον συμβολίζουμε με $d(x)$.
   74 Στην ειδική περίπτωση που $d(x)=1$, θα λέμε ότι η κατάσταση $x$ είναι απεριοδική.\\
   75 
   76 \noindent
   77 Παρατηρήστε ότι για κάθε $x\in\X$ το σύνολο $R(x)$ είναι ένα υποσύνολο του $\N$ που είναι κλειστό ως προς την πρόσθεση, δηλαδή
   78 \[
   79 m,n\in\R(x)\Rightarrow m+n\in R(x).
   80 \]
   81 Διαισθητικά αυτό σημαίνει ότι αν είναι δυνατόν να επιστρέψουμε στο $x$ μετά από $m$ βήματα, αλλά και μετά από $n$ βήματα, τότε είναι δυνατόν να επιστρέψουμε στο $x$ και μετά από $m+n$ βήματα. Πράγματι, από τις εξισώσεις \en{Chapman-Kolmogorov} έχουμε
   82 \[
   83 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,
   84 \]
   85 εφόσον $m,n\in\R(x)$. Για τέτοια σύνολα έχουμε το ακόλουθο λήμμα.
   86 \begin{lemma}
   87 Αν ένα σύνολο $R\subset\N$ είναι κλειστό ως προς την πρόσθεση, τότε το $R$ περιέχει τελικά όλους τους φυσικούς (δηλαδή υπάρχει $n_0\in\N$ τέτοιο ώστε $\{n_0,n_0+1,n_0+2,\ldots\}\subset R$) αν και μόνο αν ο μέγιστος κοινός διαιρέτης $d$ του $R$ είναι 1.
   88 \end{lemma}
   89 \end{document}
   90 
   91