Persi Diaconis

Laurent Miclo

On the spectral analysis of second-order Markov chains

Keywords: second order Markov chains, trajectorial reversibility, spectrum of non-reversible Markov kernels, spectral gap, improvement of speed of convergence, discrete position-speed Markov chains, homogeneous and Abelian second order Markov chains 60J10, secondary: 37A30, 47A55, 15A18, 60B15, 65C40

Second order Markov chains which are trajectorially reversible are considered. Contrary to the reversibility notion for usual Markov chains, no symmetry property can be deduced for the corresponding transition operators. Nevertheless and even if they are not diagonalizable in general, we study some features of their spectral decompositions and in particular the behavior of the spectral gap under appropriate perturbations is investigated. Our quantitative and qualitative results confirm that the resort to second order Markov chains is an interesting option to improve the speed of convergence to equilibrium.

Introduction

Resorting to nonreversible Markov chains or to second order Markov chains may present some important advantages from a practical simulation point of view. This feature was emphatized by Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF] who showed how the asymptotical variance can be diminished for empirical estimators of expectations, when one uses stochastic chains which have a tendency of not returning back where they were just coming from. Our main results here go in the same direction, but we will rather be interested in the asymptotic speed of convergence to equilibrium, measured through the spectral gap. This will lead us to study the whole spectrum of some second order Markov chains and its behavior under perturbations designed to improve them.

A stochastic chain (X n ) n∈N is said to be a second order Markov chain if at any time n ∈ N, its future only depends on its past through the present position and the previous one, namely if we have the following almost sure equality for the conditional laws

L((X m ) m≥n+1 |(X m ) m∈ 0,n ) = L((X m ) m≥n+1 |X n , X n-1 )
(by convention X -1 = X 0 ). Equivalently, this means that the stochastic chain (X n , X n+1 ) n∈N is Markovian. We will only consider time-homogeneous second order finite Markov chains, i.e. the X n , for n ∈ N, take value in a finite state space V and for any n ∈ N \ {0} and x, x ′ , x ′′ ∈ V , the quantity

M (x, x ′ ; x ′′ ) ≔ P[X n+1 = x ′′ |X n = x ′ , X n-1 = x] (1)
does not depend on n (when it is well-defined, i.e. when the event {X n = x ′ , X n-1 = x} is not negligeable with respect to the underlying probability P). Conversely, if we are given a Markov kernel M ≔ (M (x, x ′ ; x ′′ )) x,x ′ ,x ′′ ∈V from V 2 to V and a probability distribution m 0 = (m 0 (x, x ′ )) x,x ′ ∈V on V 2 , there exists a unique (in law) stochastic chain (X n ) n∈N on V such that the equality (1) holds and such that the initial law of (X 0 , X 1 ) is m 0 . The probability distribution m on V 2 is said to be trajectorially reversible with respect to the kernel M , if the corresponding second order Markov chain starting with the initial law m satisfies for any n ∈ N, the identity in law

L(X 0 , X 1 , • • • , X n ) = L(X n , X n-1 , • • • , X 0 ) (2)
This notion of reversibility is different from the usual reversibility for the Markov chain (X n , X n+1 ) n∈N , which is not satisfied in general. As it was shown by Bacallado and Pande [START_REF] Bacallado | Bayesian analysis of higher-order, reversible, Markov chains[END_REF], it is sufficient to check the equality [START_REF] Bacallado | Bayesian analysis of higher-order, reversible, Markov chains[END_REF] for n = 1 and n = 2. In particular the distribution m is symmetrical in its first and second variables. Let us write

∀ x, x ′ ∈ V, m(x, x ′ ) = ν(x)L(x, x ′ ) ≕ (ν × L)(x, x ′ ) ( 3
)
where ν is the law of X 0 and L is a Markov kernel corresponding to the conditional law under m of X 1 when X 0 is given (it is unique if ν is positive). By symmetry, ν is reversible (in the usual sense) with respect to L. Let ( X n ) n∈N be a Markov chain on V , starting with ν as initial distribution and whose transition kernel is given by L. It is not difficult to see that the distribution m is invariant for the Markov chain (X n , X n+1 ) n∈N and by consequence we are insured of the identities in law

∀ n ∈ N, L(X n , X n+1 ) = L( X n , X n+1 )
In particular, appropriate assumptions of aperiodicity and irreducibility on L and M will insure that whatever the initial distributions,

lim n→∞ L(X n , X n+1 ) = m = lim n→∞ L( X n , X n+1 )
and our main goal in this paper is to compare the corresponding speeds of convergence. They will be measured via spectral gaps, which give the asymptotical convergence rates to equilibrium. Let M be extended as a Markov kernel on V 2 through the formula ∀ (x, x ′ ), (x ′′ , x ′′′ ) ∈ V 2 , M ((x, x ′ ), (x ′′ , x ′′′ )) ≔ δ x ′ (x ′′ )M (x, x ′ ; x ′′′ ) (

(where δ x ′ is the Dirac function at x ′ ), i.e. we are just reinterpreting M as the transition kernel of the Markov chain (X n , X n+1 ) n∈N . This enables us to see M as a right operator on the space F(V 2 ) of real-valued functions defined on V 2 (or on the space F(V 2 , C) of complex plane-valued functions defined on V 2 ) and as a left operator on the space M(V 2 ) of signed measures on V 2 . We have for instance

∀ F ∈ F(V 2 ), ∀ (x, x ′ ) ∈ V 2 , M [F ](x, x ′ ) ≔ x ′′ ∈V M (x, x ′ ; x ′′ )F (x ′ , x ′′ )
By invariance of m, the subspace F * (m, C) ≔ {F ∈ F(V 2 , C) : m[F ] = 0} is stable by M , so let Θ * (M ) ⊂ C be the spectrum of M * , the restriction of M to F * (m, C). The spectral gap of M is

λ(M ) ≔ 1 -max{|θ| : θ ∈ Θ * (M )} ∈ [0, 1]
Then, if • is a norm on M(V 2 ), we have for any initial distribution m 0 on V 2 , lim n→∞

1 n ln ( m 0 M n -m ) ≤ ln(1 -λ(M ))
and there exists an initial point (x, x ′ ) ∈ V 2 such that lim n→∞ 1 n ln δ (x,x ′ ) M nm = ln(1λ(M ))

Similar definitions can be given for the spectral gap of L, by replacing the state space V 2 by V . One can alternatively consider the second order Markov kernel M (0) naturally associated to L:

∀ x, x ′ , x ′′ ∈ V, M (0) (x, x ′ ; x ′′ ) ≔ L(x ′ , x ′′ ) (5)
(it corresponds to the transition kernel of the Markov chain ( X n , X n+1 ) n∈N ). We will check that the spectrum of M (0) is just the spectrum of L (with the same multiplicities, except for the eigenvalue 0) plus the eigenvalue 0, so that λ(L) = λ(M (0) ). Note that since ν is reversible with respect to L, this operator is diagonalizable in R and we have Θ * (M (0) ) ⊂ R, but in general M (0) won't be diagonalizable: we will see that it contains 2 × 2-Jordan blocks if 0 is an eigenvalue of L.

Our first result states that except in the cases where L = ν (where the probability measure ν is seen as a Markov kernel via the formulas: ∀ x, x ′ ∈ V, ν(x, x ′ ) = ν(x ′ ), this convention will be assumed enforced in the whole paper) or where L is aperiodic (which by reversibility means that the graph induced by L is bipartite), it is always possible to find a second order Markov chain M which admits ν × L as trajectorial reversible measure and which has a larger spectral gap than L. Note that the largest possible spectral gap is 1 and that the equality L = ν is equivalent to the fact that λ(L) = 1, so in this situation the spectral gap cannot be improved by any means. In the aperiodic case, the spectral gap cannot be improved either: let V ′ and V ′′ be proper subsets of V such that V = V ′ ⊔ V ′′ and such that the V ′ × V ′ and V ′′ × V ′′ entries of L are null. Then if M admits ν × L as trajectorial reversible measure, necessary M is also periodic, since the Markov chain (X n , X n+1 ) n∈N goes from the set V ′ × V ′′ to the set V ′′ × V ′ and conversely.

Indeed, let M (1) be a second order Markov kernel admitting ν × L as trajectorial reversible measure and satisfying ∀ x, x ′ , x ′′ ∈ V, M (1) (x, x ′ ; x ′′ ) > L(x ′ , x ′′ ) , if x ′′ = x, L(x, x ′ ) > 0 and L(x ′ , x ′′ ) > 0 (in particular M (1) has less tendency to come back where it just came from than M (0) ). It is not difficult to see that such kernels exist. For any a ∈ [0, 1], define M (a) ≔ (1a)M (0) + aM (1) which is a second order Markov kernel still admitting ν × L as trajectorial reversible measure.

Then we have

Theorem 1 Assume that L is irreducible, that L = ν and that L is aperiodic. The mapping [0, 1] ∋ a → λ(M (a) ) is differentiable at 0 and we have dλ(M (a) ) da (0) > 0

In fact we will show a better result, saying that under the above assumptions the whole spectrum of L outside 0 has an initial tendency to improve: let [0, a 0 ] ∋ a → θ(a) be a differentiable function such that θ(a) ∈ Θ * (M (a) ) for a ∈ [0, a 0 ] (where a 0 ∈ (0, 1) will be small enough in practice) and such that θ(0) = 0. Since θ(0) ∈ Θ * (L), it is real. Then we will prove that dθ(a)/da(0) is real and that its sign is the opposite sign of θ(0), namely initially, when a starts to increase from 0, θ(a) is going in the direction of 0. But if instead of improving the whole spectrum outside 0, one only wants to improve the spectral gap, there is a more efficient way to do it, which uses the ordering of the space created by an eigenfunction associated to the eigenvalue of L corresponding to the spectral gap (under the assumption that such an eigenfunction is unique up to a factor) as it will be explained in detail in Section 3. Nevertheless, it should be kept in mind that to get quantitative bounds on the distance to equilibrium (for instance in the chi-square sense), not just an asymptotical result, the knowledge of the whole spectrum is preferable to the spectral gap.

In order to get a global picture of how the spectral gap (and indeed the whole spectrum) depends on the parameter a ∈ [0, 1], we consider a family of homogeneous-space simple examples. Assume that V is a group G. Let (X n ) n∈N be a second order Markov chain with kernel M and define the corresponding speed process (Y n ) n∈N by

∀ n ∈ N, Y n ≔ X -1 n X n+1
The position-speed process (X n , Y n ) n∈N is Markovian and its transition kernel can be written as

∀ (x, y), (x ′ , y ′ ) ∈ G 2 , P ((x, y), (x ′ , y ′ )) = δ xy (x ′ )K x ′ (y, y ′ ) (6)
where the Markov kernel of transition from speed y to speed y ′ above the point x ′ is given by

K x ′ (y, y ′ ) ≔ M (x ′ y -1 , x ′ ; x ′ y ′ ) (7)
In the examples we will consider, the group G is Abelian (in which case we adopt an additive notation) and the speed variable only takes values in a symmetrical subset S ⊂ G of generators of G, which will be small in comparison to G. Furthermore the situation will be assumed to be homogeneous: the kernels K x do not depend on the support point x ∈ G. Then under additional hypotheses (of trajectorial reversibility and a kind of irreducibility, see next section), the probability measure ν is uniform and the transition kernel L corresponds to the Markov kernel of a reversible random walk: there exists a symmetric probability measure µ whose support is S such that

∀ x, x ′ ∈ G, L(x, x ′ ) = µ(x ′ -x) (8)
In this context, the second order Markov kernel M (0) corresponds to the Markov kernel K (0) for the speed variables given by

∀ y, y ′ ∈ S, K (0) (y, y ′ ) ≔ µ(y ′ )
To define a natural perturbation, assume furthermore that µ is the uniform distribution over S (so our framework is parametrized by the data (G, S) consisting of a finite Abelian group and a symmetric subset of generators). Consider the Markov kernel K (1) which forbids to reverse speed and transfers the corresponding weight to all the other directions:

∀ y, y ′ ∈ S, K (1) (y, y ′ ) ≔ 1 |S|-1 , if y ′ = -y 0 , if y ′ = -y
Of course, this definition makes sense only if |S| ≥ 2 (due to the symmetry of S, |S| = 1 corresponds to two trivial situations: G = S = Z 1 or G = Z 2 and S = {1}). Define as well the interpolating kernels:

∀ a ∈ [0, 1], K (a) ≔ (1 -a)K (0) + aK (1) (9)
We associate to them the second order Markov kernels M (a) for a ∈ [0, 1], which are all trajectorially reversible with respect to the probability measure

∀ x, x ′ ∈ G, m(x, x ′ ) ≔ 1 |G||S| , if x ′ -x ∈ S 0 , otherwise (10)
Then we have the following behavior for the spectral gap of M (a) as a function of a ∈ [0, 1]:

Theorem 2 Assume that G is a finite Abelian group and that S is a generating set of G with |S| ≥ 2. Let µ be the uniform distribution on S and define

a 0 ≔ (|S| -1) 1 -λ(2 -λ) 1 + λ(2 -λ) ≥ 0 ( 11
)
where λ ≔ λ(L) is the spectral gap of the random walk transition kernel defined in [START_REF] Lee | Centro-Hermitian and skew-centro-Hermitian matrices[END_REF]. Then under the framework described above, λ(M (a) ) is nondecreasing for a ∈ [0, a 0 ∧ 1] and nonincreasing on [a 0 ∧ 1, 1]. So the best choice of a ∈ [0, 1] to get the largest possible spectral gap

Λ ≔ max a∈[0,1] λ(M (a)
) is a = a 0 ∧ 1 and we have, if

a 0 ≤ 1, Λ = 1 -λ(2 -λ) 1 + λ(2 -λ) while if a 0 > 1, Λ = 1 - |S| 2(|S| -1)   1 -λ + |S| -2 |S| 2 -λ(2 -λ)   (12)
The example treated in Section 4 will show that when |S| = 2, the improvement of the spectral gap can be important and erases the diffusive effect which usually slows down the convergence to equilibrium of Monte-Carlo methods. Unfortunately, as soon as |S| ≥ 3, the improvement of the spectral gap is quite weak, as we will see in Section 5. In fact our analysis will also furnish all the eigenvalues of the operators M (a) , for a ∈ [0, 1], see Section 5 for details. When a 0 ≥ 1, Formula ( 12) is a particular case of a result due to Alon, Benjamini, Lubetzky and Sodin [START_REF] Noga Alon | Non-backtracking random walks mix faster[END_REF]: they consider a random walk on a connected, non bipartite and d-regular graph V , with d ≥ 3, whose spectral gap is still denoted by λ (be careful of the changes of notations with the article [START_REF] Noga Alon | Non-backtracking random walks mix faster[END_REF], what they call λ, ρ and d correspond here respectively to |S|(1λ), 1 -Λ and |S|), and they want to compare it with the second order random walk (X n ) n∈N which does not backtrack: at any time n ∈ N \ {0} and for any positions y, x n , x n-1 , ..., x 0 ,

P[X n+1 = y|X n = x n , ..., X 0 = x 0 ] = 1 d -1 ½ y∈N (xn)\{x n-1 }
where N (x n ) is the set of neighbors of x n (for n = 0, their convention is that P

[X 1 = y|X 0 = x 0 ] = 1 d ½ y∈N (x 0
) , but this is not very important). Then they show that whatever the initial condition, if

V is a Ramanujan graph (which means that λ ≤ 1 -2 √ d -1/d, namely a 0 ≥ 1), lim sup n→∞ max u∈V P[X n = u] - 1 n 1/n = 1 -Λ ( 13
)
where Λ is defined as in [START_REF] Pressman | Matrices with multiple symmetry properties: applications of centro-Hermitian and per-Hermitian matrices[END_REF] (the value given by this formula is attained for a = 1, so it does amount in our restricted framework to forbid backtracking, note also that our statement is slightly more precise, since we get the asymptotic rate of convergence for the couple (X n , X n+1 )). Their approach is completely different from ours and it is based on the recurrence relations satisfied by the numbers of nonbacktracking paths of a given length and going from a particular point to another particular point. These recurrence relations enable the authors to write explicitely the matrix of these numbers in terms of Chebyshev polynomials (applied to the adjacency matrix) and an asymptotic analysis of some linear combinations of these polynomials leads to [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF]. This result of Alon, Benjamini, Lubetzky and Sodin [START_REF] Noga Alon | Non-backtracking random walks mix faster[END_REF] is valid in a more general setting and its proof is more straightforward (admitting only a limited knowledge of Chebyshev polynomials) than ours, but they do not consider the case of weak forbidden backtracking (corresponding to 0 < a < 1), nor are they interested in the behavior of the whole spectrum. In particular, they are not always exhibiting a faster chain. But more important for us is the following conjecture, which cannot be stated for d-regular graph, since the sentence "keep going in the same direction" has then no (at least immediate) meaning.

Indeed, we believe that the qualitative part of Theorem 2 concerning the variation of the spectral gap could be extended to more general situations. More importantly, we think that it is always possible to strongly improve the spectral gap, under the assumptions of Theorem 2, by considering a more appropriate perturbation.

Conjecture 3 Let G be a finite Abelian group and S be a generating set of G with |S| ≥ 2. Let K (1) be the identity S × S matrix (seen as a speed transfer kernel, it forces to keep going always in the same direction) and consider again the interpolating kernels given in [START_REF] Maxwell | Central limit theorems for additive functionals of Markov chains[END_REF], as well as the associated second order Markov kernels M (a) for a ∈ [0, 1], which are also trajectorially reversible with respect to the probability measure m defined in [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF]. There exists a 0 ∈ [0, 1] such that λ(M (a) ) is nondecreasing for a ∈ [0, a 0 ] and nonincreasing on [a 0 , 1]. Furthermore there exists two values 0 < c 1 < c 2 (maybe depending on |S|), such that

c 1 λ(L) ≤ λ(M (a 0 ) ) ≤ c 2 λ(L)
The main interest of second order Markov chains is maybe that they enable to introduce a notion of speed in a discrete setting. In addition to the fact that a global reversibility property can be imposed to them, this feature could be the reason why they provide so good models for molecular dynamics as it was put forward by the results of Bacallado and Pande [START_REF] Bacallado | Bayesian analysis of higher-order, reversible, Markov chains[END_REF]. In this context, a general motivation for us was to investigate the possible spectral implications of the trajectorial reversibility assumption. The results presented here should be seen as first attempts in this direction.

The plan of the paper is as follows: in next section we will study the structure of second order Markov kernels and the trajectorial reversibility property, in the general case and in the positionspeed point of view for groups. In Section 3, we prove Theorem 1 and we present some links with the work of Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF]. In Section 4, we investigate the particular homogeneous example of the discrete circle Z N , with N ∈ N \ {0, 1}, when the set of allowed speeds is S = {-1, +1}. This will lead us to revisit the analysis of a similar model done by Diaconis, Holmes and Neal [START_REF] Diaconis | Analysis of a nonreversible Markov chain sampler[END_REF], see also Gade and Overton [START_REF] Kranthi | Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler[END_REF]. In Section 5, we extend these results to prove Theorem 2 and we give some examples.

