Speed function for biased random walks with traps

Biased random walks on random graphs have been popular objects of study in recent years. The most relevant effect is that the random walk can run into traps, i. e. portions of the random graph that can only be exited by making a large number of steps in the direction opposite to the drift, which can take a long time. This leads to a decrease of the speed of the ballistic motion that is typical for a biased random in the absence of traps. Explicitly, if we embed the random graph into $\mathbb{R}^{d}$ and define the ballistic speed of the walk $(X_{t})_{t\geq 0}$ as $\overline{\mathrm{v}}=\lim_{t\to\infty}\frac{1}{t}X_{t}$ (provided the limit exists almost surely), then in many models $\overline{\mathrm{v}}$ (or rather its projection in the direction of the bias) is not a monotone function of the bias, and often equals zero beyond a critical value of the bias. The latter behaviour is known to hold for the biased walk on the infinite connected cluster of supercritical bond percolation on $\mathbb{Z}^{d}$, $d\geq 2$ [4, 8, 13], on the Galton-Watson tree with leaves [1, 6, 12] and on certain one-dimenisional percolation models [2, 10]. We refer to the lecture notes [3] and the introduction of [10] for further details on the models and relations to physical models.

The purpose of this note is to derive an explicit formula for the speed in a class of toy models that includes the biased Bouchaud’s trap model on the integers. In these models, a random walk $(Y_{n})_{n\in\mathbb{N}_{0}}$ runs on $\mathbb{Z}$, and the geometry of the random graph is replaced by a family of random average holding times. Explicitly, a random average holding time $w_{x}$ is sampled for each $x\in\mathbb{Z}$, and when the biased random walk hits the point $x$ at time $k$, it waits for a random time $\tau_{w_{x},x,k}$, mimicking the time it takes to leave a trap with entrance at $x$. The stochastic processes $(\tau_{r,x,k})_{r\geq 0}$, $x\in\mathbb{Z}$, $k\in\mathbb{N}_{0}$ are i. i. d. (independent and identically distributed) and $\tau_{r,x,k}$ has mean $r$, but the $w_{x}$, $x\in\mathbb{Z}$ are not re-sampled during the dynamics, and thus the waiting times $\tau_{w_{Y_{k}},Y_{k},k}$, $k\in\mathbb{N}_{0}$ are not independent. This means that a trivial application of the law of large numbers to compute the average waiting time per site, $\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}\tau_{w_{Y_{k}},Y_{k},k}$, is not possible. Under the assumption that $(w_{x})_{x\in\mathbb{Z}}$ is an ergodic family, we will show that the law of large numbers nevertheless holds, and derive an explicit expression for $\overline{\mathrm{v}}$ in terms of the waiting time distributions. We illustrate our results with several examples that also demonstrate how close our toy model is to various models of biased walks on random graphs.

For $\lambda>0$, let $\xi,\xi_{1},\xi_{2},\ldots$ be a sequence of i. i. d. random variables, with

We define $Y_{n}\vcentcolon=\sum_{k=1}^{n}\xi_{k}$ for $n\in\mathbb{N}_{0}=\{0,1,2,\ldots\}$. The process $(Y_{n})_{n\in\mathbb{N}_{0}}$ is a biased nearest-neighbor random walk on $\mathbb{Z}$ starting at $0$.

Let $(w_{x})_{x\in\mathbb{Z}}$ be an ergodic sequence of positive random variables, modeling the average waiting times at the points $x\in\mathbb{Z}$. Let $((\tau_{r,x,k})_{r\geq 0})_{x\in\mathbb{Z},k\in\mathbb{N}_{0}}$ be a family of independent random processes with $\mathbf{E}[\tau_{r,x,k}]=r$ for all $r\geq 0$ and all $x\in\mathbb{Z}$, $k\in\mathbb{N}$. We assume that $(\tau_{r,x,k})_{r\geq 0}$ for fixed $x\in\mathbb{Z}$ and $k\in\mathbb{N}_{0}$ is a stochastic process taking values in the Skorohod space $D=D[0,\infty)$ of right-continuous functions with existing left limits at all points in $(0,\infty)$, see e. g. [5, Section 16]. Define $(X_{t})_{t\geq 0}$ to be the continuous-time process that follows the trajectory of the walk $(Y_{n})_{n\in\mathbb{N}_{0}}$ but following its $k^{\mathrm{th}}$ step to site $x\in\mathbb{Z}$, say, spends the random time $\tau_{w_{x},x,k}$ at $x$ before making the next step. More precisely, let $T_{0}\vcentcolon=0$ and

