Thomas Masanet
email: thomas.masanet@univ-lorraine.fr

Pascal Moyal
email: pascal.moyal@univ-lorraine.fr

PERFECT SAMPLING OF STOCHASTIC MATCHING MODELS WITH RENEGING

Keywords: Markov chains, Stochastic matching, Coupling from the past, Graphs Mathematics Subject Classification: Primary 60J10 Secondary 05C70, 68M20

In this paper, we introduce a slight variation of the Dominated Coupling From the Past algorithm (DCFTP) of Kendall, for bounded Markov chains. It is based on the control of a (typically non-monotonic) stochastic recursion by a (typically monotonic) one. We show that this algorithm is particularly suitable for stochastic matching models with bounded patience, a class of models for which the steady state distribution of the system is in general unknown in closed form. We first show that the Markov chain of this model can be easily controlled by an infinite-server queue. We then investigate the particular case where patience times are deterministic, and this control argument may fail. In that case we resort to an ad-hoc technique that can also be seen as a control (this time, by the arrival sequence). We then compare this algorithm to the primitive CFTP one and to the control by an infinite server queue, and show how our perfect simulation results can be used to estimate, and compare, for instance, the loss probabilities of various systems in equilibrium.

Introduction

The study of stochastic matching models is currently a very active line of research in applied probability. It has been demonstrated in various contexts, that these stochastic models are suitable to capture the dynamics of a wide range of real-time random systems, in which elements enter the system at (possibly) random times, with a view to finding a match, that is identified as such following specified compatibility rules, given by a compatibility graph between classes of items. Then, matched couples leave the system right away as soon as they found a match. This is the case in various applications, such as, peer-to-peer applications, job-search, public housing or college allocations, organ transplants, blood banks, car sharing, assemble-to-order systems, and so on. These models have been introduced in [START_REF] Bušić | Stability of the bipartite matching model[END_REF] for bipartite graphs (which is suitable for supply/demands-type applications) and arrivals by couples, as a variant of the seminal works [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF][START_REF] Adan | Exact FCFS matching rates for two infinite multitype sequences[END_REF]. To account for a wider range of applications (e.g., dating websites, crossed kidney transplants, assemble-to-order systems or car-sharing), they have been generalized to general graphs (with simple arrivals) in [START_REF] Mairesse | Stability of the stochastic matching model[END_REF], and then to hypergraphs in [START_REF] Nazari | Reward maximization in general dynamic matching systems[END_REF][START_REF] Rahme | A stochastic matching model on hypergraphs[END_REF] and graphs with self-loops, in [START_REF] Begeot | A general stochastic matching model on multigraphs[END_REF].

Applications such as organ transplants are subject to very strong timing constraints: the patients waiting for a transplant have a finite life time in the system, and similarly, available organs are highly perishable, and must be transplanted very quickly. Hence the need to incorporate an impatience (or reneging) parameter to the system. More precisely, in this paper we address a general stochastic matching model, as defined in [START_REF] Mairesse | Stability of the stochastic matching model[END_REF], in which the elements have a finite (and possibly random) patience upon arrival, before the end of which they must find a match. Otherwise, they renege and leave the system forever. Matching models with impatience have recently been addressed for a bipartite model and the 'N' graph in [START_REF] Castro | Matching queues with reneging: a product form solution[END_REF] for a matching policy of the 'First Come, First Matched' (fcfm) type, and from the point of view of stochastic optimization, for partially static policies, in [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF]. On another hand, in [START_REF] Jonckheere | Generalized max-weight policies in stochastic matching[END_REF], stability conditions, together with moment bounds at equilibrium, have been given for models in which some, but not all, classes of items are impatient, and the matching policy is of the 'Max-weight' class.

However, it is important to observe, first, that the exact computation of the stability regions of matching models is difficult for general graphs, and heavily depends on the matching policy, see e.g. [START_REF] Mairesse | Stability of the stochastic matching model[END_REF][START_REF] Moyal | On the instability of matching queues[END_REF]. Second, the stationary distributions of the models at hand are in general unknown, and little is known about the characteristics of the steady state. In the existing literature, the models implementing the fcfm policy constitute the only exception, in which the stationary distribution is known explicitly. It can often be characterized in a product form, as is shown using dynamic reversibility arguments (see, along the various models, [START_REF] Adan | Reversibility and further properties of FCFS infinite bipartite matching[END_REF][START_REF] Adan | FCFS parallel service systems and matching models[END_REF][START_REF] Begeot | A general stochastic matching model on multigraphs[END_REF][START_REF] Moyal | A product form for the general stochastic matching model[END_REF][START_REF] Comte | Stochastic non-bipartite matching models and order-independent loss queues[END_REF]), for models without reneging. Let us also observe the recent advances in [START_REF] Comte | Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach[END_REF][START_REF] Begeot | Stability regions of systems with compatibilities, and ubiquitous measures on graph[END_REF] concerning the invariance of stationary matching rates on the matching policy for various graphs -thereby showing that all matching policies have the same matching rates as FCFM.

However, in the cases of models with reneging, aside from the particular graph geometries addressed in [START_REF] Castro | Matching queues with reneging: a product form solution[END_REF], no exact results are known. Moreover, fcfm policies are clearly not always the best option in a real-time context: coming back to the case of organ transplants, other criteria must be taken into account, such as the level of emergency, equity, ages of the patients/donor, various levels of compatibilities, and so on. Mimicking the various existing results in queueing theory, implementing policies of the 'Match the Longest queue' (ml) or 'Earliest Deadline First' (edf) type may be profitable to minimize loss, and it is significant that edf does not amount to fcfm if the patience times are random.

Our aim is to analyse matching models with reneging in steady state, for general matching policies. In view of the above discussion, we thus need to assess the stationary distribution of the matching model at hand, without knowledge of this distribution in closed form. As is well known, this task can be handled by simulating perfectly this steady state.

