# The minimal quasi-stationary distribution of the absorbed M/M/∞ queue

Elie Cerf

► To cite this version:

Elie Cerf. The minimal quasi-stationary distribution of the absorbed M/M/∞ queue. 2023. hal-04161193

HAL Id: hal-04161193

https://hal.science/hal-04161193

Preprint submitted on 13 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
# The minimal quasi-stationary distribution of the absorbed $M/M/\infty$ queue

Elie Cerf*

July 13, 2023

## Abstract

We give in this paper two characterizations of the minimal exponential rate of survival $\theta^*$ of the $M/M/\infty$ queue. The first one is a derivation of a known result on the duration of excursions of this process. The second one was conjectured by Martínez and Ycart [8] and is proved using complex analysis by establishing a connection with the first characterization in terms of the incomplete gamma function.

## 1 Introduction

Throughout the end of the last century, quasi-stationary distributions have emerged as a powerful tool to study the long time behavior of absorbed Markov processes. Let us consider a Markov process $(X_t)_{t\ge0}$ evolving on a state space $E = \tilde{E} \cup \Delta$, where $\Delta$ is the set of absorbing states and assume that the process is almost surely eventually absorbed, meaning that if we denote by $T := \inf\{s \ge 0, X_s \in \Delta\}$ the time of absorption, then for any initial distribution $\mu$

$$ \mathbb{P}_{\mu}(T < \infty) = 1. $$

In this setting, $(X_{t\wedge T})_{t\ge0}$ admits only trivial stationary distributions concentrated on $\Delta$. Therefore we define its quasi-stationary distribution as follows. Let $\nu$ be a probability measure on $\tilde{E}$, it is said to be a quasi-stationary distribution of $(X_t)_{t\ge0}$ if $\nu$ verifies for all $i \in \tilde{E}$:

$$ \mathbb{P}_{\nu}(X_t = i | t < T) = \nu(i). \qquad (1.1) $$

In fact, like stationary measures, quasi-stationary distributions can be linked to the limiting behavior of the process $(X_t)_{t\ge0}$, more precisely, one can show that, when it exists for any $j \in \tilde{E}$, the following Yaglom limit does not depend on $j$ and uniquely defines a quasi-stationary distribution called the minimal quasi-stationary distribution:

<footnote>*Université Sorbonne Paris Nord, LAGA, CNRS, UMR 7539, Laboratoire d'excellence Inflamex, F-93430 Villetaneuse, France. cerf@math.univ-paris13.fr</footnote>
$$ \nu^*(i) = \lim_{t \to \infty} \mathbb{P}_j(X_t = i | t < T), \quad \forall i \in \tilde{E}. \qquad (1.2) $$

One can also remark that (1.1) implies that for any quasi-stationary distribution $\nu$, $T$ is exponentially distributed under distribution $\mathbb{P}_\nu$ [2, Theorem 2.2. p. 19], meaning that if we denote by $\theta(\nu)$ its parameter, we have for all $t > 0$

$$ \mathbb{P}_{\nu}(T > t) = e^{-\theta(\nu)t}. \qquad (1.3) $$

The parameter $\theta(\nu)$ is sometimes called the exponential rate of survival of $\nu$ and is maximal for the minimal quasi-stationary distribution $\nu^*$

$$ \theta(\nu^*) = \sup\{\theta(\nu), \nu \text{ is a quasi-stationary distribution of } X\}. $$

Hence, studying the long-time behavior of an absorbed process $(X_t)_{t \ge 0}$ appears as strongly linked to the study of its minimal quasi-stationary distribution and of its parameter. Moreover, (1.3) shows that a necessary condition for the existence of quasi-stationary distributions is the existence of an exponential moment for the time of absorption $T$ [5], i.e

$$ \theta^* := \sup\{\theta > 0, \exists i \in \mathbb{N}^* : \mathbb{E}_i[e^{\theta T}] < \infty \} > 0, \qquad (1.4) $$

