随机过程讲义2013 - 图文

随机过程讲议

V1.0

2012年10月22日

随机过程讲义

目录

绪 论 ....................................................................................................................................................... 1 第一章 随机数及其应用 ........................................................................................................................... 2 第一节 随机数的生成 ................................................................................................................................. 2 第二节 生物信息学中的随机策略 ............................................................................................................. 8 第二章 随机过程的概念与基本类型 ..................................................................................................... 11 第一节 第二节 第三节 第四节 第五节

随机过程的基本概念 ................................................................................................................. 11 随机过程的分布律和数字特征 ................................................................................................. 12 几种重要的随机过程 ................................................................................................................. 17 泊松过程 ..................................................................................................................................... 21 布朗运动 ..................................................................................................................................... 28

第三章 马尔可夫链 ................................................................................................................................. 31 第一节 第二节 第三节 第四节

马尔可夫链的概念 ..................................................................................................................... 31 马尔可夫链的性质 ..................................................................................................................... 36 马尔可夫链的生物信息学应用—PAM打分矩阵 ...................................................................... 41 马尔可夫链的生物信息学应用—判断CPG岛 ......................................................................... 50

第四章 隐马尔可夫模型（HMM） ........................................................................................................... 54 第一节 隐马尔可夫模型的基本概念 ..................................................................................................... 54 第二节 隐马尔可夫模型中的三个基本问题 ......................................................................................... 57 第三节 隐马尔可夫模型的生物信息学应用—CPG岛识别 .................................................................. 65

随机过程讲义

绪 论

在实际的数据分析过程中，尽管横截面的数据可以反映一定的规律性，可以解释一

些现象，但大多数情况下数据都是动态的，因为我们生活在时间的维度里。

因此为了更深入的了解随机现象，我们有必要引入时间的维度，开始研究随机过程。 随机过程是一门研究随机变量怎样随着时间参数而变化的一门科学。 注：（1）通常时间参数我们使用t。

（2）我们往往将随机过程分解为一族随机变量进行研究。 随机过程的作用：

随机过程有着十分重要的作用，它通过对过去数据的统计分析，发现一些规律；再通过现在的状态，进而预测将来的情况。

例如：天气预报、股票预测、微博点击量、服务器接收手机发的短信数、等等 随机过程在生物信息学中的应用：

随机过程在生物信息学中起着十分重要的作用，各个领域的经典算法不可避免的用到随机过程。其中比较重要的两个方面是马尔可夫链蒙特卡罗方法（MCMC）和隐马尔可夫模型。

例如：序列比对、蛋白结构预测、甲基化位点鉴别、模式分类、进化树、基因调控网络、拷贝数变异预测、药物靶点预测。 概率初步

具体内容参见 《概率论与数理统计》 和 《多元统计分析》

1

随机过程讲义

第一章 随机数及其应用

第一节 随机数的生成

随机数：随机变量的样本称为随机数。由于在统计上常用的是独立样本，因此不放假

设随机数之间是独立的。生成随机数的方法称为随机数的取样法，英文sampling。

随机数在生物信息学中占有十分重要的地位，例如随机扰动网络、构建背景分布，多重检验校正中的permutation方法等等。一般在下一些结论的时候一个基本的逻辑是：看某种现象是不是随机的，如果不是随机的那么认为有一定的生物学意义，也正是我们要获得的结果。所有的这些过程都离不开随机数的使用。 1、产生随机数的一般方法介绍：

（1）手工法：是最早产生随机数的方法为即采用投掷骰子、摇号、抽签、摸球等办法，目前的彩票发行仍然采用此法。

（2）随机数表：随着一些随机模拟算法的发展，如蒙特卡罗方法（Monte-Carlo）等，需要大规模的随机数，这时手工已经不能满足计算的需要。1927年，Tippett制造了4万个随机数的表；1939年Kedell等用高速转盘生成了10万个随机数的表；后来兰德公司又用电子装置产生了100万个随机数。在计算机产生之前人民就利用这些方法产生的随机数进行统计计算。

（3）计算机存储法：在计算机发展的初期，人们只是扩展了随机数表法的简单应用，将随机数表刻在磁盘上，使用的时候将随机数调入内存，由于该方法存储随机数要占用较大的空间，随机数的长度也有限，目前已经很少用了。

（4）计算机物理法：在计算机上安装一台物理随机数发生器，将物理过程转成随机数。优点：得到的是真正的随机数，随机性和均匀性都很好，取之不尽用之不竭；缺点：有些学者做实验需要重复验证，物理法产生的随机数无法再产生一次相同的，另外随机数发生器需要经常检查和维修，因此这种方法也逐渐被取代。

（5）计算机数学法：使用数学算法，借助计算机来产生随机数。是目前使用最广、发展最快的方法。特点是占用内存少、速度快、可以生产两次相同的随机数便于重复性研究。 2、伪随机数 使用计算机，利用数学方法生成的随机数具体指的是按照一定的算法产生的数列，他们具有类似于随机变量的独立抽样序列的性质。但是由于这些数是由算法产生的，因而不可能是真正的随机数，我们通常把用数学方法产生的随机数称为伪随机数。正是由于伪随机数具有和真正的随机数相同的性质（如独立性等），我们就把伪随机数作为真正的随机数来使用。

伪随机数列：实际产生伪随机数的时候，往往利用某一递推xn?f(xn?1,xn?2,?,xn?k)产生数列x1,x2,?,xn，当n充分大时，这一数列具有独立抽样序列的性质，我们成为伪随机数列。 随机种子：递推公式中的初值，我们称为随机种子。一旦随机种子确定，随机序列便可以确定。

3、随机数基本定理（要求掌握证明）

（1） 分布F(x)的随机数：设随机变量?~F(x)，我们称?的随机抽样序列{?i}为分布F(x)2

随机过程讲义

的随机数。

例：若?~N(?,?2)，则称{?i}为正态分布随机数。 若?~均匀分布，则称{?i}为均匀随机数。 若?~?2，则称{?i}为卡方分布随机数。 （2） 随机数基本定理：

定理：设F(x)为连续且严格单调递增的分布函数，它的反函数存在，记为F?1(x)，即

F(F?1(x))?x，记U(0,1)为均匀随机数。

1）若?的分布函数为F(x)，则F(?)~U(0,1)。 2）若?~U(0,1)，则F?1(?)的分布为F(x)。 证明：

1）设F(?)的分布函数为G(x)，当x?[0,1]时；

G(x)?P(F(?)?x)?P(??F?1(x))?F(F?1(x))?x 即：分布函数是一条直线，密度函数始终为1。

且x?0时G(x)?0，x?1时，G(x)?1 故F(?)~U(0,1) 2）F?1(?)的分布为： P(F?1(?)?x)?P(??F(x))

由于?~U(0,1)，因此，P(??x)?x；这样，我们得到P(??F(x))?F(x)。

即：P(F(?)?x)?P(??F(x))?F(x)

?1证毕。

（3） 随机数基本定理的R语言代码演示： 1)正态分布->均匀分布

>x=rnorm(100000,0,1) #产生100000个均值为0，方差为1的正态随机数 >hist(x,freq=FALSE) #画出x的分布图 >z=pnorm(x) #分布函数作用于x

>hist(z,freq=FALSE) #画出z的分布图分布图 结果图：

3

随机过程讲义

（a） (b)

左图为?的分布，右图为F(x)的分布，我们可以看出F(?)~U(0,1)。 2）卡方分布->均匀分布

>x=rchisq(100000,7) #产生100000个卡方分布随机数 >hist(x,freq=FALSE) #画出x的分布图 >z=pchisq(x,7) #分布函数作用于x

>hist(z,freq=FALSE) #画出z的分布图分布图 结果图：

