$$\newcommand{\P}{\mathbb{P}}$$ $$\newcommand{\E}{\mathbb{E}}$$ $$\newcommand{\R}{\mathbb{R}}$$ $$\newcommand{\N}{\mathbb{N}}$$ $$\newcommand{\Z}{\mathbb{Z}}$$ $$\newcommand{\bs}{\boldsymbol}$$

## 10. Queuing Chains

#### Introduction

In a queuing model, customers arrive at a station for service. As always, the terms are generic; here are some typical examples:

• The customers are persons and the service station is a store.
• The customers are file requests and the service station is a web server.

Queuing models can be quite complex, depending on such factors as the probability distribution that governs the arrival of customers, the probability distribution that governs the service of customers, the number of servers, and the behavior of the customers when all servers are busy. Indeed, queuing theory has its own lexicon to indicate some of these factors. In this section, we will study one of the simplest, discrete time queuing models. However, as we will see, this discrete time chain is embedded in a much more realistic continuous time queuing process knows as the M/G/1 queue. In a general sense, the main interest in any queuing model is the number of customers in the system as a function of time, and in particular, whether the servers can adequately handle the flow of customers.

Our main assumptions are as follows:

• If the queue is empty at a given time, then a random number of new customers arrive at the next time.
• If the queue is nonempty at a given time, then one customer is served and a random number of new customers arrive at the next time.
• The number of customers who arrive at each time period form an independent, identically distributed sequence.

Thus, let $$X_n$$ denote the number of customers in the system at time $$n \in \N$$, and let $$U_n$$ denote the number of new customers who arrive at time $$n \in \N_+$$. Then $$\bs{U} = (U_1, U_2, \ldots)$$ is a sequence of independent random variables, with common probability density function $$f$$ on $$\N$$, and

$X_{n+1} = \begin{cases} U_{n+1}, & X_n = 0 \\ (X_n - 1) + U_{n+1}, & X_n \gt 0 \end{cases}, \quad n \in \N$

$$\bs{X} = (X_0, X_1, X_2, \ldots)$$ is a Markov chain with state space $$\N$$ and transition probability matrix $$P$$ given by

\begin{align} P(0, y) & = f(y), \quad y \in \N \\ P(x, y) & = f(y - x + 1), \quad x \in \N_+, \; y \in \{x - 1, x, x + 1, \ldots\} \end{align}

Explicitly find the one-step transition matrix $$P$$ for each of the following customer distributions:

1. The Poisson distribution with parameter $$m \in (0, \infty)$$
2. The binomial distribution with trial parameter $$k \in \N_+$$ and success parameter $$p \in (0, 1)$$
3. The geometric distribution on $$\N$$ with parameter $$1 - p \in (0, 1)$$
1. $$P(0, y) = e^{-m} \frac{m^y}{y!}$$ for $$y \in \N$$; $$P(x, y) = e^{-m} \frac{m^{y - x + 1}}{(y - x + 1)!}$$ for $$x \in \N_+$$, $$y \in \{x - 1, x, x + 1, \ldots\}$$
2. $$P(0, y) = \binom{k}{y} p^y (1 - p)^{k-y}$$ for $$y \in \{0, 1 \ldots, k\}$$; $$P(x, y) = \binom{k}{y - x + 1} p^{y-x} (1 - p)^{k - y + x - 1}$$ for $$x \in \N_+$$, $$y \in \{x - 1, x, \ldots, k + x - 1\}$$
3. $$P(0, y) = (1 - p) p^y$$ for $$y \in \N$$; $$\P(x, y) = (1 - p) p^{y - x + 1}$$ for $$x \in \N_+$$, $$y \in \{x - 1, x, x + 1 \ldots \}$$

Consider the queuing chain with customer probability density function given by $$f(0) = 1 - p$$, $$f(2) = p$$ where $$p \in (0, 1)$$ is a parameter. Thus, at each time period, either no new customers arrive or 2 new customers arrive. Find the probability density function of $$(X_1, X_2, X_3)$$ starting with 1 customer.

Let $$g(x, y, z) = \P(X_1 = x, X_2 = y, X_3 = z \mid X_0 = 1)$$.

1. $$g(0, 0, 0) = (1 - p)^3$$
2. $$g(0, 0, 2) = g(0, 2, 1) = g(2, 1, 0) = p (1 - p)^2$$
3. $$g(0, 2, 3) = g(2, 1, 3) = g(2, 3, 2) = p^2 (1 - p)$$
4. $$g(2, 3, 4) = p^3$$

#### Recurrence and Transience

From now on we will assume that $$f(0) \gt 0$$ and $$f(0) + f(1) \lt 1$$. Thus, at each time unit, it's possible that no new customers arrive or that at least 2 new customers arrive. Also, we let $$m = \sum_{x \in \N} x \, f(x)$$ denote the mean of $$f$$, so that $$m$$ is the average number of new customers who arrive during a time period.

The chain $$\bs{X}$$ is irreducible and aperiodic.

Proof:

