专业学习｜马尔可夫链（概念、变体以及例题）

一、马尔可夫链的概念及组成

（一）学习资料分享

来源：024-一张图，但讲懂马尔可夫决策过程_哔哩哔哩_bilibili

        马尔可夫链提供了一种建模随机过程的方法，具有广泛的应用。在实际问题中，通过转移概率矩阵及初始状态分布，我们可以推导出未来的状态概率。这使得马尔可夫链成为许多复杂系统分析中的重要工具。

其余学习文章：马尔可夫链 ▏小白都能看懂的马尔可夫链详解-CSDN博客马尔可夫链 ▏小白都能看懂的马尔可夫链详解-CSDN博客

基础知识：如何理解马尔可夫链？

（二）概念

        马尔可夫链是一种随机过程，其特点是未来的状态只依赖于当前状态，而与过去的状态无关。这一特性称为“无记忆性”或“马尔可夫性质”。马尔可夫链广泛应用于各个领域，包括物理学、经济学、计算机科学等。

（三）基本组成

1. 状态空间：马尔可夫链的所有可能状态的集合，通常用集合 ( S ) 表示。
2. 转移概率：从一个状态转移到另一个状态的概率，通常用转移概率矩阵 ( P ) 表示，其中 ( P(i,j) ) 表示从状态 ( i ) 转移到状态 ( j ) 的概率。
3. 初始状态分布：描述系统在起始时刻处于各状态的概率分布，通常用向量 ( \pi_0 ) 表示。

（四）相关扩展变体

1. 隐马尔可夫模型（HMM）：在观察数据和隐藏状态之间建立联系的模型，常用于语音识别、自然语言处理等领域。

改进点：

• 隐藏状态：在HMM中，系统的状态是不可直接观察的，而只能通过与之相关的观测数据来推断。这与基本马尔可夫模型中的状态是可以直接观察到的情况不同。
• 输出概率分布：HMM引入了从每个隐藏状态生成观测数据的概率分布，使得可以建模更复杂的现象。例如，一个隐藏状态可能对应于多个观测结果，这使得HMM能够处理更加复杂和不确定的情况。
• 序列建模能力：HMM特别适合处理时序数据，比如语音信号或文本序列，通过学习隐藏状态序列与观测数据之间的关系，可以进行预测、分类等任务。

2. 时间非齐次马尔可夫链：转移概率随时间变化的马尔可夫链。

改进点：

• 动态转移概率：在时间非齐次马尔可夫链中，转移概率不仅依赖于当前状态，还依赖于时间。这意味着模型可以捕捉到时间变化带来的影响，能够更精确地描述某些过程，如经济周期的变化。
• 灵活性：这种模型允许在不同时间点使用不同的转移概率矩阵，从而增强了模型的表达能力，可以更好地适应具有时间依赖性的实际应用场景。

3. 连续时间马尔可夫链：状态转移发生在连续时间上的马尔可夫链。

改进点：

• 时间参数化：在连续时间马尔可夫链中，状态转移发生在连续时间上，而不是离散的步骤。这种模型能够更真实地描述一些现实世界中的随机过程，例如排队系统、药物在体内的浓度变化等。
• 指数分布的使用：状态转移间隔时间通常遵循指数分布，使得模型能够自然地处理事件发生的时间间隔，这是在离散时间马尔可夫链中无法实现的。
• 更广泛的应用：连续时间马尔可夫链适用于许多需要实时监控和分析的领域，如生物统计学、金融工程和通信网络等。

（五）例题

（1）例题 0:  马尔可夫链例题

1）例题描述

        假设有一个简单的天气模型，天气状态可以是“晴天”、“阴天”或“雨天”。状态空间 ( S = {晴天, 阴天, 雨天} )。已知转移概率矩阵如下：

	晴天	阴天	雨天
晴天	0.8	0.1	0.1
阴天	0.4	0.4	0.2
雨天	0.2	0.5	0.3

假设今天是晴天，问明天天气为阴天的概率是多少？

