Applied Probability

2021

• Paper 1, Section II, 28K

  Applied Probability | Part II, 2021

  The particles of an Ideal Gas form a spatial Poisson process on $\mathbb{R}^{3}$ with constant intensity $z>0$, called the activity of the gas.

  (a) Prove that the independent mixture of two Ideal Gases with activities $z_{1}$ and $z_{2}$ is again an Ideal Gas. What is its activity? [You must prove any results about Poisson processes that you use. The independent mixture of two gases with particles $\Pi_{1} \subset \mathbb{R}^{3}$ and $\Pi_{2} \subset \mathbb{R}^{3}$ is given by $\left.\Pi_{1} \cup \Pi_{2} .\right]$

  (b) For an Ideal Gas of activity $z>0$, find the limiting distribution of

  $$\frac{N\left(V_{i}\right)-\mathbb{E} N\left(V_{i}\right)}{\sqrt{\left|V_{i}\right|}}$$

  as $i \rightarrow \infty$ for a given sequence of subsets $V_{i} \subset \mathbb{R}^{3}$ with $\left|V_{i}\right| \rightarrow \infty$.

  (c) Let $g: \mathbb{R}^{3} \rightarrow \mathbb{R}$ be a smooth non-negative function vanishing outside a bounded subset of $\mathbb{R}^{3}$. Find the mean and variance of $\sum_{x} g(x)$, where the sum runs over the particles $x \in \mathbb{R}^{3}$ of an ideal gas of activity $z>0$. [You may use the properties of spatial Poisson processes established in the lectures.]

  [Hint: recall that the characteristic function of a Poisson random variable with mean $\lambda$ is $\left.e^{\left(e^{i t}-1\right) \lambda} \cdot\right]$

  comment

• Paper 2, Section II, $28 K$

  Applied Probability | Part II, 2021

  Let $X$ be an irreducible, non-explosive, continuous-time Markov process on the state space $\mathbb{Z}$ with generator $Q=\left(q_{x, y}\right)_{x, y \in \mathbb{Z}}$.

  (a) Define its jump chain $Y$ and prove that it is a discrete-time Markov chain.

  (b) Define what it means for $X$ to be recurrent and prove that $X$ is recurrent if and only if its jump chain $Y$ is recurrent. Prove also that this is the case if the transition semigroup $\left(p_{x, y}(t)\right)$ satisfies

  $$\int_{0}^{\infty} p_{0,0}(t) d t=\infty$$

  (c) Show that $X$ is recurrent for at least one of the following generators:

  $$\begin{array}{cc} q_{x, y}=(1+|x|)^{-2} e^{-|x-y|^{2}} & (x \neq y), \\ q_{x, y}=(1+|x-y|)^{-2} e^{-|x|^{2}} & (x \neq y) . \end{array}$$

  [Hint: You may use that the semigroup associated with a $Q$-matrix on $\mathbb{Z}$ such that $q_{x, y}$ depends only on $x-y$ (and has sufficient decay) can be written as

  $$p_{x, y}(t)=\frac{1}{2 \pi} \int_{-\pi}^{\pi} e^{-t \lambda(k)} e^{i k(x-y)} d k$$

  where $\lambda(k)=\sum_{y} q_{0, y}\left(1-e^{i k y}\right)$. You may also find the bound $1-\cos x \leqslant x^{2} / 2$ useful. $]$

  comment

• Paper 3, Section II, $27 \mathrm{~K}$

  Applied Probability | Part II, 2021

  (a) Customers arrive at a queue at the event times of a Poisson process of rate $\lambda$. The queue is served by two independent servers with exponential service times with parameter $\mu$ each. If the queue has length $n$, an arriving customer joins with probability $r^{n}$ and leaves otherwise (where $\left.r \in(0,1]\right)$. For which $\lambda>0, \mu>0$ and $r \in(0,1]$ is there a stationary distribution?

  (b) A supermarket allows a maximum of $N$ customers to shop at the same time. Customers arrive at the event times of a Poisson process of rate 1 , they enter the supermarket when possible, and they leave forever for another supermarket otherwise. Customers already in the supermarket pay and leave at the event times of an independent Poisson process of rate $\mu$. When is there a unique stationary distribution for the number of customers in the supermarket? If it exists, find it.

  (c) In the situation of part (b), started from equilibrium, show that the departure process is Poissonian.

  comment

• Paper 4, Section II, $27 \mathrm{~K}$

  Applied Probability | Part II, 2021

  Let $(X(t))_{t \geqslant 0}$ be a continuous-time Markov process with state space $I=\{1, \ldots, n\}$ and generator $Q=\left(q_{i j}\right)_{i, j \in I}$ satisfying $q_{i j}=q_{j i}$ for all $i, j \in I$. The local time up to time $t>0$ of $X$ is the random vector $L(t)=\left(L_{i}(t)\right)_{i \in I} \in \mathbb{R}^{n}$ defined by

  $$L_{i}(t)=\int_{0}^{t} 1_{X(s)=i} d s \quad(i \in I)$$

  (a) Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be any function that is differentiable with respect to its second argument, and set

  $$f_{t}(i, \ell)=\mathbb{E}_{i} f(X(t), \ell+L(t)), \quad\left(i \in I, \ell \in \mathbb{R}^{n}\right)$$

  Show that

  $$\frac{\partial}{\partial t} f_{t}(i, \ell)=M f_{t}(i, \ell)$$

  where

  $$M f(i, \ell)=\sum_{j \in I} q_{i j} f(j, \ell)+\frac{\partial}{\partial \ell_{i}} f(i, \ell)$$

  (b) For $y \in \mathbb{R}^{n}$, write $y^{2}=\left(y_{i}^{2}\right)_{i \in I} \in[0, \infty)^{n}$ for the vector of squares of the components of $y$. Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function such that $f(i, \ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Using integration by parts, or otherwise, show that for all $i$

  $$-\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} \sum_{j=1}^{n} y_{j} M f\left(j, \frac{1}{2} y^{2}\right) d y=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) f\left(i, \frac{1}{2} y^{2}\right) d y,$$

  where $y^{T} Q y$ denotes $\sum_{k, m \in I} y_{k} q_{k m} y_{m}$.

  (c) Let $g: \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function with $g(\ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Given $t>0, j \in I$, now let

  $$f(i, \ell)=\mathbb{E}_{i}\left[g(\ell+L(t)) 1_{X(t)=j}\right]$$

  in part (b) and deduce, using part (a), that

  $$\begin{aligned} \int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} y_{j} g\left(\frac{1}{2} y^{2}\right) d y \\ &=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right)\left(\int_{0}^{\infty} \mathbb{E}_{i}\left[1_{X(t)=j} g\left(\frac{1}{2} y^{2}+L(t)\right)\right] d t\right) d y \end{aligned}$$

  [You may exchange the order of integrals and derivatives without justification.]

  comment

2020

• Paper 1, Section II, 28K

  Applied Probability | Part II, 2020

  (a) What is meant by a birth process $N=(N(t): t \geqslant 0)$ with strictly positive rates $\lambda_{0}, \lambda_{1}, \ldots ?$ Explain what is meant by saying that $N$ is non-explosive.

  (b) Show that $N$ is non-explosive if and only if

  $$\sum_{n=0}^{\infty} \frac{1}{\lambda_{n}}=\infty$$

  (c) Suppose $N(0)=0$, and $\lambda_{n}=\alpha n+\beta$ where $\alpha, \beta>0$. Show that

  $$\mathbb{E}(N(t))=\frac{\beta}{\alpha}\left(e^{\alpha t}-1\right) .$$

  comment

• Paper 2, Section II, 27K

  Applied Probability | Part II, 2020

  (i) Let $X$ be a Markov chain in continuous time on the integers $\mathbb{Z}$ with generator $\mathbf{G}=\left(g_{i, j}\right)$. Define the corresponding jump chain $Y$.

  Define the terms irreducibility and recurrence for $X$. If $X$ is irreducible, show that $X$ is recurrent if and only if $Y$ is recurrent.

  (ii) Suppose

  $$g_{i, i-1}=3^{|i|}, \quad g_{i, i}=-3^{|i|+1}, \quad g_{i, i+1}=2 \cdot 3^{|i|}, \quad i \in \mathbb{Z} .$$

  Show that $X$ is transient, find an invariant distribution, and show that $X$ is explosive. [Any general results may be used without proof but should be stated clearly.]

  comment

• Paper 3, Section II, 27K

  Applied Probability | Part II, 2020

  Define a renewal-reward process, and state the renewal-reward theorem.

  A machine $M$ is repaired at time $t=0$. After any repair, it functions without intervention for a time that is exponentially distributed with parameter $\lambda$, at which point it breaks down (assume the usual independence). Following any repair at time $T$, say, it is inspected at times $T, T+m, T+2 m, \ldots$, and instantly repaired if found to be broken (the inspection schedule is then restarted). Find the long run proportion of time that $M$ is working. [You may express your answer in terms of an integral.]

  comment