Trajectorial reversibility

We investigate here the trajectorially reversible second order Markov kernels, in order to be able to easily perturb them in the sequel. Their structure is not without recalling the framework of differentiable manifolds, feature which should not be so surprising, since second order Markov chains should be seen as discrete position-speed Markov processes (at any time, the knowledge of the position and of the speed of the chain is sufficient to determine the law of the future of the trajectory). In the homogeneous Abelian group case, we also exhibit a skew Kronecker product property of the second order Markov kernels which simplifies their spectral decomposition.

Let M be a second order Markov kernel on a finite state space V as in the introduction. We want to characterize the fact that M is trajectory reversible with respect to some probability measure m on V 2 . As it was mentioned in the introduction, necessarily m is of the form (3), where L is reversible with respect to ν.

Let V ′ ≔ {x ∈ V : ν(x) > 0} be the support of ν. By reversibility, if x ∈ V ′ and x ′ ∈ V satisfies L(x, x ′ ) > 0, then x ′ ∈ V ′ . For x ′ ∈ V ′ , consider V ′ x ′ ≔ {x ∈ V ′ : L(x ′ , x) > 0}, and M x ′ the Markov kernel defined by ∀ x, x ′′ ∈ V, M x ′ (x, x ′′ ) ≔ M (x, x ′ ; x ′′ ) Let us check that the restriction of M x ′ to V ′ x ′ × V ′
x ′ is still a Markov kernel (which will also be denoted by M x ′ ). Indeed, the trajectorial reversibility of M with m can be written has

∀ x, x ′ ∈ V ′ , ∀ x ′′ ∈ V, ν(x ′ )L(x ′ , x)M x ′ (x, x ′′ ) = ν(x ′ )L(x ′ , x ′′ )M x ′ (x ′′ , x) (14)
so it appears that if x ∈ V ′ x ′ and x ′′ ∈ V ′ x ′ , then we have M x ′ (x, x ′′ ) = 0. Thus only what happens on V ′ is relevant: in the sequel we assume that V ′ = V and we remove the primes from the notations. By considering [START_REF] Weaver | Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors[END_REF] for x ′ ∈ V and x, x ′′ ∈ V x ′ and by dividing this identity by ν(x ′ ), it follows that the kernel M x ′ must be reversible with respect to the probability measure L(x ′ , •) on V x ′ . Let denote by R(L(x ′ , •)) the convex set consisting of the kernels on V x ′ which are reversible with respect to L(x ′ , •) and let R(L) be the "kernel-bundle" x∈V R(L(x ′ , •)) over V . The above arguments show the direct implication in the following characterization and the reverse implication is proven in the same way through [START_REF] Weaver | Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors[END_REF].

Lemma 4

The second order Markovian kernel M is trajectorially reversible with respect to m = ν × L if and only if (M x ) x∈V ∈ R(L), namely if M is a section of the bundle R(L) and from now on this will be indicated by the notation M ∈ R(L).

This result makes it clear that it is easy to perturbe a second order Markov kernel while keeping it trajectorially reversible with respect to a fixed measure m = ν × L, since this can be done independently in the different fibers of R(L). Note also that the particular second order Markov kernel M (0) considered in the introduction corresponds to the section (L(x, •)) x∈V ∈ R(L).

Contrary to reversibility, the notions of invariance, irreducibility and aperiodicity relative to second order Markovian kernel M will be the usual ones, when M is interpreted as a transition kernel from V 2 to V 2 , see [START_REF] Allen | Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process[END_REF]. Nevertheless usually V 2 is not an appropriate state space and we restrict M to a subset of V 2 , for instance in the previous situation the natural state space is {(x, x ′ ) ∈ V 2 : m(x, x ′ ) > 0} (or a recurrent component of this subset). We now check an assertion made in the introduction:

Lemma 5 If the second order Markovian kernel M is trajectorially reversible with respect to m, then m is invariant for M .

Proof

By definition a probability measure m on V 2 is invariant by M if

∀ (x ′ , x ′′ ) ∈ V 2 , x∈V m(x, x ′ )M (x, x ′ ; x ′′ ) = m(x ′ , x ′′ )
Equivalently, it means that for any F ∈ F(V 2 ),

E[F (X 1 , X 2 )] = E[F (X 0 , X 1 )] (15)
where (X n ) n∈N is a second order Markov chain with M as kernel and starting from the initial distribution m. But if m is reversible, we have

E[F (X 1 , X 2 )] = E[F (X 1 , X 0 )] = E[F (X 0 , X 1 )]
where the second equality comes from the symmetry of m.

Remark 6 One can give a characterization similar to Lemma 4 of second order Markov kernels which leave a measure m invariant. First note that if m is left invariant by a second order Markov kernel M , then its marginals on the first and second factor of V 2 are equal. Indeed, just apply (15) to a function F only depending on the first variable. Let us call ν this common marginal distribution on V and as before assume that its support is V . Let L 1 and L 2 the Markov kernels defined by

∀ x, x ′ ∈ V, m(x, x ′ ) = ν(x)L 2 (x, x ′ ) = ν(x ′ )L 1 (x ′ , x)
(ν is invariant by L 1 and L 2 ). As above, represent M as a family of Markov kernels (M x ) x∈V . It follows from the invariance of m by M , that for any x ∈ V , M x can be seen as a Markov kernel from V - x to V + x , where

V - x ≔ {x ′ ∈ V : m(x ′ , x) > 0} V + x ≔ {x ′ ∈ V : m(x, x ′ ) > 0}
Then it is not difficult to see that m is invariant for M if and only if for any x ∈ V , M x transports the probability measure L 1 (x, •) into the probability measure L 2 (x, •). In particular Lemma 4 enables to see that a probability measure m is trajectorially reversible with respect to M if and only it is invariant and symmetric.

Assume again that the second order Markov kernel M is trajectorially reversible with respect to m and consider M * the dual operator of M in L 2 (m). Since m is invariant for M , it is well-known that M * is Markovian in the abstract sense: it is nonnegativity preserving and the function ½ taking everywhere the value 1 is preserved. But as we compute it in next result, in general M * has not the form of a second order Markov kernel: Lemma 7 Define the tilde operation on F(V 2 ) as the exchange of coordinates:

∀ F ∈ F(V 2 ), ∀ x, x ′ ∈ V, F (x, x ′ ) ≔ F (x ′ , x)
Then we have

∀ F ∈ F(V 2 ), M * [F ] = M [ F ]
or more explicitely,

∀ x, x ′ ∈ V, M * [F ](x, x ′ ) = x ′′ ∈V M (x ′ , x; x ′′ )F (x ′′ , x)
Proof Consider again (X n ) n∈N a second order Markov chain with M as kernel and starting from the initial distribution m. For any F, G ∈ F(V 2 ), we have

m[F M [G]] = E[F (X 0 , X 1 )G(X 1 , X 2 )] = E[F (X 2 , X 1 )G(X 1 , X 0 )] = E[ G(X 0 , X 1 ) F (X 1 , X 2 )] = E[ G(X 0 , X 1 )M [ F ](X 0 , X 1 )] = m[ GM [ F ]] = m[ GM [ F ]] = m[G M [ F ]]
where the last but one equality comes from the symmetry of m.

We now come to the situation where the state space is a group G and we consider the family of Markov kernels (K x ) x∈G associated to M as in [START_REF] Kato | Perturbation theory for linear operators[END_REF]. In addition define the Markov kernels

∀ x, y, y ′ ∈ G, K x (y, y ′ ) ≔ K x (y -1 , y ′ )
which will be called the modified speed kernels associated to M . If a symmetric probability measure m = ν × L is given on V 2 with ν giving a positive mass to all the elements of G, we consider the family of probability distributions ( µ x ) x∈G given by ∀ x, y ∈ G, µ x (y) ≔ L(x, xy)

Then Lemma 4 leads to the following result:

Lemma 8 The second order Markovian kernel M is trajectorially reversible with respect to the symmetric distribution m if and only if for any x ∈ G, K x is reversible with respect to µ x . If furthermore the kernels K x do not depend on x ∈ G and admit a unique recurrence class S which generates G, then ν is the uniform distribution and L is the Markov kernel of the random walk on G whose increments follow the symmetric law µ on S which is reversible with respect to K.

Proof

The first part follows immediately from the fact that

∀ x, y, y ′ ∈ G, K x (y, y ′ ) = M x (xy, xy ′ )
For the second part, assume that for all x ∈ G, K x = K, where K admits a unique recurrence class S which generates G and that K is reversible with respect to a probability measure µ. Then the support of µ is S and by uniqueness of the invariant measure on a recurrence class, we have

