Question

let G = (V, E) be a finite graph where V denotes the set of vertices and E the set of edges and further assume that there are no isolated vertices. Consider the simple random walk Sn on G which from any vertex jumps to one of the adjacent vertices uniformly. Prove that all vertices of G are recurrent.

Answer 1

To prove that all vertices of a graph G are recurrent, we can use the Fundamental Theorem of Random Walks, which states that for an irreducible, finite, and connected graph, all vertices are recurrent.

Step-by-step explanation:

In order to prove that all vertices of a graph G are recurrent, we need to show that for any vertex v in G, the expected return time to v is finite. In other words, the expected number of steps for the random walk to return to v is finite.

One approach to proving this is by using the Fundamental Theorem of Random Walks. This theorem states that for an irreducible graph (meaning that there is a path between any pair of vertices), if the graph is finite and connected, then all vertices are recurrent.

Since G is a finite graph with no isolated vertices (meaning that every vertex has at least one edge connecting it to another vertex), we can conclude that all vertices of G are recurrent.