马尔可夫链数学模型基础
[TOC]
马尔可夫链是马尔可夫决策的数学模型, 也是非常重要的随机过程模型. 本文根据《应用随机过程 概率模型导论》教材的第四章内容进行了整理. 主要内容是离散马尔可夫链的基础, 极限概率, 时间可逆的马尔可夫链, 马尔可夫决策过程, 隐马尔可夫链的相关内容. 省略了详细的推导过程, 把比较有用的干货整理了出来.
马尔可夫链
有一系列相继的状态(在时刻$t$时的状态为 $X_i$ , 即 ${\{X_n,n=0,1,2,3,...m\}}$ )的概率过程满足如下性质:在给定的过去的状态 $X_0,X_1,X_2…X_{n-1}$ 和现在的状态 $X_n$, 将来的状态 $X_{n+1}$ 分布独立于过去的状态, 且只依赖现在的状态.
被称作马尔可夫链.
现实的意义在哪里呢? 我们依靠过去的历史去预测未来, 当然想依赖的过去越少越好(不然内存马上爆掉), 最理想的状态下就是只依靠上一时刻的. 但是如此一来肯定不准, 历史那么多信息都有可能有用. 那再加上一个假设, 上一时刻浓缩了历史上所有信息, 这样递归下来, 既满足了不要求太多历史信息导致的内存不够用问题, 也解决了历史信息都能得到反映的问题. 是个理想的模型.
下面 $P_{ij}$ 表示了状态从 $i$ 转到 $j$ 的概率.
$$ \mathrm{P}\left\{X_{n+1}=j \mid X_{n}=i, X_{n-1}=i_{n-1}, \cdots, X_{1}=i_{1}, X_{0}=i_{0}\right\}=P_{i j}\\\\ P_{i j} \geqslant 0, \quad i, j \geqslant 0 ; \quad \sum_{j=0}^{\infty} P_{i j}=1, \quad i=0,1, \cdots $$汇总成矩阵即为概率转移矩阵(单步):
$$
\boldsymbol{P}=\left[\begin{array}{cccc}
P_{00} & P_{01} & P_{02} & \cdots \\
P_{10} & P_{11} & P_{12} & \cdots \\
\vdots & \vdots & \vdots & \\
P_{i 0} & P_{i 1} & P_{i 2} & \cdots \\
\vdots & \vdots & \vdots &
\end{array}\right]
$$
例子: 汽车保险评级概率模型.
中国的汽车保险是参保年内出险次数越多评级越低,下一年度的保金越高. 如果不出险, 评级升高, 下一年度的保金会降低.
假设参保年内一个参保人要求出险的次数 $k$ 的概率 $a_k$ 为参数为 $\lambda$ 的泊松随机分布, 即
$$
a_{k}=\mathrm{e}^{-\lambda} \frac{\lambda^{k}}{k !}, k \geqslant 0
$$
如果某保险公司的评级体系如下表,
$$ \begin{array}{cc|cccc} \hline {}& {}& {}& \qquad {\text { 下一个状态 }} \\ \hline \text { 状态 } & \text { 年保险金 } & 0 \text { 个理赔 } & 1 \text { 个理赔 } & 2 \text { 个理赔 } & 3 \text { 个理赔以上 } \\ \hline 1 & 200 & 1 & 2 & 3 & 4 \\\\ \hline 2 & 250 & 1 & 3 & 4 & 4 \\\\ \hline 3 & 400 & 2 & 4 & 4 & 4 \\\\ \hline 4 & 600 & 3 & 4 & 4 & 4 \\\\ \hline \end{array} $$可得状态转移概率矩阵如下:
$$
\boldsymbol{P}=\left[\begin{array}{lllll}
a_{0} & a_{1} & a_{2} & 1-a_{0}-a_{1}-a_{2} \\
a_{0} & 0 & a_{1} & 1-a_{0}-a_{1} & \\
0 & a_{0} & 0 & 1-a_{0} & \\
0 & 0 & a_{0} & 1-a_{0} &
\end{array}\right]
$$
可以看到每行的概率之和为 1.
C-K 方程
C-K 方程表达形式如下:
$$
P_{i j}^{n+m}=\sum_{k=0}^{\infty} P_{i k}^{n} P_{k j}^{m} \text {, for all } n, m \geqslant 0, \text { for all } i, j
$$
其中, $P_{ij}^{n}$ 为经历 $n$ 步的转移概率.
C-K 方程表示为从 $i$ 到 $j$ 经历 $n+m$ 步的转移概率等于经历所有中间状态 $k$ 的 $n$ 步与 $m$ 步乘积的和.
经过 $n$ 步的状态转移矩阵可以由 $P^{n}$ 表示, 由单步转移矩阵 $P$ 自乘 $n$ 次得到. $P$ 的维度为 $m \times m$ 的话, $P^n$ 的维度仍为 $m \times m$.
例子: 假定球被逐个放入 8 个罐中, 各球以相同可能性放入各个罐中. 问在经过 9 次放球后恰好有 3 个罐不是空的概率是多少?
模型: $X_n$ 记为有 $n$ 个非空罐子的事件, 则 ${X_n,n \geq 0}$ 为马尔可夫链, 状态为 $[0,1,2…8]$, 共 9 个状态.
状态转移方程: $P_{i,i}=\frac{i}{8} = 1-P_{i,i+1}, \quad i=0,1,2…8$
问题等同于求解: $P_{0,3}^9$
简化:
- 状态 $0$ 与 $1$ 相同, 只要开始放球, 必定有一个罐子非空, 即 $P_{0,1}=1$, 以及 $P_{0,3}^9 = P_{1,3}^8$.
- 由于我们只关心状态 $1,2,3, \geq 3$ 这 4 种状态, 考虑将 $\geq 3$ 的五种状态合并, 并且考虑到不影响马尔可夫性, 因此考虑新状态: $[1,2,3,4]$.
新状态下的状态转移矩阵如下:
$$
\left[\begin{array}{cccc}
\frac{1}{8} & \frac{7}{8} & 0 & 0 \\
0 & \frac{2}{8} & \frac{6}{8} & 0 \\
0 & 0 & \frac{3}{8} & \frac{5}{8} \\
0 & 0 & 0 & 1
\end{array}\right]
$$
$P^8$ 可以拆解为 $P^4P^4$, 因此只要一个 $P^4$ 即可, 如下:
$$
\left[\begin{array}{ccc}
0.0002 & 0.0256 & 0.2563 & 0.7178 \\
0 & 0.0039 & 0.0952 & 0.9009 \\
0 & 0 & 0.0198 & 0.9802 \\
0 & 0 & 0 & 1
\end{array}\right]
$$
应用 C-K 方程可得
$P_{1,3}^8 = P_{1,1}^4P_{1,3}^4 + P_{1,2}^4P_{2,3}^4 + P_{1,3}^4P_{3,3}^4 + P_{1,4}^4P_{4,3}^4$
$$
P_{1,3}^8 = 0.0002 \times 0.2563+0.0256 \times 0.0952+0.2563 \times 0.0198+0.7178 \times 0=0.00756
$$
这样就可以不用计算 $P^8$ 也可以求得结果, 明显效率更高.
构建含有吸收态的马尔可夫链模型
先从例子入手:
在一系列独立抛掷公平硬币的试验中, $N$ 表示直至出现连续 3 次正面的抛掷次数. 求
- $P(N) \leq 8$
- $P(N) = 8$
模型:构建状态为 $[i=0,1,2,3]$ 的马尔可夫链, 其中 $i$ 表示相继为正面的 $i$ 个连贯. 得到转移矩阵如下:
$$
P=\left(\begin{array}{cccc}
1 / 2 & 1 / 2 & 0 & 0 \\
1 / 2 & 0 & 1 / 2 & 0 \\
1 / 2 & 0 & 0 & 1 / 2 \\
0 & 0 & 0 & 1
\end{array}\right)
$$
$$
P^{s}=\left(\begin{array}{ccc}
81 / 256 & 44 / 266 & 24 / 256 & 107 / 256 \\
68 / 266 & 37 / 256 & 20 / 2026 & 131 / 256 \\
44 / 256 & 24 / 256 & 13 / 256 & 175 / 256 \\
0 & 0 & 0 & 1
\end{array}\right)
$$
问题1: 等于求解 $P_{0,3}^8=107/256$.
问题2: 有 2 种解法.
- $P(N=8)=P(N\leq8)-P(N\leq7)=P_{0,3}^8-P_{0,3}^7$
- 吸收态的马尔可夫链模型.
由于对次数进行了准确的限制, 也就是说一旦出现了连续 3 次正面的情况下, 应该不会往下进行了(也就是往下进行的概率为0, $i=3$ 状态为吸收态).
用数学语言描述: 对具有 $P_{i,j}$ 转移概率的马尔可夫链${X_n}$. 状态集为 $\mathscr{A}$ 吸收态集(一旦进入就无法转移到其他状态中), 初始状态 $i$ 不属于吸收态, $m$ 次转移内进入吸收态集的概率为 $\beta$.
$$
\beta=\mathrm{P}\left(X_{k} \in \mathscr{A}, \text { for some } k=1, \cdots, m \mid X_{0}=i\right)\
$$
可以在原马尔可夫链的基础上构造新的马尔可夫链 ${W_n}$, 追加吸收态集 $A$.
马尔可夫链 ${W_n}$ 的转移概率 $Q_{i,j}$ 为:
$$
\begin{array}{ll}
Q_{i, j}=P_{i, j}, & \text { if } i \notin \mathscr{A}, j \notin \mathscr{A} \\
Q_{i, A}=\sum_{j \in \mathscr{A}} P_{i, j}, & \text { if } i \notin \mathscr{A} \\
Q_{A, A}=1
\end{array}
$$
从而得到 $\beta=\mathrm{P}\left(W_{m}=A \mid X_{0}=i\right)=\mathrm{P}\left(W_{m}=A \mid W_{0}=i\right)=Q_{i, A}\\$
回到原问题中, 追加一个 3 连贯的吸收态构造新的马尔可夫链得到
$$
Q=\left(\begin{array}{ccccc}
1 / 2 & 1 / 2 & 0 & 0 & 0 \\
1 / 2 & 0 & 1 / 2 & 0 & 0 \\
1 / 2 & 0 & 0 & 1 / 2 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1
\end{array}\right)
$$
$P(N=8)=Q_{0,3}^8$
更一般地得到
若 $i \notin \mathscr{A}, j \in \mathscr{A}$
$$ \begin{aligned} \alpha=& \sum_{r \notin \mathscr{A}} \mathrm{P}\left(X_{m}=j, X_{m-1}=r, X_{k} \notin \mathscr{A}, k=1, \cdots, m-2 \mid X_{0}=i\right) \\ =& \sum_{r \notin \mathscr{A}} \mathrm{P}\left(X_{m}=j \mid X_{m-1}=r, X_{k} \notin \mathscr{A}, k=1, \cdots, m-2, X_{0}=i\right) \\ & \times \mathrm{P}\left(X_{m-1}=r, X_{k} \notin \mathscr{A}, k=1, \cdots, m-2 \mid X_{0}=i\right) \\ =& \sum_{r \notin \mathscr{A}} \mathrm{P}_{r, j} \mathrm{P}\left(X_{m-1}=r, X_{k} \notin \mathscr{A}, k=1, \cdots, m-2 \mid X_{0}=i\right) \\ =& \sum_{r \notin \mathscr{A}} \mathrm{P}_{r, j} Q_{i, r}^{m-1} \end{aligned} $$ 若 $i \in \mathscr{A}, j \notin \mathscr{A}$ $$ \mathrm{P}\left(X_{m}=j, X_{k} \notin \mathscr{A}, k=1, \cdots, m-1 \mid X_{0}=i\right)=\sum_{r \notin \mathscr{A}} Q_{r,j}^{m-1} \mathrm{P}_{i, r} $$ 若 $i, j \notin \mathscr{A}$ $$ \begin{aligned} & \mathrm{P}\left\{X_{n}=j \mid X_{0}=i, X_{k} \notin \mathscr{A}, k=1, \cdots, n\right\} \\ =& \frac{\mathrm{P}\left\{X_{n}=j, X_{k} \notin \mathscr{A}, k=1, \cdots, n \mid X_{0}=i\right\}}{\mathrm{P}\left\{X_{k} \notin \mathscr{A}, k=1, \cdots, n \mid X_{0}=i\right\}}=\frac{Q_{i, j}^{n}}{\sum_{r \notin \mathscr{A}} Q_{i, r}^{n}} \end{aligned} $$状态的分类
- 可达: 从状态 $i$ 到 $j$:$P_{i,j}^n, n \geq 0$.
- 互通: 互相可达, $i \leftrightarrow j$.
互通的性质:- 自我互通: $i$ 与 $i$ 互通.
- 互相互通: $i$ 与 $j$ 互通, 那么 $j$ 与 $i$ 互通.
- 互通传递: $i$ 与 $j$ 互通, $j$ 与 $k$ 互通, 那么 $i$ 与 $k$ 互通.
- 类: 互通的状态集合, 互通将状态空间划分为分离的类.
- 不可约: 没有互通的状态的马尔可夫链.
- 常返态: 对于任意状态 $i$,$f_i$ 为开始在 $i$ 后面迟早会进入 $i$ 的概率. $f_i=1$
- 暂态: $f_i<1$.
命题: $i$ 为
常返态, $\text{if} \quad \sum_{n=1}^{\infty} P_{i i}^{n}=\infty $
暂态, $\text{if} \quad \sum_{n=1}^{\infty} P_{i i}^{n}<\infty$
推论:
- 有限状态的马尔可夫链至少有一个常返态.
- 若 $i$ 是常返态且 $j$ 与 $i$ 互通, $j$ 也是常返态.
- 不可约马尔可夫链的状态都为常返态.
随机游动
一个由 $[0,\pm1,\pm2…]$ 状态组成的马尔可夫链, 转移概率如下:
$$
P_{i, i+1}=p=1-P_{i,i-1}, \quad i=0, \pm 1, \pm 2, \ldots\
$$
实际案例可以是醉汉沿直线行走, 也可以是赌徒收获(每次赢或者输 1 块钱).
赌博模型指出上述模型奇数次赌博不可能平局, 对于偶数次从状态 $0$ 回到 $0$ 的概率经过推导可以得到:
$$
P_{00}^{2 n} \sim \frac{(4 p(1-p))^{n}}{\sqrt{\pi n}}\
$$
其中 $p$ 为每次赢钱的概率, $1-p$ 为输钱的概率.
当且仅当 $p=\frac{1}{2}$ 时, 上式为 $\infty$, 被称为对称随机游动.
也就是说 $p=\frac{1}{2}$ 时, 链为常返的, 否则是暂态的.
对于二维的情况如下对称才会常返:
$$
P_{(i, j),(i+1, j)}=P_{(i, j),(i-1, j)}=P_{(i, j),(i, j+1)}=P_{(i, j),(i, j-1)}=\frac{1}{4}
$$
对称=常返进对一维/二维有效对于更高维度不适用.
长程性质和极限概率
研究马尔可夫链很多时候是研究一系列的转移过后的性质, 例如到达某个状态多少次, 假设每个状态停留时间相同的话, 多少次也就对应着在某个状态呆了多长时间, 由此引出长程的概念. 以及一直转移下去的极限是什么情况, 引出了稳态概率与极限概率的概念.
定义
一个函数 $f_{i,j} \quad i \ne j$, 表示从马尔可夫链的状态 $i$ 迟早到 $j$ 的概率.命题
若 $i$ 是常返的且 $i$ 与 $j$ 互通, 则 $f_{i,j}=1$.定义
$$ N_{j}=\min \left\{n>0: X_{n}=j\right\}\\ m_{j}=\mathrm{E}\left[N_{j} \mid X_{0}=j\right]\\ $$
若 $j$ 是常返的, 用 $m_j$ 标记从 $j$ 开始返回 $j$ 的期望转移次数.
- 正常返: $m_j < \infty$.
零常返: $m_j = \infty$.
长程时间比例有时也被称为平稳概率: $\pi_j$ 马尔可夫链在状态 $j$ 的停留时间比例.
- 命题
若马尔可夫链是不可约且常返的, 对于任意初始状态有:
$$
\pi_j = \frac{1}{m_j}
$$
正常返的性质:
若 $i$ 正常返且 $i \leftrightarrow j$, 则 $j$ 正常返.
若 $i$ 零常返且 $i \leftrightarrow j$, 则 $j$ 零常返.
一个不可约的有限马尔可夫链必须是正常返.
- 命题
一个不可约的马尔可夫链, 若是正常返的长程比例是下面方程的唯一解. 若下面线性方程无解, 则此马尔可夫链是暂态的或者是零常返的, 且一切 $\pi_j=0$.
$$
\begin{gathered}
\pi_{j}=\sum_{i} \pi_{i} P_{i, j}, \quad j \geqslant 1 \
\sum_{j}^{i} \pi_{j}=1
\end{gathered}
$$
例子: 阶层迁移模型
社会分为高, 中, 低三个阶层, 且家庭后继代的阶层转移主要受父母影响, 此转移过程可以看作马尔可夫链. 转移方程如下:
$$
P=\left[\begin{array}{lll}
0.45 & 0.48 & 0.07 \\
0.0 .0 & 0.70 & 0.25 \\
0.01 & 0.50 & 0.49
\end{array}\right]
$$
列出线性方程组求解得
$$
\begin{aligned}
&\pi_{0}=0.45 \pi_{0}+0.05 \pi_{1}+0.01 \pi_{2}\\
&\pi_{1}=0.48 \pi_{0}+0.70 \pi_{1}+0.50 \pi_{2}\\
&\pi_{2}=0.07 \pi_{0}+0.25 \pi_{1}+0.49 \pi_{2}\\
&\pi_{2}=0.070_{0}+0.25_{1} \\
&\pi_{0}+\pi_{1}+\pi_{2}=1
\end{aligned}
$$
解为
$$
\pi_{0}=0.07, \quad \pi_{1}=0.62, \quad \pi_{2}=0.31
$$
也就是说长期来看社会会稳定在 7% 的人在高阶层, 62% 的人在中阶层, 31% 的人在低阶层.
还有一个例子是遗传学中的哈代-温伯格律.
- 命题
若初始状态选为 $j$ 的概率是 $\pi_j$ 则任意时间 $n$ 处于 $j$ 的概率也是 $\pi_j$. $\pi_j$ 即为平稳概率. $$ \begin{gathered} \mathrm{P}\left\{X_{0}=j\right\}=\pi_{j}, \quad j \geqslant 0 \\ \mathrm{P}\left\{X_{n}=j\right\}=\pi_{j}, \quad \text { for all } \quad n, j \geqslant 0 \end{gathered} $$
报酬函数
对于不可约的有平稳概率 $\pi_j(j \geq 0)$ 的马尔可夫链 ${X_n,n\geq0}$, $r$ 为状态空间上的有界函数(可以理解为链在状态 $j$ 时的时长报酬). 那么以概率 1 有如下:
$$ \lim _{N \rightarrow \infty} \frac{\sum_{n=1}^{N} r\left(X_{n}\right)}{N}=\sum_{j=0}^{\infty} r(j) \pi_{j} $$ 证明: $$ \sum_{n=1}^{N} r\left(X_{n}\right)=\sum_{j=0}^{\infty} a_{j}(N) r(j) $$ $a_{j}(N)$ 为从 $1,...N$ 在 $j$ 上度过的全部时间, 而且 $a_{j}(N)/N \rightarrow \pi_j$, 由此得证.极限概率
貌似平稳概率就是极限概率, 但是对于周期的马尔可夫链, 是没有极限概率的. 例如转移方程如下
$$
P_{0,1}=P_{1,0}=1
$$
可得两个状态的平稳概率如下:
$$
\begin{gathered}
\pi_{0}=\pi_{1}=1 / 2 \\
P_{0,0}^{n}= \begin{cases}1, & \text { 若 } n \text { 偶 } \\
0, & \text { 若 } n \text { 奇 }\end{cases}
\end{gathered}
$$
对于非周期的马尔可夫链, 各状态的平稳概率就是极限概率.
在暂态停留的平均时间
暂态无法应用到平稳概率的概念. 如何计算其平均时间呢?
1. 构造一个仅暂态存在的转移矩阵 $\boldsymbol{P}_{T}$. $$ \boldsymbol{P}_{T}=\left[\begin{array}{cccc} P_{11} & P_{12} & \cdots & P_{1 t} \\ \vdots & \vdots & \vdots & \vdots \\ P_{t 1} & P_{t 2} & \cdots & P_{t t} \end{array}\right] $$ 2. 定义 $s_{i,j}$ 为初始状态 $i$ 到 $j$, 在 $j$ 的平均停留时间. $$ s_{i j}=\delta_{i, j}+\sum_{k} P_{i k} s_{k j}=\delta_{i, j}+\sum_{k=1}^{t} P_{i k} s_{k j} \\\\ where \quad \delta_{i, j} = \begin{cases} 1, &i=j \\ 0, &i \ne j \end{cases} $$ 3. 换成矩阵形式: $$ \boldsymbol{S}=\boldsymbol{I}+\boldsymbol{P}_{T} \boldsymbol{S} \\\\ \boldsymbol{S}=\left(\boldsymbol{I}-\boldsymbol{P}_{T}\right)^{-1} $$- 计算进入暂态的”平稳概率”.
$$
\begin{aligned}
s_{i j}=& \mathrm{E}[\text { 在 } j \text { 的时间 } \mid \text { 开始在 } i \text {, 最终转移到 } j] f_{i j} \\
&+\mathrm{E}[\text { 在 } j \text { 的时间 } \mid \text { 开始在 } i, \text { 永不转移到 } j]\left(1-f_{i j}\right) \\
=&\left(\delta_{i, j}+s_{j j}\right) f_{i j}+\delta_{i, j}\left(1-f_{i j}\right) \\
=& \delta_{i, j}+f_{i j} s_{j j}
\end{aligned}
$$
得到 $f_{i,j}$ 为初始为 $i$ 最终为 $j$ 的概率.
$$
f_{i j}=\frac{s_{i j}-\delta_{i, j}}{s_{j j}}
$$
例子:
赌博问题: $p=0.4,N=7$, 初期财富为 3, 求1)赌徒最终财富为 5 的期望. 2)最终财富为 1 的概率.
问题 1 对应的为: $s_{3,5}=0.9228$.
问题 2 对应的为: $f_{3,1}=-\frac{s_{3,1}}{s_{1,1}}=0.8797$.
分支过程
分支过程为一种特殊的马尔可夫链. 在生物繁衍上举例, 每个个体在其生命结束时以 $P_j<1(j \geq 0)$ 产生 $j$ 个后代, 不同个体产生后代之间互不影响. ${ X_n, n \geq0 }$ 代表第 $n$ 代个体个数为马尔可夫链.
除了 $P_{0,0}=1$ 为常返态(因为 $P_{i,0}=P_0^i$), 若 $P_0>0$ 其余皆为暂态, 也就是说最终要么整体灭亡要么无限繁殖.
如何计算整体灭亡的概率 $\pi_0$ 呢?
用 $\mu$ 代表单个个体后代的均值: $\mu=\sum_{j=0}^{\infty} j P_{j}$.
对不同 $\mu$ 下 $\pi_0$ 的值如下:
$$
\mu \leq 1, \quad \pi_0 = 1 \\
\mu >1, \quad \pi_{0}=\sum_{j=0}^{\infty} \pi_{0}^{j} P_{j}
$$
时间可逆的马尔可夫链
对于转移概率 $P_{i,j}$ 以及平稳概率 $\pi _i$ 的马尔可夫链 $\{ X_n, n \geq 0 \}$. 其逆马尔可夫链 ${Q_n,n=n,n-1,n-2...0}$ 的转移概率 $Q_{i,j}$ 推导如下: $$ \begin{aligned} Q_{i j} &=\mathrm{P}\left\{X_{m}=j \mid X_{m+1}=i\right\} \\ &=\frac{\mathrm{P}\left\{X_{m}=j, X_{m+1}=i\right\}}{P\left\{X_{m+1}=i\right\}} \\ &=\frac{\mathrm{P}\left\{X_{m}=j\right\} \mathrm{P}\left\{X_{m+1}=i \mid X_{m}=j\right\}}{\mathrm{P}\left\{X_{m+1}=i\right\}} \\ &=\frac{\pi_{j} P_{j i}}{\pi_{i}} \end{aligned} $$如果 $P_{i,j}=Q_{i,j}$, 则成该马尔可夫链为时间可逆的马尔可夫链.
$$
\pi_{i} P_{i j}=\pi_{j} P_{j i}, \text { for all } i, j
$$
省略后面的相关介绍, 用到时再查.
马尔可夫链蒙特卡罗方法
即通过生成一个具有特定平稳概率的马尔可夫链去实现特定的随机向量从而实现蒙特卡罗方法.
一种可以实现生成一个具有任意平稳概率的马尔可夫链的算法:梅特罗波利斯－黑斯廷斯算法(Metropolis–Hastings algorithm). 具体不展开.
马尔可夫决策过程
动作: 在时刻 1$n$, 状态 $i$ 下选取不同动作 $a$ 会导致下一时刻 $n+1$ 的状态不同.
本质是为 2 维的马尔可夫链:
策略: 选取动作的规则 $\beta$, 一般可以限制策略仅依赖于当时过程的状态, 与以前的状态与动作无关. 策略是可以按概率分布选取动作. 即 $\beta=\left\{\beta_{i}(a), a \in A, i=1, \cdots, M\right\}$.
满足:
隐马尔可夫链
考虑一种情况, 马尔可夫链的状态本身无法直接观测确定, 但是可以观测得到每个状态发出的特定信号 $s$ (信号与状态是一一对应的关系), 那么以 $s$ 及其序列 $S_n$ 在不可观测的状态 $j$ 下的概率表述如下: $$ \mathrm{P}\left\{S_{1}=s \mid X_{1}=j\right\}=p(s \mid j), \quad \mathrm{P}\left\{S_{n}=s \mid X_{1}, S_{1}, \cdots, X_{n-1}, S_{n-1}, X_{n}=j\right\}=p(s \mid j) $$ 这样的模型被称为**隐马尔可夫链**. 对于隐马尔可夫链,我们能计算的是对于信号的概率. 具体来说, 对于符合某种概率分布的随机向量 $\boldsymbol{S}^n=(S_1,...,S_n)$ 表示前 $n$ 个信号, 实际获得的信号序列为 $\boldsymbol{s}_n=s_1,...s_n$ . 用下式表述该概率: $$ F_{n}(j)=\mathrm{P}\left\{\boldsymbol{S}^{n}=\boldsymbol{s}_{n}, X_{n}=j\right\} $$ 推导如下: $$ \begin{aligned} F_{n}(j) &=\mathrm{P}\left\{\boldsymbol{S}^{n-1}=\boldsymbol{s}_{n-1}, S_{n}=s_{n}, X_{n}=j\right\} \\ &=\sum_{i} \mathrm{P}\left\{\boldsymbol{S}^{n-1}=\boldsymbol{s}_{n-1}, X_{n-1}=i, X_{n}=j, S_{n}=s_{n}\right\} \\ &=\sum_{i} F_{n-1}(i) \mathrm{P}\left\{X_{n}=j, S_{n}=s_{n} \mid \boldsymbol{S}^{n-1}=\boldsymbol{s}_{n-1}, X_{n-1}=i\right\}\\ &=\sum_{i} F_{n-1}(i) \mathrm{P}\left\{X_{n}=j, S_{n}=s_{n} \mid X_{n-1}=i\right\} \\ &=\sum_{i} F_{n-1}(i) P_{i, j} p\left(s_{n} \mid j\right) \\ &=p\left(s_{n} \mid j\right) \sum_{i} F_{n-1}(i) P_{i, j} \end{aligned} $$因此可以通过前向递推得到 $F_{n}(i)$:
$$ F_{1}(i)=\mathrm{P}\left\{X_{1}=i, S_{1}=s_{1}\right\}=p_{i} p\left(s_{1} \mid i\right) $$ 对于 $\mathrm{P}\{\boldsymbol{S}^{n}=\boldsymbol{s}_{n}\}$ 的计算, 通过下面的和求得. $$ \mathrm{P}\left\{\boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\}=\sum_{i} F_{n}(i) $$ 计算复杂度 $O(nN^2)$, $N$ 为状态数, $n$ 为时刻数.如果我们知道中间值的话可以前向递推+后向递推的形式节省计算资源.
后向递推: $$ B_{k}(i)=\mathrm{P}\left\{S_{k+1}=s_{k+1}, \cdots, S_{n}=s_{n} \mid X_{k}=i\right\} $$ 递推公式为: $$ B_{k}(i)= \sum_{j} p\left(s_{k+1} \mid j\right) B_{k+1}(j) P_{i, j} $$ 前向后向结合得: $$ \mathrm{P}\left\{\boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\}=\sum_{j} F_{k}(j) B_{k}(j) $$预测状态
仅仅知道信号的概率有时候是不够的, 我们希望找到对真实状态的估计. 例如构造问题: 使正确预测的状态数目的期望最大. 即寻找状态序列 $i_1,...,i_n$ 使得下面式子最大 $$ \mathrm{P}\left\{\boldsymbol{X}_{n}=\left(i_{1}, \cdots, i_{n}\right) \mid \boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\}=\frac{\mathrm{P}\left\{\boldsymbol{X}_{n}=\left(i_{1}, \cdots, i_{n}\right), \boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\}}{\mathrm{P}\left\{\boldsymbol{S}^{n}=\boldsymbol{s}_{s}\right\}} $$ 引入 $V_{k}(j)$ $$ V_{k}(j)=\max _{i_{1}, \cdots, i_{k-1}} \mathrm{P}\left\{\boldsymbol{X}_{k-1}=\left(i_{1}, \cdots, i_{k-1}\right), X_{k}=j, \boldsymbol{S}^{k}=\boldsymbol{s}_{k}\right\} $$ 推导得 $$ V_{k}(j) = p\left(s_{k} \mid j\right) \max _{i} P_{i, j} V_{k-1}(i) $$ 得到递推公式如下: $$ V_{1}(j)=\mathrm{P}\left\{X_{1}=j, S_{1}=s_{1}\right\}=p_{j} p\left(s_{1} \mid j\right) $$ 原问题的递推求解公式如下: $$ \begin{aligned} & \max _{i_{1}, \cdots, i_{n}} \mathrm{P}\left\{\boldsymbol{X}_{n}=\left(i_{1}, \cdots, i_{n}\right), \boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\} \\ =& \max _{j} V_{n}(j) \\ =& V_{n}\left(j_{n}\right) \\ =& \max _{i_{1}, \cdots, i_{n-1}} \mathrm{P}\left\{\boldsymbol{X}_{n}=\left(i_{1}, \cdots, i_{n-1}, j_{n}\right), \boldsymbol{S}^{n}=\boldsymbol{s}_{n}\right\} \\ =& p\left(s_{n} \mid j_{n}\right) \max _{i} P_{i, j_{n}} V_{n-1}(i) \\ =& p\left(s_{n} \mid j_{n}\right) P_{i_{n-1}\left(j_{n}\right), j_{n}} V_{n-1}\left(i_{n-1}\left(j_{n}\right)\right) \end{aligned} $$此种算法被称作维特比算法(Viterbi)