graf nieskierowany, łańcuch Markowa na przestrzeni stanów

[klejdyszklaudia]

Niech będzie dany graf nieskierowany \(\displaystyle{ \Gamma=(V,K)}\), gdzie \(\displaystyle{ V=\{v_1,v_2,\dots,v_n\}}\) oznacza zbiór wierzchołków, a \(\displaystyle{ K=\{k_1,k_2,\dots,k_n\}}\) oznacza zbiór krawędzi grafu. Oznaczmy \(\displaystyle{ deg(v)}\) stopień wierzchołka \(\displaystyle{ v\in V}\), tzn. liczbę krawędzi wychodzących z niego. Załóżmy, że \(\displaystyle{ deg(v) \ge 1}\) dla dowolnego \(\displaystyle{ v\in V}\). Dla każdego \(\displaystyle{ v\in V}\) definiujemy \(\displaystyle{ p_{v,w}= \frac{1}{deg(v)} }\) o ile wierzchołki v i w są połączone krawędzią oraz \(\displaystyle{ p_{v,w}=0}\) w przeciwnym razie. Sprawdzić, że macierz \(\displaystyle{ P=[p_{v,w}]_{v,w\in V}}\) poprawnie definiuje łańcuch Markowa na przestrzeni stanów V (nazywamy zwyczajowo prostym spacerem losowym na grafie \(\displaystyle{ \Gamma}\)). Udowodnij, że rozkład \(\displaystyle{ \mu(v)= \frac{deg(v)}{2m} }\) jest miarą stacjonarną dla tego spaceru losowego. Uzasadnij, ze graf \(\displaystyle{ \Gamma}\) jest spójny wtedy i tylko wtedy gdy prosty spacer na nim jest nieprzywiedlny.