Chapter 3 · Markov Chains and Stochastic Processes

3.3 Poisson and Birth–Death Processes

Markov processes in continuous time: counting processes and the three equivalent definitions of the Poisson process, exponential gaps and gamma arrival times, uniform arrivals given $N(t)$, thinning and superposition, compound Poisson sums, continuous-time Markov chains with their generator $Q$ and the Kolmogorov equations $P'(t)=QP(t)=P(t)Q$, birth–death processes, the Yule process and steady states.

Calls reach an emergency line, photons hit a detector, customers enter a shop, earthquakes strike a fault: in each case events happen at random instants of continuous time, and what we observe is the counting function $N(t)$, the number of events up to time $t$. The simplest and by far the most important model for such data is the Poisson process. It can be described in three apparently different ways: by Poisson counts with independent increments, by the "rare events" rule that in a short interval of length $h$ one event happens with probability about $\lambda h$, and by independent exponential waiting times between events. Proving that the three descriptions agree is the first aim of this section. The second is to use them: given the number of events, their times are scattered like uniform random points; a Poisson stream split at random gives independent Poisson streams, and merging independent streams gives a Poisson stream again.

The Poisson process is the simplest continuous-time Markov chain: it waits an exponential time and then jumps up by one. In general such a chain waits in state $i$ for an exponential time with rate $q_i$ and then jumps according to a discrete chain like those of §3.1–§3.2. The rates form a generator matrix $Q$, the transition probabilities satisfy the Kolmogorov differential equations $P'(t)=QP(t)=P(t)Q$, and the steady state solves $\pi Q=0$. Birth–death processes, in which the state moves only by $\pm1$, describe populations, epidemics and above all queues: the M/M/1 and M/M/$c$ models of §9.3 are birth–death processes. CSIR NET questions ask for Poisson probabilities with conditioning ("given that $5$ customers came in an hour, what is the chance that $2$ came in the first $20$ minutes?"), for superposition and thinning, for $e^{tQ}$ of a small generator, for steady-state probabilities and for the mean of a Yule process; Part C statements test the classic traps listed in the ⚠️ box.

Counting Processes and the Poisson Process

A stochastic process in continuous time is a family $(X(t))_{t\ge0}$ of random variables on one probability space. We shall always use versions whose sample paths $t\mapsto X(t)$ are right-continuous step functions.

📘 Definition 3.10 — Counting process; independent and stationary increments
A counting process is a process $(N(t))_{t\ge0}$ such that $N(0)=0$, each $N(t)$ takes values in $\{0,1,2,\dots\}$, and every sample path is nondecreasing, right-continuous and increases only by jumps of size $1$. The arrival times are $S_n=\inf\{t:N(t)\ge n\}$ ($S_0=0$) and the inter-arrival times are $E_n=S_n-S_{n-1}$; thus $N(t)=\#\{n\ge1:S_n\le t\}$ and $\{N(t)\ge n\}=\{S_n\le t\}$. The increment over $(s,t]$ is $N(t)-N(s)$, the number of events in that interval.
The process has independent increments if for all $0\le t_0\lt t_1\lt\cdots\lt t_k$ the increments $N(t_1)-N(t_0),\dots,N(t_k)-N(t_{k-1})$ are independent, and stationary increments if the law of $N(t+s)-N(s)$ depends only on $t$.
📘 Definition 3.11 — The Poisson process of rate $\lambda$ (three definitions)

Let $\lambda\gt0$. A counting process $N$ is a Poisson process of rate (intensity) $\lambda$, written $N\sim\mathrm{PP}(\lambda)$, if one of the following holds.

  1. (A, counts) $N$ has independent increments and $N(t+s)-N(s)\sim\operatorname{Poi}(\lambda t)$ for all $s,t\ge0$.
  2. (B, infinitesimal) $N$ has independent and stationary increments, and as $h\downarrow0$ $$P(N(h)=1)=\lambda h+o(h),\qquad P(N(h)\ge2)=o(h).$$
  3. (C, gaps) The inter-arrival times $E_1,E_2,\dots$ are iid $\operatorname{Exp}(\lambda)$.

Definition (B) is the modelling definition: it asks only that disjoint time intervals do not influence each other, that the process is time-homogeneous, and that events come one at a time at a steady rate. That such weak assumptions force Poisson counts is the reason Poisson processes appear everywhere. Definition (C) is the constructive one: it tells us how to simulate the process, as Interactive 1 does. We first work under (C).

📐 Theorem 3.28 — Arrival times; uniform arrivals given $N(t)$
Let the inter-arrival times $E_1,E_2,\dots$ be iid $\operatorname{Exp}(\lambda)$ and $S_n=E_1+\cdots+E_n$.
  1. $(S_1,\dots,S_n)$ has joint density $\lambda^ne^{-\lambda s_n}$ on $\{0\lt s_1\lt s_2\lt\cdots\lt s_n\}$; in particular $S_n\sim\operatorname{Gamma}(n,\lambda)$, with density $\lambda^ns^{n-1}e^{-\lambda s}/(n-1)!$.
  2. $N(t)\sim\operatorname{Poi}(\lambda t)$ for every $t\gt0$.
  3. (Order-statistics property) Given $N(t)=n\ge1$, the arrival times $(S_1,\dots,S_n)$ have the density $$f(s_1,\dots,s_n\mid N(t)=n)=\frac{n!}{t^n}\qquad\text{on }0\lt s_1\lt\cdots\lt s_n\lt t,$$ which is the joint density of the order statistics $U_{(1)}\lt\cdots\lt U_{(n)}$ of $n$ iid $U(0,t)$ variables. In words: given that $n$ events happened in $[0,t]$, their times are $n$ independent uniform points, sorted.

Proof. (1) The vector $(E_1,\dots,E_{n})$ has density $\prod_k\lambda e^{-\lambda e_k}=\lambda^{n}e^{-\lambda(e_1+\cdots+e_{n})}$ on $(0,\infty)^{n}$. The linear map $s_k=e_1+\cdots+e_k$ is a bijection from $(0,\infty)^n$ onto $\{0\lt s_1\lt\cdots\lt s_n\}$ whose matrix is lower triangular with ones on the diagonal, so its Jacobian is $1$ (§1.4). Hence $(S_1,\dots,S_n)$ has density $\lambda^ne^{-\lambda s_n}$ there. Integrating out $s_1,\dots,s_{n-1}$ over $0\lt s_1\lt\cdots\lt s_{n-1}\lt s$ (a region of volume $s^{n-1}/(n-1)!$) gives the gamma density of $S_n$.

(2) This is the gamma–Poisson identity of §2.1: $\{N(t)\ge n\}=\{S_n\le t\}$, and $P(S_n\le t)=1-\sum_{k\lt n}e^{-\lambda t}(\lambda t)^k/k!$. It also follows from the computation in (3).

(3) The event $\{N(t)=n\}$ is $\{S_n\le t\lt S_{n+1}\}$. For a set $B\subseteq\{0\lt s_1\lt\cdots\lt s_n\lt t\}$, by (1) applied to $(S_1,\dots,S_{n+1})$, $$P\left((S_1,\dots,S_n)\in B,\ N(t)=n\right)=\int_B\int_t^\infty\lambda^{n+1}e^{-\lambda s_{n+1}}\,ds_{n+1}\,ds_1\cdots ds_n=\int_B\lambda^ne^{-\lambda t}\,ds_1\cdots ds_n.$$ Taking $B$ to be the whole region (volume $t^n/n!$) gives $P(N(t)=n)=e^{-\lambda t}(\lambda t)^n/n!$, which proves (2) again. Dividing, the conditional density is the constant $\lambda^ne^{-\lambda t}\big/\left(e^{-\lambda t}(\lambda t)^n/n!\right)=n!/t^n$. Finally, $n$ iid $U(0,t)$ variables have joint density $t^{-n}$ on $(0,t)^n$; each ordered configuration arises from $n!$ unordered ones, so the order statistics have density $n!/t^n$ on $\{0\lt u_1\lt\cdots\lt u_n\lt t\}$. ∎

📐 Theorem 3.29 — The three definitions are equivalent
For a counting process $N$ and $\lambda\gt0$, the conditions (A), (B) and (C) of Definition 3.11 are equivalent.

Proof. (C) ⇒ (A). Fix $0=t_0\lt t_1\lt\cdots\lt t_k=t$, write $\ell_j=t_j-t_{j-1}$, and let $n_1,\dots,n_k\ge0$ with $n=\sum n_j$. By Theorem 3.28(3), given $N(t)=n$ the event times are $n$ iid uniform points on $(0,t)$ (sorting does not change how many fall in each interval). So the counts in the $k$ intervals are multinomial with probabilities $\ell_j/t$: $$P\left(N(t_j)-N(t_{j-1})=n_j\ \forall j\right)=e^{-\lambda t}\frac{(\lambda t)^n}{n!}\cdot\frac{n!}{n_1!\cdots n_k!}\prod_{j=1}^k\left(\frac{\ell_j}{t}\right)^{n_j}=\prod_{j=1}^ke^{-\lambda\ell_j}\frac{(\lambda\ell_j)^{n_j}}{n_j!},$$ using $e^{-\lambda t}=\prod_je^{-\lambda\ell_j}$ and $t^n=\prod_jt^{n_j}$. The joint pmf factorises into $\operatorname{Poi}(\lambda\ell_j)$ pmfs: the increments are independent and Poisson with mean $\lambda\times$length. (This is the Poisson splitting theorem of §2.1 with $k$ types.)

(A) ⇒ (B). The law $\operatorname{Poi}(\lambda t)$ of $N(t+s)-N(s)$ does not depend on $s$, so the increments are stationary. As $h\downarrow0$, $P(N(h)=1)=\lambda he^{-\lambda h}=\lambda h+o(h)$ and $P(N(h)\ge2)=1-e^{-\lambda h}(1+\lambda h)$ $=\frac{(\lambda h)^2}{2}+O(h^3)=o(h)$.

(B) ⇒ (A). Put $p_n(t)=P(N(t)=n)$. By independence and stationarity of increments, $p_0(t+h)=P(N(t)=0)\,P(N(t+h)-N(t)=0)$ $=p_0(t)\,p_0(h)$, and $p_0(h)=1-\lambda h+o(h)$ by (B). Hence $$\frac{p_0(t+h)-p_0(t)}{h}=p_0(t)\,\frac{p_0(h)-1}{h}\to-\lambda p_0(t).$$ For $n\ge1$, split according to the number of events in $(t,t+h]$: $$p_n(t+h)=p_n(t)\,p_0(h)+p_{n-1}(t)\,p_1(h)+\sum_{k\ge2}p_{n-k}(t)\,P(N(h)=k)=p_n(t)(1-\lambda h)+p_{n-1}(t)\lambda h+o(h),$$ the last sum being at most $P(N(h)\ge2)=o(h)$. So the right derivatives satisfy $$p_0'=-\lambda p_0,\qquad p_n'=-\lambda p_n+\lambda p_{n-1}\quad(n\ge1),\qquad p_0(0)=1,\ p_n(0)=0.$$ (Repeating the argument on $[t-h,t]$ gives the same left derivatives, so the $p_n$ are differentiable.) Then $p_0(t)=e^{-\lambda t}$, and $\frac{d}{dt}\left(e^{\lambda t}p_n(t)\right)=\lambda e^{\lambda t}p_{n-1}(t)$, so by induction $e^{\lambda t}p_n(t)=\int_0^t\lambda\frac{(\lambda s)^{n-1}}{(n-1)!}ds=\frac{(\lambda t)^n}{n!}$. Thus $N(t)\sim\operatorname{Poi}(\lambda t)$, and by stationarity so is every increment of length $t$.

(A) ⇒ (C). Under (A), independence of increments and their Poisson laws fix all the joint laws of $(N(t_1),\dots,N(t_k))$. The process built in (C) satisfies (A) by the first step, so it has the same finite-dimensional laws. The joint law of $(S_1,\dots,S_n)$ is determined by these: $$P(S_1\le u_1,\dots,S_n\le u_n)=P(N(u_1)\ge1,\dots,N(u_n)\ge n).$$ Hence under (A) the arrival times have the same law as in (C), and the inter-arrival times are iid $\operatorname{Exp}(\lambda)$. ∎

The differential equations in (B) ⇒ (A) are our first Kolmogorov forward equations: they describe the flow of probability from state $n-1$ to state $n$ at rate $\lambda$. We shall meet them again for every continuous-time Markov chain.

📐 Theorem 3.30 — Restart property, moments and the long-run rate
Let $N\sim\mathrm{PP}(\lambda)$.
  1. (Markov / restart property) For each fixed $s\ge0$, the process $M(t)=N(s+t)-N(s)$ is again a $\mathrm{PP}(\lambda)$, and it is independent of $(N(u))_{u\le s}$. In particular the residual waiting time $S_{N(s)+1}-s$ from $s$ to the next event is $\operatorname{Exp}(\lambda)$, whatever happened before $s$. (The same holds when $s$ is replaced by a stopping time, such as $S_k$; we use this without proof.)
  2. $E[N(t)]=\operatorname{Var}(N(t))=\lambda t$ and $\operatorname{Cov}(N(s),N(t))=\lambda\min(s,t)$.
  3. $N(t)/t\to\lambda$ almost surely as $t\to\infty$.

