第1页 / 共70页
第2页 / 共70页
第3页 / 共70页
第4页 / 共70页
第5页 / 共70页
第6页 / 共70页
第7页 / 共70页
第8页 / 共70页
排队论算法 （含ppt）.ppt
排队论及其应用
Lecture 2 随机过程 & 排队论初步
中国科学技术大学
计算机科学与技术学院
田 野
1
随机过程
n 随机变量X，分布函数不变
n 如果随机变量的分布函数随时间变化，对时间
集合T，得到一组随机变量，称之为随机过程
n 如果时间集合T离散，如T={0,1,2,…}，称为离散
时间的随机过程，{Xn: n∈T}
n 如果时间集合T连续，称为连续时间的随机过程，
{X(t): t∈T}
n 如果Xn或者X(t)离散/连续，称这个随机过程离散/
连续
2
n 例：
n 某路由器的IP包t时刻进入缓存等待转发，等待时
间{W(t): t>0}是一个连续时间的连续随机过程
n 从时间0到t到达路由器的IP包个数{N(t): t>0}是一
个连续时间的离散随机过程
n Xn表示一周7天中某一天某计算机启动的进程数，
n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的离散随
机过程。
n Xn表示一周7天中某一天某计算机的工作时间，
n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的连续随
机变量。
3
计数过程
n 令N(t)表示在时间段[0, t)内的某种事件发生的
次数。N(t)称为该事件的计数过程。计数过程
是一种随机过程。
n 事件：数据包到达路由器；顾客到达商店
n 性质：
1. N(0)=0
2. N(t)非负
3. 如果s
n 例，伯努力过程
n X1，X2，…是独立同分布的伯努力变量，成功的
概率为p。令Sn=X1+X2+…+Xn，即前n次伯努力实
验的成功次数，{Sn}是一个计数过程，被称为伯努
力过程。Sn的分布是二项分布。
[
P S
n
k
]
n
k
k
p
(1
p
)
n k
5
泊松过程
n 一个计数过程{N(t), t≥0}如果满足以下条件，则被称
为参数λ的泊松过程
1. 独立增量过程（即独立时间段上的事件发生的个数是独
立的）
2. 平稳过程（在任意一段时间内发生的事件个数的分布是
不变的）
3. 在一小段时间h内发生一个事件的概率为λh+o(h)。
4. 在一小段时间h内发生多于一个事件的概率为o(h)
n λ被称为泊松过程的速率
注意
lim
0
h
( )
o h
h
0
6
n 定理：{N(t)，t≥0}是一个速率为λ的泊松过程。Y表
示一段时间t>0内事件发生的个数，则
[
P Y
0,1,2,
,
k
e
k
]
k
参数为λt的泊松分布
t
(
)
t
!
k
( )
nP t
( ) [
0]
P t
0
( )(1
h o h
( ))
( )
P t
0
( )
dP t
0
dt
0( )
P t
t
e
7
n 证明：定义 ，
]
n
( )
P t P N t h N t
0
( )
P t
0
( )
[
P N t
)
(
( )
o h
h
( )
P t
0
(
(
)
P t h
0
)
P t h
0
h
取h→0
(
lim
0
h
)
P t h
0
h
( )
P t
0
( )
P t
0
( )
o h
h
代入初始条件 ，得到
0(0) 1
P
对时间t+h时n个事件发生的情况Pn(t+h)，三种情况
1. 时间t时已经发生了n个事件，
2. 时间t时发生了n-1个事件，[t,t+h)这段时间发生了1个事件
3. 时间t 时发生了n-k个事件， [t,t+h)这段时间发生了k个事
(
)
件，k>1
P t h
P t
n
n
取h→0，
( )
dP t
n
dt
( )(1
lim
0
h
( ))
t o h
)
(
P t h
n
h
( )
P t
n
( )
P t
1
n
( )
o h
( )
hP t
1
n
( )
P t
n
( )
P t
n
( )
P t
1
n
( )
o h
h
初始条件 ，迭代求解得到
0
e
( )
P t
n
t
(0)
nP
n
)
(
t
!
n
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
