# Perfect sampling of stochastic matching models with reneging

Thomas Masanet  IECL, Université de Lorraine / INRIA PASTA  and  Pascal Moyal
IECL, Université de Lorraine / INRIA PASTA

###### Abstract.

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.

##  1\. 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 [15] for bipartite graphs (which is
suitable for supply/demands-type applications) and arrivals by couples, as a
variant of the seminal works [16, 3]. 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 [32], and then to hypergraphs in [40, 42] and graphs
with self-loops, in [8].

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 [32], 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 [17] 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 [5]. On another hand, in [26],
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. [32, 38]. 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, [1, 2, 8, 37, 18]),
for models without reneging. Let us also observe the recent advances in [19,
7] 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 [17], 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
[41], and Borovkov and Foss [11, 12]. The underlying idea is now well known:
Consider a discrete-event 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 [41] 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. [13] and Chapter
2.5 of [6]), and the connections between the two notions are investigated for
various cases of stochastic recursions in [22]. 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. [11, 12]. It is
also a tool to construct stationary states on enriched probability spaces, via
skew-product constructions, see [31, 4, 36].

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 [22], it is proven in [28] 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 [20]. 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 [29, 30] and
then [28], of the so-called ‘Bounding chains’ of Huber [24, 25], that are
particularly adapted to mechanical-statistical contexts, and of various
envelope techniques for queueing systems, see e.g. [14]. More recently, DCFTP-
related methods has been implemented, together with saturation techniques, to
perfectly simulate non-Markov queueing systems, see [9] for infinite-server
and loss queues, and [10] 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 [9], 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 [27].
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.

##  2\. Preliminary

In what follows, $\mathbb{R}$, $\mathbb{N}$, $\mathbb{N}^{*}$ and $\mathbb{Z}$
denote the sets of real, non-negative integers, strictly positive integers and
relative integers, respectively. For any two elements $a,b\in\mathbb{Z}$, let
$\llbracket a,b\rrbracket$ denote the integer interval $[a,b]\cap\mathbb{Z}$.

Any (simple, finite and undirected) graph $G$ is denoted by
$G=(\mathbb{V},E)$, where $\mathbb{V}$ is the set of nodes and $E$ is the set
of edges for a node $i\in\mathbb{V}$. For $n\in\mathbb{N}^{*}$, we say that
$G$ is of size $n$ if the cardinality $|\mathbb{V}|$ of $\mathbb{V}$ is $n$.
For any nodes $i,j\in\mathbb{V}$, we write $i-j$ if $i$ share an edge in $G$,
that is, $\\{i,j\\}\in E$. Else, we write $i\nleftrightline j$. For any set
$U\subset\mathbb{V}$, we denote by $E(U)$ the neighborhood of $U$, namely,

$E(U)=\left\\{j\in\mathbb{V}\,:\,i-j\mbox{ for some }i\in U\right\\}.$

For simplicity, for all $i\in\mathbb{V}$ we set $E(i):=E(\\{i\\})$, the set of
neighbors of node $i$ in $\mathbb{V}$.

Throughout the paper, all considered random variables (r.v.’s, for short) are
defined on a common probability space $(\Omega,\mathcal{F},\mathbb{P})$.

######  Definition 1.

Let $\mathbb{X}$ and $\mathbb{V}$ be two separable metric spaces. Let
$k\in\mathbb{Z}$ and $x\in\mathbb{X}$. Let $f$ be a measurable mapping from
$\,\mathbb{X}\times\mathbb{V}$ to $\mathbb{X}$, and
$\left(v_{n}\right)_{n\in\mathbb{Z}}$ be an identically distributed sequence
of $\mathbb{V}$-valued r.v.’s. We denote by $\left(X_{n}^{k}(x)\right)_{n\geq
k}$, the stochastic recursive sequence (SRS) driven by
$\left(f,\left(v_{n}\right)_{n\in\mathbb{Z}}\right)$, of initial value $x$ at
time $k$. Namely, $\left(X_{n}^{k}(x)\right)_{n\geq k}$ is fully determined by
the recurrence equation

$\begin{cases}X^{k}_{k}(x)&=x\,;\\\
X^{k}_{n+1}(x)&=f(X^{k}_{n}(x),v_{n}),\,\quad\mbox{a.s. for all }n\geq
k.\end{cases}$