∀ x, x ′ ∈ G, L(x, x ′ ) = µ x (x -1 x ′ ) = µ(x -1 x ′ )
So it appears that L is the Markov kernel of the random walk on G whose increments follow the law µ. Since S generates G, L is irreducible and admits a unique invariant probability measure which is necessarily the uniform distribution ν, because, as L, it must be invariant by translations. By reversibility of ν with respect to L, we get that µ is symmetric:

∀ y ∈ S, µ(y -1 ) = µ(y)
and in particular S must be symmetric.

Note that in practice, it is convenient to rather start with a Markov kernel K reversible with respect to a symmetric probability measure µ. It is then immediate to check that the associated second order Markov kernel M defined by

∀ x, x ′ , x ′′ ∈ G, M (x, x ′ ; x ′′ ) ≔ K((x ′ ) -1 x, (x ′ ) -1 x ′′ )
is trajectorially reversible with respect to the measure m defined by

∀ x, x ′ ∈ G, m(x, x ′ ) = 1 |G| µ(x -1 x ′ )
The second order Markov kernel M will then be said to be (spatially) homogeneous (this situation can be extended to state spaces which are not groups, under appropriate homogeneity assumptions, but we won't enter in the description of such a setting here).

Remark 9

In general K may have several recurrent classes and the link with the recurrent classes of M is not so clear. Consider for instance the case where G = Z N , with N ∈ N \ {0, 1} and where the modified speed kernel K is given by the matrix

1 2 0 1 1 0 on the set S ≔ {-1, 1} ⊂ Z N .
The speed kernel K is then the identity kernel, which means that once a speed has been chosen in {-1, 1}, it will never change. So M has two recurrent classes:

{(x, x -1) : x ∈ Z N } and {(x, x + 1) : x ∈ Z N }.
Conversely, if we take for K the identity matrix, then all the sets of the form {(x, x + 1), (x + 1, x)}, where x ∈ Z N , are recurrent classes for M . Indeed, even the link between the recurrent classes of K and those of K can be quite involved. Nevertheless, if a set I is symmetric and invariant for K (namely x ∈ I and y ∈ I imply that K(x, y) = 0), then it is also invariant for K.

We now concentrate on the homogeneous case. We will always denote by S the support of the measure µ entering in the definition of this situation. The transition kernels K and K will be understood as S × S matrices. Without loss of generality, we assume that G is generated by S (replace otherwise G by the subgroup generated by S). By considering the change of variables

G 2 ∋ (x, x ′ ) → (x, y) ≔ (x, x -1 x ′ ) ∈ G 2
we transform the transition kernel M of the Markov chain (X n , X n+1 ) n∈N into the position-speed variables transition kernel P given in [START_REF] Horn | Matrix analysis[END_REF]. Note that the natural state space for this kernel is rather

G × S instead of G 2 .
In the next result we exhibit the spectral decomposition of kernels whose structure generalizes that of P .

Proposition 10 Let S and V be finite sets with respective cardinals s and v. Let K be a S × S matrix and for any y ∈ S, let Q y be a V × V matrix. Assume there is a basis (ϕ l ) l∈ v of F(V, C) consisting of eigenfunctions for Q y , independent of y ∈ S (where v ≔ {1, 2, ..., v}). The corresponding eigenvalues are allowed to depend on y ∈ S and are denoted by (σ l (y)) l∈ v . For fixed l ∈ v , consider K l the S × S matrix defined by

∀ y, y ′ ∈ S, K l (y, y ′ ) ≔ σ l (y)K(y, y ′ )
Assume that it is diagonalizable (in C) and denote by (θ l,k ) k∈ s and (ψ l,k ) k∈ s its eigenvalues and corresponding eigenvectors.

Next consider P the (V × S) × (V × S) matrix defined by

∀ (x, y), (x ′ , y ′ ) ∈ V × S, P ((x, y), (x ′ , y ′ )) = K(y, y ′ )Q y (x, x ′ ) (this is the skew Kronecker product of Q by K). Then P is diagonalizable, its eigenvalues are the θ l,k for (l, k) ∈ v × s and a corresponding family of eigenvectors is (ϕ l ⊗ ψ l,k ) (l,k)∈ v × s .

Proof

This result is in fact more difficult to state than to prove. For (l, k) ∈ v × s , consider F l,k ≔ ϕ l ⊗ ψ l,k . Since the family (ϕ l ) l∈ v is linearly independent and the same is true for the family (ψ l,k ) k∈ s for any fixed l ∈ v , the family (F l,k ) (l,k)∈ v × s is also linearly independent and is thus a basis of F(V × S, C). Next for given (l, k) ∈ v × s and (x, y) ∈ V × S, we compute that

P [F l,k ](x, y) = x ′ ∈V,y ′ ∈S K(y, y ′ )Q y (x, x ′ )F l,k (x ′ , y ′ ) = y ′ ∈S K(y, y ′ )ψ l,k (y ′ ) x ′ ∈V Q y (x, x ′ )ϕ l (x ′ ) = y ′ ∈S K(y, y ′ )ψ l,k (y ′ )σ l (y)ϕ l (x) = ϕ l (x) y ′ ∈S K l (y, y ′ )ψ l,k (y ′ ) = ϕ l (x)θ l,k ψ l,k (y) = θ l,k F l,k (x, y)
so F l,k is an eigenvector for the eigenvalue θ l,k relatively to P .

Coming back to our homogeneous setting, we would like to apply the above proposition with V = G and the translation kernels (Q y ) y∈S defined by

∀ x, x ′ ∈ G, Q y (x, x ′ ) ≔ δ xy (x ′ )
If they were jointly diagonalizable, they would commute and since G is generated by S, we would end up with

∀ y, y ′ ∈ G, Q y Q y ′ = Q y ′ Q y
and these identities imply that G is Abelian. Conversely, if G is Abelian, then we can find r ∈ N\{0} and N 1 , ..., N r ∈ N \ {0, 1} such that G is isomorphe to the group product l∈ 1,r Z N l , so a generical element x ∈ G will be written under the form (x l ) l∈ 1,r , with

x l ∈ Z N l for l ∈ r . For k = (k l ) l∈ 1,r ∈ l∈ 1,r 0, N l -1 , consider the mapping ρ k ∈ F(G, C) defined by ∀ x = (x l ) l∈ 1,r ∈ G, ρ k (x) = exp   2πi l∈ 1,r k l x l /N l   Since the mappings ρ k , for k ∈ l∈ 1,r 0, N l -1 , correspond to the irreducible representations of G, we get that for any y ∈ S, Q y [ρ k ] = ρ k (y)ρ k So it appears that (ρ k ) k∈ l∈ 1,r 0,N l -1 is a basis of F(G, C
) which enables to simultaneously diagonalize the Q y , for y ∈ S, and we are in position to exploit Proposition 10. To do so conveniently, we introduce some notations:

G * ≔    ρ k : k ∈ l∈ 1,r 0, N l -1    ( 16
)
and for ρ ∈ G * , △(ρ) is the S × S diagonal matrix whose diagonal entries are given by (ρ(y)) y∈S .

We also consider the S × S matrix A ρ ≔ △(ρ)K. Then Proposition 10 implies the following result:

Proposition 11 Let G be a finite Abelian group and M a homogeneous second order Markov kernel on G with speed transfer matrix K. If all the matrices A ρ , with ρ ∈ G * , are diagonalizable, then M is diagonalizable and its spectrum is the union of the spectra of the A ρ , with ρ ∈ G * (with multiplicities).

One can go further: if one of the matrices A ρ is not diagonalizable, one can consider its decomposition into Jordan blocks and an immediate extension of Proposition 10 enables to transfer these Jordan blocks into Jordan blocks for M . In particular the spectrum of M is always the union of the spectra of the A ρ , with ρ ∈ G * (with obvious relations between the dimensions of the corresponding Jordan blocks). These observations do not require M to be trajectorially reversible, but we believe that the latter property could be helpful to understand the spectral structure of the matrices A ρ , with ρ ∈ G * . Nevertheless this reversibility condition won't be sufficient to insure that they are diagonalizable, even under the stronger assumption made in Lemma 12 below (see Section 4).

We end this section with a discussion of the structural properties which can be deduced from a natural reinforcement of the trajectorial reversibility. Indeed, let M be a trajectorially reversible homogeneous second order Markov kernel, with modified speed kernel K reversible with respect to µ. By definition of K, we have for any y, y ′ ∈ S, µ(y)K(-y, y ′ ) = µ(y ′ )K(-y ′ , y), so taking into account the symmetry of µ, we get µ(-y)K(-y, y ′ ) = µ(-y ′ )K(-y ′ , y). Summing over y ′ ∈ S, it follows that µ(-y) = µK(-y), namely µ is invariant for K. So the assumption of the next result is not so farfetched, note that it is in particular satisfied by the families of examples considered in Theorem 2 and Conjecture 3.

Lemma 12 Assume that µ is also reversible with respect to K, then the matrices A ρ , with ρ ∈ G * , are conjugate to symmetric and centro-Hermitian matrices.

Recall that a S × S matrix B (where S is a symmetrical set) is said to be centro-Hermitian if B = B, where ∀ y, y ′ ∈ S, B(y, y ′ ) ≔ B(-y, -y ′ ) see for instance Lee [START_REF] Lee | Centro-Hermitian and skew-centro-Hermitian matrices[END_REF] or Pressman [START_REF] Pressman | Matrices with multiple symmetry properties: applications of centro-Hermitian and per-Hermitian matrices[END_REF]. Weaver [START_REF] Weaver | Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors[END_REF] gave a nice review of the corresponding notion of a (real) centro-symmetric matrix, property which is satisfied by the speed transition kernel under the above assumption.

Proof

Under the hypothesis of this lemma, we simplify the notations and write µ instead of µ. For ρ ∈ G * , let ρ 1/2 ≔ (ρ 1/2 (y)) y∈S be a vector of square roots of (ρ(y)) y∈S , chosen in such a way that ρ 1/2 (-y) = ρ 1/2 (y) (recall that we have ρ(-y) = ρ(y) and that this complex number has modulus 1). Define next

B ρ ≔ △( √ µρ -1/2 )A ρ △(ρ 1/2 / √ µ) = △( √ µρ 1/2 )K△(ρ 1/2 / √ µ) (17)
(where for any vector v, △(v) is the diagonal matrix with corresponding entries). Since A ρ is conjugate to B ρ , both matrix have the same spectral structure, but B ρ has two practical advantages: is is symmetric and centro-Hermitian. Indeed, we have

∀ y, y ′ ∈ S, B ρ (y, y ′ ) = µ(y) µ(y ′ ) K(y, y ′ )ρ 1/2 (y)ρ 1/2 (y ′ )
so the symmetry of B ρ is a consequence of the reversibility of K with respect to µ. The centro-Hermitian property comes from the fact that

∀ y ∈ S, µ(-y) = µ(y) and ρ 1/2 (-y) = ρ 1/2 (y)
A consequence of the above result is that the spectrum of A ρ , for ρ ∈ G * , is stable by conjugacy, since this is true for any centro-Hermitian matrix B (see for instance Lee [START_REF] Lee | Centro-Hermitian and skew-centro-Hermitian matrices[END_REF]): to any f = (f (y)) y∈S ∈ F(S, C) (seen as a column vector), associate the vector f ≔ (f (-y)) y∈S ∈ F(S, C).

An immediate computation shows that

∀ f ∈ F(S, C), Bf = B f
Thus if B is centro-Hermitian and if f is an eigenvector of B associated to eigenvalue θ ∈ C, then f is an eigenvector of B associated to eigenvalue θ.

Note that we knew a priori that the spectrum of M is stable by conjugacy, because its entries are real. But this property corresponds to the fact that the spectrum of A ρ is conjugate to the spectrum of A ρ = A ρ , for any ρ ∈ G * . This leads to the following observation: if θ is a non-real eigenvalue of A ρ , with ρ = ρ ∈ G * , then its multiplicity as an eigenvalue of M is at least the double of its multiplicity as an eigenvalue of A ρ .

Remark 13 In view of the above considerations, it is not clear how to deduce spectral informations from the trajectorial reversibility assumption. Nevertheless in the homogeneous case, one can use it to deduce information on the convergence to equilibrium in the following way. For simplicity consider the Abelian case. Let (X n , Y n ) n∈N be the position-speed Markov chain associated to the second order Markov kernel M , whose modified speed kernel is denoted K as above. Consider the Markov chain ( Y n ) n∈N defined by

∀ n ∈ N, Y n ≔ (-1) n Y n
This chain has K as transition kernel and thus is reversible with respect to µ, so to understand its convergence to equibrium, we can resort to the usual spectral techniques. The chain (X n , Y n ) n∈N can be deduced from ( Y n ) n∈N via a deterministic procedure: for any n ∈ N, we have

X n = Y 0 -Y 1 + Y 2 -• • • + (-1) n-1 Y n-1 Y n = (-1) n Y n
So (X n ) n∈N appears as a time-inhomogeneous, but periodic, additive functional of ( Y n ) n∈N . To come back to the situation of a time-homogeneous functional, it is better to consider the Markov chain ( Y 2n , Y 2n+1 ) n∈N , whose convergence to equilibrium can easily be deduced from that of ( Y n ) n∈N . Then one can resort to the well-known large time behavior of additive functionals (see for instance Maxwell and Woodroofe [START_REF] Maxwell | Central limit theorems for additive functionals of Markov chains[END_REF] and the references given therein), at least on the covering lattice of G, based on the central limit theorem for martingales. Next it remains to "project" this result on G: once the variance enables to cover a fundamental domain for G, the stochastic chain (X n ) n∈N will be close to equilibrium, namely uniformly distributed. But we won't developp this approach here, because it is not in the spirit of the paper.

Infinitesimal improvement of spectrum

Our purpose here is to show that the spectral gap (and even the whole spectrum outside 0) of a reversible Markov chain can always been improved (except in the situation of an i.i.d. sequence) by resorting to related second order Markov chains, which "have a little less tendency to hesitate in their way to equilibrium" than the original chain. The rigorous formulation of this heuristic is enclosed in Theorem 1, and this section is mainly devoted to his proof. But we will also investigate the best way to improve only the spectral gap, when the underlying first order kernel L is the transition matrix of a random walk on a regular graph and under an additional assumption of multiplicity one for the spectral gap.

Our starting point is a Markov kernel L which admits a reversible probability measure ν, positive on the finite set V . Since we will only be interested in second order Markov chains which are trajectorially reversible with respect to the probability measure ν × L (defined in (3)), up to a restriction of the state space V , there is no loss of generality in assuming that L is furthermore irreducible. We associate to L the second order Markov kernel M (0) defined in [START_REF] Kranthi | Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler[END_REF]. We begin by verifying an assertion made in the introduction: Proposition 14 The spectrum of the transition operator M (0) is equal to the spectrum of L with the same multiplicities, except for the eigenvalue 0, whose multiplicity is N 2 -N , where N = |V |.

In particular M (0) is diagonalizable if and only if 0 is not an eigenvalue of L. When 0 is an eigenvalue of L, let d be the dimension of the corresponding eigenspace. Then the canonical form of M (0) contains d 2 × 2-Jordan blocks 0 1 0 0 .

It follows that (M (0) ) 2 is always diagonalizable. This is not true for M (0) , as we will see on an example in next section.

Proof

Since ν has positive weight everywhere and is reversible with respect to L, the latter operator is diagonalizable in R. Let (θ i ) i∈ N be its spectrum and (f i ) i∈ N be a corresponding family of eigenvectors. For i ∈ N , define

F i ∈ F(V 2 ) by ∀ (x, x ′ ) ∈ V 2 , F i (x, x ′ ) ≔ f i (x ′ )
We compute that for any (x, x ′ ) ∈ V 2 ,

M (0) [F i ](x, x ′ ) = x ′′ ∈V M (x, x ′ ; x ′′ )F i (x ′ , x ′′ ) = x ′′ ∈V L(x ′ , x ′′ )f i (x ′′ ) = L[f i ](x ′ ) = θ i f i (x ′ ) = θ i F i (x, x ′ )
so that F i is an eigenfunction associated to the eigenvalue θ i with respect to M (0) . We denote by F the vector space generated by the functions F i , with i ∈ N . It is in fact the subspace of F(V 2 ) consisting of functions only depending on the second variable. Let us also denote by F ′ the subspace of F generated by the functions F i , with i ∈ N satisfying θ i = 0. Next for x 0 ∈ V , consider F x 0 the space of functions F from F(V 2 ) which can be written under the following form

∀ (x, x ′ ) ∈ V 2 , F (x, x ′ ) = δ x 0 (x)f (x ′ ) where f ∈ F(V ) satisfies L[f ](x 0 ) = 0. For such a function F ∈ F x 0 , we compute that for any (x, x ′ ) ∈ V 2 , M (0) [F ](x, x ′ ) = x ′′ ∈V L(x ′ , x ′′ )F (x ′ , x ′′ ) = δ x 0 (x ′ ) x ′′ ∈V L(x ′ , x ′′ )f (x ′′ ) = δ x 0 (x ′ )L[f ](x 0 ) = 0
so that F is an eigenfunction associated to the eigenvalue 0 with respect to M (0) . Next consider F ′′ the subspace of F(V 2 ) generated by all the F x 0 , with x 0 ∈ V . By the above computation, F ′′ is included in the eigenspace associated to the eigenvalue 0 of M (0) . Clearly the subspaces F x 0 , for x 0 ∈ V , are mutually linearly independent, since the corresponding functions vanish on disjoint sets. Furthermore the mapping

F(V ) ∋ f → L[f ](x 0
) is a non degenerate linear form, so the dimension of F x 0 is N -1. Thus we get that the dimension of F ′′ is N 2 -N . Note that the dimension of F is N , so M (0) would be diagonalizable if we had F ∩ F ′′ = {0}. But in general, we only have F ∩ F ′′ = F ′ . Indeed, let F ∈ F ∩ F ′′ , we can find some coefficients (a x 0 ) x 0 ∈V and some functions f x 0 ∈ F x 0 , for x 0 ∈ V , such that

F = x 0 ∈V a x 0 δ x 0 ⊗ f x 0
Further there exists f ∈ F(V ) such that

∀ (x, x ′ ) ∈ V 2 , F (x, x ′ ) = f (x ′ ) = a x f x (x ′ )
It follows that for any x ∈ V ,

L[f ](x) = a x L[f x ](x) = 0 so that F ∈ F ′ . Conversely, if F ∈ F ′ , just choose a x 0 = 1 and f x 0 = f for all x 0 ∈ V in the above description to see that F ∈ F ′′ and by consequence F ∈ F ∩ F ′′ .
Thus in general, we have only found N 2d independent eigenvectors for M (0) . For i ∈ N , with

θ i = 0, consider the function G i ∈ F(V 2 ) defined by ∀ (x, x ′ ) ∈ V 2 , G i (x, x ′ ) ≔ f i (x)
We compute that for any (x, x ′ ) ∈ V 2 ,

M (0) [G i ](x, x ′ ) = x ′′ ∈V M (x, x ′ ; x ′′ )G i (x ′ , x ′′ ) = x ′′ ∈V L(x ′ , x ′′ )f i (x ′ ) = f i (x ′ ) = F i (x, x ′ )
Thus the 2-dimensional vector space generated by F i and G i is stable by M (0) and the matrix associated to the operator M (0) in the basis (G i , F i ) is the 2 × 2-Jordan block 0 1 0 0 . The announced results follow at once.

In the above proof the reversibility of L was not really necessary, it was sufficient to assume that it is diagonalizable. One can even go further by revisiting the above proof:

Remark 15 Let L be any Markov kernel on S and construct the kernel M (0) as in [START_REF] Kranthi | Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler[END_REF]. Then as above the spectrum of M (0) is equal to the spectrum of L plus the value 0. More precisely, the Jordan blocks associated to an eigenvalue θ = 0 of L are in exact correspondance with those of M (0) . Concerning the eigenvalue 0, let d be the number of 1 × 1-Jordan blocks for L. All of them are transformed into 2 × 2 blocks for M (0) . But for r ≥ 2, all the r × r-Jordan blocks of L are transformed into r × r-Jordan blocks for M (0) . And there is furthermore the creation of N 2 -Nd

1 × 1-Jordan blocks for M (0) . This comes from the fact that the (r + 1) × (r + 1) matrix A defined by

∀ i, j ∈ r + 1 , A(i, j) ≔    1 , if j = i + 1 and i ∈ r -1 1
, if i = 0 and j = r + 1 0 , otherwise admits a decomposition into a 1 × 1 block and a r × r block (both associated to the eigenvalue 0).

In Proposition 14 we have considered the spectrum of M (0) as an operator on F(V 2 ), but in general we are only interested on its action on a subspace of F(V 2 ): since the probability measure ν × L is invariant for M (0) , we prefer to see M (0) as an operator on L 2 (ν × L), whose dimension is the cardinal of the set {(x, y) ∈ V 2 : L(x, y) > 0}. By our assumption ν > 0, we have

F(V ) = L 2 (ν)
and there is no ambiguity for the spectrum of L. The proof of Proposition 14 can then be extended to this situation: the spectrum of M (0) is the spectrum of L plus maybe the eigenvalue 0. Indeed the eigenvalue 0 is necessary in the spectrum of M (0) if dim(L 2 (ν × L)) > N . Note that under our reversibility and irreducibility assumptions on L, the only situations when this inegality is not satisfied is when |V | = 1 or |V | = 2 and L is given by the matrix 0 1 1 0 . Similar observations also hold in the more general setting of the above remark (but assume furthermore that L is irreducible, so that it admits a unique positive invariant measure).

In order to go in the direction of Theorem 1, consider a second order Markov kernel M (1) admitting ν × L as trajectorial reversible measure and satisfying for any x, x ′ , x ′′ ∈ V ,

M (1) (x, x ′ ; x ′′ ) > L(x ′ , x ′′ ) , if x ′′ = x, L(x, x ′ ) > 0 and L(x ′ , x ′′ ) > 0 (18)
Such transition kernels exists, since according to Lemma 4, the only requirement is that for any fixed x ′ ∈ V , the kernel (M

x ′ (x, x ′′ )) x,x ′′ ∈V is reversible with respect to the probability L(x ′ , •). Next, as in the introduction, for any a ∈ [0, 1], we consider the interpolation kernel between M (0) and M (1) : (1) which is a second order Markov kernel still admitting ν × L as trajectorial reversible measure. We need some information about the behavior of the spectral decomposition of M (a) as a function of a, at least for small a. From Chapter 2 §1.8 of Kato [START_REF] Kato | Perturbation theory for linear operators[END_REF], we easily deduce the following result:

M (a) ≔ (1 -a)M (0) + aM
Lemma 16 There exists a 0 ∈ (0, 1) such that the number s of distinct eigenvalues of M (a) does not depend on a ∈ (0, a 0 ). It is possible to parameterize these eigenvalues by (θ l (a)) l∈ s in such a way that for any l ∈ s , the mapping (0, a 0 ) ∋ a → θ l (a) is analytical. Furthermore these mappings admit continuous extension to [0, a 0 ) and the set {θ l (0) : l ∈ s } coincides with the spectrum of M (0) (note nevertheless that the cardinal of this spectrum can be stricly less than s, when occurs a splitting phenomenon of some eigenvalues at 0). Moreover for any l ∈ s , we can find a continuous mapping [0, a 0 ) ∋ a → F l (a) ∈ F(V 2 , C) \ {0} such that for any a ∈ [0, a 0 ), F l is an eigenfunction associated to the eigenvalue θ l (a) of M (a) , and such that the mapping (0, a 0 ) ∋ a → F l (a) ∈ F(V 2 , C) \ {0} is analytical.

In fact the above lemma holds for general second order Markov kernel M (1) . But the assumption (18) is need for the next result.

Proposition 17 With the notations introduced in the previous lemma, assume that l ∈ s is such that θ l (0) = 0. Then the limit lim a→0 + θ ′ l (a) exists and belongs to R. By consequence θ ′ l (0) exists and coincides with the previous limit. Furthermore if

|θ l (0)| = 1, then the sign of θ ′ l (0) is the opposite sign of θ l (0) (recall that θ l (0) ∈ R \ {0}). If |θ l (0)| = 1, we have θ ′ l (0) = 0.
Proof By definition, we have for any a ∈ [0, a 0 ),

M (a) F l (a) = θ l (a)F l (a)
and we can differentiate this equality for a ∈ (0, a 0 ) to get

(M (1) -M (0) )F l (a) + M (a) F ′ l (a) = θ ′ l (a)F l (a) + θ l (a)F ′ l (a) (19)
where the primes represent differentiation with respect to a ∈ (0, a 0 ). Our goal is to get rid of the term F ′ l (a) that we don't control as a is going to 0 + . Lemma 7 implies that the fonction F l (a) defined over there is an eigenvector of (M (a) ) * associated to the eigenvalue θ(a). Indeed, we have

(M (a) ) * [ F l (a)] = M (a) [F l (a)] = θ(a)F l (a) = θ(a) F l (a)
Multiply ( 19) by F l (a) and integrate the obtained equation with respect to m, to get

m[ F l (a)(M (1) -M (0) )F l (a)] + m[ F l (a)M (a) F ′ l (a)] = θ ′ l (a)m[ F l (a)F l (a)] + θ l (a)m[ F l (a)F ′ l (a)]
By definition of the dual operator (M (a) ) * we have

m[ F l (a)M (a) F ′ l (a)] = m[(M (a) ) * [ F l (a)]F ′ l (a)] = θ(a)m[ F l (a)F ′ l (a)]
Thus we deduce the following equation where the term F ′ l (a) has disappeared:

m[ F l (a)(M (1) -M (0) )F l (a)] = θ ′ l (a)m[ F l (a)F l (a)]
We can now use the continuity properties put forward in Lemma 16 to see that

lim a→0 + m[ F l (a)(M (1) -M (0) )F l (a)] = m[ F l (0)(M (1) -M (0) )F l (0)] lim a→0 + m[ F l (a)F l (a)] = m[ F l (0)F l (0)]
so the limit lim a→0 + θ ′ l (a) exists if we have m[ F l (0)F l (0)] = 0. To compute this term, we note that since F l (0) is an eigenvector of M (0) associated to the eigenvalue θ l (0), according to the proof of Proposition 14, there exists an eigenfunction f ∈ F(V ) of M (0) associated to the eigenvalue θ l (0) such that

∀ x, x ′ ∈ V, F l (0)(x, x ′ ) = f (x ′ ) It follows that m[ F l (0)F l (0)] = x,x ′ ∈V ν(x)L(x, x ′ )f (x)f (x ′ ) = ν[f L[f ]] = θ l (0)ν[f 2 ]
which is different from 0. Thus lim a→0 + θ ′ l (a) exists and by consequence the mapping [0, a 0 ) ∋ a → θ l (a) is differentiable at 0 and θ ′ l (0) = lim a→0 + θ ′ l (a). To evaluate this derivative, it remains to compute

m[ F l (0)(M (1) -M (0) )F l (0)] = x,x ′ ∈V ν(x)L(x, x ′ )f (x) x ′′ ∈V D x ′ (x, x ′′ )f (x ′′ ) ( 20
)
where for any x, x ′ , x ′′ ∈ V , we have defined

D x ′ (x, x ′′ ) ≔ M (1) x ′ (x, x ′′ ) -M (0) x ′ (x, x ′′ ) = M (1) (x, x ′ ; x ′′ ) -L(x ′ , x ′′ )
These quantities are real, so we already get that θ ′ l (0) ∈ R. To go further, note that for any x ′ ∈ V , D x ′ is a generator matrix: outside the diagonal its entries are nonnegative (even positive in the present case) and the sum of the entries of any row is zero. Furthermore this matrix is reversible (in the usual sense) with respect to the (row) vector (L(x ′ , x)) x∈V . It is then easy to see that (cf. for instance the lecture notes of Saloff-Coste [START_REF] Saloff-Coste | Lectures on finite Markov chains[END_REF])

x,x ′′ ∈V L(x ′ , x)D x ′ (x, x ′′ )f (x)f (x ′′ ) = - 1 2 x =x ′′ ∈V L(x ′ , x)D x ′ (x, x ′′ )(f (x ′′ ) -f (x)) 2 ≤ 0
Since by reversibility of L the r.h.s. of (20) can also be written as

x ′ ∈V ν(x ′ ) x,x ′′ ∈V L(x ′ , x)D x ′ (x, x ′′ )f (x)f (x ′′ )
it appears that m[ F l (0)(M (1) -M (0) )F l (0)] ≤ 0 and by consequence θ l (0)θ ′ l (0) ≤ 0. Let us now consider the situation where θ l (0)θ ′ l (0) = 0. According to the previous computations, this is equivalent to the fact that

∀ x, x ′ , x ′′ ∈ V, D x ′ (x, x ′′ )(f (x ′′ ) -f (x)) = 0
namely, for any x, x ′ , x ′′ ∈ V such that D x ′ (x, x ′′ ) = 0, we must have f (x ′′ ) = f (x). Due to our assumption (18), this amounts to the condition that for any x = x ′′ ∈ V such that there exists x ′ ∈ V with L(x, x ′ ) > 0 and L(x ′ , x ′′ ) > 0 (inequalities which are equivalent to M (1) (x, x ′ ; x ′′ ) > 0), we must have f (x ′′ ) = f (x). This is equivalent to the fact that f must be constant on the recurrence classes of L 2 , namely L 2 [f ] = f . Thus, since L[f ] = θ l (0)f , this means that θ 2 l (0) = 1, hence the announced results.

We can now come to the

Proof of Theorem 1

Since L is assumed to be irreducible, the eigenspace associated to the eigenvalue 1 is just Vect(½), so that 1 ∈ Θ * (L). Furthermore -1 ∈ Θ * (L), otherwise L would be periodic, thus we have λ(L) > 0. On the other hand, as it was mentioned in the introduction, the condition that L = ν insures that λ(L) = 1, so in fact λ(M (0) ) ∈ (0, 1). With the notations of Lemma 16, define

I ≔ {l ∈ s : |θ l (0)| = 1 -λ(L)}
By continuity of the eigenvalues of M (a) as functions of a, we can find a ′ 0 ∈ (0, a 0 ) such that

∀ a ∈ [0, a ′ 0 ], λ(M (a) ) = max{1 -|θ l (a)| : l ∈ I}
By considering a first order expansion at 0 + of the functions θ l , for l ∈ I, Proposition 17 easily implies that [0, 1] ∋ a → λ(M (a) ) is differentiable at 0 and that

dλ(M (a) ) da (0) = min{ θ ′ l (a) : l ∈ I} > 0
Next consider the situation where instead of infinitesimally improving the nonnull part of the spectrum of M (0) , we just want to improve its spectral gap. What is the best way to do it, at least infinitesimally? More precisely, let D be the set of signed kernels D = (D(x, x ′ ; x ′′ ) x,x ′ ,x ′′ ∈V from V 2 to V , such that for ǫ > 0 small enough, M (0) + ǫD is a second order Markov kernel which is trajectorially reversible with respect to ν × M and such that the following normalization condition is satisfied:

∀ x, x ′ ∈ V, x ′′ ∈V D(x, x ′ ; x ′′ ) ≤ 2
As above, we can show that λ(M (0) + ǫD) is differentiable at the right of 0 and we are wondering what are the perturbations D † ∈ D which maximize the improvement of the spectral gap, namely such that

d dǫ λ(M (0) + ǫD † ) ǫ=0 = sup D∈D d dǫ λ(M (0) + ǫD) ǫ=0 (21)
To simplify the analysis of this problem, assume that there is only one eigenvalue θ of L such that λ(L) = 1 -|θ| (θ can be positive or negative) and that the multiplicity of θ is 1. By a slight misuse of language, in this situation we will say that the spectral gap is of multiplicity 1. Let f ∈ F(V ) be an associated eigenfunction (different from 0). To any signed kernel D from V 2 to V , associate the family (D x ′ ) x ′ ∈V of signed kernels from V to V defined by

∀ x ′ , x, x ′′ ∈ V, D x ′ (x, x ′′ ) ≔ D(x, x ′ ; x ′′ )
For fixed x ′ ∈ V , let D x ′ be the set of signed kernels (D(x, x ′′ )) x,x ′′ ∈V from V to V which are reversible with respect to L(x ′ , •) (i.e. ∀ x, x ′′ ∈ V, L(x ′ , x)D(x, x ′′ ) = L(x ′ , x ′′ )D(x ′′ , x)) and which satisfy x ′′ ∈V |D(x, x ′ ; x ′′ )| ≤ 2 and x ′′ ∈V D(x, x ′′ ) = 0 for all x ∈ V . It is easy to check (see the proof of Lemma 4) that D ∈ D if and only if D x ′ ∈ D x ′ for all x ′ ∈ V . Define for any x ′ ∈ V , the mapping H x ′ : D x ′ → R via the formula

∀ D = (D(x, x ′′ )) x,x ′′ ∈V ∈ D x ′ , H x ′ (D) = x,x ′′ ∈V L(x ′ , x)D(x, x ′′ )f (x)f (x ′′ )
Then the arguments given in the proofs of Proposition 17 and Theorem 1 also show the Lemma 18 A signed kernel D † ∈ D satisfies (21) if and only if for any x ′ ∈ V , D † x ′ minimizes the mapping H x ′ on D x ′ . As a consequence, by compactness of D x ′ and continuity of H x ′ , such an optimal D † ∈ D exists.

In order to get an idea of an optimal D † ∈ D, let us make the following additional assumption: for any x ′ ∈ V , the probability measure L(x ′ , •) is uniform over V x ′ (recall that this set was defined as the support of L(x ′ , •) at the beginning of section 2) and that n ≔ |V x ′ | does not depend on x ′ ∈ V : L is the Markov transition kernel of the simple random walk on the connected and regular graph on V whose edge set is {(x, x ′ ) ∈ V 2 : L(x, x ′ ) > 0}. The reversibility condition on the elements of D x ′ amounts to asking them to be symmetric. Denote by x 1 , x 2 , ..., x n the elements of V x ′ (as we work with fixed x ′ ∈ V , we won't indicate that everything is depending on this point), ordered such that f (x 1 ) ≤ f (x 2 ) ≤ • • • ≤ f (x n ). To simplify notations, any element D ∈ D x ′ is identified with a n × n matrix (D(i, j)) i,j∈ n where D(i, j) stands for D(x i , x j ). Then under the above assumption we have:

Proposition 19 Let D †
x ′ ≔ J n -I n , where I n is the n × n identity matrix and J n is the n × n reverse diagonal matrix (∀ i, j ∈ n , J n (i, j) ≔ δ n-j+1 (i)). The matrix D †

x ′ is a minimizer of the functional H x ′ on D x ′ . Thus, when L is the transition kernel of a random walk on a regular graph whose spectral gap is of multiplicity 1, D † = (D †

x ′ ) x ′ ∈V corresponds to the best way to perturb M (0) in order to improve infinitesimally its spectral gap.

The proof of this proposition will be based on the following technical result:

Lemma 20 Consider SP n the set of n × n doubly substochastic matrices and the functional G defined on SP n by

∀ P = (P (i, j)) i,j∈ n ∈ SP n , G(P ) = i,j∈ n P (i, j)g(i)h(j) (22)
where g, h : n → R + are two nondecreasing functions. Then I n is a maximizer of G on SP n .

Proof

Note that for any P ∈ SP n we can find a Q ∈ P n , the set of n × n doubly stochastic matrices, such that all the entries of Q are larger or equal to those of P . Since g and h are nonnegative functions, it follows that G(Q) ≥ G(P ), and it is sufficient to prove the above lemma with SP n replaced by P n . To do so, we consider an induction on n ∈ N \ {0}. For n = 1 the result is obvious, since P 1 = {I 1 }. Next assume that the above lemma is true for some n ∈ N \ {0} (and for all g, h as in the lemma) and consider P a maximizer on P n+1 of a functional G which has the form described in (22) with n replaced by n + 1. If there exists k ∈ n such that P (k, n + 1) > 0, then P (n + 1, n + 1) < 1 and we can find l ∈ n such that P (n + 1, l) > 0. Assume for instance that P (k, n + 1) ≤ P (n + 1, l) (otherwise work with the transposed matrix) and introduce the matrix P ′ ∈ P n+1 defined by

∀ i, j ∈ n + 1 , P ′ (i, j) =        0 , if (i, j) = (k, n + 1) P (n + 1, l) -P (k, n + 1) , if (i, j) = (n + 1, l) P (i, j) + P (k, n + 1)
, if (i, j) = (n + 1, n + 1) or (i, j) = (k, l) P (i, j)

, otherwise

We compute that

G(P ) -G(P ′ ) = (g(n + 1)h(n + 1) + g(k)h(l) -g(n + 1)h(l) -g(k)h(n + 1))P (n + 1, k) = (g(n + 1) -g(k))(h(n + 1) -h(l))P (n + 1, k)
quantity which is nonnegative due to the assumptions g(k) ≤ g(n+1) and h(l) ≤ h(n+1). Thus P ′ is also a maximizer of G on P n+1 . Iterating this procedure, we end up with a maximizer

Q ∈ P n+1 such that Q(n + 1, i) = Q(i, n + 1) = 0 for all i ∈ n and G(Q) = G ′ (Q ′ ) + g(n + 1)h(n + 1)
, where Q ′ ≔ (Q(i, j)) i,j∈ n ∈ P n and G ′ is the mapping on P n defined by the rhs of ( 22). So it remains to apply the iterative assumption to get the result.

Let us now proceed to the

Proof of Proposition 19

We first assume that n is even, say n = 2m. Let l ∈ R be given, for any D = (D(i, j)) i,j∈ n ∈ D x ′ , we have by definition of D x ′ and due to the fact that L(x ′ , •) ≡ 1/n on V x ′ (set which was defined at the beginning of Section 2), we have

nH x ′ (D) = x,x ′′ ∈V D(x, x ′′ )(f (x) -l + l)(f (x ′′ ) -l + l) = x,x ′′ ∈V D(x, x ′′ )(f (x) -l)(f (x ′′ ) -l) +l x,x ′′ ∈V D(x, x ′′ )(f (x) + f (x ′′ )) -l 2 x,x ′′ ∈V D(x, x ′′ ) = x,x ′′ ∈V D(x, x ′′ )(f (x) -l)(f (x ′′ ) -l) +2l x,x ′′ ∈V D(x, x ′′ )f (x) = x,x ′′ ∈V D(x, x ′′ )(f (x) -l)(f (x ′′ ) -l) (23)
Choose

l = f (m) + f (m + 1) 2 (24) so that (f (x) -l)(f (x ′′ ) -l) is nonpositive for (x, x ′′ ) ∈ m × m + 1, n ⊔ m + 1, n × m and nonnegative for (x, x ′′ ) ∈ m × m ⊔ m + 1, n × m + 1, n . It follows that to minimizes H x ′ on D x ′ , it is enough to consider D ∈ D x ′ such that D -,-≔ (D(i, j
)) i,j∈ m and D +,+ ≔ (D(i, j)) i,j∈ m+1,n have nonpositive entries and such that D -,+ ≔ (D(i, j)) (i,j)∈ m × m+1,n and D +,-≔ (D(i, j)) (i,j)∈ m+1,n × m have nonnegative entries. Indeed, for instance if D(i, j) > 0 with i, j ∈ m , consider the matrix D ′ ∈ D x ′ defined by

∀ i ′ , j ′ ∈ n , D ′ (i ′ , j ′ ) =            0 , if (i ′ , j ′ ) = (i, j) or (i ′ , j ′ ) = (j, i) D(i ′ , j ′ ) + D(i, j) , if (i ′ , j ′ ) = (m + 1, i) or (i ′ , j ′ ) = (m + 1, j) D(i ′ , j ′ ) + D(i, j) , if (i ′ , j ′ ) = (i, m + 1) or (i ′ , j ′ ) = (j, m + 1) D(i ′ , j ′ ) -2D(i, j) , if (i ′ , j ′ ) = (m + 1, m + 1) D(i ′ , j ′ ) , otherwise
We have

H x ′ (D ′ ) = H x ′ (D) -2( f (i) f (j) -( f (i) + f (j)) f (m + 1) + f 2 (m + 1))D(i, j) ≤ H x ′ (D)
where we have taken f ≔ fl.

The case where there exists (i, j) ∈ m × m + 1, n with D(i, j) < 0 is even easier to treat: just transfer the negative weights at the entries (i, j) and (j, i) to the entries (i, i) and (j, j).

Thus to find a minimizer D ∈ D x ′ for H x ′ , we can assume that the entries of D -,-and D +,+ are nonpositive while those of D -,+ and D +,-are nonnegative. Define P -,-as the matrix obtained from -D -,-by reversing the order of the rows and of the columns, P +,+ ≔ -D +,+ , P -,+ as the matrix obtained from D -,+ by inverting the order of the rows, and P +,-as the matrix obtained from D +,-by inverting the order of the columns, so that these four matrices are doubly substochastic. We can write naturally

nH x ′ (D) = -(G -,-(P -,-) + G +,+ (P -,-) + G -,+ (P -,+ ) + G +,-(P +,-))
where for instance G -,-is the functional on SP m defined by

∀ P = (P (i, j)) i,j∈ m ∈ SP m , G -,-(P ) = i,j∈ m P (i, j)g(i)h(j)
where g = h is the nonnegative and nondecreasing function given by

∀ i ∈ m , g(i) ≔ -f (m -i + 1)
In fact the four functionals G -,-, G +,+ , G -,+ and G +,-are of the same type as the map G considered in Lemma 20. It follows that I m is a maximizer for all these functional. Coming back to the description of D in terms of P -,-, P +,+ , P -,+ and P +,-, we get that D = J n -I n is in fact a minimizer for H x ′ . It remains to treat the case where n is odd, say n = 2m + 1. In this situation, we rather define l = f (m + 1) instead of (24), so (23) enables to erase the (m + 1) th row and the (m + 1) th column.

Then the above arguments can be applied to the remaining matrix.

The proof of Lemma 20 also shows that the maximizer is unique if and only if g(1

) < g(2) < • • • < g(n) and h(1) < h(2) < • • • < h(n).
From the above proof we deduce that the minimizer of

H x ′ is unique if and only if f is on V x ′ .
If this is true for all x ′ ∈ V , we get from Lemma 18 that there exists a unique D † ∈ D such that (21) is satisfied. In particular this condition is fulfilled if the eigenvector f is globally one-to-one.

Remark 21

The random walk assumption is quite restrictive, but we believe that the qualitative fact that the best infinitesimal perturbation corresponds to jumping from smallest values to largest values of an eigenvector associated to the spectral gap (on the neighborhood V x , for x ∈ V ) can be extended, except that in the general case, one would have to use the repartition function for the values of the restriction of this eigenfunction to the neighborhood V x endowed with the probability measure L(x, •). We won't go further in this direction, since our purpose was just to indicate that the local landscape induced by such an eigenvector can be used to optimally improve the spectral gap, at least infinitesimally.

Under some circumstances, one can get nice informations about the speed of convergence to equilibrium by studying singular values, see for instance Fill [START_REF] Allen | Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process[END_REF]. This is not the case in our situation: the singular values associated to a trajectorially reversible second order Markov kernel are relatively easy to compute but they don't provide pertinent quantitative informations:

Proposition 22 Let M be a second order Markov kernel trajectorially reversible with respect to ν × L (with ν > 0) and consider its dual operator M * in L 2 (ν × L). The spectrum of the Markovian operator M * M in L 2 (ν × L) is the union, with multiplicities, of the spectra of the 2

x , for x ∈ V , where M x is the transition kernel on V x defined at the beginning of Section 2.

We knew a priori that the kernels M x , for x ∈ V , were diagonalizable in R, since they are reversible with respect to the probability measures L(x,

•). The diagonalizability in R of M * M (in L 2 (ν × L)) comes from its self-adjointness in L 2 (ν × L).
The examples of next section show that usually the information contained in the M x , for x ∈ V , is of a local nature (it just describes how the speed evolves above the point x ∈ V ) and is not sufficient to deduce the global rate of convergence to equilibrium. That is why in our context the singular value approach is not very promising.

Proof

Taking into account Lemme 7, we compute that for any F ∈ F(V 2 ) and any (x,

x ′ ) ∈ V 2 , M * M [F ](x, x ′ ) = x ′′ ,x ′′′ ∈V M (x ′ , x; x ′′ )M (x ′′ , x; x ′′′ )F (x, x ′′′ ) = x ′′′ ∈V x ′′ ∈V M x (x ′ , x ′′ )M x (x ′′ , x ′′′ ) F (x, x ′′′ ) = x ′′′ ∈V M 2 x (x ′ , x ′′′ )F (x, x ′′′ )
It follows that for any fixed x ∈ V , the set {(x, x ′ ) : x ′ ∈ V x } is stable by the Markov kernel M * M . Furthermore the restriction of M * M to {(x, x ′ ) : x ′ ∈ V x } is given by the matrix M 2

x . The announced results follow, once one has identified L 2 (ν × L) with the set of functions defined on the support of ν × L, which is

⊔ x∈V {(x, x ′ ) : x ′ ∈ V x }.
To end up this section, we make some connections with the work of Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF]. We begin by recalling the notion of asymptotic variance. Let P an irreducible Markov kernel on V admitting µ as invariant probability. Consider (X n ) n∈N a Markov chain whose transition kernel is P and let f ∈ F(V ) a function satisfying µ[f ] = 0. Then for n ∈ N large, the variance of the random variable (f (X 1 ) +

• • • + f (X n ))/
√ n admits a limit σ(P, f ) called the asymptotic variance of f (it does not depend on the initial distribution of X 0 ). This result can be extended to second order Markov chains: let (X n ) n∈N be such a chain with second order transition kernel M . Assume that M is irreducible on a subset of V 2 and let m be the associated invariant measure. Let f ∈ F(V ) be a function whose integral with respect to the second marginal of m (or with respect to the first one, see Remark 6) is null. Then the above limit also exists and again it is denoted by σ(M, f ).

Next consider a second order Markov kernel M (1) , trajectorially reversible with respect to ν ×L, with ν > 0 and L irreducible. Assume that the relaxed version of ( 18) is fulfilled:

∀ x ′′ = x ∈ V, M (1) (x, x ′ ; x ′′ ) ≥ L(x ′ , x ′′ )
and that M (1) is irreducible on the support of ν × L (in his Theorem 2, Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF] stated this irreducibility condition is a consequence of the previous assumptions, but this is wrong in general, consider the example of next section with a = 1). Then Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF] has proven that