Proof. (1) $M(0)=0$ and $M$ is a counting process. Its increments over $(t_{j-1},t_j]$ are increments of $N$ over $(s+t_{j-1},s+t_j]$, so they are independent with $\operatorname{Poi}(\lambda(t_j-t_{j-1}))$ laws: $M$ satisfies (A). Every finite collection of the variables $N(u)$, $u\le s$, is a function of increments of $N$ inside $[0,s]$, which are independent of the increments of $N$ after $s$; this gives the independence. The residual time is the first arrival time of $M$, which is $\operatorname{Exp}(\lambda)$ by (C).

(2) Mean and variance are those of $\operatorname{Poi}(\lambda t)$. For $s\le t$, $N(t)=N(s)+(N(t)-N(s))$ with independent summands, so $\operatorname{Cov}(N(s),N(t))=\operatorname{Var}(N(s))=\lambda s$.

(3) By the strong law of large numbers (§2.3), $S_n/n\to1/\lambda$ almost surely, so $S_n\to\infty$ and $N(t)\to\infty$. From $S_{N(t)}\le t\lt S_{N(t)+1}$, $$\frac{N(t)}{S_{N(t)+1}}\lt\frac{N(t)}{t}\le\frac{N(t)}{S_{N(t)}},$$ and both bounds tend to $\lambda$ almost surely (the left one is $\frac{N(t)}{N(t)+1}\cdot\frac{N(t)+1}{S_{N(t)+1}}$). ∎

✏️ Example 1 — Calls to a helpline
Calls reach a helpline as a Poisson process with rate $4$ per hour, starting at time $0$. Find (a) the probability of exactly $3$ calls in the first half hour; (b) the probability of $2$ calls in the first half hour and $3$ in the first hour; (c) $P(N(1)=3\mid N(\frac12)=2)$ and $P(N(\frac12)=2\mid N(1)=3)$; (d) the mean and standard deviation of the time of the fifth call, and the probability that it comes within the first hour; (e) the correlation between $N(\frac12)$ and $N(1)$.
(a) $N(\frac12)\sim\operatorname{Poi}(2)$: $P(N(\frac12)=3)=e^{-2}\frac{2^3}{3!}=\frac43e^{-2}\approx0.1804$.
(b) Independent increments Overlapping counts must be rewritten with disjoint intervals: $\{N(\frac12)=2,\ N(1)=3\}=\{N(\frac12)=2,\ N(1)-N(\frac12)=1\}$, and the two increments are independent $\operatorname{Poi}(2)$ variables. So the probability is $2e^{-2}\cdot2e^{-2}=4e^{-4}\approx0.0733$.
(c) Forwards and backwards Forwards: $P(N(1)=3\mid N(\frac12)=2)=P(N(1)-N(\frac12)=1)=2e^{-2}\approx0.2707$ (independence). Backwards: given $N(1)=3$, the three call times are iid uniform on $(0,1)$ (Theorem 3.28(3)), so the number in the first half is $\operatorname{Bin}(3,\frac12)$ and $P(N(\frac12)=2\mid N(1)=3)=\binom32\frac18=\frac38$. Notice that the rate $\lambda$ has disappeared.
(d) Gamma arrival time $S_5\sim\operatorname{Gamma}(5,4)$: $E[S_5]=\frac54$ h $=75$ min and $\operatorname{SD}(S_5)=\frac{\sqrt5}{4}$ h $\approx33.5$ min. Also $P(S_5\le1)=P(N(1)\ge5)=1-e^{-4}\left(1+4+8+\frac{32}3+\frac{32}3\right)=1-\frac{103}{3}e^{-4}\approx0.3712$.
(e) By Theorem 3.30(2), $\operatorname{Corr}=\frac{\lambda\cdot\frac12}{\sqrt{\lambda\cdot\frac12\cdot\lambda\cdot1}}=\sqrt{\tfrac12}\approx0.707$. Counts over nested intervals are positively correlated; only counts over disjoint intervals are independent.
✏️ Example 2 — Prove or disprove: four statements about a Poisson process
Let $N\sim\mathrm{PP}(\lambda)$. Prove or disprove: (a) given that no event occurred in $[0,s]$, the time of the first event is distributed as $s+\operatorname{Exp}(\lambda)$; (b) the inter-arrival interval that contains a fixed time $t$ has mean length $1/\lambda$; (c) $N(t)/t\to\lambda$ almost surely; (d) $2N(t)$ is a Poisson process of rate $2\lambda$.
(a) True $\{N(s)=0\}=\{S_1\gt s\}$ and $P(S_1-s\gt x\mid S_1\gt s)=e^{-\lambda(s+x)}/e^{-\lambda s}=e^{-\lambda x}$: the memoryless property of the exponential law (§2.1). More is true: by Theorem 3.30(1) the whole process after $s$ is a fresh $\mathrm{PP}(\lambda)$.
(b) False: the inspection paradox Write the interval containing $t$ as $A(t)+R(t)$, with the age $A(t)=t-S_{N(t)}$ and the residual life $R(t)=S_{N(t)+1}-t$. By the restart property $R(t)\sim\operatorname{Exp}(\lambda)$, independent of $A(t)$, so $E[R(t)]=\frac1\lambda$. For $0\le a\lt t$, $A(t)\gt a$ means no event in $(t-a,t]$, so $P(A(t)\gt a)=e^{-\lambda a}$, while $A(t)\le t$ always. Hence $E[A(t)]=\int_0^te^{-\lambda a}da=\frac{1-e^{-\lambda t}}{\lambda}$ and $$E[A(t)+R(t)]=\frac{2-e^{-\lambda t}}{\lambda}\ \longrightarrow\ \frac2\lambda.$$ A passenger arriving at a random time at a stop served by Poisson buses with mean gap $10$ minutes waits $10$ minutes on average (not $5$), and lands in a gap of mean length almost $20$ minutes. Long gaps are more likely to contain the inspection time.
(c) True Theorem 3.30(3); this is how $\lambda$ is estimated from one long record.
(d) False $2N(t)$ jumps by $2$, so it is not even a counting process in the sense of Definition 3.10. Also $\operatorname{Var}(2N(t))=4\lambda t\ne2\lambda t=E[2N(t)]$, whereas a Poisson count has variance equal to its mean. On the other hand $N(2t)$ is a $\mathrm{PP}(2\lambda)$ (check (A)), and so is the sum of two independent $\mathrm{PP}(\lambda)$ processes (Theorem 3.31).

Thinning, Superposition and Compound Poisson Processes

A stream of events is often split (calls are local or international; particles are detected or missed) or merged (two bus routes share a stop). For Poisson streams both operations stay inside the Poisson family, and splitting produces independent streams.

📐 Theorem 3.31 — Superposition and thinning
  1. (Superposition) If $N_1,\dots,N_k$ are independent with $N_i\sim\mathrm{PP}(\lambda_i)$, then $N=N_1+\cdots+N_k\sim\mathrm{PP}(\lambda)$ with $\lambda=\sum_i\lambda_i$. Each event of $N$ comes from $N_i$ with probability $\lambda_i/\lambda$, independently of the times of the events and of the sources of the other events. In particular the first event comes from $N_1$ with probability $\lambda_1/(\lambda_1+\cdots+\lambda_k)$.
  2. (Thinning) Let $N\sim\mathrm{PP}(\lambda)$ and let each event, independently of everything else, be of type $1$ with probability $p$ and of type $2$ with probability $1-p$. Then the type-$1$ and type-$2$ counting processes are independent Poisson processes with rates $\lambda p$ and $\lambda(1-p)$.
  3. (Time-dependent marking) If instead an event at time $s$ is of type $1$ with probability $p(s)$ (a measurable function), independently of all other events, then $N_1(t)$ and $N_2(t)$ are independent with $$N_1(t)\sim\operatorname{Poi}\left(\lambda\int_0^tp(s)\,ds\right),\qquad N_2(t)\sim\operatorname{Poi}\left(\lambda\int_0^t(1-p(s))\,ds\right).$$

Proof. (1) Use (A). For disjoint intervals, the increments of $N$ are sums of increments of the independent $N_i$, so they are independent; an increment of length $t$ is a sum of independent $\operatorname{Poi}(\lambda_it)$ variables, hence $\operatorname{Poi}(\lambda t)$ (sums of independent Poisson variables, §2.1). For the sources: the first event of $N$ is at $\min_iS^{(i)}_1$, a minimum of independent $\operatorname{Exp}(\lambda_i)$ variables. For $k=2$, $P(S^{(1)}_1\lt S^{(2)}_1)=\int_0^\infty\lambda_1e^{-\lambda_1x}e^{-\lambda_2x}dx=\frac{\lambda_1}{\lambda_1+\lambda_2}$, and the same computation gives $\lambda_i/\lambda$ in general. Moreover $P(\min=S_1^{(1)}\gt x)=\int_x^\infty\lambda_1e^{-\lambda u}du=\frac{\lambda_1}{\lambda}e^{-\lambda x}$ factorises, so the source is independent of the time. After the first event all $k$ processes restart afresh (Theorem 3.30(1) at a stopping time), which gives independence of the later sources.

(2) Fix a partition $0=t_0\lt\cdots\lt t_k$. The increments $D_j=N(t_j)-N(t_{j-1})$ are independent $\operatorname{Poi}(\lambda\ell_j)$, and the types of the events in different intervals are independent. By the splitting theorem for a Poisson count (§2.1), each $D_j$ splits into independent $\operatorname{Poi}(\lambda p\ell_j)$ and $\operatorname{Poi}(\lambda(1-p)\ell_j)$ counts. So the $2k$ variables (type-$1$ and type-$2$ increments over the $k$ intervals) are independent Poisson variables with the right means. Hence $N_1$ and $N_2$ both satisfy (A), and all their joint laws factorise, so they are independent processes.

(3) Condition on $N(t)=n$. By Theorem 3.28(3) the $n$ event times, in random order, are iid $U(0,t)$, so each event is independently of type $1$ with probability $\bar p=\frac1t\int_0^tp(s)\,ds$. Exactly as in the splitting theorem, $$P(N_1(t)=i,\ N_2(t)=j)=e^{-\lambda t}\frac{(\lambda t)^{i+j}}{(i+j)!}\binom{i+j}{i}\bar p^{\,i}(1-\bar p)^j=e^{-\lambda t\bar p}\frac{(\lambda t\bar p)^i}{i!}\cdot e^{-\lambda t(1-\bar p)}\frac{(\lambda t(1-\bar p))^j}{j!}.\ ∎$$

Thinning must be independent of the process. Keeping every second event of a $\mathrm{PP}(\lambda)$ halves the rate too, but the gaps of the result are $\operatorname{Gamma}(2,\lambda)$, not exponential, so the thinned stream is not Poisson. Interactive 1 shows independent thinning at work: the scatter of $(N_1(T),N_2(T))$ over many runs shows no trend at all.

