更新过程(硕士)

更新过程及理论关键词：更新函数， 极限定理， 更新报酬过程， 再生过程

§1 引言与基本定义以N (t ) t 0表示在时间间隔 0, t 内出现得质点数(事件A发生次数)

N (t ), t 0 是一状态取非负整数、时间连续的随机过程，称为计数过程。

定义：泊松过程称计数过程{N(t),t≥0}为具有参数λ >0的泊松过程，若它满足下列条件： 1. N(0)=0; 2. N(t)是独立增量过程； 回顾 泊松过程

3. 在任一长度为t的区间中，事件A发生的次数服从参数λ>0的泊松分 布，即对任意s,t≥0,有

P{N(t s) N( s) n} e t

( t ) n , n 0,1, n!

定理一：强度为λ 的泊松流(泊松过程)的点间间距是相互独 立的随机变量，且服从同一指数分布。记X i Si Si 1 i 1, 2, S0 0, 称为相继出现的第i 1个质点和第i个质点的点间间距。 e t t 0 X i的概率密度为：f X i t 即 X i , i 1, 2, 服从同一个指数分布。 t 0 0

Si X j 服从 n, 分布。j 0

i

定理二：如果对于计数过程任意相继出现的两个质点的点间间距 Xn是相互独立，且服从同一个指数分布： e t t 0 f t t 0 0

则计数过程构成强度为λ 的泊松过程

自然延伸—更新过程

令{N (t ), t 0}是一个计数过程，而以X n记这个过程的第n 1个和第 n个事件(质点)之间的时间，n 1.

定义1:如果非负随机变量列{ X 1 , X 2 , }是独立同分布的，那么计数过程 {N (t ), t 0}称为更新过程。理解：一个更新过程，其直到第一个事件发生的时间具有某个分布F,第 一个和第二个事件之间的时间独立于的一个事件的时间，且具有相同分 布F ,以此类推，当一个事件发生时，我们说发生了更新。

举个例子：假设有无穷多个灯泡，它们的寿命是独立同分布的。当 一个灯泡失效后，立刻换上新的。若N (t )表示直到时间t为止失效的 灯泡个数，则{N (t ), t 0}是一个更新过程。

X1

X2 S1 S2

Xn

Sn 1

Sn

Sn X ii 0

n

以F 记到达间隔分布，假设F (0) P ( X n 0) 1,令

E[ X n ],

n 1

是相继更新之间的平均时间，显然 0。

结论一：对于t的某个(有限的)值，N (t )必定有限。证明：由强大数定律，以概率1 Sn , 当n 时 n 因为 0,当n 时，S n必趋向于无穷。因此，对于有限值t,至多只有有限个n,使Sn t. 因为，N (t ) sup{n : Sn t}, 所以N (t )必有限。结论得证。 结论二：当t 时，N (t ) 或 N ( ) limt N (t )

证明：因为使更新总数N ( )有限的唯一方法是有一个来到间隔 无穷大，所

以 P{N ( ) } P{ X n , 对某个n} P{ { X n }}n 1

P{X n } 0n 1

§2 N(t)的分布更新过程中，N (t ) n S n t

即时间t之前的更新次数大于等于n当且仅当第n次更新发生在时间t或t之前.

因此 P{N (t ) n} P{N (t ) n} P{N (t ) n 1} P{S n t} P{S n 1 t}

随机变量X i 独立，且具有相同分布F,由此推出 Sn i 1 X i与F的n次卷积Fn同分布，得到n

P{N (t ) n} Fn (t ) Fn 1 (t )说明：更新过程由到达间隔分布确定。

进而可以计算N (t )的均值m(t ), m(t ) E[ N (t )] Fn (t )证明：N (t ) I nn 1

n 1

1 其中I n 0因此，

若第n次更新发生在[0,t]内 其它

E[ N (t )] E[ I n ] E[ I n ] P{I n 1} P{S n t} Fn (t )n 1 n 1 n 1 n 1 n 1

结论一：m(t ) , 对于一切t 证明：因为P{ X n 0} 1,由概率的连续性可知存在一个 0,使得 P{ X n } 0。 定义一个关连的更新过程{ X n , n 1}如下：

0,若X n Xn ,若X n 且令 N (t ) sup{n : X 1 X 2 X n t}。易知此更新只能在时刻t n 处发生，n 0,1, 2, , 且这些时刻的 更新次数是独立的几何随机变量，其均值为 1 P{ X n }

于是 (t / 1) E[ N (t )] P{ X n }且因X n X n,意味着N (t ) N (t ),结论得证。

结论二：更新函数的积分方程： m(t ) F (t ) m(t x ) f ( x)dx0 t

证明：对首次更新时间取条件，可得 m(t ) E[ N (t )] E[ N (t ) | X 1 x] f ( x)dx0

由于更新过程概率地在一次更新发生后重新开始，可得 1 E[ N (t x)] E[ N (t ) | X 1 x] 0 若x t 若x t

m(t )的表达式转化为： m(t ) (1 E[ N (t x)]) f ( x) dx (1 m(t x)) f ( x) dx0 0 t t

F (t ) m(t x) f ( x) dx0

t

称为更新方程。

例1:若到达间隔分布遵循(0,1)上的均匀分布，利用更新方程 求更新函数表达式。