for $n\in\mathbb{N}$. Then we define $(X_{t})_{t\geq 0}$ via

The biased Bouchaud’s trap model on $\mathbb{Z}$ is the special case where $(w_{x})_{x\in\mathbb{Z}}$ is an i. i. d.  sequence, and where $\tau_{r,x,k}=r\mathbf{e}_{x,k}$, and $(\mathbf{e}_{x,k})_{x\in\mathbb{Z},\,k\in\mathbb{N}}$ is a family of i. i. d. exponentially distributed random variables with mean $1$; see [3] for further details on Bouchaud’s trap model. Note that the exponential distribution is necessary (and sufficient) to make $(X_{t})_{t\geq 0}$ a continuous time Markov process, but this property is irrelevant for our purposes.

There is a strong law of large numbers for our model. To formulate it, we introduce the notation $p_{\mathrm{esc}}=p_{\mathrm{esc}}(\lambda)$ for the escape probability of $(Y_{n})_{n\in\mathbb{N}_{0}}$ from the origin, i.e.,

Formula (2.4) has the simple interpretation that $(Y_{n})_{n\in\mathbb{N}_{0}}$ travels, by the strong law of large numbers, with linear speed $2p_{\lambda}-1=p_{\mathrm{esc}}(\lambda)$. The average duration of each visit of the walk $(X_{t})_{t\geq 0}$ to a site $x$ is equal to $\mathbf{E}[w_{x}]=\mathbf{E}[w_{0}]$. So on average, the walk makes a step every $1/\mathbf{E}[w_{0}]$ units of time resulting in a speed of $p_{\mathrm{esc}}(\lambda)/\mathbf{E}[w_{0}]$.

While Theorem 2.1 is highly plausible, a rigorous proof is required. We use a coupling-from-the-past argument adapted from [2], in which a formula, not tractable for explicit calculations, for the speed of biased random walk in a one-dimensional percolation environment is derived.

On a suitable probability space, consider independent families of random variables $(w_{x})_{x\in\mathbb{Z}}$, $((\tau_{r,x,k})_{r\geq 0})_{x\in\mathbb{Z},k\in\mathbb{N}_{0}}$ and $(U_{x}(k))_{x\in\mathbb{Z},\,k\in\mathbb{N}}$ where $U_{x}(k)$ is uniform on $(0,1)$, $(w_{x})_{x\in\mathbb{Z}}$ is ergodic, the processes $(\tau_{r,x,k})_{r\geq 0}$, $x\in\mathbb{Z},k\in\mathbb{N}_{0}$ are i. i. d. $r,x,k$ and $\mathbf{E}[\tau_{r,x,k}]=r$ for all $r\geq 0$. We note already here that by [2, Lemma 5.6(b)], the family

is ergodic. Let us write $E\vcentcolon=(0,1)^{\mathbb{N}}\times\mathbb{R}^{+}\times D^{\mathbb{N}}$ for the target space of the $\boldsymbol{V}_{\!x}$. By [2, Lemma 5.6(b)], for any measurable function $f:E^{\mathbb{N}}\times E^{\mathbb{N}}\to\mathbb{R}$, the sequence

is ergodic. We will make extensive use of this fact.

First, for any $x\in\mathbb{Z}$, we may define $(Y_{n}^{x})_{n\in\mathbb{N}_{0}}$ as the discrete-time random walk started at $x$ that, when hitting a state $y\in\mathbb{Z}$ for the $k^{\mathrm{th}}$ time, makes the next step from $y$ to $y-1$ if