Perfect simulation has been a constantly active line of research in the analysis of stochastic systems, since the pioneering works of Propp and Wilson [START_REF] Propp | Exact sampling with coupled markov chains and applications to statistical mechanics[END_REF], and Borovkov and Foss [START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Borovkov | Two ergodicity criteria for stochastically recursive sequences[END_REF]. The underlying idea is now well known: Consider a discreteevent stochastic system whose stationary distribution is intractable mathematically.

Then we can study the system in steady state, by precisely simulating samples of the stationary distribution, even though the latter is not known in closed form, instead of approximating it by long-run trajectories. Then, various average performance parameters at equilibrium can be assessed by Monte-Carlo techniques.

The celebrated Propp and Wilson algorithm [START_REF] Propp | Exact sampling with coupled markov chains and applications to statistical mechanics[END_REF] is based on coupling-from-the-past (CFTP), namely, all trajectories of the considered Markov chain coalesce before time 0, whenever these trajectories are initiated from all possible states of the chain, far away enough in the past. This phenomenon is closely related to the concept of strong backwards coupling (see e.g. [START_REF] Borovkov | Ergodicity and stability of stochastic processes[END_REF] and Chapter 2.5 of [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF]), and the connections between the two notions are investigated for various cases of stochastic recursions in [START_REF] Foss | Perfect simulation and backward coupling[END_REF]. Strong backwards coupling is the pillar of the construction of the stationary state under general non-Markov assumptions, via the use of renovating events, see e.g. [START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Borovkov | Two ergodicity criteria for stochastically recursive sequences[END_REF]. It is also a tool to construct stationary states on enriched probability spaces, via skew-product constructions, see [START_REF] Lisek | A method for solving a class of recursive stochastic equations[END_REF][START_REF] Anantharam | A correction and some additional remarks on: stationary solutions of stochastic recursions describing discrete event systems[END_REF][START_REF] Moyal | A generalized backward scheme for solving non-monotonic stochastic recursions[END_REF].

As they rely on the exact coalescence of a family of Markov chains, CFTP algorithms are typically adapted to finite-state spaces and to monotonic dynamics, using envelope techniques. Various authors have extended these settings: generalizing the ideas in [START_REF] Foss | Perfect simulation and backward coupling[END_REF], it is proven in [START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF] that geometrically ergodic Markov chains admit a CFTP algorithm of the envelope-type, even if they are not monotonic, a result that was then generalized to a wider class of ergodic Markov chains, in [START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF]. Various related approaches have then been proposed, that all rely on the following intuitive idea: simulating from the past a more 'simple' recursion, and deducing the stationary state of the recursion of interest by comparison. This is the core idea of the so-called 'Dominated coupling from the past' (DCFTP) introduced in [START_REF] Kendall | Perfect simulation for the area-interaction point process[END_REF][START_REF] Kendall | Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes[END_REF] and then [START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF], of the so-called 'Bounding chains' of Huber [START_REF] Huber | Perfect sampling using bounding chains[END_REF][START_REF] Huber | Perfect simulation[END_REF], that are particularly adapted to mechanical-statistical contexts, and of various envelope techniques for queueing systems, see e.g. [START_REF] Bušić | Perfect simulation and non-monotone markovian systems[END_REF]. More recently, DCFTP-related methods has been implemented, together with saturation techniques, to perfectly simulate non-Markov queueing systems, see [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF] for infinite-server and loss queues, and [START_REF] Blanchet | Perfect sampling of gi/gi/c queues[END_REF] for multiple-server queues. This paper is a first contribution to the perfect sampling of stochastic matching models. We introduce two perfect sampling algorithms, Algorithms 2 and 3 below, that produce samples of the stationary distribution of stochastic matching models with reneging, in the case where arrival times are discrete. The first algorithm simply relies on the control of the model at hand by an infinite server queue, an algorithm that would clearly not be optimal in a context of heavy traffic. Indeed, as was observed in [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF], as it relies on the depletion of a corresponding infinite-server model, the coalescence time for Algorithm 2 grows exponentially in function of the arrival rates, see [START_REF] Kelly | Loss networks[END_REF]. Our second algorithm, Algorithm 3, is peculiar to the case where patience times are deterministic (and so the matching policies fcfm and edf are equivalent). In that case, we propose an ad-hoc control of the system simulated backwards in time by the input of the system.

Then, the algorithm substantially reduces the number of operations compared to the primitive CFTP. In particular, if latency is allowed, we show that Algorithm 3 also outperforms the algorithm based on the control by the infinite server queue, Algorithm 2. In fact, both Algorithms 2 and 3 can be seen as particular cases of a more general perfect sampling algorithm for bounded Markov chains, Algorithm 1 below, which we call perfect sampling by control, a condition that is closely related to those under which a DCFTP-type algorithm can be implemented. This paper is organized as follows. After some preliminary in Section 2, we introduce our general perfect sampling algorithm by control in Section 3. In Section 4, we introduce the general stochastic matching model with reneging, and the two corresponding perfect sampling algorithms in sub-sections 4.2 and 4.3.3. The performances of the latter algorithm are investigated in sub-section 4.3.4. We compare the performance of Algorithm 3 to the primitive CFTP algorithm in sub-section 4.5, and to Algorithm 2 in sub-section 4.4, for a model with reneging and latency. A first application to the comparison of the steady-state performances of two matching policy (here, edf -or in other words fcfm -and ml), is provided in sub-section 4.5.

Preliminary

In what follows, R, N, N * and Z denote the sets of real, non-negative integers, strictly positive integers and relative integers, respectively. For any two elements a, b ∈ Z, let

a, b denote the integer interval [a, b] ∩ Z.
Any (simple, finite and undirected) graph G is denoted by G = (V, E), where V is the set of nodes and E is the set of edges for a node i ∈ V. For n ∈ N * , we say that G is of size n if the cardinality |V| of V is n. For any nodes i, j ∈ V, we write ij if i share an edge in G, that is, {i, j} ∈ E. Else, we write i ̸ j. For any set U ⊂ V, we denote by

E(U ) the neighborhood of U , namely, E(U ) = {j ∈ V ∶ i -j for some i ∈ U } .
For simplicity, for all i ∈ V we set E(i) ∶= E({i}), the set of neighbors of node i in V.

Throughout the paper, all considered random variables (r.v.'s, for short) are defined on a common probability space (Ω, F, P). Definition 1. Let X and V be two separable metric spaces. Let k ∈ Z and x ∈ X.

Let f be a measurable mapping from X × V to X, and (v n ) n∈Z be an identically distributed sequence of V-valued r.v.'s. We denote by (X k n (x)) n≥k , the stochastic recursive sequence (SRS) driven by (f, (v n ) n∈Z ), of initial value x at time k. Namely,

(X k n (x)) n≥k is fully determined by the recurrence equation ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ X k k (x) = x ; X k n+1 (x) = f (X k n (x), v n ), a.s. for all n ≥ k.
It is immediate that (X k n (x)) n∈Z is a X-valued Markov chain whenever the sequence (v n ) n∈Z is IID. Conversely, any X-valued Markov chain (Z n ) n∈N of fixed starting time k and initial value x, having transition matrix Q over X, can be represented by the SRS driven by (f, (v n ) n∈Z ), where (v n ) n∈Z is an IID sequence of uniformly distributed r.v.'s on [0, 1] and f is piecewise constant and satisfies for all x 1 , x 2 ∈ X,

λ ({x ∶ , f (x 1 , x) = x 2 }) = Q(x 1 , x 2 ),
for λ the Lebesgue measure, see e.g. Section 2.5.3 of [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF].

Fix an SRS X ∶= (X k n (x)) n≥k . Then for all e ∈ X, we set

τ X,k e (x) = inf {n ≥ k ∶ X k n (x) = e} , the hitting time of value e by (X k n (x)) n≥k . If (v n ) n∈Z is IID, then (X k n (x)
) n≥k is a Markov chain, and the distribution of τ X,k e (x)k is independent of k. In that case, we then denote by τ X e (x), a generic r.v. that is so distributed.

A perfect sampling algorithm by control

In this section we present a perfect simulation algorithm, Algorithm 1, for processes that are bounded, in a sense that we will make precise hereafter.

i ← i + 1 ; end T down ← Tup -1 ; Tup ← 2Tup end for k ← 1 to q do if Y = b k then X ← a k ; /*
i < 0 do X ← f (X, vi) ; i ← i + 1 ; end return X
Algorithm 1: Simulation of the stationary probability of X.

Our procedure is closely related to that of the dominated coupling from the past algorithm introduced by Kendall and Moller in [START_REF] Kendall | Perfect simulation for the area-interaction point process[END_REF][START_REF] Kendall | Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes[END_REF]. Algorithm 1 roughly proceeds as follows: simulating from the past an auxiliary chain Y , until at has reached one of the end points, at which time we start simulating a trajectory of the CTMC X, up to time 0. As will be shown hereafter, under certain conditions the output of Algorithm 1 is sampled exactly from the stationary distribution of X.

Until the end of this section, we fix three separable metric spaces X, Y and V, and

two mappings f ∶ X × V → X and g ∶ Y × V → Y.

A control condition

The control of an SRS of interest by an auxiliary one, is the key to our perfect simulation algorithm. It is defined hereafter, Definition 2. Let (X n ) n∈Z and (Y n ) n∈Z be two SRS, respectively valued in X and Y and q ∈ N * . We say that The following result establishes that under certain conditions including the control of (X n ) n∈Z and (Y n ) n∈Z , Algorithm 1 terminates almost surely, and the output is a sample of the stationary distribution of the SRS (X n ) n∈Z .

(Y n ) n∈Z r-controls (X n ) n∈Z , if there exists b 1 , ..., b r , y ∈ Y and a 1 , ..., a r ∈ X such that For all i ∈ 1, r , k ∈ Z and n ≥ k, [Y k n (y) = b i ] ⇒ [∀x ∈ X, X k n (x) = a i ] . (1
Theorem 1. Suppose that the sequence (v n ) n∈Z is IID, and let X and Y be two SRS respectively driven by (f, (v n ) n∈Z ) and (g, (v n ) n∈Z ). Suppose that X is r-controlled by Y for b 1 , ..., b r , y and a 1 , ..., a r , and that it holds that

P [τ Y bi (y) < ∞] = 1, i ∈ 1, r . (2)
Then Algorithm 1 terminates almost surely, and its output is sampled from the unique stationary distribution of X.

Proof. We first show that Algorithm 1 terminates almost surely. To see this, observe that for any i ∈ 1, r and any N ∈ N,

P ( ⋃ n∈N {τ Y,-2 n bi (y) ≤ 0}) = P ( ⋃ n∈N {τ Y,-2 n bi (y) + 2 n ≤ 2 n }) ≥ P ({τ Y,-2 N bi (y) + 2 N ≤ 2 N }) = P ({τ Y bi (y) ≤ 2 N }) ,
in view of the stationarity of the input. So we obtain that

P ( ⋃ n∈N {τ Y,-2 n bi (y) ≤ 0}) ≥ lim N →+∞ P ({τ Y bi (y) ≤ 2 N }) = P({τ Y bi (y) < +∞}) = 1,
showing that Algorithm 1 terminates almost surely. Now, let N be the backwards coalescence time of the chain X, that is, the smallest starting time for which the CFTP algorithm terminates for X, or in other words

N = min {n ≥ 0 ∶ X -n 0 (x) = X -n 0 (x ′ ) for all x ≠ x ′ ∈ X} . (3)
Let R be the smallest termination time of Algorithm 1. Then, by the very definition of Algorithm 1 and (1) there exists i ∈ 1, q , a time n 0 > 0 such that -R < -n 0 , and

such that X -R -n0 (x) = X -R -n0 (x ′ ) = a i for all x, x ′ ∈ X, x ≠ x ′
, and thereby

X -R 0 (x) = X -R 0 (x ′ ) = X -n0 0 (a i ), for all x, x ′ ∈ X, x ≠ x ′ . (4)
In particular, it naturally follows from (3) that we necessarily have R ≥ N , otherwise all versions of the chain X starting from a time posterior to -N , would have coalesced before 0, an absurdity. In particular, N is almost surely finite. In the terms of [START_REF] Foss | Perfect simulation and backward coupling[END_REF], the vertical backwards coalescence time of X is successful, and so it follows from Theorem 4.1 in [START_REF] Foss | Perfect simulation and backward coupling[END_REF], first, that there exists a unique invariant probability π for the chain X, and second, that the output X -N 0 (x) of the CFTP algorithm when started from any x ∈ X, is sample from π. But it also follows from (4), that

X -R 0 (x) = X -N 0 (x) = X -n0 0 (a i ), for all x ∈ X.
So Algorithm 1 and the CFTP algorithm produce the same output, which completes the proof. ◻ Remark 2. It follows from the equivalence shown in Theorem 4.2 of [START_REF] Foss | Perfect simulation and backward coupling[END_REF] that under the assumptions of Theorem 1, the Markov chain X is uniformly ergodic, since the vertical coalescence time for X is successful.

Renovating events and small sets

Assumption (1) is key to our analysis. Under this control condition the value of the SRS Y forces that of X at time n, whatever the value of X at time N . This is reminiscent of the concept of renovating event, as introduced by Borovkov and Foss, see [START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Borovkov | Two ergodicity criteria for stochastically recursive sequences[END_REF]. Let us remind the following, Definition 3. Let X be an SRS driven by f and (v n ) n∈Z , and (A n ) n∈N be a sequence of events. We say that (A n ) n∈N is a sequence of renovating events of length m and associated mapping h ∶ V m → X for the chain X if for any n ∈ Z, on A n we have

X n+m = h(v n , ..., v n+m-1 ).
Now suppose that (1) holds for a 1 , ..., a r , b 1 , ..., b r and y. Then, it is easily seen that

for all k ∈ Z, i ∈ 1, r and x ∈ X, ({Y k n (y) = b i }) n≥k is a sequence of renovating events of length 1 for the sequence (X k n (x)) n≥k . Indeed, for all n ≥ k, on {Y k n (y) = b i } we get that X k n (x) = a i ,
and therefore

X k n+1 (x) = f (a i , v n ) =∶ h(v n ).
Then, various conditions on the events ({Y k n (y) = b i }) n≥k can be given, that imply that there exist a stationary version of the chain (X n ) n∈N , see e.g. Theorem 2.5.3 and Property 2.5.5 in [START_REF] Baccelli | Elements of queueing theory: Palm Martingale calculus and stochastic recurrences[END_REF].

There is also an insightful connection between the control condition of Definition 2 and the concept of small set, that is recalled hereafter under the formulation of Chapter 5 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF].

Definition 4. For a positive integer m, we say that the subset A ⊂ X is m-small for the Markov chain (X n ) n∈N on X, if there exists η m > 0, and a non-null Borel measure

µ m on X such that ∀x ∈ A, ∀B ∈ B(X), P [X m ∈ B | X 0 = x] ≥ η m µ m (B).
Thus, starting from such set, the chain (partially) regenerates in a finite horizon of size m, since after that, the transitions of the chain do not depend on the starting point x with strictly positive probability. The existence of small sets is of crucial use in the construction of uniformly ergodic Markov chains, see [START_REF] Foss | Perfect simulation and backward coupling[END_REF][START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF][START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF].

It is significant that under the control condition of Definition 2 and (2), the whole set X is small. To see this, observe that for any i ∈ 1, r , for any m ∈ N such that

P [τ Y bi (y) = m -1] > 0,
in view of the Markov property, for all x ∈ X and all borelian subsets B ⊂ X we have

P [X m ∈ B | X 0 = x] ≥ P [{X m ∈ B} ∩ {X m-1 = a i } | X 0 = x] = P [X m-1 = a i | X 0 = x] P [X m ∈ B | {X m-1 = a i } ∩ {X 0 = x}] ≥ P [τ Y bi (y) = m -1] P [X 1 ∈ B | X 0 = a i ] =∶ δ i m µ i m (B).
Hence X is m-small.

The ordered case

A typical context in which the control of the SRS X by the SRS Y occurs, is when the two sequences are constructed on the same input, and their driving maps satisfy some monotonicity properties, which we detail below. Throughout this section, (U, ≺) denotes a partially ordered space, and we define two mappings φ ∶ X → U and

ψ ∶ Y → U.
Definition 5. We say that the mapping f ∶ X → X is dominated (for U, φ and ψ) by

the mapping g ∶ Y → Y, and denote f ≺ U,φ,ψ g, if ∀x ∈ X, y ∈ Y, [φ(x) ≺ ψ(y)] ⇒ [φ ○ f (x) ≺ ψ ○ g(y)] .
In the definition above, U is an auxiliary partially ordered set that is used for comparing f to g via the projections φ and ψ. Observe the following simple particular case, Proposition 1. In the case where X = Y = U, X is partially ordered by ≺ and φ = ψ = i the identity function, we have f ≺ X,i,i g under either one of the conditions below, (i) g is ≺-nondecreasing and pointwise lower-bounded by f ;

(ii) f is ≺-nondecreasing and pointwise upper-bounded by g.

Proof.

Plainly, for all x, y ∈ X such that x ≺ y, if we assume that (i) holds, then we get f (x) ≺ g(x) ≺ g(y), whereas if (ii) holds we obtain that f (x) ≺ f (y) ≺ g(y). ◻ Proposition 2. Let X and Y be two SRS respectively driven by (f, (v n ) n∈Z ) and

(g, (v n ) n∈Z ), where the input (v n ) n∈Z is IID on V. Suppose that f (., v) ≺ U,φ,ψ g(., v)
for all v ∈ V, where U admits the ≺-minimal point o. Suppose also that φ -1 (o) = {a},

that there exists y ∈ Y such that ∀x ∈ X, φ(x) ≺ ψ(y), (5)
and that τ Y b (y) is almost surely finite for some b ∈ ψ -1 (o). Then, Algorithm 1 for y, a and b, terminates a.s., and produces a sample of the unique stationary distribution of X.

Proof. We aim at showing that Y controls X for b, y, a. Let k, n ∈ Z be such that

n > k and Y k n (y) = b. Let x ∈ X. We show by induction on ℓ, that for all ℓ ∈ k, n , φ(X k ℓ (x)) ≺ ψ(Y k ℓ (y)). (6)
First, from ( 5) we get that φ(

X k k (x)) = φ(x) ≺ ψ(y) = ψ(Y k k (y)), so (6) holds for ℓ = k. Suppose that it is true at rank ℓ ∈ k, n -1 , i.e., that φ(X k ℓ (x)) ≺ ψ(Y k ℓ (y)).
Then, from the domination assumption of f by g we obtain that

φ(X k ℓ+1 (x)) = φ(f (X k ℓ (x), v ℓ )) ≺ ψ(g(Y k ℓ (y), v ℓ )) = ψ(Y k ℓ+1 (y)), so (6)
holds at rank ℓ + 1. It is therefore true for all ℓ ∈ k, n . In particular, we have that

φ(X k n (x)) ≺ ψ(Y k n (y)) = ψ(b) = o, implying that X k n (x) = a.
Thus Y controls X, and we conclude using Theorem 1. ◻ As a conclusion, provided that f ≺ U,φ,ψ g, Algorithm 1 provides a perfect sampling algorithm for the SRS X. In fact, in this ordered case, Algorithm 1 is closely related to the DCFTP algorithms of Kendall, see [START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF][START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF]. Specifically, as in [START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF], thanks to [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF] we have an upper bound process Y , that we can simulate backwards in time. We also have a lower bound process, namely the constant process equal to b. Similarly to the sandwiching method in [START_REF] Propp | Exact sampling with coupled markov chains and applications to statistical mechanics[END_REF], we only have to simulate the process Y starting at state y.

When that process meets the lower bound backwards in time, means that coalescence has been detected. Then, as in [START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF][START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF], we simulate X starting from a single state until time 0. Notice that the DCFTP algorithms introduced in [START_REF] Kendall | Geometric ergodicity and perfect simulation[END_REF] and [START_REF] Connor | Perfect simulation for a class of positive recurrent markov chains[END_REF] use geometric ergodicity, and are based on small sets constructions. As we observed above (Section 3.2), the control condition implies the smallness of X, so our approach is reminiscent of this idea.

Observe that similar approaches are used for the perfect sampling of loss queueing systems in [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF] using the domination of the system by an infinite server queue in some sense (an idea that we also use in the construction of Section 4.2 below) and likewise, for the perfect sampling of multiple-server queues in [START_REF] Blanchet | Perfect sampling of gi/gi/c queues[END_REF].

Remark 3. The above DCFTP conditions are in fact reminiscent of stochastic domination conditions for the construction of stationary SRS's in the general stationary ergodic context. For instance, for X = E a lattice space, Condition (i) in Proposition 1 above amounts to condition (H1) in [START_REF] Moyal | A generalized backward scheme for solving non-monotonic stochastic recursions[END_REF] for any SRS X and Y that are respectively driven by f and g, and a common input (v n ) n∈Z . This latter condition guarantees, under general stationary ergodic assumptions, the existence of a stationary version of the SRS X, at least on an extended probability space, provided that a stationary version of the SRS Y exists on the original one. See [START_REF] Lisek | A method for solving a class of recursive stochastic equations[END_REF], and Theorem 3 in [START_REF] Moyal | A generalized backward scheme for solving non-monotonic stochastic recursions[END_REF].

A stochastic matching model with impatience

In this section we address the perfect sampling of the stationary state of a class of models, which we refer to as 'general stochastic matching models with impatience'.

The model

We consider a general stochastic matching model (GM), as was defined in [START_REF] Mairesse | Stability of the stochastic matching model[END_REF]: items enter one by one in a system, and each of them belongs to a determinate class. The set of classes is denoted by V, and identified with 1, |V| . We fix a simple, connected graph G = (V, E) having set of nodes V, termed compatibility graph. Upon arrival, any incoming item of class, say, i ∈ V is either matched with an item present in the buffer, of a class j such that i shares an edge with j in G, if any, or if no such item is available, it is stored in the buffer to wait for its match. Whenever several possible matches are possible for an incoming item i, a matching policy determines what is the match of i without ambiguity. Each matched pair departs the system right away.

A GM model with impatience is a GM model in which each entering item in the system is assigned a patience time upon arrival. If the considered item has not been matched at the end of her patience time, then she leaves the system forever. To formalize this, after fixing the compatibility graph G = (V, E) and the matching policy Φ, we consider that arrivals occur at integer times, i.e., we suppose that the generic inter-arrival time ξ is constant equal to one, and fix two IID sequences (V n ) n∈Z and

(P n ) n∈Z
, where for all n ∈ Z, P n ∈ R + and V n ∈ V respectively represent the patience time and the class of the n-th item entering the system. We denote respectively by

V and P , generic r.v.'s distributed like (V n ) n∈Z and (P n ) n∈Z respectively, and assume throughout that the r.v. P is integrable. The two sequences (V n ) n∈Z and (P n ) n∈Z are not necessarily independent. In particular, it can be the case that the patience time

P n of the n-th item depends on her class V n .
In what follows, we denote by µ the law of V on V.

The class of models defined in Section 4.1 admits the following Markov representation. Define the set

X ∶= {∅} ∪ ∞ ⋃ q=1 (R * + × V) q .
For all t ≥ 0, let Q(t) be the number of customers in the system at time t, and let us define the profile of the system at t, as the following element of X,

X(t) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ((R 1 (t), V 1 (t)) , ⋯, (R Q(t) (t), V Q(t) (t))) if Q(t) ≥ 1, ∅ else, (7)
where for all i ∈ 1, Q(t) , we denote by R i (t) (resp., V i (t)) the remaining patience at time t (resp., the class) of the i-th item in line at time t, in the order of arrivals. If the system is empty at t, we again set X(t) = ∅. Definition 6. We say that the matching policy Φ is admissible if, upon each arrival, the choice of the match amongst compatible items in line at t, if any, is made according to the sole knowledge of X(t), and possibly of a draw that is independent of everything else.

Remark 4. It is easily seen that matching policies that depend only on the arrival times (First Come, First Matched, denoted hereafter by fcfm, or Last Come, First Matched), remaining patience times (Earliest Deadline First, Latest Deadline First), matching policies that depend on the queue sizes of the various nodes (Match the Longest, Match the Shortest, Max-Weight) and priority policies are all admissible. See e.g. [START_REF] Mairesse | Stability of the stochastic matching model[END_REF][START_REF] Moyal | A product form for the general stochastic matching model[END_REF][START_REF] Jonckheere | Generalized max-weight policies in stochastic matching[END_REF] for a detailed presentation of admissible policies for classical matching models.

Set (T n ) n∈Z = (n) n∈Z , the arrival times to the system, and for all n ∈ Z, denote by

X n = X(T - n ) = X(n -)
, the state of the system seen by the customer entered at time n. Then we obtain the following result, Proposition 3. For any admissible matching policy Φ, the profile sequence (X n ) n∈Z is stochastic recursive, driven by the couple sequence ((V n , P n )) n∈Z , and a mapping

f Φ ∶ X × (R + × V) → X that
depends on Φ and possibly on a random draw independent of everything else. In other words we get that

X n+1 = f Φ (X n , (P n , V n )) , n ∈ Z.
Proof. The construction of f Φ is immediate: If the incoming element at n is matched upon arrival, the couple corresponding to its match, determined by Φ, is erased from the vector X n ; else, the couple (V n , P n ) is added at the end of the vector X n . Last, the couples (possibly including the incoming couple (V n , P n )) whose second coordinate is strictly less than 1 at n are erased from the vector X n (because they will have reneged by time n + 1), and the second coordinates of all other couples of X n , if any, decrease by 1. ◻

A first Perfect sampling algorithm

We can then design a first perfect sampling algorithm for matching models with impatience, that is simply based on the control (in the sense of Section 3) by an infinite server system. In this context, we let Y ∶= (Y n ) n∈Z be a R + -valued SRS defined by the recursion

Y n+1 = [max(Y n , P n ) -1] + =∶ g (Y n , P n ) , n ∈ Z. (8)
Then, for all n, Y n can be interpreted as the largest remaining service time of a D/GI/∞ queue of service times (P n ) n∈Z , upon the arrival of the n-th customer. As the generic r.v. P is assumed integrable, it is well known that whenever

P(P ≤ ξ) = P(P ≤ 1) > 0 (9)
the Markov chain (Y n ) n∈Z is positive recurrent: See e.g. Corollary 4.32 in [START_REF] Decreusefond | Stochastic modeling and analysis of telecom networks[END_REF], [START_REF] Thorisson | Coupling, stationarity, and regeneration[END_REF], and the generalization to the case where (P n ) n∈Z is stationary ergodic, combining Lemma 5 of [START_REF] Moyal | Stability of a processor-sharing queue with varying throughput[END_REF] with Corollary 2 in [START_REF] Moyal | On queues with impatience: stability, and the optimality of earliest deadline first[END_REF]. Consider Algorithm 2, which is a declination of Algorithm 1 started with y = m for m defined below, for Y the recursion defined by ( 8), q = 1, a 1 = ∅ and b 1 = 0. Theorem 2. Under condition [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF], the profile Markov chain (X n ) n∈Z admits a unique stationary distribution. If moreover there exists m > 0 such that P(P ≤ m) = 1, then Algorithm 2 terminates almost surely, and its output is sampled from the stationary distribution of (X n ) n∈Z .

Proof. We apply Proposition 2, by setting in this case

φ ∶ X → R + (10) x = ((r 1 , v 1 ), ⋯, (r q , v q )) ≠ ∅ → max {r i ∶ i ∈ 1, q } ∅ → 0.
As any item spends in the system a time that is less or equal to its patience time, for any n ∈ Z, φ(X n ) corresponds to the largest remaining maximal sojourn time in the system of an item in the system just before time T n . Consequently, for any (p, v) ∈ R + × V, for all x ∈ X we obtain that

φ (f Φ (x, (p, v))) ≤ [max (φ (x) , p) -1] + = g (φ (x) , p) . (11)
Therefore, for any x ∈ X and y ∈ R + such that φ(x) ≤ y, for any (p, v), as g(., p) is non-decreasing on R + we get that

φ (f Φ (x, (p, v))) ≤ g (y, p) .
Proposition 2 completes the proof. ◻

Deterministic patience times

Whenever condition [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF] does not hold, the existence and uniqueness of a stationary distribution for the Markov chain (X n ) n∈N are not granted. One then has to resort to ad-hoc techniques to show stability and to sample the stationary state.

In this section, we consider the particular case of the previous model, in which patience times are deterministic. Specifically, we suppose that P ≡ p + ε, for some p ∈ N * and 0 < ε < 1. Assuming that patience times are not integers, while arrivals occur at integer times, allows us to avoid the ambiguous situation in which an element enters the system and finds an element of remaining patience times zero. In practice, any incoming element can either be matched upon arrival, or with any of the p following entering items. If not, the item is lost before the arrival of the p + 1-th element after it, because its remaining time then equals ε -1 < 0. For short, we denote such a matching model by (G, Φ, µ, p).

Clearly, in this context, (9) fails. (Notice that taking p = 0 in the present construction would lead to a system in which no item could ever be matched.) In this section, we show that such systems are nevertheless positive recurrent, and construct an alternative perfect sampling algorithm that is another declination of Algorithm 1, and is again based on the control condition defined in Section 3.

4.3.1.

Alternative Markov representation. In this particular case, the profile Markov chain can be simplified, so as to obtain the following alternate, simpler, Markov representation of the system state, Definition 7. For all n ∈ Z, the word-profile of the system just before time n is defined by the word

Xn = w 1 ⋯w p ∈ (V ∪ {0}) p ,
where for all i ∈ 1, p ,

w i = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩
V n-p+i-1 if the item entered at np + i -1 was not matched before n; 0 else.

.

In particular, if the element entered at time np is still in the system at time n (its class thus appearing as the first letter of the word Xn ), it is either matched with the incoming element at time n, or it is considered lost.

We call X ⊂ (V ∪ {0}) p , the (finite) state space of X. Similarly to Proposition 3, it is immediate that for any admissible policy Φ, the sequence ( Xn ) n∈Z is a Markov chain, and we denote by f Φ , the (deterministic, up to a possible draw that is independent of

everything else) map f Φ ∶ X × V → X, such that Xn+1 = f Φ ( Xn , V n ) , n ∈ Z.
4.3.2. Synchronizing words. For a fixed model (G, Φ, µ, p), with G = (V, E), let V * be the set of words on V. For any word v = v 1 ⋯v l in V * and any X ∈ X, let us denote by W Φ ( X, v) ∈ X, the state of a system started at X and receiving the arrivals v 1 , ..., v l in that order.

Definition 8. Fix a model (G, Φ, µ, p). A word w = w 1 ⋯ w q ∈ V * is said to be

synchronizing, if ∃z(w) ∈ X ∶ ∀x ∈ X, W Φ (x, w) = z(w).
In other words, w is a synchronizing word if all buffers synchronize to some value z(w), whenever they are fed by a common arrival scenario w, whatever the initial state. It is obvious how synchronizing words can be used for perfect simulation. Indeed, if we start the Markov chain at a time -M from all possible states, observing a synchronizing word of length q < M amongst the arrivals (in the sense that the classes of q consecutive incoming items are given by the letters of w, in that order), clearly guarantees that all chains have coalesced by time 0. In fact, recalling Definition 4, it is immediate that whenever there exists a synchronizing word w, then the whole set X is (q + 1)-small for the chain( Xn ) n∈Z . Indeed, for all x ∈ X and B ⊂ X,

P [ Xq+1 ∈ B | X0 = x] ≥ P [{ Xq+1 ∈ B} ∩ {V 0 V 1 ⋯ V q-1 = w} | X0 = x] = P [V 0 V 1 ⋯ V q-1 = w] P [ Xq+1 ∈ B | {V 0 V 1 ⋯ V q-1 = w} ∩ { X0 = x}] = q-1 ∏ i=0 µ(w i )P [ Xq+1 ∈ B | Xq = z] .
In fact, our approach hereafter for perfect simulation is reminiscent of the small-set techniques for exact sampling in [START_REF] Murdoch | Exact sampling from a continuous state space[END_REF][START_REF] Green | Exact sampling for Bayesian inference: towards general purpose algorithms[END_REF][START_REF] Wilson | How to couple from the past using a read-once source of randomness[END_REF]. Specifically, we will use the arrivals of synchronizing words as a control to ensure the coalescence of all versions of the Markov chains.

We first provide a sufficient condition for the existence of synchronizing words, for any discrete matching system. Hereafter, for any k, ℓ

∈ V we write k ℓ if (k, ℓ) ∈ E,
that is, the nodes k and ℓ share an edge in G. Else, we write k ̸ ℓ.

Definition 9. Let w ∈ V * . We say that the word of length 2p,

w = w 1 ⋯ w 2p ∈ V * is strongly synchronizing, if ∀i ∈ 1, p , ∀j ∈ p + 1, p + i , w i ̸ w j .
The term strongly synchronizing is justified by the following result, Theorem 3. In a discrete matching model with impatience (G, Φ, µ, p), any strongly synchronizing word is a synchronizing word.

Proof. Let w = w 1 ⋯ w 2p be a strongly synchronizing word, and let u = w 1 ⋯ w p and v = w p+1 ⋯ w 2p . Let x ∈ X and 0 p = 0 ⋯ 0 p , be the empty state. As u is of length p, any item present in the buffer represented by x is no longer in there after the arrivals represented by u (it is either matched or discarded, possibly just after the arrival of the last item of class w p ). Therefore W Φ (x, u) = u ′ = w ′ 1 , ..., w ′ p where for all i ∈ 1, p , w ′ i = w i if the corresponding item is still in the buffer after these arrivals, or w ′ i = 0 else. As w is strongly synchronizing, for any i ∈ 1, p such that w ′ i ≠ 0 and any j ∈ p + 1; p + i , we have that w ′ i ̸ w j . All elements corresponding to non-zero letters of u ′ are not matched, because their patience necessarily expires before the arrival of a compatible item, and no letters from v can be married to a letter in u ′ . Therefore if j, h ∈ p + 1, 2p are such that the element corresponding to w j is matched to that corresponding to w h if we add v to the empty buffer 0 p , then it is also the case if we add v to the buffer u ′ . In other words, we get that

W Φ (x, w) = W Φ (W Φ (x, u), v) = W Φ (u ′ , v) = W Φ (0 p , v).
As this is true for any x ∈ X, w is a synchronizing word for z(w) ∶= W Φ (0 p , v). ◻

We proceed with two technical lemmas. In what follows, for all a ∈ V ∪ {0} and all k ∈ 0, p we define the following word of length p,

x a (k) = 0⋯0 k a⋯a p-k .
First observe the following, Lemma 1. Consider a matching model with impatience (G, fcfm, µ, p), with matching policy fcfm. Let a ∈ V. Then, for all k ∈ 0, p -1 , for all words w of length p, W Φ (x a (k), w) and W Φ (x a (k + 1), w) differ at most by one letter in some position i (substituting 0 to the i-th letter).

Proof. Let k ∈ 0, p -1 , and write w = w 1 ⋯ w p . With some abuse, in the proof below the matching procedure of the initial state x a (k) (or x a (k + 1)) with the arrival represented by w is itself called W fcfm (x a (k), w) (or W fcfm (x a (k + 1), w)).

If w i ̸ a for all i ∈ 1, p , then we trivially get that

W fcfm (x a (k), w) = W fcfm (x a (k + 1), w).
Else, let i 1 , ..., i l be the indices, in increasing order, of the letters of w matched with letters of x a (k + 1) in W fcfm (x a (k + 1), w). There are three possibilities for the indices (in increasing order) of the letters of w that are matched with letters of x a (k) in W fcfm (x a (k), w) (which we call for short "the indices" in the discussion hereafter):

1. Either the first a of x a (k) is matched in W fcfm (x a (k), w) with a letter of w of indice i 0 < i 1 .Then all the remaining a's in x a (k) are matched in W fcfm (x a (k), w)

exactly as the a's in W fcfm (x a (k+1), w), and so the indices are precisely i 0 , i 1 , ..., i l .

2. Or the first a of x a (k) is not matched in W fcfm (x a (k), w). Then, all the remaining a's of x a (k) are matched in W fcfm (x a (k), w) exactly as the a's in W fcfm (x a (k + 1), w), and the indices are again i 1 , ..., i l .

3. Or, the first matched a of x a (k) in W fcfm (x a (k), w) is matched with the letter of index i 1 in w. Then, in W fcfm (x a (k), w), either the indices of the matched letters of w are the same as in W fcfm (x a (k + 1), w) (and then the last a in x a (k) remains unmatched), or the first pk -1 a's of x a (k) are matched with letters of w at indices i 1 , ..., i l , and the last a is matched with a letter of w of index i l+1 , with i l < i l+1 , in which case the indices are i 1 , ..., i l+1 .

If the indices are i 1 , ..., i l , then W fcfm (x a (k), w) = W fcfm (x a (k + 1), w). If the indices are i 0 , i 1 , ..., i l or i 1 , ..., i l+1 then there is a letter b of w that is not matched with an a of

x a (k+1) in W fcfm (x a (k+1), w), but is matched with an a of x a (k) in W fcfm (x a (k), w).
Then, either that letter b remains unmatched in W fcfm (x a (k + 1), w), in which case W fcfm (x a (k + 1), w) and W fcfm (x a (k), w) differ only at index i 0 (or i l+1 ), where there is a b in W fcfm (x a (k + 1), w) and 0 in W fcfm (x a (k), w). Or, b is matched with a letter c of w in W fcfm (x a (k + 1), w). Then, either the letter c remains unmatched in W fcfm (x a (k), w), in which case W fcfm (x a (k+1), w) and W fcfm (x a (k), w) differ only at the place of that letter c in W fcfm (x a (k), w), where there is a 0 in W fcfm (x a (k +1), w).

Or, c is matched with another letter b ′ in W fcfm (x a (k), w), in which case we can repeat the same procedure for b ′ instead of b. As we have a finite number of letters in w, we eventually stop with a letter being present in a buffer and 0 in the other. In all cases, the buffers W fcfm (x a (k + 1), w) and W fcfm (x a (k), w) differ only by one letter. ◻ For all x ∈ X, let us denote

T (x, a) = Card {letters xi of x ∶ xi -a} .
It follows from the above that Corollary 1. Let w be a word of length 2p such that for some i ∈ 1; p and j ∈ p + 1; p + i , we have w iw j . For such couple {i, j}, and k ∈ 0, 2p , let

x i,j (k) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x wi (k) if k ∈ 0, p -1 , 0 2p if k = p, x wj (2p -k) if k ∈ p + 1, 2p .
Let also u(k) = W fcfm (x i,j (k), w 1 ⋯ w p ), for all k ∈ 0, 2p . Then, there exists an

integer k in 0, 2p -1 , such that u(k) = z 1 ⋯ z p differs from u(k + 1) = z ′ 1 ⋯ z ′
p by only one letter in some position l, such that z lw j , z ′ l = 0, and for all h ∈ 1, p , z ′ h = w h or z ′ h = 0. Moreover we have that T (u(k), w j ) = 1 and T (u(k + 1), w j ) = 0.

Proof. By Lemma 1, for all k ∈ 0, 2p -1 , u(k) and u(k + 1) differ at most by one letter in some position i (one being w i , the other being a 0). Therefore, for all k ∈ 0, 2p -1 , |T (u(k), w j ) -T (u(k + 1), w j )| ≤ 1. Now notice that 2 ≤ T (u(0), w j ), because gathering the words x i,j (0) and w would lead to at least p + 1 w i 's out of 2p letters -so at least two w i must remain in u(0). On the other hand, we also have that T (u(2p), w j ) = 0, because any letter of w 1 ⋯ w p that can be matched with w j get matched in u(2p) with the letters of x i,j (2p). As a consequence, there exists a rank k ∈ 0, 2p -1 such that T (u(k), w j ) = 1 and T (u(k + 1), w j ) = 0. The remaining statements follow readily from Lemma 1. ◻ Theorem 4. Consider a matching model with impatience (G, fcfm, µ, p). Let w be a word of length 2p of V * . Then the following conditions are equivalent:

(i) w is a strongly synchronizing word;

(ii) w is a synchronizing word.

Proof. In view of Theorem 3, only the implication (ii) ⇒ (i) remains to be proven.

For this, we reason by contraposition. So let w be a word of length 2p such that w i -w j for some i ∈ 1; p and j ∈ p + 1; p + i . Let i * ∈ 1; p and j * ∈ p + 1; p + i * such that w i *w j * and j * = inf{j ∈ p + 1; 2p , ∃i ∈ 2pj; p w iw j }. We denote u = w 1 ⋯w p and v = w p+1 ⋯w 2p . Let k * be the integer obtained in Corollary 1 for i ≡ i * and j ≡ j * .

Then, we get u(k * ) = d 1 ⋯d p and u(k * + 1) = e 1 ⋯e p , where u(.) is defined in Corollary 1. We will prove that W fcfm (u(k * ), v) ≠ W fcfm (u(k * + 1), v), which will show in turn that w is not a synchronizing word.

Let i 1 , ..., i l be the indices (in increasing order) of letters of v that are matched with letters of u(k * ) in W fcfm (u(k * ), v), and i ′ 1 , ..., i ′ h be the indices (in increasing order) of letters of v that are matched with letters of u(k * + 1) in W fcfm (u(k * + 1), v). Now let us define the following sets,

⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ I 0 = ∅; I m+1 = I m ∪ {inf {j ∈ p + 1, p + m + 1 ∖ I m ∶ w j -d m+1 }} , m ∈ 0, p -1 .
At each step of this construction we add to the set I m the index of the letter that is matched with d m+1 in W fcfm (u(k * ), v), if any, as in FCFM, d m+1 is matched with the first compatible letter that has not been matched to a previous letter of u * k . In particular, we finally obtain that I p = {i 1 , ..., i l }. In the same way, we define the sets

⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ I ′ 0 = ∅; I ′ m+1 = I ′ m ∪ {inf {j ∈ p + 1, p + m + 1 ∖ I ′ m ∶ w j -e m+1 }} , m ∈ 0, p -1 ,
and the same argument leads to I ′ p = {i ′ 1 , ..., i ′ h }. If in Corollary 1, the letter a that can be matched with w j * in u(k * ) (and be replaced by a 0 in u(k * + 1)) is at position m, then by construction of j * , u(k * ) and u(k * + 1), a will indeed be matched with w j * in u(k * ). So the m-th step is different for W fcfm (u(k * ), v) and W fcfm (u(k * + 1), v). For every other step m ′ , as d m ′ ̸ w j * and e m ′ ̸ w j * , we add the same letter, if any, to I m ′ -1 and I ′ m ′ -1 . So we have I p = I ′ p ∪ {j * }. Let n 1 (resp., n 2 ) be the total number of letters from v that are matched in W fcfm (u(k * ), v) (resp., W fcfm (u(k * + 1), v)). As the total numbers of matched letters are even, both n 1 + |I p | and n 2 + |I ′ p | are even. But as |I p | and |I ′ p | are of different parity, so are n 1 and n 2 . Thus,

W fcfm (x i * ,j * (k * ), w) = W fcfm (u(k * ), v) ≠ W fcfm (u(k * + 1), v) = W fcfm (x i * ,j * (k * + 1), w),
and w is not a synchronizing word. ◻

We have proven that being strongly synchronizing is a necessary and sufficient condition for being a synchronizing word of length 2p in the case where the matching policy is fcfm. It is not the case for all matching policies. For example, for the matching policy lcfm (Last Come, First Matched'), it can be proven that there exists synchronizing words of length ⌊ 3p 2 ⌋, so that any suffix of those words that would not satisfy the p-condition would still be a synchronizing word. However, as we prove hereafter, checking that a word is strongly synchronizing is a simple criterion, that can be used to construct an efficient perfect sampling algorithm.

4.3.3.

A second perfect sampling algorithm. We are now in position to introduce a perfect sampling algorithm for the state of a matching model with deterministic patience.

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Ỹ k k = ∅; Ỹ k n+1 = g( Ỹ k n , V n+1 ) ∶= ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ v 1 ⋯v i V n+1 , if Ỹ k n = v 1 ⋯v i ∈ V i with i < 2p v 2 ⋯v 2p V n+1 , if Ỹ k n = v 1 ⋯v 2p ∈ V 2p
, n ≥ k, in a way that for all k and all n ≥ k + 2p, Ỹ k n represents the last 2p arrivals to the system at time n. Consider Algorithm 3. It consists of another declination of Algorithm 1, started with Ỹ = ∅, for Ỹ the recursion of Definition 10, b 1 , ..., b q , the strongly synchronizing words of the model, and a 1 , ..., a q , the states of X after the arrival of b 1 ,...,b q , respectively.

i < 0 do X ← f Φ ( X, vi) ; i ← i + 1 ; end return X
Algorithm 3: Simulation of the stationary probability of X -Matching model with deterministic patience.

We have the following result, Proposition 4. X is recurrent positive. Moreover, Algorithm 3 terminates a.s., and its output is sampled from the stationary distribution of X.

Proof. We can easily show that Ỹ r-controls X, with q the number of strongly synchronizing word. Let w be a strongly synchronizing word. By Theorem 3, w is a synchronizing word. Thus for all k ∈ Z and n ≥ k, we get in particular that

[ Ỹ k n (∅) = w] ⇒ [∀x ∈ X, Xk n (x) = W Φ (∅, w)] , (12)
which implies that Ỹ controls X over all strongly synchronizing words. We conclude using Theorem 1. ◻ Remark 5. Observe that Ỹ is not irreducible, however it reaches its recurrent class in 2p iterations. So for all strongly synchronizing word w, we still have that

P(τ Ỹ ∅ (w) < ∞) = 1.
4.3.4. Efficiency of Algorithm 3. In this section we analyse the coalescence time of Algorithm 3. For this, one needs to assess the probability that a given input word of length 2p is strongly synchronizing. This is, in turn, a function of µ and of the number of admissible arrival words of length 2p that are strongly synchronizing. The latter number is, clearly, highly dependent on the geometry of the compatibility graph at hand.

Let us first bound the average number of iterations of the algorithm to see the coalescence time, and then for the corresponding horizon in the past, in function of the number of strongly synchronizing words. We have the following, Proposition 5. Let I be the number of iterations of Algorithm 1 to detect coalescence, and T = -p2 I be the corresponding starting time. Then, we have that

E [-T ] ≤ 2p P p,µ ,
where

P p,µ = P [V 1 ⋯V 2p is strongly synchronizing] .
Proof. For any integer n ≥ 1, we let for all i ∈ N * , z n i be the word of length 2p representing the arrivals into the system between time -p2 n + (i -1)2p and time -p2 n + i2p -1 included, in the order of arrivals. We also let

K n = inf {i ∈ N * ∶ z n i is strongly synchronizing} .
The independence of arrivals implies that the r.v.'s K n , n ∈ N * are identically distributed (but not independent) of geometric distribution of parameter P p,µ . Now, it readily follows from Theorem 3, that for all n ∈ N * , I ≤ n in particular if there has been a strongly synchronizing arrival array between times -p2 n and -1 included, that is, if 2pK n ≤ p2 n . Consequently, for all n ∈ N * we get that

P [-T > p2 n ] = P [I > n] ≤ P [2pK n > p2 n ] = P [2pK 1 > p2 n ] .
This readily implies that -T ≤ st 2pK 1 , where ≤ st denotes the strong stochastic ordering.

We deduce that

E [-T ] ≤ 2pE [K 1 ] = 2p P p,µ . ◻
Whenever the arrival measure µ is uniform over V, the latter results specializes as follows,

Corollary 2. If the graph G = (V, E) is of size n and µ is uniform over V, we get the bounds E [-T ] ≤ 2pn 2p N (G, p) , E [I] ≤ 1 + 2pLogn -LogN (G, p) Log2 ,
where N (G, p) is the number of strongly synchronizing words of V * .

Proof. The results readily follow from Proposition 5, observing that in this case

P p,µ = N (G, p) n 2p ⋅ ◻
For a given G and a given p, computing the number N (G, p) of strongly synchronizing words, is of crucial interest to assess the efficiency of Algorithm 1. As Corollary 2 demonstrates, a function of the latter quantity provides bounds for the expected values of |T | and I. We now turn to a specific evaluation of N (G, p), and for this, we first need the following definitions, Definition 11. Let (G = (V, E), Φ, µ, p) be a discrete matching model with impatience. For any strongly synchronizing word w = w 1 ⋯w 2p , the trace of w is defined as the word Z w gathering, in their order of apparences, all distinct letters of the second half of w. In other words, we set

(1) Z w 1 = w p+1 , (2)
For all i ∈ 1, p -1 ,

Z w i+1 = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ Z w i , if w p+i+1 ∈ Z w i ; Z w i w p+i+1 , if w p+i+1 ∉ Z w i ,
and

Z w ≡ Z w p .
In what follows, for any word z = z 1 ⋯ z l , we denote by β(z) the cardinality of the set of nodes that are incompatible with all letters of z, namely

β(z) = Card{v ∈ V ∶ ∀i ∈ 1, l , v ̸ z i }.
We have the following, Proposition 6. Let (G = (V, E), Φ, µ, p) be a discrete matching model with impatience, and let T (G) be the set of words having distinct letters, that form a permutation of the elements of a set U ⊂ V that is such that E(U ) ≠ V. Then, the number N (G, p) of strongly synchronizing words is given by

N (G, p) = ∑ z=z1⋯z l ∈T (G) ∑ {1=k1<k2<⋯<k l <k l+1 =p+1} l ∏ i=1 i ki+1-ki-1 β(z 1 z 2 ⋯z i ) ki+1-ki .
Proof. Let z = z 1 ⋯ z l ∈ V * be a word having l distinct letters. Let us denote, for any word w = w 1 ⋯ w 2p of trace z,

k w i = inf{j ∈ 1, p , w p+j = z i }, i ∈ 1, l ,
the consecutive indexes, in the second half suffix of w, corresponding to the first occurrences of the successive letters of z.

Let 1 = k 1 < k 2 < ⋯ < k l < k l+1 = p + 1 be
a fixed family of integers and w be a word of length 2p. We first show the equivalence between the two following assertions, (i) w is strongly synchronizing, has trace z = z 1 ⋯z l , and

(k w 1 , k w 2 , ..., k w l ) = (k 1 , k 2 , ..., k l ).
(ii) For all i ∈ 1, l , (iia) w p+ki = z i ;

(iib) For all j ∈ k i , k i+1 -1 , w p+j ∈ {z 1 , ⋯, z i } and

w j ∈ E ({z 1 , ⋯ , z i }) c .
Indeed, if (i) holds true then (ii) also holds by induction on i: First, (iia)-(iib) hold true for i = 1. Indeed, for all j ∈ k 1 , k 2 -1 we have that w p+j = z 1 by definition of k 1 and k 2 , and thus, by definition of a strongly synchronizing word, that w j ̸ w p+k1 = z 1 .

Now suppose that (iia)-(iib) hold true for some i -1 ∈ 1, p -1 . Then (iia) holds for i by definition of the trace and of k i . (iib) also holds true by induction on j over k i , k i+1 -1 : First, we have w p+ki = z i by (iia), implying, by definition of a strongly synchronizing word and in view of the induction assumption, that

w ki ∈ E ({w ℓ ∶ ℓ ∈ p + 1, p + k i }) c = E ({w ℓ ∶ ℓ ∈ p + 1, p + k i -1 } ∪ {w p+ki }) c = E ({z 1 , ⋯, z i -1} ∪ {z i }) c = E ({z 1 , ⋯, z i }) c ,
so the properties in (iib) hold for j = k i . Now suppose that they hold true for some j -1 ∈ k i , k i+1 -2 . Then w p+j ∈ {z 1 , ⋯, z i } by the very definition of k i . Thus, as w is strongly synchronizing we have that

w j ∈ E ({w ℓ ∶ ℓ ∈ p + 1, p + j }) c = E ({w ℓ ∶ ℓ ∈ p + 1, p + j -1 } ∪ {w p+j }) c = E ({z 1 , ⋯, z i } ∪ {w p+j }) c = E ({z 1 , ⋯, z i }) c .
Thus (iib) hold true at index i, which completes the proof of (ii). Now suppose that (ii) holds. Then it follows from (iia) and the first property in (iib) that k w i = k i for all i ∈ 1, l . Now fix j ∈ 1, p , and let i be the index in 1, l such that j ∈ k i , k i+1 -1 . Then, in view of (iia)-(iib) we get that

w j ∈ E ({z 1 , ⋯ , z i }) c = E ({w p+1 , ⋯ , z p+j }) c ,
so w is indeed strongly synchronizing. From (ii), w also clearly has trace z, so (i) holds, which concludes the proof of (i) ⇔ (ii). Now, for a fixed trace z, to count the strongly synchronizing words having trace z it thus suffices to count, for all families of integers 1

= k 1 < k 2 < ⋯ < k l < k l+1 = p + 1,
all the words w satisfying (ii). First, the letters at indices k 1 ,...,k l are fixed, and for all i ∈ 1, l we have i possibilities for each letter between indices k i + 1 and k i+1 -1, and β(z 1 ⋯z i ) possibilities for each letter between indices k ip and k i+1 -1p. Therefore, the number of strongly synchronizing words and having z has a trace is given by

N z ∶= ∑ {1=k1<k2<⋯<k l <k l+1 =p+1} l ∏ i=1 i ki+1-ki-1 β(z 1 z 2 ⋯z i ) ki+1-ki . (13)
Last, to get N (G, p) we must sum the above quantity over all possible traces of strongly synchronizing words. To characterize this set, observe that any trace z necessarily has distinct letters, forming a permutation of a set U z ⊂ V. If E(U z ) ≠ V, then there exists a letter i ∈ V ∖ E(U z ), and z clearly is the trace of any word w whose prefix of size p is ii ⋯ i, and whose suffix of size p is a permutation of the elements of U . If now E(U z ) = V, as for any strongly synchronizing word w and having trace z we must have that w p / ∈ E(U z ), leading to an immediate contradiction. Thus it is necessarily and sufficient that E(U z ) ≠ V for z to be a trace, which concludes the proof. ◻ Indeed, any trace containing a 2 can only contain 2 since adding another class will result in having compatible classes which can't be the case for a trace. Conversely, Any other word containing 1 or 3 or 4 is possible as a trace since not having 2 in the word means that the letters of the word are still compatible with the class 1. It is then immediate to compute β(z) for all z ∈ T (G) using [START_REF] Borovkov | Ergodicity and stability of stochastic processes[END_REF]. We obtain

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ N 1 = 3 p , N 2 = 1, N 3 = 2 p , N 4 = 2 p , N 13 = 3 2 4 p -2.3 p , N 14 = 3 2 4 p -2.3 p , N 31 = 1 2 4 p -2 p , N 34 = (p -1)2 p-1 , N 41 = 1 2 4 p -2 p , N 43 = (p -1)2 p-1 , N 134 = 3.2 2p-1 -(2p + 4)3 p-1 , N 143 = 3.2 2p-1 -(2p + 4)3 p-1 , N 314 = 2 2p-1 -4.3 p-1 + 2 p , N 341 = 2.3 p-1 -(p + 1)2 p-1 , N 413 = 2 2p-1 -4.3 p-1 + 2 p , N 431 = 2.3 p-1 -(p + 1)2 p-1 . (14)
For clarity, let us detail one of the above computations, for z = 13. We then have β(1) = |{1, 3, 4}| = 3 and β(13) = |{1, 3}| = 2. Therefore, using (13) we have

N 13 = p ∑ k2=2 1 k2-1-1 β(1) k2-1 2 p+1-k2-1 β(13) p+1-k2 = p ∑ k2=2 3 k2-1 2 p-k2 2 p+1-k2 = 2 × 4 p 3 p ∑ k2=2 ( 3
) k2 = 3 2 4 p -2.3 p . 4
Summing all elements of ( 14) and rearranging, we obtain that

N (G, p) = 1 + 2 2p+3 -3 p+1 -4(p + 3)3 p-1 .
Then, applying Corollary 2 and Jensen's inequality we obtain the following bound for the average number of iterations of Algorithm 1 to detect coalescence,

E [I] ≤ 1 + 2p Logn -LogN (G, p) Log2 = 1 + 4p - Log (1 + 2 2p+3 -3 p+1 -4(p + 3)3 p-1 ) Log2 =∶ B I ,
and the average starting time T to detect coalescence is bounded by -p2 B I . In Table • In the CFTP algorithm, the match of the incoming individuals amounts to an investigation of the set of stored compatible items in a determinate order, and thereby, of a sequence of such operations. Second, so does the test of equality of the current states of all Markov chains, at any given time.

• In Algorithm 3, testing the 'strong synchronizing' property at all time is again a sequence of operations, and so does the construction of the dynamics of the recursion, from the coalescence time on.

To estimate the number of operations in the two algorithms, for two values of p (3 and 6), we have first drawn realizations of Erdös-Rényi graphs G of parameters (n, α), that are conditioned to be connected, for various values of the size n and of the connectivity parameter α. We have then tracked the average number of operations for 10 realizations and multiple values of (n, α).

p = 3 α = 1 8 α = 2 8 α = 3 8 α = 4 8 α = 5 8 n = 4
of both algorithms, on the same graph each time. The results are presented in Table 2 and3.

The results gathered in Tables 2 and3 tend to indicate that Algorithm 3 is much more efficient than primitive CFTP, and that the performance gap is particular important for sparse graphs. This last fact is an intuitively clear consequence of the fact that the proportion of strongly synchronizing words is decreasing in the number of edges.

For α ≥ 3 4 , however, we observe cases where the Algorithm 3 does not terminate in a reasonable amount of time.

Deterministic matching model with latency

It is well known that the primitive CFTP algorithm is in general not a good benchmark in terms of complexity, as it requires the coalescence of a large number of versions of the considered Markov chain -which makes its use unpractical for a large state space. On the other hand, and as previously mentioned, non-trivial deterministic matching models do not satisfy condition [START_REF] Blanchet | Perfect sampling for infinite server and loss systems[END_REF]. This means that the SRS defined by the recursion (2) cannot hit 0, and so we cannot use Algorithm 2 for deterministic matching models. Table 5: Average cputime of the algorithms on standard computer for 10 repetitions with p = 6 and multiple values of (n, α).

In this section we introduce the following variant of the model of Section 4.3: we suppose that latency is allowed, that is, at each instant we suppose that, with a positive probability γ, no item enters the system. In other words, the generic inter-arrival time ξ follows a geometric law of parameter 1γ. The sequences ( Vn ) n∈Z and ( Pn ) n∈Z are then defined as follows:

• If an item enters the system at time n, then Vn is the class of the item entering the system, and Pn = p + ε is the patience of the item entering the system;

• Else, we set Vn = -1 and Pn = 0.

We denote such deterministic model with latency, by (G, Φ, µ, p, γ). Similarly to Section But for all l ∈ 1, k-1 we have that Ŷn-l+1 ≥ Ŷn-l -1, so that by an immediate induction,

Ŷn ≥ p + ε -1 -(k -1) ≥ ε > 0.
◻ As a consequence of Proposition 7, determining when Ŷ = 0 in Algorithm 2 amounts to checking that the last p arrivals are all -1's, meaning that no item has entered the system in the last p instants. In fact, as ii) above has a positive probability, we immediately see that in the present context, Algorithm 2 terminates almost surely.

For any x = x 1 ⋯ x p ∈ X, denote by Definition 13. A word w ∈ (V ∪ -1) * is said to be synchronizing for the deterministic matching model with latency (G, Φ, µ, p, γ) if ∃z ∈ X, ∀x ∈ X, W Φ (x, w) = w x is such that

○ w x = z. (16)
We say that a word w = w 1 ⋯w 2p ∈ (V ∪ -1) * is strongly synchronizing, if ∀i ∈ 1, p , ∀j ∈ p + 1, p + i , w i ̸ w j , where, by convention, ∀v ∈ V, v ̸ -1.

We can then apply the exact same arguments as for Theorems 3 and 4, to show that Proposition 8. Any strongly synchronizing word w ∈ (V ∪ -1) * is also synchronizing word for the deterministic matching model with latency (G, Φ, µ, p, γ). Conversely, if the matching policy Φ is fcfm, then any synchronizing word of length 2p is strongly synchronizing. As a conclusion, for a model with latency, both Algorithm 2 and Algorithm 3 are valid perfect sampling algorithms that terminate almost surely, and we can now compare their performance. For this, first notice that Algorithm 3 is readily faster than the Algorithm 2, since the arrival of p consecutive -1 also creates a strongly synchronizing word, as any word of length 2p containing p '-1' as its first or last p letters is strongly synchronizing. In Tables 6 to 9, we quantify this gain of applying Algorithm 3 rather than Algorithm 2 in terms of cpu time, for various parameters.

4.5. Estimating of the loss probability for ml and fcfm Algorithm 3 returns a random variable that is distributed from the stationary distribution of the system. This result can be of critical use, to compare the performance of systems, for which no exact characterization of the steady state is known. As an example, we are able to assess the asymptotic loss rate of items of every class. We use this to compare two matching policies in steady state: Match the Longest (ml) and

p = 3 α = 1

) b 1

 1 , ..., b r are called the endpoints of Y . If r = 1, we simply say that Y controls X.

Remark 1 .

 1 The assumptions of Theorem 1 are satisfied in particular if Y is positive recurrent and irreducible on the discrete state space Y, or if the distribution of Y has atoms at points b 1 , ..., b r with finite hitting times from y.

Algorithm 2 :

 2 Data: A probability distribution µ on V × R + T down ← -1 ; Tup ← -1 ; /* We initialize the starting time. */ Y ← m ; while Y ≠ 0 do i ← Tup ; Y ← ∅ ; for j ← Tup to T down do draw (vj, pj) from µ; /* We draw the random variables still needed at this iteration */ end while i < 0 and Y ≠ 0 do Y ← [max(Y, pi) -1] + ; i ← i + 1 ; end T down ← Tup -1 ; Tup ← 2Tup ; end X ← ∅ ; /* As Y has reached 0 we know that X has reached ∅. */ /* We now transition X to time 0 as a matching system. */ while i < 0 do X ← f Φ (X, (vi, pi)) ; i ← i + 1 ; end return X Simulation of the stationary probability of X -Matching model with impatience.

Definition 10 .

 10 Consider a model (G, Φ, µ, p), and define for all k ∈ Z, the SRS Ỹ ∶= ( Ỹ k n ) n≥k on the set Ỹ = {∅} ∪ ⋃ 2p j=1 V j , as follows:

  Data: A probability distribution µ on V T down ← -1 ; Tup ← -2p ; /* We initialize the starting time at time 2p */ Ỹ ← ∅ ; while Ỹ is not strongly synchronizing do i ← Tup ; Y ← ∅ ; for j ← Tup to T down do draw vj from µ; /* We draw the input at this iteration */ end while i < 0 and Ỹ is not strongly synchronizing do Ỹ ← g( Ỹ , vi); /* We investigate all arrival scenarios of length 2p from Tup to 0, and stop if one of them is strongly synchronizing. */ i ← i + 1 ; end T down ← Tup -1 ; Tup ← 2Tup ; end X ← z( Ỹ ) ; /* We assign to X the common state induced by the synchronizing word Ỹ */ /* We now transition X to time 0 as a matching system. */ while

4. 3 . 5 .

 35 Example. To illustrate the efficiency of Algorithm 3 in the case of deterministic patience times, we consider the simple non-trivial example of the so-called paw graph G of Figure1.

Figure 1 :

 1 Figure 1: The paw graph.

4. 3 ,

 3 we then easily obtain a simplified representation of the system state: Definition 12. For all n ∈ Z, the word-profile of the system just before time n is defined by the wordXn = w 1 ⋯w p ∈ (V ∪ {0} ∪ {-1}) p ,We now turn to the converse implication i) ⇒ ii) : Suppose, to the contrary, that for some k ∈ 1, p we have Pn-k ≠ 0 which, by the very definition of P , means that Pn-k = p + ε. Then, as Ŷn-k ≤ p + ε -1 we have thatŶn-k+1 = [max( Ŷn-k , Pn-k ) -1] + = Pn-k -1 = p + ε -1.

○ x the word ○ x 1 ⋯

 1 ○x p , where for all i ∈ 1, p ,○ x i = x i 1 xi≠-1 .The notions of synchronizing and strongly synchronizing words, are then extended as follows.

8 n = 4 ,Table 6 :

 846 Algo 2 0.0038045 0.0037805 0.0040165 0.0039802 0.0042959 n = 4, Algo 3 0.0004670 0.0004578 0.0005623 0.0007405 0.0009837 n = 5, Algo 2 0.0044388 0.0041361 0.0043400 0.0045547 0.0043607 n = 5, Algo 3 0.0004592 0.0005210 0.0005462 0.0006469 0.0008396 n = 6, Algo 2 0.0046643 0.0045620 0.0046185 0.0046222 0.0048220 n = 6, Algo 3 0.0004305 0.0004332 0.0005398 0.0006290 0.0010127 n = 7, Algo 2 0.0049668 0.0053617 0.0051719 0.0048706 0.0047918 n = 7, Algo 3 0.0003674 0.0005255 0.0006371 0.0008323 0.0009967 n = 8, Algo 2 0.0049822 0.0049859 0.0050439 0.0052366 0.0059534 n = 8, Algo 3 0.0003490 0.0003939 0.0006275 0.0008972 0.0013853 Average cpu time of the algorithms on standard computer for 100 repetitions with p = 3, γ = 0.2 and multiple values of (n, α).The previous result implies that Algorithm 3 (by taking strongly synchronizing words in this new acception) terminates almost surely, and also produces a sample of the stationary distribution of the model with latency.

Table 1 :

 1 Efficiency of Algorithm 1.

	1,

bounds for E [I] and E [-T ], for various values of p. 4.3.6. Complexity comparison. After having provided a bound for the average coalescence time for Algorithm 3, we now compare the number of operations necessary to p N (G, p) Bound for E [I] Bound for E [-T ] complete Algorithm 3, to the number of operations necessary to complete the primitive CFTP algorithm, consisting of running chains started from all possible states, in parallel. To compare those two algorithms, we need to specify what we mean by operations: We say that an algorithm does one operation if it compares two letters of V, to determine if they are equal or not or if the two letters are connected in G. It is intuitively clear, that the two algorithms can be basically decomposed into a sequence of such operations:

Table 2 :

 2 Average number of operations of the algorithms for 10 repetitions with p = 3

Funding information

This research was funded by the Research Grant ANR-18-CE40-0019-01 'MATCHES', and by a 'Region Grand Est' PhD grant.

where for all i ∈ 1, p ,

was not matched before n;

was matched before n.

Vn-p+i-1 = -1 if no item entered at time np + i -1.

. We can therefore view the latency at a certain time n, as the arrival of an item labeled -1, that cannot be matched with any other item. We then denote by

the (finite) state space space of X. Contrary to the model of Section 4.3 (which can be seen as a particular of the present one for γ = 0), ( 9) is verified here, since the geometric r.v. ξ can be arbitrarily large. Therefore, Algorithm 2 can be used to design a perfect sampling algorithm in this case. Let Ŷ ∶= ( Ŷn ) n∈Z be the SRS defined by the recursive equation

Proposition 7. For any n ∈ Z, the following statements are equivalent:

Proof. Fix n ∈ Z. Regarding the implication ii) ⇒ i), by the construction of P and Ŷ we have that

