2.1. Existence and uniqueness of stationary regime

In this section, we begin analyzing the stationary regime of the process on a compact domain D defined in Section 2. First, the existence and uniqueness of a stationary regime can be established by a simple Lyapunov. For the sake of completeness we give an alternate proof, based on a coupling-from-the-past argument.

Suppose we have a bi-infinite time-ergodic Poisson point process $\Phi$ on $D\times\mathbb{R}$ , with marks in ${\boldsymbol{C}}\times\mathbb{R}^+$ , where the first coordinate is the color of the particle and the second coordinate is the patience, as in the construction in Section 2. Briefly, in the coupling-from-the-past construction, the steady-state realization is constructed as a limit of a sequence of processes started at increasingly negative times using the same driving process $\Phi$ . We state the theorems here and present the proofs later in Appendix A.

In the next section, we present a product-form characterization of this steady-state distribution. For this, the key step is to construct the reversed process.

2.2. Product-form characterization of the steady state

In this section, we give a product-form characterization of the steady-state distribution, by getting a handle on the time-reversal of the steady-state process $\eta$ . Let $\Phi$ be as in Section 2.1.

Theorem 2.1 implies that there exists a unique bi-infinite spatial matching process that is driven by $\Phi$ . We can thus define a (random) matching function, $m\,{:}\,\Phi\rightarrow D\times\mathbb{R}\times{\boldsymbol{C}}$ , such that

\begin{align*}m(x)=\begin{cases}(p_x,b_x+w_x,c_x) &\textrm{if} x \textrm{exits on its own,}\\[5pt] (p_y,b_y,c_y) &\textrm{if} x \textrm{matches to $y\in\Phi$.}\end{cases}\end{align*}

Conversely, m stores all the information necessary to build the process ${\{\eta_t\}}_{t\in\mathbb{R}}$ . Indeed, the state of the spatial matching process we are interested in is given by

\begin{align*}\eta_t=((p_x,c_x)\,{:}\,x\in \Phi, b_x\leq t <b_{m(x)}),\end{align*}

where the list is ordered according to the birth times $b_x$ .

Taking inspiration from Adan et al. [Reference Adan, Bušić, Mairesse and Weiss1], we will include some additional data in the state of the system that will simplify the description of the reversed process. We shall consider a process that we call the backward detailed process generated by $\Phi$ and m. This process contains unmatched and matched particles in its state, and we distinguish these types by using the marks ‘ $\texttt{u}$ ’ and ‘ $\texttt{m}$ ’ respectively. For any particle x in the state, $s_x$ will refer to this mark.

For $t\in\mathbb{R}$ , let

\begin{equation*}T_t \,{:\!=}\, \min \{b_x\,{:}\,x\in \Phi, b_x\leq t < b_{m(x)}\}\end{equation*}

be the time of arrival of the earliest among the unmatched particles at time t. Let

\begin{equation*}\Gamma_{\texttt{u},t}\,{:\!=}\,\{(p_x,b_x,c_x,\texttt{u})\,{:}\,x\in \Phi, b_x\leq t < b_{m(x)}\}\end{equation*}

be the set of (locations, arrival times, and colors of) unmatched particles in $[T_t,t]$ . Let

\begin{align*}\Gamma_{\texttt{m},t}&\,{:\!=}\,\{(p_{x},b_{m(x)},c_{x},\texttt{m})\,{:}\,x\in \Phi,b_{x} \leq t, T_t\leq b_{m(x)}\leq t\}\\[3pt] &=\{(p_{m(x)},b_{x},c_{m(x)},\texttt{m})\,{:}\,x\in \Phi, b_{m(x)}\leq t,T_t\leq b_x\leq t, c_x\neq c_{m(x)}\}\\[3pt] &\mbox{}\qquad\qquad\cup\{(p_{x},b_{m(x)},c_{x},\texttt{m})\,{:}\,x\in \Phi,b_{x} \leq t, T_t\leq b_{m(x)}\leq t, c_x=c_{m(x)}\}\end{align*}

be the set of so-called matched and exchanged particles that are present in $[T_t,t]$ . In the last expression, the first set of elements corresponds to particles that arrive in the relevant interval, $[T_t,t]$ , and are matched by the time t; but instead of recording their positions and types, we record those of their matches. The second set of elements in that expression corresponds to particles that arrive before t and that depart on their own in the time interval $[T_t,t]$ ; we record the time at which they depart.

Finally, define the backward detailed process, $\hat \eta_t$ , by the list $((p_x,c_x,s_x)\,{:}\,x\in \Gamma_{\texttt{u},t}\cup \Gamma_{\texttt{m},t})$ , ordered according to the values of b-projections of the points in $\Gamma_{\texttt{u},t}\cup\Gamma_{\texttt{m},t}$ . Clearly, the original process $\eta_t$ can be obtained from $\hat\eta_t$ by removing the particles with marks $s_x=\texttt{m}$ . Notice that if $|\hat\eta_t|>0$ , the first element in $\hat\eta_t$ , denoted by $x_1$ , always satisfies $s_{x_1}=\texttt{u}$ .

The backward detailed process, $\hat\eta_t$ , is a stationary version of a Markov process. A valid state of this Markov process is any finite list of elements $(x_1,\ldots,x_n)$ from the set $D\times{\boldsymbol{C}}\times \{\texttt{u},\texttt{m}\}$ that satisfies the following definition.

Condition 2 in the above definition essentially states that there cannot be a compatible unmatched pair in a valid state. This is equivalent to the condition that

\begin{equation*}\{y\in x_1,\ldots, x_n\,{:}\,s_y=\texttt{u}\}\cap N(\{y\in x_1,\ldots,x_n\,{:}\,s_y=\texttt{u}\})=\emptyset.\end{equation*}

Condition 3 cannot be violated, since otherwise the particle whose matched and exchanged pair is $x_j$ could instead have matched to some $x_i$ that arrived earlier. This is equivalent to the condition that for all $1\leq j\leq n$ ,

\begin{equation*}s_{x_j}=\texttt{m}\implies x_j\notin N(\{y\in x_1,\ldots, x_j\,{:}\,s_y=\texttt{u}\}).\end{equation*}

Any valid state can be achieved by the process $\hat\eta_t$ in finite time with positive probability starting from the empty state. Indeed, any valid state $\hat\eta$ can result from the empty state if the arrivals occur in the order listed in $\hat\eta$ , with appropriate patience so that the particles in $\hat\eta$ marked $\texttt{u}$ survive until time t, and the particles in $\hat\eta$ marked $\texttt{m}$ exit on their own before the next arrival.

Transitions for $\hat\eta_t$ occur at the time of arrival of a new particle or at the event of a voluntary departure. At the time of a new arrival, we match and exchange the earliest compatible particle in the list $\hat\eta_t$ ; if there is no possible match we add the arriving particle to the end of the list with mark $\texttt{u}$ . At the time of a voluntary departure, we put the departing particle at the end of the list $\hat\eta_t$ , while updating the mark to $\texttt{m}$ . Below, we describe the transitions and transition rates of this Markov process in detail.

The transitions and transition rates for $\hat\eta_t$ are as follows. Let $\hat\eta=(x_1,\ldots,x_n)$ , $n\in \mathbb{N}$ , be a valid state.

1. 1. A particle $x_i\in\hat\eta$ , with $s_{x_i}=\texttt{u}$ , loses patience: This occurs at rate $\mu$ . In this case, the new state is obtained by removing $x_i$ and inserting the point $(p_{x_i},c_{x_i},\texttt{m})$ at the end of the list $\hat\eta$ . Additionally, we need to prune leading matched and exchanged particles from $\hat\eta$ to obtain the new state.

2. 2. A new particle $y=(p_y,c_y)$ arrives and is matched to a particle $x_i\in\hat\eta$ , with $d(p_{x_i},p_y)\leq 1$ and $c_{x_i}\neq c_y$ : This occurs at rate $\bar{\lambda}(dy) \mathbb{1}(y\in W_{x_i})$ . The new state is obtained by matching and exchanging the appropriate pair, and then pruning the leading matched and exchanged particles.

3. 3. A new particle y arrives and there is no particle of opposite color within a distance of 1 from it: This occurs at rate $\bar{\lambda}(dy) \mathbb{1}(y\notin N(\hat\eta))$ . The new state is the one obtained by adding this new particle to the end of the list as an unmatched particle.

We now guess the time-reversed version of the backward detailed process and obtain its transition rates. The following construction will be useful in doing this. Consider a dual process $\check\eta_t$ , which we call the forward detailed process. It is defined as follows: for $t\in\mathbb{R}$ let

\begin{equation*}Y_t\,{:\!=}\,\max\{b_{m(x)}\,{:}\,x\in \Phi, b_x\leq t < b_{m(x)}\}\end{equation*}

be the latest time at which all unmatched particles at time t are matched or exit. Let

