Most transient random walks have infinitely many cut times

In this section we describe the high-level strategy underlying Theorem 1.1 and present a proof in the much simpler case of an exponentially decaying hitting probability process $\mathbb{H}(X_{n})$. We then document the issues that arise when attempting to extend this method to the subexponential case and outline how we overcome them.

The high-level idea is to construct a function $F:\Omega\rightarrow[0,\infty)$ such that there are infinitely many times $n$ when the trajectory $(X_{m})$ of the irreducible Markov chain $M=(\Omega,P)$ satisfies

1. $F(X_{n})<\min_{m<n}F(X_{m})$.       and       2. $F(X_{m})\leq F(X_{n})$ for $m>n.$

In other words, at each of these times $n$, the process $F(X_{i})$ must drop lower than it has previously, and this drop must be a permadrop, i.e. $F(X_{i})$ must not recover to any level achieved prior to the drop. Indeed, if both 1. and 2. hold then the walk cannot return to any vertex it has previously visited and therefore has a cut time at $n$. For the first of these two properties to hold infinitely often, it is sufficient that the process $(F(X_{n}))_{n\geq 0}$ converges to zero, and given transience of the Markov chain, a candidate such as $F(x)=d(o,x)^{-1}$ would suffice. Indeed, studying graph distances appears to be a particularly natural choice in the superdiffusive regime. Unfortunately, there seem to be very limited tools available to prove that this function yields infinitely many permadrops, even when the random walk has positive speed.

These considerations make it natural to instead study the decay of hitting probabilities along the random walk: when the chain is transient the hitting probability process $(\mathbb{H}(X_{n},X_{0}))_{n\geq 0}$ automatically tends to zero, and we can use the fact that the process is a martingale to attempt to analyse the number of permadrops. Indeed, Benjamini, Gurel-Gurevich and Schramm [3] used martingale techniques to show that the expected number of permadrops of this process is always infinite when the chain is transient and hence that every transient chain has infinitely many cut times in expectation. Thus, a natural approach to the cut times problem is to find sufficient conditions for the number of permadrops of this process to be infinite almost surely.

Let us first consider the special case in which $M$ is irreducible and $\mathbb{H}(X_{n},X_{0})$ decays exponentially. Note that this case is already sufficient to resolve the conjecture of Benjamini, Gurel-Gurevich, and Schramm [3] in conjunction with the spatially-dependent-killing argument of Section 3.

The proof of this proposition will rely on Lévy’s zero-one law [26], which is a special case of the martingale convergence theorem.

Problems in the subexponential case. As we have just seen, it is straightforward to show that $Z_{n}$ has infinitely many permadrops whenever it decays exponentially: the large decay rate guarantees an infinite supply of drops of a constant relative size, and the optional stopping theorem bounds the probability of each of these drops being a permadrop below by a constant. This constant lower bound means we can rely on soft techniques like Lévy’s zero-one law to deduce that permadrop events occur infinitely often without having to worry about their dependencies. However, even if we did have to think about dependencies, we could choose the drops far enough away from each other such that we could easily control the correlations between their recovery events. (The exact argument is somewhat subtle: it is not necessarily true that the correlations are small, but the conditional probability of there being a permadrop on one scale given what has happened on previous scales is bounded away from 0.)

When we move to the subexponential case, this argument quickly begins to break down. Indeed, the best we were able to do by optimizing the above approach was to handle the case of stretched-exponential decay $Z_{n}=e^{-\Theta(n^{z})}$ for $z>1/2$. Let us now overview the problems that arise when attempting to perform such an optimization. First, without access to Lévy’s zero-one law, we now have to consider correlations between recovery events. Perhaps more significantly, however, subexponential decay gives us only very loose information about the local behaviour of the hitting probability process. We know the extent to which it must decrease over long periods of time, but have relatively little structural information about how this decrease occurs or about the positions and sizes of the drops: the overall fall in value of the process could be made up of frequent small drops, rare large drops, or any combination thereof. Consider for instance the case of stretched exponential decay $Z_{n}=e^{-\Theta(n^{z})}$ for $z\in(0,1)$. This decay could be achieved by drops by a factor of size $1-n^{z-1}$ at a positive density of times, or, say, by halving at each time of the form $n^{1/z}$. The only restriction is that we cannot have too much of the decay made up of very small drops, as this would contradict the assumed decay of the process.

In an attempt to adapt the arguments used in the exponential decay case, a natural starting place would be to attempt to extract a sparse sequence of roughly independent drops of guaranteed size. For instance, in the stretched exponential decay case $Z_{n}=e^{-\Theta(n^{z})}$, we can set up the infinite sequence of stopping times

