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.
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$.
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.
- (A, counts) $N$ has independent increments and $N(t+s)-N(s)\sim\operatorname{Poi}(\lambda t)$ for all $s,t\ge0$.
- (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).$$
- (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).
- $(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)!$.
- $N(t)\sim\operatorname{Poi}(\lambda t)$ for every $t\gt0$.
- (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\}$. ∎
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.
- (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.)
- $E[N(t)]=\operatorname{Var}(N(t))=\lambda t$ and $\operatorname{Cov}(N(s),N(t))=\lambda\min(s,t)$.
- $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}}$). ∎
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.
- (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)$.
- (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)$.
- (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.
- $X$ has independent and stationary increments.
- 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).
- Wherever $M_Y(u)=E[e^{uY}]$ is finite, $M_{X(t)}(u)=\exp\left(\lambda t\,(M_Y(u)-1)\right)$.
- 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).
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.
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. ∎
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.
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$.
- 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$.
- 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$.
- 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}.$$
- 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$.
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.
| 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 |
Let $X$ be a pure birth process with rates $\lambda_n\gt0$ and $X(0)=i$.
- 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$.
- (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}$.
- (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. ∎
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).$$- 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$.
- $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.
- 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.
- 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.
- 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)$.
- 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.
- 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.
- 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.
- 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)$.
- 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.
- 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)$.
- 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.
- 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.
- $\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
- 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 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 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 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.
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$.
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$.
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$.
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$.
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$.
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.
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}$.
Suggested plan — 3 lectures × 60 min.
- 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.
- 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).
- 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 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.
- 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).
- 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.
- 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)$.
- 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.
🧪 Self-check quiz
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