\begin{align*}\Xi_{\texttt{m},t}&\,{:\!=}\,\{(p_x,b_{m(x)},c_x,\texttt{m})\,{:}\,x\in \Phi, b_x\leq t<b_{m(x)}\}\\[3pt]&=\{(p_{m(x)},b_x,c_{m(x)},\texttt{m})\,{:}\,x\in \Phi, b_{m(x)}\leq t <b_{x},c_x\neq c_{m(x)}\}\\[3pt] &\mbox{}\qquad\qquad\cup\{(p_x,b_{m(x)},c_x,\texttt{m})\,{:}\,x\in\Phi, b_x\leq t<b_{m(x)},c_x=c_{m(x)}\}\end{align*}

be the matched and exchanged particles corresponding to the particles that were born before time t, but have not been removed from the system by time t. Let

\begin{align*}\Xi_{\texttt{u},t}\,{:\!=}\,\{(p_x,c_x,b_{x},\texttt{u})\,{:}\,x\in \Phi, t<b_x<Y_t,t<b_{m(x)}\}\end{align*}

be the particles in the relevant interval $(t,Y_t)$ , whose match arrives after time t. Now, let $\check\eta_t$ be the list $((p_x,c_x,s_x)\,{:}\,x\in\Xi_{\texttt{u},t}\cup\Xi_{\texttt{m},t})$ ordered according to the values $b_{(\cdot)}$ . Thus, the last element in the list, $x_{|\check\eta|}$ , always has $s_{x_{|\check\eta|}}=\texttt{m}$ . For motivations for these definitions, see Adan et al. [Reference Adan, Bušić, Mairesse and Weiss1].

Under our construction, using the bi-infinite Poisson point process $\Phi$ , the process ${\{\check\eta_t\}}_{t\in\mathbb{R}}$ is a stationary process. In fact, it is a stationary version of a Markov process, since all the arrivals and deaths are Markovian. The transitions and transition rates are defined in detail in Appendix C.

The underlying idea in obtaining the product-form distribution is stated in the following lemma.

Lemma 2.1. For any list of elements $\gamma$ in $D\times{\boldsymbol{C}}\times\{\texttt{u},\texttt{m}\}$ , let $\textrm{revx}(\gamma)$ denote the list of elements in $\gamma$ written in the reverse order, with the marks $\texttt{u}$ and $\texttt{m}$ flipped. Then we claim that ${\{\textrm{revx}(\check\eta_t)\}}_{t\in\mathbb{R}}$ has the same distribution as the time-reversal of the backward detailed process. That is,

\begin{align*}{\{\hat\eta_{-t}\}}_{t\in\mathbb{R}}\stackrel{d}{=}{\{\textrm{revx}(\check\eta_t)\}}_{t\in\mathbb{R}}.\end{align*}

To obtain the product-form expression for the stationary distribution, we need to check certain local balance conditions (see Appendix B.1 for the definition of the local balance conditions). This is the main result of this section. However, before we state the result we need to fix some notation.

For any list $\gamma\in O(D,{\boldsymbol{C}}\times\{\texttt{u},\texttt{m}\})$ and $i\in\mathbb{N}$ , we define $Q^i_\texttt{u}(\gamma)$ to be the number of unmatched particles among the first i particles on $\gamma$ , and define $Q^i_\texttt{m}(\gamma)$ to be the number of matched particles excluding the first i particles of $\gamma$ . In this notation, we may drop the reference to $\gamma$ when the context is clear.

In the following result, we use the operator $\oplus$ to denote the direct sum of two measures, and the operator $\otimes$ to denote the direct product.

Theorem 2.2. The density of the stationary measure of the backward detailed process ${\{\hat\eta_t\}}_{t\in\mathbb{R}}$ , with respect to the measure $\oplus_{n=0}^\infty{(\lambda\otimes m_c\otimes m_c)}^n$ on

\begin{equation*}O(D,{\boldsymbol{C}}\times\{\texttt{u},\texttt{m}\})\subset \sqcup_{n=0}^\infty {(D\times{\boldsymbol{C}}\times\{\texttt{u},\texttt{m}\})}^n,\end{equation*}

is given by

(2) \begin{align}\hat\pi(\gamma)&=K\mathbb{1}(\gamma\textrm{is} \textrm{valid})\prod_{i=0}^{|\gamma|}\frac{1}{2\lambda(D)+Q^i_\texttt{u}(\gamma)\mu}\,{=\!:}\,K\mathbb{1}(\gamma\textrm{is valid})\hat\Pi(\gamma),\end{align}

(3) \begin{align}\hat\pi(\emptyset)&=K,\end{align}

where

\begin{equation*}\hat\Pi(\gamma)\,{:\!=}\,\prod_{i=0}^{|\gamma|}\frac{1}{2\lambda(D)+Q^i_\texttt{u}(\gamma)\mu},\end{equation*}

and where K is the normalizing constant:

\begin{align*}K^{-1}=\sum_{n=0}^\infty\int_{{(D\times {\boldsymbol{C}}\times\{\texttt{u},\texttt{m}\})}^n}\mathbb{1}(\gamma { is valid})\prod_{i=0}^n\frac{1}{2\lambda(D)+Q^i_\texttt{u}(\gamma)\mu}{(\lambda\otimes m_c\otimes m_c)}^{(n)}(d\gamma).\end{align*}

The form of the density in (2) is typical of a product-form distribution seen in the context of queueing theory (see Asmussen et al. [Reference Asmussen3]). For instance, $2\lambda(D)+Q^{|\gamma|}_{\texttt{u}}(\gamma)\mu$ is the total rate of change when the backward detailed process is in state $\gamma$ , as $2\lambda(D)$ is the total rate of new arrivals and $Q^{|\gamma|}_{\texttt{u}}(\gamma)\mu$ is the rate at which unmatched particles depart on their own.

For the stationary distribution $\pi$ of the original process $\eta_t$ , we compute the marginals of $\hat\pi$ . Firstly, a state $\gamma=(x_1,\ldots,x_n)\in O(D,{\boldsymbol{C}})$ is a valid state of the process ${\{\eta_t\}}_{t\in\mathbb{R}}$ if and only if $\{x_1,\ldots, x_n\}\cap N(\gamma)=\emptyset$ .

Corollary 2.1. The density of the stationary distribution $\pi$ of the process $\eta_t$ , with respect to the measure $\oplus_{n=0}^\infty\bar{\lambda}^n$ on $\sqcup_{n=0}^\infty{(D\times{\boldsymbol{C}})}^n$ , is given by

(4) \begin{align}\pi(\gamma)&=K\mathbb{1}(\gamma\textrm{ is valid})\prod_{i=1}^{|\gamma|}\frac{1}{\bar{\lambda}(N(\gamma_1^{i}))+i\mu},\end{align}

(5) \begin{align}\pi(\emptyset)&=K,\end{align}

where K is the same normalizing constant as in Theorem 2.2.

The proofs of Theorem 2.2 and Corollary 2.1 are given in Appendix C.

2.3. Clustering properties and the FKG property

In this section, we focus on the stochastic geometric properties of the steady-state arrangement of the particles in the space D. Hence, we forget the reference to the order of the particles in the steady state. Intuitively, the Janossy density of a point process (see Daley and Vere-Jones [Reference Daley and Vere-Jones10]) is the relative probability of observing a given configuration of points with respect to a given reference measure. The Janossy density of the steady-state distribution of our point process model, with respect to the Poisson point process on $D\times{\boldsymbol{C}}$ with intensity $\bar{\lambda}$ , is given by dropping the order of particles in Equation (4). That is, the Janossy density is

(6) \begin{equation}\begin{aligned} \tilde{\pi}(x_1^n)&=K\mathbb{1}(x_1^n\textrm{ is valid})\tilde{\Pi}(x_1^n),\\[3pt] \tilde\Pi(x_1^n)&=\sum_{(X_1^n)\in \mathcal{P}(x_1^n)}\prod_{i=1}^n\frac{1}{\bar{\lambda}(N(X_1^i))+i\mu},\end{aligned}\end{equation}

where $\mathcal{P}(x_1^n)$ is the set of all permutations of $x_1,\ldots,x_n$ , and K is a normalizing constant.

Let us take a moment to interpret the term $\bar{\lambda}(N(x_1^i))$ that appears in the above expression. This is the sum of the volumes of the union of balls around the red particles in $x_1,\ldots, x_i$ and the union of balls around the blue particles in $x_1,\ldots,x_i$ . Since such terms appear in the denominator in Equation (6), we expect that in the steady state the particles of the same color are clumped together.

In a variety of point processes, such as the one-particle Widom–Rowlinson model, or certain Cox processes (Błaszczyszyn and Yogeshwaran [Reference Błaszczyszyn and Yogeshwaran5]), the FKG lattice property is a useful tool for proving stochastic dominance and clustering properties. In the case of the Widom–Rowlinson model, the FKG inequality is also useful in showing the existence of a phase transition (Chayes et al. [Reference Chayes, Chayes and Kotecky9]). The FKG lattice property defined on a measure $\psi$ over a finite distributive lattice $\Omega$ states that for every $\xi,\gamma\in \Omega$ ,

(7) \begin{align}\psi(\xi\vee \gamma)\psi(\xi\wedge\gamma)\geq\psi(\xi)\psi(\gamma).\end{align}

If $\psi$ satisfies (7), it is said to be log-submodular. The FKG lattice property implies the positive association inequality:

(8) \begin{align}\psi(fg)\geq \psi(f)\psi(g) \end{align}

for all increasing functions f and g on $\Omega$ , where $\psi(f)$ represents the expectation of f with respect to $\psi$ .

This theorem can also be extended to point processes in the continuum as follows (see [Reference Chayes, Chayes and Kotecky9,Reference Georgii and Küneth12] for details). Let P be a point process on a measurable space S, with Janossy density $\psi$ with respect to a Poisson point process with intensity $\lambda$ ; then the FKG lattice property states that

(9) \begin{align}\psi(\xi\cup \gamma)\psi(\xi\cap\gamma)\geq\psi(\xi)\psi(\gamma) \quad\textrm{for all }\xi,\gamma\in M(S).\end{align}

Under this hypothesis, one can conclude positive association inequalities such as (8), where f and g are now increasing functions on M(S).

In the following, we describe an FKG lattice property that holds for the steady-state version of our model. The property holds under a specific lattice structure defined on $M(D,{\boldsymbol{C}})$ . Let $\xi=(\xi^\texttt{R},\xi^\texttt{B})$ and $\gamma=(\gamma^\texttt{R},\gamma^\texttt{B})$ be two configurations in $M(D,{\boldsymbol{C}})$ , where $\xi^\texttt{R}$ and $\gamma^\texttt{R}$ are the red particles and $\xi^\texttt{B}$ and $\gamma^\texttt{B}$ are the blue particles in the configurations. We say that $\xi>\gamma$ if and only if $\xi^\texttt{R}\supset \gamma^\texttt{R}$ and $\xi^\texttt{B}\subset\gamma^\texttt{B}$ .

Theorem 2.3. For any two finite subsets $\xi=(\xi^\texttt{R},\xi^\texttt{B})$ and $\gamma=(\gamma^\texttt{R},\gamma^\texttt{B})$ of $D\times {\boldsymbol{C}}$ , we have

(10) \begin{align}\tilde{\Pi}(\xi\vee\gamma)\tilde{\Pi}(\xi\wedge\gamma)\geq \tilde{\Pi}(\xi)\tilde{\Pi}(\gamma),\end{align}

where $\xi\vee\gamma = (\xi^\texttt{R}\cup\gamma^\texttt{R},\xi^\texttt{B}\cap \gamma^\texttt{B})$ and $\xi\wedge\gamma = (\xi^\texttt{R}\cap\gamma^\texttt{R},\xi^\texttt{B}\cup \gamma^\texttt{B})$ .

The proof of this theorem is deferred to Appendix D. We note that a similar FKG lattice property is satisfied in the binary-particle Widom–Rowlinson model with the same lattice structure.

From Theorem 2.3 and the FKG inequality (see Appendix in Chayes et al. [Reference Chayes, Chayes and Kotecky9]), we can conclude that the stationary measure is positively associated; i.e., for any two increasing functions f and g,

(11) \begin{align}\mathbb{E}_{\tilde\eta}\,f(\tilde\eta)\,g(\tilde\eta)\geq\mathbb{E}_{\tilde\eta}\,f(\tilde\eta)\mathbb{E}_{\tilde\eta}\,g(\tilde\eta),\end{align}

where $\tilde\eta$ is a version of the unordered stationary process and has the density $\tilde\pi$ with respect to the Poisson point process with intensity $\bar{\lambda}$ . The above positive association inequalities also imply that the marginal point processes of the red points (or the blue points) are also positively associated. This can be seen by taking increasing functions f and g that depend only on the red points (or the blue points). From this result and Corollary 3.1 of Błaszczyszyn and Yogeshwaran [Reference Błaszczyszyn and Yogeshwaran5], we can conclude that $\tilde\eta^\texttt{R}$ and $\tilde\eta^\texttt{B}$ are weakly super-Poissonian. Intuitively, this means that the points are more clustered than the points in a Poisson point process of the same intensity.

2.4. Boundary conditions and monotonicity

In this section, we assume that D is a compact subset of the Euclidean space $\mathbb{R}^d$ , for some $d\geq 1$ . We will use the FKG lattice property to prove monotonicity of measures under different boundary conditions. To state these results we will require the following notation. Let $\zeta\subset\mathbb{R}^d\backslash D\times{\boldsymbol{C}}$ be a valid state, i.e., $N(\zeta)\cap\zeta=\emptyset$ . For any such boundary condition, we define a measure on $M(D,{\boldsymbol{C}})$ with Janossy density

(12) \begin{equation}\begin{aligned}\tilde{\pi}_{D,\zeta}(x_1^n)&=K_{D,\zeta}\mathbb{1}(N(x_1^n)\cap (\zeta\cup x_1^n)=\emptyset)\tilde{\Pi}_{\zeta}(x_1^n),\\\tilde{\Pi}_\zeta(x_1^n)&=\sum_{(X_1^n)\in\mathcal{P}(x_1^n)}\prod_{i=1}^n\frac{1}{\bar{\lambda}(N(X_1^i)\cap{N(\zeta)}^{c})+i\mu}.\end{aligned}\end{equation}

Three important boundary conditions are $\zeta = (\mathbb{R}^d\backslash D)\times\{\texttt{R}\}$ , $\zeta = \emptyset$ , and $\zeta = (\mathbb{R}^d\backslash D)\times\{\texttt{B}\}$ . These are respectively termed the red, the free and the blue boundary conditions. We use special notation for the densities with these boundary conditions, namely, $\tilde{\pi}_{S,\texttt{R}}$ , $\tilde{\pi}_{S}$ , and $\tilde{\pi}_{S,\texttt{B}}$ .

The boundary conditions can also be partially ordered: let $\zeta_1\geq \zeta_2$ if and only if $\zeta_1^\texttt{R}\supset\zeta_2^\texttt{R}$ and $\zeta_1^\texttt{B}\subset\zeta_2^\texttt{B}$ . We are now in a position to state the first result of this section.

Outline of the proof. By Holley’s inequality (see Holley [Reference Holley14]), it is enough to prove that for two states $\eta, \gamma\in M(D,{\boldsymbol{C}})$ , we have

(13) \begin{align}\tilde{\pi}_{D,\zeta_1}(\eta\vee\gamma) \tilde{\pi}_{D,\zeta_2}(\eta\wedge\gamma)\geq \tilde{\pi}_{D,\zeta_1}(\eta)\tilde{\pi}_{D,\zeta_2}(\gamma).\end{align}

We first note that if $N(\eta)\cap( \zeta\cup\eta)=\emptyset$ and $N(\gamma)\cap(\zeta_2\cup\gamma)=\emptyset$ , then

