1 IEOR 6711: Notes on the Poisson Process

1 Copyright c 2009 by Karl Sigman 1 IEOR 6711 : Notes on the Poisson Process We present here the essentials of the Poisson point Process with its many interesting properties. As preliminaries, we first define what a point Process is, define the renewal point Process and state and prove the Elementary Renewal Theorem. Point Processes Definition A simple point Process = {tn : n 1} is a sequence of strictly increas- ing points 0 < t1 < t2 < , (1). def with tn as n . With N (0) = 0 we let N (t) denote the number of points that fall in the interval (0, t]; N (t) = max{n : tn t}. {N (t) : t 0} is called the counting Process for . If the tn are random variables then is called a random point Process . def We sometimes allow a point t0 at the origin and define t0 = 0. Xn = tn tn 1 , n 1, is called the nth interarrival time. We view t as time and view tn as the nth arrival time (although there are other kinds of applications in which the points tn denote locations in space as opposed to time).)

2 The word simple refers to the fact that we are not allowing more than one arrival to ocurr at the same time (as is stated precisely in (1)). In many applications there is a system to which customers are arriving over time (classroom, bank, hospital, supermarket, airport, etc.), and {tn } denotes the arrival times of these customers to the system. But {tn } could also represent the times at which phone calls are received by a given phone, the times at which jobs are sent to a printer in a computer network, the times at which a claim is made against an insurance company, the times at which one receives or sends email, the times at which one sells or buys stock, the times at which a given web site receives hits, or the times at which subways arrive to a station. Note that tn = X1 + + Xn , n 1, the nth arrival time is the sum of the first n interarrival times. Also note that the event {N (t) = 0} can be equivalently represented by the event {t1 > t}, and more generally {N (t) = n} = {tn t, tn+1 > t}, n 1.

3 In particular, for a random point Process , P (N (t) = 0) = P (t1 > t). 1. Renewal Process A random point Process = {tn } for which the interarrival times {Xn } form an sequence is called a renewal Process . tn is then called the nth renewal epoch and F (x) =. P (X x), x 0, denotes the common interarrival time distribution. To avoid trivialities we always assume that F (0) < 1, hence ensuring that wp1, tn . The rate of the def renewal Process is defined as = 1/E(X) which is justified by Theorem (Elementary Renewal Theorem (ERT)) For a renewal Process , N (t). lim = t t and E(N (t)). lim = . t t Proof : Observing that tN (t) t < tN (t)+1 and that tN (t) = X1 + XN (t) , yields after division by N (t): N (t) N (t)+1. 1 X t 1 X. Xj Xj . N (t) j=1 N (t) N (t) j=1. By the Strong Law of Large Numbers (SLLN), both the left and the right pieces converge to E(X) as t . Since t/N (t) is sandwiched between the two, it also converges to E(X), yielding the first result after taking reciprocals.

4 For the second result, we must show that the collection of rvs {N (t)/t : t 1} is uniformly integrable (UI)1 , so as to justify the interchange of limit and expected value, E(N (t)) N (t) . lim = E lim . t t t t We will show that P (N (t)/t > x) c/x2 , x > 0 for some c > 0 hence proving UI. To this end, choose a > 0 such that 0 < F (a) < 1 (if no such a exists then the renewal Process is deterministic and the result is trival). Define new interarrival times via truncation X n =.. aI{Xn > a}. Thus Xn = 0 with probability F (a) and equals a with probability 1 F (a). Letting N (t) denote the counting Process obtained by using these new interarrival times, it follows that N (t) N (t), t 0. Moreover, arrivals (which now occur in batches) can now only occur at the deterministic lattice of times {na : n 0}. Letting p = 1 F (a), and letting Kn denote the number of arrivals that occur at time na, we conclude that {Kn } is iid with a geometric distribution with success probability p.

