我们先看几个重要的概念，这里的一些知识点和例子可以参照《Foundations of stochastic inventory theory》。
首先是随机过程,Markov过程,和Markov（马尔可夫）链。 Markov过程在工程系统中的噪 声和信号分析、通信网络的模拟、统计 物理学、生物学、数字计算方法、经济 管理和市场预测等领域中都有十分重要 的作用和广泛的应用，它在人工智能和 在人工神经网络中也有重要的应用。比如，在金融领域，马尔可夫链模型被用于预测企业产品的市场占有率。
马尔可夫链是一种相当常见的、相对简单的统计模型随机过程的方法。它们已经被应用于许多不同的领域,从文本生成到金融建模。
一：马尔可夫过程的分类
马尔可夫过程按其状态和时间可参数是连续,离散分为三类:
1. 时间，状态都是离散的马尔可夫过程，称马尔可夫链
2. 时间连续，状态离散的马尔可夫过程，称为连续的马尔可夫过程
3. 时间，状态都是连续的马尔可夫过程
二：马尔可夫链的定义
时间和状态都是离散的马尔可夫过程称为马尔可夫链。
通过上面的数学推导可见，马尔可夫链的马尔可夫性可以表示为：
P{Xn+1 =in+1 | Xn = in }
也就是说当前状态只与前一个状态有关，与其他状态无关。
下面是我找到的网上对随机过程和马尔可夫链比较有意思的解释，感兴趣的同学可以去看看微信公众号红猴子。
随机过程，顾名思义，它其实就是个过程，比如今天下雨，那么明天下不下雨呢？后天下不下雨呢？从今天下雨到明天不下雨再到后天下雨，这就是个过程。那么怎么预测N天后到底下不下雨呢？这其实是可以利用公式进行计算的，随机过程就是这样一个工具，把整个过程进行量化处理，用公式就可以推导出来N天后的天气状况，下雨的概率是多少，不下雨的概率是多少。说白了，随机过程就是一些统计模型，利用这些统计模型可以对自然界的一些事物进行预测和处理，比如天气预报，比如股票，比如市场分析，比如人工智能。它的应用还真是多了去了。
再次，我们看看什么是马尔可夫链 （Markov Chain）。
马尔可夫链是随机过程中的一种过程，到底是哪一种过程呢？
先说说我们村智商为0的王二狗，人傻不拉几的，见人就傻笑，每天中午12点的标配，仨状态：吃，玩，睡。这就是传说中的状态分布。
你想知道他n天后中午12点的状态么？是在吃，还是在玩，还是在睡？这些状态发生的概率分别都是多少？
先看个假设，他每个状态的转移都是有概率的，比如今天玩，明天睡的概率是几，今天玩，明天也玩的概率是几。
这个矩阵就是转移概率矩阵P，并且它是保持不变的，就是说第一天到第二天的转移概率矩阵跟第二天到第三天的转移概率矩阵是一样的。（这个叫时齐（time-homogeneity），时齐性是指，系统由状态 ii 到状态 jj 的转移概率只依赖于其时间间隔的长短，与起始时间无关。）。
有了这个矩阵，再加上已知的第一天的状态分布，就可以计算出第N天的状态分布了。
S1 是4月1号中午12点的的状态分布矩阵[0.6, 0.2, 0.2]，里面的数字分别代表吃的概率，玩的概率，睡的概率。
那么4月2号的状态分布矩阵 S2 = S1 * P (俩矩阵相乘)。
月3号的状态分布矩阵 S3 = S2 * P (看见没，跟S1无关，只跟S2有关)。
4月4号的状态分布矩阵 S4 = S3 * P (看见没，跟S1，S2无关，只跟S3有关)。
...
4月n号的状态分布矩阵 Sn = Sn-1 * P (看见没，只跟它前面一个状态Sn-1有关)。
总结：马尔可夫链就是这样一个任性的过程，它将来的状态分布只取决于现在，跟过去无关。
就把下面这幅图想象成是一个马尔可夫链吧。实际上就是一个随机变量随时间按照Markov性进行变化的过程。
Note: 马尔可夫过程的平衡状态与初始值无关。
一个马尔科夫实例 （参见：https://blog.csdn.net/robert_chen1988/article/details/81234790）：
1. 状态（state）
一个零售商面对的顾客有两种状态，
状态 s1： 上一个月买过该零售商的商品
状态 s2：上一个月没有买过该零售商的商品
2. 决策 (action)
零售商可以做出 3 个决策及对应的决策成本：
决策 a1 ： 什么都不做 成本：0
决策 a2 ： 发礼物，小促销 成本：0.5
决策 a3： 发礼物， 大促销 成本：0.5
3. 状态转移及转移概率 (transition equation and possibility)
Initial state action next state s1 and possibility next state s2 and possibility
S1 a1 s1 0.99 s2 0.01
S1 a2 s1 0.93 s2 0.07
S1 a3 s1 0.85 s2 0.15
S2 a1 s1 0.80 s20.20
S2 a2 s1 0.72 s2 0.28
S2 a3 s1 0.50 s2 0.50
4. 折现率 (discount factor)
折现率 \alpha=0.09
有效转移概率p=q*a
5. 即时收益（immediate value）
Initial state action action cost expected return
S1 a1 0 0.08
S1 a2 0.5 -0.01
S1 a3 0.5 -0.05
S2 a1 0 1.6
S2 a2 0.5 1.4
S2 a3 0.5 1
若顾客不购买商品，收益为 0；
不促销时，顾客购买商品，收益为 8；
小促销时，顾客购买商品，收益为 7；
大促销时，顾客购买商品，收益为 3；
减去成本，得到的期望即时回报（immediate return）
若是单周期决策，从上表可以看出，不论初始状态是什么，最有决策都是 a1a1，即不促销不发礼物。
6. 两阶段决策
若是两阶段决策，则期望回报和需要再算一层。
Initial state action action cost expected return expected immediate return
S1 a1 0 0.08 0.1736
S1 a2 0.5 -0.01 0.17
S1 a3 0.5 -0.05 0.2
S2 a1 0 1.6 1.87
S2 a2 0.5 1.4 1.85
S2 a3 0.5 1 1.75
从上表可以得出最优决策策略是：若初始状态为 s1s1，最优决策 a3a3，即大促销；若初始状态为 s2s2， 最优决策 a1a1，即不促销。
7. 最优递推方程
定义 fn(s)fn(s) 表示初始状态为 ss，之后 nn 个阶段的最优期望回报，则最优递推方程可以表示为：
f_n(s)=sup(r(s,a))+\alpha\sumP_{sj}f_{n-1}(j}
界限方程一般是：f_0(s)=v(s)
这就是一个动态规划表达式。
另外一个马尔科夫实例 （参见https://blog.csdn.net/weaponsun/article/details/50007411）
假设我们在研究一个粒子的运动。这个粒子随机地在A门与B门之间跳动。如果这个粒子跳入A门，那么它下一次跳入A门的概率为0.8。如果这个粒子跳入B门，那么它下次跳入B门的概率为0.7。我们的问题是，现在有100000个这样的粒子让它们跳跃，让它们跳跃1000次,我们会观察到多少个粒子在A门多少个在B门？
首先随机生成100000个粒子。1代表该粒子在A门，0代表在B门。
生成10000个以概率0.8为1，概率0.2为0的随机数。同时在生成10000个以概率0.7为0，概率0.3为1随机数。
用2a－AA。如果值为1说明该粒子从A门跳转到A门；如果值为2则说明该粒子从A门跳转到B门。另外值为0，－1则说明该粒子初始状态是在B门。
用2a－BB。如果值为0说明该粒子从B门跳转到B门；如果值为-1则说明该粒子从B门跳转到A门。另外值为2，1则说明该粒子初始状态是在A门。
找到A中大于等于1的元素与B中小于等于0的元素。同时新建一个向量a2用于存储结果。
将A中大于等于1的元素与B中小于等于0的元素按照对应的位置放入新的向量a中。
这时a2中1和－1代表粒子在A门；2和0代表粒子在B门。将－1换成1，2换成0。
通过while loop让粒子跳跃1000次。
得出的结果大概在60000左右。也就是说大概能观察到60000个粒子在A门，40000个在B门。
再看一个马尔科夫实例 （参见http://blog.sciencenet.cn/blog-255662-513722.html）
例子： 姜华平、陈海泳对某城市2002年居民出行方式所占比例进行了调查。结果如下
公交车bus,自行车Bicycle,步行walk,其他other
19%, 14%, 56%, 11%
本时期各出行方式转移概率如下表(%)
bus bicycle walk other
Bus 90 4 2 4
bicycle 7 86 1 6
walk 8 7 80 5
other 10 2 3 85
假设该城市居民每天出行总人数为468万人次，出行人数不变，各出行方式的转移概率也不变，
问题：
（1） 预测2006年该城市乘公交出行的人数
（2） 经历足够长的时间，求出行方式的比例是多少？
写出转移矩阵
T <- matrix(c(90, 4 , 2 , 4 ,
7 , 86, 1 , 6 ,
8 , 7 , 80, 5 ,
10, 2 , 3 , 85 )/100,
nrow = 4, ncol = 4, byrow = TRUE)
写出初始矩阵
p <- matrix(c(19, 14, 56, 11)/100, nrow = 1, ncol = 4, byrow = TRUE)
下一年的概率应该为当年分配概率和转移矩阵的乘积
2003
p1 <- p%*%T
2004
p2 <- p1%*%T
2005
p3 <- p2%*%T
2006
p4 <- p3%*%T
2006年乘坐公交车出行的总人数应为
res <- 468 * p4[1]