\begin{align*}N(\eta\vee\gamma)\cap(\zeta_1\cup(\eta\vee\gamma))=N(\eta\wedge\gamma)\cap(\zeta_2\cup((\eta\wedge\gamma))=\emptyset.\end{align*}

Since the red and blue subsets do not interact by Corollary 8, we only need to show that if $\zeta_2\subset\zeta_1\subset(\mathbb{R}^d\backslash D)\times\{\texttt{R}\}$ and $\eta, \gamma\in M(D,\{\texttt{R}\})$ , then

\begin{align*}\tilde{\Pi}_{\zeta_1}(\eta\cup\gamma)\tilde{\Pi}_{\zeta_2}(\eta\cap\gamma)\geq\tilde{\Pi}_{\zeta_1}(\eta)\tilde{\Pi}_{\zeta_2}(\gamma).\end{align*}

The proof of the last statement follows by a simple modification of the proof of Theorem D.1, presented in Appendix D. Specifically, the inequality (53) in the appendix is modified to

(14) \begin{align}& \mathbb{E}\prod_{i=1}^{n+m+2k}{\left[\substack{\bar{\lambda}(N(\mathfrak{a}_{1}^{\mathfrak{S}_x(i)})\cap{N(\zeta_1)}^c)+\bar{\lambda}(N(\mathfrak{b}_{1}^{\mathfrak{S}_y(i)})\cap{N(\zeta_2)}^c)+i\mu\\ \\ \bar{\lambda}(N(\mathfrak{c}_{1}^{\mathfrak{S}_z(i)})\cap{N(\zeta_1)}^c)-\bar{\lambda}(N(\mathfrak{a}_{1}^{\mathfrak{S}_x(i)})\cap N(\mathfrak{c}_{1}^{\mathfrak{S}_z(i)})\cap {N(\zeta_1)}^c)\\ \\ +\bar{\lambda}(N(\bar{\mathfrak{c}}_{1}^{\mathfrak{S}_w(i)})\cap{N(\zeta_2)}^c)-\bar{\lambda}(N(\mathfrak{b}_{1}^{\mathfrak{S}_y(i)})\cap N(\mathfrak{c}_{1}^{\mathfrak{S}_z(i)})\cap {N(\zeta_2)}^c)}\right] }^{-1} \nonumber\\ &\geq\mathbb{E}\prod_{i=1}^{n+m+2k}{\left[\substack{\bar{\lambda}(N(\mathfrak{a}_{1}^{\mathfrak{S}_x(i)})\cap{N(\zeta_1)}^c)+\bar{\lambda}(N(\mathfrak{b}_{1}^{\mathfrak{S}_y(i)})\cap{N(\zeta_2)}^c)+i\mu\\ \\ \bar{\lambda}(N(\mathfrak{c}_{1}^{\mathfrak{S}_z(i)})\cap { N(\zeta_1)}^c)-\bar{\lambda}(N(\mathfrak{a}_{1}^{\mathfrak{S}_x(i)})\cap N(\mathfrak{c}_{1}^{\mathfrak{S}_z(i)})\cap {N(\zeta_1)}^c)\\ \\ +\bar{\lambda}(N(\bar{\mathfrak{c}}_{1}^{\mathfrak{S}_w(i)})\cap{N(\zeta_2)}^c)-\bar{\lambda}(N(\mathfrak{b}_{1}^{\mathfrak{S}_y(i)})\cap N(\bar{\mathfrak{c}}_{1}^{\mathfrak{S}_z(i)})\cap{N(\zeta_2)}^c)}\right]}^{-1},\end{align}

where the expectation is over a uniformly random choice

The rest of the proof follows similar steps to the proof in Appendix D.

Remark 2.2. The above proof can be modified to give the following interesting result. Let $D_1\subset D_2$ be two compact subsets of $\mathbb{R}^d$ . With an abuse of notation, let $\tilde{\pi}_{D_2,\texttt{R}}(\eta)$ denote the marginal Janossy density of observing $\eta$ in $D_1$ , under the measure with density $\tilde{\pi}_{D_2,\texttt{R}}$ . We similarly overload the notation for $\tilde{\pi}_{D_2,\texttt{B}}$ . With this notation, we may prove that $\tilde{\pi}_{D_1,\texttt{R}}\geq\tilde{\pi}_{D_2,\texttt{R}}$ and $\tilde{\pi}_{D_1,\texttt{B}}\leq\tilde{\pi}_{D_2,\texttt{B}}$ . For the proof, we apply Holley’s inequality, which requires that the following inequality hold:

\begin{align*}\tilde{\pi}_{D_1,\texttt{R}}(\eta\vee\gamma)\tilde{\pi}_{D_2,\texttt{R}}(\eta\wedge\gamma)\geq\tilde{\pi}_{D_1,\texttt{R}}(\eta)\tilde{\pi}_{D_2,\texttt{R}}(\gamma),\end{align*}

where $\eta,\gamma\in M(D_1,{\boldsymbol{C}})$ are two valid configurations. This follows from the inequality

\begin{align*}\tilde{\pi}_{D_1,\texttt{R}}(\eta\vee\gamma)\tilde{\pi}_{D_2,\texttt{R}}(\xi\cup(\eta\wedge\gamma))\geq\tilde{\pi}_{D_1,\texttt{R}}(\eta)\tilde{\pi}_{D_2,\texttt{R}}(\xi\cup\gamma),\end{align*}

where $\xi\in M(D_1\backslash D_2,{\boldsymbol{C}})$ is any configuration such that $\xi\cup\gamma$ is a valid configuration. The latter inequality can be proved using ideas similar to those in the proof of Theorem D.1 in Appendix D. We skip the details of the cumbersome calculations here. We only remark that such a monotonicity of measures allows us to consider the limiting extremal measures

\begin{equation*}\lim_{D_n\nearrow\mathbb{R}^d}\tilde{\pi}_{D_n,\texttt{R}}, \qquad\lim_{D_n\nearrow\mathbb{R}^d}\tilde{\pi}_{D_n,\texttt{B}}\end{equation*}

on the infinite Euclidean space $\mathbb{R}^d$ . In the next few sections, we will consider the FIFM process on infinite Euclidean spaces and prove the existence of a stationary regime. We leave the job of exploring of the connection between the stationary measure so obtained and these limiting measures to future work.

3.1. Construction of stationary regime on Euclidean spaces

The simple coupling-from-the-past argument presented in Section 2 does not hold in the case where $\lambda(D)=\infty$ , since we cannot find a sequence of regeneration times going to $\infty$ in this case. We show, however, that a coupling-from-the-past argument can still be performed locally in space. This is done by first showing that, for a compact subset C of the domain $\mathbb{R}^d$ , there exists a time $T_C$ beyond which two simulations agree for all times t beyond time $T_C$ (so, $T_C$ is not a stopping time). A key ingredient in proving the existence of $T_C$ is an analysis of the decay in first-order moment measures of the discrepancies between the two point patterns in simulation. Using this analysis, we are also able to bound the moments of $T_C$ , which enables the application of ergodic theorems, as in the simple coupling-from-the-past construction in Section 2. In the following sections, we present this coupling-from-the-past argument in detail.

3.2. A coupling of two processes

We will first obtain some results about a coupling of two different processes, ${\{\eta_t^1\}}_{t\geq 0}$ and ${\{\eta_t^2\}}_{t\geq 0}$ , starting from two different initial conditions, but driven by the same driving process $\Phi\in O(\mathbb{R}^d\times\mathbb{R},{\boldsymbol{C}}\times\mathbb{R}^+)$ . Let $\eta^1_0$ and $\eta^2_0$ be the two valid initial conditions ( $\eta^i_0\cap N(\eta^i_0)=\emptyset$ ). At any time $t\geq 0$ , there are some particles that are present in both processes. These particles will be called regular particles, and denoted by $R_t$ . Particles that are present in $\eta^1_t$ and absent in $\eta^2_t$ will be called zombies, and those that are absent in $\eta^1_t$ and present in $\eta^2_t$ will be called antizombies. We denote zombies and antizombies by $Z_t$ and $A_t$ , respectively. Further, particles in $Z_t\cup A_t$ will be called special particles and denoted by $S_t$ .

We now prove that the density of the special particles decays exponentially to zero.

Proof. Let $K\subset \mathbb{R}^d$ be compact. Define $K^+=\{y\in \mathbb{R}^d\,{:}\,d(y,K)\leq 1\}$ and $K^-={\{y\in \mathbb{R}^d\,{:}\, d(y,K^c)\leq 1\}}^c$ , $\partial K^+=K^+-K$ , and $\partial K^-=K-K^-$ . Also, for the sake of brevity, for any $V\subset\mathbb{R}^d$ let $V_{{\boldsymbol{C}}}$ denote the set $V\times {\boldsymbol{C}}$ . We will compute the difference $\mathbb{E} [Z_{t+\delta}(K_{{\boldsymbol{C}}})-Z_{t}(K_{{\boldsymbol{C}}})]$ for small $\delta>0$ , by tracking the changes that may occur in the short time interval $(t,t+\delta)$ . Recall that we use the notation $W^i_x$ to denote the domain of influence of the particle $x\in\eta^i_t$ , $i=1,2$ . Also, in the following we have $\bar{\lambda}\,{:\!=}\,\ell\otimes m_c$ on $\mathbb{R}^d\times{\boldsymbol{C}}$ . The following possibilities may occur:

• A zombie in K exits on its own by losing patience. The expected difference is

  (16) \begin{align}-\mu\delta\mathbb{E} Z_{t}(K_{{\boldsymbol{C}}})+o(\delta).\end{align}

• With probability $o(\delta)$ , two or more particles arrive or depart in $K^+$ . The expected change in $Z_t(K)$ , given that this occurs, is $o(\delta)$ .

• A zombie in K matches with a particle arriving in $K^c$ , which is accepted in the process $\eta_t^2$ . This results in a difference of

  (17) \begin{align}-\delta\mathbb{E}\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}}\bar{\lambda}(W^1_x\cap K^c_{{\boldsymbol{C}}}\cap {(N(\eta_t^2))}^c)+o(\delta).\end{align}

• A zombie in K matches with a particle arriving in K, which is accepted in the process $\eta_t^2$ . This new particle is an antizombie. The resulting change is

  (18) \begin{align}-\delta\mathbb{E}\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}}\bar{\lambda}(W_x^1\cap K_{{\boldsymbol{C}}}\cap {(N(\eta_t^{2}))}^c)+o(\delta).\end{align}

• A zombie in K matches with an arriving particle, which also matches with some particle in $K^c$ in the complementary process. This results in an expected change of

  (19) \begin{align}-\delta\mathbb{E}\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}}\sum_{y\in\eta_t^{2}\cap K^c_{{\boldsymbol{C}}}}\bar{\lambda}(W^1_x\cap W^2_y)+o(\delta).\end{align}

• A zombie in K matches with an arriving particle, which also matches with some antizombie in K. This results in an expected change of

  (20) \begin{align}-\delta\mathbb{E}\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}}\sum_{y\in A_t\cap K_{{\boldsymbol{C}}}}\bar{\lambda}(W^1_x\cap W_y^2)+o(\delta).\end{align}

• An antizombie matches with a particle arriving in K that is accepted in the complementary process. This particle becomes a zombie. This results in an expected change of

  (21) \begin{align}\delta\mathbb{E}\sum_{x\in A_t}\bar{\lambda}(W^2_x\cap K_{{\boldsymbol{C}}}\cap{(N(\eta_t^1))}^c)+o(\delta).\end{align}

