ch08马尔可夫链和马尔可夫决策过程.ppt

教学要求: 第八章马尔可夫链和马尔可夫决策过程?掌握掌握马尔可夫分析的基本原理和方法?会运用马尔可夫决策过程解决一些基本问题?了解马尔可夫决策过程的建模和求解方法目录?马尔可夫链?n步转移概率?马尔可夫链中状态的分类?稳态概率?马尔可夫决策规划目录?马尔可夫链?n步转移概率?马尔可夫链中状态的分类?稳态概率?马尔可夫决策规划定义?离散时间随机过程:假设我们观测一个系统在离散时间点上某个特性的情况,令为此系统特性在时刻 t的值。离散时间的随机过程就是关于随机变量之间关系的描述。?马尔可夫链:称一个离散时间随机过程为马尔可夫链, 如果对于所有的和状态,成立称概率规则在时间上是平稳的链为平稳马尔可夫链。),,,,( 001111 11iXiXiXiXiXP tttttt??????????)( 11ttttiXiXP??????转移概率:在马尔可夫链中,对于所有的状态 i和j,以及所有的时刻 t,有,称为马尔可夫链的转移概率。对于平稳马尔可夫链,转移概率可以用一个转移概率矩阵 P表示。 ijttpiXjXP????)( 1 tXXX,,, 10? tX ijp ?,2,1,0?t例题赌徒问题考虑一赌徒,在时刻 0拥有赌金 2元,在时刻进行赌局。在每赌博中,赢一元的概率是,输一元的概率是。赌徒的目标是赌金增加到 4元,所以当赌金增加到4元或输光时赌博结束。请描述此离散时间随机过程,并判断其是否为一个平稳马尔可夫链?若是,请写出其概率转移矩阵。?,2,1p p?1解答我们定义为赌徒在第 t场赌局结束后的赌金,则可以把看作是离散时间的随机过程。注意到是已知条件,但是和其后的值是随机的。因为赌徒在第 t +1 场赌局结束时的赌金概率分布只依赖于赌徒在第 t场赌局结束时的赌金,所以此为一个马尔可夫链。因为赌博输赢的概率并不因时间而改变,所以此又为一个平稳马尔可夫链。其转移概率矩阵如下: t10,,,XXX?2 0?X 1X tX tX????????????????????10000 0100 0010 0001 000014$ 3$ 2$ 1$ 0$ 4$3$2$1$0$pp pp ppP 状态目录?马尔可夫链?n步转移概率?马尔可夫链中状态的分类?稳态概率?马尔可夫决策规划 n步转移概率假设已知马尔可夫链的转移概率矩阵 P。问:如果一个马尔可夫链在时刻 m处于状态 i,那么在 n个阶段后,此马尔可夫链处于状态 j的概率是多少? 因为研究的是平稳马尔可夫链,所以这个概率与 m无关,可以记作: 其中, 称作从状态 i到状态 j的n步转移概率。显然, ;; 又由转移概率矩阵,得: 就是矩阵的第 i行第 j列元素。推而广之,可知对于 n >1 , )()()( 0nPiXjXPiXjXP ij n m nm???????)(nP ij ij ijpP?)1(??? sk kj ik ijppP 1)2()2( ijP 2P 列元素行第的第 jiPnP n ij?)(例题饮料的市场份额问题假设目前饮料市场上只有两种饮料。假定顾客上一次购买时选择饮料 1,则下次选购饮料 1的概率为 90% ;顾客上一次购买时选择饮料 2,则下次选购饮料 2的概率为 80% 。 a)如果顾客当前选购的是饮料 2,则在此后的第二次购买时选择饮料 1的概率是多少? b)如果顾客当前选购的是饮料 1,则在此后的第三次购买时选择饮料 1的概率是多少? 解答 1 我们可以把顾客的饮料选购过程看作一个马尔可夫链, 其中任何给定时刻的状态为顾客在最近一次购买时选择的饮料种类。由此,顾客的饮料选购过程可表示为两个状态的马尔可夫链,其中状态 1 = 顾客最近一次选购的是饮料 1, 状态 2 = 顾客最近一次选购的是饮料 2。定义为顾客在将来第次购买时选择的饮料种类(当前一次选购的饮料种类为),则可被表示为具有如下转移概率矩阵的马尔可夫链, ?,, 10XX 0X tX???????80 .020 .0 10 .090 .02 1 21饮料饮料饮料饮料 P