13  Poisson processes

Author

Affiliation

Aditya Mahajan

McGill University

The Bernoulli process describes arrivals in discrete time. We now develop its continuous-time analogue, the Poisson process. We first introduce the process through exponential interarrival times and derive its counting properties. We then study superposition, splitting, and conditional arrival times, and connect the construction to continuous-time Markov chains.

13.1 From Bernoulli processes to Poisson processes

1. Recall the Bernoulli process from Example 10.1. Let \(\{B_n\}_{n\ge1}\) be i.i.d. \(\operatorname{Bernoulli}(p)\) random variables, where \(B_n=1\) indicates an arrival at time \(n\). The number of arrivals by time \(n\) is \[ N_n=\sum_{k=1}^nB_k, \] so \(N_n\sim\operatorname{Binomial}(n,p)\).

2. There are two equivalent ways to describe the arrivals. Let

   • \(T_k\) be the time between the \((k-1)\)-st and \(k\)-th arrivals;
   • \(S_k=T_1+\cdots+T_k\) be the time of the \(k\)-th arrival.

   For a Bernoulli process, the interarrival times \(T_1,T_2,\ldots\) are i.i.d. geometric random variables. The counting process and arrival times contain the same information: \[ \{N_n\ge k\}=\{S_k\le n\}. \]

3. To pass to continuous time, divide an interval of length \(t\) into \(m\) short intervals and suppose that an arrival occurs in each interval with probability \(λt/m\). The number of arrivals is binomial, and for every fixed \(n\), \[ \binom mn\left(\frac{λt}{m}\right)^n \left(1-\frac{λt}{m}\right)^{m-n} \longrightarrow e^{-λt}\frac{(λt)^n}{n!} \qquad\text{as }m\to\infty. \] This rare-event limit suggests that the number of continuous-time arrivals in an interval of length \(t\) should have a \(\operatorname{Poisson}(λt)\) distribution.

13.2 Exponential interarrival times

1. The geometric distribution is the only memoryless distribution on the nonnegative integers. Its continuous-time analogue is the exponential distribution. If \(T\sim\operatorname{Exponential}(λ)\), then \[ \PR(T>t)=e^{-λt}, \qquad f_T(t)=λe^{-λt}, \qquad t\ge0, \] and \[ \EXP[T]=\frac1λ. \] The parameter \(λ\) is called the rate.

2. The exponential distribution is memoryless: for \(s,t\ge0\), \[ \PR(T>s+t\mid T>s) =\frac{e^{-λ(s+t)}}{e^{-λs}} =e^{-λt} =\PR(T>t). \] Thus, given that no arrival has occurred by time \(s\), the remaining waiting time has the same distribution as the original waiting time.

3. The converse is also true.

   Example 13.1 (Continuous memoryless distributions) Let \(T\) be a nonnegative continuous random variable such that \[ \PR(T>s+t\mid T>s)=\PR(T>t) \] for every \(s,t\ge0\). Then \(T\) has an exponential distribution.

   NoteSolution

   Let \(\overline F(t)=\PR(T>t)\). The memoryless property gives \[ \overline F(s+t)=\overline F(s)\overline F(t). \] Therefore, \(g(t)=-\log\overline F(t)\) satisfies \[ g(s+t)=g(s)+g(t). \] Since \(\overline F\) is continuous, \(g\) is continuous, and the continuous solutions of this equation are \(g(t)=λt\) for some \(λ\ge0\). For a proper nondegenerate distribution, \(λ>0\). Hence \[ \overline F(t)=e^{-λt}. \]

13.3 Construction of the Poisson process

1. Let \(T_1,T_2,\ldots\) be i.i.d. \(\operatorname{Exponential}(λ)\) random variables and define \[ S_0=0, \qquad S_n=T_1+\cdots+T_n, \quad n\ge1. \] The random variable \(S_n\) is the time of the \(n\)-th arrival. The associated counting process is \[\begin{equation}\label{eq:poisson-counting-process} N(t)=\max\{n\ge0:S_n\le t\}, \qquad t\ge0. \end{equation}\] The process \(\{N(t)\}_{t\ge0}\) is called a Poisson process with rate \(λ\).

   The counting process and the arrival times contain the same information. In particular, \[ N(t)=\sum_{n=1}^{∞}\IND\{S_n\le t\}, \qquad S_n=\inf\{t\ge0:N(t)\ge n\}. \] The first identity counts the arrivals that have occurred by time \(t\), while the second recovers the time of the \(n\)-th arrival from the counting process.

2. The sample paths of \(N(t)\) are nondecreasing, right-continuous staircase functions. They start at zero and increase by one at each arrival time \(S_n\).