• An arriving particle matches with a zombie in $K^c$ and a regular particle in $\eta_t^2\cap K_{{\boldsymbol{C}}}$ . The regular particle turns into a zombie. This results in a change of

  (22) \begin{align}\delta\mathbb{E}\sum_{\substack{x\in R_t\cap K_{{\boldsymbol{C}}}\\ y\in Z_t\cap K^c_{{\boldsymbol{C}}}}}\bar{\lambda}(W^2_x\cap W_y^1)+o(\delta).\end{align}

Taking only the contributions from (16), (18), (21), and (22) in the above changes, dividing by $\delta$ , and taking the limit as $\delta\rightarrow0$ , we obtain

\begin{align*}\frac{d\mathbb{E} Z_t(K_{{\boldsymbol{C}}})}{dt}\leq&-\mu\mathbb{E} Z_t(K_{{\boldsymbol{C}}})+\mathbb{E}\left[-\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}}\bar{\lambda}(W_x^1\cap K_{{\boldsymbol{C}}}\cap {(N(\eta_t^2))}^c)\right.\\&\mbox{}\qquad\left.+\sum_{x\in A_t}\bar{\lambda}(W^2_x\cap K_{{\boldsymbol{C}}}\cap{(N(\eta_t^1))}^c)+\sum_{\substack{x\in R_t\cap T_{{\boldsymbol{C}}}\\y\in Z_t\cap T^c_{{\boldsymbol{C}}}}}\bar{\lambda}(W^2_x\cap W_y^1)\right].\end{align*}

We have similar bounds for derivatives of $\mathbb{E}{A_t(K_{{\boldsymbol{C}}})}$ . Adding these expressions, we obtain

\begin{align}&\frac{d}{dt}\mathbb{E}{S_t(K_{{\boldsymbol{C}}})}\leq-\mu\mathbb{E}{S_t(K_{{\boldsymbol{C}}})}+\mathbb{E}\left[\sum_{\substack{x\in R_t\cap K_{{\boldsymbol{C}}}\\y\in Z_t\cap K^c_{{\boldsymbol{C}}}}}\bar{\lambda}(W^2_x\cap W_y^1)+\sum_{\substack{x\in R_t\cap K_{{\boldsymbol{C}}}\\y\in A_t\cap K^c_{{\boldsymbol{C}}}}}\bar{\lambda}(W^2_x\cap W_y^1)\right]\nonumber\\&\mbox{}\qquad\qquad+E\left[\sum_{x\in A_t\cap K_{{\boldsymbol{C}}}^c}\bar{\lambda}(W^2_x\cap K_{{\boldsymbol{C}}}\cap {N(\eta^1_t)}^c)+\sum_{x\in Z_t\cap K_{{\boldsymbol{C}}}^c}\bar{\lambda}(W^1_x\cap K_{{\boldsymbol{C}}}\cap {N(\eta^2_t)}^c)\right]\nonumber\\&\leq -\mu\mathbb{E} S_t(K_{{\boldsymbol{C}}})+4\bar{\lambda}(\partial K_{{\boldsymbol{C}}}^+\cup\partial K^-_{{\boldsymbol{C}}})\nonumber.\end{align}

Taking the limit $K\nearrow\mathbb{R}^d$ , by spatial ergodicity of the process $S_t$ , we obtain

(23) \begin{align}\frac{d}{dt}\beta_{S_t}\leq -\mu\beta_{S_t},\end{align}

from which we can conclude that $\beta_{S_t}\leq \beta_{S_0}e^{-\mu t}$ .

3.3. The coupling-from-the-past construction

In this section, we present the coupling-from-the-past construction of the stationary regime. Let $\Phi$ be a doubly infinite Poisson point process, as in Lemma A.1. That is, $\Phi$ is a Poisson point process defined on $\mathbb{R}^d\times \mathbb{R}$ , with i.i.d. marks in ${\boldsymbol{C}}\times\mathbb{R}^+$ , that is time-shift invariant. The intensity of the point process is $2\ell\otimes\ell$ , and the marks are independent of each other, with the color uniformly distributed in ${\boldsymbol{C}}$ and the patience an exponential random variable. Let ${\{\theta_t\}}_{t\in\mathbb{R}}$ be a sequence of time-shift operators such that $\Phi\circ \theta_t(L\times A)=\Phi(L\times (A-t))$ . Let ${\{\eta^T_{t}\}}_{t\geq-T}$ , $T\in\mathbb{N}$ , be a sequence of processes starting at time $-T$ with empty initial conditions and driven by arrivals from $\Phi$ . We have $\eta^T_t=\eta^0_{t+T}\circ\theta_{-T}$ .

The processes $\eta^1_t$ and $\eta^0_t$ are driven by the same Poisson point process $\Phi$ beyond time 0. Treating the particles in $\eta^1_0$ as the initial conditions, we have a coupling of ${\{\eta^1_t\}}_{t\geq 0}$ and ${\{\eta^0_t\}}_{t\geq 0}$ as in Section 3.2. The discrepancies on any bounded set go to zero exponentially fast by Lemma 3.2. In the next lemma, we prove that this exponential rate of convergence is enough to show that the time after which discrepancies never appear in any compact region has finite expectation. For any compact $K\subset D$ , define

(24) \begin{align}\tau^0(K)\,{:\!=}\,\inf\{t>0\,{:}\,\eta_{s}^1|_K=\eta^0_s|_K,\ s\geq t\},\end{align}

and in the following, let $S_t$ denote the set of discrepancies, $\eta^0_t\triangle\eta^1_t$ . Note that $\tau^0(K)$ is not a stopping time in our setting, since, first, $S_t\neq \emptyset$ for all $t\geq 0$ a.s. by spatial ergodicity, and second, once discrepancies vanish in K, they can reappear because of interactions with particles from outside of K.

Lemma 3.3. For all compact $K\subset\mathbb{R}^d$ , $\mathbb{E}\tau^0(K)<\infty$ .

Proof. We view $S_t(K)$ , $t\geq 0$ , as a birth–death process. Let $S_t(K)=S_0(K)+S^+(0,t] -S^-(0,t]$ , where $S^+$ and $S^-$ are simple counting processes. Since new special particles only result from the interaction of arriving particles with existing special particles, the rate of increase in $S^+$ is bounded above by

\begin{equation*}\sum_{x\in S_t\cap K}\ell(B(x,1))=\ell(B(0,1))S_t(K).\end{equation*}

Hence,

\begin{align*}\mathbb{E} S^+[0,\infty)&\leq\ell(B(0,1))\int_0^\infty\mathbb{E} S_t(K)dt <\infty,\end{align*}

where we use Lemma 3.2 to obtain the last inequality. Since total departures are less than total arrivals, $\mathbb{E} S^-[0,\infty)\leq\mathbb{E} S_0(K)+ \mathbb{E} S^+[0,\infty)$ . This in particular shows that $S^+[0,\infty)$ and $S^-[0,\infty)$ exist and are finite a.s. Thus, $\lim_{t\rightarrow \infty}S_t(K)$ also exists and is finite a.s. By the dominated convergence theorem,

\begin{equation*}\lim_{t\rightarrow\infty}\mathbb{E} S_t(K)=\mathbb{E}\lim_{t\rightarrow\infty}S_t(K).\end{equation*}

Thus, by Lemma 3.2, $\lim_{t\rightarrow\infty}S_t(K)=0$ a.s. This shows that $\tau^0(K)<\infty$ a.s.

Since $\tau^0(K)<\infty$ a.s., there is a last exit and we may write $\tau^0(K)\leq\int_0^\infty tS^-(dt)$ . We therefore have

\begin{align*}\mathbb{E} \tau^0(K)&\leq\mathbb{E}\int_0^\infty tS^-(dt)\\[3pt]&=\mathbb{E}\int_0^\infty tS^+(dt)-\mathbb{E}\int_0^\infty t(S^+-S^-)(dt)\\[3pt] &=\mathbb{E}\int_0^\infty tS^+(dt)+E\int_0^\infty (S^+-S^-)(t)dt,\end{align*}

where the last equality follows from a change-of-variables formula. Using the bound of $\ell(B(0,1))S_t(K)$ on the rate of arrival in $S^+$ , the first expectation can be bounded above by $\ell(B(0,1))+\int_0^\infty t\mathbb{E}S_t(K)dt$ . We thus have

\begin{align*}\mathbb{E}\tau^0(K)&\leq \ell(B(0,1))\int_0^\infty t\mathbb{E} S_t(K)dt+\int_0^\infty\mathbb{E} S_t(K)dt\\&<\infty,\end{align*}

by Lemma 3.2.

We use the above lemma to prove the following existence result, using a coupling-from-the-past argument.

Proof. Let $\tau^T(K)$ be defined as

\begin{align*}\tau^T(K)\,{:\!=}\,\inf\{t>-T\,{:}\,\eta_{s}^{T+1}|_K=\eta^T_s|_K,\ s\geq t\};\end{align*}

$\tau^T(K)$ denotes the time at which realizations of the processes $\{\eta^T_t\}$ and $\{\eta^{T+1}_t\}$ coincide inside the set K. We have

\begin{align*}\tau^T(K)=\tau^0(K)\circ\theta_{-T}-T.\end{align*}

That is,

