Queues

Consider a random walk on the non-negative integers with a reflecting barrier at $0$, and which moves rightwards or leftwards with respective probabilities $\rho /(1+\rho )$ and $1 /(1+\rho )$; when at $0$, the particle moves to 1 at the next step. Show that the walk has a stationary distribution if and only if $\rho < 1$, and in this case the unique such distribution $\pi$ is given by $\pi_{0} = \frac{1}{2}(1-\rho ), \pi_{n} = \frac{1}{2}\left(1-\rho^{2}\right) \rho^{n-1}$ for $n \geq 1$.

Suppose now that the random walker of Exercise (11.2.1) delays its steps in the following way. When at the point $n$, it waits a random length of time having the exponential distribution with parameter $\theta_{n}$ before moving to its next position; different 'holding times' are independent of each other and of further information concerning the steps of the walk. Show that, subject to reasonable assumptions on the $\theta_{n}$, the ensuing continuous-time process settles into an equilibrium distribution $\mathbf{v}$ given by $v_{n} = C \pi_{n} / \theta_{n}$ for some appropriate constant $C$.

By applying this result to the case when $\theta_{0} = \lambda , \theta_{n} = \lambda +\mu$ for $n \geq 1$, deduce that the equilibrium distribution of the $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue is $v_{n} = (1-\rho ) \rho^{n}, n \geq 0$, where $\rho = \lambda / \mu < 1$.

Consider a $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue with $\rho = \lambda / \mu$ satisfying $\rho < 1$, and suppose that the number $Q(0)$ of people in the queue at time 0 has the stationary distribution $\pi_{n} = (1-\rho ) \rho^{n}$, $n \geq 0$. Let $W$ be the time spent by a typical new arrival before he begins his service. Show that the distribution of $W$ is given by $\mathbb {P}\left(W \leq x\right) = 1-\rho e^{-x(\mu -\lambda )}$ for $x \geq 0$, and note that $\mathbb {P}\left(W = 0\right) = 1-\rho$.

A box contains $i$ red balls and $j$ lemon balls, and they are drawn at random without replacement. Each time a red (respectively lemon) ball is drawn, a particle doing a walk on $\left\{ 0,1,2, \ldots \right\}$ moves one step to the right (respectively left); the origin is a retaining barrier, so that leftwards steps from the origin are suppressed. Let $\pi (n ; i, j)$ be the probability that the particle ends at position $n$, having started at the origin. Write down a set of difference equations for the $\pi (n ; i, j)$, and deduce that

where $A(n ; i, j) = \binom {i}{n} /\binom {j+n}{n}$.

Let $Q$ be a $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue with $Q(0) = 0$. Show that $p_{n}(t) = \mathbb {P}\left(Q(t) = n\right)$ satisfies

where the $\pi (n ; i, j)$ are given in Exercise (11.2.4).

Let $Q(t)$ be the length of an $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue at time $t$, and let $Z = \left\{ Z_{n}\right\}$ be the jump chain of $Q$. Explain how the stationary distribution of $Q$ may be derived from that of $Z$, and vice versa.

Two queues have one server each, and all service times are independent and exponentially distributed, with parameter $\mu_{i}$ for queue $i$. Customers arrive at the first queue at the instants of a Poisson process of rate $\lambda \left( < \min \left\{ \mu_{1}, \mu_{2}\right\} \right)$, and on completing service immediately enter the second queue. The queues are in equilibrium. Show that:

Consider $\mathrm{M}(\lambda ) / \mathrm{D}(d) / 1$ where $\rho = \lambda d < 1$. Show that the mean queue length at moments of departure in equilibrium is $\frac{1}{2} \rho (2-\rho ) /(1-\rho )$.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$, and show that the moment generating function of a typical busy period is given by

for all sufficiently small but positive values of $s$.

Consider the $M(\lambda ) / G / 1$ queue with no waiting room. Customers who arrive while the server is busy are lost. Show that the long run proportion of arrivals lost is $1 /\left(1+\rho^{-1}\right)$ where $\rho = \lambda \mathbb {E}\left[S\right]$ is the traffic intensity.

Consider $\mathrm{G} / \mathrm{M}(\mu ) / 1$, and let $\alpha_{j} = \mathbb {E}\left[(\mu X)^{j} e^{-\mu X} / j!\right]$ where $X$ is a typical interarrival time. Suppose the traffic intensity $\rho$ is less than 1. Show that the equilibrium distribution $\pi$ of the imbedded chain at moments of arrivals satisfies

