注明：本文根据数学建模BOOM网课简单整理，自用

❑ 模型简介

❑ 张三的日常

• 法外狂徒张三日常处于以下4种状态之一：行窃、吃喝嫖赌、逃亡和蹲大牢

• 若已知张三当前处于某种状态，则他未来的状态只与现在有关，而与过去无关

• 例如已知昨天张三在吃喝嫖赌、现在张三在逃亡，能影响明天的只有今天“逃亡”的状态

• 那么明天的状态只与今天的“逃亡”有关，而与昨天的“吃喝嫖赌”无关

• 注意，张三的状态是随机的，只能求明天处于每一种状态的概率

• 而这概率又只与今天的状态有关，不需要管昨天或更早的状态是什么

• 描述这种随机现象的模型，称为马尔科夫模型

❑ 从张三到马尔科夫链

• 离散时间：张三的昨天为初始时间𝑛 = 1，则今天为2，明天为3，以及以后的4，5，…

• 状态空间：张三处于行窃状态记为𝑗 = 1，则处于吃喝嫖赌、逃亡和蹲大牢依次记为2，3，4

• 状态：𝑋𝑛 = 𝑗表示第𝑛天张三处于状态𝑗，例如𝑋3 = 2，表示第3天张三处于吃喝嫖赌的状态

• 马尔科夫链：设{𝑋𝑛, 𝑛 = 1,2, … }是一个随机序列（张三在第n天的状态是随机的）

• 假设已知张三第1天为状态3(逃亡)即𝑋1 = 3 ；第2天为状态1（行窃）即𝑋2 = 1，第3天为状态4（蹲大牢）即𝑋3 = 4，……，第𝑛天为状态2（吃喝嫖赌）即𝑋𝑛 = 2

• 那么第𝑛 + 𝑚天张三处于状态1（行窃）的概率（注意等号两边式子差异在哪）：

• 即条件概率表达式里，一大堆的条件都是无用的，只有第𝒏天的条件才是有用的！

• 同样的形式可写出第𝑛 + 1天张三处于状态2、状态3和状态4的概率计算式

❑ 适用赛题

❑ 健康与疾病

• 人的健康状态是会随着时间变化的，而变化又是随机的

• 预测一个人下一年的健康状态，只需要看当前的状态，无需关系过去

• 可能与优化模型结合，例如保险公司追求收益最大化，需要预测投保人的健康状态

❑ 销售与贮存

• 一些奢侈品例如钢琴，一般销量很小，商店不会贮存太多

• 钢琴每周的销售量也是随机的，进货贮存过多会积压资金，贮存过少又有可能失去销售机会

• 商家需要根据一周的销量决定是否进货

❑ 等级结构

• 工程师按照级别分为技术员、助理工程师、中级工程师、副高级工程师和高级工程师

• 一个人明年的级别也是随机的，无论升级还是降级都只与其当前的级别有关

• 预测下一年的级别变动，也可用马尔科夫预测

❑ 此类问题最基本的特点：状态随机，下一阶段的状态只与当前有关

❑ 典型例题与原理讲解

❑时齐性

❑ 时齐的马尔科夫链

• 若第𝑛天张三处于状态𝑖，则经过了m天后，张三处于状态𝑗的概率满足：

• 则称{𝑋𝑛, 𝑛 = 1,2, … }为时齐的马尔科夫链

• 例如已知第3天为状态1（行窃），求7天后(第10天)处于状态4（蹲大牢）的概率：

• 𝑃{𝑋10 = 4 |𝑋3 = 1 }= 𝑃14(7)

• 或者已知第100天为状态1（行窃），求7天后(第107天)处于状态4（蹲大牢）的概率：

• 𝑃{𝑋107 = 4 |𝑋100 }= 1 = 𝑃14(7)

• 同理……

• 若第𝑛天张三处于状态𝑖，则经过了m天后，张三处于状态𝑗的概率满足：

• 则称{𝑋𝑛, 𝑛 = 1,2, … }为时齐的马尔科夫链

• 两种状态转换的概率，只与时间间隔有关，与更早的过去无关，也与起始时刻无关

• 满足这种的条件的马尔科夫链，称为时齐的马尔科夫链，本期课程所讲的都是满足时齐的

• 是否满足时齐，是问题本身决定的（查文献）！一般带有周期性的问题才会满足时齐

• 例如销售类问题，可以在论文的模型假设里写“假设销售规律满足时齐性”

• 𝑚 = 1时，称𝑃𝑖𝑗(1)为一步转移概率，所有𝑃𝑖𝑗(1)所组成的矩阵为马尔科夫链的一步转移矩阵

• 一步转移概率怎么求？问题内在规律推导，根据统计数据计算估计值，查文献

❑典型例题

