马尔可夫决策规划2.doc

马尔可夫决策规划第二讲 马尔可夫链与马尔可夫过程2.1 马尔可夫链为书写方便，下面用X表示随机变量（）。定义2.1：随机变量序列Xn, n=0,1,2,.称为是一个马尔科夫（Markov）链，如果等式pXm+k=j|Xm=i, XkL=iL, ., Xk2=i2, Xk1=i1 =pXm+k=j|Xm=i对任意整数k、L、m以及非负整数mkLk2k1均成立。其中，Xm=i表示马尔科夫链在第m步（时刻m）位于状态i，状态i的集合S称为状态空间；p(k)ij(m)=pXm+k=j|Xm=i称为在时刻m位于状态i经k步转移到达状态j的k步转移概率，而pij(m)= p(1)ij(m) 称为时刻m的1步转移概率；P(k)(m)=(p(k)ij(m)称为时刻m的k步转移概率矩阵，而P(m)=(p(1)ij(m)=(pij(m)称为时刻m的1步转移概率矩阵。Markov满足的K-C方程如下：A. P(k)(m)= P(l)(m)P(k-l)(m+l)，其中0lk 约定：P(0)(m)=IB. 约定：定义2.2：马尔科夫链Xn, n=0,1,2,.称为是齐次的，是指它在时刻m的1步转移概率矩阵P(m)与m无关，它等价于P(k)(m)与m无关。其中，P(k)=(p(k)ij)称为齐次马氏链的k步转移概率矩阵，而P= (pij)称为齐次马氏链的1步转移概率矩阵。相应地有，A. K-C方程：P(k) = P(l)P(k-l)，其中0lk B. P(k)=PkC. 马尔科夫链的概率分布：设Xn, n=0,1,2, .为一马尔科夫链，X0的分布列（初始分布）为(约定马尔科夫链的概率分布列为行向量)，记为Xn的分布列或Markov链在时刻n的瞬时分布列，P(n), n=0,1,2,.为一步转移概率矩阵的集合，则有： C1：（非齐次） C2：（齐次）关于马氏链的存在性：对任意给定的分布列和一束随机矩阵P(n), n=0,1,2,.，a.s唯一地存在某概率空间（, F, P）上的马氏链，恰以为初始分布列、以P(n), n=0,1,2,.为转移概率矩阵的集合。因此，齐次马氏链由它的初始分布和一步转移概率矩阵唯一决定。例2.1 假设三个食品公司分别生产三种不同牌子的方便面。它们除通过改进成品口味、美化包装以增强在市场的竞争力外，还各自开展了广告攻势促销本公司的产品。因此，各公司所占的市场比例是随时间有所变化的，可以根据个别人的行为来推断多数人的行为。比如，随机选择的个人若以概率1/2偏爱公司1生产的方便面，则表明公司1占有50%的市场比例。以表示随机选择的个人(样本空间的一个元素)在第n周所偏爱的公司。有理由认为，当给定现在的偏爱，将来的偏爱与过去的选择无关。于是，便构成一个以为状态空间的Markov链。假设在任一时刻，公司1能留住它1/2的老顾客，其余的则对半购买另两个公司的产品。公司2的一半顾客在下周改买公司1的产品，其余的仍购买公司2的产品。公司3能维持其3/4的老顾客，其余的则在下周流向公司2。即Markov链的转移概率矩阵可表示为 (2.1)公司对第n周它所占有的市场份额感兴趣，即概率。再者当n趋于无穷时，若这一概率的极限存在，则此极限概率也是令各公司感兴趣的，它刻画了公司i占有市场的稳态概率。例2.2 继续考虑例2.1的三个食品公司之间的竞争问题，描述顾客偏爱变化情形的转移概率矩阵P已由(2.1)式给出，(1) 求出；(2) 假设已知任一初始分布，求。解：利用关系式计算首先，求出与转移概率矩阵P对应的特征值及特征向量。由得即转移概率矩阵P的三个特征值分别为，。为求特征向量，令与特征值对应的特征向量为，由于，列出方程组即可求得，此处不再详述。取为相应于特征值1的特征值向量，再分别求出与特征值及相对应的特征向量与。鉴于特征值、与互不相同，故可知与必线性无关。若令 ，则可逆，且有，可以算出，于是 于是有(2) 设是任一初始分布，则由分布概率与转移概率的关系有。这表明，不管初始时三个食品公司所占的市场份额如何，在经过充分长的一段时间的竞争后，每个公司所占的市场份额趋于稳定，均为左右。2.2 状态的分类及状态空间的分解1、状态的常返性定义2.3：设Xn, n=0,1,2, .是一马尔科夫链，状态空间为S，称为由状态i出发经n步首次到达状态j的概率，其中，；称为由状态i出发经有限步到达状态j的概率。 显然，。进一步地，当n取时，表示从状态i出发永不到达状态j的概率，即。 对，称为Markov链X首次到达状态j的时刻，也就是首次到达状态j的间隔。显然，对任意的有，lll定义2.4：若，则称状态i是常返的；若，则称状态i是非常返的。另外，如果，则称i为吸收状态。 进一步地，定义为常返状态i的平均返回时间，表示Markov链X自状态i出发，首次重返状态i所需时间的期望值。定义2.5：如果，则称常返状态i为正常返的；如果，则称常返状态i为零常返。例2.3 设Markov链的状态空间。转移矩阵为 ，判断哪些状态是常返的。解：图2.1中画出了各状态之间的转移图。从图2.1可知，所以；，所以；， 所以；，所以。于是，状态2，3，4是常返状态，而状态1是非常返状态，且状态4还是吸收状态。1/411/21/41/211/21432图2.1 某Markov链的状态转移图2、状态的周期性定义2.6：如集合非空，则称该集合的最大公约数d=d(i)=G.C.D为状态i的周期。如d1，就称i为周期的；如d=1，就称i为非周期的。特别地，若，则状态i是非周期的。定义2.7：如果状态i既是正常返的，又是非周期的，则称状态i是遍历的。例如，吸收状态是一种最特殊的遍历状态。例2.4 设某Markov链状态空间为，转移概率矩阵P为 试求状态0的周期。解：不难直接算出，而，。由于的最大公约数为2，所以状态0的周期为2。3、判别状态类别的两种方法 从前述可知，状态类别判断的依据是首达概率。1) 首达概率的计算定理2.1：首达概率的计算方法为（1）（2）例2.5设Markov链X的状态空间为，其一步转移概率矩阵P由下式给出：试判断出以上各状态是常返的或是非常返的。解：由定理2.1的结论(1)有，由于，故。从而，故状态1为正常返的。其次，仍由定理2.1的结论，对任意，有 (2.2)在上式中取，即。由此可推得。于是，结合(2.2)式，有 。故，这表明状态2是非常返的。 类似地，可求得，故，于是状态3也是非常返的。 最后，由定理2.1的结论(2)，有 。由此推知，类似地可以求出。 综上所述，状态2与3皆为非常返的，而状态1是正常返的。2) 势矩阵的计算为避开首次概率的计算，下面给出判断常返状态的另一个准则。称为Markov链X的势矩阵，其中。令，并记，于是，势矩阵的概率含义为：定理2.2：对任意，有引理2.1：（1）对任意，； （2）对任意，有如下结论成立：， 下面是常返态的另一判别准则：定理2.3：状态j为常返的充要条件是。4、状态空间的分解定义2.8：1) 如果存在，使得，则称状态i可达(accessible)状态j，记作; 2) 如对一切，皆有，则称从状态i不可达状态j，记作; 3）如果且，则称状态i与状态j是互达的，记作。 其中，所有状态都可互达的齐次Markov链称作不可约的。定理2.4：互达关系是数学上的一个等价关系，即满足1） 自反性：;2） 对称性：，则;3） 传递性：，则。定理2.5：状态的充要条件是。推论2.1：设状态，则的充要条件是。定理2.6：设i 是常返状态，且，则，而且j也是常返状态。 定理2.7：设，则以下结论成立：1） 若状态i为常返的，则状态j也为常返的；2） 若状态i为非常返的，则状态j也为非常返的；3） 状态i与状态j具有相同的周期。 利用上面的结论，可对状态空间进行分解。若Markov链X的状态空间S是不可约的，则无法进行分解。否则，分别用C、D表示Markov链X的所有常返状态及非常返状态，有。如果，可以按照互达关系继续进行分解。于是，可将常返类C分解成一些互不相交的等价类C1,C2,，即，从而有。因此，对，或，有或（）。例2.6 继续考虑例2.1，已知描述顾客偏爱变化的转移概率矩阵P为： 与它相对应的转移图在图2.2中给出。由此转移图不难看出，状态空间中的任意两个状态之间都是互达的，即此Markov链是不可约的。显然，若以图2.2中所示的转移图为依据，也可反写出相应的转移概率矩阵P。一般来说，转移概率矩阵和转移图是相互对应的。1/21/41/21/41/43/41/2132 图2.2 描述顾客偏爱变化的转移图2.3 转移概率的极限性质 下面，用C与D表示Markov链X的常返类与非常返类，用C(i)表示常返状态i所属的不可约常返类，即。定理2.8：1）对任意，如果，则有；对任意，如果，则有； 2）对任意，有；对任意，有。定理2.9：对于任意以及，恒有。定理2.10：对，j为非常返状态，则。 下面的定理表达了常返状态与转移概率的极限概率之间的联系：定理2.11：设j为常返状态，则1） j为零常返状态的充要条件是；2） j为遍历状态的充要条件是；3） j为周期的正常返状态的充要条件是不存在。定理2.12：设j为零常返状态或遍历状态，则对有当出现下述两种情形时，转移概率的极限值不存在：（1）i与j为互达的、周期的正常返状态；（2）i为非常返状态，j为周期的正常返状态。但它们的平均极限总是存在的，且对一切恒有：2.4 平稳分布在Markov链X中，状态概率是一个重要的量，表示系统在时刻n处于状态j的概率。这里的问题是：是否存在一个不随时间变化的所谓“平稳的”概率分布？定义2.9：设Markov链X=Xn, n1的转移概率矩阵为P。若离散概率分布满足，则称是Markov链X的平稳分布。定理2.13：设Markov链X=Xn, n1是遍历的，P为转移概率矩阵，记，则方程组有唯一的正解。定理2.14：设Markov链X=Xn, n1是遍历的。令，其中，则是Markov链X的唯一的平稳分布。此外，还有，。利用上述定理，可得下述一般性结论：设Markov链X是不可约正常返的，令，（），则是Markov链X唯一的平稳分布，且有，下面的定理给出了任意一个Markov链X具有平稳分布的条件。定理2.15：设X=Xn, n1是一Markov链，则1） X没有平稳分布的充要条件是X没有正常返状态；2） X具有唯一平稳分布的充要条件是X仅有一个不可约的正常返类；3） X具有无限多个平稳分布的充要条件是X至少有两个不可约的正常返类。例2.7 再返回到例2.1中已讨论过的三个食品公司之间的竞争问题。以表示随机选择的个人在第n周所偏好的公司，在例2.1中已指出是一个以为状态空间的Markov链，其转移概率矩阵P由(2.1)式给出。而且，由于S中三个状态互达，于是X是不可约的。再因为该的状态空间S是有限的，而由于不可约的有限Markov链必是正常返的，于是X为正常返的。这样，X有唯一的平稳分布，而且此平稳分布是，的唯一正解。先解方程。将它写成分量的形式即得 此方程的通解为，于是，满足的唯一正解为，它便是X的唯一的平稳分布。 此外，因，由定义2.6可知，状态1是非周期的，从而，X是遍历的。于是上述结论是与例2.2直接计算获得的结果相吻合的，但这里采用的方法要简单多了。2.5 马尔可夫过程1、相关概念定义2.10：设T=0,+)，随机过程Xt, tT如果对任意n0, t0, ssnsn-1s10, 以及任意状态i1,i2,in ,i,j(状态空间)，均有pXs+t=j|Xs=i,Xsn=in,.,Xs1=i1 = pXs+t=j| Xs=i，则称随机过程Xt, t0为一马尔科夫过程，其中T=0,+)称为时间参数集。定义2.11：马尔科夫过程Xt, t0称为可列马尔科夫过程(时间连续)，如果它的状态空间S为可列集，此时记S=0,1,2,.。定义2.12：如果马氏过程Xt, tT的转移概率pij(s,s+t)独立于时刻s，即pXs+t=j| Xs=i= pXt=j| X0=i，则称其为齐次马尔科夫过程，以下简记为pij(t)。P(t)=(pij(t) 称为转移概率矩阵，简称转移矩阵。注：本课“排队论”涉及到的主要是“齐次可列马尔科夫过程”。以下若无特殊说明，均指齐次可列马尔科夫过程！2、马氏过程的讨论1）对马氏过程Xt, tT，显然有：对成立，这说明转移矩阵P(t)是随机矩阵。进一步地，若还满足，则称P(t)是一标准转移概率矩阵（或称马氏过程X(t)是标准的）。记qj(t)=p(Xt=j), ，则称以qj(t)为分量的行向量=qj(t)为马氏过程在时刻t的瞬时分布，而称为初始分布。2）K-C方程1）对任意正整数n，任意0t0t1tn恒有 2）P(s+t)=P(s)P(t) 3）3）如果(其中)存在且有限，则称标准的转移概率矩阵P(t)=(pij(t)是可微的。这时称Q=(qij, i,jS)为P(t)的密度矩阵，或称Q为P(t)对应的马氏过程的密度矩阵。4）若离散概率分布满足在条件下, 则称是马尔科夫过程的平稳分布。 一般地，若马尔科夫过程是不可约的，那么有，否则（零常返或非常返），极限为0。且有： ， 上式的含义：不可约Markov过程X离开状态j的概率等于从任何其他状态进入状态j的概率。例2.8：某商店有两台运行的机器，由于出现故障较频繁，故安排一名全职修理工专门负责维修。设维修时间服从参数为的负指数分布，均值为1/2天。当维修完毕后，又发生故障的时间也服从参数为的负指数分布，均值为1天，且两分布相互独立。定义X(t)为X(t)=在时刻t发生故障的机器数。试求出各状态的平稳分布。解：根据题意知，随机变量X(t)取值为0,1,2,()，连续时间随机过程刻画