Postscript version of this file

STAT 380 Week 6

Poisson Processes

Particles arriving over time at a particle detector. Several ways to describe most common model.

Approach 1: numbers of particles arriving in an interval has Poisson distribution, mean proportional to length of interval, numbers in several non-overlapping intervals independent.

For $s<t$, denote number of arrivals in $(s,t]$ by $N(s,t)$. Model is

1. $N(s,t)$ has a Poisson $(\lambda(t-s))$ distribution.

2. For $0 \le s_1 < t_1 \le s_2 < t_2 \cdots \le s_k < t_k$ the variables $N(s_i,t_i);i=1,\ldots,k$ are independent.

Approach 2:

Let $0 < S_1 <S_2 < \cdots$ be the times at which the particles arrive.

Let $T_i = S_i-S_{i-1}$ with $S_0=0$ by convention.

Then $T_1,T_2,\ldots$ are independent Exponential random variables with mean $1/\lambda$.

Note $P(T_i > x) =e^{-\lambda x}$ is called survival function of $T_i$.

Approaches are equivalent. Both are deductions of a model based on local behaviour of process.

Approach 3: Assume:

1. given all the points in $[0,t]$ the probability of 1 point in the interval $(t,t+h]$ is of the form
   $$\lambda h +o(h)$$

2. given all the points in $[0,t]$ the probability of 2 or more points in interval $(t,t+h]$ is of the form
   $$o(h)$$

All 3 approaches are equivalent. I show: 3 implies 1, 1 implies 2 and 2 implies 3. First explain $o$, $O$.

Notation: given functions $f$ and $g$ we write

$$f(h) = g(h) +o(h)$$

provided

$$\lim_{h \to 0} \frac{f(h)-g(h)}{h} = 0$$

[Aside: if there is a constant $M$ such that

$$\limsup_{h \to 0} \left\vert\frac{f(h)-g(h)}{h}\right\vert \le M$$

we say

$$f(h) = g(h)+O(h)$$

Notation due to Landau. Another form is

$$f(h) = g(h)+O(h)$$

means there is $\delta>0$ and $M$ s.t. for all $\vert h\vert<\delta$

$$\vert f(h)-g(h) \vert\le M h$$

Idea: $o(h)$ is tiny compared to $h$ while $O(h)$ is (very) roughly the same size as $h$.]

Model 3 implies 1: Fix $t$, define $f_t(s)$ to be conditional probability of 0 points in $(t,t+s]$ given value of process on $[0,t]$.

Derive differential equation for $f$. Given process on $[0,t]$ and 0 points in $(t,t+s]$ probability of no points in $(t,t+s+h]$ is

$$f_{t+s}(h) = 1-\lambda h+o(h)$$

Given the process on $[0,t]$ the probability of no points in $(t,t+s]$ is $f_t(s)$. Using $P(AB\vert C)=P(A\vert BC)P(B\vert C)$ gives

$$f_t(s+h) = f_t(s)f_{t+s}(h)$$

$$= f_t(s)(1-\lambda h +o(h))$$

Now rearrange, divide by $h$ to get

$$\frac{f_t(s+h) - f_t(s)}{h} = -\lambda f_t(s) +\frac{o(h)}{h}$$

Let $h \to 0$ and find

$$\frac{\partial f_t(s)}{\partial s} = -\lambda f_t(s)$$

Differential equation has solution

$$f_t(s) = f_t(0) \exp(-\lambda s) = \exp(-\lambda s)\, .$$

Notice: survival function of exponential rv..

General case. Notation: $N(t) =N(0,t)$.

$N(t)$ is a non-decreasing function of $t$. Let

$$P_k(t) = P(N(t)=k)$$

Evaluate $P_k(t+h)$ by conditioning on $N(s);0 \le s < t$ and $N(t)=j$.

Given $N(t)=j$ probability that $N(t+h) = k$ is conditional probability of $k-j$ points in $(t,t+h]$.

So, for $j\le k-2$:

$$\begin{multline*} P(N(t+h)=k\vert N(t) = j, N(s), 0 \le s < t) \\ =o(h) \end{multline*}$$

For $j=k-1$ we have

$$\begin{multline*} P(N(t+h)= k\vert N(t) = k-1, N(s), 0 \le s < t) \\ = \lambda h + o(h) \end{multline*}$$