• Paper 4, Section II, K

  Applied Probability | Part II, 2020

  (i) Explain the notation $\mathrm{M}(\lambda) / \mathrm{M}(\mu) / 1$ in the context of queueing theory. [In the following, you may use without proof the fact that $\pi_{n}=(\lambda / \mu)^{n}$ is the invariant distribution of such a queue when $0<\lambda<\mu$.

  (ii) In a shop queue, some customers rejoin the queue after having been served. Let $\lambda, \beta \in(0, \infty)$ and $\delta \in(0,1)$. Consider a $\mathrm{M}(\lambda) / \mathrm{M}(\mu) / 1$ queue subject to the modification that, on completion of service, each customer leaves the shop with probability $\delta$, or rejoins the shop queue with probability $1-\delta$. Different customers behave independently of one another, and all service times are independent random variables.

  Find the distribution of the total time a given customer spends being served by the server. Hence show that equilibrium is possible if $\lambda<\delta \mu$, and find the invariant distribution of the queue-length in this case.

  (iii) Show that, in equilibrium, the departure process is Poissonian, whereas, assuming the rejoining customers go to the end of the queue, the process of customers arriving at the queue (including the rejoining ones) is not Poissonian.

  comment

2019

• Paper 1, Section II, K

  Applied Probability | Part II, 2019

  Let $S$ be a countable set, and let $P=\left(p_{i, j}: i, j \in S\right)$ be a Markov transition matrix with $p_{i, i}=0$ for all $i$. Let $Y=\left(Y_{n}: n=0,1,2, \ldots\right)$ be a discrete-time Markov chain on the state space $S$ with transition matrix $P$.

  The continuous-time process $X=\left(X_{t}: t \geqslant 0\right)$ is constructed as follows. Let $\left(U_{m}: m=0,1,2, \ldots\right)$ be independent, identically distributed random variables having the exponential distribution with mean 1. Let $g$ be a function on $S$ such that $\varepsilon<g(i)<\frac{1}{\varepsilon}$ for all $i \in S$ and some constant $\varepsilon>0$. Let $V_{m}=U_{m} / g\left(Y_{m}\right)$ for $m \geqslant 0$. Let $T_{0}=0$ and $T_{n}=\sum_{m=0}^{n-1} V_{m}$ for $n \geqslant 1$. Finally, let $X_{t}=Y_{n}$ for $T_{n} \leqslant t<T_{n+1}$.

  (a) Explain briefly why $X$ is a continuous-time Markov chain on $S$, and write down its generator in terms of $P$ and the vector $g=(g(i): i \in S)$.

  (b) What does it mean to say that the chain $X$ is irreducible? What does it mean to say a state $i \in S$ is (i) recurrent and (ii) positive recurrent?

  (c) Show that

  (i) $X$ is irreducible if and only if $Y$ is irreducible;

  (ii) $X$ is recurrent if and only if $Y$ is recurrent.

  (d) Suppose $Y$ is irreducible and positive recurrent with invariant distribution $\pi$. Express the invariant distribution of $X$ in terms of $\pi$ and $g$.

  comment

• Paper 2, Section II, K

  Applied Probability | Part II, 2019

  Let $X=\left(X_{t}: t \geqslant 0\right)$ be a Markov chain on the non-negative integers with generator $G=\left(g_{i, j}\right)$ given by

  $$\begin{aligned} g_{i, i+1} &=\lambda_{i}, & & i \geqslant 0 \\ g_{i, 0} &=\lambda_{i} \rho_{i}, & & i>0 \\ g_{i, j} &=0, & & j \neq 0, i, i+1 \end{aligned}$$

  for a given collection of positive numbers $\lambda_{i}, \rho_{i}$.

  (a) State the transition matrix of the jump chain $Y$ of $X$.

  (b) Why is $X$ not reversible?

  (c) Prove that $X$ is transient if and only if $\prod_{i}\left(1+\rho_{i}\right)<\infty$.

  (d) Assume that $\prod_{i}\left(1+\rho_{i}\right)<\infty$. Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for $X$ to be explosive.

  (e) Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for the existence of an invariant measure for $X$.

  [You may use any general results from the course concerning Markov chains and pure birth processes so long as they are clearly stated.]

  comment

• Paper 3, Section II, K

  Applied Probability | Part II, 2019

  (a) What does it mean to say that a continuous-time Markov chain $X=\left(X_{t}: 0 \leqslant\right.$ $t \leqslant T$ ) with state space $S$ is reversible in equilibrium? State the detailed balance equations, and show that any probability distribution on $S$ satisfying them is invariant for the chain.

  (b) Customers arrive in a shop in the manner of a Poisson process with rate $\lambda>0$. There are $s$ servers, and capacity for up to $N$ people waiting for service. Any customer arriving when the shop is full (in that the total number of customers present is $N+s$ ) is not admitted and never returns. Service times are exponentially distributed with parameter $\mu>0$, and they are independent of one another and of the arrivals process. Describe the number $X_{t}$ of customers in the shop at time $t$ as a Markov chain.

  Calculate the invariant distribution $\pi$ of $X=\left(X_{t}: t \geqslant 0\right)$, and explain why $\pi$ is the unique invariant distribution. Show that $X$ is reversible in equilibrium.

  [Any general result from the course may be used without proof, but must be stated clearly.]

  comment

• Paper 4, Section II, K

  Applied Probability | Part II, 2019

  (a) Let $\lambda: \mathbb{R}^{d} \rightarrow[0, \infty)$ be such that $\Lambda(A):=\int_{A} \lambda(\mathbf{x}) d \mathbf{x}$ is finite for any bounded measurable set $A \subseteq \mathbb{R}^{d}$. State the properties which define a (non-homogeneous) Poisson process $\Pi$ on $\mathbb{R}^{d}$ with intensity function $\lambda$.

  (b) Let $\Pi$ be a Poisson process on $\mathbb{R}^{d}$ with intensity function $\lambda$, and let $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^{s}$ be a given function. Give a clear statement of the necessary conditions on the pair $\Lambda, f$ subject to which $f(\Pi)$ is a Poisson process on $\mathbb{R}^{s}$. When these conditions hold, express the mean measure of $f(\Pi)$ in terms of $\Lambda$ and $f$.

  (c) Let $\Pi$ be a homogeneous Poisson process on $\mathbb{R}^{2}$ with constant intensity 1 , and let $f: \mathbb{R}^{2} \rightarrow[0, \infty)$ be given by $f\left(x_{1}, x_{2}\right)=x_{1}^{2}+x_{2}^{2}$. Show that $f(\Pi)$ is a homogeneous Poisson process on $[0, \infty)$ with constant intensity $\pi$.

  Let $R_{1}, R_{2}, \ldots$ be an increasing sequence of positive random variables such that the points of $f(\Pi)$ are $R_{1}^{2}, R_{2}^{2}, \ldots$ Show that $R_{k}$ has density function

  $$h_{k}(r)=\frac{1}{(k-1) !} 2 \pi r\left(\pi r^{2}\right)^{k-1} e^{-\pi r^{2}}, \quad r>0$$

  comment

2018

• Paper 1, Section II, J

  Applied Probability | Part II, 2018

  Let $\lambda:[0, \infty) \rightarrow(0, \infty)$ be a continuous function. Explain what is meant by an inhomogeneous Poisson process with intensity function $\lambda$.

  Let $\left(N_{t}: t \geqslant 0\right)$ be such an inhomogeneous Poisson process, and let $M_{t}=N_{g(t)}$ where $g:[0, \infty) \rightarrow[0, \infty)$ is strictly increasing, differentiable and satisfies $g(0)=0$. Show that $M$ is a homogeneous Poisson process with intensity 1 if $\Lambda(g(t))=t$ for all $t$, where $\Lambda(t)=\int_{0}^{t} \lambda(u) d u$. Deduce that $N_{t}$ has the Poisson distribution with mean $\Lambda(t)$.

  Bicycles arrive at the start of a long road in the manner of a Poisson process $N=\left(N_{t}: t \geqslant 0\right)$ with constant intensity $\lambda$. The $i$ th bicycle has constant velocity $V_{i}$, where $V_{1}, V_{2}, \ldots$ are independent, identically distributed random variables, which are independent of $N$. Cyclists can overtake one another freely. Show that the number of bicycles on the first $x$ miles of the road at time $t$ has the Poisson distribution with parameter $\lambda \mathbb{E}\left(V^{-1} \min \{x, V t\}\right)$.

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2018

  Let $X=\left(X_{t}: t \geqslant 0\right)$ be a continuous-time Markov chain on the finite state space $S$. Define the terms generator (or Q-matrix) and invariant distribution, and derive an equation that links the generator $G$ and any invariant distribution $\pi$. Comment on the possible non-uniqueness of invariant distributions.

  Suppose $X$ is irreducible, and let $N=\left(N_{t}: t \geqslant 0\right)$ be a Poisson process with intensity $\lambda$, that is independent of $X$. Let $Y_{n}$ be the value of $X$ immediately after the $n$th arrival-time of $N$ (and $\left.Y_{0}=X_{0}\right)$. Show that $\left(Y_{n}: n=0,1, \ldots\right)$ is a discrete-time Markov chain, state its transition matrix and prove that it has the same invariant distribution as $X$.

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2018

  Individuals arrive in a shop in the manner of a Poisson process with intensity $\lambda$, and they await service in the order of their arrival. Their service times are independent, identically distributed random variables $S_{1}, S_{2}, \ldots$. For $n \geqslant 1$, let $Q_{n}$ be the number remaining in the shop immediately after the $n$th departure. Show that

  $$Q_{n+1}=A_{n}+Q_{n}-h\left(Q_{n}\right)$$

  where $A_{n}$ is the number of arrivals during the $(n+1)$ th service period, and $h(x)=$ $\min \{1, x\}$.

  Show that

  $$\mathbb{E}\left(A_{n}\right)=\rho, \quad \mathbb{E}\left(A_{n}^{2}\right)=\rho+\lambda^{2} \mathbb{E}\left(S^{2}\right),$$

  where $S$ is a typical service period, and $\rho=\lambda \mathbb{E}(S)$ is the traffic intensity of the queue.

  Suppose $\rho<1$, and the queue is in equilibrium in the sense that $Q_{n}$ and $Q_{n+1}$ have the same distribution for all $n$. Express $\mathbb{E}\left(Q_{n}\right)$ in terms of $\lambda, \mathbb{E}(S), \mathbb{E}\left(S^{2}\right)$. Deduce that the mean waiting time (prior to service) of a typical individual is $\frac{1}{2} \lambda \mathbb{E}\left(S^{2}\right) /(1-\rho)$.

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2018

  Let $X_{1}, X_{2}, \ldots$ be independent, identically distributed random variables with finite mean $\mu$. Explain what is meant by saying that the random variable $M$ is a stopping time with respect to the sequence $\left(X_{i}: i=1,2, \ldots\right)$.

  Let $M$ be a stopping time with finite mean $\mathbb{E}(M)$. Prove Wald's equation:

  $$\mathbb{E}\left(\sum_{i=1}^{M} X_{i}\right)=\mu \mathbb{E}(M)$$

  [Here and in the following, you may use any standard theorem about integration.]

  Suppose the $X_{i}$ are strictly positive, and let $N$ be the renewal process with interarrival times $\left(X_{i}: i=1,2, \ldots\right)$. Prove that $m(t)=\mathbb{E}\left(N_{t}\right)$ satisfies the elementary renewal theorem:

  $$\frac{1}{t} m(t) \rightarrow \frac{1}{\mu} \quad \text { as } t \rightarrow \infty .$$

  A computer keyboard contains 100 different keys, including the lower and upper case letters, the usual symbols, and the space bar. A monkey taps the keys uniformly at random. Find the mean number of keys tapped until the first appearance of the sequence 'lava' as a sequence of 4 consecutive characters.

  Find the mean number of keys tapped until the first appearance of the sequence 'aa' as a sequence of 2 consecutive characters.

  comment

2017

• Paper 1, Section II, $27 \mathrm{~K}$

  Applied Probability | Part II, 2017

  (a) Define a continuous time Markov chain $X$ with infinitesimal generator $Q$ and jump chain $Y$.

  (b) Let $i$ be a transient state of a continuous-time Markov chain $X$ with $X(0)=i$. Show that the time spent in state $i$ has an exponential distribution and explicitly state its parameter.

  [You may use the fact that if $S \sim \operatorname{Exp}(\lambda)$, then $\mathbb{E}\left[e^{\theta S}\right]=\lambda /(\lambda-\theta)$ for $\theta<\lambda$.]

  (c) Let $X$ be an asymmetric random walk in continuous time on the non-negative integers with reflection at 0 , so that

  $$q_{i, j}= \begin{cases}\lambda & \text { if } \quad j=i+1, i \geqslant 0 \\ \mu & \text { if } \quad j=i-1, i \geqslant 1\end{cases}$$

  Suppose that $X(0)=0$ and $\lambda>\mu$. Show that for all $r \geqslant 1$, the total time $T_{r}$ spent in state $r$ is exponentially distributed with parameter $\lambda-\mu$.

  Assume now that $X(0)$ has some general distribution with probability generating function $G$. Find the expected amount of time spent at 0 in terms of $G$.

  comment

• Paper 2, Section II, K

  Applied Probability | Part II, 2017

  (a) Give the definition of a Poisson process on $\mathbb{R}_{+}$. Let $X$ be a Poisson process on $\mathbb{R}_{+}$. Show that conditional on $\left\{X_{t}=n\right\}$, the jump times $J_{1}, \ldots, J_{n}$ have joint density function

  $$f\left(t_{1}, \ldots, t_{n}\right)=\frac{n !}{t^{n}} \mathbf{1}\left(0 \leqslant t_{1} \leqslant \ldots \leqslant t_{n} \leqslant t\right)$$

  where $\boldsymbol{I}(A)$ is the indicator of the set $A$.

  (b) Let $N$ be a Poisson process on $\mathbb{R}_{+}$with intensity $\lambda$ and jump times $\left\{J_{k}\right\}$. If $g: \mathbb{R}_{+} \rightarrow \mathbb{R}$ is a real function, we define for all $t>0$

  $$\mathcal{R}(g)[0, t]=\left\{g\left(J_{k}\right): k \in \mathbb{N}, J_{k} \leqslant t\right\}$$

  Show that for all $t>0$ the following is true

  $$\mathbb{P}(0 \in \mathcal{R}(g)[0, t])=1-\exp \left(-\lambda \int_{0}^{t} \mathbf{I}(g(s)=0) d s\right)$$

  comment

• Paper 3, Section II, K

  Applied Probability | Part II, 2017

  (a) Define the Moran model and Kingman's $n$-coalescent. Define Kingman's infinite coalescent.

  Show that Kingman's infinite coalescent comes down from infinity. In other words, with probability one, the number of blocks of $\Pi_{t}$ is finite at any time $t>0$.

  (b) Give the definition of a renewal process.

  Let $\left(X_{i}\right)$ denote the sequence of inter-arrival times of the renewal process $N$. Suppose that $\mathbb{E}\left[X_{1}\right]>0$.

  Prove that $\mathbb{P}(N(t) \rightarrow \infty$ as $t \rightarrow \infty)=1$.

  Prove that $\mathbb{E}\left[e^{\theta N(t)}\right]<\infty$ for some strictly positive $\theta$.

  [Hint: Consider the renewal process with inter-arrival times $X_{k}^{\prime}=\varepsilon \mathbf{1}\left(X_{k} \geqslant \varepsilon\right)$ for some suitable $\varepsilon>0$.]

  comment

• Paper 4, Section II, $26 K$

  Applied Probability | Part II, 2017

  (a) Give the definition of an $M / M / 1$ queue. Prove that if $\lambda$ is the arrival rate and $\mu$ the service rate and $\lambda<\mu$, then the length of the queue is a positive recurrent Markov chain. What is the equilibrium distribution?

  If the queue is in equilibrium and a customer arrives at some time $t$, what is the distribution of the waiting time (time spent waiting in the queue plus service time)?

  (b) We now modify the above queue: on completion of service a customer leaves with probability $\delta$, or goes to the back of the queue with probability $1-\delta$. Find the distribution of the total time a customer spends being served.

  Hence show that equilibrium is possible if $\lambda<\delta \mu$ and find the stationary distribution.

  Show that, in equilibrium, the departure process is Poisson.

  [You may use relevant theorems provided you state them clearly.]

  comment

2016

• Paper 1, Section II, J

  Applied Probability | Part II, 2016

  (a) Define a continuous-time Markov chain $X$ with infinitesimal generator $Q$ and jump chain $Y$.

  (b) Prove that if a state $x$ is transient for $Y$, then it is transient for $X$.

  (c) Prove or provide a counterexample to the following: if $x$ is positive recurrent for $X$, then it is positive recurrent for $Y$.

  (d) Consider the continuous-time Markov chain $\left(X_{t}\right)_{t \geqslant 0}$ on $\mathbb{Z}$ with non-zero transition rates given by

  $$q(i, i+1)=2 \cdot 3^{|i|}, \quad q(i, i)=-3^{|i|+1} \quad \text { and } \quad q(i, i-1)=3^{|i|}$$

  Determine whether $X$ is transient or recurrent. Let $T_{0}=\inf \left\{t \geqslant J_{1}: X_{t}=0\right\}$, where $J_{1}$ is the first jump time. Does $X$ have an invariant distribution? Justify your answer. Calculate $\mathbb{E}_{0}\left[T_{0}\right]$.

  (e) Let $X$ be a continuous-time random walk on $\mathbb{Z}^{d}$ with $q(x)=\|x\|^{\alpha} \wedge 1$ and $q(x, y)=q(x) /(2 d)$ for all $y \in \mathbb{Z}^{d}$ with $\|y-x\|=1$. Determine for which values of $\alpha$ the walk is transient and for which it is recurrent. In the recurrent case, determine the range of $\alpha$ for which it is also positive recurrent. [Here $\|x\|$ denotes the Euclidean norm of $x$.]

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2016

  (a) Define an $M / M / \infty$ queue and write without proof its stationary distribution. State Burke's theorem for an $M / M / \infty$ queue.

  (b) Let $X$ be an $M / M / \infty$ queue with arrival rate $\lambda$ and service rate $\mu$ started from the stationary distribution. For each $t$, denote by $A_{1}(t)$ the last time before $t$ that a customer departed the queue and $A_{2}(t)$ the first time after $t$ that a customer departed the queue. If there is no arrival before time $t$, then we set $A_{1}(t)=0$. What is the limit as $t \rightarrow \infty$ of $\mathbb{E}\left[A_{2}(t)-A_{1}(t)\right]$ ? Explain.

  (c) Consider a system of $N$ queues serving a finite number $K$ of customers in the following way: at station $1 \leqslant i \leqslant N$, customers are served immediately and the service times are independent exponentially distributed with parameter $\mu_{i}$; after service, each customer goes to station $j$ with probability $p_{i j}>0$. We assume here that the system is closed, i.e., $\sum_{j} p_{i j}=1$ for all $1 \leqslant i \leqslant N$.

  Let $S=\left\{\left(n_{1}, \ldots, n_{N}\right): n_{i} \in \mathbb{N}, \sum_{i=1}^{N} n_{i}=K\right\}$ be the state space of the Markov chain. Write down its $Q$-matrix. Also write down the $Q$-matrix $R$ corresponding to the position in the network of one customer (that is, when $K=1$ ). Show that there is a unique distribution $\left(\lambda_{i}\right)_{1 \leqslant i \leqslant N}$ such that $\lambda R=0$. Show that

  $$\pi(n)=C_{N} \prod_{i=1}^{N} \frac{\lambda_{i}^{n_{i}}}{n_{i} !}, \quad n=\left(n_{1}, \ldots, n_{N}\right) \in S$$

  defines an invariant measure for the chain. Are the queue lengths independent at equilibrium?

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2016

  (a) State the thinning and superposition properties of a Poisson process on $\mathbb{R}_{+}$. Prove the superposition property.

  (b) A bi-infinite Poisson process $\left(N_{t}: t \in \mathbb{R}\right)$ with $N_{0}=0$ is a process with independent and stationary increments over $\mathbb{R}$. Moreover, for all $-\infty<s \leqslant t<\infty$, the increment $N_{t}-N_{s}$ has the Poisson distribution with parameter $\lambda(t-s)$. Prove that such a process exists.

  (c) Let $N$ be a bi-infinite Poisson process on $\mathbb{R}$ of intensity $\lambda$. We identify it with the set of points $\left(S_{n}\right)$ of discontinuity of $N$, i.e., $N[s, t]=\sum_{n} \mathbf{l}\left(S_{n} \in[s, t]\right)$. Show that if we shift all the points of $N$ by the same constant $c$, then the resulting process is also a Poisson process of intensity $\lambda$.

  Now suppose we shift every point of $N$ by $+1$ or $-1$ with equal probability. Show that the final collection of points is still a Poisson process of intensity $\lambda$. [You may assume the thinning and superposition properties for the bi-infinite Poisson process.]

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2016

  (a) Give the definition of a renewal process. Let $\left(N_{t}\right)_{t \geqslant 0}$ be a renewal process associated with $\left(\xi_{i}\right)$ with $\mathbb{E} \xi_{1}=1 / \lambda<\infty$. Show that almost surely

  $$\frac{N_{t}}{t} \rightarrow \lambda \quad \text { as } t \rightarrow \infty$$

  (b) Give the definition of Kingman's $n$-coalescent. Let $\tau$ be the first time that all blocks have coalesced. Find an expression for $\mathbb{E} e^{-q \tau}$. Let $L_{n}$ be the total length of the branches of the tree, i.e., if $\tau_{i}$ is the first time there are $i$ lineages, then $L_{n}=$ $\sum_{i=2}^{n} i\left(\tau_{i-1}-\tau_{i}\right)$. Show that $\mathbb{E} L_{n} \sim 2 \log n$ as $n \rightarrow \infty$. Show also that $\operatorname{Var}\left(L_{n}\right) \leqslant C$ for all $n$, where $C$ is a positive constant, and that in probability

  $$\frac{L_{n}}{\mathbb{E} L_{n}} \rightarrow 1 \quad \text { as } n \rightarrow \infty$$

  comment

2015

• Paper 1, Section II, K

  Applied Probability | Part II, 2015

  (a) Give the definition of a birth and death chain in terms of its generator. Show that a measure $\pi$ is invariant for a birth and death chain if and only if it solves the detailed balance equations.

  (b) There are $s$ servers in a post office and a single queue. Customers arrive as a Poisson process of rate $\lambda$ and the service times at each server are independent and exponentially distributed with parameter $\mu$. Let $X_{t}$ denote the number of customers in the post office at time $t$. Find conditions on $\lambda, \mu$ and $s$ for $X$ to be positive recurrent, null recurrent and transient, justifying your answers.

  comment

• Paper 2, Section II, $24 K$

  Applied Probability | Part II, 2015

  (i) Defne a Poisson process on $\mathbb{R}_{+}$with rate $\lambda$. Let $N$ and $M$ be two independent Poisson processes on $\mathbb{R}_{+}$of rates $\lambda$ and $\mu$ respectively. Prove that $N+M$ is also a Poisson process and find its rate.

  (ii) Let $X$ be a discrete time Markov chain with transition matrix $K$ on the finite state space $S$. Find the generator of the continuous time Markov chain $Y_{t}=X_{N_{t}}$ in terms of $K$ and $\lambda$. Show that if $\pi$ is an invariant distribution for $X$, then it is also invariant for $Y$.

  Suppose that $X$ has an absorbing state $a$. If $\tau_{a}$ and $T_{a}$ are the absorption times for $X$ and $Y$ respectively, write an equation that relates $\mathbb{E}_{x}\left[\tau_{a}\right]$ and $\mathbb{E}_{x}\left[T_{a}\right]$, where $x \in S$.

  [Hint: You may want to prove that if $\xi_{1}, \xi_{2}, \ldots$ are i.i.d. non-negative random variables with $\mathbb{E}\left[\xi_{1}\right]<\infty$ and $M$ is an independent non-negative random variable, then $\left.\mathbb{E}\left[\sum_{i=1}^{M} \xi_{i}\right]=\mathbb{E}[M] \mathbb{E}\left[\xi_{1}\right] .\right]$

  comment

• Paper 3, Section II, K

  Applied Probability | Part II, 2015

  (i) Let $X$ be a Poisson process of parameter $\lambda$. Let $Y$ be obtained by taking each point of $X$ and, independently of the other points, keeping it with probability $p$. Show that $Y$ is another Poisson process and find its intensity. Show that for every fixed $t$ the random variables $Y_{t}$ and $X_{t}-Y_{t}$ are independent.

  (ii) Suppose we have $n$ bins, and balls arrive according to a Poisson process of rate 1 . Upon arrival we choose a bin uniformly at random and place the ball in it. We let $M_{n}$ be the maximum number of balls in any bin at time $n$. Show that

  $$\mathbb{P}\left(M_{n} \geqslant(1+\epsilon) \frac{\log n}{\log \log n}\right) \rightarrow 0 \quad \text { as } n \rightarrow \infty$$

  [You may use the fact that if $\xi$ is a Poisson random variable of mean 1 , then

  $$\mathbb{P}(\xi \geqslant x) \leqslant \exp (x-x \log x) .]$$

  comment

• Paper 4, Section II, K

  Applied Probability | Part II, 2015

  (i) Let $X$ be a Markov chain on $S$ and $A \subset S$. Let $T_{A}$ be the hitting time of $A$ and $\tau_{y}$ denote the total time spent at $y \in S$ by the chain before hitting $A$. Show that if $h(x)=\mathbb{P}_{x}\left(T_{A}<\infty\right)$, then $\mathbb{E}_{x}\left[\tau_{y} \mid T_{A}<\infty\right]=[h(y) / h(x)] \mathbb{E}_{x}\left(\tau_{y}\right) .$

  (ii) Define the Moran model and show that if $X_{t}$ is the number of individuals carrying allele $a$ at time $t \geqslant 0$ and $\tau$ is the fixation time of allele $a$, then

  $$\mathbb{P}\left(X_{\tau}=N \mid X_{0}=i\right)=\frac{i}{N}$$

  Show that conditionally on fixation of an allele $a$ being present initially in $i$ individuals,

  $$\mathbb{E}[\tau \mid \text { fixation }]=N-i+\frac{N-i}{i} \sum_{j=1}^{i-1} \frac{j}{N-j}$$

  comment

2014

• Paper 1, Section II, J

  Applied Probability | Part II, 2014

  (i) Explain what a $Q$-matrix is. Let $Q$ be a $Q$-matrix. Define the notion of a Markov chain $\left(X_{t}, t \geqslant 0\right)$ in continuous time with $Q$-matrix given by $Q$, and give a construction of $\left(X_{t}, t \geqslant 0\right)$. [You are not required to justify this construction.]

  (ii) A population consists of $N_{t}$ individuals at time $t \geqslant 0$. We assume that each individual gives birth to a new individual at constant rate $\lambda>0$. As the population is competing for resources, we assume that for each $n \geqslant 1$, if $N_{t}=n$, then any individual in the population at time $t$ dies in the time interval $[t, t+h)$ with probability $\delta_{n} h+o(h)$, where $\left(\delta_{n}\right)_{n=1}^{\infty}$ is a given sequence satisfying $\delta_{1}=0, \delta_{n}>0$ for $n \geqslant 2$. Formulate a Markov chain model for $\left(N_{t}, t \geqslant 0\right)$ and write down the $Q$-matrix explicitly. Then find a necessary and sufficient condition on $\left(\delta_{n}\right)_{n=1}^{\infty}$ so that the Markov chain has an invariant distribution. Compute the invariant distribution in the case where $\delta_{n}=\mu(n-1)$ and $\mu>0$.

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2014

  (i) Explain what the Moran model and the infinite alleles model are. State Ewens' sampling formula for the distribution of the allelic frequency spectrum $\left(a_{1}, \ldots, a_{n}\right)$ in terms of $\theta$ where $\theta=N u$ with $u$ denoting the mutation rate per individual and $N$ the population size.

  Let $K_{n}$ be the number of allelic types in a sample of size $n$. Give, without justification, an expression for $\mathbb{E}\left(K_{n}\right)$ in terms of $\theta$.

  (ii) Let $K_{n}$ and $\theta$ be as above. Show that for $1 \leqslant k \leqslant n$ we have that

  $$P\left(K_{n}=k\right)=C \frac{\theta^{k}}{\theta(\theta+1) \cdots(\theta+n-1)}$$

  for some constant $C$ that does not depend on $\theta$.

  Show that, given $\left\{K_{n}=k\right\}$, the distribution of the allelic frequency spectrum $\left(a_{1}, \ldots, a_{n}\right)$ does not depend on $\theta$.

  Show that the value of $\theta$ which maximises $\mathbb{P}\left(K_{n}=k\right)$ is the one for which $k=\mathbb{E}\left(K_{n}\right)$.

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2014

  (i) Define a Poisson process $\left(N_{t}, t \geqslant 0\right)$ with intensity $\lambda$. Specify without justification the distribution of $N_{t}$. Let $T_{1}, T_{2}, \ldots$ denote the jump times of $\left(N_{t}, t \geqslant 0\right)$. Derive the joint distribution of $\left(T_{1}, \ldots, T_{n}\right)$ given $\left\{N_{t}=n\right\}$.

  (ii) Let $\left(N_{t}, t \geqslant 0\right)$ be a Poisson process with intensity $\lambda>0$ and let $X_{1}, X_{2}, \ldots$ be a sequence of i.i.d. random variables, independent of $\left(N_{t}, t \geqslant 0\right)$, all having the same distribution as a random variable $X$. Show that if $g(s, x)$ is a real-valued function of real variables $s, x$, and $T_{j}$ are the jump times of $\left(N_{t}, t \geqslant 0\right)$ then

  $$\mathbb{E}\left[\exp \left\{\theta \sum_{j=1}^{N_{t}} g\left(T_{j}, X_{j}\right)\right\}\right]=\exp \left\{\lambda \int_{0}^{t}\left(\mathbb{E}\left(e^{\theta g(s, X)}\right)-1\right) d s\right\}$$

  for all $\theta \in \mathbb{R}$. [Hint: Condition on $\left\{N_{t}=n\right\}$ and $T_{1}, \ldots, T_{n}$, using (i).]

  (iii) A university library is open from 9 am to $5 \mathrm{pm}$. Students arrive at times of a Poisson process with intensity $\lambda$. Each student spends a random amount of time in the library, independently of the other students. These times are identically distributed for all students and have the same distribution as a random variable $X$. Show that the number of students in the library at $5 \mathrm{pm}$ is a Poisson random variable with a mean that you should specify.

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2014

  (i) Define the $M / M / 1$ queue with arrival rate $\lambda$ and service rate $\mu$. Find conditions on the parameters $\lambda$ and $\mu$ for the queue to be transient, null recurrent, and positive recurrent, briefly justifying your answers. In the last case give with justification the invariant distribution explicitly. Answer the same questions for an $M / M / \infty$ queue.

  (ii) At a taxi station, customers arrive at a rate of 3 per minute, and taxis at a rate of 2 per minute. Suppose that a taxi will wait no matter how many other taxis are present. However, if a person arriving does not find a taxi waiting he or she leaves to find alternative transportation.

  Find the long-run proportion of arriving customers who get taxis, and find the average number of taxis waiting in the long run.

  An agent helps to assign customers to taxis, and so long as there are taxis waiting he is unable to have his coffee. Once a taxi arrives, how long will it take on average before he can have another sip of his coffee?

  comment

2013

• Paper 1, Section II, J

  Applied Probability | Part II, 2013

  Let $\left(X_{t}, t \geqslant 0\right)$ be a Markov chain on $\{0,1, \ldots\}$ with $Q$-matrix given by

  $$\begin{aligned} q_{n, n+1} &=\lambda_{n} \\ q_{n, 0} &=\lambda_{n} \varepsilon_{n} \quad(n>0) \\ q_{n, m} &=0 \quad \text { if } m \notin\{0, n, n+1\} \end{aligned}$$

  where $\varepsilon_{n}, \lambda_{n}>0$.

  (i) Show that $X$ is transient if and only if $\sum_{n} \varepsilon_{n}<\infty$. [You may assume without proof that $x(1-\delta) \leqslant \log (1+x) \leqslant x$ for all $\delta>0$ and all sufficiently small positive $x$.]

  (ii) Assume that $\sum_{n} \varepsilon_{n}<\infty$. Find a necessary and sufficient condition for $X$ to be almost surely explosive. [You may assume without proof standard results about pure birth processes, provided that they are stated clearly.]

  (iii) Find a stationary measure for $X$. For the case $\lambda_{n}=\lambda$ and $\varepsilon_{n}=\alpha /(n+1)(\lambda, \alpha>0)$, show that $X$ is positive recurrent if and only if $\alpha>1$.

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2013

  (i) Define a Poisson process as a Markov chain on the non-negative integers and state three other characterisations.

  (ii) Let $\lambda(s)(s \geqslant 0)$ be a continuous positive function. Let $\left(X_{t}, t \geqslant 0\right)$ be a right-continuous process with independent increments, such that

  $$\begin{aligned} \mathbb{P}\left(X_{t+h}=X_{t}+1\right) &=\lambda(t) h+o(h) \\ \mathbb{P}\left(X_{t+h}=X_{t}\right) &=1-\lambda(t) h+o(h) \end{aligned}$$

  where the $o(h)$ terms are uniform in $t \in[0, \infty)$. Show that $X_{t}$ is a Poisson random variable with parameter $\Lambda(t)=\int_{0}^{t} \lambda(s) d s$.

  (iii) Let $X=\left(X_{n}: n=1,2, \ldots\right)$ be a sequence of independent and identically distributed positive random variables with continuous density function $f$. We define the sequence of successive records, $\left(K_{n}, n=0,1, \ldots\right)$, by $K_{0}:=0$ and, for $n \geqslant 0$,

  $$K_{n+1}:=\inf \left\{m>K_{n}: X_{m}>X_{K_{n}}\right\}$$

  The record process,$\left(R_{t}, t \geqslant 0\right)$, is then defined by

  $$R_{t}:=\#\left\{n \geqslant 1: X_{K_{n}} \leqslant t\right\}$$

  Explain why the increments of $R$ are independent. Show that $R_{t}$ is a Poisson random variable with parameter $-\log \{1-F(t)\}$ where $F(t)=\int_{0}^{t} f(s) d s$.

  [You may assume the following without proof: For fixed $t>0$, let $Y$ (respectively, $Z$ ) be the subsequence of $X$ obtained by retaining only those elements that are greater than (respectively, smaller than) $t$. Then $Y$ (respectively, $Z$ ) is a sequence of independent variables each having the distribution of $X_{1}$ conditioned on $X_{1}>t$ (respectively, $X_{1}<t$ ); and $Y$ and $Z$ are independent.]

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2013

  Define the Moran model. Describe briefly the infinite sites model of mutations.

  We henceforth consider a population with $N$ individuals evolving according to the rules of the Moran model. In addition we assume:

  • the allelic type of any individual at any time lies in a given countable state space $S$;

  • individuals are subject to mutations at constant rate $u=\theta / N$, independently of the population dynamics;

  • each time a mutation occurs, if the allelic type of the individual was $x \in S$, it changes to $y \in S$ with probability $P(x, y)$, where $P(x, y)$ is a given Markovian transition matrix on $S$ that is symmetric:

  $$P(x, y)=P(y, x) \quad(x, y \in S)$$

  (i) Show that, if two individuals are sampled at random from the population at some time $t$, then the time to their most recent common ancestor has an exponential distribution, with a parameter that you should specify.

  (ii) Let $\Delta+1$ be the total number of mutations that accumulate on the two branches separating these individuals from their most recent common ancestor. Show that $\Delta+1$ is a geometric random variable, and specify its probability parameter $p$.

  (iii) The first individual is observed to be of type $x \in S$. Explain why the probability that the second individual is also of type $x$ is

  $$\mathbb{P}\left(X_{\Delta}=x \mid X_{0}=x\right),$$

  where $\left(X_{n}, n \geqslant 0\right)$ is a Markov chain on $S$ with transition matrix $P$ and is independent of $\Delta$.

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2013

  (i) Define an $M / M / 1$ queue. Justifying briefly your answer, specify when this queue has a stationary distribution, and identify that distribution. State and prove Burke's theorem for this queue.

  (ii) Let $\left(L_{1}(t), \ldots, L_{N}(t), t \geqslant 0\right)$ denote a Jackson network of $N$ queues, where the entrance and service rates for queue $i$ are respectively $\lambda_{i}$ and $\mu_{i}$, and each customer leaving queue $i$ moves to queue $j$ with probability $p_{i j}$ after service. We assume $\sum_{j} p_{i j}<1$ for each $i=1, \ldots, N$; with probability $1-\sum_{j} p_{i j}$ a customer leaving queue $i$ departs from the system. State Jackson's theorem for this network. [You are not required to prove it.] Are the processes $\left(L_{1}(t), \ldots, L_{N}(t), t \geqslant 0\right)$ independent at equilibrium? Justify your answer.

  (iii) Let $D_{i}(t)$ be the process of final departures from queue $i$. Show that, at equilibrium, $\left(L_{1}(t), \ldots, L_{N}(t)\right)$ is independent of $\left(D_{i}(s), 1 \leqslant i \leqslant N, 0 \leqslant s \leqslant t\right)$. Show that, for each fixed $i=1, \ldots, N,\left(D_{i}(t), t \geqslant 0\right)$ is a Poisson process, and specify its rate.

  comment

2012

• Paper 1, Section II, $27 \mathrm{~K}$

  Applied Probability | Part II, 2012

  (a) Give the definition of a Poisson process $\left(N_{t}, t \geqslant 0\right)$ with rate $\lambda$, using its transition rates. Show that for each $t \geqslant 0$, the distribution of $N_{t}$ is Poisson with a parameter to be specified.

  Let $J_{0}=0$ and let $J_{1}, J_{2}, \ldots$ denote the jump times of $\left(N_{t}, t \geqslant 0\right)$. What is the distribution of $\left(J_{n+1}-J_{n}, n \geqslant 0\right) ?$ (You do not need to justify your answer.)

  (b) Let $n \geqslant 1$. Compute the joint probability density function of $\left(J_{1}, J_{2}, \ldots, J_{n}\right)$ given $\left\{N_{t}=n\right\}$. Deduce that, given $\left\{N_{t}=n\right\},\left(J_{1}, \ldots, J_{n}\right)$ has the same distribution as the nondecreasing rearrangement of $n$ independent uniform random variables on $[0, t]$.

  (c) Starting from time 0, passengers arrive on platform $9 \mathrm{~B}$ at King's Cross station, with constant rate $\lambda>0$, in order to catch a train due to depart at time $t>0$. Using the above results, or otherwise, find the expected total time waited by all passengers (the sum of all passengers' waiting times).

  comment

