Ergodicity of the zigzag process

Introduction

In recent years there has been a growing interest in the use of Piecewise Deterministic Markov Process (PDMPs) within the field of Markov Chain Monte Carlo (MCMC). In MCMC the objective is to simulate from a ‘target’ probability distribution $\pi$ by designing a Markov chain (or process) which is ergodic and has stationary distribution $\pi$. Although in principle MCMC, e.g. in the form of the Metropolis-Hastings algorithm , can be used to sample from almost any probability distribution of interest, it can suffer from slow convergence as well as heavy computational cost per iteration.

It is for exactly these two reasons that PDMPs are so promising. Firstly, PDMPs are nonreversible, and it is known that nonreversible Markov processes may offer faster convergence relative to reversible Markov processes (see e.g. ) Secondly, a remarkable feature of the simulation procedure of some PDMPs is that we can choose to use unbiased estimates of the ‘canonical’ switching rate without affecting the stationarity of $\pi$. In settings in Bayesian statistics with large data sets (consisting of $n$ observations, say), this offers significant benefits , reducing computational effort per iteration from $\mathcal{O}(n)$ to $\mathcal{O}(1)$. Similar computational benefits can be obtained in systems in statistical physics consisting of many particles . The use of PDMPs in sampling is a very active area of current research and (although it is not possible to give a complete list of references) we point the interested reader to .

In order for a Markov process to be useful in MCMC, it should have the prescribed stationary distribution and furthermore the process should be ergodic: the empirical time averages of a test function $f$ along a trajectory should converge to the space average $\int fd\pi$, a property that usually follows from some kind of irreducibility, meaning roughly speaking that the process should be able to reach any point starting from any other point. The first requirement, stationarity, is relatively easy to satisfy. However the second requirement is certainly non-trivial in the case of PDMPs. For example, it is known that without ‘refreshments’ of the velocity, the BPS can be non-ergodic, for instance for any elliptically symmetric distribution such as a multivariate Gaussian . In contrast, it is known that the ZZP is ergodic in certain cases in which the BPS is not ergodic , and computer experiments have suggested that in fact the ZZP is ergodic under only minimal assumptions. The main result of this paper is a proof of ergodicity for the ZZP under very mild and reasonable conditions, giving theoretical justification for its use in MCMC. This gives the ZZP a possible advantage over the BPS: the practitioner can be confident of the validity of the ZZP as MCMC algorithm and does not need to worry about tuning a refreshment parameter, which may slow down convergence to equilibrium if chosen suboptimally. However other aspects are also influential in determining speed of convergence and computational efficiency, and the relative merits of the ZZP versus the BPS is an area of challenging current and future research. See for results in this direction.

Once ergodicity is established, one may look for estimates of rates of convergence to the invariant measure, in various senses. One of the possible approaches to establish such results is to find a Lyapunov function. For nonreversible processes with small noise, it is often very difficult to guess the form of a suitable Lyapunov function, and quite technical to prove that it indeed works: see for example . In the zigzag case, it turns out that under a reasonable assumption on the decay of the target measure $\pi$ at infinity, we are able to find a Lyapunov function in a quite simple form. Leveraging well known results on long time convergence of processes, this proves in particular that the convergence towards the target measure $\pi$ occurs exponentially fast, and we also get a central limit theorem for ergodic averages.

In ergodicity of the one-dimensional zigzag process is established, which is significantly easier than the multi-dimensional case: for the one-dimensional process it is always possible to switch the single direction component along a trajectory, so that irreducibility is relatively straightforward. The examples of Section 1.3 illustrate why proving ergodicity in the multi-dimensional case is fundamentally different. The conditions for exponential ergodicity in the one-dimensional case are weaker than those we impose for the multi-dimensional case, which is due to the fact that the one-dimensional Lyapunov function does not carry over to the multi-dimensional case; see Section 3.4 for a brief discussion. From a practical viewpoint the slightly stronger conditions which we impose here are very reasonable.

2 Preliminaries

We equip $E$ with its natural product topology, so that a function $(x,\theta)\mapsto f(x,\theta)$ is continuous if and only if $x\mapsto f(x,\theta)$ is continuous for every $\theta$. Similarly $f$ is Lebesgue measurable if $x\mapsto f(x,\theta)$ is measurable for every $\theta$.

For $i=1,\dots,d$ introduce the mapping $F_{i}:\{-1,1\}^{d}\rightarrow\{-1,1\}^{d}$ which flips the $i$-th component: For $j=1,\dots,d$ and $\theta\in\{-1,1\}^{d}$,

An equivalent condition on the switching rates is the existence of a continuous function $\gamma:E\rightarrow[0,\infty)^{d}$ whose $i$-th component does not depend on $\theta_{i}$,

and which is related to the switching rate through

Let $(T^{0},X^{0},\Theta^{0}):=(0,x,\theta)$.

Let $x^{k}(t):=X^{k-1}+\Theta^{k-1}t$, $t\geq 0$

For $i=1,\dots,d$, let $\tau^{k}_{i}$ be distributed according to

Let $i_{0}:=\argmin_{i\in\{1,\dots,d\}}\tau^{k}_{i}$ and let $T^{k}:=T^{k-1}+\tau^{k}_{i_{0}}$. In principle, it is possible that $\tau^{k}_{i}=\infty$ for all $i$ in which case the value of $i_{0}$ will turn out to be irrelevant and we set $T^{k}:=\infty$.

If $T^{k}<\infty$ let $X^{k}:=x^{k}(T^{k})$ and $\Theta^{k}=F_{i_{0}}\Theta^{k-1}$ and repeat the steps. If $T^{k}=\infty$, terminate the procedure.

The piecewise deterministic trajectories $(X_{t},\Theta_{t})$ are now obtained as

defining a process in $E$ with the strong Markov property.

Informally, the process moves in straight lines, only changing velocities at the times $T^{k}$. In the case of canonical switching rates $\lambda_{i}(x,\theta)=(\theta_{i}\partial_{i}U(x))_{+}$, a change in the $i$th component $\theta_{i}$ of the velocity may only happen when in this direction, the process is going “uphill”, that is, if $\theta_{i}\partial_{i}U(x)>0$. Note in particular that if following the current velocity increases $U$, then $\langle\theta,\nabla U(x)\rangle>0$ and at least one of the components has a positive rate of jump.

