随机移动的相关结论

首先介绍两个关键的概念：首次相遇时间（First Hitting Time）和首次返回时间（First Return Time）[126]。令X（t）表示一个状态集为的稳态分布的马尔科夫链。

定义4.1　首次相遇时间

定义状态集合的首次相遇时间为

定义状态集合的首次返回时间为

其中，X（0）服从X分布。

考虑一个d维的环（Torus），记作，其可描述为一个d维整数向量（i=（i1，i2，…，id）modulo k）的集合，通常来讲，可以看做一个由kd个顶点组成的2d-regular图。针对中的单个状态考虑首次相遇时间和首次返回时间。

引理4.3　首次相遇和返回时间

记d维的环中单个状态的首次相遇时间和首次返回时间为τH和τR，则以高概率有

HRWMM和DRDMM都是基于2维的环，以L（a，c）来表示。一个L（a，c）能够被转换为一个，其中，d=2且k=。从而，我们有针对L（a，c）的首次相遇时间和首次返回时间。

引理4.4　环中的首次相遇和返回时间

对于格子环（Torus Lattice）L（a，c），则以高概率有(www.xing528.com)

下面介绍另外一个概念：首次离开时间（First Exiting Time）。令表示与点x距离小于r的点的集合。

定义4.2　首次离开时间

对任意点i，的首次离开时间（记为τE（r））定义为

下面介绍联系时间（Contact Time）。

定义4.3　联系时间

对任意两个点，i和j，联系时间τC（r）的定义为

关于联系时间和首次离开时间，我们有

引理4.5　联系时间和首次离开时间

在HRWMM和DRDMM下，以高概率有