We need to prove that a simple random walk on $G_k$ is recurrent if and only if it is recurrent on $G$, where $G_k$ is obtained from $G$ by adding edges between non-adjacent vertices that are at most $k$ steps apart in $G$.

Step 1: Definition of Recurrence

A simple random walk on a graph $G$ is recurrent if, with probability 1 , the walk returns to its starting vertex infinitely often. Otherwise, it is transient.

The key fact about recurrence is that it is a property of the large-scale structure of the graph, rather than the specific arrangement of edges, as long as the graph maintains uniform bounded degrees.

Step 2: Relationship Between $G$ and $G_k$

The transformation from $G$ to $G_k$ adds edges between nodes that were previously at most $k$ steps apart in $G$. The resulting graph $G_k$ retains all edges of $G$ and is generally more connected.

• Since $G$ has bounded degrees, $G_k$ also has bounded degrees because each vertex in $G_k$ has at most some function of the maximum degree of $G$.
• The transition probabilities in a simple random walk are altered, but recurrence depends on whether the walker can escape to infinity rather than local transitions.

Step 3: Showing Equivalence of Recurrence in $G$ and $G_k$

(a) If the random walk is recurrent on $G$, it is recurrent on $G_k$

• Since $G_k$ only adds edges, any path available in $G$ remains in $G_k$.
• The additional edges in $G_k$ make traversal faster, but they do not provide an escape mechanism to infinity.
• Because the walk on $G$ is recurrent, the walker returns infinitely often to any starting vertex. Since $G_k$ only enhances connectivity, recurrence is preserved.

(b) If the random walk is recurrent on $G_k$, it is recurrent on $G$

• Consider a random walk on $G_k$. Since $G_k$ contains all edges of $G$, every path in $G$ is also a valid path in $G_k$.
• Suppose, for contradiction, that the random walk is transient on $G$. Then there exists a positive probability that the walker escapes to infinity in $G$.
• However, the additional edges in $G_k$ only allow shortcuts between nearby vertices and do not remove paths. If the walk could escape in $G$, it would also escape in $G_k$, contradicting the recurrence assumption.
• Thus, recurrence in $G_{ k }$ implies recurrence in $G$.

Step 4: Conclusion

Since recurrence in $G$ implies recurrence in $G_k$, and vice versa, we conclude that: