Regenerative Processes

Size: px

Start display at page:

Download "Regenerative Processes"

迫歪项
5 years ago
Views:

1 Regenerative Processes Václav Kozmík Faculty of Mathematics and Physics Charles University in Prague 11 / 12 / 212

2 Regenerative Processes Recall basics from renewal theory Basic limit theory of regenerative processes Examples and applications Time-average properties Rare events and extreme values

3 Renewal theory Definition Let S S 1 < S 2 < be the times of occurrences of some phenomenon and Y n = S n S n 1, Y = S. Then {S n } n N is called a renewal process if Y, Y 1, Y 2,... are independent and Y 1, Y 2,... (but not necessarily Y ) have the same distribution. Common distribution of Y 1, Y 2,... = inter-arrival distribution F Number of steps needed to reach time t: N t = inf {n : S n > t} Backward recurrence time process {A t } t, A t = t S Nt 1 Forward recurrence time process {B t } t, A t = S Nt t Notation µ = EY 1, F = 1 F F distribution with density f = F µ

4 Renewal theory Renewal function U(t) = F n (t) Theorem (Key renewal theorem) Suppose that the function z in the renewal equation Z = z + F Z is d.r.i. Then Z(t) = U z(t) 1 µ z(x)dx, t

5 The classical definition of a stochastic process {X t } to be regenerative means in intuitive terms that the process can be split into i.i.d. cycles. A basic Regenerative example is the Processes GI/G/1 queue length process and its busy cycles, i.e. the time intervals separated by the instants S n with a customer entering an empty systems; cf. Fig At each such instant the queue regenerates, i.e. Processes that can be split into i.i.d. cycles. starts completely from scratch independently of the past. Different cycles are Busy independent cycles of and theall GI/G/1 governed queue by length the same process probability law. Similar statements different holdcycles for the are workload independent orand other have processes the sameassociated probabilitywith the system. distribution Figure 1.1 This structure with i.i.d. cycles is found in the majority of examples and

6 Regenerative Processes X t has state space E, t T discrete or continuous Definition We call {X t } t T regenerative (pure or delayed) if there exists a renewal process (pure or delayed) {S n } = {Y + + Y n } with the following property: for each n the post-s n process θ Sn X = ( Y n+1, Y n+2,..., {X Sn+t} t T ) is independent of S,..., S n and its distribution does not depend on n. S n is called embedded renewal process, S n are regeneration points embedded process is not unique: consider {S 2n } or start of the idle part in M/G/1 k-th cycle {X t+sk } t Yk+1

7 Regenerative Processes Zero-delayed version {X S +t} t T with E, P Y = Y 1 length of the cycle, µ = E Y Cycles need not be i.i.d. as will be seen later Proposition (1.1) If {X t } t T is regenerative and ϕ : E F any measurable mapping, then {ϕ(x t )} t T is regenerative with the same embedded renewal process.

8 Regenerative Processes Theorem (1.2) Assume that a (possibly delayed) regenerative process {X t } t T has metric state-space, right-continuous paths and non-lattice cycle length distribution F with mean µ <. Then the limiting distribution P e exists and is given by: E e f (X t ) = 1 µ E Y f (X s )ds Similar statement for the total variation convergence can be found in the book, also covering discrete time case and periodicity

9 Regenerative Processes Proof. Let f be an indicator f (t) = I [Xt A], then f 1. Let Z(t) = E [f (X t )], z(t) = E [f (X t ), t < Y ], F (x) = P [Y x]: t E [f (X t )] = E [f (X t ), t < Y ] + = E [f (X t ), t < Y ] + t E [f (X t ), Y = x] F (dx) = Z(t x)f (dx) Let t then it is sufficient to show that Z(t) E e f (X t ). We have following renewal equation: t Z(t) = z(t) + Z(t x)f (dx)

10 Regenerative Processes Proof. Function z is right-continuous, hence continuous a.e. z(t) z (t) = P [Y > t], with z non-increasing, Lebesgue integrable. Hence z is d.r.i. We apply Key renewal theorem: Z(t) 1 µ E [f (X t )] 1 µ = 1 µ Y = 1 µ E Y z(x)dx E [f (X s ), s < Y ] ds = E [f (X s )] ds = f (X s )ds