Look for a solution of the form $\pi_{n} = \theta^{n}$ for some $\theta$, and deduce that the unique stationary distribution is given by $\pi_{j} = (1-\eta ) \eta^{j}$ for $j \geq 0$, where $\eta$ is the smallest positive root of the equation $s = M_{X}(\mu (s-1))$.

Consider a $\mathrm{G} / \mathrm{M}(\mu ) / 1$ queue in equilibrium. Let $\eta$ be the smallest positive root of the equation $x = M_{X}(\mu (x-1))$ where $M_{X}$ is the moment generating function of an interarrival time. Show that the mean number of customers ahead of a new arrival is $\eta (1-\eta )^{-1}$, and the mean waiting time is $\eta \left\{ \mu (1-\eta )\right\}^{-1}$.

Consider $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$ where $\mu > 1$. Show that the continuous-time queue length $Q(t)$ does not converge in distribution as $t \rightarrow \infty$, even though the imbedded chain at the times of arrivals is ergodic.

Show that, for a $G / G / 1$ queue, the starting times of the busy periods of the server constitute a renewal process.

Consider a $\mathrm{G} / \mathrm{M}(\mu ) / 1$ queue in equilibrium, together with the dual (unstable) $\mathrm{M}(\mu ) / \mathrm{G} / 1$ queue. Show that the idle periods of the latter queue are exponentially distributed. Use the theory of duality of queues to deduce for the former queue that: (a) the waiting-time distribution is a mixture of an exponential distribution and an atom at zero, and (b) the equilibrium queue length is geometric.

Consider $\mathrm{G} / \mathrm{M}(\mu ) / 1$, and let $G$ be the distribution function of $S-X$ where $S$ and $X$ are typical (independent) service and interarrival times. Show that the Wiener-Hopf equation

for the limiting waiting-time distribution $F$ is satisfied by $F(x) = 1-\eta e^{-\mu (1-\eta ) x}, x \geq 0$. Here, $\eta$ is the smallest positive root of the equation $x = M_{X}(\mu (x-1))$, where $M_{X}$ is the moment generating function of $X$.

Consider the $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue with $\rho = \lambda / \mu < 1$. Let $Q_{\rho }$ be a random variable with the equilibrium queue distribution, and show that $(1-\rho ) Q_{\rho }$ converges in distribution as $\rho \uparrow 1$, the limit distribution being exponential with parameter 1.

Consider an open migration process with $c$ stations, in which individuals arrive at station $j$ at rate $v_{j}$, individuals move from $i$ to $j$ at rate $\lambda_{i j} \phi_{i}\left(n_{i}\right)$, and individuals depart from $i$ at rate $\mu_{i} \phi_{i}\left(n_{i}\right)$, where $n_{i}$ denotes the number of individuals currently at station $i$. Show when $\phi_{i}\left(n_{i}\right) = n_{i}$ for all $i$ that the system behaves as though the customers move independently through the network. Identify the explicit form of the stationary distribution, subject to an assumption of irreducibility, and explain a connection with the Bartlett theorem of Problem (8.10.6).

Let $Q$ be an $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / s$ queue where $\lambda < s \mu$, and assume $Q$ is in equilibrium. Show that the process of departures is a Poisson process with intensity $\lambda$, and that departures up to time $t$ are independent of the value of $Q(t)$.

Customers arrive in the manner of a Poisson process with intensity $\lambda$ in a shop having two servers. The service times of these servers are independent and exponentially distributed with respective parameters $\mu_{1}$ and $\mu_{2}$. Arriving customers form a single queue, and the person at the head of the queue moves to the first free server. When both servers are free, the next arrival is allocated a server chosen according to one of the following rules:

Consider an $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue modified so that on completion of service the customer leaves with probability $\delta$, or rejoins 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, but if the rejoining customer goes to the end of the queue, the composite arrival process is not Poisson.

Consider an open migration process in equilibrium. If there is no path by which an individual at station $k$ can reach station $j$, show that the stream of individuals moving directly from station $j$ to station $k$ forms a Poisson process.

Show that an open migration process is non-explosive.

