A non-oriented first passage percolation model and statistical invariance by time reversal

We present a non-oriented first passage percolation (FPP) model satisfying a statistical invariance property by time reversal. This property is analogous to the statistical invariance property satisfied by the random walk in Dirichlet random environment [4].

Random walk in random environment (or RWRE, for short) is a challenging model for which several fundamental questions remain open, including the proof of a law of large numbers [6, 2]. In particular, in the multidimensional case, very few explicit computations can be made, so that for example, there are no general formulas for the velocity, asymptotic direction, the diffusion matrix in the case of Gaussian fluctuations, or the large deviation rate functions. The random walk in Dirichlet environment (RWDE) is a particular case of RWRE in which the marginal law of the environment at each site is given by a Dirichlet distribution [4]. Sabot proved in [3] that RWDE satisfies a property of satistical invariance by time reversal. This was used in several works (see [4]), to prove fundamental properties of this model, including explicit conditions for transient-recurrent behavior in dimension $d=3$ [3] and an explicit formula for the asymptotic direction in [5]. Also, a particular case of the RWDE model corresponding to parameters which allow only oriented (or directed) movements of the random walk, called the Beta random walk, was studied by Barraquand and Corwin in [1], where they were able to proved Tracy–Widom GUE fluctuations of the quenched large deviation principle, thus establishing the belonging of this model to the KPZ universality class. Furthermore, the zero-temperature limit of the Beta random walk, which is a first passage percolation model called Exponential first passage percolation, was also studied in [1], where they showed that the fluctuations of the first passage times are also of the Tracy–Widom GUE type.

In this article we introduce a zero-temperature version of general RWDE, which we call the Bernoulli–Exponential first passage percolation model, which turns out to be a non-oriented extension of the exponential first passage percolation model from [1]. The main result of this article is the proof of a zero-temperature version of the statistical reversibility under time reversal property of this model. To our knowledge, this is the first model of FPP type satisfying such a property.

In principle, the definition of the Bernoulli–Exponential first passage percolation model can be understood following the principles of tropical geometry: starting from RWDE, addition is replaced with minimization and multiplication with addition. However, due to the presence of infinite sums in the probabilities involved in the RWDE, this correspondence cannot be made rigorous, and so in the end here the Bernoulli–Exponential first passage percolation model is defined and studied directly, without any specific reference to the RWDE. An exception to this is the proof of the statistical invariance property under time reversal for the Bernoulli–Exponential first passage percolation model, which is derived through a limiting procedure from the RWDE.

In what follows, in Section 2, we give a precise statement of the main results of the article. In Section 3, we derive the Bernoulli–Exponential first passage exponential model as a zero-temperature limit of the RWDE. In Section 4, we present a proof of the statistical invariance by time reversal of the model. Finally in Section 5, we apply the statistical invariance by time reversal property to compute some first passage times in specific graphs.

In order to define this model, we need to introduce first a multinomial version of the Bernoulli–Exponential random variable. To this end, let us recall the generalized Bernoulli distribution: given $M\in\mathbb{N}$ and a probability vector $\mathbf{p}=(p_{1},\dots,p_{M})\in\mathbb{R}^{M}$, we say that a random vector $B=(B_{1},\dots,B_{M})$ has generalized Bernoulli distribution of order $M$ with parameters $\mathbf{p}$, and denote it by $B\sim\textrm{Be}_{M}(\mathbf{p})$, if it satisfies

where $\mathrm{e}_{i}$ denotes the $i$-th canonical vector in $\mathbb{R}^{M}$. We next define the Bernoulli–Exponential distribution of order $M$.