We further impose an integrability condition on the potential function:

Under this condition the zigzag process has a stationary probability distribution given by

3 Why ergodicity of the ZZP is non-trivial

However, having non-zero values for $\gamma(x,\theta)$ is not beneficial for efficiency: the zigzag process becomes more diffusive as $\gamma_{i}$ increases which results in higher computational costs, see e.g. for a detailed investigation of this phenomenon in the one-dimensional case. Therefore we are mainly interested in the question of ergodicity for the case in which $\gamma_{i}(x,\theta)=0$ for all $i$, $x$ and $\theta$, i.e. for the canonical switching rates.

The expression for the canonical switching rates immediately tells us that one or more of the components of $\lambda$ are zero in large parts of the state space. If the switching rate is zero on a set, it means that while the trajectory moves within this set, there is no freedom to switch the components of the direction vector. As a consequence it is far from obvious how to construct trajectories between any two given points $(x,\theta)$ and $(y,\eta)$ in the state space, which could be a realization of a canonical ZZP trajectory.

To illustrate the difficulties, let us discuss three examples highlighting what could go wrong with the zigzag process.

The potential $U$ is almost everywhere differentiable, with

In this example we consider what may go wrong in the fundamental case of a Gaussian target distribution. Consider first the standard normal case, U(x)=\mbox{\frac{1}{2}}\|x\|^{2}, so that $\nabla U(x)=x$ and $\lambda_{i}(x,\theta)=\max(0,\theta_{i}x_{i})$. As a result, starting from $(x,\theta)$,

We see that in this situation, as $t$ increases, eventually the switching rate in any component becomes positive. This means that after travelling in a certain direction, we may switch any component of the direction vector. The same holds for Gaussian distributions with a diagonally dominant inverse covariance matrix. In our first attempts to prove irreducibility this provided us with a concrete way of building trajectories between any two points.

An example in the setting of Example 2 in which the switching rate in the second coordinate drops to zero after being non-zero initially. Consider a two-dimensional Gaussian target distribution, with potential function U(x)=\mbox{\frac{1}{2}}x^{\top}Vx, where $V=\begin{pmatrix}6&3;&3&2\end{pmatrix}$ (which is positive definite, but not diagonally dominant). In Figure (a) the gradient field of $U$ is drawn. The region where $\partial_{2}U>0$ is shaded blue. In Figure (b) the constant vector field $\theta=(+1,-1)$ is superimposed over the division between regions. If a trajectory follows this vectorfield, coming from the yellow region where $\partial_{2}U<0$, at some point it enters the blue region. At this point the switching rate for $\theta_{2}$, i.e. $\lambda_{2}(x,\theta)=\max(0,-\partial_{2}U(x))$, drops to zero. The conclusion is that switching rates of individual components are not necessarily strictly increasing along the piecewise linear segments of the trajectory, contrary to what intuition may suggest.

However, we should be careful since it is not always the case that, for large enough $t$, we can switch any component of the direction vector, even in ideal situations (e.g. with a strictly convex potential). For example in a two dimensional Gaussian case, it may happen that the switching rate in a certain component may drop from being positive to zero as time increases. See Figure 2 for an illustration of this phenomenon.

4 Main results

We introduce three ‘growth conditions’, i.e. conditions on the tail behaviour of the potential function.

$U\in\mathcal{C}^{2}$ and $\lim_{|x|\rightarrow\infty}U(x)=\infty$.

The following theorems are the main results of this paper.

Suppose the potential function is $\mathcal{C}^{3}$, has a nondegenerate local minimum and satisfies Growth Condition 2. Then the zigzag process is ergodic, in the sense that

The proof of Theorem 1 also establishes that the process is positively Harris recurrent (see Section 3 below for a precise definition), so that the Law of Large Numbers holds (see e.g. ): for all initial conditions $(x,\theta)\in E$ and $g\in L^{1}(\pi)$ for which $s\mapsto g(X_{s},\Theta_{s})$ is almost surely locally integrable,

In particular, the Theorem 2 allows for the case of canonical switching rates, i.e. $\gamma\equiv 0$.

Many target distributions which do not satisfy GC3 can be transformed by a suitable change of variables after which GC3 will be satisfied and exponential ergodicity can be obtained for the transformed distribution. The trajectories of the transformed process can then be used to compute ergodic averages approximating the intended target distribution. We refer to for details of this approach.

Theorem 2 establishes exponential ergodicity under reasonable conditions (i.e. comparable to other sufficient conditions for establishing exponential ergodicity of other processes ) on the tails of the target distribution. E.g. for potential functions of the form $U(x)=(1+\|x\|^{2})^{\alpha/2}$, Theorem 2 establishes exponential ergodicity for any $\alpha>1$. For heavier tails, it is not yet clear what would be a suitable Lyapunov function and this remains a topic of current research.

Although GC3 does not seem to imply GC2, it does imply non-evanescence through a Lyapunov argument [29, Theorem 3.1].

Under essentially the same conditions, we can also establish a Functional Central Limit Theorem. In the following theorem, we write $D$ for the Skorohod space of cadlag functions on $$.

Define $Z_{n}(t):=\frac{1}{\sqrt{n}}\int_{0}^{nt}(g(X_{s},\Theta_{s})-\pi(g))\,ds$, $t\geq 0$.

There exists a $0\leq\sigma_{g}<\infty$ such that for any starting distribution, $Z_{n}$ converges in distribution in $D$ to $\sigma_{g}B$, where $B$ is a standard brownian motion.

In particular, under the conditions of Theorem 3 the Central Limit Theorem of ergodic averages holds:

If $U$ grows faster than a positive power of $\left|x\right|$, then the integrability condition will be satisfied for $\eta$ arbitrarily small, and the CLT applies as soon as $\left|g(\cdot)\right|\leq k\exp(\beta U)$ for some $\beta<1/2$. In other words it applies for “almost” all functions $g\in L^{2}(\pi)$.

A CLT for the one-dimensional Zig-Zag process was obtained earlier in .

5 Strategy

The diagram in Figure 4 illustrates how the different Growth Conditions of Section 1.4 are related to key properties of the zigzag process, which are crucial to establish the main results. As seen in the diagram, it is possible to distinguish between ‘deterministic’ results and ‘probabilistic’ results.