5 Letting [x] denote the smallest integer x, we have the inequality [t/a]. X. (t) S(t) =. N (t) N Kn , t 0. n=1. 1. A collection of rvs {Xt : t T } is said to be uniformly integrable (UI), if supt T E(|Xt |I{|Xt | >. x}) 0, as x . 2. Observing that E(S(t)) = [t/a]E(K) and V ar(S(t)) = [t/a]V ar(K), we obtain E(S(t)2 ) =. V ar(S(t) + E(S(t))2 = [t/a]V ar(K) + [t/a]2 E 2 (K) c1 t + c2 t2 , for constants c1 >. 0, c2 > 0. Finally, when t 1, Chebychev's inequality implies that P (N (t)/t > x) . E(N 2 (t))/t2 x2 E(S 2 (t))/t2 x2 c/x2 where c = c1 + c2 . Remark In the elementary renewal theorem, the case when = 0 ( , E(X) = ). is allowed, in which case the renewal Process is said to be null recurrent. In the case when 0 < < ( , 0 < E(X) < ) the renewal Process is said to be positive recurrent. Poisson point Process There are several equivalent definitions for a Poisson Process ; we present the simplest one. Although this definition does not indicate why the word Poisson is used, that will be made apparent soon.)

6 Recall that a renewal Process is a point Process = {tn : n 0}. in which the interarrival times Xn = tn tn 1 are with common distribution F (x) = P (X x). The arrival rate is given by = {E(X)} 1 which is justified by the ERT (Theorem ). In what follows it helps to imagine that the arrival times tn correspond to the consec- utive times that a subway arrives to your station, and that you are interested in catching the next subway. Definition A Poisson Process at rate 0 < < is a renewal point Process in which the interarrival time distribution is exponential with rate : interarrival times {Xn : n 1} are with common distribution F (x) = P (X x) = 1 e x , x 0;. E(X) = 1/ . Since tn = X1 + + Xn (the sum of n exponentially distributed ), we conclude that the distribution of tn is the nth -fold convolution of the exponential distri- bution and thus is a gamma(n, ) distribution (also called an Erlang(n, ) distribution);. its density is given by ( t)n 1.

7 Fn (t) = e t , t 0, (2). (n 1)! where f1 (t) = f (t) = e t is the exponential density, and E(tn ) = E(X1 + + Xn ) =. nE(X) = n/ . For example, f2 is the convolution f1 f1 : Z t f2 (t) = f1 (t s)f1 (s)ds 0. Z t = e (t s) ds e s ds 0. Z t t = e ds 0. t = e t, 3. and in general fn+1 = fn f1 = f1 fn . The Poisson distribution: A Poisson Process has Poisson increments Later, in Section we will prove the fundamental fact that: For each fixed t > 0, the distribution of N (t) is Poisson with mean t: ( t)k P (N (t) = k) = e t , k 0. k! In particular, E(N (t)) = t, V ar(N (t)) = t, t 0. In fact, the number of arrivals in any arbitrary interval of length t, N (s + t) N (s) is also Poisson with mean t: ( t)k P (N (s + t) N (s) = k) = e t , s > 0, k 0, k! and E(N (s + t) N (s)) = t, V ar(N (s + t) N (s)) = t, t 0. N (s+t) N (s) is called a length t increment of the counting Process {N (t) : t 0}; the above tells us that the Poisson counting Process has increments that have a distribution that is Poisson and only depends on the length of the increment.

8 Any increment of length t is distributed as Poisson with mean t. Review of the exponential distribution The exponential distribution has many nice properties; we review them next. A X has an exponential distribution at rate , denoted by X exp( ), if X. is non-negative with F (x) = P (X x), tail F (x) = P (X > x) = 1 F (x) and density f (x) = F 0 (x) given by F (x) = 1 e x , x 0, F (x) = e x , x 0, f (x) = e x , x 0. It is easily seen that 1. E(X) =.. 2. E(X 2 ) =. 2. 1. V ar(X) = . 2. 4. For example, Z . E(X) = xf (x)dx Z0 . = x e x dx Z0 . = F (x)dx (integrating the tail method). 0. Z . = e x dx 0. 1. = .. The most important property of the exponential distribution is the memoryless prop- erty, P (X y > x|X > y) = P (X > x), for all x 0 and y 0, which can also be written as P (X > x + y) = P (X > x)P (X > y), for all x 0 and y 0. The memoryless property asserts that the residual (remaining) lifetime of X given that its age is at least y has the same distribution as X originally did, and is independent of its age: X forgets its age or past and starts all over again.

9 If X denotes the lifetime of a light bulb, then this property implies that if you find this bulb burning sometime in the future, then its remaining lifetime is the same as a new bulb and is independent of its age. So you could take the bulb and sell it as if it were brand new. Even if you knew, for example, that the bulb had already burned for 3 years, this would be so. We say that X. (or its distribution) is memoryless. The fact that if X exp( ), then it is memoryless is immediate from P (X > x + y). P (X y > x|X > y) =. P (X > y). (x+y). e =. e y x = e = P (X > x). But the converse is also true: Proposition A non-negative X (which is not identically 0) has the memoryless property if and only if it has an exponential distribution. 5. Proof : One direction was proved above already, so we need only prove the other. Letting g(x) = P (X > x), we have g(x + y) = g(x)g(y), x 0, y 0, and we proceed to show that such a function must be of the form g(x) = e x for some.

10 To this end, observe that by using x = y = 1 it follows that g(2) = g(1)g(1) and more generally g(n) = g(1)n , n 1. Noting that 1 1 1. 1= + + + (m summands), m m m we see that g(1) = g(1/m)m yielding g(1/m) = g(1)1/m . Thus for any rational number r = n/m, n 1 1 1. r= = + + + (n summands), m m m m yielding g(r) = g(1/m)n = g(1)n/m = g(1)r . Finally, we can, for any irrational x > 0, choose a decreasing sequence of rational numbers, r1 > r2 > , such that rn x, as n . Since g is the tail of a , it is right-continuous in x and hence g(x) = lim g(rn ). n . = lim g(1)rn n . = g(1)x . We conclude that g(x) = g(1)x , x 0, and since g(x) = P (X > x) 0 as x , we conclude that 0 g(1) < 1. But g(1) > 0, for otherwise g(x) = P (X > x) = 0, x 0. implies that P (X = 0) = 1, a contradiction to the assumption that X not be identically 0. Thus 0 < g(1) < 1. Since g(1)x = ex ln(g(1)) we finally obtain g(x) = e x , where def = ln(g(1)) > 0. Other useful properties of the exponential distribution are given by Proposition If X1 has an exponential distribution with rate 1 , and X2 has an exponential distribution with rate 2 and the two are independent, then 1.