For $j=k$ we have

$$\begin{multline*} P(N(t+h)= k\vert N(t) = k, N(s), 0 \le s < t) \\ = 1-\lambda h + o(h) \end{multline*}$$

$N$ is increasing so only consider $j\le k$.

$$P_k(t+h) = \sum_{j=0}^k P(N(t+h)=k\vert N(t) = j) P_j(t)$$

$$= P_k(t) (1-\lambda h) +\lambda h P_{k-1}(t) + o(h)$$

Rearrange, divide by $h$ and let $h \to 0$ t get

$$P_k^\prime(t) = -\lambda P_k(t) + \lambda P_{k-1}(t)$$

For $k=0$ the term $P_{k-1}$ is dropped and

$$P^\prime_0(t) = -\lambda P_0(t)$$

Using $P_0(0)=1$ we get

$$P_0(t) = e^{-\lambda t}$$

Put this into the equation for $k=1$ to get

$$P_1^\prime(t) = -\lambda P_1(t) +\lambda e^{-\lambda t}$$

Multiply by $e^{\lambda t}$ to see

$$\left(e^{\lambda t}P_1(t)\right)^\prime = \lambda$$

With $P_1(0)=0$ we get

$$P_1(t) = \lambda t e^{-\lambda t}$$

For general $k$ we have $P_k(0)=0$ and

$$\left(e^{\lambda t}P_k(t)\right)^\prime = \lambda e^{\lambda t}P_{k-1}(t)$$

Check by induction that

$$e^{\lambda t}P_k(t) = (\lambda t)^k/k!$$

Hence: $N(t)$ has Poisson $(\lambda t)$ distribution.

Similar ideas permit proof of

$$\begin{multline*} P(N(s,t)=k\vert N(u); 0 \le u \le s) \\ = \frac{\left\{\lambda(t-s)\right\}^k e^{-\lambda(t-s) }}{k!} \end{multline*}$$

From which (by induction) we can prove that $N$ has independent Poisson increments.

Exponential Interarrival Times

If $N$ is a Poisson Process we define $T_1,T_2,\ldots$ to be the times between 0 and the first point, the first point and the second and so on.

Fact: $T_1,T_2,\ldots$ are iid exponential rvs with mean $1/\lambda$.

We already did $T_1$ rigorously. The event $T>t$ is exactly the event $N(t)=0$. So

$$P(T>t) = \exp(-\lambda t)$$

which is the survival function of an exponential rv.

I do case of $T_1,T_2$. Let $t_1,t_2$ be two positive numbers and $s_1=t_1$, $s_2=t_1+t_2$. Consider event

$$\{t_1 < T_1 \le t_1+\delta_1\} \cap \{t_2 < T_2 \le t_2+\delta_2\} \, .$$

This is almost the same as the intersection of the four events:

$$N(0,t_1] =0$$

$$N(t_1,t_1+\delta_1] = 1$$

$$N(t_1+\delta_1,t_1+\delta_1+t_2] =0$$

$$N(s_2+\delta_1,s_2+\delta_1+\delta_2] = 1$$

which has probability

$$e^{-\lambda t_1} \times \lambda\delta_1 e^{-\lambda \delta_1} \times e^{-\lambda t_2} \times \lambda\delta_2 e^{-\lambda \delta_2}$$

Divide by $\delta_1\delta_2$ and let $\delta_1$ and $\delta_2$ go to 0 to get joint density of $T_1,T_2$ is

$$\lambda^2e^{-\lambda t_1}e^{-\lambda t_2}$$

which is the joint density of two independent exponential variates.

More rigor:

• Find joint density of $S_1,\ldots,S_k$.

• Use change of variables to find joint density of $T_1,\ldots,T_k$.

First step: Compute

$$P( 0 < S_1 \le s_1 < S_2 \le s_2 \cdots < S_k \le s_k)$$

This is just the event of exactly 1 point in each interval $(s_{i-1},s_i]$ for $i=1,\ldots,k-1$ ($s_0=0$) and at least one point in $(s_{k-1},s_k]$ which has probability

$$\prod_1^{k-1} \left\{\lambda(s_i-s_{i-1})e^{-\lambda(s_i-s_{i-1})}\right\} \left(1-e^{-\lambda(s_k-s_{k-1})}\right)$$

