我们需要证明，如果且仅如果简单随机游走在$G$上是重现的，那么它在$G_k$上也是重现的，其中$G_k$是通过在$G$中距离最多为$k$步的非相邻顶点之间添加边而从$G$获得的。

步骤 1：重现性的定义

图$G$上的简单随机游走是重现的，如果以概率1，游走者无限次返回其起始顶点。否则，它是暂态的。

关于重现性的关键事实是，它是图的大尺度结构的属性，而不是边的具体排列，只要图保持一致的有界度。

步骤 2：$G$和$G_k$之间的关系

从$G$到$G_k$的变换在先前在$G$中距离最多为$k$步的节点之间添加边。得到的图$G_k$保留了$G$的所有边，并且通常更加连通。

• 由于$G$具有有界度，因此$G_k$也具有有界度，因为$G_k$中的每个顶点最多具有$G$的最大度的某个函数。
• 简单随机游走中的转移概率被改变，但重现性取决于游走者是否可以逃逸到无穷大，而不是局部转移。

步骤 3：证明$G$和$G_k$中重现性的等价性

(a) 如果随机游走在$G$上是重现的，则它在$G_k$上是重现的

• 由于$G_k$只添加边，因此$G$中任何可用的路径都保留在$G_k$中。
• $G_k$中添加的边使遍历更快，但它们不提供逃逸到无穷大的机制。
• 由于在$G$上的游走是重现的，因此游走者无限次返回任何起始顶点。由于$G_k$只增强了连通性，因此重现性得以保留。

(b) 如果随机游走在$G_k$上是重现的，则它在$G$上是重现的

• 考虑$G_k$上的随机游走。由于$G_k$包含$G$的所有边，因此$G$中的每个路径也是$G_k$中的有效路径。
• 假设，为了反证，随机游走在$G$上是暂态的。那么存在一个正概率，游走者在$G$中逃逸到无穷大。
• 但是，$G_k$中添加的边只允许附近顶点之间的捷径，并且不删除路径。如果游走可以在$G$中逃逸，它也会在$G_k$中逃逸，这与重现性假设相矛盾。
• 因此，$G_k$中的重现性意味着$G$中的重现性。

步骤 4：结论

由于$G$中的重现性意味着$G_k$中的重现性，反之亦然，我们得出结论：