σ(M (1) , f ) ≤ σ(M (0) , f ) (25)
for any function f ∈ F(V ). The link of this bound with relations between the spectrum of M (1) and that of M (0) is not obvious. To try to clarify the situation, let us recall Peskun's theorem [START_REF] Peskun | Optimum Monte-Carlo sampling using Markov chains[END_REF]. Indeed, Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF] also gave a new and very elegant proof of Peskun's theorem, based as that of (25), on a decomposition of the trajectories. So consider two irreducible Markov kernels P (0) and P (1) , both reversible with respect to the same probability measure µ on V . Assume that P (1) has less tendency to stay at the same place than P (0) :

∀ x = x ′ ∈ V, P (1)
(x, x ′ ) ≥ P (0) (x, x ′ ) Then Peskun's theorem asserts that

∀ f ∈ F(V ), σ(P (1) , f ) ≤ σ(P (0) , f )
In this situation, this bound leads to relations between the spectra of P (1) and P (0) . Indeed, one have, for i = 1, 2, that (see for instance Peskun [START_REF] Peskun | Optimum Monte-Carlo sampling using Markov chains[END_REF])

σ(P (i) , f ) = 2µ[(f -µ[f ])(Id -P (i) ) -1 [f -µ[f ]]] -µ[(f -µ[f ]) 2 ]
where (Id-P (i) ) -1 is the inverse of the operator Id-P (i) : F 0 (µ) → F 0 (µ), with F 0 (µ) the subspace of F(V ) of functions f such that µ[f ] = 0. Using the variational formulation of eigenvalues (see for instance the book of Horn and Johnson [START_REF] Horn | Matrix analysis[END_REF]), it follows that

