Uncategorized – Applied Probability Notes

M/G/∞ Queue and Campbell’s Theorem

The M/G/$\infty$ has Poisson arrivals and general service times; here, the number of jobs in service is Poisson distributed. Campbell’s theorem extends the proof idea by giving the moment generating function of sums taken over the points of a Poisson process.

Continue reading “M/G/∞ Queue and Campbell’s Theorem”

Kingman’s Bound

We next describe an elegant and useful bound for a single-server queue (G/G/1) due to John Kingman:

$\displaystyle \mathbb E[w]\leq\frac{1}{2}\frac{\sigma_s^2+\sigma_a^2}{\bar s-\bar a}.$

Continue reading “Kingman’s Bound”

Lindley’s Recursion and the G/G/1 Queue

Lindley’s recursion gives a useful formula relating waiting times in a queue to general inter-arrival and service times.

Consider a FIFO single-server queue. We define:

$\tau_n$ as the inter-arrival time between the $n$ th and $(n+1)$ th arrivals;
$\sigma_n$ as the service time of the $n$ th arrival;
$W_n$ as the waiting time of the $n$ th arrival; and
$S_n:=\sum_{j=0}^n(\sigma_j-\tau_j)$ , with $S_{-1}:=0$ .

Lindley’s Recursion

The waiting time of the $(n+1)$ th arrival satisfies

$\displaystyle W_{n+1}=\max\{0,W_n+\sigma_n-\tau_n\}.$

If $W_0=0$ , then

$\displaystyle W_{n+1}=S_n-\min_{-1\leq j\leq n}S_j=S_n-\min\{0,S_0,\ldots,S_n\}.$

The process $S_n$ is a random walk. Lindley’s recursion therefore allows us to convert questions about the G/G/1 queue into questions about a random walk and its running minimum.

Continue reading “Lindley’s Recursion and the G/G/1 Queue”

A Server with General Service: The M/G/1 Queue

We consider a queue with Poisson arrivals of rate $\lambda$ . Since exponentially distributed service times are often unrealistic, we assume that service times are independent and identically distributed with general distribution $F_S(\cdot)$ . There is a single server, which serves jobs at unit speed.

Continue reading “A Server with General Service: The M/G/1 Queue”

Renewal Processes and Residual Service

The assumption of exponential inter-arrival times is often reasonable. The Poisson process provides a useful model for many real-world systems when arrivals are drawn independently from a large population. However, the assumption of exponential service times is usually less realistic.

Exponential service times are a useful starting point because the resulting models can often be analysed using the well-developed theory of continuous-time Markov chains. These models allow us to understand the main features of a queueing system and build intuition before introducing more realistic service-time distributions.

Continue reading “Renewal Processes and Residual Service”

Erlang Link and The Infinite Server Queue

The Erlang link and M/M/$\infty$ queue are models in which jobs do not wait. In the Erlang link, jobs are lost when all servers are busy, while in the M/M/$\infty$ queue every job begins service immediately.

Continue reading “Erlang Link and The Infinite Server Queue”

A Call Centre Queue (M/M/N)

Consider a queue where $N$ servers serve one job at a time. The remaining jobs wait in a queue. Jobs arrive as a Poisson process of rate $\lambda$ . Jobs have independent, exponentially distributed service requirements with mean $\mu^{-1}$ . In Kendall notation, this is called an M/M/N queue.

We can think of this as a simple model of a call centre. Some customers receive service immediately when there are idle servers. Otherwise, they must wait in the queue for the next available server.

Continue reading “A Call Centre Queue (M/M/N)”

Little’s Law

Little’s Law is such a fundamental result in queueing theory that it is called a “law.” It states that the average number of jobs in a system is equal to the average arrival rate multiplied by the average time spent in the system. It applies to any system involving waiting, provided that the system is not overloaded.

Little’s Law

For a queueing system in equilibrium,

$\displaystyle \bar N = \lambda \bar W$

where

$\bar N$ is the mean number of jobs in the system,

$\lambda$ is the mean arrival rate, and

$\bar W$ is the mean time spent in the system.

We use the letter $W$ to denote the time spent in the system, also called the sojourn time.

Continue reading “Little’s Law”

A single-server queue (M/M/1)

We consider what is perhaps the simplest and most tractable queueing model: a single-server queue with Poisson arrivals and exponential service times. This is called the M/M/1 queue.

Poisson Arrivals See Time Averages (PASTA)

We are often interested in the state an arriving customer observes in a queue. If arrivals are Poisson, then the average arrival sees the system in its equilibrium state.

This may seem counterintuitive. When a customer arrives, we might expect the system to be slightly emptier in anticipation of the arrival. However, this is not the case for Poisson processes: they are uniformly distributed over time, and arrivals after time $t$ are independent of what happened before $t$ .