✏️ Example 3 — Patients in an emergency department (the M/G/∞ model)
Patients arrive at an emergency department as a Poisson process of rate $6$ per hour, starting at 8:00 with the department empty. Each patient stays for a random time with distribution $G$, independently of the others and of the arrivals; there is room for everyone. Take $G=\operatorname{Exp}$ with mean $2$ hours. (a) Find the distribution of the number $X(t)$ of patients present $t$ hours after 8:00, and $P(X(4)\ge10)$. (b) Show that the number of patients discharged by time $t$ is independent of $X(t)$. (c) Find the limiting distribution of $X(t)$ and the long-run probability that more than $15$ patients are present. Would the limit change if stays were uniform on $[1,3]$ hours? (d) Find the probability that the department is empty at 9:00.
Marking A patient arriving at time $s\le t$ is still present at $t$ iff the stay exceeds $t-s$, which happens with probability $p(s)=1-G(t-s)$, independently of the others. By Theorem 3.31(3), $X(t)\sim\operatorname{Poi}(m(t))$ with $m(t)=6\int_0^t(1-G(t-s))\,ds=6\int_0^t(1-G(u))\,du$.
(a) $1-G(u)=e^{-u/2}$, so $m(t)=12\left(1-e^{-t/2}\right)$. At noon ($t=4$), $m(4)=12(1-e^{-2})\approx10.376$ and $P(X(4)\ge10)=1-P(\operatorname{Poi}(10.376)\le9)\approx0.588$.
(b) "Present" and "discharged" are the two types of a time-dependent marking, so by Theorem 3.31(3) they are independent, the discharged number being $\operatorname{Poi}(6t-m(t))$; at $t=4$ its mean is $24-10.376=13.624$. This is far from obvious: knowing that the department is crowded tells us nothing about how many have left.
(c) As $t\to\infty$, $m(t)\uparrow6\int_0^\infty(1-G(u))\,du=6\,E[\text{stay}]=12$ (the tail formula for the mean, §1.3). So $X(t)\Rightarrow\operatorname{Poi}(12)$, and $P(\operatorname{Poi}(12)\gt15)\approx0.156$. The limit depends on $G$ only through its mean, so uniform stays on $[1,3]$ (mean $2$) give the same $\operatorname{Poi}(12)$ limit, although $m(t)$ is different for $t\lt3$. This "insensitivity" is special to systems with unlimited capacity.
(d) $P(X(1)=0)=e^{-m(1)}=\exp\left(-12(1-e^{-1/2})\right)\approx0.0089$.
📘 Definition 3.12 — Compound Poisson process
Let $N\sim\mathrm{PP}(\lambda)$ and let $Y_1,Y_2,\dots$ be iid real random variables, independent of $N$. The process $$X(t)=\sum_{i=1}^{N(t)}Y_i\qquad(X(t)=0\text{ if }N(t)=0)$$ is a compound Poisson process. Think of $N$ as counting insurance claims and $Y_i$ as their sizes, or $N$ as counting buses and $Y_i$ as the number of passengers on each.
📐 Theorem 3.32 — Moments of a compound Poisson process
Let $X$ be compound Poisson with rate $\lambda$ and jump law $Y$.
  1. $X$ has independent and stationary increments.
  2. If $E|Y|\lt\infty$, then $E[X(t)]=\lambda t\,E[Y]$; if $E[Y^2]\lt\infty$, then $\operatorname{Var}(X(t))=\lambda t\,E[Y^2]$ (the second moment of $Y$, not its variance).
  3. Wherever $M_Y(u)=E[e^{uY}]$ is finite, $M_{X(t)}(u)=\exp\left(\lambda t\,(M_Y(u)-1)\right)$.
  4. If $Y$ takes the values $y_1,\dots,y_k$ with probabilities $p_1,\dots,p_k$, then $X(t)=\sum_jy_jN_j(t)$ with independent $N_j\sim\mathrm{PP}(\lambda p_j)$.

Proof. (3) Conditioning on $N(t)=n$, the sum of $n$ iid copies of $Y$ has mgf $M_Y(u)^n$, so $M_{X(t)}(u)=E\left[M_Y(u)^{N(t)}\right]$ $=G_{N(t)}(M_Y(u))=e^{\lambda t(M_Y(u)-1)}$, where $G_{N(t)}(s)=e^{\lambda t(s-1)}$ is the Poisson pgf (§2.1). (2) $E[X(t)\mid N(t)]=N(t)E[Y]$ and $\operatorname{Var}(X(t)\mid N(t))=N(t)\operatorname{Var}(Y)$. The tower property and the law of total variance (§1.4) give $E[X(t)]=\lambda tE[Y]$ and $\operatorname{Var}(X(t))=\lambda t\operatorname{Var}(Y)+\lambda t(E[Y])^2=\lambda tE[Y^2]$. (4) Mark each event by the value of its $Y$; Theorem 3.31(2), with $k$ types, makes the $N_j$ independent Poisson processes. (1) The increment over $(s,t]$ is the sum of the $Y_i$ attached to the events in $(s,t]$; these depend only on the increments of $N$ in $(s,t]$ and on $Y$'s not used by other intervals, which gives independence, and its law is that of $X(t-s)$. ∎

For example, if claims arrive at $5$ per day and claim sizes have mean $20$ and standard deviation $30$ (in thousands of rupees), the total claimed in $30$ days has mean $150\times20=3000$ and variance $150\times(30^2+20^2)=195\,000$, so its standard deviation is about $442$ (thousand rupees). Because $X(t)$ is a sum of a large random number of iid terms, it is approximately normal when $\lambda t$ is large (Exercise II.7).

Interactive 1 — A Poisson Stream, Thinned into Two Independent Streams

Events of a Poisson process of rate $\lambda$ are generated on $[0,T]$, $T=10$, from exponential gaps (Definition (C), seeded generator). Each event is coloured red (type 1) with probability $p$ and blue (type 2) otherwise. The top panel shows one run: the step functions $N(t)$, $N_1(t)$ and $N_2(t)$. ▶ Play repeats the experiment many times. Bottom left: the histogram of $N_1(T)$ against the $\operatorname{Poi}(\lambda pT)$ probabilities (purple). Bottom right: the scatter of the pairs $(N_1(T),N_2(T))$. There is no trend, and the sample correlation stays near $0$: the two streams are independent (Theorem 3.31(2)), although they are cut from the same stream.

2.00.30
runs—
N₁(T): mean / variance (theory λpT)—
corr(N₁(T), N₂(T))—
mean wait for first red event (theory 1/(λp))—

Continuous-Time Markov Chains

A Poisson process waits an exponential time and jumps from $n$ to $n+1$. Allowing the waiting rate and the target of the jump to depend on the current state gives the general continuous-time Markov chain.

📘 Definition 3.13 — Continuous-time Markov chain; transition function
Let $S$ be finite or countable. A process $(X(t))_{t\ge0}$ with values in $S$ and right-continuous step-function paths is a (time-homogeneous) continuous-time Markov chain (CTMC) with transition function $P(t)=(p_{ij}(t))_{i,j\in S}$ if for all $n$, all times $0\le t_0\lt t_1\lt\cdots\lt t_n\lt t_{n+1}$ and all states, $$P\left(X(t_{n+1})=j\mid X(t_n)=i,\ X(t_{n-1})=i_{n-1},\dots,X(t_0)=i_0\right)=p_{ij}(t_{n+1}-t_n)$$ whenever the conditioning event has positive probability. Each $P(t)$ is a stochastic matrix, $P(0)=I$, and the Chapman–Kolmogorov equations $P(s+t)=P(s)P(t)$ hold (condition on $X(s)$, as in §3.1). We assume that $P(t)\to I$ as $t\downarrow0$ (a standard transition function).
📘 Definition 3.14 — Generator, holding rates and jump chain
The generator (Q-matrix, rate matrix) of the chain is $Q=P'(0)$: $$q_{ij}=\lim_{h\downarrow0}\frac{p_{ij}(h)}{h}\ge0\ (i\ne j),\qquad q_i=-q_{ii}=\lim_{h\downarrow0}\frac{1-p_{ii}(h)}{h}.$$ We assume these limits exist, are finite and $\sum_{j\ne i}q_{ij}=q_i$ (a conservative generator; this always holds for finite $S$). So $Q$ has nonnegative off-diagonal entries and row sums $0$. The number $q_{ij}$ is the rate of jumps from $i$ to $j$, and $q_i$ is the total rate of leaving $i$. The jump chain (embedded chain) is the discrete-time chain with transition matrix $R=(r_{ij})$, where $r_{ij}=q_{ij}/q_i$ for $j\ne i$ and $r_{ii}=0$ when $q_i\gt0$, and $r_{ii}=1$ when $q_i=0$ (then $i$ is absorbing).
📐 Theorem 3.33 — Holding times and jumps
Let $X$ be a CTMC with conservative generator $Q$, started at $i$, and let $H=\inf\{t\ge0:X(t)\ne i\}$ be the holding time in $i$. Then $H\sim\operatorname{Exp}(q_i)$ ($H=\infty$ if $q_i=0$); the state $X(H)$ entered at the jump is independent of $H$ with $P(X(H)=j)=q_{ij}/q_i$; and after the jump the chain starts afresh from $X(H)$. Hence the chain visits the states $Y_0,Y_1,Y_2,\dots$ of a Markov chain with matrix $R$, staying in $Y_n$ for an $\operatorname{Exp}(q_{Y_n})$ time, the holding times being conditionally independent given $(Y_n)$.
Conversely, for any conservative $Q$ this recipe constructs a CTMC with generator $Q$, provided the chain does not explode, i.e. the holding times add up to $\infty$ almost surely. Explosion is impossible if $S$ is finite, if $\sup_iq_i\lt\infty$, or if the jump chain is recurrent.

Proof sketch. Paths are right-continuous step functions, so $\{H\gt s\}$ is the event that $X(u)=i$ for all $u\in[0,s]$, an event determined by the past up to time $s$ (approximate it by the events $\{X(u)=i$ for dyadic $u\le s\}$). By the Markov property at time $s$, $P_i(H\gt s+t\mid H\gt s)=P_i(H\gt t)$. So $H$ is memoryless, and the only memoryless laws on $(0,\infty]$ are the exponential laws and the point mass at $\infty$ (§2.1): $P_i(H\gt t)=e^{-ct}$ for some $c\in[0,\infty)$. Now $p_{ii}(h)$ differs from $P_i(H\gt h)$ by at most the probability of at least two jumps in $[0,h]$, which is $o(h)$; so $1-p_{ii}(h)=ch+o(h)$ and $c=q_i$. Similarly $P_i(X(H)=j)=\lim_{h\downarrow0}P_i(X(h)=j\mid X(h)\ne i)$ $=\lim_h\frac{p_{ij}(h)}{1-p_{ii}(h)}=\frac{q_{ij}}{q_i}$. Independence of $H$ and $X(H)$, and the fresh start, come from the strong Markov property at the stopping time $H$.

For the converse, the construction defines $X(t)$ for all $t$ only when $\sum_nH_n=\infty$. If $q_i\le c$ for all $i$, then $H_n\ge\tilde H_n/c$ with $\tilde H_n=q_{Y_n}H_n$ iid $\operatorname{Exp}(1)$, and $\sum_n\tilde H_n=\infty$ almost surely by the strong law. If the jump chain is recurrent, it visits some state $i$ infinitely often, and the infinitely many iid $\operatorname{Exp}(q_i)$ holding times there already sum to $\infty$. Checking the Markov property of the constructed process uses the memoryless property once more. ∎

📐 Theorem 3.34 — Kolmogorov backward and forward equations

Let $S$ be finite with generator $Q$. Then $t\mapsto P(t)$ is differentiable and $$P'(t)=QP(t)\ \ (\text{backward}),\qquad P'(t)=P(t)Q\ \ (\text{forward}),\qquad P(0)=I.$$ The unique solution is the matrix exponential $P(t)=e^{tQ}=\sum_{n\ge0}\frac{t^nQ^n}{n!}$. In coordinates,

$$p_{ij}'(t)=-q_i\,p_{ij}(t)+\sum_{k\ne i}q_{ik}\,p_{kj}(t),\qquad p_{ij}'(t)=-p_{ij}(t)\,q_j+\sum_{k\ne j}p_{ik}(t)\,q_{kj}.$$

For a distribution $p(t)=\lambda P(t)$ of $X(t)$, the forward equation reads $p'(t)=p(t)Q$. For countable $S$ the backward equations always hold; the forward equations and $P(t)=e^{tQ}$ hold when $\sup_iq_i\lt\infty$, and the forward equations hold for every non-explosive birth–death process below.

Proof. By Chapman–Kolmogorov, $P(t+h)-P(t)=(P(h)-I)P(t)$ $=P(t)(P(h)-I)$. Dividing by $h\gt0$ and letting $h\downarrow0$ (a finite matrix, so limits can be taken entry by entry) gives the right derivative $QP(t)=P(t)Q$. For the left derivative write $P(t)-P(t-h)=(P(h)-I)P(t-h)$. First, $P$ is continuous: $$|p_{ij}(t)-p_{ij}(t-h)|\le\sum_k|p_{ik}(h)-\delta_{ik}|\,p_{kj}(t-h)\le2(1-p_{ii}(h))\to0.$$ Hence $\frac{P(t)-P(t-h)}{h}=\frac{P(h)-I}{h}\,P(t-h)\to QP(t)$, and the two one-sided derivatives agree. For uniqueness, if $F'(t)=QF(t)$ and $F(0)=I$, then $\frac{d}{dt}\left(e^{-tQ}F(t)\right)=e^{-tQ}(-Q+Q)F(t)=0$, so $F(t)=e^{tQ}$; the same works for the forward equation. ∎

The two equations have different meanings. The backward equation conditions on what happens in the first short interval $[0,h]$ (leave $i$ at rate $q_i$, to $k$ at rate $q_{ik}$); the forward equation conditions on the last interval $[t,t+h]$: probability flows into $j$ from each $k$ at rate $q_{kj}$ and out of $j$ at rate $q_j$. For a $\mathrm{PP}(\lambda)$, viewed as a CTMC on $\{0,1,2,\dots\}$ with $q_{n,n+1}=\lambda$, the forward equations are exactly the equations $p_n'=\lambda p_{n-1}-\lambda p_n$ of Theorem 3.29.

