第2章 随机过程与排队轮基础

1、第二章 随机过程与排队轮基础无线通信与网络研究室李屹 博士/副教授/硕导通信网基础2准备知识: 随机过程3准备知识: 随机过程4准备知识: 计数过程随机过程N(t),t0称为一个计数过程。N(t)表示到时刻t为止已发生的“事件”的总数。 N(t)0； N(t)是整数； N(t) N(s)，当t s； N(t) - N(s)代表时间区间t, s)中发生的“事件” 数5随机事件的两种描述法6随机事件的概率特征描述7随机事件的概率特征描述8随机事件特征量的物理意义9随机事件特征量的物理意义10Poisson过程 定义：计数过程N(t)服从泊松分布的随机过程，即长度为t的时间内到达k个事件的概率为 其

2、中0是泊松流的强度，表示平均到达率； 且N(0) = 0；不相交区间上增量相互独立，即对一切 0t1t2tn，N(t1), N(t2)-N(t1), N(t3)-N(t2), , N(tn)-N(tn-1)相互独立。 应用：广泛用于各种随机事件的描述或近似，可用来描述完全不可预测的随机事件和大量随机事件的叠加。etkkkttp!)()( , 2 , 1 , 0k11o（1）平稳性:在区间 内有k个事件到来的概率与起点a无关，只与时间区间的长度有关，这个概率记为 o（2）无记忆性：不相交区间内到达的事件数是相互独立的；o（3）稀疏性:令 表示长度为t的区间内至少到达两个事件的概率， 则 o（4）

3、有限性：在任意有限区间内到达有限个事件的概率为1，即taa,)(),(tPtaaPkk)(t1)(0tPkk)()(tot 0tPoisson过程12都可以近似看作泊松流都可以近似看作泊松流.某电话交换台收到的电话呼叫数；某电话交换台收到的电话呼叫数；到某机场降落的飞机数到某机场降落的飞机数;一个售货员接待的顾客数一个售货员接待的顾客数;一台纺纱机的断头数一台纺纱机的断头数; 一放射性源放射出的一放射性源放射出的 粒子数；粒子数；Poisson过程13Poisson过程14例题分析设电话呼叫按设电话呼叫按30次次/小时的泊松过程进行，求小时的泊松过程进行，求5分钟分钟间隔内，间隔内，(1)没有

4、呼叫的概率；没有呼叫的概率；(2)呼叫呼叫3次的概率。次的概率。解：按题意= 30次/h = 0.5次/min t = 5min，分别计算k = 0或k=3 214. 0! 35 . 2)5(082. 0)5(55 . 03355 . 00ePeP15Simon Denis Poisson oBorn: 6/21/1781-Pithiviers, FranceoDied: 4/25/1840-Sceaux, Franceo“Life is good for only two things: discovering mathematics and teaching mathematics.”16

5、Simon Denis PoissonoPoissons father originally wanted him to become a doctor. After a brief apprenticeship with an uncle, Poisson realized he did not want to be a doctor.oAfter the French Revolution, more opportunities became available for Poisson, whose family was not part of the nobility.oPoisson

6、went to the cole Centrale and later the cole Polytechnique in Paris, where he excelled in mathematics, despite having much less formal education than his peers.17Poissons education and worko Poisson impressed his teachers Laplace and Lagrange with his abilities.o Unfortunately, the cole Polytechniqu

7、e specialized in geometry, and Poisson could not draw diagrams well.o However, his final paper on the theory of equations was so good he was allowed to graduate without taking the final examination.o After graduating, Poisson received his first teaching position at the cole Polytechnique in Paris, w

8、hich rarely happened.o Poisson did most of his work on ordinary and partial differential equations. He also worked on problems involving physical topics, such as pendulums and sound.18Poissons accomplishmentso He has many mathematical and scientific tools named for him, including Poissons integral,

9、Poissons equation in potential theory, Poisson brackets in differential equations, Poissons ratio in elasticity, and Poissons constant in electricity. He first published his Poisson distribution in 1837 in Recherches sur la probabilit des jugements en matire criminelle et matire civile. Although thi

10、s was important to probability and random processes, other French mathematicians did not see his work as significant. His accomplishments were more accepted outside France, such as in Russia, where Chebychev used Poissons results to develop his own.19泊松过程的期望与方差()(),0,1,2,!kttP Xkekk 0kkkpxXE1()1 !kt

11、ktek11()1 !ktkttekt0()!ktktkek20 022kkkpxXE1( )1 !ktktkektt2)(1( )1 11 !ktktkek 1!1)(kktkktke 22EXXEXD t20()!ktktk ek1()11 !ktktkek泊松过程的期望与方差21Poisson过程的叠加和分解22Poisson过程的叠加o性质2-1：m个Poisson流的参数分别为 ， ， ，并且它们是相互独立的，合并流仍然为Poisson流，且参数为 。o这个性质也就是说独立的Poisson过程是可加的。12mm21 = 1 +21223o性质2-2：参数为 的Poisson流到达交换

12、局A后，每个呼叫将独立去两个不同方向，且去两个方向的概率分别为o o则Poisson流被分解为两个独立的Poisson流，参数分别为 2121和iiP 2 , 1iPoisson过程的分解24o设N(t) 表示一个Poisson 过程，o假设t ,i = 0,1,2, i 为相应的呼叫到达时刻，考虑呼叫的间隔：o根据Poisson 的特性o随机变量X 满足PX t = et ，o分布函数为：PX t= Pmin(T1, T2)t= PT1t, T2t=PT1t PT2t 又因为 ， 所以11tP Tte22tP Tte12()tP Tte(2)先证明11212P TT1212121212121

13、00112xyx yxyxyxP TTedxdyeedy dxeedx 29(3)需要证明的就是随机变量T与随机事件T1t, T1tPT1T2。2111212121221()()111212, yxtTxxtP Tt TTP tTTedyedxedxeP Tt P TT 性质2.4的证明 30例题分析(1/6)31例题分析(2/6)32例题分析(3/6)33例题分析(4/6)34例题分析(5/6)35例题分析(6/6)36名言中的数学哲理37 由泊松定理，由泊松定理，n重贝努里试验中重贝努里试验中稀有事件稀有事件出现的次数近似地服从出现的次数近似地服从泊松分布泊松分布. 我们把在每次试验中出现

14、概率很小的事我们把在每次试验中出现概率很小的事件称作件称作稀有事件稀有事件.如地震、火山爆发、特大洪水、意外事故等等如地震、火山爆发、特大洪水、意外事故等等名言中的数学哲理38生灭过程的应用与举例生灭过程的应用与举例 o应用： 用于处理输入过程为最简单流，服务时间为指数分布的一类最简单的排队模型。o举例： (1) 某地区人口数量的自然增减 (2) 细菌的繁殖与死亡 (3) 服务窗口前顾客数的变化39生灭过程的定义生灭过程的定义 o 用N(t) 表示系统在时刻t 的状态，N(t) 取非负整数值。如果N(t) = k ，称在时刻t 系统处于状态k 。系统是生灭过程的条件：n（a）在时间(t, t+

15、t) 内系统从状态k (k0) 转移到k+1的概率为k t + o (t)，这里k 为在状态k 的出生率；n（b）在时间(t, t + t) 内系统从状态k (k1) 转移到k1的概率为k t + o(t)，这里k 为在状态k 的死亡率；n（c）在时间(t, t + t) 内系统发生跳转的概率为o (t) ；n（d）在时间(t, t + t) 内系统停留在状态k 的概率为1 (k + k) t + o(t)。40生灭过程的定义生灭过程的定义 41生灭过程的状态转移生灭过程的状态转移o生灭过程的状态转移图o状态转移图包含系统的所有状态和所有可能的变化。o状态变化仅仅发生在相邻的状态之间，整个状态

16、图是一个有限或无限的链。 生灭过程是一个马尔可夫链4211|,.,llm km kjjjjmmp XiXiXi Xi|m km kmmp XiXi “将来” “过去” “现在”= “将来” “现在”-马氏性(无记忆性， 无后效性)马尔可夫链的概念马尔可夫链的概念43生灭过程的特性生灭过程的特性 o生灭过程是一种特殊的离散状态的连续时间马尔可夫过程，或被称为连续时间马尔可夫链。o生灭过程的特殊性在于状态为有限个或可数个，并且系统的状态变化一定是在相邻状态之间进行。o生灭过程的极限解或稳态解有很简单的形式。o应用：考虑一个电话机中的呼叫数，既可以增加也可以减少，所以需要引入的生灭过程可以用来描述电

17、话交换机中呼叫数的变化。Poisson 过程是一种特殊的纯生过程。44生灭过程的稳态分布生灭过程的稳态分布o考虑系统的稳态分布。生灭过程满足的柯尔莫哥洛夫（Kolmogorov）方程。n pk (t) = P N(t) = k ；n pik(t) 为系统从状态i 经过时间t 后转移到k 的条件概率：n根据生灭过程性质有45生灭过程的稳态分布生灭过程的稳态分布o推导后当 t 0 时，有o称为柯尔莫哥洛夫方程组o如果加上初始条件pk (0)，可确定各个时刻t 的分布。o考虑的重点为极限分布或稳态分布，就不需要处理复杂的微分方程组，而是线性方程组。46稳态分布满足的必要条件o假设稳态分布存在，对方程

18、求解 o在t 时，o方程变为： (k+k ) pk + k1pk1 + k+1pk+1 = 0n其中 1= 0 = p1= 0；n另外47稳态分布稳态分布 o解容易得到o其中48极限定理 o定理2-3：对有限状态的生灭过程或对满足条件 的可数状态的生灭过程，稳态分布存在，且与初始条件无关。o有限状态时，稳态分布为：kkkkk149o关于生灭过程中微分方程和稳态方程的建立可以依照下面图2-3简单完成 微分方程和稳态方程50生灭过程小结n方程组： 和初始值决定系统的变化，它们是瞬态分析的基础。n生灭过程的稳态分布，虽然一般是无限多变量的线性方程组，但是由于生灭过程只有相邻状态有关系，故可以简单化解

19、。n如果系统的状态变化不局限在相邻状态之间，分布就不容易得到。如果到达的呼叫流不平稳，有时可以用特殊的生灭过程表示信源。51名人名言 生活中最重要的问题，其中绝大多数在实生活中最重要的问题，其中绝大多数在实质上只是概率的问题质上只是概率的问题 . -拉普拉斯拉普拉斯 我又转念，见日光之下，快跑的人未必能我又转念，见日光之下，快跑的人未必能赢，力战的未必得胜，智慧的未必得粮食，明赢，力战的未必得胜，智慧的未必得粮食，明哲的未必得资财，灵巧的未必得喜悦，所临到哲的未必得资财，灵巧的未必得喜悦，所临到众人的，是在乎当时的机会众人的，是在乎当时的机会. -传道书传道书52排队系统的基本概念o排队论是专

20、门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。53排队系统的基本概念54排队系统的基本概念55排队系统的基本概念56排队系统的基本概念57排队系统的基本概念58排队系统的描述59排队系统的描述60排队系统的描述61排队系统的描述62排队系统的描述63排队系统的描述64排队系统的描述65排队系统的描述66排队模型表示排队模型表示肯德尔肯德尔记号记号67排队系统的参数和指标68排队系统的参数和指标69排队系统的参数和指标70排队系统的参数和指标71排队系统的参数和指标72Little定理73Little定理74Little定理75Little定理76Little定理77Littl

21、e定理78Little公式的应用1. 考虑一个传输线，每隔K秒到达一个数据包，假设第一个包在0时刻到达。所有的包长度相等，需要相同的传输和处理时间，分别为K秒和X秒，问传输线上停留的数据分组的平均数目为多少？解： 1 /K；N T (K+X)/ K +X/K 79Little公式的应用2. 假设一个服务大厅有K个窗口，该服务大厅最多容纳N个顾客(NK)，且服务大厅始终是客满的，即一个顾客离开将会有另一个顾客进入。设每个顾客的服务时间是X，问顾客在大厅内停留的时间T为多少？3. 改变上题目中的顾客到达方式，假设顾客到达时发现服务窗口被占就立即离开大厅(即顾客被阻塞)。设顾客到达率是，问顾客的阻塞

22、率为多少？解：NT T N /；K X K /X； TNX/K解：平均处于忙的窗口数为j (j K)，系统中平均用户数： j(1)X； 1j/X 1K/X 80Little公式的应用81M/M/1o M/M/1的到达过程为一个参数为 的Poisson过程；系统允许排队的队长可以是无穷大(系统的缓存容量无限大)；服务时间是参数为 的负指数分布；服务员的数目为1，到达过程与服务过程相互独立。如果用系统中的顾客数来表征系统的状态，容易验证这是一个生灭过程，并且k0, 2 , 10kkk82o 令 ，根据生灭过程的性质o在 时 oM/M/1的队长分布 0ppkk1111p10kk)1 (pkk , 2 , 1 , 0kM/M/183M/M/184M/M/185M/M/186M/M/187M/M/11111w由Little定理，顾客停留在系统中的平均时间 ：顾客的平均排队时间 ：1)1 (11sE112WNQ顾客的平均排队(等待)队长 ： 假设k为顾客到达时看到的队长分布，这个分布在许多情形下不同于稳态分布p k ，不过在到达过程为泊松过程时k和p k是一样的。88M/M/189o定理2-5： M/M/1排队系统在稳态时，系统时间s服从参数为-的负指数分布。M/M/190M/M/19