1

# Parallel Batched Interpolation Search Tree

Vitaly Aksenov  ITMO University  ,  Ilya Kokorin  ITMO University  and  Alena
Martsenyuk  MIPT

(Date: August 2021)

###### Abstract.

Ordered set (and map) is one of the most used data type. In addition to
standard set operations, like insert, delete and contains, it can provide set-
set operations such as union, intersection, and difference. Each of these set-
set operations is equivalent to batched operations: the data structure should
process a set of operations insert, delete and contains. It is obvious that we
want these “large” operations to be parallelized. Typically, these sets are
implemented with the trees of logarithmic height, such as 2-3 tree, Treap, AVL
tree, Red-Black tree, etc. Until now, little attention was devoted to data
structures that work better but under several restrictions on the data. In
this work, we parallelize Interpolation Search Tree which serves each request
from a _smooth_ distribution in doubly-logarithmic time. Our data structure of
size $n$ performs a batch of $m$ operations in $O(m\log\log n)$ work and poly-
log span.

††conference: ACM SIGPLAN Conference on Programming Languages; January 01–03,
2018; New York, NY, USA††journalyear: 2018††doi: ††copyright: none

##  1\. Preliminaries

### Model.

We use the work-span model to calculate the complexity of our algorithm.

### Related work.

There are several works that presented parallel batched search trees. Paul,
Vishkin and Wagener (Paul et al., 1983) studied 2-3 trees. Park and Park (Park
and Park, 2001) showed similar results for red-black trees. Blelloch and Reid-
Miller (Blelloch and Reid-Miller, 1998) presented a work-efficient parallel
batched treap. Akhremtsev and Sanders (Akhremtsev and Sanders, 2016) looked on
work-efficient $(a,b)$-trees. And, finally, Blelloch et al. (Blelloch et al.,
2016) worked on the parallel work-efficient batched generic binary search
trees with the only provided _Join_ function. However, none of these works
consider the trees that could have lower than logarithmic height under a wide
range of distributions. In this work, we consider the parallel batched version
of Interpolation Search Tree (later called IST) introduced in (Mehlhorn and
Tsakalidis, 1993). The main difference with the previously researched data
structures is that insertions, deletions and searches with smoothly
distributed arguments take $O(\log\log n)$ time, where $n$ is the size of the
tree.

### Standard functions.

We need to use several standard _parallelizable_ functions. _Span_ function
calculates the prefix sums of the array of size $n$ in $O(n)$ work and $O(\log
n)$ span. _Filter_ function filters out all the elements that do not satisfy
the condition $C$. If the size of the array is $n$, it takes
$O(n\cdot\mathrm{cost}(C))$ work and $O(\log n\cdot\mathrm{cost}(C))$ span.
Please note that in our data structure condition functions are pretty simple
and they work in $O(1)$, thus, the complexity of filter becomes $O(n)$ work
and $O(\log n)$ span. Also, we need _rank_ function that given two sorted
arrays $a$ and $b$ of sizes $n$ and $m$, correspondingly, finds the position
$k$ of each element $a[i]$ in $b$ such that $b[k-1]\leq a[i]\leq b[k]$. It
works in $O(n+m)$ work and $O(\log^{2}(n+m))$ span. Moreover, we need _merge_
algorithm that given two sorted arrays $a$ and $b$ of size $n$ and $m$,
correspondingly, merges to arrays together with $O(n+m)$ work and
$O(\log^{2}(n+m))$ span. 111We can just use _rank_ to achieve such merge
complexity. Finally, we need a _parallel-for_ loop on $n$ iterations that
executes each loop step in parallel. It is implemented using a binary-
splitting technique and introduces additional $O(\log n)$ span and $O(n)$
work.

### Result.

Our data structure, parallel batched IST, performs a batch of $M$ requests in
expected $O(M\log\log(n+M))$ work and $\mathrm{polylog}(n+m)$ span. It
outperforms parallel batched Treap presented in (Blelloch et al., 2016) on our
experiments.

##  2\. IST definition

###### Definition 1.

Let $a$ and $b$ are reals. An Interpolation Search Tree (IST) with boundaries
$a$ and $b$ for a set of $n$ keys $\\{x_{1},\ldots,x_{n}\\}\subseteq[a,b]$
consists of:

  1. (1)

An array REP of representatives
$x_{i_{1}},\ldots,x_{i_{k}},i_{1}<i_{2}<\ldots<i_{k}$ that is
$\text{REP}[j]=x_{i_{j}}$. Furthermore, $k$ satisfies $\sqrt{n}/2\leq k\leq
2\cdot\sqrt{n}$.

  2. (2)

Interpolation search trees $T_{1},\ldots,T_{k+1}$ for subarrays of keys
$S_{1},\ldots,S_{k+1}$ where $S_{j}=\\{x_{i_{j-1}+1},\ldots x_{i_{j}-1}\\}$
for $2\leq j\leq k$, $S_{1}=\\{x_{1},\ldots,x_{i_{1}-1}\\}$, and
$S_{k+1}=\\{x_{i_{k}+1},\ldots,x_{n}\\}$. Furthemore, tree $T_{j}$, $2\leq
j\leq k$ has boundaries $x_{i_{j-1}}$ and $x_{i_{j}}$, $T_{1}$ has boundaries
$a$ and $x_{1}$, and $T_{k+1}$ has boundaries $x_{k}$ and $b$.

  3. (3)

An array $\text{ID}[1,\ldots,m]$, where $m$ is some integer, with
$\text{ID}[i]=j$ iff $\text{REP}[j]<a+i(b-a)/m\leq\text{REP}[j+1]$.

Array REP contains a sample of the keys and array ID helps to find a value in
the array REP, i.e., it gives the first approximation that is then corrected
to the actual position, using some search technique, for example, binary
search. We require _ideal_ IST to have the samples in REP to be equally
spaced. We rebuild subtrees in insertion and deletion algorithms at
_appropriate_ time intervals, i.e. when enough insert or delete operations
have been executed on that subtree.

###### Definition 2.

An IST with parameter $\alpha$, $\frac{1}{2}\leq\alpha<1$, for set $S$ of size
$n$ is _ideal_ if $i_{j}=j[\sqrt{n}]$ for all $j\geq 1$, if $m=[n^{\alpha}]$,
and if the subtrees are again ideal ISTs.