With Definition 2.1 at our disposal, we now define the generalized Bernoulli–Exponential first passage percolation model as follows. Let $G=(V,\mathcal{E})$ be a directed graph endowed with a family of positive weights $\mathbf{a}:=(a_{e})_{e\in\mathcal{E}}$. Assume that $G$ is finite and strongly connected, i.e., that for any $x,y\in V$ there exists a path going from $x$ to $y$, where by path we understand a finite vector $\pi=(x_{0},\ldots,x_{n})$ with $x_{0},\ldots,x_{n}\in V$ and $(x_{i},x_{i+1})\in\mathcal{E}$ for all $0\leq i\leq n-1$. For each $x\in V$, define $\mathcal{E}_{x}:=\{e\in\mathcal{E}:e=(x,y)\text{ for some }y\in V\}$ to be the set of edges in $\mathcal{E}$ leaving $x$ and write $M_{x}:=\#\mathcal{E}_{c}$ for their total number. Now consider a family $\omega=(\omega(x))_{x\in V}$ of independent random vectors where, for each $x\in V$, the vector $\omega(x)=(\omega(x,e))_{e\in\mathcal{E}_{x}}$ has generalized Bernolli–Exponential distribution of order $M_{x}$ with parameters $\mathbf{a}_{x}:=(a_{e})_{e\in\mathcal{E}_{x}}$. We will call the family $\omega$ a generalized Bernoulli–Exponential environment on the graph $G$ with parameters $\mathbf{a}$, and denote its law by $\mathbb{P}_{\text{BE}}^{(\mathbf{a})}$. Finally, we denote by $\Pi(x,y)$ the set of paths going from $x$ to $y$. Now, we define the first passage time between two points $x,y\in G$ by

where $\Delta x_{i}:=(x_{i},x_{i+1})$. We will call $(T(x,y))_{x,y\in V}$ the generalized Bernoulli-Exponential first passage percolation model on $G$.

In order to state our main result, we first need to introduce the dual graph of $G=(V,\mathcal{E})$, which is defined as $\check{G}:=(V,\check{\mathcal{E}})$, where

is the set of reversed edges of $\mathcal{E}$. In the following, we will write $\check{e}=(y,x)$ for the reversal of the edge $e=(x,y)$. We endow $\check{G}$ with the family of reversed weights $\check{\mathbf{a}}:=(\check{a}_{\check{e}})_{\check{e}\in\check{\mathcal{E}}}$, where

Furthermore, define the divergence operator on the graph $G$ as the function $\text{div}:{\mathbb{R}}^{\mathcal{E}}\to{\mathbb{R}}^{V}$ given by

where $\mathcal{E}^{x}:=\{e\in\mathcal{E}:e=(y,x)\text{ for some }y\in V\}$ is the set of edges in $\mathcal{E}$ arriving at $x$. Finally, we shall say that a function $f:\mathcal{E}\to\mathbb{R}$ satisfies the closed loop property if for every path $\pi=(x_{0},\ldots,x_{n})$ which is closed, i.e., which satisfies $x_{n}=x_{0}$, we have that

Our main result is then the following.

In Section 5, we will see how we can use Theorem 2.2 to compute certain passage times.

To establish Theorem 2.2, an important step will be to show that the Bernoulli–Exponential distribution can be obtained as the weak limit of (suitably rescaled) Dirichlet random vectors. For convenience of the reader, we recall the definition of the Dirichlet distribution next.

The main result of this section is the following proposition.

To prove Proposition 3.3, we will need two auxiliary results. The first is a standard property of Dirichlet random vectors, contained in Proposition 3.4 below, whose proof is omitted.

The second auxiliary result gives two key properties of the Bernoulli–Exponential law.

We are now ready to prove Proposition 3.3.

We will now use Proposition 3.3 together with the property of statistical reversibility of random walks in Dirichlet environments to prove our Theorem 2.2. We begin by recalling the model of random walks in Dirichlet environments.

Given a strongly connected finite directed graph $G=(V,\mathcal{E})$, for each $x\in V$ let

