(a) Random walk on a graph. 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:={10ifthereisanedgebetweenverticesiandj,otherwise. The transition matrix P of the random walk on G is defined by pi,j:=Diai,jwhereDi:=jai,j. Prove that P is symmetrizable and that EiTi=D/Di where D:=iDi.[6] Hint: You are indirectly given i (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 number of edges leaving each site, then use above results