✏️ Example 4 — A machine that fails and is repaired, in continuous time
A machine works for an $\operatorname{Exp}(\alpha)$ time, is then repaired for an $\operatorname{Exp}(\beta)$ time, and so on, all times independent. Let $X(t)=0$ if it works and $1$ if it is under repair. Find $P(t)$, the long-run availability, and, with $\alpha=0.1$ and $\beta=0.5$ per hour, the probability that a machine working at time $0$ is working at time $3$ h, and its expected working time during the first $10$ hours. Compare with the jump chain.
Generator $Q=\begin{pmatrix}-\alpha&\alpha\\\beta&-\beta\end{pmatrix}$.
Forward equation $p_{00}'=-\alpha p_{00}+\beta p_{01}=-\alpha p_{00}+\beta(1-p_{00})=\beta-(\alpha+\beta)p_{00}$, $p_{00}(0)=1$. This linear equation has solution $$p_{00}(t)=\frac{\beta}{\alpha+\beta}+\frac{\alpha}{\alpha+\beta}e^{-(\alpha+\beta)t},$$ and in the same way $p_{11}(t)=\frac{\alpha}{\alpha+\beta}+\frac{\beta}{\alpha+\beta}e^{-(\alpha+\beta)t}$, with $p_{01}=1-p_{00}$, $p_{10}=1-p_{11}$. (Equivalently, $Q^2=-(\alpha+\beta)Q$ gives $e^{tQ}=I+\frac{1-e^{-(\alpha+\beta)t}}{\alpha+\beta}Q$; Exercise III.2.)
Numbers The long-run availability is $\frac{\beta}{\alpha+\beta}=\frac{0.5}{0.6}=\frac56$. Here $p_{00}(t)=\frac56+\frac16e^{-0.6t}$, so $p_{00}(3)=\frac56+\frac16e^{-1.8}\approx0.8609$. The expected working time in $[0,10]$ is $\int_0^{10}p_{00}(t)\,dt=\frac{50}{6}+\frac{1-e^{-6}}{6\times0.6}\approx8.61$ hours.
Jump chain $R=\begin{pmatrix}0&1\\1&0\end{pmatrix}$: the flip chain of §3.2, periodic, with stationary distribution $(\frac12,\frac12)$. The CTMC is not periodic at all: $P(t)$ converges, to rows $(\frac56,\frac16)$. The two stationary distributions differ because the CTMC spends a mean time $1/\alpha=10$ h in state $0$ per visit and only $1/\beta=2$ h in state $1$.
📐 Theorem 3.35 — Stationary distributions and convergence of a CTMC

Let $X$ be an irreducible CTMC (every state leads to every other, i.e. its jump chain is irreducible) with conservative generator $Q$ and $q_i\gt0$ for all $i$.

  1. A measure $\lambda$ satisfies $\lambda Q=0$ if and only if $\nu_j=\lambda_jq_j$ is an invariant measure of the jump chain: $\nu R=\nu$.
  2. If $S$ is finite, a distribution $\pi$ satisfies $\pi P(t)=\pi$ for all $t$ if and only if $\pi Q=0$. Such a $\pi$ exists, is unique, and $\pi_j\gt0$ for all $j$.
  3. Suppose the jump chain is recurrent, and let $m_i=E_i(T_i^+)$ be the mean return time, where $T_i^+=\inf\{t\ge H:X(t)=i\}$. Then $m_i\lt\infty$ for every $i$ (positive recurrence) if and only if there is a probability vector $\pi$ with $\pi Q=0$; then $\pi$ is unique and $$\pi_i=\frac{1}{q_i\,m_i}=\frac{\text{mean holding time in }i}{\text{mean return time to }i}.$$
  4. In the situation of (2), or of (3) with positive recurrence, $p_{ij}(t)\to\pi_j$ as $t\to\infty$ for all $i,j$, and $\frac1t\int_0^t\mathbf 1\{X(s)=j\}\,ds\to\pi_j$ almost surely. There is no periodicity in continuous time.

Proof. (1) For each $j$, using $q_{ij}=q_ir_{ij}$ for $i\ne j$ and $r_{jj}=0$, $$(\lambda Q)_j=\sum_{i\ne j}\lambda_iq_{ij}-\lambda_jq_j=\sum_i(\lambda_iq_i)r_{ij}-\lambda_jq_j=(\nu R)_j-\nu_j.$$ (2) If $\pi P(t)=\pi$ for all $t$, differentiate at $t=0$: $\pi Q=0$. Conversely, if $\pi Q=0$ then $\pi Q^n=0$ for $n\ge1$, so $\pi e^{tQ}=\pi$. The jump chain $R$ is finite and irreducible, so it has, up to a constant factor, exactly one invariant measure $\nu$, with all $\nu_j\gt0$ (§3.2). By (1), the solutions of $\lambda Q=0$ are exactly the multiples of $(\nu_j/q_j)$, and exactly one of them is a probability vector.

(3) (Sketch.) Fix $k$ and let $\gamma^k$ be the invariant measure of the recurrent jump chain built from excursions from $k$ (§3.2), so $\gamma^k_j$ is the expected number of visits to $j$ between two visits to $k$, and every invariant measure of $R$ is a multiple of $\gamma^k$. Each visit to $j$ lasts an $\operatorname{Exp}(q_j)$ time with mean $1/q_j$, independently of the number of visits, so the expected time spent in $j$ during an excursion from $k$ is $\gamma^k_j/q_j$, and summing over $j$, $m_k=\sum_j\gamma_j^k/q_j$. By (1), the solutions of $\lambda Q=0$ are the multiples of $\lambda_j=\gamma_j^k/q_j$, whose total mass is $m_k$. So a normalisable solution exists iff $m_k\lt\infty$, and then $\pi_k=\lambda_k/m_k=(\gamma^k_k/q_k)/m_k=1/(q_km_k)$, since $\gamma_k^k=1$.

(4) (Sketch.) Fix $h\gt0$. The skeleton $Z_n=X(nh)$ is a discrete-time chain with matrix $P(h)$. It is aperiodic because $p_{ii}(h)\ge P_i(H\gt h)=e^{-q_ih}\gt0$, and irreducible: if $i=k_0,k_1,\dots,k_m=j$ is a path with all $q_{k_{r}k_{r+1}}\gt0$, the probability of making exactly these $m$ jumps within time $h$ and then staying put is positive, so $p_{ij}(h)\gt0$ for every $h\gt0$. Also $\pi P(h)=\pi$. The convergence theorem of §3.2 gives $p_{ij}(nh)\to\pi_j$. Finally $|p_{ij}(t+s)-p_{ij}(t)|\le2(1-p_{ii}(s))$, uniformly in $t$, which fills the gaps between grid points. The time-average statement follows from the excursion argument of the ergodic theorem (§3.2). ∎

The formula $\pi_j\propto\nu_j/q_j$ is worth remembering: the CTMC spends in $j$ a fraction of time proportional to (visits to $j$) × (mean duration of a visit). Like discrete chains, a CTMC can have a detailed balance solution, $\pi_iq_{ij}=\pi_jq_{ji}$ for all $i\ne j$; summing over $i$ shows that such a $\pi$ satisfies $\pi Q=0$.

✏️ Example 5 — Prove or disprove: a CTMC and its jump chain
Let $X$ have generator $Q=\begin{pmatrix}-2&2&0\\1&-3&2\\0&4&-4\end{pmatrix}$ on $\{1,2,3\}$. Prove or disprove: (a) the stationary distribution of $X$ equals that of its jump chain; (b) since the jump chain has period $2$, $p_{11}(t)$ does not converge as $t\to\infty$; (c) starting from $3$, the expected time until the chain returns to $3$ after leaving it is $1$; (d) $X$ satisfies detailed balance.
Stationary law $\pi Q=0$: the first column gives $-2\pi_1+\pi_2=0$, the third $2\pi_2-4\pi_3=0$. So $\pi\propto(1,2,1)$ and $\pi=(\frac14,\frac12,\frac14)$.
(a) False The jump chain has rows $(0,1,0)$, $(\frac13,0,\frac23)$, $(0,1,0)$. By Theorem 3.35(1) its stationary law is proportional to $\pi_jq_j=(\frac14\cdot2,\frac12\cdot3,\frac14\cdot4)=(\frac12,\frac32,1)$, i.e. $\nu=(\frac16,\frac12,\frac13)\ne\pi$. (Check: $\nu R=(\frac16,\ \frac16+\frac13,\ \frac13)=\nu$.)
(b) False The jump chain alternates between $\{2\}$ and $\{1,3\}$, so it has period $2$, but the CTMC is irreducible and finite, so $p_{11}(t)\to\pi_1=\frac14$ by Theorem 3.35(4). Exponential holding times destroy any periodicity.
(c) True $m_3=\frac1{q_3\pi_3}=\frac1{4\cdot\frac14}=1$. Directly: the chain stays in $3$ for a mean time $\frac14$ and jumps to $2$. Let $h_i$ be the expected time to reach $3$ from $i$. Then $h_1=\frac12+h_2$ and $h_2=\frac13+\frac13h_1$, so $h_2=\frac34$, $h_1=\frac54$; the mean return time is $\frac14+h_2=1$.
(d) True $\pi_1q_{12}=\frac14\cdot2=\frac12=\frac12\cdot1=\pi_2q_{21}$ and $\pi_2q_{23}=1=\frac14\cdot4=\pi_3q_{32}$; the pair $\{1,3\}$ has rate $0$ both ways. Every birth–death CTMC is reversible, as Theorem 3.37 shows.

Birth–Death Processes

In many models the state is the size of a population (customers in a queue, infected individuals, cells, molecules) and changes only by one unit at a time. These are the continuous-time analogues of the birth–death chains of §3.2.

📘 Definition 3.15 — Birth–death process
A birth–death process is a CTMC on $S=\{0,1,2,\dots\}$ (or $\{0,1,\dots,N\}$) whose only nonzero off-diagonal rates are $$q_{n,n+1}=\lambda_n\ \ (\text{birth rates}),\qquad q_{n,n-1}=\mu_n\ \ (\text{death rates}),\qquad\mu_0=0.$$ It is a pure birth process if all $\mu_n=0$ and a pure death process if all $\lambda_n=0$. The distribution $p_n(t)=P(X(t)=n)$ obeys the forward equations $$p_n'(t)=\lambda_{n-1}p_{n-1}(t)-(\lambda_n+\mu_n)\,p_n(t)+\mu_{n+1}p_{n+1}(t)\qquad(\lambda_{-1}=0).$$
model$\lambda_n$$\mu_n$steady state
Poisson process$\lambda$$0$none (drifts to $\infty$)
Yule (pure birth, linear)$n\lambda$$0$none
linear birth–death$n\lambda$$n\mu$$0$ is absorbing
immigration–death (M/M/∞)$\lambda$$n\mu$$\operatorname{Poi}(\lambda/\mu)$
M/M/1 queue$\lambda$$\mu$ ($n\ge1$)$(1-\rho)\rho^n$ if $\rho=\lambda/\mu\lt1$
machine repair, $N$ machines$(N-n)\lambda$$\mu$ ($n\ge1$)finite, always exists
📐 Theorem 3.36 — Pure birth processes: the Yule process and explosion

Let $X$ be a pure birth process with rates $\lambda_n\gt0$ and $X(0)=i$.

  1. The forward equations $p_i'=-\lambda_ip_i$, $p_n'=\lambda_{n-1}p_{n-1}-\lambda_np_n$ ($n\gt i$) have the unique solution $p_i(t)=e^{-\lambda_it}$, $p_n(t)=\lambda_{n-1}\int_0^te^{-\lambda_n(t-s)}p_{n-1}(s)\,ds$.
  2. (Yule process) If $\lambda_n=n\lambda$ and $X(0)=1$, then $X(t)$ is geometric with success probability $e^{-\lambda t}$: $$P(X(t)=n)=e^{-\lambda t}\left(1-e^{-\lambda t}\right)^{n-1}\ (n\ge1),\qquad E[X(t)]=e^{\lambda t},\qquad\operatorname{Var}(X(t))=e^{2\lambda t}-e^{\lambda t}.$$ From $X(0)=i$, $X(t)$ is a sum of $i$ independent such variables (negative binomial): $P(X(t)=n)=\binom{n-1}{i-1}e^{-i\lambda t}(1-e^{-\lambda t})^{n-i}$.
  3. (Explosion) Let $T_\infty=\sum_{n\ge i}H_n$ be the time at which $X$ reaches $\infty$, with independent $H_n\sim\operatorname{Exp}(\lambda_n)$. If $\sum_n1/\lambda_n\lt\infty$, then $T_\infty\lt\infty$ almost surely and $\sum_np_n(t)\lt1$ for $t\gt0$; if $\sum_n1/\lambda_n=\infty$, then $T_\infty=\infty$ almost surely and $\sum_np_n(t)=1$ for all $t$.

Proof. (1) The first equation gives $p_i=e^{-\lambda_it}$; each later equation is linear of first order with zero initial value, solved by variation of constants: $\frac{d}{dt}\left(e^{\lambda_nt}p_n\right)=\lambda_{n-1}e^{\lambda_nt}p_{n-1}$.

