当前位置:文档之家› 2010年5月苏北赛算法:马尔可夫链。适合很多题型

2010年5月苏北赛算法:马尔可夫链。适合很多题型

马尔可夫链在自然界与社会现象中,许多随机现象遵循下列演变规律,已知某个系统(或过程)在时刻0t t =所处的状态,与该系统(或过程)在时刻0t t >所处的状态与时刻0t t <所处的状态无关。

例如,微分方程的初值问题描述的物理系统属于这类随机性现象。

随机现象具有的这种特性称为无后效性(随机过程的无后效性),无后效性的直观含义:已知“现在”,“将来”和“过去”无关。

在贝努利过程(){},1X n n ≥中,设()X n 表示第n 次掷一颗骰子时出现的点数,易见,今后出现的点数与过去出现的点数无关。

在维纳过程(){},0X t t ≥中,设()X t 表示花粉在水面上作布朗运动时所处的位置,易见,已知花粉目前所处的位置,花粉将来的位置与过去的位置无关。

在泊松过程(){,0}N t t ≥中,设()N t 表示时间段[0,]t 内进入某商店的顾客数。

易见,已知时间段0[0,]t 内进入商店的顾客数()0N t ,在时间段()0[0,]t t t >内进入商店的顾客数()N t 等于()0N t 加上在时间段0(,]t t 内进入商店的顾客数()()0N t N t -,而与时刻0t 前进入商店的顾客无关。

一、马尔可夫过程定义:给定随机过程(){},X t t T ∈。

如果对任意正整数3n ≥,任意的12,,1,,n i t t t t T i n <<<∈= ,任意的11,,,n x x S -∈ S 是()X t 的状态空间,总有()()()1111|,n n n n P X x X t x X t x --≤==()()11|,n n n n n P X x X t x x R --=≤=∈ 则称(){},X t t T ∈为马尔可夫过程。

在这个定义中,如果把时刻1n t -看作“现在”,时刻n t 是“将来”,时刻12,,n t t - 是“过去”。

马尔可夫过程要求:已知现在的状态()11n n X t x --=,过程将来的状态()n X t 与过程过去的状态()()1122,,n n X t x X t x --== 无关。

这就体现了马尔可夫过程具有无后效性。

通常也把无后效性称为马尔可夫性。

从概率论的观点看,马尔可夫过程要求,给定()()1111,,n n X t x X t x --== 时,()n X t 的条件分布仅与()11n n X t x --=有关,而与()()12,,n X t X t - 无关。

二、马尔可夫链及其转移概率马尔可夫链是参数离散、状态离散的最简单的马尔可夫过程。

在马尔可夫链(){},X t t T ∈中,一般取参数空间{}0,1,2,T = 。

马尔可夫链的状态空间E 的一般形式是{}0,1,2,E = 。

1、马尔柯夫链定义:一个随机序列{X(t), t=1,2,3,…}取值于正整数空间E ={0,1,2,……},或者为E 的子集, 如果有:()()()()1111|,n n n n P X t x X t x X t x --===()()()11|n n n n P X t x X t x --=== x i ∈E ={0,1,2,……} ; i=1,2,…则称为序列(){},X t t T ∈为马尔柯夫(Markov)链。

这种序列具有马尔可夫性,也叫无后致性。

注意:t 和i 均取整数。

2、马尔柯夫链的含义:可以这样理解:序列(){}X t 的“将来”只与“现在”有关而与“过去”无关。

3、马尔柯夫链的状态:马尔柯夫链序列(){}X t 中的某一个符号X(t i )的数值一定为E 中的某一个元素x i (或x j ),这时,称x I (或x j )为随机序列的一个状态Si 。

4、马尔柯夫链的一步转移概率马尔柯夫(Markov)链的统计特性用条件概率(状态转移概率)来描述: 习惯上把转移概率记做()()()()()()()()(1)11|1|n n ij ij P X t x X t x P X t j X t i p t p t -+===+====这称为马氏链的一步转移概率。

为马尔柯夫链从状态i 变为状态j 的条件概率。

它满足:(概率的加法公式)p ij (1)(t)≥0 i j ∈E()1ij j Ep t i E ∈=∈∑5、马尔柯夫链的K 步转移概率:其k 步转移概率为:为马尔柯夫链从状态i 经过k 步(k 个单位时间)后变为状态j 的条件概率:()()()()()|k ij P X t k j X t i p t +===它满足:p (k)ij (t)≥0 i j ∈E()()1k ijj Ept i E ∈=∈∑6、平稳马尔柯夫链的性质:如果马尔柯夫链是平稳的,即与时刻无关,与t 无关,我们讨论的马尔柯夫链只是这种最简单的情况。

这种平稳马氏链称为齐次马氏链。

由于这种齐次马尔柯夫链的转移概率与时间无关,因此去掉其时间变量t ,其中的一步转移概率为()1ij ij p p =,k 步转移概率为()k ij p ,n 步转移概率为()n ij p 。

定义2:向量()12,,,n u u u u = 称为概率向量,如果u 满足: 10,1,2,,1nj ii u j nu=≥==∑定义3:若方阵P 的每行都为概率向量,则称此方阵为概率矩阵。

