马尔可夫链
一. 马尔可夫链的基础知识
📌 1. 马尔可夫链的核心三要素（Core Components of a Markov Chain）
-
🧱 状态空间（States Space）
表示系统可能处于的所有状态的集合。 -
🧠 无记忆性（Memorylessness）
马尔可夫性质：
P(St∣St−1,St−2,St−3,…)=P(St∣St−1) P(S_t \mid S_{t-1}, S_{t-2}, S_{t-3}, \ldots) = P(S_t \mid S_{t-1}) P(St∣St−1,St−2,St−3,…)=P(St∣St−1)
当前状态的转移仅依赖于前一时刻的状态。 -
🔁 转移矩阵（Transition Matrix）
描述从一个状态转移到另一个状态的概率，用矩阵形式统一表示所有状态对之间的转移关系。
📌 2. 马尔可夫链的应用
- 在自然语义处理方面，我们可以利用字符词语之间的转移矩阵，去联想用户接下来想说什么想搜什么。
- 也可以利用马尔可夫链随机生成诗词、文章等。
- 大佬推荐：信息论之父Claude Shannon的通信的数学理论（A Mathematical Theory of Communication）。
📌 3. 马尔可夫链的遍历性与唯一稳态
①. 全部对象
- A
- B
- C
②. 马尔可夫链的三大条件
如果马尔可夫链的全部状态节点都满足以下三大条件，则该链符合遍历性的要求：
-
常返性（Recurrence）
状态 iii 是常返的（recurrent），表示从状态 iii 开始，最终有可能回到状态 iii，即存在返回该状态的概率为1。也就是说，无论链从哪个状态开始，总有可能回到该状态。 -
非周期性（Aperiodicity）
状态是非周期的，意味着从任何状态 iii 出发，达到该状态所需的步数不局限于某个固定的周期。换句话说，状态 iii 的到达步骤可以是任意整数步，而不仅仅是某个固定的间隔。 -
两个连通（Irreducibility）
马尔可夫链是两个连通的，意味着从任何一个状态 iii 都可以通过有限步到达任意其他状态 jjj。换句话说，所有状态之间是可达的，链的所有状态构成一个连通的图。
③. 遍历性条件的意义
当满足这三大条件时，马尔可夫链被称为遍历链，也就是说，链的每个状态最终都会被访问到，而且每个状态在长期运行时都能稳定下来，从而达到一个唯一的稳态分布。这个稳定分布的特点是，在经过足够多的步数后，状态的概率分布不再发生变化。
二. 随机抽样、蒙特卡洛模拟与逆转换方法（为后面进阶做基础知识回顾）
1. 抽样 Sampling
抽样是从总体（Population）中选取一部分样本（Sample）进行研究的过程。在许多实际应用中，直接获取整个总体的数据可能不切实际或不可能，因此我们通过抽样从中选择具有代表性的部分数据进行分析。
抽样的基本概念包括：
- 总体（Population）：指的是研究对象的全体，通常规模庞大，不易全面获取。
- 样本（Sample）：从总体中选取的一部分数据，它代表了总体的某些特征。
常见的抽样方法：
-
简单随机抽样
每个个体在总体中被选中的概率相等，常用于基于随机数生成的抽样。 -
分层抽样
将总体划分为若干层次，从每个层次中进行随机抽样。这种方法能保证从每个子群体中抽取样本，适用于数据具有明显分层结构的情况。 -
系统抽样
选择一个起始点，然后按照固定间隔选择样本点。常用于数据按某种顺序排列的情况。 -
整群抽样
将总体分为若干群体，然后随机选择群体进行研究。适用于群体之间差异较大时，能简化抽样过程。
2. 逆转换方法 Inverse Transform Sampling（均匀分布抽样转化为复杂分布抽样的方法）
① 引入PDF和CDF
PDF:
f(x)={0x<010≤x≤10x>1
f(x) = \begin{cases}
0 & x < 0 \\\\
1 & 0 \leq x \leq 1 \\\\
0 & x > 1
\end{cases}
f(x)=⎩⎨⎧010x<00≤x≤1x>1
其CDF为：
F(x)=∫0x1 dx′=x F(x) = \int_0^x 1 \, dx' = x F(x)=∫0x1dx′=x
② 转换函数
[0,1]均匀分布→u转换函数 T→T(u)指数分布 [0,1] \text{均匀分布} \quad \xrightarrow{u} \quad \text{转换函数} \, T \quad \xrightarrow{T(u)} \quad \text{指数分布} [0,1]均匀分布u转换函数TT(u)指数分布
f(x)={0,x<0e−x,x≥0 f(x) = \begin{cases} 0, & x < 0 \\\\ e^{-x}, & x \geq 0 \end{cases} f(x)=⎩⎨⎧0,e−x,x<0x≥0
CDF
F(x)=∫0xe−x′ dx′=1−e−x F(x) = \int_0^x e^{-x'} \, dx' = 1 - e^{-x} F(x)=∫0xe−x′dx′=1−e−x
P(T(a)≤x)=F(x)
P(T(a) \leq x) = F(x)
P(T(a)≤x)=F(x)
P(a≤T−1(x))=F(x) P(a \leq T^{-1}(x)) = F(x) P(a≤T−1(x))=F(x)
P(a≤T−1(x))=T−1(x)=F(x) P(a \leq T^{-1}(x)) = T^{-1}(x) = F(x) P(a≤T−1(x))=T−1(x)=F(x)
T−1(x)=F(x) T^{-1}(x) = F(x) T−1(x)=F(x)
T(x)=F−1(x) T(x) = F^{-1}(x) T(x)=F−1(x)
T(a)=F−1(a) T(a) = F^{-1}(a) T(a)=F−1(a)