第五章 马尔可夫过程-4

5马尔可夫过程马尔可夫过程的概念离散参数马尔可夫链连续参数马尔可夫链生灭过程及排队系统5.4生灭过程5.4.1定义如果连续参数马尔可夫链{X(t),t≥0}满足：（1）状态转移仅限于从一个状态向其邻近状态转移；（2）若X(t)=i，则在[t,t+τ]内由状态i转移状态i+1的概率为；由状态i转移状态i-1的概率为；状态i不变的概率为；（3）若X(t)=i，则在[t,t+τ]内由状态i转移二个或二个以上状态的概率为o(τ)。则称该链{X(t),t≥0}为生灭过程。状态空间E={0,1,2,3,…}(状态无限);T=[0,∞]。如果λi,μi均是t的函数，则称为非齐次生灭过程；如果λi,μi均是t的线性函数，则称为非齐次线性生灭过程；如果λi,μi均与t无关，则称为齐次生灭过程。()()itλτοτ+()()itμτοτ+1[()()]()iittλμτοτ−++5.4生灭过程5.4.2转移概率齐次生灭过程转移概率如下：可见，在一小段时间内，忽略高阶无穷小o(τ)，生灭过程的状态变化只有三种情况：（1）状态i转移至状态i+1，状态增加1，群体“生”了一个个体，“生长率”为λi；（2）状态i转移至状态i-1，状态减少1，群体“死”了一个个体，“灭亡率”为μi；（3）状态不增不减，群体个数不变。生灭过程所有状态都是相通的。110(1)()(),0(2)()(),0,=0(3)()1()()(4)()(),||2.iiiiiiiiiiiiijpopopopoijτλττλτμττμμτλμττττ+−=+=+=−++=−≥5.4生灭过程5.4.3转移速率矩阵根据转移速率的定义，转移速率矩阵为当μi=0,为纯生过程；当λi=0,为纯灭过程。0,1(),1lim(),0,||2iijijiijiijipjiqjijiτλτδμλμτ→=+⎧⎪−=−⎪==⎨−+=⎪⎪−≥⎩00111122220000()0000()0000()0000iiiiλλμλμλμλμλμλμλ−⎛⎞⎜⎟−+⎜⎟⎜⎟−+⎜⎟=⎜⎟⎜⎟−+⎜⎟⎜⎟⎜⎟⎝⎠Q#%%%%###%%%%%%5.4生灭过程5.4.4转移速率图生灭过程012N……λ0μ1λ1λ2λN-1λNμ2μ3μNμN+1012N……λ00λ1λ2λN-1λN0000纯生过程纯灭过程012N……0μ10000μ2μ3μNμN+15.4生灭过程5.4.5微分方程柯尔莫哥洛夫前进方程、后退方程：转移概率与转移速率的微分关系。()(),(0)tt′==PPQPI1,11,100011()()()()(),1()()()ijjjijjijjijiiiptptptptjptptptλμλμλμ−−++′=−+++≥⎧⎨′=−+⎩前进方程5.4生灭过程5.4.5微分方程柯尔莫哥洛夫前进方程、后退方程：转移概率与转移速率的微分关系。()(),(0)tt′==PQPPI1,1,00001()()()()(),1()()()ijiiijiijjijjjjptptptptiptptptλμλμλλ+−′=−+++≥⎧⎨′=−+⎩后退方程5.4生灭过程5.4.5微分方程福克-普朗克方程：绝对概率与转移速率的微分关系。111100011()()()()(),1()()()jjjjjjjjptptptptjptptptλμλμλμ−−++′=−+++≥⎧⎨′=−+⎩0101[()()()][()()()]NNptptptptptpt′′′=Q()()tt′=PPQ5.4生灭过程5.4.6平稳分布若极限分布存在,则存在平稳状态.根据定理，若平稳分布{πi,i=1,2,…}存在，必满足线性方程组又把转移速率代入，方程组化为()01iπππ=Q001iiπ+∞==∑0011111100()0,1,2,...1iiiiiiiiiiλπμπλπλμπμππ−−+++∞=⎧⎪−+=⎪⎪−++==⎨⎪⎪=⎪⎩∑5.4生灭过程5.4.6平稳分布解该方程组得0101011210212011012011001121iiiiiiλππμλλλπππμμμλλλππμμμλλλππμμμ−+∞−=====+=∑5.4生灭过程5.4.6平稳分布当收敛时，存在平稳分布当发散时，生灭过程不存在平稳分布。101101120110121,1,2,3,...iiiiiiiλλλπμμμλλλππμμμ−+∞−=−⎡⎤=+⎢⎥⎣⎦==∑011112iiiλλλμμμ+∞−=∑011112iiiλλλμμμ+∞−=∑5.4生灭过程5.4.6平稳分布平衡方程当过程渐近平稳状态时，有称为整体平衡方程,即它表示进入状态i的平均速率等于离开状态i的平均速率。001111110()0,1,2,...iiiiiiiiλπμπλπλμπμπ−−++−+=−++==1111iiiiiiiiλπμπλπμπ−−+++=+5.4生灭过程5.4.6平稳分布平衡方程生灭过程的平稳分布，从该式得到称为详细平衡方程，它表示从状态i-1转移到状态i的平均速率等于从状态i转移到状态i-1的平均速率。11iiiiμπλπ−−=011012,1,2,3,...iiiiλλλππμμμ−==5.4生灭过程5.4.7有限状态状态空间E={0,1,2,3,…,N};T=[0,∞]当i≥N,λi=0;当iN,μi=0.微分方程：1111000111111()()()()(),()()()()()()jjjjjjjjNNNNNjNptptptptptptptptptptλμλμλμλμ−−++−−≤≤−′=−+++⎧⎪′=−+⎨⎪′=−⎩()()tt′=PPQ5.4生灭过程5.4.7有限状态状态空间E={0,1,2,3,…,N};T=[0,∞]当i≥N,λi=0;当iN,μi=0.平稳分布：001111111100()0,1,2,...,01iiiiiiiNNNNiiiNλπμπλπλμπμπλπμππ−−++−−+∞=−+=⎧⎪−++==⎪⎪−=⎨⎪⎪=⎪⎩∑有限状态的生灭过程必存在平稳分布5.4生灭过程5.4.8纯生过程状态空间E={0,1,2,3,…};T=[0,∞]当j≥0,μj=0.微分方程:初始概率:p0(0)=1,对i≥1,pi(0)=011000()()(),1()()jjjjjptptptjptptλλλ−−′=−+≥⎧⎨′=−⎩100()[]ljjtjjljlkpttceλλ−−===∑∏1()ljljljcλλ≠=−∏5.5生灭过程在排队论中的应用5.5.1随机服务系统（排队论）的基本概念一、随机服务系统模型顾客到达等待服务接受服务顾客离去排队规则等待时间排队顾客数服务台数接受服务顾客数服务时间系统顾客数系统时间5.5.1随机服务系统（排队论）的基本概念二、有关定义、概念若顾客在时刻tk到达，则称tk为到达时间；随机变量Tk=tk+1-tk称为到达间隔；若Tk是独立同分布的，则称E{Tk}为平均到达间隔；若顾客在[0,t)内到达的数目为随机过程N(t),则称N(t)/t为该区间上的平均到达率(λ),即单位时间内平均到达系统的顾客数量,反映了顾客到达系统的快慢程度。λ=1/E{Tk}例如，强度为λ泊松过程的平均到达间隔为1/λ,平均到达率则为λ。5.5.1随机服务系统（排队论）的基本概念二、有关定义、概念服务台对第k个顾客的服务时间tk是一个随机变量序列，若该序列是独立同分布的，则期望E{tk}便是平均服务时间，其倒数则为平均服务率（μ），即单位时间内由一个服务台进行服务所离开系统的平均顾客数。例如，若服务时间是参数为μ的指数分布，则平均服务时间为1/μ,平均服务率则为μ。顾客的等待时间为一个随机变量序列，其数学期望为平均等待时间。5.5.1随机服务系统（排队论）的基本概念二、有关定义、概念系统时间：顾客从到达到离开系统所用的时间。显然，一个顾客的系统时间为等待时间与服务时间之和。系统容量：系统所容许的最大顾客数。系统的总顾客数可分成两种状态：排队状态和接受服务状态。显然，总顾客数为排队顾客数与接受服务顾客数之和。平均拒绝率：当请求服务的顾客数目超过系统容量时，则将有部分顾客被系统拒绝。单位时间内被系统拒绝的平均顾客数称为系统的平均拒绝率。服务台利用率：若系统共有m个服务台，某时刻被占用的服务台数为r(t),则服务台利用率定义为E{r(t)}/m。5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素四要素：输入过程、排队规则、服务过程、服务台数目。1.输入过程：描述顾客到达的规律(与顾客到达率和到达时间的随机性有关)。其特征常用相邻两个顾客到达的时间间隔的分布函数来描述。几种常见的输入过程：（1）泊松过程。顾客到达间隔Tk为独立同分布的随机序列，其分布为指数分布，概率密度为其数学期望，即平均到达间隔为1/λ,平均到达率则为λ。顾客到达数目为泊松分布，即(),0tTftetλλ−=≥(){()},0,1,2,...!nttPNtnennλλ−===5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素（2）爱尔朗(Erlang)分布。顾客到达间隔Tk为独立同分布的随机序列，其满足Erlang分布，概率密度为（3）定长输入。顾客到达的时间间隔一定。（4）伯努利到达。顾客的到达仅限于某一固定时间T的整数倍时刻，在各个整数倍时刻顾客是否到达是由概率为p的伯努利试验决定的。预约到达、集体到达，等。顾客源无限；顾客源有限。1()(),0(1)!ntTtftetnλλλ−−=≥−5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素四要素：输入过程、排队规则、服务过程、服务台数目。2.排队规则：顾客接受服务的规则，或等待服务的顾客进入服务所规定的次序。常见的排队规则有：（1）消失制。当顾客到达时，见到所有服务台都已被占用，就自行消失，不进入排队等待行列。（2）等待制。当顾客到达时，若所有服务台都已被占用时，多余的顾客排队等待，这是无限空间等候的情形。（3）混合制。当顾客到达时，若队伍长度小于某个预定数时，就排入队伍，否则就自动离去。5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素常见服务规则有：（1）先来先服务。（2）后来先服务。（3）随机选择服务。所有到达的顾客都有相同的概率接受服务。（4）优先权服务。（5）批量服务。5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素常见排队方式有：混合排队-多服务台顾客服务台单队-单服务台分别排队-多服务台两次混合排队-多服务台多次排队-多服务台并列5.5.1随机服务系统（排队论）的基本概念三、随机服务系统要素四要素：输入过程、排队规则、服务过程、服务台数目。3.服务过程：指各个顾客接受服务的时间的分布规律(取决于服务机构的效率和服务时间)。其特征用服务时间的分布函数来描述。服务时间常常是独立同分布的，其概率分布常有：指数分布、Erlang分布、定长分布等，对应的服务称为指数服务、Erlang服务、定长服务等。4.服务台数目：系统内可以同时提供服务的设备或窗口数。可以有1个、N个或∞个。各服务台之间彼此独立地工作。5.5.1随机服务系统（排队论）的基本概念四、排队系统的表示一个排队系统常按下列特征和顺序，并用记号表示：顾客到达分布/服务时间分布/服务台数目/系统容量/顾客源数/服务规则顾客到达间隔分布和服务时间分布用下列字母表示：M-指数分布；D-定长时间分布；G-一般分布；E-Erlang分布。例如：M/M/n/N/∞/FIFO(FirstInFirstOut)表示输入过程为泊松过程，顾客到达间隔服从指数分布；服务时间为指数分布；服务台n个；系统容量N个；顾客来源无限；服务规则是先到先服务。5.5.1随机服务系统（排队论）的基本概念五、评价随机服务系统的指标评价一个随机服务系统性能优劣的标准：从顾客的角度来说，平均系统时间和平均等待时间越短越好；平均拒绝率与平均到达率之比越小越好。从系统资源利用率的角度来看，服务台利用率越大越好。5.5.1随机服务系统（排队论）的基本概念六、排队系统的需要研究