be the space of all probability vectors on $\mathcal{E}_{x}$ and consider the product space $\Omega:=\prod_{x\in V}\mathcal{P}_{x}$ endowed with the usual product topology. Any element $\omega\in\Omega$ will be called an environment, i.e., each $\omega=(\omega(x))_{x\in V}$ is a finite family of probability vectors $\omega(x)=(\omega(x,e))_{e\in\mathcal{E}_{x}}\in\mathcal{P}_{x}$. Given any $z\in V$ and $\omega\in\Omega$, we define the random walk in the environment $\omega$ starting at $z$ as the Markov chain $(X_{n})_{n\in\mathbb{N}_{0}}$ on $G$ whose law $P_{z,\omega}$ is given by

for all $x,y\in V$ such that $(x,y)\in\mathcal{E}$. If we now let the environment $\omega$ be chosen at random according to some Borel probability measure $\mathbb{P}$ on $\Omega$, we obtain the measure $P_{x}$ on $\Omega\times V^{\mathbb{N}_{0}}$ given by

for all Borel sets $A\subseteq\Omega$ and $B\subseteq V^{\mathbb{N}_{0}}$. The process $(X_{n})_{n\in\mathbb{N}_{0}}$ under the measure $P_{z}$ is called the random walk in random environment (RWRE) with environmental law $\mathbb{P}$ (starting at $z$). The measure $P_{z}$ is known as the annealed law of the RWRE, whereas $P_{z,\omega}$ for a fixed $\omega\in\Omega$ is referred to as the quenched law. Finally, if given a family of positive weights $\mathbf{a}=(a_{e})_{e\in\mathcal{E}}$ we consider the environmental law

where, as before, we write $\mathbf{a}_{x}:=(a_{e})_{e\in\mathcal{E}_{x}}$, then the resulting RWRE is called a random walk in a Dirichlet environment (RWDE) with parameters $\mathbf{a}$.

Now let us fix a family of positive weights $\mathbf{a}=(a_{e})_{e\in\mathcal{E}}$ on $\mathcal{E}$ and, for each $\varepsilon>0$, consider a Dirichlet random environment $\omega_{\varepsilon}$ on $G$ with parameter $\varepsilon\mathbf{a}$, i.e., a family of independent random vectors $\omega_{\varepsilon}=(\omega_{\varepsilon}(x))_{x\in V}$ where, for each $x\in V$, the vector $\omega_{\varepsilon}(x)=(\omega_{\varepsilon}(x,e))_{e\in\mathcal{E}_{x}}$ has Dirichlet distribution of order $M_{x}$ with parameters $\varepsilon\mathbf{a}_{x}:=(\varepsilon a_{e})_{e\in\mathcal{E}_{x}}$. Then, since $\varepsilon a_{e}>0$ for every $e\in\mathcal{E}$ and $G$ is strongly connected, for $\mathbb{P}^{(\varepsilon\mathbf{a})}$-almost every $\omega_{\varepsilon}$ the associated walk $(X_{n})_{n\in\mathbb{N}_{0}}$ is an irreducible finite-state Markov chain under $P_{z,\omega}$ and, as such, admits a unique stationary distribution $\pi^{\omega_{\varepsilon}}=(\pi^{\omega_{\varepsilon}}(x))_{x\in V}$. Following [4], we can now define the time-reversed environment $\check{\omega}_{\varepsilon}$ in the dual graph $\check{G}$ by

Since $\textrm{div}(\mathbf{a})=0$, it follows from [4, Lemma 3] that $\check{\omega}_{\varepsilon}$ is a Dirichlet random environment on the dual graph $\check{G}$ with parameters $\varepsilon\check{\mathbf{a}}$, for $\check{\mathbf{a}}$ as defined in (4).

If for each $e=(x,y)\in\mathcal{E}$ we define the quantities

then (12) gives

where

Finally, consider the random vector

It follows from Proposition 3.3 and (13) that the family $(\Upsilon_{\varepsilon})_{\varepsilon>0}$ is tight as $\varepsilon\to 0$, as shown in the following lemma.

As a consequence of Lemma 4.1 we obtain that there exists some subsequence $(\varepsilon_{n})_{n\in\mathbb{N}}$ such that $\lim_{n\to\infty}\varepsilon_{n}=0$ and a random vector $\Upsilon=(\Upsilon^{(1)}(x,e),\Upsilon^{(2)}(y,\check{e}),\Upsilon^{(3)}(e))_{e=(x,y)\in\mathcal{E}}$ satisfying that as $n\to\infty$,