and we call $\theta^*$ the exponential rate of survival of the process $(X_t)_{t \ge 0}$. For a complete overview on quasi-stationary distribution, the reader can refer to the book by Collet et al. [2].

In this paper, we study the quasi-stationary distributions of a birth-and-death process on $\mathbb{N}$, with absorption at 0. The applications of birth-and-death processes in biology to the study of the dynamics of populations have motivated several authors to look at the quasi-stationary distributions of such processes [9]. In fact, it has been shown that the condition $\{\theta^* > 0\}$ is not only necessary but sufficient for the existence of quasi-stationary distributions [4]. Moreover, in this case, for any given $\theta \in (0, \theta^*]$, one can construct a unique quasi-stationary distribution $\nu_\theta$ with exponential rate of survival $\theta$ of $(X_t)_{t \ge 0}$ and vice-versa. And it is also the parameter of the minimal quasi-stationary distribution $\nu^*$ defined by (1.2), i.e

$$ \theta^* = \theta(\nu^*). $$

Therefore, it is crucial to be able to compute or at least approximate the minimal rate of survival $\theta^*$ if we want to understand the quasi-stationarity of a birth-and-death process. In some cases, authors have been able to give an explicit characterization of $\theta^*$, like for the symmetric random walk or the linear birth-and-death chain [11]. But other more difficult or general cases are left open problems and still studied [3], [1]. The aim of this paper is to focus on the case of the $M/M/\infty$ queue.

Let us now formally introduce our process of interest. Let $(X_t)_{t \ge 0}$ be a continuous-time birth-and-death Markov chain on $\mathbb{N} = \{0, 1, 2, \dots\}$, with $\Delta = \{0\}$ as an absorbing state, counting the number of customer in a queue system with rate matrix $Q := (q_{i,j})_{i,j \in \mathbb{N}}$ given by :

$$ q_{i,i+1} = a, \quad q_{i,i-1} = iq, \quad q_{i,i} = -(a+iq), \quad \text{for } i \in \mathbb{N}^*. $$
In this process, a new customer arrives at rate $a > 0$ while each customer is served at rate $q > 0$. Thus, it is usually called the $M/M/\infty$ queue in relation to Kendall's notation in queueing theory: Makovian arrivals/Markovian service time/ infinite number of servers. These processes are of great interest in queueing theory and have been studied by computer scientists for a long time. In particular, in [7] Guillemin and Simonian computed a formula for the Laplace transform of excursion times above any given level of the $M/M/\infty$ queue using Kummer functions, and in [6] Guillemin and Pinchon managed to get another, simpler formula for the same variable through the study of continued fractions linked to the process.

In an article studying the decay rates of birth-and-death processes, Martínez and Ycart found an upper bound for the exponential rate of survival $\theta^*$ of the $M/M/\infty$ queue and conjectured its exact value [8]. We validate this conjecture in this article, proving the following result:

**Theorem 1.1.** The exponential rate of survival $\theta^*$ of $(X_t)_{t \ge 0}$ is the unique solution in $(0, q)$ of:

$$1 = \frac{a}{q} \int_{0}^{1} (1-x)^{-\frac{\theta}{q}} e^{-\frac{ax}{q}} dx. \qquad (1.5)$$

In a first part, we use the work of Guillemin and Pinchon [6] to give a first characterization of $\theta^*$ using a special function. Then, by complex analysis arguments, we prove that this first characterization is equivalent to the one of Theorem 1.1.

## 2 Laplace transform of the time of absorption

Our first characterization of the exponential rate of survival of $(X_t)_{t \ge 0}$ is given by its definition (1.4) as the first singularity point of the Laplace transform of the time of absorption of the process. Remark that, thanks to the irreducibility of $(X_t)_{t \ge 0}$ the point of explosion of $\theta \mapsto \mathbb{E}_i[e^{\theta T}]$ does not depend on $i$, so we may only consider the trajectories of the process starting at 1 and write

