线性代数/主题：马尔可夫链

线性代数
← 主题：线性映射的几何	主题：马尔可夫链	主题：正交矩阵 →

这是一个简单的游戏：玩家每次掷硬币下注一美元，游戏结束的条件是玩家要么输光了钱，要么赚到了五美元。如果玩家一开始有3美元，游戏至少进行五次的概率是多少？二十五次呢？

在任何时刻，玩家要么有0美元，要么有1美元，……，要么有5美元。我们称玩家处于状态 $s_{0}$ ， $s_{1}$ ，……，或者 $s_{5}$ 。游戏就是从一个状态移动到另一个状态。例如，现在处于状态 $s_{3}$ 的玩家，在下一次掷硬币时有 $0.5$ 的概率移动到状态 $s_{2}$ ，以及 $0.5$ 的概率移动到 $s_{4}$ 。边界状态略有不同；一旦处于状态 $s_{0}$ 或者状态 $s_{5}$ ，玩家就永远不会离开。

令 $p_{i}(n)$ 表示玩家在第 $n$ 次掷硬币后处于状态 $s_{i}$ 的概率。那么，例如，我们有玩家在第 $n+1$ 次掷硬币后处于状态 $s_{0}$ 的概率为 $p_{0}(n+1)=p_{0}(n)+0.5\cdot p_{1}(n)$ 。这个矩阵方程总结了这一点。

{\begin{pmatrix}1&0.5&0&0&0&0\\0.5&0&0.5&0&0&0\\0&0.5&0&0.5&0&0\\0&0&0.5&0&0.5&0\\0&0&0&0.5&0&0.5\\0&0&0&0&0.5&1\end{pmatrix}}{\begin{pmatrix}p_{0}(n)\\p_{1}(n)\\p_{2}(n)\\p_{3}(n)\\p_{4}(n)\\p_{5}(n)\end{pmatrix}}={\begin{pmatrix}p_{0}(n+1)\\p_{1}(n+1)\\p_{2}(n+1)\\p_{3}(n+1)\\p_{4}(n+1)\\p_{5}(n+1)\end{pmatrix}}

在玩家初始拥有三美元的条件下，计算结果如下。

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$\cdots$	$n=24$
${\begin{pmatrix}0\\0\\0\\1\\0\\0\end{pmatrix}}$	${\begin{pmatrix}0\\0\\0.5\\0\\0.5\\0\end{pmatrix}}$	${\begin{pmatrix}0\\0.25\\0\\0.5\\0\\0.25\end{pmatrix}}$	${\begin{pmatrix}0.125\\0\\0.375\\0\\0.25\\0.25\end{pmatrix}}$	${\begin{pmatrix}0.125\\0.1875\\0\\0.3125\\0\\0.375\end{pmatrix}}$	$\cdots$	${\begin{pmatrix}0.39600\\0.00276\\0\\0.00447\\0\\0.59676\end{pmatrix}}$

正如这个计算探索所表明的，这个游戏不太可能持续很久，玩家很快就会结束在 $s_{0}$ 状态或 $s_{5}$ 状态。例如，在第四次翻转后，游戏已经结束的概率为 $0.50$ 。 (因为进入任何一个边界状态的玩家都不会离开，所以它们被称为吸收态。)

这个游戏是马尔可夫链的一个例子，以 20 世纪上半叶工作的 A.A. 马尔可夫命名。每个 $p$ 向量都是概率向量，矩阵是转移矩阵。马尔可夫链模型的显著特征是无记忆性，即在固定转移矩阵的情况下，下一个状态只取决于当前状态，而不依赖于任何先前的状态。因此，例如，一个从 $s_{3}$ 状态开始，先进入 $s_{2}$ 状态，然后进入 $s_{1}$ 状态，然后又进入 $s_{2}$ 状态的玩家，此时进入 $s_{3}$ 状态的概率，与一个从 $s_{3}$ 状态开始，先进入 $s_{4}$ 状态，然后进入 $s_{3}$ 状态，然后进入 $s_{2}$ 状态的玩家完全一样。

以下来自社会学的马尔可夫链。一项研究 (Macdonald & Ridge 1988，第 202 页) 将英国的职业划分为上层 (高管和专业人士)、中层 (主管和熟练体力劳动者) 和下层 (非熟练劳动者)。为了确定世代之间的流动性，大约两千名男性被问到，“你目前处于哪个层级？当你 14 岁时，你父亲处于哪个层级？”这个等式总结了结果。

