第二讲 renewal process.doc

第二讲 更新过程课时：8学时（6小时）1. 更新过程2. 更新时刻，更新间隔，更新次数3. 更新方程4. 更新方程解的极限5. 更新过程的应用有一类过程具有如下特征：在一些特殊时刻观察过程，就概率意义而言，过程将是过去的重复。这些特殊时刻所对应的事件是一个随机事件的一个实现。一些例子例1 （Bernoulli试验）如果把成功时刻作为特殊时刻，那么从试验开始到成功这个事件，就在这些特殊的时刻不断地被重复。这些特殊的时刻构成了一个随机过程，其特点是相应的事件发生间隔时间，即增量过程是独立平稳过程，这里约定。也可以考虑其它的特殊时刻，例如连续两次成功实现的时刻，等等。可参见【5,Feller 第十三章 循环事件，更新方程】例2 （随机游动）随机游动中回到出发点的时刻。例3 （赌徒问题）赌徒的赌资回到他开始的时刻。例4 （设备更换）如果某种设备的寿命分布为，设备更换时刻，如果观测是从全新设备开始的，自然可设。此时，是设备的更新时间，服从的分布即为设备的寿命分布。同样，是独立同分布的。定义（更新过程）设非负随机变量序列是非负平稳独立增量过程，就称该过程为更新时刻过程，而称为更新间隔时间过程，是到时间发生的更新次数。一个更新过程必须首先确定更新间隔时间的分布，这是研究更新过程的先决条件。后面讨论都假定更新间隔时间的分布是已知的。问题1（Bernoulli试验中的更新过程）Bernoulli试验中，成功的间隔时间是独立同分布的，且分布律为，。这是间隔时间为离散分布的情况。而是第次成功的时刻，是到时刻成功的总次数。古典概率方法如何得到三个过程的分布？提示 间隔时间分布是几何分布，其和，即成功时刻的分布是负二项分布，而成功次数的分布是二项分布。即，1）（几何分布）：； 2）（负二项分布）：，；3）（二项分布）：。当然，Bernoulli试验可由每次试验结果所确定的独立随机过程：来刻划。这里是第次试验相应的随机变量，独立服从分布。显然，这是个平稳独立增量过程。问题1的习题1. 给出的矩母函数，并计算均值和方差。提示 ，利用Newton负二项公式：（对求阶导数即得），为理解一般的更新过程，这里采用另外的处理方法，以间隔时间作为出发点。在更新次数和更新时刻之间的关系，即“第次更新所需的试验次数不超过”等价于“在次试验中，更新的次数不少于次”。问题1的习题2利用上面更新次数和更新时刻的关系，由二项分布推导负二项分布。提示：记，即第次成功发生在时刻，显然。此处，给定。由全概率公式问题1的习题3. 验证负二项分布的分布律满足上述方程。直接要求解上述方程并不容易，但离散状态随机过程利用母函数常常更容易处理。记，即。利用条件数学期望。注意到，所以，。此即负二项分布的母函数。问题1的习题4. 由母函数确定。5. 直接利用得到的矩母函数。下面讨论更新次数的分布律。仍利用更新特点来处理。记，即到时刻，发生的更新次数为的概率。其母函数为。关于首次更新取条件概率，。问题1的习题6. 讨论时的方程，并验证是上述方程的解。提示 利用组合公式。同样，直接建立母函数满足的更新方程，。问题1的习题7. 验证是上述方程的解。8. 利用母函数方法求解上述方程。提示所以，由此，成功次数满足二项分布。过程的数字特征：平均更新次数。记，即到时刻，更新的平均次数，称其为更新函数。经典概率理论的结论，。同样可以用更新方法来得到结论。，这里用了结论：。由此该更新函数的母函数满足代数方程：，这里，。问题1的习题9. 证明：，从而。提示：，所以。问题2 泊松过程。讨论间隔时间服从指数分布的情况，即，参数。此时更新时刻是一个状态取连续值的过程，更新次数为随机过程。基本想法和问题1是一致的。确定的概率分布。同样利用首次更新方法，显然，所以。此处可计算重卷积：。问题2的习题。1. 证明 。（利用归纳法，或者直接计算）利用Laplace变换是处理更新方程的有效方法。定理1 （卷积的Laplac变换）。Laplace 变换的概率意义：。这里关于分布的Laplace变换与通常的记号有差异，通常定义，注意其不同，这种理解仅限于对分布函数，如有不同理解会特别指出。这里函数与分布的卷积记号与一般的记号稍有不同：，而不是通常的，换言之，按通常记号此卷积应记为，以后没有混淆，与分布的卷积都以此方式理解。问题2的习题。2. 证明定理1。提示 ，3. 特征函数方法：，其相应的分布为Erlang分布。用Laplace变换：，其逆变换即为密度函数。由此，。计算。因此。对更新次数和更新函数满足的方程的讨论。(1) 首先讨论概率，同样利用首次更新方法得，或。注意到，所以，可以得到（泊松分布）。问题2的习题4. 利用证明：。5. 由证明：。(2) 下面再讨论更新函数，即到时刻时的更新次数的期望值。从古典概率易知，。同样也可以按首次更新方法得到更新方程：。问题2的习题6. 证明上面的更新方程。7. 证明该更新方程的解为。提示 如果记更新函数的Laplace变换为，则，此处，即得，其逆变换函数为。问题3 作为特殊计数过程的Poisson过程可以不从更新过程的角度来理解。从应用随机过程来理解Poisson过程更具有启发性。如果计数过程（即取非负整数）是平稳独立增量过程。且具有如下性质：1） ；2）过程是平稳的：表示时间内事件发生的次数，其概率分布与相同；且增量过程具有独立性：任意给定，则随机变量序列是独立的；3） 无穷小特性：，此处。这个过程一定就是Poisson过程。这种方式定义过程更直观，容易把握。下面是从该定义出发，得到的一些过程性质的习题。问题3的习题1. 记，推导其满足的微分方程组。并证明该微分方程组的解为。2. 矩母函数，则。推导其满足的偏微分方程，由此得到其概率分布。3. 一个用于模拟泊松过程的结果。分布与上均匀分布产生的顺序统计量是相同的。提示 直接计算其联合密度函数。4. 证明；。提示 用更简洁的方式论证结论：上均匀分布得到的随机变量序列，而在条件下，到达时刻构成的序列是其顺序统计量，所以，因此。5. Suppose that customers arrive at a train depot in accordance with a Poisson process with rate . If the train departs at time , compute the expected sum of the waiting times of customers arriving in.（【Ross】p37）问题4 更新过程中的其它一些过程，Markov事件（停时）和Wald等式在更新过程中，还有一些其它随机过程需要关注。剩余寿命（Excess life）：时刻开始，最近一次更新发生的时刻。用更新时刻和更新次数来表示：。问题4的习题1. 对Poisson过程，剩余寿命的分布。提示 。年龄（current life）：到时刻，最后一次更新已过去的时间。用更新时刻和更新次数来表示：问题4的习题2. 对Psisson过程，计算年龄的分布。提示 寿命：包涵时刻的更新过程的时间间隔。利用更新时间和更新次数表示：。显然，有等式。3. 证明 对Poisson 过程证明 。提示 一般的更新过程，若，若，因此，如果记，则当，；当，。即，。因此，。对，若，则，若，则。问题4的习题4. 对Poisson过程证明：。（可见在特定时刻观测的寿命要长）提示 。5. 对Poisson过程证明剩余寿命和年龄的联合分布为。提示 （图示上述三个随机变量，更容易理解）在上述三个过程中，都涉及到随机变量和，即随机多个随机变量的和。对Poisson过程可以计算和，会发现它们的不同之处：，。问题4的习题6. 就Poisson过程验证上面的结论。提示 但，所以。对后者，所以，所以。所以。类似，可用此方法直接计算。，所以，所以。所以。产生这种差异的原因是什么？Markov 时间或停时：给定随机过程和取正整数值的随机变量，称后者是关于前者的一个Markov时间或停时，如果是由随机变量确定，与独立。下面的参考文献有助于对停时的理解。【Kai-Lai Chung】Introduction to Random time and Quantum Randomness, Mc Graw Hill, 2001问题4的习题7. 在Bernoulli试验中，首次成功所经过的试验次数是否是停时？成功次数达到100次所需的次数是否是停时？在更新过程中，对给定的时刻，如果是更新间隔时间，那么不是停时，而是停时。事实上，后者有随机变量决定。但则必须知道的信息。这是前面等式成立与否的关键因素。定理 （Wald等式）如果随机变量是关于独立同分布随机过程的停时，且，则有等式：。一般证明见【Ross,p59】。由于证明思想类似，所以这里只就更新过程的情况证明结论。证 ，后者即在事件发生时，相应的才加入和式。由于这里的随机变量是非负的，可对无限和也可进行和与积分的交换，所以，。同时，事件与独立，所以，与其余事件当然也独立，即与独立。所以，所以。问题4的习题上述证明对不是更新过程情况要作什么样的修改？对更新过程，可以利用首次更新方法给出另一种解决方法。利用首次更新方法建立的更新方程。由于，所以，即，该方程的解为问题4的习题8. 建立满足的更新方程，并就间隔时间是指数分布的情况求出解。提示 ，所以所以。问题5 一般更新过程当间隔时间不是指数分布，而是一般的分布，对更新过程处理的基本思想和方法是类似的，但计算结果会出现一些困难。更新时刻的分布：；更新次数的分布：。后者利用，则知。更新函数：。利用首次更新方法不难建立这些量的更新方程。问题5的习题1. 证明：记，则；对，。2. 证明: 记，则对，；。3. 证明：。对剩余寿命，年龄和寿命，其相应的更新方程就较复杂。问题5的习题4剩余寿命的补分布，证明。并求解方程。如果是Poisson过程，结果的explicit 表示式是什么？Hint 【Karlin,193】即无记忆性。5. 寿命的补余分布，证明。提示 ，而当，则；当，则。所以，6 建立年龄的更新方程。7. 确定的更新方程。问题6 一般更新方程和更新定理一般的更新方程：。这里，甚至不一定要求必须是分布函数，但本课程通常都假设其为分布函数，除非特别指出。形式上，方程的解为。经常要讨论时，解的特性。这类结论常常冠以更新定理名字。定理（基本更新定理1）对更新函数， 。证明 更新时刻与更新次数的一个不等式关系：是证明的关键。形式上，。如果，取极限，就能得到结论。但需要证明其次。方法：限制更新的时间上限，当超过某一给定时间一定要更新。（能否举例说明上述不等式不一定成立？）证明见【Karlin,p189】。对Poisson过程，。定理 （基本更新定理2）设是一个具有均值的正随机变量的分布函数。假设是一个直接黎曼可积函数，而是下面更新方程的解。（1）如果不是算术分布，那么；（2）如果是算术分布，步长为，则对，。特别，取，则，所以，（1）如果不是算术分布，则；（2）如果是算术分布，则对，结论仍成立。上面的定理证明较困难，待有简洁直观的证明方法再补上其证明。单调可积函数是直接Riemann可积的。还有其他一些充分条件。下面讨论这些定理的应用。问题6的习题1. 证明剩余寿命的极限分布为【Karlin，p193】。剩余寿命和年龄的联合分布：，因此其极限分布为，2. 证明寿命的极限分布为，提示 。3. 对指数分布，证明寿命极限分布的均值为：提示 ，其均值为：，可见，要大于原来的均值。4. 试就密度函数为的情况，证明上面的结论：平均间隔时间要小于极限寿命的均值：。5. 应用基本更新定理2可以得到比定理1更深入的结果：。提示 可以推导满足的方程：表示成更简洁形式：而，因此。所以更新方程中是否有限，对极限结果有决定性影响。如果积分无限，则需找出其等价的无穷大项。问题7 从Laplace变换来形式上推导极限（本节内容是启发性的）如果函数的Laplace变换函数为，形式上，。即如果极限存在，确实可用来计算，但反之不见得正确，主要是函数可能在振荡。例如，则，不能得到充分性结论。思考题 什么条件能得到条件的充分性？在什么条件下？以此想法，来得到极限形式上的结果。更新函数的极限：从更新方程得到其Laplace变换，但，即。而函数的Laplace变换为：，所以，。一般更新方程解：由更新方程得，由此。更新定理的深入结果：的Laplace变换函数为，所以同样，离散时间离散状态的随机过程同样可以讨论矩母函数用来计算极限分布律问题。对Bernoulli试验，相应的更新函数成立，或写为：。对一般的离散时间的更新过程，形式上能否用矩母函数处理极限问题？形式上，若，则。事实上，因此。希望讨论一般的问题：，则序列极限的性质如何用描述。如果，那么上述结论是否正确？并不是很直观的：例如。由于在处发散，所以必须对序列收敛速度有一定要求，保证在处收敛。又如：，则。问题7的习题1. Show that , where is the variance of a renewal process and and are the mean and variance, respectively, of the interarrival distribution.Hint .Hence，it is sufficient to prove .The renewal equation for , by the first renewal time technique,.Approach 1. Laplace transformation.We only need to find , because by,the following results is derived,.If we only want to find , it is sufficient to find the coefficients .By , .But , here the 2-order expansion is sufficient., hence, . So,.Approach 2. The renewal theorem. Find the renewal equation for .,.The main task now is to find the integral.Too complicated to calculate.问题8 终止更新过程有缺省情形下的更新过程：，即更新间隔时间可以是，即，此意味着即使是无限长时间，更新次数也可能是有限的。事件当且仅当前面的次更新间隔时间必须是有限，即，即得。由此，。但是，有限时间内更新次数仍成立，所以更新函数仍满足更新方程：。其相应的Laplace变换函数：，因此形式上，。对一般的有缺省的更新型方程有一种方法，可化为正常的更新方程来处理。注意到是一个连续函数，且，所以，可以找到，使，因此如果令，那么该函数就是一个正常分布函数。相应的更新方程：。由于，所以不能确定。由于，已知，那么收敛速度如何？相应的更新方程，不难计算，计算其积分所以。问题9 更新次数的极限分布问题10 风险理论中的应用设是时间内发生的理赔次数。假设该事件发生的次数服从泊松分布。每次理赔的数额是独立同分布的随机变量，分布函数为。假设公司的初始资本为，单位时间的收入为。那么公司的不破产的概率是多大？ 公司时刻的现金流为：。不破产的概率为。利用更新理论的思想：显然，若，则，因此，（变量代换：）关于求导：或：。得到更新方程记。由于，因此是一个密度函数。方程为习题1. If , , compute, , .hint , .2. A particular arrive at a doctors office. With probability he receives service immediately, while with probability his service is deferred an hour. After an hours wait again with probability his needs are serviced instantly or another delay of an hour is imposed and so on.(a) What is the waiting time distribution of the first arrival?(b) What is the distribution of the number of patients who received service over an 8-hr period assuming the same procedure is followed for every arrival and the arrival pattern is that of a Poisson process with parameter 1.hint (a) Denote as the time he waited. Then ,.(b) 问题需要叙述得更明确。开门时，是否一定有一个顾客到达；服务的开始时间是否总是在整点？每小时服务的顾客数只可能是0个，一个。但如何按更新过程来理解？3. Consider repeated independent trials of two outcomes S (success) or F (failure) with probabilities and , respectively. Determine the mean of the number of trials required for the first occurrence of the event SF (i.e., success followed by failure). Do the same for the event SSF and SFS.Hint 记为首次SF的时刻。，则。注意到，即得递推关系，；。后面处理较简单。或记，则。但在分布意义下，所以。因此，。其余问题简单。关于SSF，对，注意到，对，得到差分方程，整理得，而，。类似可用母函数处理。【karlin,p230】2. Find in a renewal process having lifetime densityWhere is fixed.Hint ., its inverse transformation, ,.【Karlin,p154】11 Suppose is the conditional rate of failure of an article at time , given that it has not failed up to time , i.e.,as . Assume that is positive and continuous on . Find an expression forin terms of .Hint Derive a differential equation for . .12 Consider a variable time Poisson process, i.e., the occurrence of an event during the time duration is independent of the number of previous occurrences of and its probability is (). (Note that may now depend on .)(a) Prove that the probability of no occurrence of during the time duration is.(b) Prove that the probability of occurrences of during the time duration is.(c) Find the mean number of occurrences of during the time duration .3. Through its lifetime, itself a random variable having distribution function , an organism produces offspring according to a non-homogenous Poisson process with intensity function . Independently each offspring follows the same probabilistic pattern, and thus a population evolves. Assuming,show that the mean population size asymptotically grows exponentially at rate , where uniquely sholves.Hint 需要对模型作一些假设：organism的后代是否是在其消失的时刻产生。否则，就须对产生后代的方式做一些假设。换言之，每个organism的后代都是同时产生的，且同时原来的organism消失。如果记是后代个体总数，则。对，而时，。因此。由，因此，不是分布函数。则方程为由条件，存在常数，使，因此变换分布函数，则，则得到更新方程，。所以4. For a renewal process with distribution compute .Obtain this explicitly for a Poisson process with parameter and also explicitly when .Hint Denote, (zero is included).It is note difficult to find and .For Poisson process, we can directly to find the differential equations for and .,., and . Using Laplace transformation is more easy to find the solution: ,., hence, , ,.思考题 为何对一般的更新方程，此方法就不能奏效？5. Show that the renewal function corresponding to the lifetime density,is .6. Let be i.i.d. uniformly distributed on . Define be the index satisfying (the kth powers). Determine.Hint Denote , . The density function.,But the limit is about , it is not easy to find the explicit expression of .Pay attention to the fact is a Markov time corresponding to , by the Walds equality, .Whether can we prove that ?10. Show that the age in a renewal process, considered as a stochastic process, is a Markov process, and derive its transition distribution function.Hint A diagram of the process is useful to understand the following results.If denotes the residual life, its density function is.And .11. Suppose solves the renewal equation , where is a bounded non-decreasing function with . Establish that , where and is the mean of .Hint. By Laplace transform, it is easy to understand the result., that is, ., but , it is the key to consider., hence, .Hence, , which means, .But , that is, ，or,It means .A mathematic vigorous proof. If we know the result, it is easy to find an accurate proof.,We only need to calculate .12. Consider a system that can be in one of two states: “on” or “off”. At time zero, it is “on”. It then serves before breakdown for a random time with distribution function . It is then off before being repaired for a random time with the same distribution . It then repeated a statistically independent and identically distributed similar cycle, and so on. Determined the mean of , the random variable measuring the total time the system is operating during the interval .Hint.13. Successive independent observations are taken from a distribution with density functionuntil the sum of the observations exceeds the number . Let be the number of observations required. Prove that.Hint. 。But , , which means .And Hence, .14. A renewal process is an integer-valued stochastic process that registers the number of points in , when the interarrival times of the points are independent, identically distributed random variables with common distribution function for and zero elsewhere, and is continuous at . A modified renewal process is one where the common distribution function of the interarrival times has a jump at zero. Show that a modified renewal process is equivalent to an ordinary renewal process, where the numbers of points registered at each arrival are independent identically distributed random variables, with distribution,for all , where .Hint. What is the meaning of equivalent here? The distribution of is same?For , 15. Consider a renewal process with underlying distribution function . Let be the time when the interval duration from the preceding renewal event first exceeds (a fixed constant). Determine an integral equation satisfied by.Calculate . (Assume an event occurs at time .)Hint. For ,. Hence, assume that . Then.So, ,.16. Consider a renewal process with associated distribution function . Define . Show that satisfies the renewal equation where.Hint. .17. (Continuation of Problem 16). By induction show that.18. Consider a stochastic process , , which alternation in two states and . Denote by the successive sojourn times spent in states and , respectively, and suppose is in . Assume are i.i.d.r.v.s with distribution function and are i.i.d.r.v.s with distribution function . Denote by and in total sojourn time spent in states and during the time interval . Clearly, and are random variables and . Let be the renewal process generated by . Define .Prove ,and express this in terms of the distribution and .Hint. It is necessary to study the alternative renewal process completely.19. Consider a renewal process with distribution . Suppose each event is erased with probability . Expand the time scale by a factor . Show that the resulting of events constitutes a renewal process where the distribution function of the time between events iswhere as usual denotes the -fold convolution of .Hint. If the inter-arrival time is for the new renewal process, then the original duration time is .注 如果不考虑时间标度变换，事件是所有事件“原来的更新过程中，内事件发生的次数至少是次，但前次被删除，而第次被保留”的并，而不是事件“原来的更新过程中，内事件发生的次数是次，但前次被删除，而第次被保留”的并。20. (continuation of problem 19). In the preceding problem let be the Laplace transform of . Determine the Laplace transform of .Hint. 21. (continuation of the above problem). If has two moments, prove that, as , for all , ,where .Hint. .22. (continuation of the above problem). Appealing to the convergence theorem, prove that.(如果从更新次数入手，应该有，就有一个数学分析问题：。用分析方法如何直接证明？)23. Consider a renewal process with interarrival distribution . Suppose each event is kept with probability and deleted with probability , and then the time scale is expanded by . Show that the mean interarrival time is the same for the original and the new process. Repeat the above operation of deletion and scale expansion to obtain a sequence of renewal process with interarrival distribution given by after such transformations of the process. In all these operations is held fixed. Show that if , then,where .Hint. .24. Consider a triangular array of identically distributed renewal process , , where the interarrival times have a distribution with mean . Consider t