Second step: write this in terms of joint cdf of $S_1,\ldots,S_k$. I do $k=2$:

$$\begin{multline*} P( 0 < S_1 \le s_1 < S_2 \le s_2) \\ = F_{S_1,S_2}(s_1,s_2)-F_{S_1,S_2}(s_1,s_1) \end{multline*}$$

Notice tacit assumption $s_1 < s_2$.

Differentiate twice, that is, take

$$\frac{\partial^2}{\partial s_1\partial s_2}$$

to get

$$\begin{multline*} f_{S_1,S_2}(s_1,s_2)\\ = \frac{\partial^2}{\partial s_1\partia... ...ambda s_1 e^{-\lambda s_1} \left(1-e^{-\lambda (s_2-s_1)}\right) \end{multline*}$$

Simplify to

$$\lambda^2 e^{-\lambda s_2}$$

Recall tacit assumption to get

$$f_{S_1,S_2}(s_1,s_2) =\lambda^2 e^{-\lambda s_2} 1(0 < s_1 < s_2)$$

That completes the first part.

Now compute the joint cdf of $T_1,T_2$ by

$$F_{T_1,T_2}(t_1,t_2) = P(S_1 < t_1, S_2-S_1 <t_2)$$

This is

$$P(S_1 < t_1, S_2-S_1 <t_2)$$

$$= \int_0^{t_1} \int_{s_1}^{s_1+t_2} \lambda^2 e^{-\lambda s_2} ds_2ds_1$$

$$= \lambda \int_0^{t_1} \left(e^{-\lambda s_1} - e^{-\lambda(s_1+t_2)}\right) ds_1$$

$$= 1-e^{-\lambda t_1} - e^{-\lambda t_2} + e^{-\lambda(t_1+t_2)}$$

Differentiate twice to get

$$f_{T_1,T_2}(t_1,t_2) = \lambda e^{-\lambda t_1} \lambda e^{-\lambda t_2}$$

which is the joint density of two independent exponential random variables.

Summary so far:

Have shown:

Instantaneous rates model implies independent Poisson increments model implies independent exponential interarrivals.

Next: show independent exponential interarrivals implies the instantaneous rates model.

Suppose $T_1,\ldots$ iid exponential rvs with means $1/\lambda$. Define $N_t$ by $N_t=k$ if and only if

$$T_1+\cdots+T_k \le t \le T_1+\cdots +T_{k+1}$$

Let $A$ be the event $N(s)=n(s) ;0 < s \le t$. We are to show

$$P(N(t,t+h] = 1\vert N(t)=k,A) = \lambda h + o(h)$$

and

$$P(N(t,t+h] \ge 2\vert N(t)=k,A) = o(h)$$

If $n(s)$ is a possible trajectory consistent with $N(t) = k$ then $n$ has jumps at points

$$s_1\equiv t_1,s_2\equiv t_1+t_2, \ldots,s_k\equiv t_1+\cdots+t_k < t$$

and at no other points in $(0,t]$.

So given $N(s)=n(s) ;0 < s \le t$ with $n(t)=k$ we are essentially being given

$$T_1=t_1,\ldots,T_k=t_k, T_{k+1}> t-s_k$$

and asked the conditional probabilty in the first case of the event $B$ given by

$$t-s_k <T_{k+1}\le t-s_k+h < T_{k+2}+T_{k+1}\, .$$

Conditioning on $T_1,\ldots,T_k$ irrelevant (independence).

$$P(N(t,t+h] = 1\vert N(t)=k,A) /h$$

$$= P(B\vert T_{k+1}> t-s_k)/h$$

$$= \frac{P(B) }{he^{-\lambda(t-s_k)}}$$

The numerator may be evaluated by integration:

$$P(B) = \int_{t-s_k}^{t-s_k+h} \int_{t-s_k+h - s_1}^\infty \lambda^2 e^{-\lambda(s_1+s_2)} ds_2ds_1$$

Let $h \to 0$ to get the limit

$$P (N(t,t+h] = 1\vert N(t)=k,A) /h \to \lambda$$

as required.

The computation of

$$\lim_{h\to 0} P(N(t,t+h] \ge 2\vert N(t)=k,A) /h$$

is similar.

Properties of exponential rvs

Convolution: If $X$ and $Y$ independent rvs with densities $f$ and $g$ respectively and $Z=X+Y$ then

$$P(Z \le z) = \int_{-\infty}^\infty \int_{-\infty}^{z-x} f(x) g(y) dy dx$$

Differentiating wrt $z$ we get

$$f_Z(z) = \int_{-\infty}^\infty f(x) g(z-x) dx$$

This integral is called the convolution of densities $f$ and $g$.

If $T_1,\ldots,T_n$ iid Exponential$(\lambda)$ then $S_n=T_1+\cdots+T_n$ has a Gamma $(n,\lambda)$ distribution. Density of $S_n$ is

$$f_{S_n}(s) = \lambda (\lambda s)^{n-1} e^{-\lambda s} / n!$$

for $s>0$.

Proof:

$$P(S_n>s) = P(N(0,s] < n)$$

$$= \sum_{j=0}^{n-1} (\lambda s)^j e^{-\lambda s}/j!$$

Then

$$f_{S_n}(s) = \frac{d}{ds} P(S_n \le s)$$

$$= \frac{d}{ds}\left\{1-P(S_n>s)\right\}$$

$$= -\lambda \sum_{j=1}{n-1}\left\{ j(\lambda s)^{j-1} -(\lambda s)^j\right\} \frac{e^{-\lambda s}}{j!}$$

$$\qquad + \lambda e^{-\lambda s}$$

$$= \lambda e^{-\lambda s } \sum_{j=1}^{n-1}\left\{ \frac{(\lambda s)^j}{j!} - \frac{(\lambda s)^{j-1}}{(j-1)!}\right\}$$

$$\qquad + \lambda e^{-\lambda s}$$

This telescopes to

$$f_{S_n}(s) = \lambda (\lambda s)^{n-1} e^{-\lambda s} / (n-1)!$$

Extreme Values: If $X_1,\ldots,X_n$ are independent exponential rvs with means $1/\lambda_1,\ldots,1/\lambda_n$ then $Y = \min\{X_1,\ldots,X_n\}$ has an exponential distribution with mean

$$\frac{1}{\lambda_1+\cdots+\lambda_n}$$

Proof:

$$P(Y > y) = P(\forall k X_k>y)$$

$$= \prod e^{-\lambda_k y}$$

$$= e^{-\sum\lambda_k y}$$

Memoryless Property: conditional distribution of $X-x$ given $X \ge x$ is exponential if $X$ has an exponential distribution.

Proof:

$$P(X-x>y\vert X\ge x)$$

$$= \frac{P(X>x+y,X\ge x)}{P(X>x)}$$

$$= \frac{PX>x+y)}{P(X\ge x)}$$