2）解题讲解

1. 确定初始状态：根据题意，今天是晴天，因此初始状态分布可以表示为：

2. 利用转移概率矩阵：我们需要找出从“晴天”到“阴天”的转移概率。根据转移概率矩阵，我们可以看到：

3. 最终结果：因此，如果今天是晴天，则明天天气为阴天的概率为 ( 0.1 )。

（2）例题 1：隐马尔可夫模型（HMM）

1）问题描述

        假设有一个隐马尔可夫模型用于识别天气状态与观察到的气象。隐藏状态为“晴天”、“阴天”、“雨天”，观察状态为“户外活动”、“在家”。已知转移概率矩阵和发射概率矩阵如下：

转移概率矩阵 ( P )：

	晴天	阴天	雨天
晴天	0.7	0.2	0.1
阴天	0.3	0.4	0.3
雨天	0.2	0.5	0.3

发射概率矩阵 ( B )：

	户外活动	在家
晴天	0.9	0.1
阴天	0.5	0.5
雨天	0.1	0.9

如果今天观察到的是“户外活动”，求出最可能的天气状态序列。

2）解题讲解

为了求解这个问题，我们可以使用维特比算法，该算法用于寻找最有可能的状态序列。

1.初始化：

• 根据初始状态分布假设，假设初始状态均匀分布。
• 计算每个状态的初始概率乘以观测概率：

2.递推计算：对于后续的观测进行递推计算，每个状态计算最大概率路径：

• 对于第二个观测（假设为“在家”），需要考虑前一步的转移概率和当前的观测概率。
• 重复此过程直到最后一步，选择最大概率路径。

3.回溯找到最优路径：在获得所有状态的最大概率后，回溯找到最优状态序列。

（3）例题 2：时间非齐次马尔可夫链

1）问题描述

        考虑一个市场状态模型，有两种状态：“上涨”和“下跌”。它们的转移概率不是固定不变的，而是随时间变化，如下表所示：

时间	上涨转上涨	上涨转下跌	下跌转上涨	下跌转下跌
t=1	0.6	0.4	0.3	0.7
t=2	0.8	0.2	0.4	0.6

假设在时刻 ( t=0 ) 的状态为“上涨”，计算在时刻 ( t=2 ) 时状态为“下跌”的概率。

2）解题讲解

1. 确定初始状态：在时间 ( t=0 )，状态为“上涨”，即初始状态分布为：

2. 计算转移概率：

   • 从 ( t=0 ) 到 ( t=1 )：

3. 计算从 ( t=1 ) 到 ( t=2 )：

   • 已知在 ( t=1 ) 时状态分布为：
   • 接下来使用 ( t=2 ) 的转移概率矩阵进行计算：

   时间	上涨转上涨	上涨转下跌	下跌转上涨	下跌转下跌
   t=2	0.8	0.2	0.4	0.6

   • 计算在 ( t=2 ) 时状态分布：

   对于状态“上涨”和“下跌”，计算如下：

   • 状态“上涨”在时刻 ( t=2 ) 的概率：

   • 状态“下跌”在时刻 ( t=2 ) 的概率：

4. 结果：因此，在时刻 ( t=2 ) 状态为“下跌”的概率为 ( 0.36 )。

（4）例题 3：吸收马尔可夫链

1）问题描述

考虑一个抽奖游戏，参与者可以处于以下三种状态：

• 状态 0: 未中奖
• 状态 1: 中了一等奖
• 状态 2: 中了二等奖

如果在状态 0，参与者以 50% 的概率中一等奖，以 30% 的概率中二等奖，以 20% 的概率继续保持在状态 0。

已知奖金不再返回到状态 0，因此这是一个吸收马尔可夫链。求在多次抽奖后最终进入状态 1 或状态 2 的概率。

2）解题讲解

1. 建立转移概率矩阵 ( P ):

2. 这里的第一行表示从状态 0 转移到其他状态的概率，第二、第三行分别表示状态 1 和状态 2 是吸收状态。