In the ideal IST the first level node contains $\sqrt{n}$ keys, all nodes on
the second level contains $\sqrt[4]{n}$ keys, and so on.

###### Theorem 3.

Let $\frac{1}{2}\leq\alpha<1$. Then an ideal IST for an ordered set $S$ of
size $n$ can be built in $O(n)$ time and require $O(n)$ space. It has depth
$O(\log\log n)$.

Additionally, at each subtree $T$ we maintain the number of operations from
the last rebuild $C(T)$, the size of the subtree just after the last rebuild
$S_{0}(T)$, and the current size of the subtree $S(T)$.

Thus, an insertion and a deletion work as follows. They traverse the IST
recursively, visiting in each node the desired child, also they maintain the
counters $C(T)$ and $S(T)$ until it finds a node with $C(T)\geq S_{0}(T)/4$.
At that node it builds a new _ideal_ IST out of $T$ including the element,
being inserted. Deletions are performed by marking the element to be deleted.
The element is physically removed only during the rebuild operation.

###### Theorem 4 ((Mehlhorn and Tsakalidis, 1993)).

Let $\mu$ be a smooth density of finite support $[a,b]$ with parameter
$\alpha$, $\frac{1}{2}\leq\alpha<1$, and let $T$ be a $\mu$-random IST of size
$n$. Then, the expected cost of processing a $\mu$-random search is
$O(\log\log n)$ and $O(\log^{2}n)$ worst time. The expected amortized cost of
processing a $\mu$-random insertion and deletion is $O(\log\log n)$ and
$O(\log n)$ worst case amortized time.

##  3\. Parallel Construction of Ideal IST

We start the description of our algorithm with how to build an ideal IST from
the sorted array $a$ of keys with length $n$.

For that we choose each $[\sqrt{n}]$-th element
($[\sqrt{n}],2[\sqrt{n}],\ldots$) and create an array REP out of them. Then,
recursively build the ideal ISTs from subarrays $a[1,\ldots,[\sqrt{n}]-1]$,
$a[[\sqrt{n}]+1,2[\sqrt{n}]-1]$, and so on. To build them we used a parallel-
for loop with $O(\sqrt{n})$ iterations giving $O(\sqrt{n})$ work and $O(\log
n)$ span. Finally, we have to find array ID of length $m=n^{\alpha}$, i.e.,
for each $k$ find the position of $a+k\cdot(b-a)/m$ in array REP. For that we
can use the standard _rank_ algorithm with $O(n+m)=O(m)$ work and
$O(\log^{2}(n+m))=O(\log^{2}n)$ span.

Our rebuild algorithm runs recursively on $O(\log\log n)$ levels, since the
height of an ideal tree is $O(\log\log n)$. Thus, in total the work is $O(n)$
by Theorem 3 and the span is $O(\log\log n\cdot\log^{2}n)$.

##  4\. Flatten IST into Array

The other thing that we need for our data structure is to flatten the tree:
get all the unmarked keys of the tree into the sorted array. For that we use
the counters $S$ for the size of subtrees. We create an array with the length
of REP array and calculate prefix sums of the sizes of the subtrees using
_scan_ function while _filtering_ out the marked keys in REP array. Then, we
recursively go into subtrees knowing the position where they should be located
in the array. The height of IST is $O(\log n)$ at worst. Thus, this algorithm
works in $O(n)$ work and $O(\log^{2}n)$ span.

##  5\. Batched operations

Now, we are given a batch of $M$ operations that we want to apply to a
$\mu$-random IST $T$. At first, we compare how many operations was done to $T$
since the last rebuild $C(T)$ with the size of $T$, $S_{0}(T)$, after the last
rebuild divided by $4$, i.e., $S_{0}(T)/4$. If the number of operations is
smaller, then we simply find for each operation in which subtree it should go
using standard search algorithm in REP array of IST, mark the necessary
elements to be inserted or deleted, and then continue recursively with each
subtree. Also, we update the size of the subtree. Otherwise, if the number of
operations since the last rebuild is bigger, then we transform the tree into a
sorted array using the previously described algorithm, merge it with the keys
of operations, apply the operations using _parallel-for_ loop, and, finally,
build the tree from a sorted array using the previously described algorithm.
Since the height of IST is at most $O(\log n)$, the work is expected to be
$O(M\log\log(n+M))$ and the span is $O(\mathrm{polylog}(n+M))$.

##  6\. Experiments

We implement the data structure on C++ and compile it with OpenCilk 1.0
compiler (ope, [n.d.]) using -O2 flag. We wrote the code with the help of the
pctl library presented in (Acar et al., 2019). It contains the scalable
implementations of standard functions and provides an automatic solution to
the granularity problem. Also, to resolve the issue with the parallel memory
allocation we used tcmalloc (Google, [n.d.]).

We run our code on an Intel Xeon Gold 6230 machine with 16 cores.

We compared our parallel batched IST with the parallel batched Treap explained
in (Blelloch et al., 2016) and the sequential std::set from C++ standard
library. For the experiments, we fill the data structures with approximately
$10^{7}$ of keys uniformly taken from $[1,2\cdot 10^{7}]$ (each key is taken
with the probability $1/2$) and then we apply the batch of $10^{6}$ insertions
with the keys taken uniformly from $[1,2\cdot 10^{7}]$. We run data structures
on $1$ and $16$ processes and calculate their speedup. The experimental
results are presented in the following table. Each value was averaged over
$10$ runs.

| 1 proc, s | 16 proc, s | speedup
---|---|---|---
IST | 5.1s | 0.36s | 14.1
Treap | 7.5s | 0.5s | 14.9
std::set | 3.6s | — | —

As one can see, our data structure outperforms std::set on 16 processes and
outperforms parallel batched Treap on both settings, however, it has a little
bit worse speedup.

##  7\. Conclusion

In this short paper, we presented a new parallel batched data structure based
on the sequential IST (Mehlhorn and Tsakalidis, 1993). It appears to perform
better than parallel batched Treap presented in (Blelloch et al., 2016). In
the future, we want to run more experiments on the trees of different sizes
with different types of operations and on different machines with more cores.