for some decreasing sequence $(a_{n})$ very slowly converging to $0$, and $z^{\prime}\in(0,z)$, where the sequence $a_{n}$ should be chosen to allow us to safely ignore dependencies between successive steps. It turns out that this works well for $z>1/2$: a deterministic argument proves that if $(Z_{m})$ has only finitely many drops of any constant relative size, then for $n$ large enough, the drop at time $t_{n}$ must approximately have size at least $1-n^{(z^{\prime}-1)/z}$, and optional stopping allows us to control the dependencies between the recovery events. Optional stopping then gives a $n^{(z^{\prime}-1)/z}$ probability of the drop at time $t_{n}$ being a permadrop, and a simple generalisation of Borel-Cantelli then implies that there are infinitely many permadrops almost surely. For $z\leq\frac{1}{2}$, however, the sequence $n^{(z^{\prime}-1)/z}$ has a convergent sum and the argument breaks down. At this stage we are very far from handling polynomial decay!

Addressing the problems. To get results when the process decays slower than $e^{-n^{1/2}}$, we can no longer just extract sparse sequences and must begin to consider neighbouring drops and the interactions between their recovery events. We attempted to employ a second moment method, bounding each $\operatorname{\mathbb{P}}(A_{i}\cap A_{j})$ from above where $A_{i}$ is the probability that the $i$th drop is a permadrop. Unfortunately, due to the looseness of the information that we have regarding the locations and sizes of the drops, this method proved difficult to implement and did not seem capable of producing optimal results. To overcome the outlined issues, we instead analyse the path of the hitting probability process as it traverses a series of spatial scales. At each scale we upper bound the expected number of large permadrops conditional on there being at least one, and simultaneously lower bound the unconditional expected number of large permadrops. We modulate the definition of “large” across scales to ensure that the former quantity is not too large and the latter is not too small: we need the threshold for the drop sizes we consider to be small enough that we get an adequate supply of drops to lower bound the unconditional expectation while being large enough to prevent an accumulation of drops amplifying the conditional expectation. Once we have done this with a well-chosen choice of thresholding function, comparing these two quantities allows us to lower bound the probability that there is a permadrop on each scale; considering a whole scale simultaneously, rather than individual pairs of drops, allowed us to tackle the flexibility present in the structure of the decay. The Borel-Cantelli counterpart then has a natural application demonstrating that there are infinitely many permadrops when the decay of the hitting probability is strong enough.

Rather than working directly with the hitting probability process of the Markov chain, we work with an augmented continuous time process which we call the drawbridge process. This makes the hitting probability process a continuous martingale away from $1$ and lets us use optional stopping to get exact expressions for permadrop probabilities rather than one-sided inequalities: this is important since we need to prove both upper and lower bounds on relevant expectations. As mentioned above, we will work primarily in the setting of locally finite Markov chains that are irreducible bar the presence of a graveyard state, before deducing a result for general Markov chains via a simple reduction argument.

At several points in our analysis we will want to apply the optional stopping theorem to get equalities rather than one-sided inequalities, making it convenient to work with continuous rather than discrete martingales. For the random walk on a graph, it is well-known that one can embed the discrete-time random walk inside a continuous-time continuous process by considering Brownian motion on an appropriately constructed metric graph known as the cable graph [17, 28]. We now construct a similar way of embedding a non-reversible locally finite Markov chain inside a continuous Markov process, which we call the drawbridge process, and hence of embedding the discrete-time hitting probability process inside a continuous martingale. While there are precedents for considering similar processes [25], it appears to be much less well known than the cable process, and we give a fairly detailed introduction to keep the paper self-contained.

Before giving a precise definition let us first give the intuition behind the name. Let $M=(\Omega,P,\dagger)$ be a locally finite Markov chain with killing and suppose that $P(x,x)=0$ for every $x\neq\dagger$. Consider the corresponding directed graph $G$ with vertex set $\Omega$ and with a directed edge from a vertex $u$ to a vertex $v$ if $u\neq v$ and $P(u,v)>0$. We can make this abstract graph physical, in some sense, by assigning the positive real length $1/P(u,v)$ to each directed edge $(u,v)$. While it is nonsensical to think of a Brownian motion which can only travel in one direction, we can recover restrictions in motion through the use of “drawbridges”. More specifically, we envision Brownian motion on a modified version of the metric graph, in which one places a “drawbridge” along each directed edge of the metric graph. Each drawbridge has two states, raised and lowered. When the drawbridge at $(u,v)$ is raised, the connection between the part of the edge near $v$ and the vertex $v$ itself is severed, and the Brownian motion cannot cross from $v$ onto the edge $(u,v)$. Conversely, when $(u,v)$ is lowered it is possible for the Brownian motion to enter the edge from either $u$ or $v$. For each vertex $u$, we call the drawbridges across the edges emanating from $u$ in the corresponding directed graph the outgoing drawbridges from $u$. The drawbridge process will be defined by taking the Brownian motion on this metric graph and raising and lowering drawbridges as the Brownian motion moves so that, at each time, the outgoing drawbridges from the last vertex it visited are lowered and all other drawbridges are raised.