（a） (b)

左图为?的分布，右图为F(x)的分布，我们可以看出F(?)~U(0,1)。 3）指数分布->均匀分布

>x=rexp(100000,5) #产生100000个指数分布随机数 >hist(x,freq=FALSE) #画出x的分布图 >z=pexp(x,5) #分布函数作用于x

>hist(z,freq=FALSE) #画出z的分布图 分布图:

4

随机过程讲义

（a） (b)

左图为?的分布，右图为F(x)的分布，我们可以看出F(?)~U(0,1)。 4)均匀分布->正态、卡方、指数分布

>x=runif(10000) #产生均匀分布，甚至均匀序列x=seq(0,1,0.0001) >hist(x,freq=FALSE) #画出z的分布图分布图 >z1=qnorm(x,100,8) #正态分布的反函数 >hist(z1,freq=FALSE) #画出z的分布图分布图 >z2=qchisq(x,7) #卡方分布的反函数

>hist(z2,freq=FALSE) #画出z的分布图分布图 >z3=qexp(x,7) #指数分布的反函数

>hist(z3,freq=FALSE) #画出z的分布图分布图

（a） (b)

5

随机过程讲义

（c） (d) 我们可以看出，均匀分布序列通过其某种分布的反函数的运算可以得到该分布的序列。因此，其他分布可以由均匀分布来构建，均匀分布是随机数产生的基础。下面我们将绍均匀分布随机数的产生策略。 （4） 均匀随机数的产生：

均匀随机数产生有很多种方法，其中最普遍用于产生均匀随机数的方法是同余法。 求余运算记为A(modM)，定义如下：

AA?M?A?A A(modM)?A?[]?M??A?[]?MA?MM?M?A其中[]表示取整运算。

M同余法的一般递推公式如下： ?yn?(kyn?1?b)(modM)?yxn?n(n?1,2,3,?) ?M?y0初值?其中K,b,y0,M的选取对生成随机数十分关键，如果数值偏小，生成序列可能重复出现，

也就是产生的数列会有周期性。一个理想的随机序列一般来说需要非常长的周期。几个典

型的例子如下：

?yn?513yn?1(mod236)?yn?xn?36(n?1,2,3,?) 1）?2?y0?1初值??其周期约为2?10。

106

随机过程讲义

?yn?517yn?1(mod242)?yn?xn?42(n?1,2,3,?) 2）?2?y0?1初值??其周期约为10。

12R语言的实现代码

对于1）我们也给出其R语言的实现代码：

##构建生成随机数函数myrandom，两个参数myseed为种子y0的初值、num为要产生多少个随机数。

myrandom<-function(myseed,num){ y=myseed x=c()

for(i in 1:(num+1)){

y[i+1]=(5^13*y[i])%%(2^36) if(i>1){x[i-1]=y[i]/2^36} }

return(x) }

data<-myrandom(1,10000) #产生10000个均匀随机数 hist(data,freq=FALSE) #查看分布图

从图中，我们可以看出，所产生的随机数是均匀分布。

有了均匀随机数，我们就可以利用反函数法构建其他任何分布的随机数以便于我们分析。另外其他分布的随机数也后单独的生成方式，如正态随机数生成的Box-Muller方法等，在这里就不一一介绍。目前随机数的产生策略也在有研究者不断的开发。 4、实际数据分析中的一些随机数函数

前面介绍的的随机数生成的一些基本原理是为了对随机数更深入的理解，在实际应用中一些统计分析软件都有对特定分布随机数的生成函数，我们仅就R语言中随机数的生成函数做介绍。

R语言的几个重要分布的随机数生成函数

7

随机过程讲义

表：R语言中常用分布的随机数生成函数

分布类型

Gaussian (normal) exponential gamma Poisson Weibull Cauchy beta

The Student t Distribution F Distribution

Pearson Chi-Squared Distribution binomial multinomial geometric

hypergeometric logistic lognormal

negative binomial uniform

Wilcoxon Signed Rank Statistic Wilcoxon Rank Sum Statistic

R函数

rnorm(n, mean=0, sd=1) rexp(n, rate=1)

rgamma(n, shape, scale=1) rpois(n, lambda)

rweibull(n, shape, scale=1) rcauchy(n, location=0, scale=1) rbeta(n, shape1, shape2) rt(n, df)

rf(n, df1, df2) rchisq(n, df)

rbinom(n, size, prob) rmultinom(n, size, prob) rgeom(n, prob) rhyper(nn, m, n, k)

rlogis(n, location=0, scale=1) rlnorm(n, meanlog=0, sdlog=1) rnbinom(n, size, prob) runif(n, min=0, max=1) rsignrank(nn, n) rwilcox(nn, m, n),

从上表中我们可以看出R语言中的随机数生成函数都是以r开头的，代表random。同样的其他语言如Matlab中也有类似情况，例如Matlab中正态随机数生成函数为normrnd()，将rnd作为函数的结尾，用法与R语言中类似，就不详细介绍，使用可以自行查阅。

第二节 生物信息学中的随机策略

一、 分配概率

在产生随机数的使用过程中，常需要按照某一概率完成某项任务，这个概率称为分配概率。例如，临床试验中常采用分配概率对病人进行分组。

?x1?xn?定理：设随机变量?只取有限个值，其分布为?~??p?p??。把[0,1]区间分成n个

n??1不相交的子区间，使得第i个区间Ji的长度为pi。任取一个随机数U，则如果U落入到Ji里，我们取??xi，则这时生成的随机数列，是一个?随机数。

这一定理可以指导我们可以利用分割区间，然后用产生均匀随机数的策略来获得分配

概率。

例：临床试验中为了检验用药的效果分成两组，测试组和对照组，现对于一个样本，我们要求按照0.6的概率将该样本分到测试组。

8

随机过程讲义

具体操作如下：

（1） 产生1-100范围内的一个随机数 （2） 判断是否<=60

（3） 分配：若<=60则分配到测试组，否则分配到对照组

R语言代码：

assign_sample<-function(p){ x=sample(1:100,1) marker=c() if(x<=p*100){ marker='case' }else{

marker='control' }

return(marker) }

sample_100=sapply(1:100,function(x){assign_sample(0.6)}) sample_100

二、 Permutation

在生物信息学分析中，经常使用的一个策略就是permutation。

Permutation主要的目的是为了确定某一现象是否存在，也就是说确定某一现象是否为非随机，如果非随机则确定这一现象是存在的。

Shuffle(扰动)，又称洗牌，是指打乱样本的顺序。R语言中可以用sample()函数实现。 1、Permutation确定统计显著性：

确定统计显著性是permutation的一个比较重要的应用，我们以具体实例来给出permutation确定统计显著性的策略。

假定人类KEGG通路数据库中共有M?5000个基因，有K（假设200）个通路，每个通路mk（k?1,2,?,K）个基因，该数据库中有某种疾病相关基因D（假设100）个，我们如何设计permutation程序来鉴别该疾病相关通路。

具体过程如下：

1）计算200个通路中每个通路内疾病基因数目，第k个通路内的疾病基因数目记为

dk。

2）保证通路内基因不变，随机扰动疾病-基因标签，将疾病标签随机的分配给任意的基因（可以将基因贴上0,1标签，例如疾病基因为1，其余基因为0，然后shuffle随机扰动）。

3）重新计算通路内疾病基因个数

4）整个过程重复N次（如N=1000或更大）。

5）对每个通路，计算真实疾病基因数目，构建随机背景，在随机背景中的位置，并转换成百分数。

这样就计算出了每个通路在各自背景中的p值。

类似的应用很多，还可以对每个基因付值，如表达值、某种得分等等，然后通过

9

随机过程讲义

