一、马尔可夫链及其概率分布的定义 状态和时间参数都是离散的马尔可夫过程称为马尔可夫链，或马氏链 记为｛Xn=X(n),n=0,1，2，…｝,记链的状态空间为＝a1，a2，…，aiR .在链的情况，马尔可夫性通常用分布率表示 1.1.马氏链的定义马氏链的定义 其中a., 称｛Xn,n=0,1，2，…｝为马氏链定义定义1 1 若对于任意的正整数n，r和任意的 则称｛Xn,n0｝为马氏链 定义定义2 2 设{Xn,n0},其状态空间为,若对于任意的正整数n和任意的,称为马氏链在时刻m系统处于状态ai的条件下，在时刻m+n转移到状态aj的转移概率 例.记从数1,2, …,N中任取一数为X0 0，当n1时，记从数1,2, …,Xn n-1-1中任取一数为Xn n,证明｛Xn n,n=0，1，2,…｝是一个马氏链证：｛Xn n,n=0，1，2,…｝的状态空间={i,1iN}, 可见,｛Xn n,n=0，1，2,…｝是一个马氏链 2 2．转移概率的性质．转移概率的性质 (1)(1) Pij0； 事实上，因为链在m时刻从状态ai出发，到m+n时刻必然转移到a1，a2，状态中的一个，从而 2. .定义定义 若对任意的正整数m,n及任意的ai，aj，有 即马氏链{Xn,n0}的转移概率Pij(n,n+1)与n无关，则称转移概率具有平稳性，这时，马尔可夫链称为是齐次的。
称为马氏链的一步转移概率；齐次马尔可夫链及一步转移概率齐次马尔可夫链及一步转移概率 称为马氏链的一步转移概率矩阵；其中列为Xm的状态，行为Xm+1的状态 例（0－1传输系统）在一个n级数字传输系统中，设每一级的率为p，误码率为q=1-p，并设一个单位时间传输一级，X0是第一级的输入, Xn是第n级的输出（n≧1）,那么｛Xn n, n=0，1，2,…｝是一随机过程，状态空间={0,1}.0 0 1 1p1-p X0 X1 Xn-1 Xn0 0 1 1p1-p0 0 1 1p1-p 当Xn=i, i为已知时，Xn+1n+1所处的状态的概率分布只与Xn n=i 有关，而与时刻n以前所处的状态无关，所以它是一个马氏链 定义定义3 3 称条件概率 为马尔可夫链在时刻m处于状态ai的条件下，在时刻m+n步转移到状态aj的n步转移概率，简称为转移概率 且一步转移概率和一步转移概率矩阵分别为 ,且是齐次马氏链. 则称｛Xn,n0｝为(齐次)马氏链。
定义定义2 2 设{Xn,n0},其状态空间为E,若对于任意的正整数m,n和任意的E, 例例(一维随机游动) 设一醉汉Q（或看作一随机游动的质点），在如图所示直线的点集I＝｛1，2，3，4，5｝上作游动，仅仅在1秒、2秒…等时刻发生游动游动的概率规则是：如果Q现在位于点i (1
此时，相应链的转移概率矩阵只须把P中第1横行改为（1，0，0，0，0）总之，改变游动的概率规则，就可得到不同方式的游动和相应的马氏链 例 设Xn,n=0，1，2,…是独立同分布的随机变量列,记Xn可能取值的全体为I={i,i 1},则{Xn}为马氏链，并求其一步转移概率解 对任意的n及 所以{Xn}为马氏链 由于Xn, n=0，1，2,…独立同分布，因而 所以{Xn}为齐次马氏链其一步转移概率P: //例3 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成，见图7－3服务规则是：先到先服务，后来者需在等候室依次排队假定一个需要服务的顾客到达系统时发现系统内已有3个顾客（一个正在接受服务，两个在等候室排队）则该 顾客即离去设时间间隔Δt内将有一个顾客进入系统的概率为q，有一原来被服务的顾客离开系统（即服务完毕）的概率为p又设当Δt充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的再设有无顾客来到与服务是否完毕是相互独立的现用马氏链来描述这个服务系统 随机到达者等候室服务台系 统离去者设P表示一步转移概率Pij所组成的矩阵，则 称P为一步转移概率矩阵，它具有如下性质 （1） （2） （2）式中对j求和是对状态空间I的所有可能的状态进行的。
此性质说明，一步转移概率矩阵中任一行元素之和为1 表示时刻 时，系统内的顾客数，即系统的状态｛xn, n=0，1，2,…｝是一随机过程，状态空间I＝｛0，1，2，3｝，而且仿照例1、例2的分析，可知它是一个齐次马氏链下面来计算此马氏链的一步转移概率 p00――在系统内没有顾客的条件下，以 后仍没有顾客的概率（此处是条件概率，以下同），p00=1-q. p01――系统内没有顾客的条件下, 经 后有一顾客进入系统的概率, p01=q. p10――系统内恰有一顾客正在接受服务的条件下，经 后系统内无人的概率，它等于在 间隔内顾客因服务完毕而离去，且无人进入系统的概率，p10=p(1-q).p11――系统内恰有一顾客的条件下，在 间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客将继续要求服务，且无人进入系统的概率，这p11＝pq＋(1-p) (1-q). p12――正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率，p12=q(1-p). p13――正在接受服务的顾客继续要求服务，且在 间隔内有两个顾客进入系统的概率由假设，后者实际上是不可能发生的，p13=0. 类似地，有p21= p32 = p(1-q), p22 = pq+(1-p) (1-q), p23=q(1-p), pij= 0( | i-j |≧2 ). p33――或者一人将离去且另一人将进入系统，或者无人离开系统的概率，p33= pq+(1-p). 于是该马氏链的一步转移概率矩阵为 例4 某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察），用1表示正常状态，用0表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111设Xn为第n (n=1,2,…,97) 个时段的计算机状态，可以认为它是一个齐次马氏链，状态空间I={0,1}, 96次状态转移的情况是： 0→0，8次，0→1，18次； 1→0，18次，1→1，52次。
因此，一步转移概率可用频率近似地表示为 //为了进一步讨论马尔可夫链的统计性质，我们需讨论多步转移概率和有限维分布，为此我们先给出几个概念，n步转移概率，初始概率分布，绝对 概率分布// 3.3.多步转移概率及C-K方程 若{Xn}为齐次马氏链，则对任意非负整数m，任意正整数n,及， 因此，马氏链的齐次性可写为 定义定义 称条件概率 为马氏链{Xn,n≥0}的n步转移概率，并称由Pij(n)组成的矩阵 为马尔可夫链的n步转移概率矩阵 定义 设{Xn,n=0,1,…}为马尔可夫链，称X0 0的分布 pj j(0)=P{X0=j}, j为{Xn,n=0,1,…}的初始分布. 称Xn的分布pj(n)=P{Xn=j}, j 为{Xn,n=0,1,…}的绝对分布，初始分布和任一时刻 n的绝对分布可用向量表示 q(0)=(p1(0),p2(0), …) q(n)=(p1(n),p2(n), …)定理定理 设{Xn，n=0,1,…}为马氏链，则对于任意的正整数k,m，有 此方程称为Chapman-kolmogorov(切普曼－柯尔莫哥洛夫)方程,简称C-K方程. 证： 既:“从Xn=ai出发，经时刻m转移到中间状态ar,再从ar经k时段转移到aj状态”这样一些事件的和事件。
如果把转移概率写成矩阵的形式，那么C－K方程具有以下简单的形式 P P(m+k)=P P(m)P P(k) m, k≧0 特别地，P P(n)=P Pn, n步转移概率由一步转移概率完全决定 例 求带有两个反射壁的一维随机游动的两步转移概率矩阵 例 在n级0-1传输系统中，设p=0.9，求系统二级传输后的率与三级传输后的误码率.解 先求出n步转移概率矩阵P P(n)=P Pn 有相异特征值1=1，2=p-q ,由线性代数知识，可将矩阵P表示为对角阵 的相似矩阵 具体做法是：求出 1 ,2对应的特征向量 则P＝HH-1于是，容易算得 由上式可知，当p=0.9时，系统经二级传输后的率 与三级传输后的误码率分别为 对于只有两个状态的马氏链，一步转移概率矩阵一 般可表示为： 利用类似的方法，可得n步转移概率矩阵为 n=1,2,…. 四、有限维分布及遍历性 1．有限维分布 设马氏链{Xn,n≥0},状态空间，n步转移概率矩阵P(n). (1)一维分布 设链的 一维分布可用行向量表示p p(n)=(p1(n),p2(n),…,pj(n),…), 利用矩阵的乘法：p(n)= p(0)P(n) 说明马氏链在任一时刻n的一维分布由初始分布与n步 转移概率矩阵确定。
(2)n维分布 对任意n个时刻 0≤t1>1时就可得到n步转移概率的近似值： 1.1.定义定义 设马尔可夫链的状态空间为，如果对于所有的ai , aj, 转移概率pij(n) ,当n→∞时，存在不依赖于i的极限 则称此链具有遍历性，又若 ,称 =(1,2,…)为链的极限分布。
2.2.遍历性的定理遍历性的定理 定理定理 设齐次马氏链｛Xn,n0｝的状态空间为＝{a1, a2,…,an}，P是它的一步转移概率矩阵，如果存在正整数m，使对任意的ai ,aj，都有 Pij(m)>0, i , j =1,2,…,N 则此链具有遍历性，且有极限分布 =(1,2,…, N)，它是方程组 的满足条件 j>0, 的唯一解 在定理的条件下，马氏链的极限分布又是平稳分布，意即若用作为链的初始分布，即p(0)=，则链在任一时刻n的分布p(n)永远与一致.因为 例1: 试说明例2中，带有两个反射壁的随机游动是遍历的，并求其极限分布 解: 为简便，以符号“×”代表转移概率矩阵的正元素于是，由例2中的一步转移概率矩阵P，得 即P(4)无零元由定理，链是遍历的再根据定理，极限分布 满足的方程组 先由前四个方程，解得 31=2=3=4=35. 将它们代入归一条件，即最后一个方程，解之得唯一解： 1=5=1/11, 2=3=4=3/11 所以极限分布为 =(1/11, 3/11, 3/11, 3/11, 1/11). 例2 设一马氏链的一步转移概率矩阵为 试讨论它的遍历性。
解: 先算得 进一步可验证：当n为奇数时，P(n)=P(1)=P； n为偶数时，P(n)＝P(2) 这表明对任一固定的 j(=1,2,3,4)，极限 都不存在按定义，此链不具遍历性。