• Paper 2, Section II, K

  Applied Probability | Part II, 2012

  (a) A colony of bacteria evolves as follows. Let $X$ be a random variable with values in the positive integers. Each bacterium splits into $X$ copies of itself after an exponentially distributed time of parameter $\lambda>0$. Each of the $X$ daughters then splits in the same way but independently of everything else. This process keeps going forever. Let $Z_{t}$ denote the number of bacteria at time $t$. Specify the $Q$-matrix of the Markov chain $Z=\left(Z_{t}, t \geqslant 0\right)$. [It will be helpful to introduce $p_{n}=\mathbb{P}(X=n)$, and you may assume for simplicity that $\left.p_{0}=p_{1}=0 .\right]$

  (b) Using the Kolmogorov forward equation, or otherwise, show that if $u(t)=$ $\mathbb{E}\left(Z_{t} \mid Z_{0}=1\right)$, then $u^{\prime}(t)=\alpha u(t)$ for some $\alpha$ to be explicitly determined in terms of $X$. Assuming that $\mathbb{E}(X)<\infty$, deduce the value of $u(t)$ for all $t \geqslant 0$, and show that $Z$ does not explode. [You may differentiate series term by term and exchange the order of summation without justification.]

  (c) We now assume that $X=2$ with probability 1 . Fix $0<q<1$ and let $\phi(t)=\mathbb{E}\left(q^{Z_{t}} \mid Z_{0}=1\right)$. Show that $\phi$ satisfies

  $$\phi(t)=q e^{-\lambda t}+\int_{0}^{t} \lambda e^{-\lambda s} \phi(t-s)^{2} d s$$

  By making the change of variables $u=t-s$, show that $d \phi / d t=\lambda \phi(\phi-1)$. Deduce that for all $n \geqslant 1, \mathbb{P}\left(Z_{t}=n \mid Z_{0}=1\right)=\beta^{n-1}(1-\beta)$ where $\beta=1-e^{-\lambda t}$.

  comment

