马尔可夫链：状态，转移概率，不可约的，非周期性的，稳态分布，击中时间 强大数定律 大数定律：不可约意味着有唯一的稳态分布，这个分布等于长期时间比例；如果既不可约又是非周期性的，则收敛于稳态分布 击中时间：首步方程 重要方程与公式 马尔可夫链的定义 式（1.3） 马尔可夫链X(n)的概率方程 式（1.5） 平衡方程 式（1.1） 首步方程 式（1.9） 1.6 参考资料 关于马尔可夫链有非常多优秀的书籍，我最喜欢的是Grimmett和Stirzaker的Probability and Random Processes，以及Bertsekas和Tsitsiklis的Introduction to Probability．最初介绍PageRank的专利文献是“Method for node ranking in a linked database”．Easley和Kleinberg的电子书Networks，Crowds，and Markets: Reasoning About a Highly Connected World对社交网络的探讨很有启发性．该书的第14章讨论了PageRank． 1.7 练习 1. 构造一个不可约的马尔可夫链，要求其分布收敛于唯一的稳态分布． 2. 给出一个马尔可夫链，要求其分布的极限收敛且依赖于初始分布． 3. 你能找到一个分布不收敛、不可约、非周期性的有限马尔可夫链吗？ 4. 给出一个有限、不可约、非周期性的马尔可夫链，要求它以很慢的速度收敛于稳态分布． 5. 证明：如果X(n)是一个马尔可夫链，则函数Y(n) = g(X(n)) 有可能不是一个马尔可夫链． 6. 如果一个马尔可夫链是独立同分布的随机变量序列，它是否是不可约的和非周期性的？ 7. 考虑马尔可夫链X(n)，其状态如图1-8所示，其中a, b∈(0,1)． 图1-8 第7题的马尔可夫链 (a) 证明这个马尔可夫链是非周期性的． (b) 计算P[X(1) = 1, X(2) = 0, X(3) = 0, X(4) = 1|X(0) = 0]． (c) 计算其稳态分布． (d) 令Ti = min{n≥0|X(n) = i}，计算E[T2|X(0) = 1]． 8. 用Matlab写一个K状态马尔可夫链{X(n), n≥1}的模拟程序．假设其初始分布为π，转移概率矩阵为P．这个程序需要完成以下任务： (a) 绘制{X(n), n = 1, …, N}; (b) 绘制X(n)在某些指定状态上所花的时间比例，并将其表示为m的函数（m = 1, …, N）； (c) 绘制X(n)等于某些确定状态的概率，其中n = 1, …, N； (d) 用这个程序模拟一个5状态的周期性马尔可夫链； (e) 用这个程序模拟一个5状态的非周期性马尔可夫链． 9. 用你在问题8中写的程序模拟图1-1和图1-5的马尔可夫链． 10. 计算图1-5所示的马尔可夫链的稳态分布． 11. 计算图1-5所示的马尔可夫链的d(1)、d(2)和d(3)（定义在式（1.6）中）． 12. 计算图1-1所示的马尔可夫链的d(A)（定义在式（1.6）中）． 13. 设{Xn, n≥0}为一个有限状态马尔可夫链．假设它有唯一的稳态分布π且πn对于任意初始分布π0都收敛于π．请问以下哪些选项是正确的？ Xn是不可约的． Xn是周期性的． Xn是非周期性的． Xn可能不是不可约的． 14. 考虑在{0, 1}上的马尔可夫链{Xn, n≥0}．设P(0, 1) = 0.1，P(1, 0) = 0. 3，以下哪些选项是正确的？ 该马尔可夫链的样本空间是{0,1}． 该马尔可夫链的稳态分布为[0.75, 0.25]． 令T1 = min{n≥0|Xn = 1}，那么E[T1|X0 = 0] = 1.2． E[X1+X2|X0 = 0] = 0.8． 15. 考虑一个马尔可夫链，其状态转移如图1-9所示． 图1-9 第15题的马尔可夫链 (a) 该马尔可夫链的周期是多少？解释原因． (b) 找出该马尔可夫链的所有稳态分布． (c) Xn 的分布πn在n→∞时是否收敛？解释原因． (d) 马尔可夫链花在不同状态中的时间比例是否收敛？如果收敛，其极限是多少？ 16. 考虑图1-10所示的马尔可夫链． 图1-10 第16题的马尔可夫链 (a) 找出该马尔可夫链的所有稳态分布． (b) 假设π0(3) = 1，求limn→∞πn． 17. 考虑图1-11所示的马尔可夫链． 图1-11 第17题的马尔可夫链 (a) 找出该马尔可夫链的所有稳态分布． (b) 当n→∞时，πn是否收敛？如果收敛，加以证明． (c) 马尔可夫链花在所有状态中的时间比例是否收敛？并证明之． 18. 考虑一个马尔可夫链，其状态转移如图1-12所示． 图1-12 第18题的马尔可夫链 (a) 找出该马尔可夫链的稳态分布π． (b) 计算从状态0到2的所需时间期望值． (c) 用Matlab绘制从0开始经过n步后，马尔可夫链还未到达2的概率． (d) 用Matlab对该马尔可夫链进行模拟并绘制在n步后花费在不同状态上的时间比例． (e) 用Matlab绘制πn． 19. 考虑图1-13所示的马尔可夫链{Xn, n≥0}，假设X0 = 0．求Xn在到达2之前两次到达1的概率． 图1-13 第19题的马尔可夫链 20. 画一个6状态、不可约、非周期性的马尔可夫链，并且设置转移概率．在Matlab中模拟该马尔可夫链．画出该链在所有6个状态的时间比例．假设从状态1开始，画出它在每个状态的概率． 21. 重复第20题，将条件改为模拟一个周期性的马尔可夫链． 22. 如何使网页排序算法给你的主页一个较高等级？ 提示：尝试添加另一个网页并加入一些链接． 23. 证明状态的保持时间是几何分布的． 24. 抛掷一枚骰子，平均来说，要抛掷多少次才能得到最后两次点数和为10？ 25. 抛掷一枚骰子，平均来说，要抛掷多少次才能得到最后三次的点数和至少为15？ 26. 一个二重随机矩阵是非负矩阵，行、列和均为1．证明这样一个转移矩阵的稳态分布是均匀的． 27. 假设图1-5中的马尔可夫链(c)从状态1开始．计算它在被状态3吸收前，访问状态1的平均次数． 28. 一个人尝试爬上有N级的梯子．他在爬每一步的时候，都有概率p掉回地面，否则爬上一级．用首步方程的方法从理论上分析他到达顶部所需的平均时间，计算N = 1, …, 20和p = 0.05, 0.1, 0.2的情况．利用Matlab绘制相应的图像． 29. 设{Xn, n≥0}为一个有限状态、不可约的马尔可夫链，其概率转移矩阵为P．证明当 时， 的概率为1． 30. 证明马尔可夫链{Xn, n≥0}可以写作Xn+1 = f(Xn,Vn)，n≥0．这里的Vn是独立于X0的独立同分布的随机变量． 31.设 和 是随机矩阵，π是有限集X上的概率分布．假设 , 证明π是P的稳态分布． 32. 设Xn是有限集X上的马尔可夫链．假设该马尔可夫链的转移图为一棵树，如图1-14所示．证明如果π是稳态的，P是转移矩阵，则它满足如下细致平衡方程： . 图1-14 树状的转移图 33. 设{Xn, n≥0}是一个在{1,1}上的马尔可夫链．假设P(1,1) = P(1,1)=a，其中a是给定的且a∈(0,1)．定义Yn = X0+…+Xn，n≥0． (a) {Yn, n≥0}是马尔可夫链吗？证明之． (b) 如何计算 ，其中 或 34. 假设无限次地抛掷一枚均匀的硬币．证明正面出现次数总是比背面出现次数大的概率为0．