viewof poisson_rate = Inputs.range([0.5, 5], {label: "rate λ", value: 2, step: 0.5})
viewof rerun_poisson = Inputs.button("Generate sample path")

poisson_path = {
  rerun_poisson
  const horizon = 10
  const points = [{t: 0, N_t: 0}]
  let t = 0
  let count = 0
  while (true) {
    t += -Math.log(1 - Math.random()) / poisson_rate
    if (t > horizon) break
    count += 1
    points.push({t, N_t: count})
  }
  points.push({t: horizon, N_t: count})
  return points
}

Plot.plot({
  grid: true,
  height: 180,
  x: {domain: [0, 10], label: "t"},
  y: {domain: [0, 50], label: "N(t)"},
  marks: [
    Plot.ruleY([0]),
    Plot.line(poisson_path, {x: "t", y: "N_t", curve: "step-after", strokeWidth: 1.5}),
    Plot.dot(poisson_path.slice(0, -1), {x: "t", y: "N_t", fill: "currentColor", r: 2})
  ]
})

3. Since \(S_n\) is a sum of \(n\) independent exponential random variables, it has an Erlang distribution: \[\begin{equation}\label{eq:erlang-density} f_{S_n}(s) =\frac{λ^n s^{n-1}e^{-λs}}{(n-1)!}, \qquad s\ge0. \end{equation}\] In particular, \[ \EXP[S_n]=\frac nλ, \qquad \VAR(S_n)=\frac n{λ^2}. \]

4. The events \(\{N(t)=n\}\) and \(\{S_n\le t<S_{n+1}\}\) are the same. For \(n\ge1\), conditioning on \(S_n=s\) gives \[\begin{align*} \PR(N(t)=n) &=\int_0^t f_{S_n}(s)\PR(T_{n+1}>t-s)\,ds\\ &=\int_0^t \frac{λ^n s^{n-1}e^{-λs}}{(n-1)!} e^{-λ(t-s)}\,ds\\ &=e^{-λt}\frac{(λt)^n}{n!}. \end{align*}\] The same formula holds for \(n=0\) because \(\PR(N(t)=0)=\PR(T_1>t)=e^{-λt}\). Therefore, \[\begin{equation}\label{eq:poisson-count-distribution} \boxed{ N(t)\sim\operatorname{Poisson}(λt). } \end{equation}\]

5. It follows that \[ \EXP[N(t)]=λt, \qquad \VAR(N(t))=λt. \] The process itself is not stationary because the distribution of \(N(t)\) depends on \(t\).

6. However, knowing that \[ N(t)\sim\operatorname{Poisson}(λt) \] for every \(t\) specifies only the one-dimensional marginal distributions of the process. It does not specify the dependence between counts at different times. In the next section, we show that the Poisson process has stationary independent increments, which supplies this temporal dependence.

13.4 Increments and covariance

1. The memoryless property implies that, at any deterministic time \(s\), the waiting time until the next arrival is again \(\operatorname{Exponential}(λ)\) and is independent of the arrivals before time \(s\). Consequently, \[\begin{equation}\label{eq:poisson-increment-distribution} N(t)-N(s)\sim\operatorname{Poisson}(λ(t-s)), \qquad 0\le s<t. \end{equation}\] Thus, the Poisson process has stationary increments.

2. Counts over disjoint time intervals are independent. Therefore, the Poisson process has independent increments. Equivalently, for \[ 0\le t_0<t_1<\cdots<t_m, \] the random variables \[ N(t_1)-N(t_0),\ldots,N(t_m)-N(t_{m-1}) \] are independent.

3. For \(0\le s\le t\), \[ N(t)=N(s)+[N(t)-N(s)], \] where the two terms on the right are independent. Hence \[\begin{equation}\label{eq:poisson-covariance} \COV(N(s),N(t))=λs, \end{equation}\] or, for arbitrary \(s,t\ge0\), \[ \COV(N(s),N(t))=λ\min(s,t). \] This is the continuous-time analogue of the covariance of the Bernoulli counting process and the discrete-time random walk.

13.5 Superposition of Poisson processes

1. Let \(\{N_1(t)\}\) and \(\{N_2(t)\}\) be independent Poisson processes with rates \(λ_1\) and \(λ_2\), and define \[ N(t)=N_1(t)+N_2(t). \] Then \(\{N(t)\}\) is a Poisson process with rate \(λ_1+λ_2\).

2. To see this, consider any interval \((s,t]\). The increment \[ N(t)-N(s) =[N_1(t)-N_1(s)]+[N_2(t)-N_2(s)] \] is the sum of independent Poisson random variables and therefore has a \(\operatorname{Poisson}((λ_1+λ_2)(t-s))\) distribution. Increments over disjoint intervals remain independent, so this is a process-level statement, not just a statement about \(N(t)\) at one time.