permutation的策略鉴别出比随机背景偏高或者偏低的通路。

2、Permutation多重检验校正：

Westfall and Young permutation等提出permutation的方法对分析产生的p值进行多重检验校正。以基因表达谱为例。

该方法的具体步骤如下：

1）对每个基因利用原始病例组和对照组数据，计算每个差异表达p值 2）然后扰动样本标签（shuffle），保证病例组和对照组样本数目不变。 3）对所有重新扰动后的数据，重新计算每个基因p值。 4）整个过程重复N次（如N=1000或更大）。

5）对于某个基因，将获得的N个随机p值进行排序，通过计算真实p值在随机p值中的位置百分数，选取一定的阈值（如0.05），挑选那些校正后的p值小于阈值的基因。

缺点：基因数目和样本数目比较多的时候，速度可能会比较慢。

10

随机过程讲义

第二章 随机过程的概念与基本类型

第一节 随机过程的基本概念

在初等概率论中，我们主要讨论的是一个或有限个随机变量。在实际的科学研究中，我们往往不只关注于单个变量，而是研究依赖于时间的一簇随机变量的情况，进而理解随机现象的全部统计规律性，我们称这样的随机变量簇为随机过程。

下面，我们通过几个实例来进一步理解随机过程： 例1.癌细胞增长问题。假定研究癌细胞的数目变化，以Xt表示在t时刻癌细胞的个数，则对于每一个t，Xt是一个随机变量。假定我们从t=0时刻起，每天对癌细胞的数目观察一次，则{Xt,t?0,1,?}是一个随机过程。

例2. 电话交换机在时间[0,t]内接到的呼唤次数是一个与t有关的随机变量Xt，对于固定的t，Xt是一个取固定整数的随机变量，而{Xt,t?[0,??)}是一个随机过程。

例3．天气预报问题。若以Xt代表某地区第t次统计所得到的最高天气气温，则Xt是随机变量。为了预测该地区未来的气温，我们必须研究随机过程{Xt,t?0,1,?}的规律。

随机过程的定义：

在概率空间中，假定T是给定的参数集合，若对每个t?T，我们有一个随机变量Xt与之相对应，我们称随机变量簇{Xt,t?[0,?)}是一个随机过程。

注：

（1）t一般指时间。t也可以指其他，当t是一个向量时，我们称为随机场。本门课程中，t仅代表时间。

（2其他记法：还可以记为{X(t),t?[0,?)}、{xt,t?[0,?)}或{x(t),t?[0,?)} 随机过程的理解：

（1）当Xt和t都是固定值—>一个确定值 （2）Xt是变量，t都是固定值—>一个随机变量 （3）Xt固定值，t是变量—>一个确定的时间函数 （4）Xt和t都是变量—>一个时间函数族。

11

随机过程讲义

随机过程的轨道：

当Xt在每个时间点都取得某一个固定值时，我们Xt在每个时间点都为一个随机变量，

称为随机过程{Xt,t?[0,?)}的一个轨道，或者称为样本函数。随机过程的示意图都是实现，真正的随机过程是画不出来的。

例如，

（1）同学们每天可以选择去食堂1、2、3、4楼的某一层吃午饭，则一个月内吃午饭去哪层楼这件事情就是一个随机过程，某一个人一个月内吃午饭的楼层，就是一个轨道（如第一天去2楼，第二天去4楼…）。而今天中午（也就是t固定）去几楼吃饭，这就是个随机事件。

（2）再例如，人生就是个随机过程，每个人的人生都是这个随机过程中的一个轨道。比如某一天考研报志愿了，这一天（也就是t固定）你有很多种选择，这就是个随机事件。 （3）再例如，天气晴天、阴天、下雨就是一个随机过程，而某个月内的天气预报记录就是一个轨道。

（4）再例如，股票的走势图。

我们每天生活在流逝的时间里，随机过程和我们生活息息相关。我们需要做的事情是找到这些随机过程的规律，以便对整个现象有所认识，理解过去，认识现在，展望未来。例如天气预报是随机过程的一个重要的应用，它将预测明天是否会有雨。 图例：

随机过程分类：

若随机过程按照时间是连续或离散的分类，可分为两类：

（1） 若T是有限集或可列集合时，则称为离散参数的随机过程或随机序列（时间序列分

析）。

（2） 若T是有限或者是无限区间时，则称连续参数随机过程。

若随机过程按任意时刻的状态时连续性随机变量或离散型随机变量，分为两类： （1） 若对任意的时间点t，Xt都是离散型随机变量，则称为离散型随机过程。 （2） 若对任意的时间点t，Xt都是连续型随机变量，则称为连续型随机过程。 下面，我们将介绍一些重要的随机过程及其相应的性质。

第二节 随机过程的分布律和数字特征

分布和数字特征（如均值、方差等）是随机变量研究中比较重要的内容。在随机过程中分布和数字特征也仍然十分重要。 （1）随机过程的分布：

由于随机过程可以视为一簇随机变量，因此我们采用有限维分布函数族来刻画随机过程的统计规律。

12

随机过程讲义

定义：设{Xt,t?T}是一个随机过程，对任意的t1,t2,?,tn?T，随机向量(Xt1,Xt2,?,Xtn)的联合分布函数为：

Ft1,t2,?,tn(x1,x2,?,xn)?P{Xt1?x1,Xt2?x2,?,Xtn?xn} 这些分布函数的全体：

F?{Ft1,t2,?,tn(x1,x2,?,xn):t1,t2,?,tn?T,n?1} 称为有限维分布函数族 （2）随机过程的数字特征： 均值函数和方差函数：

定义：设{Xt,t?T}是一个随机过程，如果对任意t?T，EXt存在，则称函数

mX(t)?EXt,t?T

为{Xt,t?T}的均值函数。

均值函数示意图

若对任意t?T，EXt存在，则称{Xt,t?T}为二阶矩过程。称 DX(t)?E(Xt?mX(t))2,2t?T

为方差函数。

相关函数：

均值函数和方差函数只描述了随机过程在某个特定时刻的统计特性，并不能表示随机过程在两个不同时刻状态之间的关系。例如，下图中，两个随机过程Xt?X(t)和Yt?Y(t)大致具有相同的均值函数（趋势相似）和方差函数（宽窄相似）。但是这两个过程有明显的区别，任取两个时刻，状态之间的相关性较弱；Xt?X(t)Yt?Y(t)随时间t变化要剧烈一些，随时间t变化要缓慢一些，任取两个时刻，状态之间的相关性较强。因此只用均值函数和方差函数是不能反映出这些特征的。为此，我们引入一个能反映两个不同时刻状态相关程度的数字特征—相关函数。

13

随机过程讲义

相关函数： 我们称RX(s,t)?E(XsXt),t?T 为相关函数。以t轴为中心。

s,t?T

协方差函数：称BX(s,t)?E(Xs?mX(s))(Xt?mX(t)),为{Xt,t?T}的协方差函数。均值函数为中心。 相关函数和协方差函数之间的关系：

BX(s,t)?E(Xs?mX(s))(Xt?mX(t))?E(XsXt)?mX(s)mX(t)?RX(XsXt)?mX(s)mX(t)

即：BX(s,t)?RX(s,t)?mX(s)mX(t)

当均值函数为t轴，也就是mX(s)?mX(t)?0，我们有：

BX(s,t)?RX(s,t)

区分：均值函数、方差函数、相关函数、协方差函数

（1）均值函数mX(t)反应的是随机过程{Xt,t?T}在t时刻的平均值（反映整体趋势）； （2）方差函数DX(t)反应的是随机过程{Xt,t?T}在t时刻偏离均值mX(t)的程度（反映宽窄）。