$$\theta^* = \sup\{\theta > 0, \mathbb{E}_1[e^{\theta T}] < \infty\}. \qquad (2.1)$$

Guillemin and Pinchon [6] made an exhaustive study of the excursions of the non-killed $M/M/\infty$ queue. In particular, they were able to compute an explicit formula for the Laplace transform of the duration of an excursion by an $M/M/\infty$ queue above any given state $C \in \mathbb{N}$. We use this to compute the Laplace transform of $T$ as the length of an excursion above level 0.

**Proposition 2.1** (Laplace transform of $T$). For any $s \in \mathbb{C} \setminus \{0, -1, -2, \dots\}$ and $x \in \mathbb{C}$, define

$$\bar{\gamma}(s, x) := \sum_{k=0}^{\infty} \frac{(-x)^k}{(k+s)k!}. \qquad (2.2)$$
The Laplace transform of $T = \inf\{t > 0, X_t = 0\}$ is given by :

$$ \mathbb{E}_1[e^{\theta T}] = \frac{a - \theta}{a} - \frac{1}{\frac{a}{q} e^{-\frac{a}{q}\bar{\gamma}(-\frac{\theta}{q}, -\frac{a}{q})}}, \quad \text{for any } \theta > 0. \qquad (2.3) $$

*Proof.* Guillemin and Pinchon only give the formula when the serving rate is $q = 1$: consider a $M/M/\infty$ queue $(Y_t)_{t\ge0}$ with arrival rate $\tilde{a}$ and serving rate 1 and denote $\tilde{T} = \inf\{t > 0, Y_t = 0\}$, then we have for any $\theta > 0$

$$ \mathbb{E}_1[e^{\theta \tilde{T}}] = \frac{\tilde{a} - \theta}{\tilde{a}} - \frac{1}{\tilde{a} e^{-\tilde{a} \tilde{\gamma}(-\theta, -\tilde{a})}}. \qquad (2.4) $$

We recover the formula for $(X_t)_{t\ge0}$ by a change of time. Indeed, let $(\tilde{X}_t)_{t\ge0} := (X_{\frac{t}{q}})_{t\ge0}$. Then, $(\tilde{X}_t)_{t\ge0}$ is still a $M/M/\infty$ queue but with modified transition rates : the arrival rate is now $\tilde{a} = \frac{a}{q}$ and the serving rate is 1. Moreover, its time of death $\tilde{T} := \inf\{t > 0, \tilde{X}_t = 0\}$ is just a deformation of the one of $(X_t)_{t\ge0}$ :

$$ \tilde{T} = qT. $$

Therefore we have

$$ \mathbb{E}_1[e^{\theta T}] = \mathbb{E}_1[e^{\frac{\theta}{q} \tilde{T}}], $$

and we can use (2.4) to obtain (2.3). $\square$

In the same work, Guillemin and Pinchon [6] proved that $\bar{\gamma}(\cdot, -\frac{a}{q})$ admits an unique root in $(-1, 0)$ which gives the first singularity point of $\mathbb{E}[e^{\theta T}]$, namely $\theta^*$ the minimal rate of survival of $(X_t)_{t\ge0}$.

**Lemma 2.2** (Characterization of $\theta^*$). The exponential rate of survival $\theta^*$ is the unique solution in $(0, q)$ of

$$ \bar{\gamma}(-\frac{\theta^*}{q}, -\frac{a}{q}) = 0, \quad \text{i.e.} \quad \sum_{k=0}^{\infty} \frac{\left(\frac{a}{q}\right)^k}{(k - \frac{\theta^*}{q})k!} = 0. \qquad (2.5) $$

*Proof.* It is a direct application of (2.1), (2.3) and of the fact that $\bar{\gamma}(\cdot, -\frac{a}{q})$ has a unique root in $(-1, 0)$. $\square$