(25) \begin{align} \tau^T(K)+T=\tau^0(K)\circ\theta_{-T}.\end{align}

Therefore, the sequence $\tau^T(K)+T$ is a stationary and ergodic sequence. By Birkhoff’s pointwise ergodic theorem and Lemma 3.3,

\begin{align*}\lim_{T\rightarrow\infty}\sum_{i=0}^T\frac{\tau^i(K)+i}{T}&=\mathbb{E}\tau^0(K)<\infty \quad\textrm{a.s.}\end{align*}

Therefore the last term in the summation,

\begin{equation*}\frac{\tau^T(K)+T}{T},\end{equation*}

goes to 0 as $T\rightarrow\infty$ . From this we conclude that

(26) \begin{align}\lim_{T\rightarrow\infty}\tau^T(K)=-\infty \quad \text{a.s.}\end{align}

This implies that for every realization of $\Phi$ , any compact set K, and $t\in \mathbb{R}$ , there exists a $k\in\mathbb{N}$ such that for all $T>k$ , $\tau^0(K)\circ \theta_{-T}-T<t$ . That is, the executions of all processes $\{\eta^T_s\}$ , $T>k$ , coincide at time t on the compact set K. Therefore, locally in the sense of total variation, the following limit is well-defined a.s.:

(27) \begin{align}\eta_t\,{:\!=}\,\lim_{T\rightarrow\infty}\eta^T_t.\end{align}

The process $\eta$ is ${\{\theta_n\}}_{n\in\mathbb{Z}}$ -compatible, since

\begin{align*}\eta_t\circ\theta_{1}&=\lim_{T\rightarrow\infty}\eta^T_t\circ \theta_1\\&=\lim_{T\rightarrow\infty}\eta^0_{T+t}\circ\theta_{-T+1}\\&=\lim_{T\rightarrow\infty}\eta^0_{t+1+T-1}\circ\theta_{-T+1}\\&=\eta_{t+1}.\end{align*}

Further, the process can also be shown to be ${\{\theta_s\}}_{s\in\mathbb{R}}$ -compatible: for any $s\in\mathbb{R}$ , by a similar backward coupling argument, it can be shown that

\begin{equation*}\lim_{T\rightarrow\infty}\eta^{T+s}_t=\lim_{T\rightarrow\infty}\eta^T_t \textrm{ a.s.}\end{equation*}

Since $\eta^{T+s}_t=\eta^T_{t+s}\circ\theta_{-s}$ , we have $\eta_{t+s}=\eta_t\circ\theta_s$ . This proves that ${\{\eta_t\}}_{t\in \mathbb{R}}$ is the stationary regime of the process.

B.1. Dynamic reversibility of Markov processes

In this section we give a brief discussion of a result needed to construct the product-form distribution. This concept will be termed dynamic reversibility of a Markov process, following the terminology in Kelly [Reference Kelly16], where the concept was discussed for Markov processes on countable state spaces. We thus define it first on countable state spaces, then on general state spaces.

Let ${\{X(t)\}}_{t\in\mathbb{R}}$ be a stationary, irreducible continuous-time Markov process with values in a countable state space S. Let q(j, k) denote the transition rate from state $j\in S$ to $k\in S$ , and let $\pi$ be the stationary distribution of the process. In this case, the balance equations are $\sum_{j\in S}\pi(j)q(j,k)=0$ .

The reversed process, $X(\!-t)$ , is also a stationary Markov process, with transition rates

\begin{equation*}q'(j,k)=\frac{\pi(k)q(k,j)}{\pi(j)}.\end{equation*}

The converse of this statement can be used as a characterization of the stationary distribution. We state this result in the following theorem.

Theorem B.1. Let X(t) be a stationary irreducible Markov process with transition rates $q(j,k),\ j,k\in S$ . If there exists a collection of numbers $q'(j,k),\ j,k\in S$ , and a probability measure $\pi$ on S such that

(31) \begin{align}\pi(j)q(j,k)=\pi(k)q'(k,j),\quad j,k\in S, \end{align}

and

(32) \begin{align}\sum_{k\in S}q'(j,k)=0, \quad j\in S,\end{align}

then $\pi$ is the stationary distribution of the process, and q’ is the transition rate matrix for the time-reversed process.

Thus, if we can guess the transition rates of the reversed process and a stationary measure, we can verify them by checking a local balance condition of the form (31). See Theorem 1.13 of Kelly [Reference Kelly16] for a proof of this result. In practice, finding q’ is usually as intractable as finding the stationary distribution directly. However, occasionally we may come across pairs of Markov processes that are reversed versions of each other, perhaps after a transformation of the state space. We state this phenomenon in the next theorem.

Theorem B.2. Let S and T be two countable spaces. Let X(t) and Y(t) be two stationary irreducible Markov processes with values in S and T, and with transition matrices q and q’ respectively. Suppose there is an isomorphism $\phi\,{:}\,S\rightarrow T$ between the two spaces. Also suppose that there is a probability measure $\pi$ on S such that

\begin{align*}\pi(j)q(j,k)=\pi(k)q'(\phi(k),\phi(j)),\quad j,k\in S.\end{align*}

Then $\pi$ is the stationary distribution of X(t) and $\pi(\phi^{-1}(\cdot))$ is the stationary distribution of Y(t).

Theorem B.2 can be extended to a more general setting, as follows.

Theorem B.3. Let S and T be two locally compact Hausdorff topological spaces. Let X(t) and Y(t) be two stationary Markov jump processes with values in S and T. Suppose the probability semigroup of the process X(t) (resp. Y(t)) is characterized by the generators $L_X$ (resp. $L_Y$ ), defined over $dom(L_X)$ (resp. $dom(L_Y)$ ), where the domain is a subset of the Banach space of continuous functions over S (resp. T) vanishing at infinity, equipped with the uniform norm topology. Let $\phi\,{:}\,S\rightarrow T$ be a measure space isomorphism such that for all $f\in dom(L_X)$ , we have $f\circ\phi^{-1}\in dom(L_Y)$ . If $\pi$ is a probability measure on S such that

\begin{align*}\int_{S}f(x)L_X g(x)\pi(dx)=\int_TL_Y(f\circ\phi^{-1})(y)g\circ\phi^{-1}(y)\phi_{*}\pi(dy),\end{align*}

then $\pi$ is a stationary distribution for X(t).

Proof. Let g be any element in $dom(L_X)$ . Taking a sequence $f_n\in dom(L_Y)$ such that $f_n$ converges pointwise to the constant function 1 as $n\rightarrow\infty$ , we have

\begin{align*}\int_{S}L_X g(x)\pi(dx)=\int_TL_Y(1)(y)g\circ\phi^{-1}(y)\phi_{*}\pi(dy)=0.\end{align*}

By standard results from the theory of positive operator semigroups, it is known that for $g\in dom(L_X)$ , the map $x\mapsto \mathbb{E}[g(X(t))|X(0)=x]$ belongs to $dom(L_X)$ (see Lemma 1.3 of Engel and Nagel [Reference Engel and Nagel11], for example). Thus, for $g\in dom(L_X)$ , we have

\begin{align*}\frac{d}{dt}\int_{S}\mathbb{E}[g(X(t))|X(0)=x]\pi(dx)=\int_{S}L(\mathbb{E}[g(X_t)|\cdot])(x)\pi(dx) =0.\end{align*}

It is also known that $dom(L_X)$ is dense on the space of continuous functions vanishing at infinity (Theorem 1.4 of Engel and Nagel [Reference Engel and Nagel11]). This implies that $\mathbb{E}_\pi g(X(t))=\mathbb{E}_\pi g(X(0))$ for all bounded continuous functions and all $t>0$ , and so $\pi$ must be a stationary measure of X(t).

If two processes satisfy the hypotheses of the above theorem, we say that the processes are dynamically reversible.

B.2 Additional global notation

In the following few sections we need some notation to define the transitions in the Markov processes. We collect this notation in this section.

Let $\gamma=(x_1,\ldots, x_n)$ , $n\in \mathbb{N}$ , and x respectively be a list of elements and a particular element belonging to the same abstract space S. We define the following operators:

1. 1. Let $\gamma \blacktriangleleft_i x$ , $i=0,\ldots,n$ , denote the insertion of the element x after the ith element in $\gamma$ ; i.e.,

   \begin{equation*}\gamma\blacktriangleleft_i x=(x_1,\ldots,x_i,x,x_{i+1},\ldots,x_n).\end{equation*}

2. 2. Let $\gamma\blacktriangleright_i$ , $i=1,\ldots,n$ , denote the removal of the ith element of $\gamma$ ; i.e.,

   \begin{equation*}\gamma\blacktriangleright_i\,{=}\,(x_1,\ldots,x_{i-1}, x_{i+1},\ldots,x_n).\end{equation*}

3. 3. Let $\gamma\blacktriangle_i x$ denote the replacement of the ith element in $\gamma$ with x; i.e.,

   \begin{equation*}\gamma\blacktriangle_i\, x=(x_1,\ldots,x_{i-1},x,x_{i+1},\ldots,x_n).\end{equation*}