## References

  * (1)
  * ope ([n.d.]) [n.d.].  OpenCilk.  https://github.com/OpenCilk
  * Acar et al. (2019) Umut A Acar, Vitaly Aksenov, Arthur Charguéraud, and Mike Rainey. 2019.  Provably and practically efficient granularity control. In _Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming_. 214–228.
  * Akhremtsev and Sanders (2016) Yaroslav Akhremtsev and Peter Sanders. 2016.  Fast parallel operations on search trees. In _2016 IEEE 23rd International Conference on High Performance Computing (HiPC)_. IEEE, 291–300.
  * Blelloch et al. (2016) Guy E Blelloch, Daniel Ferizovic, and Yihan Sun. 2016\.  Just join for parallel ordered sets. In _Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures_. 253–264.
  * Blelloch and Reid-Miller (1998) Guy E Blelloch and Margaret Reid-Miller. 1998.  Fast set operations using treaps. In _Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures_. 16–26.
  * Google ([n.d.]) Google. [n.d.].  tcmalloc.  https://github.com/google/tcmalloc
  * Mehlhorn and Tsakalidis (1993) Kurt Mehlhorn and Athanasios Tsakalidis. 1993.  Dynamic interpolation search.  _Journal of the ACM (JACM)_ 40, 3 (1993), 621–634.
  * Park and Park (2001) Heejin Park and Kunsoo Park. 2001.  Parallel algorithms for red–black trees.  _Theoretical Computer Science_ 262, 1-2 (2001), 415–435.
  * Paul et al. (1983) Wolfgang Paul, Uzi Vishkin, and Hubert Wagener. 1983\.  Parallel dictionaries on 2–3 trees. In _International Colloquium on Automata, Languages, and Programming_. Springer, 597–609.


# Spectral gap and curvature of monotone Markov chains

Justin Salez111CEREMADE, CNRS, UMR 7534, Université Paris-Dauphine, PSL
University, 75016 Paris, France

###### Abstract

We prove that the absolute spectral gap of any monotone Markov chain coincides
with its optimal Ollivier-Ricci curvature, where the word _optimal_ refers to
the choice of the underlying metric. Moreover, we provide a new expression in
terms of local variations of increasing functions, which has several practical
advantages over the traditional variational formulation using the Dirichlet
form. As an illustration, we explicitly determine the optimal curvature and
spectral gap of the non-conservative exclusion process with heterogeneous
reservoir densities on any network, despite the lack of reversibility.

##  1 Introduction

#### Spectral gap.

Throughout the paper, we fix an irreducible stochastic matrix $P$ on a finite
state space $\mathcal{X}$. Among the various parameters that are traditionally
used to quantify the mixing properties of $P$, the most basic one is arguably
the (absolute) _spectral gap_

$\displaystyle\gamma_{\star}$ $\displaystyle=$ $\displaystyle
1-\max\left\\{|\lambda|\colon\lambda\textrm{ is a non-trivial eigenvalue of
}P\right\\},$

where _non-trivial_ means that constant eigenfunctions are excluded. This
quantity classically captures the rate of convergence to equilibrium of the
chain, in the sense that

$\displaystyle\left(d_{\textsc{tv}}(t)\right)^{1/t}$
$\displaystyle\xrightarrow[t\to\infty]{}$ $\displaystyle 1-\gamma_{\star},$

where $d_{\textsc{tv}}(t)$ denotes the worst-case total-variation distance to
stationarity at time $t$. Under the usual assumption that $P$ is lazy and
reversible, the spectral gap coincides with the Poincaré constant and hence
provides universal controls on mixing times, concentration and isoperimetry.
We refer the unfamiliar reader to the classical textbooks [20, 23] for
details.

#### Ollivier-Ricci curvature.

Let us now assume that $\mathcal{X}$ is equipped with a metric $\rho$. When
the support of $P$ is symmetric, a canonical choice is of course the _hop-
count distance_

$\displaystyle\rho(x,y)$ $\displaystyle:=$ $\displaystyle\min\\{t\geq 0\colon
P^{t}(x,y)>0\\},$ (1)

but more sophisticated variants can prove fruitful, as we shall see. We can
then use optimal transport to ‘lift’ the metric $\rho$ to the distributional
level. Specifically, the _Wasserstein distance_ between two probability
measures $\mu$ and $\nu$ on $\mathcal{X}$ is defined as follows:

$\displaystyle\mathcal{W}\left(\mu,\nu\right)$ $\displaystyle:=$
$\displaystyle\min_{X\sim\mu,Y\sim\nu}{\mathbb{E}}\left[\rho(X,Y)\right],$

where the minimum runs over all possible couplings $(X,Y)$ of $\mu$ and $\nu$.
Minimizers always exists by compactness, and will later be referred to as
_optimal_ couplings. Following Ollivier [27, 26], we then define the
_curvature_ of $P$ to be the largest number $\kappa\in\mathbb{R}$ such that

$\displaystyle\forall\mu,\nu\in\mathcal{P}(\mathcal{X}),\qquad\mathcal{W}(\mu
P,\nu P)$ $\displaystyle\leq$ $\displaystyle(1-\kappa)\mathcal{W}(\mu,\nu).$
(2)

By Kantorovich duality, this is in fact equivalent to the functional
inequality

$\displaystyle\forall
f\in{\mathbb{C}}^{\mathcal{X}},\qquad\|Pf\|_{\textsc{lip}}$
$\displaystyle\leq$ $\displaystyle(1-\kappa)\|f\|_{\textsc{lip}},$

where $\|f\|_{\textsc{lip}}:=\max_{x\neq y}\frac{|f(x)-f(y)|}{\rho(x,y)}$
denotes the Lipschitz constant of $f$. In particular, choosing $f$ to be a
non-constant eigenfunction of $P$ readily shows that

$\displaystyle\kappa$ $\displaystyle\leq$ $\displaystyle\gamma_{\star}.$ (3)

In words, the curvature always constitutes a lower bound on the absolute
spectral gap. More importantly, this fundamental quantity has been shown to
provide an array of powerful controls in terms of geometry [15, 24], mixing
times [6, 3], expansion [30, 25], concentration of measure [17, 16, 11],
spectral independence [2] and even the cutoff phenomenon [29].

#### Optimal curvature.