The ‘deterministic’ results, discussed in Section 2 concern the control theoretic aspects of zigzag trajectories. Here we are concerned with reachability: the existence of zigzag trajectories between any points in the state space such that, for a given potential function $U$, the trajectories are admissible: the switching intensities should be positive at the times at which the trajectory changes direction, even in the case of canonical switching rates. As a weaker notion, we are also interested in full flippability: can we, starting from any point in the state space, be certain that eventually all components of the direction vectors are switched at least once? This will all be made more precise in Section 2.

Next, in the ‘probabilistic’ section, Section 3, the results of Section 2 are employed in order to establish several key properties ($\psi$-irreducibility, aperiodicity, the $T$-process property, non-evanescence and (positive) Harris recurrence) of the zigzag process as a Markov process, which finally result in proofs of the main theorems. The definitions of these probabilistic notions, which are standard in the Markov process literature , are recalled in the introduction of Section 3. We conclude with proofs of the main results, located in Section 3.5.

Reachability

More formally, writing $\tau_{k}=\sum_{i=0}^{k-1}t_{i}$ with the usual convention $\tau_{0}=0$, we define $(x(t),\theta(t))$ on $[0,\tau_{m+1}]$ by

Here $F_{(i_{1},\dots,i_{k})}=F_{i_{1}}F_{i_{2}}\dots F_{i_{k}}\theta$, i.e. $F_{I}\theta$ flips all components of $\theta$ listed in the tuple $I=(i_{1},\dots,i_{k})$. This defines a piecewise constant trajectory $\theta(t)$ such that at at time $\tau_{k}$, the $i_{k}$th component of $\theta(t)$ changes sign. The final position $(x(\tau_{m+1}),\theta(\tau_{m+1}))$ will be denoted by $\Phi_{\mathbf{u}}(x,\theta)$.

The following definitions apply for switching intensities $\lambda_{i}(x,\theta)$ satisyfing (1).

A component $i$ of the velocity is flippable at a point $(x,\theta)\in E$ if the corresponding switching rate $\lambda_{i}(x,\theta)$ is strictly positive.

Given a starting point $(x,\theta)$, a control sequence $(\mathbf{t},\mathbf{i})$ is admissible if $i_{k}$ is flippable at the point $(x(\tau_{k}),\theta(\tau_{k}))$, that is, if

Given a starting point $(x,\theta)$ and an end point $(x^{\prime},\theta^{\prime})$, we say that $(x^{\prime},\theta^{\prime})$ is reachable from $(x,\theta)$ and we write $(x,\theta)\leadsto(x^{\prime},\theta^{\prime})$ if there exists an admissible control sequence $\mathbf{u}=(\mathbf{t},\mathbf{i})$ such that $\Phi_{\mathbf{u}}(x,\theta)=(x^{\prime},\theta^{\prime})$.

We write $(x,\theta)\looparrowright(x^{\prime},\theta^{\prime})$ if in addition, every index in $\{1,...,d\}$ appears at least once in $\mathbf{i}$, that is, all the components of the velocity are flipped at least once during the trajectory.

Our goal in this section is to prove that, under weak assumptions, any point is reachable from any other point. It is clear that if $(x,\theta)\leadsto(y,\eta)$ using the canonical, minimal switching rates $\lambda_{i}(x,\theta)=(\partial_{i}U(x)\theta_{i})_{+}$, then the same is true for any choice of the switching rates. Consequently, we may and will assume in this section that the $\lambda_{i}$ are the canonical switching rates.

Given two control sequences $\mathbf{u}=(s_{0},\dots,s_{p};i_{1},\dots,i_{p})$ and $\mathbf{v}=(t_{0},\dots,t_{q};j_{1},\dots,j_{q})$, we can concatenate them into

If $\mathbf{u}$ is admissible starting from $(x,\theta)$ and $\mathbf{v}$ is admissible starting from $\Phi_{\mathbf{u}}(x,\theta)$, then $\mathbf{w}$ is admissible starting from $(x,\theta)$ and $\Phi_{\mathbf{w}}(x,\theta)=\Phi_{\mathbf{v}}\circ\Phi_{\mathbf{u}}(x,\theta)$.

If $(x,\theta)\leadsto(x^{\prime},\theta^{\prime})$, then $(x^{\prime},-\theta^{\prime})\leadsto(x,-\theta)$: indeed if $\lambda_{i}(x,\theta)>0$ then

so if $(t_{0},\dots,t_{m};i_{1},\dots,i_{m})$ is an admissible control that sends $(x,\theta)$ to $(x^{\prime},\theta^{\prime})$, then the reversed sequence $(t_{m},\dots,t_{0};i_{m},\dots,i_{1})$ is admissible and sends $(x^{\prime},\theta^{\prime})$ to $(x,\theta)$. (We thank the AE for pointing out that, without further conditions, this does not hold for non-canonical switching intensties.)

We will first establish reachability for the case where the potential $U$ is quadratic, so that the target measure is Gaussian. We will use this in Section 2.3 to see that around a local minimum of the potential, we can reach any velocity. We will then show that, under Growth Condition 1, starting from any point, it is possible to switch all components of the velocity. All these results will be put together in Section 2.5 to prove reachability in the general case.

2 Reachability for multivariate normal distributions

Suppose that the target distribution is a nondegenerate Gaussian $U(x)=\langle x,Ax\rangle$, where $A$ is a positive definite symmetric matrix. Then for any $(x,\theta)$, $(x^{\prime},\theta^{\prime})$, $(x,\theta)\leadsto(x^{\prime},\theta^{\prime})$.

Even for this simple case, the fact that the jump rates may be zero and that the process may be unable to jump for long stretches makes the proof quite involved. The main idea is to use the fact that by going in a straight line for a sufficiently long time, the process will always reach a region where it can switch some components of its velocity. Let us first define a useful notational shortcut.

For any two velocities $\theta$, $\theta^{\prime}$, we say that $\theta^{\prime}$ is reachable from $\theta$ and we write $\theta\leadsto\theta^{\prime}$ if for any $x$, there exists an $x^{\prime}$ such that $(x,\theta)\leadsto(x^{\prime},\theta^{\prime})$.