{\begin{pmatrix}0.60&0.29&0.16\\0.26&0.37&0.27\\0.14&0.34&0.57\end{pmatrix}}{\begin{pmatrix}p_{U}(n)\\p_{M}(n)\\p_{L}(n)\end{pmatrix}}={\begin{pmatrix}p_{U}(n+1)\\p_{M}(n+1)\\p_{L}(n+1)\end{pmatrix}}

例如，一个下层工人阶级孩子的长大后成为中产阶级的概率为 $.27$ 。需要注意的是，马尔可夫模型关于历史的假设似乎是合理的——我们预计，虽然父母的职业会直接影响孩子的职业，但祖父母的职业不会有这种直接影响。在给定受访者父亲的初始分布的情况下，该表列出了接下来五代的分布。

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$
${\begin{pmatrix}0.12\\0.32\\0.56\end{pmatrix}}$	${\begin{pmatrix}0.23\\0.34\\0.42\end{pmatrix}}$	${\begin{pmatrix}0.29\\0.34\\0.37\end{pmatrix}}$	${\begin{pmatrix}0.31\\0.34\\0.35\end{pmatrix}}$	${\begin{pmatrix}0.32\\0.33\\0.34\end{pmatrix}}$	${\begin{pmatrix}0.33\\0.33\\0.34\end{pmatrix}}$

再来一个例子，来自一个非常重要的主题。美国棒球的世界大赛由赢得美国联盟的球队和赢得国家联盟的球队之间进行（我们遵循 [Brunner]，但也可以参见 [Woodside]）。第一支赢得四场比赛的球队赢得系列赛。这意味着一个系列赛处于 24 个状态之一：0-0（两队都还没有赢球）、1-0（美国联盟队赢了一场，国家联盟队没有赢球）等等。如果我们假设美国联盟队赢得每一场比赛的概率为 $p$ ，那么我们有以下转移矩阵。

{\begin{pmatrix}0&0&0&0&\ldots \\p&0&0&0&\ldots \\1-p&0&0&0&\ldots \\0&p&0&0&\ldots \\0&1-p&p&0&\ldots \\0&0&1-p&0&\ldots \\\vdots &\vdots &\vdots &\vdots \end{pmatrix}}{\begin{pmatrix}p_{\text{0-0}}(n)\\p_{\text{1-0}}(n)\\p_{\text{0-1}}(n)\\p_{\text{2-0}}(n)\\p_{\text{1-1}}(n)\\p_{\text{0-2}}(n)\\\vdots \end{pmatrix}}={\begin{pmatrix}p_{\text{0-0}}(n+1)\\p_{\text{1-0}}(n+1)\\p_{\text{0-1}}(n+1)\\p_{\text{2-0}}(n+1)\\p_{\text{1-1}}(n+1)\\p_{\text{0-2}}(n+1)\\\vdots \end{pmatrix}}

一个特别有趣的特例是 $p=0.50$ ; 该表列出了 $n=0$ 到 $n=7$ 向量的结果成分。（在计算机代数系统 Octave 中生成此表的代码位于练习之后。）

	$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$	$n=6$	$n=7$
0-0	1	0	0	0	0	0	0	0
1-0	0	0.5	0	0	0	0	0	0
0-1	0	0.5	0	0	0	0	0	0
2-0	0	0	0.25	0	0	0	0	0
1-1	0	0	0.5	0	0	0	0	0
0-2	0	0	0.25	0	0	0	0	0
3-0	0	0	0	0.125	0	0	0	0
2-1	0	0	0	0.325	0	0	0	0
1-2	0	0	0	0.325	0	0	0	0
0-3	0	0	0	0.125	0	0	0	0
4-0	0	0	0	0	0.0625	0.0625	0.0625	0.0625
3-1	0	0	0	0	0.25	0	0	0
2-2	0	0	0	0	0.375	0	0	0
1-3	0	0	0	0	0.25	0	0	0
0-4	0	0	0	0	0.0625	0.0625	0.0625	0.0625
4-1	0	0	0	0	0	0.125	0.125	0.125
3-2	0	0	0	0	0	0.3125	0	0
2-3	0	0	0	0	0	0.3125	0	0
1-4	0	0	0	0	0	0.125	0.125	0.125
4-2	0	0	0	0	0	0	0.15625	0.15625
3-3	0	0	0	0	0	0	0.3125	0
2-4	0	0	0	0	0	0	0.15625	0.15625
4-3	0	0	0	0	0	0	0	0.15625
3-4	0	0	0	0	0	0	0	0.15625