(2) Starting from $1$, the process reaches $n$ at time $H_1+\cdots+H_{n-1}$ with independent $H_k\sim\operatorname{Exp}(k\lambda)$. Compare with $n-1$ iid $\operatorname{Exp}(\lambda)$ lifetimes, started together: the first death comes after the minimum of $n-1$ exponentials, an $\operatorname{Exp}((n-1)\lambda)$ time; by the memoryless property the $n-2$ survivors then start afresh, and the next death comes after an independent $\operatorname{Exp}((n-2)\lambda)$ time; and so on (the Rényi representation). So $H_1+\cdots+H_{n-1}$ has the law of the maximum of $n-1$ iid $\operatorname{Exp}(\lambda)$ variables, and $$P(X(t)\ge n)=P(H_1+\cdots+H_{n-1}\le t)=\left(1-e^{-\lambda t}\right)^{n-1}.$$ Subtracting, $P(X(t)=n)=(1-u)^{n-1}-(1-u)^n$ $=u(1-u)^{n-1}$ with $u=e^{-\lambda t}$. The mean and variance of this geometric law are $\frac1u=e^{\lambda t}$ and $\frac{1-u}{u^2}=e^{2\lambda t}-e^{\lambda t}$. From $X(0)=i$, each of the $i$ initial individuals founds its own independent Yule family (the total birth rate $n\lambda$ is the sum of the individual rates $\lambda$), and a sum of $i$ iid geometric variables is negative binomial.

(3) $E[T_\infty]=\sum_n1/\lambda_n$, so if this is finite then $T_\infty\lt\infty$ almost surely. Moreover $\sum_np_n(t)=P(T_\infty\gt t)$, and this is $\lt1$ for every $t\gt0$: choose $m$ with $\sum_{n\ge m}1/\lambda_n\lt t/4$; by Markov's inequality the tail $\sum_{n\ge m}H_n$ is at most $t/2$ with probability at least $\frac12$, the finitely many $H_i,\dots,H_{m-1}$ add up to at most $t/2$ with positive probability, and the two events are independent. If $\sum1/\lambda_n=\infty$, then by independence and monotone convergence $$E\left[e^{-T_\infty}\right]=\prod_{n\ge i}\frac{\lambda_n}{\lambda_n+1}=\prod_{n\ge i}\left(1+\frac1{\lambda_n}\right)^{-1}=0,$$ because $\sum_n\log(1+1/\lambda_n)=\infty$ (if $1/\lambda_n\not\to0$ the terms do not tend to $0$; otherwise $\log(1+x)\ge x/2$ for small $x\gt0$). Hence $e^{-T_\infty}=0$, that is $T_\infty=\infty$, almost surely. ∎

✏️ Example 6 — A growing culture of bacteria
Each bacterium in a culture splits into two at rate $\lambda=0.5$ per hour, independently of the others, and none die. The culture starts with one cell. Find (a) the probability that there is still a single cell after $4$ hours and the probability that there are at least $10$; (b) the mean and standard deviation of the population at $4$ hours; (c) the expected time until the population first reaches $10$; (d) the limiting law of $X(t)e^{-\lambda t}$. (e) Could a pure birth process with rates $\lambda_n=\lambda n^2$ be used instead?
Model With $n$ cells, the time to the next split is the minimum of $n$ independent $\operatorname{Exp}(\lambda)$ times, which is $\operatorname{Exp}(n\lambda)$: a Yule process. At $t=4$, $u=e^{-\lambda t}=e^{-2}\approx0.1353$.
(a) $P(X(4)=1)=e^{-2}\approx0.135$ (the first cell has not yet split). $P(X(4)\ge10)=(1-e^{-2})^9\approx0.270$.
(b) $E[X(4)]=e^2\approx7.39$ and $\operatorname{SD}=\sqrt{e^4-e^2}\approx6.87$. The standard deviation is almost as large as the mean: the early splits, which happen at random times, have a lasting effect.
(c) The population passes through $1,2,\dots,9$ and spends a mean time $\frac1{k\lambda}$ in state $k$: $E[T_{10}]=\sum_{k=1}^9\frac{1}{0.5k}=2H_9\approx5.66$ hours, where $H_9=1+\frac12+\cdots+\frac19$.
(d) For $x\gt0$, $P(X(t)e^{-\lambda t}\gt x)=(1-u)^{\lfloor xe^{\lambda t}\rfloor}$ with $u=e^{-\lambda t}$, and $(1-u)^{x/u}\to e^{-x}$ as $u\to0$. So $X(t)e^{-\lambda t}\Rightarrow\operatorname{Exp}(1)$: the population grows like $We^{\lambda t}$ with a random factor $W$ fixed by the early history.
(e) No $\sum_n\frac{1}{\lambda n^2}=\frac{\pi^2}{6\lambda}\lt\infty$, so by Theorem 3.36(3) the population would explode, reaching infinite size at a finite random time with mean $\frac{\pi^2}{6\lambda}$ hours. A model with superlinear birth rates is not a sensible model of a population.
📐 Theorem 3.37 — Steady state of a birth–death process

Let $X$ be a birth–death process on $\{0,1,2,\dots\}$ with $\lambda_n\gt0$ ($n\ge0$) and $\mu_n\gt0$ ($n\ge1$), and put

$$\theta_0=1,\qquad\theta_n=\frac{\lambda_0\lambda_1\cdots\lambda_{n-1}}{\mu_1\mu_2\cdots\mu_n}\quad(n\ge1).$$
  1. Every solution of $\pi Q=0$ satisfies the cut equations $\lambda_n\pi_n=\mu_{n+1}\pi_{n+1}$ (detailed balance), so $\pi_n=\pi_0\theta_n$. A probability solution exists iff $\sum_n\theta_n\lt\infty$, and then $\pi_n=\theta_n\big/\sum_k\theta_k$.
  2. $X$ is recurrent iff $\displaystyle\sum_{n\ge0}\frac1{\lambda_n\theta_n}=\infty$, and positive recurrent iff, in addition, $\sum_n\theta_n\lt\infty$. If the birth rates are bounded, $\sum_n\theta_n\lt\infty$ alone implies positive recurrence.
  3. When $X$ is positive recurrent, $p_n(t)\to\pi_n$ from every initial state, and $\pi_n$ is the long-run fraction of time spent in $n$.

On a finite state space $\{0,\dots,N\}$ (with $\lambda_N=0$) the same formula, with $n\le N$, always gives the unique stationary distribution.

Proof. (1) The $0$-th equation of $\pi Q=0$ is $-\lambda_0\pi_0+\mu_1\pi_1=0$. If $\lambda_{n-1}\pi_{n-1}=\mu_n\pi_n$, the $n$-th equation $\lambda_{n-1}\pi_{n-1}-(\lambda_n+\mu_n)\pi_n+\mu_{n+1}\pi_{n+1}=0$ reduces to $\mu_{n+1}\pi_{n+1}=\lambda_n\pi_n$. By induction all cut equations hold, so $\pi_{n+1}=\pi_n\lambda_n/\mu_{n+1}$ and $\pi_n=\pi_0\theta_n$. This can be normalised iff $\sum\theta_n\lt\infty$.

(2) The jump chain is a birth–death chain with up-probabilities $p_n=\frac{\lambda_n}{\lambda_n+\mu_n}$ and down-probabilities $q_n=\frac{\mu_n}{\lambda_n+\mu_n}$ ($p_0=1$). By the recurrence criterion for birth–death chains (§3.2) it is recurrent iff $\sum_n\rho_n=\infty$, where $$\rho_n=\prod_{k=1}^n\frac{q_k}{p_k}=\frac{\mu_1\cdots\mu_n}{\lambda_1\cdots\lambda_n}=\frac{\lambda_0}{\lambda_n\theta_n}.$$ Recurrence of $X$ means recurrence of its jump chain. Given recurrence, Theorem 3.35(3) and part (1) say that positive recurrence is equivalent to $\sum\theta_n\lt\infty$. If $\lambda_n\le\Lambda$ for all $n$ and $\sum\theta_n\lt\infty$, then $\theta_n\to0$, so $\frac{1}{\lambda_n\theta_n}\ge\frac1{\Lambda\theta_n}\to\infty$ and the series in (2) diverges.

(3) This is Theorem 3.35(4). The finite case is Theorem 3.35(2) together with the cut equations. ∎

The cut equations have a direct meaning: in equilibrium, the long-run rate of crossings from $n$ up to $n+1$, which is $\lambda_n\pi_n$, must equal the rate of crossings from $n+1$ down to $n$, which is $\mu_{n+1}\pi_{n+1}$, because up- and down-crossings of a cut alternate. The extra condition in (2) is not a technicality: for $\lambda_n=4^n$, $\mu_n=2\cdot4^{n-1}$ we get $\theta_n=2^{-n}$, a summable sequence, but $\frac1{\lambda_n\theta_n}=2^{-n}$ is summable too. That process is transient and explodes, and the "stationary distribution" $\pi_n=2^{-(n+1)}$ describes nothing.

✏️ Example 7 — Three steady states
(a) Cars arrive at a large car park as a Poisson process of rate $30$ per hour, and each stays for an $\operatorname{Exp}$ time with mean $2$ hours. Find the steady-state distribution of the number of parked cars and the probability that more than $70$ are parked. (b) Three machines each break down at rate $0.2$ per day while working, and a single mechanic repairs broken machines one at a time at rate $1$ per day. Find the steady-state distribution of the number of broken machines, the mean number broken, and the fraction of time the mechanic is busy; check the answer by a flow argument. (c) Find the steady state of the M/M/1 queue ($\lambda_n=\lambda$, $\mu_n=\mu$ for $n\ge1$).
(a) M/M/∞ With $n$ cars parked, each leaves at rate $\frac12$, so $\mu_n=\frac n2$, and $\lambda_n=30$. Then $\theta_n=\frac{30^n}{(n/2)\cdots(1/2)}=\frac{60^n}{n!}$ and $\pi_n=e^{-60}\frac{60^n}{n!}$: the steady state is $\operatorname{Poi}(60)$, as Example 3 predicts with mean $\lambda\,E[\text{stay}]=60$. So $P(\text{more than }70)=P(\operatorname{Poi}(60)\ge71)\approx0.090$.
(b) Machine repair State $n$ = number broken, $n\in\{0,1,2,3\}$: $\lambda_n=(3-n)\cdot0.2$, $\mu_n=1$. So $\theta=(1,\ 0.6,\ 0.6\cdot0.4,\ 0.24\cdot0.2)=(1,\frac35,\frac6{25},\frac6{125})$, with sum $\frac{236}{125}$, and $$\pi=\tfrac{1}{236}(125,\ 75,\ 30,\ 6)\approx(0.530,\ 0.318,\ 0.127,\ 0.025).$$ The mean number broken is $\frac{75+60+18}{236}=\frac{153}{236}\approx0.648$, and the mechanic is busy a fraction $1-\pi_0=\frac{111}{236}\approx0.470$ of the time.
Check In equilibrium breakdowns and repairs happen at the same long-run rate. Breakdowns: $0.2\times E[\text{working}]=0.2\left(3-\frac{153}{236}\right)=\frac{111}{236}$ per day; repairs: $1\times P(\text{mechanic busy})=\frac{111}{236}$ per day. They agree.
(c) M/M/1 $\theta_n=\rho^n$ with $\rho=\lambda/\mu$. If $\rho\lt1$, $\pi_n=(1-\rho)\rho^n$ (birth rates are bounded, so this is a true steady state), the mean number in the system is $\frac{\rho}{1-\rho}$, and the server is idle a fraction $1-\rho$ of the time. If $\rho\ge1$ there is no steady state: the queue is null recurrent for $\rho=1$ ($\sum1/(\lambda\theta_n)=\infty$, $\sum\theta_n=\infty$) and transient for $\rho\gt1$. Chapter 9 builds queueing theory on this computation.
Interactive 2 — Birth–Death Processes: One Path and the Kolmogorov Flow to Equilibrium

Choose a model and its birth rate $\lambda$. The left panel draws one simulated path $X(t)$ (exponential holding times, seeded). The right panel shows the exact distribution $p_n(t)=P(X(t)=n)$ (blue bars), obtained by solving the Kolmogorov forward equations numerically, against the steady state $\pi_n$ of Theorem 3.37 (purple). Watch the bars flow into the purple marks, slowly when $\rho=\lambda/\mu$ is close to $1$ in the M/M/1 queue. For the Yule process there is no steady state: the distribution stays geometric and slides to the right while $E[X(t)]=e^{\lambda t}$.