An elementary but crucial observation is that the left-hand side of the
inequality (3) depends on the choice of the underlying metric $\rho$, whereas
the right-hand side does not. This asymmetry can obviously be turned to one’s
advantage, as follows: instead of blindly setting $\rho$ to the default choice
(1), one can treat it as a variable which one can try to fine-tune so as to
optimize the bound (3). Beyond the spectral gap, this strategy can be applied
to boost any estimate that uses the Ollivier-Ricci curvature as an input. It
has already led to remarkable improvements in the mixing-time analysis of
several important Markov chains, and we refer the interested reader to the
seminal papers [22, 4] for an introduction to this line of research. Motivated
by this fertile idea, we here define the _optimal curvature_ of the chain to
be the number

$\displaystyle\kappa_{\star}$ $\displaystyle:=$
$\displaystyle\sup_{\rho}\kappa(\rho),$

where $\kappa(\rho)$ denotes the curvature of $P$ with respect to the metric
$\rho$, and where the supremum runs over all possible metrics $\rho$ on
$\mathcal{X}$. While highly meaningful from a theoretical viewpoint, this
_intrinsic_ notion of curvature may seem difficult to manipulate in practice:
its definition involves three nested optimization problems that a priori
require a test over all pairs of probability measures $(\mu,\nu)$, all
couplings $(X,Y)$ of $\mu P$ and $\nu P$, and all metrics $\rho$ on
$\mathcal{X}$. However, our main discovery is that $\kappa_{\star}$ admits a
remarkably simple expression as soon as $P$ satisfies a classical and
widespread property known as _monotony_.

#### Monotone chains.

From now on, we fix a partial order $\preceq$ on our state space
$\mathcal{X}$. To avoid degeneracies, we assume that this relation is rich
enough to _connect_ $\mathcal{X}$ in the usual sense: for any states
$x,y\in\mathcal{X}$, there is a finite sequence $(x_{0},\ldots,x_{\ell})$ such
that $x_{0}=x$, $x_{\ell}=y$, and for all $1\leq i\leq\ell$, $x_{i-1}\preceq
x_{i}$ or $x_{i}\preceq x_{i-1}$. We let $\mathcal{I}$ denote the cone of
functions $f\colon\mathcal{X}\to\mathbb{R}$ which are _increasing_ , meaning
that $f(x)\leq f(y)$ whenever $x\preceq y$. Finally, we say that our matrix
$P$ is _monotone_ if its action preserves the set $\mathcal{I}$, i.e.

$\displaystyle f\in\mathcal{I}$ $\displaystyle\Longrightarrow$ $\displaystyle
Pf\in\mathcal{I}.$

By Strassen’s Theorem, this stability property is equivalent to the existence
of a _monotone Markovian coupling_ : given any pair $(x,y)\in\mathcal{X}^{2}$
with $x\preceq y$, we can jointly construct two random states $X$ and $Y$ with
respective marginal distributions $P(x,\cdot)$ and $P(y,\cdot)$ such that
${\mathbf{P}}(X\preceq Y)=1$. Such chains are ubiquitous in statistical
physics: emblematic examples include Glauber dynamics for the ferromagnetic
Ising model, lazy birth-and-death chains, the noisy voter model, or the non-
conservative exclusion process with arbitrary reservoir densities. We refer to
[20, Chapter 22] for several other examples, as well as many interesting
properties. The purpose of the present paper is to reveal a remarkable
connection between the curvature and the spectral gap of such chains.

##  2 Main result and implications

Our main contribution is the following surprising result, which asserts that
monotone chains always saturate the inequality (3): their optimal curvature
$\kappa_{\star}$ equals their spectral gap $\gamma_{\star}$. Moreover, we
provide a remarkably simple characterization of those constants in terms of
_local variations_ of increasing functions. Specifically, we introduce the
quantity

$\displaystyle\mathfrak{v}_{\star}$ $\displaystyle:=$
$\displaystyle\inf_{f\in\mathring{\mathcal{I}}}\max_{x\vartriangleleft
y}\left\\{\frac{Pf(y)-Pf(x)}{f(y)-f(x)}\right\\},$ (4)

where $\mathring{\mathcal{I}}$ denotes the set of _strictly increasing_
functions $f\colon\mathcal{X}\to\mathbb{R}$ (meaning that $f(x)<f(y)$ whenever
$x\prec y$), and where $\vartriangleleft$ denotes the usual _covering_
relation on $\mathcal{X}$:

$\displaystyle x\vartriangleleft y$ $\displaystyle\Longleftrightarrow$
$\displaystyle x\prec y\textrm{ and there is no }z\in\mathcal{X}\textrm{ such
that }x\prec z\prec y.$ (5)

######  Theorem 1 (Spectral gap and curvature of monotone chains).

If $P$ is monotone, then

$\displaystyle\kappa_{\star}$ $\displaystyle=$ $\displaystyle\gamma_{\star}\
=\ 1-\mathfrak{v}_{\star}.$

#### Discussion and perspectives.

Beyond the obvious theoretical interest of this surprising equivalence between
three fundamentally different notions (a spectral one, a geometric one, and a
variational one), we believe that the above result is of practical interest
for several reasons. An immediate one is that curvature classically provides
much more powerful controls on mixing times and on concentration than the
spectral gap does: our first equality $\kappa_{\star}=\gamma_{\star}$ shows
that those improvements come ‘for free’ in all monotone chains. Another
potentially rich source of applications lies in our second equality
$\gamma_{\star}\ =\ 1-\mathfrak{v}_{\star}$. To see why, let us recall that
the spectral gap of lazy reversible chains admits the variational
characterization

$\displaystyle\gamma_{\star}$ $\displaystyle=$
$\displaystyle\inf_{f}\left\\{\frac{\sum_{x,y\in\mathcal{X}}\pi(x)P(x,y)\left(f(y)-f(x)\right)^{2}}{\sum_{x,y\in\mathcal{X}}\pi(x)\pi(y)\left(f(y)-f(x)\right)^{2}}\right\\},$
(6)

where $\pi$ denotes the stationary law and where the infimum runs over all
non-constant test functions $f\colon\mathcal{X}\to\mathbb{R}$. Compared to
this classical formulation, our variational characterization in terms of
$\mathfrak{v}_{\star}$ offers a number of practical advantages, which we now
enumerate.

  1. 1.

It does not require reversibility, nor laziness.

  2. 2.

It involves a supremum instead of an infimum, so that any test function can be
plugged into the formula to produce a lower bound on the spectral gap.

  3. 3.

It is purely local instead of involving an average under the stationary law
$\pi$, which is sometimes very far from explicit.

  4. 4.