To conclude this first part, note that the definition (2.2) of $\bar{\gamma}$ implies that for any fixed $x \in \mathbb{C}$, the function $s \mapsto \bar{\gamma}(s, x)$ is meromorphic on $\mathbb{C}$ with the negative integers as poles. Moreover, for $s, x > 0$, $\bar{\gamma}(s, x)$ admits an integral representation which is linked to the lower incomplete gamma function $\gamma(s, x)$, indeed we can write

$$ \begin{align} \bar{\gamma}(s, x) &= \frac{1}{x^s} \sum_{k=0}^{\infty} (-1)^k \frac{x^{k+s}}{(k+s)k!}, \notag \\ &= \frac{1}{x^s} \int_0^x \sum_{k=0}^{\infty} (-1)^k \frac{t^{s+k-1}}{k!} dt, \tag{2.6} \\ &= \frac{1}{x^s} \int_0^x t^{s-1} e^{-t} dt = \frac{1}{x^s} \gamma(s, x). \notag \end{align} $$
This integral form acts as a link with the work of Martínez and Ycart we present in the next section.

### 3 Generating function of the minimal quasi-stationary distribution

In this section, we study $\theta^*$ using its characterization as the rate of survival of the minimal quasi-stationary distribution $\nu^*$, which can be written as follows.

**Proposition 3.1.** Let $\nu$ be a quasi-stationary distribution of $(X_t)_{t \ge 0}$, then its parameter $\theta(\nu)$ satisfies :

$$ \nu Q|_{\{1,2,...\}} = -\theta(\nu)\nu \quad \text{and} \quad \theta(\nu) = Q(1,0)\nu(1). \qquad (3.1) $$

Moreover, for the minimal quasi-stationary distribution $\nu^*$,

$$ \theta(\nu^*) = \theta^*. $$

This characterization is the most commonly used when computing the quasi-stationary distributions of birth and death processes : from (3.1) one can get a functional equation on the generating function of $\nu^*$. This is the method used by Martínez and Ycart [8] to get the following result on the quasi-stationary distributions of $(X_t)_{t \ge 0}$.

**Proposition 3.2 (Martínez, Ycart 2001).** Let $\nu$ be a q.s.d of the process $(X_t)_{t \ge 0}$ and denote by $g_\nu : s \mapsto \sum_{k=1}^\infty \nu(k)s^k$ its generating function. Then $g_\nu$ is given for any $s \in (0,1)$ by :

$$ g_{\nu}(s) = 1 + (1 - s)^{\frac{\theta(\nu)}{q}} e^{\frac{as}{q}} \left(-1 + \frac{a}{q} \int_{0}^{s} (1-x)^{-\frac{\theta(\nu)}{q}} e^{-\frac{ax}{q}} dx\right), \qquad (3.2) $$

where $\theta(\nu) = q\nu(1)$.

Moreover, they remarked that the function $\theta \mapsto \frac{a}{q} \int_0^1 (1-x)^{-\frac{\theta}{q}} e^{-\frac{ax}{q}} dx$ is continuous and strictly increasing, with values ranging from $1 - e^{-\frac{a}{q}}$ to $+\infty$. Hence, there exists a unique $\tilde{\theta} \in (0,q)$ such that

$$ \frac{a}{q} \int_{0}^{1} (1-x)^{-\frac{\tilde{\theta}}{q}} e^{-\frac{ax}{q}} dx = 1. $$

Therefore, if we consider a quasi-stationary distribution $\nu$ of $(X_t)_{t \ge 0}$ and suppose that $\theta(\nu) > \tilde{\theta}$, then by (3.2) we have $g_\nu(s) > 1$ for $s$ close enough to 1 which contradicts the fact that $g_\nu$ is a generating function of a probability measure. So

$$ \theta^* \le \tilde{\theta}. $$

Through numerical simulations, Martínez and Ycart conjectured that this last inequality is in fact an equality. Thanks to the characterization of Lemma 2.2 we can prove this fact. We start the proof with two technical lemmas.
Firstly, we want to understand the domain of definition of the function F given by

