【Python】【原创】马尔可夫链与马尔可夫性质

白冥 · 发表于 2025-1-30 03:02:06

本帖最后由白冥于 2025-2-10 05:55 编辑

目录

概述
主要功能
类结构与方法
源代码
主要方法
示例代码

概述
      马尔科夫链（Markov Chain）是一种数学模型，描述了一个系统在离散时间内从一个状态转移到另一个状态的过程。在马尔科夫链中，每个状态的转移概率仅与当前状态有关，而与过去的历史无关。
      本帖所提供的代码均由本人编写。

主要功能
      1)路径生成(随机游走)：基于当前状态和转移概率进行多次随机游走，生成可能的状态转移路径。可以用于模拟随机过程，如网页浏览的跳转行为、社交网络的传播过程等。
      2)状态预测：根据初始状态和时间步数，预测马尔科夫链在未来某个时间点可能处于的状态分布。可以用于金融市场预测、天气预测等问题，通过预测未来状态的概率分布来制定决策。

类结构和方法    修改次数1
      Markov_chain 类
         ├ __init__ 方法
         ├ _add_states 方法
         ├ _build_P 方法
         ├ random_walk 方法
         └ predict 方法
      Matrix_Operations 类
         ├ _mul 方法
         └ _pow 方法

源代码    修改次数5
Markov_chain 类：Markov_chain 类

Matrix_Operations类：Matrix_Operations 类

主要方法    修改次数2
1）__init__(self, edges: List[Tuple[str, str, float]])
      此方法用于初始化一个马尔科夫链对象。它接收一个包含转移概率的边列表  edges ，并根据该列表构建状态集合和转移矩阵。
      ○ edges ：一个列表，包含若干元组  (state_0, state_1, cpd) ，其中  state_0  和  state_1  是状态， cpd  是从  state_0  转移到  state_1  的条件概率。

2） _build_P(self, edges, states)
      此方法用于根据边列表和状态集合构建转移矩阵  P 。在此过程中，方法还会检查每个状态的出度和条件概率的有效性。

      ○ P : 转移矩阵描述了在一个N项有限状态空间 S 上的马尔可夫链 {Xₜ}，它的每一项都是一个表示概率的非负实数，其中每一行求和为1。即如果在一个时间步长t→t+1内，Xₜ=sᵢ，sᵢ,sⱼ∈S，从sᵢ转移到sⱼ的条件概率pᵢⱼ = p(Xₜ₊₁=sⱼ | Xₜ=sᵢ)，则P₍ₜ₎₍ₜ₊₁₎（以下简写为P）的第i行第j列由p(Xₜ₊₁=sⱼ | Xₜ=sᵢ)给出。
      ○ 无记忆性(马尔可夫性质)：
            如果学过我上一贴关于贝叶斯网络的坛友都知道，若一个随机变量X的父级变量Pa(X)存在，那么它与它的非后代变量Non-desc(X)条件独立，即X⊥Non-desc(X) | Pa(X)。马尔可夫链{Xₜ}可以看作一种特殊的贝叶斯网络，任意一个随机变量Xₜ₊₁∈{Xₜ}，它的父级Pa(Xₜ₊₁)=Xₜ，它的非后代Non-desc(Xₜ₊₁)=Xₜ₋₁, Xₜ₋₂…, X₀。
(马尔可夫链可以看作一种单链贝叶斯网络)
            即在一个时间步长t→t+1内，在链中给定随机变量Xₜ，则Xₜ₊₁与Xₜ之前的所有变量F(Xₜ)都是条件独立的，记作Xₜ₊₁⊥F(Xₜ) | Xₜ，其中F(Xₜ)=Non-desc(Xₜ₊₁)：P(Xₜ₊₁ | Xₜ, F(Xₜ)) = P(Xₜ₊₁ | Xₜ)。
            由于马尔可夫链过于出名，这种无记忆性也被称为马尔可夫性质。

3） random_walk(self, state: str, time: int)
      ○ 随机游走：随机游走是由一连串轨迹(trajectory)组成，它的每一个微小轨迹都是随机的。因此，绝大多数可见的随机游走，都可以看成马尔可夫链模型或具有马尔可夫性质的类似模型，比如动物的觅食路径、天气的连续变化、股票的涨跌趋势、赌徒的钱包状况，乃至无处不在的布朗运动也是马尔可夫性质的(扩散作用的布朗运动除外)。

4） predict(self, state: str, time: int)
      ○ 状态分布：
            由于随机游走是马尔可夫性质的，因此事实上我们无从同时知道当前状态与将来状态，即当前状态与将来状态是条件独立的。
            然而我们确实需要做到对将来状态的预测，就如古人所说的“未雨绸缪”一样，我们需要知道未来大概率要发生什么。
            任何状态开始，随机游走一步，都相当于一个状态的One-hot向量右乘一个转移矩阵，结果是它的状态分布，即vₛₜₐₜₑP=b₁。因此，对它的每一次随机游走，都等价地右乘一个P，则对于任意k(k∈N*)，都有bₖ=vₛₜₐₜₑPᵏ，代表k步随机游走后它的状态分布，||bₖ||=0，bₖ=(x₁,x₂,x₃,…xɴ)，0≤xᵢ≤1(i=1,2,3,…,N)。

示例代码