马尔可夫链

马尔可夫链该模型里，过去对未来的影响归结于对状态的影响，它的概率分布随着时间变化。假设变量取值的状态只取有限个值。应用：几乎全部动力系统，通信、自动化控制、信息传输、制造业、经济、运筹学等。离散时间的马尔可夫链状态在确定的离散时间点上发生变化。转移概率Pij：当前状态i，下一个状态j的概率。核心假设：只要时刻n的状态为i，不论过去发生什么，不论如何达到状态i，下一个时刻转移到状态j的概率一定是转移概率Pij。马尔可夫模型的性质：一个马尔可夫链模型由以下特征确定：1.状态集合{1,2,,}Sm2.可能发生状态转移(,)ij的集合，即由所有0ijP的,ij组成。3.ijP的取值（取正值）。由该模型描述的马尔可夫链是一个随机变量序列01,,XX，它们取值于S，并且满足：对于任意的时间n，所有状态以及所有之前可能的状态序列0,,nii，均有11100(|,,,)nnnnijPxjxixixiP马尔可夫链由转移概率矩阵刻画：第i行，第j列的元素为Pij1111mmmmPPPP转移概率图1.节点nodes：表示状态2.连接节点的有向弧线arcs：表示可能发生的转移3.Pij：标在相应的弧线旁边例1：爱丽丝上一门课程，每周可能进步也可能落后。如果给定的一周，她进步了，那么后一周进步的概率为0.8，落后的概率为0.2；如果给定的一周，她落后了，那么后一周进步的概率为0.6，落后的概率为0.4；假设这些概率都不依赖她之前的每周的进步落后情况。转移概率矩阵0.80.20.60.4转移概率图-------------------------------------------------------------------------------------例2：苍蝇和蜘蛛一只苍蝇在一条直线上移动（共4个单位），每次移动一个单位长度。每单位时间，它以0.3的概率向左移动一个单位，以0.3的概率向右移动一个单位，以0.4的概率停留在原地。两只蜘蛛等待在位置1和4，如果苍蝇到达这两个位置，它将被蜘蛛捕获，过程结束。转移概率矩阵10000.30.40.3000.30.40.30001转移概率图例3：一个教授抽取测试卷子。卷子的难度分成3种：困难、中等和容易。如果本次抽到的困难的卷子，则下次分别有0.5的概率抽中中等和容易的卷子。如果本次抽到的是中等的卷子，则下次仍旧0.5的概率为中等难度，另外有0.25的概率抽中困难或容易的卷子。如果本次抽到的是容易的卷子，则下次仍旧0.5的概率为容易难度，另外有0.25的概率抽中困难或中等的卷子。转移概率矩阵00.50.50.250.50.250.250.250.5转移概率图------------------------------------------------------------------------------------------路径的概率计算未来任何一个给定状态序列的概率。01121001100(,,,)()nnnniiiiiiPxixixiPxiPPP图形上，一个状态序列能表示为在转移概率图中的一个转移弧线序列。在给定初始状态下，该路径的概率等于每个弧线上转移概率的乘积。n步转移概率定义：0()(|)ijnrnPxixi计算在当前状态条件下，未来某个时期状态的概率分布。当前状态i，n个时间段后的状态将是j的计算公式：C-K方程1()(1)mijijkjkrnrnP，其中(1)ijijrP表示为矩阵：RPPPP()nnC-K公式证明，应用全概率公式：01010110111(|)(|)(|,)(|)(|)(1)mnnnnkmnnnkmijkjkPxjxiPxkxiPxjxkxiPxkxiPxjxkrnPn步转移概率矩阵：()ijrn看成一个二维矩阵第i行第j列的元素。讨论n时：例1中，每一个()ijrn都收敛于一个极限值，不依赖于初始状态i。0.750.25()0.750.25ijP例2中，()ijrn仍旧收敛，但是极限值依赖于初始状态，并且对于某特定的状态极限值可能为0。10002/3001/3()1/3002/30000ijP状态的分类可达的如果对于某一个n，n步转移概率()ijrn是正的，则称状态j为从状态i可达的。常返态：对于每个从i出发可达的状态j，相应的从j出发也可达i，那么状态i称为常返的。如果一个状态不是常返的，我们称之为非常返的。如果i是常返态，那么从i可达的状态集合()Ai组成一个常返类。单个常返类一个非常返态(3)和一个常返类(1,2)两个非常返态(2,3)和两个常返类马尔可夫链的分解一个马尔可夫链的状态集合可以分解成一个或多个常返类，加上可能的一些非常返状态。一个常返态从它所属的类里任何一个状态出发是可达的，但从其他类里的常返状态出发是不可达的。从任何一个常返状态出发都不可到达非常返状态。从一个非常返状态出发，至少有一个或多个常返态是可达的。常返类的周期性：一个状态被回访时间是否出现周期性。如果一个常返类的状态可被分成d1个互不相交的子集，且满足所有的转移都是从一个这样的子集到下一个，我们称这个常返类是周期的。如果一个常返类不具有周期，称为非周期的。稳态性质研究对象：一个常返类，并且不是周期的。单个常返类的链也可能是不收敛的，比如具有周期的常返类。稳态收敛定理：考虑一个非周期的，单个常返类的马尔可夫链，那么，状态j和它对应的稳态概率jW具有如下性质：1、对于每个j有lim()ijjnrnW2、是下面方程组的唯一解：1mjkkjkWWp11mkkW3、另外有0jW，对于所有的非常返状态j0jW，对于所有的常返状态j写作矩阵乘法：111111[][001]111mmmmppWWpmp，可用MATLAB解决。