马尔科夫链

发布于 2023-06-28  448 次阅读


Please refresh the page if equations are not rendered correctly.
---------------------------------------------------------------

一、基本概念

1、随机过程(stochastic process)

考虑一个随机变量的序列X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix},t=0,1,2,\ldots
这里X_{t}表示时刻t的随机变量,每个随机变量X_{t}的取值集合相同,称为状态空间,表示为S。随机变量可以是离散的,也可以是连续的。以上随机变量的序列构成随机过程

(1)状态空间:所有随机变量都定义在相同的概率空间上,设X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix},t=0,1,2,\ldots如果每个X_{t}都在S中取值,则称S为状态空间,称S中的元素为状态;

(2)状态:当S中只有有限个或可列个状态时,可以将S中的状态进行编号,得到由整数构成的集合II{X_{t}}的状态空间,用 i,j,k,i_{0},i_{1},\ldots来表示I中的状态 。

2、马尔科夫链(Markov chain)

马尔科夫链定义本身比较简单,它假设某一时刻状态转移的概率只依赖于它的前一个状态。

假设在时刻X_{0}的随机变量遵循概率分布P(X_{0})=\pi_{0},称为初始状态分布。在某个时刻t\geq1的随机变量X_{t}与前一个时刻的随机变量X_{t-1}之间有条件分布P(X_{t}|X_{t-1}),如果X_{t}只依赖于X_{t-1},而不依赖于过去的随机变量\begin{Bmatrix}X_0,X_1,\ldots,X_{t-1},\ldots\end{Bmatrix},这一性质称为马尔可夫性,即:

P(X_t|X_{t-1},X_{t-2},\ldots,X_0)=P(X_t|X_{t-1}),t=1,2,\ldots

具有马尔可夫性的随机序列X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix}称为马尔可夫链,或马尔可夫过程(Markov process)。条件概率分布P(X_{t}|X_{t-1})称为马尔科夫链的转移概率分布。转移概率分布决定了马尔科夫链的特性。

加入状态也就是下式:

P(X_{t+1}=j|X_{t}=i,X_{t-1}=i_{t-1},\ldots,X_{0}=i_{0})=P(X_{t+1}=j|X_{t}=i)

就是说X_{t}时的状态,只与X_{t-1}有关,而与之前的状态没有关系。

若转移概率分布P(X_{t}|X_{t-1})t无关,即

P(X_{t+1}=j|X_t=i)=P(X_1=j|X_0=i),i,j\in I

也就是与具体在某个时刻是没有关系的,只和间隔的转移次数有关,那么就称该马尔科夫链为为时间齐次的马尔科夫链。

二、离散状态马尔科夫链(Discrete-time Markov chains)

1、转移概率矩阵(matrix of transition probability)

离散状态马尔科夫链X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix},随机变量X_{t}(t=0,1,2,\ldots)定义在离散空间S,转移概率分布可以由矩阵表示。

转移概率可记作

P_{ij}= P(X_{t+1}=j|X_{t}=i)

满足

P_{i,j}\geq0,\sum_{i}P_{i,j}=1

马尔科夫链的转移概率可以由矩阵表示,即

P=\left[\begin{matrix}P_{11}&P_{12}&P_{13}&\cdots\\\ P_{21}&P_{32}&P_{23}&\cdots\\\ P_{31}&P_{32}&P_{33}&\cdots\\\ \cdots&\cdots&\cdots&\cdots\end{matrix}\right]

成为马尔科夫的概率转移矩阵,矩阵列元素之和为1。

2、柯尔莫哥洛夫—切普曼方程(K—C方程)

对于任意的m,n≥,有:

P_{i j}^{(m+n)}=\sum_{k\in I}P_{i k}^{n}P_{k j}^{m}

也就是

P^{(n+m)}=P^{n+m}

其内涵是n+m步转移矩阵就等于一步转移矩阵的n+m次方。

所以,

P^{(m)}=P\times P\times\cdots\times P=P^{m}

3、状态分布(state distribution)

转移概率(transition probability)

P(X_{t+1}=j|X_{t}=i)=P_{i j}(t)

表示t时刻由状态i到状态j的过程。

静止概率(rest probability)

\pi_{i}(t)=P(X_{t}=i)

表示t时刻是状态i的概率。

马尔科夫过程(Markov process)

\pi(t)=A\pi(t-1),A=P^T

P(t)=A P(t-1)

马尔科夫链在t时刻的概率分布称为t时刻的状态分布:

\pi(t)=\begin{bmatrix}
\pi_1(t)\\\ \pi_2(t)\\\ \pi_3(t)\\\ \cdots\end{bmatrix}

特别地,马尔可夫链的初始状态分布可以表示为:

\pi(0)=\begin{bmatrix}
\pi_1(0)\\\ \pi_2(0)\\\ \pi_3(0)\\\ \cdots\end{bmatrix}

通常初始分布\pi(0)向量只有一个分量是1,其余分量都是0(因为一个时刻只能有一种状态),表示马尔可夫链从一个具体状态开始。