请注意，势均力敌的球队很可能会有很长的系列赛——系列赛至少进行六场比赛的概率为 $0.625$ 。

包含本主题的一个原因是马尔可夫链是矩阵运算最广泛的应用之一。另一个原因是它提供了一个矩阵使用的例子，在这个例子中，我们不考虑矩阵所代表的映射的意义。有关马尔可夫链的更多信息，可以参考许多资料，例如 (Kemeny & Snell 1960) 和 (Iosifescu 1980).

练习

使用计算机解决这些问题。例如，您可以修改下面给出的 Octave 脚本。

问题 1

这些问题指的是抛硬币游戏。

检查第一段末尾表格中的计算结果。
考虑向量表中的第二行。注意这一行有交替出现的 $0$ 's。当 $j$ 为奇数时， $p_{1}(j)$ 一定是 $0$ 吗？证明它必须是，或者提供一个反例。
进行一个计算实验，以估计玩家从一美元、两美元和四美元开始，最终达到五美元的概率。

问题 2

我们考虑掷骰子，并说系统处于状态 $s_{i}$ ，如果骰子上出现的最大数字是 $i$ 。

给出转移矩阵。
从状态 $s_{1}$ 开始系统，并运行五次投掷。最后得到的向量是什么？

(Feller 1968, p. 424)

问题 3

人们一直很关注美国工业是否正在从东北部和中北部地区转移到南部和西部，其动机是较温暖的气候、较低的工资和较少的工会化。以下是电力和电子设备大型企业的转移矩阵 (Kelton 1983, p. 43)

	NE	NC	S	W	Z
NE	0.787	0	0	0.111	0.102
NC	0	0.966	0.034	0	0
S	0	0.063	0.937	0	0
W	0	0	0.074	0.612	0.314
Z	0.021	0.009	0.005	0.010	0.954

例如，东北地区的一家公司明年有 $0.111$ 的概率位于西部地区。（Z 条目是“生死”状态。例如，有 $0.102$ 的概率，东北部一家大型电力和电子设备公司将在明年离开该系统：倒闭、搬迁到国外或转为其他类型的公司。有 $0.021$ 的概率，一家处于国家制造商普查的公司将进入电子行业、新创建或从国外搬迁到东北部。最后，根据这项研究，有 $0.954$ 的概率，其他类别的公司将保持不变。

马尔可夫模型假设缺乏历史似乎合理吗？
假设初始分布是均匀的，除了在 $Z$ 处的值为 $0.9$ 。计算 $n=1$ 到 $n=4$ 的向量。
假设初始分布是这个。

NE NC S W Z
0.0000 0.6522 0.3478 0.0000 0.0000

计算 $n=1$ 到 $n=4$ 的分布。
找到 $n=50$ 和 $n=51$ 的分布。系统是否已稳定到均衡状态？

问题 4

该模型已建议用于某些类型的学习（Wickens 1982，第 41 页）。学习者从一个不确定的状态 $s_{U}$ 开始。最终学习者必须决定做出响应 $A$ （即，处于状态 $s_{A}$ ）或响应 $B$ （最终进入 $s_{B}$ ）。但是，学习者不会直接从不确定状态跳到确定 $A$ 是正确选择（或 $B$ ）。相反，学习者会在一个“尝试- $A$ "状态或一个“尝试- $B$ "状态中花费一些时间，尝试做出响应（这里表示为 $t_{A}$ 和 $t_{B}$ ）。假设一旦学习者做出决定，该决定就是最终的，因此一旦 $s_{A}$ 或 $s_{B}$ 被进入，它将永远不会离开。对于其他状态变化，假设以概率 $p$ 在任一方向上进行转换。

构建转移矩阵。
取 $p=0.25$ 并将初始向量取为 $1$ 在 $s_{U}$ 。运行五步。最终到达 $s_{A}$ 的概率是多少？
对 $p=0.20$ 执行相同操作。
绘制图表 $p$ 与最终到达 $s_{A}$ 的概率。是否有一个 $p$ 的阈值，使得学习者几乎可以确定在不超过五步的情况下完成任务？

问题 5