—
time t—
E[X(t)] from the forward equations—
benchmark—
d_TV(p(t), π)—
⚠️ Counterexamples and pitfalls
  1. Poisson marginals do not make a Poisson process. Let $U\sim U(0,1)$, let $G_t$ be the cdf of $\operatorname{Poi}(\lambda t)$ and put $N(t)=\min\{k:G_t(k)\gt U\}$. This is a counting process with $N(t)\sim\operatorname{Poi}(\lambda t)$ for every $t$, but its increments are not independent: for $\lambda=1$, $P(N(1)=1,N(2)=1)=3e^{-2}-e^{-1}\approx0.038$, while a Poisson process gives $e^{-2}\approx0.135$. Independence of increments is part of the definition.
  2. Not every transformation of a Poisson process is Poisson. $2N(t)$ jumps by $2$ and has variance $4\lambda t\ne2\lambda t$; $N(t^2)$ has Poisson increments but they are not stationary (a non-homogeneous Poisson process). $N(ct)$ is a $\mathrm{PP}(c\lambda)$.
  3. Overlapping counts are dependent. $\operatorname{Cov}(N(s),N(t))=\lambda\min(s,t)$; always rewrite $\{N(1)=3,N(2)=5\}$ as $\{N(1)=3,N(2)-N(1)=2\}$ before multiplying probabilities.
  4. The inspection paradox. The gap containing a fixed time has mean $(2-e^{-\lambda t})/\lambda$, not $1/\lambda$; the wait from a fixed time to the next event is $\operatorname{Exp}(\lambda)$ with mean $1/\lambda$, not half a gap.
  5. Given $N(t)=n$, the arrival times are not iid uniform in their given order. They are the order statistics of $n$ iid uniforms: $S_1\mid N(t)=n$ has density $\frac{n}{t}(1-\frac st)^{n-1}$, not $\frac1t$. Only for $n=1$ is $S_1$ uniform.
  6. Independence after thinning needs a Poisson total and independent marks. Given $N(t)=n$, the two type counts are $\operatorname{Bin}(n,p)$ and $n$ minus it: perfectly negatively correlated. Thinning by a rule that looks at the process (keep every second event) does not give a Poisson process: the gaps become $\operatorname{Gamma}(2,\lambda)$.
  7. A generator is not a stochastic matrix. Its rows sum to $0$ and its diagonal is negative; $P(t)=e^{tQ}$, not $Q^t$ or $I+tQ$. And $e^{t(A+B)}\ne e^{tA}e^{tB}$ unless $A$ and $B$ commute.
  8. The CTMC and its jump chain have different stationary laws. $\pi_j\propto\nu_j/q_j$; they agree only when all $q_j$ are equal. In Example 4 the jump chain gives $(\frac12,\frac12)$, the CTMC $(\frac56,\frac16)$.
  9. There is no periodicity in continuous time. $p_{ii}(t)\ge e^{-q_it}\gt0$, and for $i\ne j$ either $p_{ij}(t)\gt0$ for every $t\gt0$ or for none. A periodic jump chain (Examples 4, 5) does not stop $P(t)$ from converging.
  10. Explosion. A pure birth process with $\sum1/\lambda_n\lt\infty$ (e.g. $\lambda_n=n^2$ or $2^n$) reaches $\infty$ in finite time, and then $\sum_np_n(t)\lt1$: the forward equations have a "dishonest" solution. Large death rates ($\mu_n=n\mu$ in M/M/∞) never cause explosion.
  11. $\pi Q=0$ with $\sum\pi_n=1$ does not by itself give positive recurrence on an infinite state space. The birth–death process with $\lambda_n=4^n$, $\mu_n=2\cdot4^{n-1}$ has the probability solution $\pi_n=2^{-(n+1)}$ but is transient and explosive (Theorem 3.37(2)).

Exercises

I
The Poisson process.
  • 1 Customers arrive as a Poisson process of rate $3$ per minute. Find $P(N(2)=4)$, $P(N(2)=4,\ N(5)=10)$ and $P(N(2)=4\mid N(5)=10)$.
  • 2 For $N\sim\mathrm{PP}(\lambda)$ and $s\le t$, show that $E[N(s)N(t)]=\lambda s+\lambda^2st$, and evaluate it and $\operatorname{Corr}(N(2),N(5))$ for $\lambda=3$.
  • 3 Find $E[S_4]$, $\operatorname{Var}(S_4)$ and $P(S_4\gt t)$ (as a finite sum) for a $\mathrm{PP}(\lambda)$.
  • 4 Using only Definition (A), show that $P(S_1\le s\mid N(t)=1)=\frac st$ for $0\le s\le t$.
  • 5 Given $N(t)=n$, find $E[S_1+\cdots+S_n]$ and $E[S_n]$.
  • 6 Prove that for $0\lt s\lt t$, given $N(t)=n$, $N(s)\sim\operatorname{Bin}(n,s/t)$; deduce that $E[N(s)\mid N(t)]=\frac stN(t)$.
  • 7 Let $N\sim\mathrm{PP}(\lambda)$. Prove or disprove: (a) for $c\gt0$, $M(t)=N(ct)$ is a Poisson process of rate $c\lambda$; (b) $K(t)=N(t^2)$ is a Poisson process.
  • 8 (Modelling) On a clear night meteors are seen at rate $12$ per hour. An observer watches for $20$ minutes. Find the probability that she sees at least $3$; the expected time from the start until she has seen $3$; and, given that she saw exactly $3$ in the $20$ minutes, the probability that all three came in the first $10$ minutes.
1 $N(2)\sim\operatorname{Poi}(6)$: $P(N(2)=4)=e^{-6}\frac{6^4}{24}=54e^{-6}\approx0.1339$. With the independent increment $N(5)-N(2)\sim\operatorname{Poi}(9)$: $P(N(2)=4,N(5)=10)=54e^{-6}\cdot e^{-9}\frac{9^6}{6!}\approx0.01219$. Given $N(5)=10$, $N(2)\sim\operatorname{Bin}(10,\frac25)$, so the conditional probability is $\binom{10}{4}(0.4)^4(0.6)^6\approx0.2508$.
2 $E[N(s)N(t)]=E[N(s)^2]+E[N(s)]\,E[N(t)-N(s)]=(\lambda s+\lambda^2s^2)+\lambda s\cdot\lambda(t-s)=\lambda s+\lambda^2st$. For $\lambda=3$, $s=2$, $t=5$: $6+90=96$. $\operatorname{Corr}=\frac{\lambda s}{\sqrt{\lambda s\cdot\lambda t}}=\sqrt{s/t}=\sqrt{0.4}\approx0.632$.
3 $S_4\sim\operatorname{Gamma}(4,\lambda)$: $E=\frac4\lambda$, $\operatorname{Var}=\frac4{\lambda^2}$, and $P(S_4\gt t)=P(N(t)\le3)=e^{-\lambda t}\left(1+\lambda t+\frac{(\lambda t)^2}2+\frac{(\lambda t)^3}6\right)$.
4 $\{S_1\le s,\ N(t)=1\}=\{N(s)=1,\ N(t)-N(s)=0\}$. So the conditional probability is $\frac{\lambda se^{-\lambda s}\cdot e^{-\lambda(t-s)}}{\lambda te^{-\lambda t}}=\frac st$.
5 By Theorem 3.28(3), $S_1+\cdots+S_n$ has the law of $U_1+\cdots+U_n$ with iid $U(0,t)$ (sorting does not change a sum), so its mean is $\frac{nt}2$. $S_n$ has the law of $\max U_i$, with $P(\max\le x)=(x/t)^n$, so $E[S_n\mid N(t)=n]=\frac{n}{n+1}t$.
6 For $0\le k\le n$: $\frac{P(N(s)=k)\,P(N(t)-N(s)=n-k)}{P(N(t)=n)}=\frac{e^{-\lambda s}\frac{(\lambda s)^k}{k!}e^{-\lambda(t-s)}\frac{(\lambda(t-s))^{n-k}}{(n-k)!}}{e^{-\lambda t}\frac{(\lambda t)^n}{n!}}=\binom nk\left(\frac st\right)^k\left(1-\frac st\right)^{n-k}$. The binomial mean gives $E[N(s)\mid N(t)=n]=\frac{s}{t}n$.
7 (a) True: $M(0)=0$; increments of $M$ over disjoint intervals are increments of $N$ over disjoint intervals, hence independent; and $M(t+u)-M(u)=N(ct+cu)-N(cu)\sim\operatorname{Poi}(c\lambda t)$. (b) False: $K(2)-K(1)=N(4)-N(1)\sim\operatorname{Poi}(3\lambda)$, while $K(1)-K(0)\sim\operatorname{Poi}(\lambda)$, so increments of equal length have different laws. $K$ is a non-homogeneous Poisson process with intensity $2\lambda t$.
8 $N(\frac13)\sim\operatorname{Poi}(4)$: $P(\ge3)=1-e^{-4}(1+4+8)=1-13e^{-4}\approx0.762$. The third meteor comes at $S_3\sim\operatorname{Gamma}(3,12)$, mean $\frac3{12}$ h $=15$ minutes. Given $3$ meteors in $20$ minutes, each time is uniform, independently, so all three fall in the first half with probability $(\frac12)^3=\frac18$.
II
Superposition, thinning and compound Poisson processes.
  • 1 Cars and trucks pass a checkpoint as independent Poisson processes with rates $8$ and $2$ per minute. Find the probability that the first vehicle after noon is a truck, the probability that the next $3$ vehicles are all cars, and the distribution and mean of the number of cars passing before the first truck.
  • 2 Emails arrive at $30$ per hour, each independently spam with probability $0.4$. Find the probability of exactly $3$ genuine emails and exactly $2$ spam emails in a given $10$-minute period.
  • 3 In II.2, given that $5$ emails arrived in the period, find the probability that exactly $2$ are spam.
  • 4 $N_1\sim\mathrm{PP}(\lambda_1)$ and $N_2\sim\mathrm{PP}(\lambda_2)$ are independent. Find the probability that $N_1$ has $n$ events before $N_2$ has its first.
  • 5 Show directly that a geometric sum $\sum_{k=1}^KE_k$ of iid $\operatorname{Exp}(\lambda)$ variables, with $K\sim\operatorname{Geom}(p)$ on $\{1,2,\dots\}$ independent of the $E_k$, is $\operatorname{Exp}(\lambda p)$. Explain how this proves that the gaps of a thinned Poisson process are exponential.
  • 6 A detector records an event of a $\mathrm{PP}(\lambda)$ that occurs at time $s$ with probability $e^{-\alpha s}$ (it degrades), independently. Find the law of the number recorded in $[0,t]$ and of the total number ever recorded.
  • 7 (Modelling) Insurance claims arrive at $4$ per week; claim sizes are iid with mean $5$ and standard deviation $2$ (thousand rupees). Find the mean and standard deviation of the total claimed in $13$ weeks, and approximate the probability that it exceeds $300$ thousand rupees.
  • 8 Groups arrive as a $\mathrm{PP}(\lambda)$; each group is a single person or a couple with probability $\frac12$ each. Let $X(t)$ be the number of people arrived by time $t$. Find $E[X(t)]$, $\operatorname{Var}(X(t))$ and $P(X(t)=2)$.
