强化学习笔记：马尔科夫链介绍及基于Python的蒙特卡洛仿真_马尔科夫链 不可约和遍历

目录

0. 前言

0.1 马尔可夫性

0.2 马尔科夫链

0.3 马尔科夫链有什么用？

1. 离散时间马尔科夫链(DTMC)

2. 马尔科夫链建模

2.1 转移概率矩阵

2.2 有向图表示

2.3 一个实例

2.4 矩阵运算例

3. 马尔科夫链蒙特卡洛仿真

3.1 Python modelling

3.2 The first trial

3.3 蒙特卡洛仿真

---

0. 前言

0.1 马尔可夫性

        简而言之，所谓马尔可夫性(Markov Property)是指系统的下一个状态仅与当前状态有关，而与以前的状态无关。

        马尔可夫性的一个更通俗的说法是无记忆性(memorylessness)，即系统不记得当前状态以前的状态，仅仅基于当前状态来决定下一个时刻转移到什么状态。

0.2 马尔科夫链

        马尔可夫链（Markov Chain, MC）是具有马尔可夫性（Markov property）的随机过程（stochastic process）,又称马尔可夫(随机)过程。

        如果指标集(index set)是连续的，则称为连续时间马尔可夫链（Continuous-Time MC, CTMC）；如果指标集是离散的，则称为离散时间马尔可夫链（Discrete-Time MC, DTMC）。注意，这里‘时间’应该以广义的方式理解。时间是指标(index)的一种，但是的确是最常用的一种。因此，人们通常以时间作为广义的index的代名词。

        通常情况下，我们碰到的都是DTMC，并且常常就简称为马尔科夫链。所以，当没有特别指明的情况，说起马尔科夫链的话通常就是指DTMC。

        马尔可夫链可通过转移矩阵和转移图定义，除马尔可夫性外，马尔可夫链可能具有不可约性、常返性、周期性和遍历性。一个不可约和正常返的马尔可夫链是严格平稳的马尔可夫链，拥有唯一的平稳分布。遍历马尔可夫链（ergodic MC）的极限分布收敛于其平稳分布。

0.3 马尔科夫链有什么用？

马尔可夫链可被应用于蒙特卡罗方法中，形成马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC），也被用于经济学、博弈论、通信理论、金融、动力系统、化学反应、排队论、市场行为和信息检索的数学建模。此外作为结构最简单的马尔可夫模型（Markov model），一些机器学习算法，例如隐马尔可夫模型（Hidden Markov Model, HMM）、马尔可夫随机场（Markov Random Field, MRF）和马尔可夫决策过程（Markov decision process, MDP）以马尔可夫链为理论基础。

Markov Chains have prolific usage in mathematics. They are widely employed in economics, game theory, communication theory, genetics and finance. They arise broadly in statistical specially Bayesian statistics and information-theoretical contexts. When it comes real-world problems, they are used to postulate solutions to study cruise control systems in motor vehicles, queues or lines of customers arriving at an airport, exchange rates of currencies, etc. The algorithm known as PageRank, which was originally proposed for the internet search engine Google, is based on a Markov process. Reddit's Subreddit Simulator is a fully-automated subreddit that generates random submissions and comments using markov chains, so cool!

        马尔可夫链的命名来自俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков）以纪念其首次提出马尔可夫链和对其收敛性质所做的研究[2]。

 

1. 离散时间马尔科夫链(DTMC)

如前所述，DTMC是指其指标为离散时间，称为time step（时间步，时刻），系统状态在每个time step随机变化。每个time step的状态相当于一个随机变量。因此DTMC可以看作是一个离散随机变量序列。当然，把time step换成任意其它的离散指标，比如说距离啊什么，也完全可以。总之，把离散时间广义地理解为离散指标就没有错。

记时刻t的状态随机变量为