WARNING: This article may be obsoleteThis post was published in 2021-12-21. Obviously, expired content is less useful to users if it has already pasted its expiration date.
This article is categorized as "Garbage" . It should NEVER be appeared in your search engine's results.Table of Contents
2022-07-22补充
学习N-gram的时候复习了这篇笔记。需要强调的是，[mathjax]k^{th}{\text -}\text{order Markov chain}[/mathjax]并不是一个标准的markov chain/markov process . 本笔记中截图的定义（来自浙大概率论）确实是和wikipedia一致的。
主要参考资料
浙大概率论第四版
马尔可夫过程
注：Markov process = Markov chain，同一个概念。
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.
https://en.wikipedia.org/wiki/Markov_chain
✪
找工作的简历里还会写上小学获得的三好学生奖状吗？当然不会。但小升初的时候这玩意应该有点作用。
或者我想测试一个新出的聊天机器人好不好用。我连续问了他2个一模一样的问题，果然它发现了，并反问我“你怎么还问这个问题？”。如果我在2个相同问题之间夹了另一个问题，它就发现不了我的小伎俩。于是我可以认为这个聊天机器人也就是个普通的齐次马尔可夫，没法成为更强大的聊天机器人。（这里可以假设更强的聊天机器人可能会使用n-gram, n很大，见：🔗 [2022-07-22 - Truxton's blog] https://truxton2blog.com/2022-07-22/#N-gram模型与k-order_Markov_model）
✪ 马尔可夫过程 前言
✪ 马尔可夫过程 定义
* 这是标准的马尔可夫过程定义。至于各种变体，那是之后才会讨论的问题。各种变体： 🔗 [Markov chain - Wikipedia] https://en.wikipedia.org/wiki/Markov_chain
✪
长时间不看这张图的话可能会产生疑惑，这是因为上图的公式倒过来写了，正着写可能就容易懂了：
[mathjax-d]\begin{aligned} &P\left\{X_{m+n}=a_{j} \mid X_{t_{1}}=a_{i_{1}}, X_{t_{2}}=a_{i_{2}}, \cdots, X_{t_{r}}=a_{i_{r}}, X_{m}=a_{i}\right\} \\ &=P\left\{X_{m+n}=a_{j} \mid X_{m}=a_{i}\right\} \end{aligned}[/mathjax-d]✪ 齐次/平稳 马尔可夫链
✪
马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。
✪ 回顾高斯过程
🔗 [概率论2-随机过程 | Buracag的博客] https://buracagyang.github.io/2019/06/14/probability-theory-2/
✪ 随机游走/随机漫步/random walk
🔗 [随机游走 - 维基百科，自由的百科全书] https://zh.wikipedia.org/zh-hans/隨機漫步
有的时候我们只会接触到简单形式的random walk，称为： 简单对称的随机游走 .
有关马尔可夫和random walk的另一个话题，见：preview 🔗 [2022-07-20 - Truxton's blog] https://truxton2blog.com/2022-07-20/#马尔可夫，随机游走，50获胜的赌博
✪ （一步）转移概率矩阵
✪ 例题
注意：这道题有后续例题
✪ 例题2 （例5，从第一页的末尾开始）
会使用到的公式：（见🔗 [Chapman–Kolmogorov equation - Wikipedia] https://en.wikipedia.org/wiki/Chapman–Kolmogorov_equation）
[mathjax-d]p_{i_{1}, \ldots, i_{n}}\left(f_{1}, \ldots, f_{n}\right)=p_{i_{1}}\left(f_{1}\right) p_{i_{2} ; i_{1}}\left(f_{2} \mid f_{1}\right) \cdots p_{i_{n} ; i_{n-1}}\left(f_{n} \mid f_{n-1}\right)[/mathjax-d]多步马尔可夫的转移概率
✪ 解释[mathjax]P_{i j}(n)[/mathjax]，齐次马氏链的n步转移概率：从状态[mathjax]i[/mathjax]开始，经历[mathjax]n[/mathjax]步到达状态[mathjax]j[/mathjax]的转移概率
✪ 马尔可夫的（其他平台，比如维基百科）表达公式：
解释[mathjax]p_{i ; j}\left(f_{i} \mid f_{j}\right)[/mathjax]，齐次马氏链的n步转移概率：从状态[mathjax]j[/mathjax]转移到状态[mathjax]j[/mathjax]的转移概率
✪ Chapman–Kolmogorov / C-K 方程
在浙大概率论中，用[mathjax]P_{i j}(n)[/mathjax]表达：[mathjax-d]P_{i j}(u+v)=\sum_{k=1}^{+\infty} P_{i k}(u) P_{k j}(v), i, j=1,2, \cdots .[/mathjax-d]
在维基百科中的表达方式：[mathjax-d]p_{i_{3} ; i_{1}}\left(f_{3} \mid f_{1}\right)=\int_{-\infty}^{\infty} p_{i_{3} ; i_{2}}\left(f_{3} \mid f_{2}\right) p_{i_{2} ; i_{1}}\left(f_{2} \mid f_{1}\right) d f_{2}[/mathjax-d]
Informally, this says that the probability of going from state 1 to state 3 can be found from the probabilities of going from 1 to an intermediate state 2 and then from 2 to 3, by adding up over all the possible intermediate states 2.
Chapman–Kolmogorov equation - Wikipedia
✪ n步转移概率矩阵 （注意[mathjax]\boldsymbol{P}[/mathjax]最好加粗）
[mathjax-d]\boldsymbol{P}(n)=\boldsymbol{P}^{n}[/mathjax-d]对齐次马氏链而言，n步转移概率矩阵是一步转移概率矩阵的n次方。
马尔可夫的遍历性
✪ 定义
✪ 定理
对这个定理的简单解释：
✪ 一道例题的后续
代码验证：
import numpy as np
def pn(a, n):
k = a
for i in range(0, n):
k = k @ a
return k
a = np.array([
[0, 1, 0, 0, 0],
[1 / 3, 1 / 3, 1 / 3, 0, 0],
[0, 1 / 3, 1 / 3, 1 / 3, 0],
[0, 0, 1 / 3, 1 / 3, 1 / 3],
[0, 0, 0, 1, 0]
])
print(pn(a, 5))
print()
print(pn(a, 10))
print()
print(pn(a, 20))
print()
print(pn(a, 100))
print()
print(pn(a, 200))
结果：
[[0.13580247 0.34567901 0.27983539 0.18106996 0.05761317]
[0.11522634 0.34430727 0.26886145 0.21124829 0.06035665]
[0.09327846 0.26886145 0.27572016 0.26886145 0.09327846]
[0.06035665 0.21124829 0.26886145 0.34430727 0.11522634]
[0.05761317 0.18106996 0.27983539 0.34567901 0.13580247]]
[[0.10045894 0.29587292 0.27240089 0.25043608 0.08083117]
[0.09862431 0.28988354 0.2729033 0.25511016 0.08347869]
[0.0908003 0.2729033 0.27259282 0.2729033 0.0908003 ]
[0.08347869 0.25511016 0.2729033 0.28988354 0.09862431]
[0.08083117 0.25043608 0.27240089 0.29587292 0.10045894]]
[[0.09160774 0.27433829 0.27272659 0.27111804 0.09020934]
[0.0914461 0.2739627 0.27272764 0.27149088 0.09037268]
[0.09090886 0.27272764 0.27272699 0.27272764 0.09090886]
[0.09037268 0.27149088 0.27272764 0.2739627 0.0914461 ]
[0.09020934 0.27111804 0.27272659 0.27433829 0.09160774]]
[[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]]
[[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]
[0.09090909 0.27272727 0.27272727 0.27272727 0.09090909]]
