【Python】【原创】马尔可夫链与马尔可夫性质
本帖最后由 白冥 于 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])
此方法用于初始化一个马尔科夫链对象。它接收一个包含转移概率的边列表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)。
示例代码
edges = [
("A", "A", 0.9),
("A", "B", 0.1),
("B", "A", 0.5),
("B", "C", 0.5),
("C", "D", 0.8),
("C", "G", 0.2),
("D", "E", 0.4),
("D", "F", 0.6),
("E", "B", 0.2),
("E", "C", 0.4),
("E", "D", 0.4),
("F", "G", 1.0)
]
# 创建马尔科夫链对象
markov_chain = Markov_chain(edges)
# 执行随机游走
path = markov_chain.random_walk("A", 10)
print("Random walk path:", path)
# 进行状态预测
prediction = markov_chain.predict("A", 5)
print("Prediction after 5 steps:", prediction)
感觉没看懂，还没有学离散数学，太痛苦了 瞧见代码后，有种基因被激发的感觉（脑袋发懵） 。 QAQ ？已经开始星星眼了jpg 头晕目眩 马什么可夫jpg 本可总有一天会在泥潭学会很多知识惹.JPG{:6_169:} 现在各种专业都有计算机相关的必修或者选修课程惹 这次真的是连标题都没看懂了{:6_167:} 隐约好像再概率论数字信号等课程学过。。然而我现在根本不懂唉{:5_132:} 有点好奇楼主的专业，先大胆猜一手应用数学（ 哇塞，看不懂，但十分震撼，佩服，大佬！ 谢谢楼主的分享，对于学计算机的我很有用。 突然回到了写python代码的记忆:o（有些记忆突然唤起） 大学选修过python课但是完全不懂，痛苦的复习记忆涌了上来，还好最后被捞低分飘过 真的是非常让人CPU烧掉的知识了 看到这个代码，感觉大脑都糊了” 我的妈，看到代码之后感觉基因被唤醒了（头大）
楼主好厉害，感觉IT行业内卷的风浪已被证实.jpg 还记得乌克兰战争刚开始的时候，隔壁一个老师为了抵制俄罗斯拒绝讲马可夫链，我怀疑他只是懒 我的天惹，开年初二就开始让我长脑子了，完全看不懂思密达 这些好像是在机器学习的课程里面听过 发帖与专业知识复习兼顾，一举两得是吧{:6_188:} 完全看不懂，只感觉很厉害
页:
[1]
2