• Paper 3, Section II, K

  Applied Probability | Part II, 2012

  We consider a system of two queues in tandem, as follows. Customers arrive in the first queue at rate $\lambda$. Each arriving customer is immediately served by one of infinitely many servers at rate $\mu_{1}$. Immediately after service, customers join a single-server second queue which operates on a first-come, first-served basis, and has a service rate $\mu_{2}$. After service in this second queue, each customer returns to the first queue with probability $0<1-p<1$, and otherwise leaves the system forever. A schematic representation is given below:

  

  (a) Let $M_{t}$ and $N_{t}$ denote the number of customers at time $t$ in queues number 1 and 2 respectively, including those currently in service at time $t$. Give the transition rates of the Markov chain $\left(M_{t}, N_{t}\right)_{t \geqslant 0}$.

  (b) Write down an equation satisfied by any invariant measure $\pi$ for this Markov chain. Let $\alpha>0$ and $\beta \in(0,1)$. Define a measure $\pi$ by

  $$\pi(m, n):=e^{-\alpha} \frac{\alpha^{m}}{m !} \beta^{n}(1-\beta), \quad m, n \in\{0,1, \ldots\}$$

  Show that it is possible to find $\alpha>0, \beta \in(0,1)$ so that $\pi$ is an invariant measure of $\left(M_{t}, N_{t}\right)_{t \geqslant 0}$, if and only if $\lambda<\mu_{2} p$. Give the values of $\alpha$ and $\beta$ in this case.

  (c) Assume now that $\lambda p>\mu_{2}$. Show that the number of customers is not positive recurrent.

  [Hint. One way to solve the problem is as follows. Assume it is positive recurrent. Observe that $M_{t}$ is greater than a $M / M / \infty$ queue with arrival rate $\lambda$. Deduce that $N_{t}$ is greater than a $M / M / 1$ queue with arrival rate $\lambda p$ and service rate $\mu_{2}$. You may use without proof the fact that the departure process from the first queue is then, at equilibrium, a Poisson process with rate $\lambda$, and you may use without proof properties of thinned Poisson processes.]

  comment

• Paper 4, Section II, $26 K$

  Applied Probability | Part II, 2012

  (a) Define the Moran model and Kingman's $n$-coalescent. State and prove a theorem which describes the relationship between them. [You may use without proof a construction of the Moran model for all $-\infty<t<\infty$.]

  (b) Let $\theta>0$. Suppose that a population of $N \geqslant 2$ individuals evolves according to the rules of the Moran model. Assume also that each individual in the population undergoes a mutation at constant rate $u=\theta /(N-1)$. Each time a mutation occurs, we assume that the allelic type of the corresponding individual changes to an entirely new type, never seen before in the population. Let $p(\theta)$ be the homozygosity probability, i.e., the probability that two individuals sampled without replacement from the population have the same genetic type. Give an expression for $p(\theta)$.

  (c) Let $q(\theta)$ denote the probability that a sample of size $n$ consists of one allelic type (monomorphic population). Show that $q(\theta)=\mathbb{E}\left(\exp \left\{-(\theta / 2) L_{n}\right\}\right)$, where $L_{n}$ denotes the sum of all the branch lengths in the genealogical tree of the sample - that is, $L_{n}=\sum_{i=2}^{n} i\left(\tau_{i}-\tau_{i-1}\right)$, where $\tau_{i}$ is the first time that the genealogical tree of the sample has $i$ lineages. Deduce that

  $$q(\theta)=\frac{(n-1) !}{\prod_{i=1}^{n-1}(\theta+i)}$$

  comment

2011

• Paper 1, Section II, J

  Applied Probability | Part II, 2011

  (i) Let $X$ be a Markov chain with finitely many states. Define a stopping time and state the strong Markov property.

  (ii) Let $X$ be a Markov chain with state-space $\{-1,0,1\}$ and Q-matrix

  $$Q=\left(\begin{array}{ccc} -(q+\lambda) & \lambda & q \\ 0 & 0 & 0 \\ q & \lambda & -(q+\lambda) \end{array}\right), \text { where } q, \lambda>0$$

  Consider the integral $\int_{0}^{t} X(s) \mathrm{d} s$, the signed difference between the times spent by the chain at states $+1$ and $-1$ by time $t$, and let

  $$\begin{aligned} Y &=\sup \left[\int_{0}^{t} X(s) \mathrm{d} s: t>0\right] \\ \psi_{\pm}(c) &=\mathbb{P}\left(Y>c \mid X_{0}=\pm 1\right), \quad c>0 \end{aligned}$$

  Derive the equation

  $$\psi_{-}(c)=\int_{0}^{\infty} q e^{-(\lambda+q) u_{+}} \psi_{+}(c+u) \mathrm{d} u$$

  (iii) Obtain another equation relating $\psi_{+}$to $\psi_{-}$.

  (iv) Assuming that $\psi_{+}(c)=e^{-c A}, c>0$, where $A$ is a non-negative constant, calculate $A$.

  (v) Give an intuitive explanation why the function $\psi_{+}$must have the exponential form $\psi_{+}(c)=e^{-c A}$ for some $A$.

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2011

  (i) Explain briefly what is meant by saying that a continuous-time Markov chain $X(t)$ is a birth-and-death process with birth rates $\lambda_{i}>0, i \geqslant 0$, and death rates $\mu_{i}>0$, $i \geqslant 1$.

  (ii) In the case where $X(t)$ is recurrent, find a sufficient condition on the birth and death parameters to ensure that

  $$\lim _{t \rightarrow \infty} \mathbb{P}(X(t)=j)=\pi_{j}>0, \quad j \geqslant 0$$

  and express $\pi_{j}$ in terms of these parameters. State the reversibility property of $X(t)$.

  Jobs arrive according to a Poisson process of rate $\lambda>0$. They are processed individually, by a single server, the processing times being independent random variables, each with the exponential distribution of rate $\nu>0$. After processing, the job either leaves the system, with probability $p, 0<p<1$, or, with probability $1-p$, it splits into two separate jobs which are both sent to join the queue for processing again. Let $X(t)$ denote the number of jobs in the system at time $t$.

  (iii) In the case $1+\lambda / \nu<2 p$, evaluate $\lim _{t \rightarrow \infty} \mathbb{P}(X(t)=j), j=0,1, \ldots$, and find the expected time that the processor is busy between two successive idle periods.

  (iv) What happens if $1+\lambda / \nu \geqslant 2 p$ ?

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2011

  (i) Define an inhomogeneous Poisson process with rate function $\lambda(u)$.

  (ii) Show that the number of arrivals in an inhomogeneous Poisson process during the interval $(0, t)$ has the Poisson distribution with mean

  $$\int_{0}^{t} \lambda(u) \mathrm{d} u$$

  (iii) Suppose that $\Lambda=\{\Lambda(t), t \geqslant 0\}$ is a non-negative real-valued random process. Conditional on $\Lambda$, let $N=\{N(t), t \geqslant 0\}$ be an inhomogeneous Poisson process with rate function $\Lambda(u)$. Such a process $N$ is called a doubly-stochastic Poisson process. Show that the variance of $N(t)$ cannot be less than its mean.

  (iv) Now consider the process $M(t)$ obtained by deleting every odd-numbered point in an ordinary Poisson process of rate $\lambda$. Check that

  $$\mathbb{E} M(t)=\frac{2 \lambda t+e^{-2 \lambda t}-1}{4}, \quad \operatorname{Var} M(t)=\frac{4 \lambda t-8 \lambda t e^{-2 \lambda t}-e^{-4 \lambda t}+1}{16}$$

  Deduce that $M(t)$ is not a doubly-stochastic Poisson process.

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2011

  At an $\mathrm{M} / \mathrm{G} / 1$ queue, the arrival times form a Poisson process of rate $\lambda$ while service times $S_{1}, S_{2}, \ldots$ are independent of each other and of the arrival times and have a common distribution $G$ with mean $\mathbb{E} S_{1}<+\infty$.

  (i) Show that the random variables $Q_{n}$ giving the number of customers left in the queue at departure times form a Markov chain.

  (ii) Specify the transition probabilities of this chain as integrals in $\mathrm{d} G(t)$ involving parameter $\lambda$. [No proofs are needed.]

  (iii) Assuming that $\rho=\lambda \mathbb{E} S_{1}<1$ and the chain $\left(Q_{n}\right)$ is positive recurrent, show that its stationary distribution $\left(\pi_{k}, k \geqslant 0\right)$ has the generating function given by

  $$\sum_{k \geqslant 0} \pi_{k} s^{k}=\frac{(1-\rho)(s-1) g(s)}{s-g(s)},|s| \leqslant 1$$

  for an appropriate function $g$, to be specified.

  (iv) Deduce that, in equilibrium, $Q_{n}$ has the mean value

  $$\rho+\frac{\lambda^{2} \mathbb{E} S_{1}^{2}}{2(1-\rho)}$$

  comment

2010

• Paper 1, Section II, I

  Applied Probability | Part II, 2010

  (a) Define what it means to say that $\pi$ is an equilibrium distribution for a Markov chain on a countable state space with Q-matrix $Q=\left(q_{i j}\right)$, and give an equation which is satisfied by any equilibrium distribution. Comment on the possible non-uniqueness of equilibrium distributions.

  (b) State a theorem on convergence to an equilibrium distribution for a continuoustime Markov chain.

  A continuous-time Markov chain $\left(X_{t}, t \geqslant 0\right)$ has three states $1,2,3$ and the Qmatrix $Q=\left(q_{i j}\right)$ is of the form

  $$Q=\left(\begin{array}{ccc} -\lambda_{1} & \lambda_{1} / 2 & \lambda_{1} / 2 \\ \lambda_{2} / 2 & -\lambda_{2} & \lambda_{2} / 2 \\ \lambda_{3} / 2 & \lambda_{3} / 2 & -\lambda_{3} \end{array}\right)$$

  where the rates $\lambda_{1}, \lambda_{2}, \lambda_{3} \in[0, \infty)$ are not all zero.

  [Note that some of the $\lambda_{i}$ may be zero, and those cases may need special treatment.]

  (c) Find the equilibrium distributions of the Markov chain in question. Specify the cases of uniqueness and non-uniqueness.

  (d) Find the limit of the transition matrix $P(t)=\exp (t Q)$ when $t \rightarrow \infty$.

  (e) Describe the jump chain $\left(Y_{n}\right)$ and its equilibrium distributions. If $\widehat{P}$is the jump probability matrix, find the limit of $\widehat{P}^{n}$ as $n \rightarrow \infty$.

  comment