Let $X$ be an irreducible, continuous-time Markov chain with generator $\mathbf{G}$ on the state space $T = S \cup \left\{ \infty \right\}$, where $S$ is countable and non-empty. Show that a distribution $\mathbf{\pi }$ on $T$ satisfies $\mathbf{\pi } \mathbf{G} = \mathbf{0}$ if and only if, for $j \in S, \sum_{i \in T} \pi_{i} g_{i j} = 0$.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$ with the constraint that arriving customers who see $N$ customers in the line ahead of them leave and never return. Find the stationary distribution of queue length for the cases $k = 1$ and $k = 2$.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ with the constraint that if an arriving customer sees $n$ customers in the line ahead of him, he joins the queue with probability $p(n)$ and otherwise leaves in disgust.

In a Moscow supermarket customers queue at the cash desk to pay for the goods they want; then they proceed to a second line where they wait for the goods in question. If customers arrive in the shop like a Poisson process with parameter $\lambda$ and all service times are independent and exponentially distributed, parameter $\mu_{1}$ at the first desk and $\mu_{2}$ at the second, find the stationary distributions of queue lengths, when they exist, and show that, at any given time, the two queue lengths are independent in equilibrium.

Consider M/G/1, with the modification that the server may serve up to $m$ customers simultaneously. If the queue length is less than $m$ at the beginning of a service period then she serves everybody waiting at that time. Find a formula which is satisfied by the probability generating function of the stationary distribution of queue length at the times of departures, and evaluate this generating function explicitly in the case when $m = 2$ and service times are exponentially distributed.

Consider $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ where $\lambda < \mu$. Find the moment generating function of the length $B$ of a typical busy period, and show that $\mathbb {E}\left[B\right] = (\mu -\lambda )^{-1}$ and $\operatorname {Var}\left[B\right] = (\lambda +\mu ) /(\mu -\lambda )^{3}$. Show that the density function of $B$ is

where $I_{1}$ is a modified Bessel function.

Consider $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ in equilibrium. Obtain an expression for the mean queue length at departure times. Show that the mean waiting time in equilibrium of an arriving customer is $\frac{1}{2} \lambda \mathbb {E}\left[S^{2}\right] /(1-\rho )$ where $S$ is a typical service time and $\rho = \lambda \mathbb {E}\left[S\right]$.

Amongst all possible service-time distributions with given mean, find the one for which the mean waiting time is a minimum.

Let $W_{t}$ be the time which a customer would have to wait in a $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ queue if he were to arrive at time $t$. Show that the distribution function $F(x ; t) = \mathbb {P}\left(W_{t} \leq x\right)$ satisfies

where $S$ is a typical service time, independent of $W_{t}$. Suppose that $F(x, t) \rightarrow H(x)$ for all $x$ as $t \rightarrow \infty$, where $H$ is a distribution function satisfying $0 = h-\lambda H+\lambda \mathbb {P}\left(U+S \leq x\right)$ for $x > 0$, where $U$ is independent of $S$ with distribution function $H$, and $h$ is the density function of $H$ on $(0, \infty )$. Show that the moment generating function $M_{U}$ of $U$ satisfies

where $\rho$ is the traffic intensity. You may assume that $\mathbb {P}\left(S = 0\right) = 0$.

Consider a $\mathrm{G} / \mathrm{G} / 1$ queue in which the service times are constantly equal to $2$, whilst the interarrival times take either of the values 1 and 4 with equal probability $\frac{1}{2}$. Find the limiting waiting time distribution.

Consider an extremely idealized model of a telephone exchange having infinitely many channels available. Calls arrive in the manner of a Poisson process with intensity $\lambda$, and each requires one channel for a length of time having the exponential distribution with parameter $\mu$, independently of the arrival process and of the duration of other calls. Let $Q(t)$ be the number of calls being handled at time $t$, and suppose that $Q(0) = I$.

Determine the probability generating function of $Q(t)$, and deduce $\mathbb {E}\left[Q(t)\right], \mathbb {P}\left(Q(t) = 0\right)$, and the limiting distribution of $Q(t)$ as $t \rightarrow \infty$.

Assuming the queue is in equilibrium, find the proportion of time that no channels are occupied, and the mean length of an idle period. Deduce that the mean length of a busy period is $\left(e^{\lambda / \mu }-1\right) / \lambda$.

Customers arrive in a shop in the manner of a Poisson process with intensity $\lambda$, where $0 < \lambda < 1$. They are served one by one in the order of their arrival, and each requires a service time of unit length. Let $Q(t)$ be the number in the queue at time $t$. By comparing $Q(t)$ with $Q(t+1)$, determine the limiting distribution of $Q(t)$ as $t \rightarrow \infty$ (you may assume that the quantities in question converge). Hence show that the mean queue length in equilibrium is $\lambda \left(1-\frac{1}{2} \lambda \right) /(1-\lambda )$.