It is suitable for comparing very different chains: for example, we see that
$\gamma_{\star}(P)\geq\gamma_{\star}(Q)$ as soon as $Q$ is ‘more increasing’
than $P$ in the sense that $Q-P$ is monotone.

We intend to implement those ideas on concrete models in the near future. Let
us here only mention a very simple application of Theorem 1 to strictly
increasing eigenfunctions.

#### Strictly increasing eigenfunctions.

Suppose that $P$ is monotone and that it admits an eigenfunction $f$ in
$\mathring{\mathcal{I}}$, associated with some eigenvalue $\lambda$. We can
then plug $f$ into the definition of $\mathfrak{v}_{\star}$ and use our
variational characterization to deduce that $\gamma_{\star}\geq 1-\lambda$,
while the converse inequality is trivially forced by the very definition of
$\gamma_{\star}$. Thus, we can safely conclude that
$\gamma_{\star}=1-\lambda$, without having to search for other eigenfunctions
and their associated eigenvalues. Let us record this useful observation here.

######  Corollary 1 (Strictly increasing eigenfunctions).

If $P$ is monotone and if $f\in\mathring{\mathcal{I}}$ satisfies $Pf=\lambda
f$ for some $\lambda\in\mathbb{R}$, then we necessarily have
$\lambda=1-\gamma_{\star}$.

To the best of our knowledge, this result was only known to hold under the
additional assumptions that $P$ is reversible and that its support only
consists of pairs of comparable elements [20, Lemma 22.18]. An example of a
monotone chain which fails to satisfy those two additional requirements is the
non-conservative exclusion process with inhomogeneous reservoir densities. In
Section 4, we will use the above corollary to explicitly determine the
spectral gap and optimal curvature of this process on any network. Let us
first recast our main result in the setting of continuous-time Markov chains.

#### Continuous-time version.

Consider an irreducible Markov generator $L$ on the poset
$(\mathcal{X},\preceq)$, and write $(P_{t})_{t\geq 0}$ for the associated
semi-group. The spectral gap $\gamma_{\star}$ is the smallest real part of a
non-zero eigenvalue of $-L$, and the optimal curvature $\kappa_{\star}$ is
defined as before, except that the requirement (2) is replaced with its
continuous-time analogue:

$\displaystyle\forall t\geq 0,\qquad\mathcal{W}\left(\mu P_{t},\nu
P_{t}\right)$ $\displaystyle\leq$ $\displaystyle e^{-\kappa
t}\mathcal{W}(\mu,\nu).$

We naturally call the generator $L$ _monotone_ if the cone of increasing
functions $\mathcal{I}$ is preserved under the action of the semi-group. In
other words, $L$ is monotone if the stochastic matrix $P_{t}$ is monotone in
the previous sense, for each $t>0$. This allows us to apply our main theorem
to $P_{t}$ for every $t>0$. We may then send $t\to 0$ and exploit the
approximation $P_{t}=I+tL+o(t)$ to obtain the following continuous-time
version of Theorem 1 and Corollary 1.

######  Corollary 2 (Continuous-time version).

If $L$ is monotone, then

$\displaystyle\kappa_{\star}$ $\displaystyle=$ $\displaystyle\gamma_{\star}\
=\ -\inf_{f\in\mathring{\mathcal{I}}}\max_{x\vartriangleleft
y}\left\\{\frac{Lf(y)-Lf(x)}{f(y)-f(x)}\right\\}.$

In particular, if $f\in\mathring{\mathcal{I}}$ satisfies $-Lf=\lambda f$ for
some $\lambda\in\mathbb{R}$, then we necessarily have
$\lambda=\gamma_{\star}$.

##  3 Proof of the main result

We henceforth assume that $P$ is monotone, and our goal is to establish the
double identity

$\displaystyle\gamma_{\star}$ $\displaystyle=$ $\displaystyle
1-\mathfrak{v}_{\star}\ =\ \kappa_{\star}.$

Since we always have $\kappa_{\star}\leq\gamma_{\star}$, our task reduces to
the following two inequalities:

  1. (i)

$\gamma_{\star}\leq 1-\mathfrak{v}_{\star}$;

  2. (ii)

$\kappa_{\star}\geq 1-\mathfrak{v}_{\star}$.

We now prove each of those two claims separately.

###  3.1 Proof of Claim (i)

The first claim is trivial if $P$ admits an eigenfunction $f$ in
$\mathring{\mathcal{I}}$, since the latter may then be simply plugged into the
definition of $\mathfrak{v}_{\star}$. Unfortunately, not all monotone chains
admit an eigenfunction in $\mathring{\mathcal{I}}$: a simple counter-example
is the product of two chains on $\\{0,1\\}$ with different spectral gaps. Our
solution consists in considering ‘approximate eigenvectors’ in the sense of
the following lemma, which establishes Claim (i) above.

######  Lemma 1 (Proving Claim (i)).

For each $\varepsilon>0$, there is $f_{\varepsilon}\in\mathring{\mathcal{I}}$
such that

$\displaystyle\max_{x\vartriangleleft
y}\left\\{\frac{Pf_{\varepsilon}(y)-Pf_{\varepsilon}(x)}{f_{\varepsilon}(y)-f_{\varepsilon}(x)}\right\\}$
$\displaystyle\leq$ $\displaystyle 1-\gamma_{\star}+\varepsilon.$ (7)

###### Proof.

We first note that the set $\mathring{\mathcal{I}}$ is not empty. Indeed, a
strictly increasing function $f\colon\mathcal{X}\to\mathbb{R}$ can be
constructed sequentially by choosing any minimal element, assigning it a value
that is strictly larger than all previously assigned ones, removing it from
the poset and iterating. Upon replacing $f$ by $f-\pi f$ if necessary, we may
further assume that $f$ is centered under the stationary law $\pi$. Now, fix
$\varepsilon>0$ and consider the centered function

$\displaystyle f_{\varepsilon}$ $\displaystyle:=$ $\displaystyle\left({\rm
I}-\frac{P}{1-\gamma_{\star}+\varepsilon}\right)^{-1}f\ =\
\sum_{n=0}^{\infty}\left(\frac{1}{1-\gamma_{\star}+\varepsilon}\right)^{n}P^{n}f,$