3. More generally, the superposition of independent Poisson processes with rates \(λ_1,\ldots,λ_m\) is a Poisson process with rate \[ λ_1+\cdots+λ_m. \]

13.6 Splitting a Poisson process

1. Suppose each arrival of a rate-\(λ\) Poisson process is independently labeled type 1 with probability \(p\) and type 2 with probability \(1-p\). Let \(N_1(t)\) and \(N_2(t)\) count the two types. Then \(\{N_1(t)\}\) and \(\{N_2(t)\}\) are independent Poisson processes with rates \(pλ\) and \((1-p)λ\), respectively.

2. For fixed \(t\), conditional on \(N(t)=m+k\), the pair \((N_1(t),N_2(t))\) has a binomial splitting distribution: \[ \PR(N_1(t)=m,N_2(t)=k\mid N(t)=m+k) =\frac{(m+k)!}{m!k!}p^m(1-p)^k. \] Therefore, \[\begin{align*} &\PR(N_1(t)=m,N_2(t)=k)\\ &\quad= \frac{(pλt)^m e^{-pλt}}{m!} \frac{((1-p)λt)^k e^{-(1-p)λt}}{k!}. \end{align*}\] The factorization shows both the marginal Poisson distributions and their independence. Applying the same argument on disjoint intervals gives independence of the two processes.

3. The same result holds for \(r\) types. If an arrival is independently assigned type \(i\) with probability \(p_i\), where \(p_1+\cdots+p_r=1\), then the type processes are independent Poisson processes with rates \(p_iλ\).

13.7 Conditional arrival times

1. Suppose that \(N(t)=1\). Conditional on this event, the single arrival time \(S_1\) is uniformly distributed on \([0,t]\). For \(0 \le s \le t\), \[\begin{align*} \PR(S_1\le s\mid N(t)=1) &=\frac{\PR(N(s)=1,N(t)-N(s)=0)}{\PR(N(t)=1)}\\ &=\frac{(λs)e^{-λs}e^{-λ(t-s)}}{(λt)e^{-λt}}\\ &=\frac st. \end{align*}\]

2. More generally, conditional on \(N(t)=n\), the arrival times \[ 0<S_1<\cdots<S_n<t \] have the same joint distribution as the order statistics of \(n\) independent \(\operatorname{Uniform}(0,t)\) random variables. Their conditional joint density is \[ f_{S_1,\ldots,S_n\mid N(t)}(s_1,\ldots,s_n\mid n) =\frac{n!}{t^n}, \] on the region \(0<s_1<\cdots<s_n<t\).

3. This result is useful for simulation. One can generate a Poisson process on \([0,t]\) by first drawing \(N\sim\operatorname{Poisson}(λt)\), then drawing \(N\) independent uniform random variables on \([0,t]\), and finally sorting them to obtain the arrival times.

4. We have therefore encountered three equivalent descriptions of a Poisson process:

   • The interarrival times are i.i.d. \(\operatorname{Exponential}(λ)\) random variables.
   • The process has stationary independent increments, with \[ N(t)-N(s)\sim\operatorname{Poisson}(λ(t-s)), \qquad 0\le s<t. \]
   • On any interval \([0,t]\), first draw \(N(t)\sim\operatorname{Poisson}(λt)\); conditional on \(N(t)=n\), the \(n\) arrival times are the order statistics of \(n\) independent \(\operatorname{Uniform}(0,t)\) random variables.

   The first description is based on waiting times, the second on counts over intervals, and the third provides a finite-interval construction.

13.8 Competing Poisson processes

1. Let \(T_1\sim\operatorname{Exponential}(λ_1)\) and \(T_2\sim\operatorname{Exponential}(λ_2)\) be independent waiting times. Then \[ \PR(\min(T_1,T_2)>t) =e^{-λ_1t}e^{-λ_2t} =e^{-(λ_1+λ_2)t}, \] so \[ \min(T_1,T_2)\sim\operatorname{Exponential}(λ_1+λ_2). \]

2. The probability that process 1 produces the first arrival is \[\begin{align*} \PR(T_1<T_2) &=\int_0^\infty \PR(T_2>t)f_{T_1}(t)\,dt\\ &=\int_0^\infty e^{-λ_2t}λ_1e^{-λ_1t}\,dt\\ &=\frac{λ_1}{λ_1+λ_2}. \end{align*}\] This is another way to see the superposition and splitting results: the combined clock rings at rate \(λ_1+λ_2\), and each ring comes from process \(i\) with probability proportional to \(λ_i\).