It is immediate that $\left(X_{n}^{k}(x)\right)_{n\in\mathbb{Z}}$ is a
$\mathbb{X}$-valued Markov chain whenever the sequence
$\left(v_{n}\right)_{n\in\mathbb{Z}}$ is IID. Conversely, any
$\mathbb{X}$-valued Markov chain $\left(Z_{n}\right)_{n\in\mathbb{N}}$ of
fixed starting time $k$ and initial value $x$, having transition matrix $Q$
over $\mathbb{X}$, can be represented by the SRS driven by
$\left(f,\left(v_{n}\right)_{n\in\mathbb{Z}}\right)$, where
$\left(v_{n}\right)_{n\in\mathbb{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}\in\mathbb{X}$,

$\lambda\left(\\{x\,:\,,f(x_{1},x)=x_{2}\\}\right)=Q(x_{1},x_{2}),$

for $\lambda$ the Lebesgue measure, see e.g. Section 2.5.3 of [6].

Fix an SRS $X:=\left(X_{n}^{k}(x)\right)_{n\geq k}$. Then for all
$e\in\mathbb{X}$, we set

$\tau^{X,k}_{e}(x)=\inf\left\\{n\geq k\,:\,X_{n}^{k}(x)=e\right\\},$

the hitting time of value $e$ by $\left(X_{n}^{k}(x)\right)_{n\geq k}$. If
$\left(v_{n}\right)_{n\in\mathbb{Z}}$ is IID, then
$\left(X_{n}^{k}(x)\right)_{n\geq k}$ is a Markov chain, and the distribution
of $\tau^{X,k}_{e}(x)-k$ is independent of $k$. In that case, we then denote
by $\tau^{X}_{e}(x)$, a generic r.v. that is so distributed.

##  3\. 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.
Our procedure is closely related to that of the dominated coupling from the
past algorithm introduced by Kendall and Moller in [29, 30]. 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
$\mathbb{X},\mathbb{Y}$ and $\mathbb{V}$, and two mappings
$f:\mathbb{X}\times\mathbb{V}\to\mathbb{X}$ and
$g:\mathbb{Y}\times\mathbb{V}\to\mathbb{Y}$.

Data: $a_{1},...,a_{q}\in\mathbb{X}$, $b_{1},...,b_{q},y\in\mathbb{Y}$, a
probability distribution $\mu$ on $\mathbb{V}$

$T_{down}\leftarrow-1$ ;

$T_{up}\leftarrow-1$ ;

/* We initialize the starting time. */

$Y\leftarrow y$;

while  _$Y\not\in\\{b_{1},...,b_{q}\\}$_ do

$i\leftarrow T_{up}$ ;

$Y\leftarrow y$;

for  _$j\leftarrow T_{up}\ \textnormal{{to}}\ T_{down}$_ do

draw $v_{j}$ from $\mu$;

/* We draw the random variables still needed for this iteration */

end for

while  _$i <0$ and $Y\not\in\\{b_{1},...,b_{q}\\}$_ do

$Y\leftarrow g(Y,v_{i})$ ;

$i\leftarrow i+1$ ;

end while

$T_{down}\leftarrow T_{up}-1$ ;

$T_{up}\leftarrow 2T_{up}$

end while

for  _$k\leftarrow 1\ \textnormal{{to}}\ q$_ do

if  _$Y=b_{k}$_ then

$X\leftarrow a_{k}$ ;

/* We assign to $X$ the state corresponding to the endpoint reached by $Y$. */

end if

end for

/* We now transition $X$ to time $0$. */

while  _$i <0$ _ do

$X\leftarrow f(X,v_{i})$ ;

$i\leftarrow i+1$ ;

end while

return _$X$_

Algorithm 1 Simulation of the stationary probability of $X$

###  3.1. 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 $\left(X_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(Y_{n}\right)_{n\in\mathbb{Z}}$ be two SRS, respectively valued in
$\mathbb{X}$ and $\mathbb{Y}$ and $q\in\mathbb{N}^{*}$. We say that
$\left(Y_{n}\right)_{n\in\mathbb{Z}}$ $q$-controls
$\left(X_{n}\right)_{n\in\mathbb{Z}}$, if there exists
$b_{1},...,b_{q},y\in\mathbb{Y}$ and $a_{1},...,a_{q}\in\mathbb{X}$ such that

(1) $\forall i\in\llbracket 1,q\rrbracket,\forall k\in\mathbb{Z},\,\forall
n\geq k,\,\left[Y^{k}_{n}(y)=b_{i}\right]\Longrightarrow\left[\forall
x\in\mathbb{X},\,X^{k}_{n}(x)=a_{i}\right].$

$b_{1},...,b_{q}$ are called the endpoints of $Y$. If $q=1$ we simply say that
$Y$ controls $X$.

The following result establishes that under certain conditions including the
control of $\left(X_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(Y_{n}\right)_{n\in\mathbb{Z}}$, Algorithm 1 terminates almost surely,
and the output is a sample of the stationary distribution of the SRS
$\left(X_{n}\right)_{n\in\mathbb{Z}}$.

######  Theorem 1.

Suppose that the sequence $\left(v_{n}\right)_{n\in\mathbb{Z}}$ is IID, and
let $X$ and $Y$ be two SRS respectively driven by
$\left(f,\left(v_{n}\right)_{n\in\mathbb{Z}}\right)$ and
$\left(g,\left(v_{n}\right)_{n\in\mathbb{Z}}\right)$. Suppose that $X$ is
$q$-controlled by $Y$ for $b_{1},...,b_{q},y$ and $a_{1},...,a_{q}$, and that
it holds that

(2) ${\mathbb{P}}\left[\tau^{Y}_{b_{i}}(y)<\infty\right]=1,\quad
i\in\llbracket 1,q\rrbracket.$

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\in\llbracket 1,q\rrbracket$ and any $N\in\mathbb{N}$,

$\displaystyle\mathbb{P}\left(\bigcup\limits_{n\in\mathbb{N}}\left\\{\tau^{Y,-2^{n}}_{b_{i}}(y)\leq
0\right\\}\right)$
$\displaystyle=\mathbb{P}\left(\bigcup\limits_{n\in\mathbb{N}}\left\\{\tau^{Y,-2^{n}}_{b_{i}}(y)+2^{n}\leq
2^{n}\right\\}\right)$
$\displaystyle\geq\mathbb{P}\left(\left\\{\tau^{Y,-2^{N}}_{b_{i}}(y)+2^{N}\leq
2^{N}\right\\}\right)=\mathbb{P}\left(\left\\{\tau^{Y}_{b_{i}}(y)\leq
2^{N}\right\\}\right),$

in view of the stationarity of the input. So we obtain that

$\displaystyle\mathbb{P}\left(\bigcup\limits_{n\in\mathbb{N}}\left\\{\tau^{Y,-2^{n}}_{b_{i}}(y)\leq
0\right\\}\right)$ $\displaystyle\geq\lim_{N\rightarrow+\infty}\
\mathbb{P}\left(\left\\{\tau^{Y}_{b_{i}}(y)\leq 2^{N}\right\\}\right)$
$\displaystyle=\mathbb{P}(\\{\tau^{Y}_{b_{i}}(y)<+\infty\\})=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

(3) $N=\min\left\\{n\geq 0\,:\,X^{-n}_{0}(x)=X^{-n}_{0}(x^{\prime})\mbox{ for
all }x\neq x^{\prime}\in\mathbb{X}\right\\}.$

Let $R$ be the smallest termination time of Algorithm 1. Then, by the very
definition of Algorithm 1 and (1) there exists $i\in\llbracket 1,q\rrbracket$,
a time $n_{0}>0$ such that $-R<-n_{0}$, and such that
$X^{-R}_{-n_{0}}(x)=X^{-R}_{-n_{0}}(x^{\prime})=a_{i}$ for all
$x,x^{\prime}\in\mathbb{X}$, $x\neq x^{\prime}$, and thereby

(4) $X^{-R}_{0}(x)=X^{-R}_{0}(x^{\prime})=X^{-n_{0}}_{0}(a_{i}),\mbox{ for all
$x,x^{\prime}\in\mathbb{X}$, $x\neq x^{\prime}$. }$

In particular, it naturally follows from (3) that we necessarily have $R\geq
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 [22], the vertical backwards coalescence
time of $X$ is successful, and so it follows from Theorem 4.1 in [22], first,
that there exists a unique invariant probability $\pi$ for the chain $X$, and
second, that the output $X^{-N}_{0}(x)$ of the CFTP algorithm when started
from any $x\in\mathbb{X}$, is sample from $\pi$. But it also follows from (4),
that

$X^{-R}_{0}(x)=X^{-N}_{0}(x)=X^{-n_{0}}_{0}(a_{i}),\quad\mbox{ for all
}x\in\mathbb{X}.$

So Algorithm 1 and the CFTP algorithm produce the same output, which completes
the proof. ∎

######  Remark 1.

The assumptions of Theorem 1 are satisfied in particular if $Y$ is positive
recurrent and irreducible on the discrete state space $\mathbb{Y}$, or if the
distribution of $Y$ has atoms at points $b_{1},...,b_{q}$ with finite hitting
times from $y$.

######  Remark 2.

It follows from the equivalence shown in Theorem 4.2 of [22] that under the
assumptions of Theorem 1, the Markov chain $X$ is uniformly ergodic, since the
vertical coalescence time for $X$ is successful.

###  3.2. 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 [11, 12]. Let us remind the following,

######  Definition 3.

Let $X$ be an SRS driven by $f$ and $\left(v_{n}\right)_{n\in\mathbb{Z}}$, and
$\left(A_{n}\right)_{n\in\mathbb{N}}$ be a sequence of events. We say that
$\left(A_{n}\right)_{n\in\mathbb{N}}$ is a sequence of renovating events of
length $m$ and associated mapping $h:\mathbb{V}^{m}\rightarrow\mathbb{X}$ for
the chain $X$ if for any $n\in\mathbb{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_{q},b_{1},...,b_{q}$ and $y$.
Then, it is easily seen that for all $k\in\mathbb{Z}$, $i\in\llbracket
1,q\rrbracket$ and $x\in\mathbb{X}$,
$\left(\\{Y^{k}_{n}(y)=b_{i}\\}\right)_{n\geq k}$ is a sequence of renovating
events of length 1 for the sequence $\left(X^{k}_{n}(x)\right)_{n\geq k}$.
Indeed, for all $n\geq 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
$\left(\\{Y^{k}_{n}(y)=b_{i}\\}\right)_{n\geq k}$ can be given, that imply
that there exist a stationary version of the chain
$\left(X_{n}\right)_{n\in\mathbb{N}}$, see e.g. Theorem 2.5.3 and Property
2.5.5 in [6].

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 [33].

######  Definition 4.

For a positive integer $m$, we say that the subset $A\subset\mathbb{X}$ is
$m$-small for the Markov chain $\left(X_{n}\right)_{n\in\mathbb{N}}$ on
$\mathbb{X}$, if there exists $\eta_{m}>0$, and a non-null Borel measure
$\mu_{m}$ on $\mathbb{X}$ such that

$\forall x\in A,\forall
B\in\mathcal{B}(\mathbb{X}),\quad{\mathbb{P}}\left[X_{m}\in
B\,|\,X_{0}=x\right]\geq\eta_{m}\mu_{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 [22, 28, 20].

It is significant that under the control condition of Definition 2 and (2),
the whole set $\mathbb{X}$ is small. To see this, observe that for any
$i\in\llbracket 1,q\rrbracket$, for any $m\in\mathbb{N}$ such that
${\mathbb{P}}\left[\tau^{Y}_{b_{i}}(y)=m-1\right]>0$, in view of the Markov
property, for all $x\in\mathbb{X}$ and all borelian subsets
$B\subset\mathbb{X}$ we have

$\displaystyle{\mathbb{P}}\left[X_{m}\in B\,|\,X_{0}=x\right]$
$\displaystyle\geq{\mathbb{P}}\left[\\{X_{m}\in
B\\}\cap\\{X_{m-1}=a_{i}\\}\,|\,X_{0}=x\right]$
$\displaystyle={\mathbb{P}}\left[X_{m-1}=a_{i}\,|\,X_{0}=x\right]{\mathbb{P}}\left[X_{m}\in
B\,|\,\\{X_{m-1}=a_{i}\\}\cap\\{X_{0}=x\\}\right]$
$\displaystyle\geq{\mathbb{P}}\left[\tau^{Y}_{b_{i}}(y)=m-1\right]{\mathbb{P}}\left[X_{1}\in
B\,|\,X_{0}=a_{i}\right]$ $\displaystyle=:\delta^{i}_{m}\mu^{i}_{m}(B).$

Hence $\mathbb{X}$ is $m$-small.

###  3.3. 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, $(\mathbb{U},\prec)$ denotes a partially ordered space, and we
define two mappings $\varphi:\,\mathbb{X}\longmapsto\mathbb{U}$ and
$\psi:\,\mathbb{Y}\longmapsto\mathbb{U}$.

######  Definition 5.

We say that the mapping $f:\mathbb{X}\to\mathbb{X}$ is dominated (for
$\mathbb{U}$, $\varphi$ and $\psi$) by the mapping
$g:\mathbb{Y}\to\mathbb{Y}$, and denote $f\prec^{\mathbb{U},\varphi,\psi}g$,
if

$\forall
x\in\mathbb{X},\,y\in\mathbb{Y},\quad\left[\varphi(x)\prec\psi(y)\right]\Longrightarrow\,\left[\varphi\circ
f(x)\prec\psi\circ g(y)\right].$

In the definition above, $\mathbb{U}$ is an auxiliary partially ordered set
that is used for comparing $f$ to $g$ via the projections $\varphi$ and
$\psi$. Observe the following simple particular case,

######  Proposition 1.

In the case where $\mathbb{X}=\mathbb{Y}=\mathbb{U}$, $\mathbb{X}$ is
partially ordered by $\prec$ and $\varphi=\psi=\mbox{i}$ the identity
function, we have $f\prec^{\mathbb{X},\mbox{i},\mbox{i}}g$ under either one of
the conditions below,

  * (i)

$g$ is $\prec$-nondecreasing and pointwise lower-bounded by $f$;

  * (ii)

$f$ is $\prec$-nondecreasing and pointwise upper-bounded by $g$.

###### Proof.

Plainly, for all $x,y\in\mathbb{X}$ such that $x\prec y$, if we assume that
(i) holds, then we get $f(x)\prec g(x)\prec g(y),$ whereas if (ii) holds we
obtain that $f(x)\prec f(y)\prec g(y).$ ∎

######  Proposition 2.

Let $X$ and $Y$ be two SRS respectively driven by
$(f,\left(v_{n}\right)_{n\in\mathbb{Z}})$ and
$(g,\left(v_{n}\right)_{n\in\mathbb{Z}})$, where the input
$\left(v_{n}\right)_{n\in\mathbb{Z}}$ is IID on $\mathbb{V}$. Suppose that
$f(.,v)\prec^{\mathbb{U},\varphi,\psi}g(.,v)$ for all $v\in\mathbb{V}$, where
$\mathbb{U}$ admits the $\prec$-minimal point $o$. Suppose also that
$\varphi^{-1}(o)=\\{a\\}$, that there exists $y\in\mathbb{Y}$ such that

(5) $\forall x\in\mathbb{X},\,\,\varphi(x)\prec\psi(y),$

and that $\tau^{Y}_{b}(y)$ is almost surely finite for some
$b\in\psi^{-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 $X$ controls $Y$ for $b,y,a$. Let $k,n\in\mathbb{Z}$ be
such that $n>k$ and $Y^{k}_{n}(y)=b$. Let $x\in\mathbb{X}$. We show by
induction on $\ell$, that for all $\ell\in\llbracket k,n\rrbracket$,

(6) $\varphi(X^{k}_{\ell}(x))\prec\psi(Y^{k}_{\ell}(y)).$

First, from (5) we get that
$\varphi(X^{k}_{k}(x))=\varphi(x)\prec\psi(y)=\psi(Y^{k}_{k}(y)),$ so (6)
holds for $\ell=k$. Suppose that it is true at rank $\ell\in\llbracket
k,n-1\rrbracket$, i.e., that
$\varphi(X^{k}_{\ell}(x))\prec\psi(Y^{k}_{\ell}(y))$. Then, from the
domination assumption of $f$ by $g$ we obtain that

$\varphi(X^{k}_{\ell+1}(x))=\varphi(f(X^{k}_{\ell}(x),v_{\ell}))\prec\psi(g(Y^{k}_{\ell}(y),v_{\ell}))=\psi(Y^{k}_{\ell+1}(y)),$

so (6) holds at rank $\ell+1$. It is therefore true for all $\ell\in\llbracket
k,n\rrbracket$. In particular, we have that

$\varphi(X^{k}_{n}(x))\prec\psi(Y^{k}_{n}(y))=\psi(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\prec^{\mathbb{U},\varphi,\psi}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 [28, 20]. Specifically, as in [20], thanks to (5) 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 [41], 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 [28, 20], we
simulate $X$ starting from a single state until time $0$. Notice that the
DCFTP algorithms introduced in [28] and [20] use geometric ergodicity, and are
based on small sets constructions. As we observed above (Section 3.2), the
control condition implies the smallness of $\mathbb{X}$, so our approach is
reminiscent of this idea.

Observe that similar approaches are used for the perfect sampling of loss
queueing systems in [9] 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 [10].

######  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 $\mathbb{X}=E$ a lattice space, Condition
(i) in Proposition 1 above amounts to condition (H1) in [36] for any SRS $X$
and $Y$ that are respectively driven by $f$ and $g$, and a common input
$\left(v_{n}\right)_{n\in\mathbb{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 [31], and
Theorem 3 in [36].

##  4\. 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’.

###  4.1. The model

We consider a general stochastic matching model (GM), as was defined in [32]:
items enter one by one in a system, and each of them belongs to a determinate
class. The set of classes is denoted by $\mathbb{V}$, and identified with
$\llbracket 1,|\mathbb{V}|\rrbracket$. We fix a simple, connected graph
$G=(\mathbb{V},E)$ having set of nodes $\mathbb{V}$, termed compatibility
graph. Upon arrival, any incoming item of class, say, $i\in\mathbb{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=(\mathbb{V},E)$ and the matching policy $\Phi$, we consider that arrivals
occur at integer times, i.e., we suppose that the generic inter-arrival time
$\xi$ is constant equal to one, and fix two IID sequences
$\left(V_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(P_{n}\right)_{n\in\mathbb{Z}}$, where for all $n\in\mathbb{Z}$,
$P_{n}\in\mathbb{R}_{+}$ and $V_{n}\in\mathbb{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
$\left(V_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(P_{n}\right)_{n\in\mathbb{Z}}$ respectively, and assume throughout that
the r.v. $P$ is integrable. The two sequences
$\left(V_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(P_{n}\right)_{n\in\mathbb{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 $\mu$ the law
of $V$ on $\mathbb{V}$.

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

${\mathbb{X}}:=\\{\emptyset\\}\cup\bigcup_{q=1}^{\infty}\left(\mathbb{R}^{*}_{+}\times\mathbb{V}\right)^{q}.$

For all $t\geq 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 ${\mathbb{X}}$,

(7)
$X(t)=\begin{cases}\left(\left({R}^{1}(t),V^{1}(t)\right),\cdots,\left({R}^{{Q}(t)}(t),V^{Q(t)}(t)\right)\right)&\mbox{
if }{Q}(t)\geq 1,\\\ \emptyset&\mbox{ else,}\end{cases}$

where for all $i\in\llbracket 1,Q(t)\rrbracket$, we denote by $R^{i}(t)$
(resp., $\mathbb{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)=\emptyset$.

######  Definition 6.

We say that the matching policy $\Phi$ 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. [32, 37, 26] for a detailed presentation of
admissible policies for classical matching models.

Set $\left(T_{n}\right)_{n\in\mathbb{Z}}=\left(n\right)_{n\in\mathbb{Z}}$, the
arrival times to the system, and for all $n\in\mathbb{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 $\Phi$, the profile sequence
$\left(X_{n}\right)_{n\in\mathbb{Z}}$ is stochastic recursive, driven by the
couple sequence $\left((V_{n},P_{n})\right)_{n\in\mathbb{Z}}$, and a mapping
$f^{\Phi}:\mathbb{X}\times(\mathbb{R}_{+}\times\mathbb{V})\longmapsto\mathbb{X}$
that depends on $\Phi$ and possibly on a random draw independent of everything
else. In other words we get that

$X_{n+1}=f^{\Phi}\left(X_{n},(P_{n},V_{n})\right),\quad n\in\mathbb{Z}.$

###### Proof.

The construction of $f^{\Phi}$ is immediate: If the incoming element at $n$ is
matched upon arrival, the couple corresponding to its match, determined by
$\Phi$, 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$. ∎

###  4.2. 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:=\left(Y_{n}\right)_{n\in\mathbb{Z}}$ be a $\mathbb{R}_{+}$-valued SRS
defined by the recursion

(8)
$Y_{n+1}=\left[\max(Y_{n},P_{n})-1\right]^{+}=:g\left(Y_{n},P_{n}\right),\quad
n\in\mathbb{Z}.$

Then, for all $n$, $Y_{n}$ can be interpreted as the largest remaining service
time of a D/GI/$\infty$ queue of service times
$\left(P_{n}\right)_{n\in\mathbb{Z}}$, upon the arrival of the $n$-th
customer. As the generic r.v. $P$ is assumed integrable, it is well known that
whenever

(9) $\mathbb{P}(P\leq\xi)=\mathbb{P}(P\leq 1)>0$

the Markov chain $\left(Y_{n}\right)_{n\in\mathbb{Z}}$ is positive recurrent:
See e.g. Corollary 4.32 in [21], [43], and the generalization to the case
where $\left(P_{n}\right)_{n\in\mathbb{Z}}$ is stationary ergodic, combining
Lemma 5 of [34] with Corollary 2 in [35].

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}=\emptyset$ and $b_{1}=0$.

Data: A probability distribution $\mu$ on $\mathbb{V}\times\mathbb{R}^{+}$

$T_{down}\leftarrow-1$ ;

$T_{up}\leftarrow-1$ ;

/* We initialize the starting time. */

$Y\leftarrow m$ ;

while  _$Y\neq 0$_ do

$i\leftarrow T_{up}$ ;

$Y\leftarrow\emptyset$ ;

for  _$j\leftarrow T_{up}\ \textnormal{{to}}\ T_{down}$_ do

draw $(v_{j},p_{j})$ from $\mu$;

/* We draw the random variables still needed at this iteration */

end for

while  _$i <0$ and $Y\neq 0$_ do

$Y\leftarrow\left[\max(Y,p_{i})-1\right]^{+}$ ;

$i\leftarrow i+1$ ;

end while

$T_{down}\leftarrow T_{up}-1$ ;

$T_{up}\leftarrow 2T_{up}$ ;

end while

$X\leftarrow\emptyset$ ;

/* As $Y$ has reached $0$ we know that $X$ has reached $\emptyset$. */

/* We now transition $X$ to time $0$ as a matching system. */

while  _$i <0$_ do

$X\leftarrow f^{\Phi}(X,(v_{i},p_{i}))$ ;

$i\leftarrow i+1$ ;

end while

return _$X$_

Algorithm 2 Simulation of the stationary probability of $X$ \- Matching model
with impatience

######  Theorem 2.

Under condition (9), the profile Markov chain
$\left(X_{n}\right)_{n\in\mathbb{Z}}$ admits a unique stationary distribution.
If moreover there exists $m>0$ such that $\mathbb{P}(P\leq m)=1$, then
Algorithm 2 terminates almost surely, and its output is sampled from the
stationary distribution of $\left(X_{n}\right)_{n\in\mathbb{Z}}$.

###### Proof.

We apply Proposition 2, by setting in this case

$\displaystyle\varphi:$ $\displaystyle\mathbb{X}$
$\displaystyle\longrightarrow\mathbb{R}_{+}$ $\displaystyle
x=\left((r_{1},v_{1}),\cdots,(r_{q},v_{q})\right)\neq\emptyset$
$\displaystyle\longmapsto\max\left\\{r_{i}:\,i\in\llbracket
1,q\rrbracket\right\\}$ $\displaystyle\emptyset$ $\displaystyle\longmapsto 0.$

As any item spends in the system a time that is less or equal to its patience
time, for any $n\in\mathbb{Z}$, $\varphi(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)\in\mathbb{R}_{+}\times\mathbb{V}$, for all $x\in\mathbb{X}$ we obtain
that

(11)
$\varphi\left(f^{\Phi}\left(x,(p,v)\right)\right)\leq\left[\max\left(\varphi\left(x\right),p\right)-1\right]^{+}=g\left(\varphi\left(x\right),p\right).$

Therefore, for any $x\in\mathbb{X}$ and $y\in\mathbb{R}_{+}$ such that
$\varphi(x)\leq y$, for any $(p,v)$, as $g(.,p)$ is non-decreasing on
$\mathbb{R}_{+}$ we get that

$\varphi\left(f^{\Phi}\left(x,(p,v)\right)\right)\leq g\left(y,p\right).$

Proposition 2 completes the proof. ∎

###  4.3. Deterministic patience times

Whenever condition (9) does not hold, the existence and uniqueness of a
stationary distribution for the Markov chain
$\left(X_{n}\right)_{n\in\mathbb{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\equiv
p+\varepsilon$, for some $p\in\mathbb{N}^{*}$ and $0<\varepsilon<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
$\varepsilon-1<0$. For short, we denote such a matching model by
$(G,\Phi,\mu,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\in\mathbb{Z}$, the word-profile of the system just before time $n$
is defined by the word

$\tilde{X}_{n}=w_{1}\cdots w_{p}\in(\mathbb{V}\cup\\{0\\})^{p},$

where for all $i\in\llbracket 1,p\rrbracket$,

$w_{i}=\begin{cases}V_{n-p+i-1}&\mbox{if the item entered at }n-p+i-1\mbox{
was not matched before }\small{n};\\\ 0&\mbox{else}.\end{cases}.$

In particular, if the element entered at time $n-p$ is still in the system at
time $n$ (its class thus appearing as the first letter of the word
$\tilde{X}_{n}$), it is either matched with the incoming element at time $n$,
or it is considered lost.

We call $\tilde{\mathbb{X}}\subset(\mathbb{V}\cup\\{0\\})^{p}$, the (finite)
state space of $\tilde{X}$. Similarly to Proposition 3, it is immediate that
for any admissible policy $\Phi$, the sequence
$\left(\tilde{X}_{n}\right)_{n\in\mathbb{Z}}$ is a Markov chain, and we denote
by $\tilde{f}^{\Phi}$, the (deterministic, up to a possible draw that is
independent of everything else) map
$\tilde{f}^{\Phi}:\tilde{\mathbb{X}}\times\mathbb{V}\to\tilde{\mathbb{X}}$,
such that

$\tilde{X}_{n+1}=\tilde{f}^{\Phi}\left(\tilde{X}_{n},V_{n}\right),\quad
n\in\mathbb{Z}.$

####  4.3.2. Synchronizing words

For a fixed model $(G,\Phi,\mu,p)$, with $G=(V,E)$, let $\mathbb{V}^{*}$ be
the set of words on $\mathbb{V}$. For any word $v=v_{1}\cdots v_{l}$ in
$\mathbb{V}^{*}$ and any $\tilde{X}\in\tilde{\mathbb{X}}$, let us denote by
$W^{\Phi}(\tilde{X},v)\in\tilde{\mathbb{X}}$, the state of a system started at
$\tilde{X}$ and receiving the arrivals $v_{1},...,v_{l}$ in that order.

######  Definition 8.

Fix a model $(G,\Phi,\mu,p)$. A word $w=w_{1}\,\cdots\,w_{q}\in\mathbb{V}^{*}$
is said to be synchronizing, if

$\exists
z(w)\in\tilde{\mathbb{X}}:\,\forall\tilde{x}\in\tilde{\mathbb{X}},\,W^{\Phi}(\tilde{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 $\tilde{\mathbb{X}}$ is $(q+1)$-small for the
chain$\left(\tilde{X}_{n}\right)_{n\in\mathbb{Z}}$. Indeed, for all
$\tilde{x}\in\tilde{\mathbb{X}}$ and $B\subset\tilde{\mathbb{X}}$,

$\displaystyle{\mathbb{P}}\left[\tilde{X}_{q+1}\in
B\,|\,\tilde{X}_{0}=\tilde{x}\right]$
$\displaystyle\geq{\mathbb{P}}\left[\\{\tilde{X}_{q+1}\in
B\\}\cap\\{V_{0}V_{1}\,\cdots\,V_{q-1}=w\\}\,|\,\tilde{X}_{0}=\tilde{x}\right]$
$\displaystyle={\mathbb{P}}\left[V_{0}V_{1}\,\,\cdots\,\,V_{q-1}=w\right]{\mathbb{P}}\left[\tilde{X}_{q+1}\in
B\,|\,\\{V_{0}V_{1}\,\cdots\,V_{q-1}=w\\}\cap\\{\tilde{X}_{0}=\tilde{x}\\}\right]$
$\displaystyle=\prod_{i=0}^{q-1}\mu(w_{i}){\mathbb{P}}\left[\tilde{X}_{q+1}\in
B\,|\,\tilde{X}_{q}=z\right].$

In fact, our approach hereafter for perfect simulation is reminiscent of the
small-set techniques for exact sampling in [39, 23, 44]. 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,\ell\in V$ we
write $k\leftrightline\ell$ if $(k,\ell)\in E$, that is, the nodes $k$ and
$\ell$ share an edge in $G$. Else, we write $k\nleftrightline\ell$.

######  Definition 9.

Let $w\in\mathbb{V}^{*}$. We say that the word of length $2p$,
$w=w_{1}\,\cdots\,w_{2p}\in\mathbb{V}^{*}$ is strongly synchronizing, if

$\forall i\in\llbracket 1,p\rrbracket,\,\forall j\in\llbracket
p+1,p+i\rrbracket,\,w_{i}\nleftrightline w_{j}.$

The term strongly synchronizing is justified by the following result,

######  Theorem 3.

In a discrete matching model with impatience $(G,\Phi,\mu,p)$, any strongly
synchronizing word is a synchronizing word.

###### Proof.

Let $w=w_{1}\,\cdots\,w_{2p}$ be a strongly synchronizing word, and let
$u=w_{1}\,\cdots\,w_{p}$ and $v=w_{p+1}\,\cdots\,w_{2p}$. Let
$\tilde{x}\in\tilde{\mathbb{X}}$ and
$\mathbf{0}_{p}=\underbrace{0\,\cdots\,0}_{p}$, be the empty state. As $u$ is
of length $p$, any item present in the buffer represented by $\tilde{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^{\Phi}(\tilde{x},u)=u^{\prime}=w^{\prime}_{1},...,w^{\prime}_{p}$
where for all $i\in\llbracket 1,p\rrbracket,w^{\prime}_{i}=w_{i}$ if the
corresponding item is still in the buffer after these arrivals, or
$w^{\prime}_{i}=0$ else. As $w$ is strongly synchronizing, for any
$i\in\llbracket 1,p\rrbracket$ such that $w^{\prime}_{i}\neq 0$ and any
$j\in\llbracket p+1;p+i\rrbracket$, we have that
$w^{\prime}_{i}\nleftrightline w_{j}$. All elements corresponding to non-zero
letters of $u^{\prime}$ 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^{\prime}$. Therefore if $j,h\in\llbracket
p+1,2p\rrbracket$ 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
$\mathbf{0}_{p}$, then it is also the case if we add $v$ to the buffer
$u^{\prime}$. In other words, we get that

$W^{\Phi}(\tilde{x},w)=W^{\Phi}(W^{\Phi}(\tilde{x},u),v)=W^{\Phi}(u^{\prime},v)=W^{\Phi}(\mathbf{0}_{p},v).$

As this is true for any $\tilde{x}\in\tilde{\mathbb{X}}$, $w$ is a
synchronizing word for $z(w):=W^{\Phi}(\mathbf{0}_{p},v).$ ∎

We proceed with two technical lemmas. In what follows, for all
$a\in\mathbb{V}\cup\\{0\\}$ and all $k\in\llbracket 0,p\rrbracket$ we define
the following word of length $p$,

$x^{a}(k)=\underbrace{0\cdots 0}_{k}\underbrace{a\cdots a}_{p-k}.$

First observe the following,

######  Lemma 1.

Consider a matching model with impatience $(G,\textsc{fcfm},\mu,p)$, with
matching policy fcfm. Let $a\in\mathbb{V}$. Then, for all $k\in\llbracket
0,p-1\rrbracket$, for all words $w$ of length $p$, $W^{\Phi}(x^{a}(k),w)$ and
$W^{\Phi}(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\in\llbracket 0,p-1\rrbracket$, and write $w=w_{1}\,\cdots\,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^{\textsc{fcfm}}(x^{a}_{k},w)$ (or
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$).

If $w_{i}\nleftrightline a$ for all $i\in\llbracket 1,p\rrbracket$, then we
trivially get that

$W^{\textsc{fcfm}}(x^{a}(k),w)=W^{\textsc{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^{\textsc{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^{\textsc{fcfm}}(x^{a}_{k},w)$ (which we call for
short “the indices” in the discussion hereafter):

  1. (1)

Either the first $a$ of $x^{a}_{k}$ is matched in
$W^{\textsc{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^{\textsc{fcfm}}(x^{a}_{k},w)$ exactly as the a’s in
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$, and so the indices are precisely
$i_{0},i_{1},...,i_{l}$.

  2. (2)

Or the first $a$ of $x^{a}_{k}$ is not matched in
$W^{\textsc{fcfm}}(x^{a}_{k},w)$. Then, all the remaining $a$’s of $x^{a}(k)$
are matched in $W^{\textsc{fcfm}}(x^{a}_{k},w)$ exactly as the $a$’s in
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$, and the indices are again
$i_{1},...,i_{l}$.

  3. (3)

Or, the first matched $a$ of $x^{a}_{k}$ in $W^{\textsc{fcfm}}(x^{a}_{k},w)$
is matched with the letter of index $i_{1}$ in $w$. Then, in
$W^{\textsc{fcfm}}(x^{a}_{k},w)$, either the indices of the matched letters of
$w$ are the same as in $W^{\textsc{fcfm}}(x^{a}(k+1),w)$ (and then the last
$a$ in $x^{a}(k)$ remains unmatched), or the first $p-k-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^{\textsc{fcfm}}(x^{a}(k),w)=W^{\textsc{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^{\textsc{fcfm}}(x^{a}(k+1),w)$, but is matched with an $a$ of $x^{a}_{k}$
in $W^{\textsc{fcfm}}(x^{a}_{k},w)$. Then, either that letter $b$ remains
unmatched in $W^{\textsc{fcfm}}(x^{a}(k+1),w)$, in which case
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$ and $W^{\textsc{fcfm}}(x^{a}(k),w)$ differ
only at index $i_{0}$ (or $i_{l+1}$), where there is a $b$ in
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$ and $0$ in $W^{\textsc{fcfm}}(x^{a}(k),w)$.
Or, $b$ is matched with a letter $c$ of $w$ in
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$. Then, either the letter $c$ remains
unmatched in $W^{\textsc{fcfm}}(x^{a}(k),w)$, in which case
$W^{\textsc{fcfm}}(x^{a}(k+1),w)$ and $W^{\textsc{fcfm}}(x^{a}(k),w)$ differ
only at the place of that letter $c$ in $W^{\textsc{fcfm}}(x^{a}(k),w)$, where
there is a $0$ in $W^{\textsc{fcfm}}(x^{a}(k+1),w)$. Or, $c$ is matched with
another letter $b^{\prime}$ in $W^{\textsc{fcfm}}(x^{a}(k),w)$, in which case
we can repeat the same procedure for $b^{\prime}$ 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^{\textsc{fcfm}}(x^{a}(k+1),w)$ and $W^{\textsc{fcfm}}(x^{a}(k),w)$ differ
only by one letter. ∎

For all $\tilde{x}\in\tilde{\mathbb{X}}$, let us denote

$T(\tilde{x},a)=\mbox{Card}\left\\{\mbox{letters }\tilde{x}_{i}\mbox{ of
}\tilde{x}\,:\,\tilde{x}_{i}-a\right\\}.$

It follows from the above that

######  Corollary 1.

Let $w$ be a word of length $2p$ such that for some $i\in\llbracket
1;p\rrbracket$ and $j\in\llbracket p+1;p+i\rrbracket,$ we have $w_{i}-w_{j}$.
For such couple $\\{i,j\\}$, and $k\in\llbracket 0,2p\rrbracket$, let

$x^{i,j}(k)=\begin{cases}x^{w_{i}}(k)&\mbox{ if }k\in\llbracket
0,p-1\rrbracket,\\\ \mathbf{0}_{2p}&\mbox{ if }k=p,\\\ x^{w_{j}}(2p-k)&\mbox{
if }k\in\llbracket p+1,2p\rrbracket.\end{cases}$

Let also $u(k)=W^{\textsc{fcfm}}(x^{i,j}(k),w_{1}\,\cdots\,w_{p}),$ for all
$k\in\llbracket 0,2p\rrbracket$. Then, there exists an integer $k$ in
$\llbracket 0,2p-1\rrbracket$, such that $u(k)=z_{1}\,\cdots\,z_{p}$ differs
from $u(k+1)=z^{\prime}_{1}\,\cdots\,z^{\prime}_{p}$ by only one letter in
some position $l$, such that $z_{l}-w_{j}$, $z^{\prime}_{l}=0$, and for all
$h\in\llbracket 1,p\rrbracket$, $z^{\prime}_{h}=w_{h}$ or $z^{\prime}_{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\in\llbracket 0,2p-1\rrbracket$, $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\in\llbracket 0,2p-1\rrbracket$,
$|T(u(k),w_{j})-T(u(k+1),w_{j})|\leq 1$. Now notice that $2\leq
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}\,\cdots\,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\in\llbracket 0,2p-1\rrbracket$ 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,\textsc{fcfm},\mu,p)$. Let $w$
be a word of length $2p$ of $\mathbb{V}^{*}$. Then the following conditions
are equivalent:

  1. (i)

$w$ is a strongly synchronizing word;

  2. (ii)

$w$ is a synchronizing word.

###### Proof.

In view of Theorem 3, only the implication (ii) $\Rightarrow$ (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\in\llbracket 1;p\rrbracket$
and $j\in\llbracket p+1;p+i\rrbracket$. Let $i^{*}\in\llbracket 1;p\rrbracket$
and $j^{*}\in\llbracket p+1;p+i^{*}\rrbracket$ such that $w_{i^{*}}-w_{j^{*}}$
and $j^{*}=\inf\\{j\in\llbracket p+1;2p\rrbracket$, $\exists i\in\llbracket
2p-j;p\rrbracket$ $w_{i}-w_{j}\\}$. We denote $u=w_{1}\cdots w_{p}$ and
$v=w_{p+1}\cdots w_{2p}$. Let $k^{*}$ be the integer obtained in Corollary 1
for $i\equiv i^{*}$ and $j\equiv j^{*}$. Then, we get $u(k^{*})=d_{1}\cdots
d_{p}$ and $u(k^{*}+1)=e_{1}\cdots e_{p}$, where $u(.)$ is defined in
Corollary 1. We will prove that $W^{\textsc{fcfm}}(u(k^{*}),v)\neq
W^{\textsc{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^{\textsc{fcfm}}(u(k^{*}),v)$, and $i^{\prime}_{1},...,i^{\prime}_{h}$ be
the indices (in increasing order) of letters of $v$ that are matched with
letters of $u(k^{*}+1)$ in $W^{\textsc{fcfm}}(u(k^{*}+1),v)$. Now let us
define the following sets,

$\begin{cases}I_{0}&=\emptyset;\\\
I_{m+1}&=I_{m}\cup\left\\{\inf\left\\{j\in\llbracket
p+1,p+m+1\rrbracket\setminus
I_{m}\,:\,w_{j}-d_{m+1}\right\\}\right\\},\,m\in\llbracket
0,p-1\rrbracket.\end{cases}$

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^{\textsc{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

$\begin{cases}I^{\prime}_{0}&=\emptyset;\\\
I^{\prime}_{m+1}&=I_{m}\cup\left\\{\inf\left\\{j\in\llbracket
p+1,p+m+1\rrbracket\setminus
I^{\prime}_{m}\,:\,w_{j}-e_{m+1}\right\\}\right\\},\,m\in\llbracket
0,p-1\rrbracket,\end{cases}$

and the same argument leads to
$I^{\prime}_{p}=\\{i^{\prime}_{1},...,i^{\prime}_{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^{\textsc{fcfm}}(u(k^{*}),v)$ and $W^{\textsc{fcfm}}(u(k^{*}+1),v)$. For
every other step $m^{\prime}$, as $d_{m^{\prime}}\nleftrightline w_{j^{*}}$
and $e^{m^{\prime}}\nleftrightline w_{j^{*}}$, we add the same letter, if any,
to $I_{m^{\prime}-1}$ and $I^{\prime}_{m^{\prime}-1}$. So we have
$I_{p}=I^{\prime}_{p}\cup\\{j^{*}\\}$. Let $n_{1}$ (resp., $n_{2}$) be the
total number of letters from $v$ that are matched in
$W^{\textsc{fcfm}}(u(k^{*}),v)$ (resp., $W^{\textsc{fcfm}}(u(k^{*}+1),v)$). As
the total numbers of matched letters are even, both $n_{1}+|I_{p}|$ and
$n_{2}+|I^{\prime}_{p}|$ are even. But as $|I_{p}|$ and $|I^{\prime}_{p}|$ are
of different parity, so are $n_{1}$ and $n_{2}$. Thus,

$\displaystyle
W^{\textsc{fcfm}}(x^{i^{*},j^{*}}(k^{*}),w)=W^{\textsc{fcfm}}(u(k^{*}),v)$
$\displaystyle\neq W^{\textsc{fcfm}}(u(k^{*}+1),v)$
$\displaystyle=W^{\textsc{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
$\lfloor\frac{3p}{2}\rfloor$, 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.

######  Definition 10.

Consider a model $(G,\Phi,\mu,p)$, and define for all $k\in\mathbb{Z}$, the
SRS $\tilde{Y}:=\left(\tilde{Y}^{k}_{n}\right)_{n\geq k}$ on the set
$\tilde{\mathbb{Y}}=\\{\emptyset\\}\cup\bigcup_{j=1}^{2p}\mathbb{V}^{j},$ as
follows:

$\begin{cases}\tilde{Y}^{k}_{k}&=\emptyset;\\\
\tilde{Y}^{k}_{n+1}&=\tilde{g}(\tilde{Y}^{k}_{n},V_{n+1})\\\
&:=\begin{cases}v_{1}\cdots v_{i}V_{n+1},\mbox{ if
$\tilde{Y}^{k}_{n}=v_{1}\cdots v_{i}\in\mathbb{V}^{i}$ with $i<2p$}\\\
v_{2}\cdots v_{2p}V_{n+1},\mbox{ if $\tilde{Y}^{k}_{n}=v_{1}\cdots
v_{2p}\in\mathbb{V}^{2p}$}\end{cases},\,n\geq k,\end{cases}$

in a way that for all $k$ and all $n\geq k+2p$, $\tilde{Y}^{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 $\tilde{Y}=\emptyset$, for $\tilde{Y}$ the recursion of
Definition 10, $b_{1},...,b_{q}$, the strongly synchronizing words of the
model, and $a_{1},...,a_{q}$, the states of $\tilde{X}$ after the arrival of
$b_{1}$,…,$b_{q}$, respectively.

Data: A probability distribution $\mu$ on $\mathbb{V}$

$T_{down}\leftarrow-1$ ;

$T_{up}\leftarrow-2p$ ;

/* We initialize the starting time at time $2p$ */

$\tilde{Y}\leftarrow\emptyset$ ;

while  _$\tilde{Y}\,\mbox{{\em is not strongly synchronizing}}$_ do

$i\leftarrow T_{up}$ ;

$Y\leftarrow\emptyset$ ;

for  _$j\leftarrow T_{up}\ \textnormal{{to}}\ T_{down}$_ do

draw $v_{j}$ from $\mu$;

/* We draw the input at this iteration */

end for

while  _$i <0$ and $\tilde{Y}\,\mbox{{\em is not strongly synchronizing}}$_ do

$\tilde{Y}\longleftarrow g(\tilde{Y},v_{i})$;

/* We investigate all arrival scenarios of length $2p$ from $T_{up}$ to 0, and
stop if one of them is strongly synchronizing. */

$i\longleftarrow i+1$ ;

end while

$T_{down}\leftarrow T_{up}-1$ ;

$T_{up}\leftarrow 2T_{up}$ ;

end while

$\tilde{X}\longleftarrow z(\tilde{Y})$ ;

/* We assign to $\tilde{X}$ the common state induced by the synchronizing word
$\tilde{Y}$ */

/* We now transition $\tilde{X}$ to time $0$ as a matching system. */

while  _$i <0$_ do

$\tilde{X}\longleftarrow\tilde{f}^{\Phi}(\tilde{X},v_{i})$ ;

$i\longleftarrow i+1$ ;

end while

return _$\tilde{X}$_

Algorithm 3 Simulation of the stationary probability of $\tilde{X}$ \-
Matching model with deterministic patience

We have the following result,

######  Proposition 4.

$\tilde{X}$ is recurrent positive. Moreover, Algorithm 3 terminates a.s., and
its output is sampled from the stationary distribution of $\tilde{X}$.

###### Proof.

We can easily show that $\tilde{Y}$ $q$-controls $\tilde{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\in\mathbb{Z}$
and $n\geq k$, we get in particular that

(12)
$\left[\tilde{Y}^{k}_{n}(\emptyset)=w\right]\Longrightarrow\left[\forall\tilde{x}\in\tilde{\mathbb{X}},\,\tilde{X}^{k}_{n}(\tilde{x})=W^{\Phi}(\emptyset,w)\right],$

which implies that $\tilde{Y}$ controls $\tilde{X}$ over all strongly
synchronizing words. We conclude using Theorem 1. ∎

######  Remark 5.

Observe that $\tilde{Y}$ is not irreducible, however it reaches its recurrent
class in $2p$ iterations. So for all strongly synchronizing word $w$, we still
have that

$\mathbb{P}(\tau_{\emptyset}^{\tilde{Y}}(w)<\infty)=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 $\mu$ 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

${\mathbb{E}}\left[-T\right]\leq{2p\over q^{p,\mu}}\,,$

where

$q^{p,\mu}={\mathbb{P}}\left[V_{1}\cdots V_{2p}\mbox{ is strongly
synchronizing}\right].$

###### Proof.

For any integer $n\geq 1$, we let for all $i\in\mathbb{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\left\\{i\in\mathbb{N}^{*}\,:\,z^{n}_{i}\mbox{ is strongly
synchronizing}\right\\}.$

The independence of arrivals implies that the r.v.’s
$K^{n},\,n\in\mathbb{N}^{*}$ are identically distributed (but not independent)
of geometric distribution of parameter

$q^{p,\mu}={\mathbb{P}}\left[V_{1}\cdots V_{2p}\mbox{ is strongly
synchronizing}\right].$

Now, it readily follows from Theorem 3, that for all $n\in\mathbb{N}^{*}$,
$I\leq n$ in particular if there has been a strongly synchronizing arrival
array between times $-p2^{n}$ and $-1$ included, that is, if $2pK^{n}\leq
p2^{n}$. Consequently, for all $n\in\mathbb{N}^{*}$ we get that

${\mathbb{P}}\left[-T>p2^{n}\right]={\mathbb{P}}\left[I>n\right]\leq{\mathbb{P}}\left[2pK^{n}>p2^{n}\right]={\mathbb{P}}\left[2pK^{1}>p2^{n}\right].$

This readily implies that $-T\leq_{\tiny{\mbox{st}}}2pK^{1}$, where
$\leq_{\tiny{\mbox{st}}}$ denotes the strong stochastic ordering. We deduce
that

${\mathbb{E}}\left[-T\right]\leq 2p{\mathbb{E}}\left[K^{1}\right]={2p\over
q^{p,\mu}}.$

∎

Whenever the arrival measure $\mu$ is uniform over $\mathbb{V}$, the latter
results specializes as follows,

######  Corollary 2.

If the graph $G=(\mathbb{V},E)$ is of size $n$ and $\mu$ is uniform over
$\mathbb{V}$, we get the bounds

${\mathbb{E}}\left[-T\right]\leq{2pn^{2p}\over
N(G,p)},\quad{\mathbb{E}}\left[I\right]\leq 1+{2p\mbox{{\em Log}}n-\mbox{{\em
Log}}N(G,p)\over\mbox{{\em Log}}2},$

where $N(G,p)$ is the number of strongly synchronizing words of
$\mathbb{V}^{*}$.

###### Proof..

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

$q^{p,\mu}={N(G,p)\over n^{2p}}\cdot$

∎

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=(\mathbb{V},E),\Phi,\mu,p)$ be a discrete matching model with
impatience. For any strongly synchronizing word $w=w_{1}\cdots 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. (1)

$Z^{w}_{1}=w_{p+1},$

  2. (2)

For all $i\in\llbracket 1,p-1\rrbracket$,

$Z^{w}_{i+1}=\begin{cases}Z^{w}_{i},&\,\mbox{ if }w_{p+i+1}\in Z^{w}_{i};\\\
Z^{w}_{i}\ w_{p+i+1},&\,\mbox{ if }w_{p+i+1}\notin Z^{w}_{i},\end{cases}$

and $Z^{w}\equiv Z^{w}_{p}$.

In what follows, for any word $z=z_{1}\,\cdots\,z_{l}$, we denote by
$\beta(z)$ the cardinality of the set of nodes that are incompatible with all
letters of $z$, namely

$\beta(z)=\mbox{Card}\Bigl{\\{}v\in\mathbb{V}\,:\,\forall i\in\llbracket
1,l\rrbracket,v\nleftrightline z_{i}\Bigl{\\}}.$

We have the following,

######  Proposition 6.

Let $(G=(\mathbb{V},E),\Phi,\mu,p)$ be a discrete matching model with
impatience, and let $\mathscr{T}(G)$ be the set of words having distinct
letters, that form a permutation of the elements of a set $U\subset\mathbb{V}$
that is such that $E(U)\neq\mathbb{V}$. Then, the number $N(G,p)$ of strongly
synchronizing words is given by

$N(G,p)=\sum\limits_{z=z_{1}\cdots
z_{l}\in\mathscr{T}(G)}\sum\limits_{\\{1=k_{1}<k_{2}<\cdots<k_{l}<k_{l+1}=p+1\\}}\prod_{i=1}^{l}i^{k_{i+1}-k_{i}-1}\beta(z_{1}z_{2}\cdots
z_{i})^{k_{i+1}-k_{i}}.$

###### Proof.

Let $z=z_{1}\,\cdots\,z_{l}\in\mathbb{V}^{*}$ be a word having $l$ distinct
letters. Let us denote, for any word $w=w_{1}\,\cdots\,w_{2p}$ of trace $z$,

$k^{w}_{i}=\inf\Bigl{\\{}j\in\llbracket
1,p\rrbracket,\,w_{p+j}=z_{i}\Bigl{\\}},\quad i\in\llbracket 1,l\rrbracket,$

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}<\cdots<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,

  1. (i)

$w$ is strongly synchronizing, has trace $z=z_{1}\cdots z_{l}$, and

$(k^{w}_{1},k^{w}_{2},...,k^{w}_{l})=(k_{1},k_{2},...,k_{l}).$

  2. (ii)

For all $i\in\llbracket 1,l\rrbracket$,

     * (iia)

$w_{p+k_{i}}=z_{i}$;

     * (iib)

For all  $j\in\llbracket
k_{i},k_{i+1}-1\rrbracket,\,w_{p+j}\in\\{z_{1},\cdots,z_{i}\\}$ and $w_{j}\in
E\left(\\{z_{1},\,\cdots\,,z_{i}\\}\right)^{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\in\llbracket
k_{1},k_{2}-1\rrbracket$ 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}\nleftrightline w_{p+k_{1}}=z_{1}$. Now suppose that (iia)-(iib) hold
true for some $i-1\in\llbracket 1,p-1\rrbracket$. Then (iia) holds for $i$ by
definition of the trace and of $k_{i}$. (iib) also holds true by induction on
$j$ over $\llbracket k_{i},k_{i+1}-1\rrbracket$: First, we have
$w_{p+k_{i}}=z_{i}$ by (iia), implying, by definition of a strongly
synchronizing word and in view of the induction assumption, that

$\displaystyle w_{k_{i}}$ $\displaystyle\in
E\left(\left\\{w_{\ell}\,:\,\ell\in\llbracket
p+1,p+k_{i}\rrbracket\right\\}\right)^{c}$ $\displaystyle\in
E\left(\left\\{w_{\ell}\,:\,\ell\in\llbracket
p+1,p+k_{i}-1\rrbracket\right\\}\cup\\{w_{p+k_{i}}\\}\right)^{c}$
$\displaystyle=E\left(\left\\{z_{1},\cdots,z_{i}-1\right\\}\cup\\{z_{i}\\}\right)^{c}=E\left(\left\\{z_{1},\cdots,z_{i}\right\\}\right)^{c},$

so the properties in (iib) hold for $j=k_{i}$. Now suppose that they hold true
for some $j-1\in\llbracket k_{i},k_{i+1}-2\rrbracket$. Then
$w_{p+j}\in\\{z_{1},\cdots,z_{i}\\}$ by the very definition of $k_{i}$. Thus,
as $w$ is strongly synchronizing we have that

$\displaystyle w_{j}$ $\displaystyle\in
E\left(\left\\{w_{\ell}\,:\,\ell\in\llbracket
p+1,p+j\rrbracket\right\\}\right)^{c}$
$\displaystyle=E\left(\left\\{w_{\ell}\,:\,\ell\in\llbracket
p+1,p+j-1\rrbracket\right\\}\cup\\{w_{p+j}\\}\right)^{c}$
$\displaystyle=E\left(\left\\{z_{1},\cdots,z_{i}\right\\}\cup\\{w_{p+j}\\}\right)^{c}=E\left(\left\\{z_{1},\cdots,z_{i}\right\\}\right)^{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\in\llbracket 1,l\rrbracket$. Now
fix $j\in\llbracket 1,p\rrbracket$, and let $i$ be the index in $\llbracket
1,l\rrbracket$ such that $j\in\llbracket k_{i},k_{i+1}-1\rrbracket$. Then, in
view of (iia)-(iib) we get that

$w_{j}\in
E\left(\\{z_{1},\,\cdots\,,z_{i}\\}\right)^{c}=E\left(\\{w_{p+1},\,\cdots\,,z_{p+j}\\}\right)^{c},$

so $w$ is indeed strongly synchronizing. From (ii), $w$ also clearly has trace
$z$, so (i) holds, which concludes the proof of (i) $\Leftrightarrow$ (ii).

Now, for a fixed trace $z$, to count the strongly erasing words having trace
$z$ it thus suffices to count, for all families of integers
$1=k_{1}<k_{2}<\cdots<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\in\llbracket 1,l\rrbracket$ we have $i$ possibilities for each letter
between indices $k_{i}+1$ and $k_{i+1}-1$, and $\beta(z_{1}\cdots z_{i})$
possibilities for each letter between indices $k_{i}-p$ and $k_{i+1}-1-p$.
Therefore, the number of strongly synchronizing words and having $z$ has a
trace is given by

(13)
$N_{z}:=\sum\limits_{\\{1=k_{1}<k_{2}<\cdots<k_{l}<k_{l+1}=p+1\\}}\prod_{i=1}^{l}i^{k_{i+1}-k_{i}-1}\beta(z_{1}z_{2}\cdots
z_{i})^{k_{i+1}-k_{i}}.$

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}\subset\mathbb{V}$. If $E(U_{z})\neq\mathbb{V}$, then there exists a
letter $i\in\mathbb{V}\setminus E(U_{z})$, and $z$ clearly is the trace of any
word $w$ whose prefix of size $p$ is $ii\,\cdots\,i$, and whose suffix of size
$p$ is a permutation of the elements of $U$. If now $E(U_{z})=\mathbb{V}$, as
for any strongly synchronizing word $w$ and having trace $z$ we must have that
$w_{p}\not\in E(U_{z})$, leading to an immediate contradiction. Thus it is
necessarily and sufficient that $E(U_{z})\neq\mathbb{V}$ for $z$ to be a
trace, which concludes the proof. ∎

####  4.3.5. 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 Figure 1.

1234 Figure 1. The paw graph.

As the above results demonstrate, for any $p$, to compute the number $N(G,p)$
of strongly synchronizing words we first need to determine the set of all
possible traces $\mathscr{T}(G)$ of $G$. In the present case we readily obtain
that

$\mathscr{T}(G)=\Bigl{\\{}1,2,3,4,13,14,31,34,41,43,134,143,314,341,413,431\\}.$

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
$\beta(z)$ for all $z\in\mathscr{T}(G)$ using (13). We obtain

(14)
$\begin{cases}N_{\footnotesize{1}}=3^{p},\,N_{2}=1,\,N_{3}=2^{p},\,N_{4}=2^{p},N_{13}=\frac{3}{2}4^{p}-2.3^{p},\,N_{14}=\frac{3}{2}4^{p}-2.3^{p},\\\
N_{31}=\frac{1}{2}4^{p}-2^{p},\,N_{34}=(p-1)2^{p-1},\,N_{41}=\frac{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}.\end{cases}$

For clarity, let us detail one of the above computations, for $z=13$. We then
have $\beta(1)=|\\{1,3,4\\}|=3$ and $\beta(13)=|\\{1,3\\}|=2$. Therefore,
using (13) we have

$\displaystyle N_{13}$
$\displaystyle=\sum_{k_{2}=2}^{p}1^{k_{2}-1-1}\beta(1)^{k_{2}-1}2^{p+1-k_{2}-1}\beta(13)^{p+1-k_{2}}$
$\displaystyle=\sum_{k_{2}=2}^{p}3^{k_{2}-1}2^{p-k_{2}}2^{p+1-k_{2}}$
$\displaystyle=\frac{2\times
4^{p}}{3}\sum_{k_{2}=2}^{p}\left(\frac{3}{4}\right)^{k_{2}}=\frac{3}{2}4^{p}-2.3^{p}.$

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,

$\displaystyle{\mathbb{E}}\left[I\right]$ $\displaystyle\leq 1+{2p\mbox{{
Log}}n-\mbox{{Log}}N(G,p)\over\mbox{{Log}}2}$
$\displaystyle=1+4p-{\mbox{{Log}}\left(1+2^{2p+3}-3^{p+1}-4(p+3)3^{p-1}\right)\over\mbox{{Log}}2}=:B_{I},$

and the average starting time $T$ to detect coalescence is bounded by
$-p2^{B_{I}}$. In Table 1, we specify the number of strongly synchronizing
words, together with the corresponding bounds for ${\mathbb{E}}\left[I\right]$
and ${\mathbb{E}}\left[-T\right]$, for various values of $p$.

$p$ | $N(G,p)$ | Bound for ${\mathbb{E}}\left[I\right]$ | Bound for ${\mathbb{E}}\left[-T\right]$
---|---|---|---
1 | 8 | 2 | 4
2 | 42 | 3,608 | 24,381
3 | 216 | 5,245 | 113,778
4 | 1050 | 6,964 | 499,322
5 | 4872 | 8,750 | 2152,250
6 | 21834 | 10,586 | 9220,784
7 | 95352 | 12,460 | 39412,874
8 | 408378 | 14,360 | 168274,189
9 | 1723176 | 16,283 | 717831,830
10 | 7187946 | 18,223 | 3059320,779
Table 1. Efficiency of Algorithm 1.

####  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 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 $\mathbb{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:

  * •

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,q)$, that are conditioned to be connected, for various values
of the size $n$ and of the connectivity parameter $q$. We have then tracked
the average number of operations for 10 realizations of both algorithms, on
the same graph each time. The results are presented in Table 2 and 3.

$p=3$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, CFTP | $2907.67$ | $3356.04$ | $3012.46$ | $3228.72$ | $3393.52$
$n=4$, Algo 3 | $123.16$ | $168.11$ | $297.64$ | $213.27$ | $307.5$
$n=5$, CFTP | $4689.57$ | $5078.86$ | $4694.66$ | $5542.87$ | $4713.41$
$n=5$, Algo 3 | $102.2$ | $108.24$ | $161.58$ | $422.99$ | $548.35$
$n=6$, CFTP | $7888.29$ | $7350.42$ | $6550.72$ | $7466.3$ | $7319.94$
$n=6$, Algo 3 | $93.96$ | $82.39$ | $161.96$ | $338.36$ | $406.9$
$n=7$, CFTP | $11458.40$ | $10200.46$ | $111044.26$ | $10455.48$ | $9222.91$
$n=7$, Algo 3 | $69.06$ | $117.94$ | $140.82$ | $252.71$ | $764.8$
$n=8$, CFTP | $15984.74$ | $14829.7$ | $15127.1$ | $12565.42$ | $12189.06$
$n=8$, Algo 3 | $56.85$ | $86.28$ | $93.19$ | $241.3$ | $818.16$
Table 2. Average number of operations of the algorithms for $10$ repetitions with $p=3$ and multiple values of $(n,q)$. $p=3$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, CFTP | $0.00969$ | $0.01$ | $0.00890$ | $0.00937$ | $0.01$
$n=4$, Algo 3 | $0.00078$ | $0.00093$ | $0.00172$ | $0.00125$ | $0.00172$
$n=5$, CFTP | $0.01282$ | $0.01468$ | $0.01328$ | $0.01609$ | $0.01422$
$n=5$, Algo 3 | $0.00047$ | $0.00047$ | $0.00125$ | $0.00280$ | $0.00328$
$n=6$, CFTP | $0.02236$ | $0.02046$ | $0.01875$ | $0.02188$ | $0.02375$
$n=6$, Algo 3 | $0.00063$ | $0.00062$ | $0.00110$ | $0.00220$ | $0.00233$
$n=7$, CFTP | $0.03499$ | $0.03608$ | $0.03281$ | $0.03407$ | $0.02954$
$n=7$, Algo 3 | $0.00046$ | $0.00062$ | $0.00079$ | $0.00187$ | $0.00484$
$n=8$, CFTP | $0.04984$ | $0.04545$ | $0.04404$ | $0.03125$ | $0.02922$
$n=8$, Algo 3 | $0.00048$ | $0.00078$ | $0.00078$ | $0.00172$ | $0.00594$
Table 3. Average cputime of the algorithms on standard computer for $10$ repetitions with $p=3$ and multiple values of $(n,q)$. $p=6$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, CFTP | $467834.38$ | $477424.56$ | $457725.73$ | $433542.6$ | $363723.37$
$n=4$, Algo 3 | $5576.1$ | $12843.9$ | $12070.8$ | $21559.18$ | $17672.3$
$n=5$, CFTP | $1248551.28$ | $1139776.29$ | $919830.29$ | $853625.28$ | $980490.29$
$n=5$, Algo 3 | $12472.92$ | $11666.23$ | $11111.01$ | $58257.99$ | $143122.55$
$n=6$,CFTP | $3218753.63$ | $2446069.32$ | $2999130.02$ | $2128500.86$ | $1547150.53$
$n=6$, Algo 3 | $3183.32$ | $6274.56$ | $11272.88$ | $127429.52$ | $284116.14$
$n=7$, CFTP | $4790047.9$ | $7288225.3$ | $7117622.9$ | $2536934.7$ | $3628303.2$
$n=7$, Algo 3 | $2609.97$ | $9818.73$ | $455.36$ | $171196.79$ | $381580.97$
$n=8$, CFTP | $14779764.95$ | $10594880.96$ | $8477686.16$ | $6073463.72$ | $4123539.06$
$n=8$, Algo 3 | $2382.32$ | $2174.99$ | $14180.58$ | $46050.05$ | $389028.98$
Table 4. Average number of operations of the algorithms for $10$ repetitions with $p=6$ and multiple values of $(n,q)$. $p=3$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, CFTP | $1.10219$ | $1.20124$ | $1.13655$ | $1.09686$ | $0.91844$
$n=4$, Algo 3 | $0.05930$ | $0.1313$ | $0.1328$ | $0.24062$ | $0.2062$
$n=5$, CFTP | $2.85954$ | $2.66343$ | $2.06705$ | $2.23469$ | $2.66578$
$n=5$, Algo 3 | $0.06749$ | $0.08233$ | $0.06798$ | $0.55468$ | $2.4180$
$n=6$, CFTP | $7.99048$ | $6.53797$ | $9.8092$ | $5.83189$ | $4.18533$
$n=6$, Algo 3 | $0.01812$ | $0.03922$ | $0.07391$ | $1.31535$ | $3.8147$
$n=7$, CFTP | $17.61454$ | $14.21235$ | $15.81282$ | $10.9244$ | $17.6595$
$n=7$, Algo 3 | $0.01516$ | $0.06514$ | $0.03921$ | $3.53732$ | $7.23748$
$n=8$, CFTP | $42.85513$ | $35.96576$ | $27.95357$ | $18.95672$ | $12.183$
$n=8$, Algo 3 | $0.01517$ | $0.01281$ | $0.09954$ | $46.98482$ | $13.43019$
Table 5. Average cputime of the algorithms on standard computer for $10$
repetitions with $p=6$ and multiple values of $(n,q)$.

The results gathered in Tables 2 and 3 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 $q\geq\frac{3}{4}$, however, we observe
cases where the Algorithm 3 does not terminate in a reasonable amount of time.

###  4.4. 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
(9). This means that the SRS defined by the recursion (2) cannot hit $0$, and
so we cannot use Algorithm 2 for deterministic matching models.

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 $\gamma$, no item enters the system. In
other words, the generic inter-arrival time $\xi$ follows a geometric law of
parameter $1-\gamma$. The sequences
$\left(\widehat{V}_{n}\right)_{n\in\mathbb{Z}}$ and
$\left(\widehat{P}_{n}\right)_{n\in\mathbb{Z}}$ are then defined as follows:

  * •

If an item enters the system at time $n$, then $\widehat{V}_{n}$ is the class
of the item entering the system, and $\widehat{P}_{n}=p+\varepsilon$ is the
patience of the item entering the system;

  * •

Else, we set $\widehat{V}_{n}=-1$ and $\widehat{P}_{n}=0$.

We denote such deterministic model with latency, by $(G,\Phi,\mu,p,\gamma).$
Similarly to Section 4.3, we then easily obtain a simplified representation of
the system state:

######  Definition 12.

For all $n\in\mathbb{Z}$, the word-profile of the system just before time $n$
is defined by the word

$\widehat{X}_{n}=w_{1}\cdots w_{p}\in(\mathbb{V}\cup\\{0\\}\cup\\{-1\\})^{p},$

where for all $i\in\llbracket 1,p\rrbracket$,

$w_{i}=\begin{cases}\widehat{V}_{n-p+i-1}=v\in\mathbb{V}&\mbox{if the item of
class v entered at time }n-p+i-1\\\ &\mbox{ was not matched before
}\small{n};\\\ 0&\mbox{if the item entered at time }n-p+i-1\\\ &\mbox{ was
matched before }\small{n}.\\\ \widehat{V}_{n-p+i-1}=-1&\mbox{if no item
entered at time }n-p+i-1.\end{cases}.$

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

$\widehat{\mathbb{X}}=(\mathbb{V}\cup\\{0\\}\cup\\{-1\\})^{p},$

the (finite) state space space of $\widehat{X}$. Contrary to the model of
Section 4.3 (which can be seen as a particular of the present one for
$\gamma=0$), (9) is verified here, since the geometric r.v. $\xi$ can be
arbitrarily large. Therefore, Algorithm 2 can be used to design a perfect
sampling algorithm in this case. Let
$\widehat{Y}:=\left(\widehat{Y}_{n}\right)_{n\in\mathbb{Z}}$ be the SRS
defined by the recursive equation

(15)
$\widehat{Y}_{n+1}=\left[\max(\widehat{Y}_{n},\widehat{P}_{n})-1\right]^{+}=g\left(\widehat{Y}_{n},\widehat{P}_{n}\right),\quad
n\in\mathbb{Z}.$

######  Proposition 7.

For any $n\in\mathbb{Z}$, the following statements are equivalent:

  1. i)

$\widehat{Y}_{n}=0$

  2. ii)

For all $k\in\llbracket 1,p\rrbracket,\widehat{V}_{n-k}=-1$ (and equivalently
$\widehat{P}_{n-k}=0$).

###### Proof.

Fix $n\in\mathbb{Z}$. Regarding the implication ii) $\Rightarrow$ i), by the
construction of $\widehat{P}$ and $\widehat{Y}$ we have that

$\widehat{Y}_{n-p}\leq p+\varepsilon-1.$

Moreover, for all $k\in\llbracket 1,p\rrbracket$,

$\widehat{Y}_{n-k+1}=\left[\max(\widehat{Y}_{n-k},{\widehat{P}_{n-k}})-1\right]^{+}=\left[\max(\widehat{Y}_{n-k},0)-1\right]^{+}=\left[\widehat{Y}_{n-k}-1\right]^{+},$

so by induction we obtain that

$\widehat{Y}_{n}\leq\max(\widehat{Y}_{n-p}-p,0)\leq\max(p{+\varepsilon}-1-p,0)=0.$

We now turn to the converse implication i) $\Rightarrow$ ii) : Suppose, to the
contrary, that for some $k\in\llbracket 1,p\rrbracket$ we have
$\widehat{P}_{n-k}\neq 0$ which, by the very definition of $\widehat{P}$,
means that $\widehat{P}_{n-k}=p+\varepsilon$. Then, as $\widehat{Y}_{n-k}\leq
p+\varepsilon-1$ we have that

$\widehat{Y}_{n-k+1}=\left[\max(\widehat{Y}_{n-k},\widehat{P}_{n-k})-1\right]^{+}=\widehat{P}_{n-k}-1=p+\varepsilon-1.$

But for all $l\in\llbracket 1,k-1\rrbracket$ we have that
$\widehat{Y}_{n-l+1}\geq\widehat{Y}_{n-l}-1$, so that by an immediate
induction,

$\widehat{Y}_{n}\geq p+\varepsilon-1-(k-1)\geq\varepsilon>0.$

∎

As a consequence of Proposition 7, determining when $\widehat{Y}=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}\,\cdots\,x_{p}\in\widehat{\mathbb{X}}$, denote by
$\overset{\circ}{x}$ the word
$\overset{\circ}{x}_{1}\,\cdots\,\overset{\circ}{x}_{p}$, where for all
$i\in\llbracket 1,p\rrbracket,$
$\overset{\circ}{x}_{i}=x_{i}\mathbf{1}_{x_{i}\neq-1}$. The notions of
synchronizing and strongly synchronizing words, are then extended as follows.

######  Definition 13.

A word $w\in(\mathbb{V}\cup{-1})^{*}$ is said to be synchronizing for the
deterministic matching model with latency $(G,\Phi,\mu,p,\gamma)$ if

(16) $\exists z\in\widehat{\mathbb{X}},\,\forall
x\in\widehat{\mathbb{X}},\,W^{\Phi}(x,w)=w_{x}\mbox{ is such that
}\overset{\circ}{w_{x}}=z.$

We say that a word $w=w_{1}\cdots w_{2p}\in(\mathbb{V}\cup{-1})^{*}$ is
strongly synchronizing, if

$\forall i\in\llbracket 1,p\rrbracket,\,\forall j\in\llbracket
p+1,p+i\rrbracket,\,w_{i}\nleftrightline w_{j},$

where, by convention, $\forall v\in\mathbb{V},v\nleftrightline-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\in(\mathbb{V}\cup-1)^{*}$ is also
synchronizing word for the deterministic matching model with latency
$(G,\Phi,\mu,p,\gamma)$. Conversely, if the matching policy $\Phi$ is fcfm,
then any synchronizing word of length $2p$ is strongly synchronizing.

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.

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.

$p=3$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, 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$
Table 6. Average cpu time of the algorithms on standard computer for $100$ repetitions with $p=3,\gamma=0.2$ and multiple values of $(n,q)$. $p=3$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, Algo 2 | $0.0003215$ | $0.0003227$ | $0.0003087$ | $0.0003241$ | $0.0002954$
$n=4$, Algo 3 | $0.0002715$ | $0.0002666$ | $0.0002210$ | $0.0002102$ | $0.0002593$
$n=5$, Algo 2 | $0.0003761$ | $0.0003799$ | $0.0003718$ | $0.0003690$ | $0.0003190$
$n=5$, Algo 3 | 0.0002000 | 0.0001950 | 0.0001834 | 0.0002102 | 0.0002446
$n=6$, Algo 2 | $0.0004253$ | $0.0003487$ | $0.0003704$ | $0.0003690$ | $0.0003768$
$n=6$, Algo 3 | $00.0002045$ | $0.0001953$ | $0.0002090$ | $0.0002409$ | $0.0002559$
$n=7$, Algo 2 | $0.0004097$ | $0.0003916$ | $0.0004289$ | $0.0004132$ | $0.0004103$
$n=7$, Algo 3 | $0.0002384$ | $0.0002094$ | $0.0002073$ | $0.0002868$ | $0.0002901$
$n=8$, Algo 2 | $0.0004186$ | $0.0004070$ | $0.0004908$ | $0.0005598$ | $0.0006104$
$n=8$, Algo 3 | $0.0002074$ | $0.0001791$ | $0.0002156$ | $0.0002520$ | $0.0002659$
Table 7. Average cpu time of the algorithms on standard computer for $10000$ repetitions with $p=3,\gamma=0.5$ and multiple values of $(n,q)$. $p=6$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$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 8. Average cputime of the algorithms for $100$ repetitions with $p=6,\gamma=0.2$ and multiple values of $(n,q)$. $p=6$ | $q=\frac{1}{8}$ | $q=\frac{2}{8}$ | $q=\frac{3}{8}$ | $q=\frac{4}{8}$ | $q=\frac{5}{8}$
---|---|---|---|---|---
$n=4$, Algo 2 | $0.0046900$ | $0.00316360$ | $0.0034701$ | $0.0031292$ | $0.0031772$
$n=4$, Algo 3 | $0.0010425$ | $0.0010735$ | $0.0012352$ | $0.0013639$ | $0.0016111$
$n=5$, Algo 2 | $0.0040600$ | $0.0035472$ | $0.0035068$ | $,0.0034339$ | $0.0035351$
$n=5$, Algo 3 | $0.0008387$ | $0.0010067$ | $0.0010954$ | $0.0013510$ | $0.0015984$
$n=6$, Algo 2 | $0.0034200$ | $0.0035355$ | $0.0039241$ | $0.00358213$ | $0.0036049$
$n=6$, Algo 3 | $0.0008432$ | $0.0008729$ | $0.0010616$ | $0.0013186$ | $0.0017617$
$n=7$, Algo 2 | $0.0048400$ | $0.0037248$ | $0.0037925$ | $0.0036611$ | $0.0038020$
$n=7$, Algo 3 | $0.0007764$ | $0.0008591$ | $0.0010278$ | $0.0013062$ | $0.0017764$
$n=8$, Algo 2 | $0.0054600$ | $0.0038513$ | $0.0038263$ | $0.0037788$ | $0.0038358$
$n=8$, Algo 3 | $0.0007209$ | $0.0008657$ | $0.0010599$ | $0.0013521$ | $0.0018399$
Table 9. Average cputime of the algorithms on standard computer for $10000$
repetitions with $p=6,\gamma=0.5$ and multiple values of $(n,q)$.

###  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 First Come, First Matched (fcfm).

Let $(G=(\mathbb{V},E),\Phi,\mu,p)$ be a discrete matching model with
deterministic impatience, and
$\tilde{X}=\left(\tilde{X}_{n}\right)_{n\in\mathbb{Z}}$ be the Markov chain of
the system. Let $\pi$ be the stationnary distribution for $X$ and for all
$(i,j)\in\mathbb{V}^{2}$ such that $(i,j)\not\in E$,

$A_{i,j}=\\{x=x_{1}\cdots x_{j}\in\mathbb{X},\,x_{1}=i\text{ and the arrival
is of class }j\mbox{ in a buffer }x\\}.$

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

(17)
$\rho(i):=\lim\limits_{N\rightarrow+\infty}\frac{\sum\limits_{n=1}^{N}\mathds{1}_{A^{i}_{n}}}{N},$

where for all $n$,

$A^{i}_{n}=\\{\text{An item of class }i\text{ is lost at time }n\\}.$

An immediate first step analysis implies that

(18) $\rho(i)=\sum\limits_{j\in\mathbb{V}}\pi(A_{i,j})\mu(j),$

so $\rho(i)$ can also be interpreted as the probability to lose an item of
class $i$ in the system at a given instant, in steady state. Reasoning
similarly,

$\rho=\sum\limits_{i\in\mathbb{V}}\rho(i)$

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
$\pi(A_{i,j})$ for all $i,j\in\mathbb{V}$, by a Monte-Carlo estimate.

Table 4 presents the results over $10^{4}$ simulations, for $G$ a random
Erdös-Renyi graph of parameters $n=5,q=0.6$, conditioned on being connected,
for $p=5$, and for $\mu$ 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.

| $\rho$ | $\rho(1)$ | $\rho(2)$ | $\rho(3)$ | $\rho(4)$ | $\rho(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
Table 10. MC Estimates for the asymptotic loss rates for $10^{4}$ repetitions
of Algorithm 3 for a random Erdös-Renyi graph of parameters $n=5,q=0.6$, for
$p=5$ and $\mu$ the uniform distribution.

## References

  * [1] Adan, I., Bušić, A., Mairesse, J., and Weiss, G. Reversibility and further properties of FCFS infinite bipartite matching.  Mathematics of Operations Research 43, 2 (2018), 598–621.
  * [2] Adan, I., Kleiner, I., Righter, R., and Weiss, G. FCFS parallel service systems and matching models.  Performance Evaluation 127 (2018), 253–272.
  * [3] Adan, I., and Weiss, G. Exact FCFS matching rates for two infinite multitype sequences.  Operations Research 60 (2012), 475–489.
  * [4] Anantharam, V., and Konstantopoulos, T. A correction and some additional remarks on: stationary solutions of stochastic recursions describing discrete event systems.  Stoch. Process. Appl 80 (1999), 271–278.
  * [5] Aveklouris, A., DeValve, L., Ward, A. R., and Wu, X. Matching impatient and heterogeneous demand and supply.  arXiv preprint arXiv:2102.02710 (2021).
  * [6] Baccelli, F., and Brémaud, P. Elements of queueing theory: Palm Martingale calculus and stochastic recurrences, vol. 26.  Springer Science & Business Media, 2013.
  * [7] Begeot, J., Marcovici, I., and Moyal, P. Stability regions of systems with compatibilities, and ubiquitous measures on graph.  Queueing Systems: Theory and Applications 103, 3-4 (2023), 275–312.
  * [8] Begeot, J., Marcovici, I., Moyal, P., and Rahme, Y. A general stochastic matching model on multigraphs.  ALEA 18 (2021), 1325–1351.
  * [9] Blanchet, J., and Dong, J. Perfect sampling for infinite server and loss systems.  Advances in Applied Probability 47, 3 (2015), 761–786.
  * [10] Blanchet, J., Dong, J., and Pei, Y. Perfect sampling of gi/gi/c queues.  Queueing Systems: Theory and Applications 90, 1 (2018), 1–33.
  * [11] Borovkov, A., and Foss, S. Stochastically recursive sequences and their generalizations.  Siberian advances in Mathematics 2, 1 (1992), 16–92.
  * [12] Borovkov, A., and Foss, S. Two ergodicity criteria for stochastically recursive sequences.  Acta Applicandae Mathematica 34, 1 (1994), 125–134.
  * [13] Borovkov, A. A. Ergodicity and stability of stochastic processes.  J. Wiley, 1998.
  * [14] Bušić, A., Gaujal, B., and Vincent, J.-M. Perfect simulation and non-monotone markovian systems.  In 3rd International Conference Valuetools’ 08 (2008), ICST.
  * [15] Bušić, A., Gupta, V., and Mairesse, J. Stability of the bipartite matching model.  Advances in Applied Probability 45, 2 (2013), 351–378.
  * [16] Caldentey, R., Kaplan, E., and Weiss, G. FCFS infinite bipartite matching of servers and customers.  Adv. Appl. Probab 41, 3 (2009), 695–730.
  * [17] Castro, F., Nazerzadeh, H., and Yan, C. Matching queues with reneging: a product form solution.  Queueing Systems 96, 3 (2020), 359–385.
  * [18] Comte, C. Stochastic non-bipartite matching models and order-independent loss queues.  Stochastic Models 38, 1 (2022), 1–36.
  * [19] Comte, C., Mathieu, F., and Bušić, A. Stochastic dynamic matching: A mixed graph-theory and linear-algebra approach.  ArXiv math.PR/2112.14457 (2021).
  * [20] Connor, S. B., and Kendall, W. S. Perfect simulation for a class of positive recurrent markov chains.  The Annals of Applied Probability 17, 3 (2007), 781–808.
  * [21] Decreusefond, L., and Moyal, P. Stochastic modeling and analysis of telecom networks.  John Wiley & Sons, 2012.
  * [22] Foss, S. G., and Tweedie, R. L. Perfect simulation and backward coupling.  Stochastic models 14, 1-2 (1998), 187–203.
  * [23] Green, P., and Murdoch, D. Exact sampling for Bayesian inference: towards general purpose algorithms (with discussion)., vol. 6.  1999, pp. 301–321.
  * [24] Huber, M. Perfect sampling using bounding chains.  The Annals of Applied Probability 14, 2 (2004), 734–753.
  * [25] Huber, M. L. Perfect simulation, vol. 148.  Monographs on Statistics and Applied Probability, 2016.
  * [26] Jonckheere, M., Moyal, P., Ramírez, C., and Soprano-Loto, N. Generalized max-weight policies in stochastic matching.  Stochastic Systems 13, 1 (2023), 40–58.
  * [27] Kelly, F. P. Loss networks.  The Annals of Applied Probability 1, 3 (1991), 319–378.
  * [28] Kendall, W. Geometric ergodicity and perfect simulation.  Electronic Communications in Probability 9 (2004), 140–151.
  * [29] Kendall, W. S. Perfect simulation for the area-interaction point process.  In Probability Towards 2000, l. accardi and c. heyde ed. Springer Verlag, 1998, pp. 218–234.
  * [30] Kendall, W. S., and Moller, J. Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes.  Advances in Applied Probability 32, 3 (2000), 844–865.
  * [31] Lisek, B. A method for solving a class of recursive stochastic equations.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 60, 2 (1982), 151–161.
  * [32] Mairesse, J., and Moyal, P. Stability of the stochastic matching model.  Journal of Applied Probability 53, 4 (2016), 1064–1077.
  * [33] Meyn, S. P., and Tweedie, R. L. Markov chains and stochastic stability.  Springer Science & Business Media, 2012.
  * [34] Moyal, P. Stability of a processor-sharing queue with varying throughput.  Journal of Applied Probability 45, 4 (2008), 953–962.
  * [35] Moyal, P. On queues with impatience: stability, and the optimality of earliest deadline first.  Queueing Systems: Theory and Applications 75, 2 (2013), 211–242.
  * [36] Moyal, P. A generalized backward scheme for solving non-monotonic stochastic recursions.  The Annals of Applied Probability 25, 2 (2015), 582–599.
  * [37] Moyal, P., Bušić, A., and Mairesse, J. A product form for the general stochastic matching model.  Journal of Applied Probability 58, 2 (2021), 449–468.
  * [38] Moyal, P., and Perry, O. On the instability of matching queues.  The Annals of Applied Probability 27, 6 (2017), 3385–3434.
  * [39] Murdoch, D., and Green, P. Exact sampling from a continuous state space.  Scandinavian Journal of Statistics Theory and Application 25 (1998), 483–502.
  * [40] Nazari, M., and Stolyar, A. L. Reward maximization in general dynamic matching systems.  Queueing Systems: Theory and Applications 91, 1 (2019), 143–170.
  * [41] Propp, J. G., and Wilson, D. B. Exact sampling with coupled markov chains and applications to statistical mechanics.  Random Structures & Algorithms 9, 1-2 (1996), 223–252.
  * [42] Rahme, Y., and Moyal, P. A stochastic matching model on hypergraphs.  Advances in Applied Probability 53, 4 (2021), 951–980.
  * [43] Thorisson, H. Coupling, stationarity, and regeneration.  Springer Verlag, 2000.
  * [44] Wilson, D. B. How to couple from the past using a read-once source of randomness.  Random Structures & Algorithms 16, 1 (2000), 85–113.