解：m(t ) t m(t x)dx=t m( y)dy0 0

t

t

(令y t x)ln h(t ) t C

两端求导：m '(t ) 1 m(t )

令h(t ) 1 m(t ),易得：h '(t ) h(t )得：h(t ) Ket 或 m(t ) Ket 1

或

由m(0) 0, 可得K 1, 得到m(t ) et 1

§3 若干极限定理前面已得当t 时，N (t ) ,感兴趣的是N (t )趋于无穷的速度，即 了解 limt N (t ) 的情况。 t

先引入两个记号：S N (t )和S N (t ) 1 , 其中 S N (t ) 表示时刻t之前或在时刻t最后一次更新的时刻； S N (t )+1表示时刻t之后第一次更新的时刻；

命题1:以概率1,

当t 时， N (t ) 1 t

证明：由于 S N (t )

S N ( t ) t S N ( t ) 1,可见 (1)是N(t)个独立同分布随机变量的

S N (t ) 1 t N (t ) N (t ) N (t )N (t )

由于S N (t ) /N (t ) i 1 X i / N (t )

平均值，由强大数定律推出当N (t ) 时，S N (t ) /N (t ) 又因为t 时，N (t ) , 得到t 时 S N (t ) N (t )且同样推理，可得 S N ( t )+1 S N ( t )+1 N (t ) 1 N (t ) N (t ) 1 N (t ) 当t

由()式，t / N (t )介于两个变量之间，当t 时，都收敛于 ,结论得证。 1

注：() 1/ 称为更新过程的速率，即以概率1,长时间后更新 1 发生的速率将等于1/

(2)(基本更新定理)

m(t ) 1 t

当t 时

例2:贝弗利有一台使用单个电池的收音机，一旦电池失效，贝弗 利立刻换上新电池。如果电池寿命(小时)在区间(30, )上均 60 匀分布，那么贝弗利以什么速率更换电池？

解：以N (t )记到时刻t为止失效的电池个数，由命题1更换电池速率为 N (t ) 1 1 lim t t 45

从长远来看，贝弗利必须每45小时更换一次电池。

例3:假设例2中，贝弗利手头没有任何多余电池，而每次失效时， 他必须去购买新电池，如果他买到新电池需要用的时间在(0,1) 均匀分布，则他以什么速率更换电池？解：两次更换之间的平均时间由 EU1 EU 2给出，其中U1在 (30,60)均匀分布，U 2在(0,1)均匀分布.因此， =45+0.5=45.5

从长远来看，贝弗利应该以2/91的速率放新电池，即每91小时 更换两次电池。

命题2:E[ S N (t ) 1 ] [m(t ) 1]证明：令g (t ) E[ S N (t ) 1 ],对首次更新时间取条件，得到 g (t ) E[ S N (t ) 1 | X 1 x] f ( x)dx0

由于更新过程概率地在一次更新发生后重新开始， x g (t x) E[ S N ( t ) 1 | X 1 x] x代入可得 g (t ) g (t x ) f ( x )dx + xf ( x )dx0 0 t

若x t 若x t

或 g (t ) g (t x) f ( x)dx0

t

实际上，令g1 (t ) g (t ) / , 可得 g1 (t ) 1 1 [ g1 (t x) 1] f ( x)dx0 t

整理得到 g1 (t ) F (t ) g1 (t x) f ( x)dx0

t

与更新方程对比：m(t ) F (t ) m(t x) f ( x)dx0

t

即g1 (t )

E[ S N (t ) 1 ]

1满足更新方程，由唯一性，等于m(t ), 结论得证。

命题3:更新过程的中心极限定理 N (t ) t / 1 lim P x 2 3 t 2 t /

x

e

y2 / 2

dy

证明：令rt t / x t 2 / 3,则 N (t ) t / P x P N (t ) rt P{S rt t} t 2 / 3 S r S r rt

t r x t rt t t P P x 1 2 2 t rt rt 2 rt S r 由中心极限定理，当t(于是rt ) 时，rt t 1/ 2

rt2

收敛于

均值为0, 方差为1的正态随机变量。

x 又因为t 时， x 1 t

1/ 2

x

N (t ) t / 1 可见，P x 2 3 2 t / 又因为 1 2

x

x

e

y2 / 2

dy

x

e

y2 / 2

1 dy 2

e

y2 / 2

dy

结论得证。说明：对于较大的t,N (t )是渐进正态的，均值为t / ,方差为 t 2 / 3,其中 和 2分别是到达间隔分布的均值与方差。

例3:两台机器相继地处理无穷多个零活。在机器1上处理一个零活 的时间是参数为n=4和 =2的伽玛随机变量，而在机器2上处理一个 零活的时间在0和4之间均匀的分布。求到时间t=100为止，两台机器 一起至少可以处理90个零活的概率的近似值。解： 1 (t ), t 0}和{N 2 (t ), t 0}分别代表两台机器到时刻t可以处理的 {N 零活数，则是两个相互独立的更新过程。

机器1的更新过程的到达间隔分布为参数为n=4和 =2的伽玛随机变量， 故均值为2,方差为16/12。

故均值为2,方差为1。机器2的更新过程的到达间隔在0和4之间均匀分布