0%

随机过程之离散马可夫链笔记

以下定义和性质针对于离散状态离散时间时齐马可夫链。

一些说明

事物所处的状态(通常用 $1,2,3\dots$ 表示)称为状态,状态的全体称为状态空间(记为 $S$)。

一些定义

马可夫链(Markov)实质上是说明未来的状态与现在的状态有关,而与过去的状态无关,用条件概率表示为

$$P(X_n = j | X_{n-1}=i,X_{n-2}=k_{n-2},\dots,X_{0}=k_{0}) = P(X_n = j | X_{n-1}=i)$$

  • 一步转移概率:从状态 $i$ 经过 1 次到状态 $j$ 的概率,记为 $p_{ij}$
  • n 步转移概率:从状态 $i$ 经过 n 次到状态 $j$ 的概率,记为 $p_{ij}^n$
  • 一步转移矩阵:第 $i$ 行第 $j$ 列表示从状态 $i$ 经过一次到状态 $j$ 的概率,记

$$
\begin {equation} % 开始数学环境
P =
\left(
\begin{array}{ccc}
p_{11} & p_{12} &\dots\\
p_{21} & p_{22} & \dots\\
\vdots & \vdots & \ddots\\
\end{array}
\right)
\end{equation}
$$

  • n 步转移矩阵:第 $i$ 行第 $j$ 列表示从状态 $i$ 经过 n 次到状态 $j$ 的概率,记

$$
\begin {equation} % 开始数学环境
P^{\left(n\right)} =
\left(
\begin{array}{ccc}
p_{11}^n & p_{12}^n &\dots\\
p_{21}^n & p_{22}^n & \dots\\
\vdots & \vdots & \ddots\\
\end{array}
\right)
\end{equation}
$$

  • 一步首达概率:从状态 $i$ 经过 1 次到状态 $j$ 的概率,且中间不能经过状态 $j$(即为首次到达) ,记为 $f_{ij}$
  • n 步首达概率:从状态 $i$ 经过 n 次到状态 $j$ 的概率,且中间不能经过状态 $j$ ,记为 $f_{ij}^\left (n\right)$
  • 状态 $i$ 可达 $j$: $p_{ij}^n > 0 (\exists n>0)$ ,记为 $i\rightarrow j$
  • 状态 $i$ 与 $j$ 互通:$i\rightarrow j,j\rightarrow i$ ,记为 $i\leftrightarrow j$
  • 类:互通的状态称为同一类,所有状态为一类则称为马可夫链为不可约的
  • 状态的周期:称状态 $i$ 的周期为经过 n 步回到状态 $i$ 的所有的 n 的最大公约数,如果周期为 1 称为非周期的,周期大于 1 称为周期的,不存在这样的 n 称为周期无穷大
  • 状态的常返:$f_{ii} = \sum_{n=1}^{\infty} f_{ii}^\left (n\right)$(即为回到自身概率)
  • 状态为正常返:$f_{ii} = 1$
  • 状态为非常返:$f_{ii} < 1$
  • 状态的平均回转步数(时间):$u_{i} = \sum_{n=1}^{\infty} n f_{ii}^\left (n\right)$
  • 状态为遍历:非周期的正常返
  • 状态为吸收:$f_{ii}^\left (1\right) = 1$ 的遍历状态
  • 马可夫链为遍历的:不可约的马可夫链,全部状态均为遍历的

一些性质

n 步转移概率的计算(C-K 方程)

$$p_{ij}^n = \sum_{k\in S}p_{ik}^l p_{kj}^\left(n-l\right)$$

n 步转移矩阵的计算

$$
\begin {equation*} % 开始数学环境
P^\left(n\right) =
\left(
\begin{array}{ccc}
p_{11}^n & p_{12}^n &\dots\\
p_{21}^n & p_{22}^n & \dots\\
\vdots & \vdots & \ddots\\
\end{array}
\right)
\end{equation*} = P * P * \dots * P = P^{n}
$$

周期是类性质

类性质指同一类具有相同的属性,这里同一类具有相同的周期。_不同的类周期不一定不同_。

常返是类性质

相同的类具有相同的正常返零常返非常返

$i$ 可达 $j$ 且 $i$ 为常返,则 $f_{ij}=1$

直观上说明了常返的 “一定回来” 的性质

周期无穷必然自身为一类

周期无穷即不存在 n 能回到其自身状态,那不可能存在状态与其互通,即自身一类。

状态有限的马可夫链不具有零常返状态,不可能全为非常返状态

如果不可约的有限的马可夫链即可得出全部状态均为正常返状态。

极限定理

状态 $i$ 转移概率的极限:
$$ \lim_{n \to +\infty} p_{ii}^n$$

  • 状态为正常返且周期为 1(即遍历),极限为 $\frac {1}{u_{i}}$
  • 正常返且周期大于 1,极限不存在
  • 非常返和零常返极限趋于 0

状态 $i$ 到状态 $j$ 转移概率的极限:
$$ \lim_{n \to +\infty} p_{ij}^n$$

  • $j$ 为非常返或零常返,任意的 $i$,极限为 0
  • $i$ 和 $j$ 均为遍历状态,极限为 $\frac {1}{u_{j}}$

马可夫链为遍历的具有平稳分布


$$ \pi = \left(\pi_1,\pi_2,\pi_3,\dots,\pi_n\right)$$
经过一部转移后为
$$ \left(\pi_1’,\pi_2’,\pi_3’,\dots,\pi_n’\right) = \pi * P$$
如果
$$\left(\pi_1’,\pi_2’,\pi_3’,\dots,\pi_n’\right) = \pi$$
则 $\pi$ 为平稳分布。

通常马可夫链不一定具有平稳分布,马可夫链为遍历的具有平稳分布。

通过线性方程组求解和 $\sum_{i=1}^{n} \pi_i = 1$ 可得平稳分布。

马可夫链为遍历的平均回转时间为平稳分布的倒数

$$ u_j = \frac{1}{\pi_j}$$