$$F : (s, x) \mapsto -x \int_{0}^{1} (1-y)^s e^{xy} dy. \qquad (3.3)$$

and its properties over it.

**Lemma 3.3.** Denote $\Omega := \{s \in \mathbb{C}, \Re(s) > -1\}$. Then F verifies :

* for any fixed $x \in \mathbb{C}$, the function $s \mapsto F(s, x)$ is holomorphic on $\Omega$;

* for any fixed $s \in \Omega$, the function $x \mapsto F(s, x)$ is holomorphic on $\mathbb{C}$.

*Proof.* We use a classic result on holomorphicity for functions defined by an integral (see for example [10, Theorem I.7. p. 308]). Let us fix $x \in \mathbb{C}$.

First, for $y \in (0, 1)$, the function $s \mapsto (1-y)^s e^{xy}$ is holomorphic on $\Omega$, as can be seen by writing it as

$$(1 - y)^s e^{xy} = e^{s \ln(1-y) + xy}.$$

Secondly, we show that for $s$ in any compact subdomain $K$ of $\Omega$, the function $y \mapsto (1-y)^s e^{xy}$ is dominated by a positive and integrable function on $(0, 1)$. But, for such a set $K$, there exists $r_{\min}$ such that for any $s \in K$

$$\Re(e(s)) > r_{\min} > -1.$$

Therefore, for any $s \in K$ and $y \in (0, 1)$

$$|(1 - y)^s e^{xy}| = (1 - y)^{\Re(e(s))} e^{\Re(e(x)y)} \le (1 - y)^{r_{\min}} e^{\Re(e(x)y)}.$$

Since $r_{\min} > -1$, the function $y \mapsto (1-y)^{r_{\min}} e^{\Re(e(x)y)}$ is indeed positive and integrable on $(0, 1)$.

This also implies that for fixed $s \in \Omega$, the function $y \mapsto (1-y)^s e^{xy}$ is integrable on $(0, 1)$. These three assertions ensure that $s \mapsto F(s, x)$ is holomorphic on $\Omega$.

For the second function, we use similar arguments. Let us fix $s \in \Omega$. For any $y \in (0, 1)$, the function $x \mapsto (1-y)^s e^{xy}$ is holomorphic on $\mathbb{C}$. The second point is the same as before. And, finally, let $C$ be a compact subdomain of $\mathbb{C}$, then, there exists $R_{\max} > 0$ such that for any $x \in C$,

$$\Re(e(x)) \le R_{\max}.$$

Therefore, for any $x \in C$ and $y \in (0, 1)$

$$|(1 - y)^s e^{xy}| \le (1 - y)^{\Re(e(s))} e^{R_{\max}y},$$

which concludes the proof.

<figure><img src="image_2.png" /></figure>

We remark that the expression (3.3) is not far from the integral representation of $\bar{\gamma}$ given by (2.6). In fact, we can prove the following link between F and $\bar{\gamma}$.
**Lemma 3.4.** For any $s, x \in (0, \infty)$, we have the following identity :

$$F(s, x) = 1 - se^{x\bar{\gamma}(s, x)}. \qquad (3.4)$$

*Proof.* Let $s, x > 0$, taking $u = 1 - y$ under the integral in (3.3) we have:

$$F(s, x) = -xe^x \int_0^1 u^s e^{-ux} du.$$

We integrate by parts and get:

$$\begin{aligned} F(s, x) &= -xe^x \left(-\frac{e^{-x}}{x} + \frac{s}{x} \int_0^1 u^{s-1} e^{-ux} du\right), \\ &= 1 - se^x \int_0^1 u^{s-1} e^{-ux} du. \end{aligned}$$

Finally we take $y = ux$ under the integral, it follows:

$$F(s, x) = 1 - se^x \frac{1}{x^s} \int_0^x y^{s-1} e^{-y} dy = 1 - se^x \bar{\gamma}(s, x),$$

using the integral form of $\bar{\gamma}$ given by (2.6).

