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...