L26.8 Mean First Passage Time

Summary

在本视频中，我们继续探讨与马尔科夫链短期行为相关的量。假设我们有一个由单个重现类组成的马尔科夫链，并且我们感兴趣的是从特定的重现状态（例如9）开始，计算从初始状态1到9首次到达所需的期望时间。我们介绍了如何计算从任意起始状态到目标状态的平均首次到达时间，并使用转移图简化计算。之后，我们探讨了重现时间的概念，即从9出发，返回9所需的期望时间，最终展示了相关的数学公式和求解方法。

Takeaways

• 😀 该视频讲解了Markov链的短期行为中的量，如平均首次到达时间和平均回归时间。
• 😀 假设我们有一个包含单一重返类的Markov链，视频中以状态9作为目标状态进行说明。
• 😀 我们的目标是计算从初始状态1出发，首次到达状态9的期望时间。
• 😀 期望首次到达时间是一个随机变量，我们需要计算这个随机变量的期望值。
• 😀 为了简化计算，我们忽略了某些边（即无法通过这些边访问状态9），从而改变了转移概率。
• 😀 通过这个简化的图，我们将问题转化为计算从状态1到状态9的期望时间，使用了吸收状态的概念。
• 😀 计算过程涉及一个系统的方程，通过解这个方程可以得到期望时间。
• 😀 视频还介绍了一个相关问题，即平均回归时间，计算从状态9返回到状态9的期望时间。
• 😀 平均回归时间是一个随机变量，目标是计算从状态9出发，返回到9的平均时间。
• 😀 通过类似的方法，我们使用树形结构来推导出平均回归时间的计算公式，涉及状态转移概率与方程解的结合。
• 😀 最终，平均回归时间的计算公式为：通过状态9的转移概率与其他状态的期望时间加权求和，并加上1步的转移时间。

Q & A

什么是马尔科夫链的平均首次到达时间？

马尔科夫链的平均首次到达时间是指从某个初始状态出发，到达特定状态（例如状态s）所需的期望步数。它是一个随机变量，表示从初始状态i到目标状态s的首次到达的平均时间。

在本视频中，假设的马尔科夫链的状态结构是什么？

视频中的马尔科夫链包含一个递归类（recurrent class）和一些瞬态状态（transient states）。其中，状态9是特定的递归状态，视频关注的是从状态1出发到达状态9的平均首次到达时间。

如何计算从状态1到状态9的首次到达时间？

计算从状态1到状态9的首次到达时间时，我们首先忽略那些在状态9之后可能出现的转移，因为它们在首次到达状态9之前不会发生。通过调整转移概率图，去除无关的转移路径，然后使用吸收状态的计算方法来求解。

在简化后的图中，哪些状态成为了吸收状态？

在简化后的转移图中，状态9成为了唯一的吸收状态，而其他状态（原先的递归状态）都变成了瞬态状态。这种简化使得我们可以使用吸收状态的相关计算来求解问题。

什么是马尔科夫链的平均复归时间？

马尔科夫链的平均复归时间是指马尔科夫链从某一递归状态（如状态9）出发，返回到该状态所需的期望步数。它是一个随机变量，表示从状态9出发，首次返回到状态9的平均时间。

如何计算状态9的平均复归时间？

计算状态9的平均复归时间时，可以利用之前的计算方法。通过构建一个树形结构，考虑从状态9出发到达其他状态（例如状态3、5等）的转移概率，进而求解每个状态到达状态9的平均时间，再结合概率加权求出总体的平均复归时间。

什么是马尔科夫链中的吸收状态？

吸收状态是指一旦马尔科夫链进入该状态，就不会离开该状态。在视频中，状态9被视为吸收状态，因为一旦进入该状态，马尔科夫链就不会再进行其他状态的转移。

如何通过系统方程求解马尔科夫链的平均首次到达时间？

通过构建一个系统方程，其中对于每个状态，设定一个变量表示从该状态到达目标状态（吸收状态）的期望时间。解这个方程组可以得到从任何状态到目标状态的平均首次到达时间。

在视频中，状态i从1开始，为什么选择从状态1出发进行分析？

选择从状态1开始进行分析是为了方便计算并且保持一致性。状态1作为初始状态，允许我们通过该状态到达其他状态，尤其是目标状态9，从而可以计算从1到9的首次到达时间。

如何通过树形结构简化计算平均复归时间？

通过树形结构，我们可以将马尔科夫链从状态9出发的所有可能转移列出，并根据每个转移的概率加权平均计算得到回到状态9的平均时间。每一个转移后的状态都有一个对应的平均首次到达时间，通过加权求和得到整体的平均复归时间。