❑ 计算机运行状态的预测（题目源于《数学建模算法与应用（第三版）》例15.7）

• 设一随机系统状态空间，总共有4种状态，记录观测系统所处状态如下：

• 若该系统可用马尔科夫模型描述，且当前系统处于状态4，则下一步最可能是状态几？

❑求解方法

• 求解一步转移概率：从状态𝑖到状态𝑗的概率的估计值为

 

• 例如，从状态1可以转移到状态1、2、3、4，那么状态1转移到其他状态的总次数，就是观测到的数据中，出现“1 1”“1 2”“1 3”“1 4”的总次数，也就是公式中的分母

❑对已知数据的统计

• 从状态𝑖到状态𝑗的次数统计（不需要手算，代码部分会讲）

• 进而求出一步转移矩阵：

• 其中第𝑖行第𝑗列的数，代表着从状态𝑖一步转移到状态𝑗的概率的估计值

• 题目说当前状态为4，则下一步的状态最有可能是3

❑进一步分析

❑ n步后的概率分布

• 假设该系统初始时4种状态出现的概率为：𝑃(0) = [0.2, 0.3,0.3,0.2]

• 则系统初始化后，运行到第2步最有可能出现状态几？第5步呢？

• 初始概率分布行向量（即初始时每种状态出现的概率）记做𝑃(0)，一步转移概率矩阵记做𝑃

• 则第n步的状态的概率分布为：

• 系统初始化后运行到第2步的概率分布： 𝑃(2) = 𝑃(0)𝑃2 = [0.291, 0.289, 0.271, 0.149]

• 系统初始化后运行到第5步的概率分布： 𝑃(5) = 𝑃(0)𝑃5 = [0.294, 0.289, 0.268, 0.149]

• 注意：求“第n步”状态的概率分布，需要根据题目确定究竟是否把“初始化”算作第1步！

• 系统初始时的概率分布行向量怎么求？与一步转移概率一样：问题内在规律推导，根据统计

数据计算估计值，查文献

❑注意事项

❑ 马尔科夫预测和其他预测有什么不同？

• 其他预测模型：计算的是“数值”，理论上是无数种可能（常见实数集合）

• 马尔科夫预测：计算的是“概率”，需要有限种已知的可能结果

• 例如根据城市近几年的噪声值，预测下一年的噪声值之类的问题

• 因为“噪声值”是数值，理论上可以是任何实数

• 所以有无数种可能的结果，此时就不能用马尔科夫预测

• 例如根据某销量很小的奢侈品过去几个月的销量，预测下个月销量

• 某奢侈品的 “销量”只能是正整数

• 又因为“销量很少”可以根据已知数据假定小于某个正整数（例如月销量不超过10）

• 此时“销量”有0到10总共11个可能的结果

• 可以用马尔科夫预测下个月的销量最有可能是几

❑ 马尔科夫预测的重难点

• 本节课的计算过程都非常简单，没有复杂原理、公式或推导

• 理解马尔科夫链的核心：未来只与当前有关、与过去无关，以及时齐性

• 后续要讲的模拟退火，就是一个马尔科夫过程

• 更多的性质，例如非时齐的情况，以及极限概率分布，以后遇到再讲

• 能否用马尔科夫预测，是看问题本身决定的！即是否有“有限种已知的可能结果”

❑ 代码求解

❑ 求一步转移矩阵

• 一般需要根据已知数据，求出一步转移矩阵的估计值

• 需要遍历已知数据，统计每一组相邻两个状态的数量（找出有多少个“1 1”,“1 2”,……）

• 如果题目所定的系统状态是文字（例如张三的四种状态），那么在写代码时，可以自行定义

不同状态对应的数字，写出矩阵

一步转移概率：

clc, clear

% 题目给我们的是把数据写成了多行，需要把数据改成一行，才方便后面的运算
a0=[4  3  2  1  4  3  1  1  2  3 
   2  1  2  3  4  4  3  3  1  1
   1  3  3  2  1  2  2  2  4  4
   2  3  2  3  1  1  2  4  3  1];
a1=a0';   % 转置
a2=a1(:);    % a1(:)为每列合并成一个长的列向量
a=a2';       % 转置后为一个行向量

%遍历整个字符串，统计每种子字符串的个数
%也就是求任意两种状态相邻的总次数
for i=1:4
   for j=1:4
      f(i,j)=length(strfind(a,[i j])); %统计每种子串的个数；【i，j】在矩阵a中出现的次数
   end
end

ni=sym(sum(f,2));  %sum中的2表示对矩阵f按行求和（语法规则）。若调用sym可转换为符号数
P=f./ni    %状态转移矩阵的估计值

p0=[0.2 0.3 0.3 0.2];
p5=p0*(P^5)