{'fraction_non_alphanumeric': 0.07168744563641635, 'fraction_numerical': 0.01587416642505074, 'mean_word_length': 3.282122905027933, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Services within a busy period of an M/M/1 queue and Dyck paths

We analyze the service times of customers in a stable M/M/1 queue in equilibrium depending on their position in a busy period. We give the law of the service of a customer at the beginning, at the end, or in the middle of the busy period. It enables as a by-product to prove that the process of instants of beginning of services is not Poisson. We then proceed to a more precise analysis. We consider a family of polynomial generating series associated with Dyck paths of length 2n and we show that they provide the correlation function of the successive services in a busy period with (n+1) customers.


Introduction
The M/M/1/∞/FIFO queue (or M/M/1 queue) is the queue with a Poissonian arrival stream, exponential services, a single server, an unlimited buffer capacity, and a First-In-First-Out service discipline. It can be argued that the M/M/1 queue is the most elementary and the most studied system in queueing theory, see for instance [3,11,8,9]. Quoting [9], "most likely, any book with queueing in the title has something to say on the subject".
Let λ be the intensity of the Poisson arrival process and let µ be the parameter of the exponential service times. Assume that the stability condition λ < µ holds and consider the queue in equilibrium. Our objective is to get precise information on the distribution of the service of a customer based on its position in the busy period.
First of all, recall that the distribution of the first, respectively last, service is an exponential of parameter µ, respectively (λ + µ). We are then able to compute the distribution of a service in the "middle" of a busy period (i.e. neither at the beginning nor at the end). As a by-product, we also get the distribution of the duration between two successive beginning of services. Since it is not an exponential, we conclude that the point process of the instants of beginning of services is not Poisson (as opposed to the point process of completion of services).
Then we study the service time of the k-th customer in a busy period of length n + 1 (i.e. containing n + 1 customers). Consider a busy period conditionned to be of length n + 1, and let (q i ) 0,...,2n+2 be the corresponding embedded queue-length excursion. Its trajectories are equiprobable and it is easy to see that they are in bijection with Dyck paths of length 2n. If we condition (q i ) 0,...,2n+2 to be associated with a given Dyck path π of length 2n then we observe that the law of the service time of the k-th customer is equal to the convolution product of l k + 1 exponentials of parameter λ + µ where l k is the length of the intersection of π with the line y = x − 2k. By summing over Dyck paths of length 2n, we get an expression for the joint law of the services in a busy period of length n+1. Then using elementary properties of Dyck paths, we obtain results on services within a busy period somewhat difficult to obtain by direct probabilistic arguments (Section 4). The correlation function of the services is a natural generating polynomial of Dyck paths following a simple integral recursion (Section 5).
Using the combinatorial properties of lattice paths to study the busy period of simple queues is classical, see [4,6,12] and references therein. In these articles, quantities such that the area swept by the queue-length process during a busy period are studied, with a much more involved combinatorial analysis than what is presented below for the sequence of services within a busy period. This should come as no surprise. The area and related quantities, are derived by counting in a Dyck path the number of ascents and descents of a given vertical coordinate (Dyck paths are lattice paths in N × N, see Section 3). On the contrary, the sequence of services is derived by counting in a Dyck path the number of ascents of a given horizontal coordinate (roughly speaking). This is in essence like working with generating polynomials of Dyck paths in non-commuting variables. It is therefore hopeless to get as precise information.

In the Middle of the Busy Period
Given a positive real random variable X with law µ, denote its Laplace transform by Ψ X (s) = Ψ µ (s) = exp(−sx)dµ(x), s ∈ C, Re(s) ≥ 0. We write L[X | A] = P{X ∈ · | A} for the conditional law of X given an event A. The corresponding Laplace transform is denoted Ψ X|A (s). The convolution product of two probability distributions µ and ν is denoted by µ ⋆ ν. The indicator function of a subset A of a set is denoted by ½ A . It is convenient to denote by Exp(a) the exponential distribution of parameter a defined by Exp(a)[x, +∞) = exp(−ax), x ∈ R + . Recall that Ψ Exp(a) (s) = a/(a + s).
We consider an M/M/1 queue with the following notations. Let (A n ) n∈Z be the arrival Poisson process of intensity λ. Let (τ n ) n∈Z be the inter-arrival times, with τ n = A n+1 − A n . Denote by (σ n ) n∈Z the service times of the customers. The sequence (σ n ) n is i.i.d. and σ 0 ∼ Exp(µ). We assume that the stability condition λ < µ is satisfied, and we consider the queue in equilibrium. Let (Q t ) t∈R be the queue-length process, where Q t is the number of customers either in service or in the buffer at time t.
The state of the server can be described as an alternating sequence of idle and busy periods. A busy period is a maximal period during which Q t > 0. An idle period is a maximal period during which Q t = 0. The length |B| of a busy period B (not to be confused with its duration) is the number of customers served during the busy period. Throughout, when we consider a generic busy period B, we denote for simplicity by σ 0 , . . . , σ |B|−1 and τ 0 , . . . , τ |B|−1 respectively the service times and the inter-arrival times of the different customers in the busy period.
Lemma 2.1. Let ∆ n be the event that a generic busy period consists of n + 1 customers, then The justification is easy. The durations of successive busy periods and idle periods are independent random variables. The duration of an idle period is clearly distributed as Exp(λ). The distribution of a busy period is more complex. The next results can be found for instance in [3, Chapter II.2.2] or [11,Chapter 1.2]. The probability that a busy period B consists of (n + 1) customers is given by where C n is the n-th Catalan number, see §3. Let δ n be the conditional law of the duration of a busy period, given that the length of the busy period is (n + 1). The Laplace transform of δ n is given by Hence, δ n is the distribution of the sum of (2n + 1) i.i.d. r.v.'s of law Exp(λ + µ).
Given two independent random variables X ∼ Exp(α) and Y ∼ Exp(β), where α, β ∈ R * + , recall that Using elementary arguments based on the memoryless property of the exponential distribution, we get: Furthermore, remarking that {|B| = 1} = {σ 0 ≤ τ 0 } and using (2.4), it follows that: Our goal is now to derive the law of a service in the middle of B, i.e. of a service which is neither the first nor the last one (assuming that |B| > 2). Let σ * be the service of a generic customer numbered * and let B be the busy period it belongs to. Define the events Clearly the four events are disjoint and P{E o ∪ E f ∪ E l ∪ E m } = 1. Since the lengths of successive busy periods are i.i.d., we obtain immediately that .
That is, After simplification of the above expression, we obtain the Laplace transform of the conditional law of σ * on the event E m : As a by-product, we can prove that the process of instants of beginning of services is not a Poisson process, in contrast with the process of completion of services (departure instants) which is Poisson of intensity λ according to Burke Theorem [2,7]. Let us detail the argument. Let ξ * be the difference between the instants of beginning of services of two generic successive customers numbered * and ( * + 1). Let B be the busy period of * and let ν be the first idle period following B (ν ∼ Exp(λ)). Using (2.5), (2.6), we get immediately that Since we have just computed Ψ σ * |Em (s), we deduce the Laplace transform of ξ * : We check on this expression that E[ξ * ] = 1/λ and we have E[ξ 2 * ] = λ 3 −µλ 2 +µ 3 +µ 2 λ λ 2 µ 2 (λ+µ) . In particular, we have E[ξ 2 * ] < E[d 2 * ] = 2/λ 2 , where d * is a generic inter-departure time.
In particular, C n is the number of Dyck paths of length 2n. A Dyck path of length 2n is a path in the lattice N × N which begins at the origin (0, 0) ends at (0, 2n) and with steps of type (1, 1) or (1, −1). Denote by D n the set of Dyck paths of length 2n, observe that D 0 is a singleton whose element is the unique Dyck path of length 0. We now define a family of polynomials related to Dyck paths. Let π ∈ D n and let γ j be the line y = x − 2j, for j ∈ {0, . . . , n − 1} and denote by α j the length of the intersection of γ j with π (equivalently α j + 1 is the number of lattice points common to π and γ j ). We introduce two polynomials P π and R π defined by P π (y 0 , y 1 , . . . , y n−1 ) = Let (P n ) n∈N and (R n ) n∈N be the two families of polynomials defined by P n = π∈Dn P π , R n = π∈Dn R π . Clearly P n and R n are homogeneous polynomials of degree n over the n variables y 0 , y 1 , . . . , y n−1 .

The Law of the Services in a Busy Period
Recall that the queue-length process (Q t ) t∈R is a continuous time Birth-and-Death process on N with generator P such that P n,n+1 = λ, n ≥ 0; P n,n−1 = µ, n ≥ 1; P n,m = 0, |n−m| ≥ 2. Let (q n ) n∈Z denote the Markov chain embedded at its jump instants. More precisely, let T be the point process obtained as the superposition of the arrival and departure processes and let (T n ) n∈Z be its points with the convention T 0 = A 0 . Then we set q n = Q T − n . The transition matrix of (q n ) n∈Z is given by and p i,j = 0 otherwise. A busy period corresponds to an excursion of (q n ) n∈Z from 0 to its first return to 0. With the same numbering convention as in Section 2, the generic busy period B consists of n + 1 customers if and only if q 0 = 0, q i > 0, i ∈ {1, · · · , 2n + 1}, q 2n+2 = 0 . On this event, the (random) path with successive edges (i − 1, q i − 1), i ∈ {1, · · · , 2n + 1} is a (random) Dyck path of length 2n. We call it the Dyck path associated with B (see Figure 1). On the event {|B| = n + 1}, all Dyck paths appear with the same probability (the probability of a given trajectory (q n ) n depends only on the number of increasing and decreasing jumps, see (4.1)). On the event that |B| = n + 1 and that the associated Dyck path is π ∈ D n , the power of y i−1 in P π is the number of customers which join the system between the the i-th and the (i + 1)-th departures. Combining these observations with the fact that the time between successive transitions of (Q t ) t∈R are independent r.v.'s of law Exp(λ + µ) as long as the queue is non empty, we get : Given that the length of the busy period is n + 1, the conditional density of the random vector (σ 0 , . . . , σ n ) representing the service times of the successive customers is D(y 0 , . . . , y n ) = (λ + µ) 2n+1 C n e −(λ+µ)(y 0 +···+y n−1 ) P n (y 0 , . . . , y n−1 )e −(λ+µ)yn , where P n is the Dyck polynomial of degree n defined in Section 3. where z i = λ+µ λ+µ+s i , ∀i ∈ {0, . . . , n}, and R n is defined in Section 3.
Let us paraphrase the above results in a somewhat more intuitive way. In a busy period of length (n + 1), the conditional law of (σ 0 , . . . σ n ) is the same as the law of (σ 0 , . . .σ n ) that we now describe. The law ofσ n is an Exp(λ + µ) independent of (σ 0 , . . . ,σ n−1 ). Let Π be a r.v. uniformly distributed over D n = {π 1 , . . . , π Cn }. Conditionally on {Π = π i }, the r.v.'sσ j are independent and distributed as the sum of k i j random variables of law Exp(λ + µ), where (k i j − 1) is the exponent of y j in P π i . This is illustrated in Table 1. We now exploit the correspondance with Dyck paths. Let D <i> n be the set of Dyck paths of length 2n where the first return to the axis {(n, 0), n ∈ N}, after the origin (0, 0), occurs at the point (2i, 0), i ∈ {1, . . . , n}. Clearly, the sets D <i> n are disjoint and D n = ∪ n i=1 D <i> n . Furthermore A consequence of the above is the very classical identity on Catalan numbers : Let R n be defined by R n (z 0 , . . . , z n−1 ) = R n (z 0 , . . . , z n−1 ) × z 0 . . . z n−1 , going back to Corollary 4.2, we have Ψ (σ 0 ,...,σn) (s 0 , . . . , s n ) = 1 C n R n (z 0 , . . . , z n−1 ).z n .

Dyck Paths Polynomials
We go back to the family of polynomials (P n ) n∈N defined in Section 3. We are going to use Theorem 4.1 to give nice expressions for the P n 's. Let ∆ n be the event that a generic busy period consists of n + 1 customers. Let A 0 , . . . , A n be borelians of R * + , P{σ i ∈ A i , i = 0, . . . , n | ∆ n } = P{σ i ∈ A i , i = 0, . . . , n; ∆ n } P{∆ n } .
Let L n = P{σ i ∈ A i , i ∈ {0, n}; ∆ n } and for k = 0, . . . , n, let Y k = k i=0 y i and X k = k i=0 x i . Using Lemma 2.1, we have Then, using theorem 4.1, we get   Figure 4: The volumes of the gray areas are P 2 (y 0 , y 1 ) (left) and P 3 (y 0 , y 1 , y 2 ) (right).
This result can also be proved using the theory of species presented in [1]. Finally, using (5.3), the polynomials (P n ) n∈N can be interpreted as volumes. We give a representation of this in Figure 4 for n = 2 and n = 3.

Conclusion.
Here are several other simple models of queues for which the queue-length process is a Birth-and-Death process: the M/M/K/∞ queue, the M/M/∞ queue, or the M/M/K/L queue (K ≤ L < ∞). In each case, if the generic busy period is of length n + 1, we can associate with it a Dyck path of length 2n. However, the different Dyck paths of length 2n are not equiprobable anymore. Hence, we do not get a simple formula for the joint law of the services as in Theorem 4.1.