We now make this precise. Let $M=(\Omega,P,\dagger)$ be a locally finite Markov chain with killing such that $P(x,x)=0$ for every $x\neq\dagger$. For each state $x\in\Omega$, we define the set of outgoing states $x^{\rightarrow}$ to be $\{y\in\Omega\setminus\{x\}:P(x,y)>0\}$. We define the star graph $S[x]$ to be the metric graph with vertex set $\{x\}\cup x^{\rightarrow}$, with edge set $\{\{x,y\}:y\in x^{\rightarrow}\}$, and with edge lengths $1/P(x,y)$, so that $S[\dagger]$ is the metric graph consisting of the single vertex $\{\dagger\}$ and no edges. In an abuse of notation, we will identify vertices in the star graph with their corresponding states; the precise meaning will be clear from context. We construct the metric space $\mathcal{S}$ from the disjoint union $\mathcal{S}^{\sqcup}=\sqcup_{y\in\Omega}S[y]=\{(x,y):x\in\Omega,y\in S[x]\}$ by gluing together $(u,u)$ and $(v,u)$ for every $v\in\Omega$ and $u\in v^{\rightarrow}$. Note that every point in $\mathcal{S}$ has a unique representation of the form $(x,y)$ where $x\in\Omega$ and $y\in S[x]\setminus x^{\rightarrow}$.

Let $(x_{0},y)\in\mathcal{S}$ be such that $x_{0}\in\Omega$ and $y\in S[x]\setminus x_{0}^{\rightarrow}$. We construct the drawbridge process on $\mathcal{S}$ starting at $(x,y)$ as follows. First we start a Brownian motion $(B^{0}_{t})_{t\geq 0}$ on $\mathcal{S}^{\sqcup}$ starting at $(x_{0},y)$ at time $\mathcal{T}(0)=0$ and run until the stopping time $\mathcal{T}(1)=\inf\{t>\mathcal{T}(0):B^{0}_{t}\in\{x_{0}\}\times x_{0}^{\rightarrow}\}$, so that if $\mathcal{T}(1)<\infty$ then $B^{0}_{\mathcal{T}(1)}=(x_{0},x_{1})$ for some $x_{1}\in x_{0}^{\rightarrow}$. If $\mathcal{T}(1)$ is finite, we then run a Brownian motion $(B^{1}_{t})_{t=\mathcal{T}(1)}^{\mathcal{T}(2)}$ on $\mathcal{S}[x_{1}]$, started from $(x_{1},x_{1})$ at time $\mathcal{T}(1)$ and run until the stopping time $\mathcal{T}(2)=\inf\{t>\mathcal{T}(1):B^{1}_{t}\in\{x_{1}\}\times x_{1}^{\rightarrow}\}$. We iterate this construction to generate a possibly infinite sequence $((B^{i}_{t})_{\mathcal{T}(i)\leq t\leq\mathcal{T}(i+1)})_{i}$, noting that $\mathcal{T}(i)$ is almost surely finite whenever $x_{i}\neq\dagger$. If the sequence terminates because $\mathcal{T}(i)=\infty$ for some $i\in N$, which almost surely happens exactly when the process first visits the graveyard state $\dagger$, then we define $\mathcal{T}(j)=\infty$ for $j>i$, set $\tau_{\stretchrel*{{{\dagger}}}{X}}=i-1$ and $\mathcal{T}_{\dagger}=\mathcal{T}(\tau_{\dagger})$. If the sequence does not terminate, we set $\tau_{\stretchrel*{{{\dagger}}}{X}}=\mathcal{T}_{\dagger}=\infty$. Finally, we construct the drawbridge process $(\mathcal{X}_{t})_{t\geq 0}$ by concatenating, in order, the images of the paths of the Brownian motions $(B^{i})_{0\leq i\leq\tau_{\stretchrel*{{{\dagger}}}{X}}}$ in $\mathcal{S}$ under the gluing map $\mathcal{S}^{\sqcup}\rightarrow\mathcal{S}$.