and steps to $y+1$, otherwise. A point $x\in\mathbb{Z}$ is called a regeneration point if $Y_{n}^{x}>x$ for all $n\in\mathbb{N}$. Write $I_{x}\vcentcolon=\mathbbm{1}_{\{Y_{n}^{x}>x\text{ for all }n\in\mathbb{N}\}}$ for the indicator of the event that $x$ is a regeneration point.

We write $\boldsymbol{U}_{\!x}$ for $(U_{x}(k))_{k\in\mathbb{N}}$.

By (3.1), $\mathbf{P}(I_{x}=1\text{ for infinitely many }x\in\mathbb{N}_{0})=1$ and hence, by shift invariance and with some effort, we conclude $\mathbf{P}(I_{x}=1\text{ for infinitely many }x<0)=1$. We enumerate the random points $x\in\mathbb{Z}$ with $I_{x}=1$ from left to right with $\ldots,R_{-1},R_{0},R_{1},R_{2},\ldots$ such that $R_{k}<R_{k+1}$ for all $k\in\mathbb{Z}$ and $R_{-1}<0\leq R_{0}<R_{1}$. Now notice that for any $x,y\in\mathbb{Z}$, the trajectories of $(Y_{n}^{x})_{n\in\mathbb{N}_{0}}$ and $(Y_{n}^{y})_{n\in\mathbb{N}_{0}}$ coincide once they hit the first $R_{k}\geq x\vee y$. For $k\in\mathbb{Z}$, define $\rho_{k}\vcentcolon=\inf\{n\in\mathbb{N}_{0}:Y_{n}^{R_{k}}=0\}$ to be the first time at which the random walk started at $R_{k}$ hits $0$. By the transience to the right, $\rho_{k}<\infty$ for all $k<0$. Also, at time $\rho_{k-1}-\rho_{k}$ the walk started at $R_{k-1}$ hits $R_{k}$ and its trajectory then coincides with the walk started at $R_{k}$ for $k<0$, i.e.,

Consequently, we may set

for $k<0$. As $\rho_{k}\to\infty$ almost surely as $k\to-\infty$, this defines $Y_{n}^{-\infty}$ for all $n\in\mathbb{Z}$ almost surely, as we may choose $k<0$ (randomly) such that $-\rho_{k}<n$. Notice that when $-\rho_{k}<n$, then also $-\rho_{k-1}<n$ and $Y_{n}^{-\infty}$ is defined twice (actually infinitely often). Then (3.2) guarantees that the definitions coincide, namely,

We may assume without loss of generality that $(Y_{n})_{n\in\mathbb{N}_{0}}=(Y_{n}^{0})_{n\in\mathbb{N}_{0}}$. We then define $(X_{t})_{t\geq 0}$ as the continuous-time process (with right-continuous paths) starting at the origin at time $0$ that follows the trajectory of $(Y_{n})_{n\in\mathbb{N}_{0}}$ but stays at $x\in\mathbb{Z}$ upon its $k^{\mathrm{th}}$ visit to this point for time $\tau_{w_{x},x,k}$. (This process has the same law as the process defined in Section 2.) Similarly, we define $(X_{t}^{-\infty})_{t\geq 0}$ as the continuous-time process (with right-continuous paths) that follows the trajectory of $(Y_{n}^{-\infty})_{n\in\mathbb{N}_{0}}$, hits the origin for the first time at time $0$ and stays at $x\in\mathbb{Z}$ upon its $k^{\mathrm{th}}$ visit to this point for time $\tau_{w_{x},x,k}$.

For $x\in\mathbb{Z}$, we define

to be the number of visits of the walk $(Y_{n}^{-\infty})_{n\in\mathbb{Z}}$ to $x$ and the time the continuous-time random walk $(X_{t}^{-\infty})_{t\in\mathbb{R}}$ spends at $x$, respectively.