1 The superposition is a $\mathrm{PP}(10)$ in which each vehicle is a truck with probability $\frac2{10}=0.2$, independently (Theorem 3.31(1)). First vehicle a truck: $0.2$. Next three all cars: $0.8^3=0.512$. The number $K$ of cars before the first truck is geometric: $P(K=k)=0.8^k\cdot0.2$, $k\ge0$, with mean $\frac{0.8}{0.2}=4$.
2 Thinning gives independent Poisson streams of rates $18$ (genuine) and $12$ (spam) per hour, i.e. means $3$ and $2$ in $10$ minutes. Probability: $e^{-3}\frac{3^3}{3!}\cdot e^{-2}\frac{2^2}{2!}=9e^{-5}\approx0.0606$.
3 Given the total, the number of spam emails is $\operatorname{Bin}(5,0.4)$: $\binom52(0.4)^2(0.6)^3=0.3456$.
4 In the superposition each event belongs to $N_1$ with probability $\frac{\lambda_1}{\lambda_1+\lambda_2}$ independently; the required event is that the first $n$ events all belong to $N_1$: probability $\left(\frac{\lambda_1}{\lambda_1+\lambda_2}\right)^n$.
5 For $u\lt\lambda p$: $E\left[e^{u\sum_{k\le K}E_k}\right]=\sum_{k\ge1}(1-p)^{k-1}p\left(\frac{\lambda}{\lambda-u}\right)^k=\frac{p\lambda/(\lambda-u)}{1-(1-p)\lambda/(\lambda-u)}=\frac{p\lambda}{p\lambda-u}$, the $\operatorname{Exp}(\lambda p)$ mgf. In a thinned process, the gap between kept events is a sum of a $\operatorname{Geom}(p)$ number of the original iid $\operatorname{Exp}(\lambda)$ gaps, and successive gaps use disjoint blocks of original gaps and marks, so they are iid $\operatorname{Exp}(\lambda p)$: Definition (C).
6 Theorem 3.31(3) with $p(s)=e^{-\alpha s}$: the number recorded in $[0,t]$ is $\operatorname{Poi}\left(\frac\lambda\alpha(1-e^{-\alpha t})\right)$. As $t\to\infty$ the counts increase to the total ever recorded, which is $\operatorname{Poi}(\lambda/\alpha)$; in particular it is finite with probability one.
7 $\lambda t=52$, $E[Y]=5$, $E[Y^2]=2^2+5^2=29$. Mean $52\times5=260$, variance $52\times29=1508$, SD $\approx38.83$ (thousand rupees). Normal approximation: $P(X\gt300)\approx1-\Phi\left(\frac{40}{38.83}\right)=1-\Phi(1.030)\approx0.151$. (A simulation with gamma claim sizes gives about $0.152$.)
8 $E[Y]=\frac32$ and $E[Y^2]=\frac52$, so $E[X(t)]=\frac32\lambda t$ and $\operatorname{Var}(X(t))=\frac52\lambda t$ (Theorem 3.32). By Theorem 3.32(4), $X=N_1+2N_2$ with independent $N_1,N_2\sim\operatorname{Poi}(\lambda t/2)$, so $P(X(t)=2)=P(N_1=2,N_2=0)+P(N_1=0,N_2=1)=e^{-\lambda t}\left(\frac{\lambda^2t^2}{8}+\frac{\lambda t}{2}\right)$.
III
Continuous-time Markov chains and the Kolmogorov equations.
  • 1 A CTMC on $\{1,2,3\}$ has rates $q_{12}=1$, $q_{13}=2$, $q_{21}=3$, $q_{23}=0$, $q_{31}=1$, $q_{32}=1$. Write down $Q$, the holding rates and the jump matrix $R$, and find the stationary distributions of the CTMC and of the jump chain.
  • 2 For the two-state generator of Example 4, show that $Q^2=-(\alpha+\beta)Q$ and deduce $e^{tQ}=I+\frac{1-e^{-(\alpha+\beta)t}}{\alpha+\beta}Q$.
  • 3 Prove that for every finite generator $Q$ the matrix $e^{tQ}$ ($t\ge0$) is stochastic. (Hint: $Q+cI\ge0$ entrywise for large $c$.)
  • 4 (Uniformisation) Let $c\ge\max_iq_i$ and $K=I+Q/c$. Show that $K$ is stochastic and $P(t)=\sum_{n\ge0}e^{-ct}\frac{(ct)^n}{n!}K^n$. Interpret this formula with a Poisson clock.
  • 5 A CTMC on $\{0,1,2\}$ moves $0\to1\to2\to0$, each jump at rate $2$. Find its stationary distribution, the eigenvalues of $Q$, and show that $p_{00}(t)=\frac13+\frac23e^{-3t}\cos(\sqrt3\,t)$.
  • 6 Show that $p_{ii}(t)\ge e^{-q_it}$ for every $t$, and deduce that no $2\times2$ generator has $e^{Q}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$.
  • 7 Prove or disprove: if all holding rates $q_i$ of an irreducible finite CTMC are equal, then the CTMC and its jump chain have the same stationary distribution.
  • 8 (Modelling) A component is in state $0$ (good), $1$ (worn) or $2$ (failed, absorbing), with rates $q_{01}=2$, $q_{10}=1$ (self-repair) and $q_{12}=1$ per year. Find the expected time to failure from each of the states $0$ and $1$.
1 $Q=\begin{pmatrix}-3&1&2\\3&-3&0\\1&1&-2\end{pmatrix}$, $(q_1,q_2,q_3)=(3,3,2)$, $R$ has rows $(0,\frac13,\frac23)$, $(1,0,0)$, $(\frac12,\frac12,0)$. Solving $\pi Q=0$, $\sum\pi_i=1$ gives $\pi=(\frac38,\frac14,\frac38)$ (check the second column: $\frac38-\frac34+\frac38=0$). The jump chain has $\nu\propto\pi_jq_j=(\frac98,\frac34,\frac34)$, so $\nu=(\frac37,\frac27,\frac27)$.
2 Direct multiplication: $Q^2=\begin{pmatrix}\alpha^2+\alpha\beta&-\alpha^2-\alpha\beta\\-\beta^2-\alpha\beta&\beta^2+\alpha\beta\end{pmatrix}=-(\alpha+\beta)Q$. With $s=\alpha+\beta$, $Q^n=(-s)^{n-1}Q$ for $n\ge1$, so $e^{tQ}=I+Q\sum_{n\ge1}\frac{t^n(-s)^{n-1}}{n!}=I+\frac{1-e^{-st}}{s}Q$. Its $(0,0)$ entry is $1-\frac{\alpha}{s}(1-e^{-st})$, as in Example 4.
3 Take $c=\max_iq_i$. Then $Q+cI\ge0$, so every power, and hence $e^{t(Q+cI)}$, has nonnegative entries. Since $cI$ commutes with $Q$, $e^{tQ}=e^{-ct}e^{t(Q+cI)}\ge0$. Rows: $Q\mathbf 1=0$ gives $Q^n\mathbf 1=0$ for $n\ge1$, so $e^{tQ}\mathbf 1=\mathbf 1$.
4 $K$ has off-diagonal entries $q_{ij}/c\ge0$, diagonal $1-q_i/c\ge0$ and row sums $1$. Since $Q=c(K-I)$ and $I$ commutes with $K$, $e^{tQ}=e^{-ct}e^{ctK}=\sum_ne^{-ct}\frac{(ct)^n}{n!}K^n$. Interpretation: a Poisson clock of rate $c$ rings, and at each ring the chain moves according to $K$ (possibly staying put); so $X(t)=Y_{M(t)}$ with $Y$ a discrete chain with matrix $K$ and $M\sim\mathrm{PP}(c)$ independent. This is also a stable way to compute $e^{tQ}$ numerically.
5 $Q=2(C-I)$ with $C$ the cyclic permutation matrix. Columns of $Q$ sum to $0$, so $\pi=(\frac13,\frac13,\frac13)$. The eigenvalues of $C$ are $1,\omega,\omega^2$ ($\omega=e^{2\pi i/3}$), so those of $Q$ are $0$ and $2(\omega-1)=-3\pm i\sqrt3$. Now $e^{tQ}=e^{-2t}e^{2tC}$ and $(C^k)_{00}=1$ iff $3\mid k$, so $p_{00}(t)=e^{-2t}\sum_{3\mid k}\frac{(2t)^k}{k!}=e^{-2t}\cdot\frac13\left(e^{2t}+e^{2t\omega}+e^{2t\omega^2}\right)=\frac13+\frac23e^{-3t}\cos(\sqrt3\,t)$. The convergence oscillates, but it happens, although the jump chain is a deterministic rotation of period $3$.
6 $p_{ii}(t)\ge P_i(H\gt t)=e^{-q_it}$ (Theorem 3.33). So the diagonal of $e^{Q}$ is at least $e^{-q_i}\gt0$, and the flip matrix, with zero diagonal, is not of the form $e^{Q}$. (Consequently the discrete flip chain cannot be "embedded" in any CTMC.)
7 True. If $q_i=q$ for all $i$, Theorem 3.35(1) says that $\pi Q=0$ iff $\nu=q\pi$ satisfies $\nu R=\nu$, so the normalised versions coincide. (Then $Q=q(R-I)$, and $X$ is the jump chain run by a Poisson clock of rate $q$.)
8 Let $h_i$ be the expected time to absorption. First-step analysis: $h_0=\frac12+h_1$ (hold for mean $\frac12$, then go to $1$) and $h_1=\frac12+\frac12h_0$ (total rate $2$; to $0$ or $2$ with probability $\frac12$ each). Solving, $h_0=2$ and $h_1=\frac32$ years. In matrix form, $h=(-Q_T)^{-1}\mathbf 1$ with $Q_T=\begin{pmatrix}-2&2\\1&-2\end{pmatrix}$ the generator restricted to the transient states.
IV
Birth–death processes and steady states.
  • 1 In an M/M/1 queue with $\lambda=4$ and $\mu=5$ per hour, find $\pi_n$, the probability of at least $3$ customers in the system and the mean number in the system.
  • 2 (Erlang loss) A small exchange has $3$ lines. Calls arrive at $2$ per minute and last an $\operatorname{Exp}$ time with mean $1$ minute; calls arriving when all lines are busy are lost. Find the steady-state probability that all lines are busy.
  • 3 For the linear birth–death process ($\lambda_n=n\lambda$, $\mu_n=n\mu$) with $X(0)=i$, use the forward equations to show that $m(t)=E[X(t)]$ satisfies $m'=(\lambda-\mu)m$, so $m(t)=ie^{(\lambda-\mu)t}$.
  • 4 For the same process, use the jump chain to show that the probability of eventual extinction from $X(0)=i$ is $(\mu/\lambda)^i$ if $\lambda\gt\mu$ and $1$ if $\lambda\le\mu$.
  • 5 A population has birth rates $\lambda_n=n+2$ (individual births at rate $1$ plus immigration at rate $2$) and death rates $\mu_n=2n$. Find the steady state and its mean.
  • 6 A pure birth process has $\lambda_n=(n+1)^2$ and $X(0)=0$. Show that it explodes and find the expected explosion time.
  • 7 For the M/M/∞ process ($\lambda_n=\lambda$, $\mu_n=n\mu$) with $X(0)=0$, show that $X(t)\sim\operatorname{Poi}\left(\frac\lambda\mu(1-e^{-\mu t})\right)$.
  • 8 Prove or disprove: a birth–death process on $\{0,1,2,\dots\}$ with $\lambda_n=\mu_{n+1}\gt0$ for all $n$ has a stationary distribution.
Check lab: steady state of a finite birth–death process

Enter the birth rates $\lambda_0,\dots,\lambda_{N-1}$ and the death rates $\mu_1,\dots,\mu_N$, separated by commas. The lab computes $\theta_n$, the steady state $\pi_n=\theta_n/\sum_k\theta_k$ (Theorem 3.37), its mean, and the long-run rate of births $\sum_n\lambda_n\pi_n$, which must equal the rate of deaths. It starts with the exchange of Exercise IV.2; try Example 7(b) with births $0.6, 0.4, 0.2$ and deaths $1, 1, 1$.

π—
mean of π—
π at the top state—
birth rate = death rate—
1 $\rho=0.8$: $\pi_n=0.2\cdot0.8^n$; $P(X\ge3)=\sum_{n\ge3}\pi_n=0.8^3=0.512$; mean $\frac{\rho}{1-\rho}=4$ customers.
2 $\lambda_n=2$ ($n=0,1,2$), $\mu_n=n$: $\theta=(1,2,2,\frac43)$, sum $\frac{19}3$, so $\pi_3=\frac{4/3}{19/3}=\frac4{19}\approx0.211$. This is the Erlang loss formula $\pi_c=\frac{a^c/c!}{\sum_{k\le c}a^k/k!}$ with $a=2$, $c=3$; by the PASTA property of §9.3 it is also the fraction of calls lost.
3 $m'=\sum_nnp_n'=\sum_nn\left[\lambda(n-1)p_{n-1}-(\lambda+\mu)np_n+\mu(n+1)p_{n+1}\right]$. Shifting indices, $\sum_nn(n-1)p_{n-1}=\sum_k(k+1)kp_k=E[X^2]+E[X]$ and $\sum_nn(n+1)p_{n+1}=\sum_k(k-1)kp_k=E[X^2]-E[X]$. So $m'=\lambda(E X^2+m)-(\lambda+\mu)EX^2+\mu(EX^2-m)=(\lambda-\mu)m$, and $m(0)=i$. (Exchanging $\frac d{dt}$ and $\sum$ is justified because the process is non-explosive with finite second moments; we accept this.)
4 From $n\ge1$ the jump chain goes up with probability $\frac{\lambda}{\lambda+\mu}$ and down with $\frac{\mu}{\lambda+\mu}$, independently of $n$, and $0$ is absorbing. This is the gambler's ruin against an infinitely rich casino (§3.1): the probability of ever hitting $0$ from $i$ is $\left(\frac{\mu}{\lambda}\right)^i$ if $\lambda\gt\mu$ and $1$ otherwise. Note that for $\lambda=\mu$ extinction is certain although $E[X(t)]=i$ for all $t$.
5 $\theta_n=\prod_{k=0}^{n-1}\frac{k+2}{2(k+1)}=\frac{n+1}{2^n}$; $\sum\theta_n=\sum_n(n+1)2^{-n}=4$, so $\pi_n=\frac{n+1}{2^{n+2}}$, a negative binomial law (number of failures before the second success, success probability $\frac12$), with mean $2$. The birth rates are unbounded, but $\frac1{\lambda_n\theta_n}=\frac{2^n}{(n+2)(n+1)}\to\infty$, so the series of Theorem 3.37(2) diverges and the steady state is genuine.
6 $\sum_n\frac1{(n+1)^2}=\frac{\pi^2}6\lt\infty$, so it explodes (Theorem 3.36(3)), and $E[T_\infty]=\sum_{n\ge0}\frac{1}{(n+1)^2}=\frac{\pi^2}{6}\approx1.645$.
7 This is Example 3 with $\operatorname{Exp}(\mu)$ stays: $X(t)\sim\operatorname{Poi}\left(\lambda\int_0^te^{-\mu u}du\right)=\operatorname{Poi}\left(\frac\lambda\mu(1-e^{-\mu t})\right)$. (Alternatively, check that the pgf $\exp\left(\frac\lambda\mu(1-e^{-\mu t})(s-1)\right)$ satisfies the forward equations, written as $\partial_tG=(s-1)(\lambda G-\mu\partial_sG)$.)
8 False: $\theta_n=\prod_{k=1}^n\frac{\lambda_{k-1}}{\mu_k}=1$ for all $n$, so $\sum\theta_n=\infty$ and $\pi Q=0$ has no probability solution. Example: the M/M/1 queue with $\lambda=\mu$, which is null recurrent.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B Buses arrive at a stop as a Poisson process with rate $6$ per hour. Given that exactly $2$ buses arrived between 10:00 and 10:30, the probability that both arrived before 10:10 is (A) $\frac19$; (B) $\frac13$; (C) $\frac49$; (D) $\frac29$.