$$= \frac{e^{-\lambda(x+y)}}{e^{-\lambda x}}$$

$$= e^{-\lambda y}$$

Hazard Rates

The hazard rate, or instantaneous failure rate for a positive random variable $T$ with density $f$ and cdf $F$ is

$$r(t) = \lim_{\delta\to 0} \frac{P(t < T\le t+\delta \vert T \ge t)}{\delta}$$

This is just

$$r(t) = \frac{f(t)}{1-F(t)}$$

For an exponential random variable with mean $1/\lambda$ this is

$$h(t) = \frac{ \lambda e^{-\lambda t}}{e^{-\lambda t}} = \lambda$$

The exponential distribution has constant failure rate.

Weibull random variables have density

$$f(t\vert\lambda,\alpha) = \lambda(\lambda t)^{\alpha-1}e^{- (\lambda t)^\alpha}$$

for $t>0$. The corresponding survival function is

$$1-F(t) = e^{- (\lambda t)^\alpha}$$

and the hazard rate is

$$r(t) = \lambda(\lambda t)^{\alpha-1}$$

which is increasing for $\alpha>1$, decreasing for $\alpha<1$. For $\alpha=1$ this is the exponential distribution.

Since

$$r(t) = \frac{dF(t)/dt}{1-F(t)} =-\frac{d\log(1-F(t))}{dt}$$

we can integrate to find

$$1-F(t) = \exp\{ -\int_0^t r(s) ds\}$$

so that $r$ determines $F$ and $f$.