3. 求解吸收概率：

   • 定义 ( R ) 为吸收状态的概率矩阵，即只有状态 1 和状态 2 的转移概率。即:

   • 计算 ( B ) 为从未中奖状态（状态 0）转入各吸收状态的概率。

   • 首先，计算 ( Q ) 矩阵（非吸收状态间的转移概率）：

1. 求解吸收概率（续）：

   第一个方程表示，从状态 0 转移到状态 1 的概率包括直接转移到状态 1 的概率 ( 0.5 ) 和保持在状态 0 后再次转移到状态 1 的概率 ( 0.2p_1 )。

   第二个方程同理，表示从状态 0 转移到状态 2 的概率。

   • 我们已经建立了状态转移矩阵 ( P ) 和吸收概率矩阵 ( R )。现在，我们需要找到从未中奖状态（状态 0）进入状态 1 和状态 2 的最终概率。

   • 对于这个问题，我们可以通过计算期望吸收时间和对应的吸收概率来解决。首先，定义：

     • ( p_1 ): 从状态 0 进入状态 1 的概率
     • ( p_2 ): 从状态 0 进入状态 2 的概率

   • 因为状态 1 和状态 2 是吸收状态，所以在状态 0 下的转移可以写作：

2. 解方程：

   • 将第一个方程重组为：

   • 第二个方程同样重组为：

3. 结果：

   • 最后，我们得到了从状态 0 开始进入各个吸收状态的概率：

     • 从状态 0 进入状态 1 的概率 ( p_1 = 0.625 )
     • 从状态 0 进入状态 2 的概率 ( p_2 = 0.375 )

   • 验证：这两个概率的总和为 ( p_1 + p_2 = 0.625 + 0.375 = 1 )，符合概率性质。

二、马尔可夫链与动态规划的联系和区别

        马尔可夫链和动态规划虽然在某些方面有交集，但它们的核心理念、应用目标和具体实现方法有所不同。理解这两者的关系和区别，有助于在实际问题中选择合适的工具和方法。

（一）联系

马尔可夫链和动态规划都是处理状态转移和决策过程的重要工具，它们之间存在如下联系：

1. 状态：二者都涉及状态的概念。在马尔可夫链中，状态是系统在某一时刻可能处于的情况；而在动态规划中，状态通常表示某个子问题的解决方案。

2. 转移：马尔可夫链关注状态之间的转移概率，而动态规划则关注从一个状态到下一个状态的决策过程。两者都利用先前的状态信息来推导后续状态。

3. 优化：动态规划常用于求解具有最优子结构性质的问题，而马尔可夫决策过程（MDP）是一种将动态规划应用于随机环境的方法。这使得动态规划可以处理带有不确定性的决策问题。

4. 递归关系：动态规划依赖于递归关系来定义状态间的转移；马尔可夫链也通过转移概率定义了状态之间的关系。

（二）区别

尽管马尔可夫链和动态规划有相似之处，但它们在目的、方法和应用等方面存在显著区别：

1. 目的：

   • 马尔可夫链：主要用于建模和分析随机过程，关注的是状态转移的概率分布。
   • 动态规划：主要用于寻找最优解，关注的是如何在给定条件下做出最佳决策。

2. 决策 vs. 预测：

   • 马尔可夫链：通常是被动的，描述现象的演化，可以用于预测未来状态的概率。
   • 动态规划：是主动的，制定决策以达到目标，通常涉及优化某个目标函数。

3. 模型类型：

   • 马尔可夫链：是一种随机模型，强调无记忆性和状态转移的随机性。
   • 动态规划：可以是确定性的，也可以是随机的，但其核心是通过分解问题并逐步构建解决方案。

4. 应用领域：

   • 马尔可夫链：广泛应用于统计学、金融、物理、计算机科学等领域，尤其是在序列数据和随机过程的分析中。
   • 动态规划：常用在运筹学、算法设计、计算机程序优化等领域，适用于背包问题、最长公共子序列等经典问题。