版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第1章 随机过程简介1 1第第1 1章章 随机过程简介随机过程简介1.1随机过程基本概念1.2泊松过程1.3马尔可夫过程1.4离散时间马尔可夫链的性质1.5连续时间马尔可夫链1.6生灭过程第1章 随机过程简介2 21.1随机过程基本概念1. 随机过程的定义例1.1热噪声电压电阻上的热噪声是由于电阻中的电子的热运动所引起的。现对一个电阻上的热噪声电压进行n次长时间的测量,同时记录每一次热噪声的电压波形,并以X(t), t0,)表示热噪声电压, 如图1.1所示。 图中x1(t)表示第一次测量得到的波形图,x2(t)表示第二次测量得到的波形图,xn(t)表示第n次测量得到的波形图。第1章 随机过程简
2、介3 3图1.1热噪声电压第1章 随机过程简介4 4例1.2随机无限次抛掷硬币现抛掷m盘硬币,同时记录每盘抛掷硬币的结果。若以X(n), nI表示抛掷硬币的结果,其中I为正整数集合,则X(n), nI是一个随机过程,如图1.2所示。第1章 随机过程简介5 5图1.2随机无限次抛掷硬币第1章 随机过程简介6 6例1.3电话交换站呼叫计数设一个电话交换台迟早会接到用户的呼叫,并以X(t)表示时间间隔0,t)内交换台接到的呼叫次数,则X(t)是一个随机变量,但是对于不同的t0,),X(t)是不同的随机变量,于是X(t), t0,)是随机过程, 如图1.3所示。第1章 随机过程简介7 7图1.3电话交
3、换站呼叫计数第1章 随机过程简介8 8例1.4纺纱机纺出长度为l的细纱若对一个纺纱机进行n次长时间测量,同时记录每一次纺纱机纺出细纱长度的曲线,并以X(u), u0,)表示纺纱机纺出细纱的长度,则X(u)是一个随机变量,如图1.4所示。 第1章 随机过程简介9 9图1.4纺纱机纺出长度为l的细纱第1章 随机过程简介10 10随机过程随机过程是定义在给定概率空间上的一族随机变量X(t), tT。 T表示参数集,是实数轴(,)上的一个子集(T又称为索引集、指标集),当t取遍参数集T中的每个值时,均有一个随机变量X(t)与之对应。第1章 随机过程简介11 11根据参数集T(离散集和连续集)和状态空间
4、取值(离散的和连续的)的情况,可以把随机过程分为四类: (1) 离散参数、离散状态的随机过程;(2) 离散参数、连续状态的随机过程; (3) 连续参数、离散状态的随机过程;(4) 连续参数、连续状态的随机过程。第1章 随机过程简介12 122. 随机过程的描述对于固定t值的X(t),其特性可由概率分布函数和概率密度函数表示。对于连续状态过程,我们有如下描述: 一维分布函数F(x; t)=PX(t)x, 其中tT是固定的, F(;t)=0,F(+;t)=1。第1章 随机过程简介13 13n维联合分布函数对于任意固定的t1,t2,tnT,t1t2tn,F(x;t)=F(x1,x2, xn; t1,
5、t2,tn)= PX(t1)x1, X(t2)x2, X(tn)0,其中A是在区间(0,a)上服从均匀分布的随机变量,试求X(t)的均值函数和方差函数。第1章 随机过程简介2020解X(t)的均值函数和方差函数分别为第1章 随机过程简介21 21 1.2泊 松 过 程1. 强平稳随机过程对于随机过程X(t), tT , 如果其n维联合分布函数(n1)有 F(x;t)=F(x; t+)其中, xRn, tTn,且对于所有标量, 有ti+T,则称该过程为强(严、狭义)平稳随机过程,或严格静止的随机过程。第1章 随机过程简介22222. 弱平稳随机过程设有一个二阶矩随机过程X(t), tT,若其数学
6、期望(t)=为常数,相关函数R(t, t+)=R(),与t无关,则称其为弱(宽、广义)平稳过程,或广义静止的随机过程。它是一类统计特性不随时间推移而变化的随机过程。第1章 随机过程简介23233. 独立过程如果随机过程X(t), tT 的n维联合分布函数满足: 则称其为独立过程。第1章 随机过程简介24244. 独立增量过程如果在参数集T上任选n(n1)个点t1t2tn,随机过程X(t), t0, )的增量X(t2)X(t1), X(t3)X(t2), X(tn)X(tn1)是相互统计独立的随机变量,则称过程X(t), t0, )为独立增量随机过程。第1章 随机过程简介25255. 泊松过程设
7、随机过程X(t), t0, )的无限状态空间是E=0,1,2,。若满足下面两个条件: (1) X(t)是平稳独立增量过程;(2) 对任意a, t0,每一个增量X(a+t)X(a)非负,且服从参数为t(0)的泊松分布,则称X(t)是具有参数的泊松过程。第1章 随机过程简介2626定理强度为的泊松过程的点间间距是相互独立的随机变量,且服从同一个负指数分布。定理如果任意相继出现的两个质点的点间间距相互独立且服从同一个负指数分布,则质点流构成了强度为的泊松过程。第1章 随机过程简介27271.3马尔可夫过程无后效性又称为马尔可夫特性: 对于随机过程X(t), tT,如果对于任意的参数t0t1t2tnt
8、,在X(t0), X(t1), X(tn)值已知的情况下, X(t)的条件分布只与X(tn)的状态有关,即PX(t)x|X(tn)xn,X(tn1)xn1, X(t0)x0=PX(t)x|X(tn)xn第1章 随机过程简介2828马尔可夫链n时刻的k步转移概率: n时刻MC处于状态i,经过k步时间,系统处于j状态的概率,记为第1章 随机过程简介2929特别的, 当 k=1 时, 得到一步转移概率第1章 随机过程简介3030其一步转移概率矩阵P(1)为k步转移概率矩阵记为P(k)。第1章 随机过程简介31 31本课程研究时间齐次马尔可夫过程,简称时齐马尔可夫过程。它满足PX(t)x|X(tn)=
9、xn=PX(ttn)x|X(0)=xn其中假定系统的行为不依赖于观测的时间,即马尔可夫过程中的条件分布函数不随观察起始时刻的变化而变化,我们可以任选时间轴的起点。第1章 随机过程简介3232对于马尔可夫链,如果n时刻的k步转移概率满足即从i状态转到j状态的概率和时刻n无关,就称这类MC为时齐马尔可夫链,或齐次马尔可夫链,有时也说它是具有平稳转移概率的马尔可夫链。通常考虑状态空间是有限的齐次马尔可夫链。第1章 随机过程简介3333例1.6只传输数字0和1的串联系统(0-1传输系统)如图1.5所示,设每一级的传真率为p, 误码率为q=1p,设一个单位时间传输一级,X0是第一级的输入,Xn是第n级的
10、输出。第1章 随机过程简介3434图1.50-1传输系统第1章 随机过程简介3535分析可见: Xn,n=1,2,是一个随机过程,状态空间I=0,1。且当Xn=i,iI为已知时,Xn+1所处的状态分布只与Xn=i有关,而与时刻n之前所处的状态无关,所以它是个马尔可夫链,并是齐次的。它的一步转移概率和一步转移概率矩阵分别为: 第1章 随机过程简介3636例1.7一维随机游动设一质点在如图1.6所示的直线的点集I=1,2, 3,4,5上随机游动,并仅在1秒、2秒等整秒的时刻发生游动。第1章 随机过程简介3737图1.6一维随机游动第1章 随机过程简介3838游动的规则是: 如果Q现在位于点i(1i
11、0,即过程可以经过n步(n1)从状态j返回到状态j,则定义所有正整数n的最大公约数为状态j的周期(period), 记为dj。若对一切n1,pjj(n)=0,则约定dj=。 如果dj1, 那么称状态j是周期性状态; 如果dj=1, 那么称状态j是非周期性状态。第1章 随机过程简介6363定理若,则di=dj,即互通的状态具有相同的周期。图1.13给出了两个例子,用以描述上述定理。读者可以根据周期的定义一个一个地找最大公约数来验证定理是否成立。第1章 随机过程简介6464图1.13马尔可夫链的周期性(一)第1章 随机过程简介6565事实上,直接根据定义来验证周期性是很繁琐的,下面给出两个比较容易
12、判读的充分条件进行验证。判别一个状态是非周期的充分条件: 若此状态带有自环,则必为非周期的(非周期的状态不一定有自环); 若此状态与一个非周期的状态互通,则必为非周期的。图1.14给出了两个例子来说明如何使用该充分条件。第1章 随机过程简介6666图1.14马尔可夫链的周期性(二)第1章 随机过程简介67674. 常返性常返性是考察马尔可夫链由一个状态出发之后能否再次回归到本状态的特性。常返性分三种: 正常返(必定会返回,平均返回时间为有限值); 零常返(必定会返回,平均返回时间为(); 非常返(可能不再返回)。为定义常返性,给出如下描述:第1章 随机过程简介6868 如果fj1,状态j被称为
13、是非常返的(暂短的(transient)或滑过的),亦即过程存在一个离开状态j后决不再返回j的非零的正数概率。滑过态意味着从状态j出发至多返回状态j有限多次,之后就不再回到状态j了(返回的次数是随机的)。 如果fj=1,状态j被称为常返的(回归的(recurrent),亦即过程在离开状态j后以概率1返回j。常返态意味着从状态j出发必定要无限多次返回到状态j。第1章 随机过程简介6969常返态j的平均返回时间Mj: 定义为它是离散马尔可夫链中离开状态j后第一次返回状态j所需要的平均步数。 零常返: 具有无限的平均返回时间(Mj=或)的常返态。 正常返: 满足Mj的常返态。图1.15中, p、q为
14、转移概率,且都大于0,p+q =1,请读者尝试用定义来验证各个状态的常返性。第1章 随机过程简介7070图1.15马尔可夫链的常返性(一)第1章 随机过程简介71 71在此,我们直接给出结果: 若pq,则均为非常返。图1.16给出了一个例子。第1章 随机过程简介7272图1.16马尔可夫链的常返性(二)第1章 随机过程简介7373事实上,判断马尔可夫链的常返性经常使用如下方法。对有限状态齐次马尔可夫链,必有: 若此马尔可夫链不可约,则E全由常返态组成; 不存在零常返态; 不可约马尔可夫链均由正常返态组成。第1章 随机过程简介7474定理设X是不可约马尔可夫链,那么其状态集E或者全由非常返态组成
15、,或者全为零常返态,或者全为正常返态,且每个状态周期相同。这个定理也被称做“不可约马尔可夫链的状态一致性”。第1章 随机过程简介75755.遍历性马尔可夫链的遍历性: 在马尔可夫链中,如果n步转移概率pij(n)对一切i,j存在不依赖于i的极限,即则称马尔可夫链具有遍历性。其中,pj()表示在极限时间(平衡状态)系统处于状态j的概率,pj表示系统处于状态j的概率。第1章 随机过程简介7676定理如果齐次马尔可夫链的一个状态j是非周期、正常返的,则此状态j为遍历的。定理如果一个不可约马尔可夫链所有状态均为遍历的,则此马尔可夫链就是遍历链。第1章 随机过程简介7777例1.11设马尔可夫链的状态空
16、间为S=1,2,3,转移概率为: P11=1/2,Pi,i+1=1/2,Pi1=1/2, iS,研究各状态的分类。解画出状态转移图, 如图1.17所示。第1章 随机过程简介7878图1.17例1.11的状态转移图第1章 随机过程简介7979由图可知故第1章 随机过程简介8080故状态1是常返的。 又故状态1是正常返的。第1章 随机过程简介81 81例1.12设齐次马尔可夫链的状态空间为1,2,3,4,一步转移矩阵为: 试研究其状态关系。第1章 随机过程简介8282解画出状态转移图, 如图1.18所示。可知: 故状态3和状态4为非常返态。第1章 随机过程简介8383图1.18例1.12的状态转移
17、图第1章 随机过程简介8484故状态1和状态2都是正常返的,易知它们是非周期的,从而是遍历状态。第1章 随机过程简介85856. 稳定状态分布在离散马尔可夫链中,一个重要问题是研究稳定状态分布的存在及其评价。即平稳的概率分布(平稳分布): 定义在DTMC状态上的概率分布列zi, iS(即zi0,)被称为是平稳的,如果有,这时对一切n1有, 也就是说,一旦过程到达该平稳分布, 则对于所有后续的步而言,过程取哪一个状态的概率不再随时间而变化,各状态的概率趋于稳定。第1章 随机过程简介8686极限概率hj,jS(过程处于j状态)定义为:,(hj(n)为n时刻过程处于j状态的概率)。 极限概率的意义在
18、于,对于固定的状态j,不管链在某一时刻从什么状态出发,到达状态j的概率都趋近于hj,这就是遍历性。第1章 随机过程简介8787在这种情况下,所有状态是遍历的,且DTMC本身也是遍历的。极限概率hj,jS是唯一的,能通过下列线性方程求解:第1章 随机过程简介8888定理马尔可夫链是遍历的其平稳分布必定存在、唯一、与初始分布无关且保持不变。我们用图1.19来说明上述描述。第1章 随机过程简介8989图1.19马尔可夫链的初始分布、瞬时分布与平稳分布第1章 随机过程简介9090定理设齐次马尔可夫链的状态空间为S=1,2,3,N,P是其一步转移概率矩阵,如果存在正整数m,使对任意的状态i,jS都有pi
19、j (m)0,i,j =1,2,3,N,即m步转移矩阵没有零元,则此链具有遍历性,且由极限分布h=(h 1, h n)知,它是方程组h = h p的满足条件h j0,的唯一解。第1章 随机过程简介91 91例1.13一质点在1、2、3三个点上作随机游动,1和3是两个反射壁,当质点处于2时,下一时刻转移到1和3的概率各为1/2。写出一步转移概率矩阵,判断此链是否具有遍历性,若有,则求出极限分布。第1章 随机过程简介9292解 第1章 随机过程简介9393例1.14一质点在1、2、3三个点上随机游动,1和3是两个反射壁,当质点处于2时,下一时刻处于1、2、3是等可能的。写出一步转移概率矩阵,判断此
20、链是否具有遍历性,若有,则求出极限分布。第1章 随机过程简介9494解第1章 随机过程简介9595设极限分布h=(h 1, h 2, h 3),得方程组解得第1章 随机过程简介9696例1.15考虑一个双处理器系统,包括两个CPU及它们的私用存储器和一个共用存储器,共用存储器一次只能允许一个处理器访问。两个CPU共享一个时钟,在发出一个共用存储器存取请求以前,私用存储器运行一个随机数量周期。假定这个随机数量周期是参数为p的几何分布,使得一个处理机在它私用存储器运行的每个周期发出一个共用存储器存取请求的概率为p,在两个共用存储器存取请求之间的平均周期数量为。 第1章 随机过程简介9797共用存储
21、器存取时间间隔也假定为参数为q的几何分布,当共用存储器存取进行时,在每个周期完成一个共用存储器存取的概率为q,共用存储器存取的平均期间为周期。在初始环境,假定仅有一个处理机可操作。在这种情况,系统仅处于下列两个状态中的一个状态:(1) 处理机正在它的私用存储器中运行;(2) 处理机正在共用存储器中存取。第1章 随机过程简介9898系统的行为可由两状态的离散时间过程模拟。设所引进的系统工作负载假定条件使得系统动态行为满足没有记忆特性,它是DTMC。它有转移概率矩阵:这个两状态的DTMC的特性在图1.20中描述。这个图同转移概率矩阵描述了相同的信息,这种图称为DTMC的状态(转换)图,如图1.20
22、所示。 第1章 随机过程简介9999图1.20单处理机模型的状态转换图第1章 随机过程简介100100只要p和q大于零且小于1,这个两状态的DTMC就明显是不可约的和非周期的。在相同的假定下,此模型是历遍的,稳定状态分布可由下列线性方程求得:第1章 随机过程简介101101注意到前两个方程是线性相关的,因而其中一个可以删除。 可求得其稳定状态概率为它表明处理机执行在私用存储器的稳定状态概率是q/p+q,状态2的平均返回时间是p+q/p个周期,在两个连续私用存储器存取之间共用存储器的平均存取周期是p/q。第1章 随机过程简介102102现在让我们回到两个处理机的系统,假定它们的工作负载特性如上所
23、述,用下标A和B表示不同处理机的执行可能性,则系统可有如下五个状态:(1) 两个处理机都在私用存储器中执行。(2) 处理机B在私用存储器中执行,而处理机A在共用存储器中存取。(3) 处理机A在私用存储器中执行,而处理机B在共用存储器中存取。(4) 处理机B在等待共用存储器,而处理机A在共用存储器中存取。(5) 处理机A在等待共用存储器,而处理机B在共用存储器中存取。第1章 随机过程简介103103系统的行为可由一个五状态的离散时间过程模拟。在系统负载引进的假定使系统动态满足无记忆特性,系统的行为是DTMC。它有转移概率矩阵:第1章 随机过程简介1041041.5连续时间马尔可夫链定义:随机过程
24、X(t),t0 是一个连续时间马尔可夫链(简称CTMC),即对于 nN,xkS,且所有序列t0,t1,tn+1满足t0t1t,则转移概率:当t时,定义:第1章 随机过程简介106106如果CTMC是时间齐次的,则转移概率仅依赖于时间差=t,简化书写符号有:表示给定过程当前处于状态i,经过时间间隔后过程在状态j的概率。第1章 随机过程简介1071071. 稳定状态分布首先,令hi(t)=PX(t)=i,定义极限概率hj,jS为同离散情况,稳定状态分布的存在条件依赖于链的结构和状态的分类。第1章 随机过程简介108108定义: 在一定条件下,极限存在,我们称qij为马尔科夫过程的瞬间转移速率或发生
25、器,又称为无穷小转移率或跳跃强度,它刻画了马尔科夫过程的转移概率函数在零时刻对时间的变化率; qii是过程离开状态i的速率。从上式可见:qij0,ij; qij0,i=j第1章 随机过程简介109109假定qij对于 i,jS是有限的,则有:定义状态j的首次命中时间hj是过程在离开当前状态后第1次进入状态j 的时刻。进一步让(类似于DCMC,可称之为首达概率):第1章 随机过程简介110110 如果fjj 0,使得pij(t)0,则称由状态i可达状态j,记为ij; 若对一切t0,有pij(t)=0,则称由状态i不可达状态j;若ij且ji,则称状态i与j相通,记作 。由上面可知,相通是一等价关系
26、,从而可根据相通关系对状态空间分类。相通的状态组成一个状态类。第1章 随机过程简介112112假设状态空间S的一个子集A是闭合的(closed),如果则在此情况下,对于所有iA,所有j 和所有t0,都有pij(t)=0,因此不能从A中的状态出发到达 中的状态。一个CTMC的状态空间S没有子集是闭合的,整个状态空间是一个状态类,则说它是不可约的(irreducible),每一个状态可由任何其它状态达到。 AA第1章 随机过程简介113113对于所有具有有限状态、不可约和齐次的CTMC,限定概率存在,与初始分布hi(0),jS无关,可形成稳定状态概率。由解下列线性方程系统获得:第1章 随机过程简介
27、114114在上述条件下,CTMC的状态是遍历的,所以这个链本身也被称为是遍历的。状态j的平均返回时间Mj定义为离开状态j后首次返回状态j的平均时间:第1章 随机过程简介1151152. 矩阵方程式定义转移概率矩阵P(t)为定义矩阵:叫做转移概率矩阵P(t)的无限产生器或者转换速率矩阵。第1章 随机过程简介116116一个可约CTMC的稳定状态概率的矩阵方程:其中, h h是向量: h h =(h1,h2,)。第1章 随机过程简介1171173. 逗留和回归时间CTMC在状态iS的逗留时间是指数分布的随机变量,用SJi表示,有:注:上式即参数为qii的负指数分布的概率密度函数,qii是过程离开
28、状态i的速率。因此,在状态i的平均逗留时间是第1章 随机过程简介118118 时间t的前向返回时间f(t):过程在t时间状态仍将进一步维持所要花费的时间数量,即从时间t到下一次状态改变所经历的时间长度,亦即根据状态逗留时间的无记忆性概率分布函数,可以有:因此前向返回时间同逗留时间一样是指数分布,且具有相同的概率分布函数。第1章 随机过程简介119119 时间t的后向返回时间:过程在t时间状态已经花费了的时间。如果参数t(,),则后向、前向返回时间具有相同的性质。通常在参数t0,)时,后向返回时间的分布是截尾的指数分布。无论如何,在t 的极限情况下,前、后向返回时间都是指数分布的。第1章 随机过程简介120120例1.16同在DTCM中的例子
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年美国驾照中文模拟试题及参考答案
- 2026年信息安全合规典型模拟试题及答案
- 2026年国开外国文学专题形考任务1-4模拟试题(含答案)
- 2026年新版合肥财经校模拟试卷及答案
- 2026年骨折救援模拟试卷带答案
- 2026年社区发展模拟试题及参考答案
- 2026年输血应急预案模拟试题及答案
- 2026年机械工程师机械制造基础知识备考试题(含答案)
- 2026年护理手卫生模拟试题(含答案)
- 2026年矿大开设模拟试题及参考答案
- 医药购销不正之风治理课件
- 塔吊司索工考试题库及答案2026
- 广东省广州市增城区2025-2026学年七年级上学期期中生物学试题(含答案)
- (2026版)传染病防治自查报告
- 2026年四川省广元市辅警人员招聘考试真题解析含答案
- 广东省江门市2026年重点中学小升初语文考试真题试卷(+答案)
- 2025年兵团新职工考试题及答案
- 2026年中国铁路广州局铁路局校园招聘真题
- 2026年滴滴出行司机管理岗竞聘模拟题
- (2025年)自动监测数据标记规则及督办规则综合基础考试题附答案
- 机械制造技术 课件 6机械加工精度
评论
0/150
提交评论