In the above notation, we may drop the subscript i if $i=|\gamma|$ , i.e., when we are making changes to the last element. Also, when composing these operators, unless clarified using parentheses, the order of application of operations is from left to right.

B.3 Continuous-time first-come-first-served bipartite matching model with reneging

In this section, we illustrate how dynamic reversibility is used in the proof of Theorem 2.2, by working on a countable state space Markov model. This allows us to organize and present the main ideas without the complexity of dealing with measure-valued processes.

Specifically, in this section, we consider the following modified version of the FCFS bipartite matching model considered in Adan et al. [Reference Adan, Bušić, Mairesse and Weiss1]. Consider two finite sets of types $\mathcal{C}=\{c_1,\ldots, c_I\}$ and $\mathcal{S}=\{s_1,\ldots, s_J\}$ and a bipartite compatibility graph $G=(\mathcal{C},\mathcal{S},\mathcal{E})$ with $\mathcal{E}\subset\mathcal{C}\times\mathcal{S}$ . Let $\bar{\lambda}$ be a measure on $C\cup S$ , and let $\mu>0$ be a parameter. We say that c and s can be matched or are compatible if $(c,s)\in\mathcal{E}$ in the compatibility graph E. We define the FCFS bipartite matching model with reneging as a Markov jump process with state space $\Gamma$ , which is the set of all finite ordered lists of elements from $C\cup S$ such that for every $c\in C$ and $s\in S$ in the list, $(c,s)\notin \mathcal{E}$ . Furthermore, given that the state of the process at any time t is $\gamma=(x_1,\ldots,x_n)$ , the state is updated with the following transition rates:

1. 1. A new element $x\in C\cup S$ arrives at rate $\lambda(x)$ . At the time of the arrival, if there are one or more elements in $\gamma$ that are compatible with x, then the first such element, $x_i$ , is removed, and we say that x and $x_i$ are matched. If there is no such element, then x is added to the end of the list $\gamma$ .

2. 2. Each element in the list is removed at rate $\mu>0$ .

The comments and results of Sections 2.1 and 2.2 can be mirrored in this setting. We briefly review them here.

We can simulate the above process using arrivals from a Poisson point process $\Phi$ on $(C\cup S)\times\mathbb{R}$ , with i.i.d. exponential marks in $\mathbb{R}^+$ , and with intensity $\lambda\otimes\ell$ . The base of the Poisson point process $\Phi$ encodes the arrivals of the agents, and the mark of a point encodes the time each agent is willing to wait (its patience), if it is accepted. We will use the following notation: for any point $x\in (C\cup S)\times\mathbb{R}\times \mathbb{R}^+$ , $c_x$ will denote its projection onto $C\cup S$ , $b_x$ will denote the second coordinate, and $w_x$ will denote the third coordinate.

Standard coupling- or Lyapunov-based arguments can be used to show that this Markov process has a stationary regime. Moreover, a stationary version of the process can be constructed via a coupling-from-the-past scheme that uses an ergodic arrival process, $\Phi$ , which is now a Poisson point process on $(C\cup S)\times \mathbb{R}$ , with marks as above. To construct the stationary regime, the notion of regeneration time of the system may be defined as follows. We say that $t\in \mathbb{R}$ is a regeneration time of $\Phi$ if for all $x\in \Phi$ with $b_x< t$ , we have $t-b_x>w_x$ . The forward-time construction of the process starting from a regeneration time with empty initial conditions is clear. Moreover, if $t_1<t_2$ are two regeneration times and $\eta^1$ and $\eta^2$ are such processes starting from $t_1$ and $t_2$ respectively, then for $t>t_2$ , $\eta^1_{t}=\eta^2_t$ . Thus, we can construct a bi-infinite stationary version, ${\{\eta_t\}}_{t\in\mathbb{R}}$ , of this process as a factor of $\Phi$ , if we can find a sequence of regeneration times going to $-\infty$ . Indeed, if $t_1>t_2>\cdots$ is such a sequence (with $t_0$ set to $\infty$ ), then the $\eta_t$ for $t\in[t_i,t_{i-1})$ , for some $i\in\mathbb{N}$ , is obtained by simulating the process, starting from empty initial conditions, from time $t_i$ until time t. An argument similar to that of Lemma A.1 can be used to show the existence of such a sequence of regeneration times.

This coupling-from-the-past scheme yields the definition of the matching function,

\begin{equation*}m\,{:}\,\Phi\rightarrow (C \cup S)\times \mathbb{R},\end{equation*}

similar to the one defined in Section 2.2. For $x\in \Phi$ , let $T\in\mathbb{R}^-$ be a regeneration time before $b_x$ . The value of m(x) can be set by simulating the process using $\Phi$ , starting from time T, with empty initial conditions. If x is matched to an agent $y\in \Phi$ , then $m(x)=(c_y,b_y)$ . Otherwise, if x reneges, then $m(x)=(c_x,b_w+w_x)$ .

Given the function m, we can obtain the process $\eta_t$ , since $\eta_t=(x\in\Phi\,{:}\, b_x\leq t< b_{m(x)})$ , where the agents in the list are ordered according to their birth times $b_\cdot$ . Let $\texttt{m}$ and $\texttt{u}$ be additional marks, respectively indicating whether an agent is matched or unmatched. Consider the detailed stochastic process ${\{\hat\eta_t\}}_{t\in\mathbb{R}}$ defined as follows, for $t\in\mathbb{R}$ :

1. 1. Let $T_t=\min\{b_x\,{:}\,x\in \Phi, b_x\leq t< b_{m(x)}\}$ .

2. 2. Let

   \begin{equation*}\Gamma_{\texttt{u},t}=\{(c_x,b_x,\texttt{u})\,{:}\,x\in \Phi, T_t\leq b_x\leq t<b_{m(x)}\}\end{equation*}
   and
   \begin{equation*}\Gamma_{\texttt{m},t}=\{(c_x,b_{m(x)},\texttt{m})\in N\,{:}\, b_x\leq t,T_t\leq b_{m(x)}\leq t \}.\end{equation*}

3. 3. Define $\hat\eta_t\,{:\!=}\,((c_x,s_x)\,{:}\,x\in \Gamma_{\texttt{u},t}\cup \Gamma_{\texttt{m},t})$ , where $s_y$ refers to the matched or unmatched status of an agent $y\in\Gamma_{\texttt{u},t}\cup\Gamma_{\texttt{m},t}$ , and the list is ordered according to the second coordinate, $b_{(\cdot)}$ .

Clearly, $\eta_t$ can be obtained from $\hat\eta_t$ by removing the agents with marks $\texttt{m}$ . We call the process $\hat\eta_t$ the backward detailed process, following the terminology in Adan et al. [Reference Adan, Bušić, Mairesse and Weiss1].

Since the backward detailed process at time t only depends on the points of $\Phi$ before time t, it is a stationary process. Moreover, it is a stationary version of some Markov process, since for $t<s$ , the state at time s can be constructed using the state at time t and the process $\Phi$ in the interval (t, s]. We describe this Markov process in detail now. A valid state of this Markov process is a finite list of elements $(x_1,\ldots,x_n)$ from the set $(C\cup S)\times \{\texttt{u},\texttt{m}\}$ , such that the following hold:

1. 1. $s_{x_1}=\texttt{u}$ if $n\geq 1$ .

2. 2. If $s_{x_i}=s_{x_j}=\texttt{u}$ , then $(c_{x_i},c_{x_j})\notin \mathcal{E}$ .

3. 3. For all $i<j$ , if $s_i=\texttt{u}$ and $s_j=\texttt{m}$ , then $(c_{x_i},c_{x_j})\notin\mathcal{E}$ .

Below, we utilize the definitions in Appendix B.2. Additionally, mirroring our notation in the continuum setting, for any $x\in C\cup S$ let

\begin{equation*}N(\{x\})=\{y\in C\cup S\,{:}\, (x,y)\in \mathcal{E}\textrm{ or }(y,x)\in\mathcal{E}\},\end{equation*}

and for any $A\subseteq C\cup S$ let $N(A)=\cup_{x\in A} N(\{x\})$ . With an abuse of notation, we will let $N(x)\,{:\!=}\,N(\{x\})$ for $x\in C\cup S$ . Also, for $\gamma \in O(C\cup S,\{\texttt{u},\texttt{m}\})$ and any $x\in\gamma$ , we will write

\begin{align*}\gamma^x&=\{y\in\gamma\,{:}\,y<_\gamma x\};\\[3pt] \gamma^\texttt{u}&=\{y\in\gamma\,{:}\,s_y=\texttt{u}\}, \qquad \gamma^\texttt{m}=\{y\in\gamma\,{:}\,s_y=\texttt{m}\};\\[3pt] W_x&=\begin{cases}N(c_x)\backslash N(\gamma^{\texttt{u},x}) &\textrm{ if } s_x=\texttt{u},\\[3pt] \emptyset & \textrm{otherwise}.\end{cases}\end{align*}

The transitions and transition rates for the backward detailed process are the following, given that the state of system is $\hat\eta=(x_1,\ldots, x_n)$ :

