10-首次到达时间

回顾

考虑网络

有效电阻定义为

考虑该网络上的随机游走。格林函数定义为

我们有

今天的目标

• 首次到达时间；
• 往返时间；
• 传递网络。

目标时间

假设

是一条不可约马尔可夫链，其转移矩阵为 ，平稳测度为 。令 表示首次到达状态 的时刻：

引理. 数量

与起点 无关。我们称它为目标时间，并将其记为

首次到达时间

定义. 定义最坏情形首次到达时间为

由目标时间的定义，

引理. 假设该链不可约，并具有平稳测度 。则

定理. 对一条不可约传递马尔可夫链，

传递马尔可夫链

粗略地说，从状态空间中的任何一点看过去，一条传递马尔可夫链都“具有相同的样子”。

定义. 如果对每一对

都存在一个双射

使得

并且对任意 ，

则称该马尔可夫链是传递的。

例. -循环上的简单随机游走和超立方体上的简单随机游走都是传递马尔可夫链。

引理. 对有限状态空间 上的传递马尔可夫链，均匀测度是平稳测度。

往返时间

定义. 假设马尔可夫链从

出发。定义 与 之间的往返时间为

也就是说，链从 出发，先到达 ，随后返回 ；完成这一往返过程所需的总时间就是 。

定理（往返时间恒等式）. 考虑网络

上的随机游走，则

其中 表示网络的总电导。

引理. 假设马尔可夫链不可约，并具有平稳测度 。又设 是一个停时，并满足

则

传递网络

一般而言，

可能相差很大，参见练习 10.3。但是，如果网络是传递的，这两个期望就相等。

定义. 如果对每一对

都存在一个双射

使得

并且对任意 ，

则称网络

是传递的。

注. 传递网络上的随机游走是一条传递马尔可夫链。

定理. 对传递连通网络上的随机游走，以及任意顶点 ，都有

总结

对于一般网络上的随机游走，

并且

对于传递网络上的随机游走，

从而

这些关系可以概括为

麻省理工学院开放式课程