∀ j ∈ |V | , θ (1) j ≤ θ
(0) j where 1 = θ

(i) 1 ≥ θ (i) 2 ≥ • • • ≥ θ (i)
|V | ≥ -1 is the spectrum of P (i) . This observation enables to see that if for a ∈ [0, 1] and j ∈ |V | , θ (a) j is the j th eigenvalue (in nonincreasing order) of P (a) ≔ (1a)P (0) + aP (1) , then the mapping [0

, 1] ∋ a → θ (a) j ∈ [-1, 1] is nonincreasing. Next,
with the notations of the introduction, consider 1λ(P (a) ) = max{|θ

(a) 2 |, |θ (a) |V | |}. Let a 0 = inf{a ∈ [0, 1] : 1 -λ(a) = -θ (a)
|V | }, with the convention that a 0 = 1 if the previous set is empty. It appears that the mapping [0, 1] ∋ a → 1λ(a) is nonincreasing on [0, a 0 ] and nondecreasing on [a 0 , 1]. Note that this corresponds to the qualitative behavior we are hoping for in Conjecture 3. Nevertheless, there is a strong difference between the behavior of the spectrum in the situation of Peskun's theorem and in the setting of Theorem 1: initially at a = 0, the nonnull eigenvalues begin by going toward 0 in Theorem 1, while they are decreasing in Peskun's theorem (so for the eigenvalues starting from a negative value, they are going outward 0). This discussion cannot be extended to (25), first because this equation is only valid for functions depending on one variable and second because we don't know if the variational formulation of eigenvalues is true for second order kernels, which usually are not reversible in the usual sense. So despite the assumptions of Theorem 1 are similar to those considered by Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF] and the fact that we are working in a similar spirit, it seems there is no obvious relation between (25) and our results.