whose existence is guaranteed by the fact that the restriction of $P$ to
centered functions has spectral radius $1-\gamma_{\star}$. Note that
$f_{\varepsilon}$ is strictly increasing, because each term in the above
series is increasing and the first one is strictly increasing. Moreover, we
have $Pf_{\varepsilon}=(1-\gamma_{\star}+\varepsilon)(f_{\varepsilon}-f)$ by
construction, so that for any $x\vartriangleleft y$,

$\displaystyle Pf_{\varepsilon}(y)-Pf_{\varepsilon}(x)$ $\displaystyle=$
$\displaystyle(1-\gamma_{\star}+\varepsilon)\left[\left(f_{\varepsilon}(y)-f_{\varepsilon}(x)\right)-\left(f(y)-f(x)\right)\right]$
$\displaystyle\leq$
$\displaystyle(1-\gamma_{\star}+\varepsilon)\left(f_{\varepsilon}(y)-f_{\varepsilon}(x)\right),$

as desired. ∎

###  3.2 Proof of Claim (ii)

Our proof of Claim (ii) relies on the simple observation that the curvature
$\kappa$ of a monotone chain admits a remarkably simple expression when the
underlying metric $\rho$ has a certain ‘gradient structure’, which we now
describe. Recall that the _Hasse diagram_ of the poset $(\mathcal{X},\preceq)$
is the graph $G=(\mathcal{X},E)$ whose edge-set is obtained by symmetrizing
the covering relation $\vartriangleleft$ defined at (5):

$\displaystyle E$ $\displaystyle:=$
$\displaystyle\left\\{(x,y)\in\mathcal{X}^{2}\colon x\vartriangleleft
y\textrm{ or }y\vartriangleleft x\right\\}.$

As usual, a _path_ in $G$ is a finite sequence of vertices
$\sigma=(\sigma_{0},\ldots,\sigma_{\ell})$ such that
$\\{\sigma_{i-1},\sigma_{i}\\}\in E$ for all $1\leq i\leq\ell$. The integer
$\ell\in\\{0,1,2,\ldots,\\}$ is called the length of the path, and denoted by
$|\sigma|$. We write $\Sigma_{x\to y}$ for the set of all paths starting at
$x$ and ending at $y$. Now, given any function $f\in\mathring{\mathcal{I}}$,
we define a metric $\rho$ on $\mathcal{X}$ by the following formula:

$\displaystyle\rho(x,y)$ $\displaystyle:=$
$\displaystyle\min_{\sigma\in\Sigma_{x\to
y}}\left\\{\sum_{i=1}^{|\sigma|}|f(\sigma_{i})-f(\sigma_{i-1})|\right\\}.$ (8)

On the resulting metric space $(\mathcal{X},\rho)$, the curvature of any
monotone chain is given by the following lemma, from which Claim (ii) readily
follows by taking a supremum over all $f\in\mathring{\mathcal{I}}$.

######  Lemma 2 (Proving Claim (ii)).

The curvature of $P$ with respect to the metric (8) is

$\displaystyle\kappa(\rho)$ $\displaystyle=$ $\displaystyle
1-\max_{x\vartriangleleft y}\left\\{\frac{Pf(y)-Pf(x)}{f(y)-f(x)}\right\\}.$

###### Proof.

It is clear from the definition (8) that our metric $\rho$ satisfies

$\displaystyle\rho(x,y)$ $\displaystyle\geq$ $\displaystyle f(y)-f(x),$ (9)

for all $x,y\in\mathcal{X}$. Moreover, there is equality whenever $x\preceq
y$, since the very definition of the covering relation $\vartriangleleft$ then
guarantees the existence of a path $\sigma$ from $x$ to $y$ such that
$\sigma_{i-1}\vartriangleleft\sigma_{i}$ for all $1\leq i\leq|\sigma|$. Now,
fix $x,y\in\mathcal{X}^{2}$ such that $x\vartriangleleft y$. Then, for any
coupling $(X,Y)$ of $P(x,\cdot),P(y,\cdot)$, the above observation ensures
that

$\displaystyle{\mathbb{E}}\left[\rho(X,Y)\right]$ $\displaystyle\geq$
$\displaystyle{\mathbb{E}}\left[f(Y)-f(X)\right]\ =\ Pf(y)-Pf(x),$ (10)

with equality as soon as ${\mathbf{P}}(X\preceq Y)=1$. But our monotony
assumption on $P$ precisely guarantees the existence of such a monotone
coupling. Thus, we obtain the two identities

$\displaystyle{\mathcal{W}\left(P(x,\cdot),P(y,\cdot)\right)}$
$\displaystyle=$ $\displaystyle Pf(y)-Pf(x),$ $\displaystyle\rho(x,y)$
$\displaystyle=$ $\displaystyle f(y)-f(x),$

whenever $x\vartriangleleft y$. This already shows that
$\mathfrak{v}:=\max_{x\vartriangleleft
y}\left\\{\frac{Pf(y)-Pf(x)}{f(y)-f(x)}\right\\}$ is the smallest number such
that the inequality

$\displaystyle{\mathcal{W}\left(P(x,\cdot),P(y,\cdot)\right)}\leq\mathfrak{v}\,\rho(x,y).$
(11)

holds whenever $\\{x,y\\}\in E$. Now, observe that this last inequality
automatically extends to arbitrary points $x,y\in\mathcal{X}$, since we can
apply it to all edges along a _geodesic_ path from $x$ to $y$ (i.e., a path
achieving the minimum in the definition of $\rho(x,y)$) and then invoke the
triangle inequality for $\mathcal{W}\left(\cdot,\cdot\right)$ to conclude.
Finally, given $\mu,\nu\in\mathcal{P}(\mathcal{X})$, we can construct a
coupling $(X^{\prime},Y^{\prime})$ of $\mu P$ and $\nu P$ in two steps as
follows:

  1. 1.

Generate $(X,Y)$ according to an optimal coupling of $\mu$ and $\nu$.

  2. 2.

For each possible realization $(x,y)\in\mathcal{X}^{2}$, conditionally on the
event $\left\\{(X,Y)=(x,y)\right\\}$, let $(X^{\prime},Y^{\prime})$ be
distributed as an optimal coupling of $P(x,\cdot)$ and $P(y,\cdot)$.

The resulting pair $(X^{\prime},Y^{\prime})$ is clearly a coupling of $\mu P$
and $\nu P$ and therefore,