Moreover, for all k ∈ 1, p ,

so by induction we obtain that n = 4, Algo 2 0.7051800 0.5984500 0.5163900 0.4517600 0.7003300 n = 4, Algo 3 0.0034300 0.0057900 0.0056100 0.0068200 0.0246900 n = 5, Algo 2 0.5984500 0.8970700 0.5821500 0.6060300 0.5139100 n = 5, Algo 3 0.0035900 0.0026300 0.0065800 0.0109600 0.0221800 n = 6, Algo 2 0.7514100 0.6232700 0.6096600 0.9526300 0.7364400 n = 6, Algo 3 0.0009300 0.0042500 0.0051800 0.0105000 0.0219500 n = 7, Algo 2 0.7517200 0.5460800 0.4714300 0.5977900 0.6670700 n = 7, Algo 3 0.0014000 0.0025000 0.0042300 0.0084900 0.0171500 n = 8, Algo 2 0.5546900 0.6359300 0.4876600 0.7620300 0.6122400 n = 8, Algo 3 0.00109000 0.0017500 0.0037400 0.0092300 0.0376300 Table 9: Average cputime of the algorithms on standard computer for 10000 repetitions with p = 6, γ = 0.5 and multiple values of (n, α).

First Come, First Matched (fcfm).

Let (G = (V, E), Φ, µ, p) be a discrete matching model with deterministic impatience, and X = ( Xn ) n∈Z be the Markov chain of the system. Let π be the stationnary distribution for X and for all (i, j) ∈ V 2 such that (i, j) / ∈ E, A i,j = {x = x 1 ⋯x j ∈ X, x 1 = i and the arrival is of class j in a buffer x}.