A case study

We are interested here in the simplest family of examples in the homogeneous setting: the group G is the cyclic group Z N , with N ∈ N \ {0, 1, 2} and the speed only takes values in the symmetric set S = {-1, +1} ⊂ Z N . In particular we will check that Theorem 2 is true in this case.

The natural state space of the associated second order Markov chain is the set of nearest neighbors

G (2) ≔ {(x, x ′ ) ∈ Z 2 N : |x ′ -x| = 1}
, and for any a ∈ [0, 1], consider

∀ (x, x ′ ) ∈ G (2) , ∀ x ′′ ∈ G, M (a) (x, x ′ ; x ′′ ) ≔            (1 + a)/2 , if x ′ = x + 1 and x ′′ = x ′ + 1 (1 + a)/2 , if x ′ = x -1 and x ′′ = x ′ -1 (1 -a)/2 , if x ′ = x + 1 and x ′′ = x ′ -1 (1 -a)/2 , if x ′ = x -1 and x ′′ = x ′ + 1 0 , otherwise
This is a homogeneous situation since the speed transition kernel does not depend on the underlying position and is given by

K (a) = 1+a 2 1-a 2 1-a 2 1+a 2
The set G * defined in ( 16) is the collection of the mappings ρ :

G ∋ x → exp(2πikx/N ) ∈ C,
where k ∈ 0, N -1 . Thus according to the comments made after Proposition 11 and before (17), the spectral decomposition of M (a) into Jordan blocks corresponds to the union of the spectral decompositions of the matrices

B (a) ρ ≔ 1+a 2 ρ(1) 1-a 2 1-a 2 1+a 2 ρ(-1)
where ρ ∈ G * . For the rest of this section, let us identify ρ with ρ(1) and G * with {exp(2πik/N ) : k ∈ 0, N -1 } ⊂ C. Consider more generally, for ρ ∈ T, the unit circle in C, the matrix defined by

B (a) ρ ≔ 1+a 2 ρ 1-a 2 1-a 2 1+a 2 ρ (26)
These matrices were already used in Diaconis, Holmes and Neal [START_REF] Diaconis | Analysis of a nonreversible Markov chain sampler[END_REF] to deduce the spectral decomposition of a related model, where the discrete circle Z N is replaced by the path N (but the authors did not interpret the chain they studied as a second order Markov chain, nor as a position-speed Markov chain, furthermore their reduction to the above matrices is not deduced in the same manner as here).

A direct computation shows the following result:

Lemma 23 Let write ρ ≕ C + iS, with C = ℜ(ρ), S = ℑ(ρ) ∈ [-1, 1]
the respective real and imaginary parts of ρ, and let a 0 (ρ)

≔ (1 -|S|)/(1 + |S|) ∈ [0, 1]. The matrix B (a 0 (ρ)) ρ
is not diagonalizable and is in the conjugacy class of a 2 × 2-Jordan block associated to the eigenvalue (1 + a)C/2 (which will also conveniently denoted θ

(a 0 (ρ)) ρ,±
). If a ∈ [0, a 0 (ρ)), the matrix B (a) ρ is diagonalizable in R and its eigenvalues are

θ (a) ρ,± = 1 + a 2 C ± (1 -a) 2 -S 2 (1 + a) 2 2 If a ∈ (a 0 (ρ), 1], the matrix B (a)
ρ is diagonalizable in C and its eigenvalues are