某个城镇位于某个国家（这是一个假设问题）。每年有 10% 的城镇居民迁往该国其他地区。每年有 1% 的来自其他地区的人迁往该城镇。假设有两个状态 $s_{T}$ ，住在城镇里，以及 $s_{C}$ ，住在其他地方。

构建转移矩阵。
从初始分布 $s_{T}=0.3$ 和 $s_{C}=0.7$ 开始，获得前十年的结果。
对 $s_{T}=0.2$ 做同样的操作。
两种结果是否相同还是不同？

问题 6

对于世界大赛的应用，使用计算机为 $p=0.55$ 和 $p=0.6$ 生成七个向量。

即使美国联盟球队赢得任何一场比赛的概率仅为 $0.45$ 或 $0.40$ ，国家联盟球队赢得最终胜利的概率是多少？
绘制图表 $p$ 与美国联盟球队赢得最终胜利的概率。是否有一个阈值——一个 $p$ ，使得实力更强的球队几乎可以确定获胜？

（下面包含一些示例代码。）

问题 7

马尔可夫矩阵的每个条目都是正数，并且每一列的总和为 $1$ .

检查本主题中显示的三个转移矩阵是否满足这两个条件。任何转移矩阵都必须满足这两个条件吗？
观察如果 $A{\vec {v}}_{0}={\vec {v}}_{1}$ 且 $A{\vec {v}}_{1}={\vec {v}}_{2}$ 则 $A^{2}$ 是从 ${\vec {v}}_{0}$ 到 ${\vec {v}}_{2}$ 的转移矩阵。证明马尔可夫矩阵的幂也是马尔可夫矩阵。
通过证明两个适当大小的马尔可夫矩阵的乘积也是一个马尔可夫矩阵来概括前一项。

解决方案

计算机代码

此脚本 markov.m 用于计算机代数系统 Octave 用于生成世界系列结果表。（井号#将该行余下部分标记为注释。）

# Octave script file to compute chance of World Series outcomes.
function w = markov(p,v)
q = 1-p;
A=[0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-0
p,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-0
q,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-1_
0,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-0
0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-1
0,0,q,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-2__
0,0,0,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-0
0,0,0,q,p,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-1
0,0,0,0,q,p, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-2_
0,0,0,0,0,q, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-3
0,0,0,0,0,0, p,0,0,0,1,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 4-0
0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-1__
0,0,0,0,0,0, 0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-2
0,0,0,0,0,0, 0,0,q,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-3
0,0,0,0,0,0, 0,0,0,q,0,0, 0,0,1,0,0,0, 0,0,0,0,0,0;  # 0-4_
0,0,0,0,0,0, 0,0,0,0,0,p, 0,0,0,1,0,0, 0,0,0,0,0,0;  # 4-1
0,0,0,0,0,0, 0,0,0,0,0,q, p,0,0,0,0,0, 0,0,0,0,0,0;  # 3-2
0,0,0,0,0,0, 0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0;  # 2-3__
0,0,0,0,0,0, 0,0,0,0,0,0, 0,q,0,0,0,0, 1,0,0,0,0,0;  # 1-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,p,0, 0,1,0,0,0,0;  # 4-2
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,q,p, 0,0,0,0,0,0;  # 3-3_
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,q, 0,0,0,1,0,0;  # 2-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,p,0,1,0;  # 4-3
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,q,0,0,1]; # 3-4
w = A * v;
endfunction

然后 Octave 会话是这样的。

> v0=[1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0]
> p=.5
> v1=markov(p,v0)
> v2=markov(p,v1)
...

翻译到其他计算机代数系统应该很容易——所有的命令都类似于这些。

参考文献

Feller, William (1968), An Introduction to Probability Theory and Its Applications, vol. 1 (3rd ed.), Wiley.
Iosifescu, Marius (1980), Finite Markov Processes and Their Applications, UMI Research Press.
Kelton, Christina M.L. (1983), Trends on the Relocation of U.S. Manufacturing, Wiley.
Kemeny, John G.; Snell, J. Laurie (1960), Finite Markove Chains, D.~Van Nostrand.
Macdonald, Kenneth; Ridge, John (1988), "Social Mobility", British Social Trends Since 1900, Macmillian.
Wickens, Thomas D. (1982), Models for Behavior, W.H. Freeman.

线性代数
← 主题：线性映射的几何	主题：马尔可夫链	主题：正交矩阵 →

NE	NC	S	W	Z
0.0000	0.6522	0.3478	0.0000	0.0000