马尔科夫链在时刻t的状态分布,可以由在时刻t-1的状态分布以及转移概率矩阵决定

\pi(t)=P\pi(t-1)

因为

\begin{matrix}\pi_{i}(t)=P(X_{t}=i)\\ = \ \sum_{m}P(X_{t}=i|X_{t-1}=m)P(X_{t-1}=m) \\
=\sum_{m}P_{i m}\pi_{m}(t-1)\end{matrix}

4、平稳分布(stationary distribution)

\lim_{n\rightarrow\infty}\pi_{n}=\pi

使得

\pi=P\pi

则称π为马尔科夫链X={X_{0},X_{1},\ldots,X_{t},\ldots},的平稳分布。

\pi=P\pi=\ldots=P^{(n)}\pi=P^{n}\pi

马尔科夫链模型的状态转移矩阵收敛到的稳定概率分布(平稳分布π)与我们的初始状态概率分布无关。也就是说,如果我们得到了这个稳定概率分布对应的马尔科夫链模型的状态转移矩阵,则我们可以用任意的概率分布样本开始,带入马尔科夫链模型的状态转移矩阵,这样经过一些序列的转换,最终就可以得到符合对应稳定概率分布的样本。

平稳分布时,πA特征值为1的特征向量。

A多次迭代作用即重复

P(t)=A P(t-1)

得到的分布向量逐渐地接近与A的最大特征值相关的A的特征向量。(任何初始向量分布都可以写成A的特征向量的线性组合。设A的特征向量和相应的特征值分别为\boldsymbol{x}_1,\ldots,\boldsymbol{x}_n\lambda_1,\ldots,\lambda_n,显然有

P(k)=A^{k}P(0)=\sum_{i=1}^{t}c_{i}\lambda_{i}^{k}x_{i}

A乘以初始向量,线性组合中第K个特征向量的系数乘以相应的特征值,如果重复t次,则每个系数相乘的因子为\lambda_{i}^{k}。如果t较大,则特征值最大的项占主导地位)。

由于A的每一列和都为1,所以考虑用A-E,显然有:

|A-E|=0

A-E相当于A的每一列和都减去1,因此A-E的每一列和都为0。

首先将A做特征值分解。\Lambda为对角矩阵,对角线上元素为A的特征值,X为对应特征值的特征向量矩阵。

A=X\Lambda X^{-1}

\begin{aligned}
|A-E|& =|X\Lambda X^{-1}-E| \\
&=|X\Lambda X^{-1}-XEX^{-1}| \\
&=|X(\Lambda-E)X^{-1}| \\
&=\prod\limits_{i=1}^{n}(\lambda_i-1)
\end{aligned}

于是有

\prod_{i=1}^n\left(\lambda_i-1\right)=0

所以一定存在特征值为1的情况。且A的列和为1,所以

|\lambda_{i}| \leq1

即A的最大特征值为1。

5、马尔科夫链的收敛性质

如果一个非周期的马尔科夫有状态转移矩阵P,并且他的任何两个状态是连通的(不可约),那么\lim\limits_{n\to\infty}P^n_{ij}i无关,有:

\text{1.}\lim\limits_{n\to\infty}P^n_{ij}=\pi(j)

2.\underset{n\to\infty}{\text{lim}}P^n=\begin{bmatrix}\pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \ \vdots&\vdots&\vdots&\ddots&\vdots\\\ \ \pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \ \vdots&\vdots&\vdots&\ddots&\vdots\ \end{bmatrix}.

3.\pi(j)=\sum_{i=0}^\infty\pi(i)P_{ij}

4.π是方程\pi=P\pi唯一非负解,其中,

\pi=[\pi(1),\pi(2),\cdots,\pi(j),\cdots],\sum_{i=1}^{\infty}\pi(i)=1

π是马氏链的平稳分布。

三、基于马尔科夫链采样

如果我们得到了某个平稳分布所对应的马尔科夫链状态转移矩阵,我们就很容易采用出这个平稳分布的样本集。

假设我们任意初始的概率分布是\pi_{0}\left(x\right),经过第一轮马尔科夫链状态转移后的概率分布是\pi_{1}\left(x\right),...,第 i轮的概率分布是\pi_{i}\left(x\right)。假设经过t轮后马尔科夫链收敛到我们的平稳分布 π(x) ,即

\pi_t(x)=\pi_{t+1}(x)=\pi_{t+2}(x)=...=\pi(x)

对于每个分布,都有

\pi_{i}(x)=\pi_{i-1}(x)P=\pi_{i-2}(x)P^{2}=\ldots=\pi_{0}(x)P^{i}

现在可以开始采样,首先,基于初始任意简单概率分布比如高斯分布 \pi_{0}\left(x\right)采样得到状态值x_{0},基于条件概率分布P(X|X_{0})采样状态值 x_{1} ,一直进行下去,当状态转移进行到一定的次数时,比如到t次时,我们认为此时的采样集 即是符合我们的平稳分布的对应样本集,可以用来做蒙特卡罗模拟求和。

Everything not saved will be lost.
最后更新于 2023-06-30