The asymptotic loss rate of items of class i is denoted by

where for all n, A i n = {An item of class i is lost at time n}.

An immediate first step analysis implies that

so ρ(i) can also be interpreted as the probability to lose an item of class i in the system ρ ρ(1) ρ( 2) ρ( 3) ρ( 4) ρ( 5) fcfm 0.0293 0.00026 0.00032 0.0132 0.0152 0.00032 ml 0.03122 0.00028 0.0003 0.01536 0.01486 0.00042

is the asymptotic loss rate of items (of any class) in the system, and can also be seen as the probability to lose an item (of any class) at a given time, in steady state. Using equation 18 we can then estimate those asymptotic loss rate by running our perfect simulation algorithm 3, and then estimating π(A i,j ) for all i, j ∈ V, by a Monte-Carlo estimate.

Table 10 presents the results over 10 4 simulations, for G a random Erdös-Renyi graph of parameters n = 5, α = 0.6, conditioned on being connected, for p = 5, and for µ the uniform distribution. Both matching policies fcfm and ml are implemented on the same samples each time. We observe that the overall asymptotic loss rate is slightly, but consistently lower under fcfm than under ml, although nominal loss rates of given nodes can be higher under fcfm.

Competing interests

There were no competing interests to declare which arose during the preparation or publication process of this article.