$\displaystyle\mathcal{W}(\mu P,\nu P)$ $\displaystyle\leq$
$\displaystyle{\mathbb{E}}\left[\rho(X^{\prime},Y^{\prime})\right]$
$\displaystyle=$
$\displaystyle\sum_{x,y\in\mathcal{X}}{\mathbf{P}}\left((X,Y)=(x,y)\right)\mathcal{W}\left(P(x,\cdot),P(y,\cdot)\right)$
$\displaystyle\leq$
$\displaystyle\mathfrak{v}\sum_{x,y\in\mathcal{X}}{\mathbf{P}}\left((X,Y)=(x,y)\right)\rho(x,y)$
$\displaystyle=$ $\displaystyle\mathfrak{v}{\mathbb{E}}\left[\rho(X,Y)\right]$
$\displaystyle=$ $\displaystyle\mathfrak{v}\mathcal{W}(\mu,\nu),$

where the middle inequality is simply (11). Since this is true for all
$\mu,\nu\in\mathcal{P}(\mathcal{X})$, we may safely conclude from this
computation that $1-\mathfrak{v}\leq\kappa(\rho)$, and the optimality of
$\mathfrak{v}$ in (11) shows that this is in fact an equality, as desired. ∎

##  4 Application to the exclusion process

The exclusion process is a classical model of interacting random walks in
which indistinguishable particles attempt to evolve independently on a graph,
except that their jumps are canceled if the destination is already occupied
[32, 21]. Here we consider the non-conservative variant of the model, where
particles may additionally be created and annihilated at certain vertices,
modeling contact with external reservoirs. We refer the reader to the seminal
works [1, 19] or the more recent papers [12, 13, 31, 33] for background and
motivation. The model is parametrized by an integer $n\in\mathbb{N}$
representing the number of sites, a non-negative symmetric array
$(c_{ij})_{1\leq i,j\leq n}$ specifying the exchange rates, and two non-
negative vectors $(r^{+}_{i})_{1\leq i\leq n}$ and $(r^{-}_{i})_{1\leq i\leq
n}$ describing the creation and annihilation rates. The exclusion process with
those parameters is the continuous-time Markov chain with state space
$\mathcal{X}=\\{0,1\\}^{n}$ and whose infinitesimal generator $L$ acts on any
$f\colon\mathcal{X}\to\mathbb{R}$ as follows:

$\displaystyle(Lf)(x)$ $\displaystyle:=$
$\displaystyle\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}\left[f(x^{i\leftrightarrow
j})-f(x)\right]$
$\displaystyle+\sum_{i=1}^{n}r^{+}_{i}\left[f(x^{i,1})-f(x)\right]$
$\displaystyle+\sum_{i=1}^{n}r^{-}_{i}\left[f(x^{i,0})-f(x)\right],$

where $x^{i\leftrightarrow j}$, $x^{i,1}$ and $x^{i,0}$ naturally denote the
vectors obtained from $x$ by respectively swapping the $i-$th and $j-$th
coordinates (exchange), resetting the $i-$th coordinate to $1$ (creation), and
resetting it to $0$ (annihilation). To ensure irreducibility, we henceforth
assume that the support of the matrix $c$ connects the sites, and that the
supports of $r^{+}$ and $r^{-}$ are not empty.

A simple object that plays an important role in the analysis of the above
process is the _Laplace matrix_ $\Delta=(\Delta_{ij})_{1\leq i,j\leq n}$ of
the underlying network, defined as follows:

$\displaystyle\Delta_{ij}$ $\displaystyle:=$
$\displaystyle\left\\{\begin{array}[]{ll}c_{ij}&\textrm{if }j\neq i\\\
-r^{+}_{i}-r^{-}_{i}-\sum_{k\in[n]\setminus\\{i\\}}c_{ik}&\textrm{if
}j=i.\end{array}\right.$

This symmetric negative definite matrix describes the evolution of a single
random walker moving across the $n$ sites according to the conductances
$(c_{ij})_{1\leq i,j\leq n}$ and killed at the space-varying rates
$(r^{+}_{i}+r^{-}_{i})_{1\leq i\leq n}$. Our Theorem 2 below shows that the
mixing properties of the $2^{n}\times 2^{n}$ generator $L$ are essentially
dicated by those of the $n\times n$ matrix $\Delta$. This remarkable
‘dimensionality reduction’ constitutes a non-conservative extension of Aldous’
celebrated _spectral gap conjecture_ , now proved by Caputo, Liggett and
Richthammer [10]. Interestingly, a similar phenomenon has recently been
established in several other interacting particle models [7, 14, 8, 9, 28, 5,
18]. However, to the best of our knowledge, its validity for the exclusion
process was only known to hold in the reversible case where the vector
$\kappa^{+}+\kappa^{-}$ is constant [31].

######  Theorem 2 (Dimensionality reduction).

The spectral gap and optimal curvature of the generator $L$ coincide with the
smallest eigenvalue of the matrix $-\Delta$.

###### Proof.

Let $\lambda>0$ be the smallest eigenvalue of the definite positive matrix
$-\Delta$. By Perron’s theorem and our irreducibility assumption, there is a
corresponding eigenvector $v=(v_{i})_{1\leq i\leq n}$ whose entries are all
positive. Set $p:=(-\Delta)^{-1}r^{+}$, and consider the function
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ defined by

$\displaystyle f(x)$ $\displaystyle:=$ $\displaystyle\langle v,x-p\rangle\ =\
\sum_{i=1}^{n}v_{i}(x_{i}-p_{i}).$

We claim that $f$ is an eigenfunction of $L$ corresponding to the eigenvalue
$-\lambda$. Indeed, using the definition of $L$, we find

$\displaystyle(Lf)(x)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}v_{i}\left[\sum_{j=1}^{n}c_{ij}(x_{j}-x_{i})+r^{+}_{i}(1-x_{i})-r^{-}_{i}x_{i}\right]$
$\displaystyle=$ $\displaystyle\langle v,\Delta x+r^{+}\rangle$
$\displaystyle=$ $\displaystyle\langle v,\Delta(x-p)\rangle$ $\displaystyle=$
$\displaystyle\langle\Delta v,x-p\rangle$ $\displaystyle=$
$\displaystyle-\lambda f(x),$

