马尔可夫链的基本概念

【马尔可夫性】

设 $\{X(t),t\in T\}$ 是一随机过程，当 $\{X(t),t\in T\}$ 在 $t_0$ 时刻所处的状态已知时，若其在 $t>t_0$ 时刻所处状态的条件分布与其在 $t_0$ 之前所处的状态无关，则称 $\{X(t),t\in T\}$ 具有马尔可夫性

简单来说，马尔可夫性是指：在已知过程现在条件下，其将来的条件分布只依赖于现在，不依赖于过去

【马尔可夫链】

设 $\{X(t),t\in T\}$ 是一随机过程，若该随机过程具有马尔可夫性，则称该随机过程为马尔可夫过程（Markov Process）或马尔可夫链（Markov Chain），其形式化定义如下：

设 $\{X(t),t\in T\}$ 的状态空间为 $S$，若对 $\forall n\geq 2,\forall t_1<t_2<\cdots<t_n\in T$，在条件 $X(t_i)=x_i,x_i\in S,i=1,2,\cdots,n-1$ 下，$X(t_n)$ 的条件概率分布恰好等于在条件 $X(t_{n-1})=x_{n-1}$ 下的条件概率分布，即

$$\begin{align*} &P(X(t_n)\leq x_n|X(t_1)=x_1,,\cdots,X(t_{n-1})=x_{n-1})\\ =&P(X(t_n)\leq x_n|X(t_{n-1})=x_{n-1}),\quad x_n\in \mathbb{R} \end{align*}$$

则称 $\{X(t),t\in T\}$ 为马尔可夫链

【离散时间马尔可夫链】

对于马尔可夫链 $\{X(t),t\in T\}$，当参数集 $T$ 为离散参数集时，称 $\{X(t),t\in T\}$ 为离散时间马尔可夫链（Discrete-Time Markov Chain，DTMC）

离散状态

当 $X(t)$ 的状态空间 $S$ 为离散状态空间时，此时马尔可夫性可表示为：

对 $\forall n\geq 2,\forall t_1<t_2<\cdots<t_n\in T,i_1,i_2,\cdots,i_n\in S$，有

$$\begin{align*} &P(X(t_n)= i_n|X(t_1)=i_1,X(t_2)=i_2,\cdots,X(t_{n-1})=i_{n-1})\\ =&P(X(t_n)= i_n|X(t_{n-1})=i_{n-1}) \end{align*}$$

特别地，当取 $T=\{0,1,2,\cdots\}$ 时，马尔可夫链常记为 $\{X(n),n\geq 0\}$，称为系统，此时马尔可夫性可表示为：

对 $\forall n\geq 1,i_0,i_1,i_2,\cdots,i_n\in S$，有

$$\begin{align*} &P(X(n)= i_n|X(0)=i_1,X(1)=i_1,\cdots,X(n-1)=i_{n-1})\\ =&P(X(n)= i_n|X(n-1)=i_{n-1}) \end{align*}$$

其中，$X(i)$ 可简写为 $X_i$

连续状态

当 $X(t)$ 的状态空间 $S$ 为连续状态空间时，此时马尔可夫性可表示为：

对 $\forall n\geq 2,\forall t_1<t_2<\cdots<t_n\in T$，有

$$P(X(t_n)|X(t_1),X(t_2),\cdots,X(t_{n-1})) =P(X(t_n)|X(t_{n-1}))$$

【连续时间马尔可夫链】

对于马尔可夫链 $\{X(t),t\in T\}$，当参数集 $T$ 为连续参数集时，称 $\{X(t),t\in T\}$ 为连续时间马尔可夫链（Continuous-Time Markov Chain，DTMC）

离散状态

当 $X(t)$ 的状态空间 $S$ 为离散状态空间时，此时马尔可夫性可表示为：

对 $s,t,u\in T,0\leq u\leq s,i,j\in S$，有：

$$P(X(s+t)= j|X(s)=i,X(u))=P(X(s+t)= j|X(t)=i)$$

连续状态

当 $X(t)$ 的状态空间 $S$ 为连续状态空间时，此时马尔可夫性可表示为：

对 $s,t,u\in T,0\leq u\leq s$，有：

$$P(X(s+t)|X(s),X(u))=P(X(s+t)|X(t))$$