θ (a) ρ,± = 1 + a 2 C ± i S 2 (1 + a) 2 -(1 -a) 2 2
Thus it appears that for a ∈ [0, 1], M (a) is diagonalizable if and only if a ∈ {a 0 (ρ) : ρ ∈ G * }. In any case, the spectrum of M (a) coincides with the set {θ 1 is a, so with the notations of the introduction we have

Θ * (M (a) ) = {θ (a) ρ,ǫ : ρ ∈ G * \ {1}, ǫ ∈ {-, +}} ∪ {a}
In particular the spectral gap of M (a) is given by

λ(M (a) ) = 1 -max({θ (a) ρ, * : ρ ∈ G * \ {1}} ∪ {a}) (27)
where for any ρ ∈ T, θ

ρ, * ≔ max θ

Note that the quantities θ

Lemma 24 Let ρ ∈ T \ R be given. On [0, a 0 (ρ)] the mapping a → θ (a)
ρ, * is strictly concave and decreasing. For a ∈ [a 0 (ρ), 1], we have θ

(a) ρ, * = √ a.
Proof According to the above observations, we can assume that the argument of ρ belongs to (0, π/2].

In this situation, for a ∈ [0, a 0 (ρ)], we have

θ (a) ρ, * = θ (a) ρ,+ = 1 + a 2 C + (1 -a) 2 -S 2 (1 + a) 2 2
where

C = ℜ(ρ), S = ℑ(ρ). It is clear that θ (a)
ρ, * is a smooth function of a ∈ [0, a 0 (ρ)) and its second derivative is given by

d 2 d 2 a θ (a) ρ, * = - 2S 2 ((1 -a) 2 -S 2 (1 + a) 2 ) 3 2
Thus it appears that a → θ

(a)
ρ, * is strictly concave. Either by direct computation or by using Theorem 1, we get that d da θ

(0) ρ, * < 0, so θ (a) ρ, * is a decreasing function of a ∈ [0, a 0 (ρ)]. For a ∈ [a 0 (ρ), 1], we have θ (a) ρ,+ = θ (a) ρ,-and θ (a) ρ, * = θ (a) ρ,+ = 1 2 (1 + a) 2 C 2 + S 2 (1 + a) 2 -(1 -a) 2 = √ a So the look of the mapping [0, 1] ∋ a → θ (a)
ρ, * is: it decreases until it reaches the curve [0, 1] ∋ a → √ a

(at a 0 (ρ)) that it follows afterward (and thus is increasing). Note that just before a 0 (ρ), θ

ρ, * is strongly decreasing, since lim a→a 0 (ρ)-

d da θ (a)
ρ, * = -∞, as it can be easily be seen. In particular we have

∀ a ∈ [0, 1], θ (a)
ρ, * ≥ √ a ≥ a (29) so ( 27) can be transformed into

λ(M (a) ) = 1 -max{θ (a) ρ, * : ρ ∈ G * \ {1}}
Furthermore, since the maximum of curves which are first nonincreasing and next nondecreasing has the same appearance, we already deduce that the mapping [0, 1] ∋ a → λ(a) first nondecreases and next nonincreases. To get more information in this direction, we need the following simple result.

Lemma 25 Let ρ, ρ ′ ∈ T be such that their respective real parts satisfy C > C ′ ≥ 0. Then for any a ∈ [0, 1] we have,

θ (a) ρ, * ≥ θ (a) ρ ′ , *

Proof

The assumption 0 ≤ C ′ < C clearly implies S 2 < (S ′ ) 2 for the corresponding imaginary parts and a 0 (ρ) > a 0 (ρ ′ ), so in view of the above behaviors, it is sufficient to prove the wanted inequality for a ∈ [0, a 0 (ρ ′ )]. But in this interval it can be written

1 + a 2 C + (1 + a) 2 C 2 -4a 2 ≥ 1 + a 2 C ′ + (1 + a) 2 (C ′ ) 2 -4a 2
and so it is obvious (the strict inequality even holds there).

This result leads us to consider ρ 0 ∈ G * whose real part is the largest possible in absolute value, since we get

∀ a ∈ [0, 1], λ(M (a) ) = 1 -θ (a) ρ 0 , *
A picture enables to convince oneself that

ρ 0 = exp(2πi⌊N/2⌋/N )
where ⌊•⌋ stands for the integer part. Note that ρ 0 is also the unique element of G * such that λ(M (0) ) = 1θ (0) ρ 0 , * and recall that λ(M (0) ) = λ(L), where in the present example L is the transition kernel of the nearest neighbor random walk on Z N . According to the parity of N we have different results:

• When N is even, we have ρ 0 = -1 and λ(L) = 0, this reflects the periodicity of the corresponding random walk. We obtain that λ(M (a) ) = 0, for any a ∈ [0, 1], fact we could also have deduced a priori from periodicity (see the introduction).

• When N is odd, let C N ≔ cos(π/N ) be the absolute value of the real part of ρ 0 . We have λ(L) = 1 -C N and define a N ≔ a 0 (ρ 0 ) = (1 + sin(π/N )) -1 (1sin(π/N )). Note that for N large (and still odd) this number is close to 1 and that the beginning of its expansion in terms of 1/N is a N ≃ 1 -2π/N . We can also express it in terms of the spectral gap of L:

a N = 1 -1 -C 2 N 1 + 1 -C 2 N = 1 -λ(L)(2 -λ(L)) 1 + λ(L)(2 -λ(L))
The spectral gap of λ(M (a) ) for a ∈ [0, 1] is then given by

λ(M (a) ) = 1 -1+a 2 C N - √ (1+a) 2 C 2 N -4a 2 , if a ∈ [0, a N ] 1 - √ a , if a ∈ [a N , 1] (30)
Similarly to what we remarked for θ

ρ, * after the proof of Lemma 24, λ(M (a) ) is improving a lot just before a N . The largest spectral gap of M (a) correspond to the choice a = a N and we get

λ(M (a N ) ) = 1 - √ a N = 1 - 1 -λ(L)(2 -λ(L)) 1 + λ(L)(2 -λ(L))
Thus for N large and odd, we have

λ(M (a N ) ) ∼ π N
which is an important improvement with respect to the spectral gap of L satisfying λ(L) ∼ π 2 2N 2 . The diffusive effect has been erased. Theorem 2 amounts to the above statements in the case of our example (since S = {-1, 1}, replace |S| in the formulas by 2 and note that the alternative a 0 > 1 does not occur in the present case).

More generally, the previous considerations (see also Gade and Overton [START_REF] Kranthi | Optimizing the asymptotic convergence rate of the Diaconis-Holmes-Neal sampler[END_REF], when the discrete circle is replaced by a path) enable to get the following picture for the evolution of the spectrum of M (a) (seen as an operator on F(G (2) )) as a goes from 0 to 1, for N odd (a similar behavior holds for N even, except for that the eigenvalue -1 does not move). First note that for any a ∈ [0, 1], the spectrum of M (a) is included into [-1, 1] ∪ C( √ a) where C( √ a) ⊂ C is the circle centred at 0 and of radius √ a. Next the eigenvalues go by pairs. At a = 0, one starts from zero and the other one from an eigenvalue of L and they go in the direction of each other (there is one particular case which is the pair containing the eigenvalue 1: this value does not move and just looks its partner, the eigenvalue a, coming in its direction). When they meet, they begin to leave the real line and go on the circle C( √ a) ⊂ C. They will keep on moving on the circle (which itself is increasing), in a conjugate way. Putting aside the exceptional pair containing 1, the last pair to leave the real line is the one containing the eigenvalue corresponding to the spectral gap. Once this pair has left the interval [-1, 1], all the eigenvalues (except the two exceptional ones) have the same modulus and so all of them correspond to the spectral gap. At a = 1, all eigenvalues are regularly distributed on the unit circle C(1) and are all of multipicity 2. Indeed M (1) has two irreducible classes, which correspond respectively to the determinist walks which always turn around Z N in the clockwise or in the anti-clockwise direction and both of them have G * as spectrum.

Remark 26 Up to a real factor, the matrices defined in (26) with a ∈ [-1, 1] and ρ ∈ T correspond to the general 2× 2 matrices which are symmetrical and centro-Hermitian. These properties enable to get some of the above results without entering into the computations of the eigenvalues. This approach, as well as a better exploitation of Lemma 12, would have to be developed further in order to go in the direction of Conjecture 3. But here let us just deduce the first part of Lemma 24.

Recall the tilde operation on F({-1, +1}, C) which was defined after the proof of Lemma 12: if

f = (f (-1), f (1)
∀ f = (f (-1), f (1)), g = (g(-1), g(1)) ∈ F({-1, +1}, C), f, g ≔ f (-1)g(-1) + f (1)g(1)
The above properties of the eigenvectors imply that for ǫ ∈ {-, +},

ϕ (a) ρ,ǫ , ϕ (a) ρ,ǫ = 2ϕ (a) ρ,ǫ (-1)ϕ (a) ρ,ǫ (1)
ρ,+ = 0. Note that since we can find t ∈ R such that (ϕ

ρ,+ ) are of opposite signs. We can renormalize the eigenvectors so that these quantities are 1 and -1 or vice-versa. Taking into account the elementary fact that for any c 1 , c 2 ∈ R, we have inf

s,t≥0 : t-s =0 c 1 t -c 2 s t -s = max(c 1 , c 2 )
we deduce that Here we reduce the proof of Theorem 2 to the computations made in the previous section. But we will also see that when the generating set S contains strictly more than two elements, then the resort to the second order Markov chains considered here only provides weak improvements of the spectral gap. Three examples will illustrate this unfortunate fact.

θ (a) ρ,+ = inf f ∈F ({-1,+1},C) : f ,f =0 f , B (a) ρ [f ] f , f θ (a) ρ,-= sup f ∈F ({-1,+1},C) : f ,f =0 f , B (a)
Let us recall the framework of Theorem 2: G is a finite Abelian group and S is a symmetric subset of generators of G, with s ≔ |S| ≥ 2. For any a ∈ [0, 1], we consider the homogeneous speed transition kernel given by

∀ y, y ′ ∈ S, K (a) (y, y ′ ) ≔ 1 + a s-1 µ(y ′ ) , if y ′ = -y (1 -a)µ(y ′ ) , if y ′ = -y
where µ is the uniform distribution on S. Of course, if G is a cyclic group and S = {-1, 1}, we recover the example treated in the preceding section. Consider G * the set defined in (16), where G has been identified with a product group l∈ 1,r Z N l (with r ∈ N \ {0} and N 1 , ..., N r ∈ N \ {0, 1}). For a ∈ [0, 1], let M (a) be the second order Markov kernel associated to the homogeneous speed transition kernel K (a) . According to the comments following Proposition 11, the spectral decomposition of M (a) into Jordan blocks corresponds to the union of the spectral decompositions of the matrices A

ρ ≔ △(ρ)K (a) (recall that △(ρ) is the diagonal matrix whose diagonal entries are given by ρ), for ρ ∈ G * . Since S is generating G, any ρ ∈ G * is uniquely determined by (ρ(y)) y∈S , we can identify ρ with (ρ(y)) y∈S . More generally, let R be the set of functions ρ : S → T which satisfies ρ(-y) = ρ(y) for any y ∈ S and ρ(0) = 1 if 0 ∈ S. For any ρ ∈ R, we define A (a) ρ ≔ △(ρ)K (a) in the same way as above. The main step to understand their spectral structure is contained in the next result:

Proposition 27 Let a ∈ [0, 1] and ρ ∈ R be fixed and assume that ρ is not proportional to ½, the element of R always taking the value 1 on S. Denote b (a) ≔ a/(s-1), c

Proof

Let J be the reverse diagonal S × S matrix: ∀ y, y ′ ∈ S, J(y, y ′ ) ≔ δ -y (y ′ ) (it was already encountered in Lemma 20). It appears that for any a ∈ [0, 1], we have

K (a) = (1 + b (a) )K (0) -b (a) J (31)
Using this formula, we compute that

A (a) ρ [½] = (1 + b (a) )△(ρ)K (0) [½] -b (a) △(ρ)J[½] = (1 + b (a) )△(ρ)½ -b (a) △(ρ)½ = ρ
On the other hand we have

A (a) ρ [ρ] = (1 + b (a) )△(ρ)K (0) [ρ] -b (a) △(ρ)J[ρ] = c (a) ρ ρ -b (a) ½
Thus the vector space W generated by ½ and ρ is left stable by the operator A (a)

ρ . By assumption, W is of dimension 2 and in the basis (½, ρ), the matrix associated to the restriction of A (a)

ρ to W is just C (a) ρ . Next consider W ′ ≔ {f ∈ F(S, C) : µ[f ] = 0 and µ[ρf ] = 0}
and let us check that W ′ is also left stable by A (a) ρ . Indeed, using (31), we get that for any f ∈ W ′ ,

A (a) ρ [f ] = -b (a) △(ρ)J[f ] (32)
So we compute first that

µ[A (a) ρ [f ]] = -b (a) µ[ρJ[f ]] = -b (a) s -1 y∈S ρ(y)f (-y) = -b (a) s -1 y∈S ρ(-y)f (y) = -b (a) µ[ρf ] = 0 and next that µ[ρA (a) ρ [f ]] = -b (a) µ[ρρJ[f ]] = -b (a) µ[J[f ]] = -b (a) µ[f ] = 0
The stability of W ′ by A (a)

ρ follows from these two equalities. In order to go further in the spectral decomposition of A To conclude the proof of the above proposition, it remains to show that the restriction A

(a) ρ | W ′ of A (a)
ρ to W ′ is diagonalizable and that its only possible eigenvalues are b (a) and -b (a) . Coming back to (32), we compute that for any f ∈ W ′ and y ∈ S,

(A (a) ρ ) 2 [f ](y) = -b (a) ρ(y)A (a) ρ [f ](-y) = -b (a) ρ(y)(-b (a) )ρ(-y)f (y) = (b (a) ) 2 f (y)
The announced results are then a consequence of the identity (A

(a) ρ | W ′ ) 2 = (b (a) ) 2 Id.
To finish the spectral analysis of A ρ . To come back to the situation of the previous section, we just apply the arguments of the above proof to the case where s = 2:

Lemma 28 Let a ′ = b (a) ∈ [0, 1] and ρ ′ ∈ T be such that its real part is given by s

-1 y∈S ρ(y). Then C (a)
ρ is in the same conjugacy class as

B (a ′ ) ρ ′ ≔ 1+a ′ 2 ρ ′ 1-a ′ 2 1-a ′ 2 1+a ′ 2 ρ ′ Proof Let us starts from the matrix B (a ′ )
ρ ′ , where a ′ ∈ [0, 1] and ρ ′ ∈ T. According to formula (17), this matrix is in the same conjugacy class as

A (a ′ ) ρ ′ ≔ 1+a ′ 2 ρ ′ 1-a ′ 2 ρ ′ 1-a ′ 2 ρ ′ 1+a ′ 2 ρ ′
The latter matrix has the same structure as the matrices A (a)

ρ considered above, but with a set S of cardinal 2. So by the computations of the proof of Proposition 27, we have

0 -a ′ 1 (1 + a ′ ) ρ+ρ ′ 2 = U (a ′ ) ρ ′ A (a ′ ) ρ ′ (U (a ′ ) ρ ′ ) -1
where

U (a ′ ) ρ ′ ≔ 1 ρ ′ 1 ρ ′
Thus if we take a ′ = b (a) ∈ [0, 1] and ρ ′ ∈ T such that its real part is given by s -1 y∈S ρ(y), we recover the matrix C (a) ρ and the wanted result follows.

The matrix B (a ′ ) ρ ′ coincides with the matrix defined in (26), where a and ρ have to be replaced by a ′ and ρ ′ . As a consequence the spectral decomposition of C (a) ρ is given by Lemma 23, where a and ρ have to be replaced by a ′ and ρ ′ . In particular, the bound (29) implies that the largest modulus of the eigenvalues of C where the rhs was defined in (28) (where a and ρ have to be replaced by a ′ and ρ ′ ).

We can now come to the

Proof of Theorem 2

To complete the previous investigation of the spectrum of the operator M (a) , for a ∈ [0, 1], we must study the matrix A (a) ρ when ρ ∈ G * is proportional to ½. So let ρ ∈ G * be such that there

exists z ∈ C with ∀ y ∈ S, ρ(y) = z
By symmetry of S and due to the fact that ρ(-y) = ρ(y) for any y ∈ S, we get that z ∈ R. Thus there is only two possibilities: either z = 1 or z = -1. In the latter case, namely if there exists ρ ∈ G * such that ρ(y) = -1 for all y ∈ S, we get that the underlying random walk kernel L is periodic: it only allows transitions from G + to G -and from G -to G + , where for ǫ ∈ {-, +},

G ǫ ≔ {x ∈ G : ρ(x) = ǫ1}. Then -1 is an eigenvalue of L (an associated eigenvector is ½ G + -½ G -)
and by consequence the spectral gap λ of L is zero. By periodicity, the spectral gap λ(M (a) ) of M (a) , for a ∈ [0, 1], also vanishes and we get that Λ ≔ max a∈[0,1] λ(M (a) ) = 0. In this situation, Theorem 2 asserts that a 0 = s -1 ≥ 1 and formula ( 12) is true, because its rhs also vanishes.

Let us now consider the case z = 1, namely ρ = ½ (identifying elements of G * with their representative in R). The corresponding matrix A Due to the fact that in Proposition 29 the quantity a ′ = a/(s -1) is independent of ρ ∈ G * , the behavior of the spectrum of M (a) described at the end of Section 4 is also valid here with three differences:

-the increasing circle containing the nonreal eigenvalues has radius a/(s -1), -if a 0 > 1, not the all eigenvalues issued from the spectrum of L will encounter an eigenvalue issued from 0 before a reaches 1, -there are some "unpaired" eigenvalues, but their value is either -a/(s -1) or a/(s -1), note in particular that no eigenvalue stays in 0 (for a = 0).

Unfortunately, in general Theorem 2 does not provide great improvements of the spectral gap, except if |S| = 2. This phenomenon was already observed by Neal [START_REF] Neal | Improving asymptotic variance of MCMC estimators: Non-reversible chains are better[END_REF], relatively to the improvement of the asymptotic variance (recall the discussion at the end of Section 3). To get an idea of the improvement brought by the resort to the second order Markov chains introduced in Theorem 2, let us consider an abstract family of examples parametrized by N belonging to a set N , endowed with a filter so that the notion N → ∞ has a meaning. Thus for any N ∈ N , we are given a finite Abelian group G N and a symmetric set of generators S N , with |S N | ≥ 2. Denote by λ N the spectral gap of the underlying random walk and more generally, put the index N to all the notations introduced in Theorem 2 to indicate their dependence on N ∈ N .

Proposition 30 Assume that there exists s ∈ N \ {0, 1, 2} such that for any N ∈ N , |S N | = s. Under the assumption that lim N →∞ λ N = 0, we have as N → ∞,

Λ N = λ(M (1) ) ∼ s 2(s -1) 1 + s s -2 2 λ N

Proof

Clearly we have for the quantity a N defined in [START_REF] Peskun | Optimum Monte-Carlo sampling using Markov chains[END_REF], with λ replaced by λ N , lim N →∞ a N = s -1 > 1 So for N "large" enough, we get

Λ N = 1 - s 2(s -1)   1 -λ N + s -2 s 2 -λ N (2 -λ N )   = 1 - s 2(s -1)   1 -λ N + s -2 s 1 - s s -2 2 λ N (2 -λ N )   = 1 - s 2(s -1) 1 -λ N + s -2 s 1 - s s -2 2 λ N + o(λ N ) = s 2(s -1) 1 + s s -2 2 λ N + o(λ N )
Let s ∈ N \ {0, 1, 2} be fixed. One can take for N the set of all couples (G, S) where G is a finite Abelian group and S a symmetric set of generators of S, with |S| = s. The assumptions of the previous result are then all satisfied if we endow N with the filter base corresponding to the subsets {(G, S) ∈ N : λ (G,S) ≤ ǫ}, for ǫ ∈ (0, 1). Nevertheless, let us end this section with three more concrete families of examples. The first family is similar to the one considered in the previous section, except that we add 0 to the generating set S. because we easily check that here the maximum is attained for k = 1 (this is an important difference with the previous section, in particular no periodicity phenomenon occurs now). Note that for N = 3, λ N = 1: this is a situation where the spectral gap cannot be improved and Theorem 2 gives us a 3 = 0 and Λ 3 = λ 3 . Indeed for N = 3, the spectral gap is worsening with a ∈ [0, 1], since (34) is always valid (in this particular case with C 0 = b 0 = 0) and we get λ(M (a) ) = 1a/2. But for N ∈ N \ {3}, we get a strict improvement of the spectral gap. Nevertheless, it remains quite modest, because we compute that for N ∈ N large,

λ N ∼ 4π 2
3N 2 and Proposition 30 gives us

Λ N ∼ 15 2 λ N ∼ 10π 2
N Note that we can also consider the case N = 2, then G 2 = S 2 = Z 2 . As for N = 3, this is a situation where the spectral gap cannot be improved: λ 2 = 1. Proposition 27 enables to see that for any a ∈ [0, 1], the spectrum of M (a) (acting here on Z 2

2 ) is equal to {1, a, -√ a, √ a} so that the spectral gap is worsening with a: λ(M (a) ) = 1 -√ a.

The second family of examples corresponds to the nearest neighbor multidimensional torus models.

Example 32 Let r ∈ N\{0, 1} be fixed. We denote N = (N\{0, 1, 2}) r and for N = (N 1 , ..., N r ) ∈ N , consider the group G N = l∈ 1,r Z N l and the generating set Then as N → ∞, we have

λ N ∼ π 2 2r l∈l N 1 N 2 l
where l N ≔ {l ∈ 1, r : N l is odd}. In particular lim N →∞ λ N = 0 and Proposition 30 implies that as N → ∞,

Λ N ∼ r 2r -1 1 + r r -1 2 λ N
The case where some of the N i , i ∈ 1, r , are equal to 2 can be treated in a similar way except that now

|S N | = r i=1 ½ {N i =2} + 2½ {N i >2}
In particular we can deal with the situation G = Z 2 2 , S = {(0, 1), (1, 0)}, which, up to an isomorphism of G, is the only case with |S| = 2 which was not treated in Section 4. and if √ N is even, we get λ N = 0. For N ∈ N large enough, the maximum is attained for k = (N -1)/2 (and for k = (N + 1)/2) and it appears that

λ N = 1 - 1 2 cos(π/N ) + cos(π/ √ N ) ∼ π 2 4N
for N large. Again Proposition 30 shows only a modest improvement for the spectral gap of M (1) : for N large,

Λ N ∼ 10 3 λ N ∼ 5π 2 6N

  : ρ ∈ G * , ǫ ∈ {-, +}}. Note that the eigenvalue 1 of M (a) associated to the constant eigenvectors correspond to the eigenvalue 1 of the matrix B

  only depend on the real part of ρ ∈ T, i.e. θ } = {-θ (a) -ρ,-, -θ (a) -ρ,+ }. It follows that θ (a) ρ, * is a function of the absolute value of the real part of ρ ∈ T. A first step toward Theorem 2 is the following study:

  ) ∈ F({-1, +1}, C), we have f ≔ (f (1), f (-1)). When the matrix B (a) ρ defined in (26) has two distinct real eigenvalues, the corresponding eigenvectors, say ϕ (a) ρ,-and ϕ (a) ρ,+ , can be assumed to be real. According to the remark after the proof of Lemma 12, for ǫ ∈ {-, +}, we have furthermore that ϕ (a) ρ,ǫ is proportional to ϕ (a) ρ,ǫ . Consider the usual bilinear (not sesquilinear) form •, • defined by

  to the proportionality of ϕ

  , we would end up with ϕ (a) ρ,ǫ = (0, 0). Furthermore, since B (a) ρ is symmetric with respect to •, • , we get that θ