13.9 Renewal processes

1. The Poisson process is a special case of a broader class of counting processes. Let \(T_1,T_2,\ldots\) be arbitrary positive i.i.d. interarrival times, and define \[ S_n=T_1+\cdots+T_n, \qquad N(t)=\max\{n:S_n\le t\}. \] Then \(\{N(t)\}_{t\ge0}\) is called a renewal process. The Poisson process is the special case in which the interarrival times are exponential.

2. If \(\EXP[T_1]<\infty\), then \[ \frac{N(t)}{t}\xrightarrow{\text{a.s.}}\frac{1}{\EXP[T_1]} \qquad\text{as }t\to\infty. \] This follows intuitively by applying the strong law to \(S_n/n\) and viewing \(N(t)\) as the inverse of the arrival-time sequence. Thus, the reciprocal of the mean interarrival time is the long-run arrival rate.

3. The counting processes encountered so far fit into one common picture:

   • geometric interarrival times give the discrete-time Bernoulli counting process;
   • exponential interarrival times give the Poisson process;
   • general positive i.i.d. interarrival times give a renewal process.

13.10 Connection with continuous-time Markov chains

1. A Poisson process is a continuous-time Markov process on \(\integers_{\ge0}\). From state \(n\), it waits an \(\operatorname{Exponential}(λ)\) amount of time and then jumps to state \(n+1\).

2. A continuous-time Markov chain generalizes this construction in two ways:

   • the exponential holding-time rate may depend on the current state;
   • when the clock rings, the process may jump to different states with different probabilities.

   Thus, the Poisson process provides the basic random-clock mechanism underlying continuous-time Markov chains.

Exercises

1. Suppose requests arrive at a web server according to a Poisson process with rate \(λ=10\) per minute.

   1. What is the expected time of the 100th request?

   2. What is the probability that the time between the 100th and 101st requests exceeds one minute?

   3. Each request is from Canada independently with probability \(1/5\). What is the probability that no request from Canada arrives during the next two minutes?

   NoteSolution

   1. The 100th arrival time is \(S_{100}=T_1+\cdots+T_{100}\), so \[ \EXP[S_{100}]=\frac{100}{10}=10\text{ minutes}. \]

   2. The waiting time \(T_{101}\) is \(\operatorname{Exponential}(10)\), so \[ \PR(T_{101}>1)=e^{-10}. \]

   3. Thinning gives a Poisson process of Canadian requests with rate \(2\) per minute. Thus, \[ \PR(N_C(2)=0)=e^{-4}. \]

2. Suppose \(N(t)=2\). Find the conditional joint density of \((S_1,S_2)\) and the conditional marginal density of \(S_1\).

   NoteSolution

   The joint density is \[ f_{S_1,S_2\mid N(t)}(s_1,s_2\mid2) =\frac{2}{t^2}, \qquad 0<s_1<s_2<t. \] Therefore, \[ f_{S_1\mid N(t)}(s\mid2) =\int_s^t\frac{2}{t^2}\,du =\frac{2(t-s)}{t^2}, \qquad 0<s<t. \]

3. Independent requests arrive from two sources according to Poisson processes with rates \(λ_1\) and \(λ_2\). Find the distribution of the time until the first request and the probability that the first request comes from source 1.

4. Let \(\{N(t)\}\) be a Poisson process with rate \(λ\). Independently assign every arrival to one of three streams with probabilities \(p_1,p_2,p_3\). Show that the three output processes are independent, find their rates, and verify that their superposition recovers the original process.

5. Let \(S_n=T_1+\cdots+T_n\) be the time of the \(n\)-th arrival in a Poisson process with rate \(λ\).

   1. Use the central limit theorem to show that, for large \(n\), \[ \frac{S_n-n/λ}{\sqrt n/λ} \] is approximately a standard normal random variable.

   2. Suppose arrivals occur at rate \(4\) per minute. Use the normal approximation to estimate the probability that the 100th arrival occurs after 27 minutes.

6. Independent type-1 and type-2 arrivals form Poisson processes with rates \(λ_1\) and \(λ_2\), respectively. Let \(M\) be the number of type-2 arrivals before the first type-1 arrival. Use superposition and labeling of the combined process to show that \[ \PR(M=k) =\left(\frac{λ_2}{λ_1+λ_2}\right)^k \frac{λ_1}{λ_1+λ_2}, \qquad k=0,1,\ldots. \] Hence, identify the distribution of \(M\).

Further reading

• Gubner, Chapter 8.
• Grimmett and Stirzaker, Chapter 6.
• R. G. Gallager, Discrete Stochastic Processes, Chapters 2 and 3.