• Paper 2, Section II, I

  Applied Probability | Part II, 2010

  (a) Let $S_{k}$ be the sum of $k$ independent exponential random variables of rate $k \mu$. Compute the moment generating function $\phi_{S_{k}}(\theta)=\mathbb{E} e^{\theta S_{k}}$ of $S_{k}$. Show that, as $k \rightarrow \infty$, functions $\phi_{S_{k}}(\theta)$ converge to a limit. Describe the random variable $S$ for which the limiting function $\lim _{k \rightarrow \infty} \phi_{S_{k}}(\theta)$ coincides with $\mathbb{E} e^{\theta S}$.

  (b) Define the $M / G / 1$ queue with infinite capacity (sometimes written $M / G / 1 / \infty$ ). Introduce the embedded discrete-time Markov chain $\left(X_{n}\right)$ and write down the recursive relation between $X_{n}$ and $X_{n-1}$.

  Consider, for each fixed $k$ and for $0<\lambda<\mu$, an $\mathrm{M} / \mathrm{G} / 1 / \infty$ queue with arrival rate $\lambda$ and with service times distributed as $S_{k}$. Assume that the queue is empty at time 0 . Let $T_{k}$ be the earliest time at which a customer departs leaving the queue empty. Let $A$ be the first arrival time and $B_{k}=T_{k}-A$ the length of the busy period.

  (c) Prove that the moment generating functions $\phi_{B_{k}}(\theta)=\mathbb{E} e^{\theta B_{k}}$ and $\phi_{S_{k}}(\theta)$ are related by the equation

  $$\phi_{B_{k}}(\theta)=\phi_{S_{k}}\left(\theta-\lambda\left(1-\phi_{B_{k}}(\theta)\right)\right)$$

  (d) Prove that the moment generating functions $\phi_{T_{k}}(\theta)=\mathbb{E} e^{\theta T_{k}}$ and $\phi_{S_{k}}(\theta)$ are related by the equation

  $$\frac{\lambda-\theta}{\lambda} \phi_{T_{k}}(\theta)=\phi_{S_{k}}\left((\lambda-\theta)\left(\phi_{T_{k}}(\theta)-1\right)\right)$$

  (e) Assume that, for all $\theta<\lambda$,

  $$\lim _{k \rightarrow \infty} \phi_{B_{k}}(\theta)=\mathbb{E} e^{\theta B}, \quad \lim _{k \rightarrow \infty} \phi_{T_{k}}(\theta)=\mathbb{E} e^{\theta T},$$

  for some random variables $B$ and $T$. Calculate $\mathbb{E} B$ and $\mathbb{E} T$. What service time distribution do these values correspond to?

  comment

• Paper 3, Section II, I

  Applied Probability | Part II, 2010

  Cars looking for a parking space are directed to one of three unlimited parking lots A, B and C. First, immediately after the entrance, the road forks: one direction is to lot A, the other to B and C. Shortly afterwards, the latter forks again, between B and C. See the diagram below.

  

  The policeman at the first road fork directs an entering car with probability $1 / 3$ to A and with probability $2 / 3$ to the second fork. The policeman at the second fork sends the passing cars to $\mathrm{B}$ or $\mathrm{C}$ alternately: cars $1,3,5, \ldots$ approaching the second fork go to $\mathrm{B}$ and cars $2,4,6, \ldots$ to $\mathrm{C}$.

  Assuming that the total arrival process $(N(t))$ of cars is Poisson of rate $\lambda$, consider the processes $\left(X^{\mathrm{A}}(t)\right),\left(X^{\mathrm{B}}(t)\right)$ and $\left(X^{\mathrm{C}}(t)\right), t \geqslant 0$, where $X^{i}(t)$ is the number of cars directed to lot $i$ by time $t$, for $i=\mathrm{A}, \mathrm{B}, \mathrm{C}$. The times for a car to travel from the first to the second fork, or from a fork to the parking lot, are all negligible.

  (a) Characterise each of the processes $\left(X^{\mathrm{A}}(t)\right),\left(X^{\mathrm{B}}(t)\right)$ and $\left(X^{\mathrm{C}}(t)\right)$, by specifying if it is (i) Poisson, (ii) renewal or (iii) delayed renewal. Correspondingly, specify the rate, the holding-time distribution and the distribution of the delay.

  (b) In the case of a renewal process, determine the equilibrium delay distribution.

  (c) Given $s, t>0$, write down explicit expressions for the probability $\mathbb{P}\left(X^{i}(s)=X^{i}(s+t)\right)$ that the interval $(s, t+s)$ is free of points in the corresponding process, $i=\mathrm{A}, \mathrm{B}, \mathrm{C}$.

  comment

• Paper 4, Section II, I

  Applied Probability | Part II, 2010

  (a) Let $\left(X_{t}\right)$ be an irreducible continuous-time Markov chain on a finite or countable state space. What does it mean to say that the chain is (i) transient, (ii) recurrent, (iii) positive recurrent, (iv) null recurrent? What is the relation between equilibrium distributions and properties (iii) and (iv)?

  A population of microorganisms develops in continuous time; the size of the population is a Markov chain $\left(X_{t}\right)$ with states $0,1,2, \ldots$ Suppose $X_{t}=n$. It is known that after a short time $s$, the probability that $X_{t}$ increased by one is $\lambda(n+1) s+o(s)$ and (if $n \geqslant 1$ ) the probability that the population was exterminated between times $t$ and $t+s$ and never revived by time $t+s$ is $\mu s+o(s)$. Here $\lambda$ and $\mu$ are given positive constants. All other changes in the value of $X_{t}$ have a combined probability $o(s)$.

  (b) Write down the Q-matrix of Markov chain $\left(X_{t}\right)$ and determine if $\left(X_{t}\right)$ is irreducible. Show that $\left(X_{t}\right)$ is non-explosive. Determine the jump chain.

  (c) Now assume that

  $$\mu=\lambda$$

  Determine whether the chain is transient or recurrent, and in the latter case whether it is positive or null recurrent. Answer the same questions for the jump chain. Justify your answers.

  comment

2009

• Paper 1, Section II, J

  Applied Probability | Part II, 2009

  (a) Let $\left(X_{t}, t \geqslant 0\right)$ be a continuous-time Markov chain on a countable state space I. Explain what is meant by a stopping time for the chain $\left(X_{t}, t \geqslant 0\right)$. State the strong Markov property. What does it mean to say that $X$ is irreducible?

  (b) Let $\left(X_{t}, t \geqslant 0\right)$ be a Markov chain on $I=\{0,1, \ldots\}$ with $Q$-matrix given by $Q=\left(q_{i, j}\right)_{i, j \in I}$ such that:

  (1) $q_{i, 0}>0$ for all $i \geqslant 1$, but $q_{0, j}=0$ for all $j \in I$, and

  (2) $q_{i, i+1}>0$ for all $i \geqslant 1$, but $q_{i, j}=0$ if $j>i+1$.

  Is $\left(X_{t}, t \geqslant 0\right)$ irreducible? Fix $M \geqslant 1$, and assume that $X_{0}=i$, where $1 \leqslant i \leqslant M$. Show that if $J_{1}=\inf \left\{t \geqslant 0: X_{t} \neq X_{0}\right\}$ is the first jump time, then there exists $\delta>0$ such that $\mathbb{P}_{i}\left(X_{J_{1}}=0\right) \geqslant \delta$, uniformly over $1 \leqslant i \leqslant M$. Let $T_{0}=0$ and define recursively for $m \geqslant 0$,

  $$T_{m+1}=\inf \left\{t \geqslant T_{m}: X_{t} \neq X_{T_{m}} \text { and } 1 \leqslant X_{t} \leqslant M\right\}$$

  Let $A_{m}$ be the event $A_{m}=\left\{T_{m}<\infty\right\}$. Show that $\mathbb{P}_{i}\left(A_{m}\right) \leqslant(1-\delta)^{m}$, for $1 \leqslant i \leqslant M$.

  (c) Let $\left(X_{t}, t \geqslant 0\right)$ be the Markov chain from (b). Define two events $E$ and $F$ by

  $$E=\left\{X_{t}=0 \text { for all } t \text { large enough }\right\}, \quad F=\left\{\lim _{t \rightarrow \infty} X_{t}=+\infty\right\}$$

  Show that $\mathbb{P}_{i}(E \cup F)=1$ for all $i \in I$.

  comment

• Paper 2, Section II, J

  Applied Probability | Part II, 2009

  Let $X_{1}, X_{2}, \ldots$, be a sequence of independent, identically distributed positive random variables, with a common probability density function $f(x), x>0$. Call $X_{n}$ a record value if $X_{n}>\max \left\{X_{1}, \ldots, X_{n-1}\right\}$. Consider the sequence of record values

  $$V_{0}=0, V_{1}=X_{1}, \ldots, V_{n}=X_{i_{n}},$$

  where

  $$i_{n}=\min \left\{i \geqslant 1: X_{i}>V_{n-1}\right\}, n>1 .$$

  Define the record process $\left(R_{t}\right)_{t \geqslant 0}$ by $R_{0}=0$ and

  $$R_{t}=\max \left\{n \geqslant 1: V_{n}<t\right\}, \quad t>0$$

  (a) By induction on $n$, or otherwise, show that the joint probability density function of the random variables $V_{1}, \ldots, V_{n}$ is given by:

  $$f_{V_{1}, \ldots, V_{n}}\left(x_{1}, \ldots, x_{n}\right)=f\left(x_{1}\right) \frac{f\left(x_{2}\right)}{1-F\left(x_{1}\right)} \times \ldots \times \frac{f\left(x_{n}\right)}{1-F\left(x_{n-1}\right)},$$

  where $F(x)=\int_{0}^{x} f(y) \mathrm{d} y$ is the cumulative distribution function for $f(x)$.

  (b) Prove that the random variable $R_{t}$ has a Poisson distribution with parameter $\Lambda(t)$ of the form

  $$\Lambda(t)=\int_{0}^{t} \lambda(s) \mathrm{d} s,$$

  and determine the 'instantaneous rate' $\lambda(s)$.

  [Hint: You may use the formula

  $$\begin{aligned} &\mathbb{P}\left(R_{t}=k\right)=\mathbb{P}\left(V_{k} \leqslant t<V_{k+1}\right) \\ &=\int_{0}^{t} \ldots \int_{0}^{t} \mathbf{1}_{\left\{t_{1}<\ldots<t_{k}\right\}} f_{V_{1}, \ldots, V_{k}}\left(t_{1}, \ldots, t_{k}\right) \\ &\quad \times \mathbb{P}\left(V_{k+1}>t \mid V_{1}=t_{1}, \ldots, V_{k}=t_{k}\right) \prod_{j=1}^{k} \mathrm{~d} t_{j}, \end{aligned}$$

  for any $k \geqslant 1 .]$

  comment

• Paper 3, Section II, J

  Applied Probability | Part II, 2009

  (a) Define the Poisson process $\left(N_{t}, t \geqslant 0\right)$ with rate $\lambda>0$, in terms of its holding times. Show that for all times $t \geqslant 0, N_{t}$ has a Poisson distribution, with a parameter which you should specify.

  (b) Let $X$ be a random variable with probability density function

  $$f(x)=\frac{1}{2} \lambda^{3} x^{2} e^{-\lambda x} \mathbf{1}_{\{x>0\}} .$$

  Prove that $X$ is distributed as the sum $Y_{1}+Y_{2}+Y_{3}$ of three independent exponential random variables of rate $\lambda$. Calculate the expectation, variance and moment generating function of $X$.

  Consider a renewal process $\left(X_{t}, t \geqslant 0\right)$ with holding times having density $(*)$. Prove that the renewal function $m(t)=\mathbb{E}\left(X_{t}\right)$ has the form

  $$m(t)=\frac{\lambda t}{3}-\frac{1}{3} p_{1}(t)-\frac{2}{3} p_{2}(t)$$

  where $p_{1}(t)=\mathbb{P}\left(N_{t}=1 \bmod 3\right), p_{2}(t)=\mathbb{P}\left(N_{t}=2 \bmod 3\right)$ and $\left(N_{t}, t \geqslant 0\right)$ is the Poisson process of rate $\lambda$.

  (c) Consider the delayed renewal process $\left(X_{t}^{\mathrm{D}}, t \geqslant 0\right)$ with holding times $S_{1}^{\mathrm{D}}, S_{2}, S_{3}, \ldots$ where $\left(S_{n}, n \geqslant 1\right)$, are the holding times of $\left(X_{t}, t \geqslant 0\right)$ from (b). Specify the distribution of $S_{1}^{\mathrm{D}}$ for which the delayed process becomes the renewal process in equilibrium.

  [You may use theorems from the course provided that you state them clearly.]

  comment

• Paper 4, Section II, J

  Applied Probability | Part II, 2009

  A flea jumps on the vertices of a triangle $A B C$; its position is described by a continuous time Markov chain with a $Q$-matrix

  $$Q=\left(\begin{array}{ccc} -1 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 0 & -1 \end{array}\right) \quad \begin{aligned} &A \\ &B \\ &C \end{aligned}$$

  (a) Draw a diagram representing the possible transitions of the flea together with the rates of each of these transitions. Find the eigenvalues of $Q$ and express the transition probabilities $p_{x y}(t), x, y=A, B, C$, in terms of these eigenvalues.

  [Hint: $\operatorname{det}(Q-\mu \mathbf{I})=(-1-\mu)^{3}+1$. Specifying the equilibrium distribution may help.]

  Hence specify the probabilities $\mathbb{P}\left(N_{t}=i \bmod 3\right)$ where $\left(N_{t}, t \geqslant 0\right)$ is a Poisson process of rate $1 .$

  (b) A second flea jumps on the vertices of the triangle $A B C$ as a Markov chain with Q-matrix

  $$Q^{\prime}=\left(\begin{array}{ccc} -\rho & 0 & \rho \\ \rho & -\rho & 0 \\ 0 & \rho & -\rho \end{array}\right) \quad \begin{aligned} &A \\ &B \\ &C \end{aligned}$$

  where $\rho>0$ is a given real number. Let the position of the second flea at time $t$ be denoted by $Y_{t}$. We assume that $\left(Y_{t}, t \geqslant 0\right)$ is independent of $\left(X_{t}, t \geqslant 0\right)$. Let $p(t)=\mathbb{P}\left(X_{t}=Y_{t}\right)$. Show that $\lim _{t \rightarrow \infty} p(t)$ exists and is independent of the starting points of $X$ and $Y$. Compute this limit.

  comment

2008