In a positive state, the chain can more at least one unit to the right and can move one unit to the left at the next step. From state 0, the chain can move two or more units to the right or can stay in 0 at the next step. Thus, every state leads to every other state.

Our goal in this section is to compute the probability that the chain reaches 0, as a function of the initial state (so that the server is able to serve all of the customers). As we will see, there are some curious and unexpected parallels between this problem and the problem of computing the extinction probability in the branching chain. As a corollary, we will also be able to classify the queuing chain as transient or recurrent. Our basic parameter of interest is $$q = H(1, 0)$$, the probability that the queue eventually empties, starting with a single customer, where as usual, $$H$$ is the hitting probability matrix.

The queuing chain satisifes the following properties:

1. The restriction of $$P$$ to $$\{x, x + 1, \ldots\} \times \{x - 1, x, \ldots\}$$ is independent of $$x \in \N_+$$.
2. $$q = H(x, x - 1)$$ for every $$x \in \N_+$$.
3. $$q^x = H(x, 0)$$ for every $$x \in \N_+$$.

$$q$$ satisfies the following fundamental equation:

$q = \sum_{x = 0}^\infty f(x) q^x$
Proof:

The follows from the previous theorem by conditioning on the first state.

Note that this is exactly the same equation that we considered for the branching chain, namely $$\Phi(q) = q$$, where $$\Phi$$ is the probability generating function of the distribution that governs the number of new customers that arrive during each period.

$$q$$ is the smallest solution in $$(0, 1]$$ of the equation $$\Phi(t) = t$$. Moreover

1. If $$m \le 1$$ then $$q = 1$$ and the chain is recurrent.
2. If $$m \gt 1$$ then $$0 \lt q \lt 1$$ and the chain is transient..
Proof:

This follows from our analysis of branching chains. The graphs above show the two cases. Note that the condition in (a) means that on average, one or fewer new customers arrive for each customer served. The condition in (b) means that on average, more than one new customer arrives for each customer served.

Find the PGF $$\Phi$$ for each new customer PDF $$f$$ below. Find $$q$$, the probability that the queue is eventually empty, starting with 1 customer.

1. $$f(n) = (1 - p) p^n$$ for $$n \in \N$$, the geometric distribution on $$\N$$ with parameter $$1 - p \in (0, 1)$$.
2. $$f(0) = 1 - p$$, $$f(2) = p$$ where $$p \in (0, 1)$$ is a parameter. Thus, at each time period, either no new customers arrive or 2 new customers arrive.
1. $$\Phi(t) = \frac{1 - p}{1 - p\,t}$$. Hence $$q = 1$$ if $$p \le \frac{1}{2}$$ (so the chain is recurrent), and $$q = \frac{1 - p}{p}$$ if $$p \gt \frac{1}{2}$$ (so the chain is transient).
2. $$\Phi(t) = (1 - p) + p \, t^2$$. Hence $$q = 1$$ if $$p \le \frac{1}{2}$$ (so the chain is recurrent), and $$q = \frac{1 - p}{p}$$ if $$p \gt \frac{1}{2}$$ (so the chain is transient).

#### Positive Recurrence

Our next goal is to find conditions for the queuing chain to be positive recurrent. Recall that $$m$$ is the mean of the probability density function $$f$$; that is, the expected number of new customers who arrive during a time period. As usual, let $$T_0$$ denote the first positive time that the chain is in state 0.

Let $$\Psi$$ denote the probability generating function of $$T_0$$, starting in state 1. Then

1. $$\Psi$$ is also the probability generating function of $$T_0$$ starting in state 0.
2. $$\Psi^x$$ is the probability generating function of $$T_0$$ starting in state $$x \in \N_+$$.

$$\Psi(t) = t \Phi[\Psi(t)]$$ for $$t \in [0, 1]$$.

The deriviative of $$\Psi$$ is

$\Psi^\prime(t) = \frac{\Phi[\Psi(t)]}{1 - t \Phi^\prime[\Psi(t)]}, \quad t \in [0, 1)$

As usual, let $$\mu(0) = \E(T_0 \mid X_0 = 0)$$, the mean return time to state 0. Then

1. $$\mu(0) = \frac{1}{1 - m}$$ if $$m \lt 1$$ and therefore the chain is positive recurrent.
2. $$\mu(0) = \infty$$ if $$m = 1$$ and therefore the chain is null recurrent.
Proof:

This follows by letting $$t \to \infty$$ in the previous theorem.

For each of the new customer distributions in Exercise 8, compute the mean $$m$$. Find conditions on the parameter $$p$$ for the queuing chain to be positive recurrent, null recurrent, and transient.

1. $$m = \frac{p}{1 - p}$$. The chain is positive recurrent if $$p \lt \frac{1}{2}$$, null recurrent if $$p = \frac{1}{2}$$, and transient if $$p \gt \frac{1}{2}$$.
2. $$m = 2\,p$$. The chain is positive recurrent if $$p \lt \frac{1}{2}$$, null recurrent if $$p = \frac{1}{2}$$, and transient if $$p \gt \frac{1}{2}$$.