\documentclass[twoside,12pt]{article}
\usepackage{graphics,latexsym,a4wide}
\usepackage{graphicx}
%\usepackage[bf,centerlast]{subfigure}

\usepackage[latin2]{inputenc}
\usepackage{t1enc}
\usepackage[magyar]{babel}

\newenvironment{proof}{\noindent{\bf Bizony\'{\i}t\'as:}}{\qed\bigskip}
\newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}

\newtheorem{thm}{T\'etel}
\newtheorem{corollary}{K\"ovetkezm\'eny}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{\'All\'{\i}t\'as}
\newtheorem{definition}{Defin\'{\i}ci\'o}
\newtheorem{example}{P\'elda}
\newtheorem{algorithm}{Algoritmus}
\newtheorem{note}{Megjegyz\'es}
\newcommand{\qed}{$\Box$}
\newcommand{\Pbold}{\mathbf{P}}
\newcommand{\eloadas}[2]{
%\pagestyle{myheadings}[H\'al\'ozatok \'es a World Wide Web matematik\'aja][#1 \hfill #2]
\thispagestyle{empty}

\noindent
\begin{center}\framebox{
\vbox{ \hbox to 5.875in { {H\'al\'ozatok \'es a World Wide Web
matematik\'aja \hfill
        2003/2004 I. f\'el\'ev} }
\vspace{4mm} \hbox to 5.875in {\hfill {\Large #1}
        \hfill  #2}
\vspace{2mm} \hbox to 5.875in { {\it El\H{o}ad\'o: Bencz\'ur
Andr\'as\quad \texttt{benczur@sztaki.hu} \hfill  } } \hbox to
5.875in { {\it Jegyzet\'{\i}r\'o: P\'oczos Barnab\'as \quad
\texttt{pbarn@cs.elte.hu}} \hfill } }}\end{center}

\vspace*{4mm} }

\begin{document}
\eloadas{M\'asodik el\H{o}ad\'as}{2003. okt\'ober ???.}

\section{Markov l\'ancok}
\begin{definition}
Az $\{ X_t \}=\{X_1,X_2,\ldots \}$ valószínűségi változók sorozatát (sztochasztikus folyamatot) diszkrét idejű
\textbf{Markov láncnak} nevezzük, ha $P(X_{t+1}|X_{t},\ldots
,X_1)=P(X_{t+1}|X_{t})$ $\forall t$ estén, azaz ha a következő állapot teljes múltra vonatkozó feltételes eloszlása csak a jelenlegi állapottól függ. (A múlt ismerete nem ad további információt a jövő megismeréséhez). Az állapotok $\mathcal{X}$ halmazát a \textbf{Markov lánc állapotterének} nevezzük. A továbbiakban feltesszük, hogy $|\mathcal{X}|<\infty$, azaz az állapottér véges. Az általánosság megszorítása nélkül feltehetjük, hogy $\mathcal{X}=\{1,\ldots,n\}$. A Markov folyamatot
\textbf{homogénnek} nevezzük, ha $P(X_{t+1}|X_{t})$ átmenet valószínűség $t$-től független.
\end{definition}

Az ilyen diszkrét idejű, véges állapotterű, homogén $\{ X_t \}$
Markov folyamatokhoz hozzárendelhető egy $G$ irányított gráfon történő bolyongás. A gráf csúcsai legyenek az$\{ X_t \}$ Markov folyamat állapotai, és $\forall$ $(i,j)$ élre írjuk rá a
$P(X_{t+1}=j|X_t=i)$ átmenet valószínűségét, majd a kapott teljes gráfból töröljük azokat az éleket, melyekhez 0 valószínűséget rendeltünk. Látható, hogy ezzel valóban az $\{ X_t \}$ Markov folyamathoz hozzárendeltünk egy $G$ irányított gráfon történő bolyongást. A $G$ gráf csúcsait a továbbiakban
$V(G)=\{1,\ldots,n\}$, az éleit $E(G)=\{(i,j)\}$ jelöli.

\begin{definition}
A $\Pbold=[P]_{ij}=P(X_{t+1}=j|X_{t}=i)$ mátrixot egylépéses átmenet mátrixnak nevezzük.
\end{definition}
Nyilvánvalóan a diszkrét idejű, véges állapotterű, homogén Markov láncnak létezik egylépéses $\Pbold$ átmenet mátrixa.

\begin{note} Könnyen látható, hogy
\begin{enumerate}
  \item $\Pbold=[P_{ij}]$ átmenet mátrix egy súlyozott
adjacencia mátrix.
  \item $P_{ij}>0$ $\forall (i,j) \in E(G)$ élre, hisz a 0
  valószínűségű éleket töröltük.
  \item $\sum_j P_{ij}=1$ $\forall i$, azaz $\Pbold$
egy sztochasztikus mátrix.
\end{enumerate}
\end{note}


\begin{example}
Egy egyszerű példa az Uniform bolyongás. Ennek egy egyszerű esete
látható az \ref{f:uniform}. ábrán.
 $$P_{ij}=\left\{ \begin{array}{cc}
  \frac{1}{kifok(i)} & \textit{ha}\, (i,j)\in E(G)\\
  0 & \textit{k\"ul\"onben} \end{array}
  \right.$$
\end{example}

%ÁBRA

\begin{figure}[h!] \label{f:uniform}
\centering\includegraphics[width=3cm]{Uniform.eps}
\caption{\textbf{Uniform átmenet az A csúcsból} } A nyilakon az
átmenet feltételes valószínűsége látható. Az A csúcsot
\textsl{forrásnak} nevezzük.
\end{figure}

Homogén Markov láncok esetén a fenti egylépéses $\Pbold$ átmenet
mátrix mintájára definiálhatjuk az úgynevezett t lépéses átmenet
mátrixot.

\begin{definition}
$[Q]_{ij}=P(X_{k+t}=j|X_{k}=i)$ mátrixot \textbf{t lépéses átmenet mátrix}nak nevezzük.
\end{definition}

Az alábbi lemma szerint ez a definíció értelmes, és $\mathbf{Q}$ t lépéses átmenet mátrix a $\Pbold$ egylépéses átmenetmátrixból hatványozással megkapható.

\begin{lemma}
$P(X_{k+t}=j|X_{k}=i)=[P^t]_{ij}$, $\forall (k,i,j)$ esetén, azaz annak a valószínűsége, hogy a k. időpontban egy i állapotból indulva t lépés múlva a j állapotba érek, épp a mátrix t-edik hatványának ij eleme.
\end{lemma}
\begin{proof}
Ez az egylépéses átmenet mátrix, és a mátrix szorzás definíciójának triviális következménye. (Feltettük, hogy a Markov lánc homogén).
\end{proof}

Az alábbi példák néhány elfajuló esetet mutatnak be.

\begin{example}
Egy $i$ csúcsot \textbf{forrás}nak (\ref{f:uniform}. ábra,
\textbf{A} csúcs) nevezünk, ha 0 a befoka. Ide soha sem juthatunk,
hacsaknem innen indultunk $t=1$-ben.
\end{example}

\begin{example} Egy $i$ csúcsot \textbf{Nyelő}nek (2. ábra), illetve \textbf{Csapdá}nak nevezünk, ha 0 a kifoka. Ebből az $i$ csúcsból nem tudunk kijutni.
$P_{ii}=1$. Ez a $G$ gráfban hurokélnek felel meg.
\end{example}

\begin{figure}[h!] \label{f:nyelo}
\centering\includegraphics[width=4cm]{Nyelo.eps}
\caption{\textbf{Nyelő} } A gráf D csúcsát nyelőnek nevezzük.
\end{figure}

Az alábbiakban azt próbáljuk megvizsgálni, hogy a Markov folyamat mikor ér egy adott i állapotból egy adott j állapotba? Mikor ér oda először? Mennyi a valószínűsége, hogy odaér? Véges időn belül oda ér-e? E kérdések megválaszolásához szükségünk lesz az alábbi definíciókra.

\begin{definition}
$r_{ij}^t=P(\textit{t lépés múlva érünk először j-be}|\textit{
i-ből indulunk})$
\end{definition}

\begin{definition}
$f_{ij}=P(\textit{i-ből valaha j-be érünk}|\textit{ i-ből indulunk})$
\end{definition}

\begin{lemma}

\begin{eqnarray}
f_{ij}&=&\sum_{t=0}^{\infty}r_{ij}^t \hspace{1cm} i\neq j \nonumber\\
f_{ii}&=&\sum_{t=1}^{\infty}r_{ii}^t \hspace{1cm} \textit{Ez az i állapotba visszatérés valószínűsége} \nonumber
\end{eqnarray}

\end{lemma}
\begin{proof}
Triviális a definíciókból.
\end{proof}

\begin{definition}
$h_{ij}=E(\textit{i állapotból j állapotba érkezéshez szükséges lépésszám}| \textit{i-ből indulunk})=\sum_{t=0}^{\infty}tr_{ij}^t$
\end{definition}

\begin{definition}
i állapot \textbf{tranziens}, ha $f_{ii}<1$, azaz véges valószínűséggel előfordulhat, hogy sohasem érünk vissza i-be.
\end{definition}

\begin{definition}
i állapot \textbf{perzisztens}, ha $f_{ii}=1$, azaz 1 valószínűséggel a Markov folyamat visszatér i-be.
\end{definition}

Ha tudjuk, hogy az i állapot perzisztens, érdekelhet minket, hogy várhatóan mikor érünk vissza.
\begin{definition}
i állapot \textbf{nullperzisztens}, ha perzisztens, de
$h_{ii}=\infty$, azaz a visszatérés várható ideje végtelen.
\end{definition}

\begin{definition}
i állapot \textbf{nem nullperzisztens}, ha perzisztens, és
$h_{ii}<\infty$, azaz várhatóan véges időn belül visszatérünk az i
állapotba.
\end{definition}

\begin{lemma} \label{l:eöfkomp}
Erősen összefüggő komponens minden i állapota perzisztens, azaz
$f_{ii}=1$.
\end{lemma}
\begin{proof}
Legyen az erősen összefüggő komponens mérete k. Tudjuk, hogy minden csúcsból vezet egy legfeljebb k hosszú út i-be. Ezért minden j csúcsra pozitív annak a valószínűsége, hogy j-ből indulva legfeljebb
k hosszú úton eljutunk i-be. Ezért P(max k hosszú úton nem i-be érek| j-ből indulok)<1. Legyen $$ \delta= \max_{j} P(\textit{max k hosszú úton nem i-be érek}| \textit{j-ből indulok})$$ Nyílván
$\delta<1$, hisz $\delta$ véges sok 1-nél kisebb érték maximuma.
Ekkor
$$ P(\textit{max kt hosszú úton nem i-be érek}| \textit{j-ből indulok})\leq\delta^t\rightarrow0$$ Tehát $f_{ii}=1$
\end{proof}

\begin{thm}
Az i állapot perzisztens, akkor és csak akkor az i állapot erősen összefüggő komponenséből nem vezet ki él.
\end{thm}
\begin{proof}
Legyen i perzisztens. Indirekt tegyük fel, hogy az i állapot erősen összefüggő komponenséből vezet ki él. Ekkor véges valószínűséggel kijutok ezen erősen összefüggő komponensből, de visszafelé már nem vezet út. Emiatt pozitív a valószínűsége, hogy
i csúcsból indulva nem jutok vissza i-be. Tehát $f_{ii}<1$, azaz i nem perzisztens. Így ellentmondásra jutottunk.

Tegyük fel, hogy az i állapot erősen összefüggő komponenséből nem vezet ki él. Ekkor az erősen összefüggő komponensben fogunk bolyongani, de ott \ref{l:eöfkomp}. lemma miatt visszatérünk i-be, ezért i perzisztens.
\end{proof}


\begin{thm}
i állapot perzisztens, akkor nem nullperzisztens.
\end{thm}
\begin{proof}
Legyen az i állapot a k méretű erősen összefüggő komponensben.
Ekkor minden $t$-hez létezik $t'$, hogy $(t'-1)k<t\leq t'k$. Legyen
$$\delta= \max_{j} P(\textit{max k hosszú úton nem érek i-be}|
\textit{j-ből indulok})$$ Nyílván $\delta<1$, hiszen minden j csúcsból létezik max k hosszú út i-be. Ezért
\begin{eqnarray}
 h_{ii}&=&\sum_{t=1}^\infty t r_{ii}^t\leq \sum_{t'=1}^\infty
kt' P(kt' \textit{lépésben i-be érünk, de }k(t'-1) \textit{ lépésen belül még nem érünk i-be} ) \nonumber \\
&\leq& \sum_{t'=1}^\infty kt' P( k(t'-1)\textit{ lépésen belül még nem érünk i-be}) \leq k \sum_{t'=1}^\infty t' \delta^{t'-1} <
\infty \nonumber
\end{eqnarray}
\end{proof}

\begin{corollary}
\end{corollary}

\begin{itemize}
    \item Ha erősen összefüggő komponensben vagyunk, akkor 1 valószínűséggel visszatérünk, sőt ezt várhatóan véges időn belül megtesszük.
    \item Ha nem erősen összefüggő komponensben vagyunk, akkor
    pozitív valószínűséggel nem térünk vissza.
\end{itemize}

\begin{definition}
A $G$ gráfot \textbf{irreducibilis}nek nevezzük, ha minden csúcsából vezet irányított út minden csúcsba, azaz ha a gráf egyetlen erősen összefüggő komponensből áll.
\end{definition}

\begin{lemma}
Ha a gráf erősen összefüggő komponensek diszjunkt uniója, akkor a gráf minden csúcsa perzisztens. Speciálisan, ha a gráf
irreducibilis, akkor minden csúcsa perzisztens.
\end{lemma}

A célunk most az lesz, hogy a bolyongás aszimptotikus tulajdonságait megvizsgáljuk. Hosszú távon vajon a bolyongás
'elfelejti-e', hogy honnan indult, és kialakul-e az állapotoknak egy hosszú távú aszimptotikus határeloszlása, vagy másként mondva
stacionarizálódik-e az eloszlás.

\begin{definition}
A $\mathbf{v}=(v_1,\ldots v_n)$ eloszlást \textbf{stacionárius} eloszlásnak nevezzük, ha $v_i\geq 0$, $\forall i$ esetén.
$\sum_{i=1}^T v_i=1$, és $\mathbf{v}\Pbold=\mathbf{v}$.
\end{definition}
Ennek szemléletes jelentése az, hogy ha a t. időben $(v_1,\ldots
v_n)$ arányban vagyunk az $(1\ldots n)$ állapotokon, akkor a
$t+1$. időben is ugyanilyen arányban fordulunk elő az ($1\ldots
n$) állapotokban. Ez tehát egy szükséges feltétel, ahhoz hogy a
Markov lánc határeloszlásáról beszélhessünk.

\begin{example}
Fontos feltétel még, hogy a Markov lánc elfelejtse, hogy honnan indultunk a kezdeti időpontban. Legyen ugyanis $$\Pbold=
\begin{tabular}{|c c|}
  0 & 1 \\
  1 & 0 \\
\end{tabular}$$
Erre $(\frac{1}{2},\frac{1}{2})\Pbold=(\frac{1}{2},\frac{1}{2})$
Viszont ha (1,0), illetve (0,1) eloszlásból indítjuk a Markov láncot, akkor határeloszlás már nem létezik, a bolyongás ciklikusan körbe-körbe fog menni az állapotokon.
\end{example}
A periodikus Markov láncok tehát nem felejtik el, hogy honnan indultunk. Az állapotok eloszlása függ attól, hogy melyik t időpontban vagyunk (modulo periódushossz).

\begin{definition}
A $G$ gráf \textbf{aperiodikus}, ha a $G$-beli irányított körök hosszának legnagyobb közös osztója 1.
\end{definition}

\begin{definition}
A $G$ gráf \textbf{periodikus}, ha nem aperiodikus.
\end{definition}


\begin{example}Az irreducibilitás is nyílván egy szükséges feltétel az indítástól független határeloszlás létezéséhez. Legyen ugyanis $G$ egy irányítatlan értelemben nem összefüggő gráf, de minden komponense erősen összefüggő. Ekkor nyílván egyik
komponensből soha nem tudunk átjutni a másik komponensbe, így a határeloszlás attól függ, hogy mely komponensből indultunk.
\end{example}

\begin{example}
Szimulációk alapján, pusztán a Markov folyamat realizációját
vizsgálva, még ha létezik is stacionárius eloszlás, nehéz
eldönteni, hogy a Markov folyamat már beállt-e, illetve közel
van-e (valamilyen értelemben) a stacionárius eloszláshoz.
Előfordulhat ugyanis, hogy csak exponenciálisan sok idő alatt
jutunk be egy gráf erősen összefüggő komponensébe, viszont csak
ezekben alakulhat ki stacionárius eloszlás. (3. ábra)
\end{example}

\begin{figure}[h!] \label{f:Explassu}
\centering\includegraphics[width=6cm]{Explassu.eps}
\caption{\textbf{Az A csúcsból a B csúcsba várhatóan csak
exponenciálisan hosszú idő alatt jutunk el.} }
\end{figure}


A fenti bevezető után már kimondhatjuk a Markov láncok fő tételét:
\begin{thm}
Legyen G irreducibilis aperiodikus gráf. Ekkor
\begin{enumerate}
  \item Minden csúcs nem nullperzisztens.
  \item Létezik egyértelmű $\pi=(\pi_1,\ldots \pi_n)$ stacionárius
  eloszlás.
  \item $\lim \limits_{t \rightarrow \infty} \frac{E(\textit{ennyiszer jutunk
  t lépés alatt i-be})}{t}=\pi_i$
  \item $\lim \limits_{t \rightarrow \infty} \mathbf{v}\Pbold^t = \pi$, $\forall
  \mathbf{v}$ esetén, azaz a Markov lánc elfelejti, hogy honnan indultunk.
\end{enumerate}
\end{thm}
\begin{proof}
Nem bizonyítjuk, csupán speciális estben d reguláris gráfokon megnézünk egy-két részletet.
\end{proof}

\begin{note}
$\mathbf{vP=v}$ jelentése, hogy $\mathbf{v}$ a $\Pbold$ mátrix sajátvektora 1 sajátértékkel.
\end{note}

\begin{thm}
A d reguláris irányítatlan összefüggő gráfokon az 1 egyszeres sajátértek.
\end{thm}
\begin{proof}
Tegyük fel, hogy $\mathbf{v}$ sajátvektor. Ekkor
$(\mathbf{vP})_j=\sum v_iP_{ij}$. Legyen $v_{max}=\max\{v_i\}$.
Ekkor $$\sum_{i=1}^n v_i P_{ij} \leq v_{max} \sum_{i=1}^n
P_{ij}=v_{max} $$ Ezért nem létezik olyan vektor, amelynek
$\Pbold$ minden koordinátáját 1-nél jobban megnyújtaná, tehát
$\Pbold$-nek nincs 1-nél nagyobb sajátértéke. Ha az 1 sajátérték, akkor a fenti egyenlőtlenségben egyenlőségnek kell teljesülnie minden j-re.
$$\sum_{i=1}^n v_i P_{ij}=v_{max} ,\hspace{1cm} \forall j \textit{ esetén}$$
Tehát a $v_1, \ldots, v_n$ értékek nem elfajuló lineáris kombinációja $v_{max}$ (mivel $ P_{ij}>0)$, ezért
$$(v_1,\ldots,v_n)=(1/n,\ldots, 1/n)$$
\end{proof}
\begin{thm}
$\lambda=-1$, is lehetséges. Ekkor G páros gráf. A valószínűségi interpretációnak viszont már nincs értelme. A többi esetben
$|\lambda|<1$.
\end{thm}

\begin{proof}
Az előbbihez hasonló módon haladunk.
$$
|(vP)_j|=|\sum_{i=1}^n v_i P_{ij}|\leq \sum_{i=1}^n
P_{ij}|v_{max}|=|v_{max}|
$$ Ezért $|\lambda|=1$ a lehetséges legnagyobb abszolút értékű sajátérték. Ha $\lambda=-1$, akkor
$$
-v_j=\sum_{i=1}^n v_i P_{ij}
$$
Ezért ha $P_{ij}>0$, ez csak úgy lehetséges, ha $v_i=-v_j$. Legyen
\begin{eqnarray}
V_1&=&\{i \in G: v_i>0\} \nonumber \\
V_2&=&\{i \in G: v_i<0\} \nonumber
\end{eqnarray}
Ekkor G páros gráf a $V_1$, és $V_2$ halmazon.
\end{proof}

\begin{thm}
Legyen $G$ összefüggő, d reguláris, irányítatlan gráf. Legyen
$\mathbf{v}_{0}>0$ tetszőleges vektor. Ekkor
$\mathbf{v}_{0}\Pbold^t$ konvergencia sebessége $\lambda_2$-ben exponenciális.
\end{thm}
\begin{proof}
Tudjuk, hogy az 1 egyszeres legnagyobb sajátérték $P$-ben. Legyen
$\mathbf{w}_1, \ldots \mathbf{w}_n$ sajátvektor bázis $\lambda_1,
\ldots \lambda_n$ sajátértékekkel, úgy hogy $1=\lambda_1> \ldots
>\lambda_n$. Írjuk fel $\mathbf{v}_0-t$ ebben a bázisban.
$$
\mathbf{v}_{0}=\sum_{i=1}^n \alpha_i \mathbf{w}_i
$$
Tegyük fel, hogy $\alpha_1 \neq 0$. Ekkor
$$
\mathbf{v}_0\Pbold^t=\sum_{i=1}^n \alpha_i
\mathbf{w}_i\Pbold^t=\sum_{i=1}^n \alpha_i \lambda_i^t
\mathbf{w}_i=\alpha_1 \mathbf{w}_1 + \sum_{i=2}^n \alpha_i
\lambda_i^t \mathbf{w}_i
$$
Az első tag konstans, a második tag pedig exponenciális sebességgel tart 0-hoz. Könnyen meggondolható, hogy $\alpha_1 = 0
$ nem lehet. Ekkor ugyanis az $(1/n, \ldots , 1/n)$ saját vektorra
$\mathbf{v}_0$ merőleges lenne, ami csak úgy  lehet, ha
$\mathbf{v}_0$-nak lennének negatív elemei is, de ez nem lehet.
\end{proof}
\end{document}