Idea Given $N=2$ in a $30$-minute window, the two arrival times are iid uniform on the window (Theorem 3.28(3)); the rate is irrelevant.
Compute Each falls in the first $10$ minutes with probability $\frac13$: both do with probability $\frac19$. (Option (C), $\frac49=2\cdot\frac13\cdot\frac23$, is the probability that exactly one does.)
Answer (A).

E2. CSIR Part B A continuous-time Markov chain on $\{1,2,3\}$ has generator $Q=\begin{pmatrix}-2&2&0\\1&-2&1\\0&3&-3\end{pmatrix}$. The long-run fraction of time it spends in state $3$ is (A) $\frac14$; (B) $\frac2{11}$; (C) $\frac3{11}$; (D) $\frac13$.

Idea A birth–death generator: $\lambda_0=2$, $\lambda_1=1$, $\mu_1=1$, $\mu_2=3$ (states relabelled $0,1,2$). Use the cut equations.
Compute $\theta=(1,\ 2,\ \frac{2\cdot1}{1\cdot3})=(1,2,\frac23)$, sum $\frac{11}3$, so $\pi=(\frac3{11},\frac6{11},\frac2{11})$. Option (A) is the jump chain's answer, $\nu\propto\pi_jq_j=(\frac6{11},\frac{12}{11},\frac6{11})$, a classic trap.
Answer (B).

E3. CSIR Part B GATE ST In a Yule process with birth rate $\lambda=1$ per individual and $X(0)=1$, $P(X(\log2)=3)$ equals (A) $\frac18$; (B) $\frac14$; (C) $\frac38$; (D) $\frac12$.

Idea $X(t)$ is geometric with success probability $e^{-\lambda t}$ (Theorem 3.36(2)); here $e^{-\log 2}=\frac12$.
Compute $P(X=3)=\frac12\left(\frac12\right)^2=\frac18$. (Option (B) is $P(X=2)$, option (D) is $P(X=1)$.)
Answer (A).

E4. CSIR Part C Let $N$ be a Poisson process of rate $\lambda$ with arrival times $S_1\lt S_2\lt\cdots$. Which of the following statements are true? (One or more options may be correct.) (A) Given $N(1)=2$, $S_1$ is uniformly distributed on $(0,1)$. (B) $S_1$ and $S_2-S_1$ are independent. (C) $N(1)$ and $N(2)$ are independent. (D) For $0\lt s\lt t$, $P(N(s)=0\mid N(t)=2)=(1-s/t)^2$.

(A) False Given $N(1)=2$, $S_1$ is the minimum of two iid $U(0,1)$ variables, with density $2(1-s)$ on $(0,1)$ (Theorem 3.28(3)).
(B) True They are the iid $\operatorname{Exp}(\lambda)$ inter-arrival times $E_1,E_2$ (Definition (C)).
(C) False $\operatorname{Cov}(N(1),N(2))=\lambda\gt0$ (Theorem 3.30(2)); only $N(1)$ and $N(2)-N(1)$ are independent.
(D) True Given $N(t)=2$, $N(s)\sim\operatorname{Bin}(2,s/t)$, and $P(N(s)=0)=(1-s/t)^2$.
Answer (B) and (D).

E5. CSIR Part C Consider the birth–death process on $\{0,1,2,\dots\}$ with $\lambda_n=2$ and $\mu_n=n$ for all $n$. Which of the following are true? (A) Its stationary distribution has $\pi_0=e^{-2}$. (B) The stationary distribution of its jump chain gives state $0$ probability $e^{-2}$. (C) The mean time between two successive entrances into state $0$ is $\frac{e^2}{2}$. (D) Because the death rates are unbounded, the process explodes with positive probability.

(A) True $\theta_n=\frac{2^n}{n!}$, so $\pi=\operatorname{Poi}(2)$ and $\pi_0=e^{-2}$ (M/M/∞, Theorem 3.37; the birth rates are bounded).
(B) False By Theorem 3.35(1), $\nu_n\propto\pi_nq_n=\pi_n(2+n)$, and $\sum_n\pi_n(2+n)=2+E[\operatorname{Poi}(2)]=4$. So $\nu_0=\frac{2e^{-2}}{4}=\frac{e^{-2}}2$.
(C) True $m_0=\frac1{q_0\pi_0}=\frac{1}{2e^{-2}}=\frac{e^2}2\approx3.69$ (Theorem 3.35(3)). The mean time between entrances into $0$ equals the mean return time from $0$, since a cycle starts at each entrance.
(D) False Explosion means infinitely many jumps in finite time, with the state running off to infinity. Here the birth rates are bounded and $\sum\theta_n\lt\infty$, so the process is positive recurrent (Theorem 3.37(2)); its jump chain is recurrent, and by Theorem 3.33 there is no explosion. Large death rates only pull the process down faster.
Answer (A) and (C).

E6. CSIR Part C Which of the following are true? (A) The pure birth process with $\lambda_n=2^n$ satisfies $\sum_nP(X(t)=n)\lt1$ for some $t\gt0$. (B) For every finite generator $Q$ and every $t\ge0$, all diagonal entries of $e^{tQ}$ are strictly positive. (C) If $Q$ is the generator of an irreducible CTMC on a finite set, then every entry of $e^{tQ}$ is strictly positive for every $t\gt0$. (D) There is a $2\times2$ generator $Q$ with $e^{Q}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$.

(A) True $\sum_n2^{-n}\lt\infty$, so the process explodes almost surely at a finite time $T_\infty$ with a continuous law, and $\sum_nP(X(t)=n)=P(T_\infty\gt t)\lt1$ for every $t\gt0$ (Theorem 3.36(3)).
(B) True $p_{ii}(t)\ge e^{-q_it}\gt0$: the chain may simply not move.
(C) True For $i\ne j$ choose a path of positive rates from $i$ to $j$; making exactly those jumps within time $t$ has positive probability (proof of Theorem 3.35(4)).
(D) False By (B) the diagonal of $e^Q$ is positive.
Answer (A), (B) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. The Poisson process. Start from data: arrival times of calls, and the question "what is random here?". Definitions 3.10–3.11 with all three descriptions on the board; Theorem 3.28 (the Jacobian-one change of variables is short) and Theorem 3.29, proving (B) ⇒ (A) through the differential equations in full. Theorem 3.30. Example 1 (stress the rewriting into disjoint intervals) and Example 2(b), the inspection paradox, as a class poll before the computation.
  2. Splitting, merging, compounding. Interactive 1: first $p=0.3$, then $p=0.5$; ask the class to predict the scatter before pressing Play. Theorem 3.31 with proofs of (2) and (3); Example 3 (the independence of "present" and "discharged" always surprises). Definition 3.12 and Theorem 3.32 with the total-variance proof. Then Definitions 3.13–3.14, Theorem 3.33 (state it, sketch the memoryless argument).
  3. CTMCs and birth–death processes. Theorem 3.34 with the finite proof; Example 4 by solving the scalar ODE. Theorem 3.35, emphasising $\pi_j\propto\nu_j/q_j$ and the absence of periodicity; Example 5. Definition 3.15 and the table of models; Theorem 3.36 with the Rényi-representation proof; Example 6. Theorem 3.37 with Example 7 and Interactive 2 (M/M/1 at $\lambda=0.5$ and $0.9$; then Yule). Finish with E2, E4 and E5 done live.

Discussion questions. (1) Definition (B) never mentions the Poisson distribution. Which of its assumptions would fail for buses that run to a timetable, for earthquakes with aftershocks, and for customers arriving in groups? (2) Why is the number of patients still in the department independent of the number already discharged, although both are built from the same arrivals? (3) A CTMC spends time in a state; a discrete chain only visits it. Why does that change the stationary distribution, and why does it destroy periodicity?

Misconceptions to watch for. Multiplying $P(N(s)=a)P(N(t)=b)$ for nested intervals; treating the conditional arrival times as iid uniform in order (E4(A)); forgetting that thinning must be independent of the process; writing $\operatorname{Var}$ of a compound Poisson sum as $\lambda t\operatorname{Var}(Y)$; using a stochastic matrix instead of a generator (rows summing to $1$); solving $\nu R=\nu$ and reporting $\nu$ as the CTMC's steady state; assuming every solution of $\pi Q=0$ is a genuine steady state on an infinite state space.

Suggested homework. I(1, 2, 5, 7, 8), II(1, 4, 6, 7, 8), III(1, 2, 5, 7, 8), IV(2, 3, 4, 5, 8); Exam corner E1, E2, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. Given a record of event times (earthquakes in a region, goals in football matches, arrivals at a hospital, website hits), how can we tell whether they behave like a Poisson process, and what does a departure from Poisson behaviour reveal about the mechanism?

Why it matters. Seismologists separate "background" earthquakes, which look Poisson, from aftershock clusters; hospital planners size emergency departments with Poisson arrival models; network engineers learned in the 1990s that internet traffic is far burstier than Poisson, which changed how routers are designed. In each case the diagnostic tools are exactly the theorems of this section: Poisson counts, exponential gaps and uniform conditional times.

What to do.

  1. With a seeded generator, simulate three processes on $[0,1000]$ with the same mean rate $1$: (i) a $\mathrm{PP}(1)$; (ii) a renewal process with $\operatorname{Gamma}(2,2)$ gaps (more regular); (iii) a compound Poisson "cluster" process in which events come singly or in pairs with probability $\frac12$ each, at group rate $\frac23$ (burstier).
  2. For each, cut $[0,1000]$ into $100$ windows of length $10$ and compute the index of dispersion (sample variance ÷ sample mean of the window counts). Predict its value for each process from the theory before computing.
  3. For each, take the event times in $[0,1000]$, divide by $1000$, and test them for uniformity with a Kolmogorov–Smirnov test (Theorem 3.28(3)). Also make a histogram of the gaps and compare it with $\operatorname{Exp}(1)$.
  4. Apply the same three diagnostics to a real record you can download (for example a public earthquake catalogue for one region and year) and say which of the three simulated processes it resembles.

Tools: Python with numpy and scipy (or R); a public event catalogue.

Hand in: A table of the dispersion indices and KS $p$-values for the three simulated processes and your real data, two gap histograms, and one paragraph interpreting the departures from Poisson behaviour.

Going further. Read about the renewal central limit theorem, $\operatorname{Var}N(t)\approx\sigma^2t/m^3$ for gaps with mean $m$ and variance $\sigma^2$, and about self-exciting (Hawkes) processes, in which every event raises the rate of future events; they are used for aftershocks, for financial trades and for the spread of posts on social media.

Instructor note: the expected dispersion indices are $1$ for the Poisson process; for the $\operatorname{Gamma}(2,2)$ renewal process (gap mean $\frac12\cdot2=1$, variance $\frac12$) the renewal CLT gives $\operatorname{Var}N(t)/E N(t)\to\sigma^2/m^2=\frac12$; for the cluster process Theorem 3.32 gives $E[Y^2]/E[Y]=\frac{5/2}{3/2}=\frac53$. With $100$ windows students will see values scattered around these, roughly within $\pm0.25$ for the Poisson case, since under the Poisson hypothesis $99\times$index is approximately $\chi^2_{99}$. The KS test on rescaled times essentially never rejects for (ii) and rejects for (iii) only about one time in five at the $5\%$ level (a quick simulation of $400$ runs gives these rates), because the long-run arrangement of both is still roughly uniform; the dispersion index and the gap histogram are the sharper diagnostics. Good discussion point: uniformity of the conditional times is necessary but far from sufficient.

🧪 Self-check quiz

0/5 correct

Q1. For a Poisson process of rate $\lambda$, given that exactly one event occurred in $[0,t]$, its time is

Q2. Two independent Poisson processes have rates $2$ and $3$. Their sum is

Q3. The stationary distribution $\pi$ of an irreducible finite continuous-time Markov chain with generator $Q$ is determined by

Q4. In a Yule process with per-individual birth rate $\lambda$ and $X(0)=1$, $E[X(t)]$ equals

Q5. The birth–death process with $\lambda_n=\lambda$ and $\mu_n=n\mu$ has steady state