随机图ξ（n,M）上随机游动的平均返回时间

摘要

设 G 是一个连通图,G 上的随机游动是如下的马氏链:其状态空间是 G 的顶点集,从一个顶点总是以等概率转移到相邻的顶点。用 E_(n,M)(k)表示在全体具有 n 个顶点 M 条边的连通图上,随机游动回到具有次数为 h 的项点所用的平均时间。我们得到了以下结果:对任意固定实数 c,令 M_o=[1/2nl_n+cn],那么当→∞时,