[工学]ch08.ppt

教学要求： 目 录 马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 目 录 马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 定义 离散时间随机过程 ：假设我们观测一个系统在离散时间点上某个特性的情况，令 为此系统特性在时刻t的值。离散时间的随机过程就是关于随机变量 之间关系的描述。 马尔可夫链 ：称一个离散时间随机过程为马尔可夫链，如果对于所有的 和状态，成立 称概率规则在时间上是平稳的链为平稳马尔可夫链。 例题 赌徒问题 考虑一赌徒，在时刻0拥有赌金2元，在时刻 进行赌局。在每赌博中，赢一元的概率是 ，输一元的概率是 。赌徒的目标是赌金增加到4元，所以当赌金增加到4元或输光时赌博结束。 请描述此离散时间随机过程 ，并判断其是否为一个平稳马尔可夫链？若是，请写出其概率转移矩阵。 解答 我们定义 为赌徒在第t场赌局结束后的赌金，则可以把 看作是离散时间的随机过程。注意到 是已知条件，但是 和其后的 值是随机的。 因为赌徒在第t+1场赌局结束时的赌金概率分布只依赖于赌徒在第t场赌局结束时的赌金，所以此为一个马尔可夫链。因为赌博输赢的概率并不因时间而改变，所以此又为一个平稳马尔可夫链。其转移概率矩阵如下： 目 录 马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 n步转移概率 假设已知马尔可夫链的转移概率矩阵P。问：如果一个马尔可夫链在时刻m处于状态i，那么在n个阶段后，此马尔可夫链处于状态j的概率是多少？ 因为研究的是平稳马尔可夫链，所以这个概率与m无关，可以记作： 其中， 称作从状态i到状态j的n步转移概率。 显然， ； ； 又由转移概率矩阵，得： 就是矩阵 的第i行第j列元素。 推而广之，可知对于n1， 例题 饮料的市场份额问题 假设目前饮料市场上只有两种饮料。假定顾客上一次购买时选择饮料1，则下次选购饮料1的概率为90%；顾客上一次购买时选择饮料2，则下次选购饮料2的概率为80%。 如果顾客当前选购的是饮料2，则在此后的第二次购买时选择饮料1的概率是多少？ 如果顾客当前选购的是饮料1，则在此后的第三次购买时选择饮料1的概率是多少？ 解答1 我们可以把顾客的饮料选购过程看作一个马尔可夫链，其中任何给定时刻的状态为顾客在最近一次购买时选择的饮料种类。由此，顾客的饮料选购过程可表示为两个状态的马尔可夫链，其中 状态1 = 顾客最近一次选购的是饮料1， 状态2 = 顾客最近一次选购的是饮料2。 定义 为顾客在将来第次购买时选择的饮料种类（当前一次选购的饮料种类为 ），则 可被表示为具有如下转移概率矩阵的马尔可夫链， 解答 2 回答问题a） 我们知道 的第2行第1列元素。 所以， ，这就意味着当前购买饮料2的顾客在此后第二次购买时选择饮料1的概率是0.34。 回答问题b） 我们知道 的第1行第1列元素。 所以， 初始状态未知的情况 在许多情况下，我们不知道马尔可夫链在时刻0时的状态。令 为系统在时刻0时处于状态的概率，则我们可以确定系统在n时刻处于状态j的概率 时刻n处于状态j的概率 = = 目 录 马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 定义1 路径：给定两个状态i和j。从i到j的一条路径，是指以为i起点，以j为终点的一系列状态转移，且每次转移都具有正的发生概率。 可达性：如果存在一条从i到j的路，则称状态j是从i状态可达的。 相通性：如果状态j是从i状态可达的，且i是从j可达的，则称状态i和j是相通的。 闭集：如果对于马尔可夫链中的一个状态集合S，满足任何一个S外的状态都不可能从S内的某个状态可达的，则称S为闭集。 吸收状态：如果