where we have successively used the identity $r^{+}=-\Delta p$, the symmetry
of $\Delta$ and the identity $\Delta v=-\lambda v$. Now, the positivity of $v$
ensures that the eigenfunction $f$ is strictly increasing with respect to the
usual coordinate-wise order $\preceq$ on $\\{0,1\\}^{n}$. Moreover, this order
is clearly preserved under each possible transition $x\mapsto
x^{i\leftrightarrow j}$, $x\mapsto x^{i,1}$ and $x\mapsto x^{i,0}$, and hence
also under the ‘obvious’ coupling that consists in performing those
transitions at the same random times in both trajectories. Thus, $L$ is
monotone and we may invoke Corollary 2 to conclude that
$\gamma_{\star}=-\lambda$, as desired. ∎

#### Acknowledgment.

The author warmly thanks Pietro Caputo for suggesting several interesting
possible applications, which will be investigated in the near future. This
work was partially supported by Institut Universitaire de France.

## References

  * [1] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, and C. Landim.  Large deviations for the boundary driven symmetric simple exclusion process.  Math. Phys. Anal. Geom., 6(3):231–267, 2003.
  * [2] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda.  On mixing of Markov chains: coupling, spectral independence, and entropy factorization.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022.
  * [3] Magnus Bordewich and Martin Dyer.  Path coupling without contraction.  J. Discrete Algorithms, 5(2):280–292, 2007.
  * [4] Magnus Bordewich, Martin E. Dyer, and Marek Karpinski.  Metric construction, stopping times and path coupling.  Electron. Colloquium Comput. Complex., TR05, 2005.
  * [5] Alexandre Bristiel and Pietro Caputo.  Entropy inequalities for random walks and permutations, 2021.
  * [6] R. Bubley and M. Dyer.  Path coupling: A technique for proving rapid mixing in markov chains.  In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 223–231, 1997.
  * [7] Pietro Caputo.  On the spectral gap of the Kac walk and other binary collision processes.  ALEA Lat. Am. J. Probab. Math. Stat., 4:205–222, 2008.
  * [8] Pietro Caputo, Cyril Labbé, and Hubert Lacoin.  Mixing time of the adjacent walk on the simplex.  Ann. Probab., 48(5):2449–2493, 2020.
  * [9] Pietro Caputo, Cyril Labbé, and Hubert Lacoin.  Spectral gap and cutoff phenomenon for the gibbs sampler of $\nabla\varphi$ interfaces with convex potential, 2020.
  * [10] Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer.  Proof of Aldous’ spectral gap conjecture.  J. Amer. Math. Soc., 23(3):831–851, 2010.
  * [11] Ronen Eldan, James R Lee, and Joseph Lehec.  Transport-entropy inequalities and curvature in discrete-space Markov chains.  In A Journey Through Discrete Mathematics, pages 391–406. Springer, 2017.
  * [12] Nina Gantert, Evita Nestoridi, and Dominik Schmid.  Mixing times for the simple exclusion process with open boundaries, 2021\.
  * [13] Patrícia Gonçalves, Milton Jara, Rodrigo Marinho, and Otávio Menezes.  Sharp convergence to equilibrium for the ssep with reservoirs, 2021.
  * [14] Jonathan Hermon and Justin Salez.  A version of Aldous’ spectral-gap conjecture for the zero range process.  Ann. Appl. Probab., 29(4):2217–2229, 2019.
  * [15] Jürgen Jost, Florentin Münch, and Christian Rose.  Liouville property and non-negative Ollivier curvature on graphs.  arXiv preprint arXiv:1903.10796, 2019.
  * [16] Aldéric Joulin.  Poisson-type deviation inequalities for curved continuous-time Markov chains.  Bernoulli, 13(3):782–798, 2007.
  * [17] Aldéric Joulin and Yann Ollivier.  Curvature, concentration and error estimates for Markov chain Monte Carlo.  Ann. Probab., 38(6):2418–2442, 2010.
  * [18] Seonwoo Kim and Federico Sau.  Spectral gap of the symmetric inclusion process, 2023.
  * [19] C. Landim, A. Milanés, and S. Olla.  Stationary and nonequilibrium fluctuations in boundary driven exclusion processes.  Markov Process. Related Fields, 14(2):165–184, 2008.
  * [20] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, 2017.  Second edition of [ MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [21] Thomas M. Liggett.  Interacting particle systems.  Classics in Mathematics. Springer-Verlag, Berlin, 2005.  Reprint of the 1985 original.
  * [22] Michael Luby and Eric Vigoda.  Fast convergence of the Glauber dynamics for sampling independent sets.  volume 15, pages 229–241. 1999.  Statistical physics methods in discrete probability, combinatorics, and theoretical computer science (Princeton, NJ, 1997).
  * [23] Ravi Montenegro and Prasad Tetali.  Mathematical aspects of mixing times in Markov chains.  Found. Trends Theor. Comput. Sci., 1(3):x+121, 2006.
  * [24] Florentin Münch.  Non-negative Ollivier curvature on graphs, reverse Poincaré inequality, Buser inequality, Liouville property, Harnack inequality and eigenvalue estimates.  arXiv preprint arXiv:1907.13514, 2019.
  * [25] Florentin Münch and Justin Salez.  Mixing time and expansion of non-negatively curved markov chains.  Journal de l’École polytechnique — Mathématiques, 10:575–590, mar 2023.
  * [26] Yann Ollivier.  A survey of Ricci curvature for metric spaces and Markov chains, volume 57 of Adv. Stud. Pure Math. Math. Soc. Japan, Tokyo.
  * [27] Yann Ollivier.  Ricci curvature of Markov chains on metric spaces.  Journal of Functional Analysis, 256(3):810–864, 2009.
  * [28] Matteo Quattropani and Federico Sau.  Mixing of the averaging process and its discrete dual on finite-dimensional geometries, 2021.
  * [29] Justin Salez.  Cutoff for non-negatively curved Markov chains.  arXiv preprint arXiv:2102.05597, 2021.
  * [30] Justin Salez.  Sparse expanders have negative curvature.  Geom. Funct. Anal., 32(6):1486–1513, 2022.
  * [31] Justin Salez.  Universality of cutoff for exclusion with reservoirs.  Ann. Probab., 51(2):478–494, 2023.
  * [32] Frank Spitzer.  Interaction of Markov processes.  Advances in Math., 5:246–290 (1970), 1970.
  * [33] Hong-Quan Tran.  Cutoff for the non reversible ssep with reservoirs, 2022.