可以证明,如果矩阵A 和B 皆为概率矩阵,则,,kkAB A B 也都是概率矩阵(k 为正整数)由所有一步转移概率组成的矩阵称为一步转移概率矩阵表示为:111212122212n n n n nn p p p p p p P p p p ⎛⎫ ⎪⎪= ⎪ ⎪⎝⎭120.80.180.020.80.20.650.250.10.70.3001P P ⎛⎫⎛⎫ ⎪== ⎪⎪⎝⎭⎪⎝⎭转移矩阵必为概率矩阵,且具有以下两个性质: 1)()()1k k PP P -=2) ()k k PP =下面主要学习正则链和吸收链1、正则链:这类马氏链的特点是,从任意状态出发经过有限次转移都能达到另外的任意状态,有如下定义.定义4 一个有n 个状态的马氏链如果存在正整数N ,使从任意状态i 经过N 次转移都已大于零的概率到达状态(),1,2,,j i j n = ,则称为正则链。

正则链的判断方法:对于概率矩阵P ,若幂次方mP 的所有元素皆为正数(指mP 的每一元素大于零),则矩阵P 称为正规概率矩阵,此时马氏链称为正则链,或者称马氏链具有遍历性。

遍历性的直观含义:一个遍历的马尔可夫链经过相当长的时间后,它处于各个状态的概率趋于稳定,且概率稳定值与初始状态无关。

在工程技术中,当马尔可夫链的极限概率分布存在时,它的遍历性表示一个系统经过相当长时间后趋于平衡状态,这时,系统处于各个状态的概率分布即不依赖于初始状态,也不在随时间的推移而改变。

设系统的极限分布(也是稳态分布)用行向量()013,,,,n πππππ=来表示,一步转移概率矩阵为P ,则有P ππ=,且11ni i π==∑从而可以解出系统的极限分布(或稳态分布)从状态i 出发经k 次转移,第一次到达状态j 的概率称为i 到j 的首达概率,记做()ij f n , 于是 ()1ij iji nf n μ∞==∑为由状态i 第一次到达状态j 的平均转移次数,特别的,ii μ是状态i 首次返回的平均转移次数,ii μ与稳态概率ω有密切关系,即对于正则链,1/ii i μπ=马尔可夫链模型:设系统在0k =时所处的初始状态()()()()()00012,,,nS S S S = 为已知,经过k 次转移后所处的状态向量()()()()()()12,,,1,2,k kkk nSS S S k == ,则()()()11121002122212kn k n k n n nn p p p p p p SS P Sp p p ⎛⎫⎪ ⎪== ⎪⎪⎝⎭此式即为马尔可夫预测模型。

由上式可以看出,系统在经过k 次转移后所处的状态()k S只取决于它的初始状态()0S和转移概率P 。

因此对于马氏链模型最基本的问题是构造状态()X t 及写出转移矩阵P ,一旦有了P ,那么给定初始状态概率()0S就可以用上式计算任意时段的状态概率()k S。

2、 吸收链在马尔可夫链中,称1ij p =的状态i,j 为吸收状态。

如果一个马尔可夫链中至少包含一个吸收状态,并且从每一个非吸收状态出发,都可以到达某个吸收状态,那么这个马尔可夫链称为吸收链。

含有m 个吸收状态和(n-m)个非吸收状态的吸收链,其转移矩阵的标准形式为()()0m m n nn m n m I P R Q ⨯⨯-⨯-⎛⎫= ⎪ ⎪⎝⎭(1)其中矩阵R 中含有非零元素,m m I ⨯为m 阶单位矩阵。

Q 不是概率矩阵,它至少存在一个小于1的行和,且如下定理成立。

定理1 对于吸收链P 的标准形式(1),()I Q -可逆,()1s s M I Q Q ∞-==-=∑,记元素全为1的列向量()1,1,,1e '= ,则y Me =的第i 分量是从第i 个非吸收态出发,到某个吸收状态吸收的平均转移次数。

设状态i 是非吸收态,j 是吸收状态,那么首达概率()ij f n 实际上是i 经n 次转移被j 吸收的概率,而()1ij ij n f f n ∞==∑则是从非吸收状态i 出发终被吸收状态j 吸收的概率,记{}()ij k r rF f -⨯=,下面的定理给出了计算ij f 的方法。

定理2 设吸收链的转移矩阵P 表为标准形式(1),则F MR =例1、设马尔可夫链(){},0X t t ≥的状态空间{}1,2,3E =,一步转移概率矩阵为1/43/401/31/31/301/43/4P ⎛⎫ ⎪= ⎪ ⎪⎝⎭初始分布为()()01/4,1/2,1/4S=,即()()()()()()11101,02,03424P X P X P X ======则 ()()()220113/576,230/576,233/576P P P ==用Matlab 计算如下:s0=[1/4 1/2 1/4]; P=[1/4 3/4 0;1/3 1/3 1/3;0 1/4 3/4];S2=s0*P.^2=(0.0712 0.2118 0.1962)稳态分布 T=(t1,t2,t3),TP=T,变换后 (P ’-E)T ’=0 T=(0.16 0.36 0.48) 附程序:liyiw.m市场占有率模型设有甲、乙、丙三家企业,生产同一种产品,共同供应1000家用户,各用户在各企业间自由选购,但不超出这三家企业,也无新的客户。

假定在10月末经过市场调查得知,甲、乙、丙三家企业拥有的客户分别是:250户,300户,450户,而11月份用户可能的流动情况如表所示:假定该产品用户的流动按上述方向继续变化下去(转移概率不变),预测12月份三家企业市场用户各自的拥有量,并计算经过一段时间后,三家企业在稳定状态下该种产品的市场占有率。

相关主题