Rachunek prawdopodobieństwa 1, 2
\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\ep }{\varepsilon }\)
\(\newcommand {\ve }{\varepsilon }\)
\(\newcommand {\s }{\sigma }\)
\(\newcommand {\o }{\omega }\)
\(\newcommand {\f }{\varphi }\)
\(\newcommand {\vr }{\varrho }\)
\(\newcommand {\a }{\mathcal {A}}\)
\(\newcommand {\h }{\mathcal {H}}\)
\(\newcommand {\b }{\mathcal {B}}\)
\(\newcommand {\G } {\mathbb {G}}\)
\(\newcommand {\r } {\mathbb {R}}\)
\(\newcommand {\rn } {\mathbb {R}^n}\)
\(\newcommand {\Z } {\mathbb {Z}}\)
\(\newcommand {\z } {\mathbb {Z}}\)
\(\newcommand {\N } {\mathbb {N}}\)
\(\newcommand {\C } {\mathbb {C}}\)
\(\newcommand {\K } {\mathbb {K}}\)
\(\newcommand {\Q } {\mathbb {Q}}\)
\(\newcommand {\bx }{\mathbf {x}}\)
\(\newcommand {\by }{\mathbf {y}}\)
\(\newcommand {\bY }{\mathbf {Y}}\)
\(\newcommand {\p }{\mathbf {p}}\)
\(\newcommand {\P }{\mathbf {P}}\)
\(\let \leq \leqslant \)
\(\let \le \leqslant \)
\(\newcommand {\O }{\emptyset }\)
\(\newcommand {\imp }{\Longrightarrow }\)
\(\newcommand {\str }{\longrightarrow }\)
\(\newcommand {\rwn }{\Longleftrightarrow }\)
\(\newcommand {\di }{\displaystyle }\)
17.4 Spacery losowe po grafie (nieskierowanym)
Niech \(G = (V,E)\) będzie grafem. Dla wierzchołka \(v\) określamy jego stopień \(\deg (v)\) jako liczbę krawędzi wychodzących z \(v\), czyli liczbę sąsiadów \(v\).
Spacer losowy \(\{X_t\}\) po grafie \(G\).
Cząstka, która w chwili \(t\) znajduje się w wierzchołku \(v\), czyli \(X_t = v\), może przejść w jednym kroku do jednego z sąsiednich wierzchołków, \(X_{t+1}\), z prawdopodobieństwem \(\frac {1}{\deg (v)}\). Gdy wierzchołek nie
ma sąsiadów, cząstka z prawdopodobieństwem \(1\) pozostaje w tym wierzchołku.
Następujące dwa twierdzenia są oczywiste.
-
Twierdzenie – 17.16 \(\{X_t\}\) jest łańcuchem Markowa na przestrzeni stanów \(V\) z macierzą przejścia \(\P \) określoną następująco: \(\P (u,v) = \frac {1}{\deg (u)}\), gdy \(uv \in E\), \(\P
(v,v) = 1\), gdy \(v\) nie ma sąsiadów, \(\P (u,v) = 0\) w pozostałych przypadkach.
Gdy każde dwa wierzchołki można połączyć ciągiem krawędzi (mówimy wtedy, że graf jest spójny), to \(\{X_t\}\) jest nieredukowalny.
-
Twierdzenie – 17.18 Niech \(\{X_t\}\) oznacza taki spacer losowy po grafie \(G = (V,E)\), \(\sharp V = d\), że dla każdego \(v \in V\) \(\deg (v) > 0\) (nie ma wierzchołków
izolowanych). \(n = \sharp V\).
Określamy \(\pi _v = \frac {\deg (v)}{C}\) dla \(v \in V\), przy czym \(C = \sum _{u\in V}\deg (u)\).
Wtedy wektor \(\pi \in \r ^d\) o współrzędnych \(\pi _v\) jest rozkładem stacjonarnym łańcucha Markowa \(X_t\), to znaczy:
\[\P ^T\pi = \pi , \ \ \ \sum _{v\in V}\pi _v = 1, \ \ \ \pi _v > 0 \mbox { dla } v \in V.\]
Dowód. Wystarczy pokazać, że \(\sum _{u \in V}\P (u,v)\pi _u = \pi _v\) dla każdego \(v \in V\). Pamiętając, że \(\deg (v)\) oznacza \(\sharp N(v)\), przy czym \(N(v)\) jest zbiorem sąsiadów
wierzchołka \(v\), i korzystając z określenia łańcucha, widzimy, że:
\[\sum _{u \in V}\P (u,v)\pi _u = \sum _{u \in N(v)}\P (u,v)\pi _u = \sum _{u \in N(v)}\frac {1}{\deg (u)}\frac {\deg (u)}{C} = \frac {\deg (v)}{C} = \pi _v.\]
