在图1-1中，假设从网页A开始浏览．在每一步以相同的概率点击进入当前页的一个外部链接网页，那么需要多少步才能到达网页E？我们把这个时间叫作网页E的击中时间，也叫首通时间，记作TE．从图中可以看到，TE的最小值为2．当然，TE也有可能比2大得多． 图1-7 这可不是我们说的击中时间 1.4.1 平均击中时间 我们的目标是计算从X0 = A开始的TE的均值： . 完成这一计算的关键在于计算从所有可能的初始页面到E的平均击中时间．也就是说，我们要计算当i = A, B, C, D, E时的β(i)， . 这么做的原因在于，从A开始命中E的平均时间与从B和从D开始的平均击中时间相关联，而它们又和从C开始的平均击中时间有关．首先得到 （1.7） 可以这样理解这个式子：从A开始经过1步后，马尔可夫链以1/2的概率转到状态B，而以1/2的概率处于状态D．因此，在1步后，马尔可夫链命中E的平均时间以1/2的概率等于从B开始到命中E的平均时间，以1/2的概率等于从D开始到命中E的平均时间． 这个情况和下面这个例子类似：抛掷一枚均匀硬币，如果正面朝上可以得到随机的X元，如果反面朝上则可以得到随机的Y元．平均下来，可以得到 . 通过类似的论证，可以得到以下和式（1.7）并列的等式： 这些方程和式（1.7）一起构成了首步方程（First Step Equation，FSE）．通过求解方程得到 . 1.4.2 击中另一状态之前命中某一状态的概率 仍然考虑前面的例子，但是这次考虑从网页A开始先访问C再访问E的概率．我们将这一概率记作 . 和前面的情况类似，需要计算所有i = A, B, C, D, E时的α(i)．首先 . （1.8） 式（1.8）成立是因为，从A开始经过1步之后会有两种情况：第一，以1/2的概率处于状态B，然后会以α(B)的概率在E之前访问C；第二，以1/2的概率处于状态D，然后会以α(D)的概率在E之前访问C．因此，从A开始在E之前访问C的事件是这两个互斥事件的集合，因为要么先经过B，要么先经过D，然后再在E之前访问C．将这两个事件的概率相加，得到式（1.8）． 如同计算平均击中时间一样，我们也得到以下的等式组： 这些方程和式（1.8）一起叫作首步方程．解之可得 . 1.4.3 马尔可夫链的首步方程 现在把前面例子中得到的结果推广到任意的有限马尔可夫链．记X = {1, 2, …, N}为状态集合，并记P为马尔可夫链的转移概率矩阵．此时，定义Ti为状态i的击中时间．对于状态集合 ，定义TA = min{n≥0|X(n)∈A}为集合A的击中时间． 第一个扩展考虑TA的平均值．定义 , 则首步方程是 接下来，对两个不相交的集合A和B，即 且A∩B= ，考虑在击中集合B之前击中集合A的概率．定义 , 然后可以得到下述的首步方程组 第三个扩展是 . 这可以理解为每次访问状态i时我们得到h(i)的奖励，直到马尔可夫链进入状态集合A为止．令 可以得到以下的首步方程 （1.9） 第四个扩展是研究 的值． 这里β为折扣因子．令 则首步方程是 希望以上这些例子能让读者大致认识到，许多关于有限状态马尔可夫链的问题都能找到解答的方式．这是一件十分幸运的事情，因为马尔可夫链在对工程和自然系统的建模与模拟中都有着广泛的应用．