ρ5

  Due to the fact that for a ∈ [0, a 0 (ρ)], these eigenvalues have the same sign (because det(B (a) ρ ) = 4a), the first part of Lemma 24 is then a consequence of the affine nature of the map [0, 1] ∋ a → B has conjuguate nonreal eigenvalues, note that the tilde operation enables to pass from one eigenvector to the other eigenvector. Contrary to the above situation, we then have ϕ(a) ρ,ǫ , ϕ (a) ρ,ǫ = 0, for ǫ ∈ {+, -}, because θ (a) ρ,ǫ ϕ (a) ρ,ǫ , ϕ (a) ρ,ǫ = ϕ (a) ρ,ǫ , B (a) ρ [ϕ (a) ρ,ǫ ] = B (a) ρ [ ϕ (a) ρ,ǫ ], ϕ (a) Global improvement of the spectral gap

ρ

  is in the same conjugacy class as a block diagonal matrix whose diagonal blocks are the 2 × 2 block C (a)ρ , with multiplicity one, complemented with some 1 × 1 block(s) (b(a) ) and/or (-b(a) ).

  must verify that F(S, C) = W ⊕W ′ , which amounts here to check that W ∩ W ′ = {0} (because the liberty of ½ and ρ in the dual spaceof L 2 [µ, C] implies that the dimension of W ′ is |S| -2). So let f ∈ W ∩ W ′and write it under the form v½ + wρ, with v, w ∈ C. Let r ≔ µ[ρ], which is also equal to µ[ρ] by symmetry, thus r is a real number. We compute that µ[f ] = v + rw µ[ρf ] = rv + w Thus the system of equations µ[f ] = 0, µ[ρf ] = 0 admits a non trivial solution in v, w, if and only if r 2 = 1. But if this is true, then we have |µ[ρ]| = µ[|ρ|] = 1 and necessarily ρ has to be proportional to ½. This is excluded by our assumption and it follows that v = w = 0, i.e. f = 0.

ρ

  , say for fixed a ∈ [0, 1] and ρ ∈ R such that ½ are ρ are not proportional, we must study more precisely C (a)

ρ

  is larger than a ′ = b(a) . Then Proposition 27 leads to the following result: Proposition 29 Let be given a ∈ [0, 1] and ρ ∈ R such that ½ are ρ are not proportional and define a ′ ∈ [0, 1] and ρ ′ ∈ T as in Lemma 28. Consider Θ (a) ρ, * the largest modulus of the eigenvalues of A (a) ρ . Then we have Θ (a) ρ, * = θ (a ′ ) ρ ′ , *

2 ,

 2 is just K(a) . The arguments used in the proof of Proposition 27 become simpler to deduce the spectral decomposition of K(a) : the function ½ S is an eigenvector of K (a) associated to the eigenvalue 1, the restriction ofK (a) to W ′ ≔ {f ∈ F(S, C) : µ[f ] = 0} is diagonalizable and its spectrum is included into {-b (a) , b (a) }.It follows from these considerations, that the largest modulus of the eigenvalues of M (a) , outside the eigenvalue 1 associated to the eigenvector ½ G (which according to Proposition 10, corresponds to the eigenvector ½ S of A (a) ½ ), is the largest of the quantities Θ (a) ρ, * , where ρ ∈ G * \{½}. Furthermore, when L is aperiodic, which is the situation we will consider for the rest of this proof, all ρ ∈ G * \{½} are not proportional to ½. Due to Proposition 29 and Lemma 25, the ρ ∈ G * \ {½} maximizing Θ (a) ρ, * do not depend on the value of a ∈ [0, 1]. In particular they are the ρ 0 ∈ G * \ {½} such that the spectral gap λ of L satisfies 1λ = Θ (0) ρ 0 , * . Let us defineC 0 ≔ s -1 y∈S ρ 0 (y)According to Proposition 29 and to the computations of the previous section, this quantity does not depend on the particular choice of the ρ 0 ∈ G * \ {½} such that 1λ = Θ (0) ρ 0 , * and indeed we have1λ = C 0(33)Furthermore, Proposition 29 leads to a result similar to (30): the spectral gap of λ(M (a) ) for a ∈ [0, 1] is then given byλ(M (a) ) = 1 -1+b (a) 2 C 0 -√ (1+b (a) ) 2 C 2 0 -4b (a) if b (a) ∈ [0, b 0 ] 1 -√ b (a) , if b (a) ∈ [b 0 , 1](34)where b 0 ∈ [0, 1] is defined by the equation1 + b 0 2 C 0 -(1 + b 0 ) 2 C 2 0 -4b 0 2 = b 0if such a value exists in [0, 1] and b 0 = 1 otherwise. Recalling that b (a) = a/(s -1) and taking into account the relation (33), as well as the results of the previous section, the announced results follow at once.

Example 31

 31 So let N = N \ {0, 1, 2} and for N ∈ N , we take G N = Z N and S N = {-1, 0, 1}, so that s ≔ |S N | = 3. According to equation (33), we have 1λ N = max 1 3 |1 + exp(2πik/N ) + exp(-2πik/N )| : k ∈ 1, N -

S

  N ≔ {±e l : l ∈ 1, r } where e l = (δ l (k)) k∈ 1,r . Note that |S N | = 2r. Let us say that N → ∞ if all its coordinates N 1 , ..., N r go to infinity. Taking into account the parametrization of G * given in (16), equation (33) gives 1λ N = max l /N l ) : (k 1 , ..., k r ) ∈ l∈ 1,r 0, N l -1 \ {(0, ..., cos(2π⌊N l /2⌋/N l )

  The third family of examples comes back to the cyclic group, but with a different set of generators, with cardinal 4.Example 33 We takeN ≔ {n 2 : n ∈ N \ {0, 1} and n odd} so that √ N is an odd integer for N ∈ N. The notion N → ∞ is the usual one. For N ∈ N, we consider G N ≔ Z N and S N ≔ {±1, ± √ N }.If one had allowed squares of even numbers in the definition of N , the corresponding underlying random walks would be periodic, so that the study of the spectral gap is trivial. Indeed, for √ N ∈ N \ {0, 1}, we always have, according to equation (33), 1λ N = max 1 2 cos(2πk/N ) + cos(2πk/ √ N ) : k ∈ 1, N -1