• 1.II.26I

  Applied Probability | Part II, 2008

  Let $\left(X_{t}, t \geqslant 0\right)$ be an irreducible continuous-time Markov chain with initial probability distribution $\pi$ and Q-matrix $Q$ (for short: a $(\pi, Q)$ CTMC), on a finite state space $I$.

  (i) Define the terms reversible CTMC and detailed balance equations (DBEs) and explain, without proof, the relation between them.

  (ii) Prove that any solution of the DBEs is an equilibrium distribution (ED) for $\left(X_{t}\right)$.

  Let $\left(Y_{n}, n=0,1, \ldots\right)$ be an irreducible discrete-time Markov chain with initial probability distribution $\widehat{\pi}$and transition probability matrix $\widehat{P}$(for short: a $(\widehat{\pi}, \widehat{P})$ DTMC), on the state space $I$.

  (iii) Repeat the two definitions from (i) in the context of the DTMC $\left(Y_{n}\right)$. State also in this context the relation between them, and prove a statement analogous to (ii).

  (iv) What does it mean to say that $\left(Y_{n}\right)$ is the jump chain for $\left(X_{t}\right)$ ? State and prove a relation between the ED $\pi$ for the $\operatorname{CTMC}\left(X_{t}\right)$ and the ED $\widehat{\pi}$for its jump chain $\left(Y_{n}\right)$.

  (v) Prove that $\left(X_{t}\right)$ is reversible (in equilibrium) if and only if its jump chain $\left(Y_{n}\right)$ is reversible (in equilibrium).

  (vi) Consider now a continuous time random walk on a graph. More precisely, consider a CTMC $\left(X_{t}\right)$ on an undirected graph, where some pairs of states $i, j \in I$ are joined by one or more non-oriented 'links' $e_{i j}(1), \ldots, e_{i j}\left(m_{i j}\right)$. Here $m_{i j}=m_{j i}$ is the number of links between $i$ and $j$. Assume that the jump rate $q_{i j}$ is proportional to $m_{i j}$. Can the chain $\left(X_{t}\right)$ be reversible? Identify the corresponding jump chain $\left(Y_{n}\right)$ (which determines a discrete-time random walk on the graph) and comment on its reversibility.

  comment

• 2.II.26I

  Applied Probability | Part II, 2008

  Consider a continuous-time Markov chain $\left(X_{t}\right)$ given by the diagram below.

  

  We will assume that the rates $\alpha, \beta, \lambda$ and $\mu$ are all positive.

  (a) Is the chain $\left(X_{t}\right)$ irreducible?

  (b) Write down the standard equations for the hitting probabilities

  $$h_{\mathrm{C} i}=\mathbb{P}_{\mathrm{C} i}(\text { hit W0) }, \quad i \geqslant 0,$$

  and

  $$h_{\mathrm{W} i}=\mathbb{P}_{\mathrm{W} i}(\text { hit W0) }, \quad i \geqslant 1 .$$

  Explain how to identify the probabilities $h_{\mathrm{C} i}$ and $h_{\mathrm{W} i}$ among the solutions to these equations.

  [You should state the theorem you use but its proof is not required.]

  (c) Set $h^{(i)}=\left(\begin{array}{c}h_{\mathrm{C} i} \\ h_{\mathrm{W} i}\end{array}\right)$ and find a matrix $A$ such that

  $$h^{(i)}=A h^{(i-1)}, \quad i=1,2, \ldots$$

  The recursion matrix $A$ has a 'standard' eigenvalue and a 'standard' eigenvector that do not depend on the transition rates: what are they and why are they always present?

  (d) Calculate the second eigenvalue $\vartheta$ of the matrix $A$, and the corresponding eigenvector, in the form $\left(\begin{array}{l}b \\ 1\end{array}\right)$, where $b>0$.

  (e) Suppose the second eigenvalue $\vartheta$ is $\geqslant 1$. What can you say about $h_{\mathrm{C} i}$ and $h_{\mathrm{W} i}$ ? Is the chain $\left(X_{t}\right)$ transient or recurrent? Justify your answer.

  (f) Now assume the opposite: the second eigenvalue $\vartheta$ is $<1$. Check that in this case $b<1$. Is the chain transient or recurrent under this condition?

  (g) Finally, specify, by means of inequalities between the parameters $\alpha, \beta, \lambda$ and $\mu$, when the chain $\left(X_{t}\right)$ is recurrent and when it is transient.

  comment

• 3.II.25I

  Applied Probability | Part II, 2008

  Let $\left(X_{t}\right)$ be an irreducible continuous-time Markov chain with countably many states. What does it mean to say the chain is (i) positive recurrent, (ii) null recurrent? Consider the chain $\left(X_{t}\right)$ with the arrow diagram below.

  

  In this question we analyse the existence of equilibrium probabilities $\pi_{i \mathrm{C}}$ and $\pi_{i \mathrm{~W}}$ of the chain $\left(X_{t}\right)$ being in state $i \mathrm{C}$ or $i \mathrm{~W}, i=0,1, \ldots$, and the impact of this fact on positive and null recurrence of the chain.

  (a) Write down the invariance equations $\pi Q=0$ and check that they have the form

  $$\begin{aligned} \pi_{0 C} &=\frac{\beta}{\lambda+\alpha} \pi_{0 \mathrm{~W}}, \\ \left(\pi_{1 \mathrm{C}}, \pi_{1 \mathrm{~W}}\right) &=\frac{\beta \pi_{0 \mathrm{~W}}}{\lambda+\alpha}\left(\frac{\lambda(\mu+\beta)}{\mu(\lambda+\alpha)}, \frac{\lambda}{\mu}\right) \\ \left(\pi_{(i+1) \mathrm{C}}, \pi_{(i+1) \mathrm{W}}\right) &=\left(\pi_{i \mathrm{C}}, \pi_{i \mathrm{~W}}\right) B, \quad i=1,2, \ldots, \end{aligned}$$

  where $B$ is a $2 \times 2$ recursion matrix:

  $$B=\left(\begin{array}{cc} \frac{\lambda \mu-\beta \alpha}{\mu(\lambda+\alpha)} & -\frac{\alpha}{\mu} \\ \frac{\beta(\beta+\mu)}{\mu(\lambda+\alpha)} & \frac{\beta+\mu}{\mu} \end{array}\right)$$

  (b) Verify that the row vector $\left(\pi_{1 \mathrm{C}}, \pi_{1 \mathrm{~W}}\right)$ is an eigenvector of $B$ with the eigenvalue $\theta$ where

  $$\theta=\frac{\lambda(\mu+\beta)}{\mu(\lambda+\alpha)}$$

  Hence, specify the form of equilibrium probabilities $\pi_{i \mathrm{C}}$ and $\pi_{i \mathrm{~W}}$ and conclude that the chain $\left(X_{t}\right)$ is positive recurrent if and only if $\mu \alpha>\lambda \beta$.

  comment

• 4.II.26I

  Applied Probability | Part II, 2008

  On a hot summer night, opening my window brings some relief. This attracts hordes of mosquitoes who manage to negotiate a dense window net. But, luckily, I have a mosquito trapping device in my room.

  Assume the mosquitoes arrive in a Poisson process at rate $\lambda$; afterwards they wander around for independent and identically distributed random times with a finite mean $\mathbb{E} S$, where $S$ denotes the random wandering time of a mosquito, and finally are trapped by the device.

  (a) Identify a mathematical model, which was introduced in the course, for the number of mosquitoes present in the room at times $t \geqslant 0$.

  (b) Calculate the distribution of $Q(t)$ in terms of $\lambda$ and the tail probabilities $\mathbb{P}(S>x)$ of the wandering time $S$, where $Q(t)$ is the number of mosquitoes in the room at time $t>0$ (assuming that at the initial time, $Q(0)=0$ ).

  (c) Write down the distribution for $Q^{\mathrm{E}}$, the number of mosquitoes in the room in equilibrium, in terms of $\lambda$ and $\mathbb{E} S$.

  (d) Instead of waiting for the number of mosquitoes to reach equilibrium, I close the window at time $t>0$. For $v \geqslant 0$ let $X(t+v)$ be the number of mosquitoes left at time $t+v$, i.e. $v$ time units after closing the window. Calculate the distribution of $X(t+v)$.

  (e) Let $V(t)$ be the time needed to trap all mosquitoes in the room after closing the window at time $t>0$. By considering the event $\{X(t+v) \geqslant 1\}$, or otherwise, compute $\mathbb{P}[V(t)>v]$.

  (f) Now suppose that the time $t$ at which I shut the window is very large, so that I can assume that the number of mosquitoes in the room has the distribution of $Q^{E}$. Let $V^{E}$ be the further time needed to trap all mosquitoes in the room. Show that

  $$\mathbb{P}\left[V^{E}>v\right]=1-\exp \left(-\lambda \mathbb{E}\left[(S-v)_{+}\right]\right),$$

  where $x_{+} \equiv \max (x, 0)$.

  comment

2007

• 1.II.26J

  Applied Probability | Part II, 2007

  An open air rock concert is taking place in beautiful Pine Valley, and enthusiastic fans from the entire state of Alifornia are heading there long before the much anticipated event. The arriving cars have to be directed to one of three large (practically unlimited) parking lots, $a, b$ and $c$ situated near the valley entrance. The traffic cop at the entrance to the valley decides to direct every third car (in the order of their arrival) to a particular lot. Thus, cars $1,4,7,10$ and so on are directed to lot $a$, cars $2,5,8,11$ to lot $b$ and cars $3,6,9,12$ to lot $c$.

  Suppose that the total arrival process $N(t), t \geqslant 0$, at the valley entrance is Poisson, of rate $\lambda>0$ (the initial time $t=0$ is taken to be considerably ahead of the actual event). Consider the processes $X^{a}(t), X^{b}(t)$ and $X^{c}(t)$ where $X^{i}(t)$ is the number of cars arrived in lot $i$ by time $t, i=a, b, c$. Assume for simplicity that the time to reach a parking lot from the entrance is negligible so that the car enters its specified lot at the time it crosses the valley entrance.

  (a) Give the probability density function of the time of the first arrival in each of the processes $X^{a}(t), X^{b}(t), X^{c}(t)$.

  (b) Describe the distribution of the time between two subsequent arrivals in each of these processes. Are these times independent? Justify your answer.

  (c) Which of these processes are delayed renewal processes (where the distribution of the first arrival time differs from that of the inter-arrival time)?

  (d) What are the corresponding equilibrium renewal processes?

  (e) Describe how the direction rule should be changed for $X^{a}(t), X^{b}(t)$ and $X^{c}(t)$ to become Poisson processes, of rate $\lambda / 3$. Will these Poisson processes be independent? Justify your answer.

  comment

• 2.II.26J

  Applied Probability | Part II, 2007

  In this question we work with a continuous-time Markov chain where the rate of jump $i \rightarrow j$ may depend on $j$ but not on $i$. A virus can be in one of $s$ strains $1, \ldots, s$, and it mutates to strain $j$ with rate $r_{j} \geqslant 0$ from each strain $i \neq j$. (Mutations are caused by the chemical environment.) Set $R=r_{1}+\ldots+r_{s}$.

  (a) Write down the Q-matrix (the generator) of the chain $\left(X_{t}\right)$ in terms of $r_{j}$ and $R$.

  (b) If $R=0$, that is, $r_{1}=\ldots=r_{s}=0$, what are the communicating classes of the chain $\left(X_{t}\right)$ ?

  (c) From now on assume that $R>0$. State and prove a necessary and sufficient condition, in terms of the numbers $r_{j}$, for the chain $\left(X_{t}\right)$ to have a single communicating class (which therefore should be closed).

  (d) In general, what is the number of closed communicating classes in the chain $\left(X_{t}\right)$ ? Describe all open communicating classes of $\left(X_{t}\right)$.

  (e) Find the equilibrium distribution of $\left(X_{t}\right)$. Is the chain $\left(X_{t}\right)$ reversible? Justify your answer.

  (f) Write down the transition matrix $\widehat{P}=\left(\widehat{p}_{i j}\right)$ of the discrete-time jump chain for $\left(X_{t}\right)$ and identify its equilibrium distribution. Is the jump chain reversible? Justify your answer.

  comment

• 3.II.25J

  Applied Probability | Part II, 2007

  For a discrete-time Markov chain, if the probability of transition $i \rightarrow j$ does not depend on $i$ then the chain is reduced to a sequence of independent random variables (states). In this case, the chain forgets about its initial state and enters equilibrium after a single transition. In the continuous-time case, a Markov chain whose rates $q_{i j}$ of transition $i \rightarrow j$ depend on $j$ but not on $i \neq j$ still 'remembers' its initial state and reaches equilibrium only in the limit as the time grows indefinitely. This question is an illustration of this property.

  A protean sea sponge may change its colour among $s$ varieties $1, \ldots, s$, under the influence of the environment. The rate of transition from colour $i$ to $j$ equals $r_{j} \geqslant 0$ and does not depend on $i, i \neq j$. Consider a Q-matrix $Q=\left(q_{i j}\right)$ with entries

  $$q_{i j}= \begin{cases}r_{j}, & i \neq j \\ -R+r_{i}, & i=j\end{cases}$$

  where $R=r_{1}+\ldots+r_{s}$. Assume that $R>0$ and let $\left(X_{t}\right)$ be the continuous-time Markov chain with generator $Q$. Given $t \geqslant 0$, let $P(t)=\left(p_{i j}(t)\right)$ be the matrix of transition probabilities in time $t$ in chain $\left(X_{t}\right)$.

  (a) State the exponential relation between the matrices $Q$ and $P(t)$.

  (b) Set $\pi_{j}=r_{j} / R, j=1, \ldots, s$. Check that $\pi_{1}, \ldots, \pi_{s}$ are equilibrium probabilities for the chain $\left(X_{t}\right)$. Is this a unique equilibrium distribution? What property of the vector with entries $\pi_{j}$ relative to the matrix $Q$ is involved here?

  (c) Let $\mathbf{x}$ be a vector with components $x_{1}, \ldots, x_{s}$ such that $x_{1}+\ldots+x_{s}=0$. Show that $\mathbf{x}^{\mathrm{T}} Q=-R \mathbf{x}^{\mathrm{T}}$. Compute $\mathbf{x}^{\mathrm{T}} P(t)$

  (d) Now let $\delta_{i}$ denote the (column) vector whose entries are 0 except for the $i$ th one which equals 1. Observe that the $i$ th row of $P(t)$ is $\delta_{i}^{\mathrm{T}} P(t)$. Prove that $\delta_{i}^{\mathrm{T}} P(t)=\pi^{\mathrm{T}}+e^{-t R}\left(\delta_{i}^{\mathrm{T}}-\pi^{\mathrm{T}}\right) .$

  (e) Deduce the expression for transition probabilities $p_{i j}(t)$ in terms of rates $r_{j}$ and their sum $R$.

  comment

