Łańcuch Markowa można opisać za pomocą grafu skierowanego (digrafu) z wagami.
Niektóre spacery losowe po grafie (nieskierowanym) będące łańcuchami Markowa mają ciekawą interpretację, a także znaczenie praktyczne.
Definicja – 17.13 Dany jest zbiór skończony \(V = \{v_1,...,v_d\}\).
1. Grafem nazywamy parę \((V,E)\), przy czym \(E\) jest pewnym zbiorem dwuelementowych podzbiorów utworzonych z elementów zbioru \(V\).
2. Grafem skierowanym nazywamy parę \((V,E)\), przy czym \(E\) jest pewnym zbiorem par utworzonych z elementów zbioru \(V\) (\(E \subset V \times V\)).
3. Grafem z wagami nazywamy parę \((V,W)\), przy czym \(W: V \times V \to \r \)
(\(W\) jest pewną macierzą indeksowaną prze elementy \(V\)).
Elementy zbioru \(V\) nazywamy wierzchołkami, elementy zbioru \(E\) nazywamy krawędziami. Każdy graf z wagami \((V,W)\) indukuje graf skierowany \((V,E)\), przy czym \(E = \{(v_i,v_j): A(v_i,v_j) \neq 0 \}\). Wtedy elementy \(W(v_i,v_j)\) nazywamy wagami krawędzi \((v_i,v_j)\). Najczęściej przy zapisie krawędzi opuszczamy nawiasy. Czyli \(uv = (u,v)\) w przypadku grafu skierowanego, \(uv = \{u,v\}\) w przypadku grafu.
Bardzo często grafy interpretuje się w sposób geometryczny, co ma mocne uzasadnienie intuicyjne i w wielu sytuacjach ułatwia ich analizę. Niemniej jest to pojęcie mające niekiedy daleko szerszą interpretacje.
Uwaga – 17.14 Jeżeli \(\{X_n\}\) jest łańcuchem Markowa na przestrzeni stanów \(M\) i ma macierz przejścia \(\P \), to \((M,\P )\) jest grafem z wagami.
Przykład – 17.15 W przykładzie o Syzyfie graf z wagami może wyglądać tak:
\(d\)-wymiarowa kostka dyskretna jako graf.
Niech \(d\) będzie ustaloną liczbą naturalną. Określamy
\[V = \{0,1\}^d = \{(\ve _1, \dots , \ve _d): \ve _i \in \{0,1\}, i = 1, \dots , d\}. \]
Niech \(E\) będzie zbiorem wszystkich takich dwuelementowych zbiorów \(\{u,v\}\) \(u, v \in V\), że \(u\), \(v\) różnią się od siebie dokładnie na jednym miejscu.
Dla \(d = 2\) mamy więc cztery wierzchołki i cztery krawędzie, które możemy interpretować jako boki kwadratu. Dla \(d = 3\) mamy 8 wierzchołków i 12 krawędzi, które możemy interpretować jako krawędzie sześcianu.
Dla \(d \ge 3\) liczba krawędzi gwałtownie wzrasta.