（3）协方差函数BX(s,t)和相关函数RX(s,t)反应的是随机过程{Xt,t?T}在s和t时刻的线性相关程度，前者中心为均值函数，后者中心为t轴。显然，自协方差函数和自相关函数描述的特性基本相同（反映波动性）。 例题1：假设随机过程 Xt?Ycos(?t)?Zsin(?t),t?0

其中，Y和Z是相互独立的随机变量，且EY?EZ?0，DY?DZ??2，求{Xt,t?T}的均值函数mX(t)和协方差函数BX(s,t)。

14

随机过程讲义

解：mX(t)?EXt?E[Ycos(?t)?Zsin(?t)]?cos(?t)EY?sin(?t)EZ?0 由于均值为0，所以

BX(s,t)?RX(s,t)?E(XsXt)

?E[Ycos(?s)?Zsin(?s)][Ycos(?t)?Zsin(?t)]?E[Y2cos(?s)cos(?t)?YZcos(?s)sin(?t)?YZsin(?s)cos(?t)?Z2sin(?s)sin(?t)]由于Y于Z独立，则不存在线性关系，即E(YZ)?0 故原式等于

?cos(?s)cos(?t)EY2?sin(?s)sin(?t)EZ2??cos[(t?s)?]R语言实现：

Y=rnorm(100,0,1); Z=rnorm(100,0,1); t=seq(1:1000) theta=pi/6;