• 4.II.26J

  Applied Probability | Part II, 2007

  A population of rare Monarch butterflies functions as follows. At the times of a Poisson process of rate $\lambda$ a caterpillar is produced from an egg. After an exponential time, the caterpillar is transformed into a pupa which, after an exponential time, becomes a butterfly. The butterfly lives for another exponential time and then dies. (The Poissonian assumption reflects the fact that butterflies lay a huge number of eggs most of which do not develop.) Suppose that all lifetimes are independent (of the arrival process and of each other) and let their rate be $\mu$. Assume that the population is in an equilibrium and let $C$ be the number of caterpillars, $R$ the number of pupae and $B$ the number of butterflies (so that the total number of insects, in any metamorphic form, equals $N=C+R+B)$. Let $\pi_{(c, r, b)}$ be the equilibrium probability $\mathbb{P}(C=c, R=r, B=b)$ where $c, r, b=0,1, \ldots$

  (a) Specify the rates of transitions $(c, r, b) \rightarrow\left(c^{\prime}, r^{\prime}, b^{\prime}\right)$ for the resulting continuous-time Markov chain $\left(X_{t}\right)$ with states $(c, r, b)$. (The rates are non-zero only when $c^{\prime}=c$ or $c^{\prime}=c \pm 1$ and similarly for other co-ordinates.) Check that the holding rate for state $(c, r, b)$ is $\lambda+\mu n$ where $n=c+r+b$.

  (b) Let $Q$ be the Q-matrix from (a). Consider the invariance equation $\pi Q=0$. Verify that the only solution is

  $$\pi_{(c, r, b)}=\frac{(3 \lambda / \mu)^{n}}{3^{n} c ! r ! b !} \exp \left(-\frac{3 \lambda}{\mu}\right), \quad n=c+r+b$$

  (c) Derive the marginal equilibrium probabilities $\mathbb{P}(N=n)$ and the conditional equilibrium probabilities $\mathbb{P}(C=c, R=r, B=b \mid N=n)$.

  (d) Determine whether the chain $\left(X_{t}\right)$ is positive recurrent, null-recurrent or transient.

  (e) Verify that the equilibrium probabilities $\mathbb{P}(N=n)$ are the same as in the corresponding $M / G I / \infty$ system (with the correct specification of the arrival rate and the service-time distribution).

  comment

2006

• 1.II.26J

  Applied Probability | Part II, 2006

  (a) What is a $Q$-matrix? What is the relationship between the transition matrix $P(t)$ of a continuous time Markov process and its generator $Q$ ?

  (b) A pond has three lily pads, labelled 1, 2, and 3. The pond is also the home of a frog that hops from pad to pad in a random fashion. The position of the frog is a continuous time Markov process on $\{1,2,3\}$ with generator

  $$Q=\left(\begin{array}{ccc} -1 & 1 & 0 \\ 1 & -2 & 1 \\ 1 & 0 & -1 \end{array}\right)$$

  Sketch an arrow diagram corresponding to $Q$ and determine the communicating classes. Find the probability that the frog is on pad 2 in equilibrium. Find the probability that the frog is on pad 2 at time $t$ given that the frog is on pad 1 at time 0 .

  comment

• 2.II.26J

  Applied Probability | Part II, 2006

  (a) Define a renewal process $\left(X_{t}\right)$ with independent, identically-distributed holding times $S_{1}, S_{2}, \ldots .$ State without proof the strong law of large numbers for $\left(X_{t}\right)$. State without proof the elementary renewal theorem for the mean value $m(t)=\mathbb{E} X_{t}$.

  (b) A circular bus route consists of ten bus stops. At exactly 5am, the bus starts letting passengers in at the main bus station (stop 1). It then proceeds to stop 2 where it stops to let passengers in and out. It continues in this fashion, stopping at stops 3 to 10 in sequence. After leaving stop 10, the bus heads to stop 1 and the cycle repeats. The travel times between stops are exponentially distributed with mean 4 minutes, and the time required to let passengers in and out at each stop are exponentially distributed with mean 1 minute. Calculate approximately the average number of times the bus has gone round its route by $1 \mathrm{pm}$.

  When the driver's shift finishes, at exactly $1 \mathrm{pm}$, he immediately throws all the passengers off the bus if the bus is already stopped, or otherwise, he drives to the next stop and then throws the passengers off. He then drives as fast as he can round the rest of the route to the main bus station. Giving reasons but not proofs, calculate approximately the average number of stops he will drive past at the end of his shift while on his way back to the main bus station, not including either the stop at which he throws off the passengers or the station itself.

  comment

• 3.II.25J

  Applied Probability | Part II, 2006

  A passenger plane with $N$ numbered seats is about to take off; $N-1$ seats have already been taken, and now the last passenger enters the cabin. The first $N-1$ passengers were advised by the crew, rather imprudently, to take their seats completely at random, but the last passenger is determined to sit in the place indicated on his ticket. If his place is free, he takes it, and the plane is ready to fly. However, if his seat is taken, he insists that the occupier vacates it. In this case the occupier decides to follow the same rule: if the free seat is his, he takes it, otherwise he insists on his place being vacated. The same policy is then adopted by the next unfortunate passenger, and so on. Each move takes a random time which is exponentially distributed with mean $\mu^{-1}$. What is the expected duration of the plane delay caused by these displacements?

  comment

• 4.II.26J

  Applied Probability | Part II, 2006

  (a) Let $\left(N_{t}\right)_{t \geqslant 0}$ be a Poisson process of rate $\lambda>0$. Let $p$ be a number between 0 and 1 and suppose that each jump in $\left(N_{t}\right)$ is counted as type one with probability $p$ and type two with probability $1-p$, independently for different jumps and independently of the Poisson process. Let $M_{t}^{(1)}$ be the number of type-one jumps and $M_{t}^{(2)}=N_{t}-M_{t}^{(1)}$ the number of type-two jumps by time $t$. What can you say about the pair of processes $\left(M_{t}^{(1)}\right)_{t \geqslant 0}$ and $\left(M_{t}^{(2)}\right)_{t \geqslant 0}$ ? What if we fix probabilities $p_{1}, \ldots, p_{m}$ with $p_{1}+\ldots+p_{m}=1$ and consider $m$ types instead of two?

  (b) A person collects coupons one at a time, at jump times of a Poisson process $\left(N_{t}\right)_{t \geqslant 0}$ of rate $\lambda$. There are $m$ types of coupons, and each time a coupon of type $j$ is obtained with probability $p_{j}$, independently of the previously collected coupons and independently of the Poisson process. Let $T$ be the first time when a complete set of coupon types is collected. Show that

  $$\mathbb{P}(T<t)=\prod_{j=1}^{m}\left(1-e^{-p_{j} \lambda t}\right)$$

  Let $L=N_{T}$ be the total number of coupons collected by the time the complete set of coupon types is obtained. Show that $\lambda \mathbb{E} T=\mathbb{E} L$. Hence, or otherwise, deduce that $\mathbb{E} L$ does not depend on $\lambda$.

  comment

2005

• 1.II.26I

  Applied Probability | Part II, 2005

  A cell has been placed in a biological solution at time $t=0$. After an exponential time of rate $\mu$, it is divided, producing $k$ cells with probability $p_{k}, k=0,1, \ldots$, with the mean value $\rho=\sum_{k=1}^{\infty} k p_{k}(k=0$ means that the cell dies $)$. The same mechanism is applied to each of the living cells, independently.

  (a) Let $M_{t}$ be the number of living cells in the solution by time $t>0$. Prove that $\mathbb{E} M_{t}=\exp [t \mu(\rho-1)]$. [You may use without proof, if you wish, the fact that, if a positive function $a(t)$ satisfies $a(t+s)=a(t) a(s)$ for $t, s \geqslant 0$ and is differentiable at zero, then $a(t)=e^{\alpha t}, t \geqslant 0$, for some $\left.\alpha .\right]$

  Let $\phi_{t}(s)=\mathbb{E} s^{M_{t}}$ be the probability generating function of $M_{t}$. Prove that it satisfies the following differential equation

  $$\frac{\mathrm{d}}{\mathrm{d} t} \phi_{t}(s)=\mu\left(-\phi_{t}(s)+\sum_{k=0}^{\infty} p_{k}\left[\phi_{t}(s)\right]^{k}\right), \quad \text { with } \quad \phi_{0}(s)=s$$

  (b) Now consider the case where each cell is divided in two cells $\left(p_{2}=1\right)$. Let $N_{t}=M_{t}-1$ be the number of cells produced in the solution by time $t$.

  Calculate the distribution of $N_{t}$. Is $\left(N_{t}\right)$ an inhomogeneous Poisson process? If so, what is its rate $\lambda(t)$ ? Justify your answer.

  comment

• 2.II.26I

  Applied Probability | Part II, 2005

  What does it mean to say that $\left(X_{t}\right)$ is a renewal process?

  Let $\left(X_{t}\right)$ be a renewal process with holding times $S_{1}, S_{2}, \ldots$ and let $s>0$. For $n \geqslant 1$, set $T_{n}=S_{X_{s}+n}$. Show that

  $$\mathbb{P}\left(T_{n}>t\right) \geqslant \mathbb{P}\left(S_{n}>t\right), \quad t \geqslant 0,$$

  for all $n$, with equality if $n \geqslant 2$.

  Consider now the case where $S_{1}, S_{2}, \ldots$ are exponential random variables. Show that

  $$\mathbb{P}\left(T_{1}>t\right)>\mathbb{P}\left(S_{1}>t\right), \quad t>0$$

  and that, as $s \rightarrow \infty$,

  $$\mathbb{P}\left(T_{1}>t\right) \rightarrow \mathbb{P}\left(S_{1}+S_{2}>t\right), \quad t \geqslant 0$$

  comment

• 3.II.25I

  Applied Probability | Part II, 2005

  Consider an $\mathrm{M} / \mathrm{G} / r / 0$ loss system with arrival rate $\lambda$ and service-time distribution $F$. Thus, arrivals form a Poisson process of rate $\lambda$, service times are independent with common distribution $F$, there are $r$ servers and there is no space for waiting. Use Little's Lemma to obtain a relation between the long-run average occupancy $L$ and the stationary probability $\pi$ that the system is full.

  Cafe-Bar Duo has 23 serving tables. Each table can be occupied either by one person or two. Customers arrive either singly or in a pair; if a table is empty they are seated and served immediately, otherwise, they leave. The times between arrivals are independent exponential random variables of mean $20 / 3$. Each arrival is twice as likely to be a single person as a pair. A single customer stays for an exponential time of mean 20 , whereas a pair stays for an exponential time of mean 30 ; all these times are independent of each other and of the process of arrivals. The value of orders taken at each table is a constant multiple $2 / 5$ of the time that it is occupied.

  Express the long-run rate of revenue of the cafe as a function of the probability $\pi$ that an arriving customer or pair of customers finds the cafe full.

  By imagining a cafe with infinitely many tables, show that $\pi \leqslant \mathbb{P}(N \geqslant 23)$ where $N$ is a Poisson random variable of parameter $7 / 2$. Deduce that $\pi$ is very small. [Credit will be given for any useful numerical estimate, an upper bound of $10^{-3}$ being sufficient for full credit.]

  comment

• 4.II.26I

  Applied Probability | Part II, 2005

  A particle performs a continuous-time nearest neighbour random walk on a regular triangular lattice inside an angle $\pi / 3$, starting from the corner. See the diagram below. The jump rates are $1 / 3$ from the corner and $1 / 6$ in each of the six directions if the particle is inside the angle. However, if the particle is on the edge of the angle, the rate is $1 / 3$ along the edge away from the corner and $1 / 6$ to each of three other neighbouring sites in the angle. See the diagram below, where a typical trajectory is also shown.

  

  The particle position at time $t \geqslant 0$ is determined by its vertical level $V_{t}$ and its horizontal position $G_{t}$. For $k \geqslant 0$, if $V_{t}=k$ then $G_{t}=0, \ldots, k$. Here $1, \ldots, k-1$ are positions inside, and 0 and $k$ positions on the edge of the angle, at vertical level $k$.

  Let $J_{1}^{V}, J_{2}^{V}, \ldots$ be the times of subsequent jumps of process $\left(V_{t}\right)$ and consider the embedded discrete-time Markov chains

  $$Y_{n}^{\text {in }}=\left(\widehat{G}_{n}^{\text {in }}, \widehat{V}_{n}\right) \text { and } Y_{n}^{\text {out }}=\left(\widehat{G}_{n}^{\text {out }}, \widehat{V}_{n}\right)$$

  where $\widehat{V}_{n}$ is the vertical level immediately after time $J_{n}^{V}, \widehat{G}_{n}^{\text {in }}$ is the horizontal position immediately after time $J_{n}^{V}$, and $\widehat{G}_{n}^{\text {out }}$ is the horizontal position immediately before time $J_{n+1}^{V}$. (a) Assume that $\left(\widehat{V}_{n}\right)$ is a Markov chain with transition probabilities

  $$\mathbb{P}\left(\widehat{V}_{n}=k+1 \mid \widehat{V}_{n-1}=k\right)=\frac{k+2}{2(k+1)}, \mathbb{P}\left(\widehat{V}_{n}=k-1 \mid \widehat{V}_{n-1}=k\right)=\frac{k}{2(k+1)},$$

  and that $\left(V_{t}\right)$ is a continuous-time Markov chain with rates

  $$q_{k k-1}=\frac{k}{3(k+1)}, \quad q_{k k}=-\frac{2}{3}, \quad q_{k k+1}=\frac{k+2}{3(k+1)}$$

  [You will be asked to justify these assumptions in part (b) of the question.] Determine whether the chains $\left(\widehat{V}_{n}\right)$ and $\left(V_{t}\right)$ are transient, positive recurrent or null recurrent.

  (b) Now assume that, conditional on $\widehat{V}_{n}=k$ and previously passed vertical levels, the horizontal positions $\widehat{G}_{n}^{\text {in }}$ and $\widehat{G}_{n}^{\text {out }}$ are uniformly distributed on $\{0, \ldots, k\}$. In other words, for all attainable values $k, k_{n-1}, \ldots, k_{1}$ and for all $i=0, \ldots, k$,

  $$\begin{aligned} &\mathbb{P}\left(\widehat{G}_{n}^{\text {in }}=i \mid \widehat{V}_{n}=k, \widehat{V}_{n-1}=k_{n-1}, \ldots, \widehat{V}_{1}=k_{1}, \widehat{V}_{0}=0\right) \\ &\quad=\mathbb{P}\left(\widehat{G}_{n}^{\text {out }}=i \mid \widehat{V}_{n}=k, \widehat{V}_{n-1}=k_{n-1}, \ldots, \widehat{V}_{1}=k_{1}, \widehat{V}_{0}=0\right)=\frac{1}{k+1} \end{aligned}$$

  Deduce that $\left(\widehat{V}_{n}\right)$ and $\left(V_{t}\right)$ are indeed Markov chains with transition probabilities and rates as in (a).

  (c) Finally, prove property $(*)$.

  comment

2004

• B2.13

  Applied Probability | Part II, 2004

  Let $M$ be a Poisson random measure of intensity $\lambda$ on the plane $\mathbb{R}^{2}$. Denote by $C(r)$ the circle $\left\{x \in \mathbb{R}^{2}:\|x\|<r\right\}$ of radius $r$ in $\mathbb{R}^{2}$ centred at the origin and let $R_{k}$ be the largest radius such that $C\left(R_{k}\right)$ contains precisely $k$ points of $M$. [Thus $C\left(R_{0}\right)$ is the largest circle about the origin containing no points of $M, C\left(R_{1}\right)$ is the largest circle about the origin containing a single point of $M$, and so on.] Calculate $\mathbb{E} R_{0}, \mathbb{E} R_{1}$ and $\mathbb{E} R_{2}$.

  Now let $N$ be a Poisson random measure of intensity $\lambda$ on the line $\mathbb{R}^{1}$. Let $L_{k}$ be the length of the largest open interval that covers the origin and contains precisely $k$ points of $N$. [Thus $L_{0}$ gives the length of the largest interval containing the origin but no points of $N, L_{1}$ gives the length of the largest interval containing the origin and a single point of $N$, and so on.] Calculate $\mathbb{E} L_{0}, \mathbb{E} L_{1}$ and $\mathbb{E} L_{2}$.

  comment