We claim that $\Upsilon$ is the desired coupling. Indeed, by Proposition 3.3 we have that $\Upsilon^{(1)}\sim\mathbb{P}^{(\mathbf{a})}_{\text{BE}}$ and $\Upsilon^{(2)}\sim\mathbb{P}^{(\check{\mathbf{a}})}_{\text{BE}}$. On the other hand, (13) and (14) together imply that

for all $e=(x,y)\in\mathcal{E}$. Finally, if $\pi=(x_{0},x_{1},\dots,x_{n-1},x_{n})$ is a closed path, then given $\varepsilon>0$ since $x_{n}=x_{0}$ we have that

so that by (13) the vector $(\upsilon_{\varepsilon}(e))_{e\in\mathcal{E}}$ satisfies the closed loop property. It then follows from (14) that $(\Upsilon^{(3)}(e))_{e\in\mathcal{E}}$ must satisfy the closed loop property as well. Therefore, we see that $\Upsilon$ satisfies all the required properties and thus constitutes the desired coupling. This concludes the proof of Theorem 2.2.

We conclude by giving an example of how Theorem 2.2 can be used to do explicit computations of non-trivial first passage times.

Consider the finite graph $G$ of Figure 1. The vertices are classified into seven layers, plus an extra vertex which we call $y$. The super-index $i$ in a vertex $x_{k}^{i}$ indicates to which layer it belongs, e.g. $x^{i}_{k}$ is the $k$-th vertex of the $i$-th layer. Let us fix three parameters $a_{1},a_{2},a_{3}>0$. We give the weight $a_{1}+a_{2}+a_{3}$ to the edge from $x^{1}_{1}$ to any vertex in layer $2$. From layer $2$ to $3$ we give, for each $1\leq k,j\leq 3$, the weight $a_{j}$ to the edge connecting $x^{2}_{k}$ to $x^{3}_{j}$. In general, given $j\in\{1,2,3\}$, for $2\leq i\leq 6$ we give the weight $a_{j}$ to any outgoing edge from a vertex $x^{i}_{k}$ in layer $i$ to the $j$-th vertex $x^{i+1}_{j}$ in layer $i+1$. Every outgoing edge from layer $7$ to $x^{1}_{1}$ or $y$ is assigned the weight $(a_{1}+a_{2}+a_{3})/2$. The edge from $y$ to $x^{1}_{1}$ has weight $a_{1}+a_{2}+a_{3}$, while the edge from $x_{1}^{1}$ to $y$ has weight $(a_{1}+a_{2}+a_{3})/2$. The weights indicated in the edges of graph $G$ define a generalized Bernoulli–Exponential first passage percolation model with those weights. Notice that the divergence condition $\text{div}({\bf a})=0$ is satisfied, where $\mathbf{a}$ denotes the vector of all such edge weights.

Define now the passage time,

where $\Pi_{c}$ is the set of paths which exit $x^{1}_{1}$ through the right in Figure 1 (first jump is through any of the edges from $x^{1}_{1}$ to layer $2$) and finish entering again $x^{1}_{1}$ through layer $7$ or vertex $y$. By the statistical reversibility of Theorem 2.2, we have that

where $\check{\Pi}_{c}$ is the set of paths in the dual graph $\check{G}$ which exit $x^{1}_{1}$ with a first jump through any of the edges from $x^{1}_{1}$ to layer $7$ or vertex $y$, and finish entering again $x^{1}_{1}$ through layer $2$. But now note that for the reversed process there is always a path of $0$ weight from any vertex in layer $7$ to the vertex $x^{1}_{1}$. Hence the minimum in the right-hand side of (15) is just the minimum of the passage time in the dual graph $\check{G}$ from $x^{1}_{1}$ to layer $7$ (without revisiting $x^{1}_{1}$), which can be immediately computed and gives