Let $\theta\in\{-1,1\}^{d}$. If $\sum_{j}\theta_{i}A_{ij}\theta_{j}>0$ we say that the $i$th component of $\theta$ is asymptotically flippable. The velocity $\theta$ itself is called asymptotically flippable if all its components are asymptotically flippable.

The above definition is explained by noting that in case of asymptotic flippability of the $i$-th component, along any trajectory $x+\theta t$ the $i$-th switching intensity will eventually become positive.

If $I$ is a sequence of asymptotically flippable components for $\theta$, then $\theta\leadsto F_{I}(\theta)$. In particular, if $\eta$ is asymptotically flippable, then for any $\theta$, $\eta\leadsto\theta$.

Write $I=\{i_{1},\dots,i_{m}\}$. Starting from $x$ with velocity $\theta$, after a large time $t$ the components of $A(x+t\theta)$ will have the signs of the components of $A\theta$, so the $i$th component for $i\in I$ will all be flippable. The “pseudo”-control sequence $(t,0,\dots,0;i_{1},\dots,i_{m})$, would therefore bring $(x,\theta)$ to $(x^{\prime},F_{I}\theta)$ for some $x^{\prime}$. It is strictly speaking not a control sequence since its times between switches are zero. However since the positivity of the jump rates is an open condition and the map $\mathbf{t}\mapsto\Phi_{(\mathbf{t},\mathbf{i})}(x,\theta)$ is continuous, this implies the existence of a $\mathbf{t^{\prime}}$ with positive coefficients such that $(\mathbf{t^{\prime}};i_{1},\dots,i_{m})$ is admissible starting from $(x,\theta)$, proving that $\theta\leadsto F_{I}(\theta)$. ∎

The usefulness of this definition is readily seen through the following result.

If $\eta$ is asymptotically flippable, then for any $x$ and $x^{\prime}$, $(x,\eta)\leadsto(x^{\prime},-\eta)$.

Before proving this lemma, let us give a simple case where it is enough to conclude the argument.

If $A$ is diagonally dominant, then every $\theta$ is asymptotically flippable, and $(x,\theta)\leadsto(x^{\prime},\theta^{\prime})$ for all pairs of states.

If $A$ is diagonally dominant then $\sum_{j}\theta_{i}A_{ij}\theta_{j}\geq A_{ii}-\sum_{j,j\neq i}\left|A_{ij}\right|>0$ so all velocities are asymptotically flippable. Given $(x,\theta)$ and $(x^{\prime},\theta^{\prime})$, we first use Lemma 1 to get the existence of $x^{\prime\prime}$ such that $(x,\theta)\leadsto(x^{\prime\prime},-\theta^{\prime})$. By Lemma 2 we can then reach $(x^{\prime},\theta^{\prime})$ from $(x^{\prime\prime},-\theta^{\prime})$, and we are done by transitivity. ∎

Let $\eta$ be an asymptotically flippable velocity, and $x$, $x^{\prime}$ be two arbitrary positions. To control the system from $x$ to $x^{\prime}$, the idea is to go very far in the direction of $\eta$, to a region where all components of $\eta$ are flippable, to flip them in a well chosen order and with well chosen time intervals between flips, so that when the last component is flipped, the system reaches $x^{\prime}$ after a long run in the direction $-\eta$.

To do this rigorously, define $d_{i}=(x^{\prime}_{i}-x_{i})/\eta_{i}$, and suppose first that the $d_{i}$ are increasing: $d_{1}<\dots<d_{n}$. For $1\leq i\leq n-1$, let $t_{i}=(d_{i+1}-d_{i})/2$, and choose $t_{0}$ and $t_{n}$ positive numbers such that $t_{0}-t_{n}=\frac{d_{1}+d_{n}}{2}$.

Now let $t$ be a large time to be chosen later, and consider the control

Starting from $(x,\eta)$, the $i$th component of the position will follow $\eta_{i}$ for a time $t+t_{0}+\cdots+t_{i-1}$, and $-\eta_{i}$ for the remaining time $t_{i}+\cdots+t_{n}+t$. Therefore, the $i$th component of the final position is

If the $d_{i}$ are not increasing but all distinct, we can reorder them by finding a permutation $\sigma$ such that the $d_{\sigma(i)}$ increase, and perform the same argument using the control sequence $(t+t_{0},t_{1},\dots,t_{n-1},t_{n}+T;\sigma(1),\dots,\sigma(n))$ where $t_{i}=(d_{\sigma(i+1)}-d_{\sigma(i)})$.

It remains to check that all the moves are admissible. By a computation similar to the one just above, the position $x^{(i)}$ just before the $i$th flip in the control sequence is given by:

Once the $t_{k}$ are fixed (by the given input of the starting and ending positions $x$ and $x^{\prime}$), one can always take $t$ large enough so that $(Ax^{(i)})_{i}$ has the sign of $\eta_{i}$, which implies that the $i$th jump is indeed admissible.

Finally, if some of the $d_{i}$ are equal, we may always introduce intermediary points $y$ and $y^{\prime}$ such that the differences $(y_{i}-x_{i})/\eta_{i}$ are distinct for all $i$, and likewise the differences $(y^{\prime}_{i}-y_{i})/(-\eta_{i})$, and $(x^{\prime}_{i}-y_{i})/\eta_{i}$. Therefore $(x,\eta)\leadsto(y,-\eta)\leadsto(y^{\prime},\eta)\leadsto(x^{\prime},-\eta)$, and we are done by transitivity. ∎

We now tackle the general case, when $A$ is not diagonally dominant.

For all $\theta$ there exists an asymptotically flippable velocity $\eta$ such that $\theta\leadsto\eta$.

To prove this result, it is useful to represent the matrix $A$ as a Gramian matrix: as can be seen by an $LL^{\top}$ or a symmetric square root representation, there exists a family of vectors $(v_{1},\dots,v_{n})$ such that $A_{ij}=\langle v_{i},v_{j}\rangle$. For a velocity $\theta$, let $v(\theta)=\sum_{i}\theta_{i}v_{i}$. Using this representation, we have the equivalence:

Let $\theta$ be an arbitrary velocity, and suppose that $\theta$ is not asymptotically flippable. Denote by $I$ the subset of asymptotically flippable indices:

Since $\sum_{i}\langle\theta_{i}v_{i},v(\theta)\rangle=\left|v(\theta)\right|^{2}>0$ by positive definiteness of $A$, this set is non empty; by hypothesis it is not equal to $\{1,\dots,n\}$. Let $F_{I}(\theta)$ be the velocity obtained by flipping all asymptotically flippable components. The key point is that this flip increases the norm of $v$:

Indeed, let $v_{+}=\sum_{i\in I}\theta_{i}v_{i}$ and $v_{-}=\sum_{i\notin I}\theta_{i}v_{i}$. Since $v(\theta)=v_{+}+v_{-}$ and $v(F_{I}\theta)=v_{-}-v_{+}$,

Now $\langle v(\theta),v_{-}\rangle$ must be non-positive by definition of $v_{-}$ and the set $I$, but this is $\left|v_{-}\right|^{2}+\langle v_{-},v_{+}\rangle$. The scalar product $\langle v_{-},v_{+}\rangle$ is therefore negative, and

Now starting from $\theta$, apply the following ‘algorithm’:

if $\theta$ is asymptotically flippable, stop.

if it is not, move to $F_{I}\theta$ where $I$ is the set of asymptotically flippable indices.

The fact that $\theta$ is not asymptotically flippable implies that $v_{-}$ cannot be zero (because $I\neq\{1,\dots,d\}$ and the $v_{i}$ are linearly independent because $A$ is positive definite), so the norm will increase. Since along the algorithm, $|v(\theta)|$ is strictly increasing, it must stop at one time; at this time it has (by definition) reached an asymptotically flippable velocity. ∎

Now we have all the ingredients to prove the full reachability in the Gaussian case.

Let $(x,\theta)$ and $(x^{\prime},\theta^{\prime})$ be two points. By Lemma 3, there exists an asymptotically flippable velocity $\eta^{\prime}$ and a point $y^{\prime}$ such that $(x^{\prime},-\theta^{\prime})\leadsto(y^{\prime},\eta^{\prime})$. By the time-reversal property of Remark 8, $(y^{\prime},-\eta^{\prime})\leadsto(x^{\prime},\theta^{\prime})$. Now by Lemma 3 again, we get the existence of an asymptotically flippable velocity $\eta$ and a point $y$ such that $(x,\theta)\leadsto(y,\eta)$. Lemma 1 gives us a point $z$ such that $(y,\eta)\leadsto(z,\eta^{\prime})$, and Lemma 2 tells us that $(z,\eta^{\prime})\leadsto(y^{\prime},-\eta^{\prime})$, which finishes the construction of an admissible trajectory. ∎

3 Reachability around a local minimum

Let the switching rates for the Gaussian density $\pi^{V}$ be denoted by $(\lambda_{i}^{V})$. For a given control sequence $(\mathbf{t},\mathbf{i})=(t_{0},\dots,t_{p};i_{1},\dots,i_{p})$ with associated switching points $(x(\tau_{i}),\theta(\tau_{i}))_{i=1}^{p}$ and final point $(x(\tau_{p+1}),\theta(\tau_{p+1}))$, define

Let $N:=\max_{\theta,\eta}N_{\theta,\eta}$. It follows that for every $\theta\in\{-1,1\}^{d}$ and $(y,\eta)\in E$, $|y|\leq 1$, we have $(0,\theta)\looparrowright(y,\eta)$ through trajectories with minimal switching rate larger than $1/N$ and a maximal distance from the origin smaller than $N$. By a Taylor expansion we have that, for some constant $c$, which we may assume to satisfy $c>1$,

Now let $\theta\in\{-1,1\}^{d}$ and $(y,\eta)\in E$, such that $|y|<\gamma:=\frac{1}{2cN^{3}}$. Let $z=y/\gamma$ so that $|z|<1$. There exists a control sequence $(\mathbf{t},\mathbf{i})$ for which $(0,\theta)\looparrowright(z,\eta)$ such that $\lambda_{\min}^{V}(\mathbf{t},\mathbf{i})>\frac{1}{N}$ and $r_{\max}(\mathbf{t},\mathbf{i})<N$. After a rescaling of $\mathbf{t}$ to $\mathbf{t}^{\prime}=\gamma\mathbf{t}$ we obtain a control sequence for $(0,\theta)\looparrowright(y,\eta)$ such that $\lambda_{\min}^{V}(\mathbf{t}^{\prime},\mathbf{i})>\frac{\gamma}{N}=\frac{1}{2cN^{4}}$ (since the switching rates for the Gaussian potential scale linearly with distance from the origin), and such that the complete trajectory is contained within a ball of radius $\gamma N<\frac{1}{2cN^{2}}<1$, so that we may apply (6) along the trajectory. Along the trajectory with switching times $(\tau_{j})_{j=1}^{p}$ corresponding to the control sequence $(\mathbf{t}^{\prime},\mathbf{i})$, we obtain

i.e. the control sequence $(\mathbf{t}^{\prime},\mathbf{i})$ is admissible for $(0,\theta)\looparrowright(y,\eta)$ with respect to the switching rates $(\lambda_{i})$.

By an analogous argument there exists an admissible control sequence for $(y,\eta)\looparrowright(0,\theta)$. The statement of the proposition follows by concatenation of trajectories. ∎

4 Flippability

Recall that $(x,\theta)\looparrowright(y,\eta)$ if there is an admissible path from $(x,\theta)$ to $(y,\eta)$ along which all components of the velocity are switched.

The process is fully flippable if for each $(x,\theta)$, there exists a $(y,\eta)$ such that $(x,\theta)\looparrowright(y,\eta)$,

If the potential $U$ satisfies Growth Condition 1, then the process is fully flippable.

By definition, the process is fully flippable if for all points $(x,\theta)$, there exists an admissible control sequence $(\textbf{i},\textbf{t})$ such that all indices appear in i. Striving for a contradiction, suppose that there is an $(x,\theta)$ such that, for any admissible control sequence, there is an index in $\{1,...,d\}$ that does not appear in the indices sequence. Suppose that starting from $(x,\theta)$, we are able to construct, for any $\varepsilon$ and any $T$, an admissible trajectory $(x(t),\theta(t))_{t\in[0,T]}$ along which the following bound holds:

Integrating $U$ along this trajectory, we get $U(x(T))\leq U(x)+\varepsilon dT$. However, by hypothesis this trajectory leaves at least one index in the velocity unchanged, so $\|x(T)-x\|_{\infty}\geq T$. This shows that

and is therefore not larger than $U(x)$ by taking $\varepsilon$ to zero. This contradicts the hypothesis that $U$ converges to infinity.

Let us now prove that such trajectories exist. Fix $\varepsilon>0$, and say $T$ is “nice” if there exists an admissible control sequence starting from $(x,\theta)$ such that the bound (7) holds. The set of nice $T$ is clearly open in $[0,\infty)$, so it will be enough to check that it is closed.

To this end, suppose that the $T_{n}$ are an increasing sequence of nice times converging to $T$. The natural idea to construct a nice trajectory of length $T$ is to pick a trajectory of length $T_{n}$ and continue it in the final direction $\theta_{T_{n}}$ until time $T$. The corresponding trajectory will be admissible, but it may fail to satisfy (7) if, during the interval $[T_{n},T)$, one of the quantities $(\theta(t))_{i}\partial_{i}U(x(t))$ crosses the level $\varepsilon$. We will prove that by switching the corresponding indices, we can construct a nice trajectory.

Since the process moves at finite speed, we know that all admissible trajectories of length less than $T$ starting from $(x,\theta)$ will lie in a bounded set, only depending on $T$. Let $C_{T}$ be an upper bound on the Hessian of $U$ on this bounded set. Let $n$ be large enough so that $T-T_{n}<\varepsilon/{2C_{T}}$, and consider a “nice” trajectory of length $T_{n}$; we wish to continue it up to time $T$. Let $D=\{i_{1},...,i_{m}\}$ be the set of “dangerous” indices, that is, indices for which $\theta_{i}\partial_{i}U(x(T_{n}))>\varepsilon/2$. Consider the trajectory obtained by concatenating the nice $T_{n}$ control sequence with the sequence $(i_{1},...,i_{m};\varepsilon^{\prime},...,\varepsilon^{\prime},T-T_{n}-m\varepsilon^{\prime})$. If $\varepsilon^{\prime}$ is small enough, this trajectory will be both admissible and nice: all “dangerous” indices will be switched before the corresponding product reaches $\varepsilon$, and they will not have time to grow up to $\varepsilon$ again. The set of nice $T$ is therefore $[0,\infty)$ in its entirety. ∎

5 Reachability in the general case

If $(x,\theta)\looparrowright(y,\eta)$, then there is an open neighborhood $U$ of $(y,\eta)$ such that for all $(y^{\prime},\eta^{\prime})\in U$, $(x,\theta)\looparrowright(y^{\prime},\eta^{\prime})$.

By hypothesis there is a sequence of times and indices such that

Define $\Phi:(s_{0},...,s_{n})\mapsto x+s_{0}\theta+s_{1}F_{i_{1}}\theta+\cdots s_{n}F_{i_{1},...,i_{n}}\theta$. Then $D\Phi=(\theta,F_{i_{1}}\theta,...,F_{i_{1},...,i_{n}}\theta)$. Since the difference between two consecutive vectors in this family is $\pm 2e_{i_{k}}$, the map $\Phi$ has full rank if all components are switched at least once. Therefore $\Phi$ is a submersion from a neighborhood of $(t_{0},...,t_{n})$ to a neighborhood of $y$. By continuity of the switching rates, we may assume without loss of generality that for all $(s_{0},...,s_{n})$ in this neighborhood, the corresponding trajectory is admissible. Since the sequence of switches is the same as the original trajectory, we get the conclusion. ∎

Let us now prove openness. If $(y,\eta)$ is in the non-trivial class of $(x,\theta)$, then $(x,\theta)\looparrowright(x,\theta)\leadsto(y,\eta)$, so $(x,\theta)$ leads to all points near $(y,\eta)$. Similarly, $(x,-\theta)\looparrowright(y,-\eta)$, so $(x,-\theta)$ leads to all points in a neighborhood of $(y,-\eta)$, and by reversal, all points near $(y,\eta)$ must lead to $(x,\theta)$. Therefore all points near $(y,\eta)$ are in fact equivalent to $(x,\theta)$ and the class is open.

The reversal property is a consequence of the similar property for $\leadsto$. ∎

The open equivalent classes are “almost stable” under $\leadsto$ and its inverse, that is, if the class of $(x,\theta)$ is open, then for $\pi$-almost every $(y,\eta)$, we have the equivalence $(y,\eta)\leadsto(x,\theta)\iff(x,\theta)\leadsto(y,\eta)\iff(x,\theta)\sim(y,\eta)$.

In the countable state setting, classes that are stable under the analogue of $\leadsto$ are called “essential” (see, e.g., ). In a general state space, it is known that the communication structures are more difficult to define and study; this has led in particular to the definition of $\psi$-irreducibility, see [30, Chapter 5]. It turns out that in our particular case, the relation $\leadsto$ defines interesting equivalence classes that we can study before discussing $\psi$-irreducibility.

Let $O$ be an open class. Let $O_{+}$ be the “future” of $O$, that is, the set of $(y,\eta)$ such that there exists $(x,\theta)\in O$ such that $(x,\theta)\leadsto(y,\eta)$. Note that since $(x,\theta)\looparrowright(x,\theta)$, $O_{+}$ is open, therefore measurable. Let $P^{t}((x,\theta),A)$ denote the Markov transition kernel of the zigzag process. Let us use the invariance of $\pi$ through the resolvent kernel:

Since $O_{+}$ is stable by $\leadsto$, the probability in the first integral is $1$, so the whole first integral is equal to $\pi(O_{+})$. Therefore the second integral must vanish: for all $(x,\theta)$ in some set $A$ of full $\pi$-measure,

If $(x,\theta)$ is in $A$ and leads to a point in $O$, then the probability above is strictly positive, so $(x,\theta)$ must be in $O_{+}$. Consequently we can build a loop from $(x,\theta)$ that intersects $O$, so $(x,\theta)$ is in $O$.

In the other direction, we use reversal. Without loss of generality we may assume $A$ is stable by reversal of velocities. If $(x,\theta)$ in $A$ is reachable from a point $(y,\eta)$ in $O$, then $(x,-\theta)\leadsto(y,-\eta)$, so $(x,-\theta)\in RO$, and $(x,\theta)\in O$.