• B3.13

  Applied Probability | Part II, 2004

  Let $\left(X_{t}, t \geq 0\right)$ be a renewal process with holding times $\left(S_{n}, n=1,2, \ldots\right)$ and $\left(Y_{t}, t \geq 0\right)$ be a renewal-reward process over $\left(X_{t}\right)$ with a sequence of rewards $\left(W_{n}, n=1,2, \ldots\right)$. Under assumptions on $\left(S_{n}\right)$ and $\left(W_{n}\right)$ which you should state clearly, prove that the ratios

  $$X_{t} / t \text { and } Y_{t} / t$$

  converge as $t \rightarrow \infty$. You should specify the form of convergence guaranteed by your assumptions. The law of large numbers, in the appropriate form, for sums $S_{1}+\ldots+S_{n}$ and $W_{1}+\ldots+W_{n}$ can be used without proof.

  In a mountain resort, when you rent skiing equipment you are given two options. (1) You buy an insurance waiver that costs $C / 4$ where $C$ is the daily equipment rent. Under this option, the shop will immediately replace, at no cost to you, any piece of equipment you break during the day, no matter how many breaks you had. (2) If you don't buy the waiver, you'll pay $3 C$ in the case of any break.

  To find out which option is better for me, I decided to set up two models of renewalreward process $\left(Y_{t}\right)$. In the first model, (Option 1), all of the holding times $S_{n}$ are equal to 6 . In the second model, given that there is no break on day $n$ (an event of probability $4 / 5)$, we have $S_{n}=6, W_{n}=C$, but given that there is a break on day $n$, we have that $S_{n}$ is uniformly distributed on $(0,6)$, and $W_{n}=4 C$. (In the second model, I would not continue skiing after a break, whereas in the first I would.)

  Calculate in each of these models the limit

  $$\lim _{t \rightarrow \infty} Y_{t} / t$$

  representing the long-term average cost of a unit of my skiing time.

  comment

• B4.12

  Applied Probability | Part II, 2004

  Consider an $M / G / 1$ queue with $\rho=\lambda \mathbb{E} S<1$. Here $\lambda$ is the arrival rate and $\mathbb{E} S$ is the mean service time. Prove that in equilibrium, the customer's waiting time $W$ has the moment-generating function $M_{W}(t)=\mathbb{E} e^{t W}$ given by

  $$M_{W}(t)=\frac{(1-\rho) t}{t+\lambda\left(1-M_{S}(t)\right)}$$

  where $M_{S}(t)=\mathbb{E} e^{t S}$ is the moment-generating function of service time $S$.

  [You may assume that in equilibrium, the $M / G / 1$ queue size $X$ at the time immediately after the customer's departure has the probability generating function

  $$\left.\mathbb{E} z^{X}=\frac{(1-\rho)(1-z) M_{S}(\lambda(z-1))}{M_{S}(\lambda(z-1))-z}, \quad 0 \leqslant z<1 .\right]$$

  Deduce that when the service times are exponential of rate $\mu$ then

  $$M_{W}(t)=1-\rho+\frac{\lambda(1-\rho)}{\mu-\lambda-t}, \quad-\infty<t<\mu-\lambda .$$

  Further, deduce that $W$ takes value 0 with probability $1-\rho$ and that

  $$\mathbb{P}(W>x \mid W>0)=e^{-(\mu-\lambda) x}, \quad x>0 .$$

  Sketch the graph of $\mathbb{P}(W>x)$ as a function of $x$.

  Now consider the $M / G / 1$ queue in the heavy traffic approximation, when the service-time distribution is kept fixed and the arrival rate $\lambda \rightarrow 1 / \mathbb{E} S$, so that $\rho \rightarrow 1$. Assuming that the second moment $\mathbb{E} S^{2}<\infty$, check that the limiting distribution of the re-scaled waiting time $\tilde{W}_{\lambda}=(1-\lambda \mathbb{E} S) W$ is exponential, with rate $2 \mathbb{E} S / \mathbb{E} S^{2}$.

  comment

2003

• B2.13

  Applied Probability | Part II, 2003

  Let $S_{k}$ be the sum of $k$ independent exponential random variables of rate $k \mu$. Compute the moment generating function of $S_{k}$.

  Consider, for each fixed $k$ and for $0<\lambda<\mu$, an $M / G / 1$ queue with arrival rate $\lambda$ and with service times distributed as $S_{k}$. Assume that the queue is empty at time 0 and write $T_{k}$ for the earliest time at which a customer departs leaving the queue empty. Show that, as $k \rightarrow \infty, T_{k}$ converges in distribution to a random variable $T$ whose moment generating function $M_{T}(\theta)$ satisfies

  $$\log \left(1-\frac{\theta}{\lambda}\right)+\log M_{T}(\theta)=\left(\frac{\theta-\lambda}{\mu}\right)\left(1-M_{T}(\theta)\right)$$

  Hence obtain the mean value of $T$.

  For what service-time distribution would the empty-to-empty time correspond exactly to $T$ ?

  comment

• B3.13

  Applied Probability | Part II, 2003

  State the product theorem for Poisson random measures.

  Consider a system of $n$ queues, each with infinitely many servers, in which, for $i=1, \ldots, n-1$, customers leaving the $i$ th queue immediately arrive at the $(i+1)$ th queue. Arrivals to the first queue form a Poisson process of rate $\lambda$. Service times at the $i$ th queue are all independent with distribution $F$, and independent of service times at other queues, for all $i$. Assume that initially the system is empty and write $V_{i}(t)$ for the number of customers at queue $i$ at time $t \geqslant 0$. Show that $V_{1}(t), \ldots, V_{n}(t)$ are independent Poisson random variables.

  In the case $F(t)=1-e^{-\mu t}$ show that

  $$\mathbb{E}\left(V_{i}(t)\right)=\frac{\lambda}{\mu} \mathbb{P}\left(N_{t} \geqslant i\right), \quad t \geqslant 0, \quad i=1, \ldots, n,$$

  where $\left(N_{t}\right)_{t \geqslant 0}$ is a Poisson process of rate $\mu$.

  Suppose now that arrivals to the first queue stop at time $T$. Determine the mean number of customers at the $i$ th queue at each time $t \geqslant T$.

  comment

• B4.12

  Applied Probability | Part II, 2003

  Explain what is meant by a renewal process and by a renewal-reward process.

  State and prove the law of large numbers for renewal-reward processes.

  A component used in a manufacturing process has a maximum lifetime of 2 years and is equally likely to fail at any time during that period. If the component fails whilst in use, it is replaced immediately by a similar component, at a cost of $£ 1000$. The factory owner may alternatively replace the component before failure, at a time of his choosing, at a cost of $£ 200$. What should the factory owner do?

  comment

2002

• B2.13

  Applied Probability | Part II, 2002

  Two enthusiastic probability students, Ros and Guil, sit an examination which starts at time 0 and ends at time $T$; they both decide to use the time to attempt a proof of a difficult theorem which carries a lot of extra marks.

  Ros' strategy is to write the proof continuously at a constant speed $\lambda$ lines per unit time. In a time interval of length $\delta t$ he has a probability $\mu \delta t+o(\delta t)$ of realising he has made a mistake. If that happens he instantly panics, erases everything he has written and starts all over again.

  Guil, on the other hand, keeps cool and thinks carefully about what he is doing. In a time interval of length $\delta t$, he has a probability $\lambda \delta t+o(\delta t)$ of writing the next line of proof and for each line he has written a probability $\mu \delta t+o(\delta t)$ of finding a mistake in that line, independently of all other lines he has written. When a mistake is found, he erases that line and carries on as usual, hoping for the best.

  Both Ros and Guil realise that, even if they manage to finish the proof, they will not recognise that they have done so and will carry on writing as much as they can.

  (a) Calculate $p_{l}(t)$, the probability that, for Ros, the length of his completed proof at time $t \geqslant l / \lambda$ is at least $l$.

  (b) Let $q_{n}(t)$ be the probability that Guil has $n$ lines of proof at time $t>0$. Show that

  $$\frac{\partial Q}{\partial t}=(s-1)\left(\lambda Q-\mu \frac{\partial Q}{\partial s}\right)$$

  where $Q(s, t)=\sum_{n=0}^{\infty} s^{n} q_{n}(t)$.

  (c) Suppose now that every time Ros starts all over again, the time until the next mistake has distribution $F$, independently of the past history. Write down a renewal-type integral equation satisfied by $l(t)$, the expected length of Ros' proof at time $t$. What is the expected length of proof produced by him at the end of the examination if $F$ is the exponential distribution with mean $1 / \mu$ ?

  (d) What is the expected length of proof produced by Guil at the end of the examination if each line that he writes survives for a length of time with distribution $F$, independently of all other lines?

  comment

• B3.13

  Applied Probability | Part II, 2002

  (a) Define a renewal process and a discrete renewal process.

  (b) State and prove the Discrete Renewal Theorem.

  (c) The sequence $\mathbf{u}=\left\{u_{n}: n \geqslant 0\right\}$ satisfies

  $$u_{0}=1, \quad u_{n}=\sum_{i=1}^{n} f_{i} u_{n-i}, \quad \text { for } n \geqslant 1$$

  for some collection of non-negative numbers $\left(f_{i}: i \in \mathbb{N}\right)$ summing to 1 . Let $U(s)=$ $\sum_{n=1}^{\infty} u_{n} s^{n}, F(s)=\sum_{n=1}^{\infty} f_{n} s^{n}$. Show that

  $$F(s)=\frac{U(s)}{1+U(s)} .$$

  Give a probabilistic interpretation of the numbers $u_{n}, f_{n}$ and $m_{n}=\sum_{i=1}^{n} u_{i}$.

  (d) Let the sequence $u_{n}$ be given by

  $$u_{2 n}=\left(\begin{array}{c} 2 n \\ n \end{array}\right)\left(\frac{1}{2}\right)^{2 n}, \quad u_{2 n+1}=0, \quad n \geqslant 1 .$$

  How is this related to the simple symmetric random walk on the integers $\mathbb{Z}$ starting from the origin, and its subsequent returns to the origin? Determine $F(s)$ in this case, either by calculating $U(s)$ or by showing that $F$ satisfies the quadratic equation

  $$F^{2}-2 F+s^{2}=0, \quad \text { for } \quad 0 \leqslant s<1 .$$

  comment

• B4.12

  Applied Probability | Part II, 2002

  Define a Poisson random measure. State and prove the Product Theorem for the jump times $J_{n}$ of a Poisson process with constant rate $\lambda$ and independent random variables $Y_{n}$ with law $\mu$. Write down the corresponding result for a Poisson process $\Pi$ in a space $E=\mathbb{R}^{d}$ with rate $\lambda(x)(x \in E)$ when we associate with each $X \in \Pi$ an independent random variable $m_{X}$ with density $\rho(X, d m)$.

  Prove Campbell's Theorem, i.e. show that if $M$ is a Poisson random measure on the space $E$ with intensity measure $\nu$ and $a: E \rightarrow \mathbb{R}$ is a bounded measurable function then

  $$\mathbf{E}\left[e^{\theta \Sigma}\right]=\exp \left(\int_{E}\left(e^{\theta a(y)}-1\right) \nu(d y)\right)$$

  where

  $$\Sigma=\int_{E} a(y) M(d y)=\sum_{X \in \Pi} a(X)$$

  Stars are scattered over three-dimensional space $\mathbb{R}^{3}$ in a Poisson process $\Pi$ with density $\nu(X)\left(X \in \mathbb{R}^{3}\right)$. Masses of the stars are independent random variables; the mass $m_{X}$ of a star at $X$ has the density $\rho(X, d m)$. The gravitational potential at the origin is given by

  $$F=\sum_{X \in \Pi} \frac{G m_{X}}{|X|}$$

  where $G$ is a constant. Find the moment generating function $\mathbf{E}\left[e^{\theta F}\right]$.

  A galaxy occupies a sphere of radius $R$ centred at the origin. The density of stars is $\nu(\mathbf{x})=1 /|\mathbf{x}|$ for points $\mathbf{x}$ inside the sphere; the mass of each star has the exponential distribution with mean $M$. Calculate the expected potential due to the galaxy at the origin. Let $C$ be a positive constant. Find the distribution of the distance from the origin to the nearest star whose contribution to the potential $F$ is at least $C$.

  comment

2001

• B2.13

  Applied Probability | Part II, 2001

  Let $M$ be a Poisson random measure on $E=\mathbb{R} \times[0, \pi)$ with constant intensity $\lambda$. For $(x, \theta) \in E$, denote by $l(x, \theta)$ the line in $\mathbb{R}^{2}$ obtained by rotating the line $\{(x, y): y \in \mathbb{R}\}$ through an angle $\theta$ about the origin.

  Consider the line process $L=M \circ l^{-1}$.

  (i) What is the distribution of the number of lines intersecting the disc $\left\{z \in \mathbb{R}^{2}:|z| \leqslant a\right\}$ ?

  (ii) What is the distribution of the distance from the origin to the nearest line?

  (iii) What is the distribution of the distance from the origin to the $k$ th nearest line?

  comment

• B3.13

  Applied Probability | Part II, 2001

  Consider an $M / G / 1$ queue with arrival rate $\lambda$ and traffic intensity less

  than 1. Prove that the moment-generating function of a typical busy period, $M_{B}(\theta)$, satisfies

  $$M_{B}(\theta)=M_{S}\left(\theta-\lambda+\lambda M_{B}(\theta)\right),$$

  where $M_{S}(\theta)$ is the moment-generating function of a typical service time.

  If service times are exponentially distributed with parameter $\mu>\lambda$, show that

  $$M_{B}(\theta)=\frac{\lambda+\mu-\theta-\left\{(\lambda+\mu-\theta)^{2}-4 \lambda \mu\right\}^{1 / 2}}{2 \lambda}$$

  for all sufficiently small but positive values of $\theta$.

  comment

• B4.12

  Applied Probability | Part II, 2001

  Define a renewal process and a renewal reward process.

  State and prove the strong law of large numbers for these processes.

  [You may assume the strong law of large numbers for independent, identically-distributed random variables.

  State and prove Little's formula.

  Customers arrive according to a Poisson process with rate $\nu$ at a single server, but a restricted waiting room causes those who arrive when $n$ customers are already present to be lost. Accepted customers have service times which are independent and identicallydistributed with mean $\alpha$ and independent of the arrival process. Let $P_{j}$ be the equilibrium probability that an arriving customer finds $j$ customers already present.

  Using Little's formula, or otherwise, determine a relationship between $P_{0}, P_{n}, \nu$ and

  Part II

  comment