We let $\mathbf{P}_{x,y}$, $\mathbf{E}_{x,y}$ denote probability and expectation with respect to the law of $\mathcal{X}$ started at $(x,y)$ and write $\mathbf{P}_{x}=\mathbf{P}_{x,x}$ and $\mathbf{E}_{x}=\mathbf{E}_{x,x}$. Observe that if $\mathcal{X}$ is started at $(x,x)$ for some $x\in\Omega$ then the discrete-time process $X=(X_{n})_{n=0}^{\tau_{\dagger}}$ defined by $(\mathcal{X}_{\mathcal{T}(n)})_{n=0}^{\tau_{\dagger}}=(X_{n},X_{n})_{n=0}^{\tau_{\dagger}}$ has the distribution of a trajectory of the Markov chain stopped when it hits the graveyard state $\dagger$. Thus, if we fix an arbitrary ‘origin’ state $o\neq\dagger$ and let $\mathcal{T}_{o}=\inf\{t\geq 0:\mathcal{X}_{t}=(o,o)\}$ be the hitting time of $o$, setting $\mathcal{T}_{o}=\infty$ if $o$ is never hit, then the hitting probability $\mathcal{H}(x,y)=\mathbf{P}_{x,y}(\mathcal{T}_{o}<\infty)$ satisfies $\mathcal{H}(x,x)=\mathbb{H}(x)=\mathbb{H}(x,o)$ for all $x\in\Omega$. We define $(\mathcal{Z}_{t})_{t\geq 0}=(\mathcal{H}(\mathcal{X}_{t}))_{t\geq 0}$ and $(Z_{n})_{n\geq 0}=(\mathbb{H}(X_{n}))_{n\geq 0}=(\mathcal{Z}_{\mathcal{T}(n)})_{n\geq 0}$, noting that if $\sigma_{1}\leq\sigma_{2}$ are stopping times for $\mathcal{X}$ such that $\mathcal{X}_{t}\neq o$ almost surely for every $\sigma_{1}<t<\sigma_{2}$ then $(\mathcal{Z}_{t})_{t=\sigma_{1}}^{\sigma_{2}}$ is a continuous time martingale with respect to its natural filtration.

We now set up the notation to record the behaviour of the running minima of a non-negative sequence as it converges to zero across a series of exponential scales. Recall that for each sequence $(z_{n})_{n\geq 1}$ we write $(z_{n}^{*})_{n\geq 0}=(\min_{m\leq n}z_{m})_{n\geq 0}$ for the associated sequence of running minima. Given a non-negative sequence $(z_{n})_{n\geq 0}$ converging to $0$ with $z_{0}>0$, we construct a sequence of logarithmic scales over which to analyse and control its behaviour. We record the associated notation in the following definition.

We begin the proof by proving the following deterministic lemma. Roughly speaking, this lemma says that for sequences which decay to zero sufficiently quickly, we can define a threshold between large and small drops in such a way that the following hold:

1. 1.

   For a good proportion of scales, a good proportion of the decay is made up of large drops.

2. 2.

   The large drops are large enough that there cannot be too many such drops at any particular scale.

The actual threshold we will use will be a simple function of the $\psi$ which is outputted by this lemma. Later, we will apply this lemma to the hitting probability process. Given an increasing function $\psi:[0,\infty)\to[0,\infty)$ and a sequence of non-negative numbers $(z_{n})_{n\geq 0}$, we say that $(z_{n})_{n\geq 0}$ is $\psi$-good on scale $k$ if

or equivalently if

where we write $\prod\{A_{i}:i\in I\}=\prod_{i\in I}A_{i}$ for reasons of legibility. That is, $(z_{n})_{n\geq 0}$ is $\psi$-good on scale $k$ if at least half of the total decay across the scale comes from drops of size at least $\Psi(k):=e^{-k/2\psi^{-1}(k)}$ in a geometric sense. Note that $\psi^{-1}$ denotes the inverse of $\psi$ defined by $\psi^{-1}(x)=\min\{y\geq 0:\psi(y)\geq x\}$; we will typically think of $\psi$ as being a slowly growing function so that $\psi^{-1}$ satisfies $\psi^{-1}(x)\gg x$.

As mentioned above, the function $\psi$, which we think of as “$\phi$ with some room”, is used to define the threshold for a drop on scale $k$ to be “large”, with $z$ being $\psi$-good on scale $k$ precisely when a good proportion of the total decay on this scale comes from drops that are larger than this threshold. Meanwhile, the sequence $a$ is used to take a sparse sequence of spatial scales so that we can safely ignore dependencies between scales while keeping various series divergent so that we can still hope to conclude via Borel-Cantelli.

The proof of Lemma 2.6 will rely on the following elementary analytic facts.