Let $W$ be the waiting time of a newly arrived customer when the queue is in equilibrium. Deduce from the results above that $\mathbb {E}\left[W\right] = \frac{1}{2} \lambda /(1-\lambda )$.

Consider $\mathrm{M}(\lambda ) / \mathrm{D}(1) / 1$, and suppose that the queue is empty at time 0. Let $T$ be the earliest time at which a customer departs leaving the queue empty. Show that the moment generating function $M_{T}$ of $T$ satisfies

and deduce the mean value of $T$, distinguishing between the cases $\lambda < 1$ and $\lambda \geq 1$.

Suppose $\lambda < \mu$, and consider a $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue $Q$ in equilibrium.

Consider the queue $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$, where $k \geq 1$. Show that a stationary distribution $\mathbf{\pi }$ exists if and only if $\lambda < k \mu$, and calculate it in this case.

Suppose that the cost of operating this system in equilibrium is

the positive constants $A$ and $B$ representing respectively the costs of employing a server and of the dissatisfaction of delayed customers.

Show that, for fixed $\mu$, there is a unique value $\lambda^{*}$ in the interval $(0, \mu )$ such that it is cheaper to have $k = 1$ than $k = 2$ if and only if $\lambda < \lambda^{*}$.

Customers arrive in a shop in the manner of a Poisson process with intensity $\lambda$. They form a single queue. There are two servers, labelled 1 and $2$, server $i$ requiring an exponentially distributed time with parameter $\mu_{i}$ to serve any given customer. The customer at the head of the queue is served by the first idle server; when both are idle, an arriving customer is equally likely to choose either.

Consider the $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$ queue where $\mu > 1$, and let $Q_{n}$ be the number of people in the queue just before the $n$th arrival. Let $Q_{\mu }$ be a random variable having as distribution the stationary distribution of the Markov chain $\left\{ Q_{n}\right\}$. Show that $\left(1-\mu^{-1}\right) Q_{\mu }$ converges in distribution as $\mu \downarrow 1$, the limit distribution being exponential with parameter 2.

Taxis arrive at a stand in the manner of a Poisson process with intensity $\tau$, and passengers arrive in the manner of an (independent) Poisson process with intensity $\pi$. If there are no waiting passengers, the taxis wait until passengers arrive, and then move off with the passengers, one to each taxi. If there is no taxi, passengers wait until they arrive. Suppose that initially there are neither taxis nor passengers at the stand. Show that the probability that $n$ passengers are waiting at time $t$ is $(\pi / \tau )^{\frac{1}{2} n} e^{-(\pi +\tau ) t} I_{n}(2 t \sqrt{\pi \tau })$, where $I_{n}(x)$ is the modified Bessel function, i.e. the coefficient of $z^{n}$ in the power series expansion of $\exp \left\{ \frac{1}{2} x\left(z+z^{-1}\right)\right\}$

Machines arrive for repair as a Poisson process with intensity $\lambda$. Each repair involves two stages, the $i$ th machine to arrive being under repair for a time $X_{i}+Y_{i}$, where the pairs $\left(X_{i}, Y_{i}\right), i = 1,2, \ldots$, are independent with a common joint distribution. Let $U(t)$ and $V(t)$ be the numbers of machines in the $X$-stage and $Y$-stage of repair at time $t$. Show that $U(t)$ and $V(t)$ are independent Poisson random variables.

An insurance company pays independent and identically distributed claims $\left\{ K_{n}: n \geq 1\right\}$ at the instants of a Poisson process with intensity $\lambda$, where $\lambda \mathbb {E}\left[K_{1}\right] < 1$. Premiums are received at constant rate 1. Show that the maximum deficit $M$ the company will ever accumulate has moment generating function

For an $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ queue with $\lambda < \mu$, when in equilibrium, show that the expected time until the queue is first empty is $\lambda (\mu -\lambda )^{-2}$.

Consider an $M(\lambda ) / G / \infty$ queue. Use the renewal-reward theorem to show that the expected duration of a busy period is $\left(e^{\rho }-1\right) / \lambda$ where $\rho = \lambda \mathbb {E}\left[S\right]$.