We now prove a stronger stability statement by getting rid of the “$\pi$-almost surely”. Consider a point $(x,\theta)$ in an open class $O$ and suppose that $(y,\eta)$ is reachable from $(x,\theta)$. By the assumption, we can find a $(z,\xi)$ such that $(y,\eta)\looparrowright(z,\xi)$. By Lemma 5, $(y,\eta)\leadsto(z^{\prime},\xi^{\prime})$ for all $(z^{\prime},\xi^{\prime})$ in a neighborhood of $(z,\xi)$. By transitivity, $(x,\theta)$ itself leads to all points in this neighborhood. Such a neighborhood must have a positive $\pi$-measure, so at least one of the $(z^{\prime},\xi^{\prime})$ leads back to $(x,\theta)$. Therefore we have a loop $(x,\theta)\leadsto(y,\eta)\leadsto(z^{\prime},\xi^{\prime})\leadsto(x,\theta)$, so all three points are in the same class, so open classes are stable by $\leadsto$. Using reversal it is easy to see that they are also stable in the other direction.

If the potential $U$ is $\mathcal{C}^{3}$, satisfies Growth Condition 1, and has a nondegenerate local minimum, then there is only one equivalence class. In particular $(x,\theta)\leadsto(y,\eta)$ for all $(x,\theta)\in E$ and $(y,\eta)\in E$.

Ergodicity and exponential ergodicity

To prove ergodicity and exponential ergodicity, we will use standard results from . In order to show that they apply, we need to check a certain number of properties of the process. Some of these properties (aperiodicity, irreducibility) are analogues in the continuous time and continuous space setting of classical notions for Markov chains. In order to guarantee that the process does not behave too wildly with respect to the topology of the ambient space, Meyn and Tweedie have also introduced the notion of $T$-processes (where $T$ stands for “topology”). We will first recall these here, phrased in terms of a general Markov process $(Z_{t})$ taking values in a space $E$, for completeness. For a more detailed overview of these notions, we refer to the aforementioned papers, in particular , and the reference book .

A measurable set $C\subset E$ is called petite if there exists a probability distribution $a$, a constant $c>0$ and a nontrivial measure $\nu$ on $E$ such that

In the next sections, we establish that the zigzag process is in fact an irreducible, aperiodic $T$-process; Section 3.4 is devoted to finding a suitable Lyapunov function.

In this section we give two results on the existence of an absolutely continuous component in the distribution of the position of the process. We start with an easy result, expressed in terms of a certain stopping time.

Let $(T_{i})$ be the random times where the components of the velocity switch. Let $N$ be the random integer such that $T_{N}$ is the first time when $d-1$ components have switched; let $N=\infty$ if this does not occur. Let $\tau=T_{N+1}$ if $T_{N}$ is finite, and $\tau=\infty$ otherwise.

In particular, in case $d=1$, then $N=0$, $T_{N}=0$ and $\tau$ is the time of the first switch.

It is well known (see ) that the law of $(X_{t},\Theta_{t})$ may be obtained by a thinning procedure. More precisely, let $\overline{\lambda}$ be an upper bound on the switching rates up to time $t$ (such a bound exists since the process has finite speed and the switching rates are continuous). Then the process may be constructed on $[0,t]$ by running a Poisson clock with intensity $\overline{\lambda}d$, and, for each Poisson event, picking an index $i$ uniformly, then accepting or rejecting the flip of the corresponding component of the velocity with a probability given by $\lambda_{i}(x,\theta)/\overline{\lambda}$.

Recall that $F_{i_{1},...,i_{k}}\theta$ is the velocity obtained from $\theta$ by flipping, possibly many times, the components appearing in the sequence. For convenience, we extend this definition to allow zero values in the index sequence, which corresponds to no flipping. This allows us to write

where $M$ is a random integer (larger than $N$), the $(I_{k})$ take values in $\{0,1,...,d\}$ with $I_{k}=j$ for $j\neq 0$ indicating a proposed and accepted $j$ flip, while $I_{k}=0$ corresponding to all rejected flips, and the $(E_{i})$ are the interarrival times of the Poisson clock. We decompose over all possible index sequences:

If $M=m$, $N\leq m$ so by definition, at least $d-1$ different (non-zero) indices must appear in the sequence $(i_{1},...,i_{m})$, and

The proof of the existence of an absolutely continuous component at a fixed time is a bit more involved, but is the key ingredient to prove that the process behaves nicely.

If $(x,\theta)\looparrowright(y,\eta)$ then there exist open sets $U$ and $V$, with $x\in U$ and $y\in V$, and constants $\varepsilon>0$, $t_{0}>0$, $c>0$, such that for any $x^{\prime}\in U$, and all $t\in(t_{0},t_{0}+\varepsilon]$,

Similar results may be found in previous works, e.g. [3, Lemmas 2 and 3], or [4, Section 6.5]. In order to get the probabilistic consequences, we need the uniformity in the starting point that appears in . Since our hypotheses here are slightly different, we include a proof for the sake of completeness. We also note that taking canonical switching rates leads to a degenerate situation where the local Hörmander type criteria of do not apply.

By hypothesis there exists an admissible deterministic control sequence $\mathbf{u}=(\mathbf{t},\mathbf{i})=(t_{0},...,t_{m};i_{1},...,i_{m})$, such that all indices occur at least once in $\mathbf{i}$, and $\Phi_{\mathbf{u}}(x,\theta)=(y,\eta)$. Recall the notation $\tau_{k}=\sum_{j=0}^{k-1}t_{j}$ and let $t=\tau_{m+1}=\sum_{k=0}^{m}t_{k}$ be the final time of the trajectory.

We use the same thinning construction as in the proof of Lemma 7 above, with a Poisson clock of intensity $\overline{\lambda}d$, where $\overline{\lambda}$ is an upper bound on the switching rates up to time $t$.

For $j=1,...,(m-1)$, let $\mathcal{U}_{j}$ be a bounded neighbourhood of $\tau_{j}$; we may assume that the $\mathcal{U}_{j}$ do not intersect and, by continuity, that the control sequences $(\mathbf{s},\mathbf{i})=(s_{0},...,s_{m-1},\mathbf{i})$ satisfy $\lambda_{\min}(\mathbf{s},\mathbf{i})\geq\underline{\lambda}>0$ for any $\mathbf{s}$ such that $\sum_{l=0}^{j-1}s_{l}\in\mathcal{U}_{j}$ for all $j$.

