Let G be a graph which is connected (so you can go from any vertex to...

Transcribed Image Text:

Let G be a graph which is connected (so you can go from any vertex to any other along the edges). Assume that G has no double edges (there is at most one edge between any two vertices) and no edge connects a vertex back to itself (each edge must connect two distinct vertices). The adjacency matrix, A, of graph G is defined by ai.j 1 {} if there is an edge between vertices i and j, 0 otherwise. The transition matrix P of the random walk on G is defined by ai,j D₁ Pi,j:= -Σaij. where D₁ := Prove that P is symmetrizable and that E;T; = D/D; where D:=E, D₁. [6] Hint: You are indirectly given T₁ (how?), so it is sufficient to 'guess' a solution and verify that it satisfies the detailed balance equations... (b) The crazy knight! Prove that a knight on a chess-board making legal chess moves at random and starting at a corner square will take on average 168 moves to return there. Hint: think of the graph associated with this random walk and count the num- ber of edges leaving each site, then use above results... Let G be a graph which is connected (so you can go from any vertex to any other along the edges). Assume that G has no double edges (there is at most one edge between any two vertices) and no edge connects a vertex back to itself (each edge must connect two distinct vertices). The adjacency matrix, A, of graph G is defined by ai.j 1 {} if there is an edge between vertices i and j, 0 otherwise. The transition matrix P of the random walk on G is defined by ai,j D₁ Pi,j:= -Σaij. where D₁ := Prove that P is symmetrizable and that E;T; = D/D; where D:=E, D₁. [6] Hint: You are indirectly given T₁ (how?), so it is sufficient to 'guess' a solution and verify that it satisfies the detailed balance equations... (b) The crazy knight! Prove that a knight on a chess-board making legal chess moves at random and starting at a corner square will take on average 168 moves to return there. Hint: think of the graph associated with this random walk and count the num- ber of edges leaving each site, then use above results...

Answer rating: 100% (QA)

To prove that the transition matrix P of the random walk on graph G is symmetrizable we need to show that there exists a diagonal matrix D such that D... View the full answer