<figure><img src="image_3.png" /></figure>

Recall that we want to prove that $\theta^*$ is solution of (1.5), i.e

$$F\left(-\frac{\theta^*}{q}, -\frac{a}{q}\right) = 1,$$

so we want to take $s = -\frac{\theta^*}{q}$ and $x = -\frac{a}{q}$ in (3.4) and use our first characterization of $\theta^*$ (2.5) to conclude. But both conditions $s > 0$ and $x > 0$ are necessary in our proof of Lemma 3.4. Therefore, we need to extend the identity (3.4) to negative value of $s$ and $x$. We do so by complex analysis arguments.

*Proof of Theorem 1.1.* It is enough to show that Identity (3.4) is verified for any $s \in \Omega$ and $x \in \mathbb{C}$, then (1.5) will follow as a corollary of Lemma 2.2. This is done in two steps.

First, let us fix $s > 0$. We know from a previous remark and Lemma 3.3 that both $x \mapsto 1 - se^x \bar{\gamma}(s, x)$ and $x \mapsto F(s, x)$ are holomorphic on $\mathbb{C}$. Moreover, we showed in Lemma 3.4 that they are equal on the real half-line $(0, +\infty)$ so, by analyticity, they are equal on the plane $\mathbb{C}$. Hence, we have for any $x \in \mathbb{C}$ that for any $s > 0$

$$F(s, x) = 1 - se^{x\bar{\gamma}(s, x)}.$$

Therefore, we can proceed to the second step and fix $x \in \mathbb{C}$ and use symmetric arguments to extend the last equality, namely (3.4), to $s \in \Omega$.

Finally, since $\theta^*$ is the unique solution in $(0, q)$ of (2.5), it is also the unique solution in $(0, q)$ of (1.5), which concludes the proof.

<figure><img src="image_4.png" /></figure>

**Acknowledgments.** We acknowledge financial support by the Investissements d'Avenir programme 10-LABX-0017, Sorbonne Paris Cité, Laboratoire d'excellence INFLAMEX.
References

[1] J. R. Chazottes, P. Collet, and S. Méléard, *Large population limit of the spectrum of killed birth-and-death processes*, 2022, arXiv:2204.10748.

[2] P. Collet, S. Martínez, and J. San Martín, *Quasi-stationary distributions. markov chains, diffusions and dynamical systems*, Berlin: Springer, 2013.

[3] P. Coolen-Schrijner and E. A. van Doorn, *Quasi-stationary distributions for birth-death processes with killing*.

[4] P. Ferrari, S. Martínez, and P. Picco, *Existence of non-trivial quasi-stationary distributions in the birth-death chain*, Appl. Probability vol 24 (1992), 795-813.

[5] P. Good, *The limiting behavior of transient birth and death processes conditioned on survival*, Journal of the Australian Mathematical Society 8 (1968), no. 4, 716-722.

[6] F. Guillemin and D. Pinchon, *Continued fraction analysis of the duration of an excursion in an M/M/∞ system*, J. Appl. Probab. 35 (1998), no. 1, 165-183.

[7] F. Guillemin and A. Simonian, *Transient characteristics of an M/M/∞ system*, Advances in Applied Probability 27 (1995), no. 3, 862-888.

[8] S. Martínez and B. Ycart, *Decay rates and cutoff for convergence and hitting times of Markov chains with countably infinite state space*, Adv. Appl. Probab. 33 (2001), no. 1, 188-205.

[9] S. Méléard and D. Villemonais, *Quasi-stationary distributions and population processes*, Probability Surveys 9 (2011).

[10] H. Queffélec and C. Zuily, *Analyse pour l'agrégation: cours et exercices corrigés*, Je prépare, Dunod, 2020 (French).

[11] E. A. van Doorn, *Quasi-stationary distributions and convergence to quasi-stationarity of birth-death processes*, Adv. Appl. Probab. 23 (1991), no. 4, 683-700.