1. 1. Any agent $x_i\in \hat\eta$ , with $s_{x_i}=\texttt{u}$ , loses patience. In this case, the new state is $\hat\eta'=\hat\eta\blacktriangleright_i\blacktriangleleft(c_{x_i},\texttt{m})$ , except possibly when $i=1$ , where we need to prune all the leading matched and exchanged elements from $\hat\eta'$ . We still denote the new state by $\hat\eta\blacktriangleright_i\,\blacktriangleleft(c_{x_i},\texttt{m})$ , even in this case, keeping in mind that all leading matched terms must be removed. Each such transition occurs at rate $\mu$ .

2. 2. A new agent $x=(c_x,\texttt{u})$ , $c_x\in C\cup S$ , arrives and is matched to the agent $x_i\in \hat\eta$ , with $(c_{x_i}, c_x)\in\mathcal{E}$ and $s_{x_i}=\texttt{u}$ . In this case, the new state is (a valid pruning of) $\hat\eta\blacktriangle_i\,(c_x,\texttt{m})\blacktriangleleft(c_{x_i},\texttt{m})$ . This occurs at rate $\bar{\lambda}(c_x)\mathbb{1}\left (c_x\in W_{x_i} \right)$ .

3. 3. A new agent $x=(c_x,\texttt{u})$ , with $c_x\in C\cup S$ , arrives and is not matched to any agent. The new state is $\hat\eta\blacktriangleleft x $ . This occurs at rate $\bar{\lambda}(c_x) \mathbb{1}(c_x\notin N(\hat\eta^\texttt{u}))$ .

We now define the forward detailed process, which is the dual of the process ${\{\hat\eta_t\}}_{t\in\mathbb{R}}$ , and which we denote by ${\{\check\eta_t\}}_{t\in\mathbb{R}}$ . For $t\in\mathbb{R}$ , define the following:

1. 1. Let $Y_t=\max\{b_{m(x)}:x\in \Phi, b_x\leq t< b_{m(x)}\}$ .

2. 2. Let

   \begin{equation*}\Xi_{\texttt{m},t}=\{(c_x,b_{m(x)},\texttt{m})\,{:}\,x\in \Phi, b_x\leq t<b_{m(x)}\}\end{equation*}
   and
   \begin{equation*}\Xi_{\texttt{u},t}=\{(c_x,b_x,\texttt{u})\,{:}\,t< b_x<Y_t, t<b_{m(x)}\}.\end{equation*}

3. 3. Let $\check\eta_t=((c_x,s_x)\,{:}\,x\in\Xi_{\texttt{u},t}\cup \Xi_{\texttt{m},t})$ , where the elements are ordered according to the second coordinate $b_{(\cdot)}$ .

The forward detailed process is also a stationary version of a Markov process. Any valid state $(x_1,\ldots, x_n)$ of this Markov process of the system satisfies the following:

1. 1. $s_{x_n}=\texttt{m}$ when $n\geq 1$ .

2. 2. If $s_{x_i}=s_{x_j}=\texttt{m}$ , then $(c_{x_i},c_{x_j})\notin\mathcal{E}$ .

3. 3. If $i<j$ , $s_{x_i}=\texttt{u}$ , $s_{x_j}=\texttt{m}$ , then $(c_{x_i},c_{x_j})\notin\mathcal{E}$ .

The transitions and the transition rates of the Markov process are as follows: given that the state of the system is $\check\eta$ , the next jump occurs at rate $\bar{\lambda}(C\cup S)+Q^0_\texttt{m}(\check\eta)\mu$ , where $Q^i_\texttt{m}(\check\eta)$ is the number of matched elements in $\check\eta$ after ith location. Intuitively, this is so because the total rate of new arrivals is $\bar{\lambda}(C\cup S)$ and the total death rate is $Q^0_\texttt{m}\mu$ , since $Q^0_\texttt{m}$ is the number of matched agents in the forward process. For the sake of brevity, let us denote $\bar{\lambda}(C\cup S)+n\mu$ by $\rho(n)$ , for all $n\in\mathbb{N}$ . If $\check\eta$ is non-empty, at each jump, to obtain the new state, we need to process the first element, $x_1$ , in $\check\eta$ . This is done with the following probabilities:

1. 1. If $x_1$ is matched, then it is removed from $\check\eta$ . The new state is $\check\eta\blacktriangleright_1$ .

2. 2. If $x_1$ is unmatched, then for the next state, we sample a random variable $\tau\in\mathbb{N}$ with distribution

   \begin{align*}\mathbb{P}(\tau=k)=\frac{\mu}{\rho(Q^k_\texttt{m}+1)}\prod_{i=1}^{k-1}\frac{\rho(Q^i_\texttt{m})}{\rho(Q^i_\texttt{m}+1)},\end{align*}
   and then sample $x_{n+1},\ldots x_{\tau}$ i.i.d. random unmatched elements in $\{C\cup S\}$ with distribution $\bar{\lambda}(\cdot)/\bar{\lambda}(C\cup S)$ .

   1. (a) If there is an FCFS matching $x_i$ , $2\leq i\leq \tau$ , then we set the new state to $(x_1^{\max(n,\tau)})\blacktriangle_i\,(c_{x_1},\texttt{m})\blacktriangleright_1$ , with the understanding that all the ending unmatched agents are discarded.

   2. (b) If there is no FCFS matching, we set the new state to $(x_1^{\max(n,\tau)})\blacktriangleleft_\tau(c_{x_1},\texttt{m})\blacktriangleright_1$ .

If the state is $\check\eta=\emptyset$ , then the next jump occurs at rate $\bar{\lambda}(C\cup S)$ . When a jump occurs, a random unmatched point $x_1\in C\cup S$ is sampled with distribution $\bar{\lambda}(\cdot)/\bar{\lambda}(C\cup S)$ . The next state is decided as in Step 2 above, with this new $\check\eta=x_1$ ; we ignore the details here.

We have the following theorem.

Theorem B.4. The two processes $\hat\eta_t$ and $\check\eta_t$ are dynamically reversible. The concerned isomorphism $\phi$ is the one that takes a valid state $\hat\eta$ , reverses the order of its elements, and flips the marks $\texttt{u}$ and $\texttt{m}$ . The stationary distribution is

\begin{align*}\pi(\hat\eta)&=K\mathbb{1}(\hat\eta\textrm{ is valid}) \prod_{i=1}^{n}\frac{\lambda(c_{x_i})}{\rho(Q^i_\texttt{u})},\\[3pt] \Pi(\emptyset)&=K,\end{align*}

where $\hat\eta=(x_1,\ldots,x_n)$ and where K is a normalizing constant.

Outline of the proof. To prove this, we start by looking at the balance equations of the form in Theorem B.2. Let $\hat\eta$ be the state of the backward detailed process, and let $\hat\eta'$ be a state after a valid transition. In the following, we illustrate the local balance condition (31) for only one type of transition; other types can be handled similarly. Let q and q’ be the transition rates of the backward and forward detailed processes, respectively. Also, let $c_j(\gamma)$ denote the type of the jth element in $\gamma$ , for any $\gamma\in O(C\cup S)$ .

Suppose that $\hat\eta=(x_1,\ldots,x_n)$ , $n>0$ , and that $\hat\eta'$ is obtained from $\hat\eta$ when one of the elements $x_i$ , at some location $i>1$ , is matched and exchanged with a new arrival $(c_x,\texttt{u})$ . In this case, $\hat\eta'= \hat\eta\blacktriangle_i\,(c_x,\texttt{m})\blacktriangleleft(c_{x_i},\texttt{m})$ , and

(33) \begin{align*}\frac{\pi(\hat\eta)}{\pi(\hat\eta')}q(\hat\eta,\hat\eta')&=\lambda(c_x)\prod_{j=1}^{|\hat\eta|}\frac{\lambda(c_j(\hat\eta))}{\rho(Q^j_\texttt{u}(\hat\eta))}\prod_{j=1}^{|\hat\eta'|}\frac{\rho(Q^j_\texttt{u}(\hat\eta'))}{\lambda(c_j(\hat\eta'))}.\end{align*}

The first $i-1$ elements in $\hat\eta'$ are $x_1,\ldots,x_{i-1}$ , and $|\hat\eta'|=|\hat\eta|+1$ . Moreover, $Q^j_\texttt{u}(\hat\eta)=Q^j_\texttt{u}(\hat\eta')+1$ for $i\leq j\leq |\hat\eta|$ . Hence, Equation (33) simplifies to

\begin{align*}\frac{\pi(\hat\eta)}{\pi(\hat\eta')}q(\hat\eta,\hat\eta')&=\prod_{j=i}^{|\hat\eta|}\frac{\rho(Q^j_\texttt{u}(\hat\eta'))}{\rho(Q^j_\texttt{u}(\hat\eta')+1)}\times\rho(Q^{|\hat\eta'|}_\texttt{u}(\hat\eta))\\[3pt]&=\mathbb{P}(\tau_{\phi(\hat\eta')}> |\phi(\hat\eta')|-i)\times \rho(Q^0_\texttt{m}(\phi(\hat\eta')))\\[3pt] &=q'(\phi(\hat\eta'),\phi(\hat\eta)).\end{align*}

We claim that local balance equations for other valid transitions can be handled similarly. This completes the proof of this theorem.