离散时间马尔可夫链 (Markov Chain)

一般来讲，为了化简一些过程，需要对对象进行一些假设，使其简单（无记忆性）、被大量随机过程满足、应用广泛。一个较好的假设，是现在的结果只依赖于最近一次的结果。

定义：

设具有可数样本空间E的随机序列 ${X_m}_{m=0}^\infty$ 满足：

$\forall k, \forall m_1<\cdots <m_{k+1},$

$\mathbb{P}(X_{m_{k+1}}=n_{k+1}|X_{m_{k+1}}=n_{k+1},\cdots ,X_{m_1}=n_1)=\mathbb{P}(X_{m_{k+1}}=n_{k+1}|X_{m_{k+1}}=n_{k+1})$;

则称 ${X_m}_{m=0}^\infty$ 为离散时间Markov链。化简条件后：

$\forall k,\ \ \mathbb{P}(X_{m_{k+1}}=n_{k+1}|X_{m_{k+1}}=n_{k+1},\cdots ,X_{m_1}=n_1)=\mathbb{P}(X_{m_{k+1}}=n_{k+1}|X_{m_{k+1}}=n_{k+1})$

另一种描述方式：

知道过去A，知道现在B，对未来C进行推断，只有现在才起作用。

$\mathbb{P}(C|BA)=\mathbb{P}(C|B)\Longleftrightarrow \mathbb{P}(CA|B)=\mathbb{P}(C|B)\mathbb{P}(A|B)$

直观来说，已知现在的条件下，过去和未来是独立的，也就是过去的信息对未来的预测不起作用。

将过去和未来模糊（复杂化），不会改变马尔可夫性。但是如果现在复杂化，有可能破坏马尔可夫性。也就是

$\mathbb{P}(X_{n+1}\in B|X_n=i,(X_{n-1},\cdots,X_0)\in A)=\mathbb{P}(X_{n+1}\in B|X_n=i);$

$\mathbb{P}(X_{n+1}=j|X_n\in B,X_{n-1}=i_{n-1},\cdots,X_0=i_0)\neq\mathbb{P}(X_{n+1}=j|X_n\in B)$.

老师说，人要对马尔可夫性有一种追求。过去和未来有对称性，过去没意思，未来也猜不透，就抓住现在。现在是基础，是条件，是约束，现在的重要性优先级高于过去和未来。

一步转移概率

考虑离散时间Markov链的n维联合概率（分布）：

$\mathbb{P}(X_1=i_1,X_2=i_2,\cdots ,X_n=i_n)$

$=\mathbb{P}(X_n=i_n|X_{n-1}=i_{n-1})\cdots \mathbb{P}(X_2=i_2|X_1=i_1)\mathbb{P}(X_1=i_1)$

从而可知，Markov链的任意维联合分布都决定于条件概率:

推广 $\mathbb{P_{ij}}(k,k+1)=\mathbb{P}(X_{k+1}=j|X_k=i)$ 称为一步转移概率。

n步转移概率： $\mathbb{P_{ij}}(k,k+n)=\mathbb{P}(X_{k+n}=j|X_k=i)$ 。