6.262: Discrete Stochastic Processes Lecture 5: Poisson combining and splitting etc. Outline: • Review of Poisson processes • Combining independent Poisson processes • Splitting a Poisson process • Non-homogeneous Poisson processes • Conditional arrival densities Review of Poisson processes A Poisson process is an arrival process with IID exponentially-distributed interarrival times. It can be represented by its arrival epochs, S1, S2, . . . , or by its interarrival times, X1, X2, . . . or by its count ing process, {N (t); t > 0}, where X3 ✛ ✛ ✛ 0 X1 � � X2 ✲ ✲ S1 � ✲ {Sn ≤ t} = {N (t) ≥ n} ✻ N (t) N (t) = n for Sn ≤ t < Sn+1 t S2 S3 The interarrival times Xi of a Poisson process are memoryless, i.e., for x, t > 0, Pr{Xi > t + x | Xi > t} = Pr {Xi > x} = exp(−λx) ✛ ✲� Z ✛ ✲ X3 � ✻ ✛ X ✲ N (t) 2 N (t) = n for Sn ≤ t < Sn+1 � ✛ ✲ X1 t 0 S1 S2 S3 Given N (t) = n and Sn = τ , we have Xn+1 > t − τ . The interval Z = Xn+1 − (t − τ ). � � Pr Z > z | N (t), SN (t) = exp(−λz) Z is independent of {N (τ ); τ ≤ t}; Z is the ﬁrst in terarrival of the Poisson process {N (t�)−N (t); t� > t}; {N (t�)−N (t); t� > t} is independent of {N (τ ); τ ≤ t}. For any set of times, 0 < t1 < t2 < · · · tk , the Poisson �(t , t); t 0, then the process is Poisson. Thm: If an arrival process has the stationary and independent increment properties and satisﬁes the following incremental condition, then the process is Poisson. � � �(t, t+δ) = n = Pr N    1 − λδ + o(δ) λδ + o(δ)   o(δ) for for for n=0 n=1 n≥2 Combining independent Poisson processes Two Poisson processes {N1(t); t>0} and {N2(t); t>0} are independent if for all t1, . . . , tn, the rv’s N1(t1), . . . , N1(tn) are independent of N2(t1), . . . , , N2(tn). Thm: if {N1(t); t>0} and {N2(t); t>0} are indepen dent Poisson processes of rates λ1 and λ2 and N (t) = N1(t) + N2(t) for all t > 0, then {N (t); t>0} is a Pois son process of rate λ = λ1 + λ2. The idea is that in any increment (t, t+δ], �(t, t+δ) N pN� (t,t+δ)(1) = = � (t, t+δ) + N � (t, t+δ) N 1 2 (1)pN� (t,t+δ)(0) 2 + pN� (t,t+δ)(0)pN� (t,t+δ)(1) 1 2 = pN� 1 (t,t+δ) [δ λ1 + o(δ)][1 − δλ2 + o(δ)] + [1 − δλ1 + o(δ)][δλ2 + o(δ)] = δ(λ1 + λ2) + o(δ) �(t, t+δ) = 0 if both N � (t, t+δ) = 0 and Similarly, N 1 � (t, t+δ) = 0. Thus N 2 � � �(t, t+δ) = 0 = [1 − (λ + λ )δ + o(δ)] Pr N 1 2 It is much cleaner analytically to use the Poisson � (t, t+δ) and N � (t, t+δ) distribution directly. Since N 1 2 are independent and Poisson, �(t, t+δ) = N � (t, t+δ) + N � (t, t+δ) N 1 2 is a Poisson rv with mean λδ. The sum of many small independent arrival pro cesses tends to be close to Poisson even if the small processes are not. In a sense, the independence between the processes overcomes the dependence between successive arrivals in each process. Splitting a Poisson process N (t) rate λ ✟✟ ✟✟ ✟ ✟✟ ✲✟ ❍❍ ❍❍ ❍❍ ❍❍ p 1−p N1(t) rate λ1 = pλ ✲ N2(t) ✲ rate λ2 = (1−p)λ Each arrival is switched to {N1(t); t > 0} with prob ability p and otherwise goes to {N2(t); t > 0}. View the switch as a Bernoulli process independent of {N (t); t > 0}. A p biased coin is ﬂipped indepen dently at each arrival. Each new process clearly has the stationary and independent increment property and each satisﬁes the small increment property. Thus each is Poisson. The small increment property doesn’t make it clear that the split processes are independent. For in dependence, both processes must sometimes have arrivals in the same small increment. Independence is hidden in the o(δ) terms. See text. Combining and splitting are often done together. First one views separate independent Poisson pro cesses as a combined process. Then it is split again with binary choices between processes. Example: Consider a last-come ﬁrst-serve queue with Poisson arrivals, rate λ and independent expo nential services, rate µ. A new arrival starts service immediately, but is interrupted if a new arrival oc curs before service completion. View services as a Poisson process. We can either ignore this process when there is nothing to serve, or visualize a low priority task that is served at rate µ when there is nothing else to do. The arrival process plus the service process is Poisson, rate λ + µ. The probability an arrival completes service before being interrupted is µ/(λ + µ). Given that you are interrupted, what is the proba bility of no further interruption? Two services (the interruping job and you) must ﬁnish before the next 2 µ interruption, so Answer: (λ+µ) 2. Non-homogeneous Poisson processes Consider optical transmission, where an optical stream of photons is modulated by variable power. The photon stream is reasonably modelled as a Poisson process, and the modulation converts the steady photon rate into a variable rate, say λ(t). We model the number of photons in any interval (t, t+δ] as a Poisson random variable whose rate pa rameter over (t, t+δ] is the average photon rate over (t, t+δ] times δ. In the small increment model, we have � � �(t, t+δ) = n = Pr N   1 − δλ(t) + o(δ)  λ(t)δ + o(δ)   o(δ) for for for n=0 n=1 n≥2 We can use this small increment model to see that the number of arrivals in each increment is Poisson with where n � � � � �(t, τ ) = n = [m(t, τ )] exp[−m(t, τ )] Pr N n! � m(t, τ) = � τ t λ(u) du. Combining and splitting non-homogeneous processes still works as in the homogeneous case, but the in dependent exponential interarrivals doesn’t work. We now return to homogeneous Poisson processes. Conditional arrival densities There are many interesting and useful results about the increment (0, t] of a Poisson process conditional on N (t). First condition on N (t) = 1. ✲ 0 δ✛ s1 t fS1|N (t)(s1|1) = lim δ→0 pN (s1)(0) pN� (s ,s +δ)(1) pN� (s +δ,t)(0) 1 1 1 δ pN (t)(1) e−λs1 λδe−λδ e−λ(t−s1−δ) 1 = δλte−λt t The important point is that this does not depend on s1, i.e., it is uniform over (0, t]. = Next consider N (t) = 2. ✲ 0 δ✛ s1 ✲ δ✛ s2 t e−λs1 λδe−λδ e−λ(s2−s1−δ)λδe−λδ e−λ(t−s2−δ) δ δ 2pN (t)(2) 2 = 2 t Again, this does not depend on s1, s2, or λ for 0 < s1 < s2 < t, i.e., it is uniform over the given region of s1, s2. f (s1s2|2) = lim We can do the same thing for N (t) = n for arbitrary n. Note that the exponents above always sum to λt. ✲ 0 δ✛ s1 ✲ δ✛ s2 ✲ δ✛ s3 t (δλ)n exp(−λt) δ→0 δ npN (t)(n) n! = n t This is ‘uniform’ over 0 < s1 < · · · < sn < t. fS� (n)|N (t)(�s(n)|n) = lim This is a uniform n dimensional probability density over the volume tn/n! corresponding to the con straint region 0 < s1 < · · · < sn < t. How did this derivation ‘know’ that the volume of s1, . . . , sn over 0 < s1 < · · · < sn < t is n!/tn? To see why n! appears in this uniform density, let U1, . . . , Un be n IID rv’s, each uniform over (0, t]. Let � n, i.e., S1, . . . , Sn be the order statistics for U S1 = min(U1, . . . Un), . . . , Sk = kth smallest, . . . �n The region of volume tn where the density of U is nonzero partitions into n! regions, one in which u1 < u2 < · · · < un and one for each other ordering of u1, . . . , un. From symmetry, each volume is the same, and thus each is tn/n!. � n is nonzero is one of these The region where S partitions, and thus also has volume tn/n!. � n has the same density, whether it is the Since S conditional density of n arrival epochs given N (t) = n or the order statistics of n uniform rv’s, we can use results about either for the other. As an example of using order statistics, consider ﬁnding the distribution function of S1 conditional on N (t) = n. Viewing S1 as the minimum of U1, . . . , Un, we have Pr � min Ui > s1 1≤i≤n � = = �n Pr{Ui > s} i=1 � �n � s1 i=1 1− � � s1 n = 1− t �n t s FcS |N (t)(s1|n) = 1 − 1 for s1 ≤ t 1 t E [S1 | N (t) = n] can be found by integration, � E [S1 | N (t) = n] = t n+1 Return to N (t) = 2 and look at fX1X2|N (t)(x1, x2|2). � � � � � � � � � � � � ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❘ ❅ ❅ ❅ ❅ s2 x2 s1 x1 Note that the area in the s1, s2 space where 0 < s1 < s2 < t is t2/2, explaining why the density is 2/t2. Note that a δ 2 box in the s1, s2 space maps into a parallelepided of the same area in the x1, x2 space. The area in the x1, x2 space where 0 < x1 + x2 < t is again t2/2 and f (x1, x2|N (t)=2) = 2/t2. ∗ XN = t − SN (t) (t)+1 ✛ 0 x1 ✲✛ s1 x2 ✲ ✛ x∗3 ✲ s2 t f (x1, x2|N (t)) = 2/t2 for x1, x2, x∗3 > 0; x1+x2+x∗3 = t From symmetry, any 2 of the variables X1, X2, X3∗ can replace X1, X2 above. Also, since X1 = S1, X1 has density and expected value FcX |N (t)(x1|2) = 1 � � x1 2 1− t t . 3 we see that X2 and X3∗ can be substituted for X1 in the As a sanity check, note that � above formulas. � ∗ E X1+X2+X3 = t E [X1 | N (t)=2] = This extends to N (t) = n for arbitrary n. � � x n fX1|N (t)(x1|n) = 1 − 1 t t E [X1 | N (t)=n] = . n+1 ∗ This relation also applies to Xn+1 = t − SN (t) � � x n fX ∗ |N (t)(x|n) = 1 − n+1 t � � t E Xn∗+1 | N (t)=n = . n+1 E � ∗ XN (t)+1 � = = ∞ � t (λt)ne−λt n! n=0 n+1 ∞ � (λt)n+1e−λt n=0 λ(n+1)! = 1 − e−λt λ Paradox: The mean interarrival time for a Poisson process is 1/λ. But the mean time from any given t to the next arrival is 1/λ and the mean time back to the previous arrival is (1/λ)(1−e−λt). Thus the mean length of the interval containing t is (1/λ)(2 − e−λt). This paradox will become clearer when we study renewals. A temporary half-intuitive explanation is to ﬁrst choose a sample path for a Poisson process and then choose a uniform random value for t over some large interval far from 0. The larger interarrival intervals occupy proportionally more of the overall interval than the smaller, so t is biased to lie in one of those larger intervals.

Lecture 5 Notes: Poisson Combining and Splitting

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock