Laurent Miclo

On the convergence of global-optimization fraudulent stochastic algorithms

Keywords: Global optimization, stochastic algorithms, diffusion processes on Riemannian manifolds, almost sure convergence, Morse functions, Bessel processes primary: 60J60, secondary: 58J65, 90C26, 65C05, 60F15, 60J35, 35K10

We introduce and analyse the almost sure convergence of a new stochastic algorithm for the global minimization of Morse functions on compact Riemannian manifolds. This diffusion process is called fraudulent because it requires the knowledge of minimal value of the function. Its investigation is nevertheless important, since in particular it appears as the limit behavior of non-fraudulent and time-inhomogeneous swarm mean-field algorithms used in global optimization.

Introduction

To find the global minima of functions also admitting local minima is of great importance, both from a theoretical and practical point of view. Here the smooth context of Morse functions on compact Riemannian manifolds is considered. We introduce a new time-homogeneous stochastic algorithm X called fraudulent because it requires the knowledge of the minimal value. In some sense it serves as an illustration of the folklore assertion that to know the minimal value of a function and to find a corresponding global minimum are equivalent problems. Nevertheless we found interesting to investigate this algorithm for three reasons:

• The process X is an approximation of the large-time limit behavior of the time-inhomogeneous swarm mean-field algorithm introduced in [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF]. The latter algorithm is non-fraudulent since it uses its current distribution to estimate in real time the minimal value.

• The principle behind the convergence of X toward the global minima can be used to devise other non-fraudulent stochastic algorithms based on particles systems that learn adaptatively the minimal value.

• The stochastic algorithm X is useful to find other global minima, once one is known, because as soon as the dimension is larger than or equal to 2, all global minima attract X with a positive probability.

More precisely, on a compact Riemannian manifold M , of dimension m ě 1, let be given a Morse function U satisfying min M U " 0. Recall that a smooth mapping is a Morse function if its Hessian is non-degenerate at each of its critical points (which are the points where the gradient vanishes).

Consider a diffusion X pXptqq tě0 associated to the generator

L β U ¨´β x∇U, ∇¨y
where , x¨, ¨y and ∇ stand for the Laplacian, scalar product and gradient coming from the Riemannian structure, and where β is a real number. Since we want to find the global minima of U , we are more interested in the case β ą 0, where the drift has an attractive (respectively repulsive) effect with respect to the local minima (resp. maxima). But as we are to see, it is convenient to also consider non-positive values of β, where the effects of the drift are reversed.

Due to the Morse assumption on U and the fact that min M U " 0, we have that ?

U is a Lipschitz mapping on M (for more details, see Remark 4 below). As a consequence it is possible to construct X, whatever the initial condition, as the unique strong solution to a stochastic differential equation driven by a m-dimensional Brownian motion B pBptqq tě0 (independent from Xp0q), see for instance Ikeda and Watanabe [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF]. Heuristically, this stochastic differential equation can be written under the Itô's form dXptq " ´β∇U pXptqq dt `a2U pXptqq dBptq [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF] or under Stratonovich's form dXptq " ´ˆβ `1 2 ? 2 ˙∇U pXptqq dt `a2U pXptqq ˝dBptq where dBptq has to be isometrically interpreted in the tangent space above Xptq through some stochastic parallel displacements. At least when M is a flat torus, the writing (1) is perfectly rigorous. Consider the set of global minima of U given by

U tx P M : U pxq " 0u
Note that if Xp0q P U, then X does not move: for any t ě 0, we have Xptq " Xp0q. This observation can be strengthened into the attractiveness of U, which is the main goal of this paper.

We need some additional notations. Under the Morse assumption, U consists of a finite set of points, say y 1 , y 2 , ..., y N , with N P N. For each n P N t1, 2, ..., N u, denote λ 1 pnq ď λ 2 pnq ď ¨¨¨ď λ m pnq the positive eigenvalues of the Hessian of U at y n . Introduce the condition

β ą max nP N ř iP m λ i pnq 2λ 1 pnq ´1 (2)
Theorem 1 Whatever the initial condition Xp0q, under (2) the limit Xp8q lim tÑ`8 Xptq exists a.s. and belongs to U. Furthermore, when m ě 2, if X starts from a point x 0 R U, we have for any x P U, P x 0 rXp8q " xs ą 0 When m " 1, denote x 1 and x 2 the boundary points of the connected component of M zU containing x 0 (when U is a singleton, we get x 1 " x 2 ). Then we have P x 0 rXp8q " x 1 s ą 0, P x 0 rXp8q " x 2 s ą 0, @ x P Uztx 1 , x 2 u, P x 0 rXp8q " xs " 0 Thus under (2) X is a time-homogeneous stochastic algorithm minimizing globally U and finding all the global minima as soon as m ě 2.

It is natural to wonder about the optimality of (2). In this direction, we will show:

Theorem 2 Assume that β ă min nP N ř iP m λ i pnq 2λ m pnq ´1 (3)
Whatever the initial condition Xp0q, we have

P " lim tÑ`8
Xptq exists and belongs to U  " 0

As a consequence, the value m{2 ´2 is critical for β when at each global minimum the Hessian is proportional to the identity: Corollary 3 Assume that for each n P N we have λ 1 pnq " λ m pnq, then we have

β ą m 2 ´1 ñ P " lim tÑ`8
Xptq exists and belongs to U

 " 1 β ă m 2 ´1 ñ P " lim tÑ`8
Xptq exists and belongs to U  " 0

In particular this result always applies in dimension 1 and we get ´1{2 as the critical value for β (justifying our consideration of negative β).

In practice we may not have access to the eigenvalues of the Hessian at the global minima, so Condition (2) is difficult to check. An alternative to the appropriate choice of the coefficient β is to let it depend on the current value of U . More precisely, consider ζ : p0, `8q Ñ p0, `8q a smooth function such that

lim uÑ0 `ζ puq " `8 (4) lim uÑ0 `?uζ puq " 0 (5)
We replace the generator L β by

L ζ U ¨´ζpU q x∇U, ∇¨y (6)
with ζpU pxqq∇U pxq " 0 for x P U by continuity, due to (5) (this is in fact the only justification for this assumption). Heuristically this generator corresponds to the Itô stochastic differential equation dXptq " ´ζpU pXptqq∇U pXptqq dt `a2U pXptqq dBptq

The coefficients of this equation are not globally Lipschitz, nevertheless, we will see that whatever the initial distribution, there is a unique strong diffusion X associated to [START_REF] Gall | Bessel processes, the Brownian snake and super-Brownian motion[END_REF] in the sense of martingale problem. For this process X, Theorem 1 still holds, without Assumption [START_REF] Chow | Hamilton's Ricci flow[END_REF]. Of course in this situation we lose the critical phenomenon described by Corollary 3. But the advantage is that the diffusion X associated to [START_REF] Gall | Bessel processes, the Brownian snake and super-Brownian motion[END_REF] could be applied to deal with situations less regular than Morse functions.

In the above results, no estimate on the speed of convergence were provided, but it should be possible to remedy this by examining more quantitatively the following arguments. We hope to go further in future investigations.

The plan of the paper is as follows. In the next section we prove Theorem 1 under a stronger assumption than [START_REF] Chow | Hamilton's Ricci flow[END_REF]. Bessel processes with negative dimension play a pivotal role. In Section 3 the arguments are improved to lead to the desired results. An appendix succinctly recalls the swarm mean-field algorithm of [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF] to explain how a fraudulent algorithm can appear from the investigation on non-fraudulent ones. Another simpler and illustrative example is given, even if it is probably less efficient than swarm algorithms.

Acknowledgments:

I would particularly like to thank Marc Arnaudon, Jérôme Bolte and Stéphane Villeneuve for the discussions we had about this paper.

Proof of a weaker version of Theorem 1

Here we prove Theorem 1 under the stronger assumption

β ą 1 `sup nP N ř iP m λ i pnq 2λ 1 pnq (7)
Its relaxation to (2) will be shown in the next section.

First let us give a sketch of the proof. For any given global minimum y n , with n P N , we can find a small radius r n ą 0 such that inside the ball Bpy n , r n q, the evolution of U pXptqq is comparable to a time-changed Bessel process with negative dimension. Since a Bessel process with negative dimension a.s. converges to zero in finite time, X will stay in Bpy n , r n q forever with positive probability and then converge to y n , if it happens to belong to an even smaller neighborhood V n of y n at some time. Nevertheless, the convergence is not expected to occur in finite time due to the time-change, see Example 7 below. It remains to remark that outside Y nP N V n , the diffusion X is elliptic, so it will end up entering Y nP N V n . Since each times this happens X has a positive chance to converge to a point of U, this event will end up occurring with probability 1. The last assertions of Theorem 1 are consequences of the ellipticity of X outside U.

Let us now develop more precisely the above arguments. We begin by recalling some general facts about the process X, for any fixed β P R. Its law on the set of continuous trajectories from R `to M is uniquely determined by the initial distribution of Xp0q and the by fact for any smooth function f : M Ñ R, the process M f pM f ptqq tě0 defined by @ t ě 0, M f ptq f pXptqq ´f pXp0qq ´ż t 0 L β rf spXpsqq ds is a continuous martingale (with respect to the filtration generated by X). Furthermore, its bracket (the notation of which should not to be confused with the Riemannian scalar product) is given by

@ t ě 0, A M f E t " 2 ż t 0 U pXpsqq }∇f pXpsqq} 2 ds (8)
where }¨} stands for the Riemannian norm. When M is a flat torus, these observations can be deduced from Itô's formula, asserting that:

df pXptqq " rU pXptqq f pXptqq ´β x∇U pXptqq, ∇f pXptqqys dt `a2U pXptqq x∇f pXptqq, dBptqy so that

@ t ě 0, M f ptq " ż t 0 a 2U pXpsqq x∇f pXpsqq, dBpsqy
This formula can be generalized for general compact Riemannian manifolds, nevertheless the above martingale problem point of view is more synthetic and enables to avoid delicate geometric constructions. For extensive developments of the martingale problem approach, we refer to the books of Stroock and Varadhan [START_REF] Stroock | Multidimensional diffusion processes[END_REF] and Ethier and Kurtz [START_REF] Stewart | Markov processes[END_REF].

Introduce

σ f inftt ě 0 : U pXptqq }∇f pXptqq} 2 " 0u
with the convention that σ f " `8 when the r.h.s. is the empty set. Assume that U pXptqq }∇f pXptqq} 2 ‰ 0, so that σ f ą 0 a.s. Since for any t P r0, σ f q, we have U pXptqq }∇f pXptqq} 2 ą 0, we can consider the time change pτ f t q tPr0,ςq uniquely defined through

@ t P r0, ς f q, 2 ż τ f t 0 U pXpsqq }∇f pXpsqq} 2 ds " t where ς f 2 ż σ f 0 U pXpsqq }∇f pXpsqq} 2 ds Define the process Y f via pY f ptqq tPr0,ς f q pf pXpτ f t qqq tPr0,ς f q
Classical time-change theory, see for instance the first section of Chapter 5 of Revuz and Yor [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF], Levy's characterization theorem and ( 8), enable us to construct a Brownian motion pW ptqq tě0 (up to a possible enlargement of the underlying probability space), so that for any time t P r0, ςq,

dY f ptq " 1 2 F f pY f ptqq dt `dW ptq
where for any x P M such that U pxq }∇f pxq} 2 ‰ 0,

F f pxq L β rf spxq U pxq }∇f pxq} 2 " f pxq }∇f pxq} 2 ´β x∇U pxq, ∇f pxqy U pxq }∇f pxq} 2
Now let us apply these considerations to a particular function f . The first idea is to take f " U (in next section we will see that this is not optimal). To simplify the notations, all the superscripts f are removed in this case. Thus we have σ " inftt ě 0 : Xptq P Cu with C tx P M : ∇U pxq " 0u being the set of critical points of U . Furthermore we consider the process Y given by pY ptqq tPr0,ςq pU pXpτ t qqq tPr0,ςq with @ t P r0, ςq, 2

ż τt 0 U pXpsqq }∇U pXpsqq} 2 ds " t and ς 2 ż σ 0 U pXpsqq }∇U pXpsqq} 2 ds
The evolution of Y is given by

dY ptq " 1 2 F pXpτ t qq dt `dW ptq (9)
where pW ptqq tě0 is a Brownian motion and where for any x P M zC,

F pxq U pxq }∇U pxq} 2 ´β U pxq
The process pU pXptqqq tě0 is not Markovian in general, nevertheless we are to show that it can be conveniently compared to a Bessel process while Xptq is close to an element of U.

Indeed, fix a global minimum y n , with n P N . Consider an exponential system of coordinates px 1 , x 2 , ..., x m q on a neighborhood of N n of y n with x 1 py n q " x 2 py n q " ¨¨¨" x m py n q " 0 and such that the vectors pB x i q iP m forms an orthonormal basis of the tangent space at y n consisting of eigenvectors of the Hessian of U respectively to the eigenvalues pλ i pnqq iP m . Let be given P p0, 1q, the value of which will be chosen more precisely below. We can find a small enough radius r n ą 0, such that the open ball Bpy n , r n q is included into N n and such that for any x P Bpy n , r n q, identified with its coordinates px 1 , x 2 , ..., x m q, we have

p1 ´ q ÿ iP m λ i pnq ď U pxq ď p1 ` q ÿ iP m λ i pnq (10) p1 ´ q ÿ iP m λ 2 i pnqx 2 i ď }∇U } 2 pxq ď p1 ` q ÿ iP m λ 2 i pnqx 2 i (11) 1 2 p1 ´ q ÿ iP m λ i pnqx 2 i ď U pxq ď 1 2 p1 ` q ÿ iP m λ i pnqx 2 i (12)
Indeed, the first and second estimates are obtained through the expressions of the Laplace-Beltrami and gradient operators in terms of the metric, taking into account that the first order expansion of the metric in a exponential (or geodesic) chart is constant, see for instance Section 10.1 page 58 of Chow, Lu and Ni [START_REF] Chow | Hamilton's Ricci flow[END_REF].

Remark 4 For x P M zU, we have ∇ ? U " ∇U {p2 ? U q and the above bounds enable to see the norm of this vector is bounded on Bpx n , r n qzty n u, for all n P N . Since

› › ∇ ? U › › is clearly bounded on M z Y nP N Bpy n , r n q, we
deduce that ? U is Lipschitzian, as announced in the introduction.

In particular, y n is the unique critical point of U in Bpy n , r n q. Assume that Xp0q P V n with

V n tx P Bpy n , r n qzty n u : U pxq ă c n {2u (13) with u n min zPBBpyn,rnq U pzq (14)
where BBpy n , r n q is the boundary of Bpy n , r n q. Denote σ n inftt ě 0 : Xptq " y n or Xptq R Bpy n , r n qu ď σ (15) (as usual, σ n " `8 when the r.h.s. is the empty set), and

ς n 2 ż σn 0 U pXpsqq }∇U pXpsqq} 2 ds
Replacing ς by ς n ď ς in the above considerations enables to investigate the process X while it stays in Bpy n , r n {2qzty n u. We are led to study pY ptqq tPr0,ςns . The following result is important in this respect.

Lemma 5 We have for any x P Bpy n , r n qzty n u,

˜p1 ´ q 2 ř iP m λ i pnq 2p1 ` qλ m pnq ´β¸1 U pxq ď F pxq ď ˜p1 ` q 2 ř iP m λ i pnq 2p1 ´ qλ 1 pnq ´β¸1 U pxq

Proof

For any x P Bpy n , r n qzty n u, we have

p1 ´ q ř iP m λ i pnqx 2 i p1 ` q ř iP m λ 2 i pnqx 2 i ď 2U pxq }∇U pxq} 2 ď p1 ` q ř iP m λ i pnqx 2 i p1 ´ q ř iP m λ 2 i pnqx 2 i implying p1 ´ q p1 ` qλ m pnq ď 2U pxq }∇U pxq} 2 ď p1 ` q p1
´ qλ 1 pnq since for any real numbers x i , for i P m , not all of them vanishing, we have

1 λ m pnq ď ř iP m λ i pnqx 2 i ř iP m λ 2 i pnqx 2 i ď 1 λ 1 pnq
The announced follows, by writting

@ x P Bpy n , r n qzty n u, F pxq " ˆ U pxq U pxq }∇U pxq} 2 ´β˙1 U pxq
Recall that β has been chosen so that

β ą 1 `sup nP N ř iP m λ i pnq 2λ 1 pnq
so we can choose ą 0 so that

δ p1 ` q 2 ř iP m λ i pnq 2p1 ´ qλ 1 pnq `1 ´β is negative.
We deduce from (9) that

@ t P r0, ς n q, dY ptq ď dW ptq `δ ´1 2Y ptq dt (16)
This inequality leads us to consider r Y p r Y ptqq tě0 solution of the stochastic differential equation

@ t ě 0, d r Y ptq " dW ptq `δ ´1 2 r Y ptq dt ( 17
)
starting with r Y p0q " u n {2 (defined in ( 14)). The process r Y is a Bessel process with negative dimension δ ă 0, for a recent account, see e.g. Le Gall [START_REF] Gall | Bessel processes, the Brownian snake and super-Brownian motion[END_REF]. It hits 0 in (a.s.) finite time and stays at 0 afterward, the strength of the drift not allowing it to escape 0. Define

θ inftt ě 0 : r Y ptq " 0u r θ inftt ě 0 : r Y ptq " u n u p n Prθ ă r θs (18)
Since r Y is a Markov process and that lim tÑ`8 r Y ptq " 0 a.s., we have p n ą 0. By comparison, we get Lemma 6 Assume that Xp0q P V n defined in (13). Then we have P " @ t ě 0, Xptq P Bpx n , r n q and lim tÑ`8

Xptq " x n  ě p n

Proof

For P p0, Y p0qq, define

θ inftt ě 0 : r Y ptq " u
Applying Theorem (3.7) of Revuz and Yor [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF], we get that

@ t P r0, θ ^r θq, Y ptq ď r Y ptq
Indeed, this a consequence of Y p0q ď u n {2 " r Y p0q as well as of the comparison between ( 16) and (17). Note that in the proof of Theorem (3.7) of Revuz and Yor [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF], we need r Y to be Markovian and that its drift is Lipschitz, which is true as long as it belongs to the segment r , u n s. But Y is not required to be Markovian, it is sufficient that its drift is adapted.

Letting go to zero, we deduce @ t P r0, θ ^r θq, Y ptq ď r Y ptq (one would have remarked that Y ptq remains strictly below u n and thus Xpτ t q remains in Bpy n , r n q as long as t ă r θ). It follows that on the event tθ ă r θu, we have that Y hits 0 in finite time. Equivalently, Xpτ t q has to hit y n in finite time, since Xpτ t q has also to remain in Bpy n , r n q on tθ ă r θu and y n is the unique point of this ball where U vanishes. Recall that if X hits y n , then it has to stay there forever. Thus on the event tθ ă r θu, Xptq always stays in Bpx n , r n q and lim tÑ`8 Xptq " y n . It leads to the announced result.

Due to the time change, we cannot deduce the convergence of X to y n in finite time from the corresponding convergence of pX τt q tě0 (when it occurs). On the contrary, we believe that X never converges in finite time, as suggested by the following caricatural example.

Example 7 Let us momentarily leave the compact setting and consider the function

U : R Q x Þ Ñ x 2 .
The corresponding diffusion X on R given by (1) solves the stochastic differential equation @ t ě 0, dXptq " ´βXptqdt `|Xptq|dBptq

Assume that Xp0q ą 0 and consider σ inftt ě 0 : Xptq " 0u

While t P r0, σq, we have Xptq ą 0, so that @ t P r0, σq, dXptq " ´βXptqdt `XptqdBptq

It leads us to introduce p r Xptqq tě0 pe βt Xptqq tě0 , satisfying @ t P r0, σq, d r Xptq " r XptqdBptq whose solution is well known to be the exponential martingale

@ t P r0, σq, r Xptq " r Xp0q exppBptq ´t{2q
It follows that @ t P r0, σq, Xptq " Xp0q exppBptq ´p1 `2βqt{2q

By consequence we have σ " `8 and the process X does not hit the global minima of U in finite time. Note also that lim tÑ`8 Xptq " 0 as soon as β ą ´1{2 in accordance with the observation following Corollary 3.

This example can be transferred on the compact space R{p2πZq in the following way: consider on R{p2πZq a Morse function r U coinciding with the above U on r´π{2, π{2s and such that 0 is a global minimum of r U . Let r X be the diffusion evolving as (1), but with U replaced by r U . Assume that r Xp0q " π{4 and by contradiction that the corresponding hitting time r σ of 0 is finite with positive probability. Taking into account the Markov property, the process r X then stays inside r´π{2, π{2s and converges to 0 in finite time with a positive probability p ą 0 (since if starting from π{4, r X always hits π{2 before 0, it cannot converge to 0). It follows that if X also starts from π{4 and uses the same driving Brownian motion, then it coincides with r X for all times with probability p. This implies that X converges to zero in finite time with positive probability, a contradiction.

The fact that the diffusion given by (1) does not hit U in finite time with positive probability is probably true under the Morse assumption of this paper.

The end of the proof of Theorem 1 follows the pattern sketched at the beginning of this section. More precisely, define

r A M z Y nP N Bpy n , r n q p A Y nP N V n p mintp n : n P N u ą 0
Whatever the initial distribution of Xp0q, consider the sequences of stopping times p r θ k q kě0 and p p θ k q kě0 defined iteratively from r θ 0 " 0 via Pr@ k P Z `, r θ k ă `8s " 0

# p θ k inftt ě
The fact that a.s. there exists a random k P Z `such that r θ k " `8 ends the proof of the first statement of Theorem 1.

Concerning its second statement, note that when Xp0q P V n , for some n P N , there is a positive probability that X exits Bpy n , r n qzty n u via the boundary BBpy n , r n q.

When m ě 2, assume that the r n ą 0, for n P N , have been furthermore chosen so small so that M z \ nP N V n is connected and contains \ nP N BBpy n , r n q (the \ meaning that it is a union of disjoint sets). It follows that if Xp0q P \ nP N BBpy n , r n q, then by ellipticity of L β on the connected set M z \ nP N V n , for any n P N , we have PrXp p θ 1 q P Bpy n , r n qs ą 0 for any given n P N . Taking into account that Pr r θ 2 " `8|Xp p θ 1 q P Bpy n , r n qs ą 0, we deduce that PrXp8q " y n s ą 0. When m " 1, a similar reasoning leads to the desired result, ending the proof of Theorem 1 under (7).

Extensions

After ending the proof of Theorem 1, we show Theorem 2 and next we present the extension to generators of the form (6) and discuss the Morse assumption.

Under Assumption (2)

We end the proof of Theorem 1. The overall approach is the same but instead of considering f " U , we take f " U a , with a P p0, 1q. This exponent being fixed, we remove all the superscripts f from the notations, as in the previous section when f was equal to U . An immediate drawback with respect to the latter case is that a priori U a is not smooth. But it is not difficult to go around this problem, since U a is smooth on M zU and we are only considering our process up to the time it may reach U.

More precisely, we proceed as in the previous section, assuming that Xp0q P V n zty n u for some n P N . Instead of considering σ n given in (15), we introduce for any P p0, U pXp0qqq the stopping time

σ n, inftt ě 0 : Xptq R A n, u with A n, tx P Bpy n , r n q : U pxq ě u Remark that lim Ñ0 `σn, " σ n
The advantage of A n, is that there exist smooth functions f on M coinciding with U a on A n, . The considerations at the beginning of Section 2 can be applied to such a function f , up to the time σ n, . By letting go to 0 `, we get the following result, analogous to [START_REF] Stroock | Multidimensional diffusion processes[END_REF].

Consider the process Y given by pY ptqq tPr0,ςnq pU pXpτ t qqq tPr0,ςnq with @ t P r0, ς n q, 2 ż τt 0 U pXpsqq }∇U a pXpsqq} 2 ds " t and

ς n 2
ż σn 0 U pXpsqq }∇U a pXpsqq} 2 ds
The evolution of Y is given by

dY ptq " 1 2 F pXpτ t qq dt `dW ptq
where pW ptqq tě0 is a Brownian motion and for any x P M zC,

F pxq U a pxq }∇U a pxq} 2 ´β x∇U pxq, ∇U a pxqy U pxq }∇U a pxq} 2 "
U a pxq a 2 U 2a´2 pxq }∇U } 2 ´β aU a pxq We compute that outside C, U a " aU a´1 U `apa ´1qU a´2 }∇U } 2 so that outside C,

F " 1 a ˆU U }∇U } 2 `a ´1 ´β˙1 U a
From Lemma 5, we get that a comparison is possible with a Bessel process of asymptotic dimension (i.e. when we let go to zero in Lemma 5)

δ a " 2 `1 a ˜řiP m λ i pnq 2λ 1 pnq ´1 ´βŢ
hus under (2), by choosing a ą 0 sufficiently small, we can get δ a ă 0, ending the proof of Theorem 1.

Remark 8 Without resorting to U a , Condition (2) can also be obtained through the following observation. Coming back to the argument of the previous section, what is important for our purpose is that the Bessel process (17) can hit 0 in finite time, since this implies the same behavior for the process Y . Indeed, once X has hit y n , it cannot escape from it, so it closes our time-horizon (this is even more true when X does not hit y n in finite time as suggested by Remark 7). It remains to recall that a Bessel process of dimension δ hits 0 in finite time if and only if δ ă 2. This leads to Condition [START_REF] Chow | Hamilton's Ricci flow[END_REF]. But this argument conceals there is a negative (even as negative as we want) dimension Bessel process behind the scene.

Proof of Theorem 2

Up to now we have not taken into account the lower bound in Lemma 5. It can be used to prove there is no convergence toward U. More precisely, assume that (3) holds and let us show we cannot have lim tÑ`8 Xptq P U (except on a P-negligible set).

Indeed, the lower bound in Lemma 5 enables to make a reverse comparison between Y and the Bessel process r Y of (asymptotic) dimension

δ min nP N ř iP m λ i pnq 2λ m pnq `1 ´β
which is (strictly) larger than 2 under (3). Such a Bessel process diverges to `8 in large time without hitting 0 (starting from a positive value). It implies that the time σ n always satisfies that Xpσ n q belongs to the boundary of the ball Bpy n , r n q. If we come back to (19), we get that for any k P Z `, r θ k ă `8. In particular the set M z Y nP N Bpy n , r n q is visited again after any given time: the convergence to U is thus forbidden.

Corollary ( 3) is an immediate consequence of Theorems 1 and 2.

Remark 9 If we insist on also having β ą 0 in (3), we must assume that

min nP N ř iP m λ i pnq 2λ m pnq ą 1 (20)
Since for any n P N we have

ř iP m λ i pnq 2λ m pnq ď mλ m pnq 2λ m pnq " m 2
condition (20) is only possible for m ě 3. A little more generally, denote for any β P R,

N ´pβq # n P N : ř iP m λ i pnq 2λ m pnq ´1 ą β + N `pβq # n P N : ř iP m λ i pnq 2λ 1 pnq ´1 ă β +
From the above considerations, we see that X cannot converge to y n with n P N ´pβq, while there is a positive probability that X converges to y n for n P N `pβq. But this criterion does not strongly discriminate the elements of U, in the sense we cannot find β P R with N ´pβq ‰ H and N `pβq ‰ H, due to the inequalities @ n, n 1 P N ,

ř iP m λ i pnq 2λ m pnq ď m 2 ď ř iP m λ i pn 1 q 2λ 1 pn 1 q
We don't know if it is possible, in dimension m ě 2, to find a Morse function U , β P R and n ‰ n 1 P N such that PrXp8q " y n s ą 0 and PrXp8q " y n 1 s " 0

Further extensions

Let us first consider the case of the generator L ζ defined in [START_REF] Gall | Bessel processes, the Brownian snake and super-Brownian motion[END_REF] under Assumptions (4) and [START_REF] Ikeda | Stochastic differential equations and diffusion processes[END_REF]. Its coefficients are not globally Lipschitz but they are Lipschitz on any open subset U tx P M : U pxq ą u, with P p0, max M U q. This observation enables to construct by localization X until the first time it hits U. Furthermore the law of the process obtained in this way is uniquely determined until it leaves U , for any P p0, max M U q, due to the uniqueness of the solution of the corresponding martingale problem. The uniqueness of the law of X until it hits U follows. Taking into account that starting from U, the process X cannot move (e.g. by using that L ζ U " 0 " L ζ U 2 ), we get the announced uniqueness of X in the sense of martingale problems.

By localization also, we can construct small neighborhoods of the elements of U, where the evolution of U pXptqq can be compared with that of a Bessel process of negative dimension (as large as we wish, due to (4)), up to a time change. The arguments of Section 2 then show that Theorem 1 holds for this new diffusion X, without Assumption [START_REF] Chow | Hamilton's Ricci flow[END_REF].

The Morse assumption on U was considered for simplicity, but it can be relaxed. For instance in the cases where U consists of finite number of connected and disjoint submanifolds, say U 1 , U 2 , ..., U N , with non-degenerate Hessians of U in the orthogonal directions. Assume furthermore that for any n P N , we can find orthogonal vector fields on U n which are eigenvectors of the orthogonal Hessians. Then approximations such as (10), ( 11) and ( 12) are still valid in the corresponding exponential systems of coordinates, where m has to be replaced by the co-dimension m 1 of U n . More precisely, we can extend them into

p1 ´ q ÿ iP m 1 λ i pyq ď U pxq ď p1 ` q ÿ iP m 1 λ i pyq p1 ´ q ÿ iP m 1 λ 2 i pyqz 2 i ď }∇U } 2 pxq ď p1 ` q ÿ iP m 1 λ 2 i pyqz 2 i 1 2 p1 ´ q ÿ iP m 1 λ i pyqz 2 i ď U pxq ď 1 2 p1 ` q ÿ iP m 1 λ i pyqz 2 i
in a sufficiently small tubular neighborhood of U n , with x charted by py, zq, y standing for the Riemannian projection on U n and z pz i q iP m 1 for the coordinates in the exponential systems deduced from the eigenvectors (note that the gradient and the Laplacian of U in the directions of y are negligible). More generally, when the eigenvectors cannot be defined globally on U n , one has to work in a finite number of charts, which increases the technicality of the proofs without changing the convergence result, when β is large enough in terms of the orthogonal eigenvalues of the Hessian (or when a generator of the form (6) is considered).

A Non-fraudulent algorithms

Two examples are given below showing how fraudulent algorithms can be related to the investigation of non-fraudulent algorithms.

We start with the time-inhomogeneous swarm mean-field algorithm introduced in [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF], which was the initial motivation for this work. On a compact Riemannian manifold, consider the non-linear evolution equation

d dt ρ t " divpρ t rγ t ∇U `∇ϕ 1 pρ t qsq (21)
where • ρ t is the density with respect to the Riemannian probability of another probability on M ,

• pγ t q tě0 is an inverse temperature scheme, assumed to be smooth and to increase to `8 in large times,

• ϕ : R `Ñ R `is a strictly convex function satisfying ϕp0q " 0 and ϕ 1 p0q " ´8 and is C 2 on p0, `8q.

A non-linear diffusion Y pY ptqq tě0 is associated to this equation, whose evolution can be heuristically described as in (1) via dY ptq " ´γt ∇U pY ptqq `a2αpρ t pY ptqqq dBptq where • ρ t is the density with respect to the Riemannian probability of the law of Xptq,

• the function α : p0, `8q Ñ R `is given by @ r ą 0, αprq 1 r ż r 0 sϕ 2 psq ds

• pBptqq tě0 is a m-dimensional Brownian motion.

In [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF] we considered the convex function defined, for given m P p0, 1{2q, by

@ r ě 0, ϕ # ϕ m prq if r P p0, 1s ϕ 2 prq if r P p1, `8q
with for any m P p0, `8qzt1u, @ r ě 0, ϕ m prq r m ´1 ´mpr ´1q mpm ´1q

It was shown through new functional inequalities that at least in dimension 1, we can find power schemes pγ t q tě0 , such that for any neigborhood N of U, we have lim tÑ`8 ρ t pN q " 1 namely that the above evolutions provide a theoretical global optimization procedure for U . In practice, the evolution pρ t q tě0 should be seen as a mean-field limit and approximated by swarm particle systems (each particle "counting" the number of particles around it to get an estimate of the local density and boosting the intensity of its own Brownian motion accordingly if they are too few or too many).

In the final discussion section of [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF], an heuristic comparison was made with usual simulated annealing and it appeared that in large times and up to a time change, Y behaves like the diffusion X described by (1) with β " m{p1 ´mq.

Condition (2) may explain the restriction to dimension 1 considered in [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF] and suggests the means to go beyond it, but the relation between the swarm and fraudulent algorithms should be first investigated more closely.

Another illustrative example consists of the following simpler algorithm, which is probably less efficient than the swarm particle algorithm due to the lack of interactions between the approximating particles, called Z 1 , Z 2 , ..., Z q below. The underlying idea is to estimate the quantity U pxq ´min M U through

@ x P M, U pxq ´min M U " ´lim γÑ`8 1 γ lnpµ γ pxqq (22)
where µ γ is the density of the Gibbs measure associated to the potential U and to the inverse temperature γ ě 0:

@ x P M, µ γ pxq expp´γU pxqq ş M expp´γU pyqq pdyq
Other ways of approximating the l.h.s. of (22) can be devised, thus in [START_REF] Bolte | Swarm gradient dynamics for global optimization: the density case[END_REF] the main role is played by the stationary measure of (21) for a fixed parameter γ t , which is next sent to infinity. The convergence (22) is more classical and leads to the following natural procedure. Nevertheless other alternative approaches would deserve to be investigated.

The Gibbs measure µ γ d is the invariant (an even reversible) probability measure associated to the Markov generator ¨´γ x∇U, ∇¨y, namely to the diffusion Y pY ptqq tě0 heuristically described as in (1) through @ t ě 0, dY ptq " ´γ∇U pY ptqq dt `?2 dW ptq where W pW ptqq tě0 is a m-dimensional Brownian motion. It is well-known that the law of Y ptq converges to µ γ as t goes to infinity. To get γ going to infinity, we consider a time-inhomogeneous version Z pZptqq tě0 of Y associated to a scheme γ : R `Q t Þ Ñ γ t via @ t ě 0, dZptq " ´γt ∇U pZptqq dt `?2 dW ptq From the theory of simulated annealing, see Holley, Kusuoka and Stroock [START_REF] Holley | Asymptotics of the spectral gap with applications to the theory of simulated annealing[END_REF], it is known that for large times t ě 0, the law LpZptqq of Zptq becomes closer and closer to µ γt d if the inverse temperature scheme γ has a sufficiently slow logarithmic growth. More precisely, for a scheme of the form @ t ě 0, γ t " k ´1 lnp1 `tq

the relative entropy of LpZptqq with respect to µ γt goes to zero for large time t ě 0 when k ą c, where c ě 0 the largest height of a well not containing a given element of U (the constant c does not depend on this fixed element).

To get an approximation of the density µ γt pxq, we first consider a finite sequence Z 1 , ..., Z Q , Q P N of independent copies of Z, namely satisfying @ q P Q , @ t ě 0, dZ q ptq " ´γt ∇U pZ q ptqq dt `?2 dW q ptq where W q pW q ptqq tě0 are independent m-dimensional Brownian motions for q P Q . For Q large enough, by the law of the large numbers, we can expect that for fixed t ě 0, the empirical measure of the Z q ptq, q P Q is an approximation of the law of Zptq and thus is close to µ γt if the time t has been chosen large enough and the inverse temperature schedule according to (23) with k ą c.

Next let be given a kernel approximation of the Dirac masses: it is a family pK h p¨, ¨qq hą0 of smooth mappings on M 2 such that for any x P M , K h px, yq pdyq is a probability measure weakly converging toward δ x as h goes to 0 `(a geometrical example is the heat kernel on M at small times).

Through classical density approximation, see e.g. the book of Silverman [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF], we hope that for t ě 0 and Q large enough and h ą 0 small enough,

1 Q ÿ qP Q K h pZ q ptq, xq
is a good approximation of µ γt pxq for any x P M . In view of (22), we are led to consider a process X pXptqq tě0 defined by dXptq " ´β∇U pXptqq dt `b2V pγ t , Xptq, Z Qt ptqq dBptq where β satisfies (2) and the Brownian motion B is independent of the Brownian motions W q , for q P N, where We can assume that the potential upward jumps Q t ´Qt´a re either 0 or of size 1 and that furthermore when a jump of Q does occur at time t ě 0, then a particle is chosen among the current Q t´o nes and gives rise to a new particle at the same place. Afterward the two particles at this same place evolve independently.

V
More precisely, in addition to (23) with k ą c, we are looking for appropriate schedules Q and h such that X turns out to be a global minimizer of U , in the sense that Xptq converges a.s. for large times t ě 0 toward an element of U, which is expected to be random if U is not a singleton, according to Theorem 1. miclo@math.cnrs.fr Toulouse School of Economics, 1, Esplanade de l'université 31080 Toulouse cedex 06, France Institut de Mathématiques de Toulouse Université Paul Sabatier, 118, route de Narbonne 31062 Toulouse cedex 9, France

  pγ t , Xptq, Z Qt ptqq ˇˇln ´řqP Qt K ht pZ q ptq, Xptqq{Q ¯ˇγ t and where Q : R `Q t Þ Ñ Q t P N and h : R `Q t Þ Ñ h t are respectively non-decreasing and increasing evolutions, such that

	lim tÑ`8	Q t " `8 and	lim tÑ`8	h t " 0

* Fundings from the grants ANR-17-EURE-0010 and AFOSR-22IOE016 are acknowledged.


Laurent Miclo

On the elementary Hodge decomposition for finite Markov processes

Keywords: Elementary Hodge decompositions, compact Riemannian manifolds, vector fields, gradient fields, Poisson equation, optimal transport, finite Markov processes, finite weighted graphs primary: 60J27, secondary: 60J60, 58J65, 46E27, 37C10, 58B20

Elementary Hodge decompositions break down any vector field into a sum of a gradient field and a divergence-free vector field. Such a result is extended to finite irreducible and reversible Markov processes, where vector fields correspond to anti-symmetric functions on the oriented edges of the underlying graph.

Introduction

The elementary Hodge decomposition on a compact Riemannian manifold writes any vector field as a sum of a gradient field and a vector field whose divergence vanishes. In some sense, this decomposition corresponds to the Riemannian probability distribution and can be extended to any other probability measure admitting a positive and smooth density with respect to , with its corresponding skewed divergence, see Theorem 1 below. An interest of this extension is to explain why in the variational formulation of Benamou and Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] of the Wasserstein distance, only gradient fields are needed.

Our main goal here is to transpose this decomposition to the finite Markov process setting, see Theorem 8 in Section 3, via some geometric definitions inspired by Kenyon [9], interpreting 1-forms as anti-symmetric functions on the oriented edges of the underlying graph. The main difference with the continuous situation turns out to be that the two-sided flow of diffeomorphisms generated by a vector field has to be replaced by a one-sided flow on probability measures generated by some nonlinear Markov generators. It will enable us to revisit the works of Maas [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF] and Erbar and Maas [START_REF] Erbar | Ricci curvature of finite Markov chains via convexity of the entropy[END_REF] on optimal transport for finite Markov processes. Denote P `pV q the set of all probability measures on the finite state space V giving a positive weight to all its points. We will see furthermore that any smooth mapping P `pV q Q ρ Þ Ñ L ρ , where L ρ is an irreducible Markov generator admitting ρ as reversible measure, leads to a Riemannian structure on P `pV q which is natural in the context of finite optimal transport. But we will check that not all Riemannian structures on P `pV q are of this Markovian form, except when V has only two points.

The above decompositions are said to be "elementary Hodge" because they can be seen as generalizations of the Helmholtz decomposition, see for instance Section 3.44 of Rutherford [START_REF] Aris | Vectors, tensors and the basic equations of fluid mechanics[END_REF], while being less involved that the Hodge decomposition exposed e.g. in Chapter 6 of Warner [START_REF] Warner | Foundations of differentiable manifolds and Lie groups[END_REF] or in Bertin, Demailly, Illusie, and Peters [START_REF] Bertin | Introduction to Hodge theory[END_REF].

The plan of this note is as follows. In the next section we recall in details the elementary Hodge decompositions relative to "nice" probability measures on compact Riemannian manifolds, since we did not find a pedagogical exposition in the literature. This point of view is transferred to finite irreducible and reversible Markov processes in Section 3, which leads to the introduction of Markov-Riemannian metrics. The paper finishes with two appendices. One dealing, on finite state spaces, with a continuity property of the solutions to Poisson equations, which are at the heart of the elementary Hodge decompositions. The second appendix computes a Metropolis-Riemann distance on the two point state space.

Acknowledgments: I would particularly like to thank Jérôme Bolte and Stéphane

Villeneuve for the discussions we had about this paper, and Thăng Lê for finding mistakes in a first version.

The compact Riemannian manifold setting

A reminder of the elementary Hodge decomposition of vector fields is presented here, which will serve as a guide for the extension to the finite state space framework.

Consider M a compact and connected Riemannian manifold. Denote T M " Ů xPM T x M the corresponding tangent space, where T x M is the tangent space above x P M . Let ΣpT M q be the set of tangent vector fields on M , namely the smooth sections from M to T M .

Denote P `pM q the set of probability measures ρ on M admitting a smooth and positive density, still denoted ρ, with respect to the Riemannian probability measure . For any ρ P P `pM q, we see ΣpT M q as a tangent space above ρ and we endow it with the scalar product xx¨, ¨yy ρ given by

@ b, b 1 P ΣpT M q, @@ b, b 1 DD ρ ż M @ b, b 1 D x ρpdxq
(where x¨, ¨yx in the scalar product in the tangent space T x M ). This introduces a notion of ρorthogonality on ΣpT M q. Given a smooth function U : M Ñ R, the Riemannian gradient ∇U of U is an example of vector field. We denote G their set as U runs through all smooth functions. It appears that G is a linear sub-bundle of ΣpT M q.

A vector field b P ΣpT M q is said to leave ρ P P `pM q invariant, if @ t ě 0, ϕ t pρq " ρ where pϕ t q tPR is the flow generated by b and where for any t ě 0, ϕ t pρq is the push-forward of ρ by ϕ t . Denote by Ipρq the set of b P ΣpT M q leaving ρ invariant.

Here is the statement of the elementary Hodge ρ-decomposition of ΣpT M q:

Theorem 1 For any ρ P P `pM q, we have

ΣpT M q " G ' Ipρq
where the terms of the r.h.s. are ρ-orthogonal.

Before giving proof of this decomposition, let us recall a computational characterization of Ipρq. For any ρ P P `pM q, denote div ρ the ρ-skewed divergence defined by

@ b P ΣpT M q, div ρ pbq 1 ρ divpρbq
where divp¨q is the usual Riemannian divergence. The corresponding ρ-skewed Laplacian ρ is defined similarly @ f P C 8 pM q, ρ pf q div ρ p∇f q " pf q `x∇ lnpρq, ∇f y where is the Laplace-Beltrami operator. The second order operator ρ has several names, depending in the context in which it is used: the generalized Ornstein-Uhlenbeck diffusion generator in probability theory, the over-damped Langevin operator in analysis and the Witten Laplacian in geometry (especially concerning its extensions to differential forms).

The interest of ρ-skewed divergence is the well-known:

Lemma 2 For any fixed ρ P P `pM q, we have for any b P ΣpT M q, b P Ipρq ô div ρ pbq " 0

Proof

This is a simple consequence of Stokes' theorem. Indeed, ρ P P `pM q and b P ΣpT M q being fixed, denote ρ t ϕ t pρq for any t ě 0. We have that ρ P Ipρq if and only if for any test function f P C 8 pM q, @ t ě 0, ρ t rf s " ρrf s or equivalently @ t ě 0, B t ρ t rf s " 0 It leads us to compute B t | t"0 ρ t rf s, since B t ρ t rf s can be computed similarly at any time t ě 0, replacing ρ by ρ t (which is well-known to belong to P `pM q too).

We have by definition of the flow,

B t | t"0 ρ t rf s " B t | t"0 ż f pϕ t pxqq ρpdxq " ż xb, ∇f y dρ " ż xρb, ∇f y d " ´ż divpρbqf d " ´ż div ρ pbqf dρ
Since the density ρ is positive, this expression vanishes for all f P C 8 pM q if and only div ρ pbq " 0, as desired.

We can now come to the

Proof of Theorem 1

The elements ρ P P `pM q and b P ΣpT M q being fixed, we consider the Poisson equation in U :

" ρ pU q " div ρ pbq rU s " 0 (1)
This equation is well-known to admit a unique solution if and only if ρrdiv ρ pbqs " 0. We compute ρrdiv ρ pbqs "

ż div ρ pbq dρ " ż divpρbq d " 0
where Stokes' theorem has been invoked again.

Consider U the unique solution of (1) and define β b ´∇U . We have div ρ pβq " div ρ pb ´∇U q " div ρ pbq ´ ρ pU q " 0 by construction of U . It remains to check that for any ∇U P G and any β P Ipρq are ρ-orthogonal. We compute 1), for given ρ P P `pM q and b P ΣpT M q. For x P M , consider pX ρ x psqq sě0 a diffusion of generator L ρ starting from x. We have the probabilistic representation

U pxq " ´ż `8 0 Erdiv ρ pbqpX ρ x qpsqs ds (2)
where the integrant converges exponentially fast to 0 with respect to s, as the spectral gap of ρ can be bounded below uniformly in terms of the supremum norm of lnpρq (see also Appendix A, where this property will be developed in the finite state space setting). Girsanov formula relates explicitly the law of X ρ x r0, ss pX ρ x puqq uPr0,ss to that of the Riemannian Brownian motion X 1

x r0, ss, for any s ě 0, by stating that for any measurable bounded function F on the M -valued trajectories over the time interval r0, ss,

ErF pX ρ x r0, ssqs " E " F pX 1 x r0, ssq exp ˆż s 0 @ ∇ lnpρqpX 1 x pvqq, dX 1 x pvq D ´1 2
ż s 0 |∇ lnpρqpX 1 x pvqq| 2 dv ˙ " E " F pX 1 x r0, ssq exp ˆlnpρqpX 1 x psqq ´lnpρqpxq ´1 2 ż s 0 lnpρqpX 1 X pvqq `|∇ lnpρqpX 1 x pvqq| 2 dv

˙

(where the scalar product and the norms are taken above X 1 X pvq). In conjunction with (2), it can be deduced that the mapping P `pM q Q ρ Þ Ñ U P C 8 pM q is regular, when P `pM q is endowed with the topology inherited from C 8 pM q.

Let us give a classical consequence of the elementary Hodge decomposition of Theorem 1 concerning the introduction of a (infinite-dimensional) Riemannian-like structure on P `pM q as in Ambrosio, Gigli and Savaré [START_REF] Ambrosio | Gradient flows in metric spaces and in the space of probability measures[END_REF].

A (smooth) curve r0, 1s Q t Þ Ñ ρ t P P `pM q (for the topology inherited from C 8 pM q) is said to be generated by a (smooth) curve r0, 1s Q t Þ Ñ b t P ΣpT M q of vector fields when @ t P r0, 1s, ρ t " ϕ t pρ 0 q

where the time-inhomogenous flow pϕ t q tPr0,1s is defined through @ t P r0, 1s, @ x P M, d dt ϕ t pxq " b t pϕ t pxqq (starting with ϕ 0 being the identity mapping). When there is a (smooth) curve r0, 1s Q t Þ Ñ U t P C 8 pM q of smooth functions such that furthermore

@ t P r0, 1s, b t " ∇U t
we say pρ t q tPr0,1s is generated by a (smooth) curve of gradient fields.

Generation by vector fields is in fact equivalent to generation by gradient fields:

Proposition 4 Assume that pρ t q tPr0,1s is generated by the vector field curve pb t q tPr0,1s . Then it is also generated by the gradient field curve p∇U t q tPr0,1s , where for any t P r0, 1s, ∇U t comes from the elementary Hodge decomposition of b t above ρ t : b t " ∇U t `βt with β t P Ipρ t q. Furthermore p∇U t q tPr0,1s is the only gradient field curve generating pρ t q tPr0,1s .

Proof

Taking into account Remark 3, we get r0,

1s Q t Þ Ñ ∇U t is as smooth as r0, 1s Q t Þ Ñ b t .
Denote by pr ρ t q tPr0,1s the flow generated by the gradient fields p∇U t q tPr0,1s . Consider a test function f P C 8 pM q, we have for any t P r0, 1s,

B t ρ t rf s " B t ż f pϕ t pxqq ρpdxq " ż xb t , ∇f y ϕtpxq ρpdxq " ż xb t , ∇f y x ρ t pdxq
" ´ż f div ρt pb t q dρ t " ´ż f div ρt p∇U t q dρ t (4)

" B t r ρ t rf s
By integration, it follows that pρ t q tPr0,1s coincides with pr ρ t q tPr0,1s . Assume there is another gradient field curve p∇ r U t q tPr0,1s generating pρ t q tPr0,1s . According to (4), we have for any t P r0, 1s and any test function f P C 8 pM q, ż f div ρt p∇U t q dρ t "

ż f div ρt p∇ r U t q dρ t
It follows that for any given t P r0, 1s, ż A ∇f, ∇pU t ´r U t q E dρ t " 0 so that taking f " U t ´r U t , we get ∇pU t ´r U t q " 0. Since this is true for any t P r0, 1s, it means the two gradient field curves p∇U t q tPr0,1s and p r ∇U t q tPr0,1s coincide.

Remark 5 To make evolve the boundary BA of a smooth domain A in M , one usually resorts to a T pM q-valued vector field on BA and "pushes the boundary points" according to this vector field. It is well-known, see e.g. Mantegazza [START_REF] Mantegazza | Lecture notes on mean curvature flow[END_REF], that it is sufficient to consider vector fields that are normal to BA, because their tangential components leave BA invariant (and just act as an infinitesimal reparametrization). Proposition 4 is a result analogous to this orthogonal decomposition of vector fields on BA into normal and tangential components. In fact we believe that both the elementary Hodge decomposition and the normal and tangential decomposition are two instances of a more general result for measures on M (where BA would be identified with the Hausdorff trace of on BA) that is outside the scope of the present note. To go in the direction of a Riemannian-type distance on P `pM q, we have to define the length of a curve. We start by associating to ρ 0 P P `pM q and to a curve of vector fields pb t q tPr0,1s the quantity Lpρ 0 , pb t q tPr0,1s q

d ż 1 0 }b t } 2 ρt dt (5)
where pρ t q tPr0,1s is deduced from ρ 0 and pb t q tPr0,1s via (3). Next, if pρ t q tPr0,1s is a curve in P `pM q, we define Lppρ t q tPr0,1s q inf Lpρ 0 , pb t q tPr0,1s q : pb t q tPr0,1s P Bppρ t q tPr0,1s q (

where Bppρ t q tPr0,1s q stands for the set of vector field curves generating pρ t q tPr0,1s .

Lemma 6 Let pρ t q tPr0,1s be a curve in P `pM q generated by a vector field curve. Consider p∇U t q tPr0,1s the unique gradient field curve generating pρ t q tPr0,1s according to Proposition 4. We have Lppρ t q tPr0,1s q " Lpρ 0 , p∇U t q tPr0,1s q

Proof

Consider any vector field curve pb t q tPr0,1s generating pρ t q tPr0,1s and decompose it as in Proposition 4.

The orthogonality property of Theorem 1 then shows that

@ t P r0, 1s, }b t } 2 ρt " }∇U t } 2 ρt `}β t } 2 ρt implying that
Lpρ 0 , pb t q tPr0,1s q ě Lpρ 0 , p∇U t q tPr0,1s q

This shows that the infimum of ( 6) is attained at the unique gradient field generating pρ t q tPr0,1s .

The last step in constructing a Riemannian-like distance D on P `pM q is to define, for any ρ 0 , ρ 1 P P `pM q, Dpρ 0 , ρ 1 q inftLppρ t q tPr0,1s q : pρ t q tPr0,1s P Rpρ 0 , ρ 1 qu

where Rpρ 0 , ρ 1 q is the set of curves in P `pM q, starting at ρ 0 and ending at ρ 1 , and generated by vector field curves. Lemma 6 shows that in this definition, it is sufficient to consider gradient field curves, thus enabling us to recover the variational formulation of Benamou and Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF] in terms of gradient field curves. It turns out that D is a Wasserstein distance, but we will not go further in this direction.

The finite Markov process setting

We propose here a version of Theorem 1 valid for finite Markov processes (as a first step toward a full Markov process extension?).

The Riemannian structure of M can be entirely encapsulated into the Laplace-Beltrami operator . By analogy, a finite framework consists in an irreducible Markov generator L pLpx, yqq x,yPV whose invariant probability π is supposed to be reversible. Denote V the underlying finite state space. It is endowed with a graph structure, by defining its edge set as

E tpx, yq P V 2 : Lpx, yq ą 0u (7)
Note that the edges are directed and that by reversibility we have @ x, y P V, px, yq P E ô py, xq P E Thus it could be tempting to consider the corresponding set of undirected edges. It is more convenient to choose an orientation for any undirected edge. More precisely we consider a set E Ă E, such that for any px, yq P E, either px, yq P E or py, xq P E, but not both px, yq and py, xq belong to E.

A function F : E Ñ R is said to be a vector field if and only if @ px, yq P E, F px, yq " ´F py, xq

We denote by ΣpEq the set of vector fields on the graph pV, Eq. Note that it is in natural bijection with R E the set of mapping from E to R. This definition is inspired by Kenyon [START_REF] Kenyon | Spanning forests and the vector bundle Laplacian[END_REF] (see also Remark 12 below). The latter paper also writes L in a form analogous to " div ˝∇ in the Riemannian setting.

More precisely, given a function f : V Ñ R (whose space is denoted R V ), define the gradient of f as the vector field given by @ px, yq P E, ∇f px, yq f pyq ´f pxq (8)

Endow V with the probability measure π and E with the measure µ defined by @ px, yq P E, µpx, yq πpxqLpx, yq

The operator ∇ can be seen as going from L 2 pπq to L 2 pµq. By definition, the divergence div is the opposite of the adjoint operator to ∇. Then we can write again:

L " div ˝∇ (10)
Denote G the set of vector fields which are gradients.

Pursuing our analogies with the Riemannian case, let P `pV q stands for all probability measures giving a positive weight to all points of V . Consider F P ΣpEq, to make it act on elements of P `pV q, consider the Markov generator L F associated to F via

@ x ‰ y P V, L F px, yq F `px, yqLpx, yq (11)
where we adopt the convention

@ px, yq R E, F px, yq " 0 (12)
and where F `px, yq stands for the non-negative part of F px, yq (the entries of the diagonal of L F are such that the row sums all vanish).

Remark 7

The Markov processes X F generated by L F mimick, as much as possible, dynamical systems generated by vector fields. In particular edges can be crossed only in one direction. Note that if F is a gradient ∇f , then the jumps of X F (strictly) increase f and it follows that X F converges in finite but random time toward a (random) local maxima of f . Recall that x P V is a local maxima for f (with respect to the neighborhood structure given by E) when for any px, yq P E, we have f pyq ď f pxq. The Markov generator L F enables to associate to F the flow pϕ t q tě0 acting on P `pV q via @ ν P P `pV q, @ t ě 0, ϕ t pνq ν expptL F q (13)

Contrary to the Riemannian case, we cannot consider negative times if we want to stay in P `pV q.

The other major difference is that there is no underlying dynamical system acting on the points of V . Instead, it must be replaced by the Markov process generated by L F (whose time-marginal distribution are the pϕ t pνqq tě0 when the initial distribution is ν). We say that a vector field F P ΣpEq leaves our fixed reversible probability π invariant if and only if @ t ě 0, ϕ t pπq " π Denote again by Ipπq the set of F P ΣpEq leaving π invariant.

Let us define a scalar product on ΣpEq, seen as a tangent space to P `pV q above π P P `pV q, to get a notion of π-orthogonality. We define the scalar product xx¨, ¨yy π on ΣpEq through @ F, F 1 P ΣpEq, @@ F, F 1 DD π "

ÿ xPV @ F, F 1 D x πpxq
where

@ x P V, @ F, F 1 P ΣpEq, @ F, F 1 D x ÿ yPV ztxu F px, yqF 1 px, yqLpx, yq
Namely, we have

@ F, F 1 P ΣpEq, @@ F, F 1 DD π " ÿ x‰yPV F px, yqF 1 px, yqπpxqLpx, yq
(this quantity can also be identified with 2 xF, F 1 y L 2 pµq , where µ is defined in ( 9)).

We have the analogue of Theorem 1, but restricted to the probability π:

Theorem 8 We have ΣpEq " G ' Ipπq
where the terms of the r.h.s. are π-orthogonal.

Let us compute the divergence, as in Kenyon [START_REF] Kenyon | Spanning forests and the vector bundle Laplacian[END_REF], who used the following explicit form to deduce [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF].

Lemma 9

We have for any F P ΣpEq: The desired formula follows.

@ x P V, divpF qpxq " ÿ yPV F px, yqLpx, yq (14)
We deduce the analogue of Lemma 2, at least for ρ " π:

Lemma 10 We have for any F P ΣpEq, F P Ipπq ô divpF q " 0 Proof Consider a vector field F satisfying divpF q " 0. It is equivalent to the fact that for any f P R V , we have πrf divpF qs " 0. We compute, taking into account the convention [START_REF] Miclo | Processus de Markov inhomogènes finis[END_REF], the reversibility of π for L and the anti-symmetry of F , and the desired equivalence follows.

πrf
Now we have at our disposal all the ingredients necessary to the

Proof of Theorem 8

The arguments are exactly the same as those of the proof of Theorem 1. The vector field F P ΣpEq being fixed, we consider the Poisson equation in U :

" LpU q " divpF q πrU s " 0 (16)
This equation is well-known to admit a unique solution if and only if πrdivpF qs " 0. From (15) and writing 1 for the constant function taking the value 1, we get πrdivpF qs " ´πrL F r1ss " 0 Consider U the unique solution of ( 16) and define G b ´∇U . We have divpGq " divpF ´∇U q " divpF q ´LpU q " 0 by construction of U .

It Of course, Theorem 8 can be extended to any ρ P P `pV q, it is sufficient to be given a corresponding irreducible generator L ρ admitting ρ as reversible probability measure and to consider all the above related notions. Let us assume that the corresponding graph pV, Eq remains the same, which amounts to assuming there is a function ρ : E Ñ p0, `8q such that @ px, yq P V 2 , x ‰ y, L ρ px, yq " ρpx, yqLpx, yq (when px, yq R E, x ‰ y, the values of ρpx, yq are irrelevant since Lpx, yq " 0, we can take for instance ρpx, yq " 0). The reversibility of ρ is equivalent to

@ px, yq P E, δ ρ pxqρpx, yq " δ ρ pyqρpy, xq (17)
where δ ρ is the density of ρ with respect to π:

@ x P V, δ ρ pxq ρpxq πpxq
Remark 11 Maas in [START_REF] Maas | Gradient flows of the entropy for finite Markov chains[END_REF] also "extends" the probability ρ into a function ρ of two variables of the state space (rather corresponding to the sides of ( 17)). He makes further assumptions, in particular that there exists a function θ : p0, `8q 2 Ñ p0, `8q such that ρpx, yq " θpρpxq, ρpyqq, which are not necessary for our purposes. The definition of the gradient remains the same, but in [START_REF] Kenyon | Spanning forests and the vector bundle Laplacian[END_REF] we have to consider @ px, yq P E, µ ρ px, yq ρpxqL ρ px, yq with the corresponding notion of divergence div ρ , so that L ρ " div ρ ˝∇. Definition [START_REF] Mantegazza | Lecture notes on mean curvature flow[END_REF] has to be replaced by @ x ‰ y P V, L ρ,F px, yq pF px, yqq `Lρ px, yq " pF px, yqq `ρpx, yqLpx, yq

The set Ipρq can be seen as the set of vector fields F leaving ρ invariant, with respect to the linear flow pϕ ρ,t q tě0 defined, as in [START_REF] Warner | Foundations of differentiable manifolds and Lie groups[END_REF], by @ ν P P `pV q, @ t ě 0, ϕ t pνq ν expptL ρ,F q but it seems more natural (cf. (24) below) to see Ipρq as the set of vector fields F leaving ρ invariant, with respect to the non-linear flow pψ t q tě0 described by its evolution:

@ ν P P `pV q, @ t ě 0, B t ψ t pνq " ψ t pνqL ψtpνq,F (19)
(and starting with ψ 0 pνq " ν). This non-linearity is a true discrepancy with respect to the Riemannian situation.

Remark 12

The fact that Definition (8) does not depend on L nor ρ, suggests, as in Kenyon [START_REF] Kenyon | Spanning forests and the vector bundle Laplacian[END_REF], that it corresponds more to a 1-form than to a gradient, in analogy with differential geometry, where the differential of a function does not depend on the Riemannian structure, contrary to the gradient. Thus it seems Hodge decompositions would be more natural for differential form fields than for vector fields. In the Riemannian setting, vector fields are important to describe corresponding dynamical systems, reason why we prefer to work with them. In the finite Markov setting, this link is distorted by the mapping F Þ Ñ L ρ,F , so we should probably adopt the 1-form terminology. Finally the scalar product xx¨, ¨yy ρ on ΣpEq should be defined through @ F, F 1 P ΣpEq, @@ F, F 1 DD ρ "

ÿ x‰yPV F px, yqF 1 px, yqρpxqL ρ px, yq (20)
leading to the notion of ρ-orthogonality on ΣpEq.

With these definitions, Theorem 8 extends immediately into

Theorem 13 For any ρ P P `pV q, we have

ΣpEq " G ' Ipρq
where the terms of the r.h.s. are ρ-orthogonal.

Another difference with the Riemannian case is the choice of the L ρ for ρ P P `pV q, role which previously were "naturally" played the ρ for ρ P P `pM q. A classical choice is to consider the Metropolis generators, which corresponds to @ ρ P P `pV q, @ px, yq P E, ρpx, yq " min ˆ1, ρpyqπpxq πpyqρpxq ˙" min ˆ1, δ ρ pyq δ ρ pxq

˙(21)

which satisfies (17), since @ px, yq P E, δ ρ pxqρpx, yq " minpδ ρ pxq, δ ρ pyqq (

(there is a relation between this construction of L ρ from L and ρ and that of ρ from and ρ, since they both correspond to the minimization of some trajectorial entropy, see [START_REF] Diaconis | On characterizations of Metropolis type algorithms in continuous time[END_REF]).

The favorite choice of Erbar and Maas [START_REF] Erbar | Ricci curvature of finite Markov chains via convexity of the entropy[END_REF], to extend the notions of Ricci lower bounds and their consequences for functional inequalities of finite Markov processes, is @ ρ P P `pV q, @ px, yq P E, δ ρ pxqρpx, yq " δ ρ pyq ´δρ pxq lnpδ ρ pyqq ´lnpδ ρ pxqq (23)

Whatever the choice, some regularity of the mapping P `pV q Q ρ Þ Ñ L ρ P R V ˆV must be assumed for the considerations of Remark 3 to hold (for more details in this respect see the following appendix). For instance let us assume this mapping is locally Lipschitzian (seeing P `pV q as a subset of p0, 1q V ), condition which also insures the needed local existence and uniqueness of the solution to (19). Note that both ( 22) and ( 23) satisfy this condition. Proposition 4 and Lemma 6 are then also valid in the finite setting, via the same proofs. Indeed, it is sufficient to extend the notion of generation by vector or gradient field curves via: a continuous curve r0, 1s Q t Þ Ñ ρ t P P `pV q is said to be generated by a continuous curve r0, 1s Q t Þ Ñ F t P ΣpEq of vector fields when @ t P r0, 1s,

9 ρ t " ρ t L ρt,Ft (24)
We say furthermore that r0, 1s Q t Þ Ñ ρ t P P `pV q is generated by a continuous gradient field curve, when F t belongs to G for all t P r0, 1s. Then Proposition 4 and Lemma 6 extend literally to the finite Markov setting.

More precisely, we are led to introduce as in ( 5), for any ρ 0 P P `pV q and any continuous curve r0, 1s Q t Þ Ñ F t P ΣpEq of vector fields, Lpρ 0 , pF t q tPr0,1s q

d ż 1 0 }F t } 2 ρt dt
where pρ t q tPr0,1s is the solution of (24). Next, as in ( 6), when pρ t q tPr0,1s is a continuous curve in P `pM q, we define Lppρ t q tPr0,1s q inf Lpρ 0 , pF t q tPr0,1s q : pF t q tPr0,1s P Bppρ t q tPr0,1s q ( where Bppρ t q tPr0,1s q stands for the set of continuous vector field curves generating pρ t q tPr0,1s . We get then that if Bppρ t q tPr0,1s q ‰ H, then Lppρ t q tPr0,1s q " Lpρ 0 , p∇U t q tPr0,1s q where p∇U t q tPr0,1s is the unique gradient field curve generating pρ t q tPr0,1s . By the usual convention, when Bppρ t q tPr0,1s q " H, we take Lppρ t q tPr0,1s q " `8. Following a traditional path, we construct a Riemannian-like distance D on P `pM q by defining, for any ρ 0 , ρ 1 P P `pM q, Dpρ 0 , ρ 1 q inftLppρ t q tPr0,1s q : pρ t q tPr0,1s P Rpρ 0 , ρ 1 qu (25

)
where Rpρ 0 , ρ 1 q is the set of continuous curves in P `pM q, starting at ρ 0 and ending at ρ 1 .

To check this distance takes finite values, we have to show that Rpρ 0 , ρ 1 q contains at least one curve generated by a continuous vector field. The following result is the main step in this direction.

Lemma 14 Let be given ρ P P `pV q and a signed measure η P HpV q with HpV q # η pηpxqq xPV P R V :

ÿ xPV ηpxq " 0 +
Then there exists a unique function U P R V with ř xPV U pxq " 0 and such that

η " ρL ρ,∇U (26)
Furthermore the mapping pρ, ηq Þ Ñ U is continuous.

Proof

Equation (26) amounts to where the Markov generator r L ρ is defined via

@ x P V,
@ x ‰ y P V, r L ρ px, yq ρpyqL ρ py, xq (29)
(and the diagonal of r L ρ is such that all the row sums vanish). Note that r L ρ is a symmetric matrix so its reversible measure is the uniform distribution υ over V . Since r L ρ is irreducible, υ is also its unique invariant measure. These observations show that U is the unique solution of the Poisson equation " r L ρ pU q " η υrU s " 0 (30)

The continuity of U in pρ, ηq is obtained as in the proof of Proposition 16 in Appendix A.

The previous lemma proves that any C 1 curve pρ t q tPr0,1s in P `pV q is generated by the continuous gradient field p∇U t q tPr0,1s , where for any t P r0, 1s, ∇U t is obtained as in (26), where η is replaced by 9 ρ t and ρ by ρ t . In particular Rpρ 0 , ρ 1 q ‰ H, for any ρ 0 , ρ 1 P P `pV q.

The fact that in (26), η " 0 is equivalent to ∇U " 0 implies that D defined in ( 25) is a genuine Riemannian distance on P `pV q. Indeed, from the previous definitions, the scalar product above ρ P P `pV q of two tangent vectors η, η 1 P HpV q is given by

@@@ η, η 1 DDD ρ @@ ∇U, ∇U 1 DD ρ ( 31
)
where ∇U and ∇U 1 are the respective unique solutions to (26) and to η 1 " ρL ρ,∇U 1 .

The particular case where pL ρ q ρPP `pV q correspond to the Metropolis construction (starting from a given irreducible and fixed couple pπ, Lq) could be called the Metropolis-Riemann structure of P `pV q. In Appendix B we compute the associated distance D when V has two points and the jump rates of L are both equals to 1.

In general, let us compute more explicitly the scalar product given in (31):

Lemma 15 For any ρ P P `pV q and any η, η 1 P HpV q, we have

@@@ η, η 1 DDD ρ " ÿ x‰yPV r
A ρ px, yqpηpyq ´ηpxqqpη 1 pyq ´η1 pxqq with r A ρ p r A ρ px, yqq x,yPV the matrix given by

@ x, y P V, r A ρ px, yq 2
ż r0,`8q r P ρ,t px, yq ´1 |V | dt (32)
where @ t ě 0, r P ρ,t exppt r L ρ q (recall that the Markov generator r L ρ was defined in (29), that it is reversible with respect to the uniform distribution υ " 1 |V | and that the r.h.s. is absolutely convergent since the integrant is converging exponentially fast to zero).

Proof

By definition, we have for any ρ P P `pV q, @@ ∇U, ∇U 1 DD ρ "

ÿ x‰yPV ρpxqL ρ px, yqpU pyq ´U pxqqpU 1 pyq ´U 1 pxqq " ÿ x‰yPV r L ρ px, yqpU pyq ´U pxqqpU 1 pyq ´U 1 pxqq " ÿ xPV r L ρ rpU ´U pxqqpU 1 ´U 1 pxqqspxq Note that r L ρ rpU ´U pxqqpU 1 ´U 1 pxqqs " r L ρ rU U 1 s ´U pxq r L ρ rU 1 s ´U 1 pxq r L ρ rU s so we deduce, taking into account the reversibility of υ for r L ρ xx∇U, ∇U 1 yy ρ |V | " υr r L ρ rU 2 s ´U r L ρ rU 1 s ´U 1 r L ρ rU ss " ´υrU r L ρ rU 1 ss ´υrU 1 r L ρ rU ss " ´2υrU r L ρ rU 1 ss " 2υrU η 1 s
according to (26), where η and U are replaced by η 1 and U 1 .

Recall that the solution of (30) is given by

@ x P V, U pxq " ż `8 0 Erηp r X ρ,x ptqqs dt
where r X ρ,x p r X ρ,x ptqq tě0 is a Markov process of generator r L ρ starting from x P V . Taking into account that η P HpV q, the r.h.s. can written

ż `8 0 Erηp r X ρ,x ptqqs ´υrηs dt " ż `8 0 r P ρ,t rηspxq ´1 |V | ÿ yPV ηpyq dt " ÿ yPV ηpyq ż `8 0 ˆr P ρ,t px, yq ´1 |V | ˙dt It follows that @@ ∇U, ∇U 1 DD ρ " 2 ÿ x,yPV η 1 pxqηpyq ż `8 0 ˆr P ρ,t px, yq ´1 |V | ˙dt " 2 ÿ x,yPV r A ρ px, yqη 1 pxqηpyq
Note that r A ρ p r A ρ px, yqq x,yPV is a symmetric matrix, since the same is true for r L ρ and thus for r P ρ,t for any t ě 0. Furthermore we have

@ x P V, ÿ yPV ˆr P ρ,t px, yq ´1 |V | ˙" 0
and by symmetry

@ y P V, ÿ xPV ˆr P ρ,t px, yq ´1 |V | ˙" 0 It follows that @ x P V, ÿ yPV A ρ px, yq " 0 " ÿ yPV A ρ py, xq
and the announced result follows.

Consider any scalar product, xxx¨, ¨yyy on HpV q. It can be extended into a semi-definite scalar product on R V , still written xxx¨, ¨yyy, by imposing that 1, the vector whose entries are all equal to 1, is orthogonal to HpV q and that xxx1, 1yyy " 0. Consider A pApx, yqq x,yPV the associated symmetric matrix. It is a non-negative matrix of rank |V | ´1 and all the row and column sums vanish and we can write @ η, η 1 P HpV q, @@@ η, η 1 DDD "

ÿ x‰yPV Apx, yqpηpyq ´ηpxqqpη 1 pyq ´η1 pxqq
Any Riemannian structure on P `pV q is thus equivalent to the datum of a smooth mapping

P `pV q Q ρ Þ Ñ A ρ P A ( 33
)
where A is the space of all symmetric non-negative matrices of rank |V | ´1 whose row and column sums all vanish.

It is natural to wonder if all Riemannian structures on P `pV q come from a smooth family pL ρ q ρPP of irreducible Markov generators, respectively reversible with respect to the ρ. Or equivalently, if the mapping (33) is constructed, as in Lemma 15, from a family p r L ρ q ρPP of irreducible Markov generators reversible with respect to the uniform distribution υ. Let us call these metric structures Markov-Riemannian.

To investigate the existence of non-Markov-Riemannian structures, we consider a generic A P A and we wonder if we can find on V an irreducible Markov generator r L reversible with respect to υ such that A " r A p r Apx, yqq x,yPV with @ x, y P V, r Apx, yq 2

ż r0,`8q exppt r Lqpx, yq ´1 |V | dt
Consider a spectral decomposition of ´r L: p r λ n , r ϕ n q nP 0,|V |´1 , where p r ϕ n q nP 0,|V |´1 is an orthogonal basis of R V for its usual scalar product, where @ n P 0, |V | ´1 , r Lr r ϕ n s " ´r λ n r ϕ n and where r λ 0 " 0 and r ϕ 0 " 1.

It appears that a spectral decomposition of r

A is pλ n , r ϕ n q nP 0,|V |´1 , where

@ n P 0, |V | ´1 , λ n # 0 , if n " 0 2 r λn , otherwise
We are thus led to the following question. Consider an orthogonal basis pϕ n q nP 0,|V |´1 of R V , with ϕ 0 " 1. Let be given positive numbers pλ n q nP |V |´1 and take λ 0 " 0. The matrix of the operator A : R V Ñ R V described by

@ n P 0, |V | ´1 ,
Arϕ n s " λ n ϕ n corresponds to a generic element of A. When is the operator r L defined by r Lrϕ 0 s " 0 and

@ n P |V | ´1 , r Lrϕ n s " ´2 λ n ϕ n (34)
a Markov generator? It amounts to check that the off-diagonal entries of r L are non-negative. This problem is related to the determination of Markov sequences, see Definition 2.3 of Bakry and Huet [START_REF] Bakry | The hypergroup property and representation of Markov kernels[END_REF] and to the hypergroup property of the basis pϕ n q nP 0,|V |´1 .

When |V | " 2, the operator r L defined by (34) is always a Markov generator, since it is given by r L " ˆ´1{λ 1 1{λ 1 1{λ 1 ´1{λ 1

Ḃut

as soon as |V | ě 3, it is well-known that r L defined by (34) may not be a Markov generator. Here is an example with V " t1, 2, 3u (which can be extended to any V with |V | ě 3). We take

ϕ 0 " ¨1 1 1 ' ϕ 1 " ¨1 ´2 1 ' ϕ 2 " ¨´1 0 1 ' Consider r
L described by (34), with λ 1 , λ 2 ą 0 to be chosen later. Introduce the function

f 2ϕ 0 `ϕ1 `3ϕ 2 " ¨0 0 6 ' If r
L was to be Markovian we would have

@ t ě 0, f t 2ϕ 0 `expp´2t{λ 1 qϕ 1 `3 expp´2t{λ 2 qϕ 2 ě 0
In particular we should have B t f t p1q| t"0 ě 0. But we compute that

B t | t"0 f t p1q " ´2 λ 1 `6 λ 2
quantity which is negative with λ 1 " 2 and λ 2 " 7.

A Continuity of the solution to the Poisson equation

The purpose of this appendix is to show that the solution U of ( 16) is continuous in terms of F, L and π.

On the finite set V , let RpV q be the set of couples pπ, Lq consisting of an irreducible Markov generator L reversible with respect to the probability measure π. Endow V with a total order ď and consider

Ý Ñ V tpx, yq P V 2 : x ă yu
The mapping

RpV q Q pπ, Lq Þ Ñ ppπpxqq xPV , pLpx, yqq px,yqP Ý Ñ V q P p0, 1q V ˆr0, `8q

Ý Ñ V
is a bijection on its image and enables us to endow RpV q with a natural topology. Let ΣpV 2 q be the set of general vector fields, which are the functions F :

V 2 Ñ R satisfying @ px, yq P V 2 , F px, yq " ´F py, xq (35)
(in particular F vanishes on the diagonal). Again, ΣpV 2 q is endowed with the topology inherited from

R Ý Ñ V .
The divergence associated to L is the mapping transforming any vector field F P ΣpV 2 q into the function div L pF q defined on V via

@ x P V, div L pF qpxq " ÿ yPV F px, yqLpx, yq
For any vector field F P ΣpV 2 q and any pπ, Lq P RpV q, consider the Poisson equation in the unknown function U L,F described by

"

LpU L,F q " div L pF q πrU L,F s " 0 (36) By reversibility of π for L and by the anti-symmetry property (35), we have πrdiv L pF qs " 0 so there is a unique solution U L,F to (36). Our main result here is:

Proposition 16 The mapping

ΣpV 2 q ˆRpV q Q pF, π, Lq Þ Ñ U L,F P R V is continuous.

Proof

Recall the probabilistic representation of U L,F :

@ x P V, U L,F pxq " ´ż `8 0 Erdiv L pF qpX x ptqqs dt (37)
where X x pX x ptqq tě0 ) stands for a left-limit and right-continuous Markov process starting from x and admitting L (resp. L) as generator.

To see the r.h.s. of (37) is well-defined, introduce the spectral gap of L:

λpLq min " ´πrf Lrf ss πrf 2 s : f P R V zt0u, πrf s " 0 *
which is the smallest non-zero eigenvalue of ´L (which is diagonalizable in R `by reversibility). We have ΛpLq ą 0 by irreducibility of L. For x P V and t ě 0, denote m x,t the law of X x ptq, seen as a row vector. Using matrix product, we have @ t ě 0, m x,t " m x,0 expptLq and by duality, il follows that @ t ě 0, m x,t π " expptLq " m x,0 π ı where the densities mx,t π and m x,0 π are seen as a function, thus represented by column vectors. We deduce that for any test function f P R V , @ t ě 0, |m x,t rf s ´πrf s| " ˇˇπ "´m

x,t π ´1¯f ıˇˇď d π " ´mx,t π ´1¯2  a πrf 2 s " d π " ´expptLq " m x,0 π ´1ı¯2  a πrf 2 s ď expp´λpLqtq d π " ´mx,0 π ´1¯2  a πrf 2 s " expp´λpLqtq g f f e π « ˆδx π ´1˙2 ff a πrf 2 s ď d πrf 2 s πpxq expp´λpLqtq
Applying this bound with f " div L pF q, we get @ x P V, @ t ě 0, |Erdiv L pF qpX x ptqqs| " |m x,t rdiv L pF qs ´πrdiv L pF qs| ď d πrdiv L pF q 2 s πpxq expp´λpLqtq which shows that the integral in (37) is absolutely converging. It is well-known, see for instance Kato [START_REF] Kato | Perturbation theory for linear operators[END_REF], that the mapping

RpV q Q pπ, Lq Þ Ñ λpLq P p0, ` 8q
is continuous. More precisely, to come back to the symmetric setting of Chapter 2 Section 5 of Kato [START_REF] Kato | Perturbation theory for linear operators[END_REF], note that λpLq is also the spectral gap of the symmetric matrix pLpx, yq a πpxq{πpyqq x,yPV . It follows we can apply the convergence under integral theorem to get the desired continuity from (37).

The previous result enables us to extend Proposition 4 to the finite setting, by showing that continuous curve r0, 1s Q t Þ Ñ ρ t P P `pV q generated (in the sense of (24)) by a continuous vector field curve is also generated by a continuous gradient vector field curve. Proposition 4 is even more than what we need. Indeed in Section 3, we fixed an element pπ, Lq of RpV q and only considered the other elements pr π, r Lq P RpV q sharing with pπ, Lq the same oriented edge set E defined in [START_REF] Erbar | Ricci curvature of finite Markov chains via convexity of the entropy[END_REF]. We end up with the previous set RpV q only when E coincides with V 2 minus its diagonal. Otherwise, the set of such elements pr π, r

Lq is a proper subset RpEq of RpV q. Of course by restriction, Proposition 16 is also valid if RpV q is replaced by RpEq.

The interest of RpEq is that a Girsanov formula holds between its elements, a finite setting analogue of Remark 2. More precisely, let pr π, r Lq P RpEq and denote r X x p r X x ptqq tě0 be a left-limit and rightcontinuous Markov process starting from x and admitting r L as generator. Then for any T ě 0, the laws

B On the two point state space

The goal of this appendix is to compute a Metropolis distance on the set of positive probability measures on V t0, 1u, as an illustration of the constructions of Section 3.

As reference framework we choose

L ˆ´1 1 1 ´1 ṡo
π " p1{2, 1{2q and the corresponding edge set is E " tp0, 1q, p1, 0qu. Any ρ P P `pV q writes p1 ´ρp1q, ρp1qq, where ρp1q P p0, 1q. From now on, to simplify notations, ρ is identified with ρp1q which is denoted ρ P p0, 1q. We consider the Metropolis choice of generators described in (21): @ ρ P p0, 1q, L ρ " ˆ´ρp0, 1q ρp0, 1q ρp1, 0q ´ρp1, 0q ẇith ρp0, 1q " 1 ^ρ 1 ´ρ ρp1, 0q " 1 ^1 ´ρ ρ

Any vector field F P ΣpEq is determined by the value F p0, 1q P R which will simply be denoted F P R in the sequel. Note that in the present situation, any vector field is a gradient field. With this convention, the Markov generator (18) is given by @ ρ P p0, 1q, @ F P R, L ρ,F "

$ ' ' ' ' & ' ' ' ' % ˆ´F ρp0, 1q F ρp0, 1q 0 0 ˙, if F ě 0 ˆ0 0 ´F ρp1, 0q F ρp1, 0q ˙, if F ă 0
We also compute that, as in (20) and with the above notations, @ ρ P p0, 1q, @ F P R, }F } Let be given ρ 0 , ρ 1 P p0, 1q, the distance Dpρ 0 , ρ 1 q defined in (25) is described by D 2 pρ 0 , ρ 1 q " 2 min "ż 1 0 rρ t ^p1 ´ρt qsF 2 t dt : pF t q tPr0,1s P Dpρ 0 , ρ 1 q * (39)

where pρ t q tPr0,1s is the solution of (38) and where Dpρ 0 , ρ 1 q is the set of stepwise continuous mappings r0, 1s Q t Þ Ñ F t P R which are such that the corresponding pρ t q tPr0,1s does start at ρ 0 and end at ρ 1 . Indeed, our previous continuity assumption can be relaxed into stepwise continuity by classical arguments of regularization by convolution.

To compute Dpρ 0 , ρ 1 q, there is no loss of generality in assuming that ρ 0 ď ρ 1 and even ρ 0 ă ρ 1 , since Dpρ 0 , ρ 0 q " 0. Furthermore, we can restrict our attention to non-negative r0, 1s Q t Þ Ñ F t P R `. Indeed, if we have F t 0 ă 0 for some t 0 P r0, 1s, then, since 9 ρ t has the same sign as F t for all t P r0, 1s, we can find t 1 ă t 2 P r0, 1s with t 0 P pt 1 , t 2 q such that ρ t 1 " ρ t 2 . It follows that in the minimization (39), it is advantageous to replace pF t q tPr0,1s by pG t q tPr0,1s defined by @ t P r0, 1s, G t " 0 , if t P rt 1 , t 2 s F t , otherwise since pG t q tPr0,1s P Dpρ 0 , ρ 1 q and ż 1 0 rρ t ^p1 ´ρt qsF 2 t dt ą ż 1 0 rρ t ^p1 ´ρt qsG 2 t dt

Let us consider the case where ρ 0 ě 1{2. The situation where ρ 1 ď 1{2 can be treated similarly and the case where ρ 0 ă 1{2 and ρ 1 ą 1{2 is deduced by writting Dpρ 0 , ρ 1 q " Dpρ 0 , 1{2q `Dp1{2, ρ 1 q.

Lemma 17 For 1{2 ď ρ 0 ă ρ 1 , we have Dpρ 0 , ρ 1 q " 4p a 1 ´ρ0 ´a1 ´ρ1 q

Proof

Assuming, as we are allowed to, F t ě 0 for any t P r0, 1s, (38) reduces to @ t P r0, 1s, 9 ρ t " p1 ´ρt qF t since ρ t ě 1{2 for all t P r0, 1s. We deduce that @ t P r0, 1s, ρ t " 1 ´p1 ´ρ0 q expp´φ t q where @ t P r0, 1s, φ t " ż t 0 F s ds It appears that pF t q tPr0,1s belongs to Dpρ 0 , ρ 1 q if and only if φ 1 " ln ˆ1 ´ρ0 1 ´ρ1

˙(40)

Introduce the mapping h defined on R `via @ u P R `, hpuq ż u 0 a p1 ´ρ0 qe ´q dq so that ż 1 0 rρ t ^p1 ´ρt qsF 2 t dt "

ż 1 0 p1 ´ρt qF 2 t dt " ż 1 0 ph 1 pφ t q 9 φ t q 2 dt
The optimization problem (39) amounts to minimize twice the above r.h.s. under the condition hpφ 1 q " h ˆln ˆ1 ´ρ0 1 ´ρ1

˙˙ A which is equivalent to (40). Writing for any t P r0, 1s, ϕ t h 1 pφ t q 9 φ t , we are led to the simple problem of minimizing ş 1 0 ϕ 2 t dt under the contraint ş 1 0 ϕ t dt " A. It is well-known that the minimizer r0, 1s Q t Þ Ñ ϕ t is constant and so we end up with A 2 for the minimal value.

Thus we have shown that which is the desired result.

D 2 pρ 0 , ρ 1 q 2 " h 2 ˆln ˆ1 ´ρ0

  remains to check that for any ∇U P G and any G P Ipπq are π-orthogonal. By definition we have xx∇U, Gyy π "

			ÿ
			pU pyq ´U pxqqGpx, yq πpxqLpx, yq
		x,yPV
	By symmetry, we have
	ÿ
	x,yPV	U pyqGpx, yq πpxqLpx, yq "	´ÿ x,yPV	U pxqGpx, yq πpxqLpx, yq
	so that
		xx∇U, Gyy π "	´2 ÿ	U pxqGpx, yq πpxqLpx, yq
			x,yPV
		" ´2πrU divpGqs
		" 0

  Lp r Xr0, T sq and LpXr0, T sq of r Xr0, T s and Xr0, T s are equivalent and the Radon-Nikodym derivative of Lp r Xr0, T sq with respect to LpXr0, T sq is given by where for any px, yq P E, N T px, yq is the number of jumps of Xr0, T s from x to y and

	dLp r Xr0, T sq dLpXr0, T sq	" exp	¨ÿ px,yqPE	ln	˜r Lpx, yq Lpx, yq	¸NT px, yq	´ż T 0	HpX t q dt '
		@ x P V,	Hpxq	r Lpx, xq ´Lpx, xq
	For a proof of this result, see e.g. the lecture notes [12].

  Given a continuous curve r0, 1s Q t Þ Ñ F t P R, Equation (24) writes @ t P r0, 1s,9 ρ t " " p1 ´ρt qF t ρ t p0, 1q , if F t ě 0 ρ t F t ρ t p1, 0q , if F t ă 0

	" rρ ^p1 ´ρqsF t	(38)
	ρ " 2	ÿ

x‰yPV F 2 px, yqρpxqL ρ px, yq " 2rρ ^p1 ´ρqsF

2

* Fundings from the grants ANR-17-EURE-0010 and AFOSR-22IOE016 are acknowledged.