Now let $f$ be an arbitrary non-negative test function. Let $A$ be the event that $m$ Poisson events $T_{1},...,T_{m}$ occur before time $t$, that $T_{j}\in\mathcal{U}_{j}$ for all $j$, that the indices are picked as in $\mathbf{i}$, and that all proposed switches are accepted. Then

Since the choice of indices to switch and the acceptance/rejection tests are independent from the Poisson process, we get by conditioning:

Using classical properties of the Poisson process, this implies that for some positive constant $c$,

where the $U_{j}$ are independent and $U_{j}$ is uniformly distributed on $\mathcal{U}_{j}$.

The partial map $(u_{1},...,u_{m})\mapsto\Psi(x,t,u_{1},...,u_{m})$ has full rank: indeed, the image of its differential is spanned by the vectors

To prove the uniform version, we see $x$ and $t$ as a parameter and apply the uniform submersion lemma [4, Lemma 6.3] to get the result. ∎

2 Non-evanescence

For classical Markov chains on countable spaces, it is well known that for any $x$ and $y$, the following equivalence holds:

For general chains and processes, this equivalence is no longer true: starting from a point $x$, the time spent in a set $A$ may be finite with positive probability, even when its expectation is infinite. This may essentially happen if the process has a positive probability of escaping to infinity when it starts in a particular set: this canonical counter-example is explained e.g. in [30, Section 9.1.2].

This equivalence is used to prove that a (classical) irreducible chain that admits an invariant probability measure is positive recurrent. To obtain the natural property of Harris recurrence for a general chain, ($\psi$-)irreducibility and the existence of the invariant probability are not enough, and we need to show additionally that the escaping to infinity does not happen.

In the context of the zigzag process, we refer to the ‘ridge’, Example 3 in Section 1.3, which describes a smooth potential function with the property that for certain initial conditions the zigzag process will escape to infinity with full probability.

A point $(x,\theta)$ is said to be non-evanescent if ${\rm Phys.~Rev.~B}[x,\theta]{\left|X_{t}\right|\to\infty}=0$. It is weakly non-evanescent if this probability is strictly less than $1$.

We start by showing how the deterministic statements on flippability may be used to prove probabilistic non-evanescence properties.

Note that the first growth condition $U\to\infty$ already has the probabilistic consequence that the process switches infinitely often. Indeed, for any $(x,\theta)$ and any $n$,

so ${\rm Phys.~Rev.~B}[(x,\theta)]{T^{1}<\infty}=1$, where $(T^{i})$ are the switching times as introduced in Section 1.2. By the strong Markov property, this implies for all $k$

If the invariant measure $\pi$ is a probability measure (as it is assumed to be in this paper), then $\pi$-almost all points are non-evanescent.

If additionally the process is fully flippable in the sense of Definition 6, then all points are weakly non-evanescent.

The first statement is classical. For the sake of completeness we include a proof. Let $K$ be a compact set. Since \liminf_{t\rightarrow\infty}\mathbf{1}_{X_{t}\notin K}=\{X_{t}\text{ eventually leavesK}\}, we have by Fatou’s lemma

Since \{\left|X_{t}\right|\to\infty\}=\bigcap_{K}\{X_{t}\text{ eventually leavesK}\}, we are done since $\{\pi\}$ is tight.

Let us now prove the second statement. Let $\mathcal{N}$ be the set of non-evanescent points: this set has full $\pi$-measure, so its complement is Lebesgue negligible. Let $(x,\theta)$ be an arbitrary starting point, and consider the stopping time $\tau$ introduced in Lemma 7. By the strong Markov property,

If the process is fully flippable, this last probability is positive, proving the weak non-evanescence property. ∎

If we add a slightly stronger hypothesis on the growth of the potential at infinity, namely Growth Condition 2, we get a stronger non-evanescence result. We start by saying that if the process is evanescent, it must go to infinity in a very particular way, by staying forever in an affine subspace.

Let $d\geq 2$. Suppose that there exists an invariant probability measure, and that $(x,\theta)$ satisfies ${\rm Phys.~Rev.~B}[(x,\theta)]{\left|X_{t}\right|\to\infty}>0$. Then there exist two indices $i$ and $j$ such that

We prove this statement by contraposition and assume that, with probability one, at most one component of the velocity does not switch. This implies that the time $T_{N}$ defined in Lemma 7 is a.s. finite, and since there are infinitely many switches by Remark 11, the time $\tau=T_{N+1}$ of the same Lemma 7 is also finite. Reusing the bound (9) from the proof of Lemma 9, we immediately get that ${\rm Phys.~Rev.~B}[(x,\theta)]{\left|X_{t}\right|\to\infty}=0$, proving the lemma. ∎

Recall that Growth Condition 2 states, in dimension $d$, that

We wish to prove for all $d$ the following statement:

If $d=1$, by (9), with $\tau$ denoting the time of the first switch, and Remark 11, ( P d ) follows.

For $d\geq 2$, the strategy is to prove this by induction. The form of the growth condition is tailored to this strategy: it clearly implies that $\int\exp(-U(x))dx$ is finite and may be normalized into a probability, but it crucially also implies that the same is true for all the conditional measures on affine subspaces. For the base case $d=2$, using Lemma 10, we see that if ${\rm Phys.~Rev.~B}[(x,\theta)]{|X_{t}|\to\infty}>0$ then with positive probability the process never switches. Since $U\to\infty$ this is not possible (see Remark 11).

Let us now prove the induction step by contraposition. Assume that ($\mathcal{P}_{d+1}$) is false: there exists a potential $U$ in dimension $d+1$ that satisfies the growth condition, but for which the zigzag process is evanescent, that is, there is a point $(x,\theta)$ such that ${\rm Phys.~Rev.~B}[(x,\theta)]{\left|X_{t}\right|\to\infty}>0$. Our goal is to define a potential in dimension $d$ that also satisfies the growth condition and for which we also have evanescence.

By Lemma 10, there are two indices, say $d$ and $d+1$ without loss of generality, such that