11 Regenerative Processes Proposition (1.3) Let {X t } t T be regenerative and {A t } t Y the backward recurrence time process of the embedded renewal process. Further let f : E R be measurable and bounded and define g(t) = E [f (X t ) Y > t]. Then E [f (X t )] = E [g(a t ), Y t] + E [f (X t ), Y > t]. In particular, in the zero-delayed case E [f (X t )] = E [g(a t )]. Follows by the same renewal argument as in previous theorem

12 Examples Limiting distributions of recurrence times A t, B t of a renewal process: For t < Y : A t = t, B t = Y t The limiting distribution of both recurrence times is the same: P [A t ξ] = 1 µ E = 1 µ E Their common value: Y Y Y I [At ξ]dt = 1 µ E I [Y t ξ] dt = P [B t ξ] I [t ξ] dt 1 µ E I [t ξ,t<y ] dt = 1 µ ξ P [t < Y ] dt = 1 µ ξ F (t)dt = F (ξ)

13 Examples Limiting distribution of current life C t of a renewal process: P [C t ξ] = 1 µ E Y Y I [Ct ξ]dt = 1 µ E = 1 µ E [Y ; Y ξ] dt = 1 µ ξ I [Y ξ] dt xf (dx)

14 Examples Alternating renewal process Y, Y 2,... distribution G, Y 1, Y 3,... distribution G 1 For example Y 2k 1 lifetime of the k-th item and Y 2k time needed to replace it System regenerates at points Y + Y 2k { if Y + Y X t = 2k 1 t < Y + Y 2k for some k 1 if Y + Y 2k t < Y + Y 2k+1 for some k p(t) = P [X t = 1] probability that the system is operating at time t Cycle length Y 1 + Y 2 with distribution F = G G 1 Suppose F non-lattice with µ = EY + EY 1 < For Y = we have: lim p(t) = 1 Y1+Y 2 t µ E I [Xt=1]dt = 1 µ EY EY 1 1 = EY + EY 1

15 Examples Reflected Brownian Motion {X t } reflected Brownian motion with drift µ < and variance 1, starting from X = We can view the cycles as excursions away from, but inf {t : X t = } = Consider: It can be shown that τ(1) = inf {t > : X t = 1 X = } Y = inf {t > τ(1) : X t = X = } E [τ(1)] = 2µ + exp { 2µ} 1 2µ 2

16 Examples Regenerative simulation Task: numerically determine θ = E e f (X t ) For example {X t } queue length process: f (x) = x leads to θ being a mean queue length in a steady state f (x) = I [x N] leads to θ being a probability of queue length at least N Simulating from the distribution P e directly is difficult Steady state is unknown We can start and simulate to some large time T, then compute f (X T ), but it s inefficient and there is uncertainty about the choice of T Simulate i.i.d. regenerative cycles, n = 1,..., N: Y We want to compute 1 µ E f (X s)ds Y From each cycle observe R n (1) = Y and R n (2) = E f (X t)dt Let ˆµ = 1 N N n=1 R n(1), ˆν = 1 N N n=1 R n(2) and ˆθ = ˆνˆµ Estimators are consistent by LLN, with i.i.d. cycles we can obtain asymptotic normality and confidence intervals

17 Examples More general functionals of regenerative processes We may study max k=,...n X n+k or t+h X t s ds Tuples (X Y, X Y +1 ) and (X Y 1, X Y ) belong to the distinct cycles, but may be dependent The definition of a regenerative process does not require independence with the pre-s n process {X t} t<sn Let θ t X = {X t+s } s T Also regenerative with the same embedded renewal process {S n}

18 Examples Theorem (2.1) If {X t } satisfies the condition { } for existence of a limit of X t, then also θ t X has a limit X (e) = (weakly for T = [, ), in total variation for T = N): X (e) t t T ] E e [ϕ(x (e) ) = 1 Y [ ] Y µ E ϕ(θ t X )dt = E µ ϕ(θ UY X ) for any nonnegative or bounded ϕ where U is uniform on { (,} 1) and independent of the regenerative process. Furthermore, strictly stationary. X (e) t t T is

19 Time-average properties Definition Real-valued process {Z t } is called cumulative if Z = and there exists a renewal process {S n } such that for any n: {Z Sn+t Z Sn } t is independent of S,..., S n and {Z t } t<sn and the distribution is independent of n. Basic example: Z t = t f (X s)ds {X t } regenerative with i.i.d. cycles We will write Z t = U (t) + U U Nt 1 + t U (t) = Z t S, U n = Z Sn Z Sn 1, t = Z t Z SN t 1 U (t) eventually becomes negligible, to handle t define V n = max t S n 1 t<s n V 1, V 2,... i.i.d. with V n D = V

20 Time-average properties Assume V < and µ = E Y < Theorem (3.1) Suppose µ = E Y <, E U < and let z = E U µ. Then a.s. z if and only if E V <. Z t t In the regenerative example we may write EU 1 µ as E ef (X t ) Theorem (3.2) Assume var U <, var Y <. Then the limiting distribution of exists and is normal with mean zero and variance σ2 µ where Z t t z t σ 2 = var [U zy ]

21 Rare events Example with state space E = [, ) Rare event of exceeding the level x: τ(x) = inf {t > : X t > x} Let X T = max t T X t, then P [τ(x) > T ] = P [ XT x ] Consider a family of cycle events {A(x)} x Measurable sets indexed by parameter x Suppose property that A(x) x ] Let a(x) = P [{X t } t<y A(x) It follows that a(x) x Define M(x) index of first cycle in which A(x) occurs: M(x) = inf {n =, 1,... : { } } X t+y + +Y n 1 t<y n A(x)

22 Rare events Let ω(x) = Y + Y Y M(x) 1, ω(x) = Y + Y Y M(x) Rare event occurs between ω(x) and ω(x) M(x) is geometric with parameter a(x) and the mean time is µ(x) = µe M(x) = µ a(x) Proposition (4.1) For all x, E ω(x) = µ(x). Further, for a delayed process with EY <, a(x)eω(x), a(x)eω(x) both converge to µ as x.

23 Rare events Theorem (4.2) As x it holds that a(x)ω(x) D µv, a(x)ω(x) D µv, where V is standard exponential. Further, a(x) (ω(x) ω(x)) P. Example: {X n } positive recurrent Markov chain with state space {, 1,...}, p x > x First jump from to x: τ(, x) = inf {n > : X n 1 =, X n = x} A(x) = {X n 1 =, X n = x for some n} We take every visit to state as the start of the cycle: A(x) = {X =, X 1 = x} a(x) = P [A(x)] = p x µ = E [Y ] = 1 π, where (π, π 1,... is the stationary distribution Since ω(x) τ(, x) ω(x): p x τ(, x) is asymptotically exponential with mean 1 π.

24 Extreme values Classical extreme value theory: find s T, r T such s T ( X T r T ) has a limit Γ in distribution, in the i.i.d. case only three types are possible I Gumbel P [Γ G x] = exp { exp { x}} II Fréchet P [Γ F x] = exp { x α } III Weibull - only in the case of bounded support Proposition (4.9) Assume that E is a real interval unbounded to the right and that a(x) = P [τ(x) < Y ] c exp { γx} as x continuously for some c > and some γ >. Then where Γ G is Gumbel. γ X T log T log(c /µ) D Γ G, T

25 Extreme values Proposition (4.1) Assume that E is a real interval unbounded to the right or that E contains a set of the form {n, n + 1,...} and that a(x) L(x)/x α where α > and L(x) is slowly varying. Then X T b(t /µ) D Γ F, T where Γ F is Fréchet and b(x) is determined by L(b(x))/b(x) α 1/x. Definition A function L : (, ) (, ) is called slowly varying (at infinity) if for all a > : L(ax) lim x L(x) = 1

26 References Asmussen, S. (23): Applied Probability and Queues, Second Edition, Springer, New York, ISBN Wikipedia

27 Conclusion Thank you for your attention! Václav Kozmík

Stochastic Processes (XI) Hanjun Zhang School of Mathematics and Computational Science, Xiangtan University 508 YiFu Lou talk 06/

Stochastic Processes (XI) Hanjun Zhang School of Mathematics and Computational Science, Xiangtan University hjzhang001@gmail.com 508 YiFu Lou talk 06/04/2010 - Page 1 Outline 508 YiFu Lou talk 06/04/2010