X=Y*cos(theta*t)+Z*sin(theta*t) plot(t,X,type=\图：

2

15

随机过程讲义

例题2：假设，盒子中有2个红球，3个白球，每次有放回取出一个球，定义随机过程如下：

?2t,第t次取出的是红球，t取正整数1,2…。 Xt???t,第t次取出的是白球求：（1）Xt的一维分布族{F(t,x):t?1}

（2）Xt的二维分布族{F(1,2,x1,x2) 解：（1）将区间分割成(??,t)?[t,2t)?[2t,??)

x?t?0,?3F(t,x)?P(Xt?x)??,t?x?2t

?5x?2t?1,

（2）有于不同时刻取球是相互独立的，因此

F(1,2,x1,x2)?P(X1?x1,X2?x2)?P(X1?x1)P(X2?x2)x1?1或x2?2?0?31?x1?2且x2?4?5? ,?3??x1?2且2?x2?4?5?91?x?2且2?x?412?25?x1?2,x2?4?1互协方差函数： 更进一步扩展，在实际的分析过程中，我们有时候需要考虑两个随机过程之间的关系，这时我们采用互协方差函数来表示。

定义：假定{Xt,t?T}，{Yt,t?T}是两个二阶矩过程，则称：

BXY(s,t)?E(Xs?mX(s))(Yt?mY(t)),s,t?T

为{Xt,t?T}与{Yt,t?T}的互协方差函数。称 RXY(s,t)?E(XsYt)

为{Xt,t?T}与{Yt,t?T}的互相关函数。

它们反应的是随机过程{Xt,t?T}在s时刻与{Yt,t?T}在t时刻的线性相关程度，前者中心为均值，后者中心为原点。

16

随机过程讲义

第三节 几种重要的随机过程

1、独立增量过程

设{Xt,t?T}是一个随机过程，若对任意的正整数n和t1,t2,?,tn?T，随机变量Xt1，

Xt2?Xt1，Xt3?Xt2，… ，Xtn?Xtn?1是相互独立的，则称{Xt,t?T}是独立增量过程。 注：

（1）几何意义：独立增量过程在任何一组两两不相交区间上，其增量都相互独立的，又称为可加过程。后面要介绍的泊松过程和布朗运动都是它的特例。

（2）独立增量过程的特点是：在任意的一个时间间隔上过程状态的改变，不影响任何一个与它不相重叠的时间间隔上状态的改变。

例：同学早晨穿跑步鞋跑步，一直跑到坏为止，再换新鞋。假定鞋的使用寿命是个随机变量，设Nt是在0~t时间内更换鞋的数目，Nt是一个随机过程，这可以认为是独立增量过程。比如今年跑坏3双鞋，对后年跑坏几双鞋没有任何影响。

2、平稳过程

严平稳过程：设{Xt,t?T}是一个随机过程，对任意的常数?t，正整数n，若

{Xt1,Xt2,?,Xtn}与{Xt1??t,Xt2??t,?,Xtn??t}具有相同的分布，我们称{Xt,t?T}为严平稳过程，也称狭义平稳过程。

在实际的分析中，严平稳的条件一般很难达到，因为它要求对任意的n都有：

{Xt1,Xt2,?,Xtn}与{Xt1??t,Xt2??t,?,Xtn??t}同分布。我们一般使用另一种平稳过程—宽平稳过程。

宽平稳过程：假定设{Xt,t?T}是一个随机过程，如果满足： （1）{Xt,t?T}的二阶矩存在。

（2）对任意的t?T，{Xt,t?T}的数学期望为常数，即mX(t)?E(Xt)?常数。 （3）对任意的s,t?T，自相关函数RX(s,t)?E(XsXt)?RX(t?s)，即只与?t?t?s有关。

此时称{Xt,t?T}是一个宽平稳过程，或称为广义平稳过程。

以后再无特殊说明是，平稳过程均指宽平稳过程。 宽平稳过程与严平稳过程的关系：

（1） 宽平稳过程不一定是严平稳过程，严平稳过程也不一定是宽平稳过程。 前者因为，严平稳过程二阶矩不一定存在；后者因为即使二阶矩存在，并且不随时间推移而改变，也很难保证有穷维的分布不随时间而改变。 （2） 在二阶矩存在的情况下，严平稳过程一定为宽平稳过程。

17

随机过程讲义

（3） 对于正态过程，二者等价。

注：

（1）平稳过程是同分布，而不是变分布。这时,增量X(t)-X(s)的分布函数实际上只依赖于时间差?t?t?s (0≤s

（2）几何意义：给每个时间间隔，有一个公共的时间平移，它的分布不变。

（3）由宽平稳定义的第三条可以看出，自相关函数是?t?t?s的函数，表达的意思是只要时间间隔不变，随机过程的波动性不变。

总结平稳过程：我们研究的平稳过程是这样的一种过程：均值函数常数（整体趋势不变）、方差有限（过程范围一定）、自相关函数只与?t有关（时间间隔一定时，平移波动性不变）。 例：设随机过程： Xt?Ycos(?t)?Zsin(?t),t?0

其中，Y和Z是相互独立的随机变量，且EY?EZ?0，DY?DZ??2 证明Xt为宽平稳过程。

证明：mX(t)?EXt?E[Ycos(?t)?Zsin(?t)]?cos(?t)EY?sin(?t)EZ?0 由于均值为0，所以

BX(s,t)?RX(s,t)?E(XsXt)

?E[Ycos(?s)?Zsin(?s)][Ycos(?t)?Zsin(?t)]?E[Y2cos(?s)cos(?t)?YZcos(?s)sin(?t)?YZsin(?s)cos(?t)?Z2sin(?s)sin(?t)]由于Y于Z独立，则不存在线性关系，即E(YZ)?0 故原式等于

?cos(?s)cos(?t)EY2?sin(?s)sin(?t)EZ2??cos[(t?s)?]2

由于均值函数mX(t)?0，且相关函数BX(s,t)??2cos[(t?s)?]只与?t?t?s有关，因此

Xt为宽平稳过程。 R语言实现：

Y=rnorm(100,0,1); Z=rnorm(100,0,1); t=seq(1:1000) theta=pi/6;

18

随机过程讲义

X=Y*cos(theta*t)+Z*sin(theta*t) plot(t,X,type=\图：运行三次程序

100个或1000个平稳过程放在同一张图中： Y=rnorm(100,0,1);

19

随机过程讲义

Z=rnorm(100,0,1); t=seq(1:1000) theta=pi/6;

X=Y*cos(theta*t)+Z*sin(theta*t) plot(t,X,type=\

for(i in 1:100){ #可以改成1000 Y=rnorm(100,0,1); Z=rnorm(100,0,1); t=seq(1:1000) theta=pi/6;

X=Y*cos(theta*t)+Z*sin(theta*t) lines(t,X) }

图：

我们可以看出，均值函数是常数0。

平稳增量过程：在任何一段长度为?t的时间区间内， 增量Xt??t?Xt的分布只与?t有关，而与?t所处的位置（或与起始时刻t）无关。

时齐过程：对于一个独立增量过程，当具有平稳增量性时，称相应的独立增量过程是齐次的或时齐的.

注意区分平稳过程、平稳增量过程、时齐过程： 平稳过程：均值函数常数（整体趋势不变）、方差有限（过程范围一定）、自相关函数只与?t有关（时间间隔一定时，平移波动性不变）。

平稳增量过程：{Xt,t?T}是一个随机过程，其增量Xt??t?Xt的分布只与?t有关。 时齐过程：独立增量过程+平稳增量过程=时齐过程

增量平稳过程和时齐过程未必是平稳过程。

齐次的应用的非常多，齐次的意味可以平移，有足够的数学工具可以研究，可以将其平移到原点，研究其在原点附近的性质。只要长度一样，概率特性保持不变，可以平移。

20

随机过程讲义

3、马尔可夫（Markov）过程

定义：设{Xt,t?T}是一个随机过程，若对任意的正整数n和t1,t2,?,tn?2,tn?1,tn?T，满足条件分布：

P(Xtn?xn|Xt1?x1,Xt2?x2,?,Xtn?1\\?xn?1)?P(Xtn?xn|Xtn?1\\?xn?1) 则称{Xt,t?T}为马尔可夫过程。 上式称为马尔可夫性，或称为无后效性。 注：

（1）我们将时间点进行划分，将tn?1看做是当前时间点，则t1,t2,?,tn?2为过去时间点，tn可

以看做将来的时间点。Xti?xi表示系统在时刻ti的时候处于状态xi。

（2）P(Xtn?xn|Xt1?x1,Xt2?x2,?,Xtn?1\\?xn?1)?P(Xtn?xn|Xtn?1\\?xn?1)表示系统将来的状态与过去所处的状态无关，只与现状的状态有关。换句话说，只要已知系统现在的状态，则系统未来所处的状态的概率就已经已知，不管系统是如何到达现在的状态的。 例如：不管昨天在做什么，前天在做什么，只要今天走进课堂，将会有一定的概率来学习这门随机过程。

后面我们还会详细的介绍马尔科夫过程。

接下来，我们介绍两个重要的随机过程，布朗运动和泊松过程，这两个过程的理论体系研究已经十分完善，可以说是随机过程的两大基石。

第四节 泊松过程

预备知识-泊松分布：

Poisson分布是一种描述小概率事件出现规律性的一种重要的离散型分布。 如：某段时间特定人群中某种恶性肿瘤患者的分布或出生缺陷的发病情况， 设随机变量X所有可能取的值为0 , 1 , 2 , … , 且概率分布为：

P(X?n)?e???nn!,n?0,1,2,??, 其中?是常数,则称 X 服从参数为?的泊松分布,记作X~P(?).

21

随机过程讲义

泊松分布是作为二项分布的近似，于1837年由法国数学家泊松引入的。

limCp(1?pn)n??knknn?k?e???kk!,k?0,1,2,??,

泊松分布的均值和方差：E(X)?D(X)??

泊松过程是一类时间连续、状态离散的随机过程。在许多方面都有着广泛的应用。 计数过程：

设Nt表示到时刻t为止，已发生的事件的总数，若Nt满足下列条件：

（1）Nt?0； （2）Nt是正整数； （3）若s

（4）当s

我们称随机过程Nt为计数过程。

计数过程比较常见，日常生活中很多问题都是计数问题。

独立增量的计数过程：如果计数过程Nt在不相重叠的时间内，事件发生的次数是相互独立的，我们称Nt是独立增量计数过程。

或描述为：当t1?t2?t3?t4，若在(t1,t2]内事件发生的次数Nt?Nt1与在(t3,t4]内事件发生的次数

2Nt?Nt3是相互独立的，我们称该计数过程是一个独立增量计数过程。

4平稳增量的计数过程：

22

随机过程讲义

在任何一段长度为?t的时间区间内，事件发生的次数Nt??t?Nt只与?t有关，而与?t所处的位置（或与起始时刻t）无关。

泊松过程： 定义：

设计数过程{Xt,t?T}满足下列条件：

（1）X0?0；

（2）Xt是独立平稳增量过程（时齐的）；

（3）Xt满足下列条件：

?P(Xt?h?Xt?1)??h?o(h) ??P(Xt?h?Xt?2)?o(h)则称计数过程{Xt,t?T}为具有参数?的泊松过程（时齐的泊松过程）。

注：条件（3）中所描述的意义为：在如果时间区间充分小，事件最多发生一次，而不能有两个或两个以上的事件同时发生。 例如：

电话交换台在某段时间接到的呼唤。令{Xt,t?T}表示电话交换机在[0,t]时间内接收到呼唤的次数，则{Xt,t?T}满足条件（3），{Xt,t?T}是一个泊松过程。

到火车站售票口前买票的旅客，若记{Xt,t?T}为在时间[0,t]内到达售票口的旅客数目，则{Xt,t?T}是一个泊松过程。

机枪发射子弹，若记{Xt,t?T}为在时间[0,t]内到发射子弹的数目，则{Xt,t?T}是一个泊松过程。

通过上述定义，我们可以推导出泊松过程的另一数学描述（具体推导过程见参考书，我们在这里不加以详述）。

定义：

设计数过程{Xt,t?T}满足下列条件：

（1）X0?0；

（2）Xt是独立平稳增量过程（时齐的）；

（3）在任意长度?t的区间中，时间发生的次数服从参数??t?0的泊松分布，即对任意的?t和t有：

23

随机过程讲义

P(Xt??t?Xt?n)?e???t(??t)n,k?0,1,2,??, n!则称计数过程{Xt,t?T}为具有参数?的泊松过程。

注：泊松过程不是平稳过程，是独立增量平稳的时齐过程。后面我们还将扩展到非时齐的泊松过程。

一条泊松过程轨道。

泊松过程的数字特征：

泊松过程的均值函数和方差函数：

根据泊松分布的均值和方差，我们可以得到再根据第二定义的（3），我们可以得到：

E(Xt??t?Xt)?D(Xt??t?Xt)???t

由于泊松过程是一个计数过程，初始计数为0，即X0?0，有：

E(X0??t?X0)?E(X?t)???t

E(X?t)??，表示的意思是，单位时间内时间发生的平均个数,也称?为此过程的强度?t或速率。

因此，对任意的t，令?t?t?0?t我们可以得到:

此时，

泊松过程的均值函数为：mX(t)?E(Xt)??t，

泊松过程的方差函数为：?2X(t)?D(Xt)?D(Xt?X0)??t 相关函数：

RX(s,t)?E(XsXt)?E[Xs(Xt?Xs?Xs)]

24

随机过程讲义

?E[(Xs?X0)(Xt?Xs)]?E(Xs)2

由于泊松过程是一个独立增量过程，增量独立，再根据方差的计算公式，有：

?E(Xs?X0)E(Xt?Xs)?D(Xs)?[E(Xs)]2 ??s?(t?s)??s?(?s)2??s(?t?1) 协方差函数：

BX(s,t)?RX(s,t)?mX(s)mX(t)??s(?t?1)??s?t??s 一般的，泊松过程的协方差函数可以表示为：

BX(s,t)??min(s,t)

时间间隔的分布：

在实际分析过程中，我们还对事件发生的时间间隔感兴趣，因此我们有必要讨论时间间隔的分布。

例如：泊松分布的一个经典例子是服务系统，比如排队买票和排队存钱等等，对于售票员或者银行工作人员来说，每隔多长时间受理一个客户。

假设{Xt,t?T}为具有参数?的泊松过程，令Xt表示t时刻时间A发生（顾客出现）的次数，W1,W2,?表示第一次，第二次，…，事件A发生的时间，Tn?Wn?Wn?1表示从第n-1次事件发生到第n次事件发生的时间间隔。如图：

定义：Tn?Wn?Wn?1为从第n-1次事件发生到第n次事件发生的时间间隔。

Tn也是一个随机变量，那么Tn服从什么分布呢？

我们可以利用泊松过程，研究各次事件间的时间间隔分布。

定理：设{Xt,t?T}为具有参数?的泊松过程，Tn?Wn?Wn?1是对应的时间间隔序列，则随机变量Tn均服从参数为?的指数分布（均值为 证明： 当n=1时

1?）。

FT1(t)?P{T1?t}?1?P{T1?t}

由于T1?t表示在t时刻还没有任何事件发生。因此：

P{T1?t}?P{Xt?X0?0}?e??t

25

随机过程讲义

故

FT1(t)?1?P{T1?t}?1?e??t 服从参数?的指数分布。 当n=2时

FT2(t)?P{T2?t|T1?s}?1?P{T2?t|T1?s} 由于泊松过程是一个独立平稳增量过程，也就是说

P{T2?t|T1?s}?P{在(s,s?t]内没有事件发生|T1?s} ?P{在(s,s?t]内没有事件发生}

?P{Xt?s?Xs?0}

由于平稳、增量独立，可以将其平移到原点

?P{Xt?X0?0}?e??t 因此，

FT2(t)?P{T2?t}?1?P{T2?t}?1?e??t 同理：

FTn(t)?P{Tn?t}?1?e??t 注：

??e??t（1）概率密度函数为：fTn(t)???0t?0 t?0（2）这个结论是在平稳独立增量过程的假设下得到的，其概率意义是指在泊松分布在过程的任意时刻都从头开始，即从任何时刻起过程独立于先前已发生的一切（独立增量），且有与原过程相同的分布（增量平稳）。

总结：泊松分布的三大性质：

增量平稳性：在任何一段长度为?t的时间区间内，出现任意数量事件的概率只与?t有关，而与?t所处的位置（或与起始时刻）无关。记λ为平稳流的强度。

无后效性（又称无记忆性或者马氏性）：在互不相交的两时间区间T1、T2内所出现的事件数是相互独立的。

普通性：在同一瞬间，多于一个顾客出现的概率（或同时到达系统有两个或两个以上顾客的概率）可忽略不计。

1定理：设{Xt,t?T} 是一个计数过程，若其时间间隔服从均值为 的指数分布，则它是强度 λ

?的泊松过程。

此定理为上面定理的逆定理。（此定理亦可以作为泊松过程的定义）这个定理提供了对泊松

26

随机过程讲义

过程进行计算机模拟的方便途径：只需产生几个不同指数分的随机数，将其作为Xn,n=1,2, …即可得到泊松过程的一条样本路径。

我们前面R语言仿真的泊松过程就是按照这种方式产生的。 等待时间的分布：

一般我们称Wn为第n次事件的等待时间（或称为第n次事件的出现时刻） Wn??Ti

i?1n例：求Wn的分布函数（即n个独立的指数分布的和的分布）及概率密度函数。 解：FWn(t)?P{Wn?t}

由于地n个事件在时刻t或之前已经发生，这与在t时刻已发生事件的数目至少是n是等价的，即：

Wn?t?Xt?n 因此，

FWn(t)?P{Wn?t}?P{Xt?n}??P{Xt?X0?j}??ej?nj?n????t(?t)j j!概率密度：

对上式求导，

fWn(t)???ej?n???tjj?1??(?t)j??t(?t)??t(?t) ????e???ej!j!(j?1)!j?nj?n????ej?n????tn?1j?1?(?t)j??t(?t)??t(?t) ??e???ej!(n?1)!j?n?1(j?1)!n?1j?(?t)j??t(?t)??t(?t) ??e???ej!(n?1)!j?n(j)!????ej?n??t??e??t(?t)n?1 (n?1)!该式又称为爱尔兰分布，是n个相互独立的指数分布的随机变量之和的概率密度。

首达时刻的条件分布：

假设随机事件在[0,t]事件内已经发生过一次，我们要确定这一事件首次到达时刻W1的分布。 解：

假定事件在s时刻首次到达，s

27

随机过程讲义

P{W1?s|Xt?X0?1}?P{W1?s,Xt?X0?1}

P{Xt?X0?1} 我们按照时间s将区间[0,t]进行分割,

P{W1?s|Xt?X0?1}?P{Xs?X0?1,Xt?Xs?0}

P{Xt?X0?1}由于是独立增量过程，因此P{Xs?X0?1,Xt?Xs?0}?P{Xs?X0?1}P{Xt?Xs?0} 于是原式等于

?P{Xs?X0?1}P{Xt?Xs?0}

P{Xt?X0?1}e?s?s?e?(t-s)[?(t-s)]0?

e?t?ts? t第五节 布朗运动

1、随机徘徊

随机徘徊是一个简单的随机过程，但是却起着十分重要的作用。我们首先介绍随机徘徊，以便更加深入的理解随机过程。 简单对称随机徘徊：

一个粒子在直线上每隔单位时间，向左或向右机会均等的走一步，每步走一个单位。若考虑第n步时粒子所在的位置，则它就是一个随机过程，称为简单对称随机徘徊。 简单对称随机徘徊的数学表达： 设X0?a为初始位置的坐标，记

?1若第n步向右走Zn??

?1若第n步向左走?则：

Xn?Xn?1?Zn?a??Zk；

k?1n我们称随机变量序列Xn?{Xn}为一个简单对称随机徘徊，此时向右走的概率p?0.5。 注：简单对称随机徘徊向左，向右、左移动的概率都为0.5。

简单随机徘徊：

粒子在直线上每隔单位时间，以概率p向右走一步或以概率q=1-p向左走一步，每次移动与其他次移动无关。若考虑第n步时粒子所在的位置，则它是一个随机过程，称为简

28

随机过程讲义

单随机徘徊。

注：简单随机徘徊是简单对称随机徘徊的扩展，即简单对称随机徘徊中向左或向右的概率

p?[0,1]。

注：简单随机徘徊具有马尔可夫性，即下一步只与当前状态有关，而与过去状态无关。

关于简单随机徘徊的一些其他性质，我们将在下一章马尔可夫链中，作为马尔科夫链的一个特例进行讲解。

2、布朗运动

作为随机徘徊的极限过程，我们介绍一下布朗运动。

1827年英国生物学家Brown在显微镜下观测页面上的花粉，发现花粉的微粒都进行着不规则的运动，但是他并不清楚这种运行的本质原因。

直到19世纪末，人们才清楚这种运动时由于花粉微粒受到大量液体分子无规则的碰撞产生的。

1923年时，维纳（Wiener）严格的给出了布朗运动的数学定义，构建了一个概率空间和其上的随机过程来刻画布朗运动，因而布朗运动也称为维纳过程。

目前，布朗运动的理论体系已经相当成熟，在自然科学的各个领域都有着十分广泛的应用，已经称为随机过程的两大基石之一。 布朗运动:

随机过程{Xt,t?0}，如果满足如下条件： （1）X0?0

（2）{Xt,t?0}有独立的平稳增量

2（3）对任意的?t和t有：Xt??t?Xt~N(0,??t)

我们称随机过程{Xt,t?0}为布朗运动，也称为维纳过程，也记为{Bt,t?0}或{Wt,t?0}。 当??1时，我们称为标准布朗运动。 数字特征：

布朗运动的均值函数和方差函数： X0?0，有：

E(X0??t?X0)?E(X?t)?0

因此，对任意的t，令?t?t?0?t我们可以得到: 布朗运动的均值函数为：mX(t)?E(Xt)?0，

布朗运动的方差函数为：?2X(t)?D(Xt)?D(Xt?X0)??2t 相关函数：

29

随机过程讲义

假定s

RX(s,t)?E(XsXt)?E[Xs(Xt?Xs?Xs)]

?E[(Xs?X0)(Xt?Xs)]?E(Xs)2

由于布朗运动是一个独立增量过程，增量独立，再根据方差的计算公式，有：

?E(Xs?X0)E(Xt?Xs)?D(Xs)?[E(Xs)]2??2s 因此，对于任意的s和t则有RX(s,t)??2min(s,t) 协方差函数：

BX(s,t)?RX(s,t)?mX(s)mX(t)??2min(s,t)

布朗运动的第二定义:

我们注意到，对于上面布朗运动定义中Xt可以理解为初始时刻为0，时间增量为t的随机过程，即布朗运动还可以定义为：

随机过程{Xt,t?0}，如果满足如下条件： （1）X0?0

（2）{Xt,t?0}有独立的平稳增量

2（3）对任意t有：Xt~N(0,?t)

我们称随机过程{Xt,t?0}为布朗运动，也称为维纳过程。 仍然有，当??1时，我们称为标准布朗运动。 另外，当??1时{Xt?,t?0}为标准布朗运动。

因此，在很多分析模型中，都采用标准布朗运动为模型进行分析。 布朗运动的一些性质： 若{Xt,t?0}是布朗运动则: （1）{?Xt,t?0}是布朗运动 （2）Xt??t?X?t是布朗运动 （3）{1?X?t,t?0}是布朗运动

30

随机过程讲义

第三章 马尔可夫链

马尔可夫过程按其状态和时间参数是连续的还是离散的，可以分为三类 （1） 时间、状态都是离散的马尔可夫过程，称为马尔可夫链；

（2） 时间连续、状态离散的马尔可夫过程，称为连续事件的马尔可夫过程； （3） 时间、状态都连续的马尔可夫过程。 本章中，我们主要关注马尔科夫链。

第一节 马尔可夫链的概念

一、马尔可夫链的定义

由于马尔可夫链的时间和状态都离散，因此我们用n=0,1,2,3…代替代表离散时刻t。 时间集合: T?{1,2,3,4,?}

状态集合： S?{S1,S2,S3,?SN},假定有N个状态。Xn的所有可能取值的总体构成状态集合：马尔可夫链的定义：

若随机过程{Xn,n?T}，对任意的n?T和任意的状态s0,s1,s2,?,sn?i,sn?1?j?S，其中sn?i，sn?1?j表示第n时刻所处的状态的为i，第n+1时刻所处的状态j，其条件概率满足：

P(Xn?1?sn?1|X0?s0,X1?s1,X2?s2,?,Xn?sn)?P(Xn?1?sn?1|Xn?sn) 我们称{Xn,n?T}为马尔可夫链，简称马氏链。

二、转移概率

条件概率P(Xn?1?sn?1|Xn?sn)的直观意义：为系统在n时刻处于状态sn的条件下，在时刻n+1所处状态为sn?1的概率。

条件概率P(Xn?1?sn?1|Xn?sn)的动态意义：随机游动的质点在时刻n 时刻处于状态sn的条件下，下一步转移到状态sn?1的概率。

注：为了后面我们对概率转移矩阵表述的方便，我们假定：sn?i，sn?1?j。

即：P(Xn?1?j|Xn?i)想对应于随机游动的质点在时刻n 时刻处于状态的i条件下，下一步转移到状态j的概率。

31

随机过程讲义

一步转移概率的定义：

我们称pij(n)?P(Xn?1?j|Xn?i)为马尔可夫链{Xn,n?T}在时刻n的一步转移概率，也称为转移概率。 平稳转移概率：

一般情况下，转移概率pij(n)与状态i、j和时刻n有关，但如果pij(n)不依赖于时刻n，我们称马尔可夫链有平稳转移概率。 齐次马尔可夫链：

对任意的状态i和j，若马尔可夫链{Xn,n?T}的转移概率pij(n)与n无关，我们称马尔可夫链{Xn,n?T}是齐次的，或时齐的，并记pij(n)为pij。

注：以后我们在讨论问题的时候，只讨论齐次马尔可夫链，如不加说明，我们提到的马尔可夫链均指齐次马尔可夫链。 一步转移概率矩阵：

假定状态空间为S?{S1,S2,S3,?SN}，由一步转移概率构成的矩阵，我们称为一步转移概率矩阵，记为：

?p11?pP??21????pN1p12p22????p1N?p2N?? ???pNN?pN2?

pij表示状态i到状态j的转移概率。 一步转移概率的性质：

（1）pij?0； （2）?pij?1

j?1N注：转移概率矩阵中的每一行之和为1，通常满足上面性质的矩阵被称为随机矩阵。 n步转移概率的定义： 我们称pij(n)?P(Xm?n?j|Xm?i)为马尔可夫链{Xn,n?T}的n步转移概率。

n步转移概率矩阵：

假定状态空间为S?{S1,S2,S3,?SN}，由n步转移概率构成的矩阵，我们称为n步转移概率矩阵，记为：

32

随机过程讲义

P(n)?p11(n)?(n)p??21???(n)??pN1p12(n)p22?(n)pN2(n)????(n)p1N?(n)?p2N? ??(n)?pNN??

(n)pij表示状态i到状态j的n步转移概率。

注：

n步转移概率矩阵中也有pij当n=1时，pij(1)(n)?0；?pijj?1N(n)?1，n步转移概率矩阵也为随机矩阵。

?pij该矩阵为一步转移矩阵。

(0)另外，我们定义pij?0i?j ???1i?j

n步转移概率矩阵的性质：

(n)假定{Xn,n?T}为马尔可夫链，假定n?0，0?l?n，对于n步转移概率pij具有如下性

质： （1）pij即

?p11(n)?(n)p??21???(n)??pN1p12(n)p22?(n)pN2(n)(n)??pikpkj(l)k?1N(n?l)；或P(n)?P(l)P(n?l)

：

P(n)????(n)(l)p1N??p11?(l)(n)?p2N??p21??????(l)(n)?pNN????pN1p12(l)p22?(l)pN2(l)????(l)(n?l)p1N??p11(l)??(n?l)p2N??p21????(l)??(n?l)pNN????pN1p12(n?l)p22?(n?l)pN2(n?l)????(n?l)?p1N(n?l)?p2N???(n?l)?pNN?? 这可以利用全概率公式推得，该式称为切普曼-克尔莫格洛夫方程，简称C-K方程。

注：该方程在马尔可夫的转移概率矩阵计算中起着十分重要的作用。 （2）上式当l?1时为，P(n)?PP(n?1)?Pn

我们可以看出，n步转移概率由一步转移概率决定，并且n步转移概率是一步转移概率的n次方。

马尔可夫链的一些例子： 例1、简单随机徘徊

粒子在直线上每隔单位时间，以概率p向右走一步或以概率q=1-p向左走一步，每次移动与其他次移动无关。若考虑第n步时粒子所在的位置{Xn,n?T}，称为简单随机徘徊。

{Xn,n?T}是一个齐次马尔可夫链，试写出它的一步转移概率矩阵。

33

随机过程讲义

}，其一步转移概率矩阵为 解：{Xn,n?T}的状态空间为{0,?1,?2,?????????0p???q0pP??q0p????q0???????????????? ????????

例2、天气预报问题 假定

（1）昨日、今日都下雨，明日下雨的概率诶0.7； （2）昨日无雨，今日、明日都有雨的概率为0.5； （3）昨日有雨，今日无雨，明日有雨的概率为0.4； （4）昨日今日均无雨，明日有雨的概率为0.2。

若某个星期的星期一、星期二均有雨，求星期四又下雨的概率。

解：连续两天的有无雨的状态构成状态空间，设R代表下雨，N代表无雨，则状态空间为：

S?{RR,NR,RN,NN} 假定，则转移概率矩阵为：

?p11?pP??21?p31??p41p12p22p32p42p13p23p33p43p14?p24?? p34??p44?下面我们求具体的元素值，

p11?P(RR|RR)?P(R今R明|R昨R今)?P(昨日今日有雨，明日有雨)?P(R明|R昨R今)?0.7p12?P(NR|RR)?P(N今R明|R昨R今)?0,为不可能事件。

p13?P(RN|RR)?P(R今N明|R昨R今)?P(昨日今日有雨，明日无雨)?1-P(R明|R昨R今)?0.3p14?P(NN|RR)?P(N今N明|R昨R今)?0,为不可能事件。

同理，可求得其他元素。于是我们得到一步转移概率矩阵为：

?p11?pP??21?p31??p41p12p22p32p42p13p23p33p43p14??0.700.30??0.500.50?p24????? p34??00.400.6????p44??00.200.8?

本题中的问题，相当于求两步转移概率，通过前面的定理可以知道，两步转移概率矩阵为

34

随机过程讲义

两个一步转移概率矩阵的乘积。

P(2)?0.700.30??0.700.30??0.49?0.500.50??0.500.50??0.35????????00.400.6??00.400.6??0.20??????00.200.8??00.200.8??0.100.120.200.120.160.210.150.200.100.18?0.30?? 0.48??0.64?

本题中我们要求得的星期一、星期二均有雨，求星期四又下雨的概率。 由于星期一星期二均有雨，因此我们可以理解为初始状态为RR，

周四下雨，可以理解为状态空间的RR或NR，即连续两天中最后一天为下雨。

因此，我们利用两步概率转移矩阵，可知星期一、星期二均有雨，求星期四又下雨的概率p：

p?p11(2)?p12(2)?0.49?0.12?0.61

例3

假定粒子在1,2,3,4点做随机游动，当转移到2,3点时以概率1/3向左或向右移动一格，当移动到1时，停留在原处，当移动到4时以概率1移动到3。若以{Xn,n?T}表示质点在时刻n所处的位置，则{Xn,n?T}是一个齐次马尔可夫链，求其转移概率矩阵。 解：状态空间S?{1,2,3,4}

上图为各个状态之间转移概率示意图。 我们可以得到转移概率矩阵为：

?p11?pP??21?p31??p41p12p22p32p42p13p23p33p43p14??1000??1/31/31/30?p24????? p34??01/31/31/3????p44??0010?

注：

（1）行可以看成是输出，例如，对于点3，有三个输出；列可以看成是输入，点3有三个

35

随机过程讲义

输入。

（2）点1称为吸收壁，也就是说，粒子一旦到达这个状态后就被吸收，不再移动。 （3）点4称为反射壁，也就是说，粒子一旦到达这个状态后，就被反射回去。

第二节 马尔可夫链的性质

一、马尔可夫链的状态分类

1、状态的周期

设马尔可夫链的状态空间为S?{S1,S2,S3,?SN}，由状态i出发再返回i的所有可能步数记为T?{T1,T2,T3,?}，T的最大公约数为d?1，则称i是周期的；我们称d为i的周期。若d?1 则称i为非周期的。

例：求下图中各个状态的周期：

解：

（1） 对于状态1，从状态1出发，能回到状态1的所有可能步骤为能回到4,8,12…，最大

公约数为4，因此状态1的周期为4。

（2） 对于状态5，从状态5出发，能回到状态5的所有可能步骤为能回到2,4,6,8,…，最

大公约数为2，因此状态5的周期为2。

注：对于下图，由状态1出发再返回状态1的步骤为4,6,8,10…;最大公约数为2，尽管状态1经过2步不能回到状态1，根据机械运动的启示，我们仍然称2为状态1的周期。

2、常返性

36

随机过程讲义

我们看下图，设设马尔可夫链的状态空间为S?{1,2,3,4}，我们可以看出状态2和状态3有相同的周期2，但是由状态3出发，一定能返回状态3；而对于状态2，一旦当有2转移到状态3之后，则再也不能回到状态2。为了区分这两种情况，我们引入常返性的概念。

首中概率：由质点i出发，经过n步首次达到质点j的概率，称为首中概率。 记为：

fij(n)?P{Xm?v?j,1?v?n?1,Xm?n?j|Xm?i}

终达概率：由质点i出发，经过有限步终于达到质点j的概率，称为终达概率。 记为：

fij??fij(n)

n?T即： 所有可能的首中概率的和。 常返：若fii?1，我们称状态i为常返的。

注：i是常返态，可以理解为从状态i开始经过有限步可以返回i的概率为1。

对于常返态i，其所有可能的首达概率构成一个分布（即：经过1步返回到i的概率fij(1)、经过2步返回到i的概率fij(2)，等等，构成一个概率分布。分布的期望值表示从i出发再返回i的平均返回时间。

平均返回时间记为：?i??nfii(n)

n?T非常返：若fii?1，我们称状态i为非常返的。

注：非常返的意义为所有首次返回的概率之和不足1，也就意味着以1?fii永远不再返回到i。 例：

上例中：状态2出发返回状态2的概率为1?2221?，因此，状态2以概率1??永不返3333回，故状态2为非常返态。

上例中：状态3出发返回状态3的概率为1?1?1，因此，状态3为常返态。

正常返：若平均返回时间?i??，则称常返态i为正常返。

37

随机过程讲义

零常返：若平均返回时间?i??，则称常返态i为零常返。

遍历态：非周期的正常返态为遍历态。也可以理解为周期为1的正常返态度为遍历态。 吸收态：若pii?1，称状态i为吸收态。

3、互通性

可达：对于马尔可夫链的两个状态i和j，如果存在n?0，使得n步转移概率不为0（即

(n)，我们称自状态i可达状态j，记为i?j。 pii?0）

互通：对于马尔可夫链的两个状态i和j， i?j同时j?i，我们称状态i和j互通，记为

i?j。

注：可达关系和互通关系都具有传递性： （1）如果i?j，j?k则，i?k； （2）如果i?j，j?k则，i?k。

互通关系是一类重要的关系，具有互通关系的状态具有一些相同的属性，为我们分析

马尔可夫链带来方便。

二、马尔可夫链状态空间的分解

不可约闭集：假设C为状态空间S的非空子集，若对任意i?C及k?C都有pik?0，则称C为随机闭集。若C中所有状态都是互通的，称C为不可约的闭集。

注：闭集的意思是C内部的状态不能达到C外部的状态，也就是一旦质点进入闭集C中，它将永远留在C中运动。

不可约马氏链：若马尔可夫链{Xn,n?T}的状态空间S是不可约闭集，则称{Xn,n?T}为不可约马氏链。

38

本文来源：https://www.bwwdw.com/article/bner.html